Measures Are Better

John Littlewood is the latter half of famous duo of Hardy-Littlewood. I have discussed him before here and only wish to point out that he was, on his own, one of the great analyst of the last century.

Today I will discuss the Littlewood Conjecture, which has been open now for over eighty years.

There are conjectures that seem to approachable, and there are those that seem unapproachable. The Littlewood conjecture falls into the former category. Yet it has resisted efforts to solve it now for years. Akshay Venkatesh of NYU has a lovely survey about the problem. Also Tim Gowers has some interesting ideas about it—see this post.

The Conjecture

Define to be the fractional part of the real number . Thus, . Littlewood was interested in how well two real numbers could be approximated by rational numbers that had the same denominator. A reasonable question, no? He conjectured that for any two real numbers and ,

could be made as small as one wished by choosing the right natural number . Another fancier way to say this is that

Note, that it is not hard to prove that is bounded for arbitrarily large . Thus the critical point of the conjecture is for these larger and larger , why would not at least be smaller and smaller?

I got interested in this question for several reasons, but perhaps the most compelling reason is there is some strong evidence that it is true. In particular, it is now known that the and for which the conjecture fails are very “sparse”: they have Hausdorff dimension zero. This is even stronger than measure zero. Yet it is open whether the conjecture is true even for and . This reminds me of the situation that we face in many parts of complexity theory. Often we can prove that there exists some object, but finding a concrete example is another whole story.

Let’s take a quite look at why Littlewood was possibly led to his conjecture, and discuss some simple issues around the conjecture.

Dirichlet Approximation Theorem

Lejeune Dirichlet’s famous theorem of 1842 says:

Theorem: For any real number there are an infinite number of natural numbers and so that

To be sure, the theorem is only interesting when is irrational, and in that case one can add that and have no common factor.

Note that the theorem implies that . Thus to prove Littlewood’s conjecture—since this is bounded—we need “only” show that can be made small for some of the ‘s.

The Proof

We can assume that is irrational. Divide the interval into intervals: the is where is from the range . Define the function as the interval that

is in. Recall that means the fractional part of : it is where is an integer and . Note that since is irrational, the function is well defined. Now consider ranging over the values

where is less than but large. Then by the pigeonhole principle there must be a so that for two values: denote them by and and assume .

The key is that than there are integers and so that

where both and are less than . It follows that

where is an integer. Let , and so

An alternate way to view this is given as “Theorem 1” in Gowers’ post. For any and , if we choose uniformly, the expected number of members of the progression (wrapping modulo ) that give is . Hence by the probabilistic method, for some there exist two such members, call them and with . These automatically give .

One Trick

Again look at Venkatesh’s paper for more information on the Littlewood Conjecture. One “trick” that is key to progress is this: measures sometimes behave better than sets. Consider what a set is and what a measure is:

• A set can be viewed as a map from a universe to the boolean values .
• A measure can be viewed as a map from subsets of the universe to the real interval .

The idea used in the study of the Littlewood Conjecture is that measures can often behave better than sets.

Here is a concrete version from the paper. Take a closed subset of the unit square . Let be a projection from the square to the interval . Define as the set . There is no reason that and near each other should have and “near” in any sense. Sets behave badly.

But measures can save the day. Change the set to a measure . Then the corresponding idea almost works: on a set of measure the measures will be near each other. That is, let be the projected measure on the interval of the -axis, and for each , let be the measure restricted to the fiber . Then we obtain

where importantly, the function is continuous on all but a set of tiny measure.

I am intrigued by this shift from sets to measures. In complexity theory can we use anything like this?

Littlewood Conjecture And An Old Friend

A classic pair of results are that and are both irrational; actually even better, they are transcendental numbers. That is they are not just not rational, but are not the roots of any integer polynomial. What about and ? One must be irrational: if both were rational then their sum would be too, which is impossible. But which one is irrational? I believe that this is still wide open.

There is a simple connection to the Littlewood Conjecture. Call and a bad pair of irrational numbers if they are counterexamples to the conjecture. That is

Can and be a bad pair?

Let’s look at this. Suppose that for some rational number . Then by Dirichlet’s Theorem there are with as large as we like so that

But this implies that

We get, therefore, that

and that

This shows for large enough that can be made as small as one wishes. Thus and are not a bad pair, provided we know that is rational.

What does this mean? It shows that there is a simple connection—which I believe to be a really interesting connection—between two old hard problems. Can we exploit it to say something more about either the Littlewood Conjecture or whether or not numbers like are irrational?

Open Problems

It would help greatly if we had some control over the value of in the Dirichlet Theorem. Suppose that we place into bins. Let be the set of so that and and go into the same bin. What can we say about ? Can we say anything useful?