Restricted sumset

${\displaystyle S=\{a_1+\cdots +a_n:a_1\in A_1,\dots ,a_n\in A_n\mathrm{a}\mathrm{n}\mathrm{d}P(a_1,\dots ,a_n)\ne 0\},}$

where ${\displaystyle A_1,\dots ,A_n}$ are finite nonempty subsets of a field F and ${\displaystyle P(x_1,\dots ,x_n)}$ is a polynomial over F.

If ${\displaystyle P}$ is a constant non-zero function, for example ${\displaystyle P(x_1,\dots ,x_n)=1}$ for any ${\displaystyle x_1,\dots ,x_n}$, then ${\displaystyle S}$ is the usual sumset ${\displaystyle A_1+\cdots +A_n}$ which is denoted by ${\displaystyle nA}$ if ${\displaystyle A_1=\cdots =A_n=A.}$

When

${\displaystyle P(x_1,\dots ,x_n)=\prod _{1\le i<j\le n}(x_j-x_i),}$

S is written as ${\displaystyle A_1\dotplus \cdots \dotplus A_n}$ which is denoted by ${\displaystyle n^{\wedge }A}$ if ${\displaystyle A_1=\cdots =A_n=A.}$

Note that |S| > 0 if and only if there exist ${\displaystyle a_1\in A_1,\dots ,a_n\in A_n}$ with ${\displaystyle P(a_1,\dots ,a_n)\ne 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 ${\displaystyle \mathbb{Z}/p\mathbb{Z}}$ we have the inequality

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

where ${\displaystyle A+B:=\{a+b(\mathrm{mod}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 ${\displaystyle A,B}$ are subsets of a group ${\displaystyle G}$, then

${\displaystyle |A+B|\ge min\{p(G),|A|+|B|-1\}}$

where ${\displaystyle p(G)}$ is the size of the smallest nontrivial subgroup of ${\displaystyle G}$ (we set it to ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \mathbb{Z}/p\mathbb{Z}}$, every element of ${\displaystyle \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.