Let $F$ be a free group on a finite set $X$, and let $M$ be a finitely generated subgroup.

Marshall Hall's theorem states that $M$ is closed in the profinite topology on $F$. That is, $M$ is the intersection of some family of finite index subgroups of $F$.

Is there a purely algebraic/algorithmic proof of this fact not using any topological argument?

What I mean is that I expect the proof to go more or less like:

Let $m_1, \dots m_r$ be a finite set of generators for $M$, and take some $t \notin M$. It is sufficient to find an open subgroup containing $m_1, \dots, m_r$ bot not $t$. For this we just need to find an epimorphism to a finite group $\phi : F \rightarrow G$ such that $\phi(t)$ is not generated by $\phi(m_1), \dots, \phi(m_r)$. Here comes some construction (which should better be a computable function of $m_1, \dots,m_r,t$) of $G$ and $\phi$ ...


closed as off-topic by HJRW, Stefan Kohl, Ryan Budney, Daniel Moskovich, Benjamin Steinberg Nov 11 '14 at 3:02

  • This question does not appear to be about research level mathematics within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Pablo, every f.g. subgroup $M$ of a f.g. free group $F$ is a free factor of a finite-index subgroup of $F$. So, the problem is reduced to the case where $M$ is a free factor of $F$, where it is quite easy. $\endgroup$ – Anton Klyachko Nov 9 '14 at 16:44
  • 2
    $\begingroup$ Surely, there is an algorithm for finding this finite-index subgroup and the free complement in this subgroup. Just look at the proof of Hall's free-factor theorem. It is quite easy using Stallings graphs.. $\endgroup$ – Anton Klyachko Nov 9 '14 at 17:01
  • 2
    $\begingroup$ @Pablo, if you read the standard 'topological' proof carefully, it's easy to construct the homomorphism you want (to the group of permutations of the vertices of the graph you build). Alternatively you could read Marshall Hall's original (1949) paper, in which he uses no topology. $\endgroup$ – HJRW Nov 9 '14 at 19:15
  • 5
    $\begingroup$ Here's another point of view on the topological argument. The Stallings graph argument exhibits an algorithmic construction of the desired epimorphism. While it may be that one uses topology to prove that the algorithm does what one wants it to do, that does not detract from the fact that it is an algorithm. Furthermore, the topology proof itself is very algebraic, because it involves only finite graphs, and the boundary between the topology and the combinatorics of finite graphs is very, very thin. $\endgroup$ – Lee Mosher Nov 9 '14 at 20:14
  • 4
    $\begingroup$ This question has been answered in comments. $\endgroup$ – HJRW Nov 10 '14 at 11:31