# 9.5: Sage

- Page ID
- 81102

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Sage has limited support for actually creating isomorphisms, though it is possible. However, there is excellent support for determining if two permutation groups are isomorphic. This will allow us to begin a little project to locate *all* of the groups of order less than \(16\) in Sage's permutation groups.

## Isomorphism Testing

If `G`

and `H`

are two permutation groups, then the command `G.is_isomorphic(H)`

will return `True`

or `False`

as the two groups are, or are not, isomorphic. Since “isomorpic to” is an equivalence relation by Theorem \(9.10\), it does not matter which group plays the role of `G`

and which plays the role of `H`

.

So we have a few more examples to work with, let us introduce the Sage command that creates an external direct product. If `G`

and `H`

are two permutation groups, then the command `direct_product_permgroups([G,H])`

will return the external direct product as a new permutation group. Notice that this is a function (not a method) and the input is a list. Rather than just combining two groups in the list, any number of groups can be supplied. We illustrate isomorphism testing and direct products in the context of Theorem \(9.21\), which is an equivalence, so tells us *exactly* when we have isomorphic groups. We use cyclic permutation groups as stand-ins for \({\mathbb Z}_n\) by Theorem \(9.8\).

First, two isomorphic groups.

Now, two non-isomorphic groups.

Notice how the simple computation of a greatest common divisor predicts the incredibly complicated computation of determining if two groups are isomorphic. This is a nice illustration of the power of mathematics, replacing a difficult problem (group isomorphism) by a simple one (factoring and divisibility of integers). Let us build one more direct product of cyclic groups, but with three groups, each with orders that are pairwise relatively prime.

If you try the following with larger parameters you may get an error (`database_gap`

).

## Classifying Finite Groups

Once we understand isomorphic groups as being the “same”, or “fundamentally no different,” or “structurally identical,” then it is natural to ask how many “really different” finite groups there are. Corollary \(9.9\) gives a partial answer: for each prime there is just one finite group, with \({\mathbb Z}_p\) as a concrete manifestation.

Let us embark on a quest to find all the groups of order less than \(16\) in Sage as permutation groups. For prime orders \(1,2,3,5,7,11\) and \(13\) we know there is really just one group each, and we can realize them all:

So now our smallest unknown case is order \(4\text{.}\) Sage knows at least three such groups, and we can use Sage to check if any pair is isomorphic. Notice that since “isomorphic to” is an equivalence relation, and hence a transitive relation, the two tests below are sufficient.

So we have at least two different groups: \({\mathbb Z}_4\) and \({\mathbb Z}_2\times{\mathbb Z}_2\text{,}\) with the latter also known as the Klein 4-group. Sage will not be able to tell us if we have a *complete* list — this will always require theoretical results like Theorem \(9.10\). We will shortly have a more general result that handles the case of order \(4\text{,}\) but right now, a careful analysis (by hand) of the possibilities for the Cayley table of a group of order \(4\) should lead you to the two possibilities above as the only possibilities. Try to deduce what the Cayley table of an order \(4\) group should look like, since you know about identity elements, inverses and cancellation.

We have seen at least two groups of order \(6\) (next on our list of non-prime orders). One is abelian and one is not, so we do not need Sage to tell us they are structurally different. But let us do it anyway.

Is that all? There is \({\mathbb Z}_3\times{\mathbb Z}_2\text{,}\) but that is just \({\mathbb Z}_6\) since \(2\) and \(3\) are relatively prime. The dihedral group, \(D_3\text{,}\) all symmetries of a triangle, is just \(S_3\text{,}\) the symmetric group on \(3\) symbols.

Exercise \(9.4.55\) from this section classifies all groups of order \(2p\text{,}\) where \(p\) is a prime. Such a group is either cyclic or a dihedral group. So the two groups above, \({\mathbb Z}_6\) and \(D_3\text{,}\) are the complete list of groups of order \(6\text{.}\)

By this general result, in addition to order \(6\text{,}\) we also know the complete lists of groups of orders \(10\) and \(14\text{.}\) To Be Continued.

## Internal Direct Products

An internal direct product is a statement about subgroups of a single group, together with a theorem that links them to an external direct product. We will work an example here that will illustrate the nature of an internal direct product.

Given an integer \(n\text{,}\) the set of positive integers less than \(n\text{,}\) and relatively prime to \(n\) forms a group under multiplication mod \(n\text{.}\) We will work in the set `Integers(n)`

where we can add *and* multiply, but we want to stay strictly with multiplication only.

First we build the subgroup itself. Notice how we must convert `x`

into an integer (an element of `ZZ`

) so that the greatest common divisor computation performs correctly.

So we have a group of order \(12\text{.}\) We are going to try to find a subgroup of order \(6\) and a subgroup of order \(2\) to form the internal direct product, and we will restrict our search initially to cyclic subgroups of order \(6\text{.}\) Sage has a method that will give the order of each of these elements, relative to multiplication, so let us examine those next.

We have many choices for generators of a cyclic subgroup of order \(6\) and for a cyclic subgroup of order \(2\text{.}\) Of course, some of the choices for a generator of the subgroup of order \(6\) will generate the same subgroup. Can you tell, just by counting, how many subgroups of order \(6\) there are? We are going to pick the first element of order \(6\text{,}\) and the last element of order \(2\text{,}\) for no particular reason. After your work through this once, we encourage you to try other choices to understand why some choices lead to an internal direct product and some do not. Notice that we choose the elements from the list `U`

so that they are sure to be elements of `Z36`

and behave properly when multiplied.

So `A`

and `B`

are two cyclic subgroups. Notice that their intersection is the identity element, one of our requirements for an internal direct product. So this is a good start.

`Z36`

is an abelian group, thus the condition on all products commuting will hold, but we illustrate the Sage commands that will check this in a non-abelian situation.

Finally, we need to check that by forming products with elements from `A`

and `B`

we create the entire group. Sorting the resulting list will make a check easier for us visually, and is required if we want Sage to do the check.

That's it. We now condense all this information into the statement that “`U`

is the internal direct product of `A`

and `B`

.” By Theorem \(9.27\), we see that `U`

is isomorphic to a product of a cyclic group of order \(6\) and a cyclic group of order \(2\text{.}\) So in a very real sense, `U`

is no more or less complicated than \({\mathbb Z}_6\times{\mathbb Z}_2\text{,}\) which is in turn isomorphic to \({\mathbb Z}_3\times{\mathbb Z}_2\times{\mathbb Z}_2\text{.}\) So we totally understand the “structure” of `U`

. For example, we can see that `U`

is not cyclic, since when written as a product of cyclic groups, the two orders are not relatively prime. The final expression of `U`

suggests you could find three cyclic subgroups of `U`

, with orders \(3\text{,}\) \(2\) and \(2\text{,}\) so that `U`

is an internal direct product of the three subgroups.