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 can be non-trivially approximated by 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 any polynomial of degree 3 is exponentially small. Essentially the same result (with different correlation bounds) was independently obtained by Green and Tao cite{gt07}. Their analysis uses a modification of a Ramsey-type argument of Alon and Beigel cite{ab} 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^2.

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 can be non-trivially approximated by 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 any polynomial
of degree 3 is exponentially small. Essentially the same result
(with different correlation bounds) was independently obtained by
Green and Tao cite{gt07}. Their analysis uses a modification of a
Ramsey-type argument of Alon and Beigel cite{ab} 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^2.

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 can be non-trivially approximated by 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 any polynomial of degree 3 is exponentially small.

Essentially the same result (with different correlation bounds) was independently obtained by Green and Tao \cite{gt07}. Their analysis uses a modification of a Ramsey-type argument of Alon and Beigel \cite{ab} 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^2.