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?

  • $\begingroup$ You mean a book "Analytic Number Theory"? $\endgroup$ – Sergei Jun 10 '15 at 4:56
  • 2
    $\begingroup$ By improving slightly the second and third terms in (1), I was able to deduce (2) in all cases. See Updates 2 and 3 in my response. In short, Theorem 8.1 in Iwaniec-Kowalski is fine, but some more careful estimates are needed for small $q$ and $N$. $\endgroup$ – GH from MO Jun 10 '15 at 15:32
  • $\begingroup$ @GHfromMO Thanks!!! I am surprised that the authors left out a proof which needed careful and meticulous details! $\endgroup$ – r9m Jun 10 '15 at 15:35
  • 3
    $\begingroup$ @r9m: The edit is fine. Wait a few days and see if you get a more direct argument. If not, then you can open a new question, referring to this post and focusing on (2) only. Note, on the other hand, that the precise constants or the possible extra $O(1)$ terms are irrelevant in this theorem. The authors wanted to give a very explicit result, but this is of no importance, really. $\endgroup$ – GH from MO Jun 11 '15 at 1:15
  • 1
    $\begingroup$ I see you put a bounty on your question. As my response makes it clear that (1) and the trivial estimate alone are insufficient to imply (2), you should phrase the question more carefully. For example: "Is it possible to deduce (2) more directly, without much numerical work at small values?" $\endgroup$ – GH from MO Jun 12 '15 at 15:31

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

  • 1
    $\begingroup$ I have a doubt .. in the case $\log q < 4$, you are making the claim 'It suffices to show $|S_f(N)| \le 2Nq^{-1/2}(1+\log q)$' but $2Nq^{-1/2}(1+\log q) \ge 2Nq^{-1/2} + q^{1/2}\log q$. So that proves a weaker bound. $\endgroup$ – r9m Jun 10 '15 at 9:35
  • $\begingroup$ @r9m: You are right, I have been up for too long. Let me try to fix it (or sleep on it). $\endgroup$ – GH from MO Jun 10 '15 at 10:04
  • 1
    $\begingroup$ @r9m: I updated the argument. It seems that the argument of Iwaniec-Kowalski is incomplete, and perhaps the statement also fails for some pairs $(N,q)$. On the other hand, the number of exceptional pairs is finite as I explain in my post. $\endgroup$ – GH from MO Jun 10 '15 at 12:37
  • $\begingroup$ The authors didn't bother to prove the result (or left it out for some other reason). So I was expecting a proof using the theory developed in the preceding section of Thm 8.1. Many thanks again! :-) $\endgroup$ – r9m Jun 10 '15 at 12:43
  • 3
    $\begingroup$ @r9m: Well, in practice finitely many exceptions is not a problem. For example, adding the constant $100$ to the right hand side fixes Theorem 8.1. Note also that your (1) is already a consequence of a (slightly) sharper inequality. So there is definitely room for improvement. $\endgroup$ – GH from MO Jun 10 '15 at 13:02

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

enter image description here

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.