Volume 7 (2011) Article 9 pp. 131-145
Inverse Conjecture for the Gowers Norm is False
Revised: April 29, 2011
Published: July 12, 2011
[PDF (224K)]    [PS (846K)]    [PS.GZ (244K)]
[Source ZIP]
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).