Equivalence of polynomial conjectures in additive combinatorics (Q377805)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Equivalence of polynomial conjectures in additive combinatorics
scientific article

    Statements

    Equivalence of polynomial conjectures in additive combinatorics (English)
    0 references
    0 references
    7 November 2013
    0 references
    Let \(S\subset \mathbb{F}^n_2\). The set \(S\) is said to have doubling \(K\) if \(| S+S| \leq K| S| \), where \(S+S=\{x+y: x,y\in S\}\). According to a theorem of \textit{I. Z. Ruzsa} [Structure theory of set addition. Astérisque 258, 323--326 (1999; Zbl 0946.11007)], any such set is contained in a vector space which is not much larger: \(| \text{Span}(S)| \leq K^22^{K^4}| S| \). The factor \(K^22^{K^4}\) was improved to \(K^22^{2K^2-2}\) by \textit{B. Green} and \textit{I. Z. Ruzsa} [Bull.\ London Math.\ Soc. 38, No. 1, 43--52 (2006; Zbl 1155.11307)], to \(2^{O(K^{3/2}\log K)}\) by \textit{T. Sanders} [Comb.\ Probab.\ Comput. 17, No. 2, 297--305 (2008; Zbl 1151.15003)], to \(2^{2K+O(\sqrt K \log K)}\) by \textit{B. Green} and \textit{T. Tao} [Comb.\ Probab.\ Comput. 18, No. 3, 335--355 (2009; Zbl 1254.11093)]. The bound \(2^{(2+o(1))K}\) is tight up to the \(o(1)\) term. The Polynomial Freiman-Ruzsa conjecture states that there is a subset \(S'\subset S\) such that \(| S'| \geq K^{-O(1)}| S| \) and \(| \text{Span} (S')| \leq K^{O(1)}| S| \). The Gowers norm is defined over complex functions \(F\colon \mathbb{F}^n_2\to \mathbb{C}\). Define the derivative of \(F\) in direction \(y\in \mathbb{F}^n_2\) as \(F_y(x)=F(x+y)\overline{F(x)}\), and iterated derivatives analogously. The third Gowers norm of \(F\) is defined as \[ | | F| | _{U^3}=\left( \mathbb{E}_{x, y_1, y_2, y_3\in \mathbb{F}^n_2} [F_{y_1, y_2, y_3}(x)] \right)^{1/{2^3}}. \] Let \(f\colon \mathbb {F}^n_2 \to \mathbb{F}_2\) be a function for which \(| | (-1)^f| | _{U^3}\geq \varepsilon\). The Polynomial Inverse Gowers conjecture for \(U^3\) speculates that there exists a quadratic polynomial \(p(x)\) such that \(\text{Pr}_x [f(x)=p(x)] \geq \frac {1}{2} +\varepsilon^{O(1)}\). In the paper under review the author proves that the Polynomial Freiman-Ruzsa conjecture and the Polynomial Inverse Gowers conjecture for \(U^3\) are equivalent. The author also remarks that this result was independently discovered by \textit{B. Green} and \textit{T. Tao} [Math.\ Proc.\ Camb.\ Phil.\ Soc. 149, No. 1, 1--19 (2010; Zbl 1229.11132)], who also proved it for the case of groups of unbounded torsion.
    0 references
    polynomial Freiman-Ruzsa conjecture
    0 references
    polynomial inverse Gowers conjecture for \(U^3\)
    0 references

    Identifiers