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 ${||x||}$ to be the fractional part of the real number ${x}$. Thus, ${||8.9||=.9}$. 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 ${\alpha}$ and ${\beta}$,

$\displaystyle n||n\alpha|| \cdot ||n\beta||$

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

$\displaystyle \liminf_{n \rightarrow \infty} n||n\alpha|| \cdot ||n\beta|| = 0.$

Note, that it is not hard to prove that ${ n||n\alpha|| }$ is bounded for arbitrarily large ${n}$. Thus the critical point of the conjecture is for these larger and larger ${n}$, why would ${ ||n\beta||}$ 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 ${\alpha}$ and ${\beta}$ 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 ${\alpha = \sqrt{2}}$ and ${\beta=\sqrt{3}}$. 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 ${\alpha}$ there are an infinite number of natural numbers ${p}$ and ${q}$ so that

$\displaystyle \left| \alpha - \frac{p}{q} \right| \le \frac{1}{q^{2}}.$

To be sure, the theorem is only interesting when ${\alpha}$ is irrational, and in that case one can add that ${p}$ and ${q}$ have no common factor.

Note that the theorem implies that ${ q||q \alpha || \le 1 }$. Thus to prove Littlewood’s conjecture—since this is bounded—we need “only” show that ${ || q\beta|| }$ can be made small for some of the ${q}$‘s.

## The Proof

We can assume that ${\alpha}$ is irrational. Divide the interval ${[0,1]}$ into ${n}$ intervals: the ${k^{th}}$ is ${[\frac{k}{n},\frac{k+1}{n}]}$ where ${k}$ is from the range ${0,\dots,n-1}$. Define the function ${f(r)}$ as the interval that

$\displaystyle r\alpha \bmod 1$

is in. Recall that ${z \bmod 1}$ means the fractional part of ${z}$: it is ${z-i}$ where ${i}$ is an integer and ${0 \le z-i < 1}$. Note that since ${\alpha}$ is irrational, the function ${f}$ is well defined. Now consider ${r}$ ranging over the values

$\displaystyle 0, \dots, n$

where ${\ell}$ is less than ${n}$ but large. Then by the pigeonhole principle there must be a ${k}$ so that ${f(r)=k}$ for two values: denote them by ${s}$ and ${t}$ and assume ${s>t}$.

The key is that than there are integers ${i}$ and ${j}$ so that

$\displaystyle \begin{array}{rcl} s\alpha - i &=& \frac{k}{n} + \delta_{1} \\ t\alpha - j &=& \frac{k}{n} + \delta_{2}, \end{array}$

where both ${\delta_{1}}$ and ${\delta_{2}}$ are less than ${1/n}$. It follows that

$\displaystyle (s-t)\alpha - k = \delta_{1}-\delta_{2},$

where ${k}$ is an integer. Let ${m = s-t}$, and so

$\displaystyle \left| \alpha - \frac{k}{m} \right| \le \frac{1}{mn} \le \frac{1}{m^{2}}.$

An alternate way to view this is given as “Theorem 1” in Gowers’ post. For any ${\alpha}$ and ${n}$, if we choose ${0 \leq \beta < 1}$ uniformly, the expected number of members ${i}$ of the progression ${0,\alpha,2\alpha,\dots,n\alpha}$ (wrapping modulo ${1}$) that give ${\beta \leq i\alpha < \beta + \frac{1}{n}}$ is ${1 + \frac{1}{n} > 1}$. Hence by the probabilistic method, for some ${\beta}$ there exist two such members, call them ${s\alpha}$ and ${t\alpha}$ with ${0 \leq s < t \leq n}$. These automatically give ${||\alpha(t - s)|| \leq \frac{1}{n}}$.

## 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 ${S}$ from a universe ${U}$ to the boolean values ${\{0,1\}}$.
• A measure can be viewed as a map ${\mu}$ from subsets of the universe to the real interval ${[0,1]}$.

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 ${S}$ of the unit square ${[0,1]^{2}}$. Let ${\pi}$ be a projection from the square to the interval ${[0,1]}$. Define ${S_{x}}$ as the set ${\pi^{-1}(\{x\}) \cap S}$. There is no reason that ${x}$ and ${y}$ near each other should have ${S_{x}}$ and ${S_{y}}$ “near” in any sense. Sets behave badly.

But measures can save the day. Change the set ${S}$ to a measure ${\mu}$. Then the corresponding idea almost works: on a set of measure ${0.999999}$ the measures will be near each other. That is, let ${\nu}$ be the projected measure on the interval ${[0,1]}$ of the ${x}$-axis, and for each ${x}$, let ${\mu_x}$ be the measure ${\mu}$ restricted to the fiber ${\pi^{-1}(x)}$. Then we obtain

$\displaystyle \mu = \int_{x \in [0,1]} \mu_x d\nu(x)$

where importantly, the function ${x \mapsto \mu_x}$ 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 ${e}$ and ${\pi}$ 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 ${e + \pi}$ and ${e - \pi}$? 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 ${\alpha}$ and ${\beta}$ a bad pair of irrational numbers if they are counterexamples to the conjecture. That is

$\displaystyle \liminf_{n \rightarrow \infty} n||n\alpha|| \cdot ||n\beta|| > 0.$

Can ${e}$ and ${\pi}$ be a bad pair?

Let’s look at this. Suppose that ${e = \pi + r/s}$ for some rational number ${r/s}$. Then by Dirichlet’s Theorem there are ${p,q}$ with ${q}$ as large as we like so that

$\displaystyle \left| e - \frac{p}{q} \right| < \frac{1}{q^{2}}.$

But this implies that

$\displaystyle \left| \pi + \frac{r}{s} - \frac{p}{q} \right| < \frac{1}{q^{2}}.$

We get, therefore, that

$\displaystyle q\left| qe - p \right| < 1,$

and that

$\displaystyle \left| q\pi + r - p \right| < \frac{s}{q}.$

This shows for large enough ${n}$ that ${n||n\alpha|| \cdot ||n\beta||}$ can be made as small as one wishes. Thus ${e}$ and ${\pi}$ are not a bad pair, provided we know that ${e - \pi}$ 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 ${e + \pi}$ are irrational?

## Open Problems

It would help greatly if we had some control over the value of ${q}$ in the Dirichlet Theorem. Suppose that we place ${0,\dots,n^{2}}$ into ${n}$ bins. Let ${S}$ be the set of ${x-y}$ so that ${x>y}$ and ${x}$ and ${y}$ go into the same bin. What can we say about ${S}$? Can we say anything useful?

April 11, 2013 11:17 pm

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!

2. April 12, 2013 1:53 am

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

3. April 12, 2013 3:08 am

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

4. April 12, 2013 4:25 am

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?

5. April 12, 2013 2:15 pm

what about making $||n\alpha|| \approx ||n \beta||$, 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.

6. April 13, 2013 5:59 pm

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.

7. April 14, 2013 4:36 am

In your proof $(s-t)\alpha -k = \delta_1-\delta_2$ $\Rightarrow 0 \leq n(s-t)\alpha -k <1$ $\Rightarrow 0 \leq n^2(s-t)(s'-t')\alpha - k... < 1$, where $(s'-t')\beta -k' = \delta'_1-\delta'_2$, by the symmetry $0 \leq n^2(s-t)(s'-t')\beta - k... < 1$ (choose appropriate integer k where needed) that implies $n^2||(s-t)(s'-t')\alpha|| < 1, n^2||(s-t)(s'-t')\beta|| < 1$ which implies $(s-t)(s'-t') || (s-t)(s-t') \alpha|| || (s-t)(s-t') \beta|| < \frac{1}{n^2}$

April 14, 2013 5:24 pm

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

• April 14, 2013 11:48 pm

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 $n \times m$ grid with n intervals on x axis, m on y axis, f maps integers to ordered air of reals $(|| r \alpha ||, || r \beta ||)$. One needs $0 < t - s \leq m \times n$ to fill all cells. Than we get $|| (t-s) \alpha || < \frac{1}{n}, || (t-s) \beta || < \frac{1}{m} \Rightarrow (t-s) || (t-s) \alpha || || (t-s) \beta || < \frac{ t-s }{ m \times n }$ that is not guaranteed to be small.

On the other hand, for any two points at distance $t-s$ $(t-s) || (t-s) \alpha || || (t-s) \beta || < | (t-s) (|| t \alpha|| - || s \alpha || ) ( || t \beta ||- || s beta || )$, which asks among all 2D-points what is the shortest distance, as a function of point separation.

9. April 29, 2013 12:30 pm

Reblogged this on Being simple.