Lagrange's theorem (group theory)

In the mathematical field of group theory, Lagrange's theorem states that if H is a subgroup of any finite group G, then \(|H|\) is a divisor of \(|G|\). That is, the order (number of elements) of every subgroup divides the order of the whole group.

The theorem is named after Joseph-Louis Lagrange. The following variant states that for a subgroup \(H\) of a finite group \(G\), not only is \(|G|/|H|\) an integer, but its value is the index \([G:H]\), defined as the number of left cosets of \(H\) in \(G\).

Lagrange's theorem, If H is a subgroup of a group G, then \(\left|G\right| = \left[G : H\right] \cdot \left|H\right|.\)

This variant holds even if \(G\) is infinite, provided that \(|G|\), \(|H|\), and \([G:H]\) are interpreted as cardinal numbers.

The left cosets of H in G are the equivalence classes of a certain equivalence relation on G: specifically, call x and y in G equivalent if there exists h in H such that x = yh. Therefore, the set of left cosets forms a partition of G. Each left coset aH has the same cardinality as H because \(x \mapsto ax\) defines a bijection \(H \to aH\) (the inverse is \(y \mapsto a^{-1}y\)). The number of left cosets is the index [G : H]. By the previous three sentences,

\(\left|G\right| = \left[G : H\right] \cdot \left|H\right|.\)

Lagrange's theorem can be extended to the equation of indices between three subgroups of G.

Extension of Lagrange's theorem, If H is a subgroup of G and K is a subgroup of H, then

\([G:K] = [G:H]\,[H:K].\)

Let S be a set of coset representatives for K in H, so \(H = \bigsqcup_{s \in S} sK\) (disjoint union), and \(|S|=[H:K]\). For any \(a \in G\), left-multiplication-by-a is a bijection \(G \to G\), so \(aH = \bigsqcup_{s \in S} asK\). Thus each left coset of H decomposes into \([H:K]\) left cosets of K. Since G decomposes into \([G:H]\) left cosets of H, each of which decomposes into \([H:K]\) left cosets of K, the total number \([G:K]\) of left cosets of K in G is \([G:H][H:K]\).

If we take K = {e} (e is the identity element of G), then [G : {e}] = |G| and [H : {e}] = |H|. Therefore, we can recover the original equation |G| = [G : H] |H|.

A consequence of the theorem is that the order of any element a of a finite group (i.e. the smallest positive integer number k with a = e, where e is the identity element of the group) divides the order of that group, since the order of a is equal to the order of the cyclic subgroup generated by a. If the group has n elements, it follows

\(\displaystyle a^n = e\mbox{.}\)

This can be used to prove Fermat's little theorem and its generalization, Euler's theorem. These special cases were known long before the general theorem was proved.

The theorem also shows that any group of prime order is cyclic and simple, since the subgroup generated by any non-identity element must be the whole group itself.

Lagrange's theorem can also be used to show that there are infinitely many primes: suppose there were a largest prime \(p\). Any prime divisor \(q\) of the Mersenne number \(2^p -1\) satisfies \(2^p \equiv 1 \pmod {q}\) (see modular arithmetic), meaning that the order of \(2\) in the multiplicative group \((\mathbb Z/q\mathbb Z)^*\) is \(p\). By Lagrange's theorem, the order of \(2\) must divide the order of \((\mathbb Z/q\mathbb Z)^*\), which is \(q-1\). So \(p\) divides \(q-1\), giving p < q\), contradicting the assumption that \(p\) is the largest prime.

Lagrange's theorem raises the converse question as to whether every divisor of the order of a group is the order of some subgroup. This does not hold in general: given a finite group G and a divisor d of |G|, there does not necessarily exist a subgroup of G with order d. The smallest example is A₄ (the alternating group of degree 4), which has 12 elements but no subgroup of order 6.

A "Converse of Lagrange's Theorem" (CLT) group is a finite group with the property that for every divisor of the order of the group, there is a subgroup of that order. It is known that a CLT group must be solvable and that every supersolvable group is a CLT group. However, there exist solvable groups that are not CLT (for example, A₄) and CLT groups that are not supersolvable (for example, S₄, the symmetric group of degree 4).

There are partial converses to Lagrange's theorem. For general groups, Cauchy's theorem guarantees the existence of an element, and hence of a cyclic subgroup, of order any prime dividing the group order. Sylow's theorem extends this to the existence of a subgroup of order equal to the maximal power of any prime dividing the group order. For solvable groups, Hall's theorems assert the existence of a subgroup of order equal to any unitary divisor of the group order (that is, a divisor coprime to its cofactor).

The converse of Lagrange's theorem states that if d is a divisor of the order of a group G, then there exists a subgroup H where |H| = d.

We will examine the alternating group A₄, the set of even permutations as the subgroup of the Symmetric group S₄.

A₄ = {e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3), (1 2 3), (1 3 2), (1 2 4), (1 4 2), (1 3 4), (1 4 3), (2 3 4), (2 4 3)}.

|A₄| = 12 so the divisors are 1, 2, 3, 4, 6, 12. Assume to the contrary that there exists a subgroup H in A₄ with |H| = 6.

Let V be the non-cyclic subgroup of A₄ called the Klein four-group.

V = {e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)}.

Let K = H ⋂ V. Since both H and V are subgroups of A₄, K is also a subgroup of A₄.

From Lagrange's theorem, the order of K must divide both 6 and 4, the orders of H and V respectively. The only two positive integers that divide both 6 and 4 are 1 and 2. So |K| = 1 or 2.

Assume |K| = 1, then K = {e}. If H does not share any elements with V, then the 5 elements in H besides the Identity element e must be of the form (a b c) where a, b, c are distinct elements in {1, 2, 3, 4}.

Condensed: the full section is in Wikipedia.

Lagrange himself did not prove the theorem in its general form. He stated, in his article Réflexions sur la résolution algébrique des équations, that if a polynomial in n variables has its variables permuted in all n! ways, the number of different polynomials that are obtained is always a factor of n!. (For example, if the variables x, y, and z are permuted in all 6 possible ways in the polynomial x + y − z then we get a total of 3 different polynomials: x + y − z, x + z − y, and y + z − x. Note that 3 is a factor of 6.) The number of such polynomials is the index in the symmetric group S_n of the subgroup H of permutations that preserve the polynomial. (For the example of x + y − z, the subgroup H in S₃ contains the identity and the transposition (x y).) So the size of H divides n!. With the later development of abstract groups, this result of Lagrange on polynomials was recognized to extend to the general theorem about finite groups which now bears his name.

In his Disquisitiones Arithmeticae in 1801, Carl Friedrich Gauss proved Lagrange's theorem for the special case of \((\mathbb Z/p \mathbb Z)^*\), the multiplicative group of nonzero integers modulo p, where p is a prime. In 1844, Augustin-Louis Cauchy proved Lagrange's theorem for the symmetric group S_n.

Camille Jordan finally proved Lagrange's theorem for the case of any permutation group in 1861.