# -*- coding: utf-8 -*-
r"""
The class ``FinitelyGeneratedSubgroup`` is meant to represent finitely generated subgroups of free groups
The representation of a ``FinitelyGeneratedSubgroup`` is a tuple of partial injections on a set of the form `[0..(n-1)]` (one for each generator of the ambient free group), which represent the Stallings graph of the subgroup, with base vertex 0.
Methods implemented in this file:
- definition of a ``FinitelyGeneratedSubgroup`` from a list of generators (``Words``)
- definition of a ``FinitelyGeneratedSubgroup`` from a ``DiGraph`` (by folding and pruning)
- random instance
- ``ambient_group_rank``, to compute the rank of the ambient free group
- ``stallings_graph_size``
- ``rank``, to compute the rank of the subgroup
- ``stallings_graph``, to compute the Stallings graph of the subgroup
- ``show_Stallings_graph``, to visualize the Stallings graph
- ``is_valid``, to check the necessary properties of connectedness and trimness
- ``eq``, to check whether two objects represent the same finitely generated subgroup
- ``basis``
- ``contains_element``, to check whether the subgroup contains a given word
- ``contains_subgroup``, to check whether the subgroup contains a given subgroup
- ``intersection``
- ``has_index``, to compute the index of the subgroup
- ``conjugated_by``, to compute the conjugate of a subgroup by a given word
- ``is_conjugated_to``, to check whether two subgroups are conjugated and, optionally, compute a conjugating word
- ``is_malnormal``, to check whether the subgroup is malnormal and, optionally, compute a witness of its non-malnormality
- ``is_free_factor_of_ambient``, to check whether the subgroup is a free factor of the ambient group and, optionally, to compute a complement
- ``is_free_factor_of_``, to check whether the subgroup is a free factor of another and, optionally, to compute a complement
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: gens = ['ab','ba']
sage: G = FinitelyGeneratedSubgroup.from_generators(gens, alphabet_type='abc')
sage: G
A subgroup of the free group of rank 2, whose Stallings graph has 3 vertices
::
sage: gens = [[1,2,5,-1,-2,2,1],[-1,-2,2,3],[1,2,3]]
sage: G = FinitelyGeneratedSubgroup.from_generators(gens)
sage: G
A subgroup of the free group of rank 5, whose Stallings graph has 3 vertices
::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: from stallings_graphs.about_words import random_reduced_word
sage: from stallings_graphs.about_automata import bouquet
sage: L = [random_reduced_word(100,2) for _ in range(10)]
sage: G = bouquet(L)
sage: H = FinitelyGeneratedSubgroup.from_digraph(G)
sage: H # random
A subgroup of the free group of rank 2, whose Stallings graph has 965 vertices
::
sage: H = FinitelyGeneratedSubgroup.random_instance(15)
sage: H
A subgroup of the free group of rank 2, whose Stallings graph has 15 vertices
AUTHORS:
- Pascal WEIL (2018-04-26): initial version
CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr>
"""
from sage.structure.sage_object import SageObject
from sage.rings.integer_ring import ZZ
from sage.graphs.digraph import DiGraph
from sage.misc.cachefunc import cached_function
from sage.misc.latex import LatexExpr
from stallings_graphs.partial_injections import PartialInjection
from stallings_graphs.about_words import *
from stallings_graphs.about_automata import *
from stallings_graphs.about_bases import *
from stallings_graphs.about_folding import *
# remplacer * par le nom des fonctions utilisées
[docs]class FinitelyGeneratedSubgroup(SageObject):
r"""
Define the class ``FinitelyGeneratedSubgroup``, which represents subgroups of free groups.
The representation of a finitely generated subgroup is by means of the partial
injections (on a set of the form `[0..n-1]`, one per generator of the ambient free group)
which describes its Stallings graph, with base vertex 0. The Stallings graph of a subgroup is
a uniquely defined finite directed graph,
whose edges are labeled by positive letters, rooted in a designated
vertex, subject to three conditions: it must be connected, folded (no two edges
with the same label share the same initial (resp. terminal) vertex),
and every vertex must have valency 2 (in the underlying non-directed graph),
except possibly for the root (also known as base vertex). That is: a subgroup is represented by
a tuple of partial injections on `[0..n-1]`, up to a relabeling of the elements of `[0..n-1]`
fixing the base vertex (namely 0).
A ``FinitelyGeneratedSubgroup`` can be created from:
- a list of objects of the class ``PartialInjection``, all of the same size;
or
- a list of ``Words`` on a symmetrical alphabet: either `a`:`z` / `A`:`Z` (upper case is the inverse of lower case), so-called ``alphabet_type='abc'`` ; or `[-r..-1,1..r]`, so-called ``alphabet_type='123'``.
or
- a labeled ``DiGraph`` with vertex set `[0..(n-1)]` and edge labels in a positive alphabet (`a`:`z` if ``alphabet_type='abc'`` or `[1..r]` if ``alphabet_type='123'``). The ``DiGraph`` is considered to be rooted at vertex 0.
or
- a random instance.
"""
def __init__(self, partial_injections):
r"""
Create a ``FinitelyGeneratedSubgroup`` by specifying the list of objects of the
class ``PartialInjection``, which determines its Stallings graph.
The ``PartialInjection``objects are expected to have the same size, and their graph of
transitions must be connected, with every vertex except possibly 0 of valency at least 2.
NB - The first property is verified in ``__init__``, the other properties are not verified.
INPUT:
- ``partial_injections`` -- list of objects from the class ``PartialInjection``.
OUTPUT:
- an object of class ``FinitelyGeneratedSubgroup``.
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup, PartialInjection
sage: L = [[0,3,None,4,None,2],[None,2,3,None,1,0]]
sage: L = [PartialInjection(x) for x in L]
sage: H = FinitelyGeneratedSubgroup(L)
sage: H
A subgroup of the free group of rank 2, whose Stallings graph has 6 vertices
::
sage: H = FinitelyGeneratedSubgroup([])
sage: H
A subgroup of the free group of rank 0, whose Stallings graph has 1 vertices
::
sage: H = FinitelyGeneratedSubgroup([PartialInjection([None]),PartialInjection([None])])
sage: H
A subgroup of the free group of rank 2, whose Stallings graph has 1 vertices
.. WARNING::
An exception will be raised if the input is not a list or if the ``PartialInjection`` objects
in that list do not have the same size. There will be trouble if the input is a list
of other objects than ``PartialInjection``.
A list of `r` PartialInjections of the form `[``None``]` yields the trivial subgroup
in the rank `r` free group (including if `r = 0`).
If the graph defined by the input list of ``PartialInjection`` is not connected or if a
vertex other than the base vertex 0 has valency 1, the definition will go through
but the object will not represent a subgroup of a free group.
"""
if not isinstance(partial_injections, list):
raise TypeError('partial_injections(={}) must be of type list'.format(partial_injections))
if (partial_injections and any(partial_injections[0].size() != p.size() for p in partial_injections)):
raise ValueError('all partial injections must have the same length')
#
self._partial_injections = partial_injections
def __repr__(self):
r"""
Describe a ``FinitelyGeneratedSubgroup``.
The description consists in giving the rank of the ambient free group, that is,
the length of the list of ``PartialInjection`` objects which define the ``FinitelyGeneratedSubgroup``;
and the size of the Stallings graph, that is, the length of the partial injections.
INPUT:
- ``self`` -- an object of the class ``FinitelyGeneratedSubgroup``.
OUTPUT:
- a sentence describing the corresponding subgroup of a free group.
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup, PartialInjection
sage: L = [[0,3,None,4,None,2],[None,2,3,None,1,0]]
sage: M = [PartialInjection(x) for x in L]
sage: H = FinitelyGeneratedSubgroup(M)
sage: H
A subgroup of the free group of rank 2, whose Stallings graph has 6 vertices
"""
return 'A subgroup of the free group of rank {}, whose Stallings graph has {} vertices'.format(self.ambient_group_rank(), self.stallings_graph_size())
[docs] @staticmethod
def random_instance(size, ambient_rank=2, verbose=False):
r"""
Return a randomly chosen ``FinitelyGeneratedSubgroup``.
``size`` is expected to be at least 1 and ``ambient_rank`` is expected to be
at least 0 (a ``ValueError`` will be raised otherwise).
The ``FinitelyGeneratedSubgroup`` is picked uniformly at random among those
of the given size and with the same ambient free group rank.
If the option ``verbose`` is set to ``True``, also prints the number of attempts in the
rejection algorithm.
INPUT:
- ``size`` -- integer
- ``ambient_rank`` -- integer, default value 2
- ``verbose`` -- a boolean, default value False
OUTPUT:
- an object of the class ``FinitelyGeneratedSubgroup`` if ``verbose = False``,
and a tuple of an object of the class ``FinitelyGeneratedSubgroup`` and an integer otherwise
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup, PartialInjection
sage: H = FinitelyGeneratedSubgroup.random_instance(12)
sage: H
A subgroup of the free group of rank 2, whose Stallings graph has 12 vertices
::
sage: H = FinitelyGeneratedSubgroup.random_instance(2, ambient_rank = 0)
sage: H
A subgroup of the free group of rank 0, whose Stallings graph has 1 vertices
::
sage: H,c = FinitelyGeneratedSubgroup.random_instance(12,3,verbose=True)
sage: H
A subgroup of the free group of rank 3, whose Stallings graph has 12 vertices
::
sage: c #random
1
ALGORITHM:
This uses a rejection algorithm. It consists in drawing uniformly at random
a tuple of ``ambient_rank`` partial injections, each of size ``size`` and testing
whether they define a valid ``FinitelyGeneratedSubgroup``. If they do not, the tuple
is tossed and another is drawn.
For a justification, see [BNW2008]_.
"""
if size < 1:
raise ValueError('the first (size) argument must be at least 1')
if ambient_rank < 0:
raise ValueError('the second (ambient_rank) argument must be at least 0')
counter = 0
while True:
partial_injections = [PartialInjection.random_instance(size) for _ in range(ambient_rank)]
H = FinitelyGeneratedSubgroup(partial_injections)
counter +=1
if H.is_valid():
return (H,counter) if verbose == True else H
[docs] @staticmethod
def from_digraph(G):
r"""
Return the ``FinitelyGeneratedSubgroup`` specified by a ``DiGraph``.
``G`` is expected to be a ``DiGraph`` with edge labels in `[1..r]`, whose vertices are a
set of non-negative integers including 0 (no verification is made). In particular,
the empty graph with no vertices is not admissible.
The Stallings graph of the finitely generated subgroup produced is obtained by choosing
0 as the base vertex, folding and pruning `G`.
INPUT:
- ``G`` -- ``DiGraph``
OUTPUT:
- an object of the class ``FinitelyGeneratedSubgroup``
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: L = ['abaBa', 'BaBaB', 'cacBac', 'AbAbb']
sage: from stallings_graphs.about_automata import bouquet
sage: G = bouquet(L, alphabet_type='abc')
sage: H = FinitelyGeneratedSubgroup.from_digraph(G)
sage: H
A subgroup of the free group of rank 3, whose Stallings graph has 14 vertices
::
sage: V = [0]
sage: E = []
sage: G = DiGraph([V,E], format='vertices_and_edges', loops=True, multiedges=True)
sage: H = FinitelyGeneratedSubgroup.from_digraph(G)
sage: H
A subgroup of the free group of rank 0, whose Stallings graph has 1 vertices
::
sage: V = [0]
sage: E = [(0,0,1)]
sage: G = DiGraph([V,E], format='vertices_and_edges', loops=True, multiedges=True)
sage: H = FinitelyGeneratedSubgroup.from_digraph(G)
sage: H
A subgroup of the free group of rank 1, whose Stallings graph has 1 vertices
::
sage: V = [0]
sage: E = [(0,0,3)]
sage: G = DiGraph([V,E], format='vertices_and_edges', loops=True, multiedges=True)
sage: H = FinitelyGeneratedSubgroup.from_digraph(G)
sage: H
A subgroup of the free group of rank 3, whose Stallings graph has 1 vertices
.. WARNING::
No exception will be raised if the input is not of the expected type.
"""
GG = NT_fold(G)
GGG = pruning(GG)
partial_injections = DiGraph_to_list_of_PartialInjection(GGG)
return FinitelyGeneratedSubgroup(partial_injections)
[docs] @staticmethod
def from_generators(generators, alphabet_type = '123'):
r"""
Return the ``FinitelyGeneratedSubgroup`` specified by a set of generators.
``generators`` is expected to be a list of valid ``Word`` objects, either numerical or
alphabetical, in accordanc with the value of ``alphabet_type``.
The ``FinitelyGeneratedSubgroup`` produced represents the subgroup generated by these words.
It is computed by operating a free group reduction on the elements of generators, computing the
bouquet of these words and then creating the ``FinitelyGeneratedSubgroup`` specified by the bouquet.
INPUT:
- ``generators`` -- a tuple of ``Word`` objects
OUTPUT:
- an object of the class ``FinitelyGeneratedSubgroup``
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: gens = ['ab','ba']
sage: H = FinitelyGeneratedSubgroup.from_generators(gens, alphabet_type='abc')
sage: H
A subgroup of the free group of rank 2, whose Stallings graph has 3 vertices
::
sage: gens = [[1,2,5,-1,-2,2,1],[-1,-2,2,3],[1,2,3]]
sage: H = FinitelyGeneratedSubgroup.from_generators(gens)
sage: H
A subgroup of the free group of rank 5, whose Stallings graph has 3 vertices
::
sage: L = []
sage: H = FinitelyGeneratedSubgroup.from_generators(L)
sage: H
A subgroup of the free group of rank 0, whose Stallings graph has 1 vertices
::
sage: L = [[2]]
sage: H = FinitelyGeneratedSubgroup.from_generators(L)
sage: H
A subgroup of the free group of rank 2, whose Stallings graph has 1 vertices
.. WARNING::
No exception will be raised if the input is not of the expected type. Also:
``generators`` can be an empty list.
"""
if alphabet_type == 'abc':
gens = [translate_alphabetic_Word_to_numeric(w) for w in generators]
elif alphabet_type == '123':
gens = generators
else:
raise ValueError('last argument must be "abc" or "123" (default)')
reduced_gens = [free_group_reduction(w) for w in gens]
G = bouquet(reduced_gens)
return FinitelyGeneratedSubgroup.from_digraph(G)
[docs] def ambient_group_rank(self):
r"""
Return the rank of the ambient free group of this ``FinitelyGeneratedSubgroup`` object.
Exploits the fact that the rank of the ambient free group is the number of partial
injections which specify this ``FinitelyGeneratedSubgroup``.
INPUT:
- ``self`` -- a ``FinitelyGeneratedSubgroup``
OUTPUT:
- an integer
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup, PartialInjection
sage: L = [PartialInjection([1,2,None,4,5,3]), PartialInjection([0,3,4,None,None,None])]
sage: H = FinitelyGeneratedSubgroup(L)
sage: H.ambient_group_rank()
2
::
sage: L = []
sage: H = FinitelyGeneratedSubgroup.from_generators(L)
sage: H.ambient_group_rank()
0
"""
return len(self._partial_injections)
[docs] def stallings_graph_size(self):
r"""
Return the size of this ``FinitelyGeneratedSubgroup``.
The size of the ``FinitelyGeneratedSubgroup`` is the number of vertices of the Stallings
graph of the subgroup it represents. It is equal to the (common) length of the partial
injections defining it.
INPUT:
- ``self`` -- ``FinitelyGeneratedSubgroup``
OUTPUT:
- an integer
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup, PartialInjection
sage: L = [PartialInjection([1,2,None,4,5,3]), PartialInjection([0,3,4,None,None,None])]
sage: H = FinitelyGeneratedSubgroup(L)
sage: H.stallings_graph_size()
6
::
sage: L = []
sage: H = FinitelyGeneratedSubgroup.from_generators(L)
sage: H.stallings_graph_size()
1
"""
if self._partial_injections:
return self._partial_injections[0].size()
else:
return 1
[docs] def rank(self):
r"""
Return the rank of this ``FinitelyGeneratedSubgroup``.
The rank of this ``FinitelyGeneratedSubgroup`` is equal to ``edges`` - ``vertices`` + 1,
where ``vertices`` and ``edges`` refer to the number of vertices and edges of the Stallings
graph of the corresponding subgroup. In particular ``vertices`` is ``stallings_graph_size``
and ``edges`` is the sum of the domain sizes of the partial injections.
INPUT:
- ``self`` -- ``FinitelyGeneratedSubgroup``
OUTPUT:
- an integer
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup, PartialInjection
sage: L = [PartialInjection([1,2,None,4,5,3]), PartialInjection([0,3,4,None,None,None])]
sage: H = FinitelyGeneratedSubgroup(L)
sage: H.rank()
3
:
sage: L = []
sage: H = FinitelyGeneratedSubgroup.from_generators(L)
sage: H.rank()
0
"""
number_of_edges = sum([p.domain_size() for p in self._partial_injections])
rank = number_of_edges - self.stallings_graph_size() + 1
return rank
[docs] def stallings_graph(self):
r"""
Return the Stallings ``DiGraph`` of this ``FinitelyGeneratedSubgroup``.
The Stallings graph of the subgroup of a free group represented
by this ``FinitelyGeneratedSubgroup`` is an edge-labeled ``DiGraph``. The vertex set
is `[0..(n-1)]`, where `n` is the ``size`` of the input. The base vertex is 0. If `r` is
the ``ambient_group_rank`` of the input, each of the `r` partial injections defining the
``FinitelyGeneratedSubgroup`` specifies the edges labeled by that particular letter.
INPUT:
- ``self`` -- ``FinitelyGeneratedSubgroup``
OUTPUT:
- a DiGraph
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup, PartialInjection
sage: L = [PartialInjection([1,2,None,4,5,3]), PartialInjection([0,3,4,None,None,None])]
sage: H = FinitelyGeneratedSubgroup(L)
sage: G = H.stallings_graph()
sage: G
Looped multi-digraph on 6 vertices
::
sage: L = []
sage: H = FinitelyGeneratedSubgroup.from_generators(L)
sage: G = H.stallings_graph()
sage: G
Looped multi-digraph on 1 vertex
"""
edges = []
vertices = [0]
if self._partial_injections:
vertices = range(self.stallings_graph_size())
partial_injections_as_lists = [pinj._list_of_images for pinj in self._partial_injections]
for i,p in enumerate(partial_injections_as_lists):
edges.extend([(j,image_j,i + 1) for (j,image_j) in enumerate(p)
if not image_j is None])
G = DiGraph([vertices, edges], format='vertices_and_edges', loops=True, multiedges=True)
return G
[docs] def show_Stallings_graph(self,alphabet_type='abc',visu_tool='plot'):
r"""
Show the Stallings graph of this ``FinitelyGeneratedSubgroup``.
Edge labels can be of the form `a_1,...,a_r` (``alphabet_type='123'``) or of the form
`a,b,c,...,z` (``alphabet_type='abc'``). The visualization tool can be ``graph.plot``
(with a color coding for the base vertex) or Sébastien Labbé's ``TikzPicture``
`method <http://www.slabbe.org/Sage>`_.
INPUT:
- ``self`` -- a ``FinitelyGeneratedSubgroup``
- ``alphabet_type`` -- a string which is either ``'abc'`` or ``'123'``
- ``visu_tool`` -- a string which is either ``'plot'`` or ``'tikz'``
OUTPUT:
- a visualization of the Stallings graph using ``graph.plot`` or using ``TikzPicture``,
according to the value of ``visu_tool``. In the ``'tikz'`` case, the output can be saved
as a ``.png``, ``.pdf`` or ``.tex`` file
EXAMPLES ::
sage: from stallings_graphs import FinitelyGeneratedSubgroup, PartialInjection
sage: L = [PartialInjection([1,2,None,4,5,3]), PartialInjection([0,3,4,None,None,None])]
sage: H = FinitelyGeneratedSubgroup(L)
sage: H.show_Stallings_graph(alphabet_type='abc',visu_tool='plot')
Graphics object consisting of 28 graphics primitives
::
sage: t = H.show_Stallings_graph(alphabet_type='abc',visu_tool='tikz')
sage: # one can then type t.png, t.tex, t.pdf
"""
G = self.stallings_graph()
GG = prepare4visualization_graph(G,alphabet_type=alphabet_type,visu_tool=visu_tool)
if visu_tool == 'plot':
return show_rooted_graph(GG,0)
elif visu_tool == 'tikz':
from slabbe import TikzPicture
return TikzPicture.from_graph(GG, merge_multiedges=False, edge_labels=True, color_by_label=False, prog='dot')
[docs] def is_valid(self, verbose=False):
r"""
Return whether this ``FinitelyGeneratedSubgroup`` input really defines a subgroup.
If ``verbose`` is set to ``True``, indications are given if the input is not valid, on
the first reason encountered why it is the case. In order: not all elements of
``partial_injections`` are actually partial injections; the graph is not
connected; some vertex other than 0 has degree less than 2.
INPUT:
- ``self`` -- ``FinitelyGeneratedSubgroup``
- ``verbose`` -- boolean
OUTPUT:
- a boolean if ``verbose`` is set to ``False``; a pair of a boolean and a string otherwise
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup, PartialInjection
sage: L = [PartialInjection([1,2,None,4,5,3]), PartialInjection([0,3,4,None,None,None])]
sage: H = FinitelyGeneratedSubgroup(L)
sage: H.is_valid()
True
::
sage: M = [PartialInjection([1,2,None,4,5,3]), PartialInjection([0,2,1,None,4,3])]
sage: K = FinitelyGeneratedSubgroup(M)
sage: K.is_valid()
False
ALGORITHM:
The first verification is whether every element of the input's constitutive list of
partial injections is indeed a valid partial injection. The fact that these partial
injections all have the same size was checked when this list was made into a
``FinitelyGeneratedSubgroup``. The next steps are to verify whether the graph
induced by these partial injections is connected, and that all the vertices except
for the base vertex (vertex 0) have degree at least 2.
.. WARNING::
It is not checked whether the input is of the correct type.
"""
from stallings_graphs.partial_injections import is_valid_partial_injection
b1 = all(is_valid_partial_injection(p._list_of_images) for p in self._partial_injections)
if verbose:
if not b1:
print('not all given partial injections are truly partial injections')
else:
print('all given partial injections are okay')
if b1:
G = self.stallings_graph()
b1 = b1 and G.is_connected()
if verbose:
if not b1:
print('the resulting graph is not connected')
else:
print('the graph is connected')
if b1:
b2 = True
for v in G.vertices():
if not(v == 0) and G.degree(v) < 2:
b2 = False
v_exceptional = v
b1 = b1 and b2
if verbose:
if not b1:
print('vertex {} has degree less than 2'.format(v_exceptional))
else:
print('all vertices other than the base vertex (#0) have degree at least 2')
return b1
def __eq__(self, other):
r"""
Return whether these two FinitelyGeneratedSubgroup s represent the same subgroup.
Both arguments are expected to be objects of class FinitelyGeneratedSubgroup. A ValueError
is raised if other is not a FinitelyGeneratedSubgroup. The two objects
represent the same subgroup if the Stallings graphs (or the tuple of PartialInjection s)
coincide up to a relabeling of the vertices that fixes the base vertex (vertex 0).
INPUT:
- ``self`` -- a FinitelyGeneratedSubgroup
- ``other`` -- a FinitelyGeneratedSubgroup
OUTPUT:
- a boolean
EXAMPLES ::
sage: from stallings_graphs import FinitelyGeneratedSubgroup, PartialInjection
sage: L1 = [PartialInjection([1,2,None,4,5,3]), PartialInjection([0,3,4,None,None,None])]
sage: H1 = FinitelyGeneratedSubgroup(L1)
sage: L2 = [PartialInjection([1,2,None,5,3,4]), PartialInjection([0,3,5,None,None,None])]
sage: H2 = FinitelyGeneratedSubgroup(L2)
sage: gens = ['baaaB','aabAB']
sage: H3 = FinitelyGeneratedSubgroup.from_generators(gens, alphabet_type='abc')
sage: othergens = ['b','aabaaBA','abaBAA']
sage: H4 = FinitelyGeneratedSubgroup.from_generators(othergens, alphabet_type='abc')
sage: H1 == H2
True
::
sage: H2 == H3
False
::
sage: H1 == H4
True
::
sage: H = FinitelyGeneratedSubgroup.from_generators([])
sage: K = FinitelyGeneratedSubgroup([])
sage: H == K
True
ALGORITHM:
The verification of equality is delegated to the is_the_same method.
"""
b = isinstance(other, FinitelyGeneratedSubgroup)
if not b:
print('the second argument is not a FinitelyGeneratedSubgroup')
return False
else:
G = self.stallings_graph()
H = other.stallings_graph()
return are_equal_as_rooted_unlabeled(G,H)
# return self.is_the_same_as(other)
[docs] def has_index(self):
r"""
Return the index of this subgroup if it is finite, ``+Infinity`` otherwise.
INPUT:
- ``self`` -- a ``FinitelyGeneratedSubgroup``
OUTPUT:
- an integer or ``+Infinity``
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: L = [[3,1,-2,-1,3],[1,2,-1,-2,1,2],[1,2,-3,-3,1]]
sage: H = FinitelyGeneratedSubgroup.from_generators(L)
sage: H.has_index()
+Infinity
::
sage: H = FinitelyGeneratedSubgroup([])
sage: H.has_index()
1
::
sage: HH = FinitelyGeneratedSubgroup.from_generators(['ab', 'ba', 'Abab'], alphabet_type = 'abc')
sage: HH.has_index()
2
"""
if all(p.is_permutation() for p in self._partial_injections):
return self.stallings_graph_size()
else:
from sage.rings.infinity import Infinity as oo
return oo
[docs] def basis(self, alphabet_type = 'abc'):
r"""
Return a basis of this subgroup.
The input is expected to be an object of the class ``FinitelyGeneratedSubgroup``.
The variable ``alphabet_type`` determines whether the words in the output
are numerical or alphabetic.
INPUT:
- ``self`` -- a ``FinitelyGeneratedSubgroup``
- ``alphabet_type`` -- a string, which is either ``'abc'`` or ``'123'``
OUTPUT: A list of objects of the class ``Word``
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: L = [[3,1,-2,-1,3],[1,2,-1,-2,1,2],[1,2,-3,-3,1]]
sage: H = FinitelyGeneratedSubgroup.from_generators(L)
sage: H.basis(alphabet_type = '123')
[word: -3,1,2,-1,-3, word: -2,-1,2,1,-2,-1, word: -1,3,3,-2,-1]
::
sage: H.basis()
[word: CabAC, word: BAbaBA, word: AccBA]
::
sage: H = FinitelyGeneratedSubgroup([])
sage: H.basis()
[]
::
sage: H = FinitelyGeneratedSubgroup.from_generators(['A'],alphabet_type = 'abc')
sage: H.basis()
[word: a]
"""
G = self.stallings_graph()
T,L,D = spanning_tree_and_paths(G)
B = basis_from_spanning_tree(G, T, D,alphabet_type=alphabet_type)
# if alphabet_type == 'abc':
# B = [translate_numeric_Word_to_alphabetic(w) for w in B]
return B
[docs] def intersection(self, K):
r"""
Return the intersection of two subgroups.
Both inputs are expected to be objects of class ``FinitelyGeneratedSubgroup``. We
understand both to be subgroups of the rank `r` free group, where `r` is the maximum
of the ambient group ranks of the input subgroups. The intersection is also
understood to be a subgroup of the same rank `r` free group.
INPUT:
- ``self`` -- ``FinitelyGeneratedSubgroup``
- ``other`` -- ``FinitelyGeneratedSubgroup``
OUTPUT:
- ``FinitelyGeneratedSubgroup``
EXAMPLES ::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: L = [[2,1,-2,2,1,-2], [2,3,1,-3,3,1,-2]]
sage: H = FinitelyGeneratedSubgroup.from_generators(L)
sage: M = ['ab','ba', 'bdaB']
sage: K = FinitelyGeneratedSubgroup.from_generators(M, alphabet_type = 'abc')
sage: H.intersection(K)
A subgroup of the free group of rank 4, whose Stallings graph has 1 vertices
::
sage: L = ['ab', 'aaBa', 'bbAb']
sage: H = FinitelyGeneratedSubgroup.from_generators(L, alphabet_type = 'abc')
sage: M = ['ab', 'bbbb', 'baba', 'aa']
sage: K = FinitelyGeneratedSubgroup.from_generators(M, alphabet_type = 'abc')
sage: S = H.intersection(K)
sage: S.basis()
[word: baba, word: baBaBB, word: ab, word: AbAA]
"""
r = max(self.ambient_group_rank(),K.ambient_group_rank())
GH = self.stallings_graph()
GK = K.stallings_graph()
GHK = fibered_product(GH,GK)
V = GHK.connected_component_containing_vertex((0,0))
G = GHK.subgraph(V)
G = normalize_vertex_names(G)
G = pruning(G)
n = len(G.vertices())
pinj = [PartialInjection([None for _ in range(n)]) for _ in range(r)]
if G.edges():
PI = DiGraph_to_list_of_PartialInjection(G)
for a in range(len(PI)):
pinj[a] = PI[a]
return FinitelyGeneratedSubgroup(pinj)
[docs] def is_malnormal(self, alphabet_type='123', witness=False):
r"""
Return whether this subgroup is malnormal.
The first argument is assumed to be an object of class ``FinitelyGeneratedSubgroup``.
The second argument determines whether words are to be represented numerically or
alphabetically. This makes a difference only if ``witness`` is set to ``True``. In that
case, the output includes witness words `s,t` such that `s` belongs to the intersection
of `H` and `t^{-1} H t`.
INPUT:
- ``self`` -- ``FinitelyGeneratedSubgroup``
- ``alphabet_type`` -- a string which is either ``'abc'`` or ``'123'``
- ``witness`` -- a boolean
OUTPUT:
- a boolean if ``witness`` is set to ``False``; and if ``witness`` is set to ``True``, then
a tuple of the form ``(True, None, None)`` if the subgroup is malnormal, and of the form
``(False,s,t)`` if it is not, where `s` and `t` are of the class ``Word``.
EXAMPLES ::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: L = [[2,1,-2,2,1,-2], [2,3,1,-3,3,1,-2]]
sage: H = FinitelyGeneratedSubgroup.from_generators(L)
sage: H.is_malnormal()
False
::
sage: L = ['ab', 'aaBa', 'bbAb']
sage: H = FinitelyGeneratedSubgroup.from_generators(L, alphabet_type = 'abc')
sage: H.is_malnormal()
False
::
sage: L = ['baB', 'ababa', 'aababbb']
sage: H = FinitelyGeneratedSubgroup.from_generators(L, alphabet_type = 'abc')
sage: H.is_malnormal()
True
::
sage: M = ['ab', 'bbbb', 'baba', 'aa']
sage: K = FinitelyGeneratedSubgroup.from_generators(M, alphabet_type = 'abc')
sage: K.is_malnormal()
False
::
sage: H = FinitelyGeneratedSubgroup.from_generators(['a'], alphabet_type = 'abc')
sage: H.is_malnormal()
True
::
sage: H = FinitelyGeneratedSubgroup([])
sage: H.is_malnormal()
True
::
sage: L = ['aba', 'abb', 'aBababA']
sage: H = FinitelyGeneratedSubgroup.from_generators(L, alphabet_type='abc')
sage: H.is_malnormal(alphabet_type='abc', witness=True)
(False, word: aba, word: aB)
TODO :
The algorithm is quadratic and that is rather inefficient for large instances. One would probably gain significant time if, after verifying non malnormality, one could explore the (non-diagonal) connnected components starting with the smaller ones.
"""
G = self.stallings_graph()
GG = fibered_product(G,G)
CC = GG.connected_components()
# Let baseCC be the connected component containing vertex (0,0): it is isomorphic to G.
# The number E of edges of GG outside baseCC is len(GG.edges()) - len(G.edges())
# and the corresponding number of vertices V is len(GG.vertices()) - len(G.vertices()).
# The connected components of GG other than baseCC are all trees if and only if
# V - E = number of (non-base) connected components.
# All together, the formula to verify is
# len(GG.vertices()) + len(G.edges()) - len(G.vertices()) - len(GG.edges()) =
# len(CC) - 1
if len(GG.vertices()) + len(G.edges()) - len(G.vertices()) - len(GG.edges()) == len(CC) - 1:
return True if witness == False else (True,None,None)
# now the subgroup is not malnormal
if witness == False:
return False
# now the subgroup is not malnormal and we need a witness
baseCC = GG.connected_component_containing_vertex((0,0))
CC.remove(baseCC)
look_for_non_trivial_CC = True
i = 0
while look_for_non_trivial_CC:
GGX = GG.subgraph(vertices=CC[i])
if len(GGX.edges()) > len(CC[i]) - 1:
look_for_non_trivial_CC = False
else:
i += 1
X = CC[i]
# now X is an interesting connected component
T,L,P = spanning_tree_and_paths(GGX,root=X[0])
E = list(GGX.edges())
F = T.edges()
for e in F:
E.remove(e)
(p,q,a) = E[0]
u = P[p] + Word([a]) + group_inverse(P[q])
TG,LG,PG = spanning_tree_and_paths(G)
s = free_group_reduction(PG[X[0][0]] + u + group_inverse(PG[X[0][0]]))
t = free_group_reduction(PG[X[0][1]] + group_inverse(PG[X[0][0]]))
return (False, s, t) if alphabet_type=='123' else (False, translate_numeric_Word_to_alphabetic(s),translate_numeric_Word_to_alphabetic(t))
[docs] def contains_element(self, w, alphabet_type = '123'):
r"""
Return whether the subgroup contains the word `w`.
``w`` is expected to be a ``Word`` on a numerical alphabet (``alphabet_type = '123'``) or
on a letter alphabet (``alphabet_type = 'abc'``).
INPUT:
- ``self`` -- a ``FinitelyGeneratedSubgroup``
- ``w`` -- a ``Word``
- ``alphabet_type`` -- a string which is either ``'abc'`` or ``'123'``
OUTPUT:
- a boolean
EXAMPLES ::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: L = ['ab','ba', 'aBaa']
sage: H = FinitelyGeneratedSubgroup.from_generators(L, alphabet_type = 'abc')
sage: w = Word([1,-2,-2])
sage: H.contains_element(w)
False
::
sage: w = Word('abba')
sage: H.contains_element(w, alphabet_type = 'abc')
True
::
sage: w = Word()
sage: H.contains_element(w)
True
::
sage: H = FinitelyGeneratedSubgroup([])
sage: w = Word()
sage: H.contains_element(w)
True
::
sage: w = Word([1,2,1])
sage: H.contains_element(w)
False
"""
if alphabet_type == 'abc' and len(w) > 0:
w = translate_alphabetic_Word_to_numeric(w)
G = self.stallings_graph()
return (image_of_word(G,w) == 0)
[docs] def contains_subgroup(self, other):
r"""
Return whether the subgroup contains another subgroup.
``other`` is expected to be an object of class ``FinitelyGeneratedSubgroup``.
INPUT:
- ``self`` -- a ``FinitelyGeneratedSubgroup``
- ``other`` -- a ``FinitelyGeneratedSubgroup``
OUTPUT:
- a boolean
EXAMPLES ::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: L = ['ab','ba', 'aBaa']
sage: H = FinitelyGeneratedSubgroup.from_generators(L, alphabet_type = 'abc')
sage: M = ['ab','ba']
sage: K = FinitelyGeneratedSubgroup.from_generators(M, alphabet_type = 'abc')
sage: H.contains_subgroup(K)
True
::
sage: LL = ['abba','bAbA']
sage: K = FinitelyGeneratedSubgroup.from_generators(LL, alphabet_type = 'abc')
sage: H.contains_subgroup(K)
True
::
sage: H = FinitelyGeneratedSubgroup([])
sage: H.contains_subgroup(K)
False
::
sage: K.contains_subgroup(H)
True
"""
B = other.basis(alphabet_type='123')
return all(self.contains_element(b) for b in B)
[docs] def conjugated_by(self, w, alphabet_type = '123'):
r"""
Return the conjugate of this subgroup by the given word.
``w`` is expected to be a Word, on a numerical or letter alphabet, depending
on the value of ``alphabet_type``. The conjugate of a subgroup `H` by a word `w`
is the subgroup `w^{-1} H w`.
INPUT:
- ``self`` -- a ``FinitelyGeneratedSubgroup``
- ``w`` -- a Word
- ``alphabet_type`` -- a string which can be either ``'abc'`` or ``'123'``
OUTPUT:
- a ``FinitelyGeneratedSubgroup``
EXAMPLES ::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: L = ['ab','ba', 'aBaa']
sage: H = FinitelyGeneratedSubgroup.from_generators(L, alphabet_type = 'abc')
sage: H
A subgroup of the free group of rank 2, whose Stallings graph has 4 vertices
::
sage: w1 = Word('bA')
sage: K1 = H.conjugated_by(w1, alphabet_type='abc')
sage: K1
A subgroup of the free group of rank 2, whose Stallings graph has 4 vertices
::
sage: w2 = Word('bAA')
sage: K2 = H.conjugated_by(w2, alphabet_type='abc')
sage: K2
A subgroup of the free group of rank 2, whose Stallings graph has 5 vertices
::
sage: w = Word('abba')
sage: K3 = H.conjugated_by(w, alphabet_type='abc')
sage: H == K3
True
"""
n = self.stallings_graph_size()
lenw = len(w)
if alphabet_type == 'abc':
w = translate_alphabetic_Word_to_numeric(w)
G = self.stallings_graph()
(q,m,qq) = image_of_word(G, w, qinitial = 0, trace = True)
if q is None:
G.add_vertices(range(n, n + lenw - m))
if w[m] > 0:
G.add_edge((qq, n, w[m]))
else:
G.add_edge((n, qq, -w[m]))
for i in range(m + 1, lenw):
if w[i] > 0:
G.add_edge((n + i - m - 1, n + i - m, w[i]))
else:
G.add_edge((n + i - m, n + i - m - 1, - w[i]))
future_base_vertex = n + lenw - m - 1
else:
future_base_vertex = q
#
G = exchange_labels(G,0,future_base_vertex)
return FinitelyGeneratedSubgroup.from_digraph(G)
[docs] def is_conjugated_to(self, other, conjugator=False, alphabet_type = '123'):
r"""
Return whether self and other are conjugated.
If ``conjugator`` is set to ``True``, the output will also include a conjugator (``None`` if
the two subgroups are not conjugated). A word `w` is a conjugator of `H` into `K` if
`w^{-1} H w = K`.
INPUT:
- ``other`` -- ``FinitelyGeneratedSubgroup``
- ``conjugator`` -- boolean
- ``alphabet_type`` -- a string which can be either ``'abc'`` or ``'123'``
OUTPUT:
- a boolean or, if ``conjugator`` is ``True``, a tuple consisting of a boolean and a
``Word`` or ``None``.
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: generators = ['abCA', 'abbaBA', 'aCacA', 'abbbcA']
sage: H = FinitelyGeneratedSubgroup.from_generators(generators, alphabet_type='abc')
sage: other_gens = ['ba', 'bbcb', 'bbcc', 'bbaBB']
sage: K = FinitelyGeneratedSubgroup.from_generators(other_gens, alphabet_type='abc')
sage: H.is_conjugated_to(K)
True
::
sage: b,w = H.is_conjugated_to(K,conjugator=True,alphabet_type = 'abc')
sage: w
word: ac
"""
GH = self.stallings_graph()
if conjugator:
CRGH,w1 = cyclic_reduction(GH,trace=True)
else:
CRGH = cyclic_reduction(GH)
vCRGH = len(CRGH.vertices())
#
GK = other.stallings_graph()
if conjugator:
CRGK,w3 = cyclic_reduction(GK,trace=True)
else:
CRGK = cyclic_reduction(GK)
vCRGK = len(CRGK.vertices())
#
if vCRGH != vCRGK:
return (False, None) if conjugator else False
#
KK = FinitelyGeneratedSubgroup.from_digraph(CRGK)
for v in CRGH.vertices():
modifiedCRGH = exchange_labels(CRGH,0,v)
HH = FinitelyGeneratedSubgroup.from_digraph(modifiedCRGH)
if HH == KK:
if conjugator:
T,list_of_leaves,path_in_tree = spanning_tree_and_paths(CRGH)
w2 = path_in_tree[v]
w = w1 + w2 + group_inverse(w3)
w = free_group_reduction(w)
if alphabet_type == 'abc':
w = translate_numeric_Word_to_alphabetic(w)
return (True,w)
else:
return True
return (False, None) if conjugator else False
[docs] def SW_is_free_factor_of_ambient(self, complement = True, alphabet_type = '123'):
r"""
Return whether ``self`` is a free factor of the ambient group and, if ``complement`` is
set to ``True``, gives either a statement about it not being a free factor, or if it is,
a basis of a complement of ``self`` (in numerical or in alphabetic form depending on
``alphabet_type``).
INPUT:
- ``complement``-- boolean
- ``alphabet_type`` -- a string which can be either ``'abc'`` or ``'123'``
OUTPUT:
- a boolean if ``complement`` is ``False`` and a pair of a boolean and either a string of a list of objects of type ``Word`` otherwise
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: L1 = ['ac','bacd','ed']
sage: H1 = FinitelyGeneratedSubgroup.from_generators(L1, alphabet_type='abc')
sage: H1.SW_is_free_factor_of_ambient(complement = True, alphabet_type = 'abc')
(True, [word: baE, word: B])
::
sage: L2 = ['acac','bacd','ed']
sage: H2 = FinitelyGeneratedSubgroup.from_generators(L2, alphabet_type='abc')
sage: H2.SW_is_free_factor_of_ambient(complement = True, alphabet_type='abc')
(False, 'the 1st argument is not a free factor of the second')
::
sage: H = FinitelyGeneratedSubgroup.from_generators(['A','d'], alphabet_type='abc')
sage: H.SW_is_free_factor_of_ambient(complement = True, alphabet_type='abc')
(True, [word: b, word: c])
ALGORITHM:
The algorithm implemented is from [SW2008]_. Be aware that the worst-case complexity
is polynomial in the size of the argument subgroup but exponential in the rank
difference between that subgroup and the ambient group.
"""
from stallings_graphs.about_free_factors import SilvaWeil_free_factor_of_ambient
if complement:
(valeur,base) = SilvaWeil_free_factor_of_ambient(self, maxletter = 0, complement = True)
if alphabet_type == 'abc' and valeur == True:
base = [translate_numeric_Word_to_alphabetic(w) for w in base]
return (valeur,base)
else:
return SilvaWeil_free_factor_of_ambient(self, maxletter = 0, complement = False)
[docs] def SW_is_free_factor_of(self, other, complement = True, alphabet_type = '123'):
r"""
Return whether ``self`` is a free factor of ``other`` and, if ``complement`` is
set to ``True``, gives either a statement about it not being a free factor, or if it is,
a basis of a complement of ``self`` in ``other`` (in numerical or in alphabetic form
depending on ``alphabet_type``).
``other`` is expected to be a ``FinitelyGeneratedSubgroup``
INPUT:
- ``other`` -- ``FinitelyGeneratedSubgroup``
- ``complement`` -- boolean
- ``alphabet_type`` -- a string which can be either ``'abc'`` or ``'123'``
OUTPUT:
- a boolean if ``complement`` is ``False``, and a pair of a boolean and either a string or a list of objects of type ``Word`` otherwise
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: LH = [[2,-3,1,3,2,3,-2,-1,2,-3,-1], [3,1,1,1,-3,-1], [1,3,-2,-1,2,-1,2], [3,2,3,-1,2,-1]]
sage: LK = [[2,-3], [1,1], [1,3,-2,1,2,-3,-1], [3,2], [3,1,-3,-1], [1,3,2,-1], [1,3,3,-1], [1,3,1,-3]]
sage: H = FinitelyGeneratedSubgroup.from_generators(LH, alphabet_type='123')
sage: K = FinitelyGeneratedSubgroup.from_generators(LK, alphabet_type='123')
sage: H.SW_is_free_factor_of(K, complement = True)
(True, [word: 3,2,3,1,2,-1, word: 32, word: 3,1,3,-1, word: 11])
::
sage: H.SW_is_free_factor_of(K, complement = False)
True
::
sage: LH = [[-3,1,-2,-1,-1,-3,2,2,3], [-3,-1,-1,3,1,1,-3,-1,3,1,3,3], [-3,1,3,-1,-1,-3,1,1,1,3,-1,-1], [1,1,-3,1,3,1,1,-3,-1,3]]
sage: LK = [[1,1,2,-1,3], [1,1,3,-1], [-3,1,3,-1,-1], [-3,1,1,3], [-3,2,3], [1,3,3]]
sage: H = FinitelyGeneratedSubgroup.from_generators(LH, alphabet_type='123')
sage: K = FinitelyGeneratedSubgroup.from_generators(LK, alphabet_type='123')
sage: H.SW_is_free_factor_of(K, complement = True)
(False, 'the 1st argument is not a free factor of the second')
::
sage: H.SW_is_free_factor_of(K, complement = False)
False
::
sage: LH = [[3,1,-2,-1,-1,-3,2,2,3], [-3,-1,-1,3,1,1,-3,-1,3,1,3,3], [-3,1,3,-1,-1,-3,1,1,1,3,-1,-1], [1,1,-3,1,3,1,1,-3,-1,3]]
sage: LK = [[1,1,2,-1,3], [1,1,3,-1], [-3,1,3,-1,-1], [-3,1,1,3], [-3,2,3], [1,3,3]]
sage: H = FinitelyGeneratedSubgroup.from_generators(LH, alphabet_type='123')
sage: K = FinitelyGeneratedSubgroup.from_generators(LK, alphabet_type='123')
sage: H.SW_is_free_factor_of(K, complement = True)
(False, '1st argument not contained in 2nd')
::
sage: H.SW_is_free_factor_of(K, complement = False)
False
::
sage: H = FinitelyGeneratedSubgroup.from_generators(['bba','bAbaB'], alphabet_type='abc')
sage: K = FinitelyGeneratedSubgroup.from_generators(['a', 'bb', 'bAbaB'], alphabet_type='abc')
sage: H.SW_is_free_factor_of(K, complement = True, alphabet_type = 'abc')
(True, [word: BB])
::
sage: H.SW_is_free_factor_of(K, complement = False, alphabet_type = 'abc')
True
::
sage: H = FinitelyGeneratedSubgroup.from_generators(['a','B'], alphabet_type='abc')
sage: K = FinitelyGeneratedSubgroup.from_generators(['a','b','d'], alphabet_type='abc')
sage: H.SW_is_free_factor_of(K, complement = True, alphabet_type = 'abc')
(True, [word: d])
::
sage: H.SW_is_free_factor_of(K, complement = False, alphabet_type = 'abc')
True
ALGORITHM:
The algorithm implemented is from [SW2008]_. Be aware that the worst-case complexity
is polynomial in the size of the two argument subgroups, but exponential in the
difference between their ranks.
"""
from stallings_graphs.about_free_factors import SilvaWeil_free_factor_of
if complement:
(valeur,base) = SilvaWeil_free_factor_of(self, other, complement = True)
if alphabet_type == 'abc' and valeur == True:
base = [translate_numeric_Word_to_alphabetic(w) for w in base]
return (valeur,base)
else:
return SilvaWeil_free_factor_of(self, other, complement = False)
[docs] def algebraic_extensions(self):
r"""
Return a dictionary listing the algebraic extensions of ``self``. The keys are integers
without any particular meaning, except key 0 corresponds to ``H`` itself. The entries are
lists of an algebraic extension, sets of keys corresponding to parents and children
of this extension (not a Hasse diagram of the containment relation, but including such
a diagram), and a boolean indicating whether the extension is e-algebraic.
For a definition of algebraic and e-algebraic extensions, see [MVW2007]_.
INPUT:
- ``self`` -- an object of the class ``FinitelyGeneratedSubgroup``.
OUTPUT:
- a dictionary whose keys are integers and whose entries are lists of an object of type
``FinitelyGeneratedSubgroup``, two sets of keys, and a boolean
EXAMPLES::
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: from stallings_graphs.about_free_factors import compute_algebraic_extensions
sage: testgens = ['aba','bab']
sage: testH = FinitelyGeneratedSubgroup.from_generators(testgens,alphabet_type='abc')
sage: testH.algebraic_extensions()
{0: [A subgroup of the free group of rank 2, whose Stallings graph has 5 vertices,
set(),
{1},
True],
1: [A subgroup of the free group of rank 2, whose Stallings graph has 1 vertices,
{0},
set(),
True]}
::
sage: testgens = ['ab','cd']
sage: testH = FinitelyGeneratedSubgroup.from_generators(testgens,alphabet_type='abc')
sage: testH.algebraic_extensions()
{0: [A subgroup of the free group of rank 4, whose Stallings graph has 3 vertices,
set(),
set(),
True]}
::
sage: testgens = ['ABBaaBABa','Baba','Abababba','AbabbABa','ABabAba']
sage: testH = FinitelyGeneratedSubgroup.from_generators(testgens,alphabet_type='abc')
sage: testH.algebraic_extensions()
{0: [A subgroup of the free group of rank 2, whose Stallings graph has 10 vertices,
set(),
{3, 6, 11},
True],
3: [A subgroup of the free group of rank 2, whose Stallings graph has 1 vertices,
{0, 6, 11},
set(),
True],
6: [A subgroup of the free group of rank 2, whose Stallings graph has 3 vertices,
{0, 11},
{3},
True],
11: [A subgroup of the free group of rank 2, whose Stallings graph has 8 vertices,
{0},
{3, 6},
True]}
"""
original_basis = self.basis(alphabet_type='123')
from stallings_graphs.about_free_factors import compute_algebraic_extensions
semilattice_AE = compute_algebraic_extensions(self)
semilattice = {}
for key in semilattice_AE.keys():
newgenerators = original_basis + semilattice_AE[key][2]
newextension = FinitelyGeneratedSubgroup.from_generators(newgenerators, alphabet_type='123')
semilattice[key] = [newextension, semilattice_AE[key][0], semilattice_AE[key][1], semilattice_AE[key][4]]
return semilattice