%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-27/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{thrm}{Theorem}
\newtheorem{fact}{Fact}
\newtheorem{lmma}{Lemma}
\newtheorem*{ackn}{Acknowledgement}

\title{Sums of Fractional Parts of Integer Multiples of an Irrational}
\author{
Tom C. Brown\footnote{Department of Mathematics and Statistics, Simon Fraser University, Burnaby, British Columbia, V5A 1S6, Canada. \texttt{tbrown@sfu.ca}} and
Peter Jau-shyong Shiue\footnote{Department of Mathematical Sciences, University of Nevada, Las Vegas, NV, USA 89154-4020. \texttt{shiue@nevada.edu}}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown} and P.J.-S. {Shiue}, \emph{Sums of fractional parts of integer multiples of an irrational},
  J. Number Theory \textbf{50} (1995), 181--192.}\bigskip\end{center}

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

\begin{abstract}Let $\alpha$ be a positive irrational real number, and let $C_\alpha(n)
= \sum_{1\leq k\leq n}(\{k\alpha\}-\frac12)$, $n\geq1$, where $\{x\}$ denotes the
fractional part of $x$. We give an explicit formula for $C_\alpha(n)$ in terms
of the simple continued fraction for $\alpha$, and use this formula to give
simple proofs of several results of A. Ostrowski, G. H. Hardy and J. E. Littlewood,
and V. T. S\'os. We also show that there exist positive constants $d_A$ such
that if $\alpha = [a_0,a_1,a_2,\ldots]$ and $(1/t)\sum_{1\leq j\leq t}a_j\leq A$
holds for infinitely many $t$, then $C_\alpha(x) > d_A\log x$ and $C_\alpha(x)
< - d_A\log x$ each hold for infinitely many $x$.
\end{abstract}

\section{Introduction \label{s1}}

For real numbers $\beta$, let us agree to write $\{\beta\}$ for the
fractional part of $\beta$, that is, $\{\beta\} = \beta-\floor{\beta}$, where
$\floor{\beta}$ is the greatest integer less than or equal to $\beta$.

For an irrational number $\alpha$, $0<\alpha<1$, and for integers $n\geq1$,
we write
\[ C_\alpha(n) = \sum_{1\leq k\leq n} (\{k\alpha\} - \frac12). \]

There are a number of papers dealing with estimates of $C_\alpha(n)$ as
a function of $n$. Most of the known results are contained in two long
1922 papers by G. H. Hardy and J. E. Littlewood \cite{hardy+littlewood1922-1,
hardy+littlewood1922-2}, a long 1922 paper by A. Ostrowski \cite{ostrowski1922},
and a 1957 paper by Vera T. S\'os \cite{sos1957}. Further references can
be found in \cite{shallit1992}.

In the present note we give a simple and self-contained proof of a formula
for $C_\alpha(n)$ which is more explicit than those which have appeared
before, namely in \cite{ostrowski1922,sos1957}. We then use this formula
to derive several of the main results in \cite{hardy+littlewood1922-1,
hardy+littlewood1922-2,ostrowski1922} and the main result in \cite{sos1957}.
It seems to us that our proofs are far simpler than those given previously.
In some cases they lead to improvements.

In addition, we extend one of the main results in \cite{hardy+littlewood1922-2,
ostrowski1922}. Ostrowski and Hardy and Littlewood showed independently that
there exist positive constants $c$ and $c_A$ with the following properties.
If $\alpha$ is an arbitrarily positive irrational number, then the inequality
$|C_a(x)|>c\log x$ holds for infinitely many $x$. If $\alpha=[a_0,a_1,a_2,
\ldots]$ and $a_i\leq A$ for all $i$, then $C_a(x)> c_A\log x$ and $C_a(x)
< - c_A\log x$ each hold for infinitely many $x$. (Hardy and Littlewood
\cite{hardy+littlewood1922-2} call the proofs of these two results the most
difficult in their paper. They give no values for the constants $c$ and $c_A$.
Ostrowski gives $c\geq\frac1{720}$ and $c_A\geq1/8(A+1)^6$.) We show that
there exist positive constants $d_A$ such that if $\alpha[a_0,a_1,a_2,\ldots]$
and $(1/5)\sum_{1\leq j\leq t}a_j\leq A$ holds for infinitely many $t$, then
$C_\alpha(x) > d_A\log x$ and $C_\alpha(x) < - d_A\log x$ each hold for
infinitely many $x$. (We show that $d_A\geq 1/(7\cdot64(A+1)^2\log(A+1))$.
Since $c_A\geq d_A$, this improves Ostrowski's bound. We also show that
$c\geq\frac1{256}$.)

\section{Notation\label{s2}}

