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$.