8
$\begingroup$

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 Answers 1

13

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.

  • 0
    Ok, I'll dig the conjugacy classes for subgroups then. Thanks a lot for your answer!2012-09-20