A polynomial bound in Freiman's theorem.
In the fifties, Freiman started to study the sets of integers with the small doubling property. His famous theorem states that, for \(\alpha\) a real number, the sets of integers \(A\) such that \(| A+ A|\leq\alpha| A|\) are ``structured'' in the sense that \(A\) has to be contained in a \(d\)-dimensional arithmetic progression, that is a set of the form \[ P= \Biggl\{p_0+ \sum^d_{i=1} x_i p_i\text{ where }0\leq x_i\leq d_i\Biggr\}, \] that \(A\) fulfills well (by which we mean \(| A|\geq c| P|\) for some \(c > 0\)). The point is that \(d\) and \(c\) are bounded by a function depending only on \(\alpha\). This theorem is included in \textit{G. A. Freiman's} famous book [Foundations of a structural theory of set addition (Russian), Kazan. Gos. Ped. Inst., Elabuzh. Gos. Ped. Inst., Kazan (1966; Zbl 0203.35305)] and its English translation [Translations of Mathematical Monographs, Vol. 37, AMS (1973; Zbl 0271.10044)]. There has been some progress (and new proofs) on Freiman's original result: see \textit{I. Z. Ruzsa} [Acta Math. Hung. 65, 379--388 (1994; Zbl 0816.11008)] and \textit{Y. Bilu} [Structure of sets with small sumset. Structure theory of set addition. Astérisque 258, 77--108 (1999; Zbl 0946.11004)]. In particular, effective estimates on the functions \(d(\alpha)\) and \(c(\alpha)\) were established. In the present paper, improved estimates are proved, namely \(d(\alpha)\leq [\alpha- 1]\) and \(c(\alpha)\geq\exp(-c_0 \alpha^2\log^3\alpha)\) (for some constant \(c_0\)). The bound on \(c(\alpha\)) is a drastic improvement since earlier bounds provided doubly exponential estimates. The proof of this important result combines the -- locally improved -- known proofs of Freiman's theorem (mainly that one of Ruzsa) and new harmonic analysis arguments.
scientific article; zbMATH DE number 1820912
scientific article