Erdős Problem #749

Round-2 continuation for Erdős Problems 741, 749, 750

This is a genuine continuation of the previous round. I only use Round-1 material when explicitly indicated below, and I only re-prove statements when they are strengthened.

Conventions for this continuation: $\overline d(\cdot)$ and $\underline d(\cdot)$ denote upper and lower asymptotic density in $\mathbb N$, and when discussing Problem 750 it is enough to work with induced subgraphs, since deleting edges can only increase the independence number.

---

Problem 749

1) ROUND-2 OBJECTIVE

Path (C): prove a rigorous asymptotic obstruction that is substantially sharper than the Round-1 bound $A(x)\ll \sqrt{x}$.

The goal of this round is to show that any hypothetical solution must in fact be quadratically parameterized: if $A=\{a_1<a_2<\cdots\}$, then necessarily \[ a_n=\Theta(n^2), \] with explicit constants depending only on $\epsilon$ and the representation bound.

2) Round-1 FOUNDATION USED

I use exactly two Round-1 facts.

• Round-1 proved the coarse necessary bound $A(x)\ll \sqrt{x}$ from bounded representation.
• Round-1 observed that the real obstacle is compatibility across scales, not finite-model feasibility.

In this round I sharpen the first point from a coarse counting estimate in $x$ to a precise estimate in terms of the ordered sequence $a_n$.

3) NEW INSIGHT / TOOL (ROUND-2)

The key observation is to evaluate the density condition at the special cutoff \[ N=a_{n+1}-1. \] Since every sum $\le N$ uses only the first $n$ elements of $A$, one gets a direct upper bound on $a_{n+1}$ from the maximum possible number of distinct sums of an $n$-element set. Combined with the bounded-representation lower bound, this traps $a_n$ between two quadratic curves.

4) ATTACK PLAN (ROUND-2)

The exact gap left by Round-1 was:

Can we say anything more precise than $A(x)\asymp \sqrt{x}$ about the shape of a candidate set?

I will prove two complementary bounds.

Theorem 749.1. Let $A=\{a_1<a_2<\cdots\}\subseteq\mathbb N$.

1. If $\underline d(A+A)\ge 1-\epsilon$, then for every $\eta>0$ there exists $n_0(\eta)$ such that \[ a_{n+1}\le \frac{n(n+1)}{2(1-\epsilon-\eta)}+1 \qquad (n\ge n_0(\eta)). \] In particular, \[ \limsup_{n\to\infty}\frac{2a_n}{n^2}\le \frac{1}{1-\epsilon}. \]

2. If moreover $(\mathbf 1_A\ast \mathbf 1_A)(m)\le g$ for all $m$, then for every $n$, \[ a_n\ge \frac{n^2}{2g}. \] In particular, \[ \liminf_{n\to\infty}\frac{2a_n}{n^2}\ge \frac1g. \]

Hence any candidate for Problem 749 must satisfy \[ \frac1g\le \liminf_{n\to\infty}\frac{2a_n}{n^2} \le \limsup_{n\to\infty}\frac{2a_n}{n^2} \le \frac1{1-\epsilon}, \] and therefore \[ a_n=\Theta(n^2), \] while the counting function \[ A(x):=|A\cap[1,x]| \] satisfies \[ A(x)=\Theta(\sqrt x). \]

5) WORK (ROUND-2)

Proof of Theorem 749.1$1$. Fix $\eta>0$. Since $\underline d(A+A)\ge 1-\epsilon$, there exists $N_0(\eta)$ such that for all $N\ge N_0(\eta)$, \[ |(A+A)\cap[1,N]|\ge (1-\epsilon-\eta)N. \] Now take $N=a_{n+1}-1$. Any representation \[ m=a_i+a_j\le a_{n+1}-1 \] must use only indices $i,j\le n$, because $a_{n+1}+a_1>a_{n+1}-1$. Therefore \[ (A+A)\cap[1,a_{n+1}-1] \subseteq \{a_i+a_j:1\le i\le j\le n\}. \] The set on the right has cardinality at most the number of unordered pairs from an $n$-element set, namely $n(n+1)/2$. Hence, for all sufficiently large $n$, \[ (1-\epsilon-\eta)(a_{n+1}-1) \le \left|(A+A)\cap[1,a_{n+1}-1]\right| \le \frac{n(n+1)}{2}. \] So \[ a_{n+1}\le \frac{n(n+1)}{2(1-\epsilon-\eta)}+1. \] Dividing by $n^2/2$ and letting $n\to\infty$ yields \[ \limsup_{n\to\infty}\frac{2a_n}{n^2}\le \frac{1}{1-\epsilon-\eta}. \] Since $\eta>0$ is arbitrary, \[ \limsup_{n\to\infty}\frac{2a_n}{n^2}\le \frac{1}{1-\epsilon}. \] This proves $1$. $\square$

Proof of Theorem 749.1$2$. Assume \[ (\mathbf 1_A\ast \mathbf 1_A)(m)\le g \qquad\text{for all }m. \] Consider the $n^2$ ordered pairs $(a_i,a_j)$ with $1\le i,j\le n$. Each such pair produces a sum in $[2,2a_n]$. Since each integer is assumed to have at most $g$ ordered representations, the number of distinct sums produced by these $n^2$ pairs is at least $n^2/g$. But there are at most $2a_n-1$ positive integers in $[2,2a_n]$, so certainly \[ 2a_n\ge \frac{n^2}{g}. \] Equivalently, \[ a_n\ge \frac{n^2}{2g}. \] Dividing by $n^2/2$ gives \[ \frac{2a_n}{n^2}\ge \frac1g \] for every $n$, hence \[ \liminf_{n\to\infty}\frac{2a_n}{n^2}\ge \frac1g. \] This proves $2$. $\square$

Combining $1$ and $2$ gives the stated quadratic window.

6) ADVERSARIAL VERIFICATION

• Why $N=a_{n+1}-1$? This is essential. At that cutoff, no sum involving $a_{n+1}$ can appear, so only the first $n$ elements matter.
• Ordered vs. unordered representations. The upper bound in part $1$ counts distinct sums, so unordered pairs are correct. The lower bound in part $2$ uses the hypothesis on $(\mathbf 1_A\ast \mathbf 1_A)(m)$, which counts ordered representations, so $n^2$ ordered pairs are correct there.
• Lower density. Part $1$ uses only the definition of $\underline d(A+A)$ with an arbitrary $\eta>0$; no unjustified subsequence argument appears.
• No hidden assumption on $A(0)$. The argument uses only positivity of the elements and monotonicity of the sequence $(a_n)$.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round-2 proves a sharp structural obstruction:

Any solution of Problem 749 must come from a sequence $A=\{a_n\}$ with genuinely quadratic growth $a_n=\Theta(n^2)$, and the quadratic constant is trapped between $1/(2g)$ and $1/(2(1-\epsilon))$.

So the open problem is not merely about finding a sparse set of size $\asymp \sqrt{x}$; it is about building an almost extremal quadratic generalized Sidon-type sequence whose initial segments remain globally compatible.

This rules out an entire family of overly separated recursive strategies from Round-1.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 45%

9) REFERENCES

• T. F. Bloom, Erdős Problem #749, erdosproblems.com.

---

OBJECTIVE AND SOURCE REVIEW

Erdős #749; independent attempt, 2026-09-23. For every $\epsilon>0$, seek $A\subseteq\mathbb N$ with $\underline d(A+A)\ge1-\epsilon$ and uniformly bounded ordered representation function $r_A(m)$. I read the complete supplied 749.tex. Its quadratic bounds on the enumeration of a hypothetical $A$ are necessary conditions, not a construction. The indexed official entry distinguishes this lower-density question from the resolved upper-density variant.

WORK: A PRECISE FINITE COMPATIBILITY CRITERION

Fix $0<\delta<1$, an integer $g$, and $N_0$. The following two assertions are equivalent:

1. An infinite $A\subseteq\{1,2,\ldots\}$ satisfies $r_A(m)\le g$ for every $m$ and $|(A+A)\cap[1,n]|\ge\delta n$ for every $n\ge N_0$.
2. For arbitrarily large $N$, there is $B_N\subseteq[1,N]$ such that $r_{B_N}(m)\le g$ for every $m$, and $|(B_N+B_N)\cap[1,n]|\ge\delta n$ simultaneously for every $N_0\le n\le N$.

