The structure theory of set addition revisited

Sanders, Tom

doi:10.1090/S0273-0979-2012-01392-7

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-9485(online) ISSN 0273-0979(print)

The structure theory of set addition revisited

Author: Tom Sanders
Journal: Bull. Amer. Math. Soc. 50 (2013), 93-127
MSC (2010): Primary 11B13
Posted: October 2, 2012
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this article we survey some of the recent developments in the structure theory of set addition.

[Bil99] Yuri Bilu, Structure of sets with small sumset, Astérisque 258 (1999), xi, 77–108 (English, with English and French summaries). Structure theory of set addition. MR 1701189 (2000h:11109)
[Bog39] N. Bogolioùboff, Sur quelques propriétés arithmétiques des presque-périodes, Ann. Chaire Phys. Math. Kiev 4 (1939), 185–205 (Ukrainian, French). MR 0020164 (8,512b)
[Bou99] J. Bourgain, On triples in arithmetic progression, Geom. Funct. Anal. 9 (1999), no. 5, 968–984. MR 1726234 (2001h:11132), http://dx.doi.org/10.1007/s000390050105
[Bou08] Jean Bourgain, Roth’s theorem on progressions revisited, J. Anal. Math. 104 (2008), 155–192. MR 2403433 (2009g:11011), http://dx.doi.org/10.1007/s11854-008-0020-x
[BS94] Antal Balog and Endre Szemerédi, A statistical theorem of set addition, Combinatorica 14 (1994), no. 3, 263–268. MR 1305895 (95m:11019), http://dx.doi.org/10.1007/BF01212974
[Cha02] Mei-Chu Chang, A polynomial bound in Freiman’s theorem, Duke Math. J. 113 (2002), no. 3, 399–419. MR 1909605 (2003d:11151), http://dx.doi.org/10.1215/S0012-7094-02-11331-3
[Cha04] Mei-Chu Chang, On problems of Erdös and Rudin, J. Funct. Anal. 207 (2004), no. 2, 444–460. MR 2032997 (2004j:11022), http://dx.doi.org/10.1016/S0022-1236(03)00073-9
[Cha09] Mei-Chu Chang, Some consequences of the polynomial Freiman-Ruzsa conjecture, C. R. Math. Acad. Sci. Paris 347 (2009), no. 11-12, 583–588 (English, with English and French summaries). MR 2532910 (2010e:11005), http://dx.doi.org/10.1016/j.crma.2009.04.006
[CŁS11] E. S. Croot, I. Łaba, and O. Sisask.
Arithmetic progressions in sumsets and ${L}^p$ -almost-periodicity.
2011, arXiv:1103.6000.
[CS10] Ernie Croot and Olof Sisask, A probabilistic technique for finding almost-periods of convolutions, Geom. Funct. Anal. 20 (2010), no. 6, 1367–1396. MR 2738997 (2012d:11019), http://dx.doi.org/10.1007/s00039-010-0101-8
[DHP04] Jean-Marc Deshouillers, François Hennecart, and Alain Plagne, On small sumsets in (ℤ/2ℤ)ⁿ, Combinatorica 24 (2004), no. 1, 53–68. MR 2057683 (2005f:11231), http://dx.doi.org/10.1007/s00493-004-0004-0
[FHR92] G. A. Freiman, H. Halberstam, and I. Z. Ruzsa, Integer sum sets containing long arithmetic progressions, J. London Math. Soc. (2) 46 (1992), no. 2, 193–201. MR 1182477 (93j:11008), http://dx.doi.org/10.1112/jlms/s2-46.2.193
[Fre66] G. A. Freiman, Nachala strukturnoi teorii slozheniya mnozhestv, Kazan. Gosudarstv. Ped. Inst, 1966 (Russian). MR 0360495 (50 #12943)
[Fre73a] G. A. Freĭman.
Foundations of a structural theory of set addition.
American Mathematical Society, Providence, R. I., 1973.
Translated from the Russian, Translations of Mathematical Monographs, Vol 37.
[Fre73b] G. A. Freĭman.
Groups and the inverse problems of additive number theory.
In Number-theoretic studies in the Markov spectrum and in the structural theory of set addition (Russian), pages 175-183. Kalinin. Gos. Univ., Moscow, 1973.
[Gow98] W. T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, Geom. Funct. Anal. 8 (1998), no. 3, 529–551. MR 1631259 (2000d:11019), http://dx.doi.org/10.1007/s000390050065
[Gow01] W. T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), no. 3, 465–588. MR 1844079 (2002k:11014), http://dx.doi.org/10.1007/s00039-001-0332-9
[GR06] Ben Green and Imre Z. Ruzsa, Sets with small sumset and rectification, Bull. London Math. Soc. 38 (2006), no. 1, 43–52. MR 2201602 (2006i:11027), http://dx.doi.org/10.1112/S0024609305018102
[GR07] Ben Green and Imre Z. Ruzsa, Freiman’s theorem in an arbitrary abelian group, J. Lond. Math. Soc. (2) 75 (2007), no. 1, 163–175. MR 2302736 (2007m:20087), http://dx.doi.org/10.1112/jlms/jdl021
[Gre02] B. Green, Arithmetic progressions in sumsets, Geom. Funct. Anal. 12 (2002), no. 3, 584–597. MR 1924373 (2003i:11148), http://dx.doi.org/10.1007/s00039-002-8258-4
[GS08] Ben Green and Tom Sanders, A quantitative version of the idempotent theorem in harmonic analysis, Ann. of Math. (2) 168 (2008), no. 3, 1025–1054. MR 2456890 (2010c:11013), http://dx.doi.org/10.4007/annals.2008.168.1025
[GT06] B. Green and T. Tao, Compressions, convex geometry and the Freiman-Bilu theorem, Q. J. Math. 57 (2006), no. 4, 495–504. MR 2277597 (2007g:11013), http://dx.doi.org/10.1093/qmath/hal009
[GT08] Ben Green and Terence Tao, An inverse theorem for the Gowers 𝑈³(𝐺) norm, Proc. Edinb. Math. Soc. (2) 51 (2008), no. 1, 73–153. MR 2391635 (2009g:11012), http://dx.doi.org/10.1017/S0013091505000325
[GT09a] Ben Green and Terence Tao, Freiman’s theorem in finite fields via extremal set theory, Combin. Probab. Comput. 18 (2009), no. 3, 335–355. MR 2501431 (2010f:11176), http://dx.doi.org/10.1017/S0963548309009821
[GT09b] Ben Green and Terence Tao, A note on the Freiman and Balog-Szemerédi-Gowers theorems in finite fields, J. Aust. Math. Soc. 86 (2009), no. 1, 61–74. MR 2495998 (2010d:11015), http://dx.doi.org/10.1017/S1446788708000359
[GT10] Ben Green and Terence Tao, An equivalence between inverse sumset theorems and inverse conjectures for the 𝑈³ norm, Math. Proc. Cambridge Philos. Soc. 149 (2010), no. 1, 1–19. MR 2651575 (2011g:11019), http://dx.doi.org/10.1017/S0305004110000186
[JL01] William B. Johnson and Joram Lindenstrauss, Basic concepts in the geometry of Banach spaces, Handbook of the geometry of Banach spaces, Vol. I, North-Holland, Amsterdam, 2001, pp. 1–84. MR 1863689 (2003f:46013), http://dx.doi.org/10.1016/S1874-5849(01)80003-6
[KK10] Nets Hawk Katz and Paul Koester, On additive doubling and energy, SIAM J. Discrete Math. 24 (2010), no. 4, 1684–1693. MR 2746716 (2012d:11020), http://dx.doi.org/10.1137/080717286
[KŁ06] Sergei Konyagin and Izabella Łaba, Distance sets of well-distributed planar sets for polygonal norms, Israel J. Math. 152 (2006), 157–179. MR 2214458 (2006m:11032), http://dx.doi.org/10.1007/BF02771981
[Kne53] Martin Kneser, Abschätzung der asymptotischen Dichte von Summenmengen, Math. Z. 58 (1953), 459–484 (German). MR 0056632 (15,104c)
[Kon08] S. V. Konyagin, On Freiman’s theorem in finite fields, Mat. Zametki 84 (2008), no. 3, 472–474 (Russian); English transl., Mat. Zametki 84 (2008), no. 4, 435–438. MR 2473762 (2009i:11013)
[Lov10] S. Lovett.
Equivalence of polynomial conjectures in additive combinatorics.
2010, arXiv:1001.3356.
[LR75] Jorge M. López and Kenneth A. Ross, Sidon sets, Marcel Dekker Inc., New York, 1975. Lecture Notes in Pure and Applied Mathematics, Vol. 13. MR 0440298 (55 #13173)
[Pet11a] G. Petridis.
New proofs of Plünnecke-type estimates for product sets in groups.
2011, arXiv:1101.3507.
[Pet11b] Giorgis Petridis, Plünnecke’s inequality, Combin. Probab. Comput. 20 (2011), no. 6, 921–938. MR 2847275, http://dx.doi.org/10.1017/S096354831100037X
[Plü69] Helmut Plünnecke, Eigenschaften und Abschätzungen von Wirkungsfunktionen, BMwF-GMD-22, Gesellschaft für Mathematik und Datenverarbeitung, Bonn, 1969 (German). MR 0252348 (40 #5569)
[Rud60] Walter Rudin, Trigonometric series with gaps, J. Math. Mech. 9 (1960), 203–227. MR 0116177 (22 #6972)
[Rud90] Walter Rudin, Fourier analysis on groups, Wiley Classics Library, John Wiley & Sons Inc., New York, 1990. Reprint of the 1962 original; A Wiley-Interscience Publication. MR 1038803 (91b:43002)
[Ruz78] I. Z. Ruzsa, On the cardinality of 𝐴+𝐴 and 𝐴-𝐴, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam, 1978, pp. 933–938. MR 519317 (80c:05016)
[Ruz89] Imre Z. Ruzsa, An application of graph theory to additive number theory, Sci. Ser. A Math. Sci. (N.S.) 3 (1989), 97–109. MR 2314377
[Ruz94] I. Z. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar. 65 (1994), no. 4, 379–388. MR 1281447 (95k:11011), http://dx.doi.org/10.1007/BF01876039
[Ruz99] Imre Z. Ruzsa, An analog of Freiman’s theorem in groups, Astérisque 258 (1999), xv, 323–326 (English, with English and French summaries). Structure theory of set addition. MR 1701207 (2000h:11111)
[Sam07] Alex Samorodnitsky, Low-degree tests at large distances, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 506–515. MR 2402476 (2009f:68077), http://dx.doi.org/10.1145/1250790.1250864
[San10] T. Sanders.
On the Bogolyubov-Ruzsa lemma.
Anal. PDE, to appear, 2010, arXiv:1011.0107.
[Sch03] Tomasz Schoen, Multiple set addition in ℤ_{𝕡}, Integers 3 (2003), A17, 6. MR 2036483 (2004j:11012)
[Sch11] Tomasz Schoen, Near optimal bounds in Freiman’s theorem, Duke Math. J. 158 (2011), no. 1, 1–12. MR 2794366 (2012f:11018), http://dx.doi.org/10.1215/00127094-1276283
[SV06] E. Szemerédi and V. Vu, Long arithmetic progressions in sumsets: thresholds and bounds, J. Amer. Math. Soc. 19 (2006), no. 1, 119–169. MR 2169044 (2006j:11015), http://dx.doi.org/10.1090/S0894-0347-05-00502-3
[Sze69] E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hungar. 20 (1969), 89–104. MR 0245555 (39 #6861)
[Sze75] E. Szemerédi, On sets of integers containing no 𝑘 elements in arithmetic progression, Acta Arith. 27 (1975), 199–245. Collection of articles in memory of Juriĭ Vladimirovič Linnik. MR 0369312 (51 #5547)
[Tao08] Terence Tao, Product set estimates for non-commutative groups, Combinatorica 28 (2008), no. 5, 547–594. MR 2501249 (2010b:11017), http://dx.doi.org/10.1007/s00493-008-2271-7
[Tao10] Terence Tao, Freiman’s theorem for solvable groups, Contrib. Discrete Math. 5 (2010), no. 2, 137–184. MR 2791295 (2012e:05063)
[TV06] Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012 (2008a:11002)
[TV07] Terence Tao and Van Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007), no. 3, 603–628. MR 2291914 (2008h:60027), http://dx.doi.org/10.1090/S0894-0347-07-00555-3
[Wol09] J. Wolf.
A local inverse theorem in $\mathbb{F}_2^n$ .
Preprint, 2009.
[Zoh11] C. E. Zohar.
On sums of generating sets in $\mathbb{Z}_2^n$ .
2011, arXiv:1108.4902.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|