Word problem in residually finite groups - enumerating normal subgroups

Question

I am trying to prove that the word problem is solvable for residually finite, finitely presented groups. It is known that one runs two algorithms in parallel. One algorithm stops when the word $w$ is trivial and the other when it is not. I am trying to reconstuct the second algorithm. Literature says that the algorithm works as follows:

1. Enumerate all finite index normal subgroups $N$ / all homomorphism to finite groups $\phi:G\to Q$;
2. For every normal subgroup, check whether $w$ lies in $N$, or check whether $w$ becomes trivial under the homomorphism $\phi$;
3. If $w$ does not lie in $N$ or $\phi(w)\neq 1$ then $w$ is not trivial in $G$. (End the algorithm.)

My question is as follows: How does one enumerate all the normal subgroups or all homomorphism to all finite groups? So far I succeeded in doing these things:

• I can algorithmically enumerate all subgroups of index $n$ as $\text{Stab}_G(1)$ for homomorphism $G\to S_n$, where $G$ transitively on $\{1,2,\dots n\}$.

How does one decide whether the subgroup is normal in $G$? It would suffice to find generators of $\text{Stab}_G(1)$, but how does one do so? Or is there another method?

It is quite important for my work that the enumeration goes from small to larger indices.

Answer 1

Let me answer the alternative question Or is there another method?

The alternative method is, first, to ignore normal subgroups and focus on homomorphisms. Also, in Step 1, focus just on finite symmetric groups $S_n$ instead of arbitrary finite groups (taking advantage of Cayley's Theorem which embeds each finite group into a finite symmetric group $S_n$).

So, with these changes, your 3 steps become:

1. Enumerate all homomorphisms to finite symmetric groups $\phi : G \to S_n$ ($n \ge 2$).

To do this, as said in the comments, from the given finite presentation $G = \langle S \mid R \rangle$ such that $S=\{s_1,...,s_d\}$, enumerate all $d$-tuples in $S_n$, map the generating $d$-tuple $s_1,...,s_d$ to each $d$-tuple of $S_n$ in turn, and check whether each relation in $R$ is satisfied: if so then you have a homomorphism $\phi : G \to S_n$ and you go to Step 2; otherwise continue looping Step 1 (with the next $d$-tuple, or with the next $n$ if you've exhausted all $d$-tuples in $S_n$).

2. Check whether $\phi(w)$ is trivial in $S_n$: if so then continue looping Step 1.

Just to clarify one issue, $w$ has already been given as a specific word in the generators $s_1,...,s_d$, so $\phi(w) \in S_n$ is easily calculated.

3. If $\phi(w)$ is not trivial in $S_n$ then $w$ is not trivial in $G$. (End the algorithm.)