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
FinitelyGeneratedSubgroupfrom a list of generators (Words) - definition of a
FinitelyGeneratedSubgroupfrom aDiGraph(by folding and pruning) - random instance
ambient_group_rank, to compute the rank of the ambient free groupstallings_graph_sizerank, 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 subgroupbasiscontains_element, to check whether the subgroup contains a given wordcontains_subgroup, to check whether the subgroup contains a given subgroupintersectionhas_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.SageObjectDefine 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
FinitelyGeneratedSubgroupcan be created from:- a list of objects of the class
PartialInjection, all of the same size;
or
- a list of
Wordson 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
DiGraphwith vertex set \([0..(n-1)]\) and edge labels in a positive alphabet (\(a\):\(z\) ifalphabet_type='abc'or \([1..r]\) ifalphabet_type='123'). TheDiGraphis 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
selfis a free factor ofotherand, ifcomplementis set toTrue, gives either a statement about it not being a free factor, or if it is, a basis of a complement ofselfinother(in numerical or in alphabetic form depending onalphabet_type).otheris expected to be aFinitelyGeneratedSubgroupINPUT:
other–FinitelyGeneratedSubgroupcomplement– booleanalphabet_type– a string which can be either'abc'or'123'
OUTPUT:
- a boolean if
complementisFalse, and a pair of a boolean and either a string or a list of objects of typeWordotherwise
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
selfis a free factor of the ambient group and, ifcomplementis 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
complementisFalseand a pair of a boolean and either a string of a list of objects of typeWordotherwise
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 toHitself. 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
FinitelyGeneratedSubgroupobject.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_typedetermines whether the words in the output are numerical or alphabetic.INPUT:
self– aFinitelyGeneratedSubgroupalphabet_type– a string, which is either'abc'or'123'
OUTPUT: A list of objects of the class
WordEXAMPLES:
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.
wis 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– aFinitelyGeneratedSubgroupw– 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\).
wis expected to be aWordon a numerical alphabet (alphabet_type = '123') or on a letter alphabet (alphabet_type = 'abc').INPUT:
self– aFinitelyGeneratedSubgroupw– aWordalphabet_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.
otheris expected to be an object of classFinitelyGeneratedSubgroup.INPUT:
self– aFinitelyGeneratedSubgroupother– 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
FinitelyGeneratedSubgroupspecified by aDiGraph.Gis expected to be aDiGraphwith 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
FinitelyGeneratedSubgroupspecified by a set of generators.generatorsis expected to be a list of validWordobjects, either numerical or alphabetical, in accordanc with the value ofalphabet_type. TheFinitelyGeneratedSubgroupproduced 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 theFinitelyGeneratedSubgroupspecified by the bouquet.INPUT:
generators– a tuple ofWordobjects
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:
generatorscan be an empty list.
-
has_index()[source]¶ Return the index of this subgroup if it is finite,
+Infinityotherwise.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–FinitelyGeneratedSubgroupother–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
conjugatoris set toTrue, the output will also include a conjugator (Noneif the two subgroups are not conjugated). A word \(w\) is a conjugator of \(H\) into \(K\) if \(w^{-1} H w = K\).INPUT:
other–FinitelyGeneratedSubgroupconjugator– booleanalphabet_type– a string which can be either'abc'or'123'
OUTPUT:
- a boolean or, if
conjugatorisTrue, a tuple consisting of a boolean and aWordorNone.
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 ifwitnessis 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–FinitelyGeneratedSubgroupalphabet_type– a string which is either'abc'or'123'witness– a boolean
OUTPUT:
- a boolean if
witnessis set toFalse; and ifwitnessis 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
FinitelyGeneratedSubgroupinput really defines a subgroup.If
verboseis 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_injectionsare actually partial injections; the graph is not connected; some vertex other than 0 has degree less than 2.INPUT:
self–FinitelyGeneratedSubgroupverbose– boolean
OUTPUT:
- a boolean if
verboseis 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.sizeis expected to be at least 1 andambient_rankis expected to be at least 0 (aValueErrorwill be raised otherwise). TheFinitelyGeneratedSubgroupis picked uniformly at random among those of the given size and with the same ambient free group rank.If the option
verboseis 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
FinitelyGeneratedSubgroupifverbose = False, and a tuple of an object of the classFinitelyGeneratedSubgroupand 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_rankpartial injections, each of sizesizeand 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
FinitelyGeneratedSubgroupis equal toedges-vertices+ 1, whereverticesandedgesrefer to the number of vertices and edges of the Stallings graph of the corresponding subgroup. In particularverticesisstallings_graph_sizeandedgesis 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é’sTikzPicturemethod.INPUT:
self– aFinitelyGeneratedSubgroupalphabet_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.plotor usingTikzPicture, according to the value ofvisu_tool. In the'tikz'case, the output can be saved as a.png,.pdfor.texfile
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
DiGraphof thisFinitelyGeneratedSubgroup.The Stallings graph of the subgroup of a free group represented by this
FinitelyGeneratedSubgroupis an edge-labeledDiGraph. The vertex set is \([0..(n-1)]\), where \(n\) is thesizeof the input. The base vertex is 0. If \(r\) is theambient_group_rankof the input, each of the \(r\) partial injections defining theFinitelyGeneratedSubgroupspecifies 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
FinitelyGeneratedSubgroupis 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