# Sums, series, and products in Diophantine approximation

Jordan Bell
jordan.bell@gmail.com
Department of Mathematics, University of Toronto
(March 3, 2023)
###### Abstract

There is not much that can be said for all $x$ and for all $n$ about the sum

 $\sum_{k=1}^{n}\frac{1}{|\sin k\pi x|}.$

However, for this and similar sums, series, and products, we can establish results for almost all $x$ using the tools of continued fractions. We present in detail the appearance of these sums in the singular series for the circle method. One particular interest of the paper is the detailed proof of a striking result of Hardy and Littlewood, whose compact proof, which delicately uses analytic continuation, has not been written freshly anywhere since its original publication. This story includes various parts of late 19th century and early 20th century mathematics.

## 1 Introduction

In this paper we survey a class of estimates for sums, series, and products that involve Diophantine approximation. We both sort out a timeline of the literature on these questions and give careful proofs of many lesser known results. Rather than being an open-pit mine for the history of Diophantine approximation, this paper follows one vein as deep as it goes.

For $x\in\mathbb{R}$, we write $\left\|x\right\|=\min_{n\in\mathbb{Z}}|x-n|$, the distance from $x$ to a nearest integer. In this paper we give a comprehensive presentation of estimates for sums whose $j$th term involves $\left\|jx\right\|$ and determine the abscissa of convergence and radius of convergence respectively of Dirichlet series and power series whose $j$th term involves $\left\|jx\right\|$. We also give a detailed proof of a result of Hardy and Littlewood that

 $\lim_{n\to\infty}\left(\prod_{k=1}^{n}|\sin k\pi x|\right)^{1/n}=\frac{1}{2}$

for almost all $x$.

We either prove or state in detail and give references for all the material on continued fractions and measure theory that we use in this paper. Many of the results we prove in this paper do not have detailed proofs written in any books, and the proofs we give for results that do have proofs in books are often written significantly more meticulously here than anywhere else; in some cases the proofs in the literature are so sketchy that the proof we give is written from scratch, for example Lemma 9. Our presentation of Hardy and Littlewood’s estimate for $\prod_{k=1}^{n}|\sin\pi kx|$ makes clear exactly what results in Diophantine approximation one needs for the proof.

In the next section we introduce the Bernoulli polynomials, the Euler-Maclaurin summation formula, and Euler’s constant, which we shall use in a few places. Because the calculations are similar to what we do in the rest of this paper and because we want to be comfortable using Bernoulli polynomials, we work things out from scratch rather than merely stating results as known. In the section after that we summarize various problems that involve sums of the type we are talking about in this paper.

## 2 The Bernoulli polynomials, the Euler-Maclaurin summation formula, and Euler’s constant

For $k\geq 0$, the Bernoulli polynomial $B_{k}(x)$ is defined by

 $\frac{ze^{xz}}{e^{z}-1}=\sum_{k=0}^{\infty}B_{k}(x)\frac{z^{k}}{k!},\qquad|z|<% 2\pi.$ (1)

The Bernoulli numbers are $B_{k}=B_{k}(0)$, the constant terms of the Bernoulli polynomials. For any $x$, using L’Hospital’s rule the left-hand side of (1) tends to $1$ as $z\to 0$, and the right-hand side tends to $B_{0}(x)$, hence $B_{0}(x)=1$. Differentiating (1) with respect to $x$,

 $\sum_{k=0}^{\infty}B_{k}^{\prime}(x)\frac{z^{k}}{k!}=\frac{z^{2}e^{xz}}{e^{z}-% 1}=\sum_{k=0}^{\infty}B_{k}(x)\frac{z^{k+1}}{k!}=\sum_{k=1}^{\infty}B_{k-1}(x)% \frac{z^{k}}{(k-1)!},$

so $B_{0}^{\prime}(x)=0$ and for $k\geq 1$ we have $\frac{B_{k}^{\prime}(x)}{k!}=\frac{B_{k-1}(x)}{(k-1)!}$, i.e.

 $B_{k}^{\prime}(x)=kB_{k-1}(x).$

Furthermore, integrating (1) with respect to $x$ on $[0,1]$ gives, since $\int e^{xz}dx=\frac{e^{z}-1}{z}$,

 $1=\sum_{k=0}^{\infty}\left(\int_{0}^{1}B_{k}(x)dx\right)\frac{z^{k}}{k!},% \qquad|z|<2\pi,$

hence $\int_{0}^{1}B_{0}(x)dx=1$ and for $k\geq 1$,

 $\int_{0}^{1}B_{k}(x)dx=0.$

The first few Bernoulli polynomials are

 $B_{0}(x)=1,\quad B_{1}(x)=x-\frac{1}{2},\quad B_{2}(x)=x^{2}-x+\frac{1}{6},% \quad B_{3}(x)=x^{3}-\frac{3}{2}x^{2}+\frac{1}{2}x.$

The Bernoulli polynomials satisfy the following:

 $\displaystyle\sum_{k=0}^{\infty}B_{k}(x+1)\frac{z^{k}}{k!}$ $\displaystyle=\frac{ze^{(x+1)z}}{e^{z}-1}$ $\displaystyle=\frac{ze^{xz}(e^{z}-1+1)}{e^{z}-1}$ $\displaystyle=ze^{xz}+\frac{ze^{xz}}{e^{z}-1}$ $\displaystyle=\sum_{k=0}^{\infty}\frac{x^{k}z^{k+1}}{k!}+\sum_{k=0}^{\infty}B_% {k}(x)\frac{z^{k}}{k!}$ $\displaystyle=\sum_{k=1}^{\infty}\frac{x^{k-1}z^{k}}{(k-1)!}+\sum_{k=0}^{% \infty}B_{k}(x)\frac{z^{k}}{k!},$

hence

 $B_{k}(x+1)=kx^{k-1}+B_{k}(x),\qquad k\geq 1,x\in\mathbb{R}.$ (2)

In particular, for $k\geq 2$, $B_{k}(1)=B_{k}(0)$. The identity (2) yields Faulhaber’s formula, for $k\geq 0$ and positive integers $a,

 $\sum_{a\leq m\leq b}m^{k}=\frac{B_{k+1}(b+1)-B_{k+1}(a)}{k+1}.$ (3)

The following identity is the multiplication formula for the Bernoulli polynomials, found by Raabe [122, pp. 19–24, §13].

###### Lemma 1.

For $k\geq 0$, $q\geq 1$, and $x\in\mathbb{R}$,

 $qB_{k}(qx)=q^{k}\sum_{j=0}^{q-1}B_{k}\left(x+\frac{j}{q}\right).$
###### Proof.

Using (2) with $x=\frac{qn+j}{q}=n+\frac{j}{q}$,

 $(qn+j)^{k}=\frac{q^{k}}{k+1}\left(B_{k+1}\left(n+\frac{j}{q}+1\right)-B_{k+1}% \left(n+\frac{j}{q}\right)\right),$

thus

 $\displaystyle\sum_{m=q}^{Nq-1}m^{k}$ $\displaystyle=\sum_{n=1}^{N-1}\sum_{j=0}^{q-1}(nq+j)^{k}$ $\displaystyle=\frac{q^{k}}{k+1}\sum_{j=0}^{q-1}\sum_{n=1}^{N-1}\left(B_{k+1}% \left(n+\frac{j}{q}+1\right)-B_{k+1}\left(n+\frac{j}{q}\right)\right)$ $\displaystyle=\frac{q^{k}}{k+1}\sum_{j=0}^{q-1}\left(B_{k+1}\left(N+\frac{j}{q% }\right)-B_{k+1}\left(1+\frac{j}{q}\right)\right).$

Then by (3),

 $B_{k+1}(qN)-B_{k+1}(q)=q^{k}\sum_{j=0}^{q-1}\left(B_{k+1}\left(N+\frac{j}{q}% \right)-B_{k+1}\left(1+\frac{j}{q}\right)\right).$

Let $F_{k,q}(x)=B_{k+1}(qx)-q^{k}\sum_{j=0}^{q-1}B_{k+1}(x+j/q)$, which is a polynomial of degree $\leq k+1$. The above means that for $N\geq 1$, $F_{k,q}(N)=F_{k,q}(1)$, which implies that the polynomial $F_{k,q}(x)-F_{k,q}(1)$ is identically $0$ and, a fortiori, $F_{k,q}^{\prime}(x)$ is identically $0$:

 $qB_{k+1}^{\prime}(qx)-q^{k}\sum_{j=0}^{q-1}B_{k+1}^{\prime}\left(x+\frac{j}{q}% \right)=0.$

Using $B_{k+1}^{\prime}(x)=(k+1)B_{k}(x)$,

 $qB_{k}(qx)=q^{k}\sum_{j=0}^{q-1}B_{k}\left(x+\frac{j}{q}\right).$

We remark that for prime $p$ and for $k\geq 0$, one uses Lemma 1 to prove that there is a unique $p$-adic distribution $\mu_{B,k}$ on the $p$-adic integers $\mathbb{Z}_{p}$ such that $\mu_{B,k}(a+p^{N}\mathbb{Z}_{p})=p^{N(k-1)}B_{k}(a/p^{N})$ [80, p. 35, Chapter II, §4], called a Bernoulli distribution.

For $x\in\mathbb{R}$, let $[x]$ be the greatest integer $\leq x$, and let $R(x)=x-[x]$, called the fractional part of $x$. Write $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ and define the periodic Bernoulli functions $P_{k}:\mathbb{T}\to\mathbb{R}$ by

 $P_{k}=B_{k}\circ R.$

For $k\geq 2$, because $B_{k}(1)=B_{k}(0)$, the function $P_{k}$ is continuous. For $f:\mathbb{T}\to\mathbb{C}$ define its Fourier series $\hat{f}:\mathbb{Z}\to\mathbb{C}$ by

 $\hat{f}(n)=\int_{\mathbb{T}}f(t)e^{-2\pi int}dt,\qquad n\in\mathbb{Z}.$

For $k\geq 1$, one calculates $\widehat{P}_{k}(0)=0$ and using integration by parts, $\widehat{P}_{k}(n)=-\frac{1}{(2\pi in)^{k}}$ for $n\neq 0$. Thus for $k\geq 1$, the Fourier series of $P_{k}$ is

 $P_{k}(t)\sim\sum_{n\in\mathbb{Z}}\widehat{P}_{k}(n)e^{2\pi int}=-\frac{1}{(2% \pi i)^{k}}\sum_{n\neq 0}n^{-k}e^{2\pi int}.$

For $k\geq 2$, $\sum_{n\in\mathbb{Z}}|\widehat{P}_{k}(n)|<\infty$, from which it follows that $\sum_{|n|\leq N}\widehat{P}_{k}(n)e^{2\pi int}$ converges to $P_{k}(t)$ uniformly for $t\in\mathbb{T}$. Furthermore, for $t\not\in\mathbb{Z}$ [102, p. 499, Theorem B.2],

 $P_{1}(t)=-\frac{1}{\pi}\sum_{n=1}^{\infty}\frac{1}{n}\sin 2\pi nt.$

Thus for example,

 $B_{1}\left(\frac{1}{2\pi}\right)=P_{1}\left(\frac{1}{2\pi}\right)=-\frac{1}{% \pi}\sum_{k=1}^{\infty}\frac{\sin k}{k}.$

