PermutationGroup


Basics

  • PermutationGroup represents a group of permutations.
  • Redberry can handle permutation groups with degree in the range of a few thousand, hence working with groups with more than $10^{1000}$ elements.
  • PermutationGroup can be specified by its generating set:

def gen1 = [[1, 4, 5]].p
def gen2 = [[2, 3]].p
def group = Group(gen1, gen2)
//print all group elements
group.each { println it }
   > +[]
   > +[[2, 3]]
   > +[[1, 5, 4]]
   > +[[1, 5, 4], [2, 3]]
   > +[[1, 4, 5]]
   > +[[1, 4, 5], [2, 3]]

  • One can construct a special kinds of PermutationGroup: symmetric or alternating by using SymmetricGroup(degree) and AlternatingGroup(degree) respectively:

def sym69 = SymmetricGroup(69)
println sym69.order()
   > 17112245242814131137246833888127283909227054489352036939364804092325
        7279754140647424000000000000000
def alt54 = AlternatingGroup(54)
println alt54.order()
   > 115421848669620690236046371341513790541639282285903970566144000000000000

  • PermutationGroup provides a number of common methods for working wih permutation groups: membership testing, coset enumeration, searching for centralizers, stabilizers, etc. One can find many examples in below subsections.

Examples

Let us consider some common features of PermutationGroup by a particular examples. Consider the following permutation group:

//first generator in cycle notation
def perm1 = [[1,28,5,3,13,25,8,4,17,11,29,7,2,21,23,10,6],
              [9,16,22,30,18,15,20,19,14]].p
//second generator in cycle notation
def perm2 = [[1, 4, 27], [2, 5, 3]].p
//create group 
def group = Group(perm1, perm2)


  • Print group order (i.e. number of all elements):

println group.order()
   > 28810681675776000


  • Get orbit of some point:

println group.orbit(20)
   > [9, 16, 22, 30, 18, 15, 20, 19, 14]


  • Get a pointwise stabilizer (i.e. subgroup that fixes specified points)

def pStabilizer =  group.pointwiseStabilizer(3, 25, 27)
println pStabilizer
   > Group( +[[9, 16, 22, 30, 18, 15, 20, 19, 14]],
            +[[1, 17, 11, 21, 23, 28, 5, 29, 7, 2, 13, 8, 4, 10, 6]],
            +[[1, 29, 2, 17, 7, 6, 23, 8, 21, 13, 11], [4, 10, 28]])
println pStabilizer.order()
   > 5884534656000


  • Check membership (i.e. whether some permutation belongs to PermutationGroup)

def p = [[1, 28, 2, 8, 27, 10, 11], [21, 29, 23]].p
println group.membershipTest(p)
   > true
def n = [[7, 19, 5, 17, 3, 4, 21, 25]].p
println group.membershipTest(n)
   > false


  • Calculate a setwise stabiliser (i.e. a subgroup that fixes a set as a whole):

def sStabilizer = group.setwiseStabilizer(3, 27, 25)
println sStabilizer 
   > Group( +[[9, 16, 22, 30, 18, 15, 20, 19, 14]],
               +[[1, 17, 11, 21, 23, 28, 5, 29, 7, 2, 13, 8, 4, 10, 6]],
               +[[1, 29, 2, 17, 7, 6, 23, 8, 21, 13, 11], [4, 10, 28]],
               +[[1, 4], [25, 27]], +[[1, 4], [3, 25]] )
println sStabilizer.order()
   > 35307207936000


  • Calculate derived subgroup (i.e. a commutator subgroup of group with itself):

def dSubgroup = group.derivedSubgroup()
println dSubgroup.order()
 
   > 3201186852864000


  • Define some other group and check whether it is a subgroup of group:

def oth = Group([[1, 17, 12, 19], [23, 25]].p, [[4, 14, 26]].p)
println group.containsSubgroup(oth)
 
   > false


  • Calculate union of groups:

def union = group.union(oth)
assert union.containsSubgroup(group)
assert union.containsSubgroup(oth)

println union.order()
 
   > 4420880996869850977271808000000


  • Calculate intersection of groups:

def intersection = union.intersection(group)
assert intersection == group
 


  • Calculate coset representatives:

println sStabilizer.leftCosetRepresentatives(pStabilizer)
 
   > [+[],
          +[[1, 4], [25, 27]],
          +[[1, 4], [3, 25]],
          +[[3, 25, 27]],
          +[[3, 27, 25]],
          +[[1, 4], [3, 27]]]


  • Calculate centralizer of subgroup:

println group.centralizerOf(sStabilizer)
 
   > Group( +[[9, 14, 19, 20, 15, 18, 30, 22, 16]] )

Features

General features

The following table lists relevant features of PermutationGroup:

.center() center of group.
.centralizerOf(perm) centralizer of permutation perm.
.centralizerOf(group). centralizer of subgroup group.
.commutator(oth) commutator with oth group.
.conjugate(perm) conjugation of group with specified permutation perm( i.e. $p^{-1} G p$, where $p$ is perm and $G$ is a group).
.containsSubgroup(oth) returns whether group contains subgroup oth.
.degree() natural degree of group, i.e. largest moved point plus one.
.derivedSubgroup() derived subgroup, i.e. commutator subgroup of group with itself.
. directProduct(oth) direct product of group oth group. This product is organized as follows: the initial segment of each permutation is equal to permutation taken from group, while the rest is taken from permutation of oth.
. equals(oth) returns whether group is equal to oth in mathematical sense.
.generators() a list of group generators.
. base base of group.
. getBSGS() low level representation of base and strong generating set.
. intersection(oth) intersection of group with oth.
. isAbelian() returns whether group is abelian.
. isAlternating() returns whether group is alternating.
. isRegular() returns whether group is regular (i.e. transitive and its order equals to degree).
. isSymmetric() returns whether group is symmetric.
. isTransitive() returns whether group is transitive.
. isTransitive(from, to) returns whether group acts transitively on the the range from (inclusive) to to (exclusive).
. isTrivial() returns whether group is trivial (contains only identity element).
. leftCosetRepresentatives(subgroup) array of left coset representatives of a subgroup.
. leftTransversalOf(subgroup, perm) a unique left coset representative of perm.
. mapping(from, to) iterator over permutations that maps from points on to.
. membershipTest(perm) returns whether perm belongs to group.
. normalClosureOf(subgroup) normal closure of specified subgroup.
. orbit(points) orbit of points.
.order() group order (i.e. number of all elements).
. pointwiseStabilizer(set) pointwise stabilizer of specified set of points.
. randomElement() uniformly distributed random element from group.
. rightCosetRepresentatives(subgroup) array of right coset representatives of a subgroup.
. setwiseStabilizer(set) pointwise stabilizer of specified set of points.
. union(oth) union of group and specified group (or set of generators), i.e. group which is generated by union of generators of group and oth.

Orbits

One can take an orbit of some point using method .orbit(point):

def perm1 = [[0, 7, 4, 2, 10], [8, 5, 9]].p
def perm2 = [[0, 3, 6], [1, 4, 2]].p
def group = Group(perm1, perm2)

println group.orbit(2)
   > [0, 7, 3, 4, 6, 2, 10, 1]
println group.orbit(5)
   > [5, 9, 8]
In order to take a list of all orbits one can do
def orbits = group.orbits()
println orbits
   > [[0, 7, 3, 4, 6, 2, 10, 1], [5, 9, 8]]
Given a list of all orbits, one can take an orbit of specified point by using array positionsInOrbits: an i-th element in this array is an index of orbit of i-th point in array of orbits:
def poss = group.positionsInOrbits
println poss
   > [0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0]
//orbit of 2
println orbits[poss[2]]
   > [0, 7, 3, 4, 6, 2, 10, 1]
//orbit of 5
println orbits[poss[5]]
   > [5, 9, 8]
