Ancillary functions about free factors¶
The methods for the class FinitelyGeneratedSubgroup use a number of ancillary functions.
These are the functions which deal with free factors: determining whether a subgroup is a
free factor of the ambient group of another subgroup, deciding primitivity of a word, computing the
lattice of algebraic extensions of a subgroup.
We have the following functions:
SilvaWeil_free_factor_of_ambient: to decide whether a given subgroup is a free factor of the ambient group and, possibly give a basis of its complementSilvaWeil_free_factor_of: to decide whether a given subgroup is a free factor of another and, possibly, give a basis of its complement
The algorithm implemented in SilvaWeil_free_factor_of_ambient and SilvaWeil_free_factor_of
is from [SW2008]. The worst-case complexity
is polynomial in the size of the subgroups considered but exponential in the rank difference
between them.
set_of_possible_additional_generators: an ancillary function to find the additional generators that will lead to the overgroups of a subgroup obtained by identifying two vertices of the Stallings graphcompute_algebraic_extensions: computes the semilattice of algebraic extensions of a subgroup noting those that are elementary algebraic and some of their inclusion relation (sufficiently many to include a Hasse diagram)
The algorithm implemented in compute_algebraic_extensions is from [MVW2007]. It requires
verifying whether certain subgroups are free factors of others. This is done using the Silva Weil algorithm.
EXAMPLES:
sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: from stallings_graphs.about_free_factors import SilvaWeil_free_factor_of_ambient, SilvaWeil_free_factor_of
sage: L1 = ['ac','bacd','ed']
sage: H1 = FinitelyGeneratedSubgroup.from_generators(L1, alphabet_type='abc')
sage: SilvaWeil_free_factor_of_ambient(H1, maxletter = 0, complement = True)
(True, [word: 2,1,-5, word: -2])
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: SilvaWeil_free_factor_of(H, K, complement = True)
(False, 'the 1st argument is not a free factor of the second')
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: SilvaWeil_free_factor_of(H, K, complement = True)
(False, '1st argument not contained in 2nd')
sage: H = FinitelyGeneratedSubgroup.from_generators(['bba','bAbaB'], alphabet_type='abc')
sage: K = FinitelyGeneratedSubgroup.from_generators(['a', 'bb', 'bAbaB'], alphabet_type='abc')
sage: SilvaWeil_free_factor_of(H, K, complement = True)
(True, [word: -2,-2])
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: compute_algebraic_extensions(testH)
{0: [set(),
{1},
[],
{word: -1, word: -1,2, word: 1,-2, word: 11, word: 22},
True,
False],
1: [{0}, set(), [word: -1], set(), True, False]}
AUTHOR:
- Pascal WEIL (2020-05-11): initial version CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr>
-
stallings_graphs.about_free_factors.SilvaWeil_free_factor_of(H, K, complement=True)[source]¶ If
complementis set toFalse, returns whether \(H\) (a boolean). Ifcomplementis set toTrue, returns a pair of a boolean as above, and a string explaining why \(H\) is not a free factor, or a basis for a complement of \(H\) in \(K\) (in numerical form) if \(H\) is a free factor.HandKare expected to be of typeFinitelyGeneratedSubgroup;complementis expected to be a Boolean.INPUT:
H–FinitelyGeneratedSubgroupK–FinitelyGeneratedSubgroupcomplement– boolean
OUTPUT:
- a boolean if
complementis set toFalse, and a pair consisting of a boolean and either a string or a list ofWordsin numerical form otherwise
ALGORITHM:
The algorithm implemented is from [P. Silva, P. Weil. On an algorithm to decide whether a free group is a free factor of another, Theoretical Informatics and Applications 42 (2008) 395-414]. Be aware that the worst-case complexity is polynomial in the size of \(H\) and \(K\) but exponential in the rank difference between \(H\) and \(K\).EXAMPLES:
sage: from stallings_graphs import FinitelyGeneratedSubgroup sage: from stallings_graphs.about_free_factors import SilvaWeil_free_factor_of 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: SilvaWeil_free_factor_of(H, K, complement = True) (True, [word: 3,2,3,1,2,-1, word: 32, word: 3,1,3,-1, word: 11])
sage: SilvaWeil_free_factor_of(H, 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: SilvaWeil_free_factor_of(H, K, complement = True) (False, 'the 1st argument is not a free factor of the second')
sage: SilvaWeil_free_factor_of(H, 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: SilvaWeil_free_factor_of(H, K, complement = True) (False, '1st argument not contained in 2nd')
sage: SilvaWeil_free_factor_of(H, 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: SilvaWeil_free_factor_of(H, K, complement = True) (True, [word: -2,-2])
sage: SilvaWeil_free_factor_of(H, K, complement = False) True
sage: H = FinitelyGeneratedSubgroup.from_generators(['a','B'], alphabet_type='abc') sage: K = FinitelyGeneratedSubgroup.from_generators(['a','b','d'], alphabet_type='abc') sage: SilvaWeil_free_factor_of(H, K, complement = True) (True, [word: 4])
sage: SilvaWeil_free_factor_of(H, K, complement = False) True
-
stallings_graphs.about_free_factors.SilvaWeil_free_factor_of_ambient(H, maxletter=0, complement=True)[source]¶ If
complementis set toFalse, returns whether \(H\) is set toTrue, returns a pair of a boolean as above, and a string explaining why \(H\) is not a free factor, or a basis for a complement of \(H\) if \(H\) is a free factor (in numerical form). In that case, the ambient free group is understood to be of rank the maximal letter occurring in \(H\) ifmaxletteris set to 0, of rankmaxletterotherwise.His expected to be aFinitelyGeneratedSubgroup;maxletteris expected to be a non-negative integer, equal to 0 or greater than or equal to the maximal letter occurring inH;complementis expected to be a Boolean.INPUT:
H–FinitelyGeneratedSubgroupmaxletter– integercomplement– boolean
OUTPUT:
- a boolean if
complementis set toFalse, and a pair consisting of a boolean and either a string or a list ofWordsin numerical form otherwise
ALGORITHM:
The algorithm implemented is from [P. Silva, P. Weil. On an algorithm to decide whether a free group is a free factor of another, Theoretical Informatics and Applications 42 (2008) 395-414]. Be aware that the worst-case complexity is polynomial in the size of \(H\) but exponential in the rank difference between \(H\) and the ambient group.EXAMPLES:
sage: from stallings_graphs import FinitelyGeneratedSubgroup sage: from stallings_graphs.about_free_factors import SilvaWeil_free_factor_of_ambient sage: L1 = ['ac','bacd','ed'] sage: H1 = FinitelyGeneratedSubgroup.from_generators(L1, alphabet_type='abc') sage: SilvaWeil_free_factor_of_ambient(H1, maxletter = 0, complement = True) (True, [word: 2,1,-5, word: -2])
sage: SilvaWeil_free_factor_of_ambient(H1, maxletter = 0, complement = False) True
sage: L2 = ['acac','bacd','ed'] sage: H2 = FinitelyGeneratedSubgroup.from_generators(L2, alphabet_type='abc') sage: SilvaWeil_free_factor_of_ambient(H2, maxletter = 0, complement = True) (False, 'the 1st argument is not a free factor of the second')
sage: SilvaWeil_free_factor_of_ambient(H2, maxletter = 0, complement = False) False
sage: H = FinitelyGeneratedSubgroup.from_generators(['A','d'], alphabet_type='abc') sage: SilvaWeil_free_factor_of_ambient(H, complement = True) (True, [word: 2, word: 3])
sage: SilvaWeil_free_factor_of_ambient(H, complement = False) True
-
stallings_graphs.about_free_factors.compute_algebraic_extensions(H)[source]¶ Returns detailed information on the semilattice of algebraic extensions of the subgroup
H: a dictionary whose keys are integers (without any particular meaning, except key 0 corresponds toHitself) and whose entries are a list of information on algebraic extensions: sets of parents and children (not a Hasse diagram of the containment relation, but including such a diagram), list of generators to be added to those ofHto generate that particular extension, a set of words which help compute the immediate overgroups of this extension, and two boolean flags expressing, respectively, that the extension is e-algebraic and that it is not algebraic.His expected to be aFinitelyGeneratedSubgroupINPUT:
H–FinitelyGeneratedSubgroup
OUTPUT:
- a dictionary whose keys are integers and whose entries are lists of two sets of keys, a list
of
Words, a set ofWordsand two booleans
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: compute_algebraic_extensions(testH) {0: [set(), {1}, [], {word: -1, word: -1,2, word: 1,-2, word: 11, word: 22}, True, False], 1: [{0}, set(), [word: -1], set(), True, False]}
sage: testgens = ['ab','cd'] sage: testH = FinitelyGeneratedSubgroup.from_generators(testgens,alphabet_type='abc') sage: compute_algebraic_extensions(testH) {0: [set(), set(), [], {word: -3, word: -1, word: 1,-3}, True, False]}
sage: testgens = ['ABBaaBABa','Baba','Abababba','AbabbABa','ABabAba'] sage: testH = FinitelyGeneratedSubgroup.from_generators(testgens,alphabet_type='abc') sage: compute_algebraic_extensions(testH) {0: [set(), {3, 6, 11}, [], {word: -2,-1,-2,1, word: -1,-2,-2,1,-2,-1,-2,1, word: -1,-2,-2,1,-2,1, word: -1,-2,-2,1,-1,-2,1, word: -1,-2,-2,1,1, word: -1,-2,1, word: -1,2,2,1, word: 1, word: 2, word: 21, word: 221}, True, False], 3: [{0, 6, 11}, set(), [word: -1,-2,1], set(), True, False], 6: [{0, 11}, {3}, [word: 21], {word: -1}, True, False], 11: [{0}, {3, 6}, [word: -1,-2,-2,1,-2,1], {word: -1,-2,1, word: -1,2, word: 2}, True, False]}
-
stallings_graphs.about_free_factors.set_of_possible_additional_generators(G)[source]¶ Gis expected to be the Stallings graph of a finitely generated subgroup of a free group. The function returns a set of Words of the form \(u_pu_q^{-1}\), where \(u_p\)) is a path from the root vertex 0 to vertex \(p\)).INPUT:
G–DiGraph
OUTPUT:
- a set of objects of type
Word
EXAMPLE:
sage: from stallings_graphs import FinitelyGeneratedSubgroup sage: from stallings_graphs.about_free_factors import set_of_possible_additional_generators sage: testgens = ['aba','bab'] sage: testH = FinitelyGeneratedSubgroup.from_generators(testgens,alphabet_type='abc') sage: testG = testH.stallings_graph() sage: set_of_possible_additional_generators(testG) {word: -1, word: -1,2, word: 1,-2, word: 11, word: 22}