Roth’s theorem on arithmetic progressions asserts that every subset of the integers {{\bf Z}} of positive upper density contains infinitely many arithmetic progressions of length three. There are many versions and variants of this theorem. Here is one of them:

Theorem 1 (Roth’s theorem) Let {G = (G,+)} be a compact abelian group, with Haar probability measure {\mu}, which is {2}-divisible (i.e. the map {x \mapsto 2x} is surjective) and let {A} be a measurable subset of {G} with {\mu(A) \geq \alpha} for some {0 < \alpha < 1}. Then we have

\displaystyle \int_G \int_G 1_A(x) 1_A(x+r) 1_A(x+2r)\ d\mu(x) d\mu(r) \gg_\alpha 1,

where {X \gg_\alpha Y} denotes the bound {X \geq c_\alpha Y} for some {c_\alpha > 0} depending only on {\alpha}.

This theorem is usually formulated in the case that {G} is a finite abelian group of odd order (in which case the result is essentially due to Meshulam) or more specifically a cyclic group {G = {\bf Z}/N{\bf Z}} of odd order (in which case it is essentially due to Varnavides), but is also valid for the more general setting of {2}-divisible compact abelian groups, as we shall shortly see. One can be more precise about the dependence of the implied constant {c_\alpha} on {\alpha}, but to keep the exposition simple we will work at the qualitative level here, without trying at all to get good quantitative bounds. The theorem is also true without the {2}-divisibility hypothesis, but the proof we will discuss runs into some technical issues due to the degeneracy of the {2r} shift in that case.

We can deduce Theorem 1 from the following more general Khintchine-type statement. Let {\hat G} denote the Pontryagin dual of a compact abelian group {G}, that is to say the set of all continuous homomorphisms {\xi: x \mapsto \xi \cdot x} from {G} to the (additive) unit circle {{\bf R}/{\bf Z}}. Thus {\hat G} is a discrete abelian group, and functions {f \in L^2(G)} have a Fourier transform {\hat f \in \ell^2(\hat G)} defined by

\displaystyle \hat f(\xi) := \int_G f(x) e^{-2\pi i \xi \cdot x}\ d\mu(x).

If {G} is {2}-divisible, then {\hat G} is {2}-torsion-free in the sense that the map {\xi \mapsto 2 \xi} is injective. For any finite set {S \subset \hat G} and any radius {\rho>0}, define the Bohr set

\displaystyle B(S,\rho) := \{ x \in G: \sup_{\xi \in S} \| \xi \cdot x \|_{{\bf R}/{\bf Z}} < \rho \}

where {\|\theta\|_{{\bf R}/{\bf Z}}} denotes the distance of {\theta} to the nearest integer. We refer to the cardinality {|S|} of {S} as the rank of the Bohr set. We record a simple volume bound on Bohr sets:

Lemma 2 (Volume packing bound) Let {G} be a compact abelian group with Haar probability measure {\mu}. For any Bohr set {B(S,\rho)}, we have

\displaystyle \mu( B( S, \rho ) ) \gg_{|S|, \rho} 1.

Proof: We can cover the torus {({\bf R}/{\bf Z})^S} by {O_{|S|,\rho}(1)} translates {\theta+Q} of the cube {Q := \{ (\theta_\xi)_{\xi \in S} \in ({\bf R}/{\bf Z})^S: \sup_{\xi \in S} \|\theta_\xi\|_{{\bf R}/{\bf Z}} < \rho/2 \}}. Then the sets {\{ x \in G: (\xi \cdot x)_{\xi \in S} \in \theta + Q \}} form an cover of {G}. But all of these sets lie in a translate of {B(S,\rho)}, and the claim then follows from the translation invariance of {\mu}. \Box

Given any Bohr set {B(S,\rho)}, we define a normalised “Lipschitz” cutoff function {\nu_{B(S,\rho)}: G \rightarrow {\bf R}} by the formula

