Volume 7 (2011) Article 9 pp. 131-145

Inverse Conjecture for the Gowers Norm is False

by Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky

Received: October 8, 2008
Revised: April 29, 2011
Published: July 12, 2011

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).

DOI: 10.4086/toc.2011.v007a009

© 2011 Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky
Licensed under a Creative Commons Attribution License (CC-BY)