Characters

1. Additive characters

If f(z) = ∑_{n=0}^{∞} c_{n}z^{n} is a power series, we can restrict our attention to terms for which n has prescribed parity by considering

\frac{1}{2}f(z) + \frac{1}{2}f(−z) = ∑_{\begin{matrix}n=0 \\ n≡0 (2) \end{matrix}}^{∞} c_{n}z^{n}

or

\frac{1}{2}f(z) − \frac{1}{2}f(−z) = ∑_{\begin{matrix}n=0 \\ n≡1 (2) \end{matrix}}^{∞} c_{n}z^{n}.

That is, we can express the characteristic function of an arithmetic progression (mod 2) as a linear combination \frac{1}{2}1^{n} ± \frac{1}{2}(−1)^{n} of 1^{n} and (−1)^{n}. Here 1 and −1 are the square-roots of 1, and we can similarly express the characteristic function of an arithmetic progression (mod q) as a linear combination of the sequences ζ^{n} where ζ runs over the q different q^{th} roots of unity. We write e(θ) = e^{2πiθ}, and then the q^{th} roots of unity are the numbers ζ = e(a/q) for 1 ≤ a ≤ q. If (a, q) = 1 then the least integer n such that ζ^{n} = 1 is q, and we say that ζ is a primitive q^{th} root of unity. From the formula

∑_{k=0}^{q−1} ζ^{k} = \frac{1 − ζ^{q}}{1 − ζ}

for the sum of a geometric progression, we see that if ζ is a q^{th} root of unity then

∑_{k=1}^{q} ζ^{k} = 0

unless ζ = 1. Hence

(1)  \frac{1}{q} ∑_{k=1}^{q} e(−ka/q)e(kn/q) = \{ \begin{matrix}1 & if n ≡ a (mod q), \\ 0 & otherwise, \end{matrix}

and thus the characteristic function of an arithmetic progression (mod q) can be expressed as a linear combination of the sequences e(kn/q). These functions are called the additive characters (mod q) because they are the homomorphisms from the additive group (ℤ/qℤ)^{+} of integers (mod q) to the multiplicative group ℂ^{×} of non-zero complex numbers.

In the language of linear algebra we see that the arithmetic functions of period q form a vector space of dimension q. For any k, 1 ≤ k ≤ q, the sequence {e(kn/q)}_{n=−∞}^{∞} has period q, and these q sequences form a basis for the space of q-periodic arithmetic functions. Indeed, the formula (1) expresses the a^{th} elementary vector as a linear combination of the vectors [e(n/q), e(2n/q), …, e((q − 1)n/q), 1].

If f(n) is an arithmetic function with period q then we define the finite Fourier transform of f to be the function

(2)  f̂(k) = \frac{1}{q} ∑_{n=1}^{q} f(n)e(−kn/q).

To obtain a Fourier representation of f we multiply both sides of (1) by f(n) and sum over n to see that

f(a) = ∑_{n=1}^{q} \frac{f(n)}{q} ∑_{k=1}^{q} e(−ka/q)e(kn/q)

= ∑_{k=1}^{q} e(−ka/q)\frac{1}{q} ∑_{n=1}^{q} f(n)e(kn/q)

= ∑_{k=1}^{q} e(−ka/q)f̂(−k).

Here the exact values that k runs through are immaterial, as long as the set of these values forms a complete residue system modulo q. Hence we may replace k by −k in the above, and so we see that

(3)  f(n) = ∑_{k=1}^{q} f̂(k)e(kn/q).

This includes (1) as a special case, for if we take f to be the characteristic function of the arithmetic progression a (mod q) then by (2) we have f̂(k) = e(−ka/q)/q, and then (3) coincides with (1). The pair (2), (3) of inversion formulæ are analogous to the formula for the Fourier coefficients and Fourier expansion of a function f ∈ L^{1}(𝕋), but the situation here is simpler because our sums have only finitely many terms.

Let v(h) be the vector v(h) = [e(h/q), e(2h/q), …, e((q − 1)h/q), 1]. From (1) we see that two such vectors v(h_{1}) and v(h_{2}) are orthogonal unless h_{1} ≡ h_{2} (mod q). These vectors are not normalized, but they all have the same length \sqrt{q}, so apart from some rescaling, the transformation from f to f̂ is an isometry. More precisely, if f has period q and f̂ is given by (2), then by (3),

∑_{n=1}^{q} |f(n)|^{2} = ∑_{n=1}^{q} | ∑_{k=1}^{q} f̂(k)e(kn/q)|^{2}.

Characters

By expanding and taking the sum over n inside, we see that this is

= ∑_{j=1}^{q} ∑_{k=1}^{q} f̂(j)\overline{f̂(k)} ∑_{n=1}^{q} e(jn/q)e(−kn/q).

By (1) the innermost sum is q if j = k and is 0 otherwise. Hence

(4)  ∑_{n=1}^{q} |f(n)|^{2} = q ∑_{k=1}^{q} |f̂(k)|^{2}.

This is analogous to Parseval’s identity for functions f ∈ L^{2}(𝕋), or to Plancherel’s identity for functions f ∈ L^{2}(ℝ).

1. Exercises

1. Let U = [u_{kn}] be the q × q matrix with elements u_{kn} = e(kn/q)/\sqrt{q}. Show that UU^{∗} = U^{∗}U = I, i.e., that U is unitary.

2. (a) Let

f(q) = ∑_{\begin{matrix}a=1 \\ (a,q)=1 \end{matrix}}^{q} e(a/q).

Show that

∑_{d|q} f(d) = ∑_{a=1}^{q} e(a/q) = \{ \begin{matrix}1 & (q = 1), \\ 0 & (q > 1). \end{matrix}

(b) Deduce that

∑_{\begin{matrix}a=1 \\ (a,q)=1 \end{matrix}}^{q} e(a/q) = μ(q)

for all positive integers q.

3. Let Φ_{q}(z) denote the q^{th} cyclotomic polynomial, i.e. the monic polynomial whose roots are precisely the primitive q^{th} roots of unity, so that

Φ_{q}(z) = ∏_{\begin{matrix}n=1 \\ (n,q)=1 \end{matrix}}^{q}(z − e(n/q)).

(a) Show that

Φ_{q}(z) = ∏_{d|q} (z^{d} − 1)^{μ(q/d)}

and that (z^{d} − 1)^{μ(q/d)} has a power series expansion, valid when |z| < 1, with integer coefficients. Deduce that Φ_{q}(z) ∈ ℤ[z].

(b) Suppose that z ∈ ℤ and p | Φ_{q}(z) and let e denote the order of z modulo p. Show that e | q and that if p | (z^{d} − 1) then e | d.

(c) Choose t so that p^{t}∥(z^{e} − 1). Show that for m ∈ ℕ with p ∤ m one has p^{t}∥(z^{me} − 1).

(d) Show that if p ∤ q, then p^{ht}∥Φ_{q}(z) where h = ∑_{e|d|q}μ(q/d). Deduce that e = q and that q | (p − 1).

(e) By taking z to be a suitable multiple of q, or otherwise, show that there are infinitely many primes p with p ≡ 1 (mod q).

2. Dirichlet characters

In the preceding section we expressed the characteristic function of an arithmetic progression as a linear combination of additive characters. For purposes of multiplicative number theory we shall similarly represent the characteristic function of a reduced residue class (mod q) as a linear combination of totally multiplicative functions χ(n) each one supported on the reduced residue classes and having period q. These are the Dirichlet characters. Since χ(n) has period q we may think of it as mapping from residue classes, and since χ(n) ≠ 0 if and only if (n, q) = 1, we may think of χ as mapping from the multiplicative group of reduced residue classes to the multiplicative group ℂ^{×} of non-zero complex numbers. As χ is totally multiplicative, χ(mn) = χ(m)χ(n) for all m, n, we see that the map χ : (ℤ/qℤ)^{×} ⟶ ℂ^{×} is a homomorphism. The method we use to describe these characters applies when (ℤ/qℤ)^{×} is replaced by an arbitrary finite abelian group G, so we consider the slightly more general problem of finding all homomorphisms χ : G → ℂ^{×} from such a group G to ℂ^{×}. We call these homomorphisms the characters of G, and let Ĝ denote the set of all characters of G. We let χ_{0} denote the principal character, whose value is identically 1. We note that if χ ∈ Ĝ then χ(e) = 1 where e denotes the identity in G. Let n denote the order of G. If g ∈ G and χ ∈ Ĝ, then g^{n} = e, and hence χ(g^{n}) = 1. Consequently χ(g)^{n} = 1, and so we see that all values taken by characters are n^{th} roots of unity. In particular, this implies that Ĝ is finite, since there can be at most n^{n} such maps. If χ_{1} and χ_{2} are two characters of G, then we can define a product character χ_{1}χ_{2} by χ_{1}χ_{2}(g) = χ_{1}(g)χ_{2}(g). For χ ∈ Ĝ, let \overline{χ} be the character \overline{χ(g)}. Then χ · \overline{χ} = χ_{0}, and we see that Ĝ is a finite abelian group with identity χ_{0}. The following lemmas prepare for a full description of Ĝ in Theorem 4.

Lemma 1. Suppose that G is cyclic of order n, say G = (a). Then there are exactly n characters of G, namely χ_{k}(a^{m}) = e(km/n) for 1 ≤ k ≤ n. Moreover,

(5)  ∑_{g∈G} χ(g) = \{ \begin{matrix}n & if χ = χ_{0}, \\ 0 & otherwise, \end{matrix}

and

(6)  ∑_{χ∈Ĝ} χ(g) = \{ \begin{matrix}n & if g = e, \\ 0 & otherwise. \end{matrix}

In this situation, Ĝ is cyclic, Ĝ = (χ_{1}).

Proof. Suppose that χ ∈ Ĝ. As we have observed, χ(a) is a n^{th} root of unity, say χ(a) = e(k/n) for some k, 1 ≤ k ≤ n. Hence χ(a^{m}) = χ(a)^{m} = e(km/n). Since the characters are now known explicitly, the remaining assertions are easily verified.

Next we describe the characters of the direct product of two groups in terms of the characters of the factors.

Lemma 2. Suppose that G_{1} and G_{2} are finite abelian groups, and that G = G_{1} ⊗ G_{2}. If χ_{i} is a character of G_{i}, i = 1, 2, and g ∈ G is written g = (g_{1}, g_{2}), g_{i} ∈ G_{i}, then χ(g) = χ_{1}(g_{1})χ_{2}(g_{2}) is a character of G. Conversely, if χ ∈ Ĝ, then there exist unique χ_{i} ∈ G_{i} such that χ(g) = χ_{1}(g_{1})χ_{2}(g_{2}). The identities 5) and 6) hold for G if they hold for both G_{1} and G_{2}.

We see here that each χ ∈ Ĝ corresponds to a pair (χ_{1}, χ_{2}) ∈ Ĝ_{1} × Ĝ_{2}. Thus G ≅ Ĝ_{1} ⊗ Ĝ_{2}.

Proof. The first assertion is clear. As for the second, put χ_{1}(g_{1}) = χ((g_{1}, e_{2})), χ_{2}(g_{2}) = χ((e_{1}, g_{2})). Then χ_{i} ∈ Ĝ_{i} for i = 1, 2, and χ_{1}(g_{1})χ_{2}(g_{2}) = χ(g). The χ_{i} are unique, for if g = (g_{1}, e_{2}), then

χ(g) = χ((g_{1}, e_{2})) = χ_{1}(g_{1})χ_{2}(e_{2}) = χ_{1}(g_{1}),

and similarly for χ_{2}. If χ(g) = χ_{1}(g_{1})χ_{2}(g_{2}), then

∑_{g∈G} χ(g) = ( ∑_{g_{1}∈G_{1}} χ_{1}(g_{1}))( ∑_{g_{2}∈G_{2}} χ_{2}(g_{2})),

so that (5) holds for G if it holds for G_{1} and for G_{2}. Similarly, if g = (g_{1}, g_{2}), then

∑_{χ∈Ĝ} χ(g) = ( ∑_{χ1 ∈Ĝ_{1}} χ_{1}(g_{1}))( ∑_{χ1 ∈Ĝ_{2}} χ_{2}(g_{2})),

so that (6) holds for G if it holds for G_{1} and G_{2}.

Theorem 3. Let G be a finite abelian group. Then Ĝ is isomorphic to G, and (5) and (6) both hold.

Proof. Any finite abelian group is isomorphic to a direct product of cyclic groups, say

G ≅ C_{n_{1}} ⊗ C_{n_{2}} ⊗ ⋯ ⊗ C_{n_{r}}.

The result then follows immediately from the lemmas.

Though G and Ĝ are isomorphic, the isomorphism is not canonical. That is, no particular one-to-one correspondence between the elements of G and those of Ĝ is naturally distinguished.

Corollary 4. The multiplicative group (ℤ/qℤ)^{×} of reduced residue classes (mod q) has φ(q) Dirichlet characters. If χ is such a character, then

(7)  ∑_{\begin{matrix}n=1 \\ (n,q)=1 \end{matrix}}^{q} χ(n) = \{ \begin{matrix}φ(q) & if χ = χ_{0}, \\ 0 & otherwise. \end{matrix}

If (n, q) = 1, then

(8)  ∑_{χ} χ(n) = \{ \begin{matrix}φ(q) & if n ≡ 1 (mod q), \\ 0 & otherwise \end{matrix}

where the sum is extended over the φ(q) Dirichlet characters χ (mod q).

As we remarked at the outset, for our purposes it is convenient to define the Dirichlet characters (mod q) on all integers; we do this by setting χ(n) = 0 when (n, q) > 1. Thus χ is a totally multiplicative function with period q that vanishes whenever (n, q) > 1, and any such function is a Dirichlet character (mod q).

Corollary 5. If χ_{i} is a character (mod q_{i}) for i = 1, 2, then χ_{1}(n)χ_{2}(n) is a character (mod [q_{1}, q_{2}]). If q = q_{1}q_{2}, (q_{1}, q_{2}) = 1, and χ is a character (mod q), then there exist unique characters χ_{i} (mod q), i = 1, 2, such that χ(n) = χ_{1}(n)χ_{2}(n) for all n.

Proof. The first assertion follows immediately from the observations that χ_{1}(n)χ_{2}(n) is totally multiplicative, that it vanishes if (n, [q_{1}, q_{2}]) > 1, and that it has period [q_{1}, q_{2}]. As for the second assertion, we may suppose that (n, q) = 1. By the Chinese Remainder Theorem we see that

(ℤ/qℤ)^{×} ≅ (ℤ/q_{1}ℤ)^{×} ⊗ (ℤ/q_{2}ℤ)^{×}

if (q_{1}, q_{2}) = 1. Thus the result follows from Lemma 1.

Our proof of Theorem 3 depends on Abel’s Theorem that any finite abelian group is isomorphic to the direct product of cyclic groups, but we can prove Corollary 4 without appealing to this result, as follows. By the Chinese Remainder Theorem we see that

(ℤ/qℤ)^{×} ≅ ⨂_{p^{α}∥q} (ℤ/p^{α}ℤ)^{×}.

If p is odd then the reduced residue classes (mod p^{α}) form a cyclic group; in classical language we say there is a primitive root g. Thus if (n, p) = 1 then there is a unique ν (mod φ(p^{α})) such that g^{ν} ≡ n (mod p^{α}). The number ν is called the index of n, and is denoted ν = ind_{g} n. From Lemma 2 it follows that the characters (mod p^{α}), p > 2, are given by

(9)  χ_{k}(n) = e(\frac{k ind_{g} n}{φ(p^{α})})

for (n, p) = 1. We obtain φ(p^{α}) different characters by allowing k to assume integral values in the range 1 ≤ k ≤ φ(p^{α}). By Lemma 2 it follows that if q is odd then the general character (mod q) is given by

(10)  χ(n) = e( ∑_{p^{α}∥q} \frac{k ind_{g} n}{φ(p^{α})})

for (n, q) = 1, where it is understood that k = k(p^{α}) is determined (mod φ(p^{α})) and that g = g(p^{α}) is a primitive root (mod p^{α}).

The multiplicative structure of the reduced residues (mod 2^{α}) is more complicated. For α = 1 or α = 2 the group is cyclic (of order 1 or 2, respectively), and (9) holds as before. For α ≥ 3 the group is not cyclic, but if n is odd then there exist unique μ (mod 2) and ν (mod 2^{α−2}) such that n ≡ (−1)^{μ}5^{ν} (mod 2^{α}). In group-theoretic terms this means that

(ℤ/2^{α}ℤ)^{×} ≅ C_{2} ⊗ C_{2^{α−2}}

when α ≥ 3. By Lemma 2 the characters in this case take the form

(11)  χ(n) = e(\frac{jμ}{2} + \frac{kν}{2^{α−2}} )

for odd n where j = 0 or 1 and 1 ≤ k ≤ 2^{α−2}. Thus (10) holds if 8 ∤ q, but if 8|q then the general character takes the form

(12)  χ(n) = e(\frac{jμ}{2} + \frac{kν}{2^{α−2}} + ∑_{\begin{matrix}p^{α}∥q \\ p>2 \end{matrix}} \frac{ℓ ind_{g} n}{φ(p^{α})})

when (n, q) = 1.

By definition, if f(n) is totally multiplicative, f(n) = 0 whenever (n, q) > 1, and f(n) has period q, then f is a Dirichlet character (mod q). It is useful to note that the first condition can be relaxed.

Theorem 6. If f is multiplicative, f(n) = 0 whenever (n, q) > 1, and f has period q, then f is a Dirichlet character modulo q.

Proof. It suffices to show that f is totally multiplicative. If (mn, q) > 1, then f(mn) = f(m)f(n) since 0 = 0. Suppose that (mn, q) = 1. Hence in particular (m, q) = 1, so that the map k ↦ n + kq (mod m) permutes the residue classes (mod m). Thus there is a k for which n + kq ≡ 1 (mod m), and consequently (m, n + kq) = 1. Then

f(mn) = f(m(n + kq))  (by periodicity)
= f(m)f(n + kq)  (by multiplicativity)
= f(m)f(n)  (by periodicity),

and the proof is complete.

2. Exercises

1. Let G be a finite abelian group of order n. Let g_{1}, g_{2}, …, g_{n} denote the elements of G, and let χ_{1}(g), χ_{2}(g), …, χ_{n}(g) denote the characters of G. Let U = [u_{ij}] be the n × n matrix with elements u_{ij} = χ_{i}(g_{j})/\sqrt{n}. Show that UU^{∗} = U^{∗}U = I, i.e., that U is unitary.

2. Show that for arbitrary real or complex numbers c_{1}, …, c_{q},

∑_{χ} | ∑_{n=1}^{q} c_{n}χ(n)|^{2} = φ(q) ∑_{\begin{matrix}n=1 \\ (n,q)=1 \end{matrix}}^{q} |c_{n}|^{2}

where the sum on the left hand side runs over all Dirichlet characters χ (mod q).

3. Show that for arbitrary real or complex numbers c_{χ},

∑_{n=1}^{q} | ∑_{χ} c_{χ}χ(n)|^{2} = φ(q) ∑_{χ} |c_{χ}|^{2}

where the sum over χ is extended over all Dirichlet characters (mod q).

4. Let (a, q) = 1, and suppose that k is the order of a in the multiplicative group of reduced residue classes (mod q).

(a) Show that if χ is a Dirichlet character (mod q) then χ(a) is a k^{th} root of unity.

(b) Show that if z is a k^{th} root of unity then

1 + z + ⋯ + z^{k−1} = \{ \begin{matrix}k & if z = 1, \\ 0 & otherwise. \end{matrix}

(c) Let ζ be a k^{th} root of unity. By taking z = χ(a)/ζ, show that each k^{th} root of unity occurs precisely φ(q)/k times among the numbers χ(a) as χ runs over the φ(q) Dirichlet characters (mod q).

5. Let χ be a Dirichlet character (mod q), and let k denote the order of χ in the character group.

(a) Show that if (a, q) = 1 then χ(a) is a k^{th} root of unity.

(b) Show that each k^{th} root of unity occurs precisely φ(q)/k times among the numbers χ(a) as a runs over the φ(q) reduced residue classes (mod q).

3. Dirichlet L-functions

For real s > 1 we define the Riemann zeta function ζ(s) to be

(13)  ζ(s) = ∑_{n=1}^{∞} \frac{1}{n^{s}} .

By the integral test we note that

(14)  \frac{1}{s − 1} = ∫_{1}^{∞} x^{−s} dx < ∑_{n=1}^{∞} \frac{1}{n^{s}} < 1 + ∫_{1}^{∞} x^{−s} dx = \frac{s}{s − 1} .

Hence in particular, ζ(s) → ∞ as s → 1^{+}. A second formula for the zeta function, known as the Euler product formula, asserts that

(15)  ζ(s) = ∏_{p} (1 − \frac{1}{p^{s}} )^{−1}

for s > 1. To understand why this holds, suppose that y is given, and let 𝒩 = 𝒩(y) denote the set of those positive integers composed entirely of primes not exceeding y. By the unique factorization theorem it follows that

∑_{n∈𝒩} \frac{1}{n^{s}} = ∏_{p≤y} (1 + \frac{1}{p^{s}} + \frac{1}{p^{2s}} + ⋯) = ∏_{p≤y} (1 − \frac{1}{p^{s}} )^{−1} .

Here the reordering of the summands is justified by absolute convergence, and we obtain (15) by letting y tend to infinity.

Similarly, if χ is a character (mod q), then for s > 1 we put

(16)  L(s, χ) = ∑_{n=1}^{∞} χ(n)n^{−s}.

Since χ is totally multiplicative, it follows that

(17)  L(s, χ) = ∏_{p} (1 − χ(p)p^{−s})^{−1}

for s > 1. In particular, we see that

(18)  L(s, χ_{0}) = ∑_{\begin{matrix}n=1 \\ (n,q)=1 \end{matrix}}^{∞} n^{−s} = ζ(s) ∏_{p|q} (1 − p^{−s})

for s > 1.

The zeta function is differentiable for s > 1, since the differentiated series

− ∑_{n=1}^{∞} \frac{log n}{n^{s}}

is uniformly convergent for s ≥ 1 + δ. Indeed, since (log n)/n is monotonically decreasing for n ≥ 3, it follows by the integral test that

(19)  ζ′(s) = − ∑_{n=1}^{∞} \frac{log n}{n^{s}} = − ∫_{1}^{∞} \frac{log x}{x^{s}} dx + O(1) = \frac{−1}{(s − 1)^{2}} + O(1)

uniformly for s > 1. By taking logarithms of both sides of the Euler product identity (15), we find that

log ζ(s) = ∑_{p} log (1 − p^{−s})^{−1} = ∑_{p} ∑_{k=1}^{∞} \frac{1}{kp^{ks}}

in view of the power series expansion log(1 − w)^{−1} = ∑_{k=1}^{∞} w^{k}/k. We can differentiate the above term-by-term, since the differentiated series is uniformly convergent for s ≥ 1 + δ. Thus we find that

(20)  \frac{ζ′(s)}{ζ(s)} = − ∑_{p} ∑_{k=1}^{∞} \frac{log p}{p^{ks}} = ∑_{n=1}^{∞} \frac{Λ(n)}{n^{s}}

where Λ(n) is the von Mangoldt lambda function,

Λ(n) = \{ \begin{matrix}log p & if n = p^{k}, \\ 0 & otherwise. \end{matrix}

We note that

(21)  ∑_{d|n} Λ(d) = ∑_{p^{a}∥n} ∑_{b=1}^{a} log p = ∑_{p^{a}∥n} a log p = log n,

which is an elementary way of expressing the relation

( − \frac{ζ′(s)}{ζ(s)}) · ζ(s) = −ζ′(s) .

By taking logarithms in (18), and then differentiating, we deduce that

\frac{L′(s, χ_{0})}{L(s, χ_{0})} = \frac{ζ′(s)}{ζ(s)} + ∑_{p|q} \frac{log p}{p^{s} − 1}

for s > 1. On combining this with the estimates (14) and (19), we deduce that

(22)  \frac{L′(s, χ_{0})}{L(s, χ_{0})} = \frac{−1}{s − 1} + O_{q}(1)

for s > 1.

For χ ≠ χ_{0} we proceed somewhat differently. First we recall Dirichlet’s test, which asserts that if a_{n} is a sequence of real or complex numbers such that the sums ∑_{n=1}^{N} a_{n} are uniformly bounded, and if b_{n} are positive real numbers decreasing monotonically to 0, then the series ∑_{n=1}^{∞} a_{n}b_{n} converges. From (7) we see that if χ ≠ χ_{0}, then

∑_{1≤n≤kq} χ(n) = 0

for k = 1, 2, 3, . . .. Hence

(23)  | ∑_{n≤x} χ(n)| ≤ q

for all x/ge1. Thus by Dirichlet’s test, the series (16) that defines L(s, χ) is convergent for all s > 0, when χ ≠ χ_{0}. The usual proof of Dirichlet’s test can be modified to show further that if the sums ∑_{n=1}^{N} a_{n} are uniformly bounded, and b_{n}(x) are functions such that b_{n}(x) ≥ b_{n+1}(x) for all x ∈ [a, b], with 0 ≤ b_{n}(x) ≤ B_{n} for all x ∈ [a, b], and B_{n} → 0 as n → ∞, then ∑ a_{n}b_{n}(x) is uniformly convergent. By applying this to the differentiated series − ∑ χ(n)(log n)n^{−s}, we deduce that

L′(s, χ) = − ∑_{n=1}^{∞} \frac{χ(n) log n}{n^{s}}

is a continuous function for s > 0. For s > 1 we apply (21), and thus find that the above is

= − ∑_{n=1}^{∞} \frac{χ(n)}{n^{s}} ∑_{d|n} Λ(d).

On putting n = md, and inverting the order of summation, we find that the above is

= − ∑_{d=1}^{∞} \frac{χ(d)Λ(d)}{d^{s}} ∑_{m=1}^{∞} \frac{χ(m)}{m^{s}}

= −L(s, χ) ∑_{m=1}^{∞} \frac{χ(m)Λ(m)}{m^{s}}.

That is,

(24)  \frac{L′(s, χ)}{L(s, χ)} = − ∑_{m=1}^{∞} \frac{χ(m)Λ(m)}{m^{s}}

for s > 1. Suppose that (a, q) = 1. If we multiply both sides of the above by \overline{χ}(a), sum over χ (mod q), and divide both sides by φ(q), then we find that

∑_{\begin{matrix}n=1 \\ n≡a (q) \end{matrix}}^{∞} \frac{Λ(n)}{n^{s}} = \frac{−1}{φ(q)} ∑_{χ} \overline{χ}(a)\frac{L′(s, χ)}{L(s, χ)}

for s > 1. Our intent is to show that the above tends to infinity as s → 1^{+}. From (22) we see that the contribution made by the principal character on the right hand side tends to infinity. The other terms on the right hand side tend to finite limits, provided that L(1, χ) ≠ 0. That is, if L(1, χ) ≠ 0 for all χ ≠ χ_{0}, then

∑_{\begin{matrix}n=1 \\ n≡a (q) \end{matrix}}^{∞} \frac{Λ(n)}{n} = ∞.

Since

∑_{p} ∑_{k>1} \frac{log p}{p^{k}} = ∑_{p} \frac{log p}{p^{2} − p} < ∞,

it follows that

∑_{\begin{matrix}p \\ p≡a (q) \end{matrix}} \frac{log p}{p} = ∞.

Thus our approach has the following logical structure:

Lemma 7. (Dirichlet) Let χ be a Dirichlet character modulo q, χ ≠ χ_{0}. Then L(1, χ) ≠ 0.

Theorem 8. (Dirichlet) Suppose that (a, q) = 1. Then there exist infinitely many primes p such that p ≡ a (mod q), and indeed

∑_{\begin{matrix}p \\ p≡a (q) \end{matrix}} \frac{log p}{p} = ∞ .

Our proof of Lemma 7 depends on the nature of the character involved. We call a character real if all its values are real (i.e., χ(n) = 0 or ±1 for all n). Otherwise a character is complex. A character is quadratic if it has order 2 in the character group: χ^{2} = χ_{0} but χ ≠ χ_{0}. Thus a quadratic character is real, and a real character is either principal or quadratic. If χ is quadratic, then χ^{2} = χ_{0}, and hence χ is its own inverse in the character group. If χ is complex, then \overline{χ} is also a character, χ ≠ \overline{χ}, and χ\overline{χ} = χ_{0}, so that \overline{χ} is the inverse of χ in the character group.

To prove Lemma 7 for complex characters, we first show that

(25)  ∏_{χ} L(s, χ) ≥ 1

for all s > 1. To this end we take logarithms on both sides of the Euler product formula (17) for L(s, χ) to see that

log L(s, χ) = ∑_{p} log (1 − χ(p)p^{−s})^{−1} = ∑_{p} ∑_{k=1}^{∞} \frac{χ(p^{k})}{kp^{ks}} = ∑_{n=2}^{∞} \frac{Λ(n)}{log n} · \frac{χ(n)}{n^{s}} .

We sum over χ and use the orthogonality relation (8) to see that

∑_{χ} log L(s, χ) = φ(q) ∑_{\begin{matrix}n=2 \\ n≡1 (q) \end{matrix}}^{∞} \frac{Λ(n)}{log n} · \frac{χ(n)}{n^{s}} .

On exponentiating, we deduce that

∏_{χ} L(s, χ) = exp (φ(q) ∑_{\begin{matrix}n=2 \\ n≡1 (q) \end{matrix}}^{∞} \frac{Λ(n)}{log n} · \frac{χ(n)}{n^{s}}) .

On the right hand side we are exponentiating a non-negative real number, and hence the right hand side is at least 1, which is to say we have (25).

We note that the argument just completed involves taking logarithms of complex numbers. This can be avoided by the following alternative line of reasoning: On the left hand side of (25) we express each L-function by its Euler product formula. The contribution of a particular prime p is then

∏_{χ} (1 − \frac{χ(p)}{p^{s}})^{−1}.

Suppose that p has order 4 in the multiplicative group of reduced residue classes (mod q). By Exercise 2.4 we know that the numbers χ(p) are k^{th} roots of unity, each one with multiplicity φ(q)/k. Also, we note the polynomial factorization z^{k} −1 = ∏_{a=1}^{k}(z −e(a/k)). Hence the above is

= ∏_{a=1}^{k} (1 − \frac{e(a/k)}{p^{s}})^{−φ(q)/k} = (1 − \frac{1}{p^{ks}} )^{−φ(q)/k}.

Since this last expression is clearly > 1, we again have (25).

We now consider the asymptotic behavior of the left hand side of (25) as s → 1^{+}. From (14) and (18) we see that

L(s, χ_{0}) ∼ \frac{φ(q)/q}{s − 1}

as s → 1^{+}. Suppose that χ ≠ χ_{0}. Then L(s, χ) is continuous for s > 0, and hence lim_{s→1^{+}} L(s, χ) = L(1, χ). Suppose now that L(1, χ) = 0. Since L′(s, χ) is continuous for s > 0, the number

C_{χ} = max_{1≤s≤2} |L′(s, χ)|

is finite, and by Rolle’s theorem |L(s, χ)| ≤ C_{χ}(s − 1) for 1 < s ≤ 2. We note that the factor s − 1 cancels the effect of the factor 1/(s − 1) contributed by L(s, χ_{0}). Suppose now that L(1, χ) = 0 for n different characters (mod q). Then the left hand side of (25) is < C(s − 1)^{n−1} as s → 1^{+}, which contradicts (25) if n > 1. That is, L(1, χ) = 0 for at most one character (mod q). However, if χ is a complex character, then L(s, \overline{χ}) = \overline{L(s, chi)}). Hence if L(1, χ) = 0, then also L(1, \overline{χ}) = 0. Since this we now have two different characters that vanish at s = 1, we deduce that L(1, χ) ≠ 0 when χ is complex.

We now see that the heart of the matter is to show that L(1, χ) ≠ 0 when χ is a quadratic character. Dirichlet achieved this by relating L(1, χ) to the number of equivalence classes of binary quadratic forms. To prepare for our more elementary approach, we first establish two subsidiary estimates.

Lemma 9. There is a real number C such that

∑_{m≤y} \frac{1}{\sqrt{m}} = 2y^{1/2} + C + O(y^{−1/2})

for y ≥ 1.

The constant C here is ζ(1/2) = −1.4603545 …, but this is a bit nonsensical, since we have only defined the zeta function for real s > 1.

Proof. Suppose that f has continuous derivative on an interval [a, b]. Then by integration by parts we see that

∫_{a}^{b} f(x) dx = \frac{b − a}{2}(f(a) + f(b)) − ∫_{a}^{b}(x − \frac{a+b}{2})f′(x) dx .

Here the first term on the right hand side is the area of a trapezoid, and the integral on the right represents the error introduced when approximating to an integral by the trapezoid rule. (For purposes of numerical integration, one would usually integrate this latter integral by parts to obtain an estimate in terms of f′′(x).) By taking a = m, b = m + 1, f(x) = x^{−1/2}, we find that

\frac{1}{2}(\frac{1}{\sqrt{m}} + \frac{1}{\sqrt{m + 1}}) = ∫_{m}^{m+1} x^{−1/2} dx − \frac{1}{2} ∫_{m}^{m+1}(x − m − 1/2)x^{−3/2} dx .

By summing this over m = 1, 2, …, M − 1, we find that

∑_{m=1}^{M} \frac{1}{\sqrt{m}} = \frac{1}{2} + \frac{1}{2\sqrt{M}} + ∫_{1}^{M} x^{−1/2} dx − \frac{1}{2} ∫_{1}^{M}(\{x\} − 1/2)x^{−3/2} dx

= 2M^{1/2} − \frac{3}{2} − \frac{1}{2} ∫_{1}^{∞}(\{x\} − 1/2)x^{−3/2} dx + \frac{1}{2\sqrt{M}} + \frac{1}{2} ∫_{M}^{∞}(\{x\} − 1/2)x^{−3/2} dx

= 2M^{1/2} + C + O(M^{−1/2})

where

C = −\frac{1}{2} ∫_{1}^{∞}(\{x\} − 1/2)x^{−3/2} dx .

Lemma 10. Let χ be a non-principal character modulo q. If s > 0 and x ≥ 1, then

∑_{n≤x} \frac{χ(n)}{n^{s}} = L(s, χ) + O(qx^{−s}) .

We have already made the qualitative observation that the series defining L(s, χ) converges for s > 0. In the above, we are making a more specific claim concerning the rate of this convergence.

Proof. Let S(x) = ∑_{n≤x} χ(n). Then

∑_{n=M+1}^{M+N} \frac{χ(n)}{n^{s}} = ∑_{n=M+1}^{M+N} \frac{S(n) − S(n − 1)}{n^{s}}

= ∑_{n=M+1}^{M+N−1} S(n)(\frac{1}{n^{s}} − \frac{1}{(n + 1)^{s}} ) + \frac{S(M + N)}{(M + N)^{s}} − \frac{S(M)}{(M + 1)^{s}}

We have already observed that |S(x)| ≤ q for all x. Thus the above has absolute value not exceeding

q( ∑_{n=M+1}^{M+N} (\frac{1}{n^{s}} − \frac{1}{(n + 1)^{s}} ) + \frac{1}{(M + 1)^{s}} + \frac{1}{(M + N)^{s}} ) = \frac{2q}{(M + 1)^{s}} .

Thus we have the stated result.

We now complete the proof of Lemma 7. Suppose that χ is a quadratic character modulo q, and put r(n) = ∑_{d|n} χ(d). Since χ is multiplicative, it follows that r(n) is also multiplicative, and indeed if n = ∏_{p} p^{α} where α = α(p), then

r(n) = ∏_{p} (1 + χ(p) + χ(p^{2}) + ⋯ + χ(p^{α})) .

We note that

(26)  1 + χ(p) + χ(p^{2}) + ⋯ + χ(p^{α}) = \{ \begin{matrix}1 & if p|q, \\ α + 1 & if χ(p) = 1, \\ 1 & if χ(p) = −1 and 2|α, \\ 0 & if χ(p) = −1 and 2 ∤ α. \end{matrix}

Next we show that

(27)  ∑_{n≤x} \frac{r(n)}{\sqrt{n}} = 2x^{1/2}L(1, χ) + O(\sqrt{q})

for x ≥ q. For d|n we write n = md, we let y be a parameter to be chosen later, 1 ≤ y ≤ x, and we distinguish between d ≤ y and d > y to see that the above is

∑_{n≤x} n^{−1/2} ∑_{d|n} χ(d) = ∑_{\begin{matrix}m,d \\ md≤x \end{matrix}} \frac{χ(d)}{\sqrt{md}}

= ∑_{d≤y} \frac{χ(d)}{\sqrt{d}} ∑_{m≤x/d} \frac{1}{\sqrt{m}}

+ ∑_{m≤x/y} \frac{1}{\sqrt{m}} ∑_{y<d≤x/m} \frac{χ(d)}{\sqrt{d}}

which by Lemmas 9 and 10 is

= ∑_{d≤y} \frac{χ(d)}{\sqrt{d}}(2\sqrt{x/d} + C + O(\sqrt{d/x})) + O( ∑_{m≤x/y} \frac{q}{\sqrt{my}} )

= 2\sqrt{x} ∑_{d≤y} \frac{χ(d)}{d} + C ∑_{d≤y} \frac{χ(d)}{\sqrt{d}} + O(y/\sqrt{x}) + O(q\sqrt{x}/y) .

By two further applications of Lemma 10 we see that this is

= 2\sqrt{x}L(1, χ) + CL(1/2, χ) + O(y/\sqrt{x}) + O(q\sqrt{x}/y) .

By taking x = q and s = 1/2 in Lemma 10, and estimating the sum on the left hand side trivially, we deduce that L(1/2, χ) = O(\sqrt{q}). On inserting this in the above, and taking y = \sqrt{qx}, we obtain the estimate (27).

If L(1, χ) = 0, then the right hand side of (27) remains bounded as x tends to infinity. On the other hand, from (26) we see that r(n) ≥ 0 for all n, and that r(n^{2}) ≥ 1. Thus the left hand side of (27) is ≥ ∑_{m≤\sqrt{x}} 1/m, which tends to infinity with x. Thus L(1, χ) > 0, and so Lemma 7 is proved, and with it, Theorem 8.

4. Gauss sums

In the additive characters e(an/q) we have a basis for the vector space of arithmetic functions with period q. Let χ(n) be a Dirichlet character modulo q. Since χ(n) has period q, it follows that the multiplicative character χ can be written as a linear combination of additive characters. This can be done for arbitrary q, but we restrict our attention here to a prime modulus. Let χ be a non-principal character (mod p). We define the Gauss sum of χ to be

(28)  τ(χ) = ∑_{n=1}^{p} χ(n)e(n/p) .

Note that this is the inner product of χ with the particular additive character e(n/p). We may consider similar inner products with other characters, say by setting

G(a, χ) = ∑_{n=1}^{p} χ(n)e(an/p).

By (7) we see that

(29)  G(0, χ) = 0.

On the other hand, if (a, p) = 1, then

χ(a)G(a, χ) = ∑_{n=1}^{p} χ(an)e(an/p) .

Since an runs through a complete residue system (mod p) as n does, the right hand side above is τ(χ). That is,

(30)  G(a, χ) = \overline{χ}(a)τ(χ)

for a ≢ 0 (mod p). From (29) we see that the above also holds when a ≡ 0 (mod p); thus it holds for all a.

In the notation (2) of the finite Fourier transform,

χ̂(k) = \frac{1}{p}G(−k, χ) .

We recall that the Parseval identity (4) for the finite Fourier transform asserts that

∑_{n=1}^{p} |χ(n)|^{2} = p ∑_{k=1}^{p} |χ̂(k)|^{2}.

Here the left hand side is p − 1, and by (30) the right hand side is (p − 1)|τ(χ)|^{2}/p. Consequently,

(31)  |τ(χ)| = \sqrt{p}

for each non-principal character character χ (mod p). The Gauss sum (28) could also be defined similarly for the principal character χ_{0}; by (7) we find that τ(χ_{0}) = −1. This is a special case of Exercise 1.2.

By taking complex conjugates in the definition (28) of the Gauss sum, we find that

\overline{τ(χ)} = ∑_{n=1}^{p} \overline{χ}(n)e(−n/p),

which by (30) is

= χ(−1)τ(\overline{χ}).

The only quadratic character modulo p is the Legendre symbol (\frac{n}{p}). When the above is applied to this particular character, we find that

(32)  τ((\frac{·}{p})) = \{ \begin{matrix}±\sqrt{p} & if p ≡ 1 (mod 4), \\ ±i\sqrt{p} & if p ≡ −1 (mod 4) . \end{matrix}

Gauss noticed empirically—and eventually proved—that only the plus sign occurs. For complex characters the location of τ(χ) on the circle |z| = \sqrt{p} is less predictable, and indeed Deligne showed that the numbers τ(χ) are asymptotically uniformly distributed on this circle, as p → ∞.

On the additive group of real numbers we have additive characters x ↦ e^{−ax}, which is to say homomorphisms into the multiplicative group ℂ^{×} of non-zero of complex numbers. On the multiplicative group of positive real numbers—which may be construed as analogous to the reduced residues modulo q—we have multiplicative characters x ↦ x^{s} where s is a complex number. The inner product of these, with respect to the multiplicatively invariant measure dx/x, is

∫_{0}^{∞} e^{−ax}x^{s} \frac{dx}{x} = a^{−s} ∫_{0}^{∞} e^{−x}x^{s} \frac{dx}{x} = a^{−s}Γ(s)

for ℜs > 0. This is Euler’s integral for the Gamma function. Although it converges only for ℜs > 0, the Gamma function may be considered to by analogous, for any complex s, to the Gauss sum τ(χ).

Consider (30) with a non-principal character χ replaced by \overline{χ}. Since τ(\overline{χ}) ≠ 0 we can divide by this quantity to find that

(33)  χ(a) = \frac{1}{τ(\overline{χ})} ∑_{n=1}^{p} \overline{χ(n)}e(an/p)

for all a. Here we have expressed the multiplicative character χ(a) as a linear combination of the additive characters e(an/p). The above has many important applications. As an example, we show that it is now a routine matter to evaluate the sum

S(h) = ∑_{a=1}^{p} (\frac{a}{p})(\frac{a + h}{p}) .

By two applications of (33) we see that the above is

∑_{a=1}^{p} \frac{1}{τ_{p}^{2}} ∑_{m=1}^{p} (\frac{m}{p})e(\frac{am}{p}) ∑_{n=1}^{p} (\frac{n}{p})e(\frac{n(a + h)}{p}).

By (32) we see that τ_{p}^{2} = p(\frac{−1}{p}). Thus the above is

\frac{(\frac{−1}{p})}{p} ∑_{m=1}^{p} (\frac{m}{p}) ∑_{n=1}^{p} (\frac{n}{p}) ∑_{a=1}^{p} e(\frac{(m + n)a + hn}{p}) .

Here the innermost sum vanishes unless n ≡ −m (mod p), in which case it has the value pe(hn/p). Thus the above is

(\frac{−1}{p}) ∑_{m=1}^{p} (\frac{−m^{2}}{p} )e(\frac{−mh}{p}) = ∑_{m=1}^{p−1} e(\frac{−mh}{p})

= \{ \begin{matrix}−1 & if h ≢ 0 (mod p), \\ p − 1 & if h ≡ 0 (mod p). \end{matrix}

4. Exercises

1. (a) Show that if p > 2 and p ∤ b, then

∑_{n=1}^{p} (\frac{n}{p})(\frac{n + b}{p}) = −1.

(b) Suppose that p > 2 and that p ∤ d. Explain why

∑_{x=1}^{p} (\frac{x^{2} − d}{p}) = ∑_{n=1}^{p} (1 + (\frac{n}{p}))(\frac{n − d}{p}),

and deduce that this sum is −1.

(c) Put d = b^{2} − 4ac, and suppose that p > 2, p ∤ d. Show that

∑_{x=1}^{p} (\frac{ax^{2} + bx + c}{p}) = (\frac{a}{p}).

2. Let p be a prime, p ≡ 1 (mod 4), and let 𝒩 be a set of Z residue classes modulo p.

(a) Explain why

∑_{m∈𝒩} ∑_{n∈𝒩} (\frac{m − n}{p}) = \frac{1}{\sqrt{p}} ∑_{a=1}^{p} (\frac{a}{p})| ∑_{n∈𝒩} e(an/p)|^{2}.

(b) Suppose that (\frac{m−n}{p}) = 1 whenever m ∈ 𝒩, n ∈ 𝒩, and m ≠ n. Show that Z ≤ \sqrt{p}.

3. Put f_{a}(r) = r^{2} +a_{1}r +a_{0} where a = (a_{0}, a_{1}). Show that if r_{1}, r_{2}, r_{3} are distinct modulo p, then

∑_{a_{0}=1}^{p} ∑_{a_{1}=1}^{p} (\frac{f_{a}(r_{1})}{p})(\frac{f_{a}(r_{2})}{p})(\frac{f_{a}(r_{3})}{p}) = p.

4. Let

G_{k}(a) = ∑_{n=1}^{p} e(\frac{an^{k}}{p} ).

(a) Let N_{k}(h) denote the number of solutions of the congruence x^{k} ≡ h (mod p). Explain why

G_{k}(a) = ∑_{h=1}^{p} N_{k}(h)e(\frac{ah}{p}).

(b) Let l = (k, p − 1). Show that if k is a positive integer, then N_{k}(h) = N_{l}(h) for all h, and hence that G_{k}(a) = G_{l}(a).

(c) Suppose that k | (p − 1). Explain why

∑_{a=1}^{p} |G_{k}(a)|^{2} = p ∑_{h=1}^{p} N_{k}(h)^{2}.

(d) Suppose that k | (p − 1). Show that there are (p − 1)/k residues h (mod p) for which N_{k}(h) = k, that N_{k}(0) = 1, and that N_{k}(h) = 0 for all other residue classes (mod p). Hence show that the right hand side above is p(1 + (p − 1)k).

(e) Let k be a divisor of p − 1. Suppose that p ∤ a, p ∤ c, and that b ≡ ac^{k} (mod p). Show that G_{k}(a) = G_{k}(b).

(f) Suppose that k | (p − 1). Show that if p ∤ a, then |G_{k}(a)| < k\sqrt{p}.

5. Suppose that k | (p − 1), that N_{k}(h) is as in Exercise 4(a), and let χ be a character of order k, say χ(n) = e((ind n)/k).

(a) Show that for all h,

N_{k}(h) = 1 + ∑_{j=1}^{k−1} χ^{j}(h).

(b) Show that if p ∤ a then

G_{k}(a) = ∑_{j=1}^{k−1} \overline{χ}^{j}(a)τ(χ).

(c) Show that if p ∤ a, then |G_{k}(a)| ≤ (k − 1)\sqrt{p}.

6. Let N(q) denote the number of pairs x, y of residue classes (mod q) such that y^{2} ≡ x^{3}+7 (mod q).

(a) Show that N(q) is a multiplicative function of q, that N(2) = 2, N(3) = 3, N(7) = 7, and that N(p) = p when p ≡ 2 (mod 3).

(b) Suppose that p ≡ 1 (mod 3). Let χ_{1}(n) be a cubic character modulo p, and let χ_{2}(n) = (\frac{n}{p}) be the quadratic character modulo p. Show that

N(p) = \frac{1}{p} ∑_{a=1}^{p} e(7a/p)( ∑_{h=1}^{p} (1 + χ_{1}(h) + χ_{1}^{2}(h))e(ah/p))( ∑_{k=1}^{p} (1 + χ_{2}(k))e(−ak/p))

= p + \frac{2}{p}ℜ(τ(χ_{1})τ(χ_{2})τ(χ_{1}^{2}χ_{2})χ_{1}χ_{2}(−7)),

and deduce that |N(p) − p| ≤ 2\sqrt{p}.

(c) Deduce that N(p) > 0 for all p.

(d) Show that N(2^{k}) = 2^{k−1} for k ≥ 2, that N(3^{k}) = 2·3^{k−1} for k ≥ 2, that N(7^{k}) = 6·7^{k−1} for k ≥ 2, and that N(p^{k}) = N(p)p^{k−1} for all other primes.

(e) Conclude that the congruence y^{2} ≡ x^{3} + 7 (mod q) has solutions for every positive integer q.

(f) Suppose that x and y are integers such that y^{2} = x^{3} + 7. Show that 2 | y, x ≡ 1 (mod 4), and that x > 0. Note that y^{2} + 1 = (x + 2)(x^{2} − 2x + 4), so that y^{2} + 1 is composed of primes ≡ 1 (mod 4), and yet x + 2 ≡ 3 (mod 4). Deduce that this equation has no solution in integers.

7. Explain why the number N of solutions of the congruence c_{1}x_{1}^{k_{1}} + ⋯ + c_{m}x_{m}^{k_{m}} ≡ c (mod p) is

N = \frac{1}{p} ∑_{a=1}^{p} e(−ac/p) ∏_{j=1}^{m} G_{k_{j}}(ac_{j})

where G_{k} is defined as in Exercise 4.

(b) Suppose that c = 0 but that p does not divide any of the numbers c_{j}. Show that |N − p^{m−1}| ≤ Cp^{m/2} where C = ∏_{j=1}^{m}((k_{j}, p − 1) − 1).

(c) Suppose that c ≢ 0 (mod p) and that for all j, c_{j} ≢ 0 (mod p). Show that |N −p^{m−1}| ≤ Cp^{(m−1)/2} where C is defined as above.

8. Let χ_{1} and χ_{2} be nonprincipal characters (mod p).

(a) Show that if (a, p) = 1, then

∑_{n=1}^{p} χ_{1}(n)χ_{2}(a − n) = χ_{1}χ_{2}(a)p\frac{τ(\overline{χ}_{1}\overline{χ}_{2})}{τ(\overline{χ}_{1})τ(\overline{χ}_{2})}.

(b) Show that if χ_{1}χ_{2} is nonprincipal, then

(34)  ∑_{n=1}^{p} χ_{1}(n)χ_{2}(a − n) = χ_{1}χ_{2}(a)\frac{τ(χ_{1})τ(χ_{2})}{τ(χ_{1}χ_{2})}

for all a.

When a = 1, the sum (34) is known as the Jacobi sum J(χ_{1}, χ_{2}). In the same way that the Gauss sum is analogous to the gamma function, the Jacobi sum (and it’s evaluation in terms of Gauss sums) is analogous to the Beta function

B(α, β) = ∫_{0}^{1} x^{α−1}(1 − x)^{β−1} dx = \frac{Γ(α)Γ(β)}{Γ(α + β)}.

9. Let C be the smallest field that contains the field Q of rational numbers and is closed under square roots. Thus C is the set of complex numbers that are constructible by rulerand-compass. We show that if p is of the form p = 2^{k} + 1 then ζ = e(1/p) ∈ C, which is to say that a regular p-gon can be constructed.

(a) Let p be any prime, and χ any nonprincipal character modulo p. Explain why

τ(χ)^{2} ∑_{n=1}^{p} \overline{χ}(n)\overline{χ}(1 − n) = pτ(χ^{2}).

(b) From now on assume that p is of the form p = 2^{k} + 1. Explain why χ^{2^{k}} = χ_{0} for any character modulo p, and deduce that χ(n) ∈ C for all χ and all integers n.

(c) Deduce that if τ(χ^{2}) ∈ C, then τ(χ) ∈ C.

(d) Suppose that χ has order 2^{r}. Show successively that the numbers

−1 = τ(χ^{2^{r}}), τ(χ^{2^{r−1}}), …, τ(χ^{2}), τ(χ)

lie in C.

(e) Explain why ∑_{χ} τ(χ) = (p − 1)ζ.

(f) (Gauss) If p = 2^{k} + 1, then ζ ∈ C.

12. Let χ be a character modulo p and put J(χ) = ∑_{n=1}^{p} χ(n)χ(1 − n).

(a) Show that if χ^{2} ≠ χ_{0}, then |J(χ)| = \sqrt{p}.

(b) Show that if p ≡ 1 (mod 4), then there is a quartic character χ modulo p.

(c) Show that if χ is a quartic character, then J(χ) is a Gaussian integer. That is, J(χ) = a + ib where a and b are rational integers.

(d) Deduce that a^{2} + b^{2} = p