Sketch of proof

This is a standard application of the theory of covering spaces. Let $p:\widetilde{\Gamma}\rightarrow\Gamma$ be the universal cover, let $\gamma:[0,1]\rightarrow|\Gamma|$ be a path in the homotopy class c and let $v_0=\gamma(0)$ and $v_1=\gamma(1)$. Choose $\widetilde{v}_0\in p^{-1}(v_0)$, let $\widetilde{\gamma}:[0,1]\rightarrow|\widetilde{\Gamma}|$ be the unique lifting of γ such that $\widetilde{\gamma}(0)=\widetilde{v}_0$ and let $\widetilde{v}_1=\gamma(1)$.

The map p induces a bijection between paths $\widetilde{\sigma}$ in $\widetilde{\Gamma}$ from $\widetilde{v}_0$ to $\widetilde{v}_1$ and paths σ in Γ with $[\sigma]=c$; moreover, reduced paths $\widetilde{\sigma}$ are in bijection with reduced paths σ. In particular, since $\widetilde{\Gamma}$ is a tree, there is a unique reduced path in $\widetilde{\Gamma}$ from $\widetilde{v}_0$ to $\widetilde{v}_1$, and thus a unique reduced path in the homotopy class c.

Sketch of proof

We consider the CW complex $|\Gamma|$ and we collapse the subcomplex $|T|$, obtaining a bouquet of circles, one for each pair of reverse edges $\{e,\overline{e}\}\subseteq E'$. This induces an isomorphism at the level of the fundamental groups, since the subcomplex $|T|$ is contractible. In the bouquet of circles, the image of $|\sigma_e|$ crosses the 1-cell corresponding to the pair $\{e,\overline{e}\}$ exactly once, and it doesn’t cross any other 1-cell. The result follows by induction on the number of circles, using van Kampen’s theorem.

Proof. We have $\{s_\alpha+1,s_\alpha+2,...,t_\alpha-2,t_\alpha-1\}\subseteq\{s_1,t_1,...,s_{\alpha-1},t_{\alpha-1}\}$ and in particular neither s_β nor t_β can occur in the interval $\{s_\alpha,s_\alpha+1,...,t_\alpha-1,t_\alpha\}$. The conclusion follows.

Proof. Suppose that the residual path $\sigma'$ isn’t reduced. Then there are integers $s',t'\in\{1,...,\ell\}\setminus\{s_1,t_1,...,s_m,t_m\}$ such that $s' \lt t'$ and $e_{s'}=\overline{e}_{t'}$ and $e_{s'}$ and $e_{t'}$ are adjacent when seen as edges of the residual path $\sigma'$. This means that $\{s'+1,s'+2,...,t'-2,t'-1\}\subseteq\{s_1,t_1,...,s_m,t_m\}$, and in particular we can define the couple $(s_{m+1},t_{m+1}):=(s',t')$ and this provides a reduction process $(s_1,t_1),...,(s_m,t_m),(s_{m+1},t_{m+1})$ for σ, as desired.

Proof. The residual path of the process is a reduced path in the homotopy class $[\sigma]$. But by Proposition 2.2, there is a unique such path. The conclusion follows.

Sketch of proof

It’s easy to prove that the maps $f^i_*:\pi_1(\Gamma^i,*)\rightarrow\pi_1(\Delta_n,*)$ and $f^{i+1}_*:\pi_1(\Gamma^{i+1},*)\rightarrow\pi_1(\Delta_n,*)$ have the same image. Now (ii) follows by induction.

We now consider the covering space $p:({\text{cov}}(H),*)\rightarrow(\Delta_n,*)$. The labelling map $f^i:(\Gamma^i,*)\rightarrow(\Delta_n,*)$ satisfies the condition $f^i_*(\pi_1(\Gamma^i,*))\subseteq p_*(\pi_1({\text{cov}}(H),*))$ on the fundamental groups; by standard results about covering spaces, this implies the existence of a unique lifting of the map $f^i:(\Gamma^i,*)\rightarrow(\Delta_n,*)$ to a map $h^i:(\Gamma^i,*)\rightarrow({\text{cov}}(H),*)$. The condition of being a lifting (i.e. of having $p\circ h^i=f^i$) is equivalent to the condition of hⁱ being label-preserving.

It is immediate to prove that the images of the maps $h^i:\Gamma^i\rightarrow{\text{cov}}(H)$ and $h^{i+1}:\Gamma^{i+1}\rightarrow{\text{cov}}(H)$ are the same. Now (iii) follows by induction.

Since no folding operation is possible on $\Gamma^m$, we have that the labelling map $f^m:\Gamma^m\rightarrow\Delta_n$ sends reduced paths to reduced paths. It follows from Proposition 2.2 that the map $f^m_*:\pi_1(\Gamma,*)\rightarrow\pi_1(\Delta_n,*)$ is injective, and thus the map $h^m_*:\pi_1(\Gamma^m,*)\rightarrow\pi_1({\text{cov}}(H),*)$ is an isomorphism.

Suppose that there are two distinct vertices of $\Gamma^m$ that are identified by h^m. Then there is a reduced non-closed path σ in $\Gamma^m$ that is sent to a closed path $h^m_*(\sigma)$. Since no folding operation is possible on $\Gamma^m$, this implies that $h^m_*(\sigma)$ is reduced. Up to conjugation, we can assume that σ goes from the basepoint $*$ to a different vertex. Take the homotopy class $[h^m_*(\sigma)]$ in $\pi_1({\text{cov}}(H),*)$, use that $h^m_*:\pi_1(\Gamma^m,*)\rightarrow\pi_1(\Gamma^m,*)$ is an isomorphism, and apply Proposition 2.2: there is a unique closed reduced path τ in $\Gamma^m$ from $*$ to $*$ such that $h^m_*(\tau)=h^m_*(\sigma)$. In particular, the two paths $\tau,\sigma$ start at the same point, and while going along them we read the same word $f^m_*(\tau)=f^m_*(\sigma)$: since no folding operation is possible on $\Gamma^m$, this implies that $\tau=\sigma$. But τ is a closed path while σ isn’t, contradiction.

This shows that $h^m:\Gamma^m\rightarrow{\text{cov}}(H)$ is injective on the set of vertices. Since no folding operation is possible on $\Gamma^m$, it follows immediately that h^m is injective, allowing to see $\Gamma^m$ as a subgraph of ${\text{cov}}(H)$. Since h^m induces an isomorphism of fundamental groups, we must have that the image of h^m contains ${\text{core}}_*(H)$, yielding (iv).

Finally, we observe that the final graph $\Gamma^m$ is the image of the unique map $h^0:\Gamma\rightarrow{\text{cov}}(H)$, and thus it doesn’t depend on the chosen folding sequence. Also, the number of folding operations required is exactly $m=\|\Gamma\|-\|\Gamma^m\|$, so it doesn’t depend on the chosen folding sequence either. This proves (i).

Proof. Part (i) is trivial.

For (ii), suppose the sequence $\Gamma^k\rightarrow\cdots\rightarrow \Gamma^m$ contains a rank-preserving folding operation, and let $j\ge k$ be the smallest integer such that $\Gamma^j\rightarrow \Gamma^{j+1}$ is rank-preserving; this means that there are two edges $e_1,e_2$ in $\Gamma^j$ with the same label, an endpoint $v=\iota(e_1)=\iota(e_2)$ in common, and the other endpoints $v_1=\tau(e_1)$ and $v_2=\tau(e_2)$ which are distinct. Let $p:\Gamma^k\rightarrow \Gamma^j$ be the composition of the sequence of folding operations $\Gamma^k\rightarrow\cdots\rightarrow \Gamma^j$: each of those operations is non-rank-preserving, and in particular it induces a bijection on the set of vertices. Let $v',v_1',v_2'$ be the unique vertices of $\Gamma^k$ such that $p(v')=v,p(v_1')=v_1,p(v_2')=v_2$ respectively. Take any edges $e_1',e_2'$ in $\Gamma^k$ such that $p(e_1')=e_1,p(e_2')=e_2$ and notice that we must have $\iota(e_1')=\iota(e_2')=v$ and $\tau(e_1')=v_1,\tau(e_2')=v_2$. Thus it’s possible to fold $e_1'$ and $e_2'$, performing a rank-preserving folding operation on $\Gamma^k$. This gives a contradiction because the sequence of rank-preserving folding operations $\Gamma^0\rightarrow\cdots\rightarrow \Gamma^k$ was maximal.

Part (iii) is trivial.

For part (iv), we observe the following: along the sequence $\Gamma^0\rightarrow\cdots\rightarrow \Gamma^k$, at each step the number of vertices decreases by one, while along the sequence $\Gamma^k\rightarrow\cdots\rightarrow \Gamma^m$ the number of vertices is preserved. Thus k is equal to the number of vertices of Γ minus the number of vertices of ${\text{fold}}(\Gamma)$, regardless of the chosen sequence. By Proposition 3.2, the sum m + k doesn’t depend on the chosen sequence, and thus neither does m.

Proof. If we have $\varphi(b_r)=1$, then we just put b_r in N and then we restrict our attention to the subgroup $\langle b_1,...,b_{r-1}\rangle$. Thus, it’s enough to prove the statement in the case where $\varphi(b_i)\not=1$ for $i=1,..,r$.

Let $\Delta_n$ be the graph given by $V(\Delta_n)=\{*\}$ and $E(\Delta_n)=\{a_1,\overline{a}_1,...,a_n,\overline{a}_n\}$. Let $\Gamma={\text{core}}_*(\langle\varphi(b_1)\rangle)\vee\cdots\vee{\text{core}}_*(\langle\varphi(b_r)\rangle)$ be the labelled graph given by the join of the graphs ${\text{core}}_*(\langle\varphi(b_i)\rangle)$ for $i=1,...,r$ (see Figure 5). For $i=1,...,r$, let β_i be the unique reduced path in ${\text{core}}_*(\langle\varphi(b_i)\rangle)$ representing the element b_i. Let $f:\Gamma\rightarrow \Delta_n$ be the labelling map, inducing a map $f_*:\pi_1(\Gamma,*)\rightarrow\pi_1(\Delta_n,*)$ between the fundamental groups. Let $\theta:F_r\rightarrow\pi_1(\Gamma,*)$ be the isomorphism given by $\theta(b_i)=[\beta_i]$ for $i=1,...,r$. Observe that $f_*\circ\theta=\varphi$ as maps from F_r to $\pi_1(\Delta_n,*)=F_n$.

