Inverse Conjecture for the Gowers norm is false
| dc.creator | Lovett, Shachar | |
| dc.creator | Meshulam, Roy | |
| dc.creator | Samorodnitsky, Alex | |
| dc.date | 2007-11-21 | |
| dc.date | 2008-10-20 | |
| dc.date.accessioned | 2026-07-07T10:11:08Z | |
| dc.date.available | 2026-07-07T10:11:08Z | |
| dc.description | 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$. | |
| dc.description | 20 pages | |
| dc.identifier | https://arxiv.org/abs/0711.3388 | |
| dc.identifier | http://arxiv.org/abs/0711.3388 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/171768 | |
| dc.subject | Combinatorics | |
| dc.subject | 11T06 | |
| dc.title | Inverse Conjecture for the Gowers norm is false | |
| dc.type | text |