In additive number theory and combinatorics, a restricted sumset has the form
- <math>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\},</math> where <math> A_1,\ldots,A_n</math> are finite nonempty subsets of a field <math>F</math> and <math>P(x_1,\ldots,x_n)</math> is a polynomial over <math>F</math>. When <math>P(x_1,\ldots,x_n)=1</math>, <math>S</math> is the usual sumset <math>A_1+\cdots+A_n</math> which is denoted by <math>nA</math> if <math>A_1=\cdots=A_n=A</math>; when
- <math>P(x_1,\ldots,x_n)=\prod_{1\le i<j\le n}(x_j-x_i),</math>
<math>S</math> is written as <math>A_1\dotplus\cdots\dotplus A_n</math> which is denoted by <math>n^{\wedge} A</math> if <math>A_1=\cdots=A_n=A</math>. Note that <math>|S|>0</math> if and only if there exist <math>a_1\in A_1,\ldots,a_n\in A_n</math> with <math>P(a_1,\ldots,a_n)\not=0</math>. The Cauchy–Davenport theorem named after Cauchy and Harold Davenport asserts that for any prime <math>p</math> and nonempty subsets <math>A</math> and <math>B</math> of the field <math>\Bbb Z/p\Bbb Z</math> we have the inequality
- <math>|A+B|\ge\min\{p,\ |A|+|B|-1\}.</math>
The Erdős–Heilbronn conjecture posed by Paul Erdős and Hans Heilbronn in 1964 states that <math>|2^\wedge A|\ge\min\{p,2|A|-3\}</math> if <math>p</math> is a prime and <math>A</math> is a nonempty subset of the field <math>\Bbb Z/p\Bbb Z</math>. This was first confirmed by J.A. Dias da Silva and Y.O. Hamidoune in 1994 who showed that
- <math>|n^\wedge A|\ge\min\{p(F),\ n|A|-|A|^2+1\},</math>
where <math>A</math> is a finite nonempty subset of a field <math>F</math>, and <math>p(F)</math> is a prime <math>p</math> if <math>F</math> is of characteristic <math>p</math>, and <math>p(F)=\infty</math> if <math>F</math> 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 <math>f(x_1,\ldots,x_n)</math> be a polynomial over a field <math>F</math>. Suppose that the coefficient of the monomial <math>x_1^{k_1}\cdots x_n^{k_n}</math> in <math>f(x_1,\ldots,x_n)</math> is nonzero and <math>k_1+\cdots+k_n</math> is the total degree of <math>f(x_1,\ldots,x_n)</math>. If <math>A_1,\ldots,A_n</math> are finite subsets of <math>F</math> with <math>|A_i|>k_i</math> for <math>i=1,\ldots,n</math>, then there are <math>a_1\in A_1,\ldots,a_n\in A_n</math> such that <math>f(a_1,\ldots,a_n)\not=0</math>. 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.
References
- Alon, Noga (1999). "Combinatorial Nullstellensatz". Combinatorics, Probability and Computing 8 (1–2): 7–29. doi:10.1017/S0963548398003411. MR1684621.
- Alon, Noga; Nathanson, Melvyn B.; Ruzsa, Imre (1996). "The polynomial method and restricted sums of congruence classes". Journal of Number Theory 56 (2): 404–417. doi:10.1006/jnth.1996.0029. MR1373563.
- Alon, Noga; Tarsi, Michael (1989). "A nowhere-zero point in linear mappings". Combinatorica 9: 393–395. doi:10.1007/BF02125351. MR1054015.
- Dias da Silva, J. A.; Hamidoune, Y. O. (1974). "Cyclic spaces for Grassman derivatives and additive theory". Bulletin of the London Mathematical Society 26: 140–146.
- Hou, Qing-Hu; Sun, Zhi-Wei (2002). "Restricted sums in a field". Acta Arithmetica 102 (3): 239–249. MR1884717.
- Károlyi, Gyula (2004). "The Erdős–Heilbronn problem in abelian groups". Israel Journal of Mathematics 139: 349–359. MR2041798.
- Sun, Zhi-Wei (2006). "An additive theorem and restricted sumsets". arXiv:math.CO/0610981.
