%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-33/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{fact}{Fact}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem*{remark}{Remark}
\newtheorem*{ack}{Acknowledgements}

\title{A Characterization of the Quadratic Irrationals}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{A characterization of the quadratic irrationals}, Canad. Math.
  Bull. \textbf{34} (1991), 36--41.}\bigskip\end{center}

\begin{abstract}
Let $\alpha$ be a positive irrational real number, and let $f_\alpha(n) = [(n + 1)\alpha] - [n\alpha] - [\alpha]$, $n \geq 1$, where $[x]$ denotes the greatest integer not exceeding $x$. It is shown that the sequence $f_\alpha$ has a certain `substitution property' if and only if $\alpha$ is the root of a quadratic equation over the rationals.
\end{abstract}

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

The astronomer J. Bernoulli~\cite{bernoulli1772} considered the sequence $([(n + 1)\alpha + 1/2] - [n\alpha + 1/2]: n \geq 1)$, for positive irrational numbers $\alpha$, and gave (without proof) an explicit description of the terms of this sequence, based on the simple continued fraction expansion of $\alpha$.

A. A. Markov~\cite{markoff1882} proved the validity of Bernoulli's description, and did this by first describing the terms of the sequence $f_\alpha = (f_\alpha(n): n \geq 1)$, where $f_\alpha(n) = [(n + 1)\alpha] - [n\alpha] - [\alpha]$. A beautiful exposition (about 2 pages long) of Markov's proof is given by B. A. Venkov~\cite{venkov1970}.

K. B. Stolarsky~\cite{stolarsky1976} gave a different description of the sequence $f_\alpha$, for certain values of $\alpha$. A. S. Fraenkel, M. Mushkin, and U. Tassa~\cite{fraenkel+mushkin+tassa1978} gave a very short and polished proof which extended Stolarsky's result to all positive $\alpha$, including rational values. Both~\cite{stolarsky1976} and~\cite{fraenkel+mushkin+tassa1978} contain extensive lists of references.

Stolarsky gave two proofs of his result. In his second proof, he used Markov's theorem to show that if $\alpha = [0,k,k,\dots] = \frac{1}{k+}\frac{1}{k+} \frac{1}{k+} \dots$, then the sequence $f_\alpha$, which is a sequence of 0's and 1's, is invariant under the substitution $0 \mapsto B_1 = 0^{k-1}1, 1 \mapsto B_2 = 0^{k-1}10$. To say that $f_\alpha$ is invariant under this substitution means that if each 0 in $f_\alpha$ is replaced by the block $B_1$, and each 1 is replaced by $B_2$, then the resulting sequence is identical with $f_\alpha$. Here $0^{k-1}$ indicates a block of $k-1$ consecutive 0's, and if $k=1$ then $0^{k-1}$ is the empty block. (If $k = 3$, the substitution is $0 \mapsto 001$, $1 \mapsto 0010$.)
In this note we give a simple proof, which does not use Markov's theorem, of a generalization of Stolarsky's result. Our main results are based on the fact that if $\alpha$ is any quadratic irrational, then the simple continued fraction for $\alpha$ is periodic.

Throughout, we used the standard notation $[a_0,a_1,a_2,\dots]$ for the simple continued fraction $a_0 + 1/(a_1 + 1/(a_2 + \cdots))$.

We show that if $\alpha = [0,\overline{a_1,\dots,a_m}] = [0,a_1,\dots,a_m,a_1,\dots,a_m,\dots] = [0,a_1,\dots,a_m + \alpha]$ then there are blocks $B_1$ and $B_2$ (not both of length 1) such that $f_\alpha$ is invariant under the substitution $0 \mapsto B_1$, $1 \mapsto B_2$.

We also show that such blocks $B_1$ and $B_2$ cannot be found for \emph{all} quadratic irrationals $\alpha$.

However, we show that it is true that for every quadratic irrational $\alpha$, $f_\alpha$ is invariant under a substitution of the following kind. There always exist blocks $s,t,C_1,C_2$ of 0's and 1's (where $C_1$ is longer than $s$ or $C_2$ is longer than $t$) such that $f_\alpha$ may be written as a sequence of $s$'s and $t$'s, $C_1$ and $C_2$ may be written as blocks of $s$'s and $t$'s, and $f_\alpha$ is invariant under the substitution $s \mapsto C_1$, $t \mapsto C_2$. 

Finally, we show that if $f_\alpha$ is invariant under a substituion in the above sense, then $\alpha$ is a quadratic irrational. Thus the `substitution property' of $f_\alpha$ characterizes quadratics among the irrationals.

\section{Results} \label{sec: 2} 

We will make use of the sequence $g_\alpha = (g_\alpha(n): n \geq 1)$, the characteristic function of the sequence $([n\alpha]: n\geq 1)$, where $g_\alpha(n) = 1$ if $n = [k\alpha]$ for some $k$, and $g_\alpha(n) = 0$ otherwise. We will also use the fact (from the defnition of $f_\alpha$) that if $j$ is any integer with $0 \leq j < \alpha$, then $f_\alpha = f_{\alpha - j}$.

It will be convenient to use the notation $1/b = [0,b]$, $1/(a + 1/b) = [0,a,b]$, etc., for positive real numbers $a,b$.

We begin with a fact which is mentioned by Fraenkel, Mushkin, and Tassa~\cite{fraenkel+mushkin+tassa1978}:

\begin{lemma} \label{lemma: 1}
For any irrational $\alpha > 1$, $g_\alpha = f_{1/\alpha}$.
\end{lemma} 

\begin{proof} It is straightforward to show from the definitions of $g_\alpha$ and $f_{1/\alpha}$ that $g_\alpha(n) = 1 \Rightarrow f_{1/\alpha}(n) = 1$ and $g_\alpha(n) = 0 \Rightarrow f_{1/\alpha}(n) = 0$. 
\end{proof} 

\begin{defn} Let $k \geq 1$ be fixed, and let $w$ be any block of 0's and 1's or any sequence of 0's or 1's. Then $h_k(w)$ is obtained from $w$ by applying the substitution $0 \mapsto 0^{k-1}1$, $1 \mapsto 0^{k-1}10$, where $0^{k-1}$ is a block of $k-1$ consecutive 0's. That is, $h_k(w)$ is obtained from $w$ by replacing each 0 in $w$ by $0^{k-1}1$, and each 1 by $0^{k-1}10$. If $k=1$ the substitution is $0 \mapsto 1$, $1 \mapsto 10$.
\end{defn}

\begin{lemma} \label{lemma: 2}
Let $k \geq 1$ and $\alpha$ be given, where $\alpha$ is irrational and $0 < \alpha < 1$. Then $h_k(f_\alpha) = g_{k + \alpha}= f_{1/(k + \alpha)}$.
\end{lemma}

\begin{proof} By definition,
\[ f_{\alpha} = f_\alpha(1) f_\alpha(2) \cdots f_\alpha(j) \cdots, \]
where 

\[ f_\alpha(j) = [(j + 1)\alpha] - [j\alpha], \quad j \geq 1, \]
and 
\[ h_k(\alpha) = D_1D_2 \cdots D_q D_{q + 1} \cdots, \]
where 
\[ D_j = h_k(f_\alpha(j)), \quad j \geq 1. \]
Note that each block $D_j$ contains exactly one ``1", which is in the $k$th position, and has length either $k$ or $k + 1$.

Consider $h_k(f_\alpha)$ now as a sequence of 0's and 1's, and let $n$ be the position in this sequence of the $(q + 1)^{\textup{st}}$ ``1", that is, the 1 in the block $D_{q + 1}$. Then 
\[ n = L(D_1D_2 \cdots D_q) + k, \]
where $L(D_1D_2 \cdots D_q)$ denotes the \emph{length} of $D_1D_2 \cdots D_q$. 

Since the block $D_j$ has length $k$ if $f_\alpha(j) = 0$ and has length $k + 1$ if $f_\alpha(j) = 1$, it follows that 
\[ L(D_1D_2 \cdots D_q) = qk + f_\alpha(1) + \cdots + f_\alpha(q). \]
Since $f_\alpha(j) = [(j + 1)\alpha] - [j\alpha]$, and $[\alpha] = 0$, the sum telescopes to 
\[ L(D_1D_2 \cdots D_q) = qk + [(q + 1)\alpha]. \]
Thus $n$, the position of the $(q + 1)^{\textup{st}}$ ``1" in the sequence $h_k(f_\alpha)$ satisfies
\[ n = qk + [(q + 1)\alpha] + k = [(q + 1)(k + \alpha)]. \]
Thus $[h_k(f_\alpha)(n) = 1] \Leftrightarrow [n = [(q + 1)(k + \alpha)]$ for some $q \geq 0] \Leftrightarrow [g_{k + \alpha} (n) = 1]$. That is, $h_k(f_\alpha) = g_{k + \alpha}$.

Using Lemma~\ref{lemma: 1}, this gives
\[ h_k(f_\alpha) = g_{k + \alpha} = f_{1/(k + \alpha)}. \qedhere \]
\end{proof}

\begin{thm} \label{thm: 1}
Let $\alpha = [0,\overline{a_1,\dots,a_m}]$. Then $f_\alpha$ is invariant under the substitution
\begin{align*}
0 &\mapsto B_1 = h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_m}(0) \\
1 &\mapsto B_2 = h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_m}(1), 
\end{align*}
where $\circ$ denotes composition.
\end{thm}

\begin{proof} By Lemma~\ref{lemma: 2}, we have $h_{a_m}(f_\alpha) = f_{1/(a_m + \alpha)} = f_{[0,a_m + \alpha]}$, $h_{a_{m -1}} \circ h_{a_m}(f_\alpha) = f_{1/(a_{m-1} + [0,a_m + \alpha])} = f_{[0,a_{m-1}, a_{m} + \alpha]}, \dots, h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_{m}}(f_\alpha) = f_\beta$, where $\beta = [0,a_1,a_2,\dots,a_m + \alpha] = \alpha$. 
\end{proof}

\begin{remark}
The blocks $B_1 = h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_{m}}(0)$ and $B_2 = h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_{m}}(1)$ can be described as follows. Let $S_0 = 0$, $S_1 = 0^{a_1 - 1}1$, and for $2 \leq j \leq m$, let $S_j = (S_{j-1})^{a_j}S_{j-2}$. Then $B_1 = S_m$, and $B_2 = S_mS_{m-1}$. This can be seen by induction on $m$.
\end{remark}

\begin{cor} 
For any block $w$ of 0's and 1's, let $H(w)$ be obtained from $w$ by replacing each 0 by $B_1$, and each 1 by $B_2$. (That is, $H = h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_{m}}.$) Then $f_\alpha$ can be generated by starting with $w = f_\alpha(1)$ and repeatedly replacing $w$ by $H(w)$.
\end{cor}

\begin{proof} Let $E_1 = f_\alpha(1)$ and for $k \geq 1$ let $E_{k + 1} = H(E_k)$. Then by the Theorem and induction, each $E_k$ is an initial segment of $f_\alpha$.
\end{proof}

\begin{thm} \label{thm: 2}
Let $\beta > 0$ be any quadratic irrational. Since $f_\beta = f_{\beta - [\beta]}$, assume without loss of generality that $0 < \beta < 1$, so that (for suitable $a_i, b_j$) $\beta = [0,b_1,\dots,b_q, \overline{a_1,\dots,a_m}]$. Let 
\begin{align*} s &= h_{b_1} \circ h_{b_2} \circ \cdots \circ h_{b_q}(0) \\
t &= h_{b_1} \circ h_{b_2} \circ \cdots \circ h_{b_q}(1), \end{align*}
and 
\begin{align*} C_1 &= h_{b_1} \circ h_{b_2} \circ \cdots \circ h_{b_q} \circ h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_m}(0) \\
C_2 &= h_{b_1} \circ h_{b_2} \circ \cdots \circ h_{b_q} \circ h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_m}(1). 
\end{align*}
Then $f_\beta$, $C_1,C_2$, can be written as sequences of $s$'s and $t$'s and $f_\beta$ is invariant under the substitution $s \mapsto C_1, t \mapsto C_2$.
\end{thm}

\begin{proof}
Let $\alpha = [0,\overline{a_1,\dots,a_m}]$, so that $\beta = [0,b_1,b_2,\dots,b_q + \alpha]$. Let $H_1 = h_{b_1} \circ h_{b_2} \circ \cdots \circ h_{b_q}$, $H_2 = h_{a_1} \circ h_{a_2} \circ \cdots \circ h_{a_m}$, $B_1 = H_2(0)$, $B_2 = H_2(1)$. Then we have $s = H_1(0)$, $t = H_1(1)$, and $C_1 = H_1(B_1)$, $C_2 = H_1(B_2)$, so that $C_1, C_2$ can be written as blocks of $s$'s and $t$'s.