Let $\alpha$ be a positive irrational real number, and let
\[ \alpha = a_0 + \frac1{a_1 + \frac1{a_2 + \cdots }} \]
be the simple continued fraction for $\alpha$, which we abbreviate as
$\alpha = [a_0,a_1,a_2,\ldots]$. We write $p_n/q_n = [a_0,a_1,a_2,\ldots,
a_n]$ and $d_{2k} = q_{2k}\alpha-p_{2k}$, $d_{2k+1} = p_{2k+1}-q_{2k+1}
\alpha$, $k\geq0$. Then $p_n = a_np_{n-1}+p_{n-2}$, $q_n = a_nq_{n-1}+
q_{n-2}$, $n\geq2$, $p_{2k}/q_{2k}<\alpha<p_{2k+1}/q_{2k+1}$, $k\geq0$,
and $0<d_n<1/q_{n+1}$, $n\geq0$.

\section{A formula for $C_\alpha(n)$\label{s3}}

Throughout this section, $\alpha$ is a fixed irrational number, $0<\alpha<1$,
$\alpha = [a_0,a_1,a_2,\ldots]$. Let us use the notation
\[ S_\alpha(n) = \sum_{1\leq k\leq n}\floor{k\alpha}, \qquad n\geq1. \]

\begin{lmma}\label{l1} If $1\leq k\leq q_n$, then $\floor{k\alpha} =
\floor{k(p_n/q_n)}$. Also, $\floor{q_n\alpha} = p_n$, $n$ even, $\floor{
q_n\alpha} = p_n-1$, $n$ odd.\end{lmma}
\begin{proof} This follows from $d_n<1/q_{n+1}$.\end{proof}

\begin{lmma}\label{l2} For $n\geq1$,
\begin{align*}
S_\alpha(q_n) &= \frac12(p_nq_n - q_n + p_n + (-1)^n), \\
C_\alpha(q_n) &= \frac12(-1)^n(d_n(q_n+1) - 1).
\end{align*}
\end{lmma}
\begin{proof} The second part follows from the first using $\floor{\beta}
+ \{\beta\} = \beta$ and the definition of $d_n$. To prove the first part,
observe that since $(p_n,q_n) = 1$, $kp_n$ runs through all the non-zero
residue classes modulo $q_n$, therefore
\[ \sum_{1\leq k\leq q_n-1}\fp{k\frac{p_n}{q_n}} = \sum_{1\leq t\leq q_n-1} \frac{t}{q_n} = \frac{q_n - 1}2, \]
hence
\[ \sum_{1\leq k\leq q_n-1}\floor{k\frac{p_n}{q_n}} = \sum_{1\leq k\leq q_n-1}
\left(k\frac{p_n}{q_n} - \fp{k\frac{p_n}{q_n}}\right) = \frac{(p_n-1)(q_n-1)}2. \]
Now apply Lemma \ref{l1}.\end{proof}

\begin{lmma}\label{l3} If $n\geq1$, $q_n\leq N<q_{n+1}$, $N=bq_n+k$, $1\leq k<q_n$,
then $\floor{N\alpha} = bp_n + \floor{k\alpha}$. If $N = bq_n$, then $\floor{N
\alpha} = bp_n-1$ if $n$ is odd, $\floor{N\alpha} = bp_n$ if $n$ is even.\end{lmma}
\begin{proof} Assume $N = bq_n + k$, $1\leq k <q_n$. Let $L = \floor{k(p_n/q_n)}$.
Then $L+1/q_n\leq k(p_n/q_n)\leq L + (q_n-1)/q_n$. If $n$ is even, then $0<(bq_n
+k)(\alpha-p_n/q_n)<q_{n+1}/q_{n+1}q_n=q_n$, or $0<N\alpha-bp_n-k(p_n/q_n)<1/q_n$.
Adding to the second preceding inequality gives $L<N\alpha-bp_n<L+1$, hence
$\floor{N\alpha} = bp_n + L = bp_n+\floor{k(p_n/q_n)} = bp_n + \floor{k\alpha}$.
(For the last equality we used Lemma \ref{l1}.)

If $n$ is odd the calculation is similar. The second statement of the lemma is
easy. (Actually, even more is true, namely if $0<q<q_{n+1}$, then $\floor{(q+q_n)
\alpha} = p_n + \floor{q\alpha}$; see \cite{fraenkel+mushkin+tassa1978}.)
\end{proof}

\begin{lmma}\label{l4}\begin{enumerate}
\item[(a)] Let $n\geq1$, $q_n<bq_n+m<q_{n+1}$, $1\leq m<q_n$. Then
\[ S_\alpha(bq_n + m) = S_\alpha(bq_n) + S_\alpha(m) + mbp_n. \]
\item[(b)] Let $n\geq1$, $q_n<bq_n<q_{n+1}$. Then
\[ S_\alpha(bq_n) = \frac12b(bp_nq_n - q_n + p_n + (-1)^n). \]
\end{enumerate}\end{lmma}
\begin{proof}\begin{enumerate}
\item[(a)]\begin{align*}
S_\alpha(bq_n + m)
&= \sum_{1\leq k\leq bq_n+m} \floor{k\alpha} = S_\alpha(bq_n) + \sum_{1\leq k\leq m}\floor{(bq_n+k)\alpha} \\
&= S_\alpha(bq_n) + \sum_{1\leq k\leq m} (bp_n + \floor{k\alpha}).
\end{align*}
\item[(b)] For $b=1$, Lemma \ref{l2} applies. Now induction using part
(a) does the rest.
\end{enumerate}\end{proof}

