Timeline for Membership to double cosets in free groups
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 25, 2021 at 10:30 | comment | added | Carl-Fredrik Nyberg Brodda | Great! Yes, usually these are not too difficult when the states are few. In the reasonable-time cases I used it for, the resulting automata would have maybe $200$ states and $20000$ transitions, or so, for reference. | |
| Apr 25, 2021 at 9:43 | comment | added | Ashot Minasyan | Thanks for offering your help with the software! For my concrete example, I managed to apply Benjamin Steinberg’s solution by hand: the resulting automaton only had 12 states. | |
| Apr 24, 2021 at 20:40 | comment | added | Carl-Fredrik Nyberg Brodda | @AshotMinasyan I implemented Benois' algorithm in GAP a while ago, if you're interested (though it's far from optimised). | |
| Apr 24, 2021 at 19:39 | comment | added | Derek Holt | @AshotMinasyan Yes that's fine - he has described the details of what is going on. If you have any actual instances of this problem that you think would e interesting then please let me know, because I might try and implement it in Magma - I don't expect it to take long, because nearly all of the machinery is there already. | |
| Apr 24, 2021 at 17:27 | comment | added | Ashot Minasyan | Dear @DerekHolt, many thanks for your answer. I could only accept one answer, and Benjamin Steinberg's second answer was precisely what I was looking for. | |
| Apr 24, 2021 at 16:43 | comment | added | Derek Holt | @BenjaminSteinberg Yes thanks, that reduces the amount of work I would need to do, because I can use the existing functionality to construct the automaton for $w^{-1}Hw$. I might actually do this next week, just in case anyone really want to solve such a problem! | |
| Apr 24, 2021 at 16:25 | comment | added | Benjamin Steinberg | Hw is w(w^{-1}Hw) if it makes implementation easier. That's what my version of your argument does. | |
| Apr 24, 2021 at 16:00 | comment | added | Derek Holt | Incidentally, all of this generalizes to quasiconvex subgroups of hyperbolic groups, although for that there would be more work to do to implement it for coset membership rather than subgroup membership. | |
| Apr 24, 2021 at 15:56 | comment | added | Derek Holt | @BenjaminSteinberg I think you mean $w \in HgK$ if and only if $Hw \cap gK$ is nonempty. It makes a slight difference from my viewpoint as someone who does implementations, because the automaton for membership of $gK$ is a lot easier to construct from that of $K$ than for $Hw$. I would probably use $Hw = (w^{-1}H)^{-1}$ to do that, but then you need to read the input word backwards. Personally I think the approach I describe is a lot easier, but that's because I could complete the implementation in at most a few hours. | |
| Apr 24, 2021 at 14:51 | comment | added | Benjamin Steinberg | Yes, a reduced word $z$ would read in that fiber product from (start,start) to (end,end) iff it belongs to $wH\cap gK$ and so there is no need to throw in direction or anything. This is much easier than general rational subsets. | |
| Apr 24, 2021 at 14:46 | comment | added | Benjamin Steinberg | @AshotMinasyan, my guess is you can just view the Stallings graph for H with a thorn reading from w to the base point (folded in) and the Stallings graph for K with a thorn reading g going into the base point (folded in), these are graph immersions over the bouquet. Take the fiber product immersion and can the pair start(g),start(w) reach the pair base point, base point where you can move along edges in either direction and don’t formally include inverse edges. | |
| Apr 24, 2021 at 14:41 | comment | added | Benjamin Steinberg | @AshotMinasyan, I guess it is not easier if you do what I said formally to do. But if you can get away with allowing yourself to travel in either direction along the edges, then it is easier. | |
| Apr 24, 2021 at 14:39 | comment | added | Ashot Minasyan | @BenjaminSteinberg, I don't see why this method is much easier that the method suggested in your answer. Don't you still need to saturate the automaton, and then construct the automaton for the intersection? | |
| Apr 24, 2021 at 14:37 | comment | added | Benjamin Steinberg | @AshotMinasyan, I’m not so sure. I think that the intersection of the two cosets is empty iff the start and end are in different connected components even if you are allowed to go backward. Intuitively you are checking if the orbit of wH in the coset graph under $K$ hits g. So I think direction doesn’t matter but to be safe you formally should have inverses edges and keep track of direction. But it may not be necessary. | |
| Apr 24, 2021 at 14:30 | comment | added | Ashot Minasyan | So, you're suggesting to build automatons for the coset $Af$ and the subgroup $B$, then use the direct product construction, to construct an automaton accepting the intersection of $Af$ and $B$. This intersection is non-empty iff there is a directed path from the start vertex to the accept vertex... Still, you have to be careful with directed edges... | |
| Apr 24, 2021 at 14:28 | comment | added | Benjamin Steinberg | To spell it out, $w\in HgK$ iff $wH\cap gK$ is nonempty | |
| Apr 24, 2021 at 14:26 | comment | added | Benjamin Steinberg | I was interested in the old days in membership in products $gH_1\cdots H_k$ with $H_1,\ldots, H_k$ finitely generated subgroups. By the Ribes and Zalesskii theorem all closures of regular languages in a free group in the profinite topology are a finite union of sets of that form. Here you can’t get away with just using subgroup graphs. | |
| Apr 24, 2021 at 14:24 | comment | added | Benjamin Steinberg | That is a good point, double cosets membership is equivalent to coset intersection emptiness which can be done essentially with Stallings graphs. | |
| Apr 24, 2021 at 14:24 | comment | added | Ashot Minasyan | Thank you for the update on GAP and MAGMA! It is not worth writing a code for my question, I was just wondering whether all such algorithms concerning subgroups of free groups have already been implemented. | |
| Apr 24, 2021 at 14:07 | history | answered | Derek Holt | CC BY-SA 4.0 |