Lagrange's Theorem through the algorithmic lens

Groups lie at the heart of many cryptographic constructions. In this post, we revisit the classic Lagrange’s theorem through a more algorithmic lens. Largange’s theorem is a simple structure theorem that will be useful for many more advanced results.

Recall that a group is a non-empty set $G$ and a function $f: G \times G \to G$ (often denoted as a binary operator $\cdot$) such that:

• Associativity: $\forall a,b,c \in G, \ (a \cdot b) \cdot c = a \cdot (b \cdot c)$
• Identity: $\exists e \in G, \ \forall a \in G, \ a \cdot e = e \cdot a = a$
• Inverse: $\forall a \in G, \ \exists b \in G, \ a \cdot b = b \cdot a = e$

We denote the identity element as $e$, and often use $a^{-1}$ to denote the inverse of $a$.

A subgroup $H \subseteq G$ is a subset that forms a group under the same operation.

For a finite group $G$, we define the order of $G$, written $\lvert G\rvert$, as the number of elements in $G$.

Given a subgroup $H$ and an element $g \in G$, the left coset of $H$ by $g$ is the set:

Each left coset is a “shifted copy” of $H$ in the group $G$. These cosets will be the main building blocks in our constructive proof of Lagrange’s Theorem.

Lagrange’s Theorem

Theorem:
If $G$ is a finite group and $H$ is a subgroup of $G$, then:

In words: the order of any subgroup divides the order of the group.

An Algorithmic Perspective

Let’s take a constructive approach. Suppose we know all elements of a subgroup $H$, and want to explore the entire group $G$ by applying operations with elements from $H$. We’ll build a partition of $G$ using left multiplication.

Algorithm: LagrangeCosetCount(G, H)

# Input: finite group G, subgroup H
# Output: the number k of disjoint left cosets of H in G

C = set(G)    # Elements of G not yet covered
k = 0         # Number of cosets constructed

while C:
    g = next(iter(C))               # Pick an uncovered element
    coset = {g * h for h in H}      # Construct a new left coset
    C -= coset                      # Remove all its elements from the not yet covered set
    k += 1                          # Count this coset

return k

At termination, the algorithm has found $k$ disjoint left cosets of $H$ in $G$, and each has exactly $\lvert H \rvert$ elements. Therefore:

Proof

We split the argument into three claims that correspond directly to the logic of the algorithm.

Claim 1: Each coset $gH = {g \cdot h : h \in H}$ has exactly $\lvert H \rvert$ elements.

Proof: The map $f: H \to gH$ defined by $f(h) = g \cdot h$ is injective (because if $g \cdot h_1 = g \cdot h_2$ then $h_1 = h_2$ by left-cancellation in the group) and surjective by definition. So it’s a bijection, and $\lvert gH \rvert = \lvert H \rvert$.

Claim 2: For any $g_1, g_2 \in G$, the cosets $g_1H$ and $g_2H$ are either disjoint or equal.

Proof: Suppose $x \in g_1H \cap g_2H$. Then there exist $h_1, h_2 \in H$ such that $x = g_1h_1 = g_2h_2$. Rearranging gives $g_2^{-1}g_1 = h_2h_1^{-1} \in H$, so $g_1 \in g_2H$, and thus $g_1H = g_2H$.

This shows that no element of $G$ can appear in more than one coset. So the sets built by the algorithm are disjoint. This is the core essence of the Theorem’s proof.

Claim 3: The algorithm terminates after finitely many steps and produces a partition of $G$.

Proof: Initially, $C = G$. In each iteration, the algorithm selects an element $g \in C$ and removes $\lvert H \rvert $ elements from $C$ by adding $gH$. Since the cosets are disjoint and $G$ is finite, this process must terminate. When $C = \emptyset$, the algorithm has covered all of $G$ with $k$ disjoint cosets, each of size $\lvert H \rvert $. Therefore:

This proves Lagrange’s Theorem constructively.

This post will serve as a building block for more advanced results, like showing that the set of $n$th roots of unity in a finite field forms a cyclic group — a structure essential in FFT-based cryptographic protocols.