View source for Lagrange's theorem (group theory)

{{short description|The order of a subgroup of a finite group G divides the order of G}}
{{Group theory sidebar |Finite}}
[[File:Left cosets of Z 2 in Z 8.svg|thumb|G is the group <math>\mathbb{Z}/8\mathbb{Z}</math>, the integers mod 8 under addition. The subgroup H contains only 0 and 4, and is isomorphic to <math>\mathbb{Z}/2\mathbb{Z}</math>. There are four left cosets of H: H itself, 1+H, 2+H, and 3+H (written using additive notation since this is an [[Abelian group|additive group]]). Together they partition the entire group G into equal-size, non-overlapping sets. Thus the [[Index of a subgroup|index]] [G : H] is 4.]]
In the [[Mathematics|mathematical]] field of [[Group theory|group theory]], '''Lagrange's theorem''' is a theorem that states that for any [[Finite group|finite group]] {{mvar|G}}, the order (number of elements) of every [[Subgroup|subgroup]] of {{mvar|G}} divides the order of {{mvar|G}}. The theorem is named after [[Biography:Joseph-Louis Lagrange|Joseph-Louis Lagrange]]. The following variant states that for a subgroup <math>H</math> of a finite group <math>G</math>, not only is <math>|G|/|H|</math> an integer, but its value is the [[Index of a subgroup|index]] <math>[G:H]</math>, defined as the number of left [[Coset|coset]]s of <math>H</math> in <math>G</math>.
{{math_theorem|Lagrange's theorem|If {{mvar|H}} is a subgroup of a group {{mvar|G}}, then <math>\left|G\right| = \left[G : H\right] \cdot \left|H\right|.</math>}}
This variant holds even if <math>G</math> is infinite, provided that <math>|G|</math>, <math>|H|</math>, and <math>[G:H]</math> are interpreted as [[Cardinal number|cardinal number]]s.

== Proof ==
The left [[Coset|coset]]s of {{mvar|H}} in {{mvar|G}} are the [[Equivalence class|equivalence class]]es of a certain [[Equivalence relation|equivalence relation]] on {{mvar|G}}: specifically, call {{mvar|x}} and {{mvar|y}} in {{mvar|G}} equivalent if there exists {{mvar|h}} in {{mvar|H}} such that {{math|''x'' {{=}} ''yh''}}. 
Therefore, the left cosets form a [[Partition of a set|partition]] of {{mvar|G}}.
Each left coset {{math|''aH''}} has the same cardinality as {{mvar|H}} because <math>x \mapsto ax</math> defines a bijection <math>H \to aH</math> (the inverse is <math>y \mapsto a^{-1}y</math>).
The number of left cosets is the [[Index of a subgroup|index]] {{math|[''G'' : ''H'']}}.
By the previous three sentences, 
:<math>\left|G\right| = \left[G : H\right] \cdot \left|H\right|.</math>

== Extension ==
Lagrange's theorem can be extended to the equation of indexes between three subgroups of {{mvar|G}}.<ref>{{mathworld |author=Bray, Nicolas |title=Lagrange's Group Theorem |id=LagrangesGroupTheorem|mode=cs2}}</ref>
{{math_theorem|Extension of Lagrange's theorem|If {{mvar|H}} is a subgroup of {{mvar|G}} and {{mvar|K}} is a subgroup of {{mvar|H}}, then
:<math>[G:K] = [G:H]\,[H:K].</math>}}
{{math_proof|Let {{mvar|S}} be a set of coset representatives for {{mvar|K}} in {{mvar|H}}, 
so <math>H = \coprod_{s \in S} sK</math> (disjoint union), and <math>|S|=[H:K]</math>.
For any <math>a \in G</math>, left-multiplication-by-{{mvar|a}} is a bijection <math>G \to G</math>, 
so <math>aH = \coprod_{s \in S} asK</math>.  
Thus each left coset of {{mvar|H}} decomposes into <math>[H:K]</math> left cosets of {{mvar|K}}.
Since {{mvar|G}} decomposes into <math>[G:H]</math> left cosets of {{mvar|H}},
each of which decomposes into <math>[H:K]</math> left cosets of {{mvar|K}},
the total number <math>[G:K]</math> of left cosets of {{mvar|K}} in {{mvar|G}} is <math>[G:H][H:K]</math>.
}}
If we take {{math|''K'' {{=}} {{mset|''e''}}}} ({{mvar|e}} is the identity element of {{mvar|G}}), then {{math|[''G'' : {{mset|''e''}}] {{=}} {{!}}''G''{{!}}}} and {{math|[''H'' : {{mset|''e''}}] {{=}} {{!}}''H''{{!}}}}.  Therefore, we can recover the original equation {{math|{{!}}''G''{{!}} {{=}} [''G'' : ''H''] {{!}}''H''{{!}}}}.

