Free groups are nevertheless the archetype of an effectively coherent class of groups: any subgroup of a free group is free, but the task is to compute a basis. Stallings foldings provide an  algorithmic and elegant way for this.

In a work that that deepens the foldings technique, Kapovich Weidmann and Miasnikov proved that fundamental groups of so-called benign graphs of groups are effectively coherent <cit.>.

We will prove that unipotent linear suspensions of finitely generated free groups are  effectively coherent (Proposition <ref>) by proving the benign character of their structural graph of groups decompositions.

Following <cit.>, we say that a class of groups is
hereditarily algorithmic tractable, if

the class is closed for taking finitely generated subgroups, is effectively coherent,

the presentations of the groups in the class being furthermore recursively enumerable, and if the class has uniform solution to the generation problem, and to the conjugacy problem.

In other words, there is an algorithm that given a group presentation in the class, and any finite subset of the group, produces a finite presentation of the generated subgroup, indicates if it is the whole group, and tells whether the given elements are conjugate.

This combination of algorithmic problems is useful to treat and compare decomposition in graphs of groups in which the elements of the class are vertex groups, see for instance <cit.>. Through Propositions <ref>, <ref>, and <ref>, we will prove the following.

The class of finitely generated subgroups of a given piecewise trivial suspension
of a free group is an hereditarily algorithmically tractable class.

An immediate application of this work is that we will be able fulfill the hypotheses of Proposition <ref> and Corollary <ref> and therefore algorithmically construct the canonical structural splittings of suspensions as well as of subgroups of suspensions, which in turn is foundation for the computations in Sections <ref> and <ref>.

§.§ Effective coherence, effective generation, subgroup membership

Recall a definition introduced by Kapovich, Weidmann, and Miasnikov <cit.>.

A finite graph of groups $\bbA$ is benign if the following
conditions are satisfied:

*  For each vertex $v \in \verts A$ and an edge $e
\in \edges A$ with $o(e)=v$ there is an algorithm with the
following property. Given a finite set $X \subset A_v$ and an
element $a \in A_v$ the algorithm decides whether
\[I = \bk X
\cap a \alpha_e(A_e)\]
is empty. If $I \neq \emptyset$, the
algorithm produces an element of $I$.

*  Every edge group $A_e$  of $\bbA$ is slender.

*  Every edge group $A_e$ of $\bbA$ has solvable uniform
membership problem, i.e. there is an algorithm which, given a
finite subset $X \subset A_e$ and an element $a \in A_e$ decides
whether or not $a \in \bk X$.

*  For each vertex $v \in \verts A$ and edge $e \in \edges A$
with $o(e) = v$ there is an algorithm with the following
property. For any finite subset $X \subset A_v$ the algorithm computes a
finite generating set for the subgroup $\alpha_e(A_e) \cap \bk X.$

Observe that conditions $(i)$ to $(iv)$ are conditions on vertex
groups, edge groups and the attachment maps of their adjacent edges groups. From an algorithmic viewpoint, we prefer to state this definition in the context of graphs of groups, however, it can also be stated in the context of $G$-trees with immediate rewriting.

Let $\bbX$ be  a finite graph of groups, such that any vertex group  $\bbX_v$
is of the form $\freegp{v} \oplus \bk {z_v}$, where $\freegp{v}$ is a
free group and any attached image of edge group $\alpha_e(\bbX_e)\leq \bbX_v$ is of the form
$\bk{c_v,z_v}, c_v \in \freegp{}$, then $\bbX$  is benign: properties (<ref>) and
(<ref>) of Definition <ref> hold.

Consider the vertex group $\bbX_v= \freegp{} \oplus \bk z$, and an
adjacent edge $e$, with attaching map $\alpha_e: \bbX_e\to \bbX_v$.  Consider the standard projection
$\pi_{\freegp{}}: \freegp{} \oplus \bk z \onto \freegp{}$. Given any finite set
$S \subset \freegp{} \oplus \bk z$ it is possible to compute the image
$\bar S = \pi_{\freegp{}}(S)$. By hypotheses the groups $\alpha_e(\bbX_e)$
that occur in Definition <ref> are subgroups of the
form $\bk{c, z}$ where $c \in \freegp{}$.  In particular such groups
contain $\ker(\pi_{\freegp{}})$. Therefore
$I = \bk S \cap a \alpha_e(\bbX_e) \neq \emptyset$ if and only if
$\bar S \cap a\bk c \neq \emptyset$, which is routine to check in
a free group. Because $g \in a\bk{c, z}$ if and only if $[a^{-1}g,c]=1$, an
element of the intersection can be found by enumerating $\bk{S}$
and checking whether the commutator vanishes. (<ref>) of Definition
<ref> therefore holds.

We now show that property (<ref>) of Definition
<ref> holds.

\[ S =(f_1z^{n_1},\ldots,f_kz^{n_k})\]
and perform
Nielsen reduction (see <cit.>)
on the tuple $(f_1z^{n_1},\ldots,f_kz^{n_k})$ ignoring the
$z$-letters. This will give a tuple
\[
R=(r_1z^{m_1},\cdots, r_j z^{m_j},1\cdot z^{m_{j+1}},\ldots,1\cdot z^{m_k})
\]
with $r_i \neq 1$ for $i\leq j$ (we allow $j=0$). Let
$e = \gcd(m_{j+1},\ldots,m_k)$ then we
\[ \bk{S} = \bk{r_1z^{m_1},\cdots, r_j z^{m_j}}\oplus\bk{z^e}
\]
with $\pi_{\freegp{}}(\bk{S})=\bk{r_1,\cdots, r_j}=\bk{\bar S}$, where the
$r_i$ form a basis of $\bk{\bar S}$. It is possible to decide the
minimal exponent $l$ such that $\bk{\bar S} \cap \bk c =\bk{c^l}$
and to find the explicit (possibly empty) product (or word)
$c^l=W(r_1,\cdots, r_j)$. It follows
\[ \bk{S} \cap \bk{c,z} = \bk{W(r_1z^{m_1},\cdots,
r_jz^{m_j}),z^e} = \bk{c^lz^{m_1+\cdots+m_j},z^e},\]
with $e$
possibly zero and with $l=0$ if and only if
$\bk c \cap \bk{\bar S} =\{1\}$. Since every step was computable,
(<ref>) of Definition <ref> holds.

We will use the benign property with the following result  of Kapovich Weidmann and Miasnikov.

Let $\bbA$ be a benign graph of groups such that every vertex
group is effectively
and has  solvable uniform membership problem. Then
$\pi_1(\bbA, a_0)$ is also effectively coherent and has solvable
uniform membership problem. Moreover, the algorithms for these two problems can be constructed from those given by the assumption.

From this theorem we deduce the following, about piecewise trivial suspensions of free groups.

If $\torus \alpha$ is a piecewise trivial suspension
of a free group, then it is

effectively coherent and has effectively
solvable uniform membership problem.

Given the abelian splitting
$\torus \alpha$, properties (<ref>) and (<ref>) of
Definition <ref> follow immediately. Let us now focus
on groups of the form $\freegp{} \oplus \bk z$, where $\freegp{}$
is free. Properties (<ref>) and (<ref>) follow from
Proposition <ref>. The result now follows from
Theorem <ref>.

Treating a finite subset of a subgroup of $\torus \alpha$ as generting a subgroup of $\torus \alpha$, we immediately obtain:

The class of finitely generated subgroups of piecewise trivial suspensions over  finitely generated free groups is effectively coherent.

We can also solve the generation problem.

The class of finitely generated subgroups of piecewise trivial suspensions over  finitely generated free groups has uniform solution to the generation problem.

More generally, if a class of groups  is (uniformly) effectively
coherent, and has a uniform (over the groups in the class) solution
to the uniform (over the f.p. subgroups in a group) membership
problem, then it has a uniform  solution to the generation problem
for its subgroups.

Let us prove the second assertion. Given a subgroup $H$ given by generators $\calS_H$, and a family $\calS_K$ of elements, one can compute a presentation of $H$ and a presentation of $\langle \calS_K \rangle$, one can then use the uniform membership problem for f.p. subgroups to determine whether $ \calS_K  < H$ and $\calS_H  < \langle \calS_K \rangle$. The first assertion then follows from Proposition <ref>.

§.§ Consequences of effective coherence: computing canonical splittings and solving the conjugacy problem in subgroups

We are now in a position to compute canonical splittings of finitely generated subgroups of $\torus\alpha$. Since effective coherence lets us algorithmically obtain a presentation for finitely generated subgroups and since subgroups of $\torus\alpha$ are without 2-torsion and have solvable word problem, we can apply <cit.> to get:

Given a finite generating set of a subgroup $H$ of a piecewise trivial suspension, we can compute a Grushko decomposition and a presentations of the indecomposable free free factors. In particular we can decide if $H$ is freely indecomposable.

Let $S=\{h_1,\ldots,h_r\}$ be a collection of elements in a piecewise trivial suspension $\Gamma=\torus\alpha$. Then we can compute a Grushko decomposition of $H = \bk S$ and for each one-ended free factor of $H$ we can compute the canonical splitting $\hat\bbX$ given by Corollary <ref>.

Proposition <ref> and Corollary <ref> enable us to get presentations for the freely indecomposable free factors of $H$, or to assert that $H$ is in fact a free group.

Note that the free group $F$ is hereditarily algorithmicaly tractable and that it is possible to compute centralizers of cyclic subgroups in subgroups of $F$. It follows that the requirements of Corollary <ref> are fulfilled for the one-ended free factors of $H$, and therefore that it allows to compute the canonical splitting $\hat\bbX$.

Bogopolski, Martino, Maslakova, and Ventura <cit.> proved that the conjugacy problem in [finitely-generated free]-by-cyclic groups is solvable. We can extend this result to finitely generated subgroups.

The Conjugacy Problem is uniformly solvable for the class of finitely generated subgroups of a piecewise trivial suspension of a free group.

Although the proof below invokes Proposition <ref>, which is only proved later, we note that this Proposition <ref> is not actually used anywhere else in this paper so there is no circular logic. Proposition <ref> is a statement about the normal forms that we develop in Section <ref>.

Given a generating set $S$ of a piecewise trivial suspension, by Corollary <ref> we can decide if $H=\bk S$ is freely decomposable, and if so find a Grushko decomposition of $\bk S$. The reduction of the conjugacy problem in a freely decomposable group to the conjugacy problem of its one-ended free factors is classical <cit.>, so it is enough to prove that the conjugacy problem is solvable in the case where $H=\bk S$ is one-ended.

Consider such a subgroup $H$, and the canonical tree constructed in Corollary <ref>, that is computable by Proposition <ref>. Then the result for hyperbolic elements follows immediately from Proposition <ref>.

Denote by $\bbX$ the canonical splitting for $H$. If $g,g' \in H$ are elliptic, then given an explicit graph of groups decomposition, we can decide whether $g,g'$ are conjugate into the same vertex group $\bbX_v$. We claim that if $g,g'$ are conjugate into $\bbX_v$ then we can decide whether they are conjugate in $H$.

Indeed, Let $T_g = \{x \in T|g\cdot x = x\}$ be the pointwise fixed subtree tree of $g$ and define $T_{g'}$ analogously. By hypothesis, $v \in T_g \cap T_{g'}$ and the hypothesis that there is some $h$ such that $hgh^{-1}=g'$ implies that $h\cdot T_g = T_{g'}$. If $g,g' \in \bbX_v$ are not conjugate into any images of edge groups then $T_g=T_{g'}=v$ so $h \in \bbX_v$ as required. In this case the conjugacy problem is reduced to the conjugacy problem in a free group or a trivial suspension of a free group.

Otherwise, observing that $H=\pi_1(\bbX,v)  \leq \Bass(\bbX)$ is a free factor, we have that if $g,g'$ are conjugate in $\Bass(\bbX)$ then there must be some reduced $w=a_0e_1a_1\cdots e_n a_n$ with the $e_i$ being symbols in $(\edges X)^{\pm 1}$ and $a_i \in \bbX_{v_i}$ and we have

\begin{equation}\label{eqn:conj}
\bbX_v \ni g' = (a_n^{-1}\bar e_n \cdots \bar e_1 a_0^{-1}) g (a_0e_1a_1\cdots e_n a_n).
\end{equation}

For the right hand side expression to cancel down to $g'$ we need $e_1,\ldots,e_n$ to be a loop based at $v$ and $w$ needs to be an element of $\pi_1(\bbX,v)$. Furthermore, if we consider the dual Bass-Serre tree $T$, pick some lift $\verts T \ni \tilde v$ of $v$, and identify $\bbX_v$ with $H_{\tilde v}$, then (<ref>), says that $g$ stabilizes $v$ and $w\cdot v$ and $d(v,w\cdot v)=n$. By 4-acylindricity $n\leq 4$. We distinguish two cases.

Case 1: If $v$ is a abelian black vertex, then we can assume $a_0$ is trivial and $\bar e_1 g e_1=g_1$ lies in lies in the image of an edge group in $\bbX_{v_1}$. Now if $e_2 = \bar e_1$ then $a_1$ needs to centralize $\bar e_1 g e_1$ which means $a_1$ is in the image of the same edge group; contradicting that $w$ is reduced. Otherwise  $g_1$ is conjugate into the image of the edge group associated to $e_2$. By our description of the canonical splitting of $H$, this is only possible if $g_1$ is a non-trivial element of the center of the white vertex group $\bbX_{v_1}$, in which case $a_1^{-1}g_1a_1= g_1$. Let $g_2 = \bar e_2 g_1 e_2$ then $g_2 \in \bbX_{v_2}$ which, again, is a black abelian vertex group so $a_2^{-1}g_1 a_2=g_2$, so we can assume $a_2$ is trivial and since $w$. If $v_2=v$ and $n=2$ we have $g' = \bar e_2 \bar e_1 g e_1 e_2$.

If $n > 2$ then $n=4$ as all loops in $X$ must have even length. Let $g_3 = \bar e_3 g_2 e_3 = \bar e_3 \bar e_2 \bar e_1 g e_1 e_2 e_3$. We must have that $g_3$ is conjugate in $\bbX_{v_3}$ to the image of the edge group associated to $e_4$, which is distinct from the image of the edge group associated to $e_3$ in $\bbX_{v_3}$. Again this is only possible if $g_3$ is in the center of $\bbX_{v_3}$, which is a non-abelain white vertex group. Now, the equality $g_3 = \bar e_3 \bar e_2 g_1 e_2 e_3$ in $\Bass(\bbX)$ translates to the fact that there are vertices $w,w'$ distinance 2 apart and some non-trivial element $h \in H$ that lies in the center of $H_w$ and $H{w'}$, but since we know that central elements in white vertices fix the ball of radius 2 about those vertices, we get a contradiction to 4-acylindricity.

It follows that in Case 1, it is enough to take all loops $\ell=e_1e_2$ of length 2 based at $v$ in $X$ and verify if $g' = \bar{\ell} g \ell$, to decide whether $g,g'$ are conjugate.

Case 2: If $v$ is a non-abelian white vertex, then a similar analysis to Case 1 above lets us conclude that either
\[
g' = a_2^{-1}\bar e_2\bar e_1a_0^{-1} g a_0 e_1e_2a_2
\]
where $g$ is conjugated in $\bbX_v$ by $a_0$ into the image of the edge group associated to $e_1$ and $g'$ is is conjugated in $\bbX_v$ by $a_2^{-1}$ into the image of the edge group associated to $e_2$, or
\[
g' = a_4^{-1}\bar e_4\bar e_3 \bar e_2e_1a_0^{-1} g a_0 e_1e_2e_3e_4a_4,
\]
where $g$ is conjugated in $\bbX_v$ by $a_0$ into the image of the edge group associated to $e_1$ and $g'$ is is conjugated in $\bbX_v$ by $a_4^{-1}$ into the image of the edge group associated to $e_4$, and in particular $\bar e_2 \bar e_1 a_0^{-1} g a_0 e_1 e_2$ is in the center of $\bbX_{v_2}$. Note that for $H$, in a non-abelian white vertex group, the normalizer of the image of an edge group acts trivially on that subgroup by conjugation.

It follows that in Case 2, to decide if $g,g'$ are conjugate, it is enough to consider all loops $\ell$ of length 4 based at $v$, to decide if there are elements $a,a'$ that conjugate $g,g'$ (respectively) into the appropriate edge groups and check whether $g'=a'^{-1} \bar\ell a^{-1} g a \ell a'$.

Thus in both cases the problem reduces to deciding  if $g,g'$ are conjugate into the edge groups (which is trivial for abelian black vertex groups) and then if these conjugates, which are unique, are "immediately" conjugate by the Bass-Serre relations, i.e. a finite composition (at most 4) of the edge group monomorphisms specified in $\bbX$ and their inverses bring the conjugate of $g$ to the conjugate of $g'$.

The following restatement of what was shown in the proof above will be useful.

$g,h \in \bbX_v$ are conjugate in $\Bass(\bbX)$ if and only if either

* $g$ and $h$ are conjugate in $\bbX_v$, or

* $g$ is conjugate in $\bbX_v$ to $g' \in \tau_{e}(\bbX_e)$, $h$ is  conjugate in $\bbX_v$ to $h' \in \tau_{e'}(\bbX_{e'})$. The conjugates $g',h'$ are unique and there is some $\ell$ that is an edge path in $X$ based at $v$ of length at most 4 such that $g' = \ell g' \bar\ell$ in $\Bass(\bbX)$

§ THE MIXED WHITEHEAD PROBLEM IN  PIECEWISE TRIVIAL SUSPENSIONS.

The action of $G$ on itself by conjugation extends on the set of all tuples, which is    $G^{(\bbN)}= \sqcup_{n>0}  G^n $ (all our tuples are ordered).   If $T\in G^{(\bbN)}  $, we write $[T]$ for its conjugacy class, that is,  the orbit of $T$ under the action of $G$ by conjugation.

The mixed Whitehead problem under a subgroup $H$  of $\aut G$ or of $\out G$,  is the following decision problem. Given an integer $k$, and   for  all $i\in \{1, \dots, k\}$   two tuples  $S_i \in G^{(\bbN)} $ and $T_i \in G^{(\bbN)} $,    decide whether there exists an automorphism $\sigma \in H$ such $\forall i, \,     [\sigma (S_i)] = [T_i]$.
If there exists such $\sigma$, we say that  $\vec S = (S_1, \dots, S_k)$ and $ \vec T = (T_1,\dots T_k)$  are mixed Whitehead equivalent under $H$.

In <cit.> the mixed Whitehead problem is used for comparing attaching maps of edge groups in vertex groups in certain
graphs of groups. Typically, if one is  given a graph, a group for each vertex and for each edge, and  two families of attaching maps from edge groups to vertex groups, one has  two graphs of groups; the mixed Whitehead problem helps to decide whether these two graphs of groups are isomorphic as such.

More specifically, suppose for example that  we have a graph. with two vertices $v,w$ and two edges $e_1, e_2$ from $w$ to $v$. Assume that the group of $w$ is a given group $H$, and the edge groups are $H_1, H_2$ with given attaching maps to $H$. Let $G$ be the group of $v$. We need attaching maps $H_i\to G$. Consider  two pairs of monomorphisms $\alpha_1,\alpha_2:H_1 \to G$ and $\beta_1,\beta_2: H_2 \to G$. The choices $(\alpha_1, \beta_1)$ and $(\alpha_2, \beta_2)$ define two graphs of groups. In order to
decide whether they
are (globally) isomorphic,
we want to decide whether there exists an automorphism $\sigma \in \aut G$ such that $\alpha_i$ is conjugate in $G$ to $\sigma\circ\beta_i$, for $i=1,2$. This is the mixed Whitehead problem over $\aut{G}$ for the tuples that are images of a choice of generating tuples in $H_1$ and $H_2$.

In the refinement <cit.> that is designed to study the conjugacy problem in $\out{F_n}$, the vertex and edge groups have a fiber and an orientation. Typically, the group $G$ that appears there is isomorphic to $\torus \alpha$ for $\alpha$ a polynomially growing automorphism of a free group.  In this particular context we need to solve the mixed Whitehead problem over the subgroup of $\out{G}$ that preserves the fiber and the orientation.

The goal of this section it to prove the following:

If $\torus \alpha= F\rtimes \bbZ$  is a piecewise trivial suspension over a free group $F$, then the mixed Whitehead problem for $\torus \alpha$ under  $\autfo {\torus \alpha}$ is decidable.

Given $\torus\alpha$, by Proposition <ref>, we can compute its structural tree to get $\torus\alpha = \pi_1(\bbX,b)$ and express any $g \in \torus\alpha$ as some word
\[
g = g_1\, e_1 \, g_2\, e_2\, \cdots \, e_n\, g_{n+1}
\]
where the $g_i$ are elements of the vertex groups that are isomorphic to $F_n\oplus \bbZ$. In this sense, elements of $\torus\alpha$ can be thought of as tuples of elements of the “simpler” vertex groups. Unfortunately this approach is too naive.

In Subsection <ref> we present normal form conventions that enable us to “coordinatize” elements $g\in \torus\alpha$, or elements of one-ended subgroups of $\torus\alpha$, using a tuple $DC(g,e)$ of double cosets, a tuple of integers $\mathrm{pow}(g,e)$ of powers of generators of cyclic groups, and some power $t^k$ of the stable letter. These normal forms rely on a basepoint $b$ of $\bbX$, that defines $\pi_1(\bbX,b)$, and on some edge $e$ called a polarizing edge, whose importance will only become fully apparent in Subsection <ref>.

In subsection <ref> we introduce short positions, which are a strengthening of cyclically reduced conjugates. Although the concept of cyclically reduced is well-understood in free groups, or simple graphs of groups such as amalgamated products or HNN extensions, the concept of cyclically reduced in $\pi_1(\bbX,b)$ is not satisfactory when the axis of translation of a hyperbolic element in the dual Bass-Serre tree doesn't contain a lift of the base point $b$. This leads us to “changing basepoints”, i.e. to consider $\pi_1(\bbX,v)$ instead of $\pi_1(\bbX,b)$, where both $b,v \in \verts X$. This is acheived by noting that
\[
\pi_1(\bbX,v),\pi_1(\bbX,b) \leq \Bass(\bbX)
\]
are conjugate subgroups. By exploiting 4-acylindricity of the canonical trees for $\torus\alpha$ and its one-ended subgroups, we can show that hyperbolic elements have a finite number of distinguished conjugates, called conjugates in short position, and that these can be computed. On the one hand, this result covers the conjugacy problem for hyperbolic elements in one-ended subgroups of $\torus\alpha$. On the other hand, short positions play another important tole. Given two tuples of tuples $\vec S = (S_1,\ldots,S_k)$ and $\vec T = (T_1,\ldots,T_k)$, the mixed Whitehead problem is actually an orbit problem for $\autfo{\torus\alpha}\times(\torus\alpha^k)$ as we need to find not only $\sigma \in \autfo{\torus\alpha}$ but also conjugators $g_1,\ldots,g_k$ such that $g_i\sigma(S_i)g_i^{-1}=T_i$ for $i=1,\ldots,k$. Short positions will play a role in restricing the conjugators we need to consider.

In general for a free group $F$ there is no reasonable way in which $\aut F$ will act on a double coset space $H\backslash F /K$ and no known algorithms that decide if there is an automorphism that sends a double coset to some target double coset. In Section <ref> we associate a pair of subgroups to the double cosets that occur in $DC(g,e)$. The reason for doing so is that there is an algorithm due to Gersten (see Theorem <ref>) that can decide if there is an automorphism of a free group that send a subgroup of a free group to another subgroup. We then introduce linkage configurations with is a way of collecting all the linkages from a sequence $DC(g,e)$ (as well as their duals) that will be used later on to decide if it is possible to bring all the double cosets, in the right order, arising from words in the tuples in $\vec S$ to corresponding cosets arising from the content of $\vec T$.

In Section <ref> we describe slight modifications to the tuples in $\vec S$ and $\vec T$ that will make them easier to work with. These amount to ensuring that the first entry of a tuple is hyperbolic, if possible, and conjugating in $\Bass(\bbX)$ so that the first entry is also in centered short position.

In Section <ref> we verify that a special kind of action of $\delta_1\autfo\bbX$ on tuples of tuples behaves well with respect to choices of normal forms and other conventions. In particular we show that a variation of Gersten's algorithm: the mixed Whitehead problem for subgroups of free groups (see Theorem <ref>) can be used to simultaneously send all double cosets that occur in $\vec S$ to the double cosets that occur in $\vec T$.

In Section <ref> we finally show, through a series of reductions, how to solve the fiber and orientation preserving mixed Whitehead problem in $\torus\alpha$ by using all the material computations developed up to that point. Finally in Section <ref> we give the proof of Theorem <ref>, which is substantial and was delayed so as not to break the flow of our arguments.

§.§ Describing elements

§.§.§ Normal forms

For this subsection we will exceptionally consider $G$ to either be a piecewise trivial suspension or a finitely generated one-ended subgroup of a piecewise trivial suspension. We have a  canonical graph of groups $\bbX$ and for some $b \in \verts X$ we identify $G = \pi_1(\bbX,b)$, where $b$ is chosen to be a white vertex, or equivalently, that $\bbX_b$ is non-abelian. We also fix a breadth first search (BFS) spanning tree $\tau \subset X$ based at $b$, this means that for any $v \in \verts X$, $\tau$ contains a shortest path from $b$ to $v$.

Consider a word in the generators of the Bass group representing an element in $\pi_1({\bbX},b)$:

\begin{equation}\label{eqn:bass-grp-elt}
w= g_1\, e_1 \, g_2\, e_2\, \cdots \, e_n\, g_{n+1} \in \Bass(\bbX)
\end{equation}

with $g_j \in \bbX_{\tau(e_{j-1})}$ if $j>1$ and  $g_j \in \bbX_{i(e_{j})}$ if $j\leq n$. We start by giving vocabulary to describe a few characteristics of $w$ and the element it defines. Its underlying $X$-path (in $X$) is the path $(e_1, \dots, e_n)$, from $b$ to $b$. The word $w$ is reduced if its $X$-path has minimal length among all words representing the same element. Its syllable length is the number of edges that appear in the $X$-path for any reduced word.

Even among reduced words, the choice of elements $g_i$ that appear in (<ref>) are not unique. A normal form is a function that assigns to every element of $g\in G$ of syllable length $n$ a tuple $(g_1,\ldots,g_{n+1})$ of elements lying in the appropriate vertex groups, i.e. it is a function that assigns to every $g \in G$ a specific representative word.

The vertex groups of $\bbX$ are either isomorphic to $F_v,F_v\oplus\bk{t_v},\bbZ\oplus \bbZ,$ or $\bbZ$ where $F_v$ is a free group of rank $n_v$. A choice of ordered basis for the $F_v$ induces the  well-order $\leq_v$ on $F_v$. If $\bbX_v \simeq F_v\oplus\bk{t_v}$  then we write $(w,t_v^n) < (u,t_v^m)$ if and only if either $|n|<|m|$ or, if $|n|=|m|$ then $|m|/m < |n|/$, or if $n=m$ then $w <_v u$. In this manner we have a well-order on each non-ablelian vertex group.

