Algebraic structure → Group theory 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 is a divisor of , i.e. the order (number of elements) of every subgroup H divides the order of group G.
The theorem is named after Joseph-Louis Lagrange. The following variant states that for a subgroup of a finite group , not only is an integer, but its value is the index , defined as the number of left cosets of in .
Lagrange's theorem — If H is a subgroup of a group G, then
This variant holds even if is infinite, provided that , , and 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 defines a bijection (the inverse is ). The number of left cosets is the index [G : H]. By the previous three sentences,
Lagrange's theorem can be extended to the equation of indexes between three subgroups of G. [1]
Extension of Lagrange's theorem — If H is a subgroup of G and K is a subgroup of H, then
Let S be a set of coset representatives for K in H, so (disjoint union), and . For any , left-multiplication-by-a is a bijection , so . Thus each left coset of H decomposes into left cosets of K. Since G decomposes into left cosets of H, each of which decomposes into left cosets of K, the total number of left cosets of K in G is .
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 ak = 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
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 . Any prime divisor of the Mersenne number satisfies (see modular arithmetic), meaning that the order of in the multiplicative group is . By Lagrange's theorem, the order of must divide the order of , which is . So divides , giving , contradicting the assumption that is the largest prime. [2]
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 A4 (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, A4) and CLT groups that are not supersolvable (for example, S4, 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 A4, the set of even permutations as the subgroup of the Symmetric group S4.
|A4| = 12 so the divisors are 1, 2, 3, 4, 6, 12. Assume to the contrary that there exists a subgroup H in A4 with |H| = 6.
Let V be the non-cyclic subgroup of A4 called the Klein four-group.
Let K = H ⋂ V. Since both H and V are subgroups of A4, K is also a subgroup of A4.
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}.
Since any element of the form (a b c) squared is (a c b), and (a b c)(a c b) = e, any element of H in the form (a b c) must be paired with its inverse. Specifically, the remaining 5 elements of H must come from distinct pairs of elements in A4 that are not in V. This is impossible since pairs of elements must be even and cannot total up to 5 elements. Thus, the assumptions that |K| = 1 is wrong, so |K| = 2.
Then, K = {e, v} where v ∈ V, v must be in the form (a b)(c d) where a, b, c, d are distinct elements of {1, 2, 3, 4}. The other four elements in H are cycles of length 3.
Note that the cosets 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. The index of a subgroup in a group [A4 : H] = |A4|/|H| is the number of cosets generated by that subgroup. Since |A4| = 12 and |H| = 6, H will generate two left cosets, one that is equal to H and another, gH, that is of length 6 and includes all the elements in A4 not in H.
Since there are only 2 distinct cosets generated by H, then H must be normal. Because of that, H = gHg−1 (∀g ∈ A4). In particular, this is true for g = (a b c) ∈ A4. Since H = gHg−1, gvg−1 ∈ H.
Without loss of generality, assume that a = 1, b = 2, c = 3, d = 4. Then g = (1 2 3), v = (1 2)(3 4), g−1 = (1 3 2), gv = (1 3 4), gvg−1 = (1 4)(2 3). Transforming back, we get gvg−1 = (ad)(bc). Because V contains all disjoint transpositions in A4, gvg−1 ∈ V. Hence, gvg−1 ∈ H ⋂ V = K.
Since gvg−1 ≠ v, we have demonstrated that there is a third element in K. But earlier we assumed that |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 A4 and the converse of Lagrange's theorem is not necessarily true. Q.E.D.
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, [3] 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 Sn of the subgroup H of permutations that preserve the polynomial. (For the example of x + y − z, the subgroup H in S3 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 , the multiplicative group of nonzero integers modulo p, where p is a prime. [4] In 1844, Augustin-Louis Cauchy proved Lagrange's theorem for the symmetric group Sn. [5]
Camille Jordan finally proved Lagrange's theorem for the case of any permutation group in 1861. [6]
A quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure. For example, the cyclic group of addition modulo n can be obtained from the group of integers under addition by identifying elements that differ by a multiple of and defining a group structure that operates on each such class as a single entity. It is part of the mathematical field known as group theory.
In mathematics, a finite field or Galois field is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are the integers mod p when p is a prime number.
In mathematics, a group action of a group G on a set S is a group homomorphism from G to some group of functions from S to itself. It is said that Gacts on S.
In mathematics, a group is a set with an operation that associates an element of the set to every pair of elements of the set and satisfies the following constraints: the operation is associative, it has an identity element, and every element of the set has an inverse element.
In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G.
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group defined over a finite set of symbols consists of the permutations that can be performed on the symbols. Since there are such permutation operations, the order of the symmetric group is .
In mathematics, especially group theory, two elements and of a group are conjugate if there is an element in the group such that This is an equivalence relation whose equivalence classes are called conjugacy classes. In other words, each conjugacy class is closed under for all elements in the group.
In mathematics, an alternating group is the group of even permutations of a finite set. The alternating group on a set of n elements is called the alternating group of degree n, or the alternating group on n letters and denoted by An or Alt(n).
In mathematics, specifically in the field of finite group theory, the Sylow theorems are a collection of theorems named after the Norwegian mathematician Peter Ludwig Sylow that give detailed information about the number of subgroups of fixed order that a given finite group contains. The Sylow theorems form a fundamental part of finite group theory and have very important applications in the classification of finite simple groups.
In mathematics, a unique factorization domain (UFD) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is an integral domain in which every non-zero non-unit element can be written as a product of irreducible elements, uniquely up to order and units.
In mathematics, specifically group theory, a subgroup H of a group G may be used to decompose the underlying set of G into disjoint, equal-size subsets called cosets. There are left cosets and right cosets. Cosets have the same number of elements (cardinality) as does H. Furthermore, H itself is both a left coset and a right coset. The number of left cosets of H in G is equal to the number of right cosets of H in G. This common value is called the index of H in G and is usually denoted by [G : H].
In mathematics, more specifically in the field of group theory, a solvable group or soluble group is a group that can be constructed from abelian groups using extensions. Equivalently, a solvable group is a group whose derived series terminates in the trivial subgroup.
In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group G is isomorphic to a subgroup of a symmetric group. More specifically, G is isomorphic to a subgroup of the symmetric group whose elements are the permutations of the underlying set of G. Explicitly,
In mathematics, specifically group theory, the index of a subgroup H in a group G is the number of left cosets of H in G, or equivalently, the number of right cosets of H in G. The index is denoted or or . Because G is the disjoint union of the left cosets and because each left coset has the same size as H, the index is related to the orders of the two groups by the formula
In group theory, a field of mathematics, a double coset is a collection of group elements which are equivalent under the symmetries coming from two subgroups, generalizing the notion of a single coset.
In mathematics, the interplay between the Galois group G of a Galois extension L of a number field K, and the way the prime ideals P of the ring of integers OK factorise as products of prime ideals of OL, provides one of the richest parts of algebraic number theory. The splitting of prime ideals in Galois extensions is sometimes attributed to David Hilbert by calling it Hilbert theory. There is a geometric analogue, for ramified coverings of Riemann surfaces, which is simpler in that only one kind of subgroup of G need be considered, rather than two. This was certainly familiar before Hilbert.
In mathematics, a Frobenius group is a transitive permutation group on a finite set, such that no non-trivial element fixes more than one point and some non-trivial element fixes a point. They are named after F. G. Frobenius.
In mathematics, D3 (sometimes alternatively denoted by D6) is the dihedral group of degree 3 and order 6. It equals the symmetric group S3. It is also the smallest non-abelian group.
In mathematics, a permutation group G acting on a non-empty finite set X is called primitive if G acts transitively on X and the only partitions the G-action preserves are the trivial partitions into either a single set or into |X| singleton sets. Otherwise, if G is transitive and G does preserve a nontrivial partition, G is called imprimitive.
In mathematics, specifically group theory, Cauchy's theorem states that if G is a finite group and p is a prime number dividing the order of G, then G contains an element of order p. That is, there is x in G such that p is the smallest positive integer with xp = e, where e is the identity element of G. It is named after Augustin-Louis Cauchy, who discovered it in 1845.