Small doubling in cyclic groups (Q2109417)

An important problem in additive combinatorics is to understand the structure of small-doubling sets, which are sets \(A\) of a group elements such that \(2A := \{a+b: a,b \in A\}\) has size comparable with the size of \(A\). The main result of the paper is the following: Theorem 1.1. Let \(n\) be a positive integer. If a set \(A \subset \mathbb Z_n\) satisfies \(|2A| < \frac 94 |A|\), then one of the following holds: \begin{itemize} \item[(i)] There is a subgroup \(H \le \mathbb Z_n\) such that \(A\) is contained in an \(H\)-coset and \(|A| > \frac{|H|}{2 \cdot 10^5}\). \item[(ii)] There is a proper subgroup \(H < \mathbb Z_n\) and an arithmetic progression \(P\) of size \(|P| > 1\) such that \(|P+H| = |P||H|\), \(A \subseteq P+H\), and \((|P| - 1)|H| \le |2A| - |A|\). \item[(iii)] There is a proper subgroup \(H < \mathbb Z_n\) such that \(A\) meets exactly three \(H\)-cosets, the cosets are not in an arithmetic progression, and \(3|H| \le |2A| - |A|\). \end{itemize} This theorem improves a result by \textit{J.-M. Deshouillers} and \textit{G. A. Freiman} [Proc. Lond. Math. Soc. (3) 86, No. 1, 1--28 (2003; Zbl 1032.11009)]. The properness of \(H\) in (ii) and (iii) follows from \(|H| \le |2A| - |A| < |2A|\). Similarly, if the equality \(|H+P| = |P||H|\) does not hold, then \(P+H\) is a coset of a subgroup of size at most \((|P|-1)|H| \le |2A| - |A| < \frac 54 |A|\), therefore \(|P+H| = |P||H|\) can be enforced by reclassifying \(A\) from type (ii) to type (i) whenever possible. Furthermore, the coefficient \(9/4\) in Theorem 1.1 is optimal, in the sense that the assumption of (i) cannot be relaxed even to \(|2A| \le \frac 94 |A|\). In fact, if \(n\) is large enough and \(A = \{-1,0,1\} \cup \{a\}\) with \(a \not\in \{-3,\dots,3\}\) and \(2a \not\in \{-2,\dots,2\}\), then \(|2A| = \frac 94 |A|\) while \(A\) does not have the desired structure. However, it is expected the following. Conjecture 1.4. For any \(\varepsilon > 0\) there exist positive constants \(C_1(\varepsilon)\) and \(C_2(\varepsilon)\) such that if \(n\) is a positive integer, and \(A \subseteq \mathbb Z_n\) satisfies \(|A| < \frac{n}{C_1(\varepsilon)}\) and \(|2A| < (3 - \varepsilon)|A|\), then there are a subset \(P \subseteq \mathbb Z_n\) with \(|2P|/|P| \le |2A|/|A|\) and a proper subgroup \(H < \mathbb Z_n\) such that \(A \subseteq P+H\), \((|2P| - |P|)|H| \le |2A| - |A|\), and either \(|P| \le C_2(\varepsilon)\), or \(P\) is an arithmetic progression. We notice that \(|2P|/|P| \le |2A|/|A|\) follows from the other assertions: \[ |A| \left( \frac{|2P|}{|P|} - 1 \right) \le |P||H| \left( \frac{|2P|}{|P|} - 1 \right) = (|2P| - |P|)|H| \le |2A| - |A| = |A| \left( \frac{|2A|}{|A|} - 1 \right). \] Theorem 1.1 and Conjecture 1.4 show that any set with the small doubling coefficient is, essentially, obtained by ``lifting'' a small-doubling set which is either nicely structured (an arithmetic progression), or otherwise belongs to a finite collection of sporadic examples. Two other classical results which Theorem 1.1 is worth comparing with are Kneser's theorem (that deals with small-doubling sets in arbitrary abelian groups, but requires the doubling coefficient \(|2A|/|A|\) to be smaller than \(2\), see [\textit{M. Kneser}, Math. Z. 58, 459--484 (1953; Zbl 0051.28104); Math. Z. 61, 429--434 (1955; Zbl 0064.04305); \textit{H. B. Mann}, Addition theorems: the addition theorems of group theory and number theory. New York, NY: Interscience Publishers (1965; Zbl 0127.27203)]), and Freiman's \((3n-3)\)-theorem (that allows the doubling coefficient to be as large as \(3-o(1)\), but assumes the underlying group to be torsion-free, see [\textit{G. A. Freĭman}, Sov. Math., Dokl. 2, 1520--1522 (1961; Zbl 0109.27203); translation from Dokl. Akad. Nauk SSSR 141, 571--573 (1961)] and [\textit{D. J. Grynkiewicz}, Structural additive theory. Based on courses given at Karl-Franzens-Universität Graz, Austria, 2008--2012. Cham: Springer (2013; Zbl 1368.11109), Chapter 7]). The proof of Theorem 1.1 is inductive and uses both Kneser's and Freiman's theorems, as well as character sums and combinatorics.