# Restricted sumset

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

${\displaystyle S=\{a_{1}+\cdots +a_{n}:\ a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}\ {\mathrm {and} }\ P(a_{1},\ldots ,a_{n})\not =0\},}$

where ${\displaystyle A_{1},\ldots ,A_{n}}$ are finite nonempty subsets of a field F and ${\displaystyle P(x_{1},\ldots ,x_{n})}$ is a polynomial over F.

${\displaystyle P(x_{1},\ldots ,x_{n})=\prod _{1\leq i

## 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]

${\displaystyle |A+B|\geq \min\{p,\ |A|+|B|-1\}.\,}$

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 ${\displaystyle |2^{\wedge }A|\geq \min\{p,2|A|-3\}}$ 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

${\displaystyle |n^{\wedge }A|\geq \min\{p(F),\ n|A|-n^{2}+1\},}$

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 ${\displaystyle f(x_{1},\ldots ,x_{n})}$ be a polynomial over a field F. Suppose that the coefficient of the monomial ${\displaystyle x_{1}^{k_{1}}\cdots x_{n}^{k_{n}}}$ in ${\displaystyle f(x_{1},\ldots ,x_{n})}$ is nonzero and ${\displaystyle k_{1}+\cdots +k_{n}}$ is the total degree of ${\displaystyle f(x_{1},\ldots ,x_{n})}$. If ${\displaystyle A_{1},\ldots ,A_{n}}$ are finite subsets of F with ${\displaystyle |A_{i}|>k_{i}}$ for ${\displaystyle i=1,\ldots ,n}$, then there are ${\displaystyle a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}}$ such that ${\displaystyle f(a_{1},\ldots ,a_{n})\not =0}$.

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

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. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
9. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
10. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
11. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
12. {{#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 }}