In additive number theory, an area of mathematics, the Erdős–Tetali theorem is an existence theorem concerning economical additive bases of every order.
More specifically, it states that for every fixed integer
, there exists a subset of the natural numbers
[1] The theorem is named after Paul Erdős and Prasad V. Tetali, who published it in 1990.
The original motivation for this result is attributed to a problem posed by S. Sidon in 1932 on economical bases.
is called economical[2] (or sometimes thin[3]) when it is an additive basis of order h and for every
Sidon's question was whether an economical basis of order 2 exists.
A positive answer was given by P. Erdős in 1956,[5] settling the case h = 2 of the theorem.
Although the general version was believed to be true, no complete proof appeared in the literature before the paper by Erdős and Tetali.
[6] The proof is an instance of the probabilistic method, and can be divided into three main steps.
First, one starts by defining a random sequence
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 (1983).
[7] Secondly, one then shows that the expected value of the random variable
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 (2006)[8] present this proof with a more sophisticated two-sided concentration inequality by V. Vu (2000),[9] thus relatively simplifying this step.
Alon & Spencer (2016) classify this proof as an instance of the Poisson paradigm.
[10] The original Erdős–Turán conjecture on additive bases states, in its most general form, that if
In his 1956 paper, P. Erdős[5] asked whether it could be the case that whenever
is not only unbounded, but that no function smaller than log can dominate
, making it a stronger form of the Erdős–Turán conjecture on additive bases.
In a 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.
However, Kolountzakis (1995)[11] showed the existence of a recursive set
takes polynomial time in n to be computed.
V. Vu (2000)[12] showed that this is the case for Waring bases
Another possible question is whether similar results apply for functions other than log.
, for which functions f can we find a subset of the natural numbers
It follows from a result of C. Táfula (2019)[13] that if f is a locally integrable, positive real function satisfying then there exists an additive basis
The minimal case f(x) = log x recovers Erdős–Tetali's theorem.