Have you ever wondered what restrictions symmetries inside bigger symmetries have to obey?

In this article, we will dive into the beginning of subgroup theory by proving a result first discovered in the 18'th century by the brilliant mathematician Joseph Louis Lagrange.

In fact, he is so popular that the French call him French and the Italians call him Italian, but I will leave that discussion to the respective countries and simply admire his beautiful (and non-demographic) mathematics…

When I first heard about the concept of a subgroup, I imagined a fractal-like image of a pattern inside a bigger pattern or a repeated kind of tiling inside a bigger tiling. It turns out that there are some quite interesting restrictions connecting group theory and symmetry to the field of number theory.

When symmetries get complicated or are somehow hard to visualize for us humans (because of our brain's limited powers due to (not enough) evolution) we need a mathematical tool to understand them. These symmetries might then contain other “closed” symmetries inside of them which mathematicians like to study.

It is a little like trying to understand numbers by studying the compositions of numbers in terms of prime numbers. Sometimes, the only way to understanding something is to break it down and understand its parts.

What was (maybe) a bit surprising was that the theory of these subsymmetries (called subgroups) led to even more beautiful facts than one would have first thought.

In the last article of mine: Group Theory, we discussed the basics of groups and touched upon the concept of homomorphisms.

Homomorphisms will continue to play an important role throughout this article and the field in general. However, this time we will dive into the concept of subgroups a little further.

Oh.. and then we shall generalize what we mean by even and odd numbers.

Relations

The first thing I need to introduce to you is the concept of a relation on a set.

We discussed it a little in the last article, but in order to understand subgroups, we really need to take a closer look at that. It is always helpful to keep some examples in mind, so I will investigate a special kind of arithmetic with you along the way.

There are many levels in relations. We don’t need the most technical/low level in this article, so I won’t talk about relations as cartesian products but instead, we will see it from a higher perspective where you can view a relation on a set as a statement involving elements of the set.

For example, equality is a relation we use in number sets like e.g. the whole numbers. We may state that 1 = 1.

We can also express a predicate like x = y which might be true and might be false.

Note that x = y means the same as y = x. We say that the relation is symmetric. We also always have that x = x. This is called reflexivity. Last but not least, for equality, we have the following property:

• if x = y and y = z then x = z.

This is called transitivity.

To be more general, if a relation ~ on a set A satisfies all the above three properties i.e. If

• a ~ a
• a ~ b if and only if b ~ a
• If a ~ b and b ~ c then a ~ c

Then ~ is called an equivalence relation on A.

Both = (equality) and ≡ (congruence mod n) are equivalence relations on the whole numbers ℤ.

There are of course many other relations but for this article, we only need to understand equivalence relations.

Equivalence Classes

Once we have a well-defined equivalence relation on a set, this relation will divide up the set in a natural way.

For example, say we are interested in remainders when we divide numbers by 7. What kind of patterns show up?

Well, from 0 to 6 the remainder is of course the number itself. But then 7 has remainder 0 and 8 has remainder 1 and so on.

That’s very familiar to most humans because many of our systems have this cyclic nature. That 1300 hours is the same as 1 PM is really because 13 ≡ 1 (mod 12) or said differently because the remainder of 13 when we divide by 12 is 1 and of course there are 12 hours on a clock.

Another example of this is that the same date next year will (typically) land on the next day of the week because there are 7 days on a week and 365 has remainder 1 when we divide by 7.

This way of calculating is called modular arithmetic and it is very important in number theory as well as cryptography and group theory.

This remainder calculation gives an equivalence relation on the whole numbers. In this case, we say that two numbers n and m are equivalent written n ≡ m (mod 7) if and only if they have the same remainder when we divide them by 7.

We can state this another way.

n ≡ m (mod 7) if and only if 7 divides (n - m).

Sometimes I write “|” instead of “divides”.

An equivalence class is a set containing all elements that are related to a specific element.

For example, the equivalence class of 0 in our example typically denoted [0] (sometimes with a subscript of 7) is {…, -14, -7, 0, 7, 14, …} i.e. it consists of all the numbers divisible by 7. In the same way, [1] = {…, -13, -6, 1, 8, 15, …}.

Notice that all the elements in the equivalence classes differ pairwise by exactly a multiple of 7.

There are exactly 7 equivalence classes with respect to this relation.

There is of course nothing special about the number 7. This will work for an arbitrary whole number k and we would have to take remainders after dividing by k instead of 7 giving rise to k different equivalence classes.

Evens and Odds

The example above shows what equivalence classes really are. Let’s consider remainders when we divide by the number 2.

There are only two possible remainders: 0 and 1.

If the remainder is 0, the number is even and if the remainder is 1, then the number is odd.

What are the equivalence classes with respect to this relation?

Well, it is simply the even and odd numbers!

So what is so special about even and odd numbers?

There is absolutely nothing special about even and odd numbers other than the fact that we divide the whole numbers up into exactly two non-intersecting subsets - but as you will soon see, equivalence classes are always disjoint and they always cover the entire set. It is what mathematicians call a partition.

Cosets

Having strolled around in set theory a bit we need to get back into group theory. However, our way back in will be through some special kinds of sets known as cosets.

Say we are given a group G and a subgroup H < G.

• Recall that a subgroup is a group whose underlying set is a subset of (the underlying set of) G. e.g. the even numbers 2ℤ is a subgroup of ℤ.
• Recall that the group operation is not necessarily commutative i.e. in general we have a ∗ b ≠ b ∗ a.

Let's now take an element g in G and form the set gH = {gh | h ∈ H}.

First of all, this is not necessarily a group.

Secondly, gH ≠ Hg. The set gH is called a left-coset of H in G. In this article, I will only work with left-cosets, but the results also hold for right-cosets.

The plan is to prove Lagrange’s theorem and get knowledge of cosets in the process but before proving anything let’s quickly brush up on some properties of functions.

Injectivity:

A function f is injective if and only if it “hits” elements in the codomain at most one time. i.e. if f(x) = f(y) then x = y.

Sometimes the contrapositive (and equivalent) statement is preferred: If x ≠ y, then f(x) ≠ f(y).

This property is sometimes called one-to-one.

• The function exp: ℝ → ℝ defined by exp(x) = e^x is injective.

Surjectivity:

A function is surjective if and only if every element of the codomain is “hit” by the function. i.e. let f: A → B, then for all y ∈ B there exists an x ∈ A such that y = f(x).

This property is sometimes called onto.

• The function sin: ℝ → [-1, 1] is surjective (but not injective).

Bijectivity:

A function that is both injective and surjective (one-to-one and onto) is called bijective.

Moreover, we say that there is a one-to-one correspondence between its domain and codomain.

The function f: ℝ → ℝ defined by f(x) = x³ is bijective.

The Theorem

We need some useful facts that we mathematicians sometimes call lemmas. Lemmas are propositions that are used to prove deeper results. The lemmas combined show something very interesting about cosets.

Recall that the notation H < G means: H is a subgroup of G.

Lemma 1: Let H < G. There is a one-to-one correspondence between H and any coset of H.

Proof.

Let C be a left coset of H in G. Then by definition there is a g ∈ G such that C = g ∗ H.

Define f : H → C by f(x) = g ∗ x. Then

f is injective because if x ≠ y, then since every element in G has an inverse (because it is a group), it follows that g ∗ x ≠ g ∗ y because if they were equal, then we could do a (left-) multiplication on both sides of the equation by the inverse of g contradicting the assumption. It follows that f(x) ≠ f(y).

f is surjective because if y ∈ C, then since C = g ∗ H, there is an h ∈ H such that y = g ∗ h. It follows that f(h) = y and since y was arbitrarily chosen, this holds for all elements c ∈ C.

This shows that f is a bijection and thus proves the proposition.

This lemma shows that all cosets have the same cardinality. In particular, if the group is finite, then all the cosets have the exact same number of elements.

Lemma 2: If H < G, and g, a ∈ G, then the left coset relation defined by g ~ a if and only if g∗ H = a∗ H is an equivalence relation.

Proof.

The fact that ∼ is an equivalence relation is trivial when you apply the definition because it is defined in terms of set equality and equality for sets is an equivalence relation. To be consistent, I state the following proof.

∼ is reflexive.

This is trivial. gH is a well-defined set and a set is equal to itself.

∼ is symmetric.

Let g, a ∈ G and g ∼ a. Again this is trivial. If gH = aH then aH = gH.

∼ is transitive. We use the definition again. Let a,b,c ∈ G. If aH = bH and bH = cH, then aH = cH.

This proves the proposition.

Amazingly, the cosets are actually equivalence classes with respect to the given relation.

Lemma 3: Let S be a set and ∼ be an equivalence relation on S. If A and B are two equivalence classes with A ∩ B ≠ ∅, then A = B.

Proof.

Let a ∈ A. Since A ∩ B ≠ ∅, there is a c ∈ A ∩ B. And since A is an equivalence class of ∼ and both a and c are in A, it follows that a ∼ c. But since a ∼ c, c ∈ B and B is an equivalence class of ∼, it follows that a ∈ B.

This shows that A ⊂ B. By symmetry we get B ⊂ A (mutatis mutandis). Having shown both inclusions, we conclude that A = B.

This shows that two different cosets cannot intersect. And since each element in G is in some coset of H, we can conclude that the cosets give a partition of the group. i.e. a set of non-intersecting subsets whose union is the group G. Furthermore, we have that they all have the same size.

Lagrange’s Theorem: If G is a finite group of order n and H is a subgroup of G of order k, then k|n and n /k is the number of distinct cosets of H in G.

Proof.

Let ∼ be the left coset equivalence relation defined in Lemma 2. It follows from Lemma 2 that ∼ is an equivalence relation and by Lemma 3 any two distinct cosets of ∼ are disjoint. Hence, we can write

G = (g1 ∗ H) ∪ (g2 ∗ H) ∪ · · · ∪ (gm ∗ H)

where the gi ∗ H, i = 1, 2, . . . , m are the disjoint left cosets of H guaranteed by Lemma 3. By Lemma 1, the cardinality of each of these cosets is the same as the order of H, and so

|G| = |g1 ∗ H| + |g2 ∗ H| + · · · + |gm ∗ H| = |H| + |H| + · · · + |H|

where there are m summands of |H|. Thus |G| = n = m ⋅ |H| = m ⋅ k.

This is what we needed to show.

Sometimes the number m in the proof is denoted [G : H] and is called the index of H in G. This is the number of left cosets of H in G.

Thus we can restate the theorem as |G| = [G : H] ⋅ |H|.

Lagrange’s theorem has many applications in number theory and group theory. Including Wilson’s theorem and Fermat’s little theorem. Note that the converse of the theorem does not hold in general.

See you next time.