Restricted sumset

From Wikipedia, the free encyclopedia

In combinatorial number theory, 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 $n A$ if $A_1=\cdots=A_n=A$ ; when

$P(x_1,\ldots,x_n)=\prod_{1\le i<j\le 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$ .

The Cauchy-Davenport theorem named after Cauchy and H. Davenport asserts that for any prime $p$ and nonempty subsets $A$ and $B$ of the field $\Bbb Z/p\Bbb Z$ we have the inequality

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

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

$|n^\wedge A|\ge\min\{p(F),\ n|A|-|A|^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.

A powerful tool in the study of lower bounds for cardinalities of various restricted sumsets is the following fundamental principle:

Combinatorial Nullstellensatz [1] Let $f(x_1,\ldots,x_n)$ be a polynomial over a filed $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[2] in 1995-1996, and reformulated by Alon [3] in 1999.

[edit] References

Noga Alon and M. Tarsi: A nowhere-zero point in linear mappings, Combinatorica 9(1989), 393-395.

J.A. Dias da Silva and Y.O. Hamidoune: Cyclic spaces for Grassman derivatives and additive theory, Bull. London Math. Soc. 26(1974), 140-146.

N. Alon, M.B. Nathanson and I. Ruzsa: The polynomial method and restricted sums of congruence classes (PDF) , J. Number Theory 56(1996), 404-417.

Noga Alon: Combinatorial Nullstellensatz (PDF) , Combin. Probab. Comput. 8(1999), 7-29.

Q. H. Hou and Z. W. Sun: Restricted sums in a field, Acta Arith. 102(2002), 239-249.

G. Karolyi: The Erdős-Heilbronn problem in abelian groups, Israel J. Math. 139(2004), 349-359.

Zhi-Wei Sun: On some conjectures of Erdős-Heilbronn, Lev and Snevily (PDF), a survey talk.

Zhi-Wei Sun: An additive theorem and restricted sumsets (PDF), a recent paper.

Retrieved from "http://en.wikipedia.org../../../r/e/s/Restricted_sumset.html"

Categories: Combinatorics | Number theory

Restricted sumset

From Wikipedia, the free encyclopedia

[edit] References

Views

Navigation

Search