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
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
0 references
0 references