Additive complements of the squares: minimise $\limsup \lvert A\cap[1,N]\rvert/N^{1/2}$ (Erdős #33)
Statement
Call $A\subset\mathbb{N}$ an additive complement of the squares if every sufficiently large integer can be written as $n^2+a$ for some integer $n\geq 0$ and some $a\in A$. What is the smallest possible value of $$\limsup_{N\to\infty} \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}$$ over all additive complements $A$ of the squares? Is it true that every such $A$ satisfies $$\liminf_{N\to\infty} \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}>1?$$ (The second question is known to have an affirmative answer — see background — so the live question is the first.)
Acceptance. FULLY RESOLVES: determine $c^{*}=\inf_A \limsup_{N} \lvert A\cap[1,N]\rvert/N^{1/2}$ over additive complements of the squares exactly: a construction attaining $c^{*}$ (with a complete proof both that it is a complement and that it attains the claimed ratio) together with a matching lower-bound proof that no complement does better. ADVANCES: (a) a construction, with complete proof, of a complement whose $\limsup$ ratio is strictly smaller than the best construction bound stated in the background; (b) a proven lower bound for the minimal $\limsup$ strictly exceeding the liminf bound stated in the background, or a proven improvement of that liminf constant itself; (c) a Lean formalisation of any of these results. Candidate constructions may be found by search, but each claim must come with a proof valid for all $N$ — a finite covering check alone is insufficient. Deliver the construction + proof, or the lower-bound proof.
Background
Posed by Erdős [Er56, p.134]; listed as open on erdosproblems.com/33 (fetched 2026-07-13, status 'open'). Counting forces $\lvert A\cap[1,N]\rvert\gtrsim N^{1/2}$, since only $\sim N^{1/2}$ squares lie below $N$. Erdős observed that complements exist for which the $\limsup$ is finite and $>1$. On the $\liminf$ side the picture is well developed: Moser [Mo65] proved every additive complement of the squares has $\liminf \lvert A\cap[1,N]\rvert/N^{1/2}>1.06$ (already answering the second question), and the best-known lower bound is $\liminf\ge 4/\pi\approx 1.273$, proved by Cilleruelo [Ci93], Habsieger [Ha95], and Balasubramanian–Ramana [BaRa01]. The $\limsup$-minimisation question has been much less studied: van Doorn gives an explicit construction (note linked from Bloom's page) of a complement satisfying $\lvert A\cap[1,N]\rvert/N^{1/2}< 2\phi^{5/2}\approx 6.66$ for all $N$, where $\phi=(1+\sqrt{5})/2$ is the golden ratio; no lower bound for the minimal $\limsup$ beyond the $4/\pi$ liminf bound is known, leaving a wide-open gap. The statement is formalised in Lean in the google-deepmind/formal-conjectures repository. The attacker's tools: structured constructions (interval-, digit- or Beatty-type complements) whose covering property admits a finite verification pattern plus an induction, found by computer search over candidate families; on the lower-bound side, counting/Fourier arguments in the Cilleruelo–Habsieger style.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #33 (T. F. Bloom) | website |
| REF-02 | W. van Doorn — The smallest set such that every positive integer is the sum of a square and an element from this set | paper |
| REF-03 | Lean formalisation of Erdős #33 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.