The class FinitelyGeneratedSubgroup
¶
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 aDiGraph
(by folding and pruning) - random instance
ambient_group_rank
, to compute the rank of the ambient free groupstallings_graph_size
rank
, to compute the rank of the subgroupstallings_graph
, to compute the Stallings graph of the subgroupshow_Stallings_graph
, to visualize the Stallings graphis_valid
, to check the necessary properties of connectedness and trimnesseq
, to check whether two objects represent the same finitely generated subgroupbasis
contains_element
, to check whether the subgroup contains a given wordcontains_subgroup
, to check whether the subgroup contains a given subgroupintersection
has_index
, to compute the index of the subgroupconjugated_by
, to compute the conjugate of a subgroup by a given wordis_conjugated_to
, to check whether two subgroups are conjugated and, optionally, compute a conjugating wordis_malnormal
, to check whether the subgroup is malnormal and, optionally, compute a witness of its non-malnormalityis_free_factor_of_ambient
, to check whether the subgroup is a free factor of the ambient group and, optionally, to compute a complementis_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>
-
class
stallings_graphs.finitely_generated_subgroup.
FinitelyGeneratedSubgroup
(partial_injections)[source]¶ Bases:
sage.structure.sage_object.SageObject
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-calledalphabet_type='abc'
; or \([-r..-1,1..r]\), so-calledalphabet_type='123'
.
or
- a labeled
DiGraph
with vertex set \([0..(n-1)]\) and edge labels in a positive alphabet (\(a\):\(z\) ifalphabet_type='abc'
or \([1..r]\) ifalphabet_type='123'
). TheDiGraph
is considered to be rooted at vertex 0.
or
- a random instance.
-
SW_is_free_factor_of
(other, complement=True, alphabet_type='123')[source]¶ Return whether
self
is a free factor ofother
and, ifcomplement
is set toTrue
, gives either a statement about it not being a free factor, or if it is, a basis of a complement ofself
inother
(in numerical or in alphabetic form depending onalphabet_type
).other
is expected to be aFinitelyGeneratedSubgroup
INPUT:
other
–FinitelyGeneratedSubgroup
complement
– booleanalphabet_type
– a string which can be either'abc'
or'123'
OUTPUT:
- a boolean if
complement
isFalse
, and a pair of a boolean and either a string or a list of objects of typeWord
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.
-
SW_is_free_factor_of_ambient
(complement=True, alphabet_type='123')[source]¶ Return whether
self
is a free factor of the ambient group and, ifcomplement
is set toTrue
, gives either a statement about it not being a free factor, or if it is, a basis of a complement ofself
(in numerical or in alphabetic form depending onalphabet_type
).INPUT:
complement
– booleanalphabet_type
– a string which can be either'abc'
or'123'
OUTPUT:
- a boolean if
complement
isFalse
and a pair of a boolean and either a string of a list of objects of typeWord
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.
-
algebraic_extensions
()[source]¶ Return a dictionary listing the algebraic extensions of
self
. The keys are integers without any particular meaning, except key 0 corresponds toH
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 classFinitelyGeneratedSubgroup
.
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]}
-
ambient_group_rank
()[source]¶ 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
– aFinitelyGeneratedSubgroup
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
-
basis
(alphabet_type='abc')[source]¶ Return a basis of this subgroup.
The input is expected to be an object of the class
FinitelyGeneratedSubgroup
. The variablealphabet_type
determines whether the words in the output are numerical or alphabetic.INPUT:
self
– aFinitelyGeneratedSubgroup
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]
-
conjugated_by
(w, alphabet_type='123')[source]¶ 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 ofalphabet_type
. The conjugate of a subgroup \(H\) by a word \(w\) is the subgroup \(w^{-1} H w\).INPUT:
self
– aFinitelyGeneratedSubgroup
w
– a Wordalphabet_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
-
contains_element
(w, alphabet_type='123')[source]¶ Return whether the subgroup contains the word \(w\).
w
is expected to be aWord
on a numerical alphabet (alphabet_type = '123'
) or on a letter alphabet (alphabet_type = 'abc'
).INPUT:
self
– aFinitelyGeneratedSubgroup
w
– aWord
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
-
contains_subgroup
(other)[source]¶ Return whether the subgroup contains another subgroup.
other
is expected to be an object of classFinitelyGeneratedSubgroup
.INPUT:
self
– aFinitelyGeneratedSubgroup
other
– aFinitelyGeneratedSubgroup
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
-
static
from_digraph
(G)[source]¶ Return the
FinitelyGeneratedSubgroup
specified by aDiGraph
.G
is expected to be aDiGraph
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.
-
static
from_generators
(generators, alphabet_type='123')[source]¶ Return the
FinitelyGeneratedSubgroup
specified by a set of generators.generators
is expected to be a list of validWord
objects, either numerical or alphabetical, in accordanc with the value ofalphabet_type
. TheFinitelyGeneratedSubgroup
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 theFinitelyGeneratedSubgroup
specified by the bouquet.INPUT:
generators
– a tuple ofWord
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.
-
has_index
()[source]¶ Return the index of this subgroup if it is finite,
+Infinity
otherwise.INPUT:
self
– aFinitelyGeneratedSubgroup
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
-
intersection
(K)[source]¶ 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]
-
is_conjugated_to
(other, conjugator=False, alphabet_type='123')[source]¶ Return whether self and other are conjugated.
If
conjugator
is set toTrue
, 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
– booleanalphabet_type
– a string which can be either'abc'
or'123'
OUTPUT:
- a boolean or, if
conjugator
isTrue
, a tuple consisting of a boolean and aWord
orNone
.
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
-
is_malnormal
(alphabet_type='123', witness=False)[source]¶ 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 ifwitness
is set toTrue
. 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 toFalse
; and ifwitness
is set toTrue
, 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 classWord
.
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.
-
is_valid
(verbose=False)[source]¶ Return whether this
FinitelyGeneratedSubgroup
input really defines a subgroup.If
verbose
is set toTrue
, indications are given if the input is not valid, on the first reason encountered why it is the case. In order: not all elements ofpartial_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 toFalse
; 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.
-
static
random_instance
(size, ambient_rank=2, verbose=False)[source]¶ Return a randomly chosen
FinitelyGeneratedSubgroup
.size
is expected to be at least 1 andambient_rank
is expected to be at least 0 (aValueError
will be raised otherwise). TheFinitelyGeneratedSubgroup
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 toTrue
, also prints the number of attempts in the rejection algorithm.INPUT:
size
– integerambient_rank
– integer, default value 2verbose
– a boolean, default value False
OUTPUT:
- an object of the class
FinitelyGeneratedSubgroup
ifverbose = False
, and a tuple of an object of the classFinitelyGeneratedSubgroup
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 sizesize
and testing whether they define a validFinitelyGeneratedSubgroup
. If they do not, the tuple is tossed and another is drawn.For a justification, see [BNW2008].
-
rank
()[source]¶ Return the rank of this
FinitelyGeneratedSubgroup
.The rank of this
FinitelyGeneratedSubgroup
is equal toedges
-vertices
+ 1, wherevertices
andedges
refer to the number of vertices and edges of the Stallings graph of the corresponding subgroup. In particularvertices
isstallings_graph_size
andedges
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
-
show_Stallings_graph
(alphabet_type='abc', visu_tool='plot')[source]¶ 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 begraph.plot
(with a color coding for the base vertex) or Sébastien Labbé’sTikzPicture
method.INPUT:
self
– aFinitelyGeneratedSubgroup
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 usingTikzPicture
, according to the value ofvisu_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
-
stallings_graph
()[source]¶ Return the Stallings
DiGraph
of thisFinitelyGeneratedSubgroup
.The Stallings graph of the subgroup of a free group represented by this
FinitelyGeneratedSubgroup
is an edge-labeledDiGraph
. The vertex set is \([0..(n-1)]\), where \(n\) is thesize
of the input. The base vertex is 0. If \(r\) is theambient_group_rank
of the input, each of the \(r\) partial injections defining theFinitelyGeneratedSubgroup
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
-
stallings_graph_size
()[source]¶ 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
- a list of objects of the class