Let $\Gamma=\Gamma^0\rightarrow\cdots\rightarrow \Gamma^k$ be a maximal sequence of rank-preserving folding operations and let $\Gamma^k\rightarrow\cdots\rightarrow \Gamma^m$ be a maximal sequence of folding operations for $\Gamma^k$, as in Proposition 3.5. The basepoint $*\in \Gamma$ induces a basepoint $*\in \Gamma^j$ for every $j=0,...,m$. Let $p:\Gamma\rightarrow \Gamma^k$ and $q:\Gamma^k\rightarrow \Gamma^m$ be the quotient maps given by the sequences of folds. Let $f^k:\Gamma^k\rightarrow \Delta_n$ and $f^m:\Gamma^m\rightarrow \Delta_n$ be the labelling maps, and observe that the diagram of Figure 6 commutes.

Figure 5.

In the picture, we can see the (geometric realization of the) graph Γ, for the homomorphism $\varphi:\langle b_1,b_2,b_3\rangle\rightarrow\langle a_1,a_2,a_3\rangle$ given by $\varphi(b_1)=a_2\overline{a}_3\overline{a}_1^3$ and $\varphi(b_2)=a_1^2$ and $\varphi(b_3)=a_1^2a_2\overline{a}_3\overline{a}_1$. On the left of the basepoint the graph ${\text{core}}_*(\langle a_2\overline{a}_3\overline{a}_1^3\rangle)$, above the basepoint the graph ${\text{core}}_*(\langle a_1^2\rangle)$ and on the right of the basepoint the graph ${\text{core}}_*(\langle a_1^2a_2\overline{a}_3\overline{a}_1\rangle)$. The three basepoints of the three core graphs are identified into a unique basepoint $*$.

Figure 6.

The diagram commutes.

Our plan now is to study the map φ using the fact that $\varphi=f^m_*\circ q_*\circ p_*\circ\theta$. By Propositions 3.5 and 3.2, we have that $f^m_*$ is injective (and can thus be ignored) and the maps $\theta,p_*$ are isomorphisms. As we will see, the interesting map is $q_*$.

Since p is a homotopy equivalence, the fundamental group of $\Gamma^k$ has rank r. Let T be a maximal tree for $\Gamma^k$, and let $\{e_1,\overline{e}_1,...,e_r,\overline{e}_r\}$ be the list of edges in $\Gamma^k\setminus T$, and for every pair $\{e_i,\overline{e}_i\}$ choose the one which has label in $\{a_1,...,a_n\}$ (and not in $\{\overline{a}_1,...,\overline{a}_n\}$) (without loss of generality assume it’s e_i): these give a basis $[\sigma_1],...,[\sigma_r]$ for the fundamental group $\pi_1(\Gamma^k,*)$, according to Proposition 2.3.

By Proposition 3.5, the map $q:\Gamma^k\rightarrow \Gamma^m$ induces a bijection on the set of vertices (see Figure 4); we consider the maximal tree T for $\Gamma^k$, and we observe that $q\big|_{T}$ is injective and q(T) is a maximal tree for $\Gamma^m$. Let $\{d_1,\overline{d}_1,...,d_s,\overline{d}_s\}$ be the list of edges in $\Gamma^m\setminus q(T)$, and for every pair $\{d_j,\overline{d}_j\}$ choose the one which has label in $\{a_1,...,a_n\}$ (and not in $\{\overline{a}_1,...,\overline{a}_n\}$) (without loss of generality, assume it’s d_j): these give a basis $[\rho_1],...,[\rho_s]$ for the fundamental group $\pi_1(\Gamma^m,*)$, as in Proposition 2.3.

The map $q_*:\pi_1(\Gamma^k,*)\rightarrow\pi_1(\Gamma^m,*)$ is now very easy to describe: we have

\begin{equation*} q_*([\sigma_i])=\begin{cases} 1&\text{if }q(e_i)\in q(T)\\ [\rho_j]&\text{if }q(e_i)=d_j\in \Gamma^m\setminus q(T). \end{cases} \end{equation*}

For each edge d_j in $\Gamma^m\setminus q(T)$ fix an index i(j) such that $q(e_{i(j)})=d_j$. Define the sets

