<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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://oeis.org/#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}&lt;s_{2}&lt;s_{3}&lt;\ldots\}$, and define $s_{0}=0$.  For $n\geq 1$, define the set 
$$R_{n}=\{x:as_{n-1}&lt;x\leq as_{n}\}.$$  
For $h\geq 0$, define a rooted tree $\tau_{n,h}$ of height $h$ with root  $s_{n}$ as follows.  Let $\tau_{n,0}=s_{n}$, and for $\tau_{n,1}$, the children of $s_{n}$ are the elements of $R_{n}$ in increasing order.  Thus, if $R_{n}=\{s_{i_n},\ldots,s_{i_n+p_n}\}$, then $\tau_{n,1}$ is as shown in Figure \ref{fig_skchildren}.  (Notice that $s_{i_n+p_n}=as_n$).
% \vspace{.3cm}
\begin{figure}[h]
\begin{center}
\begin{pspicture}(1,1)(3,2)
    \psset{arrows=-&gt;, 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&gt;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=-&gt;, 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}&lt;s\leq a^h s_{n}$ if and only if $s$ is a vertex in level $h$ of $\tau_{n,h}$.
\end{lem}
\begin{lem}\label{lem_node}
If $s_{n}\in S$ and $a^{\ell}x-b=f(x)\in F$, then $a^{\ell}s_{n}-b$ is a vertex in level $\ell$ of $\tau_{n,\ell}$.
\end{lem}
\begin{proof}
Note that $a^{\ell}s_{n}-b\in S$.  By definition, $0\leq b&lt;a^{\ell}$, so
$$a^{\ell}s_{n-1}\leq a^{\ell}(s_{n}-1)=a^{\ell}s_{n}-a^{\ell}&lt;a^{\ell}s_{n}-b\leq a^{\ell}s_{n}$$
It follows from Lemma \ref{obs_pathdown} that $a^{\ell}s_{n}-b$ is a leaf in the tree $\tau_{n,\ell}$.
\end{proof}

As a result of Lemmas \ref{obs_succ} and \ref{obs_pathdown}, we can write an arbitrary vertex $s$ in level $h$ of $\tau_{n,h}$ in the form $a^hs_n-c$ for some constant $c$.  The next Lemma establishes a bound for this constant.

\begin{lem}\label{lem_xRk}
Let $h\geq 1$, and let $a^hs_n-c$ be a vertex at level $h$ in the tree $\tau_{n,h}$.  Then
\begin{equation}\label{ch1}
c\leq\left(\frac{a^{h}-1}{a-1}\right)B.
\end{equation}
\end{lem}
\begin{proof}
We use induction on $h$.  Suppose $h=1$.  There exists an $s\in S$ and
a function $f(x)=a^\ell x-b\in F$, with $0\leq b&lt;a^\ell$, such that
$a^\ell s-b=f(s)=as_n-c$.  By definition of $S$, $a^{\ell-1}s\in S$,
and it follows that $s_n\leq a^{\ell-1}s$.  To see why, suppose
$a^{\ell-1}s&lt;s_n$.  Then $a^{\ell-1}s\leq s_{n-1}$, and so $a^\ell
s\leq as_{n-1}$.  Since $as_n-c$ is a vertex in $\tau_{n,1}$, by Lemma
\ref{obs_pathdown} we have that $as_n-c&gt;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&gt;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=-&gt;, 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=-&gt;, 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&gt;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} &amp;\rightarrow&amp; \overline{1}\hspace{.1cm}\overline{2}\hspace{.1cm}\overline{3}\\
\nonumber \overline{2} &amp;\rightarrow&amp; \overline{5}\hspace{.1cm}\overline{6}=\overline{2}\hspace{.1cm}\overline{3}\\
\nonumber \overline{3} &amp;\rightarrow&amp; \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})&amp;=&amp;\overline{1}\hspace{.1cm}\overline{2} \\
\nonumber \sigma(\overline{2})&amp;=&amp;\overline{3}\hspace{.1cm}\overline{4}=\overline{3}\hspace{.1cm}\overline{2} \\
\nonumber \sigma(\overline{3})&amp;=&amp;\overline{5}\hspace{.1cm}\overline{6}=\overline{5}\hspace{.1cm}\overline{2} \\
\nonumber \sigma(\overline{5})&amp;=&amp;\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}$ &amp; $\sigma(\overline{6})=\overline{11}\hspace{.1cm}\overline{6}$ &amp; &amp;
$a\rightarrow ab$ &amp;
$f\rightarrow hf$ \\

