7
$\begingroup$
  1. Is there an elementary and efficient algorithm for testing the membership to a double coset of f.g. subgroups in a free group?
  2. Has this membership problem been implemented in GAP/Magma?

More precisely, I have a finitely generated free group $F$, two finitely generated subgroups $A,B$, given by their free generating sets, and an element $f\in F$. I would like to determine whether $f \in AB$.

I was hoping for something in the spirit of Stallings core graphs, but the standard reference (the paper of Kapovich and Myasnikov [Kapovich, Ilya; Myasnikov, Alexei, Stallings foldings and subgroups of free groups, J. Algebra 248, No. 2, 608-668 (2002). ZBL1001.20015.]) does not seem to treat membership to double cosets.

Theoretically the required algorithm certainly exists. In fact, a much stronger property was proved by Grunschlag ( see Theorem 4.10 in [Grunschlag, Zeph, Computing angles in hyperbolic groups, Gilman, Robert H. (ed.), Groups, languages and geometry. 1998 AMS-IMS-SIAM joint summer research conference on geometric group theory and computer science, South Hadley, MA, USA, July 5-9, 1998. Providence, RI: American Mathematical Society. Contemp. Math. 250, 59-88 (1999). ZBL0953.20034.]

$\endgroup$
7
  • $\begingroup$ The answer is yes to 1 in cubic time at worse $\endgroup$ – Benjamin Steinberg Apr 24 at 12:55
  • $\begingroup$ @Benjamin Steinberg: is it written anywhere? $\endgroup$ – Ashot Minasyan Apr 24 at 12:57
  • $\begingroup$ It was proved by benois long before Grunschlag he is using her result $\endgroup$ – Benjamin Steinberg Apr 24 at 12:57
  • $\begingroup$ In several places. It is a special case of the rational subset membership problem. I’ll write the algorithm in an answer $\endgroup$ – Benjamin Steinberg Apr 24 at 13:00
  • 1
    $\begingroup$ Yes, Gilman rediscovered the algorithm, Actually the 68 paper is not really written in an algorithmic way but Benois redid it later the way I wrote it. $\endgroup$ – Benjamin Steinberg Apr 24 at 13:19
6
$\begingroup$

Here is a second answer that is just rephrasing @DerekHolt’s answer based on the comments. So upvote his answer first! Let $X$ be a finite alphabet. An inverse automaton is a finite directed graph labeled over the alphabet $X$ which is folded in the sense of Stallings, meaning you cannot find two edges entering or leaving a vertex with the same label. Equivalently these are immersions over a bouquet of circles. An inverse automaton has a unique initial state and a set of final states. It recognizes a subset of the free group by looking at all reduced words labelling a path from the initial state to a final state, where inverse letters read edges backward. The language accepted by an inverse automaton is a finite union of cosets of finitely generated subgroups.

The languages accepted by inverse automata are closed under intersection. You simply build the product automaton whose vertices are pairs of vertices and there is an edge labeled by $x$ from $(p,q)$ to $(p’,q’)$ if and only if there are edges from $p$ to $p’$ and $q$ to $q’$ labeled by $x$. This construction is the fiber product of the two inverse automata viewed as immersions over a bouquet of circles. The initial state is the pair of initial states and the final states are those pairs $(p,q)$ where both $p$ and $q$ are final in their respective automata. This is an inverse automata that will accept precisely those reduced words which both automata accept. In particular, the intersection is empty iff the initial vertex of the product construction cannot reach any terminal vertex.

Now to recognize $Hw$ write a linear automaton reading the word $w$ (with inverse letters read backward) and attach at the initial point a generating set for $H$ as loops and apply Stallings foldings. The initial vertex is the intial vertex of $w$ and the final vertex is the end point of $w$. These may collapse after folding. This is essentially the Stallings core of $H$ with a thorn labeled $w$ sticking out of the base point and Stallings uses this automaton in his proof of Marshall Hall's Theorem.

We can do a similar thing for $gK$, but we put the generators of $K$ as loops at the end of the path labelled $g$, and then to test if $w\in HgK$ we just form the product automaton for $Hw$ and $gK$ and check if the final state is reachable from the initial state.

Note $w=hgk$ iff $h^{-1}w=gk$. So $Hw$ and $gK$ intersect iff $w\in HgK$.

$\endgroup$
10
  • $\begingroup$ Yes, I got it backwards $\endgroup$ – Benjamin Steinberg Apr 24 at 15:34
  • $\begingroup$ My first answer is overkill because it solves a much more general problem and I didn’t bother to think if your problem was inherently easier. $\endgroup$ – Benjamin Steinberg Apr 24 at 15:39
  • $\begingroup$ Thank you, this is great! $\endgroup$ – Ashot Minasyan Apr 24 at 15:40
  • $\begingroup$ you are welcome. But I think it is what Derek was saying $\endgroup$ – Benjamin Steinberg Apr 24 at 15:52
  • 1
    $\begingroup$ @HJRW, I add a comment that the product of inverse automata is the fiber product of the corresponding immersions and emphasized inverse automata are immersions over bouquets. $\endgroup$ – Benjamin Steinberg Apr 24 at 18:36
6
$\begingroup$

Concerning implementations in GAP and Magma, there is a GAP package for handling subgroups of free groups, but I don't know whether that has the built-in functionality to do what you want.

I know more about the facilities in Magma (I coded some of them myself). It can do membership testing in finitely generated subgroups of free groups, and it does this by building a finite state automaton to recognize membership of reduced words in the subgroup. (This is constructed using coset enumeration, which is algorithmically the same as Stallings Folding.) It can also construct an automaton recognizing the intersection of two subgroups.

The problem here reduces to computing the intersection of cosets of finitely generated subgroups. There is currently no function that computes the automaton recognizing membership of a coset, but I could easily write one. One could then immediately compute the required intersections (as an automaton), which would allow membership testing.

$\endgroup$
19
  • $\begingroup$ 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. $\endgroup$ – Ashot Minasyan Apr 24 at 14:24
  • $\begingroup$ That is a good point, double cosets membership is equivalent to coset intersection emptiness which can be done essentially with Stallings graphs. $\endgroup$ – Benjamin Steinberg Apr 24 at 14:24
  • $\begingroup$ 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. $\endgroup$ – Benjamin Steinberg Apr 24 at 14:26
  • $\begingroup$ To spell it out, $w\in HgK$ iff $wH\cap gK$ is nonempty $\endgroup$ – Benjamin Steinberg Apr 24 at 14:28
  • 2
    $\begingroup$ @AshotMinasyan I implemented Benois' algorithm in GAP a while ago, if you're interested (though it's far from optimised). $\endgroup$ – Carl-Fredrik Nyberg Brodda Apr 24 at 20:40
6
$\begingroup$

Benois gave a Stallings type algorithm before Stallings to compute membership in any rational subset of a free group on a set $X$. A rational subset $R$ is given by a finite automoaton over the alphabet $X\cup X^{-1}$. An element $g\in FG(X)$ of the free group belongs to $R$ if some word which freely reduces to $g$ is accepted by the automaton. Note that you are not allowed to read an edge in the backward direction and the automaton can be non-deterministic and have epsilon-transitions.

For a double coset $HgK$ you build an automaton where the generators of $H$ and their inverses read loops at the initial state, then there is a sequence of edges spelling out $g$ landing at the final state which has loops labeled by the generators of $K$ and their inverses. If $g$ is the identity you should use an epsilon transition.

Here is the Benois algorithm. We start off with an automaton and we add epsilon transitions until we guarantee that whenever a word is readable between two states, then so is its free reduction. First of all, we search for paths of length two labelled $xx^{-1}$ or $x^{-1}x$ and we add an epsilon transiiton from the beginning of the path to the end of the path (epsilon means empty word). This is the analogue of Stallings folding Inducitvely, we search for paths of the form $\epsilon\epsilon$ or $x\epsilon x^{-1}$ or $x^{-1}\epsilon x$ ($x$ a generator) and if there is no epsilon edge from the beginning to the end of this path of length 2 or 3, we add one. Since we never changed the number of vertices, in a finite number of steps we will not be able to add any new epsilon edges. The resulting automaton is called saturated.

Notice that none of these new epsilon edges change the image of this rational set in the free group. But once it is saturated, whenever we can read a word between two vertices, we can also read its reduced form. Hence the set of reduced words accepted by the saturated automaton is exactly our rational subset of the free group. There is a well known automaton which accepts precisely the reduced words and there is a well known direct product construction that builds an automaton which recognizes the intersection of two regular languages and so you can build an automaton which recognizes exactly the reduced words in your rational subset.

Details can be found in Theorem 3.3 I believe. My memory is that this can be implemented in no worse than cubic time in the size of the automaton (which will be the natural size in the double coset case), but I haven’t thought about that in years.

Added. You can also solve this problem in virtually free groups. Here is another algorithm for free groups that also works for virtually free groups. Recall by Muller-Schupp that a group is virtually free if and only if its word problem is a context-free language. Most reasonable ways of describing a virtually free group will give that context-free grammar. Now if $R$ is a rational subset of a virtually free group (like a double coset of finitely generated subgroup), then $g\in R$ if and only if $1\in g^{-1}R$ and so it suffices to be able to solve the question given a finite automaton over the alphabet of the group, is the intersection of the word problem with the regular subset recognized by the automaton non-empty? But the intersection of a context-free language and a regular language is always context-free and emptiness is decidable for context-free languages.

$\endgroup$
7
  • $\begingroup$ Thank you for such a useful answer! It seems to me that the main difference from Stallings foldings is that we add $\epsilon$-edges instead of folding. I wonder if Stallings' method can be made to work here as well? To decide if $g \in HK$, build the automaton for $HgK$, as you suggest, marking the start vertex and the end vertex by different colours. Apply Stallings foldings to the resulting graph. Then $g \in HK$ iff the start and end vertices have been identified after the foldings are done. $\endgroup$ – Ashot Minasyan Apr 24 at 13:45
  • 2
    $\begingroup$ The problem is if you do HgK and g is in H or K you will fold things into the subgroup graph for <H,K>. Folding only works really for things like subgroups where there is no left to right direction. $\endgroup$ – Benjamin Steinberg Apr 24 at 13:55
  • 1
    $\begingroup$ Also I added a slight correction in that you have to have loops for the inverse generators for H and K to get the subgroup instead of submonoid. $\endgroup$ – Benjamin Steinberg Apr 24 at 13:58
  • 1
    $\begingroup$ That's right, you are only allowed to follow edges in the correct direction. Otherwise you wouldn't be able to us this algorithm to check membership in submonoids and also if you could read the g edge backward you would get into trouble $\endgroup$ – Benjamin Steinberg Apr 24 at 14:12
  • 1
    $\begingroup$ I don't assume $g=1$ I use an epsilon transition so the endpoints are different. I had edited it to make that clear. Sorry, I have been using the construction for over 20 years so I forget that it might not be clear to others. $\endgroup$ – Benjamin Steinberg Apr 24 at 14:13

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.