# Program to find intersection of subgroups of free groups

As the title says, I am working on examples for a research project I'm doing, and I need a way to efficiently calculate the intersection of subgroups of a free group (say, of rank 2). Are there any computer programs to do this, or any papers explaining how such a program could be written?

• You're likely to find something in GAP. – Shaun Aug 2 '19 at 15:58

The (free) computer algebra system - GAP may be what you are looking for. There is a package within GAP called "Free Group Algorithms"

Here is an example GAP session to demonstrate some features and an example you might be interested in.

gap> f:= FreeGroup("a","b");
<free group on the generators [ a, b ]>
gap> AssignGeneratorVariables(f);
#I  Assigned the global variables [ a, b ]
gap> u := Group(a^2, b^2, a*b);
Group([ a^2, b^2, a*b ])
gap> v := Group( a^3, b);
Group([ a^3, b ])
gap> w := Intersection(u, v);
Group(<free, no generators known>)
gap> RankOfFreeGroup(w);
3
gap> MinimalGeneratingSet(w);
[ b^2, a^3*b^-1, b*a^3 ]


In particular we create the free group of rank 2, with generators $$a$$ and $$b$$. Then we create a subgroup $$u$$ generated by $$a^{2}, b^{2}, ab$$ and another subgroup $$v$$ generated by $$a^3$$ and $$b$$.

We find the intersection of these two subgroups, and then find the rank of the intersection and a minimal generating set for it.

The algorithm is easy and well known. Let $$A, B$$ be finitely generated subgroups of a free group $$F$$. Construct the Stallings cores $$U,V$$ of these subgroups. These are labeled graphs whose labels-generators of $$F$$ and which have basepoints $$u,v$$. Then $$A$$ (resp. $$B$$) consists of all labels of reduced loops of $$U$$ (resp. $$V$$) at $$u$$ (resp. $$v$$). Then consider the pull-back graph $$U*V$$ which has vertices $$(x,y)$$ where $$x$$ is a vertex of $$U$$, $$y$$ is a vertex of $$V$$. The edges have the form $$(x,y)--(xs,ys)$$ where $$[x,xs]$$ (resp $$[y,ys]$$) is an edge of $$U$$ (resp. $$V$$) starting at $$x$$ (resp. $$y$$) and labeled by $$s$$. Then $$A\cap B$$ is the set of labels of reduced loops of $$U*V$$ at $$(u,v)$$. That is $$A\cap B$$ is the fundamental group of $$U*V$$ with basepoint $$(u,v)$$.