# Chapter 10: Software and Calculations
# 
# 
# For computing cosets there are functions  LeftCosets  and RightCosets 
# . They take as arguments a group G and a subgroup K and produce a list
# of the elements of G partitioned into cosets with K itself as the
# first coset. To illustrate, let's repeat example 10.1. We have
# 
> A4 := Group( [[1, 2, 3]], [[2, 3, 4]] ):
# 
# and
# 
> V := Group( [[1, 2], [3, 4]] , [[1, 3], [2, 4]] ):
# 
# Then
# 
> LeftCosets(A4,V);

  [{[], [[1, 4], [2, 3]], [[1, 3], [2, 4]], [[1, 2], [3, 4]]},

        {[[2, 3, 4]], [[1, 3, 2]], [[1, 4, 3]], [[1, 2, 4]]},

        {[[1, 3, 4]], [[1, 4, 2]], [[2, 4, 3]], [[1, 2, 3]]}]

# 
# If you only want a representative from each coset you can use 
# LeftCosetReps  or  
# RightCosetReps:
# 
> LeftCosetReps(A4,V);

                    [[], [[1, 2, 4]], [[1, 3, 4]]]

# 
# These are just the first elements from each coset. We can check that V
# satisfies 10.3(i) by
# computing its right cosets and comparing them with the left cosets:
# 
> RightCosets(A4,V);

  [{[], [[1, 3], [2, 4]], [[1, 4], [2, 3]], [[1, 2], [3, 4]]},

        {[[1, 3, 4]], [[1, 4, 2]], [[1, 2, 3]], [[2, 4, 3]]},

        {[[1, 2, 4]], [[1, 3, 2]], [[2, 3, 4]], [[1, 4, 3]]}]

# 
# So you can multiply two cosets together to get a third:
# 
> {[[1, 3, 4]], [[1, 4, 2]], [[1, 2, 3]], [[2, 4, 3]]} &* {[[1, 2, 4]],
> [[1, 3, 2]], [[2, 3, 4]], [[1, 4, 3]]};
> 

      {[], [[1, 3], [2, 4]], [[1, 4], [2, 3]], [[1, 2], [3, 4]]}

# 
# We can also verify that V is normal in A4 by calculating its
# conjugates. First we have
# the function  Conjugate(a,b) which conjugates b by a . For example, if
# 
> a := [[1, 2, 3]];

                           a := [[1, 2, 3]]

> b := [[1, 4]];

                            b := [[1, 4]]

# 
# then
# 
> Conjugate(a, b);

                               [[2, 4]]

# 
# You can conjugate all the elements of a set by a at once: 
# 
> Conjugate( a, Elements(V) );

      {[], [[1, 3], [2, 4]], [[1, 4], [2, 3]], [[1, 2], [3, 4]]}

# 
# which confirms that V is normal in A4.
# 
# 
# Example 10.5
# 
# In S5 we have the subgroup F20 (see exercise 8.19):
# 
> F20 := Group( [[1, 2, 3, 4, 5]] , [[1, 2, 4, 3]] ):
# 
# A pair of generators of S5 is
# 
> a := [[1, 2, 3, 4, 5]];

                        a := [[1, 2, 3, 4, 5]]

> b := [[1, 2]];

                            b := [[1, 2]]

# 
# To check whether F20 is normal in S5 you conjugate the generators of
# F20 first by a and then by b and look whether the resulting sets lie
# in F20. In fact since a belongs to F20 you need only check
# 
> Conjugate( b, Generators(F20) );

                 {[[1, 4, 3, 2]], [[1, 3, 4, 5, 2]]}

# 
# which does not lie in F20. So F20 is not normal. 
# 
# 
# Example 10.6
# 
# Note: Each time you run this example Maple will list the cosets of K
# in G72 differently. However it is easy
# to make the necessary changes to the discussion.
# 
# Let G72 (see exercise 8.16) be the permutation group
# 
> G72 := Group( [[1,2,3]], [[1,4],[2,5],[3,6]], [[1,5,2,4],[3,6]] ):
# 
# G72 has order 72:
# 
> Ord(G72);

                                  72

# 
# Let K be the subgroup
# 
> K := Group( [[1,2,3]], [[4,5,6]] ):
# 
# Since these two 3-cycles commute with one another, K is isomorphic to 
# Z/3Z x Z/3Z .
# 
# The first element of the list of generators of G72 is also a generator
# of K. So to check that K is a normal subgroup we need only conjugate
# the generators of K by the remaining two generators of G72:
# 
> Conjugate( [[1, 4], [2, 5], [3, 6]] , Generators(K) );

                      {[[4, 5, 6]], [[1, 2, 3]]}

> Conjugate( [[1, 5, 2, 4], [3, 6]] , Generators(K) );

                      {[[4, 6, 5]], [[1, 2, 3]]}

