Finite-field parabola/Sidon-block construction with lacunary-scale gluing

Statement

The technique in one sentence. To build a set $A\subseteq\mathbb N$ whose sumset $A+A$ covers a *prescribed* fraction of the integers while the representation function $r_A(n)=\#\{(a,a')\in A^2:a+a'=n\}$ stays *uniformly bounded* (a tension at the heart of the Erdős–Turán conjecture on additive bases, Erdős #28 — additive basis forces unbounded representations), build a small modular block as a union of parabolas over $\mathbb F_p$, certify its bounded-multiplicity sumset-covering property with a quadratic-character (Legendre-symbol) computation, amplify it into a packet by concatenating $k$ shifted copies (cost: only *linear* in $k$, not quadratic), then glue infinitely many such packets at rapidly growing ("lacunary," super-doubling) scales so that cross-terms between packets at different scales can never collide with sums *inside* a single packet.

Layer 1 — the modular parabola block (Chen 2008 / Liang–Zhang–Zuo 2024 ancestor, Bhalla 2026 simplification). Fix a prime $p>11$ and a quadratic nonresidue $m\bmod p$ avoiding finitely many forbidden residues. Set $a=m+1$, $b=m(m+1)$, $c=2m$, and define $$Q_k=\{(u,ku^2):u\in\mathbb Z_p\}\subset\mathbb Z_p^2,\qquad B=Q_a\cup Q_b\cup Q_c.$$ A short computation with the Legendre symbol $\chi$ shows every target pair $(x,y)\in\mathbb Z_p^2$ has between $1$ and $18$ ordered representations as a sum of two elements of $B$: nondegeneracy $\lambda+\mu\ne0$ for all $\lambda,\mu\in\{a,b,c\}$ rules out the trivial failure mode, and the identity $\chi(y-mx^2)+\chi(m(y-mx^2))$ forces at least one of two symmetric quadratics to have a root, which is what certifies *coverage* (not just boundedness). Lifting via $(u,v)\mapsto u+2pv$ and setting $A_1=$ (lift of $B$), $A=A_1\cup(A_1+p)$ turns this into a genuine additive basis of $\mathbb Z_{2p^2}$ with $r_A\le72$ and at most $18$ points per length-$<2p$ window (short-interval sparsity).

Layer 2 — packet amplification (linear, not quadratic, in $k$). Concatenate $k$ shifted copies of the base block into a packet $Q^{(p)}=\bigcup_{j<k}(A^{(p)}+jm_p)$. This misses at most $m_p$ residues out of $2km_p$ — a *shrinking* miss-fraction $\sim1/(2k)$ — while the representation-function bound grows only linearly, $r\le144k$, because for any fixed target residue only $O(1)$ residue classes and at most $k$ block-pair choices actually contribute (not $k^2$, which a naive union bound would give).

Layer 3 — lacunary-scale gluing (Ruzsa-1990-style). Fix $\varepsilon>0$, pick $k$ with $1/(2k)<\varepsilon$, and lay disjoint packets $P_1,P_2,\dots$ at scales $x_j=2M_{j-1}+1$ where $M_{j-1}$ is the largest sum reachable by everything placed so far — i.e. each new packet starts after twice the reach of the old ones. This scale-separation guarantees no cross-collision between sums *within* a new packet and sums involving old material, so induction only ever adds three bounded contributions ($P_j+P_j\le144k$, plus two mixed terms $F_{j-1}+P_j$, $P_j+F_{j-1}\le36$ each by short-interval sparsity), giving a uniform bound $r_A(n)\le144k+72$ for every $n$, independent of how many packets have been laid down.

Resulting theorem (Bhalla, 2026). For every $\varepsilon>0$ there exists $A\subseteq\mathbb N$ with upper asymptotic density $\overline d(A+A)\ge1-\varepsilon$ and $r_A(n)\le144k+72$ for all $n$ (any integer $k$ with $1/(2k)<\varepsilon$) — 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, a density-relaxed cousin of the 85-year-old Erdős–Turán conjecture Erdős #28 — additive basis forces unbounded representations.

