Iwaniec-Kowalski Exponential Sum for Quadratic Function

Question

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?

Answer 1

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

Answer 2

If $\log(q)\ge4$, then the fact that $N\le2N^2q^{-1}$ and $4q\log(q)\le q\log(q)^2$ show that $$ N+2N^2q^{-1}+4(N+q)\log(q)\le\overbrace{4N^2q^{-1}+q\log(q)^2+4N\log(q)}^{\left(2Nq^{-1/2}+q^{1/2}\log(q)\right)^2} $$ This shows that $(1)\implies(2)$.

---

If $q\le4$, then $$ N^2\le4N^2q^{-1}+q\log(q)^2+4N\log(q) $$ This and $|S_f(N)|\le N$ also verifies $(2)$.

---

Therefore, we need to consider $$ 4\lt q\lt e^4 $$ Consider $$ N^2\gt4N^2q^{-1}+q\log(q)^2+4N\log(q) $$ which is only true for $$ N\gt\frac{q\log(q)}{\sqrt{q}-2} $$ and $$ N+2N^2q^{-1}+4(N+q)\log(q) \gt4N^2q^{-1}+q\log(q)^2+4N\log(q) $$ which is only true for $$ N\lt\frac q4\left(1+\sqrt{1+32\log(q)-8\log(q)^2}\right) $$ Unfortunately, between $q\doteq12.592$ and $q\doteq48.802$ the bounds on $N$ above permit some common values of $N$.

The convex blue curve is $\frac{q\log(q)}{\sqrt{q}-2}$ and the concave red curve is $\frac q4\left(1+\sqrt{1+32\log(q)-8\log(q)^2}\right)$. The area above the blue curve and below the red curve is where the problem lies.

For example, at $q=30$ and $N=32$, we have $$ \begin{align} N^2&=1024\\ N+2N^2q^{-1}+4(N+q)\log(q)&=943.764\\ 4N^2q^{-1}+q\log(q)^2+4N\log(q)&=918.931 \end{align} $$ Thus, it doesn't seem that the third bound, $(2)$, can be derived from the first bound, (1), and the trivial bound. This doesn't mean that $(2)$ is not valid, just that is does not seem to follow from the other bounds.