== Applications ==
A consequence of the theorem is that the [[Order (group theory)|order of any element]] {{mvar|a}} of a finite group (i.e. the smallest positive integer number {{mvar|k}} with {{math|{{mvar|a}}<sup>{{mvar|k}}</sup> {{=}} {{mvar|e}}}}, where {{mvar|e}} is the identity element of the group) divides the order of that group, since the order of {{mvar|a}} is equal to the order of the [[Cyclic group|cyclic]] subgroup [[Generating set of a group|generated]] by {{mvar|a}}. If the group has {{mvar|n}} elements, it follows

:<math>\displaystyle a^n = e\mbox{.}</math>

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 group|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 <math>p</math>. Any prime divisor <math>q</math> of the [[Mersenne number]] <math>2^p -1</math> satisfies <math>2^p \equiv 1 \pmod {q}</math> (see [[Modular arithmetic|modular arithmetic]]), meaning that the order of <math>2</math> in the [[Multiplicative group|multiplicative group]] <math>(\mathbb Z/q\mathbb Z)^*</math> is <math>p</math>. By Lagrange's theorem, the order of <math>2</math> must divide the order of <math>(\mathbb Z/q\mathbb Z)^*</math>, which is <math>q-1</math>. So <math>p</math> divides <math>q-1</math>, giving <math> p < q </math>, contradicting the assumption that <math>p</math> is the largest prime.<ref>{{Citation|last1=Aigner|first1=Martin|last2=Ziegler|first2=Günter M.|year=2018|title=[[Proofs from THE BOOK]]|chapter=Chapter 1|pages=3–8|publisher=Springer|location=Berlin|edition=Revised and enlarged sixth|isbn=978-3-662-57264-1}}</ref>

== 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 ''A''<sub>4</sub> (the [[Alternating group|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 group|solvable]] and that every [[Supersolvable group|supersolvable group]] is a CLT group. However, there exist solvable groups that are not CLT (for example, ''A''<sub>4</sub>) and CLT groups that are not supersolvable (for example, ''S''<sub>4</sub>, the symmetric group of degree 4).

There are partial converses to Lagrange's theorem.  For general groups, [[Cauchy's theorem (group theory)|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 subgroup#Hall's theorem|Hall's theorems]] assert the existence of a subgroup of order equal to any [[Unitary divisor|unitary divisor]] of the group order (that is, a divisor coprime to its cofactor).

=== Counterexample of the converse of Lagrange's theorem ===
The converse of Lagrange's theorem states that if {{mvar|d}} is a [[Divisor|divisor]] of the order of a group {{mvar|G}}, then there exists a subgroup {{mvar|H}} where {{math|1={{!}}''H''{{!}} = ''d''}}.

We will examine the [[Alternating group|alternating group]] {{math|''A''<sub>4</sub>}}, the set of even [[Permutation group|permutations]] as the subgroup of the [[Symmetric group]] {{math|''S''<sub>4</sub>}}.

:{{nowrap|{{math|1=''A''<sub>4</sub> = {{mset|''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)}}}}.}}

{{math|1={{!}}''A''<sub>4</sub>{{!}} = 12}} so the divisors are {{math|1, 2, 3, 4, 6, 12}}. Assume to the contrary that there exists a subgroup {{mvar|H}} in {{math|''A''<sub>4</sub>}} with {{math|1={{!}}''H''{{!}} = 6}}.

Let {{mvar|V}} be the [[Cyclic group|non-cyclic]] subgroup of {{math|''A''<sub>4</sub>}} called the [[Klein four-group]].

:{{math|1=''V'' = {{mset|''e'', (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)}}}}.

Let {{math|1=''K'' = ''H'' ⋂ ''V''}}. Since both {{mvar|H}} and {{mvar|V}} are subgroups of {{math|''A''<sub>4</sub>}}, {{mvar|K}} is also a subgroup of {{math|''A''<sub>4</sub>}}.

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

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

Since any element of the form {{math|(''a b c'')}} squared is {{math|(''a c b'')}}, and {{math|1=(''a b c'')(''a c b'') = ''e''}}, any element of {{mvar|H}} in the form {{math|(''a b c'')}} must be paired with its inverse. Specifically, the remaining 5 elements of {{mvar|H}} must come from distinct pairs of elements in {{math|''A''<sub>4</sub>}} that are not in {{mvar|V}}. This is impossible since pairs of elements must be even and cannot total up to 5 elements. Thus, the assumptions that {{math|1={{!}}''K''{{!}} = 1}} is wrong, so {{math|1={{!}}''K''{{!}} = 2}}.

Then, {{math|1=''K'' = {{mset|''e'', ''v''}}}} where {{math|''v'' ∈ ''V''}}, {{mvar|v}} must be in the form {{math|(''a b'')(''c d'')}} where {{mvar|a, b, c, d}} are distinct elements of {{math|{{mset|1, 2, 3, 4}}}}. The other four elements in {{mvar|H}} are cycles of length 3.

Note that the cosets [[Generating set of a group|generated]] by a subgroup of a group form a partition of the group. The cosets generated by a specific subgroup are either identical to each other or [[Disjoint sets|disjoint]]. The index of a subgroup in a group {{math|1=[''A''<sub>4</sub> : ''H''] = {{!}}''A''<sub>4</sub>{{!}}/{{!}}''H''{{!}}}} is the number of cosets generated by that subgroup. Since {{math|1={{!}}''A''<sub>4</sub>{{!}} = 12}} and {{math|1={{!}}''H''{{!}} = 6}}, {{mvar|H}} will generate two left cosets, one that is equal to {{mvar|H}} and another, {{mvar|gH}}, that is of length 6 and includes all the elements in {{math|''A''<sub>4</sub>}} not in {{mvar|H}}.

Since there are only 2 distinct cosets generated by {{mvar|H}}, then {{mvar|H}} must be normal. Because of that, {{math|1=''H'' = ''gHg''<sup>−1</sup> (∀''g'' ∈ ''A''<sub>4</sub>)}}. In particular, this is true for {{math|1=''g'' = (''a b c'') ∈ ''A''<sub>4</sub>}}. Since {{math|1=''H'' = ''gHg''<sup>−1</sup>, ''gvg''<sup>−1</sup> ∈ ''H''}}.

Without loss of generality, assume that {{math|1=''a'' = 1}}, {{math|1=''b'' = 2}}, {{math|1=''c'' = 3}}, {{math|1=''d'' = 4}}. Then {{math|1=''g'' = (1 2 3)}}, {{math|1=''v'' = (1 2)(3 4)}}, {{math|1=''g''<sup>−1</sup> = (1 3 2)}}, {{math|1=''gv'' = (1 3 4)}}, {{math|1=''gvg''<sup>−1</sup> = (1 4)(2 3)}}. Transforming back, we get {{math|1=''gvg''<sup>−1</sup> = (''a'' ''d'')(''b'' ''c'')}}. Because {{mvar|V}} contains all disjoint transpositions in {{math|''A''<sub>4</sub>}}, {{math|''gvg''<sup>−1</sup> ∈ ''V''}}. Hence, {{math|1=''gvg''<sup>−1</sup> ∈ ''H'' ⋂ ''V'' = ''K''}}.

Since {{math|''gvg''<sup>−1</sup> ≠ ''v''}}, we have demonstrated that there is a third element in {{mvar|K}}. But earlier we assumed that {{math|1={{!}}''K''{{!}} = 2}}, so we have a contradiction.

Therefore, our original assumption that there is a subgroup of order 6 is not true and consequently there is no subgroup of order 6 in {{math|''A''<sub>4</sub>}} and the converse of Lagrange's theorem is not necessarily true.
[[Q.E.D.]]

