Sumset of a field subject to a specific polynomial restriction
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.
If is a constant non-zero function, for example for any , then is the usual sumset which is denoted by 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 we have the inequality[1][2][3]
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]
Kneser's theorem generalises this to general abelian groups.[8]
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.[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 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,[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]