where , i.e. we're using
modular arithmetic. It can be generalised to arbitrary (not necessarily abelian) groups using a
Dyson transform. If are subsets of a group , then[4]
where is the size of the smallest nontrivial subgroup of (we set it to if there is no such subgroup).
We may use this to deduce the
Erdős–Ginzburg–Ziv theorem: given any sequence of 2n−1 elements in the cyclic group , there are n elements that sum to zero modulo n. (Here n does not need to be prime.)[5][6]
A direct consequence of the Cauchy-Davenport theorem is: Given any sequence S of p−1 or more nonzero elements, not necessarily distinct, of , every element of can be written as the sum of the elements of some subsequence (possibly empty) of S.[7]
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.[9] This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994[10]
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
characteristicp, 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,[11] Q. H. Hou and
Zhi-Wei Sun in 2002,[12]
and G. Karolyi in 2004.[13]
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.[14] Let be a polynomial over a field . Suppose that the
coefficient of the
monomial in is nonzero and is the
total degree of . If are finite subsets of with for , then there are such that .
This tool was rooted in a paper of
N. Alon and M. Tarsi in 1989,[15]
and developed by Alon, Nathanson and Ruzsa in 1995–1996,[11]
and reformulated by Alon in 1999.[14]
Geroldinger, Alfred; Ruzsa, Imre Z., eds. (2009). Combinatorial number theory and additive group theory. Advanced Courses in Mathematics CRM Barcelona. Elsholtz, C.; Freiman, G.; Hamidoune, Y. O.; Hegyvári, N.; Károlyi, G.; Nathanson, M.; Solymosi, J.; Stanchescu, Y. With a foreword by Javier Cilleruelo, Marc Noy and Oriol Serra (Coordinators of the DocCourse). Basel: Birkhäuser.
ISBN978-3-7643-8961-1.
Zbl1177.11005.