The Erdős–Turán conjecture is an old unsolved problem in additive number theory (not to be confused with Erdős conjecture on arithmetic progressions) posed by Paul Erdős and Pál Turán in 1941.
Roughly, it states that the number of representations of this type cannot also be bounded.
The question concerns subsets of the natural numbers, typically denoted by
is called an (asymptotic) additive basis of finite order if there is some positive integer
such that every sufficiently large natural number
Lagrange's four-square theorem says that the set of positive square numbers is an additive basis of order 4.
Another highly non-trivial and celebrated result along these lines is Vinogradov's theorem.
One is naturally inclined to ask whether these results are optimal.
It turns out that Lagrange's four-square theorem cannot be improved, as there are infinitely many positive integers which are not the sum of three squares.
This is because no positive integer which is the sum of three squares can leave a remainder of 7 when divided by 8.
) which does not have this obvious deficit should have the property that every sufficiently large positive integer is the sum of three elements from
Therefore, one should expect that the squares are quite inefficient at representing positive integers as the sum of four elements, since there should already be lots of representations as sums of three elements for those positive integers
Examining Vinogradov's theorem quickly reveals that the primes are also very inefficient at representing positive integers as the sum of four primes, for instance.
, unlike the squares or the prime numbers, is very efficient at representing positive integers as a sum of
The best possibility is that we can find a positive integer
This is basically the question that Paul Erdős and Pál Turán asked in 1941.
Indeed, they conjectured a negative answer to this question, namely that if
of the natural numbers, then it cannot represent positive integers as a sum of at most
The conjecture was made jointly by Paul Erdős and Pál Turán in 1941.
as the sum of two (not necessarily distinct) elements of
[2] This problem has attracted significant attention[2] but remains unsolved.
In 1964, Erdős published a multiplicative version of this conjecture.
[3] While the conjecture remains unsolved, there have been some advances on the problem.
First, we express the problem in modern language.
The original conjecture spawned as Erdős and Turán sought a partial answer to Sidon's problem (see: Sidon sequence).
Later, Erdős set out to answer the following question posed by Sidon: how close to the lower bound
[4] Erdős proved that there exists an additive basis
This motivated Erdős to make the following conjecture: In 1986, Eduard Wirsing proved that a large class of additive bases, including the prime numbers, contains a subset that is an additive basis but significantly thinner than the original.
[6] In 2000, V. Vu proved that thin subbases exist in the Waring bases using the Hardy–Littlewood circle method and his polynomial concentration results.
[7] In 2006, Borwein, Choi, and Chu proved that for all additive bases