$\sigma(\overline{2})=\overline{3}\hspace{.1cm}\overline{4}$ &amp; $\sigma(\overline{7})=\overline{13}\hspace{.1cm}\overline{2}$ &amp; &amp;
$b\rightarrow cd$ &amp;
$g\rightarrow ib$ \\

$\sigma(\overline{3})=\overline{5}\hspace{.1cm}\overline{6}$ &amp; $\sigma(\overline{11})=\overline{21}\hspace{.1cm}\overline{4}$ &amp; \hspace{.7cm} or \hspace{.7cm} &amp;
$c\rightarrow ef$ &amp;
$h\rightarrow jd$ \\

$\sigma(\overline{4})=\overline{7}\hspace{.1cm}\overline{2}$ &amp; 
$\sigma(\overline{13})=\overline{2}$ &amp; &amp;
$d\rightarrow gb$ &amp;
$i\rightarrow b$ \\

$\sigma(\overline{5})=\overline{4}$ &amp;
$\sigma(\overline{21})=\overline{6}$ &amp; &amp;
$e\rightarrow d$ &amp; 
$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=-&gt;, 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=-&gt;, 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=-&gt;, 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 b&lt;a^\ell$, and $\ell\leq L$.  

If $\ell=L$, then $a^Ls-b=a^Ln-j$, and so $a^L(s-n)=b-j$.  Since $0\leq
b,j &lt;a^L$, this is only possible if $b=j$ and $s=n$.  In this case we
have that $n\in S$.  Since $\overline{u_n}=\overline{u_k}$, it must be
the case that $u_k=1$, and so $k\in S$.  It follows that
$f(k)=a^Lk-b=a^Lk-j$ is also in $S$, and thus $u_{a^Lk-j}=1$.

Suppose then that $\ell&lt;L$.  It must be the case that $a^{L-\ell}n-(a^{L-\ell}-1)\leq s\leq a^{L-\ell}n$.  To see why, notice that if $s&lt; a^{L-\ell}n-(a^{L-\ell}-1)$, then $s\leq a^{L-\ell}n-(a^{L-\ell}-1)-1=a^{L-\ell}(n-1)$, and so by \eqref{e4.1} we have
\begin{eqnarray}
a^Ln-j= a^\ell s-b &amp;\leq&amp; a^\ell(a^{L-\ell}(n-1))-b \nonumber\\
           &amp;=&amp; a^L(n-1)-b \nonumber\\
           &amp;\leq&amp; a^L(n-1) \nonumber\\
           &amp;&lt;&amp; a^L(n-1)+1 \nonumber\\
           &amp;=&amp; a^Ln-(a^L-1) \nonumber\\
           &amp;\leq&amp; a^Ln-j. \nonumber
\end{eqnarray}
This is a contradiction, and so $a^{L-\ell}n-(a^{L-\ell}-1)\leq s$.  On the other hand, suppose that $s&gt;a^{L-\ell}n$.  Then $s\geq a^{L-\ell}n+1$, and since $0\leq b&lt;a^\ell$, it follows from \eqref{e4.1} again that 
\begin{eqnarray}
a^Ln-j = a^\ell s-b &amp;\geq&amp; a^\ell(a^{L-\ell}n+1)-b \nonumber\\
                    &amp;=&amp; a^Ln+a^\ell -b \nonumber\\
                    &amp;\geq&amp; a^Ln+1 \nonumber\\
                    &amp;&gt;&amp; a^Ln-j,\nonumber
\end{eqnarray}
a contradiction, and so $s\leq a^{L-\ell}n$.
We have shown then that if $\ell&lt;L$, then
$a^{L-\ell}n-(a^{L-\ell}-1)\leq s\leq a^{L-\ell}n$.  It follows then
that $u_s$ is a vertex in the tree of height $L-1$ associated with
$u_n$, and we can write \begin{equation}\label{e4.3} s=a^{L-\ell}n-m,
\end{equation}
where $0\leq m\leq a^{L-\ell}-1$.  Notice that we also have that $a^{L-\ell}k-m$ is a vertex in the tree of height $L-1$ associated with $u_k$.  By \eqref{e4.1} and \eqref{e4.3} we have that $a^Ln-j=f(s)=a^Ln-a^{\ell}m-b$, and thus 
\begin{equation}\label{e4.4}
j=a^\ell m+b.
\end{equation}
Now, since $a^{L-\ell}n-m=s\in S$, $u_s=1$, and since
$\overline{u_n}=\overline{u_k}$, we have that $a^{L-\ell}k-m$ is in
$S$.  It also follows from \eqref{e4.4} that $a^Lk-j=a^Lk-a^\ell
m-b=f(a^{L-\ell}k-m)$.  Thus, $a^Lk-j$ is also in $S$, and therefore
$u_{a^Lk-j}=1$.

We have shown that if $u_{a^Ln-j}=1$ then $u_{a^Lk-j}=1$.  By reversing
the roles of $n$ and $k$, the same proof shows that if $u_{a^Lk-j}=1$
then $u_{a^Ln-j}=1$.  Thus, for $0\leq j\leq a^L-1$, $u_{a^Ln-j}=1$ if
and only if $u_{a^Lk-j}=1$.  This proves that $u_{a^Ln-j}=u_{a^Lk-j}$
for $0\leq j\leq a^L-1$.  Thus, the extended trees for $u_n$ and $u_k$
are the same.  Since, for $0\leq i\leq a-1$, the trees associated with
$u_{an-i}$ and $u_{ak-i}$ are subtrees of the extended trees for $u_n$
and $u_k$, respectively, it follows that $u_{an-i}=u_{ak-i}$ for $0\leq
i\leq a-1$.  Thus, $\sigma$ is well-defined.

Now extend $\sigma$ to a mapping from $A^{*}\rightarrow A^{*}$ by
concatenation.  Since $\sigma(\overline{u}_{1})=\overline{u_1}\cdots
\overline{u_{an}}$, repeated iteration of $\sigma$ on
$\overline{u}_{1}$ generates a fixed point.  As in the end of the proof
of Theorem \ref{t1}, we can define a coding which associates
$\overline{u_n}$ with $u_{n}$.  The characteristic sequence $\{u_n\}$
is then the image of this fixed point.  Since the morphism $\sigma$ is
of length $a$, the characteristic sequence is $a$-automatic
(\cite{allouche}, Theorem 6.3.2).

\begin{example}
We find the morphism generating the characteristic sequence of $S$ when $F=\{2x,4x-1,8x-3\}$.
\begin{eqnarray}
\nonumber \sigma(\overline{u_1})&amp;=&amp;\overline{u_1}~\overline{u_2}\\
\nonumber \sigma(\overline{u_2})&amp;=&amp;\overline{u_3}~\overline{u_4}=\overline{u_3}~\overline{u_2}\\
\nonumber \sigma(\overline{u_3})&amp;=&amp;\overline{u_5}~\overline{u_6}=\overline{u_5}~\overline{u_2}\\
\nonumber \sigma(\overline{u_5})&amp;=&amp;\overline{u_9}~\overline{u_{10}}=\overline{u_9}~\overline{u_2}\\
\nonumber \sigma(\overline{u_9})&amp;=&amp;\overline{u_{17}}~\overline{u_{18}}=\overline{u}_{9}~\overline{u_9}
\end{eqnarray}
This corresponds to the morphism $a \rightarrow ab$, $b \rightarrow cb$, $c \rightarrow db$, $d \rightarrow eb$, and $e \rightarrow ee$, whose fixed point produced by iteration on $a$ yields the characteristic sequence of $S$ via the coding $a\rightarrow 1$, $b\rightarrow 1$ $c\rightarrow 1$, $d\rightarrow 1$, $e\rightarrow 0$.
\end{example}