The Euler-Maclaurin summation formula is the following [102, p. 500, Theorem B.5]. If $a are real numbers, $K$ is a positive integer, and $f$ is a $C^{K}$ function on an open set that contains $[a,b]$, then

 $\displaystyle\sum_{a $\displaystyle=\int_{a}^{b}f(x)dx+\sum_{k=1}^{K}\frac{(-1)^{k}}{k!}(P_{k}(b)f^{% (k-1)}(b)-P_{k}(a)f^{(k-1)}(a))$ $\displaystyle-\frac{(-1)^{K}}{K!}\int_{a}^{b}P_{K}(x)f^{(K)}(x)dx.$

Applying the Euler-Maclaurin summation formula with $a=1,b=n,K=2,f(x)=\log x$ yields [102, p. 503, Eq. B.25]

 $\sum_{1\leq m\leq n}\log n=n\log n-n+\frac{1}{2}\log n+\frac{1}{2}\log 2\pi+O(% n^{-1}).$

Using $e^{1+O(n^{-1})}=1+O(n^{-1})$, taking the exponential of the above equation gives Stirling’s approximation,

 $n!=n^{n}e^{-n}\sqrt{2\pi n}(1+O(n^{-1})).$

Write $a_{n}=-\log n+\sum_{1\leq m\leq n}\frac{1}{m}$. Because $x\mapsto\log(1-x)$ is concave,

 $a_{n}-a_{n-1}=\frac{1}{n}+\log\left(1-\frac{1}{n}\right)\leq 1+1-\frac{1}{n}=0,$

which means that the sequence $a_{n}$ is nonincreasing. For $f(x)=\frac{1}{x}$, because $f$ is positive and nonincreasing,

 $\sum_{1\leq m\leq n}f(m)\geq\int_{1}^{n+1}f(x)dx=\log(n+1)>\log n,$

hence $a_{n}>0$. Because the sequence $a_{n}$ is positive and nonincreasing, there exists some nonnegative limit, $\gamma$, called Euler’s constant. Using the Euler-Maclaurin summation formula with $a=1,b=n,K=1,f(x)=\frac{1}{x}$, as $P_{1}(x)=[x]-\frac{1}{2}$,

 $\sum_{1

which is

 $\sum_{1

As $0\leq R(x)x^{-2}\leq x^{-2}$, the function $x\mapsto R(x)x^{-2}$ is integrable on $[1,\infty)$; let $C=1-\int_{1}^{\infty}R(x)x^{-2}$. Since $0\leq\int_{n}^{\infty}R(x)x^{-2}dx\leq\int_{n}^{\infty}x^{-2}dx=n^{-1}$,

 $\sum_{1\leq m\leq n}\frac{1}{m}=\log n+C+O(n^{-1})$

f. But $-\log n+\sum_{1\leq m\leq n}\frac{1}{m}\to\gamma$ as $n\to\infty$, from which it follows that $C=\gamma$ and thus

 $\sum_{1\leq m\leq n}\frac{1}{m}=\log n+\gamma+O(n^{-1}).$

## 3 Background

For $x\in\mathbb{R}$, let $[x]$ be the greatest integer $\leq x$ and let $R(x)=x-[x]$. It will be handy to review some properties of $x\mapsto[x]$. For $n\in\mathbb{Z}$ it is immediate that $[x+n]=[x]$. For $x,y\in\mathbb{R}$ we have $0\leq x-[x]+y-[y]<2$, which means $0=\leq[x-[y]+y-[y]]<=2$, and using $[x+n]=[x]$ this is $0\leq[x+y]-[x]-[y]<2$, therefore

 $[x]+[y]\leq[x+y]\leq[x]+[y]+1.$

For $m,n\in\mathbb{Z}$, $n>1$, and $x\in\mathbb{R}$,

 $\left[\frac{x+m}{n}\right]=\left[\frac{[x]+m}{n}\right].$

For $n$ a positive integer and for real $x$,

 $[x]=\left[x+\frac{0}{n}\right]\leq\left[x+\frac{1}{n}\right]\leq\cdots\left[x+% \frac{n-1}{n}\right]\leq\left[x+\frac{n}{n}\right]=[x]+1.$

There is a unique $\nu$, $1\leq\nu\leq n$, such that $\left[x+\frac{\nu-1}{n}\right]=[x]$ and $\left[x+\frac{\nu}{n}\right]=[x]+1$, and therefore $\left[R(x)+\frac{\nu-1}{n}\right]=0$ and $\left[R(x)+\frac{\nu}{n}\right]=1$, consequently $R(x)+\frac{\nu-1}{n}<1$ and $R(x)+\frac{\nu}{n}\geq 1$, which means $1-\frac{\nu}{n}\leq R(x)<1-\frac{\nu-1}{n}$, from which finally we get $n\leq[nx]-n[x]+\nu and so $n=[nx]-n[x]+\nu$. But

 $\sum_{k=0}^{n-1}\left[x+\frac{k}{n}\right]=\sum_{k=0}^{\nu-1}[x]+\sum_{k=\nu}^% {n-1}([x]+1)=\nu[x]+(n-\nu)([x]+1)=n[x]+n-\nu,$

and using $\nu=n-[nx]+n[x]$,

 $\sum_{k=0}^{n-1}\left[x+\frac{k}{n}\right]=n[x]+n-(n-[nx]+n[x])=[nx].$

This identity is proved by Hermite [65, pp. 310–315, §V].

The Legendre symbol is defined in the following way. Let $p$ be an odd prime, and let $a$ be an integer that is not a multiple of $p$. If there is an integer $b$ such that $a\equiv b^{2}\pmod{p}$ then $\left(\frac{a}{p}\right)=1$, and otherwise $\left(\frac{a}{p}\right)=-1$. In other words, for an integer $a$ that is relatively prime to $p$, if $a$ is a square mod $p$ then $\left(\frac{a}{p}\right)=1$, and if $a$ is not a square mod $p$ then $\left(\frac{a}{p}\right)=-1$. For example, one checks that there is no integer $b$ such that $b^{2}\equiv 6\pmod{7}$, and hence $\left(\frac{6}{7}\right)=-1$, while $3^{2}\equiv 2\pmod{7}$, and so $\left(\frac{2}{7}\right)=1$.

If $p$ and $q$ are distinct odd primes, define integers $u_{k}$, $1\leq k\leq\frac{p-1}{2}$, by

 $kq=p\left[\frac{kq}{p}\right]+u_{k};$

namely, $u_{k}$ is the remainder of $kq$ when divided by $p$. We have $1\leq u_{k}\leq p-1$. Let $\mu(q,p)$ be the number of $k$ such that $u_{k}>\frac{p-1}{2}$. It can be shown that [59, p. 74, Theorem 92]

 $\left(\frac{q}{p}\right)=(-1)^{\mu(q,p)};$

this fact is called Gauss’s lemma. For example, for $p=13$ and $q=3$ we work out that

 $u_{1}=3,\quad u_{2}=6,\quad u_{3}=9,\quad u_{4}=12,\quad u_{5}=2,\quad u_{6}=5,$

and hence $\mu(3,13)=2$, so $(-1)^{\mu(3,13)}=1$; on the other hand, $4^{2}\equiv 3\pmod{13}$, hence $\left(\frac{3}{13}\right)=1$. With

 $S(q,p)=\sum_{j=1}^{\frac{p-1}{2}}\left[\frac{jq}{p}\right],$

it is known that [59, pp. 77-78, §6.13]

 $S(q,p)\equiv\mu(q,p)\pmod{2}.$

And it can be shown that [59, p. 76, Theorem 100]

 $S(q,p)+S(p,q)=\frac{p-1}{2}\cdot\frac{q-1}{2}.$ (4)

Thus

 $\displaystyle\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)$ $\displaystyle=$ $\displaystyle(-1)^{\mu(p,q)+\mu(q,p)}$ $\displaystyle=$ $\displaystyle(-1)^{S(p,q)+S(q,p)}$ $\displaystyle=$ $\displaystyle(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.$

This is Gauss’s third proof of the law of quadratic reciprocity in the numbering [7, p. 50, §20]. This proof was published in Gauss’s 1808 “Theorematis arithmetici demonstratio nova”, which is translated in [140, pp. 112–118]. Dirichlet [38, pp. 65–72, §§42–44] gives a presentation of the proof. Eisenstein’s streamlined version of Gauss’s third proof is presented with historical remarks in . Lemmermeyer  gives a comprehensive history of the law of quadratic reciprocity, and in particular writes about Gauss’s third proof [95, pp. 9–10]. The formula (4) resembles the reciprocity formula for Dedekind sums [123, p. 4, Theorem 1].

Gauss obtains (4) from the following [140, p. 116, §5]: if $x$ is irrational and $n$ is a positive integer, then

 $\sum_{k=1}^{n}[kx]+\sum_{k=1}^{[nx]}\left[\frac{k}{x}\right]=n[nx],$ (5)

which he proves as follows. If $\left[\frac{j}{x}\right], then $[kx]=j$. Therefore

 $\displaystyle\sum_{k=1}^{n}[kx]$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{[nx]}j\left(\left[\frac{j+1}{x}\right]-\left[\frac{j}% {x}\right]\right)$ $\displaystyle=$ $\displaystyle n[nx]-\sum_{j=1}^{[nx]}\left[\frac{j}{x}\right].$

Bachmann [6, pp. 654–658, §4] surveys later work on sums similar to (5); see also Dickson [35, Chapter X]. If $m$ and $n$ are relatively prime, then

 $\left\{R\left(\frac{m}{n}\right),R\left(\frac{2m}{n}\right),\ldots,R\left(% \frac{(n-1)m}{n}\right)\right\}=\left\{\frac{1}{n},\frac{2}{n},\ldots,\frac{n-% 1}{n}\right\},$

and so

 $\sum_{k=1}^{n-1}R\left(\frac{km}{n}\right)=\sum_{k=1}^{n-1}\frac{k}{n}=\frac{1% }{n}\cdot\frac{(n-1)n}{2}=\frac{n-1}{2}.$

Hence

 $\sum_{k=1}^{n-1}\left[\frac{km}{n}\right]=\sum_{k=1}^{n-1}\frac{km}{n}-\sum_{k% =1}^{n-1}R\left(\frac{km}{n}\right)=\frac{(m-1)(n-1)}{2}.$ (6)

There is also a simple lattice point counting argument [118, p. 113, No. 18] that gives (6).

In 1849, Dirichlet  shows that

 $\sum_{k=1}^{n}d(k)=\sum_{k=1}^{n}\left[\frac{n}{k}\right],$

where $d(n)$ denotes the number of positive divisors of an integer $n$. (This equality is Dirichlet’s “hyperbola method”.) He then proves that

 $\sum_{k=1}^{n}\left[\frac{n}{k}\right]=n\log n+(2\gamma-1)n+O(\sqrt{n}).$

Hardy and Wright [59, pp. 264–265, Theorem 320] give a proof of this. Finding the best possible error term in the estimate for $\sum_{k=1}^{n}d(k)$ is “Dirichlet’s divisor problem”. Dirichlet cites the end of Section V Gauss’s Disquisitiones Arithmeticae as precedent for determining average magnitudes of arithmetic functions. (In Section V, Articles 302–304, of the Disquisitiones Arithmeticae, Gauss writes about averages of class numbers of binary quadratic forms, cf. [36, Chapter VI].)

Define $(x)$ to be $0$ if $x\in\mathbb{Z}+\frac{1}{2}$; if $x\not\in\mathbb{Z}+\frac{1}{2}$ then there is an integer $m_{x}$ for which $|x-m_{x}|<|x-n|$ for all integers $n\neq m_{x}$, and we define $(x)$ to be $x-m_{x}$. Riemann [125, p. 105, §6] defines

 $f(x)=\sum_{n=1}^{\infty}\frac{(nx)}{n^{2}};$

for any $x$, the series converges absolutely because $|(-nx)|<\frac{1}{2}$. Riemann states that if $p$ and $m$ are relatively prime and $x=\frac{p}{2m}$, then

 $f(x^{+})=\lim_{h\to 0^{+}}f(x+h)=f(x)-\frac{\pi^{2}}{16m^{2}},\qquad f(x^{-})=% \lim_{h\to 0^{-}}f(x+h)=f(x)+\frac{\pi^{2}}{16m^{2}},$

thus

 $f(x^{-})-f(x^{+})=\frac{\pi^{2}}{8m^{2}},$

and hence that $f$ is discontinuous at such points, and says that at all other points $f$ is continuous; see Laugwitz [94, §2.1.1, pp. 183-184], Neuenschwander , and Pringsheim [119, p. 37] about Riemann’s work on pathological functions. The role of pathological functions in the development of set theory is explained by Dauben [32, Chapter 1, p. 19] and Ferreirós [49, Chapter V, §1, p. 152].

For any interval $[a,b]$ and any $\sigma>0$, it is apparent from the above that there are only finitely many $x\in[a,b]$ for which $f(x^{-})-f(x^{+})>\sigma$, and Riemann deduces from this that $f$ is Riemann integrable on $[a,b]$; cf. Hawkins [63, p. 18] on the history of Riemann integration. Later in the same paper [125, p. 129, §13], Riemann states that the function

 $x\mapsto\sum_{n=1}^{\infty}\frac{(nx)}{n},$

is not Riemann integrable in any interval.

In 1897, Cesàro  asks the following question (using the pseudonym, and anagram, “Rosace” [112, p. 331]). Let $\epsilon(x)=x-[x]-\frac{1}{2}$. Is the series

 $\sum_{n=1}^{\infty}\frac{\epsilon(nx)}{n}$ (7)

convergent for all non-integer $x$? This is plausible because the expected value of $\epsilon(x)$ is 0. Landau  answers this question in 1901. Landau proves that if there is some $g$ such that

 $\sum_{k=1}^{n}[kx]=\frac{n(n+1)x}{2}-\frac{n}{2}+O(g(n))$

where $g$ is a nonnegative function such $g(n)=o(n)$ and such that $\sum_{n=1}^{\infty}\frac{g(n)}{n(n+1)}$ converges, then (7) converges. And he proves that if $x$ is rational then (7) diverges. We return to this series in §9.

Also in 1898, Franel  asks whether for irrational $x$ and for $\epsilon>0$ we have

 $\sum_{k=1}^{n}[kx]=\frac{n(n+1)x}{2}-\frac{n}{2}+O(n^{\epsilon}).$

Then in 1899, Franel  asks if we can do better than this: is the error term in fact $O(1)$? Cesàro and Franel each contributed many problems to L’Intermédiaire des mathématiciens, the periodical in which they posed their questions. Information about Franel is given in .

Lerch  answers Franel’s questions in 1904. If $x$ is irrational and $\frac{p}{q}$ is a convergent of $x$ (which we will define in §4), then using Theorem 2 (from §4) we can show that if $1\leq k\leq q$ then $[kx]=[\frac{kp}{q}]$. Lerch uses this and (6) to show that if $x$ is irrational and $\frac{p}{q}$ is a convergent of $x$ then

 $\sum_{k=1}^{q}[kx]=\frac{q(q+1)x}{2}-\frac{q}{2}+R,\qquad 0

Lerch states that if the continued fraction expansion of $x$ has bounded partial quotients (defined in §4) then, for any positive integer $n$,

 $\sum_{k=1}^{n}[kx]=\frac{n(n+1)x}{2}-\frac{n}{2}+O(\log n).$

Lerch only gives a brief indication of the proof of this. This result is proved by Hardy and Littlewood in 1922 [57, p. 24, Theorem B3], and also in 1922 by Ostrowski [110, p. 81]. On the other hand, Lerch also constructs examples of $x$ such that, for some positive integer $c$,

 $\left|\sum_{k=1}^{n}[kx]-\frac{n(n+1)x}{2}+\frac{n}{2}\right|\gg n^{1-\frac{1}% {c}}.$

Nevertheless, in 1909 Sierpinski  proves that if $x$ is irrational then

 $\sum_{k=1}^{n}[kx]=\frac{n(n+1)x}{2}-\frac{n}{2}+o(n).$

A bibliography of Lerch’s works is given in . Lerch had written earlier papers on Gauss sums, Fourier series, theta functions, and the class number; many of his papers are in Czech, but some of them are in French, several of which were published in the Paris Comptes rendus. Several of Lerch’s papers are discussed in Cresse’s survey of the class number of binary quadratic forms [36, Chapter VI].

In 1899, a writer using the pseudonym “Quemquaeris”  (“quem quaeris” = “whom you seek”) asks if we can characterize $\phi(n)$ such that for all irrational $\theta$ the series

 $\sum_{n=1}^{\infty}\frac{\phi(n)}{\sin n\pi\theta}$

converges. In particular, the writer asks if $\phi(n)=\frac{1}{n!}$ satisfies this. In the same year, de la Vallée-Poussin  answers this question. (There are also responses following de la Vallée-Poussin’s by Borel and Fabry.) For a given function $\phi(n)$, de la Vallée-Poussin shows that if we have $a_{n}>\frac{1}{\phi(q_{n-1})}$ for all $n$, for $a_{n}$ the $n$th partial quotient of $\theta$ and $q_{n}$ the denominator of the $n$th convergent of $\theta$, then the series

 $\sum_{n=1}^{\infty}\frac{\phi(n)}{\sin n\pi\theta}$

will diverge. Hardy and Littlewood prove numerous results on similar series, e.g. for $\phi(n)=n^{-r}$ for real $r>1$ and for certain classes of $\theta$, in their papers on Diophantine approximation . In 1931, Walfisz [152, p. 570, Hilfssatz 4] shows, following work of Behnke [13, p. 289, §16], that for almost all irrational $x\in[0,1]$, if $\epsilon>0$ then

 $\sum_{k=1}^{n}\frac{1}{\left\|k\theta\right\|}=O(n(\log n)^{2+\epsilon}),$

where $\left\|x\right\|=\min(R(x),1-R(x))$. Walfisz’s paper includes many results on related sums.

In 1916, Watson  finds the following asymptotic series for $S_{n}=\sum_{m=1}^{n-1}\csc\left(\frac{m\pi}{n}\right)$:

 $\pi S_{n}\sim 2n\log(2n)+2n(\gamma-\log\pi)+\sum_{j=1}^{\infty}(-1)^{j}\frac{B% _{2j}^{2}(2^{2j}-2)\pi^{2j}}{j(2j)!n^{2j-1}},$

where $\gamma$ is Euler’s constant and $B_{j}$ are the Bernoulli numbers. Truncating the asymptotic series and rewriting gives

 $S_{n}=\frac{2n\log n}{\pi}+n\cdot\frac{2\log 2+2\gamma-2\log\pi}{\pi}+O\left(% \frac{1}{n}\right).$

For example, computing $S_{1000}$ directly we get $S_{1000}=4477.593932\ldots$, and computing the right-hand side of the above formula without the error term we obtain $4477.594019\ldots$ A cleaner derivation of the asymptotic series using the Euler-Maclaurin summation formula is given later by Williams .

Early surveys of Diophantine approximation are given by Bohr and Cramér [20, pp. 833–836, §39] and Koksma [81, pp. 102–110]. Hlawka and Binder  present the history of the initial years of the theory of uniform distribution. Narkiewicz [106, pp. 82–95, §2.5 and pp. 175–183 §3.5] gives additional historical references on Diophantine approximation. The papers of Hardy and Littlewood on Diophantine approximation are reprinted in . Perron  and Brezinski  give historical references on continued fractions, and there is reliable material on the use of continued fractions by 17th century mathematicians in Whiteside . Fowler  presents a prehistory of continued fractions in Greek mathematics.

## 4 Preliminaries on continued fractions

Let

 $\left\|x\right\|=\min_{k\in\mathbb{Z}}|x-k|=\min(R(x),1-R(x)).$

Let $\mu$ be Lebesgue measure on $[0,1]$, and let $\Omega=[0,1]\setminus\mathbb{Q}$.

For positive integers $a_{1},\ldots,a_{n}$, we define

 $[a_{1},\ldots,a_{n}]=\cfrac{1}{a_{1}+\cfrac{1}{\cdots+\cfrac{1}{a_{n-1}+\cfrac% {1}{a_{n}}}}}.$

For example, $[1,1,1]=\frac{2}{3}$.

Let $\mathbb{N}$ be the set of positive integers. We call $a\in\mathbb{N}^{\mathbb{N}}$ a continued fraction, and we call $a_{n}$ the $n$th partial quotient of $a$. If there is some $K>0$ such that $a_{n}\leq K$ for all $n$ then we say that $a$ has bounded partial quotients. We call $[a_{1},\ldots,a_{n}]$ the $n$th convergent of $a$. For $n\geq 1$ let

 $\frac{p_{n}}{q_{n}}=[a_{1},\ldots,a_{n}],$

with $p_{n},q_{n}$ positive integers that are relatively prime, and set

 $p_{0}=0,\qquad q_{0}=1.$

One can show by induction [44, p. 70, Lemma 3.1] that for $n\geq 1$ we have

 $\begin{pmatrix}p_{n}&p_{n-1}\\ q_{n}&q_{n-1}\end{pmatrix}=\begin{pmatrix}0&1\\ 1&0\end{pmatrix}\begin{pmatrix}a_{1}&1\\ 1&0\end{pmatrix}\cdots\begin{pmatrix}a_{n}&1\\ 1&0\end{pmatrix}.$ (8)

We have

 $p_{1}=1,\qquad q_{1}=a_{1},$

and from (8) we get for all $n\geq 1$ that

 $p_{n+1}=a_{n+1}p_{n}+p_{n-1},$

and

 $q_{n+1}=a_{n+1}q_{n}+q_{n-1}.$

Since the $a_{n}$ are positive integers we get by induction that for all $n\geq 1$,

 $p_{n}\geq 2^{(n-1)/2},\qquad q_{n}\geq 2^{(n-1)/2}.$ (9)

In fact, setting $F_{1}=1,F_{2}=1$, $F_{n+1}=F_{n}+F_{n-1}$ for $n\geq 2$, with $F_{n}$ the $n$th Fibonacci number, as $a_{n}\geq 1$ we check by induction that

 $p_{n}\geq F_{n},\qquad q_{n}\geq F_{n+1}.$

Taking determinants of (8) gives us for all $n\geq 1$ that

 $p_{n}q_{n-1}-p_{n-1}q_{n}=(-1)^{n+1},$ (10)

and then by induction we have for all $n\geq 1$,

 $\frac{p_{n}}{q_{n}}=\sum_{k=1}^{n}\frac{(-1)^{k+1}}{q_{k-1}q_{k}}.$

For any $a\in\mathbb{N}^{\mathbb{N}}$, as $n\to\infty$ this sequence of sums converges and we denote its limit by $v(a)$. We have for all $n\geq 1$,

 $v(a)-\frac{p_{n}}{q_{n}}=\sum_{k=n+1}^{\infty}\frac{(-1)^{k+1}}{q_{k-1}q_{k}}.$

Since the right hand side is an alternating series we obtain for $n\geq 1$,

 $\left|v(a)-\frac{p_{n}}{q_{n}}\right|<\frac{1}{q_{n}q_{n+1}},$ (11)

and

 $\left|v(a)-\frac{p_{n}}{q_{n}}\right|>\frac{1}{q_{n}q_{n+1}}-\frac{1}{q_{n+1}q% _{n+2}}=\frac{a_{n+2}}{q_{n}q_{n+2}}\geq\frac{1}{q_{n}(q_{n+1}+q_{n})},$ (12)

and

 $\frac{p_{2}}{q_{2}}<\frac{p_{4}}{q_{4}}<\cdots (13)

For $x\in\Omega$, we say that $\frac{p}{q}\in\mathbb{Q}$, $q>0$, is a best approximation to $x$ if $\left\|qx\right\|=|qx-p|$ and $\left\|q^{\prime}x\right\|>\left\|qx\right\|$ for $1\leq q^{\prime}. The following theorem shows in particular that the convergents of a continued fraction $a$ are best approximations to $v(a)$ [127, p. 22, Chapter 2, §3, Theorem 1].

###### Theorem 2(Best approximations).

Let $a\in\mathbb{N}^{\mathbb{N}}$. For any $n\geq 1$,

 $\left\|q_{n}v(a)\right\|=|p_{n}-q_{n}v(a)|.$

If $1\leq q, then for any $p\in\mathbb{Z}$,

 $|qv(a)-p|\geq|p_{n}-q_{n}v(a)|.$
###### Proof.

By (11), $|q_{n}v(a)-p_{n}|<\frac{1}{q_{n+1}}$. But

 $q_{n+1}\geq q_{2}=a_{2}q_{1}+q_{0}\geq q_{1}+q_{0}=a_{1}+1\geq 2.$

So $|q_{n}v(a)-p_{n}|<\frac{1}{2}$, which means $\left\|q_{n}v(a)\right\|=|q_{n}v(a)-p_{n}|$.

Write $x=v(a)$ and let $A=\begin{pmatrix}p_{n+1}&p_{n}\\ q_{n+1}&q_{n}\end{pmatrix}$. Applying (10),

 $\det A=p_{n+1}q_{n}-p_{n}q_{n+1}=(-1)^{n}.$

Let

 $\begin{pmatrix}\mu\\ \nu\end{pmatrix}=A^{-1}\begin{pmatrix}p\\ q\end{pmatrix}=\frac{1}{\det A}\begin{pmatrix}q_{n}&-p_{n}\\ -q_{n+1}&p_{n+1}\end{pmatrix}\begin{pmatrix}p\\ q\end{pmatrix}=(-1)^{n}\begin{pmatrix}q_{n}&-p_{n}\\ -q_{n+1}&p_{n+1}\end{pmatrix}\begin{pmatrix}p\\ q\end{pmatrix}.$

Then

 $qx-p=(\mu q_{n+1}+\nu q_{n})x-(p_{n+1}\mu+p_{n}\nu)=\mu(q_{n+1}x-p_{n+1})+\nu(% q_{n}x-p_{n})$

and

 $\begin{pmatrix}p\\ q\end{pmatrix}=A\begin{pmatrix}\mu\\ \nu\end{pmatrix}=\begin{pmatrix}p_{n+1}&p_{n}\\ q_{n+1}&q_{n}\end{pmatrix}\begin{pmatrix}\mu\\ \nu\end{pmatrix}=\begin{pmatrix}p_{n+1}\mu+p_{n}\nu\\ q_{n+1}\mu+q_{n}\nu\end{pmatrix}.$

In particular, $\mu,\nu\in\mathbb{Z}$. Suppose by contradiction that $\nu=0$. Then $(q-\mu q_{n+1})x=p-\mu p_{n+1}$, and as $x\not\in\mathbb{Q}$ it must then be that $q=\mu q_{n+1}$ and $p=\mu p_{n+1}$. But $q=\mu q_{n+1}$, $1\leq q, and $\mu\in\mathbb{Z}$ are together a contradiction. Therefore $\nu\neq 0$. Either $\mu=0$ or $\mu\neq 0$. For $\mu=0$,

 $|qx-p|=|\nu||q_{n}x-p_{n}|\geq|q_{n}x-p_{n}|,$

which is the claim. For $\mu\neq 0$ we use the fact $q=q_{n+1}\mu+q_{n}\nu$ and $1\leq q. If $\mu,\nu>0$ then $q is contradicted, and if $\mu,\nu<0$ then $q\geq 1$ is contradicted. Therefore $\mu$ and $\nu$ have different signs, say $\mu=(-1)^{N}|\mu|$ and $\nu=(-1)^{N+1}|\nu|$. Furthermore, we get from (13) that

 $\mathrm{sgn}\,(q_{n}x-p_{n})=(-1)^{n},\qquad\mathrm{sgn}\,(q_{n+1}x-p_{n+1})=(% -1)^{n+1}.$

Therefore

 $\displaystyle qx-p$ $\displaystyle=\mu(q_{n+1}x-p_{n+1})+\nu(q_{n}x-p_{n})$ $\displaystyle=(-1)^{N}|\mu|\cdot(-1)^{n+1}|q_{n+1}x-p_{n+1}|+(-1)^{N+1}|\nu|% \cdot(-1)^{n}|q_{n}x-p_{n}|,$

hence

 $|qx-p|=|\mu||q_{n+1}x-p_{n+1}|+|\nu||q_{n}x-p_{n}|\geq|\nu||q_{n}x-p_{n}|\geq|% q_{n}x-p_{n}|,$

which is the claim. ∎

The above theorem says, a fortiori, that the convergents of $a$ are best approximations to $v(a)$. It can also be proved that if $\frac{p}{q}\in\mathbb{Q}$, $q>0$, is a best approximation to $v(a)$ then $\frac{p}{q}$ is a convergent of $a$ [92, p. 9, Theorem 6]. Cassels [27, p. 2, Chapter I] works out the theory of continued fractions according to this point of view. Similarly, Milnor [101, p. 234, Appendix C] works out the theory of continued fractions in the language of rotations of the unit circle.

We define the Gauss transformation $T:\Omega\to\Omega$ by $T(x)=R\left(\frac{1}{x}\right)$ for $x\in\Omega$, and we define $\Phi:\Omega\to\mathbb{N}^{\mathbb{N}}$ by

 $(\Phi(x))_{n}=\left[\frac{1}{T^{n-1}(x)}\right],\qquad n\geq 1.$

One can check that if $a\in\mathbb{N}^{\mathbb{N}}$ then $v(a)\in\Omega$ [44, p. 73, Lemma 3.2]. (Namely, the value of a nonterminating continued fraction is irrational.) One can prove that $v:\mathbb{N}^{\mathbb{N}}\to\Omega$ is injective [44, p. 75, Lemma 3.4], and for $x\in\Omega$ that [44, p. 78, Lemma 3.6]

 $(v\circ\Phi)(x)=x.$

Therefore $\Phi:\Omega\to\mathbb{N}^{\mathbb{N}}$ is a bijection. Moreover, $\Phi$ is a homeomorphism, when $\mathbb{N}$ has discrete topology, $\mathbb{N}^{\mathbb{N}}$ has the product topology, and $\Omega$ has the subspace topology inherited from $\mathbb{R}$ [44, p. 86, Exercise 3.2.2]. That $\mathbb{N}^{\mathbb{N}}$ and $\Omega$ are homeomorphic can also be proved without using continued fractions [2, p. 106, Theorem 3.68]. In descriptive set theory, the topological space $\mathscr{N}=\mathbb{N}^{\mathbb{N}}$ is called the Baire space, and the Alexandrov-Urysohn theorem states that $\mathscr{N}$ has the universal property that any nonempty Polish space that is zero-dimensional (there is a basis of clopen sets for the topology) and all of whose compact subsets have empty interior is homeomorphic to $\mathscr{N}$ [75, p. 37, Theorem 7.7]. Some of Baire’s work on $\mathscr{N}$ is described in [71, pp. 119–120] and [5, pp. 349, 372].

For $I=[0,1]$ and for $T:I\to I$, $T(x)=R(1/x)$ for $x>0$ and $T(0)=0$. For $k\geq 1$ let $I_{k}=\left(\frac{1}{k+1},\frac{1}{k}\right)$, so if $x\in I_{k}$ then $T(x)=x^{-1}-k$. Then for $x\in I=[0,1]$,

 $T(x)=\sum_{k=1}^{\infty}1_{I_{k}}(x)(x^{-1}-k).$

For $S=\{0\}\cup\{k^{-1}:k\geq 1\}$, $I\setminus S=\bigcup_{k\geq 1}I_{k}$, and for $x\in I\setminus S$,

 $T^{\prime}(x)=-\sum_{k=1}^{\infty}1_{I_{k}}(x)x^{-2},$

and for $x\in I_{k}$, $k^{2}<|T^{\prime}(x)|<(k+1)^{2}$. Differentiability and dynamical properties of the Gauss transformation are worked out by Cornfeld, Fomin and Sinai [30, pp. 165–177, Chapter 7, §4], as an instance of piecewise monotonic transformations.

For each $n\geq 1$ we define $a_{n}:\Omega\to\mathbb{N}$ by $a_{n}(x)=(\Phi(x))_{n}$. For example, $e-2\in\Omega$, and it is known [92, p. 74, Theorem 2] that for $k\geq 1$,

 $a_{3k}(e-2)=a_{3k-2}(e-2)=1\quad\textrm{and}\quad a_{3k-1}(e-2)=2k.$

The pattern for the continued fraction expansion of $e$ seems first to have been worked out by Roger Cotes in 1714 , and was later proved by Euler using a method involving the Riccati equation .

For $n\geq 1$ and $i\in\mathbb{N}^{n}$, let

 $I_{n}(i)=\{\omega\in\Omega:a_{k}(x)=i_{k},1\leq k\leq n\}.$

For $x\in I_{n}(i)$,

 $\frac{p_{n}(x)}{q_{n}(x)}=[i_{1},\ldots,i_{n}],\qquad\frac{p_{n-1}(x)}{q_{n-1}% (x)}=[i_{1},\ldots,i_{n-1}].$

The following is an expression for the sets $I_{n}(i)$ [69, p. 18, Theorem 1.2.2].

###### Theorem 3.

Let $n\geq 1$, $i\in\mathbb{Z}_{\geq 1}^{n}$, and for $p_{n}=p_{n}(x)$, $q_{n}=q_{n}(x)$, $x\in I_{n}(i)$,

 $u_{n}(i)=\begin{cases}\frac{p_{n}+p_{n-1}}{q_{n}+q_{n-1}}&\textrm{n odd}\\ \frac{p_{n}}{q_{n}}&\textrm{n even}\end{cases}$

and

 $v_{n}(i)=\begin{cases}\frac{p_{n}}{q_{n}}&\textrm{n odd}\\ \frac{p_{n}+p_{n-1}}{q_{n}+q_{n-1}}&\textrm{n even}.\end{cases}$

Then

 $I_{n}(i)=\Omega\cap(u_{n}(i),v_{n}(i)).$

It follows from the above that for $i\in\mathbb{N}^{n}$, $n\geq 1$,

 $\mu(I_{n}(i))=\frac{1}{q_{n}(q_{n}+q_{n-1})}.$

## 5 Diophantine conditions

For real $\tau,\gamma>0$ let

 $\displaystyle\mathcal{D}(\tau,\gamma)$ $\displaystyle=\bigcap_{q\in\mathbb{Z}_{\geq 1},p\in\mathbb{Z}}\left\{x\in[0,1]% :\left|x-\frac{p}{q}\right|\geq\gamma q^{-\tau}\right\}$ $\displaystyle=\bigcap_{q\in\mathbb{Z}_{\geq 1}}\left\{x\in[0,1]:\left\|qx% \right\|\geq\gamma q^{-\tau+1}\right\},$

and let

 $\mathcal{D}(\tau)=\bigcup_{\gamma>0}\mathcal{D}(\tau,\gamma).$

We relate the sets $\mathcal{D}(\tau)$ and continued fractions expansions [101, p. 241, Lemma C.6], cf. [158, p. 130, Proposition 2.4].

###### Lemma 4.

For $\tau>0$ and $x\in\Omega$, $x\in\mathcal{D}(\tau)$ if and only if there is some $C=C(x)>0$ such that $q_{n+1}(x)\leq Cq_{n}(x)^{\tau-1}$ for all $n\geq 1$.

###### Proof.

For $x\in\Omega$, write $q_{n}=q_{n}(x)$. By (12), $\left\|q_{n}x\right\|>\frac{1}{q_{n+1}+q_{n}}$, and by (11), $\left\|q_{n}x\right\|<\frac{1}{q_{n+1}}$. Suppose $x\in\mathcal{D}(\tau)$, so there is some $\gamma>0$ such that $x\in\mathcal{D}(\tau,\gamma)$. Then

 $q_{n+1}<\frac{1}{\left\|q_{n}x\right\|}\leq\gamma^{-1}q_{n}^{\tau-1}.$

Suppose $q_{n+1}\leq Cq_{n}^{\tau-1}$ for all $n\geq 1$. For $q\in\mathbb{Z}_{\geq 1}$, take $q_{n}\leq q. Using Theorem 2,

 $\left\|qx\right\|\geq\left\|q_{n}x\right\|>\frac{1}{q_{n+1}+q_{n}}>\frac{1}{2q% _{n+1}}\geq\frac{1}{2}C^{-1}q_{n}^{-\tau+1}\geq\frac{1}{2C}\cdot q^{-\tau+1},$

which means that $x\in\mathcal{D}(\tau,\frac{1}{2C})$. ∎

For $K$ a positive integer, let

 $\mathcal{B}_{K}=\{x\in\Omega:\textrm{a_{n}(x)\leq K for all n\geq 1}\},$

so $\mathcal{B}=\bigcup_{K\geq 1}\mathcal{B}_{K}$ is the set of those $x\in\Omega$ with bounded partial quotients.

###### Lemma 5.

For $x\in\Omega$, $x\in\mathcal{D}(2)$ if and only if $x\in\mathcal{B}$.

###### Proof.

Write $a_{n}=a_{n}(x)$ and $q_{n}=q_{n}(x)$. If $x\in\mathcal{D}(2)$ then there is some $\gamma>0$ such that $x\in\mathcal{D}(2,\gamma)$, hence for $n\geq 1$,

 $q_{n+1}<\frac{1}{\left\|q_{n}x\right\|}\leq\gamma^{-1}q_{n}.$

Now, $q_{n+1}=a_{n+1}q_{n}+q_{n-1}$ for $n\geq 1$, so

 $a_{n+1}

which shows that $x$ has bounded partial quotients.

If $x\in\mathcal{B}_{K}$, let $q\in\mathbb{Z}_{\geq 1}$ and let $q_{n}\leq q. Using Theorem 2 and then (12),

 $\left\|qx\right\|\geq\left\|q_{n}x\right\|>\frac{1}{q_{n+1}+q_{n}}=\frac{1}{a_% {n+1}q_{n}+q_{n-1}+q_{n}}>\frac{1}{(a_{n+1}+2)q_{n}}.$

As $x\in\mathcal{B}_{K}$,

 $\left\|qx\right\|>\frac{1}{(K+2)q_{n}}\geq\frac{1}{K+2}q^{-1},$

which means that $x\in\mathcal{D}(2,\frac{1}{K+2})$. ∎

A complex number $\alpha$ is called an algebraic number of degree $d$, $d\geq 0$, if there is some polynomial $f\in\mathbb{Z}[x]$ with degree $d$ such that $f(\alpha)=0$ and if $g\in\mathbb{Z}[x]$ has degree $ and $g(\alpha)=0$ then $g=0$. An algebraic number number of degree $2$ is called a quadratic irrational. Let $\alpha\in\Omega$. It was proved by Euler [59, p. 144, Theorem 176] that if there is some $p>0$ and some $L$ such that $a_{l+p}(\alpha)=a_{l}(\alpha)$ for all $l\geq L$ then $\alpha$ is a quadratic irrational The converse of this was proved by Lagrange [59, p. 144, Theorem 177], namely that a quadratic irrational has eventually periodic partial quotients. For example, $\alpha=\sqrt{11}-3\in\Omega$ is a quadratic irrational, being a root of $x^{2}+6x-2$, and one works out that $a_{1}(\alpha)=3,a_{2}(\alpha)=6$, and that $a_{l+2}(\alpha)=a_{l}(\alpha)$ for $l\geq 1$. In particular, if $\alpha\in\Omega$ is a quadratic irrational, then $\alpha$ has bounded partial quotients.

Liouville [59, p. 161, Theorem 191] proved that if $x\in\Omega$ is an algebraic number of degree $d\geq 2$, then $x\in\mathcal{D}(d)$. The Thue-Siegel-Roth theorem [48, p. 55, Theorem 1.23] states that if $x\in\Omega$ is an algebraic number, then for any $\delta>0$ there is some $q_{\delta}\in\mathbb{Z}_{\geq 1}$ such that for all $q\geq q_{\delta}$,

 $\left\|qx\right\|\geq q^{-1-\delta}.$

See Schmidt [131, p. 195, Theorem 2B].

## 6 Sums of reciprocals

We are interested in getting bounds on the sum $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}$. This is an appealing question because the terms $\frac{1}{\left\|jx\right\|}$ are unbounded.

Rather than merely stating that $\sum_{k=1}^{\infty}\frac{1}{k}=\infty$, we give more information by giving the estimate

 $\sum_{k=1}^{n}\frac{1}{k}=\log n+\gamma+O(n^{-1}),$

where $\gamma$ is Euler’s constant. Likewise, rather than merely stating that there are infinitely many primes, we state more information with [90, p. 102, §28]

 $\sum_{p\leq x}\frac{1}{p}=\log\log x+B+O\left(\frac{1}{\log x}\right),$

for a certain constant $B$ (namely “Merten’s constant”), or with [90, p. 226, §61]

 $\sum_{p\leq x}p=\frac{x^{2}}{2\log x}+O\left(\frac{x^{2}}{(\log x)^{2}}\right).$

Because $|\sin(\pi x)|=\sin(\pi\left\|x\right\|)\leq\pi\left\|x\right\|$ and

 $|\sin(\pi x)|=\sin(\pi\left\|x\right\|)\geq\frac{2}{\pi}\pi\left\|x\right\|=2% \left\|x\right\|,$

we have

 $\frac{1}{\pi}\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}\leq\sum_{j=1}^{m}\frac{% 1}{|\sin\pi jx|}\leq\frac{1}{2}\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}.$ (14)

