%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-13/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{fact}{Fact}
\newtheorem{appl}{Application}

\title{Applications of standard Sturmian words to elementary number theory}
\author{Tom C. Brown}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Applications of standard Sturmian words to elementary number
  theory.}, WORDS (Rouen, 1999). Theoret. Comput. Sci. \textbf{273} (2002),
  no. 1--2, 5--9.}\bigskip\end{center}

\newcommand{\ceil}[1]{{\left[{#1}\right]}}

\begin{abstract}This note is a short survey, by no means intended to be
complete, of some of the descriptions which have been given of
standard Sturmian words, and of some of the applications of these
descriptions to elementary number theory.. (`Elementary number theory' is interpreted
fairly broadly.) The descriptions and applications below have appeared
before, expect for Fact \ref{f4}, Application \ref{a1}, and the
proof of Application \ref{a2}.

\noindent Keywords: Sturmian words; Continued fractions; Zeckendorf representations
\end{abstract}

\section{Introduction}

In 1876, Smith \cite{smith1876} proved the following remarkable fact.

Let $\alpha$ be an irrational real number with $0<\alpha<1$. Define the
infinite binary word $f_\alpha$ by $f_\alpha = f_\alpha(1)f_\alpha(2)\cdots
f_\alpha(n)\cdots$ where $f_\alpha(n) = \ceil{(n+1)\alpha}-\ceil{n\alpha}$,
$n\geq1$, $\ceil{\cdot}$ denoting the greatest integer function. Assume
that $\alpha$ has the simple continued fraction expansion $\alpha=[0,a_1,
a_2,\ldots,a_n,\ldots]$, and inductively define finite words $g_0=0$, $g_1
= 0^{a_1-1}1$, $g_n = g_{n-1}^{a_n}g_{n-2}$, $n\geq 2$, and then set
$g_\alpha=\lim_{n\to\infty} g_n$. Smith proved that $f_\alpha=g_\alpha$.

The definition of $g_\alpha$ just given is equivalent to the usual modern
definition \emph{standard Sturmian word with slope $\alpha$}. See, for
example, \cite{carpi+deluca2000,carstens+deuber+thumser+koppenrade1999,
christoffel1875,danilov1972,deluca1995,deluca1997}, or the chapter on
Sturmian words in \cite{berstel+seebold}.

\section{Descriptions of standard Sturmian words}

The following notation is fixed throughout the statements of the four
facts below. Let $\alpha$ be an irrational real number with $0<\alpha<1$,
and with simple continued fraction expansion $\alpha=[0,a_1,a_2,\ldots,a_n,\ldots]$.
Let $f_\alpha$ be the infinite binary word $f_\alpha=f_\alpha(1)f_\alpha(2)\cdots
f_\alpha(n)\cdots$, where $f_\alpha(n) = \ceil{(n+1)\alpha}-\ceil{n\alpha}$,
$n\geq1$. Furthermore, for $n\geq1$ let $p_n/q_n=[0,a_1,a_2,\ldots,a_n]$,
the $n$th \emph{convergent} of $\alpha$, where $p_n$ and $q_n$ are relatively
prime positive integers, and when $n\geq1$ let $X_n$ denote the initial
segment (prefix) of $f_\alpha$ of length $q_n$, that is, $X_n = f_\alpha(1)
f_\alpha(2)\cdots f_\alpha(q_n)$, $n\geq 1$. (Although for convenience we
shall often define $X_0 = 0$, it is not necessarily true that $X_0$ is a
prefix of $f_\alpha$.)

We can now restate Smith's result in the following way, as Fact \ref{f1}.

\begin{fact}\label{f1} (Fraenkel et al. \cite{fraenkel+mushkin+tassa1978},
Rosenblatt \cite{rosenblatt1978}, Shallit \cite{shallit1991}, Smith
\cite{smith1876}, Stolarsky \cite{stolarsky1976}): For each $n\geq2$,
$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$.) We emphasize that $X_n$ is a prefix of $f_\alpha$
when $n\geq1$, but $X_0=0$ need not be a prefix of $f_\alpha$.\end{fact}

As an illustration of this, if we take $\alpha=[0,2,1,1,\ldots]$, then $f_\alpha
= 0100101001001\cdots$, the famous \emph{Fibonacci word}. Here we have $f_\alpha
= \lim_{n\to\infty} X_n$, where $X_0 = 0$, $X_1 = 01$, $X_n = X_{n-1}X_{n-2}$,
and $X_n$ has \emph{length} $|X_n| = q_n$, where $q_0 = 1$, $q_1 = 2$, $q_n
= q_{n-1} + q_{n-2}$, $n\geq 2$.

\begin{fact}\label{f2} (Bernoulli \cite{bernoulli1772}, Cristoffel \cite{christoffel1875},
Markoff \cite{markoff1882}, Venkov \cite{venkov1970}): For each $t\geq1$, define the
morphism $k_t$ by $k_t(0) = 0^{t-1}1$, $k_t(1) = 0^t1$. For each $m\geq1$,
define $c_m = k_{a_1}\circ k_{a_2}\circ\cdots\circ k_{a_m}(0)$, where
$\circ$ denotes composition. Then $f_\alpha = c_1c_2c_3\cdots c_m\cdots$.
In fact, for each $n\geq 1$, $f_\alpha = (c_1c_2c_3\cdots c_n)(k_{a_1}\circ
k_{a_2}\circ\cdots\circ k_{a_n}(f_{\alpha_n})$, where $\alpha_n$ is defined
by $\alpha = [0,a_1,a_2,\ldots,a_n + \alpha_n]$.\end{fact}

\begin{fact}\label{f3} (Brown \cite{brown1991}): For each $t\geq 1$, define the
morphism $h_t$ by $h_t(0) = 0^{t-1}1$, $h_t(1) = 0^{t-1}10$. Then for
each $n\geq1$, $f_\alpha = h_{a_1}\circ h_{a_2}\circ\cdots\circ h_{a_n}
(f_{\alpha_n})$, where $\alpha_n$ is define by $\alpha_n = [0,a_1,a_2,
\ldots, a_n + \alpha_n]$.\end{fact}

The following fact is apparently new, although it follows easily from Fact
\ref{f2}.

\begin{fact}\label{f4} Define $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\geq2$. Then $f_\alpha = Z_1Z_2Z_3\cdots Z_n\cdots$.\end{fact}

To prove Fact \ref{f4}, define $c_m$ as in Fact \ref{f2}. Then by induction
on $m$, $c_m = Z_m$, $m\geq1$. The induction step is:
\begin{align*}
c_m
&= k_{a_1}\circ k_{a_2}\circ\cdots\circ k_{a_{m-1}}(k_{a_m}(0)) = k_{a_1}\circ k_{a_2}\circ\cdots\circ k_{a_{m-1}}(0^{a_m-1}1) \\
&= c_{m-1}^{a_m-1} (k_{a_1}\circ k_{a_2}\circ\cdots\circ k_{a_{m-1}})(1) = c_{m-1}^{a_m-1} (k_{a_1}\circ k_{a_2}\circ\cdots\circ k_{a_{m-2}})(0^{a_{m-1}}1) \\
&= c_{m-1}^{a_m-1} (k_{a_1}\circ k_{a_2}\circ\cdots\circ k_{a_{m-2}})(0)(k_{a_1}\circ k_{a_2}\circ\cdots\circ k_{a_{m-2}})(0^{a_{m-1}-1}1) \\
&= c_{m-1}^{a_m-1} (k_{a_1}\circ k_{a_2}\circ\cdots\circ k_{a_{m-2}})(0)(k_{a_1}\circ k_{a_2}\circ\cdots\circ k_{a_{m-1}})(0) \\
&= c_{m-1}^{a_m-1} c_{m-2}c_{m-1} = Z_{m-1}^{a_m-1}Z_{m-2}Z_{m-1} = Z_m
\end{align*}
Hence, $f_\alpha = c_1c_2c_3\cdots c_m\cdots = Z_1Z_2Z_3\cdots Z_n\cdots$.

\section{Applications}

\begin{appl} \label{a1} Let $F_n$ be the $n$th Fibonacci number, defined as usual
by $F_0=1$, $F_1=1$, $F_n = F_{n-1} + F_{n-2}$, $n\geq2$. We show that the
Fibonacci word $f = 0100101001001\cdots$ satisfies $f = \tilde{X}_1\tilde{X}_2
\tilde{X}_3\cdots\tilde{X}_n\cdots$, where $X_n$ is the initial segment of $f$
of length $F_n$, and $\tilde{X}_n$ is the \emph{reversal} of $X_n$. (Note that
here the length of $X_n$ is different from the length of $X_n$ in the illustration
following Fact \ref{f1}.)\end{appl}

To see this, take $\beta = [0,1,1,1,\cdots]$. Then, according to Fact \ref{f1}
applied to $f_\beta$ with $X_0=0$, $X_1=1$, $X_n=X_{n-1}X_{n-2},n\geq2$, we
know that for each $n\geq1$, $X_n$ is an initial segment of $f_\beta$. The
length of $X_n$ is $|X_n| = F_n$, where $F_0 = 1$, $F_1 = 1$, $F_n = F_{n-1}
+ F_{n-2}$, $n\geq2$. On the other hand, according to Fact \ref{f4}, with
$Z_0=0$, $Z_1=1$, $Z_n=Z_{n-2}Z_{n-1}$, $n\geq2$, we know that $f_\beta =
Z_1Z_2Z_3\cdots Z_n\cdots$. By induction, it is easy to see that $Z_n = \tilde{X}_n$,
$n\geq0$, where $\tilde{X}_n$ is the \emph{reversal} of $X_n$. Thus, $f_\beta
= \tilde{X}_1\tilde{X}_2\tilde{X}_3\cdots\tilde{X}_n\cdots$, where $X_n$ is
the initial segment of $f_\beta$ of length $F_n$. Since (as is easily seen)
$f_\beta$ is the \emph{complement} of the Fibonacci word (0's and 1's
interchanged), it follows that the Fibonacci word $f=0100101001001\cdots$
has the same property: $f = \tilde{X}_1\tilde{X}_2\tilde{X}_3\cdots\tilde{X}_n\cdots$,
where $X_n$ is the initial segment of $f$ of length $F_n$.

This can be compared with \cite{deluca1995}, where it is shown that $f=0100101001001\cdots
= \tilde{X}_3\tilde{X}_5\tilde{X}_7\cdots\tilde{X}_{2n+1}\cdots$. (However, note
that in \cite{deluca1995} it is shown in addition that the division $f= 0100101001001\cdots
= \tilde{X}_3\tilde{X}_5\tilde{X}_7\cdots\tilde{X}_{2n+1}\cdots$ has a certain
\emph{minimal} property with respect to the lexicographical order.)

\begin{appl}\label{a2} (Carstens et al. \cite{carstens+deuber+thumser+koppenrade1999}). Let $\alpha$ be an
irrational real number with $\alpha > 0$, and with $1/\alpha = [a_0,a_1,a_2,\cdots]$.
(Here we do not assume $\alpha < 1$.) Define two infinite words $C_\alpha = C_\alpha(1)
C_\alpha(2)\cdots C_\alpha(n)\cdots$ and $B_\alpha = b_1b_2\cdots b_n\cdots$ as follows.
For each $n\geq1$, $C_\alpha(n) = |\alpha\mathbb{N}\cap (n,n+1)|$; that is, $C_\alpha$
is the number of positive integer multiples of $\alpha$ which lie between $n$ and
$n+1$. Each $b_k,k\geq0$, is a word on the two symbols $a_0$ and $a_0+1$, defined
inductively by $b_0 = a_0$, $b_1 = a_0^{a_1-1}(a_0 + 1)$, $b_k = b_{k-1}^{a_k-1}
b_{k-2}b_{k-1}$, $k\geq2$. Then $C_\alpha = B_\alpha$.\end{appl}

The proof in \cite{carstens+deuber+thumser+koppenrade1999} is rather long and complicated. We now give a short
proof based on Fact \ref{f4}.

\begin{proof}Assume first that $\alpha>1$, so that $a_0=0$, and both $C_\alpha$
and $B_\alpha$ are binary words on $0,1$. Now $C_\alpha$ is the characteristic
function of the set $\{\ceil{k\alpha}:k\geq1\}$, since $C_\alpha(n)=1
\Leftrightarrow |\alpha\mathbb{N}\cap (n,n+1)| = 1 \Leftrightarrow (\exists k,n
< k\alpha < n + 1) \Leftrightarrow (\exists k,n = \ceil{k\alpha})
\Leftrightarrow n \in \{\ceil{k\alpha} :k\geq 1\}$. On the other hand, it is
easy to show (using $\alpha>1$) that the characteristic function of
$\{\ceil{k\alpha}:k\geq 1\}$ is in fact $f_{1/\alpha}$, where $f_{1/\alpha}(n)
= \ceil{(n+1)1/\alpha} - \ceil{n1/\alpha}$, $n\geq1$. Since $1/\alpha =
[0,a_1,a_2,\ldots]$, and the $b_k$'s are defined exactly as the $Z_k$'s are
defined in Fact \ref{f4} (applied to $1/\alpha$), Fact \ref{f4} now tells us
that $C_\alpha = f_{1/\alpha} = Z_1Z_2\cdots = b_1b_2\cdots = B_\alpha$.

Next, assume that $\alpha < 1$. Let $\frac1\alpha = [a_0,a_1,a_2,\ldots]$, so that
$\alpha = 1/a_0 + \alpha_1$, where $\alpha_1 = [0,a_1,a_2,\ldots] < 1$. It is easy
to see that $C_\alpha(n) = a_0 + f_{\alpha_1}(n)$, $n\geq1$ (where as usual
$f_{\alpha_1}(n) = \ceil{(n+1)\alpha_1} - \ceil{n\alpha_1}$). From the definition
of the word $B_\alpha$, we see (using Fact \ref{f4} applied to $\alpha_1$) that if
the symbol $a_0$ is replaced by 0, and $a_0 + 1$ is replaced by 1, the word
$B_\alpha$ is transformed into the word $f_{\alpha_1}$. Since $C_\alpha(n) = a_0
+ f_{\alpha_1}(n)$, $n\geq1$, it follows that $C_\alpha = B_\alpha$.\end{proof}

\begin{appl}\label{a3} In \cite{adams+davison1977,bohmer1926,danilov1972} are
three independent proofs of (a generalization of) the following result. A very
simple proof using Fact \ref{f1} is in \cite{anderson+brown+shiue1995}. (See
also \cite{borwein+borwein1993}.) Let $\tau = (-1 + \sqrt5)/2$, let $F_0 =
F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$, $n\geq2$. Then
\begin{align*}
\sum_{k=1}^\infty \frac{f_\tau(k)}{2^k}
&= \sum_{k=1}^\infty \left(\frac12\right)^{\ceil{k/\tau}}
= \sum_{k=1}^\infty \frac{\ceil{k\tau}}{2^k} \\
&= \sum_{k=1}^\infty \frac{(-1)^{k-1}}{(2^{F_k} - 1)(2^{F_{k-1}} - 1)} \\
&= [0, 2^0, 2^1, 2^1, 2^2, 2^3, \ldots, 2^{F_n}, \ldots].
\end{align*}\end{appl}

\begin{appl}\label{a4} (Brown \cite{brown1993}). Assume $0<\alpha<1$, with
$\alpha = [0,a_1,a_2,\ldots,a_n,\ldots]$, and for $n\geq1$, $p_n/q_n =
[0,a_1,a_2,\ldots,a_n]$, where $p_n$ and $q_n$ are relatively prime positive
integers. For $m\geq 2$, we find the \emph{Zeckendorf representation of
$m-1$} (see, for example, \cite{fraenkel1985}) by subtracting the largest
possible $q_i$ from $m-1$, and repeating, until finally we have $m-1 =
\sum_{j=1}^t z_jq_{j-1}$. Then $\ceil{m\alpha} = \sum_{j=1}^t z_jp_{j-1}$.
\end{appl}

(The result in Application \ref{a4}, in a somewhat more complex form, appears
in \cite{fraenkel+levitt+shimshoni1972}. The proof given in \cite{brown1993}
uses in a simple way a generalization of Fact \ref{f1}.)

\begin{appl}\label{a5} (Brown and Shiue \cite{brown+shiue1995-3}). By induction
on $n$, using Fact \ref{f1}, one can show that for $n\geq1$, $\sum_{k=1}^{q_n}
[k\alpha] = \frac12(p_nq_n - q_n + p_n + (-1)^n)$. (The proof given in
\cite{brown+shiue1995-3}, however, does not use Fact \ref{f1}.) More generally,
for any $m\geq1$, if $m=\sum_{j=1}^t z_jq_{j-1}$ is the \emph{Zeckendorf
representation} of $m$ (see Application \ref{a4}) then
\[ \sum_{k=1}^m \ceil{k\alpha} = \frac12\sum_{j=1}^t z_j(z_jp_{j-1}q_{j-1} - q_{j-1} + p_{j-1} + (-1)^{j-1}) + \sum_{1\leq i<j\leq t} z_iz_j p_{j-1}q_{j-1}.\]
\end{appl}

This leads to a formula for the function $C_\alpha(m) = \sum_{k=1}^m (\{k\alpha\} - \frac12)$
($\{\cdot\}$ denotes the fractional part), which was used in \cite{brown+shiue1995-3}
to give some improvements on results of Hardy and Littlewood \cite{hardy+littlewood1922-1,
hardy+littlewood1922-2}, and Ostrowski \cite{ostrowski1922}, and a simplified
proof of a theorem of S\'os \cite{sos1957}. (See also \cite{schoissengeier1986,
schoissengeier1984}.) One of the main results of \cite{hardy+littlewood1922-1,
hardy+littlewood1922-2,ostrowski1922} is that if $\alpha=[0,a_1,a_2,\ldots]$
and $a_i\leq A$ for all $i$, then, for some positive constant $c_A$, $C_\alpha(m)
> c_A\log m$ holds for infinitely many $m$, and $C_\alpha(m) < -c_A\log m$
holds for infinitely many $m$. We show in \cite{brown+shiue1995-3} (among other
things) that the same conclusions hold if the $a_i$ are bounded infinitely
often \emph{on the average}, that is, if $1/t\sum_{j=1}^t a_j\leq A$ for
infinitely many $t$.

One can also use Application \ref{a5} to prove an old formula of Lerch \cite{lerch1904}:
$\sum_{k=1}^m \ceil{k\alpha} + \sum_{k=1}^{\ceil{m\alpha}}\ceil{k1/\alpha} = m\ceil{m\alpha}$.
This proof seems a little complicated, and it was asked at the conference whether
there is not a more direct proof. Within a day or so, Jano Manuch showed the
author a very short completely elementary proof.


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

