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.¹¹ 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 that²² 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)$ .³³ 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,⁴⁴ 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<j\leq N/M}\left(\sum_{V<k\leq N/M}\left|\sum_{M\leq m\leq 2M,m%\leq N/j,m\leq N/k}f(mj)\overline{f(mk)}\right|\right)^{1/2}.

Proof.

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

\begin{split}&\displaystyle\left|\sum_{M<m\leq 2M}b_{m}\sum_{V<k\leq N/m}c_{k}%f(mk)\right|\\\displaystyle\leq&\displaystyle\left(\sum_{M\leq m\leq 2M}|b_{m}|^{2}\right)^{%1/2}\left(\sum_{M\leq m\leq 2M}\left|\sum_{V<k\leq N/m}c_{k}f(mk)\right|^{2}%\right)^{1/2},\end{split}

and

\begin{split}&\displaystyle\sum_{M\leq m\leq 2M}\left|\sum_{V<k\leq N/m}c_{k}f%(mk)\right|^{2}\\\displaystyle=&\displaystyle\sum_{M\leq m\leq 2M}\left(\sum_{V<j\leq N/m}c_{j}%f(mj)\right)\left(\sum_{V<k\leq N/m}\overline{c_{k}f(mk)}\right)\\\displaystyle=&\displaystyle\sum_{V<j\leq N/M}\sum_{V<k\leq N/M}c_{j}\overline%{c_{k}}\sum_{M\leq m\leq 2M,m\leq N/j,m\leq N/k}f(mj)\overline{f(mk)},\end{split}

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<k\leq N/m}c_{k}f%(mk)\right|^{2}\\\displaystyle\leq&\displaystyle\sum_{V<j\leq N/M}\sum_{V<k\leq N/M}\left(\frac%{1}{2}|c_{j}|^{2}+\frac{1}{2}|c_{k}|^{2}\right)\left|\sum_{M\leq m\leq 2M,m%\leq N/j,m\leq N/k}f(mj)\overline{f(mk)}\right|\\\displaystyle=&\displaystyle\sum_{V<j\leq N/M}|c_{j}|^{2}\sum_{V<k\leq N/M}%\left|\sum_{M\leq m\leq 2M,m\leq N/j,m\leq N/k}f(mj)\overline{f(mk)}\right|\\\displaystyle\leq&\displaystyle\left(\sum_{V<j\leq N/M}|c_{j}|^{2}\right)\max_%{V<j\leq N/M}\sum_{V<k\leq N/M}\left|\sum_{M\leq m\leq 2M,m\leq N/j,m\leq N/k}%f(mj)\overline{f(mk)}\right|.\end{split}

Therefore,

\left|\sum_{M<m\leq 2M}b_{m}\sum_{V<k\leq N/m}c_{k}f(mk)\right|\leq\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}

for

\Delta=\left(\max_{V<j\leq N/M}\sum_{V<k\leq N/M}\left|\sum_{M\leq m\leq 2M,m%\leq N/j,m\leq N/k}f(mj)\overline{f(mk)}\right|\right)^{1/2}.

Because $\sum_{d\mid h}\mu(d)=0$ for $h>1$ , if $1<h\leq V$ 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<m<N/V}\Lambda(m)\sum_{V<k\leq N/m}f(mk)\sum_{d\mid k,d%\leq V}\mu(d)$
		$\displaystyle=-\sum_{U<m\leq N/V}\Lambda(m)\sum_{V<k\leq N/m}f(mk)\sum_{d\mid k%,d\leq V}\mu(d)$
		$\displaystyle=-\sum_{M\in\{U,2U,4U,\ldots\},M<N/V}\sum_{M<m\leq\min(N/V,2M)}%\Lambda(m)\sum_{V<k\leq N/m}f(mk)\sum_{d\mid k,d\leq V}\mu(d),$

|S_{4}|\leq\left(\log_{2}\frac{N}{UV}\right)\max_{U\leq M\leq N/V}\left|\sum_{%M<m\leq\min(N/V,2M)}\Lambda(m)\sum_{V<k\leq N/m}f(mk)\sum_{d\mid k,d\leq V}\mu%(d)\right|.

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<m\leq 2M}b_{m}\sum%_{V<k\leq N/m}c_{k}f(mk)\right\|$
		$\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<x<1$ ,

\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},

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

Merten’s theorem⁵⁵ 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<j\leq N/M}\left(\sum_{V<k\leq N/M}\left|\sum_{M\leq m\leq 2M,m%\leq N/j,m\leq N/k}f(mj)\overline{f(mk)}\right|\right)^{1/2}.

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<j\leq N/M}\left(\sum_{V<k\leq N/M}\left|\sum_{M\leq m\leq 2M,m%\leq N/j,m\leq N/k}f(mj)\overline{f(mk)}\right|\right)^{1/2}.

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

\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<j\leq N/M}\left%(\sum_{V<k\leq N/M}\min\left\{M,\frac{1}{\left\\|(k-j)\alpha\right\\|}\right\}%\right)^{1/2}.$

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

	$\displaystyle\sum_{V<k\leq N/M}\min\left\{M,\frac{1}{\left\\|(k-j)\alpha\right%\\|}\right\}$	$\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<q}\frac{1}{\left\\|\frac{m}{q}\right\\|-\frac{1}{%2q}}$
		$\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}<r\leq q$ , 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}.

	$\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,$

	$\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<j\leq N/M}\left%(\sum_{V<k\leq N/M}\min\left\{M,\frac{1}{\left\\|(k-j)\alpha\right\\|}\right\}%\right)^{1/2}.$

	$\displaystyle\sum_{V<k\leq N/M}\min\left\{M,\frac{1}{\left\\|(k-j)\alpha\right%\\|}\right\}$	$\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\}.$