Computing labels of divisions of a group (awaiting review)

Given a maximal division of a group, we compute its label as follows.

If the division is large, we produce a pseudo-random sequence of group elements $g_j$ and order those divisions based on the smallest $j$ such that $g_j$ is an element of the division. The conjugacy class of $g_j$ also gives a first conjugacy class within the division, which is used below. A problem with using this method generally is that some groups contain maximal divisions which are still very small in comparison to the size of the group, so it may take a prohibitive amount of time to hit all of the divisions.

If the division is small, the basic approach is to enumerate elements and pick the smallest according to the total order on the elements of the group. If the division is small enough, we can do precisely this, but for medium-sized divisions we first attempt to narrow the number of elements considered by intersecting with non-normal subgroups of $G$. In order to make this process canonical, we use a modification of the big division process to choose a subgroup to intersect with. Note that $\textsf{Magma}$ can quickly compute the maximal subgroups of the group $G$.

Using the pseudo-random sequence of group elements, we record whether or not the elements are in each maximal subgroup as a vector of $0$'s and $1$'s ($1$ for when the element is in the subgroup). We generate enough elements so that the maximal subgroups are distinguished, sorting the maximal subgroups by these vectors, largest first. Then looking recursively at maximal subgroups of maximal subgroups, we can build part of the subgroup lattice of $G$ from the top down, always having an ordering for the newly constructed subgroups. In this process, we ignore subgroups where the relative index is greater than $1000$ as that would slow the computation. Paths down this lattice are then also ordered.

For small divisions, we intersect successively with maximal subgroups until the number of elements is relatively small (but positive). We can then enumerate elements and find the first one, based on the conversion of group elements to positive integers mentioned above. This both orders the divisions and picks a first conjugacy class within the division. Note that it is possible to track the number of elements in these intersections by using appropriate centralizers, so no enumeration is required until the number of elements drops below a threshold.

Once labels for maximal divisions are computed, we can compute labels and first elements for other classes. Working through the maximal divisions in order, we pick an element from its first conjugacy class $g$ and compute in sequence the classes of elements $g^i$ with $0<i<|g|$ and $\gcd(i, |g|)>1$. The order of the non-maximal divisions is simply the order in which they appear from this sequence (looping over divisions, and within that, powers of an element).