a (source code)
= a
{scope}
We construct the output presentation explicitly, using <HNN extensions> and an <amalgamated free product>. Throughout, $P$ also denotes the group given by the input <finite group presentation>, and $X=\{x_1,\ldots,x_n\}$. Every word introduced below is a literal computable word in the displayed generators; testing whether $w=1$ is never part of the construction.
First fix the auxiliary <Higman group>
$$
Q=\langle a_1,a_2,a_3,a_4\mid a_i a_{i+1}a_i^{-1}=a_{i+1}^2\ (i\bmod4)\rangle.
$$
We need two facts: $\langle a_1,a_3\rangle$ is a <free group> of rank two, and the <normal closure> of $a_1$ is $Q$. The latter follows immediately from the relations: setting $a_1=1$ forces successively $a_2=a_2^2$, $a_3=a_3^2$, and $a_4=a_4^2$, hence all three are $1$.
Here is a normal-form verification of the first fact. The three-generator group
$$
Q_{123}=\langle a_1,a_2,a_3\mid a_1a_2a_1^{-1}=a_2^2,\ a_2a_3a_2^{-1}=a_3^2\rangle
$$
is an <amalgamated free product> of two <Baumslag-Solitar groups> $BS(1,2)$ along their infinite cyclic subgroups generated by $a_2$. Their base cyclic groups embed by <Britton's lemma>, so this amalgamation is legitimate. Nonzero powers of $a_1$ in the first factor lie outside $\langle a_2\rangle$, as shown by the homomorphism recording the exponent of its stable letter $a_1$. Nonzero powers of $a_3$ in the second factor also lie outside $\langle a_2\rangle$: the stable-letter exponent map first forces a putative equality $a_3^r=a_2^s$ to have $s=0$, and then injectivity of the base cyclic group forces $r=0$. The <normal form theorem for an amalgamated free product> therefore makes $\langle a_1,a_3\rangle$ a rank-two <free group> in $Q_{123}$.
The same argument applies to $Q_{341}$, formed from the other two cyclic conjugation relations. The full $Q$ is $Q_{123}*_{\langle a_1,a_3\rangle}Q_{341}$, so that rank-two <free group> embeds in $Q$ as well. In particular $a_1$ has infinite order.
Now take the <free product>
$$
D=P*F(z,d),\qquad c=[w,z]=wzw^{-1}z^{-1},\qquad C=d^{-1}cd,
$$
and set
$$
g_0=z,\qquad g_1=d,\qquad g_{i+1}=x_i z\quad(1\le i\le n).
$$
Introduce $n+2$ letters $u_0,\ldots,u_{n+1}$, and define the finite presentation
$$
H=\langle X,z,d,u_0,\ldots,u_{n+1}\mid R,\ u_j^{-1}cu_j=g_j\ (0\le j\le n+1)\rangle.
$$
Finally impose the Higman relations and identify
$$
C=a_1,\qquad u_j=a_3^{j+1}a_1a_3^{-(j+1)}\quad(0\le j\le n+1).
$$
Thus the algorithm outputs
$$
\boxed{\begin{aligned}
P(w)=\langle &X,z,d,u_0,\ldots,u_{n+1},a_1,a_2,a_3,a_4\mid\ R,\\
&u_j^{-1}cu_j=g_j\ (0\le j\le n+1),\quad
a_i a_{i+1}a_i^{-1}=a_{i+1}^2\ (i\bmod4),\\
&C=a_1,\quad u_j=a_3^{j+1}a_1a_3^{-(j+1)}\ (0\le j\le n+1)\rangle.
\end{aligned}}
$$
The symbols $c,C,g_j$ in this display are abbreviations for the explicit words above, not extra generators. Renaming the finitely many new generators to avoid $X$ makes this a uniform effective construction.
Back to article page
