Restricted sumset

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

${\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\},}$

where ${\displaystyle A_{1},\ldots ,A_{n}}$ are finite nonempty subsets of a field F and ${\displaystyle P(x_{1},\ldots ,x_{n})}$ is a polynomial over F.

If ${\displaystyle P}$ is a constant non-zero function, for example ${\displaystyle P(x_{1},\ldots ,x_{n})=1}$ for any ${\displaystyle x_{1},\ldots ,x_{n}}$, then ${\displaystyle S}$ is the usual sumset ${\displaystyle A_{1}+\cdots +A_{n}}$ which is denoted by ${\displaystyle nA}$ if ${\displaystyle A_{1}=\cdots =A_{n}=A.}$

When

${\displaystyle P(x_{1},\ldots ,x_{n})=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}),}$

S is written as ${\displaystyle A_{1}\dotplus \cdots \dotplus A_{n}}$ which is denoted by ${\displaystyle n^{\wedge }A}$ if ${\displaystyle A_{1}=\cdots =A_{n}=A.}$

Note that |S| > 0 if and only if there exist ${\displaystyle a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}}$ with ${\displaystyle 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 ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ we have the inequality ^{[1] [2] [3]}

${\displaystyle |A+B|\geq \min\{p,\,|A|+|B|-1\}}$

where ${\displaystyle 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 ${\displaystyle A,B}$ are subsets of a group ${\displaystyle G}$, then ^[4]

${\displaystyle |A+B|\geq \min\{p(G),\,|A|+|B|-1\}}$

where ${\displaystyle p(G)}$ is the size of the smallest nontrivial subgroup of ${\displaystyle G}$ (we set it to ${\displaystyle 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 ${\displaystyle \mathbb {Z} /n\mathbb {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 ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$, every element of ${\displaystyle \mathbb {Z} /p\mathbb {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 ${\displaystyle |2^{\wedge }A|\geq \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

${\displaystyle |n^{\wedge }A|\geq \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, ^[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 ${\displaystyle f(x_{1},\ldots ,x_{n})}$ be a polynomial over a field ${\displaystyle F}$. Suppose that the coefficient of the monomial ${\displaystyle x_{1}^{k_{1}}\cdots x_{n}^{k_{n}}}$ in ${\displaystyle f(x_{1},\ldots ,x_{n})}$ is nonzero and ${\displaystyle k_{1}+\cdots +k_{n}}$ is the total degree of ${\displaystyle f(x_{1},\ldots ,x_{n})}$. If ${\displaystyle A_{1},\ldots ,A_{n}}$ are finite subsets of ${\displaystyle F}$ with ${\displaystyle |A_{i}|>k_{i}}$ for ${\displaystyle i=1,\ldots ,n}$, then there are ${\displaystyle a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}}$ such that ${\displaystyle f(a_{1},\ldots ,a_{n})\not =0}$.

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, ^[11] and reformulated by Alon in 1999. ^[14]

See also

• Polynomial method in combinatorics

References

1. Nathanson (1996) p.44
2. Geroldinger & Ruzsa (2009) pp.141–142
3. Jeffrey Paul Wheeler (2012). "The Cauchy-Davenport Theorem for Finite Groups". arXiv: 1202.1816 [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. (1994). "Cyclic spaces for Grassmann derivatives and additive theory". Bulletin of the London Mathematical Society . 26 (2): 140–146. doi:10.1112/blms/26.2.140.
11. 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.
12. Hou, Qing-Hu; Sun, Zhi-Wei (2002). "Restricted sums in a field". Acta Arithmetica . 102 (3): 239–249. Bibcode:2002AcAri.102..239H. doi: 10.4064/aa102-3-3 . MR   1884717.
13. 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. S2CID   33387005.
14. Alon, Noga (1999). "Combinatorial Nullstellensatz" (PDF). Combinatorics, Probability and Computing . 8 (1–2): 7–29. doi:10.1017/S0963548398003411. MR   1684621. S2CID   209877602.
15. Alon, Noga; Tarsi, Michael (1989). "A nowhere-zero point in linear mappings". Combinatorica . 9 (4): 393–395. doi:10.1007/BF02125351. MR   1054015. S2CID   8208350.

• 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. Vol. 165. Springer-Verlag. ISBN   0-387-94655-1. Zbl   0859.11003.

External links

• Weisstein, Eric W. "Erdős-Heilbronn Conjecture". MathWorld .