I am reading about 'Exponential Sums' in the book 'Analytic Number Theory' by Iwaniec and Kowalski. On page 199 they mention the bound:


$$|S\_f(N)|^2 \le N +2N^2q^{-1}+4(N+q)\log q \tag{1}$$


where, $\displaystyle S\_f(n) = \sum\limits\_{n=1}^{N} e^{2\pi i(\alpha n^2 +\beta n)}$ and $1 \le q \le 2N$ satisfies $\displaystyle 2\alpha = \frac{a}{q} + \frac{\theta}{2Nq}$,with $|\theta| < 1$ and $(a,q) = 1$.


I am having trouble following why $(1)$ along with the trivial bound $|S\_f(N)| \le N$ implies,


$$|S\_f(N)| \le 2Nq^{-1/2}+q^{1/2}\log q\tag{2}$$


How do we see the claim that $(2)$ is best possible?



> 
> "Is it possible to deduce (2) more directly, without much numerical work at small values?"
> 
> 
> 


Applying Vander Corput's Inequlity, we may derive:


$$|S\_f(N)|^2 \le \frac{N^2}{H}+\frac{N(2N-H)}{q}+4N\left(1+\frac{q}{H}\right)\log q$$


where, $1\le q < 2H$, and $H$ is an integer less than $N$ we are free to choose. Is there a way to proceed to $(2)$ from here?



Iwaniec-Kowalski Exponential Sum for Quadratic Function
Regarding your first question, observe that (2) is equivalent to
$$ |S\_f(N)|^2 \le 4N^2q^{-1}+4N\log q+q\log^2 q. $$
Hence, by (1), it suffices to show
$$ N +2N^2q^{-1}+4N\log q + 4q\log q \le 4N^2q^{-1}+4N\log q+q\log^2 q,$$
which in turn is equivalent to
$$ N+4q\log q \le 2N^2q^{-1}+q\log^2 q.$$
Here we have $N\leq 2N^2q^{-1}$ by $1\leq q\leq 2N$, hence we are done when $\log q\geq 4$. 


For $\log q<4$ we argue more carefully. In this case, we can rewrite the last inequality as
$$ (4-\log q)(q\log q)\leq 2N^2q^{-1}-N,$$
$$ 32\log q-8\log^2 q\leq 16N^2q^{-2}-8Nq^{-1},$$
$$ 1+32\log q-8\log^2 q\leq (4Nq^{-1}-1)^2,$$
$$ q\left\{1+\sqrt{1+32\log q-8\log^2 q}\right\}\leq 4N.$$
The left hand side is clearly at most $e^4(1+\sqrt{33})$, hence we are done if $N\geq 93$.


The remaining pairs $(N,q)$ satisfy $1\leq q\leq 2N\leq 184$, and the question reduces to whether
$$ \min(N^2,N +2N^2q^{-1}+4(N+q)\log q)\leq 4N^2q^{-1}+4N\log q+q\log^2 q$$
holds for these pairs or not. Equivalently, we need to test the inequality
$$ \min(N^2-4N\log q,N +2N^2q^{-1}+4q\log q)\leq 4N^2q^{-1}+q\log^2 q\tag{$\ast$}$$
for $1\leq q\leq 2N\leq 184$.


Regarding your second question, observe that the right hand side of (2) is about $\sqrt{N}\log N$ when $q=N$, while the bound needs to be at least $\sqrt{N}$ due to (8.12) in Iwaniec-Kowalski. In particular, when Iwaniec-Kowalski say that "slightly better results hold true for almost all coefficients", they mean that on average $\log N$ can be either omitted or replaced by $\sqrt{\log N}$. See also (8.13) and (8.14) in the book.


**Update 1.** Checking with SAGE, it turns out that $(\ast)$ fails for some pairs $(N,q)$, the smallest and largest such pairs being $(21,13)$ and $(41,44)$. This means that the proof of Theorem 8.1 in Iwaniec-Kowalski is incomplete, but it is fine for $N\geq 42$ (and also for $N\leq 20$).


**Update 2.** Replacing $4(N+q)\log q$ in (1) by its source (cf. p.199 in Iwaniec-Kowalski)
$$ 2(N+q)\Bigl(\sum\_{1\leq\ell\leq\frac{q}{2}}\ell^{-1}+\sum\_{1\leq\ell<\frac{q}{2}}\ell^{-1}\Bigr),$$
we get with SAGE that Theorem 8.1 holds for $N\geq 32$ (and also for $N\leq 23$).


**Update 3.** Here is a further improvement that proves Theorem 8.1 in the remaining cases. In (8.8) of Iwaniec-Kowalski, we can replace $2N$ by $2(N-\ell)$ in the light of the preceding display. Hence, in (1), we can replace $2N^2q^{-1}$ by $\sum\_{1\leq\ell'\leq N'}2(N-q\ell')$, where $N':=\lfloor N/q\rfloor$. This new sum equals 
$$\sum\_{1\leq\ell'\leq N'}2(N-q\ell')=2N'N-qN'(N'+1) < 2N'N-N'N = N'N \leq N^2q^{-1}.$$
Therefore, in (1), we can replace $2N^2q^{-1}$ by $N^2q^{-1}$, and then we get with SAGE that Theorem 8.1 holds without exception. It is worthwhile to note that the improvement in "Update 2" is also needed to reach this conclusion.


**P.S.** It is possible that with the improvements of (1) outlined above, one can reach (2) in a simpler way. I have not examined this possibility (for lack of time).


