• No results found

Eliminating Low-Rank Quadratic Phases

2.4 Improved Bounds

2.4.2 Eliminating Low-Rank Quadratic Phases

2.4 Improved Bounds

2.4 Improved Bounds

For the second part, we know thatkfkU2 is the maximum of hf, giover all functions g such thatkgkU2 ≤1. Now replacingg byE(g|B1) does not affect the inner product hf, gi and does not increase kgkU2. Therefore, the maximum must be achieved by a functiong that is constant on the atoms ofB1. But then |hf, gi| ≤ kfk2kgk2, which is at most pr/4kfk2kgkU2, by the first part. This completes the proof of the lemma.

The next lemma is a standard fact about Gauss sums, which we have already en-countered as Lemma 2.29.

Lemma 2.29. Let q be a quadratic form of rankr. Then |Exωq(x)|=p−r/2.

As is to be expected, the rank of the quadratic form determines the U2- (and hence the (U2)-) norm of the corresponding quadratic phase.

Lemma 2.30. Let q be a quadratic form of rank r. Then kωqkU2 = p−r/4 and kωqkU2 =pr/4.

Proof. Let β be as in Lemma 2.29. Then for any x,a and b inFnp we have

q(x)−q(x+a)−q(x+b) +q(x+a+b) =β(x+b, a) +q(a)−q(a)−β(x, a) =β(a, b).

Therefore,

qk4U2 =Ex,a,bωβ(a,b).

Now for each fixedathe functionβ(a, b) is linear inb. It therefore sums to zero unless it is identically zero. But β has rank r, so the subspace of all a such that β(a, b) is identically zero has codimension r. Therefore, the expectation on the right hand side is p−r. This proves the first part.

Now let f be an arbitrary function from Fnp to C and let us obtain an upper bound for |hf, ωqi|. Let B1 be the linear factor whose atoms are the translates of V. Then ωq is constant on each atom, so if we let g =E(f|B1) then hf, ωqi = hg, ωqi. More-over, kgkU2 ≤ kfkU2, by Lemma 2.27. But kgk2 ≤ pr/4kgkU2, by Lemma 2.28, and therefore, by the Cauchy-Schwarz inequality and the fact that kωqk2 = 1,

|hf, ωqi|=|hg, ωqi| ≤pr/4kgkU2 ≤pr/4kfkU2.

It follows that kωqkU2 ≤ pr/4. Moreover, taking f =ωq and using the first part, we see that this inequality is in fact an equality.

We remark that an alternative argument for Lemma 2.30 is to use Lemma 2.29 to prove that ωq haspr non-zero Fourier coefficients, each of magnitude p−r/2, and then

2.4 Improved Bounds

use the fact that kfkU2 = kfbk4. However, the argument we have used takes place entirely in physical space and is therefore easier to generalize.

Now we are ready for the case of forms of very low rank.

Lemma 2.31. Let f =P

iλiωqi, where the functions qi are quadratic forms on Fnp

of rank at most r, and P

ii| ≤M. Then for everyδ >0 there is a linear factor B1 of complexity at most δ−2M4pr such that kf−E(f|B1)k2 ≤δ.

Proof. By Lemma 2.30 we know that kfkU2 ≤M pr/4, which is all we need to know about f. The rest of the proof is a standard Bogolyubov-type argument. First of all, sincekfkU2 =kfbk4, it follows thatkfkU2 =kfbk4/3. By the Fourier inversion formula, we know thatf(x) =P

rfb(r)ω−r.x. Let α=δ3/2p−r/2M−2 and let K ={r:|fb(r)| ≥ α}. Then we can decompose f as a sum f1+f2, where f1(x) = P

r∈Kfb(r)ω−r.x and f2(x) =P

r /∈Kfb(r)ω−r.x.

Let V be the subspace of all x such that r.x = 0 for every r ∈ K. Since kfkb 4/3 ≤ M pr/4, we know that |K| ≤ M4/3pr/3α−4/3. Therefore, V has codimension at most M4/3pr/3α−4/3 = δ−2M4pr, which is also an upper bound for the complexity of the linear factor B1 defined by V. Since f1 depends only on the values of the functions ωr.x with r ∈K, f1 is constant on the atoms of B1.

As for f2, we can bound itsL2 norm as follows.

kf2k22 =kfb2k22 ≤ kfb2k4/34/3kfb2k2/3 ≤α2/3M4/3pr/3 ≤δ.

To complete the proof it remains to observe that E(f|B1) is the closest function (in L2) to f that is constant on the atoms ofB1. Therefore, the statement of the lemma follows from our calculations.

Next, we deal with sums of forms that mostly have differences of high rank.

Lemma 2.32. Let f =P

iλiωqi be a function with P

ii| ≤M, let r be an integer and let Z be the set of pairs (i, j) such that the rank ofqi−qj is at mostr. Let η >0 and suppose that P

(i,j)∈Zi||λj| ≤η. Then kfk22 ≤η+p−r/2M2. Proof. By Lemma 2.29,

kfk22 =X

i,j

λiλjExωqi(x)−qj(x) ≤ X

(i,j)∈Z

i||λj|+p−r/2 X

(i,j)/∈Z

i||λj|.

By hypothesis, this is at most η+p−r/2M2, as claimed.

2.4 Improved Bounds

We are now ready for a combined lemma that will deal with arbitrary sums of forms of rank at most R.

Lemma 2.33. Let M ≥ 1 and let f = P

iλiωqi be a function with P

ii| ≤ M, where each qi is a quadratic form on Fnp of rank at most R. Let δ > 0 and let s= 218(M/δ)12. Then there is a linear factorBof complexity at most8(M/δ)2(R+s) such that kf−E(f|B)k2 ≤δ.

Proof. Let η=δ2/8M, let r be such that p−r/2M22/8 and let s=η−4M4pr. (It can be checked that this definition of s agrees with the definition in the statement.

These numbers are chosen so that we get the right bounds out of Lemmas 2.32 and 2.31, as will become clear.)

Let us define a vertex-weighted graphGas follows. The vertices ofGare the quadratic forms qi, and the weight of qi is |λi|. And qi is joined toqj if and only if the rank of qi−qj is at most r. Let V be the vertex set of G, and define the degree of a vertex qi to be the sum of the weights of those qj that are joined toqi. (We will allow G to have loops, so qi is joined to itself.)

Suppose G has a vertexqi of degree at least η. Then letV1 be the neighbourhood of qi, and removeV1 from the vertex set ofG. Now repeat this process with the induced subgraph with vertex set V \V1 (and the same weights). Continuing in this way we find disjoint sets V1, V2, . . . , Vk and W such that the weight of each Vi is at least η and every vertex in W has degree less than η.

Let us now focus on V1. If qi is the form of which V1 is the neighbourhood, then the rank of qi −qj is at most r for every qj ∈ V1. Therefore, if we set g1 to equal P

jλjωqi−qj, Lemma 2.31 tells us that there is a linear factor B1 of complexity at most s such that kg1−E(g|B1)k2 ≤ η2. It follows that kg1−E(g1|B)k2 ≤η2 for any linear factor B that refines B1.

Now let f1 = P

qj∈V1λjωqj = ωqig1. Since qi has rank at most R, there is a linear factor B01 of complexity at most R on the atoms of whichqi is constant. Therefore, if B100 is the smallest common refinement of B1 and B01, we find that B001 has complexity at most R+s and that kf1 −E(f1|B100)k2 ≤ η2. (Here we have also used the fact that the modulus ofωqi is everywhere 1.) Again, this statement is also true for every refinement B of B100.

Let us do the same for each Vi. That is, fi =P

qj∈Viλjωqj and Bi00 is a linear factor of complexity at most R+s such that kfi −E(f|Bi00)k2 ≤ η2. Let B1 be a common refinement of all the linear factors Bi00. Then kfi−E(f|B)k2 ≤η2 as well, and B has complexity at most η−1M(R+s).

2.4 Improved Bounds

Finally, let g = f − (f1 + · · ·+ fk). Then g is a sum of the form P

i∈W λiωqi, where each qi has degree less than η in the subgraph of G induced by W. If we let Z be the set of all pairs (i, j) ∈ W2 such that qi −qj has rank at most r, then P

(i,j)∈Zi||λj| ≤ηM ≤δ2/8. From Lemma 2.32 and our choice ofr, it follows that kgk22 ≤δ2/4.

We are now more or less done. We have kf −E(f|B)k2 ≤X

i

kfi−E(fi|B)k2+kg−E(g|B)k2 ≤η−1M η2+δ/2≤δ.

It remains to note that η−1M(R+s), our upper bound for the complexity ofB, is at most 8M2(R+s)/δ2, as stated.

Needless to say, the precise form of the bound for the complexity ofBis not important.

What does matter, however, is the way it depends on R. In particular, for large R the bound is significantly better than the bound of δ−2M4pR that we could read out of Lemma 2.31. If we regard δ and M as fixed, then that bound is exponential in R, whereas we have just proved a linear bound. (However, M and s will be rather large constants, so this is not quite as good as it sounds.)

Theorem 2.34. Let f : Fnp → C be a function such that kfk2 ≤ 1. Then for every δ >0, there exists a constant M such that for every R0 there exists a constant c >0 with the following property. If kfkU2 ≤c then f has a decomposition of the form

f(x) =X

i

λiωqi(x)+g(x) +h(x),

