Finding all quotients of the braid group $B_5$ up to order $720$

abstract-algebrabraid-groupsgapgroup-theoryknot-theory

Original Question. I am trying to find all quotients of the braid group $B_5$ on five strands up to order $6!=720$. From previous very slow implementations I found that there are not many. Some results I have at my disposal are the following.

  • All cyclic groups $C_n = \mathbb Z/n\mathbb Z$ are quotients of $B_5$ since the abelianization of $B_5$ is isomorphic to the integers $\mathbb Z$. With the same argument we obtain that non-cyclic abelian groups cannot be quotients of $B_5$.
  • One can construct an automorphism, namely conjugation by the image of $\delta = \sigma_1 \cdots \sigma_{n-1}$, of order divisible by $n$, yielding that all quotients of $B_5$ must have order divisible by $5$. Applying this to the subgroups $B_3$ and $B_4$ yields that any quotient of $B_5$ must have order divisible by $60$, which drastically (but not drastically enough) decreases the number of groups to check.
  • The permutation group $S_5$ is a quotient of $B_5$ by modding out the squares of the generators.
  • Implementations showed that a subdirect product $A_5 \rtimes C_4$ and a direct product $C_3 \times S_5$ are also quotients of $B_5$, but I do not know the explicit homomorphism.

What I tried is to use the function AllSmallGroups in GAP, which really does return all groups of the desired order very efficiently (presumably because they are stored in a pre-computed list). I then checked whether the list returned by GQuotients was non-empty, which is apperently quite expensive to compute. Considering I have to check thousands of groups this is a problem.

One approach I might have is to filter out the groups that have normal subgroups such that the quotient is non-cyclic and has order not divisible by $60$. Sadly, the method StructureDescription takes ages to run on groups of the magnitudes of orders I am intersted in, so I cannot really check this efficiently. Thus, to answer my question I guess it would be enough to answer the following.

How can you (more efficiently than using StructureDescription or the like) check whether a group returned by AllSmallGroups (or something similar) satisfies that the orders of all the quotients by its normal subgroups are divisible by $60$?

Update.
Alright, I managed to solve it. Here's the result: All non-cyclic quotients of order less than $720$ are either $A_5 \rtimes \mathbb Z/2^k \mathbb Z$ or $C_{2k+1} \times S_5$. What it took was the following (thanks @AlexanderKonovalov):

  1. Get a list of IDs of SmallGroups with IdsOfSmallGroups (less demanding on my workspace memory than using AllSmallGroups). This gave me about $3000$ groups.
  2. Filter out the abelian groups: very easy with the precomputed IsAbelian attribute. I'm actually not sure how important that was since it only reduced my count from about $3000$ to about $2900$ groups, but still.
  3. Getting the normal subgroups of all those groups with NormalSubgroups and checking whether all quotients were either cyclic or had order divisible by $60$. Throwing the rest away left me with $46$ groups.
  4. I then let my computer run for the whole day using GQuotients. It was able to check a remarkable $25$ groups during this time.
  5. I got a bit annoyed and ran StructureDescription on the group it was currently working at and found that it was working on a group that was somehow a direct product of $\mathbb Z/2\mathbb Z$ with some matrix group (which was previously identified as not a quotient). Since it only took a few seconds to run StructureDescription I decided to let it run on all of the remaining groups, and, miraculously, it finished this feat in half a minute or so.
  6. By hand I removed the ones that split as a direct product or a subdirect product the normal subgroup of which I knew was not a quotient, and had to run GQuotients on a single remaining group, which turned out to be not a quotient.

What occurred to me a little bit too late is that I could have introduced a step 2.5 checking whether the groups in question had a generating set consisting of only two elements. This would have reduced to groups from $2900$ to about $2000$, which would have saved maybe $5$ minutes of computing normal subgroups of stuff. But it turns out that all of the $46$ groups that required me to check by hand would not have been excluded by this step, so this is more of a side note.

Best Answer

This is rather a collection of hints, based on my earlier comments above:

1) Instead of using AllSmallGroups, you may find enumerating groups one by one more informative and convenient - see the Carpentries-style lesson on GAP, in particular this episode about the search in the Small Groups Library.

2) If you are only interested in the orders of all normal subgroups, instead of asking for StructureDescription you can call NormalSubgroups and then check their orders. For example, 

gap> AllSmallGroups(360,G->ForAll( NormalSubgroups(G), g -> Size(g)=1 or IsInt(Size(g)/60)));
[ Alt( [ 1 .. 6 ] ) ]

More tips if you are interested only in specific subgroups are in the GAP F.A.Q. It also has a question about StructureDescription.

3) Using SmallGroupsInformation, you can find out how the groups of the given order are sorted, and which information about their properties is precomputed. That could help to organise a sieving process, when you will have several passes over the list of candidates, increasing the complexity of the checked property.

4) If you have a multicore computer, or have access to several computers, you can try to set up a parallel master-worker calculation with the SCSCP package. I have a demo for the particular example of the small groups search here.

5) Another suggestion is that GQuotients has a documented findall option - if it is set to false, the algorithm will stop once one homomorphism has been found (this can be faster and might be sufficient if not all homomorphisms are needed). Although, as @Levi explained, this does not help in this case since there are only a few groups that actually are quotients.

6) Furthermore, representation matters. What are the arguments of GQuotients - are they fp, pc or permutation groups? fp groups are the slowest. You can use IsomorphismPcGroup or IsomorphismPermGroup to work with isomorphic groups with a faster internal representation - some examples are in this Jupyter notebook.

7) It is also recommended to run the latest official distribution of GAP, and have properly installed packages (some of them require compilation). Some packages may speed up certain calculations. In particular, GAP 4.10.0 has some improvements of GQuotients performance by @ahulpke (see this pull request on GitHub).

Related Question