Restricted sumset

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 + ⋯ + a n :   a 1 ∈ A 1 , … , a n ∈ A n   a n d   P ( a 1 , … , a n ) ≠ 0 } , {\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  A 1 , … , A n {\displaystyle A_{1},\ldots ,A_{n}} are finite nonempty subsets of a field F and  P ( x 1 , … , x n ) {\displaystyle P(x_{1},\ldots ,x_{n})} is a polynomial over F.

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

When

P ( x 1 , … , x n ) = ∏ 1 ≤ i < j ≤ n ( x j − x i ) , {\displaystyle P(x_{1},\ldots ,x_{n})=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}),}

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

Note that |S| > 0 if and only if there exist  a 1 ∈ A 1 , … , a n ∈ A n {\displaystyle a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}} with  P ( a 1 , … , a n ) ≠ 0. {\displaystyle P(a_{1},\ldots ,a_{n})\not =0.}

## Cauchy–Davenport theorem

[edit]

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

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

where  A + B := { a + b ( mod p ) ∣ a ∈ A , b ∈ B } {\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  A , B {\displaystyle A,B} are subsets of a group  G {\displaystyle G} , then[4]

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

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

[edit]

The Erdős–Heilbronn conjecture posed by Paul Erdős and Hans Heilbronn in 1964 states that  | 2 ∧ A | ≥ min { p , 2 | A | − 3 } {\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

| n ∧ A | ≥ min { p ( F ) ,   n | A | − n 2 + 1 } , {\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

[edit]

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

[edit]

* Polynomial method in combinatorics

## References

[edit]

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. ^ a b 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. ^ a b Alon, Noga (1999). "Combinatorial Nullstellensatz" (PDF). Combinatorics, Probability and Computing. 8 (1–2): 7–29\. doi:10.1017/S0963548398003411. MR 1684621. S2CID 209877602.1–2&rft.pages=7-29&rft.date=1999&rft_id=https://mathscinet.ams.org/mathscinet-getitem?mr=1684621#id-name=MR&rft_id=https://api.semanticscholar.org/CorpusID:209877602#id-name=S2CID&rft_id=info:doi/10.1017/S0963548398003411&rft.au=Alon,+Noga&rft_id=http://www.math.tau.ac.il/~nogaa/PDFS/null2.pdf&rfr_id=info:sid/en.wikipedia.org:Restricted+sumset" class="Z3988">
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.

* 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

[edit]

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