18
$\begingroup$

Let $G = \langle A \mid R \rangle$ be a finitely presented group, given by a finite presentation. If $G$ is abelian, then we can verify this fact: simply verify the fact that $[a, b] = 1$ for all generators $a, b \in A$ (this can be done by enumerating all words equal to $1$ in the group). That is, the property "being abelian" is a semi-decidable property (however, the property of "being non-abelian" is not semi-decidable, by the Adian–Rabin theorem, cf. also this translation). I recently bumped into the following question(s), but couldn't figure out any obvious way to answer either:

Is the property of being solvable semi-decidable? Is the property of not being solvable semi-decidable?

That is, is it possible to verify that a group is solvable? Is it possible to verify that a group is not solvable? The same questions above can also be asked for solvability of bounded derived length; for example, can one verify whether $G$ is a metabelian group (i.e. derived length $\leq 2$)? For reference, nilpotency is semi-decidable, i.e. there is a procedure for verifying nilpotency, see the article "Verifying nilpotence" by Charles Sims.

Improve this question
$\endgroup$
4
  • $\begingroup$ My immediate thought was "probably not" but I am surprised to see nilpotency is semidecidable. My guess would still be no but I wouldn't be terribly surprised to be proven wrong! $\endgroup$
    – Wojowu
    Jul 22 at 11:16
  • $\begingroup$ I seem to recall that solvability of length $n$ is equivalent to the identity $[x_1,\dots,x_{2^n}]_n=1$ where $[x]_0=x$, $[x_1,\dots,x_{2^{n+1}}]_{n+1}=[[x_1,\dots,x_{2^n}]_n,[x_{2^n+1},\dots,x_{2^{n+1}}]_n]$. Is this correct? If so, is it enough to test the identity on generators? This would make the problem semidecidable. $\endgroup$
    – Emil Jeřábek
    Jul 22 at 11:31
  • 4
    $\begingroup$ The difference here between nilpotency and solvability is that free nilpotent groups are finitely presented while free solvable groups are not. And thus testing the identity associated to solvability on the generators is not sufficient to prove solvability of a group. $\endgroup$
    – E.Rauzy
    Jul 22 at 12:29
  • 1
    $\begingroup$ @E.Rauzy yes, and for nilpotency, we also need to know that there is a computable way to assign to $n$, a finite set of relators for the free $n$-step nilpotent group. $\endgroup$
    – YCor
    Jul 22 at 13:29

1 Answer 1

Reset to default
17
$\begingroup$

The Adian–Rabin theorem, although it is not usually stated like this, says that Markov properties are not co-semi-decidable, thus « not being metabelian » or « not being solvable » are not semi-decidable. However, whether « being solvable » or « being solvable of derived length $\le n$ » is semi-decidable is an open problem. Giving a precise classification of these properties in terms of the arithmetical hierarchy is stated as an open problem in Miller’s survey article Decision Problems for Groups — Survey and Reflections.
It is natural to expect that « being solvable of derived length $\le n$ » should be $\Pi_2$ complete —i.e. equivalent to an infinite conjunction of semi-decidable properties, but not semi-decidable. Also, « being solvable » should be $\Sigma_3$ complete.

I think that these questions are both important and very basic and they definitely deserve some attention.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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