Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

Generalizations of Fourier analysis, and how to apply them


Author: W. T. Gowers
Journal: Bull. Amer. Math. Soc. 54 (2017), 1-44
MSC (2010): Primary 05D99
DOI: https://doi.org/10.1090/bull/1550
Published electronically: September 14, 2016
MathSciNet review: 3584096
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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
  • [2] 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, https://doi.org/10.1016/S0195-6698(85)80001-9
  • [3] Antal Balog and Endre Szemerédi, A statistical theorem of set addition, Combinatorica 14 (1994), no. 3, 263-268. MR 1305895, https://doi.org/10.1007/BF01212974
  • [4] Vitaly Bergelson, Bernard Host, and Bryna Kra, Multiple recurrence and nilsequences, Invent. Math. 160 (2005), no. 2, 261-303. MR 2138068, https://doi.org/10.1007/s00222-004-0428-6
  • [5] 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, https://doi.org/10.1112/jlms/jdw010
  • [6] J. Bourgain, On triples in arithmetic progression, Geom. Funct. Anal. 9 (1999), no. 5, 968-984. MR 1726234, https://doi.org/10.1007/s000390050105
  • [7] Jean Bourgain, Roth's theorem on progressions revisited, J. Anal. Math. 104 (2008), 155-192. MR 2403433, https://doi.org/10.1007/s11854-008-0020-x
  • [8] O. A. Camarena and B Szegedy, Nilspaces, nilmanifolds and their morphisms, http://arxiv.org/abs/1009.3825 [math.DS], 2012.
  • [9] P. Candela, Notes on compact nilspaces, http://arxiv.org/abs/1605.08940 [math.DS], 2016.
  • [10] P Candela, Notes on nilspaces: algebraic aspects, http://arxiv.org/abs/1601.03693 [math.DS], 2016.
  • [11] F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), no. 4, 345-362. MR 1054011, https://doi.org/10.1007/BF02125347
  • [12] 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].
  • [13] 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].
  • [14] Jacob Fox, A new proof of the graph removal lemma, Ann. of Math. (2) 174 (2011), no. 1, 561-579. MR 2811609, https://doi.org/10.4007/annals.2011.174.1.17
  • [15] 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].
  • [16] G. A. Freiman, Structure theory of set addition, Proc. Conf. Structure Theory of Set Addition, June 1993, pp. 299-318.
  • [17] 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, https://doi.org/10.1007/s000390050065
  • [18] W. T. Gowers, A new proof of Szemerédi's theorem, Geom. Funct. Anal. 11 (2001), no. 3, 465-588. MR 1844079, https://doi.org/10.1007/s00039-001-0332-9
  • [19] W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math. (2) 166 (2007), no. 3, 897-946. MR 2373376, https://doi.org/10.4007/annals.2007.166.897
  • [20] W. T. Gowers, Quasirandom groups, Combin. Probab. Comput. 17 (2008), no. 3, 363-387. MR 2410393, https://doi.org/10.1017/S0963548307008826
  • [21] W. T. Gowers, Decompositions, approximate structure, transference, and the Hahn-Banach theorem, Bull. Lond. Math. Soc. 42 (2010), no. 4, 573-606. MR 2669681, https://doi.org/10.1112/blms/bdq018
  • [22] 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].
  • [23] W. T. Gowers and J. Wolf, Linear forms and quadratic uniformity for functions on $ \mathbb{Z}_N$, J. Anal. Math. 115 (2011), 121-186. MR 2855036, https://doi.org/10.1007/s11854-011-0026-7
  • [24] W. T. Gowers and J. Wolf, Linear forms and quadratic uniformity for functions on $ \mathbb{F}^n_p$, Mathematika 57 (2011), no. 2, 215-237. MR 2825234, https://doi.org/10.1112/S0025579311001264
  • [25] 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, https://doi.org/10.1017/CBO9780511734885.002
  • [26] Ben J. Green, Sárközy's theorem in function fields, http://arxiv.org/abs/1605.07263 [math.NT].
  • [27] 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, https://doi.org/10.1017/S0013091505000325
  • [28] Ben Green and Terence Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2) 167 (2008), no. 2, 481-547. MR 2415379, https://doi.org/10.4007/annals.2008.167.481
  • [29] Benjamin Green and Terence Tao, Linear equations in primes, Ann. of Math. (2) 171 (2010), no. 3, 1753-1850. MR 2680398, https://doi.org/10.4007/annals.2010.171.1753
  • [30] 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.
  • [31] 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, https://doi.org/10.4007/annals.2012.176.2.11
  • [32] Karsten Grove, Hermann Karcher, and Ernst A. Ruh, Group actions and curvature, Invent. Math. 23 (1974), 31-48. MR 0385750
  • [33] 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 0355917
  • [34] Y. Gutman, F. Manners, and P. P. Varjú, The structure theory of nilspaces i, http://arxiv.org/abs/1605.08945 [math.DS], 2016.
  • [35] -, The structure theory of nilspaces ii: Representation as nilmanifolds, http://arxiv.org/abs/1605.08948 [math.DS], 2016.
  • [36] -, The structure theory of nilspaces iii: Inverse limit representations and topological dynamics, http://arxiv.org/abs/1605.08950 [math.DS], 2016.
  • [37] D. R. Heath-Brown, Integer sets containing no arithmetic progressions, J. London Math. Soc. (2) 35 (1987), no. 3, 385-394. MR 889362, https://doi.org/10.1112/jlms/s2-35.3.385
  • [38] Bernard Host and Bryna Kra, Nonconventional ergodic averages and nilmanifolds, Ann. of Math. (2) 161 (2005), no. 1, 397-488. MR 2150389, https://doi.org/10.4007/annals.2005.161.397
  • [39] 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
  • [40] D. Kazhdan, On $ \varepsilon $-representations, Israel J. Math. 43 (1982), no. 4, 315-323. MR 693352, https://doi.org/10.1007/BF02761236
  • [41] 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, https://doi.org/10.1016/0097-3165(95)90024-1
  • [42] 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, https://doi.org/10.1137/140958578
  • [43] 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, https://doi.org/10.1002/rsa.20117
  • [44] Vojtěch Rödl and Jozef Skokan, Regularity lemma for $ k$-uniform hypergraphs, Random Structures Algorithms 25 (2004), no. 1, 1-42. MR 2069663, https://doi.org/10.1002/rsa.20017
  • [45] K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104-109. MR 0051853
  • [46] I. Z. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar. 65 (1994), no. 4, 379-388. MR 1281447, https://doi.org/10.1007/BF01876039
  • [47] 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
  • [48] Tom Sanders, On Roth's theorem on progressions, Ann. of Math. (2) 174 (2011), no. 1, 619-636. MR 2811612, https://doi.org/10.4007/annals.2011.174.1.20
  • [49] Tom Sanders, On certain other sets of integers, J. Anal. Math. 116 (2012), 53-82. MR 2892617, https://doi.org/10.1007/s11854-012-0003-9
  • [50] J. Solymosi, A note on a question of Erdős and Graham, Combin. Probab. Comput. 13 (2004), no. 2, 263-267. MR 2047239, https://doi.org/10.1017/S0963548303005959
  • [51] 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.
  • [52] -, On higher order Fourier analysis, http://arxiv.org/abs/1203.2260 , 2012.
  • [53] E. Szemerédi, On sets of integers containing no $ k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199-245. Collection of articles in memory of Juriĭ Vladimirovič Linnik. MR 0369312
  • [54] E. Szemerédi, Integer sets containing no arithmetic progressions, Acta Math. Hungar. 56 (1990), no. 1-2, 155-158. MR 1100788, https://doi.org/10.1007/BF01903717
  • [55] Terence Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), no. 7, 1257-1280. MR 2259060, https://doi.org/10.1016/j.jcta.2005.11.006
  • [56] Andrew Thomason, Pseudorandom graphs, Random graphs '85 (Poznań, 1985) North-Holland Math. Stud., vol. 144, North-Holland, Amsterdam, 1987, pp. 307-331. MR 930498
  • [57] Matthew C. H. Tointon, Recurrence and non-uniformity of bracket polynomials, Online J. Anal. Comb. 9 (2014), 1-36. MR 3238334
  • [58] J. Wolf, Finite field models in arithmetic combinatorics--ten years on, Finite Fields Appl. 32 (2015), 233-274. MR 3293412, https://doi.org/10.1016/j.ffa.2014.11.003

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2010): 05D99

Retrieve articles in all journals with MSC (2010): 05D99


Additional Information

W. T. Gowers
Affiliation: Department of Mathematics, University of Cambridge, DPMMS, 16 Mill Lane, Cambridge CB2 1SB, United Kingdom
Email: W.T.Gowers@dpmms.cam.ac.uk

DOI: https://doi.org/10.1090/bull/1550
Received by editor(s): July 31, 2016
Published electronically: September 14, 2016
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society