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.
$\begingroup$
$\endgroup$
12
asked Sep 8, 2014 at 13:54
-
4$\begingroup$ I 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. $\endgroup$– Stefan Kohl ♦Sep 8, 2014 at 15:03
-
7$\begingroup$ @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. $\endgroup$– Johannes HahnSep 8, 2014 at 15:35
-
6$\begingroup$ 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. $\endgroup$– Geoff RobinsonSep 8, 2014 at 15:47
-
8$\begingroup$ 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. $\endgroup$– Geoff RobinsonSep 8, 2014 at 21:51
-
17$\begingroup$ 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." $\endgroup$– Timothy ChowSep 9, 2014 at 0:41
|
Show 7 more comments
2 Answers
$\begingroup$
$\endgroup$
7
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).
answered Mar 4, 2015 at 6:05
-
$\begingroup$ 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). $\endgroup$– YCorNov 19, 2021 at 8:54
-
$\begingroup$ I said "$V$ 2-codimensional", not 2-dimensional. $\endgroup$– YCorNov 19, 2021 at 9:03
-
$\begingroup$ @YCor: Ah, sorry, misread! Sergeichuk also proves it for groups whose centers are $\mathbb{Z}/p^2\mathbb{Z}$ if I recall correctly. $\endgroup$ Nov 19, 2021 at 9:05
-
$\begingroup$ 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}$. $\endgroup$– YCorNov 19, 2021 at 9:06
-
$\begingroup$ @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... $\endgroup$ Nov 19, 2021 at 9:09
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ 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. $\endgroup$ Sep 10, 2014 at 22:43
-
$\begingroup$ (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. $\endgroup$ Sep 10, 2014 at 23:58
-