Ben Green and I have just uploaded the paper “Freiman’s theorem in finite fields via extremal set theory” to the arXiv, which we have submitted to Combinatorics, Probability, and Computing. This paper is our third regarding various refinements of Freiman’s theorem; the first one concerned approximating a set of small doubling in a torsion-free group by a progression of really small rank using compressions and convex geometry, while the second one obtained an intersection version of Freiman’s theorem (and the Balog-Szemerédi-Gowers theorem) in the 2-torsion case using an induction-on-dimension argument. Here, we return to compressions to obtain particularly sharp bounds on Freiman’s theorem in the 2-torsion case, and in particular getting some partial results on the polynomial Freiman-Ruzsa conjecture. Specifically, we show that if A \subset {\Bbb F}_2^n has doubling constant at most K, thus |A+A| \leq K|A|, then A can be contained in an affine subspace of cardinality at most 2^{2K + O(\sqrt{K} \log K)} |A|. Except for the O() factor, this is sharp. If in addition A is a downset, we show that A can be covered by O(K^{46}) translates of a coordinate subspace of cardinality at most |A|. (The constant 46 is definitely not best possible, though we show that it cannot be lowered to below 1.46.) In particular, this settles the polynomial Freiman-Ruzsa conjecture in the case when the set is a downset.

The main ideas are to use ideas from extremal set systems theory, notably the method of compressions (as used for instance by Bollobás and Leader) and of shifts (as used for instance by Frankl). Using all this machinery, things eventually reduce to understanding sumsets of a very structured class of sets – the shift-minimal downsets – and their relationship with Hamming balls. This in turn ultimately rests on a certain “gamblers’ ruin” problem already considered by Frankl.