Vinogradov’s estimate for exponential sums over primes

1 Introduction

For $x\in ℝ$, let $[x]$ be the greatest integer $\le x$, let $R(x)=x-[x]$, and let

$$\parallel x\parallel =\min \{R(x),1-R(x)\}=\underset{m\in \mathbb{Z}}{\min }|x-m|.$$

In this note I work through Chapters 24 and 25 of Harold Davenport, Multiplicative Number Theory, third ed.

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

2 The von Mangoldt function

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

$$\log n=\sum _{d\mid n}\mathrm{\Lambda }(d),$$

and so by the Möbius inversion formula,

$$\mathrm{\Lambda }(n)=\sum _{d\mid n}\mu (n/d)\log d.$$

For $n>1$ it is a fact that

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

Write $\psi (x)={\sum }_{n\le x}\mathrm{\Lambda }(n)$. It is a fact that $\psi (x)=O(x)$. (The prime number theorem states $\psi (x)\sim x$.)

The derivative of the Riemann zeta function is

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

The Euler product for the Riemann zeta function is

$$\zeta (s)=\sum _{m=1}^{\mathrm{\infty }}{m}^{-s}=\prod _p{(1-p^{-s})}^{-1},\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}{\displaystyle \frac{p^{-s}\log p}{1-p^{-s}}}$

$={\displaystyle \sum _p}\log p{\displaystyle \sum _{l=1}^{\mathrm{\infty }}}{p}^{-ls}$

$={\displaystyle \sum _p}{\displaystyle \sum _{l=1}^{\mathrm{\infty }}}\mathrm{\Lambda }(p^l){(p^l)}^{-s}$

$={\displaystyle \sum _{n=1}^{\mathrm{\infty }}}\mathrm{\Lambda }(n)n^{-s}.$

Let $U,V\ge 2$, $UV\le N$, and write

$$F_U(s)=\sum _{j\le U}\mathrm{\Lambda }(j)j^{-s},G_V(s)=\sum _{k\le V}\mu (k)k^{-s}.$$

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

First,

$$F_U(s)=\sum _{n=1}^{\mathrm{\infty }}{a}_1(n)n^{-s}$$

for

Second,

$$-\zeta (s)F_U(s)G_V(s)=\sum _{n=1}^{\mathrm{\infty }}{a}_2(n)n^{-s}$$

for

$$a_2(n)=-\sum _{mjk=n,m\ge 1,j\le U,k\le V}1\cdot \mathrm{\Lambda }(j)\cdot \mu (k)=-\sum _{d\mid n}\sum _{djk=n,j\le U,k\le V}\mathrm{\Lambda }(j)\mu (k).$$

Third,

$$-{\zeta }^{\prime }(s)G_V(s)=\sum _{n=1}^{\mathrm{\infty }}{a}_3(n)n^{-s}$$

for

$$a_3(n)=\sum _{mk=n,m\ge 1,k\le V}\log (m)\cdot \mu (k)=\sum _{d\mid n}\log d\sum _{dk=n,k\le V}\mu (k).$$

Fourth,

$$-\frac{{\zeta }^{\prime }(s)}{\zeta (s)}-F_U(s)=\sum _{m>U}\mathrm{\Lambda }(m)m^{-s};$$

and

$$\zeta (s)G_V(s)=\sum _{n=1}^{\mathrm{\infty }}\left(\sum _{mk=n,m\ge 1,k\le V}1\cdot \mu (k)\right)n^{-s}=\sum _{n=1}^{\mathrm{\infty }}\left(\sum _{d\mid n,d\le V}\mu (d)\right)n^{-s}$$

whence

$$1-\zeta (s)G_V(s)=-\sum _{h=2}^{\mathrm{\infty }}\left(\sum _{d\mid h,d\le 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}^{\mathrm{\infty }}{a}_4(n)n^{-s}$$

for

$$a_4(n)=-\sum _{mh=n,m>U,h>1}\mathrm{\Lambda }(m)\left(\sum _{d\mid h,d\le V}\mu (d)\right).$$

We have

$$\mathrm{\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|\le 1$ and write

$$S_i=\sum _{n\le N}f(n)a_i(n),$$

for which

$$\sum _{n\le N}f(n)\mathrm{\Lambda }(n)=S_1+S_2+S_3+S_4.$$

$S_1$ $={\displaystyle \sum _{n\le U}}f(n)\mathrm{\Lambda }(n)$

$S_2$ $=-{\displaystyle \sum _{n\le N}}f(n){\displaystyle \sum _{d\mid n}}{\displaystyle \sum _{djk=n,j\le U,k\le V}}\mathrm{\Lambda }(j)\mu (k)$

$S_3$ $={\displaystyle \sum _{n\le N}}f(n){\displaystyle \sum _{d\mid n}}\log d{\displaystyle \sum _{dk=n,k\le V}}\mu (k)$

$S_4$ $=-{\displaystyle \sum _{n\le N}}f(n){\displaystyle \sum _{mh=n,m>U,h>1}}\mathrm{\Lambda }(m){\displaystyle \sum _{d\mid h,d\le V}}\mu (d).$

Lemma 1.

$|S_1|=O(U)$.

Proof.

As $|f|\le 1$,

$$|S_1|\le \sum _{n\le U}\mathrm{\Lambda }(n)=\psi (U)=O(U).$$

∎

Lemma 2.

$$|S_2|\le \log UV\cdot \sum _{h\le UV}\left|\sum _{r\le N/h}f(rh)\right|.$$

Proof.

$S_2$ $=-{\displaystyle \sum _{n\le N}}f(n){\displaystyle \sum _{d\mid n}}{\displaystyle \sum _{djk=n,j\le U,k\le V}}\mathrm{\Lambda }(j)\mu (k)$

$=-{\displaystyle \sum _{h\le UV}}\left({\displaystyle \sum _{jk=h,j\le U,k\le V}}\mathrm{\Lambda }(j)\mu (k)\right){\displaystyle \sum _{r\le N/h}}f(rh).$

For $h\le UV$, ${\sum }_{j\mid h}\mathrm{\Lambda }(j)=\log h\le \log UV$, so

$$|S_2|\le \log UV\cdot \sum _{h\le UV}\left|\sum _{r\le N/h}f(rh)\right|.$$

∎

Lemma 3.

$$|S_3|\le \log N\cdot \sum _{k\le V}\underset{1\le w\le N/k}{\max }\left|\sum _{w\le h\le N/k}f(kh)\right|.$$

Proof.

$S_3$ $={\displaystyle \sum _{n\le N}}f(n){\displaystyle \sum _{d\mid n}}\log d{\displaystyle \sum _{dk=n,k\le V}}\mu (k)$

$={\displaystyle \sum _{k\le V}}\mu (k){\displaystyle \sum _{h\le N/k}}f(kh)\log h$

$={\displaystyle \sum _{k\le V}}\mu (k){\displaystyle \sum _{h\le N/k}}f(kh){\displaystyle {\int }_1^h}{\displaystyle \frac{dw}{w}}$

$={\displaystyle \sum _{k\le V}}\mu (k){\displaystyle {\int }_1^{N/k}}{\displaystyle \sum _{w\le h\le N/k}}f(kh){\displaystyle \frac{dw}{w}}$

$={\displaystyle {\int }_1^N}{\displaystyle \sum _{k\le V}}\mu (k){\displaystyle \sum _{w\le h\le N/k}}f(kh){\displaystyle \frac{dw}{w}}.$

Then

$|S_3|$ $\le \underset{1\le w\le N}{\max }\left|{\displaystyle \sum _{k\le V}}\mu (k){\displaystyle \sum _{w\le h\le N/k}}f(kh)\right|\cdot {\displaystyle {\int }_1^N}{\displaystyle \frac{dw}{w}}$

$\le \log N\cdot {\displaystyle \sum _{k\le V}}\underset{1\le w\le N/k}{\max }\left|{\displaystyle \sum _{w\le h\le N/k}}f(kh)\right|.$

∎

Lemma 4.

$$|S_4|\ll N^{1/2}{(\log N)}^3\underset{U\le M\le N/V}{\max }\mathrm{\Delta },$$

for

Proof.

For $b_m,c_k\in ℂ$, using the Cauchy-Schwarz inequality,

and

so, using $|c_j{c}_k|\le \frac{1}{2}{|c_j|}^2+\frac{1}{2}{|c_k|}^2$,

Therefore,

for

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

$S_4$ $=-{\displaystyle \sum _{n\le N}}f(n){\displaystyle \sum _{mh=n,m>U,h>1}}\mathrm{\Lambda }(m){\displaystyle \sum _{d\mid h,d\le V}}\mu (d)$

so

Define $b_m=\mathrm{\Lambda }(m)$ for $m\le N/V$ and $b_m=0$ for $m>N/V$, and $c_k={\sum }_{d\mid k,d\le V}\mu (d)$. Using the above we get

$|S_4|$

$\ll (\log N)\underset{U\le M\le N/V}{\max }\mathrm{\Delta }{\left({\displaystyle \sum _{M\le m\le 2M}}{|b_m|}^2\right)}^{1/2}{\left({\displaystyle \sum _{j\le N/M}}{|c_j|}^2\right)}^{1/2}$

$\ll (\log N)\underset{U\le M\le N/V}{\max }\mathrm{\Delta }{\left({\displaystyle \sum _{M\le m\le 2M}}\mathrm{\Lambda }{(m)}^2\right)}^{1/2}{\left({\displaystyle \sum _{j\le N/M}}d{(k)}^2\right)}^{1/2}$

On the one hand,

$$\sum _{m\le y}\mathrm{\Lambda }{(m)}^2\le (\log y)\sum _{m\le y}\mathrm{\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\le b\le a}}h(p^b)$

$={\displaystyle \sum _{0\le b\le a}}(2b+1)$

$=a+1+2{\displaystyle \sum _{0\le b\le a}}b$

$=a+1+2\cdot {\displaystyle \frac{a(a+1)}{2}}$

$=a+1+a^2+a$

$=a^2+2a+1$

$=d{(p^a)}^2.$

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

${\displaystyle \sum _{k\le y}}d{(k)}^2$ $={\displaystyle \sum _{k\le y}}{\displaystyle \sum _{d\mid k}}h(d)$

$={\displaystyle \sum _{d\le y}}h(d){\displaystyle \sum _{kd\le y}}1$

$={\displaystyle \sum _{d\le y}}h(d)\cdot [y/d]$

$\le y{\displaystyle \sum _{d\le y}}{\displaystyle \frac{h(d)}{d}}$

$\le y{\displaystyle \prod _{p\le y}}{\displaystyle \sum _{a=0}^{\mathrm{\infty }}}h(p^a)p^{-a}$

$=y{\displaystyle \prod _{p\le y}}{\displaystyle \sum _{a=0}^{\mathrm{\infty }}}(2a+1)p^{-a}.$

But, for ,

$${\left(1-x\right)}^{-3}={\left(\sum _{a=0}^{\mathrm{\infty }}{x}^a\right)}^3=\sum _{a=0}^{\mathrm{\infty }}\frac{1}{2}(a+1)(a+2)x^a\ge \sum _{a=0}^{\mathrm{\infty }}(2a+1)x^a,$$

so

$$\sum _{k\le y}d{(k)}^2\le y{\left(\sum _{p\le y}{\left(1-p^{-1}\right)}^{-1}\right)}^3.$$

Merten’s theorem tells us

$$\prod _{p\le y}\left(1-\frac{1}{p}\right)\sim \frac{e^{-\gamma }}{\log y},$$

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

$$\sum _{k\le y}d{(k)}^2=O(y{(\log y)}^3).$$

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

What we now have is

$|S_4|$ $\ll (\log N)\cdot N^{1/2}{(\log N)}^2\cdot \underset{U\le M\le N/V}{\max }\mathrm{\Delta },$

proving the claim. ∎

Putting together the estimates for $S_1,S_2,S_3,S_4$ gives, for $|f|\le 1$, and $U,V\ge 2$, $UV\le N$,

${\displaystyle \sum _{n\le N}}f(n)\mathrm{\Lambda }(n)$ $\ll U+(\log N){\displaystyle \sum _{h\le UV}}\left|{\displaystyle \sum _{r\le N/h}}f(rh)\right|$

$+(\log N){\displaystyle \sum _{k\le V}}\underset{1\le w\le N/k}{\max }\left|{\displaystyle \sum _{w\le h\le N/k}}f(kh)\right|$

$+N^{1/2}{(\log N)}^3\underset{U\le M\le N/V}{\max }\mathrm{\Delta },$

for

4 Exponential sums

For $\beta \in ℝ$, on the one hand

$$\left|\sum _{N_1\le n\le N_2}{e}^{2\pi i\beta n}\right|\le N_2-N_1+1.$$

On the other hand,

$$\sum _{N_1\le n\le N_2}{e}^{2\pi i\beta n}=\sum _{0\le n\le 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\le n\le N_2}{e}^{2\pi i\beta n}\right|\le \frac{2}{|1-e^{2\pi i\beta }|}=\frac{1}{|\sin \pi \beta |}\le \frac{1}{2\parallel \beta \parallel }.$$

Thus

$$\left|\sum _{N_1\le n\le N_2}{e}^{2\pi i\beta n}\right|\ll \min \{N_2-N_1,\frac{1}{\parallel \beta \parallel }\}.$$

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

${\displaystyle \sum _{h\le UV}}\left|{\displaystyle \sum _{r\le N/h}}f(rh)\right|$ $\le {\displaystyle \sum _{h\le UV}}\min \{{\displaystyle \frac{N}{h}},{\displaystyle \frac{1}{\parallel h\alpha \parallel }}\}$

and

${\displaystyle \sum _{k\le V}}\underset{w}{\max }\left|{\displaystyle \sum _{w\le h\le N/k}}f(rt)\right|$ $\ll {\displaystyle \sum _{k\le V}}\underset{w}{\max }\min \{{\displaystyle \frac{N}{k}}-w,{\displaystyle \frac{1}{\parallel k\alpha \parallel }}\}$

$\ll {\displaystyle \sum _{k\le V}}\min \{{\displaystyle \frac{N}{k}},{\displaystyle \frac{1}{\parallel k\alpha \parallel }}\}.$

Let $S_N(\alpha )={\sum }_{n\le N}\mathrm{\Lambda }(n)f(n)$. By what we have worked out,

$|S_N(\alpha )|$ $\ll U+(\log N){\displaystyle \sum _{h\le UV}}\min \{{\displaystyle \frac{N}{h}},{\displaystyle \frac{1}{\parallel h\alpha \parallel }}\}$

$+(\log N){\displaystyle \sum _{k\le V}}\min \{{\displaystyle \frac{N}{k}},{\displaystyle \frac{1}{\parallel k\alpha \parallel }}\}$

$+N^{1/2}{(\log N)}^3\underset{U\le M\le N/V}{\max }\mathrm{\Delta },$

for

We calculate

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

so

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

We now have

$|S_N(\alpha )|$ $\ll U+(\log N){\displaystyle \sum _{h\le UV}}\min \{{\displaystyle \frac{N}{h}},{\displaystyle \frac{1}{\parallel h\alpha \parallel }}\}$

$+(\log N){\displaystyle \sum _{k\le V}}\min \{{\displaystyle \frac{N}{k}},{\displaystyle \frac{1}{\parallel k\alpha \parallel }}\}$

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

$\le {\displaystyle \sum _{0\le k\le N/M}}\min \{M,{\displaystyle \frac{1}{\parallel (k-j)\alpha \parallel }}\}$

$\le {\displaystyle \sum _{|m|\le N/M}}\min \{M,{\displaystyle \frac{1}{\parallel m\alpha \parallel }}\}$

$=M+2{\displaystyle \sum _{1\le m\le N/M}}\min \{M,{\displaystyle \frac{1}{\parallel m\alpha \parallel }}\}$

$\ll M+{\displaystyle \sum _{1\le m\le N/M}}\min \{{\displaystyle \frac{N}{m}},{\displaystyle \frac{1}{\parallel m\alpha \parallel }}\}.$

Summarizing, we have the following.

Theorem 5.

For $\alpha \mathrm{\in }\mathrm{R}$ and $U\mathrm{,}V\mathrm{\ge }\mathrm{2}\mathrm{,}U\mathit{}V\mathrm{\le }N$,

$|S_N(\alpha )|$ $\ll U+(\log N){\displaystyle \sum _{h\le UV}}\min \{{\displaystyle \frac{N}{h}},{\displaystyle \frac{1}{\parallel h\alpha \parallel }}\}$

$+N^{1/2}{(\log N)}^3\underset{U\le M\le N/V}{\max }{(M+{\displaystyle \sum _{1\le m\le N/M}}\min \{{\displaystyle \frac{N}{m}},{\displaystyle \frac{1}{\parallel m\alpha \parallel }}\})}^{1/2}.$

5 Diophantine approximation

Theorem 6.

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

$$\sum _{t\le T}\min \{\frac{N}{t},\frac{1}{\parallel t\alpha \parallel }\}\le C\left(\frac{N}{q}+T+q\right)\log (2qT).$$

Proof.

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

${\displaystyle \sum _{t\le T}}\min \{{\displaystyle \frac{N}{t}},{\displaystyle \frac{1}{\parallel t\alpha \parallel }}\}$ $\le {\displaystyle \sum _{0\le h\le T/q}}{\displaystyle \sum _{1\le r\le q}}\min \{{\displaystyle \frac{N}{hq+r}},{\displaystyle \frac{1}{\parallel hq\alpha +r\alpha \parallel }}\}$

$={\displaystyle \sum _{0\le h\le T/q}}{\displaystyle \sum _{1\le r\le q}}\min \{{\displaystyle \frac{N}{hq+r}},{\displaystyle \frac{1}{\parallel \frac{ra}{q}+hq\beta +r\beta \parallel }}\}.$

If $h=0$ and $1\le r\le \frac{q}{2}$, then, using $\parallel x-y\parallel \ge \parallel x\parallel -\parallel y\parallel$ and $|\beta |\le \frac{1}{q^2}$,

$$\frac{1}{\parallel \frac{ra}{q}+hq\beta +r\beta \parallel }=\frac{1}{\parallel \frac{ra}{q}+r\beta \parallel }\le \frac{1}{\parallel \frac{ra}{q}\parallel -\parallel r\beta \parallel }\le \frac{1}{\parallel \frac{ra}{q}\parallel -\frac{1}{2q}},$$

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

${\displaystyle \sum _{1\le r\le \frac{q}{2}}}{\displaystyle \frac{1}{\parallel \frac{ra}{q}\parallel -\frac{1}{2q}}}$

$\le 2{\displaystyle \sum _{1\le m\le \frac{q}{2}}}{\displaystyle \frac{1}{\frac{m}{q}-\frac{1}{2q}}}$

$={\displaystyle \sum _{1\le m\le \frac{q}{2}}}{\displaystyle \frac{4q}{2m-1}}$

$\le 4q{\displaystyle \sum _{1\le m\le q-1}}{\displaystyle \frac{1}{m}}$

$\le 4q\log (2q).$

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

$$\ll \sum _{0\le h\le T/q}\sum _{1\le r\le q}\min \{\frac{N}{(h+1)q},\frac{1}{\parallel \frac{ra}{q}+hq\beta +r\beta \parallel }\}.$$

So we have got

$$\sum _{t\le T}\min \{\frac{N}{t},\frac{1}{\parallel t\alpha \parallel }\}\ll q\log (2q)+\sum _{0\le h\le T/q}\sum _{1\le r\le q}\min \{\frac{N}{(h+1)q},\frac{1}{\parallel \frac{ra}{q}+hq\beta +r\beta \parallel }\}.$$

Let $1\le h\le T/q$, let $I=[A,B]$ be a closed arc in $ℝ/\mathbb{Z}$ of measure $q^{-1}$, and let $J=[A-hq\beta -q^{-1},B-hq\beta +q^{-1}]\subset ℝ/\mathbb{Z}$. For $1\le r\le 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 |\le 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},\mathrm{\dots },\frac{q\cdot a}{q}$ are distinct in $ℝ/\mathbb{Z}$, due to $\gcd (a,q)=1$, there are at most four $r$, $1\le r\le q$, for which $\frac{ra}{q}\in J$. Therefore there are at most four $r$, $1\le r\le q$, for which $\frac{ra}{q}+hq\beta +r\beta \in I$.

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

