Cosets and Transversals

Contents

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∩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∩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
    SetVerbose("DoubleCosets", n):      Maximum: 3
Given permutation groups U<G and a sequence of permutation groups L such that L1 = G, compute data for computations with the Ln-U-double cosets in G. The algorithm relies on the indices (Li : Li + 1) (for Li<Li + 1) or (Li + 1:Li) 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 [Sch90].
GetRep(p, R) : GrpPermElt, Rec -> GrpPermElt
For R being the result of a call to ProcessLadder and a permutation p∈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.
C1 eq C2 : Elt, Elt -> BoolElt
Returns true if the coset C1 is equal to the coset C2.
C1 ne C2 : Elt, Elt -> BoolElt
Returns true if the coset C1 is not equal to the coset C2.
# 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.
[Future release] 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 atbrace, Map
RightTransversal(G, H) : GrpPerm, GrpPerm -> {@ GrpPermElt atbrace, 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 φ: G -> T. If T = [t1, ..., tr] and g ∈G, φ is defined by φ(g) = ti, where g∈H * ti.
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.
V2.28, 13 July 2023