2.4 Improved Bounds
2.4.1 Decomposing f into a Sum of Quadratic Phases
Let us start almost completely from scratch and state theU3-inverse theorem [GT05b]
on which the decomposition result Theorem 2.11 is based, and whose history we have already discussed in Section 2.3.
Theorem 2.22. Let 0< δ ≤1 and let f :Fnp →C be a function with kfk∞ ≤1 and kfkU3 ≥δ. Then there exists a quadratic form q:Fnp →Fp such that
|Exf(x)ωq(x)| ≥exp(−Cδ−C).
Here, C is a constant that depends on p only.
As we saw in Section 2.3, Green and Tao use the above theorem to decompose an arbitrary functionf into two parts,f1andf2, wheref2is quadratically uniform andf1 is quadratically structured, in the sense that one can partitionFnp into a small number of quadratic subvarieties on each of which f1 is constant. In this section, we shall take a somewhat different approach, more closely analogous to the way conventional
2.4 Improved Bounds
Fourier analysis is used to prove Roth’s theorem. That is, we shall simply decompose f into a sum of functions of the form ωqi, where theqi are quadratic forms, plus an error that we can afford to ignore, and then calculate directly using this expansion of f.
A big difference between the expansion we shall obtain and the expansion of a func-tion into Fourier coefficients is that there does not seem to be a canonical way of doing it, because there are far more than pn different functions of the form ωq. (In harmonic-analysis terms, we are dealing with an “overdetermined” system.) This creates difficulties, which Green and Tao dealt with by projecting onto “quadratic factors”. Here we shall deal with them by applying the Hahn-Banach theorem for finite-dimensional normed spaces.
Before we can explain why the Hahn-Banach theorem is useful, we must state both it and one or two other simple results about duality in normed spaces. Throughout the next few results, we shall refer to an inner product: this is just the standard inner product on Cn (or later CF
np).
Theorem 2.23. Let X = (Cn,k.k)be a normed space and letx∈X be a vector with kxk ≥ 1. Then there is a vector z such that |hx, zi| ≥ 1 and such that |hy, zi| ≤ 1 whenever kyk ≤1.
Recall that the dual norm k.k∗ of a norm k.k on Cn is defined by the formula kzk∗ = sup{|hx, zi|:kxk ≤1}
For technical reasons, we shall generalize this concept to the situation where the norm k.k is defined on a subspace V of Cn. Then the dual is a seminorm, given by the formula
kzk∗ = sup{|hx, zi|:x∈V,kxk ≤1}
The next lemma is a standard fact in Banach space theory.
Lemma 2.24. Let k be a positive integer, and for each i between 1 and k let k.ki be a norm defined on a subspace Vi of Cn. Suppose that V1+· · ·+Vk =Cn, and define a norm k.k on Cn by the formula
kxk= inf{kx1k1+· · ·+kxkkk :x1+· · ·+xk =x}
Then this formula does indeed define a norm, and its dual norm k.k∗ is given by the formula
kzk∗ = max{kzk∗1, . . . ,kzk∗k}
2.4 Improved Bounds
Proof. It is a simple exercise to check that the expression does indeed define a norm.
Let us begin by supposing that kzk∗i ≥ 1 for some i. Then there exists x ∈ Vi such that kxki ≤1 and |hx, zi| ≥1. But then kxk ≤ 1 as well, from which it follows that kzk∗ ≥1. Therefore, kzk∗ is at least the maximum of thekzk∗i.
Now let us suppose that kzk∗ >1. This means that there existsx such that kxk ≤1 and |hx, zi| ≥ 1 + for some > 0. Let us choose x1, . . . , xk such that xi ∈ Vi for each i,x1+· · ·+xk=x, and kx1k1+· · ·+kxkkk<1 +. Then
X
i
|hxi, zi|>kx1k1+· · ·+kxkkk
so there must exist i such that|hxi, zi|>kxiki, from which it follows that kzk∗i >1.
This proves that kzk∗ is at most the maximum of the kzk∗i.
Corollary 2.25. Let k be a positive integer and for each i ≤ k let k.ki be a norm defined on a subspace Vi of Cn, and suppose that V1+· · ·+Vk =Cn. Let α1, . . . , αk be positive real numbers, and suppose that it is not possible to write the vector x as a linear sum x1+· · ·+xk in such a way that xi ∈Vi for each i and α1kx1k1+· · ·+ αkkxkkk ≤ 1. Then there exists a vector z ∈ C such that |hx, zi| ≥ 1 and such that kzk∗i ≤αi for every i—or equivalently, |hy, zi| ≤αi for every i and every y∈Vi with kyki ≤1.
Proof. Let us define a norm k.k by the formula
kxk= inf{α1kx1k1+· · ·+αkkxkkk:x1+· · ·+xk =x}
Then our hypothesis is that kxk ≥1. Therefore, by Theorem 2.23 there is a vector z such that |hx, zi| ≥1 and |hy, zi| ≤1 whenever kyk ≤1.
The second condition tells us that kzk∗ ≤1, and Lemma 2.24, applied to the norms αik.ki, tells us that kzk∗ is the maximum of the numbersα−1i kzk∗i. Therefore, kzk∗i ≤ αi for every i, as stated.
Recall that the difficulty we are trying to deal with is that there is no (known) canonical way of decomposing a function into functions of the form ωq. Corollary 2.25 is an extremely useful tool for proving the existence of decompositions under these circumstances. Instead of trying to find a decomposition explicitly, one assumes that there is no decomposition and uses Corollary 2.25 to derive a contradiction. The next result illustrates the technique.
2.4 Improved Bounds
Theorem 2.26. Let f : Fnp → C be a function such that kfk2 ≤ 1. Then for every δ >0 and η >0 there exists M such that 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, and
η−1kgk1+δ−1khkU3 +M−1X
i
|λi| ≤1.
In fact, M can be taken to be exp(C(ηδ)−C).
Proof. Suppose not. Then for every quadratic form q on Fnp let V(q) be the one-dimensional subspace of CF
np generated by the function ωq, with the obvious norm:
the norm of λωq is|λ|.
Applying Corollary 2.25 to these norms and subspaces, and also to the L1-norm and U3-norm defined on all of CF
n
p, we deduce that there is a function φ : Fnp →C such that |hf, φi| ≥ 1,kφk∞≤ η−1, kφk∗U3 ≤ δ−1 and |hφ, ωqi| ≤M−1 for every quadratic form q.
Now the fact that |hf, φi| ≥ 1 implies, by Cauchy-Schwarz, that kφk2 ≥ 1. But we also know that hφ, φi ≤ kφkU3kφk∗U3, so kφkU3 ≥δ. Applying the inverse theorem to ηφ, we find that there is a quadratic form q such that |hφ, ωqi| ≥ exp(−C(ηδ)−C), contradicting the fact that it has to be at most M−1.
Just before we continue, let us briefly discuss a more obvious approach to Theorem 2.26 and why it does not work. Theorem 2.22 tells us that every bounded function f with large U3-norm correlates well with some function of the formωq. So one might try a simple inductive argument along the following lines. If kfkU3 is large, then Theorem 2.26 gives us a quadratic form q1 such thatf correlates withωq1. So choose λ1 such that kf − λ1ωq1k2 is minimized, and let f1 = f −λ1ωq1. Because of the correlation, kf1k2 is substantially less than kfk2. Now repeat for f1, and keep going until you reach some k for which kfk+1kU3 is small.
The problem with this argument is that we lose control of the boundedness of f. As we continually subtract the functions λiωqi, the L2-norm goes down, but the L∞ -norm can go up. And L2 control is not enough for Theorem 2.22. (Green and Tao’s approach to quadratic Fourier analysis uses averaging projections, which decrease both the L2- and L∞-norms.)