Program to find intersection of subgroups of free groups

Question

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?

Answer 1

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.

Further reading

• For more details on dealing with Free Groups in GAP see: "Free Group Algorithms"

• For details on Finitely Presented Groups in GAP see: Chapter 47 of the GAP manual

• To learn the basics of programming in GAP check out the Carpentries-style lesson "Programming with GAP"

Answer 2

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)$.