On the dynamics of endomorphisms of the direct product of two free groups

For $(i,j)\in[n]\times[m]$, we define $\lambda_{i}:F_{n}\to\mathbb{Z}$ as the endomorphism given by $a_{k}\mapsto\delta_{ik}$ and $\tau_{j}:F_{m}\to\mathbb{Z}$ given by $b_{k}\mapsto\delta_{jk}$, where $\delta_{ij}$ is the Kronecker symbol.

For $x\in F_{n},y\in F_{m}$ and integers $p_{i},q_{i},r_{j},s_{j}\in\mathbb{Z}$, we denote $\sum\limits_{i\in[n]}\lambda_{i}(x)p_{i}$ by $x^{P}$; $\sum\limits_{j\in[m]}\tau_{j}(y)r_{j}$ by $y^{R}$; $\sum\limits_{i\in[n]}\lambda_{i}(x)q_{i}$ by $x^{Q}$ and $\sum\limits_{j\in[n]}\tau_{j}(y)s_{i}$ by $y^{S}$. We also define $P=\{p_{i}\in\mathbb{Z}\mid i\in[n]\}$, $Q=\{q_{i}\in\mathbb{Z}\mid i\in[n]\}$, $R=\{r_{j}\in\mathbb{Z}\mid j\in[m]\}$ and $S=\{s_{j}\in\mathbb{Z}\mid j\in[m]\}$. We will keep this notation throughout the paper.

In [10], the author classified endomorphisms of the direct product of two finitely generated free groups $F_{n}\times F_{m}$, with $m,n>1$ in seven different types:

1. (I)

   $(x,y)\mapsto\left(u^{x^{P}+y^{R}},v^{x^{Q}+y^{S}}\right)$, for some $1\neq u\in F_{n}$, $1\neq v\in F_{m}$ and integers $p_{i},q_{i},r_{j},s_{j}\in\mathbb{Z}$ for $(i,j)\in[n]\times[m]$, such that $P,Q,R,S\neq\{0\}$.

2. (II)

   $(x,y)\mapsto\left(y\phi,v^{x^{Q}+y^{S}}\right)$, for some nontrivial homomorphism $\phi:F_{m}\to F_{n}$, $1\neq v\in F_{m}$ and integers $q_{i},s_{j}\in\mathbb{Z}$ for $(i,j)\in[n]\times[m]$, such that $Q,S\neq\{0\}$.

3. (III)

   $(x,y)\mapsto\left(u^{x^{P}+y^{R}},y\phi\right),$ for some nontrivial endomorphism $\phi\in\text{End}(F_{m})$, $1\neq u\in F_{n}$, and integers $p_{i},r_{j}\in\mathbb{Z}$ for $(i,j)\in[n]\times[m]$, such that $P,R\neq\{0\}$.

4. (IV)

   $(x,y)\mapsto(y\phi,y\psi)$, for some nontrivial homomorphism $\phi:F_{m}\to F_{n}$ and nontrivial endomorphism $\psi\in\text{End}(F_{m})$.

5. (V)

   $(x,y)\mapsto\left(1,v^{x^{Q}+y^{S}}\right)$, for some $1\neq v\in F_{m}$, and integers $q_{i},s_{j}\in\mathbb{Z}$ for $(i,j)\in[n]\times[m]$, such that $Q,S\neq\{0\}$.

6. (VI)

   $(x,y)\mapsto(x\phi,y\psi)$, for some endomorphisms $\phi\in\text{End}(F_{n})$, $\psi\in\text{End}(F_{m})$.

7. (VII)

   $(x,y)\mapsto(y\psi,x\phi)$, for homomorphisms $\phi:F_{n}\to F_{m}$ and $\psi:F_{m}\to F_{n}$.

