<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic
Terence Tao1 and Tamar Ziegler2
1UCLA Department of Mathematics, Los Angeles, CA 90095-1596, USA
tao@math.ucla.edu
2Department of Mathematics, Technion - Israel Institute of Technology, Haifa 32000, Israel
tamarzr@tx.technion.ac.il
Annals of Combinatorics 16 (1) pp.121-188 March, 2012
AMS Subject Classification: 11B30, 11T06
Abstract:
We establish the inverse conjecture for the Gowers norm over finite fields, which asserts (roughly speaking) that if a bounded function f : V →C on a finite-dimensional vector space V over a finite field F has large Gowers uniformity norm ||f ||Us+1(V), then there exists a (non-classical) polynomial P: V →T of degree at most s such that f correlates with the phase e(P) = e2πiP. This conjecture had already been established in the “high characteristic case”, when the characteristic of F is at least as large as s. Our proof relies on the weak form of the inverse conjecture established earlier by the authors and Bergelson [3], together with new results on the structure and equidistribution of non-classical polynomials, in the spirit of the work of Green and the first author [22] and of Kaufman and Lovett [28].
Keywords: finite fields, polynomials, Gowers uniformity norms

References:

1. Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., Ron, D.: Testing flow-degree polynomials over GF(2). In: Arora, S. et al. (eds.) Approximation, Randomization, and Combinatorial Optimization, pp. 188–199. Spinger, Berlin (2003). Also: Testing Reed-Muller codes. IEEE Trans. Inform. Theory 51(11), 4032–4039 (2005)

2. Austin, T.: On the norm convergence of nonconventional ergodic averages. Ergodic Theory Dynam. Systems 30(2), 321–338 (2010)

3. Bergelson, V., Tao, T., Ziegler, T.: An inverse theorem for the uniformity seminorms associated with the action of Fp . Geom. Funct. Anal. 19(6), 1539–1596 (2010)

4. Bergelson, V., Leibman, A., McCutcheon, R.: Polynomial Szemerédi theorems for countable modules over integral domains and finite fields. J. Anal. Math. 95, 243–296 (2005)

5. Bogdanov, A., Viola, E.: Pseudorandom bits for polynomials. SIAM J. Comput. 39(6), 2464–2486 (2010)

6. Camarena, O., Szegedy, B.: Nilspaces, nilmanifolds and their morphisms. Preprint. arXiv:1009.3825 (2010)

7. Frantzikinakis, N., Host, B., Kra, B.: Multiple recurrence and convergence for sequences related to the prime numbers. J. Reine Angew. Math. 611, 131–144 (2007)

8. Furstenberg, H.: Ergodic behavior of diagonal measures and a theorem of Szemer´edi on arithmetic progressions. J. Anal. Math. 31, 204–256 (1977)

9. Furstenberg, H., Katznelson, Y.: A density version of the Hales-Jewett theorem. J. Anal. Math. 57, 64–119 (1991)

10. Gödel, K.: The consistency of the axiom of choice and of the generalized continuumhypothesis. Proc. Natl. Acad. Sci. USA 24(12), 556–557 (1938)

11. Gowers, T.: A new proof of Szemerédi’s theorem for arithmetic progressions of length four. Geom. Funct. Anal. 8(3), 529–551 (1998)

12. Gowers, T.: A new proof of Szemerédi’s theorem. Geom. Funct. Anal. 11(3), 465–588 (2001)

13. Gowers, T.: Decompositions, approximate structure, transference, and the Hahn-Banach theorem. Bull. Lond. Math. Soc. 42(4), 573–606 (2010)

14. Gowers, T., Wolf, J.: The true complexity of a system of linear equations. Proc. Lond. Math. Soc. (3) 100(1), 155–176 (2010)

15. Gowers, T., Wolf, J.: Linear forms and quadratic uniformity for functions on Fn p. Preprint.

16. Gowers, T., Wolf, J.: Linear forms and higher-degree uniformity for functions on Fn p. Geom. Funct. Anal. 21(1), 36–69 (2011)

17. Green, B., Tao, T.: The primes contain arbitrarily long arithmetic progressions. Ann. of Math. 167(2), 481–547 (2008)

18. Green, B., Tao, T.: An inverse theorem for the Gowers U3(G) norm. Proc. Edinburgh Math. Soc. (2) 51(1), 73–153 (2008)

19. Green, B., Tao, T.: Linear equations in primes. Ann. of Math. (2) 171(3), 1753–1850 (2010)

20. Green, B., Tao, T.: New bounds for Szemerédi’s Theorem, I: progressions of length 4 in finite field geometries. Proc. Lond. Math. Soc. (3) 98(2), 365–392 (2009)

21. Green, B., Tao, T.: The quantitative behaviour of polynomial orbits on nilmanifolds. Ann. of Math. (2) (to appear)

22. Green, B., Tao, T.: The distribution of polynomials over finite fields, with applications to the Gowers norms. Contrib. Discrete Math. 4(2), 1–36 (2009)

23. Green, B., Tao, T.: An arithmetic regularity lemma, an associated counting lemma, and applications. Preprint

24. Green, B., Tao, T., Ziegler, T.: An inverse theorem for the GowersUs+1[N] norm. Preprint

25. Hall, P.: A contribution to the theory of groups of prime-power order. Proc. London Math. Soc. (2) 36(1), 29–95 (1934)

26. Host, B., Kra, B.: Nonconventional ergodic averages and nilmanifolds. Ann. of Math. (2) 161(1), 397–488 (2005)

27. Host, B., Kra, B.: Parallelepipeds, nilpotent groups and Gowers norms. Bull. Soc. Math. France 136(3), 405–437 (2008)

28. Kaufman, T., Lovett, S.: Worst case to average case reductions for polynomials. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 166–175. IEEE Computer Society, Los Alamitos, CA (2008)

29. Lazard, M.: Sur certaines suites d’éléments dans les groupes libres et leurs extensions. C. R. Acad. Sci. Paris 236, 36–38 (1953)

30. Leibman, A.: Polynomial sequences in groups. J. Algebra 201(1), 189–206 (1998)

31. Leibman, A.: Polynomial mappings of groups. Israel J. Math. 129, 29–60 (2002)

32. Loeb, P.A.: Conversion from nonstandard to standard measure spaces and applications in probability theory. Trans. Amer. Math. Soc. 211, 113–122 (1975)

33. Lovett, S., Meshulam, R., Samorodnitsky, A.: Inverse conjecture for the Gowers norm is false. In: Dwork, C. (ed.) Proceedings of the 40th Annual ACM Symposium on Theory of Computing held in Victoria, BC, May 17-20, 2008, pp. 547–556. ACM, New York (2008)

34. Petresco, J.: Sur les commutateurs. Math. Z. 61, 348–356 (1954)

35. Samorodnitsky, A.: Low-degree tests at large distances. In: Feige, U. (ed.) STOC’07– Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pp. 506–515. ACM, New York (2007)

36. Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. J. Comput. System Sci. 62(2), 236–266 (2001)

37. Szegedy, B.: Gowers norms, regularization and limits of functions on abelian groups. Preprint. Avaible at arXiv:1010.6211 (2010)

38. Szegedy, B.: Structure of finite nilspaces and inverse theorems for the Gowers norms in bounded exponent groups. Preprint. Avaible at arXiv:1011.1057 (2010)

39. Tao, T.: A quantitative ergodic theory proof of Szemerédi’s theorem. Electron. J. Combin. 13(1), #R99 (2006)

40. Tao, T.: Structure and randomness in combinatorics. In: FOCS’07: Proceedings of the 48th Annual Symposium on Foundations of Computer Science, pp. 3–18. IEEE Computer Society, Los Alamitos (2007)

41. Tao, T.: Poincaré’s Legacies, Vol I., American Mathematical Society, Providence (2009)

42. Tao, T., Vu, V.: Additive Combinatorics, Cambridge Univ. Press, Cambridge (2006)

43. Tao, T., Ziegler, T.: The inverse conjecture for the Gowers norm over finite fields via the correspondence principle. Anal. PDE 3(1), 1–20 (2010)

44. Towsner, H.: A correspondence principle for the Gowers norms. Preprint. Avaible at arXiv:0905.0493 (2009)

45. Varnavides, P.: On certain sets of positive density. J. London Math. Soc. 34, 358–360 (1959)

46. Ziegler, T.: Universal characteristic factors and Furstenberg averages. J. Amer. Math. Soc. 20(1), 53–97 (2007)