\documentclass[12pt,reqno]{article} \usepackage{amsmath,amssymb,amsthm,graphicx} \usepackage[all]{xy} \usepackage{fullpage} \usepackage[usenames]{color} \usepackage{amscd} \usepackage[margin=3cm,top=4cm,footskip=2cm,nohead]{geometry} \usepackage{psfig} \usepackage{epsf} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}{Definition}[section] \newtheorem{example}{Example}[section] \newcommand\A{{\mathcal{A}}} \newcommand\treek{{X_k^*}} \newcommand\Ht{{\mathcal H^{(3)}}} \newcommand\llim{{\underset{n \to \infty}{\lim}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm {\LARGE\bf Rational Tree Morphisms and Transducer\\ \vskip .1in Integer Sequences: Definition and Examples} \vskip 1cm \large Zoran {\v S}uni{\'c} \footnote{Partially supported by NSF grant DMS-0600975.}\\ Department of Mathematics\\ Texas A\&M University\\ College Station, TX 77843-3368 \\ USA\\ \href{mailto:sunic@math.tamu.edu}{\tt sunic@math.tamu.edu}\\ \end{center} \vskip .2 in \begin{abstract} The notion of transducer integer sequences is considered through a series of examples (the chosen examples are related to the Tower of Hanoi problem on 3 pegs). By definition, transducer integer sequences are integer sequences produced, under a suitable interpretation, by finite transducers encoding rational tree morphisms (length and prefix preserving transformations of words that have only finitely many distinct sections). \end{abstract} \section{Introduction} It is known from the work of Allouche, B\'etr\'ema, and Shallit (see~\cite{allouche-b-s:hanoi,allouche-s:as}) that a squarefree sequence on 6 letters can be obtained by encoding the optimal solution to the standard Tower of Hanoi problem on 3 pegs by an automaton on six states. Roughly speaking, after reading the binary representation of the number $i$ as input word, the automaton ends in one of the 6 states. These states represent the six possible moves between the three pegs; if the automaton ends in state $q_{xy}$, this means that the one needs to move the top disk from peg $x$ to peg $y$ in step $i$ of the optimal solution. The obtained sequence over the 6-letter alphabet $\{\ q_{xy} \mid 0 \leq x,y \leq 2, \ x \neq y \ \}$ is an example of an automatic sequence. We choose to work with a slightly different type of automata, which under a suitable interpretation, produce integer sequences in the output. The difference with the above model, again roughly speaking, is that not only the final state matters, but the output depends on every transition step taken during the computation and both the input and the output words are interpreted as encodings of integers. The integer sequences that can be obtained this way are called transducer integer sequences. We provide some examples that illustrate the notion of a transducer integer sequence. The chosen examples are related to the Tower of Hanoi problem on 3 pegs, but one could certainly provide and study a variety of different examples. The choice was guided by the need for relatively familiar and appealing setting that is, at the same time, mathematically challenging and interesting. In recent years, a very fruitful line of research in group theory has led to the notion of a self-similar group~\cite{nekrashevych:b-selfsimilar} (also known as automata groups~\cite{grigorchuk-n-s:automata} or state closed groups~\cite{sidki:circuit}). Many challenging problems have been solved by using finite automata to encode groups of tree automorphisms with interesting properties, leading to solutions to outstanding problems. To name just a few, examples include first Grigorchuk group~\cite{grigorchuk:burnside}, solving the problem of Milnor on existence of groups of intermediate growth and the Day-von Neumann problem on existence of amenable but not elementary amenable groups; the Basilica group~\cite{grigorchuk-z:basilica1,bartholdi-v:basilica}, providing an example of amenable but not subexponentially amenable group; Wilson groups~\cite{wilson:nonuniform}, solving the problem of Gromov on existence of groups of non-uniform exponential growth; the realization of the lamplighter group $L_2$ by an automaton~\cite{grigorchuk-z:l2}, leading to the solution of the Strong Atiyah Conjecture on $L^2$-Betti numbers~\cite{grigorchuk-al:atiyah}, and the recent solution to Hubbard's twisted rabbit problem in holomorphic dynamics~\cite{bartholdi-n:rabbit}. The geometric language and insight coming from the interpretation of the action of the automata as tree automorphisms greatly simplifies the presentation and helps in the understanding of the underlying phenomena, such as self-similarity, contraction, branching, etc (see~\cite{grigorchuk-n-s:automata,bartholdi-g-s:branch,bartholdi-g-n:fractal,nekrashevych:b-selfsimilar} for definitions, examples, and details). In the current article we use automata in the sense of transducers. As such, they generate self-similar groups (or semigroups) of tree automorphisms (or endomorphisms). In the same time, the input and the output words are interpreted as encodings of integers, bringing the topic closer to the topic of automatic sequences. Thus, it is not surprising that the concrete examples of transducer integer sequences that are exhibited here all gave high level of self-similarity and can be defined as limits of certain iterations of sequences. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Rational tree morphisms and finite transducers}\label{s:tree} For $k \geq 2$ denote $X_k=\{0,1,\dots,k-1\}$. The free monoid $\treek$ has the structure of a $k$-ary \emph{rooted tree} $\treek$ in which the \emph{empty word} $\emptyset$ is the \emph{root}, the words of length $n$ constitute \emph{level $n$} and each vertex $v$ has $k$ \emph{children}, namely $vx$, for $x$ a letter in $X_k$ (see Figure~\ref{3tree} for the ternary tree). \begin{figure}[!ht] \begin{center} \[ \xymatrix@C=7pt{ &&&& \emptyset \ar@{-}[llld] \ar@{-}[d] \ar@{-}[rrrd]& \\ & 0 \ar@{-}[ld] \ar@{-}[d] \ar@{-}[rd] && & 1 \ar@{-}[ld] \ar@{-}[d] \ar@{-}[rd] && & 2 \ar@{-}[ld] \ar@{-}[d] \ar@{-}[rd] && \\ 00& 01& 02& 10& 11& 12& 20& 21& 22 \\ \dots& \dots& \dots& \dots& \dots& \dots& \dots& \dots& \dots& } \] \caption{Ternary rooted tree}\label{3tree} \end{center} \end{figure} The tree structure imposes order on $X_k^*$, which is the well known \emph{prefix order}. Namely, we say that $u \leq v$ if $u$ is a vertex on the unique geodesic from $\emptyset$ to $v$ in $\treek$, which is equivalent to saying that $u$ is a \emph{prefix} of $v$. A map $\mu: X_{k_1}^* \to X_{k_2}^*$ is a \emph{tree morphism} if it preserves the word length and the prefix relation, i.e \[ |\mu(u)| = |u| \qquad\text{and}\qquad \mu(u) \leq \mu(uw), \] for all words $u$ and $w$ over $X_{k_1}$. In the case when $k_1=k_2$, morphisms are called \emph{endomorphisms} and bijective endomorphisms are called \emph{automorphisms}. Every tree morphism $\mu:X_{k_1}^* \to X_{k_2}^*$ can be decomposed as \[ \mu = \pi_\mu (\mu_0,\dots,\mu_{k_1-1}) \] where $\pi_\mu:X_{k_1} \to X_{k_2}$ is a map called the \emph{root transformation} of $\mu$ and $\mu_x: X_{k_1}^* \to X_{k_2}^*$, $x$ in $X_{k_1}$, are tree morphisms called the \emph{sections} of $\mu$. The root permutation and the sections of $\mu$ are uniquely determined by the recursive relation \[ \mu(xw) = \pi_\mu(x) \mu_x(w),\] which holds for every letter $x$ and word $w$ over $X_{k_1}$. Thus the sections describe the action of $\mu$ on the $k_1$ subtrees hanging below the root in $X_{k_1}^*$ and the root transformation $\pi_\mu$ describes the action of $\mu$ at the root. The tree morphisms act on the left and the composition is performed from right to left, yielding the formula \begin{equation}\label{composition} \mu \nu = \pi_\mu (\mu_0,\dots,\mu_{k_1-1}) \pi_\nu (\nu_0,\dots,\nu_{k_1-1}) = \pi_\mu \pi_\nu (\mu_{\pi_\nu(0)}\nu_0, \dots, \mu_{\pi_\nu(k_1-1)}\nu_{k_1-1}). \end{equation} The notion of a section of a tree morphism $\mu:X_{k_1} \to X_{k_2}$ can be recursively extended to all vertices of the tree $X_{k_1}^*$ by setting $\mu_\emptyset = \mu$ and $\mu_{wx} = (\mu_w)_x$, for $w$ a word over $X_{k_1}$ and $x$ a letter in $X$. A tree morphism is \emph{rational} if it has only finitely many distinct sections. A quite efficient way of defining rational tree morphisms is by using finite synchronous transducers. A \emph{finite $k_1$ to $k_2$ synchronous transducer} is a 5-tuple $\A=(Q,X_{k_1},X_{k_2},\tau,\pi)$, where $Q$ is a finite set of \emph{states}, $X_{k_1}$ and $X_{k_2}$ are the \emph{input and output alphabets}, $\tau:Q \times X_{k_1} \to Q$ is a map called the \emph{transition map} of $\A$, and $\pi:Q \times X_{k_1} \to X_{k_2}$ is a map called the \emph{output map} of $\A$. Every state $q$ of the finite transducer $\A$ defines a tree morphism, also denoted $q$ by setting $q_x=\tau(q,x)$, for $x \in X_{k_1}$, and $\pi_q: X_{k_1} \to X_{k_2}$ to be the restriction of $\pi$ defined by $\pi_q(x) = \pi(q,x)$. Thus, for each state $q$ of $\A$ we have \begin{equation}\label{qxw} q(\emptyset) = \emptyset \qquad\text{and}\qquad q(xw) = \pi_q(x)q_x(w), \end{equation} for $x$ a letter in $X_k$ and $w$ a word over $X_k$. When started at state $q$, the transducer reads the first input letter $x$, produces the first letter of the output according to the transformation $\pi_q$ and changes its state to $q_x$. The state $q_x$ then handles the rest of the input and output. The states of a $k$-ary transducer (transducer in which $k_1=k_2=k$) define $k$-ary tree endomorphisms. An \emph{invertible} $k$-ary transducer is a transducer in which $k_1=k_2=k$ and the transformation $\pi_q$ is a permutation of $X_k$, for each state $q$ in $Q$. The states of an invertible $k$-ary transducer define $k$-ary tree automorphisms. When $k_1 \leq k_2$ and, for each state $q$, the vertex transformation $\pi_q$ is injective then every state of the transducer $\A$ is an embedding of the $k_1$-ary tree into the $k_2$-ary tree. We call such a transducer an \emph{injective transducer}. When $\A=(Q,X_{k_1},X_{k_2},\tau,\pi)$ is injective transducer one can define a partial inverse transducer $\A^{-1} = (Q^{-1}, X_{k_2},X_{k_1},\tau^{-1},\pi^{-1})$ in which $Q^{-1}=\{q^{-1}\mid q\in Q\}$, and $\tau^{-1}:Q^{-1} \times X_{k_2} \to Q^{-1}$ and $\pi^{-1}:Q^{-1} \times X_{k_2} \to X_{k_1}$ are partial maps, defined by $\tau^{-1}(q^{-1},y) = p^{-1}$ and $\pi^{-1}(q^{-1},y)=x$ whenever $\tau(q,x) = p$ and $\pi(p,x)=y$. For a state $q$ in $Q$ and words $u$ in $X_{k_1}^*$ and $v$ in $X_{k_2}^*$ we then have \[ q(u) = v \qquad \text{if and only if} \qquad q^{-1}(v)=u. \] Moreover, the composition $q^{-1}q: X_{k_1}^* \to X_{k_1}^*$ is the identity map on $X_{k_1}^*$ and the composition $qq^{-1}: q(X_{k_1}^*) \to q(X_{k_1}^*)$ is the identity map on the range $q(X_{k_1}^*)$ of the morphism $q$ in $X_{k_2}^*$. The partial morphism $q^{-1}$ is not defined at any vertex of $X_{k_2}^*$ that is not in the range $q(X_{k_1}^*)$ of $q$. For such an input word $w$, starting at the state $q^{-1}$, the work of the partial inverse transducer $\A^{-1}$ stops before reading the whole input word, because not all possible transition steps are defined. In this sense, the partial inverse transducer may be used to recognize the range of the injective morphism $q$. Namely, the transducer $\A^{-1}$ \emph{accepts} the word $w$ if and only if it can read it completely, in which case the output word is precisely $q^{-1}(w)$. The boundary $\partial \treek$ of the $k$-ary tree $\treek$ consists of all infinite (to the right) words over $X_k$. The boundary has a structure of an ultrametric space homeomorphic to a Cantor set. The recursive definition \eqref{qxw} applies to both finite and infinite words $w$. The action of a state $q$ of a $k$-ary transducer on the boundary $\partial \treek$ is by continuous maps, while the action of an invertible $k$-ary transducer is by isometries. More on relations between rational morphisms of rooted trees and transducers can be found in~\cite{grigorchuk-n-s:automata}. There are two common ways to represent finite $k_1$ to $k_2$ transducers by labeled directed graphs such as the ones in Figure~\ref{ah-al}. The graph on the left represents an invertible ternary transducer. The vertices are the states, each state $q$ is labeled by its corresponding root transformation (in this case permutation) $\pi_q$, and the edges labeled by the letters from $X_3$ define the transition function $\tau$ (for every $q$ in $Q$ and $x$ in $X_3$ there exists an edge from $q$ to $q_x=\tau(q,x)$ labeled by $x$). The graph on the right represents a non-invertible ternary transducer. The vertices are the states and for each pair $(q,x)$ in $Q \times X_3$ an edge labeled by $x \ | \ \pi_q(x) $ connects $q$ to $q_x$. One can easily switch back and forth between the two formats. We refer to the second form (the one in which the output is indicated on the edges) as the \emph{Moore diagram} of the transducer. \begin{figure}[!ht] \begin{center} \begin{tabular}{cc} \SelectTips{cm}{} \xymatrix@C=45pt@R=45pt{ & *++[o][F-]{{\scriptstyle(01)}}\ar@/_/[d]_{0}\ar@/^/[d]^{1}\ar@(ul,l)_{2}\ar@{}[ddr]^<<<{a_{01}} & \\ & *++[o][F-]{{\scriptstyle()}}\ar@(ul,l)_{0,1,2} \ar@{}[r]^<<<{id}& \\ *++[o][F-]{{\scriptstyle(02)}}\ar@/_/[ur]_{2}\ar@/^/[ur]^{0}\ar@(ul,l)_{1}\ar@{}[rr]_<<<{a_{02}} & \A_H & *++[o][F-]{{\scriptstyle(12)}}\ar@/_/[ul]_{1}\ar@/^/[ul]^{2}\ar@(ur,r)^{0}\ar@{}[ll]^<<<{a_{12}} } & \SelectTips{cm}{} \xymatrix@C=35pt{ \\ \\ & *++[o][F-]{} \ar@/^1pc/[rr]^{2/1} \ar@(u,ul)_{0/0} \ar@(d,dl)^{1/1} \ar@{}[l]|<<<<{\textstyle\alpha} && *++[o][F-]{} \ar@/^1pc/[ll]^{0/1} \ar@(u,ur)^{1/1} \ar@(d,dr)_{2/0} \ar@{}[r]|<<<<{\textstyle\beta} & \\ && \A_L } \end{tabular} \caption{An invertible ternary transducer $\A_H$ and a non-invertible ternary transducer $\A_L$} \label{ah-al} \end{center} \end{figure} For $0\leq i < j \leq 2$, the ternary tree automorphisms $a_{ij}$ from the transducer $\A_H$ are defined recursively by \[ \begin{cases} a_{ij}(\emptyset) = \emptyset, \\ a_{ij}(iw) = jw, \\ a_{ij}(jw) = iw, \\ a_{ij}(xw) = xa_{ij}(w), & x \not\in \{i,j\}, \end{cases} \] for a word $w$ over $X_3$. In simple terms, the only effect the transformation $a_{ij}$ has on a word $w$ over $X_3$ is that it changes the very first appearance of either of the symbols $i$ or $j$ in $w$ to the other symbol, if such an appearance exists. To simplify the notation, we write \[ a = a_{01}, \qquad b = a_{02}, \qquad\text{and}\qquad c = a_{12}. \] The state labeled by $id$ does not change any input word and represents the identity automorphism of the ternary tree. It is clear that $a$, $b$ and $c$ are self-invertible transformations of $X_3^*$, i.e~$a^2=b^2=c^2=id$. The 3 to 2 tree morphisms defined by the transducer $\A_L$ are defined recursively by \begin{alignat*}{4} \alpha(\emptyset) &= \emptyset, \qquad & \alpha(0w) &= 0\alpha(w),\qquad & \alpha(1w) &= 1\alpha(w), \qquad & \alpha(2w) &= 1\beta(w), \\ \beta(\emptyset) &= \emptyset, \qquad & \beta(0w) &= 1\alpha(w),\qquad & \beta(1w) &= 1\beta(w), \qquad & \beta(2w) &= 0\beta(w). \end{alignat*} \begin{definition} The semigroup (group) of $k$-ary tree endomorphisms (automorphisms) generated by all the states of an (invertible) $k$-ary transducer $\A$ is called the semigroup (group) of $\A$ and is denoted by $S(\A)$ ($G(\A)$). \end{definition} The group $G(\A_H)$ is introduced in~\cite{grigorchuk-s:hanoi-cr}, where it is called the Hanoi Towers group on 3 pegs (in fact, one Hanoi Towers group $\mathcal{H}^{(k)}$ is introduced for each number of pegs $k \geq 3$). The name is derived from the fact that the group $\Ht$ models the well-known Tower of Hanoi problem on 3 pegs. To recall, the Tower of Hanoi problem on 3 pegs and $n$ disks is the following. In a valid $n$ disk configuration, disks of different size, labeled by $1,2,\dots,n$ according to their size, are placed on three pegs, labeled 0,1 and 2, in such a way that no disk is placed on top of a smaller disk. In a single move the top disk from one peg can be moved and placed on top of another peg, as long as the newly obtained configuration is still valid. Initially all $n$ disks are placed on peg 0 and the problem asks for an optimal algorithm that moves all disks to another peg. Each valid configuration of $n$ disks can be encoded by a word of length $n$ over $X_3$. The word $x_1 \dots x_n$ represents the unique valid configuration in which disk $i$ is placed on peg $x_i$. The ternary tree automorphism $a_{ij}$ then represents a move between peg $i$ and peg $j$ (in either direction). For example the move between peg 0 and peg 2 illustrated in Figure~\ref{move} is encoded by $a_{02}(10212) = 12212$. \begin{figure}[!ht] \begin{center} \includegraphics[height=60pt]{h35move-a.eps} \end{center} \caption{A move between peg 0 and peg 2}\label{move} \end{figure} The action of $\Ht$ on the ternary tree is level transitive, meaning that it is transitive on the levels of the tree. This is equivalent to the statement that any valid configuration on $n$ disks can be obtained from any other valid configuration on $n$ disks by legal moves. Consider the stabilizer $P_n$ of the vertex $0^n$ in $\Ht$. The group $\Ht$ acts on the set $\Ht/P_n$ of left cosets of $P_n$. The action is described by the corresponding Schreier graph $\Gamma_n = \Gamma_n(\Ht,P_n,S)$ of $P_n$ with respect to the generating set $S=\{a,b,c\}$. The vertices are the cosets of $P_n$ and there is an edge connecting $hP_n$ to $shP_n$ for every coset $hP_n$ and generator $s$ in $S$. Since $h' \in hP_n$ if and only if $h'(0^n) = h(0^n)$ the vertices of the Schreier graph $\Gamma_n$ can be encoded by the vertices of the $n$-th level of the ternary tree (the coset $hP_n$ is labeled by $h(0^n)$) and two vertices are connected if and only if one is the image of the other under $s$, for some generator $s$ in $S$. The Schreier graph $\Gamma_3$ corresponding to level 3 of the ternary tree is given in Figure~\ref{sierpinski3}. \begin{figure}[!ht] \begin{center} \[ \SelectTips{cm}{} \xymatrix@C=3pt{ & & & & & & & 111 \ar@{-}@(ur,ul)_{\textstyle b} \\ & & & & & & 011 \ar@{-}[rr]_{\textstyle b} \ar@{-}[ur]^{\textstyle a} & & 211 \ar@{-}[ul]_{\textstyle c} \\ & & & & & 021 \ar@{-}[ur]^{\textstyle c} & & & & 201 \ar@{-}[ul]_{\textstyle a} \\ & & & & 221 \ar@{-}[rr]_{\textstyle c} \ar@{-}[ur]^{\textstyle b} & & 121 \ar@{-}[rr]_{\textstyle b} \ar@{-}[ul]_{\textstyle a} & & 101 \ar@{-}[rr]_{\textstyle a} \ar@{-}[ur]^{\textstyle c} & & 001 \ar@{-}[ul]_{\textstyle b} \\ & & & 220 \ar@{-}[ur]^{\textstyle a} & & & & & & & & 002 \ar@{-}[ul]_{\textstyle c} \\ & & 120 \ar@{-}[rr]_{\textstyle a} \ar@{-}[ur]^{\textstyle c} & & 020 \ar@{-}[ul]_{\textstyle b} & & & & & & 202 \ar@{-}[rr]_{\textstyle c} \ar@{-}[ur]^{\textstyle b} & & 102 \ar@{-}[ul]_{\textstyle a} \\ & 100 \ar@{-}[ld]_{\textstyle a} \ar@{-}[rd]^{\textstyle c} \ar@{-}[ur]^{\textstyle b} &&&& 010 \ar@{-}[ld]_{\textstyle b} \ar@{-}[rd]^{\textstyle a} \ar@{-}[ul]_{\textstyle c} &&&& 212 \ar@{-}[ld]_{\textstyle c} \ar@{-}[rd]^{\textstyle b} \ar@{-}[ur]^{\textstyle a} &&&& 122 \ar@{-}[ld]_{\textstyle a} \ar@{-}[rd]^{\textstyle c} \ar@{-}[ul]_{\textstyle b} \\ 000 \ar@{-}[rr]_{\textstyle b} \ar@{-}@(l,d)_{\textstyle c} && 200 \ar@{-}[rr]_{\textstyle a} && 210 \ar@{-}[rr]_{\textstyle c} && 110 \ar@{-}[rr]_{\textstyle b} && 112 \ar@{-}[rr]_{\textstyle a} && 012 \ar@{-}[rr]_{\textstyle c} && 022 \ar@{-}[rr]_{\textstyle b} && 222 \ar@{-}@(r,d)^{\textstyle a} } \] \caption{The Schreier graph of $\Ht$ at level 3}\label{sierpinski3} \end{center} \end{figure} Since all generators have order 2, no directions are indicated on the edges. The sequence of graphs $\{\Gamma_n\}$ converges to an infinite graph $\Gamma$ in the space of pointed graphs based at $0^n$ (see~\cite{grigorchuk-z:cortona} for definitions of this space), which is the Schreier graph $\Gamma=\Gamma(\Ht,P,S)$, where $P=\cap_{n=0}^\infty P_n$ is the stabilizer of the infinite ray $0^\infty=000\dots$ on the boundary of the ternary tree. One can think of the limiting graph both as the Schreier graph of the action of $\Ht$ on the orbit of the infinite ray $0^\infty$ in $\partial X_3^*$ or as the model of Tower of Hanoi problem representing all valid configurations that can be reached from the configuration in which (countably) infinitely many disks are placed on peg $0$ (this configuration corresponds to the infinite word $0^\infty$). We denote this graph by $\Gamma_{0^\infty}$. Graphs similar to $\Gamma_n$, modeling the Tower of Hanoi problem are well known in the literature, but there is a subtle difference. Namely, the difference with the corresponding graphs in~\cite{hinz:ens} modeling the Tower of Hanoi problem is that the edges in $\Gamma_3$ are labeled (by the corresponding tree automorphisms) and our graphs have loops at the corners (corresponding to situations in which all disks are on one peg and the generator corresponding to a move between the other two pegs does not change anything), which turn them into 3-regular graphs. Finite dimensional permutational representations of $\Ht$ based on the action on the levels of the ternary tree were used in~\cite{grigorchuk-s:hanoi-cr} to calculate the spectrum of the graphs $\Gamma_n$ as well as the limiting infinite graph $\Gamma$. Among interesting properties of $\Ht$ we mention that it is an amenable (but not subexponentially amenable), regular branch group over its commutator, it is not just infinite and its closure in the pro-finite group of ternary tree automorphisms is finitely constrained. Moreover, $\Ht$ is (up to conjugation) the iterated monodromy group of the finite rational map $z \mapsto z^2 - \frac{16}{27z}$, whose Julia set is the Sierpi{\'n}ski gasket. This explains the fact that the sequence of Schreier graphs $\{\Gamma_{0^n}\}$ approximates the Sierpi{\'n}ski gasket. For more information on properties of $\Ht$ we refer the interested reader to~\cite{grigorchuk-s:hanoi-cr,grigorchuk-s:standrews,grigorchuk-n-s:oberwolfach1,grigorchuk-n-s:oberwolfach2}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Transducer integer sequences} We first recall the well established notion of automatic sequence. The definition that follows (Definition~\ref{d:as}) uses one of the equivalent formulations that can be found in~\cite{allouche-s:as} (see Definition~5.1.1 and Theorem~5.2.3). A $k$-ary \emph{finite automaton with final state output} ($k \geq 2$) is a 6-tuple $\A=(Q,X_k,Y,s,\tau,\pi)$, where $Q$ is a finite set, called set of \emph{states}, $X_k=\{0,\dots,k-1\}$ is the \emph{input alphabet}, $Y$ is a finite set called the \emph{output alphabet}, $s$ is an element in $Q$ called the \emph{initial state}, $\tau:Q \times X \to Q$ is a map called \emph{transition map} and $\pi:Q \to Y$ is a map called \emph{final state output map}. For every input word $w$ over $X_k$, the automaton $\A$ produces a unique output symbol $y_w$ from $Y$, defined as the image $\pi(q)$ of the state $q$ the automaton reaches after it reads the input word $w$ starting from the initial state $s$. Thus $y_w = \pi(\tau(s,w))$, where $\tau:Q \times X^* \to Q$ is the recursive extension of $\tau$ on $Q \times X^*$ defined by $\tau(q,\emptyset)=q$ and $\tau(q,xu) = \tau(\tau(q,x),u)$, for $q$ a state in $Q$, $x$ a letter in $X_k$, and $u$ a word over $X_k$. If, for every word $w$ over $X_k$ and every finite sequence $0^m$ of zeros, the output $y_w$ is equal to the output $y_{w0^m}$ we say that the automaton $\A$ \emph{tolerates trailing zeros}. An automaton $\A$ that tolerates trailing zeros defines an infinite sequence $y_0,y_1,y_2,\dots$ over the output alphabet $Y$, called the \emph{final state output sequence} of $A$, as follows. For a natural number $i\geq 0$ let $[i]_k=i_0\dots i_m$ be any base $k$ representation of $i$ with $i = \sum_{j=0}^m i_j k^j$ (thus the least significant digit is written first and we may have any number of trailing zeros). The term $y_i$ in the final state output sequence is defined as the image $\pi(q)$ of the state $q$ the automaton reaches after it reads the input word $[i]_k$ starting from the initial state $s$, i.e., \[ y_i = \pi(\tau(s,[i]_k)). \] Automata with final state output can be represented by labeled directed graphs similar to the ones representing transducers. The only significant difference is that each state $q$ is labeled by the corresponding output letter $\pi(q)$ and the initial state is indicated by an incoming arrow. As an example, consider the ternary automaton $\A_{0-2}$ in Figure~\ref{a02}. \begin{figure}[!ht] \begin{center} \[ \SelectTips{cm}{} \xymatrix@C=55pt{ *++[o][F-]{1} \ar@(ul,l)_{0,1,2} \ar@{}[r]^<<<<{\textstyle a_0} & *++[o][F-]{1}\ar@{->}[l]^{0}\ar@{->}[r]_{2}\ar@(dl,dr)_{1}\ar@(u,u)\ar@{}[r]^<<<<{\textstyle a_1} & *++[o][F-]{\text{-1}} \ar@(ur,r)^{0,1,2}\ar@{}[l]_<<<<{\textstyle a_2} } \] \caption{A ternary automaton with final state output $\A_{0-2}$}\label{a02} \end{center} \end{figure} \begin{definition}\label{d:as} A $k$-ary automatic sequence is an infinite sequence that can be obtained as the final state output sequence of some $k$-ary finite automaton that tolerates trailing zeros. \end{definition} Note that Theorem~5.2.3 in~\cite{allouche-s:as} allows us to choose among several other, seemingly less restrictive, settings but we selected the one that reads integer representations starting from the least significant digit and that handles trailing zeros because it parallels what we are about to see (Definition~\ref{d:tis}) when we switch our attention to transducer integer sequences. By Cobham's theorem~\cite{cobham:tags}, a sequence over a finite alphabet is a $k$-ary automatic sequence if and only if it is an image under a coding of a fixed point of a $k$-uniform endomorphism. Given a free monoid $X^*$ over a finite alphabet $X$, an endomorphism $\alpha:X^* \to X^*$ can be uniquely defined by specifying the images of the letters in $X$ under $\alpha$. Suppose that, for all letters $x$ in $X$, $\alpha(x)\neq \emptyset$ and that there exists a letter $x$ in $X$ such that $\alpha(x) = xw$, where $w$ is a non-empty word. Then, for all $n \geq 0$, the $n$-th iterate $\alpha^n(x)$ is a proper prefix of the $(n+1)$-th iterate $\alpha^{n+1}(x)=\alpha(\alpha^n(x))$ and the limit $\llim \alpha^n(x)$ is a well defined infinite sequence over $X$. In the particular case when the length of all the words $\alpha(x)$, $x \in X$, is equal to $k$, the morphism $\alpha$ is called a $k$-uniform endomorphism. The following example provides a cube-free automatic sequence that both illustrates the concept of automatic sequence and the claim of Cobham's theorem. In addition, this example will play a role in our further considerations. \begin{example}[Cube-free automatic sequence] Let $X=\{1,-1\}$ and denote by $w_\alpha$ the infinite binary sequence \[ w_\alpha = \llim \alpha^n(1) = 11 \, \text{-}1 \ 11\, \text{-}1 \ 1 \, \, \text{-}1\, \text{-}1 \ 11 \, \text{-}1 \ 11\, \text{-}1 \ 1\, \text{-}1 \, \text{-}1 \ 11 \, \text{-}1 \ 1 \,\text{-}1 \, \text{-}1 \ 1 \, \text{-}1 \, \text{-}1 \dots~ \] obtained by iteration, starting from 1, of the endomorphism $\alpha:X^* \to X^*$ given by (compare to sequence \seqnum{A080846}; all sequence references are to The On-Line Encyclopedia of Integer Sequences~\cite{sloane:online}) \[ 1 \mapsto 11 \, \text{-}1 \qquad \text{-}1 \mapsto 1 \, \text{-}1 \, \text{-}1. \] A finite or infinite word $w$ over an alphabet $X$ is cube-free if it does not contain a subword of the form $uuu$, where $u$ is a nontrivial finite word over $X$. The infinite sequence $w_\alpha$ is cube-free. This claim can be easily verified by using the criterion of Richomme and Wlazinski~\cite{richomme-w:cube-free}, which only requires checking that \[ \alpha(11 \, \text{-}1 \, \text{-}11 \, \text{-}11 \, \text{-}1 \, \text{-}11 \, \text{-}1 \, \text{-}111 \, \text{-}111 \, \text{-}11 \, \text{-}111 \, \text{-}1 \, \text{-}1) \] is cube-free. We offer two additional descriptions of $w_\alpha$. Define a sequence of words $w_{[n]}$ of length $3^n$ by \begin{align*} w_{[0]} &= 1, \\ w_{[n+1]} &= w_{[n]} w_{[n]} w_{[n]}', \end{align*} where $w_{[n]}'$ is obtained from $w_{[n]}$ by changing the middle symbol in $w_{[n]}$ from 1 to -1. The limit $\llim w_{[n]}$ is well defined and is equal to $w_\alpha$. For an integer $i \geq 0$, let $(i)_k=i_0i_1 \dots $ be the sequence of digits in base $k$ representation of $i$, where $i = \sum_{j=0}^\infty i_jk^j$ (the sequence ends in infinitely many 0's). Call a natural number $i$ a 2-before-0 number if the least significant digit in the ternary representation $(i)_3$ of $i$ that is different from 1 is 2. Otherwise the number is called a 0-before-2 number. Define an infinite sequence $x_0,x_1,x_2,\dots,$ by \[ x_i = \begin{cases} 1, & \text{if }i \text{ is a 0-before-2 number}\\ -1, & \text{if }i \text{ is a 2-before-0 number} \end{cases}. \] The infinite binary sequence $x_0,x_1,x_2,\dots,$ is equal to $w_\alpha$. We claim that the infinite sequence $w_\alpha$ is a ternary automatic sequence. It can be obtained as the final state output sequence of the automaton $\A_{0-2}$. Indeed, the only time the automaton $\A_{0-2}$ produces -1 in the output is if it reaches the state $a_2$, which only happens if $i$ is a 2-before-0 number. \end{example} We define now the notion of a transducer integer sequence. \begin{definition}\label{d:tis} A $k_1$ to $k_2$ \emph{transducer integer sequence} is a sequence of integers $\{z_i\}_{i=0}^\infty$ such that there exists a $k_1$ to $k_2$ transducer $\A$ and a state $q$ in $\A$ such that, for every $i \geq 0$, the output word $q((i)_{k_1})$ is the base $k_2$ representation of $z_i$. \end{definition} Note that, by the above definition, not every transducer defines a transducer integer sequence, since some attention needs to be paid to trailing zeros. Namely, it is implicit in the definition that the state $q$ of $\A$ maps the cofinal class of $0^\infty$ in $\partial X_{k_1}^*$ to the cofinal class of $0^\infty$ in $\partial X_{k_2}^*$ (the cofinal class of $0^\infty$ is just the set of infinite words ending in $0^\infty$). We keep our attention only to this class since it is the one describing non-negative integers. We should perhaps point out that the equivalent formulation of the definition of automatic sequence provided by Theorem~5.2.4 in~\cite{allouche-s:as} even more closely parallels our definition of transducer integer sequence than the one we gave in Definition~\ref{d:as}. \begin{example} Let $\A_T$ be the ternary transducer in Figure~\ref{at}. \begin{figure}[!ht] \begin{center} \[ \xymatrix{ *++[o][F-]{} \ar@{->}[rr]^{0/1}_{2/1} \ar@(ul,dl)_{1/0} \ar@(u,u) \ar@{}[rr]_<<<{\textstyle \sigma_1} && *++[o][F-]{} \ar@(ur,dr)^{0,1,2/0} \ar@{}[ll]^<<<{\textstyle \sigma_0} } \] \caption{A ternary transducer $\A_T$}\label{at} \end{center} \end{figure} The state labeled by $\sigma_0$ just rewrites all digits to 0. Clearly, \[ \sigma_1(1^n0w) = \sigma_1(1^n2w) = 0^n10^\infty \] for any word $w$ in the cofinal class of $0^\infty$. Since $(0^n10^\infty)_3 = 3^n$ the obtained integer sequence $\{a_n\}_{n=0}^\infty$ is (compare to sequence \seqnum{A038500}) \[ 1,3,1,\ 1,9,1,\ 1,3,1,\ 1,3,1,\ 1,27,1,\ 1,3,1,\ 1,3,1,\ 1,9,1,\ 1,3,1,\dots~. \] By thinking of the powers of 3 as an (infinite) alphabet, this sequence can be thought of as the fixed point of the iterations starting from 1 of the 3-uniform endomorphism defined by \[ x \mapsto 1, \ 3x, \ 1~. \] This sequence can also be defined by blocks $a_{[n]}$ of length $3^n$ as \[ a_{[0]} = 1 \qquad\qquad a_{[n+1]} = a_{[n]}a_{[n]}'a_{[n]}, \] where $a_{[n]}'$ is obtained from $a_{[n]}$ by multiplying the middle term by 3. \end{example} The next example shows that there exist sequences of integers, and even bounded sequences of integers, that are not transducer integer sequences. \begin{example} The sign sequence (see \seqnum{A057427}) \[ 0,1,1,1,1,1,1,1,1,1,1 \dots~ \] is not a transducer integer sequence. Indeed, regardless of the cardinality of the chosen alphabets $X_{k_1}$ and $X_{k_2}$, the fact that $0^\infty$ must be mapped to $0^\infty$ (this is simply because the 0 term of the sign sequence is 0) implies that the positive number $k_1^n$ represented by $0^n10^\infty$ must be mapped either to 0 or to a number of size at least $k_2^n$, which is greater than 1 for $n \geq 1$. Here one sees in practice the important difference between the work of automata with final state output and the work of (synchronous) transducers. While the former can wait for the whole input before deciding on the output the latter must produce output at every transition step. In the above situation it is impossible for the transducer ``to know in advance'' if non-zero digits will be read at some point in the input and this makes it impossible to provide a correct output (since the correctness of the output crucially depends on the first digit of the output). \end{example} The following proposition provides a necessary condition for an integer sequence to be a transducer integer sequence. \begin{proposition} Let $\A=(Q,X_{k_1},X_{k_2},\tau,\pi)$ be a finite $k_1$ to $k_2$ synchronous transducer, and let $\{z_i\}_{i=0}^\infty$ be the transducer integer sequence defined by choosing $q$ in $Q$ as the initial state. Then the growth of the sequence $\{z_i\}_{i=0}^\infty$ is at most polynomial. More precisely, \[ z_i < k_2^{|Q|} \cdot i^{\log_{k_1}(k_2)}, \] for all $i\geq 0$. In particular, the growth of transducer integer sequences defined by rational tree endomorphisms is at most linear. \end{proposition} \begin{proof} We may assume that all states of $Q$ are accessible from $q$ (otherwise we can delete the unnecessary states and get even tighter upper bound on the growth of $\{z_i\}_{i=0}^\infty$). A $0$-path (cycle) in the Moore diagram of $\A$ is a directed path (cycle) in which each edge is labeled by $0|*$, where $*$ stands for arbitrary letters from $X_{k_2}$. Call such a path (cycle) nontrivial if at least one edge is labeled by $0|y$ for some nonzero $y$ in $X_{k_2}$. It is clear that $\A$ does not have nontrivial 0-cycles (otherwise some elements in the cofinal class of $0^\infty$ would be mapped to elements outside this class). Thus, the longest length of a non-trivial 0-path is $|Q|-1$ (any longer path would have to repeat vertices and therefore would contain a cycle). Therefore if $n$ is the smallest number of digits needed to write $i \geq 0$ in base $k_1$, then $z_i$ can be written in base $k_2$ by using no more than $n+|Q|-1$ digits. This gives the estimate \[ z_i < k_2^{n+|Q|-1} = k_2^{|Q|} \cdot k_2^{n-1} \leq k_2^{|Q|} \cdot k_2^{\log_{k_1}(i)} = k_2^{|Q|} \cdot i^{\log_{k_1}(k_2)}. \qedhere\] \end{proof} We end the section by considering another example of a transducer integer sequence (related to the transducer $\A_L$). Let $N_2$ be the set of all non-negative integers whose base 3 representation does not use the digit 2 (they are listed in sequence \seqnum{A005836}). Define a sequence $\{\ell_n\}_{n=0}^\infty$, called \emph{$L$-sequence} (see sequence \seqnum{A060374}), by \[ \ell_n = \ell_n^- + \ell_n^+ \] where $\ell_n^-$ and $\ell_n^+$ are the unique non-negative integers such that $\ell_n^-,\ \ell_n^+,\ \ell_n^- +\ell_n^+ \in N_2$ and $n=\ell_n^+ - \ell_n^-$ (the $L^-$-sequence $\{\ell_n^-\}_{n=0}^\infty$ is the sequence~\seqnum{A060373} and the $L^+$-sequence $\{\ell_n^+\}_{n=0}^\infty$ is the sequence~\seqnum{A060372}) \begin{theorem} The $L$-sequence is a ternary transducer integer sequence. It is generated by the transducer $\A_L$ with initial state $\alpha$. \end{theorem} \begin{proof} In fact, we will prove that in addition to the $L$-sequence, both the $L^-$-sequence and the $L^+$-sequence are ternary transducer sequences, and they are generated by the transducers $\A_{L^-}$ and $\A_{L^+}$ in Figure~\ref{L+} (in both cases with initial state $\alpha$). \begin{figure}[!ht] \begin{center} \begin{tabular}{cc} \SelectTips{cm}{} \xymatrix@C=35pt{ & *++[o][F-]{} \ar@/^1pc/[rr]^{2/1} \ar@(u,ul)_{0/0} \ar@(d,dl)^{1/0} \ar@{}[l]|<<<<{\textstyle\alpha} && *++[o][F-]{} \ar@/^1pc/[ll]^{0/0} \ar@(u,ur)^{1/1} \ar@(d,dr)_{2/0} \ar@{}[r]|<<<<{\textstyle\beta} & \\ && \A_{L^-} } & \SelectTips{cm}{} \xymatrix@C=35pt{ & *++[o][F-]{} \ar@/^1pc/[rr]^{2/0} \ar@(u,ul)_{0/0} \ar@(d,dl)^{1/1} \ar@{}[l]|<<<<{\textstyle\alpha} && *++[o][F-]{} \ar@/^1pc/[ll]^{0/1} \ar@(u,ur)^{1/0} \ar@(d,dr)_{2/0} \ar@{}[r]|<<<<{\textstyle\beta} & \\ && \A_{L^+} } \end{tabular} \caption{Ternary transducers $\A_{L^-}$ and $\A_{L^+}$} \label{L+} \end{center} \end{figure} Define the sequences $\{r_n^-\}_{n=0}^\infty$, $\{r_n^+\}_{n=0}^\infty$, and $\{r_n\}_{n=0}^\infty$ to be the integer sequences defined by the transducers $\A_{L^-}$, $\A_{L^+}$, and in $\A_L$, respectively. Observe that all three transducers have the same transition function (they only differ in the output function). The following table contains the information on all three transducers \[ \begin{array}{cc|ccc|ccc|c} & && \alpha &&& \beta & \\ \hline \text{input} & & 0 & 1 & 2 & 0 & 1 &2 & n \\ \hline &\A_{L^-} & 0 & 0 & 1 & 0 & 1 &0 & r_n^- \\ \text{output} &\A_{L^+} & 0 & 1 & 0 & 1 & 0 &0 & r_n^+ \\ &\A_{L} & 0 & 1 & 1 & 1 & 1 &0 & r_n \\ \hline \text{transition}& & \alpha & \alpha & \beta & \alpha & \beta & \beta \end{array} \] For example, the middle column under $\alpha$, indicates that when each of the transducers is in state $\alpha$ and the input digit in $n$ is 1 then the output digit in $\A_{L^-}$, $\A_{L^+}$, and $\A_L$ (and therefore the corresponding digit in $r_n^-$, $r_n^+$, and $r_n$) is 0, 1, and 1, respectively, and each of the transducers stays in the state $\alpha$. Since all three transducers use only the digits $0$ and $1$ in the output, it is clear that $r_n^-, \ r_n^+, \ r_n \in N_2$, for all $n \geq 0$. Further, it is easy to see that $r_n = r_n^- + r_n^+$, for all $n \geq 0$. Indeed, by checking the entries in the above table, we see that each output digit in the row corresponding to $r_n$ is exactly the sum of the two output digits in the rows corresponding to $r_n^-$ and $r_n^+$ (there is never a carryover in the calculation $r_n^- + r_n^+ = r_n$). Next, we see that $n+r_n^-=r_n^+$, for all $n \geq 0$. Note that the state $\alpha$ corresponds to the case when there is no carryover and the state $\beta$ corresponds to the case when there is a carryover of 1 for the next digit. For instance, when the transducers are in state $\alpha$ and the input digit is 2, then the output digit in $r_n^-$ is 1, the output digit in $r_n^+$ is 0 and the transition entry indicates that all three transducers move to the carryover state $\beta$ (note that $2+1=3$). When the transducers are in the carryover state $\beta$ and the input digit is 0, then the output digit in $r_n^-$ is 0, the output digit in $r_n^+$ is 1, and all three transducers move back to the state $\alpha$ (note that $0+0+1=1$; the last 1 in this sum comes from the carryover). The other 4 cases in the table are just as easy to verify. Thus the sequences defined by the transducers $\A_{L^-}$, $\A_{L^+}$, and $\A_L$ satisfy the requirements in the definition of $L^-$-sequence, $L^+$-sequence, and $L$-sequence, respectively. Let us prove a triple of sequences that satisfies these requirements is unique. By way of contradiction, assume that two distinct triples of sequences $\{h_n^-\}_{n=0}^\infty$, $\{h_n^+\}_{n=0}^\infty$, and $\{h_n\}_{n=0}^\infty$, as well as $\{s_n^-\}_{n=0}^\infty$, $\{s_n^+\}_{n=0}^\infty$, and $\{s_n\}_{n=0}^\infty$ satisfy the definition. Consider some $n$ at which these two triples of sequences differ from each other. Without loss of generality, assume that $s_n^- = h_n^-+m$, for some non-negative integer $m$. Then $s_n^+ = n + s_n^- = n + h_n^- +m = h_n^+ +m$ and $s_n = s_n^- + s_n^+ = h_n^- + h_n^+ +2m = h_n +2m$. Since the triples differ, $m$ must be positive. Note that there is no carryover in the ternary representation of the additions $h_n=h_n^- + h_n^+$ and $s_n=s_n^- + s_n^+$ (only the digits 0 and 1 are used). This means that the only possible pairs of digits appearing in the same position in the ternary representations of $h_n^-$ and $h_n^+$ (as well as $s_n^-$ and $s_n^+$) are $(0,0)$, (0,1), and $(1,0)$. Indeed, if the pair $(1,1)$ appeared, then the digit $2=1+1$ would appear in the ternary representation of the sum $h_n=h_n^- + h_n^+$. Let the least significant nonzero digit of $m$ appear in position $i$ and denote this digit by $x$. The following table describes all possible pairs of digits in position $i$ for $h_n^-$ and $h_n^+$ as well as the corresponding pair of digits for $s_n^-$ and $s_n^+$, depending on whether $x=1$ or $x=2$: \[ \begin{array}{c|c|c} & x=1 & x=2 \\ \hline (h_n^-,h_n^+) & (s_n^-,s_n^+) & (s_n^-,s_n^+) \\ \hline (0,0) & (1,1) & (2,2) \\ (0,1) & (1,2) & (2,0) \\ (1,0) & (2,1) & (0,2) \end{array} \] We see that in each case, either the digit 2 appears in one of the ternary representations of $s_n^-$ and $s_n^+$ or the pair of digits $(1,1)$ appears in the same position in $s_n^-$ and $s_n^+$, none of which is allowed. Thus we have a contradiction and there is only one triple of integer sequences satisfying the definition of $L^-$-sequence, $L^+$-sequence and $L$-sequence, which then must be the triple $\{r_n^-\}_{n=0}^\infty$, $\{r_n^+\}_{n=0}^\infty$, and $\{r_n\}_{n=0}^\infty$ defined by the transducers $\A_{L^-}$, $\A_{L^+}$, and $\A_L$, respectively. \end{proof} Let $\{p_n\}_{n=0}^\infty$ be the sequence defined by \[ p_0 = 0, \qquad\qquad p_n= \sum_{i=0}^{n-1} w_ia_i, \quad\text{ for }n \geq 1 \] where the sequence $\{w_n\}_{n=0}^\infty$ providing the signs is the cube-free sequence generated by the automaton $\A_{0-2}$ and $\{a_n\}_{n=0}^\infty$ is the transducer integer sequence generated by $\A_T$. \begin{proposition} The sequence $\{p_n\}$ is equal to the $L$-sequence. \end{proposition} \begin{proof} We have $p_0=0=\ell_0$ and, for $n$ a positive integer and $w$ a word over $X_3$, \begin{align*} \alpha(0w+1) &= \alpha(1w) = 1\alpha(w) = 0\alpha(w)+1 = \alpha(0w)+1,\\ \alpha(1^n0w+1) &= \alpha(21^{n-1}0w) = 11^{n-1}1\alpha(w) = 1^n0\alpha(w) + 3^n = \alpha(1^n0w) + 3^n,\\ \alpha(1^n2w+1) &= \alpha(21^{n-1}2w) = 11^{n-1}0\beta(w) = 1^n1\beta(w) - 3^n = \alpha(1^n2w) - 3^n, \\ \alpha(2^n0w+1) &= \alpha(0^n1w) = 0^n1\alpha(w) = 10^{n-1}1\alpha(w) - 1 = \alpha(2^n0w) - 1, \\ \alpha(2^n1w+1) &= \alpha(0^n2w) = 0^n1\beta(w) = 10^{n-1}1\alpha(w) - 1 = \alpha(2^n1w) - 1. \\ \end{align*} In each case the change in the value of $\alpha(i)$ is exactly $w_ia_i$, i.e., for all $i$, \[ \ell_{i+1} = \alpha(i+1) = \alpha(i) + w_ia_i = \ell_i+ w_ia_i \] and therefore the sequence of partial sums $\{p_n\}$ is exactly the $L$-sequence. \end{proof} The sequence $\{\ell_n\}_{n=0}^\infty$ can also be described as a fixed point of an endomorphism over the alphabet consisting of the elements of $N_2$. The iterations start at 0 and the endomorphism is given by \[ 0 \mapsto 0, 1 \qquad\qquad x \mapsto 3x+1, 3x, 3x+1, \quad \text{ for } x\geq 1. \] \section{Relation to the Tower of Hanoi problem} In this section we exhibit a connection between the Tower of Hanoi problem, the automatic cube-free sequence $\{w_n\}$ and the transducer integer sequence $\{a_n\}$. Define a matrix $K_n$ of size $3^n \times n$, $n \geq 1$, with entries in $X_3$ by \[ K_1 = \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix}, \hspace{3cm} K_{n+1} = \begin{bmatrix} K_n & 0_n \\ K_n^R & 1_n \\ K_n & 2_n \end{bmatrix}, \] where the matrix $K_n^R$ is obtained from the matrix $K_n$ by flipping $K_n$ along the horizontal axis, and $0_n$, $1_n$ and $2_n$ are column vectors with $3^n$ entries equal to 0, 1 and 2, respectively. Denote the infinite limit matrix $\underset{n \to \infty}{\lim} K_n$ by $K$. For example, the transpose of $K_3$ is given by \[ K_3^T = \begin{bmatrix} 012 & 210 & 012 & 210 & 012 & 210 & 012 & 210 & 012 \\ 000 & 111 & 222 & 222 & 111 & 000 & 000 & 111 & 222 \\ 000 & 000 & 000 & 111 & 111 & 111 & 222 & 222 & 222 \end{bmatrix} \] The limiting matrix $K$ is well defined due to the fact that $K_n$ appears as the upper left corner in $K_{n+1}$. By definition, the indexing of the rows of $K$ starts with 0 while the indexing of the columns starts with 1. For future use, denote the $i$-th row of $K$ by $k_i$. We will think of $k_i$ as of a right infinite word over $X_3$. Similarly, denote the $i$-th row of the matrix $K_n$ by $k_i^{(n)}$. We will think of $k_i^{(n)}$ as a word of length $n$ over $X_3$. Note that, for $i \in \{0,\dots,3^n-1\}$, $k_i = k_i^{(n)}0^\infty$, $k_{i+2\cdot 3^n} = k_i^{(n)}20^\infty$, and $k_{i+3^n} = k_{3^n-1-i}^{(n)}10^\infty$ A sequence $w_0,\dots,w_{k^n-1}$ of words of length $n$ over $X_k$ is a $k$-ary Gray code of length $n$ if all words of length $n$ over $X_k$ appear exactly once in the sequence and any two consecutive words differ in exactly one position. Note that the $3^n$ rows of the matrix $K_n$ represent a ternary Gray code of length $n$. By interpreting the rows of $K$ as ternary representations of integers, we obtain the sequence \[ 0,1,2,5,4,3,6,7,8,17,16,15,12,13,14,11,10,9,\dots, \] which is not included in The On-Line Encyclopedia of Integer Sequences (as of December 2006). We observe that the successive rows in $K$ are obtained from each other by applying the ternary tree automorphism $a$ at odd steps and $c$ at even steps (the automorphisms $a$ and $c$ are defined by $\A_H$ - the transducer generating the Tower of Hanoigroup). \begin{proposition}\label{gray3} For $j \geq 0$, define $t_{2j} = (ca)^j$ and $t_{2j+1} = a(ca)^j$. Then \[ k_i = t_i(k_0). \] \end{proposition} \begin{proof} Recall that the result of the action of the rational ternary tree automorphism $a$ on any ternary word $w$ is that the first occurrence of a letter from $\{0,1\}$ in $w$, if such an occurrence exists, is replaced by the other letter from that set, while the result of the action of $c$ is that the first occurrence of a letter from $\{1,2\}$ in $w$, if such an occurrence exists, is replaced by the other letter from that set. As already observed, this implies that both $a$ and $c$ have order 2. Also, note that $a$ and $c$ change at most one letter in any word. We will prove by induction on $n$ that $k_i = t_i(k_0)$, for $0 \leq i \leq 3^n-1$. Since $a(0^\infty) = 10^\infty$ and $c(10^\infty) = 20^\infty$, the claim is true for $i \leq 2$. Assume that the claim is true for all $i \leq 3^n-1$, for some $n \geq 1$. Since the last row in $K_n$ is $2^n$, we see that $k_{3^n-1} = 2^n0^\infty$. This row is obtained from the previous row by applying $c$ in step $3^n-1$. In the next step applying $a$ to $2^n0^\infty$ produces $2^n10^\infty$, which is equal to $k_{3^n}$. We wish to understand the next $3^n-1$ steps, starting at the word $2^n10^\infty$, in which $c$ and $a$ are applied alternately. By inductive assumption, starting at $0^\infty$, alternate applications of $a$ and $c$ ($3^n-1$ total) change the word in the first $n$ positions from $0^n$ to $2^n$ by going through the $3^n$ words in the rows of $K_n$. Since both $c$ and $a$ are self-inverse, starting at $2^n10\infty$, alternate applications of $c$ and $a$ ($3^n-1$ total) backtrack the word in the first $n$ positions from $2^n$ back to $0^n$ by going through the $3^n$ words in the rows of $K_n^R$. Moreover, during this backtracking, no part of the word beyond the position $n$ is affected. This is simply because neither $c$ nor $a$ change more than 1 letter in any word. Thus, starting from $0^\infty$, alternate applications of $a$ and $c$ ($3^n-1+1+3^n-1=2\cdot 3^n-1$ total) produce the first $2 \cdot 3^n$ rows of $K$. The last taken step is $a$ and therefore, in the next step, $c$ takes $0^n10^\infty$ to $0^n20^\infty$. Alternate applications of $a$ and $c$ then again change the word in the first $n$ positions from $0^n$ to $2^n$ in $3^n-1$ steps by going through the $3^n$ words in the rows of $K_n$ without affecting any letter beyond position $n$ and eventually producing $2^{n+1}0^\infty$ in $2\cdot 3^n-1 + 1 + 3^n-1 = 3^{n+1}-1$ steps. \end{proof} It is clear that the rows of $K$ constitute the whole cofinal class of $0^\infty$. Thus the subgroup $\langle a, c\rangle$ acts transitively on this class. Since the order of both $a$ and $c$ is 2 this means that $\langle a,c\rangle$ is the infinite dihedral group $D_\infty$. The transitivity of the action of $\langle a,c\rangle$ on the cofinal class of $0^\infty$ is equivalent to the known fact that any valid $n$ disk configuration can be obtained from any other in a restricted version of Tower of Hanoi problem in which no disk can move between pegs 0 and 2 (in our terminology, applications of the automorphism $b$ are not allowed). Figure~\ref{peano} shows the path taken by $(ca)^{13}$ from $000$ to $222$ in $\Gamma_3$. \begin{figure}[!ht] \begin{center} \[ \SelectTips{cm}{} \xymatrix@C=3pt{ & & & & & & & 111 \\ & & & & & & 011 \ar@{-}[ur]^{\textstyle a} & & 211 \ar@{-}[ul]_{\textstyle c} \\ & & & & & 021 \ar@{-}[ur]^{\textstyle c} & & & & 201 \ar@{-}[ul]_{\textstyle a} \\ & & & & 221 \ar@{-}[rr]_{\textstyle c} & & 121 \ar@{-}[ul]_{\textstyle a} & & 101 \ar@{-}[rr]_{\textstyle a} \ar@{-}[ur]^{\textstyle c} & & 001 \\ & & & 220 \ar@{-}[ur]^{\textstyle a} & & & & & & & & 002 \ar@{-}[ul]_{\textstyle c} \\ & & 120 \ar@{-}[rr]_{\textstyle a} \ar@{-}[ur]^{\textstyle c} & & 020 & & & & & & 202 \ar@{-}[rr]_{\textstyle c} & & 102 \ar@{-}[ul]_{\textstyle a} \\ & 100 \ar@{-}[ld]_{\textstyle a} \ar@{-}[rd]^{\textstyle c} &&&& 010 \ar@{-}[rd]^{\textstyle a} \ar@{-}[ul]_{\textstyle c} &&&& 212 \ar@{-}[ld]_{\textstyle c} \ar@{-}[ur]^{\textstyle a} &&&& 122 \ar@{-}[ld]_{\textstyle a} \ar@{-}[rd]^{\textstyle c} \\ 000 && 200 \ar@{-}[rr]_{\textstyle a} && 210 \ar@{-}[rr]_{\textstyle c} && 110 && 112 \ar@{-}[rr]_{\textstyle a} && 012 \ar@{-}[rr]_{\textstyle c} && 022 && 222 } \] \caption{The ternary Gray code path generated by $a$ and $c$ in $\Ht$ at level 3}\label{peano} \end{center} \end{figure} Order all configurations (words in the cofinal class of $0^\infty$) according to their position in the matrix $K$ (small configurations correspond to rows with small index). When $b$ is applied to any configuration $k_i$ the obtained configuration $b(k_i)$ is either larger or smaller than $k_i$. Based on this alternative define an infinite sequence $\{d_i\}_{i=0}^\infty$ over $X=\{1,-1\}$ by \[ d_i = \begin{cases} 1, & \text{if } b(k_i) > k_i \\ -1, & \text{if } b(k_i) < k_i \end{cases}. \] Call this sequence the $b$-direction sequence. Further, define an integer sequence $\{\hat{b}_i\}_{i=0}^\infty$ by $\hat{b}_i = |i-j|/2$, where $j$ is the index of the configuration $k_j=b(k_i)$. Call this sequence the $b$-change sequence. \begin{theorem} The $b$-direction sequence is exactly the cube-free automatic sequence $\{w_n\}$ generated by $\A_{0-2}$ and the $b$-change sequence is exactly the transducer integer sequence $\{a_n\}$ generated by $\A_T$. \end{theorem} \begin{proof} The proof is by induction on blocks of size $3^n$. For $n=1$, the $b$-change sequence is $1,3,1$ which coincides with the transducer integer sequence generated by $\A_T$, while the $b$-direction sequence is $1,1,-1$, which coincides with the cube-free automatic sequence generated by $\A_{0-2}$. Assume that the $b$-change sequence $\{\hat{b}_i\}$ and the transducer integer sequence $\{a_i\}$ defined by $\A_T$ agree up to index $3^n-1$, and that the $b$-direction sequence $\{d_i\}$ and the automatic sequence $\{w_i\}$ defined by $\A_{0-2}$ agree up to index $3^n-1$, for some $n \geq 1$. Note that this implies that for $i \in \{0,\dots,3^n-1\}$, $i \neq (3^n-1)/2$, \[ \hat{b}_i = \hat{b}_{3^n-1-i} \qquad \text{and} \qquad d_i = - d_{3^n-1-i}. \] This is true simply because both claims are true for the transducer integer sequence $\{a_i\}$ and the automatic sequence $\{w_i\}$. Also, note that for the middle term in this block we have \[ \hat{b}_{(3^n-1)/2} = 3^n \qquad \text{and} \qquad d_{(3^n-1)/2} = 1. \] Let $i \in \{ 0,\dots,3^n-1 \}$, $i \neq (3^n-1)/2$. Note that the exception $i \neq (3^n-1)/2$ corresponds to $k_i^{(n)}=1^n$ (the middle row of $K_n$ consists entirely of $1$'s). Since either $0$ or $2$ appears in $k_i^{(n)}$ we know that the tree automorphism $b$ acts on any ternary word that has $k_i^{(n)}$ as a prefix by simply replacing the first occurrence of $0$ or $2$ in $k_i^{(n)}$ by the other letter and leaving everything else unchanged. Therefore, \[ b(k_{i+2\cdot3^n}) = b\left(k_{i}^{(n)}20^\infty\right) = k_{i+d_i \hat{b}_i}^{(n)}20^\infty = k_{i+d_i \hat{b}_i+2\cdot 3^n}. \] This implies that \[ \hat{b}_{i+2\cdot 3^n} = \hat{b}_i \qquad \text{and} \qquad d_{i+2\cdot 3^n} = d_i. \] Similarly, \[ b(k_{i+3^n}) = b\left(k_{3^n-1-i}^{(n)}10^\infty\right) = k_{3^n-1-i+d_{3^n-1-i} \hat{b}_{3^n-1-i}}^{(n)}10^\infty = k_{3^n-1-i -d_i \hat{b}_i}^{(n)}10^\infty = k_{i+d_i \hat{b}_i+3^n}, \] and this implies that \[ \hat{b}_{i + 3^n} = \hat{b}_i \qquad \text{and} \qquad d_{i + 3^n} = d_i. \] We now handle the exceptional terms (those are the ``middle'' terms, i.e., the terms corresponding to the indices $(3^n-1)/2 + 3^n$ and $(3^n-1)/2 + 2\cdot 3^n$). Since \[ b(k_{(3^n-1)/2 + 2\cdot 3^n}) = b(1^n20^\infty) = b(1^n00^\infty) = k_{(3^n-1)/2} \] we see that \[ \hat{b}_{(3^n-1)/2 + 2\cdot 3^n} = 3^n = \hat{b}_{(3^n-1)/2} \qquad \text{and} \qquad d_{(3^n-1)/2 + 2\cdot 3^n} = -1 = - d_{(3^n-1)/2}. \] Further, \[ b(k_{(3^n-1)/2 + 3^n}) = b(1^n10^\infty) = 1^{n+1}20^\infty = k_{(3^{n+1}-1)/2 + 2\cdot 3^{n+1}}, \] and therefore \[ \hat{b}_{(3^n-1)/2 + 3^n} = 3^{n+1} = 3 \cdot \hat{b}_{(3^n-1)/2} \qquad \text{and} \qquad d_{(3^n-1)/2 + 3^n} = 1 = d_{(3^n-1)/2}. \] Thus the block of length $3^{n+1}$ of the $b$-change sequence is obtained by repeating the block of length $3^n$ three times and then changing the middle term by multiplying it by 3. This is exactly how the block of length $3^{n+1}$ of the sequence $\{a_n\}$ is obtained from the block of length $3^n$. Similarly, the block of length $3^{n+1}$ of the $b$-direction sequence is obtained by repeating the block of length $3^n$ three times and then changing the middle term in the third sub-block of length $3^n$ from 1 to -1. This is exactly how the block of length $3^{n+1}$ of the sequence $\{w_n\}$ is obtained from the block of length $3^n$. This completes our induction step. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Geodesic configurations in the Tower of Hanoi problem} Define a matrix $M_n$ of size $2^n \times n$, $n \geq 1$, with entries in $X_2$ by \[ M_1 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}, \hspace{3cm} M_{n+1} = \begin{bmatrix} M_n & 0_n \\ M_n^R & 1_n \end{bmatrix}, \] where the matrix $M_n^R$ is obtained from the matrix $M_n$ by flipping $M_n$ along the horizontal axis, and $0_n$ and $1_n$ are column vectors with $2^n$ entries equal to 0 and 1, respectively. The $2^n$ rows of the matrix $M_n$ represent a binary Gray code of length $n$. Denote the infinite limit matrix $\underset{n \to \infty}{\lim} M_n$ by $M$. For future use, denote the $i$-th row of $M$ by $m_i$ and the $i$-th row of the matrix $M_n$ by $m_i^{(n)}$. We will think of $m_i$ as an infinite word and of $m_i^{(n)}$ as a word of length $n$ over $X_2$. Note that, for $i \in \{0,\dots,2^n-1\}$, $m_i = m_i^{(n)}0^\infty$, $m_{i+ 2^n} = m_{2^n-1-i}^{(n)}10^\infty$. We observe that the successive rows in $M$ are obtained from each other by applying the binary tree automorphism $f$ at odd steps and the automorphism $g$ at even steps, where $f$ and $g$ are given by the invertible transducer $\A_D$ given in Figure~\ref{ad}. The self-similar group $G(\A_D)$ defined by $\A_D$ and generated by $f$ and $g$ is the infinite dihedral group $D_\infty$. \begin{figure}[!ht] \begin{center} \begin{tabular}{ccc} $ \SelectTips{cm}{} \xymatrix@C=35pt{ \A_D: & *++[o][F-]{{\scriptstyle()}}\ar@(ul,l)_{0,1}\ar@{}[r]|<<<{id} & *++[o][F-]{{\scriptstyle(01)}}\ar@/^1pc/[l]^{0}\ar@/_1pc/[l]_{1}\ar@{}[l]|<<{f} & *++[o][F-]{{\scriptstyle()}} \ar@{->}[l]^{1}\ar@(ur,r)^{0}\ar@{}[l]_<<{g} } $ && $ \SelectTips{cm}{} \xymatrix@C=35pt{ \A_{L_2}: & *++[o][F-]{{\scriptstyle()}}\ar@(ul,l)_{0} \ar@/_1pc/[r]_{1} \ar@{}[r]|<<<{\lambda_0} & *++[o][F-]{{\scriptstyle(01)}} \ar@(ur,r)^{1} \ar@/_1pc/[l]_{0} \ar@{}[l]|<<{\lambda_1} } $ \end{tabular} \caption{Two binary invertible transducers: $\A_D$ and $\A_{L_2}$}\label{ad} \end{center} \end{figure} \begin{proposition} For $j \geq 0$, define $s_{2j} = (gf)^j$ and $s_{2j+1} = f(gf)^j$. Then \[ m_i = s_i(m_0). \] \end{proposition} Note that the previous result is just a binary analogue of Proposition~\ref{gray3} and can also be proved by a simple inductive argument. Consider now the transducer in the right half of Figure~\ref{at}. It is known~\cite{grigorchuk-z:l2} (see also~\cite{silva-s:lamplighter,bartholdi-s:bs}) that the group $G(\A_{L_2})$ is the lamplighter group $L_2$ which is the wreath product of the cyclic group of order 2 (representing a switch) and the infinite cyclic group (representing moves between consecutive lamps). The realization of the lamplighter group $L_2$ by the transducer $\A_{L_2}$ was used by Grigorchuk and \.Zuk~\cite{grigorchuk-z:l2} to calculate the spectrum of the Markov operator on the Cayley graph of $L_2$, which then lead to the solution of Strong Atiyah Conjecture in~\cite{grigorchuk-al:atiyah}. For $i \geq 0$, denote by $\langle i \rangle_2^{(n)}$ the length $n$ binary representative (including leading zeros if necessary) in which the most significant digits are written first. Define, for $i \in \{0,\dots,2^n-1\}$, $\overline{m}_i^{(n)}$ to be the reversal of the word $m_i^{(n)}$ (more generally, denote by $\overline{w}$ the reversal of any word $w$). \begin{proposition} For $i = 0,\dots,2^n-1$, \[ \lambda_0\left(\langle i \rangle_2^{(n)}\right) = \overline{m}_i^{(n)}. \] \end{proposition} \begin{proof} We prove, by induction on $n$, that \[ \lambda_0\left(\langle i \rangle_2^{(n)}\right) = \overline{m}_i^{(n)} \qquad\text{and}\qquad \lambda_1\left(\langle i \rangle_2^{(n)}\right) = \overline{m}_{2^n-1-i}^{(n)}, \] for $0 \leq i \leq 2^n-1$. The claim is correct for $n=1$, since $\lambda_0(0)=0=\overline{m}_0^{(1)}$, $\lambda_0(1)=1=\overline{m}_1^{(1)}$, $\lambda_1(0)=1=\overline{m}_1^{(1)}$, and $\lambda_1(1)=0=\overline{m}_0^{(1)}$. Assume that the claim is correct for some $n \geq 1$. Then, for $0 \leq i \leq 2^n-1$, \begin{align*} \lambda_0\left(\langle i \rangle_2^{(n+1)}\right) &= \lambda_0\left(0\langle i \rangle_2^{(n)}\right) = 0 \lambda_0\left(\langle i \rangle_2^{(n)}\right) = 0 \overline{m}_i^{(n)} = \overline{m_i^{(n)}0} = \overline{m}_i^{(n+1)}, \\ \lambda_1\left(\langle i \rangle_2^{(n+1)}\right) &= \lambda_1\left(0\langle i \rangle_2^{(n)}\right) = 1 \lambda_0\left(\langle i \rangle_2^{(n)}\right) = 1 \overline{m}_i^{(n)} = \overline{m_i^{(n)}1} = \overline{m}_{2^{n+1}-1-i}^{(n+1)}, \end{align*} while for $2^n \leq i \leq 2^{n+1}-1$, \begin{align*} \lambda_0\left(\langle i \rangle_2^{(n+1)}\right) &= \lambda_0\left(1\langle i-2^n \rangle_2^{(n)}\right) = 1 \lambda_1\left(\langle i-2^n \rangle_2^{(n)}\right) = \\ &= 1 \overline{m}_{2^{n+1}-1-i}^{(n)} = \overline{m_{2^{n+1}-1-i}^{(n)}1} = \overline{m}_i^{(n+1)}, \\ \lambda_1\left(\langle i \rangle_2^{(n+1)}\right) &= \lambda_1\left(1\langle i-2^n \rangle_2^{(n)}\right) = 0 \lambda_1\left(\langle i-2^n \rangle_2^{(n)}\right) = \\ &= 0 \overline{m}_{2^{n+1}-1-i}^{(n)} = \overline{m_{2^{n+1}-1-i}^{(n)}0} = \overline{m}_{2^{n+1}-1-i}^{(n+1)}. \qedhere \end{align*} \end{proof} We can define a variation on the notion of transducer integer sequences as sequences that can be obtained from transducers by reading the input starting from the most significant digit (and interpreting the output as starting from the most significant digit). Call these sequences SF transducer integer sequences (for significant first). Since the sequence of binary Gray code words can be obtained by feeding the binary representations of integers, most significant digit first, into $\A_{L_2}$ starting at $\lambda_0$, we see that the sequence \seqnum{A003188} of integers \[ 0 , 1, 3, 2, 6, 7, 5, 4, \dots \] represented by the binary Gray code words is a SF binary transducer integer sequence. We offer two 2 to 3 transducers each of which generates all the configurations on the three geodesic paths between the three regular configurations $0^n$, $1^n$ and $2^n$ in the Schreier graph $\Gamma_n$ modeling the Tower of Hanoi problem on 3 pegs and $n$ disks (a geodesic path between two vertices is a path of shortest possible length connecting the vertices). Call such configurations \emph{geodesic configurations}. The first transducer (see Theorem~\ref{oh}) uses the natural order, while the second one (see Theorem~\ref{oh'}) uses the order implied by the binary Gray code. \begin{theorem}\label{oh} The 2 to 3 transducer $\mathcal{O}_H$ in Figure~\ref{geodesic} generates the geodesic configurations in the Tower of Hanoi problem. More precisely, for $x,y \in\{0,1,2\}$, $x \neq y$, starting at state $q_{xy}$, and feeding the length $n$ binary representative $\langle i \rangle_2^{(n)}$ of $i$ (including leading 0's if needed) into $\mathcal{O}_H$ produces the reverse of the length $n$ ternary word representing the unique $n$ disk configuration at distance $i$ along the geodesic from $x^n$ to $y^n$ in the $n$-th level Schreier graph $\Gamma_n$ of Tower of Hanoi group $\Ht$. \end{theorem} \begin{figure}[!ht] \[ \SelectTips{cm}{} \xymatrix@C=30pt@R=55pt{ {\mathcal{O}_H:} & *++[o][F-]{} \ar@/^1pc/[rr]^{0/0} \ar@{}[ddrr]|<<<<<{\textstyle q_{01}} \ar@/^1pc/[dl]^{1/1} && *++[o][F-]{} \ar@/^1pc/[dr]^{1/2} \ar@{}[ddll]|<<<<<{\textstyle q_{02}} \ar@/^1pc/[ll]^{0/0} & \\ *++[o][F-]{} \ar@/^1pc/[ur]^{1/1} \ar@{}[r]|<<<<<<{\textstyle q_{21}} \ar@/^1pc/[dr]^{0/2} &&&& *++[o][F-]{} \ar@/^1pc/[dl]^{0/1} \ar@{}[l]|<<<<<{\textstyle q_{12}} \ar@/^1pc/[ul]^{1/2} \\ & *++[o][F-]{} \ar@/^1pc/[ul]^{0/2} \ar@{}[uurr]|<<<<<{\textstyle q_{20}} \ar@/^1pc/[rr]^{1/0} && *++[o][F-]{} \ar@/^1pc/[ll]^{1/0} \ar@{}[uull]|<<<<<{\textstyle q_{10}} \ar@/^1pc/[ur]^{0/1} & } \] \caption{A 2 to 3 transducer generating geodesic configurations}\label{geodesic} \end{figure} \begin{proof} For any permutation $x,y,z$ of the three letters in $X_3$ the states of the transducer $\mathcal{O}_H$ have (as tree morphisms) the decomposition \[ q_{xy} = \pi_{xy} (q_{xz},q_{zy}), \] where $\pi_{xy}:X_2 \to X_3$ is the map defined by $\pi_{xy}(0)=x$ and $\pi_{xy}(1)=y$. It is well known that the unique way to solve the Tower of Hanoi problem in which $n$, $n \geq 1$, disks are moved from peg $x$ to peg $y$ in $2^n-1$ steps can be recursively described as follows. First, in $2^{n-1}-1$ steps move the top $n-1$ disks from peg $x$ to peg $z$ (the third available peg). Then, in step number $2^{n-1}$, move the largest disk from peg $x$ to peg $y$. Then, in $2^{n-1}-1$ steps, move the $n-1$ smallest disks from peg $z$ to peg $y$. Observe that the largest disk is moved only once, in the middle step (step number $2^{n-1}$). Employing the encoding of configurations by words over $X_3$, we see that the unique geodesic path of length $2^n-1$ from $x^n$ to $y^n$ connects $x^n$ to $z^{n-1}x$ in the first $2^{n-1}-1$ steps, then in the next step it connects $z^{n-1}x$ to $z^{n-1}y$, and in the last $2^{n-1}-1$ steps it connects $z^{n-1}y$ to $y^n$. Since the largest disk is moved only once, the last digit in the configurations on the geodesic from $x^n$ to $y^n$ is equal to $x$ in the first $2^{n-1}$ configurations along the way, and it is equal to $y$ in the last $2^{n-1}$ configurations. Thus, if we denote by $\xi_{xy}^{(n)}(i)$ the reversal of the word over $X_3$ representing the vertex at distance $i$ from $x^n$ along the geodesic between $x^n$ and $y^n$ in $\Gamma_n$, we have, for $n \geq 2$, \[ \xi_{xy}^{(n)}(i) = \begin{cases} x\xi_{xz}^{(n-1)}(i), & 0 \leq i \leq 2^{n-1}-1 \\ y\xi_{zy}^{(n-1)}(i-2^{n-1}), & 2^{n-1} \leq i \leq 2^n-1 \\ \end{cases}. \] We can now easily prove that \[ q_{xy}\left(\langle i \rangle_2^{(n)}\right) = \xi_{xy}^{(n)}(i), \] by using induction on $n$. Since $q_{xy}(0) = \pi_{xy}(0) = x = \xi_{xy}^{(1)}(0)$ and $q_{xy}(1) = \pi_{xy}(1) = y = \xi_{xy}^{(1)}(1)$, the claim is true for $n=1$. Assume that the claim is true for all integers smaller than some $n$, $n \geq 2$. Then, for $0 \leq i \leq 2^{n-1}-1$, \[ q_{xy}\left(\langle i \rangle_2^{(n)}\right) = q_{xy}\left(0 \langle i \rangle_2^{(n-1)}\right) = \pi_{xy}(0)q_{xz}\left(\langle i \rangle_2^{(n-1)}\right) = x\xi_{xz}^{(n-1)}(i) = \xi_{xy}^{(n)}(i) \] and, for $0 \leq i \leq 2^{n-1}-1$, \begin{multline*} q_{xy}\left(\langle i \rangle_2^{(n)}\right) = q_{xy}\left(1 \langle i-2^{n-1} \rangle_2^{(n-1)}\right) = \\ = \pi_{xy}(1)q_{zy}\left(\langle i-2^{n-1} \rangle_2^{(n-1)}\right) = y\xi_{zy}^{(n-1)}(i-2^{n-1}) = \xi_{xy}^{(n)}(i). \qedhere \end{multline*} \end{proof} \begin{theorem}\label{oh'} The 2 to 3 transducer $\mathcal{O}_H'$ in Figure~\ref{geodesic2} generates the geodesic configurations in the Tower of Hanoi problem. More precisely, for $x,y \in\{0,1,2\}$, $x \neq y$, starting at state $t_{xy}$, and feeding the reversal $\overline{m}_i^{(n)}$ of the length $n$ row $i$ binary Gray code word from $M_n$ into $\mathcal{O}_H'$ produces the reverse of the length $n$ ternary word representing the unique $n$ disk configuration at distance $i$ along the geodesic from $x^n$ to $y^n$ in the $n$-th level Schreier graph $\Gamma_n$ of the Tower of Hanoi group $\Ht$. \end{theorem} \begin{figure}[!ht] \[ \SelectTips{cm}{} \xymatrix@C=75pt@R=55pt{ {\mathcal{O}_H':}& *++[o][F-]{} \ar@/_1pc/[r]^{1/1} \ar@/^1pc/[d]^{0/0} \ar@{}[l]|<<<<{\textstyle t_{01}} & *++[o][F-]{} \ar@/_1pc/[r]^{1/2} \ar@/^1pc/[d]^{0/1} \ar@{}[l]_<<<{\textstyle t_{12}} & *++[o][F-]{} \ar@/_2pc/[ll]_{1/0} \ar@/^1pc/[d]^{0/2} \ar@{}[r]|<<<<{\textstyle t_{20}} & \\ & *++[o][F-]{} \ar@/_2pc/[rr]_{1/2} \ar@/^1pc/[u]^{0/0} \ar@{}[l]|<<<<{\textstyle t_{02}} & *++[o][F-]{} \ar@/_1pc/[l]^{1/0} \ar@/^1pc/[u]^{0/1} \ar@{}[l]^<<<{\textstyle t_{10}} & *++[o][F-]{} \ar@/_1pc/[l]^{1/1} \ar@/^1pc/[u]^{0/2} \ar@{}[r]|<<<<{\textstyle t_{21}} & } \] \caption{A 2 to 3 transducer generating geodesic configurations}\label{geodesic2} \end{figure} \begin{proof} Observe that, for any permutation $x,y,z$ of the three letters in $X_3$ the states of the transducer $\mathcal{O}_H'$ have (as tree morphisms) the decomposition \[ t_{xy} = \pi_{xy} (t_{xz},t_{yz}), \] where $\pi_{xy}:X_2 \to X_3$ is the map defined by $\pi_{xy}(0)=x$ and $\pi_{xy}(1)=y$. If we preserve the notation from the proof of Theorem~\ref{oh}, we have, for $n \geq 2$, \[ \xi_{xy}^{(n)}(i) = \begin{cases} x\xi_{xz}^{(n-1)}(i), & 0 \leq i \leq 2^{n-1}-1 \\ y\xi_{yz}^{(n-1)}(2^n-1-i), & 2^{n-1} \leq i \leq 2^n-1 \\ \end{cases}. \] The reason that this formula is correct for $2^{n-1} \leq i \leq 2^n-1$ is simply that vertices that are distance $i$ from $x^n$ along the geodesic between $x^n$ and $y^n$ are distance $2^n-1-i$ from $y^n$. One can then use induction on $n$ just as in the proof of Theorem~\ref{oh}. The only small difference is in the inductive step for $0 \leq i \leq 2^{n-1}-1$, which now reads \begin{multline*} t_{xy}\left(\overline{m}_i^{(n)}\right) = t_{xy}\left(\overline{m_{2^{n-1}-1-i}^{(n-1)}1}\right) = t_{xy}\left(1 \overline{m}_{2^{n-1}-1-i}^{(n-1)}\right) = \\ = \pi_{xy}(1)t_{yz}\left( \overline{m}_{2^{n-1}-1-i}^{(n-1)} \right) = y\xi_{yz}^{(n-1)}(2^{n-1}-1-i) = \xi_{xy}^{(n)}(i). \qedhere \end{multline*} \end{proof} Observe that the $X_2^* \to X_3^*$ tree morphism defined by the state $q_{xy}$ in the transducer $\mathcal{O}_H$ is just the composition of the binary tree automorphism $X_2^* \to X_2^*$ defined by the state $\lambda_0$ with the $X_2^* \to X_3^*$ tree morphism defined by the state $t_{xy}$ in the transducer $\mathcal{O}_H'$ (recall that $\lambda_0$ translates from reversals of binary representations to reversals of Gray code words and the state $t_{xy}$ in $\mathcal{O}'_H$ translates from reversals of Gray code words to reversals of geodesic configurations between $x^n$ and $y^n$). This observation could be used to prove only one of the two theorems above and then claim the result in the other as a simple corollary. The transducer $\mathcal{O}_H$, started at $q_{01}$, generates the sequence \seqnum{A055661} \[ 0,1,7,8,17,15,12,13,\dots, \] but only when all input words are adjusted by leading zeros to have odd length, and it gives the sequence \[ 0,2,5,4,22,21,24,26,\dots, \] which does not appear in The On-Line Encyclopedia of Integer Sequences (as of December 2006), when the input words are adjusted to have even length. In fact, the former sequence records the integers whose ternary representations give the configurations in the Tower of Hanoi problem on the geodesic line in the infinite Schreier graph $\Gamma_{0^\infty}$ (recall the definition of the limiting graph $\Gamma_{0^\infty}$ in Section~\ref{s:tree}) determined by applying repeatedly the automorphisms $a$, $b$ and $c$ (in that order) and the latter records the integers whose ternary representations give the configurations on the geodesic line in $\Gamma_{0^\infty}$ determined by applying repeatedly the automorphisms $b$, $a$ and $c$ (in that order). There is nothing strange in this split, since it is known that the optimal solution transferring disks from peg 0 to peg 1 follows different paths depending on the parity of the number of disks. Namely, for odd number of disks, the optimal way to transfer the disks from peg 0 to peg 1 is to apply repeatedly the ternary tree automorphisms $a$, $b$ and $c$ (in that order), and for even number of disks, the optimal way is to apply repeatedly the ternary tree automorphisms $b$, $a$ and $c$ (in that order). By flipping the input and the output symbol in the transducers $\mathcal{O}_H$ and $\mathcal{O}_H'$ we obtain the partial inverse transducers $\mathcal{O}_H^{-1}$ and $\mathcal{O}_H'^{-1}$ that can be used to recognize the geodesic configurations in the Tower of Hanoi problem and encode them either by using binary representations or by Gray code words. \begin{corollary} The 3 to 2 transducer $\mathcal{O}_H^{-1}$ in Figure~\ref{geodesic-inv} obtained by inversion from the 2 to 3 transducer $\mathcal{O}_H$, recognizes the geodesic configurations in the Tower of Hanoi problem. More precisely, starting at the inverse state $q_{xy}^{-1}$, $x,y\in X_3$, $x \neq y$, and feeding ternary words of length $n$ into the inverse transducer $\mathcal{O}_H'^{-1}$, only reversals of ternary words representing the configurations on the geodesic from $x^n$ to $y^n$ in $\Gamma_n$ are read entirely by the transducer and, for such configurations, the output represents reversals of the binary representation of the distance to $x^n$. \end{corollary} \begin{corollary} The 3 to 2 transducer $\mathcal{O}_H'^{-1}$ obtained by inversion from the 2 to 3 transducer $\mathcal{O}_H'$, recognizes the geodesic configurations in the Tower of Hanoi problem. More precisely, starting at the inverse state $t_{xy}^{-1}$, $x,y\in X_3$, $x \neq y$, and feeding ternary words of length $n$ into the inverse transducer $\mathcal{O}_H^{-1}$, only reversals of ternary words representing configurations on the geodesic from $x^n$ to $y^n$ in $\Gamma_n$ are read entirely by the transducer and, for such configurations, the reversal of the corresponding binary Gray code word of length $n$ is produced in the output. \end{corollary} \begin{figure}[!ht] \[ \SelectTips{cm}{} \xymatrix@C=30pt@R=55pt{ {\mathcal{O}_H^{-1}:} & *++[o][F-]{} \ar@/^1pc/[rr]^{0/0} \ar@{}[ddrr]|<<<<<<{\textstyle q_{01}^{-1}} \ar@/^1pc/[dl]^{1/1} && *++[o][F-]{} \ar@/^1pc/[dr]^{2/1} \ar@{}[ddll]|<<<<<<{\textstyle q_{02}^{-1}} \ar@/^1pc/[ll]^{0/0} & \\ *++[o][F-]{} \ar@/^1pc/[ur]^{1/1} \ar@{}[r]|<<<<<<<{\textstyle q_{21}^{-1}} \ar@/^1pc/[dr]^{2/0} &&&& *++[o][F-]{} \ar@/^1pc/[dl]^{1/0} \ar@{}[l]|<<<<<<{\textstyle q_{12}^{-1}} \ar@/^1pc/[ul]^{2/1} \\ & *++[o][F-]{} \ar@/^1pc/[ul]^{2/0} \ar@{}[uurr]|<<<<<<{\textstyle q_{20}^{-1}} \ar@/^1pc/[rr]^{0/1} && *++[o][F-]{} \ar@/^1pc/[ll]^{0/1} \ar@{}[uull]|<<<<<<{\textstyle q_{10}^{-1}} \ar@/^1pc/[ur]^{1/0} & } \] \caption{A 3 to 2 transducer recognizing geodesic configurations}\label{geodesic-inv} \end{figure} For example, the configuration $10021$ is not a geodesic configuration between $00000$ and $11111$. This follows from the fact that the reversal word $12001$ is not accepted by $\mathcal{O}_H^{-1}$ starting from the state $q_{01}^{-1}$ (the reading stops in state $q_{20}^{-1}$ after reading the first 4 symbols and the transducer cannot read the last symbol). On the other hand, starting from the state $q_{01}^{-1}$ the word $12002$ is read completely and it produces the output $10110$, which says that the configuration $20021$ is on the geodesic between $00000$ and $11111$ and its distance to $00000$ is $2^4+2^2+2^1=22$. If we read $12002$ starting from state $q_{10}^{-1}$ we obtain the output $01001$, which confirms that the configuration $20021$ is on the geodesic between $11111$ and $00000$ and that its distance to $11111$ is $2^3+2^0=9$ (note that $22+9=31=2^5-1$, which is the distance between $00000$ and $11111$). \section{Acknowledgements} I would like to thank the referee for the extremely careful reading of the manuscript and her/his numerous helpful remarks. \def\cprime{$'$} \begin{thebibliography}{10} \bibitem{allouche-b-s:hanoi} J.-P.~Allouche, J.~B{\'e}tr{\'e}ma, and J.~O.~Shallit, \newblock Sur des points fixes de morphismes d'un mono\"\i de libre, \newblock {\em RAIRO Inform. Th\'eor. Appl.} {\bf 23} (1989), 235--249. \bibitem{allouche-s:as} J.-P.~Allouche and J.~Shallit, \newblock {\em Automatic sequences}, \newblock Cambridge University Press, 2003. \bibitem{bartholdi-g-n:fractal} L.~Bartholdi, R.~Grigorchuk, and V.~Nekrashevych, \newblock From fractal groups to fractal sets, \newblock In {\em Fractals in Graz 2001}, Trends Math., Birkh\"auser, 2003, pp.\ 25--118. \bibitem{bartholdi-g-s:branch} L.~Bartholdi, R.~I.~Grigorchuk, and Z.~{\v{S}}uni{\'k}, \newblock Branch groups, \newblock In {\em Handbook of algebra} Vol. {\bf 3}, North-Holland, 2003, pp.\ 989--1112. \bibitem{bartholdi-n:rabbit} L.~Bartholdi and V.~Nekrashevych, \newblock Thurston equivalence of topological polynomials, \newblock {\em Acta Math.} {\bf 197} (2006), 1--51. \bibitem{bartholdi-s:bs} L.~Bartholdi and Z.~{\v{S}}uni{\'k}, \newblock Some solvable automaton groups, \newblock In {\em Topological and asymptotic aspects of group theory}, Vol.\ {\bf 394} of {\em Contemp. Math.}, Amer. Math. Soc., 2006, pp.\ pp.\ 11--29. \bibitem{bartholdi-v:basilica} L.~Bartholdi and B.~Vir{\'a}g, \newblock Amenability via random walks, \newblock {\em Duke Math. J.} {\bf 130} (2005), 39--56. \bibitem{cobham:tags} A.~Cobham, \newblock Uniform tag sequences, \newblock {\em Math. Systems Theory} {\bf 6} (1972), 164--192. \bibitem{grigorchuk:burnside} R.~I.~Grigorchuk, \newblock On {B}urnside's problem on periodic groups, \newblock {\em Funktsional. Anal. i Prilozhen.} {\bf 14} (1980), 53--54. \bibitem{grigorchuk-n-s:automata} R.~I.~Grigorchuk, V.~V.~Nekrashevich, and V.~I.~Sushchanski{\u\i}, \newblock Automata, dynamical systems, and groups, \newblock {\em Tr. Mat. Inst. Steklova} {\bf 231} (2000), 134--214. \bibitem{grigorchuk-n-s:oberwolfach2} R.~Grigorchuk, V.~Nekrashevych, and Z.~{\v S}uni\'c, \newblock Hanoi towers group on 3 pegs and its pro-finite closure, \newblock {\em Oberwolfach Reports} {\bf 25} (2006), 15--17. \bibitem{grigorchuk-n-s:oberwolfach1} R.~Grigorchuk, V.~Nekrashevych, and Z.~{\v S}uni\'c, \newblock Hanoi towers groups, \newblock {\em Oberwolfach Reports} {\bf 19} (2006), 11--14. \bibitem{grigorchuk-s:standrews} R.~Grigorchuk and Z.~{\v S}uni{\'c}, \newblock Self-similarity and branching in group theory. \newblock In {\em Groups St. Andrews 2005, I}, Vol.\ {\bf 339} of {\em London Math. Soc. Lecture Note Ser.}, Cambridge Univ. Press, 2007, pp.\ 36--95. \bibitem{grigorchuk-s:hanoi-cr} R.~Grigorchuk and Z.~{\v{S}}uni{\'k}, \newblock Asymptotic aspects of {S}chreier graphs and {H}anoi {T}owers groups, \newblock {\em C. R. Math. Acad. Sci. Paris} {\bf 342}, (2006), 545--550. \bibitem{grigorchuk-al:atiyah} R.~I.~Grigorchuk, P.~Linnell, T.~Schick, and A.~{\.Z}uk, \newblock On a question of {A}tiyah, \newblock {\em C. R. Acad. Sci. Paris S\'er. I Math.} {\bf 331} (2000), 663--668. \bibitem{grigorchuk-z:cortona} R.~I.~Grigorchuk and A.~{\.Z}uk, \newblock On the asymptotic spectrum of random walks on infinite families of graphs, \newblock In {\em Random walks and discrete potential theory (Cortona, 1997)}, Sympos. Math., {\bf 39}, Cambridge Univ. Press, 1999, pp.\ 188--204. \bibitem{grigorchuk-z:l2} R.~I.~Grigorchuk and A.~{\.Z}uk, \newblock The lamplighter group as a group generated by a 2-state automaton, and its spectrum, \newblock {\em Geom. Dedicata} {\bf 87} (2001), 209--244. \bibitem{grigorchuk-z:basilica1} R.~I.~Grigorchuk and A.~{\.Z}uk, \newblock On a torsion-free weakly branch group defined by a three state automaton, \newblock {\em Internat. J. Algebra Comput.} {\bf 12} (2002), 223--246. \bibitem{hinz:ens} A.~M.~Hinz, \newblock The {T}ower of {H}anoi, \newblock {\em Enseign. Math. (2)} {\bf 35} (1989), 289--321. \bibitem{nekrashevych:b-selfsimilar} V.~Nekrashevych. \newblock {\em Self-similar {G}roups}, Vol.\ {\bf 117} of {\em Mathematical Surveys and Monographs}. \newblock Amer. Math. Soc., 2005. \bibitem{richomme-w:cube-free} G.~Richomme and F.~Wlazinski, \newblock Some results on {$k$}-power-free morphisms, \newblock {\em Theoret. Comput. Sci.} {\bf 273} (2002), 119--142. \bibitem{sidki:circuit} S.~Sidki, \newblock Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity, \newblock {\em J. Math. Sci. (New York)} {\bf 100} (2000), 1925--1943. \bibitem{silva-s:lamplighter} P.~V.~Silva and B.~Steinberg, \newblock On a class of automata groups generalizing lamplighter groups, \newblock {\em Internat. J. Algebra Comput.} {\bf 15} (2005), 1213--1234. \bibitem{sloane:online} N.~J.~A.~Sloane, The on-line encyclopedia of integer sequences. \newblock \href{http://www.research.att.com/\~njas/sequences/}{\tt {http://www.research.att.com/\~{}njas/sequences/}}. \bibitem{wilson:nonuniform} J.~S.~Wilson, \newblock On exponential growth and uniformly exponential growth for groups, \newblock {\em Invent. Math.} {\bf 155} (2004), 287--303. \end{thebibliography} \newpage \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 11Y55; Secondary 11B85, 20M20, 20M35. \\ \noindent {\it Keywords}: transducers, integer sequences, automatic sequences, self-similar groups, self-similar semigroups, Tower of Hanoi problem. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A003188}, \seqnum{A005836}, \seqnum{A038500}, \seqnum{A055661}, \seqnum{A057427}, \seqnum{A060236}, \seqnum{A060372}, \seqnum{A060373}, \seqnum{A060374}, and \seqnum{A080846}.) \bigskip \hrule \bigskip \noindent Received December 4, 2006; revised version received April 10 2007. Published in {\it Journal of Integer Sequences}, April 13 2007. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}