It is known that the isomorphism problem for finitely presented groups is in general undecidable. What are some classes of groups whose isomorphism problem is known to be solvable in polynomial time? (f.p. abelian groups would be an obvious example).
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Not quite an answer to your question but the isomorphism problem is solved among hyperbolic groups. I don't know of any bound on the complexity, however. $\endgroup$– jpmacmanusCommented Jul 20, 2023 at 11:33
-
$\begingroup$ @ADL thanks, I had wondered about this before. That's a nice argument $\endgroup$– jpmacmanusCommented Jul 20, 2023 at 12:27
-
$\begingroup$ @jpmacmanus I've deleted my comment as it is sketchier than I'm comfortable with! I'll contact Murray, as I assume he can remember his argument properly :-) $\endgroup$– ADLCommented Jul 20, 2023 at 12:54
-
$\begingroup$ @ADL No worries, I'd be very interested in hearing the response! $\endgroup$– jpmacmanusCommented Jul 20, 2023 at 13:47
-
$\begingroup$ The best known upper bounds on the complexity of the isomorphism problem for arbitrary hyperbolic groups are certainly horrendous. $\endgroup$– HJRWCommented Aug 3, 2023 at 16:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
A two-generator, one-relator group with torsion is a group with presentation of the form $\langle a, b\mid R^n\rangle$, $R\in F(a, b)$ and $n>1$. Their isomorphism problem is decidable in quadratic time (in the minimum length of the two relators).
This follows by combining a theorem of Steve Pride which says that $\langle a, b\mid R^n\rangle$ and $\langle x, y\mid S^m\rangle$ define isomorphic groups if and only if there is an isomorphism of free groups $\phi:F(a, b)\to F(x, y)$ such that $\phi(R^n)=S^m$ [1], and a theorem of Bilal Khan which says that this latter problem is decidable in quadratic time [2].
The algorithm required here is simply a rephrasing of Whitehead's algorithm, and in the case of rank two Khan improved on Whitehead's algorithm to get a quadratic time algorithm. It is an open problem if Whitehead's algorithm can be improved in arbitrary rank to a polynomial time algorithm. However, it is known to run in quadratic time for "generic" inputs. Similarly, the analogue of Pride's result holds for generic one-relator groups, and so we have the following theorem of Kapovich, Schupp and Shpilrain: The isomorphism problem for generic one-relator groups is decidable in quadratic time [3].
1.Stephen J. Pride, The isomorphism problem for two-generator one-relator groups with torsion is solvable. Trans. Amer. Math. Soc. 227 (1977), 109-139. MR 0430085
2.Bilal Khan, The structure of automorphic conjugacy in the free group of rank two, Computational and experimental group theory, Contemp. Math., vol. 349, Amer. Math. Soc., Providence, RI, 2004, pp. 115–196. MR 2077762
3.Ilya Kapovich, Paul Schupp and Vladimir Shpilrain, Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups. Pacific J. Math. 223 (2006), no.1, 113–140. MR 2221020
-
1$\begingroup$ To show further how much “easier” this subcase of the isomorphism problem for one-relator groups is than the general case (which is still open, as you know), Pride also gave examples of words $w_1, w_2$ (over $a,b$) such that the groups $G_1$ resp. $G_2$ with relation $w_1^n = 1$ resp. $w_2^n = 1$ are isomorphic if and only if $n=1$. That is, in the $2$-generated torsion case the isomorphism classes are a lot more “sparse”, indeed only related by Nielsen transformations as Pride proved. $\endgroup$ Commented Jul 20, 2023 at 15:09