Module permgroup

Permutation groups

A {\it permutation group} is a finite group G whose elements are permutations  
of a given finite set X (i.e., bijections X --> X) and whose group operation is 
the composition of permutations. The number of elements of $X$ is called the
{\it degree} of G.

In \sage a permutation is represented as either a string that defines a 
permutation using disjoint cycle notation, or a list of tuples, which represent 
disjoint cycles.

\begin{verbatim}
(a,...,b)(c,...,d)...(e,...,f)  <--> [(a,...,b), (c,...,d),..., (e,...,f)]
                  () = identity <--> []
\end{verbatim}                  
           
You can make the "named" permutation groups (see \code{permgp_named.py})
and use the following constructions:

-- permutation group generated by elements,
-- direct_product_permgroups, which takes a list of permutation
             groups and returns their direct product.

JOKE:
    Q: What's hot, chunky, and acts on a polygon? A: Dihedral soup.
    Renteln, P. and Dundes, A. "Foolproof: A Sampling of Mathematical 
    Folk Humor." Notices Amer. Math. Soc. 52, 24--34, 2005.

AUTHOR:
    - David Joyner (2005-10-14): first version
    - David Joyner (2005-11-17)
    - William Stein (2005-11-26): rewrite to better wrap Gap
    - David Joyner (2005-12-21)
    - Stein and Joyner (2006-01-04): added conjugacy_class_representatives
    - David Joyner (2006-03): reorganization into subdirectory perm_gps;
                              added __contains__, has_element; fixed _cmp_;
                              added subgroup class+methods, PGL,PSL,PSp, PSU classes, 
    - David Joyner (2006-06): added PGU, functionality to SymmetricGroup, AlternatingGroup,
                                    direct_product_permgroups
    - David Joyner (2006-08): added degree, ramification_module_decomposition_modular_curve
                              and ramification_module_decomposition_hurwitz_curve
                              methods to PSL(2,q), MathieuGroup, is_isomorphic
    - Bobby Moretti (2006)-10): Added KleinFourGroup, fixed bug in DihedralGroup
    - David Joyner (2006-10): added is_subgroup (fixing a bug found by Kiran Kedlaya), 
                              is_solvable, normalizer, is_normal_subgroup, Suzuki
    - David Kohel (2007-02): fixed __contains__ to not enumerate group elements, 
                              following the convention for __call__
    - David Harvey, Mike Hansen, Nick Alexander, William Stein (2007-02,03,04,05): Various patches
    - Nathan Dunfield (2007-05): added orbits
    - David Joyner (2007-06): added subgroup method (suggested by David Kohel),
                              composition_series, lower_central_series, upper_central_series,
                              cayley_table, quotient_group, sylow_subgroup, is_cyclic,
                              homology, homology_part, cohomology, cohomology_part, 
                              poincare_series, molien_series, is_simple, is_monomial,
                              is_supersolvable, is_nilpotent, is_perfect, is_polycyclic,
                              is_elementary_abelian, is_pgroup, gens_small,
                              isomorphism_type_info_simple_group.
                              moved all the "named" groups to a new file.
    - Nick Alexander (2007-07): move is_isomorphic to isomorphism_to, add from_gap_list
    - William Stein (2007-07): put is_isomorphic back (and make it better)
    - David Joyner (2007-08): fixed bugs in composition_series, upper/lower_central_series, derived_series,
    - David Joyner (2008-06): modified is_normal (reported by W. J. Palenstijn),
                              and added normalizes

REFERENCES:
    Cameron, P., Permutation Groups. New York: Cambridge University Press, 1999.
    Wielandt, H., Finite Permutation Groups. New York: Academic Press, 1964.
    Dixon, J. and Mortimer, B., Permutation Groups, Springer-Verlag, Berlin/New York, 1996. 

NOTE:
    Though Suzuki groups are okay, Ree groups should *not* be wrapped as permutation groups - the 
    construction is too slow - unless (for small values or the parameter) they are
    made using explicit generators.
  

Takes the direct product of the permutation groups listed in P.

EXAMPLES:
    sage: G1 = AlternatingGroup([1,2,4,5])
    sage: G2 = AlternatingGroup([3,4,6,7])
    sage: D = direct_product_permgroups([G1,G2,G1])
    sage: D.order()
    1728
    sage: D = direct_product_permgroups([G1])
    sage: D==G1
    True
    sage: direct_product_permgroups([])
    Symmetric group of order 1! as a permutation group

Convert a string giving a list of GAP permutations into a list of elements of G.

EXAMPLES:
    sage: from sage.groups.perm_gps.permgroup import from_gap_list
    sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
    sage: L = from_gap_list(G, "[(1,2,3)(4,5), (3,4)]"); L
    [(1,2,3)(4,5), (3,4)]
    sage: L[0].parent() is G
    True
    sage: L[1].parent() is G
    True

Return the permutation group associated to $x$ (typically a list
of generators).

EXAMPLES:
    sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
    sage: G
    Permutation Group with generators [(1,2,3)(4,5), (3,4)]

We can also make permutation groups from PARI groups:
    sage: H = pari('x^4 - 2*x^3 - 2*x + 1').polgalois()
    sage: G = PariGroup(H, 4); G            
    PARI group [8, -1, 3, "D(4)"] of degree 4
    sage: H = PermutationGroup(G); H          # requires optional database_gap
    Transitive group number 3 of degree 4
    sage: H.gens()                            # requires optional database_gap
    ((1,2,3,4), (1,3))

We can also create permutation groups whose generators are
Gap permutation objects.
    sage: p = gap('(1,2)(3,7)(4,6)(5,8)'); p
    (1,2)(3,7)(4,6)(5,8)
    sage: PermutationGroup([p])
    Permutation Group with generators [(1,2)(3,7)(4,6)(5,8)]
    
EXAMPLES:
There is an underlying gap object that implements each permutation group.

    sage: G = PermutationGroup([[(1,2,3,4)]])
    sage: G._gap_()
    Group( [ (1,2,3,4) ] )
    sage: gap(G)
    Group( [ (1,2,3,4) ] )
    sage: gap(G) is G._gap_()
    True
    sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
    sage: current_randstate().set_seed_gap()
    sage: G._gap_().DerivedSeries()
    [ Group( [ (1,2,3)(4,5), (3,4) ] ), Group( [ (1,5)(3,4), (1,5)(2,3), (1,5,4) ] ) ]