Thus, getting bounds on $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}$ will give us bounds on $\sum_{j=1}^{m}\frac{1}{|\sin\pi jx|}$.

Let $\psi$ be a nondecreasing function defined on the positive integers such that $\psi(h)>0$ for $h\geq 1$ (for example, $\psi(h)=\log(2h)$). Following Kuipers and Niederreiter [85, p. 121, Definition 3.3], we say that an irrational number $x$ is of type $<\psi$ if $\left\|hx\right\|\geq\frac{1}{h\psi(h)}$ for all integers $h\geq 1$. If $\psi$ is a constant function, then we say that $x$ is of constant type.

###### Lemma 6.

$x\in\Omega$ is of constant type if and only if it has bounded partial quotients.

###### Proof.

Suppose that $x\in\Omega$ is of constant type. So there is some $K>0$ such that $\left\|hx\right\|\geq\frac{1}{hK}$ for all integers $h\geq 1$. For $n\geq 2$ we have $q_{n}=a_{n}q_{n-1}+q_{n-2}$, and hence, by (11),

 $a_{n}=\frac{q_{n}}{q_{n-1}}-\frac{q_{n-2}}{q_{n-1}}<\frac{q_{n}}{q_{n-1}}\leq q% _{n}\cdot K\left\|q_{n-1}x\right\|

showing that $x$ has bounded partial quotients.

Suppose that $x\in\Omega$ has bounded partial quotients, say $a_{n}\leq K$ for all $n\geq 1$. Let $h$ be a positive integer and take $q_{n}\leq h. Then first by Theorem 2 and then by (12),

 $\left\|hx\right\|\geq\left\|q_{n}x\right\|>\frac{1}{q_{n}+q_{n+1}}>\frac{1}{2q% _{n+1}}=\frac{1}{2(a_{n+1}q_{n}+q_{n-1})}>\frac{1}{2(a_{n+1}q_{n}+q_{n})},$

and so

 $\left\|hx\right\|>\frac{1}{2(K+1)}\frac{1}{q_{n}}\geq\frac{1}{2(K+1)}\frac{1}{% h},$

showing that $x$ is of constant type. ∎

However, almost all $x$ do not have bounded partial quotients [78, p. 60, Theorem 29]. Shallit  gives a survey on numbers with bounded partial quotients.

We state and prove a result of Khinchin’s [78, p. 69, Theorem 32] that we then use.

###### Lemma 7.

Let $f$ be a positive function on the positive integers. If

 $\sum_{q=1}^{\infty}f(q)<\infty,$

then for almost all $x\in\Omega$ there are only finitely many $q$ such that $\left\|qx\right\|.

###### Proof.

