# Double coset normal form for FPAs

Liza Frenkel is visiting the department, and she wants me to write an algorithm to compute double coset representation normal forms for free products with amalgamation.

Here are some notes I typed up in write maths, see maths as she and Andrew talked. I’m just putting them up here so I don’t lose them.

Suppose:
${F}_{1}$, ${F}_{2}$ free groups (finitely generated by $X$ and $Y$, respectively)
${H}_{1}\le {F}_{1}$, ${H}_{2}\le {F}_{2}$
$\mathrm{\exists }$ an isomorphism $\varphi :{H}_{1}\to {H}_{2}$
i.e. we have a finite generating set (in fact a basis) $\left\{{h}_{1},\dots ,{h}_{n}\right\}$ for ${H}_{1}$ (and$\left\{{h}_{1}\prime ,\dots ,{h}_{n}^{\prime }\right\}$ for ${H}_{2}$) and generating sets $X,Y$ for ${F}_{1}$ and ${F}_{2}$

Consider a group generated by ${z}_{1},\dots ,{z}_{m}$, with
${z}_{1}={h}_{1}\left({x}_{1},\dots ,{x}_{n}\right)={h}_{1}\prime \left({y}_{1},\dots ,{y}_{r}\right),\dots ,{z}_{m}={h}_{m}\left({x}_{1},\dots ,{x}_{n}\right)={h}_{m}^{\prime }\left({y}_{1},\dots ,{y}_{r}\right)$
$G={F}_{1}\underset{{H}_{1}={H}_{2}}{\ast }{F}_{2}$ has presentation $⟨X,Y|{h}_{i}={h}_{i}^{\prime },i=1\dots m⟩$
Choose a set $S\subseteq F$ such that ${F}_{1}=\bigcup _{s\in S}{H}_{1}s{H}_{1}$
(we are assuming $S$ is infinite)
every element $w$ of ${F}_{1}$ is equal to $w={h}_{1}s{h}_{2}$, for unique $s\in S$,
${h}_{1},{h}_{2}\in {H}_{1}$
can do the same for ${F}_{2}=\bigcup _{t\in T}{H}_{2}t{H}_{2}$

Let $g\in G$.
A word $w$ representing $g$ is in normal form if $w={h}_{{i}_{1}}\left(z\right){p}_{1}{h}_{{i}_{2}}\left(z\right){p}_{2}\dots {h}_{{i}_{k}}\left(z\right){p}_{k}{h}_{{i}_{k+1}}\left(z\right)$, with ${p}_{i}\in S$, $i=1\dots k$.

Suppose $g={g}_{1}{g}_{2}\dots {g}_{k}$. Rewrite using double coset representatives
$g={h}_{1}\left(X\right){s}_{1}{h}_{2}\left(Y\right){t}_{2}{h}_{3}\left(X\right)\dots$

$g$ is in reduced form if $g={g}_{1}\dots {g}_{k}$ and
$k=1⇒$ $g\in {F}_{1}$ or $g\in {F}_{2}$
$k>1⇒{g}_{i}\in {F}_{1}\mathrm{\setminus }{H}_{1}$ or ${g}_{i}\in {F}_{2}\mathrm{\setminus }{H}_{2}$ and ${g}_{i}$, ${g}_{i+1}$ belong to different factors

Let ${\mathrm{\Gamma }}_{{H}_{1}}$ be a folded subgroup graph of ${H}_{1}$. Take two copies.

For some word $w={h}_{1}s{h}_{2}$, the question is how to find $s$.

Algorithm:
Read all possible loops round first graph, to get ${h}_{1}$.
Keep reading letters round the graph until there is no edge corresponding to the current letter. Call this ${s}_{1}$.
Start at the other end, reading loops to get ${h}_{2}$, and then maximal ${s}_{2}$ partway round a loop.
Then either there are no letters left to look at, and $s={s}_{1}{s}_{2}$, or some bit ${f}_{0}$ in the middle, and $s={s}_{1}{f}_{0}{s}_{2}$.

We want ${h}_{1},{h}_{2},s$ to all have maximal length.

Example

i) $\begin{array}{rl}g& ={x}_{1}^{3}{x}_{2}^{2}{y}_{1}{y}_{2}\\ & =\left({x}_{1}^{2}\right)\left({x}_{1}{x}_{2}\right)\left({x}_{2}^{-1}{\right)}^{-1}\cdot \left({y}_{1}\right)\left({y}_{2}^{-1}{\right)}^{-1}\end{array}$

## Membership problem

$\begin{array}{rl}G& ={F}_{1}\underset{{H}_{1}={H}_{2}}{\ast }{F}_{2}\\ {H}_{3}& =⟨{c}_{1},\dots ,{c}_{l}⟩⩽G\end{array}$
Can write the ${c}_{i}$ in normal form.
Question: Given $w\in G$ in normal form, is $w\in {H}_{3}$?

Constructing a folded graph which makes use of the normal form is tricky.