---
title: "On a conjecture of Marton — paper by Gowers et al. (2023)"
description: "The authors define a penalized distance functional and show that any pair of variables at positive… 19 references, cited by 6 papers here."
authors: ["W. T. Gowers", "Ben Green", "Freddie Manners", "Terence Tao"]
year: 2023
venue: "arXiv:2311.05762"
source: "https://arxiv.org/abs/2311.05762"
doi: "10.48550/arxiv.2311.05762"
arxiv: "2311.05762"
licence: "CC BY 4.0 (arXiv)"
licence_url: "http://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/gowers-2023-conjecture-marton/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/gowers-2023-conjecture-marton/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2023](https://md.research.elamur.ai/free/en/papers/2023/page/13/) / On a conjecture of Marton

# On a conjecture of Marton

**Authors:** W. T. Gowers, Ben Green, Freddie Manners and [Terence Tao](https://md.research.elamur.ai/free/en/authors/terence-tao/) · **Year:** 2023 · **Venue:** arXiv:2311.05762 · **Licence:** [CC BY 4.0 (arXiv)](http://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/2311.05762) · [PDF](https://arxiv.org/pdf/2311.05762) · [DOI 10.48550/arxiv.2311.05762](https://doi.org/10.48550/arxiv.2311.05762) · [arXiv 2311.05762](https://arxiv.org/abs/2311.05762) · [OpenAlex](https://openalex.org/W4408419148)

**Citations:** 15 citations (OpenAlex, 2026-10-14) · [6](https://md.research.elamur.ai/free/en/papers/gowers-2023-conjecture-marton/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## 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 Cambridge](https://md.research.elamur.ai/free/en/universities/university-of-cambridge/) — University, Cambridge, United Kingdom · 287 works · 125,174 citations
- [University of Oxford](https://md.research.elamur.ai/free/en/universities/university-of-oxford/) — University, Oxford, United Kingdom · 138 works · 161,448 citations
- [University of California, Los Angeles](https://md.research.elamur.ai/free/en/universities/university-of-california-los-angeles/) — University, Los Angeles, United States · 110 works · 58,034 citations
- [University of California San Diego](https://md.research.elamur.ai/free/en/universities/university-of-california-san-diego/) — University, San Diego, United States · 101 works · 54,571 citations
- [Collège de France](https://md.research.elamur.ai/free/en/universities/college-de-france/) — University, Paris, France · 4 works · 65 citations

📚 Shelves (3): [➗ Mathematics](https://md.research.elamur.ai/free/en/shelves/mathematics/) · 233 works · [➗ Algebra and Number Theory](https://md.research.elamur.ai/free/en/shelves/mathematics/algebra-and-number-theory/) · 2 works · [➗ Discrete Mathematics and Combinatorics](https://md.research.elamur.ai/free/en/shelves/mathematics/discrete-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.

```bibtex
@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}
}
```

- [← previous ModuleFormer: Modularity Emerges from Mixture-of-Experts](https://md.research.elamur.ai/free/en/papers/shen-2023-moduleformer-modularity-emerges-mixture-experts/)
- [next → TRIGO: Benchmarking Formal Mathematical Proof Reduction for Generative Language Models](https://md.research.elamur.ai/free/en/papers/xiong-2023-trigo-benchmarking-formal-mathematical-proof/)
- [↑ back to papers of 2023](https://md.research.elamur.ai/free/en/papers/2023/page/13/)

## 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) [↗](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](https://scholar.google.com/scholar?q=J%2E+Bourgain+and+M%2E%2D+C%2E+Chang%2C+On+the+size+of+k%2Dfold+sum+and+product+sets+of+integers%2C+J%2E+Amer%2E+Math%2E+Soc%2E+17+%282004%29%2C+no%2E+2%2C+473%E2%80%93497%2E)
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](https://scholar.google.com/scholar?q=M%2E+C%2E+Chang%2C+Some+consequences+of+the+polynomial+Freiman%E2%80%93Ruzsa+conjecture%2C+C%2E+R%2E+Math%2E+Acad%2E+Sci%2E+Paris+347+%282009%29%2C+no%2E11%E2%80%9312%2C+583%E2%80%93588%2E)
4. H. Diao, Freiman–Ruzsa-type theory for small doubling constant, Math. Proc. Cambridge Philos. Soc. 146 (2009), no.2, 269–276. [find](https://scholar.google.com/scholar?q=H%2E+Diao%2C+Freiman%E2%80%93Ruzsa%2Dtype+theory+for+small+doubling+constant%2C+Math%2E+Proc%2E+Cambridge+Philos%2E+Soc%2E+146+%282009%29%2C+no%2E2%2C+269%E2%80%93276%2E)
5. C. Even-Zohar, On sums of generating sets in Z n 2 , Combin. Probab. Comput. 21 (2012), no. 6, 916–941. [find](https://scholar.google.com/scholar?q=C%2E+Even%2DZohar%2C+On+sums+of+generating+sets+in+Z+n+2+%2C+Combin%2E+Probab%2E+Comput%2E+21+%282012%29%2C+no%2E+6%2C+916%E2%80%93941%2E)
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](https://scholar.google.com/scholar?q=W%2E+T%2E+Gowers%2C+B%2E+J%2E+Green%2C+F%2E+R%2E+W%2E+M%2E+Manners+and+T%2E+C%2E+Tao%2C+The+polynomial+Freiman%E2%80%93Ruzsa+conjecture+in+odd+characteristic%2C+manuscript%2E)
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](https://scholar.google.com/scholar?q=B%2E+J%2E+Green%2C+Finite+field+models+in+additive+combinatorics%2C+in+Surveys+in+Combinatorics+2005+London+Math%2E+Soc%2E+Lecture+Notes+327%2C+1%E2%80%9327%2E+%2C+Notes+on+the+polynomial+Freiman%E2%80%93Ruzsa+conjecture%2C+unpublished+)
8. available at [https://people.maths.ox.ac.uk/greenbj/papers/PFR.pdf](https://people.maths.ox.ac.uk/greenbj/papers/PFR.pdf) [↗](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](https://scholar.google.com/scholar?q=B%2E+J%2E+Green%2C+T%2E+C%2E+Tao%2C+Freiman%E2%80%99s+theorem+in+finite+fields+via+extremal+set+theory%2C+Combin%2E+Probab%2E+Comput%2E+18+%282009%29%2C+335%E2%80%93355%2E)
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](https://scholar.google.com/scholar?q=%2C+An+equivalence+between+inverse+sumset+theorems+and+inverse+conjectures+for+the+U+3+norm%2C+Math%2E+Proc%2E+Cambridge+Philos%2E+Soc%2E+149+%282010%29%2C+no%2E1%2C+1%E2%80%9319%2E)
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) [↗](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](https://scholar.google.com/scholar?q=K%2E+Hosseini%2C+S%2E+Lovett%2C+A+bilinear+Bogolyubov%E2%80%93Ruzsa+lemma+with+polylogarithmic+bounds%2C+Discrete+Anal%2E+2019+%282019%29%2C+Paper+No%2E+10%2C+14+pp%2E)
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](https://scholar.google.com/scholar?q=V%2E+A%2E+Kaimanovich+and+A%2E+M%2E+Vershik%2C+Random+walks+on+discrete+groups%3A+boundary+and+entropy%2C+Ann%2E+Probab%2E+11+%281983%29%2C+no%2E+3%2C+457%E2%80%93490%2E)
14. N. H. Katz and P. Koester, On additive doubling and energy, SIAM J. Discrete Math. 24 (2010), no. 4, 1684–1693. [find](https://scholar.google.com/scholar?q=N%2E+H%2E+Katz+and+P%2E+Koester%2C+On+additive+doubling+and+energy%2C+SIAM+J%2E+Discrete+Math%2E+24+%282010%29%2C+no%2E+4%2C+1684%E2%80%931693%2E)
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) [↗](https://arxiv.org/abs/2307.15030)
16. S. Konyagin, On the Freiman theorem in finite fields, Math. Notes 84 (2008), 435–438. [find](https://scholar.google.com/scholar?q=S%2E+Konyagin%2C+On+the+Freiman+theorem+in+finite+fields%2C+Math%2E+Notes+84+%282008%29%2C+435%E2%80%93438%2E)
17. J. Liao, comment available at [https://terrytao.wordpress.com/2023/11/13/on-a-conjecture-of-mart](https://terrytao.wordpress.com/2023/11/13/on-a-conjecture-of-mart) [↗](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](https://scholar.google.com/scholar?q=S%2E+Lovett%2C+Equivalence+of+polynomial+conjectures+in+additive+combinatorics%2C+Combinatorica+32+%282012%29%2C+no%2E+5%2C+607%E2%80%93618%2E+%5C%23%5C%23+32+W%2E+T%2E+GOWERS%2C+BEN+GREEN%2C+FREDDIE+MANNERS%2C+AND+TERENCE+TAO+%2C+An+Exposition+o)
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](https://scholar.google.com/scholar?q=ON+A+CONJECTURE+OF+MARTON+Colle%CC%80ge+de+France%2C+11%2C+place+Marcelin%2DBerthelot%2C+75231+Paris+05%2C+France%2C+and+Centre+for+Mathematical+Sciences%2C+Wilberforce+Road%2C+Cambridge+CB3+0WB%2C+UK+Email+address%3A+wtg10%40d)

*Updated 3 November 2026*