# Advanced Number Theory Note #14: An inequality due to Pólya for the partial sums of primitive Dirichlet characters

The mathematician George Pólya, author of the famous book How to Solve it, found an inequality for sums of primitive Dirichlet characters which involves a number of key ideas relating to periodic arithmetical functions and Gauss sums. The inequality says that if $\chi$ is any primitive character mod $k$, then for all $x \geq 1$ we have

$\bigg| \sum_{m \leq x} \chi(m) \bigg| < \sqrt{k} \log k$

In this note I want to carefully go through the (rather tricky) proof of this inequality, using this as an opportunity to bring together a variety of ideas which have appeared in my last few blog posts on advanced number theory.

Looking back through my notes, a key theme that jumps out is that interesting things happen when we consider sums of (complex) roots of unity. To start with, the Möbius function $\mu(k)$ can be obtained as a sum of the primitive $k$th roots of unity:

$\mu(k) = \sum_{\substack{1 \le a \le k \\ gcd(a,k)=1}} e^{2\pi ia/k}$

I discussed this in detail in Advanced Number Theory Note #10. A generalisation of this is Ramanujan’s sum, which for some fixed integer $n$ is the sum of the $n$th powers of the primitive roots of unity:

$c_k(n) = \sum_{\substack{m\hspace{1 mm} mod \hspace{1 mm}k \\ gcd(m, k)=1}} e^{2\pi imn/k}$

I discussed Ramanujan’s sum in Advanced Number Theory Note #11 (also see references therein). Ramanujan’s sum reduces to the Möbius function when $n = 1$:

$\mu(k) = c_k(1)$

A further generalisation is the Gauss sum associated with a Dirichlet character $\chi$ mod $k$:

$G(n. k) = \sum_{m=1}^k \chi(m) e^{2 \pi imn/k}$

I discussed Gauss sums in detail in Advanced Number Theory Note #12. The Gauss sum reduces to Ramanujan’s sum when the Dirichlet character appearing in the sum is the principal character mod $k$, i.e.,

$G(n, \chi_1) = \sum_{\substack{m\hspace{1 mm} mod \hspace{1 mm}k \\ gcd(m, k)=1}} e^{2\pi imn/k} = c_k(n)$

Consideration of the separability of Gauss sums leads to the concepts of induced moduli and primitive Dirichlet characters which I discussed in detail in Advanced Number Theory Note #13. Key results here are that if $\chi$ is a primitive Dirichlet character mod $k$ then $G(n, \chi)$ is separable for every $n$, that is,

$G(n, \chi) = \overline{\chi}(n) G(1, \chi)$

for every $n$, and furthermore

$|G(1, \chi)|^2 = k$

All of these sums are periodic mod $k$ and another key idea in my previous notes is that every arithmetical function $f$ which is periodic mod $k$, that is, which is such that

$f(n + k) = f(n)$

has a finite Fourier expansion expressed as a linear combination of nth powers of kth roots of unity. I discussed this in detail in Advanced Number Theory Note #9. The key result in that note is Theorem 4 which says that $f$ can be written as

$f(m) = \sum_{n \hspace{1 mm} mod \hspace{1 mm} k}g(n) e^{2\pi imn/k}$

where $g$ is a uniquely determined arithmetical function which is also periodic mod $k$ and which is given by the formula

$g(n) = \frac{1}{k}\sum_{m \hspace{1 mm} mod \hspace{1 mm} k}f(m) e^{-2\pi imn/k}$

(the summations can be extended over any complete residue system mod $k$).

Turning now to the proof of Pólya’s inequality, we begin by noting that since any Dirichlet character $\chi$ mod $k$ is periodic mod $k$, it has a finite Fourier expansion of the form

$\chi(m) = \sum_{n=1}^k a_k(n) e^{2 \pi i mn/k}$

where the coefficients $a_k(n)$ are given by the formula

$a_k(n) = \frac{1}{k} \sum_{m=1}^k \chi(m) e^{-2 \pi i mn/k} = \frac{1}{k} G(-n, \chi)$

(the last equality follows from the definition of a Gauss sum). Now assume that $\chi$ is primitive. Then $G(-n, \chi)$ is separable for every $n$ so we have

$G(-n, \chi) = \overline{\chi}(-n) G(1, \chi)$

and the expression for $a_k(n)$ above can be written

$a_k(n) = \frac{G(1, \chi)}{k} \overline{\chi}(-n)$

Therefore the expression for the finite Fourier expansion of $\chi(m)$ above can be written as

$\chi(m) = \sum_{n=1}^k a_k(n) e^{2 \pi i mn/k} = \frac{G(1, \chi)}{k} \sum_{n=1}^k \overline{\chi}(-n) e^{2 \pi i mn/k} = \frac{G(1, \chi)}{k} \sum_{n=1}^k \overline{\chi}(n) e^{-2 \pi i mn/k}$

(The last equality can be justified on the basis that if $gcd(a, k) = 1$ we can replace the index of summation $n$ by $an$ to get $\sum_{n=1}^k \overline{\chi}(-an) e^{2 \pi i anm/k}$. When $a = -1$ we get the last expression on the right hand side).

What we have shown is that the finite Fourier expansion of a primitive Dirichlet character $\chi$ mod $k$ has the form

$\chi(m) = \frac{\tau_k(\chi)}{\sqrt{k}}\sum_{n=1}^k \overline{\chi}(n) e^{-2 \pi i mn/k}$

where

$\tau_k(\chi) = \frac{G(1, \chi)}{\sqrt{k}}$

The numbers $\tau_k(\chi)$ have absolute value $1$ by virtue of the fact noted above that for a separable Gauss sum we have $|G(1, \chi)|^2 = k$.

Summing the finite Fourier expansion for $\chi(m)$ over all $m \leq x$ we get

$\sum_{m \leq x} \chi(m) = \frac{\tau_k(\chi)}{\sqrt{k}}\sum_{n=1}^{k-1} \overline{\chi}(n) \sum_{m \leq x} e^{-2 \pi i mn/k}$

(The upper limit of the first summation on the right hand side can be taken to be $k-1$ rather than $k$ since for any Dirichlet character we have $\chi(k) = 0$).

Taking absolute values and multiplying through by $\sqrt{k}$ we get

$\sqrt{k} \bigg| \sum_{m \leq x} \chi(m) \bigg| \leq \sum_{n=1}^{k-1} \bigg| \sum_{m \leq x} e^{-2 \pi i mn/k} \bigg| \equiv \sum_{n=1}^{k-1} |f(n)|$

where

$f(n) \equiv \sum_{m \leq x} e^{-2 \pi i mn/k}$

(Note that the Dirichlet characters disappear upon taking absolute values because being $k$-th roots of unity they all lie on the unit circle and therefore have absolute value equal to $1$).

We now make use of the observation that

$f(k - n) = \sum_{m \leq x} e^{-2 \pi i m(k - n)/k} = \sum_{m \leq x} e^{-2 \pi i m} \cdot e^{2 \pi i mn/k}$

$= \sum_{m \leq x} e^{2 \pi i mn/k} = \overline{f(n)}$

and thus

$|f(k - n)| = |f(n)|$

To clarify the implications of this, consider some specific values for $k$. Suppose $k = 9$, an odd number. Then we have

$\sum_{n=1}^{k-1} |f(n)| = \sum_{n=1}^{8} |f(n)|$

$= |f(1)| + |f(2)| + |f(3)| + |f(4)| + |f(5)| + |f(6)| + |f(7)| + |f(8)|$

but since $|f(k - n)| = |f(n)|$ we have

$|f(8)| = |f(1)|$

$|f(7)| = |f(2)|$

$|f(6)| = |f(3)|$

$|f(5)| = |f(4)|$

Therefore when $k = 9$ we get

$\sum_{n=1}^{k-1} |f(n)| = \sum_{n=1}^{8} |f(n)| = 2 \sum_{n < 9/2} |f(n)|$

Now consider the case when $k$ is an even number, say $k = 10$. We then have

$\sum_{n=1}^{k-1} |f(n)| = \sum_{n=1}^{9} |f(n)|$

$= |f(1)| + |f(2)| + |f(3)| + |f(4)| + |f(5)| + |f(6)| + |f(7)| + |f(8)| + f(9)$

$= 2(|f(1)| + |f(2)| + |f(3)| + |f(4)|) + |f(5)|$

$= 2 \sum_{n < 10/2} |f(n)| + \big| f\big( \frac{10}{2} \big) \big|$

In general, then, we have

$\sum_{n=1}^{k-1} |f(n)| = 2 \sum_{n < k/2} |f(n)| + \big| f\big( \frac{k}{2} \big) \big|$

where the last term on the right appears only if $k$ is even.

Going back to our previous expression involving the finite Fourier expansion for $\chi(m)$ we can now write

$\sqrt{k} \bigg| \sum_{m \leq x} \chi(m) \bigg| \leq \sum_{n=1}^{k-1} \bigg| \sum_{m \leq x} e^{-2 \pi i mn/k} \bigg| \equiv \sum_{n=1}^{k-1} |f(n)|$

$= 2 \sum_{n < k/2} |f(n)| + \big| f\big( \frac{k}{2} \big) \big|$

We now make further progress by observing that $f(n)$ is in fact the sum of a geometric sequence:

$f(n) = \sum_{m=1}^r y^m = \frac{y^{r+1} - y}{y - 1} = y \frac{y^r - 1}{y - 1}$

where $r = [x]$. Writing $z = e^{- \pi i n/k}$, we have $y = z^2$ and thus

$f(n) = y \frac{y^r - 1}{y - 1} = z^2 \frac{z^{2r} - 1}{z^2 - 1}$

$= \frac{z^{2(r+1)} - z^2}{z^2 - 1}$

$= z^{r+1}\frac{z^{r+1} - z^{2- r - 1}}{z^2 - 1}$

$= z^{r+1}\frac{z^{r+1} - z^{1 - r}}{z^2 - 1}$

$= z^{r+1}\frac{z^r - z^{-r}}{z - z^{-1}}$

Now taking absolute values we obtain

$|f(n)| = \big| \frac{z^r - z^{-r}}{z - z^{-1}} \big|$

$= \frac{\big| \sin \frac{\pi r n}{k} \big|}{\big| \sin \frac{\pi n}{k} \big|}$

$\leq \frac{1}{\sin \frac{\pi n}{k}}$

where I have used the fact that

$\sin x = \frac{e^{ix} - e^{-ix}}{2i}$

Now we use the inequality

$\sin t \geq \frac{2}{\pi} t$

which is valid for $0 \leq t \leq \pi/2$ (as can easily be seen using a sketch). Using this with $t = \pi n/k$ we get

$|f(n)| \leq \frac{1}{\frac{2}{\pi}\frac{\pi n}{k}} = \frac{k}{2n}$

Going back to our previous expression involving the finite Fourier expansion for $\chi(m)$ we can now write

$\sqrt{k} \bigg| \sum_{m \leq x} \chi(m) \bigg| \leq \sum_{n=1}^{k-1} \bigg| \sum_{m \leq x} e^{-2 \pi i mn/k} \bigg| \equiv \sum_{n=1}^{k-1} |f(n)|$

$= 2 \sum_{n < k/2} |f(n)| + \big| f\big( \frac{k}{2} \big) \big|$

$\leq 2 \sum_{n < k/2} \frac{k}{2n} + \big| f\big( \frac{k}{2} \big) \big|$

$\leq k \sum_{n < k/2} \frac{1}{n} + 1$

(since $|f(k/2)| \leq 1$)

$= k \bigg \{\sum_{n < k/2} \frac{1}{n} + \frac{1}{k} \bigg \}$

$< k \sum_{n \leq k} \frac{1}{n}$

$< k \int_1^k \frac{1}{n} dn$

$= k \log k$

Pólya’s inequality now follows upon dividing through by $\sqrt{k}$.