ECCC-Report TR07-123https://eccc.weizmann.ac.il/report/2007/123Comments and Revisions published for TR07-123en-usMon, 20 Oct 2008 00:00:00 +0200
Revision 2
| Inverse Conjecture for the Gowers norm is false |
Shachar Lovett,
Roy Meshulam,
Alex Samorodnitsky
https://eccc.weizmann.ac.il/report/2007/123#revision2Let $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$.
Mon, 20 Oct 2008 00:00:00 +0200https://eccc.weizmann.ac.il/report/2007/123#revision2
Revision 1
| Inverse Conjecture for the Gowers norm is false Revision of: TR07-123 |
Shachar Lovett,
Roy Meshulam
https://eccc.weizmann.ac.il/report/2007/123#revision1Let $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$.
Tue, 06 May 2008 00:00:00 +0300https://eccc.weizmann.ac.il/report/2007/123#revision1
Paper TR07-123
| Inverse Conjecture for the Gowers norm is false |
Shachar Lovett,
Roy Meshulam,
Alex Samorodnitsky
https://eccc.weizmann.ac.il/report/2007/123
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$.
Fri, 07 Dec 2007 11:45:46 +0200https://eccc.weizmann.ac.il/report/2007/123