{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "

\n", "Abstract Algebra: An Interactive Approach, 2e\n", "

\n", "\n", "

\n", "\n", "\n", "\n", "

\n", "Chapter 8
\n", "Solvable and Insoluble Groups\n", "

\n", "\n", "\n", "

Initialization: This cell MUST be evaluated first:

" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "%display latex\n", "try:\n", " load('absalgtext.sage')\n", "except IOError:\n", " load('/media/sf_sage/absalgtext.sage')" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Subnormal Series and the Jordan-Hölder Theorem
\r\n", "Derived Group Series
\r\n", "Polycylic Groups
\r\n", "Solving the Pyraminx™
\r\n", "Sage Interactive Problems
\r\n", "\r\n", "\r\n", "

Subnormal Series and the Jordan-Hölder Theorem

\r\n", "\r\n", "
\r\n", "In this chapter we will study the concept of solvable groups. Every group will be classified either as solvable or insoluble, and in fact most of the groups we \r\n", "have looked at so far turn out to be solvable.

\r\n", "\r\n", "Solvable groups play a key role in studying polynomial equations. Whether or not a given polynomial can be solved in terms of radicals (square roots, cube \r\n", "roots, etc.) depends on whether a certain group corresponding to that polynomial is a solvable group. In fact this application is the origin of the \r\n", "term "solvable group."

\r\n", "\r\n", "Before we introduce the true definition of a solvable group, we must make some preliminary definitions. We have already encountered situations in which we had a \r\n", "normal subgroup of a normal subgroup, such as in the third isomorphism theorem. But suppose we have a whole series of subgroups of a group G, each one \r\n", "fitting inside of the previous one like Russian dolls.

\r\n", "\r\n", "DEFINITION 8.1
\r\n", "A subnormal series for a group G is a sequence G₀, G₁, G₂, … G_n of \r\n", "subgroups of G such that\r\n", "

G = G₀ ⊇ G₁ ⊇ G₂ ⊇ \r\n", "⋯ ⊇ G_n = {e}.

\r\n", "where each G_i is a normal subgroup of G_i−1 for i = 1, 2,…, n.

\r\n", "\r\n", "A subnormal series is called a normal series if it satisfies the stronger condition that all of the groups G_i are normal subgroups of \r\n", "the original group G. We will be mainly interested in subnormal series, but there are a few of the exercises regarding normal series.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Consider the group S₄, for which we have seen a normal subgroup of order 4, namely
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "K = Group( C(1,2)*C(3,4), C(1,3)*C(2,4) ); K" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Certainly the identity element is a normal subgroup of K, so we can write\r\n", "

S₄ ⊇ K ⊇ {( )}

\r\n", "which would be a subnormal series of length n = 2. Is there a way that we can make a longer series out of this one? Because A₄ is also a \r\n", "normal subgroup of S₄, and K is a normal subgroup of A₄, we can slip this group into our series. Also, the group \r\n", "K contains some proper subgroups, which will be normal subgroups of K since K is abelian. For an example of a proper subgroup, consider
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "H = Group( C(1,2)*C(3,4) ); H" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Therefore, we have a longer subnormal series for S₄:\r\n", "

S₄ ⊇ A₄ ⊇ K ⊇ H ⊇ {( )}.

\r\n", "We say that this new subnormal series is a refinement of the first subnormal series.

\r\n", "\r\n", "DEFINITION 8.2
\r\n", "We say that a subnormal (or normal) series \r\n", "

G = H₀ ⊇ H₁ ⊇ H₂ ⊇ \r\n", "⋯ ⊇ H_k = {e}

\r\n", "is a refinement of the subnormal (or normal) series\r\n", "

G = G₀ ⊇ G₁ ⊇ G₂ ⊇ \r\n", "⋯ ⊇ G_n = {e}

\r\n", "if each subgroup G_i appears as H_j for some j.

\r\n", "\r\n", "Is there a way that we can refine our subnormal series to produce an even longer chain? Our definition did not exclude the possibility of two groups in the series \r\n", "being the same, so we could consider\r\n", "

S₄ ⊇ A₄ ⊇ A₄ ⊇ K ⊇ H ⊇ H \r\n", "⊇ H ⊇ {( )}.

\r\n", "This is certainly a longer subnormal series, but it is rather pointless to repeat the same subgroup in the series. Let us make the following definition:

\r\n", "\r\n", "DEFINITION 8.3
\r\n", "A composition series of a group G is a subnormal series\r\n", "

G = G₀ ⊇ G₁ ⊇ G₂ ⊇ \r\n", "⋯ ⊇ G_n = {e},

\r\n", "for which each subgroup is smaller than the proceeding subgroup, and for which there is no refinement that includes additional subgroups.\r\n", "

\r\n", "\r\n", "
\r\n", "Using this definition, we see that\r\n", "

S₄ ⊇ A₄ ⊇ K ⊇ H ⊇ {( )}

\r\n", "is a composition series for S₄, since no subgroups are repeated, and there simply isn't enough room between two of these subgroups to slip in \r\n", "another subgroup. For example, A₄ is half of the size of S₄, so any subgroup containing more than A₄ must be \r\n", "all of S₄. In fact, we can easily test to see whether a subnormal series is a composition series.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 8.1
\r\n", "The subnormal series\r\n", "

G = G₀ ⊇ G₁ ⊇ G₂ ⊇ \r\n", "⋯ ⊇ G_n = {e}

\r\n", "is a composition series if, and only if, all of the quotient groups G_k−1/G_k are nontrivial simple groups.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "The quotient groups G_k−1/G_k in a composition series for G are called the composition factors of \r\n", "the composition series.

\r\n", "\r\n", "For example, let us find the composition factors for the composition series for S₄:\r\n", "

S₄ ⊇ A₄ ⊇ K ⊇ H ⊇ {( )}

\r\n", "We have\r\n", "

S₄/A₄ ≈ Z₂, A₄/K ≈ \r\n", "Z₃, K/H ≈ Z₂, and H/{()} ≈ Z₂.

\r\n", "So the composition factors are Z₂, Z₃, Z₂, and Z₂, which are all simple groups, as we \r\n", "would expect.

\r\n", "\r\n", "It is certainly possible for a group to have more than one composition series. For example, if we pick the subgroup
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "B = Group( C(1,4)*C(2,3) ); B" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "then B is a normal subgroup of K. Thus we would have the composition series\r\n", "

S₄ ⊇ A₄ ⊇ K ⊇ B ⊇ {( )}

\r\n", "Even though this is a different composition series, the composition factors are isomorphically the same. Will this happen all of the time? To show that it will, we \r\n", "first need the following lemmas:\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 8.1
\r\n", "Let X, Y, and Z be three subgroups of the group G, with Y being a subgroup of X, and Y·Z = \r\n", "Z·Y. Then\r\n", "

X ∩ (Y·Z) = Y·(X ∩ Z) = (X ∩ \r\n", "Z)·Y.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "\r\n", "Lemma 8.2
\r\n", "Let X, Y, and Z be three subgroups of the group G, with Y being a normal subgroup of X, and Z a normal \r\n", "subgroup of G. Then Y·Z is a normal subgroup of X·Z, and\r\n", "

(X·Z)/(Y·Z) ≈ X/(X ∩(Y·Z)).

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "We are now ready to show that any two composition series for a group are related. We do this by proving a theorem that is true for any two subnormal series, and then \r\n", "apply that theorem to a composition series.\r\n", "\r\n", "

\r\n", "\r\n", "THEOREM 8.1: The Refinement Theorem
\r\n", "Suppose that there are two subnormal series for a group G. That is, there are subgroups A_i and B_j such that\r\n", "

G = A₀ ⊇ A₁ ⊇ A₂ ⊇ \r\n", "⋯ ⊇ A_n = {e},

\r\n", "and\r\n", "

G = B₀ ⊇ B₁ ⊇ B₂ ⊇ \r\n", "⋯ ⊇ B_m = {e},

\r\n", "where each A_i is a normal subgroup of A_i−1, and each B_j is a normal subgroup \r\n", "of B_j−1. Then it is possible to refine both series by inserting the subgroups\r\n", "

A_i−1 = A_i,0 ⊇ A_i,1 ⊇ \r\n", "A_i,2 ⊇ ⋯ ⊇ A_i,m = A_i, i = 1, 2, … n,

\r\n", "

B_j−1 = B_j,0 ⊇ B_j,1 ⊇ \r\n", "B_j,2 ⊇ ⋯ ⊇ B_j,n = B_j, j = 1, 2, … m,

\r\n", "in such a way that\r\n", "

A_i,j−1/A_i,j ≈ \r\n", "B_j,i−1/B_j,i.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "If we now apply the refinement theorem to two composition series we find that the composition factors will be the same.\r\n", "\r\n", "

\r\n", "\r\n", "THEOREM 8.2: The Jordan-Hölder Theorem
\r\n", "Let G be a finite group, and let\r\n", "

G = A₀ ⊇ A₁ ⊇ A₂ ⊇ \r\n", "⋯ ⊇ A_n = {e},

\r\n", "and\r\n", "

G = B₀ ⊇ B₁ ⊇ B₂ ⊇ \r\n", "⋯ ⊇ B_m = {e}

\r\n", "be two composition series for G. Then n = m, and the composition factors A_i−1/A_i \r\n", "are isomorphic to the composition factors B_j−1/B_j in some order.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "The Jordan-Hölder theorem (8.2) shows that the composition factors do not depend on the composition series, but rather the finite group G. This is \r\n", "reminiscent of the unique factorization of integers, where every positive integer greater than 1 can be written as a unique product of prime numbers. Since the \r\n", "composition factors are always nontrivial simple groups, in a sense the simple groups play the same role in group theory that prime numbers play in number theory. The \r\n", "correspondence is heightened by the fact that Z_p is a nontrivial simple group if, and only if, p is a prime number. However, we have seen \r\n", "that there are other simple groups, such as Aut(Z₂₄^*) and A_n for n > 4.

\r\n", "\r\n", "Since these non-cyclic simple groups are rather large (at least 60 elements), they will only show up as composition factors for very large groups. For example, a \r\n", "composition series for S₅ is given by\r\n", "

S₅ ⊃ A₅ ⊃ {( )}, S₅/A₅ ≈ \r\n", "Z₂, A₅/{( )} ≈ A₅.

\r\n", "Since Z₂ and A₅ are both simple groups, this is a composition series, and the composition factors of S₅ are \r\n", "Z₂ and A₅.

\r\n", "\r\n", "The composition series play a vital role in determining whether groups are solvable or not. However, we will hold off on the definition of a solvable group until we \r\n", "have defined another tool in group theory, the derived group.

\r\n", "\r\n", "\r\n", "

Derived Group Series

\r\n", "\r\n", "
\r\n", "In the last section we saw that two different composition series produced the same composition factors. In this section we will find a method for producing a \r\n", "composition series that is easily implimented using Sage. This method hinges on the concept of a "commutator."

\r\n", "\r\n", "DEFINITION 8.4
\r\n", "Given two elements x and y of a group G, the commutator of x and y is the \r\n", "element x^-1·y^-1·x·y, and is written [x, y].

\r\n", "\r\n", "Notice that if G is an abelian group the commutator will always give the identity element.

\r\n", "\r\n", "We can also consider the commutator of two subgroups of G. If H and K denote two subgroups, then consider the set\r\n", "

{ x^-1·y^-1·x·y | x ∈ \r\n", "H and y ∈ K }.

\r\n", "Will this set form a group? Unfortunately, not always.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Consider the subgroups H = {( ), (1 2)} and K = {( ), (2 3 4), (2 4 3)} of \r\n", "S₄.\r\n", "Then the set of all elements of the form x^-1·y^-1·x·y with x in X and \r\n", "y in Y can be found by making a table:

\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

x^-1·y^-1·x·y		( )	(2 3 4)	(2 4 3)
	\|
( )	\|	( )	( )	( )
(1 2)	\|	( )	(1 4 2)	(1 3 2)

\r\n", "\r\n", "
\r\n", "So the elements of the form x^-1·y^-1·x·y with x in H and y \r\n", "in K is the set\r\n", "

{( ), (1 3 2), (1 4 2)}.

\r\n", "This is not a subgroup.

\r\n", "\r\n", "However, all is not lost, for we can consider the group generated by all of the commutators.

\r\n", "\r\n", "DEFINITION 8.5
\r\n", "Given two subgroups H and K of a group G, we define the mutual commutator subgroup of H and K, denoted \r\n", "[H, K], to be the subgroup generated by the elements\r\n", "

{ x^-1·y^-1·x·y | x ∈ \r\n", "H and y ∈ K }.

\r\n", "\r\n", "Although this definition circumvents the problem that the set of commutators do not always form a group, it creates difficulty in proving some of the theorems about \r\n", "the mutual commutator subgroups. This is because whenever u is in [H, K] we cannot say \r\n", "that u = x^-1·y^-1·x·y for some x in H and some y \r\n", "in K. Rather, we have to write\r\n", "

u = u₁·u₂ ⋯ u_n,

\r\n", "where each u_i = \r\n", "x_i^-1·y_i^-1·x_i·y_i. Yet in spite of this \r\n", "difficulty, we will be able to discover some remarkable properties of the mutual commutator groups.

The Sage command for finding the mutual \r\n", "commutator subgroup of H and K is MutualCommutator(H, K). For example, we can find the mutual commutator subgroup of H and \r\n", "K by the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "H = Group( C(1,2) ); H" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "K = Group( C(2,3,4) ); K" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MutualCommutator(H, K)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that there are elements in [H, K] that are neither in H nor in K.

\r\n", "\r\n", "One of the simple facts that we can prove for mutual commutator subgroups is that [H, K] will be a normal subgroup whenever H and K \r\n", "are normal.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 8.2
\r\n", "If H and K are normal subgroups of G, then [H, K] is a normal subgroup of G.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Many times one of the two groups H or K will be the whole group G. We call the subgroup [G, H] \r\n", "the commutator subgroup of H in G. In this case Sage can find the commutator subgroup faster with the \r\n", "simplified command Commutator(G, H).

\r\n", "\r\n", "Note that this Sage command assumes that H is a subgroup of G. In fact, Sage will correctly find the commutator subgroup if only \r\n", "the generators of H are specified. For example, suppose we wish to find the commutator [S₄, A₄].

\r\n", "\r\n", "We first find the group S₄:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S4 = Group( C(1,2), C(1,2,3,4) )\r\n", "S4" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Since A₄ is generated by the 3-cycles C[1,2,3] and C[2,3,4], we can load this group as follows:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "A4 = Group( C(1,2,3), C(2,3,4) )\r\n", "A4" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Rather than using the command Commutator(S4, A4) it is faster to use only the generators of A₄:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Commutator(S4, [C(1,2,3), C(2,3,4)] )" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This gives us the group A₄ again.

\r\n", "\r\n", "What would happen if took the commutator subgroup of the entire group? That is, what if we considered [S₄, S₄]? Let's try it.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Commutator(S4, [C(1,2), C(1,2,3,4)] )" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This gives us the subgroup A₄ again. So the commutator subgroup of S₄ with itself is something other \r\n", "than S₄.

\r\n", "\r\n", "DEFINITION 8.6
\r\n", "We define the commutator subgroup of G with itself, [G, G], to be the derived group of G, \r\n", "denoted G′.

\r\n", "\r\n", "Since G is a normal subgroup of itself, Proposition 8.2 states that the derived group will be a normal subgroup of G. Since the commutator of any \r\n", "two elements in an abelian group is e, [G, G] will be the trivial group whenever G is abelian. In fact, the size of the derived group \r\n", "in a sense measures just how non-commutative the group is.

Before we explore other properties of the derived group, let us look at some more examples. We know \r\n", "that the derived group of S₄ is A₄, so what is the derived group of A₄? Let's explore:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "K = Commutator(A4, [C(1,2,3), C(2,3,4)] ); K" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This is the normal subgroup of order 4. What if we took the derived group of this group?
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Commutator(K, K)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This is to be expected, since the group K was abelian. In this case we happened to find all of the normal subgroups of S₄ by taking \r\n", "successive derived groups.

\r\n", "\r\n", "We can denote the derived group of the derived group G′ as G′′. Likewise, the derived group of G′′ will be \r\n", "denoted G′′′, and so on. Because each of these groups is a normal subgroup of the previous one, we have the series\r\n", "

G ⊇ G′ ⊇ G′′ ⊇ G′′′ ⊇ ⋯.

\r\n", "This is called the derived series for the group G. The derived series is in fact a subnormal series as long as the groups keep getting smaller and \r\n", "smaller until they finally get to the trivial subgroup {e}. Will this always happen?

\r\n", "\r\n", "It is not hard to think of a group where the derived series never gets to the element {e}. Consider the group A₅. We have already seen that \r\n", "this is a simple group, and since [A₅, A₅] must be a normal subgroup of A₅, we have \r\n", "that [A₅, A₅] is either A₅ or {e}. But A₅ is not \r\n", "abelian, so [A₅, A₅] can't be {e}. Hence the derived series for A₅ is\r\n", "

A₅ ⊇ A₅ ⊇ A₅ ⊇ A₅ ⊇ ⋯

\r\n", "which never gets to {e}.

\r\n", "\r\n", "We want to characterize those groups in which the derived series eventually becomes the trivial group.

\r\n", "\r\n", "DEFINITION 8.7
\r\n", "A group G is called solvable if the derived series\r\n", "

G ⊇ G′ ⊇ G′′ ⊇ G′′′ ⊇ ⋯.

\r\n", "includes the trivial group in a finite number of steps. If the derived series never reaches the trivial group, G is said to be insoluble.

\r\n", "\r\n", "By our experiments, we see that S₄ is a solvable group, whereas A₅ is not. Whenever we have a solvable group G, the \r\n", "derived series is in fact a subnormal series for G. So it is natural that the derived series would shed some light as to what the composition factors \r\n", "of G are. First we will need the following lemma, which characterizes the derived group.\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 8.3
\r\n", "Let G be a group. Then the derived group G′ is the smallest normal subgroup for which the quotient group is abelian.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "We now can express a relationship between the composition factors of a group and the derived series of a group.\r\n", "\r\n", "

\r\n", "\r\n", "THEOREM 8.3: The Solvability Theorem
\r\n", "Let G be a finite group. Then G is solvable if, and only if, the composition factors of G are cyclic groups of prime order.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Historically, solvability was defined in terms of the composition factors. But this definition could only be used on finite groups, since infinite groups do not have \r\n", "a composition series. By defining solvability in terms of the derived series, we allow for infinite groups to be solvable.

\r\n", "\r\n", "For example, the group of integers ℤ is abelian, so the derived group is the trivial group. Hence, ℤ is solvable, yet there is no composition series \r\n", "for ℤ. This is because every proper subgroup of ℤ is isomorphic to ℤ.

\r\n", "\r\n", "From the solvability theorem we see that for finite group, solvability can be defined in terms of the composition factors. That is, a finite group is solvable as long \r\n", "as there are none of those huge non-abelian simple groups appearing either as a subgroup or a quotient group. So we can quickly tell that a group of order 48 must \r\n", "be solvable, since the smallest non-abelian simple group is A₅, which is of order 60.

\r\n", "\r\n", "Does this hold true for infinite groups as well? That is, is an infinite group solvable as long as there is no non-abelian simple group (finite or infinite) \r\n", "lurking somewhere within its structure, either as a subgroup or as a quotient group? To shed some light on this problem, we will first need the following lemma.\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 8.4
\r\n", "If N is a normal subgroup of G, and H is a subgroup of G, then\r\n", "

(H·N/N)′ = (H′·N)/N.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "With this simple lemma we will be able to show the relationship with a solvable group to its subgroups and quotient groups.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 8.3
\r\n", "Suppose that G is a group and H is a normal subgroup of G. Then G is solvable if, and only if, both H and \r\n", "G/H are solvable.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "From this proposition, we see that for an infinite solvable group there cannot be any non-abelian simple groups within its structure whether as a subgroup, a quotient \r\n", "group, a subgroup of a quotient group, etc. Thus the current definition of solvability for infinite groups agrees with the historical notion of a group that does not \r\n", "contain non-abelian simple groups in the composition factors.

\r\n", "\r\n", "Why do we want to know whether a group is solvable or not? We already mentioned one important application, that a polynomial equation will be solvable by \r\n", "radicals if, and only if, a corresponding group is solvable. But there is another application which we have been using throughout these notebooks unawares. Most of \r\n", "the groups used in these notebooks were entered into Sage using the InitGroup command along with a series \r\n", "of Define commands. For example, all of the groups up to order 16 were defined this way, and even S₄ was introduced as the \r\n", "octahedronal group, and defined in terms of 3 generators. Occasionally, we defined a group in terms of a subset of a symmetric group. For \r\n", "example, A₅ and Aut(Z₂₄^*) were defined as subgroups of S₅ and \r\n", "S₇ respectively.

\r\n", "\r\n", "By now, we can see the pattern. The solvable groups could be entered into Sage using the InitGroup and Define \r\n", "commands, whereas the insoluble groups had to be considered as a subgroup of a symmetric group. In the next section, we will see not only why this is so, but \r\n", "will determine a procedure for entering any finite solvable group into Sage.

\r\n", "\r\n", "\r\n", "

Polycyclic Groups

\r\n", "\r\n", "
\r\n", "Throughout these notebooks, we have been using the Sage commands InitGroup and Define to produce many of the groups that we \r\n", "have been studying. Only occasionally did we have to use a different method for representing groups, such as in the groups A₅ and \r\n", "Aut(Z₂₄^*). However, the exact method for converting a finite group into a set of Sage commands has never been fully \r\n", "explained. We know that the groups can be represented by a small number of generators. How do we know how many? Why was S₄ defined in \r\n", "Sage with three generators when only two generators would generate the group?

\r\n", "\r\n", "The secret to defining a group G in Sage using a set of generators comes from the composition series for G. Whenever G is solvable \r\n", "the composition factors of the series will all be cyclic groups of prime order. With such a composition series, we can define a group in Sage, but this is \r\n", "actually more than we need. Suppose that we insisted that the factors of a series are cyclic, but not necessarily of prime order. This leads to the following \r\n", "definition.

\r\n", "\r\n", "DEFINITION 8.8
\r\n", "A subnormal series\r\n", "

G = G₀ ⊇ G₁ ⊇ G₂ ⊇ \r\n", "⋯ ⊇ G_n = {e}

\r\n", "is a polycyclic series if the quotient groups G_i−1/G_i are all cyclic groups. The number n is \r\n", "called the length of the polycyclic series.

\r\n", "\r\n", "It is obvious that a group with a polycyclic series must be solvable, since the cyclic quotient groups would be solvable. On the other hand, any finite solvable group \r\n", "has a polycyclic series, since a composition series would have cyclic factors of prime order.

\r\n", "\r\n", "It should be noted that an infinite solvable group may not always have a polycyclic series. The groups that have a polycyclic series, whether or not they \r\n", "are finite, are called polycyclic groups. We will mainly be concerned with finite groups in this section, so this distinction will not be important.

\r\n", "\r\n", "The first step in expressing a finite group in Sage is to find a polycyclic series for the group, preferably with the smallest possible length. For example, \r\n", "the quaternionic group Q has a normal subgroup of order 4: {1, i, −1, −i}. This is of course cyclic, and the quotient group \r\n", "is isomorphic to Z₂, which is also cyclic. Thus, there is a polycyclic series of Q of length 2. The length of the polycyclic series will \r\n", "be the number of generators required for expressing the group in Sage, so naturally the shorter the polycyclic series, the less work the \r\n", "definition entails.

\r\n", "\r\n", "Our strategy will be to work inductively on the length of the series. That is, given a polycyclic series for a polycyclic group,\r\n", "

G = G₀ ⊇ G₁ ⊇ G₂ ⊇ \r\n", "⋯ ⊇ G_n = {e},

\r\n", "we will begin by defining G_n, the trivial group, and then define G_i−1 in terms of G_i. Thus, \r\n", "after n steps, we will have defined the group G into Sage.

\r\n", "\r\n", "Defining G_n is easy, since this is the trivial group. This group is defined by the single command

\r\n", "\r\n", "InitGroup(\"e\")

\r\n", "\r\n", "where e is the name of the identity element.

\r\n", "\r\n", "Next we add the variables for the group, in the order of the polycyclic series.

\r\n", "\r\n", "AddGroupVar(\"g₁\", \"g₂\", … \r\n", "\"g_n\")

\r\n", "We will suppose that the group G_i is defined inductively by Sage in terms of the elements g_i+1, \r\n", "g_i+2, …, g_n. Since G_i−1/G_i is cyclic, there is a generator \r\n", "of this quotient group, which we will call g_i·G_i, where g_i is in the \r\n", "subgroup G_i−1. If this quotient group is of order \r\n", "m_i, then (g_i·G_i)^mⁱ = G_i, so \r\n", "g_i^mⁱ ∈ G_i. So Sage can \r\n", "represent g_i^mⁱ in terms of the elements g_i+1, \r\n", "g_i+2, …, g_n. Thus, we can make the definition

\r\n", "\r\n", "Define(g_i^m_i, b)

\r\n", "\r\n", "where b is the Sage representation of g_i^mⁱ in terms of \r\n", "the elements g_i+1, \r\n", "g_i+2, …, g_n.

\r\n", "\r\n", "Our goal will be to have Sage express every element in terms of generators that are multiplied in increasing order. We consider the \r\n", "generators g₁, g₂, g₃, … as "letters," going in alphabetical order, then we need \r\n", "definitions which would find a way of expressing any element of the group as a product of generators such that the generators are in alphabetical order. That is, \r\n", "the expression g₂·g₃·g₁ will need to be reduced, whereas \r\n", "g₁·g₂·g₃·g₃ does not. As such, we have to program Sage \r\n", "to unravel expressions that are "in the wrong order." Any expression in the wrong order will contain a \r\n", "sequence g_k·g_i, where k > i. Since G_i is a normal subgroup \r\n", "of G_i−1, g_i^-1·g_k·g_i = y_k is \r\n", "in G_i, and hence can be expressed in Sage in terms of the elements g_i+1, \r\n", "g_i+2, …, g_n. We can perform the following sequence of commands to \r\n", "force Sage to always put the generators in the proper order.

\r\n", "\r\n", "Define(g_i^-1*g_i+1*g_i, \r\n", " y_i+1)
\r\n", "Define(g_i^-1*g_i+2*g_i, \r\n", " y_i+2)
\r\n", " ………
\r\n", "Define(g_i^-1*g_n*g_i, \r\n", " y_n)

\r\n", "\r\n", "\r\n", "With these definitions, Sage will continue to process a given element until the generators are arranged in order. Although it is not clear right now that a \r\n", "given element can be expressed as a product of generators arranged in order, we will see that the group generated by the \r\n", "elements {g_i, g_i+1, … g_n} will be isomorphic to G_i−1. Thus, \r\n", "we will be able to construct the group G inductively.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Use a polycyclic series to define the group Q in Sage.

\r\n", "\r\n", "The first step is to find a polycyclic series for Q, which \r\n", "we have already found:\r\n", "

G₀ = Q ⊃ G₁ = {1, i, −1, −i} ⊃ \r\n", "G₂ = {1}.

\r\n", "Since this is a series of length 2, we will need 2 generators. We begin by defining G₂, the trivial group:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The next step is to determine what all of the generators will be. To find g₂, we need to find a generator of the \r\n", "group G₁/G₂. Certainly {i} or {−i} \r\n", "would work, so we let g₂ be one of these elements. We might as well pick g₂ = i.

\r\n", "\r\n", "We then observe that G₀/G₁ is of order 2, and a generator \r\n", "is {j, k, −j, −k}. We pick g₁ to be any one of these elements, \r\n", "say j.

\r\n", "\r\n", "To make this a true polycyclic group, it is important that we add the generator names in the left to right order of the polycyclic series.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddGroupVar(\"j\", \"i\")" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We are now ready to define G₁. Since G₁/G₂ is cyclic of order 4, we have that i⁴ is in \r\n", "G₂, which is the identity. So we \r\n", "can define
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(i^4, e)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This defines G₁. We now observe that G₀/G₁ is of order 2, so j² must be in \r\n", "G₁, and in fact j² = −1 = i². So we can define
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(j^2, i^2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Finally, we note that j^-1·i·j must be in G₁. In fact, \r\n", "j^-1·i·j = (j·i²)·i·j = \r\n", "i³. We will use a rather unusual Define command this time to enter this information into Sage:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(j^-1*i*j, i^3)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In spite of the unusual way we defined the group, we can still display it.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(j, i)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The purpose of defining the group the way we did in Sage is that we can convert the group to a Polycyclic format. This is done with the \r\n", "command ToPolycyclic().
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q = ToPolycyclic()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We still can see our group,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "only now all products are simplified to a standardized form.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "j^4 * i^2 * j" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This is like having the best parts of ReducedMultiplication and ListGroup at the same time. This makes working with polycyclic groups \r\n", "much easier and faster that groups defined the standard way. Too bad we only learned about it near the end of the section on groups.

\r\n", "\r\n", "To get the group definition that we are more familier with, we can take the "mirror image" of this definition, where all products are done in reverse order.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"i\",\"j\")\r\n", "Define(i^4, e)\r\n", "Define(j^2, i^2)\r\n", "Define(j*i, i^3*j)\r\n", "ListGroup()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "However, this violates the rules for a polycyclic definition. If we try to force this to a polycyclic group:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q = ToPolycyclic()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we find that it doesn't work.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Use the polycyclic series for S₄:\r\n", "

G₀ = S₄ ⊇ G₁ = \r\n", "A₄ ⊇ G₂ = K ⊇ G₃ = H ⊇ G₄ = {( )}

\r\n", "to enter this group into Sage as a polycyclic group.

\r\n", " \r\n", "Since there are four cyclic quotient groups, we will need four generators g₁, \r\n", "g₂, g₃, g₄ such \r\n", "that g_i G_i is a generator \r\n", "of G_i−1/G_i. Some obvious choices \r\n", "are g₁ = (1 2), g₂ = (1 2 3), g₃ = (1 3)(2 4), and \r\n", "g₄ = (1 2)(3 4). We can use a, b, c, and d for the 4 generators.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\",\"b\",\"c\",\"d\")" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Next, g_i^mⁱ ∈ G_i, where m_i is the order of G_i−1/G_i. Looking at the polycyclic series \r\n", "for S₄, we find that m₁ = 2, m₂ = 3, \r\n", "m₃ = 2, and m₄ = 2. Hence we \r\n", "calculate g₁² = ( ), g₂³ = ( ), g₃² = ( ), and g₄² = ( ). In this case, all of these turned out to be \r\n", "the identity element, but we are only promised that g_i^mⁱ will be \r\n", "in G_i, and hence expressible in terms \r\n", "of g_i+1, …, g_n.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(a^2, e)\r\n", "Define(b^3, e)\r\n", "Define(c^2, e)\r\n", "Define(d^2, e)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Finally, we calculate g_i^-1·g_j·g_i for \r\n", "each j > i, and express each of these in terms of g_i+1, … \r\n", "g_n. We find that g₁^-1·g₂·g₁ \r\n", "= (1 3 2) = g₂², \r\n", "g₁^-1·g₃·g₁ = (1 4)(2 3) = \r\n", "g₃·g₄,\r\n", "g₁^-1·g₄·g₁ = (1 2)(3 4) = \r\n", "g₄, g₂^-1·g₃·g₂ =\r\n", "(1 4)(2 3) = g₃·g₄,\r\n", "g₂^-1·g₄·g₂ = (1 3)(2 4) = \r\n", "g₃, and g₃^-1·g₃·g₂ = \r\n", "(1 2)(3 4) = g₄.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(a^-1*b*a, b^2)\r\n", "Define(a^-1*c*a, c*d)\r\n", "Define(a^-1*d*a, d)\r\n", "Define(b^-1*c*b, c*d)\r\n", "Define(b^-1*d*b, c)\r\n", "Define(c^-1*d*c, d)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This should now define the group using 4 generators. Because of the way we defined the group, we can convert it to a \r\n", "polycyclic group.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(a,b,c,d)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Sage is expressing each element as a product of generators, but not always in \r\n", "alphabetical order. But since we used a polycyclic series to define this group,\r\n", "we can convert it to a polycyclic form.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S4 = ToPolycyclic()" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S4" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We now see every element in a form where the generators are in alphabetical order. We can double check that we have created the group S₄.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "StructureDescription()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXAMPLE:
\r\n", "Enter the mystery group A into Mathematica using a polycyclic series.

\r\n", "\r\n", "Let A be a group of order 16 with the elements\r\n", "

{1, L, M, N, O, P, Q, R, S, T, U, V, \r\n", "W, X, Y, Z}.

\r\n", "Suppose we are given the following multiplication table:\r\n", "\r\n", "

The mystery group A:

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

\r\n", "\r\n", "
\r\n", "Although our tendency is to look for hidden words, we really should be looking for hidden subgroups. Is this a group that we have seen before in some other \r\n", "form? Notice that as we look down the main diagonal, we see the element 1 only four times. So only three elements are of order 2, namely Y, S, and \r\n", "Q. But the only other elements appearing in the main diagonal are Y and S. Thus, the forth power of every element must be 1. Since there are \r\n", "no elements of order 8, this cannot be any of the groups of the form Z₈ ⋊_ϕ Z₂ that we studied \r\n", "in §6.4. Also, this group is not abelian, since Z·W = T, while W·Z = V.

\r\n", "\r\n", "To find some subgroups, we can begin by looking at the center of the group. An element will be in the center if the corresponding row and column are identical. Looking \r\n", "at the multiplication table, we find that 1, Y, S, and Q are in the center. Since this is a normal subgroup it is natural to look at the \r\n", "quotient group. We can use the table to find the left cosets: {1, Y, S, Q}, {Z, X, R, \r\n", "P}, {W, U, O, M}, and {V, T, N, L}. Both the center and its quotient group \r\n", "are isomorphic \r\n", "to Z₈^*, so to produce a polycyclic series we need to add two more subgroups:\r\n", "

A ⊃ {1, Y, S, Q, Z, X, R, P} ⊃ \r\n", "{1, Y ,S, Q} ⊃ {1, Y} ⊃ {1}.

\r\n", "Each quotient group is isomorphic to Z₂. Certainly this series would do, but it would involve 4 generators. Is there a shorter polycyclic \r\n", "series?

\r\n", "\r\n", "Looking at the table, one might have noticed the subgroup in the top left hand corner: {1, Z, Y, X}. Since Z is a generator of \r\n", "this subgroup, we have a cyclic group of order 4. Using this group in the polycyclic series would shorten it by at least one subgroup. We can notice from the table \r\n", "that both the left and right cosets of {1, Z, Y, X} are\r\n", "

{{1 ,Z, Y, X}, {W, V, U, T}, \r\n", "{S, R, Q, P}, {O, N, M, L}}.

\r\n", "Thus, {1, Z, Y, X} is a normal subgroup of A. Also notice that {W, V, U, T} generates the \r\n", "quotient group. Thus, both the subgroup and the quotient group are isomorphic to Z₄. Therefore, we have a much shorter polycyclic series:\r\n", "

G₀ = A ⊃ G₁ = {1, Z, Y, X} ⊃ \r\n", "G₂ = {1}.

\r\n", "By using this series, we need only two generators, a and b. Since G₁/G₂ has two generators, {Z} and \r\n", "{X}, we can let b represent either element, say b = Z. Then b⁴ = Z⁴ is \r\n", "in G₂ = {1}, and so we have the definition
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\",\"b\")\r\n", "Define(b^4, e)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Next, we notice that both {W, V, U, T} and {O, N, M, L} are generators \r\n", "of G₀/G₁. Thus, we can let a be any of these 8 elements. If we let a = W, then \r\n", "a⁴ = W⁴ is in G₁, and in fact a⁴ = e. So we have the definition
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(a^4, e)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We also need to let Sage know how to handle the combination b·a. Using the multiplication table we have \r\n", "that a^-1·b·a = W^-1·Z·W = \r\n", "X = b³. So a^-1·b·a = b³. Let us add this fact \r\n", "into Sage:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(a^-1*b*a, b^3)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We now have the group entered into Sage.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "A = ListGroup(); A" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(A)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Because we used a polycyclic series to define the group, we can convert it to a polycyclic group.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "A = ToPolycyclic()" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "A" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(A)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Even though we have entered this group into Sage, we still have not identified this group in terms of the groups that we are familiar with. We can have Sage\r\n", "determine what the group is:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "StructureDescription()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This group is a semi-direct product of Z₄ with itself. In fact, it is the only such semi-direct product, so we can refer to this group \r\n", "as Z₄ ⋊ Z₄.

\r\n", "\r\n", "Both Sage's pc groups and Mathematica's groups are rewriting systems. That is, the fundamental methodology is to replace certain combinations of \r\n", "generators with other combinations until no more possible replacements are possible. But there is still one question that we have not addressed. How do we \r\n", "know for certain that the computer will not get hung in a loop? To illustrate the potential problem, suppose we tried to enter a group using the following commands:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"x\",\"y\")\r\n", "Define(x^3, e)\r\n", "Define(y^6, e)\r\n", "Define(y*x, x^2*y^2)\r\n", "G = Group(x,y)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(G)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "ListGroup()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "Sage was actually able to define this group, because it uses a different algorithm than Mathematica. So Sage catches the fact that not \r\n", "every element of the group has a natural representation. On the other hand, Mathematica's algorithm hinges on being able to repeatedly make the replacements set \r\n", "up in the Define commands until no more replacements are possible. So Mathematica would try to simplify
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "y^2*x" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "by blindly making the following substitutions:\r\n", "

y·y·x → y·x·x·y·y \r\n", "→ x·x·y·y·x·y·y → \r\n", "x·x·y·x·x·y·y·y·y →\r\n", "x·x·x·x·y·y·x·y·y·y·y → ⋯

\r\n", "creating longer and longer expressions and never stopping. The result is that Mathematica will go into an "infinite loop." The problem is not that \r\n", "the group does not exist; in fact Sage was able to find a group of order 24 for which there are elements x and y such \r\n", "that x³ = e, y⁶ = e, and y·x = x²·y². (See Problem 14.) The \r\n", "above infinite loop stems from trying to define this group in terms of subgroups that are not normal subgroups.

\r\n", "\r\n", "How can we be assured that this will not happen? The following proposition shows that if we use the polycyclic series and the definitions described \r\n", "above, Mathematica will always be able to simplify any combination of generators to a point where no further reductions are possible. In \r\n", "short, Mathematica will always return with the correct element of the group. Note that the following proposition is not in the textbook, since it \r\n", "mainly applies to Mathematica.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 8.4
\r\n", "Let G be a finite solvable group, and let\r\n", "

G = G₀ ⊇ G₁ ⊇ G₂ ⊇ \r\n", "⋯ ⊇ G_n = {e}

\r\n", "be a polycyclic series for G. If the group is defined in Mathematica or Sage using n generators and the procedure described above, \r\n", "then Mathematica will simplify any combination of generators to a point where no further reductions are possible.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "This proof is a bit longer and more technical than most of the proofs that we have seen. Yet because this result is the foundation that allows this set of notebooks to \r\n", "exist, it is included. It gives a good example of how the tools that we have learned throughout the course, such as induction and reductio ad absurdum, can be \r\n", "applied consecutively to solve harder problems.

\r\n", "\r\n", "We will close this sequence of notebooks by returning to a problem introduced in §2.3—the Rubik's Pyramix™. The understanding that we have learned \r\n", "since Chapter 2 can be applied to help us to solve the puzzle. The techniques that we will show could be applied to any of the Rubik's puzzles.

\r\n", "\r\n", "\r\n", "

Solving the Pyraminx™

\r\n", "\r\n", "
\r\n", "In section 2.3, we introduced a very large group called the Pyraminx™ group. This was the group of all permutations of the faces of the Pyraminx™ puzzle \r\n", "obtained by rotating the four corners. The Pyraminx™ puzzle is shown by executing the following command.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitPuzzle()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This group was described by four generators, r, l, b, and f. These four elements represent the 120° clockwise rotation of the \r\n", "right, left, back, and front corners respectively. Recall that we could perform multiple operations in Mathematica using the command RotatePuzzle. Thus, the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotatePuzzle(r, l)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "first rotates the right corner, and then the left corner. We can reset the puzzle with the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitPuzzle()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "What we want to do in this section is to study this group using the tools that we have learned throughout the course. From the result of this study we will be able to \r\n", "learn enough to solve the puzzle. The techniques used in this section can not only be used on other Rubik's puzzles, but on many other puzzles that are marketed \r\n", "today.

\r\n", "\r\n", "Because this group is so large, (933,120 elements), we will not be able to have Sage list all of the elements as we have done for the other groups we have \r\n", "studied. However, we will still be able to gleam information about the group by studying the puzzle.

\r\n", "\r\n", "We will begin by asking whether the group has a nontrivial center. That is, are there any elements which commute with all other elements? In terms of the puzzle, we \r\n", "are asking whether there are any sequence of moves such that the sequence, when performed in conjunction with any other sequence of moves, yields the same effect \r\n", "regardless of the order these two sequences of moves are performed.

\r\n", "\r\n", "To answer this question, we notice that the four corner pieces, although they can rotate, will never move about in the puzzle. Suppose that a sequence of moves rotates \r\n", "one of these corner pieces, returning all other pieces to their original positions. The result would look like the following:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "PuzzlePosition1()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "If another sequence of moves was performed on this position rather than the starting position, the only difference would be that the front corner would be turned \r\n", "another 120° clockwise. Thus, the action of rotating one corner 120° commutes with all other actions taken on the puzzle. So this action would be in the center \r\n", "of the group.

\r\n", "\r\n", "What sequence of moves produces this action? With a little bit of experimenting, we find one set of moves that work:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitPuzzle()\r\n", "RotatePuzzle(f,r,f,r,r,f,r,f,r,r)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "There are many other sequences of moves that work, all of them are at least as long. We will later show how Sage came up with this combination.

\r\n", "\r\n", "Note that Sage has a nice animation feature for repeated rotations. This element obviously has order 3. In fact, we could consider rotating one of the other \r\n", "three corners as well. Since the four corners act independently, we would have 3·3·3·3 = 81 elements in the center of the group. Let us call \r\n", "this subgroup K.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Using the above sequence as a model, can you find sequences of moves which rotate the other 3 corners?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Are there elements in the center besides those in K? Actually, there are. Suppose there was a sequence of moves that produced the following pattern:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "PuzzlePosition2()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that in this position all corner pieces are in their proper place. The edge pieces are also in the right position, but they are all reversed. So such a sequence \r\n", "of moves would effectively reverse all six of the edges. If another sequence of moves was performed on this position rather than the starting position, the difference \r\n", "in the end positions would be that all six edges would be reversed. Thus, the action of reversing all six of the edges will commute with all other actions taken on \r\n", "the puzzle. Therefore, the action of reversing all six edges would also be in the center of the group.

\r\n", "\r\n", "What sequence of moves reverses all six edges? The shortest solution is as follows, which happens to be easy to remember.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitPuzzle()\r\n", "RotatePuzzle(l,l,b,f,l,l,b,f,l,l,b,f)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This action obviously has order 2, and so this action is different from the other elements of K.

\r\n", "\r\n", "Are there any other actions that would be in the center of the group? Could there be an element of the center that moves an edge piece from location A to a \r\n", "new location B? Such an element would not commute with an action that reverses location A but leaves location B alone. So all elements of \r\n", "the center must fix the edge pieces.

\r\n", "\r\n", "What if an element of the center reversed one of the edges at location A, but not all of them? Say that it left the edge at location B fixed. This \r\n", "element would not commute with an action that sent the edge at location A to location B. So an element from the center of the group must either \r\n", "reverse all six edges, or none at all.

\r\n", "\r\n", "Thus, there are at most 2·3·3·3·3 = 162 elements in the center of the group, and we have discovered the generators which lead to a group \r\n", "of this size. Thus, the center of the Pyramix™ group is isomorphic to \r\n", "

Z₂ × Z₃ × Z₃ × Z₃ × \r\n", "Z₃.

\r\n", "The center of the group is certainly a normal subgroup, and includes all actions that return the edges to their original positions. What if we considered the set of \r\n", "actions that return all of the corners to their original place? This certainly would be a subgroup, which we will call E. Let us show that E is \r\n", "a normal subgroup of the Pyramix™ group. If x is an element of E, and y is a general element, say y rotates the front \r\n", "corner n degrees. Then y·x·y^-1 rotates the front corner n + 0 + (−n) = 0 \r\n", "degrees. So the front corner returns to its original position. The same is true for the other 3 corners, and \r\n", "so y·x·y^-1 fixes all 4 corners. Thus, E is a normal subgroup.

\r\n", "\r\n", "What is the intersection of E and K? Such an element in the intersection would have to leave both the edges and the corners fixed, and hence would have \r\n", "to be the identity element. Since both E and K are normal (since K is in the center), by the direct product \r\n", "theorem, E·K is isomorphic to E×K. Yet any action on the Pyramix™ can be performed by first moving \r\n", "all of the edge pieces, and then moving all of the corners. Thus, the entire group is in E·K, and so the Pyramix™ group is isomorphic to\r\n", "

E × K ≈ E × Z₃ × Z₃ × \r\n", "Z₃ × Z₃.

\r\n", "Therefore, if we can find the structure of the subgroup E, we will have found the structure of the entire Pyramix™ group.

\r\n", "\r\n", "This breakdown of the structure of the Pyramix™ group gives us a way the solve the puzzle. Suppose that we first ignore the corners of the puzzle and manage \r\n", "to get all 6 edge pieces in place. Then by using the routine\r\n", "

f·r·f·r·r·f·r·f·r·r

\r\n", "we could rotate the front corner until it was in position. We could then do the same for the other three corners, and the puzzle would be solved.

\r\n", "\r\n", "So how do we put the edge pieces in place? This amounts to analyzing the subgroup E. In order to ignore the corner pieces it is helpful to have Sage \r\n", "erase the corners with the following command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HideCorners()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This looks like a much easier puzzle to solve! We can rotate the puzzle without the corners just as before:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotatePuzzle(f)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Try changing the "f" in the above command to one of the other possible rotations and re-evaluate the expression. Since there are only twelve triangles in \r\n", "the puzzle now, it is clear that each action could be described as a permutation of the 12 triangles. In fact, notice that turning one corner 120° moves 6 \r\n", "triangles. If we follow carefully where the triangles go, we find that three of the triangles change places with each other, and the other three also rotate \r\n", "places. Thus, each turn produces an even permutation of the 12 triangles. So E is a subgroup of A₁₂.

\r\n", "\r\n", "Let us now try to find a normal subgroup of E. We know that the center of E is the identity together with the element that reverses all six \r\n", "edges. What if we considered the subgroup of actions which returns the edge pieces to their place, but may reverse some of them? Let us call this \r\n", "subgroup H. Is H a normal subgroup of E? If x be an element of H, and y an element of E, then the \r\n", "action y may move an edge piece from position A to position B. The action x will keep the edge piece at position B, whether \r\n", "or not it is reversed. Then y^-1 will send the edge piece back to \r\n", "position A. So y·x·y^-1 leaves the edge piece at position A fixed, even though it may be \r\n", "reversed. The same will be true for all of the edge pieces, and therefore H will be a normal subgroup of E.

\r\n", "\r\n", "Let us determine the structure of H. At first one might think that each edge piece may be reversed independently of all of the others, but this is \r\n", "not true. An action which reverses only one edge piece, leaving all other edge pieces in place, would be an odd permutation of the triangles! We \r\n", "already observed that E was a subgroup of even permutations. So every element of H must reverse an even number of edge pieces.

\r\n", "\r\n", "Is there an element of H that reverses only 2 edges? Yes, and in fact the following command gives an animation of a sequence of moves producing such an \r\n", "element.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitPuzzle()\r\n", "RotatePuzzle(l,f,l,b,l,b,f,b,f)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Since we can reverse the two front edge pieces, we can reverse any two edge pieces which are touching using a similar sequence of moves. In this way we can reverse \r\n", "any combination of edges as long as the number of edges reversed is even.

\r\n", "\r\n", "How many elements of H will there be? If we had considered the edge pieces to be reversed independently, there would have \r\n", "been 2·2·2·2·2·2 = 64 elements. Of these 64 possibilities, half of them reverse an even number of edges . Therefore there are 32 \r\n", "elements of H. Note that every element of H besides the identity is of order 2. Also, H is an abelian group. By the fundamental theorem \r\n", "of abelian groups every finite abelian group has a unique representation as the direct product of cyclic groups whose order is a power of a prime. Thus, the only \r\n", "such representation of H would be \r\n", "

\r\n", "H ≈ Z₂ × Z₂ × Z₂ × Z₂ × Z₂.

\r\n", "Now that we know the structure of the normal group H, can we find the structure of the quotient group? First, suppose we made the corners disappear on our \r\n", "puzzle again.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HideCorners()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The quotient group can now be realized by ignoring whether the edge pieces are reversed or not. That is, we will concern ourselves only with the position of the six \r\n", "edge pieces. Certainly this would be a subgroup of the permutations of the six edges. Notice that when we rotate one of the corners,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotatePuzzle(f)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "exactly three of the edge pieces move. Thus, this is an even permutation of the six edge pieces. Since E/H is generated by even \r\n", "permutations, E/H must be isomorphic to a subgroup of A₆.

\r\n", "\r\n", "Using the following reasoning we can see that E/H is isomorphic to all of A₆. We can clearly manipulate the puzzle to put any of \r\n", "the six edge pieces on the bottom. We can then, by rotating just the front and back corners, put any of the remaining five edge pieces on the far left. We then can put \r\n", "any of the four remaining edge pieces into the far right position as follows: If the piece is not already in position, rotate the front corner until it is in the \r\n", "top position. Then the sequence\r\n", "

f·b·f·f·b·b

\r\n", "puts the top edge piece into the far right position. Finally, we rotate the front corner to place any of the remaining three edge pieces into the top \r\n", "position. Therefore, there are at least 6·5·4·3 = 360 elements of E/H, so\r\n", "

E/H ≈ A₆.

\r\n", "\r\n", "This raises a natural question. Is E isomorphic to a semi-direct product of H by A₆? To see that it is, we need to find a copy \r\n", "of A₆ inside of E which contains no elements of H besides the identity. That is, we need to find a subgroup Y of actions \r\n", "which will allow us to rearrange the six edge pieces into any even permutation, but which will not allow us to reverse an edge piece. Notice that when we were showing \r\n", "that we could move four of the six pieces to prescribed positions, we only rotated the front and back corners, except in placing the bottom edge piece. That is, once \r\n", "the bottom piece was in place, the other five could be put into any even permutation using only the moves f and b. However, there is no way to reverse \r\n", "one of the edge pieces using only these two commands. It is not hard to find a third sequence of moves that changes the bottom edge without reversing any of \r\n", "them. The sequence r·f·f·r·r·f gives one example. Try this yourself.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotatePuzzle(r,f,f,r,r,f)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This moves a new edge piece to the bottom, yet there is no way to reverse an edge piece using any combination of this sequence and rotating the front and back \r\n", "corners. Thus, the group generated by\r\n", "

M = [ f, b, r·f·f·r·r·f ]

\r\n", "gives us a group isomorphic to A₆. Since it is impossible to reverse any edges with the elements of M, the intersection \r\n", "of M and H is the identity. Every arrangement of the edges can be obtained by first putting all of the edges into position, and then reversing \r\n", "several edges. Thus, E = M·H. Therefore by the semi-direct product theorem (6.3), E is isomorphic to a semi-direct product \r\n", "of H by K. If we let ϕ represent the homomorphism from K to Aut(H), we have that\r\n", "

E ≈ (Z₂ × Z₂ × \r\n", "Z₂ × Z₂ × Z₂) ⋊_ϕ A₆.

\r\n", "\r\n", "\r\n", "Unfortunately, this representation of E depends on the homomorphism ϕ from A₆ to \r\n", "Aut(Z₂ × Z₂ × Z₂ × Z₂ × Z₂). Let us try to \r\n", "find a representation of E that does not require additional knowledge. So instead, we will express E in terms of the wreath product.

\r\n", "\r\n", "DEFINITION 8.9
\r\n", "Let G be a group, and H a subgroup of S_n. We define the wreath product \r\n", "

G Wr H

\r\n", "as the semi-direct product Gⁿ ⋊_ϕ H, where Gⁿ denotes the direct product of G with itself n times, and for σ ∈ H, we define ψ_σ : Gⁿ → Gⁿ by\r\n", "

ψ_σ(g₁, g₂, …, g_n) = \r\n", "(g_σ₋₁₍₁₎, g_σ₋₁₍₂₎, … g_σ₋₁_(n)).

\r\n", "We explored the wreath product in Problems 13 through 16 of §6.4. In these problems, we demonstrated that ψ is a homomorphism \r\n", "from H to Aut(Gⁿ), so the wreath product is a group of size |G|ⁿ·|H|.

\r\n", "\r\n", "Consider the wreath product Z₂ Wr A₆. This would be a semi-direct product \r\n", "

(Z₂ × Z₂ × Z₂ × \r\n", "Z₂ × Z₂ × Z₂) ⋊_ϕ A₆,

\r\n", "which is similar to, but twice as large, as E. In fact, it is not too hard to see the correlation. If we considered the 6 edges of the puzzle being able to be flipped independently, then the group of all edge flips would be (Z₂)⁶. But then we can permute the edges with any even permutation. The wreath product combines the actions of the edge permutations with the edge flips. Thus, E is isomorphic to a subgroup of Z₂ Wr A₆. In \r\n", "fact, it is a normal subgroup, since it contains half of the elements.

\r\n", "\r\n", "How can we specify this subgroup? Consider the derived subgroup of Z₂ Wr A₆. This subgroup is generated by elements of the form \r\n", "x^-1·y^-1·x·y, which clearly would flip an even number of edges. There is a natural subgroup \r\n", "of Z₂ Wr A₆ which is isomorphic to A₆, and since (A₆)′ = A₆, this \r\n", "subgroup would be in the derived subgroup. Also, if x flips two of the six edges, and y permutes three edges without flipping any, moving only one of the two edges flipped by x, then x^-1·y^-1·x·y will flip two edges, returning them to there \r\n", "original position. Thus, we see that E ≈ (Z₂ Wr A₆)′, and hence the Pyraminx group is isomorphic to \r\n", "

(Z₂ Wr A₆)′ × Z₃ × Z₃ × Z₃ × Z₃.

\r\n", "We can use Sage to analyze this group, by analyzing (Z₂ Wr A₆)′. First we consider the subgroup H, which is the subgroup of flipping an even number of edges. We can represent the edges by disjoint transpositions." ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "H = Group( C(1,2)*C(3,4), C(3,4)*C(5,6), C(5,6)*C(7,8), C(7,8)*C(9,10), C(9,10)*C(11,12) )" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(H)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "Next, we consider the subgroup generated of even permutations of the cycles, without flipping them. This subgroup is generated by a three cycle and five cycle of edges." ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "M = Group( C(1,3,5)*C(2,4,6), C(3,5,7,9,11)*C(4,6,8,10,12) )" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(M)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "We now can combine this subgroups, to form the whole group." ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = H * M" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "This group is far too large to display, even with integer representation. However, we can determine how many elements there are of a given order, by computing \r\n", "R_k(G) for various k.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RootCount(G, 2)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RootCount(G, 3)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RootCount(G, 4)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RootCount(G, 5)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RootCount(G, 6)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RootCount(G, 8)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RootCount(G, 10)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This shows the group has 391 elements of order 2. From this information, we can find the number of elements of any given order, \r\n", "summarized in the following table.

\r\n", "\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

1	element of order 1,
391	elements of order 2,
800	elements of order 3,
2520	elements of order 4,
2304	elements of order 5,
1760	elements of order 6,
1440	elements of order 8,
2304	elements of order 10,

11520	elements total.

\r\n", "\r\n", "
\r\n", "This table, along with the fact that the Pyraminx group is \r\n", "

(Z₂ Wr A₆)′ × Z₃ × Z₃ × Z₃ × Z₃.

\r\n", "allows us to analyze the Pyraminx group.

\r\n", "\r\n", "\r\n", "\r\n", "Knowing the structure of the group allows us the solve the puzzle! Here is the strategy based on this decomposition of the group.

\r\n", "\r\n", "1) First put all of the edge pieces in place. We can begin with the bottom, then rotate the front and back corners until the back two edges are in the right \r\n", "place (they may be reversed). Finally, rotate the front corner until all six edges are in place.

\r\n", "\r\n", "2) At this point, an even number of edges will be reversed. We can find routines that will flip two, four, or six of the edges. These may rotate corners in \r\n", "the process.

\r\n", "\r\n", "3) Now only the four corner pieces are out of position. We can find rotations to rotate these into position.

\r\n", "\r\n", "To find a combination of the four moves f, b, r, and l that will accomplish these goals, we can have Sage help us. First we\r\n", "number the 24 triangles, as shown in the textbook. Since we consider the product of several rotations to be done from left to right, we need to convert the rotations to permutations the way that we converted book rearrangements. That is, for each number, we consider what new number will be in that position after the rotation. Thus, the permutation (4 14 23)(5 15 24)(6 16 19) can represent r, while \r\n", "

l = (8 21 16)(9 22 17)(10 23 18) f = (1 7 13)(2 8 14)(6 12 18) and b = \r\n", "(2 19 10)(3 20 11)(4 21 12).

\r\n", "\r\n", "We can enter these into Sage.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "r = C(4, 14, 23)*C(5, 15, 24)*C(6, 16, 19)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "l = C(8, 21, 16)*C(9, 22, 17)*C(10, 23, 18)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "f = C(1, 7, 13)*C(2, 8, 14)*C(6, 12, 18)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "b = C(2, 19, 10)*C(3, 20, 11)*C(4, 21, 12)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Now that these rotations are entered into Sage as permutations, the natural question is how to express any given permutation in the group generated by these elements\r\n", "in terms of f, b, r and l in the most efficient way. For example, suppose we want to find an efficient way to rotate just the right \r\n", "corner piece clockwise, that is the permutation (5 15 24). Sage can do this with the ExpressAsWord command.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "ExpressAsWord([\"r\", \"l\", \"f\", \"b\"], C(5, 15, 24) )" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This returns a string that describes one of the fastest ways to reach the target permutation from the permutations given. If we evaluate the contents of the string,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "r*b*r^-2*b^-1*r*b*r*b^-1" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we see that indeed this gives us the permutation that we are looking for. Notice that the first argument in ExpressAsWord is a list of strings \r\n", "that represent the generating permutations, whose variables have been previously set up. Note that ExpressAsWord is not guaranteed to produce \r\n", "the shortest solution, merely the first solution it finds. Rearranging the generating permutations may give a different solution.

\r\n", "\r\n", "Let us find combinations that will flip two or more edge pieces. Following the strategy above, we have the advantage that we do not care if the corners are \r\n", "rotated in the process. So we can enter versions of r, l, f, and b that ignore the corner pieces.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "r = C(4, 14, 23)*C(6, 16, 19)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "l = C(8, 21, 16)*C(10, 23, 18)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "f = C(2, 8, 14)*C(6, 12, 18)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "b = C(2, 19, 10)*C(4, 21, 12)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "By ignoring corners, we reduce the number of puzzle positions down to 11520, so it should be easy to find combinations that produce the right \r\n", "flips. For example, to flip the top and front left edges, we need the permutation (2 12)(8 18).
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "ExpressAsWord([\"r\", \"l\", \"f\", \"b\"], C(2,12)*C(8,18) )" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can check that this works.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "r*l^-1*b^-1*l*r^-1*f^-1" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", "Flipping the left rear and front right edges requires the permutation (6 14)(10 21). Find a combination of r, l, f and b that produce\r\n", "this permutation.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can use this technique to determine routines for flipping any combination of edges:

\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

l^-1·b·f·l^-1·b·f·l^-1·b·f	flip all six edges
f·b·r^-1·l·r·b^-1	flip two front edges
b·l·b·r·l·r^-1·l^-1·b	flip top & bottom edges
f·r·l^-1·b·l·r^-1	flip top & front left edges
r·l^-1·b·l·r^-1·f	flip top & front right edges
r·b·r·l·b·l^-1·b^-1·r	flip left rear and front right edges
l·r·l·b·r·b^-1·r^-1·l	flip right rear and front left edges
r·b·l^-1·f·l·b^-1	flip bottom & front right edges
l·b·f^-1·r·f·b^-1	flip bottom & front left edges
b·r·f^-1·l·f·r^-1	flip top & left rear edges
b·l·r^-1·f·r·l^-1	flip top & right rear edges
b·f·l^-1·r·l·f^-1	flip rear two edges
l·f·r^-1·b·r·f^-1	flip bottom & left rear edges
r·f·b^-1·l·b·f^-1	flip bottom & right rear edges
l·r·b^-1·f·b·r^-1	flip two left hand edges
r·l·f^-1·b·f·l^-1	flip two right hand edges

\r\n", "\r\n", "
\r\n", "Finally, we found a sequence of moves that rotates the right corner, and leaves the rest of the puzzle intact. From this sequence, we can learn how to rotate any \r\n", "corner into position:

\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", "

f·r·f·r^-1·f·r·f·r^-1	rotate front corner 120° clockwise
l·r·l·r^-1·l·r·l·r^-1	rotate left corner 120° clockwise
r·b·r·b^-1·r·b·r·b^-1	rotate right corner 120° clockwise
b·r·b·r^-1·b·r·b·r^-1	rotate back corner 120° clockwise

\r\n", "\r\n", "
\r\n", "By applying these four routines once or twice, we can get all four corners into position, and solve the puzzle!

\r\n", "\r\n", "Notice that our three steps can be expressed in terms of a subnormal series for the Pyraminx™ group:\r\n", "

((Z₂ Wr A₆)′ × Z₃ × \r\n", "Z₃ × Z₃ × Z₃) ⊃ (Z₂ × Z₂ × \r\n", "Z₂ × Z₂ × Z₂ × Z₃ × Z₃ × \r\n", "Z₃ × Z₃) ⊃ (Z₃ × Z₃ × \r\n", "Z₃ × Z₃) ⊃ {e}.

\r\n", "This is not a composition series, but it is easy to see how the series can be expanded to make a composition series. Notice that our first step in solving the puzzle \r\n", "rids us of the A₆ factor, bringing the puzzle to a combination that is in a abelian subgroup. The second step in solving the puzzle corresponds \r\n", "to bringing the puzzle into a combination which is within the subgroup Z₃ × Z₃ × \r\n", "Z₃ × Z₃. The third step used four phases for the four corners to bring the puzzle to the identity element, the solved \r\n", "puzzle.

\r\n", "\r\n", "Since one of the factors in this composition series is the simple group A₆, the Pyraminx™ group is not a solvable group. This is not to say \r\n", "that the puzzle is not solvable, but rather that we cannot enter this group into Sage using the InitGroup and Define \r\n", "commands. Not that we would want to anyway, since this group has\r\n", "

360·2·2·2·2·2·3·3·3·3 = 933,120 elements.

\r\n", "
\r\n", "\r\n", "This same type of analysis can be used to solve other puzzles, such as the Rubik's Cube^©. Several problems in the homework relate to this \r\n", "puzzle. Thus, we can see a practical application of the properties of groups that we have studied throughout the course.

\r\n", "\r\n", "But not all applications of groups are fun and games. Group theory has also become the backbone of modern mathematics and many important proofs, such as the \r\n", "impossibility of finding solutions to fifth degree polynomials, hinge entirely on finite groups. The theory of finite groups also has applications in quantum \r\n", "physics and inorganic chemistry and crystallography. Therefore, the material presented in this course has many applications beyond mathematics.\r\n", "\r\n", "

\r\n", "\r\n", "

Proofs:

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 8.1:

\r\n", "\r\n", "Note that if there are no repeated subgroups in the subnormal series then each G_k−1/G_k must contain at least two \r\n", "elements. Likewise, if G_k−1/G_k is nontrivial, then G_k−1 is not equal \r\n", "to G_k. So the quotient groups are nontrivial if, and only if, there are no repeated subgroups in the subnormal series.
\r\n", "
\r\n", "\r\n", "Suppose that the subnormal series is not a composition series yet does not repeat any subgroups. Then there must be an additional group H that we can add \r\n", "between G_k−1 and G_k, so that\r\n", "

G_k−1 ⊇ H ⊇ G_k,

\r\n", "where H is a normal subgroup of G_k−1 and G_k is a normal subgroup of H. Then by \r\n", "Lemma 4.5, H/G_k will be a normal subgroup of G_k−1/G_k, and since H is \r\n", "neither G_k−1 nor G_k, we have a proper normal \r\n", "subgroup of G_k−1/G_k.

\r\n", "\r\n", "Now suppose that there is a proper normal subgroup N of G_k−1/G_k. Can we then lift N to find \r\n", "a suitable subgroup H to fit between G_k−1 and G_k? If we consider the canonical \r\n", "homomorphism ϕ from G_k−1 to the quotient group G_k−1/G_k, we can \r\n", "take H = ϕ^-1(N). Then since N is a normal subgroup \r\n", "of G_k−1/G_k, by Corollary 4.2 H will be a normal subgroup \r\n", "of G_k−1. Also, G_k will be a normal subgroup of H, for H is \r\n", "in G_k−1. Because N has at least two elements, H will be strictly larger than the kernel of ϕ, yet \r\n", "since N is not the entire image of ϕ, H will be strictly smaller than G_k−1. Therefore, the \r\n", "subnormal series is not a composition series.

\r\n", "\r\n", "Thus, a subnormal series is a composition series if, and only if, the quotient groups G_k−1/G_k are nontrivial \r\n", "simple groups.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Lemma 8.1:

\r\n", "\r\n", "Note that (X ∩ Z) ⊆ X, and since Y ⊆ X, Y·(X ∩ Z) ⊆ \r\n", "X. Also, (X ∩ Z) ⊆ Z, so Y·(X ∩ Z) ⊆ \r\n", "Y·Z. Hence,\r\n", "

Y·(X ∩ Z) ⊆ X ∩ (Y·Z).

\r\n", "All we need to do is prove the inclusion in the other direction. Suppose that x ∈ X ∩(Y·Z). Then x is \r\n", "in X, and can also be written as x = y·z, where y is in Y, and z is in Z. But \r\n", "then z = y^-1·x would be in both X and Z. Thus,\r\n", "

x = y·(y^-1·x) ∈ Y·(X ∩ Z).

\r\n", "Therefore, we have inclusions in both directions, so\r\n", "

Y·(X ∩ Z) = X ∩ (Y·Z).

\r\n", "So far, we haven't used the fact that Y·Z = Z·Y. By Lemma 4.2, Y·Z is a subgroup \r\n", "of G, and so the intersection of X with Y·Z is a subgroup of G. So by Lemma 4.2 again, we have\r\n", "

Y·(X ∩ Z) = (X ∩ Z)·Y.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Lemma 8.2:

\r\n", "\r\n", "Since Z is a normal subgroup of G, both Y·Z and X·Z are subgroups of G by Lemma 4.5. If we \r\n", "let y·z be in Y·Z, and x·w be in X·Z, then\r\n", "

(x·w)·(y·z)·(x·w)^-1 = \r\n", "x·(y·x^-1·x·y^-1)·w·y·z·w^-1·x^-1 = \r\n", "(x·y·x^-1)·(x·(y^-1·w·y)·z·w^-1·x^-1).

\r\n", "Now, x·y·x^-1 is in Y, since Y is a normal subgroup \r\n", "of X. Likewise, y^-1·w·y is in Z, since y is \r\n", "in G. Then (y^-1·w·y)·z·w^-1 is in Z, and \r\n", "so x·(y^-1·w·y)·z·w^-1·x^-1 is \r\n", "in Z, since x is \r\n", "in G. Therefore, \r\n", "

(x·w)·(y·z)·(x·w)^-1 ∈ \r\n", "Y·Z,

\r\n", "and so Y·Z is a normal subgroup of X·Z.

\r\n", "\r\n", "We now can use the second isomorphism theorem (4.2), using K = Y·Z. We have that X·K = \r\n", "X·Y·Z = X·Z, since Y is a subgroup of X. So\r\n", "

(X·Z)/(Y·Z) = (X·K)/K ≈ \r\n", "X/(X ∩ K) = X/(X ∩ (Y·Z)).

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Theorem 8.1:

\r\n", "\r\n", "We let \r\n", "

A_i,j = (A_i−1 ∩ \r\n", "B_j)·A_i and B_j,i = (B_j−1 ∩ \r\n", "A_i)·B_j.

\r\n", "To see that these fit the conditions we need, we first want to show that these are groups. Note that both\r\n", "

X = (A_i−1 ∩ B_j−1) and Y \r\n", "= (A_i−1 ∩ B_j)

\r\n", "are subgroups of A_i−1, Y is a subgroup of X, and Z = A_i is a normal subgroup \r\n", "of A_i−1.

\r\n", "\r\n", "So by Lemma 4.3, both A_i,j−1 = X·Z and A_i,j = \r\n", "Y·Z are subgroups of A_i−1. We can now use Lemma 8.2, \r\n", "using G = A_i−1. Since B_j is a normal subgroup of B_j−1, Y is \r\n", "a normal subgroup of X, so by Lemma 8.2, Y·Z is a normal subgroup of X·Z, and\r\n", "

A_i,j−1/A_i,j = \r\n", "(X·Z)/(Y·Z) ≈ X/(X ∩ (Y·Z)).

\r\n", "Now Lemma 8.1 comes into use. Since Y is a subgroup of X,\r\n", "

X ∩ (Y·Z) = Y·(X ∩ Z) = \r\n", "(A_i−1 ∩ B_j)·(A_i−1 ∩ \r\n", "B_j−1 ∩ A_i) = \r\n", "(A_i−1 ∩ B_j)·(A_i ∩ B_j−1) = \r\n", "(A_i ∩ B_j−1)·(A_i−1 ∩ B_j).

\r\n", "Thus,\r\n", "

A_i,j−1/A_i,j ≈ \r\n", "(A_i−1 ∩ B_j−1)/[(A_i−1 ∩ \r\n", "B_j)·(A_i ∩ B_j−1)].

\r\n", "By switching the roles of the two series we find by the exact same argument that \r\n", "

B_j,i−1/B_j,i ≈ \r\n", "(B_j−1 ∩ A_i−1)/[(B_j−1 ∩ \r\n", "A_i)·(B_j ∩ A_i−1)].

\r\n", "Notice that these are exactly the same thing, so\r\n", "

A_i,j−1/A_i,j ≈ \r\n", "B_j,i−1/B_j,i.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Theorem 8.2:

\r\n", "\r\n", "By the refinement theorem (8.1), there is a refinement of both composition series such that the quotient groups of the two subnormal series are isomorphic to each other \r\n", "in some order. In particular, the nontrivial quotient groups of one subnormal series are isomorphic to the nontrivial quotient groups of the other. But these are \r\n", "composition series, so any refinements merely repeat a subgroup a number of times. Thus, by eliminating these repetitions, we eliminate the trivial quotient groups \r\n", "and produce the original two composition series. Thus, the quotient groups A_i−1/A_i are isomorphic to the \r\n", "quotient groups B_j−1/B_j in some order. The fact that n = m merely comes from the \r\n", "one-to-one correspondence of the nontrivial quotient groups.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 8.2:

\r\n", "\r\n", "Let u be an element of [H, K], and g an element of G. Then u = \r\n", "u₁·u₂ ⋯ u_n where either u_i or u_i^-1 is \r\n", "x_i^-1·y_i^-1·x_i·y_i, with \r\n", "x_i ∈ H and y_i ∈ K. Then \r\n", "

g·u·g^-1 = \r\n", "(g·u₁·g^-1)·(g·u₂·g^-1) ⋯ \r\n", "(g·u_n·g^-1),

\r\n", "and\r\n", "

g·x_i^-1·y_i^-1·x_i·y_i·g^-1 = \r\n", "(g·x_i^-1·g^-1)·(g·y_i^-1·g^-1)·(g·x_i·g^-1)·(g·y_i·g^-1) = \r\n", "[ g·x_i·g^-1, g·y_i·g^-1 ].

\r\n", "If H and K are both normal subgroups of G, then g·x_i·g^-1 is in H, and \r\n", "g·y_i·g^-1 is in K. Thus, \r\n", "[ g·x_i·g^-1, g·y_i·g^-1 ] is \r\n", "in [H, K].

\r\n", "\r\n", "Since (g·u_i·g^-1)^-1 = \r\n", "(g·u_i^-1·g^-1), if one of these is in [H, K], they both \r\n", "are. Hence, g·u_i·g^-1 is in [H, K] for every u_i, \r\n", "and g·u·g^-1 ∈ [H, K]. By Proposition 3.4, [H, K] is a \r\n", "normal subgroup of G.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Lemma 8.3:

\r\n", "\r\n", "First we need to show that G/G′ is abelian. Consider the canonical homomorphism ϕ from G \r\n", "onto G/G′. Then for x and y in G, \r\n", "x^-1·y^-1·x·y is in G′, and \r\n", "so ϕ(x^-1·y^-1·x·y) is the identity element \r\n", "in G/G′. But then\r\n", "

ϕ(x^-1·y^-1·x·y) = \r\n", "ϕ(x)^-1·ϕ(y)^-1·ϕ(x)·ϕ(y) = \r\n", "e.

\r\n", "so ϕ(x)·ϕ(y) = ϕ(y)·ϕ(x). Since ϕ is surjective, \r\n", "we see that G/G′ is abelian.

\r\n", "\r\n", "Now suppose that N is another normal subgroup of G for which G/N is abelian. To show that G′ is a smaller \r\n", "group, we will show that N contains G′.

\r\n", "\r\n", "For any x and y in G, note that x^-1·y^-1·x·y is certainly \r\n", "contained in \r\n", "x^-1·N·y^-1·N·x·N·y·N. But \r\n", "since the quotient group G/N is abelian, we have\r\n", "

\r\n", "x^-1·N·y^-1·N·x·N·y·N = \r\n", "x^-1·N·x·N·y^-1·N·y·N =\r\n", "N·N = N.

\r\n", "Thus, x^-1·y^-1·x·y is in N for all x and y in G. Since \r\n", "G′ is generated by all such elements, G′ is contained in N.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Theorem 8.3:

\r\n", "\r\n", "Suppose that the composition factors of G are all cyclic groups of prime order. Then there exists a composition series for G:\r\n", "

G = G₀ ⊃ G₁ ⊃ G₁ ⊃ \r\n", "⋯ ⊃ G_n = {e}.

\r\n", "Since G₀/G₁ is an abelian group, we have from Lemma 8.3 that G′ is contained in G₁. But \r\n", "since G₁/G₂ is also abelian, by Lemma 8.2 we have G₁′ is in G₂, and so\r\n", "

G′′ ⊆ G₁′ ⊆ G₂.

\r\n", "Proceeding in this way we find that the n^th derived group, G⁽ⁿ⁾, must be contained in G_n = {e}. Thus, \r\n", "the derived series produced the trivial group in at most n steps, so G is solvable.

\r\n", "\r\n", "Now suppose that G is solvable and finite, and so the derived series can be written\r\n", "

G ⊇ G′ ⊇ G′′ ⊇ G′′′ ⊇ ⋯ \r\n", "⊇ G⁽ⁿ⁾ = {e}.

\r\n", "If G⁽ⁿ⁾ is the first term in the derived series equal to {e}, then this subnormal series can never repeat any two \r\n", "subgroups. Because this is a finite group, there are only a finite number of ways this series could be refined without repeating subgroups. Thus, by the refinement \r\n", "theorem, we can refine this to produce a composition series. Because each of the quotient groups of the derived series is abelian, the quotient groups of the refinement \r\n", "must also be abelian. But by Proposition 8.1, the quotient groups of the composition series must be nontrivial simple groups. The only nontrivial simple groups that \r\n", "are abelian are the cyclic groups of prime order. Thus, the quotient groups for this composition series are cyclic groups of prime order. By the Jordan-Hölder \r\n", "theorem (8.2), all composition series are the same way.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Lemma 8.4:

\r\n", "\r\n", "We first note that since N is a normal subgroup of G, H·N is a subgroup of G, and so N is a normal subgroup of H·N. Two typical elements of H·N/N are h·n·N and \r\n", "k·m·N, where h and k are in H, and n and m are in N. Then \r\n", "(H·N/N)′ is generated from the elements of the form\r\n", "

(h·n·N)^-1·(k·m·N)^-1·(h·n·N)·(k·m·N) = \r\n", "h^-1·k^-1·h·k·N.

\r\n", "But these elements are also in (H′·N)/N. In fact, (H′·N)/N is generated by the elements \r\n", "of the form h^-1·k^-1·h·k·N. Therefore, the \r\n", "groups (H·N/N)′ and (H′·N)/N are equal.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 8.3:

\r\n", "\r\n", "We begin by showing that if G is solvable, and H is a subgroup of G, normal or not, then H is solvable. Since H is contained \r\n", "in G, we have\r\n", "

H′ ⊆ G′ ⟹ H′′ ⊆ \r\n", "G′′ ⟹ H′′′ ⊆ G′′′ ⋯.

\r\n", "Thus, since G⁽ⁿ⁾ = {e} for some n, H⁽ⁿ⁾ = {e}, and H is solvable.

\r\n", "\r\n", "Next we want to show that if H is normal, then G/H is solvable. Since G = G·H we can use Lemma 8.4 to \r\n", "find (G/H)′ = (G′·H)/H. But since G′ is a subgroup, we can continue to use Lemma 8.4 to \r\n", "find\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

(G/H)′′	=	(G′·H/H)′ = (G′′·H)/H,
(G/H)′′′	=	(G′′·H/H)′ = (G′′′·H)/H, ….

\r\n", "\r\n", "
\r\n", "Since G is a solvable group, G⁽ⁿ⁾ = {e} for some n. Thus\r\n", "

(G/H)⁽ⁿ⁾ = (G⁽ⁿ⁾·H)/H

\r\n", "would be the identity group H/H. Therefore, G/H is a solvable group.

\r\n", "\r\n", "Now suppose that both H and G/H are solvable. Then (G/H)⁽ⁿ⁾ is the identity for some n, \r\n", "so (G⁽ⁿ⁾·H)/H is the identity. Thus, G⁽ⁿ⁾ is a subgroup of H, and since \r\n", "H is solvable, G⁽ⁿ⁾ must be solvable. Therefore, G^(n+m) is the identity for some m, \r\n", "and so G is a solvable group.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 8.4:

\r\n", "\r\n", "This is not really a proof about Mathematica, but about the structure of polycyclic groups. However, the proposition can best be stated in \r\n", "terms of how Mathematica handles the elements of the group.

\r\n", "\r\n", "First consider the case where n = 1. The group G is will then be a cyclic group, say of order m > 1. The \r\n", "only Define statement would replace g₁^m with e, so each substitution would reduce the number \r\n", "of g's in the expression, and hence would eventually come to the point where no more substitutions are possible.

\r\n", "\r\n", "We can now proceed by induction on the length of the polycyclic series of G. That is, we will assume that the proposition is true for all groups with \r\n", "shorter polycyclic series, in particular, G₁.

\r\n", "\r\n", "Since G₀/G₁ is cyclic, we will let u·G₁ be a generator, and \r\n", "let m = |G₀/G₁|. We will then let g₁ be one element \r\n", "from u·G₁. Since g₁^m is in G₁, by induction we can \r\n", "let g₁^m = b, where b is defined in terms of the \r\n", "generators {g₂, g₃, … g_n}. Also, \r\n", "g₁^-1·g_i·g₁ is in G₁ for each of these generators, and so we \r\n", "can define k_i = g₁^-1·g_i·g₁ for \r\n", "i = 2, 3, … n in terms of the generators {g₂, g₃, … g_n}. We then have \r\n", "the additional n Define commands:

\r\n", "\r\n", "Define(g₁^m, b)
\r\n", "\r\n", "Define(g₂*g₁, \r\n", "g₁*k₂)
\r\n", "\r\n", "Define(g₃*g₁, \r\n", "g₁*k₃)
\r\n", "\r\n", " ……………
\r\n", "\r\n", "Define(g_n*g₁, \r\n", "g₁*k_n)

\r\n", "\r\n", "We will call these n new Define commands "first category substitutions," and all previously defined definitions as "second \r\n", "category substitutions." Certainly these definitions are compatible with the group structure of G, so if we can simplify every combination to a unique \r\n", "form, this form will be the correct representation of the element.

\r\n", "\r\n", "The only thing that would go wrong is if there was some expression for which there existed an infinite sequence of substitutions from either category. Suppose that this \r\n", "was the case. That is, suppose that there is a infinite sequence of expressions\r\n", "

u₁, u₂, u₃, …

\r\n", "where each expression u_i is formed from a substitution of either of the two categories applied to u_i−1. Note that \r\n", "the u_i's do not represent elements of G, but rather expressions that are products of the \r\n", "generators {g₁, g₂, … g_n}. In fact, all of the u_i's are different ways of \r\n", "expressing the same element of G. If such an infinite sequence of expressions existed, the computer would have the potential of running into an infinite \r\n", "loop.

\r\n", "\r\n", "Let d represent the number of times that g₁ appears in the expression u₁. Note that if d = 0, then \r\n", "u₁ is expressed in terms of the generators {g₂, g₃, … g_n} of \r\n", "G₁. But by induction, G₁ does not form any such infinite sequences. Thus, we may assume that there is at least one occurrence \r\n", "of g₁ in the expression u₁. By the same argument, we can suppose that there is at least one occurrence \r\n", "of g₁ in all of the expressions u_i.

\r\n", "\r\n", "Consider the first appearance of the generator g₁ in each expression u_i. If we let v_i be the part of \r\n", "the expression occurring before this first g₁, and let w_i represent the part of the expression occurring after it, we can \r\n", "express u_i as v_i·g₁·w_i. Note that v_i and \r\n", "w_i may be empty expressions.

\r\n", "\r\n", "Since v₁ contains no g₁'s, it is in G₁ and so by our induction hypothesis, there is only a finite number \r\n", "of expressions that could be produced using substitutions from the second catagory. Let s denote the number of generators in the longest such \r\n", "expression.

\r\n", "\r\n", "We now will show, using induction on the number d, that an infinite sequence of substitutions is impossible. That is, we will assume that an expression with \r\n", "only d−1 occurrences of g₁ could not appear in an infinite loop. Note that we are already using an induction hypothesis, so this is \r\n", "an "induction inside of an induction." We will keep the two induction arguments straight by referring to them as the "inner induction" and \r\n", "the "outer induction."

\r\n", "\r\n", "Notice that the first substitution of the first category,

\r\n", "\r\n", "Define(g₁^m, b)

\r\n", "\r\n", "reduces the number of g₁'s by m. All other substitutions of the first category preserve the number of g₁'s while \r\n", "all substitutions of the second category do not affect any of the g₁'s. Thus, if g₁^m is ever replaced \r\n", "by b, the resulting expression would have only d−m occurrences of g₁, and by the inner induction hypothesis would \r\n", "not get into an infinite loop. Hence we can suppose that the number of g₁'s that appears in any of the expressions u_i is the \r\n", "same, which is d.

\r\n", "\r\n", "For each expression v_i·g₁·w_i, there are three types of substitutions that can be \r\n", "done:

\r\n", "\r\n", "1) A substitution of the second category applied to v_i.

\r\n", "\r\n", "2) A substitution of either category applied to w_i

\r\n", "\r\n", "3) A substitution of the first category applied to the last generator of v_i and the first occurrence of g₁. The \r\n", "resulting v_i+1 will be shorter than v_i by one generator.

\r\n", "\r\n", "By the outer induction hypothesis, since v_i is in G₁, only a finite number of substitutions of the first type can be done before \r\n", "doing one of the third. Likewise, by the inside induction hypothesis, since w_i contains only (d−1) occurrences \r\n", "of g₁, only a finite number of substitutions of the second type can be done before performing one of type 3. But the size \r\n", "of v_i goes down by one each time the third type of substitution occurs, which could happen only s times. Thus, the computer will not go \r\n", "into an infinite loop when the generator g₁ appears d times. Thus, by the inner induction, the computer will not go into an infinite loop \r\n", "making substitutions on any combination of generators \r\n", "in {g₁, g₂, g₃, … g_n}.

\r\n", "\r\n", "We now can close the outer induction argument. Since we have shown that there cannot be an infinite number of substitutions on a combination of generators \r\n", "in G₀ provided that the same was true for G₁, and that G₀/G₁ was cyclic, we can see \r\n", "by induction that no such infinite number of substitutions is possible on the original group G.

\r\n", "\r\n", "Return to text

\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "

Sage Interactive Problems

