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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1,\ldots,A_n} are finite nonempty subsets of a field F and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} is the usual sumset Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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\leq i<j\leq n}(x_{j}-x_{i}),

S is written as Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 $\mathbb {Z} /p\mathbb {Z}$ we have the inequality^[1]^[2]^[3]

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A+B| \ge \min\{p,\, |A|+|B|-1\}}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A, B} are subsets of a group Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} , then^[4]

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A+B| \ge \min\{p(G),\, |A|+|B|-1\}}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(G)} is the size of the smallest nontrivial subgroup of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}/p\mathbb{Z}} , every element of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |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,^[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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_1,\ldots,x_n)} be a polynomial over a field Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} . Suppose that the coefficient of the monomial Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x_{1}^{k_{1}}\cdots x_{n}^{k_{n}}} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_1,\ldots,x_n)} is nonzero and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k_1+\cdots+k_n} is the total degree of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_1,\ldots,x_n)} . If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1,\ldots,A_n} are finite subsets of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} with $|A_{i}|>k_{i}$ for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=1,\ldots,n} , then there are Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1\in A_1,\ldots,a_n\in A_n} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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]

References

^ Nathanson (1996) p.44
^ Geroldinger & Ruzsa (2009) pp.141–142
^ Jeffrey Paul Wheeler (2012). "The Cauchy-Davenport Theorem for Finite Groups". arXiv:1202.1816 [math.CO].
^ DeVos, Matt (2016). "On a Generalization of the Cauchy-Davenport Theorem". Integers. 16.
^ 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 Grassmann derivatives and additive theory". Bulletin of the London Mathematical Society. 26 (2): 140–146. doi:10.1112/blms/26.2.140.
^ ^11.0 ^11.1 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. Bibcode:2002AcAri.102..239H. 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. S2CID 33387005.
^ ^14.0 ^14.1 Alon, Noga (1999). "Combinatorial Nullstellensatz" (PDF). Combinatorics, Probability and Computing. 8 (1–2): 7–29. doi:10.1017/S0963548398003411. MR 1684621. S2CID 209877602.
^ Alon, Noga; Tarsi, Michael (1989). "A nowhere-zero point in linear mappings". Combinatorica. 9 (4): 393–395. CiteSeerX 10.1.1.163.2348. 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.

[1] Nathanson (1996) p.44

[GR1412-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

[GR53-6] Geroldinger & Ruzsa (2009) p.53

[7] Wolfram's MathWorld, Cauchy-Davenport Theorem, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html, accessed 20 June 2012.

[GR143-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.

[Alon1996-11] 11.0 ^11.1 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.

[Alon1999-14] 14.0 ^14.1 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. CiteSeerX 10.1.1.163.2348. doi:10.1007/BF02125351. MR 1054015. S2CID 8208350.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Cauchy–Davenport theorem

Erdős–Heilbronn conjecture

Combinatorial Nullstellensatz

See also

References

External links