Inverse Conjecture for the Gowers norm is false

Details Inverse Conjecture for the Gowers norm is false Inverse Conjecture for the Gowers norm is false

2007-11-21

arxiv.org/abs/0711.3388v3

Mathematics

Combinatorics

20 pages

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Inverse Conjecture for the Gowers norm is false does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Inverse Conjecture for the Gowers norm is false, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inverse Conjecture for the Gowers norm is false will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-414619