×

zbMATH — the first resource for mathematics

A polynomial bound in Freiman’s theorem. (English) Zbl 1035.11048
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 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 I. Z. Ruzsa [Acta Math. Hung. 65, 379–388 (1994; Zbl 0816.11008)] and 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.

MSC:
11P70 Inverse problems of additive number theory, including sumsets
11B13 Additive bases, including sumsets
11B25 Arithmetic progressions
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] V. Bergelson and A. Liebman, Polynomial extensions of van der Waerden’s and Szemerédi’s theorem , J. Amer. Math. Soc. 9 (1996), 725–753. JSTOR: · Zbl 0870.11015 · doi:10.1090/S0894-0347-96-00194-4 · links.jstor.org
[2] Y. Bilu, “Structure of sets with small sumset” in Structure Theory of Set Addition , Astérisque 258 , Soc. Math. France, Montrouge, 1999, 77–108. · Zbl 0946.11004
[3] N. N. Bogolioùboff [Bogolyubov], Sur quelques propriétés arithmétiques des presque-periodes , Ann. Chaire Phys. Math. Kiev 4 (1939), 185–205. · JFM 65.0268.01
[4] M. Chaimovich, “New structural approach to integer programming: A survey” in Structure Theory of Set Addition , Astérisque 258 , Soc. Math. France, Montrouge, 1999, 341–362. · Zbl 0987.90060
[5] M.-C. Chang, Inequidimensionality of Hilbert schemes , Proc. Amer. Math. Soc. 125 (1997), 2521–2526. JSTOR: · Zbl 0883.14001 · doi:10.1090/S0002-9939-97-03836-7 · links.jstor.org
[6] G. Cohen and G. Zémor, “Subset sums and coding theory” in Structure Theory of Set Addition , Astérisque 258 , Soc. Math. France, Montrouge, 1999, 327–339. · Zbl 1044.94016
[7] G. Elekes, On the number of sums and products , Acta Arith. 81 (1997), 365–367. · Zbl 0887.11012 · eudml:207071
[8] P. Erdős and E. Szemerédi, “On sums and products of integers” in Studies in Pure Mathematics , Birkhäuser, Basel, 1983, 213–218. · Zbl 0526.10011
[9] K. Falconer, The Geometry of Fractal Sets , Cambridge Tracts in Math. 85 , Cambridge Univ. Press, Cambridge, 1986.
[10] G. Freiman, Foundations of a Structural Theory of Set Addition , Trans. Math. Monogr. 37 , Amer. Math. Soc., Providence, 1973. · Zbl 0271.10044
[11] G. Freiman, H. Halberstam, and I. Ruzsa, Integer sum sets containing long arithmetic progressions , J. London Math. Soc. (2) 46 (1992), 193–201. · Zbl 0768.11005 · doi:10.1112/jlms/s2-46.2.193
[12] H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions , J. Anal. Math. 31 (1977), 204–256. · Zbl 0347.28016 · doi:10.1007/BF02813304
[13] H. Furstenberg, Y. Katznelson, and D. Ornstein, The ergodic theoretical proof of Szemerédi’s theorem , Bull. Amer. Math. Soc. (N.S.) 7 (1982), 527–552. · Zbl 0523.28017 · doi:10.1090/S0273-0979-1982-15052-2
[14] W. T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four , Geom. Funct. Anal. 8 (1998), 529–551. · Zbl 0907.11005 · doi:10.1007/s000390050065
[15] –. –. –. –., A new proof of Szemerédi’s theorem , Geom. Funct. Anal. 11 (2001), 465–588. \CMP1 844 079 · Zbl 1028.11005 · doi:10.1007/s00039-001-0332-9
[16] M. Herzog, “New results on subset multiplication in groups” in Structure Theory of Set Addition , Astérisque 258 , Soc. Math. France, Montrouge, 1999, 309–315. · Zbl 0944.20019
[17] N. Katz, I. Laba, and T. Tao, An improved bound on the Minkowski dimension of Besicovitch sets in \(R^3\) , Ann. of Math. (2) 152 (2000), 383–446. \CMP1 804 528 JSTOR: · Zbl 0980.42014 · doi:10.2307/2661389 · www.math.princeton.edu · eudml:121609
[18] N. Katz and T. Tao, Some connections between Falconer’s distance set conjecture and sets of Furstenburg type , New York J. Math. 7 (2001), 149–187. \CMP1 856 956 · Zbl 0991.28006 · emis:journals/NYJM/j/2001/7-10nf.htm · eudml:121950
[19] J. Lopez and K. Ross, Sidon Sets , Lecture Notes in Pure and Appl. Math. 13 , Dekker, New York, 1975.
[20] M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets , Springer, New York, 1996. · Zbl 0859.11003
[21] M. Nathanson and G. Tenenbaum, “Inverse theorems and the number of sums and products” in Structure Theory of Set Addition , Astérisque 258 , Soc. Math. France, Montrouge, 1999, 195–204. · Zbl 0947.11008
[22] K. Roth, On certain sets of integers , J. London Math. Soc 28 (1953), 104–109. · Zbl 0050.04002 · doi:10.1112/jlms/s1-28.1.104
[23] W. Rudin, Trigonometric series with gaps , J. Math. Mech. 9 (1960), 203–227. · Zbl 0091.05802
[24] I. Ruzsa, Arithmetic progressions in sumsets , Acta Arith. 60 (1991), 191–202. · Zbl 0728.11009 · eudml:206433
[25] –. –. –. –., Generalized arithmetic progressions and sumsets , Acta Math. Hungar. 65 (1994), 379–388. · Zbl 0816.11008 · doi:10.1007/BF01876039
[26] –. –. –. –., “An analog of Freiman’s theorem in groups” in Structure Theory of Set Addition , Astérisque 258 , Soc. Math. France, Montrouge, 1999, 323–326. · Zbl 0946.11007
[27] S. Shelah, Primitive recursive bounds for van der Waerden numbers , J. Amer. Math. Soc. 1 (1988), 683–697. JSTOR: · Zbl 0649.05010 · doi:10.2307/1990952 · links.jstor.org
[28] E. Szemerédi, On sets of integers containing no \(k\) elements in arithmetic progression , Acta Arith. 27 (1975), 199–245. · Zbl 0303.10056 · matwbn.icm.edu.pl · eudml:205339
[29] E. Szemerédi and W. Trotter, Extremal problems in discrete geometry , Combinatorica 3 (1983), 381–392. · Zbl 0541.05012 · doi:10.1007/BF02579194
[30] T. Tao, From rotating needles to stability of waves: Emerging connections between combinatorics, analysis, and PDE , Notices Amer. Math. Soc. 48 (2001), 294–303. · Zbl 0992.42002
[31] B. L. van der Waerden, Beweis einer Baudetsche Vermutung , Nieuw Arch. Wisk. 15 (1927), 212–216. · JFM 53.0073.12
[32] T. Wolff, “Recent work connected with the Kakeya problem” in Prospects in Mathematics (Princeton, 1996) , Amer. Math. Soc., Providence, 1999, 129–162. · Zbl 0934.42014
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.