text:
# Twisted conjugacy in free groups and Makanin’s question

## 1. Conjugacy and twisted conjugacy

Suppose $`G`$ is a group given by a presentation in generators and defining relations. Three following decision problems formulated by M. Dehn  in 1912 (see also \[9, Ch. 1, § 2; Ch. 2, § 1 \]) are fundamental in the group theory.

Word problem: Does there exist an algorithm to determine if an arbitrary group word $`W`$ given in the generators of $`G`$ defines the identity element of $`G`$?

Conjugacy problem: Does there exist an algorithm to determine is an arbitrary pair of group words $`U`$, $`V`$ in the generators of $`G`$ define conjugate elements of $`G`$?

Isomorphism problem: Does there exist an algorithm to determine for any two arbitrary finite presentations whether the groups they present are isomorphic or not?

All three of these problems have negative answers in general (see, for example , \[3, Ch. 6.7\]). These results together with solutions of Dehn’s problems in restricted cases have been of central importance in the combinatorial group theory. For this reason combinatorial group theory has always searched for and studied classes of groups in which these decision problems are solvable. Also, various generalizations of these problems were considered (see, for example , \[9, Ch. 4, § 4\]).

In the present paper we discuss the twisted conjugacy problem, that can be considered as a generalization of Dehn’s conjugacy problem. Suppose $`G`$ is a group given by a presentation and $`H`$ is a subset of its automorphisms group $`\text{Aut}(G)`$.

Twisted conjugacy problem: Does there exist an algorithm to determine is for an arbitrary pair of group words $`U`$ and $`V`$ in generators of $`G`$ the equality $`\phi (W)U=VW`$ holds for some $`WG`$ and $`\phi H`$?

Since the twisted conjugacy problem depends of a group $`G`$ as well as a subset $`H\text{Aut}(G)`$, this problem will be referred to as the conjugacy problem in $`G`$ relative to $`H`$ or as the $`H`$–twisted conjugacy problem in $`G`$. If $`H`$ consists of the identity automorphism then we deal with the classical conjugacy problem. If $`H=\{\phi \}`$ consists of the unique automorphism then, obviously, a property to be twisted conjugated is an equivalence relation.

The following question was posted by G. Makanin in “Kourovka notebook” \[8, Question 10.26(a)\]: Does there exist an algorithm to determine is for an arbitrary pair of words $`U`$ and $`V`$ of a free group $`G`$ and an arbitrary automorphism $`\phi `$ of $`G`$ the equation $`\phi (X)U=VX`$ solvable in $`G`$? This question can be regarded as the twisted conjugacy problem for the case when $`G`$ is a free group and $`H=\{\phi \}`$ consists of the unique automorphism.

We remark that the twisted conjugacy problem is also connected with the question of solving equations in the holomorph $`\text{Hol}(G)=G\text{Aut}(G)`$. In this context we recall the following question of G. Makanin \[8, Question 10.26(b)\]: Does there exist an algorithm to determine is for arbitrary automorphisms $`\phi _1,\mathrm{},\phi _n`$ of a free group the equation $`w(x_{i_1}^{\phi _1},\mathrm{},x_{i_n}^{\phi _n})=1`$ solvable?

## 2. Basic notations and results

In the present paper we deal with the case when $`G=F_n`$ is the finitely generated free group with basis $`\{x_1,\mathrm{},x_n\}`$. Elements of $`F_n`$ are words in the alphabet $`𝕏=\{x_1^{\pm 1},\mathrm{},x_n^{\pm 1}\}`$. In our considerations below we will need to distinguish words which represent the same element of the group. So, we will usually use small letters to denote elements of $`F_n`$ and capital letters to denote words in the above alphabet. We will write $`U=V`$ (or $`u=v`$) if two words (or two elements of the group) are equal as elements of the group, and $`UV`$ if two words coincide graphically. We use standard notations $`\text{Aut}(F_n)`$ and $`\text{Inn}(F_n)`$ for the group of automorphisms and the group of inner automorphisms of $`F_n`$.

Denote by $`|W|`$ the length of a word $`W`$ in the alphabet $`𝕏`$. A word $`W`$ is said to be reduced if it contains no part $`xx^1`$, $`x𝕏`$. A reduced word $`W`$ defines a non-identity element if and only if $`|W|1`$. A reduced word obtained by reducing of an original word will be referred to as its reduction. By $`W`$ we will denote the length of the reduction of a word $`W`$.

We define a linear order “$`<`$” on the set of reduced words in the alphabet $`𝕏`$. Assume that letters of $`𝕏`$ are ordered in the following way:

$$x_1<x_1^1<x_2<x_2^1<\mathrm{}<x_n<x_n^1.$$

We write $`U<V`$ if $`|U|<|V|`$ or if $`|U|=|V|`$ and the word $`U`$ is less than the word $`V`$ in respect to the lexicographical order corresponding to the above defined linear order on $`𝕏`$.

Recall that all three classical Dehn problems have simple and elegant solutions in free groups. Since reducing any word is an algorithmic process, this provides a solution of the word problem. Further, a reduced word $`W=x_{i_1}^{\epsilon _1}x_{i_2}^{\epsilon _2}\mathrm{}x_{i_n}^{\epsilon _n},`$ where $`\epsilon _i=\pm 1,`$ $`i=1,\mathrm{},n`$, is said to be cyclically reduced if $`i_1i_n`$ or if $`i_1=i_n`$ then $`\epsilon _1\epsilon _n`$. Clearly, every element of a free group is conjugated to an element given by a cyclically reduced word called a cyclic reduction. This leads to a solution of the conjugacy problem. Suppose for given words $`U`$ and $`V`$, words $`\overline{U}`$, $`\overline{V}`$ are their cyclic reductions. Then $`U`$ is conjugated to $`V`$ if and only if $`\overline{U}`$ is a cyclic permutation of $`\overline{V}`$. Finally, two finitely generated free groups are isomorphic if and only if they have the same rank.

In this paper we consider the twisted conjugacy problem in $`G=F_n`$ relative to $`H=\{\phi \}`$, where $`\phi \text{Aut}(F_n)`$ is such that $`\phi ^m\text{Inn}(F_n)`$ for some non-zero integer $`m`$. Such automorphism $`\phi `$ will be referred to as a virtually inner automorphism. In particular, if an automorphism $`\phi `$ is of finite order or inner, then it is virtually inner. The main result of the paper is the following

###### Theorem 1.

Suppose $`\phi `$ is a virtually inner automorphism of the free group $`F_n`$. Then the $`\phi `$–twisted conjugacy problem in $`F_n`$ is solvable.

To prove this statement, we introduce $`\phi `$-twisted conjugated normal form of a word, which can be constructed by a finite number of steps. We show that two words are $`\phi `$-twisted conjugated if and only if their $`\phi `$-twisted conjugated normal form coincide (see Section 6 for the proof).

Consider the mapping torus (in other words, the ascending HNN extension)

$$F_n(\phi )=x_1,\mathrm{},x_n,t|t^1x_it=\phi (x_i),i=1,\mathrm{},n$$

that is the semidirect product of $`F_n`$ and $`t`$. There is an evident relation between the $`\phi `$-twisted conjugacy problem in $`F_n`$ and the classical conjugacy problem in $`F_n(\phi )`$.

###### Lemma 1.

The $`\phi `$–twisted conjugacy problem in the free group $`F_n`$ is solvable if and only if there exists an algorithm to determine is a pair of words $`tU`$ and $`tV`$ from $`F_n(\phi )`$, where $`U,VF_n`$, define elements conjugated by some element of $`F_n`$.

###### Proof.

Obviously, the equality $`X^1(tV)X=tU`$ holds in $`F_n(\phi )`$ for some $`XF_n`$ if and only if the equality $`\phi (X^1)VX=U`$ holds in $`F_n`$, i.e. $`\phi (X)U=VX`$. ∎

It was shown by Bestvina and Feighn in , that if $`\phi \text{Aut}(F_n)`$ have no nontrivial periodic conjugacy classes (see next section for the definition) then $`F_n(\phi )`$ is hyperbolic. So, the conjugacy problem is solvable in it. (We note, that virtually inner automorphisms that we consider below, are such that each conjugacy class is periodic.) We will show in Proposition 1 that also the problem of conjugation by an element of $`F_n`$ is solvable in it.

Theorem 1, Lemma 1, and Proposition 1 imply the partial affirmative answer on the above mentioned Makanin’s question \[8, Question 10.26(a)\]:

###### Corollary 1.

Let $`\phi \text{Aut}(F_n)`$ be a virtually inner or having no nontrivial periodic conjugacy classes. Then there exists an algorithm to determine for an arbitrary pair of words $`U`$ and $`V`$ the solvability in $`F_n`$ of the equation $`\phi (X)U=VX`$.

## 3. Automorphisms having no nontrivial periodic conjugacy classes

An automorphism $`\phi `$ of the free group $`F_n`$ is said to have nontrivial periodic conjugacy class if there exist integer $`\mathrm{}`$ and elements $`x,yF_n`$ such that $`\phi ^{\mathrm{}}(x)=y^1xy`$. It was proven by Bestvina and Feighn  and by P. Brinkmann , that $`F_n(\phi )`$ is hyperbolic (in the Gromov’s sense) if and only if automorphism $`\phi `$ has no nontrivial periodic conjugacy classes.

###### Proposition 1.

Suppose $`\phi Aut(F_n)`$ has no nontrivial periodic conjugacy classes. Then the $`\phi `$-twisted conjugacy problem in $`F_n`$ is solvable.

###### Proof.

By Lemma 1, the $`\phi `$–twisted conjugacy of words $`U`$ and $`V`$ from $`F_n`$ is equivalent to the conjugacy of words $`tU`$ and $`tV`$ from $`F_n(\phi )`$ by some element of $`F_n`$. Since $`\phi `$ has no nontrivial periodic conjugacy classes, by  the group $`F_n(\phi )`$ is hyperbolic and so, the conjugacy problem in this group is solvable (see, for example, \[4, Ch. 3\]).

If $`tU`$ and $`tV`$ are not conjugated in $`F_n(\phi )`$, then they, in particular, are not conjugated by an element of $`F_n`$, so $`U`$ and $`V`$ are not $`\phi `$–twisted conjugated.

Assume that $`tU`$ and $`tV`$ are conjugated in $`F_n(\phi )`$ by some element $`t^kW`$, where $`WF_n`$ and $`k`$ is integer. If $`k=0`$, the statement follows from Lemma 1. If $`k0`$, we remark the following. Each element of $`F_n(\phi )`$ that conjugates $`tU`$ to $`tV`$ is of the form $`ct^kW`$, where $`c`$ belongs to the centralizer $`C_G(tU)`$ of $`tU`$ in $`G=F_n(\phi )`$. It was shown by Gromov (see, for example, \[4, Corollary 3.10, p. 462\]), that in a hyperbolic group the centralizer of any nontrivial element is almost cyclic and there exists an algorithm to find generators of the centralizer $`C_G(tU)`$. Considering the canonical homomorphism of the centralizer $`C_G(tU)`$ onto the group $`t`$, one can check if the element $`t^k`$ lies in the image of that homomorphism. If yes, then elements $`tU`$ and $`tV`$ are conjugated by an element of $`F_n`$. If not, then they are not conjugated by an element of $`F_n`$, and so, elements $`U`$ and $`V`$ are not $`\phi `$-twisted conjugated. ∎

We are thankful to Oleg Bogopol’skii for useful discussion of results from this Section.

## 4. Virtually inner automorphisms of free groups

Let $`\phi \text{Aut}(F_n)`$ be a virtually inner automorphism such that $`\psi =\phi ^m`$ is an inner automorphism of $`F_n`$. Without loss of generality we can assume that $`m`$ is taken the smallest positive integer having such a property. There exists a reduced word $`\mathrm{\Delta }F_n`$ such that

$$\phi ^m(f)=\mathrm{\Delta }^1f\mathrm{\Delta }$$

for any $`fF_n`$.

###### Lemma 2.

(1) Automorphisms $`\phi `$ and $`\psi `$ commute.
(2) If $`k=mq+r`$, where $`q`$ and $`0rm1`$, then for any word $`U`$ of the alphabet $`𝕏`$ we have

$$\phi ^k(U)=\phi ^r(\mathrm{\Delta }^qU\mathrm{\Delta }^q).$$

(3) $`\phi (\mathrm{\Delta })=\mathrm{\Delta }`$.

###### Proof.

Properties (1) and (2) hold obviously, since $`\psi `$ is a power of $`\phi `$.
To show (3), remark that by (1) we have

$$\mathrm{\Delta }^1\phi (f)\mathrm{\Delta }=\phi (\mathrm{\Delta }^1f\mathrm{\Delta })=\phi (\mathrm{\Delta }^1)\phi (f)\phi (\mathrm{\Delta })$$

for any $`fF_n`$. Therefore, $`\phi (\mathrm{\Delta })\mathrm{\Delta }^1`$ and $`\phi (f)`$ commute for all $`fF_n`$. Since $`\phi `$ is automorphism, we get $`\phi (\mathrm{\Delta })\mathrm{\Delta }^1=1`$, so $`\phi (\mathrm{\Delta })=\mathrm{\Delta }`$. ∎

A reduced word $`VF_n`$ is said to be $`\mathrm{\Delta }`$-reduced if $`|V|\mathrm{\Delta }^kV\mathrm{\Delta }^k`$ for all $`k`$. Obviously, if $`V`$ is cyclically reduced, then the length of any word conjugated to $`V`$ is not less than the length of $`V`$, so $`V`$ is $`\mathrm{\Delta }`$-reduced.

###### Lemma 3.

Suppose that $`\mathrm{\Delta }`$ is cyclically reduced. A reduced word $`VF_n`$ is $`\mathrm{\Delta }`$-reduced if $`|V|\mathrm{\Delta }^\epsilon V\mathrm{\Delta }^\epsilon `$ for $`\epsilon =\pm 1`$.

###### Proof.

If $`V`$ is cyclically reduced, by the above observation it is $`\mathrm{\Delta }`$-reduced. If $`V`$ is not cyclically reduced, we represent it in the form $`VU^1WU`$, where $`U`$ and $`W`$ are reduced nonempty words in $`F_n`$ and $`W`$ is cyclically reduced.