$$\parallel \frac{ra}{q}+hq\beta +r\beta \parallel \ge \min \{j{q}^{-1},1-(j+1)q^{-1}\}$$

i.e.

$$\frac{1}{\parallel \frac{ra}{q}+hq\beta +r\beta \parallel }\le \frac{q}{\min \{j,q-j-1\}}.$$

Therefore, for $1\le r\le q$ with $\frac{ra}{q}+hq\beta +r\beta \in I_j\subset ℝ/\mathbb{Z}$,

$\min \{{\displaystyle \frac{N}{(h+1)q}},{\displaystyle \frac{1}{\parallel \frac{ra}{q}+hq\beta +r\beta \parallel }}\}$ $\le \min \{{\displaystyle \frac{N}{(h+1)q}},{\displaystyle \frac{q}{\min \{j,q-j-1\}}}\}$

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

Putting things together,

${\displaystyle \sum _{t\le T}}\min \{{\displaystyle \frac{N}{t}},{\displaystyle \frac{1}{\parallel t\alpha \parallel }}\}$ $\ll q\log (2q)+{\displaystyle \frac{N}{q}}\log (2T)+\left({\displaystyle \frac{T}{q}}+1\right)q\log (2q)$

$\ll q\log (2qT)+{\displaystyle \frac{N}{q}}\log (2qT)+T\log (2qT).$

∎

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

$|S_N(\alpha )|$ $\ll U+(\log N)\left({\displaystyle \frac{N}{q}}+UV+q\right)\log (2qUV)$

$+N^{1/2}{(\log N)}^3\underset{U\le M\le N/V}{\max }{(M+({\displaystyle \frac{N}{q}}+{\displaystyle \frac{N}{M}}+q)\log (2qN/M))}^{1/2}$

$\ll U+{(\log 2qN)}^3\left({\displaystyle \frac{N}{q}}+UV+q\right)$

$+N^{1/2}{(\log qN)}^{7/2}\underset{U\le M\le N/V}{\max }{(M+{\displaystyle \frac{N}{q}}+{\displaystyle \frac{N}{M}}+q)}^{1/2}$

$\ll U+{(\log 2qN)}^3\left({\displaystyle \frac{N}{q}}+UV+q\right)$

$+N^{1/2}{(\log qN)}^{7/2}\left({\left(U+{\displaystyle \frac{N}{q}}+{\displaystyle \frac{N}{U}}+q\right)}^{1/2}+{\left({\displaystyle \frac{N}{V}}+{\displaystyle \frac{N}{q}}+V+q\right)}^{1/2}\right).$

Now take $U=V$, for which

$|S_N(\alpha )|$ $\ll U+{(\log 2qN)}^3\left({\displaystyle \frac{N}{q}}+U^2+q\right)$

$+N^{1/2}{(\log qN)}^{7/2}{\left(U+{\displaystyle \frac{N}{q}}+{\displaystyle \frac{N}{U}}+q\right)}^{1/2}$

$\ll U+{(\log 2qN)}^3\left({\displaystyle \frac{N}{q}}+U^2+q\right)$

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

$=U+{(\log 2qN)}^3\left({\displaystyle \frac{N}{q}}+U^2+q\right)$

$+{(\log qN)}^{7/2}(N^{1/2}{U}^{1/2}+N{q}^{-1/2}+N{U}^{-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 \mathrm{\in }\mathrm{R}$, $\mathrm{\left|}\alpha \mathrm{-}\frac{a}{q}\mathrm{\right|}\mathrm{\le }\frac{\mathrm{1}}{q^{\mathrm{2}}}$, $a\mathrm{\ge }\mathrm{1}$, $\gcd \mathit{}\mathrm{(}a\mathrm{,}q\mathrm{)}\mathrm{=}\mathrm{1}$, then for any $N\mathrm{\ge }\mathrm{1}$,

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