Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
# -*- coding: utf-8 -*- 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.
Index of methods ----------------
Here are the method of a :func:`PermutationGroup`
{METHODS_OF_PermutationGroup_generic}
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. )
- Javier Lopez Pena (2013): Added conjugacy classes.
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.
""" #***************************************************************************** # Copyright (C) 2006 William Stein <wstein@gmail.com> # David Joyner <wdjoyner@gmail.com> # # Distributed under the terms of the GNU General Public License (GPL) # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import absolute_import from six.moves import range from six import integer_types
from functools import wraps
from sage.misc.randstate import current_randstate import sage.groups.old as group
from sage.rings.all import QQ, Integer from sage.interfaces.expect 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, PackageNotFoundError from sage.sets.finite_enumerated_set import FiniteEnumeratedSet from sage.categories.all import FiniteEnumeratedSets from sage.groups.conjugacy_classes import ConjugacyClassGAP from sage.structure.richcmp import (richcmp_method, richcmp_not_equal, richcmp, rich_to_bool, op_EQ)
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() # optional - gap_packages """ try: gap.load_package("hap") except Exception: gap.load_package("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 """ if not is_package_installed('gap_packages'): raise PackageNotFoundError("gap_packages") load_hap() from sage.arith.all 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)
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 """ else:
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 is a list of strings, each of which is a permutation of # integers in cycle notation. It may contain \n and spaces. for g in str(src).replace(" ","").replace("\n","")[1:-2].split("),")]
# src is a list of list of strings. Each string is a list of # integers separated by ',' for cycle in g]) for g in src]
# src is now a list of group elements
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)]
Permutation groups can work on any domain. In the following examples, the permutations are specified in list notation, according to the order of the elements of the domain::
sage: list(PermutationGroup([['b','c','a']], domain=['a','b','c'])) [(), ('a','b','c'), ('a','c','b')] sage: list(PermutationGroup([['b','c','a']], domain=['b','c','a'])) [()] sage: list(PermutationGroup([['b','c','a']], domain=['a','c','b'])) [(), ('a','b')]
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 """ return gens._permgroup_() canonicalize=canonicalize, category=category)
@richcmp_method class PermutationGroup_generic(group.FiniteGroup): """ A generic 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)] 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""" Initialize ``self``.
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 enumerated permutation groups sage: TestSuite(A4).run()
TESTS::
sage: TestSuite(PermutationGroup([[]])).run() sage: TestSuite(PermutationGroup([])).run() sage: TestSuite(PermutationGroup([(0,1)])).run() """ .or_subcategory(category) raise ValueError("you must specify gens or gap_group")
#Handle the case where only the GAP group is specified.
#Here we need to check if all of the points are integers #to make the domain contain all integers up to the max. #This is needed for backward compatibility
def construction(self): """ Return the construction of ``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') """ else: 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 """
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])])' """
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)>' """
def __richcmp__(self, right, op): """ 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 """
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``).
EXAMPLES::
sage: AlternatingGroup(17)._element_class() <type 'sage.groups.perm_gps.permgroup_element.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)] """
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 """ return x
def list(self): """ Return list of all elements of this group.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3,4)], [(1,2)]]) sage: G.list() [(), (1,2), (1,2,3,4), (1,3)(2,4), (1,3,4), (2,3,4), (1,4,3,2), (1,3,2,4), (1,3,4,2), (1,2,4,3), (1,4,2,3), (2,4,3), (1,4,3), (1,4)(2,3), (1,4,2), (1,3,2), (1,3), (3,4), (2,4), (1,4), (2,3), (1,2)(3,4), (1,2,3), (1,2,4)]
sage: G = PermutationGroup([[('a','b')]], domain=('a', 'b')); G Permutation Group with generators [('a','b')] sage: G.list() [(), ('a','b')]
TESTS:
Test :trac:`9155`::
sage: G = SymmetricGroup(2) sage: elements = G.list() sage: elements.remove(G("()")) sage: elements [(1,2)] sage: G.list() [(), (1,2)] """
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 """
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 """
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] [(), (1,2), (1,2,3), (2,3), (1,3,2), (1,3)]
Test that it is possible to iterate through moderately large groups (:trac:`18239`)::
sage: p = [(i,i+1) for i in range(1,601,2)] sage: q = [tuple(range(1+i,601,3)) for i in range(3)] sage: A = PermutationGroup([p,q]) sage: A.cardinality() 60000 sage: for x in A: # long time - 2 secs ....: pass # long time """ successors=lambda g: (g._mul_(h) for h in self.gens())))
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() [()] """
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 """
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) """ else: raise ValueError("You must specify which generator you want") else:
def ngens(self): """ Return the number of generators of ``self``.
EXAMPLES::
sage: A4 = PermutationGroup([[(1,2,3)], [(2,3,4)]]); A4 Permutation Group with generators [(2,3,4), (1,2,3)] sage: A4.ngens() 2 """
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() () """
def exponent(self): r""" 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
"""
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 """
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 """
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'} """
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]' """ else:
@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' """
def representative_action(self,x,y): r""" Return an element of self that maps `x` to `y` if it exists.
This method wraps the gap function ``RepresentativeAction``, which can also return elements that map a given set of points on another set of points.
INPUT:
- ``x,y`` -- two elements of the domain.
EXAMPLES::
sage: G = groups.permutation.Cyclic(14) sage: g = G.representative_action(1,10) sage: all(g(x) == 1+((x+9-1)%14) for x in G.domain()) True
TESTS::
sage: g = graphs.PetersenGraph() sage: g.relabel(list("abcdefghik")) sage: g.vertices() ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k'] sage: ag = g.automorphism_group() sage: a = ag.representative_action('a','b') sage: g == g.relabel(a,inplace=False) True sage: a('a') == 'b' True """ self._domain_to_gap[y])
@cached_method def orbits(self): """ Returns the orbits of the elements of the domain under the default 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 """ self._gap_().Orbits(self._domain_gap()).sage()]
@cached_method def orbit(self, point, action="OnPoints"): """ Return the orbit of a point under a group action.
INPUT:
- ``point`` -- can be a point or any of the list above, depending on the action to be considered.
- ``action`` -- string. if ``point`` is an element from the domain, a tuple of elements of the domain, a tuple of tuples [...], this variable describes how the group is acting.
The actions currently available through this method are ``"OnPoints"``, ``"OnTuples"``, ``"OnSets"``, ``"OnPairs"``, ``"OnSetsSets"``, ``"OnSetsDisjointSets"``, ``"OnSetsTuples"``, ``"OnTuplesSets"``, ``"OnTuplesTuples"``. They are taken from GAP's list of group actions, see ``gap.help('Group Actions')``.
It is set to ``"OnPoints"`` by default. See below for examples.
OUTPUT:
The orbit of ``point`` as a tuple. Each entry is an image under the action of the permutation group, if necessary converted to the corresponding container. That is, if ``action='OnSets'`` then each entry will be a set even if ``point`` was given by a list/tuple/iterable.
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')
Action of `S_3` on sets::
sage: S3 = groups.permutation.Symmetric(3) sage: S3.orbit((1,2), action = "OnSets") ({1, 2}, {2, 3}, {1, 3})
On tuples::
sage: S3.orbit((1,2), action = "OnTuples") ((1, 2), (2, 3), (2, 1), (3, 1), (1, 3), (3, 2))
Action of `S_4` on sets of disjoint sets::
sage: S4 = groups.permutation.Symmetric(4) sage: S4.orbit(((1,2),(3,4)), action = "OnSetsDisjointSets") ({{1, 2}, {3, 4}}, {{2, 3}, {1, 4}}, {{1, 3}, {2, 4}})
Action of `S_4` (on a nonstandard domain) on tuples of sets::
sage: S4 = PermutationGroup([ [('c','d')], [('a','c')], [('a','b')] ]) sage: S4.orbit((('a','c'),('b','d')),"OnTuplesSets") (({'a', 'c'}, {'b', 'd'}), ({'a', 'd'}, {'c', 'b'}), ({'c', 'b'}, {'a', 'd'}), ({'b', 'd'}, {'a', 'c'}), ({'c', 'd'}, {'a', 'b'}), ({'a', 'b'}, {'c', 'd'}))
Action of `S_4` (on a very nonstandard domain) on tuples of sets::
sage: S4 = PermutationGroup([ [((11,(12,13)),'d')], ....: [((12,(12,11)),(11,(12,13)))], [((12,(12,11)),'b')] ]) sage: S4.orbit((( (11,(12,13)), (12,(12,11))),('b','d')),"OnTuplesSets") (({(11, (12, 13)), (12, (12, 11))}, {'b', 'd'}), ({'d', (12, (12, 11))}, {(11, (12, 13)), 'b'}), ({(11, (12, 13)), 'b'}, {'d', (12, (12, 11))}), ({(11, (12, 13)), 'd'}, {'b', (12, (12, 11))}), ({'b', 'd'}, {(11, (12, 13)), (12, (12, 11))}), ({'b', (12, (12, 11))}, {(11, (12, 13)), 'd'})) """ "OnPoints" : [], "OnSets" : [Set], "OnPairs" : [tuple], "OnTuples" : [tuple], "OnSetsSets" : [Set, Set], "OnSetsDisjointSets" : [Set, Set], "OnSetsTuples" : [Set, tuple], "OnTuplesSets" : [tuple, Set], "OnTuplesTuples" : [tuple, tuple], }
except KeyError: raise ValueError('{0} is not part of the domain'.format(x))
else: except KeyError: raise NotImplementedError("This action is not implemented (yet?).")
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')] """ for i in self.orbit(point)]
def stabilizer(self, point, action="OnPoints"): """ Return the subgroup of ``self`` which stabilize the given position. ``self`` and its stabilizers must have same degree.
INPUT:
- ``point`` -- a point of the :meth:`domain`, or a set of points depending on the value of ``action``.
- ``action`` (string; default ``"OnPoints"``) -- should the group be considered to act on points (``action="OnPoints"``) or on sets of points (``action="OnSets"``) ? In the latter case, the first argument must be a subset of :meth:`domain`.
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)]
The stabilizer of a set of points::
sage: s10 = groups.permutation.Symmetric(10) sage: s10.stabilizer([1..3],"OnSets").cardinality() 30240 sage: factorial(3)*factorial(7) 30240
::
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) Traceback (most recent call last): ... ValueError: 8 does not belong to the domain
::
sage: G = PermutationGroup([ [('c','d')], [('a','c')] ], domain='abcd') sage: G.stabilizer('a') Subgroup of (Permutation Group with generators [('c','d'), ('a','c')]) generated by [('c','d')] sage: G.stabilizer('b') Subgroup of (Permutation Group with generators [('c','d'), ('a','c')]) generated by [('c','d'), ('a','c')] sage: G.stabilizer('c') Subgroup of (Permutation Group with generators [('c','d'), ('a','c')]) generated by [('a','d')] sage: G.stabilizer('d') Subgroup of (Permutation Group with generators [('c','d'), ('a','c')]) generated by [('a','c')]
TESTS::
sage: G.stabilizer(['a'],"OnMonkeys") Traceback (most recent call last): ... ValueError: 'action' must be equal to 'OnPoints' or to 'OnSets'. """ action != "OnSets"): else:
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] """
except KeyError: raise ValueError("seed must be a subset of self.domain()")
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.
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 - database_gap sage: G.strong_generating_system() # optional - database_gap [[(), (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)], [()], [()], [()], [()], [()], [()], [()], [()], [()], [()]]
TESTS::
sage: G = SymmetricGroup(10) sage: H = PermutationGroup([G.random_element() for i in range(randrange(1,3,1))]) sage: prod(len(x) for x in H.strong_generating_system()) == H.cardinality() True """
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' """
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 (\text{\texttt{a}},\text{\texttt{b}},\text{\texttt{c}}), (\text{\texttt{a}},\text{\texttt{b}}) \rangle """ ', '.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: G = SymmetricGroup(10).subgroup([(i, 10) for i in range(1, 10) if i != 4]) sage: G._order() 362880
TESTS::
sage: [SymmetricGroup(n).stabilizer(1)._gap_().Size() for n in [4..10]] [6, 24, 120, 720, 5040, 40320, 362880] sage: special_gens = [ ....: [(3,4), (2,4)], ....: [(4,5), (3,5), (2,5)], ....: [(5,6), (4,6), (3,6), (2,6)], ....: [(6,7), (5,7), (4,7), (3,7), (2,7)], ....: [(7,8), (6,8), (5,8), (4,8), (3,8), (2,8)], ....: [(8,9), (7,9), (6,9), (5,9), (4,9), (3,9), (2,9)], ....: [(9,10), (8,10), (7,10), (6,10), (5,10), (4,10), (3,10), (2,10)]] sage: [SymmetricGroup(n).subgroup(gen)._order() for gen in special_gens] [6, 24, 120, 720, 5040, 40320, 362880]
Checks that output is a Sage integer (:trac:`23778`)::
sage: P = PermutationGroup(['(1,2)','(1,3)']) sage: P.cardinality() 6 sage: isinstance(P.cardinality(), Integer) True """ # This special case only works with more than 1 generator. return None # Special case: certain subgroups of the symmetric group for which Gap reports # generators of the form ((1, 2), (1, 3), ...) # This means that this group is isomorphic to a smaller symmetric group # S_n, where n is the number of generators supported. # # The code that follows checks that the following assumptions hold: # * All generators are transpositions (i.e., permutations # that switch two elements and leave everything else fixed), # * All generators share a common element. # # We then know that this group is isomorphic to S_n, # and therefore its order is n!.
# Check that all generators are order 2 and have length-1 cycle tuples.
# Find the common element. else: # Count the number of unique elements in the generators.
# Compute the order.
def order(self): """ Return the number of elements of this group. See also: G.degree()
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
``cardinality`` is just an alias::
sage: PermutationGroup([(1,2,3)]).cardinality() 3 """
return Integer(1)
cardinality = order
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 () """
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] """ try: return [Integer(n) for n in self._gap_().IdGroup()] except RuntimeError: if not is_package_installed('database_gap'): raise PackageNotFoundError("database_gap") raise
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 group_primitive_id(self): """ Return the index of this group in the GAP database of primitive groups.
Requires "optional" database_gap-4.4.x package.
OUTPUT:
A positive integer, following GAP's conventions. A ``ValueError`` is raised if the group is not primitive.
EXAMPLES::
sage: G = PermutationGroup([[(1,2,3,4,5)], [(1,5),(2,4)]]) sage: G.group_primitive_id() # optional - database_gap 2 sage: G.degree() 5
From the information of the degree and the identification number, you can recover the isomorphism class of your group in the GAP database::
sage: H = PrimitiveGroup(5,2) # optional - database_gap sage: G == H # optional - database_gap False sage: G.is_isomorphic(H) # optional - database_gap True """ if not self.is_primitive(): raise ValueError('Group is not primitive')
try: return Integer(self._gap_().PrimitiveIdentification()) except RuntimeError: if not is_package_installed('database_gap'): raise PackageNotFoundError("database_gap") raise
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 [()] """
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,2)(3,4), (1,4)(2,3)] """
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 [()]
"""
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)]
"""
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 [()]
"""
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 """
def conjugacy_class(self, g): r""" Return the conjugacy class of ``g`` inside the group ``self``.
INPUT:
- ``g`` -- an element of the permutation group ``self``
OUTPUT:
The conjugacy class of ``g`` in the group ``self``. If ``self`` is the group denoted by `G`, this method computes the set `\{x^{-1}gx\ \vert\ x \in G \}`
EXAMPLES::
sage: G = DihedralGroup(3) sage: g = G.gen(0) sage: G.conjugacy_class(g) Conjugacy class of (1,2,3) in Dihedral group of order 6 as a permutation group """
def conjugacy_classes(self): r""" Return a list with all the conjugacy classes of ``self``.
EXAMPLES::
sage: G = DihedralGroup(3) sage: G.conjugacy_classes() [Conjugacy class of () in Dihedral group of order 6 as a permutation group, Conjugacy class of (2,3) in Dihedral group of order 6 as a permutation group, Conjugacy class of (1,2,3) in Dihedral group of order 6 as a permutation group] """
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 """
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) """ else:
def semidirect_product(self, N, mapping, check=True): r""" The semidirect product of ``self`` with ``N``.
INPUT:
- ``N`` - A group which is acted on by ``self`` and naturally embeds as a normal subgroup of the returned semidirect product.
- ``mapping`` - A pair of lists that together define a homomorphism, `\phi :` self `\rightarrow` Aut(N), by giving, in the second list, the images of the generators of ``self`` in the order given in the first list.
- ``check`` - A boolean that, if set to False, will skip the initial tests which are made on ``mapping``. This may be beneficial for large ``N``, since in such cases the injectivity test can be expensive. Set to True by default.
OUTPUT:
The semidirect product of ``self`` and ``N`` defined by the action of ``self`` on ``N`` given in ``mapping`` (note that a homomorphism from A to the automorphism group of B is equivalent to an action of A on the B's underlying set). The semidirect product of two groups, `H` and `N`, is a construct similar to the direct product in so far as the elements are the Cartesian product of the elements of `H` and the elements of `N`. The operation, however, is built upon an action of `H` on `N`, and is defined as such:
.. MATH::
(h_1,n_1)(h_2,n_2) = (h_{1}h_{2}, n_{1}^{h_2}n_2)
This function is a wrapper for GAP's ``SemidirectProduct`` command. The permutation group returned is built upon a permutation representation of the semidirect product of ``self`` and ``N`` on a set of size `\mid N \mid`. The generators of ``N`` are given as their right regular representations, while the generators of ``self`` are defined by the underlying action of ``self`` on ``N``. It should be noted that the defining action is not always faithful, and in this case the inputted representations of the generators of ``self`` are placed on additional letters and adjoined to the output's generators of ``self``.
EXAMPLES:
Perhaps the most common example of a semidirect product comes from the family of dihedral groups. Each dihedral group is the semidirect product of $C_2$ with $C_n$, where, by convention, $3 \leq n$. In this case, the nontrivial element of $C_2$ acts on $C_n$ so as to send each element to its inverse. ::
sage: C2 = CyclicPermutationGroup(2) sage: C8 = CyclicPermutationGroup(8) sage: alpha = PermutationGroupMorphism_im_gens(C8,C8,[(1,8,7,6,5,4,3,2)]) sage: S = C2.semidirect_product(C8,[[(1,2)],[alpha]]) sage: S == DihedralGroup(8) False sage: S.is_isomorphic(DihedralGroup(8)) True sage: S.gens() [(3,4,5,6,7,8,9,10), (1,2)(4,10)(5,9)(6,8)]
A more complicated example can be drawn from [TW1980]_. It is there given that a semidirect product of $D_4$ and $C_3$ is isomorphic to one of $C_2$ and the dicyclic group of order 12. This nonabelian group of order 24 has very similar structure to the dicyclic and dihedral groups of order 24, the three being the only groups of order 24 with a two-element center and 9 conjugacy classes. ::
sage: D4 = DihedralGroup(4) sage: C3 = CyclicPermutationGroup(3) sage: alpha1 = PermutationGroupMorphism_im_gens(C3,C3,[(1,3,2)]) sage: alpha2 = PermutationGroupMorphism_im_gens(C3,C3,[(1,2,3)]) sage: S1 = D4.semidirect_product(C3,[[(1,2,3,4),(1,3)],[alpha1,alpha2]]) sage: C2 = CyclicPermutationGroup(2) sage: Q = DiCyclicGroup(3) sage: a = Q.gens()[0]; b=Q.gens()[1].inverse() sage: alpha = PermutationGroupMorphism_im_gens(Q,Q,[a,b]) sage: S2 = C2.semidirect_product(Q,[[(1,2)],[alpha]]) sage: S1.is_isomorphic(S2) True sage: S1.is_isomorphic(DihedralGroup(12)) False sage: S1.is_isomorphic(DiCyclicGroup(6)) False sage: S1.center() Subgroup of (Permutation Group with generators [(5,6,7), (1,2,3,4)(6,7), (1,3)]) generated by [(1,3)(2,4)] sage: len(S1.conjugacy_classes_representatives()) 9
If your normal subgroup is large, and you are confident that your inputs will successfully create a semidirect product, then it is beneficial, for the sake of time efficiency, to set the ``check`` parameter to ``False``. ::
sage: C2 = CyclicPermutationGroup(2) sage: C2000 = CyclicPermutationGroup(500) sage: alpha = PermutationGroupMorphism(C2000,C2000,[C2000.gen().inverse()]) sage: S = C2.semidirect_product(C2000,[[(1,2)],[alpha]],check=False)
TESTS::
sage: C3 = CyclicPermutationGroup(3) sage: D4 = DihedralGroup(4) sage: alpha = PermutationGroupMorphism(C3,C3,[C3("(1,3,2)")]) sage: alpha1 = PermutationGroupMorphism(C3,C3,[C3("(1,2,3)")])
sage: s = D4.semidirect_product('junk', [[(1,2,3,4),(1,2)], [alpha, alpha1]]) Traceback (most recent call last): ... TypeError: junk is not a permutation group
sage: s = D4.semidirect_product(C3, [[(1,2,3,4),(1,2)], [alpha, alpha1]]) Traceback (most recent call last): ... ValueError: the generator list must generate the calling group, [(1, 2, 3, 4), (1, 2)] does not generate Dihedral group of order 8 as a permutation group
sage: s = D4.semidirect_product(C3, [[(1,2,3,4),(1,3)], [alpha]]) Traceback (most recent call last): ... ValueError: the list of generators and the list of morphisms must be of equal length
sage: alpha2 = PermutationGroupMorphism(C3, D4, [D4("()")]) sage: s = D4.semidirect_product(C3, [[(1,2,3,4),(1,3)], [alpha, alpha2]]) Traceback (most recent call last): ... ValueError: an element of the automorphism list is not an endomorphism (and is therefore not an automorphism)
sage: alpha3 = PermutationGroupMorphism(C3,C3,[C3("()")]) sage: s = D4.semidirect_product(C3, [[(1,2,3,4),(1,3)], [alpha, alpha3]]) Traceback (most recent call last): ... ValueError: an element of the automorphism list is not an injection (and is therefore not an automorphism)
AUTHOR:
- Kevin Halasz (2012-8-12)
"""
# create a parallel list of the automorphisms of N in GAP # create the necessary homomorphism from self into the # automorphism group of N in GAP
def holomorph(self): r""" The holomorph of a group as a permutation group.
The holomorph of a group `G` is the semidirect product `G \rtimes_{id} Aut(G)`, where `id` is the identity function on `Aut(G)`, the automorphism group of `G`.
See :wikipedia:`Holomorph (mathematics)`
OUTPUT:
Returns the holomorph of a given group as permutation group via a wrapping of GAP's semidirect product function.
EXAMPLES:
Thomas and Wood's 'Group Tables' (Shiva Publishing, 1980) tells us that the holomorph of `C_5` is the unique group of order 20 with a trivial center. ::
sage: C5 = CyclicPermutationGroup(5) sage: A = C5.holomorph() sage: A.order() 20 sage: A.is_abelian() False sage: A.center() Subgroup of (Permutation Group with generators [(5,6,7,8,9), (1,2,4,3)(6,7,9,8)]) generated by [()] sage: A Permutation Group with generators [(5,6,7,8,9), (1,2,4,3)(6,7,9,8)]
Noting that the automorphism group of `D_4` is itself `D_4`, it can easily be shown that the holomorph is indeed an internal semidirect product of these two groups. ::
sage: D4 = DihedralGroup(4) sage: H = D4.holomorph() sage: H.gens() [(3,8)(4,7), (2,3,5,8), (2,5)(3,8), (1,4,6,7)(2,3,5,8), (1,8)(2,7)(3,6)(4,5)] sage: G = H.subgroup([H.gens()[0],H.gens()[1],H.gens()[2]]) sage: N = H.subgroup([H.gens()[3],H.gens()[4]]) sage: N.is_normal(H) True sage: G.is_isomorphic(D4) True sage: N.is_isomorphic(D4) True sage: G.intersection(N) Permutation Group with generators [()] sage: L = [H(x)*H(y) for x in G for y in N]; L.sort() sage: L1 = H.list(); L1.sort() sage: L == L1 True
Author:
- Kevin Halasz (2012-08-14) """
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)] """ category=category, canonicalize=canonicalize, check=check)
def as_finitely_presented_group(self, reduced=False): """ Return a finitely presented group isomorphic to ``self``.
This method acts as wrapper for the GAP function ``IsomorphismFpGroupByGenerators``, which yields an isomorphism from a given group to a finitely presented group.
INPUT:
- ``reduced`` -- Default ``False``, if ``True`` :meth:`FinitelyPresentedGroup.simplified <sage.groups.finitely_presented.FinitelyPresentedGroup.simplified>` is called, attempting to simplify the presentation of the finitely presented group to be returned.
OUTPUT:
Finite presentation of self, obtained by taking the image of the isomorphism returned by the GAP function, ``IsomorphismFpGroupByGenerators``.
ALGORITHM:
Uses GAP.
EXAMPLES::
sage: CyclicPermutationGroup(50).as_finitely_presented_group() Finitely presented group < a | a^50 > sage: DihedralGroup(4).as_finitely_presented_group() Finitely presented group < a, b | b^2, a^4, (b*a)^2 > sage: GeneralDihedralGroup([2,2]).as_finitely_presented_group() Finitely presented group < a, b, c | a^2, b^2, c^2, (c*b)^2, (c*a)^2, (b*a)^2 >
GAP algorithm is not guaranteed to produce minimal or canonical presentation::
sage: G = PermutationGroup(['(1,2,3,4,5)', '(1,5)(2,4)']) sage: G.is_isomorphic(DihedralGroup(5)) True sage: K = G.as_finitely_presented_group(); K Finitely presented group < a, b | b^2, (b*a)^2, b*a^-3*b*a^2 > sage: K.as_permutation_group().is_isomorphic(DihedralGroup(5)) True
We can attempt to reduce the output presentation::
sage: PermutationGroup(['(1,2,3,4,5)','(1,3,5,2,4)']).as_finitely_presented_group() Finitely presented group < a, b | b^-2*a^-1, b*a^-2 > sage: PermutationGroup(['(1,2,3,4,5)','(1,3,5,2,4)']).as_finitely_presented_group(reduced=True) Finitely presented group < a | a^5 >
TESTS::
sage: PermutationGroup([]).as_finitely_presented_group() Finitely presented group < a | a > sage: S = SymmetricGroup(6) sage: perm_ls = [S.random_element() for i in range(3)] sage: G = PermutationGroup(perm_ls) sage: G.as_finitely_presented_group().as_permutation_group().is_isomorphic(G) True
`D_9` is the only non-Abelian group of order 18 with an automorphism group of order 54 [TW1980]_::
sage: D = DihedralGroup(9).as_finitely_presented_group().gap() sage: D.Order(), D.IsAbelian(), D.AutomorphismGroup().Order() (18, false, 54)
`S_3` is the only non-Abelian group of order 6 [TW1980]_::
sage: S = SymmetricGroup(3).as_finitely_presented_group().gap() sage: S.Order(), S.IsAbelian() (6, false)
We can manually construct a permutation representation using GAP coset enumeration methods::
sage: D = GeneralDihedralGroup([3,3,4]).as_finitely_presented_group().gap() sage: ctab = D.CosetTable(D.Subgroup([])) sage: gen_ls = gap.List(ctab, gap.PermList) sage: PermutationGroup(gen_ls).is_isomorphic(GeneralDihedralGroup([3,3,4])) True sage: A = AlternatingGroup(5).as_finitely_presented_group().gap() sage: ctab = A.CosetTable(A.Subgroup([])) sage: gen_ls = gap.List(ctab, gap.PermList) sage: PermutationGroup(gen_ls).is_isomorphic(AlternatingGroup(5)) True
AUTHORS:
- Davis Shurbert (2013-06-21): initial version """
# Convert GAP relators to Sage relators using the Tietze word of each defining relation. for rel_word in image_fp.RelatorsOfFpGroup()])
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 [()] """ # Return Q as a permutation group # This is currently done using the right regular representation # FIXME: GAP certainly knows of a better way!
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 """ else:
@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 -zeta3 - 1 zeta3 1] [ 1 zeta3 -zeta3 - 1 1] [ 3 0 0 -1] 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)
"""
# Finally return the result as a matrix.
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]] """
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 """
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 """
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) """
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 [(2,4), (1,2)(3,4), (1,4)(2,3)]]
::
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 [(2,3), (1,2,3)]]
AUTHORS:
- David Joyner (2006-10) """
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() [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)], Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(1,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 [(2,3), (1,2,3)]]
sage: G = CyclicPermutationGroup(14) sage: G.subgroups() [Subgroup of (Cyclic group of order 14 as a permutation group) generated by [()], Subgroup of (Cyclic group of order 14 as a permutation group) generated by [(1,8)(2,9)(3,10)(4,11)(5,12)(6,13)(7,14)], Subgroup of (Cyclic group of order 14 as a permutation group) generated by [(1,3,5,7,9,11,13)(2,4,6,8,10,12,14)], Subgroup of (Cyclic group of order 14 as a permutation group) generated by [(1,2,3,4,5,6,7,8,9,10,11,12,13,14)]]
AUTHOR:
- Rob Beezer (2011-01-24) """
@cached_method def _regular_subgroup_gap(self): r""" Return a conjugacy class of regular subgroups, if there is one, as a GAP element.
This allows finding such a group without constructing it in Sage. The result is cached, so constructing the obtained subgroup later is possible without recomputing it.
EXAMPLES:
The symmetric group on 4 elements has a regular subgroup::
sage: S4 = groups.permutation.Symmetric(4) sage: S4._regular_subgroup_gap() # random ConjugacyClassSubgroups(SymmetricGroup( [ 1 .. 4 ] ),Group( [ (1,4)(2,3), (1,3)(2,4) ] ))
""" First(ConjugacyClassesSubgroups(%s), x -> IsRegular(Representative(x), [1..%d])) """ % (self._gap_().name(), self.degree())) # prevent caching GAP fails
@cached_method def has_regular_subgroup(self, return_group = False): r""" Return whether the group contains a regular subgroup.
INPUT:
- ``return_group`` (boolean) -- If ``return_group = True``, a regular subgroup is returned if there is one, and ``None`` if there isn't. When ``return_group = False`` (default), only a boolean indicating whether such a group exists is returned instead.
EXAMPLES:
The symmetric group on 4 elements has a regular subgroup::
sage: S4 = groups.permutation.Symmetric(4) sage: S4.has_regular_subgroup() True sage: S4.has_regular_subgroup(return_group = True) # random Subgroup of (Symmetric group of order 4! as a permutation group) generated by [(1,3)(2,4), (1,4)(2,3)]
But the automorphism group of Petersen's graph does not::
sage: G = graphs.PetersenGraph().automorphism_group() sage: G.has_regular_subgroup() False
""" else: else:
def blocks_all(self, representatives = True): r""" Returns the list of block systems of imprimitivity.
For more information on primitivity, see the :wikipedia:`Wikipedia article on primitive group actions <Primitive_permutation_group>`.
INPUT:
- ``representative`` (boolean) -- whether to return all possible block systems of imprimitivity or only one of their representatives (the block can be obtained from its representative set `S` by computing the orbit of `S` under ``self``).
This parameter is set to ``True`` by default (as it is GAP's default behaviour).
OUTPUT:
This method returns a description of *all* block systems. Hence, the output is a "list of lists of lists" or a "list of lists" depending on the value of ``representatives``. A bit more clearly, output is :
* A list of length (#number of different block systems) of
* block systems, each of them being defined as
* If ``representatives = True`` : a list of representatives of each set of the block system
* If ``representatives = False`` : a partition of the elements defining an imprimitivity block.
.. SEEALSO::
- :meth:`~PermutationGroup_generic.is_primitive`
EXAMPLES:
Picking an interesting group::
sage: g = graphs.DodecahedralGraph() sage: g.is_vertex_transitive() True sage: ag = g.automorphism_group() sage: ag.is_primitive() False
Computing its blocks representatives::
sage: ag.blocks_all() [[0, 15]]
Now the full block::
sage: sorted(ag.blocks_all(representatives = False)[0]) [[0, 15], [1, 16], [2, 12], [3, 13], [4, 9], [5, 10], [6, 11], [7, 18], [8, 17], [14, 19]]
TESTS::
sage: g = PermutationGroup([("a","b","c","d")]) sage: g.blocks_all() [['a', 'c']] sage: g.blocks_all(False) [[['a', 'c'], ['b', 'd']]] """ for rep in ag.AllBlocks().sage()] else: for rep in ag.AllBlocks()]
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('(1,3,5,7)(2,4,6,8)'); 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('(1,2,3)'); 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) """
def minimal_generating_set(self): r""" Return a minimal generating set
EXAMPLES::
sage: g = graphs.CompleteGraph(4) sage: g.relabel(['a','b','c','d']) sage: mgs = g.automorphism_group().minimal_generating_set(); len(mgs) 2 sage: mgs # random [('b','d','c'), ('a','c','b','d')]
TESTS::
sage: PermutationGroup(["(1,2,3)(4,5,6)","(1,2,3,4,5,6)"]).minimal_generating_set() [(2,5)(3,6), (1,5,3,4,2,6)] """
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)] """
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)] """
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( name := "Z(5)", parameter := 5, series := "Z" )
TESTS:
This shows that the issue at :trac:`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. """ else:
###################### Boolean tests #####################
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 """
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 """
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 """
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 """
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)] -> [...] """ raise TypeError("right must be a permutation group")
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 """ raise TypeError("right must be a permutation group")
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 """
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 """
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 """ raise TypeError("%s must be a subgroup of %s"%(self, other))
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 """
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 """
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 """
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 """
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 """
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 """
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 """
def non_fixed_points(self): r""" Return 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] """
def fixed_points(self): r""" Return 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] """
def is_transitive(self, domain=None): r""" 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 """ #If the domain is not a subset of self.domain(), then the #action isn't transitive.
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)
.. SEEALSO::
- :meth:`~PermutationGroup_generic.blocks_all`
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
""" #If the domain is not a subset of self.domain(), then the #action isn't primitive. except ValueError: return False
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
""" except ValueError: return False
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
""" except ValueError: return False
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. """
############## Series ######################
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 [()] """
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)]] """
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)]] """
def molien_series(self): r""" Return the Molien series of a 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)
Some further tests (after :trac:`15817`)::
sage: G = PermutationGroup([[(1,2,3,4)]]) sage: S4ms = SymmetricGroup(4).molien_series() sage: G.molien_series() / S4ms x^5 + 2*x^4 + x^3 + x^2 + 1
This works for not-transitive groups::
sage: G = PermutationGroup([[(1,2)],[(3,4)]]) sage: G.molien_series() / S4ms x^4 + x^3 + 2*x^2 + x + 1
This works for groups with fixed points::
sage: G = PermutationGroup([[(2,)]]) sage: G.molien_series() 1/(x^2 - 2*x + 1) """ # because NaturalCharacter forgets about fixed points :
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 """
def poincare_series(self, p=2, n=10): r""" Return the Poincaré 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 PackageNotFoundError("gap_packages") load_hap() from sage.arith.all 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...
"""
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 [()]] """
from sage.groups.generic import structure_description
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.
INPUT:
- ``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 """ raise TypeError("ambient (=%s) must be perm group."%ambient) category=category, canonicalize=canonicalize)
def __richcmp__(self, other, op): r""" Compare ``self`` and ``other``.
First, ``self`` and ``other`` are compared as permutation groups, see :meth:`PermutationGroup_generic.__richcmp__`.
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
""" return rich_to_bool(op, 0)
else:
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)]' """
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) \hbox{Subgroup } \langle (1,2,3,4) \rangle \hbox{ of } \langle (1,2,3,4), (1,4)(2,3) \rangle sage: S._latex_() '\\hbox{Subgroup } \\langle (1,2,3,4) \\rangle \\hbox{ of } \\langle (1,2,3,4), (1,4)(2,3) \\rangle' """ ', '.join([x._latex_() for x in self.gens()]) + ' \\rangle' (gens, self.ambient_group()._latex_())
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 """
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
"""
from sage.misc.rest_index_of_methods import gen_rest_table_index __doc__ = __doc__.format(METHODS_OF_PermutationGroup_generic=gen_rest_table_index(PermutationGroup_generic)) |