For every integer n ≥ 0, every real number K ≥ 1, and every nonempty set A ⊆ F_2^n satisfying | A+A| ≤ K| A|, there exist a subspace H ≤ F_2^n and elements x_1,…,x_m ∈ F_2^n such that | H| ≤ | A|, m ≤ 2K^12, and A ⊆ bigcup_i=1^m(x_i+H).

Polynomial Freiman–Ruzsa conjecture

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 $2K^{12}$ cosets. Lean formalization was completed on December 5, 2023, with no unresolved sorry statements; minor typographical issues were corrected. Jyun-Jie Liao subsequently improved the exponent from $12$ to $9$ for $\mathbb{F}_2^n$ .

Current status (as of August 2026): The stated Polynomial Freiman–Ruzsa conjecture over $\mathbb{F}_2^n$ is proved and formally verified; no open issue remains for this formulation.

Polynomial Freiman–Ruzsa conjecture

Primary source

Additional references

Progress summary

Solutions 0