Theory of Computing
-------------------
Title     : Inverse Conjecture for the Gowers Norm is False
Authors   : Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky
Volume    : 7
Number    : 9
Pages     : 131-145
URL       : https://theoryofcomputing.org/articles/v007a009

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_p^N \to F_p is 
non-negligible, that is, larger than a constant independent of N, 
then f is non-trivially correlated to 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 
d = 4, by presenting an explicit function whose 4-th Gowers norm 
is non-negligible, but whose correlation to any polynomial of 
degree 3 is exponentially small.  Essentially the same result 
(with different correlation bounds) was independently
obtained by Green and Tao (2009).