Restricted sumset#Combinatorial Nullstellensatz

{{short description|Sumset of a field subject to a specific polynomial restriction}}

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.

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+\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 $\mathbb{Z}/p\mathbb{Z}$ we have the inequalityNathanson (1996) p.44Geroldinger & Ruzsa (2009) pp.141–142{{Cite arXiv|eprint = 1202.1816|author1 = Jeffrey Paul Wheeler|title = The Cauchy-Davenport Theorem for Finite Groups|year = 2012| class=math.CO }}

: $|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{{Cite journal |last=DeVos |first=Matt |date=2016 |title=On a Generalization of the Cauchy-Davenport Theorem |url=http://math.colgate.edu/~integers/q7/q7.Abstract.html |journal=Integers |volume=16}}

: $|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 $\mathbb{Z}/n\mathbb{Z}$ , there are n elements that sum to zero modulo n. (Here n does not need to be prime.)Nathanson (1996) p.48Geroldinger & Ruzsa (2009) p.53

A direct consequence of the Cauchy-Davenport theorem is: Given any sequence S of p−1 or more nonzero elements, not necessarily distinct, of $\mathbb{Z}/p\mathbb{Z}$ , every element of $\mathbb{Z}/p\mathbb{Z}$ can be written as the sum of the elements of some subsequence (possibly empty) of S.Wolfram's MathWorld, Cauchy-Davenport Theorem, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html, accessed 20 June 2012.

Kneser's theorem generalises this to general abelian groups.Geroldinger & Ruzsa (2009) p.143

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.Nathanson (1996) p.77 This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994{{cite journal

|author1=Dias da Silva, J. A. |author2=Hamidoune, Y. O.

| title = Cyclic spaces for Grassmann derivatives and additive theory

| journal = Bulletin of the London Mathematical Society

| volume = 26

| year = 1994

| pages = 140–146

| doi = 10.1112/blms/26.2.140

| issue = 2}}

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,{{cite journal

|author1=Hou, Qing-Hu |author2-link=Zhi-Wei Sun

|author2=Sun, Zhi-Wei

| title = Restricted sums in a field

| journal = Acta Arithmetica

| volume = 102

| year = 2002

| issue = 3

| pages = 239–249

| mr = 1884717

| doi = 10.4064/aa102-3-3| bibcode = 2002AcAri.102..239H

| doi-access = free

}}

and G. Karolyi in 2004.{{cite journal

| author = Károlyi, Gyula

| title = The Erdős–Heilbronn problem in abelian groups

| journal = Israel Journal of Mathematics

| volume = 139

| year = 2004

| pages = 349–359

| mr = 2041798

| doi = 10.1007/BF02787556| s2cid = 33387005

}}

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.{{cite journal

| author = Alon, Noga

| url = http://www.math.tau.ac.il/~nogaa/PDFS/null2.pdf

| title = Combinatorial Nullstellensatz

| journal = Combinatorics, Probability and Computing

| volume = 8

| issue = 1–2

| year = 1999

| pages = 7–29

| mr = 1684621

| doi = 10.1017/S0963548398003411| s2cid = 209877602

| author-link = Noga Alon

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

This tool was rooted in a paper of N. Alon and M. Tarsi in 1989,{{cite journal

|author1=Alon, Noga |author2=Tarsi, Michael

| title = A nowhere-zero point in linear mappings

| journal = Combinatorica

| volume = 9

| year = 1989

| pages = 393–395

| mr = 1054015

| doi = 10.1007/BF02125351

| issue = 4|s2cid=8208350

|author1-link=Noga Alon

| citeseerx = 10.1.1.163.2348

}}

and developed by Alon, Nathanson and Ruzsa in 1995–1996,{{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

| doi = 10.1006/jnth.1996.0029|author1-link=Noga Alon }}

and reformulated by Alon in 1999.

References

{{cite book | editor1-last=Geroldinger | editor1-first=Alfred | editor2-last=Ruzsa | editor2-first=Imre Z. | others=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) | title=Combinatorial number theory and additive group theory | series=Advanced Courses in Mathematics CRM Barcelona | location=Basel | publisher=Birkhäuser | year=2009 | isbn=978-3-7643-8961-1 | zbl=1177.11005 }}
{{cite book | first=Melvyn B. | last=Nathanson | title=Additive Number Theory: Inverse Problems and the Geometry of Sumsets | volume=165 | series=Graduate Texts in Mathematics | publisher=Springer-Verlag | year=1996 | isbn=0-387-94655-1 | zbl=0859.11003 }}

External links

{{mathworld | urlname = Erdos-HeilbronnConjecture | title = Erdős-Heilbronn Conjecture}}

Category:Augustin-Louis Cauchy

Category:Sumsets

Category:Additive combinatorics

Category:Additive number theory