Elamur Research⌕
☰
home / papers / 2023 / On a conjecture of Marton

On a conjecture of Marton

Paper · 2023 · W. T. Gowers, Ben Green, Freddie Manners et al.

Summary

The paper settles Marton's conjecture, better known as the polynomial Freiman–Ruzsa (PFR) conjecture, for vector spaces over F₂. The conjecture says that a set A ⊂ F₂ⁿ with |A+A| ⩽ K|A| can be covered by 2K^C cosets of a subgroup no larger than A. In other words, small doubling forces subgroup-like structure, and the loss is only polynomial in K. Before this work, the best bounds were quasi-polynomial (Sanders, with a refinement by Konyagin).

The proof does not attack the combinatorial statement directly. It works with an equivalent entropic formulation, built on the entropic Ruzsa distance between random variables. The authors define a penalized distance functional and show that any pair of variables at positive distance can be replaced by a pair with a strictly smaller value. A compactness argument then yields a pair at zero distance, which must be uniform on a coset of a subgroup.

The result gives C = 12. It also unlocks several equivalent statements and applications across additive combinatorics and theoretical computer science.

Key points

  • Main result: Theorem 1.2 proves the conjecture with C = 12. A later refinement by Jyun-Jie Liao lowers this to C = 11. The previous record was a bound of shape exp(log^{3+ε} K) (Konyagin's variant of Sanders' method).
  • Entropic version (Theorem 1.8): in this version, the subgroup H found by the proof satisfies d[X₁⁰;U_H] + d[X₂⁰;U_H] ⩽ 11·d[X₁⁰;X₂⁰]. The argument runs through a functional τ with penalty weight η = 1/9.
  • Consequences:
    • the weak PFR conjecture over Z^D;
    • an inverse theorem for the Gowers U³ norm on F₂ⁿ with polynomial bounds;
    • polynomial bounds in linearity testing;
    • Mudgal's sum–product result for real sets.
  • Formal verification: the proof was formalized in Lean4 in about three weeks by a collaborative project (teorth.github.io/pfr).
  • Odd characteristic: the method extends to F_p for odd p, with details deferred to a separate paper. The polynomial Bogolyubov conjecture and the strong PFR conjecture over Z remain open.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of CambridgeCambridge · United Kingdom287 works · 125,174 citations🎓University of OxfordOxford · United Kingdom138 works · 161,448 citations🎓University of California, Los AngelesLos Angeles · United States110 works · 58,035 citations🎓University of California San DiegoSan Diego · United States101 works · 54,571 citations🎓Collège de FranceParis · France4 works · 65 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Mathematics · 233 worksAlgebra and Number Theory · 2 worksDiscrete Mathematics and Combinatorics · 1 work

Cite

Cite as W. T. Gowers, Ben Green, Freddie Manners and Terence Tao. 2023. On a conjecture of Marton. arXiv:2311.05762.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2311.05762 · arXiv 2311.05762

@misc{gowers2023conjecture,
  title = {{On a conjecture of Marton}},
  author = {W. T. Gowers, Ben Green, Freddie Manners and Terence Tao},
  year = {2023},
  doi = {10.48550/arxiv.2311.05762},
  eprint = {2311.05762},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2311.05762}
}

References

19 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. J. Aaronson, A counterexample to a strong variant of the polynomial Freiman– Ruzsa conjecture, preprint available at https://arxiv.org/abs/1902.00353 — [arXiv:1902.00353](https://arxiv.org/abs/1902.00353) ↗
  2. J. Bourgain and M.- C. Chang, On the size of k-fold sum and product sets of integers, J. Amer. Math. Soc. 17 (2004), no. 2, 473–497. find
  3. M. C. Chang, Some consequences of the polynomial Freiman–Ruzsa conjecture, C. R. Math. Acad. Sci. Paris 347 (2009), no.11–12, 583–588. find
  4. H. Diao, Freiman–Ruzsa-type theory for small doubling constant, Math. Proc. Cambridge Philos. Soc. 146 (2009), no.2, 269–276. find
  5. C. Even-Zohar, On sums of generating sets in Z n 2 , Combin. Probab. Comput. 21 (2012), no. 6, 916–941. find
  6. W. T. Gowers, B. J. Green, F. R. W. M. Manners and T. C. Tao, The polynomial Freiman–Ruzsa conjecture in odd characteristic, manuscript. find
  7. B. J. Green, Finite field models in additive combinatorics, in Surveys in Combinatorics 2005 London Math. Soc. Lecture Notes 327, 1–27. , Notes on the polynomial Freiman–Ruzsa conjecture, unpublished note find
  8. available at https://people.maths.ox.ac.uk/greenbj/papers/PFR.pdf ↗
  9. B. J. Green, T. C. Tao, Freiman’s theorem in finite fields via extremal set theory, Combin. Probab. Comput. 18 (2009), 335–355. find
  10. , An equivalence between inverse sumset theorems and inverse conjectures for the U 3 norm, Math. Proc. Cambridge Philos. Soc. 149 (2010), no.1, 1–19. find
  11. B. J. Green, F. R. W. M. Manners and T. C. Tao, Sumsets and entropy revisited, preprint available at https://arxiv.org/abs/2306.13403 — [arXiv:2306.13403](https://arxiv.org/abs/2306.13403) ↗
  12. K. Hosseini, S. Lovett, A bilinear Bogolyubov–Ruzsa lemma with polylogarithmic bounds, Discrete Anal. 2019 (2019), Paper No. 10, 14 pp. find
  13. V. A. Kaimanovich and A. M. Vershik, Random walks on discrete groups: boundary and entropy, Ann. Probab. 11 (1983), no. 3, 457–490. find
  14. N. H. Katz and P. Koester, On additive doubling and energy, SIAM J. Discrete Math. 24 (2010), no. 4, 1684–1693. find
  15. P. Keevash and N. Lifshitz, Sharp hypercontractivity for symmetric groups and its applications, preprint available at https://arxiv.org/abs/2307.15030. — [arXiv:2307.15030](https://arxiv.org/abs/2307.15030) ↗
  16. S. Konyagin, On the Freiman theorem in finite fields, Math. Notes 84 (2008), 435–438. find
  17. J. Liao, comment available at https://terrytao.wordpress.com/2023/11/13/on-a-conjecture-of-mart ↗
  18. S. Lovett, Equivalence of polynomial conjectures in additive combinatorics, Combinatorica 32 (2012), no. 5, 607–618. \#\# 32 W. T. GOWERS, BEN GREEN, FREDDIE MANNERS, AND TERENCE TAO , An Exposition of Sanders’ Quasi-Polynomial Freiman–Ruzsa Theorem, Theory of Computing Library Graduate Surveys 6 (201… — [arXiv:2308.04191](https://arxiv.org/abs/2308.04191) find
  19. ON A CONJECTURE OF MARTON Collège de France, 11, place Marcelin-Berthelot, 75231 Paris 05, France, and Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, UK Email address: wtg10@dpmms.cam.ac.uk Mathematical Institute, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodsto… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/gowers-2023-conjecture-marton/