5
$\begingroup$

I've come across the following question in my research, which seems elusive but is almost surely decidable.

Let $H$ be a quasi-convex subgroup of the hyperbolic group $G$. Given $x, y \in G$, we wish to decide whether $HxH = HyH$. This is equivalent to asking whether there exists $h, h' \in H$ such that $hx = yh'$.

It is easy to see that the question $x \in yH$ is easily decidable, since $H$ has a solvable membership problem and this reduces to checking whether $y^{-1} x \in H$.

The double coset problem seems harder, but the instinct is that this might solved by bounding the lengths of $h, h'$, akin to the solution to the conjugacy problem.

Does this problem appear in the literature anywhere? Any references or thoughts are appreciated.

Thanks!

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ If you look at a geodesic quadrilateral with paths labelled by geodesic words for $x$, $y$, $h$ and $h'$ then, if the words for $h$ and $h'$ are much longer than those for $x$ and $y$, won't you get a thin bit in the middle of the $h$ and $h'$ words, and hence a repeating short connecting path, which would enable you to cut of out bits of these words and shorten them? $\endgroup$
    – Derek Holt
    Commented Mar 10, 2022 at 19:33
  • 2
    $\begingroup$ In my previous comment, for the cutting out part to work, we need to be using words that are labelled by generators of $H$. While these words are not generally geodesic words in the Cayley graph, the quasiconvexity of $H$ means that they can be chosen to lie uniformly close to geodesic words, so the argument should still work. $\endgroup$
    – Derek Holt
    Commented Mar 10, 2022 at 20:00
  • 4
    $\begingroup$ In free groups, this problem is solved by computing the fibre product of core graphs. Kharlampovich, Myasnikov and Weil have a paper generalising core graphs to the context of quasi convex subgroups of hyperbolic groups, so it’s conceivable that their techniques can be used to solve this problem. $\endgroup$
    – HJRW
    Commented Mar 10, 2022 at 22:32
  • 1
    $\begingroup$ I have more or less convinced myself that the argument outlined in my comments works, and If necessary I can expand it to a more detailed answer, but that will have to wait until Monday - it really needs a picture! $\endgroup$
    – Derek Holt
    Commented Mar 11, 2022 at 7:58
  • 1
    $\begingroup$ A remark: define $f_H(n)$ as the the sup over all $x,y$ in the $n$-ball and in the same $H$-doublecoset of the minimal $k$ such that there exist $h,h'$ in the $k$-ball with $y=hxh'$. Then deciding whether 2 elements are in the same $H$-doublecoset is the same as asking whether $f_H$ is a computable map, or also as whether it is bounded above by a computable map. Then for $H$ quasi-convex in $G$ hyperbolic, one certainly expects $f_H$ not only to be bounded above by a computable function, but to actually grow linearly (= be bounded above by a polynomial of degree 1). $\endgroup$
    – YCor
    Commented Mar 11, 2022 at 11:11

1 Answer 1

Reset to default
5
$\begingroup$

This is answered for free groups in Membership to double cosets in free groups and the same method basically works for hyperbolic groups. You might as well do double cosets $HgK$ with $H,K$ both quasiconvex. Then $w\in HgK$ if and only if $Hw\cap gK$ intersect nontrivially.

Now the set of geodesic words belonging to $Hw$ is a regular language and there are known algorithms for constructing an automaton recognizing these languages (HJRW mentioned this in the comments for subgroups, but it is more or less straightforward to generalize for cosets) and similarly for $gK$. Therefore the geodesic words in $Hw\cap gK$ are recognized by a finite automaton that you can construct. Since emptiness is decidable for finite automata, you are done. You need the quasi-convexity constants of course to build these automata.

I should mention the algorithms for these things I have seen do not appear super-effecitve. The point is if $H$ is $L$-quasiconvex, then to get the automaton for $Hw$ you construct the $(L+|w|)$-neighborhood of the coset $H$ in the Schreier graph associated to $G/H$ and make $H$ the start state and $Hw$ the final state and intersect with the automaton computing the language of geodesic words for $G$. Any geodesic for an element of $Hw$ does not leave this $(L+|w|)$-neighborhood by quasi-convexity. One can build this fragment of the Schreier graph via a Todd-Coxeter style method: see section 4 of https://arxiv.org/pdf/1408.1917.pdf. However, there are some classes of groups (like surface groups) where more efficient means to build this core are known.

Improve this answer
$\endgroup$
8
  • $\begingroup$ There is no real need to intersect with the language of geodesics, you will just recognize some nongeodesic words. So you could just take the fiber product of sufficiently large balls in the two Schreier graphs (based on the quasiconvexity constant and the lengths of g,w) . The size of this fiber product will give you a bad bound on the shortest word in $Hw\cap gK$ and hence on elements $h,k$ with $w=hgk$. $\endgroup$
    – Benjamin Steinberg
    Commented Mar 11, 2022 at 19:17
  • $\begingroup$ That's probably a better method than the one I outlined, and it could be implemented. I already have have implemented software (the KBMAG package written in C, but accessible from GAP and Magma) that can do various calculations in the Schreier graph of quasiconvex subgroups of hyperbolic graph, and it can build an automaton that recognizes geodesic words that represent elements of $H$. I have never got round to implementing the algorithm for testing geodesic words for membership of cosets $Hw$, and it would require extra work, ... ctd $\endgroup$
    – Derek Holt
    Commented Mar 11, 2022 at 19:38
  • $\begingroup$ but perhaps I will try and do it some time now that I am retired. But I am afraid that it would have very unpleasant complexity in the length of $w$, and would probably only work for moderately short words. The methods I used are generally based on the Knuth-Bendix completion process rather than Todd-Coxeter. Another central technique is to construct candidates for the required automaton, and then test them for correctness using methods that enable you to improve them if they are wrong. $\endgroup$
    – Derek Holt
    Commented Mar 11, 2022 at 19:40
  • 1
    $\begingroup$ @DerekHolt, I guess you have thought more about this. In the free group the reduced words in HgK is a regular language and you can construct its automaton directly. Therefore if g is fixed the size of w is not relevant. Is something similar true for double cosets of quasi-convex subgroups of hyperbolic groups.? $\endgroup$
    – Benjamin Steinberg
    Commented Mar 11, 2022 at 20:05
  • 1
    $\begingroup$ @DerekHolt I agree intersecting is easy but you made it sound like getting the coset Hw is painful and so doing it for each input word w is costly. If you could build one automaton for the double coset that works for all w it might be more efficient $\endgroup$
    – Benjamin Steinberg
    Commented Mar 11, 2022 at 20:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .