From a packing problem to quantitative recurrence in [0,1] and the Lagrange spectrum of interval exchanges

From a packing problem to quantitative recurrence in [0,1] and the Lagrange spectrum of interval exchanges, Discrete Analysis 2017:10, 25 pp.

A basic fact in the theory of Diophantine approximation is Dirichlet’s theorem that for every real number \(\alpha\) there are infinitely many pairs \((m,n)\) of integers such that \(|\alpha-\frac mn|\leq\frac 1n\). Equivalently, there are infinitely many positive integers \(n\) such that \(n\langle\langle n\alpha\rangle\rangle\leq C\), where \(\langle\langle x\rangle\rangle\) denotes the distance from \(x\) to the nearest integer.

This allows us to define a parameter \(r(\alpha)=\lim\inf_{n\to\infty} n\langle\langle n\alpha\rangle\rangle\). The above fact states that \(r(\alpha)\) is always finite, but the question of what values it can take turns out to be an interesting one.

It is no surprise that the worst example – that is, the \(\alpha\) for which \(r(\alpha)\) is largest – is the golden ratio, or more generally any real number with a continued-fraction expansion that is 1 in all but finitely many places. For such a number \(r(\alpha)=1/\sqrt 5\). A little more unexpected is that this value is isolated amongst the possible values that can be taken: if \(r(\alpha)\ne 1/\sqrt 5\), then \(r(\alpha) \leq 1/2\sqrt 2\). However, this is less surprising when one reflects that for a number to violate this condition, its continued fraction must be different from 1 in infinitely many places, which will affect an infinite sequence of best approximations, each one quite substantially. There is in fact a sequence of isolated values that can be taken, related to certain binary quadratic forms, but there is also a constant \(c\) such that all values in the interval \((0,c]\) are taken. It was shown by Freiman that \(c\) is the remarkable constant \(491993569/(2221564096 + 283748\sqrt{462})\).

It is customary to take the reciprocals of all these numbers: the Lagrange spectrum is defined to be the set of all possible values that can be taken by \(r(\alpha)^{-1}\).

This paper contains two very nice generalizations of Hurwitz’s theorem. To state the first, we begin by observing that the definition of the Lagrange spectrum has a simple reformulation in dynamical terms. Let \(\mathbb T\) be the circle \(\mathbb R/\mathbb Z\) and let \(R_\alpha\) be the rotation \(x\mapsto x+\alpha\), where addition is mod 1. Then the distance from \(x\) to \(R_\alpha^nx\) is \(\langle\langle n\alpha\rangle\rangle\). So if \(T\) is now any measurable map from \(\mathbb T\) to \(\mathbb T\) and \(x\in T\), we can define \(r(T,x)\) to be \(\lim\inf_{n\to\infty}nd(x,T^nx)\), and this definition gives us \(r(\alpha)\) (for any \(x\)) in the special case that \(T=R_\alpha\).

The first main theorem of the paper is that if \(T\) is a measure preserving map from the circle to itself, then \(r(T,x)\leq 1/\sqrt 5\) for almost every \(x\). Thus, golden-ratio-related rotations are the extremal examples not just amongst rotations but amongst all measure-preserving maps.

The second generalization concerns interval-exchange transformations. If one thinks of the circle as the half-open interval \([0,1)\), then a rotation by \(\alpha\) can be achieved by partitioning the circle into the two subintervals \([0,1-\alpha)\) and \([\alpha,1)\). The first of these is translated to the right by \(\alpha\) and the second is translated to the left by \(1-\alpha\). An interval-exchange transformation is any bijection from \([0,1)\) to \([0,1)\) that is achieved by partitioning \([0,1)\) into finitely many intervals and translating them. (This can of course be straightforwardly generalized to intervals of other lengths.) A useful non-triviality condition to impose, called the Keane condition, is that however many times the transformation is iterated, no end-point is ever mapped to another end-point. (In the case of rotations, this is saying that \(\alpha\) is irrational.)

If \(T\) is an interval-exchange transformation and \(n\) is a positive integer, then \(T^n\) is also an interval-exchange transformation. If \(T\) satisfies the Keane condition and chops \([0,1)\) into \(k\) pieces, then \(T^n\) chops \([0,1)\) into \((k-1)n+1\) pieces. Under these circumstances, we define the Lagrange constant of \(T\) to be the reciprocal of the quantity \(\mathcal{E}(T)=\lim\inf_{n\to\infty}n\varepsilon_n(T)\), where \(\varepsilon_n(T)\) is the length of the shortest interval coming from the interval-exchange transformation \(T^n\). Note that if \(k=2\), so that \(T=R_\alpha\) for some \(\alpha\), then \(\varepsilon_n(T)\) is precisely \(\langle\langle n\alpha\rangle\rangle\).

The second main theorem of the paper states that \(\mathcal{E}(T)\) cannot be bigger than \(1/((k-1)\sqrt 5)\) (where \(k\) is still the number of intervals into which \([0,1)\) is partitioned and the Keane condition is still assumed). Moreover, this is again an isolated value: there is an absolute constant \(\varepsilon_0 > 0\) such that for each \(k\), if \(\mathcal{E}(T) < 1/((k-1)\sqrt 5)\), then \(\mathcal{E}(T)\leq 1/((k-1)\sqrt 5+k^{-1}\varepsilon_0)\).

Both results are proved with the help of a somewhat unusual packing problem. Typically with a packing problem one wishes to fit as many points as possible into a set subject to a lower bound on the distance between any two distinct points. That is the case here, but the “distance” between two points \((x_1,x_2)\) and \((y_1,y_2)\) is \(\sqrt{|x_1-y_1||x_2-y_2|}\), which is not actually a distance because it does not satisfy the triangle inequality. However, it is highly relevant to this kind of problem: for example, if we place into \(\mathbb T^2\) the points \((x/n,\alpha x)\), as \(x\) runs from 0 to \(n-1\), and if we can find two points at “distance” \(d\) from each other, then we have integers \(x\) and \(y\) between 0 and \(n-1\) such that \(n^{-1}|x-y|\langle\langle\alpha(x-y)\rangle\rangle=d\). If this is the smallest distance, that tells us that for every positive integer \(m < n\) we have \(m\langle\langle\alpha m\rangle\rangle\geq nd > md\).