Automatic Logarithm and Associated Measures

Abstract

We introduce the notion of the Automatic Logarithm ${\mathcal{L}}_{\mathcal{A},\mathcal{B}}$ with the purpose of studying the expanding properties of Schreier graphs of action of the group generated by two finite initial Mealy automata $\mathcal{A}$ and $\mathcal{B}$ on the levels of a regular $d$-ary rooted tree $\mathcal{T}$, where $\mathcal{A}$ is level-transitive and of bounded activity. ${\mathcal{L}}_{\mathcal{A},\mathcal{B}}$ computes the lengths of chords in this family of graphs. Formally, $\mathcal{L}$ is a map $\partial \mathcal{T}\to {\mathbb{Z}}_d$ from the boundary of the tree to the integer $p$-adics whose values are determined by a Moore machine. The distribution of its outputs yields a probabilistic measure $\mu$ on $\partial \mathcal{T}$, which in some cases can be computed by a Mealy-type machine (we then say that $\mu$ is finite-state). We provide a criterion to determine whether $\mu$ is finite-state. A number of examples illustrating the different cases with $\mathcal{A}$ being the adding machine is provided.

46 pages, 17 figures, 4 tables