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 ${\displaystyle h\geq 2}$, there exists a subset of the natural numbers ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ satisfying

$${\displaystyle r_{{\mathcal {B}},h}(n)\asymp \log n,}$$

where ${\displaystyle r_{{\mathcal {B}},h}(n)}$ denotes the number of ways that a natural number n can be expressed as the sum of h elements of B.^[1]

The theorem is named after Paul Erdős and Prasad V. Tetali, who published it in 1990.

Motivation

The original motivation for this result is attributed to a problem posed by S. Sidon in 1932 on economical bases. An additive basis ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ is called economical^[2] (or sometimes thin^[3]) when it is an additive basis of order h and

${\displaystyle r_{{\mathcal {B}},h}(n)\ll _{\varepsilon }n^{\varepsilon }}$

for every ${\displaystyle \varepsilon >0}$. 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 ${\displaystyle B_{h}[g]}$-sequences^[4] 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,^[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]

Ideas in the proof

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 ${\displaystyle \omega \subseteq \mathbb {N} }$ by

${\displaystyle \Pr(n\in \omega )=C\cdot n^{{\frac {1}{h}}-1}(\log n)^{\frac {1}{h}},}$

where ${\displaystyle C>0}$ is some large real constant, ${\displaystyle h\geq 2}$ 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 ${\displaystyle r_{\omega ,h}(n)}$ has the order of log. That is,

${\displaystyle \mathbb {E} (r_{\omega ,h}(n))\asymp \log n.}$

Finally, one shows that ${\displaystyle r_{\omega ,h}(n)}$ almost surely concentrates around its mean. More explicitly:

${\displaystyle \Pr {\big (}\exists c_{1},c_{2}>0~|~{\text{for all large }}n\in \mathbb {N} ,~c_{1}\mathbb {E} (r_{\omega ,h}(n))\leq r_{\omega ,h}(n)\leq c_{2}\mathbb {E} (r_{\omega ,h}(n)){\big )}=1}$

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]

Relation to the Erdős–Turán conjecture on additive bases

The original Erdős–Turán conjecture on additive bases states, in its most general form, that if ${\textstyle {\mathcal {B}}\subseteq \mathbb {N} }$ is an additive basis of order h then

${\displaystyle \limsup _{n\to \infty }r_{{\mathcal {B}},h}(n)=\infty$ ;}

that is, ${\textstyle r_{{\mathcal {B}},h}(n)}$ cannot be bounded. In his 1956 paper, P. Erdős^[5] asked whether it could be the case that

${\displaystyle \limsup _{n\to \infty }{\frac {r_{{\mathcal {B}},2}(n)}{\log n}}>0}$

whenever ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ is an additive basis of order 2. In other words, this is saying that ${\textstyle r_{{\mathcal {B}},2}(n)}$ is not only unbounded, but that no function smaller than log can dominate ${\textstyle r_{{\mathcal {B}},2}(n)}$. The question naturally extends to ${\displaystyle h\geq 3}$, 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.

Further developments

See also

• Erdős–Fuchs theorem: For any non-zero ${\displaystyle C\in \mathbb {R} }$, there is no set ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ which satisfies ${\displaystyle \textstyle {\sum _{n\leq x}r_{{\mathcal {B}},2}(n)=Cx+o\left(x^{1/4}\log(x)^{-1/2}\right)}}$.
• Erdős–Turán conjecture on additive bases: If ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ is an additive basis of order 2, then ${\displaystyle r_{{\mathcal {B}},2}(n)\neq O(1)}$.
• Waring's problem, the problem of representing numbers as sums of k-powers, for fixed ${\displaystyle k\geq 2}$.

References

• Erdős, P.; Tetali, P. (1990). "Representations of integers as the sum of k terms". Random Structures & Algorithms. 1 (3): 245–261. doi:10.1002/rsa.3240010302.
• Halberstam, H.; Roth, K. F. (1983). Sequences. Springer New York. ISBN 978-1-4613-8227-0. OCLC 840282845.
• Alon, N.; Spencer, J. (2016). The probabilistic method (4th ed.). Wiley. ISBN 978-1-1190-6195-3. OCLC 910535517.
• Tao, T.; Vu, V. (2006). Additive combinatorics. Cambridge University Press. ISBN 0521853869. OCLC 71262684.