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 a DiGraph (by folding and pruning)
  • random instance
  • ambient_group_rank, to compute the rank of the ambient free group
  • stallings_graph_size
  • rank, to compute the rank of the subgroup
  • stallings_graph, to compute the Stallings graph of the subgroup
  • show_Stallings_graph, to visualize the Stallings graph
  • is_valid, to check the necessary properties of connectedness and trimness
  • eq, to check whether two objects represent the same finitely generated subgroup
  • basis
  • contains_element, to check whether the subgroup contains a given word
  • contains_subgroup, to check whether the subgroup contains a given subgroup
  • intersection
  • has_index, to compute the index of the subgroup
  • conjugated_by, to compute the conjugate of a subgroup by a given word
  • is_conjugated_to, to check whether two subgroups are conjugated and, optionally, compute a conjugating word
  • is_malnormal, to check whether the subgroup is malnormal and, optionally, compute a witness of its non-malnormality
  • is_free_factor_of_ambient, to check whether the subgroup is a free factor of the ambient group and, optionally, to compute a complement
  • is_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-called alphabet_type='abc' ; or \([-r..-1,1..r]\), so-called alphabet_type='123'.

or

  • a labeled DiGraph with vertex set \([0..(n-1)]\) and edge labels in a positive alphabet (\(a\):\(z\) if alphabet_type='abc' or \([1..r]\) if alphabet_type='123'). The DiGraph 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 of other and, if complement is set to True, gives either a statement about it not being a free factor, or if it is, a basis of a complement of self in other (in numerical or in alphabetic form depending on alphabet_type).

other is expected to be a FinitelyGeneratedSubgroup

INPUT:

  • otherFinitelyGeneratedSubgroup
  • complement – boolean
  • alphabet_type – a string which can be either 'abc' or '123'

OUTPUT:

  • a boolean if complement is False, and a pair of a boolean and either a string or a list of objects of type Word 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, if complement is set to True, gives either a statement about it not being a free factor, or if it is, a basis of a complement of self (in numerical or in alphabetic form depending on alphabet_type).

INPUT:

  • complement– boolean
  • alphabet_type – a string which can be either 'abc' or '123'

OUTPUT:

  • a boolean if complement is False and a pair of a boolean and either a string of a list of objects of type Word 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 to H 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 class FinitelyGeneratedSubgroup.

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 – a 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.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 variable alphabet_type determines whether the words in the output are numerical or alphabetic.

INPUT:

  • self – a FinitelyGeneratedSubgroup
  • 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 of alphabet_type. The conjugate of a subgroup \(H\) by a word \(w\) is the subgroup \(w^{-1} H w\).

INPUT:

  • self – a FinitelyGeneratedSubgroup
  • w – a Word
  • alphabet_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 a Word on a numerical alphabet (alphabet_type = '123') or on a letter alphabet (alphabet_type = 'abc').

INPUT:

  • self – a FinitelyGeneratedSubgroup
  • w – a Word
  • 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 class FinitelyGeneratedSubgroup.

INPUT:

  • self – a FinitelyGeneratedSubgroup
  • other – a FinitelyGeneratedSubgroup

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 a DiGraph.

G is expected to be a DiGraph 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:

  • GDiGraph

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 valid Word objects, either numerical or alphabetical, in accordanc with the value of alphabet_type. The FinitelyGeneratedSubgroup 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 the FinitelyGeneratedSubgroup specified by the bouquet.

INPUT:

  • generators – a tuple of Word 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 – a FinitelyGeneratedSubgroup

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:

  • selfFinitelyGeneratedSubgroup
  • otherFinitelyGeneratedSubgroup

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 to True, 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:

  • otherFinitelyGeneratedSubgroup
  • conjugator – boolean
  • alphabet_type – a string which can be either 'abc' or '123'

OUTPUT:

  • a boolean or, if conjugator is True, a tuple consisting of a boolean and a Word or None.

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 if witness is set to True. 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:

  • selfFinitelyGeneratedSubgroup
  • alphabet_type – a string which is either 'abc' or '123'
  • witness – a boolean

OUTPUT:

  • a boolean if witness is set to False; and if witness is set to True, 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 class Word.

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 to True, indications are given if the input is not valid, on the first reason encountered why it is the case. In order: not all elements of partial_injections are actually partial injections; the graph is not connected; some vertex other than 0 has degree less than 2.

INPUT:

  • selfFinitelyGeneratedSubgroup
  • verbose – boolean

OUTPUT:

  • a boolean if verbose is set to False; 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 and ambient_rank is expected to be at least 0 (a ValueError will be raised otherwise). The FinitelyGeneratedSubgroup 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 to True, also prints the number of attempts in the rejection algorithm.

INPUT:

  • size – integer
  • ambient_rank – integer, default value 2
  • verbose – a boolean, default value False

OUTPUT:

  • an object of the class FinitelyGeneratedSubgroup if verbose = False, and a tuple of an object of the class FinitelyGeneratedSubgroup 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 size size and testing whether they define a valid FinitelyGeneratedSubgroup. 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 to edges - vertices + 1, where vertices and edges refer to the number of vertices and edges of the Stallings graph of the corresponding subgroup. In particular vertices is stallings_graph_size and edges is the sum of the domain sizes of the partial injections.

INPUT:

  • selfFinitelyGeneratedSubgroup

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 be graph.plot (with a color coding for the base vertex) or Sébastien Labbé’s TikzPicture method.

INPUT:

  • self – a FinitelyGeneratedSubgroup
  • 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 using TikzPicture, according to the value of visu_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 this FinitelyGeneratedSubgroup.

The Stallings graph of the subgroup of a free group represented by this FinitelyGeneratedSubgroup is an edge-labeled DiGraph. The vertex set is \([0..(n-1)]\), where \(n\) is the size of the input. The base vertex is 0. If \(r\) is the ambient_group_rank of the input, each of the \(r\) partial injections defining the FinitelyGeneratedSubgroup specifies the edges labeled by that particular letter.

INPUT:

  • selfFinitelyGeneratedSubgroup

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:

  • selfFinitelyGeneratedSubgroup

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