where the qi are quadratic forms on Fnp, all of which have rank at least R0, and δ−1kgk1−1khkU3 +M−1X

i

i| ≤17.

Moreover, M can be taken to beexp(C(1/δ2)C)andccan be taken to beδp−R/4, where R ≤(223(M/δ)12)M/δR0.

Proof. Let us begin by applying Theorem 2.26 withη replaced byδ. Then we obtain a decomposition of the required kind, except that we do not know anything about the ranks of the quadratic forms qi and we know that

δ−1kgk1−1khkU3 +M−1X

i

i| ≤1.

2.4 Improved Bounds

However, now we have the extra hypothesis that kfkU2 ≤c.

The next step is to find a number R1 ≥R0 such that

X{|λi|:R1 ≤r(qi)< θR1+t} ≤δ,

where we have written r(qi) to stand for the rank of qi, we have set θ:= 221(M/δ)14 and t is chosen so that pt/4 > M/δ. Since t is much less than θ and we know that P

ii| ≤M, we must be able to find such anR1 withR1 ≤(2θ)M/δR0. Let us define R to be θR1. It is not hard to check that R satisfies the inequality stated in the theorem.

Now let S = {i:r(qi) < R1} and L= {i:r(qi) ≥R+t}. (These letters are chosen to stand for “small” and “large”, respectively.) Then

X

i

λiωqi =X

i∈S

λiωqi +X

i∈L

λiωqi+g1,

where kg1k1 ≤ δ. Let fS = P

i∈Sλiωqi and fL = P

i∈Lλiωqi. Then we have shown that f has a decomposition of the form fS +fL+g +h, where fS is made out of functionsωq withqof rank at mostR1, the forms used forfLhave rank at leastR+t, the function g (which is the new name we have given to the old g+g1) has L1-norm at most 2δ, and khkU3 ≤δ.

Now Lemma 2.33 gives us a linear factor B of complexity at most 8(M/δ)2(R1+s), where s= 218(M/δ)12, such thatkfS−E(fS|B)k2 ≤δ. In order to simplify matters, let us bound this complexity above by θR1 =R.

So now we have a decomposition f =E(fS|B) +fL+g+h, where fS, fL and h are as before and kgk1 ≤ 3δ. (We have added fS −E(fS|B) to the old g and used the fact that its L1-norm is at most its L2-norm.)

Without the term fS0 := E(fS|B), we would be done. To complete the proof we shall show that fS can be absorbed into the error term g +h. More precisely, let us suppose that we cannot write fS0 as a sum g0 +h0 with kg0k1 ≤ 6δ and kh0kU3 ≤ 6δ. Then by Corollary 2.25 there exists a function φ such that |hfS0, φi| ≥ 1 and 6δkφk+ 6δkφkU3 ≤1.

Next, we apply Lemma 2.27, which allows us to replace φbyE(φ|B). The reason for this is that the averaging projection does not increase the L- or (U3)- norms and does not change the inner producthfS0, φi. Let us therefore assume thatφ is constant on the atoms of B.

2.4 Improved Bounds

We are a short step away from the contradiction we are looking for. Since kφk ≤ 1/6δ and kgk1 ≤ 3δ, it follows that |hg, φi| ≤ 1/2. Similarly, |hh, φi| ≤ 1/6 because kφkU3 ≤1/6δ and khkU3 ≤δ.

Lemma 2.28 implies that kφkU2 ≤ pR/4kφk2, which is at most pR/4kφk, which we know is at most pR/4/6δ. Therefore, |hf, φi| ≤ cpR/4/6δ. By our choice of c, this is at most 1/6.

Finally, Lemma 2.30 and the triangle inequality imply between them that kfLkU2 ≤ p−(R+t)/4M. Therefore, |hfL, φi| ≤ pR/4p−(R+t)/4M/6δ, which, by our choice of t, is strictly less than 1/6. This is a contradiction because f = fS0 +fL+g +h and we have now shown that |hfS0, φi|>|hf, φi|+|hfL, φi|+|hg, φi|+|hh, φi|.

This contradiction shows that we can after all writefS0 as a sumg0+h0 withkg0k1 ≤6δ and kh0kU3 ≤ 6δ. Therefore, we can write f = fL +g +h with kgk1 ≤ 9δ and khkU3 ≤7δ, which implies the result.

Once again, the exact bounds we obtain are not too important, but we do care about their rough order of magnitude and the constants on which they depend. Since M is exponential in δ−2, R is exponential in M and c depends exponentially on R, the dependence of c on δ in Theorem 2.34 has the form c ≤ pexp exp(C/δ2) for some absolute constant C. That is, it has a trebly exponential dependence on δ.

Theorem 2.34 will be our main tool. Before we apply it to systems of square-independent linear forms, we need a couple of lemmas to help us with our calcu-lations.