Erdős–Turán Conjecture On Additive Bases
   HOME

TheInfoList



OR:

The Erdős–Turán conjecture is an old unsolved problem in
additive number theory Additive number theory is the subfield of number theory concerning the study of subsets of integers and their behavior under addition. More abstractly, the field of additive number theory includes the study of abelian groups and commutative semigro ...
(not to be confused with Erdős conjecture on arithmetic progressions) posed by
Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and
Pál Turán Pál Turán (; 18 August 1910 – 26 September 1976) also known as Paul Turán, was a Hungarian mathematician who worked primarily in extremal combinatorics. In 1940, because of his Jewish origins, he was arrested by History of the Jews in Hun ...
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

The question concerns
subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
s of the
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s, typically denoted by \mathbb , called additive bases. A subset B is called an (asymptotic) additive basis of finite order if there is some positive
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
h such that every sufficiently large natural number n can be written as the sum of at most h elements of B. 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 Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number, nonnegative integer can be represented as a sum of four non-negative integer square number, squares. That is, the squares form an additive basi ...
says that the set of positive
square number In mathematics, a square number or perfect square is an integer that is the square (algebra), square of an integer; in other words, it is the multiplication, product of some integer with itself. For example, 9 is a square number, since it equals ...
s is an additive basis of order 4. Another highly non-trivial and celebrated result along these lines is
Vinogradov's theorem In number theory, Vinogradov's theorem is a result which implies that any sufficiently large odd integer can be written as a sum of three prime numbers. It is a weaker form of Goldbach's weak conjecture, which would imply the existence of such a re ...
. One is naturally inclined to ask whether these results are optimal. It turns out that
Lagrange's four-square theorem Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number, nonnegative integer can be represented as a sum of four non-negative integer square number, squares. That is, the squares form an additive basi ...
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 B which is about as sparse as the squares (meaning that in a given interval ,N/math>, roughly N^ of the integers in ,N/math> lie in B) which does not have this obvious deficit should have the property that every sufficiently large positive integer is the sum of three elements from B. This follows from the following probabilistic model: suppose that N/2 < n \leq N is a positive integer, and x_1, x_2, x_3 are 'randomly' selected from B \cap ,N/math>. Then the probability of a given element from B being chosen is roughly 1/N^. One can then estimate the expected value, which in this case will be quite large. Thus, we 'expect' that there are many representations of n as a sum of three elements from B, unless there is some arithmetic obstruction (which means that B 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 n that passed the arithmetic obstruction. Examining
Vinogradov's theorem In number theory, Vinogradov's theorem is a result which implies that any sufficiently large odd integer can be written as a sum of three prime numbers. It is a weaker form of Goldbach's weak conjecture, which would imply the existence of such a re ...
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 B, unlike the squares or the prime numbers, is very efficient at representing positive integers as a sum of h elements of B. How efficient can it be? The best possibility is that we can find a positive integer h and a set B such that every positive integer n is the sum of at most h elements of B in exactly one way. Failing that, perhaps we can find a B such that every positive integer n is the sum of at most h elements of B in at least one way and at most S(h) ways, where S is a function of h. This is basically the question that
Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and
Pál Turán Pál Turán (; 18 August 1910 – 26 September 1976) also known as Paul Turán, was a Hungarian mathematician who worked primarily in extremal combinatorics. In 1940, because of his Jewish origins, he was arrested by History of the Jews in Hun ...
asked in 1941. Indeed, they
conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's conjecture (now a theorem, proven in 1995 by Andrew Wiles), ha ...
d a ''negative'' answer to this question, namely that if B is an additive basis of order h of the natural numbers, then it cannot represent positive integers as a sum of at most h too efficiently; the number of representations of n, as a function of n, must tend to infinity.


History

The conjecture was made jointly by
Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and
Pál Turán Pál Turán (; 18 August 1910 – 26 September 1976) also known as Paul Turán, was a Hungarian mathematician who worked primarily in extremal combinatorics. In 1940, because of his Jewish origins, he was arrested by History of the Jews in Hun ...
in 1941. In the original paper, they write :"(2) If f(n) > 0 for n > n_0, then \varlimsup_ f(n) = \infty", where \varlimsup_ denotes the
limit superior In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting (that is, eventual and extreme) bounds on the sequence. They can be thought of in a similar fashion for a function (see limit of a function). For ...
. Here f(n) is the number of ways one can write the natural number n as the sum of two (not necessarily distinct) elements of B. If f(n) is always positive for sufficiently large n, then B is called an additive basis (of order 2). This problem has attracted significant attention but remains unsolved. In 1964, Erdős published a multiplicative version of this conjecture.


Progress

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 B \subset \mathbb, we define its ''representation function'' r_B(n) = \#\. Then the conjecture states that if r_B(n) > 0 for all n sufficiently large, then \limsup_ r_B(n) = \infty . More generally, for any h \in \mathbb and subset B \subset \mathbb, we can define the h representation function as r_(n) = \#\. We say that B is an additive basis of order h if r_(n) > 0 for all n sufficiently large. One can see from an elementary argument that if B is an additive basis of order h, then :\displaystyle n \leq \sum_^n r_(m) \leq , B \cap ,n^h So we obtain the lower bound n^ \leq , B \cap ,n. 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 , B \cap ,n \geq n^ can an additive basis B of order h get? This question was answered in the case h=2 by Erdős in 1956. Erdős proved that there exists an additive basis B of order 2 and constants c_1, c_2 > 0 such that c_1 \log n \leq r_B(n) \leq c_2 \log n for all n sufficiently large. In particular, this implies that there exists an additive basis B such that r_B(n) = n^ , which is essentially best possible. This motivated Erdős to make the following conjecture: :If B is an additive basis of order h, then \limsup_ r_B(n)/\log n > 0. 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. In 1990, Erdős and Prasad V. Tetali extended Erdős's 1956 result to bases of arbitrary order. In 2000, V. Vu proved that thin subbases exist in the Waring bases using the Hardy–Littlewood circle method and his polynomial concentration results. In 2006, Borwein, Choi, and Chu proved that for all additive bases B, f(n) eventually exceeds 7.


References

{{DEFAULTSORT:Erdos-Turan Conjecture On Additive Bases Additive number theory Conjectures Unsolved problems in number theory