Marton’s “Polynomial Freiman-Ruzsa” Conjecture was Settled by the A-Team.

Combinatorics and more 2023-11-13

“If you have a problem, if no one else can help, and if you can find them, maybe you can hire… the A-Team.” (The A-teams of the 1980s television series on the left. Gowers, Green, Manners and Tao on the right.)

A conjecture of Marton, widely known as “the polynomial Freiman-Ruzsa conjecture” was certainly a holy grail of additive combinatorics. (Here is a 2007 short blog post by Ben Green presenting the problem.) Tim Gowers, Ben Green, Freddie Manners and Terry Tao have now solved it over a field of characteristic 2. Congratulations! Here is the theorem

Theorem: Suppose that $A \subset F_2^n$ is a set with $|A + A| \le 6 K|A|$ . Then $A$ is covered by at most $2K^C$ cosets of some subgroup $H \subset F_2^n$ of size at most $|A|$ . In fact, we can take $C = 12$ .

A subsequent paper of the same team will contain a proof for odd characteristics. (As far as I understand the conjecture over the integers remains a challenge.)

Famously, Ruzsa proved the assertion of the theorem with exponential bound ( $2K^22^{K^4}$ ) and in a major breakthrough Tom Sanders proved a quasi-polynomial upper bound $K^{(3+\epsilon)not that I know\log K}$ . Sanders actually proved a stronger statement that he referred to as Bogolyubov-Ruzsa type result and for this statement a polynomial bound is still unknown. For a very good survey of Sanders result and some connections to theoretical computer science (going back to a paper by Samorodnitsky) see this paper by Lovett.

Let me say a few words about Kati Marton who made the conjecture early on. Marton was a Hungarian mathematician famous for her work on information theory, concentration of measure, probability theory, and ergodic theory. Let me mention Marton’s entropy formulation and new conceptual proof for Talagrand’s concentration of measure theorem. Here are also slides from a talk by Abbas El Gamal about Kati Marton and her famous short information-theoretic proof of the “Blowing up lemma”. It is only appropriate that entropy computations seem to play important role in the new proof of Marton’s conjecture.

KatiMarton

Kati Marton’s picture at the Renyi Institute, Budapest.