# 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](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/66.lean).

## 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](https://doi.org/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](https://doi.org/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](https://doi.org/10.1002/rsa.3240010302)
4. C. Táfula, Representation functions with prescribed rates of growth, *Random Structures Algorithms* 69 (2026), e70088. [arXiv:2405.01530](https://arxiv.org/abs/2405.01530)

## Source

Imported from [Erdős Problems 66](https://www.erdosproblems.com/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.