Polynomial Freiman–Ruzsa conjecture
For every integer , every real number , and every nonempty set satisfying , there exist a subspace and elements such that , , and .
References
Source: GitHub
Progress summary
Marton’s conjecture, published by Imre Ruzsa in 1999, asserts a polynomial covering bound for sets with small doubling. Tim Gowers, Ben Green, Freddie Manners, and Terence Tao proved the binary vector-space case in November 2023, exactly covering the problem stated here.
Known results
- Ruzsa, 1999: an earlier exponential-type covering bound.
- Sanders, 2012: the first almost-polynomial bound, but not a polynomial one.
November 2023 proof and April 2024 strengthening
The Gowers–Green–Manners–Tao theorem proves the stated bound with at most cosets. Jyun-Jie Liao subsequently improved the exponent from to for .
Current status (as of August 2026): The stated Polynomial Freiman–Ruzsa conjecture over is proved and formally verified; no open issue remains for this formulation.
Solutions 0
No solutions have been posted yet.