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$