The problem
A subset of \(\mathbb{F}_p^n\) with doubling constant \(K\) is covered by at most \(K^{O(1)}\) cosets of a subspace of size at most \(K^{O(1)}\) times the set. (Resolved 2023.)
The polynomial Freiman–Ruzsa conjecture
historicHistory & significance
Freiman's theorem (integers, 1960s–70s) says small doubling forces approximate subgroup structure; Ruzsa extended the philosophy to general groups. Marton reformulated it over \(\mathbb{F}_2^n\) with polynomial bounds — the form that resisted for decades, with Sanders (2012) reaching quasipolynomial bounds. In November 2023 Gowers–Green–Manners–Tao proved the full polynomial conjecture, with an argument Tao estimated a computer search could in principle have found but humans did find first.
Connected problems
- related The Green–Tao Theorem
More in Additive combinatorics
- same area The Cap Set Problem
- same area The Erdős–Szemerédi Sum–Product Conjecture over ℝ
References
- primaryRead the primary source →
- sourceFreiman's theorem
The resolution (human proof)
Gowers–Green–Manners–Tao (November 2023) proved that a subset of a vector space over a finite field with small doubling is covered by polynomially few cosets of a subspace of comparable size, establishing polynomial bounds in full.
Verified by curator — see the API for full claim provenance.