Restricted sumset explained

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

S = \{a _{1+ … +a} _{n: a} _{1\in} A _{1,\ldots,a} _{n\in} A _{n} 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.

If

P is a constant non-zero function, for example P(x _{1,\ldots,x} _{n)=1} for any x _{1,\ldots,x} _{n} , then S is the usual sumset A _{1+ … +A} _{n} which is denoted by nA if A _{1= … =A} _{n=A.}

When

P(x _{1,\ldots,x} _{n)} = \prod _{1} (x _{j-x} _{i),}

S is written as

A _{• 1 • plus … plus} A _{n} which is denoted by n ^{\wedge} A if A _{1= … =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

Z /p Z we have the inequality^{[1] [2] [3]} |A + B| \ge min \{p, |A| + |B| -1 \}

where

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

where

p(G) is the size of the smallest nontrivial subgroup of G (we set it to 1 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

Z /n Z , 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

Z /p Z , every element of Z /p Z 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

| 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.^[9] This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994^[10] 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, Q. H. Hou and Zhi-Wei Sun in 2002,^[11] and G. Karolyi in 2004.^[12]

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.^[13] Let

f(x _{1,\ldots,x} _{n)} be a polynomial over a field F . Suppose that the coefficient of the monomial x ^{k _{1}} _{1} … x ^{k _{n}} _{n} in f(x _{1,\ldots,x} _{n)} is nonzero and k _{1+ … +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 .

This tool was rooted in a paper of N. Alon and M. Tarsi in 1989,^[14] and developed by Alon, Nathanson and Ruzsa in 1995–1996,^[15] and reformulated by Alon in 1999.^[13]

See also

• Polynomial method in combinatorics

References

• Book: Geroldinger . Alfred . Ruzsa . Imre Z. . 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) . Combinatorial number theory and additive group theory . Advanced Courses in Mathematics CRM Barcelona . Basel . Birkhäuser . 2009 . 978-3-7643-8961-1 . 1177.11005 .
• Book: Nathanson, Melvyn B. . Additive Number Theory: Inverse Problems and the Geometry of Sumsets . 165 . . . 1996 . 0-387-94655-1 . 0859.11003 .

Notes and References

1. Nathanson (1996) p.44
2. Geroldinger & Ruzsa (2009) pp.141–142
3. 1202.1816. Jeffrey Paul Wheeler. The Cauchy-Davenport Theorem for Finite Groups. 2012. math.CO .
4. DeVos . Matt . 2016 . On a Generalization of the Cauchy-Davenport Theorem . Integers . 16.
5. Nathanson (1996) p.48
6. Geroldinger & Ruzsa (2009) p.53
7. Wolfram's MathWorld, Cauchy-Davenport Theorem, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html, accessed 20 June 2012.
8. Geroldinger & Ruzsa (2009) p.143
9. Nathanson (1996) p.77
10. Dias da Silva, J. A. . Hamidoune, Y. O. . Cyclic spaces for Grassmann derivatives and additive theory . . 26 . 1994 . 140–146 . 10.1112/blms/26.2.140 . 2.
11. Hou, Qing-Hu . Zhi-Wei Sun . Sun, Zhi-Wei . Restricted sums in a field . . 102 . 2002 . 3 . 239–249 . 1884717 . 10.4064/aa102-3-3. 2002AcAri.102..239H . free .
12. Károlyi, Gyula . The Erdős–Heilbronn problem in abelian groups . . 139 . 2004 . 349–359 . 2041798 . 10.1007/BF02787556. 33387005 .
13. Alon, Noga . Combinatorial Nullstellensatz . . 8 . 1–2 . 1999 . 7–29 . 1684621 . 10.1017/S0963548398003411. 209877602 . Noga Alon .
14. Alon, Noga . Tarsi, Michael . A nowhere-zero point in linear mappings . . 9 . 1989 . 393–395 . 1054015 . 10.1007/BF02125351 . 4. 8208350 . Noga Alon . 10.1.1.163.2348 .
15. Alon, Noga . Nathanson, Melvyn B. . Ruzsa, Imre . The polynomial method and restricted sums of congruence classes . . 56 . 2 . 1996 . 404–417 . 1373563 . 10.1006/jnth.1996.0029. Noga Alon .