To find a non-trivial bound for an expression is an essential task in analytic number theory. For example, to derive a asymptotic formula for the number of primes less than or equal to $x$, i.e. $\pi(x)$, we investigate into the function $\Psi(x) = \sum_{\substack{n \le x \\ n = p^k}} \log p.$ Along the way to the asymptotic formula for $\Psi(x)$, it’s important to bound the error terms so that they won’t overweight the dominant term. Nowadays, many mathematicians are interested in finding non-trivial bounds for weighted $\Psi(x)$, i.e., $\Psi(x) = \sum_{\substack{n \le x \\ n = p^k}} a_n \log p,$ where $a_n \in \C$. If $a_n = \chi(n)$ for some character $\chi \text{ mod }q$, this is actually $\Psi(x, \chi)$. Trivially, we can have $\left\lvert \Psi(x) \right\rvert \le \sum_{\substack{n \le x \\ n = p^k}} |a_n| \log p.$ Therefore, it seems that we can just work with $a_n \in \R_{\ge 0}$. Truly, this will give us a bound for $\Psi(x)$, but it ignores all the cancellation encoded in the signs of $a_n$, thus it won’t provide any good bounds.

Another kind of expressions that many mathematicians work with are those sums involving characters. The simplest example is $\displaystyle \sum_{n=m+1}^{m+N} \chi(n)$ for a character $\chi \text{ mod }q$. The trivial bound for it is $N$, since $|\chi(n)| \le 1$, which is certainly a coarse bound. Actually, we have

Theorem 1 (Pólga-Vinogradov inequality). Let $\chi \text{ mod }q$ be a primitive character and $q \ge 3$. Then $\left\lvert \sum_{n=m+1}^{m+N} \chi(n) \right\rvert < \sqrt{q}\log q.$

This non-trivial bound doesn’t depend on the length $N$ at all, but only depends on the modulus $q$. If the primitive condition is dropped, then it is bounded by $2 \sqrt{q}\log q$.

In this post, I will give a non-trivial bound for the sum $\displaystyle \sum_{n=1}^{N} \chi(n)\chi(n+1)$, which was originally asked by my friend Yongxiao, as a practice for my analytic number theory course.

$\renewcommand{\mod}{\ \mathrm{mod}\ #1}\newcommand{\abs}{\left\lvert#1\right\rvert}\newcommand{\e}{e\left(#1\right)}\newcommand{\inner}{\left\langle #1 \, , \, #2\right\rangle}$

Theorem 2.Let $\chi \mod q$ be a primitive character and $q \ge 3$. Then $\begin{equation*} \abs{\sum_{n=1}^{N} \chi(n)\chi(n+1)} < \frac{N}{\sqrt{q}} + q^2. \end{equation*}$

Proof. Since $\chi \mod q$ is primitive, for any $n$, $\chi(n) = \frac{1}{\tau(\overline{\chi})} \sum_{a \mod q} \overline{\chi}(a)\e{\frac{an}{q}},$ where $\e{x}=e^{2\pi ix}$. Therefore, $\begin{equation} \begin{split} &\sum_{n=1}^{N} \chi(n)\chi(n+1) \\ &= \sum_{n=1}^{N} \frac{1}{\tau(\overline{\chi})^2} \sum_{a \mod q}\sum_{b \mod q} \overline{\chi}(a)\overline{\chi}(b)\e{\frac{an}{q}}\e{\frac{bn+b}{q}} \\ &= \frac{1}{\tau(\overline{\chi})^2} \sum_{a, b} \overline{\chi}(a)\overline{\chi}(b)\e{\frac{b}{q}} \sum_{n=1}^{N} \e{\frac{(a+b)n}{q}} \\ &= \frac{N}{\tau(\overline{\chi})^2} \sum_{\substack{a, b\\q \mid a+b}} \overline{\chi}(a)\overline{\chi}(b)\e{\frac{b}{q}} \\ &\;\;\;\;+ \frac{1}{\tau(\overline{\chi})^2} \sum_{\substack{a, b\\q \nmid a+b}} \overline{\chi}(a)\overline{\chi}(b)\e{\frac{b}{q}} \sum_{n=1}^{N} \e{\frac{(a+b)n}{q}} \\ &= \frac{N\overline{\chi}(-1)}{\tau(\overline{\chi})^2} \sum_{b} \overline{\chi}^2(b)\e{\frac{b}{q}} \\ &\;\;\;\;+ \frac{1}{\tau(\overline{\chi})^2} \sum_{\substack{a, b\\q \nmid a+b}} \overline{\chi}(a)\overline{\chi}(b)\e{\frac{b}{q}} \sum_{n=1}^{N} \e{\frac{(a+b)n}{q}}. \end{split} \label{20150511-1} \end{equation}$

Consider the Fourier transform on $\Z/q\Z$ under the inner product $\inner{f}{g} = \frac{1}{q} \sum_{n \mod q}f(n)\overline{g(n)},$ where $f$ and $g$ are in $L^2\left(\Z/q\Z\right)$, the space of functions on $\Z/q\Z$. Note that, $\left\{\e{\frac{a-}{q}}: a \in \Z/q\Z \right\}$ is a orthonormal basis of $L^2\left(\Z/q\Z\right)$, so we can write $\overline{\chi}^2(n) = \sum_{a \mod q} \inner{\overline{\chi}^2}{\e{\frac{a-}{q}}} \e{\frac{an}{q}}.$ By Plancherel theorem, $\begin{equation} \inner{\overline{\chi}^2}{\overline{\chi}^2} = \sum_{a \mod q} \abs{\inner{\overline{\chi}^2}{\e{\frac{a-}{q}}}}^2. \label{20150511-2} \end{equation}$

If $(a, q)=1$, then with a change of variable, we can have $\inner{\overline{\chi}^2}{\e{\frac{a-}{q}}} = \chi^2(a)\inner{\overline{\chi}^2}{\e{\frac{-}{q}}}.$ On the other hand, $\inner{\overline{\chi}^2}{\overline{\chi}^2} = \frac{1}{q} \sum_{n \mod q}\overline{\chi}^2(n)\chi^2(n) = \frac{\varphi(q)}{q},$ where $\varphi$ is the Euler function. Hence, from $\eqref{20150511-2}$, $\varphi(q)\abs{\inner{\overline{\chi}^2}{\e{\frac{-}{q}}}}^2 \le \frac{\varphi(q)}{q},$ or $\abs{\inner{\overline{\chi}^2}{\e{\frac{-}{q}}}} \le \frac{1}{\sqrt{q}}.$ Therefore, $\begin{equation} \abs{\sum_{b \mod q} \overline{\chi}^2(b)\e{\frac{b}{q}}} = q\abs{\inner{\overline{\chi}^2}{\e{\frac{-}{q}}}} \le \sqrt{q}. \label{20150511-3} \end{equation}$

Since $\begin{equation*} \begin{split} \sum_{n=1}^{N} \e{\frac{(a+b)n}{q}} &= \e{\frac{a+b}{q}}\frac{\e{\frac{(a+b)N}{q}}-1}{\e{\frac{a+b}{q}}-1} \\ &= \e{\frac{a+b}{2q}}\e{\frac{(a+b)N}{2q}}\frac{\sin \frac{(a+b)N\pi}{q}}{\sin \frac{(a+b)\pi}{q}} \end{split} \end{equation*}$ Therefore, $\begin{equation} \begin{split} &\abs{\sum_{\substack{a, b\\q \nmid a+b}} \overline{\chi}(a)\overline{\chi}(b)\e{\frac{b}{q}} \sum_{n=1}^{N} \e{\frac{(a+b)n}{q}}} \\ &= \abs{\sum_{\substack{a, b\\q \nmid a+b}} \overline{\chi}(a)\overline{\chi}(b)\e{\frac{b}{q}} \e{\frac{a+b}{2q}}\e{\frac{(a+b)N}{2q}}\frac{\sin \frac{(a+b)N\pi}{q}}{\sin \frac{(a+b)\pi}{q}}} \\ &\le \sum_{\substack{a, b \mod q\\q \nmid a+b}} \frac{1}{\abs{\sin \frac{(a+b)\pi}{q}}} = \sum_{\substack{0 < \abs{a} < q/2 \\ 0 < \abs{b} < q/2 \\ 0 < a+b < q}} \frac{2}{\abs{\sin \frac{(a+b)\pi}{q}}} \\ &= \sum_{\substack{0 < \abs{a} < q/2 \\ 0 < \abs{b} < q/2 \\ 0 < a+b \le q/2}} \frac{2}{\abs{\sin \frac{(a+b)\pi}{q}}} + \sum_{\substack{0 < \abs{a} < q/2 \\ 0 < \abs{b} < q/2 \\ q/2 < a+b < q}} \frac{2}{\abs{\sin \left(\pi - \frac{(a+b)\pi}{q}\right)}} \\ & < \sum_{\substack{0 < \abs{a} < q/2 \\ 0 < \abs{b} < q/2 \\ 0 < a+b \le q/2}} \frac{2}{\frac{2(a+b)\pi}{\pi q}} + \sum_{\substack{0 < \abs{a} < q/2 \\ 0 < \abs{b} < q/2 \\ q/2 < a+b < q}} \frac{2}{\frac{2}{\pi}\left(\pi - \frac{(a+b)\pi}{q}\right)} \\ &= \sum_{\substack{0 < \abs{a} < q/2 \\ 0 < \abs{b} < q/2 \\ 0 < a+b \le q/2}} \frac{q}{a+b} + \sum_{\substack{0 < \abs{a} < q/2 \\ 0 < \abs{b} < q/2 \\ q/2 < a+b < q}} \frac{q}{q-(a+b)} \\ &= \sum_{t = 2}^{[q/2]} \frac{q(t-1)}{t} + \sum_{t=2}^{[q/2]} \frac{q(t-1)}{t} < q^2. \end{split} \label{20150511-4} \end{equation}$

By $\eqref{20150511-1}$, $\eqref{20150511-3}$ and $\eqref{20150511-4}$, we conclude the theorem. $\square$

Remark. The proof above doesn’t depend on the interval of summation, so we can change the summation from $\displaystyle \sum_{n = 1}^{N}$ to $\displaystyle \sum_{n = m+1}^{m + N}$. Also, we can substitute $\chi(n+1)$ by $\chi(n+s)$ as long as $(q, s) = 1$. A similar proof with only slight changes can work out this case. To sum up, we have

Theorem 3.Let $\chi \mod q$ be a primitive character and $q \ge 3$. Let $s \in \N$ be such that $(q, s)=1$ and let $m \in \N$. Then $\begin{equation*} \abs{\sum_{n=m+1}^{m+N} \chi(n)\chi(n+s)} < \frac{N}{\sqrt{q}} + q^2. \end{equation*}$

I have to admit that this bound is also not that good though it’s non-trivial. If we let $\frac{N}{\sqrt{q}} = q^2$, we get the best possible bound $2N^{\frac{4}{5}}$.