• No results found

A Review of Quadratic Fourier Analysis

2.3 True Complexity for Vector Spaces over Finite Fields

2.3.2 A Review of Quadratic Fourier Analysis

We shall now turn our attention to the main result of this chapter, which states that if L has CS-complexity at most 2 and is square-independent, then the true complexity of L is at most 1. We begin with a quick review of quadratic Fourier analysis for functions defined on Fnp. Our aim in this review is to give precise statements of the results that we use in our proof. The reader who is prepared to use quadratic Fourier analysis as a black box should then find that this chapter is self-contained.

So far in our discussion of uniformity, we have made no mention of Fourier analysis at all. However, at least for theU2-norm, there is a close connection. Letf be a complex-valued function defined on a finite Abelian group G. If γ is a character on G, the

2.3 True Complexity for Vector Spaces over Finite Fields

Fourier coefficient fb(γ) is defined to beExf(x)γ(x). The resulting Fourier transform satisfies the convolution identityf[∗g =fbbg, Parseval’s identitykfbk2 =kfk2 and the inversion formula f(x) =P

γfb(γ)γ(−x). (The second and third identities depend on the correct choice of normalization: kfk22 is defined to be Ex|f(x)|2, whereas kfbk22 is defined to be P

γ|fb(γ)|2. That is, as mentioned earlier, we take averages in G and sums in G.) It follows thatb kfk4U2 =kfkb 44, since both are equal to kf∗fk22.

It is often useful to split a function f up into a “structured” part and a uniform part. One way of doing this is to letK be the set of all charactersγ for which|fb(γ)|

is larger than some δ and to write f = f1 +f2, where f1 = P

γ∈Kfb(γ)γ(−x) and f2 =P

γ /∈Kfb(γ)γ(−x). If kfk ≤1, (as it is in many applications), then Parseval’s identity implies that |K| ≤ δ−2, and can also be used to show that kf2kU2 ≤ δ1/2. That is, K is not too large, andf2 is δ1/2-uniform.

When G is the group Fnp, the characters all have the form x 7→ ωrTx. Notice that this character is constant on all sets of the form {x: rTx = u}, and that these sets partition Fnp into p affine subspaces of codimension 1. Therefore, one can partition Fnp into at most p|K| affine subspaces of codimension |K| such that f1 is constant on each of them. This is the sense in which f1 is “highly structured”.

The basic aim of quadratic Fourier analysis is to carry out a similar decomposition for the U3-norm. That is, given a functionf, we would like to writef as a sum f1+f2, where f1 is “structured” and f2 is quadratically uniform. Now this is a stronger (in fact, much stronger) property to demand of f2, so we are forced to accept a weaker notion of structure for f1.

Obtaining any sort of structure at all is significantly harder than it is for the U2 -norm, and results in this direction are much more recent. The first steps were taken in [Gow98] and [Gow01] for the group ZN in order to give an analytic proof of Szemer´edi’s theorem. The structure of that proof was as follows: Theorem 2.3 can be used to show that if a set A is sufficiently uniform of degree k−2, then it must contain an arithmetic progression of length k. Then an argument that is fairly easy when k = 3 but much harder when k ≥ 4 can be used to show that if A is not c-uniform of degree k, then it must have “local correlation” with a function of the form ωφ(x), whereω = exp 2πi/N and φ is a polynomial of degree d. “Local” in this context means that one can partition ZN into arithmetic progressions of size Nη (for some η that depends on c and k only) on a large proportion of which one can find such a correlation.

This was strong enough to prove Szemer´edi’s theorem, but for several other applica-tions the highly local nature of the correlation is too weak. However, in the quadratic

2.3 True Complexity for Vector Spaces over Finite Fields

case, this problem has been remedied by Green and Tao [GT05a]. In this case, the obstacle to “globalizing” the argument is that a certain globally-defined bilinear form that occurs in the proof of [Gow01] is not symmetric, and thus does not allow one to define a corresponding globally-defined quadratic form. (In the context of ZN,

“global” means something like “defined on a proportional-sized Bohr set”. For Fnp

one can take it to mean “defined everywhere”.) Green and Tao discovered an in-genious “symmetry argument” that allows one to replace the bilinear form by one that is symmetric, and this allowed them to prove a quadratic structure theorem for functions with largeU3-norm that is closely analogous to the linear structure theorem that follows from conventional Fourier analysis.

An excellent exposition of this structure theorem when the groupGis a vector space over a finite field can be found in [Gre05b]. This contains proofs of all the background results that we state here.

Recall that in the linear case, we called f1 “structured” because it was constant on affine subspaces of low codimension. For quadratic Fourier analysis, we need a quadratic analogue of the notion of a decomposition ofFnp into parallel affine subspaces of codimensiond1. In order to define such a decomposition, one can take a surjective linear map Γ1 : Fnp → Fdp1 and for each a ∈ Fdp1 one can set Va to equal Γ−11 ({a}).

If we want to make this idea quadratic, we should replace the linear map Γ1 by a “quadratic map” Γ2, which we do in a natural way as follows. We say that a function Γ2 :Fnp →Fdp2 is quadratic if it is of the form x7→(q1(x), . . . , qd2(x)), where q1, . . . , qd2 are quadratic forms on Fnp. Then, for each b ∈ Fdp2 we define Wb to be {x∈Fnp : Γ2(x) = b}.

In [GT05b], Green and Tao defineB1 to be the algebra generated by the sets Va and B2 for the finer algebra generated by the setsVa∩Wb. They callB1 alinear factor of complexity d1 and (B1,B2) a quadratic factor of complexity (d1, d2). This is to draw out a close analogy with the “characteristic factors” that occur in ergodic theory.

These definitions give us a suitable notion of a “quadratically structured” function—

it is a function f1 for which we can find a linear map Γ1 :Fnp →Fdp1 and a quadratic map Γ2 : Fnp → Fdp2 such that d1 and d2 are not too large and f1 is constant on the sets Va∩Wb defined above. This is equivalent to saying that f1 is measurable with respect to the algebra B2, and also to saying that f1(x) depends on (Γ1(x),Γ2(x)) only.

The quadratic structure theorem of Green and Tao implies that a bounded function f defined on Fnp can be written as a sumf1+f2, wheref1 is quadratically structured in the above sense, and kf2kU3 is small. In [GT05b] the result is stated explicitly for

2.3 True Complexity for Vector Spaces over Finite Fields

p= 5, but this is merely because of the emphasis placed on 4-term progressions. The proof is not affected by the choice of p(as long as it stays fixed).

In the statement below, which is taken from [GT05b], we write E(f|B2) for the conditional expectation, or averaging projection, of f. That is, if X = Va∩Wb is an atom of B2 and x ∈ X, then E(f|B2)(x) is the average of f over X. Since the functionE(f|B2) is constant on the setsVa∩Wb, it is quadratically structured in the sense that interests us.

Theorem 2.9. Let p be a fixed prime, let δ > 0 and suppose that n > n0(δ) is suf-ficiently large. Given any function f : Fnp → [−1,1], there exists a quadratic factor (B1,B2) of complexity at most ((4δ−1)3C0+1,(4δ−1)2C0+1) together with a decomposi-tion

f =f1+f2, where

f1 :=E(f|B2) and kf2kU3 ≤δ.

The absolute constant C0 can be taken to be 216.

As it stands, the above theorem is not quite suitable for applications, because tech-nical problems arise if one has to deal with quadratic forms of low rank. (Notice that so far we have said nothing about the quadratic forms qi—not even that they are dis-tinct.) Let Γ2 = (q1, . . . , qk) be a quadratic map and for eachiletβi be the symmetric bilinear form corresponding to qi: that is, βi(x, y) = (qi(x+y)−qi(x)−qi(y))/2.

We shall say that Γ2 is of rank at least r if the bilinear form P

iλiβi has rank at least r whenever λ1, . . . , λd2 are elements of Fp that are not all zero. If Γ2 is used in combination with some linear map Γ1 to define a quadratic factor (B1,B2), then we shall also say that this quadratic factor has rank at least r.

Just to clarify this definition, let us prove a simple lemma that will be used later.

Lemma 2.10. Let β be a symmetric bilinear form of rank r on Fnp and let W be a subspace of Fnp of codimension d1. Then the rank of the restriction of β to W is at least r−2d1.

Proof. Let V =Fnp. For every subspace W of V, let us writeW for the subspace {v ∈V :β(v, w) = 0 for every w∈W}.

The rank ofβ is just the codimension ofV, and equals rby hypothesis. Now letW have codimension d1, and let Y be a complement for W, which will therefore have

2.3 True Complexity for Vector Spaces over Finite Fields

dimensiond1. ThenV =W∩Y and Yhas dimension at leastn−d1. It follows easily that

r = codimV≤codimW+ codimY ≤codimW+d1,

which implies that the codimension of W is at least r−d1. Hence the codimension of W inside W is at least r−2d1.

We are now in a position to state the version of the structure theorem that we shall be using. It can be read out of (but is not explicitly stated in) [Gre05b] and [GT05b].

Theorem 2.11. Letpbe a fixed prime, letδ >0, let r:N→Nan arbitrary function (which may depend on δ) and suppose that n > n0(r, δ) is sufficiently large. Then given any function f :Fnp → [−1,1], there exists d0 =d0(r, δ) and a quadratic factor (B1,B2)of rank at leastr(d1+d2)and complexity at most(d1, d2), d1, d2 ≤d0, together with a decomposition

f =f1+f2+f3, where

f1 :=E(f|B2), kf2k2 ≤δ and kf3kU3 ≤δ.

Note that Ef1 =Ef. In particular Ef1 = 0 whenever f is the balanced function of a subset of Fnp. It can be shown that f1 is uniform whenever f is uniform: roughly speaking, the reason for this is that E(f|B1) is approximately zero and the atoms of B2 are uniform subsets of the atoms of B1. However, we shall not need this fact.

We shall apply Theorem 2.11 when r is the function d7→2md+C for a constant C.

Unfortunately, ensuring that factors have high rank is an expensive process: even for this modest function the argument involves an iteration that increases d0 exponen-tially at every step. For this reason we have stated the theorem in a qualitative way.

A quantitative version would involve a tower-type bound.