Cosets and Transversals

Cosets

H * g: GrpPerm, GrpPermElt -> Elt

Right coset of the subgroup \(H\) of the group \(G\), where \(g\) is an element of \(G\).

DoubleCoset(G, H, g, K): GrpPerm, GrpPerm, GrpPermElt, GrpPerm -> GrpPermDcosElt

The double coset \(H*g*K\) of the subgroups \(H\) and \(K\) of the group \(G\), where \(g\) is an element of \(G\).

DoubleCosetRepresentatives(G, H, K): GrpPerm, GrpPerm, GrpPerm -> SeqEnum, SeqEnum

Given a group \(G\) and two subgroups \(H\) and \(K\) of \(G\), return a sequence \(S\) containing representatives of the \(H\)-\(K\)-double cosets in \(G\). The first element of \(S\) is guaranteed to be the identity element of \(G\). The second return sequence gives the sizes of the corresponding double cosets. The algorithm used refines double cosets down a chain of subgroups from \(G\) to one of \(H\) or \(K\).

DoubleCosetCanonical(G, H, g, K: parameters): GrpPerm, GrpPerm, GrpPermElt, GrpPerm -> SeqEnum, SeqEnum
B: SeqEnum                    Default: 
M: GrpPerm                    Default: H meet K^(g^-1)

Returns a canonical base image for the double coset \(HgK\) in \(G\). The desired base may be supplied as parameter B, and M may be set as a subgroup of \(H\cap K^{g^{-1}}\). If this group is large then the calculation will go more quickly. If these parameters are not supplied then an appropriate value is computed. The return values are the canonical base image, and the base used. The base used for one calculation may be supplied as parameter B for another to avoid recalculation and ensure consistency of base image returned.

ProcessLadder(L, G, U): [GrpPerm], GrpPerm, GrpPerm -> Rec
DoubleCosets: Verbose                    Default: 3

Given permutation groups \(U<G\) and a sequence of permutation groups \(L\) such that \(L_1 = G\), compute data for computations with the \(L_n\)-\(U\)-double cosets in \(G\). The algorithm relies on the indices \((L_i : L_{i+1})\) (for \(L_i<L_{i+1}\)) or \((L_{i+1}:L_i)\) otherwise to be small. In contrast to the method used by DoubleCosetRepresentatives, the sequence used in the computation is a ladder, not necessarily a descending chain. For details see [Sch90a].

GetRep(p, R): GrpPermElt, Rec -> GrpPermElt

For \(R\) being the result of a call to ProcessLadder and a permutation \(p\in G\), return the canonical double coset representative for \(p\).

DeleteData(R): Rec

Deletes the data computed using ProcessLadder.

YoungSubgroupLadder(L): [RngIntElt] -> [GrpPerm]
Full: RngIntElt                    Default: false

Computes a ladder from the full symmetric group down to the Young subgroup parametrised by the sequence \(L\) suitable for double coset enumeration using ProcessLadder. The optional parameter Full can be used if the Young subgroup should be considered as a subgroup of the symmetric group on Full points rather than on \&*L.

StabilizerLadder(G, d): GrpPerm, RngMPolElt -> [GrpPerm]

Given a subgroup \(G\) of the symmetric group of degree \(n\) and a monomial in \(n\) indeterminates, compute a ladder down from the full symmetric group to the stabilizer of the monomial, suitable for processing with ProcessLadder.

x in C: GrpPermElt, Elt -> BoolElt

Returns true if element \(g\) of group \(G\) lies in the coset \(C\).

x notin C: GrpPermElt, Elt -> BoolElt

Returns true if element \(g\) of group \(G\) does not lie in the coset \(C\).

C₁ eq C₂: Elt, Elt -> BoolElt

Returns true if the coset \(C_1\) is equal to the coset \(C_2\).

C₁ ne C₂: Elt, Elt -> BoolElt

Returns true if the coset \(C_1\) is not equal to the coset \(C_2\).

# C: Elt -> RngIntElt

The cardinality of the coset \(C\).

CosetTable(G, H): Grp, Grp -> Map

The (right) coset table for \(G\) over subgroup \(H\) relative to its defining generators.

CosetTable(G, f): Grp, Map -> Map

The coset table for \(G\) corresponding to the permutation representation \(f\) of \(G\), where \(f\) is a homomorphism of \(G\) onto a transitive permutation group.

Transversals

Transversal(G, H): GrpPerm, GrpPerm -> {@ GrpPermElt  @}, Map
RightTransversal(G, H): GrpPerm, GrpPerm -> {@ GrpPermElt  @}, Map

Given a permutation group \(G\) and a subgroup \(H\) of \(G\), this function returns

(a)

An indexed set of elements \(T\) of \(G\) forming a right transversal for \(G\) over \(H\); and

(b)

The corresponding transversal mapping \(\phi: G \rightarrow T\). If \(T = [t_1, \ldots, t_r]\) and \(g \in G\), \(\phi\) is defined by \(\phi(g) = t_i\), where \(g\in H*t_i\).

TransversalProcess(G, H): GrpPerm, GrpPerm -> GrpPermTransProc

Given a permutation group \(G\) and \(H\), a subgroup of \(G\), create a process to run through a left transversal for \(H\) in \(G\). The method used is a backtrack search for a canonical coset representative. The intrinsic TransversalProcess can be used when the index of \(H\) in \(G\) is too large to allow a full transversal to be created.

TransversalProcessRemaining(P): GrpPermTransProc -> RngIntElt

The number of coset representatives the process has yet to produce. Initially this will be the index of the subgroup in the group.

TransversalProcessNext(P): GrpPermTransProc -> GrpPermElt

Advance the process to the next coset representative and return that representative. This may only be used when TransversalProcessRemaining(P) is positive. The first call to TransversalProcessNext will always give the identity element.

ShortCosets(p, H, G): GrpPermElt, GrpPerm, GrpPerm -> [GrpPermElt]

Computes a set of representatives for the transversal of \(G\) modulo \(H\) of all cosets that contain \(p\). This computation does not do a full transversal of \(G\) modulo \(H\) and may therefore be used even if the index of \((G:H)\) is very large.