Facts

- Direct ancestor is a $\mathbb Z_m$ result, not originally about sumset density at all. Y.-G. Chen, "The analogue of Erdős–Turán conjecture in $\mathbb Z_m$," *J. Number Theory* 128 (2008), 2573–2581, proves a sharper modular representation-count lemma (bound $\le16$, vs. Bhalla's weaker but easier $\le18$); G. Liang, Y. Zhang, H. Zuo, "Additive and subtractive bases of $\mathbb Z_m$ in average," arXiv:2407.02344 (2024), independently confirmed extant via WebSearch this session, prove $\limsup_{m\to\infty}\ell_m\le144$ for additive bases of $\mathbb Z_m$ — the exact constant $144$ reused unchanged in Bhalla's Layer-2 packet bound, confirming the modular block is imported wholesale rather than reproven. - Why the parabola specifically, and why three of them. A single parabola $Q_k=\{(u,ku^2)\}$ over $\mathbb F_p$ is itself already a Sidon-type object (a graph of a quadratic map has bounded line-intersection multiplicity — at most 2 points per line, by "a quadratic equation has $\le2$ roots"), but one parabola alone does not have $\mathbb F_p$-plane-covering sumset density. Taking a union of three parabolas with algebraically related slopes $a=m+1,b=m(m+1),c=2m$ (all derived from a single quadratic-nonresidue seed $m$) is what pushes the sumset from "sparse" to "covers everything with multiplicity $O(1)$" — the three-way union is exactly calibrated so the quadratic-character coverage identity $\chi(y-mx^2)+\chi(m(y-mx^2))$ closes. - The core numeric asymmetry that makes packets cheap: linear-in-$k$, not quadratic-in-$k$. A naive union of $k$ independent Sidon-type blocks would be expected to cost $O(k^2)$ in representation-multiplicity (every pair of blocks can separately collide), but the packet construction's Claim 3.1 (per wiki/problems/749.md's reading of the Bhalla PDF) shows only $O(1)$ residue classes and $O(k)$ block-pair choices per residue actually contribute — this is the numerical fact that makes the $\varepsilon\to0$ limit achievable at all with a bound that stays finite (linear in $1/\varepsilon$, not exploding). - Upper density is the tractable direction; lower density is not (and this is the live open frontier). Upper density only requires $(1-\varepsilon)$-coverage on *some* self-chosen, exponentially-separated sequence of scales — exactly what lacunary gluing is built to deliver "for free," since scale-separation is precisely what makes cross-packet terms vanish. Lower density would require coverage on *every* sufficiently large interval, which is the opposite of what lacunary spacing buys you — Terence Tao (erdosproblems.com forum, 5 Apr–6 Jun 2026, per wiki/problems/28.md) reduced this harder case to an explicit still-open "$K$-scale toy problem": make the packet-coverage constant uniform across $K$ *nested* scales simultaneously, rather than usable one scale at a time. A counterexample to the full Erdős–Turán conjecture Erdős #28 — additive basis forces unbounded representations would resolve #749's lower-density case for every $\varepsilon$ (Tao, forum, 5 Apr 2026) — making this the closest live stepping-stone toward #28 as of mid-2026. - An easy trap the technique does NOT fall into: a prior, weaker, non-comparable partial result. Ruzsa (1990, *Monatsh. Math.* 109, 145–151) built a genuine basis with representation function bounded only *in square mean* ($\sum_{n\le N}r_A(n)^2=O(N)$) — an $L^2$ statement that says nothing about the $L^\infty$/limsup question #28 and #749 actually ask. This was explicitly flagged and then retracted as insufficient evidence on the #749 forum thread (per wiki/problems/28.md) — a caution that "bounded-on-average" constructions are a structurally different (and much easier) target than the "bounded-everywhere, for all $n$" property this parabola/packet/gluing construction actually delivers. - Credited AI assistance: Aron Bhalla resolved the upper-density case with GPT-5.4 Thinking's assistance (4 Apr 2026), independently verified by Nat Sothanaphan on the erdosproblems.com forum; this is one of a small number of erdosproblems.com results with credited AI co-investigation (cross-confirmed via github.com/teorth/erdosproblems wiki page "AI contributions to Erdős problems," WebSearch this session).

