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
complement
is set toFalse
, returns whether \(H\) (a boolean). Ifcomplement
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\) in \(K\) (in numerical form) if \(H\) is a free factor.H
andK
are expected to be of typeFinitelyGeneratedSubgroup
;complement
is expected to be a Boolean.INPUT:
H
–FinitelyGeneratedSubgroup
K
–FinitelyGeneratedSubgroup
complement
– boolean
OUTPUT:
- a boolean if
complement
is set toFalse
, and a pair consisting of a boolean and either a string or a list ofWords
in 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
complement
is 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\) ifmaxletter
is set to 0, of rankmaxletter
otherwise.H
is expected to be aFinitelyGeneratedSubgroup
;maxletter
is expected to be a non-negative integer, equal to 0 or greater than or equal to the maximal letter occurring inH
;complement
is expected to be a Boolean.INPUT:
H
–FinitelyGeneratedSubgroup
maxletter
– integercomplement
– boolean
OUTPUT:
- a boolean if
complement
is set toFalse
, and a pair consisting of a boolean and either a string or a list ofWords
in 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 toH
itself) 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 ofH
to 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.H
is expected to be aFinitelyGeneratedSubgroup
INPUT:
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 ofWords
and 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]¶ G
is 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}