Main content start
Seminar

Marton's Conjecture, aka the Polynomial Freiman--Ruzsa conjecture

Speaker
Freddie Manners (UC San Diego / Google DeepMind)
Date
Thu, Oct 23 2025, 3:00pm
Location
384H
red knot logo

A function f from a finite vector space over the field on two elements to itself is linear if f(x+y) = f(x) + f(y) for all pairs (x,y). Suppose f is "a bit linear" -- say, f(x+y)=f(x)+f(y) for 1% of pairs (x,y).  What can you say about f?  Must it be closely related to an actually linear function?  If so, how closely? This question turns out to be equivalent to asking for good quantitative bounds in the Freiman--Ruzsa theorem, a foundational result in additive combinatorics.  Marton gave a formulation, equivalent to the statement above, which she conjectured should have polynomial bounds.  I will give the main ideas of the proof of this conjecture. Joint work with Timothy Gowers, Ben Green and Terence Tao.