About morphisms between free groups: connecting with the train_track package

The methods for the class FinitelyGeneratedSubgroup use a number of ancillary functions. These are the functions which deal with morphisms between free groups.

More precisely, morphisms and automorphisms are handled by Thierry Coulbois’s train_track package. Here we provide mutual translations between objects of class Word, as used in stallings_graphs, and words as used in the train_track package. Specifically, we stick to words on a numerical alphabet (alphabet_type='123') and to the train_track format type='x0'.

The translation is as follows: if \(i\) is a positive integer, the corresponding letter is xj with \(j = i-1\); if \(i\) is a negative integer, the corresponding letter is Xj with \(j = -i-1\).

We have functions to:

  • translate a character, or a word, from one of the formats to the other
  • define a FGendomorphism``(this is a ``FreeGroupMorphism from train_track), by giving the list of images of the ambient free group basis
  • compute the image of a word (alphabetic or numeric) by a FGendomorphism

We inherit the methods from train_track, to compose morphisms, to check whether they are invertible and, if so, to compute their inverse.

EXAMPLES:

sage: from stallings_graphs.about_TC_morphisms import FGendomorphism
sage: L = ['ab','a']
sage: phi = FGendomorphism(L,alphabet_type='abc')
sage: phi
Morphism from Free Group on generators {x0, x1} to Free Group on generators {x0, x1}: x0->x0*x1,x1->x0
sage: from stallings_graphs.about_TC_morphisms import image_of_Word_by_endomorphism
sage: w = 'abAbA'
sage: image_of_Word_by_endomorphism(phi, w, alphabet_type='abc')
word: abaBBA

AUTHOR:

  • Pascal WEIL, CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr> (2019-04-04): initial version.
stallings_graphs.about_TC_morphisms.FGendomorphism(L, alphabet_type='abc')[source]

Return a FreeGroupMorphism in the sense of the train_track package, defined by the given list.

L is expected to be a list of objects of class Word, on a numerical or letter alphabet according to the value of alphabet_type.

INPUT:

  • L – list of objects of class Word
  • alphabet_type – string, which is either '123' or 'abc'

OUTPUT:

  • FreeGroupMorphism

EXAMPLES:

sage: from stallings_graphs.about_TC_morphisms import FGendomorphism
sage: L = ['ab','a']
sage: phi = FGendomorphism(L,alphabet_type='abc')
sage: phi
Morphism from Free Group on generators {x0, x1} to Free Group on generators {x0, x1}: x0->x0*x1,x1->x0
stallings_graphs.about_TC_morphisms.image_of_Word_by_endomorphism(phi, w, alphabet_type='abc')[source]

Return the image of the second argument by the first.

INPUT:

  • phiFreeGroupMorphism
  • w – a Word on a numeric or letter alphabet, depending on the value of alphabet_type
  • alphabet_type – string, which is either '123' or 'abc'

OUTPUT:

  • Word

EXAMPLES:

sage: from stallings_graphs.about_TC_morphisms import image_of_Word_by_endomorphism 
sage: from stallings_graphs.about_TC_morphisms import FGendomorphism
sage: L = ['ab','a']
sage: phi = FGendomorphism(L,alphabet_type='abc')
sage: w = 'abAbA'
sage: image_of_Word_by_endomorphism(phi, w, alphabet_type='abc')
word: abaBBA
stallings_graphs.about_TC_morphisms.translate_numeric_Word_to_x0_list(w)[source]

Return the corresponding word in Thierry Coulbois’s x0 format.

w is expected to be a Word on a numerical alphabet.

INPUT:

  • w – Word

OUTPUT:

  • list

EXAMPLES:

sage: from stallings_graphs.about_TC_morphisms import translate_numeric_Word_to_x0_list
sage: translate_numeric_Word_to_x0_list([7,1,-2,3,-3])
['x6', 'x0', 'X1', 'x2', 'X2']
stallings_graphs.about_TC_morphisms.translate_numeric_to_x0_character(i)[source]

Return the corresponding character in Thierry Coulbois’s x0 format.

i is expected to be a non-zero integer. An exception is raised if that is not the case.

INPUT:

  • i – integer

OUTPUT:

  • string

EXAMPLES:

sage: from stallings_graphs.about_TC_morphisms import translate_numeric_to_x0_character
sage: translate_numeric_to_x0_character(7)
'x6'
sage: translate_numeric_to_x0_character(-7)
'X6'
stallings_graphs.about_TC_morphisms.translate_x0_character_to_numeric(letter)[source]

Return the corresponding numeric.

letter is expected to be a string of the form xj or Xj, where j is a non-negative integer in decimal expansion.

INPUT:

  • letter – string

OUTPUT:

  • integer

EXAMPLES:

sage: from stallings_graphs.about_TC_morphisms import translate_x0_character_to_numeric
sage: translate_x0_character_to_numeric('x100')
101
sage: translate_x0_character_to_numeric('X100')
-101
stallings_graphs.about_TC_morphisms.translate_x0_word_to_numeric_Word(u)[source]

Return the corresponding numeric Word.

u is expected to be a FreeGroup element in the sense of the train_track package, written with letters of the form xj or Xj, where j is a non-negative integer in decimal expansion.

INPUT:

  • u – element of type train_track.free_group.FreeGroup_class_with_category.element_class (the free group elements in the train_track package)

OUTPUT:

  • Word

EXAMPLES:

sage: from train_track import FreeGroupMorphism
sage: D = {'x0':['x0','x1'],'x1':['X0']}
sage: phi = FreeGroupMorphism(D)
sage: print(phi)
x0->x0*x1,x1->x0^-1
sage: w = phi(['X0','x1','x0'])
sage: from stallings_graphs.about_TC_morphisms import translate_x0_word_to_numeric_Word
sage: translate_x0_word_to_numeric_Word(w)
word: -2,-1,2
sage: w = phi([])
sage: translate_x0_word_to_numeric_Word(w)
word: