John-type theorems for generalized arithmetic progressions and iterated sumsets (Q944315)

A classical theorem of [\textit{F. John}, Extremum problems with inequalities as subsidiary conditions, Studies Essays, pres. to R. Courant, 187--204 (1948; Zbl 0034.10503)] states that for any symmetric convex body \(B\) in \(\mathbb{R}^d\), there exists an ellipsoid \(E\) centered at the origin such that \(E \subseteq B \subseteq \sqrt{d} \cdot E\). This rather technical yet elementary paper establishes various discrete analogues of John's theorem. It constitutes a valuable resource for anyone in need of precise quantitative statements about containment properties of generalized arithmetic progressions. The first fundamental result is a John-type theorem for lattices, a proof of which can also be found in [\textit{T. Tao} and \textit{V. Vu}, Additive Combinatorics. Cambridge Studies in Advanced Mathematics 105. Cambridge: Cambridge University Press (2006; Zbl 1127.11002)]. For the convenience of the reader we shall state it (and the remaining results of this paper) in a simplified form. Let \(B\) be a convex symmetric body and \(\Gamma\) be a lattice in \(\mathbb{R}^d\). Then there exists a symmetric infinitely proper generalized arithmetic progression (GAP) \(P\) of rank at most \(d\) in \(\Gamma\), with the property that \[ (O(d)^{-3d/2} \cdot B) \cap \Gamma \subseteq \text{Im}(P) \subseteq B \cap \Gamma \subseteq \text{Im}(P_{O(d)^{3d/2}}), \] where Im stands for the image of the GAP and \(P_t\) for the \(t\)-dilate of \(P\). A GAP is called \(t\)-proper if its dilate \(P_t\) is proper (that is, all its elements are distinct), and infinitely proper if it is \(t\)-proper for all \(t\). As a corollary the authors obtain in the torsion-free case a John-type theorem for GAPs, which states that given a symmetric GAP of rank \(d\) in a torsion-free group \(G\), there exists a \(t\)-proper symmetric GAP \(Q\) of rank at most \(d\) such that \[ \text{Im}(Q) \subseteq \text{Im}(P) \subseteq \text{Im}(Q_{O(d)^{3d/2}t}). \] Essentially the same result is obtained in the torsion case with GAPs replaced by so-called coset progressions, a concept that originated in the work of [\textit{B. J. Green} and \textit{I. Ruzsa}, J. Lond. Math. Soc. 75, No. 1, 163--175 (2007; Zbl 1133.11058)]. The above proof techniques are then combined with Freiman-type results by Green and Ruzsa to strengthen a recent result by \textit{E. Szemerédi} and \textit{V. Vu} [J. Am. Math. Soc. 19, No. 1, 119--169 (2006; Zbl 1088.11012)], which can be interpreted as a John-type theorem for iterated sumsets: Let \(A \subseteq G\) be a finite subset such that \(|lA| \leq c(d) l^d|A|\) for some explicitly specified constant \(c(d)\) depending on \(d\). Then there exists a proper symmetric coset progression \(Q\) of rank \(d'\leq d-1\) and size at least \(c(d)l^{d'}|A|\) together with \(x,y \in G\) such that \[ x+\text{Im}(Q) \subseteq lA \subseteq y+c(d)^{-1} \text{Im}(Q). \]