7
$\begingroup$

Fix a prime $p$. Then the question is about the difficulty of classifying finite $p$-groups. Originally I was going to ask if this was a "wild" problem but thanks to Joel David Hamkins' answer to question 10481 I now know to ask if it is a smooth problem.

At one time there was a minor industry producing papers which showed that a particular list of invariants did not classify finite $p$-groups so my understanding is that it would be remarkable if this problem was smooth.

Also for each prime $p$ and each $n$ the number of groups of order $p^n$ (up to isomorphism) is finite. This gives a sequence of integers for each $p$. For $p=2,3,5,7$ these sequences appear in OEIS as sequences A000679, A090091, A090130, A090140.

A supplementary question is: Does knowing if the classification is or is not smooth have any bearing on the complexity of these sequences?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ My sense is that au courant thinking in this area is that p-groups should be classified by coclass rather than by size; if I understand correctly, for each coclass there is a FINITE list of infinite pro-p groups of that coclass, and all the finite ones arise as quotients of these. Of course this doesn't say at all how the classification problem fits into any schema of "wild" vs. "tame"! $\endgroup$
    – JSE
    Commented Jan 13, 2011 at 16:19

4 Answers 4

Reset to default
5
$\begingroup$

If I understood Joel David Hamkins's explanation correctly, then the problem of classifying finite ($p$-)groups is smooth for silly reasons. Attach to each group the following datum: randomly number the elements of a group $G$ from 1 to $|G|$ and consider the set $S_G$ of multiplication tables of $G$ with respect to all possible permutations of the elements, so $(|G|)!$ multiplication tables in total. Two groups $G$ and $H$ are isomorphic if and only if the sets $S_G$ and $S_H$ are equal.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I agree with you. This means I did not get the question right. This is saying that I can decide if two $p$-groups are isomorphic without too much difficulty. I wanted to formalise the idea that the classification of finite $p$-groups is difficult. $\endgroup$
    – Bruce Westbury
    Commented Jan 12, 2011 at 18:41
  • 1
    $\begingroup$ Dear Bruce, I understood what you were getting at, but the hierarchy explained by Joel David Hamkins seems too coarse for that. I think you can safely ask another question about whether there is a good precise way to capture the fact that the classification is difficult. $\endgroup$
    – Alex B.
    Commented Jan 13, 2011 at 1:43
4
$\begingroup$

As said in Alex's answer, smoothness is too coarse (=automatic) for classification of finite objects. It concerns equivalence relations on uncountable sets (borel spaces).

On the other hand, there has been great progress on the classification of $p$-groups lately. You can try this 2008 presentation by Bettina Eick (she also has a paper in a 2008 LMS Bulletin whith Leedham-Green, by I dont't have a link).

Improve this answer
$\endgroup$
4
$\begingroup$

Given a finite $p$-group $G$ of class $c$ and order $p^n$ we say that $G$ has coclass $r=n-c$. In the 80’s Charles Leedham-Green and Mike Newman came up with the 5 coclass conjectures which were striking and counterintuitive. Essentially they say that a $p$-group with small coclass is close to being abelien, e.g. it has derived length that is bounded by a function of $p$ and $r$. The proof of the coclass conjectures is a great achievement. It is due to many mathematicians, let me just mention Charles Leedham-Green, Steve Donkin, Aner Shalev, and Efim Zelmanov who probably contributed the most.

So in some sense $p$-groups are classified by their coclass. The problem is that for the coclass to say something meaningful about a $p$-group the group has to be very large. In other words, if the coclass of $G$ with respect to the order of $G$ is not too small we cannot say much about $G$.

Improve this answer
$\endgroup$
3
$\begingroup$

1) The classification of p-groups (even p-groups of class 2) is indeed wild over $\mathbb{F}_p$ [V. Sergeichuk, The classification of metabelian p-groups (Russian), Matrix problems, Akad. Nauk Ukrain. SSR Inst. Mat., Kiev, 1977, pp. 150-161.]

(It's not clear to me why Hamkins's answer on your other question led you away from asking about wildness...)

2) Rather than smoothness - since as pointed out by others, classification problems on finite spaces are trivially smooth - in addition to wildness, you might consider computational complexity as a measure of difficulty of a finite classification problem. In particular, the existence of a polynomial-time algorithm for a classification problem is some evidence that the classification is "easy."

There is currently no known poly-time algorithm to test isomorphism of finite groups, given by their multiplication tables, and it is widely believed that p-groups (even those of class 2) are the hardest cases. (Beware of potential circularity in beliefs though: the wildness of classifying p-groups of class 2 is one of the pieces of evidence for the preceding belief, although there are others as well.)

Furthermore, despite all of the exciting recent progress on classifying groups by coclass, as far as I know this hasn't yet been used to make any progress towards a polynomial-time algorithm for testing isomorphism of p-groups. Furthermore, isomorphism of p-groups of class 2 are believed to be the hardest cases, and these are exactly the groups of maximal coclass, for which the recent classification results say the least.

(Polynomial-time as a version of "easiness" is a little subtle compared to mathematical experience: for example, the fact that finite simple groups are all generated by 2 elements (a consequence of CFSG) implies that there is a relatively simple polynomial-time algorithm to test isomorphism of finite simple groups (find a generating pair of elements in the one group, try all possible maps of that pair into the other group and check if each is an iso), but that algorithm relies on a massive, difficult theorem for its correctness. However, I still think the computational complexity of a classification problem is one useful gauge of its difficulty, particularly when it comes to finite problems.)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .