\documentclass{slides}
\usepackage{amsmath, amsfonts, amssymb, multirow}

\include{nielsenmacros}

\newenvironment{head}
        {
        \begin{center}\bf
        }
        {
        \end{center}
        }

\begin{document}
\begin{slide}
\begin{head}
Computation of Reidemeister classes by nilpotentization
\end{head}
\begin{center}P. Christopher Staecker

\tt http://www.messiah.edu/\~{}cstaecker
\end{center}
\end{slide}

\begin{slide}
\begin{head}
Setting
\end{head}

$G$ is a free (or one-relator orientable surface) group, and $\phi:G
\to G$ is a homomorphism.

Given $x, y \in G$, we say that $x \sim y$ iff $\exists z \in G$ with 
\[ x = \phi(z) y z^{-1}. \]

A quotient by this relation forms the set of {\bf Reidemeister
  classes}.

Verifying whether or not two given words are equivalent is a difficult
problem, and no general algorithm is known.
\end{slide}

\begin{slide}

\begin{head}Nielsen theory context\end{head}
The problem appears in the following context:

Let $f$ be a self-map of an orientable surface with or without
boundary which induces the homomorphism $\phi:G \to G$ at the
fundamental group level, with  
\[ \phi: \begin{array}{rcl} a &\mapsto &a^{-2} c\\
 b &\mapsto &b^{-1}\\
 c &\mapsto &bca^{-1}\end{array}
\]

A theorem of Fadell and Husseini gives the \emph{Reidemeister
  trace} (also called \emph{generalized Lefschetz number}):
\begin{align*}
\RT &= \rho\left( 1 - \frac{\pd}{\pd a} \phi(a) - \frac\pd{\pd b}\phi(b) -
\frac\pd{\pd c}\phi(c) \right) \\
&= \rho (1 + a^{-1} + a^{-2} + b^{-1} - b) \\
&= [1] + [a^{-1}] + [a^{-2}] + [b^{-1}] - [b]
\end{align*}

Now a theorem of Wecken says that $L(f)$ is the coefficient sum, and
$N(f)$ is the number of distinct terms having nonzero coefficients.

\end{slide}

\begin{slide}
\begin{head}Abelianization\end{head}

We'll show that $[1] \neq [a^{-1}]$ for the above mapping. Let 
\[ 1 = \phi(z) a^{-1} z^{-1}, \]
and project into the abelianization $\bar G$,
\[ 0 = \phi(\bar z) - \bar a - \bar z.\]
Since $\bar z = i\bar a + j\bar b + k\bar c$, we have
\begin{align*} 0 &= i(-2 \bar a + \bar c) + j(-\bar b) + k(-\bar a +
  \bar b + \bar c) \\
&\qquad - \bar a - i\bar a - j\bar b - k\bar c \\
\bar a &= (-3i -k) \bar a + (-2j + k)\bar b + i \bar c 
\end{align*}
and this is verified to have no integer solutions by a matrix computation.

\end{slide}

\begin{slide}
Abelianization often fails to distinguish elements $x,y$. It is
certainly possible for $[x]\neq [y]$, but $[\bar x] = [\bar y]$.

We desire a quotient which allows computation, but retains the
structure of $G$. We explore projections of the form
\[ p_n: G \to G/\gamma_n(G), \]
where $\gamma_n(G)$ is the $n$th term of the lower central series of
$G$. 

The quotient $G/\gamma_n(G)$ is a class $n$ nilpotent group, which we call
the \emph{class $n$ nilpotentization}.
\end{slide}

\begin{slide}
\begin{head}Computation in nilpotent groups\end{head}

P. Hall: The following hold in any group,
\begin{align*}
yx &= [x,y]^{-1}xy, \\
[y,x] &= [x,y]^{-1}, \\
[xy,z] &= [x,[y,z]][y,z][x,z].
\end{align*}

In a class two nilpotent group, these reduce to:
\begin{align*}
yx &= xy[x,y]^{-1}, \\
[y,x] &= [x,y]^{-1}, \\
[xy,z] &= [x,z][y,z].
\end{align*}

So we can put any word from a class 2 nilpotent group into a standard
form:
\begin{align*} 
abca &= abac[a,c]^{-1} = a^2b[a,b]^{-1}c[a,c]^{-1} \\
&= a^2 bc[a,b]^{-1}[a,c]^{-1}.
\end{align*}
We can write any word as a product of powers of generators in order,
with a product of commutators in order. By a theorem of Hall (1954),
this form is \emph{unique}, given the ordering. This is our tool for
distinguishing words. 
\end{slide}

\begin{slide}
\begin{head} Nilpotentization \end{head}
We'll show that $[1] \neq [a^{-2}]$. Let 
\[ 1 = \phi(z)a^{-2}z^{-1}, \]
and project into $\bar G$. As before, we set up a matrix computation,
but it gives a solution
\[ \bar z = \bar b + 2 \bar c. \]

Now we project into $\hat G = G / \gamma_2(G)$:
\[ \hat 1 = \hat \phi(\hat z) \hat a^{-2} \hat z^{-1}. \]

We know that $\hat z$ must have the form
\[ \hat z = \hat b \hat c^2 [\hat a,\hat b]^{n_1} [\hat a,
  \hat c]^{n_2} [\hat b, \hat c]^{n_3}. \]

\end{slide}

\begin{slide}
\[ \hat 1 = \hat \phi(\hat z) \hat a^{-2} \hat z^{-1}. \]
\[ \hat z = \hat b \hat c^2 [\hat a,\hat b]^{n_1} [\hat a,
  \hat c]^{n_2} [\hat b, \hat c]^{n_3}. \]


Now we perform a taxing computation:
\begin{align*}
\hat \phi(\hat z) &\hat a^{-2} \hat z^{-1} = \\
&[\hat a,\hat b]^{n_1 - n_2 - n_3 + 1} [\hat a, \hat c]^{-2n_1 + 1}
   [\hat b, \hat c]^{n_1 - n_2 - 2n_3 + 3} 
\end{align*}

Setting the above equal to $\hat 1$ gives a matrix equation:
\[ \begin{bmatrix} 1 & -1 & -3 \\ -2 & 0 & 0 \\ 1 & -1 & -2
\end{bmatrix}
\begin{bmatrix}n_1 \\ n_2 \\ n_3 \end{bmatrix} = \begin{bmatrix} -1 \\ -1
    \\ -3\end{bmatrix} \]

This cannot have an integral solution, and so
$[1] \neq [a^{-2}]$.
\end{slide}

\begin{slide}
\begin{head} When does it work?\end{head}
{\bf Good news:} If $x \neq y$, then there is some $n$ with 
\[ p_n(x) \neq p_n(y), \]
where $p_n:G \to G/\gamma_n(G)$ is projection to the class $n$
nilpotentization. 

This is because free and one-relator groups are residually nilpotent.

{\bf Bad news:} Depending on $\phi, x, y$, it is possible that
$[x]\neq [y]$, but 
\[ [p_n(x)] = [p_n(y)] \]
for every $n$.

Apparently, the Reidemeister structure is not always residually
nilpotent.
\end{slide}

\begin{slide}
\begin{head} Bad news: Example\end{head}
{\bf Example:} Let 
\[ \phi: \begin{array}{rcl} a &\mapsto & [a,b]\\
 b &\mapsto &[a,c]\\
 c &\mapsto &[b,c^{-1}] \end{array}
\]

Then $\bar \phi(\bar z) = 0$, and so 
\[ \bar \phi(\bar z) + \bar x - \bar z = \bar y \]
always has a solution. This solution in $\bar G$ can be used to
construct a solution in $G/\gamma_2(G)$, etc.

So for this $\phi$, we have
\[ [p_n(x)] = [p_n(y)] \]
for every $n$, and any words $x$ and $y$.
\end{slide}

\begin{slide}
\begin{head} More bad news\end{head}
In each step, we require a matrix computation.
If our matrix equation is ever singular with infinitely many
solutions, then we will be unable to continue to the next nilpotency
class.

Our theorem is:
\begin{thm*}
If $\phi$ has residually nilpotent Reidemeister structure and is
\emph{``totally nonsingular''}, then we have an algorithm to verify that
$[x]\neq [y]$.
\end{thm*}
\end{slide}

\begin{slide}
\begin{head} Verifying that $[x]=[y]$ \end{head}
Algorithmics is not the issue, since a brute force enumeration of the
group will succeed in finding $z$ with
\[ \phi(z) x z^{-1} = y \]
if indeed $[x]=[y]$.

Nilpotentization gives a natural improvement to the brute-force check:
Each step gives a hint as to the structure of the desired $z$. 

In our example above, our check in the abelianization showed that 
\[ \bar z = \bar b + 2\bar c. \]
Thus in our enumeration, we need only check elements like
\[ bc^2, cbc, c^2b. \]
\end{slide}

\begin{slide}
If these ``class 1 candidates'' fail to demonstrate equality of $[x]$
and $[y]$, do a class 2 nilpotentization check to obtain more
structural information about $z$.

Combining this candidate checking process with the above technique for
distinguishing classes gives:

\begin{thm*}
If $\phi$ has residually nilpotent Reidemeister structure and is
totally nonsingular, then we have an algorithm to compute $N(f)$.
\end{thm*}

Neither of these conditions is necessary to make the computation. We
only require that the specific Fox calculus elements be
Reidemeister-distinguishable by nilpotentization, and that our matrix
computations are nonsingular in the necessary classes. Typically this
only requires $n=2,3,4$. 
\end{slide}



\begin{slide}
\begin{head} Comparison to existing techniques\end{head}
Nilpotentization is an elaboration on the established technique of
abelianization, and so is in general more successful.

For free groups, another technique is Wagner's algorithm (1999), which
is indeed an algorithm for computing $N(f)$, provided that the mapping
\emph{has remnant}.

Implementations of the three techniques were written in \magma, and
compared.
\end{slide}

\begin{slide}
\begin{head} Success Rates \end{head}
\begin{center}
\begin{tabular}{|c|c|l|l|l|}
\hline
Group & Length & Nilpn. & Abel. & Wagner \\
\hline
\hline
\multirow{4}{*}{$F_2$}
  & 2 & 93.99\%  &  82.16\%  &  41.11\% \\
  & 3 & 90.35\%  &  69.99\%  &  49.19\% \\
  & 4 & 85.85\%  &  58.53\%  &  54.09\% \\
  & 5 & 84.55\%  &  51.21\%  &  60.07\% \\
\hline\hline
\multirow{4}{*}{$F_3$}
  & 2 & 91.12\%  &  78.19\%  &  15.43\% \\
  & 3 & 86.89\%  &  65.64\%  &  24.85\% \\
  & 4 & 84.78\%  &  55.42\%  &  33.71\% \\
  & 5 & 84.22\%  &  46.91\%  &  41.05\% \\
\hline\hline
\multirow{4}{*}{$F_4$}
  & 2 & 89.28\%  &  77.00\%  &   5.20\% \\
  & 3 & 85.17\%  &  64.32\%  &  13.19\% \\
  & 4 & 84.18\%  &  54.58\%  &  22.29\% \\
  & 5 & 83.44\%  &  47.30\%  &  30.50\% \\
\hline
\end{tabular}
\end{center}

Each line gives data from 10,000 randomly generated maps of given word length.
\end{slide}


\end{document}