Skip to main content

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:
F1, F2 free groups (finitely generated by X and Y, respectively)
H1F1, H2F2
an isomorphism ϕ:H1H2
i.e. we have a finite generating set (in fact a basis) {h1,,hn} for H1 (and{h1,,hn} for H2) and generating sets X,Y for F1 and F2

Consider a group generated by z1,,zm, with
z1=h1(x1,,xn)=h1(y1,,yr),,zm=hm(x1,,xn)=hm(y1,,yr)
G=F1H1=H2F2 has presentation X,Y|hi=hi,i=1m
Choose a set SF such that F1=sSH1sH1
(we are assuming S is infinite)
every element w of F1 is equal to w=h1sh2, for unique sS,
h1,h2H1
can do the same for F2=tTH2tH2

Let gG.
A word w representing g is in normal form if w=hi1(z)p1hi2(z)p2hik(z)pkhik+1(z), with piS, i=1k.

Suppose g=g1g2gk. Rewrite using double coset representatives
g=h1(X)s1h2(Y)t2h3(X)

g is in reduced form if g=g1gk and
k=1 gF1 or gF2
k>1giF1H1 or giF2H2 and gi, gi+1 belong to different factors

Let ΓH1 be a folded subgroup graph of H1. Take two copies.

For some word w=h1sh2, the question is how to find s.

Algorithm:
Read all possible loops round first graph, to get h1.
Keep reading letters round the graph until there is no edge corresponding to the current letter. Call this s1.
Start at the other end, reading loops to get h2, and then maximal s2 partway round a loop.
Then either there are no letters left to look at, and s=s1s2, or some bit f0 in the middle, and s=s1f0s2.

We want h1,h2,s to all have maximal length.

Example

i) g=x13x22y1y2=(x12)(x1x2)(x21)1(y1)(y21)1

Membership problem

G=F1H1=H2F2H3=c1,,clG
Can write the ci in normal form.
Question: Given wG in normal form, is wH3?

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