Restricted sumset

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

[math]\displaystyle{ 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]\displaystyle{ A_1,\ldots,A_n }[/math] are finite nonempty subsets of a field F and [math]\displaystyle{ P(x_1,\ldots,x_n) }[/math] is a polynomial over F.

If [math]\displaystyle{ P }[/math] is a constant non-zero function, for example [math]\displaystyle{ P(x_1,\ldots,x_n)=1 }[/math] for any [math]\displaystyle{ x_1,\ldots,x_n }[/math], then [math]\displaystyle{ S }[/math] is the usual sumset [math]\displaystyle{ A_1+\cdots+A_n }[/math] which is denoted by [math]\displaystyle{ nA }[/math] if [math]\displaystyle{ A_1=\cdots=A_n=A. }[/math]

When

[math]\displaystyle{ P(x_1,\ldots,x_n) = \prod_{1 \le i \lt j \le n} (x_j-x_i), }[/math]

S is written as [math]\displaystyle{ A_1\dotplus\cdots\dotplus A_n }[/math] which is denoted by [math]\displaystyle{ n^{\wedge} A }[/math] if [math]\displaystyle{ A_1=\cdots=A_n=A. }[/math]

Note that |S| > 0 if and only if there exist [math]\displaystyle{ a_1\in A_1,\ldots,a_n\in A_n }[/math] with [math]\displaystyle{ P(a_1,\ldots,a_n)\not=0. }[/math]

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 [math]\displaystyle{ \mathbb{Z}/p\mathbb{Z} }[/math] we have the inequality^[1][2][3]

[math]\displaystyle{ |A+B| \ge \min\{p,\, |A|+|B|-1\} }[/math]

where [math]\displaystyle{ A+B := \{a+b \pmod p \mid a \in A, b \in B\} }[/math], i.e. we're using modular arithmetic. It can be generalised to arbitrary (not necessarily abelian) groups using a Dyson transform. If [math]\displaystyle{ A, B }[/math] are subsets of a group [math]\displaystyle{ G }[/math], then^[4]

[math]\displaystyle{ |A+B| \ge \min\{p(G),\, |A|+|B|-1\} }[/math]

where [math]\displaystyle{ p(G) }[/math] is the size of the smallest nontrivial subgroup of [math]\displaystyle{ G }[/math] (we set it to [math]\displaystyle{ 1 }[/math] if there is no such subgroup).

We may use this to deduce the Erdős–Ginzburg–Ziv theorem: given any sequence of 2n−1 elements in the cyclic group [math]\displaystyle{ \mathbb{Z}/n\mathbb{Z} }[/math], there are n elements that sum to zero modulo n. (Here n does not need to be prime.)^[5][6]

A direct consequence of the Cauchy-Davenport theorem is: Given any sequence S of p−1 or more nonzero elements, not necessarily distinct, of [math]\displaystyle{ \mathbb{Z}/p\mathbb{Z} }[/math], every element of [math]\displaystyle{ \mathbb{Z}/p\mathbb{Z} }[/math] can be written as the sum of the elements of some subsequence (possibly empty) of S.^[7]

Kneser's theorem generalises this to general abelian groups.^[8]

Erdős–Heilbronn conjecture

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

[math]\displaystyle{ |n^\wedge A| \ge \min\{p(F),\ n|A|-n^2+1\}, }[/math]

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,^[11] Q. H. Hou and Zhi-Wei Sun in 2002,^[12] and G. Karolyi in 2004.^[13]

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.^[14] Let [math]\displaystyle{ f(x_1,\ldots,x_n) }[/math] be a polynomial over a field [math]\displaystyle{ F }[/math]. Suppose that the coefficient of the monomial [math]\displaystyle{ x_1^{k_1}\cdots x_n^{k_n} }[/math] in [math]\displaystyle{ f(x_1,\ldots,x_n) }[/math] is nonzero and [math]\displaystyle{ k_1+\cdots+k_n }[/math] is the total degree of [math]\displaystyle{ f(x_1,\ldots,x_n) }[/math]. If [math]\displaystyle{ A_1,\ldots,A_n }[/math] are finite subsets of [math]\displaystyle{ F }[/math] with [math]\displaystyle{ |A_i|\gt k_i }[/math] for [math]\displaystyle{ i=1,\ldots,n }[/math], then there are [math]\displaystyle{ a_1\in A_1,\ldots,a_n\in A_n }[/math] such that [math]\displaystyle{ f(a_1,\ldots,a_n)\not = 0 }[/math].

This tool was rooted in a paper of N. Alon and M. Tarsi in 1989,^[15] and developed by Alon, Nathanson and Ruzsa in 1995–1996,<ref name="Alon1996">{{cite journal

|author1=Alon, Noga |author2=Nathanson, Melvyn B. |author3=Ruzsa, Imre
| url = http://www.math.tau.ac.il/~nogaa/PDFS/anrf3.pdf
| title = The polynomial method and restricted sums of congruence classes
| journal = Journal of Number Theory
| volume = 56
| issue = 2
| year = 1996
| pages = 404–417
| mr = 1373563 

and reformulated by Alon in 1999.^[14]

See also

• Polynomial method in combinatorics

References

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

External links

• Weisstein, Eric W.. "Erdős-Heilbronn Conjecture". http://mathworld.wolfram.com/Erdos-HeilbronnConjecture.html. 

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Restricted sumset. Read more