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.

Improve this question
$\endgroup$
5
  • $\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
    Commented Dec 30, 2018 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
    Commented Dec 30, 2018 at 4:23
  • $\begingroup$ oops, right. sorry for noise. $\endgroup$
    – Dima Pasechnik
    Commented Dec 30, 2018 at 4:27
  • 3
    $\begingroup$ This is known as "solvable uniform (subgroup) membership problem". $\endgroup$
    – YCor
    Commented Dec 30, 2018 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$
    – Nico A
    Commented Dec 30, 2018 at 16:06

1 Answer 1

Reset to default
18
$\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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ In fact the algorithm can be thought of as a special case of Todd-Coxeter coset enumeration. $\endgroup$
    – Derek Holt
    Commented Dec 30, 2018 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
    Commented Dec 30, 2018 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
    Commented Dec 30, 2018 at 20:36
  • 2
    $\begingroup$ The algorithm is made pretty explicit there. $\endgroup$
    – Benjamin Steinberg
    Commented Dec 30, 2018 at 21:44

You must log in to answer this question.

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