\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{tikz}
\usetikzlibrary{arrows,automata}
\usetikzlibrary{matrix,arrows}
\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}
\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}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{assumption}[theorem]{Assumption}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
Symbolic Dynamics of $(-\beta)$-Expansions
}
\vskip 1cm
\large
K. Dajani and S. D. Ramawadh\\
Department of Mathematics\\
Utrecht University\\
Postbus 80.010 \\
3508 TA Utrecht\\
The Netherlands \\
\href{mailto:k.dajani1@uu.nl}{\tt k.dajani1@uu.nl} \\
\href{mailto:S.D.Ramawadh@uu.nl}{\tt S.D.Ramawadh@uu.nl}\\
\end{center}
\vskip .2 in
\newcommand{\ba}{\begin{eqnarray}}
\newcommand{\ea}{\end{eqnarray}}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
%\newcommand{\cal}{\mathcal}
\newcommand{\T}{T_{-\beta}}
\newcommand{\Tl}{T_{L,-\beta}}
\newcommand{\Tr}{T_{R,-\beta}}
\newcommand{\dn}{d_{-\beta}}
\newcommand{\dl}{d_{L,-\beta}}
\newcommand{\dr}{d_{R,-\beta}}
\newcommand{\dls}{d^*_{L,-\beta}}
\newcommand{\drs}{d^*_{R,-\beta}}
\newcommand{\Sn}{S_{-\beta}}
\newcommand{\Sl}{S_{L,-\beta}}
\newcommand{\Sr}{S_{R,-\beta}}
\newcommand{\vectwo}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\newcommand{\vecthree}[3]{\begin{array}{c}#1\\#2\\#3\end{array}}
\begin{abstract}
We study shift spaces associated with a family of transformations
generating expansions in base $-\beta$, with $\beta>1$. We give a
complete characterization when these shift spaces are sofic or even
shifts of finite type.
\end{abstract}
\section{Introduction}
In 1957, R\'{e}nyi studied the expansions of numbers in base $\beta>1$.
He only considered the numbers in $[0,1)$, and only considered one
specific rule, the $\beta$-transformation, with which we could find
these expansions \cite{Ren57}. Many other mathematicians have studied
these expansions since then, of which the most famous result is a paper
by Parry \cite{Par60}, in which he gave quite an extensive description
of both ergodic and symbolic properties of the $\beta$-transformation
posed by R\'{e}nyi. Later on several others looked at other types of
$\beta$-expansions. Erd\H{o}s \cite{EJ91}, for example, studied lazy
$\beta$-expansions (the opposite, the greedy $\beta$-expansions were
studied by R\'{e}nyi). Dajani and Kraaikamp studied a whole class of
$\beta$-expansions \cite{DK03} and also random $\beta$-expansions
\cite{DK04,DV05}.
In 2009, Ito and Sadahiro \cite{IS09} studied $(-\beta)$-expansions in base $-\beta$, $\beta>1$. They introduced a transformation, the $(-\beta)$-transformation, which allowed them to find an expansion of the form
\ba\label{eq:1}
x = \sum_{n=1}^\infty \frac{x_n}{(-\beta)^n}, & & x_n\in\{0,1,\ldots,\lfloor\beta\rfloor\}
\ea
of any number $x\in I:=\left[-\frac{\beta}{\beta+1},\frac{1}{\beta+1}\right)$. After having introduced this dynamical system, they continued their study of these expansions by introducing an order on the set of expansions and studying the resulting $(-\beta)$-shift. This approach was later continued by Frougny and Lai \cite{FL09}, who gave a detailed description of the symbolic properties of the $(-\beta)$-shift. Recently, others have considered different transformations generating $(-\beta)$-expansions. Dombek, Mas\'{a}kov\'{a} and Pelantov\'{a}
\cite{DMP11} considered a generalization of the aforementioned approach. Dajani and Kalle \cite{DK11}, took an even more general approach by studying a whole class of transformations generating $(-\beta)$-expansions for $1<\beta<2$.
The aim of this paper is to study shift spaces associated with various transformations generating $(-\beta)$-expansions and to give a complete characterization when these shift spaces are sofic or shifts of finite type.
\section{The dynamical system}
Let $\beta>1$ be given. The set of numbers $x\in\RR$ that satisfy \eqref{eq:1} for certain coefficients $x_n\in\{0,1,\ldots,\lfloor\beta\rfloor\}$ is contained in the interval
\bea
I_{-\beta} := \left[-\frac{\beta\cdot\lfloor\beta\rfloor}{\beta^2-1},\ \frac{\lfloor\beta\rfloor}{\beta^2-1}\right].
\eea
We call the set ${\cal A}:=\{0,1,\ldots,\lfloor\beta\rfloor\}$ the \emph{canonical alphabet}. If $x$ has an expansion of the form \eqref{eq:1}, then we may refer to the right-hand side of \eqref{eq:1} as \emph{a $(-\beta)$-expansion of x}. Moreover, we can refer to the digits of the expansion explicitly as follows:
\bea
\dn(x) := (x_1,x_2,\ldots) & \textrm{and} & \dn(x,n) := x_n.
\eea
We may also write $x=(.x_1x_2\cdots)_{-\beta}$. Moreover, if a part is periodic we can show this by overlining it. For example, $(1,\overline{0,2})=(1,0,2,0,2,0,2,\ldots)$. If a sequence consists of only a periodic part, we will call it \emph{purely periodic}. If it consists of a pre-periodic and a periodic part, we will call it \emph{eventually periodic}. Now, suppose that $x\in I_{-\beta}$ with expansion $\dn(x)=(x_1,x_2,\ldots)$. It follows that
\bea
-\beta x-x_1 = \sum_{n=1}^\infty \frac{x_{n+1}}{(-\beta)^n}.
\eea
In particular, we see that $-\beta x-x_1\in I_{-\beta}$ as the right-hand side is another $(-\beta)$-expansion. Therefore, one should look at the family of maps $-\beta x-a$, $a\in{\cal A}$, on the interval $I_{-\beta}$. Figure \ref{fig:1} shows what happens for a specific choice for $\beta$.
\begin{figure}
\centering
\begin{tikzpicture}[scale=2.5]
\draw[->] (-1.2,0) -- (0.8,0);
\draw[->] (0,-1.2) -- (0,0.8);
\draw[black!50!white] (0,-1) -- (0,0.62);
\draw[black!50!white] (0.62,0) -- (-1,0);
\draw[dashed] (-0.38,-1) -- (-0.38,0.62);
\draw (-1,-1) rectangle (0.62,0.62);
\draw[color=blue,thick] (-1,0.62) -- (0,-1);
\draw[color=blue,thick] (-0.38,0.62) -- (0.62,-1);
\draw (-1,-1) node [below] {$-1$} -- (-0.38,-1) node [below] {$-\frac{1}{\beta^2}$} -- (0.62,-1) node [below] {$\frac{1}{\beta}$};
\end{tikzpicture}
\caption{The maps $-\beta x-a$ with $a\in{\cal A}$ on $I_{-\beta}$ for $\beta=\frac{1+\sqrt{5}}{2}$.\label{fig:1}}
\end{figure}
Notice that there is a small subinterval for which there is more than one possibility for $a$ such that $-\beta x-a$ remains in $I_{-\beta}$ for all points in this subinterval. Such a subinterval will be called a \emph{choice region}. Other subintervals, where there is only one choice for $a\in{\cal A}$, are called \emph{uniqueness regions}. Note that this behaviour is not restricted to this specific base $-\beta$; in fact, it happens for all non-integer base $-\beta$. This is a consequence of our alphabet ${\cal A}$.
In any case, we need to specify a function $d:I_{-\beta}\to{\cal A}$, the \emph{digit function}, such that for any $x\in I_{-\beta}$ it follows that also $-\beta x-d(x)\in I_{-\beta}$. Henceforth, we will work with the following assumptions:
\begin{assumption}\label{ass:2.1}
The digit function $d:I_{-\beta}\to{\cal A}$ satisfies the following properties:
\begin{enumerate}
\item[i.] $d(x)$ is such that $x\in I_{-\beta}\Rightarrow -\beta x-d(x)\in I_{-\beta}$,
\item[ii.] $d$ is either left- or right-continuous everywhere,
\item[iii.] $d$ is nonincreasing on $I_{-\beta}$.
\end{enumerate}
\end{assumption}
The idea behind the assumptions on the digit function is that it divides the interval $I_{-\beta}$ into at most $\lfloor\beta\rfloor+1$ smaller intervals, where the intervals are all either left- or right-closed and each of the intervals has a digit from the alphabet ${\cal A}$ assigned to them. These digits are assigned in such a way that, from left to right, these digits are decreasing. This implies that all digits of ${\cal A}$ are actually used.
Property i of Assumption 2.1 is worth considering more carefully. As a consequence of our choice of alphabet ${\cal A}$, we have that for any $\beta>1$ and any $x\in I_{-\beta}$ there is at least one $a\in{\cal A}$ such that $-\beta x-a\in I_{-\beta}$. To see why, fix $x\in I_{-\beta}$ and consider the set $S(x)=\left\{-\beta x-a:\ a\in{\cal A}\right\}$. The smallest element of $S(x)$ cannot be greater than $\frac{\lfloor\beta\rfloor}{\beta^2-1}$ and the largest element of $S(x)$ cannot be smaller than $-\frac{\beta\cdot\lfloor\beta\rfloor}{\beta^2-1}$. Moreover, $I_{-\beta}$ has length strictly greater than $1$, whereas the difference between two consecutive digits in ${\cal A}$ is $1$. These observations imply that $S(x)\cap I_{-\beta}\neq\emptyset$.
The points where $d$ is discontinuous are called \emph{cut points}. The cut points always lie in choice regions, and the cut points divide these regions into smaller regions on which the digit function dictates which map $-\beta x-a$ to choose.
Using this digit function, we can finally pose our dynamical system. We define, for a given digit function $d$, the map
\bea
\T(x) & := & -\beta x-d(x)
\eea
on $I_{-\beta}$. If we want to emphasize whether the underlying digit function is left- or right-continuous, we may write $\Tl(x)$ and $\Tr(x)$ respectively.
\begin{proposition}\label{prop:2.2}
Let $x\in I_{-\beta}$ be arbitrary and let $x_n := d\left(\T^{n-1}(x)\right)$. Then we have $x=(.x_1x_2\ldots)_{-\beta}$.
\end{proposition}
\begin{proof}
We show, by induction on $n$, that for all $n\geq 1$ we have
\bea
x = \frac{\T^n(x)}{(-\beta)^n} + \sum_{k=1}^n \frac{x_k}{(-\beta)^k}.
\eea
By definition, we have $\T(x)=-\beta x-x_1$, which in turn is equivalent to $x=\frac{\T(x)}{-\beta}+\frac{x_1}{-\beta}$. Hence, the statement holds for $n=1$.
Now assume that the statement is true for some positive integer $m-1$. Since we know that $\T^m(x)=-\beta\T^{m-1}(x)-x_m$, we also have
\bea
\T^{m-1}(x) = \frac{x_m}{-\beta}+\frac{T^m(x)}{-\beta}
\eea
and hence
\bea
x &=& \frac{\T^{m-1}(x)}{(-\beta)^{m-1}} + \sum_{k=1}^{m-1} \frac{x_k}{(-\beta)^k}\\
&=& \frac{\frac{x_m}{-\beta}+\frac{T^m(x)}{-\beta}}{(-\beta)^{m-1}} + \sum_{k=1}^{m-1} \frac{x_k}{(-\beta)^k}\\
&=& \frac{\T^m(x)}{(-\beta)^m} + \sum_{k=1}^m \frac{x_k}{(-\beta)^k}.
\eea
We see that the statement is true for $m$ as well. The proof is finished by noting that $\frac{\T^m(x)}{(-\beta)^m}\to 0$ as $m\to\infty$.
\end{proof}
The following example shows that the original $(-\beta)$-transformation posed by Ito and Sadahiro \cite{IS09} can be viewed as restrictions of our maps.
\begin{example}\label{ex:2.3}
Let the base be given by $\beta = \frac{1+\sqrt{5}}{2}$ and consider the map $\Tl$ with cut point $2-\sqrt{5}$. This map is shown in Figure \ref{fig:2}.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=2.5]
\draw[->] (-1.2,0) -- (0.8,0);
\draw[->] (0,-1.2) -- (0,0.8);
\draw[black!50!white] (0,-1) -- (0,0.62);
\draw[black!50!white] (0.62,0) -- (-1,0);
\draw (-1,-1) rectangle (0.62,0.62);
\draw[color=blue,thick] (-1,0.62) -- (-0.236,-0.62);
\draw[color=blue,thick] (-0.232,0.36) -- (0.62,-1);
\filldraw[color=blue] (-0.236,-0.62) circle(0.5pt);
\draw[color=blue] (-0.239,0.38) circle(0.5pt);
\draw (-1,-1) node [below] {$-1$} -- (0,-1) node [below left] {$0$} -- (0.62,-1) node [below] {$\beta-1$};
\draw[dashed] (-0.62,-0.62) rectangle (0.38,0.38);
\end{tikzpicture}
\caption{The map $\Tl$ from Example \ref{ex:2.3}.\label{fig:2}}
\end{figure}
The smaller box in Figure \ref{fig:2} is the $(-\beta)$-transformation as defined by Ito and Sadahiro. Hence, for this particular $\beta$ and choice of cut point, our map $\Tl$ is an extension of their $(-\beta)$-transformation.
Finding $(-\beta)$-expansions using this map $\Tl$ can be done using Proposition \ref{prop:2.2}. For example, we find $-\frac{1}{2}=\left(.\overline{100}\right)_{-\beta}$, which agrees with the result of Ito and Sadahiro. However, we can also find $-\frac{3}{4}=\left(.1\overline{011110}\right)_{-\beta}$; a result that cannot be found using the original $(-\beta)$-transformation.
\end{example}
\section{Admissibility and shift spaces}
Henceforth, whenever we refer to the map $\T$, we assume that it has been fixed beforehand. A sequence $(x_1,x_2,\ldots)\in{\cal A}^\NN$ is called \emph{$\T$-admissible} if we have $\dn(x)=(x_1,x_2,\ldots)$ for some $x\in I_{-\beta}$ and, moreover, the $(-\beta)$-expansion of $x$ generated by the map $\T$ (see Proposition \ref{prop:2.2}) has coefficients $x_1,x_2,\ldots$ A finite block is called $\T$-admissible if it appears in a $\T$-admissible sequence.
In order to nicely characterize the $\T$-admissible sequences, we introduce an order on the set of $\T$-admissible sequences: the \emph{alternate (lexicographical) order}. We write $(x_1,x_2,\ldots)\prec(y_1,y_2,\ldots)$ if and only if there exists some integer $k\geq 1$ such that $x_i=y_i$ for all $ic$.
Let $(x^n)_{n=1}^\infty$ be a decreasing sequence for which $\dn(x^n,1)=\drs(c,1)$ for all $n\geq 1$, where $\dn(x^n)$ is the $(-\beta)$-expansion of $x^n$ generated by $\T$. For all $m,n\geq 1$ with $m0$ for all $n\geq 1$.
\end{proof}
\begin{example}\label{ex:3.7}
We continue Example \ref{ex:3.4}. Since the orbit of $0$ never hits $0$ again under $\Tl$, we conclude that $\dls(0)=\dl(0)=(1,\overline{1,0})$. Under $\Tr$, however, $0$ hits itself after one iteration. Hence, we have $\drs(0,1)=0$ and continue iterating $\Tl$. At this point, we know the orbit of $0$ under $\Tl$ and therefore $\drs(0)$ is the concatenation of the single-digit block $(0)$ with $(1,\overline{1,0})$: $\drs(0)=(0,1,\overline{1,0})$.
\end{example}
\begin{example}\label{ex:3.8}
We continue Example \ref{ex:3.2}. Since the orbit of $2-\sqrt{5}$ never hits itself under both $\Tl$ and $\Tr$, we have $\dls(2-\sqrt{5})=\dl(2-\sqrt{5})=(1,1,\overline{0})$ and $\drs(2-\sqrt{5})=\dr(2-\sqrt{5})=(0,0,1,\overline{0})$.
\end{example}
\begin{remark}
The sequences $\dls(c)$ and $\drs(c)$ are concatenations of blocks of sequences of the form $\dl(\ell_a)$, $\dr(\ell_a)$, $\dl(r_a)$ and $\dr(r_a)$ where $a\in{\cal A}$.
\end{remark}
The following lemma is very important:
\begin{lemma}
Let $(x_1,x_2,\ldots)\in{\cal A}^\NN$. The following hold:\label{lem:3.10}
\begin{itemize}
\item[(a)] If for all $n\geq 1$ we have
\bea
\drs(\ell_{x_n})\preceq(x_n,x_{n+1},\ldots)\preceq\dl(r_{x_n}),
\eea
then every finite subblock of $(x_1,x_2,\ldots)$ is $\Tl$-admissible.
\item[(b)] If for all $n\geq 1$ we have
\bea
\dr(\ell_{x_n})\preceq(x_n,x_{n+1},\ldots)\preceq\dls(r_{x_n}),
\eea
then every finite subblock of $(x_1,x_2,\ldots)$ is $\Tr$-admissible.
\end{itemize}
\end{lemma}
\begin{proof}
We only prove (a), as the proof of (b) is similar. Suppose that $(x_1,x_2,\ldots)$ satisfies the given condition and define $x^{(k)}:=\sum_{n=k}^\infty \frac{x_n}{(-\beta)^{n-k+1}}$. Assume that there exist integers $s(k),t(k)>k$ such that:
\bea
x_k\cdots x_{s(k)-1} = \drs(\ell_{x_k},1)\cdots\drs(\ell_{x_k},s(k)-k),\\
(-1)^{s(k)-k+1}\left(\drs(\ell_{x_k},s(k)-k+1)-x_{s(k)}\right)<0,
\eea
and
\bea
x_k\cdots x_{t(k)-1} = \dl(r_{x_k},1)\cdots \dl(r_{x_k},t(k)-k),\\
(-1)^{t(k)-k+1}\left(x_{t(k)}-\dl(r_{x_k},t(k)-k+1)\right)<0.
\eea
If either $s(k)$ or $t(k)$ does not exist, then there is nothing to prove. Let $y$ be a point such that $\dl(y,i)=\drs(\ell_{x_k},i)$ for $1\leq i\leq s(k)-k+1$, then
\bea
x^{(k)}-\ell_{x_k} & > & x^{(k)}-y\\
&=& \sum_{n=s(k)}^\infty \frac{x_n}{(-\beta)^{n-k+1}} - \frac{\Tl^{s(k)-k}(y)}{(-\beta)^{s(k)-k}}\\
&>& \frac{1}{(-\beta)^{s(k)-k}}\left(x^{s(k)}-\Tl^{s(k)-k}(y)\right),
\eea
from which it follows that
\ba\label{eq:3.2}
x^{(k)}-\ell_{x_k} &>& \begin{cases}
\frac{x^{s(k)}-\ell_{x_{s(k)}}}{(-\beta)^{s(k)-k+1}}, & \text{if $s(k)-k+1$ is odd};\\
\frac{x^{s(k)}-r_{x_{s(k)}}}{(-\beta)^{s(k)-k+1}}, & \text{if $s(k)-k+1$ is even}.
\end{cases}
\ea
Similarly, one can show that
\ba\label{eq:3.3}
r_{x_k}-x^{(k)} &>& \begin{cases}
\frac{r_{x_{t(k)}}-x^{t(k)}}{(-\beta)^{t(k)-k+1}}, & \text{if $t(k)-k+1$ is odd};\\
\frac{\ell_{x_{t(k)}}-x^{t(k)}}{(-\beta)^{t(k)-k+1}}, & \text{if $t(k)-k+1$ is even}.\\
\end{cases}
\ea
By iteratively applying the bounds in \eqref{eq:3.2} and \eqref{eq:3.3} we get a sequence of bounds that approach zero (as the numerator is bounded and the denominator goes to infinity). It follows that $l_{x_k},>=stealth',shorten >=1pt,auto,node distance=2.2cm,semithick]
\node[state] (00) {$\vectwo{0}{0}$};
\node[state] (10) [right of=00] {$\vectwo{1}{0}$};
\node[state] (01) [below of=00] {$\vectwo{0}{1}$};
\node[state] (120) [right of=10] {$\vectwo{1,2}{0}$};
\node[state] (31) [below of=120] {$\vectwo{3}{1}$};
\node[state] (140) [right of=31] {$\vectwo{1,4}{0}$};
\node[state] (1230) [above of=140] {$\vectwo{1,2,3}{0}$};
\node[state] (1240) [right of=1230] {$\vectwo{1,2,4}{0}$};
\node[state] (012) [below of=01] {$\vectwo{0}{1,2}$};
\node[state] (13) [right of=012] {$\vectwo{1}{3}$};
\node[state] (122) [right of=13] {$\vectwo{1,2}{2}$};
\node[state] (123) [right of=122] {$\vectwo{1,2}{3}$};
\path (00) edge node {0} (10)
edge node [left] {1} (01)
(10) edge node {0} (120)
edge [bend left] node {1} (01)
(01) edge [bend left] node {0} (10)
edge node {1} (012)
(120) edge [loop above] node {0} (120)
edge node {1} (31)
(31) edge node [below] {0} (140)
edge node {1} (012)
(140) edge node {0} (1230)
(1230) edge [bend left] node {0} (1240)
edge node {1} (31)
(1240) edge [bend left] node {0} (1230)
(012) edge node [below] {0} (13)
edge [loop left] node {1} (012)
(13) edge node [below] {0} (122)
(122) edge [bend left] node {0} (123)
edge node {1} (31)
(123) edge [bend left] node {0} (122);
\end{tikzpicture}
\caption{A labeled graph recognizing the shift space given by \eqref{eq:5}.\label{fig:3}}
\end{figure}
\end{example}
\begin{example}\label{ex:4.6}
Now consider the map given in Example \ref{ex:3.4}. By Example \ref{ex:3.7}, $\drs(0)=(0,1,\overline{1,0})$, and thus a sequence belongs to the shift space generated by this map if and only if
\ba\label{eq:6}
(x_n,x_{n+1},\ldots)\preceq(1,\overline{1,0}) & \vee & (0,1,\overline{1,0})\preceq(x_n,x_{n+1},\ldots)
\ea
holds for all $n\geq 1$. Once again, we omitted two inequalities since they are redundant. We can proceed as in the previous example and create the following tables:
\bea
\begin{tabular}{|c|c|c|}
$m_0^\ell(i/d)$ & 0 & 1\\
\hline
0 & 1 & 0\\
1 & $F$ & 2\\
2 & 0 & 3\\
3 & 2 & 0\\
\end{tabular}
& &
\begin{tabular}{|c|c|c|}
$m_1^r(i/d)$ & 0 & 1\\
\hline
0 & 0 & 1\\
1 & 0 & 2\\
2 & 1 & 0\\
\end{tabular}
\eea
The tables now only reveal one forbidden block: $(0,0)$. As we will see in a later section, this is the only forbidden block. For the moment, assume we are not aware of this. We construct a labeled graph that recognizes the shift based on our lengthy exposition earlier. This graph is shown in Figure \ref{fig:4}.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.2cm,semithick]
\node[state] (00) {$\vectwo{0}{0}$};
\node[state] (10) [right of=00] {$\vectwo{1}{0}$};
\node[state] (01) [below of=00] {$\vectwo{0}{1}$};
\node[state] (012) [below of=01] {$\vectwo{0}{1,2}$};
\node[state] (11) [below of=10] {$\vectwo{1}{1}$};
\node[state] (21) [right of=11] {$\vectwo{2}{1}$};
\node[state] (212) [below of=21] {$\vectwo{2}{1,2}$};
\node[state] (312) [right of=212] {$\vectwo{3}{1,2}$};
\node[state] (121) [above of=312] {$\vectwo{1,2}{1}$};
\node[state] (2312) [above of=121] {$\vectwo{2,3}{1,2}$};
\path (00) edge node {0} (10)
edge node [left] {1} (01)
(10) edge [bend left] node {1} (21)
(01) edge node {0} (10)
edge node {1} (012)
(012) edge node {0} (11)
edge [loop left] node {1} (012)
(11) edge [bend left] node {1} (212)
(21) edge [bend left] node {0} (10)
edge node {1} (312)
(212) edge [bend left] node {0} (11)
edge node {1} (312)
(312) edge node {0} (121)
edge [bend left] node {1} (012)
(121) edge node [right] {1} (2312)
(2312) edge [bend right] node [left] {0} (121)
edge [bend left] node {1} (312);
\end{tikzpicture}
\caption{A labeled graph recognizing the shift space given by \eqref{eq:6}.\label{fig:4}}
\end{figure}
\end{example}
As in the case of expansions in positive base, whenever $\beta$ is Pisot we can improve Theorem \ref{thm:4.4} a little. Recall that a \emph{Pisot number} is a positive algebraic integer whose other conjugates lie in the unit circle in the complex plane. The following theorem shows why Pisot bases are nice to work with.
\begin{theorem}
Let $\beta$ be Pisot, $x\in I_{-\beta}$ and $\T$ be given and let $\dn(x)$ be the $(-\beta)$-expansion of $x$ generated by $\T$. If $x\in\QQ(\beta)$, then $\dn(x)$ is eventually periodic.
\end{theorem}
\begin{proof}
We will not give the complete proof here, as it is nearly identical to the proof of \cite[Theorem 24]{DMP11}. In our case, replace $[l,r)$ with $I_{-\beta}$ and note that we have the bound $|r_n|<\frac{\beta\cdot\lfloor\beta\rfloor}{\beta^2-1}$.
\end{proof}
As an immediate corollary, we have:
\begin{theorem}\label{thm:4.8}
Let $\beta$ be Pisot and $\Sn$ be given. Then $\Sn$ is sofic if and only if the cut points of the underlying map $\T$ all lie in $\QQ(\beta)$.
\end{theorem}
\section{Forbidden blocks}
Example \ref{ex:4.6} showed that, while technically correct, our construction of the labeled graph can yield us quite large graphs. However, by carefully looking at Examples \ref{ex:4.5} and \ref{ex:4.6} we see why the first one is only sofic and the latter is actually a shift of finite type. In the first example, the forbidden blocks contain both a part of the pre-periodic and a part of the periodic part of the boundary sequence, where in the second example the forbidden block only contained part of the pre-periodic part. This observation quickly leads us to a conjecture: a shift space of the form given in Theorem \ref{thm:4.2} is a shift of finite type if and only if its forbidden blocks only contain part of either pre-periodic or periodic parts of boundary sequences, but not both. Indeed, if the latter does happen, we can abuse the periodicity of the boundary sequences to generate infinitely many forbidden blocks that cannot be covered by a finite set (because of the pre-periodic part). Based on these observations, we state the following
\begin{theorem}\label{thm:5.1}
Let $\Sn$ be a sofic shift. Then $\Sn$ is a shift of finite type if and only if the periodic part of every eventually periodic boundary sequence is a purely periodic boundary sequence.
\end{theorem}
\begin{proof}
Once again, we assume that the underlying map is left-continuous and write $\Sl$ instead of $\Sn$. Let $\Sl$ be a shift of finite type. Every shift of finite type is sofic and hence by Theorem \ref{thm:4.4} we conclude that all boundary sequences are eventually periodic. Assume that there exists a left-boundary sequence (the proof is similar for right-boundary sequences) $(a_1,\ldots,a_k,\overline{a_{k+1},\ldots,a_{k+p}})$, where $k,p\geq 1$, whose periodic part does not equal some other boundary sequence. Moreover, assume that $k$ is odd (the proof is similar for $k$ even). By assumption, there exists a smallest integer $1\leq j\leq p$ such that there exists some $b\in{\cal A}$ for which we have $(-1)^{k+j}(b-a_{k+j})<0$. It follows that the block $(a_1,\ldots,a_{k+j-1},b)$ is forbidden. Moreover, the blocks $w^{(n)}:= a_1\cdots a_k(a_{k+1}\cdots a_{k+p})^{2n} a_{k+1}\cdots a_{k+j-1}b$ are forbidden for all $n\geq 0$.
Suppose that there exists some $1\leq i\leq j-1$ such that the subblock $a_{k+i}\cdots b$ of length at most $j$ is forbidden. Then the blocks $(a_{k+1}\cdots a_{k+p})^{2n}a_{k+1}\cdots a_{k+j-1}b$ are forbidden for all $n\geq 0$ and thus we conclude that
\bea
(\overline{a_{k+1}\cdots a_{k+p}})\prec (a_{k+1}\cdots a_{k+p})^{2n} a_{k+1}\cdots a_{k+j-1}b
\eea
holds for all $n\geq 1$. This, however, implies that $(\overline{a_{k+1},\ldots,a_{k+p}})$ is a right-boundary sequence, which contradicts our initial assumption. Hence, there exists some integer $1\leq m\leq k$ such that the blocks $a_m\cdots a_k(a_{k+1}\cdots a_{k+p})^{2n}a_{k+1}\cdots a_{k+j-1}b$ are forbidden for all $n\geq 0$, but any of their subblocks are admissible. Hence, $\Sn$ is not a shift of finite type.
Next, assume that all boundary sequences satisfy the property given in Theorem \ref{thm:5.1} and let $(a_1,a_2,\ldots)$ be an arbitrary but fixed left-boundary sequence (the proof is similar for right-boundary sequences). If it is purely periodic with period $p$, then the forbidden blocks are given by
\ba\label{eq:7}
\left\{ (x_1,\ldots,x_{2p})\in{\cal A}^{2p}:\ (x_1,\ldots,x_{2p})\prec (a_1,\ldots,a_{2p})\,\wedge\,x_1=a_1\right\}.
\ea
If it is eventually periodic with pre-periodic part of length $q$ and period $p$, then the set
\ba\label{eq:8}
\left\{ (x_1,\ldots,x_{q+1})\in{\cal A}^{q+1}:\ (x_1,\ldots,x_{q+1})\prec(a_1,\ldots,a_{q+1})\,\wedge\,x_1=a_1\right\}
\ea
is sufficient. To see why, let $(y_1,y_2,\ldots)$ be a sequence such that $y_1=a_1$ and $(y_1,y_2,\ldots)\prec(a_1,a_2,\ldots)$. Let $m$ be the smallest integer such that $y_i=a_i$ for $iq+1$. Moreover, assume that $q$ is odd (the argument is similar for $q$ even). Then $y_1\cdots y_{q+1}=a_1\cdots a_{q+1}$ and
\bea
(\overline{a_{q+1},\ldots,a_{q+p}})\prec(y_{k+1},y_{k+2},\ldots).
\eea
Since the purely periodic sequence on the left-hand side is another boundary sequence, it follows that the forbidden blocks of $(y_1,y_2,\ldots)$ are contained within the subsequence $(y_{q+1},y_{q+2},\ldots)$. But these forbidden blocks are already covered by a set of the form \eqref{eq:7}. Hence, it is sufficient to consider forbidden blocks of the form in \eqref{eq:8}. Since there are finitely many boundary sequences and since each of these boundary sequences only have a finite number of forbidden blocks, the shift space is a shift of finite type.
\end{proof}
We can use the result of this theorem to reduce our graphs quite a bit as follows. Consider any boundary sequence. If its periodic part is a boundary sequence of the same shift space, then remove this periodic part. If our memory contains the whole pre-periodic part of this boundary sequence, then accept it and forget about it (i.e., the new memory index in this specific case would be a zero). The following two examples illustrate this.
\begin{example}
Reconsider Example \ref{ex:4.6}. Since $(\overline{1,0})$ is a boundary sequence (the smallest with respect to $\prec$), we can forget about this periodic part. Moreover, this turns $(1,\overline{1,0})$ into the single digit boundary block $(1)$, which itself is redundant, and hence we are left with the following condition:
\bea
(0,1)\preceq(x_n,x_{n+1})
\eea
for all $n\geq 1$ such that $x_n=0$. Although not necessary at this point, we still fill in the table:
\bea
\begin{tabular}{|c|c|c|}
$m_0^\ell(i/d)$ & 0 & 1\\
\hline
0 & 1 & 0\\
1 & $F$ & 0\\
\end{tabular}
\eea
The resulting graph is shown in Figure \ref{fig:5}.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.2cm,semithick]
\node[state] (0) {$0$};
\node[state] (1) [right of=0] {$1$};
\path (0) edge [loop left] node {1} (0)
edge [bend left] node {0} (1)
(1) edge [bend left] node {1} (0);
\end{tikzpicture}
\caption{Another labeled graph recognizing the shift space of Example \ref{ex:4.6}.\label{fig:5}}
\end{figure}
\end{example}
The same approach can be applied to any shift space of the form in Theorem \ref{thm:4.2} as long as at least one eventually periodic boundary sequence has a periodic part equal to a periodic boundary sequence.
\begin{example}\label{ex:5.3}
Let $\beta=2$ and consider the left-continuous map with cut points $-\frac{5}{6}$ and $-\frac{1}{6}$. Theorem \ref{thm:4.2} tells us that $(x_1,x_2,\ldots)\in\Sn$ if and only if for all $n\geq 1$ we have:
\bea
\begin{array}{rrllll}
& (\overline{2,0}) & \preceq & (x_n,x_{n+1},\ldots) & \preceq & (2,\overline{1}),\\
& (1,\overline{0,2}) & \preceq & (x_n,x_{n+1},\ldots) & \preceq & (1,\overline{1,0}),\\
\textrm{or} & (0,\overline{0,1}) & \preceq & (x_n,x_{n+1},\ldots) & \preceq & (\overline{0,2}).
\end{array}
\eea
Careful inspection reveals that the boundary sequences ($\overline{2,0})$ and $(\overline{0,2})$ are redundant (the smallest and largest possible sequence with respect to $\prec$). Moreover, we may reduce $(1,\overline{0,2})$ to the single digit block $(1)$, which is once again redundant. We are left with:
\ba\label{eq:9}
\begin{cases}
(x_n,x_{n+1},\ldots) \preceq (2,\overline{1}), & \text{whenever $x_n=2$};\\
(x_n,x_{n+1},\ldots) \preceq (1,\overline{1,0}), & \text{whenever $x_n=1$};\\
(0,\overline{0,1}) \preceq (x_n,x_{n+1},\ldots), & \text{whenever $x_n=0$}.
\end{cases}
\ea
We create tables one more time:
\bea
\begin{tabular}{c|c|c|c}
$m_0^\ell(i/d)$ & 0 & 1 & 2\\
\hline
0 & 1 & 0 & 0\\
1 & 2 & 0 & 0\\
2 & 0 & 1 & $F$
\end{tabular}
&
\begin{tabular}{c|c|c|c}
$m_1^r(i/d)$ & 0 & 1 & 2\\
\hline
0 & 0 & 1 & 0\\
1 & 0 & 2 & $F$\\
2 & 1 & 0 & 0
\end{tabular}
&
\begin{tabular}{c|c|c|c}
$m_2^r(i/d)$ & 0 & 1 & 2\\
\hline
0 & 0 & 0 & 1\\
1 & 0 & 2 & $F$\\
2 & $F$ & 1 & 0
\end{tabular}
\eea
and use these to produce the labeled graph in Figure \ref{fig:6}.
\begin{figure}[b]
\centering
\begin{tikzpicture}[->,>=stealth',auto,node distance=3.5cm,semithick,scale=0.5]
\node[state] (000) {$\vecthree{0}{0}{0}$};
\node[state] (010) [right of=000] {$\vecthree{0}{1}{0}$};
\node[state] (100) [below of=010] {$\vecthree{1}{0}{0}$};
\node[state] (001) [below of=000] {$\vecthree{0}{0}{1}$};
\node[state] (012) [below of=001] {$\vecthree{0}{1}{2}$};
\node[state] (0122) [right of=012] {$\vecthree{0}{1,2}{2}$};
\node[state] (0121) [right of=0122] {$\vecthree{0}{1,2}{1}$};
\node[state] (0120) [right of=010] {$\vecthree{0}{1,2}{0}$};
\node[state] (1200) [right of=100] {$\vecthree{1,2}{0}{0}$};
\node[state] (110) [right of=1200] {$\vecthree{1}{1}{0}$};
\path (000) edge node {0} (100)
edge node {1} (010)
edge node {2} (001)
(010) edge node {1} (0120)
edge node [left] {0} (100)
(001) edge node {0} (100)
edge node {1} (012)
(100) edge [bend right] node [right] {1} (010)
edge [bend left] node {2} (001)
edge node {0} (1200)
(012) edge [bend left=60] node [below] {1} (0121)
(0121) edge [bend right] node {0} (110)
edge [bend left] node {1} (0122)
(0122) edge [bend left] node {1} (0121)
(1200) edge [loop above] node {0} (1200)
edge node {1} (110)
(0120) edge [loop above] node {1} (0120)
edge node [below left] {0} (110)
(110) edge [bend right] node [above right] {1} (0120)
edge [bend left] node {0} (1200);
\end{tikzpicture}
\caption{A labeled graph recognizing the shift from Example \ref{ex:5.3}.\label{fig:6}}
\end{figure}
\end{example}
\section{Discussion}
Our goal was to consider a large class of $(-\beta)$-transformations and to prove statements analogous to what Ito and Sadahiro for their $(-\beta)$-transformation. Our class of $(-\beta)$-transformations include transformations that, when restricted to the interval $\left[-\frac{\beta}{\beta+1},\frac{1}{\beta+1}\right)$, are the Ito-Sadahiro transformation. As to be expected, our results agree with results on their transformation (compare Theorem \ref{thm:3.9} and \ref{thm:4.4} with \cite[Theorem 10 \& 12]{IS09} and Theorem \ref{thm:5.1} with \cite[Theorem 4]{FL09}). While we only considered the canonical alphabet, there are many other alphabets to be considered. In fact, there is a rather large class of alphabets satisfying property i of Assumption \ref{ass:2.1} (compare with \cite[Proposition 2.1]{Ped04}) of which we assume the results in this paper will carry over.
Of the many open problems surrounding $(-\beta)$-expansions we want to highlight two. The first problem is based on the examples in sections 4 and 5 illustrating the output of our algorithm. Can this algorithm be improved upon? The second problem follows from \cite{IS09}: given two sequences $\boldsymbol{x},\boldsymbol{y}\in{\cal A}^\NN$ (or any other alphabet), is there a $(-\beta)$-transformation such that $\boldsymbol{x}$ and $\boldsymbol{y}$ are boundary sequences of this transformation?
\begin{thebibliography}{10}
\bibitem{DK11} K. Dajani and C. Kalle, Transformations generating negative $\beta$-expansions, \emph{Integers} \textbf{11B} (2011).
\bibitem{DK03} K. Dajani and C. Kraaikamp, From greedy to lazy expansions and their driving dynamics, \emph{Expo. Math.} \textbf{20} (2002), 315--327.
\bibitem{DK04} K. Dajani and C. Kraaikamp, Random $\beta$-expansions, \emph{Ergodic Theory Dynam. Systems} \textbf{23} (2003), 461--479.
\bibitem{DV05} K. Dajani and M. de Vries, Measures of maximal entropy for random $\beta$-expansions, \emph{J. Eur. Math. Soc. (JEMS)} \textbf{7} (2005), 51--68.
\bibitem{DMP11} D. Dombek, Z. Mas\'{a}kov\'{a}, and E. Pelantov\'{a}, Number representation using generalized $(-\beta)$-transformation, \emph{Theoret. Comput. Sci.} \textbf{412} (2011), 6653--6665.
\bibitem{EJ91} P. Erd\H{o}s and I. Jo\'{o}, On the expansion $1=\sum q^{-n_i}$, \emph{Period. Math. Hungar.} \textbf{23} (1991), 27--30.
\bibitem{FL09} C. Frougny and A. C. Lai, On negative bases, in
{\it Proc. DLT 09},
Lecture Notes in Comp. Sci., Vol.\ 5583, Springer,
2009, pp.\ 252--263.
\bibitem{IS09} S. Ito and T. Sadahiro, Beta-expansions with negative bases, \emph{Integers} \textbf{9} (2009), 239--259.
\bibitem{LM95} D. Lind and B. Marcus, \emph{An Introduction to Symbolic Dynamics and Coding}, Cambridge University Press, 1995.
\bibitem{Par60} W. Parry, On the $\beta$-expansions of real numbers, \emph{Acta. Math. Acad. Sci. Hung.} \textbf{11} (1960), 401--416.
\bibitem{Ped04} M. Pedicini, Greedy expansions and sets with deleted digits, \emph{Theoret. Comput. Sci.} \textbf{332} (2005), 313--336.
\bibitem{Ren57} A. R\'{e}nyi, Representations for real numbers and their ergodic properties, \emph{Acta. Math. Acad. Sci. Hung.} \textbf{8} (1957), 477--493.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 37B10; Secondary 11A63.
\noindent \emph{Keywords: }
$(-\beta)$-expansions, sofic shift, shift of finite type.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received October 10 2011;
revised version received January 11 2012.
Published in {\it Journal of Integer Sequences}, January 14 2012.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}