Restricted sumset

From formulasearchengine
Jump to navigation Jump to search

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/pZ we have the inequality[1][2]

We may use this to deduce the Erdős–Ginzburg–Ziv theorem: given any 2n−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/pZ, every element of Z/pZ 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/pZ.[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]


  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,, accessed 20 June 2012.
  6. Geroldinger & Ruzsa (2009) p.143
  7. Nathanson (1996) p.77
  8. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  9. 9.0 9.1 {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  10. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  11. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  12. 12.0 12.1 {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  13. {{#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 }}