r"""
Permutation groups
A permutation group is a finite group `G` whose elements are
permutations of a given finite set `X` (i.e., bijections
`X \longrightarrow X`) and whose group operation is the composition of
permutations. The number of elements of `X` is called the 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. That is::
(a,...,b)(c,...,d)...(e,...,f) <--> [(a,...,b), (c,...,d),..., (e,...,f)]
() = identity <--> []
You can make the "named" permutation groups (see
``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.
AUTHORS:
- 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)
- William Stein and David 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
- David Joyner (2008-08): Added example to docstring of cohomology.
- Simon King (2009-04): __cmp__ methods for PermutationGroup_generic and PermutationGroup_subgroup
- Nicolas Borie (2009): Added orbit, transversals, stabiliser and strong_generating_system methods
- Christopher Swenson (2012): Added a special case to compute the order efficiently.
(This patch Copyright 2012 Google Inc. All Rights Reserved. )
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.
"""
from functools import wraps
from sage.misc.randstate import current_randstate
import sage.groups.group as group
from sage.rings.all import QQ, Integer
from sage.interfaces.all import is_ExpectElement
from sage.interfaces.gap import gap, GapElement
from sage.groups.perm_gps.permgroup_element import PermutationGroupElement, standardize_generator
from sage.groups.abelian_gps.abelian_group import AbelianGroup
from sage.misc.cachefunc import cached_method
from sage.groups.class_function import ClassFunction
from sage.misc.package import is_package_installed
from sage.sets.finite_enumerated_set import FiniteEnumeratedSet
from sage.categories.all import FiniteEnumeratedSets
from sage.functions.other import factorial
def load_hap():
"""
Load the GAP hap package into the default GAP interpreter
interface. If this fails, try one more time to load it.
EXAMPLES::
sage: sage.groups.perm_gps.permgroup.load_hap()
"""
try:
gap.eval('LoadPackage("hap")')
except:
gap.eval('LoadPackage("hap")')
def hap_decorator(f):
"""
A decorator for permutation group methods that require HAP. It
checks to see that HAP is installed as well as checks that the
argument ``p`` is either 0 or prime.
EXAMPLES::
sage: from sage.groups.perm_gps.permgroup import hap_decorator
sage: def foo(self, n, p=0): print "Done"
sage: foo = hap_decorator(foo)
sage: foo(None, 3) #optional - gap_packages
Done
sage: foo(None, 3, 0) #optional - gap packages
Done
sage: foo(None, 3, 5) #optional - gap packages
Done
sage: foo(None, 3, 4) #optional - gap_packages
Traceback (most recent call last):
...
ValueError: p must be 0 or prime
"""
@wraps(f)
def wrapped(self, n, p=0):
if not is_package_installed('gap_packages'):
raise RuntimeError, "You must install the optional gap_packages package."
load_hap()
from sage.rings.arith import is_prime
if not (p == 0 or is_prime(p)):
raise ValueError, "p must be 0 or prime"
return f(self, n, p=p)
return wrapped
def direct_product_permgroups(P):
"""
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 0! as a permutation group
"""
n = len(P)
if n == 0:
from sage.groups.perm_gps.permgroup_named import SymmetricGroup
return SymmetricGroup(0)
elif n == 1:
return P[0]
else:
G = gap.DirectProduct(*P)
return PermutationGroup(gap_group=G)
def from_gap_list(G, src):
r"""
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
"""
src = src.replace("[", "").replace("]", "")
srcs = src.split("),")
for i in range(len(srcs[:-1])):
srcs[i] = srcs[i] + ")"
srcs = map(G, srcs)
return srcs
def PermutationGroup(gens=None, gap_group=None, domain=None, canonicalize=True, category=None):
"""
Return the permutation group associated to `x` (typically a
list of generators).
INPUT:
- ``gens`` - list of generators (default: ``None``)
- ``gap_group`` - a gap permutation group (default: ``None``)
- ``canonicalize`` - bool (default: ``True``); if ``True``,
sort generators and remove duplicates
OUTPUT:
- A permutation group.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
sage: G
Permutation Group with generators [(3,4), (1,2,3)(4,5)]
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 # optional - database_gap
Transitive group number 3 of degree 4
sage: H.gens() # 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)]
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( [ (3,4), (1,2,3)(4,5) ] ), Group( [ (1,5)(3,4), (1,5)(2,4), (1,5,3) ] ) ]
TESTS::
sage: r = Permutation("(1,7,9,3)(2,4,8,6)")
sage: f = Permutation("(1,3)(4,6)(7,9)")
sage: PermutationGroup([r,f]) #See Trac #12597
Permutation Group with generators [(1,3)(4,6)(7,9), (1,7,9,3)(2,4,8,6)]
sage: PermutationGroup(SymmetricGroup(5))
Traceback (most recent call last):
...
TypeError: gens must be a tuple, list, or GapElement
"""
if not is_ExpectElement(gens) and hasattr(gens, '_permgroup_'):
return gens._permgroup_()
if gens is not None and not isinstance(gens, (tuple, list, GapElement)):
raise TypeError, "gens must be a tuple, list, or GapElement"
return PermutationGroup_generic(gens=gens, gap_group=gap_group, domain=domain,
canonicalize=canonicalize, category=category)
class PermutationGroup_generic(group.Group):
"""
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
sage: G
Permutation Group with generators [(3,4), (1,2,3)(4,5)]
sage: G.center()
Subgroup of (Permutation Group with generators [(3,4), (1,2,3)(4,5)]) generated by [()]
sage: G.group_id() # optional - database_gap
[120, 34]
sage: n = G.order(); n
120
sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
sage: TestSuite(G).run()
"""
def __init__(self, gens=None, gap_group=None, canonicalize=True, domain=None, category=None):
r"""
INPUT:
- ``gens`` - list of generators (default: ``None``)
- ``gap_group`` - a gap permutation group (default: ``None``)
- ``canonicalize`` - bool (default: ``True``); if ``True``,
sort generators and remove duplicates
OUTPUT:
- A permutation group.
EXAMPLES:
We explicitly construct the alternating group on four
elements::
sage: A4 = PermutationGroup([[(1,2,3)],[(2,3,4)]]); A4
Permutation Group with generators [(2,3,4), (1,2,3)]
sage: A4.__init__([[(1,2,3)],[(2,3,4)]]); A4
Permutation Group with generators [(2,3,4), (1,2,3)]
sage: A4.center()
Subgroup of (Permutation Group with generators [(2,3,4), (1,2,3)]) generated by [()]
sage: A4.category()
Category of finite permutation groups
sage: TestSuite(A4).run()
TESTS::
sage: TestSuite(PermutationGroup([[]])).run()
sage: TestSuite(PermutationGroup([])).run()
"""
from sage.categories.finite_permutation_groups import FinitePermutationGroups
super(PermutationGroup_generic, self).__init__(category = FinitePermutationGroups().or_subcategory(category))
if (gens is None and gap_group is None):
raise ValueError, "you must specify gens or gap_group"
if gens is None:
if isinstance(gap_group, str):
gap_group = gap(gap_group)
gens = [gen for gen in gap_group.GeneratorsOfGroup()]
if domain is None:
gens = [standardize_generator(x) for x in gens]
domain = set()
for x in gens:
for cycle in x:
domain = domain.union(cycle)
domain = sorted(domain)
if all(isinstance(p, (Integer, int, long)) for p in domain):
domain = range(1, max([1] + domain)+1)
if domain not in FiniteEnumeratedSets():
domain = FiniteEnumeratedSet(domain)
self._domain = domain
self._deg = len(self._domain)
self._domain_to_gap = dict((key, i+1) for i, key in enumerate(self._domain))
self._domain_from_gap = dict((i+1, key) for i, key in enumerate(self._domain))
if not gens:
gens = [()]
gens = [self._element_class()(x, self, check=False) for x in gens]
if canonicalize:
gens = sorted(set(gens))
self._gens = gens
def construction(self):
"""
EXAMPLES::
sage: P1 = PermutationGroup([[(1,2)]])
sage: P1.construction()
(PermutationGroupFunctor[(1,2)], Permutation Group with generators [()])
sage: PermutationGroup([]).construction() is None
True
This allows us to perform computations like the following::
sage: P1 = PermutationGroup([[(1,2)]]); p1 = P1.gen()
sage: P2 = PermutationGroup([[(1,3)]]); p2 = P2.gen()
sage: p = p1*p2; p
(1,2,3)
sage: p.parent()
Permutation Group with generators [(1,2), (1,3)]
sage: p.parent().domain()
{1, 2, 3}
Note that this will merge permutation groups with different
domains::
sage: g1 = PermutationGroupElement([(1,2),(3,4,5)])
sage: g2 = PermutationGroup([('a','b')], domain=['a', 'b']).gens()[0]
sage: g2
('a','b')
sage: p = g1*g2; p
(1,2)(3,4,5)('a','b')
"""
gens = self.gens()
if len(gens) == 1 and gens[0].is_one():
return None
else:
from sage.categories.pushout import PermutationGroupFunctor
return (PermutationGroupFunctor(gens, self.domain()),
PermutationGroup([]))
@cached_method
def _has_natural_domain(self):
"""
Returns True if the underlying domain is of the form (1,...,n)
EXAMPLES::
sage: SymmetricGroup(3)._has_natural_domain()
True
sage: SymmetricGroup((1,2,3))._has_natural_domain()
True
sage: SymmetricGroup((1,3))._has_natural_domain()
False
sage: SymmetricGroup((3,2,1))._has_natural_domain()
False
"""
domain = self.domain()
natural_domain = FiniteEnumeratedSet(range(1, len(domain)+1))
return domain == natural_domain
def _gap_init_(self):
r"""
Returns a string showing how to declare / initialize ``self`` in Gap.
Stored in the ``self._gap_string`` attribute.
EXAMPLES:
The ``_gap_init_`` method shows how you
would define the Sage ``PermutationGroup_generic``
object in Gap::
sage: A4 = PermutationGroup([[(1,2,3)],[(2,3,4)]]); A4
Permutation Group with generators [(2,3,4), (1,2,3)]
sage: A4._gap_init_()
'Group([PermList([1, 3, 4, 2]), PermList([2, 3, 1, 4])])'
"""
return 'Group([%s])'%(', '.join([g._gap_init_() for g in self.gens()]))
def _magma_init_(self, magma):
r"""
Returns a string showing how to declare / initialize self in Magma.
EXAMPLES:
We explicitly construct the alternating group on four
elements. In Magma, one would type the string below to construct
the group::
sage: A4 = PermutationGroup([[(1,2,3)],[(2,3,4)]]); A4
Permutation Group with generators [(2,3,4), (1,2,3)]
sage: A4._magma_init_(magma)
'PermutationGroup<4 | (2,3,4), (1,2,3)>'
sage: S = SymmetricGroup(['a', 'b', 'c'])
sage: S._magma_init_(magma)
'PermutationGroup<3 | (1,2,3), (1,2)>'
"""
g = ', '.join([g._gap_cycle_string() for g in self.gens()])
return 'PermutationGroup<%s | %s>'%(self.degree(), g)
def __cmp__(self, right):
"""
Compare ``self`` and ``right``.
The comparison extends the subgroup relation. Hence, it is first checked
whether one of the groups is subgroup of the other. If this is not the
case then the ordering is whatever it is in Gap.
NOTE:
The comparison does not provide a total ordering, as can be seen
in the examples below.
EXAMPLES::
sage: G1 = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
sage: G2 = PermutationGroup([[(1,2,3),(4,5)]])
sage: G1 > G2 # since G2 is a subgroup of G1
True
sage: G1 < G2
False
The following example shows that the comparison does not yield a total
ordering::
sage: H1 = PermutationGroup([[(1,2)],[(5,6)]])
sage: H2 = PermutationGroup([[(3,4)]])
sage: H3 = PermutationGroup([[(1,2)]])
sage: H1 < H2 # according to Gap's ordering
True
sage: H2 < H3 # according to Gap's ordering
True
sage: H3 < H1 # since H3 is a subgroup of H1
True
"""
if (not isinstance(right, PermutationGroup_generic) or
self.domain() != right.domain()):
return -1
if self is right:
return 0
gSelf = self._gap_()
gRight = right._gap_()
gapcmp = gSelf.__cmp__(gRight)
if not gapcmp:
return 0
if gSelf.IsSubgroup(gRight):
return 1
if gRight.IsSubgroup(gSelf):
return -1
return gapcmp
def _element_class(self):
r"""
Return the class to be used for creating elements of this group. By
default this is
``sage.groups.perm_gps.permgroup_element.PermutationGroupElement``, but
it may be overridden in derived subclasses (most importantly
``sage.rings.number_field.galois_group.GaloisGroup_v2``).
EXAMPLE::
sage: SymmetricGroup(17)._element_class()
<type 'sage.groups.perm_gps.permgroup_element.PermutationGroupElement'>
"""
return PermutationGroupElement
def __call__(self, x, check=True):
"""
Coerce ``x`` into this permutation group.
The input can be either a string that defines a permutation in
cycle notation, a permutation group element, a list of integers
that gives the permutation as a mapping, a list of tuples, or the
integer 1.
EXAMPLES:
We illustrate each way to make a permutation in `S_4`::
sage: G = SymmetricGroup(4)
sage: G((1,2,3,4))
(1,2,3,4)
sage: G([(1,2),(3,4)])
(1,2)(3,4)
sage: G('(1,2)(3,4)')
(1,2)(3,4)
sage: G('(1,2)(3)(4)')
(1,2)
sage: G(((1,2,3),(4,)))
(1,2,3)
sage: G(((1,2,3,4),))
(1,2,3,4)
sage: G([1,2,4,3])
(3,4)
sage: G([2,3,4,1])
(1,2,3,4)
sage: G(G((1,2,3,4)))
(1,2,3,4)
sage: G(1)
()
Some more examples::
sage: G = PermutationGroup([(1,2,3,4)])
sage: G([(1,3), (2,4)])
(1,3)(2,4)
sage: G(G.0^3)
(1,4,3,2)
sage: G(1)
()
sage: G((1,4,3,2))
(1,4,3,2)
sage: G([(1,2)])
Traceback (most recent call last):
...
TypeError: permutation [(1, 2)] not in Permutation Group with generators [(1,2,3,4)]
"""
try:
if x.parent() is self:
return x
except AttributeError:
pass
if isinstance(x, (int, long, Integer)) and x == 1:
return self.identity()
return self._element_class()(x, self, check=check)
def _coerce_impl(self, x):
r"""
Implicit coercion of ``x`` into ``self``.
EXAMPLES:
We illustrate some arithmetic that involves implicit
coercion of elements in different permutation groups::
sage: g1 = PermutationGroupElement([(1,2),(3,4,5)])
sage: g1.parent()
Symmetric group of order 5! as a permutation group
sage: g2 = PermutationGroupElement([(1,2)])
sage: g2.parent()
Symmetric group of order 2! as a permutation group
sage: g1*g2
(3,4,5)
sage: g2*g2
()
sage: g2*g1
(3,4,5)
We try to implicitly coerce in a non-permutation, which raises a
TypeError::
sage: G = PermutationGroup([[(1,2,3,4)], [(1,2)]])
sage: G._coerce_impl(1)
Traceback (most recent call last):
...
TypeError: no implicit coercion of element into permutation group
"""
from permgroup_named import SymmetricGroup
if isinstance(x, PermutationGroupElement):
x_parent = x.parent()
if x_parent is self:
return x
compatible_domains = all(point in self._domain_to_gap for point in x_parent.domain())
if compatible_domains and (self.__class__ == SymmetricGroup or x._gap_() in self._gap_()):
return self._element_class()(x.cycle_tuples(), self, check=False)
raise TypeError, "no implicit coercion of element into permutation group"
@cached_method
def list(self):
"""
Return list of all elements of this group.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3,4)], [(1,2)]])
sage: G.list()
[(), (3,4), (2,3), (2,3,4), (2,4,3), (2,4), (1,2), (1,2)(3,4), (1,2,3), (1,2,3,4), (1,2,4,3), (1,2,4), (1,3,2), (1,3,4,2), (1,3), (1,3,4), (1,3)(2,4), (1,3,2,4), (1,4,3,2), (1,4,2), (1,4,3), (1,4), (1,4,2,3), (1,4)(2,3)]
sage: G = PermutationGroup([[('a','b')]], domain=('a', 'b')); G
Permutation Group with generators [('a','b')]
sage: G.list()
[(), ('a','b')]
"""
return list(self.__iter__())
def __contains__(self, item):
"""
Returns boolean value of ``item in self``.
EXAMPLES::
sage: G = SymmetricGroup(16)
sage: g = G.gen(0)
sage: h = G.gen(1)
sage: g^7*h*g*h in G
True
sage: G = SymmetricGroup(4)
sage: g = G((1,2,3,4))
sage: h = G((1,2))
sage: H = PermutationGroup([[(1,2,3,4)], [(1,2),(3,4)]])
sage: g in H
True
sage: h in H
False
sage: G = PermutationGroup([[('a','b')]], domain=('a', 'b'))
sage: [('a', 'b')] in G
True
"""
try:
item = self(item, check=True)
except:
return False
return True
def has_element(self, item):
"""
Returns boolean value of ``item in self`` - however *ignores*
parentage.
EXAMPLES::
sage: G = CyclicPermutationGroup(4)
sage: gens = G.gens()
sage: H = DihedralGroup(4)
sage: g = G([(1,2,3,4)]); g
(1,2,3,4)
sage: G.has_element(g)
True
sage: h = H([(1,2),(3,4)]); h
(1,2)(3,4)
sage: G.has_element(h)
False
"""
return item in self
def __iter__(self):
"""
Return an iterator over the elements of this group.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3)], [(1,2)]])
sage: [a for a in G]
[(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)]
"""
for g in self._gap_().Elements():
yield self._element_class()(g, self, check=False)
def gens(self):
"""
Return tuple of generators of this group. These need not be
minimal, as they are the generators used in defining this group.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3)], [(1,2)]])
sage: G.gens()
[(1,2), (1,2,3)]
Note that the generators need not be minimal, though duplicates are
removed::
sage: G = PermutationGroup([[(1,2)], [(1,3)], [(2,3)], [(1,2)]])
sage: G.gens()
[(2,3), (1,2), (1,3)]
We can use index notation to access the generators returned by
``self.gens``::
sage: G = PermutationGroup([[(1,2,3,4), (5,6)], [(1,2)]])
sage: g = G.gens()
sage: g[0]
(1,2)
sage: g[1]
(1,2,3,4)(5,6)
TESTS:
We make sure that the trivial group gets handled correctly::
sage: SymmetricGroup(1).gens()
[()]
"""
return self._gens
def gens_small(self):
"""
For this group, returns a generating set which has few elements.
As neither irredundancy nor minimal length is proven, it is fast.
EXAMPLES::
sage: R = "(25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24)" ## R = right
sage: U = "( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19)" ## U = top
sage: L = "( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35)" ## L = left
sage: F = "(17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11)" ## F = front
sage: B = "(33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27)" ## B = back or rear
sage: D = "(41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40)" ## D = down or bottom
sage: G = PermutationGroup([R,L,U,F,B,D])
sage: len(G.gens_small())
2
The output may be unpredictable, due to the use of randomized
algorithms in GAP. Note that both the following answers are equally valid.
::
sage: G = PermutationGroup([[('a','b')], [('b', 'c')], [('a', 'c')]])
sage: G.gens_small() # random
[('b','c'), ('a','c','b')] ## (on 64-bit Linux)
[('a','b'), ('a','c','b')] ## (on Solaris)
sage: len(G.gens_small()) == 2
True
"""
gens = self._gap_().SmallGeneratingSet()
return [self._element_class()(x, self, check=False) for x in gens]
def gen(self, i=None):
r"""
Returns the i-th generator of ``self``; that is, the i-th element of
the list ``self.gens()``.
The argument `i` may be omitted if there is only one generator (but
this will raise an error otherwise).
EXAMPLES:
We explicitly construct the alternating group on four
elements::
sage: A4 = PermutationGroup([[(1,2,3)],[(2,3,4)]]); A4
Permutation Group with generators [(2,3,4), (1,2,3)]
sage: A4.gens()
[(2,3,4), (1,2,3)]
sage: A4.gen(0)
(2,3,4)
sage: A4.gen(1)
(1,2,3)
sage: A4.gens()[0]; A4.gens()[1]
(2,3,4)
(1,2,3)
sage: P1 = PermutationGroup([[(1,2)]]); P1.gen()
(1,2)
"""
gens = self.gens()
if i is None:
if len(gens) == 1:
return gens[0]
else:
raise ValueError, "You must specify which generator you want"
else:
return gens[i]
def identity(self):
"""
Return the identity element of this group.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3),(4,5)]])
sage: e = G.identity()
sage: e
()
sage: g = G.gen(0)
sage: g*e
(1,2,3)(4,5)
sage: e*g
(1,2,3)(4,5)
sage: S = SymmetricGroup(['a','b','c'])
sage: S.identity()
()
"""
return self._element_class()([], self, check=True)
def exponent(self):
"""
Computes the exponent of the group. The exponent `e` of a
group `G` is the LCM of the orders of its elements, that
is, `e` is the smallest integer such that `g^e=1`
for all `g \in G`.
EXAMPLES::
sage: G = AlternatingGroup(4)
sage: G.exponent()
6
"""
return Integer(self._gap_().Exponent())
def largest_moved_point(self):
"""
Return the largest point moved by a permutation in this group.
EXAMPLES::
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]])
sage: G.largest_moved_point()
4
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
sage: G.largest_moved_point()
10
::
sage: G = PermutationGroup([[('a','b','c'),('d','e')]])
sage: G.largest_moved_point()
'e'
.. warning::
The name of this function is not good; this function
should be deprecated in term of degree::
sage: P = PermutationGroup([[1,2,3,4]])
sage: P.largest_moved_point()
4
sage: P.cardinality()
1
"""
try:
return self._domain_from_gap[Integer(self._gap_().LargestMovedPoint())]
except KeyError:
return self.degree()
def degree(self):
"""
Returns the degree of this permutation group.
EXAMPLES::
sage: S = SymmetricGroup(['a','b','c'])
sage: S.degree()
3
sage: G = PermutationGroup([(1,3),(4,5)])
sage: G.degree()
5
Note that you can explicitly specify the domain to get a
permutation group of smaller degree::
sage: G = PermutationGroup([(1,3),(4,5)], domain=[1,3,4,5])
sage: G.degree()
4
"""
return Integer(len(self._domain))
def domain(self):
r"""
Returns the underlying set that this permutation group acts
on.
EXAMPLES::
sage: P = PermutationGroup([(1,2),(3,5)])
sage: P.domain()
{1, 2, 3, 4, 5}
sage: S = SymmetricGroup(['a', 'b', 'c'])
sage: S.domain()
{'a', 'b', 'c'}
"""
return self._domain
def _domain_gap(self, domain=None):
"""
Returns a GAP string representation of the underlying set
that this group acts on. See also :meth:`domain`.
EXAMPLES::
sage: P = PermutationGroup([(1,2),(3,5)])
sage: P._domain_gap()
'[1, 2, 3, 4, 5]'
"""
if domain is None:
return repr(range(1, self.degree()+1))
else:
try:
return repr([self._domain_to_gap[point] for point in domain])
except KeyError:
raise ValueError, "domain must be a subdomain of self.domain()"
@cached_method
def smallest_moved_point(self):
"""
Return the smallest point moved by a permutation in this group.
EXAMPLES::
sage: G = PermutationGroup([[(3,4)], [(2,3,4)]])
sage: G.smallest_moved_point()
2
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
sage: G.smallest_moved_point()
1
Note that this function uses the ordering from the domain::
sage: S = SymmetricGroup(['a','b','c'])
sage: S.smallest_moved_point()
'a'
"""
return self._domain_from_gap[Integer(self._gap_().SmallestMovedPoint())]
@cached_method
def orbits(self):
"""
Returns the orbits of the elements of the domain under the
group action.
EXAMPLES::
sage: G = PermutationGroup([ [(3,4)], [(1,3)] ])
sage: G.orbits()
[[1, 3, 4], [2]]
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
sage: G.orbits()
[[1, 2, 3, 4, 10], [5], [6], [7], [8], [9]]
sage: G = PermutationGroup([ [('c','d')], [('a','c')],[('b',)]])
sage: G.orbits()
[['a', 'c', 'd'], ['b']]
The answer is cached::
sage: G.orbits() is G.orbits()
True
AUTHORS:
- Nathan Dunfield
"""
return [[self._domain_from_gap[x] for x in orbit] for orbit in
self._gap_().Orbits(self._domain_gap()).sage()]
@cached_method
def orbit(self, point):
"""
Return the orbit of the given point under the group action.
EXAMPLES::
sage: G = PermutationGroup([ [(3,4)], [(1,3)] ])
sage: G.orbit(3)
[3, 4, 1]
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
sage: G.orbit(3)
[3, 4, 10, 1, 2]
sage: G = PermutationGroup([ [('c','d')], [('a','c')] ])
sage: G.orbit('a')
['a', 'c', 'd']
"""
point = self._domain_to_gap[point]
return [self._domain_from_gap[x] for x in self._gap_().Orbit(point).sage()]
def transversals(self, point):
"""
If G is a permutation group acting on the set `X = \{1, 2, ...., n\}`
and H is the stabilizer subgroup of <integer>, a right
(respectively left) transversal is a set containing exactly
one element from each right (respectively left) coset of H. This
method returns a right transversal of ``self`` by the stabilizer
of ``self`` on <integer> position.
EXAMPLES::
sage: G = PermutationGroup([ [(3,4)], [(1,3)] ])
sage: G.transversals(1)
[(), (1,3,4), (1,4,3)]
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
sage: G.transversals(1)
[(), (1,2)(3,4), (1,3,2,10,4), (1,4,2,10,3), (1,10,4,3,2)]
sage: G = PermutationGroup([ [('c','d')], [('a','c')] ])
sage: G.transversals('a')
[(), ('a','c','d'), ('a','d','c')]
"""
G = self._gap_()
return [self(G.RepresentativeAction(self._domain_to_gap[point], self._domain_to_gap[i]))
for i in self.orbit(point)]
def stabilizer(self, point):
"""
Return the subgroup of ``self`` which stabilize the given position.
``self`` and its stabilizers must have same degree.
EXAMPLES::
sage: G = PermutationGroup([ [(3,4)], [(1,3)] ])
sage: G.stabilizer(1)
Subgroup of (Permutation Group with generators [(3,4), (1,3)]) generated by [(3,4)]
sage: G.stabilizer(3)
Subgroup of (Permutation Group with generators [(3,4), (1,3)]) generated by [(1,4)]
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
sage: G.stabilizer(10)
Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4,10)]) generated by [(2,3,4), (1,2)(3,4)]
sage: G.stabilizer(1)
Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4,10)]) generated by [(2,3)(4,10), (2,10,4)]
sage: G = PermutationGroup([[(2,3,4)],[(6,7)]])
sage: G.stabilizer(1)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(6,7), (2,3,4)]
sage: G.stabilizer(2)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(6,7)]
sage: G.stabilizer(3)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(6,7)]
sage: G.stabilizer(4)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(6,7)]
sage: G.stabilizer(5)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(6,7), (2,3,4)]
sage: G.stabilizer(6)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(2,3,4)]
sage: G.stabilizer(7)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(2,3,4)]
sage: G.stabilizer(8)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(6,7), (2,3,4)]
"""
try:
position = self._domain_to_gap[point]
except KeyError:
return self.subgroup(gens=self.gens())
return self.subgroup(gap_group=gap.Stabilizer(self, point))
def base(self, seed=None):
r"""
Returns a (minimum) base of this permutation group. A base $B$
of a permutation group is a subset of the domain of the group
such that the only group element stabilizing all of $B$ is the
identity.
The argument `seed` is optional and must be a subset of the domain
of `base`. When used, an attempt to create a base containing all or part
of `seed` will be made.
EXAMPLES::
sage: G = PermutationGroup([(1,2,3),(6,7,8)])
sage: G.base()
[1, 6]
sage: G.base([2])
[2, 6]
sage: H = PermutationGroup([('a','b','c'),('a','y')])
sage: H.base()
['a', 'b', 'c']
sage: S = SymmetricGroup(13)
sage: S.base()
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
sage: S = MathieuGroup(12)
sage: S.base()
[1, 2, 3, 4, 5]
sage: S.base([1,3,5,7,9,11]) # create a base for M12 with only odd integers
[1, 3, 5, 7, 9]
"""
if seed is None:
seed = self.domain()
try:
seed = [self._domain_to_gap[point] for point in seed]
except KeyError:
raise ValueError, "seed must be a subset of self.domain()"
return [self._domain_from_gap[x] for x in self._gap_().StabChain(seed).BaseStabChain().sage()]
def strong_generating_system(self, base_of_group=None):
"""
Return a Strong Generating System of ``self`` according the given
base for the right action of ``self`` on itself.
``base_of_group`` is a list of the positions on which ``self`` acts,
in any order. The algorithm returns a list of transversals and each
transversal is a list of permutations. By default, ``base_of_group``
is ``[1, 2, 3, ..., d]`` where `d` is the degree of the group.
For ``base_of_group`` =
`[ \mathrm{pos}_1, \mathrm{pos}_2, \dots , \mathrm{pos}_d]`
let `G_i` be the subgroup of `G` = ``self`` which stabilizes
`\mathrm{pos}_1, \mathrm{pos}_2, \dots , \mathrm{pos}_i`, so
.. math::
G = G_0 \supset G_1 \supset G_2 \supset \dots \supset G_n = \{e\}
Then the algorithm returns `[ G_i.\mathrm{transversals}(\mathrm{pos}_{i+1})]_{1 \leq i \leq n}`
INPUT:
- ``base_of_group`` (optional) -- default: ``[1, 2, 3, ..., d]``
-- a list containing the integers
`1, 2, \dots , d` in any order (`d` is the degree of ``self``)
OUTPUT:
- A list of lists of permutations from the group, which form a strong
generating system.
TESTS::
sage: G = SymmetricGroup(10)
sage: H = PermutationGroup([G.random_element() for i in range(randrange(1,3,1))])
sage: prod(map(lambda x : len(x), H.strong_generating_system()),1) == H.cardinality()
True
EXAMPLES::
sage: G = PermutationGroup([[(7,8)],[(3,4)],[(4,5)]])
sage: G.strong_generating_system()
[[()], [()], [(), (3,4,5), (3,5)], [(), (4,5)], [()], [()], [(), (7,8)], [()]]
sage: G = PermutationGroup([[(1,2,3,4)],[(1,2)]])
sage: G.strong_generating_system()
[[(), (1,2)(3,4), (1,3)(2,4), (1,4)(2,3)], [(), (2,3,4), (2,4,3)], [(), (3,4)], [()]]
sage: G = PermutationGroup([[(1,2,3)],[(4,5,7)],[(1,4,6)]])
sage: G.strong_generating_system()
[[(), (1,2,3), (1,4,6), (1,3,2), (1,5,7,4,6), (1,6,4), (1,7,5,4,6)], [(), (2,6,3), (2,5,7,6,3), (2,3,6), (2,7,5,6,3), (2,4,7,6,3)], [(), (3,6,7), (3,5,6), (3,7,6), (3,4,7,5,6)], [(), (4,5)(6,7), (4,7)(5,6), (4,6)(5,7)], [(), (5,7,6), (5,6,7)], [()], [()]]
sage: G = PermutationGroup([[(1,2,3)],[(2,3,4)],[(3,4,5)]])
sage: G.strong_generating_system([5,4,3,2,1])
[[(), (1,5,3,4,2), (1,5,4,3,2), (1,5)(2,3), (1,5,2)], [(), (1,3)(2,4), (1,2)(3,4), (1,4)(2,3)], [(), (1,3,2), (1,2,3)], [()], [()]]
sage: G = PermutationGroup([[(3,4)]])
sage: G.strong_generating_system()
[[()], [()], [(), (3,4)], [()]]
sage: G.strong_generating_system(base_of_group=[3,1,2,4])
[[(), (3,4)], [()], [()], [()]]
sage: G = TransitiveGroup(12,17) # optional
sage: G.strong_generating_system() # optional
[[(), (1,4,11,2)(3,6,5,8)(7,10,9,12), (1,8,3,2)(4,11,10,9)(5,12,7,6), (1,7)(2,8)(3,9)(4,10)(5,11)(6,12), (1,12,7,2)(3,10,9,8)(4,11,6,5), (1,11)(2,8)(3,5)(4,10)(6,12)(7,9), (1,10,11,8)(2,3,12,5)(4,9,6,7), (1,3)(2,8)(4,10)(5,7)(6,12)(9,11), (1,2,3,8)(4,9,10,11)(5,6,7,12), (1,6,7,8)(2,3,4,9)(5,10,11,12), (1,5,9)(3,11,7), (1,9,5)(3,7,11)], [(), (2,6,10)(4,12,8), (2,10,6)(4,8,12)], [()], [()], [()], [()], [()], [()], [()], [()], [()], [()]]
"""
sgs = []
stab = self
if base_of_group is None:
base_of_group = self.domain()
for j in base_of_group:
sgs.append(stab.transversals(j))
stab = stab.stabilizer(j)
return sgs
def _repr_(self):
r"""
Returns a string describing ``self``.
EXAMPLES:
We explicitly construct the alternating group on four
elements. Note that the ``AlternatingGroup`` class has
its own representation string::
sage: A4 = PermutationGroup([[(1,2,3)],[(2,3,4)]]); A4
Permutation Group with generators [(2,3,4), (1,2,3)]
sage: A4._repr_()
'Permutation Group with generators [(2,3,4), (1,2,3)]'
sage: AlternatingGroup(4)._repr_()
'Alternating group of order 4!/2 as a permutation group'
"""
return "Permutation Group with generators %s"%self.gens()
def _latex_(self):
r"""
Method for describing ``self`` in LaTeX. Encapsulates
``self.gens()`` in angle brackets to denote that ``self``
is generated by these elements. Called by the
``latex()`` function.
EXAMPLES:
We explicitly construct the alternating group on four
elements::
sage: A4 = PermutationGroup([[(1,2,3)],[(2,3,4)]]); A4
Permutation Group with generators [(2,3,4), (1,2,3)]
sage: latex(A4)
\langle (2,3,4), (1,2,3) \rangle
sage: A4._latex_()
'\\langle (2,3,4), (1,2,3) \\rangle'
sage: S = SymmetricGroup(['a','b','c'])
sage: latex(S)
\langle (\verb|a|,\verb|b|,\verb|c|), (\verb|a|,\verb|b|) \rangle
"""
return '\\langle ' + \
', '.join([x._latex_() for x in self.gens()]) + ' \\rangle'
def _order(self):
"""
This handles a few special cases of computing the subgroup order much
faster than GAP.
This currently operates very quickly for stabilizer subgroups of
permutation groups, for one.
Will return None if the we could not easily compute it.
Author: Christopher Swenson
EXAMPLES::
sage: SymmetricGroup(10).stabilizer(4)._order()
362880
sage: SymmetricGroup(10).stabilizer(4).stabilizer(5)._order()
40320
sage: SymmetricGroup(200).stabilizer(100)._order() == factorial(199) # this should be very fast
True
TESTS::
sage: [SymmetricGroup(n).stabilizer(1)._gap_().Size() for n in [4..10]]
[6, 24, 120, 720, 5040, 40320, 362880]
sage: [SymmetricGroup(n).stabilizer(1)._order() for n in [4..10]]
[6, 24, 120, 720, 5040, 40320, 362880]
"""
gens = self.gens()
if not gens or len(gens) < 2:
return None
for g in gens:
if g.order() != 2:
return None
if len(g.cycle_tuples()) != 1:
return None
g0 = gens[0].cycle_tuples()[0]
g1 = gens[1].cycle_tuples()[0]
a, b = g0
if a not in g1 and b not in g1:
return None
if a in g1:
elem = a
else:
elem = b
unique = set()
for g in gens:
a, b = g.cycle_tuples()[0]
if a != elem and b != elem:
return None
unique.add(a)
unique.add(b)
return factorial(len(unique))
def order(self):
"""
Return the number of elements of this group.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
sage: G.order()
12
sage: G = PermutationGroup([()])
sage: G.order()
1
sage: G = PermutationGroup([])
sage: G.order()
1
"""
if not self.gens() or self.gens() == [self(1)]:
return Integer(1)
subgroup_order = self._order()
if subgroup_order is not None:
return subgroup_order
return Integer(self._gap_().Size())
def random_element(self):
"""
Return a random element of this group.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
sage: a = G.random_element()
sage: a in G
True
sage: a.parent() is G
True
sage: a^6
()
"""
current_randstate().set_seed_gap()
return self(self._gap_().Random(), check=False)
def group_id(self):
"""
Return the ID code of this group, which is a list of two integers.
Requires "optional" database_gap-4.4.x package.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
sage: G.group_id() # optional - database_gap
[12, 4]
"""
return [Integer(n) for n in self._gap_().IdGroup()]
def id(self):
"""
(Same as ``self.group_id()``.) Return the ID code of this group, which
is a list of two integers. Requires "optional" database_gap-4.4.x
package.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
sage: G.group_id() # optional - database_gap
[12, 4]
"""
return self.group_id()
def center(self):
"""
Return the subgroup of elements that commute with every element
of this group.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3,4)]])
sage: G.center()
Subgroup of (Permutation Group with generators [(1,2,3,4)]) generated by [(1,2,3,4)]
sage: G = PermutationGroup([[(1,2,3,4)], [(1,2)]])
sage: G.center()
Subgroup of (Permutation Group with generators [(1,2), (1,2,3,4)]) generated by [()]
"""
return self.subgroup(gap_group=self._gap_().Center())
def socle(self):
r"""
Returns the socle of ``self``. The socle of a group $G$ is
the subgroup generated by all minimal normal subgroups.
EXAMPLES::
sage: G=SymmetricGroup(4)
sage: G.socle()
Subgroup of (Symmetric group of order 4! as a permutation group) generated by [(1,2)(3,4), (1,4)(2,3)]
sage: G.socle().socle()
Subgroup of (Subgroup of (Symmetric group of order 4! as a permutation group) generated by [(1,2)(3,4), (1,4)(2,3)]) generated by [(1,3)(2,4), (1,4)(2,3)]
"""
return self.subgroup(gap_group=self._gap_().Socle())
def frattini_subgroup(self):
r"""
Returns the Frattini subgroup of ``self``. The Frattini
subgroup of a group $G$ is the intersection of all
maximal subgroups of $G$.
EXAMPLES::
sage: G=PermutationGroup([[(1,2,3,4)],[(2,4)]])
sage: G.frattini_subgroup()
Subgroup of (Permutation Group with generators [(2,4), (1,2,3,4)]) generated by [(1,3)(2,4)]
sage: G=SymmetricGroup(4)
sage: G.frattini_subgroup()
Subgroup of (Symmetric group of order 4! as a permutation group) generated by [()]
"""
return self.subgroup(gap_group=self._gap_().FrattiniSubgroup())
def fitting_subgroup(self):
r"""
Returns the Fitting subgroup of ``self``. The Fitting
subgroup of a group $G$ is the largest nilpotent normal
subgroup of $G$.
EXAMPLES::
sage: G=PermutationGroup([[(1,2,3,4)],[(2,4)]])
sage: G.fitting_subgroup()
Subgroup of (Permutation Group with generators [(2,4), (1,2,3,4)]) generated by [(2,4), (1,2,3,4), (1,3)]
sage: G=PermutationGroup([[(1,2,3,4)],[(1,2)]])
sage: G.fitting_subgroup()
Subgroup of (Permutation Group with generators [(1,2), (1,2,3,4)]) generated by [(1,2)(3,4), (1,3)(2,4)]
"""
return self.subgroup(gap_group=self._gap_().FittingSubgroup())
def solvable_radical(self):
r"""
Returns the solvable radical of ``self``. The solvable
radical (or just radical) of a group $G$ is the largest
solvable normal subgroup of $G$.
EXAMPLES::
sage: G=SymmetricGroup(4)
sage: G.solvable_radical()
Subgroup of (Symmetric group of order 4! as a permutation group) generated by [(1,2), (1,2,3,4)]
sage: G=SymmetricGroup(5)
sage: G.solvable_radical()
Subgroup of (Symmetric group of order 5! as a permutation group) generated by [()]
"""
return self.subgroup(gap_group=self._gap_().RadicalGroup())
def intersection(self, other):
r"""
Returns the permutation group that is the intersection of
``self`` and ``other``.
INPUT:
- ``other`` - a permutation group.
OUTPUT:
A permutation group that is the set-theoretic intersection of ``self``
with ``other``. The groups are viewed as subgroups of a symmetric
group big enough to contain both group's symbol sets. So there is
no strict notion of the two groups being subgroups of a common parent.
EXAMPLES::
sage: H = DihedralGroup(4)
sage: K = CyclicPermutationGroup(4)
sage: H.intersection(K)
Permutation Group with generators [(1,2,3,4)]
sage: L = DihedralGroup(5)
sage: H.intersection(L)
Permutation Group with generators [(1,4)(2,3)]
sage: M = PermutationGroup(["()"])
sage: H.intersection(M)
Permutation Group with generators [()]
Some basic properties. ::
sage: H = DihedralGroup(4)
sage: L = DihedralGroup(5)
sage: H.intersection(L) == L.intersection(H)
True
sage: H.intersection(H) == H
True
The group ``other`` is verified as such. ::
sage: H = DihedralGroup(4)
sage: H.intersection('junk')
Traceback (most recent call last):
...
TypeError: junk is not a permutation group
"""
from sage.categories.finite_permutation_groups import FinitePermutationGroups
if other not in FinitePermutationGroups():
raise TypeError("{0} is not a permutation group".format(other))
return PermutationGroup(gap_group=gap.Intersection(self, other))
def conjugate(self, g):
r"""
Returns the group formed by conjugating ``self`` with ``g``.
INPUT:
- ``g`` - a permutation group element, or an object that converts
to a permutation group element, such as a list of integers or
a string of cycles.
OUTPUT:
If ``self`` is the group denoted by `H`, then this method computes
the group
.. math::
g^{-1}Hg = \{g^{-1}hg\vert h\in H\}
which is the group `H` conjugated by `g`.
There are no restrictions on ``self`` and ``g`` belonging to
a common permutation group, and correspondingly, there is no
relationship (such as a common parent) between ``self`` and the
output group.
EXAMPLES::
sage: G = DihedralGroup(6)
sage: a = PermutationGroupElement("(1,2,3,4)")
sage: G.conjugate(a)
Permutation Group with generators [(1,4)(2,6)(3,5), (1,5,6,2,3,4)]
The element performing the conjugation can be specified in
several ways. ::
sage: G = DihedralGroup(6)
sage: strng = "(1,2,3,4)"
sage: G.conjugate(strng)
Permutation Group with generators [(1,4)(2,6)(3,5), (1,5,6,2,3,4)]
sage: G = DihedralGroup(6)
sage: lst = [2,3,4,1]
sage: G.conjugate(lst)
Permutation Group with generators [(1,4)(2,6)(3,5), (1,5,6,2,3,4)]
sage: G = DihedralGroup(6)
sage: cycles = [(1,2,3,4)]
sage: G.conjugate(cycles)
Permutation Group with generators [(1,4)(2,6)(3,5), (1,5,6,2,3,4)]
Conjugation is a group automorphism, so conjugate groups
will be isomorphic. ::
sage: G = DiCyclicGroup(6)
sage: G.degree()
11
sage: cycle = [i+1 for i in range(1,11)] + [1]
sage: C = G.conjugate(cycle)
sage: G.is_isomorphic(C)
True
The conjugating element may be from a symmetric group with
larger degree than the group being conjugated. ::
sage: G = AlternatingGroup(5)
sage: G.degree()
5
sage: g = "(1,3)(5,6,7)"
sage: H = G.conjugate(g); H
Permutation Group with generators [(1,4,6,3,2), (1,4,6)]
sage: H.degree()
6
The conjugating element is checked. ::
sage: G = SymmetricGroup(3)
sage: G.conjugate("junk")
Traceback (most recent call last):
...
TypeError: junk does not convert to a permutation group element
"""
try:
g = PermutationGroupElement(g)
except:
raise TypeError("{0} does not convert to a permutation group element".format(g))
return PermutationGroup(gap_group=gap.ConjugateGroup(self, g))
def direct_product(self, other, maps=True):
"""
Wraps GAP's ``DirectProduct``, ``Embedding``, and ``Projection``.
Sage calls GAP's ``DirectProduct``, which chooses an efficient
representation for the direct product. The direct product of
permutation groups will be a permutation group again. For a direct
product ``D``, the GAP operation ``Embedding(D,i)`` returns the
homomorphism embedding the i-th factor into ``D``. The GAP operation
``Projection(D,i)`` gives the projection of ``D`` onto the i-th factor.
This method returns a 5-tuple: a permutation group and 4 morphisms.
INPUT:
- ``self, other`` - permutation groups
OUTPUT:
- ``D`` - a direct product of the inputs, returned as
a permutation group as well
- ``iota1`` - an embedding of ``self`` into ``D``
- ``iota2`` - an embedding of ``other`` into ``D``
- ``pr1`` - the projection of ``D`` onto ``self`` (giving a
splitting 1 - other - D - self - 1)
- ``pr2`` - the projection of ``D`` onto ``other`` (giving a
splitting 1 - self - D - other - 1)
EXAMPLES::
sage: G = CyclicPermutationGroup(4)
sage: D = G.direct_product(G,False)
sage: D
Permutation Group with generators [(5,6,7,8), (1,2,3,4)]
sage: D,iota1,iota2,pr1,pr2 = G.direct_product(G)
sage: D; iota1; iota2; pr1; pr2
Permutation Group with generators [(5,6,7,8), (1,2,3,4)]
Permutation group morphism:
From: Cyclic group of order 4 as a permutation group
To: Permutation Group with generators [(5,6,7,8), (1,2,3,4)]
Defn: Embedding( Group( [ (1,2,3,4), (5,6,7,8) ] ), 1 )
Permutation group morphism:
From: Cyclic group of order 4 as a permutation group
To: Permutation Group with generators [(5,6,7,8), (1,2,3,4)]
Defn: Embedding( Group( [ (1,2,3,4), (5,6,7,8) ] ), 2 )
Permutation group morphism:
From: Permutation Group with generators [(5,6,7,8), (1,2,3,4)]
To: Cyclic group of order 4 as a permutation group
Defn: Projection( Group( [ (1,2,3,4), (5,6,7,8) ] ), 1 )
Permutation group morphism:
From: Permutation Group with generators [(5,6,7,8), (1,2,3,4)]
To: Cyclic group of order 4 as a permutation group
Defn: Projection( Group( [ (1,2,3,4), (5,6,7,8) ] ), 2 )
sage: g=D([(1,3),(2,4)]); g
(1,3)(2,4)
sage: d=D([(1,4,3,2),(5,7),(6,8)]); d
(1,4,3,2)(5,7)(6,8)
sage: iota1(g); iota2(g); pr1(d); pr2(d)
(1,3)(2,4)
(5,7)(6,8)
(1,4,3,2)
(1,3)(2,4)
"""
G = self._gap_().DirectProduct(other)
D = PermutationGroup(gap_group=G)
if not maps:
return D
else:
from sage.groups.perm_gps.permgroup_morphism import PermutationGroupMorphism_from_gap
iota1 = PermutationGroupMorphism_from_gap(self, D, G.Embedding(1))
iota2 = PermutationGroupMorphism_from_gap(other, D, G.Embedding(2))
pr1 = PermutationGroupMorphism_from_gap(D, self, G.Projection(1))
pr2 = PermutationGroupMorphism_from_gap(D, other, G.Projection(2))
return D, iota1, iota2, pr1, pr2
def subgroup(self, gens=None, gap_group=None, domain=None, category=None, canonicalize=True, check=True):
"""
Wraps the ``PermutationGroup_subgroup`` constructor. The argument
``gens`` is a list of elements of ``self``.
EXAMPLES::
sage: G = PermutationGroup([(1,2,3),(3,4,5)])
sage: g = G((1,2,3))
sage: G.subgroup([g])
Subgroup of (Permutation Group with generators [(3,4,5), (1,2,3)]) generated by [(1,2,3)]
"""
return PermutationGroup_subgroup(self, gens=gens, gap_group=gap_group, domain=None,
category=category, canonicalize=canonicalize, check=check)
def quotient(self, N):
"""
Returns the quotient of this permutation group by the normal
subgroup `N`, as a permutation group.
Wraps the GAP operator "/".
EXAMPLES::
sage: G = PermutationGroup([(1,2,3), (2,3)])
sage: N = PermutationGroup([(1,2,3)])
sage: G.quotient(N)
Permutation Group with generators [(1,2)]
sage: G.quotient(G)
Permutation Group with generators [()]
"""
Q = self._gap_() / N._gap_()
phi = Q.RegularActionHomomorphism()
return PermutationGroup(gap_group=phi.Image())
def quotient_group(self, N):
"""
This function has been deprecated and will be removed in a
future version of Sage; use ``quotient`` instead.
Original docstring follows.
Returns the quotient of this permutation group by the normal
subgroup `N`.
Wraps the GAP operator "/".
TESTS::
sage: G = PermutationGroup([(1,2,3), (2,3)])
sage: N = PermutationGroup([(1,2,3)])
sage: G.quotient_group(N)
doctest:...: DeprecationWarning: quotient_group() is deprecated; use quotient() instead.
Permutation Group with generators [(1,2)]
"""
from sage.misc.misc import deprecation
deprecation('quotient_group() is deprecated; use quotient() instead.')
return self.quotient(N)
def commutator(self, other=None):
r"""
Returns the commutator subgroup of a group, or of a pair of groups.
INPUT:
- ``other`` - default: ``None`` - a permutation group.
OUTPUT:
Let $G$ denote ``self``. If ``other`` is ``None`` then this method
returns the subgroup of $G$ generated by the set of commutators,
.. math::
\{[g_1,g_2]\vert g_1, g_2\in G\} = \{g_1^{-1}g_2^{-1}g_1g_2\vert g_1, g_2\in G\}
Let $H$ denote ``other``, in the case that it is not ``None``. Then
this method returns the group generated by the set of commutators,
.. math::
\{[g,h]\vert g\in G\, h\in H\} = \{g^{-1}h^{-1}gh\vert g\in G\, h\in H\}
The two groups need only be permutation groups, there is no notion
of requiring them to explicitly be subgroups of some other group.
.. note::
For the identical statement, the generators of the returned
group can vary from one execution to the next.
EXAMPLES::
sage: G = DiCyclicGroup(4)
sage: G.commutator()
Permutation Group with generators [(1,3,5,7)(2,4,6,8)(9,11,13,15)(10,12,14,16)]
sage: G = SymmetricGroup(5)
sage: H = CyclicPermutationGroup(5)
sage: C = G.commutator(H)
sage: C.is_isomorphic(AlternatingGroup(5))
True
An abelian group will have a trivial commutator. ::
sage: G = CyclicPermutationGroup(10)
sage: G.commutator()
Permutation Group with generators [()]
The quotient of a group by its commutator is always abelian. ::
sage: G = DihedralGroup(20)
sage: C = G.commutator()
sage: Q = G.quotient(C)
sage: Q.is_abelian()
True
When forming commutators from two groups, the order of the
groups does not matter. ::
sage: D = DihedralGroup(3)
sage: S = SymmetricGroup(2)
sage: C1 = D.commutator(S); C1
Permutation Group with generators [(1,2,3)]
sage: C2 = S.commutator(D); C2
Permutation Group with generators [(1,3,2)]
sage: C1 == C2
True
This method calls two different functions in GAP, so
this tests that their results are consistent. The
commutator groups may have different generators, but the
groups are equal. ::
sage: G = DiCyclicGroup(3)
sage: C = G.commutator(); C
Permutation Group with generators [(5,7,6)]
sage: CC = G.commutator(G); CC
Permutation Group with generators [(5,6,7)]
sage: C == CC
True
The second group is checked. ::
sage: G = SymmetricGroup(2)
sage: G.commutator('junk')
Traceback (most recent call last):
...
TypeError: junk is not a permutation group
"""
if other is None:
return PermutationGroup(gap_group=gap.DerivedSubgroup(self))
else:
from sage.categories.finite_permutation_groups import FinitePermutationGroups
if other not in FinitePermutationGroups():
raise TypeError("{0} is not a permutation group".format(other))
return PermutationGroup(gap_group=gap.CommutatorSubgroup(self, other))
@hap_decorator
def cohomology(self, n, p = 0):
r"""
Computes the group cohomology `H^n(G, F)`, where `F = \ZZ`
if `p=0` and `F = \ZZ / p \ZZ` if `p > 0` is a prime.
Wraps HAP's ``GroupHomology`` function, written by Graham Ellis.
REQUIRES: GAP package HAP (in gap_packages-\*.spkg).
EXAMPLES::
sage: G = SymmetricGroup(4)
sage: G.cohomology(1,2) # optional - gap_packages
Multiplicative Abelian Group isomorphic to C2
sage: G = SymmetricGroup(3)
sage: G.cohomology(5) # optional - gap_packages
Trivial Abelian Group
sage: G.cohomology(5,2) # optional - gap_packages
Multiplicative Abelian Group isomorphic to C2
sage: G.homology(5,3) # optional - gap_packages
Trivial Abelian Group
sage: G.homology(5,4) # optional - gap_packages
Traceback (most recent call last):
...
ValueError: p must be 0 or prime
This computes `H^4(S_3, \ZZ)` and
`H^4(S_3, \ZZ / 2 \ZZ)`, respectively.
AUTHORS:
- David Joyner and Graham Ellis
REFERENCES:
- G. Ellis, 'Computing group resolutions', J. Symbolic
Computation. Vol.38, (2004)1077-1118 (Available at
http://hamilton.nuigalway.ie/).
- D. Joyner, 'A primer on computational group homology and
cohomology', http://front.math.ucdavis.edu/0706.0549.
"""
if p == 0:
L = self._gap_().GroupCohomology(n).sage()
else:
L = self._gap_().GroupCohomology(n, p).sage()
return AbelianGroup(len(L), L)
@hap_decorator
def cohomology_part(self, n, p = 0):
"""
Computes the p-part of the group cohomology `H^n(G, F)`,
where `F = \ZZ` if `p=0` and `F = \ZZ / p \ZZ` if
`p > 0` is a prime. Wraps HAP's Homology function, written
by Graham Ellis, applied to the `p`-Sylow subgroup of
`G`.
REQUIRES: GAP package HAP (in gap_packages-\*.spkg).
EXAMPLES::
sage: G = SymmetricGroup(5)
sage: G.cohomology_part(7,2) # optional - gap_packages
Multiplicative Abelian Group isomorphic to C2 x C2 x C2
sage: G = SymmetricGroup(3)
sage: G.cohomology_part(2,3) # optional - gap_packages
Multiplicative Abelian Group isomorphic to C3
AUTHORS:
- David Joyner and Graham Ellis
"""
if p == 0:
return AbelianGroup(1, [1])
else:
G = self._gap_()
S = G.SylowSubgroup(p)
R = S.ResolutionFiniteGroup(n+1)
HR = R.HomToIntegers()
L = HR.Cohomology(n).sage()
return AbelianGroup(len(L), L)
@hap_decorator
def homology(self, n, p = 0):
r"""
Computes the group homology `H_n(G, F)`, where
`F = \ZZ` if `p=0` and `F = \ZZ / p \ZZ` if
`p > 0` is a prime. Wraps HAP's ``GroupHomology`` function,
written by Graham Ellis.
REQUIRES: GAP package HAP (in gap_packages-\*.spkg).
AUTHORS:
- David Joyner and Graham Ellis
The example below computes `H_7(S_5, \ZZ)`,
`H_7(S_5, \ZZ / 2 \ZZ)`,
`H_7(S_5, \ZZ / 3 \ZZ)`, and
`H_7(S_5, \ZZ / 5 \ZZ)`, respectively. To compute the
`2`-part of `H_7(S_5, \ZZ)`, use the ``homology_part``
function.
EXAMPLES::
sage: G = SymmetricGroup(5)
sage: G.homology(7) # optional - gap_packages
Multiplicative Abelian Group isomorphic to C2 x C2 x C4 x C3 x C5
sage: G.homology(7,2) # optional - gap_packages
Multiplicative Abelian Group isomorphic to C2 x C2 x C2 x C2 x C2
sage: G.homology(7,3) # optional - gap_packages
Multiplicative Abelian Group isomorphic to C3
sage: G.homology(7,5) # optional - gap_packages
Multiplicative Abelian Group isomorphic to C5
REFERENCES:
- G. Ellis, "Computing group resolutions", J. Symbolic
Computation. Vol.38, (2004)1077-1118 (Available at
http://hamilton.nuigalway.ie/.
- D. Joyner, "A primer on computational group homology and cohomology",
http://front.math.ucdavis.edu/0706.0549
"""
if p == 0:
L = self._gap_().GroupHomology(n).sage()
else:
L = self._gap_().GroupHomology(n, p).sage()
return AbelianGroup(len(L), L)
@hap_decorator
def homology_part(self, n, p = 0):
r"""
Computes the `p`-part of the group homology
`H_n(G, F)`, where `F = \ZZ` if `p=0` and
`F = \ZZ / p \ZZ` if `p > 0` is a prime. Wraps HAP's
``Homology`` function, written by Graham Ellis, applied to the
`p`-Sylow subgroup of `G`.
REQUIRES: GAP package HAP (in gap_packages-\*.spkg).
EXAMPLES::
sage: G = SymmetricGroup(5)
sage: G.homology_part(7,2) # optional - gap_packages
Multiplicative Abelian Group isomorphic to C2 x C2 x C2 x C2 x C4
AUTHORS:
- David Joyner and Graham Ellis
"""
if p == 0:
return AbelianGroup(1, [1])
else:
S = self._gap_().SylowSubgroup(p)
R = S.ResolutionFiniteGroup(n+1)
TR = R.TensorWithIntegers()
L = TR.Homology(n).sage()
return AbelianGroup(len(L), L)
def character_table(self):
r"""
Returns the matrix of values of the irreducible characters of a
permutation group `G` at the conjugacy classes of
`G`. The columns represent the conjugacy classes of
`G` and the rows represent the different irreducible
characters in the ordering given by GAP.
EXAMPLES::
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3)]])
sage: G.order()
12
sage: G.character_table()
[ 1 1 1 1]
[ 1 1 -zeta3 - 1 zeta3]
[ 1 1 zeta3 -zeta3 - 1]
[ 3 -1 0 0]
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3)]])
sage: CT = gap(G).CharacterTable()
Type ``print gap.eval("Display(%s)"%CT.name())`` to display this
nicely.
::
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]])
sage: G.order()
8
sage: G.character_table()
[ 1 1 1 1 1]
[ 1 -1 -1 1 1]
[ 1 -1 1 -1 1]
[ 1 1 -1 -1 1]
[ 2 0 0 0 -2]
sage: CT = gap(G).CharacterTable()
Again, type ``print gap.eval("Display(%s)"%CT.name())`` to display this
nicely.
::
sage: SymmetricGroup(2).character_table()
[ 1 -1]
[ 1 1]
sage: SymmetricGroup(3).character_table()
[ 1 -1 1]
[ 2 0 -1]
[ 1 1 1]
sage: SymmetricGroup(5).character_table()
[ 1 -1 1 1 -1 -1 1]
[ 4 -2 0 1 1 0 -1]
[ 5 -1 1 -1 -1 1 0]
[ 6 0 -2 0 0 0 1]
[ 5 1 1 -1 1 -1 0]
[ 4 2 0 1 -1 0 -1]
[ 1 1 1 1 1 1 1]
sage: list(AlternatingGroup(6).character_table())
[(1, 1, 1, 1, 1, 1, 1), (5, 1, 2, -1, -1, 0, 0), (5, 1, -1, 2, -1, 0, 0), (8, 0, -1, -1, 0, zeta5^3 + zeta5^2 + 1, -zeta5^3 - zeta5^2), (8, 0, -1, -1, 0, -zeta5^3 - zeta5^2, zeta5^3 + zeta5^2 + 1), (9, 1, 0, 0, 1, -1, -1), (10, -2, 1, 1, 0, 0, 0)]
Suppose that you have a class function `f(g)` on
`G` and you know the values `v_1, \ldots, v_n` on
the conjugacy class elements in
``conjugacy_classes_representatives(G)`` =
`[g_1, \ldots, g_n]`. Since the irreducible characters
`\rho_1, \ldots, \rho_n` of `G` form an
`E`-basis of the space of all class functions (`E`
a "sufficiently large" cyclotomic field), such a class function is
a linear combination of these basis elements,
`f = c_1 \rho_1 + \cdots + c_n \rho_n`. To find
the coefficients `c_i`, you simply solve the linear system
``character_table_values(G)`` `[v_1, ..., v_n] = [c_1, ..., c_n]`,
where `[v_1, \ldots, v_n]` = ``character_table_values(G)`` `^{(-1)}[c_1, ..., c_n]`.
AUTHORS:
- David Joyner and William Stein (2006-01-04)
"""
G = self._gap_()
cl = G.ConjugacyClasses()
n = Integer(cl.Length())
irrG = G.Irr()
ct = [[irrG[i+1, j+1] for j in range(n)] for i in range(n)]
from sage.rings.all import CyclotomicField
e = irrG.Flat().Conductor()
K = CyclotomicField(e)
ct = [[K(x) for x in v] for v in ct]
from sage.matrix.all import MatrixSpace
MS = MatrixSpace(K, n)
return MS(ct)
def irreducible_characters(self):
r"""
Returns a list of the irreducible characters of ``self``.
EXAMPLES::
sage: irr = SymmetricGroup(3).irreducible_characters()
sage: [x.values() for x in irr]
[[1, -1, 1], [2, 0, -1], [1, 1, 1]]
"""
return [ClassFunction(self, irr) for irr in self._gap_().Irr()]
def trivial_character(self):
r"""
Returns the trivial character of ``self``.
EXAMPLES::
sage: SymmetricGroup(3).trivial_character()
Character of Symmetric group of order 3! as a permutation group
"""
values = [1]*self._gap_().NrConjugacyClasses().sage()
return self.character(values)
def character(self, values):
r"""
Returns a group character from ``values``, where ``values`` is
a list of the values of the character evaluated on the conjugacy
classes.
EXAMPLES::
sage: G = AlternatingGroup(4)
sage: n = len(G.conjugacy_classes_representatives())
sage: G.character([1]*n)
Character of Alternating group of order 4!/2 as a permutation group
"""
return ClassFunction(self, values)
def conjugacy_classes_representatives(self):
"""
Returns a complete list of representatives of conjugacy classes in
a permutation group `G`. The ordering is that given by GAP.
EXAMPLES::
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]])
sage: cl = G.conjugacy_classes_representatives(); cl
[(), (2,4), (1,2)(3,4), (1,2,3,4), (1,3)(2,4)]
sage: cl[3] in G
True
::
sage: G = SymmetricGroup(5)
sage: G.conjugacy_classes_representatives()
[(), (1,2), (1,2)(3,4), (1,2,3), (1,2,3)(4,5), (1,2,3,4), (1,2,3,4,5)]
::
sage: S = SymmetricGroup(['a','b','c'])
sage: S.conjugacy_classes_representatives()
[(), ('a','b'), ('a','b','c')]
AUTHORS:
- David Joyner and William Stein (2006-01-04)
"""
cl = self._gap_().ConjugacyClasses()
return [self(rep.Representative(), check=False) for rep in cl]
def conjugacy_classes_subgroups(self):
"""
Returns a complete list of representatives of conjugacy classes of
subgroups in a permutation group `G`. The ordering is that given by
GAP.
EXAMPLES::
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]])
sage: cl = G.conjugacy_classes_subgroups()
sage: cl
[Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [()], Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(1,2)(3,4)], Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(1,3)(2,4)], Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(2,4)], Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(1,2)(3,4), (1,4)(2,3)], Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(2,4), (1,3)(2,4)], Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(1,2,3,4), (1,3)(2,4)], Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(1,2)(3,4), (1,2,3,4), (1,3)(2,4)]]
::
sage: G = SymmetricGroup(3)
sage: G.conjugacy_classes_subgroups()
[Subgroup of (Symmetric group of order 3! as a permutation group) generated by [()], Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(2,3)], Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(1,2,3)], Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(1,2), (1,3,2)]]
AUTHORS:
- David Joyner (2006-10)
"""
cl = self._gap_().ConjugacyClassesSubgroups()
return [self.subgroup(gap_group=sub.Representative()) for sub in cl]
def subgroups(self):
r"""
Returns a list of all the subgroups of ``self``.
OUTPUT:
Each possible subgroup of ``self`` is contained once
in the returned list. The list is in order, according
to the size of the subgroups, from the trivial subgroup
with one element on through up to the whole group.
Conjugacy classes of subgroups are contiguous in the list.
.. warning::
For even relatively small groups this method can
take a very long time to execute, or create vast
amounts of output. Likely both. Its purpose is
instructional, as it can be useful for studying
small groups. The 156 subgroups of the full
symmetric group on 5 symbols of order 120, `S_5`,
can be computed in about a minute on commodity hardware
in 2011. The 64 subgroups of the cyclic group of order
`30030 = 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13` takes
about twice as long.
For faster results, which still exhibit the structure of
the possible subgroups, use
:meth:`conjugacy_classes_subgroups`.
EXAMPLES::
sage: G = SymmetricGroup(3)
sage: G.subgroups()
[Permutation Group with generators [()],
Permutation Group with generators [(2,3)],
Permutation Group with generators [(1,2)],
Permutation Group with generators [(1,3)],
Permutation Group with generators [(1,2,3)],
Permutation Group with generators [(1,2), (1,3,2)]]
sage: G = CyclicPermutationGroup(14)
sage: G.subgroups()
[Permutation Group with generators [()],
Permutation Group with generators [(1,8)(2,9)(3,10)(4,11)(5,12)(6,13)(7,14)],
Permutation Group with generators [(1,3,5,7,9,11,13)(2,4,6,8,10,12,14)],
Permutation Group with generators [(1,2,3,4,5,6,7,8,9,10,11,12,13,14)]]
AUTHOR:
- Rob Beezer (2011-01-24)
"""
all_sg = []
ccs = self._gap_().ConjugacyClassesSubgroups()
for cc in ccs:
for h in cc.Elements():
all_sg.append(PermutationGroup(gap_group=h))
return all_sg
def cosets(self, S, side='right'):
r"""
Returns a list of the cosets of ``S`` in ``self``.
INPUT:
- ``S`` - a subgroup of ``self``. An error is raised
if ``S`` is not a subgroup.
- ``side`` - default: 'right' - determines if right cosets or
left cosets are returned. ``side`` refers to where the
representative is placed in the products forming the cosets
and thus allowable values are only 'right' and 'left'.
OUTPUT:
A list of lists. Each inner list is a coset of the subgroup
in the group. The first element of each coset is the smallest
element (based on the ordering of the elements of ``self``)
of all the group elements that have not yet appeared in a
previous coset. The elements of each coset are in the same
order as the subgroup elements used to build the coset's
elements.
As a consequence, the subgroup itself is the first coset,
and its first element is the identity element. For each coset,
the first element listed is the element used as a representative
to build the coset. These representatives form an increasing
sequence across the list of cosets, and within a coset the
representative is the smallest element of its coset (both
orderings are based on of the ordering of elements of ``self``).
In the case of a normal subgroup, left and right cosets should
appear in the same order as part of the outer list. However,
the list of the elements of a particular coset may be in a
different order for the right coset versus the order in the
left coset. So, if you check to see if a subgroup is normal,
it is necessary to sort each individual coset first (but not
the list of cosets, due to the ordering of the representatives).
See below for examples of this.
.. note::
This is a naive implementation intended for instructional
purposes, and hence is slow for larger groups. Sage and GAP
provide more sophisticated functions for working quickly with
cosets of larger groups.
EXAMPLES:
The default is to build right cosets. This example works with
the symmetry group of an 8-gon and a normal subgroup.
Notice that a straight check on the equality of the output
is not sufficient to check normality, while sorting the
individual cosets is sufficient to then simply test equality of
the list of lists. Study the second coset in each list to understand the
need for sorting the elements of the cosets. ::
sage: G = DihedralGroup(8)
sage: quarter_turn = G.list()[5]; quarter_turn
(1,3,5,7)(2,4,6,8)
sage: S = G.subgroup([quarter_turn])
sage: rc = G.cosets(S); rc
[[(), (1,3,5,7)(2,4,6,8), (1,5)(2,6)(3,7)(4,8), (1,7,5,3)(2,8,6,4)],
[(2,8)(3,7)(4,6), (1,7)(2,6)(3,5), (1,5)(2,4)(6,8), (1,3)(4,8)(5,7)],
[(1,2)(3,8)(4,7)(5,6), (1,8)(2,7)(3,6)(4,5), (1,6)(2,5)(3,4)(7,8), (1,4)(2,3)(5,8)(6,7)],
[(1,2,3,4,5,6,7,8), (1,4,7,2,5,8,3,6), (1,6,3,8,5,2,7,4), (1,8,7,6,5,4,3,2)]]
sage: lc = G.cosets(S, side='left'); lc
[[(), (1,3,5,7)(2,4,6,8), (1,5)(2,6)(3,7)(4,8), (1,7,5,3)(2,8,6,4)],
[(2,8)(3,7)(4,6), (1,3)(4,8)(5,7), (1,5)(2,4)(6,8), (1,7)(2,6)(3,5)],
[(1,2)(3,8)(4,7)(5,6), (1,4)(2,3)(5,8)(6,7), (1,6)(2,5)(3,4)(7,8), (1,8)(2,7)(3,6)(4,5)],
[(1,2,3,4,5,6,7,8), (1,4,7,2,5,8,3,6), (1,6,3,8,5,2,7,4), (1,8,7,6,5,4,3,2)]]
sage: S.is_normal(G)
True
sage: rc == lc
False
sage: rc_sorted = [sorted(c) for c in rc]
sage: lc_sorted = [sorted(c) for c in lc]
sage: rc_sorted == lc_sorted
True
An example with the symmetry group of a regular
tetrahedron and a subgroup that is not normal.
Thus, the right and left cosets are different
(and so are the representatives). With each
individual coset sorted, a naive test of normality
is possible. ::
sage: A = AlternatingGroup(4)
sage: face_turn = A.list()[4]; face_turn
(1,2,3)
sage: stabilizer = A.subgroup([face_turn])
sage: rc = A.cosets(stabilizer, side='right'); rc
[[(), (1,2,3), (1,3,2)],
[(2,3,4), (1,3)(2,4), (1,4,2)],
[(2,4,3), (1,4,3), (1,2)(3,4)],
[(1,2,4), (1,4)(2,3), (1,3,4)]]
sage: lc = A.cosets(stabilizer, side='left'); lc
[[(), (1,2,3), (1,3,2)],
[(2,3,4), (1,2)(3,4), (1,3,4)],
[(2,4,3), (1,2,4), (1,3)(2,4)],
[(1,4,2), (1,4,3), (1,4)(2,3)]]
sage: stabilizer.is_normal(A)
False
sage: rc_sorted = [sorted(c) for c in rc]
sage: lc_sorted = [sorted(c) for c in lc]
sage: rc_sorted == lc_sorted
False
TESTS:
The keyword ``side`` is checked for the two possible values. ::
sage: G = SymmetricGroup(3)
sage: S = G.subgroup([G("(1,2)")])
sage: G.cosets(S, side='junk')
Traceback (most recent call last):
...
ValueError: side should be 'right' or 'left', not junk
The subgroup argument is checked to see if it is a permutation group.
Even a legitimate GAP object can be rejected. ::
sage: G=SymmetricGroup(3)
sage: G.cosets(gap(3))
Traceback (most recent call last):
...
TypeError: 3 is not a permutation group
The subgroup is verified as a subgroup of ``self``. ::
sage: A = AlternatingGroup(3)
sage: G = SymmetricGroup(3)
sage: S = G.subgroup([G("(1,2)")])
sage: A.cosets(S)
Traceback (most recent call last):
...
ValueError: Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(1,2)] is not a subgroup of Alternating group of order 3!/2 as a permutation group
AUTHOR:
- Rob Beezer (2011-01-31)
"""
from copy import copy
from sage.categories.finite_permutation_groups import FinitePermutationGroups
if not side in ['right','left']:
raise ValueError("side should be 'right' or 'left', not %s" % side)
if not S in FinitePermutationGroups():
raise TypeError("%s is not a permutation group" % S)
if not S.is_subgroup(self):
raise ValueError("%s is not a subgroup of %s" % (S, self))
group = copy(self.list())
group.sort()
subgroup = [self(s) for s in S.list()]
subgroup.sort()
decomposition = []
while group:
rep = group[0]
if side == 'right':
coset = [e*rep for e in subgroup]
if side == 'left':
coset = [rep*e for e in subgroup]
for e in coset:
group.remove(e)
decomposition.append(coset)
return decomposition
def normalizer(self, g):
"""
Returns the normalizer of ``g`` in ``self``.
EXAMPLES::
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]])
sage: g = G([(1,3)])
sage: G.normalizer(g)
Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(2,4), (1,3)]
sage: g = G([(1,2,3,4)])
sage: G.normalizer(g)
Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(2,4), (1,2,3,4), (1,3)(2,4)]
sage: H = G.subgroup([G([(1,2,3,4)])])
sage: G.normalizer(H)
Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(2,4), (1,2,3,4), (1,3)(2,4)]
"""
return self.subgroup(gap_group=self._gap_().Normalizer(g))
def centralizer(self, g):
"""
Returns the centralizer of ``g`` in ``self``.
EXAMPLES::
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]])
sage: g = G([(1,3)])
sage: G.centralizer(g)
Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(2,4), (1,3)]
sage: g = G([(1,2,3,4)])
sage: G.centralizer(g)
Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(1,2,3,4)]
sage: H = G.subgroup([G([(1,2,3,4)])])
sage: G.centralizer(H)
Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4)]) generated by [(1,2,3,4)]
"""
return self.subgroup(gap_group=self._gap_().Centralizer(g))
def isomorphism_type_info_simple_group(self):
"""
If the group is simple, then this returns the name of the group.
EXAMPLES::
sage: G = CyclicPermutationGroup(5)
sage: G.isomorphism_type_info_simple_group()
rec( series := "Z", parameter := 5, name := "Z(5)" )
TESTS: This shows that the issue at trac ticket 7360 is fixed::
sage: G = KleinFourGroup()
sage: G.is_simple()
False
sage: G.isomorphism_type_info_simple_group()
Traceback (most recent call last):
...
TypeError: Group must be simple.
"""
if self.is_simple():
info = self._gap_().IsomorphismTypeInfoFiniteSimpleGroup()
return info
else:
raise TypeError, "Group must be simple."
def is_abelian(self):
"""
Return ``True`` if this group is abelian.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: G.is_abelian()
False
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_abelian()
True
"""
return self._gap_().IsAbelian().bool()
def is_commutative(self):
"""
Return ``True`` if this group is commutative.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: G.is_commutative()
False
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_commutative()
True
"""
return self.is_abelian()
def is_cyclic(self):
"""
Return ``True`` if this group is cyclic.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: G.is_cyclic()
False
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_cyclic()
True
"""
return self._gap_().IsCyclic().bool()
def is_elementary_abelian(self):
"""
Return ``True`` if this group is elementary abelian. An elementary
abelian group is a finite abelian group, where every nontrivial
element has order `p`, where `p` is a prime.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: G.is_elementary_abelian()
False
sage: G = PermutationGroup(['(1,2,3)','(4,5,6)'])
sage: G.is_elementary_abelian()
True
"""
return self._gap_().IsElementaryAbelian().bool()
def isomorphism_to(self, right):
"""
Return an isomorphism from ``self`` to ``right`` if the groups
are isomorphic, otherwise ``None``.
INPUT:
- ``self`` - this group
- ``right`` - a permutation group
OUTPUT:
- ``None`` or a morphism of permutation groups.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: H = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.isomorphism_to(H) is None
True
sage: G = PermutationGroup([(1,2,3), (2,3)])
sage: H = PermutationGroup([(1,2,4), (1,4)])
sage: G.isomorphism_to(H) # not tested, see below
Permutation group morphism:
From: Permutation Group with generators [(2,3), (1,2,3)]
To: Permutation Group with generators [(1,2,4), (1,4)]
Defn: [(2,3), (1,2,3)] -> [(2,4), (1,2,4)]
TESTS:
Partial check that the output makes some sense::
sage: G.isomorphism_to(H)
Permutation group morphism:
From: Permutation Group with generators [(2,3), (1,2,3)]
To: Permutation Group with generators [(1,2,4), (1,4)]
Defn: [(2,3), (1,2,3)] -> [...]
"""
current_randstate().set_seed_gap()
if not isinstance(right, PermutationGroup_generic):
raise TypeError, "right must be a permutation group"
iso = self._gap_().IsomorphismGroups(right)
if str(iso) == "fail":
return None
dsts = [right(iso.Image(x), check=False) for x in self.gens()]
from permgroup_morphism import PermutationGroupMorphism_im_gens
return PermutationGroupMorphism_im_gens(self, right, dsts)
def is_isomorphic(self, right):
"""
Return ``True`` if the groups are isomorphic.
INPUT:
- ``self`` - this group
- ``right`` - a permutation group
OUTPUT:
- boolean; ``True`` if ``self`` and ``right`` are isomorphic groups;
``False`` otherwise.
EXAMPLES::
sage: v = ['(1,2,3)(4,5)', '(1,2,3,4,5)']
sage: G = PermutationGroup(v)
sage: H = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_isomorphic(H)
False
sage: G.is_isomorphic(G)
True
sage: G.is_isomorphic(PermutationGroup(list(reversed(v))))
True
"""
if not isinstance(right, PermutationGroup_generic):
raise TypeError, "right must be a permutation group"
iso = self._gap_().IsomorphismGroups(right)
return str(iso) != 'fail'
def is_monomial(self):
"""
Returns ``True`` if the group is monomial. A finite group is monomial
if every irreducible complex character is induced from a linear
character of a subgroup.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_monomial()
True
"""
return self._gap_().IsMonomialGroup().bool()
def is_nilpotent(self):
"""
Return ``True`` if this group is nilpotent.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: G.is_nilpotent()
False
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_nilpotent()
True
"""
return self._gap_().IsNilpotent().bool()
def is_normal(self, other):
"""
Return ``True`` if this group is a normal subgroup of ``other``.
EXAMPLES::
sage: AlternatingGroup(4).is_normal(SymmetricGroup(4))
True
sage: H = PermutationGroup(['(1,2,3)(4,5)'])
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: H.is_normal(G)
False
"""
if not(self.is_subgroup(other)):
raise TypeError("%s must be a subgroup of %s"%(self, other))
return other._gap_().IsNormal(self).bool()
def is_perfect(self):
"""
Return ``True`` if this group is perfect. A group is perfect if it
equals its derived subgroup.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: G.is_perfect()
False
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_perfect()
False
"""
return self._gap_().IsPerfectGroup().bool()
def is_pgroup(self):
"""
Returns ``True`` if this group is a `p`-group. A finite group is
a `p`-group if its order is of the form `p^n` for a prime integer
`p` and a nonnegative integer `n`.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3,4,5)'])
sage: G.is_pgroup()
True
"""
return self._gap_().IsPGroup().bool()
def is_polycyclic(self):
r"""
Return ``True`` if this group is polycyclic. A group is polycyclic if
it has a subnormal series with cyclic factors. (For finite groups,
this is the same as if the group is solvable - see
``is_solvable``.)
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: G.is_polycyclic()
False
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_polycyclic()
True
"""
return self._gap_().IsPolycyclicGroup().bool()
def is_simple(self):
"""
Returns ``True`` if the group is simple. A group is simple if it has no
proper normal subgroups.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_simple()
False
"""
return self._gap_().IsSimpleGroup().bool()
def is_solvable(self):
"""
Returns ``True`` if the group is solvable.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_solvable()
True
"""
return self._gap_().IsSolvableGroup().bool()
def is_subgroup(self, other):
"""
Returns ``True`` if ``self`` is a subgroup of ``other``.
EXAMPLES::
sage: G = AlternatingGroup(5)
sage: H = SymmetricGroup(5)
sage: G.is_subgroup(H)
True
"""
return all((x in other) for x in self.gens())
def is_supersolvable(self):
"""
Returns ``True`` if the group is supersolvable. A finite group is
supersolvable if it has a normal series with cyclic factors.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_supersolvable()
True
"""
return self._gap_().IsSupersolvableGroup().bool()
def non_fixed_points(self):
r"""
Returns the list of points not fixed by ``self``, i.e., the subset
of ``self.domain()`` moved by some element of ``self``.
EXAMPLES::
sage: G = PermutationGroup([[(3,4,5)],[(7,10)]])
sage: G.non_fixed_points()
[3, 4, 5, 7, 10]
sage: G = PermutationGroup([[(2,3,6)],[(9,)]]) # note: 9 is fixed
sage: G.non_fixed_points()
[2, 3, 6]
"""
pnts = set()
for gens in self.gens():
for cycles in gens.cycle_tuples():
for thispnt in cycles:
if thispnt not in pnts:
pnts.add(thispnt)
return sorted(pnts)
def fixed_points(self):
r"""
Returns the list of points fixed by ``self``, i.e., the subset
of ``.domain()`` not moved by any element of ``self``.
EXAMPLES::
sage: G=PermutationGroup([(1,2,3)])
sage: G.fixed_points()
[]
sage: G=PermutationGroup([(1,2,3),(5,6)])
sage: G.fixed_points()
[4]
sage: G=PermutationGroup([[(1,4,7)],[(4,3),(6,7)]])
sage: G.fixed_points()
[2, 5]
"""
non_fixed_points = self.non_fixed_points()
return [i for i in self.domain() if i not in non_fixed_points]
def is_transitive(self, domain=None):
"""
Returns ``True`` if ``self`` acts transitively on ``domain``.
A group $G$ acts transitively on set $S$ if for all $x,y\in S$
there is some $g\in G$ such that $x^g=y$.
EXAMPLES::
sage: G = SymmetricGroup(5)
sage: G.is_transitive()
True
sage: G = PermutationGroup(['(1,2)(3,4)(5,6)'])
sage: G.is_transitive()
False
::
sage: G = PermutationGroup([[(1,2,3,4,5)],[(1,2)]]) #S_5 on [1..5]
sage: G.is_transitive([1,4,5])
True
sage: G.is_transitive([2..6])
False
sage: G.is_transitive(G.non_fixed_points())
True
sage: H = PermutationGroup([[(1,2,3)],[(4,5,6)]])
sage: H.is_transitive(H.non_fixed_points())
False
Note that this differs from the definition in GAP, where
``IsTransitive`` returns whether the group is transitive on the
set of points moved by the group.
::
sage: G = PermutationGroup([(2,3)])
sage: G.is_transitive()
False
sage: gap(G).IsTransitive()
true
"""
try:
domain = self._domain_gap(domain)
except ValueError:
return False
return self._gap_().IsTransitive(domain).bool()
def is_primitive(self, domain=None):
r"""
Returns ``True`` if ``self`` acts primitively on ``domain``.
A group $G$ acts primitively on a set $S$ if
1. $G$ acts transitively on $S$ and
2. the action induces no non-trivial block system on $S$.
INPUT:
- ``domain`` (optional)
EXAMPLES:
By default, test for primitivity of ``self`` on its domain.
sage: G = PermutationGroup([[(1,2,3,4)],[(1,2)]])
sage: G.is_primitive()
True
sage: G = PermutationGroup([[(1,2,3,4)],[(2,4)]])
sage: G.is_primitive()
False
You can specify a domain on which to test primitivity::
sage: G = PermutationGroup([[(1,2,3,4)],[(2,4)]])
sage: G.is_primitive([1..4])
False
sage: G.is_primitive([1,2,3])
True
sage: G = PermutationGroup([[(3,4,5,6)],[(3,4)]]) #S_4 on [3..6]
sage: G.is_primitive(G.non_fixed_points())
True
"""
try:
domain = self._domain_gap(domain)
except ValueError:
return False
return self._gap_().IsPrimitive(domain).bool()
def is_semi_regular(self, domain=None):
r"""
Returns ``True`` if ``self`` acts semi-regularly on ``domain``.
A group $G$ acts semi-regularly on a set $S$ if the point
stabilizers of $S$ in $G$ are trivial.
``domain`` is optional and may take several forms. See examples.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3,4)]])
sage: G.is_semi_regular()
True
sage: G = PermutationGroup([[(1,2,3,4)],[(5,6)]])
sage: G.is_semi_regular()
False
You can pass in a domain to test semi-regularity::
sage: G = PermutationGroup([[(1,2,3,4)],[(5,6)]])
sage: G.is_semi_regular([1..4])
True
sage: G.is_semi_regular(G.non_fixed_points())
False
"""
try:
domain = self._domain_gap(domain)
except ValueError:
return False
return self._gap_().IsSemiRegular(domain).bool()
def is_regular(self, domain=None):
r"""
Returns ``True`` if ``self`` acts regularly on ``domain``.
A group $G$ acts regularly on a set $S$ if
1. $G$ acts transitively on $S$ and
2. $G$ acts semi-regularly on $S$.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3,4)]])
sage: G.is_regular()
True
sage: G = PermutationGroup([[(1,2,3,4)],[(5,6)]])
sage: G.is_regular()
False
You can pass in a domain on which to test regularity::
sage: G = PermutationGroup([[(1,2,3,4)],[(5,6)]])
sage: G.is_regular([1..4])
True
sage: G.is_regular(G.non_fixed_points())
False
"""
try:
domain = self._domain_gap(domain)
except ValueError:
return False
return self._gap_().IsRegular(domain).bool()
def normalizes(self, other):
r"""
Returns ``True`` if the group ``other`` is normalized by ``self``.
Wraps GAP's ``IsNormal`` function.
A group `G` normalizes a group `U` if and only if for every
`g \in G` and `u \in U` the element `u^g`
is a member of `U`. Note that `U` need not be a subgroup of `G`.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: H = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: H.normalizes(G)
False
sage: G = SymmetricGroup(3)
sage: H = PermutationGroup( [ (4,5,6) ] )
sage: G.normalizes(H)
True
sage: H.normalizes(G)
True
In the last example, `G` and `H` are disjoint, so each normalizes the
other.
"""
return self._gap_().IsNormal(other).bool()
def composition_series(self):
"""
Return the composition series of this group as a list of
permutation groups.
EXAMPLES:
These computations use pseudo-random numbers, so we set
the seed for reproducible testing.
::
sage: set_random_seed(0)
sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
sage: G.composition_series() # random output
[Permutation Group with generators [(1,2,3)(4,5), (3,4)], Permutation Group with generators [(1,5)(3,4), (1,5)(2,3), (1,5,4)], Permutation Group with generators [()]]
sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
sage: CS = G.composition_series()
sage: CS[3]
Subgroup of (Permutation Group with generators [(1,2), (1,2,3)(4,5)]) generated by [()]
"""
current_randstate().set_seed_gap()
CS = self._gap_().CompositionSeries()
return [self.subgroup(gap_group=group) for group in CS]
def derived_series(self):
"""
Return the derived series of this group as a list of permutation
groups.
EXAMPLES:
These computations use pseudo-random numbers, so we set
the seed for reproducible testing.
::
sage: set_random_seed(0)
sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
sage: G.derived_series() # random output
[Permutation Group with generators [(1,2,3)(4,5), (3,4)], Permutation Group with generators [(1,5)(3,4), (1,5)(2,4), (2,4)(3,5)]]
"""
current_randstate().set_seed_gap()
DS = self._gap_().DerivedSeries()
return [self.subgroup(gap_group=group) for group in DS]
def lower_central_series(self):
"""
Return the lower central series of this group as a list of
permutation groups.
EXAMPLES:
These computations use pseudo-random numbers, so we set
the seed for reproducible testing.
::
sage: set_random_seed(0)
sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
sage: G.lower_central_series() # random output
[Permutation Group with generators [(1,2,3)(4,5), (3,4)], Permutation Group with generators [(1,5)(3,4), (1,5)(2,3), (1,3)(2,4)]]
"""
current_randstate().set_seed_gap()
LCS = self._gap_().LowerCentralSeriesOfGroup()
return [self.subgroup(gap_group=group) for group in LCS]
def molien_series(self):
r"""
Returns the Molien series of a transitive permutation group. The
function
.. math::
M(x) = (1/|G|)\sum_{g\in G} \det(1-x*g)^{-1}
is sometimes called the "Molien series" of `G`. GAP's
``MolienSeries`` is associated to a character of a
group `G`. How are these related? A group `G`, given as a permutation
group on `n` points, has a "natural" representation of dimension `n`,
given by permutation matrices. The Molien series of `G` is the one
associated to that permutation representation of `G` using the above
formula. Character values then count fixed points of the
corresponding permutations.
EXAMPLES::
sage: G = SymmetricGroup(5)
sage: G.molien_series()
1/(-x^15 + x^14 + x^13 - x^10 - x^9 - x^8 + x^7 + x^6 + x^5 - x^2 - x + 1)
sage: G = SymmetricGroup(3)
sage: G.molien_series()
1/(-x^6 + x^5 + x^4 - x^2 - x + 1)
"""
pi = self._gap_().NaturalCharacter()
cc = pi.ConstituentsOfCharacter()
M = cc.Sum().MolienSeries()
R = QQ['x']
nn = M.NumeratorOfRationalFunction()
dd = M.DenominatorOfRationalFunction()
return (R(str(nn).replace("_1","")) /
R(str(dd).replace("_1","")))
def normal_subgroups(self):
"""
Return the normal subgroups of this group as a (sorted in
increasing order) list of permutation groups.
The normal subgroups of `H = PSL(2,7) \\times PSL(2,7)` are
`1`, two copies of `PSL(2,7)` and `H`
itself, as the following example shows.
EXAMPLES::
sage: G = PSL(2,7)
sage: D = G.direct_product(G)
sage: H = D[0]
sage: NH = H.normal_subgroups()
sage: len(NH)
4
sage: NH[1].is_isomorphic(G)
True
sage: NH[2].is_isomorphic(G)
True
"""
NS = self._gap_().NormalSubgroups()
return [self.subgroup(gap_group=group) for group in NS]
def poincare_series(self, p=2, n=10):
"""
Returns the Poincare series of `G \mod p` (`p \geq 2` must be a
prime), for `n` large. In other words, if you input a finite
group `G`, a prime `p`, and a positive integer `n`, it returns a
quotient of polynomials `f(x) = P(x) / Q(x)` whose coefficient of
`x^k` equals the rank of the vector space
`H_k(G, \ZZ / p \ZZ)`, for all `k` in the
range `1 \leq k \leq n`.
REQUIRES: GAP package HAP (in gap_packages-\*.spkg).
EXAMPLES::
sage: G = SymmetricGroup(5)
sage: G.poincare_series(2,10) # optional - gap_packages
(x^2 + 1)/(x^4 - x^3 - x + 1)
sage: G = SymmetricGroup(3)
sage: G.poincare_series(2,10) # optional - gap_packages
1/(-x + 1)
AUTHORS:
- David Joyner and Graham Ellis
"""
if not is_package_installed('gap_packages'):
raise RuntimeError, "You must install the optional gap_packages package."
load_hap()
from sage.rings.arith import is_prime
if not (p == 0 or is_prime(p)):
raise ValueError, "p must be 0 or prime"
ff = self._gap_().PoincareSeriesPrimePart(p, n)
R = QQ['x']
nn = ff.NumeratorOfRationalFunction()
dd = ff.DenominatorOfRationalFunction()
return (R(str(nn).replace('x_1', 'x')) /
R(str(dd).replace('x_1', 'x')))
def sylow_subgroup(self, p):
"""
Returns a Sylow `p`-subgroup of the finite group `G`, where `p` is a
prime. This is a `p`-subgroup of `G` whose index in `G` is coprime to
`p`. Wraps the GAP function ``SylowSubgroup``.
EXAMPLES::
sage: G = PermutationGroup(['(1,2,3)', '(2,3)'])
sage: G.sylow_subgroup(2)
Subgroup of (Permutation Group with generators [(2,3), (1,2,3)]) generated by [(2,3)]
sage: G.sylow_subgroup(5)
Subgroup of (Permutation Group with generators [(2,3), (1,2,3)]) generated by [()]
TESTS:
Implementation details should not prevent us from computing
large subgroups (trac #5491)::
sage: PSL(10,2).sylow_subgroup(7)
Subgroup of...
"""
return self.subgroup(gap_group=self._gap_().SylowSubgroup(p))
def upper_central_series(self):
"""
Return the upper central series of this group as a list of
permutation groups.
EXAMPLES:
These computations use pseudo-random numbers, so we set
the seed for reproducible testing::
sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
sage: G.upper_central_series()
[Subgroup of (Permutation Group with generators [(3,4), (1,2,3)(4,5)]) generated by [()]]
"""
current_randstate().set_seed_gap()
UCS = self._gap_().UpperCentralSeriesOfGroup()
return [self.subgroup(gap_group=group) for group in UCS]
class PermutationGroup_subgroup(PermutationGroup_generic):
"""
Subgroup subclass of ``PermutationGroup_generic``, so instance methods
are inherited.
EXAMPLES::
sage: G = CyclicPermutationGroup(4)
sage: gens = G.gens()
sage: H = DihedralGroup(4)
sage: H.subgroup(gens)
Subgroup of (Dihedral group of order 8 as a permutation group) generated by [(1,2,3,4)]
sage: K = H.subgroup(gens)
sage: K.list()
[(), (1,2,3,4), (1,3)(2,4), (1,4,3,2)]
sage: K.ambient_group()
Dihedral group of order 8 as a permutation group
sage: K.gens()
[(1,2,3,4)]
"""
def __init__(self, ambient, gens=None, gap_group=None, domain=None,
category=None, canonicalize=True, check=True):
r"""
Initialization method for the
``PermutationGroup_subgroup`` class.
INPUTS:
- ``ambient`` - the ambient group from which to construct this
subgroup
- ``gens`` - the generators of the subgroup
- ``from_group`` - ``True``: subgroup is generated from a Gap
string representation of the generators (default: ``False``)
- ``check`` - ``True``: checks if ``gens`` are indeed elements of the
ambient group
- ``canonicalize`` - boolean (default: ``True``); if ``True``, sort
generators and remove duplicates
EXAMPLES:
An example involving the dihedral group on four elements.
`D_8` contains a cyclic subgroup or order four::
sage: G = DihedralGroup(4)
sage: H = CyclicPermutationGroup(4)
sage: gens = H.gens(); gens
[(1,2,3,4)]
sage: S = G.subgroup(gens)
sage: S
Subgroup of (Dihedral group of order 8 as a permutation group) generated by [(1,2,3,4)]
sage: S.list()
[(), (1,2,3,4), (1,3)(2,4), (1,4,3,2)]
sage: S.ambient_group()
Dihedral group of order 8 as a permutation group
However, `D_8` does not contain a cyclic subgroup of order
three::
sage: G = DihedralGroup(4)
sage: H = CyclicPermutationGroup(3)
sage: gens = H.gens()
sage: S = PermutationGroup_subgroup(G,list(gens))
Traceback (most recent call last):
...
TypeError: each generator must be in the ambient group
"""
if not isinstance(ambient, PermutationGroup_generic):
raise TypeError, "ambient (=%s) must be perm group."%ambient
if domain is None:
domain = ambient.domain()
if category is None:
category = ambient.category()
PermutationGroup_generic.__init__(self, gens=gens, gap_group=gap_group, domain=domain,
category=category, canonicalize=canonicalize)
self._ambient_group = ambient
if check:
for g in self.gens():
if g not in ambient:
raise TypeError, "each generator must be in the ambient group"
def __cmp__(self, other):
r"""
Compare ``self`` and ``other``.
First, ``self`` and ``other`` are compared as permutation
groups, see :method:`PermutationGroup_generic.__cmp__`.
Second, if both are equal, the ambient groups are compared,
where (if necessary) ``other`` is considered a subgroup of
itself.
EXAMPLES::
sage: G=SymmetricGroup(6)
sage: G1=G.subgroup([G((1,2,3,4,5)),G((1,2))])
sage: G2=G.subgroup([G((1,2,3,4)),G((1,2))])
sage: K=G2.subgroup([G2((1,2,3))])
sage: H=G1.subgroup([G1(())])
``H`` is subgroup of ``K``, and therefore we have::
sage: H<K
True
sage: K<H
False
In the next example, both ``H`` and ``H2`` are trivial
groups, but the ambient group of ``H2`` is strictly contained
in the ambient group of ``H``, and thus we obtain::
sage: H2=G2.subgroup([G2(())])
sage: H2<H
True
Of course, ``G`` as a permutation group and ``G`` considered
as sub-group of itself are different objects. But they
compare equal, both when considered as permutation groups
or permutation subgroups::
sage: G3 = G.subgroup([G((1,2,3,4,5,6)),G((1,2))])
sage: G
Symmetric group of order 6! as a permutation group
sage: G3
Subgroup of (Symmetric group of order 6! as a permutation group) generated by [(1,2), (1,2,3,4,5,6)]
sage: G is G3
False
sage: G == G3 # as permutation groups
True
sage: G3 == G # as permutation subgroups
True
TESTS::
sage: G = SymmetricGroup(4)
sage: G.subgroup([G((1,2,3))]) == G.subgroup([G((2,3,1))])
True
sage: G.subgroup([G((1,2,3))]) == G.subgroup([G((1,3,2))])
True
"""
if self is other:
return 0
if not isinstance(other, PermutationGroup_generic):
return -1
c = PermutationGroup_generic.__cmp__(self, other)
if c:
return c
if hasattr(other, 'ambient_group'):
o_ambient = other.ambient_group()
else:
o_ambient = other
return cmp(self.ambient_group(), o_ambient)
def _repr_(self):
r"""
Returns a string representation / description of the permutation
subgroup.
EXAMPLES:
An example involving the dihedral group on four elements,
`D_8`::
sage: G = DihedralGroup(4)
sage: H = CyclicPermutationGroup(4)
sage: gens = H.gens()
sage: S = PermutationGroup_subgroup(G, list(gens))
sage: S
Subgroup of (Dihedral group of order 8 as a permutation group) generated by [(1,2,3,4)]
sage: S._repr_()
'Subgroup of (Dihedral group of order 8 as a permutation group) generated by [(1,2,3,4)]'
"""
s = "Subgroup of (%s) generated by %s"%(self.ambient_group(), self.gens())
return s
def _latex_(self):
r"""
Return LaTeX representation of this group.
EXAMPLES:
An example involving the dihedral group on four elements,
`D_8`::
sage: G = DihedralGroup(4)
sage: H = CyclicPermutationGroup(4)
sage: gens = H.gens()
sage: S = PermutationGroup_subgroup(G, list(gens))
sage: latex(S)
Subgroup of (Dihedral group of order 8 as a permutation group) generated by [(1,2,3,4)]
sage: S._latex_()
'Subgroup of (Dihedral group of order 8 as a permutation group) generated by [(1,2,3,4)]'
"""
return self._repr_()
def ambient_group(self):
"""
Return the ambient group related to ``self``.
EXAMPLES:
An example involving the dihedral group on four elements,
`D_8`::
sage: G = DihedralGroup(4)
sage: H = CyclicPermutationGroup(4)
sage: gens = H.gens()
sage: S = PermutationGroup_subgroup(G, list(gens))
sage: S.ambient_group()
Dihedral group of order 8 as a permutation group
sage: S.ambient_group() == G
True
"""
return self._ambient_group
def is_normal(self, other=None):
"""
Return ``True`` if this group is a normal subgroup of
``other``. If ``other`` is not specified, then it is assumed
to be the ambient group.
EXAMPLES::
sage: S = SymmetricGroup(['a','b','c'])
sage: H = S.subgroup([('a', 'b', 'c')]); H
Subgroup of (Symmetric group of order 3! as a permutation group) generated by [('a','b','c')]
sage: H.is_normal()
True
"""
if other is None:
other = self.ambient_group()
return PermutationGroup_generic.is_normal(self, other)
