Cosets and Lagrange's Theorem

Lagrange’s Theorem

Introduction

Lagrange’s theorem is about finite groups. A finite group G is a special kind of a set with a natural number n of elements, n > 0.

In general, a group G is a set in which there is defined an operation like addition, multiplication or any other. Let´s call * a generic operation. The following conditions define a group G, with respect to the operation *: (G, *).

1.       If a, b are elements of G, then a*b is an element of G

2.       (a * b) * c = a * (b * c), for all a, b, c elements of G

3.       There is a unique element e in G such that x * e = x = x * e, for all x in G

4.       For each x in G there is exactly one x’ in G such that x *x’ = e = x´ *x

If a * b = b * a for all a, b in G then the group is commutative (or abelian)

The element e is called neutral or identical. For each element a in G; a’ is called the inverse of a with respect to the operation *.

One of the more known groups is Z, the set of integers, an infinite group. For this group, the operation is addition (* is +), the identical element is 0 (e is 0) and a’, the inverse of integer a with respect to addition, is -a (a’ is -a).

The set {[0], [1], [2], [3], [4]} of integers, mod 5 is a finite group with respect to addition mod 5. In this case, [0] is the identical, [3]’ = [2], [4]’ = [1].

Subgroups of a group

If H is a subset of a group G and H itself is a group, with respect to the operation defined in G, then H is a subgroup of G. For each group G there are two trivial subgroups: G and {e}. Any other subgroups of a group are called proper subgroups of it.

Example: the set of even integers is a proper subgroup of the group (Z, +).

Cosets

The concept of coset for a given subgroup will be useful in the development of Lagrange’s  Theorem.

Let H be a subgroup of the group (G, *). If g is an element of G, then the set

g*H = {g*x| x is an element of H}

Is called a left coset for H.

Analogously, H*g is defined as a right coset for H. If G is an abelian group, there is no difference between right and left cosets.

Example. Let G = {[1], [2], [3], [4], [5], [6]}. This is the set of integers mod 7, without [0]. It may be verified that G is a group under multiplication. Also, it may be seen that H = {[1], [2], [4]} is a subgroup of G. The following are the left cosets for H:

[1].H = {[1], [2], [4]}

[2].H = {[2], [4], [1]}

[3].H = {[3], [6], [5]}

[4].H = {[4], [1], [2]}

[5].H = {[5], [3], [6]}

[6].H = {[6], [5], [3]}

It can be seen that [1].H = [2].H = [4].H; also [3].H = [5].H = [6].H; but [2].H and [3].H are disjoint sets.

From above description it can be obtained a partition of G:

{{[1], [2], [4]}, {[3], [6], [5]}}

It can be verified also that the set J = {[1], [6]} is another subgroup of G. The following are the left cosets for J:

[1].J = {[1], [6]}

[2].J = {[2], [5]}

[3].J = {[3], [4]}

[4].J = {[4], [3]}

[5].J = {[5], [2]}

[6].J = {[6], [1]}

In this case, [1].J = [6]. J, [2].J = [5].J, [3].J = [4].J; but the cosets  [6].J ,  [5].J and [3].J have not elements in common. It can be obtained the following partition of G: {{[1], [6]}, {[2], [5]}, {[3], [4]}}.

The described partitions can be obtained in a different way: starting with the subgroup H = {[1], [2], [4]}, take an element of G, not in H. If [3] is chosen, construct the left coset [3].H = {[3], [6], [5]}. There are not any elements of G that are not included in H or [3].H. So, the process has ended and a partition of G has been obtained: {{[1], [2], [4]}, {[3], [6], [5]}}.

Similarly, for the subgroup J = {[1], [6]}, an element of G not in J is [2]; the corresponding left coset is [2]. J = {[2], [5]}. Now, take another element of G, not in J or [2]. J; if [4] is chosen, [4]. J = {[4], [3]}. There are not any elements of G that are not included in J or [2]. J or [4]. J. So, the process has ended and a partition of G has been obtained: {{[1], [6]}, {[2], [5]}, {[3], [4]}}.

The last process described for above example can be generalized to obtain directly a partition of a given group G. If G is a group and H is a subgroup of it, take an element g1 of G, not in H and construct the left coset g1*H. Claim: H and g1*H are disjoint sets. To prove this (by contradiction), suppose that a belongs to H and g1*H. Then a = g1*h, for some h in H. As H is a group, h’, the inverse of h, is in H. Then a*h´ is in H. That is, g1 is in H. But this contradicts that the element g1 has been chosen out of H. The following note shows details.

Note: As a = g1*h, then a*h’ = (g1*h)*h’ = g1*(h*h’) = g1*e = g1. That is, a*h’ = g1.

Take an element g2 in G which is not in H or g1*H, and construct g2*H. It can be shown, as before, that H and g2*H are disjoint sets. Claim: g1*H an g2*H are disjoint sets too. This will be shown by contradiction.

Suppose that b is an element of G which belongs to g1*H and g2*h. Then b = g1*h1, for some h1 in H, and b = g2*h2, for some h2 in H.

From g1*h1 = g2*h2 it follows that (g1*h1)*h2’ = g2 and g1*(h1*h2’) = g2. As h1 and h2 are elements of subgroup H, h2’ is in H and h1*h2’ = h3, for some h3 in H.

It follows that g*h3 = g2 is in H. But this contradicts what has been supposed before: g2 is not in H.

With the same restrictions for g1, g2 there can be constructed the left cosets g3*H, …, gk*H, where g1, g2, … gk are elements of G and k is not greater than n.

In this process all the elements of G are used in the list of cosets without repetition as it occurred in the first construction of left cosets in above example.

If gr*H = gs*H for gr, gs in G, but not in H, or gr*H, or gs*H then gr*h1 = gs*h2 for some h1 and h2 in H. In this case, (gr*h1)*h2’ = gs, that is gr*(h1*h2’) = gs that is gr*ht = gs, for some ht in H. But then, gs is in gr*H, a contradiction with previous statement.

 As g1, g2, …, gk are chosen with the conditions above described, any two of the left cosets g1*H, g2*H, …, gk*H are disjoint sets.

The union of all the left cosets of H, is G, since each element of G have been used. In this process it has been obtained a partition of G.

If H has m elements, the left coset g*H has m elements too. This means that all the left cosets of H have the same number m of elements. The total number of left cosets (without repetitions) is k.

As G has n elements, and all of them have been used in the construction of the left cosets of H, it follows that m.k = n.

This result is known as Lagrange’s Theorem: If a finite group G has n elements, and H is a subgroup of it with m elements, then m is a factor of n.

In above discussion the concept of left coset of a subgroup has been used. It can be repeated using the concept of right coset. This is necessary, from a strict point of view, since this theorem is valid for a finite group G, abelian or not.