Marton’s conjecture (Polynomial Freiman-Ruzsa) constant

Description of constant

$C_{18}$ is the least constant such that, whenever $A$ is a subset of $\mathbb F_{2}^n$ with $\lvert A+A\rvert \leq K\lvert A\rvert$, then $A$ can be covered by $K^{C_{18}+o(1)}$ cosets of a subspace of cardinality at most $\lvert A\rvert$, where the limit $o(1)$ is with respect to the limit $K \to \infty$.

Known upper bounds

Known lower bounds

Additional comments and links

• Conjectured to be finite by Katalin Marton, as recorded in [R1999]. It is the special case of the Polynomial Freiman-Ruzsa (PFR) conjecture when the ambient group is a vector space over the field $\mathbb F_{2}$. (The precise formulation of the PFR conjecture in the case of unbounded torsion is still not fully settled.)
• The lower bound of 1 is not expected to be sharp.
• Surveys on this problem can be found at [G2005], [G-unpub], and [Lovett2015].

References

• [G2005] Green, B. J. Finite field models in additive combinatorics. In: Surveys in Combinatorics 2005, London Math. Soc. Lecture Note Series 327, Cambridge University Press, 2005, 1–27.
• [G-unpub] Green, B. J. Notes on the polynomial Freiman–Ruzsa conjecture. Unpublished note available at https://people.maths.ox.ac.uk/greenbj/papers/PFR.pdf
• [GGMT2025] Gowers, W. T.; Green, B.; Manners, F.; Tao, T. On a conjecture of Marton. Annals of Mathematics, Second Series, Volume 201 (2025), Issue 2, 515–549. arXiv:2311.05762
• [Lovett2015] Lovett, S. An Exposition of Sanders’ Quasi-Polynomial Freiman–Ruzsa Theorem. Theory of Computing Library Graduate Surveys 6 (2015), 1–14.
• [L2024] Liao, J.-J. Improved Exponent for Marton’s Conjecture in $\mathbb F_{2}^n$. arXiv:2404.09639 (2024).
• [R1999] Ruzsa, I. Z. An analog of Freiman’s theorem in groups. Astérisque 258 (1999), 323–326.