# Group subsets¶

RepLAB has FiniteSet as a base for all sets of elements coming originally from a finite group. Note that a FiniteGroup itself is also a FiniteSet.

Such subsets have a decomposition which speeds up many algorithms in RepLAB.

A finite group is partitioned into conjugacy classes.

A finite group can also be partitioned into cosets by one (or two!) of its subgroups.

## FiniteSet¶

class replab.FiniteSet

Bases: replab.Domain

Describes a subset of a finite group

Examples of finite subsets include:

If the finite set is not empty (nElements is nonzero), the set has a distinguished representative element. For permutation groups, this representative element is the minimal element under lexicographic ordering.

### Own members

representative_

Minimal member of this set under the type ordering. If the set is empty, value is undefined.

Type

element of type

type

Type of the contained elements

Type

FiniteGroupType

contains(self, el)

Tests whether this set contains the given element

The element must be part of type, as in the example below: only permutations with the same domain size should be tested using contains.

Example

>>> G = replab.PermutationGroup.of([2 3 4 1]);
>>> G.contains([4 3 2 1])
0

Parameters

el (element of type) – Element to test for membership

Returns

True if this set contains el and false otherwise

Return type

logical

elements(self)

Returns a cell array containing all the elements of this set

The sequence is sorted according to the total ordering defined by type.

Note: if the number of elements is bigger than replab.globals.maxElements, an error is thrown.

Returns

Elements

Return type

cell(1,*) of finite set elements

elementsSequence(self)

Returns a sequence corresponding to this set

The sequence is sorted according to the total ordering defined by type.

Returns

An enumeration of the set elements

Return type

Sequence

hasSameTypeAs(self, rhs)

Returns if this finite set has the same type as the given finite set

In particular, it means that the contains method of one set can be called with elements of the other set.

Parameters

rhs (replab.FiniteSet) – Other finite set

Returns

True if the groups have compatible types

Return type

logical

imap(self, f)

Returns the image of this finite set under an isomorphism

Parameters

f (FiniteIsomorphism) – Isomorphism such that this finite set is contained in f.source

Returns

This finite set mapped under f, expressed as a subset of f.image

Return type

FiniteSet

isequal(self, rhs)

Tests finite sets for equality

Alternative syntax to eq

Example

>>> G = replab.PermutationGroup.of([2 3 1], [2 1 3]);
>>> H = replab.PermutationGroup.of([2 1 3], [1 3 2]);
>>> isequal(G, H)
1

nElements(self)

Returns the size of this set

Returns

Set cardinality

Return type

vpi

representative(self)

Returns the minimal element of this set under the type ordering

Returns

Canonical representative of this set

Return type

element

setProduct(self)

Returns a description of this set as a product of sets

Returns

Generic description of the elements of this set

Return type

SetProduct

## SetProduct¶

class replab.SetProduct(monoid, sets, identityFirst)

Bases: replab.Domain

Describes a multiset of elements obtained by reduction of the elements of a cartesian product

Let T1, ..., Tn be finite subsets of a monoid G. The set product of such T is the multiset of elements of the form x = t1 t2 ... tn iterating over each ti in each Ti. The binary operation is given by the composition of G.

Thus, the multiset has |T1| * |T2| * ... * |Tn| elements, possibly with repetition.

RepLAB uses SetProduct in two areas:

• to describe a unique decomposition of a finite group, in which case the multiset is actually a set whose cardinality is the group order; we additionally require that the first element of each T{i} is the identity;

• to describe the left cosets of the connected component in a compact Lie group.

### Own members

identityFirst

True if each element T contains the identity as its first element

Type

logical

monoid

Monoid providing the binary operation

Type

replab.Monoid

sets

Stores the sets Ti as {T1 T2 ... Tn}

Type

cell(1,*) of cell(1,*) of elements

static identity(monoid)

Constructs a SetProduct containing only the identity of a monoid

Parameters

monoid (Monoid) – Monoid to take the identity from

Returns

A singleton SetProduct

Return type

SetProduct

imap(self, isomorphism)

Maps this multiset under an isomorphism

Parameters

isomorphism (Isomorphism) – Isomorphism with its containing all elements of this SetProduct

Returns

Multiset with elements in isomorphism.target

Return type

SetProduct

## ConjugacyClasses¶

class replab.ConjugacyClasses(group, classes)

Bases: replab.Obj

Stores information about the conjugacy classes of a group

This class can compute power maps.

### Own members

classes

Conjugacy classes

Type

cell(1,nC) of ConjugacyClass

group

Group whose conjugacy classes we describe

Type

FiniteGroup

primePowerMap

Power maps (computed as needed)

Type

integer(nP,nC)

primes

List of primes that divide the group order (computed as needed)

Type

integer(1,nP)

centralizerSizes(self)

Returns the sizes of the centralizers

Returns

Size of the centralizer for each conjugacy class

Return type

cell(1,*) of vpi

classElementOrders(self)

Returns the element order for each of the conjugacy classes

Returns

Elements orders

Return type

integer(1,*)

classIndexOf(self, g, varargin)

Finds the conjugacy class where a given element is located

Parameters
• g (element of group) – Group element

• isCanonical – Whether the given g is the class canonical representative, default: false

Kwtype isCanonical

logical, optional

Returns

Index of the class containing g

Return type

integer

classRepresentatives(self)

Returns the canonical representatives of the conjugacy classes

Returns

Representatives

Return type

cell(1,*) of ConjugacyClass

classSizes(self)

Returns the sizes of the conjugacy classes

Returns

Size of each conjugacy class

Return type

cell(1,*) of vpi

imap(self, f)

Maps the conjugacy classes under an isomorphism

Parameters

f (FiniteIsomorphism) – Isomorphism with self.group.isSubgroupOf(f.source)

Returns

The conjugacy classes mapped under f, expressed as a subset of f.image

Return type

ConjugacyClasses

indicesOfClasses(self, classes)

Returns the indices of the given conjugacy classes in this list

Parameters

classes (ConjugacyClasses) – Conjugacy classes of group

Returns

Indices of the given classes in these classes

Return type

integer(1,*)

nClasses(self)

Returns the number of conjugacy classes in the group

Returns

Number of classes

Return type

integer

normalSubgroupClasses(self, indices)

Returns the normal subgroup consisting of the conjugacy classes whose positions are given

Parameters

indices (integer(1,*)) – Indices of conjugacy classes

Returns

Normal subgroup representing that union

Return type

FiniteGroup

powerMap(self, n)

Returns the power map corresponding to the given exponent

We have m(i) = self.classIndexOf(self.group.composeN(self.classes{i}.representative, n)).

Parameters

p (integer) – Exponent

Returns

Index of the power of each conjugacy class

Return type

integer(1,*)

powerMapDefaultPrimes(self)

Returns the list of primes that are necessary to reconstruct any power map

Returns

Prime numbers that are less or equal to the largest class element order

Return type

integer(1,*)

powerMapMatrix(self)

Returns an adjacency-like matrix that describes (incomplete) relationships between conjugacy classes

powerMaps(self, exponents)

Returns or computes&stores the power map corresponding to the given exponent

Parameters

exponents (integer(1,*)) – Exponents

Returns

Index of the power of each conjugacy class

Return type

integer(length(exponents),*)

## ConjugacyClass¶

class replab.ConjugacyClass

Describes a conjugacy class of a finite group

A conjugacy class containing the representative $$r \in G$$ is the set $$\{g r g^{-1} : g \in G \}$$.

The centralizer of $$r$$ in $$G$$ is the subgroup $$C_{G}(r) = \{ g r g^{-1} == r : g \in G \}$$.

Thus, the left cosets $$G/C_{G}(r) = \{ g C_{G}(r) : g \in G \}$$ are in one to one correspondence with the elements of the conjugacy class.

