# Vinogradov’s estimate for exponential sums over primes

Jordan Bell
February 23, 2016

## 1 Introduction

For $x\in\mathbb{R}$, let $[x]$ be the greatest integer $\leq x$, let $R(x)=x-[x]$, and let

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

In this note I work through Chapters 24 and 25 of Harold Davenport, Multiplicative Number Theory, third ed.11 1 Many of the manipulations of sums in these chapters are hard to follow, and I greatly expand on the calculations in Davenport. The organization of the proof in Davenport seems to be due to Vaughan. I have also used lecture notes by Andreas Strömbergsson, http://www2.math.uu.se/~astrombe/analtalt08/www_notes.pdf, pp. 245–257. Another set of notes, which I have not used, are http://jonismathnotes.blogspot.ca/2014/11/prime-exponential-sums-and-vaughans.html

We end up proving that there is some constant $C$ such that if $\alpha\in\mathbb{R}$ and $\left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q^{2}}$, with $a$ positive and $\gcd(a,q)=1$, then for any $N\geq 2$,

## 2 The von Mangoldt function

Let $\Lambda$ be the von Mangoldt function: $\Lambda(n)=\log p$ if $n=p^{\alpha}$ for some prime $p$ and $\alpha\geq 1$, and $\Lambda(n)=0$ otherwise. For example, $\Lambda(4)=\log 2$, $\Lambda(11)=\log 11$, and $\Lambda(12)=0$. This satisfies

 $\log n=\sum_{d\mid n}\Lambda(d),$

and so by the Möbius inversion formula,

 $\Lambda(n)=\sum_{d\mid n}\mu(n/d)\log d.$

For $n>1$ it is a fact that22 2 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, fifth ed., p. 235, Theorem 263.

 $\sum_{d\mid n}\mu(d)=0.$

Write $\psi(x)=\sum_{n\leq x}\Lambda(n)$. It is a fact that $\psi(x)=O(x)$.33 3 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, fifth ed., p. 341, Theorem 414. (The prime number theorem states $\psi(x)\sim x$.)

The derivative of the Riemann zeta function is

 $\zeta^{\prime}(s)=-\sum_{n=1}^{\infty}n^{-s}\log n,\qquad\mathrm{Re}\,s>1.$

The Euler product for the Riemann zeta function is

 $\zeta(s)=\sum_{m=1}^{\infty}m^{-s}=\prod_{p}(1-p^{-s})^{-1},\qquad\mathrm{Re}% \,s>1.$

Then

 $-\log\zeta(s)=\sum_{p}\log(1-p^{-s}),$

so, for $\mathrm{Re}\,s>1$,

 $\displaystyle-\frac{\zeta^{\prime}(s)}{\zeta(s)}$ $\displaystyle=\sum_{p}\frac{p^{-s}\log p}{1-p^{-s}}$ $\displaystyle=\sum_{p}\log p\sum_{l=1}^{\infty}p^{-ls}$ $\displaystyle=\sum_{p}\sum_{l=1}^{\infty}\Lambda(p^{l})(p^{l})^{-s}$ $\displaystyle=\sum_{n=1}^{\infty}\Lambda(n)n^{-s}.$

Let $U,V\geq 2$, $UV\leq N$, and write

 $F_{U}(s)=\sum_{j\leq U}\Lambda(j)j^{-s},\qquad G_{V}(s)=\sum_{k\leq V}\mu(k)k^% {-s}.$

For $\mathrm{Re}\,s>1$,

 $\begin{split}&\displaystyle-\frac{\zeta^{\prime}(s)}{\zeta(s)}\\ \displaystyle=&\displaystyle F_{U}(s)-\zeta(s)F_{U}(s)G_{V}(s)-\zeta^{\prime}(% s)G_{V}(s)+\left(-\frac{\zeta^{\prime}(s)}{\zeta(s)}-F_{U}(s)\right)(1-\zeta(s% )G_{V}(s)).\end{split}$

First,44 4 Harold Davenport, Multiplicative Number Theory, third ed., p. 138, Chapter 24.

 $F_{U}(s)=\sum_{n=1}^{\infty}a_{1}(n)n^{-s}$

for

 $a_{1}(n)=\begin{cases}\Lambda(n)&n\leq U\\ a_{1}(n)=0&n>U.\end{cases}$

Second,

 $-\zeta(s)F_{U}(s)G_{V}(s)=\sum_{n=1}^{\infty}a_{2}(n)n^{-s}$

for

 $a_{2}(n)=-\sum_{mjk=n,m\geq 1,j\leq U,k\leq V}1\cdot\Lambda(j)\cdot\mu(k)=-% \sum_{d\mid n}\sum_{djk=n,j\leq U,k\leq V}\Lambda(j)\mu(k).$

Third,

 $-\zeta^{\prime}(s)G_{V}(s)=\sum_{n=1}^{\infty}a_{3}(n)n^{-s}$

for

 $a_{3}(n)=\sum_{mk=n,m\geq 1,k\leq V}\log(m)\cdot\mu(k)=\sum_{d\mid n}\log d% \sum_{dk=n,k\leq V}\mu(k).$

Fourth,

 $-\frac{\zeta^{\prime}(s)}{\zeta(s)}-F_{U}(s)=\sum_{m>U}\Lambda(m)m^{-s};$

and

 $\zeta(s)G_{V}(s)=\sum_{n=1}^{\infty}\left(\sum_{mk=n,m\geq 1,k\leq V}1\cdot\mu% (k)\right)n^{-s}=\sum_{n=1}^{\infty}\left(\sum_{d\mid n,d\leq V}\mu(d)\right)n% ^{-s}$

whence

 $1-\zeta(s)G_{V}(s)=-\sum_{h=2}^{\infty}\left(\sum_{d\mid h,d\leq V}\mu(d)% \right)h^{-s};$

thus

 $\left(-\frac{\zeta^{\prime}(s)}{\zeta(s)}-F_{U}(s)\right)(1-\zeta(s)G_{V}(s))=% \sum_{n=1}^{\infty}a_{4}(n)n^{-s}$

for

 $a_{4}(n)=-\sum_{mh=n,m>U,h>1}\Lambda(m)\left(\sum_{d\mid h,d\leq V}\mu(d)% \right).$

We have

 $\Lambda(n)=a_{1}(n)+a_{2}(n)+a_{3}(n)+a_{4}(n).$

## 3 Sums involving the von Mangoldt function

Let $f$ be an arithmetical function with $|f|\leq 1$ and write

 $S_{i}=\sum_{n\leq N}f(n)a_{i}(n),$

for which

 $\sum_{n\leq N}f(n)\Lambda(n)=S_{1}+S_{2}+S_{3}+S_{4}.$
 $\displaystyle S_{1}$ $\displaystyle=\sum_{n\leq U}f(n)\Lambda(n)$ $\displaystyle S_{2}$ $\displaystyle=-\sum_{n\leq N}f(n)\sum_{d\mid n}\sum_{djk=n,j\leq U,k\leq V}% \Lambda(j)\mu(k)$ $\displaystyle S_{3}$ $\displaystyle=\sum_{n\leq N}f(n)\sum_{d\mid n}\log d\sum_{dk=n,k\leq V}\mu(k)$ $\displaystyle S_{4}$ $\displaystyle=-\sum_{n\leq N}f(n)\sum_{mh=n,m>U,h>1}\Lambda(m)\sum_{d\mid h,d% \leq V}\mu(d).$
###### Lemma 1.

$|S_{1}|=O(U)$.

###### Proof.

As $|f|\leq 1$,

 $|S_{1}|\leq\sum_{n\leq U}\Lambda(n)=\psi(U)=O(U).$

###### Lemma 2.
 $|S_{2}|\leq\log UV\cdot\sum_{h\leq UV}\left|\sum_{r\leq N/h}f(rh)\right|.$
###### Proof.
 $\displaystyle S_{2}$ $\displaystyle=-\sum_{n\leq N}f(n)\sum_{d\mid n}\sum_{djk=n,j\leq U,k\leq V}% \Lambda(j)\mu(k)$ $\displaystyle=-\sum_{h\leq UV}\left(\sum_{jk=h,j\leq U,k\leq V}\Lambda(j)\mu(k% )\right)\sum_{r\leq N/h}f(rh).$

