I think there is a general belief that the classification of all finite groups is "impossible". I would like to know if this claim can be made more precise in any way. For instance, if there is a subproblem of the classification problem that is already equivalent to an already agreed-upon wild problem.

  • 4
    @StefanKohl: Well, that's basically the twin prime problem, isn't it? Is there a real group theoretic component to the answer to this question? Since one can surely translate the number theoretic questions about primes into questions about finite abelian simple groups, there is really no sense in using this as an excuse not to have a "classification" of such groups because the group theoretic component here is as completely understood as possible. It's really just the number theory in the background that gets in the way. – Johannes Hahn Sep 8 '14 at 15:35
  • 5
    I am not sure (though others may be) whether there is any realistic hope of enumerating precisely the number of isomorphism types of groups of order $p^{n}$ for general primes $p$ and positive integers $n.$ There are good asymptotic estimates, but knowing the exact number seems to be another matter. – Geoff Robinson Sep 8 '14 at 15:47
  • 3
    I would not say that the classification of possible Jordan normal forms for $n \times n$ matrices gets conceptually more difficult as $n$ increases: there is a good parametrization of possibilities for any dimension. – Geoff Robinson Sep 8 '14 at 18:01
  • 5
    I think that a reasonable interpretation of classification is a list which enumerates (or parametrizes them) in such a way that we can be sure that each one is described once and only once. – Geoff Robinson Sep 8 '14 at 21:51
  • 11
    There should also be, at minimum, some requirement about computational complexity. Otherwise a trivial (but exponential) algorithm that exhaustively generates all multiplication tables and eliminates isomorphic copies will "list" all groups "once and only once." – Timothy Chow Sep 9 '14 at 0:41
up vote 6 down vote accepted

One can make the argument by wildness much more concrete than in the previous answer: Sergeichuk ["Classification of metabelian p-groups", in: Matrix problems, Inst. Mat. Ukrain. Akad. Nauk, Kiev, 1977, pp. 150-161, in Russian] showed that isomorphism of 2-step nilpotent p-groups is already wild (over $\mathbb{F}_p$), whenever the center is not cyclic of order p.

To answer David Harden's question from the comments, which also gets at Timothy Chow's point about computational complexity: simultaneous conjugacy of k-tuples of matrices can be solved in polynomial time [Sergeichuk; Brooksbank-Luks; Chistov-Ivanyos-Karpinski] (or, I believe, even in $\mathsf{NC}$, depending on the field and model of computation; an even simpler algorithm puts it in $\mathsf{RNC}$). However, the problem of isomorphism of 2-step nilpotent $p$-groups is much closer to the problem of conjugacy of $k$-dimensional subspaces of matrices. Belitskii and Sergeichuk showed that the latter classification problem is strictly harder than $k$-tuple conjugacy (that is, subspace conjugacy contains k-tuple conjugacy but not conversely). When the subspaces are given by a spanning set, subspace conjugacy is at least as hard as Graph Isomorphism [Chapter 4 here contains a freely available and more complete version] (that is, Graph Iso reduces to subspace conjugacy in polynomial time), which is not known to be in $\mathsf{P}$.

There is a standard definition of a linear algebra problem being "wild" if it is harder than the problem of classifying a pair of matrices up to simultaneous conjugation. The classification of finite groups contains many subproblems which are expressible by linear algebra and thus I think this is a good measure. In particular, the classification of 7-step nilpotent Lie algebras is wild (I hear). If we restrict the characteristic to be sufficiently large compared to the dimension, and impose the requirement that all elements are $p$-torsion, probably the classification of such $n$-step nilpotent finite groups is the same as the classification of $n$-step nilpotent Lie algebras, thus wild, but finite $p$-groups are generally harder. Also, the classification of $n$-step nilpotent Lie algebras over $\mathbb Q_p$ probably casts a shadow over the classification of n-step nilpotent $p$-groups with bounded number of generators and sufficiently large exponent.

  • 1. Can we make that expository paper about wild linear algebra problems community wiki? 2. Speaking of wildness and computational complexity, how do those problems behave when the field of interest is finite? Simultaneous conjugacy of ordered pairs of matrices is, for example, obviously in NP. – DavidLHarden Sep 10 '14 at 22:43
  • (1) what? the arxiv link? the MO link? (2) It is not clear to me that the standard tame question, classifying matrices up to conjugation, is itself in P. Rational canonical form is not, because it requires factorization, but I suspect that there is a way around that. – Ben Wieland Sep 10 '14 at 23:58
  • I had the arxiv link in mind. – DavidLHarden Sep 11 '14 at 0:04

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.