== History ==
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'',<ref>{{citation | last = Lagrange|first= Joseph-Louis |  year = 1771 | title = 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. |trans-title=Series of reflections on the algebraic solution of equations. Third section. On the solution of equations of the fifth degree & higher degrees | journal = Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin | pages = 138–254 | url = https://books.google.com/books?id=_-U_AAAAYAAJ&pg=PA138}} ; see especially [https://books.google.com/books?id=_-U_AAAAYAAJ&pg=PA202 pages 202-203.]</ref> that if a polynomial in {{mvar|n}} variables has its variables permuted in all {{math|''n''!}} ways, the number of different polynomials that are obtained is always a factor of {{math|''n''!}}.  (For example, if the variables {{mvar|x}}, {{mvar|y}}, and {{mvar|z}} are permuted in all 6 possible ways in the polynomial {{math|''x'' + ''y'' − ''z''}} then we get a total of 3 different polynomials: {{math|''x'' + ''y'' − ''z''}}, {{math|''x'' + ''z'' − ''y''}}, and {{math|''y'' + ''z'' − ''x''}}.  Note that 3 is a factor of 6.) The number of such polynomials is the index in the [[Symmetric group|symmetric group]] {{math|''S''<sub>n</sub>}} of the subgroup {{mvar|''H''}} of permutations that preserve the polynomial.  (For the example of {{math|''x'' + ''y'' − ''z''}}, the subgroup {{mvar|''H''}} in {{math|''S''<sub>3</sub>}} contains the identity and the transposition {{math|(''x y'')}}.) So the size of {{mvar|''H''}} divides {{math|''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, [[Biography:Carl Friedrich Gauss|Carl Friedrich Gauss]] proved Lagrange's theorem for the special case of <math>(\mathbb Z/p \mathbb Z)^*</math>, the multiplicative group of nonzero integers [[Modular arithmetic|modulo]] {{mvar|p}}, where {{mvar|p}} is a prime.<ref>{{Citation|last=Gauss|first=Carl Friedrich|title=Disquisitiones Arithmeticae|location=Leipzig (Lipsia)|language=la|publisher=G. Fleischer|year=1801}}, [http://babel.hathitrust.org/cgi/pt?id=nyp.33433070725894;view=1up;seq=63 pp. 41-45, Art. 45-49.]</ref>  In 1844, [[Biography:Augustin-Louis Cauchy|Augustin-Louis Cauchy]] proved Lagrange's theorem for the symmetric group {{math|''S''<sub>n</sub>}}.<ref>[[Biography:Augustin-Louis Cauchy|Augustin-Louis 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), [https://books.google.com/books?id=-c3fxufDQVEC&pg=PA183 pp. 183-185.]</ref>

[[Biography:Camille Jordan|Camille Jordan]] finally proved Lagrange's theorem for the case of any [[Permutation group|permutation group]] in 1861.<ref>{{citation | first=Camille| last=Jordan| year = 1861 | title = Mémoire sur le numbre des valeurs des fonctions |trans-title=Memoir on the number of values of functions |journal = Journal de l'École Polytechnique | volume = 22 | pages = 113–194 | url = http://gallica.bnf.fr/ark:/12148/bpt6k433691p/f118.image.langEN}}  Jordan's generalization of Lagrange's theorem appears on [http://gallica.bnf.fr/ark:/12148/bpt6k433691p/f171.image.r=Lagrange.langEN page 166.]</ref>

== Notes ==
{{reflist}}

== References ==
* {{Citation | last=Bray | first=Henry G. | title=A note on CLT groups | journal=Pacific J. Math. | volume=27 | year=1968 | pages=229–231 | issue=2 | doi=10.2140/pjm.1968.27.229| doi-access=free }}
* {{Citation | last=Gallian | first=Joseph | title=Contemporary Abstract Algebra | publisher=Houghton Mifflin | location=Boston  | edition=6th | isbn=978-0-618-51471-7 | year=2006}}
* {{Citation | last1=Dummit | first1=David S. | last2=Foote | first2=Richard M. | title=Abstract algebra | publisher={{wipe|John Wiley & Sons}} | location=New York | edition=3rd | isbn=978-0-471-43334-7 | mr=2286236  | year=2004}}
* {{Citation | last=Roth | first=Richard R. | title=A History of Lagrange's Theorem on Groups | journal=Mathematics Magazine | volume=74 | issue=2 | pages=99–108 | year=2001 | jstor=2690624 | doi=10.2307/2690624}}


[[Category:Articles containing proofs]]

{{Sourceattribution|Lagrange's theorem (group theory)}}