Tag Archive

You are currently browsing the tag archive for the ‘Furstenberg-Katznelson theorem’ tag.

A counterexample to a strong polynomial Freiman-Ruzsa conjecture

9 November, 2008 in expository, math.CO | Tags: , , , | by | 6 comments

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

Read the rest of this entry »

RSS Google+ feed

  • An error has occurred; the feed is probably down. Try again later.
Follow

Get every new post delivered to your Inbox.

Join 2,333 other followers