\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\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,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{subfigure}
\usepackage{vaucanson-g}
\newcommand{\f}{\varphi}
\newcommand{\rep}{\textrm{rep}}
\newcommand{\val}{\textrm{val}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\NP}{-\mathbb{N}}
\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/~njas/sequences/index.html?q=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf On the Recognizability of Self-Generating \\
\vskip .1in
Sets
}
\vskip 1cm
\large
Tomi K\"arki\footnote{Part of this research was done when the author was working in the Department of Mathematics at the University of Li{\`e}ge. The financial support from the Osk. Huttunen Foundation is gratefully acknowledged.}\\
University of Turku \\
Department of Mathematics\\
FI-20014 Turku \\
Finland\\
\href{mailto:topeka@utu.fi}{\tt topeka@utu.fi} \\
\ \\
Anne Lacroix and Michel Rigo\\
University of Li{\`e}ge \\
Department of Mathematics\\
Grande Traverse 12 (B37) \\
B-4000 Li{\`e}ge \\
Belgium\\
\href{mailto:A.Lacroix@ulg.ac.be}{\tt A.Lacroix@ulg.ac.be} \\
\href{mailto:M.Rigo@ulg.ac.be}{\tt M.Rigo@ulg.ac.be} \\
\end{center}
\vskip .2 in
\begin{abstract}
Let $I$ be a finite set of integers and $F$ be a finite set of
maps of the form $n\mapsto k_i\, n+\ell_i$ with integer
coefficients. For an integer base $k\ge 2$, we study the
$k$-recognizability of the minimal set $X$ of integers containing
$I$ and satisfying $\varphi(X)\subseteq X$ for all $\varphi\in F$.
We answer an open problem of Garth and Gouge by showing that $X$ is $k$-recognizable when the multiplicative constants $k_i$ are all powers of $k$ and additive constants $\ell_i$ are chosen freely.
Moreover, solving a conjecture of Allouche, Shallit and Skordev, we
prove under some technical conditions that if two of the constants
$k_i$ are multiplicatively independent, then $X$ is not
$k$-recognizable for any $k\ge 2$.
\end{abstract}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}
\section{Introduction}
In the general framework of numeration systems, the so-called
recognizable sets of integers have been extensively studied. Let $k\ge
2$ be an integer. The function $\rep_k\colon \mathbb{N} \to
\{0,\ldots,k-1\}^*$ maps a non-negative integer onto its $k$-ary
representation (without leading zeros). A set $X\subseteq\mathbb{N}$
is {\em $k$-recognizable} if the language $\rep_k(X)=\{\rep_k(n)\mid
n\in X\}$ is regular; see, for instance, \cite{BHMV}. A similar
definition can be given for the $k$-recognizable subsets of
$\mathbb{Z}$ using convenient conventions to represent negative
numbers, like adding a symbol ``$-$'' to the alphabet or considering
the positive and the negative elements separately. Since the seminal
work of Cobham \cite{Cob69}, it is well-known that the recognizability
of a set depends on the choice of the base $k$ --- except for the
ultimately periodic sets, i.e., the union of a finite set and a finite
number of infinite arithmetic progressions, which are easily seen to
be $k$-recognizable for all $k\ge 2$. The celebrated theorem of Cobham
can be stated as follows. Let $k,\ell\ge 2$ be two multiplicatively
independent bases, i.e., $\log k/\log \ell$ is irrational. If a set
$X\subseteq\mathbb{N}$ is both $k$-recognizable and
$\ell$-recognizable, then it is ultimately periodic.
Kimberling~\cite{Kim00} introduced the so-called \emph{self-generating} sets of
integers. They can be defined as follows. Let $r\ge 1$
and $G=\{\f_1,\f_2,\ldots,\f_r\}$ be a set of affine maps where
$\f_i\colon n\mapsto k_i\, n+\ell_i$ with $k_i,\ell_i \in
\mathbb{Z}$ and $2 \leq k_1 \leq k_2 \leq \cdots \leq k_r$. The set
generated by $G$ and a finite set of integers $I$ is the minimal
subset $X$ of $\mathbb{Z}$ containing $I$ and such that
$\f_i(X)\subseteq X$ for all $i=1,\ldots,r$. For any subset
$S\subseteq\mathbb{Z}$, we set $G(S):=\{\f(s) \mid s \in S, \f\in
G\}$, $G^0(S):=S$ and $G^{m+1}(S):=G(G^m(S))$ for all $m\ge 0$.
Otherwise stated, $X=\bigcup_{m\ge 0} G^m(I)$ is the set of all
integers $n$ such that there exist $m\ge 0$, $a \in I$ and a finite
sequence $(\f_{i_1},\f_{i_2},\ldots,\f_{i_m})$ of maps in $G$ such
that
\begin{equation}\label{eqDefSG}
n=\f_{i_m} \circ \f_{i_{m-1}}\circ \cdots \circ \f_{i_1}(a)
=\f_{i_m}(\f_{i_{m-1}}(\cdots \f_{i_1}(a) \cdots)).
\end{equation}
\begin{example}\label{exa:1}
Kimberling~\cite{Kim00} showed for $G=\{n\mapsto 2n,n\mapsto 4n-1\}$ and $I=\{1\}$ that the corresponding self-generating set
$$\mathcal{K}_1=\{1,2,3,4,6,7,8,11,12,14,15,16,\ldots\}$$ is
closely related to the Fibonacci word. This relationship will be developed in Section~\ref{secKF},
where with our techniques we obtain again Kimberling's original
result. Notice that for $I=\{0\}$,
we get a subset containing negative integers:
$\mathcal{K}_0=\{0,-1,-2,-4,-5,-8,-9,\ldots\}$. In particular, for
$I=\{0,1\}$, the corresponding self-generating set is
$\mathcal{K}_0\cup\mathcal{K}_1$.
\end{example}
Self-generating sets are also called \emph{affinely recursive}
in~\cite{Kim04} where the correspondence between words $i_1 i_2
\cdots i_m$ over the alphabet $\{1,2,\ldots,r\}$ and integers
$\f_{i_m}(\f_{i_{m-1}}(\cdots \f_{i_1}(1) \cdots))$ is studied. For
example, conditions under which this correspondence is one-to-one
are given, which in turn implies that the natural ordering of the
integers induces an ordering on the set of non-empty words over
$\{1,2,\ldots,r\}$ providing a kind of abstract numeration system
\cite{LR}. Note that in the definition of affinely recursive sets~\cite{Kim04}
the set of generating functions~$G$ can be an
infinite set of maps of the form $\f_i\colon n\mapsto k_i\,
n+\ell_i$, where $k_i,\ell_i \in \mathbb{N}$.
Allouche, Shallit and Skordev \cite{AllSha05} consider a general framework for self-generating sets.
The $k$-ary representations of the elements of some
self-generating sets are related to words over
$\Sigma_k=\{0,1,\ldots,k-1\}$ where some fixed block of digits is
missing. As an illustration, one can notice that the set
$\mathcal{K}_1-1=\{0,1,2,3,5,6,7,10,\ldots\}$ introduced in
Example~\ref{exa:1} consists of all integers whose binary expansion
does not contain ``$00$'' as factor. Recall that the {\em
characteristic sequence} $(\mathbf{c}_X(n))_{n\geq 0}$ of a set
$X\subseteq\mathbb{N}$ is defined by $\mathbf{c}_X(n)=1$, if $n \in
X$ and $\mathbf{c}_X(n)=0$, otherwise. In particular, $X$ is
$k$-recognizable (resp., ultimately periodic) if and only if
$(\mathbf{c}_X(n))_{n\geq 0}$ is $k$-automatic (resp., an ultimately
periodic infinite word). Self-generating sets are consequently
studied from the point of view of automatic and morphic sequences as
well as in relation to non-standard numeration systems; for the
definitions and further information, see~\cite{AllSha03,Lot02}.
Moreover, Allouche, Shallit and Skordev ask the following question:
\emph{Under what conditions is the characteristic sequence of a self-generating
set $k$-automatic?} They also present the following conjecture.
\begin{conjecture}\label{conj}
{\em With ``mixed base'' rules, such as $G=\{n\mapsto
2n+1,n\mapsto 3n\}$, the set generated from $I=\{1\}$ is not
$k$-recognizable for any integer base $k\ge 2$.}
\end{conjecture}
Let us fix the notation once and for all.
\begin{definition}\label{def}
In this paper, instead of considering a set $G$ of maps as
described above, we will moreover consider the extended set of
$r+1\ge 2$ maps
$$F=G\cup\{\f_0\}=\{\f_0,\f_1,\ldots,\f_r\}$$
where $\f_0\colon n \mapsto n$ and $\f_i\colon n\mapsto k_i\,
n+\ell_i$ with $k_i,\ell_i \in \mathbb{Z}$ and $$2 \leq k_1
\leq k_2 \leq \cdots \leq k_r.$$ Having the identity function $\f_0$
at our disposal, for any set $S\subseteq\mathbb{Z}$, we have
$F^m(S)\subseteq F^{m+1}(S)$. Therefore, for any finite set $I$ of
integers, the set
$$F^\omega(I):=\lim_{m\to\infty}F^m(I)$$ is exactly the {\em
self-generating set} with respect to $G$ and $I$.
\end{definition}
This article is an extended version of
our presentation given in the MFCS conference 2009
\cite{KLR}. The content of the paper is the following. In Section~\ref{secRed}
we give some simple observations on self-generating sets.
For example, if we add to $F$ an extra map $\psi\colon n\mapsto n+\ell$ with $\ell\neq 0$,
then the corresponding self-generating set $F^\omega(I)$ is
ultimately periodic and therefore $k$-recognizable for all $k\ge
2$. We also show that we can restrict our considerations to subsets
of $\mathbb{N}$ and assume that all additive constants $\ell_i$ for the maps $\f_i \in F$ are non-negative.
In sections~\ref{secMD} and~\ref{secKF} we consider the
multiplicatively dependent case. The results are based on Frougny's
normalization transducer; see, e.g., Chapter 7 in~\cite{Lot02}. If
all multiplicative constants $k_i$ are pairwise
multiplicatively dependent, then we give a general method to build
a finite automaton recognizing $\rep_k(F^\omega(I))$ for any $k$
that is multiplicatively dependent on every $k_i$. This allows us to
generalize a recognizability result of Garth and Gouge~\cite{garth}. Moreover, a new proof
of the relation between the Kimberling set $\mathcal{K}_1$ and the
infinite Fibonacci word is given in Section~\ref{secKF}; for other proofs,
see~\cite{AllSha05,Kim00}.
In the multiplicatively independent case of Section~\ref{secMI} we
study differences and ratios of consecutive elements in the
considered self-generating set. The results rely on a classical gap
theorem; see Theorem~\ref{thGap}. We prove that if there exist $i,j$
such that $k_i$ and $k_j$ are
multiplicatively independent and if $\sum_{i=1}^r k_i^{-1}<1$,
then $F^\omega(I)$ is not $k$-recognizable for any $k\ge 2$.
In particular, this condition always holds for sets
$F$ where $r=2$ and $k_11$ satisfying
$f_k=b$. This implies that $\phi(f_0\cdots f_k)=uf_{l-1}f_l=udb$
and, by~\eqref{eqLength} and by the assumption, we have
\begin{equation}\label{eqInduction}
\mu(s_0\cdots
s_k)=udbs_{l+1}s_{l+2}s_{l+3}s_{l+4}s_{l+5}=udb.dbc.db,
\end{equation}
where $s_{l+4}s_{l+5}=\mu(s_k)=\mu(b)$ and
$s_{l+1}s_{l+2}s_{l+3}=\mu(s_{k-1})=\mu(d)$, since $s_k=b$ must be
preceded by~$d$ if $k>1$. We have two possibilities, either
$f_{k+1}f_{k+2}=db$ or $f_{k+1}f_{k+2}f_{k+3}=cdb$.
If $f_{k+1}f_{k+2}=db$, then $\phi(f_0\cdots
f_{k+2})=udb\phi(f_{k+1})\phi(f_{k+2})=udb.dbc.db$ and, by comparing
this to~\eqref{eqInduction}, we conclude that the claim $s_n=f_n$
holds for $1\leq n \leq l+5$.
Assume next that $f_{k+1}f_{k+2}f_{k+3}=cdb$. Now $f_1\cdots
f_{k+3}=s_1\cdots s_{k+3}$, since we must have $k+3\leq l$. Hence,
we obtain
\begin{eqnarray*}
\phi(f_0\cdots f_{k+3})&=&udb.dbc.dbc.db,\\
\mu(s_0\cdots s_{k+3})&=&udb.dbc.db.cdb.dbc.db,
\end{eqnarray*}
which implies that $s_n=f_n$ for $1\leq n \leq l+8$.
Since in the first case $f_{k+2}=b$ and in the second case
$f_{k+3}=b$, we may proceed by induction. This concludes the proof,
since the claim clearly holds for small values of $n\geq1$.
\end{proof}
\section{Multiplicatively Independent Case}\label{secMI}
In this section our aim is to show that
$F^\omega(I)\subseteq\mathbb{N}$ given in Definition~\ref{def} is
not recognizable in any base $k\ge 2$ provided that $\sum_{i=1}^r
k_i^{-1}<1$ and that there are at least two multiplicatively
independent coefficients $k_i$. For the proof, we introduce the
following notation. Let $X=\{x_01$ or $D_X<\infty$.
\end{theorem}
Note that $D_X<\infty$ means that $X$ is \emph{syndetic}, i.e., there
exists a constant $C$ such that the gap $x_{i+1}-x_{i}$ between any
two consecutive elements $x_i,x_{i+1}$ in $X$ is bounded by $C$. Let
us first show that if $\sum_{i=1}^r k_i^{-1}<1$, then the set
$F^\omega(I)$ given in Definition~\ref{def} contains arbitrarily large
gaps.
\begin{theorem}\label{thNotSyn}
Let $X=F^\omega(I)$ be a self-generating subset of $\mathbb{N}$
given in Definition~\ref{def}. If $\sum_{i=1}^r k_i^{-1}<1$, then
$X$ is not syndetic.
\end{theorem}
\begin{proof} Let $n\ge 1$ and $K=k_1k_2 \cdots k_r$.
Let $g=g_1 \circ g_2 \circ \cdots \circ g_n$ be a composite
function, where $g_j$ belongs to $G=\{\f_1,\f_2, \ldots, \f_r\}$ for
every $j=1,2,\ldots, n$ and $g_j = \f_i$ for exactly $n_i$
integers $j\in\{1,\ldots,n\}$. Note that $n_1+n_2\cdots+n_r=n$. By
definition, we have $g(x)=k_1^{n_1}k_2^{n_2}\cdots k_r^{n_r} x +
c_g$, where $c_g$ is some constant depending on $g$. Since
$k_1^{n_1}k_2^{n_2}\cdots k_r^{n_r}$ divides $K^n$, we get
$$\#\{g(x)\bmod{K^n}\mid x\in\mathbb{Z}\}=k_1^{n-n_1}k_2^{n-n_2}\cdots k_r^{n-n_r}.$$
Recall that $F=G \cup \{\f_0\}$, where $\f_0$ denotes the identity function.
The set $F^{n}(I)$ contains exactly the integers obtained by at most
$n$ applications of maps in $G$. For any interval of integers
$[\![N,N+K^n-1]\!]$ where $N>\max F^{n}(I)$, the elements of~$X$
belonging to this interval have been obtained by applying at least
$n+1$ maps. Hence, in the interval $[\![N,N+K^n-1]\!]$ there can be
at most $k_1^{n-n_1}k_2^{n-n_2}\cdots k_r^{n-n_r}$ integers $x \in
X$ such that the last $n$ maps which produce $x$ correspond to the
composite function~$g$, i.e., such that there exists $y\in X$
satisfying $g(y)=x$. For fixed numbers $n_i$, $i=1,2,\ldots, r$,
there are $n!/(n_1!n_2!\cdots n_r!)$ functions $g$ of the type
described above. Thus, the number of integers in $X \cap
[\![N,N+K^n-1]\!]$ for any large enough $N$ is at most
\[
\sum_{n_1,n_2,\ldots,n_r} \left ( \frac{n!}{n_1!n_2!\cdots n_r!}
\right ) k_1^{n-n_1}k_2^{n-n_2}\cdots k_r^{n-n_r}=K^n \left (
\frac{1}{k_1}+\frac{1}{k_2}+ \cdots + \frac{1}{k_r} \right )^n
\]
where the sum is over $n_1,n_2,\ldots,n_r \geq 0$ satisfying
$n_1+n_2+\cdots+n_r=n$.
Hence, the biggest gap $x_{i+1}-x_i$ between
two consecutive elements $x_i, x_{i+1}\in X$ in the interval
$[\![N,N+K^n-1]\!]$ is at least
\[
d(n)=\frac{K^n}{K^n \left ( \frac{1}{k_1}+\frac{1}{k_2}+ \cdots +
\frac{1}{k_r} \right )^n} = \left ( \frac{1}{k_1}+\frac{1}{k_2}+
\cdots + \frac{1}{k_r} \right )^{-n}.
\]
Since $\sum_{i=1}^r k_i^{-1}<1$, the function $d(n)$ tends to infinity
as $n$ tends to infinity. This means that there are arbitrarily large
gaps in $X$. In other words, the self-generating set $X$ is not
syndetic.
\end{proof}
Before showing that $R_X=1$ let us first recall the density property
of multiplicatively independent integers. A set $S$ is \emph{dense} in an
interval $I \subseteq \mathbb{R}$ if every subinterval of $I$ contains an element of $S$.
\begin{theorem}\label{thDense}
If $k,\ell\ge 2$ are multiplicatively independent, $\left \{
k^p/\ell^q \mid p,q \geq 0 \right \}$ is dense in
$[0,\infty)$.
\end{theorem}
This is a consequence of Kronecker's theorem, which states that
for any irrational number $\theta$ the sequence
$(\{n\theta\})_{n\geq0}$ is dense in the interval $[0,1)$. Here
$\{x\}$ denotes the fractional part of the real number $x$. The proof
of Kronecker's theorem as well as the proof of Theorem~\ref{thDense}
can be found in~\cite[Section 2.5]{AllSha03} or \cite{HW}. As an easy
consequence of the previous theorem, we obtain the following result.
\begin{corollary}\label{corDense}
Let $\alpha>0$ and $\beta$ be two real numbers. If $k$ and $\ell$
are multiplicatively independent, then the set $\left \{ (\alpha
k^p+\beta)/\ell^q \mid p,q \geq 0 \right \} $ is
dense in $[0,\infty)$.
\end{corollary}
\begin{proof}
We show how to get arbitrarily close to any positive real number
$x$. Let $\epsilon >0$. By Theorem~\ref{thDense}, there exist
integers $p$ and $q$ such that
\[
\left | \frac{x}{\alpha}-\frac{k^p}{\ell^q} \right | <
\frac{\epsilon}{2 \alpha} \quad \textrm{and} \quad \left |
\frac{\beta}{\ell^q} \right |< \frac{\epsilon}{2} .
\]
Hence, it follows that
\[
\left | x - \frac{\alpha k^p+\beta}{\ell^q} \right | \leq \left |
x-\frac{\alpha k^p}{\ell^q} \right | + \left | \frac{\beta}{\ell^q}
\right |< \frac{\epsilon}{2 \alpha} \alpha +
\frac{\epsilon}{2}=\epsilon.
\]
\end{proof}
Let us next consider the ratio $R_X$ of a self-generating set $X$.
\begin{theorem}\label{thRatio}
For any self-generating set $X=F^\omega(I) \subseteq \mathbb{N}$ given in
Definition~\ref{def} where $k_i$ and $k_j$ are multiplicatively
independent for some $i$ and $j$, we have $R_X=1$.
\end{theorem}
\begin{proof}
Without loss of generality, we may assume that
$F=\{\f_0,\f_1,\f_2\}$, where $\f_1 \colon n\mapsto k_1\, n+\ell_1$,
$\f_2 \colon n\mapsto k_2\, n+\ell_2$, and $k_1$ and $k_2$ are
multiplicatively independent. Namely, for $F \subseteq F'$, it is
obvious that $F^\omega(I) \subseteq F'^\omega(I)$ and
consequently, $R_{F^\omega(I)}=1$ implies $R_{F'^\omega(I)}=1$. By
Lemma~\ref{lmPos}, we may also assume that $\ell_1$ and $\ell_2$
are non-negative.
Let $a \in X$ be a positive integer and set $X_n:=X \cap
[\f_1^{n-1}(a),\f_1^n(a)]$ for all $n>0$. Note that $\cup_{n \in
\mathbb{N}}X_n=X\cap[a,\infty)$. Recall that
$X=\{x_0q$, the difference $x_{j+1}-x_j$ of any two consecutive elements
$x_j$, $x_{j+1}$ of $X$ in the interval
$[\f_1^{t}(x_{i}),\f_1^{t}(x_{i+1})]$ is at most
\begin{align*}
&\max\{\f_1^{t-q}(\f_1^q(x_{i+1}))-\f_1^{t-q}(\f_2^p(a)),\f_1^{t-q}(\f_2^p(a))-\f_1^{t-q}(\f_1^q(x_{i}))\}\\
&\qquad \leq\max\{\f_1^t(x_{i+1})-\f_1^{t-q}(c),\f_1^{t-q}(d)-\f_1^t(x_i)\} =\frac{3}{4}k_1^t(x_{i+1}-x_i)+b_1k_1^{t-q}.
\end{align*}
Thus, the ratio $(x_{j+1}-x_j)/x_j$ is at most
\begin{equation}\label{eqUB}
\frac{3\, k_1^t(x_{i+1}-x_i)}{4\, \f_1^t(x_i)}+\frac{b_1k_1^{t-q}}
{\f_1^t(x_i)}=\frac{3\, k_1^t(x_{i+1}-x_i)}{4\,
\f_1^t(x_i)}+\frac{1}{k_1^q} \frac{b_1k_1^t}{(x_i+b_1)k_1^t-b_1}.
\end{equation}
The latter term in this sum can be taken as small as possible for
$q$ and $t$ large enough ($1/k_1^q$ tends to $0$ and the other
factor tends to the constant $b_1/(x_i+b_1)$). In particular, for
$q$ and $t$ large enough, we have
$$\frac{b_1k_1^{t-q}}{\f_1^t(x_i)}<\frac{x_{i+1}-x_i}{12x_i}.$$
Moreover, we have
$$\frac{3\, k_1^t(x_{i+1}-x_i)}{4\, \f_1^t(x_i)}=
\frac{3\, (x_{i+1}-x_i)}{4\, (x_i+b_1-b_1/k_1^t)}<\frac{3\,
(x_{i+1}-x_i)}{4\, x_i} <\frac{10\, (x_{i+1}-x_i)}{12\, x_i}.$$
Thus, by~\eqref{eqUB}, we obtain
\begin{equation}\label{eqAppr}
\frac{x_{j+1}-x_j}{x_j}<\frac{11\, (x_{i+1}-x_i)}{12\, x_i}.
\end{equation}
Since the above holds for any consecutive elements $x_i$ and $x_{i+1}$
in $X_m$ and there are only finitely many such pairs, we conclude that
there exists an integer $N_1$ such that \eqref{eqAppr} holds for any
consecutive elements $x_j,x_{j+1} \in X_n$ where $n\geq N_1$. Hence,
we obtain $r_{n}<\frac{11}{12}\, r_m$ for every $n\geq N_1$. Moreover,
by repeating this procedure, we conclude that there exists an integer
$N_k$ such that
\[
r_{n}<\left( \frac{11}{12} \right)^k r_m
\]
for every $n\geq N_k$. This implies that $\limsup_{n \rightarrow \infty}r_n=0$ and, consequently,
\[
R_X=1+\limsup_{n \rightarrow \infty}r_n=1.
\]
\end{proof}
Our main result is a straightforward consequence of the previous theorems.
\begin{theorem}\label{thMain}
Let $X=F^\omega(I) \subseteq \mathbb{N}$ be given in Definition~\ref{def}. If
$\sum_{t=1}^r k_t^{-1}<1$ and there exist $i,j$ such that $k_i$
and $k_j$ are multiplicatively independent, then $F^\omega(I)$ is
not $k$-recognizable for any integer base $k\ge 2$.
\end{theorem}
\begin{proof}
Let $X=F^\omega(I)$ satisfy the assumptions of the theorem. By
Theorem~\ref{thNotSyn}, we have $D_X=\infty$ and, by
Theorem~\ref{thRatio}, we have $R_X=1$. Thus, Theorem~\ref{thGap}
implies that $X$ is not $k$-recognizable for any $k\geq 2$.
\end{proof}
As a corollary, we have solved the conjecture of Allouche, Shallit and Skordev~\cite{AllSha05}.
\begin{corollary}
Let $F=\{\f_0,n\mapsto k_1\, n+\ell_1,n\mapsto k_2\, n+\ell_2\}$,
where $k_1$ and $k_2$ are multiplicatively independent. Then any
infinite self-generating set~$F^\omega(I)$ given in
Definition~\ref{def} is not $k$-recognizable for any $k\ge 2$.
\end{corollary}
\begin{proof}
This follows directly from Theorem~\ref{thMain}. Namely, if $k_1$
and $k_2$ are multiplicatively independent, then $k_1\geq 2$ and
$k_2\geq3$ and $k_1^{-1}+k_2^{-1}\leq 1/2 + 1/3 = 5/6 <1$.
\end{proof}
The condition $\sum_{t=1}^r k_t^{-1}<1$ is not needed in a very
special case of self-generating sets where $\ell_i=0$ for every
$i=1,2,\ldots,r$. This situation is related to so-called $y$-smooth
numbers. An integer is \emph{$y$-smooth} if it has no prime factors
greater than $y$. For more on smooth numbers, see, e.g.,~\cite{Gra08}.
\begin{theorem}
Let $X=F^\omega(I)$ be given in Definition~\ref{def}. If $\ell_i=0$
for every $i=1,2,\ldots,r$ and there exist $i,j$ such that $k_i$ and
$k_j$ are multiplicatively independent, then $F^\omega(I)$ is not
$k$-recognizable for any integer base $k\ge 2$. In particular, for $y\geq 3$, the set
of $y$-smooth numbers is not $k$-recognizable for any $k\geq 2$.
\end{theorem}
\begin{proof}
Assume that $\f_i\colon n \mapsto k_in$ for $i=1,2,\ldots,r$ and
denote $X=F^\omega(I)$. Let $x\geq 2$ be an integer and consider $n
\in X \cap [0,x]$. By the definition of~$X$, the integer~$n$
must be of the form $k_1^{e_1} \cdots k_r^{e_r}a$, where $a \in I$.
Since the exponent $e_i$ is at most $\log_2(x)$ for every
$i=1,2,\ldots,r$, the number of integers in $X \cap [0,x]$ is
at most $(1+\log_2(x))^r|I|=O(\log^r (x))$. It follows that $x/|X
\cap [0,x]|$ tends to infinity when $x$ tends to infinity.
This implies that $F^\omega(I)$ cannot be syndetic, i.e., $D_X =
\infty$. If there are two multiplicatively independent constants
$k_1$ and $k_2$, then $R_X=1$ by Theorem~\ref{thRatio}. Hence, by
Theorem~\ref{thGap}, the self-generating set $X$ is not
$k$-recognizable for any $k\geq2$. The second claim follows, since
the set of $y$-smooth numbers can be represented as a
self-generating set $F^\omega(I)$, where $I=\{1\}$ and $\f_i\colon n
\mapsto p_in$ for $i=1,2,\ldots,r$. Here $p_i$ is the $i$th smallest
prime and $p_r$ is the largest prime less than or equal to~$y$.
\end{proof}
\section{Acknowledgments}
We thank the anonymous referees of the MFCS version of this paper for
suggesting improvements in the presentation of this paper. In
particular, it is one of the referees who pointed out a possible
connection with smooth numbers.
\begin{thebibliography}{50}
\bibitem{AllSha03} J.-P. Allouche, J. Shallit, {\em Automatic
Sequences: Theory, Applications, Generalizations}, Cambridge
University Press, 2003.
\bibitem{AllSha05} J.-P. Allouche, J. Shallit, G. Skordev,
Self-generating sets, integers with missing blocks, and
substitutions, {\em Discrete Math.} {\bf 292} (2005), 1--15.
\bibitem{BHMV} V. Bruy\`ere, G. Hansel, C. Michaux, R. Villemaire,
Logic and $p$-recognizable sets of integers, {\em Bull. Belg.
Math. Soc.} {\bf 1} (1994), 191--238.
\bibitem{Cob68b} A. Cobham, On the Hartmanis-Stearns problem for a class of tag machines, in \emph{IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory}, 1968, pp. 51--60. Also appeared as IBM Research Technical Report {\bf RC-2178}, August 23, 1968.
\bibitem{Cob69} A. Cobham, On the base-dependence of sets of numbers
recognizable by finite automata, {\em Math. Systems Theory} {\bf
3} (1969), 186--192.
\bibitem{cob1972} A. Cobham, Uniform tag sequences, {\em Math.
Systems Theory} {\bf 6} (1972), 164--192.
\bibitem{Eil74} S. Eilenberg, {\em Automata, Languages, and
Machines}, Vol. A., Pure and Applied Mathematics, Vol. {\bf 58},
Academic Press, 1974.
\bibitem{Fro} C. Frougny, Representations of numbers and finite
automata, {\em Math. Systems Theory} {\bf 25} (1992), 37--60.
\bibitem{garth} D. Garth, A. Gouge, Affinely self-generating sets
and morphisms, {\em J. Integer Seq.} {\bf 10} (2007), Article 07.1.5.
\bibitem{Gra08} A. Granville, Smooth numbers: computational number theory and beyond, in
J. P. Buhler, P. Stevenhagen, eds., \emph{Algorithmic number theory: lattices, number fields, curves and cryptography}, Math. Sci. Res. Inst. Publ. {\bf 44}, Cambridge University Press, 2008, pp. 267--323.
\bibitem{HW} G. H. Hardy, E. M. Wright, {\em Introduction to the
Theory of Numbers}, Oxford University Press, 1985.
\bibitem{KLR} T. K\"arki, A. Lacroix, M. Rigo, On the recognizability of self-generating sets, in R. Kr\'alovi\v c, D. Niwi\'nski, eds., \emph{Proceedings of the 34st International Symposium on Mathematical Foundations of Computer Science, Bratislava, August 24 - 28, 2009}, Lecture Notes in Comput.
Sci. {\bf 5734} (2009), 525--536.
\bibitem{Kim00} C. Kimberling, A self-generating set and the golden
mean, {\em J. Integer Seq.} {\bf 3} (2000), Article 00.2.8.
\bibitem{Kim04} C. Kimberling, Affinely recursive sets and orderings
of languages, {\em Discrete Math.} {\bf 274} (2004), 147--159.
\bibitem{LR} P. B. A. Lecomte, M. Rigo, Numeration systems on a regular
language, {\em Theory Comput. Syst.} {\bf 34} (2001), 27--44.
\bibitem{Lot02} M. Lothaire, {\em Algebraic Combinatorics on Words},
Encyclopedia of Mathematics and its Applications, {\bf 90},
Cambridge University Press, 2002.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 68Q45; Secondary 68R15, 11B85.
\noindent \emph{Keywords: }
self-generating set, recognizability, numeration systems, multiplicatively independent integers, Fibonacci word.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences \seqnum{A000045}, \seqnum{A000201},
\seqnum{A001950}, \seqnum{A003754}, \seqnum{A003849}, \seqnum{A052499}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received November 16 2009;
revised version received January 21 2010.
Published in {\it Journal of Integer Sequences}, January 27 2010.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}