Equal number of $n$th roots of unity within character values $f_1(a), \dots, f_m(a)$. (Apostol exercise 6.12 Intro to ANT)

Question

This problem is taken from Exercise 6.12 from Apostol's "Introduction to Analytic Number Theory".

Verbatim, the problem states

Let $f_1, \dots, f_m$ be the characters of a finite group $G$ of order $m$, and let $a$ be an element of $G$ of order $n$. Theorem 6.7 shows that each number $f_r(a)$ is an $n$th root of unity. Prove that every $n$th root of unity occurs equally often among the numbers $f_1(a), f_2(a), \dots, f_m(a)$.

Theorem 6.7 above simply states that every $f_r(a)$ is an $n$th root of unity.

The case of $n = 1$ is trivial, I'll assume $n > 1$ throughout the rest of this question. Apostol gives as a hint that evaluation of the sum

$$\sum_{r=1}^m \sum_{k=1}^n f_r(a^k) e^{-2\pi ik/n}$$

in "two different ways" shows how many $f_r(a) = e^{2\pi i/n}$. The sum above evaluates to $m$, since

$$S = \sum_{r=1}^m \sum_{k=1}^n f_r(a^k) e^{-2\pi ik/n} = \sum_{k=1}^n e^{-2\pi ik/n} \sum_{r=1}^m f_r(a^k), $$

and, by Theorem 6.13,

$$\sum_{r=1}^m f_r(a^k) = \begin{cases} m & k = n \\ 0 & \text{otherwise}. \end{cases}$$

Therefore, $S$ vanishes for $k = 1, 2, \dots, n-1$, which implies $S = me^{-2\pi i} = m$.

The "second way" to evaluate $S$ is to notice that the sum

$$\sum_{k=1}^n [f_r(a)e^{-2\pi i/n}]^k$$

equals $n$ only when $f_r(a) = e^{2\pi i/n}$, otherwise, $f_r(a)e^{-2\pi i/n}$ is some non-one $n$th root of unity $\omega$ and the sum above equals

$$\sum_{k=1}^n \omega^k = 0$$

by properties of roots of unity. Thus, since $S = m$, if $\alpha$ represents the number of $f_r(a) = e^{2\pi i/n}$, then $m = \alpha n$, or $\alpha =m/n$.

However, what would lead one to consider the sum $S$ in the first place? Where did it come from? It seems almost as if $S$ appeared out of "thin air". Is there another way to prove this statement without the evaluation of $S$?

Thanks in advance!

Answer 1

Here is a proof, using only facts from Chapter 6 of Apostol, and using its notation. Let $a\in G$ have order $n$.

The characters form a group under multiplication. Therefore, if $f_1,\dots,f_r$ are the characters, then multiplying by $f_i$ simply permutes the characters. In particular, for any fixed $a\in G$, it permutes the values in the set $$X=\{f_j(a)\mid 1\leq j\leq r\}.$$ This is the set we wish to prove is simply each $n$th root of unity appearing $r/n$ times. Suppose that $f_i(a)$ is a primitive $n$th root of unity. Then multiplying by $f_i$ has the effect of multiplying all elements in the set $X$ by $f_i(a)$, a primitive $n$th root of unity. The only way such a multiplication can preserve $X$ is if $X$ is uniform.

Thus we must check that there is such an element $f_i$. If not, then all of the $f_j(a)$ (since it is closed under multiplication as the $f_i$ form a group) must be all $m$th roots of unity for some $m$ strictly dividing $n$ (as they are already $n$th roots of unity).

But now, $a^{n/m}$ is a non-trivial element, and $f_i(a^{n/m})=1$ for all $1\leq i\leq r$. By Theorem 6.10 from Apostol (column orthogonality relation), $a^{n/m}$ is the identity, a contradiction.

Answer 2

I think I found a means to build up to the sum Apostol hints at without changing the method of proof wildly or without mentioning techniques beyond that of a pre calculus level.

Consider the sequence $g_r = f_r(a)e^{-2\pi i /n}$. Note that $g_r = 1$ only when $f_r(a) = e^{2\pi i /n}$. Otherwise, since $f_r(a)$ is some $n$th root of unity, $g_r$ would be some root of unity not equal to $1$. In a way, $g_r$ represents a sort of indicator function. However, we cannot really distinguish between the roots of unity (that is, we can't really do much with only $g_r$, I think).

In order to make $g_r$ more applicable to the problem, sum over its $n$ powers:

$$G_r = \sum_{k=1}^n g_r^k$$

in order to utilize the property that

$$\sum_{k=1}^n \omega^k = \begin{cases} n & \omega = 1 \\ 0 & \omega \neq 1, \end{cases}$$

where $\omega$ is an $n$th root of unity.

The newly defined $G_r$ is more revealing in terms of the value of $g_r$, and since $g_r$ is an $n$th root of unity,

$$G_r = \begin{cases} n & g_r = 1 \\ 0 & g_r \neq 1, \end{cases}$$

from which it can be ascertained that

$$G_r = \begin{cases} n & f_r(a) = e^{2\pi i/n} \\ 0 & f_r(a) \neq e^{2\pi i/n}. \end{cases}$$

Summing $G_r$ over $1 \leq r \leq m$ yields that

$$\sum_{r=1}^m G_r = n\alpha,$$

where $\alpha$ is the number of times $f_r(a) = e^{2\pi i /n}$. In fact, the sum above is $S$ as defined in my post.

I personally think that this is intuitive enough without more intense jargon and concepts that I haven't learned yet. However, I think such a line of reasoning may have been the initial intuition of the final sum (although I personally think the sum Apostol gives may have been too revealing, I wanna have fun struggling!!)

To complete the proof, generalize $g_r(t) = f_r(a)e^{-2\pi i t/n}$ and define everything that follows similarly to show that the number of $f_r(a) = e^{2\pi i t/n}$ equals $\alpha(t)$, where

$$S(t) = m = n\alpha(t).$$