Misplaced Pages

Restricted sumset

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Cauchy–Davenport theorem) 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

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

| 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

| 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.)

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.

Kneser's theorem generalises this to general abelian groups.

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 } {\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. This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994 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, Q. H. Hou and Zhi-Wei Sun in 2002, and G. Karolyi in 2004.

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. 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})\not =0} .

This tool was rooted in a paper of N. Alon and M. Tarsi in 1989, and developed by Alon, Nathanson and Ruzsa in 1995–1996, and reformulated by Alon in 1999.

See also

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

Categories: