The square of a k-th root of unity is a k/2-th root of unity

If we take the set of $k$ -th roots of unity (with $k$ even) and square each element, the resulting set will be a set of half the size. The new set will be the $\frac{k}{2}$ -th roots of unity.

For example, suppose $k = 6$ . The 6th roots of unity would be

\set{1,\omega,\omega^2,\omega^3,\omega^4,\omega^5}

If we square each element, we get the following set. Some elements have exponents greater than or equal to $k$ , but we will handle that in the next step.

\set{1^2,\omega^2,\omega^4,\omega^6,\omega^8,\omega^{10}}

We can then factor the exponents as follows:

\set{1^2,\omega^2,\omega^4,\omega^6,(\omega^6)\omega^2,(\omega^{6})\omega^4}

Since $\omega$ is a 6-th root of unity, $\omega^6\equiv1$ so we have:

\set{1^2,\omega^2,\omega^4,1,(1)\omega^2,(1)(\omega^4)}

Removing multiplication by $1$ , we get

\set{1^2,\omega^2,\omega^4,1,\omega^2,\omega^4}

Now replace all the duplicate terms with a single element:

\set{1,\omega^2,\omega^4}

The new set is half the size of the original, and each element is a 3-rd root of unity:

$1^3\equiv1$
$(\omega^2)^3=\omega^6\equiv1$
$(\omega^4)^3=\omega^{12}=\omega^6\omega^6\equiv1\cdot1=1$

If we plot the 6-th roots of unity on a circle, we can see that squaring “removes” every other element. We started with $\set{1,\omega,\omega^2,\omega^3,\omega^4,\omega^5}$ and ended with $\set{1,\omega^2,\omega^4}$

A diagram showing that squaring the 6-th roots of unity results in the 3-rd roots of unity

To reiterate, if we take the set of $k$ -th roots of unity, and $k$ is even, then square each element, we get a set of half the size with each element being the $\frac{k}{2}$ -th root of unity.

Some more examples:

If $k = 10$ and we square each of the 10-th roots of unity, we get a set of size five which are the fifth roots of unity.
If $k = 8$ and we square each of the 8-th roots of unity, we get a set of size four which is the fourth roots of unity.
If $k = 4$ and we square each of the 4-th roots of unity, we get a set of size two which is the 2-nd roots of unity.
If $k = 2$ and we square each of the 2-nd roots of unity, we get a set of size 1 which is just the element 1.

The last point is easily illustrated. The second roots of unity are square roots of 1, which are always $\set{1,-1}\equiv\set{1,\omega^{k/2}}$ . Squaring 1 results in 1 and squaring -1 results in 1. Equivalently, $(\omega^{k/2})^2=\omega^k\equiv1$ .

Example of squaring the 8-th roots of unity

Consider the subgroup of 8th roots of unity $\langle 9\rangle = \{1, 9, 13, 15, 16, 8, 4, 2\}$ in the finite field $\mathbb{F}_{17}$ . We square all elements of this subgroup as follows:

\begin{aligned} &1^2 = 1\pmod{17},\\ &9^2 \equiv 13\pmod{17},\\ &13^2 \equiv 16\pmod{17} ,\\ &15^2 \equiv 4\pmod{17},\\ &16^2 \equiv 1\pmod{17},\\ &8^2 \equiv 13\pmod{17},\\ &4^2 \equiv 16\pmod{17},\\ &2^2 = 4\pmod{17}. \end{aligned}

The set obtained after squaring is $\{1,13,16,4\}$ , which is precisely the subgroup of 4th roots of unity.

Here is a visualization of the roots of unity before and after squaring. We started with the set $\set{1, 9, 13, 15, 16, 8, 4, 2}$ and ended with the set $\set{1,13,16,4}$

A diagram showing that squaring the 8-th roots of unity results in the 4-th roots of unity

k must be even

If $k$ is odd, then there is no such thing as “half of the group” as an odd-sized set cannot be divided into two. For the purposes of NTT, we only deal with even-sized $k$ , so we aren’t interested in the case where $k$ is odd.

Proof of the claim that the new set is half the size

Let $\omega$ be a primitive $k$ -th root of unity with $k$ even. Let $\langle\omega\rangle$ be the subgroup generated by $\omega$ of order $k$ . We claim that $|\set{\omega^2|\omega\in\langle\omega\rangle}|=k/2$ .

The proof is actually quite simple and intuitive.

We established in an earlier chapter that $\omega^{i}$ and $\omega^{i+k/2}$ are additive inverses. Since $k$ is even, we can partition the group into two sets, the first one being $0...(k/2-1)$ and the second being $k/2...k-1$ :

\set{\omega^0,\omega^1,\omega^2,...}\quad\set{\omega^{k/2},\omega^{k/2+1},\omega^{k/2+2},...}

Those elements are congruent to the following representation:

\set{\omega^0,\omega^1,\omega^2,...}\quad\set{-\omega^0,-\omega^1,-\omega^2,...}

If we apply $f(x)=x^2$ to both sets, we get two sets with identical content and size $k/2$

\set{1,\omega^2,\omega^4,...}\quad\set{1,\omega^2,\omega^4,...}

Since the two sets are identical, the union of the two sets will be the same size, which is $k/2$ .

Proof that squaring a $k$ -th root of unity produces a $k/2$ -th root of unity

Suppose $a$ is a $k$ -th root of unity. We aim to show that $a^2$ is a $\frac{k}{2}$ -th root of unity, that is:

(a^2)^{\frac{k}{2}}\equiv 1

Let’s simplify $(a^2)^{\frac{k}{2}}$ :

(a^2)^{\frac{k}{2}} = a^{k}

Since $a^k\equiv1$ (because $a$ is a $k$ -th root of unity), it follows that $(a^2)^{\frac{k}{2}}\equiv 1$ .

Therefore, $a^2$ is indeed a $\frac{k}{2}$ -th root of unity.