Littlewood's conjecture and Klein polyhedra

Littlewood's conjecture

Littlewood's conjecture, a fascinating problem in Diophantine approximation, is that for all $x, y \in \mathbb{R}$ and for all $\epsilon \gt 0$ there is an integer $n \geq 1$ such that $n \cdot \Vert nx \Vert \cdot \Vert ny \Vert \lt \epsilon$, where $\Vert z \Vert$ denotes the distance from $z$ to the nearest integer.

I present here a few calculations, some half-baked thoughts and some nice pictures.

'Worst-case' points

Let us define $\epsilon_N (x, y) = \min \{ n \cdot \Vert nx \Vert \cdot \Vert ny \Vert : 1 \leq n \leq N \}$. Thus LC is the claim that $\max \{ \epsilon_N (x, y) : x, y \in \mathbb{R} \} \to 0$ as $N \to \infty$.

Note that $\epsilon_N (m \pm x, n \pm y) = \epsilon_N (x, y)$ for $m, n \in \mathbb{Z}$, so by symmetry we can restrict attention to the closed triangle $X = \{ (x,y) : 0 \leq x \leq \frac12, 0 \leq y \leq x \}$.

Greyscale plot of $\epsilon_7 (x, y)$, for $0 \leq x, y \leq \frac12$.

For each $N$, there will be some point $(x_N, y_N) \in X$ (conceivably more than one) where $\epsilon_N (x, y)$ is maximized. I've computed the first few values of $(x_N, y_N)$.

