An inverse theorem for the Gowers $U^{s+1}[N]$-norm

Ben Green; Terence Tao; Tamar Ziegler

doi:10.3934/era.2011.18.69

Previous Article
Deligne pairing and determinant bundle
ERA-MS Home
This Volume
Next Article
Sharpness of Zapolsky's inequality for quasi-states and Poisson brackets

2011, 18: 69-90. doi: 10.3934/era.2011.18.69

An inverse theorem for the Gowers $U^{s+1}[N]$-norm

Ben Green ^1, , Terence Tao ^2, and Tamar Ziegler ^3,

1.	Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WA
2.	Department of Mathematics, UCLA, 405 Hilgard Ave, Los Angeles, CA 90095
3.	Department of Mathematics, Technion - Israel Institute of Technology, Haifa, 32000, Israel

Received March 2011 Revised May 2011 Published July 2011

Abstract
Related Papers

This is an announcement of the proof of the inverse conjecture for the Gowers $U^{s+1}[N]$-norm for all $s \geq 3$; this is new for $s \geq 4$, the cases $s = 1,2,3$ having been previously established. More precisely we outline a proof that if $f : [N] \rightarrow [-1,1]$ is a function with ||$f$|| $U^{s+1}[N] \geq \delta$ then there is a bounded-complexity $s$-step nilsequence $F(g(n)\Gamma)$ which correlates with $f$, where the bounds on the complexity and correlation depend only on $s$ and $\delta$. From previous results, this conjecture implies the Hardy-Littlewood prime tuples conjecture for any linear system of finite complexity. In particular, one obtains an asymptotic formula for the number of $k$-term arithmetic progressions $p_1 < p_2 < ... < p_k \leq N$ of primes, for every $k \geq 3$.

Keywords: Gowers norms, nilsequences..

Mathematics Subject Classification: Primary: 11B9.

Citation: Ben Green, Terence Tao, Tamar Ziegler. An inverse theorem for the Gowers $U^{s+1}[N]$-norm. Electronic Research Announcements, 2011, 18: 69-90. doi: 10.3934/era.2011.18.69

References:

[1]	N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn and D. Ron, Testing low-degree polynomials over GF(2), Approximation, Randomization, and Combinatorial Optimization, 2003, 188-199. Also: Testing Reed-Muller codes, IEEE Transactions on Information Theory, 51 (2005), 4032-4039. doi: 10.1109/TIT.2005.856958. Google Scholar
[2]	A. Balog and E. Szemerédi, A statistical theorem of set addition, Combinatorica, 14 (1994), 263-268. doi: 10.1007/BF01212974. Google Scholar
[3]	V. Bergelson, B. Host and B. Kra, Multiple recurrence and nilsequences, (with an appendix by I. Ruzsa), Invent. Math., 160 (2005), 261-303. doi: 10.1007/s00222-004-0428-6. Google Scholar
[4]	V. Bergelson, T. Tao and T. Ziegler, An inverse theorem for uniformity seminorms associated with the action of $F_p^{\infty}$, Geom. Funct. Anal., 19 (2010), 1539-1596. doi: 10.1007/s00039-010-0051-1. Google Scholar
[5]	J.-P. Conze and E. Lesigne, Sur un théorème ergodique pour des mesures diagonales, (French) [On an ergodic theorem for diagonal measures], C. R. Acad. Sci. Paris Sér. I Math., 306 (1988), 491-493. Google Scholar
[6]	N. Frantzikinakis, B. Host and B. Kra, Multiple recurrence and convergence for sequences related to the prime numbers, J. Reine Angew. Math., 611 (2007), 131-144. doi: 10.1515/CRELLE.2007.076. Google Scholar
[7]	G. A. Freĭman, "Foundations of a Structural Theory of Set Addition," Translations of Mathematical Monographs, 37, AMS, Providence, RI, 1973. Google Scholar
[8]	H. Furstenberg, "Nonconventional Ergodic Averages," The legacy of John von Neumann (Hempstead, NY, 1988), 43-56, Proc. Sympos. Pure Math., 50, Amer. Math. Soc., Providence, RI, 1990. Google Scholar
[9]	H. Furstenberg and B. Weiss, "A mean ergodic theorem for $1/N\sum^N_{n=1}f (T^n x)g(T^ {n^ 2}x)$," Convergence in ergodic theory and probability (Columbus, OH, 1993), 193-227, Ohio State Univ. Math. Res. Inst. Publ., 5 de Gruyter, Berlin, 1996. Google Scholar
[10]	W. T. Gowers, A new proof of Szemerédi's theorem for progressions of length four, GAFA, 8 (1998), 529-551. doi: 10.1007/s000390050065. Google Scholar
[11]	-, A new proof of Szemerédi's theorem, GAFA, 11 (2001), 465-588. Google Scholar
[12]	B. Green, "Generalising the Hardy-Littlewood Method for Primes," International Congress of Mathematicians. Vol. II, 373-399, Eur. Math. Soc., Zürich, 2006. Google Scholar
[13]	B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, Annals of Math. (2), 167 (2008), 481-547. doi: 10.4007/annals.2008.167.481. Google Scholar
[14]	-, An inverse theorem for the Gowers $U^3$-norm, with applications,, Proc. Edinburgh Math. Soc., 51 (): 71. Google Scholar
[15]	-, Linear equations in primes, Ann. Math. (2), 171 (2010), 1753-1850. Google Scholar
[16]	-, The quantitative behaviour of polynomial orbits on nilmanifolds,, to appear in Ann. Math., (). Google Scholar
[17]	-, The Möbius function is strongly orthogonal to nilsequences,, to appear in Ann. Math., (). Google Scholar
[18]	-, An arithmetic regularity lemma, associated counting lemma, and applications,, in, 21 (): 261. Google Scholar
[19]	B. Green, T. Tao and T. Ziegler, An inverse theorem for the Gowers $U^4[N]$-norm, Glasgow Math. J., 53 (2011), 1-50. doi: 10.1017/S0017089510000546. Google Scholar
[20]	-, An inverse theorem for the Gowers $U^{s+1}[N]$ norm,, preprint, (). Google Scholar
[21]	I. J. Håland, Uniform distribution of generalized polynomials, J. Number Theory, 45 (1993), 327-366. doi: 10.1006/jnth.1993.1082. Google Scholar
[22]	B. Host and B. Kra, Convergence of Conze-Lesigne averages, Erg. Th. Dyn. Sys., 21 (2001), 493-509. Google Scholar
[23]	-, Averaging along cubes, Modern Dynamical Systems and Applications, Cambridge University Press, Cambridge, (2004), 123-144. Google Scholar
[24]	-, Nonconventional ergodic averages and nilmanifolds, Ann. of Math. (2), 161 (2005), 397-488. Google Scholar
[25]	-, Uniformity seminorms on $l^\infty$ and applications, J. Anal. Math., 108 (2009), 219-276. doi: 10.1007/s11854-009-0024-1. Google Scholar
[26]	A. Leibman, Pointwise convergence of ergodic averages of polynomial sequences of translations on a nilmanifold, Ergodic Theory and Dynamical Systems, 25 (2005), 201-213. doi: 10.1017/S0143385704000215. Google Scholar
[27]	-, A canonical form and the distribution of values of generalized polynomials,, to appear in Israel Journal of Mathematics., (). Google Scholar
[28]	E. Lesigne, Équations fonctionnelles, couplages de produits gauches et théorèmes ergodiques pour mesures diagonales, (French) [Functional equations, couplings of skew products, ergodic theorems for diagonal measures], Bull. Soc. Math. France, 121 (1993), 315-351. Google Scholar
[29]	I. Z. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar., 65 (1994), 379-388. doi: 10.1007/BF01876039. Google Scholar
[30]	A. Samorodnitsky, "Low-Degree Tests at Large Distances," STOC'07, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, (2007), 506-515. Google Scholar
[31]	B. Szegedy, Higher order Fourier analysis as an algebraic theory I,, preprint, (). Google Scholar
[32]	-, Higher order Fourier analysis as an algebraic theory II,, preprint, (). Google Scholar
[33]	-, Higher order Fourier analysis as an algebraic theory III,, preprint, (). Google Scholar
[34]	T. Tao and T. Ziegler, The inverse conjecture for the Gowers norms over finite fields via the correspondence principle, Anal. PDE, 3 (2010), 1-20. doi: 10.2140/apde.2010.3.1. Google Scholar
[35]	T. Tao and V. Vu, "Additive Combinatorics," Cambridge Studies in Advanced Mathematics, 105, Cambridge University Press, Cambridge, 2006. Google Scholar
[36]	T. Ziegler, Universal characteristic factors and Furstenberg averages, J. Amer. Math. Soc., 20 (2007), 53-97. doi: 10.1090/S0894-0347-06-00532-7. Google Scholar

