Equivalence of polynomial conjectures in additive combinatorics. (English) Zbl 1274.11158

Lovett, Shachar

Combinatorica 32, No. 5, 607-618 (2012).

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 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 B. Green and 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 T. Sanders [Comb.Probab.Comput. 17, No. 2, 297–305 (2008; Zbl 1151.15003)], to \(2^{2K+O(\sqrt K \log K)}\) by B. Green and 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 B. Green and 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.

Reviewer: Mihály Szalay (Budapest)

MSC:

11P70	Inverse problems of additive number theory, including sumsets
11B30	Arithmetic combinatorics; higher degree uniformity

Keywords:

polynomial Freiman-Ruzsa conjecture; polynomial inverse Gowers conjecture for \(U^3\)

Citations:

Zbl 0946.11007; Zbl 1155.11307; Zbl 1151.15003; Zbl 1254.11093; Zbl 1229.11132

References:

[1]	A. Balog and E. Szemerédi: A statistical theorem of set addition, Combinatorica, 14 (1994), 263–268. · Zbl 0812.11017 · doi:10.1007/BF01212974
[2]	V. Bergelson, T. Tao and T. Ziegler: An inverse theorem for the uniformity seminorms associated with the action of $$\(\backslash\)mathcal{F}\^\(\backslash\)omega$$ , submitted, 2009. · Zbl 1189.37007
[3]	G. A. Freiman: Foundations of a structural theory of set addition, by G. A. Freiman, American Mathematical Society, Providence, R.I., 1973.
[4]	W. T. Gowers: A new proof of Szemerédi’s theorem for arithmetic progressions of length four, GAFA, Geom. funct. anal. 8 (1998), 529–551. · Zbl 0907.11005 · doi:10.1007/s000390050065
[5]	B. Green and I. Z. Ruzsa: Sets with small sumset and rectification, Bulletin of the London Mathematical Society 38 (2006), 43–52. · Zbl 1155.11307 · doi:10.1112/S0024609305018102
[6]	B. Green: Finite field models in additive combinatorics, London Math. Soc. Lecture Note Ser., 327 (2005), 1–27. · Zbl 1155.11306
[7]	B. Green and T. Tao: The distribution of polynomials over finite fields, with applications to the Gowers norms, submitted, 2007.
[8]	B. Green and T. Tao: An inverse theorem for the Gowers U 3 norm, Proc. Edinburgh Math. Soc. 51 (2008), 73–153. · Zbl 1202.11013 · doi:10.1017/S0013091505000325
[9]	B. Green and T. Tao: A note on the Freiman and Balog-Szemerédi-Gowers theorems in finite fields, J. Aust. Math. Soc., 86 (2009), 61–74. · Zbl 1232.11014 · doi:10.1017/S1446788708000359
[10]	B. Green and T. Tao: An equivalence between inverse sumset theorems and inverse conjectures for the U 3-norm, Math. Proc. Camb. Phil. Soc. 149 (2010), 1–19. · Zbl 1229.11132 · doi:10.1017/S0305004110000186
[11]	B. Green and T. Tao: Freiman’s theorem in finite fields via extremal set theory, Comb. Probab. Comput. 18 (2009), 335–355. · Zbl 1254.11093 · doi:10.1017/S0963548309009821
[12]	S. Lovett, R. Meshulam and A. Samorodnitsky: Inverse conjecture for the Gowers norm is false, In: Proceedings of the 40 th annual ACM symposium on Theory of computing (STOC’ 08), 547–556, New York, NY, USA, 2008. ACM. · Zbl 1225.11158
[13]	I. Z. Ruzsa: An analog of Freiman’s theorem in groups, Structure Theory of Set-Addition, Astérique 258 (1999), 323–326. · Zbl 0946.11007
[14]	A. Samorodnitsky: Low-degree tests at large distances, In: Proceedings of the 39th annual ACM symposium on Theory of computing (STOC’ 07), 506–515, New York, NY, USA, 2007. ACM. · Zbl 1232.68175
[15]	T. Sanders: A note on Freiman’s theorem in vector spaces, Comb. Probab. Comput. 17 (2008), 297–305. · Zbl 1151.15003
[16]	T. Tao and T. Ziegler: The inverse conjecture for the Gowers norm over finite fields via the correspondence principle, Analysis and PDE 3 (2010), 1–20. · Zbl 1252.11012 · doi:10.2140/apde.2010.3.1