# Is there an algorithm to decide if a word is in a finitely generated subgroup of a free group?

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.

• 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... – Dima Pasechnik Dec 30 '18 at 4:21
• @DimaPasechnik: What you write down is not a group since the subgroup you are trying to take the quotient by is not normal. – Andy Putman Dec 30 '18 at 4:23
• oops, right. sorry for noise. – Dima Pasechnik Dec 30 '18 at 4:27
• This is known as "solvable uniform (subgroup) membership problem". – YCor Dec 30 '18 at 5:31
• 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 – Nico A Dec 30 '18 at 16:06

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'$$.