One of my favourite open problems in additive combinatorics is the polynomial Freiman-Ruzsa conjecture, which Ben Green guest blogged about here some time ago.  It has many equivalent formulations (which is always a healthy sign when considering a conjecture), but here is one involving “approximate homomorphisms”:

Polynomial Freiman-Ruzsa conjecture. Let f: F_2^n \to F_2^m be a function which is an approximate homomorphism in the sense that f(x+y)-f(x)-f(y) \in S for all x,y \in F_2^n and some set S \subset F_2^m.  Then there exists a genuine homomorphism g: F_2^n \to F_2^m such that f-g takes at most O( |S|^{O(1)} ) values.

Remark 1. The key point here is that the bound on the range of f-g is at most polynomial in |S|.  An exponential bound of 2^{|S|} can be trivially established by splitting F_2^m into the subspace spanned by S (which has size at most 2^{|S|}) and some complementary subspace, and then letting g be the projection of f to that complementary subspace. \diamond

Recently, Ben Green and I have shown that this conjecture is equivalent to a certain polynomially quantitative strengthening of the inverse conjecture for the Gowers norm U^3(F_2^n); I hope to talk about this in a future post.  For this (somewhat technical) post, I want to comment on a possible further strengthening of this conjecture, namely

Strong Polynomial Freiman-Ruzsa conjecture. Let f: F_2^n \to F_2^m be a function which is an approximate homomorphism in the sense that f(x+y)-f(x)-f(y) \in S for all x,y \in F_2^n and some set S \subset F_2^m.  Then there exists a genuine homomorphism g: F_2^n \to F_2^m such that f-g takes values in the sumset CS := S + \ldots + S for some fixed C=O(1).

This conjecture is known to be true for certain types of set S (e.g. for Hamming balls, this is a result of Farah).  Unfortunately, it is false in general; the purpose of this post is to describe one counterexample (related to the failure of the inverse conjecture for the Gowers norm for U^4(F_2^n) for classical polynomials; in particular, the arguments here have several features in common with those in the papers of Lovett-Meshulam-Samorodnitsky and Green-Tao).  [A somewhat different counterexample also appears in the paper of Farah.]  The verification of the counterexample is surprisingly involved, ultimately relying on the multidimensional Szemerédi theorem of Furstenberg and Katznelson.

(The results here are derived from forthcoming joint work with Ben Green.)

— Description of counterexample —

We let n be a large number, and replace F_2^m by the \frac{n(n+1)}{2}-dimensional vector space V of quadratic forms Q: F_2^n \to F_2 (with a basis given by the monomials x_i x_j with 1 \leq i \leq j \leq n).  We let f: F_2^n \to V be defined by the formula

f(h_1,\ldots,h_n)(x_1,\ldots,x_n) := \sum_{1 \leq i < j \leq n} h_i x_i h_j x_j.

A brief computation shows that for any h, k \in F_2^n, the quadratic form f(h+k)-f(h)-f(k) is of rank at most three, by which we mean that it is a function of at most three linear forms.  More specifically, we have

f(h+k)-f(h)-f(k) = a_{h,k} b_{h,k} + b_{h,k} c_{h,k} + c_{h,k} a_{h,k} (1)

where

a_{h,k}(x) = \sum_{i=1}^n h_i(1-k_i) x_i

b_{h,k}(x) = \sum_{i=1}^n (1-h_i) k_i x_i

c_{h,k}(x) = \sum_{i=1}^n h_i k_i x_i

Thus, if we let S be the space of quadratic forms of rank at most 3, the hypotheses of the polynomial Freiman-Ruzsa conjecture hold.

— Verification of counterexample —

To establish the counterexample, we assume for contradiction that there exists a linear function g: F_2^n \to V such that f(h)-g(h) has bounded rank for all h, and deduce a contradiction (for n sufficiently large).

By hypothesis, we have linear forms L_{h,1},\ldots,L_{h,d} for all h \in F_2^n and some d = O(1) and coefficients c_{h,i,j} \in F_2 for all 1 \leq i \leq j \leq d such that