From [10, Proposition 3.2], injective endomorphisms correspond to endomorphisms of type VI or VII such that the component mappings $\phi$ and $\psi$ are injective. We denote by $\mbox{\rm Mon}(G)$ the monoid of monomorphisms of a group $G$. In [10, Corollary 3.3], it is shown that automorphisms of $F_{n}\times F_{m}$ are the type VI endomorphisms with bijective component endomorphisms $\phi$ and $\psi$ and if $n=m$, there are also automorphisms of type VII, given by the type VII endomorphisms with bijective component homomorphisms $\phi$ and $\psi$. Hence, groups of the form $F_{n}\times F_{n}$ have more automorphisms than groups of the form $F_{n}\times F_{m}$ with $n\neq m$. We will usually denote endomorphisms (and homomorphisms) of free groups by $\phi,\psi$ and endomorphisms of $F_{n}\times F_{m}$ by $\Phi,\Psi$.

Given an endomorphism by the image of the generators of $F_{n}\times F_{m}$, its type is decidable. Indeed, consider an endomorphism $\varphi:F_{n}\times F_{m}\to F_{n}\times F_{m}$ defined by $(a_{i},1)\mapsto(x_{i},y_{i})$ and $(1,b_{j})\mapsto(z_{j},w_{j})$ for $i\in[n]$ and $j\in[m].$ We define $X=\{x_{i}\mid i\in[n]\}$, $Y=\{y_{i}\mid i\in[n]\}$, $Z=\{z_{j}\mid j\in[m]\}$ and $W=\{w_{j}\mid j\in[m]\}$. We say that these sets are trivial if they are singletons containing only the empty word and nontrivial otherwise. As seen in [10], matching the numbering above the endomorphisms are classified as follows:

1. (I)

   All sets $X,Y,Z$ and $W$ are nontrivial

2. (II)

   $X$ is the only trivial set

3. (III)

   $Y$ is the only trivial set

4. (IV)

   $X$ and $Y$ are the only trivial sets

5. (V)

   $X$ and $Z$ are the only trivial sets

6. (VI)

   $Y$ and $Z$ are trivial sets

7. (VII)

   $X$ and $W$ are trivial sets

Therefore, when we take an endomorphism as input (meaning that we are given images of the generators), we will often assume that its type is known.

In this case, we have that $(x,y)\Phi=(u^{x^{P}+y^{R}},v^{x^{Q}+y^{S}})$, for some words $u,v\neq 1$. It is shown in [10, Subsection 5.1] that, defining sequences in $\mathbb{Z}$ by

$\displaystyle\begin{cases}a_{1}(x,y)=x^{P}+y^{R}\\ b_{1}(x,y)=x^{Q}+y^{S}\\ a_{n+1}(x,y)=a_{n}(x,y)u^{P}+b_{n}(x,y)v^{R}\\ b_{n+1}(x,y)=a_{n}(x,y)u^{Q}+b_{n}(x,y)v^{S}\end{cases},$

we have that, for every $k>0$, $(x,y)\Phi^{k}=(u^{a_{k}(x,y)},v^{b_{k}(x,y)})$. We want to decide, given $(x,y),(z,w)\in F_{n}\times F_{m}$, whether there is some $k\in\mathbb{N}$ such that $(x,y)\Phi^{k}=(z,w)$. Using Lemma 3.4 to decide if $z$ is a power of $u$ and $w$ is a power of $v$. If in any of the cases the answer is no, then we will not have a positive solution to our problem; if both answer yes, we compute exponents $(a,b)\in\mathbb{N}^{2}$ such that $(z,w)=(u^{a},b^{v})$.

So, for all $n\in\mathbb{N}$,

$$\begin{bmatrix}a_{n}\\ b_{n}\end{bmatrix}=\begin{bmatrix}u^{P}&v^{R}\\ u^{Q}&v^{S}\end{bmatrix}^{n-1}\begin{bmatrix}x^{P}+y^{R}\\ x^{Q}+y^{S}\end{bmatrix},$$

hence, putting $M_{\Phi}=\begin{bmatrix}u^{P}&v^{R}\\ u^{Q}&v^{S}\end{bmatrix}$, the problem can now be translated as the problem of deciding whether there is some $k\in\mathbb{N}$ such that

$$M_{\Phi}^{k}\begin{bmatrix}x^{P}+y^{R}\\ x^{Q}+y^{S}\end{bmatrix}=\begin{bmatrix}a\\ b\end{bmatrix},$$

which can be done by [24].

In the conjugacy case, we start by checking if $k=0$ is a solution to our problem by solving the conjugacy problem. If not, using Lemma 3.3, we check if $z$ is conjugate to a power of $u$ and $w$ is conjugate to a power of $v$. If in any of the cases the answer is no, then we will not have a positive solution to our problem; if both answer yes, we compute the unique exponents $(a,b)\in\mathbb{N}^{2}$ such that $(z,w)\sim(u^{a},b^{v})$. Then we simply check if there is some $k$ such that $(x,y)\Phi^{k}=(u^{a},v^{b})$ using the equality algorithm above.

In this case, we have that $(x,y)\Phi=(y\phi,v^{x^{Q}+y^{S}})$, for some word $v\neq 1$ and homomorphism $\phi:F_{m}\to F_{n}$. It is shown in [10, Subsection 5.2] that, defining a sequence in $\mathbb{Z}$ by

$\displaystyle\begin{cases}a_{1}(x,y)=x^{Q}+y^{S}\\ a_{2}(x,y)=a_{1}(x,y)v^{S}+y\phi^{Q}\\ a_{n}(x,y)=a_{n-1}(x,y)v^{S}+a_{n-2}(x,y)(v\phi)^{Q}\\ \end{cases}$

we have that, for every $k>1$, $(x,y)\Phi^{k}=(v^{a_{k-1}(x,y)}\phi,v^{a_{k}(x,y)})$. We start by checking if $k=1$ is a solution. Then, by Lemma 3.4 we test if $z$ is a power of $v\phi$ and if $w$ is a power of $v$. If one of them is not, then there is no solution $k$. If both are, we compute $a,b\in\mathbb{N}$ such that $(z,w)=(v^{a}\phi,v^{b})$. Our problem now becomes finding $k>0$ such that $\begin{bmatrix}b&a\end{bmatrix}=\begin{bmatrix}a_{k+1}(x,y)&a_{k}(x,y)\end{bmatrix}$. Similarly to the type I case, we use Kannan-Lipton’s algorithm to decide the existence of such a $k$. Consider the matrix $M_{\Phi}=\begin{bmatrix}v^{S}&(v\phi)^{Q}\\ 1&0\end{bmatrix}$. Clearly, for $k>0$,

$$M_{\Phi}\begin{bmatrix}a_{k+1}(x,y)\\ a_{k}(x,y)\end{bmatrix}=\begin{bmatrix}a_{k+2}(x,y)\\ a_{k+1}(x,y)\end{bmatrix},$$

and so

$$M_{\Phi}^{k}\begin{bmatrix}a_{2}(x,y)\\ a_{1}(x,y)\end{bmatrix}=\begin{bmatrix}a_{k+2}(x,y)\\ a_{k+1}(x,y)\end{bmatrix}.$$

By [24], we can decide if there is some $k$ such that

$$\begin{bmatrix}a_{k+2}(x,y)\\ a_{k+1}(x,y)\end{bmatrix}=M_{\Phi}^{k}\begin{bmatrix}a_{2}(x,y)\\ a_{1}(x,y)\end{bmatrix}=\begin{bmatrix}b\\ a\end{bmatrix},$$

and we are done.

The variation up to conjugacy is similar to the previous case: we first decide if $z$ is conjugate to some power of $v\phi$ and $w$ is conjugate to some power of $v$ and then apply the algorithm for equality.

We have that $(x,y)\mapsto\left(u^{x^{P}+y^{R}},y\phi\right)$, for some word $u\neq 1$ and endomorphism $\phi\in\text{End}(F_{m})$. It is seen in [10, Subsection 5.3] that

$$(u^{a},y)\Phi^{k}=\left(u^{a(u^{P})^{k}+\sum\limits_{t=0}^{k-1}(y\phi^{t})^{R}(u^{P})^{k-t-1}},y\phi^{k}\right).$$

We start by solving BrP($F_{n}$) to compute $p_{0},p_{1}\in\mathbb{N}$ such that $\phi\text{-}\log_{y}(w)=p_{0}+p_{1}\mathbb{N}$. If $p_{1}=0$, then $p_{0}$ is our only candidate, so the only thing to check is if $(x,y)\Phi^{p_{0}}=(z,w)$. If $p_{1}\neq 0$, $w$ is a $\phi$-periodic point with period $p_{1}$. We check if $z$ is a power of $u$. If it is not, then we are done, since there is no possible $k$; if it is, we compute $a\in\mathbb{N}$ such that $z=u^{a}$.

Now consider the following affine transformation of $\mathbb{Z}$

	$\displaystyle\Theta\colon\mathbb{Z}$	$\displaystyle\longrightarrow\mathbb{Z}$
	$\displaystyle c$	$\displaystyle\longmapsto c(u^{P})^{p_{1}}+\sum_{t=0}^{p_{1}-1}(w\phi^{t})^{R}(u^{P})^{p_{1}-t-1},$

and denote by $(a_{n})_{n}$ the sequence such that $(x,y)\Phi^{n}=(u^{a_{n}},y\phi^{n})$. Clearly, given $k\in\mathbb{N}$, we can compute $a_{k}$. We claim that, for $k\in p_{0}+p_{1}\mathbb{N}$, writing $k=p_{0}+p_{1}r$, we have that

$\displaystyle(x,y)\Phi^{k}=(u^{a_{p_{0}}\Theta^{r}},y\phi^{k}).$

(2)

We prove it by induction over $r$. Clearly, if $r=0$, then $(x,y)\Phi^{k}=(x,y)\Phi^{p_{0}}=(u^{a_{p_{0}}},y\phi^{k}).$ Now assume that the claim holds for $r$ up to some $n\geq 0$. Notice that $w=y\phi^{p_{0}}$ is periodic with period $p_{1}$, and so, for all $n,t\in\mathbb{N}$, $y\phi^{p_{0}+np_{1}+t}=w\phi^{t}.$ Hence,

	$\displaystyle(x,y)\Phi^{p_{0}+(n+1)p_{1}}$	$\displaystyle=(x,y)\Phi^{p_{0}+np_{1}}\Phi^{p_{1}}$
		$\displaystyle=(u^{a_{p_{0}}\Theta^{n}},y\phi^{p_{0}+np_{1}})\Phi^{p_{1}}$
		$\displaystyle=\left(u^{(a_{p_{0}}\Theta^{n})(u^{P})^{p_{1}}+\sum\limits_{t=0}^{p_{1}-1}(y\phi^{p_{0}+np_{1}+t})^{R}(u^{P})^{p_{1}-t-1}},y\phi^{p_{0}+(n+1)p_{1}}\right)$
		$\displaystyle=\left(u^{(a_{p_{0}}\Theta^{n})(u^{P})^{p_{1}}+\sum\limits_{t=0}^{p_{1}-1}(w\phi^{t})^{R}(u^{P})^{p_{1}-t-1}},y\phi^{p_{0}+(n+1)p_{1}}\right)$
		$\displaystyle=\left(u^{a_{p_{0}}\Theta^{n+1}},y\phi^{k}\right).$

Since our only candidate solutions are of the form $p_{0}+p_{1}\mathbb{N}$, we can proceed as follows: we check manually the existence of a solution for $k$ up to $p_{0}$, using the word problem; then, if we obtain no positive answer, we verify the existence of some $r\in\mathbb{N}$ such that $a_{p_{0}}\Theta^{r}=a$, which can be done by Remark 2.2.

