Misplaced Pages

#414585

40-401: The Todd–Coxeter algorithm can be applied to infinite groups and is known to terminate in a finite number of steps, provided that the index of H in G is finite. On the other hand, for a general pair consisting of a group presentation and a subgroup, its running time is not bounded by any computable function of the index of the subgroup and the size of the input data. One implementation of

80-456: A choice of "which coset maps to 1 ∈ Z / p , {\displaystyle 1\in \mathbf {Z} /p,} which shows that this map is a bijection. As a consequence, the number of normal subgroups of index p is for some k; k = − 1 {\displaystyle k=-1} corresponds to no normal subgroups of index p . Further, given two distinct normal subgroups of index p, one obtains

120-410: A coset table, a relation table for each relation in R {\displaystyle R} , and a subgroup table for each generator h i {\displaystyle h_{i}} of H {\displaystyle H} . Information is gradually added to these tables, and once they are filled in, all cosets have been enumerated and the algorithm terminates. The coset table

160-511: A given index p form a projective space , namely the projective space In detail, the space of homomorphisms from G to the (cyclic) group of order p, Hom ⁡ ( G , Z / p ) , {\displaystyle \operatorname {Hom} (G,\mathbf {Z} /p),} is a vector space over the finite field F p = Z / p . {\displaystyle \mathbf {F} _{p}=\mathbf {Z} /p.} A non-trivial such map has as kernel

200-419: A multiple of n because each coset of H contains the same number of cosets of A . Finally, if for some c ∈ G and a ∈ A we have ca = xc , then for any d ∈ G dca = dxc , but also dca = hdc for some h ∈ H (by the definition of A ), so hd = dx . Since this is true for any d , x must be a member of A, so ca = xc implies that cac ∈ A and therefore A is a normal subgroup. The index of

240-468: A normal subgroup of index p, and multiplying the map by an element of ( Z / p ) × {\displaystyle (\mathbf {Z} /p)^{\times }} (a non-zero number mod p ) does not change the kernel; thus one obtains a map from to normal index p subgroups. Conversely, a normal subgroup of index p determines a non-trivial map to Z / p {\displaystyle \mathbf {Z} /p} up to

280-471: A row of a relation or subgroup table is completed, a new piece of information C i = C j g {\displaystyle C_{i}=C_{j}g} , g ∈ X ′ {\displaystyle g\in X'} , is found. This is known as a deduction . From the deduction, we may be able to fill in additional entries of the relation and subgroup tables, resulting in possible additional deductions. We can fill in

320-663: A subgroup of index 3 (this time it is a D 2h prismatic symmetry group, see point groups in three dimensions ), but in this case the whole subgroup is a normal subgroup. All members of a particular coset carry out the same permutation of these cosets, but in this case they represent only the 3-element alternating group in the 6-member S 3 symmetric group. Normal subgroups of prime power index are kernels of surjective maps to p -groups and have interesting structure, as described at Focal subgroup theorem: Subgroups and elaborated at focal subgroup theorem . There are three important normal subgroups of prime power index, each being

360-440: A subgroup table. It has only one row, corresponding to the coset of H {\displaystyle H} itself. It has t columns, and the entry in the j th column is defined (if known) to be k , where C k = H g n 1 g n 2 ⋯ g n j {\displaystyle C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}} . When

400-400: A ∈ A , as desired. Now we show that for any b ∈ B and a ∈ A , ab will be an element of B . This is because the coset Hc is the same as Hca , so Hcb = Hcab . Since this is true for any c (that is, for any coset), it shows that multiplying on the right by ab makes the same permutation of cosets as multiplying by b , and therefore ab ∈ B . What we have said so far applies whether

440-571: Is 2. More generally, | Z : n Z | = n {\displaystyle |\mathbb {Z} :n\mathbb {Z} |=n} for any positive integer n . When G is finite , the formula may be written as | G : H | = | G | / | H | {\displaystyle |G:H|=|G|/|H|} , and it implies Lagrange's theorem that | H | {\displaystyle |H|} divides | G | {\displaystyle |G|} . When G

SECTION 10

#1733085083415

480-400: Is a simple corollary of the above discussion (namely the projectivization of the vector space structure of the elementary abelian group and further, G does not act on this geometry, nor does it reflect any of the non-abelian structure (in both cases because the quotient is abelian). However, it is an elementary result, which can be seen concretely as follows: the set of normal subgroups of

520-397: Is infinite, | G : H | {\displaystyle |G:H|} is a nonzero cardinal number that may be finite or infinite. For example, | Z : 2 Z | = 2 {\displaystyle |\mathbb {Z} :2\mathbb {Z} |=2} , but | R : Z | {\displaystyle |\mathbb {R} :\mathbb {Z} |}

560-425: Is infinite. If N is a normal subgroup of G , then | G : N | {\displaystyle |G:N|} is equal to the order of the quotient group G / N {\displaystyle G/N} , since the underlying set of G / N {\displaystyle G/N} is the set of cosets of N in G . If H has an infinite number of cosets in G , then

600-444: Is maintained. Let 1 = g n 1 g n 2 ⋯ g n t {\displaystyle 1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}} be a relation in R {\displaystyle R} , where g n i ∈ X ′ {\displaystyle g_{n_{i}}\in X'} . The relation table has rows representing

640-459: Is needed to guarantee that the algorithm will terminate provided | G : H | {\displaystyle |G:H|} is finite.) When all the tables are filled, the algorithm terminates. We then have all needed information on the action of G {\displaystyle G} on the cosets of H {\displaystyle H} . Index (group theory) In mathematics , specifically group theory ,

680-401: Is no subgroup of order 15 in S 5 . In the case of n = 2 this gives the rather obvious result that a subgroup H of index 2 is a normal subgroup, because the normal subgroup of H must have index 2 in G and therefore be identical to H . (We can arrive at this fact also by noting that all the elements of G that are not in H constitute the right coset of H and also the left coset, so

720-481: 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 (interpret the quantities as cardinal numbers if some of them are infinite). Thus the index | G : H | {\displaystyle |G:H|} measures the "relative sizes" of G and H . For example, let G = Z {\displaystyle G=\mathbb {Z} } be

760-524: Is used to store the relationships between the known cosets when multiplying by a generator. It has rows representing cosets of H {\displaystyle H} and a column for each element of X ′ {\displaystyle X'} . Let C i {\displaystyle C_{i}} denote the coset of the i th row of the coset table, and let g j ∈ X ′ {\displaystyle g_{j}\in X'} denote generator of

800-419: The ( i , t ) {\displaystyle (i,t)} 'th entry is initially i , since g n 1 g n 2 ⋯ g n t = 1 {\displaystyle g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}=1} . Finally, the subgroup tables are similar to the relation tables, except that they keep track of possible relations of

840-409: 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 | G : H | {\displaystyle |G:H|} or [ G : H ] {\displaystyle [G:H]} or ( G : H ) {\displaystyle (G:H)} . Because G

SECTION 20

#1733085083415

880-425: The j th column. The entry of the coset table in row i , column j is defined to be (if known) k , where k is such that C k = C i g j {\displaystyle C_{k}=C_{i}g_{j}} . The relation tables are used to detect when some of the cosets we have found are actually equivalent. One relation table for each relation in R {\displaystyle R}

920-393: The algorithm proceeds as follows. Suppose that G = ⟨ X ∣ R ⟩ {\displaystyle G=\langle X\mid R\rangle } , where X {\displaystyle X} is a set of generators and R {\displaystyle R} is a set of relations and denote by X ′ {\displaystyle X'}

960-440: The cosets of H {\displaystyle H} , as in the coset table. It has t columns, and the entry in the i th row and j th column is defined to be (if known) k , where C k = C i g n 1 g n 2 ⋯ g n j {\displaystyle C_{k}=C_{i}g_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}} . In particular,

1000-408: The entries of the coset table corresponding to the equations C i = C j g {\displaystyle C_{i}=C_{j}g} and C j = C i g − 1 {\displaystyle C_{j}=C_{i}g^{-1}} . However, when filling in the coset table, it is possible that we may already have an entry for the equation, but

1040-409: The entry has a different value. In this case, we have discovered that two of our cosets are actually the same, known as a coincidence . Suppose C i = C j {\displaystyle C_{i}=C_{j}} , with i < j {\displaystyle i<j} . We replace all instances of j in the tables with i . Then, we fill in all possible entries of

1080-479: The generators of H {\displaystyle H} . For each generator h n = g n 1 g n 2 ⋯ g n t {\displaystyle h_{n}=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}} of H {\displaystyle H} , with g n i ∈ X ′ {\displaystyle g_{n_{i}}\in X'} , we create

1120-511: The group of integers under addition , and let H = 2 Z {\displaystyle H=2\mathbb {Z} } be the subgroup consisting of the even integers . Then 2 Z {\displaystyle 2\mathbb {Z} } has two cosets in Z {\displaystyle \mathbb {Z} } , namely the set of even integers and the set of odd integers, so the index | Z : 2 Z | {\displaystyle |\mathbb {Z} :2\mathbb {Z} |}

1160-402: The index of H in G is said to be infinite. In this case, the index | G : H | {\displaystyle |G:H|} is actually a cardinal number . For example, the index of H in G may be countable or uncountable , depending on whether H has a countable number of cosets in G . Note that the index of H is at most the order of G, which is realized for

1200-440: The index of H is finite or infinte. Now assume that it is the finite number n . Since the number of possible permutations of cosets is finite, namely n !, then there can only be a finite number of sets like B . (If G is infinite, then all such sets are therefore infinite.) The set of these sets forms a group isomorphic to a subset of the group of permutations, so the number of these sets must divide n !. Furthermore, it must be

1240-426: The normal subgroup not only has to be a divisor of n !, but must satisfy other criteria as well. Since the normal subgroup is a subgroup of H , its index in G must be n times its index inside H . Its index in G must also correspond to a subgroup of the symmetric group S n , the group of permutations of n objects. So for example if n is 5, the index cannot be 15 even though this divides 5!, because there

Todd–Coxeter algorithm - Misplaced Pages Continue

1280-454: The permutation group of the left (or right) cosets of H . Let us explain this in more detail, using right cosets: The elements of G that leave all cosets the same form a group. If Hca ⊂ Hc ∀ c ∈ G and likewise Hcb ⊂ Hc ∀ c ∈ G , then Hcab ⊂ Hc ∀ c ∈ G . If h 1 ca = h 2 c for all c ∈ G (with h 1 , h 2 ∈ H) then h 2 ca = h 1 c , so Hca ⊂ Hc . Let us call this group A . Let B be

1320-423: The result that a subgroup of index lowest prime p is normal, and other properties of subgroups of prime index are given in ( Lam 2004 ). The group O of chiral octahedral symmetry has 24 elements. It has a dihedral D 4 subgroup (in fact it has three such) of order 8, and thus of index 3 in O , which we shall call H . This dihedral group has a 4-member D 2 subgroup, which we may call A . Multiplying on

1360-424: The right any element of a right coset of H by an element of A gives a member of the same coset of H ( Hca = Hc ). A is normal in O . There are six cosets of A , corresponding to the six elements of the symmetric group S 3 . All elements from any particular coset of A perform the same permutation of the cosets of H . On the other hand, the group T h of pyritohedral symmetry also has 24 members and

1400-463: The set of elements of G which perform a given permutation on the cosets of H . Then B is a right coset of A . First let us show that if b 1 ∈ B , then any other element b 2 of B equals ab 1 for some a ∈ A . Assume that multiplying the coset Hc on the right by elements of B gives elements of the coset Hd . If cb 1 = d and cb 2 = hd , then cb 2 b 1 = hc ∈ Hc , or in other words b 2 = ab 1 for some

1440-507: The set of generators X {\displaystyle X} and their inverses. Let H = ⟨ h 1 , h 2 , … , h s ⟩ {\displaystyle H=\langle h_{1},h_{2},\ldots ,h_{s}\rangle } where the h i {\displaystyle h_{i}} are words of elements of X ′ {\displaystyle X'} . There are three types of tables that will be used:

1480-452: The smallest normal subgroup in a certain class: As these are weaker conditions on the groups K, one obtains the containments These groups have important connections to the Sylow subgroups and the transfer homomorphism, as discussed there. An elementary observation is that one cannot have exactly 2 subgroups of index 2, as the complement of their symmetric difference yields a third. This

1520-430: The tables, possibly leading to more deductions and coincidences. If there are empty entries in the table after all deductions and coincidences have been taken care of, add a new coset to the tables and repeat the process. We make sure that when adding cosets, if Hx is a known coset, then Hxg will be added at some point for all g ∈ X ′ {\displaystyle g\in X'} . (This

1560-424: The trivial subgroup, or in fact any subgroup H of infinite cardinality less than that of G. A subgroup H of finite index in a group G (finite or infinite) always contains a normal subgroup N (of G ), also of finite index. In fact, if H has index n , then the index of N will be some divisor of n ! and a multiple of n ; indeed, N can be taken to be the kernel of the natural homomorphism from G to

1600-434: The two are identical.) More generally, a subgroup of index p where p is the smallest prime factor of the order of G (if G is finite) is necessarily normal, as the index of N divides p ! and thus must equal p, having no other prime factors. For example, the subgroup Z 7 of the non-abelian group of order 21 is normal (see List of small non-abelian groups and Frobenius group#Examples ). An alternative proof of

#414585