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:
JOKE: Q: What’s hot, chunky, and acts on a polygon? A: Dihedral soup. Renteln, P. and Dundes, A. “Foolproof: A Sampling of Mathematical Folk Humor.” Notices Amer. Math. Soc. 52, 24-34, 2005.
AUTHORS:
REFERENCES:
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.
Return the permutation group associated to \(x\) (typically a list of generators).
INPUT:
OUTPUT:
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
Bases: sage.groups.old.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()
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:
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 [THOMAS-WOODS]:
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 [THOMAS-WOODS]:
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:
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]
Returns the list of block systems of imprimitivity.
For more information on primitivity, see the Wikipedia article on primitive group actions.
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 representative = True : a list of representatives of each set of the block system
- If representative = False : a partition of the elements defining an imprimitivity block.
See also
EXAMPLE:
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()
[[1, 16]]
Now the full blocks:
sage: ag.blocks_all(representatives = False)
[[[1, 16], [2, 17], [15, 20], [9, 18], [6, 11], [3, 13], [8, 19], [4, 14], [5, 10], [7, 12]]]
Return the number of elements of this group.
EXAMPLES:
sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
sage: G.order()
12
sage: G = PermutationGroup([()])
sage: G.order()
1
sage: G = PermutationGroup([])
sage: G.order()
1
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 [()]
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)]
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
Returns the matrix of values of the irreducible characters of a permutation group \(G\) at the conjugacy classes of \(G\). The columns represent the conjugacy classes of \(G\) and the rows represent the different irreducible characters in the ordering given by GAP.
EXAMPLES:
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3)]])
sage: G.order()
12
sage: G.character_table()
[ 1 1 1 1]
[ 1 1 -zeta3 - 1 zeta3]
[ 1 1 zeta3 -zeta3 - 1]
[ 3 -1 0 0]
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3)]])
sage: CT = gap(G).CharacterTable()
Type print gap.eval("Display(%s)"%CT.name()) to display this nicely.
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]])
sage: G.order()
8
sage: G.character_table()
[ 1 1 1 1 1]
[ 1 -1 -1 1 1]
[ 1 -1 1 -1 1]
[ 1 1 -1 -1 1]
[ 2 0 0 0 -2]
sage: CT = gap(G).CharacterTable()
Again, type print gap.eval("Display(%s)"%CT.name()) to display this nicely.
sage: SymmetricGroup(2).character_table()
[ 1 -1]
[ 1 1]
sage: SymmetricGroup(3).character_table()
[ 1 -1 1]
[ 2 0 -1]
[ 1 1 1]
sage: SymmetricGroup(5).character_table()
[ 1 -1 1 1 -1 -1 1]
[ 4 -2 0 1 1 0 -1]
[ 5 -1 1 -1 -1 1 0]
[ 6 0 -2 0 0 0 1]
[ 5 1 1 -1 1 -1 0]
[ 4 2 0 1 -1 0 -1]
[ 1 1 1 1 1 1 1]
sage: list(AlternatingGroup(6).character_table())
[(1, 1, 1, 1, 1, 1, 1), (5, 1, 2, -1, -1, 0, 0), (5, 1, -1, 2, -1, 0, 0), (8, 0, -1, -1, 0, zeta5^3 + zeta5^2 + 1, -zeta5^3 - zeta5^2), (8, 0, -1, -1, 0, -zeta5^3 - zeta5^2, zeta5^3 + zeta5^2 + 1), (9, 1, 0, 0, 1, -1, -1), (10, -2, 1, 1, 0, 0, 0)]
Suppose that you have a class function \(f(g)\) on \(G\) and you know the values \(v_1, \ldots, v_n\) on the conjugacy class elements in conjugacy_classes_representatives(G) = \([g_1, \ldots, g_n]\). Since the irreducible characters \(\rho_1, \ldots, \rho_n\) of \(G\) form an \(E\)-basis of the space of all class functions (\(E\) a “sufficiently large” cyclotomic field), such a class function is a linear combination of these basis elements, \(f = c_1 \rho_1 + \cdots + c_n \rho_n\). To find the coefficients \(c_i\), you simply solve the linear system character_table_values(G) \([v_1, ..., v_n] = [c_1, ..., c_n]\), where \([v_1, \ldots, v_n]\) = character_table_values(G) \(^{(-1)}[c_1, ..., c_n]\).
AUTHORS:
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:
REFERENCES:
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:
Returns the commutator subgroup of a group, or of a pair of groups.
INPUT:
OUTPUT:
Let \(G\) denote self. If other is None then this method returns the subgroup of \(G\) generated by the set of commutators,
Let \(H\) denote other, in the case that it is not None. Then this method returns the group generated by the set of commutators,
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
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 [()]
Return the conjugacy class of g inside the group self.
INPUT:
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 = SymmetricGroup(4)
sage: g = G((1,2,3,4))
sage: G.conjugacy_class(g)
Conjugacy class of (1,2,3,4) in Symmetric group of order 4! as a permutation group
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 (1,2) 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]
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:
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:
Returns the group formed by conjugating self with g.
INPUT:
OUTPUT:
If self is the group denoted by \(H\), then this method computes the group
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
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')
Returns a list of the cosets of S in self.
INPUT:
OUTPUT:
A list of lists. Each inner list is a coset of the subgroup in the group. The first element of each coset is the smallest element (based on the ordering of the elements of self) of all the group elements that have not yet appeared in a previous coset. The elements of each coset are in the same order as the subgroup elements used to build the coset’s elements.
As a consequence, the subgroup itself is the first coset, and its first element is the identity element. For each coset, the first element listed is the element used as a representative to build the coset. These representatives form an increasing sequence across the list of cosets, and within a coset the representative is the smallest element of its coset (both orderings are based on of the ordering of elements of self).
In the case of a normal subgroup, left and right cosets should appear in the same order as part of the outer list. However, the list of the elements of a particular coset may be in a different order for the right coset versus the order in the left coset. So, if you check to see if a subgroup is normal, it is necessary to sort each individual coset first (but not the list of cosets, due to the ordering of the representatives). See below for examples of this.
Note
This is a naive implementation intended for instructional purposes, and hence is slow for larger groups. Sage and GAP provide more sophisticated functions for working quickly with cosets of larger groups.
EXAMPLES:
The default is to build right cosets. This example works with the symmetry group of an 8-gon and a normal subgroup. Notice that a straight check on the equality of the output is not sufficient to check normality, while sorting the individual cosets is sufficient to then simply test equality of the list of lists. Study the second coset in each list to understand the need for sorting the elements of the cosets.
sage: G = DihedralGroup(8)
sage: quarter_turn = G.list()[5]; quarter_turn
(1,3,5,7)(2,4,6,8)
sage: S = G.subgroup([quarter_turn])
sage: rc = G.cosets(S); rc
[[(), (1,3,5,7)(2,4,6,8), (1,5)(2,6)(3,7)(4,8), (1,7,5,3)(2,8,6,4)],
[(2,8)(3,7)(4,6), (1,7)(2,6)(3,5), (1,5)(2,4)(6,8), (1,3)(4,8)(5,7)],
[(1,2)(3,8)(4,7)(5,6), (1,8)(2,7)(3,6)(4,5), (1,6)(2,5)(3,4)(7,8), (1,4)(2,3)(5,8)(6,7)],
[(1,2,3,4,5,6,7,8), (1,4,7,2,5,8,3,6), (1,6,3,8,5,2,7,4), (1,8,7,6,5,4,3,2)]]
sage: lc = G.cosets(S, side='left'); lc
[[(), (1,3,5,7)(2,4,6,8), (1,5)(2,6)(3,7)(4,8), (1,7,5,3)(2,8,6,4)],
[(2,8)(3,7)(4,6), (1,3)(4,8)(5,7), (1,5)(2,4)(6,8), (1,7)(2,6)(3,5)],
[(1,2)(3,8)(4,7)(5,6), (1,4)(2,3)(5,8)(6,7), (1,6)(2,5)(3,4)(7,8), (1,8)(2,7)(3,6)(4,5)],
[(1,2,3,4,5,6,7,8), (1,4,7,2,5,8,3,6), (1,6,3,8,5,2,7,4), (1,8,7,6,5,4,3,2)]]
sage: S.is_normal(G)
True
sage: rc == lc
False
sage: rc_sorted = [sorted(c) for c in rc]
sage: lc_sorted = [sorted(c) for c in lc]
sage: rc_sorted == lc_sorted
True
An example with the symmetry group of a regular tetrahedron and a subgroup that is not normal. Thus, the right and left cosets are different (and so are the representatives). With each individual coset sorted, a naive test of normality is possible.
sage: A = AlternatingGroup(4)
sage: face_turn = A.list()[4]; face_turn
(1,2,3)
sage: stabilizer = A.subgroup([face_turn])
sage: rc = A.cosets(stabilizer, side='right'); rc
[[(), (1,2,3), (1,3,2)],
[(2,3,4), (1,3)(2,4), (1,4,2)],
[(2,4,3), (1,4,3), (1,2)(3,4)],
[(1,2,4), (1,4)(2,3), (1,3,4)]]
sage: lc = A.cosets(stabilizer, side='left'); lc
[[(), (1,2,3), (1,3,2)],
[(2,3,4), (1,2)(3,4), (1,3,4)],
[(2,4,3), (1,2,4), (1,3)(2,4)],
[(1,4,2), (1,4,3), (1,4)(2,3)]]
sage: stabilizer.is_normal(A)
False
sage: rc_sorted = [sorted(c) for c in rc]
sage: lc_sorted = [sorted(c) for c in lc]
sage: rc_sorted == lc_sorted
False
TESTS:
The keyword side is checked for the two possible values.
sage: G = SymmetricGroup(3)
sage: S = G.subgroup([G("(1,2)")])
sage: G.cosets(S, side='junk')
Traceback (most recent call last):
...
ValueError: side should be 'right' or 'left', not junk
The subgroup argument is checked to see if it is a permutation group. Even a legitimate GAP object can be rejected.
sage: G=SymmetricGroup(3)
sage: G.cosets(gap(3))
Traceback (most recent call last):
...
TypeError: 3 is not a permutation group
The subgroup is verified as a subgroup of self.
sage: A = AlternatingGroup(3)
sage: G = SymmetricGroup(3)
sage: S = G.subgroup([G("(1,2)")])
sage: A.cosets(S)
Traceback (most recent call last):
...
ValueError: Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(1,2)] is not a subgroup of Alternating group of order 3!/2 as a permutation group
AUTHOR:
Returns the degree of this permutation group.
EXAMPLES:
sage: S = SymmetricGroup(['a','b','c'])
sage: S.degree()
3
sage: G = PermutationGroup([(1,3),(4,5)])
sage: G.degree()
5
Note that you can explicitly specify the domain to get a permutation group of smaller degree:
sage: G = PermutationGroup([(1,3),(4,5)], domain=[1,3,4,5])
sage: G.degree()
4
Return 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)]]
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:
OUTPUT:
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)
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'}
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
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)]
Returns the list of points fixed by self, i.e., the subset of .domain() not moved by any element of self.
EXAMPLES:
sage: G=PermutationGroup([(1,2,3)])
sage: G.fixed_points()
[]
sage: G=PermutationGroup([(1,2,3),(5,6)])
sage: G.fixed_points()
[4]
sage: G=PermutationGroup([[(1,4,7)],[(4,3),(6,7)]])
sage: G.fixed_points()
[2, 5]
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 [()]
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)
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()
[()]
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
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 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
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
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 article 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:
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:
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:
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:
(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 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()
()
Returns the permutation group that is the intersection of self and other.
INPUT:
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
Returns a list of the irreducible characters of self.
EXAMPLES:
sage: irr = SymmetricGroup(3).irreducible_characters()
sage: [x.values() for x in irr]
[[1, -1, 1], [2, 0, -1], [1, 1, 1]]
Return True if this group is abelian.
EXAMPLES:
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: G.is_abelian()
False
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_abelian()
True
Return True if this group is commutative.
EXAMPLES:
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: G.is_commutative()
False
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_commutative()
True
Return True if this group is cyclic.
EXAMPLES:
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: G.is_cyclic()
False
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_cyclic()
True
Return True if this group is elementary abelian. An elementary abelian group is a finite abelian group, where every nontrivial element has order \(p\), where \(p\) is a prime.
EXAMPLES:
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: G.is_elementary_abelian()
False
sage: G = PermutationGroup(['(1,2,3)','(4,5,6)'])
sage: G.is_elementary_abelian()
True
Return True if the groups are isomorphic.
INPUT:
OUTPUT:
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
Returns True if the group is monomial. A finite group is monomial if every irreducible complex character is induced from a linear character of a subgroup.
EXAMPLES:
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_monomial()
True
Return True if this group is nilpotent.
EXAMPLES:
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: G.is_nilpotent()
False
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_nilpotent()
True
Return 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
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
Returns True if this group is a \(p\)-group. A finite group is a \(p\)-group if its order is of the form \(p^n\) for a prime integer \(p\) and a nonnegative integer \(n\).
EXAMPLES:
sage: G = PermutationGroup(['(1,2,3,4,5)'])
sage: G.is_pgroup()
True
Return 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
Returns True if self acts primitively on domain. A group \(G\) acts primitively on a set \(S\) if
INPUT:
See also
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
Returns True if self acts regularly on domain. A group \(G\) acts regularly on a set \(S\) if
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
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
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
Returns True if the group is solvable.
EXAMPLES:
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: G.is_solvable()
True
Returns True if self is a subgroup of other.
EXAMPLES:
sage: G = AlternatingGroup(5)
sage: H = SymmetricGroup(5)
sage: G.is_subgroup(H)
True
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
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
Return an isomorphism from self to right if the groups are isomorphic, otherwise None.
INPUT:
OUTPUT:
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)] -> [...]
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 ticket 7360 is fixed:
sage: G = KleinFourGroup()
sage: G.is_simple()
False
sage: G.isomorphism_type_info_simple_group()
Traceback (most recent call last):
...
TypeError: Group must be simple.
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
Return list of all elements of this group.
EXAMPLES:
sage: G = PermutationGroup([[(1,2,3,4)], [(1,2)]])
sage: G.list()
[(), (3,4), (2,3), (2,3,4), (2,4,3), (2,4), (1,2), (1,2)(3,4), (1,2,3), (1,2,3,4), (1,2,4,3), (1,2,4), (1,3,2), (1,3,4,2), (1,3), (1,3,4), (1,3)(2,4), (1,3,2,4), (1,4,3,2), (1,4,2), (1,4,3), (1,4), (1,4,2,3), (1,4)(2,3)]
sage: G = PermutationGroup([[('a','b')]], domain=('a', 'b')); G
Permutation Group with generators [('a','b')]
sage: G.list()
[(), ('a','b')]
Return 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)]]
Returns the Molien series of a transitive permutation group. The function
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)
Returns the list of points not fixed by self, i.e., the subset of self.domain() moved by some element of self.
EXAMPLES:
sage: G = PermutationGroup([[(3,4,5)],[(7,10)]])
sage: G.non_fixed_points()
[3, 4, 5, 7, 10]
sage: G = PermutationGroup([[(2,3,6)],[(9,)]]) # note: 9 is fixed
sage: G.non_fixed_points()
[2, 3, 6]
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
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)]
Returns True if the group other is normalized by self. Wraps GAP’s IsNormal function.
A group \(G\) normalizes a group \(U\) if and only if for every \(g \in G\) and \(u \in U\) the element \(u^g\) is a member of \(U\). Note that \(U\) need not be a subgroup of \(G\).
EXAMPLES:
sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: H = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
sage: H.normalizes(G)
False
sage: G = SymmetricGroup(3)
sage: H = PermutationGroup( [ (4,5,6) ] )
sage: G.normalizes(H)
True
sage: H.normalizes(G)
True
In the last example, \(G\) and \(H\) are disjoint, so each normalizes the other.
Return 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'}))
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:
Return the number of elements of this group.
EXAMPLES:
sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
sage: G.order()
12
sage: G = PermutationGroup([()])
sage: G.order()
1
sage: G = PermutationGroup([])
sage: G.order()
1
Returns the Poincare series of \(G \mod p\) (\(p \geq 2\) must be a prime), for \(n\) large. In other words, if you input a finite group \(G\), a prime \(p\), and a positive integer \(n\), it returns a quotient of polynomials \(f(x) = P(x) / Q(x)\) whose coefficient of \(x^k\) equals the rank of the vector space \(H_k(G, \ZZ / p \ZZ)\), for all \(k\) in the range \(1 \leq k \leq n\).
REQUIRES: GAP package HAP (in gap_packages-*.spkg).
EXAMPLES:
sage: G = SymmetricGroup(5)
sage: G.poincare_series(2,10) # optional - gap_packages
(x^2 + 1)/(x^4 - x^3 - x + 1)
sage: G = SymmetricGroup(3)
sage: G.poincare_series(2,10) # optional - gap_packages
1/(-x + 1)
AUTHORS:
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 [()]
This function has been deprecated and will be removed in a future version of Sage; use quotient instead.
Original docstring follows.
Returns the quotient of this permutation group by the normal subgroup \(N\).
Wraps the GAP operator “/”.
TESTS:
sage: G = PermutationGroup([(1,2,3), (2,3)])
sage: N = PermutationGroup([(1,2,3)])
sage: G.quotient_group(N)
doctest:...: DeprecationWarning: quotient_group() is deprecated; use quotient() instead.
See http://trac.sagemath.org/7371 for details.
Permutation Group with generators [(1,2)]
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
()
The semidirect product of self with N.
INPUT:
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:
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 [THOMAS-WOODS]. 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)
REFERENCES:
[THOMAS-WOODS] | (1, 2, 3) A.D. Thomas and G.V. Wood, Group Tables (Exeter: Shiva Publishing, 1980) |
AUTHOR:
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'
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)]
Returns the solvable radical of self. The solvable radical (or just radical) of a group \(G\) is the largest solvable normal subgroup of \(G\).
EXAMPLES:
sage: G=SymmetricGroup(4)
sage: G.solvable_radical()
Subgroup of (Symmetric group of order 4! as a permutation group) generated by [(1,2), (1,2,3,4)]
sage: G=SymmetricGroup(5)
sage: G.solvable_radical()
Subgroup of (Symmetric group of order 5! as a permutation group) generated by [()]
Return the subgroup of self which stabilize the given position. self and its stabilizers must have same degree.
EXAMPLES:
sage: G = PermutationGroup([ [(3,4)], [(1,3)] ])
sage: G.stabilizer(1)
Subgroup of (Permutation Group with generators [(3,4), (1,3)]) generated by [(3,4)]
sage: G.stabilizer(3)
Subgroup of (Permutation Group with generators [(3,4), (1,3)]) generated by [(1,4)]
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
sage: G.stabilizer(10)
Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4,10)]) generated by [(2,3,4), (1,2)(3,4)]
sage: G.stabilizer(1)
Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4,10)]) generated by [(2,3)(4,10), (2,10,4)]
sage: G = PermutationGroup([[(2,3,4)],[(6,7)]])
sage: G.stabilizer(1)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(6,7), (2,3,4)]
sage: G.stabilizer(2)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(6,7)]
sage: G.stabilizer(3)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(6,7)]
sage: G.stabilizer(4)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(6,7)]
sage: G.stabilizer(5)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(6,7), (2,3,4)]
sage: G.stabilizer(6)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(2,3,4)]
sage: G.stabilizer(7)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(2,3,4)]
sage: G.stabilizer(8)
Subgroup of (Permutation Group with generators [(6,7), (2,3,4)]) generated by [(6,7), (2,3,4)]
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')]
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
Then the algorithm returns \([ G_i.\mathrm{transversals}(\mathrm{pos}_{i+1})]_{1 \leq i \leq n}\)
INPUT:
OUTPUT:
TESTS:
sage: G = SymmetricGroup(10)
sage: H = PermutationGroup([G.random_element() for i in range(randrange(1,3,1))])
sage: prod(map(lambda x : len(x), H.strong_generating_system()),1) == H.cardinality()
True
EXAMPLES:
sage: G = PermutationGroup([[(7,8)],[(3,4)],[(4,5)]])
sage: G.strong_generating_system()
[[()], [()], [(), (3,4,5), (3,5)], [(), (4,5)], [()], [()], [(), (7,8)], [()]]
sage: G = PermutationGroup([[(1,2,3,4)],[(1,2)]])
sage: G.strong_generating_system()
[[(), (1,2)(3,4), (1,3)(2,4), (1,4)(2,3)], [(), (2,3,4), (2,4,3)], [(), (3,4)], [()]]
sage: G = PermutationGroup([[(1,2,3)],[(4,5,7)],[(1,4,6)]])
sage: G.strong_generating_system()
[[(), (1,2,3), (1,4,6), (1,3,2), (1,5,7,4,6), (1,6,4), (1,7,5,4,6)], [(), (2,6,3), (2,5,7,6,3), (2,3,6), (2,7,5,6,3), (2,4,7,6,3)], [(), (3,6,7), (3,5,6), (3,7,6), (3,4,7,5,6)], [(), (4,5)(6,7), (4,7)(5,6), (4,6)(5,7)], [(), (5,7,6), (5,6,7)], [()], [()]]
sage: G = PermutationGroup([[(1,2,3)],[(2,3,4)],[(3,4,5)]])
sage: G.strong_generating_system([5,4,3,2,1])
[[(), (1,5,3,4,2), (1,5,4,3,2), (1,5)(2,3), (1,5,2)], [(), (1,3)(2,4), (1,2)(3,4), (1,4)(2,3)], [(), (1,3,2), (1,2,3)], [()], [()]]
sage: G = PermutationGroup([[(3,4)]])
sage: G.strong_generating_system()
[[()], [()], [(), (3,4)], [()]]
sage: G.strong_generating_system(base_of_group=[3,1,2,4])
[[(), (3,4)], [()], [()], [()]]
sage: G = TransitiveGroup(12,17) # optional
sage: G.strong_generating_system() # optional
[[(), (1,4,11,2)(3,6,5,8)(7,10,9,12), (1,8,3,2)(4,11,10,9)(5,12,7,6), (1,7)(2,8)(3,9)(4,10)(5,11)(6,12), (1,12,7,2)(3,10,9,8)(4,11,6,5), (1,11)(2,8)(3,5)(4,10)(6,12)(7,9), (1,10,11,8)(2,3,12,5)(4,9,6,7), (1,3)(2,8)(4,10)(5,7)(6,12)(9,11), (1,2,3,8)(4,9,10,11)(5,6,7,12), (1,6,7,8)(2,3,4,9)(5,10,11,12), (1,5,9)(3,11,7), (1,9,5)(3,7,11)], [(), (2,6,10)(4,12,8), (2,10,6)(4,8,12)], [()], [()], [()], [()], [()], [()], [()], [()], [()], [()]]
Return a string that tries to describe the structure of self.
This methods wraps GAP’s StructureDescription method.
Requires the optional database_gap package.
For full details, including the form of the returned string and the algorithm to build it, see GAP’s documentation.
INPUT:
OUTPUT:
Warning
From GAP’s documentation: The string returned by StructureDescription is not an isomorphism invariant: non-isomorphic groups can have the same string value, and two isomorphic groups in different representations can produce different strings.
EXAMPLES:
sage: G = CyclicPermutationGroup(6)
sage: G.structure_description() # optional - database_gap
'C6'
sage: G.structure_description(latex=True) # optional - database_gap
'C_{6}'
sage: G2 = G.direct_product(G, maps=False)
sage: LatexExpr(G2.structure_description(latex=True)) # optional - database_gap
C_{6} \times C_{6}
This method is mainly intended for small groups or groups with few normal subgroups. Even then there are some surprises:
sage: D3 = DihedralGroup(3)
sage: D3.structure_description() # optional - database_gap
'S3'
We use the Sage notation for the degree of dihedral groups:
sage: D4 = DihedralGroup(4)
sage: D4.structure_description() # optional - database_gap
'D4'
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)]
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 conjugacy_classes_subgroups().
EXAMPLES:
sage: G = SymmetricGroup(3)
sage: G.subgroups()
[Permutation Group with generators [()],
Permutation Group with generators [(2,3)],
Permutation Group with generators [(1,2)],
Permutation Group with generators [(1,3)],
Permutation Group with generators [(1,2,3)],
Permutation Group with generators [(2,3), (1,2,3)]]
sage: G = CyclicPermutationGroup(14)
sage: G.subgroups()
[Permutation Group with generators [()],
Permutation Group with generators [(1,8)(2,9)(3,10)(4,11)(5,12)(6,13)(7,14)],
Permutation Group with generators [(1,3,5,7,9,11,13)(2,4,6,8,10,12,14)],
Permutation Group with generators [(1,2,3,4,5,6,7,8,9,10,11,12,13,14)]]
AUTHOR:
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...
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')]
Returns the trivial character of self.
EXAMPLES:
sage: SymmetricGroup(3).trivial_character()
Character of Symmetric group of order 3! as a permutation group
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 [()]]
Bases: sage.groups.perm_gps.permgroup.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)]
Return the ambient group related to self.
EXAMPLES:
An example involving the dihedral group on four elements, \(D_8\):
sage: G = DihedralGroup(4)
sage: H = CyclicPermutationGroup(4)
sage: gens = H.gens()
sage: S = PermutationGroup_subgroup(G, list(gens))
sage: S.ambient_group()
Dihedral group of order 8 as a permutation group
sage: S.ambient_group() == G
True
Return 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
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
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
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
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