1.2. Roth’s theorem 43
(iii) Show that if f ∈
is non-negative with
f dμ 0, then
Λ(f, f, f) 0.
(iv) Show that if f1,f2,f3 ∈
= 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
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
6To put it another way, subsets of [N] of density much larger than 1/ log∗
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.