Reference request

[james-d-mitchell]

I wondered if someone could point me to a reference for the algorithms implemented in GAP for computing DoubleCosets of permutation groups? I tried googling, and looking in the source code but didn't find what I was looking for. I'd like to cite the reference if possible.

[MathieuDutSik]

Having worked for a C++ implementation of the double cosets myself (which is available at permutalib) and having read the GAP code extensively for many hours, I can comment a little on this.

The double coset decomposition of G into double cosets of the form UxV relies on the enumeration of the right cosets Ux of U in G:

• What you get from that enumeration is an efficient algorithm that allows you to find for a given x which coset Ux it belongs to.
• So, when you have all the cosets Ux, you make the group V act on it, and from the orbit decomposition, you get the double cosets by a simple enumeration. Moreover, and this is important for the following, you can compute the subgroup of V that stabilizes a right coset Ux.

That is the basic strategy. Of course, if the index of U in G is very large, that is a problem. What you can use is an ascending chain of subgroups (U_0, U_1,..., U_n) starting from U and ending at G. At the first step, you compute for U=U_{n-1}, V=V. At the next step, you work with U=U_{n-2} and V being the stabilizer of the right coset. You iterate, and then you are done.

In terms of reference, I did not find much that I like, but you can try:

• Linton, S. Double Coset Enumeration
• Neunhoffer, M. Orbits and double cosets (slides)
• Linton, S. Generalisation of the Todd-Coxeter Algorith (in Computational Algebra and Number Theory)

[james-d-mitchell]

Thanks for the reply, this is helpful, but I am really asking for a reference for the actual algorithm implemented in GAP. It's not clear to me from your answer how the references you mention are related to the implementation in GAP.

[fieker]

Probably not implemented in Gap, but especially for double cosets from combinatorics is Bern Schmalz's algorithm, using ladders:
Instead of using a chain of subgroup U_1 < U_2 < ... allow for up and downs, so U_n+1 can be smaller or larger than the predecessor as long as the index is small. He gives algorithms to fuse (and split) cosets accordingly. Sadly, all references I could find are non-findable and in German: the original Diploma Thesis:

Schmalz, Bernd: Verwendung von Untergruppenleitern zur Bestimmung von Doppelnebenklassen. In: Bayreuther Math. Schr. 31 (1990), S. 109 - 143

And a PhD referencing this: (see chapter 4)
https://epub.uni-bayreuth.de/id/eprint/2916/1/Dissertation_Matthias_Koch.pdf

Especially for combinatorics this can be extremely good.

[james-d-mitchell]

Thanks for the reply @fieker this is helpful, but same comment as above, I'd like to know what is actually implemented in GAP. Perhaps @hulpke or @fingolfin will know the answer?