Technique

WHEN this applies. Reach for this construction whenever a problem asks for a set (or sequence of sets at growing scale) that must simultaneously (a) have its sumset (or a related bilinear/additive image) cover a *controllable fraction* of an ambient range, and (b) keep some representation/multiplicity function *uniformly bounded* — i.e. the "dense coverage vs. bounded collisions" tension that is the defining shape of the Erdős–Turán additive-basis conjecture family (Erdős #28 — additive basis forces unbounded representations, Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open, and by extension any "basis with bounded representation function" question). It is specifically the right tool when the target density only needs to be hit on a self-chosen (upper-density / lacunary) sequence of scales, not on every scale — see the Facts point above on why lower density resists the same machine.

WHY it works (the mechanism, three separable ideas stacked)

1. Exact algebraic certification, not counting/probability, for the base block. Coverage-with-bounded-multiplicity of the parabola union is proved by a closed-form quadratic-character identity ($\chi(y-mx^2)+\chi(m(y-mx^2))$ forcing a root), in the same spirit as the Weil-bound/root-counting "Flavor B" mechanism of the broader Finite-field / projective-plane constructions for extremal additive sets family: a nonzero low-degree polynomial condition has boundedly many failure cases, full stop, no asymptotics needed at this layer. This is what makes the *constant* ($18$, then $72$, then $144k+72$) explicit and small rather than an existential $O(1)$. 2. Sub-additive (not sub-multiplicative) cost of amplification. The move from "one bounded block" to "$k$ blocks covering more" would naively cost $O(k^2)$ (every pair of blocks can collide), but a residue-class pigeonhole argument (Claim 3.1 in Bhalla's proof) shows the *actual* collision cost is $O(k)$ — this sub-quadratic amplification is the numerical engine that lets $\varepsilon\to0$ (i.e. $k\to\infty$) be reached with a *finite*, linearly-growing bound rather than a blown-up one. Recognizing when an amplification step is secretly linear rather than quadratic is the transferable insight, independent of the specific parabola algebra. 3. Lacunary (super-doubling) scale separation eliminates cross-terms by construction. Placing each new packet strictly after twice the reach of everything already placed is a purely arithmetic device (no algebra, no character sums) that converts an unbounded induction (infinitely many packets) into a bounded one: the only terms that can ever appear in $r_A(n)$ for large $n$ are the block's own internal sum, plus two "boundary" mixed terms with the immediately preceding packet — never anything from packets further back. This is the exact same "scale-separation prevents cross-scale collision" idea used generically whenever a *finite* construction needs to be extended to an *infinite* one while preserving a uniform bound (cf. the blockwise zero-padding trick in Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue, a structurally analogous but algebraically distinct device for the same purpose: making an infinite union of finite gadgets behave, collision-wise, as if it were still just one finite gadget).

HOW to use it to prove things (recombination steps)

1. Isolate a finite modular sub-problem: find a prime $p$ (or prime power $q$) at the target local scale and a *small* algebraic object over $\mathbb F_p$ — here, a union of a few parabolas $Q_k=\{(u,ku^2)\}$ with carefully chosen slopes — whose sumset-coverage-with-bounded-multiplicity can be certified by an exact character-sum / quadratic-residue identity (not an asymptotic estimate). 2. Lift the modular block to the integers via a base-$p$ (or similar) digit expansion (here $(u,v)\mapsto u+2pv$), producing a finite integer set with the same bounded-multiplicity coverage property, now living in an explicit range $[1,M]$. 3. Amplify by concatenating $k$ shifted copies into a packet, and *verify the amplification cost is linear (or otherwise sub-quadratic) in $k$* via a residue-class/pigeonhole argument — this is the step that determines whether the whole method can reach an $\varepsilon\to0$ limit with a finite bound at all. 4. Glue packets across a lacunary (rapidly-growing, e.g. super-doubling) sequence of scales, placing each new packet strictly beyond the reach of everything already built, so that the only possible representation-function contributions at any point are (a) internal to the current packet and (b) a bounded number of "boundary" terms with the immediately preceding one. 5. Read off the target statistic (density, representation bound) as a limit over the self-chosen scale sequence — this last step is exactly where the method's reach *stops*: it certifies density on the scales *you* chose, not on every scale, so it directly proves upper-density statements but does not, by itself, prove lower-density (all-scales) statements. 6. When it does NOT directly apply: any statement requiring the bounded-coverage property to hold on *every* sufficiently large interval (not just a self-chosen subsequence) — i.e. lower-density rather than upper-density statements — defeats the lacunary-gluing step, because scale-separation is precisely what that step exploits, and there is no scale left to "hide" gaps in between packets. This is exactly why Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open's lower-density case, and the parent Erdős #28 — additive basis forces unbounded representations conjecture itself, remain open despite this construction fully cracking the upper-density analogue; Tao's live-2026 "$K$-scale toy problem" is the explicit attempt to force the packet bound to be uniform across many *nested*, not lacunarily-separated, scales simultaneously.

Related

- Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open — the problem this construction directly resolves the upper-density case of (Bhalla, 4 Apr 2026); the still-open lower-density case is this technique's known limit. - Erdős #28 — additive basis forces unbounded representations — the parent 85-year-old Erdős–Turán conjecture on additive bases ($500 prize, open); a counterexample to it would resolve #749's lower-density case, per Tao's forum observation, making this construction's extension the most concrete live line of attack. - Finite-field / projective-plane constructions for extremal additive sets — the broader umbrella family (Singer difference sets, Bose–Chowla, polarity graphs, Weil-bound constructions) of which this parabola/quadratic-character construction is a "Flavor B" (root-count / character-sum, near-exact rather than exactly-exact) instance; already flags this exact technique as a live 2026 example. - Sidon sets / B_2 sets / Golomb rulers — the parent combinatorial object family (distinct-sum/distinct-difference sets); this construction is a deliberate *relaxation* of strict Sidon-ness (bounded, not unique, multiplicity) traded for much higher coverage density, structurally parallel to the $B_h[g]$ relaxation discussed there. - Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue — a different technique family (log/discrete-log transfer + zero-padded digit blocks + probabilistic alteration) solving a structurally analogous "extend a finite trick to an infinite set without losing a uniform bound" problem for genuine (unrelaxed) Sidon sets; useful contrast for how "scale-separation to kill cross-terms" recurs with different algebraic engines underneath (digit zero-buffers there, lacunary integer gaps here). - Perfect additive basis / unique representation basis ($r_A\\equiv1$) — the $r(n)\equiv1$ extreme case that Konyagin–Lev show exists for most infinite abelian groups but is exactly the phenomenon Erdős #28 — additive basis forces unbounded representations conjectures is impossible over $\mathbb N$; this construction's bounded-but-not-unique representation function sits strictly between the perfect-basis ideal and the "unbounded" conjecture. - Y.-G. Chen, *J. Number Theory* 128 (2008), 2573–2581, and G. Liang–Y. Zhang–H. Zuo, arXiv:2407.02344 (2024) — the two ancestor papers whose modular representation-count lemmas (bounds $16$ and $144$ respectively) this construction's Layer 1/Layer 2 directly import.