The original motivation for this result is attributed to a problem posed by S. Sidon in 1932 on economical bases. An additive basis is called economical when it is an additive basis of order h and that is, for every. In other words, these are additive bases that use as few numbers as possible to represent a given n, and yet represent every natural number. Related concepts include -sequences and the Erdős–Turán conjecture on additive bases. Sidon's question was whether an economical basis of order 2 exists. A positive answer was given by P. Erdős in 1956, settling the yet-to-be-called Erdős–Tetali theorem for the case. Although the general version was believed to be true, no complete proof appeared in the literature before the paper from Erdős & Tetali.
Ideas in the proof
The proof is an instance of the probabilistic method, and can be divided into three main steps. First, one start by defining a random sequence by where is some large real constant, is a fixed integer and n is sufficiently large so that the above formula is well-defined. A detailed discussion on the probability space associated with this type of construction may be found on Halberstam & Roth. Secondly, one then shows that the expected value of the random variable has the order of log. That is, Finally, one shows that almost surely concentrates around its mean. More explicitly: This is the critical step of the proof. Originally it was dealt with by means of Janson's inequality, a type of concentration inequality for multivariate polynomials. Tao & Vu present this proof with a more sophisticated two-sided concentration inequality by V. Vu, thus relatively simplifying this step. Alon & Spencer classify this proof as an instance of the Poisson paradigm.
A natural question is whether similar results apply for functions other than log. That is, fixing an integer, for which functions f can we find a subset of the natural numbers satisfying ? It follows from a result of C. Táfula that if f is a locally integrable, positive real function satisfying
then there exists an additive basis of order h which satisfies. While improvements to the upper bound for f can be reasonably expected, any improvements to the lower bound would produce a counterexample to the strong version of Erdős–Turán.
Computable economical bases
All the known proofs of Erdős–Tetali theorem are, by the nature of the infinite probability space used, non-constructive proofs. However, Kolountzakis showed the existence of a recursive set satisfying such that takes polynomial time in n to be computed. The question for remains open.
Economical subbases
Given an arbitrary additive basis, one can ask whether there exists such that is an economical basis. V. Vu showed that this is the case for Waring bases, where for every fixed k there are economical subbases of of order for every, for some large computable constant.
The original Erdős–Turán conjecture on additive bases states, in its most general form, that if is an additive basis of order h then. Nonetheless, in his 1956 paper on the case of Erdős–Tetali, P. Erdős asked whether it could be the case that actually whenever is an additive basis of order 2. The question naturally extends to, making it a way stronger assertion than that of Erdős–Turán. In some sense, what is being conjectured is that there are no additive bases substantially more economical than those guaranteed to exist by the Erdős–Tetali theorem.
