Can a representation function satisfy $1_A\ast 1_A(n)\sim c\log n$ with $c\neq 0$ exactly? (Erdős #66)
Statement
For $A\subseteq \mathbb{N}$ write $1_A\ast 1_A(n)=\#\{(a,b)\in A\times A: a+b=n\}$ for the number of ordered representations of $n$ as a sum of two elements of $A$. Is there a set $A\subseteq \mathbb{N}$ such that $$\lim_{n\to \infty}\frac{1_A\ast 1_A(n)}{\log n}$$ exists and is $\neq 0$?
Acceptance. FULLY RESOLVES: (a) a construction of $A\subseteq\mathbb{N}$ together with a complete proof that $1_A\ast 1_A(n)/\log n$ converges to a nonzero constant — probabilistic constructions must control ALL sufficiently large $n$, not almost all; or (b) a proof that no such $A$ exists (for every $A$, the limit either fails to exist or is $0$). Machine-checkable proof (Lean 4; the formal statement exists) preferred, else a complete written proof with all steps. ADVANCES: (a) a proof widening the forced oscillation: that $\lvert 1_A\ast 1_A(n)-\log n\rvert\le F(n)$ for all large $n$ is impossible for some $F$ growing strictly faster than the $\sqrt{\log n}$-scale barrier stated in the background, or the analogous statement for $c\log n$ with arbitrary $c>0$; (b) a proof of Erdős's suggested strengthening that $\limsup$ and $\liminf$ of $1_A\ast 1_A(n)/\log n$ are always separated by an absolute constant; (c) a Lean formalisation of the Erdős–Sárközy or Horváth obstruction. Deliver the construction + proof, or the impossibility proof.
Background
Asked by Erdős in many of his problem papers ([Er56], [Er59], [Er80, p.98], [ErGr80], [Er85c], [Er89d], [Er90], [Er95], [Er97c]; see also [Va99, 1.16]), with a $500 prize on offer; listed as open on erdosproblems.com/66 (fetched 2026-07-13, status 'open'). The scale $\log n$ is the natural one: a suitably constructed random set has $1_A\ast 1_A(n)\sim c\log n$ for all $n$ OUTSIDE an exceptional set of density zero — the entire difficulty is eliminating the exceptional set. Erdős believed the answer should be no; in [Er80] he asked explicitly whether a set with limit equal to $1$ exists and did not believe it did. Known obstructions to over-regular representation functions: Erdős and Sárközy proved that $\lvert 1_A\ast 1_A(n)-\log n\rvert/\sqrt{\log n}\to 0$ is impossible, and Horváth [Ho07] sharpened this, showing $\lvert 1_A\ast 1_A(n)-\log n\rvert \leq (1-\epsilon)\sqrt{\log n}$ cannot hold for all large $n$. Erdős further suggested that the $\liminf$ and $\limsup$ of $1_A\ast 1_A(n)/\log n$ may always be separated by an absolute constant, which would give a negative answer. The statement is formalised in Lean in the google-deepmind/formal-conjectures repository. The attacker's tool: proof-shaped — either a refined probabilistic/algebraic construction with a complete proof handling every $n$ (for yes), or a variance/oscillation argument in the Erdős–Sárközy–Horváth line ruling out convergence at scale $\log n$ (for no), ideally machine-checked.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #66 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #66 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.