\documentclass[trans]{beamer}
%\documentclass{beamer}

\usepackage{beamerthemesplit}
\useoutertheme{infolines} 

\input{nielsenmacros}

\title[Typical doubly-twisted conjugacy classes]{
Typical elements in free groups are in different doubly-twisted
conjugacy classes}
\author[Staecker]{P. Christopher Staecker}
\institute[Fairfield U.]{Fairfield University, Fairfield CT}
\date[]{Nielsen 2009, St. John's Newfoundland}

\newcommand{\aside}{\textcolor{red}}

\begin{document}

\frame{\titlepage}
\section{Preliminaries}
\frame
{
  \frametitle{Setting}

  \begin{itemize}
  \item $G$ and $H$ are finitely generated free groups, rank $H > 1$
  \item $\phi, \psi: G \to H$ are homomorphisms
  \item Elements $u, v \in H$ are \emph{doubly-twisted conjugate} iff
    there is some $g \in G$ with 
\[ u = \phi(g) v \psi(g)^{-1}. \]
\item No algorithm exists to decide doubly-twisted conjugacy in free groups.
  \item $[u]$ denotes the doubly-twisted conjugacy class of $u$.

  \end{itemize}
}

\frame
{ \frametitle{Anecdotal evidence}
I've done a lot of computer tests for finding twisted and
doubly-twisted conjugacy classes. We generate homomorphisms and elements
at random, and then test to see if the elements are twisted conjugate.

\vfill\pause
As it happens, usually they are not!
\vfill\pause
We aim to show that if $\phi$,$\psi$, $u$, $v$ are all chosen at
random, then $[u]\neq [v]$ with probability 1.
}

\frame
{ \frametitle{Homomorphisms with remnant}

Let $G = \langle g_1, \dots, g_n \rangle$. We say that $\phi$
\emph{has remnant} if for every $i$, the word $\phi(g_i)$ has a
subword which does not cancel in any product like 
\[ \phi(g_j)^{\pm 1} \phi(g_i) \quad \text{or} \quad \phi(g_i)
\phi(g_j)^{\pm 1} \]
except $j=i$ with exponent $-1$.
\vfill
\pause
This is close to saying that $\{ \phi(g_1), \dots,
\phi(g_n) \}$ is Nielsen reduced.
\vfill
\pause
Very easy to check.
}

\frame
{ \frametitle{Remnants}
\framesubtitle{I said it was easy}
\[ \phi: \begin{array}{rcl}
a &\mapsto &a^3bab^{-2} \only<1>{\phantom}{= a^2 \underline{bab^{-1}}b^{-1}} \\
b &\mapsto &ba^4ba^{-2} \only<1>{\phantom}{= b\underline{a^4b} a^{-2}}
\end{array} \]
\pause
This one has remnant, the remnants are underlined. \pause 
\vfill
We write
\begin{align*}
\Rem_\phi a &= bab^{-1} \\
\Rem_\phi b &= a^4b
\end{align*}
\vfill

It is easy to check if $\phi$ has remnant, and this is generically
true for long words. (In fact for long words, we expect the remnant
itself to be long.) 
}

\frame
{\frametitle{Remnant numbers}
Some measures of the size of the remnant:
\pause\vfill

For a natural number $\ell$, if $|\Rem_\phi g| \ge \ell$ for all generators
$g$, then we say that $\phi$ has \emph{remnant length} $\ell$.

\pause\vfill

For a real number $r \in (0,1)$, if $|\Rem_\phi g| \ge r|\phi(g)|$ for
all generators $g$, then we say that $\phi$ has \emph{remnant ratio}
$r$.

\pause\vfill

So for 
\[ \phi: \begin{array}{rcl}
a &\mapsto &a^2 \underline{bab^{-1}}b^{-1} \\
b &\mapsto &b\underline{a^4b} a^{-2}
\end{array} \]

The remnant length is 3, and the remnant ratio is 1/2.
}

\frame
{\frametitle{Our coincidence remnant condition}
We will have two homomorphisms $\phi, \psi$. We will require not only
that $\phi$ and $\psi$ each have remnant, but that they have remnant
when considered \emph{together}. 

\pause\vfill

For example:
\begin{align*} \phi&: \begin{array}{rcl}
a &\mapsto & a^2bab^{-2} \\
b &\mapsto & ba^4ba^{-2}
\end{array} \\
\psi&: \begin{array}{rcl}
a &\mapsto & b^{-1}a^4 \\
b &\mapsto & a^2ba 
\end{array}
\end{align*}

\vfill

For our purposes, this is \emph{not} good enough because $\psi(b)$ has too much
cancellation with $\phi(a^{-1})$.
}

\frame
{ \frametitle{The free product homomorphism}
Consider the free product $G*G$, and there is a natural homomorphism
$\phi * \psi: G*G \to H$. 
\pause
\vfill
For $G = \langle g_i \rangle$, write $G*G = \langle g_i, g_i' \rangle$ and define
\begin{align*} 
\phi * \psi(g_i)  &= \phi(g_i) \\
\phi * \psi(g_i') &= \psi(g_i)
\end{align*}

\pause\vfill
So from above, 
\[ \phi*\psi: \begin{array}{rcl}
a &\mapsto & a^2bab^{-2} \\
b &\mapsto & ba^4ba^{-2} \\
a'&\mapsto & b^{-1}a^4 \\
b'&\mapsto & a^2ba 
\end{array} \]
and we will require that $\phi * \psi$ has remnant. (Here, it does not.)
}

\frame
{ \frametitle{An easy lemma}
\begin{lem*} If $\phi*\psi: G*G \to H$ has remnant, then $\phi(G) \cap
  \psi(G) = \{1\}$. 
\end{lem*}
\pause
\begin{proof}
If not, then there are nontrivial $x,y\in G$ with
\[ \phi(x) = \psi(y) \]
\pause
and so 
\[ \phi(x)\psi(y)^{-1} = 1. \]
\pause

But this is impossible since $\phi * \psi$ has remnant. If we write
$x$ and $y$ in generators, the word cannot cancel. 
\end{proof}

\pause\vfill
\emph{Moral:} The condition that $\phi*\psi$ has remnant is very
strong.
}

\section{The theorem}

\frame
{ \frametitle{Remnants and doubly twisted conjugacy classes}
Let $\phi^v$ be $\phi$, conjugated by $v$.

\pause
\vfill

\begin{thm*}
Let $u \neq v$. If $\phi^v * \psi$ has remnant, and if for any
generator $g$ the remnants $\Rem_{\phi^v * \psi}g$ do not cancel in
any product: 
\[ (\phi^v * \psi(g))v^{-1}u, \quad u^{-1}v (\phi^v * \psi(g)) \]
then
\[ [u] \neq [v]. \]
\end{thm*}

\pause\vfill

\emph{Note:} the remnant hypothesis is never true for $\psi = \id$.
\pause\vfill
But it will be true for ``most'' homomorphisms and ``most'' choices of
$u$ and $v$.

}

\section{Asymptotic Density}

\frame
{ \frametitle{``Most'' homomorphisms have remnant}
Everybody knows Bob's theorem:
\begin{thm*} (R. F. Brown (in Wagner), 1999) Given any $\epsilon > 0$,
  there is some $M$ such that if $\phi$ is a random homomorphism with
  word lengths at most $M$, then $\phi$ has remnant with probability
  greater than $1-\epsilon$. 
\end{thm*}

\pause\vfill

This fits nicely into the theory of \emph{generic} sets in groups,
measured by \emph{asymptotic density}. 

\pause\vfill
Measuring the density is a great way to get a handle on properties
which we want to show hold for ``most'' things.
}

\frame
{ \frametitle{Density and generic sets}
Let $H_p$ be all words in $H$ of length at most $p$. 

\vfill

For a subset $S \subset H$, the \emph{[asymptotic] density} of $S$ is:
\[ D(S) = \lim_{p \to \infty} \frac{S \cap H_p}{H_p} \]

\pause\vfill

If $D(S) = 1$, we say $S$ is \emph{generic}.

\pause\vfill
Similarly we can define the density of sets of tuples, and thus the
density of sets of homomorphisms.

So Bob's theorem can be restated as: The set of homomorphisms $\phi:G
\to G$ with remnant is generic.

}

\frame
{ \frametitle{Property $C'(\lambda)$}

Much stronger results are known about this kind of thing:

A subset $S$ in a free group has property $C'(\lambda)$ when: given an element
$x\in S$, the pieces of $x$ cancelling in products with other elements
of $S$ (or their inverses) have length less than $\lambda|x|$. 

\begin{thm*}
(Arzhantseva, Ol'shanskii, 1996) If $H$ has rank greater than 1, then
  the set of subsets of $H$ having small cancellation property
  $C'(\lambda)$ is generic for any $\lambda > 0$.
\end{thm*}

\vfill \pause

So A\&O's theorem says that, when we look at the image words of a
homomorphism, the remnant subwords will generically be arbitrarily big.
}

\frame
{ \frametitle{Fancier generic remnant properties}
So Bob's theorem can be substantially improved:
\begin{thm*}
Let $H$ have rank greater than 1. Then:
\begin{itemize}
\item The set of homomorphisms $\phi:G \to H$ with remnant is generic.
\pause
\item The set of homomorphisms $\phi:G \to H$ with remnant length at
  least $\ell$ is generic for any $\ell$. 
\pause
\item The set of homomorphisms $\phi:G \to H$ with remnant ratio $r$
  is generic for any $r \in (0,1)$. 
\end{itemize}
\end{thm*}

\pause 

Applied to homomorphisms $G*G \to H$, this means that $\phi * \psi$
will generically have remnant subwords as long as we like.

\pause
In particular this means that $\phi(G) \cap \psi(G)$ is generically
trivial, which is a bit surprising. (Think about $\phi,\psi: F_{1000}
\to F_2$)
}

\frame
{\frametitle{Main asymptotic result}
\begin{thm*}
Let $H$ have rank greater than 1, $\phi, \psi:G \to H$ each have
remnant ratio at least 1/2, and let $k$ be the minimum length of any
word $\phi(g)$ or $\psi(g)$ for a generator $g$. 
\pause

\aside{Generically, the remnant ratio is as big as we want, and $k$ is also
as big as we want.}

\pause
Let $S$ be the set of pairs $(u,v)$ with $[u] \neq [v]$. Then 
\[ \lim_{k \to \infty} D(S) = 1. \]
\end{thm*}

We say $S$ is ``almost generic in $k$''. 

\vfill \pause

\begin{cor*}
The set of tuples $(\phi, \psi, u, v)$ with $[u] \neq [v]$ is generic.
\end{cor*}
}

\frame
{ \frametitle{The density estimate}
In case you're wondering, the proof shows that
\[ D(S) \ge 1 - 2(2m-1)^{-\frac{k-1}{2}} - (32n)^2(2m-1)^{-(k-1)}, \]
where $n$ and $m$ are the ranks of $G$ and $H$.
\vfill
This density goes to 1, but takes a while to get there. 

\vfill\pause

For maps $F_2 \to F_2$, (so $n=m=2$) the density estimate is actually negative
until $k=9$. 

\vfill\pause
\begin{center}
\begin{tabular}{|c|c|}
\hline
$k$ & $D(S)$ estimate \\
\hline
9 & .35 \\
10 & .78 \\
11 & .92 \\
12 & .97 \\
13 & .99 \\
\hline
\end{tabular}\end{center}
}

\frame
{ \frametitle{Some obvious questions}
Let $S$ be the set of $u, v \in H$ with $[u] \neq [v]$.

\aside{Theorem says $D(S) \to 1$ as $|\phi| \to \infty$ and $|\psi| \to \infty$}
\vfill \pause
\begin{enumerate}
\item Fixing a \emph{particular} pair of homomorphisms $\phi, \psi$,
  is $D(S) = 1$? 
\pause

\aside{Not for all pairs: if $\phi = \id$ and $\psi = 1$ then $[u]=[v]$ for
all $u$ and $v$.}
\pause\vfill
\item Fixing $\psi$ but allowing $\phi$ to vary,
  does $D(S) \to 1$ as $|\phi| \to \infty$?
\pause

\aside{I think I can show this when $\psi$ has remnant, using
  different methods}
\vfill
\item For singly-twisted conjugacy, does $D(S) = 1$ as $|\phi| \to \infty$?
\pause

\aside{$2 \Rightarrow 3$, and $\id$ has remnant}
\pause \vfill
\item Do similar results hold in surface groups? 
\end{enumerate}
}

\section{Density of Wecken maps}

\frame
{ \frametitle{Back to Nielsen theory}
This suggests a new approach to asking about Wecken maps on 
compact surfaces with boundary: 

A selfmap $f$ is \emph{Wecken} if $N(f) = \MF(f)$. A pair $(f,g)$ is
Wecken if $N(f,g) = \MC(f,g)$. We can say that a pair of homomorphisms
$(\phi, \psi)$ are Wecken in the obvious way.

\vfill\pause

A necessary condition for coincidence points to be merged is that
their Reidemeister classes are in the same doubly-twisted conjugacy
classes. 

\vfill\pause
All things being chosen randomly, these classes should never be
equal. 
}

\frame
{ \frametitle{Conjectures}
\begin{conj*}
If the rank of $H$ is greater than one, the set of Wecken pairs
$\phi,\psi: G \to H$ is generic.
\end{conj*}

\vfill\pause
The same should be true in fixed point theory, but different methods
would be needed.
\vfill\pause

This is maybe some way in the distance as of now, but partial results
would be nice too. Even showing that the Wecken maps have nonzero density
would (I believe) be new and interesting. 

\vfill\pause

(We know homeomorphisms are Wecken, but these are still density 0.)
}

\frame
{ \frametitle{An easy one:}
\framesubtitle{Don't steal this idea}
Wagner's algorithm says that $[u]\neq[v]$ unless certain Wagner tails
match up. 
\vfill\pause
If the Wagner tails are all different, none of the fixed points can be
merged, and thus the map is Wecken.
\vfill\pause
Estimating the density of Wecken maps in this way is just a
combinatorial exercise: what is the probability that all of the Wagner
tails are different?
}

\frame
{ \frametitle{Prophecy:}
My prediction: Wagner's algorithm, plus basic combinatorics, can show
that the Wecken maps have nonzero density, but fancier methods will be
needed to show that the density is 1.
\vfill\pause
Anectodal evidence: generate 10,000 random homomorphisms $F_n \to F_n$
with maximum word length $k$, and see how many of these have all
Wagner tails different.
}

\frame
{ \frametitle{Experimental results}
\framesubtitle{Density of homomorphisms with all Wagner tails different}
\begin{columns}
\begin{column}{0.33\linewidth}
\begin{center}
For maps $F_2 \to F_2$:
\vfill
\begin{tabular}{|c|c|c|}
\hline
$k$ & Density \\
\hline\hline
 1 & 0 \\
 2 & .19 \\
 3 & .20 \\
 4 & .22 \\
 5 & .21 \\
 6 & .20 \\
 7 & .21 \\
 8 & .20 \\
\hline
\end{tabular}\end{center}
\end{column}
\begin{column}{0.33\linewidth}
\begin{center}
For maps $F_3 \to F_3$:
\vfill
\begin{tabular}{|c|c|}
\hline
$k$ & Density \\
\hline\hline
1 & 0 \\
 2 & .08 \\
 3 & .10\\
 4 & .19\\
 5 & .22\\
 6 & .24\\
 7 & .25\\
 8 & .25\\
\hline
\end{tabular}\end{center}
\end{column}

\begin{column}{0.33\linewidth}
\begin{center}
For maps $F_4 \to F_4$:
\vfill
\begin{tabular}{|c|c|}
\hline
$k$ & Density \\
\hline\hline
1 & 0 \\
 2 & .04 \\
 3 & .06 \\
 4 & .18 \\
 5 & .25 \\
 6 & .27 \\
 7 & .27 \\
 8 & .27 \\
\hline
\end{tabular}\end{center}
\end{column}
\end{columns}
}

\frame
{
\frametitle{It's over!}
The paper is at my website and at arXiv.

\vfill

See also my web-based twisted conjugacy calculator ``The Nielsen Theory
Web Machine'', by me and Chris Putnam.

\vfill

Experiments were done in GAP, code is at my website.
\vfill
}
\end{document}