\displaystyle f(h)-g(h) = \sum_{1 \leq i \leq j \leq n} c_{h,i,j} L_{h,i} L_{h,j}

and in particular (by (1) and linearity of g)

\displaystyle a_{h,k} b_{h,k} + b_{h,k} c_{h,k} + c_{h,k} a_{h,k}

\displaystyle = \sum_{1 \leq i \leq j \leq n} c_{h+k,i,j} L_{h+k,i} L_{h+k,j} - c_{h,i,j} L_{h,i} L_{h,j} - c_{k,i,j} L_{k,i} L_{k,j}. (2)

The key point is that the linear forms a_{h,k}, b_{h,k}, c_{h,k} are usually “independent” of the linear forms L_{h,i}, L_{k,i}, L_{h+k,i}.  The key lemma in this regard is

Lemma 1. If h, k are selected uniformly and independently at random, then with probability 1-o(1), a_{h,k} is not a linear combination of the L_{h,i}, L_{k,i}, L_{h+k,i}.  Similarly for b_{h,k}, c_{h,k}.

Proof. By cyclically permuting h,k,h+k it suffices to show this for c_{h,k}.  Since there are at most O(1) possible linear combinations amongst the L_{h,i}, L_{k,i}, L_{h+k,i}, it suffices to show that for any given assignments h \mapsto L'_h, k \mapsto L''_k, h+k \mapsto L'''_{h+k} of linear forms, that the probability of the event

c_{h,k} = L'_h + L''_k + L'''_{h+k} (3)

is o(1).  Suppose for contradiction that the event (3) holds for a set E of pairs (h,k) in F_2^n \times F_2^n of positive density.  Applying the Furstenberg-Katznelson multidimensional Szemerédi theorem) we can find (for n large enough) a square (h,k), (h+r,k), (h,k+r), (h+r,k+r) in E with r non-zero.  Applying (3) for all four pairs and summing, we obtain

c_{h,k} +c_{h+r,k} + c_{h,k+r} + c_{h+r,k+r} = 0

(recall we are in characteristic 2).  But the left-hand side is equal to the linear form \sum_i r_i x_i, which is non-zero, a contradiction. \Box

Now we can obtain the desired contradiction.  For a generic choice of h,k, we now know that none of the a_{h,k}, b_{h,k}, c_{h,k} are linear combinations of the L_{h,i}, L_{k,i}, L_{h+k,i}.  Thus, on a given level set of the L_{h,i}, L_{k,i}, L_{h+k,i} (which form a subspace of F_2^n), the linear functions a_{h,k}, b_{h,k}, c_{h,k} are non-constant, and so the range of the triplet (a_{h,k}, b_{h,k}, c_{h,k}) must be an affine subspace of F_2^3 which is not contained in any plane in F_2^3 that is parallel to the two of the coordinate axes (i.e. of the form a=const, b=const, or c=const.  This forces the subspace to be parallel to (1,1,1).  But this implies that (a,b,c) \mapsto ab+bc+ca is non-constant on this space, contradicting (2).

Remark 2. The function f appearing in the above example is closely related to the symmetric polynomial

\displaystyle S_4(x) := \sum_{1 \leq i < j < k < l \leq n} x_i x_j x_k x_l.

Indeed, one can show that the derivative S_4(x+h)-S_4(x) of S_4 is equal to f(h), plus some additional terms which involve only a finite number of linear forms, and the quadratic polynomial S_2(x) := \sum_{1 \leq i < j \leq n} x_i x_j.    If it was the case that f could be approximated by a linear map g modulo low rank errors, then it one could use this to eventually show that S_4 correlated with a cubic polynomial; but it is known (from the papers of Lovett-Meshulam-Samorodnitsky and Green-Tao) that this is not the case.  Thus there is an alternate way to verify that the above example is indeed a counterexample to the strong polynomial Freiman-Ruzsa conjecture. \diamond