Let {\alpha \in {\bf R}/{\bf Z}} be an element of the unit circle, let {N \geq 1}, and let {\rho > 0}. We define the (rank one) Bohr set {B_N(\alpha;\rho)} to be the set

\displaystyle B_N(\alpha;\rho) := \{ n \in {\bf Z}: -N \leq n \leq N; \|n\alpha\|_{{\bf R}/{\bf Z}} \leq \rho \}

where {\|x\|_{{\bf R}/{\bf Z}}} is the distance to the origin in the unit circle (or equivalently, the distance to the nearest integer, after lifting up to {{\bf R}}). These sets play an important role in additive combinatorics and in additive number theory. For instance, they arise naturally when applying the circle method, because Bohr sets describe the oscillation of exponential phases such as {n \mapsto e^{2\pi i n \alpha}}.

Observe that Bohr sets enjoy the doubling property

\displaystyle B_N(\alpha;\rho) + B_N(\alpha;\rho) \subset B_{2N}(\alpha;2\rho),

thus doubling the Bohr set doubles both the length parameter {N} and the radius parameter {\rho}. As such, these Bohr sets resemble two-dimensional balls (or boxes). Indeed, one can view {B_N(\alpha;\rho)} as the preimage of the two-dimensional box {[-1,1] \times [-\rho,\rho] \subset {\bf R} \times {\bf R}/{\bf Z}} under the homomorphism {n \mapsto (n/N, \alpha n \hbox{ mod } 1)}.

Another class of finite set with two-dimensional behaviour is the class of (rank two) generalised arithmetic progressions

\displaystyle P( a_1,a_2; N_1,N_2 ) := \{ n_1 a_1 + n_2 a_2: n_1,n_2 \in {\bf Z}; |n_1| \leq N_1, |n_2| \leq N_2 \}

with {a_1,a_2 \in {\bf Z}} and {N_1,N_2 > 0} Indeed, we have

\displaystyle P( a_1,a_2; N_1,N_2 ) + P( a_1,a_2; N_1,N_2 ) \subset P( a_1,a_2; 2N_1, 2N_2 )

and so we see, as with the Bohr set, that doubling the generalised arithmetic progressions doubles the two defining parameters of that progression.

More generally, there is an analogy between rank {r} Bohr sets

\displaystyle B_N(\alpha_1,\ldots,\alpha_r; \rho_1,\ldots,\rho_r) := \{ n \in {\bf Z}: -N \leq n \leq N; \|n\alpha_i\|_{{\bf R}/{\bf Z}} \leq \rho_i

\displaystyle \hbox{ for all } 1 \leq i \leq r \}

and the rank {r+1} generalised arithmetic progressions

\displaystyle P( a_1,\ldots,a_{r+1}; N_1,\ldots,N_{r+1} ) := \{ n_1 a_1 + \ldots + n_{r+1} a_{r+1}:

\displaystyle n_1,\ldots,n_{r+1} \in {\bf Z}; |n_i| \leq N_i \hbox{ for all } 1 \leq i \leq r+1 \}.

One of the aims of additive combinatorics is to formalise analogies such as the one given above. By using some arguments from the geometry of numbers, for instance, one can show that for any rank {r} Bohr set {B_N(\alpha_1,\ldots,\alpha_r;\rho_1,\ldots,\rho_r)}, there is a rank {r+1} generalised arithmetic progression {P(a_1,\ldots,a_{r+1}; N_1,\ldots,N_{r+1})} for which one has the containments

\displaystyle B_N(\alpha_1,\ldots,\alpha_r;\epsilon \rho_1,\ldots,\epsilon \rho_r) \subset P(a_1,\ldots,a_{r+1}; N_1,\ldots,N_{r+1})

\displaystyle \subset B_N(\alpha_1,\ldots,\alpha_r;\rho_1,\ldots,\rho_r)

for some explicit {\epsilon>0} depending only on {r} (in fact one can take {\epsilon = (r+1)^{-2(r+1)}}); this is (a slight modification of) Lemma 4.22 of my book with Van Vu.

In the special case when {r=1}, one can make a significantly more detailed description of the link between rank one Bohr sets and rank two generalised arithmetic progressions, by using the classical theory of continued fractions, which among other things gives a fairly precise formula for the generators {a_1,a_2} and lengths {N_1,N_2} of the generalised arithmetic progression associated to a rank one Bohr set {B_N(\alpha;\rho)}. While this connection is already implicit in the continued fraction literature (for instance, in the classic text of Hardy and Wright), I thought it would be a good exercise to work it out explicitly and write it up, which I will do below the fold.

It is unfortunate that the theory of continued fractions is restricted to the rank one setting (it relies very heavily on the total ordering of one-dimensional sets such as {{\bf Z}} or {{\bf R}}). A higher rank version of the theory could potentially help with questions such as the Littlewood conjecture, which remains open despite a substantial amount of effort and partial progress on the problem. At the end of this post I discuss how one can use the rank one theory to rephrase the Littlewood conjecture as a conjecture about a doubly indexed family of rank four progressions, which can be used to heuristically justify why this conjecture should be true, but does not otherwise seem to shed much light on the problem.

