Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR07-123 | 20th October 2008 00:00

Inverse Conjecture for the Gowers norm is false

RSS-Feed




Revision #2
Authors: Shachar Lovett, Roy Meshulam, Alex Samorodnitsky
Accepted on: 20th October 2008 00:00
Downloads: 2874
Keywords: 


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


Revision #1 to TR07-123 | 6th May 2008 00:00

Inverse Conjecture for the Gowers norm is false Revision of: TR07-123





Revision #1
Authors: Shachar Lovett, Roy Meshulam
Accepted on: 6th May 2008 00:00
Downloads: 2897
Keywords: 


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


Paper:

TR07-123 | 21st November 2007 00:00

Inverse Conjecture for the Gowers norm is false





TR07-123
Authors: Shachar Lovett, Roy Meshulam, Alex Samorodnitsky
Publication: 7th December 2007 11:45
Downloads: 2930
Keywords: 


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



ISSN 1433-8092 | Imprint