Lagrange's theorem (group theory)

G is the group $\mathbb{Z}/8\mathbb{Z}$, the integers mod 8 under addition. The subgroup H contains only 0 and 4, and is isomorphic to $\mathbb{Z}/2\mathbb{Z}$. There are four left cosets of H: H itself, 1+H, 2+H, and 3+H (written using additive notation since this is an additive group). Together they partition the entire group G into equal-size, non-overlapping sets. Thus the index [G : H] is 4.

Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order (number of elements) of every subgroup H of G divides the order of G. The theorem is named after Joseph-Louis Lagrange.

Proof of Lagrange's Theorem

This can be shown using the concept of left cosets of H in G. The left cosets are the equivalence classes of a certain equivalence relation on G and therefore form a partition of G. Specifically, x and y in G are related if and only if there exists h in H such that x = yh. If we can show that all cosets of H have the same number of elements, then each coset of H has precisely |H| elements. We are then done since the order of H times the number of cosets is equal to the number of elements in G, thereby proving that the order of H divides the order of G. Now, if aH and bH are two left cosets of H, we can define a map f : aH → bH by setting f(x) = ba⁻¹x. This map is bijective because its inverse is given by $f^{-1}(y) = ab^{-1}y\mbox{.}$

This proof also shows that the quotient of the orders |G| / |H| is equal to the index [G : H] (the number of left cosets of H in G). If we allow G and H to be infinite, and write this statement as

$\left|G\right| = \left[G : H\right] \cdot \left|H\right|\mbox{,}$

then, seen as a statement about cardinal numbers, it is equivalent to the Axiom of choice.

Applications

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^k = 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. This in turn can be used to prove Wilson's theorem, that if p is prime then p is a factor of $(p-1)!+1$.

Lagrange's theorem can also be used to show that there are infinitely many primes: if there was a largest prime p, then a prime divisor q of the Mersenne number $2^p -1$ would be such that the order of 2 in the multiplicative group $((\mathbb Z / q) \backslash 0, \cdot)$ (see modular arithmetic) would divide the order of this group which is $q-1$. Hence $p<q$, contradicting the assumption that p is the largest prime.^[1]

Existence of subgroups of given order

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 the alternating group G = A₄, which has 12 elements but no subgroup of order 6. A 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₄, the alternating group of degree 4) 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).

History

Lagrange did not prove Lagrange's theorem in its general form. He stated, in his article Réflexions sur la résolution algébrique des équations,^[2] 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 (xy).) 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 Z(p)*, the multiplicative group of nonzero integers modulo p, where p is a prime.^[3] In 1844, Augustin-Louis Cauchy proved Lagrange's theorem for the symmetric group S_n.^[4]

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

Notes

1. Aigner, Ziegler: Proofs from the book, Springer, Chapter 1
2. Lagrange, J. L. (1771). "Suite des réflexions sur la résolution algébrique des équations. Section troisieme. De la résolution des équations du cinquieme degré & des degrés ultérieurs." [Series of reflections on the algebraic solution of equations. Third section. On the solution of equations of the fifth degree & higher degrees]. Nouveaux Mémoires de l’Académie Royale des Sciences et Belles-Lettres de Berlin: 138–254. ; see especially pages 202-203.
3. Gauss, Carl Friedrich, Disquisitiones Arithmeticae (Leipzig (Lipsia), (Germany): G. Fleischer, 1801), pp. 41-50.
4. A.-L. Cauchy, §VI. — Sur les dérivées d'une ou de plusieurs substitutions, et sur les systèmes de substitutions conjuguées [On the products of one or several permutations, and on systems of conjugate permutations] of: "Mémoire sur les arrangements que l'on peut former avec des lettres données, et sur les permutations ou substitutions à l'aide desquelles on passe d'un arrangement à un autre" [Memoir on the arrangements that one can form with given letters, and on the permutations or substitutions by means of which one passes from one arrangement to another] in: Exercises d'analyse et de physique mathématique [Exercises in analysis and mathematical physics], vol. 3 (Paris, France: Bachelier, 1844), pp. 183-185.
5. Camille Jordan (1861). "Mémoire sur le numbre des valeurs des fonctions" [Memoir on the number of values of functions]. Journal de l'École Polytechnique 22: 113–194. Jordan's generalization of Lagrange's theorem appears on page 166.

References

• Bray, Henry G. (1968), "A note on CLT groups", Pacific J. Math. 27 (2): 229–231, doi:10.2140/pjm.1968.27.229
• Gallian, Joseph (2006), Contemporary Abstract Algebra (6th ed.), Boston: Houghton Mifflin, ISBN 978-0-618-51471-7
• Dummit, David S.; Foote, Richard M. (2004), Abstract algebra (3rd ed.), New York: John Wiley & Sons, ISBN 978-0-471-43334-7, MR 2286236
• Roth, Richard R. (2001), "A History of Lagrange's Theorem on Groups", Mathematics Magazine 74 (2): 99–108, doi:10.2307/2690624, JSTOR 2690624

External links

• Bray, Nicolas, "Lagrange's Group Theorem", MathWorld.