### Own members

group

Group containing this conjugacy class

Type

replab.FiniteGroup

elementOrder(self)

Returns the order of the elements in this conjugacy class

Returns

Element order

Return type

integer

imap(self, f)

Maps this conjugacy class under an isomorphism

Parameters

f (FiniteIsomorphism) – Isomorphism with self.group.isSubgroupOf(f.source)

Returns

The conjugacy class mapped under f, expressed as a subset of f.image

Return type

ConjugacyClass

knownRepresentativeCentralizer(self)

Returns whether the centralizer of representative is known

Returns

True if the centralizer has already been computed

Return type

logical

representativeCentralizer(self)

Returns the centralizer of representative in group

Returns

Representative centralizer

Return type

FiniteGroup

## Cosets¶

class replab.Cosets

Bases: replab.Obj

Base class for the left/normal/right coset classes

This class is necessary because NormalCosets inherits from both LeftCosets or RightCosets, and thus they share the group and subgroup properties.

### Own members

group

Group

Type

FiniteGroup

subgroup

Subgroup of group

Type

FiniteGroup

nElements(self)

Returns the number of cosets

Returns

Number of cosets

Return type

integer

## Coset¶

class replab.Coset

Base class for the left/normal/right coset classes

This class is necessary because NormalCoset inherits from both LeftCoset or RightCoset, and thus they share the group and subgroup properties.

### Own members

group

Group containing this coset

Type

FiniteGroup

subgroup

Subgroup used to decompose group

Type

FiniteGroup

## CosetTable¶

class replab.CosetTable(generatorNames, internal)

Bases: replab.Str

Describes a coset table (experimental)

Example

>>> ct = replab.CosetTable.fromPresentation({'x' 'y'}, {'x^2','y^3','(x*y)^3'}, {'x*y'});
>>> ct.table.format
| x  y  inv(x)  inv(y)
--------------------------
1 | 2  2     2       3
2 | 1  3     1       1
3 | 4  1     4       2
4 | 3  4     3       4


Note

The action of words on cosets is a left action, contrary to the algorithms described in Holt. Thus, we implement the algorithms of Holt in a different class, which matches the pseudocode closely. This class, however, translates between those conventions.

### Own members

generatorNames

Names of the generators

Type

cell(1,*) of charstring

internal

Internal coset table

Type

replab.fp.CosetTable

static fromPresentation(generatorNames, relatorWords, subgroupGeneratorWords)

Enumerate cosets

Parameters
• generatorNames (cell(1,*) of charstring) – Group generator names

• relatorWords (cell(1,*) of charstring) – Group relators to parse

• subgroupGeneratorWords (cell(1, *) of charstring) – Generators for a subgroup, expressed as words in the group generators

table(self)

Returns the coset table as a prettyprintable table

Returns

String table

Return type

replab.str.Table

## LeftCosets¶

class replab.LeftCosets

Bases: replab.Cosets

Describes the set of left cosets of a finite group

Let $$H$$ be a subgroup of a group $$G$$. Then the left cosets are the sets $$g H = \{ g h : h \in H \}$$. The set of such left cosets is often written $$G / H = \{ g H : g \in G \}$$.

### Own members

cosetRepresentative(self, g)

Returns the canonical coset representative corresponding to the given element

If t = cosetRepresentative(g), then $$t^{-1} g = h \in H$$, with decomposition $$g = t h$$.

Moreover L.cosetRepresentative(g) == L.cosetRepresentative(compose(g, h)) for any $$h \in H$$.

Finally, L.cosetRepresentative(g) == L.coset(g).representative.

Parameters

g (element of group) – Group element

Returns

Coset canonical representative

Return type

t (element of group)

elements(self)

Returns the set of left cosets as a cell array

Returns

Set of left cosets

Return type

cell(1,*) of replab.LeftCoset

leftAction(self)

