“Erdős–Tetali theorem”的意思、由来-开放百科全书

In additive number theory, an area of mathematics, the Erdős–Tetali theorem is an existence theorem concerning economical additive basis of every order. More specifically, it states that for every fixed integer

, there exists a subset of the natural numbers

satisfying

where

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

is called economical^[1] (or sometimes thin^[2]) 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^[3] 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,^[4] 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 (1990).^[5]

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

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 (1983).^[6]

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 (2006)^[7] present this proof with a more sophisticated two-sided concentration inequality by V. Vu (2000),^[8] thus relatively simplifying this step. Alon & Spencer (2016) classify this proof as an instance of the Poisson paradigm.^[9]

See also

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)^[10] 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 (2000)^[11] 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

Strong form of 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

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.

References

1. ^As in Halberstam & Roth (1983), p. 111.
2. ^As in Tao & Vu (2006), p. 13.
3. ^See Definition 3 (p. 3) of O'Bryant, K. (2004), "A complete annotated bibliography of work related to Sidon sequences" (PDF), Electronic Journal of Combinatorics, 11: 39.
4. ^{{Cite journal|last=Erdős|first=P.|date=1956|title=Problems and results in additive number theory|url=|journal=Colloque Sur le Theorie des Nombres|volume=|pages=127–137|via=}}
5. ^p. 264 of Erdős & Tetali (1990).
6. ^See Theorem 1 of Chapter III.
7. ^Section 1.8 of Tao & Vu (2006).
8. ^{{Cite journal|last=Vu|first=Van H.|date=2000-07-01|title=On the concentration of multivariate polynomials with small expectation|url=http://onlinelibrary.wiley.com/doi/10.1002/1098-2418(200007)16:43.0.CO;2-5/abstract|journal=Random Structures & Algorithms|language=en|volume=16|issue=4|pages=344–363|doi=10.1002/1098-2418(200007)16:4<344::aid-rsa4>3.0.co;2-5|issn=1098-2418|citeseerx=10.1.1.116.1310}}
9. ^Chapter 8, p. 139 of Alon & Spencer (2016).
10. ^{{Cite journal|last=Kolountzakis|first=Mihail N.|date=1995-10-13|title=An effective additive basis for the integers|url=http://www.sciencedirect.com/science/article/pii/0012365X9400044J|journal=Discrete Mathematics|volume=145|issue=1|pages=307–313|doi=10.1016/0012-365X(94)00044-J}}
11. ^{{Cite journal|last=Vu|first=Van H.|date=2000-10-15|title=On a refinement of Waring's problem|journal=Duke Mathematical Journal|volume=105|issue=1|pages=107–134|doi=10.1215/s0012-7094-00-10516-9|issn=0012-7094|citeseerx=10.1.1.140.3008}}