Related Searches
Definitions

# Restricted sumset

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

$S=\left\{a_1+cdots+a_n: a_1in A_1,ldots,a_nin 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\left(x_1,ldots,x_n\right)$ is a polynomial over $F$.

When $P\left(x_1,ldots,x_n\right)=1$, $S$ is the usual sumset $A_1+cdots+A_n$ which is denoted by $nA$ if $A_1=cdots=A_n=A$; when

$S$ is written as $A_1dotpluscdotsdotplus A_n$ which is denoted by $n^\left\{wedge\right\} A$ if $A_1=cdots=A_n=A$. Note that $|S|>0$ if and only if there exist $a_1in A_1,ldots,a_nin A_n$ with $P\left(a_1,ldots,a_n\right)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 field $Bbb Z/pBbb Z$ we have the inequality

$|A+B|gemin\left\{p, |A|+|B|-1\right\}.,$

## Erdős–Heilbronn conjecture

The Erdős–Heilbronn conjecture posed by Paul Erdős and Hans Heilbronn in 1964 states that $|2^wedge A|gemin\left\{p,2|A|-3\right\}$ if $p$ is a prime and $A$ is a nonempty subset of the field $Bbb Z/pBbb Z$. This was first confirmed by J.A. Dias da Silva and Y.O. Hamidoune in 1994 who showed that

$|n^wedge A|gemin\left\{p\left(F\right), n|A|-n^2+1\right\},$

where $A$ is a finite nonempty subset of a field $F$, and $p\left(F\right)$ is a prime $p$ if $F$ is of characteristic $p$, and $p\left(F\right)=infty$ 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\left(x_1,ldots,x_n\right)$ be a polynomial over a field $F$. Suppose that the coefficient of the monomial $x_1^\left\{k_1\right\}cdots x_n^\left\{k_n\right\}$ in $f\left(x_1,ldots,x_n\right)$ is nonzero and $k_1+cdots+k_n$ is the total degree of $f\left(x_1,ldots,x_n\right)$. 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_1in A_1,ldots,a_nin A_n$ such that $f\left(a_1,ldots,a_n\right)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, and developed by Alon, Nathanson and Ruzsa in 1995-1996, and reformulated by Alon in 1999.

## References

| doi = 10.1017/S0963548398003411}}

| doi = 10.1006/jnth.1996.0029}}

| doi = 10.1007/BF02125351}}

| doi = 10.1007/BF02787556}}

• Sun, Zhi-Wei (2006). "An additive theorem and restricted sumsets". 0610981. }}