Character Orthogonality

Suppose you want to count only the primes in a single arithmetic progression — say the primes \equiv 2 \pmod 5. The primes don't come with a label telling you their residue, so how do you filter a sum \sum_{n \equiv a \,(q)} f(n) down to just one residue class without first sorting every integer by hand? The answer is a piece of Fourier analysis dressed up in number-theoretic clothes. The Dirichlet characters mod q form an orthogonal basis — a set of "pure tones" on the group (\mathbb{Z}/q\mathbb{Z})^{*} — and a clever weighted average of them collapses to the exact indicator of a single progression. That averaging trick, character orthogonality, is the engine that turns "primes in a progression" into a manageable sum over L-functions. It is the single most-used identity in the whole subject.

The two relations

Recall a Dirichlet character mod q is a homomorphism \chi \colon (\mathbb{Z}/q\mathbb{Z})^{*} \to \mathbb{C}^{*}, extended by \chi(n)=0 whenever \gcd(n,q)>1. There are exactly \varphi(q) of them, and the constant one that sends every unit to 1 is the principal character \chi_0. Everything below flows from a single fact: characters are group homomorphisms into the unit circle, so summing one over a whole group either reinforces to \varphi(q) or cancels to 0.

The two statements are mirror images: one sums a fixed character across all residues, the other sums a fixed residue across all characters. They are the "rows" and "columns" of the character table — hence the names — and each says a nontrivial sum of unit-circle values averages to nothing.

Why the row relation is true

If \chi = \chi_0 the sum just counts the units: \sum_{n} \chi_0(n) = \#\{n : \gcd(n,q)=1\} = \varphi(q). Now take \chi \neq \chi_0, so there is some unit b with \chi(b) \neq 1. Because n \mapsto bn just permutes the units, relabelling the summation index leaves the total unchanged:

S = \sum_{n \bmod q} \chi(n) = \sum_{n \bmod q} \chi(bn) = \chi(b)\sum_{n \bmod q}\chi(n) = \chi(b)\,S.

So (1 - \chi(b))\,S = 0, and since \chi(b) \neq 1 we must have S = 0. That "multiply the index by a group element and nothing changes" argument is the whole proof — and the identical idea, run over the dual group, proves the column relation. This is exactly the finite version of "\int_0^{2\pi} e^{ik\theta}\,d\theta = 0 unless k=0."

The combined form: an indicator for a progression

The column relation isolates the residue n \equiv 1. To isolate any target residue a (with \gcd(a,q)=1), apply it to n a^{-1} instead of n. Since \chi(na^{-1}) = \chi(n)\,\chi(a)^{-1} = \overline{\chi(a)}\,\chi(n) — a character's values are roots of unity, so its inverse is its conjugate — we get the master identity.

For \gcd(a,q)=1,

\frac{1}{\varphi(q)} \sum_{\chi \bmod q} \overline{\chi(a)}\,\chi(n) = \mathbf{1}\!\left[\, n \equiv a \pmod q \,\right] = \begin{cases} 1, & n \equiv a \pmod q, \\ 0, & \text{otherwise.} \end{cases}

Read the right-hand side slowly: this weighted average of characters is exactly the indicator function of the progression a \bmod q — it returns 1 on the class you want and 0 on every other class (and on everything sharing a factor with q, since then every \chi(n)=0). One tidy sum over \varphi(q) characters does the job that no single character could.

The payoff: filtering a sum

Now watch it work on a real sum. Take any function f and any target class a. Insert the indicator and swap the order of summation:

\sum_{n \equiv a \,(q)} f(n) = \sum_{n} \mathbf{1}[n \equiv a] \, f(n) = \frac{1}{\varphi(q)} \sum_{\chi \bmod q} \overline{\chi(a)} \sum_{n} \chi(n)\, f(n).

The left side — a sum restricted to one hard-to-describe progression — has become a small combination (\varphi(q) terms) of unrestricted twisted sums \sum_n \chi(n) f(n), each running over all n. That is the decisive move. If f(n) = \Lambda(n)/n^{s} or 1/n^s, each inner sum is a L-function L(s,\chi), an object with an Euler product, analytic continuation, and known zeros. Every question about primes in a progression is thereby refracted through the prism of characters into \varphi(q) questions about individual L-functions — precisely how Dirichlet proved his theorem, and how the prime number theorem for progressions is proved today.

Worked example: the column relation mod 5

Here q=5, so \varphi(5)=4 and the units are \{1,2,3,4\}. Since the group is cyclic of order 4 generated by 2, the four characters take values in the fourth roots of unity \{1, i, -1, -i\}. Writing each character by what it does to the generator 2, the full table is below (with i = \sqrt{-1}).

\chi(n) n=1 n=2 n=3 n=4 \sum_n \chi(n)
\chi_0 1 1 1 1 4
\chi_1 1 i -i -1 0
\chi_2 1 -1 -1 1 0
\chi_3 1 -i i -1 0
\sum_\chi \chi(n) 4 0 0 0

The rightmost column is the row relation: each nonprincipal row sums to 0, only \chi_0 sums to \varphi(5)=4. The bottom row is the column relation: summing down each n-column gives 4 at n=1 and 0 everywhere else. Check n=2 by hand: 1 + i + (-1) + (-i) = 0. Check n=3: 1 + (-i) + (-1) + i = 0. The imaginary parts cancel in conjugate pairs and the real parts cancel +1 against -1 — the tell-tale signature of unit-circle values pointing in balanced directions.

Now pick out n \equiv 2 \pmod 5

To isolate a=2 we weight by \overline{\chi(2)}. Reading the n=2 column of the table, the conjugates are \overline{\chi_0(2)}=1, \overline{\chi_1(2)}=\overline{i}=-i, \overline{\chi_2(2)}=-1, \overline{\chi_3(2)}=\overline{-i}=i. Evaluate the indicator \frac{1}{4}\sum_\chi \overline{\chi(2)}\,\chi(n) at, say, n=2 (should give 1) and at n=3 (should give 0):

n=2: \quad \tfrac14\big[\,1\cdot 1 + (-i)(i) + (-1)(-1) + (i)(-i)\,\big] = \tfrac14\big[1 + 1 + 1 + 1\big] = 1. \checkmark n=3: \quad \tfrac14\big[\,1\cdot 1 + (-i)(-i) + (-1)(-1) + (i)(i)\,\big] = \tfrac14\big[1 - 1 + 1 - 1\big] = 0. \checkmark

The weighting by the conjugate \overline{\chi(2)} rotates every character's value at n=2 back to +1 so they reinforce, while at any other residue the rotated values still point in balanced directions and cancel. That is the indicator in action: it lights up exactly on the class 2 \bmod 5.

The dual-group viewpoint

Step back and this is nothing but Fourier analysis on the finite abelian group G = (\mathbb{Z}/q\mathbb{Z})^{*}. The characters are precisely the elements of the dual group \widehat{G} = \operatorname{Hom}(G, \mathbb{C}^{*}), which for a finite abelian G is isomorphic to G itself (so |\widehat{G}| = |G| = \varphi(q)). Under the inner product \langle f, g \rangle = \frac{1}{\varphi(q)}\sum_{n} f(n)\overline{g(n)}, the characters are orthonormal:

\langle \chi, \psi \rangle = \frac{1}{\varphi(q)} \sum_{n \bmod q} \chi(n)\,\overline{\psi(n)} = \begin{cases} 1, & \chi = \psi, \\ 0, & \chi \neq \psi, \end{cases}

which is just the row relation applied to the character \chi\overline{\psi}. So the \varphi(q) characters are an orthonormal basis for the space of functions on G: any such function expands as a "Fourier series" f = \sum_\chi \hat f(\chi)\,\chi, and the indicator of a point a is exactly the expansion we wrote above. Characters are the pure frequencies; orthogonality is Parseval; picking out a progression is bandpass filtering. Everything analytic number theory does with progressions is this one idea, iterated.

Two traps snare almost everyone the first time. First, the sum runs only over \gcd(n,q)=1. Characters are defined to vanish on non-units, so a term with \gcd(n,q)>1 contributes nothing and the indicator is automatically 0 there — the identity says nothing about, and does nothing for, residues that share a factor with q. If you ever "find" the indicator lighting up on a non-coprime residue, you've made a slip. Second, you weight by the conjugate \overline{\chi(a)}, not by \chi(a). Get this backward and you build the indicator of a^{-1} instead of a — a genuinely different progression unless a \equiv a^{-1}. The conjugate is what rotates \chi(a)\chi(n) back to +1 when n \equiv a; drop the bar and the phases no longer line up.

Tempting, but impossible — and the reason is exactly why the whole machine has to be a sum. A single character \chi takes the same value on many different residues (mod 5, \chi_2 gives -1 at both 2 and 3), so no one character can tell those residues apart. It takes all \varphi(q) of them, weighted and averaged, for the values to interfere constructively at your target and destructively everywhere else. This is why Dirichlet needed the whole family of L-functions and not just one: each character sees a blurred, folded-up picture of the residues, and only the chorus resolves a single class. It's the same reason a single Fourier coefficient can't reconstruct a signal — you need the whole spectrum.

Why it matters

Character orthogonality is the hinge between arithmetic (residue classes, progressions) and analysis (L-functions, their zeros). Without it you cannot even write down the sum over primes in a progression as something a complex analyst can attack; with it, that sum becomes \frac{1}{\varphi(q)}\sum_\chi \overline{\chi(a)}\,(\text{something about }L(s,\chi)), and the entire apparatus of contour integration, Euler products, and zero-free regions comes to bear. The principal character contributes the "main term" (it behaves like the plain zeta function, giving the expected density 1/\varphi(q) of the primes), and every nonprincipal character contributes an "error term" controlled by the non-vanishing L(1,\chi)\neq 0. That clean split — main term from \chi_0, error from the rest — is orthogonality doing its work, and it recurs in almost every theorem about the distribution of primes in progressions.