# Recovering a word in the free group of rank two from its image

The second paragraph of Zubkov (1998) [1] reads (see the free preview here):

As usual, by a Sanov representation we mean a homomorphism of the free group $F(x, y)$ with the free generators $x$ and $y$ into $\text{SL}_{2}(\mathbb{C})$, where $\mathbb{C}$ is the field of complex numbers, by the rule $$x \to \begin{pmatrix} 1 & z \\ 0 & 1\end{pmatrix}, \quad \quad y \to \begin{pmatrix} 1 & 0 \\ z & 1 \end{pmatrix}.$$ As is well known, for $|z| \geq 2$, this representation is faithful [2]. For the method of "recovering" a word $v(x, y) \in F(x, y)$ form its image $\text{SL}_{2}(\mathbb{C})$, in the special case $z = 2$, see the same book.

The book in question is Kargapolov and Merzlyakov. My question is: what is the method described in this book, or is there another reference that explains it?

[1] Zubkov, A.N., On a matrix representation of a free group, Math. Notes 64, No.6, 745-752 (1998); translation from Mat. Zametki 64, No.6, 863-870 (1998). ZBL0953.20011.

[2] Kargapolov, M.I.; Merzlyakov, Yu.I., Foundations of group theory. (Osnovy teorii grupp). 3rd ed., rev. and suppl, Moskva: "Nauka". 288 p. (1982). ZBL0508.20001.

It seems that the book is available in pdf format from here: http://www.vixri.com/d/Kargapolov%20M.I.,Merzljakov%20Ju.I.__Osnovy%20teorii%20Grupp%20+%20KOUROVSKAJa%20TETRAD.pdf, but is in Russian.

Representation is faithful

The proof is on page 129, and it goes approximately like this:

Let $|m|\ge 2$ and let

$$A=\begin{pmatrix}1&m\\0&1\end{pmatrix}\;\text{and}\;B=\begin{pmatrix}1&0\\m&1\end{pmatrix}$$

Our goal is to prove that:

$$A^{\alpha_1}B^{\alpha_2}A^{\alpha_3}B^{\alpha_4}\cdots\ne I$$

(a finite product of $r\gt 0$ terms, which may end with $A^{\alpha_r}$ or $B^{\alpha_r}$, depending on whether $r$ is odd or even; all $\alpha_i\ne 0$). This is enough, because it will also imply:

$$B^{\alpha_1}A^{\alpha_2}B^{\alpha_3}A^{\alpha_4}\cdots\ne I$$

(reduce to the previous case by conjugation using $B^{-\alpha_1}$).

Now, start with any row-matrix $Z=[x,y]$. Note $ZA^{\alpha}=[x, y+m\alpha x]$ and $ZB^{\alpha}=[x+m\alpha y, y]$. Thus, if we start multiplying $I$ with those matrices $A^{\alpha_i}$ and $B^{\alpha_i}$ on the right, the first row $[1,0]$ of $I$ is transformed according to those two rules above.

Also, notice that, in every step, one component of the row stays "still" and the other one is transformed, in other words, if we set up $x_0=0,x_1=1$, we end up with the following sequence of rows:

$$[x_1,x_0]$$ $$[x_1,x_2]$$ $$[x_3,x_2]$$ $$[x_3,x_4]$$

etc.

Now, the crux of the proof is that the sequence of moduli $(|x_n|)$ is (strictly) increasing, therefore we can never have $[1,0]$ again somewhere in the sequence of rows.

The proof is by induction on $n$, separately for the "odd" and the "even" case. For example, after multiplying $[x,y]$ by $A^{\alpha}$, we will assume that $|x|\gt|y|$ and prove that $|y+m\alpha x|\gt|x|$. This is true because:

\begin{align}|y+m\alpha x| & \ge|m||\alpha||x|-|y| \\ & \ge 2|x|-|y| \\ & \gt |x|\end{align}

(as $|m|\ge 2$ and $\alpha$ is a nonzero integer), and similar for the other case (multiplication by $B^{\alpha}$).

Recovering the factors: Explained on page 131.

If you take $m$ to be a whole number, it is possible to prove that the generated subgroup (of $SL_2(\mathbb Z)$) has the property that every matrix $\begin{pmatrix}x&y\\z&t\end{pmatrix}$ satisfies $x,t\equiv 1\pmod {m^2}$ and $y,z\equiv 0\pmod m$, and that, conversely, such matrices form a subgroup of $SL_2(\mathbb Z)$ which precisely corresponds to our generated subgroup.

The authors don't prove the last statement, but they show how to extract the actual exponents, on one example matrix, for $m=2$:

$$X=\begin{pmatrix}-23&-86\\-4&-15\end{pmatrix}$$

($x=-23, y=-86, z=-4, t=-15$). Look at the first row, and because the "right" element $-86$ is bigger (in modulus) than the left one, we will be extracting a factor $A^\alpha$ for some $\alpha$. (Otherwise, we would be extracting $B^\alpha$.) Divide $y+|x|$ by $2x$ with a positive remainder, and get $-86+|-23|=-63=-46\times 2+29$. Thus:

$$XA^{-2}=\begin{pmatrix}-23&-86\\-4&-15\end{pmatrix}\begin{pmatrix}1&-4\\0&1\end{pmatrix}=\begin{pmatrix}-23&6\\-4&1\end{pmatrix}$$

where $A$ is raised to the negative of the previous quotient (which was $2$).

Next, we divide, analogously, $-23+|6|=-17$ by $2\times 6=12$ and get $-17=12\times(-2)+7$, so this yields a factor $B^2$:

$$XA^{-2}B^2=\begin{pmatrix}-23&-6\\-4&1\end{pmatrix}\begin{pmatrix}1&0\\4&1\end{pmatrix}=\begin{pmatrix}1&6\\0&1\end{pmatrix}$$

Finally, we can divide $6+1=7$ by $2\times 1$ to get the quotient $3$, so we have another factor $A^{-3}$:

$$XA^{-2}B^2A^{-3}=\begin{pmatrix}1&6\\0&1\end{pmatrix}\begin{pmatrix}1&-6\\0&1\end{pmatrix}=I$$

This means that $X=A^3B^{-2}A^2$.

This is as far as the book goes, the proof that this always works is apparently left to the reader.

Exercise from the book: Recover the factors of the matrix:

$$\begin{pmatrix}321&-86\\698&-187\end{pmatrix}$$

• Thanks for the link. Maybe I'm misinterpreting the passage in Zubkov, but it seems to imply that, if I had the representation of a word obtained by multiplying the matrices $A$ and $B$ in whatever order, I could somehow "unpack" the multiplication to figure out what the original word was. – Mr. G Dec 31 '17 at 2:14
• @Mr.G Just added that part... It was a lot of typing... – user491874 Dec 31 '17 at 2:41
• Many thanks for the write-up. – Mr. G Dec 31 '17 at 2:45