\displaystyle \nu_{B(S,\rho)}(x) = c_{B(S,\rho)} (1 - \frac{1}{\rho} \sup_{\xi \in S} \|\xi \cdot x\|_{{\bf R}/{\bf Z}})_+ \ \ \ \ \ (1)

where {c_{B(S,\rho)}} is the constant such that

\displaystyle \int_G \nu_{B(S,\rho)}\ d\mu = 1,

thus

\displaystyle c_{B(S,\rho)} = \left( \int_{B(S,\rho)} (1 - \frac{1}{\rho} \sup_{\xi \in S} \|\xi \cdot x\|_{{\bf R}/{\bf Z}})\ d\mu(x) \right)^{-1}.

The function {\nu_{B(S,\rho)}} should be viewed as an {L^1}-normalised “tent function” cutoff to {B(S,\rho)}. Note from Lemma 2 that

\displaystyle 1 \ll_{|S|,\rho} c_{B(S,\rho)} \ll_{|S|,\rho} 1. \ \ \ \ \ (2)

We then have the following sharper version of Theorem 1:

Theorem 3 (Roth-Khintchine theorem) Let {G = (G,+)} be a {2}-divisible compact abelian group, with Haar probability measure {\mu}, and let {\epsilon>0}. Then for any measurable function {f: G \rightarrow [0,1]}, there exists a Bohr set {B(S,\rho)} with {|S| \ll_\epsilon 1} and {\rho \gg_\epsilon 1} such that

\displaystyle \int_G \int_G f(x) f(x+r) f(x+2r) \nu_{B(S,\rho)}*\nu_{B(S,\rho)}(r)\ d\mu(x) d\mu(r) \ \ \ \ \ (3)

\displaystyle \geq (\int_G f\ d\mu)^3 - O(\epsilon)

where {*} denotes the convolution operation

\displaystyle f*g(x) := \int_G f(y) g(x-y)\ d\mu(y).

A variant of this result (expressed in the language of ergodic theory) appears in this paper of Bergelson, Host, and Kra; a combinatorial version of the Bergelson-Host-Kra result that is closer to Theorem 3 subsequently appeared in this paper of Ben Green and myself, but this theorem arguably appears implicitly in a much older paper of Bourgain. To see why Theorem 3 implies Theorem 1, we apply the theorem with {f := 1_A} and {\epsilon} equal to a small multiple of {\alpha^3} to conclude that there is a Bohr set {B(S,\rho)} with {|S| \ll_\alpha 1} and {\rho \gg_\alpha 1} such that

\displaystyle \int_G \int_G 1_A(x) 1_A(x+r) 1_A(x+2r) \nu_{B(S,\rho)}*\nu_{B(S,\rho)}(r)\ d\mu(x) d\mu(r) \gg \alpha^3.

But from (2) we have the pointwise bound {\nu_{B(S,\rho)}*\nu_{B(S,\rho)} \ll_\alpha 1}, and Theorem 1 follows.

Below the fold, we give a short proof of Theorem 3, using an “energy pigeonholing” argument that essentially dates back to the 1986 paper of Bourgain mentioned previously (not to be confused with a later 1999 paper of Bourgain on Roth’s theorem that was highly influential, for instance in emphasising the importance of Bohr sets). The idea is to use the pigeonhole principle to choose the Bohr set {B(S,\rho)} to capture all the “large Fourier coefficients” of {f}, but such that a certain “dilate” of {B(S,\rho)} does not capture much more Fourier energy of {f} than {B(S,\rho)} itself. The bound (3) may then be obtained through elementary Fourier analysis, without much need to explicitly compute things like the Fourier transform of an indicator function of a Bohr set. (However, the bound obtained by this argument is going to be quite poor – of tower-exponential type.) To do this we perform a structural decomposition of {f} into “structured”, “small”, and “highly pseudorandom” components, as is common in the subject (e.g. in this previous blog post), but even though we crucially need to retain non-negativity of one of the components in this decomposition, we can avoid recourse to conditional expectation with respect to a partition (or “factor”) of the space, using instead convolution with one of the {\nu_{B(S,\rho)}} considered above to achieve a similar effect.

