Algorithm that list all Maximal subgroups (up to conjugacy) of a finite group

Question

Question: Is a polynomial time algorithm known to find all maximal subgroups (up to conjugacy) of a given group? (by polynomial time, I mean polynomial in the input size).

If there is, please share a reference and also mention for which representation of the group the algorithm works.

If no such algorithm exists for general groups, what can we say when the group is solvable?

I have found this paper by Bettina Eick and Alexander Hulpke on maximal subgroups of permutation groups. In section 6, it is mentioned that 'An implementation of the solvable part of the algorithm shows that this method is highly efficient. Does that mean that for solvable permutation groups, their algorithm runs in polynomial time? If yes, does their algorithm also run in polynomial time for general groups?

Answer 1

In fact the answer to this question is no, irrespective of how the group is input. There is no known polynomial-time algorithm to solve this problem. As ahulpke pointed out, one problem is that the size of the output is not always bounded by a polynomial function of the size of the input.

Another perhaps more serious problem is that there is no sufficiently precise description in the literature of the maximal subgroups of all finite simple groups. If, for example, your input group is the alternating group $A_n$ for some large $n$, then you would need a complete list of the primitive permutation groups of degree $n$ in order to calculate the maximal subgroups. Currently such lists have been computed only up to degree $8191$.

Another example is the famous Monster simple group. We are getting very close to having a complete list of its maximal subgroups, but there are still a small number of uncertainties.

The currently available algorithms that are described in the literature and are used in GAP and Magma make use of stored lists of subgroups of the almost simple groups up to some (moderately large) order. So they are very effective on the sorts of groups with which we typically study on a computer, but they are not general algorithms, and they fail for large groups like $A_n$ for $n>4095$.

Of course you could find the maximal subgroups of any finite group by some kind of naive algorithm, but that would have no hope of being polynomial-time.

Answer 2

[As answer, not as remark, because it is too long]

If you ask for complexity, you should specify how you are describing the input (e.g. generating permutations? the multiplication table?), since these can differ dramatically for the same group:

E.g. for maximal subgroups, the elementary abelian group of order $p^n$ can be generated by $n$ permutations of degree $np$, making potentially for input size $n^2p$ but has $ \frac{p^n-1}{p-1}\sim p^{n-1} $ maximal subgroups. This is not polynomial in the input size and thus a polynomial time algorithm would not even be able to write out the result.