Mathematics Colloquium

A function $f : \mathbb{F}_2^n \to \mathbb{F}_2^n$ is linear if $f(x+y)=f(x)+f(y)$ for all pairs $(x,y)$. Now suppose $f$ is "a little bit linear" -- say, $f(x+y)=f(x)+f(y)$ for a 1% fraction 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 discuss this conjecture, and its (relatively) recent proof (joint with Timothy Gowers, Ben Green and Terence Tao).