cosets-sage.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section6.5Sage

¶

Sage can create all of the cosets of a subgroup, and all of the subgroups of a group. While these methods can be somewhat slow, they are in many, many ways much better than experimenting with pencil and paper, and can greatly assist us in understanding the structure of finite groups.

SubsectionCosets

Sage will create all the right (or left) cosets of a subgroup. Written mathematically, cosets are sets, and the order of the elements within the set is irrelevant. With Sage, lists are more natural, and here it is to our advantage.

Sage creates the cosets of a subgroup as a list of lists. Each inner list is a single coset. The first coset is always the coset that is the subgroup itself, and the first element of this coset is the identity. Each of the other cosets can be construed to have their first element as their representative, and if you use this element as the representative, the elements of the coset are in the same order they would be created by multiplying this representative by the elements of the first coset (the subgroup).

The keyword side can be 'right' or 'left', and if not given, then the default is right cosets. The options refer to which side of the product has the representative. Notice that now Sage's results will be “backwards” compared with the text. Here is Example 6.2 reprised, but in a slightly different order.

G = SymmetricGroup(3)
a = G("(1,2)")
H = G.subgroup([a])
rc = G.cosets(H, side='right'); rc

lc = G.cosets(H, side='left'); lc

So if we work our way through the brackets carefully we can see the difference between the right cosets and the left cosets. Compare these cosets with the ones in the text and see that left and right are reversed. Shouldn't be a problem — just keep it in mind.

G = SymmetricGroup(3)
b = G("(1,2,3)")
H = G.subgroup([b])
rc = G.cosets(H, side='right'); rc

lc = G.cosets(H, side='left'); lc

If we study the bracketing, we can see that the left and right cosets are equal. Let's see what Sage thinks:

rc == lc

Mathematically, we need sets, but Sage is working with ordered lists, and the order matters. However, if we know our lists do not have duplicates (the .cosets() method will never produce duplicates) then we can sort the lists and a test for equality will perform as expected. The elements of a permutation group have an ordering defined for them — it is not so important what this is, just that some ordering is defined. The sorted() function will take any list and return a sorted version. So for each list of cosets, we will sort the individual cosets and then sort the list of sorted cosets. This is a typical maneuver, though a bit complicated with the nested lists.

rc_sorted = sorted([sorted(coset) for coset in rc])
rc_sorted

lc_sorted = sorted([sorted(coset) for coset in lc])
lc_sorted

rc_sorted == lc_sorted

The list of all cosets can be quite long (it will include every element of the group) and can take a few seconds to complete, even for small groups. There are more sophisticated, and faster, ways to study cosets (such as just using their representatives), but to understand these techniques you also need to understand more theory.

SubsectionSubgroups

Sage can compute all of the subgroups of a group. This can produce even more output than the coset method and can sometimes take much longer, depending on the structure of the group. The list is in order of the size of the subgroups, with smallest first. As a demonstration we will first compute and list all of the subgroups of a small group, and then extract just one of these subgroups from the list for some futher study.

G = SymmetricGroup(3)
sg = G.subgroups(); sg

H = sg[4]; H

H.order()

H.list()

H.is_cyclic()

The output of the .subgroups() method can be voluminous, so sometimes we are interested in properties of specific subgroups (as in the previous example) or broader questions of the group's “subgroup structure.” Here we expand on Corollary 6.15. Notice that just because Sage does not compute a subgroup of order 6 in $A_4\text{,}$ this is no substitute whatsoever for a proof such as given for the corollary. But the computational result emboldens us to search for the theoretical result with confidence.

G = AlternatingGroup(4)
sg = G.subgroups()
[H.order() for H in sg]

So we see no subgroup of order 6 in the list of subgroups of $A_4\text{.}$ Notice how Lagrange's Theorem (Theorem 6.10) is in evidence — all the subgroup orders divide $12\text{,}$ the order of $A_4\text{.}$ Be patient, the next subgroup computation may take a while.

G = SymmetricGroup(4)
sg = G.subgroups()
[H.order() for H in sg]

Again, note Lagrange's Theorem in action. But more interestingly, $S_4$ has a subgroup of order 6. Four of them, to be precise. These four subgroups of order 6 are similar to each other, can you describe them simply (before digging into the sg list for more information)? If you were curious how many subgroups $S_4$ has, you could simply count the number of subgroups in the sg list. The len() function does this for any list and is often an easy way to count things.

len(sg)

SubsectionSubgroups of Cyclic Groups

Now that we are more familiar with permutation groups, and know about the .subgroups() method, we can revisit an idea from Chapter 4. The subgroups of a cyclic group are always cyclic, but how many are there and what are their orders?

G = CyclicPermutationGroup(20)
[H.order() for H in G.subgroups()]

G = CyclicPermutationGroup(19)
[H.order() for H in G.subgroups()]

We could do this all day, but you have Sage at your disposal, so vary the order of G by changing n and study the output across many runs. Maybe try a cyclic group of order 24 and compare with the symmetric group $S_4$ (above) which also has order 24. Do you feel a conjecture coming on?

n = 8
G = CyclicPermutationGroup(n)
[H.order() for H in G.subgroups()]

SubsectionEuler Phi Function

To add to our number-theoretic functions from Chapter 2, we note that Sage makes the Euler $\phi$-function available as the function euler_phi().

euler_phi(345)

Here's an interesting experiment that you can try running several times.

m = random_prime(10000)
n = random_prime(10000)
m, n, euler_phi(m*n) == euler_phi(m)*euler_phi(n)

Feel another conjecture coming on? Can you generalize this result?