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 {\Bbb F}_p^n over a finite field {\Bbb F}_p, in the special case when p=2 and when the function f: {\Bbb F}_p^n \to {\Bbb C} for which the inverse conjecture is to be applied is assumed to be a polynomial phase of bounded degree (thus f= e^{2\pi i P/|{\Bbb F}|}, where P: {\Bbb F}_p^n \to {\Bbb F}_p is a polynomial of some degree d=O(1)). 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 P: {\Bbb F}_p^n \to {\Bbb F}_p is a polynomial of degree at most d if and only if

\sum_{\omega_1,\ldots,\omega_{d+1} \in \{0,1\}} (-1)^{\omega_1+\ldots+\omega_{d+1}} P(x +\omega_1 h_1 + \ldots + \omega_{d+1} h_{d+1}) = 0

for all x,h_1,\ldots,h_{d+1} \in {\Bbb F}_p^n. From this one can deduce that a function f: {\Bbb F}_p^n \to {\Bbb C} bounded in magnitude by 1 is a polynomial phase of degree at most d if and only if the Gowers norm

\|f\|_{U^{d+1}({\Bbb F}_p^n)} := \bigl( {\Bbb E}_{x,h_1,\ldots,h_{d+1} \in {\Bbb F}_p^n} \prod_{\omega_1,\ldots,\omega_{d+1} \in \{0,1\}}

{\mathcal C}^{\omega_1+\ldots+\omega_{d+1}} f(x + \omega_1 h_1 + \ldots + \omega_{d+1} h_{d+1}) \bigr)^{1/2^{d+1}}

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 f: {\Bbb F}_p^n \to {\Bbb C} bounded in magnitude by 1 has large Gowers norm (e.g. \|f\|_{U^{d+1}} \geq \varepsilon) then f has some non-trivial correlation with some polynomial phase g (e.g. \langle f, g \rangle > c(\varepsilon) for some c(\varepsilon) > 0). Informally, this conjecture asserts that if a function has biased (d+1)^{th} 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 d \leq 2. 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 p > d, and in particular are rather trivial in the important case p=2; 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 S_4: {\Bbb F}_2^n \to {\Bbb F}_2 defined by

S_4(x_1,\ldots,x_n) := \sum_{1 \leq i < j < k < l \leq n} x_i x_j x_k x_l (1)

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

S_4(x+a+b+c+d)-S_4(x+a+b+c)-\ldots - S_4(x+d) + S_4(x) (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

B(a,b) B(c,d) + B(a,d) B(b,c) + B(a,c) B(b,d) (3)

where B is the symmetric bilinear form

B(a,b) := \sum_{1 \leq i < j \leq n} a_i b_j + a_j b_i.

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 S_4 does not correlate with any lower degree polynomials, but sometimes there are non-obvious correlations. For instance, the first three symmetric functions

S_1(x_1,\ldots,x_n) := \sum_{1 \leq i \leq n} x_i

S_2(x_1,\ldots,x_n) := \sum_{1 \leq i < j \leq n} x_i x_j

S_3(x_1,\ldots,x_n) := \sum_{1 \leq i < j < k \leq n} x_i x_j x_k

do not seem to be obviously related, but over {\Bbb F}_2, they turn out to obey the relationship

S_3 = S_1 S_2

and as a consequence, the cubic function S_3 correlates with the linear function S_1 and the quadratic function S_2. Indeed, if |x| denotes the number of indices i for which x_i=1, we see that S_1, S_2, S_3 are equal to 1 if and only if |x| \hbox{ mod } 4 lies in \{1,3\}, \{2,3\}, and \{3\} respectively.

In contrast, S_4 is equal to 1 if and only if |x| \hbox{ mod } 8 lies in \{4,5,6,7\}. (The pattern continues using Pascal’s triangle modulo 2, or equivalently the infinite Sierpinski gasket.) So it is clear that S_4 cannot be expressed in terms of S_1, S_2, S_3; but this does not yet rule out the possibility that S_4 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 S_4, indeed they show that

\langle (-1)^{S_4}, (-1)^{Q} \rangle = O( 2^{-cn} )

for all cubic polynomials Q: {\Bbb F}_2^n \to {\Bbb F}_2, where c is some positive absolute constant and \langle, \rangle is the usual normalised inner product on {\Bbb F}_2^n. 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

\langle (-1)^{S_4}, (-1)^{Q} \rangle = o(1) (4)

(actually, if one plugs in the best known bounds for Ramsey’s theorem, one gets the more precise bound of O( 1 / \log n ) 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 x_1,\ldots,x_n, then it is a linear combination of S_1, S_2, S_3, and then by explicit computation using the previously mentioned relationships between S_1(x), S_2(x), S_3(x), S_4(x) 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

Q(x) = Q_s(x) + \sum_{i \in A} x_i (5)

for some symmetric cubic Q_s and some collection of indices A \subset \{1,\ldots,n\}. Then we can symmetrise the error \sum_{i \in A} x_i by the simple expedient of the pigeonhole principle: either the set A contains at least m := \lfloor n/2 \rfloor 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 \{1,\ldots,m\}. Then the point is that while the linear polynomial \sum_{i \in A} x_i is not symmetric with respect to interchange of all coordinates x_1,\ldots,x_n, it is at least symmetric with respect to interchange of the coordinates x_1,\ldots,x_m. If we then foliate the domain {\Bbb F}_2^n into translates of the smaller domain {\Bbb F}_2^m (by freezing the coordinates x_{m+1},\ldots,x_n), 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

Q(x) = Q_s(x) + \sum_{\{i,j\} \in E} x_i x_j + L(x)

where Q_s is symmetric, E is a set of pairs or “edges” in \{1,\ldots,n\}, and L is some linear polynomial. The quadratic \sum_{\{i,j\} \in E} x_i x_j 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 m \sim \log n, 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 \{1,\ldots,m\}. Then the quadratic \sum_{\{i,j\} \in E} x_i x_j can be expressed as the sum of \sum_{1 \leq i < j \leq m} x_i x_j, which is symmetric with respect to permutations of x_1,\ldots,x_m, plus a remainder which is at most linear in x_1,\ldots,x_m. So if we once again foliate {\Bbb F}_2^n into translates of {\Bbb F}_2^m and use the previous results, we again recover the discorrelation estimate (4) for these polynomials. (Note that the o(1) notation for n \to \infty and the o(1) notation for m \to \infty 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

Q(x) = \sum_{\{i,j,k\} \in E} x_i x_j x_k + \hbox{ quadratic error}

for some collection E of unordered triples in \{1,\ldots,n\}. 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 \sum_{\{i,j,k\} \in E} x_i x_j x_k 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 O( 1 / \log n ); 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 S_4 is not a globally cubic polynomial, it turns out that it is “locally cubic” on the quadratic surface \{ x: S_2(x) = 0\}, in the sense that the fourth derivative (2) of S_4 vanishes when all sixteen points x, x+a, x+b, \ldots, x+a+b+c+d 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…