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 )$, the supremum of $\mu \in \mathbb{R}$ for which the inequality $0<|\alpha -p/q|<q^{-\mu }$ has infinitely many solutions. For the binary coding determined by an interval $[0,\beta )$, let ${\mathcal{W}}_N$ be the set of length-$N$ words arising from all initial points $x$ under $x\mapsto x+\alpha$. We develop new techniques for estimating edit distance and compute the growth exponents of the edit-distance diameter ${\mathrm{diam}}_E({\mathcal{W}}_N)$. For every $\alpha \notin \mathbb{Q}$ and almost every $\beta \in (0,1)$, we show that $(\ast )\underset{N\to \infty }{\mathrm{limsup}}\frac{\log {\mathrm{diam}}_E({\mathcal{W}}_N)}{\log N}=\frac{\mu (\alpha )-1}{\mu (\alpha )},$ and the corresponding $\mathrm{liminf}$ equals $1/2$. When $\mu (\alpha )-1$ is at most the golden mean $\phi$, the asymptotics $(\ast )$ hold for all $\beta$. However, for $\mu >1+\phi$, there is an uncountable set of $\alpha$ with $\mu (\alpha )=\mu$ for which the edit-distance exponents are strictly smaller than $(\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)$. Finally, we raise the question of estimating edit-distance exponents for more general dynamical systems.

47 pages, 2 figures