9
$\begingroup$

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?

$\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$
    – user6976
    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$
    – user6976
    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$
    – YCor
    Aug 13, 2018 at 18:17

1 Answer 1

2
$\begingroup$

(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.

$\endgroup$
4
  • 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, 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$
    – user6976
    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$
    – YCor
    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$
    – user6976
    Aug 15, 2018 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.