Finite-field / projective-plane constructions for extremal additive sets

Statement

The umbrella technique. A recurring and unusually powerful move across extremal additive/combinatorial number theory: realize the object you want to build (a Sidon/$B_h$ set, a difference set, a $C_4$-free graph, a sum-covering set, a sum-free set) as an explicit algebraic subset of a finite field $\mathbb F_q$, an extension $\mathbb F_{q^h}$, or the projective space $PG(n,q)$ over $\mathbb F_q$, for a prime power $q$ chosen near the target scale — then prove the required extremal property (no collisions, no repeated differences, no 4-cycle, bounded multiplicity) not by counting/probability but by an exact algebraic identity: either (a) an incidence axiom of finite projective/affine geometry (two points determine a unique line; a polarity fixes an orthogonality relation), or (b) a root-counting bound (a nonzero polynomial of degree $d$ over a field has at most $d$ roots), or (c) a Weil-type character-sum bound controlling the number of solutions of a polynomial equation over $\mathbb F_q$ to within $O(\sqrt q)$ of the "expected" (uniform-random) count. This produces deterministic, explicit, often exactly-optimal-in-leading-order constructions, in contrast to the probabilistic method's existential (and usually non-constructive, non-exact) guarantees.

Canonical instances of the recipe

1. Singer / cyclic-orbit construction (Singer finite-field perfect difference set construction): the cyclic group $\mathbb F_{q^{n+1}}^\ast$ acts simply transitively on the points of $PG(n,q)$; the points of a fixed hyperplane, read along one orbit, form a $(v,k,\lambda)$-difference set. For $n=2$ this gives a perfect difference set of size $q+1$ in $\mathbb Z_{q^2+q+1}$ — simultaneously a maximum Sidon set and the line-structure of $PG(2,q)$.

2. Bose–Chowla logarithm construction (Bose, Chowla, *Theorems in the additive theory of numbers*, Comment. Math. Helv. 37 (1962), 141–147; recap via arxiv.org/pdf/2104.12711): fix a generator $\theta$ of $\mathbb F_{q^h}^\ast$ and the discrete-log map $\log_\theta:\mathbb F_{q^h}^\ast\to\mathbb Z/(q^h-1)\mathbb Z$; select representatives (one per coset of $\mathbb F_q^\ast$, or via a fixed $\mathbb F_q$-basis of $\mathbb F_{q^h}$) so that a coincidence between two $h$-fold sums would force a nontrivial polynomial identity of bounded degree over $\mathbb F_{q^h}$ — impossible unless the sums are genuinely equal. Produces a $B_h$ set of size $\approx q$ inside $\mathbb Z_{q^h-1}$, matching order $N^{1/h}$; the $h=2$ case recovers (a variant of) Singer's Sidon construction, and generalizes it to triple sums ($B_3$, cf. Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets) and beyond.

3. Polarity-graph construction (Erdős, Rényi, "On a problem in the theory of graphs" (1962); Brown, "On graphs that do not contain a Thomsen graph," Canad. Math. Bull. 9 (1966), 281–285): vertices = points of $PG(2,q)$, edges = pairs $x\ne y$ with $x_0y_0+x_1y_1+x_2y_2=0$ (an orthogonal polarity / symmetric bilinear form). The projective-plane axiom "two points lie on a unique common line" transports, under polarity, into "$x,y$ have at most one common neighbor," i.e. the graph $ER_q$ is exactly $C_4$-free, with $q^2+q+1$ vertices and $\tfrac12q(q+1)^2$ edges — matching the Kővári–Sós–Turán upper bound $\mathrm{ex}(n,C_4)\le\tfrac12(1+\sqrt{4n-3})\,n/2$ in leading order. Tait (arXiv:1403.4489, J. Graph Theory 2016) proved the Cayley sum graph of a Bose–Chowla Sidon set is isomorphic to a large induced subgraph of $ER_q$ — i.e. constructions (2) and (3) are literally the same finite-field object viewed two ways.

4. Character-sum / Weil-bound constructions (quadratic-residue Paley graphs/tournaments; sum-product bound extremal sets over $\mathbb F_p$; "finite-field parabola" sumset-covering constructions): when no exact incidence axiom is available, Weil's theorem bounds the number of $\mathbb F_q$-points on an algebraic curve/variety (or, dually, the relevant character sum) to within $O(\sqrt q)$ of the uniform-random expectation, which is enough to certify *approximate* pseudorandomness (bounded collision multiplicity, near-uniform sumset coverage) deterministically. A live 2026 instance: Bhalla's finite-field-parabola/Sidon-block construction (credited to Liang–Zhang–Zuo, glued across scales à la Ruzsa 1990) resolving the upper-density case of Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open (see problems/28.md, this wiki).

Facts

- The two sub-mechanisms are provably the same object, not just analogous. Tait (arXiv:1403.4489) shows the Bose–Chowla Sidon-set/Cayley-sum-graph and the Erdős–Rényi–Brown polarity graph $ER_q$ are isomorphic on a large induced subgraph — the "logarithm in a cyclic extension field" and "orthogonal polarity of $PG(2,q)$" pictures are two coordinatizations of one underlying finite-field structure. - Prime-power indexing is a hard constraint, not a convenience. All of these constructions require $q$ to be a prime power (so that $\mathbb F_q$ exists); by the Bruck–Ryser–Chowla theorem, projective planes of order $\equiv1,2\pmod4$ must have order a sum of two squares, and no projective plane of *non*–prime-power order is known to exist — whether one exists is itself an open Erdős-adjacent question (cf. wiki/problems/552.md, "See also" erdos/723). Because primes are dense (gaps $O(p^{0.525})$, unconditionally), a suitable $q$ can always be found near any target scale $N$, which is the routine "approximate the target by a nearby prime power" step every transport-to-$[1,N]$ argument uses. - **These constructions are frequently *exactly* extremal in leading order, not just asymptotically good.** Because the mechanism is an exact combinatorial-design axiom (unique line through two points) rather than a probability estimate, Singer's and the Bose–Chowla/polarity-graph constructions match their respective matching upper bounds (Erdős–Turán for Sidon sets; Kővári–Sós–Turán for $C_4$-free graphs) in the leading term — a rarity flagged explicitly in the pseudorandomness/explicit-constructions literature, where "for most problems in extremal combinatorics... the probabilistic method gives the best known bound, and explicit constructions either give much worse bounds, or comparable bounds at the cost of technical tours de force" (framing per arxiv.org/pdf/cs/0601100-style surveys, via WebSearch synthesis) — finite-field/projective-plane constructions are the standard *exception* to that rule. - Weil's theorem is the "for free" pseudorandomness engine when no exact incidence axiom exists. Weil's bound on point-counts of curves/character sums over $\mathbb F_q$ gives deviation $O(\sqrt q)$ from the uniform-random expectation; this underlies quadratic-residue (Paley) constructions and the modern sum-product/finite-field-parabola constructions, where — unlike Singer/Bose–Chowla — the collision bound is *near*-zero (bounded multiplicity) rather than *exactly* zero. - The technique family is explicitly reused across this wiki's problem corpus: Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets (Bose–Chowla for $B_3$ sets vs. Green's matching upper bound), Erdős #552 — Ramsey number R(C4,Sn), dip below n+√n? (polarity graphs for the $C_4$-vs-star Ramsey number, exact values only near the prime-power subsequence $n\approx q^2$), Erdős #1029 — polynomial-factor lower bound $R(k)/(k2^{k/2})\\to\\infty$ (a *different* finite-field pseudorandom-graph construction, Conlon–Ferber's quadratic-form-over-$\mathbb F_q^t$ multicolor Ramsey lower bound, arXiv:2009.10458 — showing the "algebraic pseudorandomness" idea generalizes past Sidon/difference-set territory into Ramsey theory), and Erdős #28 — additive basis forces unbounded representations (2026-live finite-field-parabola Sidon-block gluing, the Weil-bound-flavored sub-case).

Technique

WHY it works (the mechanism, in two flavors).

*Flavor A — exact incidence transport.* Finite projective/affine geometry's defining axiom ("two distinct points lie on exactly one common line," or its dual/polarity form "two points have at most one common neighbor under an orthogonal polarity") is *itself* a difference-set / $C_4$-free identity once the points are identified with residues via a cyclic group action (a Singer cycle) or a fixed bilinear form. No counting or randomness is needed to verify the extremal property — it is baked into the geometry's own combinatorial design axioms. This is why these constructions are exact optima, not near-optima.

*Flavor B — root-counting / Weil-bound transport.* When the target property is "no two $h$-tuples sum/collide," encode a purported collision as a polynomial identity over $\mathbb F_{q^h}$ (Bose–Chowla) or bound the number of $\mathbb F_q$-points on the relevant algebraic curve/variety via Weil's theorem (quadratic-residue and parabola-type constructions). "A nonzero polynomial of degree $d$ has $\le d$ roots" (exact) or "the point-count deviates from $q$ by $O(\sqrt q)$" (near-exact) then forces the required rarity of collisions.

HOW to use it to prove things (recombination steps)