For $h\leq UV$, $\sum_{j\mid h}\Lambda(j)=\log h\leq\log UV$, so

 $|S_{2}|\leq\log UV\cdot\sum_{h\leq UV}\left|\sum_{r\leq N/h}f(rh)\right|.$

###### Lemma 3.
 $|S_{3}|\leq\log N\cdot\sum_{k\leq V}\max_{1\leq w\leq N/k}\left|\sum_{w\leq h% \leq N/k}f(kh)\right|.$
###### Proof.
 $\displaystyle S_{3}$ $\displaystyle=\sum_{n\leq N}f(n)\sum_{d\mid n}\log d\sum_{dk=n,k\leq V}\mu(k)$ $\displaystyle=\sum_{k\leq V}\mu(k)\sum_{h\leq N/k}f(kh)\log h$ $\displaystyle=\sum_{k\leq V}\mu(k)\sum_{h\leq N/k}f(kh)\int_{1}^{h}\frac{dw}{w}$ $\displaystyle=\sum_{k\leq V}\mu(k)\int_{1}^{N/k}\sum_{w\leq h\leq N/k}f(kh)% \frac{dw}{w}$ $\displaystyle=\int_{1}^{N}\sum_{k\leq V}\mu(k)\sum_{w\leq h\leq N/k}f(kh)\frac% {dw}{w}.$

Then

 $\displaystyle|S_{3}|$ $\displaystyle\leq\max_{1\leq w\leq N}\left|\sum_{k\leq V}\mu(k)\sum_{w\leq h% \leq N/k}f(kh)\right|\cdot\int_{1}^{N}\frac{dw}{w}$ $\displaystyle\leq\log N\cdot\sum_{k\leq V}\max_{1\leq w\leq N/k}\left|\sum_{w% \leq h\leq N/k}f(kh)\right|.$

###### Lemma 4.
 $|S_{4}|\ll N^{1/2}(\log N)^{3}\max_{U\leq M\leq N/V}\Delta,$

