Recently, I had tentatively announced a forthcoming result with Ben Green establishing the “Gowers inverse conjecture” (or more accurately, the “inverse conjecture for the Gowers uniformity norm”) for vector spaces over a finite field , in the special case when p=2 and when the function for which the inverse conjecture is to be applied is assumed to be a polynomial phase of bounded degree (thus , where is a polynomial of some degree ). See my FOCS article for some further discussion of this conjecture, which has applications to both polynomiality testing and to various structural decompositions involving the Gowers norm.

This conjecture can be informally stated as follows. By iterating the obvious fact that the derivative of a polynomial of degree at most d is a polynomial of degree at most d-1, we see that a function is a polynomial of degree at most d if and only if

for all . From this one can deduce that a function bounded in magnitude by 1 is a polynomial phase of degree at most d if and only if the *Gowers norm*

is equal to its maximal value of 1. The inverse conjecture for the Gowers norm, in its usual formulation, says that, more generally, if a function bounded in magnitude by 1 has large Gowers norm (e.g. ) then f has some non-trivial correlation with some polynomial phase g (e.g. for some ). Informally, this conjecture asserts that if a function has biased derivatives, then one should be able to “integrate” this bias and conclude that the function is biased relative to a polynomial of degree d. The conjecture has already been proven for . There are analogues of this conjecture for cyclic groups which are of relevance to Szemerédi’s theorem and to counting linear patterns in primes, but I will not discuss those here.

At the time of the announcement, our paper had not quite been fully written up. This turned out to be a little unfortunate, because soon afterwards we discovered that our arguments at one point had to go through a version of Newton’s interpolation formula, which involves a factor of d! in the denominator and so is only valid when the characteristic p of the field exceeds the degree. So our arguments in fact are only valid in the range , and in particular are rather trivial in the important case ; my previous announcement should thus be amended accordingly.

On investigating this further, we found that the conjecture as stated above is in fact false in the characteristic 2 case: specifically, the symmetric quartic polynomial defined by

(1)

has no significant correlation with any cubic polynomial, but nevertheless exhibits “pseudocubic” behaviour in the sense that its fourth derivative

(2)

(there are 16 terms in this alternating sum) is biased to be 0 (in fact, it is 0 about 9/16 of the time), basically because the above expression can be factorised as

(3)

where B is the symmetric bilinear form

.

This same example had also been discovered shortly beforehand by Lovett, Meshulam, and Samorodnitsky (private communication), who are now in the process of generalising this example to higher characteristics and higher degrees, and obtaining strong bounds on the discorrelation of these examples with lower degree polynomial phases. (On the other hand, for characteristics higher than the degree, this phenomenon does not occur; our forthcoming paper will show, for instance, that every pseudocubic quartic correlates with a genuine cubic in characteristic 5 and higher.)

It seems intuitively obvious that the quartic does not correlate with any lower degree polynomials, but sometimes there are non-obvious correlations. For instance, the first three symmetric functions

do not seem to be obviously related, but over , they turn out to obey the relationship

and as a consequence, the cubic function correlates with the linear function and the quadratic function . Indeed, if denotes the number of indices i for which , we see that are equal to 1 if and only if lies in , , and respectively.

In contrast, is equal to 1 if and only if lies in . (The pattern continues using Pascal’s triangle modulo 2, or equivalently the infinite Sierpinski gasket.) So it is clear that cannot be expressed in terms of ; but this does not yet rule out the possibility that instead correlates with some other linear, quadratic, or cubic polynomials.

The forthcoming paper of Lovett, Meshulam, and Samorodnitsky will establish quite a strong discorrelation estimate on , indeed they show that

for all cubic polynomials , where c is some positive absolute constant and is the usual normalised inner product on . I will not present that argument here (though it is fairly short); instead, I would like to discuss a very pretty argument of Alon and Beigel which uses Ramsey theory to give the weaker estimate

(4)

(actually, if one plugs in the best known bounds for Ramsey’s theorem, one gets the more precise bound of for some c > 0). [We thank Andrej Bogdanov and Emanuele Viola for drawing the Alon-Beigel argument to our attention; we had an earlier argument, using, of all things, a finite field analogue of the multidimensional Szemerédi theorem, which gave inferior bounds.]

The key idea is to use Ramsey theory to symmetrise the polynomial Q. Indeed, if the cubic polynomial Q was completely symmetric with respect to permutations of the coefficients , then it is a linear combination of , and then by explicit computation using the previously mentioned relationships between and |x|, we can verify by hand that (2) holds in these cases (in fact from the theory of random walks one soon establishes an exponential decay bound).

Now suppose that Q is symmetric modulo a linear error, thus

(5)

for some symmetric cubic and some collection of indices . Then we can symmetrise the error by the simple expedient of the pigeonhole principle: either the set A contains at least indices, or its complement contains at least m indices. Suppose for sake of argument that A contains at least m indices, and specifically the indices . Then the point is that while the linear polynomial is not symmetric with respect to interchange of all coordinates , it is at least symmetric with respect to interchange of the coordinates . If we then foliate the domain into translates of the smaller domain (by freezing the coordinates ), using the previous results towards (4) to obtain a correlation o(1) on each of these translates, and then averaging everything together using the triangle inequality to obtain (4) in the case (5).