— 1. Continued fractions —

One can present the theory of continued fractions in a number of ways. The classical approach is simply to work out the algebraic identities relating the various partial fractions of the continued fraction expansion. A more modern approach is to rewrite everything in terms of the action of the special linear group {SL_2({\bf Z})}, either on the Euclidean plane {{\bf R}^2}, the projective line {{\bf RP}^1}, or the hyperbolic plane {{\bf H}^2}. Here, I will split the difference and adopt a geometric perspective, interpreting continued fractions in terms of the geometry of a ray and a lattice in a plane; thus the continued fraction itself will not be the fundamental object of study, but only emerge as a derived quantity from the underlying geometry.

More specifically, we consider the lattice {{\bf Z}^2} in {{\bf R}^2}. We have the standard basis {e_1 := (1,0), e_2 := (0,1)} for this lattice. More generally, any two lattice elements {v_1 = (p_1,q_1), v_2 = (p_2,q_2)} with {v_1 \wedge v_2 := p_1 q_2 - p_2 q_1} equal to {1} forms an (oriented) basis, thanks to Cramer’s rule. (One can of course identify the pair {(v_1,v_2)} with an element of {SL_2({\bf Z})}, and indeed this would be an appropriate and modern way of thinking about these pairs; but for some mostly idiosyncratic reasons I will eschew this sort of language in this presentation.)

Given a basis {(v_1,v_2)} for {{\bf Z}^2}, we can define the associated cone {C(v_1,v_2) := \{ t_1 v_1 + t_2 v_2: t_1,t_2 \geq 0 \}}. Note that if {(v_1,v_2)} is a basis, then so are {(v_1+v_2,v_2)} and {(v_1,v_1+v_2)}; we will call these pairs the upward shift and rightward shift of {(v_1,v_2)} respectively. Furthermore, the cones of the two shifted bases essentially partition the cone of the original basis. More precisely, we have

\displaystyle C(v_1,v_2) = C(v_1+v_2,v_2) \cup C(v_1,v_1+v_2)

and {C(v_1+v_2,v_2) \cap C(v_1,v_1+v_2)} consists of a single ray with rational slope.

Now let {\alpha} be a positive real number, which we will take to be irrational to avoid some minor notational issues involving termination of the continued fraction process. The ray {\ell := \{ (t,t\alpha): t \geq 0 \}} then lies in the cone {C(e_1,e_2)}, and avoids all the lattice points in {{\bf Z}^2} except for the origin. By the preceding discussion, if {(v_1,v_2)} is a basis of {{\bf Z}^2} whose cone {C(v_1,v_2)} contains {\ell}, then exactly one of the two shifted bases {(v_1,v_1+v_2)}, {(v_1+v_2,v_2)} has their cone containing {\ell}.

We can then iterate this process, starting with the basis {(e_1,e_2)} and continually narrowing the cone of the basis around {\ell} to create a sequence of bases {(v_1^{(k)}, v_2^{(k)})} for {k=0,1,2,\ldots}, with {(v_1^{(0)},v_2^{(0)}) = (e_1,e_2)}, and {(v_1^{(k+1)},v_2^{(k+1)})} equal to either the rightward shift {(v_1^{(k)},v_1^{(k)}+v_2^{(k)})} or upward shift {(v_1^{(k)}+v_2^{(k)}, v_2^{(k)})} of {(v_1^{(k)}, v_2^{(k)})}, and the cones {C(v_1^{(k)}, v_2^{(k)})} decreasing to {\ell}. We will call the {(v_1^{(k)}, v_2^{(k)})} the semiconvergent basis sequence of {\alpha}.

We can write the semiconvergent basis sequence {(v_1^{(k)},v_2^{(k)})} in coordinates as {v_1^{(k)} = (q_1^{(k)}, p_1^{(k)})} and {v_2^{(k)} = (q_2^{(k)}, p_2^{(k)})}, then the {p_1^{(k)}, p_2^{(k)}, q_1^{(k)}, q_2^{(k)}} are monotone non-decreasing sequences of natural numbers that increase to infinity. The slopes {\frac{p_1^{(k)}}{q_1^{(k)}}, \frac{p_2^{(k)}}{q_2^{(k)}}} of {v_1^{(k)}, v_2^{(k)}} thus converge to {\alpha} from below and above respectively, and are known as the best lower rational approximants and best upper rational approximants of {\alpha}, for reasons that we shall explain shortly.

We can track the dynamics of the subconvergent basis sequence by using {(1,\alpha)} and {e_2} as a basis for {{\bf R}^2}, thus measuring the extent to which {v_1^{(k)}} and {v_2^{(k)}} fall below and above the ray {\ell} respectively. Indeed, if we write

\displaystyle v_1^{(k)} = q_1^{(k)} (1,\alpha) - \epsilon_1^{(k)} e_2


\displaystyle v_2^{(k)} = q_2^{(k)} (1,\alpha) + \epsilon_2^{(k)} e_2

then the residual errors {\epsilon_1^{(k)}, \epsilon_2^{(k)}} are positive reals, which initially take the values

\displaystyle \epsilon_1^{(0)} = \alpha; \epsilon_2^{(0)} = 1

and evolve according to the recursion

\displaystyle \epsilon_1^{(k+1)} = \epsilon_1^{(k)}; \epsilon_2^{(k+1)} = \epsilon_2^{(k)} - \epsilon_1^{(k)}

when {\epsilon_2^{(k)} > \epsilon_1^{(k)}} (rightward shift case), or

\displaystyle \epsilon_1^{(k+1)} = \epsilon_1^{(k)}-\epsilon_2^{(k)}; \epsilon_2^{(k+1)} = \epsilon_2^{(k)}

when {\epsilon_2^{(k)} < \epsilon_1^{(k)}} (upward shift case). (Note that the border case {\epsilon_1^{(k)}=\epsilon_2^{(k)}} does not occur when {\alpha} is irrational.) In particular we see that the {\epsilon_1^{(k)}} and {\epsilon_2^{(k)}} decrease monotonically to zero.

We may now justify the terminology of best rational approximation:

Proposition 1 (Best rational approximation)Let {N > 0}, and let {(v_1^{(k)}, v_2^{(k)})} be the last basis in the semiconvergent basis sequence for which {q_1^{(k)}, q_2^{(k)} \leq N}. Then for any natural numbers {0 < q \leq N} and {p \geq 0}, one has

\displaystyle p - q \alpha \geq p_2^{(k)} - q_2^{(k)} \alpha = \epsilon_2^{(k)}


\displaystyle \frac{p}{q} \geq \frac{p_2^{(k)}}{q_2^{(k)}} > \alpha


\displaystyle p - q \alpha \leq p_1^{(k)} - q_1^{(k)} \alpha = -\epsilon_1^{(k)}


\displaystyle \frac{p}{q} \leq \frac{p_1^{(k)}}{p_1^{(k)}} < \alpha.

Proof: As {v_1^{(k)}, v_2^{(k)}} form a basis for {{\bf Z}^2}, we have

\displaystyle (q,p) = a v_1^{(k)} + b v_2^{(k)}

for some integers {a, b}; in particular,

\displaystyle p - q \alpha = a \epsilon_2^{(k)} - b \epsilon_1^{(k)}

This already gives the claim when {a > 0} and {b \leq 0}, or when {a \leq 0} and {b > 0}. The case {a,b \leq 0} cannot occur since this would make {q \leq 0}, so we are left with the case {a,b > 0}. But in this case, we have {q \geq q_1^{(k)} + q_2^{(k)}}, and hence {q > N} by construction, again a contradiction. \Box

We can also track the dynamics of the semiconvergent basis sequence by introducing the relative slope {\alpha^{(k)} \in (0,+\infty)} of {\ell} with respect to the cone {C(v_1^{(k)}, v_2^{(k)})}, defined as the unique positive real number such that

\displaystyle \ell = \{ t ( v_1^{(k)} + \alpha^{(k)} v_2^{(k)}) \}.

As {\alpha} is irrational, the {\alpha^{(k)}} are all irrational. It is not difficult to see that the {\alpha^{(k)}} are defined by the following recursion: {\alpha^{(0)} = \alpha}, and one has {\alpha^{(k+1)} = \alpha^{(k)}-1} when {\alpha^{(k)}>1}, and {\frac{1}{\alpha^{(k+1)}} = \frac{1}{\alpha^{(k)}}-1} when {\alpha^{(k)} < 1}. Also, the former case arises when {(v_1^{(k+1)}, v_2^{(k+1)})} is the upward shift of {(v_1^{(k)},v_2^{(k)})}, and the latter case arises when we have a rightward shift instead.

The semiconvergent basis sequence {(v_1^{(k)}, v_2^{(k)})} can be viewed as a sequence of {a_0} upward shifts for some non-negative integer {a_0}, followed by {a_1} rightward shifts for some positive integer {a_1}, then {a_2} upward shifts for some positive integer {a_2}, and so forth. By tracking what happens to the relative slope {\alpha^{(k)}} and its reciprocal {1/\alpha^{(k)}}, we conclude that

\displaystyle \alpha = a_0 + \frac{1}{\alpha_1}

for some {\alpha_1 > 1},

\displaystyle \alpha_1 = a_1 + \frac{1}{\alpha_2}

for some {\alpha_2 > 0}, and so forth, leading to the familiar continued fraction expansion

\displaystyle \alpha = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \ldots}}.

We recursively define the sequence {w_{-2}, w_{-1}, w_0, \ldots} of lattice vectors by the formulae

\displaystyle w_{-2} = e_1; w_{-1} := e_2


\displaystyle w_n = a_n w_{n-1} + w_{n-2}

for {n \geq 0}, thus

\displaystyle w_{-2} = (1,0)

\displaystyle w_{-1} = (0,1)

\displaystyle w_0 = (1, a_0)

\displaystyle w_1 = (a_1, a_0 a_1 + 1)

\displaystyle w_2 = (1 + a_1 a_2, a_0 + a_0 a_1 a_2 + a_2)

etc. We may then describe the bases {(v_1^{(k)},v_2^{(k)})} in terms of the {w_n} as follows: if

\displaystyle k = a_0 + \ldots + a_{n-1} + j

for some {0 \leq j \leq a_n} and {n \geq 0}, then one has

\displaystyle (v_1^{(k)}, v_2^{(k)}) = (w_{n-1}, w_{n-2}+jw_{n-1})

if {n} is even, and

\displaystyle (v_1^{(k)}, v_2^{(k)}) = (w_{n-2}+jw_{n-1}, w_{n-1})

if {n} is odd. In particular, the sequence {(v_1^{(k)},v_2^{(k)})} of bases contains the sequence

\displaystyle (w_{-2}, w_{-1}), (w_{0}, w_{-1}), (w_0, w_1), (w_2, w_1), \ldots

as a subsequence, representing the places is the sequence in which one changes from a rightward shift to an upward shift or vice versa. In particular, if {w_n =: (q_n, p_n)}, then the slopes {p_n/q_n} (known as successive convergents to {\alpha}) converge to {\alpha} from below when {n} is even, and from above when {n} is odd. As bases have determinant {+1}, we also see that

\displaystyle p_n q_{n+1} - p_{n+1} q_n = (-1)^n. \ \ \ \ \ (1)


By construction, we have the recurrences

\displaystyle p_n = a_n p_{n-1} + p_{n-2}


\displaystyle q_n = a_n q_{n-1} + q_{n-2}

with initial conditions {(q_{-2}, p_{-2}) = (1,0)} and {(q_{-1}, p_{-1}) = (0,1)}, thus

\displaystyle \frac{p_{-2}}{q_{-2}} = \frac{0}{1} = 0

\displaystyle \frac{p_{-1}}{q_{-1}} = \frac{1}{0} = \infty

\displaystyle \frac{p_0}{q_0} = \frac{a_0}{1} = a_0

\displaystyle \frac{p_1}{q_1} = \frac{a_0 a_1 + 1}{a_1} = a_0 + \frac{1}{a_1}

\displaystyle \frac{p_2}{q_2} = \frac{a_0+a_0a_1a_2+a_2}{1+a_1a_2} = a_0 + \frac{1}{a_1+\frac{1}{a_2}}

etc. From an induction we see that the {p_n, q_n} are a monotonically increasing sequence of natural numbers. Indeed, they must increase at least as fast as the Fibonacci sequence {F_0 =F_1 = 1, F_2 = 2, F_3 = 3, F_4 = 5, \ldots}; from an easy induction we see that {p_{n+k} \geq F_k p_n}, {q_{n+k} \geq F_k q_n} for all {n,k \geq 0}. In particular, the {p_n,q_n} must grow at least exponentially fast in {n}.

As with the basis sequence {(v_1^{(k)}, v_2^{(k)})}, we can express the {w_n} in the {(1,\alpha), e_2} basis:

\displaystyle w_n = q_n (1,\alpha) - (-1)^n \epsilon_n e_2

or equivalently

\displaystyle p_n = \alpha q_n - (-1)^n \epsilon_n.

Then the {\epsilon_n} are positive reals, with {\epsilon_{-2} = \alpha}, {\epsilon_{-1} = 1}, and

\displaystyle \epsilon_n = \epsilon_{n-2} - a_n \epsilon_{n-1}.

By construction, we see that the {\epsilon_n} are monotone decreasing in {n} for {n \geq 0}; indeed, we see that {\epsilon_n} are essentially the output of the Euclidean algorithm applied to the real numbers {\alpha,1}. From (1)we see that

\displaystyle \epsilon_n q_{n+1} + \epsilon_{n+1} q_n = 1.

Since {\epsilon_n \geq \epsilon_{n+1}} and {q_{n+1} \geq q_n} for {n \geq 0}, we see in particular that

\displaystyle \frac{1}{2q_{n+1}} \leq \epsilon_n \leq \frac{1}{q_{n+1}}.

In particular we have a fairly precise description of how well the convergents {p_n/q_n} approximate {\alpha}:

\displaystyle \frac{1}{2q_nq_{n+1}} \leq |\alpha - \frac{p_n}{q_n}| \leq \frac{1}{q_n q_{n+1}}.

In particular, we have

\displaystyle \frac{1}{2q_{n+1}} \leq \| q_n \alpha \|_{{\bf R}/{\bf Z}} \leq \frac{1}{q_{n+1}}. \ \ \ \ \ (2)


As the {p_n/q_n} are best rational approximants, we thus also have

\displaystyle \| q \alpha \|_{{\bf R}/{\bf Z}} \geq \frac{1}{2q_{n+1}} \ \ \ \ \ (3)


whenever {1 \leq q \leq q_n}.

Remark 1 From the above inequalities one can easily establish the Dirichlet approximation theorem and the (one-dimensional) Kronecker approximation theorem.

— 2. Bohr sets —

Now we compare rank one Bohr sets {B_N(\alpha;\rho)} to rank two progressions {P(a_1,a_2; N_1,N_2)}. It turns out that the best progressions to use here come from using the denominators {q_1^{(k)}, q_2^{(k)}} of a semiconvergent basis {(v_1^{(k)}, v_2^{(k)})} as the generators. Indeed, if

\displaystyle q \in P( q_1^{(k)}, q_2^{(k)}; N_1, N_2 )

then we have

\displaystyle \| q \alpha \|_{{\bf R}/{\bf Z}} \leq N_1 \|q_1^{(k)} \alpha \|_{{\bf R}/{\bf Z}} + N_2 \| q_2^{(k)} \alpha \|_{{\bf R}/{\bf Z}} \leq N_1 \epsilon^{(k)}_1 + N_2 \epsilon^{(k)}_2


\displaystyle |q| \leq N_1 q_1^{(k)} + N_2 q_2^{(k)}.

Thus we have

\displaystyle P( q_1^{(k)}, q_2^{(k)}; N_1, N_2 ) \subset B_N(\alpha;\rho)


\displaystyle N_1 q_1^{(k)} + N_2 q_2^{(k)} \leq N \hbox{ and } N_1 \epsilon^{(k)}_1 + N_2 \epsilon^{(k)}_2 \leq \rho.

In the converse direction, suppose that {q \in B_N(\alpha;\rho)}, thus {|q| \leq N} and one has {|p-q\alpha| \leq \rho} for some integer {p}. As {(v_1^{(k)}, v_2^{(k)})} is a basis for {{\bf Z}^2}, we have

\displaystyle (q,p) = a v_1^{(k)} + b v_2^{(k)}

for some integers {a, b}. Taking wedge products, we see that

\displaystyle a = (q,p) \wedge v_2^{(k)}; \quad b = - (q,p) \wedge v_1^{(k)}.

We write {(q,p) = q (1,\alpha) + \epsilon e_2} for some {|\epsilon| \leq \rho}, and similarly write {v_i^{(k)} = q_i^{(k)} (1,\alpha) \pm \epsilon_i^{(k)} e_2} for {i=1,2}, to conclude that

\displaystyle |a| \leq |q| \epsilon_2^{(k)} + |\epsilon| q_2^{(k)} \leq N \epsilon_2^{(k)} + \rho q_2^{(k)}

and similarly

\displaystyle |b| \leq N \epsilon_1^{(k)} + \rho q_1^{(k)}.

We conclude that

\displaystyle B_N(\alpha;\rho) \subset P( q_1^{(k)}, q_2^{(k)}; N_1, N_2 )


\displaystyle N \epsilon_2^{(k)} + \rho q_2^{(k)} \leq N_1 \hbox{ and } N \epsilon_1^{(k)} + \rho q_1^{(k)} \leq N_2.

It is now a routine matter to optimise the parameters {k, N_1, N_2} to obtain a good fit. Suppose for instance that

\displaystyle \frac{N}{2 q_1^{(k)} q_2^{(k)}} \leq \rho \leq \frac{N}{q_1^{(k)} q_2^{(k)}} \ \ \ \ \ (4)


for some {k \geq 0}. If we then set

\displaystyle N_1 := \frac{1}{2} q_2^{(k)} \rho; \quad N_2 := \frac{1}{2} q_1^{(k)} \rho,

then we have

\displaystyle N_1 q_1^{(k)} + N_2 q_2^{(k)} = q_1^{(k)} q_2^{(k)} \rho \leq N.

Also, since {(v_1^{(k)}, v_2^{(k)})} is a basis, we have {v_1^{(k)} \wedge v_2^{(k)} = 1}, and thus

\displaystyle q_1^{(k)} \epsilon^{(k)}_2 + q_2^{(k)} \epsilon^{(k)}_1 = 1.

In particular,

\displaystyle N_1 \epsilon^{(k)}_1 + N_2 \epsilon^{(k)}_2 \leq \frac{N_1}{q_2^{(k)}} + \frac{N_2}{q_1^{(k)}}

\displaystyle \leq \rho.

We thus conclude from the preceding discussion that

\displaystyle P( q_1^{(k)}, q_2^{(k)}; N_1, N_2 ) \subset B_N(\alpha;\rho).

On the other hand, we have

\displaystyle N \epsilon_2^{(k)} + \rho q_2^{(k)} \leq \frac{N}{q_1^{(k)}} + 2 N_1

\displaystyle \leq 4N_1 + 2N_1 = 6 N_1

and similarly

\displaystyle N \epsilon_1^{(k)} + \rho q_1^{(k)} \leq 6N_2

and thus by the preceding discussion

\displaystyle B_N(\alpha;\rho) \subset P( q_1^{(k)}, q_2^{(k)}; 6N_1, 6N_2 )

and similarly

\displaystyle B_{N/6}(\alpha;\rho/6) \subset P( q_1^{(k)}, q_2^{(k)}; N_1, N_2 ).

Thus, in this case, the rank one Bohr set {B_N(\alpha;\rho)} is morally the same object (up to constants) as the rank two progression {P( q_1^{(k)}, q_2^{(k)}; N_1, N_2 )}.

Things are a bit more complicated in the regime

\displaystyle \frac{N}{q_1^{(k+1)} q_2^{(k+1)}} < \rho < \frac{N}{2 q_1^{(k)} q_2^{(k)}}. \ \ \ \ \ (5)


For sake of discussion, let us suppose that {(v_1^{(k+1)}, v_2^{(k+1)})} is an upward shift of {(v_1^{(k)}, v_2^{(k)})}, so that {q_1^{(k+1}) = q_1^{(k)} + q_2^{(k)}} and {q_2^{(k+1}) = q_2^{(k)}}. From (5) we see that {q_1^{(k+1)} > 2 q_1^{(k)}} and hence {q_1^{(k)} < q_2^{(k)}}. Also, we have {\epsilon_1^{(k+1)} = \epsilon_1^{(k)} - \epsilon_2^{(k)}}, so in particular, {\epsilon_2^{(k)} \leq \epsilon_1^{(k)} \leq \frac{1}{q_2^{(k)}}}. If we now set

\displaystyle N_1 := \frac{1}{2} \rho q_2^{(k)}; N_2 := \frac{N}{4q_2^{(k)}}

then we have

\displaystyle N_1 q_1^{(k)} + N_2 q_2^{(k)} \leq \frac{1}{4} N + \frac{1}{4} N \leq N


\displaystyle N_1 \epsilon^{(k)}_1 + N_2 \epsilon^{(k)}_2 \leq \frac{1}{2} \rho + \frac{1}{4} \frac{N}{(q_2^{(k)})^2}

\displaystyle \leq \frac{1}{2} \rho + \frac{1}{2} \frac{N}{q_1^{(k+1)} q_2^{(k+1)}}

\displaystyle \leq \rho

and so

\displaystyle P( q_1^{(k)}, q_2^{(k)}; N_1, N_2 ) \subset B_N(\alpha;\rho).

Conversely, we have

\displaystyle N \epsilon_2^{(k)} + \rho q_2^{(k)} \leq \frac{N}{q_2^{(k)}} + 2 N_1

\displaystyle \leq 2 \frac{N}{q_1^{(k+1)} q_2^{(k+1)}} q_2^{(k)} + 2N_1

\displaystyle \leq 4 N_1 + 2N_1 = 6N_1


\displaystyle N \epsilon_1^{(k)} + \rho q_1^{(k)} \leq \frac{N}{q_2^{(k)}} + \frac{N}{2q_2^{(k)}}

\displaystyle = 6 N_2

and so once again we have

\displaystyle B_N(\alpha;\rho) \subset P( q_1^{(k)}, q_2^{(k)}; 6N_1, 6N_2 )


\displaystyle B_{N/6}(\alpha;\rho/6) \subset P( q_1^{(k)}, q_2^{(k)}; N_1, N_2 ).

Thus again we see that in this case {B_N(\alpha;\rho)} is morally the same object as {P(q_1^{(k)}, q_2^{(k)}; N_1, N_2)}.

Note that as {\rho} shrinks, the lengths {N_1,N_2} shrink also, though every so often there is a discontinuity when {k} is incremented, thus shearing the generators {q_1^{(k)}, q_2^{(k)}} as well as the lengths {N_1,N_2}. (Technically, there is also a discontinuity when one passes from (4) to (5), but this is an artificial discontinuity and can be eliminated by performing a smoother interpolation between these two regimes which we omit.) Among other things, the above relationships give a rough description of the cardinality of the Bohr set {B_N(\alpha;\rho)}; one has

\displaystyle |B_N(\alpha;\rho)| \sim (1+N_1) (1+N_2)

and thus (by unifying all the cases) one has

\displaystyle |B_N(\alpha;\rho)| \sim 1 + N \rho + \rho (q_1^{(k)}+q_2^{(k)})


\displaystyle \frac{N}{q_1^{(k+1)} q_2^{(k+1)}} \leq \rho \leq \frac{N}{q_1^{(k)} q_2^{(k)}}.

It is a shame that there is no similarly precise formula known for the size of a rank two Bohr set {|B_N(\alpha_1,\alpha_2; \rho_1,\rho_2)|}, as this would likely lead (among other things) to a resolution of the Littlewood conjecture.

— 3. A reformulation of the Littlewood conjecture —

The Littlewood conjecture asserts that for any two real numbers {\alpha,\beta}, one has

\displaystyle \lim \inf_{n \rightarrow \infty} n \|n\alpha\|_{{\bf R}/{\bf Z}} \|n\beta\|_{{\bf R}/{\bf Z}} = 0.

The conjecture remains open, although there are some highly non-trivial partial results, such as the result of Einsiedler, Katok, and Lindenstrauss that the set of pairs {(\alpha,\beta)} for which the Littlewood conjecture fails is so small that it has Hausdorff dimension zero.

If a pair {(\alpha,\beta)} was a counterexample to the Littlewood conjecture, then

\displaystyle n \|n\alpha\|_{{\bf R}/{\bf Z}} \|n\beta\|_{{\bf R}/{\bf Z}} \gg 1

for all positive integers {n}. In particular, one has

\displaystyle n \|n\alpha\|_{{\bf R}/{\bf Z}} \gg 1

for all {n} (in other words, {\alpha} is badly approximable by rationals, and is in particular irrational). Applying (2), we conclude that {q_{n+1} \ll q_n} for all {n}, or equivalently that the coefficients {a_n} of the continued fraction expansion of {\alpha} are bounded. (Conversely, using (2) and (3) we see that if {\alpha} is irrational with bounded continued fraction coefficients, then it is badly approximable by rationals.) Similarly for {\beta}. This is already enough to establish without much additional work that the Littlewood conjecture is true for almost all {\alpha,\beta} (in the sense of Lebesgue measure), although it does not come close to the stronger result of Einseidler, Katok, and Lindenstrauss mentioned above (it is known that the set of badly approximable numbers has Hausdorff dimension one).

One can reformulate the Littlewood conjecture in terms of the denominators {q_1,q_2,\ldots} of the convergents to {\alpha}, and the denominators {r_1,r_2,\ldots} of the convergents to {\beta}:

Proposition 2 Let {\alpha,\beta} be two real numbers. Then the following are equivalent:

  • (i) {\alpha,\beta} form a counterexample to the Littlewood conjecture.
  • (ii) {\alpha,\beta} are badly approximable, and there is an {\epsilon>0} such that the rank four progressions

    \displaystyle P( q_n, q_{n+1}, r_m, r_{m+1}; \epsilon q_n^{-1/3} r_m^{2/3}, \epsilon q_n^{-1/3} r_m^{2/3}, \ \ \ \ \ (6)

    \displaystyle \epsilon q_m^{2/3} r_m^{-1/3}, \epsilon q_n^{2/3} r_m^{-1/3})

    are proper for all {n,m \geq 0}.

Recall that a progression {P(a_1,\ldots,a_r;N_1,\ldots,N_r)} is said to be proper if all of the elements {a_1 n_1 + \ldots + a_r n_r}, {|n_i| \leq N_i} of the progression are distinct.

Proof: Let us first show that (i) implies (ii). Let {\alpha,\beta} be a counterexample to the Littlewood conjecture, thus

\displaystyle |N| \|N\alpha\|_{{\bf R}/{\bf Z}} \|N\beta\|_{{\bf R}/{\bf Z}} \gg 1 \ \ \ \ \ (7)


for all non-zero integers {n}. We have already seen that {\alpha,\beta} are badly approximable (so in particular {q_{n+1} \ll q_n} and {r_{m+1} \ll r_n}. Now let {\epsilon > 0} be a sufficiently small number, and suppose that the progression (6) is not proper for some {n,m}. Then there is a non-trivial solution to the equation

\displaystyle a q_n + a' q_{n+1} = b r_m + b' r_{m+1} \ \ \ \ \ (8)


for some integers {a,a',b,b'}, not all zero, with {a,a' = O(\epsilon q_n^{-1/3} r_m^{2/3})} and {b,b' = O(\epsilon q_n^{2/3} r_m^{1/3})}. Let {N} be the integer in (8), then {N} is non-zero and {N = O( \epsilon q_n^{2/3} r_m^{2/3} )}. Also, from (2) we see that

\displaystyle \| N \alpha \|_{{\bf R}/{\bf Z}} \leq \frac{|a|}{q_{n+1}} + \frac{|a'|}{q_{n+2}} = O( \epsilon q_n^{-4/3} r_m^{2/3} )

and similarly

\displaystyle \| N \beta \|_{{\bf R}/{\bf Z}} = O( \epsilon q_n^{2/3} r_m^{-4/3} )

and thus

\displaystyle |N| \|N\alpha\|_{{\bf R}/{\bf Z}} \| N \beta \|_{{\bf R}/{\bf Z}} \ll \epsilon^3.

Setting {\epsilon} small enough, we contradict (7).

Now we show that (ii) implies (i). Let {\alpha,\beta,\epsilon} be as in (ii). Suppose for contradiction that (i) fails, thus we can find a sequence {N = N_i} of integers going off to infinity such that

\displaystyle |N| \|N\alpha\|_{{\bf R}/{\bf Z}} \|N\beta\|_{{\bf R}/{\bf Z}} = o(1),

where {o(1)} denotes a quantity that goes to zero as {N} (or {i}) goes to infinity. In particular, one can find {q,r \geq 1} (depending on {N}) such that

\displaystyle N = o( q^{2/3} r^{2/3} )

\displaystyle \|N\alpha \|_{{\bf R}/{\bf Z}} = o( q^{-4/3} r^{2/3} )

\displaystyle \|N\beta\|_{{\bf R}/{\bf Z}} = o( q^{2/3} r^{-4/3} ).

(Indeed, one can pick {q} to be {(N / \|N\alpha\|_{{\bf R}/{\bf Z}})^{1/2}} and {r} to be {(N/\|N\beta\|_{{\bf R}/{\bf Z}})^{1/2}}.) As the {q_n} increase in a lacunary fashion (thanks to the bad approximability of {\alpha}), we can find {n} such that {q_n \sim q}; similarly we may find {m} such that {r_m \sim r}, thus

\displaystyle N = o( q_n^{2/3} r_m^{2/3} )

\displaystyle \|N\alpha \|_{{\bf R}/{\bf Z}} = o( q_n^{-4/3} r_m^{2/3} )

\displaystyle \|N\beta\|_{{\bf R}/{\bf Z}} = o( q_n^{2/3} r_m^{-4/3} ).

Thus {N} lies in the Bohr sets

\displaystyle B_{o(q_n^{2/3} r_m^{2/3} )}( \alpha; o( q_n^{-4/3} r_m^{2/3} ) )


\displaystyle B_{o(q_n^{2/3} r_m^{2/3} )}( \beta; o( q_n^{2/3} r_m^{-4/3} ) ).

Applying the analysis of the preceding section, we conclude that {N} lies in the rank two progressions

\displaystyle P( q_n, q_{n+1}; o( q_n^{-1/3} r_m^{2/3} ), o( q_n^{-1/3} r_m^{2/3} ) )


\displaystyle P( r_m, r_{m+1}; o( q_n^{2/3} r_m^{-1/3} ), o( q_n^{2/3} r_m^{-1/3} ) )

and is non-zero, and so the rank four progression

\displaystyle P( q_n, q_{n+1}, r_m, r_{m+1}; o( q_n^{-1/3} r_m^{2/3} ), o( q_n^{-1/3} r_m^{2/3} ), o( q_n^{2/3} r_m^{-1/3} ), o( q_n^{2/3} r_m^{-1/3} ) )

is not proper. But this contradicts (ii) for {N} large enough. \Box

We can now give a heuristic explanation as to why there should not be any counterexample {\alpha,\beta} to the Littlewood conjecture. Such a counterexample can be completely described by the continued fraction coefficients {a_0,a_1,a_2,\ldots} for {\alpha}, and the continued fraction coefficients {b_0,b_1,b_2,\ldots} for {\beta}. These sequences need to be bounded by the bad approximability property; let us suppose that they are both bounded by some bound {M}. Thus, for any {n_0,m_0}, the number of choices for {a_0,a_1,\ldots,a_{n_0}} and {b_0,\ldots,b_{m_0}} grows at most exponentially in {n_0,m_0} (it is about {M^{n_0+m_0}}). Of course, these coefficients then determine the denominators {q_1,\ldots,q_{n_0}} and {r_1,\ldots,r_{m_0}} by the recurrences given previously.

On the other hand, by the above proposition, there needs to be an {\epsilon > 0} such that for each {n \leq n_0} and {m \leq m_0}, the progression (6) is proper. We can heuristically gauge how likely this occurs by the following numerology. For fixed {n,m} (and making the non-degeneracy assumptions that {q_n^{-1/3} r_m^{2/3}, q_n^{2/3} r_m^{-1/3} \gg 1}), there are about {\epsilon^4 q_n^{2/3} r_m^{2/3}} different ways to form a sum of the form

\displaystyle a q_n + a' q_{n+1} + b r_m + b' r_{m+1}

with {a,a' = O(\epsilon q_n^{-1/3} r_m^{2/3})} and {b,b' = O(\epsilon q_n^{2/3} r_m^{-1/3})}. These sums have magnitude about {O( \epsilon q_n^{2/3} r_m^{2/3} )}. Thus, we expect that the probability that all non-trivial sums avoid zero (which is basically what is needed for (6) to be proper) to be at most {1-\delta} for some {\delta>0} depending only on {\epsilon}.

On the other hand, the number of eligible pairs {(n,m)} for which the progression (6) is non-degenerate enough to have a chance of being proper grows quadratically in {n_0,m_0}. Due to the exponential growth of {q_n} and {r_m}, it is reasonable to suppose that the properness of each of the progressions (6) behave like independent (or at least very weakly coupled) events as {n,m} vary (viewing {a_0,\ldots,a_{n_0}} and {b_0,\ldots,b_{m_0}} as being drawn uniformly from all sequences bounded by {M}). If we assume that this independence is so strong as to be like joint independence (and here is where we really make a serious leap of faith), then we therefore expect the probability that a randomly chosen choice of coefficients has all of the (6) proper should decay quadratic-exponentially in {n_0,m_0} (i.e. it should be something like {(1-\delta)^{n_0 m_0}}, particularly if we choose {n_0} and {m_0} to be comparable in magnitude). As this beats the entropy of {M^{n_0+m_0}} for {n_0,m_0} large enough, we thus expect that for any given {M, \epsilon}, there should not in fact be any counterexamples to (ii) (and hence to the Littlewood conjecture) with this choice of parameters.

This heuristic derivation of the Littlewood conjecture uses a common (but highly nonrigorous) probabilistic argument, in which one argues that there are so many ways in which a candidate can fail to be a counterexample to the conjecture that no counterexample actually exists. This type of heuristic is common in number theory, for instance justifying the even Goldbach conjecture (for sufficiently large even numbers, at least). Unfortunately, we do not know how to rule out the existence of some bizarre “conspiracy” between the coefficients {a_n} and {b_m} that manage to align all the possible (and supposedly independent) failure events in such a way that an extremely lucky and exceptional choice of coefficients manages to evade all of these events and end up as a counterexample to the conjecture. But the best we can do with current technology is to show that such conspiracies, if they exist at all, are very rare (with the aforementioned result of Einsiedler, Katok, and Lindenstrauss being the strongest result currently known of this type).