{ "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", "©2015 This notebook is provided with the textbook, "Abstract Algebra: An Interactive Approach, 2nd Ed." by William Paulsen. Users of this notebook are encouraged to buy the textbook.\n", "

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

\n", "Chapter 2
\n", "The Structure Within a Group\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", "Generators of Groups
\r\n", "Defining Finite Groups in Sage
\r\n", "Subgroups
\r\n", "Sage Interactive Problems
\r\n", "\r\n", "\r\n", "

Generators of Groups

\r\n", "\r\n", "
\r\n", "In the last chapter, we introduced the definition of a group, giving some simple examples of groups. \r\n", "There are, of course, many other examples of groups that we will want to work with. We want to learn how \r\n", "to efficiently program Sage to work with any specific group. Many of these groups will be fairly \r\n", "large, and so rather than giving Sage the entire group, we will \r\n", "define a group using a very small number of elements. From these few elements, Sage will be able \r\n", "to reconstruct the entire group. These few elements will be called the generators of the group. So before \r\n", "we can learn how to program a group into Sage, we first need to understand generators.

\r\n", "\r\n", "In this section we will deal with finite groups, that is groups which only have a finite number of elements. We have seen several examples of finite \r\n", "groups, such as Terry's group, Zn, and Zn*. Let us return to one of the groups that we studied in the \r\n", "last section, Z10.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Study the powers of the elements 3 and 4 in the group Z10.

\r\n", "\r\n", "The following command loads this group into Sage. \r\n", "
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = ZGroup(10); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "One of the experiments from the last section was to make circle graphs of the opperation "Add n to each number." For example, the \r\n", "circle graph of Add(3), which maps each element x to the element x+3, is given by \r\n", "
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(G, Add(3))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This graph allows us to visualize powers of 3 in the group Z10. If we follow the red arrows, starting with 0, we have the sequence

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

{0, 3, 6, 9, 2, 5, 8, 1, 4, 7, 0 …}

\r\n", "This tells us that, in this group Z10,\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
30 = 0,
31 = 3,
32 = 3·3 = 6
33 = 3·3·3 = 9
34 = 3·3·3·3 = 2, etc.
\r\n", "

\r\n", " \r\n", " \r\n", "Recall that in this group, the dot represents addition modulo 10, so an exponient represents repeated addition. It is easy \r\n", "to see from the circle graph that every element in the group can be expressed as a power of 3, since one can \r\n", "travel the red arrows to get from 0 to any element of the group. This will not always be the case, as the \r\n", "circle graph of "Add(4)" indicates. \r\n", "
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(G, Add(4))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that Sage draws this graph with arrows of two different colors. This highlights the fact that one cannot travel an arrow to get from a red point to a \r\n", "green point. Thus, not every element can be written as a power of 4.

\r\n", " \r\n", "DEFINITION 2.1
\r\n", "We'll say that the element g ∈ G is a generator of the group G if every element of G can be \r\n", "expressed as a power of g.
\r\n", "\r\n", "
\r\n", "EXPERIMENT:
\r\n", "Using the circle graph, determine which elements of Z10 are generators. Is this set of numbers familar?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can have Sage list all of the generators of a group for us, using the command Generators(). In \r\n", "the case of Z10, the generators are:\r\n", "
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Generators(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", "Try finding the generators of Zn for different values of n. Do you notice a pattern?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXAMPLE:
\r\n", "Find all of the generators of the group Z7*.

\r\n", "\r\n", "This group is small enough to do by hand. For each of the elements in Z7* = {1, 2, 3, 4, 5, 6}, we raise the element to different powers until we \r\n", "reach the identity.

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
12 = 1.
22 = 4, 23 = 1.
32 = 2, 33 = 6, 34 = 4, 35 = 5, 36 = 1.
42 = 2, 43 = 1.
52 = 4, 53 = 6, 54 = 2, 55 = 3, 56 = 1.
62 = 1
\r\n", "
\r\n", "Thus, we see that 3 and 5 are generators.

\r\n", "From the first experiment one might notice a pattern. Notice that 1 will always be a generator of \r\n", "Zn, for Add(1) takes every point on the circle to the next point. See if you can use this fact to prove the next proposition.\r\n", "\r\n", "

\r\n", " \r\n", "PROPOSITION 2.1
\r\n", "The generators of Zn are precisely the integers between 0 and n that are coprime to n.

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

\r\n", "The count of numbers less than n that are coprime to n is called the Euler totient function of n, and \r\n", "is denoted ϕ(n). Thus, the number of generators of Zn is precisely ϕ(n). Here \r\n", "is a small table of this function up to n = 36. \r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
\r\n", " Table of ϕ(n)\r\n", "
nϕ(n)nϕ(n)nϕ(n)
1113122520
211462612
321582718
421682812
5417162928
62186308
7619183130
842083216
9621123320
10422103416
111023223524
1242483612
\r\n", "\r\n", "\r\n", "
\r\n", "For larger values of n, we can use the Sage command EulerPhi. For example, to find the number of generators \r\n", "of Z60, type\r\n", "
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "EulerPhi(60)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "How does Sage come up with this anwser? It uses a fairly simple formula based on the prime factorization of the number. Here is the formula, along with a proof \r\n", "of why this formula works:\r\n", "\r\n", "

\r\n", "\r\n", "THEOREM 2.1: The Totient Function Theorem
\r\n", "If the prime factorization of n is given by\r\n", "

n = p1r¹ · p2r² · \r\n", "p3r³ ··· pkrₖ,

\r\n", "\r\n", "where p1, p2, p3, … pk are primes, and r1, r2, \r\n", "r3, … rk are positive integers, then the count of numbers less then n which are coprime to n is
\r\n", "

ϕ(n) = (p1 − 1)p1r¹−1 · \r\n", "(p2 − 1)p2r²−1 · \r\n", "(p3 − 1)p3r³−1 ··· \r\n", "(pk − 1)pkrₖ−1,

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

\r\n", "Now that we know how to find generators of Zn, let us move on to other groups. Consider for example Z10*. First we \r\n", "load this into Sage:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = ZStar(10); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The elements are {1, 3, 7, 9}. Is 1 a generator of this group? Let's check:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(G, Mult(1))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We see that 1 is not a generator because 1 is the identity element.

\r\n", " \r\n", "EXPERIMENT:
\r\n", " \r\n", "Replace Mult(1) in the last command with Mult(3), Mult(7), and Mult(9) to see which elements, if any, are generators. Recall that the test for a generator is that any \r\n", "element can be reached by any other element in the circle graph by means of the arrows. How many generators are there?

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "According to the table for ϕ(n), Z8* also has four elements. Let us try the same experiment \r\n", "with Z8*. First we load the group into Sage: \r\n", "

" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = ZStar(8); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The elements of this group are {1, 3, 5, 7}. Let us check to see if 3 is a generator:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(G, Mult(3))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", " \r\n", "Replace Mult(3) in the above command with Mult(5), Mult(7), and Mult(1). How many generators are there to this group?

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "By doing this experiment, you will discover that Z8* has a totally different structure than Z10*, in spite \r\n", "of the similarity in how they are defined. As you tried to determine why no element of Z8* acts as a generator, you might notice that \r\n", "every element squared is equal to 1. This is seen in the multiplication table
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
We can also verify this by finding the set of generators of Z8*.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Generators(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Because of this property of Z8*, no element can generate the whole group.

From these examples, we see that some groups \r\n", "have generators, while others do not. This leads us to the following definition.\r\n", "\r\n", "

\r\n", "DEFINITION 2.2
\r\n", "We say a group is cyclic if there is one element that can generate the entire group.

\r\n", " \r\n", "Although we have seen an example of a finite group that is not cyclic, we will later see that the structure of any finite abelian group can be \r\n", "expressed in terms of cyclic groups.

\r\n", " \r\n", "Even when a group is not cyclic, we sometimes can find two elements by which every element of the group can be expressed. For example, consider the group Z8*, and the two elements 3 and 5. The following command maps both Mult(3) and Mult(5) on the same circle graph.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(G, Mult(3), Mult(5))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The red arrows represent multiplying by 3, while the green arrows represent multiplication by 5. Notice that by a combination of red and green arrows, any element of \r\n", "the group can reach any other element through a sequence of arrows, even though neither the red arrows alone nor the green arrows can do this job. We say that \r\n", "the set {3,5} generates the group.

\r\n", " \r\n", "Let us look at one more example. Consider Terry's group, which is loaded into Sage by the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = InitTerry(); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", " Let us see if one of the dance steps will generate the group.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(G, Mult(Spin))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", "By replacing the "Spin" in the last command with the other elements of Terry's group, see if any of the elements generate the group. If not, see if you can \r\n", "find a combination of two elements which generate the group.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "One of the keys for entering a group into Sage is knowing one or two elements (or sometimes even three) that will generate the entire group. This information \r\n", "begins to reveal the structure of the group itself.

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

Defining Finite Groups in Sage

\r\n", "\r\n", "
\r\n", "This part of the worksheet shows how to define finite groups in only Sage. The corresponding \r\n", "section in the Mathematica notebook explains entering groups \r\n", "into Mathematica.
\r\n", "
\r\n", " \r\n", "We saw in the last section that for some groups there is a single element that generates the entire group, whereas in other groups two or more elements are required. In \r\n", "this section we will show how a finite group can be entered into Sage using a set of elements that generates the group. We will begin with a cyclic\r\n", "group Zn which has a single generator which we will call x. From the circle graphs of Zn that we saw in the last secton, we could see that \r\n", "the sequence of n elements

\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
e = x0,
x = x1,
x·x = x2,
x·x·x = x3,
⋯⋯⋯⋯⋯⋯
x·x·x· ⋯ ·x = xn−1,
\r\n", "\r\n", "
\r\n", "must mention every element of Zn exactly once. In fact, this gives us a way to label the elements of Zn in terms of the generator x. We also find that xn = e.\r\n", "Thus, we can define the group Zn merely by saying "x is a generator of the group, and n is the lowest positive number such \r\n", "that xn is the identity."

\r\n", " \r\n", "There are Sage routines included that allow us to quickly make these definitions. Execute the following three statements:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddGroupVar(\"x\")" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(x^5, e)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "What does this do? The first command we have seen once before: it defines the identity element to be e. The second command defines "x" to be a \r\n", "group variable. Finally, the third command defines x5 to be the identity. This is all we need to define the group Z5.

\r\n", " \r\n", "Of course we will want to see the group. The Sage command ListGroup() lists the elements of the currently defined group in a systematic \r\n", "order.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z5 = ListGroup(); Z5" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Thus, the elements of this group are:
\r\n", "

{e, x, x2, x3, x4}.

\r\n", "A multiplication table can be given by:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(Z5)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Although the {0, 1, 2, 3, 4} notation is more concise for this particular example, the use of generators is more versitile, since almost all finite groups can be \r\n", "expressed easily using generators.

\r\n", " \r\n", "EXAMPLE:
\r\n", "Define the group Z8* in Sage.

\r\n", "\r\n", "We saw that every element of this group \r\n", "squared is the identity so this group is not cyclic. However, we found that every element can be expressed in \r\n", "terms of two of the elements, 3 and 5. Hence the set {3, 5} generates the group.

\r\n", "\r\n", "By calling a = 3 and b = 5, we can define the group this way:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddGroupVar(\"a\")" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddGroupVar(\"b\")" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(a^2, e)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(b^2, e)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Is this enough to define the group? Since 7 = 3·5, the last element can be written \r\n", "a·b. The list of four elements would be
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = [e, a, b, a*b]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let us see the multiplication table:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice the four black squares, such as one corresponding to b times a. Sage needs \r\n", "to be told that b·a is the same thing as a·b, so we \r\n", "need a third define statement:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(b*a, a*b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Will this be enough for Sage to find all products? This last Define command redefined the meaning of the \r\n", "variables a and b, so we must first relist the elements of the group.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = [e, a, b, a*b]" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This time, there are no black squares, so the group has been completely defined in Sage. We can also find out if we have finished defining the group by entering \r\n", "the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(a, b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "As long as Sage returns with a list of elements, the group has been sucessfully been defined. \r\n", "Notice that since we needed two generators for this group, we needed to include both generators in the Group command.

\r\n", "\r\n", "We can define several groups in Sage at the same time, and by listing the generators with the Group command, Sage will know which group \r\n", "we are refering to. In contrast, ListGroup() will only list the most recently defined group. In fact, it is a good idea to use a different letter for \r\n", "the identity element if we are to define two different groups, and use different letters for the generators.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Suppose we have three different books on a\r\n", "shelf, and we consider rearrangements of the books. Enter this group into Sage.

\r\n", "\r\n", "We can illustrate the three books by executing the following command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitBooks(3)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Suppose we want to rearrange the three books. One way we can rearrange them is to swap the first two books. This can be done with the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MoveBooks(First)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Another way we can rearrange the books is to take the first book out, slide the other two to the left, and \r\n", "replace the book after the other two. This can be done by the command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MoveBooks(Left)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", "By using only the commands First and Left, how many ways can you rearrange the three books? There are a total of 6 ways to arrange three books. Can you obtain \r\n", "all 6 arrangements using just these two commands?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In doing this experiment, you probably found that there are four other ways we could have rearranged the books, namely swapping the last two books (Last), moving that \r\n", "last book to the front (Right), reversing the order of the books (Rev), and finally leaving the books as they are (Stay). These four additional motions also work in \r\n", "the MoveBooks command, yet the last experiment showed that all arrangements can be obtained using just the commands First and Left. Therefore, the set {First, Left} \r\n", "generates the group of all permutations of the three books.

\r\n", "\r\n", "Let us define this group in Sage. Rather than using the names, we will use the abbreviations: \r\n", "e = the identity element, a = First, and b = Left.

\r\n", "\r\n", "We begin by defining the identity element to be e.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
Next, we have to set up the variables a and b to be two members of the group. We can do this with one AddGroupVar command.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddGroupVar(\"a\",\"b\")" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Now, if we swap the first two books twice, we get back where we started. We thus see that a2 = e. So we define:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(a^2, e)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "If we perform the Left action three times, we also will be back where we started. Thus, we have b3 = e so we can define
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(b^3, e)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In defining Z8*, we needed to also define b·a in terms of\r\n", "a·b. Let us do that for this group also. Notice what happens if we first move the books \r\n", "to the left, and then swap the first two books:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitBooks(3); MoveBooks(Left, First)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Is this the same result if we do those actions in the opposite order? Let's check:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitBooks(3); MoveBooks(First, Left)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Apparently, we need to move the books once more to the left to get the same effect. Let's try it.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitBooks(3); MoveBooks(First, Left, Left)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This tells us that b·a = a·b·b. \r\n", "This group is apparently not commutative. We enter this final definition into Sage.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(b*a, a*b^2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "If we use the Group command to find the list of elements,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(a, b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we find that the last two elements are not written in standard order. In fact, if we compare this list to \r\n", "the ListGroup output," ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = ListGroup(); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we find that a·b·a is really b2. Sage is able\r\n", "to tell us that these are the same element," ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "a*b*a == b^2" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "but will not immediately simplify an expression involving group elements." ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "b^7" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Sage will, however, simplify expressions when putting them in a multiplication table." ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Is this really a group? We can tell from the multiplication table that G is closed with respect to\r\n", "multiplication, and that there is an identity element, e. We also recognize the familiar Latin square \r\n", "property that we have seen in all of the other multiplication tables. Since every row and every column contains \r\n", "exactly one e, every element has a unique inverse. The only property that we cannot check directly using the \r\n", "multiplication table is the associativity property. But this property is guaranteed by the way Sage \r\n", "defines groups. We call this group S3, the permutation group on 3 objects.\r\n", "(Obviously it makes no difference what the three objects are. Books are just one possibility.)

\r\n", "\r\n", "Can Sage determine the inverse of an element? Let's try it:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "(a*b)^-1" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Apparently, Sage is using Proposition 1.2, \r\n", "(u·v)-1 = v-1·u-1. \r\n", "However, it does not simplify this to simpliest form. However, it will be able to detect which element this is." ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "(a*b)^-1 == a*b" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "At first it might seem frustrating that Sage does not simplify group elements. However, the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "SetReducedMult()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "will cause all products to reduce to their simpliest form. Unfortunately, this isn't the same form as \r\n", "the elements given in ListGroup.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "(a*b)^-1" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "a*b" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "See if you can determine which elements of this group are their own inverses." ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", "You may have noticed some simularities between the group S3 and Terry's group. How are these \r\n", "two groups related?

\r\n", "\r\n", "Hint: Terry is colored with the same three colors as the books. Can you find a correspondence between an \r\n", "orientation of Terry and an arrangement of the three books?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The relationship between Terry's group and S3 becomes crystal clear when we look at the \r\n", "multiplication tables of these two. The following Sage command reloads S3, and \r\n", "displays a multiplication table.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\"); \r\n", "AddGroupVar(\"a\",\"b\"); \r\n", "Define(a^2,e); \r\n", "Define(b^3,e); \r\n", "Define(b*a,a*b^2); \r\n", "G = ListGroup(); \r\n", "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", " The following command does the same thing for Terry's group.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = InitTerry();\r\n", "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that even though the names of the elements are different, the color patterns in the two tables are\r\n", "identical. Since all of the group properties come from the multiplication table, these two groups must act in \r\n", "exactly the same way. We say that Terry's group and S3 are isomorphic. We will cover \r\n", "isomophic groups later in Chapter 4.

\r\n", " \r\n", "Let's see an example of a larger group. The command below produces a picture of an octahedron. (Think of this as \r\n", "two square pyramids fused together at the bases.)
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitOctahedron()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This happens to be the shape of an uncut diamond. (Many other gemstones are this shape.) There are eight triangles, which are colored with eight different colors. \r\n", "One problem a gem cutter often faces is determining the orientation he should put the gemstone before he starts to cut. In which case, he needs to know \r\n", "all of the possible ways the octahedron can be rotated. The set of rotations would form a group, similar to Terry's dance steps.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Consider the group of rotations on the octahedron, and enter this group into Sage.

\r\n", "\r\n", "To see the other colors we can flip over this octahedron, \r\n", "using the following command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotateOctahedron(a)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that in the flipping, the orange and blue faces switched places, while the red and fuchsia faces went to \r\n", "the other side. We can see even more of the octahedron by rotating the face closest to us, that is, the face which \r\n", "is now black. We can rotate this one third of a turn counter-clockwise with the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotateOctahedron(b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Between these two actions we can see all of the colors. But there is one more thing that we can do: rotate about \r\n", "a vertex. We can rotate the octahedron one quarter of a turn clockwise about the vertex closest to us with the \r\n", "command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotateOctahedron(c)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "With these three actions we can rotate the octahedron in many different ways. The set of all actions formed by\r\n", "combining actions a, b and c form a group.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "In the previous command, change the letter c to either a or b, and re-execute the \r\n", "command. Repeat this for different letters, and observe what happens. Can you get the octahedron back to the way \r\n", "it began? (The face closest to us was red, and the fuchsia face was immediately below it.)
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In experimenting with this group you probably noticed some truisms for this group. For example, the action \r\n", "a, when performed twice, returns the octahedren to its starting position. The action b, performed\r\n", "three times, also gives us the identity. Finally, the action c must be performed four times \r\n", "before we get to where we started. We can explain these statements to Sage:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\",\"b\",\"c\")\r\n", "Define(a^2,e)\r\n", "Define(b^3,e)\r\n", "Define(c^4,e)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "You may also have noticed that this group is not commutative. That is, b·a does not do \r\n", "the same thing as a·b. However, b·a is another kind of flip, \r\n", "so that b·a·b·a = e. To see this clearly, try the following \r\n", "command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "ShowOctahedron()\r\n", "RotateOctahedron(b,a,b,a)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This animation told us that b·a is its own inverse, and so\r\n", "\r\n", "

b·a = (b·a)-1 = \r\n", "a-1·b-1 = a·b2

\r\n", "\r\n", "We can enter this into Sage with the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(b*a, a*b^2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "To find some other identities, we can try to find other combinations of a, b, and c\r\n", "that produce the identity element. Try this out:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "ShowOctahedron()\r\n", "RotateOctahedron(c,b,c,c,a)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Finally, try this:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "ShowOctahedron()\r\n", "RotateOctahedron(c,a,c,c,c,a,b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "These animations show us that
\r\n", "

c·b·c2·a = e, \r\n", "and c·a·c3·a·b = e

\r\n", "\r\n", "Even though you probably wouldn't have discovered these on your own, you might have discovered formulas similar to \r\n", "these in your experimentation. Let's see what we can do with these two.

\r\n", "\r\n", "From the first one, we have that\r\n", "

c·b = (c·c·a)\r\n", "-1 = a-1·c-1·c-1 =\r\n", "a·c3·c3 \r\n", "= a·c2.

\r\n", "\r\n", "From the second, we can deduce that\r\n", "

\r\n", "c·a = (c3·a·b)-1 \r\n", "= b-1·a-1·c-3 \r\n", "= b2·a·c9 \r\n", "= b2·a·c\r\n", "= b·a·b2·c\r\n", "= a·b2·b2·c\r\n", "= a·b·c

\r\n", "\r\n", "Notice that we had to use the identity b·a = a·b2\r\n", "twice in the final computation. We can enter these properties into Sage as well:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(c*a, a*b*c)\r\n", "Define(c*b, a*c^2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that we have defined b·a, c·a, and \r\n", "c·b in terms of operations that are performed in "alphabetical order." This is\r\n", "a very good strategy for defining any group. If Sage can sort b·a, \r\n", "c·a, and c·b into alphabetical order, then it can manipulate\r\n", "any combination of operations until it produces a form in alphabetical order. This is not the only way that we can \r\n", "define a group in Sage, but it is the one of the most efficient. Thus, Sage should have all of \r\n", "the information it needs to determine the group.

\r\n", "\r\n", "Let's plunge ahead and find out what this group looks like.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = ListGroup(); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We call this the octahedral group. How large is it? Well, we can either squint and count commas, or we can use \r\n", "the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "and have Sage count for us. Either way, we find we have 24 elements in our group. (We could also have \r\n", "found this number using geometry on the octahedron. See Problem 7 of §2.3.)

\r\n", "\r\n", "Is the set of rotations a group? The associativity comes automatically with Sage. The other properties \r\n", "can be verified by looking at the multiplication table. Of course, this group is too large to write out all of the\r\n", "elements in the table. But watch what happens:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Each element is color coded in one of 24 colors, and this code is given by the list on the left. Can you use this \r\n", "table to find the elements which are their own inverses?

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

Subgroups

\r\n", "\r\n", "
\r\n", "Whenever we have a group G, we say that H is a subset of G, denoted\r\n", "

H ⊆ G,

\r\n", "\r\n", "if H consists only of the elements of G. The empty set {} is always considered to be a subset, \r\n", "but we will restrict our attention to non-empty subsets. We are particularly interested if the set H\r\n", "forms a group, since we then would have a "group within a group."

\r\n", "\r\n", "DEFINITION  2.3
\r\n", "We say that H is a subgroup of G if H is a non-empty subset of G\r\n", "and H is a group with respect to the multiplication (·) of G.

\r\n", "\r\n", "It should be noted that all non-trivial groups have at least two subgroups. One subgroup contains just the identity element {e}, while another contains all of the \r\n", "elements of G. These two subgroups are called the trivial subgroups.

\r\n", "\r\n", "For H to be a group, it must satisfy the 4 properties of groups. But the associative property of \r\n", "H is guaranteed because G is associative. Thus, we need these three properties to be true:

\r\n", "\r\n", "1:  H is closed under multiplication. That is,\r\n", "

if x and y ∈ H, then x·y ∈ H.

\r\n", "\r\n", "2:  The identity element of G is in H.

\r\n", "\r\n", "3:  Every element of H has its inverse in H. That is,\r\n", "

if x ∈ H, then x-1 ∈ H.

\r\n", "\r\n", "
\r\n", "These three properties can be combined into one simple test.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 2.2
\r\n", "Let H ⊆ G, and H ≠ { }. Then H is a subgroup of G if, and only if, we have\r\n", "

x·y-1 ∈ H   for all   x, y ∈ H.

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

\r\n", "Let us look at an example. The following commands reload the group S3, the permutation group on three objects, into Sage.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\",\"b\")\r\n", "Define(a^2,e)\r\n", "Define(b^3,e)\r\n", "Define(b*a,a*b^2)\r\n", "G = ListGroup(); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Even though this is a fairly small group (6 elements) we can still find smaller groups within this one. For\r\n", "example, consider the subset\r\n", "

H = {e, b, b2}.

\r\n", "It is easy to see that if x and y are in H, then x·y-1 is in H . (There are nine multiplications \r\n", "to check.) Therefore, this is a subgroup.

\r\n", "\r\n", "How can we verify this is a subgroup using Sage? Let us look at the multiplication table for H:\r\n", "
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable([e, b, b^2])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Since there are no black squares in this table, it is closed under multiplication. \r\n", "Also, every row and column contains one e, so inverses exist for every element. Thus, H is a subgroup of S3.

\r\n", "\r\n", "Try the following subset instead:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable([e, a, b])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice the black squares in the table. This indicates that the subset is not closed under multiplication, and hence is not a subgroup.

\r\n", " \r\n", "EXPERIMENT:
\r\n", "Try changing the subset in the above command to see if you can find other subgroups of S3.\r\n", "How many are there? Don't forget the group itself can be considered to be a subgroup. What about the set \r\n", "containing just the identity?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Here is another example. Recall that ℤ is the group of integers using addition as the operation. If we let \r\n", "k be any integer then we can let\r\n", "

k ℤ = {k·x | x ∈ ℤ}.

\r\n", "The vertical line is read "for which." Thus, k ℤ is the set of "all numbers \r\n", "which can be expressed as k·x for which x is an integer." In other \r\n", "words, k ℤ is the set of all multiples of k. It is clear that k ℤ is a\r\n", "group under addition, since the difference of two multiples of k gives another multiple of k.

\r\n", "\r\n", "One of the main tools we will use to find subgroups of a group is the intersection. Given two subsets H and K of G, the Sage \r\n", "command Intersection finds the set of elements that are in both subsets, denoted H ∩ K. For example, if we are given two sets\r\n", "
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "H = [e, b, b^2]\r\n", "K = [e, a]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "then the Sage command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Intersection(H, K)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "finds the set of all elements in common with H and K. Note that sets are entered \r\n", "in Sage using\r\n", "square brackets, even though they are often displayed using curly braces. (Technically, using square brackets \r\n", "produce a list of elements, which\r\n", "acts similar to a set. But the Sage routines know to treat a list as if it were a set.) Moreover, \r\n", "we can consider taking the intersection of a collection of many sets. If we let
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "L = [[e, a, b], [e, a*b, b], [e, a, b, b^2]]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "then L represents a "set of sets." We can take the intersection of all of the sets in this collection with the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Intersection(L)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The mathematical notation for this intersection is\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
∩H.
H ∈ L
\r\n", "

\r\n", "\r\n", "PROPOSITION 2.3
\r\n", "Given a group G and a non-empty collection of subgroups, denoted by L, then the intersection of all of the subgroups in the collection \r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
H* = ∩H
H ∈ L
\r\n", "is a subgroup of G.

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

\r\n", "This proposition provides us with a general method of producing the subgroups of a group G. \r\n", "Let S be any subset of G. We can consider the collection of all subgroups of G \r\n", "which contain the set S, denoted by L.\r\n", "\r\n", "

\r\n", "DEFINITION 2.4
\r\n", "Given a subset S of a group G, we define the subgroup generated by S to be\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
[S] = ∩H,
H ∈ L
\r\n", "\r\n", "where L denotes the collection of subgroups of G that contains the set S.\r\n", "\r\n", "

\r\n", "By Proposition 2.3, this a subgroup of G. (The collection L is non-empty since it contains \r\n", "G.) By the way that the collection was defined, [S] contains S.

\r\n", "\r\n", "Actually, [S] is the smallest subgroup of G that contains S. For if \r\n", "H is a subgroup of G containing S, then H ∈ L, so that\r\n", "[S] ⊆ H.\r\n", "\r\n", "

\r\n", "We can define [S] in another way. It is clear that [S] contains all of the products of the form

\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
(*)x1·x2·x3· ··· ·xn,
\r\n", "\r\n", "
\r\n", "where either xk ∈ S or xk-1 ∈ S, \r\n", "(1 ≤ k ≤ n).
\r\n", "\r\n", "
\r\n", "Notice that the set of all these products forms a subgroup H of G, and this subgroup contains S. Thus, [S] ⊆ H. But \r\n", "any element of the form (*) must be in [S]. Thus we also have H ⊆ [S]. Therefore H = [S]. In other \r\n", "words, [S] is the subgroup of G consisting of all products of the form (*).

\r\n", " \r\n", "In fact, the Sage command Group finds [S] for any set S. If S\r\n", "is a set of generators of the group G, then [S] = G, so we produced the entire group with the command Group(S). Yet for \r\n", "other sets, we can use the Group command to find the subgroups of a given group.

\r\n", "\r\n", "For example, consider the group S3:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\",\"b\")\r\n", "Define(a^2,e)\r\n", "Define(b^3,e)\r\n", "Define(b*a,a*b^2)\r\n", "ListGroup()" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "SetReducedMult()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Now we can try out the group command to find [S] for different sets S. For example, what if S = {b}? Try it out for yourself:\r\n", "

" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This gives us the subgroup of order 3 that we saw before. What if S is the set {b, a·b}?
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(b, a*b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Had we not used the SetReducedMult command, the elements would have appeared in unusual combinations, yet we could still see that we had all 6 elements. With SetReducedMult, we get the same result as" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(a, b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The elements will not appear in their standard form. However, we see\r\n", "that we have 6 elements, so this apparently gives us the whole group. So {b, a·b}\r\n", "is also a set of generators for the group.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "By using the Group command, find all of the subgroups of G. How many are there?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let's look at a larger group. We found the octahedral group had order 24. Recall that the group was entered with the following Sage commands.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\",\"b\",\"c\")\r\n", "Define(a^2, e)\r\n", "Define(b^3, e)\r\n", "Define(c^4, e)\r\n", "Define(b*a, a*b^2)\r\n", "Define(c*a, a*b*c)\r\n", "Define(c*b, a*c^2)\r\n", "G = ListGroup(); G" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "SetReducedMult()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "For any set S we can find the subgroup [S] by typing G = Group(S)

For example, suppose that the S is the single \r\n", "element {c}. We would type
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(c)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "and find we have a subgroup of order 4.

\r\n", " \r\n", "We can try other combinations of elements. For example, S = {b, c}:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(b, c)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This appears as big as the whole group. Let's double check:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(_)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Since the size of this subgroup is 24 it must be the entire group. This means that the group can be generated \r\n", "with just two of the elements.

\r\n", "\r\n", "Why then did we use three elements to define the group originally? It turns out to be more efficient to define the group in Sage using three elements \r\n", "rather than two! Besides, it is much easier to put the octahedron back into its original position when one can flip the whole thing over.

\r\n", "\r\n", "Here is another subgroup:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(a, b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Wait! This looks familiar. Where have we seen this before?

\r\n", " \r\n", "Look back at the definition of S3. We had a and b as the generators, and \r\n", "we even had a2 = e, b3 = e, \r\n", "and b·a = a·b2. But these rules are all true of this \r\n", "subgroup of the octahedral group. Therefore, these are the same groups. We have found a copy of \r\n", "S3 inside of the octahedral group.
\r\n", "\r\n", "
\r\n", "Recall that we defined a group to be cyclic if there was one element in the group that generates the entire group. We also found that the element which generated \r\n", "the group was not unique. We called all such elements generators of the group.

\r\n", " \r\n", "Let us now consider just the cyclic subgroups of a group G. Notice that if we pick any element x \r\n", "of G, then [{x}] will always be a cyclic subgroup of G. This subgroup is usually denoted by \r\n", "[x].

\r\n", " \r\n", "EXAMPLE:
\r\n", "Find all of the cyclic subgroups of S3.

\r\n", "\r\n", "The process of finding all of the cyclic subgroups is similar to finding the generators of a group. For each element, we consider raising that element to higher and higher \r\n", "powers until we produce the identity element.

\r\n", "\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
(e)2 = e.
(a)2 = e.
(b)2 = b2,  (b)3 = e.
(a·b)2 = e.
(b2)2 = b,  (b2)3 = e.
(a·b2)2 = e.
\r\n", "
\r\n", "\r\n", "Thus, there are 5 cyclic subgroups, {e}, {e, a}, {e, b, b2}, \r\n", "{e, a·b}, and {e, a·b2}. Notice that none of the elements were generators, \r\n", "so the group itself is not cyclic.

\r\n", " \r\n", "The easiest way to keep track of the cyclic subgroups is to note the size of the subgroup generated by each element.

\r\n", " \r\n", "DEFINITION 2.5
\r\n", "Let G be a group and let x be an element in G, We define the order of \r\n", "x to be |[x]|. That is, if [x] is finite, the order of x is the number \r\n", "of elements in [x]. If [x] is an infinite group we define the order of x to be \r\n", "infinity.

\r\n", "\r\n", "For all of the examples we have seen in computing [x], the power of the element x eventually reached the identity element, \r\n", "indicating that we have finished finding the cyclic subgroup. Here is a proof that shows this will always happen for a finite subgroup.\r\n", " \r\n", "

\r\n", "\r\n", "PROPOSITION 2.4
\r\n", "Suppose that the element x has finite order n. Then n is the smallest positive \r\n", "integer such that xn = e. Furthermore,
\r\n", "

[x] = {e, x, x2, \r\n", "x3, …, xn−1}.

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

\r\n", "\r\n", "EXAMPLE:
\r\n", "Find the cyclic subgroups of the group Z15* = {1, 2, 4, 7, 8, 11, 13, 14}, showing the orders of the elements.

\r\n", "\r\n", "We compute powers of each element until we reach the identity.

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
12 = 1.
22 = 4,  23 = 8,  24 = 1.
42 = 1.
72 = 4,  73 = 13,  24 = 1.
82 = 4,  83 = 2,  84 = 1.
112 = 1.
132 = 4,  133 = 7,  134 = 1.
142 = 1.
\r\n", "
\r\n", "Thus, we see that the cyclic subgroups are [1] = {1}, [2] = [8] = {1,2,4,8}, [4] = {1, 4}, \r\n", "[7] = [13] = {1,4,7,13}, [11] = {1, 11}, [14] = {1, 14}. We also see that 1 has order 1, the elements 4, 11, and 14 have order 2, and the elements 2, 7, 8, and 13 have order 4. Note that this group lacks a generator.

\r\n", "\r\n", "We can make a similar observation if we have an infinite cyclic subgroup.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 2.5
\r\n", "Suppose that x has infinite order. Then xn is not the identity element for all \r\n", "nonzero integers n. Furthermore,
\r\n", "

[x] = {…, x-3, x-2, \r\n", "x-1, x0 = e, x1, x2, \r\n", "x3, …},

\r\n", "where the powers of x are all distinct.

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

\r\n", "\r\n", "Even though the group in Proposition 2.5 is infinite, we can still define it in Sage. \r\n", "In fact, we defined an infinite group in the process of defining all of the other groups. \r\n", "If we have x as the generator of an infinite group, then the group is defined by the following:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"x\")" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "At this point, we have an infinite group defined.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "x^4 * x^-7" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Order(x)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Granted, we cannot display all of the elements as we did for other groups (Group(x) would require interupting Sage), but we can still \r\n", "multiply elements of this group.

\r\n", "\r\n", "Because of Propositions 2.4 and 2.5, we know something about all cyclic groups. Any cyclic group G is either a finite group
\r\n", "

G = { e = x0, x1, x2, x3, \r\n", "… , xn-1}

\r\n", "of order n, or is an infinite group
\r\n", "

G = {…, x-3, x-2, x-1, x0 = e, \r\n", "x1, x2, x3, …}

\r\n", "where all powers of x are distinct.

\r\n", "\r\n", "Note that in the first case, G closely resembles Zn. In the second case, G closely resembles ℤ.\r\n", "From this, we can quickly determine the nature of a subgroup of a cyclic group.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 2.6
\r\n", "A subgroup of a cyclic group must be cyclic.

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

\r\n", "\r\n", "EXAMPLE:
\r\n", "Find all the subgroups of the group ℤ.

\r\n", "\r\n", "Since ℤ is cyclic, we know that all subgroups are cyclic, hence can be expresses as [k] for some integer k. But [k] would \r\n", "be the multiples of k, \r\n", "

[k] = { k·x | x ∈ ℤ}.

\r\n", "We will denote the subgroup of the multiples of k by k ℤ. Note that 0 ℤ = {0}, \r\n", "and 1 ℤ = ℤ, so even the trivial subgroups are of this form.

\r\n", "\r\n", "Finding all of the subgroups of a non-cyclic group is trickier, since we have to consider subgroups generated by two or more elements. Sage can speed up the process.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Find all of the subgroups of the group S3.\r\n", "\r\n", "We found all of the cyclic subgroups in a previous example: {e}, {e, a}, {e, b, b2}, \r\n", "{e, a·b}, and {e, a·b2}.\r\n", "Note that any subgroup containing b must also contain b2, and vice-versa. Also all subgroups will contain e. So to find subgroups that \r\n", "require two elements, we have 6 combinations to try:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^2, e)\r\n", "Define(b^3, e)\r\n", "Define(b*a, a*b^2)\r\n", "SetReducedMult()" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(a, b)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(a, a*b)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(a, a*b^2)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(b, a*b)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(b, a*b^2)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(a*b, a*b^2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In each case, we produced the entire group. This shows that the only non-cyclic subgroup of S3 is S3 itself. Thus, we have found a \r\n", "total of 6 subgroups of S3.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Find the orders of the elements of the octahedral group.

\r\n", "\r\n", "If we reload the octahedral group,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\", \"c\")\r\n", "Define(a^2, e); Define(b^3, e); Define(c^4, e)\r\n", "Define(b*a, a*b^2); Define(c*a, a*b*c); Define(c*b, a*c^2)\r\n", "G = ListGroup(); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we can use Sage to quickly find the order of any element in the group. To find the order of the element b·c, we first find \r\n", "the subgroup [b·c].
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(b*c)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This gives us the subgroup generated by the element b·c. We can observe the length of this to be 4 directly, or we can \r\n", "use Sage's len command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(_)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The Sage command Order combines these two operations into one. For example, to find the order of a·c, we type
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Order(a*c)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", "Try replacing the "a*c" with other elements of the group. What do you observe about the orders of the elements?

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "There is a trick for finding the orders of all of the elements of the group at the same time.

" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "[ Order(x) for x in G ]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Every element of this group besides the identity has order 2, 3, or 4. There is a geometrical reason for this: every element represents a rotation of \r\n", "either ±90°, ±120°, or 180°. (See Problem 7 from §2.3.)

\r\n", "\r\n", "Let us now consider the orders of the elements of a cyclic group. Consider, for example, the group Z12.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = ZGroup(12); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "We can find the orders of all of the elements in the group G using the same technique.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "[ Order(x) for x in G ]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "This tells us that there is one element of order 1, one element of order 2, 2 elements of order 3, 2 elements of order 4, 2 elements of order 6, and finally 4 elements \r\n", "of order 12.

\r\n", "\r\n", "It is apparent that finding the number of elements of order k involve finding the number of solutions to the \r\n", "equation xk = e. \r\n", "To help us find the number of solutions for a cyclic group, let us first prove the following proposition about modular multiplication.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 2.7
\r\n", "Let n and k be two positive integers. Then
\r\n", "

x·k ≡ 0 (mod n)

\r\n", "if and only if\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
x =   a·n  
gcd(n, k)
\r\n", "for some integer a.

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

\r\n", "We can now find the number of elements in a cyclic group that satisfies the equation xk = e.\r\n", " \r\n", "

\r\n", "\r\n", "COROLLARY 2.1
\r\n", "Let G be a cyclic group of order n. Then there are precisely gcd(n, k) elements of G such that xk = e.

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

\r\n", "EXPERIMENT:
\r\n", "Use Sage to find the number of solutions to x8 = 0 in Z12. Does this result agree with Corollary 2.1?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "\r\n", "Finding the number of solutions to the equation xk = e in a group will become important as we classify the different groups. We will give a notation \r\n", "to this count.

\r\n", "\r\n", "DEFINITION 2.6
\r\n", "Let G be a group, and k a positive integer. Then the number of elements of G for which xk = e is called \r\n", "the kth root count of G, and is denoted by\r\n", "

Rk(G) = ⎜{x ∈ G | xk = e}⎟.

\r\n", " \r\n", "Corollary 2.1 can now be expressed in the new notation. If G is a cyclic group, then\r\n", "

Rk(G) = gcd(|G|, k).

\r\n", "\r\n", "Sage has a command RootCount(G, k) that will compute Rk(G). For example, we can redo the last experiment with the commands:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = ZGroup(12)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RootCount(G, 8)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Now let's look at a more complicated group. You probably have heard of the infamous Rubik's Cube©. Rubik also came out with a number of other puzzles, \r\n", "one of which is called the Pyraminx™. The Pyraminx™ consists of a triangular pyramid, with each of the four triangular sides partitioned into nine \r\n", "smaller triangles. The four "tips" can rotate, but this does not affect the puzzle. To simplify the picture we can chop off the tips of the pyramid. Execute \r\n", "the following command to show a picture of the puzzle with the tips cut off:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitPuzzle()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Now the four corners of this puzzle can rotate, moving some of the middle pieces in the process. For example, the front corner can rotate clockwise 120°\r\n", "by the command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotatePuzzle(f)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can rotate the back corner clockwise with the command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotatePuzzle(b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "At this point, we see the advantage of chopping off the four tips of the pyramid: this allows us to peer inside of the puzzle to see what is on the back face!

\r\n", " \r\n", "The left and right corners can be rotated using the commands
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotatePuzzle(l)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotatePuzzle(r)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Now we have really scrambled the puzzle! Not to fear––we can put the puzzle back into its original form with the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitPuzzle()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "That is sure much easier than taking the puzzle apart and putting it back together again!

\r\n", " \r\n", "The set of all actions on the puzzle forms a group, called the Pyraminx™ group. This group is generated by the elements \r\n", "{t, b, r, l}. However, this group has over 900,000 elements!  Thus, it is not such a good idea to have Sage list \r\n", "all elements of the group. It really wouldn't tell us much, and would probably run us out of memory.

\r\n", "\r\n", "We can determine information about the Pyraminx™ group by working with the puzzle. For example, we know that the elements r, l, t\r\n", "and b each have order 3. But what about the element b·f? Try this out yourself:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotatePuzzle(b,f)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that we have the animation feature here. How many times must this statement be executed to get back to the original state? This will give us the order of the element \r\n", "b·f. So we have a subgroup, namely [b·f] of that order.

\r\n", " \r\n", "EXPERIMENT:
\r\n", "Using this method of repeating the operation, find the orders of the following elements:

\r\n", "b·f·r·f·f
\r\n", "f·b·r

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "One can see quite a variety of possibilities for the order of an element in this group. Can you find an element with an order larger that the last example? \r\n", "Perhaps we need to study the puzzle further to answer that question. When we know more about groups in general we will not only be able to answer this question, \r\n", "but also build up some tools that will help us to solve the puzzle.\r\n", "\r\n", "









































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

Proofs:

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

\r\n", "\r\n", "Suppose that g is a generator of Zn. Then 1 is able to be expressed as a power of g, so we have that
\r\n", "

gv = 1 in Zn

\r\n", " \r\n", "for some v. Since the group action of Zn is addition, raising to a power is equivalent to repeated addition, or standard \r\n", "multiplication.

\r\n", "\r\n", "Thus, we have that
\r\n", "

g v ≡ 1 (mod n).

\r\n", "By Proposition 1.7, there is such a v if, and only if, g is coprime to n.

\r\n", " \r\n", "Now suppose that g is coprime to n. By Proposition 1.7, there is a v such that
\r\n", "

g v ≡ 1 (mod n), hence gv = 1 in Zn.

\r\n", "So 1 can be expressed as a power of g. But 1 is a generator of Zn, and so every element of Zn can be expressed as a power \r\n", "of 1, say 1w. Then that element can be written as g(v w) = (gv)w = 1w.\r\n", "So every element can be expressed as a power of g, hence g is a generator of Zn.

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









































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

\r\n", "\r\n", "To begin, let us show that if p is a prime, then ϕ(pr) = (p − 1)pr−1.

\r\n", "Note that the only numbers that are not coprime to pr will be multiples of p. So of the numbers between 1 \r\n", "and pr, exactly 1/p of them will be multiples of p. The remaining (1 − 1/p)pr will be coprime, and \r\n", "this can be simplified to (p − 1)pr−1.

\r\n", " \r\n", "Next we want to show that if n and m are coprime, then ϕ(n m) = ϕ(n) ϕ(m). \r\n", "Let A denote the set of numbers that are less than n, but coprime to n. Let B denote the set of numbers that are less than \r\n", "m, but coprime to m.

\r\n", " \r\n", "Then for any number x coprime to n·m, x mod n must be in the set A, \r\n", "while x mod m must be in \r\n", "B. Yet for every a in A and b in B, there is, by the Chinese remainder theorem, a unique number less than \r\n", "n m that is equalivalent to a (mod n) and b (mod m). This number will be coprime to both n and \r\n", "m, and hence will be coprime to n m.

\r\n", " \r\n", "Therefore, we have a one-to-one correspondence between ordered pairs (a, b), where a ∈ A, and b ∈ B, and \r\n", "numbers coprime to n m. Thus, we have
\r\n", "

ϕ(n m) = ϕ(n)·ϕ(m).

\r\n", "
\r\n", "Finally, we can combine these results together. By simply noting that if

\r\n", "

n = p1r¹ · p2r² \r\n", "· p3r³ ··· pkrₖ,

\r\n", "then p1r¹, p2r², p3r³, \r\n", "…, pkrₖ will all be coprime. Hence, we can find ϕ for each of these terms, and multiply them \r\n", "together, giving us our formula.

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









































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

\r\n", "First of all, we need to see that if H is a subgroup, then x·y-1 is in H whenever x and y are in \r\n", "H. By property (3), y-1 is in H, and so by property (1), x·y-1 is in H.

\r\n", "\r\n", "Conversely, let us suppose that H ⊆ G, H ≠ {}, and whenever x, y ∈ H, then \r\n", "x·y-1 ∈ H. We need to see that properties (1) through (3) are satisfied.

\r\n", "\r\n", "Since H is not the empty set, there is an element x in H, and so x·x-1 = e is in H. \r\n", "Thus property (2) holds.

\r\n", "\r\n", "Next, we have that if y is in H, then e·y-1 = y-1 is in H, and so property (3) \r\n", "holds.

\r\n", "\r\n", "Finally, if x and y are in H, then y-1 is in H, and so \r\n", "x·(y-1)-1 = x·y is in H. \r\n", "Thus, property (1) holds.

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









































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

\r\n", "First of, note that H* is not the empty set, since the identity element is in each H in the collection. We now can apply Proposition 2.2.\r\n", "Let x and y be two elements of H*. Then for every H ∈ L we have x, y ∈ H.\r\n", "Since H is a subgroup of G, we have x·y-1 ∈ H. Therefore, x·y-1 is \r\n", "in H*, and so H* is a subgroup of G.

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









































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

\r\n", "Since [x] is finite, not all of the elements {x0, x1, x2, x3, \r\n", "x4, … } can be distinct. Suppose that xa = xb for two integers a and b, with \r\n", "b > a. Then \r\n", "x(b−a) = e and (b − a) > 0. So there exists a positive integer c such that\r\n", "xc = e. We can let n be the smallest such integer. We want to prove that\r\n", "

[x] = {e = x0, x1, x2, x3, …, \r\n", "xn−1}

\r\n", "with these elements distinct. Indeed, if\r\n", "

xa = xb with 0 ≤ a < b ≤ n − 1,

\r\n", "then xb−a = e, and 0 < b − a < n, which contradicts the definition of n. Therefore, \r\n", "the elements in\r\n", "

{ e = x0, x1, x2, x3, …,\r\n", "xn−1 }

\r\n", "are all distinct.

\r\n", "\r\n", "Finally, we need to show that if y is in [x], then there exists a r such that

\r\n", "

xr = y, with 0 ≤ r ≤ n − 1.

\r\n", "But y = xk for some k ∈ ℤ. We can define r = k mod n. \r\n", "Then 0 ≤ r ≤ n − 1, and furthermore, there is an integer q such that k − r = n q. Thus,
\r\n", "

y = xk = x(n q + r) = \r\n", "(xn)q·xr = eq·xr = xr.

\r\n", "So every element of [x] is of the form xr, with 0 ≤ r ≤ n − 1.

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









































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

\r\n", "Suppose that xn = e for some nonzero n. It suffices to consider the case n > 0, for if xn = e, then \r\n", "x−n = e.

\r\n", "\r\n", "By exactly the same reasoning as was used to prove Proposition 2.4, we see that

\r\n", "

[x] = {e = x0, x1, x2, x3, …, \r\n", "xn−1}.

\r\n", "But this contradicts the fact that [x] was infinite. Therefore, xn = e only if n = 0.

\r\n", "\r\n", "Moreover, if xa = xb, then xb−a = e, and so b − a = 0 by \r\n", "what we have just proved. Thus, the powers of x are all distinct.

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









































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

\r\n", "Let g be a generator of the cyclic group G. The trivial subgroup {e} is considered cyclic, so let S be a non-trivial subgroup. Then every \r\n", "element of S can be written as gi for some i. Since both gi and g−i would \r\n", "then be in S, we see that gi is in S for some positive i. Let k be the smallest positive integer such \r\n", "that gk is in S. Then g(mk) is in S for all integers m.

\r\n", "\r\n", "If there were some other element in S not in [gk], then this element is gy for some integer y. \r\n", "Then y = q k + r for some 0 < r < k. Then \r\n", "gr = gy·(gk)−q ∈ S, but we chose k to be the smallest positive integer for which gk ∈ S. Thus, S = [gk], and so S is cyclic.

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









































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

\r\n", "\r\n", "First of all, notice that if\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
x =   a·n  ,
gcd(n, k)
\r\n", "then\r\n", "\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·k =  a·n·k  = a·n·   k  ,
gcd(n, k)gcd(n, k)
\r\n", "
\r\n", "and since gcd(n, k) is a divisor of k, we see that x · k is a multiple of n. Thus,\r\n", "

x k ≡ 0 (mod n).

\r\n", " \r\n", "Now suppose that x·k is a multiple of n. We want to show that\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
a = x·gcd(n, k)
n
\r\n", "
\r\n", "is in fact an integer. By the greatest common divisor theorem (1.2), there exist integers u and v such that \r\n", "gcd(n, k) = u·n + v·k. Then

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
a = x·(u·n + v·k) = x·u + x·k·v.
nn
\r\n", "
\r\n", "Since x · k is a multiple of n, we see that a is an integer. Thus,\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
x =   a·n  
gcd(n, k)
\r\n", "for some integer a.

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









































\r\n", "\r\n", "\r\n", "\r\n", "Proof of Corollary 2.1:

\r\n", "Let g be a generator of G, and let x = gy be an element of G. Then\r\n", "xk = (gy)k = gy·k, which is equal to the identity if and only if
\r\n", "

y·k ≡ 0 (mod n).

\r\n", "By Proposition 2.7, this is true if and only if\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
y =   a·n  
gcd(n, k)
\r\n", "
\r\n", "for some integer a. Hence, the number of possible values of y between 0 and n − 1 for which \r\n", "gy·k = e is

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
   n    = gcd(n, k).
n / gcd(n, k)
\r\n", "
\r\n", "Each such value of y between 0 and n − 1 produces a different solution x = gy, so there are \r\n", "exactly gcd(n, k) solutions.

\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", "§2.1 #23)
\r\n", "Use Sage's circle graph to find all of the generators of the group Z21.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.1 #24)
\r\n", "Use Sage to see if there an element of Z25* that generates Z25*. If so, how many such \r\n", "elements are there?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.1 #25)
\r\n", "By using Sage's Generators() command, determine whether Zn* is cyclic for n = 9, 27, 81, 243, 5, 25, 125. \r\n", "Make a conjecture about when Zn* is cyclic if n is a power of an odd prime.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.1 #26)
\r\n", "By using Sage's Generators() command, determine whether Zn* is cyclic for n = 18, 54, 162, 486, 50, 250, 98, 686. \r\n", "Make a conjecture about when Zn* is cyclic if n is twice the power of an odd prime.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.1 #27)
\r\n", "By using Sage's Generators() command, see if you can find an n for which Zn* is cyclic, and n doesn't fit \r\n", "into the categories of Problems 25 or 26.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.2 #18)
\r\n", "Use Sage to define a group that has two elements, a and b, for which a5 = b4 =e,\r\n", "and b · a = a2 · b. How many elements does this group have?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.2 #19)
\r\n", "Find all of the generators of the group Z24. Then have Sage construct a multiplication table for the \r\n", "group Z24*.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.2 #20)
\r\n", "Since the elements b and c could generate the octahedral group, define this group\r\n", "in Sage using only b and c.
\r\n", "\r\n", "Hint: Besides b3 = e and c4 = e, \r\n", "Sage will need one more equation. What is the order of b2·c?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.2 #21)
\r\n", "Define a group in Sage that is generated by two elements a and b, \r\n", "with a3 = b5 = (a·b)2 = e. How big is the group?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.3 #21)
\r\n", "Use Problem 18 from §2.2 to find the subgroup generated by the elements a and b2. How many elements does this have?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.3 #22)
\r\n", "Use Sage to investigate the relationship between the order of an element, and the order of its inverse. First we pick a large group:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = ZStar(360)\r\n", "len(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The following command selects a random element from the group.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "a = G[randint(1, len(G)) - 1]; a" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Then compare the results of the following operations.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Order(a)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Order(a^-1)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "What do you observe? Try this with several random elements. Can you make a conjecture?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.3 #23)
\r\n", "Repeat Problem 22, only using the octahedral group.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\", \"c\")\r\n", "Define(a^2, e); Define(b^3, e); Define(c^4, e)\r\n", "Define(b*a, a*b^2); Define(c*a, a*b*c); Define(c*b, a*c^2)\r\n", "G = ListGroup()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.3 #24)
\r\n", "Use Sage to find the order of the elements b·f, b·f·r·f·f \r\n", "and f·b·r in the Pyramix™ group.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§2.3 #25)
\r\n", "Can you use Sage to find an element of the Pyramix™ group that has order 30?
\r\n", "(Hint: Exactly five of the six edges must be moved out of place. The sixth edge must flip as well.)
" ] }, { "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 }