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 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 norm

on finite additive group G, where is a complex-valued function.

As usual, the connection is easiest to state in a finite field model such as . In this case, we have the following inverse sumset theorem of Ruzsa:

Theorem 1.If is such that , then A can be covered by a translate of a subspace of of cardinality at most .

The constant has been improved for large in a sequence of papers, from by Ruzsa, by Green-Ruzsa, by Sanders, by Green and myself, and finally 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 .)If is such that , then A can be covered by translates of subspaces of 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 be a function whose norm is at least 1/K. Then there exists a quadratic polynomial such that .

Note that the quadratic phases are the only functions taking values in [-1,1] whose 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 norm).Let be a function whose norm is at least 1/K. Then there exists a quadratic polynomial such that .

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 , in which the notion of polynomial is replaced by that of a subexponential , 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 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 have density , and let be aFreiman homomorphism, thus whenever are such that . Then there exists an affine-linear map which agrees with on at least elements of .

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 over a base of cardinality roughly comparable to |A|.

To deduce Conjecture 3 from Conjecture 2, we encode the Freiman homomorphism as a function , defined by the formula

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

## 4 comments

Comments feed for this article

21 June, 2009 at 12:27 am

bengreenTerry,

I think Sergei Konyagin has published his nice improvement of our result about Freiman in F_2^n. It’s in a recent edition of Mat. Zametki.

Best

Ben

21 June, 2009 at 1:47 am

maxbaroiDear Professor Tao,

Out of curiosity, what is the intuition or motivation behind the Gower norms? The form of the product of the -th Gower norm is reminiscent of the formula for the cardinality of the union of finite sets, but I don’t have a grasp of what the $2^k$th-root of the average value of that product measures about a function the way I understand, say, the sup-norm measures “height.”

Thanks for any reply.

22 June, 2009 at 8:35 pm

Terence TaoDear Max,

In the model case of a phase function , the Gowers norm measures the oscillation of the derivative (or more precisely, difference) , where . So the Gowers norm is large when the derivative is small, in particular phases which are polynomial of degree at most k-1 have a large Gowers norm. In the original paper of Gowers where these norms are introduced, it is mentioned that these norms have some faint resemblance to Sobolev norms because of this connection with iterated derivatives, though the relationship is sort of inverted because the Gowers norms become _large_ rather than _small_ when the derivatives become small.

The inverse conjecture for the Gowers norm is essentially asserting that Gowers norm measures the extent to which the phase of a function behaves like a polynomial of degree <k (though in the integer case, one has to work with more technical generalisations of the concept of a polynomial, such as bracket polynomials or nilsequences).

Dear anonymous: I do not know of any serious proposal for a fractional Gowers norm. Given the discrete and combinatorial nature of these norms, the situation seems a bit different from the Sobolev norm setting, in which one can use the underlying real or complex structure to define fractional differentiation operators.

21 June, 2009 at 8:03 pm

AnonymousCan one meaningfully define U^p norms for p not an integer?