Inverse conjecture for the Gowers norm is false

DOI10.4086/TOC.2011.V007A009zbMATH Open1282.11009arXiv0711.3388OpenAlexW2611472186MaRDI QIDQ2913795FDOQ2913795

Alex Samorodnitsky, Shachar Lovett, Roy Meshulam

Publication date: 27 September 2012

Published in: Theory of Computing (Search for Journal in Brave)

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}o{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$.

Full work available at URL: https://arxiv.org/abs/0711.3388

zbMATH Keywords

additive combinatoricsGowers norminverse Gowers conjecture

Mathematics Subject Classification ID

Polynomials in number theory (11C08) Other combinatorial number theory (11B75) Polynomials over finite fields (11T06) Arithmetic combinatorics; higher degree uniformity (11B30) Inverse problems of additive number theory, including sumsets (11P70)

Cited In (7)

• An inverse theorem for the uniformity seminorms associated with the action of \(\mathbb F_p^\infty\)
• Energies and structure of additive sets
• Finite field models in arithmetic combinatorics -- ten years on
• Properties of high rank subvarieties of affine spaces
• The Gotsman-Linial Conjecture is False
• On the Gowers norms of certain functions
• Non-classical polynomials and the inverse theorem

This page was built for publication: Inverse conjecture for the Gowers norm is false

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2913795)