# Restricted sumset

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

where are finite nonempty subsets of a field *F* and is a polynomial over *F*.

When , *S* is the usual sumset which is denoted by *nA* if ; when

*S* is written as which is denoted by if . 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**/*p***Z** we have the inequality^{[1]}^{[2]}

We may use this to deduce the Erdős–Ginzburg–Ziv theorem: given any 2*n*−1 elements of **Z**/*n*, there is a non-trivial subset 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 elements, not necessarily distinct, of **Z**/*p***Z**, every element of **Z**/*p***Z** can be written as the sum of the elements of some subset (possibly empty) of *S*.^{[5]}

Kneser's theorem generalises this to finite abelian groups.^{[6]}

## 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**/*p***Z**.^{[7]} This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994^{[8]}
who showed that

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,^{[10]}
and G. Karolyi in 2004.^{[11]}

## 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.^{[12]} Let be a polynomial over a field *F*. Suppose that the coefficient of the monomial in 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,^{[13]}
and developed by Alon, Nathanson and Ruzsa in 1995-1996,^{[9]}
and reformulated by Alon in 1999.^{[12]}

## References

- ↑ Nathanson (1996) p.44
- ↑ Geroldinger & Ruzsa (2009) pp.141–142
- ↑ Nathanson (1996) p.48
- ↑ Geroldinger & Ruzsa (2009) p.53
- ↑ Wolfram's MathWorld, Cauchy-Davenport Theorem, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html, accessed 20 June 2012.
- ↑ Geroldinger & Ruzsa (2009) p.143
- ↑ Nathanson (1996) p.77
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑
^{9.0}^{9.1}{{#invoke:Citation/CS1|citation |CitationClass=journal }} - ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑
^{12.0}^{12.1}{{#invoke:Citation/CS1|citation |CitationClass=journal }} - ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

## External links

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}