Suppose that $`|V|\mathrm{\Delta }^1V\mathrm{\Delta }`$ and assume that there exists integer $`k>1`$ such that $`\mathrm{\Delta }^kV\mathrm{\Delta }^k<|V|`$. Then

$$\mathrm{\Delta }^kV\mathrm{\Delta }^k\mathrm{\Delta }^kU^1WU\mathrm{\Delta }^k(U\mathrm{\Delta }^k)^1W(U\mathrm{\Delta }^k).$$

Since $`\mathrm{\Delta }`$ is cyclically reduced, $`\mathrm{\Delta }^k=k|\mathrm{\Delta }|`$ and in the word $`U\mathrm{\Delta }^k`$ only cancellations of letters from $`U`$ with letters from $`\mathrm{\Delta }^k`$ can arise. If such cancellations are possible, there are two possibilities: either there are cancellations with letters of $`W`$ or not.

Case 1. Suppose that there are cancellations of letters of $`\mathrm{\Delta }^k`$ with letters of $`U`$, where, possibly, $`U`$ will be cancelled wholly (the same for $`\mathrm{\Delta }^k`$ and $`U^1`$, respectively), but there no further cancellations with letters of $`W`$. Then we can write $`U\mathrm{\Sigma }_1\mathrm{\Sigma }_2^1`$ and $`\mathrm{\Delta }^k\mathrm{\Sigma }_2\mathrm{\Sigma }_3`$ for some reduced $`\mathrm{\Sigma }_1,\mathrm{\Sigma }_2,\mathrm{\Sigma }_3F_n`$.

If the length of the cancelling part $`\mathrm{\Sigma }_2`$ is bigger than the length of $`\mathrm{\Delta }`$, then $`\mathrm{\Sigma }_2\mathrm{\Delta }\mathrm{\Sigma }_{2,1}`$ and $`U\mathrm{\Sigma }_1\mathrm{\Sigma }_{2,1}^1\mathrm{\Delta }^1U_1\mathrm{\Delta }^1`$, where $`|U_1|<|U|`$. Then

$$\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }^1U^1WU\mathrm{\Delta }=U_1^1WU_1=|W|+2|U_1|$$

that is less than

$$|V|=|U^1WU|=|W|+2|U|$$

because $`|U_1|<|U|`$. Thus we get the contradiction with the assumption.

If the length of the cancelling part $`\mathrm{\Sigma }_2`$ is less or equal to the length of $`\mathrm{\Delta }`$, then $`U\mathrm{\Sigma }_1\mathrm{\Sigma }_2^1`$ and $`\mathrm{\Delta }^k\mathrm{\Sigma }_2\mathrm{\Sigma }_3\mathrm{\Delta }^{k1}`$ for some reduced $`\mathrm{\Sigma }_1,\mathrm{\Sigma }_2,\mathrm{\Sigma }_3F_n`$. We get

$$|V|=|W|+2|U|=|W|+2|\mathrm{\Sigma }_1|+2|\mathrm{\Sigma }_2|,$$

$$\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Sigma }_3^1\mathrm{\Sigma }_1^1W\mathrm{\Sigma }_1\mathrm{\Sigma }_3=|W|+2|\mathrm{\Sigma }_1|+2|\mathrm{\Sigma }_3|,$$

and

$$\mathrm{\Delta }^kV\mathrm{\Delta }^k=\mathrm{\Delta }^{(k1)}(\mathrm{\Delta }^1V\mathrm{\Delta })\mathrm{\Delta }^{k1}$$

$$=\mathrm{\Delta }^1V\mathrm{\Delta }+2(k1)|\mathrm{\Delta }|=|W|+2|\mathrm{\Sigma }_1|+2|\mathrm{\Sigma }_3|+2(k1)|\mathrm{\Delta }|.$$

Since $`k>1`$ and $`|\mathrm{\Sigma }_2||\mathrm{\Delta }|`$, we see that $`|V|\mathrm{\Delta }^kV\mathrm{\Delta }^k`$ that gives the contradiction with the assumption.

Case 2. Suppose that letters of $`\mathrm{\Delta }^k`$ and $`\mathrm{\Delta }^k`$ are cancelling with letters of $`VU^1WU`$ is such a way that words $`U`$ and $`U^1`$ will be cancelled wholly and there are further cancellations with letters of $`W`$. Since $`|U^1WU|\mathrm{\Delta }^1U^1WU\mathrm{\Delta }`$, and $`U^1`$ and $`U`$ are cancelling wholly, we have $`U\mathrm{\Delta }_1^1`$ and $`\mathrm{\Delta }\mathrm{\Delta }_1\mathrm{\Delta }_2`$ with $`|\mathrm{\Delta }_2||\mathrm{\Delta }_1|=|U|`$. Hence

$`\mathrm{\Delta }^kV\mathrm{\Delta }^k`$ $``$ $`\mathrm{\Delta }^{(k1)}\mathrm{\Delta }_2^1\mathrm{\Delta }_1^1(\mathrm{\Delta }_1W\mathrm{\Delta }_1^1)\mathrm{\Delta }_1\mathrm{\Delta }_2\mathrm{\Delta }^{k1}`$
$`=`$ $`\mathrm{\Delta }^{(k1)}\mathrm{\Delta }_2^1W\mathrm{\Delta }_2\mathrm{\Delta }^{k1}.`$
The further cancellations are possible either in $`\mathrm{\Delta }_2^1W`$ or in $`W\mathrm{\Delta }_2`$, but not in both, since $`W`$ is cyclically reduced.

If $`\mathrm{\Delta }_2^1`$ is cancelling wholly in $`\mathrm{\Delta }_2^1W\mathrm{\Delta }_2`$, then

$$\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }_2^1W\mathrm{\Delta }_2=|W|<|V|$$

and we have a contradiction with the assumption $`\mathrm{\Delta }^1V\mathrm{\Delta }|V|`$.

If $`\mathrm{\Delta }_2^1`$ is not cancelling wholly in the product $`\mathrm{\Delta }_2^1W\mathrm{\Delta }_2`$, then $`\mathrm{\Delta }_2\mathrm{\Delta }_{21}\mathrm{\Delta }_{22}`$ and $`W\mathrm{\Delta }_{21}^1W_1`$, and

$`\mathrm{\Delta }^kV\mathrm{\Delta }^k`$ $`=`$ $`\mathrm{\Delta }^{(k1)}\mathrm{\Delta }_2^1W\mathrm{\Delta }_2\mathrm{\Delta }^{k1}`$
$`=`$ $`\mathrm{\Delta }^{(k1)}\mathrm{\Delta }_{22}^1W_1\mathrm{\Delta }_{21}\mathrm{\Delta }_{22}\mathrm{\Delta }^{k1}`$
$``$ $`|W|+2(k1)|\mathrm{\Delta }|+2|\mathrm{\Delta }_{22}|`$
$`>`$ $`|W|+2|\mathrm{\Delta }|>|W|+2|U|=|V|,`$
and we have a contradiction with the assumption $`\mathrm{\Delta }^kV\mathrm{\Delta }^k<|V|`$. By similar arguments, the case when $`\mathrm{\Delta }_2`$ is not cancelling wholly in the product $`W\mathrm{\Delta }_2`$, is also impossible.

If there exists integer $`k<1`$ with the same property, similar considerations implies the statement. ∎

If $`\mathrm{\Delta }`$ is cyclically reduced, Lemma 3 gives the finite algorithm to find for a given reduced word $`V`$ a $`\mathrm{\Delta }`$-reduced word $`V_\mathrm{\Delta }`$ conjugated to $`V`$ by some power of $`\mathrm{\Delta }`$. Indeed, it is enough to repeat conjugations of $`V`$ by $`\mathrm{\Delta }^\epsilon `$, $`\epsilon =\pm 1`$, few times. If the length of the obtained word is less than the length of the previous word, we will conjugate again. If not, then the obtained word is a $`\mathrm{\Delta }`$-reduced word $`V_\mathrm{\Delta }`$ conjugated to $`V`$. Such a construction of a $`\mathrm{\Delta }`$-reduced word $`V_\mathrm{\Delta }`$ conjugated to $`V`$ by some power of $`\mathrm{\Delta }`$ will be referred to as a $`\mathrm{\Delta }`$-reduction.

We remark that if $`\mathrm{\Delta }`$ is not cyclically reduced, then the analog of Lemma 3 does not hold. It is clear from the following example.

Example. Let $`U,W,\mathrm{\Sigma }F_n`$ be nonempty reduced words such that for an integer $`|k|>1`$ words $`\mathrm{\Delta }U^1W^1\mathrm{\Sigma }WU`$ and $`VU^1W^1\mathrm{\Sigma }^kWU^2`$ are reduced. If $`k>1`$, we get

$`\mathrm{\Delta }^1V\mathrm{\Delta }`$ $`=`$ $`U^1W^1\mathrm{\Sigma }^{k1}WUW^1\mathrm{\Sigma }WU,`$
$`\mathrm{\Delta }^2V\mathrm{\Delta }^2`$ $`=`$ $`U^1W^1\mathrm{\Sigma }^{k2}WUW^1\mathrm{\Sigma }^2WU,`$
$`\mathrm{}`$
$`\mathrm{\Delta }^{(k1)}V\mathrm{\Delta }^{k1}`$ $`=`$ $`U^1W^1\mathrm{\Sigma }WUW^1\mathrm{\Sigma }^{k1}WU,`$
$`\mathrm{\Delta }^kV\mathrm{\Delta }^k`$ $`=`$ $`W^1\mathrm{\Sigma }^kWU.`$
It is easy to see that

$$|V|<\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }^2V\mathrm{\Delta }^2=\mathrm{}=\mathrm{\Delta }^{(k1)}V\mathrm{\Delta }^{k1},$$

but $`\mathrm{\Delta }^kV\mathrm{\Delta }^k<|V|`$.

If $`k<1`$, similar example can be obtained conjugating $`V`$ by negative powers of $`\mathrm{\Delta }`$.

###### Lemma 4.

Suppose $`\mathrm{\Delta }`$ is not cyclically reduced. Let $`V`$ be a reduced word such that $`|V|\mathrm{\Delta }^\epsilon V\mathrm{\Delta }^\epsilon `$, $`\epsilon =\pm 1`$. Then one of the following cases holds:
(1) $`V`$ is $`\mathrm{\Delta }`$-reduced.
(2) $`\mathrm{\Delta }U_1^1U_2^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2\mathrm{\Delta }_{11}U_2U_1`$ and $`VU_1^1U_2^1WU_2U_1`$, for some reduced $`\mathrm{\Delta }_{11},\mathrm{\Delta }_2,U_1,U_2`$ and cyclically reduced $`W`$ for which there exist integers $`k`$, $`|k|>1`$, and $`m0`$ and reduced $`\mathrm{\Phi }`$, $`W_0`$ such that either
a) $`U_2^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}\mathrm{\Phi }W^m`$ and $`W\mathrm{\Phi }^1W_0`$,
or
b) $`\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}U_2W^m\mathrm{\Phi }`$ and $`WW_0\mathrm{\Phi }^1`$.
In addition, $`\mathrm{\Phi }`$ does not end by $`W^1`$, and $`W_0`$ is either nonempty or $`W_01`$ with $`U_1^1\mathrm{\Phi }^1U_1`$ be reduced.

In case (2) $`V_\mathrm{\Delta }=\mathrm{\Delta }^kV\mathrm{\Delta }^k`$ is $`\mathrm{\Delta }`$-reduced word conjugated to $`V`$. Moreover, case (2) describe all possible cases when $`|V|\mathrm{\Delta }^\epsilon V\mathrm{\Delta }^\epsilon `$, $`\epsilon =\pm 1`$, but $`\mathrm{\Delta }^kV\mathrm{\Delta }^k<|V|`$ for some $`|k|>1`$.

###### Proof.

Suppose that $`|V|\mathrm{\Delta }^1V\mathrm{\Delta }`$ and assume that there exists integer $`k>1`$ such that $`\mathrm{\Delta }^kV\mathrm{\Delta }^k<|V|`$.

We represent the reduced word $`\mathrm{\Delta }`$ in the form $`\mathrm{\Delta }\mathrm{\Delta }_1^1\mathrm{\Delta }_2\mathrm{\Delta }_1`$, where $`\mathrm{\Delta }_2`$ is cyclically reduced and $`\mathrm{\Delta }_1`$ is reduced. Then $`\mathrm{\Delta }^k=(\mathrm{\Delta }_1^1\mathrm{\Delta }_2\mathrm{\Delta }_1)^k=\mathrm{\Delta }_1^1\mathrm{\Delta }_2^k\mathrm{\Delta }_1`$, where the last word is reduced and $`\mathrm{\Delta }^k=2|\mathrm{\Delta }_1|+k|\mathrm{\Delta }_2|`$.

If $`V`$ is cyclically reduced, then, obviously, it is $`\mathrm{\Delta }`$-reduced.

If $`V`$ is not cyclically reduced, we write it in the form $`VU^1WU`$, where $`W`$ is cyclically reduced and $`U`$ is reduced. Then

$$\mathrm{\Delta }^kV\mathrm{\Delta }^k=\mathrm{\Delta }^kU^1WU\mathrm{\Delta }^k=(U\mathrm{\Delta }_1^1\mathrm{\Delta }_2^k\mathrm{\Delta }_1)^1W(U\mathrm{\Delta }_1^1\mathrm{\Delta }_2^k\mathrm{\Delta }_1).$$

Since $`\mathrm{\Delta }^kV\mathrm{\Delta }^k<|V|`$, there are cancellations in this word. There are two possibilities: either there are cancellations with letters of $`W`$ or not.

Case 1. Suppose that there are cancellations of letters of $`\mathrm{\Delta }^k`$ with letters of $`U`$, where, possibly, $`U`$ will be cancelled wholly (the same for $`\mathrm{\Delta }^k`$ and $`U^1`$, respectively), but there no further cancellations with letters of $`W`$. Then we can write $`U\mathrm{\Sigma }_1\mathrm{\Sigma }_2^1`$ and $`\mathrm{\Delta }_1^1\mathrm{\Delta }_2^k\mathrm{\Delta }_1\mathrm{\Sigma }_2\mathrm{\Sigma }_3`$ for some $`\mathrm{\Sigma }_1,\mathrm{\Sigma }_2,\mathrm{\Sigma }_3F_n`$.

