7
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ You're likely to find something in GAP. $\endgroup$
    – Shaun
    Commented Aug 2, 2019 at 15:58

2 Answers 2

9
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ It's worth pointing out, in reference to the question, that Myasnikov and Schupp wrote a paper about Stallings foldings, which was motivated "by the desire to describe various algorithms implemented inthe Computational Group Theory Software Package MAGNUS." (I believe much of MAGNUS was folded into GAP, but I'm not sure.) $\endgroup$
    – user1729
    Commented Jun 6, 2020 at 20:15
  • $\begingroup$ Here is an alternative description of (essentially) the same algorithm. Use Todd-Coxeter coset enumeration to compute finite state automata of which the accepted languages are the reduced words that represent elements in the two subgroups. Then compute the automaton whose language is the intersection of the languages of those for the two subgroups. $\endgroup$
    – Derek Holt
    Commented Jun 6, 2020 at 20:23
  • $\begingroup$ I think that GAP implements this allgorithm:google.com/url?sa=t&source=web&rct=j&url=https://… $\endgroup$
    – markvs
    Commented Jun 6, 2020 at 20:42
  • $\begingroup$ *Kapovich and Myasnikov, not Myasnikov and Schupp $\endgroup$
    – user1729
    Commented Jun 6, 2020 at 21:19
  • $\begingroup$ @user1729: Here is an earlier paper on subgroupa of free groups and algorithmsJ.-C. Birget, S. Margolis, J. Meakin, and P. Weil, PSPACE-complete problems for subgroups of free groups and inverse finite automata, Theoretical Computer Science 242 (2000) No. 1-2, 247-281. $\endgroup$
    – markvs
    Commented Jun 6, 2020 at 22:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .