Fundamental Theorem of Cyclic Groups

Introduction

This article introduces the Fundamental Theorem of Cyclic Groups.

The Fundamental Theorem of Cyclic Groups provides guarantees about the existence of subgroups of a desired order.

In the context of FRI protocols and the Fast Fourier Transform of polynomials over a finite field, we need multiplicative subgroups that have an order which is a power of two. The Fundamental Theorem of Cyclic Groups enables us to quickly determine if a particular finite field has a multiplicative subgroup with that order or not.

Subgroups

Given a group $(G, *)$, a subset $H$ of $G$ is a subgroup of $G$ if $(H, *)$ forms a group with respect to the group operation in $G$.

Example 1

The additive group $(Z_8 = \{0, 1, 2, 3, 4, 5, 6, 7\}, +)$ refers to the set of integers modulo 8, then $(\{0, 2, 4, 6\}, +)$ and $(\{0, 4\}, +)$ are subgroups of $Z_8$.

Order of a group

The order of a finite group $G$, denote by $|G|$, is the number of its elements. If a group is not finite, one says that its order is infinite.

Example 2

Consider the group $Z_8$ of the above example; then the order of group $Z_8$ is 8, means |$Z_8| = 8$ (since there are exactly 8 elements in the group). Moreover, the order of subgroup $H$ is 4. $|H| = 4$.

Cyclic Group

Powers of an element

If $g \in G$, the powers of element $g$, denoted by $\langle g\rangle$, is the set $\{g^k: k\in\mathbb{Z}\}$. For example, consider the group of non-zero integers under multiplication modulo 7, which is $G =\{1, 2, 3, 4, 5, 6\}$, then the powers of element $3$ in $G$ is as follows:

\[\begin{aligned} \text{Powers of $3$} = \langle 3\rangle = \{3^0, 3^1, 3^2, 3^3, 3^4, 3^5, 3^6, \dots\} \end{aligned}\]

Since:

\[\begin{aligned} &3^0 = 1,\\ &3^1 = 3,\\ &3^2 = 9 \equiv 2,\\ &3^3 = 9 * 3 \equiv 2 * 3 \equiv 6,\\ &3^4 = 9 * 9 \equiv 2 * 2 \equiv 4\\ &3^5 = 9 * 9 * 3 \equiv 2 * 2 * 3 \equiv 12 \equiv 5\\ &3^6 = 9 * 9 * 9 \equiv 2 * 2 * 2 \equiv 8 \equiv 1\\ \end{aligned}\]

How about $3^7$?

\[ 3^7 = 3^6 * 3 \equiv 1 * 3 \equiv 3\\\]

You can see for all $k \ge 7$, the element $3^k$ is equal to one of the $3^0, 3^1, 3^2, 3^3, 3^4, 3^5, 3^6$. Then,

\[\begin{aligned} \text{Powers of $3$} = \langle 3\rangle = \{1, 3, 2, 6, 4, 5\} \end{aligned}\]

Claim 1

Let $g\in G$, the set of powers of element $g$, forms a subgroup. In other words, $\langle g\rangle = \{g^k: k\in\mathbb{Z}\}$ is a subgroup of $G$.

Cyclic Subgroup and Generator

If $g \in G$, then the subgroup $\langle g\rangle = \{g^k: k\in\mathbb{Z}\}$ is called the cyclic subgroup of $G$ generated by $g$, If $G = \langle g\rangle$, then we say that $G$ is a cyclic group and that $g$ is a generator of $G$.

For example, if $G$ is any group, then $\{1\} = \langle 1\rangle$ is a cyclic subgroup of $G$.

Example 3

Consider the group of non-zero integers under multiplication modulo 7 which is $G =\{1, 2, 3, 4, 5, 6\}$. Since $\langle 3 \rangle = G$, then we say that $G$ is a cyclic group and $3$ is a generator of $G$.

Notation

Consider $d, n$ be integers, then if $d$ divides $n$, then we use the notation $d | n$. For example 3|6 but it is not true that 5|6.
$(F, +, .)$ is a field, we denote it by $F$.
$F^* = F\setminus\{0\}$.
$F_q$ is a field with $q$ elements.
When we say multiplicative subgroup $H$, means that $(H, .)$ is subgroup of $(F^*, .)$. Now we grasp where the multiplicative term in multiplicative subgroups comes from..

Theorem 1

If $F_q$ is a finite field with order $q$, then $(F^*_q, .)$ is a cyclic group of order $q-1$.

A cyclic group has a generator, therefore we know that some $g\in F^*$ exists such that

\[F^*_q = \{1, g^1, g^2, \dots, g^{q-2}\} = \langle g \rangle\]

Primitive Elements (Generators)

In field theory, a primitive element of a finite field $F_q$ is a generator of the multiplicative group of the field. The element $g$ in Theorem 1 is a primitive element in $F_q$.

The Python code below uses the galois library to identify primitive elements (generators) in $F_7$.

import galois
 
GF = galois.GF(7)
 
primitive_elements = GF.primitive_elements
print("Primitive elements:", primitive_elements)
# Primitive elements: [3 5]
 
# Alternatively, find a single primitive element
# suitable when there are a lot of primitive elements
primitive_element = GF.primitive_element
print("A primitive element:", primitive_element)
A primitive element: 3

The Fundamental Theorem of Finite Cyclic Groups

The fundamental theorem of finite cyclic groups makes three claims. Let $G$ be a finite cyclic group and $H$ be a subgroup of $G$.

$H$ is necessarily finite and cyclic (meaning $H$ has a generator).
The order of $H$ (the number of elements it has) is a factor of the order of $G$. In other words, the order of $H$ divides the order of $G$. Suppose the order of $G$ is 6. We automatically know a subgroup of order 5 does not exist since 5 does not divide 6.
If $n$ is the order of $G$ and $k$ divides $n$, then a subgroup of size $k$ necessarily exists. In fact, we can immediately find a generator for it. if $g$ is a generator of $G$, then $g^\frac{n}{k}$ is a generator for a subgroup of size $k$. This subgroup of size $k$ is equal to $\langle g^\frac{n}{k} \rangle$. We will show examples for this shortly.

Remark

Statement (2) of The Fundamental Theorem of Finite Cyclic Groups is actually true for any finite group $G$, whether or not it is cyclic. This result is Lagrange’s theorem.

Example 4

If $G = \langle g \rangle$ is any finite cyclic group of order $n$, and $\{1\}$ is a subgroup of order 1, then the generator of subgroup $\{1\}$ using the fundamental theorem is $g^{\frac{n}{1}} = g^{n}$. And in a cyclic group of order $n$, the generator $g$ to power $n$ is equal to element $1$. So, $g^n = 1$. Now we are going to generate the subgroup $\langle g^{\frac{n}{1}}\rangle$:

\[\langle g^{\frac{n}{1}}\rangle = \langle g^{n}\rangle = \langle 1\rangle = \{1\}\]

Consider group $G =\{1, 2, 3, 4, 5, 6\} = \langle 3\rangle$, non-zero integers under multiplication modulo 7, and $|G| = n = 6$. Then, the generator to power of size of the group, means $g^n = 3^6$ is equal to $1$ mod 7. So, for generating the subgroup of order 1, we have

\[\langle g^{\frac{n}{1}}\rangle = \langle g^{n}\rangle = \langle 3^6\rangle = \langle 1\rangle = \{1\}\]

Example 5

Consider the group of non-zero integers under multiplication modulo 7 which is $G =\{1, 2, 3, 4, 5, 6\} = \langle 3\rangle$, and $|G| = 6$. We have that $g = 3$ is a generator for $G$ in our example. Using the fundamental theorem of finite cyclic groups, we know that there is a subgroup of order 3 because $3|6$.

As stated in the third statement of the Fundamental Theorem of Finite Cyclic Groups, since $3 | 6$, then we can find the generator of this group as $3^{\frac{n}{k}} = 3^{\frac{6}{3}} = 3^{2} = 9 \equiv 2$. Therefore, $2$ is a generator for the subgroup of order 3.
The elements of this subgroup are, $\langle 2 \rangle = \{1, 2, 4\}$ \[\begin{aligned} &\langle 2 \rangle = \{2^0, 2^1, 2^2, 2^3, 2^4, 2^5, 2^6, \dots\} = \{1, 2, 4, 8\equiv \boxed{1}, 16\equiv \boxed{2}, 32\equiv \boxed{4}, 64 \equiv \boxed{1} \dots\} \end{aligned}\] You can see that in $\langle 2 \rangle$ the elements $1, 2, 4$ repeat when power is raised. So $\langle 2 \rangle = \{1, 2 , 4\}$.

Example 6

Consider Example 5 assumptions:

Since $6 | 6$, we have a subgroup of order 6

\[\langle 3^{\frac{n}{k}} = 3^{\frac{6}{6}} = 3^{1} = 3 \rangle =\{1, 2, 3, 4, 5, 6\} = G\]

Since $1 | 6$, we have a subgroup of order 1

\[\langle 3^{\frac{n}{k}} = 3^{\frac{6}{1}} = 3^{6} \equiv 1 \rangle =\{1\}\]

Since $2 | 6$, we have a subgroup of order 2

\[\langle 3^{\frac{n}{k}} = 3^{\frac{6}{2}} = 3^{3} \equiv 6 \rangle =\{1, 6\}\]

Since $3 | 6$, we have a subgroup of order 3

\[\langle 3^{\frac{n}{k}} = 3^{\frac{6}{3}} = 3^{2} \equiv 2 \rangle =\{1, 2, 4\}\]

Order of element

If $g$ is an element of a group $G$, then the order of element $g$ is equal to the order of subgroup $\langle g \rangle$. So, $\mathrm{ord} (g) = |\langle g \rangle|$. Colloquially, we can think of $\mathrm{ord}(g)$ as being the number of unique elements we get if we repeatedly multiply $g$ by itself.

Corollary 1

A useful corollary is that we can quickly check if a group of a certain size exists or not by listing all the divisors of n. For example, let us consider the field $F_{41}$, which has a multiplicative group $F_41^*$ with order 40. Then, we can quickly check that $F_{41}$ has a subgroup of size 8 because 8 divides 40. For another example, consider the field $F_{17}$, which has a multiplicative group $F_17^*$ with order 16. $F_{17}$ has a subgroup of size 8 because 8 divides 16, also has a subgroup of size 4, because 4 divides 16, and you can guess $F_{17}$ also has a subgroup of size 2.

To find the generator for that subgroup, however, is a different question, which we answered in the statement (3) of The Fundamental Theorem of Finite Cyclic Groups.

All In One Example

Consider field $F_{17} =\{0, 1, 2, \dots, 16\}$. For a given $n$ we want to find a multiplicative subgroup of order $n$ in $F_{17}$ using the fundamental theorem of finite cyclic groups.

The generator of $F^*_{17}$

Recall from Theorem 1 the $F^*_{17}$ is a cyclic group. We are proving that $F^*_{17} = \langle 3 \rangle$:

\[\begin{aligned} &3^0 = \boxed{1},\\ &3^1 = \boxed{3},\\ &3^2 = \boxed{9},\\ &3^3 \equiv 9 * 3 \equiv \boxed{10},\space\space (27 - 17 = 10)\\ &3^4 \equiv 10 * 3\equiv \boxed{13},\space\space(30 - 17 = 13)\\ &3^5 \equiv 13 * 3 \equiv \boxed{5},\space\space(39 - 2*17 = 5)\\ &3^6 \equiv 5 * 3 \equiv \boxed{15},\\ &3^7 \equiv 15 * 3 \equiv \boxed{11},\space\space(45 - 2*17 = 11)\\ &3^8 \equiv 11 * 3 \equiv \boxed{16},\space\space(33 - 17 = 16)\\ &3^9 \equiv 16 * 3 \equiv \boxed{14},\space\space(48 - 2*17 = 14)\\ &3^{10} \equiv 14 * 3 \equiv \boxed{8},\space\space(42 - 2*17 = 8)\\ &3^{11} \equiv 8 * 3 \equiv \boxed{7},\space\space(24 - 17 = 7)\\ &3^{12} \equiv 7 * 3 \equiv \boxed{4},\space\space(21 - 17 = 4)\\ &3^{13} \equiv 4 * 3 \equiv \boxed{12},\\ &3^{14} \equiv 12 * 3 \equiv \boxed{2},\space\space(36 - 2*17 = 2)\\ &3^{15} \equiv 2 * 3 \equiv \boxed{6},\\ &3^{16} = 6 * 3 \equiv \boxed{1},\space\space(18 - 17 = 1) \end{aligned}\]

How about $3^{17}$?

\[ 3^{17} = 3^{16} * 3 \equiv 1 * 3 = 3\\\]

You can see for all $k \ge 17$, the element $3^k$ is equal to one of the $3^0, 3^1, 3^2, \dots, 3^{16}$.

Then $\langle 3 \rangle = \{1, 2, \dots, 16\} = F^*_{17}$.

This generator can be found in python code with galois.primitive_elements

import galois
 
GF = galois.GF(17)
 
primitive_element = GF.primitive_element
print("A primitive element:", primitive_element)
# A primitive element: 3

Using The Fundamental Theorem of Finite Cyclic Groups

Suppose we want to know if a multiplicative subgroup of order 4 in the finite field $F_q = F_{17}$ exists. Note that the multiplicative group of $F_q$ has size $q-1$. Then, for $F_{17}$ we have multiplicative group $F_{17}^*$ with $q-1 = 17-1 = 16$ elements. Recall from the fundamental theorem of finite cyclic groups that since $n|q-1$, explicitly $4|16$, then $g^{\frac{q-1}{n}}$ is a generator and $\langle g^{\frac{q-1}{n}}\rangle$ is subgroup of size 4.

\[g^{\frac{q-1}{n}} = 3^{\frac{16}{4}} = 3^4 \equiv 13\]

is a generator for subgroup of size 4 in $F^*_{17}$ and

\[\langle 13 \rangle = \{13^0 = \boxed{1}, 13^1 = \boxed{13}, 13^2\equiv\boxed{16}, 13^3\equiv\boxed{4}, 13^4\equiv\boxed{1}, 13^5\equiv\boxed{13}, \dots\}\]

explicitly $\{1, 13, 16, 4\}$ is the subgroup.

Summary

The goal is to find the multiplicative subgroups of size $n$ in the field $F_q$. Recall from the fundamental theorem of cyclic groups $F_q$ has a subgroup of size $n$ if and only if $n|q-1$ and the generator of this subgroup is $g^{\frac{q-1}{n}}$ which $g$ is generator of $F^*_q$.

shadow-write-up roots-of-unity-v1