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

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^[1]^[2]

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

We may use this to deduce the Erdős–Ginzburg–Ziv theorem: given any sequence of 2n−1 elements in Z/n, there are n elements that sums to zero modulo n. (Here n does not need to be prime.)^[3]^[4]

A direct consequence of the Cauchy-Davenport theorem is: Given any set S of p−1 or more nonzero 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.^[5]

Kneser's theorem generalises this to finite abelian groups.^[6]

Erdős-Heilbronn conjecture

The Erdős–Heilbronn conjecture posed by Paul Erdős and Hans 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 Z/pZ.^[7] This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994^[8] who showed that

|n^\wedge A|\ge\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,^[9] Q. H. Hou and Zhi-Wei Sun in 2002,^[10] and G. Karolyi in 2004.^[11]

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.^[12] 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,^[13] and developed by Alon, Nathanson and Ruzsa in 1995-1996,^[9] and reformulated by Alon in 1999.^[12]

References

↑ Nathanson (1996) p.44
↑ Geroldinger & Ruzsa (2009) pp.141–142
↑ Nathanson (1996) p.48
↑ Geroldinger & Ruzsa (2009) p.53
↑ Wolfram's MathWorld, Cauchy-Davenport Theorem, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html, accessed 20 June 2012.
↑ Geroldinger & Ruzsa (2009) p.143
↑ Nathanson (1996) p.77
↑ Dias da Silva, J. A.; Hamidoune, Y. O. (1994). "Cyclic spaces for Grassman derivatives and additive theory". Bulletin of the London Mathematical Society 26 (2): 140–146. doi:10.1112/blms/26.2.140.
1 2 Alon, Noga; Nathanson, Melvyn B.; Ruzsa, Imre (1996). "The polynomial method and restricted sums of congruence classes" (PDF). Journal of Number Theory 56 (2): 404–417. doi:10.1006/jnth.1996.0029. MR 1373563.
↑ Hou, Qing-Hu; Sun, Zhi-Wei (2002). "Restricted sums in a field". Acta Arithmetica 102 (3): 239–249. doi:10.4064/aa102-3-3. MR 1884717.
↑ Károlyi, Gyula (2004). "The Erdős–Heilbronn problem in abelian groups". Israel Journal of Mathematics 139: 349–359. doi:10.1007/BF02787556. MR 2041798.
1 2 Alon, Noga (1999). "Combinatorial Nullstellensatz" (PDF). Combinatorics, Probability and Computing 8 (1–2): 7–29. doi:10.1017/S0963548398003411. MR 1684621.
↑ Alon, Noga; Tarsi, Michael (1989). "A nowhere-zero point in linear mappings". Combinatorica 9 (4): 393–395. doi:10.1007/BF02125351. MR 1054015.

Geroldinger, Alfred; Ruzsa, Imre Z., eds. (2009). Combinatorial number theory and additive group theory. Advanced Courses in Mathematics CRM Barcelona. Elsholtz, C.; Freiman, G.; Hamidoune, Y. O.; Hegyvári, N.; Károlyi, G.; Nathanson, M.; Solymosi, J.; Stanchescu, Y. With a foreword by Javier Cilleruelo, Marc Noy and Oriol Serra (Coordinators of the DocCourse). Basel: Birkhäuser. ISBN 978-3-7643-8961-1. Zbl 1177.11005.
Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics 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., "Erdős-Heilbronn Conjecture", MathWorld.

This article is issued from Wikipedia - version of the Monday, February 01, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.