Exercise 6.15

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Show that
$$ \left|\sum_{t = n}^m \legendre{t}{p}ight| < \sqrt{p}\log p.$$
The inequality holds for the sum over any range.

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow} \def\gcro{\mbox{[\hspace{-.15em}[}} \def\dcro{\mbox{]\hspace{-.15em}]}} ewcommand{\D}{\mathrm{d}} ewcommand{\Q}{\mathbb{Q}} ewcommand{\Z}{\mathbb{Z}} ewcommand{\N}{\mathbb{N}} ewcommand{\R}{\mathbb{R}} ewcommand{\C}{\mathbb{C}} ewcommand{\F}{\mathbb{F}} ewcommand{ e}{\,\mathrm{Re}\,} ewcommand{\ord}{\mathrm{ord}} ewcommand{ }{\mathrm{N}} ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}} {\bf Lemma.} If $0\leq x \leq \frac{\pi}{2}, \sin x \geq \frac{2}{\pi} x$. \begin{proof} As $-\sin$ is a convex function on $[0,\pi/2]$, the graph of $\sin$ is above any chord, and the chord between the points $(0,0)$ and $(\pi/2,1)$ has equation $y = (2/\pi) x$, we conclude that $\sin x \geq \frac{2}{\pi} x$ for $0\leq x \leq \pi/2$. \end{proof} \begin{proof} Let $S = \sum\limits_{t = n}^m \legendre{t}{p} g$ with $n\leq m$. Then $\vert S \vert = \sqrt{p} \left|\sum\limits_{t = n}^m \legendre{t}{p} ight|$. As $(t/p)g = g_t$, \begin{align*} S&= \sum _{t=m}^n g_t\ &=\sum _{t=m}^n \sum_{s=0}^{p-1}\legendre{s}{p} \zeta^{ts}\ &=\sum_{s=0}^{p-1} \legendre{s}{p} \zeta^{ms} \sum _{t=m}^n \zeta^{(t-m)s}\ &=\sum_{s=0}^{p-1} \legendre{s}{p} \zeta^{ms} \sum _{u=0}^{n-m} \zeta^{us} \qquad( u=t-m)\ &=\sum_{s=1}^{p-1} \legendre{s}{p} \zeta^{ms} \frac{\zeta^{(n-m+1)s}-1}{\zeta^s-1}\ \end{align*} (since for $s=0$, the sum $\sum _{u=0}^{n-m} \zeta^{us} = n-m+1$ and $\legendre{s}{p} = 0$). So \begin{align*} S &= \sum_{s=1}^{p-1} \legendre{s}{p} \frac{\zeta^{(n+1)s}-\zeta^{ms}}{\zeta^s-1}\ &=\sum_{s=1}^{p-1} \legendre{s}{p} \frac{\zeta^{\frac{n+m+1}{2} s}}{\zeta^{\frac{s}{2}}} \ \frac{\zeta^{\frac{n-m+1}{2} s}-\zeta^{\frac{-n+m-1}{2} s}}{\zeta^{\frac{s}{2}}-\zeta^{\frac{-s}{2}}}\ &= \sum_{s=1}^{p-1} \legendre{s}{p}\zeta^{\frac{n+m}{2} s} \ \frac{\sin \left((n-m+1)s \frac{\pi}{p} ight)} { \sin \left(s \frac{\pi}{p} ight) } \end{align*} As $\sin(x) \geq \frac{2}{\pi} x$ for $x \in [0,\frac{\pi}{2}]$, for all $s$, $1\leq s <\frac{p}{2}$, $0 \leq \frac{s \pi}{p} \leq \frac{\pi}{2} $, so $$\left| \frac{\sin \left((n-m+1)s \frac{\pi}{p} ight)} { \sin \left(s \frac{\pi}{p} ight)} ight | \leq \frac{1}{\frac{2}{\pi} \left(s\frac{\pi}{p} ight)} = \frac{p}{2s}\qquad (s = 1,2,\ldots,(p-1)/2).$$ Since $\legendre{s}{p} \zeta^{ts}$ depends only of the class of $s$, we can replace in the preceding calculation the values $s = 1,2,\ldots,p-1$ by $s=-(p-1)/2,\ldots, -1,1,\ldots,(p-1)/2$, so $$S = \sum_{s=1}^{(p-1)/2}\legendre{s}{p}\zeta^{\frac{n+m}{2} s} \ \frac{\sin \left((n-m+1)s \frac{\pi}{p} ight)} { \sin \left(s \frac{\pi}{p} ight) } +\sum_{s=-(p-1)/2}^{-1} \legendre{s}{p}\zeta^{\frac{n+m}{2} s} \ \frac{\sin \left((n-m+1)s \frac{\pi}{p} ight)} { \sin \left(s \frac{\pi}{p} ight) }.$$ As $\sin$ is an odd function, $$S = \sum_{s=1}^{(p-1)/2}\legendre{s}{p}\zeta^{\frac{n+m}{2} s} \ \frac{\sin \left((n-m+1)s \frac{\pi}{p} ight)} { \sin \left(s \frac{\pi}{p} ight) } +\sum_{s=1}^{(p-1)/2} \legendre{-s}{p}\zeta^{-\frac{n+m}{2} s} \ \frac{\sin \left((n-m+1)s \frac{\pi}{p} ight)} { \sin \left(s \frac{\pi}{p} ight) }.$$ Thus $$\vert S \vert \leq 2 \sum_{s=1}^{(p-1)/2}\frac{p}{2s} = p\sum_{s=1}^{(p-1)/2} \frac{1}{s}.$$ As $S = \sum\limits_{t = n}^m \legendre{t}{p} g$ and $|g| = \sqrt{p}$, $$ \left|\sum_{t = n}^m \legendre{t}{p} ight| \leq \sqrt{p} \sum_{s=1}^{(p-1)/2} \frac{1}{s}.$$ It remains to do a sufficient estimation of the harmonic sum. We prove by induction that for all $n \geq 1$, $$1+\frac{1}{2}+\cdots+\frac{1}{n} \leq \log(2n+1).$$ As $1 \leq \log(3)$, this proposition is true for $n=1$. Suppose that is it true for $n-1$ : $$1+\frac{1}{2}+\cdots+\frac{1}{n-1} \leq \log(2n-1).$$ Then $$1+\frac{1}{2}+\cdots+\frac{1}{n} \leq \frac{1}{n} + \log(2n-1).$$ If we prove that $\frac{1}{n} + \log(2n-1) \leq \log(2n+1)$, the induction is done. Let $u(x) = \log(2x+1) - \log(2x-1) - \frac{1}{x}, x > \frac{1}{2}$. \begin{align*} u'(x) &= \frac{2}{2x+1} - \frac{2}{2x-1} +\frac{1}{x^2}\ &=\frac{-4}{4x^2-1} + \frac{1}{x^2}\ &= \frac{-1}{(4x^2-1)x^2} <0 \end{align*} As $u(x) = \log\left(\frac{2x+1}{2x-1} ight) - \frac{1}{x}$, $ \lim\limits_{x o +\infty} u(x) =0$. Moreover $u$ is a decreasing function, so for all $x>1/2, u(x)>0$, and for all $n\in \N, n\geq 1$, $$\frac{1}{n} + \log(2n-1) \leq \log(2n+1).$$ We have proved by induction that for all $n\geq 1$, $$1+\frac{1}{2}+\cdots+\frac{1}{n} \leq \log(2n+1).$$ If $n = (p-1)/2$, where $p$ is an odd prime ($p\geq 3$), $$\sum_{s=1}^{(p-1)/2} \frac{1}{s} \leq \log p.$$ Conclusion: $$ \left|\sum_{t = n}^m \legendre{t}{p} ight| < \sqrt{p}\log p.$$ \end{proof}

Exercise 6.15

Answers

Comments

Exercise 6.15

Answers

Comments

Add answer