\begin{equation*} N'=\{[\sigma_i] : q(e_i)\in q(T)\}\cup\{[\sigma_{i'}][\sigma_{i(j)}^{-1}] : q(e_{i'})=d_j\text{and }i'\not=i(j)\}\\ M'=\{[\sigma_{i(j)}] : j=1,...,s\} \end{equation*}

and we observe that $M'\cup N'$ is a basis for $\pi_1(\Gamma^k,*)$ and that $q_*$ is injective on $\langle M'\rangle$ and zero on $\langle N'\rangle$. Thus we set $M=\theta^{-1}(p_*^{-1}(M'))$ and $N=\theta^{-1}(p_*^{-1}(N'))$ and this yields (i), (ii) and (iii).

We observe that the construction of the graphs $\Gamma,\Gamma^k,\Gamma^m$ and of the maps $p,q$ is algorithmic. We use the bases $F_r=\langle b_1,...,b_r\rangle$ and $\pi_1(\Gamma,*)=\langle[\beta_1],...,[\beta_r]\rangle$ and $\pi_1(\Gamma^k,*)=\langle[\sigma_1],...,[\sigma_r]\rangle$. The maps θ and θ ⁻¹ are of course explicit in those bases. The map $p_*$ can be algorithmically obtained too, because it is enough to look at the paths $p_*(\beta_i)$ for $i=1,...,r$ and at the occurrences of the edges $e_1,\overline{e}_1,...,e_r,\overline{e}_r$ along those paths. In order to make explicit the map $p_*^{-1}$, we observe that, for $j=1,...,k$, the folding operation $\Gamma^{j-1}\rightarrow\Gamma^j$ induces a pointed homotopy equivalence $|\Gamma^{j-1}|\rightarrow|\Gamma^j|$, and it’s easy to explicitly produce a pointed homotopy inverse $\eta^j:|\Gamma^j|\rightarrow|\Gamma^{j-1}|$; thus, we have $p_*^{-1}=\eta^1_*\circ\cdots\circ\eta^k_*$, and by looking at the homotopy classes $\eta^1_*(\cdots(\eta^{k-1}_*(\eta^k_*([\sigma_i])))\cdots)$ we obtain a writing of $p_*^{-1}([\sigma_i])$ as a word in $[\beta_1],...,[\beta_r]$, for $i=1,...,r$. This shows that M and N can be built in an algorithmic way.

Each of $[\sigma_1],...,[\sigma_r]$ can be written as a word of length at most 2 in the elements of N ^ʹ. For $i=1,...,r$ let $\ell_i$ be the length of the word $\varphi(b_i)$ in the basis $a_1,...,a_n$; the path β_i has length $\ell_i$, and so does the path $p_*(\beta_i)$; in particular, $p_*(\beta_i)$ contains the edges $e_1,\overline{e}_1,...,e_r,\overline{e}_r$ at most $\ell_i$ times, and thus $p_*([\beta_i])$ can be written as a word in $[\sigma_1],...,[\sigma_r]$ of length at most $\ell_i$. Finally, each b_i is a word of length one in $[\beta_1],...,[\beta_r]$. This proves part (iv).

Proof. Apply Theorem 3.8 to the evaluation homomorphism $\varphi_g:H*\langle x\rangle\rightarrow F_n$ (given by the inclusion on H and by $\varphi_g(x)=g$). The algorithm of Theorem 3.8 produces a basis for a free factor N of $H*\langle x\rangle$; the ideal $\mathfrak I_g$ coincides with $\ker{\varphi_g}$, which is the normal subgroup generated by N. The conclusion follows.

Proof. Write the equation w as a cyclically reduced word $c_1x^{\alpha_1}c_2x^{\alpha_2}{\cdots}c_rx^{\alpha_r}c_{r+1}$ with $\alpha_1,...,\alpha_r\in\mathbb Z\setminus\{0\}$ and $c_1,...,c_{r+1}\in H$. Then in the graph Γ we have that $\theta(w)=\theta(c_1)\cdot\theta(x^{\alpha_1})\cdot{\cdots}\cdot\theta(x^{\alpha_r})\cdot\theta(c_{r+1})$ (recall that the · symbol denotes the concatenation of paths, without any homotopy).

1. (i) Fix an edge e of ${\text{core}}(\langle g\rangle)$. Then $\theta(x^{\alpha_i})$ contains exactly one of e and $\overline{e}$, and exactly $|\alpha_i|$ times, for $i=1,...,r$. We have that $\theta(c_i)$ is contained in ${\text{core}}_*(H)$ and thus it doesn’t contain any edge of ${\text{core}}(\langle g\rangle)$. The conclusion follows since $|\alpha_1|+...+|\alpha_r|=d$.

2. (ii) Fix an edge e of ${\text{core}}_*(\langle g\rangle)\setminus{\text{core}}(\langle g\rangle)$. Then $\theta(x^{\alpha_i})$ contains exactly one occurrence of e and exactly one occurrence of $\overline{e}$, for $i=1,...,r$. We have that $\theta(c_i)$ is contained in ${\text{core}}_*(H)$ and thus it doesn’t contain any edge of ${\text{core}}(\langle g\rangle)$. The conclusion follows since $r\le d$.

Proof. Since $(s_i,t_i)$ is a couple of a reduction process for $f_*(\sigma)$, we have that $f(e_{t_i})=f(\overline{e}_{s_i})$. This means that the two edges $e_{t_i}$ and $\overline{e}_{s_i}$ have the same label. Observe that $\iota(e_{t_i})=\iota(\overline{e}_{s_i})$ but $e_{t_i}\not=\overline{e}_{s_i}$, since σ is a reduced path and $t_i=s_i+1$. This means that $e_{t_i}$ and $\overline{e}_{s_i}$ can’t both belong to ${\text{core}}_*(H)$ (because it is folded) and can’t both belong to ${\text{core}}_*(\langle g\rangle)$ (because it is folded too). Thus one of them has to belong to ${\text{core}}_*(H)$ and the other to ${\text{core}}_*(\langle g\rangle)$, and the conclusion follows.

Proof. As in the proof of Lemma 4.5, write the equation w as a cyclically reduced word

\begin{equation*} c_1x^{\alpha_1}c_2x^{\alpha_2}{\cdots}c_rx^{\alpha_r}c_{r+1} \end{equation*}

with $\alpha_1,...,\alpha_r\in\mathbb Z\setminus\{0\}$ and $c_1,...,c_{r+1}\in H$; we have $\sigma=\theta(w)=\theta(c_1)\cdot\theta(x^{\alpha_1})\cdot{\cdots}\cdot\theta(x^{\alpha_r})\cdot\theta(c_{r+1})$. We see that w has degree $d=|\alpha_1|+\cdots+|\alpha_r|\ge r$ and, using Lemma 4.7, that the path σ contains at most 2r innermost cancellations. The conclusion follows.

Proof. We want to show that $\sigma'$ is reduced. For $k=1,...,s_\beta-2$, we have that the two consecutive edges $e_k,e_{k+1}$ in $\sigma'$ also appear as consecutive edges in σ, and since σ is reduced we have $e_k\not=\overline{e}_{k+1}$. The same holds for $k=s_\alpha,...,t_\alpha-1$ and for $k=t_\beta+1,...,\ell-1$. For the two edges $e_{s_\beta-1},e_{s_\alpha}$ that appear consecutive in $\sigma'$, we notice that $e_{s_\alpha}=e_{s_\beta}$ since the couples are parallel, and $e_{s_\beta-1}\not=\overline{e}_{s_\beta}$, yielding $e_{s_\beta-1}\not=\overline{e}_{s_\alpha}$. The same holds for the two edges $e_{t_\alpha},e_{t_\beta+1}$. This proves that $\sigma'$ is reduced.

For every $i\in\{1,...,\ell/2\}$ we have that $e_{s_i}$ is removed from σ if and only if $s_\beta\le s_i \lt s_\alpha$ if and only if (by Lemma 2.6) $t_\alpha \lt t_i\le t_\beta$ if and only if $e_{t_i}$ is removed from σ. Consider the sequence $(s_1,t_1),...,(s_{\ell/2},t_{\ell/2})$ and remove the couples $(s_i,t_i)$ with $s_\beta\le s_i \lt s_\alpha$ (whilst preserving the order of the other couples): the remaining couples contain the indices of the edges that remain in $\sigma'$, the index of each edge appearing exactly once. We can thus apply ω to each number in each of the remaining couples, and we get a sequence of couples $(q_1,r_1),...,(q_{\ell'/2},r_{\ell'/2})$ such that $q_1,r_1,...,q_{\ell'/2},r_{\ell'/2}$ are a permutation of $1,...,\ell'$. Since ω is non-decreasing we also have $q_j \lt r_j$ for $j=1,...,\ell'/2$.

Fix an index $j\in\{1,...,\ell'/2\}$ and we must have $(q_j,r_j)=(\omega(s_i),\omega(t_i))$ for some $i\in\{1,...,\ell/2\}$. Since $(s_1,t_1),...,(s_{\ell/2},t_{\ell/2})$ is a reduction process for σ we have that $\{s_i+1,s_i+2,...,t_i-2,t_i-1\}\subseteq\{s_1,t_1,...,s_{i-1},t_{i-1}\}$: we remove from both those sets the indices in $\{s_\beta,...,s_\alpha-1,t_\alpha+1,...,t_\beta\}$ and we apply ω, and we obtain that $\{q_j+1,q_j+2,...,r_j-2,r_j-1\}\subseteq\{q_1,r_1,...,q_{j-1},r_{j-1}\}$. Finally, we observe that $f(e_{s_i})=f(\overline{e}_{t_i})$ implies $f(e_{q_j})=f(\overline{e}_{r_j})$.

This proves that $(q_1,r_1),...,(q_{\ell'/2},r_{\ell'/2})$ is a maximal reduction process for $f_*(\sigma')$, and it contains all the indices from 1 to $\ell'$. In particular, $f_*(\sigma')$ is homotopically trivial. The conclusion follows.

Proof. Fix an edge e of Γ belonging to ${\text{core}}(\langle g\rangle)$ and apply Lemma 4.5. The sequence of edges of $\sigma'$ is obtained from the sequence of edges of σ by removing some elements of the sequence. In particular, the number of occurrences of e and $\overline{e}$ can’t increase.

Proof. Fix a maximal reduction process $(s_1,t_1),...,(s_{\ell/2},t_{\ell/2})$ for $f_*(\sigma)$. Let $Z=\{(e,e')\in E(\Gamma)\times E(\Gamma) : f(e)=f(e')\}$ be the set of couples of edges with the same label; we have $2\|\Gamma\|$ possibilities for the choice of e, and fixed e we have at most $\|\Gamma\|$ possibilities for the choice of e ^ʹ (each label can appear on at most $\|\Gamma\|$ edges, since reverse edges have inverse label): this shows that $|Z|\le 2\|\Gamma\|^2$.

Define the map $\{1,...,\ell/2\}\rightarrow Z$ given by $i\mapsto (e_{s_i},\overline{e}_{t_i})$. By hypothesis, we have $\ell/2 \gt 2\|\Gamma\|^2\cdot2d$ and thus there is at least one element of Z which is the image of at least $2d+1$ indices $i_1 \lt \cdots \lt i_{2d+1}$ in $\{1,...,\ell/2\}$. This means that we have $2d+1$ pairwise distinct couples $(s_{i_1},t_{i_1}),...,(s_{i_{2d+1}},t_{i_{2d+1}})$ in the reduction process satisfying $e_{s_{i_1}}=e_{s_{i_2}}=\cdots=e_{s_{i_{2d+1}}}$ and $e_{t_{i_1}}=e_{t_{i_2}}=\cdots=e_{t_{i_{2d+1}}}$.

For each $k=1,...,2d+1$, the couple $(s_{i_k},t_{i_k})$ has to contain an innermost cancellation, i.e. there is an innermost cancellation $(q_k,r_k)$ with $s_{i_k}\le q_k \lt r_k\le t_{i_k}$. By Lemma 4.8, there are at most 2d innermost cancellations: since we have $2d+1$ couples $(s_{i_1},t_{i_1}),...,(s_{i_{2d+1}},t_{i_{2d+1}})$, two of them, let’s say $(s_{i_j},t_{i_j})$ and $(s_{i_k},t_{i_k})$ with j < k, have to contain the same innermost cancellation $(q_j,r_j)=(q_k,r_k)$. But by Lemma 2.6, this implies $s_{i_j} \lt s_{i_k} \lt t_{i_k} \lt t_{i_j}$. Thus the two couples $(s_{i_j},t_{i_j}),(s_{i_k},t_{i_k})$ are parallel, as desired.

Proof of Theorem 4.4

Let $w\in\mathfrak I_g$ be a non-trivial equation of degree $d_{\min}$ and of minimum possible length $\ell\ge1$. This in particular implies that w is cyclically reduced. Let σ be the corresponding cyclically reduced lift (which has length $\ell$ too).

Assume by contradiction that $\ell \gt 8\|\Gamma\|^2d_{\min}$. Let $(s_1,t_1),...,(s_{\ell/2},t_{\ell/2})$ be a maximal reduction process for $f_*(\sigma)$: by Proposition 4.12 we can find two parallel couples $(s_i,t_i),(s_j,t_j)$. We perform the corresponding parallel cancellation move (according to Lemma 4.10) and we obtain a path $\sigma'$ of length $\ell'$, with corresponding equation $w'\in\mathfrak I_g$ with $w'\not=1$. Notice that $\ell' \lt \ell$; moreover, by Lemma 4.11, the degree d ^ʹ of w ^ʹ satisfies $d'\le d_{\min}$, but since $d_{\min}$ is the minimum possible this implies $d'=d_{\min}$. But then $\ell' \lt \ell$ contradicts the minimality of $\ell$. This proves the theorem.

Algorithm

We first produce an upper bound D on the minimum degree of an equation in $\mathfrak I_g$; this is done for example by taking any non-trivial equation in $\mathfrak I_g$, which we can construct using the algorithm of Theorem 3.8, and taking its degree D. Given this upper bound D, we take all the non-trivial reduced paths σ in Γ from $*$ to $*$ and of length $\ell\le8\|\Gamma\|^2D$. For each such path σ, we check whether $f_*(\sigma)$ is homotopically trivial (in linear time on a pushdown automaton, with a free reduction process), and we compute the degree of the corresponding equation w. We take the minimum of all the degrees of those equations: this is also the minimum possible degree for a non-trivial equation in $\mathfrak I_g$.

Proof. We observe that Γ consists of the join of ${\text{core}}(H)$, ${\text{core}}(\langle g\rangle)$ and a (possibly trivial) edge-path connecting one point of ${\text{core}}(H)$ to one point of ${\text{core}}(\langle g\rangle)$.

1. (i) Let $\rho=(e_{s_\beta},e_{s_\beta+1},...,e_{s_\alpha})$ and we want to prove that ρ is contained in ${\text{core}}(H)$. Notice that ρ begins and ends with the same edge $e_{s_\beta}=e_{s_\alpha}$.

   Suppose that $e_{s_\beta}$ doesn’t belong to ${\text{core}}(H)$. Then the path ρ is reduced, and begins and ends with a same edge in $\Gamma\setminus{\text{core}}(H)$. This implies that, for every edge e of ${\text{core}}(\langle g\rangle)$, the path ρ is forced to contain either e or $\overline{e}$ at least once. It follows by Lemma 4.5 that the parallel cancellation move can’t be degree-preserving.

   Suppose now that there is an edge e_s with $s_\beta \lt s \lt s_\alpha$ such that e_s doesn’t belong to ${\text{core}}(H)$. Then ρ is reduced, begins and ends in ${\text{core}}(H)$, and contains an edge in $\Gamma\setminus{\text{core}}(H)$. This implies that, for every edge e of ${\text{core}}(\langle g\rangle)$, the path ρ is forced to contain either e or $\overline{e}$ at least once. It follows by Lemma 4.5 that the parallel cancellation move can’t be degree-preserving.

   It follows that $\rho=(e_{s_\beta},e_{s_\beta+1},...,e_{s_\alpha})$ is contained in ${\text{core}}(H)$. Similarly, we have that $(e_{t_\alpha},...,e_{t_\beta})$ has to be contained in ${\text{core}}(H)$, and this proves (i).

2. (ii) Suppose that a couple $(s_i,t_i)$ satisfies $s_\beta \lt s_i \lt t_i \lt s_\alpha$ for some $1\le i \lt \beta$. Then there must be an innermost couple $(s_j,t_j)$ with $s_\beta \lt s_j \lt t_j \lt s_\alpha$ for some $1\le j\le i$. But then by Lemma 4.7, at least one of the edges $e_{s_j},e_{t_j}$ belongs to $\Gamma\setminus{\text{core}}(H)$, contradicting (iv). It follows that no couple $(s_i,t_i)$ can satisfy $s_\beta \lt s_i \lt t_i \lt s_\alpha$; similarly, no couple $(s_i,t_i)$ can satisfy $t_\alpha \lt s_i \lt t_i \lt t_\beta$. By Lemma 2.6, we have that the reduction process has to pair up numbers in $\{s_\beta,s_\beta+1,...,s_\alpha\}$ with numbers in $\{t_\alpha,t_\alpha+1,...,t_\beta\}$, and the pairing has to be done in decreasing order. This proves (ii).

Proof. The fact that $\sigma'$ is reduced follows from the fact that σ is reduced and from the fact that $\rho_1,\rho_2$ are cyclically reduced; here it’s important the property that ρ ₁ begins with $e_{s_\alpha}$ respectively (that grants us that $e_{s_\alpha-1}\not=\overline{e}_1'$ and $e_r'\not=\overline{e}_{s_\alpha}$), and analogous for ρ ₂. A maximal reduction process for $f_*(\sigma')$ is given by $(\nu(s_1),\nu(t_1)),...,(\nu(s_\alpha),\nu(t_\alpha)),(s_\alpha+r-1,t_\alpha+r+1),(s_\alpha+r-2,t_\alpha+r+2),...,(s_\alpha,t_\alpha+2r),(\nu(s_{\alpha+1}),\nu(t_{\alpha+1})),...,(\nu(s_{\ell/2}),\nu(t_{\ell/2}))$; in other words, in order to reduce $\sigma'$, we cancel the same couples of edges as in σ, until we cancel $e_{s_\alpha}$ against $e_{t_\alpha}$; at that point, we cancel ρ ₁ against the reverse of ρ ₂ (and this can be done since by hypothesis we have $f_*(\rho_1)=f_*(\rho_2)$); and then we conclude the reduction process in the same way as in σ. In particular, $f_*(\sigma')$ is homotopically trivial, as desired.

Proof. It follows from Lemma 5.2 that $(\rho_1,\rho_2)$ is an insertion. The insertion move has to be performed at $(s_\beta,2t_\alpha-t_\beta)=(\omega(s_\alpha),\omega(t_\alpha))$, where ω is the ‘reparametrization of indices’ map as in Lemma 4.10. It follows from the definitions that when we apply the parallel insertion move to $\sigma'$ we obtain σ.

Proof. Immediate from the definitions.

Proof. When performing the moves in one order or in the other, we start with the same path σ, and we add the same edges in the same places. The only thing that changes is the order in which the edges are added, but the resulting paths are the same.

Proof. Completely analogous to the proof of Lemma 5.7.

Proof. Completely analogous to the proof of Lemma 5.7.

Proof. If the length of σ is $\ell \gt 8\|\Gamma\|^2d_{\min}$, then by Proposition 4.12 we can perform a parallel cancellation move on σ in order to get a shorter path. The degree can’t strictly increase, by Lemma 4.11, and can’t strictly decrease, since $d_{\min}$ was minimum. Thus, we obtain a strictly shorter path, whose corresponding equation has the same degree $d_{\min}$. We reiterate the process, and after a finite number of parallel cancellation moves we have to obtain a path $\sigma'$ with corresponding equation of degree $d_{\min}$ and of length $\ell'\le8\|\Gamma\|^2d_{\min}$.

Since $\sigma'$ is obtained from σ by means of a finite number of parallel cancellation moves, by Lemma 5.5, this means that σ can be obtained from $\sigma'$ by means of a sequence of parallel insertion moves. Take a sequence of parallel insertion moves $\xi_1,...,\xi_p$ that changes $\sigma'$ into σ and has minimum length p between all such sequences.

Suppose that there are two parallel insertion moves $\xi_q,\xi_r$ with q < r such that ξ_r acts on a couple that is added to the reduction process by ξ_q (see Lemma 5.4): then we take an innermost couple of parallel insertion moves with that property, so that each move ξ_j with $q \lt j \lt r$ acts on a couple in the reduction process different from the one of ξ_r. In particular, by Lemma 5.7, we can change the order in our sequence in order to bring ξ_r adjacent to ξ_q, and we can then apply Lemma 5.9 in order to substitute $\xi_q,\xi_r$ with a single parallel insertion move. This contradicts the minimality of the length p of the sequence.

Thus in our sequence $\xi_1,...,\xi_q$, we have that each insertion move acts on a couple coming from the initial reduction process of $\sigma'$. If two insertion moves $\xi_q,\xi_r$ with q < r act on the same couple, then we reason as above, and by means of Lemmas 5.7 and 5.8 we can substitute them with a single insertion move, contradicting the minimality of p.

It follows that each couple of parallel insertion moves of the sequence $\xi_1,...,\xi_p$ acts on a different couple coming from the initial reduction process of $\sigma'$, and in particular $p\le \ell'/2$. The conclusion follows.

Proof. Fix a maximal reduction process $(s_1,t_1),...,(s_{\ell/2},t_{\ell/2})$ for $f_*(\sigma)$. We say that a couple $(s_i,t_i)$ is bad if one of $e_{s_i},e_{t_i}$ belongs to ${\text{core}}_*(\langle g\rangle)$. There are at most $\|\Gamma\|$ pairs of edges $\{e,\overline{e}\}$ in ${\text{core}}_*(\langle g\rangle)$, and for each of them there are at most 2d edges of σ which are equal to e or $\overline{e}$ (by Lemma 4.5). It follows that there are in total at most $2\|\Gamma\|d$ bad couples.

Consider the set $C=\{1,2,...,\ell\}\setminus\{r : r$ belongs to a bad couple $(s_i,t_i)\}$. This means that we remove at most $4\|\Gamma\|d$ elements from the set $\{1,...,\ell\}$, and thus the remaining set C can be written as a union of at most $4\|\Gamma\|d+1$ intervals: we write $C=C_1\cup...\cup C_a$ with $a\le 4\|\Gamma\|d+1$, where $C_k=\{b_k,b_k+1,...,c_k\}$ for some $1\le b_k\le c_k\le \ell$, in such a way that $c_{k-1}+2\le b_k\le c_k\le b_{k+1}-2$ for $k=2,...,a-1$. We have $|C_1|+...+|C_a|=|C|\ge\ell-4\|\Gamma\|d$ and by hypothesis $\ell-4\|\Gamma\|d\ge16\|\Gamma\|^3d(4\|\Gamma\|d+1)+1$: it follows that there is at least one set $\overline{C}\in\{C_1,...,C_a\}$ of size at least $|\overline{C}|\ge 16\|\Gamma\|^3d+1$.

We observe that there is no couple $(s_i,t_i)$ with both $s_i,t_i\in\overline{C}$: otherwise, we could find an innermost cancellation $(s_j,t_j)$ with $s_i\le s_j \lt t_j\le t_i$, and by Lemma 4.7 $(s_j,t_j)$ would be a bad couple, and thus $\overline{C}$ would contain elements of a bad couple, contradiction. Let $Z=\{(e,e',C_k) : e,e'\in E(\Gamma)$ with $f_*(e)=f_*(e')$ and $C_k\in\{C_1,...,C_a\}$ with $C_k\not=\overline{C}\}$: we have $2\|\Gamma\|$ possibilities for choice of e, fixed e we have at most $\|\Gamma\|$ possibilities for the choice of e ^ʹ, and we have at most $4\|\Gamma\|d$ choices for C_k; it follows that $|Z|\le 8\|\Gamma\|^3d$.

Without loss of generality, assume $\overline{C}$ contains at least $8\|\Gamma\|^3d+1$ elements s_i belonging to couples $(s_i,t_i)$ of the reduction process (otherwise $\overline{C}$ has to contain at least $8\|\Gamma\|^3d+1$ elements t_i belonging to couples $(s_i,t_i)$ of the reduction process, and the reasoning is analogous). To each such edge s_i, we associate the triple $(e_{s_i},\overline{e}_{t_i},C_k)\in Z$, where $C_k\in\{C_1,...,C_a\}\setminus\{\overline{C}\}$ is the connected component to which t_i belongs. Since we have at least $8\|\Gamma\|^3d+1$ edges s_i in $\overline{C}$, and at most $|Z|\le 8\|\Gamma\|^3d$ possible triples, there are at least two elements $s_{i_1},s_{i_2}$ with the same associated triple $(e_{s_{i_1}},\overline{e}_{t_{i_1}},C_k)=(e_{s_{i_2}},\overline{e}_{t_{i_2}},C_k)$.

It immediately follows that $(s_{i_1},t_{i_1})$ and $(s_{i_2},t_{i_2})$ are parallel couples. Without loss of generality we can assume that $s_{i_1} \lt s_{i_2}$; we have that the interval $\{s_{i_1},s_{i_1}+1,...,s_{i_2}\}$ is contained in $\overline{C}$ and the interval $\{t_{i_2},t_{i_2}+1,...,t_{i_1}\}$ is contained in C_k. Thus, when we perform the parallel cancellation move relative to the couples $(s_{i_1},t_{i_1})$ and $(s_{i_2},t_{i_2})$, we only remove edges whose image is in ${\text{core}}_*(H)$. We conclude from Lemma 4.5 that the cancellation move is degree-preserving, as desired.

Proof. Take any non-trivial equation w in $\mathfrak I_g$ of degree d and minimum possible length $\ell\ge1$. This implies that w is cyclically reduced. Let σ be the corresponding cyclically reduced lift (which has length $\ell$ too). If $\ell \gt 64\|\Gamma\|^4d^2+16\|\Gamma\|^3d+4\|\Gamma\|d$ then by Proposition 5.11 we can perform a degree-preserving cancellation move on σ, and thus we can find a non-trivial equation in $\mathfrak I_g$ of degree d whose corresponding lift is strictly shorter, contradiction. Thus we must have $\ell\le 64\|\Gamma\|^4d^2+16\|\Gamma\|^3d+4\|\Gamma\|d$, and the conclusion follows.