When considering the conjugation variant, we proceed analogously. Using BrCP($F_{n}$), we compute $p_{0},p_{1}\in\mathbb{N}$ such that $\tilde{\phi}\text{-}\log_{y}(w)=p_{0}+p_{1}\mathbb{N}$. We then check if $z$ is conjugate to some power of $u$ and if so, compute $a$ such that $u^{a}\sim z$. Using the same argument as above, we check if there is some $r$ such that the first component $(x,y)\Phi^{p_{0}+rp_{1}}$ is $u^{a}$. In fact, even though $w$ is no longer a periodic point, it is enough that $w$ is $\tilde{\phi}$-periodic since, for words $u,v\in F_{m}$ such that $u\sim v$, i.e., for which there is some $z\in F_{m}$ such that $u=z^{-1}vz$, we have that

$$u^{R}=\sum\limits_{j\in[m]}\tau_{j}(u)r_{j}=\sum\limits_{j\in[m]}\tau_{j}(z^{-1}vz)r_{j}=\sum\limits_{j\in[m]}\tau_{j}(v)r_{j}=v^{R}.$$

This means that for all $n,t\in\mathbb{N}$, $(y\phi^{p_{0}+np_{1}+t})^{R}=(w\phi^{t})^{R}$ and the same reduction done above can be done here and the claim (2) holds in this case too. Hence, we reduce our problem to finding some $r\in\mathbb{N}$ such that $a_{p_{0}}\Theta^{r}=a$, which can be done by Remark 2.2.

We have that $(x,y)\mapsto(y\phi,y\psi)$, for some homomorphism $\phi:F_{m}\to F_{n}$ and endomorphism $\psi\in\text{End}(F_{m})$, and so, as seen in [10, Subsection 5.4], $(x,y)\Phi^{k}=(y\psi^{k-1}\phi,y\psi^{k}),$ for $k>0$. Using BrP($F_{n}$), we start by computing $\psi\text{-}\log_{y}(w)$. If it is empty, then there are no solutions $k$. If not, $\psi\text{-}\log_{y}(w)=p_{0}+p_{1}\mathbb{N}$ for some computable $p_{0},p_{1}\in\mathbb{N}$. We check if $k=p_{0}$ is a solution or not. We have that $w=y\psi^{p_{0}}$ is a $\psi$-periodic point with period $p_{1}$. For $k=p_{0}+p_{1}r$, with $r\geq 1$, we have that $(x,y)\Phi^{k}=(y\psi^{p_{0}+p_{1}r-1}\phi,w)$. But for all $r\geq 1$, $y\psi^{p_{0}+p_{1}r-1}=y\psi^{p_{0}+p_{1}-1}$. So we simply check if $z=y\psi^{p_{0}+p_{1}-1}\phi$. If it is, then $p_{0}+p_{1}\mathbb{N}_{>0}$ is the set of solutions; if not, then there are no solutions to our problem.

We can handle the conjugacy version of the problem in the same way, computing $\tilde{\psi}\text{-}\log_{y}(w)$ instead of $\psi\text{-}\log_{y}(w)$. In this case, we have that, for all $r\geq 1$, $y\psi^{p_{0}+p_{1}r-1}\sim y\psi^{p_{0}+p_{1}-1}$ and so $y\psi^{p_{0}+p_{1}r-1}\phi\sim y\psi^{p_{0}+p_{1}-1}\phi$ and the set of solutions is $p_{0}+p_{1}\mathbb{N}_{>0}$ if $z\sim y\psi^{p_{0}+p_{1}-1}\phi$ and empty otherwise.

We have that $(x,y)\mapsto\left(1,v^{x^{Q}+y^{S}}\right)$, for some $1\neq v\in F_{m}$, for some word $v\in F_{m}$, and so, as seen in [10, Subsection 5.5], $(x,y)\varphi^{k}=\left(1,v^{(x^{Q}+y^{S})(v^{S})^{k-1}}\right)$, for $k>0$. So we start by checking if $z=1$ and if $w$ is a power of $v$. If any of these does not hold, then there is no positive solution $k$. If both hold, we compute $a\in\mathbb{Z}$ such that $w=v^{a}$. Clearly, $k$ is a solution if and only if $(v^{S})^{k-1}=\frac{a}{x^{Q}+y^{S}}$, and its existence is decidable. The conjugacy problem is analogous: we compute the unique $a^{\prime}\in\mathbb{Z}$ such that $w\sim v^{a^{\prime}}$ and check if there is some $k$ such that $(v^{S})^{k-1}=\frac{a^{\prime}}{x^{Q}+y^{S}}$.

We have that $(x,y)\mapsto(x\phi,y\psi)$, for some endomorphisms $\phi\in\text{End}(F_{n})$, $\psi\in\text{End}(F_{m})$, and so t $(x,y)\varphi^{k}=(x\phi^{k},y\psi^{k})$, for $k>0$. So this case is also simple: we compute $p_{0},p_{1},q_{0},q_{1}\in\mathbb{N}$ such that $\phi\text{-}\log_{x}(z)=p_{0}+p_{1}\mathbb{N}$ and $\psi\text{-}\log_{y}(w)=q_{0}+q_{1}\mathbb{N}$ (if there are no $p_{0}$ or $q_{0}$, then there are no solutions to our problem). Our set of solutions is the intersection $\phi\text{-}\log_{x}(z)\cap\psi\text{-}\log_{y}(w)$, which we can check if it is empty or not. For the conjugacy version of the problem we proceed in the same way, computing $\tilde{\phi}\text{-}\log_{x}(z)$ and $\tilde{\psi}\text{-}\log_{y}(w)$ instead.

We have that $(x,y)\mapsto(y\psi,x\phi)$, for homomorphisms $\phi:F_{n}\to F_{m}$ and $\psi:F_{m}\to F_{n}$, and so, as seen in [10, Subsection 5.7], for $k\geq 0$, $(x,y)\varphi^{2k}=(x(\phi\psi)^{k},y(\psi\phi)^{k})$ and $(x,y)\varphi^{2k+1}=(y(\psi\phi)^{k}\psi,x(\phi\psi)^{k}\phi)$. So we will describe two algorithms: one to decide the existence of an even $k$, and another one to decide the existence of an odd $k$. The first one is simple, since it can be seen as an application of the previous case, defining $\Psi$ to be the type VI endomorphism mapping $(x,y)$ to $(x\phi\psi,y\psi\phi)$. Now we describe the second one. We start by checking if there is some even $r\in\mathbb{N}$ such that $(x,y)\Phi^{r}=(z,w)\Phi$. If there is none, then there is no solution $k$; otherwise compute such a minimal $r$. It is proved in [10, Subsection 5.7] that the subgroup of periodic points of $\Phi$ is given by $\text{Per}(\Phi)=\text{Per}(\phi\psi)\times\text{Per}(\psi\phi)$. In particular, it is computable and we can check if a given element of $F_{n}\times F_{m}$ is periodic or not. We verify if $(w\psi,z\phi)=(z,w)\Phi$ is periodic or not. If it is not, then our only candidate is $k=r-1$. Indeed, if there was some other $k>r$, then we would have that

$$\left((z,w)\Phi\right)\Phi^{k-r+1}=(x,y)\Phi^{r}\Phi^{k-r+1}=(x,y)\Phi^{k+1}=(z,w)\Phi$$

and if there was some other $k<r$ we would have that

$$(z,w)\Phi\Phi^{r-k}=(x,y)\Phi^{k}\Phi^{r-k+1}=(x,y)\Phi^{r+1}=(z,w)\Phi.$$

So, assume that $(z,w)\Phi$ is periodic with period $s$. In this case, there are only finitely many checks to do since the orbit of $(x,y)$ is finite, as illustrated in the following picture: