Does a minimal order-2 additive basis with $a_k\sim ck^2$ exist? (Erdős #326)
Statement
A set $A=\{a_1<a_2<\cdots\}\subseteq\mathbb{N}$ is a basis of order $2$ if every sufficiently large integer is a sum of two elements of $A$; it is minimal if no proper subset of $A$ is a basis of order $2$ (deleting any single element leaves infinitely many integers with no representation). Does there exist a minimal basis $A$ of order $2$ such that $$\lim_{k\to\infty}\frac{a_k}{k^2}=c$$ for some constant $c\neq 0$? Erdős and Graham conjectured that no such minimal basis exists.
Acceptance. FULLY RESOLVES: either (a) exhibit an explicit set $A$ with a complete proof (machine-checkable in Lean/Coq preferred, otherwise a full written proof) that $A$ is a basis of order $2$, that $A$ is minimal (for each $i$, deleting $a_i$ leaves infinitely many integers with no representation as a sum of two elements), and that $\lim_{k\to\infty}a_k/k^2=c$ for an explicit $c\neq 0$; or (b) prove that no minimal basis of order $2$ satisfies $\lim_k a_k/k^2=c\neq 0$, confirming the Erdős–Graham conjecture. ADVANCES: construct a minimal basis of order $2$ with $0<\liminf_k a_k/k^2\le\limsup_k a_k/k^2<\infty$ (bounded, without the full limit), with proof; or prove non-existence under an added regularity hypothesis on $A$; or rule out an explicit broad class of constructions. Deliver the construction with its three proofs, or the impossibility proof.
Background
Posed by Erdős and Graham [ErGr80, p.47]. The growth condition $a_k\sim ck^2$ is equivalent to the counting bound $\lvert A\cap[1,x]\rvert\sim (x/c)^{1/2}$, i.e. the sparsest density a basis of order $2$ can have (covering $[1,x]$ by pairwise sums forces $\gg x^{1/2}$ elements). Erdős originally asked the question for an arbitrary (not necessarily minimal) basis of order $2$, and Cassels [Ca57] constructed such a basis achieving $a_k\sim ck^2$; the difficulty here is the minimality constraint, which makes every element essential and tends to force the sequence to grow irregularly. Erdős and Graham conjectured a negative answer — that minimality is incompatible with the clean asymptotic $a_k\sim ck^2$. Listed as open on erdosproblems.com/326 (fetched 2026-07-21, status 'open'); a Lean formalisation of the statement exists in the DeepMind formal-conjectures project. A distinct venue neighbour is the finite problem of the minimal $2$-basis of $\{0,\ldots,n\}$ (Erdős #791), which concerns basis size rather than an infinite minimal basis with a density asymptotic. Attacker's tool: explicit construction (perturbations of the squares or of Cassels-type bases) together with a proof of minimality via an essential-element/covering argument, or a structural impossibility proof; plus computational search over greedy and randomised minimal bases to test whether $a_k/k^2$ can be driven to a nonzero limit.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #326 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #326 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.