# 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`

```magma
B: SeqEnum                    Default: 
M: GrpPerm                    Default: H\cap Kᵍ^-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`

```magma
verbose: DoubleCosets                    Default: Verbose : 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 [[Schmalz, 1990](../../references.md#cite-schmalz-ladder)].

### `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]`

```magma
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.