The forward implication uses $B_N=A\cap[1,N]$: a positive summand in a sum at most $n$ is at most $n$. For the converse, form the binary tree of all finite membership strings satisfying the displayed constraints up to their length. Prefixes remain valid, since deleting elements greater than $n$ cannot affect sums at most $n$, and cannot increase representation counts. There are nodes at arbitrarily large depths. At each node having arbitrarily deep descendants, at least one of its two children has arbitrarily deep descendants. Recursively choosing that child constructs an infinite branch. Its set $A$ satisfies every finite constraint. Positive $\delta$ forces $A$ infinite. Consequently the original question, with its quantifier over every $\epsilon$, is equivalent to the existence of such uniformly compatible finite witnesses for every $\delta<1$, with $g,N_0$ depending on $\delta$. In the forward direction choose a hypothetical lower density strictly greater than $\delta$, so the eventual inequality follows from the definition of liminf.

ADVERSARIAL VERIFICATION AND REMAINING GAP

Requiring coverage only at the terminal value $N$, or allowing the initial threshold $N_0$ to tend to infinity with $N$, destroys the prefix argument. Likewise $g$ must stay fixed as $N$ grows. Thus a sequence of isolated good finite blocks or a construction with good upper density does not supply the required tree. This is a standard compactness argument applied explicitly to this problem; it is not a new existence theorem. I have not constructed its finite witnesses with all intermediate-scale inequalities.

SOURCES CHECKED

The complete local 749.tex; indexed official entry https://www.erdosproblems.com/749; statement formalization https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/749.lean.

FINAL

UNRESOLVED. The missing uniform compatibility requirement is made exact, but no lower-density construction is obtained.

COMPLETION ESTIMATE

Subjective progress toward the original existence question, not a probability. COMPLETION: 8%

Problem 749: dense sumset with uniformly bounded representation function

1) FORMAL RESTATEMENT

Let $\epsilon>0$. Does there exist a set $A\subseteq \mathbb{N}$ such that

1. the lower density of the sumset is large: \[ \underline d(A+A)\ \ge\ 1-\epsilon, \] and
2. the additive convolution (ordered representation function) is uniformly bounded: \[ (\mathbf 1_A * \mathbf 1_A)(n)\ \ll_\epsilon\ 1 \qquad\text{for all }n\in\mathbb{N}? \]

Equivalently: can one make $A+A$ miss only an $\epsilon$-fraction of integers while ensuring that every integer has at most $C(\epsilon)$ representations as a sum of two elements of $A$?

2) QUICK LITERATURE/CONTEXT CHECK

Web browsing available? YES.

• The problem is listed as open on erdosproblems.com (Problem 749).
• It is closely related in spirit to the Erdős--Turán conjecture on additive bases of order $2$ (which would assert that if $A+A$ is eventually all integers, then $\sup_n (\mathbf 1_A*\mathbf 1_A)(n)=\infty$). Here we only ask $A+A$ to have density $1-\epsilon$, so a positive answer would not contradict Erdős--Turán.

3) ATTACK PLAN

• Necessary conditions: Derive growth restrictions on $A(x)=|A\cap[1,x]|$ from the uniform bound on $(\mathbf 1_A*\mathbf 1_A)(n)$.
• Finite-model search: For small $N$, search for $A\subseteq[0,N]$ with bounded representation counts and with $(A+A)\cap[0,N]$ large, to see what constants might be plausible.
• Candidate constructions: Try "block" or "recursive" constructions that (i) keep each sum represented $O(1)$ times, and (ii) cover most integers by sums coming from the same scale.
• Disproof attempts: Look for an information-theoretic obstruction: does bounded representation force a positive-density set of integers to be missing from $A+A$?

4) WORK

4.1 A basic necessary condition: $A$ must be $\sqrt{x}$-sized.

Assume there is a constant $g$ with $(\mathbf 1_A*\mathbf 1_A)(n)\le g$ for all $n$. For any $x$, \[ \sum_{n\le x} (\mathbf 1_A*\mathbf 1_A)(n) = |\{(a,a')\in A^2:\ a+a'\le x\}|. \] In particular, all pairs with $a,a'\le x/2$ contribute, so \[ |A\cap[1,x/2]|^2 \ \le\ \sum_{n\le x} (\mathbf 1_A*\mathbf 1_A)(n)\ \le\ gx. \] Hence \[ |A\cap[1,x]| \ \le\ |A\cap[1,x/2]| + |A\cap(x/2,x]|\ \ll\ \sqrt{g x}. \] So any solution must have density $0$ and must be of "critical" size $\asymp \sqrt{x}$.

4.2 Heuristic parameter count.

If $A(x)\asymp c\sqrt{x}$ then the number of ordered pairs $(a,a')\in A^2$ with $a+a'\le x$ is $\asymp c^2 x$. If in addition each $n$ has at most $g$ representations, then the number of represented $n\le x$ is at most $\asymp c^2 x/g$. To cover $(1-\epsilon)x$ integers up to $x$, one needs $c^2/g \gtrsim 1-\epsilon$. This is consistent with the necessary bound $A(x)\ll \sqrt{g x}$, and suggests that $g$ should need to grow at least on the order of $\log(1/\epsilon)$ in any probabilistic "Poisson"-type model.

4.3 Finite computations (evidence, not a proof).

I brute-forced small initial segments to see whether one can simultaneously: (i) keep $(\mathbf 1_A*\mathbf 1_A)(n)\le g$ for $n\le 2N$ and (ii) make $(A+A)\cap[0,N]=[0,N]$ (perfect coverage of the first block).

For $N\le 16$, there exist such sets already with $g=4$. For instance, for $N=16$ one example is \[ A=\{0,1,2,3,5,7,11,15\}\subseteq[0,16], \] for which all sums $0\le n\le 16$ occur at least once, and no sum $n\le 32$ has more than $4$ ordered representations. This suggests that a global construction with bounded representation may be plausible.

4.4 Why this still does not solve the infinite problem.

Extending a finite configuration to an infinite $A$ is nontrivial: adding new large elements creates new sums, but it can also create new representations for old sums (through mixing scales) unless scales are separated very carefully. Meanwhile, separating scales too much tends to destroy density of $A+A$.

5) VERIFICATION

• The $\sqrt{x}$-growth bound in §4.1 is rigorous and uses only counting pairs with sum $\le x$.
• The finite example in §4.3 was found by exhaustive search for small $N$; it is suggestive only, not a proof of existence of an infinite $A$.
• No step above asserts a full solution; it delineates constraints and provides computational evidence for feasibility at small scales.

6) FINAL

UNRESOLVED.

• What I have: A necessary growth constraint $A(x)\ll_{\epsilon}\sqrt{x}$ for any bounded-representation candidate, plus small-$N$ computational evidence that "cover $[0,N]$ with $g=O(1)$" is feasible in finite models (e.g. $g=4$ works for $N\le 16$).
• Where it breaks: Turning finite blocks into an infinite set without letting representations accumulate across blocks.
• Next moves:
  1. Develop a scale-separated recursive construction where new blocks are placed so that sums produced by distinct scale-pairs overlap only $O(1)$-fold.
  2. Prove (or disprove) a "bounded-overlap interval cover" lemma: choose intervals $I_k$ so that every large $n$ lies in many $I_k+I_k$ but in only $O(1)$ such sum-intervals, then populate each $I_k$ with a near-optimal $B_2[g]$-type set.
  3. Attempt a probabilistic construction with an explicit deletion scheme that caps $(\mathbf 1_A*\mathbf 1_A)(n)$ while keeping the uncovered set in $A+A$ of density at most $\epsilon$.
• Minimal lemma that would settle the problem (one plausible route): Construct for each $\epsilon>0$ a sequence of finite sets $A_k\subseteq[1,N_k]$ with \[ \max_{n\le 2N_k} (\mathbf 1_{A_k}*\mathbf 1_{A_k})(n)\le C(\epsilon), \qquad |(A_k+A_k)\cap[1,N_k]|\ge (1-\epsilon)N_k, \] and a compatibility condition ensuring that embedding $A_k$ into scale $k$ of a growing union does not increase representation counts of earlier scales.

7) COMPLETION

COMPLETION: 30% (necessary condition + computational evidence; full infinite construction remains open).

---