Permutation Groups#
- class sympy.combinatorics.perm_groups.PermutationGroup(*args, dups=True, **kwargs)[source]#
The class defining a Permutation group.
Explanation
PermutationGroup([p1, p2, ..., pn])
returns the permutation group generated by the list of permutations. This group can be supplied to Polyhedron if one desires to decorate the elements to which the indices of the permutation refer.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> from sympy.combinatorics import Polyhedron
The permutations corresponding to motion of the front, right and bottom face of a \(2 \times 2\) Rubik’s cube are defined:
>>> F = Permutation(2, 19, 21, 8)(3, 17, 20, 10)(4, 6, 7, 5) >>> R = Permutation(1, 5, 21, 14)(3, 7, 23, 12)(8, 10, 11, 9) >>> D = Permutation(6, 18, 14, 10)(7, 19, 15, 11)(20, 22, 23, 21)
These are passed as permutations to PermutationGroup:
>>> G = PermutationGroup(F, R, D) >>> G.order() 3674160
The group can be supplied to a Polyhedron in order to track the objects being moved. An example involving the \(2 \times 2\) Rubik’s cube is given there, but here is a simple demonstration:
>>> a = Permutation(2, 1) >>> b = Permutation(1, 0) >>> G = PermutationGroup(a, b) >>> P = Polyhedron(list('ABC'), pgroup=G) >>> P.corners (A, B, C) >>> P.rotate(0) # apply permutation 0 >>> P.corners (A, C, B) >>> P.reset() >>> P.corners (A, B, C)
Or one can make a permutation as a product of selected permutations and apply them to an iterable directly:
>>> P10 = G.make_perm([0, 1]) >>> P10('ABC') ['C', 'A', 'B']
References
- R51
Holt, D., Eick, B., O’Brien, E. “Handbook of Computational Group Theory”
- R52
Seress, A. “Permutation Group Algorithms”
- R53
- R54
https://en.wikipedia.org/wiki/Nielsen_transformation#Product_replacement_algorithm
- R55
Frank Celler, Charles R.Leedham-Green, Scott H.Murray, Alice C.Niemeyer, and E.A.O’Brien. “Generating Random Elements of a Finite Group”
- R56
https://en.wikipedia.org/wiki/Block_%28permutation_group_theory%29
- R57
- R58
https://en.wikipedia.org/wiki/Multiply_transitive_group#Multiply_transitive_groups
- R59
- __contains__(i)[source]#
Return
True
if i is contained in PermutationGroup.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> p = Permutation(1, 2, 3) >>> Permutation(3) in PermutationGroup(p) True
- __mul__(other)[source]#
Return the direct product of two permutation groups as a permutation group.
Explanation
This implementation realizes the direct product by shifting the index set for the generators of the second group: so if we have
G
acting onn1
points andH
acting onn2
points,G*H
acts onn1 + n2
points.Examples
>>> from sympy.combinatorics.named_groups import CyclicGroup >>> G = CyclicGroup(5) >>> H = G*G >>> H PermutationGroup([ (9)(0 1 2 3 4), (5 6 7 8 9)]) >>> H.order() 25
- static __new__(cls, *args, dups=True, **kwargs)[source]#
The default constructor. Accepts Cycle and Permutation forms. Removes duplicates unless
dups
keyword isFalse
.
- __weakref__#
list of weak references to the object (if defined)
- _coset_representative(g, H)[source]#
Return the representative of Hg from the transversal that would be computed by
self.coset_transversal(H)
.
- classmethod _distinct_primes_lemma(primes)[source]#
Subroutine to test if there is only one cyclic group for the order.
- property _elements#
Returns all the elements of the permutation group as a list
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> p = PermutationGroup(Permutation(1, 3), Permutation(1, 2)) >>> p._elements [(3), (3)(1 2), (1 3), (2 3), (1 2 3), (1 3 2)]
- _eval_is_alt_sym_monte_carlo(eps=0.05, perms=None)[source]#
A test using monte-carlo algorithm.
- Parameters
eps : float, optional
The criterion for the incorrect
False
return.perms : list[Permutation], optional
If explicitly given, it tests over the given candidats for testing.
If
None
, it randomly computesN_eps
and choosesN_eps
sample of the permutation from the group.
See also
- _p_elements_group(p)[source]#
For an abelian p-group, return the subgroup consisting of all elements of order p (and the identity)
- _random_pr_init(r, n, _random_prec_n=None)[source]#
Initialize random generators for the product replacement algorithm.
Explanation
The implementation uses a modification of the original product replacement algorithm due to Leedham-Green, as described in [1], pp. 69-71; also, see [2], pp. 27-29 for a detailed theoretical analysis of the original product replacement algorithm, and [4].
The product replacement algorithm is used for producing random, uniformly distributed elements of a group \(G\) with a set of generators \(S\). For the initialization
_random_pr_init
, a listR
of \(\max\{r, |S|\}\) group generators is created as the attributeG._random_gens
, repeating elements of \(S\) if necessary, and the identity element of \(G\) is appended toR
- we shall refer to this last element as the accumulator. Then the functionrandom_pr()
is calledn
times, randomizing the listR
while preserving the generation of \(G\) byR
. The functionrandom_pr()
itself takes two random elementsg, h
among all elements ofR
but the accumulator and replacesg
with a randomly chosen element from \(\{gh, g(~h), hg, (~h)g\}\). Then the accumulator is multiplied by whateverg
was replaced by. The new value of the accumulator is then returned byrandom_pr()
.The elements returned will eventually (for
n
large enough) become uniformly distributed across \(G\) ([5]). For practical purposes however, the valuesn = 50, r = 11
are suggested in [1].Notes
THIS FUNCTION HAS SIDE EFFECTS: it changes the attribute self._random_gens
See also
- _sylow_alt_sym(p)[source]#
Return a p-Sylow subgroup of a symmetric or an alternating group.
Explanation
The algorithm for this is hinted at in [1], Chapter 4, Exercise 4.
For Sym(n) with n = p^i, the idea is as follows. Partition the interval [0..n-1] into p equal parts, each of length p^(i-1): [0..p^(i-1)-1], [p^(i-1)..2*p^(i-1)-1]…[(p-1)*p^(i-1)..p^i-1]. Find a p-Sylow subgroup of Sym(p^(i-1)) (treated as a subgroup of
self
) acting on each of the parts. Call the subgroups P_1, P_2…P_p. The generators for the subgroups P_2…P_p can be obtained from those of P_1 by applying a “shifting” permutation to them, that is, a permutation mapping [0..p^(i-1)-1] to the second part (the other parts are obtained by using the shift multiple times). The union of this permutation and the generators of P_1 is a p-Sylow subgroup ofself
.For n not equal to a power of p, partition [0..n-1] in accordance with how n would be written in base p. E.g. for p=2 and n=11, 11 = 2^3 + 2^2 + 1 so the partition is [[0..7], [8..9], {10}]. To generate a p-Sylow subgroup, take the union of the generators for each of the parts. For the above example, {(0 1), (0 2)(1 3), (0 4), (1 5)(2 7)} from the first part, {(8 9)} from the second part and nothing from the third. This gives 4 generators in total, and the subgroup they generate is p-Sylow.
Alternating groups are treated the same except when p=2. In this case, (0 1)(s s+1) should be added for an appropriate s (the start of a part) for each part in the partitions.
See also
- _union_find_merge(first, second, ranks, parents, not_rep)[source]#
Merges two classes in a union-find data structure.
Explanation
Used in the implementation of Atkinson’s algorithm as suggested in [1], pp. 83-87. The class merging process uses union by rank as an optimization. ([7])
Notes
THIS FUNCTION HAS SIDE EFFECTS: the list of class representatives,
parents
, the list of class sizes,ranks
, and the list of elements that are not representatives,not_rep
, are changed due to class merging.See also
References
- _union_find_rep(num, parents)[source]#
Find representative of a class in a union-find data structure.
Explanation
Used in the implementation of Atkinson’s algorithm as suggested in [1], pp. 83-87. After the representative of the class to which
num
belongs is found, path compression is performed as an optimization ([7]).Notes
THIS FUNCTION HAS SIDE EFFECTS: the list of class representatives,
parents
, is altered due to path compression.See also
References
- _verify(K, phi, z, alpha)[source]#
Return a list of relators
rels
in generatorsgens`_h` that are mapped to ``H.generators
byphi
so that given a finite presentation <gens_k | rels_k> ofK
on a subset ofgens_h
<gens_h | rels_k + rels> is a finite presentation ofH
.Explanation
H
should be generated by the union ofK.generators
andz
(a single generator), andH.stabilizer(alpha) == K
;phi
is a canonical injection from a free group into a permutation group containingH
.The algorithm is described in [1], Chapter 6.
Examples
>>> from sympy.combinatorics import free_group, Permutation, PermutationGroup >>> from sympy.combinatorics.homomorphisms import homomorphism >>> from sympy.combinatorics.fp_groups import FpGroup
>>> H = PermutationGroup(Permutation(0, 2), Permutation (1, 5)) >>> K = PermutationGroup(Permutation(5)(0, 2)) >>> F = free_group("x_0 x_1")[0] >>> gens = F.generators >>> phi = homomorphism(F, H, F.generators, H.generators) >>> rels_k = [gens[0]**2] # relators for presentation of K >>> z= Permutation(1, 5) >>> check, rels_h = H._verify(K, phi, z, 1) >>> check True >>> rels = rels_k + rels_h >>> G = FpGroup(F, rels) # presentation of H >>> G.order() == H.order() True
See also
- abelian_invariants()[source]#
Returns the abelian invariants for the given group. Let
G
be a nontrivial finite abelian group. Then G is isomorphic to the direct product of finitely many nontrivial cyclic groups of prime-power order.Explanation
The prime-powers that occur as the orders of the factors are uniquely determined by G. More precisely, the primes that occur in the orders of the factors in any such decomposition of
G
are exactly the primes that divide|G|
and for any such primep
, if the orders of the factors that are p-groups in one such decomposition ofG
arep^{t_1} >= p^{t_2} >= ... p^{t_r}
, then the orders of the factors that are p-groups in any such decomposition ofG
arep^{t_1} >= p^{t_2} >= ... p^{t_r}
.The uniquely determined integers
p^{t_1} >= p^{t_2} >= ... p^{t_r}
, taken for all primes that divide|G|
are called the invariants of the nontrivial groupG
as suggested in ([14], p. 542).Notes
We adopt the convention that the invariants of a trivial group are [].
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.abelian_invariants() [2] >>> from sympy.combinatorics import CyclicGroup >>> G = CyclicGroup(7) >>> G.abelian_invariants() [7]
- property base#
Return a base from the Schreier-Sims algorithm.
Explanation
For a permutation group \(G\), a base is a sequence of points \(B = (b_1, b_2, \dots, b_k)\) such that no element of \(G\) apart from the identity fixes all the points in \(B\). The concepts of a base and strong generating set and their applications are discussed in depth in [1], pp. 87-89 and [2], pp. 55-57.
An alternative way to think of \(B\) is that it gives the indices of the stabilizer cosets that contain more than the identity permutation.
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> G = PermutationGroup([Permutation(0, 1, 3)(2, 4)]) >>> G.base [0, 2]
See also
strong_gens
,basic_transversals
,basic_orbits
,basic_stabilizers
- baseswap(base, strong_gens, pos, randomized=False, transversals=None, basic_orbits=None, strong_gens_distr=None)[source]#
Swap two consecutive base points in base and strong generating set.
- Parameters
base, strong_gens
The base and strong generating set.
pos
The position at which swapping is performed.
randomized
A switch between randomized and deterministic version.
transversals
The transversals for the basic orbits, if known.
basic_orbits
The basic orbits, if known.
strong_gens_distr
The strong generators distributed by basic stabilizers, if known.
- Returns
(base, strong_gens)
base
is the new base, andstrong_gens
is a generating set relative to it.
Explanation
If a base for a group \(G\) is given by \((b_1, b_2, \dots, b_k)\), this function returns a base \((b_1, b_2, \dots, b_{i+1}, b_i, \dots, b_k)\), where \(i\) is given by
pos
, and a strong generating set relative to that base. The original base and strong generating set are not modified.The randomized version (default) is of Las Vegas type.
Examples
>>> from sympy.combinatorics.named_groups import SymmetricGroup >>> from sympy.combinatorics.testutil import _verify_bsgs >>> from sympy.combinatorics.perm_groups import PermutationGroup >>> S = SymmetricGroup(4) >>> S.schreier_sims() >>> S.base [0, 1, 2] >>> base, gens = S.baseswap(S.base, S.strong_gens, 1, randomized=False) >>> base, gens ([0, 2, 1], [(0 1 2 3), (3)(0 1), (1 3 2), (2 3), (1 3)])
check that base, gens is a BSGS
>>> S1 = PermutationGroup(gens) >>> _verify_bsgs(S1, base, gens) True
Notes
The deterministic version of the algorithm is discussed in [1], pp. 102-103; the randomized version is discussed in [1], p.103, and [2], p.98. It is of Las Vegas type. Notice that [1] contains a mistake in the pseudocode and discussion of BASESWAP: on line 3 of the pseudocode, \(|\beta_{i+1}^{\left\langle T\right\rangle}|\) should be replaced by \(|\beta_{i}^{\left\langle T\right\rangle}|\), and the same for the discussion of the algorithm.
See also
- property basic_orbits#
Return the basic orbits relative to a base and strong generating set.
Explanation
If \((b_1, b_2, \dots, b_k)\) is a base for a group \(G\), and \(G^{(i)} = G_{b_1, b_2, \dots, b_{i-1}}\) is the
i
-th basic stabilizer (so that \(G^{(1)} = G\)), thei
-th basic orbit relative to this base is the orbit of \(b_i\) under \(G^{(i)}\). See [1], pp. 87-89 for more information.Examples
>>> from sympy.combinatorics.named_groups import SymmetricGroup >>> S = SymmetricGroup(4) >>> S.basic_orbits [[0, 1, 2, 3], [1, 2, 3], [2, 3]]
See also
- property basic_stabilizers#
Return a chain of stabilizers relative to a base and strong generating set.
Explanation
The
i
-th basic stabilizer \(G^{(i)}\) relative to a base \((b_1, b_2, \dots, b_k)\) is \(G_{b_1, b_2, \dots, b_{i-1}}\). For more information, see [1], pp. 87-89.Examples
>>> from sympy.combinatorics.named_groups import AlternatingGroup >>> A = AlternatingGroup(4) >>> A.schreier_sims() >>> A.base [0, 1] >>> for g in A.basic_stabilizers: ... print(g) ... PermutationGroup([ (3)(0 1 2), (1 2 3)]) PermutationGroup([ (1 2 3)])
See also
- property basic_transversals#
Return basic transversals relative to a base and strong generating set.
Explanation
The basic transversals are transversals of the basic orbits. They are provided as a list of dictionaries, each dictionary having keys - the elements of one of the basic orbits, and values - the corresponding transversal elements. See [1], pp. 87-89 for more information.
Examples
>>> from sympy.combinatorics.named_groups import AlternatingGroup >>> A = AlternatingGroup(4) >>> A.basic_transversals [{0: (3), 1: (3)(0 1 2), 2: (3)(0 2 1), 3: (0 3 1)}, {1: (3), 2: (1 2 3), 3: (1 3 2)}]
See also
- center()[source]#
Return the center of a permutation group.
Explanation
The center for a group \(G\) is defined as \(Z(G) = \{z\in G | \forall g\in G, zg = gz \}\), the set of elements of \(G\) that commute with all elements of \(G\). It is equal to the centralizer of \(G\) inside \(G\), and is naturally a subgroup of \(G\) ([9]).
Examples
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> D = DihedralGroup(4) >>> G = D.center() >>> G.order() 2
Notes
This is a naive implementation that is a straightforward application of
.centralizer()
See also
- centralizer(other)[source]#
Return the centralizer of a group/set/element.
- Parameters
other
a permutation group/list of permutations/single permutation
Explanation
The centralizer of a set of permutations
S
inside a groupG
is the set of elements ofG
that commute with all elements ofS
:`C_G(S) = \{ g \in G | gs = sg \forall s \in S\}` ([10])
Usually,
S
is a subset ofG
, but ifG
is a proper subgroup of the full symmetric group, we allow forS
to have elements outsideG
.It is naturally a subgroup of
G
; the centralizer of a permutation group is equal to the centralizer of any set of generators for that group, since any element commuting with the generators commutes with any product of the generators.Examples
>>> from sympy.combinatorics.named_groups import (SymmetricGroup, ... CyclicGroup) >>> S = SymmetricGroup(6) >>> C = CyclicGroup(6) >>> H = S.centralizer(C) >>> H.is_subgroup(C) True
Notes
The implementation is an application of
.subgroup_search()
with tests using a specific base for the groupG
.See also
- commutator(G, H)[source]#
Return the commutator of two subgroups.
Explanation
For a permutation group
K
and subgroupsG
,H
, the commutator ofG
andH
is defined as the group generated by all the commutators \([g, h] = hgh^{-1}g^{-1}\) forg
inG
andh
inH
. It is naturally a subgroup ofK
([1], p.27).Examples
>>> from sympy.combinatorics.named_groups import (SymmetricGroup, ... AlternatingGroup) >>> S = SymmetricGroup(5) >>> A = AlternatingGroup(5) >>> G = S.commutator(S, A) >>> G.is_subgroup(A) True
Notes
The commutator of two subgroups \(H, G\) is equal to the normal closure of the commutators of all the generators, i.e. \(hgh^{-1}g^{-1}\) for \(h\) a generator of \(H\) and \(g\) a generator of \(G\) ([1], p.28)
See also
- composition_series()[source]#
Return the composition series for a group as a list of permutation groups.
Explanation
The composition series for a group \(G\) is defined as a subnormal series \(G = H_0 > H_1 > H_2 \ldots\) A composition series is a subnormal series such that each factor group \(H(i+1) / H(i)\) is simple. A subnormal series is a composition series only if it is of maximum length.
The algorithm works as follows: Starting with the derived series the idea is to fill the gap between \(G = der[i]\) and \(H = der[i+1]\) for each \(i\) independently. Since, all subgroups of the abelian group \(G/H\) are normal so, first step is to take the generators \(g\) of \(G\) and add them to generators of \(H\) one by one.
The factor groups formed are not simple in general. Each group is obtained from the previous one by adding one generator \(g\), if the previous group is denoted by \(H\) then the next group \(K\) is generated by \(g\) and \(H\). The factor group \(K/H\) is cyclic and it’s order is \(K.order()//G.order()\). The series is then extended between \(K\) and \(H\) by groups generated by powers of \(g\) and \(H\). The series formed is then prepended to the already existing series.
Examples
>>> from sympy.combinatorics.named_groups import SymmetricGroup >>> from sympy.combinatorics.named_groups import CyclicGroup >>> S = SymmetricGroup(12) >>> G = S.sylow_subgroup(2) >>> C = G.composition_series() >>> [H.order() for H in C] [1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1] >>> G = S.sylow_subgroup(3) >>> C = G.composition_series() >>> [H.order() for H in C] [243, 81, 27, 9, 3, 1] >>> G = CyclicGroup(12) >>> C = G.composition_series() >>> [H.order() for H in C] [12, 6, 3, 1]
- conjugacy_class(x)[source]#
Return the conjugacy class of an element in the group.
Explanation
The conjugacy class of an element
g
in a groupG
is the set of elementsx
inG
that are conjugate withg
, i.e. for whichg = xax^{-1}
for some
a
inG
.Note that conjugacy is an equivalence relation, and therefore that conjugacy classes are partitions of
G
. For a list of all the conjugacy classes of the group, use the conjugacy_classes() method.In a permutation group, each conjugacy class corresponds to a particular \(cycle structure': for example, in \), the conjugacy classes are:
the identity class,
{()}
all transpositions,
{(1 2), (1 3), (2 3)}
all 3-cycles,
{(1 2 3), (1 3 2)}
Examples
>>> from sympy.combinatorics import Permutation, SymmetricGroup >>> S3 = SymmetricGroup(3) >>> S3.conjugacy_class(Permutation(0, 1, 2)) {(0 1 2), (0 2 1)}
Notes
This procedure computes the conjugacy class directly by finding the orbit of the element under conjugation in G. This algorithm is only feasible for permutation groups of relatively small order, but is like the orbit() function itself in that respect.
- conjugacy_classes()[source]#
Return the conjugacy classes of the group.
Explanation
As described in the documentation for the .conjugacy_class() function, conjugacy is an equivalence relation on a group G which partitions the set of elements. This method returns a list of all these conjugacy classes of G.
Examples
>>> from sympy.combinatorics import SymmetricGroup >>> SymmetricGroup(3).conjugacy_classes() [{(2)}, {(0 1 2), (0 2 1)}, {(0 2), (1 2), (2)(0 1)}]
- contains(g, strict=True)[source]#
Test if permutation
g
belong to self,G
.Explanation
If
g
is an element ofG
it can be written as a product of factors drawn from the cosets ofG
’s stabilizers. To see ifg
is one of the actual generators defining the group useG.has(g)
.If
strict
is notTrue
,g
will be resized, if necessary, to match the size of permutations inself
.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> a = Permutation(1, 2) >>> b = Permutation(2, 3, 1) >>> G = PermutationGroup(a, b, degree=5) >>> G.contains(G[0]) # trivial check True >>> elem = Permutation([[2, 3]], size=5) >>> G.contains(elem) True >>> G.contains(Permutation(4)(0, 1, 2, 3)) False
If strict is False, a permutation will be resized, if necessary:
>>> H = PermutationGroup(Permutation(5)) >>> H.contains(Permutation(3)) False >>> H.contains(Permutation(3), strict=False) True
To test if a given permutation is present in the group:
>>> elem in G.generators False >>> G.has(elem) False
See also
- coset_factor(g, factor_index=False)[source]#
Return
G
’s (self’s) coset factorization ofg
Explanation
If
g
is an element ofG
then it can be written as the product of permutations drawn from the Schreier-Sims coset decomposition,The permutations returned in
f
are those for which the product givesg
:g = f[n]*...f[1]*f[0]
wheren = len(B)
andB = G.base
. f[i] is one of the permutations inself._basic_orbits[i]
.If factor_index==True, returns a tuple
[b[0],..,b[n]]
, whereb[i]
belongs toself._basic_orbits[i]
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation(0, 1, 3, 7, 6, 4)(2, 5) >>> b = Permutation(0, 1, 3, 2)(4, 5, 7, 6) >>> G = PermutationGroup([a, b])
Define g:
>>> g = Permutation(7)(1, 2, 4)(3, 6, 5)
Confirm that it is an element of G:
>>> G.contains(g) True
Thus, it can be written as a product of factors (up to 3) drawn from u. See below that a factor from u1 and u2 and the Identity permutation have been used:
>>> f = G.coset_factor(g) >>> f[2]*f[1]*f[0] == g True >>> f1 = G.coset_factor(g, True); f1 [0, 4, 4] >>> tr = G.basic_transversals >>> f[0] == tr[0][f1[0]] True
If g is not an element of G then [] is returned:
>>> c = Permutation(5, 6, 7) >>> G.coset_factor(c) []
See also
- coset_rank(g)[source]#
rank using Schreier-Sims representation.
Explanation
The coset rank of
g
is the ordering number in which it appears in the lexicographic listing according to the coset decompositionThe ordering is the same as in G.generate(method=’coset’). If
g
does not belong to the group it returns None.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation(0, 1, 3, 7, 6, 4)(2, 5) >>> b = Permutation(0, 1, 3, 2)(4, 5, 7, 6) >>> G = PermutationGroup([a, b]) >>> c = Permutation(7)(2, 4)(3, 5) >>> G.coset_rank(c) 16 >>> G.coset_unrank(16) (7)(2 4)(3 5)
See also
- coset_table(H)[source]#
Return the standardised (right) coset table of self in H as a list of lists.
- coset_transversal(H)[source]#
Return a transversal of the right cosets of self by its subgroup H using the second method described in [1], Subsection 4.6.7
- coset_unrank(rank, af=False)[source]#
unrank using Schreier-Sims representation
coset_unrank is the inverse operation of coset_rank if 0 <= rank < order; otherwise it returns None.
- property degree#
Returns the size of the permutations in the group.
Explanation
The number of permutations comprising the group is given by
len(group)
; the number of permutations that can be generated by the group is given bygroup.order()
.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([1, 0, 2]) >>> G = PermutationGroup([a]) >>> G.degree 3 >>> len(G) 1 >>> G.order() 2 >>> list(G.generate()) [(2), (2)(0 1)]
See also
- derived_series()[source]#
Return the derived series for the group.
- Returns
A list of permutation groups containing the members of the derived
series in the order \(G = G_0, G_1, G_2, \ldots\).
Explanation
The derived series for a group \(G\) is defined as \(G = G_0 > G_1 > G_2 > \ldots\) where \(G_i = [G_{i-1}, G_{i-1}]\), i.e. \(G_i\) is the derived subgroup of \(G_{i-1}\), for \(i\in\mathbb{N}\). When we have \(G_k = G_{k-1}\) for some \(k\in\mathbb{N}\), the series terminates.
Examples
>>> from sympy.combinatorics.named_groups import (SymmetricGroup, ... AlternatingGroup, DihedralGroup) >>> A = AlternatingGroup(5) >>> len(A.derived_series()) 1 >>> S = SymmetricGroup(4) >>> len(S.derived_series()) 4 >>> S.derived_series()[1].is_subgroup(AlternatingGroup(4)) True >>> S.derived_series()[2].is_subgroup(DihedralGroup(2)) True
See also
- derived_subgroup()[source]#
Compute the derived subgroup.
Explanation
The derived subgroup, or commutator subgroup is the subgroup generated by all commutators \([g, h] = hgh^{-1}g^{-1}\) for \(g, h\in G\) ; it is equal to the normal closure of the set of commutators of the generators ([1], p.28, [11]).
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([1, 0, 2, 4, 3]) >>> b = Permutation([0, 1, 3, 2, 4]) >>> G = PermutationGroup([a, b]) >>> C = G.derived_subgroup() >>> list(C.generate(af=True)) [[0, 1, 2, 3, 4], [0, 1, 3, 4, 2], [0, 1, 4, 2, 3]]
See also
- property elements#
Returns all the elements of the permutation group as a set
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> p = PermutationGroup(Permutation(1, 3), Permutation(1, 2)) >>> p.elements {(1 2 3), (1 3 2), (1 3), (2 3), (3), (3)(1 2)}
- equals(other)[source]#
Return
True
if PermutationGroup generated by elements in the group are same i.e they represent the same PermutationGroup.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> p = Permutation(0, 1, 2, 3, 4, 5) >>> G = PermutationGroup([p, p**2]) >>> H = PermutationGroup([p**2, p]) >>> G.generators == H.generators False >>> G.equals(H) True
- generate(method='coset', af=False)[source]#
Return iterator to generate the elements of the group.
Explanation
Iteration is done with one of these methods:
method='coset' using the Schreier-Sims coset representation method='dimino' using the Dimino method
If
af = True
it yields the array form of the permutationsExamples
>>> from sympy.combinatorics import PermutationGroup >>> from sympy.combinatorics.polyhedron import tetrahedron
The permutation group given in the tetrahedron object is also true groups:
>>> G = tetrahedron.pgroup >>> G.is_group True
Also the group generated by the permutations in the tetrahedron pgroup – even the first two – is a proper group:
>>> H = PermutationGroup(G[0], G[1]) >>> J = PermutationGroup(list(H.generate())); J PermutationGroup([ (0 1)(2 3), (1 2 3), (1 3 2), (0 3 1), (0 2 3), (0 3)(1 2), (0 1 3), (3)(0 2 1), (0 3 2), (3)(0 1 2), (0 2)(1 3)]) >>> _.is_group True
- generate_dimino(af=False)[source]#
Yield group elements using Dimino’s algorithm.
If
af == True
it yields the array form of the permutations.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([0, 2, 3, 1]) >>> g = PermutationGroup([a, b]) >>> list(g.generate_dimino(af=True)) [[0, 1, 2, 3], [0, 2, 1, 3], [0, 2, 3, 1], [0, 1, 3, 2], [0, 3, 2, 1], [0, 3, 1, 2]]
References
- R64
The Implementation of Various Algorithms for Permutation Groups in the Computer Algebra System: AXIOM, N.J. Doye, M.Sc. Thesis
- generate_schreier_sims(af=False)[source]#
Yield group elements using the Schreier-Sims representation in coset_rank order
If
af = True
it yields the array form of the permutationsExamples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([0, 2, 3, 1]) >>> g = PermutationGroup([a, b]) >>> list(g.generate_schreier_sims(af=True)) [[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 2, 1], [0, 1, 3, 2], [0, 2, 3, 1], [0, 3, 1, 2]]
- generator_product(g, original=False)[source]#
Return a list of strong generators \([s1, \dots, sn]\) s.t \(g = sn \times \dots \times s1\). If
original=True
, make the list contain only the original group generators
- property generators#
Returns the generators of the group.
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.generators [(1 2), (2)(0 1)]
- property identity#
Return the identity element of the permutation group.
- index(H)[source]#
Returns the index of a permutation group.
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation(1,2,3) >>> b =Permutation(3) >>> G = PermutationGroup([a]) >>> H = PermutationGroup([b]) >>> G.index(H) 3
- property is_abelian#
Test if the group is Abelian.
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.is_abelian False >>> a = Permutation([0, 2, 1]) >>> G = PermutationGroup([a]) >>> G.is_abelian True
- is_alt_sym(eps=0.05, _random_prec=None)[source]#
Monte Carlo test for the symmetric/alternating group for degrees >= 8.
Explanation
More specifically, it is one-sided Monte Carlo with the answer True (i.e., G is symmetric/alternating) guaranteed to be correct, and the answer False being incorrect with probability eps.
For degree < 8, the order of the group is checked so the test is deterministic.
Notes
The algorithm itself uses some nontrivial results from group theory and number theory: 1) If a transitive group
G
of degreen
contains an element with a cycle of lengthn/2 < p < n-2
forp
a prime,G
is the symmetric or alternating group ([1], pp. 81-82) 2) The proportion of elements in the symmetric/alternating group having the property described in 1) is approximately \(\log(2)/\log(n)\) ([1], p.82; [2], pp. 226-227). The helper function_check_cycles_alt_sym
is used to go over the cycles in a permutation and look for ones satisfying 1).Examples
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> D = DihedralGroup(10) >>> D.is_alt_sym() False
See also
- property is_alternating#
Return
True
if the group is alternating.Examples
>>> from sympy.combinatorics import AlternatingGroup >>> g = AlternatingGroup(5) >>> g.is_alternating True
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> g = PermutationGroup( ... Permutation(0, 1, 2, 3, 4), ... Permutation(2, 3, 4)) >>> g.is_alternating True
Notes
This uses a naive test involving the computation of the full group order. If you need more quicker taxonomy for large groups, you can use
PermutationGroup.is_alt_sym()
. However,PermutationGroup.is_alt_sym()
may not be accurate and is not able to distinguish between an alternating group and a symmetric group.See also
- property is_cyclic#
Return
True
if the group is Cyclic.Examples
>>> from sympy.combinatorics.named_groups import AbelianGroup >>> G = AbelianGroup(3, 4) >>> G.is_cyclic True >>> G = AbelianGroup(4, 4) >>> G.is_cyclic False
Notes
If the order of a group \(n\) can be factored into the distinct primes \(p_1, p_2, \dots , p_s\) and if
\[\forall i, j \in \{1, 2, \dots, s \}: p_i \not \equiv 1 \pmod {p_j}\]holds true, there is only one group of the order \(n\) which is a cyclic group [R65]. This is a generalization of the lemma that the group of order \(15, 35, \dots\) are cyclic.
And also, these additional lemmas can be used to test if a group is cyclic if the order of the group is already found.
If the group is abelian and the order of the group is square-free, the group is cyclic.
If the order of the group is less than \(6\) and is not \(4\), the group is cyclic.
If the order of the group is prime, the group is cyclic.
References
- is_elementary(p)[source]#
Return
True
if the 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
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1]) >>> G = PermutationGroup([a]) >>> G.is_elementary(2) True >>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([3, 1, 2, 0]) >>> G = PermutationGroup([a, b]) >>> G.is_elementary(2) True >>> G.is_elementary(3) False
- property is_nilpotent#
Test if the group is nilpotent.
Explanation
A group \(G\) is nilpotent if it has a central series of finite length. Alternatively, \(G\) is nilpotent if its lower central series terminates with the trivial group. Every nilpotent group is also solvable ([1], p.29, [12]).
Examples
>>> from sympy.combinatorics.named_groups import (SymmetricGroup, ... CyclicGroup) >>> C = CyclicGroup(6) >>> C.is_nilpotent True >>> S = SymmetricGroup(5) >>> S.is_nilpotent False
See also
- is_normal(gr, strict=True)[source]#
Test if
G=self
is a normal subgroup ofgr
.Explanation
G is normal in gr if for each g2 in G, g1 in gr,
g = g1*g2*g1**-1
belongs to G It is sufficient to check this for each g1 in gr.generators and g2 in G.generators.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([1, 2, 0]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G1 = PermutationGroup([a, Permutation([2, 0, 1])]) >>> G1.is_normal(G) True
- property is_perfect#
Return
True
if the group is perfect. A group is perfect if it equals to its derived subgroup.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation(1,2,3)(4,5) >>> b = Permutation(1,2,3,4,5) >>> G = PermutationGroup([a, b]) >>> G.is_perfect False
- property is_polycyclic#
Return
True
if a 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.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([2, 0, 1, 3]) >>> G = PermutationGroup([a, b]) >>> G.is_polycyclic True
- is_primitive(randomized=True)[source]#
Test if a group is primitive.
Explanation
A permutation group
G
acting on a setS
is called primitive ifS
contains no nontrivial block under the action ofG
(a block is nontrivial if its cardinality is more than1
).Notes
The algorithm is described in [1], p.83, and uses the function minimal_block to search for blocks of the form \(\{0, k\}\) for
k
ranging over representatives for the orbits of \(G_0\), the stabilizer of0
. This algorithm has complexity \(O(n^2)\) wheren
is the degree of the group, and will perform badly if \(G_0\) is small.There are two implementations offered: one finds \(G_0\) deterministically using the function
stabilizer
, and the other (default) produces random elements of \(G_0\) usingrandom_stab
, hoping that they generate a subgroup of \(G_0\) with not too many more orbits than \(G_0\) (this is suggested in [1], p.83). Behavior is changed by therandomized
flag.Examples
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> D = DihedralGroup(10) >>> D.is_primitive() False
See also
- property is_solvable#
Test if the group is solvable.
G
is solvable if its derived series terminates with the trivial group ([1], p.29).Examples
>>> from sympy.combinatorics.named_groups import SymmetricGroup >>> S = SymmetricGroup(3) >>> S.is_solvable True
See also
- is_subgroup(G, strict=True)[source]#
Return
True
if all elements ofself
belong toG
.If
strict
isFalse
then ifself
’s degree is smaller thanG
’s, the elements will be resized to have the same degree.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> from sympy.combinatorics import SymmetricGroup, CyclicGroup
Testing is strict by default: the degree of each group must be the same:
>>> p = Permutation(0, 1, 2, 3, 4, 5) >>> G1 = PermutationGroup([Permutation(0, 1, 2), Permutation(0, 1)]) >>> G2 = PermutationGroup([Permutation(0, 2), Permutation(0, 1, 2)]) >>> G3 = PermutationGroup([p, p**2]) >>> assert G1.order() == G2.order() == G3.order() == 6 >>> G1.is_subgroup(G2) True >>> G1.is_subgroup(G3) False >>> G3.is_subgroup(PermutationGroup(G3[1])) False >>> G3.is_subgroup(PermutationGroup(G3[0])) True
To ignore the size, set
strict
toFalse
:>>> S3 = SymmetricGroup(3) >>> S5 = SymmetricGroup(5) >>> S3.is_subgroup(S5, strict=False) True >>> C7 = CyclicGroup(7) >>> G = S5*C7 >>> S5.is_subgroup(G, False) True >>> C7.is_subgroup(G, 0) False
- property is_symmetric#
Return
True
if the group is symmetric.Examples
>>> from sympy.combinatorics import SymmetricGroup >>> g = SymmetricGroup(5) >>> g.is_symmetric True
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> g = PermutationGroup( ... Permutation(0, 1, 2, 3, 4), ... Permutation(2, 3)) >>> g.is_symmetric True
Notes
This uses a naive test involving the computation of the full group order. If you need more quicker taxonomy for large groups, you can use
PermutationGroup.is_alt_sym()
. However,PermutationGroup.is_alt_sym()
may not be accurate and is not able to distinguish between an alternating group and a symmetric group.See also
- is_transitive(strict=True)[source]#
Test if the group is transitive.
Explanation
A group is transitive if it has a single orbit.
If
strict
isFalse
the group is transitive if it has a single orbit of length different from 1.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([2, 0, 1, 3]) >>> G1 = PermutationGroup([a, b]) >>> G1.is_transitive() False >>> G1.is_transitive(strict=False) True >>> c = Permutation([2, 3, 0, 1]) >>> G2 = PermutationGroup([a, c]) >>> G2.is_transitive() True >>> d = Permutation([1, 0, 2, 3]) >>> e = Permutation([0, 1, 3, 2]) >>> G3 = PermutationGroup([d, e]) >>> G3.is_transitive() or G3.is_transitive(strict=False) False
- property is_trivial#
Test if the group is the trivial group.
This is true if the group contains only the identity permutation.
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> G = PermutationGroup([Permutation([0, 1, 2])]) >>> G.is_trivial True
- lower_central_series()[source]#
Return the lower central series for the group.
The lower central series for a group \(G\) is the series \(G = G_0 > G_1 > G_2 > \ldots\) where \(G_k = [G, G_{k-1}]\), i.e. every term after the first is equal to the commutator of \(G\) and the previous term in \(G1\) ([1], p.29).
- Returns
A list of permutation groups in the order \(G = G_0, G_1, G_2, \ldots\)
Examples
>>> from sympy.combinatorics.named_groups import (AlternatingGroup, ... DihedralGroup) >>> A = AlternatingGroup(4) >>> len(A.lower_central_series()) 2 >>> A.lower_central_series()[1].is_subgroup(DihedralGroup(2)) True
See also
- make_perm(n, seed=None)[source]#
Multiply
n
randomly selected permutations from pgroup together, starting with the identity permutation. Ifn
is a list of integers, those integers will be used to select the permutations and they will be applied in L to R order: make_perm((A, B, C)) will give CBA(I) where I is the identity permutation.seed
is used to set the seed for the random selection of permutations from pgroup. If this is a list of integers, the corresponding permutations from pgroup will be selected in the order give. This is mainly used for testing purposes.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a, b = [Permutation([1, 0, 3, 2]), Permutation([1, 3, 0, 2])] >>> G = PermutationGroup([a, b]) >>> G.make_perm(1, [0]) (0 1)(2 3) >>> G.make_perm(3, [0, 1, 0]) (0 2 3 1) >>> G.make_perm([0, 1, 0]) (0 2 3 1)
See also
- property max_div#
Maximum proper divisor of the degree of a permutation group.
Explanation
Obviously, this is the degree divided by its minimal proper divisor (larger than
1
, if one exists). As it is guaranteed to be prime, thesieve
fromsympy.ntheory
is used. This function is also used as an optimization tool for the functionsminimal_block
and_union_find_merge
.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> G = PermutationGroup([Permutation([0, 2, 1, 3])]) >>> G.max_div 2
See also
- minimal_block(points)[source]#
For a transitive group, finds the block system generated by
points
.Explanation
If a group
G
acts on a setS
, a nonempty subsetB
ofS
is called a block under the action ofG
if for allg
inG
we havegB = B
(g
fixesB
) orgB
andB
have no common points (g
movesB
entirely). ([1], p.23; [6]).The distinct translates
gB
of a blockB
forg
inG
partition the setS
and this set of translates is known as a block system. Moreover, we obviously have that all blocks in the partition have the same size, hence the block size divides|S|
([1], p.23). AG
-congruence is an equivalence relation~
on the setS
such thata ~ b
impliesg(a) ~ g(b)
for allg
inG
. For a transitive group, the equivalence classes of aG
-congruence and the blocks of a block system are the same thing ([1], p.23).The algorithm below checks the group for transitivity, and then finds the
G
-congruence generated by the pairs(p_0, p_1), (p_0, p_2), ..., (p_0,p_{k-1})
which is the same as finding the maximal block system (i.e., the one with minimum block size) such thatp_0, ..., p_{k-1}
are in the same block ([1], p.83).It is an implementation of Atkinson’s algorithm, as suggested in [1], and manipulates an equivalence relation on the set
S
using a union-find data structure. The running time is just above \(O(|points||S|)\). ([1], pp. 83-87; [7]).Examples
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> D = DihedralGroup(10) >>> D.minimal_block([0, 5]) [0, 1, 2, 3, 4, 0, 1, 2, 3, 4] >>> D.minimal_block([0, 1]) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
See also
_union_find_rep
,_union_find_merge
,is_transitive
,is_primitive
- minimal_blocks(randomized=True)[source]#
For a transitive group, return the list of all minimal block systems. If a group is intransitive, return \(False\).
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> from sympy.combinatorics.named_groups import DihedralGroup >>> DihedralGroup(6).minimal_blocks() [[0, 1, 0, 1, 0, 1], [0, 1, 2, 0, 1, 2]] >>> G = PermutationGroup(Permutation(1,2,5)) >>> G.minimal_blocks() False
See also
- normal_closure(other, k=10)[source]#
Return the normal closure of a subgroup/set of permutations.
- Parameters
other
a subgroup/list of permutations/single permutation
k
an implementation-specific parameter that determines the number of conjugates that are adjoined to
other
at once
Explanation
If
S
is a subset of a groupG
, the normal closure ofA
inG
is defined as the intersection of all normal subgroups ofG
that containA
([1], p.14). Alternatively, it is the group generated by the conjugatesx^{-1}yx
forx
a generator ofG
andy
a generator of the subgroup\left\langle S\right\rangle
generated byS
(for some chosen generating set for\left\langle S\right\rangle
) ([1], p.73).Examples
>>> from sympy.combinatorics.named_groups import (SymmetricGroup, ... CyclicGroup, AlternatingGroup) >>> S = SymmetricGroup(5) >>> C = CyclicGroup(5) >>> G = S.normal_closure(C) >>> G.order() 60 >>> G.is_subgroup(AlternatingGroup(5)) True
Notes
The algorithm is described in [1], pp. 73-74; it makes use of the generation of random elements for permutation groups by the product replacement algorithm.
See also
- orbit(alpha, action='tuples')[source]#
Compute the orbit of alpha \(\{g(\alpha) | g \in G\}\) as a set.
Explanation
The time complexity of the algorithm used here is \(O(|Orb|*r)\) where \(|Orb|\) is the size of the orbit and
r
is the number of generators of the group. For a more detailed analysis, see [1], p.78, [2], pp. 19-21. Here alpha can be a single point, or a list of points.If alpha is a single point, the ordinary orbit is computed. if alpha is a list of points, there are three available options:
‘union’ - computes the union of the orbits of the points in the list ‘tuples’ - computes the orbit of the list interpreted as an ordered tuple under the group action ( i.e., g((1,2,3)) = (g(1), g(2), g(3)) ) ‘sets’ - computes the orbit of the list interpreted as a sets
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([1, 2, 0, 4, 5, 6, 3]) >>> G = PermutationGroup([a]) >>> G.orbit(0) {0, 1, 2} >>> G.orbit([0, 4], 'union') {0, 1, 2, 3, 4, 5, 6}
See also
- orbit_rep(alpha, beta, schreier_vector=None)[source]#
Return a group element which sends
alpha
tobeta
.Explanation
If
beta
is not in the orbit ofalpha
, the function returnsFalse
. This implementation makes use of the schreier vector. For a proof of correctness, see [1], p.80Examples
>>> from sympy.combinatorics.named_groups import AlternatingGroup >>> G = AlternatingGroup(5) >>> G.orbit_rep(0, 4) (0 4 1 2 3)
See also
- orbit_transversal(alpha, pairs=False)[source]#
Computes a transversal for the orbit of
alpha
as a set.Explanation
For a permutation group \(G\), a transversal for the orbit \(Orb = \{g(\alpha) | g \in G\}\) is a set \(\{g_\beta | g_\beta(\alpha) = \beta\}\) for \(\beta \in Orb\). Note that there may be more than one possible transversal. If
pairs
is set toTrue
, it returns the list of pairs \((\beta, g_\beta)\). For a proof of correctness, see [1], p.79Examples
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> G = DihedralGroup(6) >>> G.orbit_transversal(0) [(5), (0 1 2 3 4 5), (0 5)(1 4)(2 3), (0 2 4)(1 3 5), (5)(0 4)(1 3), (0 3)(1 4)(2 5)]
See also
- orbits(rep=False)[source]#
Return the orbits of
self
, ordered according to lowest element in each orbit.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation(1, 5)(2, 3)(4, 0, 6) >>> b = Permutation(1, 5)(3, 4)(2, 6, 0) >>> G = PermutationGroup([a, b]) >>> G.orbits() [{0, 2, 3, 4, 6}, {1, 5}]
- order()[source]#
Return the order of the group: the number of permutations that can be generated from elements of the group.
The number of permutations comprising the group is given by
len(group)
; the length of each permutation in the group is given bygroup.size
.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> a = Permutation([1, 0, 2]) >>> G = PermutationGroup([a]) >>> G.degree 3 >>> len(G) 1 >>> G.order() 2 >>> list(G.generate()) [(2), (2)(0 1)]
>>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.order() 6
See also
- pointwise_stabilizer(points, incremental=True)[source]#
Return the pointwise stabilizer for a set of points.
Explanation
For a permutation group \(G\) and a set of points \(\{p_1, p_2,\ldots, p_k\}\), the pointwise stabilizer of \(p_1, p_2, \ldots, p_k\) is defined as \(G_{p_1,\ldots, p_k} = \{g\in G | g(p_i) = p_i \forall i\in\{1, 2,\ldots,k\}\}\) ([1],p20). It is a subgroup of \(G\).
Examples
>>> from sympy.combinatorics.named_groups import SymmetricGroup >>> S = SymmetricGroup(7) >>> Stab = S.pointwise_stabilizer([2, 3, 5]) >>> Stab.is_subgroup(S.stabilizer(2).stabilizer(3).stabilizer(5)) True
Notes
When incremental == True, rather than the obvious implementation using successive calls to
.stabilizer()
, this uses the incremental Schreier-Sims algorithm to obtain a base with starting segment - the given points.See also
- polycyclic_group()[source]#
Return the PolycyclicGroup instance with below parameters:
Explanation
pc_sequence
: Polycyclic sequence is formed by collecting all the missing generators between the adjacent groups in the derived series of given permutation group.pc_series
: Polycyclic series is formed by adding all the missing generators ofder[i+1]
inder[i]
, whereder
represents the derived series.relative_order
: A list, computed by the ratio of adjacent groups in pc_series.
- presentation(eliminate_gens=True)[source]#
Return an \(FpGroup\) presentation of the group.
The algorithm is described in [1], Chapter 6.1.
- random_pr(gen_count=11, iterations=50, _random_prec=None)[source]#
Return a random group element using product replacement.
Explanation
For the details of the product replacement algorithm, see
_random_pr_init
Inrandom_pr
the actual ‘product replacement’ is performed. Notice that if the attribute_random_gens
is empty, it needs to be initialized by_random_pr_init
.See also
- random_stab(alpha, schreier_vector=None, _random_prec=None)[source]#
Random element from the stabilizer of
alpha
.The schreier vector for
alpha
is an optional argument used for speeding up repeated calls. The algorithm is described in [1], p.81
- schreier_sims()[source]#
Schreier-Sims algorithm.
Explanation
It computes the generators of the chain of stabilizers \(G > G_{b_1} > .. > G_{b1,..,b_r} > 1\) in which \(G_{b_1,..,b_i}\) stabilizes \(b_1,..,b_i\), and the corresponding
s
cosets. An element of the group can be written as the product \(h_1*..*h_s\).We use the incremental Schreier-Sims algorithm.
Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.schreier_sims() >>> G.basic_transversals [{0: (2)(0 1), 1: (2), 2: (1 2)}, {0: (2), 2: (0 2)}]
- schreier_sims_incremental(base=None, gens=None, slp_dict=False)[source]#
Extend a sequence of points and generating set to a base and strong generating set.
- Parameters
base
The sequence of points to be extended to a base. Optional parameter with default value
[]
.gens
The generating set to be extended to a strong generating set relative to the base obtained. Optional parameter with default value
self.generators
.slp_dict
If \(True\), return a dictionary \({g: gens}\) for each strong generator \(g\) where \(gens\) is a list of strong generators coming before \(g\) in \(strong_gens\), such that the product of the elements of \(gens\) is equal to \(g\).
- Returns
(base, strong_gens)
base
is the base obtained, andstrong_gens
is the strong generating set relative to it. The original parametersbase
,gens
remain unchanged.
Examples
>>> from sympy.combinatorics.named_groups import AlternatingGroup >>> from sympy.combinatorics.testutil import _verify_bsgs >>> A = AlternatingGroup(7) >>> base = [2, 3] >>> seq = [2, 3] >>> base, strong_gens = A.schreier_sims_incremental(base=seq) >>> _verify_bsgs(A, base, strong_gens) True >>> base[:2] [2, 3]
Notes
This version of the Schreier-Sims algorithm runs in polynomial time. There are certain assumptions in the implementation - if the trivial group is provided,
base
andgens
are returned immediately, as any sequence of points is a base for the trivial group. If the identity is present in the generatorsgens
, it is removed as it is a redundant generator. The implementation is described in [1], pp. 90-93.See also
- schreier_sims_random(base=None, gens=None, consec_succ=10, _random_prec=None)[source]#
Randomized Schreier-Sims algorithm.
- Parameters
base
The sequence to be extended to a base.
gens
The generating set to be extended to a strong generating set.
consec_succ
The parameter defining the probability of a wrong answer.
_random_prec
An internal parameter used for testing purposes.
- Returns
(base, strong_gens)
base
is the base andstrong_gens
is the strong generating set relative to it.
Explanation
The randomized Schreier-Sims algorithm takes the sequence
base
and the generating setgens
, and extendsbase
to a base, andgens
to a strong generating set relative to that base with probability of a wrong answer at most \(2^{-consec\_succ}\), provided the random generators are sufficiently random.Examples
>>> from sympy.combinatorics.testutil import _verify_bsgs >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> S = SymmetricGroup(5) >>> base, strong_gens = S.schreier_sims_random(consec_succ=5) >>> _verify_bsgs(S, base, strong_gens) True
Notes
The algorithm is described in detail in [1], pp. 97-98. It extends the orbits
orbs
and the permutation groupsstabs
to basic orbits and basic stabilizers for the base and strong generating set produced in the end. The idea of the extension process is to “sift” random group elements through the stabilizer chain and amend the stabilizers/orbits along the way when a sift is not successful. The helper function_strip
is used to attempt to decompose a random group element according to the current state of the stabilizer chain and report whether the element was fully decomposed (successful sift) or not (unsuccessful sift). In the latter case, the level at which the sift failed is reported and used to amendstabs
,base
,gens
andorbs
accordingly. The halting condition is forconsec_succ
consecutive successful sifts to pass. This makes sure that the currentbase
andgens
form a BSGS with probability at least \(1 - 1/\text{consec\_succ}\).See also
- schreier_vector(alpha)[source]#
Computes the schreier vector for
alpha
.Explanation
The Schreier vector efficiently stores information about the orbit of
alpha
. It can later be used to quickly obtain elements of the group that sendalpha
to a particular element in the orbit. Notice that the Schreier vector depends on the order in which the group generators are listed. For a definition, see [3]. Since list indices start from zero, we adopt the convention to use “None” instead of 0 to signify that an element does not belong to the orbit. For the algorithm and its correctness, see [2], pp.78-80.Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([2, 4, 6, 3, 1, 5, 0]) >>> b = Permutation([0, 1, 3, 5, 4, 6, 2]) >>> G = PermutationGroup([a, b]) >>> G.schreier_vector(0) [-1, None, 0, 1, None, 1, 0]
See also
- stabilizer(alpha)[source]#
Return the stabilizer subgroup of
alpha
.Explanation
The stabilizer of \(\alpha\) is the group \(G_\alpha = \{g \in G | g(\alpha) = \alpha\}\). For a proof of correctness, see [1], p.79.
Examples
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> G = DihedralGroup(6) >>> G.stabilizer(5) PermutationGroup([ (5)(0 4)(1 3)])
See also
- property strong_gens#
Return a strong generating set from the Schreier-Sims algorithm.
Explanation
A generating set \(S = \{g_1, g_2, \dots, g_t\}\) for a permutation group \(G\) is a strong generating set relative to the sequence of points (referred to as a “base”) \((b_1, b_2, \dots, b_k)\) if, for \(1 \leq i \leq k\) we have that the intersection of the pointwise stabilizer \(G^{(i+1)} := G_{b_1, b_2, \dots, b_i}\) with \(S\) generates the pointwise stabilizer \(G^{(i+1)}\). The concepts of a base and strong generating set and their applications are discussed in depth in [1], pp. 87-89 and [2], pp. 55-57.
Examples
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> D = DihedralGroup(4) >>> D.strong_gens [(0 1 2 3), (0 3)(1 2), (1 3)] >>> D.base [0, 1]
See also
- strong_presentation()[source]#
Return a strong finite presentation of group. The generators of the returned group are in the same order as the strong generators of group.
The algorithm is based on Sims’ Verify algorithm described in [1], Chapter 6.
Examples
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> P = DihedralGroup(4) >>> G = P.strong_presentation() >>> P.order() == G.order() True
See also
- subgroup(gens)[source]#
Return the subgroup generated by \(gens\) which is a list of elements of the group
- subgroup_search(prop, base=None, strong_gens=None, tests=None, init_subgroup=None)[source]#
Find the subgroup of all elements satisfying the property
prop
.- Parameters
prop
The property to be used. Has to be callable on group elements and always return
True
orFalse
. It is assumed that all group elements satisfyingprop
indeed form a subgroup.base
A base for the supergroup.
strong_gens
A strong generating set for the supergroup.
tests
A list of callables of length equal to the length of
base
. These are used to rule out group elements by partial base images, so thattests[l](g)
returns False if the elementg
is known not to satisfy prop base on where g sends the firstl + 1
base points.init_subgroup
if a subgroup of the sought group is known in advance, it can be passed to the function as this parameter.
- Returns
res
The subgroup of all elements satisfying
prop
. The generating set for this group is guaranteed to be a strong generating set relative to the basebase
.
Explanation
This is done by a depth-first search with respect to base images that uses several tests to prune the search tree.
Examples
>>> from sympy.combinatorics.named_groups import (SymmetricGroup, ... AlternatingGroup) >>> from sympy.combinatorics.testutil import _verify_bsgs >>> S = SymmetricGroup(7) >>> prop_even = lambda x: x.is_even >>> base, strong_gens = S.schreier_sims_incremental() >>> G = S.subgroup_search(prop_even, base=base, strong_gens=strong_gens) >>> G.is_subgroup(AlternatingGroup(7)) True >>> _verify_bsgs(G, base, G.generators) True
Notes
This function is extremely lengthy and complicated and will require some careful attention. The implementation is described in [1], pp. 114-117, and the comments for the code here follow the lines of the pseudocode in the book for clarity.
The complexity is exponential in general, since the search process by itself visits all members of the supergroup. However, there are a lot of tests which are used to prune the search tree, and users can define their own tests via the
tests
parameter, so in practice, and for some computations, it’s not terrible.A crucial part in the procedure is the frequent base change performed (this is line 11 in the pseudocode) in order to obtain a new basic stabilizer. The book mentiones that this can be done by using
.baseswap(...)
, however the current implementation uses a more straightforward way to find the next basic stabilizer - calling the function.stabilizer(...)
on the previous basic stabilizer.
- sylow_subgroup(p)[source]#
Return a p-Sylow subgroup of the group.
The algorithm is described in [1], Chapter 4, Section 7
Examples
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> from sympy.combinatorics.named_groups import AlternatingGroup
>>> D = DihedralGroup(6) >>> S = D.sylow_subgroup(2) >>> S.order() 4 >>> G = SymmetricGroup(6) >>> S = G.sylow_subgroup(5) >>> S.order() 5
>>> G1 = AlternatingGroup(3) >>> G2 = AlternatingGroup(5) >>> G3 = AlternatingGroup(9)
>>> S1 = G1.sylow_subgroup(3) >>> S2 = G2.sylow_subgroup(3) >>> S3 = G3.sylow_subgroup(3)
>>> len1 = len(S1.lower_central_series()) >>> len2 = len(S2.lower_central_series()) >>> len3 = len(S3.lower_central_series())
>>> len1 == len2 True >>> len1 < len3 True
- property transitivity_degree#
Compute the degree of transitivity of the group.
Explanation
A permutation group \(G\) acting on \(\Omega = \{0, 1, \dots, n-1\}\) is
k
-fold transitive, if, for any \(k\) points \((a_1, a_2, \dots, a_k) \in \Omega\) and any \(k\) points \((b_1, b_2, \dots, b_k) \in \Omega\) there exists \(g \in G\) such that \(g(a_1) = b_1, g(a_2) = b_2, \dots, g(a_k) = b_k\) The degree of transitivity of \(G\) is the maximumk
such that \(G\) isk
-fold transitive. ([8])Examples
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([1, 2, 0]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.transitivity_degree 3
See also