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
    $\begingroup$ You're likely to find something in GAP. $\endgroup$ – Shaun Aug 2 '19 at 15:58
8
$\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

| cite | improve this answer | |
$\endgroup$
1
$\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)$.

| cite | improve this answer | |
$\endgroup$
  • $\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 Jun 6 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 Jun 6 at 20:23
  • $\begingroup$ I think that GAP implements this allgorithm:google.com/url?sa=t&source=web&rct=j&url=https://… $\endgroup$ – JCAA Jun 6 at 20:42
  • $\begingroup$ *Kapovich and Myasnikov, not Myasnikov and Schupp $\endgroup$ – user1729 Jun 6 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$ – JCAA Jun 6 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.