You are currently browsing bengreen’s articles.

[This post is authored by Ben Green, who has kindly “guest blogged” this week’s “open problem of the week”. – T.]

In an earlier blog post Terry discussed Freiman’s theorem. The name of Freiman is attached to a growing body of theorems which take some rather “combinatorial” hypothesis, such that the sumset |A+A| of some set A is small, and deduce from it rather “algebraic” information (such that A is contained in a subspace or a grid).

The easiest place to talk about Freiman’s theorem is in the finite field model {\Bbb F}_2^n (see my survey article on this subject for a full discussion). Here it was shown by Ruzsa that if |A+A| is at most K |A| then A is contained in a subspace of size no more than about 2^{K^4}|A|. The exponent has been improved a few times since Ruzsa’s paper, the best result currently in print being due to Sanders, who obtains an upper bound of 2^{K^{3/2}\log K}|A|. Terry and I are in the process of writing a paper which obtains 2^{2K + o(K)}|A|, which is best possible in view of the example A := \{e_1,...,e_m\} where m := 2K + O(1); this set has doubling roughly K but is not contained in a subspace of dimension smaller than 2K.

This result has an air of finality (except for the true nature of the o(K) term, which represents an interesting open problem). This is something of an illusion, however. Even using this theorem, one loses an exponential every time one tries to transition between “combinatorial” structure and “algebraic” structure and back again. Indeed if one knows that A is contained in a subspace of size 2^{2K}|A| then the strongest assertion one can make about the doubling of A is that it is at most 2^{2K}.

The Polynomial Freiman-Ruzsa conjecture (PFR), in {\Bbb F}_2^n, hypothesises a more precise structure theorem for sets with small doubling. Using this
conjecture, one may flit back and forth between combinatorial and algebraic structure with only polynomial losses. Ruzsa attributes the conjecture to
Marton: it states that if A has doubling at most K then A is contained in the union of K^{O(1)} translates of some subspace H of size at most |A|.

Read the rest of this entry »