Representation functions growing exactly like log n

How regularly can the number of ways to write $n$ as a sum of two elements of a set behave? Suitable random sets give about $c\log n$ representations for almost all $n$, but not for every $n$. Erdős asked whether some set achieves $1_A\ast1_A(n)\sim c\log n$ for every large $n$, believed the answer is no, and offered $500 for a solution.

Problem

For $A\subseteq\mathbb{N}$ let $1_A\ast1_A(n)=\#\{(a,b)\in A\times A : a+b=n\}$ be the number of ordered representations of $n$ as a sum of two elements of $A$. Is there a set $A$ such that the limit

$$\lim_{n\to\infty}\frac{1_A\ast1_A(n)}{\log n}$$

exists and is non-zero?

Background

Erdős proved in 1956 that there are sets whose representation function stays between two constant multiples of $\log n$. A suitably constructed random set even satisfies $1_A\ast1_A(n)\sim c\log n$ outside an exceptional set of $n$ of density zero; the difficulty is to remove all exceptions. Erdős believed that no such set exists and suggested that the $\liminf$ and $\limsup$ of $1_A\ast1_A(n)/\log n$ might always differ by an absolute constant. The problem is closely related to the Erdős–Turán conjecture on additive bases.

What is known

• No square-root precision. Erdős and Sárközy (1985) proved that for any increasing $F$ with $F(n)\to\infty$ and $F(n)=o(n/(\log n)^2)$, one cannot have $\lvert 1_A\ast1_A(n)-F(n)\rvert=o(F(n)^{1/2})$; in particular $\lvert1_A\ast1_A(n)-\log n\rvert=o(\sqrt{\log n})$ is impossible.
• Sharper version. Horváth (2007) showed that even $\lvert1_A\ast1_A(n)-\log n\rvert\le(1-\varepsilon)\sqrt{\log n}$ cannot hold for all large $n$.
• Faster growth is possible. Táfula (2026) proved that if $F$ is regularly varying and $F(n)/\log n\to\infty$, then some set has $1_A\ast1_A(n)\sim F(n)$; so the logarithm is exactly the boundary where the question becomes hard. He also gave a probabilistic heuristic that $\limsup 1_A\ast1_A(n)/\log n<1$ forces $1_A\ast1_A(n)=0$ infinitely often.

What would count as progress

• A proof that no set has $1_A\ast1_A(n)/\log n\to c\neq0$, or a construction of one.
• A proof that $\liminf$ and $\limsup$ of $1_A\ast1_A(n)/\log n$ must differ, perhaps by an absolute constant, for every set $A$ that represents all large integers.
• Progress on the heuristic of Táfula, which would settle the case $c<1$.
• A formal proof against the Lean statement in formal-conjectures.

References

1. P. Erdős and A. Sárközy, Problems and results on additive properties of general sequences. I, Pacific J. Math. 118 (1985), 347–357. doi:10.2140/pjm.1985.118.347
2. G. Horváth, An improvement of a theorem of Erdős and Sárközy, Pollack Periodica 2 (2007), 155–161. doi:10.1556/Pollack.2.2007.S.14
3. P. Erdős and P. Tetali, Representations of integers as the sum of $k$ terms, Random Structures Algorithms 1 (1990), 245–261. doi:10.1002/rsa.3240010302
4. C. Táfula, Representation functions with prescribed rates of growth, Random Structures Algorithms 69 (2026), e70088. arXiv:2405.01530

Source

Imported from Erdős Problems 66, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.