//check
for (int i = 0; i < group.degree(); ++i)
    assert group.orbit(i) == orbits[poss[i]]

Details

The implementation of most PermutationGroup methods relies on base and strong generating set (BSGS). The algorithms such as used in calculation of groups intersections, centralizers etc. uses backtracking techniques.

Consider for example the stabilizers chain of Rubik group:

def rot1 = [[0, 2, 7, 5], [1, 4, 6, 3],
            [8, 47, 14, 11], [9, 46, 15, 12],
            [10, 45, 16, 13]].p
def rot2 = [[5, 14, 34, 25], [6, 21, 33, 18],
            [7, 29, 32, 10], [11, 13, 28, 26],
            [12, 20, 27, 19]].p
def rot3 = [[0, 11, 32, 40], [3, 19, 35, 43],
            [5, 26, 37, 45], [8, 10, 25, 23],
            [9, 18, 24, 17]].p
def rot4 = [[0, 23, 39, 16], [1, 17, 38, 22],
            [2, 8, 37, 31], [40, 42, 47, 45],
            [41, 44, 46, 43]].p
def rot5 = [[2, 42, 34, 13], [4, 44, 36, 20],
            [7, 47, 39, 28], [14, 16, 31, 29],
            [15, 22, 30, 21]].p
def rot6 = [[23, 26, 29, 42], [24, 27, 30, 41],
            [25, 28, 31, 40], [32, 34, 39, 37],
            [33, 36, 38, 35]].p

def RubikGroup = Group(rot1, rot2, rot3, rot4, rot5, rot6)
//order of Rubik group
println RubikGroup.order()
   > 43252003274489856000
Get base of group:
//get base of group
def base = RubikGroup.base
println base
   > [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32,33,34,2,23,22,24,4,
          30,17,3,1]
Let's print order of each stabilizer in stabilizers chain:
//print stabilizers chain
for (int i = 0; i < base.length; ++i) {
    //partial base
    def pBase = base[0..i] as int[]
    print('stab of ' + pBase + ' -> ')
    print(RubikGroup.pointwiseStabilizer(pBase).order())
    println ''
}
   > stab of [0] -> 1802166803103744000
   > stab of [0,5] -> 85817466814464000
   > stab of [0,5,6] -> 3575727783936000
   > stab of [0,5,6,7] -> 198651543552000
   > stab of [0,5,6,7,10] -> 198651543552000
   > stab of [0,5,6,7,10,11] -> 198651543552000
   > stab of [0,5,6,7,10,11,12] -> 198651543552000
   > stab of [0,5,6,7,10,11,12,13] -> 198651543552000
   > stab of [0,5,6,7,10,11,12,13,14] -> 198651543552000
   > stab of [0,5,6,7,10,11,12,13,14,18] -> 9029615616000
   > stab of [0,5,6,7,10,11,12,13,14,18,19] -> 9029615616000
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20] -> 451480780800
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21] -> 451480780800
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25] -> 30098718720
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26] -> 30098718720
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27] -> 1672151040
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28] -> 139345920
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29] -> 139345920
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32] -> 139345920
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32,33] ->  139345920
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32,33,34] -> 139345920
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32,33,34,2] -> 15482880
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32,33,34,2,23] -> 2580480
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32,33,34,2,23,22] -> 161280
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32,33,34,2,23,22,24] -> 11520
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32,33,34,2,23,22,24,4] -> 960
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32,33,34,2,23,22,24,4,30] -> 96
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32,33,34,2,23,22,24,4,30,17] -> 12
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32,33,34,2,23,22,24,4,30,17,3] -> 2
   > stab of [0,5,6,7,10,11,12,13,14,18,19,20,21,25,26,27,28,29,32,33,34,2,23,22,24,4,30,17,3,1] -> 1

The algorithms used in Redberry are described in:

  • Derek F. Holt, Bettina Eick, Eamonn A. O'Brien, Handbook Of Computational Group Theory, Chapman and Hall/CRC, 2005

The details on the internal implementation can be found in API.

See also