Erdős–Turán conjecture on additive bases

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.

It concerns additive bases, subsets of natural numbers with the property that every natural number can be represented as the sum of a bounded number of elements from the basis. Roughly, it states that the number of representations of this type cannot also be bounded.

Background and formulation

edit

The question concerns subsets of the natural numbers, typically denoted by  , called additive bases. A subset   is called an (asymptotic) additive basis of finite order if there is some positive integer   such that every sufficiently large natural number   can be written as the sum of at most   elements of  . For example, the natural numbers are themselves an additive basis of order 1, since every natural number is trivially a sum of at most one 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. However, one should perhaps expect that a set   which is about as sparse as the squares (meaning that in a given interval  , roughly   of the integers in   lie in  ) which does not have this obvious deficit should have the property that every sufficiently large positive integer is the sum of three elements from  . This follows from the following probabilistic model: suppose that   is a positive integer, and   are 'randomly' selected from  . Then the probability of a given element from   being chosen is roughly  . One can then estimate the expected value, which in this case will be quite large. Thus, we 'expect' that there are many representations of   as a sum of three elements from  , unless there is some arithmetic obstruction (which means that   is somehow quite different than a 'typical' set of the same density), like with the squares. 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   that passed the arithmetic obstruction. 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.

This begets the question: suppose that  , unlike the squares or the prime numbers, is very efficient at representing positive integers as a sum of   elements of  . How efficient can it be? The best possibility is that we can find a positive integer   and a set   such that every positive integer   is the sum of at most   elements of   in exactly one way. Failing that, perhaps we can find a   such that every positive integer   is the sum of at most   elements of   in at least one way and at most   ways, where   is a function of  .

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   is an additive basis of order   of the natural numbers, then it cannot represent positive integers as a sum of at most   too efficiently; the number of representations of  , as a function of  , must tend to infinity.

History

edit

The conjecture was made jointly by Paul Erdős and Pál Turán in 1941.[1] In the original paper, they write

"(2) If   for  , then  ",

where   denotes the limit superior. Here   is the number of ways one can write the natural number   as the sum of two (not necessarily distinct) elements of  . If   is always positive for sufficiently large  , then   is called an additive basis (of order 2).[2] This problem has attracted significant attention[2] but remains unsolved.

In 1964, Erdős published a multiplicative version of this conjecture.[3]

Progress

edit

While the conjecture remains unsolved, there have been some advances on the problem. First, we express the problem in modern language. For a given subset  , we define its representation function  . Then the conjecture states that if   for all   sufficiently large, then  .

More generally, for any   and subset  , we can define the   representation function as  . We say that   is an additive basis of order   if   for all   sufficiently large. One can see from an elementary argument that if   is an additive basis of order  , then

 

So we obtain the lower bound  .

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   can an additive basis   of order   get? This question was answered in the case   by Erdős in 1956.[4] Erdős proved that there exists an additive basis   of order 2 and constants   such that   for all   sufficiently large. In particular, this implies that there exists an additive basis   such that  , which is essentially best possible. This motivated Erdős to make the following conjecture:

If   is an additive basis of order  , then  

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.[5] In 1990, Erdős and Prasad V. Tetali extended Erdős's 1956 result to bases of arbitrary order.[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  ,   eventually exceeds 7.[8][9]

References

edit
  1. ^ Erdős, Paul.; Turán, Pál (1941). "On a problem of Sidon in additive number theory, and on some related problems". Journal of the London Mathematical Society. 16 (4): 212–216. doi:10.1112/jlms/s1-16.4.212.
  2. ^ a b Tao, T.; Vu, V. (2006). Additive Combinatorics. New York: Cambridge University Press. p. 13. ISBN 978-0-521-85386-6.
  3. ^ Erdős, Paul (1964). "On the multiplicative representation of integers". Israel Journal of Mathematics. 2 (4): 251–261. CiteSeerX 10.1.1.210.8322. doi:10.1007/BF02759742.
  4. ^ Erdős, P. (1956). "Problems and results in additive number theory". Colloque sur la Théorie des Nombres: 127–137.
  5. ^ Wirsing, Eduard (1986). "Thin subbases". Analysis. 6 (2–3): 285–308. doi:10.1524/anly.1986.6.23.285. S2CID 201721463.
  6. ^ Erdős, Paul.; Tetali, Prasad (1990). "Representations of integers as the sum of   terms". Random Structures Algorithms. 1 (3): 245–261. doi:10.1002/rsa.3240010302.
  7. ^ Vu, Van (2000). "On a refinement of Waring's problem". Duke Mathematical Journal. 105 (1): 107–134. CiteSeerX 10.1.1.140.3008. doi:10.1215/S0012-7094-00-10516-9.
  8. ^ Borwein, Peter; Choi, Stephen; Chu, Frank (2006). "An old conjecture of Erdős–Turán on additive bases". Mathematics of Computation. 75 (253): 475–484. doi:10.1090/s0025-5718-05-01777-1.
  9. ^ Xiao, Stanley Yao (2011). On the Erdős–Turán conjecture and related results (MSc). hdl:10012/6150.