# Measures Are Better

* The Littlewood conjecture—another drive you crazy conjecture *

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?

I don’t understand the line of thought near “Now consider r ranging over the values 0,…,n where L is less than n but large.” if it is meant to read 0,…,L then the pigeonhole doesn’t seem to work since it won’t hit all the [k/n,(k+1)/n] intervals. I must be missing something? Thanks!

How did you get your last equation, |qPi +r -p|<s/q?

Somehow, reducing a problem of boolean computation to a problem of real computation never seemed like much of reduction to me.

Surely e and pi are not a bad pair for the trivial reason that e is not a badly approximable number — or am I missing something?

what about making , e.g. only fractional part of both numbers make sense, so we can arbitrarily approximate half the difference than add approximately half to one number, and approximately half to the another number. Than since we have approximately equal numbers use approximations to both of them, or mean of them. Than iterate if needed better precision. Each step we are adding the same denominator to both numbers, the error drops down quadratically, that may work.

Another point is this. If two numbers x and y differ by a rational, then there exists q such that qx and qy differ by an integer. Let z=qx. By Dirichlet’s theorem we can find r,s with s arbitrarily large such that |z-r/s| is at most 1/s^2. That gives us that ||qsx||.||qsy|| is at most 1/s^2, so qs ||qsx||.||qsy|| is at most q/s, which can be made arbitrarily small.

In brief, if you want a bad pair then you need the times when their multiples are close to an integer to be very different, and there’s no hope of that if they differ by a rational and so are periodically the same mod 1.

I don’t quite understand the argument in the post (for the reasons pointed out by other commenters) so apologies if it is basically the argument I’ve just given, perhaps after some simple typo has been cleared up.

So I think where that leaves things is that if e-pi differ by a rational then they trivially aren’t a bad pair. But they trivially aren’t a bad pair anyway, since the convergents in the continued-fraction expansion of e are unbounded. So I think that means that there is no hope of using these ideas to make progress on either Littlewood’s conjecture or the irrationality of e-pi.

In your proof , where , by the symmetry (choose appropriate integer k where needed) that implies which implies

how do you know your k… is divisible by n^2?

yes, it does not, so it does not work :(. The naive pigeon hole principle does not work at all, but there is geometrical version of the conjecture. For instance, consider grid with n intervals on x axis, m on y axis, f maps integers to ordered air of reals . One needs to fill all cells. Than we get that is not guaranteed to be small.

On the other hand, for any two points at distance , which asks among all 2D-points what is the shortest distance, as a function of point separation.

Reblogged this on Being simple.