Orthogonality of Roots of Unity

The sum of powers of the $k$-th roots of unity generated by a primitive $k$-th root of unity is either zero or $k$. We call this property the orthogonality of roots of unity. We will directly leverage this property in the next chapter.

We first illustrate this property through examples, so the reader becomes familiar with it. Then we will prove it in general.

The sum of powers of roots of unity

Consider the $k$-th roots of unity generated by a primitive $k$-th root of unity $\omega$:

If we take this list of elements and raise each element to a power $m$, we obtain another list:

The goal of this chapter is to show what happens when we sum all the elements of this new list. In other words, we want to calculate the value of the sum $s$ below for any $m$:

Consider the $4$th roots of unity in $\mathbb{F}_{17}$ (though any field with a primitive $4$th root of unity would work). For a primitive root $\omega$, these roots are

or, using that $\omega^2 \equiv -1$ in this case, they are

Let us raise these elements to some exponent $m$, say $m=3$:

We can simplify some of these elements by noting that $(-1)^3 = -1$ and $(-\omega)^3 = - \omega^3$.

Thus, the same list can be written as

The sum of these elements is zero, since

As another example, let us start with the 4th roots of unity in $\mathbb{F}_{17}$ again, but now raise each element to the power of 8.

This yields the following elements:

Since $8$ is even, we have $(-1)^8 = 1$ and $(-\omega)^8 = \omega^8$.

Also, remember that for the $4$th roots of unity, $\omega^4=1$. Thus, $\omega^8 = (\omega^4)^2 = 1^2 = 1$.

Therefore, our list simplifies to

The sum of the elements is

In the examples above, when $m$ is not a multiple of $k$ $(k=4,m=3)$, the sum is zero, but when $m$ is a multiple of $k$ ($k=4,m=8$), the sum is $k$. This is true in general.

We will show and prove the following:

1. If the power $m$ is not a multiple of $k$, the sum is zero.
2. Otherwise, if $m$ is a multiple of $k$, the sum is $k$.

Before proving this fact in general, let us see one more example.

8th roots of unity in $\mathbb{F}_{17}$

Consider the $8$th roots of unity in $\mathbb{F}_{17}$. They can be written as

where we used that $\omega^4 \equiv -1$ for a primitive $8$th root of unity $\omega$.

If we raise each element of this list to a power $m$ that is not a multiple of $8$ and sum all the elements, the result is zero. Otherwise, if $m$ is a multiple of $8$, the sum is $8$.

The new list is given by

Let us check the possible cases.

Case 1: $m$ is not a multiple of $8$

Let us consider the case $m=2$. The list is

It can be written as

Using the fact that $\omega^4 \equiv -1$, the list becomes

Summing these elements, we obtain

Exercise: Show that the sum vanishes for $m=3$ and $m=4$.

Case 2: $m$ is a multiple of 8

Let us consider the case where $m=16$. Then we obtain the new list

or

We also have that:

Since we know that $\omega^{8} \equiv 1$ for any primitive 8th root of unity, the list is actually

and the sum of all terms is $8$.

Sum of the powers of the $k$-th roots of unity

Now let us prove in general what we have shown through examples.

Theorem. Consider all the $k$-th roots of unity generated by a primitive $k$-th root of unity $\omega$. The sum of the powers of these $k$-th roots of unity is:

1. zero if the power is not a multiple of $k$;
2. $k$ if the power is a multiple of $k$.

Below, we will prove the two cases separately.

Case (1): Proof that the sum is zero when the exponent is not a multiple of $k$

Consider the $k$-th roots of unity, each raised to a power $m$ that is not a multiple of $k$:

We want to calculate the sum

This sum can be written as

We can use the fact that $(\omega^i)^m = (\omega^m)^i$ to rewrite the sum as

The formula above is a geometric series, that is, a sum of successive powers of the same element:

A geometric series of this form satisfies

To prove that the above fraction equals zero, we must first show that the denominator is non-zero and then that the numerator equals zero.

The fact that $m$ is not a multiple of $k$ is crucial here. Recall the definition of a primitive $k$-th root of unity: it is an element $\omega$ such that $\omega^k \equiv 1$, but $\omega^r \neq 1$ for any $0 \leq r <k$.

Thus, for primitive $k$-th roots of unity $\omega$, only powers of $\omega^k$ are equal to $1$, such as $(\omega^k)^0, (\omega^k)^1, (\omega^k)^2$, and so on.

Since $m$ is not a multiple of $k$, $\omega^m$ is not of the form $\omega^{nk}$ for any integer $n$, and therefore $\omega^m \neq 1$. Thus, the denominator $\omega^m-1$ of the fraction above is nonzero.

Let us now consider the numerator $(\omega^m)^k - 1$. It can be written as $(\omega^k)^m - 1$.

Since $\omega$ is a primitive $k$-th root of unity, we have $\omega^k = 1$, and the numerator becomes

Since the numerator is zero and the denominator is nonzero, the entire sum is zero.

In the next section, we will study the case where the exponent $m$ is a multiple of $k$.

Case (2): Raising each element by an exponent that is a multiple of $k$

In this section, we will show that the sum of the $k$-th roots of unity raised to a power $m$ that is a multiple of $k$ is not zero, but rather $k$.

Consider the $k$-th roots of unity

Let us raise each element in this list to some power $m$:

Since $(a^b)^c = (a^c)^b$ , we can rearrange each term above as follows:

Now consider the case in which $m$ is a multiple of $k$, that is, $m=kn$ for some $n$. Thus, our list can be written as

Since $\omega^{nk} = (\omega^k)^n$, we obtain the list

Using $\omega^k \equiv 1$, the list consists of the number 1 raised to some power:

or simply

Since there are $k$ elements in the list, the sum is

Combining the two properties

An elegant and convenient way to express both properties is the following:

Here the summation ranges from the first term, $\omega^0$, to the last, $\omega^{k-1}$.

The inner product of two lists of $k$-th roots of unity

In this section, we will rewrite our relation obtained above in a form that is more suitable for use in the following chapters.

More precisely, we will write it as

First, let us show that these two forms are the same, and then motivate the second one.

The two forms are equivalent

If $r$ is congruent to $s$ mod $k$ (second form), then $r-s = nk$ for some integer $n$.

Thus, we are saying that $r-s$, which in the first form is written as $m$, is a multiple of $k$. This is the same as stating that $m$ is a multiple of $k$.

The reason for using $r$ and $s$ in the second form is that we will consider the inner product of two vectors, each consisting of powers of the roots of unity.

The inner product of two vectors of roots of unity

Let us consider two vectors of $k$-th roots of unity. The first vector, $A$, is raised to the power $r$ and has the form

The second vector, $B$, is raised to the negative exponent $-s$ and has the form

Note: Raising the primitive $k$-th root of unity to a negative power is not a problem. We can write $\omega^{-s} = (\omega^{-1})^s$, where $\omega^{-1}$ is the multiplicative inverse of $\omega.$

Since $\omega^{k} = 1$, multiplying both sides by $\omega^{-1}$ gives $\omega^{-1} = \omega^{k-1}$. Raising both sides to the power $s$, we obtain $\omega^{-s} = \omega^{(k-1)s}$ .

The inner product of vectors $A$ and $B$ is

Equivalently, this can be written as

In a compact notation, the inner product of $A$ and $B$ can be written as

Therefore, the formula

can be understood as follows: the inner product of two vectors whose entries are powers of $k$-th roots of unity is either $k$ or zero, depending on whether the exponents $r$ and $s$ are congruent modulo $k$. We will use this fact in the following chapters.

This article is part of a series on the Number Theoretic Transform in our ZK Book