Inverse conjecture for the Gowers norm is false

DOI10.4086/TOC.2011.V007A009MaRDI QIDQ2913795zbMATH OpenOpenAlexFDO

Authors Shachar Lovett, Roy Meshulam, Alex Samorodnitsky

Publication date 27 September 2012

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

Copyright license Creative Commons Attribution 4.0 International

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)

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

Recommendations

• Inverse conjecture for the Gowers norm is false
• The inverse conjecture for the Gowers norm over finite fields via the correspondence principle
• The inverse conjecture for the Gowers norm over finite fields in low characteristic
• An inverse theorem for the Gowers \(U^{s+1}[N]\)-norm
• An inverse theorem for the Gowers \(U^4\)-norm

Cited in

(15)

• An inverse theorem for the uniformity seminorms associated with the action of \(\mathbb F_p^\infty\)
• Energies and structure of additive sets
• An inverse theorem for Gowers norms of trace functions over \(\mathbb F_p\)
• Finite field models in arithmetic combinatorics -- ten years on
• The inverse conjecture for the Gowers norm over finite fields in low characteristic
• Properties of high rank subvarieties of affine spaces
• An inverse theorem for the Gowers \(U^{s+1}[N]\)-norm
• Inverse conjecture for the Gowers norm is false
• The Gotsman-Linial Conjecture is False
• On the Gowers norms of certain functions
• The distribution of polynomials over finite fields, with applications to the Gowers norms
• Non-classical polynomials and the inverse theorem
• An inverse theorem for the Gowers \(U^4\)-norm
• An inverse theorem for the Gowers \(U^{s+1}[N]\)-norm
• Equivalence of polynomial conjectures in additive combinatorics

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)