OpenFrontiers
Join
← Back to the index
OP-12021OpenCombinatorics

Marton's conjecture constant (PFR) (C18C_{18})

Marton's conjecture constant (PFR): determine C18C_{18} or improve its bounds; the repository records 1 (lower) and 9 (upper).

MSC 11B30 · Arithmetic combinatorics; higher degree uniformityMSC 11P70 · Inverse problems of additive number theory, including sumsets

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

C18C_{18} is the least constant such that, whenever AA is a subset of F2n\mathbb F_2^n with ∣A+A∣≤K∣A∣\lvert A+A\rvert \leq K\lvert A\rvert, then AA can be covered by KC18+o(1)K^{C_{18}+o(1)} cosets of a subspace of cardinality at most ∣A∣\lvert A\rvert, where the limit o(1)o(1) is with respect to the limit K→∞K \to \infty.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

  • Conjectured to be finite by Katalin Marton, as recorded in [R1999]. It is the special case of the Polynomial Freiman-Ruzsa (PFR) conjecture when the ambient group is a vector space over the field F2\mathbb F_2. (The precise formulation of the PFR conjecture in the case of unbounded torsion is still not fully settled.)
  • The lower bound of 1 is not expected to be sharp.
  • Surveys on this problem can be found at [G2005], [G-unpub], and [Lovett2015].

References (from the repository page)

  • [G2005] Green, B. J. Finite field models in additive combinatorics. In: Surveys in Combinatorics 2005, London Math. Soc. Lecture Note Series 327, Cambridge University Press, 2005, 1–27.
  • [G-unpub] Green, B. J. Notes on the polynomial Freiman–Ruzsa conjecture. Unpublished note available at https://people.maths.ox.ac.uk/greenbj/papers/PFR.pdf
  • [GGMT2025] Gowers, W. T.; Green, B.; Manners, F.; Tao, T. On a conjecture of Marton. Annals of Mathematics, Second Series, Volume 201 (2025), Issue 2, 515–549. arXiv:2311.05762
  • [Lovett2015] Lovett, S. An Exposition of Sanders’ Quasi-Polynomial Freiman–Ruzsa Theorem. Theory of Computing Library Graduate Surveys 6 (2015), 1–14.
  • [L2024] Liao, J.-J. Improved Exponent for Marton's Conjecture in F2n\mathbb F_2^n. arXiv:2404.09639 (2024).
  • [R1999] Ruzsa, I. Z. An analog of Freiman’s theorem in groups. Astérisque 258 (1999), 323–326.

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 1; best known upper bound 9. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
7+17=11.123…7+\sqrt{17} = 11.123\dots [GGMT2025] Usually reported as 1212
99 [L2024] A simplified argument giving 1111 is also provided

Known lower bounds

Bound Reference Comments
11 Trivial Consider KK basis vectors
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Marton's conjecture constant (PFR) ($C_{18}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.