Edit distance exponents for irrational rotations

Abstract

We study quantitative edit-distance asymptotics for symbolic codings of irrational rotations $x\mapsto x+\alpha$ on $\mathbb{T}$ in terms of the irrationality exponent $\mu (\alpha )$. For the binary coding determined by an interval $[0,\beta )$, let $d_N(x,y)$ be the edit distance between the codings of the orbits of the points $x$ and $y$ up to time $N-1$. For every $\alpha \notin \mathbb{Q}$, almost every $\beta \in (0,1)$, and almost every $x,y\in \mathbb{T}$, we determine the edit-distance exponents $(\ast )\underset{N\to \infty }{\mathrm{limsup}}\frac{\log d_N(x,y)}{\log N}=\frac{\rho (\alpha )}{\rho (\alpha )+1}$ and $\underset{N\to \infty }{\mathrm{liminf}}\frac{\log d_N(x,y)}{\log N}=\min \{\frac{1}{2},\frac{1}{\rho (\alpha )}\}$, where $\rho (\alpha ):=\mu (\alpha )-1$. We find a surprising transition at the golden mean $\phi =\frac{1+\sqrt{5}}{2}$: If $\rho (\alpha )\le \phi$, then both asymptotics in $(\ast )$ hold for all $\beta$. However, for every finite $\rho >\phi$, there is an uncountable set of $\alpha$ with $\rho (\alpha )=\rho$ for which both edit-distance exponents are strictly smaller than the corresponding values in $(\ast )$ for uncountably many $\beta$. We also derive consequences for aperiodic circle homeomorphisms and Sturmian sequences. For rotations of ${\mathbb{T}}^d$ coded by boxes, we prove that for almost every rotation vector, the common edit-distance exponent is $d/(d+1)$.

44 pages, 5 figures; simplified and reorganized