1. Identify the counting identity the problem's extremal bound comes from (e.g. $\binom{k}{2}\le N-1$ for Sidon sets; Kővári–Sós–Turán for $C_4$-free graphs; a root-count bound for $B_h$-set collisions). 2. Pick a prime power $q$ at the right scale (near $\sqrt N$ for Sidon-type problems, near $\sqrt n$ for $C_4$-free-graph problems on $n$ vertices, etc.) — always possible by prime density. 3. Coordinatize the target object as points/cosets/orbits inside $\mathbb F_q$, $\mathbb F_{q^h}$, or $PG(n,q)$: a Singer-cycle orbit, a discrete-log-selected coset family, or a polarity/quadratic-form adjacency. 4. Certify the extremal property algebraically — via an incidence axiom (Flavor A, exact) or a root-count/Weil bound (Flavor B, near-exact) — rather than by union-bound/second-moment probabilistic estimates. 5. Transport back to $\mathbb Z$, $\{1,\dots,N\}$, or an $n$-vertex graph via coset representatives, base-$q$ digit expansion, or the direct point/edge identification — this step is usually a one-line "the map is injective on the relevant range" argument. 6. **When it does *not* apply**: (a) genuinely *unbounded*-order patterns (arbitrarily long APs, general Szemerédi-type statements) are not directly amenable — that regime belongs to the polynomial method / density-increment machinery (Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt)), a mechanistically different toolkit; (b) the construction only exists at prime-power scales, so problems needing *every* scale $N$ (not just a dense subsequence) need an extra "round to nearest prime power" transport step, which can cost lower-order terms; (c) Flavor-A (exact) constructions do not extend past the specific small family of geometric identities available (difference sets, polarity/$C_4$-free graphs) — most modern extensions (multicolor Ramsey, sumset-covering) are Flavor-B (Weil-bound, near-exact) and inherit an $O(\sqrt q)$ error term that exact constructions do not have.

WHEN it applies: any extremal additive/combinatorial problem whose obstruction is a *counting/incidence* identity (distinct sums, distinct differences, no short cycle, bounded multiplicity, bounded sumset overlap) that can be re-expressed as an incidence, root-count, or point-count statement over a finite field or projective space — i.e. essentially any "how large/dense can a set avoid a fixed small algebraic coincidence" question at a computable, explicit scale.

Related

- Singer finite-field perfect difference set construction — the $n=2$ cyclic-orbit special case (Flavor A), the specific mechanism behind the classical Sidon-set lower bound. - Sidon sets / B_2 sets / Golomb rulers — the central combinatorial object (Sidon/$B_h$/Golomb-ruler sets) this technique family produces extremal examples of; already tags itself finite-field-constructions. - Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt) — the sibling toolkit for *unbounded*-order patterns (long APs, cap sets); mechanistically distinct (tensor-rank/degree sandwiches vs. incidence/root-count transport) though both are "finite-field-flavored." - Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — Sidon-set-size problem $h(N)$; Singer's construction gives the matching-leading-term lower bound. - Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets — $B_3$-set analogue; Bose–Chowla's finite-field construction vs. Green's matching Fourier upper bound. - Erdős #552 — Ramsey number R(C4,Sn), dip below n+√n? — $C_4$-vs-star Ramsey number; exact values match the Erdős–Rényi–Brown polarity-graph construction precisely on the prime-power subsequence $n\approx q^2$, and are open elsewhere. - Erdős #1029 — polynomial-factor lower bound $R(k)/(k2^{k/2})\\to\\infty$ — diagonal Ramsey numbers; Conlon–Ferber's quadratic-form-over-$\mathbb F_q^t$ construction (arXiv:2009.10458) is a structurally analogous (Flavor B) finite-field pseudorandom-graph technique that currently only closes the multicolor ($r\ge3$) case. - Erdős #28 — additive basis forces unbounded representations — live 2026 finite-field-parabola/Sidon-block construction (Bhalla, credited to Liang–Zhang–Zuo, glued à la Ruzsa 1990) resolving the upper-density case of the adjacent problem Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open; a Flavor-B (Weil-bound-flavored) instance of this technique family. - Erdős #1191 — how small can an infinite Sidon set's liminf density be? — Golomb-ruler/$\gamma$-difference-set generalization; O'Bryant's 2026 block-energy method is the *impossibility*-side counterpart that pairs with this technique's constructions. - Concept referenced but not yet its own page: "polarity graph" (Erdős–Rényi 1962 / Brown 1966 orthogonal-polarity construction of $C_4$-free extremal graphs) and "finite-field Sidon-parabola construction" (Bhalla/Ruzsa/Liang–Zhang–Zuo, live 2026) — both cited above as instances of this umbrella technique, flagged here as natural next concept pages.