# Algorithm to find conjugacy classes of subgroups/elements (in matrix groups)?

I'm looking for a simple (=doable to implement by myself) algorithm to compute the conjugacy classes of elements and subgroups of a given subgroup of $\text{P}{\Gamma}\text{L}(n,q)$. So given a group $G\le \text{P}{\Gamma}\text{L}(n,q)$, find its conjugacy classes of elements, and/or its conjugacy classes of subgroups.

I know that GAP/Magma can do this, but I would like to do my own implementation (in Java) for various reasons. I store groups by their generators, Schreier-Sims chain and action on projective subspaces of $\text{PG}(n-1,q)$, and already have the code to compute set-wise stabilizers, isomorphisms and orbits (all on projective subspaces), so the use of these in any algorithm is free for me.

Given that a doable implementation is worth losing a $\mathcal O(\log|G|)$ factor (or similar) compared to GAP/Magma, what algorithm is most suited to use here? A reference to an algorithm in pseudo- code would be most welcome: Google failed to find me anything (even a paper), and trying to understand what GAP does internally is.. well.. horrible.

## 1 Answer

You are really trying to re-invent the wheel here. There is a lot of literature on this topic, and the algorithms have undergone successive refinement over the last 30-40 years, with the need to handle larger and larger groups.

If you want to handle arbitrary subgroups of ${\rm P \Gamma L}(n,q)$ then you might just as well use general permutation group algorithms. Two recent papers on this topic are:

J. Cannon and D. Holt, Computing conjugacy classes in permutation groups. J. Algebra, 300: 213-222, 2006.

A. Hulpke, Computing classes in permutation groups via homomorphic images. Math. Comp. 69 no. 232, 1633-1651, 2000.

For moderately small groups, the random element method is often as fast as anything, and should not be hard to implement. You just keep choosing random elements, test them for conjugacy with your existing class representatives, and keep going until you have a complete set, where you test for completeness by calculating the orders of their centralizers. Of course, to do that, you would first need to implement an algorithms for computing centralizers of elements in permutation groups, which would involve a backtrack search. A weakness of this method is that it can take a long time to find elements in classes that are small compared with the group order. It generally works well for groups that are close to being nonabelian simple, and poorly for groups that are close to being solvable.

The more refined methods that function well for many types of groups start by finding the largest solvable normal subgroup $L$ of your group $G$. You then start by finding class representatives of the quotient group $G/L$ (for which you could use the random element method in the first instance, but again there are more refined methods for larger groups). Having done that you find the classes of $G$ by successively "lifting" the classes through the elementary abelian layers of the terms in a chief series for $G$ that lie in $L$. This lifting method has been used for solvable groups (the special case $G=L$) since the 1980s. A reference for that is

M. Mecky and J. Neubuser, Some remarks on the computation of conjugacy classes of soluble groups. Bull. Austral. Math. Soc. 40:281-292, 1989.

• Ok, thanks a lot, I'll take a closer look at those references. What figures should I have in mind for "moderately small" (for the random element method), are we talking group orders 1000,10000,100000,1000000 here? PGammaL is highly non-solvable (since it contains PSL as a subgroup of small index, which is simple), so the same should hold for its subgroups, which speaks in favor of this random elements method. – user1111929 Sep 19 '12 at 1:29
• By the way, does something similar to this random elements method exist for conjugacy classes of subgroups too? – user1111929 Sep 19 '12 at 1:30
• As I said, the method works best for groups that are close to being simple. For $g \in G$, the probability that a random element of $G$ is conjugate to $g$ is $1/|C_G(g)|$, so that enables you to estimate the likely search time. For ${\rm P \Gamma L}(3,4)$ of order 120960, the largest centralizer order (for $g \ne 1$) is 384, so the method should work well there. For ${\rm PGL}(4,3)$ of order 12130560, it is 11664, so again it should work, but would be slower. – Derek Holt Sep 19 '12 at 10:53
• Of course, for every new class representative $g$ that you find, you can also try proper powers of $g$ for being new representatives. So if your elements with large centralizers are proper powers, which is often the case, then you will find them more quickly than by random search alone. – Derek Holt Sep 19 '12 at 11:03
• Finding conjugacy classes of subgroups is much harder, and I don't know of any practical but reasonably elementary algorithm for that. AFAIK all good implementations use some kind of database or lookup table of known results. The "classical" method builds the subgroups up as cyclic (upwards) extensions of known subgroups, but that won't find the perfect subgroups. So implementations make use of lists of all perfect groups up to some specified order, and somehow tests them all for being subgroups. – Derek Holt Sep 19 '12 at 13:25