The Erdős–Turán conjecture on additive bases

A set of natural numbers is an additive basis of order 2 when every large integer is a sum of two of its elements. Erdős and Turán conjectured in 1941 that no such basis can be so economical that every integer has only a bounded number of representations. The statement is elementary, yet it remains open.

Problem

For $A\subseteq\mathbb{N}$ let

r_A(n)=\#\{(a,b)\in A\times A : a+b=n\}

count the ordered representations of $n$ as a sum of two elements of $A$ . Suppose that $A+A$ contains all but finitely many positive integers, that is, $r_A(n)\ge 1$ for all large $n$ . Must $r_A$ then be unbounded:

\limsup_{n\to\infty} r_A(n)=\infty\,?

Erdős offered $500 for a solution. Erdős and Turán also proposed the stronger statement $\limsup_{n\to\infty} r_A(n)/\log n>0$ , and a stronger variant still assumes only that $\lvert A\cap[1,N]\rvert\ge c\sqrt N$ for all large $N$ , a counting condition that every basis of order 2 satisfies.

Background

The question grew out of Sidon's problem of how thin an additive basis can be, and appears in the same 1941 paper in which Erdős and Turán proved the first upper bound for Sidon sets. Erdős showed in 1956 that there is a basis of order 2 with $c_1\log n\le r_A(n)\le c_2\log n$ for large $n$ , so representation counts of logarithmic size are achievable; the stronger form of the conjecture says that this is optimal. The problem is C9 in Guy's Unsolved Problems in Number Theory.

What is known

Thin bases exist. Erdős (1956) constructed a basis of order 2 whose representation function stays between two constant multiples of $\log n$ ; Erdős and Tetali (1990) extended this to bases of every order $k$ .
Small lower bounds only. No unbounded lower bound is known. Borwein, Choi and Chu (2006) proved that the representation function of every basis of order 2 exceeds 7 for infinitely many $n$ .
Reformulations. Nathanson (2004) placed the conjecture in a general family of additive problems and, using König's lemma, showed that this general problem is equivalent to one about finite sets of integers.
Variants. Problem 40 on the same site asks for which functions $g(N)\to\infty$ the hypothesis $\lvert A\cap[1,N]\rvert \gg N^{1/2}/g(N)$ already forces $\limsup r_A(n)=\infty$ ; settling it for any such $g$ would prove the conjecture.

What would count as progress

A proof that every basis of order 2 has an unbounded representation function, or an explicit basis with bounded $r_A$ .
A larger explicit constant $K$ such that $r_A(n)\ge K$ infinitely often for every basis, with any computation needed published so it can be rerun.
Progress on the stronger forms, for instance under the counting hypothesis $\lvert A\cap[1,N]\rvert\ge c\sqrt N$ instead of the basis property.
A formal proof against the Lean statement in formal-conjectures.

References

P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc. 16 (1941), 212–215. doi:10.1112/jlms/s1-16.4.212
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
M. B. Nathanson, Generalized additive bases, König's lemma, and the Erdős–Turán conjecture, J. Number Theory 106 (2004), 70–78. arXiv:math/0302155
P. Borwein, S. Choi and F. Chu, An old conjecture of Erdős–Turán on additive bases, Math. Comp. 75 (2006), 475–484. doi:10.1090/S0025-5718-05-01777-1
R. K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer (2004), problem C9. doi:10.1007/978-0-387-26677-0

Source

Imported from Erdős Problems 28, 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.