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 is any primitive character mod , then for all we have

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 can be obtained as a sum of the primitive th roots of unity:

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

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 :

A further generalisation is the Gauss sum associated with a Dirichlet character mod :

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 , i.e.,

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 is a primitive Dirichlet character mod then is separable for every , that is,

for every , and furthermore

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

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 can be written as

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

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

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

where the coefficients are given by the formula

(the last equality follows from the definition of a Gauss sum). Now assume that is primitive. Then is separable for every so we have

and the expression for above can be written

Therefore the expression for the finite Fourier expansion of above can be written as

(The last equality can be justified on the basis that if we can replace the index of summation by to get . When 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 mod has the form

where

The numbers have absolute value by virtue of the fact noted above that for a separable Gauss sum we have .

Summing the finite Fourier expansion for over all we get

(The upper limit of the first summation on the right hand side can be taken to be rather than since for any Dirichlet character we have ).

Taking absolute values and multiplying through by we get

where

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

We now make use of the observation that

and thus

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

but since we have

Therefore when we get

Now consider the case when is an even number, say . We then have

In general, then, we have

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

Going back to our previous expression involving the finite Fourier expansion for we can now write

We now make further progress by observing that is in fact the sum of a geometric sequence:

where . Writing , we have and thus

Now taking absolute values we obtain

where I have used the fact that

Now we use the inequality

which is valid for (as can easily be seen using a sketch). Using this with we get

Going back to our previous expression involving the finite Fourier expansion for we can now write

(since )

Pólya’s inequality now follows upon dividing through by .