— 1. Proof of theorem —

Fix {G, f, \epsilon > 0}. Let {k} be a large integer (depending only on {\epsilon}) to be chosen later. We will need a sequence

\displaystyle 1 = \delta_0 \gg \delta_1 \gg \dots \gg \delta_{3k-1} > 0

of small parameters, with each {\delta_i} assumed to be sufficiently small depending on all previous {\delta_0,\dots,\delta_{i-1}} and on {\epsilon}. (One should think of the {\delta_i} as shrinking to zero incredibly fast, e.g. {\delta_0 = 1} and {\delta_{i+1} = \exp( - \epsilon^{-100} \delta_i^{1/\epsilon^{100}} )} for {0 \leq i < 3k-1}.)

We then define an increasing sequence

\displaystyle \{0\} = S_0 \subset S_1 \subset \dots \subset S_k \subset \hat G

of finite sets {S_i} of frequencies, as follows.

  • (i) Initialise {S_0 := \{0\}}.
  • (ii) Once {S_i} has been selected for some {0 \leq i < k}, introduce the function

    \displaystyle \nu_i := \nu_{B(S_i,\delta_{3i} )}. \ \ \ \ \ (4)

    Note that this is a square-integrable function, thanks to (2).

  • (iii) Define {S_{i+1}} to be the set

    \displaystyle S_{i+1} := S_i \cup \{ \xi \in \hat G: |\hat f(\xi)| \geq \delta_{3i+2} \} \ \ \ \ \ (5)

    \displaystyle \cup \bigcup_{j=0}^i \{ \xi \in \hat G: |\hat \nu_j(\xi)| \geq \delta_{3i+2} \}.

    Note from Plancherel’s theorem that this is a finite set.

  • (iv) If {i < k-1}, increment {i} to {i+1} and return to step (ii).

An easy induction using Plancherel’s theorem and (2) repeatedly gives the bounds

\displaystyle \| \nu_i \|_{L^2(G)} \ll_{i,\delta_0,\dots,\delta_{3i}} 1

and

\displaystyle |S_i| \ll_{i,\delta_0,\dots,\delta_{3i-1}} 1

for all {i=0,\dots,k-1}.

From Plancherel’s theorem we also have

\displaystyle \sum_{\xi \in \hat G} |\hat f(\xi)|^2 \ll 1. \ \ \ \ \ (6)

As the {S_i} are increasing, we thus see from the pigeonhole principle (if {k} is sufficiently large depending on {\epsilon}) that there exists {1 \leq i \leq k-2} such that

\displaystyle \sum_{\xi \in S_{i+2} \backslash S_i} |\hat f(\xi)|^2 \ll \epsilon^2. \ \ \ \ \ (7)

We now decompose

\displaystyle f = f_0 + f_1 + f_2

where

\displaystyle f_0 := f * \nu_i

\displaystyle f_1 := f * \nu_{i+1} - f * \nu_i

\displaystyle f_2 := f - f*\nu_{i+1}.

One can think of {f_0, f_1, f_2} as the “low frequency” (or “structured”, or “quasiperiodic”), “medium frequency” (or “small”), and “high frequency” (or “highly pseudorandom”) components of {f}, where the notion of what it means for a frequency to be high or low is not determined by some preconceived notion of magnitude, but is instead adapted to the function {f} itself. We will think of {f_0} as the “main” term, and {f_1, f_2} as “errors”.

Since {f} is bounded in magnitude by {1}, and {\nu_i, \nu_{i+1}} are non-negative with total mass {1}, we have the {L^\infty} bounds

