\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{pst-node} \usepackage{pst-tree} \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} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \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}}} \newtheorem{define}{Definition} \newtheorem{lem}{Lemma} \newtheorem{cor}{Corollary} \newtheorem{theorem}{Theorem} \newtheorem{thm}{Theorem} \newtheorem{rem}{Remark} \newtheorem{obs}{Observation} \newtheorem{note}{Note} \theoremstyle{definition} \newtheorem{example}{Example} \def\ra{\rightarrow} \def\lra{\longrightarrow} \def\R{{\mathbb{R}}} \def\N{{\mathbb{N}}} \def\Z{{\mathbb{Z}}} \def\Q{{\mathbb{Q}}} \def\C{{\mathbb{C}}} \def\F{{\mathbb{F}}} \def\oH{\buildrel\circ\over H} \def\oH1{\buildrel\circ\over H\kern-.02in{}^1} \def\qed{{\hfill $\Box$}} \def\l{\ell} \def\dotf{\dot{f}} \def\tildeR{\widetilde R} \def\ind{\hbox{ind}} \def\cop{\bot\hskip-.075in\bot} \def\bysame{\rule{.5in}{.005in},\ } \def\Im{\hbox{\,Im\,}} \def\supp{\hbox{\,supp\,}} \def\const{\hbox{\,const\,}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Affinely Self-Generating Sets and Morphisms} \vskip 1cm \large David Garth and Adam Gouge \\ Division of Mathematics and Computer Science \\ Truman State University \\ Kirksville, MO 63501 \\ USA\\ \href{mailto:dgarth@truman.edu}{\tt dgarth@truman.edu}\\ \href{mailto:acg938@truman.edu}{\tt acg938@truman.edu}\\ \end{center} \begin{abstract} Kimberling defined a self-generating set $S$ of integers as follows. Assume 1 is a member of $S$, and if $x$ is in $S$, then $2x$ and $4x-1$ are also in $S$. We study similar self-generating sets of integers whose generating functions come from a class of affine functions for which the coefficients of $x$ are powers of a fixed base. We prove that for any positive integer $m$, the resulting sequence, reduced modulo $m$, is the image of an infinite word that is the fixed point of a morphism over a finite alphabet. We also prove that the resulting characteristic sequence of $S$ is the image of the fixed point of a morphism of constant length, and is therefore automatic. We then give several examples of self-generating sets whose expansions in a certain base are characterized by sequences of integers with missing blocks of digits. This expands upon earlier work by Allouche, Shallit, and Skordev. Finally, we give another possible generalization of the original set of Kimberling. \end{abstract} \section{Introduction} \label{intro} Kimberling \cite{kimberling1} defined a self-generating set $S$ as follows. \begin{enumerate} \item 1 belongs to $S$; \item if $x$ belongs to $S$, then $2x$ and $4x-1$ belong to $S$; and \item nothing else belongs to $S$. \end{enumerate} Writing the integers in $S$ in increasing order gives the sequence $$1,~2,~3,~4,~6,~7,~8,~11,~12,~14,~15,~16,~22,~23,~24,~27,~28,~30,~31,~32,\ldots,$$ which is Sloane's {\tt A052499} \cite{encyclopedia}. Reducing the sequence modulo 2, we obtain $$1,~0,~1,~0,~0,~1,~0,~1,~0,~0,~1,~0,~0,~1,~0,~1,~0,~0,~1,~0,\ldots$$ Kimberling found that this last sequence, starting at the second term, is the well-known Fibonacci word. Recall that the Fibonacci word can be obtained as the fixed point of the morphism $0\rightarrow 01$, $1\rightarrow 0$. The paper by Kimberling also noted that the sequence $R(n)$ of ranks past 1 of the even terms of $S$ is $$R(n)=1,~3,~4,~6,~8,~9,~11,~\ldots,$$ which is sequence {\tt A000201} \cite{encyclopedia}. Allouche, Shallit, and Skordev \cite{shallit} made some additional interesting observations about $S$. In particular, they showed that the set $T:=S-1$, the set obtained from $S$ by subtracting 1 from all the elements of $S$, is also self-generating as follows: \begin{enumerate} \item 0 belongs to $T$ \item If $x$ belongs to $T$ then $2x+1$ and $4x+2$ belong to $T$ \item Nothing else belongs to $T$. \end{enumerate} In addition, they showed that $T$ is the set of integers whose base 2 representation does not contain the block $00$. These binary expansions correspond to the lazy Fibonacci expansions of the set of natural numbers. Kimberling \cite{kimberling2} generalized the notion of self-generating sets of integers in the following way. Let $F$ be a countable set of affine functions with integer coefficients. Let $S_F$ be the set of numbers satisfying the conditions that $1\in S_{F}$, and if $x\in S_{F}$ and $f\in F$, then $f(x)\in S_F$. Kimberling's paper contained several examples. The paper by Allouche, Shallit, and Skordev \cite{shallit} cited some of these examples in connection with sequences of integers with missing blocks. For most of these examples they showed that the characteristic sequence of $S_F$ is 2-automatic. They then asked, ``How far can the sequence proposed by Kimberling be generalized?'' In particular they asked, ``Under which conditions is the corresponding characteristic sequence automatic?'' We address these questions for a general class of affine functions. For the remainder of this paper, let $F$ be the family of functions defined as follows. Let $v$ and $a$ be positive integers, let $\ell_i$ be integers satisfying $$1=\ell_0\leq \ell_1\leq\ell_2\leq\cdots\leq\ell_{v}$$ and let $b_i$ be integers satisfying $$b_0=0,~~\mbox{and}~~0\leq b_i\leq a^{\ell_i}-1~~\mbox{for}~~1\leq i\leq v.$$ For $0\leq i\leq v$ let $f_i(x)=a^{\ell_{i}}x-b_i$, and define $F=\{f_i:0\leq i\leq v\}$. Let $S$ denote the set $S_{F}$ described earlier. We prove the following two results. \begin{theorem}\label{t1} Let $m$ be a positive integer. Then the sequence $S$ reduced modulo $m$ is the image, under a coding, of an infinite word that is a fixed point of a morphism over a finite alphabet. \end{theorem} \begin{theorem}\label{t2} The characteristic sequence of $S$ is a-automatic. \end{theorem} The family $F$ considered here is slightly more general than a similar family studied by Kimberling \cite{kimberling2}. In particular, he added several restrictions to the functions in $F$ that ensure that the sets $f_j(S)$ are pairwise disjoint. In this case the numbers in $S$ are matched in one-to-one correspondence with the words over the alphabet $\{0,\ldots,v\}$. For such sets he also studied, for fixed $j$, the distribution of the numbers $\{f_j(x):x\in S\}$ in $S$. As a result of Theorem \ref{t1} these frequencies, when they exist, are coordinates of a normalized eigenvector of the incidence matrix of the morphism corresponding to its Perron-Frobenius eigenvalue (\cite{allouche}, Theorem 8.4.6). We prove Theorems \ref{t1} and \ref{t2} in Sections \ref{proof1} and \ref{charseq}, respectively. The proofs give rise to simple algorithms for constructing the morphisms. The algorithms also reveal that Theorems \ref{t1} and \ref{t2} hold when the functions in $F$ are of the form $f_i(x)=a^{\ell_{i}}x+b_i$. In Section \ref{examples} we mention some examples of self-generating sets that have further connections with sequences of integers with missing blocks. In Section \ref{openq} we suggest another possible generalization of the Kimberling set in which these results apply. We begin, however, by proving some necessary lemmas. \section{Preliminary Lemmas for Theorem \ref{t1}} \label{tree} In this section we show how to put a tree structure on $S$ that gives rise to the morphisms. Let $L=\max\{\ell_{0},\ldots,\ell_{v}\}$, and let $B=\max\{b_{0},\ldots,b_{v}\}$. Let $S=\{s_{n}\}_{n=1}^{\infty}=\{s_{1}, nodesep=6pt} \rput(1,1){\rnode{n}{$s_{i_n}$}} \rput[l](1.9,1){\rnode[l]{dots}{\ldots}} \rput[l](2,2){\rnode[l]{k}{$s_n$}} \rput[l](3,1){\rnode[l]{i+l}{$s_{i_n+p_n}$}} \ncline{k}{n} \ncline{k}{i+l} \end{pspicture} \end{center} \caption{$\tau_{n,1}$} \label{fig_skchildren} \end{figure} \noindent For $h>1$, we continue this process recursively on the children of $s_{n}$ to obtain $\tau_{n,h}$. \begin{example}\label{ex_tau14} If $F=\{2x,8x-3,16x-4\}$, then $S=\{1,2,4,5,8,10,12,13,16,\ldots\}$ and $\tau_{1,4}$ is as presented in Figure \ref{fig_tau14}. Notice that $\tau_{1,3}$, $\tau_{1,2}$, $\tau_{1,1}$, $\tau_{2,3}$, $\tau_{2,2}$, $\tau_{2,1}$, $\tau_{3,2}$, $\tau_{3,1}$, $\tau_{4,1}$, and $\tau_{5,1}$ are all contained in $\tau_{1,4}$. \begin{figure}[h!] \begin{center} \begin{pspicture}(1,0)(10,4) \psset{arrows=->, nodesep=6pt} \rput[l](1,0){\rnode[l]{l}{$1$}} \rput[l](2,0){\rnode[l]{m}{$2$}} \rput[l](3.5,0){\rnode[l]{n}{$4$}} \rput[l](5,0){\rnode[l]{o}{$5$}} \rput[l](6,0){\rnode[l]{p}{$8$}} \rput[l](7.5,0){\rnode[l]{q}{$10$}} \rput[l](9,0){\rnode[l]{r}{$12$}} \rput[l](9.5,0){\rnode[l]{s}{$13$}} \rput[l](10,0){\rnode[l]{t}{$16$}} \rput[l](1.5,1){\rnode[l]{g}{$1$}} \rput[l](3.5,1){\rnode[l]{h}{$2$}} \rput[l](5.5,1){\rnode[l]{i}{$4$}} \rput[l](7.5,1){\rnode[l]{j}{$5$}} \rput[l](9.5,1){\rnode[l]{k}{$8$}} \rput[l](2.5,2){\rnode[l]{d}{$1$}} \rput[l](5.5,2){\rnode[l]{e}{$2$}} \rput[l](8.5,2){\rnode[l]{f}{$4$}} \rput[l](4,3){\rnode[l]{b}{$1$}} \rput[l](8.5,3){\rnode[l]{c}{$2$}} \rput[l](6.25,4){\rnode[l]{a}{$1$}} \ncline{a}{b} \ncline{a}{c} \ncline{b}{d} \ncline{b}{e} \ncline{c}{f} \ncline{d}{g} \ncline{d}{h} \ncline{e}{i} \ncline{f}{j} \ncline{f}{k} \ncline{g}{l} \ncline{g}{m} \ncline{h}{n} \ncline{i}{o} \ncline{i}{p} \ncline{j}{q} \ncline{k}{r} \ncline{k}{s} \ncline{k}{t} \end{pspicture} \end{center} \caption{$\tau_{1,4}$ in Example \ref{ex_tau14}} \label{fig_tau14} \end{figure} \end{example} Notice that the vertices in level $h$ of $\tau_{1,h}$, in order, correspond to the first few elements of $S$. The following lemmas provide useful results about the structure of $\tau_{n,h}$. The first two are clear from the definitions. Note that it follows from the definition of $S$ and the fact that $b_0=0$ and $\ell_0=1$ that if $s\in S$, then $a^hs=f_0^h(s)\in S$ for all $h\geq 1$. \begin{lem}\label{obs_succ} For $h\geq 1$, the smallest element of $S$ in level $h$ of $\tau_{n,h}$ is the successor in $S$ of $a^h s_{n-1}$, and the largest element in level $h$ is $a^h s_{n}$. \end{lem} \begin{lem}\label{obs_pathdown} Let $s\in S$. Then $a^h s_{n-1}as_{n-1}\geq a^\ell s\geq a^\ell s-b=as_n-c$, a contradiction. Thus, $as_n\leq a^\ell s$, and since $as_n-c=a^\ell s-b$, it follows that $c\leq b\leq B$. Now suppose that \eqref{ch1} holds for some $h\geq 1$. Let $a^{h+1}s_n-c$ be a vertex in level $h+1$ of $\tau_{n,h+1}$. Then $a^{h+1}s_n-c$ is a child of some vertex $s_j$ in level $h$ of $\tau_{n,h}$. Write $s_j$ in the form $a^hs_n-c'$ for some constant $c'$. By hypothesis $c'\leq \left(\frac{a^h-1}{a-1}\right)B$. Also, $a^{h+1}s_n-c$ is a vertex in $\tau_{j,1}$. We can then write $a^{h+1}s_n-c=as_j-c''$ for some $c''$. By the proof of the $h=1$ case, we have that $c''\leq B$. Also, since $s_j=a^hs_n-c'$, it follows that $$a^{h+1}s_n-c=as_j-c''=a^{h+1}s_n-ac'-c''.$$ It follows then that $c=ac'+c''\leq a\left(\frac{a^h-1}{a-1}\right)B+B=\left(\frac{a^{h+1}-1}{a-1}\right)B$. \end{proof} The next Lemma shows that for $h\geq L-1$, the form of $\tau_{n,h}$ is completely determined by $\tau_{n,L-1}$, and in particular by the differences between successive vertices in each level of the tree $\tau_{n,L-1}$. \begin{lem}\label{lem_taujtauk} Assume $L\geq 1$, $k\neq 1$, and $n\neq 1$. Assume also that $\tau_{k,L-1}$ and $\tau_{n,L-1}$ have the property that $a^is_k-c$ is a vertex in $\tau_{k,L-1}$ if and only if $a^is_n-c$ is a vertex in $\tau_{n,L-1}$. Then $\tau_{k,L}$ and $\tau_{n,L}$ also possess this property. \end{lem} \begin{proof} If $L=1$ then for $k\neq 1$ and $n\neq 1$, $R_k=\{as_k-b_i:0\leq i\leq v\}$ and $R_n=\{as_n-b_i:0\leq i\leq v\}$, and the result is trivial. Assume then that $L>1$. Let $s=a^Ls_k-c$ be a vertex in level $L$ of $\tau_{k,L}$. We will show that $a^Ls_n-c$ is a vertex in level $L$ of $\tau_{n,L}$. Since $s\in S$, there is an $s'\in S$ and a function $f(x)=a^\ell x-b\in F$ such that $f(s')=s$. By Lemma \ref{lem_node}, $s$ is a vertex in level $\ell$ of the tree with root $s'$. Since $s$ is also in level $L$ of $\tau_{k,L}$, and since $\ell\leq L$, it follows that $s'$ is a leaf in the tree $\tau_{k,h}$, where $h:=L-\ell$. Let $c'$ be such that $s'=a^hs_k-c'$. Since $f(s')=s$, we have that $$a^Ls_k-c=s=f(s')=f(a^hs_k-c')=a^{\ell+h}s_k-a^\ell c'-b=a^Ls_k-a^\ell c'-b,$$ and so $c=a^\ell c'+b$. On the other hand, since $h\leq L-1$, by hypothesis we have that $a^hs_n-c'$ is a vertex in level $h$ of $\tau_{n,L-1}$. By Lemma \ref{lem_node} again, it follows that $f(a^hs_n-c')$ is a vertex in level $\ell$ of the tree with root $a^hs_n-c'$. Thus, $$f(a^hs_n-c')=a^{\ell+h}s_n-a^\ell c'-b=a^Ls_n-c$$ is a vertex in level $L$ of $\tau_{n,L}$. We have thus shown that if $a^Ls_k-c$ is a vertex in $\tau_{k,L}$, then $a^Ls_n-c$ is a vertex in $\tau_{n,L}$. Reversing the roles of $k$ and $n$, we can show that that if $a^Ls_n-c$ is a vertex in $\tau_{n,L}$ then $a^Ls_k-c$ is a vertex in $\tau_{k,L}$. This completes the proof. \end{proof} Note that it is a consequence of the definition of the trees that any two trees $\tau_{k,h}$ and $\tau_{n,h}$ satisfying the property of Lemma \ref{lem_taujtauk} have the same tree structure. Also notice that the requirement that $k\neq 1$ and $n\neq 1$ is only necessary when $L=1$. This is because $n=1$ is the only value of $n$ for which $s_n\in R_n$. \section{Proof of Theorem 1} \label{proof1} Define an equivalence relation $\sim$ on $S$ as follows. Let $\tau_{n,L-1}\bmod m$ be the tree obtained from $\tau_{n,L-1}$ by reducing the vertices of $\tau_{n,L-1}$ modulo $m$. We begin by defining $s_{1}\sim s_{1}$. For $n\neq 1$ and $k\neq 1$, we say $s_{n}\sim s_{k}$ if and only if $\tau_{n,L-1}$ and $\tau_{k,L-1}$ satisfy the property of Lemma \ref{lem_taujtauk} and $\tau_{n,L-1}\bmod m = \tau_{k,L-1}\bmod m$. We pause from the proof for a brief example. \begin{example}\label{ex_modtrees} Let $F=\{2x,4x-1,8x-3\}$. Then $2\sim 4$ when reducing modulo 2, as the following tree structures show. \vspace{.5cm} \begin{center} \begin{pspicture}(1,0)(14,3) \psset{arrows=->, nodesep=6pt} \rput(1,1){\rnode{j}{$5$}} \rput[l](2,1){\rnode[l]{k}{$6$}} \rput[l](3,1){\rnode[l]{l}{$7$}} \rput[l](4,1){\rnode[l]{m}{$8$}} \rput[l](6,1){\rnode[l]{n}{$1$}} \rput[l](7,1){\rnode[l]{o}{$0$}} \rput[l](8,1){\rnode[l]{p}{$1$}} \rput[l](9,1){\rnode[l]{q}{$0$}} \rput[l](11,1){\rnode[l]{r}{$13$}} \rput[l](12,1){\rnode[l]{s}{$14$}} \rput[l](13,1){\rnode[l]{t}{$15$}} \rput[l](14,1){\rnode[l]{u}{$16$}} \rput[l](2.5,0){\rnode[l]{v}{$\tau_{2,2}$}} \rput[l](5.6,0){\rnode[l]{w}{$\tau_{2,2}\bmod 2=\tau_{4,2}\bmod 2$}} \rput[l](12.5,0){\rnode[l]{x}{$\tau_{4,2}$}} \rput[l](1.5,2){\rnode[l]{d}{$3$}} \rput[l](3.5,2){\rnode[l]{e}{$4$}} \rput[l](6.5,2){\rnode[l]{f}{$1$}} \rput[l](8.5,2){\rnode[l]{g}{$0$}} \rput[l](11.5,2){\rnode[l]{h}{$7$}} \rput[l](13.5,2){\rnode[l]{i}{$8$}} \rput[l](2.5,3){\rnode[l]{a}{$2$}} \rput[l](7.5,3){\rnode[l]{b}{$0$}} \rput[l](12.5,3){\rnode[l]{c}{$4$}} \ncline{a}{d} \ncline{a}{e} \ncline{b}{f} \ncline{b}{g} \ncline{c}{h} \ncline{c}{i} \ncline{d}{j} \ncline{d}{k} \ncline{e}{l} \ncline{e}{m} \ncline{f}{n} \ncline{f}{o} \ncline{g}{p} \ncline{g}{q} \ncline{h}{r} \ncline{h}{s} \ncline{i}{t} \ncline{i}{u} \end{pspicture} \end{center} \vspace{.5cm} When reducing modulo 3, note that $2\nsim 4$, but $2\sim 8$, as the following tree structures show. \vspace{.5cm} \begin{center} \begin{pspicture}(1,0)(14,3) \psset{arrows=->, nodesep=6pt} \rput(1,1){\rnode{j}{$5$}} \rput[l](2,1){\rnode[l]{k}{$6$}} \rput[l](3,1){\rnode[l]{l}{$7$}} \rput[l](4,1){\rnode[l]{m}{$8$}} \rput[l](6,1){\rnode[l]{n}{$2$}} \rput[l](7,1){\rnode[l]{o}{$0$}} \rput[l](8,1){\rnode[l]{p}{$1$}} \rput[l](9,1){\rnode[l]{q}{$2$}} \rput[l](11,1){\rnode[l]{r}{$29$}} \rput[l](12,1){\rnode[l]{s}{$30$}} \rput[l](13,1){\rnode[l]{t}{$31$}} \rput[l](14,1){\rnode[l]{u}{$32$}} \rput[l](2.5,0){\rnode[l]{v}{$\tau_{2,2}$}} \rput[l](5.6,0){\rnode[l]{w}{$\tau_{2,2}\bmod 3=\tau_{8,2}\bmod 3$}} \rput[l](12.5,0){\rnode[l]{x}{$\tau_{8,2}$}} \rput[l](1.5,2){\rnode[l]{d}{$3$}} \rput[l](3.5,2){\rnode[l]{e}{$4$}} \rput[l](6.5,2){\rnode[l]{f}{$0$}} \rput[l](8.5,2){\rnode[l]{g}{$1$}} \rput[l](11.5,2){\rnode[l]{h}{$15$}} \rput[l](13.5,2){\rnode[l]{i}{$16$}} \rput[l](2.5,3){\rnode[l]{a}{$2$}} \rput[l](7.5,3){\rnode[l]{b}{$2$}} \rput[l](12.5,3){\rnode[l]{c}{$8$}} \ncline{a}{d} \ncline{a}{e} \ncline{b}{f} \ncline{b}{g} \ncline{c}{h} \ncline{c}{i} \ncline{d}{j} \ncline{d}{k} \ncline{e}{l} \ncline{e}{m} \ncline{f}{n} \ncline{f}{o} \ncline{g}{p} \ncline{g}{q} \ncline{h}{r} \ncline{h}{s} \ncline{i}{t} \ncline{i}{u} \end{pspicture} \end{center} \vspace{.3cm} \end{example} Now, by Lemma \ref{lem_xRk} there are only finitely many equivalence classes for this relation. We now define the morphism. Suppose $R_{n}=\{s_{i_n},\ldots,s_{i_n+p_n}\}$. Let $\overline{s_n}$ denote the equivalence class of $s_{n}$, and let $A$ be a complete set of equivalence class representatives. Define $\sigma:A\rightarrow A^{*}$, where $A^*$ is the set of finite words over $A$, by $$\sigma(\overline{s_n})=\overline{s_{i_n}}~\overline{s_{i_n+1}}~\cdots~\overline{s_{i_n+p_n}}.$$ To see that $\sigma$ is well-defined, suppose $\overline{s_n}=\overline{s_k}$ and $\sigma(\overline{s_k})=\overline{s_{i_k}}\cdots\overline{s_{i_k+p_k}}$. If $L>1$, then since $\overline{s_n}=\overline{s_k}$, it follows that $\tau_{n,L-1}$ and $\tau_{k,L-1}$ have the same tree structure, and therefore $p_n=p_k$. If $L=1$, it was shown in the proof of Lemma \ref{lem_taujtauk} that $p_n=p_k$. In either case, it then follows from Lemma \ref{lem_taujtauk} that $$\overline{s_{i_n}}=\overline{s_{i_k}},\overline{s_{i_n+1}}=\overline{s_{i_k+1}},\ldots,\overline{s_{i_n+p_n}}=\overline{s_{i_k+p_k}}.$$ Thus, $\sigma$ is well defined. Extend $\sigma$ by concatenation to get a morphism from $A^{*}\rightarrow A^{*}$. It is clear that $\sigma(\overline{s_1})=\overline{s_1}\cdots\overline{s_a}$. Thus, the infinite word given by \begin{equation}\label{fixedpoint} \lim_{i\rightarrow\infty}\sigma^{i}(\overline{s_1}) \end{equation} is a fixed point of $\sigma$. Now define a map $\rho:A\rightarrow\{0,1,\ldots,m-1\}$ by $$\rho(\overline{s_n})=s_n\bmod m.$$ Clearly $\rho$ is well defined. Extend $\rho$ by concatenation to obtain a morphism from $A^*\rightarrow\{0,1,\ldots,m-1\}^*$. This morphism is then a coding \cite{allouche}. It is clear that the sequence $S$ reduced modulo $m$ is the image, under $\rho$, of the fixed point \eqref{fixedpoint}. This completes the proof of Theorem \ref{t1}. \begin{example}\label{ex_3x3x-1} Let $F=\{3x,3x-1\}$. For this $F$ the resulting sequence $S$ is {\tt A032924}+1, where {\tt A032924} is the sequence of natural numbers whose ternary representation contains no 0. We will produce the morphism for $S\bmod 3$. We see that $L=1$, so for $n\neq 1$ and $k\neq 1$, $s_{n}\sim s_{k}$ if and only if $s_{n}\bmod 3 = s_{k}\bmod 3$. The complete set of equivalence class representatives is then $\{\overline{1},\overline{2},\overline{3}\}$. The morphism is therefore \begin{eqnarray} \nonumber \overline{1} &\rightarrow& \overline{1}\hspace{.1cm}\overline{2}\hspace{.1cm}\overline{3}\\ \nonumber \overline{2} &\rightarrow& \overline{5}\hspace{.1cm}\overline{6}=\overline{2}\hspace{.1cm}\overline{3}\\ \nonumber \overline{3} &\rightarrow& \overline{8}\hspace{.1cm}\overline{9}=\overline{2}\hspace{.1cm}\overline{3} \end{eqnarray} Letting $a=\overline{1}$, $b=\overline{2}$, and $c=\overline{3}$, we get the morphism $a \rightarrow abc$, $b \rightarrow bc$, $c \rightarrow bc$. Iterating this morphism on $a$ produces a fixed point. Now define the morphism $\rho:\{a,b,c\}^*\rightarrow\{0,1,2\}^*$ by $\rho(a)=1$, $\rho(b)=2$, and $\rho(c)=0$. The proof of Theorem \ref{t1} shows that the sequence $S\bmod 3$ is the image of the fixed point of $\sigma$ under this coding. \end{example} \begin{example}\label{ex_smod2} Let $F=\{2x,4x-1,8x-3\}$. We will find the morphism for $S\bmod 2$. Using the method described above, we find \begin{eqnarray} \nonumber \sigma(\overline{1})&=&\overline{1}\hspace{.1cm}\overline{2} \\ \nonumber \sigma(\overline{2})&=&\overline{3}\hspace{.1cm}\overline{4}=\overline{3}\hspace{.1cm}\overline{2} \\ \nonumber \sigma(\overline{3})&=&\overline{5}\hspace{.1cm}\overline{6}=\overline{5}\hspace{.1cm}\overline{2} \\ \nonumber \sigma(\overline{5})&=&\overline{10}=\overline{2} \end{eqnarray} Thus, the sequence $S\bmod 2$ is the image by the coding $a\rightarrow 1$, $b\rightarrow 0$, $c\rightarrow 1$, $d\rightarrow 1$, of the fixed point of the morphism $a\rightarrow ab$, $b\rightarrow cb$, $c\rightarrow db$, $d\rightarrow b$. \end{example} \begin{example}\label{ex_smod3} We use the same procedure to get the morphism for $S\bmod 3$ when $F=\{2x,4x-1,8x-3\}$: \begin{center} \begin{tabular}{lllll} $\sigma(\overline{1})=\overline{1}\hspace{.1cm}\overline{2}$ & $\sigma(\overline{6})=\overline{11}\hspace{.1cm}\overline{6}$ & & $a\rightarrow ab$ & $f\rightarrow hf$ \\ $\sigma(\overline{2})=\overline{3}\hspace{.1cm}\overline{4}$ & $\sigma(\overline{7})=\overline{13}\hspace{.1cm}\overline{2}$ & & $b\rightarrow cd$ & $g\rightarrow ib$ \\ $\sigma(\overline{3})=\overline{5}\hspace{.1cm}\overline{6}$ & $\sigma(\overline{11})=\overline{21}\hspace{.1cm}\overline{4}$ & \hspace{.7cm} or \hspace{.7cm} & $c\rightarrow ef$ & $h\rightarrow jd$ \\ $\sigma(\overline{4})=\overline{7}\hspace{.1cm}\overline{2}$ & $\sigma(\overline{13})=\overline{2}$ & & $d\rightarrow gb$ & $i\rightarrow b$ \\ $\sigma(\overline{5})=\overline{4}$ & $\sigma(\overline{21})=\overline{6}$ & & $e\rightarrow d$ & $j\rightarrow f$ \\ \end{tabular} \end{center} with the coding $b\rightarrow 2$, $e\rightarrow 2$, $h\rightarrow 2$, $a\rightarrow 1$, $d\rightarrow 1$, $g\rightarrow 1$, $i\rightarrow 1$, $c\rightarrow 0$, $f\rightarrow 0$, $j\rightarrow 0$. \end{example} \section{Proof of Theorem 2}\label{charseq} Recall that $L=\max\{\ell_{0},\ldots,\ell_{v}\}$ and $B=\max\{b_{0},\ldots,b_{v}\}$. Let $\{u_{n}\}_{n=0}^{\infty}$ be the characteristic sequence of $S$. We will show that $\{u_{n}\}$ is the image, under a coding, of a fixed point of a morphism of constant length. Specifically, we will show how to construct a morphism of length $a$ for which $\{u_{n}\}$ is the image, under a coding, of one of its fixed points. It will follow that $\{u_{n}\}$ is $a$-automatic (\cite{allouche}, Theorem 6.3.2). Define an equivalence relation $\sim$ on $\{u_{n}\}$ as follows. Associate with each $u_{n}$ a rooted tree of height $L-1$, with $u_{n}$ as the root , in which each vertex $u_i$ has children $$u_{ai-(a-1)},\ldots,u_{ai-1},u_{ai},$$ in order. It follows from this definition that the vertices of the tree of level $h$ are the terms $$u_{a^hn-(a^h-1)},\ldots,u_{a^hn-1},u_{a^hn}.$$ Figure \ref{fig_unsmall} shows a tree for $u_n$ when $L=3$ and $a=2$. \begin{figure}[h] \begin{center} \begin{pspicture}(1,1)(7,3) \psset{arrows=->, nodesep=6pt} \rput(4,3){\rnode{n}{$u_{n}$}} \rput[l](2,2){\rnode[l]{2n}{$u_{2n-1}$}} \rput[l](6,2){\rnode[l]{2n+1}{$u_{2n}$}} \rput[1](1,1){\rnode[1]{4n}{$u_{4n-3}$}} \rput[1](3,1){\rnode[1]{4n+1}{$u_{4n-2}$}} \rput[1](5,1){\rnode[1]{4n+2}{$u_{4n-1}$}} \rput[1](7,1){\rnode[1]{4n+3}{$u_{4n}$}} \ncline{n}{2n} \ncline{n}{2n+1} \ncline{2n}{4n} \ncline{2n}{4n+1} \ncline{2n+1}{4n+2} \ncline{2n+1}{4n+3} \end{pspicture} \end{center} \vspace{-.3cm} \caption{Tree associated with $u_{n}$ for $L=3$ and $a=2$} \label{fig_unsmall} \end{figure} To define $\sim$, let $u_{1}\sim u_{1}$. If $n\neq 1$ and $k\neq 1$, we say $u_{n}\sim u_{k}$ if and only if the corresponding vertices of the trees are equal. Clearly there are only finitely many equivalence classes for this relation. Let $\overline{u_n}$ be the equivalence class of $u_{n}$, and let $A$ be a complete set of equivalence class representatives. Define the mapping $\sigma:A\rightarrow A^{*}$ by \begin{equation}\label{sigma} \nonumber \sigma(\overline{u_n})=\overline{u_{an-(a-1)}}\cdots\overline{u_{an-1}}~\overline{u_{an}}. \end{equation} To show that $\sigma$ is well-defined, assume that $\overline{u_n}=\overline{u_k}$. We need to show that $\overline{u_{an-i}}=\overline{u_{ak-i}}$ for $0\leq i\leq a-1$. It suffices to consider the case that $n\neq 1$ and $k\neq 1$, since $u_1$ is the only element in the equivalence class for $u_1$. Extend the trees associated with $u_n$ and $u_k$ by one level to obtain rooted trees of height $L$. Figure 4 shows an extended tree for $L=3$ and $a=2$. \vspace{.2cm} \begin{figure}[h] \begin{center} \begin{pspicture}(0,0)(14,3) \psset{arrows=->, nodesep=6pt} \rput(7,3){\rnode{n}{$u_{n}$}} \rput[l](3,2){\rnode[l]{2n}{$u_{2n-1}$}} \rput[l](11,2){\rnode[l]{2n+1}{$u_{2n}$}} \rput[1](1,1){\rnode[1]{4n}{$u_{4n-3}$}} \rput[1](5,1){\rnode[1]{4n+1}{$u_{4n-2}$}} \rput[1](9,1){\rnode[1]{4n+2}{$u_{4n-1}$}} \rput[1](13,1){\rnode[1]{4n+3}{$u_{4n}$}} \rput[1](0,0){\rnode[1]{8n}{$u_{8n-7}$}} \rput[1](2,0){\rnode[1]{8n+1}{$u_{8n-6}$}} \rput[1](4,0){\rnode[1]{8n+2}{$u_{8n-5}$}} \rput[1](6,0){\rnode[1]{8n+3}{$u_{8n-4}$}} \rput[1](8,0){\rnode[1]{8n+4}{$u_{8n-3}$}} \rput[1](10,0){\rnode[1]{8n+5}{$u_{8n-2}$}} \rput[1](12,0){\rnode[1]{8n+6}{$u_{8n-1}$}} \rput[1](14,0){\rnode[1]{8n+7}{$u_{8n}$}} \ncline{n}{2n} \ncline{n}{2n+1} \ncline{2n}{4n} \ncline{2n}{4n+1} \ncline{2n+1}{4n+2} \ncline{2n+1}{4n+3} \psset{arrows=->, nodesep=6pt, linestyle=dashed} \ncline{4n}{8n} \ncline{4n}{8n+1} \ncline{4n+1}{8n+2} \ncline{4n+1}{8n+3} \ncline{4n+2}{8n+4} \ncline{4n+2}{8n+5} \ncline{4n+3}{8n+6} \ncline{4n+3}{8n+7} \end{pspicture} \end{center} \vspace{-.3cm} \caption{The extended tree for $u_{n}$ with $L=3$ and $a=2$.} \label{fig_unextended} \end{figure} Since $\overline{u_n}=\overline{u_k}$, the corresponding vertices in the extended trees associated with $u_n$ and $u_k$ are equal for levels $0$ through $L-1$. We will show that the corresponding vertices in level $L$ of the extended trees are also equal. Let $u_{a^Ln-j}$ be a vertex at level $L$ of the extended tree for $u_n$, where $0\leq j\leq a^L-1$. Assume also that $u_{a^Ln-j}=1$. We will show that $u_{a^Lk-j}=1$. Since $u_{a^Ln-j}=1$, then $a^Ln-j$ is an element of $S$. Since $n\neq 1$, then $a^Ln-j\neq 1$, and so there is an $s\in S$ and an $f(x)=a^\ell x-b\in F$ such that \begin{equation}\label{e4.1} a^L n-j=f(s)=a^\ell s-b. \end{equation} Recall that $0\leq ba^{L-\ell}n$. Then $s\geq a^{L-\ell}n+1$, and since $0\leq b& a^Ln-j,\nonumber \end{eqnarray} a contradiction, and so $s\leq a^{L-\ell}n$. We have shown then that if $\ell