Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open

Statement

The full Erdős problem #749 (Erdős, "Some problems in number theory, combinatorics and combinatorial geometry," *Math. Pannon.* (1994), 261–269, [Er94b, p.263]) asks:

> Let $\varepsilon>0$. Does there exist $A\subseteq\mathbb N$ such that the lower asymptotic density of $A+A$ is at least $1-\varepsilon$, yet the representation function $1_A\ast 1_A(n)\ll_\varepsilon 1$ for all $n$ (i.e. uniformly bounded by a constant depending only on $\varepsilon$)?

This lower-density case remains OPEN as of the 2026-07-02 site status. Erdős was unsure whether the answer should be yes or no; he was more confident about a companion question with upper density in place of lower density, writing (with Sárközy) that he believed bounded representation should force upper density of $A+A$ *strictly below* $1-\varepsilon$ (for some $\varepsilon_C$ depending on the bound $C$) — i.e. he expected the upper-density analogue to have a negative answer.

The upper-density variant is SOLVED, and the answer is the opposite of what Erdős expected — YES:

> Theorem (Bhalla, 2026). For every $\varepsilon>0$ there exists $A\subseteq\mathbb N$ such that the upper asymptotic density $\overline d(A+A)\ge 1-\varepsilon$, and yet $r_A(n):=1_A\ast1_A(n)\ll_\varepsilon 1$ for all $n\in\mathbb N$ — concretely $r_A(n)\le 144k+72$ for any integer $k$ with $1/(2k)<\varepsilon$.

This page documents that solved upper-density result and, most importantly for downstream use, the *technique* that produced it, since the same construction toolkit is the current live attack on the still-open lower-density case (which is the version logically adjacent to the famous Erdős #28 — additive basis forces unbounded representations Erdős–Turán conjecture on additive bases).

Facts

- This is a partial resolution, not a resolution of the whole #749 page. erdosproblems.com's own status tag for #749 remains OPEN — that status tracks the harder *lower*-density question. The *upper*-density sub-question is the one that is fully solved and is the subject of this page. - Solver and date: Aron Bhalla, with the assistance of GPT-5.4 Thinking, "On an Upper-Density Variant of an Erdős Problem" (self-hosted PDF, linked from erdosproblems.com/749; page last edited 6 April 2026). Per Erdős #28 — additive basis forces unbounded representations's independently-verified Facts, the result was posted 4 April 2026 and subsequently verified independently by Nat Sothanaphan on the erdosproblems.com forum thread for #749. - Why upper density is the tractable direction: upper density only needs *some* sequence of scales $X_j\to\infty$ on which $A+A$ covers a $(1-\varepsilon)$-fraction of $[1,X_j)$ — it does not need this to hold eventually for *all* large $X$ the way lower density would. This lets the construction concentrate all its "coverage work" on a sparse, self-chosen sequence of exponentially-separated intervals and say nothing about what happens between them. - Precise quantitative bound: $r_A(n)\le 144k+72$ where $k$ is any integer with $1/(2k)<\varepsilon$ — i.e. the bound on the representation function is $O(1/\varepsilon)$, linear in $1/\varepsilon$, not just "some function of $\varepsilon$." - Ancestor lemmas reused, not reproven from scratch: the modular building block (a set $B\subset\mathbb Z_p^2$, union of three parabolas $Q_a,Q_b,Q_c$ over $\mathbb Z_p$ with $a,b,c$ built from a quadratic nonresidue $m\bmod p$) is a simplified, self-contained variant of a construction due to Y.-G. Chen, "The analogue of Erdős–Turán conjecture in $\mathbb Z_m$," *J. Number Theory* 128 (2008), 2573–2581 (Chen's sharper bound: representation counts in $\{1,\dots,16\}$; Bhalla uses a weaker, easier-to-prove bound of $18$), as adapted by G. Liang, Y. Zhang, H. Zuo, "Additive and subtractive bases of $\mathbb Z_m$ in average," arXiv:2407.02344. - Formalization: the erdosproblems.com page for #749 links a Lean statement at google-deepmind/formal-conjectures/.../ErdosProblems/749.lean — this formalizes the still-open lower-density statement (the headline #749 question), not Bhalla's solved upper-density theorem. - **Relation to the flagship open problem Erdős #28 — additive basis forces unbounded representations:** the classical Erdős–Turán conjecture on additive bases (Erdős #28 — additive basis forces unbounded representations) asks about *density-1* (full basis) sets and claims $\limsup r_A(n)=\infty$ always. #749 is the natural "density-relaxed" interpolation: instead of forcing full density-1 coverage, only require density $\to 1-\varepsilon$ as $\varepsilon\to0$, and ask if boundedness can then survive. Per Erdős #28 — additive basis forces unbounded representations's own page, Terence Tao observed on the #28 forum thread (5 Apr 2026) that a counterexample to #28 would immediately yield a positive answer to #749's lower-density case for every $\varepsilon$ — making #749's lower-density case a genuine logical stepping-stone toward #28, while the (now solved) upper-density case is a strictly easier cousin that does not by itself say anything about #28.

Solution

Answer to the upper-density variant: YES, arbitrarily-high upper density is compatible with a uniformly bounded (in fact $O(1/\varepsilon)$) representation function.

The transferable technique — three nested layers: (1) a bounded-multiplicity finite-field parabola basis, (2) block/packet amplification, (3) lacunary-scale gluing.

1. Layer 1 — modular parabola basis (the reused Chen/Liang–Zhang–Zuo ingredient). For a prime $p>11$, pick a quadratic nonresidue $m\bmod p$ avoiding three forbidden residues, set $a=m+1,\ b=m(m+1),\ c=2m$, and let $B=Q_a\cup Q_b\cup Q_c\subset\mathbb Z_p^2$ be the union of three parabolas $Q_k=\{(u,ku^2):u\in\mathbb Z_p\}$. A short quadratic-character computation ($\chi$ the Legendre symbol) shows every pair $(x,y)\in\mathbb Z_p^2$ has between $1$ and $18$ ordered representations as a sum of two elements of $B$ (the $\lambda+\mu\ne0$ nondegeneracy for all $(\lambda,\mu)\in\{a,b,c\}^2$, plus $\chi(y-mx^2)+\chi(m(y-mx^2))$ pairing to force at least one of two symmetric quadratics to have a root). Lifting $B$ via $(u,v)\mapsto u+2pv$ and taking $A=A_1\cup(A_1+p)$ turns this into a genuine additive basis of $\mathbb Z_{2p^2}$ with representation function bounded by $72$ and short intervals sparse (≤18 points per length-$<2p$ window) — this is the "base block." 2. Layer 2 — packets amplify coverage while keeping the bound additive in $k$, not multiplicative. Concatenating $k$ shifted copies of the base block into a packet $Q^{(p)}=\bigcup_{j<k}(A^{(p)}+jm_p)$ preserves near-total coverage (misses at most $m_p$ residues out of $2km_p$, i.e. a *shrinking* miss-fraction $\sim1/(2k)$ as $k$ grows) while the representation-function bound only grows linearly in $k$ ($\le144k$), because any fixed target residue only has $O(1)$ "which pair of blocks" choices to worry about — the key counting fact (Claim 3.1) is that at most $2$ modular residues and at most $k$ block-pair choices per residue contribute, not $k^2$. 3. Layer 3 — recursive lacunary gluing turns a finite trick into an $\varepsilon$-parametrized infinite set. Fix $\varepsilon>0$, choose $k$ with $1/(2k)<\varepsilon$, and place disjoint packets $P_1,P_2,\dots$ at rapidly growing, super-doubling scales ($x_j=2M_{j-1}+1$, i.e. each new packet starts *after* twice the largest sum reachable by everything placed so far). This scale-separation is the crux: it guarantees no cross terms between old and new packets can collide with sums *within* a single new packet, so the induction step only ever has to add three bounded contributions ($P_j+P_j\le144k$, plus two "mixed" terms $F_{j-1}+P_j$ and $P_j+F_{j-1}$, each $\le36$ by the short-interval sparsity fact) — giving the final uniform bound $r_A(n)\le144k+72$ for every $n$, independent of how many packets have been laid down. Density is then read off on the self-chosen sequence of intervals $[2x_j,X_j)$ where each packet's sumset lives, giving $\overline d(A+A)\ge1-1/(2k)>1-\varepsilon$ in the limit. 4. Why this is the reusable idea for the still-open lower-density case and for #28. The whole construction is an instance of a general recipe: *build a finite gadget with a provably bounded, small representation constant and near-total local coverage (a "block"), then amplify the constant only linearly by concatenating $k$ blocks (a "packet"), then glue infinitely many packets across scales separated fast enough that cross-terms vanish.* Per Erdős #28 — additive basis forces unbounded representations's independently-verified page, this exact recipe (there filed under Finite-field parabola/Sidon-block construction with lacunary-scale gluing) is what Tao, Bhalla and Sothanaphan are now trying to push through for the lower-density case — which needs coverage on *every* sufficiently large interval, not just a self-chosen lacunary subsequence, so the scale-separation trick that makes the upper-density case easy is exactly the obstruction that makes the lower-density case (and hence progress toward #28 itself) hard. Tao's "$K$-scale toy problem" (posed live on the #749 forum, active through June 2026) is precisely the request to make the packet-coverage constant in Layer 2 uniform across $K$ nested scales simultaneously, rather than usable one scale at a time as in Bhalla's proof.

Bottom line for downstream use: block-with-bounded-multiplicity → linear-in-$k$ packet amplification → scale-separated lacunary gluing is the transferable three-layer machine. It fully cracks any "$\exists\varepsilon\to0$ density with bounded representation" question that only needs coverage on a *self-chosen* subsequence of scales (upper density); it does not yet crack the version needing coverage on *every* scale (lower density), which is the harder, still-open form directly adjacent to the 85-year-old Erdős–Turán conjecture Erdős #28 — additive basis forces unbounded representations.

Related

- Erdős #28 — additive basis forces unbounded representations — the parent Erdős–Turán conjecture on additive bases (density-1 case; $\limsup r_A(n)=\infty$ conjectured, prize \$500, OPEN). #749 is its density-relaxed interpolation; a counterexample to #28 would resolve #749's harder lower-density case for every $\varepsilon$ (Tao, forum, 5 Apr 2026, per #28's page). - Finite-field parabola/Sidon-block construction with lacunary-scale gluing — the reusable technique this page documents in detail: parabola-union blocks in $\mathbb F_p^2$ → linear-cost packet amplification → lacunary-scale gluing; already flagged on Erdős #28 — additive basis forces unbounded representations as "the live construction toolkit for #749/#28-adjacent work." - Y.-G. Chen, "The analogue of Erdős–Turán conjecture in $\mathbb Z_m$," *J. Number Theory* 128 (2008), 2573–2581 — source of the sharper ($\le16$) modular representation-count lemma that Bhalla's Layer-1 block is a simplified variant of. - G. Liang, Y. Zhang, H. Zuo, "Additive and subtractive bases of $\mathbb Z_m$ in average," arXiv:2407.02344 — the modular-basis-in-$\mathbb Z_{2p^2}$ construction Bhalla's Layer 1 directly adapts. - Ruzsa (1990), *Monatsh. Math.* 109, 145–151 — earlier, weaker ($L^2$-only) partial-progress result on the same density/boundedness tension for genuine bases; explicitly distinguished in Erdős #28 — additive basis forces unbounded representations's Facts as *not* answering either #749 case (an $L^2$ bound says nothing about the $L^\infty$ question these problems ask).