Returns, as a morphism, the action of the given group of its left cosets

Returns

Morphism of this group into a permutation group

Return type

FiniteMorphism

transversal(self)

Returns all the canonical representatives of cosets

Returns

Transversal

Return type

cell(1, *) of group elements

## RightCosets¶

class replab.RightCosets

Bases: replab.Cosets

Describes the set of right cosets of a nice finite group

Let $$H$$ be a subgroup of a group $$G$$. Then the right cosets are the sets $$H g = \{ h g : h \in H \}$$. The set of such right cosets is often written $$H \\ G = \{ H g : g \in G \}$$.

### Own members

cosetRepresentative(self, g)

Returns the coset representative corresponding to the given element

If t = cosetRepresentative(g), then $$g t^{-1} = h \in H$$, with the decomposition $$g = h t$$.

Moreover R.cosetRepresentative(g) == R.cosetRepresentative(compose(h, g)) for any $$h \in H$$.

Finally, R.cosetRepresentative(g) == R.coset(g).representative.

Parameters

g (element of group) – Group element

Returns

Coset canonical representative

Return type

t (element of group)

elements(self)

Returns the set of right cosets as a cell array

Returns

Set of right cosets

Return type

cell(1,*) of replab.RightCoset

transversal(self)

Returns all the canonical representatives of cosets

Returns

Transversal

Return type

cell(1, *) of group elements

## NormalCosets¶

class replab.NormalCosets

Describes the set of normal cosets of a finite group

Let $$H$$ be a normal subgroup of a group $$G$$. Then the left cosets are the sets $$g H = \{ g h : h \in H \}$$. Then the right cosets are the sets $$H g = \{ h g : h \in H \}$$. Because the subgroup is normal, we have $$g H = H g$$.

### Own members

elements(self)

Returns the set of normal cosets as a cell array

Returns

Set of normal cosets

Return type

cell(1,*) of replab.NormalCoset

## LeftCoset¶

class replab.LeftCoset

Bases: replab.Coset

Describes a left coset of a finite group

Let $$g \in G$$ be a coset representative and $$H \le G$$ a group. The left coset is $$g H = \{ g h : h \in H\}$$.

## RightCoset¶

class replab.RightCoset

Bases: replab.Coset

Describes a right coset of a finite group

Let $$g \in G$$ be a coset representative and $$H \le G$$ a group. The right coset is $$H g = \{ h g : h \in H\}$$.

## NormalCoset¶

class replab.NormalCoset

Describes a coset in the normal subgroup of a finite group

It is a left and right coset at the same time.

See parent classes LeftCoset and RightCoset

## DoubleCosets¶

class replab.DoubleCosets

Bases: replab.Domain

Describes the set of double cosets in a group

A double coset is a set of the form { H g K } = { h g k : h \in H, k \in K} for subgroups H and K of a group G

### Own members

group

Group

Type

FiniteGroup

leftSubgroup

Subgroup of group

Type

FiniteGroup

rightSubgroup

Subgroup of group

Type

FiniteGroup

cosetRepresentative(self, g)

Returns the canonical coset representative corresponding to the given element

Parameters

g (element of group) – Group element

Returns

Double coset canonical representative

Return type

t (element of group)

elements(self)

Returns the set of double cosets as a cell array

Returns

Set of double cosets

Return type

cell(1,*) of replab.DoubleCoset

nElements(self)

Returns the number of double cosets

Returns

Number of double cosets

Return type

integer

transversal(self)

Returns all the canonical representatives of cosets

Returns

Transversal

Return type

cell(1, *) of group elements

## DoubleCoset¶

class replab.DoubleCoset

Describes a double coset in a group

A double coset is a set of the form { H g K } = { h g k : h \in H, k \in K} for subgroups H and K of a group G

### Own members

group

Group containing this double coset

Type

FiniteGroup

leftSubgroup

Group

Type

FiniteGroup

rightSubgroup

Group

Type

FiniteGroup