Now consider the case when Q is symmetric modulo quadratic errors, thus

where is symmetric, E is a set of pairs or “edges” in , and L is some linear polynomial. The quadratic is not symmetric in general, but it can be symmetrised on medium-sized subspaces by an appeal to Ramsey’s theorem. If we view E as the edges of a graph G, this theorem says that for some integer m growing slowly with n (we can take , in fact), the graph G either contains a clique of size m, or an independent set of size m. Let’s say it contains a clique of size m, which without loss of generality we can take to be . Then the quadratic can be expressed as the sum of , which is symmetric with respect to permutations of , plus a remainder which is at most linear in . So if we once again foliate into translates of and use the previous results, we again recover the discorrelation estimate (4) for these polynomials. (Note that the o(1) notation for and the o(1) notation for are interchangeable, because m goes to infinity as n goes to infinity.)

Finally, we consider the general case when Q is an arbitrary cubic, thus

for some collection E of unordered triples in . One can view E as the edges of a (3-uniform) hypergraph on n vertices. It turns out that Ramsey’s theorem also extends to hypergraphs (it’s the same proof, iterated a few more times), and so once again we can locate medium-sized subspaces on which the cubic becomes symmetric, and so by appeal to the previous results we obtain (4) in full generality.

[A note for the experts: the above iterated use of Ramsey’s theorem was inefficient. It is possible to use just a single application of the 3-uniform hypergraph Ramsey theorem (and no application of the graph Ramsey theorem) to eventually end up with a correlation bound of ; details will be provided in our forthcoming paper. Of course, this is still significantly inferior to the exponential bounds that will be obtained by Lovett, Meshulam, and Samorodnitsky.]

Despite the above example, I personally believe that some form of the inverse conjecture of the Gowers norm persists. One particularly promising candidate is to replace the notion of a global polynomial by a local one (as is discussed in one of my papers with Ben). For instance, while is not a globally cubic polynomial, it turns out that it is “locally cubic” on the quadratic surface , in the sense that the fourth derivative (2) of vanishes when all sixteen points of the relevant parallelopiped lies on that quadratic surface. This is basically due to the identity that equates (2) and (3). So it seems there is still much to be investigated regarding this conjecture over finite fields…

## 7 comments

Comments feed for this article

7 November, 2007 at 1:27 pm

undergradthis is so high level… i can’t understand most of it.

terry, any way you can write some articles which could be understood by 1-st, 2-nd year undergrads?

sincerely,

jane

8 November, 2007 at 9:56 am

Terence TaoDear Jane,

You can find my non-technical articles at

http://terrytao.wordpress.com/category/non-technical/

In the immediate future, I expect the next few articles to continue to be graduate level, but I plan to write some more non-technical articles in due course.

9 November, 2007 at 7:30 am

TauberDear undergrad,

Serious mathematics is not easily understood. If you want to

write articles at the calculus level, you first need to put some

effort in setting up a problem interesting to a wide audience.

9 November, 2007 at 7:34 am

LucaHi Terry,

is a weak “local” version of the Gowers inverse conjecture known in vector spaces over a prime field? Something like for every $d,\epsilon$, there is $c(d,\epsilon)$ such that if $f : F^n \rightarrow C$is bounded and $||f||_{U^d} \geq \epsilon$ then there is a subspace $V$ of $F^n$ of dimension at least $c(d,\epsilon) n$, or maybe $n^{c(d,\epsilon)}$ and a degree $d-1$ polynomial phase function $p$ such that $f$ and $p$ are correlated over $V$.

9 November, 2007 at 12:58 pm

Ben GreenLuca,

I don’t believe we have such a result yet for d greater than or equal to 4 even when the characteristic of F is large. It is also possible that another ‘weak’ version of the IG conjecture is true, even in characteristic 2: If ||f||_{U^d} is large then f correlates with a polynomial of degree O_d(1). The recent examples of Lovett, Meshulam and Samorodnitsky and Terry and I show that one cannot take this O_d(1) to be d-1 in general.

I’m not sure we know how to prove that even if we already know that f is a polynomial phase of some very large degree. That is, if f is a polynomial phase of degree 1000 with large Gowers U^4 norm, does it correlate with a polynomial of degree 10 (or maybe even of degree 4)?

This characteristic 2 theory is turning out to be kind of intruiging.

23 November, 2007 at 5:25 pm

The distribution of polynomials over finite fields, with applications to the Gowers norms « What’s new[...] This paper, which we first announced at the recent FOCS meeting, and then gave an update on two weeks ago on this blog, is now in final form. It is being made available simultaneously with a closely related paper of [...]

1 September, 2008 at 7:51 am

The correspondence principle and finitary ergodic theory « What’s new[...] established, which by the correspondence principle alluded to above, implies Theorem 14. (See my previous blog post for some discussion of Theorem 14, which had been conjectured for a few years. Interestingly, as [...]