%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-31/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem*{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{fact}{Fact}
\newtheorem*{remark}{Remarks}
\newtheorem*{app}{Applications}
\newtheorem*{conj}{Conjecture}


\title{Descriptions of the Characteristic Sequence of an Irrational}
\author{Tom C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Descriptions of the characteristic sequence of an irrational},
  Canad. Math. Bull. \textbf{36} (1993), 15--21.}\bigskip\end{center}

\begin{abstract} 
Let $\alpha$ be a positive irrational real number. (Without loss of generality assume $0< \alpha < 1$.) The \emph{characteristic sequence} of $\alpha$ is 
\[ f(\alpha) = f_1f_2 \cdots, \textup{ where } f_n = [(n + 1)\alpha] - [n\alpha]. \]
We make some observations on the various descriptions of the characteristic sequence of $\alpha$ which have appeared in the literature. We then refine one of these descriptions in order to obtain a very simple derivation of an arithmetic expression for $[n\alpha]$ which appears in A. S. Fraenkel, J. Levitt, and M. Shimshoini~\cite{fraenkel+levitt+shimshoni1972}. Some concluding remarks give conditions on $n$ which are equivalent to $f_n = 1$.
\end{abstract}

\section{Introduction} \label{sec: 1} 

Let $\alpha$ be an irrational real number, $0 < \alpha < 1$. The \emph{characteristic sequence} of $\alpha$ is 
\[ f(\alpha) = f_1f_2 \cdots, \textup{ where } f_n = [(n + 1)\alpha] - [n\alpha], \quad n \geq 1. \]

(This terminology is due to E. B. Christoffel~\cite{christoffel1875}.)

Note that $f(\alpha$ is a sequence of 0's and 1's and that $[k\alpha] = f_1 + f_2 + \cdots + f_{k-1},$ $k\geq 2$. (If desired, one can allow $\alpha > 1$ by setting $f_1 = [(n + 1)\alpha] - [n\alpha] - [\alpha]$. In this case, $[k\alpha] = f_1 + f_2 + \cdots + f_{k -1} + k[\alpha]$.)

Facts~\ref{fact: 1},~\ref{fact: 2},~\ref{fact: 3} below are explicit desriptions, which have already appeared in the literature, of the sequence $f(\alpha)$, and each can be used to generated arbitrarily long initial segments of $f(\alpha)$. Fact~\ref{fact: 2} is undoubtedly the easiest of the three to use for this purpose. Fact~\ref{fact: 4} is concerned with the sequence $f(\alpha)$ when $\alpha$ is a quadratic irrational.

\section{Statements of Facts~\ref{fact: 1}--\ref{fact: 4}} \label{sec: 2}

\begin{defn} \label{defn: 1} Let $\alpha$ be an irrational real number with $0 < \alpha < 1$. Let $[0,a_1,a_2,\dots]$ be the simple continued fraction for $\alpha$, that is,
\[ \alpha = [0,a_1,a_2,\dots] = \frac{1}{a_1 + \dfrac{1}{a_2 + \cdots}}. \]
Let 
\[ \frac{p_n}{q_n} = [0,a_1,a_2,\dots,a_n], \quad n \geq 1, \]
and let
\[ X_n = f_1f_2\cdots f_{q_n}, \quad n \geq 1. \]
Thus $X_n$ is the initial segment of $f(\alpha)$ of length $q_n$.
\end{defn}

It is standard to define $p_{-2} = 0, p_{-1} = 1, q_{-2} = 1, q_{-1} = 0$, so that 
\[ p_n = a_n p_{n-1} + p_{n-2}, \quad q_n = a_nq_{n-1} + q_{n-2}, \quad n \geq 0. \]
This fact will be used throughout the remainder of the paper.

\begin{defn} \label{defn: 2} For each $n\geq 1$, define the irrational number $\alpha_n$ by $\alpha = [0,a_1,a_2,\dots,a_n + \alpha_n]$. \end{defn}

\begin{defn} \label{defn: 3}
Let $G$ be the free group generated by the symbols 0,1. Thus the elements of $G$ are blocks or words in the symbols 0,1 (and their inverses), and the identity element of $G$ is the empty word. We define, for each $t \geq 1$, homomorphisms $k_t$ and $h_t$ from $G$ into $G$ by setting $k_t(0) = 0^{t-1}1,k_t(1) = 0^t1$, and $h_t(0) = 0^{t-1}1,h_t(1) = 0^{t-1}10$. Thus $k_t(w_1w_2\cdots w_n) = k_t(w_1)k_t(w_2) \cdots k_t(w_n)$, and similarly for $h_t$. Furthermore, we extend $k_t$ and $h_t$ to act on infinite binary sequences by setting $k_t(w_1w_2\cdots) = k_t(w_1)k_t(w_2) \cdots$, and similarly for $h_t$.
\end{defn}

\begin{fact} \label{fact: 1} 
For each $m \geq 1$, define 
\[ c_m = k_{a_1} \circ k_{a_2} \circ \cdots \circ k_{a_n}(0), \]
where $\circ$ denotes composition. Then for each $n \geq 1$, 
\[ f(\alpha) = (c_1c_2 \cdots c_n) \left(k_{a_1} \circ k_{a_2} \circ \cdots \circ k_{a_m}(f(\alpha_n)) \right). \]
\end{fact} 

\begin{fact} \label{fact: 2}
For each $n \geq 2$, 
\[ X_n = X_{n-1}^{a_n}X_{n-2}, \]
where $X_0 = 0$ and $X_1 = 0^{a_1 - 1}1$. (Here $X_{n-1}^{a_n}$ denotes $X_{n-1}X_{n-1} \cdots X_{n-1}$, with $a_n$ repetitions. If $a_1 = 1$, then $X_1 = 1$.)
\end{fact}

\begin{fact} \label{fact: 3}
For each $n \geq 1$, 
\[ f(\alpha) = h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_n}\left( f(\alpha_n) \right). \]
\end{fact}

\begin{fact} \label{fact: 4}
Let $h$ be the homomorphism from $G$ to $G$ defined by $h(0) = X_m$, $h(1) = X_mX_{m-1}$, and extend $h$ to act also on infinite binary sequences. Then if $\alpha$ is purely periodic with period $m$, that is, $\alpha = [0,a_1,\dots,a_m,a_1,\dots,a_m,a_1,\dots,a_m,\dots]$, then $h(f(\alpha)) = f(\alpha)$. (As pointed out by J. Shallit~\cite{shallit1991}, this can be deduced quickly from Fact~\ref{fact: 2} by showing by induction on $n$ that $h(X_n) = X_{m + n}$ for all $n \geq 0$.)
\end{fact}

\section{Historical remarks} \label{sec: 3}

D. H. Fowler has argued persuasively~(\cite{fowler1979,fowler1980,fowler1981}) that sequences essentially equivalent to the sequence $f(\alpha)$ were studied in ancient times, in fact prior to the development of Eudoxan theory of proportions. (Fowler notes that the sequence of occurrences of two periodic events is closely related to $f(\alpha)$, where $\alpha$ is the ratio of the periods of the two events.) (See also C. Series~\cite{series1985}, R. C. Riddell~\cite{ridell1979} and W. R. Knorr~\cite{knorr1975}.)

The earliest known explicit reference to characteristic sequences seems to be in the 1772 work of the astronomer J. Bernoulli~\cite{bernoulli1772}, where he gave without proof a description of the sequence $g(\alpha) = g_1g_2\cdots$, where $g_n = [(n + 1)\alpha + 1/2] - [n\alpha + 1/2]$. (A recipe for transforming $f(\alpha)$ into $g(\alpha)$ is given in Venkov~\cite{venkov1970}.) In 1875 E. B. Christoffel~\cite{christoffel1875} asserted without proof (essentially) Fact~\ref{fact: 1} above, which was proved by A. A. Markov~\cite{markoff1882} in 1882. In the meantime H. J. S. Smith~\cite{smith1876} in 1876 proved Fact~\ref{fact: 2} above.

Papers by M. Morse and G. Hedlund~\cite{morse+hedlund1940}, G. Hedlund~\cite{hedlund1954}, H. Cohn~\cite{cohn1974}, and F. Mignosi~\cite{mignosi1989} deal with other aspects of characteristic sequences. (In most of these papers the adjective ``Sturmian" is used rather than ``characteristic.") For example, Morse and Hedlund show that for each $n$, the sequence $f(\alpha)$ contains exactly $n + 1$ distinct blocks of length $n$, and they calculate exactly the minimum length $m(n)$ such that every block of length $m(n)$ in $f(\alpha)$ contains all the distinct blocks of length $n$. Mignosi shows that $f(\alpha)$ contains $k$ identical consecutive blocks for arbitrarily large $k$, if and only if the simple continued fraction for $\alpha$ has unbounded partial quotients.

K. B. Stolarsky~\cite{stolarsky1976}, A. S. Fraenkel, M. Mushkin, and U. Tassa~\cite{fraenkel+mushkin+tassa1978}, J. Rosenblatt~\cite{rosenblatt1978}, and J. Shallit~\cite{shallit1991} gave new proofs of Fact~\ref{fact: 2} (Fact~\ref{fact: 2} appears implicitly in the first three of these four papers, explicitly in the fourth.)

S. Ito and S. Yasutomi~\cite{ito+yastomi1990}, and K. Nishioka, I. Shiokawa, and J. Tamura~\cite{nishioka+shiokawa+tamura1992}, gave extensive results dealing with generalized characteristic sequences $h(\alpha,\beta) = h_1h_2\cdots$, where $h_n = [(n + 1)\alpha + \beta] - [n\alpha + \beta]$, including Fact~\ref{fact: 2} and Fact~\ref{fact: 4}.

Fact~\ref{fact: 3} appears in Brown~\cite{brown1991}.

Finally, we mention that Fact~\ref{fact: 4} was proved by no fewer than \emph{six} independent parties: H. Cohn~\cite[1974]{cohn1974} (implicitly), S. Ito and S. Yasutomi~\cite[1990]{ito+yastomi1990}, F. Laubie~\cite[1991]{laubie1991}, J. Shallit~\cite[1991]{shallit1991}, N. Nishioka, I. Shiokawa, and J. Tamura~\cite[1992]{nishioka+shiokawa+tamura1992},and T. Brown~\cite[1991]{brown1991}.

Extensive lists of references can be found in~\cite{fraenkel+mushkin+tassa1978,porta+stolarsky1990,stolarsky1976}. 

\section{Relations among Facts~\ref{fact: 1}-\ref{fact: 3}, and an extension of Fact~\ref{fact: 2}} \label{sec: 4}

Facts~\ref{fact: 1}-\ref{fact: 3} are related to each other by Theorem~\ref{thm: 1} below. It will be seen during the proof of Theorem~\ref{thm: 1} that each of Facts~\ref{fact: 1} and~\ref{fact: 3} implies Fact~\ref{fact: 2}.

\begin{lemma} \label{lemma: 1}
Define words $Y_0,Y_1,\dots$ by $Y_0 = 0, Y_1 = 0^{a_1 - 1}1, Y_n = Y_{n-1}^{a_n}Y_{n-2}$, $n \geq 2$. Also define words $Z_0, Z_1,\dots$ by $Z_0 = 0, Z_1 = 0^{a_1 - 1}1, Z_n = Z_{n-1}^{a_n - 1}Z_{n-2}Z_{n-1}$, $n \geq 2$. Then for each $n \geq 2$, 
\[ Z_n = (Y_{n-1}\cdots Y_1)^{-1}Y_n(Y_{n-1} \cdots Y_1). \]
\end{lemma}

\begin{proof} 
Induction on $n$.
\end{proof}

\begin{thm} \label{thm: 1} 
For each $n \geq 1$, 
\[ c_1c_2\cdots c_n = X_nX_{n-1}\cdots X_1, \]
\[ h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_n}(0) = X_n, \]
\[ h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_n}(1) = X_nX_{n-1}. \]
\end{thm}

\begin{proof} From Lemma~\ref{lemma: 1}, it follows that $Z_1Z_2\cdots Z_n = Y_nY_{n-1} \cdots Y_1$ for $n \geq 1$. Next, by induction on $m$, $c_m = Z_m$ for $m \geq 1$, so we now have $c_1c_2 \cdots c_n = Y_nY_{n-1} \cdots Y_1$. By Fact~\ref{fact: 1}, $c_1c_2 \cdots c_n$ is an initial segment of $f(\alpha)$, so that $Y_n$ is an initial segment of $f(\alpha)$. Finally, by induction on $n$, $Y_n$ has length $q_n$, therefore $Y_n = X_n$, and finally $c_1c_2 \cdots c_n = X_nX_{n-1} \cdots X_1$, $n \geq 1$.

(Also, note that since $Y_n = X_n$, it follows from the definition of $Y_n$ that $X_n = X_{n-1}^{a_n}X_{n-2}$, $n \geq 2$, so that Fact~\ref{fact: 1} implies Fact~\ref{fact: 2}.)

Next, with $Y_n$ defined as above, it follows by induction that $ h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_n}(0) = Y_n$ and $ h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_n}(1) = Y_nY_{n-1}$ $n \geq 1$. Using $Y_n = X_n$ gives $ h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_n}(0) = X_n$ and $ h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_n}(1) = X_nX_{n-1}$, $n \geq 1$.

(Also, note that from Fact~\ref{fact: 3} and $ h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_n}(0) = Y_n$, $ h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_n}(1) = Y_nY_{n-1}$, one can conclude that $Y_n$ is an initial segment of $f(\alpha)$. Therefore (since $Y_n$ has length $q_n$) $Y_n = X_n$, and by the definition of $Y_n$, $X_n = X_{n-1}^{a_n} X_{n-2}$, $n \geq 2$. Thus Fact~\ref{fact: 3} implies Fact~\ref{fact: 2}.)
\end{proof}

\begin{cor} Fact~\ref{fact: 1} implies Fact~\ref{fact: 2}, and Fact~\ref{fact: 3} implies Fact~\ref{fact: 2}.
\end{cor}

Now we extend Fact~\ref{fact: 2} by using the ``Zeckendorff number system." (See A. Ostrowski~\cite[1922]{ostrowski1922}, C. G. Lekkerkerker~\cite[1952]{lekkerkerker1952}, A. M. Yaglom and I. M. Yaglom~\cite[1967]{yaglom+yaglom1967}, A. S. Fraenkel, J. Levitt and M. Shimshoni~\cite[1972]{fraenkel+levitt+shimshoni1972}, and E. Zeckendorff~\cite[1972]{zeckendorf1972}. These systems of numeration have been generalized by A. S. Fraenkel and I. Borosh~\cite[1973]{fraenkel+borosh1973}, A. S. Fraenkel~\cite[1985]{fraenkel1985}, J. Shallit~\cite[1988]{shallit1988}, and A. S. Fraenkel~\cite[1989]{fraenkel1989}.)

Our extension (Theorem~\ref{thm: 2} below) enables one to give an exact formula for $\sum_{k=1}^m [k\alpha]$, for arbitrary $m$. This has been done in~\cite{brown+shiue1995-3}.

The next Lemma is well-known. (See for example A. S. Fraenkel~\cite[p.~111]{fraenkel1985}.) Recall that $\alpha$ is irrational, $\alpha = [0,a_1,a_2,\cdots]$, $\frac{p_n}{q_n} = [0,a_1,a_2,\dots,a_n]$, $n \geq 1$, $q_{-1} = 0$, $q_{0} = 1$, and $q_n = a_nq_{n-1} + q_{n-2}$, $n \geq 1$.

\begin{lemma} \label{lemma: 2}
Let $t \geq 1$. Then every $m$, $0 \leq m \leq q_t - 1$, has a unique representation in the form $m = z_tq_{t-1} +\cdots + z_2q_1 + z_1q_0$, where 

(1) $0 \leq z_1 \leq a_1 - 1$,

(2) $0 \leq z_i \leq a_i, \quad 2 \leq i \leq t$,

(3) $z_i = a_i \Rightarrow z_{i-1} = 0, \quad 2 \leq i \leq t$.

We then write $m = (z_t,\dots,z_2,z_1)_\alpha$, and we call this the Zeckendorff representation of $m$.
\end{lemma}

\begin{thm} \label{thm: 2}
Let $m \geq 1$ be given, and let $m = (z_t,\dots,z_2,z_1)_\alpha$. Then the initial segment of $f(\alpha)$ of length $m$ is 
\[ f_1f_2 \cdots f_m = X_{t-1}^{z_t} \cdots X_1^{z_2} X_0^{z_1}. \]
(Note that for any $i$, $X_i^0$ is the empty word.)
\end{thm}

\begin{proof}
We use induction on $m$. For $1 \leq m \leq q_1 - 1 = a_1 - 1$ (if $a_1 > 1$), $m = m_{q_0}$ and $f_1 \cdots f_m = 0^m = X_0^m$.

Suppose the result is true for all $m < q_t$ for some fixed $t \geq 1$, and now let $q_t \leq m < q_{t + 1}$, say $m = z_{t + 1} q_t + r$, where $1 \leq z_{t + 1} \leq a_{t + 1}$ and $0 \leq r < q_t$.

If $r = 0$, then since $m = z_{t+1}q_t$ and $X_t^{a_{t + 1}}X_{t-1} = X_{t + 1}$ is an initial segment of $f(\alpha$, it follows that $f_1\cdots f_m = X_t^{z_{t + 1}}$. 

If $1 \leq r < q_t$, then by hypothesis we have $r = (z_t, \dots, z_2,z_1)_\alpha$ and $f_1\cdots f_r = X_{t-1}^{z_t} \cdots X_1^{z_2} X_0^{z_1}$.

Now there are two cases, depending on whether $z_{t + 1} = a_{t + 1}$ or $z_{t + 1} < a_{t + 1}$.

If $z_{t + 1} = a_{t + 1}$, then since $m = a_{t + 1}q_t + r < q_{t + 1} = a_{t + 1}q_t + q_{t-1}$, we have $r < q_{t-1}$, so that $f_1 \cdots f_r$ is an initial segment of $X_{t - 1}$ (and $z_t = 0$). Then since $X_t^{a_{t + 1}}X_{t-1} = X_{t+1}$ is an initial segment of $f(\alpha)$, we have $f_1\cdots f_m = X_t^{z_{t + 1}} f_1 \cdots f_r = X_t^{z_{t + 1}} X_{t-1}^{z_t} \cdots X_1^{z_2} X_0^{z_1}$, and $m = (z_{t + 1}, \dots, z_2,z_1)_\alpha$. 

The remaining case is $m = z_{t + 1} q_t + r$, where $1 \leq z_{t + 1} < a_{t + 1}$ and $1 \leq r < q_t$. Then $f_1 \cdots f_m$ is an initial segment of $X_t^{z_{t + 1}}X_t$, which is an initial segment of $X_t^{a_{t + 1}}$ (which is an initial segment of $f(\alpha)$). Thus again $f_1 \cdots f_m = X_t^{z_{t + 1}} f_1 \cdots f_r = X_t^{z_{t + 1}} X_{t-1}^{z_t} \cdots X_1^{z_2}X_0^{z_1}$, and $m = (z_{t + 1},\dots,z_2,z_1)_\alpha$.

This finishes the induction step and the proof of Theorem~\ref{thm: 2}. 
\end{proof} 

\section{A simple arithmetic expression for $[m\alpha]$} \label{sec: 5}

Recall once again that $X_n$ is the initial segment of $f(\alpha)$ of length $q_n$, where $\frac{p_n}{q_n} = [0,a_1,\dots,a_n]$.

\begin{lemma} \label{lemma: 3} 
For each $n \geq 0$, the number of 1's in $X_n$ is $p_n$.
\end{lemma}

\begin{proof} This is am simple induction on $n$, using Fact~\ref{fact: 2} and $p_n = a_np_{n-1} + p_{n-2}$.
\end{proof}

The following theorem appears, in a somewhat more complex form, in A. S. Fraenkel, J. Levitt, and M. Shimshoni~\cite{fraenkel+levitt+shimshoni1972}. The proof given here is simpler.

\begin{thm} \label{thm: 3} 
For $m \geq 1$, let $m - 1 = (z_t,\dots,z_2,z_1)_\alpha$. Then $[m\alpha] = z_1p_{t-1} + \cdots + z_2p_1 + z_1p_0$.
\end{thm}

\begin{proof} We have $[m\alpha] = f_1 + f_2 + \cdots + f_{m-1}$, and $f_1 + f_2 + \cdots + f_{m-1}$ equals the number of 1's in $W_{m-1}$, the initial segment of $f(\alpha)$ of length $m - 1$. Since $W_{m-1} = X_{t-1}^{z_t} \cdots X_1^{z_2}X_0^{z_1}$, and the number of 1's in each $X_i$ is $p_i$, the number of 1's in $W_{m-1}$ is $z_tp_{t-1} + \cdots + z_2p_1 + z_1p_0$.
\end{proof}

\section{Remarks and questions} \label{sec: 6}

An interesting algorithm (which exploits the complementarity of sequences $[n(1 + \alpha)]$ and $[n(1 + 1/\alpha)]$) for calculating the terms of the sequence $[n(1 + \alpha)]$ is given by I. G. Connell~\cite{connell1960}.

J. Rosenblatt~\cite{rosenblatt1978} obtained a recursive property of the ``hit sequence" $h(\alpha) = h_0h_1h_2 \cdots$, where for $k \geq 0$, $h_k$ is the \emph{number} of non-negative integers $m$ such that $[m\alpha] = k$. His property is similar to Fact~\ref{fact: 2} above. The connection between $h(\alpha)$ and $f(\alpha)$ is the following. If $\alpha = 1/(a_1 + \alpha_1) < 1$, then $h(\alpha)(m) = f(\alpha_1)(m) + a_1$, $m \geq 1$, where $h(\alpha)(m)$, $f(\alpha_1)(m)$ denote the $m$th terms of the sequeneces $h(\alpha)$, $f(\alpha_1)$ respectively. If $\alpha > 1$, then $h(\alpha)(m) = h(1/\alpha)(m)$, $m \geq 1$.

D. Crisp, W. Moran, A. Pollington, and P. Shiue~\cite{crisp+moran+pollington+shiue1993} have found a necessary and sufficient condition on $\alpha$ for $f(\alpha)$ to be invariant under a substitution of the type $0 \mapsto B_1$, $1 \mapsto B_2$, thus answering the natural question concerning the converse of the statement of Fact~\ref{fact: 2}.

Perhaps there is a simple way to show that Fact~\ref{fact: 1} implies Fact~\ref{fact: 3} and vice versa. If not, perhaps the two can be put together in an interesting way.

Peter G. Anderson~\cite{andersonPC} has observed that if $u_n$ denotes the least significant digit in the Zeckendorff representation of $n$, $n \geq 0$, and if $Y_n = u_0u_1 \cdots u_{q_n - 1}$, $n \geq 0$, then the sequence $Y_n$, $n \geq 2$, satisfies the same recurrence as does the sequence $X_n = f_1f_2 \cdots f_{q_n}$, $n \geq 2$. It follows easily that if $\alpha = [0,a_1,a_2,\dots]$ with $a_1 > 1$, then $f_n = 1$ if and only if $u_{n-1} = a_1 - 1$, $n \geq 1$. If $\alpha = [0,1,a_2, \dots]$ it follows in the same way that $f_n = 0$ if and only if $v_{n-1} = a_2$, where $v_{n-1}$ is the second least significant digit in the Zeckendorff representation of $n-1$.

Finally, we remark that $f_n = 1$ if and only if the Zeckendorff representation of $n$ terminates in an odd number of zeros. This follows from the fact that $f_n = 1$ if and ony if $n = [k/\alpha]$ for some $k$ (see the last paragraph of~\cite{fraenkel+mushkin+tassa1978} or Lemma 1 of~\cite{brown1991}), together with the characterization of the values of $[k/\alpha]$, $k \geq 1$, given in~\cite{fraenkel+levitt+shimshoni1972}. (See also Property 1 in~\cite[1989]{fraenkel1989}.) One can also deduce this result directly, using Anderson's observation.

The author is grateful to Jeffrey Shallit for references~\cite{cohn1974,crisp+moran+pollington+shiue1993,christoffel1875,ito+yastomi1990,laubie1991,mignosi1989,nishioka+shiokawa+tamura1992,ostrowski1922}, and~\cite{smith1876}, and to the referee for references~\cite{crisp+moran+pollington+shiue1993,christoffel1875,fraenkel1989,ito+yastomi1990,lekkerkerker1952,smith1876}, for an exact reference to~\cite{bernoulli1772}, and for several helpful remarks.

\nocite{borel+laubie1991,borel+laubie1993,zeeman}


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}