Since

$$\mathrm{\Delta }^kV\mathrm{\Delta }^k=|\mathrm{\Sigma }_3^1\mathrm{\Sigma }_1^1W\mathrm{\Sigma }_1\mathrm{\Sigma }_3|=|W|+2|\mathrm{\Sigma }_1|+2|\mathrm{\Sigma }_3|$$

and

$$|V|=|\mathrm{\Sigma }_2\mathrm{\Sigma }_1^1W\mathrm{\Sigma }_1\mathrm{\Sigma }_2^1|=|W|+2|\mathrm{\Sigma }_1|+2|\mathrm{\Sigma }_2|,$$

we get $`|\mathrm{\Sigma }_2|>|\mathrm{\Sigma }_3|`$.

From the representation $`\mathrm{\Delta }_1^1\mathrm{\Delta }_2^k\mathrm{\Delta }_1\mathrm{\Sigma }_2\mathrm{\Sigma }_3`$ we have $`\mathrm{\Sigma }_2\mathrm{\Delta }_1^1\mathrm{\Delta }_2^{\mathrm{}}\mathrm{\Delta }_{21}`$ and $`\mathrm{\Sigma }_3\mathrm{\Delta }_{22}\mathrm{\Delta }_2^m\mathrm{\Delta }_1`$, where $`\mathrm{\Delta }_2\mathrm{\Delta }_{21}\mathrm{\Delta }_{22}`$ (one of words $`\mathrm{\Delta }_{21}`$ and $`\mathrm{\Delta }_{22}`$ can be empty) and $`k=\mathrm{}+m+1`$.

Consider

$`\mathrm{\Delta }^1V\mathrm{\Delta }`$ $`=`$ $`\mathrm{\Delta }_1^1\mathrm{\Delta }_2^1\mathrm{\Delta }_1U^1WU\mathrm{\Delta }_1^1\mathrm{\Delta }_2\mathrm{\Delta }_1`$
$`=`$ $`\mathrm{\Delta }_1^1\mathrm{\Delta }_2^1\mathrm{\Delta }_1\mathrm{\Sigma }_2\mathrm{\Sigma }_1^1W\mathrm{\Sigma }_1\mathrm{\Sigma }_2^1\mathrm{\Delta }_1^1\mathrm{\Delta }_2\mathrm{\Delta }_1`$
$`=`$ $`\mathrm{\Delta }_1^1\mathrm{\Delta }_2^1\mathrm{\Delta }_1(\mathrm{\Delta }_1^1\mathrm{\Delta }_2^{\mathrm{}}\mathrm{\Delta }_{21})\mathrm{\Sigma }_1^1W\mathrm{\Sigma }_1(\mathrm{\Delta }_{21}^1\mathrm{\Delta }_2^{\mathrm{}}\mathrm{\Delta }_1)\mathrm{\Delta }_1^1\mathrm{\Delta }_2\mathrm{\Delta }_1`$
$`=`$ $`\mathrm{\Delta }_1^1\mathrm{\Delta }_2^\mathrm{}1\mathrm{\Delta }_{21}\mathrm{\Sigma }_1^1W\mathrm{\Sigma }_1\mathrm{\Delta }_{21}^1\mathrm{\Delta }_2^{\mathrm{}+1}\mathrm{\Delta }_1`$
$`=`$ $`|W|+2|\mathrm{\Sigma }_1|+2|\mathrm{\Delta }_1^1\mathrm{\Delta }_2^\mathrm{}1\mathrm{\Delta }_{21}|`$
and

$$|V|=|\mathrm{\Sigma }_2\mathrm{\Sigma }_1^1W\mathrm{\Sigma }_1\mathrm{\Sigma }_2^1|=|W|+2|\mathrm{\Sigma }_1|+2|\mathrm{\Sigma }_2|.$$

Since $`\mathrm{\Sigma }_2\mathrm{\Delta }_1^1\mathrm{\Delta }_2^{\mathrm{}}\mathrm{\Delta }_{21}`$, we have $`|\mathrm{\Sigma }_2|>|\mathrm{\Delta }_1^1\mathrm{\Delta }_2^\mathrm{}1\mathrm{\Delta }_{21}|`$. Therefore, $`\mathrm{\Delta }^1V\mathrm{\Delta }<|V|`$, that gives the contradiction with the assumption.

Therefore, for any $`k1`$ the inequality $`|V|\mathrm{\Delta }^kV\mathrm{\Delta }^k`$ holds.

Taking $`\mathrm{\Delta }V\mathrm{\Delta }^1`$, similar considerations show that the inequality holds also for $`k1`$. Therefore, $`V`$ is $`\mathrm{\Delta }`$-reduced word.

Case 2. Suppose that letters of $`\mathrm{\Delta }^k`$ and $`\mathrm{\Delta }^k`$, where $`\mathrm{\Delta }^k\mathrm{\Delta }_1^1\mathrm{\Delta }_2^k\mathrm{\Delta }_1`$ are cancelling with letters of $`VU^1WU`$ is such a way that words $`U`$ and $`U^1`$ will be cancelled wholly and there are further cancellations with letters of $`W`$, starting either from the initial part of $`W`$ or from the final part of $`W`$, but not from the both, since $`W`$ is cyclically reduced.

Case 2(i). Suppose that $`|U||\mathrm{\Delta }_1|`$ and cancellations in $`W`$ starts from the initial part.

Recall that $`|V|\mathrm{\Delta }^1V\mathrm{\Delta }`$, where $`|V|=|W|+2|U|`$ and $`\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }_1^1\mathrm{\Delta }_2^1\mathrm{\Delta }_1U^1WU\mathrm{\Delta }_1^1\mathrm{\Delta }_2\mathrm{\Delta }_1`$. Hence $`|U||\mathrm{\Delta }_1|+\frac{1}{2}|\mathrm{\Delta }_2|`$ and we can represent $`U^1\mathrm{\Delta }_1^1\mathrm{\Delta }_{21}`$, where $`\mathrm{\Delta }_2\mathrm{\Delta }_{21}\mathrm{\Delta }_{22}`$ and $`|\mathrm{\Delta }_{21}||\mathrm{\Delta }_{22}|`$. Then

$`\mathrm{\Delta }^kV\mathrm{\Delta }^k`$ $`=`$ $`\mathrm{\Delta }_1^1(\mathrm{\Delta }_{21}\mathrm{\Delta }_{22})^k\mathrm{\Delta }_1(\mathrm{\Delta }_1^1\mathrm{\Delta }_{21})W(\mathrm{\Delta }_{21}^1\mathrm{\Delta }_1)\mathrm{\Delta }_1^1(\mathrm{\Delta }_{21}\mathrm{\Delta }_{22})^k\mathrm{\Delta }_1`$
$`=`$ $`\mathrm{\Delta }_1^1(\mathrm{\Delta }_{21}\mathrm{\Delta }_{22})^{(k1)}\mathrm{\Delta }_{22}^1W\mathrm{\Delta }_{22}(\mathrm{\Delta }_{21}\mathrm{\Delta }_{22})^{k1}\mathrm{\Delta }_1.`$
Consider

$$|V|=|U^1WU|=|W|+2|U|=|W|+2|\mathrm{\Delta }_1|+2|\mathrm{\Delta }_{21}|$$

and

$$\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }_1^1\mathrm{\Delta }_2^1\mathrm{\Delta }_1U^1WU\mathrm{\Delta }_1^1\mathrm{\Delta }_2\mathrm{\Delta }_1=\mathrm{\Delta }_1^1\mathrm{\Delta }_{22}^1W\mathrm{\Delta }_{22}\mathrm{\Delta }_1.$$

Since $`|V|\mathrm{\Delta }^1V\mathrm{\Delta }`$, in the product $`\mathrm{\Delta }_{22}^1W`$ the word $`\mathrm{\Delta }_{22}^1`$ can not be cancelled wholly.

Indeed, if $`\mathrm{\Delta }_{22}^1`$ is cancelling wholly, then after cancellations in $`\mathrm{\Delta }_{22}^1W\mathrm{\Delta }_{22}`$ we will get a cyclically reduced word which is obtained by a cyclic shift of $`W`$. Therefore $`\mathrm{\Delta }_{22}^1W\mathrm{\Delta }_{22}=|W|`$ and

$$\mathrm{\Delta }^1V\mathrm{\Delta }|W|+2|\mathrm{\Delta }_1|<|V|,$$

and we will get the contradiction.

Therefore, we can represent $`\mathrm{\Delta }_{22}^1\mathrm{\Sigma }_0\mathrm{\Sigma }_1^1`$, where $`\mathrm{\Sigma }_1^1`$ is the cancelling part and $`\mathrm{\Sigma }_0`$ is non-empty. After cancellations in $`\mathrm{\Sigma }_1^1W\mathrm{\Sigma }_1`$ we will get a cyclically reduced word which is obtained by a cyclic shift of $`W`$. Therefore, $`\mathrm{\Sigma }_1^1W\mathrm{\Sigma }_1=|W|`$ and

$$\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }_1^1\mathrm{\Sigma }_0(\mathrm{\Sigma }_1^1W\mathrm{\Sigma }_1)\mathrm{\Sigma }_0^1\mathrm{\Delta }_1=|W|+2|\mathrm{\Delta }_1|+2|\mathrm{\Sigma }_0|.$$

Comparing with

$`\mathrm{\Delta }^kV\mathrm{\Delta }^k`$ $`=`$ $`\mathrm{\Delta }_1^1(\mathrm{\Delta }_{21}\mathrm{\Delta }_{22})^{(k1)}\mathrm{\Delta }_{22}^1W\mathrm{\Delta }_{22}(\mathrm{\Delta }_{21}\mathrm{\Delta }_{22})^{k1}\mathrm{\Delta }_1`$
$`=`$ $`\mathrm{\Delta }_1^1(\mathrm{\Delta }_{21}\mathrm{\Delta }_{22})^{(k1)}\mathrm{\Sigma }_0(\mathrm{\Sigma }_1^1W\mathrm{\Sigma }_1)\mathrm{\Sigma }_0^1(\mathrm{\Delta }_{21}\mathrm{\Delta }_{22})^{k1}\mathrm{\Delta }_1`$
$`=`$ $`|W|+2|\mathrm{\Delta }_1|+2|\mathrm{\Sigma }_0|+2(k1)|\mathrm{\Delta }_{21}\mathrm{\Delta }_{22}|,`$
we see that $`\mathrm{\Delta }^1V\mathrm{\Delta }<\mathrm{\Delta }^kV\mathrm{\Delta }^k`$ for all $`k>1`$. By similar considerations the inequality holds also for all $`k<1`$. Therefore, $`V`$ is $`\mathrm{\Delta }`$-reducible.

Case 2(ii). Suppose that $`|U||\mathrm{\Delta }_1|`$ and cancellations in $`W`$ starts from the final part. The arguments analogous to the arguments from the Case 2(i), shows that in this case $`V`$ $`\mathrm{\Delta }`$-reducible.

Case 2(iii). Suppose that $`|U|<|\mathrm{\Delta }_1|`$ and cancellations in $`W`$ starts from the initial part. Then we can write $`\mathrm{\Delta }_1\mathrm{\Delta }_{11}U`$, where $`\mathrm{\Delta }_{11}1`$. Therefore,

$`\mathrm{\Delta }^kV\mathrm{\Delta }^k`$ $``$ $`\mathrm{\Delta }_1^1\mathrm{\Delta }_2^k\mathrm{\Delta }_1U^1WU\mathrm{\Delta }_1^1\mathrm{\Delta }_2^k\mathrm{\Delta }_1`$
$`=`$ $`U^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}UU^1WUU^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}U`$
$`=`$ $`U^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}W\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}U.`$
Since $`\mathrm{\Delta }^kV\mathrm{\Delta }^k<|V|`$, where $`|V|=|W|+2|U|`$, is it necessary that in the product $`U^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}W`$ the word $`\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}`$ will be cancelled wholly and, moreover, there will be some cancellations of letters of $`U^1`$ with letters of $`W`$. Denote by $`U_2^1`$ the cancelling part of the word $`U^1`$, Then we can write $`UU_2U_1`$, where $`|U|=|U_1|+|U_2|`$, and $`W\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}U_2W_0`$, for some $`W_0`$. Since $`W`$ is cyclically reduced, the word $`W_0\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}U_2`$ is reduced and $`W_0\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}U_2=|W|`$. Hence

$`\mathrm{\Delta }^kV\mathrm{\Delta }^k`$ $`=`$ $`U_1^1U_2^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}W\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}U_2U_1`$
$`=`$ $`U_1^1W_0\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}U_2U_1`$
$`=`$ $`|W|+2|U_1|<|V|,`$
because $`|U_1|<|U|`$.

Remark that with such $`V`$ and $`\mathrm{\Delta }`$ the inequality $`\mathrm{\Delta }^1V\mathrm{\Delta }>|V|`$ also holds. Indeed,

$`\mathrm{\Delta }^1V\mathrm{\Delta }`$ $``$ $`U^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^1\mathrm{\Delta }_{11}W\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2\mathrm{\Delta }_{11}U`$
$``$ $`U_1^1U_2^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^1\mathrm{\Delta }_{11}(\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}U_2W_0)\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2\mathrm{\Delta }_{11}U_2U_1`$
$`=`$ $`U_1^1U_2^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^{(k1)}\mathrm{\Delta }_{11}U_2W_0\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2\mathrm{\Delta }_{11}U_2U_1.`$
Since the obtained word is reduced, we get $`\mathrm{\Delta }^1V\mathrm{\Delta }=|W|+2|U|+2|\mathrm{\Delta }_{11}|`$, but $`|V|=|W|+2|U|`$.

Also, it is easy to see that $`\mathrm{\Delta }V\mathrm{\Delta }^1>|V|`$.

Thus we get that if

$$\mathrm{\Delta }U_1^1U_2^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2\mathrm{\Delta }_{11}U_2U_1$$

and

$$VU_1^1U_2^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}U_2W_0U_2U_1$$

for some $`\mathrm{\Delta }_{11},\mathrm{\Delta }_2,U_1,U_2,W_0F_n`$, and some integer $`k>1`$, then $`\mathrm{\Delta }^\epsilon V\mathrm{\Delta }^\epsilon >|V|`$, but $`\mathrm{\Delta }^kV\mathrm{\Delta }^k<|V|`$. Note that we have $`W=\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}U_2W_0`$, that gives the case (2a) of the statement for the case $`m=0`$.

Above we considered the case when in the product $`U_2^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}W`$ the word $`U_2^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}`$ was cancelling wholly with initial part of $`W`$ of with the whole $`W`$, but without further cancellations. Now, let us consider the case when $`W`$ is cancelling wholly and after that there are further cancellations in the product

$$\mathrm{\Delta }^kV\mathrm{\Delta }^k=U_1^1U_2^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}W\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}U_2U_1.$$

Remark, that it is possible only if the word $`U_2^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}`$ is a product of some initial subword $`\mathrm{\Phi }`$ and of an element from the centralizer of $`W`$, i.e.

$$U_2^1\mathrm{\Delta }_{11}^1\mathrm{\Delta }_2^k\mathrm{\Delta }_{11}\mathrm{\Phi }W^m,m$$

In this case we assume that $`m`$ is maximal integer with such property, i.e. $`\mathrm{\Phi }`$ does not contain word $`W^1`$ as a final part. Then

$$\mathrm{\Delta }^kV\mathrm{\Delta }^k=U_1^1\mathrm{\Phi }W^mWW^m\mathrm{\Phi }^1U_1=U_1^1\mathrm{\Phi }W\mathrm{\Phi }^1U_1$$

and after that $`\mathrm{\Phi }`$ is cancelling with an initial subword of $`W`$, i.e. $`W\mathrm{\Phi }^1W_0`$, where $`W_0`$ can, possibly, be empty. If $`W_0`$ is empty, then, obviously, $`U_1^1\mathrm{\Phi }^1U_1`$ must be reduced.

Case 2(iv). Suppose that $`|U|<|\mathrm{\Delta }_1|`$ and cancellations in $`W`$ starts from the final part. By the same arguments as in the Case 2(iii), we get that words $`\mathrm{\Delta }`$ and $`V`$ are of the form, described in case (2b).

If $`\mathrm{\Delta }`$ is not cyclically reduced, Lemma 4 gives the finite algorithm to find for a given reduced word $`V`$ a $`\mathrm{\Delta }`$-reduced word $`V_\mathrm{\Delta }`$ conjugated to $`V`$ by some power of $`\mathrm{\Delta }`$. If $`\mathrm{\Delta }`$ and $`V`$ are of the form represented in case (2) of Lemma 4, then we define $`V_\mathrm{\Delta }=\mathrm{\Delta }^kV\mathrm{\Delta }^k`$. In this case we say that $`V_\mathrm{\Delta }`$ is obtained from $`V`$ by $`\mathrm{\Delta }`$-reducing. If $`\mathrm{\Delta }`$ and $`V`$ are others, then we follow the same steps as described after Lemma 3.

## 5. $`\mathrm{\Delta }`$-reduced words corresponding to the same word

In general, $`V_\mathrm{\Delta }`$ is not uniquely determined by $`V`$. The following statement describes different $`\mathrm{\Delta }`$-reduced words corresponding to the same reduced word.

###### Proposition 2.

(1) Let $`V`$ be reduced and $`|V|=\mathrm{\Delta }^1V\mathrm{\Delta }`$. Then

$$\mathrm{\Delta }\mathrm{\Delta }_1\mathrm{\Delta }_{31}\mathrm{\Delta }_{21}\mathrm{\Delta }_{31}\mathrm{\Delta }_{32},$$

where $`|\mathrm{\Delta }_1|=|\mathrm{\Delta }_{32}|`$, with either

$$V\mathrm{\Delta }_1V_0\mathrm{\Delta }_{21}^1\mathrm{\Delta }_{31}^1\mathrm{\Delta }_1^1\text{or}V\mathrm{\Delta }_1\mathrm{\Delta }_{31}\mathrm{\Delta }_{21}V_0\mathrm{\Delta }_1^1,$$

where $`\mathrm{\Delta }_{31}1`$ if $`V_01`$, for some $`\mathrm{\Delta }_1,\mathrm{\Delta }_{21},\mathrm{\Delta }_{31},\mathrm{\Delta }_{32},V_0F_n`$.
(2) Let $`V`$ be reduced and $`|V|=\mathrm{\Delta }V\mathrm{\Delta }^1`$. Then

$$\mathrm{\Delta }\mathrm{\Delta }_{11}\mathrm{\Delta }_{12}\mathrm{\Delta }_{21}\mathrm{\Delta }_{12}\mathrm{\Delta }_3,$$

where $`|\mathrm{\Delta }_{11}|=|\mathrm{\Delta }_3|`$, with either

$$V\mathrm{\Delta }_3^1V_0\mathrm{\Delta }_{21}\mathrm{\Delta }_{12}\mathrm{\Delta }_3\text{or}V\mathrm{\Delta }_3^1\mathrm{\Delta }_{12}^1\mathrm{\Delta }_{21}^1V_0\mathrm{\Delta }_3,$$

where $`\mathrm{\Delta }_{12}1`$ if $`V_01`$, for some $`\mathrm{\Delta }_{11},\mathrm{\Delta }_{12},\mathrm{\Delta }_{21},\mathrm{\Delta }_3,V_0F_n`$.

###### Proof.

Let us prove the statement (1). Represent a $`\mathrm{\Delta }`$-reduced word $`V`$ in the form $`VU^1WU`$, where $`W`$ is cyclically reduced and $`U`$ is reduced (we assume that $`U`$ is empty if $`V`$ is cyclically reduced itself, i.e. $`VW`$). Since $`|V|=\mathrm{\Delta }V\mathrm{\Delta }^1`$, the word $`\mathrm{\Delta }^1V\mathrm{\Delta }\mathrm{\Delta }^1U^1WU\mathrm{\Delta }`$ admits cancellations. There are two possibilities: either there are cancellations with letters of $`W`$ or not.

Case 1: Suppose that there are cancellations of letters of $`\mathrm{\Delta }`$ with letters of $`U`$, where, possibly, $`U`$ will be cancelled wholly (the same for $`\mathrm{\Delta }^1`$ and $`U^1`$, respectively), but there no further cancellations with letters of $`W`$. Then $`UU_1\mathrm{\Delta }_1^1`$ and $`\mathrm{\Delta }\mathrm{\Delta }_1\mathrm{\Delta }_3`$, where the reduced word $`\mathrm{\Delta }_1`$ is non-empty and reduced words $`U_1`$ and $`\mathrm{\Delta }_3`$ are, possibly, empty. Therefore,

$$\mathrm{\Delta }^1V\mathrm{\Delta }\mathrm{\Delta }_3^1\mathrm{\Delta }_1^1(\mathrm{\Delta }_1U_1^1WU_1\mathrm{\Delta }_1^1)\mathrm{\Delta }_1\mathrm{\Delta }_3=\mathrm{\Delta }_3^1U_1^1WU_1\mathrm{\Delta }_3$$

where the final word is reduced. So,

$$\mathrm{\Delta }^1V\mathrm{\Delta }=|W|+2|U_1|+2|\mathrm{\Delta }_3|.$$

Since

$$|V|=|\mathrm{\Delta }_1U_1^1WU_1\mathrm{\Delta }_1^1|=|W|+2|U_1|+2|\mathrm{\Delta }_1|,$$

we get $`|\mathrm{\Delta }_1|=|\mathrm{\Delta }_3|`$. Taking $`V_0U_1^1WU_1`$, $`\mathrm{\Delta }_{32}\mathrm{\Delta }_3`$, $`\mathrm{\Delta }_{21}1`$ and $`\mathrm{\Delta }_{31}1`$ we get $`\mathrm{\Delta }`$ and $`V`$ of the same form as in the statement.

Case 2: Suppose that words $`U`$ and $`U^1`$ will be cancelled wholly and there are further cancellations with letters of $`W`$, starting either from the initial part of $`W`$ or from the final part of $`W`$, but not from both, because $`W`$ is cyclically reduced.

Case 2(i): Suppose that there are cancellations starting from the final part of $`W`$ such that, possibly, $`W`$ cancelled wholly, but there are no further cancellations. Then $`\mathrm{\Delta }\mathrm{\Delta }_1\mathrm{\Delta }_2\mathrm{\Delta }_3`$, $`U\mathrm{\Delta }_1^1`$ and $`WV_0\mathrm{\Delta }_2^1`$ for some reduced $`\mathrm{\Delta }_1,\mathrm{\Delta }_2,\mathrm{\Delta }_3,V_0F_n`$. Therefore, $`V\mathrm{\Delta }_1V_0\mathrm{\Delta }_2^1\mathrm{\Delta }_1^1`$ and $`\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }_3^1\mathrm{\Delta }_2^1V_0\mathrm{\Delta }_3`$. Since

$$|V|=|V_0|+|\mathrm{\Delta }_2|+2|\mathrm{\Delta }_1|$$

and

$$\mathrm{\Delta }^1V\mathrm{\Delta }=|V_0|+|\mathrm{\Delta }_2|+2|\mathrm{\Delta }_3|,$$

we get $`|\mathrm{\Delta }_1|=|\mathrm{\Delta }_3|`$. Taking $`\mathrm{\Delta }_{21}\mathrm{\Delta }_2`$, $`\mathrm{\Delta }_{32}\mathrm{\Delta }_3`$ and $`\mathrm{\Delta }_{31}1`$ we get $`\mathrm{\Delta }`$ and $`V`$ of the same form as in the statement (with $`V_01`$ if $`W`$ cancelled wholly).

Case 2(ii): Suppose that $`W`$ is cancelled wholly starting from the final part and after that some cancellations are still possible. Therefore, $`V_01`$, $`\mathrm{\Delta }^1V\mathrm{\Delta }\mathrm{\Delta }_3^1\mathrm{\Delta }_2^1\mathrm{\Delta }_3`$ and some cancellations of letters of $`\mathrm{\Delta }_2^1`$ and $`\mathrm{\Delta }_3`$ are possible. Thus, denoting by $`\mathrm{\Delta }_{32}`$ the part (possibly, empty) of $`\mathrm{\Delta }_3`$ which cannot be cancelled, we can write $`\mathrm{\Delta }_3\mathrm{\Delta }_{31}\mathrm{\Delta }_{32}`$ and $`\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }_{32}^1\mathrm{\Delta }_{31}^1\mathrm{\Delta }_2^1\mathrm{\Delta }_{31}\mathrm{\Delta }_{32}`$, where $`\mathrm{\Delta }_{31}^1\mathrm{\Delta }_2^1\mathrm{\Delta }_{31}`$, after possible cancellations, is cyclically reduced. So, elements $`\mathrm{\Delta }_2^1`$ and $`\mathrm{\Delta }_{31}^1\mathrm{\Delta }_2^1\mathrm{\Delta }_{31}`$ are conjugated in the free group and cyclically reduced. Therefore, the reduction of the word $`\mathrm{\Delta }_{31}^1\mathrm{\Delta }_2^1\mathrm{\Delta }_{31}`$ is a cyclic permutation of the word $`\mathrm{\Delta }_2^1`$, so $`\mathrm{\Delta }_2^1=\mathrm{\Delta }_{21}^1\mathrm{\Delta }_{31}^1`$ and $`\mathrm{\Delta }_{31}^1\mathrm{\Delta }_2^1\mathrm{\Delta }_{31}^1=\mathrm{\Delta }_{31}^1\mathrm{\Delta }_{21}^1\mathrm{\Delta }_{31}^1\mathrm{\Delta }_{31}=\mathrm{\Delta }_{31}^1\mathrm{\Delta }_{21}^1`$. Hence

$$\mathrm{\Delta }\mathrm{\Delta }_1\mathrm{\Delta }_2\mathrm{\Delta }_3\mathrm{\Delta }_1\mathrm{\Delta }_{31}\mathrm{\Delta }_{21}\mathrm{\Delta }_{31}\mathrm{\Delta }_{32},$$

$$V\mathrm{\Delta }_1\mathrm{\Delta }_2^1\mathrm{\Delta }_1^1\mathrm{\Delta }_1\mathrm{\Delta }_{21}^1\mathrm{\Delta }_{31}^1\mathrm{\Delta }_1^1$$

and

$$\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }_3^1\mathrm{\Delta }_2^1\mathrm{\Delta }_3=\mathrm{\Delta }_{32}^1\mathrm{\Delta }_{31}^1\mathrm{\Delta }_{21}^1\mathrm{\Delta }_{31}^1\mathrm{\Delta }_{31}\mathrm{\Delta }_{32}=\mathrm{\Delta }_{32}^1\mathrm{\Delta }_{31}^1\mathrm{\Delta }_{21}^1\mathrm{\Delta }_{32}.$$

Since

$$|V|=2|\mathrm{\Delta }_1|+|\mathrm{\Delta }_{21}|+|\mathrm{\Delta }_{31}|$$

and

$$\mathrm{\Delta }^1V\mathrm{\Delta }=2|\mathrm{\Delta }_{32}|+|\mathrm{\Delta }_{21}|+|\mathrm{\Delta }_{31}|,$$

we get $`|\mathrm{\Delta }_1|=|\mathrm{\Delta }_{32}|`$. Taking $`V_01`$ we get that $`\mathrm{\Delta }`$ and $`V`$ are of the same form as in the statement.

Case 2(iii): Suppose that there are cancellations starting from the initial part of $`W`$ such that, possibly, $`W`$ cancelled wholly, but there no further cancellations. Then $`\mathrm{\Delta }\mathrm{\Delta }_1\mathrm{\Delta }_2\mathrm{\Delta }_3`$, $`U\mathrm{\Delta }_1^1`$ and $`W\mathrm{\Delta }_2V_0`$ for some reduced words $`\mathrm{\Delta }_1,\mathrm{\Delta }_2,\mathrm{\Delta }_3,V_0F_n`$. Therefore, $`V\mathrm{\Delta }_1\mathrm{\Delta }_2V_0\mathrm{\Delta }_1^1`$ and $`\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }_3^1V_0\mathrm{\Delta }_2\mathrm{\Delta }_3`$. Since

$$|V|=|V_0|+|\mathrm{\Delta }_2|+2|\mathrm{\Delta }_1|$$

and

$$\mathrm{\Delta }^1V\mathrm{\Delta }=|V_0|+|\mathrm{\Delta }_2|+2|\mathrm{\Delta }_3|,$$

we get $`|\mathrm{\Delta }_1|=|\mathrm{\Delta }_3|`$. Taking $`\mathrm{\Delta }_{21}\mathrm{\Delta }_2`$, $`\mathrm{\Delta }_{32}\mathrm{\Delta }_3`$ and $`\mathrm{\Delta }_{31}1`$ we get that $`\mathrm{\Delta }`$ and $`V`$ are of the form as in the statement.

Case 2(iv): Suppose that $`W`$ is cancelled wholly (starting from the initial part) and after that some cancellations are still possible. Therefore, $`V_01`$, $`\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }_3^1\mathrm{\Delta }_2\mathrm{\Delta }_3`$ and some cancellations of letters of $`\mathrm{\Delta }_3^1`$ and $`\mathrm{\Delta }_2`$ are possible. Denoting by $`\mathrm{\Delta }_{32}^1`$ the part (possibly, empty) of $`\mathrm{\Delta }_3^1`$ which can not be cancelled, we can write $`\mathrm{\Delta }_3^1\mathrm{\Delta }_{32}^1\mathrm{\Delta }_{31}^1`$, so $`\mathrm{\Delta }_3\mathrm{\Delta }_{31}\mathrm{\Delta }_{32}`$. Therefore we get $`\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }_3^1\mathrm{\Delta }_2\mathrm{\Delta }_3=\mathrm{\Delta }_{32}^1\mathrm{\Delta }_{31}^1\mathrm{\Delta }_2\mathrm{\Delta }_{31}\mathrm{\Delta }_{32}`$, where $`\mathrm{\Delta }_{31}^1\mathrm{\Delta }_2\mathrm{\Delta }_{31}`$, after possible cancellations, is cyclically reduced. Elements $`\mathrm{\Delta }_2`$ and $`\mathrm{\Delta }_{31}^1\mathrm{\Delta }_2\mathrm{\Delta }_{31}`$ are conjugated in the free group and cyclically reduced. Therefore, the reduction of the word $`\mathrm{\Delta }_{31}^1\mathrm{\Delta }_2\mathrm{\Delta }_{31}`$ is a cyclic permutation of the word $`\mathrm{\Delta }_2^1`$, so $`\mathrm{\Delta }_2=\mathrm{\Delta }_{31}\mathrm{\Delta }_{21}`$ and $`\mathrm{\Delta }_{31}^1\mathrm{\Delta }_2\mathrm{\Delta }_{31}=\mathrm{\Delta }_{31}^1\mathrm{\Delta }_{31}\mathrm{\Delta }_{21}\mathrm{\Delta }_{31}=\mathrm{\Delta }_{21}\mathrm{\Delta }_{31}`$. Hence

$$\mathrm{\Delta }\mathrm{\Delta }_1\mathrm{\Delta }_2\mathrm{\Delta }_3\mathrm{\Delta }_1\mathrm{\Delta }_{31}\mathrm{\Delta }_{21}\mathrm{\Delta }_{31}\mathrm{\Delta }_{23},$$

$$V\mathrm{\Delta }_1\mathrm{\Delta }_2\mathrm{\Delta }_1^1\mathrm{\Delta }_1\mathrm{\Delta }_{31}\mathrm{\Delta }_{21}\mathrm{\Delta }_1^1,$$

and

$$\mathrm{\Delta }^1V\mathrm{\Delta }=\mathrm{\Delta }_3^1\mathrm{\Delta }_2\mathrm{\Delta }_3=\mathrm{\Delta }_{32}^1\mathrm{\Delta }_{31}^1\mathrm{\Delta }_{31}\mathrm{\Delta }_{21}\mathrm{\Delta }_{31}\mathrm{\Delta }_{32}=\mathrm{\Delta }_{32}^1\mathrm{\Delta }_{21}\mathrm{\Delta }_{31}\mathrm{\Delta }_{32}.$$

Since

$$|V|=2|\mathrm{\Delta }_1|+|\mathrm{\Delta }_{21}|+|\mathrm{\Delta }_{31}|$$

and

$$\mathrm{\Delta }^1V\mathrm{\Delta }=2|\mathrm{\Delta }_{32}|+|\mathrm{\Delta }_{21}|+|\mathrm{\Delta }_{31}|,$$

we get $`|\mathrm{\Delta }_1|=|\mathrm{\Delta }_{32}|`$. Taking $`V_01`$ we get that $`\mathrm{\Delta }`$ and $`V`$ are of the form as in the statement.

The statement (2) follows by similar considerations. ∎

## 6. Constructing of $`\phi `$-twisted conjugated normal form

Let $`V`$ and $`V^{}`$ be words in the alphabet $`𝕏`$. If there exists $`XF_n`$ such that $`V^{}=\phi (X^1)VX`$, we say that $`V^{}`$ and $`V`$ are $`\phi `$-twisted conjugated, and that $`V^{}`$ is obtained from $`V`$ by $`\phi `$-twisted conjugation by $`X`$. Obviously, the property to be $`\phi `$-twisted conjugated is equivalence relation in the group $`F_n`$. Using this definition, the Makanin’s question can be reformulated as the following: is there exists an algorithm that admits for a given pair of elements $`U`$ and $`V`$ of a free group $`F_n`$ to decide if they are $`\phi `$-twisted conjugated.

In virtue of Lemma 2 the equality $`\phi (\mathrm{\Delta }^k)=\mathrm{\Delta }^k`$ holds for any integer $`k`$. Therefore, if elements $`U`$ and $`V`$ are conjugated by some power of $`\mathrm{\Delta }`$, they are $`\phi `$-twisted conjugated.

Below we will construct an algorithm to choose a unique representative for each class of $`\phi `$-twisted conjugated elements. We will call this representative the $`\phi `$-twisted conjugated normal form. It will be shown that two elements of $`F_n`$ are $`\phi `$-twisted conjugated if and only if their $`\phi `$-twisted conjugated normal forms coincide.

If length of a reduced word $`U`$ in the alphabet $`𝕏`$ is bigger than $`1`$ then it can be represented as a product $`UU^{}U^{\prime \prime }`$ of two nonempty reduced words. The word $`U^{}`$ will be referred to as an initial part of $`U`$ and $`U^{\prime \prime }`$ will be referred as a final part of $`U`$. Denote by $`I(U)`$ the set of all initial parts of $`U`$ and by $`F(U)`$ the set of all final parts of $`U`$.

For a word $`U`$ and an integer $`\mathrm{}`$ we denote by $`\phi ^{\mathrm{}}(U)`$ the word obtained from $`U`$ by replacing (graphically) each letter $`u`$ of $`U`$ by its image $`\phi ^{\mathrm{}}(u)`$, and denote by $`U_{[\mathrm{}]}`$ the word obtained after reducing of $`\phi ^{\mathrm{}}(U)`$.

