12
$\begingroup$

Let $S$ be a finite set and $F$ is the free group on that set. Is there an algorithm which takes as input a sequence of $w,w_1,\ldots,w_k\in F$ and decides whether $w\in \langle w_1,\ldots,w_k\rangle$?

This question keeps appearing in some of my work. My intuition is that this has been solved somewhere. It seems very related to the Nielsen-Schreier theorem and, to my understanding, Nielsen's proof of this theorem gave an algorithm for finding a free generating set for any finitely generated subgroup of a free group - which is very closely related to this problem. I also have found various literature referring to this as a "generalized word problem" and various undecidability results relating to the problem in general - but, even though nothing suggests that this is undecidable for a free group, I've not come across any algorithm for deciding it.

$\endgroup$
  • $\begingroup$ If you can decide this then you can decide whether $F/\langle w_1,...,w_k\rangle$ is trivial, just check for each $w$ being an element of $S$, right? Thus it's undecideable... $\endgroup$ – Dima Pasechnik Dec 30 '18 at 4:21
  • 1
    $\begingroup$ @DimaPasechnik: What you write down is not a group since the subgroup you are trying to take the quotient by is not normal. $\endgroup$ – Andy Putman Dec 30 '18 at 4:23
  • $\begingroup$ oops, right. sorry for noise. $\endgroup$ – Dima Pasechnik Dec 30 '18 at 4:27
  • 3
    $\begingroup$ This is known as "solvable uniform (subgroup) membership problem". $\endgroup$ – YCor Dec 30 '18 at 5:31
  • $\begingroup$ I saw this in the hot questions list and went, "Huh! We worked on something similar at Hampshire but didn't get far.". Lo and behold :D $\endgroup$ – TreFox Dec 30 '18 at 16:06
17
$\begingroup$

Let $T$ be a finite subset of the free group on a set $S$. Nielsen's original proof (described nicely in the beginning of Lyndon and Schupp's book) gives an algorithmic process to find a free generating set $T'$ for the subgroup generated by $T$ with the following very nice property: for a word $u$ in $T'$, the $T'$-length $|u|_{T'}$ of $u$ is at least the $S$-length $|u|_S$ of $u$. To recognize if a word $w$ in $S$ lies in the subgroup generated by $T$, it is thus enough to check whether it equals any of the finitely many words of length at most $|w|_S$ in $T'$.

But of course there are much faster and better ways to do this. The nicest algorithm (which runs very fast) is based on Stallings folding and can be found in

Stallings, John R. Topology of finite graphs. Invent. Math. 71 (1983), no. 3, 551–565.

I don't have the paper handy right now, so I'm not sure if the algorithm is made explicit in it, but if you understand this paper then it should be clear how to do what you want.

$\endgroup$
  • $\begingroup$ In fact the algorithm can be thought of as a special case of Todd-Coxeter coset enumeration. $\endgroup$ – Derek Holt Dec 30 '18 at 10:51
  • 1
    $\begingroup$ @DerekHolt: Conversely, having "grown up" with Stallings' algorithm, I've never needed to learn the Todd--Coxeter algorithm explicilty, since you can recover it in any group by pulling back to a free group. But I guess Todd--Coxeter comes with no guarantees that it will successfully distinguish cosets in general. $\endgroup$ – HJRW Dec 30 '18 at 15:11
  • 1
    $\begingroup$ Yes, in general if two cosets are equal, then Todd-Coxeter will eventually establish their equality, but you cannot predict how long it will take (which is inevitable since the question is undecidable). But for free groups, where there are no relations, there is a bound on the total time. $\endgroup$ – Derek Holt Dec 30 '18 at 20:36
  • 2
    $\begingroup$ The algorithm is made pretty explicit there. $\endgroup$ – Benjamin Steinberg Dec 30 '18 at 21:44

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.