\begin{example}\label{ex_charseq3x9x-1}
Let $F=\{3x,9x-1\}$.  Then $L=2$, and so each $u_n$ in the characteristic sequence $\{u_n\}$  of $S$ is associated with the tree of height $1$ having children $u_{3n-2}$, $u_{3n-1}$, and $u_{3n}$.  The morphism generating the characteristic sequence maps $\overline{u_n} \rightarrow \overline{u_{3n-2}}\hspace{.1cm}\overline{u_{3n-1}}\hspace{.1cm}\overline{u_{3n}}$.  We find that
\begin{eqnarray}
\nonumber \sigma(\overline{u_1})&amp;=&amp;\overline{u_1}~\overline{u_2}~\overline{u_3}\\
\nonumber \sigma(\overline{u_2})&amp;=&amp;\overline{u_4}~\overline{u_5}~\overline{u_6}=\overline{u_2}~\overline{u_2}~\overline{u_2}\\
\nonumber \sigma(\overline{u_3})&amp;=&amp;\overline{u_7}~\overline{u_8}~\overline{u_9}=\overline{u_2}~\overline{u_8}~\overline{u_3}\\
\nonumber \sigma(\overline{u_8})&amp;=&amp;\overline{u_{22}}~\overline{u_{23}}~\overline{u_{24}}=\overline{u_2}~\overline{u_2}~\overline{u_3}
\end{eqnarray}
This corresponds to the morphism
$a\rightarrow abc$,
$b\rightarrow bbb$,
$c\rightarrow bdc$, and 
$d\rightarrow bbc$.  The fixed point of this morphism produced by iteration on $a$ gives the characteristic sequence via the coding $a\rightarrow 1$, $c\rightarrow 1$, $d\rightarrow 1$, $b\rightarrow 0$.  
\end{example}





\section{Examples}\label{examples}

In this section we give some additional examples of self-generating
sets which produce sequences of integers defined by missing blocks.  It
was mentioned already that the original sequence of Kimberling
\cite{kimberling1} is 1+{\tt A003754}, where {\tt A003754} is the
sequence of integers whose binary expansion does not contain the block
00.  The binary expansions of the integers in this sequence also
correspond to the lazy Fibonacci expansions of the natural numbers.
The following examples expand this idea.  (For more on lazy expansions,
see \cite{erdos} and \cite{tichy}).

\begin{example}
Let $S$ be the set generated by $F=\{2x,4x-1,8x-3\}$, starting with 1.  By reasoning similar to that used for the original Kimberling sequence, $S$ is 1+{\tt A003796}, where {\tt A003796} is the sequence of integers whose binary expansion does not contain the block 000.  The binary expansions of the integers in this sequence also correspond to the lazy expansions of the natural numbers with respect to the sequence of Tribonacci numbers, starting with $t_2=1$, $t_3=2$, $t_4=4$, and $t_n=t_{n-1}+t_{n-2}+t_{n-3}$ for $n\geq 5$.  The sequence $S$ reduced modulo 2, starting with the second term, gives
$$0,~1,~0,~1,~0,~1,~0,~0,~1,~0,~1,~0,~1,~\ldots,$$
which is the image of the fixed point of the tribonacci morphism $a\rightarrow ab$, $b\rightarrow ac$, $c\rightarrow a$, under the coding $a\rightarrow 0$ and $b\rightarrow 1$, $c\rightarrow 1$.
\end{example}

\begin{example}
In general, if $F=\{2^kx-(2^{k-1}-1):1\leq k\leq n\}$, then $S-1$ is
the sequence of integers whose binary expansion does not contain blocks
of $n$ zeros.  These expansions correspond to the lazy expansions of
the natural numbers with respect to the base given by the sequence of
$n$-bonacci numbers.  The sequence $S$ reduced modulo 2, starting at
the second term, is the image of the fixed point of the morphism
$a_1\rightarrow a_1a_2$, $a_2\rightarrow a_1a_3$, $\ldots$,
$a_{n-1}\rightarrow a_1a_{n-1}$, and $a_n\rightarrow a_1$, under the
coding $a_1\rightarrow 0$ , $a_2\rightarrow 1,\cdots,a_n\rightarrow
1$.  \end{example}

