My question is a refinement of this one about 'efficient' construction of square elements: If the word problem for a (finitely generated, finitely presented) group is decidable, must the 'square problem' (given an element $g$ of $G$, is there an element $h$ with $g=h^2$?) also be decidable? If not, how 'nice' can $G$ be while still having an undecidable square problem? For instance, can $G$ be automatic? (It feels like there should be an argument based on the Dehn function that precludes this, but I'm not immediately seeing it.) Could it even be hyperbolic?
$\begingroup$
$\endgroup$
3
-
5$\begingroup$ An intuition: It should not have anything to do with the Dehn function; the square root problem should be undecidable even in groups with decidable word problem; we do not know enough about automatic groups to find out one way or another; for relatively hyperbolic groups with good enough parabolic subgroups, the problem should be decidable. $\endgroup$– user6976Commented Aug 12, 2018 at 6:17
-
3$\begingroup$ The question is interesting for groups of homeomorphisms such as various Thompson groups because the problem of extracting a root is classical in dynamics. It is also interesting for groups of matrices. $\endgroup$– user6976Commented Aug 12, 2018 at 7:28
-
$\begingroup$ There's a quantitative version: for G a f.g. group with word length $|\cdot|$, define, for $g\in G$, $u_2(g)=\min(|h|:h^2=g)$ if $g$ is a square and $u_2(g)=0$ otherwise; define $f_2(n)=\sup(u_2(g):|g|\le n)$. Then (for $G$ with solvable word problem) $f_2$ is bounded above by a recursive function iff $G$ has solvable square problem. For $G$ hyperbolic one would expect $f_2(n)=O(n)$, probably using routine arguments. Many other nice groups should have $f_2(n)=O(n)$. $\endgroup$– YCorCommented Aug 13, 2018 at 18:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
(This is not really an answer, rather a suggestion that the answer is probably negative.)
It is known that for linear groups over integers $GL(n,\mathbb{Z})$ starting from $n=4$ the membership problem is undecidable. (It is decidable for $n=2$. The case $n=3$ is an open problem for what I know.) Consider a finitely generated subgroup $G\subset GL(n,\mathbb{Z})$ with undecidable membership. It is, of course, very much decidable whether $g\in G$ is a square in $GL(n,\mathbb{Z})$ (using a Jordan normal form). There may be several square roots $h_1,h_2,\dots,h_k$, and the problem is to find out if any of them belong to $G$. I suspect that this restricted version of the membership problem is still undecidable in general, although I do not have a proof of this.
-
2$\begingroup$ This can be promoted to a proof. First, using iterated HNN extensions, every group $G$ with solvable word problem (SWP) can be embedded into a countable SWP group $H$ in which every element of $G$ is a square, and in turn $H$ can be embedded into a finitely presented group. Now consider a SWP f.p. group $A$ and a f.g. subgroup $G$ with unsolvable membership (e.g., $A=F_2\times F_2$ or a larger group such as $GL_4(Z)$). Then the square problem is unsolvable in the amalgam $H\ast_G A$. $\endgroup$– YCorCommented Aug 13, 2018 at 18:17
-
$\begingroup$ @Ycor: the last phrase in your argument is not quite clear. You are not saying that an element of $A$ is a square in the amalg. product iff it is in $G$? $\endgroup$– user6976Commented Aug 14, 2018 at 6:04
-
$\begingroup$ @MarkSapir thanks, I thought too quickly: there are elements of $A-B$ that are squares in the amalgam $W$. So I need some additional argument (and maybe more specification of $(A,B)$, I'll think about it. $\endgroup$– YCorCommented Aug 14, 2018 at 8:40
-
$\begingroup$ @YCor: You need $G$ to be a pull-back of a surjective homomorphism $\phi: F_2\to K$ where $K$ is a finitely presented with undecidable word problem and $\phi(u)^2=\phi(v)^2$ implies $\phi(u)=\phi(b)$. Such a homomorphism surely exists. Then the membership in $G$ of elements from $F_2\times F_2$ without square roots is not decidable. Take an element $(x,y)$ where either $x$ or $y$ is not a square from $F_2\times F_2$. Then $(x,y)$ is a square i your group iff it is in $G$, which is undecidable. $\endgroup$– user6976Commented Aug 15, 2018 at 4:36