# 
# Therefore K is a normal subgroup of G72. The quotient group  L := G72/
# K  has order  72/9=8 . We want to determine which group of order 8 it
# is. Since each coset has 9 elements, we will tell Maple not to print
# out the entire list of cosets when it computes L:
# 
> L := LeftCosets( G72, K):
# 
# First we look at representatives from each of the cosets.
# 
> LeftCosetReps( G72, K);

  [[[4, 6, 5]], [[1, 2], [5, 6]], [[1, 5, 2, 4, 3, 6]],

        [[1, 2], [4, 6, 5]], [[1, 4, 2, 6], [3, 5]],

        [[1, 3, 2], [4, 6]], [[1, 6, 3, 5, 2, 4]],

        [[1, 6], [2, 4, 3, 5]]]

# 
# The first coset, L[1] , is K, the identity element in L. The second,
# L[2]  = (12)(56)K. Now
# 
#  ((12)(56) K)^2 = ((12)(56))^2 K = K .
# 
# In other words, it has order 2. Furthermore
# 
> L[3]&*L[3];

  {[[4, 6, 5]], [], [[1, 2, 3], [4, 6, 5]], [[1, 3, 2], [4, 6, 5]],

        [[4, 5, 6]], [[1, 3, 2], [4, 5, 6]], [[1, 3, 2]],

        [[1, 2, 3], [4, 5, 6]], [[1, 2, 3]]}

# 
# which is just L[1] . So L[3] has order 2. Similarly L[4], L[6] and
# L[7] all have order 2.
# This leaves L[5] and L[8] . Now
# 
> L[5]&*L[5];

  {[[1, 2], [5, 6]], [[1, 2], [4, 6]], [[1, 2], [4, 5]],

        [[2, 3], [4, 6]], [[1, 3], [5, 6]], [[1, 3], [4, 6]],

        [[2, 3], [5, 6]], [[2, 3], [4, 5]], [[1, 3], [4, 5]]}

# 
# Comparing this with our list of coset representatives, we see that
# this must be L[2] , which has
# order 2. So L[5] has order 4. Furthermore
# 
> L[5]&*L[2];

  {[[1, 6], [2, 4, 3, 5]], [[1, 4, 2, 5], [3, 6]],

        [[1, 5, 2, 6], [3, 4]], [[1, 4, 3, 6], [2, 5]],

        [[1, 6, 2, 4], [3, 5]], [[1, 5, 3, 4], [2, 6]],

        [[1, 4], [2, 5, 3, 6]], [[1, 6, 3, 5], [2, 4]],

        [[1, 5], [2, 6, 3, 4]]}

# 
# which is just L[8] . Therefore L[8] = L[5]^3, which is the inverse of
# L[5], and it too has order 4.
# It begins to look as if L might be isomorphic to D4 (see equation
# (7.1)). To check this, we need
# generators 
> sigma;#   and  
> tau;#   satisfying
# 
#   
> sigma;# ^4  = 1     
> tau;# ^2  = 1     
> tau;sigma;#  = 
> sigma;# ^(-1 )
> tau#   .
# 
# Let's try  
> sigma;#  =  L[5]  and  
> tau;#  = L[3] . To see that they generate L we compute
# 
> L[3]&*L[5];

  {[[1, 3, 2], [4, 6]], [[1, 2, 3], [4, 6]], [[4, 5]],

        [[1, 2, 3], [4, 5]], [[4, 6]], [[1, 3, 2], [5, 6]],

        [[1, 2, 3], [5, 6]], [[1, 3, 2], [4, 5]], [[5, 6]]}

> L[3]&*L[2];

  {[[1, 6, 3, 5, 2, 4]], [[1, 5, 2, 6, 3, 4]], [[1, 6, 2, 4, 3, 5]],

        [[1, 4, 2, 5, 3, 6]], [[1, 5, 3, 4, 2, 6]],

        [[1, 6], [2, 4], [3, 5]], [[1, 4, 3, 6, 2, 5]],

        [[1, 5], [2, 6], [3, 4]], [[1, 4], [2, 5], [3, 6]]}

> L[3]&*L[8];

  {[[1, 2], [4, 6, 5]], [[1, 2]], [[1, 3], [4, 5, 6]],

        [[2, 3], [4, 6, 5]], [[2, 3]], [[1, 3]], [[2, 3], [4, 5, 6]],

        [[1, 2], [4, 5, 6]], [[1, 3], [4, 6, 5]]}

# 
# Thus
# 
# L[3] . L[5] =  L[6]
# L[3] . L[5]^2 = L[3] . L[2] = L[7]
# L[3] . L[5]^3 = L[3] . L[8] =  L[4]  .
# 
# So L[5] and L[3] do generate L . Now let's see whether they satisfy
# the right relation.
# We must check whether 
# 
# L[5]^(-1) . L[3] = L[8] . L[3] =  L[6]  .
# 
> L[8]&*L[3];

  {[[1, 3, 2], [4, 6]], [[1, 2, 3], [4, 6]], [[4, 5]],

        [[1, 2, 3], [4, 5]], [[4, 6]], [[1, 3, 2], [5, 6]],

        [[1, 2, 3], [5, 6]], [[1, 3, 2], [4, 5]], [[5, 6]]}

# 
# which is L[6] . So indeed
# 
# L = D4 .