Let be an element of the unit circle, let , and let . We define the (rank one) Bohr set to be the set
where is the distance to the origin in the unit circle (or equivalently, the distance to the nearest integer, after lifting up to ). 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 .
Observe that Bohr sets enjoy the doubling property
thus doubling the Bohr set doubles both the length parameter and the radius parameter . As such, these Bohr sets resemble two-dimensional balls (or boxes). Indeed, one can view as the preimage of the two-dimensional box under the homomorphism .
Another class of finite set with two-dimensional behaviour is the class of (rank two) generalised arithmetic progressions
with and Indeed, we have
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 Bohr sets
and the rank generalised arithmetic progressions
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 Bohr set , there is a rank generalised arithmetic progression for which one has the containments
for some explicit depending only on (in fact one can take ); this is (a slight modification of) Lemma 4.22 of my book with Van Vu.
In the special case when , 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 and lengths of the generalised arithmetic progression associated to a rank one Bohr set . 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 or ). 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 , either on the Euclidean plane , the projective line , or the hyperbolic plane . 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 in . We have the standard basis for this lattice. More generally, any two lattice elements with equal to forms an (oriented) basis, thanks to Cramer’s rule. (One can of course identify the pair with an element of , 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 for , we can define the associated cone . Note that if is a basis, then so are and ; we will call these pairs the upward shift and rightward shift of respectively. Furthermore, the cones of the two shifted bases essentially partition the cone of the original basis. More precisely, we have
and consists of a single ray with rational slope.
Now let 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 then lies in the cone , and avoids all the lattice points in except for the origin. By the preceding discussion, if is a basis of whose cone contains , then exactly one of the two shifted bases , has their cone containing .
We can then iterate this process, starting with the basis and continually narrowing the cone of the basis around to create a sequence of bases for , with , and equal to either the rightward shift or upward shift of , and the cones decreasing to . We will call the the semiconvergent basis sequence of .
We can write the semiconvergent basis sequence in coordinates as and , then the are monotone non-decreasing sequences of natural numbers that increase to infinity. The slopes of thus converge to from below and above respectively, and are known as the best lower rational approximants and best upper rational approximants of , for reasons that we shall explain shortly.
We can track the dynamics of the subconvergent basis sequence by using and as a basis for , thus measuring the extent to which and fall below and above the ray respectively. Indeed, if we write
then the residual errors are positive reals, which initially take the values
and evolve according to the recursion
when (rightward shift case), or
when (upward shift case). (Note that the border case does not occur when is irrational.) In particular we see that the and decrease monotonically to zero.
We may now justify the terminology of best rational approximation:
Proposition 1 (Best rational approximation)Let , and let be the last basis in the semiconvergent basis sequence for which . Then for any natural numbers and , one has
Proof: As form a basis for , we have
for some integers ; in particular,
This already gives the claim when and , or when and . The case cannot occur since this would make , so we are left with the case . But in this case, we have , and hence by construction, again a contradiction.
We can also track the dynamics of the semiconvergent basis sequence by introducing the relative slope of with respect to the cone , defined as the unique positive real number such that
As is irrational, the are all irrational. It is not difficult to see that the are defined by the following recursion: , and one has when , and when . Also, the former case arises when is the upward shift of , and the latter case arises when we have a rightward shift instead.
The semiconvergent basis sequence can be viewed as a sequence of upward shifts for some non-negative integer , followed by rightward shifts for some positive integer , then upward shifts for some positive integer , and so forth. By tracking what happens to the relative slope and its reciprocal , we conclude that
for some ,
for some , and so forth, leading to the familiar continued fraction expansion
We recursively define the sequence of lattice vectors by the formulae
for , thus
etc. We may then describe the bases in terms of the as follows: if
for some and , then one has
if is even, and
if is odd. In particular, the sequence of bases contains the sequence
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 , then the slopes (known as successive convergents to ) converge to from below when is even, and from above when is odd. As bases have determinant , we also see that
with initial conditions and , thus
etc. From an induction we see that the are a monotonically increasing sequence of natural numbers. Indeed, they must increase at least as fast as the Fibonacci sequence ; from an easy induction we see that , for all . In particular, the must grow at least exponentially fast in .
As with the basis sequence , we can express the in the basis:
Then the are positive reals, with , , and
Since and for , we see in particular that
In particular we have a fairly precise description of how well the convergents approximate :
— 2. Bohr sets —
Now we compare rank one Bohr sets to rank two progressions . It turns out that the best progressions to use here come from using the denominators of a semiconvergent basis as the generators. Indeed, if
then we have
Thus we have
In the converse direction, suppose that , thus and one has for some integer . As is a basis for , we have
for some integers . Taking wedge products, we see that
We write for some , and similarly write for , to conclude that
We conclude that
then we have
Also, since is a basis, we have , and thus
We thus conclude from the preceding discussion that
On the other hand, we have
and thus by the preceding discussion
Thus, in this case, the rank one Bohr set is morally the same object (up to constants) as the rank two progression .
For sake of discussion, let us suppose that is an upward shift of , so that and . From (5) we see that and hence . Also, we have , so in particular, . If we now set
then we have
Conversely, we have
and so once again we have
Thus again we see that in this case is morally the same object as .
Note that as shrinks, the lengths shrink also, though every so often there is a discontinuity when is incremented, thus shearing the generators as well as the lengths . (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 ; one has
and thus (by unifying all the cases) one has
It is a shame that there is no similarly precise formula known for the size of a rank two Bohr set , 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 , one has
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 for which the Littlewood conjecture fails is so small that it has Hausdorff dimension zero.
If a pair was a counterexample to the Littlewood conjecture, then
for all positive integers . In particular, one has
for all (in other words, is badly approximable by rationals, and is in particular irrational). Applying (2), we conclude that for all , or equivalently that the coefficients of the continued fraction expansion of are bounded. (Conversely, using (2) and (3) we see that if is irrational with bounded continued fraction coefficients, then it is badly approximable by rationals.) Similarly for . This is already enough to establish without much additional work that the Littlewood conjecture is true for almost all (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 of the convergents to , and the denominators of the convergents to :
Proposition 2 Let be two real numbers. Then the following are equivalent:
- (i) form a counterexample to the Littlewood conjecture.
- (ii) are badly approximable, and there is an such that the rank four progressions
are proper for all .
Recall that a progression is said to be proper if all of the elements , of the progression are distinct.
for all non-zero integers . We have already seen that are badly approximable (so in particular and . Now let be a sufficiently small number, and suppose that the progression (6) is not proper for some . Then there is a non-trivial solution to the equation
Setting small enough, we contradict (7).
Now we show that (ii) implies (i). Let be as in (ii). Suppose for contradiction that (i) fails, thus we can find a sequence of integers going off to infinity such that
where denotes a quantity that goes to zero as (or ) goes to infinity. In particular, one can find (depending on ) such that
(Indeed, one can pick to be and to be .) As the increase in a lacunary fashion (thanks to the bad approximability of ), we can find such that ; similarly we may find such that , thus
Thus lies in the Bohr sets
Applying the analysis of the preceding section, we conclude that lies in the rank two progressions
and is non-zero, and so the rank four progression
is not proper. But this contradicts (ii) for large enough.
We can now give a heuristic explanation as to why there should not be any counterexample to the Littlewood conjecture. Such a counterexample can be completely described by the continued fraction coefficients for , and the continued fraction coefficients for . These sequences need to be bounded by the bad approximability property; let us suppose that they are both bounded by some bound . Thus, for any , the number of choices for and grows at most exponentially in (it is about ). Of course, these coefficients then determine the denominators and by the recurrences given previously.
On the other hand, by the above proposition, there needs to be an such that for each and , the progression (6) is proper. We can heuristically gauge how likely this occurs by the following numerology. For fixed (and making the non-degeneracy assumptions that ), there are about different ways to form a sum of the form
with and . These sums have magnitude about . 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 for some depending only on .
On the other hand, the number of eligible pairs for which the progression (6) is non-degenerate enough to have a chance of being proper grows quadratically in . Due to the exponential growth of and , 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 vary (viewing and as being drawn uniformly from all sequences bounded by ). 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 (i.e. it should be something like , particularly if we choose and to be comparable in magnitude). As this beats the entropy of for large enough, we thus expect that for any given , 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 and 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).