To find $x_N$, $y_N$ and $\epsilon_N = \epsilon_N (x_N, y_N)$ for a given $N$, we end up having to solve three simultaneous equations of the form $n_i (n_i x - r_i) (n_i y - s_i) = q_i \epsilon$ ($i = 0, 1, 2$), where $n_i, r_i, s_i \in \mathbb{N}$ and $q_i = \pm 1$. I found the $n_i, r_i, s_i, q_i$, up to $N=62$, by careful visual inspection of the boundary curves. (No doubt with a bit of work the process could be made more rigorous, but I am just trying to get a feel for what's going on.) It appears from the data so far that $r_i$ and $s_i$ are determined by $n_i$, according to some unknown rule exemplified in the following table:

$n$ $r$ $s$
1 0 0
2 1 1
3 1 1
4 2 1
5 2 1
7 3 2
8 3 2
15 6 4
17 7 5
18 7 5
26 11 7
34 13 9
Here is a table of values of $n_0, n_1, n_2$ and $q_0, q_1, q_2 = \pm 1$ for $3 \leq N \leq 62$. I'll also list the resulting values of $x_N$, $y_N$ and $\epsilon_N$:
$N$ $n_1$ $q_1$ $n_2$ $q_2$ $n_3$ $q_3$ $x$ $y$ $\epsilon_N$
1 .5000 .5000 .2500
2 .3694 .3694 .1365
3 1 $+$ 2 $+$ 3 $-$ .4286 .2857 .1224
7 4 $-$ 5 $+$ 7 $+$ .4119 .2680 .1013
15 5 $+$ 7 $+$ 15 $+$ .4113 .2692 .0977
17 3 $-$ 5 $-$ 15 $-$ .3889 .2692 .0962
18 5 $+$ 7 $+$ 17 $+$ .4110 .2699 .0957
22 3 $-$ 15 $-$ 18 $+$ .3871 .2688 .0937
26 8 $+$ 15 $+$ 18 $+$ .3877 .2644 .0936
34 8 $+$ 18 $+$ 34 $-$ .3877 .2643 .0928
49 7 $+$ 17 $+$ 26 $-$ .4125 .2697 .0882
63 ? ? ? ? ? ? ? ? ?
In this table, three dots indicate repetition of the sequence above until the next displayed value of $N$. For example, the values of $x_N, y_N, \epsilon_N$ are the same for $N = 3, 4, 5, 6$.

From these data it is tempting to hazard a guess that $(\sqrt{2} - 1, 2 - \sqrt{3}) \approx (0.4142, 0.2679)$ is a limit point of $(x_N, y_N)$: in other words, that $(\sqrt{2}, \sqrt{3})$ is in some sense a 'worst case' for LC.

Greyscale plot of $\epsilon_{49} (x,y)$ for $0.4025 \leq x \leq 0.4225$ and $0.2597 \leq y \leq 0.2797$.

Continued fractions

Notation: for $x \in \mathbb{R}$, let $x = [a_0(x); a_1(x), a_2(x), \ldots]$ be the continued-fraction expansion, so that $x = \lim_{n \to \infty} \frac{p_n(x)}{q_n(x)}$, where $p_0(x) = 1, q_0(x) = 0, p_1(x) = a_0(x), q_1(x) = 1$, and $p_{n+2}(x) = a_{n+1}(x) p_{n+1}(x) + p_n(x)$, $q_{n+2}(x) = a_{n+1}(x) q_{n+1}(x) + q_n(x)$.

I've calculated some values of $\epsilon_N (\sqrt{2}, \sqrt{3})$. The smallest such value that I've calculated exactly is $0.0018$, at $N = 4\,628\,523$. The sequence of 'best possible so far' $N$ for $(\sqrt{2}, \sqrt{3})$ is:

By restricting the calculations to convergents of the continued-fraction expansions of $\sqrt{2}$ and $\sqrt{3}$ one can quickly find smaller values: for example, $n \cdot \Vert n \sqrt{2} \Vert \cdot \Vert n \sqrt{3} \Vert = 0.0011$ for $n = 1\,104\,728\,155\,436$, corresponding to a convergent of $\sqrt{3}$; $n \cdot \Vert n \sqrt{2} \Vert \cdot \Vert n \sqrt{3} \Vert = 0.0003$ for a $54$-digit number $n \approx 7.991 \times 10^{53}$ corresponding to a convergent of $\sqrt{2}$; and $n \cdot \Vert n \sqrt{2} \Vert \cdot \Vert n \sqrt{3} \Vert = 0.00000207$ for a $13987$-digit number $n \approx 1.486 \times 10^{13986}$ corresponding to a convergent of $\sqrt{2}$.

As well as suggesting pretty strongly that $\epsilon_N (\sqrt{2}, \sqrt{3}) \to 0$, these calculations lead me to wonder whether it might be the case that for all $x, y$ there are $n_k \to \infty$ such that $n_k \cdot \Vert n_k x \Vert \cdot \Vert n_k y \Vert \to 0$ and $n_k$ is a denominator of a convergent of one or other of $x$ and $y$.

We know that $q_n(x) \Vert q_n(x) x \Vert$ is always bounded. So if $\liminf_{n \to \infty} \Vert q_n(x) y \Vert = 0$, we are done. However, as Arkshay Venkatesh points out in this survey article, for any sequence of integers $q_n$ such that $\liminf_{n \to \infty} q_{n+1} / q_n \gt 1$ there exists $x \in \mathbb{R}$ such that $\liminf_{n \to \infty} \Vert q_n x \Vert \gt 0$.

But it is not so clear that we don't always have either $\liminf \Vert q_n(x) y \Vert = 0$ or $\liminf \Vert q_n(y) x \Vert = 0$ – at least if $x$ and $y$ are badly-approximable.

Duality

Greyscale plot of $\epsilon_{63} (x, y)$ for $\lvert x - (\sqrt{2}-1) \rvert \leq 0.1$, $\lvert y - (2 - \sqrt{3}) \rvert \leq 0.1$. The dark slanted lines illustrate a lattice duality.

On the plots for larger $N$, patterns of darkness (low values of $\epsilon_N (x, y)$) seem to appear along rational lines. Perhaps we can make sense of this in terms of the duality mentioned by Davenport in his paper Simultaneous Diophantine approximation (Proc. LMS, 1952, pp. 406–416). This duality involves replacing the parameters $r - nx$, $s - ny$ and $n$ respectively by $r$, $s$ and $rx + sy + n$, as they occur in the quantity to be minimized, which in our case is simply the absolute value of their product. This amounts to replacing one linear mapping with its adjoint (or matrix with its transpose).

In relation to LC this is not quite a 'clean' duality, since one has to make a choice about which of $r, s, n$ is allowed to be zero. Thus, in Littlewood's problem, we seek to minimize $\lvert n (r - nx) (s - ny) \rvert$ over all $r, s, n$ such that $n \neq 0$; while in the 'dual' problem we seek to minimize $\lvert r s (rx + sy + n) \rvert$ over all $r, s, n$ such that $r, s \neq 0$; and the Davenport 'dual' of the Littlewood conjecture would be that for all $x, y \in \mathbb{R}$ and for all $\epsilon \gt 0$ there are integers $r, s \neq 0$ such that $\lvert rs \rvert \cdot \Vert rx + sy \Vert \lt \epsilon$.

As it stands, this is false. Indeed, for any badly-approximable number $x$ (that is, any number with bounded partial quotients in its continued-fraction expansion, such as $\sqrt{2}$), and $y = 0$, the quantity $\lvert rs \rvert \cdot \Vert rx + sy \Vert$ is bounded away from zero. In geometric terms, the problem is that we are missing the horizontal and vertical lines that correspond to $r = 0$ or $s = 0$.

We can try to arrive at a cleaner notion of duality by modifying the statement of the conjecture. This leads us towards Oppenheim's Conjecture.

Let $M$ be a real $n \times n$ matrix. Call $M$ rational if $M \mathbf{x} \in \mathbb{Z}^n$ for some nonzero $\mathbf{x} \in \mathbb{Z}^n$. This generalizes the ordinary (one-dimensional) definition of rationality.

Note that rationality is a lattice property, because if $M$ is rational then so is $UM$ where $U$ is any unimodular matrix (i.e. integer matrix with determinant $\pm 1$).

The matrix that corresponds to Littlewood's conjecture is \[ \left( \begin{array}{ccc} 1 & 0 & 0 \\ x & 1 & 0 \\ y & 0 & 1 \end{array} \right) \] and it is this matrix whose transpose gives the (false) dual form of the conjecture. The 'problem' is that this matrix is rational.

A 'self-adjoint' variant of LC

Let $\phi : \mathbb{R}^n \to \mathbb{R}$ be the multilinear form defined by $\phi (\mathbf{x}) = \prod_i x_i$.

For a nonsingular $n \times n$ matrix $M$, define $N(M) = \inf \{ \lvert \phi ( M \mathbf{x} ) \rvert : \mathbf{x} \in \mathbb{Z}^n \setminus \{ \mathbf{0} \} \}$.

The 'norm minimum' $N$ is clearly a lattice property – it depends only on the lattice generated by a matrix – and so we can talk about $N(\Lambda)$ for a lattice $\Lambda$.

(As an example of a nonzero $N(M)$ in dimension $2$, consider $M = \left( \begin{array}{cc} \sqrt{2} & 1 \\ 1 + \sqrt{2} & 1 \end{array} \right)$.)

It is tempting to make the following modification of LC:

If $\Lambda$ is a $3$-dimensional lattice and $N(\Lambda) \gt 0$ then $\Lambda$ is rational.
I don't think this is true (but haven't come up with a counterexample yet). Oppenheim's conjecture (see below) is probably the correct formulation in this vein.

