%%%% 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 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}