Generalizations of Fourier analysis, and how to apply them
HTML articles powered by AMS MathViewer
- by W. T. Gowers PDF
- Bull. Amer. Math. Soc. 54 (2017), 1-44 Request permission
Abstract:
This is a survey of the use of Fourier analysis in additive combinatorics, with a particular focus on situations where it cannot be straightforwardly applied but needs to be generalized first. Sometimes very satisfactory generalizations exist, while sometimes we have to make do with theories that have some of the desirable properties of Fourier analysis but not all of them. In the latter case, there are intriguing hints that there may be more satisfactory theories yet to be discovered. This article grew out of the Colloquium Lectures at the Joint Meeting of the AMS and the MAA, given in Seattle in January 2016.References
- László Babai, Nikolay Nikolov, and László Pyber, Product growth and mixing in finite groups, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2008, pp. 248–257. MR 2485310
- László Babai and Vera T. Sós, Sidon sets in groups and induced subgraphs of Cayley graphs, European J. Combin. 6 (1985), no. 2, 101–114. MR 810691, DOI 10.1016/S0195-6698(85)80001-9
- 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
- Vitaly Bergelson, Bernard Host, and Bryna Kra, Multiple recurrence and nilsequences, Invent. Math. 160 (2005), no. 2, 261–303. With an appendix by Imre Ruzsa. MR 2138068, DOI 10.1007/s00222-004-0428-6
- T. F. Bloom, A quantitative improvement for Roth’s theorem on arithmetic progressions, J. Lond. Math. Soc. (2) 93 (2016), no. 3, 643–663. MR 3509957, DOI 10.1112/jlms/jdw010
- 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
- O. A. Camarena and B Szegedy, Nilspaces, nilmanifolds and their morphisms, http://arxiv.org/abs/1009.3825 [math.DS], 2012.
- P. Candela, Notes on compact nilspaces, http://arxiv.org/abs/1605.08940 [math.DS], 2016.
- P Candela, Notes on nilspaces: algebraic aspects, http://arxiv.org/abs/1601.03693 [math.DS], 2016.
- F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), no. 4, 345–362. MR 1054011, DOI 10.1007/BF02125347
- Ernie Croot, Vsevolod Lev, and Peter Pach, Progression-free sets in ${Z}_4^n$ are exponentially small, Submitted. http://arxiv.org/abs/1605.01506 [math.NT].
- Jordan S. Ellenberg and Dion Gijswijt, On large subsets of $\mathbb {F}_q^n$ with no three-term arithmetic progression, Submitted. http://arxiv.org/abs/1605.09223 [math.CO].
- Jacob Fox, A new proof of the graph removal lemma, Ann. of Math. (2) 174 (2011), no. 1, 561–579. MR 2811609, DOI 10.4007/annals.2011.174.1.17
- Jacob Fox and László Miklós Lovász, A tight bound for Green’s arithmetic triangle removal lemma in vector spaces, http://arxiv.org/abs/1606.01230 [math.CO].
- G. A. Freiman, Structure theory of set addition, Proc. Conf. Structure Theory of Set Addition, June 1993, pp. 299–318.
- 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
- W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math. (2) 166 (2007), no. 3, 897–946. MR 2373376, DOI 10.4007/annals.2007.166.897
- W. T. Gowers, Quasirandom groups, Combin. Probab. Comput. 17 (2008), no. 3, 363–387. MR 2410393, DOI 10.1017/S0963548307008826
- W. T. Gowers, Decompositions, approximate structure, transference, and the Hahn-Banach theorem, Bull. Lond. Math. Soc. 42 (2010), no. 4, 573–606. MR 2669681, DOI 10.1112/blms/bdq018
- W. T. Gowers and O. Hatami, Inverse and stability theorems for approximate representations of finite groups, https://arxiv.org/abs/1510.04085 arXiv:1510.04085 [math.GR].
- W. T. Gowers and J. Wolf, Linear forms and quadratic uniformity for functions on $\Bbb Z_N$, J. Anal. Math. 115 (2011), 121–186. MR 2855036, DOI 10.1007/s11854-011-0026-7
- W. T. Gowers and J. Wolf, Linear forms and quadratic uniformity for functions on $\Bbb F^n_p$, Mathematika 57 (2011), no. 2, 215–237. MR 2825234, DOI 10.1112/S0025579311001264
- Ben Green, Finite field models in additive combinatorics, Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge Univ. Press, Cambridge, 2005, pp. 1–27. MR 2187732, DOI 10.1017/CBO9780511734885.002
- Ben J. Green, Sárközy’s theorem in function fields, http://arxiv.org/abs/1605.07263 [math.NT].
- 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, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2) 167 (2008), no. 2, 481–547. MR 2415379, DOI 10.4007/annals.2008.167.481
- Benjamin Green and Terence Tao, Linear equations in primes, Ann. of Math. (2) 171 (2010), no. 3, 1753–1850. MR 2680398, DOI 10.4007/annals.2010.171.1753
- Benjamin Green and Terence Tao, Yet another proof of Szemerédi’s theorem, An irregular mind: Szemerédi is 70, Bolyai Soc. Math. Stud., vol. 21, Springer, 2010, pp. 335–342.
- Ben Green, Terence Tao, and Tamar Ziegler, An inverse theorem for the Gowers $U^{s+1}[N]$-norm, Ann. of Math. (2) 176 (2012), no. 2, 1231–1372. MR 2950773, DOI 10.4007/annals.2012.176.2.11
- Karsten Grove, Hermann Karcher, and Ernst A. Ruh, Group actions and curvature, Invent. Math. 23 (1974), 31–48. MR 385750, DOI 10.1007/BF01405201
- Karsten Grove, Hermann Karcher, and Ernst A. Ruh, Jacobi fields and Finsler metrics on compact Lie groups with an application to differentiable pinching problems, Math. Ann. 211 (1974), 7–21. MR 355917, DOI 10.1007/BF01344138
- Y. Gutman, F. Manners, and P. P. Varjú, The structure theory of nilspaces i, http://arxiv.org/abs/1605.08945 [math.DS], 2016.
- —, The structure theory of nilspaces ii: Representation as nilmanifolds, http://arxiv.org/abs/1605.08948 [math.DS], 2016.
- —, The structure theory of nilspaces iii: Inverse limit representations and topological dynamics, http://arxiv.org/abs/1605.08950 [math.DS], 2016.
- D. R. Heath-Brown, Integer sets containing no arithmetic progressions, J. London Math. Soc. (2) 35 (1987), no. 3, 385–394. MR 889362, DOI 10.1112/jlms/s2-35.3.385
- Bernard Host and Bryna Kra, Nonconventional ergodic averages and nilmanifolds, Ann. of Math. (2) 161 (2005), no. 1, 397–488. MR 2150389, DOI 10.4007/annals.2005.161.397
- Bernard Host and Bryna Kra, Parallelepipeds, nilpotent groups and Gowers norms, Bull. Soc. Math. France 136 (2008), no. 3, 405–437 (English, with English and French summaries). MR 2415348, DOI 10.24033/bsmf.2561
- D. Kazhdan, On $\varepsilon$-representations, Israel J. Math. 43 (1982), no. 4, 315–323. MR 693352, DOI 10.1007/BF02761236
- Roy Meshulam, On subsets of finite abelian groups with no $3$-term arithmetic progressions, J. Combin. Theory Ser. A 71 (1995), no. 1, 168–172. MR 1335785, DOI 10.1016/0097-3165(95)90024-1
- Cristopher Moore and Alexander Russell, Approximate representations, approximate homomorphisms, and low-dimensional embeddings of groups, SIAM J. Discrete Math. 29 (2015), no. 1, 182–197. MR 3304255, DOI 10.1137/140958578
- Brendan Nagle, Vojtěch Rödl, and Mathias Schacht, The counting lemma for regular $k$-uniform hypergraphs, Random Structures Algorithms 28 (2006), no. 2, 113–179. MR 2198495, DOI 10.1002/rsa.20117
- Vojtěch Rödl and Jozef Skokan, Regularity lemma for $k$-uniform hypergraphs, Random Structures Algorithms 25 (2004), no. 1, 1–42. MR 2069663, DOI 10.1002/rsa.20017
- K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104–109. MR 51853, DOI 10.1112/jlms/s1-28.1.104
- I. Z. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar. 65 (1994), no. 4, 379–388. MR 1281447, DOI 10.1007/BF01876039
- I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 939–945. MR 519318
- Tom Sanders, On Roth’s theorem on progressions, Ann. of Math. (2) 174 (2011), no. 1, 619–636. MR 2811612, DOI 10.4007/annals.2011.174.1.20
- Tom Sanders, On certain other sets of integers, J. Anal. Math. 116 (2012), 53–82. MR 2892617, DOI 10.1007/s11854-012-0003-9
- J. Solymosi, A note on a question of Erdős and Graham, Combin. Probab. Comput. 13 (2004), no. 2, 263–267. MR 2047239, DOI 10.1017/S0963548303005959
- B. Szegedy, Structure of finite nilspaces and inverse theorems for the Gowers norms in bounded exponent groups, http://arxiv.org/abs/1011.1057 [math.CO], 2010.
- —, On higher order Fourier analysis, http://arxiv.org/abs/1203.2260 , 2012.
- 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
- E. Szemerédi, Integer sets containing no arithmetic progressions, Acta Math. Hungar. 56 (1990), no. 1-2, 155–158. MR 1100788, DOI 10.1007/BF01903717
- Terence Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), no. 7, 1257–1280. MR 2259060, DOI 10.1016/j.jcta.2005.11.006
- Andrew Thomason, Pseudorandom graphs, Random graphs ’85 (Poznań, 1985) North-Holland Math. Stud., vol. 144, North-Holland, Amsterdam, 1987, pp. 307–331. MR 930498
- Matthew C. H. Tointon, Recurrence and non-uniformity of bracket polynomials, Online J. Anal. Comb. 9 (2014), 36. MR 3238334
- J. Wolf, Finite field models in arithmetic combinatorics—ten years on, Finite Fields Appl. 32 (2015), 233–274. MR 3293412, DOI 10.1016/j.ffa.2014.11.003
Additional Information
- W. T. Gowers
- Affiliation: Department of Mathematics, University of Cambridge, DPMMS, 16 Mill Lane, Cambridge CB2 1SB, United Kingdom
- MR Author ID: 264475
- ORCID: 0000-0002-5168-0785
- Email: W.T.Gowers@dpmms.cam.ac.uk
- Received by editor(s): July 31, 2016
- Published electronically: September 14, 2016
- © Copyright 2016 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 54 (2017), 1-44
- MSC (2010): Primary 05D99
- DOI: https://doi.org/10.1090/bull/1550
- MathSciNet review: 3584096