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 be a function which is an approximate homomorphism in the sense that for all and some set . Then there exists a genuine homomorphism such that takes at most values.
Remark 1. The key point here is that the bound on the range of is at most polynomial in |S|. An exponential bound of can be trivially established by splitting into the subspace spanned by S (which has size at most ) and some complementary subspace, and then letting g be the projection of f to that complementary subspace.
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 ; 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 be a function which is an approximate homomorphism in the sense that for all and some set . Then there exists a genuine homomorphism such that takes values in the sumset for some fixed .
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 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 by the -dimensional vector space V of quadratic forms (with a basis given by the monomials with ). We let be defined by the formula
A brief computation shows that for any , the quadratic form 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
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 such that has bounded rank for all h, and deduce a contradiction (for n sufficiently large).
By hypothesis, we have linear forms for all and some and coefficients for all such that
and in particular (by (1) and linearity of g)
The key point is that the linear forms are usually “independent” of the linear forms . 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), is not a linear combination of the . Similarly for .
Proof. By cyclically permuting h,k,h+k it suffices to show this for . Since there are at most O(1) possible linear combinations amongst the , it suffices to show that for any given assignments of linear forms, that the probability of the event
is o(1). Suppose for contradiction that the event (3) holds for a set E of pairs (h,k) in of positive density. Applying the Furstenberg-Katznelson multidimensional Szemerédi theorem) we can find (for n large enough) a square in E with r non-zero. Applying (3) for all four pairs and summing, we obtain
(recall we are in characteristic 2). But the left-hand side is equal to the linear form , which is non-zero, a contradiction.
Now we can obtain the desired contradiction. For a generic choice of h,k, we now know that none of the are linear combinations of the . Thus, on a given level set of the (which form a subspace of ), the linear functions are non-constant, and so the range of the triplet must be an affine subspace of which is not contained in any plane in that is parallel to the two of the coordinate axes (i.e. of the form , , or . This forces the subspace to be parallel to (1,1,1). But this implies that 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
Indeed, one can show that the derivative of is equal to , plus some additional terms which involve only a finite number of linear forms, and the quadratic polynomial . If it was the case that could be approximated by a linear map modulo low rank errors, then it one could use this to eventually show that 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.