Misplaced Pages

Erdős–Tetali theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Existence theorem for economical additive bases of every order

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

r B , h ( n ) ≍ log ⁡ n , {\displaystyle r_{{\mathcal {B}},h}(n)\asymp \log n,} where r B , h ( n ) {\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.

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 B ⊆ N {\displaystyle {\mathcal {B}}\subseteq \mathbb {N} } is called economical (or sometimes thin) when it is an additive basis of order h and

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

for every ε > 0 {\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 B h [ g ] {\displaystyle B_{h}} -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 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.

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

Pr ( n ∈ ω ) = C ⋅ n 1 h − 1 ( log ⁡ n ) 1 h , {\displaystyle \Pr(n\in \omega )=C\cdot n^{{\frac {1}{h}}-1}(\log n)^{\frac {1}{h}},}

where C > 0 {\displaystyle C>0} is some large real constant, h ≥ 2 {\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). Secondly, one then shows that the expected value of the random variable r ω , h ( n ) {\displaystyle r_{\omega ,h}(n)} has the order of log. That is,

E ( r ω , h ( n ) ) ≍ log ⁡ n . {\displaystyle \mathbb {E} (r_{\omega ,h}(n))\asymp \log n.}

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

Pr ( ∃ c 1 , c 2 > 0   |   for all large  n ∈ N ,   c 1 E ( r ω , h ( n ) ) ≤ r ω , h ( n ) ≤ c 2 E ( r ω , h ( n ) ) ) = 1 {\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) 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

Main article: Erdős–Turán conjecture on additive bases Unsolved problem in mathematics: Let h ≥ 2 {\textstyle h\geq 2} be an integer. If B ⊆ N {\textstyle {\mathcal {B}}\subseteq \mathbb {N} } is an infinite set such that r B , h ( n ) > 0 {\textstyle r_{{\mathcal {B}},h}(n)>0} for every n, does this imply that:
lim sup n → ∞ r B , h ( n ) log ⁡ n > 0 {\displaystyle \limsup _{n\to \infty }{\frac {r_{{\mathcal {B}},h}(n)}{\log n}}>0} ?
(more unsolved problems in mathematics)

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

lim sup n → ∞ r B , h ( n ) = ∞ ; {\displaystyle \limsup _{n\to \infty }r_{{\mathcal {B}},h}(n)=\infty ;}

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

lim sup n → ∞ r B , 2 ( n ) log ⁡ n > 0 {\displaystyle \limsup _{n\to \infty }{\frac {r_{{\mathcal {B}},2}(n)}{\log n}}>0}

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

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 R ⊆ N {\displaystyle {\mathcal {R}}\subseteq \mathbb {N} } satisfying r R , 2 ( n ) ≍ log ⁡ n {\displaystyle r_{{\mathcal {R}},2}(n)\asymp \log n} such that R ∩ { 0 , 1 , … , n } {\displaystyle {\mathcal {R}}\cap \{0,1,\ldots ,n\}} takes polynomial time in n to be computed. The question for h ≥ 3 {\displaystyle h\geq 3} remains open.

Economical subbases

Given an arbitrary additive basis A ⊆ N {\displaystyle {\mathcal {A}}\subseteq \mathbb {N} } , one can ask whether there exists B ⊆ A {\displaystyle {\mathcal {B}}\subseteq {\mathcal {A}}} such that B {\displaystyle {\mathcal {B}}} is an economical basis. V. Vu (2000) showed that this is the case for Waring bases N ∧ k := { 0 k , 1 k , 2 k , … } {\displaystyle \mathbb {N} ^{\wedge }k:=\{0^{k},1^{k},2^{k},\ldots \}} , where for every fixed k there are economical subbases of N ∧ k {\displaystyle \mathbb {N} ^{\wedge }k} of order s {\displaystyle s} for every s ≥ s k {\displaystyle s\geq s_{k}} , for some large computable constant s k {\displaystyle 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 ≥ 2 {\displaystyle h\geq 2} , for which functions f can we find a subset of the natural numbers B ⊆ N {\displaystyle {\mathcal {B}}\subseteq \mathbb {N} } satisfying r B , h ( n ) ≍ f ( n ) {\displaystyle r_{{\mathcal {B}},h}(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

  • 1 x ∫ 1 x f ( t ) d t ≍ f ( x ) {\displaystyle {\frac {1}{x}}\int _{1}^{x}f(t)\,\mathrm {d} t\asymp f(x)} , and
  • log ⁡ x ≪ f ( x ) ≪ x 1 h − 1 ( log ⁡ x ) − ε {\displaystyle \log x\ll f(x)\ll x^{\frac {1}{h-1}}(\log x)^{-\varepsilon }} for some ε > 0 {\displaystyle \varepsilon >0} ,

then there exists an additive basis B ⊆ N {\displaystyle {\mathcal {B}}\subseteq \mathbb {N} } of order h which satisfies r B , h ( n ) ≍ f ( n ) {\displaystyle r_{{\mathcal {B}},h}(n)\asymp f(n)} . The minimal case f(x) = log x recovers Erdős–Tetali's theorem.

See also

  • Erdős–Fuchs theorem: For any non-zero C ∈ R {\displaystyle C\in \mathbb {R} } , there is no set B ⊆ N {\displaystyle {\mathcal {B}}\subseteq \mathbb {N} } which satisfies ∑ n ≤ x r B , 2 ( n ) = C x + o ( x 1 / 4 log ⁡ ( x ) − 1 / 2 ) {\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 B ⊆ N {\displaystyle {\mathcal {B}}\subseteq \mathbb {N} } is an additive basis of order 2, then r B , 2 ( n ) ≠ O ( 1 ) {\displaystyle r_{{\mathcal {B}},2}(n)\neq O(1)} .
  • Waring's problem, the problem of representing numbers as sums of k-powers, for fixed k ≥ 2 {\displaystyle k\geq 2} .

References

  1. Alternative statement in big Theta notation: r B , h ( n ) = Θ ( log ⁡ ( n ) ) , {\displaystyle r_{{\mathcal {B}},h}(n)=\Theta (\log(n)),}
  2. As in Halberstam & Roth (1983), p. 111.
  3. As in Tao & Vu (2006), p. 13.
  4. See Definition 3 (p. 3) of O'Bryant, K. (2004), "A complete annotated bibliography of work related to Sidon sequences", Electronic Journal of Combinatorics, 11: 39.
  5. ^ Erdős, P. (1956). "Problems and results in additive number theory". Colloque sur la Théorie des Nombres: 127–137.
  6. See p. 264 of Erdős–Tetali (1990).
  7. See Theorem 1 of Chapter III.
  8. Section 1.8 of Tao & Vu (2006).
  9. Vu, Van H. (2000-07-01). "On the concentration of multivariate polynomials with small expectation". Random Structures & Algorithms. 16 (4): 344–363. CiteSeerX 10.1.1.116.1310. doi:10.1002/1098-2418(200007)16:4<344::aid-rsa4>3.0.co;2-5. ISSN 1098-2418.
  10. Chapter 8, p. 139 of Alon & Spencer (2016).
  11. Kolountzakis, Mihail N. (1995-10-13). "An effective additive basis for the integers". Discrete Mathematics. 145 (1): 307–313. doi:10.1016/0012-365X(94)00044-J.
  12. Vu, Van H. (2000-10-15). "On a refinement of Waring's problem". Duke Mathematical Journal. 105 (1): 107–134. CiteSeerX 10.1.1.140.3008. doi:10.1215/s0012-7094-00-10516-9. ISSN 0012-7094.
  13. Táfula, Christian (2019). "An extension of the Erdős-Tetali theorem". Random Structures & Algorithms. 55 (1): 173–214. arXiv:1807.10200. doi:10.1002/rsa.20812. ISSN 1098-2418. S2CID 119249787.
Categories: