×

On the critical pair theory in abelian groups: beyond Chowla’s theorem. (English) Zbl 1192.11071

The Cauchy-Davenport theorem, concerning the addition of residue classes, was generalized to cyclic groups by S. Chowla [Proc. Indian Acad. Sci. 2, 242–243 (1935; Zbl 0012.24701 and JFM 61.0149.03)]. Chowla’s theorem states: Let \(S,T\) be non-empty subsets of \(\mathbb Z/n \mathbb Z\), let \(0 \in S\), and assume that every element of \(S \setminus \{0\}\) has exact order \(n\). Then the number \(| T+S| \) of elements in \(T+S\) is \( \; \geq \min (n, | S| + | T| - 1)\).
Critical pairs are subsets \(S_c,\, T_c\), for which equality occurs in the equation above, \( | T_c+S_c| = \min (n, | S_c| + | T_c| - 1)\). For example, Vosper’s theorem gives the critical pairs in the Cauchy-Davenport theorem. Hamidoune and Rødseth proved: Let \(S, T \subset \mathbb Z/ p\mathbb Z\), \(| T| \geq 3,\; | S| \geq 4\), and \(| S+T| = | S| + | T| \leq p-4\). Then \(S, T\) are included in arithmetic progressions with the same difference and of lengths \(| S| +1\) and \(| T| +1\).
The authors’ main result generalizes this result to abelian groups, hereby improving on the theorems of Chowla and of Voster: Let \(0\in S\) be a generating subset of a finite abelian group \(G\), where \(\gcd(| G| ,6)=1\) and \(4 \leq | S| \leq | G| -7\). Assume that \(S\) is 3–separable (that means that there exists an \(X \subset G\) such that \(| X| \geq 3\) and \(| X+S| \leq | G| - 3\)), and that \[ \kappa_3(S) \overset\text{def} =\min\Bigl\{ | X+S| -| X| ;\, X \subset G, \, | X| \geq 3, \text{ and } | X+S| \leq | G| - k\Bigr\} = | S| . \] If every element of \(S\setminus \{0\}\) has order \(\geq | S| +1\), then either \(S\) is a quasi-progression or \(S \setminus \{0\}\) is quasi-periodic.
Here, a quasi-periodic set is one which can be obtained by deleting one element from a periodic set; \(S\) is a periodic set if there is some non-trivial subgroup \(H\) such that \(S+H=S\). A quasi-progression can be obtained by deleting one element of an arithmetic progression.
A second main-theorem describes the critical pairs for a finite abelian group \(G\) with \(\gcd(| G| ,6) = 1\), a generating subset \(S\), where \(0\in S\) and \(| S| \geq 4\), and where every element in \(S^\ast\) has order \(\geq | S| +1\), and for a subset \(T \subset G\), where \(| T| \geq 3\), satisfying \[ | S+T| = | S| + | T| \qquad \Bigl[ \leq | G| - 4 \Bigr]. \] For the proofs a thorough study of “\(k\)-atoms” and of a so-called “fainting technique” is necessary.

MSC:

11P70 Inverse problems of additive number theory, including sumsets
11B75 Other combinatorial number theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] N. Alon, M. B. Nathanson and I. Z. Ruzsa: The polynomial method and restricted sums of congruence classes, J. Number Theory 56 (1996), 404–417. · Zbl 0861.11006 · doi:10.1006/jnth.1996.0029
[2] A. L. Cauchy: Recherches sur les nombres, J. Ecole Polytechnique 9 (1813), 99–116.
[3] S. Chowla: A theorem on the addition of residue classes: applications to the number {\(\Gamma\)}(k) in Waring’s problem, Proc. Indian Acad. Sci. 2 (1935), 242–243. · Zbl 0012.24701
[4] H. Davenport: On the addition of residue classes, J. London Math. Soc. 10 (1935), 30–32. · Zbl 0010.38905 · doi:10.1112/jlms/s1-10.37.30
[5] J.-M. Deshouillers and G. A. Freiman: A step beyond Kneser’s Theorem for abelian finite groups, Proc. London Math. Soc. (3) 86(1) (2003), 1–28. · Zbl 1032.11009 · doi:10.1112/S0024611502013709
[6] B. Green and I. Z. Ruzsa: Sets with small sumset and rectification, Bull. London Math. Soc. 38 (2006), 43–52. · Zbl 1155.11307 · doi:10.1112/S0024609305018102
[7] Y. O. Hamidoune: On the connectivity of Cayley digraphs, Europ. J. Combinatorics 5 (1984), 309–312. · Zbl 0561.05028
[8] Y. O. Hamidoune: An isoperimetric method in Additive Theory, J. Algebra 179 (1996), 622–630. · Zbl 0842.20029 · doi:10.1006/jabr.1996.0028
[9] Y. O. Hamidoune: Some results in additive number theory I: The critical pair theory, Acta Arithmetica 96 (2000), 97–119. · Zbl 0985.11011 · doi:10.4064/aa96-2-1
[10] Y. O. Hamidoune and Ø. J. Røseth: An inverse theorem modulo p, Acta Arithmetica 92 (2000), 251–262. · Zbl 0945.11003
[11] Y. O. Hamidoune, A. S. Lladó and O. Serra: On subsets with a small product in torsion-free groups, Combinatorica 18(4) (1998), 529–540. · Zbl 0930.20034 · doi:10.1007/s004930050038
[12] Y. O. Hamidoune: On small subset product in a group. Structure Theory of setaddition; Astérisque no. 258(xiv–xv) (1999), 281–308.
[13] Y. O. Hamidoune and A. Plagne: A new critical pair theorem applied to sum-free sets in abelian groups, Commentarii Mathematici Helvetici 79(1) (2004), 183–207. · Zbl 1045.11072 · doi:10.1007/s00014-003-0786-5
[14] Y. O. Hamidoune, O. Serra and G. Zémor: On the critical pair theory in \(\mathbb{Z}\)/p\(\mathbb{Z}\), Acta Arithmetica 121 (2006), 99–115. · Zbl 1147.11060 · doi:10.4064/aa121-2-1
[15] G. A. Freiman: Foundations of a structural theory of set addition, Transl. Math. Monographs 37, Amer. Math. Soc., Providence, RI, 1973.
[16] Gy. Károlyi: An inverse theorem for the restricted set addition in abelian groups, J. Algebra 290 (2005), 557–593. · Zbl 1095.11046 · doi:10.1016/j.jalgebra.2005.04.021
[17] Gy. Károlyi: Cauchy-Davenport theorem in group extensions, Enseign. Math. (2) 51(3–4) (2005), 239–254. · Zbl 1111.20026
[18] J. H. B. Kemperman: On small sumsets in an abelian group, Acta Math. 103 (1960), 63–88. · Zbl 0108.25704 · doi:10.1007/BF02546525
[19] M. Kneser: Summenmengen in lokalkompakten abelschen Gruppen, Math. Zeit. 66 (1956), 88–110. · Zbl 0073.01702 · doi:10.1007/BF01186598
[20] H. B. Mann: An addition theorem of abelian groups for sets of elements, Proc. Amer. Math. Soc. 4 (1953), 423. · Zbl 0050.25703
[21] M. B. Nathanson: Additive Number Theory; Inverse problems and the geometry of sumsets, Grad. Texts in Math. 165, Springer, 1996. · Zbl 0859.11003
[22] O. Serra and G. Zémor: On a generalization of a theorem by Vosper, Integers Electr. J. Comb. Num. Th. 0(200), A10 (electronic). http://www.integersejcnt.org/vol0.html
[23] T. Tao and V. H. Vu: Additive Combinatorics, Cambridge Studies in Advanced Mathematics 105 (2006), Cambridge University Press.
[24] G. Vosper: The critical pairs of subsets of a group of prime order, J. London Math. Soc. 31 (1956), 200–205. · Zbl 0072.03402 · doi:10.1112/jlms/s1-31.2.200
[25] G. Zémor: A generalization to noncommutative groups of a theorem of Mann, Discrete Math. 126(1–3) (1994), 365–372. · Zbl 0791.05055 · doi:10.1016/0012-365X(94)90279-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.