\begin{lmma}\label{l5}\begin{enumerate}
\item[(a)] Let $n\geq1$, $q_n<bq_n+m<q_{n+1}$, $1\leq m<q_n$. Then
\[ C_\alpha(bq_n + m) = C_\alpha(bq_n) + C_\alpha(m) + mb(q_n\alpha - p_n). \]
\item[(b)] Let $n\geq1$, $q_n\leq bq_n<q_{n+1}$. Then
\[ C_\alpha(bq_n) = \frac12(-1)^nb(d_n(bq_n+1)-1). \]
\end{enumerate}\end{lmma}
\begin{proof} These follow from Lemma \ref{l4}. \end{proof}

\begin{thrm}\label{t1}
For any $m\geq1$, let $m=z_tq_{t-1} + \cdots + z_2q_1 + z_1q_0$, where
\begin{enumerate}
\item $0\leq z_1\leq a_1 - 1$,
\item $0\leq z_i\leq a_i$, $2\leq i \leq t$,
\item If $z_i = a_i$ then $z_{i-1} = 0$, $2\leq i\leq t$.
\end{enumerate}
(This is the so-called ``Zeckendorff representation of $m$.'' To find it, subtract
the largest possible $q_j$ from $m$ and repeat.)
\begin{enumerate}
\item[(a)]
\[ S_\alpha(m) = \frac12\sum_{1\leq i\leq t} z_i(z_ip_{i-1}q_{i-1} - q_{i-1} + p_{i-1} + (-1)^{i-1}) + \sum_{1\leq i<j\leq t}z_iz_jq_{i-1}p_{j-1}.\]
\item[(b)]
\[ C_\alpha(m) = \frac12\sum_{1\leq i\leq t} (z_i(q_{i-1}\alpha - p_{i-1})(z_iq_{i-1} + 1) + (-1)^iz_i) + \sum_{1\leq i<j\leq t}z_iz_jq_{i-1}(q_{j-1}\alpha - p_{j-1}).\]
\item[(c)]
\[ C_\alpha(m) = \sum_{1\leq j\leq t} (-1)^jz_j\left(\frac12 - d_{j-1}\left(m_{j-1}+\frac12z_jq_{j-1}+\frac12\right)\right), \]
where $m_j=\sum_{1\leq i\leq j} z_iq_{i-1}$, $m_0 = 0$.
\end{enumerate}\end{thrm}
\begin{proof} Part (a) follows from Lemma \ref{l4} by induction on $t$. Part
(b) then follows from part (a) (or from Lemma \ref{l5} and induction). Part
(c) is a rearrangement of part (b).\end{proof}

\section{A Bound for $\max_{0<m<q_t}|C_\alpha(m)|$\label{s4}}

\begin{thrm}\label{t2} For $t\geq1$,
\[ \frac1{32}\sum_{1\leq j\leq t}(a_j - 1) < \max_{0<m<q_t}|C_\alpha(m)| < \frac12\sum_{1\leq j\leq t}a_j. \]
\end{thrm}
\begin{proof} Let $m =\sum_{1\leq j\leq t}z_jq_{j-1}$. Since $0<m_{j-1}+\frac12z_jq_{j-1}
+\frac12\leq q_j$ and $0<d_{j-1}<1/q_j$, Theorem \ref{t1}(c) gives $|C_\alpha(m)|<\frac12
\sum_{1\leq j\leq t} z_j\leq\frac12\sum_{1\leq j\leq t}a_j$.

For the other side, define $M_1=\sum_{1\leq j\leq t} z_jq_{j-1}$ by $z_j=\floor{a_j/2}$
if $j$ is odd, $z_j = 0$ if $j$ is even. Then $m_j\leq\sum_{1\leq i\leq t}(a_i/2)q_{i-1}
\leq(q_j-1)/2$, so if $j$ is odd, $m_{j-1}+\frac12z_jq_{j-1}+\frac12 = m_{j-2} + \frac12
\floor{a_j/2}q_{j-1} + \frac12\leq\frac12(q_{j-1} - 1 + \frac14a_jq_{j-1}+1) = \frac14
(2q_{j-2} + a_jq_{j-1}) = \frac14(q_j + q_{j-2})<\frac38q_j$, therefore $C_\alpha(M_1)
< - \sum_{j\text{ odd}} z_j(\frac12-\frac38) = -\frac18\sum_{j\text{ odd}} z_j \leq -
\frac1{16}\sum_{j\text{ odd}}(a_j-1)$. Define $M_2 = \sum_{1\leq j\leq t} z_jq_{j-1}$
by $z_j=\floor{a_j/2}$ if $j$ is even, $z_j = 0$ if $j$ is odd; then a similar calculation
gives $C_\alpha(M_2)>\frac1{16}\sum_{j\text{ even}}(a_j-1)$. Thus $C_\alpha(M_2) - C_\alpha
(M_1) > \frac1{16}\sum_{1\leq j\leq t}(a_j-1)$, therefore $\frac1{32}\sum_{1\leq j\leq t}
(a_j-1)<\max_{0<m<q_t}|C_\alpha(m)|$.
\end{proof}

\section{Known Asymptotic Bounds and Inequalities for $C_\alpha(n)$\label{s5}}

The following facts are known, but the proofs we give are simpler (and shorter)
than those given before. In some cases our results are slight improvements. We
use the notation $\alpha=[0,a_1,a_2,\ldots]$ for each $\alpha$, $0<\alpha<1$.

\begin{fact}\label{f1} (Sierpenski \cite{sierpinski1909}). For every $\alpha$,
$C_\alpha(n) = o(n)$.\end{fact}
\begin{proof} Given $\alpha=[0,a_1,a_2,\ldots]$ and $\epsilon>0$, choose $n$
so that $(\sqrt2)^{-(n-1)} <\epsilon$, and let $P = a_1 + \cdots + a_n$.
Choose $s>n$ so that $P/q_n<\epsilon$. For $m\geq q_s$, let $m=\sum_{1\leq
j\leq t + 1}z_jq_{j-1}$; then $t\geq s$ and $z_{t+1}\geq1$. Then
\begin{align*}
\frac1m|C_\alpha(m)|
&< \frac1{2m}\sum_{1\leq j\leq t}z_j \leq \frac12\frac{P}{q_t} + \frac12\frac{\sum_{n+1\leq j \leq t + 1}z_j}{\sum_{n+1\leq j\leq t + 1}z_jq_{j-1}} \\
&< \frac12\epsilon + \frac12\frac{\sum_{n+1\leq j\leq t + 1}z_j}{(\sqrt2)^{n-1}\sum_{n+1\leq j\leq t + 1}z_j} < \epsilon.
\end{align*}
(Here we used $q_n>(\sqrt2)^{n-1}$.)\end{proof}

\begin{fact}\label{f2} (Lerch (without proof) \cite{lerch1904}, Hardy and
Littlewood \cite{hardy+littlewood1922-1}, and Ostrowski \cite{ostrowski1922}
have this result under the stronger hypothesis that $a_i\leq A$ for all $i$.)
If $\alpha=[0,a_1,a_2,\ldots]$ and $(1/t)\sum_{1\leq j \leq t}a_j\leq A$ for
all $i$, then $C_\alpha(n) = O(\log n)$. In fact,
\[ |C_\alpha(n)| < \frac{A}{2\log\tau}\log n + \left(\frac{\log\sqrt5}{2\log\tau}-\frac12\right)A,
\qquad n\geq 2,\text{ where } \tau = \frac{1+\sqrt5}2. \]
Consequently, $|C_\alpha(n)|<\frac32A\log n$, $n\geq1$, and for every
$\epsilon>0$ there is $N_0$ such that $|C_\alpha(n)| < (1/(2\log\tau)
+\epsilon)A\log n$, $n\geq N_0$. In particular, $|C_\alpha(n)|<(1.04)
A\log n$, $n\geq N_0$.\end{fact}
\begin{proof} Let
\[ \frac{P_n}{Q_n} = \overbrace{[1,1,\ldots,1]}^{n+1}. \]
Then $Q_0 = Q_1 = 1$, $Q_{n+1} = Q_n + Q_{n-1}$, and $Q_t = (1/\sqrt5)
(\tau^{t+1} - (-1/\tau)^{t+1}) > (1/\sqrt5)(\tau^{t+1} - 1)$. Since
$|C_\alpha(q_t)|<\frac12$, we can assume without loss of generality
that $q_t<n<q_{t+1}$. Then $\sqrt5n > \sqrt5q_t+1\geq\sqrt5Q_t+1>
\tau^{t+1}$, so $t+1<(\log\sqrt5 + \log n)/\log\tau$, $\frac12t <
\frac12(\log\sqrt5/\log\tau - 1) + \log n/(2\log\tau)$. Since
$|C_\alpha(n)|<\frac12\sum_{1\leq j\leq t}a_j\leq \frac12tA$, the
result follows.\end{proof}

\begin{fact}\label{f3} If $f(n) = o(n)$, then there exists $\alpha$ such that
\[ \limsup_{n\to\infty}\left|\frac{C_\alpha(n)}{f(n)}\right| = \infty. \]
\end{fact}
\begin{proof} Assume that $f(n)>0$ for all $n$. Suppose $a_1,\ldots,a_t$
have already been chosen. Choose $M$ so that $f(x)/x<1/64(t+1)q_t$, $x>M$.
Let $P = \max\{f(x):1\leq x\leq M\}$. Choose $a_{t+1}\geq 3$ so that
$\frac1{32}(a_{t+1}-1)>(t+1)P$. Finally, choose $x$, $0<x<q_{t+1}$, so
that $\frac1{32}(a_{t+1} - 1)\leq \frac1{32}\sum_{1\leq j\leq t + 1}
(a_j-1)<|C_\alpha(x)|$. If $1\leq x\leq M$, then
\[ \frac{|C_\alpha(x)|}{f(x)} > \frac{(a_{t+1}-1)}{32P} > (t+1). \]
If $M< x< q_{t+1}$, then
\[ \frac{|C_\alpha(x)|}{f(x)} = \frac{|C_\alpha(x)|}{x}\frac{x}{f(x)} > \frac{(a_{t+1}-1)}{32q_{t+1}}\cdot64(t+1)q_t > t + 1, \]
since $2(a_{t+1}-1)q_t \geq (a_{t+1} + 1)q_t > q_{t+1}$.\end{proof}

\begin{fact}\label{f4} If $A\geq2$ and $f(n) = o(\log n)$, then there
exists $\alpha = [0,a_1,a_2,\ldots]$ with $a_i\leq A$ for all $i$ and
\[ \limsup_{n\to\infty}\left|\frac{C_\alpha(n)}{f(n)}\right| = \infty. \]
In fact, this is true for every $\alpha$ such that $a_i<A$ for all $i$
and $\sum_{1\leq i\leq t}a_i\geq ct$ infinitely often, for some fixed
$c>1$.\end{fact}
\begin{proof} Assume that $f(n)>0$ for all $n$. Fix $L\geq1$. Choose $M$
so that $f(x)/\log x < (c-1)/32L\log(A+1)$, $x>M$. Let $P = \max\{f(x)
: 1 \leq x\leq M\}$. Choose $t$ so that $\frac1{32}\sum_{1\leq i\leq t}
(a_j-1) \geq\frac1{32}(c-1)t > LP$. Choose $x$, $0<x<q_t$, so $|C_\alpha(x)|
> \frac1{32}\sum_{1\leq i\leq t}(a_j-1) > LP$. If $1\leq x\leq M$ then
\[ \frac{|C_\alpha(x)|}{f(x)} \geq \frac{|C_\alpha(x)|}{P} > L. \]
If $M < x < q_t$ then
\[ \frac{|C_\alpha(x)|}{f(x)} = \frac{|C_\alpha(x)|}{\log x}\frac{\log x}{f(x)} > \frac{(c-1)t}{32\log q_t}\cdot\frac{32L\log(A+1)}{(c-1)} > L, \]
where the last inequality holds since $q_{s+1}\leq Aq_s + q_{s-1}<(A+1)
q_s$, so $\log q_t< t\log(A+1)$.\end{proof}

\section{New Results\label{s6}}

\begin{thrm}\label{t3} Let $\alpha = [a_0,a_1,a_2,\ldots]$.
\begin{enumerate}
\item[(a)] If $\sum_{1\leq i\leq t}a_j\geq(1+\frac17)t$ infinitely often, then
the inequality $|C_\alpha(x)| > \frac1{256}\log x$ holds for infinitely many $x$.
\item[(b)] If $\sum_{1\leq i\leq t}a_j \leq (1+\frac17)t$ infinitely often, then
$C_\alpha(x) > \frac1{56}\log x$ and $C_\alpha(x) < -\frac1{56}\log x$ each
hold for infinitely many $x$.
\end{enumerate}\end{thrm}

\begin{lmma} (\cite{ostrowski1922}). For each $t\geq1$, $\sum_{1\leq i\leq t}
a_i>\log q_t$.\end{lmma}
\begin{proof}[Proof of Lemma.] $q_t\leq (a_t+1)q_{t-1}\cdots \leq (a_t+1)\cdots
(a_2+1)(a_1+1)\leq e^{a_t}\cdots e^{a_2}e^{a_1}$.\end{proof}

\begin{proof}[Proof of Theorem.]
\begin{enumerate}
\item[(a)] For $t$ such that $\sum_{1\leq i\leq t}a_j\leq (1 + \frac17)t$,
apply Theorem \ref{t2} to get $x$, $0<x<q_t$, with $|C_\alpha(x)| > \frac1{32}
\sum_{1\leq j\leq t}(a_j-1)\geq\frac1{32}(t/7)$. By the Lemma, either
$\sum_{1\leq j\leq t}(a_j - 1) < \frac18\log q_t$ or $t>\frac78\log q_t$; in
either case we get $|C_\alpha(x)| > (1/(8\cdot32))\log x$.

\item[(b)] For $t$ such that $\sum_{1\leq j\leq t}a_j\leq (1 + \frac17)t$, let
$G = \{ j : 6j+1\leq t, a_{6j}=a_{6j+1}=1\}$. Since the number of $a_j>1$
among $a_1,\ldots,a_t$ is at most $\floor{t/7}$, it follows that $|G|\geq6t/7$.
Let $x = \sum_{j\in G} q_{6j}$. Note that $0<x<q_t$, so that $\frac87t\geq
\sum_{1\leq i\leq t}a_j > \log q_t > \log x$. According to Theorem \ref{t1}(c),
$C_\alpha(x) = -\sum_{j\in G}(\frac12 - d_{6j}(m_{6j} + \frac12q_{6j} + \frac12))$.
To estimate $d_{6j}m_{6j}$, we use $d_{6j}<1/q_{6j+1}$, $m_{6j}\leq q_6 + q_{12}
+ \cdots + q_{6j+1}$ (since $q_s < 2q_{s+2}$), $q_{12}<(1/8^{j-2})q_{6j+1}$, etc.,
to get
\[ d_{6j}m_{6j} < \frac18 + \frac1{8^2} + \cdots + \frac1{8^{j-1}} = \frac17 - \frac17\cdot\frac1{8^{j-1}}. \]

Next, for $j\in G$ we have $q_{6j}/q_{6j+1} = (q_{6j-1} + q_{6j-2})/(2q_{6j-1}
+ q_{6j-2}) < \frac23$. Finally, $d_{6j} < 1/q_{6j+1} < 1/8^j$. Therefore
\begin{align*}
C_{\alpha}(x)
&< -\sum_{j\in G} \left(\frac12 - \left(\frac17 - \frac17\cdot\frac1{8^{j-1}} + \frac13 + \frac12\cdot\frac1{8^j}\right)\right) \\
&< -\sum_{j\in G} \left(\frac12 - \left(\frac17 + \frac13\right)\right) = - |G|\frac1{42}.
\end{align*}
Since $|G|\geq 6t/7$ and $8t/7>\log x$, this gives $C_\alpha(x) < -\frac1{56}\log x$.
\end{enumerate}

The proof that $C_\alpha(x)>\frac1{56}\log x$ for infinity many $x$ is
essentially the same.\end{proof}

\begin{thrm}\label{t4} Let $A$ be a positive constant. Then there exists a
positive constant $d_A$ such that if $\alpha = [0,a_1,a_2,\ldots]$ is any
irrational such that $\sum_{1\leq i\leq t}a_j\leq At$ for infinitely many
$t$, then each of $C_\alpha(x) > d_A\log x$ and $C_\alpha(x) < - d_A\log x$
holds for infinitely many $x$.\end{thrm}
\begin{proof} We show that $C_\alpha(x) < -d_A\log x$ holds infinitely
often. The proof of the other inequality is essentially the same. Our method
is similar to the proof of Fact \ref{f5}.

First, choose $L$ so that $1/(2^L-1)<\frac14\cdot(1/(4A+2))$. Let $t>4L$
and $t>12A$, with $\sum_{1\leq i\leq t}a_j\leq At$.

From among the even terms $a_2,a_4,\ldots,a_{2k},\ldots$ with $2k<t$,
choose $u = \floor{t/4}$ terms each less than or equal to $4A$. From among
these $u$ terms choose the $L$th, $(2L)$th, \ldots, $(wL)$th successive
terms, where $w = \floor{t/4L}$. Let us call these $w$ terms $a_{j_1},
\ldots,a_{j_w}$.

Then $a_{j_1},\ldots,a_{j_w}$ have the following properties.
\begin{enumerate}
\item $j_k$ is even, $1\leq k\leq w$.
\item $a_{j_k}\leq 4A$, $1\leq j\leq w$.
\item $j_1 < \cdots < j_w$ and $j_{k+1} - j_k \geq 2L$, $1\leq k\leq w - 1$.
\end{enumerate}

Now let $x = q_{j_1} + \cdots + q_{j_w}$. (Then $x < q_t$.) We will show
using Theorem \ref{t1}(c) (as in the proof of Fact \ref{f5}) that $C_\alpha(x)
< -dt$ for some constant $d$ depending only on $A$. Then since $\log x<\log
q_t<\sum_{1\leq i\leq t}a_j \leq At$, we will have $C_\alpha(x) < -(d/A)\log
x$, and we can take $d_A = d/A$.

To apply Theorem \ref{t1}(c), since the $j_k$'s are even we have $C_\alpha(x)
= -\sum_{1\leq k\leq w}(\frac12 - d_{j_k}(m_{j_k} + \frac12q_{j_k} + \frac12))$.

Since $d_{j_k} < 1/q_{j_k+1}$, $m_{j_k} = q_{j_1} + \cdots + q_{j_{k-1}}$,
and $q_{j_2} > 2^La_{j_1}$, etc. (since $j_2-j_1\geq2L$), we get
\[ d_{j_k}m_{j_k} < \frac1{2^L}+\frac1{2^{2L}} + \cdots + \frac1{2^{(k-1)L}} = \frac1{2^L-1}\left(1 - \frac1{2^{(k-1)L}}\right). \]

Next, we use the (easily verified) fact that if $a_{s+1}\geq2$ then $q_s/q_{s+1}
<\frac12$ and if $a_{s+1} = 1$ then $q_s/q_{s+1}<1-1/(a_s+2)$. Since $a_{j_k}
\leq4A$ (and $\frac12<1-1/(4A + 2)$), $d_{j_k}q_{j_k} < q_{j_k}/q_{j_k+1} < 1 -
1/(4A + 2)$.

Finally, $d_{j_k}<1/q_{j_k+1}<1/2^{kL}$. Putting all these together gives
\begin{align*}
C_\alpha(x)
&< -\sum_{1\leq k\leq w}\left(\frac12 - \frac1{2^L-1}\left(1 - \frac1{2^{(k-1)L}}\right) - \frac12\left(1 - \frac1{4A + 2}\right) - \frac12\frac1{2^{kL}}\right) \\
&< -\sum_{1\leq k\leq w}\left(\frac12\left(\frac1{4A + 2}\right) - \frac1{2^L-1}\right) < -w\cdot\frac14\cdot\frac1{4A+2} < -dt,
\end{align*}
since $w = \floor{t/4L}$ and $L$ depends only on $A$. This completes the proof.
\end{proof}

By tracing back through the choice of $L$, one can see that $d_A\geq1/(7\cdot
64(A+1)^2\log(A+1))$.

\begin{thrm}\label{t5} Let $\alpha = [0,a_1,a_2,\ldots]$.
\begin{enumerate}
\item[(a)] If $\liminf_{t\to\infty}(1/t)\sum_{1\leq j\leq t}a_j = 1$, then
$C_\alpha(x) > \frac1{56}\log x$, $C_\alpha(x) < -\frac1{56}\log x$ hold
infinitely often.
\item[(b)] If $\liminf_{t\to\infty}(1/t)\sum_{1\leq j\leq t}a_j < \infty$,
then $C_\alpha(x) > d\log x$, $C_\alpha(x) < -d\log x$ hold infinitely often,
for some $d>0$.
\item[(c)] If $\liminf_{t\to\infty}(1/t)\sum_{1\leq j\leq t}a_j = \infty$,
then such a $d$ may fail to exist. (See the theorem of Vera T. S\'os below.)
However, for every $\epsilon>0$, $|C_\alpha(x)| > (\frac1{32} - \epsilon)
\log x$ holds infinitely often.
\end{enumerate}\end{thrm}
\begin{proof} Part (a) follows from Theorem \ref{t3}(b). Part (b) follows
from Theorem \ref{t4}. Part (c) is proved in the same way as Theorem \ref{t3}(a).
\end{proof}

\section{The Vera T. S\'os Theorem}
\setcounter{lmma}{0}

Our final application of Theorem \ref{t1}(c) will be a simplified proof of the
following result of Vera T. S\'os \cite{sos1957}, which answered a question of
Ostrowski \cite{ostrowski1922}.

\begin{fact}\label{f5} Let $\alpha = [0,a_1,a_2,\ldots]$, where $a_{2n+1}=1$,
$a_{2n}=n^2$, $n\geq0$. Then there exists a constant $C$ such that $C_\alpha(n)
> C$ for all $n\geq1$.\end{fact}

(In S\'os's paper, the $a_i$'s are indexed differently, and $n^3$ appears
rather than $n^2$.)

\begin{lmma}\label{l61} For $k\geq1$, $\frac12(q_{2k-2}/q_{2k-1} + d_{2k}/d_{2k-1}
-2) < k^2(\frac12 - d_{2k-1}q_{2k-1}(1 + \frac12k^2)) < 0$.\end{lmma}
\begin{proof} Using $d_{s+1}<d_s$, $q_s< q_{s+1}$, $q_{s+1}d_s+q_sd_{s+1}=1$,
and $q_{2k} = k^2q_{2k-1} + q_{2k-2}$, we get
\[ \frac1{d_{2k-1}q_{2k-1}} = \frac{q_{2k}}{q_{2k-1}} + \frac{d_{2k}}{d_{2k-1}}
= k^2 + \frac{q_{2k-2}}{q_{2k-1}} + \frac{d_{2k}}{d_{2k-1}} < k^2 + 2, \]
so $d_{2k-1}q_{2k-1}(1 + \frac12k^2) > (1 + \frac12k^2)/(k^2 + 2) = \frac12$,
which gives the right-hand inequality. Next,
\begin{align*}
0 &> \frac12 - d_{2k-1}q_{2k-1}\left(1 + \frac12k^2\right) \\
&= \frac12 - \frac{1 + \frac12k^2}{k^2 + \frac{q_{2k-2}}{q_{2k-1}} + \frac{d_{2k}}{d_{2k-1}}} \\
&= \frac{\frac{q_{2k-2}}{q_{2k-1}} + \frac{d_{2k}}{d_{2k-1}} - 2}{2\left(k^2 + \frac{q_{2k-2}}{q_{2k-1}} + \frac{d_{2k}}{d_{2k-1}}\right)} \\
&> \frac{\frac{q_{2k-2}}{q_{2k-1}} + \frac{d_{2k}}{d_{2k-1}} - 2}{2k^2},
\end{align*}
which gives the left-hand inequality.
\end{proof}

\begin{lmma}\label{l62}For $k\geq2$, $q_{2k-2}/q_{2k-1} > 1 - 1/(k-1)^2$.
For $k\geq1$, $d_{2k}/d_{2k-1} > d_{2k}q_{2k} > 1 - 2/k^2$.\end{lmma}
\begin{proof} For $k\geq 2$,
\[ \frac{q_{2k-2}}{q_{2k-1}} = \frac{q_{2k-2}}{q_{2k-2} + q_{2k-3}}
= 1 - \frac{q_{2k-3}}{q_{2k-2} + q_{2k-3}}
> 1 - \frac{q_{2k-3}}{q_{2k-2}}
> 1 - \frac1{(k-1)^2}. \]
For $k\geq1$,
\begin{align*}
\frac{d_{2k}}{d_{2k-1}}
&> d_{2k}q_{2k} \\
&= \frac1{\frac{q_{2k+1}}{q_{2k}} + \frac{d_{2k+1}}{d_{2k}}} \\
&= \frac1{1 + \frac{q_{2k-1}}{q_{2k}} + \frac{d_{2k+1}}{d_{2k}}} \\
&> \frac1{1 + \frac1{k^2} + \frac1{(k+1)^2}} > 1 - \frac2{k^2}
\end{align*}
(Here we used $q_{2k} = k^2q_{2k-1} + q_{2k-2}$ and $d_{2k} = (k+1)^2d_{2k+1}
+ d_{2k+2}$.)
\end{proof}

\begin{proof}[Proof of Fact 5.] Let $m = \sum_{1\leq j\leq t}z_jq_{j-1}$
be the Zeckendorff representation of $m$. Then
\[ C_\alpha(m) = \sum_{1\leq j\leq t} (-1)^j z_j(\frac12 - d_{j-1}(m_{j-1} + \frac12z_jq_{j-1}+\frac12)) = D_0(m) - D_1(m), \]
where
\[ D_0(m) = \sum_{1\leq 2k\leq t} z_{2k}(\frac12 - d_{2k-1}(m_{2k-1} + \frac12 z_{2k}q_{2k-1} + \frac12)), \]
\[ D_1(m) = \sum_{1\leq 2k+1\leq t} z_{2k+1}(\frac12 - d_{2k}(m_{2k} + \frac12 z_{2k+1}q_{2k} + \frac12)). \]
We wish to find constants $A$ and $B$ such that $D_0(m)\geq A$, $D_1(m)\geq B$,
$m\geq1$, so that $C_\alpha(m)\geq A - B$, $m\geq1$.

Since $m_{2k-1}\leq q_{2k-1}$, we have
\begin{align*}
D_0(m)
&> \sum_{1\leq 2k\leq t} z_{2k}(\frac12 - d_{2k-1}(q_{2k-1} + \frac12z_{2k}q_{2k-1})) \\
&= \sum_{1\leq 2k\leq t} z_{2k}(\frac12 - d_{2k-1}q_{2k-1}(1 + \frac12z_{2k})).
\end{align*}
Using $z_{2k}\leq a_{2k} = k^2$ and part of Lemma \ref{l61}, this gives $D_0(m)
\geq \sum_{1\leq 2k\leq t}k^2(\frac12 - d_{2k-1}q_{2k-1}(1 + \frac12k^2))$.
The other part of Lemma \ref{l61}, followed by Lemma \ref{l62}, now gives
\begin{align*}
D_0(m)
&> \frac12\sum_{k=1}^\infty \left(\frac{q_{2k-2}}{q_{2k-1}} + \frac{d_{2k}}{d_{2k-1}} - 2\right)
&> \frac12\left(\frac{q_0}{q_1} + \frac{d_2}{d_1} - 2\right) + \frac12\sum_{k=1}^\infty\left(-\frac1{(k-1)^2} - \frac2{k^2}\right) \\
&= A.
\end{align*}

Next, first omitting some negative terms from $D_1(m)$ gives
\[ D_1(m) \leq \sum_{1 \leq 2k+1\leq t}z_{2k+1}(\frac12 - \frac12d_{2k}z_{2k+1}q_{2k}). \]
Using Lemma \ref{l62} gives
\begin{align*}
D_1(m)
&\leq \frac12z_1(1 - d_0z_1q_0) + \frac12\sum_{3\leq2k+1\leq t}z_{2k+1}\left(1 - z_{2k+1}\left(1 - \frac2{k^2}\right)\right) \\
&\leq \frac12z_1(1 - d_0z_1q_0) + \frac12\sum_{k=1}^\infty\frac{2}{k^2} = B.
\end{align*}
(For the last inequality, we used $0\leq z_{2k+1}\leq a_{2k+1} = 1$.)
\end{proof}

\begin{ackn} The authors are grateful to the referee for Refs.
\cite{hardy+littlewood1922-1,hardy+littlewood1922-2,ostrowski1922,sos1957},
and for the statement of Theorem \ref{t1}(c) and the statement and proof of
Theorem \ref{t2}, which simplifies so many of the subsequent proofs. Indeed,
without theorem \ref{t2} it is possible that Theorems \ref{t3}, \ref{t4} and
\ref{t5} would never have been noticed.\end{ackn}


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