show all references

References:

[1]	N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn and D. Ron, Testing low-degree polynomials over GF(2), Approximation, Randomization, and Combinatorial Optimization, 2003, 188-199. Also: Testing Reed-Muller codes, IEEE Transactions on Information Theory, 51 (2005), 4032-4039. doi: 10.1109/TIT.2005.856958. Google Scholar
[2]	A. Balog and E. Szemerédi, A statistical theorem of set addition, Combinatorica, 14 (1994), 263-268. doi: 10.1007/BF01212974. Google Scholar
[3]	V. Bergelson, B. Host and B. Kra, Multiple recurrence and nilsequences, (with an appendix by I. Ruzsa), Invent. Math., 160 (2005), 261-303. doi: 10.1007/s00222-004-0428-6. Google Scholar
[4]	V. Bergelson, T. Tao and T. Ziegler, An inverse theorem for uniformity seminorms associated with the action of $F_p^{\infty}$, Geom. Funct. Anal., 19 (2010), 1539-1596. doi: 10.1007/s00039-010-0051-1. Google Scholar
[5]	J.-P. Conze and E. Lesigne, Sur un théorème ergodique pour des mesures diagonales, (French) [On an ergodic theorem for diagonal measures], C. R. Acad. Sci. Paris Sér. I Math., 306 (1988), 491-493. Google Scholar
[6]	N. Frantzikinakis, B. Host and B. Kra, Multiple recurrence and convergence for sequences related to the prime numbers, J. Reine Angew. Math., 611 (2007), 131-144. doi: 10.1515/CRELLE.2007.076. Google Scholar
[7]	G. A. Freĭman, "Foundations of a Structural Theory of Set Addition," Translations of Mathematical Monographs, 37, AMS, Providence, RI, 1973. Google Scholar
[8]	H. Furstenberg, "Nonconventional Ergodic Averages," The legacy of John von Neumann (Hempstead, NY, 1988), 43-56, Proc. Sympos. Pure Math., 50, Amer. Math. Soc., Providence, RI, 1990. Google Scholar
[9]	H. Furstenberg and B. Weiss, "A mean ergodic theorem for $1/N\sum^N_{n=1}f (T^n x)g(T^ {n^ 2}x)$," Convergence in ergodic theory and probability (Columbus, OH, 1993), 193-227, Ohio State Univ. Math. Res. Inst. Publ., 5 de Gruyter, Berlin, 1996. Google Scholar
[10]	W. T. Gowers, A new proof of Szemerédi's theorem for progressions of length four, GAFA, 8 (1998), 529-551. doi: 10.1007/s000390050065. Google Scholar
[11]	-, A new proof of Szemerédi's theorem, GAFA, 11 (2001), 465-588. Google Scholar
[12]	B. Green, "Generalising the Hardy-Littlewood Method for Primes," International Congress of Mathematicians. Vol. II, 373-399, Eur. Math. Soc., Zürich, 2006. Google Scholar
[13]	B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, Annals of Math. (2), 167 (2008), 481-547. doi: 10.4007/annals.2008.167.481. Google Scholar
[14]	-, An inverse theorem for the Gowers $U^3$-norm, with applications,, Proc. Edinburgh Math. Soc., 51 (): 71. Google Scholar
[15]	-, Linear equations in primes, Ann. Math. (2), 171 (2010), 1753-1850. Google Scholar
[16]	-, The quantitative behaviour of polynomial orbits on nilmanifolds,, to appear in Ann. Math., (). Google Scholar
[17]	-, The Möbius function is strongly orthogonal to nilsequences,, to appear in Ann. Math., (). Google Scholar
[18]	-, An arithmetic regularity lemma, associated counting lemma, and applications,, in, 21 (): 261. Google Scholar
[19]	B. Green, T. Tao and T. Ziegler, An inverse theorem for the Gowers $U^4[N]$-norm, Glasgow Math. J., 53 (2011), 1-50. doi: 10.1017/S0017089510000546. Google Scholar
[20]	-, An inverse theorem for the Gowers $U^{s+1}[N]$ norm,, preprint, (). Google Scholar
[21]	I. J. Håland, Uniform distribution of generalized polynomials, J. Number Theory, 45 (1993), 327-366. doi: 10.1006/jnth.1993.1082. Google Scholar
[22]	B. Host and B. Kra, Convergence of Conze-Lesigne averages, Erg. Th. Dyn. Sys., 21 (2001), 493-509. Google Scholar
[23]	-, Averaging along cubes, Modern Dynamical Systems and Applications, Cambridge University Press, Cambridge, (2004), 123-144. Google Scholar
[24]	-, Nonconventional ergodic averages and nilmanifolds, Ann. of Math. (2), 161 (2005), 397-488. Google Scholar
[25]	-, Uniformity seminorms on $l^\infty$ and applications, J. Anal. Math., 108 (2009), 219-276. doi: 10.1007/s11854-009-0024-1. Google Scholar
[26]	A. Leibman, Pointwise convergence of ergodic averages of polynomial sequences of translations on a nilmanifold, Ergodic Theory and Dynamical Systems, 25 (2005), 201-213. doi: 10.1017/S0143385704000215. Google Scholar
[27]	-, A canonical form and the distribution of values of generalized polynomials,, to appear in Israel Journal of Mathematics., (). Google Scholar
[28]	E. Lesigne, Équations fonctionnelles, couplages de produits gauches et théorèmes ergodiques pour mesures diagonales, (French) [Functional equations, couplings of skew products, ergodic theorems for diagonal measures], Bull. Soc. Math. France, 121 (1993), 315-351. Google Scholar
[29]	I. Z. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar., 65 (1994), 379-388. doi: 10.1007/BF01876039. Google Scholar
[30]	A. Samorodnitsky, "Low-Degree Tests at Large Distances," STOC'07, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, (2007), 506-515. Google Scholar
[31]	B. Szegedy, Higher order Fourier analysis as an algebraic theory I,, preprint, (). Google Scholar
[32]	-, Higher order Fourier analysis as an algebraic theory II,, preprint, (). Google Scholar
[33]	-, Higher order Fourier analysis as an algebraic theory III,, preprint, (). Google Scholar
[34]	T. Tao and T. Ziegler, The inverse conjecture for the Gowers norms over finite fields via the correspondence principle, Anal. PDE, 3 (2010), 1-20. doi: 10.2140/apde.2010.3.1. Google Scholar
[35]	T. Tao and V. Vu, "Additive Combinatorics," Cambridge Studies in Advanced Mathematics, 105, Cambridge University Press, Cambridge, 2006. Google Scholar
[36]	T. Ziegler, Universal characteristic factors and Furstenberg averages, J. Amer. Math. Soc., 20 (2007), 53-97. doi: 10.1090/S0894-0347-06-00532-7. Google Scholar

[1]	Tanja Eisner, Pavel Zorin-Kranich. Uniformity in the Wiener-Wintner theorem for nilsequences. Discrete & Continuous Dynamical Systems, 2013, 33 (8) : 3497-3516. doi: 10.3934/dcds.2013.33.3497
[2]	Giovanni Bellettini, Matteo Novaga, Shokhrukh Yusufovich Kholmatov. Minimizers of anisotropic perimeters with cylindrical norms. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1427-1454. doi: 10.3934/cpaa.2017068
[3]	Carsten Burstedde. On the numerical evaluation of fractional Sobolev norms. Communications on Pure & Applied Analysis, 2007, 6 (3) : 587-605. doi: 10.3934/cpaa.2007.6.587
[4]	Sugata Gangopadhyay, Constanza Riera, Pantelimon Stănică. Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations. Advances in Mathematics of Communications, 2021, 15 (2) : 241-256. doi: 10.3934/amc.2020056
[5]	Haïm Brezis. Remarks on some minimization problems associated with BV norms. Discrete & Continuous Dynamical Systems, 2019, 39 (12) : 7013-7029. doi: 10.3934/dcds.2019242
[6]	Piotr Biler, Grzegorz Karch, Jacek Zienkiewicz. Morrey spaces norms and criteria for blowup in chemotaxis models. Networks & Heterogeneous Media, 2016, 11 (2) : 239-250. doi: 10.3934/nhm.2016.11.239
[7]	Andrea Cianchi, Adele Ferone. Improving sharp Sobolev type inequalities by optimal remainder gradient norms. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1363-1386. doi: 10.3934/cpaa.2012.11.1363
[8]	Raphaël Côte, Frédéric Valet. Polynomial growth of high sobolev norms of solutions to the Zakharov-Kuznetsov equation. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1039-1058. doi: 10.3934/cpaa.2021005
[9]	Entisar A.-L. Ali, G. Charlot. Local contact sub-Finslerian geometry for maximum norms in dimension 3. Mathematical Control & Related Fields, 2021, 11 (2) : 373-401. doi: 10.3934/mcrf.2020041
[10]	Milena Stanislavova, Atanas Stefanov. Effective estimates of the higher Sobolev norms for the Kuramoto-Sivashinsky equation. Conference Publications, 2009, 2009 (Special) : 729-738. doi: 10.3934/proc.2009.2009.729
[11]	Guanglu Zhou. A quadratically convergent method for minimizing a sum of Euclidean norms with linear constraints. Journal of Industrial & Management Optimization, 2007, 3 (4) : 655-670. doi: 10.3934/jimo.2007.3.655
[12]	Antonio Avantaggiati, Paola Loreti, Cristina Pocci. Mixed norms, functional Inequalities, and Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1855-1867. doi: 10.3934/dcdsb.2014.19.1855
[13]	Myeongju Chae, Soonsik Kwon. The stability of nonlinear Schrödinger equations with a potential in high Sobolev norms revisited. Communications on Pure & Applied Analysis, 2016, 15 (2) : 341-365. doi: 10.3934/cpaa.2016.15.341
[14]	Victor Kozyakin. Iterative building of Barabanov norms and computation of the joint spectral radius for matrix sets. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 143-158. doi: 10.3934/dcdsb.2010.14.143
[15]	Sergey A. Denisov. The generic behavior of solutions to some evolution equations: Asymptotics and Sobolev norms. Discrete & Continuous Dynamical Systems, 2011, 30 (1) : 77-113. doi: 10.3934/dcds.2011.30.77
[16]	Yaiza Canzani, Boris Hanin. Fixed frequency eigenfunction immersions and supremum norms of random waves. Electronic Research Announcements, 2015, 22: 76-86. doi: 10.3934/era.2015.22.76
[17]	Yamin Wang. On nonexistence of extremals for the Trudinger-Moser functionals involving $ L^p $ norms. Communications on Pure & Applied Analysis, 2020, 19 (9) : 4257-4268. doi: 10.3934/cpaa.2020191
[18]	Zdeněk Skalák. On the asymptotic decay of higher-order norms of the solutions to the Navier-Stokes equations in R³. Discrete & Continuous Dynamical Systems - S, 2010, 3 (2) : 361-370. doi: 10.3934/dcdss.2010.3.361
[19]	Seckin Demirbas. Local well-posedness for 2-D Schrödinger equation on irrational tori and bounds on Sobolev norms. Communications on Pure & Applied Analysis, 2017, 16 (5) : 1517-1530. doi: 10.3934/cpaa.2017072
[20]	F. Catoire, W. M. Wang. Bounds on Sobolev norms for the defocusing nonlinear Schrödinger equation on general flat tori. Communications on Pure & Applied Analysis, 2010, 9 (2) : 483-491. doi: 10.3934/cpaa.2010.9.483

2020 Impact Factor: 0.929

American Institute of Mathematical Sciences

An inverse theorem for the Gowers $U^{s+1}[N]$-norm

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

An inverse theorem for the Gowers $U^{s+1}[N]$-norm

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors