For a number of reasons, including the start of the summer break for me and my coauthors, a number of papers that we have been working on are being released this week.  For instance, Ben Green and I have just uploaded to the arXiv our paper “An equivalence between inverse sumset theorems and inverse conjectures for the U^3 norm“, submitted to Math. Proc. Camb. Phil. Soc..  The main result of this short paper (which was briefly announced in this earlier post) is a connection between two types of inverse theorems in additive combinatorics, namely the inverse sumset theorems of Freiman type, and inverse theorems for the Gowers uniformity norm, and more specifically, for the U^3 norm

\|f\|_{U^3(G)}^8 := {\Bbb E}_{x,a,b,c \in G} f(x) \overline{f(x+a)} \overline{f(x+b)} \overline{f(x+c)} f(x+a+b) f(x+a+c) f(x+b+c) \overline{f(x+a+b+c)}

on finite additive group G, where f: G \to {\Bbb C} is a complex-valued function.

As usual, the connection is easiest to state in a finite field model such as G = {\Bbb F}_2^n.  In this case, we have the following inverse sumset theorem of Ruzsa:

Theorem 1. If A \subset {\Bbb F}_2^n is such that |A+A| \leq K|A|, then A can be covered by a translate of a subspace of {\Bbb F}_2^n of cardinality at most K^2 2^{K^4} |A|.

The constant K^2 2^{K^4} has been improved for large K in a sequence of papers, from K 2^{\lfloor K^3 \rfloor-1} by Ruzsa, K^2 2^{K^2-2} by Green-Ruzsa, 2^{O(K^{3/2} \log(1+K)} by Sanders, 2^{2K+O(\sqrt{K} \log K}) by Green and myself, and finally 2^{2K+O(\log K)} by Konyagin (private communication) which is sharp except for the precise value of the O() implied constant (as can be seen by considering the example when A consists of about 2K independent elements).  However, it is conjectured that the polynomial loss can be removed entirely if one modifies the conclusion slightly:

Conjecture 1. (Polynomial Freiman-Ruzsa conjecture for {\Bbb F}_2^n.) If A \subset {\Bbb F}_2^n is such that |A+A| \leq K|A|, then A can be covered by O(K^{O(1)}) translates of subspaces of {\Bbb F}_2^n of cardinality at most |A|.

This conjecture was verified for downsets by Green and myself, but is open in general.   This conjecture has a number of equivalent formulations; see this paper of Green for more discussion.  In this previous post we show that a stronger version of this conjecture fails.

Meanwhile, for the Gowers norm, we have the following inverse theorem, due to Samorodnitsky:

Theorem 2. Let f: {\Bbb F}_2^n \to [-1,1] be a function whose U^3 norm is at least 1/K.  Then there exists a quadratic polynomial Q: {\Bbb F}_2^n \to {\Bbb F}_2 such that |{\Bbb E}_{x \in {\Bbb F}_2^n} f(x) (-1)^{Q(x)}| \geq \exp( - O(K)^{O(1)} ).

Note that the quadratic phases (-1)^{Q(x)} are the only functions taking values in [-1,1] whose U^3 norm attains its maximal value of 1.

It is conjectured that the exponentially weak correlation here can be strengthened to a polynomial one:

Conjecture 2. (Polynomial inverse conjecture for the U^3({\Bbb F}_2^n) norm). Let f: {\Bbb F}_2^n \to [-1,1] be a function whose U^3 norm is at least 1/K.  Then there exists a quadratic polynomial Q: {\Bbb F}_2^n \to {\Bbb F}_2 such that |{\Bbb E}_{x \in {\Bbb F}_2^n} f(x) (-1)^{Q(x)}| \geq K^{-O(1)}.

The first main result of this paper is

Theorem 3. Conjecture 1 and Conjecture 2 are equivalent.

This result was also independently observed by Shachar Lovett (private communication).  We also establish an analogous result for the cyclic group {\Bbb Z}/N{\Bbb Z}, in which the notion of polynomial is replaced by that of a subexponential \exp(K^{o(1)}), and in which the notion of a quadratic polynomial is replaced by a 2-step nilsequence; the precise statement is a bit technical and will not be given here.  We also observe a partial partial analogue of the correpsondence between inverse sumset theorems and Gowers norms in the higher order case, in particular observing that U^4 inverse theorems imply a certain rigidity result for “Freiman-quadratic polynomials” (a quadratic version of Conjecture 3 below).

Below the fold, we sketch the proof of Theorem 3.

The deduction of Conjecture 2 from Conjecture 1 is already implicit in the work of Samorodnitsky, so we focus here on the converse implication.  It is convenient to put Conjecture 1 in the following equivalent form:

Conjecture 3. (Polynomial rigidity of Freiman homomorphisms) Let S \subset {\Bbb F}_2^m have density \sigma, and let \phi: S \to {\Bbb F}_2^N be a Freiman homomorphism, thus \phi(x)+\phi(y) = \phi(z)+\phi(w) whenever x,y,z,w \in S are such that x+y=z+w.  Then there exists an affine-linear map \psi: {\Bbb F}_2^m \to {\Bbb F}_2^N which agrees with \phi on at least \gg \sigma^{-O(1)} 2^m elements of {\Bbb F}_2^m.

The implication of Conjecture 1 from Conjecture 3 was observed by Ruzsa; basically, the idea is to use the random projection trick (cf. this post) to view the set A in Conjecture 1 as a graph of a function \phi over a base {\Bbb F}_2^m of cardinality roughly comparable to |A|.

To deduce Conjecture 3 from Conjecture 2, we encode the Freiman homomorphism \phi as a function f: {\Bbb F}_2^m \times {\Bbb F}_2^N \to \{-1,+1\}, defined by the formula

f(x,y) := 1_S(x) (-1)^{\phi(x) \cdot y},

thus f is the vertical Fourier transform of the graph of \phi.  A Fourier-analytic computation using the Freiman homomorphism property of \phiand some standard applications of the Cauchy-Schwartz inequality shows that f has a large U^3 norm (of size at least \sigma, in fact).  Applying Conjecture 2, we conclude that f must polynomially correlate with some quadratic function \Psi: {\Bbb F}_2^m \times {\Bbb F}_2^N.  Separating the x and y coordinates, this implies that for a polynomially dense set of values of x, the linear phase (-1)^{\phi(x) \cdot y} in y has polynomial correlation with a quadratic polynomial (-1)^{\Psi(0,y) + \psi(x) \cdot y}, where \psi: {\Bbb F}_2^m \to {\Bbb F}_2^N is affine-linear and \Psi is some quadratic polynomial on {\Bbb F}_2^N which is independent of x.  To put it another way, (-1)^{\Psi(0,y)} has a polynomially large Fourier coefficient at \phi(x)-\psi(x) for many x.  But Plancherel’s theorem shows that there can only be polynomially many such large Fourier coefficients, so by the pigeonhole principle, \phi(x)-\psi(x) is equal to a constant for a polynomially dense set of x, and the claim follows.