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) $\{{h}_{1},\dots ,{h}_{n}\}$ for ${H}_{1}$ (and$\{{h}_{1}\prime ,\dots ,{h}_{n}^{\prime}\}$ 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}({x}_{1},\dots ,{x}_{n})={h}_{1}\prime ({y}_{1},\dots ,{y}_{r}),\dots ,{z}_{m}={h}_{m}({x}_{1},\dots ,{x}_{n})={h}_{m}^{\prime}({y}_{1},\dots ,{y}_{r})$

$G={F}_{1}\underset{{H}_{1}={H}_{2}}{\ast}{F}_{2}$ has presentation $\u27e8X,Y|{h}_{i}={h}_{i}^{\prime},i=1\dots m\u27e9$

Choose a set $S\subseteq F$ such that ${F}_{1}={\displaystyle \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}={\displaystyle \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}}(z){p}_{1}{h}_{{i}_{2}}(z){p}_{2}\dots {h}_{{i}_{k}}(z){p}_{k}{h}_{{i}_{k+1}}(z)$, 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}(X){s}_{1}{h}_{2}(Y){t}_{2}{h}_{3}(X)\dots $

$g$ is in *reduced form* if $g={g}_{1}\dots {g}_{k}$ and

$k=1\Rightarrow $ $g\in {F}_{1}$ or $g\in {F}_{2}$

$k>1\Rightarrow {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}\\ & =({x}_{1}^{2})({x}_{1}{x}_{2})({x}_{2}^{-1}{)}^{-1}\cdot ({y}_{1})({y}_{2}^{-1}{)}^{-1}\end{array}$

## Membership problem

$$\begin{array}{rl}G& ={F}_{1}\underset{{H}_{1}={H}_{2}}{\ast}{F}_{2}\\ {H}_{3}& =\u27e8{c}_{1},\dots ,{c}_{l}\u27e9\u2a7dG\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.