Let $`VV^{}V^{\prime \prime }`$ be a reduced word in the alphabet $`𝕏`$, where $`V^{}I(V)`$, $`V^{\prime \prime }F(V)`$. The word $`V_{[1]}^{\prime \prime }V^{}`$ (that represents the element $`\phi (V^{\prime \prime })V(V^{\prime \prime })^1`$ is said to be a cyclic $`\phi `$-shift of a final part of $`VV^{}V^{\prime \prime }`$ and the word $`V^{\prime \prime }V_{[1]}^{}`$, that represents the element

$$\phi ([\phi ^1(V^{})]^1)V\phi ^1(V^{})=(V^{})^1V\phi ^1(V^{}),$$

is said to be a cyclic $`\phi `$-shift of an initial part of $`VV^{}V^{\prime \prime }`$. If $`|V^{}|=1`$, i.e. $`V^{}=x_i^\epsilon `$, $`\epsilon =\pm 1`$, then the corresponding $`\phi `$-shift of the initial part will be referred to as a cyclic $`\phi `$-shift of the initial letter. If $`|V^{\prime \prime }|=1`$ then the corresponding $`\phi `$-shift of the final part will be referred to as a cyclic $`\phi `$-shift of the final letter.

A reduced word $`V`$ will be referred to as a cyclically $`\phi `$-reduced if neither a cyclic $`\phi `$-shift of its final letter nor a cyclic $`\phi `$-shift of its initial letter do not decrease length of $`V`$. Obviously, applying cyclic $`\phi `$-shifts of the final letter (as well as of the initial letter) to a given word $`V`$, after a finite number of steps we will obtain a cyclically $`\phi `$-reduced word corresponding to $`V`$.

Now let us construct conjugated normal form for a word $`V`$. Without loss of generality (applying, if necessary, finite number of steps of above described $`\mathrm{\Delta }`$-reducings and cyclic $`\phi `$-shifts), we can assume that $`V`$ is $`\mathrm{\Delta }`$-reduced and cyclically $`\phi `$-reduced.

For given $`V`$ let $`𝒱_\mathrm{\Delta }`$ be the set, consisting of $`V`$ and all words which are conjugated to $`V`$ by powers of $`\mathrm{\Delta }`$ and are $`\mathrm{\Delta }`$-reduced. In virtue of Lemma 3 and Lemma 4, the set $`𝒱_\mathrm{\Delta }`$ is finite. Applying to all elements of $`𝒱_\mathrm{\Delta }`$ cyclic $`\phi `$-shifts of all initial parts and all final parts, we will construct the set $`(𝒱_\mathrm{\Delta })_\phi `$. Applying $`\mathrm{\Delta }`$-reducing to all element of $`(𝒱_\mathrm{\Delta })_\phi `$, we will construct the set of $`\mathrm{\Delta }`$-reduced words $`((𝒱_\mathrm{\Delta })_\phi )_\mathrm{\Delta }`$. And finally, applying, if necessary, cyclic $`\phi `$-shifts of the final letter and of the initial letter to words from $`((𝒱_\mathrm{\Delta })_\phi )_\mathrm{\Delta }`$, will construct the set $`D_0(V)=(((𝒱_\mathrm{\Delta })_\phi )_\mathrm{\Delta })_\phi `$ of $`\mathrm{\Delta }`$-reduced and cyclically $`\phi `$-reduced words.

Recall that in the free group the set of words obtained from a given word $`V`$ by cyclic shifts is finite. But the set of words obtained from $`V`$ by cyclic $`\phi `$-shifts can be infinite. Indeed, it is clear from relations

$$\left[\phi ^k(V)\phi ^{k1}(V)\mathrm{}\phi (V)\right]V\left[V^1\phi (V^1)\mathrm{}\phi ^{k1}(V^1)\right]=\phi ^k(V),$$

for $`k>0`$ and

$$\left[\phi ^k(V^1)\phi ^{k+1}(V^1)\mathrm{}V^1\right]V\left[\phi ^1(V)\mathrm{}\phi ^{k+1}(V)\phi ^k(V)\right]=\phi ^k(V),$$

for $`k<0`$, that $`V`$ is $`\phi `$-twisted conjugated to $`\phi ^k(V)`$ for any integer $`k`$.

For each integer $`k`$ we define a set $`D_k(V)=D_0(\phi ^k(V))`$ and define $`D(V)=_kD_k(V)`$. Let us verify that $`D(V)`$ is finite.

###### Lemma 5.

The following equality holds:

$$D(V)=\underset{k\{0,1,\mathrm{},m1\}}{}D_k(V).$$

###### Proof.

Let $`r`$, satisfying $`0r<m`$, be such that $`k=mq+r`$, $`q`$. By Lemma 2,

$$\phi ^k(V)=\mathrm{\Delta }^q\phi ^r(V)\mathrm{\Delta }^q.$$

We show that $`D_k(V)=D_r(V)`$, that will imply the statement. Indeed, by the definition, $`D_k(V)=D_0(\mathrm{\Delta }^q\phi ^r(V)\mathrm{\Delta }^q)`$. Denote $`UV_{[r]}=\phi ^r(V)`$ and consider elements from $`D_0(U)=D_0(\phi ^r(V))`$. By the definition, $`D_0(U)`$ consists of words $`\phi (U^{\prime \prime })U^{}`$ and $`U^{\prime \prime }\phi ^1(U^{})`$ (for all pairs of initial and final parts of $`UU^{}U^{\prime \prime }`$) to which $`\mathrm{\Delta }`$-reducing and cyclic $`\phi `$-reducing are applied. To construct $`D_k(V)`$ we need to pass from the word $`\mathrm{\Delta }^q\phi ^r(V)\mathrm{\Delta }^q`$ to a $`\mathrm{\Delta }`$-reduced word, which, in a general case, can be different from $`U\phi ^r(V)`$. But, according to the definition of $`D_0(V)`$, the set of $`\mathrm{\Delta }`$-reduced words constructed from $`\mathrm{\Delta }^q\phi ^r(V)\mathrm{\Delta }^q`$ coincides with the set of $`\mathrm{\Delta }`$-reduced words constructed from $`\phi ^r(V)`$. So, corresponding sets of all cyclic $`\phi `$-shifts of initial parts and of final parts also coincide. Therefore, $`D_k(V)=D_0(\phi ^r(V))=D_r(V)`$. ∎

###### Lemma 6.

The set $`D(V)`$ has the following properties:
(1) If $`UD(V)`$ then $`D(U)=D(V)`$;
(2) If $`V`$ and $`W`$ are $`\phi `$-twisted conjugated, and each of them is $`\mathrm{\Delta }`$-reduced and cyclically $`\phi `$-reduced, then $`D(V)=D(W)`$.

###### Proof.

Since $`D(V)`$ consists of words which are $`\phi `$-twisted conjugated in $`F_n`$, item (2), obviously, implies (1). Let us prove (2). Firstly we remark that if $`W`$ is obtained from $`V`$ by a $`\phi `$-shift of an initial part or a $`\phi `$-shift of a final part, then, obviously, $`D(W)=D(V)`$. Now assume that $`W`$ and $`V`$ are related by $`W=U_{[1]}^1VU`$ for some reduced $`UF_n`$. Since $`W`$ is cyclically $`\phi `$-reduced, the product $`U_{[1]}^1VU`$ contains cancellations. Moreover, these cancellations are either in the product $`U_{[1]}^1V`$ or in the product $`VU`$, but not in the both, since by the assumption $`V`$ is $`\phi `$-reduced. There are two possibilities: $`V`$ will be cancelled wholly or not.

Case 1: Suppose $`V`$ is not cancelling wholly.

Case 1(i): Suppose that there are cancellations in the product $`U_{[1]}^1V`$. Then $`U_{[1]}^1`$ must be cancelled wholly, since $`W`$ is assumed to be $`\phi `$–reduced, and so $`VU_{[1]}V_1`$. Then

$$W=U_{[1]}^1VUU_{[1]}^1(U_{[1]}V_1)U=V_1U$$

and $`WV_1U`$ is obtained from $`VU_{[1]}V_1`$ by the $`\phi `$-shift of the initial part $`U_{[1]}`$. Therefore, $`D(V)=D(W)`$.

Case 1(ii): Suppose that there are cancellations in the product $`VU`$. Then $`U`$ must be cancelled wholly since $`W`$ is assumed to be $`\phi `$–reduced, and so $`VV_1U^1`$. Then

$$W=U_{[1]}^1VUU_{[1]}^1(V_1U^1)U=U_{[1]}^1V_1$$

and $`WU_{[1]}^1V_1`$ is obtained from $`VV_1U^1`$ by the $`\phi `$-shift of the final part $`U^1`$. Therefore, $`D(V)=D(W)`$.

Case 2: Suppose that $`V`$ is cancelling wholly. We will use induction by length of the word $`U`$.

Case 2(i): Suppose that $`V`$ is cancelling wholly in the product $`VU`$ and after that there are cancellations of letters of the remaining part of $`U`$ with letters of $`U_{[1]}^1`$. Then we can represent $`UV^1U_1`$, therefore $`U_{[1]}^1=U_{1[1]}^1V_{[1]}`$ and

$$U_{[1]}^1VU=U_{1[1]}^1V_{[1]}VV^1U_1=U_{1[1]}^1V_{[1]}U_1.$$

If $`U_1`$ is cancelling wholly with $`V_{[1]}`$, then $`V_{[1]}V_2U_1^1`$ and

$$U_{1[1]}^1V_{[1]}U_1U_{1[1]}^1V_2U_1^1U_1=U_{1[1]}^1V_2=W.$$

Remark that $`W`$ arises in the process of the construction of $`D_1(V)`$. Indeed,

$$D_1(V)=D_0(V_{[1]})=D_0(V_2U_1^1)$$

and $`W`$ is obtained from $`V_2U_1^1`$ by the cyclic $`\phi `$-shift of the final part. If, again, $`V_{[1]}`$ is cancelling wholly with $`U_1`$, then the statement follows from the induction assumption.

Case 2(ii): Let there be a cancellation in the product $`U_{[1]}^1V`$ with $`V`$ cancelling wholly and remaining part of $`U_{[1]}^1`$ cancelling with $`U`$, i.e. $`U_{[1]}^1U_1^1V^1`$, $`U=\phi ^1(V)\phi ^1(U_1)`$ and

(1)
$$U_{[1]}^1VU=U_1^1V^1VV_{[1]}U_{1[1]}=U_1^1V_{[1]}U_{1[1]}.$$

If $`U_1^1`$ is cancelling wholly with $`V_{[1]}`$, then $`V_{[1]}=U_1V_2`$ and we get $`U_1^1V_{[1]}U_{1[1]}=U_1^1(U_1V_2)U_{1[1]}=V_2U_{1[1]}`$, i.e. $`V=U_{1[1]}V_{2[1]}`$ and $`WV_2U_{1[1]}`$. Comparing these words we see that $`W`$ belongs to $`D_1(V)`$. Indeed, by the definition,

$$D_1(V)=D_0(\phi ^1(V))=D_0(U_1V_2).$$

Applying to $`U_1V_2`$ the cyclic $`\phi `$-shift of the initial part $`U_1`$, we will get $`W=V_2U_{1[1]}`$. The case when $`V_{[1]}`$ is cancelling wholly with $`U_1^1`$ in (1) follows from the induction assumption. ∎

Now we are able to complete the proof of Theorem 1.

###### Proof.

For given $`V`$ we have constructed the finite set $`D(V)`$. From this set we choose words of minimal length, and after that, from such words choose the word which is minimal in respect to the above defined ordering on $`𝔽_n`$. Denote this word by $`\overline{V}`$ and call it the normal $`\phi `$-twisted conjugated form for $`V`$.

Let $`U`$ and $`V`$ be reduced words in the free group $`F_n`$. Let us construct words $`\overline{U}`$ and $`\overline{V}`$, which are normal $`\phi `$-conjugated forms for $`U`$ and $`V`$, respectively. In virtue of Lemma 5, $`\overline{U}=\overline{V}`$ if and only if elements $`U`$ and $`V`$ are $`\phi `$-twisted conjugated in $`F_n`$, that means, by the definition, that equation $`\phi (X)U=VX`$ is solvable in $`F_n`$. The proof is completed. ∎


format: text

text:
# Untitled Document

Abstract

We have performed a search for the rare leptonic decay $`B^+\mu ^+\nu _\mu `$ with data collected at the $`\mathrm{{\rm Y}}(4S)`$ resonance by the B A B AR experiment at the PEP-II storage ring. In a sample of 88.4 million $`B\overline{B}`$ pairs, we find no significant evidence for a signal and set an upper limit on the branching fraction $`(B^+\mu ^+\nu _\mu )<6.6\times 10^6`$ at the 90% confidence level.


text:
# A search for microquasar candidates at low galactic latitudes

## 1 Introduction

Microquasars are X-ray binary systems with the ability to generate relativistic jets. The presence of such collimated features is considered to be the unmistakable fingerprint of their microquasar nature. The jets are seen thanks to their synchrotron emission at radio wavelengths, that can be resolved with modern interferometers. Hence, all microquasars belong to the class of Radio Emitting X-ray Binaries (REXBs), which contains about $`50`$ sources among the $`280`$ known X-ray binaries (Liu et al. liu00 (2000); Liu et al. liu01 (2001)).

The discovery of microquasars, so far only in our Galaxy, illustrates how sometimes nature mimics itself at scales orders of magnitude different. The interesting analogy between quasars and microquasars, both from the morphological and physical point of view, has been pointed out by several authors. In addition, microquasars are considered to be good laboratories for understanding the physics of accretion/ejection processes and strong gravitational fields (see, e.g., Mirabel & Rodríguez mirabel99 (1999)). The key parameter that distinguishes the quasar/microquasar properties is believed to be the mass of the compact object in the central engine, varying over nine orders of magnitude from supermassive to stellar-mass black holes. The most recent findings of microquasars have been summarized in Castro-Tirado et al. (castro01 (2001)).

The current census of microquasar sources in the Galaxy amounts to 14 systems (Mirabel & Rodríguez mirabel99 (1999), Rodríguez & Mirabel rodriguez01 (2001)), with LS~5039 (Paredes et al. paredes00 (2000)), Cyg~X-1 (Stirling et al. stirling01 (2001)) and XTE~J1550$-$564 (Hannikainen et al. hannikainen01 (2001)) as the most recent additions. This number could increase dramatically if, as it has been proposed by Fender & Hendry (fender00 (2000)), radio emission from X-ray binaries always arises from relativistic jets. This would imply that all REXBs are microquasars. However, the situation is not so clear yet and REXBs appear as a rather heterogeneous group including both high-mass (e.g., Cyg~X-3, LS~I~+61~303) and low-mass companions (e.g., Aql~X-1, GX~339$-$4). Moreover, in the latter group, radio emission has been detected in both atoll and Z-type sources. In addition, the detection of radio emission does not seem to be limited to a particular type of compact object, since there are REXBs harboring black holes (e.g., GRO~J1655$-$40, Cyg~X-1) and neutron stars (e.g., Aql~X-1, Sco~X-1). Moreover, when one begins to further divide the group of REXBs according to their optical or compact companion or whether radio jets are present or not, the number of systems is no longer enough to perform a meaningful statistical study.

For example, the systems whose compact companion is believed to be a black hole appear to have jet velocities above $`0.9c`$, while those with neutron stars appear to exhibit slower jet flows with speeds below $`0.5c`$ (Mirabel & Rodríguez mirabel99 (1999)). However, Fomalont et al. (fomalont01 (2001)) have measured speeds up to $`0.57c`$ in the neutron star system Sco~X-1, and a lower limit of only $`0.6c`$ has been derived for the black hole system Cyg~X-1 by Stirling et al. (stirling01 (2001)), while systems like Cyg~X-3, where the nature of the compact object is unknown, exhibit flows with intermediate speeds of $`0.5c`$ (Martí et al. marti01 (2001)). Therefore, some questions arise: is there a true correlation? what is the speed limit of the jets in neutron star systems, if any?

Another interesting issue is the possibility of microquasars being sources of high energy $`\gamma `$-rays. Up to now, the most promising candidate is LS~5039, which appears to be associated with the third EGRET catalog (Hartman et al. hartman99 (1999)) source 3EG~J1824$-$1514 (Paredes et al. paredes00 (2000)). On the other hand, the 26.5 d periodic REXB LS~I~+61~303 could be associated with the source 3EG~J0241+6103 (Kniffen et al. kniffen97 (1997)). Although these associations will only be confirmed, or discarded, by future missions such as GLAST, clearly a sample of two sources is a very poor one, and any attempt to discover new REXBs/microquasars, and look for possible high energy $`\gamma `$-ray emission, is warranted.

Hence, the reduced population known gave us a strong motivation to start a long-term project focused on searching for new microquasars in the Galaxy. In this context, X-ray, optical and radio catalogs provide a fundamental tool for the search of new sources with known multiwavelength behavior. Therefore, we have used the best available X-ray and radio catalogs to search for new REXB candidates on the basis of positional coincidence, together with very restrictive selection criteria. As a result we have obtained a sample of 13 radio emitting X-ray sources, which is expected to contain at least some galactic X-ray binaries. For 6 of the selected candidates, a deep study involving optical and VLA high resolution observations was carried out in order to better determine their positions and nature. After these observations, all but one of the sources have appeared unresolved, even at the highest VLA resolution, and the positions are known to better than 0.01 arcsecond accuracy. Optical spectroscopy is also currently in progress to confirm the stellar nature of our candidates, while already carried out VLBI observations will be reported in a future paper.

In this paper we present the results of the cross-identification together with radio and optical astrometry and photometry of these sources. We explain the developed cross-identification method in Sect. 2. We present the follow-up radio observations in Sect. 3, while the optical ones are described in Sect. 4. An analysis of the obtained data and the corresponding discussion are presented in Sect. 5. We finally state our conclusions in Sect. 6.

## 2 Cross-identification between RBSC and NVSS catalogs

In order to find new microquasar candidates we have to search for new REXBs. The first step, hence, has consisted of a positional cross-identification of X-ray and radio sources using the most complete available catalogs at both wavelengths, namely the ROSAT all sky Bright Source Catalog (RBSC) and the NRAO VLA Sky Survey (NVSS), which are briefly introduced now.

In the X-ray domain, the RBSC (Voges et al. voges99 (1999)) contains in its current version a total of 18 806 sources in the energy band 0.1–2.4 keV, and is derived from the ROSAT All Sky Survey (Voges et al. voges96 (1996)). Four energy bands in the following ranges of keV are provided: $`A`$=0.1–0.4, $`B`$=0.5–2.0, $`C`$=0.5–0.9, $`D`$=0.9–2.0. From these bands, two hardness ratios are computed: $`HR1=(BA)/(B+A)`$, $`HR2=(DC)/(D+C)`$. The 1$`\sigma `$ positional uncertainties are typically in the range 10–20$`\mathrm{}`$.

In the radio domain, the NVSS (Condon et al. condon98 (1998)) catalog covers the sky north of $`\delta =40\mathrm{°}`$ (82% of the celestial sphere) at a frequency of 1.4 GHz (20 cm wavelength) using the VLA configurations D and DnC. It contains over $`1.8\times 10^6`$ sources stronger than its 2.5 mJy completeness limit. The rms positional uncertainties are less than $`1\mathrm{}`$ for sources stronger than 15 mJy and $`7\mathrm{}`$ for the faintest detectable sources.

Since our aim is to maximize the probability of retaining only galactic REXB systems by cross-identifying the RBSC and the NVSS catalogs, we have adopted the following selection criteria:

1. Sources with absolute galactic latitude $`<5\mathrm{°}`$ have been selected from the RBSC catalog. Since the NVSS has a limit of $`\delta >40\mathrm{°}`$, only the RBSC sources above this declination have been allowed to continue in the selection process. Therefore, approximately 75% of the whole $`|b|<5\mathrm{°}`$ area is covered ($`l347`$$`259\mathrm{°}`$ and $`\alpha 17.2`$$`8.6^\mathrm{h}`$).
2. Among the remaining RBSC sources, those containing screening flags about nearby sources contaminating measurements or problems with position determinations (Voges et al. voges99 (1999)) have been rejected.
3. From statistical RBSC identification studies, Motch et al. (motch98 (1998)) concluded that X-ray binaries are essentially recognizable from their hard X-ray spectra. Therefore, in an attempt to avoid AGNs and cataclysmic variables, we have only selected the sources with $`HR1+\sigma (HR1)`$ higher than 0.9. Although this criterion would exclude microquasars in an outburst, we note that this situation only lasts a short time of their life, and the probability of discarding one of them is very low. A total of 241 RBSC sources remain in our sample at this stage.
4. The X-ray and radio positions must agree within errors. For this purpose, we have selected NVSS sources within the 2$`\sigma `$ (95% probability) error boxes of the RBSC sources. We have also used the constraint of a maximum offset of 40$`\mathrm{}`$ between the RBSC and the NVSS positions, since, for higher distances, no reliable identification is expected (Voges et al. voges99 (1999)).
5. No extended radio source has been allowed to continue in the selection process, since any REXB is expected to appear compact at the NVSS resolution111The sources resolved only in one axis and with an angular size smaller than the other axis were allowed to continue on the process..

The sources selected with the RBSC/NVSS cross-identification, a total of 35, were then filtered with complementary optical information using the following criteria:

1. We have inspected the SIMBAD database and the NASA/IPAC Extragalactic Database (NED) for each source, and if it is listed as an extragalactic object, we have obviously rejected it from the sample.
2. We have also inspected the Digitized Sky Survey, DSS1 and DSS2-red images222http://archive.eso.org/dss/dss/, and looked for possible optical counterparts with position agreement with the NVSS sources. If an optical object is present and displays extended emission, i.e., with a galaxy-like appearance, it has also been removed from the sample.

At the end of this process the resulting sample contained 16 sources. Among them, we found the well known REXB LS~I~+61~303, which displays a one-sided jet at milliarcsecond scales (Massi et al. massi01 (2001)). We also recovered the well known microquasars LS~5039, SS~433 and Cyg~X-3. It is interesting to note that all these sources are HMXB, and none of the known microquasars with low mass companions were found by this technique. This can be easily explained by the fact that most of LMXB are transients, and the remaining persistent ones are too faint to be present in the NVSS. Moreover, all but one HMXB persistent microquasars in our explored range of galactic latitudes, namely LS~5039, SS~433 and Cyg~X-3, have been recovered by our cross-identification method. The remaining one, namely Cyg~X-1, although marginally present in the corresponding NVSS image, does not appear in the NVSS catalog. This was probably due to the source low flux density and diffuse background around it, which prevented its automatic detection by the source search software.

After removing the previously known sources of our sample, we ended with a total of 12 new unidentified REXB candidates. Among them, 7 had offsets between the X-ray and radio positions within the 1$`\sigma `$ RBSC position error, and belong to the hereafter Group 1 sample. The other 5 sources had offsets between 1–2$`\sigma `$ and form the Group 2 sample.

When we started this project in 1998 another source fullfiled all the selection criteria. Now we have performed the cross-identification process again, in order to present here an updated version of it, and we have found that this source, namely 1RXS~J072418.3$-$071508, was identified by Perlman et al. (perlman98 (1998)) as a quasar (WGA~J0724.3$-$0715 in their paper and listed as PMN~J0724$-$0715 in the NED database). Although it is clear that it is not any more a REXB candidate, we have preferred to include it in the list and present the observational results obtained up to now. Since the corresponding offset in position for this object is less than 1$`\sigma `$, it is included in Group 1.

All the sources belonging to Group 1 (a total of 8), Group 2 (a total of 5) and the already known REXBs are listed in Table 1, where Cols. 1 to 4 contain the RBSC names (which also provide the positions), the 1$`\sigma `$ errors in position, the count rates, and $`HR1`$. In Col. 5 we show the offsets between the RBSC and the NVSS positions. In Cols. 6 to 8 we list the NVSS names (which provide a limited position information), the 1$`\sigma `$ errors in position and the NVSS flux densities (at 20 cm wavelength). Finally, galactic coordinates for all sources are listed in Cols. 9 and 10. The horizontal line divides the two groups of sources and the already known REXBs.

In this paper we will focus on the Group 1 sources, while Group 2 sources will be eventually studied in the future. In order to have a look at the targets, we show in Fig. 1, for each source of Group 1, the NVSS radio contours overlaid on $`6\mathrm{}\times 6\mathrm{}`$ optical DSS1 images. To mark the RBSC positions we have plotted as open crosses the $`3\sigma `$ errors in position, allowing a better display than if we had plotted the $`1\sigma `$ errors.

As can be seen in Table 1, the NVSS errors are much smaller than the RBSC ones. Hence, the radio positions are more accurate than the X-ray ones to look for optical counterparts. An inspection of the DSS1 images in Fig. 1 reveals that some candidates have an optical counterpart approximately in the middle of the radio contours, while others do not. This is understandable because of the low galactic latitude of these objects, which implies a high degree of extinction along the line of sight. On the other hand, crowded fields near the galactic plane also prevent us to be sure about the counterparts detected. Therefore, the next step of the process is to obtain accurate radio positions and then search for possible optical counterparts.

## 3 Radio observations

The main goal of the radio observations was to obtain accurate sub-arcsecond positions, but we also wished to monitor the variability of radio flux and spectrum of our targets. On the other hand, it was also important to investigate the source structure beyond the NVSS resolution. For REXBs, most of the source flux density is expected to be concentrated in a compact core plus possible arcsecond or sub-arcsecond extended features. By observing each target with the VLA in A configuration, we were able to verify to what extend our sources were indeed compact, and to look for possible elongations or jets.

To this end, multi-frequency and multi-epoch observations of the Group 1 sources were carried out with the NRAO333The National Radio Astronomy Observatory is a facility of the National Science Foundation operated under cooperative agreement by Associated Universities, Inc. VLA in A configuration. We did not observe 1RXS~J181119.4$-$275939 and 1RXS~J185002.8$-$075833, the last two sources of Group 1 in Table 1, because they had very different right ascensions, compared to the other sources, and were not visible during the scheduled VLA observing time.

Three VLA A configuration observing sessions were carried out on 1999 July 9, 22 and 30 at 3.6 cm (8.4 GHz) and 6 cm (5 GHz) wavelengths (frequencies). A typical observation consisted of 14 minutes at 3.6 cm and 4 minutes at 6 cm on each target, preceded and followed by a 2 minute observation of a phase calibrator. During the last observing session, July 30, we included two additional 20 cm (1.4 GHz) measurements of 1RXS~J072259.5$-$073131 and 1RXS~J072418.3$-$071508. The amplitude calibrator used in all cases was 3C~48, while we used the phase calibrator J0102+584 for the first two sources, J0359+509 and J0603+177 for the third and fourth sources, respectively, and finally J0730$-$116 for the last two sources. The data were edited and calibrated using the AIPS software package of NRAO.

### 3.1 Results

All sources were detected at all frequencies, allowing us to obtain accurate positions and flux density measurements. To achieve the first goal, we made use of the phase-reference technique to calibrate the data at 3.6 cm wavelength, the ones with the highest angular resolution. Then we concatenated all these data for each source, with the task DBCON within AIPS. Finally, we performed uniform weighted maps from which positions were obtained after fitting elliptical Gaussians using JMFIT within AIPS. A realistic estimate of the position error is about $`0.01\mathrm{}`$.

In order to obtain good quality maps, once accurate positions were known, we carried out a similar process, but using phase self-calibration with the previously obtained positions for each individual snapshot at 3.6 cm wavelength. This was not possible for 1RXS~J042201.0+485610 because the flux density was too low and prevented self-calibration. The resulting uniform weighted maps, together with the optical images that will be presented in the following section, are shown in Fig. 2.

The flux densities of all sources were measured as follows. First of all we self-calibrated all snapshots at all wavelengths (again with the exception of 1RXS~J042201.0+485610). Then we performed natural weighted maps with improved dynamic range, from which flux densities were measured using again elliptical Gaussian fits.

The obtained results for all observed sources are summarized in Table 2. In Col. 1 we list the RBSC object names, while in Cols. 2 and 3 we show the radio positions derived from our phase-referenced uniform weighted maps of all concatenated 3.6 cm wavelength observations. In Col. 4 we list the observing dates and, in Cols. 5 and 6, the corresponding flux densities at both observing wavelengths, measured on the self-calibrated natural weighted maps. The flux density errors quoted are the rms noise of the maps in mJy beam-1. In Col. 7 we show the computed spectral index $`\alpha `$ (defined in such a way that $`S_\nu \nu ^{+\alpha }`$, where $`S_\nu `$ is the flux density at a given frequency $`\nu `$) of each source for all epochs. The radio spectra corresponding to the values listed in Table 2 are plotted in Fig. 3 for all sources, including the 20 cm wavelength flux densities measured on July 30 for the last two sources. We have also plotted, for all sources, the non-simultaneous 20 cm measurements from the NVSS survey obtained in VLA D configuration.

Inspection of all obtained maps (with phase-reference or self-calibration techniques, with uniform or natural weights, of individual snapshots or after concatenating all of them, and at all frequencies), reveals that all sources are point-like except 1RXS~J072259.5$-$073131, which presents extended structure towards the east, marginally present in the 3.6 and 6 cm maps, and visible as a one-sided jet in the 30 July snapshot observation at 20 cm wavelength (see Fig. 4).

## 4 Optical observations

Having in mind the goal of identifying the optical counterparts, CCD observations were made at Calar Alto (Almería, Spain) with the 1.5 m telescope of the Observatorio Astronómico Nacional (OAN), between 24 and 30 November 1998. We used the Ritchey-Chrétien focus and a Tektronics TK1024AB chip that provides a scale factor of $`0.4\mathrm{}`$ per pixel and a $`6.9\mathrm{}\times 6.9\mathrm{}`$ field of view. Deep CCD images were obtained for all our candidates, with the exception of 1RXS~J181119.4$-$275939 and 1RXS~J185002.8$-$075833 that were not visible at the epoch of our observations. The images were taken with the $`V`$, $`R`$ and $`I`$ Johnson filters, and the exposure times were typically of 600–1200 seconds. Although the images were useful for photometric measurements, their quality did not allow us to obtain accurate positions.

Complementary CCD observations were conducted on 1999 December 11 also at Calar Alto, but using the 2.2 m telescope of the Centro Astronómico Hispano-Alemán (CAHA). Images were obtained using the Ritchey-Chrétien focus and CAFOS, leading a scale factor of $`0.53\mathrm{}`$ per pixel and a $`8.8\mathrm{}\times 8.8\mathrm{}`$ field of view, through the $`I`$ Johnson filter and with exposure times between 180 and 600 seconds. The good quality of these images allowed us to perform accurate astrometric measurements, although no precise photometric information could be obtained since the images could not be photometrically calibrated.

The observations were reduced using standard procedures (bias and dark subtraction and flat-field correction) within the IRAF software package.

### 4.1 Results

Promising optical counterparts for all observed sources, i.e., the first six ones in Table 1, were found in both observing runs. Thanks to the CAHA 2.2 m observations we were able to obtain accurate positions. For this purpose, we performed a detailed astrometric reduction of each image using field stars present in the USNO-A2.0 catalog (Monet et al. monet99 (1999)). First of all we selected point-like objects in the image, not elliptical or binary objects due to crowded fields, and determined their positions ($`X`$, $`Y`$). We also rejected very faint objects to allow a significant signal-to-noise ratio. On the other hand, very bright objects were also rejected, because the positions given in the USNO-A2.0 catalog are from plates obtained around 1950, and nearby (bright) stars could have experienced a shift in position since then due to relatively high proper motions. Then we fitted an astrometric solution to our image using the USNO-A2.0 ($`\alpha `$, $`\delta `$) and image ($`X`$, $`Y`$) positions for the common stars in both the catalog and the image, and rejected spurious points above 3$`\sigma `$. We proceeded iteratively until convergence was achieved. This process allowed us to obtain plate solutions with an rms of $`0.2\mathrm{}`$ in each coordinate. This relatively high error probably arises from the non-zero proper motions of the field stars finally used in the fit, between 36 and 155 depending on each image. We have to quadratically add to this error the 1$`\sigma `$ empirical uncertainty estimate of the USNO-A2.0 catalog relative to the ICRF, which is also $`0.2\mathrm{}`$ in each coordinate (see Table 1 of Deutsch deutsch99 (1999)). Therefore, the final 1$`\sigma `$ error of our obtained coordinates is estimated to be 0.3$`\mathrm{}`$.

We show the central $`2\mathrm{}\times 2\mathrm{}`$ of the CAHA 2.2 m images in Fig. 2, with the optical counterparts marked with a circle (which is not any X-ray or radio error box). All sources appeared basically as point-like objects, except the quasar 1RXS~J072418.3$-$071508, which had a complex structure with two separate optical components, hereafter NW (northwest) and SE (southeast). The NW position falls well within the NVSS error box and close to our obtained radio position. On the contrary, the SE position is clearly out the NVSS error box, and cannot be considered as a reliable counterpart to the radio source.

Photometry was obtained thanks to the OAN 1.5 m observations. The absolute photometry is believed to be accurate only to $`\pm `$0.1 magnitude in the best cases, because we could only determine the approximate photometric zero point by observing a few standard stars from Landolt (landolt92 (1992)).

The obtained results are presented in Table 3, where Col. 1 gives the RBSC object name, Cols. 2 and 3 give the J2000.0 ICRS coordinates of the optical position with the 1$`\sigma `$ error of 0.3$`\mathrm{}`$ below each coordinate, Col. 4 gives the observing dates and Cols. 5 to 7 give the Johnson $`V`$, $`R`$ and $`I`$ magnitudes. Magnitudes for 1RXS~J072418.3$-$071508 correspond to the sum of both the NW and SE components.

## 5 Discussion

The observations reported here provide accurate positions in the optical (0.3$`\mathrm{}`$) and specially in the radio (0.01$`\mathrm{}`$) domains. The astrometric agreement for each source can be seen in the radio maps of Fig. 2, and is numerically expressed in Table 4, where we list the offsets in right ascension, in declination and the total offset between the optical and radio positions. As can be seen, the offsets in each coordinate are always smaller than the 1$`\sigma `$ optical errors in position.

Although the agreements in position are certainly very promising, we have estimated the probability of a random coincidence. For this purpose, we have obtained the limiting $`I`$ magnitude of our CAHA 2.2 m images and counted the number of objects until this threshold. Then we have estimated the object-density of our images by assigning to each object the area of the 1$`\sigma `$ error box in position, i.e., $`(2\times 1\sigma )^2=(0.6\mathrm{})^2`$. Finally, we have divided the area occupied by the stars by the area of the image, and obtained a naive estimate of the probability to find an optical object, up to a given limiting $`I`$ magnitude, close to the radio position by less than 1$`\sigma `$, or 0.3$`\mathrm{}`$, in each coordinate. The limiting $`I`$ magnitudes and obtained probabilities of random coincidence are listed in the last two columns of Table 4. Since these probabilities are always smaller than 1%, and even much smaller if we consider the particular offsets instead of the 1$`\sigma `$ optical errors, we conclude that probably all optical objects are the counterparts of the radio sources, and none of them is a field star not related to the radio source.

On the other hand, an analysis of observed radio spectra of X-ray binaries can be found in Fender (fender01 (2001)). It seems clear that negative spectral indices ($`1\alpha 0.2`$) are detected when observing synchrotron emission from expanding plasmons, which are the result of discrete ejections after an outburst. On the contrary, flat or inverted radio spectra ($`0.0\alpha 0.6`$) are typical of the low/hard X-ray state of black hole candidates, and are believed to arise in synchrotron emission from a partially self-absorbed jet. Hence, a variety of spectral indices can be found in the objects we are looking for. However, inverted spectra with $`\alpha >1`$ at high radio frequencies (above 5 GHz) would probably rule out a REXB nature.

REXBs often display a variable flux, although extragalactic sources may vary as well. Our observations, performed at one/two week interval, allow us to estimate the degree of variability given by $`(S_{\mathrm{max}}S_{\mathrm{min}})/(S_{\mathrm{max}}+S_{\mathrm{min}})`$, being $`S_{\mathrm{max}}`$ and $`S_{\mathrm{min}}`$ the maximum and the minimum flux density, respectively. As it is clear from Table 2 and Fig. 3, all sources in the sample show some degree of flux density variability at centimeter wavelengths during the three runs of our monitoring. This variability is always within 10%, except for 1RXS~J042201.0+485610 at 6 cm, where a variability up to $`30`$% is detected, although it should be considered with caution due to the low emission level.

The optical emission seen in microquasars arises from the non-degenerated star of the system, i.e., the companion of the compact object. Hence, in microquasars containing a high mass companion spectral types O or B are found, while in those containing a low mass companion the spectral type is later than A (White et al. white95 (1995)). Therefore, as optical counterpart of a given candidate, we expect to find a non-degenerated star with any spectral type, and with a luminosity class ranging from the main sequence to supergiant. In fact, once photometric magnitudes of an object through different filters and its distance are known, one can easily deduce its spectral type assuming it is a star. However, we have no information about the distance to our sources, and no correction for extinction can be applied to our data. This is particularly important in our case, since our search has been carried out at low galactic latitudes, where a high degree of extinction is expected, preventing any spectral type classification from the photometric data alone.

### 5.1 Discussion on individual sources

#### 1RXS~J001442.2+580201.

The radio counterpart, see Table 2, shows a moderate degree of variability but always displaying a negative spectral index of $`0.2`$, suggesting an optically thin or partially self-absorbed synchrotron emitter. As can be seen in Fig. 3, the non-simultaneous NVSS flux density measurement at 20 cm wavelength is compatible with this behavior or even with a flattening of the spectrum at longer wavelengths, although this could be due to intrinsic variability. Non-thermal synchrotron radiation remains therefore as the most plausible interpretation for the radio emission of this source. The optical counterpart to the radio source (Fig. 2) appears as a point-like source with $`I20`$, which makes it the weakest optical object of our sample. No $`R`$ or $`V`$ magnitudes could be obtained, although a typical behavior for low latitude highly absorbed sources is an increase of $`1`$ magnitude when changing from $`I`$ to $`R`$ and from $`R`$ to $`V`$, as can be seen in the other sources of Table 3. All the available information points towards a good REXB candidate.

#### 1RXS~J013106.4+612035.

In the radio domain it shows a slightly negative or close to zero spectral index, reminiscent of optically thin or partially self-absorbed jets in REXBs, in which the non-simultaneous NVSS flux measurement fits well, and it displays a very low degree of variability of 2% at 3.6 cm and 4% at 6 cm. This object has also been observed within the Green Bank 5 GHz radio survey (Gregory & Condon gregory91 (1991); Gregory et al. gregory96 (1996)) with a measured flux density of 24 mJy. This value is a little bit higher than the ones reported here, although this discrepancy could be due to intrinsic variability and/or to the different angular scales sampled by the interferometric VLA observations. In fact, VLA A configuration observations carried out by Laurent-Muehleisen et al. (laurent97 (1997)) on October 19, 1992, indicate a flux density of 16 mJy at 5 GHz, in good agreement with our data. In the optical domain, the counterpart to the radio source appears as a point-like object with a nearby field object at $`3\mathrm{}`$ to the northeast, visible in Fig. 2, which is $`1`$ magnitude fainter in the $`I`$ band. The optical magnitudes in Table 3 correspond to the sum of both objects (unresolved in the OAN 1.5 m images), and are typical of low latitude highly absorbed sources. Overall it seems a good REXB candidate.

#### 1RXS~J042201.0+485610.

In the RBSC this source appears catalogued with an X-ray extension of $`17\mathrm{}`$, which could suggest an extragalactic origin of the source. However, X-ray halos produced by the scattering of the original X-ray photons by interstellar dust grains are seen in some galactic microquasars, like for example in a Chandra observation of Cyg~X-3 (Predehl et al. predehl00 (2000)). In fact, Cyg~X-3 has an X-ray extension of $`63\mathrm{}`$ within the RBSC, while SS~433 has one of $`25\mathrm{}`$. Hence, the presence of an X-ray extension does not rule out a REXB nature for this source. The radio counterpart shows the lowest radio emission level of all sources in our sample, and displays an inverted spectrum up to $`\alpha +1.6`$ (see Table 2), difficult to account for self-absorbed synchrotron radiation at such high frequencies. Nevertheless, as it happens in some AGN, a highly inverted spectrum would be expected if the jet is stopped in a dense medium on a compact scale. On the other hand, the non-simultaneous NVSS flux density measurement seems to be incompatible with self-absorbed synchrotron radiation. Although this could be due to intrinsic variability of the source, this would require variations of an order of magnitude in flux. This discrepancy can be explained if we assume a thermal origin for the radio emission and if we attribute the drop in flux density in our VLA A configuration observations due to over resolution when compared to the NVSS VLA D configuration observations. The optical counterpart to the radio source has a nearby field object at $`3\mathrm{}`$ to the west, marginally visible in Fig. 2, which is $`2`$ magnitudes fainter in the $`I`$ band. The optical magnitudes in Table 3 correspond to the sum of both objects (unresolved in the OAN 1.5 m images), although the nearby one is not expected to contaminate appreciably, and are again typical of low latitude highly absorbed sources. Although at first sight our target appears as a point-like source in Fig. 2, if we perform Gaussian fits to field objects with similar magnitudes, we find our target to have a Full Width at Half Maximum (FWHM) $`15`$% greater, suggesting that it is in fact an extended optical object. In summary, the high spectral index and the extended optical emission indicate that this source is not a very promising REXB candidate.

#### 1RXS~J062148.1+174736.

In the radio domain, this source displays an inverted or flat spectrum, which could account for a partially self-absorbed jet. On the other hand, the moderate variability observed, around 10%, could explain the higher non-simultaneous NVSS flux density measurement. In the optical domain, this source appears as a point-like object with magnitudes typical of low latitude highly absorbed sources. However, a careful inspection of the optical image, reveals that the FWHM of a Gaussian fit to our target source is $`30`$% greater than those of other sources with similar magnitudes. This fact points to an extragalactic nature for this source. It is worth to mention that this source is the only one in our sample present in the second incremental release of the Two Micron All Sky Survey (2MASS) (Cutri et al. cutri00 (2000)). Its position, obtained from images taken in October 1997, is there listed as $`\alpha =6^\mathrm{h}21^\mathrm{m}47.749^\mathrm{s}\pm 0.009^\mathrm{s}`$, $`\delta =+17\mathrm{°}47\mathrm{}35.07\mathrm{}\pm 0.13\mathrm{}`$, in very good agreement with our obtained coordinates. Finally, we would like to point out that Motch et al. (motch98 (1998)) list 3 stars within the X-ray error box as possible counterparts to the X-ray source. Our proposed optical counterpart on the basis of the radio position, would rule out any of these 3 stars as the optical counterpart of this X-ray source. Overall, it looks like an extragalactic object because of its optical extension.

#### 1RXS~J072259.5$-$073131.

The radio counterpart presents an extended structure towards the east, marginally present in the 3.6 and 6 cm maps, and visible as a one-sided jet in the 30 July 4 minute snapshot observation at 20 cm wavelength (see Fig. 4). Although the one-sided morphology is suggestive of an extragalactic nature for this source, specially if we take into account that we are mapping the source at arcsecond scales, we cannot rule out a possible galactic nature on the basis of the detected morphology. The source also shows a moderate degree of variability, displaying most of time a negative spectral index but also close to 0 in the July 22 observation. As can be seen in Fig. 3, the non-simultaneous NVSS flux density measurement at 20 cm wavelength could be compatible with a non-thermal optically thin spectrum. However, simultaneous observations during July 30 show a flattening of the spectrum at higher wavelengths, which could be due to self-absorption in this energy range. The difference between the NVSS and our flux density measurement at 20 cm wavelength could be due to intrinsic variability and/or to the different VLA configurations used. Anyway, non-thermal synchrotron radiation remains as the most plausible interpretation for the radio emission of this source, specially at higher frequencies. The optical counterpart appears as a point-like object with the magnitudes of an absorbed object at low galactic latitudes. These properties are in good agreement with the expected ones for a microquasar, although the one-sided radio jet at arcsecond scales is most common in extragalactic objects.

#### 1RXS~J072418.3$-$071508.

This source has been recently (March 2002) classified as a quasar in the SIMBAD database, and it is not any more a REXB candidate. It is listed as PMN~J0724$-$0715 in the NED database, and is the source WGA~J0724.3$-$0715 in Perlman et al. (perlman98 (1998)), who reported a faint and quite broad H$`\alpha `$ emission line (rest-frame $`W_\lambda =30.3`$ Å, FWHM=4000 km s-1), and classified it as a flat spectrum radio quasar with $`z=0.270`$. Nevertheless, we have reported here our observational results for this source, since it was a candidate when we performed the observations. In the radio it displays a low degree of variability of 3% at 3.6 cm and 4% at 6 cm, with a flat or even inverted spectrum. In the optical it appears as a complex double object, with a NW and a SE components, being the first one the counterpart to the radio source. Magnitudes in $`V`$, $`R`$ and $`I`$ typical of absorbed objects at low galactic latitudes were found. On the other hand, it appears catalogued with an X-ray extension of $`40\mathrm{}`$ in the RBSC.

## 6 Conclusions

We have presented a cross-identification method to search for REXBs, which are potential microquasar sources. The obtained results give confidence to the proposed method, since the output list of objects included all but one known persistent HMXB microquasars within $`|b|<5\mathrm{°}`$. The unidentified sources in the list were divided in two groups, depending on the offset between the RBSC and NVSS positions. The Group 1 source list contained 8 objects, of which 1RXS~J181119.4$-$275939 and 1RXS~J185002.8$-$075833 were not studied because they were not visible during our observations. We studied the remaining 6 radio sources of Group 1, and found optical counterparts to all of them. We obtained accurate positions at both radio and optical wavelengths, perfectly compatible between them. We also obtained radio spectra and optical magnitudes of the sources.

After a detailed analysis of the obtained data, we conclude that 1RXS~J001442.2+580201 and 1RXS~J013106.4+612035 are good REXB candidates, while 1RXS~J042201.0+485610 is not so promising due to its highly inverted spectrum at high frequencies and its optical extended emission. A careful study of the optical counterpart of 1RXS~J062148.1+174736 reveals it is extended, which points towards an extragalactic nature for this object. The situation is not clear in the case of 1RXS~J072259.5$-$073131, because the optical data agrees with a microquasar nature, while the detected one-sided radio jet reaching arcsecond scales is most common in extragalactic sources. The last studied source, 1RXS~J072418.3$-$071508, is an already identified quasar. Hence, two sources in our sample are very promising to be new microquasars in the Galaxy.

Optical spectroscopic observations, intended to unveil the nature of the optical counterparts, were attempted in autumn 2000 and 2001, and were not carried out due to bad weather conditions. A new attempt is in progress for autumn 2002. On the other hand, VLBI observations of these sources will be reported soon (Ribó et al. 2002a ).

The two sources belonging to Group 1 not yet observed, namely 1RXS~J181119.4$-$275939 and 1RXS~J185002.8$-$075833 will be eventually studied in the future, together with Group 2 sources. Finally, since some microquasars could have been ejected from the galactic plane (Ribó et al. 2002b ), we are planning to extend this project up to higher galactic latitudes ($`5\mathrm{°}<|b|<10\mathrm{°}`$).

###### Acknowledgements.

We acknowledge useful comments and discussions with O. Fors, X. Otazu and I. Ribas. We also acknowledge J. S. Bloom for reading through a draft version of this work and for his useful suggestions. We acknowledge detailed and useful comments from H. Falcke, the referee of this paper. We acknowledge partial support by DGI of the Ministerio de Ciencia y Tecnología (Spain) under grant AYA2001-3092. We also acknowledge partial support by the European Regional Development Fund (ERDF/FEDER). M. R. is supported by a fellowship from CIRIT (Generalitat de Catalunya, ref. 1999 FI 00199). J. M. is partially supported by Junta de Andalucía (Spain) and has also been aided in this work by an Henri Chrétien International Research Grant administered by the American Astronomical Society. The authors were Visiting Astronomers at German-Spanish Astronomical Centre, Calar Alto, operated by the Max-Planck-Institute for Astronomy, Heidelberg, jointly with the Spanish National Commission for Astronomy. This research has made use of the NASA’s Astrophysics Data System Abstract Service, of the SIMBAD database, operated at CDS, Strasbourg, France, and of the NASA/IPAC Extragalactic Database (NED) which is operated by the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administration. The Digitized Sky Survey was produced at the Space Telescope Science Institute under U.S. Government grant NAG W-2166.