# Restricted sumset

In additive number theory and combinatorics, a restricted sumset has the form
    $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 $A_{1},\ldots ,A_{n}$ are finite nonempty subsets of a field F and $P(x_{1},\ldots ,x_{n})$ is a polynomial over F.
If $P$ is a constant non-zero function, for example $P(x_{1},\ldots ,x_{n})=1$ for any $x_{1},\ldots ,x_{n}$, then $S$ is the usual sumset $A_{1}+\cdots +A_{n}$ which is denoted by $nA$ if $A_{1}=\cdots =A_{n}=A.$
When
    $P(x_{1},\ldots ,x_{n})=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}),$
S is written as $A_{1}\dotplus \cdots \dotplus A_{n}$ which is denoted by $n^{\wedge }A$ if $A_{1}=\cdots =A_{n}=A.$
Note that |S| > 0 if and only if there exist $a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}$ with $P(a_{1},\ldots ,a_{n})\not =0.$

## 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 $\mathbb {Z} /p\mathbb {Z}$ we have the inequality
    $|A+B|\geq \min\{p,\,|A|+|B|-1\}$
where $A+B:=\{a+b{\pmod {p}}\mid a\in A,b\in B\}$, i.e. we're using modular arithmetic. It can be generalised to arbitrary (not necessarily abelian) groups using a Dyson transform. If $A,B$ are subsets of a group $G$, then
    $|A+B|\geq \min\{p(G),\,|A|+|B|-1\}$
where $p(G)$ is the size of the smallest nontrivial subgroup of $G$ (we set it to $1$ 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 $\mathbb {Z} /n\mathbb {Z}$, there are n elements that sum to zero modulo n. (Here n does not need to be prime.)
A direct consequence of the Cauchy-Davenport theorem is: Given any sequence S of p−1 or more nonzero elements, not necessarily distinct, of $\mathbb {Z} /p\mathbb {Z}$, every element of $\mathbb {Z} /p\mathbb {Z}$ can be written as the sum of the elements of some subsequence (possibly empty) of S.
Kneser's theorem generalises this to general abelian groups.

## Erdős–Heilbronn conjecture

The Erdős–Heilbronn conjecture posed by Paul Erdős and Hans Heilbronn in 1964 states that $|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. This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994 who showed that
    $|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, Q. H. Hou and Zhi-Wei Sun in 2002, and G. Karolyi in 2004.

## 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. Let $f(x_{1},\ldots ,x_{n})$ be a polynomial over a field $F$. Suppose that the coefficient of the monomial $x_{1}^{k_{1}}\cdots x_{n}^{k_{n}}$ in $f(x_{1},\ldots ,x_{n})$ is nonzero and $k_{1}+\cdots +k_{n}$ is the total degree of $f(x_{1},\ldots ,x_{n})$. If $A_{1},\ldots ,A_{n}$ are finite subsets of $F$ with $|A_{i}|>k_{i}$ for $i=1,\ldots ,n$, then there are $a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}$ such that $f(a_{1},\ldots ,a_{n})\not =0$.
This tool was rooted in a paper of N. Alon and M. Tarsi in 1989, and developed by Alon, Nathanson and Ruzsa in 1995–1996, and reformulated by Alon in 1999.