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?

  • 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$ – user6976 Aug 12 '18 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$ – user6976 Aug 12 '18 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$ – YCor Aug 13 '18 at 18:17

(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$ – YCor Aug 13 '18 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$ – user6976 Aug 14 '18 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$ – YCor Aug 14 '18 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$ – user6976 Aug 15 '18 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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