Inverse conjecture for the gowers norm is false

ABSTRACT

Let p be a fixed prime number and N be a large integer. The "Inverse Conjecture for the Gowers Norm" states that if the "d-th Gowers norm" of a function f:F^N_p to F_p is non-negligible, that is larger than a constant independent of N, then f has a non-trivial correlation with a degree d-1 polynomial. The conjecture is known to hold for d=2,3 and for any prime p. In this paper we show the conjecture to be false for p=2 and for d=4, by presenting an explicit function whose 4-th Gowers norm is non-negligible, but whose correlation with any polynomial of degree 3 is exponentially small. Essentially the same result, with different bounds for correlation, was independently obtained by Green and Tao. Their analysis uses a modification of a Ramsey-type argument of Alon and Beigel to show inapproximability of certain functions by low-degree polynomials. We observe that a combination of our results with the argument of Alon and Beigel implies the inverse conjecture to be false for any prime p, for d = p².

REFERENCES

• 1: Noga Alon , Richard Beigel, Lower Bounds for Approximations by Low Degree Polynomials Over Z_m, Proceedings of the 16th Annual Conference on Computational Complexity, p.184, June 18-21, 2001
• 2: N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, D. Ron, Testing low--degree polynomials over GF(2), RANDOM--APPROX 2003,pp. 188--199.
• 3: M. Bellare, D. Coppersmith, J. Hastad, M. Kiwi, M. Sudan Linearity testing in characteristic 2, IEEE Trans. Inform.Theory, vol. IT-42, 6, 1996, 1782--1795.
• 4: Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
• 5: Andrej Bogdanov , Emanuele Viola, Pseudorandom Bits for Polynomials, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.41-51, October 21-23, 2007 [doi>10.1109/FOCS.2007.56]
• 6: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 7: W. T. Gowers, A new proof of Szemeredi's theorem, GAFA Vol.11(2001), pp. 465--588.
• 8: B. Green, T. Tao, An inverse theorem for the Gowers U³norm, Proc. Edinburgh Math. Soc., to appear.
• 9: B. Green, T.Tao, The distribution of polynomials over finitefields, with applications to the Gowers norms, preprint, 2007.
• 10: B. Host, B. Kra, Nonconventional ergodic averages andnilmanifolds, Annals of Math. 161, 1 (2005) 397--488.
• 11: Tali Kaufman , Dana Ron, Testing Polynomials over General Fields, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.413-422, October 17-19, 2004 [doi>10.1109/FOCS.2004.65]
• 12: . MacWilliams and N. J. A. Sloane, TheTheory of Error Correcting Codes, Amsterdam, North--Holland, 1977.
• 13: Alex Samorodnitsky, Low-degree tests at large distances, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250864]
• 14: Terence Tao, Structure and Randomness in Combinatorics, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.3-15, October 21-23, 2007 [doi>10.1109/FOCS.2007.68]
• 15: Emanuele Viola , Avi Wigderson, Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.141-154, June 13-March 16, 2007 [doi>10.1109/CCC.2007.15]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Theory

Keywords:
gowers norm, low degree tests, multivariate polynomials