By the proof of Theorem~\ref{thm: 1}, $H_1(f_\alpha) = f_\beta$, so that $f_\beta$ can be written as a sequence of $s$'s and $t$'s, and $H_2(f_\alpha) = f_\alpha$. Note that $H_1(f_\alpha) = f_\beta$ is obtained from $f_\alpha$ by applying the substitution $0 \mapsto s, 1 \mapsto t$, and $H_2(f_\alpha) = f_\alpha$ is obtained by applying the substituion $0 \mapsto B_1, 1 \mapsto B_2$. 

Therefore we can transfrom $f_\beta$ into $f_\beta$ by successively applying the substitutions $[s \mapsto 0, t \mapsto 1]$, $[ 0 \mapsto B_1, 1 \mapsto B_2]$, and $[B_1 \mapsto C_1, B_2 \mapsto C_2]$, which transform $f_\beta$ into $f_{\alpha}$, $f_{\alpha}$ into $f_\alpha$, and $f_\alpha$ into $f_\beta$ respectively.
\end{proof}

\begin{thm} \label{thm: 3}
Let $\beta = [0,5,1,1,1,\dots]$. Then there do not exist non-trivial blocks $B_1,B_2$ of 0's and 1's such that $f_\beta$ is invariant under the substitution $0 \mapsto B_1, 1 \mapsto B_2$.
\end{thm} 

\begin{proof} Let $\alpha = [0,1,1,\dots] = (\sqrt{5} - 1)/2$. Then $f_\alpha(1) = 1$, and by Theorem~\ref{thm: 1}, $f_\alpha$ is invariant under $0 \mapsto 1, 1 \mapsto 10$, so $f_\alpha = 10110\cdots$. By the proof of Theorem~\ref{thm: 1}, $h_5(f_\alpha) = f_\beta$, so $f_\beta = tstts\cdots$, where $s = 00001$, $t = 000010$. Thus
\begin{align*} 
f_\beta &= 000010 \: 00001 \: 000010 \: 000010 \: 00001 \: 000010 \: 00001 \: 000010 \cdots \\
&= \quad \: t \qquad \: \: \: s \qquad \: \: t \qquad \: \: \: \; t \qquad \: \: s \qquad \: \: \: t \qquad \: \: s \qquad \: \: \: t \cdots. \end{align*}

It was shown by Karhumaki~\cite{karhumaki1983} that the sequence $f_\alpha = 10110\cdots$ does not contain any $4$th power. That is, $f_\alpha$ contains no non-empty block of the form $DDDD$. (Se also~\cite{berstel1980} and~\cite{restivo1989}.) Thus also the sequence $f_\beta = tsttstst \cdots$, \emph{when regarded as a sequence of $s$'s and $t$'s}, contains non non-empty block of the form $DDDD$, \emph{where $D$ is a block of $s$'s and $t$'s}.

Now suppose that $f_\beta$ is invariant under $0 \mapsto B_1$, $1 \mapsto B_2$, and for any block or sequence $w$ of 0's and 1's, let $H(w)$ be the result of applying this substitution to $w$. Note that $f_\beta = H(f_\beta) = B_1B_1B_1B_1B_2 \cdots$, so that $B_1$ is some initial segment of $f_\beta$.

Our goal is to show that $B_1$ can be written as a block of $s$'s and $t$'s, which form an initial segment of $f_\beta$, \emph{when $f_\beta$ is regarded as a sequence of $s$'s and $t$'s}. Since $f_\beta = B_1B_1B_1 \cdots$, this will contradict Karhumaki's result, and the proof will be finished. 

To this end, first note that the block $B_1$ must contain at least one ``1", since otherwise, by the Corollary to Theorem~\ref{thm: 1}, $f_\beta$ would be identically $0$. Note also that $f_\beta$ consists of blocks of either 4 or 5 consecutive 0's separated by single 1's. This implies that the block $B_1$ ends either with 1 or with 10, since otherwise $f_\beta = H(f_\beta) = B_1B_1 \cdots$ would contain a block of more than five consecutive 0's. (For example if $B_1 = C100$, then since $C = 00001D$ (which is true since $B_1$ is an initial segment of $f_\beta = 000010\cdots$), we would have 
\[ f_\beta = H(f_\beta) = B_1B_1 \cdots = C100C100\cdots = C10000001D100\cdots, \]
with too many consecutive 0's.)

Suppose now that $B_1$ \emph{fails} to be an initial segment of $s$'s and $t$'s in $f_\beta$ (when $f_\beta$ is regarded as a sequence of $s$'s and $t$'s).

If $B_1$ ends in $0$, then $B1 = Cs0$, where $Cs$ is an initial segment of $s$'s and $t$'s in $f_\beta$ (when $f_\beta$ is regarded as a sequence of $s$'s and $t$'s). Note that $C = 00001D$. Then since $Cs$ is an initial segment of $f_\beta$, we have $f_\beta = Cs\underline{0000}1 \cdots$, but also we have
\[ f_\beta = H(f_\beta) = B_1B_1 \cdots = Cs0Cs0 \cdots = Cs \underline{0 \: 00001} Ds0 \cdots, \]
a contradiction.

If $B_1$ ends in 1, then $B_1 = C00001$, where $Ct$ is an initial segment of $s$'s and $t$'s in $f_\beta$ (when $f_\beta$ is regarded as a sequence of $s$'s and $t$'s). Note again that $C = 00001D$. Then since $Ct$ is an initial segment of $f_\beta$, we have $f_\beta = Ct \cdots = C00001\underline{0\: 00001} \cdots$, but also we have 
\[ f_\beta = H(f_\beta) = B_1B_1 \cdots = C00001C00001 \cdots = C00001\underline{0000}1D00001 \cdots , \]
a contradiction.

Thus we have shown that if $f_\beta$ is invariant under a substitution $0 \mapsto B_1, 1 \mapsto B_2$, then $B_1$ can be written as a block of $s$'s and $t$'s, which form an initial segment of $f_\beta$, \emph{when $f_\beta$ is regarded as a sequence of $s$'s and $t$'s}. This gives the desired contradiction to Karhumaki's result, and completes the proof.
\end{proof}

\begin{thm} \label{thm: 4} 
Let $\alpha$ be a positive irrational real number, and let $f_\alpha$ be written as a sequence on $s,t$, where $s,t$ are blocks of 0's and 1's. Let $C_1,C_2$ be blocks of $s$'s and $t$'s such that $f_\alpha$ is invariant under the non-trivial substitution $s \mapsto C_1, t \mapsto C_2$. Then $\alpha$ is a quadratic irrational.
\end{thm}

\begin{proof} 
First consider the case where $0 < \alpha < 1$ and $s = 0$, $t = 1$. Suppose that $C_1$ contains $a$ 0's and $b$ 1's, and that $C_2$ contains $c$ 0's and $d$ 1's.

For any block $w$ of $0$'s and 1's, let $H(w)$ denote the word obtained from $w$ by replacing each 0 by $C_1 $ and each 1 by $C_2$. Let $E_1 = H(f_\alpha(1))$ and for $p \geq 1$ let $E_{p + 1} = H(E_p)$. Let $e_p$ denote the number of 1's which occur in the block $E_p$. Since the number of 1's which occur in the block $f_\alpha(1) f_\alpha(2) \cdots f_\alpha(n)$ is $f_\alpha(1) + f_\alpha(2) + \cdots f_\alpha(n)$, which equals $[(n + 1)\alpha]$, we have $e_p = [(L(E_p) + 1)\alpha]$. Also, $e_{p + 1} = e_pd + (L(E_p) - e_p)b$, and $L(E_{p + 1}) = e_p (c + d) + (L(E_p) - e_p)(a + b)$, so that 
\[ \frac{e_{p + 1}}{L(E_{p + 1})} = \frac{\frac{e_pd}{L(E_p)} + (1 - \frac{e_p}{L(E_p)})b}{\frac{e_p(c + d)}{L(E_p)} + (1 - \frac{e_p}{L(E_p)})(a + b)} . \]
Taking the limit as $p \to \infty$, we obtain
\[ \alpha = \frac{\alpha + (1 - \alpha)b}{\alpha(c + d) + (1 - \alpha)(a + b)}, \]
so that $\alpha$ is a quadratic irrational.

The general case can be handled similarly. We omit the details.
\end{proof}


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