Instead, I'd like to propose the following 'self-adjoint' variant of LC:

If \[ M_{x,y} = \left( \begin{array}{ccc} 1 & y & x \\ x & 1 & y \\ y & x & 1 \end{array} \right) \] then $N(M_{x,y}) = 0$ for all $x, y \in \mathbb{R}$.

Out of interest, I searched for $\mathbf{x} \in \mathbb{Z}^3 \setminus \{0\}$ minimizing $\lvert \phi (M_{\sqrt 2, \sqrt 3} \mathbf{x}) \rvert$ for $\Vert \mathbf{x} \Vert_\infty \leq 10^6$. The first three minima are attained at:

The second of these seems remarkably good. It corresponds to the case $495 \cdot 388 \cdot \Vert 495 \sqrt{2} - 388 \sqrt{3} \Vert \approx 0.0073$ in Davenport's dual problem, because all the smallness comes from one factor in the product. The third has only a marginally better norm minimum, despite having much larger coefficients, and doesn't obviously map onto Davenport's dual problem.

When $y = x^2$ (or $x = y^2$), the best minima tend to have one coordinate zero and the others corresponding to the convergents of the continued-fraction expansion of $x$ (or $y$).

Oppenheim's conjectures and Klein polyhedra

I picked up the notation $\phi$ and $N$ from this paper by Oleg German.

Oddly, it appears that there are two 'Oppenheim conjectures', both closely related to Littlewood's conjecture: one (discussed in Venkatesh's article) proved by Margulis in the 1980s, and one (discussed in German's article) still unproved.

German states Oppenheim's conjecture as follows:

If $n \geq 3$ and $\Lambda \subset \mathbb{R}^n$ is an $n$-dimensional lattice with $N(\Lambda) \gt 0$, then $\Lambda$ is algebraic (i.e. similar modulo the action of a group of diagonal $n \times n$ matrices to the lattice of a complete module of a totally real algebraic field of degree $n$).
Apparently the three-dimensional Oppenheim conjecture implies the Littlewood conjecture.

The converse to this conjecture follows from the Dirichlet theorem on algebraic units. See:

The association between algebraic fields and lattices is roughly as follows. Suppose we have an algebraic field $K$ of degree $n$. Assume for simplicity that it's totally real: that means that $K = \mathbb{Q}(\theta)$ where $\theta$ is a root of a polynomial of degree $n$ with integer coefficients all of whose roots are real. Then $K$ has $n$ distinct embeddings $\sigma_i : K \to \mathbb{R}$. One can then define $\sigma : K \to \mathbb{R}^n$ by $\sigma(x)_i = \sigma_i(x)$. The image of $\mathfrak{O}_K$, the ring of integers of $K$, is then a lattice.

Obviously this association is only defined modulo the permutation group. But any symmetric function of $n$ real variables gives rise, via this association, to a well-defined function on $K$.

In particular, the product $\prod_i \sigma_i (x)$ gives rise to a well-defined function, the 'norm', $N_K(x)$. The norm $N_K$ is multiplicative ($N_K(xy) = N_K(x) N_K(y)$), and if $x \in \mathfrak{O}_K$ then $N_K(x) \in \mathbb{Z}$. Since $N_K = \phi \circ \sigma$, and $N_K(x) = 0 \Rightarrow x = 0$, we have the result that $N(\Lambda) \gt 0$ when $\Lambda$ is a lattice derived (in the above way) from a totally-real algebraic field.

The other 'Oppenheim conjecture', as stated by Venkatesh (and most other sources I've seen) is:

If $Q(x_1, \ldots, x_n) = \sum_{i,j} a_{ij} x_i x_j$ is an indefinite quadratic form in $n \geq 3$ variables which is not a multiple of a rational form, then for all $\epsilon \gt 0$ there exists $\mathbf{x} \in \mathbb{Z}^n$ with $\lvert Q(\mathbf{x}) \rvert \lt \epsilon$.

Let's call these conjectures OC-P and OC-Q respectively (think 'P' for product and 'Q' for quadratic form). Venkatesh discusses the connection of OC-Q to LC, but at the moment I'm more interested in OC-P.

German's paper goes on to describe a notion of duality for lattices, and another notion of duality for polyhedra, and to relate the two, in terms of the set of 'Klein polyhedra' generated by the lattice. This is a fascinating concept, which gives a natural generalization of continued fractions to higher dimensions.

Let $\Lambda \subseteq \mathbb{R}^n$ be an $n$-dimensional irrational lattice of determinant $1$. The Klein polyhedra of $\Lambda$ are the convex hulls of the nonzero points of $\Lambda$ contained in each orthant. So an $n$-dimensional lattice has $2^n$ Klein polyhedra. The boundary of a Klein polyhedron is called a sail.

In two dimensions, the Klein polyhedra of the lattice generated by $(1, 1-\alpha)$ and $(0, 1)$ are intimately related to the partial quotients of $\alpha$, their edges and vertices encoding information about the odd and even partial quotients. It's a little more complicated in higher dimensions, but basically the faces of the Klein polyhedra (particularly the vertices, or 'edge stars', of dimension $0$, and the 'facets', of dimension $n-1$, which in some sense play dual roles) encode information about the lattice that is highly relevant to questions of Diophantine approximation. German's main theorem relates them to $N(\Lambda)$.

The information is encoded in terms of the 'determinants' of the vertices and facets, which are defined as follows:

German proves that $N(\Lambda) \gt 0$ if and only if the facets and vertices of its Klein polyhedra have uniformly bounded determinants. More precisely, the condition can be stated in two ways, which turn out to be equivalent: either one considers a single Klein polyhedron (the one in the positive orthant, say) and requires that its facets and vertices have uniformly bounded determinants; or one condiders all $2^n$ Klein polyhedra and requires that just their facets have uniformly bounded determinants.

Here are the two notions of duality:

The $k$-dimensional faces of $K$ correspond with the $(n-1-k)$-dimensional faces of $K^\circ$, via a natural inclusion-reversing bijection: $\beta_K(F) = \{ \mathbf{x} \in K^\circ : (\forall \mathbf{y} \in F) \langle \mathbf{x}, \mathbf{y} \rangle = 1 \}$. In particular, vertices and facets of $K$ correspond with facets and vertices, respectively, of $K^\circ$.

An important lemma is that $K^* \subseteq K^\circ$. There is a technical condition attached here, namely that the boundary of the positive orthant contains no nonzero points of $\Lambda$ and $\Lambda^*$. This is a slightly stronger condition than irrationality.

If $n = 2$ we have equality: $K^* = K^\circ$. This is related to the fact that in two dimensions the determinants of the vertices of a Klein polyhedron are equal to the determinants of the facets of its neighbouring Klein polyhedra. But in general the inclusion is strict.

Note that neither of these quite corresponds to Davenport's duality (which is nicely illustrated by the last plot above).

There is a neat way to transform a sail in the positive orthant $\mathcal{O}_+$ of $\mathbb{R}^n$ into a tesselation of $\mathbb{R}^{n-1}$. One first projects it onto $\mathcal{C}_+ = \{ \mathbf{x} \in \mathcal{O}_+ : \phi(\mathbf{x}) = 1\}$ by mapping $\mathbf{x}$ to $\phi(\mathbf{x})^{-1/n} \mathbf{x}$. Then one maps $\mathcal{C}_+$ onto $\mathbb{R}^{n-1}$ by mapping $\mathbf{x}$ to $(\log x_1, \ldots, \log x_{n-1})$.

In this way a lattice $\Lambda \subseteq \mathbb{R}^n$ gives rise to a tesselation $\mathcal{T}(\Lambda)$ of $\mathbb{R}^{n-1}$.

There is a nice web page by Keith Briggs about Klein polyhedra, which includes some interesting pictures of tesselations in $\mathbb{R}^2$ corresponding to algebraic lattices, or equivalently to totally-real cubic number fields. Such tesselations have a periodic structure isomorphic to $\mathbb{Z}^2$.

Cells and vertices of the resulting partition of $\mathbb{R}^{n-1}$ correspond to facets and vertices of the sail. This transformation is interesting because boundedness of the determinants of the facets together with the condition $N(\Lambda) \gt 0$ implies that the cells of the resulting partition are of bounded diameter.

So:

Therefore, LC would follow if we could show that uniform boundedness of the cells in one of these tesselations in $\mathbb{R}^2$ implies periodicity.

So there arises the question:

Perhaps one should begin with the (presumably) easier question:

A couple of the references listed on Keith Briggs's website:

They both look interesting, giving different perspectives on the subject.

Writing $V$ for the sail (the boundary of the Klein polyhedron), Lachaud defines two graphs:

An edge in either of these graphs can be associated in a natural way with a matrix of the form $UW$ where \[ U = \left( \begin{array}{cccc} 1 & \cdots & 0 & c_1 \\ \vdots & \ddots & \vdots & \vdots \\ 0 & \cdots & 1 & c_{n-1} \\ 0 & \cdots & 0 & c_n \end{array} \right) \] (with $c_i \in \mathbb{Q}^\times$) and $W$ is a permutation matrix. These matrices correspond to the partial quotients in the two-dimensional case.

Let $\mathcal{R}$ be the set of matrices of the above form $UW$. Let $\Upsilon$ be the graph whose set of vertices is $\mathrm{GL}_n(\mathbb{Q})$ and whose edges correspond to multiplication by elements of $\mathcal{R}$.

Lagrange proved that the continued-fraction expansion of a quadratic irrational is ultimately periodic. The above ideas allow us to generalize this result to higher dimensions. The statement is a little involved, but essentially the lattice is algebraic if and only if there are $n$ ultimately-periodic (in $\Upsilon$) paths in $\Gamma_{\mathrm e}(V)$ (or $\Gamma_{\mathrm f}(V)$) that asymptotically approach the coordinate axes (or hyperplanes), and whose repeating units commute with one another.


Alec Edgington, May 2012. Email Alec at emplexis dot com.