For each positive integer $q$, let $E_{q}=\{t\in\Omega:\left\|qt\right\|. If $t\in E_{q}$, then there is some integer $p$ with $0\leq p\leq q$ such that $\left|t-\frac{p}{q}\right|<\frac{f(q)}{q}$. It follows that

 $E_{q}\subset\left(0,\frac{f(q)}{q}\right)\cup\left(1-\frac{f(q)}{q},1\right)% \cup\bigcup_{p=1}^{q-1}\left(\frac{p}{q}-\frac{f(q)}{q},\frac{p}{q}+\frac{f(q)% }{q}\right).$

Therefore

 $\sum_{q=1}^{\infty}\mu(E_{q})\leq\sum_{q=1}^{\infty}2q\cdot\frac{f(q)}{q}=2% \sum_{q=1}^{\infty}f(q)<\infty.$

Let $E=\limsup_{q\to\infty}E_{q}$, i.e. $E=\{t\in\Omega:t\in E_{q}\,\textrm{for infinitely many q}\}$. Then by the Borel-Cantelli lemma [19, p. 59, Theorem 4.3] we have that $\mu(E)=0$. Therefore, for almost all $t\in\Omega$ there are only finitely many $q$ such that $t\in E_{q}$, i.e., for almost all $t\in\Omega$ there are only finitely many $q$ such that $\left\|qt\right\|. ∎

The above lemma is proved in Benedetto and Czaja [15, p. 183, Theorem 4.3.3] using the fact that a function of bounded variation is differentiable almost everywhere. We outline the proof. Define $F:[0,1]\to\mathbb{R}_{>0}$ by $F(x)=\frac{f(q)}{q}$ if $x=\frac{a}{q}$, $\gcd(a,q)=1$, $0\leq a\leq q$, and $F(x)=0$ if $x\in\Omega$. Writing $\mathscr{A}_{q}=\left\{\frac{a}{q}:0\leq a\leq q,\gcd(a,q)=1\right\}$, for $0=t_{0},

 $\sum_{j=0}^{N}F(t_{j})=\sum_{q=1}^{\infty}\sum_{j=0}^{N}F(t_{j})\cdot 1_{% \mathscr{A}_{q}}(t_{j})=\sum_{q=1}^{\infty}\frac{f(q)}{q}\sum_{j=0}^{N}1_{% \mathscr{A}_{q}}(t_{j})\leq\sum_{q=1}^{\infty}f(q).$

It follows that the total variation of $F$ is $\leq 2\sum_{q=1}^{\infty}f(q)$ and hence $F$ is a function of bounded variation. Because $F$ has bounded variation, the set $D_{F}$ of $x\in[0,1]$ at which $F$ is differentiable is a Borel set with $\lambda(D_{F})=1$. Check that $F^{\prime}(x)=0$ for $x\in D_{F}\setminus\mathbb{Q}$, and using this, if $\frac{a_{n}}{q_{n}}\to x$ with $\gcd(a_{n},q_{n})=1$ and $0\leq a_{n}\leq q_{n}$ then for some $N$, if $n\geq N$ then $\left|x-\frac{a_{n}}{q}\right|\geq\frac{F(q_{n})}{q_{n}}$.

We use the above lemma to prove the following result.

###### Lemma 8.

Let $\epsilon>0$. For almost all $x\in\Omega$, there is some $K>0$ such that $x$ is of type $.

###### Proof.

Let

 $E=\left\{t\in\Omega:\left\|ht\right\|<\frac{1}{h(\log h)^{1+\epsilon}}\,% \textrm{for infinitely many h}\right\}.$

Since $\sum_{h=1}^{\infty}\frac{1}{h(\log h)^{1+\epsilon}}$ converges, we have by Lemma 7 that $\mu(E)=0$. Let $t\in\Omega\setminus E$. Then $\left\|ht\right\|\geq\frac{1}{h(\log h)^{1+\epsilon}}$ for all sufficiently large $h$. It follows that there is some $K$ such that $t$ is of type $. ∎

The following technical lemma is from Kuipers and Niederreiter [85, p. 130, Exercise 3.9]; cf. Lang [92, p. 39, Lemma].

###### Lemma 9.

Let $x\in\Omega$ be of type $<\psi$. If $n\geq 0$ and if $0\leq h_{0}, then

 $\sum_{\stackrel{{1\leq j\leq q_{n}}}{{j+h_{0}
###### Proof.

Since $p_{n}$ and $q_{n}$ are relatively prime, the remainders of $jp_{n}$, $j=1,\ldots,q_{n}$, when divided by $q_{n}$ are all distinct. Then also, the remainders of $jp_{n}+h_{0}p_{n}$, $j=1,\ldots,q_{n}$, when divided by $q_{n}$ are all distinct. Let $\lambda_{j}$, $j=1,\ldots,q_{n}$, be the remainder of $jp_{n}+h_{0}p_{n}$ when divided by $q_{n}$. We have $\{\lambda_{j}:1\leq j\leq q_{n}\}=\{0,\ldots,q_{n}-1\}$; let $\lambda_{j_{1}}=0$, $\lambda_{j_{2}}=1$, and $\lambda_{j_{3}}=q_{n}-1$.

Write $x=\frac{p_{n}}{q_{n}}+\frac{\delta_{n}}{q_{n}q_{n+1}}$; by (11) we have $|\delta_{n}|<1$. If $j+h_{0} then by Theorem 2 we have $\left\|(j+h_{0})x\right\|\geq\left\|q_{n}x\right\|$, and since $x$ is of type $<\psi$ we have

 $\left\|(j+h_{0})x\right\|\geq\left\|q_{n}x\right\|\geq\frac{1}{q_{n}\psi(q_{n}% )}.$

Let, for $i=1,2,3$,

 $A_{i}=\begin{cases}1,&\textrm{if j_{i}+h_{0}

If $j+h_{0} and $j\neq j_{1},j_{2},j_{3}$, then

 $\left\|\frac{\lambda_{j}}{q_{n}}+\frac{(j+h_{0})\delta_{n}}{q_{n}q_{n+1}}% \right\|\geq\min\left\{\left\|\frac{\lambda_{j}}{q_{n}}+\frac{1}{q_{n}}\right% \|,\left\|\frac{\lambda_{j}}{q_{n}}-\frac{1}{q_{n}}\right\|\right\}.$

It follows that

 $\displaystyle\sum_{\stackrel{{1\leq j\leq q_{n}}}{{j+h_{0} $\displaystyle=$ $\displaystyle\frac{A_{1}}{\left\|(j_{1}+h_{0})x\right\|}+\frac{A_{2}}{\left\|(% j_{2}+h_{0})x\right\|}+\frac{A_{3}}{\left\|(j_{3}+h_{0})x\right\|}$ $\displaystyle+\sum_{\stackrel{{1\leq j\leq q_{n}}}{{\stackrel{{% j+h_{0} $\displaystyle\leq$ $\displaystyle 3q_{n}\psi(q_{n})+\sum_{\stackrel{{1\leq j\leq q_{n% }}}{{\stackrel{{j+h_{0} $\displaystyle\leq$ $\displaystyle 3q_{n}\psi(q_{n})+\sum_{\stackrel{{1\leq j\leq q_{n% }}}{{\stackrel{{j+h_{0} $\displaystyle+\sum_{\stackrel{{1\leq j\leq q_{n}}}{{\stackrel{{% j+h_{0} $\displaystyle<$ $\displaystyle 3q_{n}\psi(q_{n})+2\sum_{k=1}^{q_{n}-1}\frac{1}{\left\|\frac{k}{% q_{n}}\right\|}.$

But $\frac{1}{\left\|y\right\|}<\frac{1}{R(y)}+\frac{1}{1-R(y)}$ for $y\not\in\mathbb{Z}$, so

 $\displaystyle\sum_{k=1}^{q_{n}-1}\frac{1}{\left\|\frac{k}{q_{n}}\right\|}$ $\displaystyle<$ $\displaystyle\sum_{k=1}^{q_{n}-1}\frac{1}{R\left(\frac{k}{q_{n}}\right)}+\frac% {1}{1-R\left(\frac{k}{q_{n}}\right)}$ $\displaystyle=$ $\displaystyle\sum_{k=1}^{q_{n}-1}\frac{1}{\frac{k}{q_{n}}}+\frac{1}{1-\frac{k}% {q_{n}}}$ $\displaystyle=$ $\displaystyle 2q_{n}\sum_{k=1}^{q_{n}-1}\frac{1}{k}$ $\displaystyle<$ $\displaystyle 3q_{n}\log q_{n};$

the last inequality is because, for all $m\geq 1$,

 $\sum_{k=1}^{m}\frac{1}{k}<\frac{3}{2}\log(m+1).$

We now use Lemma 9 to obtain a bound on $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}$ in terms of the type of $x$. This is from Kuipers and Niederreiter [85, p. 131, Exercise 3.11]; cf. Lang [92, p. 39, Theorem 2].

###### Theorem 10.

If $x\in\Omega$ is of type $<\psi$, then for all $m\geq 1$ we have

 $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}<12m(\psi(m)+\log m).$
###### Proof.

We shall prove the claim by induction. Because $x$ is of type $<\psi$, we have

 $\frac{1}{\left\|x\right\|}\leq\psi(1)<12\psi(1),$

so the claim is true for $m=1$. Take $m>1$ and assume that the claim is true for all $1\leq m^{\prime}. We shall show that it is true for $m$.

Let $q_{n}\leq m. Either $m<2q_{n}$ or $m\geq 2q_{n}$. In the first case, using Lemma 9 we have

 $\displaystyle\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{q_{n}}\frac{1}{\left\|jx\right\|}+\sum_{j=1}^{m-q_{n}% }\frac{1}{\left\|(j+q_{n})x\right\|}$ $\displaystyle<$ $\displaystyle 12q_{n}(\psi(q_{n})+\log q_{n})$ $\displaystyle<$ $\displaystyle 12m(\psi(m)+\log m).$

In the second case, using the induction assumption (with $m^{\prime}=m-q_{n}$) and Lemma 9 we have, because $q_{n},

 $\displaystyle\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{m-q_{n}}\frac{1}{\left\|jx\right\|}+\sum_{j=1}^{q_{n}% }\frac{1}{\left\|(j+m-q_{n})x\right\|}$ $\displaystyle<$ $\displaystyle 12(m-q_{n})\left(\psi(m-q_{n})+\log(m-q_{n})\right)+6q_{n}(\psi(% q_{n})+\log q_{n})$ $\displaystyle<$ $\displaystyle 12(m-q_{n})\left(\psi(m)+\log m\right)+12q_{n}(\psi(q_{n})+\log q% _{n})$ $\displaystyle=$ $\displaystyle 12m(\psi(m)+\log m)-12q_{n}\left(\psi(m)-\psi(q_{n})+\log m-\log q% _{n}\right)$ $\displaystyle\leq$ $\displaystyle 12m(\psi(m)+\log m).$

The claim is true in both cases, which completes the proof by induction. ∎

We can now establish for almost all $x\in\Omega$ a tractable upper bound on the sum $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}$, and thus by (14) also on $\sum_{j=1}^{m}\frac{1}{|\sin\pi jx|}$; cf. Lang [92, p. 44, Theorem 3].

###### Theorem 11.

Let $\epsilon>0$. For almost all $x\in\Omega$, we have

 $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}=O\left(m\left(\log m\right)^{1+% \epsilon}\right),$

while if $x$ has bounded partial quotients then

 $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}=O\left(m\log m\right).$
###### Proof.

Let $\epsilon>0$. By Lemma 8, for almost all $x\in\Omega$ there is some $K$ such that $x$ is of type $. For such an $x$, it follows from Theorem 10 that for all $m\geq 1$,

 $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}<12m(K(\log m)^{1+\epsilon}+\log m)=O% \left(m\left(\log m\right)^{1+\epsilon}\right).$

If $x$ has bounded partial quotients then by Lemma 6 it is of constant type, say $\psi(m)=K$ for some $K$. It follows from Theorem 10 that for all $m\geq 1$,

 $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}<12m(K+\log m)=O\left(m\log m\right).$

For example, take $x=\frac{-1+\sqrt{5}}{2}$, for which $a_{n}(x)=1$ for all $n\in\mathbb{N}$, and so in particular $x$ has bounded partial quotients. In Figure 1 we plot $\frac{1}{m\log m}\cdot\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}$ for $m=5000,\ldots,40000$. These computations suggest that there is some constant $C$ for which $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}>Cm\log m$ for all $m$. In Theorem 13 we shall prove that for almost all $x\in\Omega$ there is such a $C(x)$.

However, the estimate in Theorem 11 is not true for all $x\in\Omega$. Define $a\in\mathbb{N}^{\mathbb{N}}$ as follows. Let $a_{1}$ be any element of $\mathbb{N}$. Then inductively, define $a_{n+1}$ to be any element of $\mathbb{N}$ that is $>q_{n}^{n-1}$. Then for any $n\in\mathbb{N}$, using (11) and $q_{n+1}=a_{n+1}q_{n}+q_{n-1}>a_{n+1}q_{n}$ we get

 $|q_{n}v(a)-p_{n}|<\frac{1}{q_{n+1}}<\frac{1}{a_{n+1}q_{n}}<\frac{1}{q_{n}^{n}},$

hence $\left\|q_{n}v(a)\right\|<\frac{1}{q_{n}^{n}}$, and then

 $\sum_{j=1}^{q_{n}}\frac{1}{\left\|jv(a)\right\|}>\frac{1}{\left\|q_{n}v(a)% \right\|}>q_{n}^{n}.$

Using $\epsilon=1$, it is then straightforward to check that there is no constant $C$ such that $\sum_{j=1}^{m}\frac{1}{\left\|jv(a)\right\|}\leq Cm(\log m)^{2}$ for all $m$.

We will need the following lemma [19, p. 324, Lemma 3] to prove a theorem; cf. Khinchin [78, p. 63, Theorem 30].

###### Lemma 12.

If $\phi$ is a function defined on the positive integers such that $\phi(n)\geq 1$ for all $n$ and

 $\sum_{n=1}^{\infty}\frac{1}{\phi(n)}<\infty,$

then for almost all $x\in\Omega$ there are only finitely many $n$ such that $a_{n}(x)\geq\phi(n)$.

###### Proof.

For a measurable set $A\subset\Omega$, define

 $\gamma(A)=\frac{1}{\log 2}\int_{A}\frac{1}{1+x}d\mu(x),$

in other words $d\gamma(x)=\frac{1}{(1+x)\log 2}d\mu(x)$. Thus for a measurable set $A\subset\Omega$ we have

 $\gamma(A)\leq\frac{1}{\log 2}\int_{A}dx=\frac{1}{\log 2}\mu(A)$

and

 $\gamma(A)\geq\frac{1}{\log 2}\int_{A}\frac{1}{2}dx=\frac{1}{2\log 2}\mu(A).$

We will use that $\gamma$ is an invariant measure for the Gauss transformation $T:\Omega\to\Omega$ [44, p. 77, Lemma 3.5], i.e., if $A\subset\Omega$ is a measurable set then

 $(T_{*}\gamma)(A)=\gamma(T^{-1}(A))=\gamma(A).$

Let $A_{n}=\{x\in\Omega:a_{n}(x)\geq\phi(n)\}$, $n\geq 1$. As

 $a_{n}(x)=\left[\frac{1}{T^{n-1}(x)}\right],$

we have

 $\displaystyle A_{n}$ $\displaystyle\subset$ $\displaystyle\{x\in\Omega:\frac{1}{T^{n-1}(x)}>\phi(n)\}$ $\displaystyle=$ $\displaystyle\left\{x\in\Omega:T^{n-1}(x)<\frac{1}{\phi(n)}\right\}$ $\displaystyle=$ $\displaystyle(T^{n-1})^{-1}\left(\left[0,\frac{1}{\phi(n)}\right)\setminus% \mathbb{Q}\right).$

Hence

 $\displaystyle\mu(A_{n})$ $\displaystyle\leq$ $\displaystyle\mu\left((T^{n-1})^{-1}\left(\left[0,\frac{1}{\phi(n)}\right)% \setminus\mathbb{Q}\right)\right)$ $\displaystyle\leq$ $\displaystyle 2\log 2\cdot\gamma\left((T^{n-1})^{-1}\left(\left[0,\frac{1}{% \phi(n)}\right)\setminus\mathbb{Q}\right)\right)$ $\displaystyle=$ $\displaystyle 2\log 2\cdot\gamma\left(\left[0,\frac{1}{\phi(n)}\right)% \setminus\mathbb{Q}\right)$ $\displaystyle\leq$ $\displaystyle 2\log 2\cdot\frac{1}{\log 2}\cdot\mu\left(\left[0,\frac{1}{\phi(% n)}\right)\setminus\mathbb{Q}\right)$ $\displaystyle=$ $\displaystyle\frac{2}{\phi(n)}.$

It follows that

 $\sum_{n=1}^{\infty}\mu(A_{n})<\infty,$

and thus by the Borel-Cantelli lemma [19, p. 59, Theorem 4.3] we have

 $\mu(\limsup_{n\to\infty}A_{n})=0.$

Let $\lambda$ be Lebesgue measure on $I=[0,1]$, let $d\gamma(x)=\frac{1}{(1+x)\log 2}d\lambda(x)$, and let $T:I\to I$ be the Gauss transformation, $T(x)=x^{-1}-[x]^{-1}$ for $x>0$ and $T(0)=0$, for which $T_{*}\gamma=\gamma$ [44, p. 77, Lemma 3.5]. Suppose that $\nu$ is a Borel probability measure on $[0,1]$ such that the pushforward measure $T_{*}\nu$ is absolutely continuous with respect to $\nu$. For $f\in L^{1}(\nu)$, define $d\nu_{f}=fd\nu$, and define $P_{\nu}:L^{1}(\nu)\to L^{1}(\nu)$ by

 $P_{\nu}f=\frac{d(T_{*}\nu_{f})}{d\nu},\qquad f\in L^{1}(\nu).$

Thus, for $g\in L^{\infty}(\nu)$, using the change of variables formula,

 $\int_{I}g\cdot P_{\nu}fd\nu=\int_{I}gd(T_{*}\nu_{f})=\int_{I}g\circ Td\nu_{f}=% \int_{I}(g\circ T)\cdot fd\nu,$

in particular,

 $\int_{I}P_{\nu}fd\nu=\int_{I}fd\nu.$

We call $P_{\nu}:L^{1}(\nu)\to L^{1}(\nu)$ a Perron-Frobenius operator for $T$. It is a fact that if $f\geq 0$ then $P_{\nu}f\geq 0$ [69, p. 57, Proposition 2.1.1], namely $P_{\nu}\geq 0$. It can be proved that for $f\in L^{1}(\gamma)$, for almost all $x\in I$ [69, p. 59, Proposition 2.1.2],

 $(P_{\gamma}f)(x)=\sum_{k=1}^{\infty}\frac{x+1}{(x+k)(x+k+1)}\cdot f\left(\frac% {1}{x+k}\right),$

and for $f\in L^{1}(\lambda)$, for almost all $x\in I$ [69, p. 60, Corollary 2.1.4],

 $(P_{\lambda}f)(x)=\sum_{k=1}^{\infty}\frac{1}{(x+k)^{2}}\cdot f\left(\frac{1}{% x+k}\right),$

and with $g(x)=(x+1)f(x)$, for $n\geq 1$ it holds for almost all $x\in I$ that $(P_{\lambda}^{n}f)(x)=\frac{(P_{\gamma}^{n}g)(x)}{x+1}$. Iosifescu and Kraaikamp [69, Chapter 2] give a detailed presentation of Perron-Frobenius operators for the Gauss map. We make the final remark that $P_{\nu}1_{I}=1_{I}$ is equivalent with $\int_{I}1_{E}d\nu=\int_{I}1_{T^{-1}(E)}d\nu$ for all Borel sets $E$ in $I$, i.e. $\nu(E)=\nu(T^{-1}(E))$, which in turn means $T_{*}\nu=\nu$, cf. Markov operators [83, Chapter 5, §5.1, pp. 177-186]. An object similar to Perron-Frobenius operators for the Gauss transformation is the zeta-function for the Gauss transformation, for which see Lagarias [87, p. 58, §3.3].

The following theorem gives a lower bound on the sum $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}$, cf. [150, p. 4, Theorem 3.1].

###### Theorem 13.

For almost all $x\in\Omega$ there is some $C>0$ such that

 $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}>Cm\log m.$
###### Proof.

For all $x\in\Omega$, if $n\geq 1$ then $q_{n}\geq 2^{\frac{n-1}{2}}$, by (9). Take $\phi(n)=2^{\frac{n-2}{2}}$. The series $\sum_{n=1}^{\infty}\frac{1}{\phi(n)}$ converges, so by Lemma 12, for almost all $x\in\Omega$ there are only finitely many $n$ such that $a_{n}\geq\phi(n)$. That is, for almost all $x\in\Omega$ there is some $n_{0}$ such that if $n\geq n_{0}$ then

 $a_{n}<\phi(n)=2^{\frac{n-2}{2}}\leq q_{n-1}.$

Hence, if $n\geq n_{0}$ then

 $q_{n}=a_{n}q_{n-1}+q_{n-2}

It follows that for almost all $x\in\Omega$ there is some $K$ such that

 $q_{n+1} (15)

for all $n\geq 0$.

For such an $x$, let $m$ be a positive integer and let $q_{n}\leq m. For $1\leq j\leq m$ we have by (11),

 $\left\|jx-\frac{jp_{n}}{q_{n}}\right\|\leq\left|jx-\frac{jp_{n}}{q_{n}}\right|% =j\left|x-\frac{p_{n}}{q_{n}}\right|<\frac{j}{q_{n}q_{n+1}}<\frac{1}{q_{n}}.$

Therefore for $1\leq j\leq m$ we have

 $\left\|jx\right\|\leq\left\|jx-\frac{jp_{n}}{q_{n}}\right\|+\left\|\frac{jp_{n% }}{q_{n}}\right\|<\frac{1}{q_{n}}+\left\|\frac{jp_{n}}{q_{n}}\right\|.$

Let $L=[\frac{m}{q_{n}}]$, so $Lq_{n}\leq m$. Then,

 $\displaystyle\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}$ $\displaystyle>$ $\displaystyle\sum_{j=1}^{m}\frac{1}{\frac{1}{q_{n}}+\left\|\frac{jp_{n}}{q_{n}% }\right\|}$ $\displaystyle\geq$ $\displaystyle\sum_{l=0}^{L-1}\sum_{h=1}^{q_{n}}\frac{1}{\frac{1}{q_{n}}+\left% \|\frac{(lq_{n}+h)p_{n}}{q_{n}}\right\|}$ $\displaystyle=$ $\displaystyle q_{n}\sum_{l=0}^{L-1}\sum_{h=1}^{q_{n}}\frac{1}{1+q_{n}\left\|% \frac{hp_{n}}{q_{n}}\right\|}$ $\displaystyle=$ $\displaystyle Lq_{n}\sum_{h=1}^{q_{n}}\frac{1}{1+q_{n}\left\|\frac{hp_{n}}{q_{% n}}\right\|}$ $\displaystyle=$ $\displaystyle Lq_{n}\sum_{k=0}^{q_{n}-1}\frac{1}{1+q_{n}\cdot\frac{k}{q_{n}}}$ $\displaystyle>$ $\displaystyle Lq_{n}\log q_{n}.$

But if $y\geq 1$ then $[y]>\frac{y}{2}$, so $L=[\frac{m}{q_{n}}]>\frac{m}{2q_{n}}$. Hence by (15),

 $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}>\frac{m}{2}\log q_{n}>\frac{m}{2}% \log\sqrt{\frac{q_{n+1}}{K}}>\frac{m}{2}\log\sqrt{\frac{m}{K}},$

and thus there is some $C>0$ such that $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}>Cm\log m$ for all $m\geq 1$. ∎

The following is from Kuipers and Niederreiter [85, p. 131, Exercise 3.12].

###### Theorem 14.

If $x\in\Omega$ is of type $<\psi$, then for all $m\geq 1$ we have

 $\sum_{j=1}^{m}\frac{1}{j\left\|jx\right\|}<24\left((\log m)^{2}+\psi(m)+\sum_{% j=1}^{m}\frac{\psi(j)}{j}\right).$
###### Proof.

Summation by parts is the following identity, which can be easily checked:

 $\sum_{n=1}^{N}a_{n}(b_{n+1}-b_{n})=a_{N+1}b_{N+1}-a_{1}b_{1}-\sum_{n=1}^{N}b_{% n+1}(a_{n+1}-a_{n}).$

Let $a_{j}=\frac{1}{j}$, let $s_{j}=\sum_{h=1}^{j}\frac{1}{\left\|hx\right\|}$, let $b_{1}=0$, and let $b_{j}=s_{j-1}$ for $j\geq 2$. Doing summation by parts gives

 $\sum_{j=1}^{m}\frac{1}{j\left\|jx\right\|}=\frac{1}{m+1}s_{m}-\sum_{j=1}^{m}s_% {j}\left(\frac{1}{j+1}-\frac{1}{j}\right)=\frac{1}{m+1}s_{m}+\sum_{j=1}^{m}s_{% j}\frac{1}{j(j+1)}.$

As $x$ is of type $<\psi$, we can use Theorem 10 to get $s_{j}<12j(\psi(j)+\log j)$ for each $j\geq 1$. Therefore

 $\displaystyle\sum_{j=1}^{m}\frac{1}{j\left\|jx\right\|}$ $\displaystyle<$ $\displaystyle\frac{1}{m+1}12m(\psi(m)+\log m)+\sum_{j=1}^{m}\frac{12(\psi(j)+% \log j)}{j+1}$ $\displaystyle<$ $\displaystyle 12(\psi(m)+\log m)+12(\log m)^{2}+12\sum_{j=1}^{m}\frac{\psi(j)}% {j+1}$ $\displaystyle<$ $\displaystyle 24(\log m)^{2}+12\psi(m)+12\sum_{j=1}^{m}\frac{\psi(j)}{j+1}.$

Erdős  proves that for almost all $x$,

 $\sum_{j=1}^{m}\frac{1}{j\left\|jx\right\|}=(1+o(1))(\log m)^{2}.$

Kruse  gives a comprehensive investigation of the sums $\sum_{j=1}^{m}\frac{1}{j^{s}\left\|jx\right\|^{t}}$, $s,t\geq 0$. The results depend on whether $s$ and $t$ are are less than, equal, or greater than $1$, and on whether $t. One of the theorems proved by Kruse is the following [84, p. 260, Theorem 7]. If $t>1$ and $0\leq s\leq t$, and if $\epsilon>0$, then for almost all $x$ we have

 $\sum_{j=1}^{m}\frac{1}{j^{s}\left\|jx\right\|^{t}}=O\left(m^{t-s}(\log m)^{(1+% \epsilon)t}\right).$

Haber and Osgood [56, p. 387, Theorem 1] prove that for real $t\geq 1$, $A>1$, $M>0$, $r>0$, there is some $C=C(t,A,M,r)>0$ such that for all $x\in\Omega$ satisfying $q_{n+1}(x), for all positive integers $K$,

 $\sum_{n=K+1}^{[AK]}\left\|nx\right\|^{-t}>\begin{cases}CK\log K&t=1\\ CK^{1+(t-1)/r}&t>1.\end{cases}$

We remind ourselves that according to Theorem 4, the elements of $\mathcal{D}(r+1)$ are those $x\in\Omega$ for which there is some $c(x)>0$ such that $q_{n+1}(x)\leq C(x)q_{n}(x)^{r}$ for all $n\geq 1$.

For $x\in\mathbb{Z}+\frac{1}{2}$, define $\{\{x\}\}=\frac{1}{2}$. If $x\not\in\mathbb{Z}+\frac{1}{2}$, then there is an integer $m_{x}$ for which $|x-m_{x}|<|x-n|$ for all integers $n\neq m_{x}$, and we define $\{\{x\}\}=x-m_{x}$. Sinai and Ulcigrai [138, p. 96, Proposition 2] prove that if $\alpha$ has bounded partial quotients, then there is some $C(\alpha)$ such that for all $M$,

 $\left|\sum_{m=1}^{M}\frac{1}{\{\{m\alpha\}\}}\right|\leq C(\alpha)M.$

## 7 Weyl’s inequality, Vinogradov’s estimate, Farey fractions, and the circle method

Write

 $\mathscr{A}=\{(a,q)\in\mathbb{Z}^{2}:\gcd(a,q)=1,q\geq 1\}.$

We first prove four estimates following Nathanson [107, pp. 104–110, Lemmas 4.8–4.11] that we will use in what follows; cf. Vinogradov [149, p. 26, Chapter I, Lemma 8b].

###### Lemma 15.

There is some $C$ such that if $\alpha\in\mathbb{R}$, $(a,q)\in\mathscr{A}$, and

 $\left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q^{2}},$

then

 $\sum_{1\leq r\leq q/2}\frac{1}{\left\|\alpha r\right\|}\leq Cq\log q.$
###### Proof.

For $q=1$, $\sum_{1\leq r\leq q/2}\frac{1}{\left\|\alpha r\right\|}=0$. For $q\geq 2$, let $1\leq r\leq\frac{q}{2}$. As $\gcd(a,q)=1$ and $r\not\equiv 0\pmod{q}$, $ar\not\equiv 0\pmod{q}$. So for $\mu_{r}=\left[\frac{ar}{q}\right]$, there is some $1\leq\sigma_{r}\leq q-1$ such that $ar=\mu_{r}q+\sigma_{r}$. Then

 $\left\|\frac{ar}{q}\right\|=\left\|\frac{\sigma_{r}}{q}\right\|\in\left\{\frac% {\sigma_{r}}{q},1-\frac{\sigma_{r}}{q}\right\}=\left\{\frac{\sigma_{r}}{q},% \frac{q-\sigma_{r}}{q}\right\}.$

Put $\frac{s_{r}}{q}=\left\|\frac{ar}{q}\right\|$, so (i) $s_{r}=\sigma_{r}$ or (ii) $s_{r}=q-\sigma_{r}$. In case (i), $\frac{s_{r}}{q}=\frac{ar}{q}-\mu_{r}$. In case (ii), $\frac{s_{r}}{q}=1-\left(\frac{ar}{q}-\mu_{r}\right)$. In case (i) let $\epsilon_{r}=1,m_{r}=\mu_{r}$, and in case (ii) let $\epsilon_{r}=-1,m_{r}=\mu_{r}+1$. Thus, whether (i) or (ii) holds we have

 $\frac{s_{r}}{q}=\epsilon_{r}\left(\frac{ar}{q}-m_{r}\right),\quad\frac{s_{r}}{% q}=\left\|\frac{ar}{q}\right\|,\quad 1\leq s_{r}\leq\frac{q}{2}.$

Write

 $\alpha-\frac{a}{q}=\frac{\theta}{q^{2}},$

for some real $\theta$, $|\theta|\leq 1$. For $\theta_{r}=\frac{2r}{q}\theta$, which satisfies $|\theta_{r}|\leq|\theta|\leq 1$,

 $\alpha r=\frac{ar}{q}+\frac{r\theta}{q^{2}}=\frac{ar}{q}+\frac{\theta_{r}}{2q}.$

Then

 $\displaystyle\left\|\alpha r\right\|$ $\displaystyle=\left\|\frac{ar}{q}+\frac{\theta_{r}}{2q}\right\|$ $\displaystyle=\left\|\epsilon_{r}\frac{s_{r}}{q}+m_{r}+\frac{\theta_{r}}{2q}\right\|$ $\displaystyle\geq\left\|\epsilon_{r}\frac{s_{r}}{q}+m_{r}\right\|-\left\|\frac% {\theta_{r}}{2q}\right\|$ $\displaystyle=\frac{s_{r}}{q}-\left|\frac{\theta_{r}}{2q}\right|$ $\displaystyle\geq\frac{s_{r}}{q}-\frac{1}{2q}.$

Take $1\leq r_{1},r_{2}\leq\frac{q}{2}$ and suppose that $s_{r_{1}}=s_{r_{2}}$. So

 $\epsilon_{r_{1}}\left(\frac{ar_{1}}{q}-m_{r_{1}}\right)=\epsilon_{r_{2}}\left(% \frac{ar_{2}}{q}-m_{r_{2}}\right)$

hence $ar_{1}\equiv\epsilon_{r_{1}}\epsilon_{r_{2}}ar_{2}\pmod{q}$. As $\gcd(a,q)=1$, $r_{1}\equiv\epsilon_{r_{1}}\epsilon_{r_{2}}r_{2}\pmod{q}$. Because $1\leq r_{1},r_{2}\leq q$, if $r_{1}\equiv r_{2}\pmod{q}$ then $r_{1}=r_{2}$ and if $r_{1}\equiv-r_{2}\pmod{q}$ then $r_{1}=\frac{q}{2}$ and $r_{2}=\frac{q}{2}$, so in any case $r_{1}=r_{2}$. Therefore

 $\left\{\frac{s_{r}}{q}:1\leq r\leq\frac{q}{2}\right\}=\left\{\frac{s}{q}:1\leq s% \leq\frac{q}{2}\right\}.$

Using the two things we have established,

 $\displaystyle\sum_{1\leq r\leq q/2}\frac{1}{\left\|\alpha r\right\|}$ $\displaystyle\leq\sum_{1\leq r\leq q/2}\frac{1}{\frac{s_{r}}{q}-\frac{1}{2q}}$ $\displaystyle=\sum_{1\leq s\leq q/2}\frac{1}{\frac{s}{q}-\frac{1}{2q}}$ $\displaystyle=2q\sum_{1\leq s\leq q/2}\frac{1}{2s-1}$ $\displaystyle\leq 2q\sum_{1\leq s\leq q/2}\frac{1}{s}$ $\displaystyle\leq 2q\left(\log\frac{q}{2}+\gamma+O(q^{-1})\right)$ $\displaystyle=O(q\log q).$

###### Lemma 16.

There is some $C$ such that if $\alpha\in\mathbb{R}$, $(a,q)\in\mathscr{A}$, and

 $\left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q^{2}},$

then for any positive real $V$ and nonnegative integer $h$,

 $\sum_{r=1}^{q}\min\left(V,\frac{1}{\left\|\alpha(hq+r)\right\|}\right)\leq C(V% +q\log q).$
###### Proof.

Write

 $\alpha=\frac{a}{q}+\frac{\theta}{q^{2}},$

which satisfies $|\theta|\leq 1$, and for $1\leq r\leq q$ define

 $\delta_{r}=R(\theta h)+\frac{\theta r}{q},$

which satisfies $-1\leq\delta_{r}<2$. Then

 $\displaystyle\alpha(hq+r)$ $\displaystyle=\left(\frac{a}{q}+\frac{\theta}{q^{2}}\right)(hq+r)$ $\displaystyle=ah+\frac{ar}{q}+\frac{\theta h}{q}+\frac{\theta r}{q^{2}}$ $\displaystyle=ah+\frac{ar}{q}+\frac{R(\theta h)+[\theta h]}{q}+\frac{\theta r}% {q^{2}}$ $\displaystyle=ah+\frac{ar+[\theta h]+\delta_{r}}{q}.$

For $m_{r}=\left[\frac{ar+[\theta h]+\delta_{r}}{q^{2}}\right]$,

 $R(\alpha(hq+r))=R\left(\frac{ar+[\theta h]+\delta_{r}}{q}\right)=\frac{ar+[% \theta h]+\delta_{r}}{q}-m_{r}.$

Suppose that $t\in\left[0,1-\frac{1}{q}\right]$ and that $t\leq R(\alpha(hq+r))\leq t+\frac{1}{q}$. Then

 $qt\leq ar+[\theta h]+\delta_{r}-qm_{r}\leq qt+1.$

This implies, as $\delta_{r}\geq-1$,

 $ar-qm_{r}\leq qt+1-[\theta h]-\delta_{r}\leq qt+1-[\theta h]+1=qt-[\theta h]+2$

and, as $\delta_{r}<2$,

 $ar-qm_{r}\geq qt-[\theta h]-\delta_{r}>qt-[\theta h]-2,$

so $ar-qm_{r}\in J_{t}$, writing

 $J_{t}=(qt-[\theta h]-2,qt-[\theta h]+2].$

For $1\leq r_{1},r_{2}\leq q$, if $ar_{1}-qm_{r_{1}}=ar_{2}-qm_{r_{2}}$ then $ar_{1}\equiv ar_{2}\pmod{q}$, and $\gcd(a,q)=1$ implies $r_{1}\equiv r_{2}\pmod{q}$; and $1\leq r_{1},r_{2}\leq q$ so $r_{1}=r_{2}$. For $t\in\left[0,1-\frac{1}{q}\right]$, four integers belong to $J_{t}$, hence

 $\{1\leq r\leq q:ar-qm_{r}\in J_{t}\}$

has at most four elements. But

 $\left\{1\leq r\leq q:R(\alpha(hq+r))\in\left[t,t+\frac{1}{q}\right]\right\}% \subset\{1\leq r\leq q:ar-qm_{r}\in J_{t}\}.$

Now,

 $\begin{split}&\left\{1\leq r\leq q:\left\|\alpha(hq+r)\right\|\in\left[t,t+% \frac{1}{q}\right]\right\}\\ =&\left\{1\leq r\leq q:R(\alpha(hq+r))\in\left[t,t+\frac{1}{q}\right]\right\}% \\ &\cup\left\{1\leq r\leq q:1-R(\alpha(hq+r))\in\left[t,t+\frac{1}{q}\right]% \right\}\\ =&\left\{1\leq r\leq q:R(\alpha(hq+r))\in\left[t,t+\frac{1}{q}\right]\right\}% \\ &\cup\left\{1\leq r\leq q:R(\alpha(hq+r))\in\left[1-\frac{1}{q}-t,1-t\right]% \right\},\end{split}$

whence

 $\displaystyle\left\{1\leq r\leq q:\left\|\alpha(hq+r)\right\|\in\left[t,t+% \frac{1}{q}\right]\right\}$ $\displaystyle\subset\{1\leq r\leq q:ar-qm_{r}\in J_{t}\}$ $\displaystyle\cup\{1\leq r\leq q:ar-qm_{r}\in J_{1-\frac{1}{q}-t}\}.$

This shows that if $t\in\left[0,1-\frac{1}{q}\right]$ then

 $\left\{1\leq r\leq q:\left\|\alpha(hq+r)\right\|\in\left[t,t+\frac{1}{q}\right% ]\right\}$

has at most eight elements. For $0\leq k<\frac{q}{2}$, writing

 $I_{k}=\left[\frac{k}{q},\frac{k}{q}+\frac{1}{q}\right],$

the set $\{1\leq r\leq q:\left\|\alpha(hq+r)\right\|\in I_{k}\}$ has at most eight elements. Therefore

 $\displaystyle\sum_{1\leq r\leq q}\min\left(V,\frac{1}{\left\|\alpha(hq+r)% \right\|}\right)$ $\displaystyle=\sum_{0\leq k $\displaystyle\leq 8V+\sum_{1\leq k $\displaystyle\leq 8V+\sum_{1\leq k $\displaystyle=O(V+q\log q).$

###### Lemma 17.

There is some $C$ such that if $\alpha\in\mathbb{R}$, $(a,q)\in\mathscr{A}$,

 $\left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q^{2}},$

$U\geq 1$ is a real number, and $n$ is a positive integer, then

 $\sum_{1\leq k\leq U}\min\left(\frac{n}{k},\frac{1}{\left\|\alpha k\right\|}% \right)\leq C\left(\frac{n}{q}+U+q\right)\log 2qU.$
###### Proof.

For $1\leq k\leq U$ there is some $0\leq h_{k}<\frac{U}{q}$ and $1\leq r_{k}\leq q$ such that $k=qh_{k}+r_{k}$, and then

 $\displaystyle\sum_{1\leq k\leq U}\min\left(\frac{n}{k},\frac{1}{\left\|\alpha k% \right\|}\right)$ $\displaystyle\leq\sum_{0\leq h $\displaystyle\leq\sum_{1\leq r\leq q/2}\frac{1}{\left\|\alpha r\right\|}+\sum_% {q/2 $\displaystyle+\sum_{1\leq h $\displaystyle\leq C_{1}q\log q+\sum_{q/2 $\displaystyle+\sum_{1\leq h

the last inequality by Lemma 15. If $\frac{q}{2} then $\frac{1}{r}<\frac{2}{q}=\frac{2}{(h+1)q}$ for $h=0$, and if $1\leq h<\frac{U}{q}$ and $1\leq r\leq q$ then $h\geq\frac{h+1}{2}$ so $hq+r>hq\geq\frac{(h+1)q}{2}$ and hence $\frac{1}{hq+r}<\frac{2}{(h+1)q}$, whence

 $\begin{split}&\sum_{q/2

Consquently

 $\sum_{1\leq k\leq U}\min\left(\frac{n}{k},\frac{1}{\left\|\alpha k\right\|}% \right)\leq C_{1}q\log q+2\sum_{0\leq h

Lemma 16 with $V=\frac{n}{(h+1)q}$ says

 $\sum_{1\leq r\leq q}\min\left(\frac{n}{(h+1)q},\frac{1}{\left\|\alpha(hq+r)% \right\|}\right)\leq C_{2}\left(\frac{n}{(h+1)q}+q\log q\right),$

therefore

 $\displaystyle\sum_{1\leq k\leq U}\min\left(\frac{n}{k},\frac{1}{\left\|\alpha k% \right\|}\right)$ $\displaystyle\ll q\log q+\sum_{0\leq h $\displaystyle\ll q\log q+\frac{n}{q}\sum_{1\leq h<\frac{U}{q}+1}\frac{1}{h}+q(% \log q)\left(\frac{U}{q}+1\right)$ $\displaystyle\ll q\log q+\frac{n}{q}\log\left(\frac{U}{q}+1\right)+U\log q$ $\displaystyle\ll U\log 2qU+q\log 2qU+\frac{n}{q}\log\left(\frac{U}{q}+1\right).$

If $U\leq q$ then $\frac{U}{q}+1\leq 2\leq 2qU$, and if $U>q$ then $\frac{U}{q}+1\leq U+1\leq 2U\leq 2qU$, hence

 $\sum_{1\leq k\leq U}\min\left(\frac{n}{k},\frac{1}{\left\|\alpha k\right\|}% \right)\ll U\log 2qU+q\log 2qU+\frac{n}{q}\log 2qU.$

###### Lemma 18.

There is some $C$ such that if $\alpha\in\mathbb{R}$, $(a,q)\in\mathscr{A}$,

 $\left|\alpha-\frac{p}{q}\right|\leq\frac{1}{q^{2}},$

and $U,V\geq 1$ are real numbers, then

 $\sum_{1\leq k\leq U}\min\left(V,\frac{1}{\left\|\alpha k\right\|}\right)\leq C% \left(q+U+V+\frac{UV}{q}\right)\max\{1,\log q\}.$
###### Proof.

For $1\leq k\leq U$ there is some $0\leq h_{k}<\frac{U}{q}$ and $1\leq r_{k}\leq q$ such that $k=qh_{k}+r_{k}$, and then, as in the proof of Lemma 17,

 $\displaystyle\sum_{1\leq k\leq U}\min\left(V,\frac{1}{\left\|\alpha k\right\|}\right)$ $\displaystyle\leq\sum_{0\leq h $\displaystyle\leq C_{1}q\log q+2\sum_{0\leq h

Using Lemma 16,

 $\displaystyle\sum_{1\leq k\leq U}\min\left(V,\frac{1}{\left\|\alpha k\right\|}\right)$ $\displaystyle\leq C_{1}q\log q+2C_{2}\sum_{0\leq h $\displaystyle\ll q\log q+(V+q\log q)\left(\frac{U}{q}+1\right)$ $\displaystyle\ll q\log q+\frac{UV}{q}+V+U\log q.$

Weyl’s inequality [107, p. 114, Theorem 4.3] is the following. For $k\geq 2$ and $\epsilon>0$, there is some $C(k,\epsilon)$ such that if $\alpha\in\mathbb{R}$, $f(x)$ is a real polynomial with highest degree term $\alpha x^{k}$, $(a,q)\in\mathscr{A}$, and

 $\left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q^{2}},$

then, writing $S_{N}(f)=\sum_{j=1}^{N}e^{2\pi if(j)}$ and $K=2^{k-1}$,

 $|S_{N}(f)|\leq C(k,\epsilon)\cdot N^{1+\epsilon}(N^{-1}+q^{-1}+N^{-k}q)^{\frac% {1}{K}}.$

Weyl’s inequality is proved using Lemma 18.

Montgomery [103, Chapter 3] gives a similar but more streamlined presentation of Weyl’s inequality. Chandrasekharan  gives a historical survey of exponential sums.

Vinogradov’s estimate [146, p. 26, Theorem 3.1] states that there is some $C$ such that for $n\geq 2$, $1\leq q\leq n$, $\gcd(a,q)=1$, and $\left|\alpha-\frac{a}{q}\right|\leq q^{-2}$, then

 $|f_{n}(\alpha)|\leq C(nq^{-1/2}+n^{4/5}+n^{1/2}q^{1/2})(\log n)^{4},$ (16)

where $f_{n}(\alpha)=\sum_{p\leq n}(\log p)e^{2\pi i\alpha p}$; cf. Nathanson [107, p. 220, Theorem 8.5] and Vinogradov [149, p. 131, Chapter IX, Theorem 1]. This is proved using Lemma 17.

Fix $B>0$ and let $P_{n}=(\log n)^{B}$. For $1\leq a\leq q\leq P_{n}$ and $\gcd(a,q)=1$, let

 $\mathfrak{M}_{n}(q,a)=\left\{\alpha\in\mathbb{R}:\left|\alpha-\frac{a}{q}% \right|\leq P_{n}n^{-1}\right\},$

called a major arc. One checks that there is some $n_{B}$ such that if $n\geq n_{B}$, then $\mathfrak{M}_{n}(q,a)$ and $\mathfrak{M}_{n}(q^{\prime},a^{\prime})$ are disjoint when $(q,a)\neq(q^{\prime},a^{\prime})$. Let

 $\mathfrak{M}_{n}=\bigcup_{1\leq a\leq q\leq P_{n},\gcd(a,q)=1}\mathfrak{M}_{n}% (q,a).$

The Farey fractions of order $N$ are

 $\mathfrak{F}_{N}=\left\{\frac{h}{k}:0\leq h\leq k\leq N,\gcd(h,k)=1\right\}.$

Cf. the Stern-Brocot tree [55, §4.5]. For early appearances of Farey fractions, see Dickson [35, pp. 155–158, Chapter V]. It is proved by Cauchy that if $h/k$ and $h^{\prime}/k^{\prime}$ are successive elements of $\mathfrak{F}_{N}$, then $kh^{\prime}-hk^{\prime}=1$ [59, p. 23, Theorem 28]. Let

 $\phi(m)=|\{1\leq k\leq m:\gcd(k,m)=1\}|,$

the Euler phi function, and write $\Phi(N)=\sum_{1\leq m\leq N}\phi(m)$. One sees that $|\mathfrak{F}_{N}|=1+\Phi(N)$, and it was proved by Mertens [59, p. 268] that

 $\Phi(N)=\frac{3N^{2}}{\pi^{2}}+O(N\log N).$

Let $\lambda$ be Lebesgue measure on $\mathbb{R}$. For $n\geq n_{B}$, because the major arcs are pairwise disjoint,

 $\displaystyle\lambda(\mathfrak{M}_{n})$ $\displaystyle=\sum_{1\leq a\leq q\leq P_{n},\gcd(a,q)=1}2P_{n}n^{-1}$ $\displaystyle=\left(\sum_{m=1}^{P_{n}}\phi(m)\right)2P_{n}n^{-1}$ $\displaystyle=\frac{6}{\pi^{2}}P_{n}^{3}n^{-1}+O(P_{n}^{2}n^{-1}\log P_{n}).$

Let $I_{n}=(P_{n}n^{-1},1+P_{n}n^{-1}]$, which for $n>2P_{n}^{2}$ contains $\mathfrak{M}_{n}$. Let

 $\mathfrak{m}_{n}=I_{n}\setminus\mathfrak{M}_{n},$

called the minor arcs.

With $f_{n}(\alpha)=\sum_{p\leq n}(\log p)e^{2\pi i\alpha p}$ and

 $R(n)=\sum_{p_{1}+p_{2}+p_{3}=n}(\log p_{1})(\log p_{2})(\log p_{3}),$

we have

 $R(n)=\int_{I_{n}}f_{n}(\alpha)^{3}e^{-2\pi in\alpha}d\alpha=\int_{\mathfrak{M}% _{n}}f_{n}(\alpha)^{3}e^{-2\pi in\alpha}d\alpha+\int_{\mathfrak{m}_{n}}f_{n}(% \alpha)^{3}e^{-2\pi in\alpha}d\alpha.$

Using (16), it can be proved that for $A>0$ with $B\geq 2A+10$ [146, p. 29, Theorem 3.2],

 $\int_{\mathfrak{m}_{n}}|f_{n}(\alpha)|^{3}d\alpha=O(n^{2}(\log n)^{-A}).$

Writing

 $\mathfrak{S}(n)=\left(\prod_{p\nmid n}(1+(p-1)^{-3})\right)\prod_{p\mid n}(1-(% p-1)^{-2}),$

called the singular series, it is proved, using the Siegel-Walfisz theorem on primes in arithmetic progressions [102, p. 381, Corollary 11.19], that for $A>0$ with $B\geq 2A$ [146, p. 31, Theorem 3.3],

 $\int_{\mathfrak{M}_{n}}f_{n}(\alpha)^{3}e^{-2\pi in\alpha}d\alpha=\frac{1}{2}n% ^{2}\mathfrak{S}(n)+O(n^{2}(\log n)^{-A}).$

Thus

 $R(n)=\frac{1}{2}n^{2}\mathfrak{S}(n)+O(n^{2}(\log n)^{-A}),$

and it follows from this that there is some $n_{0}$ such that if $n\geq n_{0}$ is odd then there are primes $p_{1},p_{2},p_{3}$ such that $n=p_{1}+p_{2}+p_{3}$.

For integers $a,b$ with $\gcd(a,b)=1$, the Ford circle $C(a,b)$ is the circle in $\mathbb{C}$ that touches the line $\mathrm{Im}\,z=0$ at $z=\frac{a}{b}$ and has radius $\frac{1}{2b^{2}}$; in other words, $C(a,b)$ is the circle in $\mathbb{C}$ with center $\frac{a}{b}+\frac{i}{2b^{2}}$ and radius $\frac{1}{2b^{2}}$. It is straightforward to prove that if $C(a,b)$ and $C(c,d)$ are Ford circles, then they are tangent if and only if $(bc-ad)^{2}=1$, and otherwise they are disjoint [4, p. 100, Theorem 5.6]. It is also straightforward to prove [4, p. 101, Theorem 5.7] that if $\frac{h_{1}}{k_{1}}<\frac{h}{k}<\frac{h_{2}}{k_{2}}$ are successive elements of $\mathfrak{F}_{N}$, then $C(h_{1},k_{1})$ and $C(h,k)$ touch at

 $\frac{h}{k}-\frac{k_{1}}{k(k^{2}+k_{1}^{2})}+\frac{i}{k^{2}+k_{1}^{2}}$

and $C(h,k)$ and $C(h_{2},k_{2})$ touch at

 $\frac{h}{k}+\frac{k_{2}}{k(k^{2}+k_{2}^{2})}+\frac{i}{k^{2}+k_{2}^{2}}.$

Bonahon [21, pp. 207 ff., Chapter 8] explains Ford circles in the language of hyperbolic geometry.

We remind ourselves that $|\mathfrak{F}_{N}|=1+\Phi(N)=1+\sum_{m=1}^{N}\phi(m)$ and let $\rho_{0,N}<\cdots<\rho_{\Phi(N),N}$ be the elements of $\mathfrak{F}_{N}$. In particular, $\rho_{0,N}=0$ and $\rho_{\Phi(N),N}=1$. For $\rho_{n,N}=\frac{h_{n,N}}{k_{n,N}}$ with $\gcd(h_{h,N},k_{n,N})=1$, write $C_{n,N}=C(h_{n,N},k_{n,N})$.

Let $A_{0,N}$ be the clockwise arc of $C_{0,N}$ from $i$ to the point at which $C_{0,N}$ and $C_{1,N}$ touch. For $0, let $A_{n,N}$ be the clockwise arc of $C_{n,N}$ from the point at which $C_{n-1,N}$ and $C_{n,N}$ touch to the point at which $C_{n,N}$ and $C_{n+1,N}$ touch. Finally, let $A_{\Phi(N),N}$ be the clockwise arc of $C_{\Phi(N),N}$ from the point at which $C_{\Phi(N)-1,N}$ and $C_{\Phi(N),N}$ touch to $i+1$. Let $A_{N}$ be the composition of the arcs

 $A_{0,N},\ldots,A_{\Phi(N),N},$ (17)

which is a contour from $i$ to $i+1$.

Write $H=\{\tau\in\mathbb{C}:\mathrm{Im}\,\tau>0\}$. The Dedekind eta function $\eta:H\to\mathbb{C}$ is defined by

 $\eta(\tau)=e^{\pi i\tau/12}\prod_{m=1}^{\infty}(1-e^{2\pi im\tau}).$

It is straightforward to check that $\eta$ is analytic and that $\eta(\tau)\neq 0$ for all $\tau\in H$ [143, pp. 17–18, §1.44]. For $(h,k)\in\mathscr{A}$, let

 $s(h,k)=\sum_{r=1}^{k-1}\frac{r}{k}\left(\frac{hr}{k}-\left[\frac{hr}{k}\right]% -\frac{1}{2}\right)=\sum_{r=1}^{k-1}\frac{r}{k}P_{1}(hr/k),$

called a Dedekind sum; $P_{1}$ is the periodic Bernoulli function. Also, for $\begin{pmatrix}a&b\\ c&d\end{pmatrix}\in SL_{2}(\mathbb{Z})$ write

 $\epsilon(a,b,c,d)=\exp\left(\pi i\left(\frac{a+d}{12c}+s(-d,c)\right)\right).$

The functional equation for the Dedekind eta function [4, p. 52, Theorem 3.4] is

 $\eta\left(\frac{a\tau+b}{c\tau+d}\right)=\epsilon(a,b,c,d)(-i(c\tau+d))^{1/2}% \eta(\tau),\quad\begin{pmatrix}a&b\\ c&d\end{pmatrix}\in SL_{2}(\mathbb{Z}),\tau\in H.$

Let $p(n)$ be the number of ways of writing $n$ as a sum of positive integers where the order does not matter, called the partition function. For example, $4,3+1,2+2,2+1+1,1+1+1+1$ are the partitions of $4$, so $p(4)=5$. Denoting by $D(0,1)$ the open disc with center $0$ and radius $1$, define $F:D(0,1)\to\mathbb{C}$ by

 $F(z)=\prod_{m=1}^{\infty}(1-z^{m})^{-1}=\sum_{n=0}^{\infty}p(n)z^{n};$

that the product and the series are equal was found by Euler. $F$ is analytic. On the one hand, $p(n)=\frac{F^{(n)}(0)}{n!}$, and on the other hand, by Cauchy’s integral formula [143, p. 82, Theorem 2.41], if $C$ is a circle with center $0$ and radius $0 then

 $F^{(n)}(0)=\frac{n!}{2\pi i}\int_{C}\frac{F(z)}{z^{n+1}}dz.$

Taking $C$ to be the circle with center $0$ and radius $e^{-2\pi}$ and doing the change of variable $z=e^{2\pi i\tau}$,

 $\displaystyle p(n)$ $\displaystyle=\frac{1}{2\pi i}\int_{i}^{i+1}\frac{F(e^{2\pi i\tau})}{e^{2\pi i% (n+1)\tau}}\cdot 2\pi ie^{2\pi i\tau}d\tau$ $\displaystyle=\int_{i}^{i+1}F(e^{2\pi i\tau})e^{-2\pi in\tau}d\tau$ $\displaystyle=\int_{A_{N}}F(e^{2\pi i\tau})e^{-2\pi in\tau}d\tau,$

where we remind ourselves that $A_{N}$ is the contour (17) from $i$ to $i+1$. Using this and the functional equation for the Dedekind eta function, Rademacher [4, p. 104, Theorem 5.10] proves that for $n\geq 1$,

 $p(n)=\frac{1}{\pi\sqrt{2}}\sum_{k=1}^{\infty}A_{k}(n)k^{1/2}\frac{d}{dn}\frac{% \sinh\left(\pi\sqrt{\frac{2}{3}}\cdot\frac{1}{k}\sqrt{n-\frac{1}{24}}\right)}{% \sqrt{n-\frac{1}{24}}},$

for $A_{k}(n)=\sum_{0\leq h.

We make a final remark about the Farey fractions. Writing the elements of $\mathfrak{F}_{N}$ as $\rho_{0,N}<\cdots<\rho_{\Phi(N),N}$, let $\eta_{n,N}=\rho_{n,N}-\frac{n}{\Phi(N)}$ for $1\leq n\leq N$. For example, $\Phi(5)=10$ and

 $\left\{\rho_{1,5},\ldots,\rho_{10,5}\right\}=\left\{\frac{1}{5},\frac{1}{4},% \frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{% 4}{5},1\right\},$

and

 $\{\eta_{1,5},\ldots,\eta_{10,5}\}=\left\{\frac{1}{10},\frac{1}{20},\frac{1}{30% },0,0,0,-\frac{1}{30},-\frac{1}{20},-\frac{1}{10},0\right\}.$

Landau , following work of Franel, proves that the Riemann hypothesis is true if and only if for every $\epsilon>0$,

 $\sum_{n=1}^{\Phi(N)}|\eta_{n,N}|=O(N^{\frac{1}{2}+\epsilon}).$

For example, for $N=5$, the left-hand side is $\frac{11}{30}$. See Narkiewicz [106, p. 40, §2.2.3].

## 8 Discrepancy and exponential sums

Discrepancy and Diophantine approximation are covered by Kuipers and Niederreiter [85, Chapters 1–2 ] and by Drmota and Tichy [41, §§1.1–1.4], especially [41, pp. 48–66, §1.4.1].

Let $\omega=(x_{n})$, $n\geq 1$, be a sequence of real numbers, and let $E\subset[0,1)$. For a positive integer $N$, let $A(E;N;\omega)$ be the number of $x_{n}$, $1\leq n\leq N$, such that $R(x_{n})\in E$. We say that the sequence $\omega$ is uniformly distributed modulo $1$ if we have for all $a$ and $b$ with $0\leq a that

 $\lim_{N\to\infty}\frac{A([a,b);N;\omega)}{N}=b-a.$

It can be shown [85, p. 3, Corollary 1.1] that a sequence $x_{n}$ is uniformly distributed modulo $1$ if and only if for every Riemann integrable function $f:[0,1]\to\mathbb{R}$ we have

 $\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^{N}f(R(x_{n}))=\int_{0}^{1}f(t)dt.$ (18)

Thus, if a sequence is uniformly distributed then the integral of any Riemann integrable function on $[0,1]$ can be approximated by sampling according to this sequence. This approximation can be quantified using the notion of discrepancy.

It can be proved [85, p. 7, Theorem 2.1] that a sequence $x_{n}$ is uniformly distributed modulo $1$ if and only if for all nonzero integers $h$ we have

 $\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^{N}e^{2\pi ihx_{n}}=0;$

this is called Weyl’s criterion. But if $x\in\Omega$, then

 $\left|\sum_{n=1}^{N}e^{2\pi ihnx}\right|=\left|\frac{1-e^{2\pi ihNx}}{1-e^{2% \pi ihx}}\right|\leq\frac{2}{|1-e^{2\pi ihx}|}=\frac{1}{|\sin\pi hx|}.$ (19)

We thus obtain the following theorem.

###### Theorem 19.

If $x\in\Omega$ then the sequence $nx$ is uniformly distributed modulo $1$.

The discrepancy of a sequence $\omega$ is defined, for $N$ a positive integer, by

 $D_{N}(\omega)=\sup_{0\leq a

One proves that the sequence $\omega$ is uniformly distributed modulo $1$ if and only if $D_{N}(\omega)\to 0$ as $N\to\infty$ [85, p. 89, Theorem 1.1].

For $f:[0,1]\to\mathbb{R}$, let $V(f)$ denote the total variation of $f$. Koksma’s inequality [85, p. 143, Theorem 5.1] states that for any sequence $\omega=(x_{n})$, for any $f:[0,1]\to\mathbb{R}$ of bounded variation, and for any positive integer $N$, we have

 $\left|\frac{1}{N}\sum_{n=1}^{N}f(R(x_{n}))-\int_{0}^{1}f(t)dt\right|\leq V(f)D% _{N}(\omega).$ (20)

Following Kuipers and Niederreiter [85, p. 122, Lemma 3.2], we can bound the discrepancy of the sequence $nx$ in terms of the sum on the left-hand side of Theorem 14

###### Lemma 20.

There is some $C>0$ such that for all $x\in\Omega$, $\omega=(nx)$, and for all positive integers $m$ we have

 $D_{N}(\omega)
###### Proof.

We shall use the following inequality, which lets us bound the discrepancy of a sequence in terms of exponential sums formed from the elements of the sequence. The Erdős-Turán theorem [85, p. 114, Eq. 2.42] states that there is some constant $C>0$ such that for any sequence $\omega=(x_{n})$ of real numbers, any positive integer $N$, and any positive integer $m$ we have

 $D_{N}(\omega)\leq C\left(\frac{1}{m}+\sum_{j=1}^{m}\frac{1}{j}\left|\frac{1}{N% }\sum_{n=1}^{N}e^{2\pi ijx_{n}}\right|\right).$ (21)

Take $x_{n}=nx$. For each $j\geq 1$, by (19) we have

 $\left|\sum_{n=1}^{N}e^{2\pi ijnx}\right|\leq\frac{1}{|\sin\pi jx|}=\frac{1}{% \sin(\pi\left\|jx\right\|)}.$

But $\sin t\geq\frac{2}{\pi}t$ for $0\leq t\leq\frac{\pi}{2}$, so

 $\frac{1}{\sin(\pi\left\|jx\right\|)}\leq\frac{1}{2\left\|jx\right\|}<\frac{1}{% \left\|jx\right\|}.$

Using this in (21) gives us

 $D_{N}(\omega)

which is the claim. ∎

It follows from Theorem 14 and Lemma 20 (taking $m=N$) that if $x$ is of type $ then

 $D_{N}(\omega)=O\left(\frac{(\log N)^{2+\epsilon}}{N}\right).$ (22)

Lemma 8 tells us that for almost all $x\in\Omega$ there is some $K>0$ such that $x$ is of type $, so for almost all $x\in\Omega$, the bound (22) is true. It likewise follows that if $x$ has bounded partial quotients then

 $D_{N}(\omega)=O\left(\frac{(\log N)^{2}}{N}\right).$ (23)

In fact, it can be proved that if $x\in\mathcal{B}_{K}$ then, for $g=\frac{1+\sqrt{5}}{2}$ [85, p. 125, Theorem 3.4],

 $D_{N}(\omega)\leq 3N^{-1}+\left(\frac{1}{\log g}+\frac{K}{\log(K+1)}\right)N^{% -1}\log N.$

We use the above bounds in the proof of the following theorem.

###### Theorem 21.

Let $\epsilon>0$. For almost all $x$ we have

 $\sum_{n=1}^{N}\left\|nx\right\|=\frac{N}{4}+O((\log N)^{2+\epsilon}),$

while if $x$ has bounded partial quotients then

 $\sum_{n=1}^{N}\left\|nx\right\|=\frac{N}{4}+O((\log N)^{2}).$
###### Proof.

Let $f(t)=\left\|t\right\|$. Then $V(f)=1$ and $\int_{0}^{1}f(t)dt=\frac{1}{4}$, so we get from Koksma’s inequality (20) that

 $\left|\frac{1}{N}\sum_{n=1}^{N}\left\|nx\right\|-\frac{1}{4}\right|\leq D_{N}(% \omega),$

thus

 $\sum_{n=1}^{N}\left\|nx\right\|=\frac{N}{4}+O(ND_{N}(\omega)).$

The claims then follow respectively from (22) and (23). ∎

Like we mentioned at the beginning of §6, because $|\sin(\pi x)|=\sin(\pi\left\|x\right\|)\leq\pi\left\|x\right\|$ and $|\sin(\pi x)|=\sin(\pi\left\|x\right\|)\geq\frac{2}{\pi}\cdot\pi\left\|x\right% \|=2\left\|x\right\|$, we have

 $2\sum_{n=1}^{N}\left\|nx\right\|\leq\sum_{n=1}^{N}|\sin(\pi nx)|\leq\pi\sum_{n% =1}^{N}\left\|nx\right\|.$

Thus Theorem 21 also gives estimates for $\sum_{n=1}^{N}|\sin(\pi nx)|$.

We can investigate the sum $\sum_{n=1}^{N}R(nx)$ rather than $\sum_{n=1}^{N}\left\|nx\right\|$; see Lang [92, p. 37, Theorem 1], who proves that for almost all $x\in\Omega$,

 $\sum_{n=1}^{N}R(nx)=\frac{N}{2}+O((\log N)^{2+\epsilon}).$

For $x\in\Omega$, let $q_{n}=q_{n}(x)$, the denominator of the $n$th convergent of the continued fraction expansion of $x$, and let $a_{n}=a_{n}(x)$, the $n$th partial quotient of the continued fraction expansion of $x$. For $m\geq 1$, one can prove [18, p. 211, Proposition 1] that $m$ can be written in one and only one way in the form

 $m=\sum_{k=1}^{\infty}z_{k}q_{k-1}=\sum_{k=1}^{t}z_{k}q_{k-1},$ (24)

where (i) $0\leq z_{1}\leq a_{1}-1$, (ii) $0\leq z_{k}\leq a_{k}$ for $k\geq 2$, (iii) for $k\geq 1$, if $z_{k+1}=a_{k+1}$ then $z_{k}=0$, and (iv) $z_{t}\neq 0$ and $z_{k}=0$ for $k>t$. The expression (24) is called the Ostrowski expansion of $m$. We emphasize that this expansion depends on $x$. Berthé  surveys applications of this numeration system in combinatorics. For $n\geq 0$, define $d_{2n}=q_{2n}x-p_{2n}$ and $d_{2n+1}=p_{2n+1}-q_{2n+1}x$. Brown and Shiue [24, p. 184, Theorem 1] prove that for $x\in\Omega$,

 $\sum_{k=1}^{m}\left(R(kx)-\frac{1}{2}\right)=\sum_{k=1}^{t}(-1)^{k}z_{k}\left(% \frac{1}{2}-d_{k-1}\left(m_{k-1}+\frac{1}{2}z_{k}q_{k-1}+\frac{1}{2}\right)% \right),$ (25)

where $m_{0}=0$ and if $k\geq 1$ then $m_{k}=\sum_{j=1}^{k}z_{j}q_{j-1}$. If $k\geq 0$, then by (11) we have $0. For $k\geq 1$, using the fact that $q_{k}\geq m_{k}+1$ (for the same reason that if the highest power of $2$ appearing in a number’s binary expansion is $2^{k-1}$, then the number is $\leq 2^{k}-1$),

 $\displaystyle m_{k-1}+\frac{1}{2}z_{k}q_{k-1}+\frac{1}{2}$ $\displaystyle=$ $\displaystyle m_{k}-\frac{1}{2}z_{k}q_{k-1}+\frac{1}{2}$ $\displaystyle\leq$ $\displaystyle q_{k}-1-\frac{1}{2}z_{k}q_{k-1}+\frac{1}{2}$ $\displaystyle=$ $\displaystyle q_{k}-\frac{1}{2}-\frac{1}{2}z_{k}q_{k-1}$ $\displaystyle<$ $\displaystyle q_{k}.$

Using (25), this inequality, and the inequality $0, we obtain

 $\displaystyle\left|\sum_{k=1}^{m}\left(R(kx)-\frac{1}{2}\right)\right|$ $\displaystyle\leq$ $\displaystyle\sum_{k=1}^{t}z_{k}\left|\frac{1}{2}-d_{k-1}\left(m_{k-1}+\frac{1% }{2}z_{k}q_{k-1}+\frac{1}{2}\right)\right|$ $\displaystyle<$ $\displaystyle\frac{1}{2}\sum_{k=1}^{t}z_{k}$ $\displaystyle<$ $\displaystyle\frac{1}{2}\sum_{k=1}^{t}a_{k}.$

If the continued fraction expansion of $x$ has bounded partial quotients, say $a_{k}\leq K$ for all $k$, we obtain from the above that

 $\left|\sum_{k=1}^{m}\left(R(kx)-\frac{1}{2}\right)\right|<\frac{Kt}{2}.$

It can be proved [24, p. 185, Fact 2] that $t<3\log m$. Thus, if $a_{k}\leq K$ for all $k$, then for $m\geq 1$,

 $\left|\sum_{k=1}^{m}\left(R(kx)-\frac{1}{2}\right)\right|<\frac{3K\log m}{2}.$

This is Lerch’s claim stated in §3. For example, if $x=\frac{-1+\sqrt{5}}{2}\in\Omega$ then $a_{k}(x)=1$ for all $k\geq 1$. We compute that

 $\sum_{k=1}^{1000000}\left(R(kx)-\frac{1}{2}\right)=0.941799\ldots;$

on the other hand, we compute that

 $\sum_{k=1}^{1000000}\left(R(k\pi)-\frac{1}{2}\right)=19.223414\ldots.$

Brown and Shiue [24, p. 185, Fact 1] use (25) to obtain the result of Sierpinski stated in §3 that for all $x\in\Omega$,

 $\sum_{k=1}^{m}R(kx)=\frac{m}{2}+o(m).$

They also prove [24, p. 188, Theorem 4] that for $A>0$, there exists some $d_{A}>0$ such that for $x\in\Omega$, if there are infinitely many $t$ such that $\sum_{k=1}^{t}a_{k}\leq At$ (which happens in particular if $x$ has bounded partial quotients), then there are infinitely many $m$ such that

 $\sum_{k=1}^{m}\left(R(kx)-\frac{1}{2}\right)>d_{A}\log m,$

and there are infinitely many $m$ such that

 $\sum_{k=1}^{m}\left(R(kx)-\frac{1}{2}\right)<-d_{A}\log m.$

It can be shown [92, p. 44, Theorem 4] that if $k$ is a positive integer and $\epsilon>0$, then for almost all $x$ we have

 $\left|\sum_{n=1}^{N}e^{2\pi in^{k}x}\right|=O\left(N^{\frac{1}{2}+\epsilon}% \right).$

Lang attributes this result to Vinogradov. But it is not so easy to obtain a bound on this exponential sum for specific $x$. For $k=2$, one can prove [92, p. 45, Lemma] that for any $x\in\Omega$,

 $\left|\sum_{n=1}^{N}e^{2\pi in^{2}x}\right|^{2}\leq N+4\sum_{n=1}^{N}\frac{1}{% |\sin 4\pi nx|}

cf. Steele [142, Problem 14.2]. By (14) this gives us

 $\left|\sum_{n=1}^{N}e^{2\pi in^{2}x}\right|^{2}

If $x$ has bounded partial quotients, it follows from Theorem 11 that

 $\left|\sum_{n=1}^{N}e^{2\pi in^{2}x}\right|=O\left(N^{1/2}(\log N)^{1/2}\right).$

Hardy and Littlewood [57, p. 28, Theorem B5] prove that if $x\in\Omega$ is an algebraic number, then there is some $0<\alpha(x)<1$ such that $\sum_{n=1}^{N}R(nx)=\frac{N}{2}+O(N^{\alpha(x)})$. Pillai  gives a different proof of this.

###### Theorem 22(Hardy and Littlewood, Pillai).

For $\tau>2$, if $x\in\mathcal{D}(\tau)$ then for $\alpha=\frac{\tau-2}{\tau-1}$,

 $\sum_{n=1}^{N}R(nx)=\frac{N}{2}+O(N^{\alpha}).$

Pillai  proves other identities and inequalities for $\sum_{n=1}^{N}R(nx)$, some for all $x\in\Omega$ and some for all algebraic $x\in\Omega$.

For $\omega=(x_{n})$, $n\geq 1$ and for $E\subset[0,1)$, we remind ourselves that $A(E;M;\omega)$ denotes the number of $x_{n}$, $1\leq n\leq M$, such that $R(x_{n})\in E$. Define for $M\geq 1$,

 $D_{M}^{*}(\omega)=\sup_{0<\beta\leq 1}\left|\frac{A([0,\beta);M;\omega)}{M}-% \beta\right|.$

It is straightforward to prove that $D_{M}^{*}\leq D_{M}\leq 2D_{M}^{*}$ [85, p. 91, Theorem 1.3]. For $N\geq 1$ write $r=\log N$. Let $\epsilon_{0}>0$ and let $N^{1/2}\leq\tau\leq N\exp(-r^{\epsilon_{0}})$. Suppose that $\alpha\in\mathbb{R}$ and

 $\alpha=\frac{a}{q}+\frac{\theta}{q\tau},\quad\gcd(a,q)=1,\quad\exp(r^{\epsilon% _{0}})\leq q\leq\tau,\quad|\theta|\leq 1.$

For $0<\beta<1$ denote by $H_{\beta}(N)$ the number of primes $p\leq N$ such that $R(\alpha p)\leq\beta$. Vinogradov [149, p. 177, Chapter XI, Theorem] proves that for $\epsilon>0$,

 $H_{\beta}(N)=\beta\pi(N)+O(N(q^{-1}+qN^{-1})^{\frac{1}{2}-\epsilon}+N^{\frac{4% }{5}+\epsilon}),\qquad N\to\infty.$

Let $\omega=(p_{n}\alpha)$, $n\geq 1$, where $p_{n}$ is the $n$th prime. Using Vinogradov’s estimate, one proves that for $\alpha\in\mathbb{R}\setminus\mathbb{Q}$, $D_{N}^{*}(\omega)\to 0$ as $N\to\infty$, which implies that the sequence $(p_{n}\alpha)$ is uniformly distributed modulo $1$. A clean proof of this is given by Pollicott [116, p. 200, Theorem 1], and this is also proved by Vaaler  using a Tauberian theorem. See also the early survey by Hua [68, pp. 98–99, §38].

Defining $S_{\alpha}(n)=\sum_{k=1}^{n}\left(R(k\alpha)-\frac{1}{2}\right)$, Beck [11, p. 14, Theorem 3.1] proves that there is some $c>0$ such that for every $\lambda\in\mathbb{R}$,

 $\frac{1}{N}\left|\left\{1\leq n\leq N:\frac{S_{\sqrt{2}}(n)}{c\sqrt{\log n}}% \leq\lambda\right\}\right|\to\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\lambda}\exp% \left(-\frac{u^{2}}{2}\right)du$

as $N\to\infty$. Beck [12, p. 20, Theorem 1.2] further proves that if $\alpha$ is a quadratic irrational, there are $C_{1}=C_{1}(\alpha)\in\mathbb{R}$ and $C_{2}=C_{2}(\alpha)\in\mathbb{R}_{>0}$ such that for $A,B\in\mathbb{R}$, $A,

 $\begin{split}&\frac{1}{N}\left|\left\{0\leq n

Beck and Chen 

## 9 Dirichlet series

The result of de la Vallée-Poussin  stated in §3 implies that there is no $s$ such that for all irrational $x$ the Dirichlet series $\sum_{n=1}^{\infty}\frac{n^{-s}}{|\sin n\pi x|}$ converges. It follows from this fact that there is no $s$ such that for all irrational $x$ the Dirichlet series $\sum_{n=1}^{\infty}\frac{n^{-s}}{\left\|nx\right\|}$ converges.

Lerch  in 1904 gives some statements without proof about the series

 $\sum_{\nu=1}^{\infty}\frac{\cot\nu\omega\pi}{(2\nu\pi)^{2m+1}}.$

He states that if $\omega$ is a real algebraic number that does not belong to $\mathbb{Q}$, then for sufficiently large $m$ this series converges, and states, for example, that with $\omega=\frac{1+\sqrt{5}}{2}$,

 $\sqrt{5}\sum_{\nu=1}^{\infty}\frac{\cot\nu\omega\pi}{(2\nu\pi)^{7}}=-\frac{8}{% 10!}.$

Writing $c_{r}(\theta)=\sum_{n=1}^{\infty}\frac{\cot(\pi n\theta)}{n^{2r-1}}$, Berndt [17, p. 135, Theorem 5.1] proves that if $\theta$ is a real algebraic number of degree $d$ and $1 (to say that $d>1$ is to say that $\theta$ is irrational), then $c_{r}(\theta)$ converges.

For a Dirichlet series $\sum_{n=1}^{\infty}a_{n}n^{-s}$, one can show [143, pp. 289–290, §9.11] that if the series is convergent at $s=\sigma_{0}+it_{0}$, then for $\sigma>\sigma_{0}$ and any $t$ the series is convergent at $s=\sigma+it$. It follows that there is some $\sigma_{0}\in[-\infty,\infty]$ such if $\sigma<\sigma_{0}$ then the series diverges at $s=\sigma+it$, and if $\sigma>\sigma_{0}$ then the series converges at $s=\sigma+it$. We call $\sigma_{0}$ the abscissa of convergence of the Dirichlet series. If each $a_{n}$ is a nonnegative real number, then the function

 $F(s)=\sum_{n=1}^{\infty}a_{n}n^{-s},\qquad\mathrm{Re}\,s>\sigma_{0},$

cannot be analytically continued to any domain that includes $s=\sigma_{0}$ [67, p. 101, Proposition 18].

Let $a_{n}$ be a sequence of complex numbers. It can be shown [143, pp. 292–293, §9.14] that if $s_{n}=a_{1}+\ldots+a_{n}$ and the sequence $s_{n}$ diverges, then the abscissa of convergence of the Dirichlet series $\sum_{n=1}^{\infty}a_{n}n^{-s}$ is given by

 $\sigma_{0}=\limsup_{n\to\infty}\frac{\log|s_{n}|}{\log n}.$

By Theorem 11 and Theorem 13 (taking, say, $\epsilon=1$), for almost all $x\in\Omega$ there are $C_{1},C_{2}$ such that for all positive integers $n$ we have

 $C_{1}n\log n<\sum_{j=1}^{n}\frac{1}{\left\|jx\right\|}

Thus, if $a_{n}=\frac{1}{\left\|nx\right\|}$, then

 $\frac{\log C_{1}}{\log n}+1+\frac{\log\log n}{\log n}<\frac{\log s_{n}}{\log n% }<\frac{\log C_{2}}{\log n}+1+\frac{2\log\log n}{\log n},$

and hence

 $\lim_{n\to\infty}\frac{\log s_{n}}{\log n}=1.$

It follows that for almost all $x\in\Omega$ the abscissa of convergence of the Dirichlet series $\sum_{n=1}^{\infty}\frac{1}{\left\|nx\right\|}n^{-s}$ is $\sigma_{0}=1$.

Likewise, by Theorem 21 (taking $\epsilon=1$), we get for almost all $x\in\Omega$ that $\sum_{j=1}^{n}\left\|jx\right\|=\frac{n}{4}+O\left((\log n)^{3}\right)$. We can then check that $\lim_{n\to\infty}\frac{\log s_{n}}{\log n}=1$, and hence that the abscissa of convergence of the Dirichlet series $\sum_{n=1}^{\infty}\left\|nx\right\|n^{-s}$ is $\sigma_{0}=1$.

A 1953 result of Mahler [48, pp. 107–108] implies that if $\alpha\in\mathbb{R}$ is an algebraic number of degree $d$, then, for $m=[20\cdot 2^{\frac{5(d-1)}{2}}]$, the Dirichlet series

 $\sum_{n=1}^{\infty}\frac{n^{-s}}{\sin n\alpha}$

has abscissa of convergence $\sigma_{0}\leq d(m+1)\log(m+1)$, and the power series

 $\sum_{n=1}^{\infty}\frac{z^{n}}{\sin n\alpha}$

Rivoal  presents later work on similar Dirichlet series. See also Queffélec and Queffélec . Lalín, Rodrigue and Rogers  prove results about Dirichlet series of the form $\sum_{n=1}^{\infty}\frac{n^{-s}}{\cos(n\pi z)}$. Duke and Imamoḡlu  review Hardy and Littlewood’s work on estimating lattice points in triangles, and prove results about lattice points in cones.

For $\theta\in\Omega$, write

 $R_{r,\theta}(\zeta,m)=\sum_{n=0}^{m}\frac{1}{r!}P_{r}(\zeta+n\theta),$

where $P_{r}$ is a periodic Bernoulli function. Spencer  proves that for any $\epsilon>0$ and almost all $\theta\in\Omega$,

 $R_{1,\theta}(\zeta,m)=O\left((\log m)^{1+\epsilon}\right).$

Another result Spencer proves in this paper is that if $q_{n}(\theta)=O(q_{n-1}^{h})$, then $R_{r,\theta}(\zeta,m)=O(m^{1-\frac{r}{h}})$ for $1\leq r. Schoißengeier  gives an explicit formula for $\sum_{k=0}^{N-1}P_{2}(k\alpha)$.

## 10 Power series

For a power series $\sum a_{n}z^{n}$ with radius of convergence $0\leq R\leq\infty$, the Cauchy-Hadamard formula [124, p. 111, Chapter 4, §1] states

 $R=\frac{1}{\limsup_{n\to\infty}|a_{n}|^{1/n}}=\liminf_{n\to\infty}|a_{n}|^{-1/% n}.$ (26)

The radius of convergence $R$ is equal to the supremum of those $t\geq 0$ for which $|a_{n}|t^{n}$ is a bounded sequence.

###### Lemma 23.

If $x\in\Omega$, then the power series

 $\sum_{n=1}^{\infty}\frac{z^{n}}{\left\|nx\right\|}$

and

 $\sum_{n=1}^{\infty}\frac{z^{n}}{|\sin\pi nx|},$

have the same radius of convergence.

###### Proof.

The radii of convergence of these power series are respectively

 $\liminf_{n\to\infty}\left\|nx\right\|^{1/n}\quad\textrm{and}\quad\liminf_{n\to% \infty}|\sin(\pi nx)|^{1/n}.$

On the one hand,

 $|\sin(\pi nx)|=\sin(\pi\left\|nx\right\|)\leq\pi\left\|nx\right\|$

Therefore, since $\lim_{n\to\infty}\pi^{1/n}=1$,

 $\liminf_{n\to\infty}|\sin(\pi nx)|^{1/n}\leq\liminf_{n\to\infty}\left(\pi\left% \|nx\right\|\right)^{1/n}=\liminf_{n\to\infty}\left\|nx\right\|^{1/n}$

On the other hand, since $\sin t\geq\frac{2}{\pi}t$ for $t\geq 0$,

 $|\sin(\pi nx)|=\sin(\pi\left\|nx\right\|)\geq\frac{2}{\pi}\pi\left\|nx\right\|% =2\left\|nx\right\|.$

Therefore, using $\lim_{n\to\infty}2^{1/n}=1$, we have

 $\liminf_{n\to\infty}|\sin(\pi nx)|^{1/n}\geq\liminf_{n\to\infty}\left(2\left\|% nx\right\|\right)^{1/n}=\liminf_{n\to\infty}\left\|nx\right\|^{1/n},$

showing that the two power series have the same radius of convergence. ∎

We show in the following theorem that for almost all $x$, the power series $\sum_{n=1}^{\infty}\frac{z^{n}}{\left\|nx\right\|}$ has radius of convergence $1$.

###### Theorem 24.

For almost all $x\in\Omega$, the power series

 $\sum_{n=1}^{\infty}\frac{z^{n}}{\left\|nx\right\|}$ (27)

has radius of convergence $1$.

###### Proof.

For $x\in\Omega$, let $R_{x}$ be the radius of convergence of the power series (27). We have $0<\left\|nx\right\|<\frac{1}{2}$, so $\frac{1}{\left\|nx\right\|}>2$. Therefore $\sum_{n=1}^{N}\frac{1}{\left\|nx\right\|}\to\infty$ as $N\to\infty$, and so the power series (27) diverges at $z=1$. Therefore $R_{x}\leq 1$ for all $x\in\Omega$.

We shall use Lemma 7 to get a lower bound on $R_{x}$ that holds for almost all $x\in\Omega$. Let $A=\{x\in\Omega:R_{x}<1\}$, let $A_{m}=\{x\in\Omega:R_{x}<1-\frac{1}{m}\}$, and let $B_{m}$ be those $x\in\Omega$ such that $\left\|nx\right\|^{1/n}<1-\frac{1}{m}$ infinitely often. If $x\in A_{m}$, then $R_{x}=\liminf_{n\to\infty}\left\|nx\right\|^{1/n}<1-\frac{1}{m}$, and this implies that there are infinitely many $n$ such that $\left\|nx\right\|^{1/n}<1-\frac{1}{m}$, so $x\in B_{m}$, i.e. $A_{m}\subset B_{m}$. But let $f_{m}(n)=\left(1-\frac{1}{m}\right)^{n}$. Then $\sum_{n=1}^{\infty}f_{m}(n)$ converges, since $1-\frac{1}{m}<1$, so, by Lemma 7, for almost all $x\in\Omega$ there are only finitely many $n$ such that $\left\|nx\right\|. Thus $\mu(B_{m})=0$. Hence $\mu(A_{m})=0$, and since $A=\bigcup_{m=2}^{\infty}A_{m}$ we get that

 $\mu(A)\leq\sum_{m=2}^{\infty}\mu(A_{m})=0,$

that is, $R_{x}\geq 1$ for almost all $x\in\Omega$. In conclusion, $R_{x}=1$ for almost all $x\in\Omega$. ∎

In fact, we can prove the above theorem using the bounds we obtained in Theorem 11. By Theorem 11, for almost all $x\in\Omega$ we have that $\sum_{j=1}^{m}\frac{1}{\left\|jx\right\|}=O(m^{2})$. (Here we will merely need the fact that the sum is subexponential in $m$.) For such an $x$, take $0. Let $a_{n}=r^{n}$, let $s_{n}=\sum_{j=1}^{n}\frac{1}{\left\|jx\right\|}$, let $b_{1}=0$, and let $b_{n}=s_{n-1}$ for $n\geq 2$. Using summation by parts, namely

 $\sum_{n=1}^{N}a_{n}(b_{n+1}-b_{n})=a_{N+1}b_{N+1}-a_{1}b_{1}-\sum_{n=1}^{N}b_{% n+1}(a_{n+1}-a_{n}),$

we get

 $\sum_{n=1}^{N}\frac{r^{n}}{\left\|nx\right\|}=r^{N+1}s_{N}+\sum_{n=1}^{N}s_{n}% r^{n}(1-r).$

Therefore

 $\sum_{n=1}^{N}\frac{r^{n}}{\left\|nx\right\|}=O\left(r^{N+1}N^{2}\right)+O% \left(\sum_{n=1}^{N}n^{2}r^{n}\right)=O(1).$

Since $\sum_{n=1}^{N}\frac{r^{n}}{\left\|nx\right\|}$ is increasing in $N$ (being a sum of positive terms), we obtain that the series $\sum_{n=1}^{\infty}\frac{r^{n}}{\left\|nx\right\|}$ converges. Since this is true for all $r$ with $0, it follows that $R_{x}\geq 1$.

For $x\in\Omega$ let $R_{x}$ be the radius of convergence of the power series $\sum_{q=1}^{\infty}\frac{z^{q}}{\left\|qx\right\|}$. We proved in Theorem 27 that for almost all $x\in\Omega$, $R_{x}=1$.

###### Theorem 25.

For $x\in\Omega$, let $R_{x}$ be the radius of convergence of the power series $\sum_{q=1}^{\infty}\frac{z^{q}}{\left\|qx\right\|}$, and let $a_{n}=a_{n}(x)$ and $q_{n}=q_{n}(x)$. Then

 $R_{x}=\liminf_{n\to\infty}a_{n+1}^{-1/q_{n}}.$

For any $0\leq R\leq 1$ there is some $x\in\Omega$ such that $R_{x}=R$.

###### Proof.

 $R_{x}=\liminf_{q\to\infty}\left\|qx\right\|^{1/q}.$

Then $R_{x}\leq\liminf_{n\to\infty}\left\|q_{n}x\right\|^{1/q_{n}}$. On the one hand, by (11), $\left\|q_{n}x\right\|, and $q_{n+1}=a_{n+1}q_{n}+q_{n-1}>a_{n+1}q_{n}$ hence $\left\|q_{n}x\right\|, and using that $\lim_{n\to\infty}q_{n}^{-1/q_{n}}=1$,

 $R_{x}\leq\liminf_{n\to\infty}a_{n+1}^{-1/q_{n}}q_{n}^{-1/q_{n}}=\liminf_{n\to% \infty}a_{n+1}^{-1/q_{n}}.$

On the other hand, let $q\geq 2$ and take $q_{n}\leq q. Applying (12),

 $\left\|q_{n}x\right\|>\frac{1}{q_{n+1}+q_{n}}>\frac{1}{2q_{n+1}}=\frac{1}{2(a_% {n+1}q_{n}+q_{n-1})}>\frac{1}{4a_{n+1}q_{n}}.$

Then applying Theorem 2, and using that $0<\left\|q_{n}x\right\|<1$ and $q\geq q_{n}$,

 $\left\|qx\right\|^{1/q}\geq\left\|q_{n}x\right\|^{1/q}\geq\left\|q_{n}x\right% \|^{1/q_{n}}>\left(\frac{1}{4a_{n+1}q_{n}}\right)^{1/q_{n}}.$

As $(4q_{n})^{-1/q_{n}}\to 1$ as $n\to\infty$, this implies

 $R_{x}=\liminf_{q\to\infty}\left\|qx\right\|^{1/q}\geq\liminf_{n\to\infty}a_{n+% 1}^{-1/q_{n}}.$

For $0, let $R=e^{-r}$ for $r>0$. Define $a\in\mathbb{N}^{\mathbb{N}}$ as follows. Define $a_{1}=1$. Suppose for $n\geq 1$ that we have defined $a_{1},\ldots,a_{n}$ and thus $p_{1},\ldots,p_{n}$ and $q_{1},\ldots,q_{n}$. Define $a_{n+1}=[e^{rq_{n}}]$. Then $a_{n+1}^{1/q_{n}}\leq e^{r}$, so $a_{n+1}^{-1/q_{n}}\geq e^{-r}$. Therefore for $x=v(a)$, $R_{x}\geq e^{-r}$. Now, $e^{rq_{n}}>1$ so $a_{n+1}=[e^{rq_{n}}]\geq 2^{-1}e^{rq_{n}}$. Then $a_{n+1}^{1/q_{n}}\geq 2^{-1/q_{n}}e^{r}$, hence

 $R_{x}=\liminf_{n\to\infty}a_{n+1}^{-1/q_{n}}\leq\liminf_{n\to\infty}2^{1/q_{n}% }e^{-r}=e^{-r}.$

We have therefore established that when $x=v(a)$, $R_{x}=e^{-r}$.

For $R=0$, define $a\in\mathbb{N}^{\mathbb{N}}$ by $a_{1}=1$ and $a_{n+1}=[e^{nq_{n}}]$, which satisfies $a_{n+1}\geq 2^{-1}e^{nq_{n}}$. For $x=v(a)$,

 $R_{x}=\liminf_{n\to\infty}a_{n+1}^{-1/q_{n}}\leq\liminf_{n\to\infty}2^{1/q_{n}% }e^{-n}=0.$

For $R=1$, define $a\in\mathbb{N}^{\mathbb{N}}$ by $a_{n}=1$ for all $n\geq 1$. Namely, $v(a)=\frac{-1+\sqrt{5}}{2}\in\Omega$. For $x=v(a)$ it is immediate that $R_{x}\geq 1$. ∎

Since $R(nx)<1$, of course the power series $\sum_{n=1}^{\infty}R(nx)z^{n}$ has radius of convergence $\geq 1$. The following result, for which Pólya and Szegő [117, p. 280, Part II, No. 168] cite Hecke, shows in particular that the radius of convergence of this power series is $\leq 1$ for $x\in\Omega$ and is thus equal to $1$.

###### Theorem 26.

For $x\in\Omega$, let

 $f(z)=\sum_{n=1}^{\infty}R(nx)z^{n},\qquad|z|<1.$

We have

 $\lim_{r\to 1^{-}}(1-r)f(re^{2\pi ix})=\frac{1}{2\pi i}.$
###### Proof.

Since $x\in\Omega$, the sequence $nx$ is uniformly distributed modulo $1$. Therefore, with $f(t)=te^{2\pi it}$ we have by (18) that

 $\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^{N}R(nx)e^{2\pi inx}=\lim_{N\to\infty}% \frac{1}{N}\sum_{n=1}^{N}f(R(nx))=\int_{0}^{1}te^{2\pi it}dt=\frac{1}{2\pi i}.$

We will use the following result [117, p. 21, Part I, No. 88]. If a sequence of complex numbers $a_{n}$ satisfies $\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^{N}a_{n}=s$, then

 $\lim_{t\to 1^{-}}(1-t)\sum_{n=1}^{\infty}a_{n}t^{n}=s.$

Let $a_{n}=R(nx)e^{2\pi inx}$, and we thus have

 $\lim_{t\to 1^{-}}(1-t)\sum_{n=1}^{\infty}R(nx)e^{2\pi inx}t^{n}=\frac{1}{2\pi i}.$

It follows from the above theorem that if $x\in\Omega$ then $|z|=1$ is a natural boundary of the function $f$ defined on the open unit disc by $f(z)=\sum_{n=1}^{\infty}R(nx)z^{n}$; cf. Segal [133, p. 255, Chapter 6], who writes about this power series, and who gives a thorough introduction to natural boundaries in the same chapter. Breur and Simon  prove a generalization of this result.

Hata [62, p. 173, Problem 12.6] mentions the appearance of the function $f$ from the above theorem in the study of the Caianiello neuron equations.

## 11 Product

We will use the following lemma proved by Hardy and Littlewood [58, p. 89], whose brief proof we expand.

###### Lemma 27.

Let $\psi:(0,\infty)\to\mathbb{R}$ be positive and nondecreasing. If

 $\sum_{k=1}^{\infty}\frac{1}{k\psi(k)}<\infty,$

then for almost all $x\in\Omega$, there exists some $H$ such that for all $n\geq 1$ and for all real $h\geq H$, there are at most $\max\{\frac{n\psi(h)}{h},1\}$ integers $m\in\{1,\ldots,n\}$ that satisfy $\left\|mx\right\|<\frac{1}{h}$.

###### Proof.

By Lemma 7, for almost all $x\in\Omega$ there is some $K$ such that if $k\geq K$ then

 $\left\|kx\right\|\geq\frac{2}{k\psi(k)}.$ (28)

Let $H$ be large enough so that

 $\min_{k

also let $\psi(H)\geq 1$. Now suppose by contradiction that there is some $n\geq 1$ and some $h\geq H$ such that there are more than $\max\{\frac{n\psi(h)}{h},1\}$ integers $m\in\{1,\ldots,n\}$ that satisfy $\left\|mx\right\|<\frac{1}{h}$. Then there are some $1\leq m_{1} satisfying $\left\|m_{1}x\right\|<\frac{1}{h}$ and $\left\|m_{2}x\right\|<\frac{1}{h}$ and such that

 $\mu=m_{2}-m_{1}<\frac{n}{\frac{n\psi(h)}{h}}=\frac{h}{\psi(h)},$

so $\mu\psi(h). On the other hand,

 $\left\|\mu x\right\|\leq\left\|m_{1}x\right\|+\left\|m_{2}x\right\|<\frac{1}{h% }+\frac{1}{h}=\frac{2}{h},$

so $h<\frac{2}{\left\|\mu x\right\|}$. Thus $\mu\psi(h)<\frac{2}{\left\|\mu x\right\|}$, i.e.,

 $\left\|\mu x\right\|<\frac{2}{\mu\psi(h)}\leq\frac{2}{\mu\psi(\mu)};$

$\mu because $\mu<\frac{h}{\psi(h)}$ and $\psi(h)\geq\psi(H)\geq 1$. Moreover, since $\left\|\mu x\right\|<\frac{2}{h}\leq\frac{2}{H}$, we have $\mu\geq K$. This contradicts (28). ∎

Hardy and Littlewood [58, p. 89, Theorem 4] prove the following theorem that gives us the conclusion (18) for certain functions that are not Riemann integrable on $[0,1]$.

###### Theorem 28.

Let $f:(0,1)\to\mathbb{R}$ be nonnegative, let $f$ be nonincreasing on $(0,\frac{1}{2})$ and nondecreasing on $(\frac{1}{2},1)$, and let

 $\int_{0}^{1}f(t)dt<\infty.$

Let $\psi:(1,\infty)\to\mathbb{R}$ be a positive and nondecreasing function such that

 $\sum_{k=2}^{\infty}\frac{1}{k\psi(k)}<\infty.$

If

 $\int_{0}^{1}f(t)\left(\psi\left(\frac{1}{t}\right)+\psi\left(\frac{1}{1-t}% \right)\right)dt<\infty,$

then for almost all $x\in\Omega$,

 $\lim_{n\to\infty}\frac{1}{n}\sum_{m=1}^{n}f(R(mx))=\int_{0}^{1}f(t)dt.$
###### Proof.

For $0<\delta<\frac{1}{2}$, define

 $f_{\delta}(t)=\begin{cases}f(t),&\delta\leq t\leq 1-\delta,\\ 0,&0

From Lemma 27, for almost all $x\in\Omega$ there is some $C$ such that for all $n$ and $h$ there are at most $C\frac{n\psi(h)}{h}$ integers $m\in\{1,\ldots,n\}$ satisfying $\left\|mx\right\|<\frac{1}{h}$. Let

 $S_{n}=\frac{1}{n}\sum_{m=1}^{n}f(R(mx))=S_{n}^{1}(\delta)+S_{n}^{2}(\delta),$

where

 $S_{n}^{1}(\delta)=\frac{1}{n}\sum_{m=1}^{n}f_{\delta}(R(mx))$

and

 $\displaystyle S_{n}^{2}(\delta)$ $\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{m=1}^{n}f(R(mx))-f_{\delta}(R(mx))$ $\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{\stackrel{{1\leq m\leq n}}{{\left\|% mx\right\|<\delta}}}f(R(mx))$ $\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{k=0}^{\infty}\sum_{\stackrel{{1\leq m% \leq n}}{{\frac{\delta}{2^{k+1}}\leq\left\|mx\right\|<\frac{\delta}{2^{k}}}}}f% (R(mx))$ $\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{k=0}^{\infty}T_{k,n}(\delta).$

There are at most $C\frac{n\psi\left(\frac{2^{k}}{\delta}\right)}{\frac{2^{k}}{\delta}}$ integers $m\in\{1,\ldots,n\}$ that satisfy $\left\|mx\right\|<\frac{\delta}{2^{k}}$, thus, as $\psi$ is nondecreasing, there are at most $2C\frac{n\delta\psi\left(\frac{2^{k}}{\delta}\right)}{2^{k+1}}\leq 2C\frac{n% \delta\psi\left(\frac{2^{k+1}}{\delta}\right)}{2^{k+1}}$ terms in $T_{k,n}(\delta)$. For each term $f(R(mx))$ in $T_{k,n}(\delta)$, since $\frac{\delta}{2^{k+1}}\leq\left\|mx\right\|$ we have, by assumption on $f$, either $f(R(mx))\leq f\left(\frac{\delta}{2^{k+1}}\right)$ or $f(R(mx))\leq f\left(1-\frac{\delta}{2^{k+1}}\right)$, and hence

 $f(R(mx))\leq f\left(\frac{\delta}{2^{k+1}}\right)+f\left(1-\frac{\delta}{2^{k+% 1}}\right).$

Therefore,

 $\displaystyle S_{n}^{2}(\delta)$ $\displaystyle\leq$ $\displaystyle\frac{1}{n}\sum_{k=0}^{\infty}2C\frac{n\delta\psi\left(\frac{2^{k% +1}}{\delta}\right)}{2^{k+1}}\left(f\left(\frac{\delta}{2^{k+1}}\right)+f\left% (1-\frac{\delta}{2^{k+1}}\right)\right)$ $\displaystyle=$ $\displaystyle 4C\sum_{k=0}^{\infty}\frac{\delta}{2^{k+2}}\psi\left(\frac{2^{k+% 1}}{\delta}\right)f\left(\frac{\delta}{2^{k+1}}\right)+4C\sum_{k=0}^{\infty}% \frac{\delta}{2^{k+2}}\psi\left(\frac{2^{k+1}}{\delta}\right)f\left(1-\frac{% \delta}{2^{k+1}}\right)$ $\displaystyle\leq$ $\displaystyle 4C\int_{0}^{\frac{\delta}{2}}\psi\left(\frac{1}{t}\right)f(t)dt+% 4C\int_{1-\frac{\delta}{2}}^{1}\psi\left(\frac{1}{1-t}\right)f(t)dt.$

Let $\epsilon>0$. Because $\int_{0}^{1}f(t)\left(\psi\left(\frac{1}{t}\right)+\psi\left(\frac{1}{1-t}% \right)\right)dt<\infty$, there exists a $\delta_{1}$ such that if $\delta\leq\delta_{1}$ then $S_{n}^{2}(\delta)<\epsilon$.

On the other hand, since $f_{\delta}$ is Riemann integrable on $[0,1]$ and because, by (19), the sequence $mx$ is uniformly distributed modulo $1$, we obtain from (18) that

 $\lim_{n\to\infty}S_{n}^{1}(\delta)=\int_{0}^{1}f_{\delta}(t)dt=\int_{\delta}^{% 1-\delta}f(t)dt.$

As $\int_{0}^{1}f(t)dt<\infty$, there exists a $\delta_{2}$ such that for $\delta\leq\delta_{2}$ and for sufficiently large $n$,

 $\left|S_{n}^{1}(\delta)-\int_{0}^{1}f(t)dt\right|\leq\left|S_{n}^{1}(\delta)-% \int_{\delta}^{1-\delta}f(t)dt\right|+\left|\int_{0}^{\delta}f(t)dt\right|+% \left|\int_{1-\delta}^{1}f(t)dt\right|<3\epsilon.$

Therefore, for sufficiently large $n$ and for sufficiently small $\delta$,

 $\left|S_{n}-\int_{0}^{1}f(t)dt\right|\leq\left|S_{n}^{1}(\delta)-\int_{0}^{1}f% (t)dt\right|+\left|S_{n}^{2}(\delta)\right|<4\epsilon.$

Thus for sufficiently large $n$,

 $\left|S_{n}-\int_{0}^{1}f(t)dt\right|\leq 4\epsilon.$

By the Birkhoff ergodic theorem [44, p. 44, Theorem 2.30], if $f\in L^{1}[0,1]$ and $x\in\Omega$, then for almost all $\alpha\in[0,1]$,

 $\lim_{n\to\infty}\frac{1}{n}\sum_{j=1}^{n}f(R(\alpha+jx))=\int_{0}^{1}f(t)dt.$

This equality holding for $\alpha=0$ is the conclusion of Theorem 28.

Baxa  reviews further results that give conditions when a function $f:[0,1]\to\mathbb{R}\cup\{+\infty\}$ that is not Riemann integrable on $[0,1]$ nevertheless satisfies

 $\lim_{n\to\infty}\frac{1}{n}\sum_{m=1}^{n}f(R(mx))=\int_{0}^{1}f(t)dt$

for certain $x\in\Omega$. Oskolkov [109, p. 170, Theorem 1] shows that if $f:(0,1)\to\mathbb{R}$ satisfies $\lim_{t\to 0+}f(t)=+\infty$ and $\lim_{t\to 1-}f(t)=+\infty$, and also the improper Riemann integral of $f$ on $[0,1]$ exists, then, for $x\in\Omega$,

 $\lim_{n\to\infty}\frac{1}{n}\sum_{m=1}^{n}f(R(mx))=\int_{0}^{1}f(t)dt$

if and only if

 $\lim_{n\to\infty}\frac{1}{q_{n}(x)}f(R(q_{n}(x)x))=0,$

where $q_{n}(x)$ is the denominator of the $n$th convergent of the continued fraction expansion of $x$.

Driver, Lubinsky, Petruska and Sarnak 

Using Theorem 28 we can now prove the following theorem of Hardy and Littlewood [58, p. 88, Theorem 2].

###### Theorem 29.

For almost all $x\in\Omega$,

 $\lim_{n\to\infty}\left(\prod_{k=1}^{n}|\sin k\pi x|\right)^{1/n}=\frac{1}{2}.$
###### Proof.

Let $f(t)=-\log\sin\pi t$. Using $\cos(t-\frac{\pi}{2})=\sin t$ and $\sin 2t=2\sin t\cos t$, one can check that $\int_{0}^{1}\log\sin\pi tdt=-\log 2$. (The earliest evaluation of this integral of which we are aware is by Euler , who gives two derivations, the first using the Euler-Maclaurin summation formula, the power series expansion for $\log\left(\frac{1+z}{1-z}\right)$, and the power series expansion of $z\cot(z)$, and the second using the Fourier series of $\log|\sin t|$.) Thus, $\int_{0}^{1}f(t)dt=\log 2<\infty$. So $f$ satisfies the conditions of Theorem 28.

Let $\psi(t)=(\log t)^{2}$. First, upper bounding the series by an integral,

 $\sum_{k=2}^{\infty}\frac{1}{k(\log k)^{2}}\leq\frac{1}{2(\log 2)^{2}}+\int_{2}% ^{\infty}\frac{1}{t(\log t)^{2}}dt=\frac{1}{2(\log 2)^{2}}+\log 2<\infty.$

Second,

 $\displaystyle\int_{0}^{1}f(t)\left(\psi\left(\frac{1}{t}\right)+\psi\left(% \frac{1}{1-t}\right)\right)dt$ $\displaystyle=$ $\displaystyle\int_{0}^{1}f(t)\left(\psi(t)+\psi(1-t)\right)dt$ $\displaystyle=$ $\displaystyle\int_{0}^{\frac{1}{2}}-2\log\sin(\pi t)$ $\displaystyle\left((\log t)^{2}+(\log(1-t))^{2}\right)dt$ $\displaystyle\leq$ $\displaystyle\int_{0}^{\frac{1}{2}}-2\log(2t)\left((\log t)^{2}+(\log(1-t))^{2% }\right)dt$ $\displaystyle<$ $\displaystyle\infty.$

Therefore by Theorem 28, for almost all $x\in\Omega$,

 $\lim_{n\to\infty}\frac{1}{n}\sum_{m=1}^{n}-\log\sin(\pi R(mx))=\int_{0}^{1}-% \log\sin\pi tdt,$

i.e.

 $\lim_{n\to\infty}\frac{1}{n}\sum_{m=1}^{n}\log|\sin\pi mx|=\log\frac{1}{2}.$

Hardy and Littlewood give another proof [58, p. 86, Theorem 1] of the above theorem, which we now work out. This proof is complicated and we greatly expand on the abbreviated presentation of Hardy and Littlewood.

We remind ourselves that the Cauchy-Hadamard formula states that the radius of convergence $R$ of a power series $\sum a_{n}z^{n}$ satisfies

 $R=\frac{1}{\limsup_{n\to\infty}|a_{n}|^{1/n}}=\liminf_{n\to\infty}|a_{n}|^{-1/% n}.$
###### Theorem 30.

Fix $x\in\Omega$ and write $q_{0}=e^{2\pi ix}$. Let $\rho$ and $R$ respectively be the radii of convergence of the power series

 $f(z)=\sum_{n=1}^{\infty}\frac{z^{n}}{n(1-q_{0}^{n})},\qquad F(z)=1+\sum_{n=1}^% {\infty}\frac{z^{n}}{(1-q_{0})(1-q_{0}^{2})\cdots(1-q_{0}^{n})}.$

Then $R=\rho$, and if $|z|<\rho$ then $F(z)=e^{f(z)}$.

The functions $f:D(0,\rho)\to\mathbb{C}$ and $F:D(0,R)\to\mathbb{C}$ are analytic [143, p. 69, Theorem 2.16].

Using the Cauchy-Hadamard formula we have

 $\rho=\liminf_{n\to\infty}n^{1/n}|1-q_{0}^{n}|^{1/n}\leq\liminf_{n\to\infty}(2n% )^{1/n}=1$

and

 $R=\liminf_{n\to\infty}(|1-q_{0}||1-q_{0}^{2}|\cdots|1-q_{0}^{n}|)^{1/n}\leq 2\rho.$ (29)
###### Lemma 31.

For $|u|=1$ and for $0\leq r<1$,

 $\left|\frac{1-u}{1-ru}\right|\leq 2.$
###### Proof.
 $|1-u|\leq|1-ru|+|ru-u|=|1-ru|+1-r.$

Because $\mathrm{Re}\,u\leq 1$ we have $1-r\leq 1-r\mathrm{Re}\,u=\mathrm{Re}\,(1-ru)\leq|1-ru|$. Hence $|1-u|\leq 2|1-ru|$, from which the claim follows. ∎

We assert the following as a common fact in complex analysis.

###### Lemma 32.

For $|w|<1$ define

 $L(w)=\sum_{n=1}^{\infty}\frac{w^{n}}{n}.$

If $|w|<1$, then $e^{L(w)}=(1-w)^{-1}$.

For $|q|,|z|<1$, we define

 $f(z,q)=\sum_{n=1}^{\infty}\frac{z^{n}}{n(1-q^{n})},\qquad F(z,q)=1+\sum_{n=1}^% {\infty}\frac{z^{n}}{(1-q)(1-q^{2})\cdots(1-q^{n})}.$

For $|q|<1$, define $c_{0}(q)=0$ and for $n\geq 1$,

 $c_{n}(q)=\frac{1}{n(1-q^{n})},$

and thus for $|z|<1$,

 $f(z,q)=\sum_{n=0}^{\infty}c_{n}(q)z^{n}.$

Furthermore define $\gamma_{0}=0$ and for $n\geq 1$,

 $\gamma_{n}=\frac{1}{n(1-q_{0}^{n})},$

and thus for $|z|<\rho$,

 $f(z)=\sum_{n=0}^{\infty}\gamma_{n}z^{n}.$

For $|q|<1$, define $C_{0}(q)=1$ and for $n\geq 1$,

 $C_{n}(q)=\frac{1}{(1-q)(1-q^{2})\cdots(1-q^{n})},$

and thus for $|z|<1$,

 $F(z,q)=\sum_{n=0}^{\infty}C_{n}(q)z^{n}.$

Furthermore define $\Gamma_{0}=1$ and for $n\geq 1$,

 $\Gamma_{n}=\frac{1}{(1-q_{0})(1-q_{0}^{2})\cdots(1-q_{0}^{n})},$

and thus for $|z|,

 $F(z)=\sum_{n=0}^{\infty}\Gamma_{n}z^{n}.$

We prove directly the following, which is an instance of the $q$-binomial formula [3, p. 17, Theorem 2.1].

###### Proposition 33.

If $|q|,|z|<1$ then

 $F(z,q)=e^{f(z,q)}.$
###### Proof.

By Lemma 32,

 $f(z,q)=\sum_{n=1}^{\infty}\frac{z^{n}}{n}\left(\sum_{m=0}^{\infty}q^{nm}\right% )=\sum_{m=0}^{\infty}\left(\sum_{n=1}^{\infty}\frac{(zq^{m})^{n}}{n}\right)=% \sum_{m=0}^{\infty}L(zq^{m}).$

Because $e^{L(w)}=(1-w)^{-1}$ for $|w|<1$,

 $e^{f(z,q)}=\prod_{m=0}^{\infty}e^{L(zq^{m})}=\prod_{m=0}^{\infty}(1-zq^{m})^{-% 1}.$

Define

 $G(z,q)=\prod_{m=0}^{\infty}(1-zq^{m})^{-1}=\sum_{n=0}^{\infty}g_{n}(q)z^{n}.$

On the one hand, $g_{0}(q)=G(0,q)=1$. On the other hand,

 $G(qz,q)=(1-z)G(z,q),$

thus

 $\sum_{n=0}^{\infty}g_{n}(q)z^{n+1}=\sum_{n=0}^{\infty}g_{n}(q)(1-q^{n})z^{n},$

and therefore for $n\geq 1$ we have $g_{n}(q)=(1-q^{n})^{-1}g_{n-1}(q)$. Thus by induction, for $n\geq 1$,

 $g_{n}(q)=\frac{1}{(1-q)(1-q^{2})\cdots(1-q^{n})}.$

Hence

 $e^{f(z,q)}=1+\sum_{n=1}^{\infty}\frac{z^{n}}{(1-q)(1-q^{2})\cdots(1-q^{n})}=F(% z,q).$

###### Proposition 34.

$R\geq\rho$, and if $|z|<\rho$ then $e^{f(z)}=F(z)$.

###### Proof.

If $\rho=0$ then the claim is immediate. Otherwise, $0<\rho\leq 1$. Let $0, $0, and define $G(\theta)=F(te^{i\theta},rq_{0})$. On the one hand,

 $G(\theta)=\sum_{n=0}^{\infty}C_{n}(rq_{0})(te^{i\theta})^{n}=\sum_{n=0}^{% \infty}C_{n}(rq_{0})t^{n}e^{in\theta},$

which implies that $\widehat{G}(n)=C_{n}(rq_{0})t^{n}$ for $n\geq 0$ and $\widehat{G}(n)=0$ for $n<0$. On the other hand, for $n\in\mathbb{Z}$, using Proposition 33,

 $\displaystyle\widehat{G}(n)$ $\displaystyle=\frac{1}{2\pi}\int_{0}^{2\pi}G(\theta)e^{-in\theta}d\theta$ $\displaystyle=\frac{1}{2\pi}\int_{0}^{2\pi}F(te^{i\theta},rq_{0})e^{-in\theta}d\theta$