# Chapter 3: Software and Calculations
# 
# The package "groups" can be used to make useful calculations in
# permutation groups. To start you must load it:
# 
> read groups;
# 
# Next you have to know how our notation for permutations is
# implemented. In this package a permutation (in mapping notation) is
# given by the list of its images enclosed in square brackets.  For
# example
# 

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

# 
# is represented by
> [2, 4, 1, 6, 3, 5]# 
# You can name this permutation:
# 
> a := [2, 4, 1, 6, 3, 5];

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

# 
# If  b  is another permutation then the product  ab  is given by
# 
# a &* b
# For example if
# 
> b := [4, 2, 3, 6, 1, 5];

                       b := [4, 2, 3, 6, 1, 5]

# 
# then entering
# 
> a&*b;

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

# 
# To find the inverse of  a , enter
# 
> Inverse(a);

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

# 
# A permutation in cycle notation is written as the list of its cycles,
# which are in turn lists. For example  (1 2)(3 4 5)  is represented by
# 
# [[1 2], [3 4 5]]
# 
#  You can take products and inverses using cycle notation just as with
# mapping notation:
# 
> [[1, 2],[3, 4, 5]] &* [[1, 2, 3, 4, 5]];

                            [[2, 4, 3, 5]]

> Inverse( [[1, 2],[3, 4, 5]] );

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

# 
# You can apply these functions to lists of permutations. When you take
# the product of two lists of permutations, the product of every
# permutation in the first list with every one in the second will be
# computed: for example
# 
> {a,b} &* {a,b};

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

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

# 
# These functions are useful for checking whether a set of permutations
# form a group. For example let
# 
> G := { [2, 3, 1, 5, 4], [4, 1, 2, 5, 3], [1, 3, 5, 2, 4], [2, 1, 3, 4,
> 5], 
>     [1, 2, 3, 4, 5] };

  G := {[1, 2, 3, 4, 5], [1, 3, 5, 2, 4], [4, 1, 2, 5, 3],

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

> Inverse(G);

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

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

# 
# So the inverse of [2, 3, 1, 5, 4] , which is [3, 1, 2, 5, 4] , is not
# in the set  G  and therefore  G  is not a permutation group.
# 
# The function  GROUP  calculates the permutation group generated by a
# given set of permutations. All computations take place in a where n 
# is the largest number occurring in the cycles in the input. The
# algorithm used is the one given in exercise 3.8. For example, the
# permutation group  G = <(1 2 3 4 5), (1 2)(3 5)>  is given by
# 
> G := Group( [[1, 2, 3, 4, 5]] , [[1, 2],[3, 5]] );

  G := [[[[1, 2, 3, 4, 5]], [[1, 2], [3, 5]]], {[], [[1, 2], [3, 5]],

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

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

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

# 
# The result consists of the two generators followed by the list of the
# elements in the group G. If the group
# is a bit larger , it is a good idea to use a colon ":" at the end of
# the input statement so that you do not get pages of output. To just
# see a list of the elements in G, you use the function Elements:
# 
> Elements(G);

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

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

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

# 
# The function Generators will print out the generators of G again:
# 
> Generators(G);

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

# 
# The order of the permutation group is given by the function  Ord :
# 
> Ord(G);

                                  10

# 
# We can verify by computation that (1 2) and (1 2 3 4 5 6) generate S6:
# 
> Ord( Group( [[1, 2]], [[1, 2, 3, 4, 5, 6]] ) );

                                 720

# 
# Since  6! = 720  , they do generate S6.
# 
# Let's look for generators of A4, which is also not cyclic. We know
# that the even permutations of degree 4 are the 3-cycles, the products
# of 2 disjoint transpositions and the identity. We first try two
# 3-cycles:
# 
> Ord( Group( [[1, 2, 3]], [[2, 3, 4]] ) );

                                  12

# 
# It is not hard to show that the order of An is  n!/2 (see exercise
# 3.11). Therefore the two 3-cycles do generate a. How about a 3-cycle
# and a product of two disjoint transpositions?
# 
> Ord( Group( [[1, 2, 3]], [[1,2],[3, 4]] ) );

                                  12

# 
# These two appear to generate A4 as well. Let's see how these
# calculations extend to A5 . We could use two 3-cycles again. But that
# would not work in A6 . So we shall try with a 5-cycle and a 3-cycle:
# 
> Ord( Group( [[1, 2, 3, 4, 5]], [[1, 2, 3]] ) );

                                  60

# 
# And 60 is the order of A5 . We now try 5-cycle and a product of two
# disjoint transpositions;
# 
> Ord( Group( [[1, 2, 3, 4, 5]], [[1,2],[3, 4]] ) );

                                  60

# 
# This works too. Do these calculations extend to A6 ? Do they
# generalize to An , for arbitrary n?
#