1.2. Roth’s theorem 43

(iii) Show that if f ∈

L∞(Z1)

is non-negative with

[N]

f dμ 0, then

Λ(f, f, f) 0.

(iv) Show that if f1,f2,f3 ∈

L∞([N])

and

E(fi|Z1)

= 0 for at least one

i = 1, 2, 3, then Λ(f1,f2,f3) = 0.

(v) Conclude the proof of Roth’s theorem using ultralimits.

Remark 1.2.14. Note how the (finitary) arithmetic regularity lemma has

been replaced by the more familiar (infinitary) theory of conditional expecta-

tion to a factor, and the finitary notion of measurability has been replaced

by a notion from the traditional (countably additive) infinitary theory of

measurability. This is one of the key advantages of the ultralimit approach,

namely that it allows one to exploit already established theories of infinitary

mathematics (e.g. measure theory, ergodic theory, Hilbert space geometry,

etc.) to prove a finitary result.

Exercise 1.2.15. Use the ultralimit energy increment method to establish

yet another proof of Exercise 1.2.7.

Remark 1.2.15. The ultralimit approach to the above type of decomposi-

tions can be generalised to the task of counting more complicated patterns

than arithmetic progressions; see [Sz2009], [Sz2009b], [Sz2010]. The ap-

proach taken in those papers is analogous in many ways to the ergodic-

theoretic approach of Host and Kra [HoKr2005], which we will not discuss

in detail here.

1.2.3. More quantitative bounds (optional). The above proofs of

Roth’s theorem (as formulated in, say, Theorem 1.2.2) were qualitative in

the sense that they did not explicitly give a bound for N0 in terms of δ.

Nevertheless, by analysing the finitary arguments more carefully, a bound

can be extracted:

Exercise 1.2.16. Show that in Proposition 1.2.6, one can take N

εO(1)N 1/2.

Using this and the density increment argument, show that one

can take N0 exp(exp(O(1/δ))) in Theorem 1.2.2. (To put it another

way, subsets of [N] of density much larger than 1/ log log N will contain

progressions of length three.)

Exercise 1.2.17. Show that in the energy increment proof of Roth’s theo-

rem, one can take the growth functions F involved to be polynomial in K

(but with the exponent growing exponentially with each refinement of the

factor), and F can be taken to be an iterated exponential; thus ultimately

allows one to take N0 to be a tower exponential

6

of height

O(δ−O(1)).

Thus

6To put it another way, subsets of [N] of density much larger than 1/ log∗

c

N for some c 0

will contain progressions of length three, where log∗ N is the number of logarithms needed to

reduce N to below (say) 2.