For all edges $e$ with $\tau(e)= v$, we denote $I_e = \tau_e(\bbX_{e})\leq \bbX_v$. Similarily, if $v = i_e(e)$, we denote by $O_e = i_e(\bbX_{e}) \leq \bbX_v$. Note that $O_e=I_{\bar e}$. A pair of edges $(e,e')$ such that $\tau(e)=i(e')$ is called a turn. An element represented by a word $w$ as in (<ref>) is an element of $\pi_1(\bbX,v)$ if and only if $i(e_1)=b$ and each $(e_i,e_{i+1})$ is a turn where indices $i,i+1$ are taken are modulo $\bbZ/n\bbZ$. The double coset space associated to the turn $(e,e')$ is $I_e\backslash\bbX_v/O_{e'}$ and we define
\[
DCR(e,e') = \{\bar g \in \bbX_v : \bar g \textrm{ is minimal w.r.t $<$ in its $I_e\backslash\bbX_v/O_{e'}$ double coset}\},
\]
to be the set of double coset representatives for the turn $(e,e').$

We will now define normal forms. First we note that $\bbX$ is will always have an underlying bipartite graph with black and white vertices. Furthermore if $v$ is a black vertex then $\bbX_v$ will be ableian (either isomorphic to $\bbZ$ or $\bbZ^2$) and it will coincide with the images of all incident edge groups. In particular we can always use the Bass group relations to rewrite $w$ as in (<ref>) so that $g_{2j}=1$ for all $1\leq j \leq n/2$.

When writing elements of $\pi_1(\bbX,b)$ as in (<ref>), we will always ensure that $b$ is a white vertex with $\bbX_b$ non-abelian and we will ensure that $g_i$ that lie in abelian vertex groups are trivial.

Given a word $w$ as in (<ref>), due to not being “sandwiched” between two letters from $\edges X$, there is some ambiguity in the choice of double coset space for the elements $g_1,g_{n+1}$. We remedy this by picking an edge $e \in \edges X$ be such that $i(e)=b$. Let $g \in \pi_1(\bbX,b)$ be written as a reduced word as in (<ref>) then the tuple of double cosets for $g$ polarized by $e$ is the tuple
\[
DC(g,e)=(I_{\bar e}g_1O_{e_1},1,I_{e_2}g_3O_{e_3},1,\ldots,I_{e_n}g_{n+1}O_{e}),
\]
in particular we take the first and last cosets to lie in the double coset spaces associated to the turns $(\bar e,e_1)$ and $(e_n,e)$. This choice of $e$ will become important later on.

We also have the corresponding sequence of double coset representatives for $g$ polarized by $e$.

\[
DCR(g,e) = (\bar f_1, 1, \bar f_3 ,\ldots,\bar f_{n+1}).
\]

We note that, as indicated by the notation, $DCR(g,e)$ and $DC(g,e)$ depend only on $g \in \pi_1(\bbX,b)$ and not on the choice of word used to represent $g$.
Let $t_v$ be a generator of the (possibly trivial) center of $\bbX_v$ for every non-abelian $\bbX_v$ if $G$ is a one-ended subgroup of a piecewise trivial suspension by Proposition <ref> item <ref>, then $t_v$ lies in $O_{e}$ for all $e$ such that $i(e)=v$. It follows that the for any $g \in \pi_1(\bbX,b)$ that can be expressed as $w$ as in <ref> the word
\begin{equation}\label{eq:normalform}
\bar{w}=c_{\bar e}^{d_0}\bar f_1 e_1e_2 c_{e_2}^{d_2}\bar f_3 \cdots e_nc_{e_n}^{d_n} \bar f_{n+1} c_{\bar e}^{d_{n+1}} t_b^k
\end{equation}
representing $g$, where $\bar f_i$ is the $i$-th entry in $DCR(g,e)$ and $c_f$ is the $<$-minimal generator of $I_f\cap F_{\tau(f)}$ where $f \in \edges X$, is fully defined.

The word $\bar w$ given in (<ref>) is called the normal form for $g \in \pi_1(\bbX,b)$ polarized by $e$ the tuple of exponents
\[
\mathrm{pow}(g,e)=(d_0,d_2,\ldots,d_n,d_{n+1},k)
\]
is called the power vector and the exponent $k$ is called the abscissa, where we set $k=0$ if $t_b=1$. In summary.

Given $g\in \pi_1(\bbX,b)$ and some $e \in \edges X$ such that $i(e)=b$ the $X$-path underlying $g$, the  tuples $DCR(g,e)$ and $\mathrm{pow}(g,e)$, and the abscissa of $g$ are well-defined.

§.§.§ Short positions

We say that $g \in \pi_1(\bbX,b)$ is cyclically reduced if it has minimal syllable length among all its conjugates in $\pi_1(\bbX,b)$. For graphs of groups that are more complicated than amalgamated products or HNN extensions, it may be that $g$ is cyclically reduced, but its syllable length exceeds the translation length of the action of $g$ on the dual Bass-Serre Tree. By our convention that $\tau$ is a BFS-tree we have that $g$ has a family of cyclically reduced conjugates of the form
\[
E g_v \bar E
\]
where $E$ is a path from $b$ to some white vertex $v$ in $\tau$ and $g_v\in \pi_1(\bbX,v) \leq \Bass(\bbX)$. Furthermore the syllable length of $g_v$ coincides with the translation length of $g$. We say that $g_v$ is a recentering of $g$ at $v$. We note that the axis of translation of $g$ in the Bass-Serre tree must contain a lift of $v$.

We assume that $g \in \pi_1(\bbX,b)$ is a hyperbolic element and therefore that any recentering $g_v$ is also hyperbolic. We will switch the basepoint to $v$ and use the notation developed in Section <ref> in this new context.

We say that $h \in \pi_1(\bbX,v)$ is centered $e_1e_2$-prefix-short if it is cyclically reduced, has syllable length equal to its translation length, and can be written in normal form

\[
h = e_1e_2 c_{e_2}\bar f_2 \cdots.
\]
It is obvious that any hyperbolic element recentered at $v$ is conjugate in $\pi_1(\bbX,v)$ to an element in prefix-short form. Two prefix-short elements
\[
e_1e_2 c_{e_2}^{d_2}\bar f_2 \cdots, e_1e_2 c_{e_2}^{d'_2}\bar f_2' \cdots
\]
are elliptically-conjugate if they are conjugate by an element of $O_{e_1}\leq \pi_1(\bbX,v)$ and we say they lie in the same elliptic-class.

We say that $h\in\pi_1(\bbX,b)$ is $e_1e_2$-prefix-short if there exists a path $E\subset \tau$ from $b$ to $v$ such that
\[
h = Eg_v\bar E
\]
and $g_v$ is centered $e_1e_2$prefix-short. It is clear that every hyperbolic  $g\in\pi_1(\bbX,b)$ has at least one prefix-short conjugate.

If $h \in \pi_1(\bbX,v)$ is centered $e_1e_2$-prefix-short, we say it is in centered short position if its $e_1$-polarized normal form is

* $h = e_1e_2\bar c_{e_2}^{d_2} f_2c_{\bar e_1}^{d}t_v^k$, with $d_2=0$ and $d$ minimal (w.r.t some fixed well-order on $\bbZ$) among all other conjugates of $h$ that are in $e_1e_2$-prefix-short position with $d_2=0$, if $h$ has translation length 2

* $h = e_1e_2c_{e_2}^{d_2}\bar f_2e_3e_4c_{e_4}^{d}\bar f_4 \cdots$,  with $d_2=0$ and $d$ minimal (w.r.t some fixed well-order on $\bbZ$) among all other conjugates of $h$ that are in $e_1e_2$-prefix-short position with $d_2=0$, if $h$ has translation length 4 or more.

Although they are not explicitly invoked in the definition, the prefix $e_1e_2$ as well as the basepoint $v$ are completely specified. To show that this is canonical we have the following:

The exponent $d$ given in the the definition of centered short position determines the first 6 edges of the segment $[\tilde v,h\cdot \tilde v]$ of the axis of $h$ for the action on the Bass-Serre tree dual to $\pi_1(\bbX,v)$.

First consider the case where $h$ has translation length 2. Then the axis of $h$ is the same as the axis of $h^3$, passing to $e_1$-polarized normal forms we have
\[
h^3= e_1e_2\bar f_2 e_1e_2c_e^{d'}\bar f_2 e_1e_2 c_{e_2}^{d''} \bar f_2 t_v^{3k},
\]
where ${c_{e_2}}^{d'}$ is obtained by migrating $c_{\bar e_1}^{d}$ accross $e_1e_2$, and it is clear that the exponent $d'$ determines the first 6 edges of the path $[\tilde v,h^4\tilde v]$ and therefore of the axis of $h$.
Similarly, if $h$ has translation length 4 or more we can take $h^2$ and pass to $e_1$-polarized normal form
\[
h^2 = e_1e_2\bar f_2e_3e_4c_{e_4}^{d}\bar f_4 e_5e_6 c_{e_6}^{d_6} \bar f_6 \cdots,
\]
and again it is apparent that the first 6 edges of the path $[\tilde v,h^4\tilde v]$ and therefore of the axis of $h$ are determined by the exponent $d$.

Let $g \in \pi_1(\bbX,v)$ be a hyperbolic element whose syllable length coincides with its translation length. Then there is a unique element of $\bbX_v\leq \pi_1(\bbX,v)$ that conjugates $g$ to centered short postion.

In $e_1$-polzarized normal form we have $g=c_{\bar e_1}^{d_0}\bar f_1e_1e_2{c_{e_2}}^{d_2}\bar f_2 \cdots$ conjugating by $f_1 \in \bbX_V$ and then by the element of $a\in O_{e_1} \leq \bbX_v$ such that $a e_1e_2 = e_1e_2 {c_{e_2}}^{-d_2}$ gives us a normal form
\[
g_1=(a^{-1}\bar f_1^{-1} c_{\bar e_1}^{-d_0})g (c_{\bar e_1}^{d_0}\bar f_1 a) = e_1e_2 \bar f_2' \cdots
\]
whose "$f_1$-syllable" and $"d_2"$-exponent are trivial. We further note that any conjugation by an element of $\bbX_v \setminus O_{e_1}$ will undo this condition.

Now there is a subgroup $Z_{e_1}\leq O_{e_1}$ such that $ze_1e_2 = e_1e_2 z'$ and $z'\bar f_2' = \bar f_2' z'$, which is either trivial or cyclic, that can affect the exponent $d$ given in the definition of centered short position while keeping the exponent $d_2=0$. I.e. $Z_{e_1}$ is a group of element that fix an arc of length 4 in the Bass-Serre tree.

Let $k \in Z_{e_1}$ be the conjugator that gives the minimal exponent $d$. We have that $p=kc_{\bar e_1}^{d_0}\bar f_1 a$ is a conjugator that brings $g$ to centered short position. Note that the initial conjugator $c_{\bar e_1}^{d_0}\bar f_1 a$ is well defined up to left multiplication by some element $z \in Z_{e_1}$. It follows that in all cases, the double coset representative $\bar f_2'$ is common to all possible centered short positions.

To see that it is unique, suppose there was another $p'$ such that $(p')^{-1} g p'$ was in centered short position. Then
\[
p^{-1}p' (e_1e_2\bar f_2' *\cdots) (p')^{-1}p^{-1} = e_1e_2 f_2' *'\cdots,
\]
where, both $h=e_1e_2 f_2' *$ and $h'e_1e_2 \bar f_2' *'$ are in centered short position with the same minimal exponent $d$. Now note that $\mathrm{axis}(h') = (p^{-1}p')\cdot \mathrm{axis}(h)$ and so by Lemma <ref> $(p^{-1}p')$ fixes a segment of length 6, which by 4-acylindricity implies that $p'=p$. This completes the proof.

Finally we say that a hyperbolic $g \in \pi_1(\bbX,b)$ is in short position if
\[
g = E g_v \bar E
\]
where $E$ is a path in $\tau$ from $b$ to $v$ and $g_v$ is in centered short position. We call the vertex $v \in \verts X$ the anchor vertex of the short position and the first edge $e_1$ of $g_v$ the polarizing edge of the short position. Thus, given some $g \in \pi_1(\bbX,b)$, by going through the $\bk{g}$-orbits of the white vertices of $\mathrm{axis}(g)$ and applying the corollary above gives:

Let $G=\pi_1(\bbX,v)$ be a one-ended subgroup of a piecewise trivial suspension. Let $g\in \pi_1(\bbX,b)$ be hyperbolic with translation length $n$ then its conjugacy class contains at most $n/2$ elements in short position and the normal forms, anchor vertices and polarizing edges, of these elements can be computed.

§.§ Tuples of cosets and linkage configurations in piecewise trivial suspensions

We now return our focus to a piecewise trivial suspension $\torus\alpha = F \semidirect \alpha \bk t = \pi_1(\bbX,b)$. In the the notation of subsection <ref> we will assume every white vertex group is decomposed as $\bbX_v = F_v \oplus \bk{t_v}$ where $F_v = F \cap \bbX_v$ (which is well-defined since $F \triangleleft \torus\alpha)$), thus elements in the fibre will always be smaller with respect to $<$ than other elements. In particular if we write
\[
g = a_1\bar f_1 b_1 e_1e_2 a_3 \bar f_3 b_3 \cdots e_n a_{n+1}\bar f_{n+1} b_{n+1}
\]
where $\bar f_i$ is the $i$th entry in $DCR(g,e)$ for some $e$ with $i(e)=b$, then the representation of this form that minimizes the tuple $(a_1,b_1,\ldots,a_{n+1},b_{n+1})$ is precisely the normal form polarized by $e$. When it is not necessary to see the exponents in the power vector, we will call an expression
\[
g = f_1e_1e_2 f_3 \cdots e_n f_{n+1}t^k
\]
in reduced fiber and abscissa form provided $g_f=f_1e_1e_2 f_3 \cdots e_n f_{n+1} \in \pi_1(\bbX,b)\cap F$ is a reduced word. This initial subword $g_f$ is called the fiber part and is well-defined by our normal form conventions. We record some more observations.

The fiber part $g_f$ of $g \in \torus\alpha$ is well-defined. Furthermore if $g,g' \in \torus\alpha$ and $g_f=g'_f$ then
\[
DC(g,e)=DC(g',e) \textrm{~and~} pow(g,e)=pow(g',e)
\]
for all $e$ with $i(e)=v$.

We wish to describe how automorphisms act on the double cosets that appear in the sequences $DC(g,e)$. Even in a  free group, we shouldn't expect automorphisms to act in any sensible way a double coset space. That said, it will turns out that the constraints of the Bass diagram will lead to a sensible action on the double coset spaces we are interested in.

We will also develop an algorithmic theory to compute orbits of our double cosets. Our approach is to reduce the double coset orbit problems to something related to orbit problems of finitely generates subgroups of free groups (see Theorem <ref>.) This next subsection establishes the dictionary bewtween double cosets and subgroups of free groups.

§.§.§ Linkages of double cosets

Turns were defined in Subsection <ref>. we now define the entrance of a turn, and  the linkage of a double coset at a given turn. Before continuing we will make a slight modification to our notation.

[Double cosets for elements of $\torus\alpha$]
For the rest of Section <ref> we will assume that the double cosets that appear in $DC(g,e)$ are actually double cosets in the fibre part $F_v = \bbX_v\cap F$. In particular if we write $I_e\bar f O_{e'}$ then $I_e = \bk{c_e}$ and $O_{e'}=\bk{c_{\bar e'}}$, where $c_e,c_{\bar e'} \in F_v$ are, as usual, generators of the images of the corresponing incident edge groups.

We note that by Lemma <ref> and the fact that our ordering convention forces double coset representatives to lie in $F_v$ considering double cosets to lie in the fibre part of the vertex groups causes no loss of information.

Whenever $f \in F_v$, and $(e, e')$ is a turn at $v$, the entrance of the turn is the element $c_e$ (it generates $I_e <\bbX_v$). We define the  linkage $\link{e, f, e'}$ and the dual linkage $(\mathscr{l}_*)_{e, f, e'}$ to be the following  subgroups of $ \bbF_v$:

\[ \begin{array}{cclcl} \link{e, f, e'} &  = &   \langle I_e,  f O_{e'} f^{-1} \rangle & &  \\ (\mathscr{l}_*)_{e, f, e'} & =  & \mathscr{l}_{\bar e', f^{-1}, \bar e}   & = &   \langle O_{e'},  f^{-1} I_{e} f \rangle  \end{array}   \]

If the double coset appears in the reduced form of an element $g$ in the fibre, the dual linkage is the linkage of a coset appearing in the reduced form of $g^{-1}$.

Double cosets determine linkages, as stated in the following Lemma, which  is immediate.

If $f$ and $f'$ are in the same double coset
$I_e x O_{e'}$ then   $\link{e, f, e'}=\link{e, f', e'}$.

In particular, if $f$ is in the fibre of $G$, all of the reduced words representing it share the same sequence of edges, of entrances, and of linkages.

However, in principle, different elements $f$ can lead to the same linkage, while being in different double cosets.
It is thus  worth warning that a given linkage can have different duals if it can be defined by elements in different double cosets.

We propose a converse to Lemma <ref>, in which double cosets are characterised by a pair of linkages that are dual to one another.

Consider a pair of linkages $\mathscr{l} = \mathscr{l}_{e,f,e'}$ and  $\mathscr{l}'= \mathscr{l}_{e,h,e'}$ and a   dual pair $\mathscr{l}_* =  \mathscr{l}_{\bar e', f^{-1}, \bar e}$, and $\mathscr{l}_*'=  \mathscr{l}_{\bar e', h^{-1}, \bar e} $.

If one has equality of pairs
\[( \mathscr{l}, \mathscr{l}_*   ) = (\mathscr{l}', \mathscr{l}_*') \]

then the double cosets $I_e f O_{e'}$ and $I_e h O_{e'}$ are equal.

The result will the follow from this statement.

Let $\tau(e_-)= i(e_+) =v$ and, to simplify notation, let $\bk{c_{e_{-}}} = I_{e_{-}}$ and $\bk{c_{e_{+}}} = O_{e_+}.$

If $h, h' \in \bbF_v$ are such that
\[\langle c_{e_-},\, h' c_{e_+} h'^{-1}  \rangle \, = \, \langle c_{e_{-}},\, h c_{e_+} h^{-1}  \rangle,  \; \hbox{ and } \; \langle c_{e_+},\, h'^{-1} c_{e_-} h'  \rangle \, = \, \langle c_{e_{+}},\, h^{-1} c_{e_-} h  \rangle      \]

then  $h\in  \langle c_{e_{-}}\rangle   h'    \langle c_{e_{+}}\rangle$.

Start  with the equality $\langle c_{e_-},\, h' c_{e_+} h'^{-1}  \rangle \; = \; \langle c_{e_{-}},\, h c_{e_+} h^{-1}  \rangle$.

These two groups are subgroups of $\bbF_{v_i}$, hence free.

If they have rank one, then  by maximality of the edge groups, $h'c_{e_+}h'^{-1} = c_{e_{-}}^{\pm 1}= (h c_{e_+} h^{-1})^{\pm 1}$. It follows  that $h^{-1}h'$  centralises $c_{e_+}$ (it cannot  conjugate it to its inverse). Therefore it is in $O_{e_+}$.

If they are rank two, one has that
\[  h c_{e_+} h^{-1} \in I_{e_{-}}\, h' c_{e_+} h'^{-1} \, I_{e_{-}}.  \]

Let us write  $ h c_{e_+} h^{-1} \in I_{e_{-}}\, h' c_{e_+} h'^{-1} \,c_{e_{-}}^{-r} $. Let $h'' =c_{e_{-}}^{r} h' $. We have that  $ h c_{e_+} h^{-1} \in I_{e_{-}}\, h'' c_{e_+} h''^{-1}$ and also that $\langle c_{e_{-}},\, h'' c_{e_+} h''^{-1}  \rangle \; = \; \langle c_{e_{-}},\, h c_{e_+} h^{-1} \rangle $, and we still want to show that $h\in  I_{e_{-}}   h''    O_{e_+}$.

Let us write that, for some integer $k$,  $ h c_{e_+} h^{-1} = c_{e_{-}}^k\, h'' c_{e_+} h''^{-1}$:

\[  c_{e_{-}}^k =  h c_{e_+}\; h^{-1}h'' \; c_{e_+}^{-1} \; h''^{-1},  \]

\[ c_{e_{-}}^k =   ( [ h''^{-1}h, \; c_{e_+}])^{h''^{-1}}.\]

In a free group, a non-trivial commutator is not a proper power
<cit.>, <cit.>, <cit.>,
hence $|k|\leq 1$.

If $k=0$, then $h''^{-1} h$ commutes with $c_{e_{+}}$ hence is in $O_{e_{+}}$, which is what we wanted to show.

If $|k|= 1$, then $c_{e_{-}}$ is conjugate to a commutator of an certain element with $c_{e_+}$. This is a property of the turn  $(e_{-}, e_+)$ and in this case we say that $(e_{-}, e_+)$ is a dangerous turn.

We claim that in this case, $(\bar e_+, \bar e_{-})$ (which is also a turn at the same vertex) is not dangerous. Indeed, if it was dangerous too, it would mean that $c_{e_+}$ is conjugate to a commutator of an element and $c_{e_{-}}$ too. To get the contradiction, it suffices to prove the following lemma.

In a free group, if $a$ is conjugate to $[b,c]$ and $b$ is conjugate to $[a,d]$, then $a=b=1$.

Iwasawa, and Magnus proved  that free group are residually nilpotent, meaning that any element survives in a nilpotent quotient (see <cit.>.
Any such a quotient satisfies the law that all iterated commutators $[[\dots[ \cdot, \cdot ], \cdot ], \cdot \dots ]$ of certain depth must vanish. However $a$ and $b$ can be written as commutators of arbitrary depth, by iterative substitution.

Now that we know that the turn $(\bar e_+, \bar e_{-})$ is not dangerous, we may apply  our analysis above  on the dual configuration to get that $h^{-1}\in O_{e_+}(h'_i)^{-1} I_{e_{-}}$, which is equivalent to what we wanted to show.

§.§.§ The linkage configuration at a vertex induced by a path and a sequence of double cosets

Given a loop  $(e_1, \dots e_n)$ based at $v \in \verts X$ and a sequence of double cosets over this loop
\[( I_{\bar e_0}f_1 O_{e_1}, 1 ,I_{e_2}f_3O_{e_3}, \dots, 1 ,I_{e_n}f_{n+1} O_{e_0}),\]
where $e_0$ is some polarizing edge, we can construct the associated linkage tuple
\[\vec{\link{}}=(\link{1}, \dots \link{n+1}) = (\link{\bar e_0,f_1,e_1},1,\ldots,\link{e_n, f_{n+1}, e_0}).\]

We reverse this path to get $\bar e_n,\ldots,\bar e_1$ and the corresponding dual coset tuple
\begin{multline*}
(O_{e_0}f_{n+1}^{-1}I_{e_n}, 1 ,\ldots , O_{e_3}f_3^{-1}I_{e_2},1,O_{e_1}f_1^{-1}I_{\bar e_0})=\\
(I_{\bar e_0}f_{n+1}^{-1}O_{\bar e_n},1,
\ldots,I_{\bar e_3} f_3^{-1} O_{\bar e_2},1,
I_{\bar e_1} f_1^{-1} O_{e_0})
\end{multline*}

and the corresponding dual linkage tuple that works out to
\[
\vec{\link{}} = ((\link *)_{n+1},\ldots,(\link *)_1),
\]
i.e. reading $\vec{\link{}}$ and $\vec{\link *}$ in opposite directions we get pairs of dual linkages of the double cosets $I_{e_{j-1}}f_j O_{e_j}.$ We note that the if a sequence of double cosets came from $DC(g,e)$ then the dual sequence would come from $DC(g^{-1},e).$  By Lemma <ref> and Proposition <ref>, given the underlying loop and polarizing edge, the dual pair $(\vec{\link{}},\vec{\link *})$ fully determines the tuple of double cosets and vice-versa.

Consider the two pairs
\[
(\bar e_0,e_1,\ldots,e_n,e_{n+1}), (\link{1}, \dots \link{n+1}) \textrm{~and~} (\bar e_{n+1},\bar e_n,\ldots,\bar e_1, e_0), ((\link{*})_{n+1}, \dots (\link{*})_1)
\]
with common indices $1\leq i\leq n+1$, where $e_0$ is the polarizing edge and $e_{n+1}=e_0$. Consider $v$ a vertex in $X$, and let $J_v \subset \{1, \dots, n\}$ be the set of indices $j\leq n$ such that $\tau(e_j) = v$, and $J^*_v$ the set of indices for which $\tau(\bar e_j) = v$. For each oriented edge $e$ in $X$, $J_{v, e}$  is the subset of $J_v$ for which $e_j= e$ and, similarily, ${J^*}_{v,e} = \{ j \in {J^*}_v : \bar e_j=e\}$.

For each  $J_{v,e}$ (possibly empty), one associates the following $(|J_{v,e}|)$-tuple $\calP_{v,e} = (\link{{j+1}} : j\in J_{v, e})$, where the $\link{j+i}$ are entries from $\vec{\link{}}$. We note that $\calP_{v,e}$ consists of entries from $\vec{\link{}}$ of the form $\link{e,f,e'}$, where $f,e'$ are arbitrary. Similarly, we define $\calP^*_{v,e} = ((\link{*})_{j}: j\in J^{*}_{v,e})$, where the $(\link{*})_{j+i}$ are entries from $\vec{\link{*}}$. We note that entries of $\calP^*_{v,e}$ consists of linkages of the form $\link{e ,f,e'}$ where $f,e'$ are arbitrary.

The triple $\calQ_{v,e}(g,e_0) =  (c_e, \calP_{v,e},  \calP^*_{v,e})$  is the linkage configuration of the $e_0$-polarized element $g$ at $v$ for $e$. The following will be useful to remember in the proof of Proposition <ref>.

Every entry $\link{e,f,e'}$ in $\vec{\link{}}$ and $\vec{\link{*}}$ that is associated to a turn $(e,e')$ at $v$ is in $\calQ_{v,e}$.

Note that the order of appearance of each linkage is part of the data of $\calQ_{v,e}(g,e_0)$, i.e. $\calQ_{v,e}(g,e_0)$ is not just a set of linkages.

Ordering the edges of $X$,  one thus obtains, from a linkage tuple, and for each $v$,  a tuple $\calQ_v(g,e)$ of conjugacy classes of linkage configurations at $v$: $\calQ_v(g,e_0)$ is the tuple of the conjugacy classes of the tuple  $\calQ_{v,e}(g,e_0)$, $e$ ranging over the edges of $X$ terminating at $v$, in the chosen order.  We call it the total linkage configuration at $v$ for the given sequence of double cosets.

§.§ Tuples of tuples and associated data

§.§.§ Elliptic, lineal and hyperbolic tuples, and their enrichments

We consider a tuple of $r-2$ elements $S=(g_2, \dots, g_r)$ of $\torus\alpha$ (we start at index $2$ on purpose).

The tuple is said elliptic if there exists $\tilde v \in T$ that is fixed by all $g_i$. It is said small elliptic if $\tilde v \in \tilde \tau$. Define its enriched tuple $S^+ = (g_0, g_1, g_2, \dots, g_r)$ by setting $g_0=g_1=g_2$.

If $S$ is not elliptic, either there exists $i$ a smallest index such that $g_i$ is not elliptic, or  all $g_i$ are elliptic and there exists $(i,j)$ a smallest pair  in lexicographical order so that $g_i$ and $g_j$ do not fix the same vertex (there exists such a pair because pairwise intersecting convex sets in trees have global intersection). Let $g_0=g_i$ in the first case and $g_0=g_ig_j$ in the second case. It is a hyperbolic element.

Again there are two cases: either all elements of $S$ commute with $g_0$ or one of them does not.

In the first case, we say that the tuple is lineal and we set its  enriched tuple $S^+ = (g_0, g_1, g_2, \dots, g_r)$ by setting $g_1=g_0$.

In the second case, we say that the tuple is hyperbolic, and  we set its  enriched tuple $S^+ = (g_0, g_1, g_2, \dots, g_r)$ by setting $g_1=g_0^{g_i}$ where $i$ is the first index such that $g_i$ does not commute with $g_0$.

§.§.§ Small tuples

An enriched tuple  $(g_0, g_1, g_2, \dots, g_r)$ is small if:

* if it is elliptic:  the elements have a common  fixed point  is in $\tilde \tau$.

* if it is lineal: $g_0$ is cyclically reduced in short position.

* if it is hyperbolic: $g_0$ is cyclically reduced in short position, and $g_1$ has minimal syllable length among its conjugates by powers of $g_0$.

In the first case, there exists a simple path $(e_0e_1 \dots e_k)$ in $\tau$ starting at $b_0$,  such that for each $i$, there exists $h_i \in \bbX_{\tau(e_k)}$ for which
\[g_i \, =\, (e_0e_1\dots e_k) h_i (\bar e_k \bar e_{k-1}\dots  \bar e_0).\]

In the second case,  $g_0$ (hence the tuple)  preserves a line $L$ in $T$ that intersects $\tau$. Let $\tilde v_0$ in this line closest to $\tilde b$, and $v_0$ its image in $X$.

The element $g_0$ can thus be expressed as   $(e_0 e_1\dots e_k) h_0 (\bar e_k \bar e_{k-1}\dots  \bar e_0)$ for  $(e_0e_1 \dots e_k)$ a simple path  in $\tau$ from $b$ to $ v_0$, and $h \in \pi_1(\bbX,  v_0)$ is in centered short position and $v_0$ is the anchor vertex of the short position.

From Proposition <ref>,  we easily obtain:

Given a tuple, it is decidable whether it is an elliptic, lineal or hyperbolic tuple, and a small conjugate of the enriched  tuple is computable. If it is not elliptic a finite list of all small conjugates of the enriched tuple is computable.

§.§.§ Centered non-elliptic tuples

Given a small tuple $S$ of elements in $\pi_1(\bbX,b)$, we define its central vertex $v_S \in \verts X$ as follows. If the leading entry $g_0$ is elliptic then every entry in $S$ is conjugate in $\Bass(\bbX)$ into some $\bbX_{v_T}$, so $v_T$ is the central vertex. Otherwise if $S$ is lineal or hyperbolic, recalling the terminology of Subsection <ref>, we take $v_S$ to be the anchor of the short position of the leading entry $g_0$. If $S$ is lineal or hyperbolic we further define the polarizing edge $e_S \in \edges X$ to be the  polarizing edge of the short position of the leading entry $g_0$.

Now given a small tuple $S$ of elements in $\pi_1(\bbX,b)$ we can conjugate it in $\Bass(\bbX)$ be the element $E$ given by the path in the spanning tree $\tau$ from $b$ to $v_S$ such that $g_0 = E (g_0)_{v_S} \bar E$, where $(g_0)_{v_S}$ is in centered short position.

It follows that the conjugate $\bar E S E$ is a now a tuple of elements in $\pi_1(\bbX,v_S)$, its leading entry is in centered short position, and $e_S$ can be read off as the first symbol occuring in the leading entry. We call the conjugate of $\bar E S E$ the the re-centering $S$ and we say that $\bar E S E$ a centered tuple. Proposition <ref> immediately implies that for any tuple $S$ we can compute the complete set of all its centered tuples in $\Bass(\bbX)$.

The following result will have the immediate benefit of providing reassurance that taking conjugates outside $\pi_1(\bbX,b)$ is sensible.

Let $g,h \in \pi_1(\bbX,v)$. $g$ and $h$ are conjugate in $\pi_1(\bbX,v)$ if and only if they are conjugate in $\Bass(\bbX)$.

On the one hand we have that $\pi_1(\bbX,v)\leq \Bass(\bbX)$, on the other hand, for a spanning subtree $\tau$ of $X$, we have a commuting diagram
\[
\begin{tikzpicture}[xscale=2]
\node (B) at (0,0) {$\Bass(\bbX)$};
\node (H) at (0,-1) {$\pi_1(\bbX,v)$};
\node (Bbar) at (2,-1){$\Bass(\bbX)/_{\bk{\bk{\edges{\tau}}}}$};
\draw[->>] (B) -- (Bbar);
\path (H) -- node[sloped]{$\leq$} (B);
\draw[->] (H) --node[above]{$\sim$} (Bbar);
\end{tikzpicture}
\]
where the horizontal arrow is an isomorphism. If two elements in $\pi_1(\bbX,v)$ are conjugate in $\Bass(\bbX)$ then the image of the conjugator $\Bass(\bbX)/_{\bk{\bk{\edges{\tau}}}}$ gives a conjugator in $\pi_1(\bbX,v)$.

§.§.§ Centered elliptic tuples and variations

If $S = (g_0,\ldots,g_{r})$ is an elliptic tuple then its central vertex $v_s \in \verts X$ is the vertex such all the $g_i$ are simultaneously conjugate in $\Bass(\bbX)$ into $\bbX_{v_s}$. We say $S$ is centered if its entries are in  $\bbX_{v_s}$. If $S$ is centered and all its entries are simultaneously conjugate into the image of the same edge group, then we will require the centering of $S$ to be the a conjugate in which all entries lie in the image of some common edge group and we call the variations of a centered $S'$ to be all the tuples $(g'_0,\ldots,g'
_r)$ such that
\[
g_i' = \ell g_i \bar \ell \in \bbX_{v_s}
\]
where $\ell$ is a loop based at $v_s$ of length at most 4. (See Lemma <ref>.)

We define the linkage configuration of $S$ to be the tuple
\[\calQ(S) = (\bk{(g_0)_f},\ldots,\bk{(g_r)_f}) \in F\cap \bbX_{v_s}\]
of cyclic subgroups of free groups generated by fiber parts.

Given an elliptic tuple, it is possible to compute its centering and all its variations.

§.§ The actions of $\delta_1 \autfo \bbX$

The mixed Whitehead problem involves the action of $\delta\autfo(\bbX)$ as well as the action of $(\torus\alpha)^k$ on a tuple of tuples. We start by studying the action of $\delta\autfo{\bbX}$ on centered tuples.

§.§.§ Preliminaries

Recall that $\delta \autfo \bbX$ surjects on $\outfo \G$ and that by Corollary <ref> we can compute a complete list $\nu = \{\nu_1,\ldots, \nu_v\}$ of $\delta_1\autfo\bbX$-coset representatives. If for each each $j\in \{1, \dots, v\} $,  we define $\vec S_j = \nu_j(\vec S) = (\nu_j(S_1),\ldots,\nu_j(S_k))$, then we immediately get a first reduction, before diving into the main argument:

$\vec S$ and $\vec T$ are mixed Whitehead equivalent under $\autfo \G$  if and only if there is
$j\in \{1, \dots, v\}$
such that      $\vec S_j$ and $\vec T$ are Whitehead equivalent under $\delta_1 \autfo \bbX $.   In particular the mixed Whitehead  problem under $\autfo \G$ reduces to the mixed Whitehead problem under $\delta_1 \autfo \bbX $.

Observe that $\delta_1 \autfo \bbX$ preserves the paths (hence the syllable lengths), and the abscissa. Note that, according to our convention,  these paths are to be understood as paths in $X$, not in $T$.

If $\alpha \in \delta_1\autfo \bbX$ is seen as an homomorphism of the Bass group, then it preserves the $X$-paths and abscissa of elements in $\pi_1(\bbX,v)$ for all $v \in \verts X$. If $w$ is reduced, then $\alpha(w)$ is reduced of same syllable length. If $g$ is cyclically reduced, then $\alpha(g)$ is cyclically reduced.

Any fibre and orientation preserving automorphism induces the identity on the cyclic quotient of the suspension, hence  preserves the abscissa.

Being in $\delta_1\autfo \bbX$, $\alpha$ is of the form $\alpha = (Id_X, (\phi_v), (Id_e), (\gamma_e))$. It sends each edge $e_i$ to $\gamma_{\overline {e_i}}^{-1} e_i \gamma_{e_i} $  in the Bass group. In particular, it preserves the paths.

Also, it sends the word $g_1e_1g_2\cdots e_ng_{n+1}$ to $h_1e_1h_2e_2\cdots e_nh_{n+1}$ where  $h_i =    \gamma_{e_{i-1}}  \phi_{v_i}(g_i) \gamma_{\overline {e_{i}}}^{-1} $, if $1< i < n+1$.
In particular it  is in the same vertex groups as  $g_i$.
If the word  $h_1e_1h_2e_2\cdots e_nh_{n+1}$  fails to be reduced, there exists $i$ in $\{2, \dots,  n-1\}$ such that $e_{i+1}= \bar e_i$, and  $h_i \in \tau_{e_i}(\bbX_{e_i}) < \bbX_{v_{i+1}}$. The Bass diagram implies that $g_1e_1g_2\cdots e_ng_{n+1}$     is not reduced either.

If $g$ is cyclically reduced, consider $\alpha(g)$, and assume by contradiction that it  is not cyclically reduced. There is a shorter conjugate, and its image by $\alpha^{-1}$ (also in $\delta_1\autfo \bbX$, inducing an isometry of the Bass-Serre tree),
is a conjugate of $g$ that is represented by a word that is reduced by the previous argument, and shorter: a contradiction.

§.§.§ Action on linkages, and on double cosets

For the remainder of this section we assume any tuple $T$ of elements is  centered and its elements lie in $\pi_1(\bbX,v_T)$ where $v_T$ is the central vertex of the centered tuple. The leading entry of $T$ is in centered short position and the first edge in its prefix is $e_T$. We will always use $e_T$-polarized normal forms to work with the element of $T.$

Let us compute the action  of $\delta_1 \autfo \bbX$ on the linkage tuples. Observe that it is equivalent to consider $\delta_1 \aut \bbF$. First of all we will want to fix an edge $e$ and consider $e$-polarized normal forms. Obviously this only makes sense for element of $\pi_1(\bbX,v)$ with $i(e)=v$. Given $g \in \pi_1(\bbX,i(e))$ and $\phi=(Id_X, (\phi_v), (Id_e), (\gamma_e))$ an element of $\delta_1 \autfo \bbX$ we define the $e$-polarized action of $\phi$ to be
\[
\phi\cdot_e g = (\ad{\gamma_{\bar e}^{-1}}\circ \phi)(g),
\]
where for this section $\ad{x}(y) = x^{-1}yx$. Note that $(\ad x \circ \ad y) (z) = \ad x (y^{-1}zy) = x^{-1}y^{-1}z y x = \ad{yx}(z)$, which due to the fact that our conjugation convention gives a right action but functions act on the left.

The $e-$polarized action is well-defined group action.

Let $\phi=(Id_X, (\phi_v), (Id_e), (\alpha_e))$, $\psi=(Id_X, (\psi_v), (Id_e), (\beta_e))$  and let $\theta = \psi\circ\phi = (Id_X, (\psi_v), (Id_e), (\gamma_e))$. On the one hand we have
\[
\psi(\phi(e))=\psi(\alpha_{\bar e}^{-1})
\beta_{\bar e}^{-1}
e \beta_e \psi(\alpha_e) \Rightarrow \gamma_{\bar e}^{-1} = \psi(\alpha_{\bar e}^{-1})\beta_{\bar e}^{-1}.
\]
(See also the Bass diagram (<ref>).)  On the other hand we have
\[
(\ad{\beta_{\bar e}^{-1}}\circ\psi)\circ(\ad{\alpha_{\bar e}^{-1}}
\circ \phi) = \ad{\beta_{\bar e}^{-1}}\circ\ad{\psi(\alpha_{\bar
e}^{-1})} \circ \psi\circ\phi = \ad{\psi(\alpha_{\bar
e}^{-1})\beta_{\bar e}^{-1}} \circ \psi\circ\phi.
\]
It follows that
\[
(\psi\circ \phi)\cdot_e (g) = (\ad{\gamma_{\bar e}^{-1}}\circ \psi\circ \phi)(g) = \psi\cdot_e(\phi\cdot_e g),
\]
as required.

Let $g\in \pi_1(\bbX, v)$, and let its reduced fiber form be
\[g=\bar f_1e_1 \bar f_2\cdots e_nf_{n+1} t^k,\]
where $t$ is our oriented generator of the center of $\bbX_v$ and write $v_i = \tau(e_{i-1}) = i(e_i)$, so that $f_i \in \bbX_{v_i}\cap F$.
Let $\phi=(Id_X, (\phi_v), (Id_e), (\gamma_e))$ an element of $\delta_1 \autfo \bbX$. Let $e$ be such that $i(e)=v$

The image of $\phi\cdot_e g$  has same $X$-path, and same sequence of turns as $g$.

The linkage tuple of $\phi \cdot_e g$ with respect to the $e$-polarization has $i$-th coordinate that is equal to $ (\phi_{v_i} ( \langle I_{e_{i-1}}, f_i O_{e_i} f_i^{-1} \rangle ))^{ \gamma_{e_{i-1}}^{-1}}      $, which is $\phi_{v_i} ( \vec{\link{}}(g)_i)^{\gamma_{e_{i-1}}^{-1}} $.

First note that $\phi(t) = t$ since $\phi$ is orientation pererving and $t$ is a generator of the center of $\bbX_{b}$. The equality of the paths is immediate, given that $\phi$ induces $Id_X$, hence the sequence of turns is the same too.

We write

\begin{multline}\label{eqn:phieofg}
\phi\cdot_e g = \gamma_{\bar e} \phi(g) \gamma_{\bar e}^{-1} =  \gamma_{\bar e} \phi_{v_1}(f_1) \gamma_{\bar e_1}^{-1} \cdot e_1 \cdot \gamma_{e_1}\,\phi_{v_2} (f_2) \gamma_{\bar e_2}^{-1} \cdot e_2 \cdots\\ e_n \cdot \gamma_{e_n}\cdot\phi_{v_{n+1}} (f_{n+1}) \gamma_{\bar e}^{-1}  \, t^{\pm k}
\end{multline}

Considering the sequence $DC(\phi\cdot_e g,e)$ we see that we can express $\vec{\link{}}(\phi(g))_i$ as

\[\vec{\link{}}(\phi(g))_i = \langle I_{e_{i-1}}, \gamma_{e_{i-1}} \phi_{v_i} (f_i) \gamma_{\bar e_i}^{-1}\, \cdot \, O_{e_i} \,\cdot \,  \gamma_{\bar e_i}     \phi_{v_i} (f_i)^{-1} \gamma_{e_{i-1}}^{-1}    \rangle, \]
for $1\leq i \leq n+1$ and where, for the sake of defining cosets in the context of $e$-polarization, we define $e_0=\bar e$ and $e_{n+1}=e$. The Bass diagram (for $e_{i-1}$ and $\bar e_i$) ensures:

\begin{equation}\label{eq:bass-diag-oeie}
\begin{array}{rclr}
\gamma_{\bar e_i}^{-1} O_{e_i}  \gamma_{\bar e_i} & = & \phi_{v_i} (O_{e_i}) &  (\hbox{image of } O_{e_i})
\\  I_{e_{i-1}} & = &  \gamma_{e_{i-1}} \phi_{v_i} ( I_{e_{i-1}})\gamma_{e_{i-1}}^{-1} &  (\hbox{image of } I_{e_{i-1}}).
\end{array}
\end{equation}

It follows that
\begin{multline*}\langle I_{e_{i-1}}, \gamma_{e_{i-1}} \phi_{v_i} (f_i) \gamma_{\bar e_i}^{-1} O_{e_i}  \gamma_{\bar e_i}     \phi_{v_i} (f_i)^{-1} \gamma_{e_{i-1}}^{-1}    \rangle = \\
\langle \phi_{v_i} (I_{e_{i-1}}),  \phi_{v_i} (f_i) \phi_{v_i} (O_{e_i})       \phi_{v_i} (f_i)^{-1}    \rangle^{\gamma_{e_{i-1}}^{-1}}, \end{multline*}
which is what we wanted.

For all vertex $v$ and edges $e_-, e_+$ such that $\tau(e_-) = i(e_+)=v$,  we consider the following action of $\delta_1 \autfo \bbX$ on the set  $I_{e_-} \backslash \bbF_v/ O_{e_+}$ of double cosets   $I_{e_-} f O_{e_+}$   in $\bbF_v$.

Let  $\phi= (Id_X, (\phi_v), (Id_e), (\gamma_e)) \in \delta_1 \autfo \bbX$, let  $w\in \verts X$ be a white vertex, and let $e_-, e_+$ edges such that $\tau(e_-) = i(e_+)=w$.   Let   $f\in \bbF_{v}$. and consider  the set   of  double cosets  $I_{e_-} f O_{e_+}$   in $\bbF_v$. We set

\[\phi \cdot  (I_{e_-} f O_{e_+}) \; = \;  I_{e_-} \, \gamma_{e_-} \phi_v(f) \gamma_{\bar e_+}^{-1}  \, O_{e_+}. \]

One easily checks from the composition formula in Section <ref> that this defines an action of $\delta_1 \autfo \bbX$  on  $I_{e_-} \backslash \bbF_v/ O_{e_+}$. By Lemma <ref>,  it is the natural action of the thus obtained automorphisms of $\torus \alpha$ on the double cosets defined by polarized reduced forms:

Consider $g \in \pi_1(\bbX,v)$ which, in $e$-polarized normal form, is written $g=f_1e_1f_2\cdots e_nf_{n+1} t^k$,  and $\phi \in \delta_1 \autfo \bbX$. For all $j$, denote $v_j=i(e_j)$. Then for all $i$, there exists $f'_i \in \bbF_{v_i}$ such that
\[\phi\cdot_e g = (\ad{\gamma_{\bar e}^{-1}}\circ \phi (g))=f'_1e_1f'_2e_2\cdots e_nf'_{n+1} t^k,\]
and the double coset $I_{e_{i-1}} f'_i O_{e_i}$ is $\phi\cdot (I_{e_{i-1}} f_i O_{e_i})$. Equivalently if $DC(g,e)=(I_{\bar e}f_1 O_{e_1},1,\ldots,1, I_{e_n} f_{n+2} O_{\bar e})$ then
\[\phi\cdot DC(g,e)=DC(\phi\cdot_e g,e) = \left(\phi\cdot(I_{\bar e}f_1 O_{e_1}),1,\ldots,1, \phi\cdot(I_{e_n} f_{n+2} O_{e})\right).\]

The expression of $\phi\cdot_e g$ has already been computed in (<ref>) in the proof Lemma <ref>, where setting $e_0=\bar e$ and $e_{n+1}=e$ we have

\[\phi\cdot e(g) = \gamma_{e_0}\phi_{v_1}(f_1) \gamma_{\bar e_1}^{-1} \cdot e_1 \cdot \gamma_{e_1} \phi_{v_2} (f_2) \gamma_{\bar e_2}^{-1} \cdot e_2 \cdots e_n \cdot \gamma_{e_n} \phi_{v_{n+1}} (f_{n+1})\gamma_{\bar e_{n+1}}^{-1} \; t^{\pm k}.  \]
We further note that in the word above the factors $(\gamma_{e_{2i-1}}\gamma_{\bar e_{2i}}^{-1}), i=1,\ldots,n/2$ that appear in the abelian vertex groups can be migrated through either $e_{2i-1}$ or $e_{2i}$ without affecting the double coset. The proposition now follows.

§.§.§ The action of automorphisms on sequence of double cosets, and a linkage configuration

Consider two double coset sequences $DC(g,e_0)$ and $DC(g',e_0)'$ over the same $X$-path with polarizing edge $e_0$. Consider the linkage configurations induced for each vertex and oriented edge in $X$ by these sequences, $\calQ_{v,e}=\calQ_{v,e}(g,e_0)$ and $\calQ'_{v,e}(g',e_0)$.

There exists an automorphism $\phi =(Id_X, (\phi_v), (Id_e), \gamma_e) \in \delta_1 \autfo \bbX$ that sends $DC(g,e)$ to $DC(g',e)'$ (for the action defined by Convention <ref> and as in Proposition <ref>)  if, and only if,
for each $v \in \verts X$ and each $e \in \edges X$, there exists a $\phi_v$ and $\gamma_e$,  such that $\phi_v(\calQ_{v,e}) = (\calQ'_{v,e})^{\gamma_e}$.

Assume $\phi=(Id_X, (\phi_v), (Id_e), (\gamma_e))$ sends  $DC(g,e)$ to $DC(g',e)$.
Consider a linkage $\mathscr{l}$ that is associated, or dually associated, to a double coset $I_{e_-} f O_{e_+}$ in $DC(g,e)$, and $\mathscr{l}'$ the corresponding linkage for the image $I_{e_-} f' O_{e_+} $ by $\phi$ of this double coset.

Write $\mathscr{l} = \langle c_{e_-} , f c_{e_+} f^{-1} \rangle $, and $\mathscr{l}'= \langle c_{e_-} , f' c_{e_+} f'^{-1} \rangle $. We want to show that $\phi_v (\mathscr{l})$ is conjugate to $\mathscr{l}'$ by an element that only depends on $\phi$ and $e_-$.

We know (by Proposition <ref>) that $\phi \cdot I_{e_-} f O_{e_+} = I_{e_-} f' O_{e_+} $, but it is also, by definition of the action  $I_{e_-}  \gamma_{e_-}  \phi_v(f)   \gamma_{\bar e_+}^{-1}  O_{e_+}$.

It follows that  $\mathscr{l}'= \langle c_{e_-} ,
\gamma_{e_-}  \phi_v(f)   \gamma_{\bar e_+}^{-1}  c_{e_+}  (\gamma_{e_-}  \phi_v(f)   \gamma_{\bar e_+}^{-1})^{-1}\rangle      $.

By the Bass diagrams (as recorded in (<ref>) in the proof of Lemma <ref>), we also know that  $\phi_v (\mathscr{l})=   \langle c_{e_-}^{\gamma_{e_-}} ,  \phi_v(f) c_{e_+}^{\gamma_{\bar e_+}} \phi_v(f)^{-1} \rangle $.

This means that $\phi_v (\mathscr{l})=  \langle c_{e_-} ,  \gamma_{e_-} \phi_v(f) c_{e_+}^{\gamma_{\bar e_+}}  \phi_v(f)^{-1}  \gamma_{e_-}^{-1} \rangle^{\gamma_{e_-}}$, which is a conjugate of
$\mathscr{l}'$ by $\gamma_{e_-}$, as required.

We now show the converse. Suppose we are given automorphisms $\phi_v$ for each vertex of $X$ and an element $\gamma_e$ for each edge of $X$. By hypothesis,
$\phi_v(\calQ_{v,e}) =  (\calQ_{v,e}')^{\gamma_e}$.
Observe  the first coordinate of $\calQ_{v,e}$ and  $\calQ_{v,e}'$: one has   $\phi_v(c_e)= c_e^{\gamma_e}$.  This ensures that the tuple $(Id_X, (\phi_v), (Id_e), (\gamma_e))$ satisfies the Bass diagrams for all edges. This therefore defines an automorphism $(Id_X,(\phi_v),Id_e,\gamma_e)\in \delta_1 \autfo \bbX$.

Consider the $j$-th double coset in the tuple $DC(g,e)$, and denote it $I_{e_-} f O_{e_+} $. and denote by   $I_{e_-} f' O_{e_+} $  the $j$-th double coset of $DC(g',e)$ (observe that it must be a double coset for the same pair of groups, because the underlying path is the same).

We want to show that  $\phi \cdot  I_{e_-} f O_{e_+}$ is  equal to $I_{e_-} f' O_{e_+} $.  Recall that by definition  $\phi\cdot I_{e_-} f O_{e_+} = I_{e_-}  \gamma_{e_-}  \phi_v(f)   \gamma_{\bar e_+}^{-1}  O_{e_+} $. So we immediately rephrase our goal as to show equality between

\[  I_{e_-}  \gamma_{e_-}  \phi_v(f)   \gamma_{\bar e_+}^{-1}  O_{e_+} \; \hbox{ and } \;  I_{e_-} f' O_{e_+}.  \]

The double coset $I_{e_-} f O_{e_+} $ defines the two linkages $\mathscr{l}_j$ and $(\mathscr{l}_*)_j$, which, with the notations of Section <ref> are respectively part of

the linkage configurations $\calQ_{v,e_-}$ and $\calQ_{v, \bar e_+}$ (see Lemma <ref>.)

Let $\mathscr{l}'_j, ({\mathscr{l}'}^*)_{j}$ be the (mutually dual) linkages of $I_{e_-} f' O_{e_+} $ for the corresponding index for $DC(g',e)$.

By assumption on the preservation of linkage configurations, $\phi_v(\mathscr{l}_j) =  (\mathscr{l}'_j)^{\gamma_{e_-}}$ and  $\phi_v(\mathscr{l}^*_j) =  ({\mathscr{l}'}^*_j)^{\gamma_{\bar e_+}}$.

Let us write these equality in more detail. Recall that $\mathscr{l}_j = \langle c_{e_-},  f c_{e_+}f^{-1}\rangle $, and that, by the Bass diagrams, we have   $ \phi_v(c_{e_-}) = c_{e_-}^{\gamma_{e_-} }$, and   $\phi(c_{e_+}) = c_{e_+}^{\gamma_{\bar e_+} }$.

We have

\[\begin{array}{rcl}

\phi_v(\mathscr{l}_j) & = &  \langle c_{e_-}^{\gamma_{e_-}},  \phi_v(f) c_{e_+}^{\gamma_{\bar e_+}} \phi_v(f)^{-1} \rangle \\
& = &  \langle c_{e_-}, \;    \gamma_{e_-} \phi_v(f)\gamma_{\bar e_+}^{-1} \,  c_{e_+} \,{\gamma_{\bar e_+}} \phi_v(f)^{-1} \gamma_{e_-}^{-1} \rangle^{\gamma_{e_-}} \end{array}  \]

However, as already mentionned,  $\phi_v(\mathscr{l}_j) = (\mathscr{l}'_j)^{\gamma_{e_-}}$.  Therefore
\[\mathscr{l}'_j \; = \;  \langle c_{e_-}, \;    \gamma_{e_-} \phi_v(f)\gamma_{\bar e_+}^{-1} \,  c_{e_+} \,{\gamma_{\bar e_+}} \phi_v(f)^{-1} \gamma_{e_-}^{-1} \rangle. \]

In the same way, considering the duals, one checks that

\[{\mathscr{l}^*}'_j \; = \;  \langle c_{\bar e_+},    \;\gamma_{\bar e_+} \phi_v(f)^{-1} \gamma_{e_-}^{-1} \,  c_{e_-} \, {\gamma_{e_-}} \phi_v(f) \gamma_{\bar e_+}^{-1} \rangle.  \]

It remains to apply Proposition <ref> to obtain, as desired,  that

\[  I_{e_-}  \gamma_{e_-}  \phi_v(f)   \gamma_{\bar e_+}^{-1}  O_{e_+} \;  =   \;  I_{e_-} f' O_{e_+}.  \]

§.§.§ Orbits in vertices I: subgroups,  linkages

Suppose we are given two centered tuples of tuples $\vec S=(S_1,\ldots,S_k)$ and $\vec T=(T_1,\ldots, T_k)$. Denote by $e_i$ the polarizing edge $e_{S_i}$ and $v_i$ the central vertex $v_{S_i}$. Consider the action
\begin{equation}\label{eq:tupletuple-action}
\left.
\begin{array}{l}
\phi\cdot \vec S = (\phi\cdot S_1,\ldots,\phi\cdot S_k)\\
\phi\cdot S_i = \begin{cases}
(\phi\cdot_{e_i} S_{i1},\ldots,\phi\cdot_{e_i} S_{il_i})
& \text{if  $S_i$ is not elliptic,}\\
& \text{if $S_i$ is elliptic.}
\end{cases}
\end{array}
\right.
\end{equation}

Our first goal is to decide if this action can bring all the double cosets in $\vec{DC}(S_i)$ to $\vec{DC}(T_i)$ for $1\leq i \leq k$ for the $S_i,T_i$ that are non-elliptic, where
$$\vec{DC}(T_i) = DC(T_{i1},e_{T_i})\odot \cdots \odot DC(T_{il_i},e_{T_i}),$$
where $\odot$ denotes concatenation of tuples.

We recall the following theorem of Gersten improving the classical Whitehead algorithm.

Let  $\freegp{}$ be a finitely generated free group, and $A,B$ be two tuples of conjugacy classes of finitely
generated subgroups of $\freegp{}$ then,

*  There is an effective procedure for determining if there is
some $\alpha \in \aut{\freegp{}}$ such that $\alpha A = B$.

*  The stabilizer of $B$ in $\aut{\freegp{}}$ is finitely
presented and a finite presentation can be effectively

We need the following refinement, in which the conjugators for certain subgroups are required to be equal.

Let $\freegp{}$ be a finitely generated free group, and
$$A=([A_1], \dots [A_r]), B=([B_1], \dots, [B_r])$$
be two tuples of  conjugacy classes of tuples of finitely
generated subgroups of $\freegp{}$ then,

*  There is an effective procedure for determining if there is
some $\alpha \in \aut{\freegp{}}$ such that, for all $i$,   $[\alpha A_i]=[B_i]$ (as conjugacy classes of tuple of subgroups).

*  The stabilizer of $B$ in $\aut{\freegp{}}$ is finitely
presented and a finite presentation can be effectively

Due to its  specific independence with the current notations and objects,  we differ the proof of Theorem <ref> to Section <ref>. We finish now our  study of the Mixed Whitehead Problem assuming that Theorem <ref> is established.

Given two centered tuples of tuples $\vec S=(S_1,\ldots,S_k)$ and $\vec T=(T_1,\ldots, T_k)$, it is decidable whether there exists some $\phi \in \delta_1\autfo\bbX$ such that
\[
\vec{DC}(\phi\cdot S_i) = \vec{DC}(T_i)
\]
for $i=1,\ldots,k$ and $S_i,T_i$ are non elliptic, and such that for elliptic tuples
\[
[\phi\cdot S_i]_{v_i}=[Ti]_{v_i}
\]

where the action is as defined in (<ref>) and where $[S_i]_{v_i}$ denotes conjugacy classes in $\bbX_{v_i}$. Furthermore, a finite generating set of the stabilizer $A_{\vec T}\leq\delta_1\autfo\bbX$ of the all the tuples $\vec{DC}(T_i)$ and $[T_j]$ for $T_i$ non-elliptic and $T_j$ elliptic (respectively) can be computed.

This problem is solved by using an instance of the mixed Whitehead Problem for subgroups for each free group $F_v, v \in \verts X$. For a given vertex $v$ the tuple of tuples $\calT_v(\vec S)$ for a tuple of tuples $\vec S$ is constructed as follows:

* Let $I_v$ denote the indices $i$ such that $S_i$ is elliptic and the central vertex $v_{S_i}=v$, let $J$ denote the indices of the non-elliptic tuples.

* Let $\calE_v = (\calQ(S_i):i \in I_v)$, be the tuple of linkage configurations of elliptic tuples centered at $v$.

* Denote by
\[
\calH_{v,e}(S_i) = \bigodot_{j=1}^{l_j}\left( \calP_{v,e,j}\odot\calP_{v,e,j}^*\right)
\]
where $\calQ_{v,e}(S_{ij},e_j) = (c_e,\calP_{v,e},\calP_{v,e}^*)$ is the linkage configuration for the entry $S_{ij}$ of $S_i$ and $\odot$ denotes concatenation of tuples.

* Set $\calH_{v,e} = (c_e) \odot\left(\bigodot_{i \in J} \calH_{v,e}(S_i)\right)$ then make the tuple of tuples of subgroups
\[\calH_v = (\calH_{v,e}: e \in \edges X).\]

* The required tuple of tuples
\[
\calT_v = \calE_v \odot \calH_v.
\]

By Theorem <ref> the Mixed whitehead problem for tuples of tuples of subgroups of $F_v$ is decidable so we can decide $\calT_v(\vec S)$ and $\calT_v(\vec T)$ are equivalent via some $\phi_v \in \aut{F_v}$. The issue remains that even we preserved the conjugacy classes of subgroups $\bk{c_e}$ or entries $\bk{(T_{ij})_f}$ in $\phi_v(\calE_v)$, we may have sent the certain of the $c_e$ or $(T_{ij})_f$ to conjugates of their inverses. However, because we can compute a finite generating set of the stabilizer of $\calT_v(\vec T)$, we can determine if there is an element of that stabilizer that also preserves the sign of those elements. Once we have done this and amended $\phi_v$ we can then compute a generating set of the finite index subgroup of the stabilizer of $\calT_v(\vec T)$ that also preserves the signs of individual elements.

The result now follows by applying Proposition <ref> for corresponding pairs of non-elliptic tuples and by the definition of the Mixed Whitehead problem applied corresponding pairs of elliptic tuples.

§.§.§ Orbits in vertices II: actions on power tuples.

Fix an $X$-loop $\rho=e_1,\ldots,e_n$ based at $v$ a polarizing edge $e$ with $i(e)=v$ and a sequence of cosets $D = (I_{\bar e} f_1 O_{e_1},1,I_{e_2}f_3O_{e_3},\ldots,I_{e_n}f_{n+1}O_{e})$. We call $\calE_{(D,p,e)} = \mathbb Z^{n/2+3}$ the embedding space for $(D,\rho,e)$. There is a bijection from $\calE_{(D,\rho,e)}$ to the set:

\[ \calG(D,\rho,e)=\{ g \in \pi_1(\bbX,v)| g \textrm{~has underlying $X$-path $\rho$ and~} DC(g,e)=D\}\]

given by the inverse maps:

\begin{eqnarray*}
(d_0,d_2,\ldots,d_{n+1},k) & \mapsto & c_{\bar e}^{d_0}\bar f_1 e_1e_2 c_{e_2}^{d_2}\bar f_3 \cdots e_nc_{e_n}^{d_n} \bar f_{n+1} c_{\bar e}^{d_{n+1}} t_b^k\\
\mathrm{pow}(g,e) & \mapsfrom & g
\end{eqnarray*}

Where the $\bar f_i$ are the coset representatives from $DCR(g,e)$. This next lemma justifies the use of polarized actions.

If $g \in \pi_1(\bbX,i(e_1))$ is centered $e_1e_2$-prefix-short and $\phi=(Id_X, (\phi_v), (Id_e), (\gamma_e)) \in \delta_1 \autfo \bbX$. Then $\phi\cdot_{e_1} g$ is also centered $e_1e_2$-prefix-short. In other words the $e_1$-polarized action of $\delta_1 \autfo \bbX$ acts on the set of centered $e_1e_j$-prefix-short elements.

Let $g = e_1e_2f_2\cdots$ and applying $\phi$ to each symbol gives
\[
\phi\cdot_{e_1} g = \gamma_{\bar e} \phi(g)\gamma_{\bar e}^{-1}
= \gamma_{\bar e_1}( \gamma_{\bar e_1}^{-1}e_1\gamma_{e_1}\gamma_{\bar{e_2}}^{-1}e_2\gamma_{e_2}\phi_{v_2}(f_2) \cdots )\gamma_{\bar e_1}^{-1}.
\]
Since $v_1=\tau(e_1)$ is abelian and coincides with the images of incident edge groups we can migrate $\gamma_{e_1}\gamma_{\bar{e_2}}^{-1}$ accross $e_2$ to get
\[
\phi\cdot_{e_1} g = e_1e_2f_2'\cdots,
\]
as required.

For any $\phi \in \delta_1\autfo\bbX$ and $g \in \pi_1(\bbX,i(e))$, $g$ is $ee_j$-prefix short, for some other $e_j \in \edges X$ if and only if $\phi\cdot_e g $ is $ee_j$-prefix short.

With this detail established we now have:

Let $D$ be a tuple of cosets, let $A_D \leq \delta_1\autfo\bbX$ be a subgroup of automorphisms that preserves the cosets in $D$ via the action in Convention <ref>. Then $A_D$ acts on $\calG(D,\rho,e)$ and also, viewing $\calE_{D,\rho,e}$ as an abelian group, there is a homomorphism
\[\epsilon_{D,\rho,e}: A_D \to \calE_{D,\rho,e}\]
such that
\[
\mathrm{pow}(\phi\cdot_e g,g) = \mathrm{pow}(g,e)+\epsilon_{D,\rho,e}(\phi).
\]

The proof amounts to applying $\phi\cdot_e$ and keeping track of exponents. Applying $\phi$ to every symbol and making obvious cancellations gives:

\begin{multline*}
\phi\cdot_e g=  \phi\cdot_e (c_{\bar e}^{d_0}\bar f_1 e_1e_2 c_{e_2}^{d_2}\bar f_3 \cdots e_nc_{e_n}^{d_n} \bar f_{n+1} c_{\bar e}^{d_{n+1}} t_b^k)\\
= \gamma_{\bar e} \phi(c_{\bar e}^{d_0})\phi(\bar f_1)\phi(e_1)\phi(e_2) \cdots
\phi(e_n)\phi(c_{e_n}^{d_n}) \phi(\bar f_{n+1})\phi(c_{\bar e}^{d_{n+1}})\phi( t_b^k)
\gamma_{\bar e}^{-1}\\
= \gamma_{\bar e} \gamma_{\bar e}^{-1}c_{\bar e}^{d_0}\gamma_{\bar e}\phi(\bar f_1)\gamma_{\bar e_1}^{-1}e_1 \gamma_{e_1} \gamma_{\bar e_2}^{-1}e_2 \gamma_{e_2} \cdots\\
\gamma_{\bar e_n}^{-1}e_n\gamma_{e_n}\gamma_{e_n}^{-1}c_{e_n}^{d_n} \gamma_{e_n} \phi(\bar f_{n+1})\gamma_{\bar e}^{-1} c_{\bar e}^{d_{n+1}} \gamma_{\bar e}\gamma_{\bar e}^{-1}t_b^k\\
=c_{\bar e}^{d_0}(\gamma_{\bar e}\phi(\bar f_1)\gamma_{\bar e_1}^{-1})e_1 (\gamma_{e_1} \gamma_{\bar e_2}^{-1})e_2 \gamma_{e_2} \cdots
\gamma_{\bar e_n}^{-1}e_nc_{e_n}^{d_n} (\gamma_{e_n} \phi(\bar f_{n+1})\gamma_{\bar e}^{-1}) c_{\bar e}^{d_{n+1}}t_b^k
\end{multline*}

Now note that for every odd index $i$, noting that the vertex group $\bbX_{\tau(e_i)}$  must be abelian and coincides with images of incident edge groups we have

\[e_i(\gamma_{e_i}\gamma_{\bar e_{i+1}}^{-1}) e_{i+1} = e_{i}e_{i+1}c_{e_i+1}^{m_i},\]
for some $m_i \in \bbZ$. This gives

\begin{multline*}
\phi\cdot_e g = c_{\bar e}^{d_0}(\gamma_{\bar e}\phi(\bar f_1)\gamma_{\bar e_1}^{-1})e_1 e_2 c_{e_2}^{m_2} \cdots
e_n c_{e_n}^{m_n}c_{e_n}^{d_n} (\gamma_{e_n} \phi(\bar f_{n+1})\gamma_{\bar e}^{-1}) c_{\bar e}^{d_{n+1}}t_b^k
\end{multline*}

Finally note that our assumption that $\phi$ preserves $D$ implies that since $\bar f_{i+1} \in \bk{c_{e_i}}\bar f_{i+1} \bk{c_{\bar e_{i+1}}}$ then we must have that $\phi(\bar f_{i+1}) = c_{e_i}^{n_i}\bar f_{i+1} c_{\bar e_{i+1}}^{n_{i+1}}$ for some $n_i,n_{i+1} \in \bbZ$,

provided we set $e_0 = \bar e$ and $e_n = e$. Applying the identities
\[
c_{\bar e_{i+1}}^{n_{i+1}} e_{i+1}e_{i+2}=e_{i+1}e_{i+2} c_{e_{i+2}}^{n_{i+1}}
\]
finally gives
\[
\phi\cdot_e g = c_{\bar e}^{d_0+n_0}\bar f_1 e_1e_2 c_{e_2}^{d_2+n_1+m_1+n_2}\bar f_3 \cdots e_nc_{e_n}^{d_n+n_{n-1}+n_n+m_{n-1}} \bar f_{n+1} c_{\bar e}^{d_{n+1}+n_{n+1}} t_b^k.
\]
Thus, if $g$ is not $ee_j$-prefix clean we have
\[\mathrm{pow}(\phi\cdot_e g,e) = \mathrm{pow}(g,e)+\underbrace{(n_0,m_1+n_1+n_2,\ldots,m_{n-1}+n_{n-1}+n_n,n_{n+1})}_{\epsilon_{D,\rho,e}(\phi)},\]
since $\epsilon_{D,\rho,e}(\phi)$ doesn't depend on $\mathrm{pow}(g,e)$, but only on $D,\rho,e,\phi$.

If $g$ is $ee_j$ prefix clean, then note that since $e_1=e$ we have

\[%\begin{multline*}
\phi\cdot_e e_1e_2c_{e_2}^{d_2}\bar f_3 \cdots = \gamma_{\bar e} \gamma_{\bar e}^{-1}e_1\gamma_{e_1}\gamma_{e_2}^{-2}e_2 \cdots =e_1\gamma_{e_1}\gamma_{e_2}^{-2}e_2 \cdots = e_1e_2\cdots
\]

In particular if $g$ is $ee_j$ prefix clean then the $n_0$-entry in $\epsilon_{D,\rho,\epsilon}(\phi)$ is trivial.

Up to this point we have been focusing mainly on fiber parts of words we will now consider conjugation by elements that are not in the fiber.

Let $D$ be a tuple of cosets, $e$ some polarizing edge and $\rho$ some $X$-loop based at $i(e)=v$ that is compatible with $D$. Then the edge group $\bbX_e$ acts on $\calG(D,\rho,e)$ via
\[
a \cdot g = i_e(a) g i_e(a)^{-1}, g \in \calG(D,\rho,e), a \in \bbX_e
\]
and this action induces a homomorphism $\alpha_{D,\rho,e}:\bbX_e \to \calE_{D,\rho,e}$ such that
\[
\mathrm{pow}(a\cdot g,g) = \mathrm{pow}(g,e)+\alpha{D,\rho,e}(a).
\]

By the definition of $e-$polarized normal forms, conjugation of $g$ by $i_e(a)=c_{\bar e} \in i_e(\bbX_e)$ doesn't change $DC(g,e)$. If $g$ is $ee_j$-prefix clean then we can  migrate the initial $c_{\bar e}^{n_0}$ symbol through the $ee_j$ prefix and stay in prefix clean form. It's easy to verify that the new power vector is obtained from the old power vector by adding some $\epsilon_{D,\rho,e}(a)$. The other generator of $i_e(\bbX_e)$ is $t_v$, the generator of the center of $\bbX_v$. The action by conjugation by $t_v$ on the fiber $F \leq \torus\alpha$ is precisely the multiple Dehn twist $\alpha$ which is given by the $\edges X$ substitution $e \mapsto e c_e^{n_{e,\alpha}}$. In particular conjugation by $t_v$ can be realized by an element of $\delta_1\autfo\bbX$ so Proposition <ref> implies the result for conjugation by powers of $t_v$, and the result follows.

Let $A_D \leq \delta_1\autfo\bbX$ be a subgroup of automorphisms that preserve the cosets in $D$. Then $\bbX_e\times A_D$ acts on $\calG(D,\rho,e)$ via
\[
(a,\phi)\cdot g = i_e(a)(\phi\cdot_e g)i_e(a)^{-1}
\]
and this action gives rise to a homomorphism
\[
\chi_{D,\rho,e}:\bbX_e\times A_D \to \calE_{D,\rho,e}
\]
such that

\begin{equation}\label{eqn:power-action}
\mathrm{pow}((a,\phi)\cdot g,e)=\mathrm{pow}(g,e)+\chi_{D,\rho,e}(a,\phi)
\end{equation}

§.§ Solving the fiber and orientation preserving Mixed Whitehead problem

In this section we describe and prove the correctness of our algorithm. Suppose we are given two tuples of tuples $\vec S=(S_1,\ldots,S_k)$ and $\vec T=(T_1,\ldots, T_k)$ of elements from $\torus\alpha$. The fibre and orientation preserving Mixed Whitehead problem is the decision problem of whether $\vec S$ and $\vec T$ in the same orbit under the action of $\delta\autfo\bbX\times(\torus\alpha^k)$ given by

\begin{equation}\label{eqn:OG-action}
(\phi,g_1,\ldots,g_k)\cdot (S_1,\ldots,S_k) = (g_1^{-1}\phi(T_1)g_1,\ldots,g_k^{-1}\phi(T_k)g_k).
\end{equation}

We first note that $\vec S$ and $\vec T$ are in the same orbit if and only if their augmentations $\vec S^+=(S_1^+,\ldots,S_k^+)$ and $\vec T^+=(T_1^+,\ldots, T_k^+)$ are in the same orbit. So, without loss of generality, we will assume that $\vec S$ and $\vec T$ are tuples of augmented tuples, if they aren't then we replace their entries by augmentations (which can be done algorithmically).

By Lemma <ref> this problem could be reduced to a finite computable set of instances of similar orbit problems under $\delta_1\autfo\bbX\times(\torus\alpha^k)$. Specifically $\vec S$ and $\vec T$ are in the same $\delta_1\autfo\bbX\times(\torus\alpha^k)$-orbit if and only if for for one of the representatives $\nu_i$ of a coset of $\delta_1\autfo\bbX\backslash\delta\autfo\bbX$ we have that $\vec{\nu_i(S)}$ is in the same $\delta_1\autfo\bbX\times(\torus\alpha^k)$-orbit as $\vec T$.

Now given some tuple $T$ of elements, we denote by $\calT$ the set of all the $\Bass(\bbX)$-conjugates of $T$ that are in centered short position (recall Section <ref>), if $T$ is hyperbolic or lineal, otherwise $\calT$ is the set containing the centering of $T$ and all its variations, should any exist (recall Section <ref>.) With this notation we define two sets of tuples of tuples
\[
\vec{\calS} = \bigcup_{i=1}^v\calS_{i1}\times\cdots\times\calS_{ik}
\]
where $\{\nu_1,\ldots,\nu_v\}$ is the computable set of representatives given by Lemma <ref> and $\vec{\nu_i(S)} = (S_{i1},\ldots,S_{ik}); i=1,\ldots,v$. We also define
\[
\vec\calT = \calT_1\times\cdots\times\calT_k
\]
where $\vec T = (T_1,\ldots,T_k)$.

On the one hand, $\delta_1\autfo\bbX$ actually extends to a group of automorphisms $\Bass(\bbX)$. On the other hand Lemma <ref> implies that we can extend our consideration to conjugation in the Bass group. Therefore our original $\vec S$ and $\vec T$ are in the same $\delta\autfo\bbX\times(\torus\alpha^k)$-orbit if and only if there exists at least one pair of tuples of tuples $\vec S' \in \vec\calS$ and  $\vec T' \in \vec\calT$ that are in the same $\delta_1\autfo\bbX\times(\Bass(\bbX)^k)$-orbit.

In Section <ref>, we considered polarized actions which are not exactly the same as the action given in (<ref>). However, since the Mixed Whitehead problem involves post-conjugation by group elements, this does not
change the problem. To be clear: our original $\vec S$ and $\vec T$ are in the same $\delta\autfo\bbX\times(\torus\alpha^k)$-orbit if and only if there exists at least one pair of tuples of tuples $\vec S' \in \vec\calS$ and  $\vec T' \in \vec\calT$ that are in the same $\delta_1\autfo\bbX\times(\Bass(\bbX)^k)$-orbit where the new action is given by:

\begin{equation}\label{eqn:newschool-action}
(\phi,g_1,\ldots,g_k)\cdot (S'_1,\ldots,S'_k) = \left(g_1^{-1}(\phi \cdot S'_1) g_1,\ldots,g_k^{-1} (\phi\cdot S'_k)g_k\right).
\end{equation}

Where the action is given by (<ref>). This is because if $S'_j$ is hyperbolic or lineal, then $\phi\cdot S'_j = \gamma_{\bar e} \phi(S'_j)\gamma_{\bar e}^{-1}$.

By Lemma <ref>, prefix short forms are preserved by polarized actions. So suppose that $\vec S'$ and $\vec T'$ are in the same $\delta_1\autfo\bbX\times(\Bass(\bbX)^k)$ orbit, under the new action. Then there is some $\phi \in \delta_1\autfo\bbX$ such $\phi\cdot S'_i$ is conjugate in $\Bass(\bbX)$ to $T'_i$ for all $i=1,\ldots,k$. Now non-elliptic tuples in $\phi \cdot \vec S'$ may no longer be centered short position, but their leading entries are in prefix clean position. It follows that there are elements in $a_i\in i_{e_i}(\bbX_{i_(e_i)})$ such that the leading entry of
\[
a_i (\phi\cdot S'_i)a_i^{-1}
\]
is in short position for all appropriate indices. We'll now show why the entire tuple  $a_i (\phi\cdot S'_i)a_i^{-1}$ is in centered short position (and not only its leading entry). If that isn't the case, then we would need to further conjugate $a_i (\phi\cdot S'_i)a_i^{-1}$ by some element in the centralizer of the first entry to get to short position of the tuple. If $S'_i$ is lineal, doing so doesn't change any of the entries in $a_i (\phi\cdot S'_i)a_i^{-1}$, so $a_i (\phi\cdot S'_i)a_i^{-1}$ is already in short position. Otherwise $S'_i$ was already chosen so that its second entry had shortest syllable length among all conjugates by the centralizer of the first entry, since applying $\phi$ and conjugation by $a_i$ did not change syllable lengths, further conjugation by an element of the centralizer of the first entry of $a_i (\phi\cdot S'_i)a_i^{-1}$ will increase the syllable length of the second entry, so in this case as well $a_i (\phi\cdot S'_i)a_i^{-1}$ is already in short position.

Now all the tuples in $\vec T'$ are also in centered short position. Thus either $a_i (\phi\cdot S'_i)a_i^{-1} = T'_i$, otherwise $a_i (\phi\cdot S'_i)a_i^{-1}$ is equal to one of the other finitely many short conjugates of $T'_i$. In particular there must be some other $\vec T'' \in \vec\calT$ such that $a_i (\phi\cdot S'_i)a_i^{-1} = T''_i$.

If $S'_i$ is elliptic and $\phi\cdot S'_i$ is conjugate to $T'_i$ then either $\phi\cdot S'_i$ is conjugate to $T'_i$ by an element of $\bbX_{v_{S'_i}}$ or by some element of the form $\bbX_{v_{S'_i}}\ell$ where $\ell$ is a loop in $X$ based at $v_{S'_i}$. By our definition of variations and by Lemma <ref>, there is some $\vec S''$ such that $\phi\cdot S''_i$ is conjugate to $T'_i$ by an element of $\bbX_{v_{S''_i}}$.

Therefore our original instance of the fibre and orientation preserving Mixed Whitehead problem has a positive solution if and only if there exist $\vec S' \in \vec\calS$ and $\vec T' \in \vec\calT$, some $\phi \in \delta_1\autfo\bbX$ and elements $a_i$ where $a_i \in F_{v_i}$ if $S'_i$ is elliptic and $a_i \in i_{e_i}(\bbX_{e_i})$ if $S'_i$ is lineal or hyperbolic such that

\begin{equation}\label{eqn:final}
a_i (\phi\cdot S'_i) a_i^{-1}=T'_i.
\end{equation}

Note that by Proposition <ref> conjugation by such elements $a_i$ for non-elliptic tuples leave invariant $DC(\phi\cdot S_i)$. We therefore finally apply Corollary <ref> to $\vec S'$ and $\vec T'$. This gives us an automorphism $\phi_1 \in \delta_1\autfo\bbX$ such that for elliptic tuples we already have $[\phi_1 \cdot S'_i]_{v_i} = [T'_i]_{v_i}$, so (<ref>) has a solution for elliptic tuples.

Without loss of generality the first $h$ entries $S'_1,\ldots,S'_h$ of $\vec S'$ are precisely the non-elliptic tuples, the same must be true for $\vec T'$. For a tuple of elements $T_{i}=(T_{i1},\ldots,T_{il_i})$ we define the embedding space
\[
\calE_{T_i} = \bigoplus_{j=1}^{l_i} \calE_{DC(T_{ij},e_i),\rho_{ij},e_i}
\]
where $\rho_{ij}$ is the $X$-path underlying $T_{ij}$. For the tuple of tuples $\vec T'$ we define the embedding space
\[
\calE(\vec T') = \bigoplus_{i=1}^h \calE_{T_i}.
\]

Now by Corollary <ref> we can decide if there is some  $\phi_1 \in \delta_1\autfo\bbX$ such that in addition $\vec{DC}(S'_i,e_i)=\vec{DC}(T'_i,e_i)$ in which case we would also have $\calE(\phi_1\cdot \vec S') = \calE(\vec T')$.

Consider now analogous mappings
\[\mathrm{pow}(T_i) = \bigodot_{j=1}^{l_i} \mathrm{pow}(T_{ij},e_i) \textrm{~and~} \mathrm{pow}(\vec T') = \bigodot_{i=1}^h \mathrm{pow}(T_i),\]
where $\odot$ denotes concatenation of tuples. By Corollary <ref> there is an action of $A_{\vec T'}\times \bbX_{e_1} \times \cdots\times \bbX_{e_h}$,  where $A_{\vec T'}$ is as given in Corollary <ref>, obtained by assembling the actions on embedding spaces and a corresponding homomorphism
\[
\chi: A_{\vec T'}\times \bbX_{e_1} \times \cdots\times \bbX_{e_h} \to \calE(\vec T'),
\]

that satisfies the analogue of (<ref>).

It finally follows that our instance of Mixed Whitehead problem has a solution if and only if for the fixed $\phi_1 \in \delta_1\autfo\bbX$ that we computed above, there is some $(\phi_2,a_1,\ldots,a_n) \in A_{\vec T'}\times \bbX_{e_1} \times \cdots\times \bbX_{e_h}$ such that
\[
\mathrm{pow}(\vec T') = \mathrm{pow}(\phi_1\cdot \vec S')+\chi(\phi_2,a_1,\ldots,a_n).
\]
Since we have an explicit generating set of
$A_{\vec T'}\times \bbX_{e_1} \times \cdots\times \bbX_{e_h}$ and can compute $\chi$ the problem reduces to deciding if given a generating set for a subgroup $\bk{h_1,\ldots,h_n}=H \leq \bbZ^n$ and two elements $\vec s$ and $\vec t$ whether there is $\vec h \in H$ such that $\vec t = \vec s + \vec h$. This amounts to elementary linear algebra over $\bbZ$ and is readily decidable.

It therefore follows that the fibre and orientation preserving Mixed Whitehead problem is decidable in $\torus\alpha.$

§.§ The proof of Theorem <ref>

We finally come back to  Theorem <ref>, for which we promised a proof.

Let fix a finite basis $X$ of $F=F(X)$, then there is a one to one correspondence between subgroups of $F$ and core graphs with a base vertex $v$ (see <cit.> or <cit.>.) If $H \leq \freegp n$ is finitely generated, then the corresponding based core graph is also finite. An unbased core graph is a directed graph with labels in $X$ which is folded (in the sense of <cit.>) without vertices of valence one. By <cit.> there is a bijective correspondence between conjugacy classes of subgroups of $F$ and unbased core graphs. $\aut{F}$ acts on this set of graphs as follows: given an automorphism $\alpha$ and an unbased graph $\StalGraph H$, the image $\alpha(\StalGraph H)$ is computed using the following steps.

*  For each edge labelled $y$    subdivide it into a path graph along which we read $\alpha(y)$.

*  Perform a sequence of Stallings folds, until the graph is folded.

*  Perform a coring operation, i.e. repeatedly contract edges adjacent to vertices of valence 1 to points until none such remain.

Details are given in <cit.>. Note that each  of these operations can be realized as a sequence of continuous quotient maps between graphs sending vertices to vertices. In particular each vertex of $\StalGraph H)$ has a well-defined image in $\alpha'(\StalGraph H)$. A crucial fact is that the individual folds or edge contractions in steps <ref> and <ref> can be done in any order and the end result will be the same.We will use Gerten's Theorem <ref> presented earlier.

As mentioned earlier, an actual subgroup $H \leq F$ is given by  a core graph with a base vertex $\BasedStalGraph H v$ which is a directed folded graph with labels in $X$ all of whose vertices, except possibly the base vertex $v$, have valence one. The elements of $H$ are precisely the reduced words one reads of reduced loops starting and ending at the base vertex $v$.

§.§.§ Construction of an auxiliary $F(X,K)$ with its tuples of conjugacy classes of subgroups

For the remainder of this section we fix tuples $A=(A_1,\ldots,A_r)$ and $B=(B_1,\ldots,B_r)$

of tuples of subgroups of $F=F(X)$ (i.e. each $A_i$ is a

tuple of subgroups).  We assume that $|A_i|=|B_i|$, and by convention, we assume that $|A_i|\geq 2$ for all $i$. It it happens that one is interested in $A_i$ being a singleton, one may duplicate it as a couple of twice the same subgroup, so that this convention is satisfied. This duplication does not add any further constraint, hence is done without loss of generality.

For each $i$, let $K_i$ be a  set of symbols  so that $|K_i|=|A_i|=|B_i|$.  Let $K=K_1 \sqcup \cdots \sqcup K_r$ and consider $F=F(X)$ as a free factor of $F(X,K)$.

We list $K_i = \{\kappa_{i1},\ldots,\kappa_{in_i}\}$ as a set of symbols double indexed by positive integers such that $K_i \cap X = \emptyset$ and such that $i\neq j \Rightarrow K_i\cap K_j = \emptyset$. A $K_i$-star is a directed labelled tree with a root vertex $v_i$ and for each symbol in $\kappa_{ij} \in K_i$ there is an edge outgoing from $v_i$ with label $\kappa_{ij}$.

We encode the tuples $A_i=(A_{i1},\ldots,A_{in_i})$ and $B_i=(B_{i1},\ldots,B_{in_i})$ of subgroups of $F$ using an tuple-graph, denoted $\StalGraph{A_i}$ and $\StalGraph{B_i}$, respectively. They are constructed by taking a $K_i$-star, the disjoint union of the core graphs with a base vertex $\BasedStalGraph{A_{ij}}{u_{ij}}$ (respectively $\BasedStalGraph{B_{ij}}{u_{ij}}$), and identifying the vertex of the $K_i$-star with incoming edge labelled $\kappa_{ij}$ to the base vertex $u_{ij}$ (respectively $v_{ij}$). The key fact is that although $\StalGraph{A_i}$ is not a based graph, due to its specific structure, and edges with special labels $\kappa_{ij}$ it is possible to recover the core graphs with base vertex $\BasedStalGraph{A_{ij}}{u_{ij}}$ or $\BasedStalGraph{B_{ij}}{v_{ij}}$ and thus the ordered tuple of subgroups $A_i$ or $B_i$ respectively.

An tuple-graph always has a distinguished vertex $v_i$, namely the only vertex with outgoing edges labelled by the elements $K_i$. Denote by $\dot A_i=\pi_1(\StalGraph{A_i},v_i) \leq F(X,K)$ the subgroup consisting of the elements that are represented as the words read along closed loops in $\StalGraph{A_i}$ based at $v_i$ and define $\dot{B_i}$ analogously. Note that the conjugacy classes $[\dot A_i]$ and $[\dot B_i]$ correspond exactly to the tuple graphs $\StalGraph{A_i}$ and $\StalGraph{B_i}$ respectively.

Fix the following tuples of subgroups:

\begin{eqnarray*}
\hat A &=& (\dot A_1, \ldots, \dot A_r, F(X), F(K_1),\ldots,F(K_r), R_1,\ldots R_r)\\
\hat B &=& (\dot B_1, \ldots, \dot B_r, F(X), F(K_1),\ldots,F(K_r), R_1,\ldots R_r),\\
\end{eqnarray*}

where $R_i \leq F(K_i)$ is a rigid subgroup, in the sense that ${\rm Stab}_{\aut{F(K_i)}}(R_i)\leq \Inn{F(K_i)}$, for example $R_i = \bk{c_i}$ where $c_i$ is a C-test element as given in <cit.>. These are precisely the objects that Theorem <ref> is about.

Let $\beta \in \aut{F(X,K)}$ send $\hat A$ to $\hat B$ or fix $\hat B$. Then we have the following restrictions

* $\beta|_{F(X)} = \ad{w}\circ \alpha$, where $\alpha \in \aut{F(X)}$ and $w \in F(X,K)$, and

* $\beta|_{F(K_i)} = \ad{w_i}$ for some $w_i \in F(X,K)$.

By hypothesis $\beta$ maps $F(X)$ to a conjugate $w^{-1}F(X)w$ and similarly $\beta(F(K_i))={w_i}^{-1}F(K_i)w_i$. This implies that the restriction $\ad{w^{-1}}\circ\beta|_{F(X)}$ is given by an automorphism $\alpha: F(X) \to F(X) \leq F(X,K).$ This proves the first point.

For the second point, note that we also require that $\beta$ maps $R_i$ to a conjugate of $R_i$ since the restriction $\ad{w_i}\circ\beta|_{F(K_i)}$ is an automorphism of $\alpha_i$ of $F(K_i)$ and therefore $\ad{w_i}\circ\beta(R_i)=g_i^{-1}R_ig_i$ for some $g_i \in F(K_i)$. The hypothesis that $R_i$ is rigid implies that $\ad{w_i}\circ\beta|_{F(K_i)}$ actually restricts to an inner automorphism on $F(K_i)$. This proves the second point.

§.§.§ From a solution in $F(X)$ to a solution in $F(X,K)$

If there is an $\alpha \in \aut{F(X)}$ such that $[\alpha(A_i)] =   [B_i]$

then there is an automorphism $\beta \in \aut{F(X,K)}$ such that
\[
\beta(\hat A)=\hat B.
\]

The $\alpha$ given in the hypothesis extends to an automorphism $\hat\alpha$ of $F(X,K)$ that fixes the elements of the free factor $F(K)$ elementwise. Let $w_i \in F(x)$ be the elements such that $w_i\alpha(A_i)w_i^{-1} = B_i$.

The conjugacy class $[\dot A_i]$ corresponds to the (unbased) tuple graph $\StalGraph{A_i}=\StalGraph{\dot A_i}$. Denote by $v_{i1},\ldots,v_{in_i}$ the vertices that are the basepoints of the based subgraphs $\BasedStalGraph{A_{ij}}{v_{ij}} \subset \StalGraph{A_i}$ coming from the entries $A_{ij}$ of the tuple $A_i$. Every edge of $\StalGraph{A_i}$ with a label in $X$ lies in one of these subgraphs. Applying $\hat\alpha$ to $\StalGraph{A_i}$ is achieved by subdividing every edge with label $x \in X$ to an appropriately oriented path with label $\alpha(x)$, leaving the edges  with label $K_i$ unchanged, and finally folding and coring. The same result can be achieved by tuple graph for $(\alpha(A_{i1}),\ldots,\alpha(A_{in_i}))$. This is not quite the target tuple we want, but we can remedy that by conjugating the special symbols the $K_i$ by the appropriate elements of $F(X)$. We achieve this with the automorphism $\beta' \in \aut{F(X,K)}$ that is defined on the basis $X\cup K$ as follows:
\[
\beta'(z) = \begin{cases}
z & \textrm{if~} z=x\in X\\
w_i z w_i^{-1} &\textrm{if~} z=\kappa_{ij} \in K_i
\end{cases}.
\]
The effect of first applying $\beta'$ to each $\hat\alpha(\StalGraph{A_i})$ and then folding and coring is depicted in Figure <ref>. Thus, taking $\beta = \beta'\circ\hat\alpha$, we have $[\beta(\dot A_i)]= [\dot B_i]$. Furthermore it is immediate from the construction that $\beta$ maps $F(X)$ to itself and the restrictions $\beta|_{F(K_i)}(g) = \ad{w_i^{-1}}(g)$. So, in particular, $\beta$ maps the $F(K_i)$ to themselves and the subgroups $R_i$ to conjugates in $F(X,K)$.

The effect of applying $\beta'$ to $\hat\alpha(\StalGraph{A_i})$, shown in four steps. Each arrow is a continuous map, we use the same notation to designate a vertex and its image.

§.§.§ From a solution in $F(X,K)$ to a solution in $F(X)$

Before stating and proving Proposition <ref>, let us prove a lemma about foldings.

Let $\calG$ be a directed graphs with labels in $X\cup K$ that is constructed as follows. Take some $K_i$-star, whose vertices of valence 1 are denoted $u_1,\ldots,u_{n_i}$. Then take a disjoint union of directed graphs with basepoints $(\calG_1,v_1),\ldots,(\calG_{n_i},v_{n_i})$ with labels in $X$, all of which have non-trivial fundamental group. Also take $n_i$ copies of some path (a directed labelled graph homeomorphic to a line segment) $\gamma$ with labels in $X\cup K$ with initial vertex $u_\gamma$ and terminal vertex $v_\gamma$. Suppose furthermore that the word read along $\gamma$ is reduced. Finally from $\calG$ by joining each $\calG_i$ to the $K_i$-star by a copy of $\gamma$ by identifying $u_i$ with the copy of $u_\gamma$ and the copy of $v_\gamma$ with $v_i$. See Figure <ref>

If $\gamma$ contains any edges with a label that is not in $X$, then $\calG$ cannot be brought to a unbased core graph that is the tuple graph of some tuple $(H_1,\ldots,H_{n_i})$ of subgroups of $F(X)$ by a sequence of folds or coring operations.

Let the word read along $\gamma$ as we read from $u_\gamma$ to $v_\gamma$ be written as
\[z_1\cdots z_r,\]
where $z_i \in (X\cup K)^{\pm 1}$. Suppose towards a contradiction that some $z_i \not\in X^{\pm 1}$ but that $\calG$ after folding and coring can be brought to the tuple graph of some tuple of subgroups of $F(X)$.

Without loss of generality we can assume that the last symbol $z_r$ read along $\gamma$ lies in $K$. Indeed we are supposing that there is some symbol labelling an edge of $\gamma$ that is in $K$. We can redefine the graphs $(\calG_1,v_1)$, by adjoining the maximal terminal segments of the copies of $\gamma$ only containing symbols from $X$ and redefining $\gamma$ so that it is the minimal initial segment containing all symbols in $K$. The resulting graph is exactly the same. One of the properties of a tuple graph is that the only edges with labels in $K$ are the ones contained in the $K_i$-star. By hypothesis, the paths that are copies of $\gamma$ contain edges with labels in $K$, there must therefore be some folding to identify all of these edges with the edges in the $K_i$-star.

We start by performing folds within the graphs $\calG_i$. Since the terminal edge in $\gamma$ has a label in $K$, there is no possible folding between the edges in the $\calG_i$s and edges in terminal segments of copies of $\gamma$. We may then proceed to coring. At this point we can now assume that the only possible foldings occur between the initial edge of some copy of $\gamma$ and some edge of the $K_i$-star.

Without loss of generality we may assume that $z_1 = \kappa_{in_i}^{-1}$ and this means that at this point there is at most one pair of edges that can be folded. We will now consider the folding process step-by-step. Denote by $\gamma_i$ the copy of $\gamma$ attached to $u_i$, then we first fold the first edge of $\gamma_{n_i}$ with the edge of the $K_i$-star labelled $\kappa_{in_i}$. If there are no other possible folds then the resulting graph is not a tuple graph as required, so we must continue folding. Without loss of generality $z_1=\kappa_{i1}$, and the terminal segment of $\gamma_{n_i}$ starts being partially identified with an initial segment of $\gamma_1$ this gives equalities

\begin{equation}\label{eq;gamma-fold}
z_3=z_1, z_4=z_2,\ldots
\end{equation}

for each edge of $\gamma_{n_i}$ that gets folded with an edge of $\gamma_1$. Note, however, that (<ref>) implies that if $\gamma^+$ is the initial segment of $\gamma_{1}$ consisting of edges that get identified with edges of $\gamma_{n_i}$. If $\gamma^+$ has label
\[
z_1\cdots z_\ell
\]
then we have
\[
z_i = \begin{cases}
{\kappa_{in_i}}^{-1} & \textrm{if $i$ is odd}\\
\kappa_{i1} & \textrm{if $i$ is even.}
\end{cases}\]

for all $1\leq i\leq \ell+2$. Furthermore by choice of $\ell$ we must have that $z_{\ell+3} \neq z_{\ell+1}$, which includes the possibility that $z_{\ell+3}$ does not exist (which would happen if the terminal segment of $\gamma_{n_i}$ completely folded into $\gamma_1$ and $|\gamma|=\ell+2$.)

Suppose now that we have folded up to identifying the $\ell^{\mathrm{th}}$ edge in $\gamma_1$ (labelled by $z_\ell$) up with the $(\ell+2)^{\mathrm{th}}$ edge of $\gamma_{n_i}$. There are two possibilities:

* If $z_{\ell+3}$ exists, i.e. $|\gamma|\geq \ell+3$, then there are no more possible folding operations and the resulting graph cannot be the a tuple graph (see Figure <ref>).

* If $z_{\ell+3}$ does not exist, i.e. the terminal segment of $\gamma_{n_i}$ has completely folded into $\gamma_1$, then we are in a situation where the graph obtained by folding and coring $\calG_{n_i}$ is attached to a vertex in $\gamma_1$ between edges with labels $z_\ell$ and $z_\ell+1$, both of which lie in $K^{\pm 1}$, and there is no more possible folding. The resulting graph cannot be a tuple graph either.

In all cases we arrive at a contradiction so the result holds.

The possibly unfolded graph $\calG$ of Lemma <ref> and attempting to fold it down to a tuple graph. The thickened segment represents the edges that got folded with edges of $\gamma_{n_i}.$

We may now prove the main proposition of this subsection.

Let $A, B$ be two tuples of conjugacy classes of tuples of subgroups of the free group $F(X)$, and let $F(X,K)$ be the extension as above, and $\dot A_i, \dot B_i$ the corresponding groups of tuple graphs (they are subgroups of $F(X,K)$).

Assume that $\beta \in \aut{F(X,K)}$ is such that

* $\beta(F(X)) = F(X)$,

* for all $i$, $[\beta(F(K_i))] = [F(K_i)]$ and $[\beta(R_i)]= [R_i]$,

* for all $i$, $[\beta(\dot A_i)] = [\dot B_i]$.

Then $\beta|_{F(X)}: F(X) \to F(X)$ is an automorphism that sends the $F(X)$-conjugacy class (of tuples of subgroups) $[A_i]$ to $[B_i]$.

Observe that  $\beta|_{F(X)}$ is indeed an automorphism of $F(X)$ by assumption.

Proving the proposition amounts to proving that the element that conjugates $\beta(\dot A_i)$ to
$\dot B_i$ can be taken in $F(X)$.

For each index $i$, there is a right coset $F(K_i)x_i$  such that $\beta(F(K_i))= F(K_i)^{x_i} $.

By rigidity property of $R_i$, one has actually an element $ k_i \in F(K_i)$ such that, for all index $j$, $\beta(\kappa_{ij}) = \kappa_{ij}^{k_ix_i}$. Let us write $w_i=k_ix_i$.

Applying Lemma <ref> to $\gamma = w_i$ and $\calG=\StalGraph{B_i}$, we obtain that    $w_i\in F(X)$.

It is therefore sufficient to prove that  $\beta(\dot A_i)= (\dot B_i)^{w_i}$.
This is the next lemma.

$\beta(\dot A_i)= (\dot B_i)^{w_i}$.

Knowing that $w_i\in F(X) $, we can consider the image of $\dot A_i$: it is generated by the groups $w_i^{-1}\kappa_{ij}w_i\beta(A_j) w_i^{-1}\kappa_{ij}^{-1} w_i$. We also know that $\beta(A_j) <F(X)$ since $\beta$ preserves $F(X)$.

Let $g_{i,j,k}$ ($k$ ranging in some set $S_{i,j}$) be generators of $w_i^{-1}\kappa_{ij}w_i\beta(A_j) w_i^{-1}\kappa_{ij}^{-1} w_i$.

All the considered generators $g_{i,j,k}$  are in $F(X)^{\kappa_{ij}^{-1} w_i}$ (for various $j$).  Foldings in the word $g_{i,j,k} (\neq 1)$ will never cancel the two letters
$\kappa_{ij}$ and $\kappa_{ij}^{-1}$ since all other letters are in $X$, and thus reveals a common prefix $w_i^{-1}$ and suffix $w_i$.

Conjugating  $\beta(\dot A_i)$ by $w_i^{-1}$ produces a group generated by the $\kappa_{ij} C_{ij} \kappa_{ij}^{-1}$  (for $j$ ranging in the indices of the tuple $A_i$) with $C_{ij} <F(X)$.
We must show that the generated group is $\dot B_i$.

By assumption on $\beta$, each $\kappa_{i,j} C_{ij} \kappa_{i,j}^{-1}$  must be in a conjugate of $\dot B_i$ and their union generate this conjugate. Thus, let $y$ be such that for all $j$,  $ C_{ij}^{\kappa_{ij}^{-1}y^{-1}} <\dot B_i$, and the union (over $j$) generate $\dot B_i$.

Recall that by convention,  there are at least two indices $j$ in the tuple $A_i$. Write $y$ as a reduced word over $X\cup K$, and select $j$ such that $y\kappa_{ij}$ is reduced (there exists such $j$). Then considering reduced words $c\in C_{ij}$ (in $X$ only), the  words $y\kappa_{ij}c\kappa_{ij}^{-1}y^{-1}$ are reduced and are all in $\dot B_i$. Folding them on the graph $\StalGraph{B_i}$, it easily follows that $y\in \dot B_i$ (i.e. its folding finishes back to the vertex $v_i$, the only vertex on which the next edge labelled $\kappa_{ij}$ can fold). Hence  $ C_{ij}^{\kappa_{ij}^{-1}} <\dot B_i$, and the union over $j$ generate $\dot B_i$. In other words  $\beta(\dot A_i) =(\dot B_i)^{w_i}$, which we wanted to show.

Propositions <ref> and <ref>  make the following an application of Gersten's theorem <ref> (first point).

Let $F$ be a free group, then given two tuples of conjugacy classes of tuples of finitely generated subgroups, one can decide whether an automorphism of $F$ sends the first to the second.

§.§.§ From generators of stabilizers in $\aut {F(X,K)}$ to generators of stabilizers in $\aut{F(X)}$

Let $B$ be a tuple of conjugacy classes of tuples of subgroups of the free group $F(X)$, and let $F(X,K)$ and $\hat B$ the extensions as above ($\hat B$ is a tuple of conjugacy classes of subgroups).

We are interested in $\SAFXKB$

(which we can compute by Theorem <ref>), and its relation with  $\SAFB$.

As an auxiliary tool, we will consider
\[\SSABFX
%= {\rm Stab}_{{\rm Stab}_{\aut{F(X,K)}}(\hat B)}(F(X))

Let $B$ be a tuple of conjugacy classes of tuples of subgroups of the free group $F(X)$, and let $F(X,K)$ and $\hat B$ the extensions as above ($\hat B$ is a tuple of conjugacy classes of subgroups).

Let $\{\beta_j, \;  j\in J \}$ be a generating set of $\SAFXKB$, that contains the elements ${\rm ad}_x, x\in X$.

Then for all $j\in J$, there exists $\gamma_j \in F(X,K)$ such that

\[{\rm ad}_{\gamma_j} \circ \beta_j \in \SSABFX   < \SAFF, \]

and $\{ {\rm ad}_{\gamma_j} \circ \beta_j,\; j\in J\}$ is a generating set of

Observe that the condition that the given generating set contains the elements ${\rm ad}_x, x\in X$ is not restrictive since all these automorphisms preserve trivially $\hat B$, since the later is a tuple of conjugacy classes.

By definition of $\hat B$, the automorphisms of $F(X,K)$ preserving $\hat B$ must preserve the conjugacy class of $F(X)$.
Therefore there exists $\gamma_j$ such that ${\rm ad}_{\gamma_j} \circ \beta_j \in \SAFF$.

We way take $\gamma_j = 1$ for all the $\beta_j$ that are of the form ${\rm ad}_x, x\in X$.

Moreover, as we recalled, all inner automorphisms of $F(X,K)$ preserve trivially $\hat B$. It follows that

\[{\rm ad}_{\gamma_j} \circ \beta_j \in \SSABFX
%    {\rm Stab}_{{\rm                Stab}_{\aut{F(X,K)}}(\hat B)}(F(X))
< \SAFF. %{\rm Stab}_{\aut{F(X,K)}}(F(X)).
\]

It remains to prove that the obtained automorphisms $\{ {\rm ad}_{\gamma_j} \circ \beta_j, \; j \in J \}$ generate the group

Let $\alpha_j =  {\rm ad}_{\gamma_j} \circ \beta_j$, to ease notations.

Consider an element  $w$ of $\SSABFX $.

Since $\{\beta_j, \;  j\in J \}$ is a generating set of $\SAFXKB$,
we may write $w$ as
\[w = \beta_{a_1}\beta_{a_2} \dots \beta_{a_s}\]
with $a_i \in J$ for all $i$. Consider than $w' = \alpha_{a_1}\alpha_{a_2} \dots \alpha_{a_s} $. Substituting $\alpha_{a_i}$ by ${\rm ad}_{\gamma_{a_i}} \circ \beta_{a_i}$ and rearranging, it is elementary that there exists $\gamma$ such that $w' = {\rm ad}_\gamma \circ w$.

On one hand, $w'(F(S)) = F(S)$ because it is a composition of the  $\alpha_j$. On the other hand, $w(F(S)) = F(S)$ by assumption on $w$. It follows that $ {\rm ad}_\gamma$ preserves $F(S)$. However, since $F(S)$ is malnormal in $F(S,K)$, we can conclude that $\gamma \in F(S)$.

Since ${\rm ad}_x, x\in X$ are elements of the given generating set,  by our choice of $\gamma_j$, they are also elements of  $\{ \alpha_j, \; j\in J\}$. It is therefore possible to write
${\rm ad}_\gamma$ as a word in the $\alpha_j$, and finally ${\rm ad}_{\gamma^{-1}}  \circ w' \in \langle \alpha_j, \; j\in J \rangle$.  Since ${\rm ad}_{\gamma^{-1}}  \circ w' = w$ we have proved that $w\in \langle \alpha_j \; j\in J \rangle$.

We therefore have established the equality
\[\SSABFX
%{\rm Stab}_{{\rm Stab}_{\aut{F(X,K)}}(\hat B)}(F(X))
=  \langle \alpha_j \; j\in J \rangle.\]

Observe now the following.

If  $w\in \SSABFX$,

\[w|_{F(X)} \in \SAFB.\]

If $w_0 \in \SAFB$,

then there exists
$w\in \SSABFX$,

for which $w|_{F(X)} = w_0$.

The first part is a rewriting of the definitions, and for the second part, extend $w_0$ as the identity on $K$.

Given $B$ as in  Proposition <ref>, a generating set of the group  $\SAFB$

is computable.

Construct $F(X,K)$ and $\hat B$, compute, by Gersten's theorem <ref> a generating set of  $ \SAFB$,

apply Proposition <ref>, this provides, by Lemma <ref>  a generating set of  $\SAFB$.

By Corollary <ref>, and Corollary <ref>, we obtain Theorem <ref>, as promised.

§ EFFECTIVELY MINKOWSKIAN SUBGROUPS

If $G$ is a group and $P$ is a characteristic subgroup of $G$ (i.e. invariant by automorphisms of $G$), we write $P\charsgp G$.

If $P_0$ is a finite index subgroup of a finitely generated group $G$, it is easy to construct an associated characteristic finite index subgroup, by taking the intersection of all the (finitely many) subgroups of $G$ of same index as $P_0$.

Let $P \charsgp G$ be a finite index characteristic subgroup. We
say $P$-congruences separate the torsion of $\out G$ (or
that $P$ is Minkowskian in $G$), if every finite order outer automorphism
$[\alpha] \in \out G$ has non-trivial image $[\bar\alpha]$ through the
natural map
\[ \out G \to \out{G/P}.
\]

A class of groups is effectively Minkowskian if each group admits a Minkowskian finite index subgroup, that is computable from a presentation.

A subgroup $P\charsgp G$ as in the definition above is called a Minkowskian subgroup and a quotient $G/P$ by a Minkowskian subgroup is called a Minkowskian quotient.

The proposed  terminology comes from a classical theorem of Minkowski: if $p\geq 3$, the kernel of the quotient $GL_n(\mathbb{Z}) \to GL_n(\mathbb{Z}/p\mathbb{Z})$ is torsion free. In other words $(3\mathbb{Z})^n$ is  Minkowskian in $\mathbb{Z}^n$, and free abelian groups form an effectively Minkowskian class.

The following is a useful remark.

If $P \charsgp G$
and $H\charsgp P$ is  a
characteristic subgroup of $P$, then
$H \charsgp G$ and  if   $P$-congruences separate the torsion in $\out G$, then $H$-congruences separate the torsion in $ \out G$.

Any automorphism of $G$ induces an automorphism of $P$, hence preserves $H$.
There is a natural map $\out{ G/H} \to \out {G/P}$ which commutes with $\out G\to \out {G/P}$.  Any  finite order outer automorphism of $G$ survives in $\out {G/P}$, hence also in $\out {G/H}$.

The aim of this section is to prove the following.

Finitely generated subgroups of piecewise trivial suspensions of free groups, are effectively Minkowskian.

Recall that we have two levels of decomposition for such a group, from top to bottom:

* the Grushko decomposition in free product,

* for each freely indecomposable free factor,  the canonical decomposition given by Corollary <ref>:
an  acylindrical  bipartite  graph-of-groups with  edge groups either cyclic or isomorphic to $\bbZ^2$,  and white vertex groups that are either finitely generated free or direct product of finitely generated free groups with an infinite cyclic group (a trivially partially suspended canonical decomposition).

By Proposition <ref> such decompositions can be found effectively. In order to prove Theorem <ref> we will show the two following theorems.

A free product of  freely indecomposable, residually finite,  effectively Minkowskian, torsion-free groups  and free groups is effectively Minkowskian.

Any freely-indecomposable group that has a  trivially partially suspended canonical decomposition, as defined above, is effectively Minkowskian.

In the free product case, we will use Hensel and Kielak's version of the Nielsen realisation theorem for free products: a finite order automorphism of a free product is realised as a graph-of-group automorphism that takes advantage of a symmetry of a certain graph of groups, and induces finite order outer automorphisms of the fixed vertex groups.

In the one-ended case (Theorem <ref>), this is more involved.  We will first construct a clean covering of the given graph of groups, inspired by <cit.>. The cover will be taken to be characteristic, so that automorphisms of the ambient group $\Gamma$ induce automorphisms of the finite-index subgroup $\Xi$  associated to the cover.

Then we will take a quotient of $\Xi$, that we will call a vertex filling, to obtain a virtually free group $V$, which is a graph of finite groups over the same underlying graph, in which sufficiently many witnesses of the non-triviality of the finite order outer-automorphisms will have survived.

Finally, we will take a quotient of $V$ to a finite group $Q_0$, in which all the conjugacy classes of finite order elements remain disjoint. By studying the images of the of witnesses in the induced quotient $Q$ of $\Gamma$, we will finally establish that $Q$ is in fact a  Minkowskian quotient, thus giving us the desired result.

§.§ Effective Minkowskian property for Free products

In this section, we prove Theorem <ref>. Let $G_1, \dots, G_k$ be non-trivial, torsion-free  freely indecomposable groups that are effectively Minkowskian and residually finite.
The group $L_r$ is a free group of rank $r$. We consider the free product $\Gamma = G_1 *G_2 \dots G_k*L_r$.

There exists a finite list of finite quotients of $\Gamma$ such that,
for each automorphism $\alpha$ of $\Gamma$ that is non-trivial in $\out \Gamma$ and  has finite order in $\out \Gamma$, there is $\alpha'$ conjugate to $\alpha$ in $\out \Gamma$, a finite quotient $\Gamma \to \bar \Gamma$ in the list,  whose kernel is preserved by $\alpha'$, and on which $\alpha'$ descends as an automorphism $\bar {\alpha'} \in \aut{\bar \Gamma}$ whose outer class is non-trivial (in $\out{\bar \Gamma}$).

We will distinguish several cases according to the properties of $\alpha$. First observe that $\alpha$ must permute (and can possibly preserve) the conjugacy classes of the groups $G_i$. For each $i$, let $G_i \to \overline{G_i}^{M}$ be a Minkowskian finite quotient.

If there is an index $i\leq k$, and $\gamma_i \in \Gamma$ such that $\alpha(G_i)^{\gamma_i} = G_i$, and if $ {\rm ad}_{\gamma_i} \circ \alpha|_{G_i}: G_i \to G_i$ defines a non-trivial outer automorphism of $G_i$, then the quotient
\[\Gamma \to G_i \to \overline{G_i}^{M}\]
satisfies the conclusion of Proposition <ref> for $\alpha$.

Observe that $ {\rm ad}_{\gamma_i} \circ \alpha$ is the same outer class than $\alpha$, hence has finite order in $\out \Gamma$. It follows that in restriction to $G_i$ (that it preserves) it has finite order up to conjugation by an element normalising $G_i$, thus in $\out{G_i}$. By assumption, it is non-trivial. Applying the Minkowski property for $G_i$, it survives in the quotient $\overline{G_i}^{M}$.

In the next lemma, consider for each $i$ a non-trivial finite finite quotient by a characteristic subgroups $G_i \to \bar{G_i}^c$. This exists by residual finiteness, and one chooses them so that $ \bar{G_i}^c \simeq \bar{G_j}^c$ if and only if $G_i\simeq G_j$.

Construct the free product quotient of $\Gamma$:
\[ \Gamma \to \overline{\Gamma}^{vf} \; = \;\bar{G_1}^c*\bar{G_2}^c*\dots \bar{G_k}^c*L_r.\]

Observe that $\overline{\Gamma}^{vf}$ is virtually free. Make the further quotient to a finite group
\[\overline{\Gamma}^{vf} \to \overline{\Gamma}^{dp}   \; = \; \bar{G_1}^c\times \bar{G_2}^c \times \dots \bar{G_k}^c.\]

Let $\alpha$ be an automorphism of $\Gamma$ with an index $i$  for which  for which $[\alpha(G_i)] \neq [G_i]$. Then $\alpha$ descends to the quotient  $\overline{\Gamma}^{dp}$ as a non-trivial outer automorphism.

First it is clear that all automorphisms of $\Gamma$ descend to $\overline{\Gamma}^{dp}$.
Let $g_i \in G_i$ that survives in $ \bar{G_i}^c$. Then $\bar \alpha$ sends $\bar g_i$ to a non-trivial element of another direct factor, hence a non-conjugate element; this proves the claim.

From now on,  $\alpha$ is an automorphism of $\Gamma$ that is non-trivial in $\out \Gamma$, and of finite order in $\out \Gamma$, and such that, for all indices $i$, there exists $\gamma_i \in \Gamma$ for which ${\rm ad}_{\gamma_i} \circ \alpha|_{G_i}: G_i \to G_i$ is the identity of $G_i$.

To make sense such $\alpha$ we need the following statement.

There are only finitely many conjugacy classes of elements as given in Convention <ref> in $\out \Gamma$.

Moreover, for each such $\alpha$, there exists $L'_r<\Gamma$ and $\gamma\in \Gamma$  such that
* $\Gamma$ splits as a free product $G_1*\dots G_k*L'_r$,
* $\ad{\gamma} \circ \alpha (L'_r) = L'_r$

* $\ad{\gamma} \circ \alpha|_{L'_r}$ is non-trivial and of finite order in $\out{L'_r}$.

By <cit.> all such outer-automorphisms must fix a baricenter of a simplex in the relative outer-space of the free product. In other words,  the group   $\Gamma$ splits as a graph of group with trivial edge groups and infinite vertex groups that are conjugate to $G_i$, in such a way that $\alpha$ induces an automorphism of graph of groups.

This allows us to write an element  $\ad{\gamma} \circ \alpha$ of the outer-class of  $\alpha$, as a graph-of-group automorphism of some fixed free splitting graph of groups $\bbX$. Let it be  $\ad{\gamma} \circ \alpha = (\alpha_X, \alpha_v, \alpha_e, \gamma_e)$. By assumption on $\alpha$, one may take $\alpha_v = Id$ for all vertices, and $\alpha_e = Id$ for all edges as well.  Also, the graph automorphism $\alpha_X$ must induce the trivial permutation on the non-free vertices of the graph (i.e. those that are attached to a non-trivial group).

Write  $\ad{\gamma} \circ \alpha = \alpha'$ to ease notation.

It follows that $(\alpha')^s = (\alpha_X^s, (Id_v)_v, (Id_e)_e, (\gamma_e^s)_e )$. Since $\gamma_e$ has infinite order,[The result would hold with little modification if each free factor of $\Gamma$ had only finitely many torsion elements  – in particular for the free product of finite groups]

if $[\alpha^m] =[Id]$, then $\gamma_e = 1$.

Thus $\ad{\gamma} \circ \alpha = (\alpha_X, Id_v, Id_e, 1)$. Let $L'_r$ be the free factor of $\pi_1(\bbX, v_0)$ defined by the graph $X$. We see that $L'_r$ is preserved by $\alpha'$, and that $\alpha'$ indces a finite order automorphism of $L'_r$, which is non-trivial in $\out{L'_r}$ (otherwise $\alpha'$ would be  trivial in $\out \Gamma$.

It follows that there cannot be more conjugacy classes of automorphisms $\alpha$ (in $\out \Gamma$) than the number of orbits of cells in the relative outer space multiplied by the maximal order of graph automorphism groups of thus appearing graphs.

We may thus proceed to analyse the automorphisms $\alpha$ satisfying Convention <ref> one by one.

If $\alpha$ is an automorphism satisfying Convention <ref>, then there exists a finite quotient of $\Gamma$ in which $\alpha$ descends as a non-trivial outer-automorphism.

Taking the notations of the previous lemma, it suffices to notice that there is a finite quotient of $L'_r$ on which $\alpha'$ descends as a non-trivial outer-automorphisms. This is the Minkowskian property for free groups, proved in <cit.>

We thus showed Lemma <ref>  that all automorphisms satisfying the convention <ref> are separated in a finite quotient, and Lemma <ref>, that there are only finitely many conjugacy classes of them. We also showed (Lemma <ref>,  <ref>) that there are finitely many finite quotient separating all finite order outer automorphisms that do not satisfy the convention.

Proposition <ref> is thus established.

It is therefore sufficient to prove the following, in order to obtain Theorem <ref>. Let $\alpha \in \out \Gamma$ and let $K\leq \Gamma$ be a finite index subgroup. If $\alpha([K])=[K]$ and $\alpha$ descends to a non-trivial outer automorphism of $\Gamma/K$ then we say $K$ separates $\alpha$.

If $K_1$ separates $\alpha_1$ and $K_2$ separates $\alpha_2$, then there is a subgroup $K$ that separates both $\alpha_1$ and $\alpha_2$.

We will consider $K$ to be the intersection of all images of $K_1 \cap K_2$ by automorphisms (it is a finite intersection of subgroups sharing the same index in $\Gamma$). To show that $K$ is as required, we need examine to how $\alpha_1$ survives in $\Gamma/K$. First it induces an automorphism of $\Gamma/K$ since the quotient is characateristic. Second, $\Gamma/K_1$ is a quotient of $\Gamma/K$ on which $\alpha_1$ descends non-trivially non-trivially as an outer autorphism, thus it cannot be a trivial outer automorphism in $\Gamma/K$.

§.§ Effective Minkowskian property for one-ended groups with canonical splittings.

In this section we consider the  Minkowskian property for groups for which a canonical decomposition as a graph-of-groups $\bbX$ is given. In that case, all outer automorphisms can be expressed as elements of $\delta \aut \bbX$, thus we clarify a possible congruence strategy to separate the torsion in  $\delta \aut \bbX$.

§.§.§ From graphs-of-groups to vertex groups

The following Proposition isolates two origins of torsion in  $\delta \aut \bbX$, either witnessed by permuting vertices, or by restring to a non-trivial finite order outer automorphism of a vertex group.

Let $\Gamma$ be the fundamental group of a

graph of group $\bbX$, and let $\phi = (\phi_X, (\phi_v)_v, (\phi_e)_e, (\gamma_e)_e \in \delta \aut \bbX$ be non-trivial and of finite order in $\out \Gamma$. Suppose furthermore that for each non-abelian vertex group $\bbX_v$, the quotient by its center is torsion free.

Then if $\phi_X = Id$, for at least  one vertex $v$, $\phi_v$ defines a non-trivial, finite order element in $\out{\bbX_v}$.

Assume the contrary: all $\phi_v$ must be of the form ${\rm ad}_{g_v}$.
We choose a prefered vertex $v_0$, with non-abelian vertex group,  and identify $\Gamma$ with $\pi_1(\bbX, v_0)$. After composition with an inner automorphism of   $\Gamma$, we may assume that  $g_{v_0} =1$, that is $\phi_{v_0} = Id$.

Since $\phi_X $ is the identity, in the Bass group each edge $e$ is sent, by $\phi$,  on $\gamma_{\bar e}^{-1} e \gamma_e$.

If we choose $\tau $ a maximal subtree of $X$, one may change the expression of $\phi$ without changing its image in $\out \Gamma$, so that, for each edge $e$ in $\tau$ pointing outward from  $v_0$, the element $\gamma_e$ is trivial. To see this,  enumerate the edges in $\tau$ respectively to the distance to $v_0$ and modify iteratively as follows:  for a given $e$,  change   $\gamma_e$ by $1$, change    $g_{\tau(e)}$ by $ g_{\tau(e)}\gamma_e^{-1}$, and all  $\gamma_{\bar e'}$ for $e'$ exiting $\tau(e)$ by $ \gamma_{\bar e'} \gamma_e^{-1} $ (this was already done for $e' = \bar e$ !). It is an immediate computation to see that the Bass diagrams are satisfied, and the automorphism on $\Gamma= \pi_1(\bbX, v_0)$ is the same.
(For that, note that, in the Bass group, the element $ehe'$ is sent on $\gamma_{\bar e}^{-1} e \gamma_e g_{\tau(e)}^{-1}\,  h\,  g_{\tau(e)}   \, \gamma_e^{-1} \gamma_e \,  \gamma_{\bar e'}^{-1} e' \gamma_{e'} $.)

If all $\phi_v$ are the identity, then, since all the $\gamma_e$ are trivial or have infinite order, it follows that $\phi$ is trivial or has infinite order.

Consider $v_1$ closest to $v_0$ (in $\tau$) such that $\phi_{v_1}$ is not the identity. It is ${\rm ad}_{g_{v_1}}$ for some $g_{v_1}$ non-central in $\bbX_{v_1}$ (in particular $\bbX_{v_1}$ is non-abelian). By assumption, no power of $g_{v_1}$ is central. Let $p=e_1\dots e_k$ be a path from $v_0$ to $v_1$ in $\tau$, and consider
\[\gamma(g) = g_0 e_1 \dots e_k g \bar e_k \dots \bar e_1 g'_0\]
for $g\in \bbX_{v_1}$, and $g_0, g'_0$ not in adjacent edge groups and not inverse of each other (which is possible by choice of $v_0$).

Using that $\gamma_{e_i}=1$, one can compute that  the image of $\gamma(g)$ by $\phi^n$ is

\[\phi^n(\gamma(g)) \; = \;  g_0  \, x_{1,n} \, e_1 \, x_{2, n} \, e_2 \dots x_{k,n} e_k  %\gamma_{e_k}^n
\, g^{g_{v_1}^n} % \gamma_{e_k}^{-n}  ...
\, \bar e_k \,  x_{k,n}^{-1} \, \bar e_{k-1} \dots   x_{1,n}^{-1} \,  g'_0  \]

where the $x_{i, n} =( \gamma_{\bar{e_i}})^{-n}$ are in the vertex group $\bbX_{\tau(e_{i-1})}$.

For all $n$, $ g_{v_1}^{n}$ is, by assumption, non-central in its vertex group, therefore  we may find
$g$ outside the centraliser of $g_{v_1}^{n}$,
so that
$ %\gamma_{e_k}^n
g^{g_{v_1}^n} %\gamma_{e_k}^{-n}
$ is different from $g$.  It follows that, since the expression of $\phi^n(\gamma(g))$ is in normal form,

that $\phi^n$ is non trivial. Since it is trivial on $\bbX_{v_0}$, but non-trivial on $\bbX_{v_1}$ it is non-trivial in $\out \Gamma$. This is in contradiction with the assumption that $\phi$ has finite order.