\displaystyle \|f_0\|_{L^\infty(G)}, \|f_1\|_{L^\infty(G)}, \|f_2\|_{L^\infty(G)} \ll 1. \ \ \ \ \ (8)

Now we give further bounds on {f_0,f_1,f_2}. We begin with {f_2}:

Lemma 4 ({f_2} has very small Fourier coefficients) We have

\displaystyle \| \hat f_2 \|_{\ell^\infty(\hat G)} \ll \delta_{3i+2}.

Proof: Let {\xi \in \hat G}. From the definition of {f_2} and elementary Fourier analysis we have

\displaystyle \hat f_2(\xi) = \hat f(\xi) (1 - \hat \nu_{i+1}(\xi)).

If {\xi \not \in S_{i+1}}, then from (5) we have

\displaystyle |\hat f(\xi)| \leq \delta_{3i+2}

and the claim follows (since {\nu_{i+1}} has total mass one). Now suppose instead that {\xi \in S_{i+1}}. Then from (4) we have

\displaystyle e^{2\pi i \xi \cdot x} = 1 - O( \delta_{3i+3} )

for all {x} in the support of {\nu_{i+1}}, and thus

\displaystyle \hat \nu_{i+1}(\xi) = 1 - O( \delta_{3i+3} )

and the claim again follows. \Box

Now we control {f_1}:

Lemma 5 ({f_1} small in {L^2}) We have

\displaystyle \| f_1 \|_{L^2(G)} \ll \epsilon.

Proof: From the definition of {f_1} and elementary Fourier analysis we have

\displaystyle \| f_1 \|_{L^2(G)}^2 = \sum_{\xi \in\hat G} |\hat f(\xi)|^2 |\hat \nu_i(\xi) - \hat \nu_{i+1}(\xi)|^2. \ \ \ \ \ (9)

We wish to bound this by {O(\epsilon^2)}. From (7) we see that the contribution of those {\xi} in {S_{i+2} \backslash S_i} are acceptable. Now let us look at the contribution with {\xi \not \in S_{i+2}}. From (5) we have

\displaystyle |\hat \nu_i(\xi)|, |\hat \nu_{i+1}(\xi)| < \delta_{3i+5}

for such {\xi}, so this contribution to (9) is certainly acceptable thanks to (6). Now suppose that {\xi \in S_i}. The argument in the proof of Lemma 4 shows that {\hat \nu_{i+1}(\xi) = 1-O( \delta_{3i+3} )} and {\hat \nu_i(\xi) = 1-O( \delta_{3i} )}, and so this contribution is again acceptable thanks to (6). \Box

Finally, we record the key properties of {f_0}:

Lemma 6 ({f_0} continuous) {f_0} is non-negative, has mean {\int_G f_0\ d\mu = \int_G f\ d\mu}, and obeys the bound

\displaystyle f_0(x+r) = f_0(x) + O(\epsilon)

whenever {x \in G} and {r \in B( S_i, \delta_{3i+1} )}.

Proof: The first two properties are obvious, so we turn to the third. Since {f_0 = f * \nu_i} and {f} is bounded, it suffices to show that

\displaystyle \nu_i(x+r) = \nu_i(x) + O(\epsilon)

whenever {x \in G} and {r \in B( S_i, \delta_{3i+1} )}. But from (1) and the triangle inequality we have

\displaystyle |\nu_i(x+r) - \nu_i(x)| \leq c_{B(S_i,\delta_{3i})} \frac{\delta_{3i+1}}{\delta_{3i}}

for such {x,r}, and the claim follows from (2). \Box

Now we can prove Theorem 3 with {B(S,\rho) = B(S_i,\delta_{3i+1})}. Splitting {f=f_0+f_1+f_2} as above, we can decompose the left-hand side of (3) into {3^3=27} terms, each of the form

\displaystyle \int_G \int_G f_a(x) f_b(x+r) f_c(x+2r) \nu_{B(S_i,\delta_{3i+1})}*\nu_{B(S_i,\delta_{3i+1})}(r)\ d\mu(x) d\mu(r)

