The structure theory of set addition revisited

Sanders, Tom

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

The structure theory of set addition revisited
HTML articles powered by AMS MathViewer

by Tom Sanders PDF

Bull. Amer. Math. Soc. 50 (2013), 93-127 Request permission

Abstract:

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

References

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
N. Bogolioùboff, Sur quelques propriétés arithmétiques des presque-périodes, Ann. Chaire Phys. Math. Kiev 4 (1939), 185–205 (Ukrainian, with French summary). MR 20164
J. Bourgain, On triples in arithmetic progression, Geom. Funct. Anal. 9 (1999), no. 5, 968–984. MR 1726234, DOI 10.1007/s000390050105
Jean Bourgain, Roth’s theorem on progressions revisited, J. Anal. Math. 104 (2008), 155–192. MR 2403433, DOI 10.1007/s11854-008-0020-x
Antal Balog and Endre Szemerédi, A statistical theorem of set addition, Combinatorica 14 (1994), no. 3, 263–268. MR 1305895, DOI 10.1007/BF01212974
Mei-Chu Chang, A polynomial bound in Freiman’s theorem, Duke Math. J. 113 (2002), no. 3, 399–419. MR 1909605, DOI 10.1215/S0012-7094-02-11331-3
Mei-Chu Chang, On problems of Erdös and Rudin, J. Funct. Anal. 207 (2004), no. 2, 444–460. MR 2032997, DOI 10.1016/S0022-1236(03)00073-9
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, DOI 10.1016/j.crma.2009.04.006
E. S. Croot, I. Łaba, and O. Sisask. Arithmetic progressions in sumsets and ${L}^p$-almost-periodicity. 2011, arXiv:1103.6000.
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, DOI 10.1007/s00039-010-0101-8
Jean-Marc Deshouillers, François Hennecart, and Alain Plagne, On small sumsets in $(\Bbb Z/2\Bbb Z)^n$, Combinatorica 24 (2004), no. 1, 53–68. MR 2057683, DOI 10.1007/s00493-004-0004-0
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, DOI 10.1112/jlms/s2-46.2.193
G. A. Freĭman, Nachala strukturnoĭ teorii slozheniya mnozhestv, Kazan. Gosudarstv. Ped. Inst.; Elabuž. Gosudarstv. Ped. Inst., Kazan, 1966 (Russian). MR 0360495
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.
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.
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, DOI 10.1007/s000390050065
W. T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), no. 3, 465–588. MR 1844079, DOI 10.1007/s00039-001-0332-9
Ben Green and Imre Z. Ruzsa, Sets with small sumset and rectification, Bull. London Math. Soc. 38 (2006), no. 1, 43–52. MR 2201602, DOI 10.1112/S0024609305018102
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, DOI 10.1112/jlms/jdl021
B. Green, Arithmetic progressions in sumsets, Geom. Funct. Anal. 12 (2002), no. 3, 584–597. MR 1924373, DOI 10.1007/s00039-002-8258-4
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, DOI 10.4007/annals.2008.168.1025
B. Green and T. Tao, Compressions, convex geometry and the Freiman-Bilu theorem, Q. J. Math. 57 (2006), no. 4, 495–504. MR 2277597, DOI 10.1093/qmath/hal009
Ben Green and Terence Tao, An inverse theorem for the Gowers $U^3(G)$ norm, Proc. Edinb. Math. Soc. (2) 51 (2008), no. 1, 73–153. MR 2391635, DOI 10.1017/S0013091505000325
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, DOI 10.1017/S0963548309009821
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, DOI 10.1017/S1446788708000359
Ben Green and Terence Tao, An equivalence between inverse sumset theorems and inverse conjectures for the $U^3$ norm, Math. Proc. Cambridge Philos. Soc. 149 (2010), no. 1, 1–19. MR 2651575, DOI 10.1017/S0305004110000186
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, DOI 10.1016/S1874-5849(01)80003-6
Nets Hawk Katz and Paul Koester, On additive doubling and energy, SIAM J. Discrete Math. 24 (2010), no. 4, 1684–1693. MR 2746716, DOI 10.1137/080717286
Sergei Konyagin and Izabella Łaba, Distance sets of well-distributed planar sets for polygonal norms, Israel J. Math. 152 (2006), 157–179. MR 2214458, DOI 10.1007/BF02771981
Martin Kneser, Abschätzung der asymptotischen Dichte von Summenmengen, Math. Z. 58 (1953), 459–484 (German). MR 56632, DOI 10.1007/BF01174162
S. V. Konyagin, On Freiman’s theorem in finite fields, Mat. Zametki 84 (2008), no. 3, 472–474 (Russian); English transl., Math. Notes 84 (2008), no. 3-4, 435–438. MR 2473762, DOI 10.1134/S0001434608090137
S. Lovett. Equivalence of polynomial conjectures in additive combinatorics. 2010, arXiv:1001.3356.
Jorge M. López and Kenneth A. Ross, Sidon sets, Lecture Notes in Pure and Applied Mathematics, Vol. 13, Marcel Dekker, Inc., New York, 1975. MR 0440298
G. Petridis. New proofs of Plünnecke-type estimates for product sets in groups. 2011, arXiv:1101.3507.
Giorgis Petridis, Plünnecke’s inequality, Combin. Probab. Comput. 20 (2011), no. 6, 921–938. MR 2847275, DOI 10.1017/S096354831100037X
Helmut Plünnecke, Eigenschaften und Abschätzungen von Wirkungsfunktionen, Gesellschaft für Mathematik und Datenverarbeitung, Bonn, 1969 (German). BMwF-GMD-22. MR 0252348
Walter Rudin, Trigonometric series with gaps, J. Math. Mech. 9 (1960), 203–227. MR 0116177, DOI 10.1512/iumj.1960.9.59013
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, DOI 10.1002/9781118165621
I. Z. Ruzsa, On the cardinality of $A+A$ and $A-A$, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 933–938. MR 519317
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
I. Z. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar. 65 (1994), no. 4, 379–388. MR 1281447, DOI 10.1007/BF01876039
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
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, DOI 10.1145/1250790.1250864
T. Sanders. On the Bogolyubov-Ruzsa lemma. Anal. PDE, to appear, 2010, arXiv:1011.0107.
Tomasz Schoen, Multiple set addition in $\Bbb Z_p$, Integers 3 (2003), A17, 6. MR 2036483
Tomasz Schoen, Near optimal bounds in Freiman’s theorem, Duke Math. J. 158 (2011), no. 1, 1–12. MR 2794366, DOI 10.1215/00127094-1276283
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, DOI 10.1090/S0894-0347-05-00502-3
E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hungar. 20 (1969), 89–104. MR 245555, DOI 10.1007/BF01894569
E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199–245. MR 369312, DOI 10.4064/aa-27-1-199-245
Terence Tao, Product set estimates for non-commutative groups, Combinatorica 28 (2008), no. 5, 547–594. MR 2501249, DOI 10.1007/s00493-008-2271-7
Terence Tao, Freiman’s theorem for solvable groups, Contrib. Discrete Math. 5 (2010), no. 2, 137–184. MR 2791295
Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012, DOI 10.1017/CBO9780511755149
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, DOI 10.1090/S0894-0347-07-00555-3
J. Wolf. A local inverse theorem in $\mathbb {F}_2^n$. Preprint, 2009.
C. E. Zohar. On sums of generating sets in $\mathbb {Z}_2^n$. 2011, arXiv:1108.4902.