Timeline for Given a quasi-convex subgroup $H$ of hyperbolic $G$, can we decide if two elements $x,y \in G$ lie in the same double coset of $H$?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 11, 2022 at 20:19 | comment | added | Benjamin Steinberg | @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 | |
| Mar 11, 2022 at 20:10 | comment | added | Derek Holt | I've never thought about double cosets, but intersecting two cosets would be easy. | |
| Mar 11, 2022 at 20:05 | comment | added | Benjamin Steinberg | @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.? | |
| Mar 11, 2022 at 19:50 | comment | added | Derek Holt | I wouldn't construct the whole neighborhood, I would construct a bit of it then use that to construct an automaton, and test its correctness for the coset $wH$, say, by checking that, for all accepted words $v$ , the automaton also accepts the normal form word for $vx$, for all generators $x$ of $H$. One annoying problem with this is that the wrong automata are typically much larger than the correct one. | |
| Mar 11, 2022 at 19:45 | comment | added | Benjamin Steinberg | @DerekHolt, that wouldn't surprise me. You can't get away with just adding a thorn like in the free group case. I still feel there should be something more efficient than adding the whole L+|w| neighborhood. | |
| Mar 11, 2022 at 19:40 | comment | added | Derek Holt | 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. | |
| Mar 11, 2022 at 19:38 | comment | added | Derek Holt | 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 | |
| Mar 11, 2022 at 19:17 | comment | added | Benjamin Steinberg | 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$. | |
| Mar 11, 2022 at 19:07 | history | edited | Benjamin Steinberg | CC BY-SA 4.0 |
added 645 characters in body
|
| Mar 11, 2022 at 19:02 | history | edited | Benjamin Steinberg | CC BY-SA 4.0 |
added 645 characters in body
|
| Mar 11, 2022 at 18:48 | history | answered | Benjamin Steinberg | CC BY-SA 4.0 |