Familiarity with the method of the proof Theorem \ref{t1} reveals that
the Theorem is also valid when the functions in $F$ are all of the form
$f_i(x)=a^{\ell_i}x+b_i$.  Moreover, if the minimal requirement is that
$0\in S$, then the requirement that $b_0=0$ can be removed.

\begin{example}
Let $F=\{3x+1,3x+2,9x+3,9x+6\}$.  If the minimal requirement for $S$ is that $0\in S$, then it is not hard to see that $S$ is the sequence of integers whose ternary representation does not contain the block 00.  These ternary representations correspond to the lazy representations of the natural numbers with respect to sequence {\tt A028859}, which is given recursively by $r_1=1$, $r_2=3$, $\ldots$, $r_n=2r_{n-1}+2r_{n-2}$.  It is also interesting to note that if the sequence $S+1$ is reduced modulo 3 and then reduced again modulo 2, then the resulting sequence, starting from the second character, is the fixed point of the morphism $0\rightarrow 001$, $1\rightarrow 00$.  
\end{example}
It is worth mentioning that the preceding examples can be easily generalized to generate the sequences of integers with missing blocks of zeros of any length in any base.

\section{Further Generalizations}\label{openq}

In this section we explore another possible generalization of Kimberling's set and its connections with morphisms and sequences of integers with missing blocks.  Consider the following example.
\begin{enumerate}
\item Let $1,2$ belong to $S$.
\item If $x$ belongs to $S$ then $3x$ belongs to $S$.
\item If $x$ belongs to $S$ and either $x=3k$ or $x=3k-1$ for some $k\in\mathbb{Z}$, then $3x-1$ and $3x-2$ belong to $S$.
\item Nothing else belongs to $S$.
\end{enumerate}
We say that $S$ is {\it conditionally self-generating}.  Arranging the elements of $S$ in increasing order gives the sequence
$$S=1,~2,~3,~4,~5,~6,~7,~8,~9,~12,~13,~14,~15,~16,~17,~18,~21,~22,~23,~\ldots$$
Letting $T:=S-1$, it is not hard to see that the integers in $T$ are those whose ternary representation does not contain the blocks 00 or 01.  Moreover, these representations are precisely the Lazy representations of the natural numbers with respect to sequence {\tt A001333},
$$1,~3,~7,~17,~41,~99,~239,\ldots,$$
which is given by the recurrence $a_0=1$, $a_1=3$, $a_n=2a_{n-1}+a_{n-2}$.  Reducing $S$ modulo 3 gives the sequence 
$$1,~2,~0,~1,~2,~0,~1,~2,~0,~0,~1,~2,~0,~1,~2,~0,~0,~1,~2,~0,~1,~2,~0,~\ldots$$
It is not hard to see that the proof of Theorem \ref{t1} applies to this $S$.  The method of Theorem \ref{t1} shows that the sequence $S$ reduced modulo 3 is the image by the map $a\rightarrow 1$, $b\rightarrow 2$, $c\rightarrow 0$, $d\rightarrow 1$, $e\rightarrow 2$ of the fixed point of the morphism $a\rightarrow abc$, $b\rightarrow dec$, $c\rightarrow dec$, $d\rightarrow c$, $e\rightarrow dbc$.
Reducing this last sequence modulo 2 gives
$$1,~0,~0,~1,~0,~0,~1,~0,~0,~0,~1,~0,~0,~1,~0,~0,~0,~1,~0,~0,~1,~0,~0,~\ldots$$
Again, it is not hard to see that the proof of Theorem \ref{t1} also applies when reducing modulo 3 and then again modulo 2.  This reduced sequence turns out to be the image of the fixed point of the morphism $a\rightarrow abb$, $b\rightarrow cbb$, and $c\rightarrow b$, under the coding $a\rightarrow 1$, $b\rightarrow 0$, $c\rightarrow 1$.
It is interesting to note that omitting the first term, this sequence is actually the fixed point of the morphism:
$$0\rightarrow 001~~\mbox{and}~~1 \rightarrow 0.$$
Finally, it is also not hard to see that the proof of Theorem \ref{t2} applies in this case, and the characteristic sequence of $S$ is 3-automatic, being the image of the fixed point of the morphism $a\rightarrow abb$, $b\rightarrow cbb$, $c\rightarrow ddb$, and $d\rightarrow ddd$, under the coding $a\rightarrow 1$, $b\rightarrow 1$, $c\rightarrow 1$, $d\rightarrow 0$.

