Marton’s “Polynomial Freiman-Ruzsa” Conjecture was Settled by Tim Gowers, Ben Green, Freddie Manners and Terry Tao

Gowers, Green, Manners and Tao. They reminded me of the A-team of the 1980s television series: “If you have a problem, if no one else can help, and if you can find them, maybe you can hire… the A-Team.”

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 is a set with . Then is covered by at most cosets of some subgroup of size at most . In fact, we can take .

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.) Updates: For more background and for some ideas of the proof see this post in Terry Tao’s blog. A subsequent post on Terry Tao’s blog describes a project for formalizing the proof using Lean.

Famously, Ruzsa proved the assertion of the theorem with exponential bound () and in a major breakthrough Tom Sanders proved a quasi-polynomial upper bound . 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.

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