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.
Asked
Active
Viewed 4,229 times
25
-
4I think whether the "classification of all finite groups" is possible or not depends on what one is willing to accept as a "classification". For example, while there is a classification of finite simple groups which most people accept as such, we still do not know whether there are infinitely many pairs of simple groups $G$ and $H$ such that $|G| = |H| + 2$. If you want to classify all finite groups, such caveats get bigger. – Stefan Kohl Sep 08 '14 at 15:03
-
7@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 08 '14 at 15:35
-
1Are you basically asking why the group extension problem is hard? Having classified finite simple groups, a full solution to the extension problem would classify all finite groups. – Harry Wilson Sep 08 '14 at 15:43
-
6I 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 08 '14 at 15:47
-
@StefanKohl: Well, I take CFSG as a complete classification, even though it does not answer all questions that one can pose about the finite simple groups. Such a listing would be perfectly OK. My question is, whether there are any obvious obstruction that one cannot expect to come up with such a list for all groups. For instance, the classification of the groups of order $p^n$ gets increasingly complicated with $n$, but so does the classification of $n \times n$ matrices up to conjugacy (Jordan form), so in what sense is the classification of groups of prime power "impossible"? – Keivan Karai Sep 08 '14 at 16:44
-
3I 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 08 '14 at 18:01
-
1I think the comments (except Geoff Robinson) miss the point. As I understand it: the classification of finite 2-groups is a wild problem. – BWW Sep 08 '14 at 20:52
-
8I 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 08 '14 at 21:51
-
17There 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 09 '14 at 00:41
-
2I think the more precise expression "or parametrizes them" suggests giving a recipe (in terms, say, of a list of invariants) which allows the list to be reconstructed in a systematic way. I think we all agree that group multiplication tables are not the best way to describe groups. – Geoff Robinson Sep 09 '14 at 09:16
-
3On reflection, I think there are lots of perfectly valid classifications which give workable characterizations, but could not be implemented in finite time. Jordan normal form over the complex numbers, for example- there are uncountably many Jordan normal forms in each dimension. The classification of finite simple groups requires, strictly speaking, the knowledge of all prime powers. So invoking computational complexity introduces new questions ( which may be good). – Geoff Robinson Sep 09 '14 at 09:59
-
Some necromancy, I don't think anyone intends to classify all the finite groups but rather all possible finite extensions, once you have the simple groups and all the extensions you in some sense have achieved classification of all the groups. I believe some areas of homological algebra were motivated by this originally but I don't know how far they got. – Sidharth Ghoshal Sep 20 '22 at 18:58
2 Answers
21
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.
Ben Wieland
- 8,667
-
- 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
-
17
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 Tensor Isomorphism-complete G-Qiao. Another TI-complete problem is 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}$. It is even harder than Code Equivalence (which itself is thought to be harder than Graph Iso).
Joshua Grochow
- 2,880
-
To specify the first assertion, for $p$ odd prime, a 2-step-nilpotent group of exponent $p$ whose abelianization has rank $n$ is the same as the quotient of the free $n$-generated exponent $p$ 2-step-nilpotent group $L_n$ by a subspace $V$ of its center. The latter can be identified to $\bigwedge^2\mathbf{F}_p^n$ (which has dimension $n(n-1)/2$), and two resulting groups $L_n/V$, $L_n/V'$ are isomorphic iff $V,V'$ are in the same $\mathrm{GL}_n(\mathbf{F}_p)$-orbit. Even for 2-codimensional $V$ (i.e. such groups of order $p^{n+2}$), I think this is wild (say, when $p$ is fixed and $n$ grows). – YCor Nov 19 '21 at 08:54
-
-
@YCor: Ah, sorry, misread! Sergeichuk also proves it for groups whose centers are $\mathbb{Z}/p^2\mathbb{Z}$ if I recall correctly. – Joshua Grochow Nov 19 '21 at 09:05
-
Ah thanks. I have much less intuition about these ones, say of exponent $p^2$, since this boils down to Lie algebras over no longer fields but $\mathbf{Z}/p^2\mathbf{Z}$. – YCor Nov 19 '21 at 09:06
-
@YCor: Ah, but now I am confused. When the center is $\mathbb{Z}/p\mathbb{Z})^2$ I believe there is a tame classification because of Kronecker normal form for matrix pencils (eg the corresponding classification for genus 2 p-groups can be seen in Brooksbank-Maglione-Wilson). I will have to dig/think some more to reconcile these... – Joshua Grochow Nov 19 '21 at 09:09
-
OK, actually I had no serious clue to say "I think this is wild", and should rather have said "I guess" — this is close to classifying spaces with a pair of alternating forms. Possibly one needs codimension 3 (that's roughly classifying spaces with a triple of alternating forms)? – YCor Nov 19 '21 at 09:31
-
@YCor Actually I wasn't so much referring to your comment as Sergeichuk's result. I am confused about how to reconcile that result with the classification that one gets from Kronecker normal form for pencils. Either way you are right that codimension 3 is wild; and unrestricted codimension is TI-complete (when formulated appropriately) or what one might call "tensor wild" (eg https://doi.org/10.1016/j.laa.2018.12.022). – Joshua Grochow Nov 19 '21 at 16:48