“Restricted sumset”的意思、由来-开放百科全书

In additive number theory and combinatorics, a restricted sumset has the form

S is written as

which is denoted by

. Note that |S| > 0 if and only if there exist

with

Cauchy–Davenport theorem

The Cauchy–Davenport theorem named after Augustin Louis Cauchy and Harold Davenport asserts that for any prime p and nonempty subsets A and B of the prime order cyclic group Z/pZ we have the inequality^[1]^[2]

We may use this to deduce the Erdős–Ginzburg–Ziv theorem: given any sequence of 2n−1 elements in Z/n, there are n elements that sums to zero modulo n. (Here n does not need to be prime.)^[3]^[4]

A direct consequence of the Cauchy-Davenport theorem is: Given any set S of p−1 or more nonzero elements, not necessarily distinct, of Z/pZ, every element of Z/pZ can be written as the sum of the elements of some subset (possibly empty) of S.^[5]

Erdős–Heilbronn conjecture

The Erdős–Heilbronn conjecture posed by Paul Erdős and Hans Heilbronn in 1964 states that

if p is a prime and A is a nonempty subset of the field Z/pZ.^[7] This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994^[8]

where A is a finite nonempty subset of a field F, and p(F) is a prime p if F is of characteristic p, and p(F) = ∞ if F is of characteristic 0. Various extensions of this result were given by Noga Alon, M. B. Nathanson and I. Ruzsa in 1996,^[9] Q. H. Hou and Zhi-Wei Sun in 2002,^[9]

Combinatorial Nullstellensatz

A powerful tool in the study of lower bounds for cardinalities of various restricted sumsets is the following fundamental principle: the combinatorial Nullstellensatz.^[11] Let

be a polynomial over a field F. Suppose that the coefficient of the monomial

is nonzero and

is the total degree of

. If

are finite subsets of F with

for

, then there are

such that

The method using the combinatorial Nullstellensatz is also called the polynomial method. This tool was rooted in a paper of N. Alon and M. Tarsi in 1989,^[12]

References

1. ^Nathanson (1996) p.44
2. ^Geroldinger & Ruzsa (2009) pp.141–142
3. ^Nathanson (1996) p.48
4. ^Geroldinger & Ruzsa (2009) p.53
5. ^Wolfram's MathWorld, Cauchy-Davenport Theorem, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html, accessed 20 June 2012.
6. ^Geroldinger & Ruzsa (2009) p.143
7. ^Nathanson (1996) p.77
8. ^{{cite journal | author = Dias da Silva, J. A.; Hamidoune, Y. O. | title = Cyclic spaces for Grassmann derivatives and additive theory | journal = Bulletin of the London Mathematical Society | volume = 26 | year = 1994 | pages = 140–146 | doi = 10.1112/blms/26.2.140 | issue = 2}}
9. ^{{cite journal | author = Hou, Qing-Hu; Sun, Zhi-Wei | title = Restricted sums in a field | journal = Acta Arithmetica | volume = 102 | year = 2002 | issue = 3 | pages = 239–249 | mr = 1884717 | doi = 10.4064/aa102-3-3| bibcode = 2002AcAri.102..239H }}
10. ^{{cite journal | author = Károlyi, Gyula | title = The Erdős–Heilbronn problem in abelian groups | journal = Israel Journal of Mathematics | volume = 139 | year = 2004 | pages = 349–359 | mr = 2041798 | doi = 10.1007/BF02787556}}
11. ^¹{{cite journal | author = Alon, Noga | url = http://www.math.tau.ac.il/~nogaa/PDFS/null2.pdf | title = Combinatorial Nullstellensatz | journal = Combinatorics, Probability and Computing | volume = 8 | issue = 1–2 | year = 1999 | pages = 7–29 | mr = 1684621 | doi = 10.1017/S0963548398003411}}
12. ^{{cite journal | author = Alon, Noga; Tarsi, Michael | title = A nowhere-zero point in linear mappings | journal = Combinatorica | volume = 9 | year = 1989 | pages = 393–395 | mr = 1054015 | doi = 10.1007/BF02125351 | issue = 4}}
13. ^¹{{cite journal | author = Alon, Noga; Nathanson, Melvyn B.; Ruzsa, Imre | url = http://www.math.tau.ac.il/~nogaa/PDFS/anrf3.pdf | title = The polynomial method and restricted sums of congruence classes | journal = Journal of Number Theory | volume = 56 | issue = 2 | year = 1996 | pages = 404–417 | mr = 1373563 | doi = 10.1006/jnth.1996.0029}}

Cauchy–Davenport theorem

Erdős–Heilbronn conjecture

Combinatorial Nullstellensatz

References

External links