[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|.

Various equivalent formulations of this may be found in my survey article referenced above. They are all due to Imre Ruzsa and here is one I find particularly tantalising: suppose that f : {\Bbb F}_2^n \to {\Bbb F}_2^n is a function such that the size of the set \{f(x+y) - f(x) - f(y): x,y \in {\Bbb F}_2^n\} is at most K. Then f can be written as g + h, where g is linear and the cardinality |h({\Bbb F}_2^n)| of the image of h is bounded by a polynomial in K. It is fairly clear that h can be made at most 2^K; simply define f on the basis vectors and extend linearly. Now I come to think of it, for this variant of the problem I’m not sure a bound much better than 2^K is known at all.

The main open problem in the area is to prove the PFR. There are two other groups of problems which might be highlighted here:

  1. Generalising the PFR to other groups. Even for the group \Bbb Z, there is some controversy about the statement of PFR. I’d be happy enough to
    formulate the following conjecture: If the doubling of A is at most K then there is a convex body P of dimension O(\log K) and volume at most |A|
    together with an affine map \phi : P \to {\Bbb Z} such that A lies in the union of at most K^C translates of A.It may be that some slightly technical “roundness” condition on P is desirable for applications. It is not clear at present whether P can be
    taken to be a box; this seems to involve some rather tricky geometry of numbers issues though one suspects the answer may be “no”.
  2. Applications. The PFR seems to be the key to unlocking the relationship between combinatorial and algebraic structure. But what applications does
    it have? It could be very helpful in the theory of sum-product estimates; I know for example that it easily implies a (very difficult) result of
    Bourgain and Chang     which states that \hbox{max}( |kA|, |A^k| ) \gg |A|^{f(k)}, where f(k) tends to infinity with k. Could it be helpful with, say, Waring’s problem? If the k^{th} powers A are not a basis of small order then the iterated sumset (i+1)A must be closer than one expects to iA, for some i. One might then hope to show that the k^{th} powers have some kind of weak algebraic structure, a possibility which could be eliminated by other (number-theoretical means). I don’t have any idea how to do either part of this at the moment.
  3. Another possible application might be to the following very nice question: If A is a set of square numbers, is |A+A| \gg |A|^{1+c} for some positive c? Again, one could use PFR to show that if this is not the case then there is a set of squares with high density on a “grid” (image of a convex body). One might then hope to adapt techniques of Bombieri, Zannier, Granville and Pintz which showed that squares cannot concentrate overly much on a progression. I particularly like this question because it seems very closely related to a lovely question of Rudin: Are the squares \{ n^2: n \in {\Bbb N}\} a \Lambda(p) set for some p less than 4? I refer the reader to Bourgain’s survey article on \Lambda(p) sets for more information.