for

 $\Delta=\max_{V
###### Proof.

For $b_{m},c_{k}\in\mathbb{C}$, using the Cauchy-Schwarz inequality,

 $\begin{split}&\displaystyle\left|\sum_{M

and

 $\begin{split}&\displaystyle\sum_{M\leq m\leq 2M}\left|\sum_{V

so, using $|c_{j}c_{k}|\leq\frac{1}{2}|c_{j}|^{2}+\frac{1}{2}|c_{k}|^{2}$,

 $\begin{split}&\displaystyle\sum_{M\leq m\leq 2M}\left|\sum_{V

Therefore,

 $\left|\sum_{M

for

 $\Delta=\left(\max_{V

Because $\sum_{d\mid h}\mu(d)=0$ for $h>1$, if $1 then $\sum_{d\mid h,d\leq V}\mu(d)=0$. Thus

 $\displaystyle S_{4}$ $\displaystyle=-\sum_{n\leq N}f(n)\sum_{mh=n,m>U,h>1}\Lambda(m)\sum_{d\mid h,d% \leq V}\mu(d)$ $\displaystyle=-\sum_{U $\displaystyle=-\sum_{U $\displaystyle=-\sum_{M\in\{U,2U,4U,\ldots\},M

so

 $|S_{4}|\leq\left(\log_{2}\frac{N}{UV}\right)\max_{U\leq M\leq N/V}\left|\sum_{% M

Define $b_{m}=\Lambda(m)$ for $m\leq N/V$ and $b_{m}=0$ for $m>N/V$, and $c_{k}=\sum_{d\mid k,d\leq V}\mu(d)$. Using the above we get

 $\displaystyle|S_{4}|$ $\displaystyle\ll(\log N)\max_{U\leq M\leq N/V}\left|\sum_{M $\displaystyle\ll(\log N)\max_{U\leq M\leq N/V}\Delta\left(\sum_{M\leq m\leq 2M% }|b_{m}|^{2}\right)^{1/2}\left(\sum_{j\leq N/M}|c_{j}|^{2}\right)^{1/2}$ $\displaystyle\ll(\log N)\max_{U\leq M\leq N/V}\Delta\left(\sum_{M\leq m\leq 2M% }\Lambda(m)^{2}\right)^{1/2}\left(\sum_{j\leq N/M}d(k)^{2}\right)^{1/2}$

On the one hand,

 $\sum_{m\leq y}\Lambda(m)^{2}\leq(\log y)\sum_{m\leq y}\Lambda(m)=O(y\log y).$

On the other hand, let $h$ be the multiplicative arithmetic function such that for prime $p$ and for nonnegative integer $a$, $h(p^{a})=2a+1$. The divisor function satisfies $d(p^{a})=a+1$, and

 $\displaystyle\sum_{d\mid p^{a}}h(d)$ $\displaystyle=\sum_{0\leq b\leq a}h(p^{b})$ $\displaystyle=\sum_{0\leq b\leq a}(2b+1)$ $\displaystyle=a+1+2\sum_{0\leq b\leq a}b$ $\displaystyle=a+1+2\cdot\frac{a(a+1)}{2}$ $\displaystyle=a+1+a^{2}+a$ $\displaystyle=a^{2}+2a+1$ $\displaystyle=d(p^{a})^{2}.$

Hence, as $d\mapsto\frac{h(d)}{d}$ is multiplicative and nonnegative,

 $\displaystyle\sum_{k\leq y}d(k)^{2}$ $\displaystyle=\sum_{k\leq y}\sum_{d\mid k}h(d)$ $\displaystyle=\sum_{d\leq y}h(d)\sum_{kd\leq y}1$ $\displaystyle=\sum_{d\leq y}h(d)\cdot[y/d]$ $\displaystyle\leq y\sum_{d\leq y}\frac{h(d)}{d}$ $\displaystyle\leq y\prod_{p\leq y}\sum_{a=0}^{\infty}h(p^{a})p^{-a}$ $\displaystyle=y\prod_{p\leq y}\sum_{a=0}^{\infty}(2a+1)p^{-a}.$

But, for $0,

 $\left(1-x\right)^{-3}=\left(\sum_{a=0}^{\infty}x^{a}\right)^{3}=\sum_{a=0}^{% \infty}\frac{1}{2}(a+1)(a+2)x^{a}\geq\sum_{a=0}^{\infty}(2a+1)x^{a},$

so

 $\sum_{k\leq y}d(k)^{2}\leq y\left(\sum_{p\leq y}\left(1-p^{-1}\right)^{-1}% \right)^{3}.$

Merten’s theorem55 5 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, fifth ed., p. 351, Theorem 429. tells us

 $\prod_{p\leq y}\left(1-\frac{1}{p}\right)\sim\frac{e^{-\gamma}}{\log y},$

where $\gamma$ is Euler’s constant, and using this,

 $\sum_{k\leq y}d(k)^{2}=O(y(\log y)^{3}).$

We have therefore got for $U\leq M\leq N/V$,

 $\begin{split}&\displaystyle\left(\sum_{M\leq m\leq 2M}\Lambda(m)^{2}\right)^{1% /2}\left(\sum_{k\leq N/M}d(k)^{2}\right)^{1/2}\\ \displaystyle\leq&\displaystyle\left(\sum_{m\leq 2M}\Lambda(m)^{2}\right)^{1/2% }\left(\sum_{k\leq N/M}d(k)^{2}\right)^{1/2}\\ \displaystyle\leq&\displaystyle\left(O(M\log M)\right)^{1/2}\left(O(N/M(\log(N% /M))^{3}\right)^{1/2}\\ \displaystyle=&\displaystyle O(N^{1/2}(\log N)^{2}).\end{split}$

What we now have is

 $\displaystyle|S_{4}|$ $\displaystyle\ll(\log N)\cdot N^{1/2}(\log N)^{2}\cdot\max_{U\leq M\leq N/V}\Delta,$

proving the claim. ∎

Putting together the estimates for $S_{1},S_{2},S_{3},S_{4}$ gives, for $|f|\leq 1$, and $U,V\geq 2$, $UV\leq N$,

 $\displaystyle\sum_{n\leq N}f(n)\Lambda(n)$ $\displaystyle\ll U+(\log N)\sum_{h\leq UV}\left|\sum_{r\leq N/h}f(rh)\right|$ $\displaystyle+(\log N)\sum_{k\leq V}\max_{1\leq w\leq N/k}\left|\sum_{w\leq h% \leq N/k}f(kh)\right|$ $\displaystyle+N^{1/2}(\log N)^{3}\max_{U\leq M\leq N/V}\Delta,$

for

 $\Delta=\max_{V

## 4 Exponential sums

For $\beta\in\mathbb{R}$, on the one hand

 $\left|\sum_{N_{1}\leq n\leq N_{2}}e^{2\pi i\beta n}\right|\leq N_{2}-N_{1}+1.$

On the other hand,

 $\sum_{N_{1}\leq n\leq N_{2}}e^{2\pi i\beta n}=\sum_{0\leq n\leq N_{2}-N_{1}}e^% {2\pi i\beta n}=\frac{1-e^{2\pi i\beta(N_{2}-N_{1}+1)}}{1-e^{2\pi i\beta}}$

and hence

 $\left|\sum_{N_{1}\leq n\leq N_{2}}e^{2\pi i\beta n}\right|\leq\frac{2}{|1-e^{2% \pi i\beta}|}=\frac{1}{|\sin\pi\beta|}\leq\frac{1}{2\left\|\beta\right\|}.$

Thus

 $\left|\sum_{N_{1}\leq n\leq N_{2}}e^{2\pi i\beta n}\right|\ll\min\left\{N_{2}-% N_{1},\frac{1}{\left\|\beta\right\|}\right\}.$

Let $\alpha\in\mathbb{R}$ and let $f(n)=e^{2\pi i\alpha n}$. Then

 $\displaystyle\sum_{h\leq UV}\left|\sum_{r\leq N/h}f(rh)\right|$ $\displaystyle\leq\sum_{h\leq UV}\min\left\{\frac{N}{h},\frac{1}{\left\|h\alpha% \right\|}\right\}$

and

 $\displaystyle\sum_{k\leq V}\max_{w}\left|\sum_{w\leq h\leq N/k}f(rt)\right|$ $\displaystyle\ll\sum_{k\leq V}\max_{w}\min\left\{\frac{N}{k}-w,\frac{1}{\left% \|k\alpha\right\|}\right\}$ $\displaystyle\ll\sum_{k\leq V}\min\left\{\frac{N}{k},\frac{1}{\left\|k\alpha% \right\|}\right\}.$

Let $S_{N}(\alpha)=\sum_{n\leq N}\Lambda(n)f(n)$. By what we have worked out,

 $\displaystyle|S_{N}(\alpha)|$ $\displaystyle\ll U+(\log N)\sum_{h\leq UV}\min\left\{\frac{N}{h},\frac{1}{% \left\|h\alpha\right\|}\right\}$ $\displaystyle+(\log N)\sum_{k\leq V}\min\left\{\frac{N}{k},\frac{1}{\left\|k% \alpha\right\|}\right\}$ $\displaystyle+N^{1/2}(\log N)^{3}\max_{U\leq M\leq N/V}\Delta,$

for

 $\Delta=\max_{V

We calculate

 $\displaystyle\sum_{M\leq m\leq 2M,m\leq N/j,m\leq N/k}f(mj)\overline{f(mk)}$ $\displaystyle=\sum_{M\leq m\leq 2M,m\leq N/j,m\leq N/k}e^{2\pi i\alpha m(j-k)}$

so

 $\left|\sum_{M\leq m\leq 2M,m\leq N/j,m\leq N/k}f(mj)\overline{f(mk)}\right|\ll% \min\left\{M,\frac{1}{\left\|(j-k)\alpha\right\|}\right\}.$

We now have

 $\displaystyle|S_{N}(\alpha)|$ $\displaystyle\ll U+(\log N)\sum_{h\leq UV}\min\left\{\frac{N}{h},\frac{1}{% \left\|h\alpha\right\|}\right\}$ $\displaystyle+(\log N)\sum_{k\leq V}\min\left\{\frac{N}{k},\frac{1}{\left\|k% \alpha\right\|}\right\}$ $\displaystyle+N^{1/2}(\log N)^{3}\max_{U\leq M\leq N/V}\max_{V

But for $V, a fortiori $0\leq j\leq N/M$, whence

 $\displaystyle\sum_{V $\displaystyle\leq\sum_{0\leq k\leq N/M}\min\left\{M,\frac{1}{\left\|(k-j)% \alpha\right\|}\right\}$ $\displaystyle\leq\sum_{|m|\leq N/M}\min\left\{M,\frac{1}{\left\|m\alpha\right% \|}\right\}$ $\displaystyle=M+2\sum_{1\leq m\leq N/M}\min\left\{M,\frac{1}{\left\|m\alpha% \right\|}\right\}$ $\displaystyle\ll M+\sum_{1\leq m\leq N/M}\min\left\{\frac{N}{m},\frac{1}{\left% \|m\alpha\right\|}\right\}.$

Summarizing, we have the following.

###### Theorem 5.

For $\alpha\in\mathbb{R}$ and $U,V\geq 2,UV\leq N$,

 $\displaystyle|S_{N}(\alpha)|$ $\displaystyle\ll U+(\log N)\sum_{h\leq UV}\min\left\{\frac{N}{h},\frac{1}{% \left\|h\alpha\right\|}\right\}$ $\displaystyle+N^{1/2}(\log N)^{3}\max_{U\leq M\leq N/V}\left(M+\sum_{1\leq m% \leq N/M}\min\left\{\frac{N}{m},\frac{1}{\left\|m\alpha\right\|}\right\}\right% )^{1/2}.$

## 5 Diophantine approximation

###### Theorem 6.

There is some $C$ such that for all $0<\alpha<1$, if $\left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q^{2}}$, $\gcd(a,q)=1$, and $T\geq 1$, then

 $\sum_{t\leq T}\min\left\{\frac{N}{t},\frac{1}{\left\|t\alpha\right\|}\right\}% \leq C\left(\frac{N}{q}+T+q\right)\log(2qT).$
###### Proof.

Write $\beta=\alpha-\frac{a}{q}$. Then

 $\displaystyle\sum_{t\leq T}\min\left\{\frac{N}{t},\frac{1}{\left\|t\alpha% \right\|}\right\}$ $\displaystyle\leq\sum_{0\leq h\leq T/q}\sum_{1\leq r\leq q}\min\left\{\frac{N}% {hq+r},\frac{1}{\left\|hq\alpha+r\alpha\right\|}\right\}$ $\displaystyle=\sum_{0\leq h\leq T/q}\sum_{1\leq r\leq q}\min\left\{\frac{N}{hq% +r},\frac{1}{\left\|\frac{ra}{q}+hq\beta+r\beta\right\|}\right\}.$

If $h=0$ and $1\leq r\leq\frac{q}{2}$, then, using $\left\|x-y\right\|\geq\left\|x\right\|-\left\|y\right\|$ and $|\beta|\leq\frac{1}{q^{2}}$,

 $\frac{1}{\left\|\frac{ra}{q}+hq\beta+r\beta\right\|}=\frac{1}{\left\|\frac{ra}% {q}+r\beta\right\|}\leq\frac{1}{\left\|\frac{ra}{q}\right\|-\left\|r\beta% \right\|}\leq\frac{1}{\left\|\frac{ra}{q}\right\|-\frac{1}{2q}},$

and, as $\gcd(a,q)=1$,

 $\displaystyle\sum_{1\leq r\leq\frac{q}{2}}\frac{1}{\left\|\frac{ra}{q}\right\|% -\frac{1}{2q}}$ $\displaystyle\leq\sum_{1\leq m $\displaystyle\leq 2\sum_{1\leq m\leq\frac{q}{2}}\frac{1}{\frac{m}{q}-\frac{1}{% 2q}}$ $\displaystyle=\sum_{1\leq m\leq\frac{q}{2}}\frac{4q}{2m-1}$ $\displaystyle\leq 4q\sum_{1\leq m\leq q-1}\frac{1}{m}$ $\displaystyle\leq 4q\log(2q).$

Otherwise, $1\leq h\leq T/q$ or $\frac{q}{2}, and then $hq+r\geq\frac{1}{2}(h+1)q$, and the sum over these indices is

 $\ll\sum_{0\leq h\leq T/q}\sum_{1\leq r\leq q}\min\left\{\frac{N}{(h+1)q},\frac% {1}{\left\|\frac{ra}{q}+hq\beta+r\beta\right\|}\right\}.$

So we have got

 $\sum_{t\leq T}\min\left\{\frac{N}{t},\frac{1}{\left\|t\alpha\right\|}\right\}% \ll q\log(2q)+\sum_{0\leq h\leq T/q}\sum_{1\leq r\leq q}\min\left\{\frac{N}{(h% +1)q},\frac{1}{\left\|\frac{ra}{q}+hq\beta+r\beta\right\|}\right\}.$

Let $1\leq h\leq T/q$, let $I=[A,B]$ be a closed arc in $\mathbb{R}/\mathbb{Z}$ of measure $q^{-1}$, and let $J=[A-hq\beta-q^{-1},B-hq\beta+q^{-1}]\subset\mathbb{R}/\mathbb{Z}$. For $1\leq r\leq q$, if $\frac{ra}{q}+hq\beta+r\beta\in I$ then $\frac{ra}{q}+r\beta\in[A-hq\beta,B-hq\beta]$, and as $|r\beta|\leq q^{-1}$, then $\frac{ra}{q}\in J$. As $J$ is a closed arc with measure $3q^{-1}$ and $\frac{a}{q},\frac{2a}{q},\ldots,\frac{q\cdot a}{q}$ are distinct in $\mathbb{R}/\mathbb{Z}$, due to $\gcd(a,q)=1$, there are at most four $r$, $1\leq r\leq q$, for which $\frac{ra}{q}\in J$. Therefore there are at most four $r$, $1\leq r\leq q$, for which $\frac{ra}{q}+hq\beta+r\beta\in I$.

For $0\leq j\leq q-1$, let $I_{j}=[jq^{-1},(j+1)q^{-1}]$. If $\frac{ra}{q}+hq\beta+r\beta\in I_{j}\subset\mathbb{R}/\mathbb{Z}$, then

 $\left\|\frac{ra}{q}+hq\beta+r\beta\right\|\geq\min\{jq^{-1},1-(j+1)q^{-1}\}$

i.e.

 $\frac{1}{\left\|\frac{ra}{q}+hq\beta+r\beta\right\|}\leq\frac{q}{\min\{j,q-j-1% \}}.$

Therefore, for $1\leq r\leq q$ with $\frac{ra}{q}+hq\beta+r\beta\in I_{j}\subset\mathbb{R}/\mathbb{Z}$,

 $\displaystyle\min\left\{\frac{N}{(h+1)q},\frac{1}{\left\|\frac{ra}{q}+hq\beta+% r\beta\right\|}\right\}$ $\displaystyle\leq\min\left\{\frac{N}{(h+1)q},\frac{q}{\min\{j,q-j-1\}}\right\}$ $\displaystyle\leq\begin{cases}\frac{N}{(h+1)q}&j=0,q-1\\ \frac{q}{\min\{j,q-j-1\}}&1\leq j\leq q-2.\end{cases}$

We have just established that for each $0\leq j\leq q-1$ there are at most four $1\leq r\leq q$ such that $\frac{ra}{q}+hq\beta+r\beta\in I_{j}\subset\mathbb{R}/\mathbb{Z}$, and hence

 $\begin{split}&\displaystyle\sum_{0\leq h\leq T/q}\sum_{1\leq r\leq q}\min\left% \{\frac{N}{(h+1)q},\frac{1}{\left\|\frac{ra}{q}+hq\beta+r\beta\right\|}\right% \}\\ \displaystyle\leq&\displaystyle\sum_{0\leq h\leq T/q}\sum_{0\leq j\leq q-1}4% \cdot\begin{cases}\frac{N}{(h+1)q}&j=0,q-1\\ \frac{q}{\min\{j,q-j-1\}}&1\leq j\leq q-2\end{cases}\\ \displaystyle=&\displaystyle\sum_{0\leq h\leq T/q}\left(\frac{8N}{(h+1)q}+\sum% _{1\leq j\leq q-2}\frac{q}{\min\{j,q-j-1\}}\right)\\ \displaystyle\leq&\displaystyle\frac{8N}{q}\sum_{1\leq h\leq\frac{T}{q}+1}% \frac{1}{h+1}+\left(\frac{T}{q}+1\right)\cdot 2q\sum_{1\leq j\leq q/2}\frac{1}% {j}\\ \displaystyle\ll&\displaystyle\frac{N}{q}\log(2T/q)+\left(\frac{T}{q}+1\right)% \cdot q\log q.\end{split}$

Putting things together,

 $\displaystyle\sum_{t\leq T}\min\left\{\frac{N}{t},\frac{1}{\left\|t\alpha% \right\|}\right\}$ $\displaystyle\ll q\log(2q)+\frac{N}{q}\log(2T)+\left(\frac{T}{q}+1\right)q\log% (2q)$ $\displaystyle\ll q\log(2qT)+\frac{N}{q}\log(2qT)+T\log(2qT).$

We now combine Theorem 5 and Theorem 6. For $U,V\geq 2,UV\leq N,T\geq 1$, $\left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q^{2}}$, $\gcd(a,q)=1$,

 $\displaystyle|S_{N}(\alpha)|$ $\displaystyle\ll U+(\log N)\left(\frac{N}{q}+UV+q\right)\log(2qUV)$ $\displaystyle+N^{1/2}(\log N)^{3}\max_{U\leq M\leq N/V}\left(M+\left(\frac{N}{% q}+\frac{N}{M}+q\right)\log(2qN/M)\right)^{1/2}$ $\displaystyle\ll U+(\log 2qN)^{3}\left(\frac{N}{q}+UV+q\right)$ $\displaystyle+N^{1/2}(\log qN)^{7/2}\max_{U\leq M\leq N/V}\left(M+\frac{N}{q}+% \frac{N}{M}+q\right)^{1/2}$ $\displaystyle\ll U+(\log 2qN)^{3}\left(\frac{N}{q}+UV+q\right)$ $\displaystyle+N^{1/2}(\log qN)^{7/2}\left(\left(U+\frac{N}{q}+\frac{N}{U}+q% \right)^{1/2}+\left(\frac{N}{V}+\frac{N}{q}+V+q\right)^{1/2}\right).$

Now take $U=V$, for which

 $\displaystyle|S_{N}(\alpha)|$ $\displaystyle\ll U+(\log 2qN)^{3}\left(\frac{N}{q}+U^{2}+q\right)$ $\displaystyle+N^{1/2}(\log qN)^{7/2}\left(U+\frac{N}{q}+\frac{N}{U}+q\right)^{% 1/2}$ $\displaystyle\ll U+(\log 2qN)^{3}\left(\frac{N}{q}+U^{2}+q\right)$ $\displaystyle+N^{1/2}(\log qN)^{7/2}(U^{1/2}+N^{1/2}q^{-1/2}+N^{1/2}U^{-1/2}+q% ^{1/2})$ $\displaystyle=U+(\log 2qN)^{3}\left(\frac{N}{q}+U^{2}+q\right)$ $\displaystyle+(\log qN)^{7/2}(N^{1/2}U^{1/2}+Nq^{-1/2}+NU^{-1/2}+N^{1/2}q^{1/2% }).$

For $U=N^{2/5}$ we get the following.

###### Theorem 7.

There is some $C$ such that if $\alpha\in\mathbb{R}$, $\left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q^{2}}$, $a\geq 1$, $\gcd(a,q)=1$, then for any $N\geq 1$,

 $|S_{N}(\alpha)|\leq C(Nq^{-1/2}+N^{4/5}+N^{1/2}q^{1/2})(\log N)^{4}.$