Open problem, Arithmetic and number theory, Combinatorics and discrete mathematics, posed 1941

Erdős–Turán conjecture on additive bases

OpenErdős

Let $A \subseteq \mathbb{N}$ be an asymptotic additive basis of order $2$ , meaning that every sufficiently large integer $n \ge n_0$ can be written as $n = a + b$ with $a, b \in A$ . Then the representation function $r_A(n) = \#\{(a, b) \in A^2 : a + b = n\}$ cannot be bounded above: $\limsup_{n \to \infty} r_A(n) = \infty$ .

Posed by, 1941Paul Erdős

Research frontier as of 2026

As of 2026, the Erdős–Turán conjecture on additive bases remains open even for order $2$ . While assuming $r_A(n) \ge 1$ for all $n \ge n_0$ implies $\limsup_{n \to \infty} r_A(n) \ge 8$ (for ordered pairs) and forces the representation function not to be eventually constant, even ruling out $\limsup_{n \to \infty} r_A(n) \le 10$ is unsolved. Progress has focused on bounding the second moment $N^{-1} \sum_{n \le N} r_A(n)^2$ and studying the growth of $B_2[g]$ sets.

Best known results

Every asymptotic additive basis of order $2$ satisfies $\limsup_{n \to \infty} r_A(n) \ge 8$ for ordered representations (Grekos, Haddad, Helou, and Pihko, 2003).
There exist asymptotic bases of order $2$ with logarithmic representation growth $c_1 \log n \le r_A(n) \le c_2 \log n$ for all large $n$ (Erdős, 1956).

Tools and where they stop

Tool	Achieved	Where it stops
Generating functions and circle-method parseval bounds	Relates the generating series $f(z) = \sum_{a \in A} z^a$ on the unit circle to averages of $r_A(n)$ , ruling out eventually constant representation functions.	$L^2$ Fourier averages allow sparse spikes or cancellations and cannot by themselves force an $L^\infty$ blowup of the coefficients of $f(z)^2$ .
Probabilistic method for random thin bases	Constructs bases with $r_A(n) = \Theta(\log n)$ by selecting each integer $x$ independently with probability $c \sqrt{\log x / x}$ .	Independent random selection requires the $\sqrt{\log x}$ factor by the Borel–Cantelli lemma to avoid uncovered gaps, preventing $r_A(n) = O(1)$ via random constructions.

Open questions

Does every asymptotic additive basis of order $2$ satisfy $\limsup_{n \to \infty} r_A(n) = \infty$ ?
Can an asymptotic additive basis of order $2$ satisfy $r_A(n) = o(\log n)$ as $n \to \infty$ ?

References

Paul Erdős, Pál Turán (1941). On a problem of Sidon in additive number theory, and on some related problems · DOI:10.1112/jlms/s1-16.4.212
Georges Grekos, Labib Haddad, Charles Helou, Jukka Pihko (2003). On the Erdős–Turán conjecture · DOI:10.1016/S0022-314X(03)00099-4