Revised: April 29, 2011

Published: July 12, 2011

**Keywords:**Inverse Gowers conjecture, additive combinatorics, Gowers norm

**ACM Classification:**F.2.2

**AMS Classification:**05E99

**Abstract:**
[Plain Text Version]

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:\mathbb{F}^N_p \to \mathbb{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).