Is there an algorithm that, given a finite presentation of a free group, outputs a free basis for the group?

Question

I have been stuck on this problem for two weeks, and I'm not sure I believe it to be true anymore. I have no idea how to proceed. I know nothing about algorithms or how to find them, this is my first time trying a question of this sort and I am at the end of my wits. Can someone give me a hint in the right direction?

Answer 1

Hint: Suppose $G$ is a free group on $n$ generators (for some finite $n$). Then a set $S\subseteq G$ is a free basis for $G$ iff $S$ generates $G$ and $|S|\leq n$ (see Is a free group of finite rank Hopfian? for instance). So, you can search through all possible $n$-tuples until you find one that generates.

More details are hidden below.

First, you can compute the rank $n$ of the free group from its presentation by abelianizing and using linear algebra. Now given any finite list $S$ of words in the generators, you can test whether $S$ generates the group by just trying all possible ways to string together elements of $S$ and their inverses and then reduce them using the relations, to see whether you eventually get all the generators in the presentation. (This will eventually halt if $S$ does generate, but will run forever if $S$ does not generate.) Now dovetail this test for all possible lists $S$ of $n$ words. Since the group is free on $n$ generators, you must eventually find some $S$ that does generate, and therefore must be a free basis since it has at most $n$ elements.