for some {a,b,c \in \{0,1,2\}}.

Let us consider a term for which {a=1}. We can bound this term by

\displaystyle O( \int_G |f_1(x)| \nu_{B(S_i,\delta_{3i+1})}*\nu_{B(S_i,\delta_{3i+1})}(r)\ d\mu(x) d\mu(r) )

\displaystyle = O( \int_G |f_1(x)|\ d\mu(x) )

which is {O(\epsilon)} thanks to Lemma 5. Similar arguments hold for terms with {b=1} or {c=1}, after shifting {x} by {r} or {2r}.

Now let us consider a term for which {a=2}, that is to say

\displaystyle \int_G \int_G f_2(x) f_b(x+r) f_c(x+2r) \nu_{B(S_i,\delta_{3i+1})}*\nu_{B(S_i,\delta_{3i+1})}(r)\ d\mu(x) d\mu(r).

A short Fourier-analytic calculation reveals that this integral may be written as a sum

\displaystyle \sum_{\xi_1,\xi_2,\xi_3 \in \hat G: \xi_1+\xi_2+\xi_3 = 0} \hat f_2(\xi_1) \hat f_b(\xi_2) \hat f_c(\xi_3) |\hat \nu_{B(S_i,\delta_{3i+1})}(-\xi_2 - 2 \xi_3 )|^2.

From (2) we have

\displaystyle \int_G |\nu_{B(S_i,\delta_{3i+1})}|^2\ d\mu \ll_{i,\delta_0,\dots,\delta_{3i+1}} 1

and thus by Plancherel

\displaystyle \sum_{\xi \in \hat G} |\nu_{B(S_i,\delta_{3i+1})}(\xi)|^2\ d\mu \ll_{i,\delta_0,\dots,\delta_{3i+1}} 1.

Similarly, from (6) we have

\displaystyle \sum_{\xi \in \hat G} |\hat f_b(\xi)|^2 \ll 1

and

\displaystyle \sum_{\xi \in \hat G} |\hat f_c(\xi)|^2 \ll 1,

and hence by Cauchy-Schwarz and the {2}-torsion-free nature of {\hat G}, one has

\displaystyle \sum_{\xi_2,\xi_3 \in\hat G: -\xi_2-2\xi_3 = \xi} |\hat f_b(\xi_2)| |\hat f_c(\xi_3)| \ll 1

for all {\xi \in \hat G}. Combining these estimates with Lemma 4, we conclude that this contribution to (3) is

\displaystyle O_{i,\delta_0,\dots,\delta_{3i+1}}( \delta_{3i+2} ) = O( \epsilon ).

Similar arguments dispose of the terms for which {b=2} or {c=2}.

The only remaining term is when {a=b=c=0}, that is to say

\displaystyle \int_G \int_G f_0(x) f_0(x+r) f_0(x+2r) \nu_{B(S_i,\delta_{3i+1})}*\nu_{B(S_i,\delta_{3i+1})}(r)\ d\mu(x) d\mu(r).

From several applications of Lemma 6 we see that

\displaystyle f_0(x+r), f_0(x+2r) = f_0(x) + O(\epsilon)

for {(x,r)} in the support of this integrand. Thus this term may be written as

\displaystyle \int_G \int_G (f_0(x)^3 + O(\epsilon)) \nu_{B(S_i,\delta_{3i+1})}*\nu_{B(S_i,\delta_{3i+1})}(r)\ d\mu(x) d\mu(r),

which on evaluating the {r} integral simplifies to

\displaystyle \int_G (f_0(x)^3 + O(\epsilon))\ d\mu(x),

but by the non-negativity of {f_0} and Hölder’s inequality, this is at least

\displaystyle (\int_G f_0\ d\mu)^3 - O(\epsilon) = (\int_G f\ d\mu)^3 - O(\epsilon)

and the claim follows.