Restricted sumset

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={a1+⋯+an: a1∈A1,…,an∈An and P(a1,…,an)=0},

where A1,…,An are finite nonempty subsets of a field F and P(x1,…,xn) is a polynomial over F.

If P is a constant non-zero function, for example P(x1,…,xn)=1 for any x1,…,xn, then S is the usual sumset A1+⋯+An which is denoted by nA if A1=⋯=An=A.

When

P(x1,…,xn)=∏1≤i<j≤n(xj−xi),

S is written as A1∔⋯∔An which is denoted by n∧A if A1=⋯=An=A.

Note that |S| > 0 if and only if there exist a1∈A1,…,an∈An with P(a1,…,an)=0.

## Contents

* 1 Cauchy–Davenport theorem
* 2 Erdős–Heilbronn conjecture
* 3 Combinatorial Nullstellensatz
* 4 See also
* 5 References
* 6 External links

## 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 ℤ/pℤ we have the inequality[1][2][3]

|A+B|≥min⁡{p,|A|+|B|−1}

where A+B:={a+b(modp)∣a∈A,b∈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|≥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 ℤ/nℤ, 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 ℤ/pℤ, every element of ℤ/pℤ 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∧A|≥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|−n2+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 f(x1,…,xn) be a polynomial over a field F. Suppose that the coefficient of the monomial x1k1⋯xnkn in f(x1,…,xn) is nonzero and k1+⋯+kn is the total degree of f(x1,…,xn). If A1,…,An are finite subsets of F with |Ai|>ki for i=1,…,n, then there are a1∈A1,…,an∈An such that f(a1,…,an)=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,<ref name="Alon1996">{{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

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. http://math.colgate.edu/~integers/q7/q7.Abstract.html.
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. ↑ Cite error: Invalid `<ref>` tag; no text was provided for refs named `Alon1996`
12. ↑ "Restricted sums in a field". Acta Arithmetica 102 (3): 239–249. 2002. doi:10.4064/aa102-3-3. Bibcode: 2002AcAri.102..239H.
13. ↑ Károlyi, Gyula (2004). "The Erdős–Heilbronn problem in abelian groups". Israel Journal of Mathematics 139: 349–359. doi:10.1007/BF02787556.
14. ↑ 14.0 14.1 Alon, Noga (1999). "Combinatorial Nullstellensatz". Combinatorics, Probability and Computing 8 (1–2): 7–29. doi:10.1017/S0963548398003411. http://www.math.tau.ac.il/~nogaa/PDFS/null2.pdf.
15. ↑ Alon, Noga; Tarsi, Michael (1989). "A nowhere-zero point in linear mappings". Combinatorica 9 (4): 393–395. doi:10.1007/BF02125351.

* 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.
* Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics. 165. Springer-Verlag. ISBN 0-387-94655-1.

## External links

* Weisstein, Eric W.. "Erdős-Heilbronn Conjecture". http://mathworld.wolfram.com/Erdos-HeilbronnConjecture.html.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Restricted sumset. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Restricted_sumset&oldid=242390"