This is not my area of research, but I am curious. Let $G=\left< X|R \right>$ be a finitely presented group, where $X$ and $R$ are finite. There are many questions which are undecidable for all such $G$, for example whether $G$ is trivial or whether a particular word is trivial in $G$. Is there any non-trivial question (by trivial I mean that the answer is always yes or always no) which is decidable? For instance, is there a class $S$ (non-empty and not equal to all the finitely presented groups) such you can always decide whether $G$ is in this class?
$\begingroup$
$\endgroup$
4
asked Mar 31, 2011 at 7:56
-
1$\begingroup$ You might like to look at the answers to this question, and the question it refers to: mathoverflow.net/questions/16532/… . $\endgroup$– HJRWCommented Mar 31, 2011 at 9:06
-
2$\begingroup$ Thanks. If a question is interesting, then it will come back. $\endgroup$– Yiftach BarneaCommented Mar 31, 2011 at 9:44
-
$\begingroup$ There is active research going on about whether such problems are decidable if we assume the word problem has a solution. For instance, determining whether a group is a 3-manifold group is decidable, given a presentation and a solution to the word problem. $\endgroup$– JeremyKunCommented Oct 18, 2011 at 2:20
-
$\begingroup$ en.wikipedia.org/wiki/Adian%E2%80%93Rabin_theorem $\endgroup$– TT_ stands with RussiaCommented Apr 24, 2021 at 3:42
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
The problem whether $G$ is perfect, that is $G=[G,G]$ is decidable because you need to abelianize all relations (replace the operation by "+" in every relation) and solve a system of linear equations over $\mathbb Z$. For example, if the defining relations are $xy^{-1}xxy^5x^{-8}=1, x^{-3}y^{-2}xyx^5 = 1 $, then the Abelianization gives $-5x+4y=0, 3x-y=0$. Now you need to check if these two relations "kill" $\mathbb{Z^2}$. That means for some integers $a,b,c,d$ we should have $x = a(-5x+4y)+b(3x-y), y = c(-5x+4y)+d(3x-y) $. This gives 4 integer equations with four unknowns: $1=-5a+3b, 0=4a-b, 1=4c-d, 0=-5c+3d $. This systems does not have an integer solution (it implies $7a=1 $), so $G\ne [G,G]$.
-
$\begingroup$ Here the abelianization has the abelian group presentation $(x,y:5x=4y,3x=y)$ and this can be rewritten as $(x,y:7x=0,3x=y)$ which is a presentation of $C_7$, so the abelianization is $C_7$, so the abelianization is nonzero. $\endgroup$– YCorCommented Oct 20, 2018 at 6:04
-
$\begingroup$ In general, there's a much more efficient procedure than making an integral non-homogeneous system on $m^2$ variables. For instance, one has a matrix $n\times m$ matrix ($n$ number of generators, $m$ relators): then abelianization is zero iff this matrix has rank $n$ over every field. One checks over $\mathbf{Q}$, using standard elementary operations, and keeping the list of denominators of these. If it doesn't have rank $n$, we are done. Otherwise, we then check whether the rank is $n$ modulo every prime appearing among divisors of the listed denominators. $\endgroup$– YCorCommented Oct 20, 2018 at 6:08
-
$\begingroup$ @YCor: One needs to show that the volume of fundamental domain is 1. That is easy. But the method I described is, in addition, obvious. $\endgroup$– user6976Commented Oct 20, 2018 at 9:03
$\begingroup$
$\endgroup$
2
Many of the undecidable properties of finitely presented groups are verifiable i.e. if they are true, then they can be proved true. Such properities include trivial, finite, abelian, nilpotent, free, automatic, hyperbolic, isomorphic to some other specified finitely presented group.
As a follow-up question, are there any properties of finitely presented groups that are known to be neither verifiable nor for there negation to be verifiable? Might solvability be such a property?
answered Mar 31, 2011 at 9:34
-
2$\begingroup$ @Derek: It is not clear even if solvability of class 2 is verifiable. Right? Same for unsolvability of class 2. Residual finiteness and its negation should be non-verifiable, but it is not obvious either. $\endgroup$– user6976Commented Mar 31, 2011 at 10:00
-
3$\begingroup$ @Derek - You could ask that as a separate question. $\endgroup$– Sam NeadCommented Mar 31, 2011 at 10:02