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 complement
  • SilvaWeil_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 graph
  • compute_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:

stallings_graphs.about_free_factors.SilvaWeil_free_factor_of(H, K, complement=True)[source]

If complement is set to False, returns whether \(H\) (a boolean). If complement is set to True, 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 and K are expected to be of type FinitelyGeneratedSubgroup; complement is expected to be a Boolean.

INPUT:

  • HFinitelyGeneratedSubgroup
  • KFinitelyGeneratedSubgroup
  • complement – boolean

OUTPUT:

  • a boolean if complement is set to False, and a pair consisting of a boolean and either a string or a list of Words 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 to False, returns whether \(H\) is set to True, 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\) if maxletter is set to 0, of rank maxletter otherwise.

H is expected to be a FinitelyGeneratedSubgroup; maxletter is expected to be a non-negative integer, equal to 0 or greater than or equal to the maximal letter occurring in H; complement is expected to be a Boolean.

INPUT:

  • HFinitelyGeneratedSubgroup
  • maxletter – integer
  • complement – boolean

OUTPUT:

  • a boolean if complement is set to False, and a pair consisting of a boolean and either a string or a list of Words 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 to H 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 of H 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 a FinitelyGeneratedSubgroup

INPUT:

  • HFinitelyGeneratedSubgroup

OUTPUT:

  • a dictionary whose keys are integers and whose entries are lists of two sets of keys, a list of Words, a set of Words 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:

  • GDiGraph

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}