Erdős–Tetali Theorem
   HOME

TheInfoList



OR:

In additive number theory, an area of
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the Erdős–Tetali theorem is an
existence theorem In mathematics, an existence theorem is a theorem which asserts the existence of a certain object. It might be a statement which begins with the phrase " there exist(s)", or it might be a universal statement whose last quantifier is existential ...
concerning economical additive bases of every order. More specifically, it states that for every fixed integer h \geq 2, there exists a subset of the natural numbers \mathcal \subseteq \mathbb satisfying r_(n) \asymp \log n, where r_(n) denotes the number of ways that a natural number ''n'' can be expressed as the sum of ''h'' elements of ''B''. The theorem is named after
Paul Erdős Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 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 ...
and
Prasad V. Tetali Prasad V. Tetali is an Indian-American mathematician and computer scientist who works as a professor at the Georgia Institute of Technology, with a joint appointment in mathematics and the College of Computing.
, 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 \mathcal\subseteq\mathbb is called ''economical'' (or sometimes ''thin'') when it is an additive basis of order ''h'' and :r_(n) \ll_ n^\varepsilon for every \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 B_h /math>-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 case 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.


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'' \omega \subseteq \mathbb by :\Pr(n\in \omega) = C\cdot n^ (\log n)^, where C>0 is some large real constant, 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). Secondly, one then shows that the
expected value In probability theory, the expected value (also called expectation, expectancy, mathematical expectation, mean, average, or first moment) is a generalization of the weighted average. Informally, the expected value is the arithmetic mean of a l ...
of the
random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...
r_(n) has the order of log. That is, :\mathbb(r_(n)) \asymp \log n. Finally, one shows that r_(n) almost surely concentrates around its mean. More explicitly: :\Pr\big(\exists c_1,c_2>0 ~, ~ \text n\in\mathbb ,~ c_1\mathbb(r_(n)) \leq r_(n) \leq c_2\mathbb(r_(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) present this proof with a more sophisticated two-sided concentration inequality by V. Vu (2000), thus relatively simplifying this step. Alon & Spencer (2016) classify this proof as an instance of the Poisson paradigm.


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 \mathcal\subseteq\mathbb is an additive basis of order ''h'' then :\limsup_ r_(n) = \infty; that is, r_(n) cannot be bounded. In his 1956 paper, P. Erdős asked whether it could be the case that :\limsup_ \frac > 0 whenever \mathcal\subseteq\mathbb is an additive basis of order 2. In other words, this is saying that r_(n) is not only unbounded, but that no function smaller than log can dominate r_(n). The question naturally extends to 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


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 (1995) showed the existence of a recursive set \mathcal\subseteq \mathbb satisfying r_(n) \asymp \log n such that \mathcal\cap\ takes polynomial time in ''n'' to be computed. The question for h\geq 3 remains open.


Economical subbases

Given an arbitrary additive basis \mathcal\subseteq\mathbb, one can ask whether there exists \mathcal\subseteq\mathcal such that \mathcal is an economical basis. V. Vu (2000) showed that this is the case for Waring bases \mathbb^ k := \, where for every fixed ''k'' there are economical subbases of \mathbb^k of order s for every s \geq s_k, for some large computable constant s_k.


Growth rates other than log

Another possible question is whether similar results apply for functions other than log. That is, fixing an integer h\geq 2, for which functions ''f'' can we find a subset of the natural numbers \mathcal\subseteq \mathbb satisfying r_(n) \asymp f(n)? It follows from a result of C. Táfula (2019) that if ''f'' is a locally integrable, positive real function satisfying * \frac\int_^ f(t) \,\mathrmt \asymp f(x), and * \log x \ll f(x) \ll x^(\log x)^ for some \varepsilon > 0, then there exists an additive basis \mathcal\subseteq \mathbb of order ''h'' which satisfies r_(n) \asymp f(n). The minimal case recovers Erdős–Tetali's theorem.


See also

*
Erdős–Fuchs theorem In mathematics, in the area of additive number theory, the Erdős–Fuchs theorem is a statement about the number of ways that numbers can be represented as a sum of elements of a given additive basis, stating that the average order of this number ...
: For any non-zero C\in \mathbb, there is no set \mathcal\subseteq \mathbb which satisfies \textstyle. * Erdős–Turán conjecture on additive bases: If \mathcal\subseteq\mathbb is an additive basis of order 2, then r_(n) \neq O(1). * Waring's problem, the problem of representing numbers as sums of ''k''-powers, for fixed 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. . * Halberstam, H.; Roth, K. F. (1983). '' Sequences''. Springer New York. . . * Alon, N.; Spencer, J. (2016). ''The probabilistic method'' (4th ed.). Wiley. . . * Tao, T.; Vu, V. (2006). ''Additive combinatorics''. Cambridge University Press. . . {{DEFAULTSORT:Erdos-Tetali theorem Theorems in number theory Theorems in combinatorics Additive number theory Tetali theorem