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}[1]{\ \mathrm{mod}\ #1}\newcommand{\abs}[1]{\left\lvert#1\right\rvert}\newcommand{\e}[1]{e\left(#1\right)}\newcommand{\inner}[2]{\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}}\).

analytic number theory character