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

When $P(x_{1},\ldots ,x_{n})=1$, $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 field ${\mathbb {Z}}/p{\mathbb {Z}}$ 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 ${\mathbb {Z}}/p{\mathbb {Z}}$, every element of ${\mathbb {Z}}/p{\mathbb {Z}}$ can be written as the sum of the elements of some subset (possibly empty) of $S$.

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 ${\mathbb {Z}}/p{\mathbb {Z}}$. 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)=\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(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$.

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

• Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics. Vol. 165. Springer-Verlag. ISBN 0-387-94655-1. Zbl 0859.11003.

External links

• Sun, Zhi-Wei (2006). "An additive theorem and restricted sumsets". Math. Res. Lett. , no. 15 (6): 1263–1276. arXiv:math.CO/0610981.
• Zhi-Wei Sun: On some conjectures of Erdős-Heilbronn, Lev and Snevily (PDF), a survey talk.
• Weisstein, Eric W. "Erdos-Heilbronn Conjecture". MathWorld.