\section{Open Questions} 

We close with some remaining questions.

\begin{itemize}
\item Do Theorems \ref{t1} and \ref{t2} hold when the generating
functions are characterized by ``mixed base'' rules?  For example, do
they hold when $F=\{2x,3x+1\}$?  Allouche, Shallit, and Skordev
\cite{shallit} commented that in this case the corresponding
characteristic sequence for $S$ is probably not $k$-automatic for any
$k$.  It seems likely that there is no analog of Lemmas \ref{lem_xRk}
and \ref{lem_taujtauk} in the mixed base case.  \item Do Theorems
\ref{t1} and \ref{t2} hold for more general families of functions?  The
proofs of Theorems \ref{t1} and \ref{t2} rely heavily on the fact that
if $f(x)=a^\ell x-b\in F$, then $0\leq b&lt;a^\ell$.  What if functions
were allowed for which $b\geq a^\ell$?

\end{itemize}

 
\begin{thebibliography}{10}

\bibitem{allouche} Jean-Paul Allouche and Jeffrey Shallit, {\it
Automatic Sequences: Theory, Applications, Generalizations}, Cambridge
University Press, Cambridge, 2003.

\bibitem{shallit} J.-P. Allouche, J. Shallit, G. Skordev, 
Self-generating sets, integers with missing blocks, and substitutions,
{\it Discrete Math.} {\bf 292} (2005), 1--15.

\bibitem{erdos} P. Erd{\H o}s, I. Jo\'o, V. Komornik,
Characterization of the unique expansions $1=\sum_{i=1}^\infty
q^{-n_i}$ and related problems, {\it Bull.\ Soc.\ Math.\ France}
{\bf 118} (1990), 377--390.

\bibitem{kimberling1} C. Kimberling, {\it A self-generating set and the
golden mean}, J. Int. Seq. {\bf 3} (2000) Article 00.2.8.
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL3/goldentext.html}{\tt http://www.cs.uwaterloo.ca/journals/JIS/VOL3/goldentext.html}

\bibitem{kimberling2} C. Kimberling, Affinely recursive sets and
orderings of languages, Discrete Math. {\bf 274} (2004), 147--159.

\bibitem{tichy} A. Petho and R.F. Tichy, On digit expansions with
respect to linear recurrences, {\it J. Number Theory}, {\bf 33} (1989),
243-256.

\bibitem{encyclopedia} N.J.A. Sloane, On-line Encyclopedia of Integer Sequences, published electronically at 
\newline
\href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/$\sim$njas/sequences/}

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
11B99; Secondary 11B85.

\noindent \emph{Keywords: } Kimberling sequence, self-generating set, morphism, characteristic sequence, automatic sequence, lazy expansion, integers with missing blocks

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000201}
\seqnum{A001333},
\seqnum{A003754},
\seqnum{A003796},
\seqnum{A028859},
\seqnum{A032924},
and
\seqnum{A052499}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 4 2006;
revised versions received September 14 2006; October 19 2006.
Published in {\it Journal of Integer Sequences}, December 30 2006.


\bigskip
\hrule
\bigskip

\noindent
Return to \href{http://www.math.uwaterloo.ca/JIS/}{Journal of Integer Sequences home page}.

\vskip .1in


\end{document}



                                                                                

</pre></body></html>