Lagrange's Theorem

What is Lagrange's Theorem?

Over the past year I've gone down a deep dive of cryptography of which group theory is a pivotal dependency. One theorem I've seem that are leaned on heavily when using popular cryptographic objects like finite fields is Lagrange's Theorem.

Simply put Lagrange's theorem states:

If $H$ is a subgroup of a finite group $G$. Then the order of $H$ divides the order of $G$.

Or in terse mathematical notation:

This a pretty elegant finding! Thanks Lagrange!

To understand why this is true we'll go through four checkpoints.

1. What is a coset?
2. When are cosets the same?
3. Why cosets are equal xor disjoint?
4. Why cosets split the group?

What is a coset?

While the word "coset" seems like a fancy unrelated term, but in reality it's a very simple concept that will be core in proving Lagrange's Theorem.

If $H$ is a subgroup of $G$, then a coset is the set of elements where $g$ is applied on $H$ where $g$ is an element of $G$.

In other words, the cosets of a subgroup $H$ can be thought of as applying the group operation as a mapping function on the elements of $H$ with the elements of $G$

For a more terse math notation, cosets can be described like this:

Note: There is a notion of "left" and "right" cosets, but for this post we'll be assuming $G$ is abelian.

Let's make this a little more concrete with an example. Lets consider the cosets of the group $\Z/24\Z$ with the subgroup generated by $4$ via group addition.

Here are some things worth noticing about this table:

1. $0 + H$ and $4 + H$ are the same! I left this in intentionally to point out the fact that if we keep incrementing our added term to the $0 + H$ coset, we eventually wrap around with what we started with! Is this a coincidence or is this always the case?
2. The size of all the cosets are the same. This makes sense because when we have a subgroup and we add a number to it, it can be thought of as a "translation" of all the elements, hence the sizes will all the same as $0 + H$. But how do we know the elements of a coset of any subgroup have no shared elements? If this were the case this could result in different coset sizes!
3. All the elements of the cosets contain all the elements of the group! Does this mean that all the cosets split the group?

It's not that obvious now, but proving that these observations are always true will give us all the information needed to prove Lagranges Theorem!

When are cosets the same?

In our first observation we saw the same coset twice, this begs the question when are any two cosets equal? We will show that if two cosets have a single element in common, then all their elements will be in common, making them the same. In terse math notation we can write this assumption as:

One of the most effective ways to show that two cosets are equal is by showing that if each coset shares an element, then it's a subset of the other. Let's break it down.

The first thing we can observe is that if $a \in H b$, then there must exist an element $h_1$ such that:

This means we can take our first coset $H a$, select a random element $x$ from it, and rewrite it as $x = a h_{2}$. By doing this and rewriting in terms $a$ like so:

By doing this reduction, we know that any random element of $H a$ is an element of $H b$. Now we need to show the inverse is true and that any random element of $H b$ is an element of $H a$.

We can do this by leveraging the property of inverses of groups to rewrite $a = b h_{1}$ into $a h_1^{-1} = b$. With this we can show that for some $y \in H b$ the follow reduction can be done:

This implies that if we select any element from either coset, it must belong to the other, implying that all the elements of one coset must be in the other, or in other words, they are the same!

Why cosets are equal xor disjoint?

We showed when cosets are equal, but in order to show our second observation is always the case, we need to show that if two cosets don't share an element, then they are disjoint (no shared elements). Luckily we can build on our previous coset equality result to show this.

To show that cosets are disjoint we will assume that the intersection of $H a$ and $H b$ is empty, but if there is a shared element, they are equal. With this assumption we can do the following:

Here we show that if we pull an element from the intersection of two cosets, the coset generated by $a$ must be in $H b$. But this should look familiar because we just proved above that if $a \in H b$, then both cosets must be equal! This implies that if there are shared elements between both cosets, they must be equal which also implies if they don't have common element(s), they have nothing in common.

Why do cosets split the group?

Our last observation to prove is that all cosets of a group split the group. To show this is true, we just need to ensure that every element $g \in G$ belongs to some coset $H g$. Luckily this is simple to show:

Since $H$ is a subgroup, it must have an identity element. Then we can create the coset $H g$ of which $e g$ must be an element. And since applying the group operation with the identity element returns the applied element, we know that $g$ will always belong the coset it generates, meaning every element in $G$ belongs to a coset.

Lagrange's Theorem

Now that we have all the component information for Lagrange's Theorem, we can move forward in proving it. We showed in the beginning that the theorem can be stated as:

To reach this conclusion we will start with our previous result that all the cosets split the group, meaning by "unioning" all the cosets we reconstruct the original group:

Keep in mind there will be some integer $n$ number of cosets. If we transition to thinking about orders, then the total order of the group will be the sum of the number of elements of the cosets:

But since we know that all cosets of the subgroup are the same size as the subgroup, we can rewrite this as:

And we're done! This shows that the order of a group $G$ is a multiple of the order of a subgroup $H$ which is functionally the same as saying the order of the subgroup divides the order of the group!

This incredible result attributed to Lagrange means that just by knowing the order of a group allows us to infer information about the order of subgroups (and vice versa). But one of the most important details to keep in mind about this proof is that just because the order of a subgroup must divide the order of the group, it doesn't guarantee a subgroup of a dividing order exists. In essence this is a "one way" proof stating that any subgroups that exist will divide the order of the group.

Downstream implications

This theorem has large implications for the rest of group theory. For example if we consider groups that are of prime order $p$ ... well by definition nothing divides it except itself and one, so the only subgroups that can exist are the identity element and the group itself! This type of group has a special name, a "cyclic" group because any non identity element of the group can generate the rest of the group.

There are also many practical applications of Lagrange's Theorem. For example in the ZKHACK 2021 hackathon in the second puzzle, participants need to leverage Lagrange's Theorem to break the discrete log of an unsafe group with small prime cofactors.

Thanks for reading! Stay tuned for breakdowns of more group theory theorems like the primitive root theorem, and maybe more regarding implementing ECC pairings 😮!