# 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\},$ $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

$|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.)

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.

Kneser's theorem generalises this to finite 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

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, and developed by Alon, Nathanson and Ruzsa in 1995-1996, and reformulated by Alon in 1999.