\r\n", "\r\n", "
\r\n", "§8.1 #19)
\r\n", "Use Sage to find a composition series for the following group of order 20:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^5, e); Define(b^4, e); Define(b*a, a^2*b)\r\n", "M = ListGroup()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§8.1 #20)
\r\n", "Use Sage to find a composition series for the following group:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "DisplayPermInt = true\r\n", "G = Group(NthPerm(2374), NthPerm(6212)); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§8.2 #18)
\r\n", "Use Sage to find the derived group series of Q:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q = InitQuaternions(); Q" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Add any subgroups necessary to make this series a composition series.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§8.2 #19)
\r\n", "Use Sage's Commutator command as an altermative way to show that Aut(Z₂₄^*) is insoluble. Load this group \r\n", "with the commands
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "DisplayPermInt = true\r\n", "A = Group(NthPerm(187), NthPerm(723) )\r\n", "A" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "and find A′. Note that Sage can find the derived group fairly quickly.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§8.2 #20)
\r\n", "Find the derived group series of the following group:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "DisplayPermInt = true\r\n", "G = Group(NthPerm(2374), NthPerm(6212) ); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "What group is G′ isomorphic to? Is G a semi-direct product of two familiar groups?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§8.3 #16)
\r\n", "Redo Example 8.3 with the subgroup {1, j, −1, −j}. How does Sage rename the elements of the group?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§8.3 #17)
\r\n", "Use a polycyclic decompostion of A₄ to enter this group into Sage. Then use ToPolycyclic to convert the group \r\n", "to a polycyclic form.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§8.3 #18)
\r\n", "Find a polycyclic decomposition of group B of order 16, and use this to enter the group into Sage. Then use ToPolycyclic \r\n", "to convert the group to a polycyclic form.\r\n", "\r\n", "

The mystery group B:

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§8.3 #19)
\r\n", "Find a polycyclic decomposition of group C of order 16, and use this to enter the group into Sage. Then use ToPolycyclic to \r\n", "convert the group to a polycyclic form.\r\n", "\r\n", "

The mystery group C:

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§8.3 #20)
\r\n", "Find a polycyclic decomposition of group D of order 16, and use this to enter the group into
Sage. Then use ToPolycyclic to \r\n", "convert the group to a polycyclic form.\r\n", "\r\n", "

The mystery group D:

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§8.4 #18)
\r\n", "First show that S₇ is generated by the elements a = (2 6 3 7 4) and b = (1 5 4 2). Then use ExpressAsWord to \r\n", "find a way to express (1 2) in terms of a and b.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§8.4 #19)
\r\n", "First show that A₇ is generated by the elements a = (1 6 7)(2 5 4) and b = (1 3 7 2)(4 6). Then use ExpressAsWord to \r\n", "find a way to express (1 2 3) in terms of a and b.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§8.4 #20)
\r\n", "Consider the puzzle in Figure 8.5 in the book, with 7 disks on 2 wheels. The action L turns the left wheel 90° clockwise, taking the disks with it. The \r\n", "action R turns the right wheel 72° clockwise, again taking the disks with it. The goal is to swap disks 5 and 6, so the disks are in consecutive order.\r\n", "Use Sage's ExpressAsWord to solve this puzzle. A few brave souls might try to solve this puzzle without Sage's help.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\r\n", "\r\n", "\r\n", "\r\n", "" ] } ], "metadata": { "kernelspec": { "display_name": "SageMath (stable)", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.14" } }, "nbformat": 4, "nbformat_minor": 0 }