Source code for stallings_graphs.about_words

# -*- coding: utf-8 -*-
r"""
The methods for the class ``FinitelyGeneratedSubgroup`` use a number of ancillary functions. These are the functions which deal with words (actually, objects of class ``Word``) in the context of group theory.

A word is a string of characters from either a numerical or an alphabetical set
of letters: ``alphabet_type='123'`` or ``'abc'``

``alphabet_type='123'``: The positive letters form an interval `[1,r]`. Their inverses (a.k.a.
negative letters) are the corresponding negative integers. The symmetrized
alphabet is the union of positive and negative letters (zero is NOT a letter).
The `\textit{rank}` of a word is the maximal absolute value of a letter occurring in the word.
When represented in a (say LaTeX) file (``.tex``, ``.pdf``), the letters are written
`a_i`.

``alphabet_type='abc'``: positive letters are lower case (at most 26 letters, `a`:`z`)
and their inverses are the corresponding upper case letters (`A`:`Z`).

We have functions to:

- translate a word or a list of words from one ``alphabet_type`` to the other

- test whether a word of ``alphabet_type '123'`` is (freely) reduced or cyclically reduced

- freely reduce a word of ``alphabet_type '123'``

- computes the cyclic reduction of a word of ``alphabet_type '123'``

- produce a random word of ``alphabet_type '123'`` of given length on an alphabet of given rank (given a positive integer `r`).

EXAMPLES::

    sage: from stallings_graphs.about_words import group_inverse
    sage: w = Word('aBabbaBA')
    sage: group_inverse(w,alphabet_type='abc')
    word: abABBAbA
    
::
    
    sage: from stallings_graphs.about_words import free_group_reduction
    sage: w = Word([3,1,-2,-2,2,1,-1,2,5,-3])
    sage: free_group_reduction(w)
    word: 3,1,5,-3
    
::

    sage: from stallings_graphs.about_words import random_reduced_word
    sage: w = random_reduced_word(7,3)   #random
    Word([2,-1,3,-1,-1,2,-3])


AUTHOR:

- Pascal WEIL, CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr> (2018-06-09): initial version.

"""

from sage.misc.prandom import randint
from sage.combinat.words.word import Word
#from sage.graphs.digraph import DiGraph
#from sage.sets.disjoint_set import DisjointSet
#from sage.misc.latex import LatexExpr
#
#from partial_injections import PartialInjection



[docs]def positive_letters(r): r""" Return the list of positive (numerical) letters up to `r`. `r` is expected to be positive. INPUT: - ``r`` -- integer OUTPUT: - list EXAMPLES:: sage: from stallings_graphs.about_words import positive_letters sage: positive_letters(6) [1, 2, 3, 4, 5, 6] """ return list(range(1,r + 1))
[docs]def negative_letters(r): r""" Return the set of negative (numerical) letters up to `-r`. `r` is expected to be positive. INPUT: - ``r`` -- integer OUTPUT: - the list of integers from `-1` to `-r` EXAMPLES:: sage: from stallings_graphs.about_words import negative_letters sage: negative_letters(6) [-1, -2, -3, -4, -5, -6] """ return list(range(-1,-r-1,-1))
[docs]def symmetric_alphabet(r): r""" Return the full symmetric (numerical) alphabet. `r` is expected to be positive. INPUT: - ``r`` -- integer OUTPUT: - the list of integers from `1` to `r` and from `-1` to `-r` EXAMPLES:: sage: from stallings_graphs.about_words import symmetric_alphabet sage: symmetric_alphabet(6) [1, 2, 3, 4, 5, 6, -1, -2, -3, -4, -5, -6] """ L = positive_letters(r) L.extend(negative_letters(r)) return L
[docs]def inverse_letter(i): r""" Return the inverse of this (numerical) letter. `i` is expected to be a non-zero integer. INPUT: - ``i`` -- integer OUTPUT: - integer EXAMPLES:: sage: from stallings_graphs.about_words import inverse_letter sage: inverse_letter(3) -3 :: sage: inverse_letter(-4) 4 """ return -i
[docs]def positive_value(i): r""" Return the positive value of a (numerical) letter. `i` is expected to be a non-zero integer. INPUT: - ``i`` -- integer OUTPUT: - integer EXAMPLES:: sage: from stallings_graphs.about_words import positive_value sage: positive_value(3) 3 sage: positive_value(-4) 4 """ if i < 0: return inverse_letter(i) else: return i
[docs]def translate_character_to_numeric(x): r""" Return the numeric equivalent of a character in `a`:`z` or `A`:`Z`. `x` is expected to be a character in `a`:`z` or `A`:`Z`. The numeric equivalent is 1-26 for `a`:`z` and the opposite for `A`:`Z`. INPUT: - ``x`` -- character OUTPUT: - integer EXAMPLES:: sage: from stallings_graphs.about_words import translate_character_to_numeric sage: translate_character_to_numeric('b') 2 sage: translate_character_to_numeric('D') -4 """ if ord(x) in range(65,91): return -(ord(x) - 64) elif ord(x) in range(97,123): return ord(x) - 96 else: raise ValueError('the argument must be a letter in a:z or A:Z')
[docs]def translate_numeric_to_character(x): r""" Return the character equivalent of a numerical letter. `x` is expected to be a non-zero integer in the interval `[-26;26]`. A ValueError is raised otherwise. The numeric equivalent is a lower case character if `x > 0` and an upper case character otherwise. INPUT: - ``x`` -- integer OUTPUT: - character EXAMPLES:: sage: from stallings_graphs.about_words import translate_numeric_to_character sage: translate_numeric_to_character(16) 'p' :: sage: translate_numeric_to_character(-10) 'J' """ if x in list(range(-26,0)): return chr(- x + 64) elif x in list(range(1,27)): return chr(x + 96) else: raise ValueError('the argument must be a non-zero integer between -26 and 26')
[docs]def alphabetic_inverse(x): r""" Return the inverse of an alphabetic letter. `x` is expected to be a character in `a`:`z` or `A`:`Z`. Taking the inverse toggles between upper and lower case letters. INPUT: - ``x`` -- character OUTPUT: - character EXAMPLES:: sage: from stallings_graphs.about_words import alphabetic_inverse sage: alphabetic_inverse('b') 'B' sage: alphabetic_inverse('D') 'd' """ return translate_numeric_to_character(-translate_character_to_numeric(x))
### Words and lists of Words ###
[docs]def translate_alphabetic_Word_to_numeric(w): r""" Return the numerical equivalent of a ``Word`` of ``alphabet_type = 'abc'``. `w` is expected to be a ``Word`` on alphabet `a`:`z` `+` `A`:`Z`. The output is a ``Word`` on alphabet `\{\pm 1, ..., \pm 26\}`. INPUT: - ``w`` -- ``Word`` OUTPUT: - ``Word`` EXAMPLES:: sage: from stallings_graphs.about_words import translate_alphabetic_Word_to_numeric sage: translate_alphabetic_Word_to_numeric(Word('aBBaAc')) word: 1,-2,-2,1,-1,3 :: sage: translate_alphabetic_Word_to_numeric(Word('')) word: :: sage: translate_alphabetic_Word_to_numeric(Word([])) word: """ if len(w) == 0: return Word([]) u = [translate_character_to_numeric(x) for x in w] return Word(u)
[docs]def translate_numeric_Word_to_alphabetic(w): r""" Return the alphabetic equivalent of a numeric word. `w` is expected to be a ``Word`` on a numerical alphabet `\{\pm 1, \dots, \pm 26\}`. The output is a ``Word`` on alphabet `a`:`z` `+` `A`:`Z`. INPUT: - ``w`` -- ``Word`` OUTPUT: - ``Word`` EXAMPLES:: sage: from stallings_graphs.about_words import translate_numeric_Word_to_alphabetic sage: translate_numeric_Word_to_alphabetic(Word([2,-1,-2,3,1,3])) word: bABcac """ if len(w) == 0: return Word([]) u = [translate_numeric_to_character(x) for x in w] return Word(u)
[docs]def is_valid_Word(w, alphabet_type='123'): r""" Return whether a ``Word`` is valid, in the sense of having a consistent alphabet. `w` is expected to be a ``Word``. It is `\textit{valid}` if all its letters are non-zero integers if ``alphabet_type='123'``; or are in `a`:`z` `+` `A`:`Z` if ``alphabet_type='abc'``. INPUT: - ``w`` -- ``Word`` - ``alphabet_type`` -- string, which must be either ``'abc'`` or ``'123'`` OUTPUT: - boolean EXAMPLES:: sage: from stallings_graphs.about_words import is_valid_Word sage: w = Word([2,-1,-2,3,1,3]) sage: is_valid_Word(w) True :: sage: is_valid_Word(Word('bABcac'), alphabet_type='abc') True :: sage: is_valid_Word(Word([2,-1,-2,0,1,3])) False """ from sage.rings.integer_ring import ZZ if (alphabet_type != '123') and (alphabet_type != 'abc'): raise ValueError('the second argument is neither "123" nor "abc".') if len(w) == 0: return True if alphabet_type == '123': return all((x in ZZ and x != 0) for x in w) L = list(range(65,91)) + list(range(97,123)) return all(isinstance(x,str) for x in w) and all(ord(x) in L for x in w)
[docs]def is_valid_list_of_Words(L,alphabet_type='123'): r""" Return whether a list of ``Words`` is valid, in the sense of ``is_valid_Word``. `L` is expected to be a list of objects of class ``Word``. It is valid if all its components satisfy ``is_valid_Word``. INPUT: - ``L`` -- ``List`` of objects of the class ``Word`` - ``alphabet_type`` -- string, which must be either ``'abc'`` or ``'123'`` OUTPUT: - boolean EXAMPLES:: sage: from stallings_graphs.about_words import is_valid_list_of_Words sage: L = [Word([2,-1,-2,3,1,3]), Word([1,2,-3,1,-1])] sage: is_valid_list_of_Words(L) True :: sage: L = [Word('bABcac'),'abcBA','baaCB'] sage: is_valid_list_of_Words(L, alphabet_type='abc') True """ if (alphabet_type != '123') and (alphabet_type != 'abc'): raise ValueError('the second argument is neither "123" nor "abc".') return all(is_valid_Word(w, alphabet_type) for w in L)
[docs]def positive_alphabetic_content(w,check=False): r""" Return the set of positive letters which occur, or their inverse occurs in `w`. `w` is expected to be a ``Word`` on a numerical alphabet. If ``check`` is ``True``, ``is_valid_Word(w,alphabet_type='123')`` is run. INPUT: - ``w`` -- ``Word`` - ``check`` -- Boolean OUTPUT: - list of positive integers EXAMPLES:: sage: from stallings_graphs.about_words import positive_alphabetic_content sage: w = Word([3,1,-2,-2,5,-3]) sage: positive_alphabetic_content(w) {1, 2, 3, 5} :: sage: w = Word([]) sage: positive_alphabetic_content(w) set() """ if check == True: if not(is_valid_Word(w,alphabet_type='123')): raise ValueError('the argument is not a valid (numerical) Word: probably contains 0, which is not a letter, or is of type "abc".') return set(positive_value(x) for x in w.letters())
[docs]def rank(w,check=False): r""" Return the least rank of a free group containing this ``Word``. `w` is expected to be a ``Word`` on a numerical alphabet. The least rank of a free group containing `w` is the max of the positive values of its letters. If ``check`` is ``True``, ``is_valid_Word(w,alphabet_type='123')`` is run. INPUT: - ``w`` -- ``Word`` - ``check`` -- boolean OUTPUT: - integer EXAMPLES:: sage: from stallings_graphs.about_words import rank sage: w = Word([3,1,-2,-2,5,-3]) sage: rank(w) 5 :: sage: w = Word([]) sage: rank(w) 0 """ if check == True: if not(is_valid_Word(w,alphabet_type='123')): raise ValueError('the argument is not a valid (numerical) Word: probably contains 0, which is not a letter, or is of type "abc".') if len(w) == 0: return 0 else: return max(positive_alphabetic_content(w))
############################################## ## group properties: inverting, reducing, etc. ##############################################
[docs]def group_inverse(w,alphabet_type='123',check=False): r""" Return the (free group) inverse of a word. `w` is expected to be a ``Word`` on a numerical or letter alphabet, depending on the value of ``alphabet_type``. Its inverse is obtained in reading `w` in reverse order and replacing each letter by its inverse. If ``check`` is set to ``True``, ``is_valid_Word`` is run on `w`. INPUT: - ``w`` -- ``Word`` - ``alphabet_type`` -- string, which must be either ``'abc'`` or ``'123'`` OUTPUT: - ``Word`` EXAMPLES :: sage: from stallings_graphs.about_words import group_inverse sage: w = Word([3,1,-9,-2,5]) sage: group_inverse(w) word: -5,2,9,-1,-3 :: sage: w = Word([-1,1,2,-2]) sage: group_inverse(w) word: 2,-2,-1,1 :: sage: w = Word([1]) sage: group_inverse(w) word: -1 :: sage: w = Word() sage: group_inverse(w) word: """ if check == True: if not(is_valid_Word(w,alphabet_type)): raise ValueError('the first argument is not a valid Word of the given alphabet_type') if alphabet_type == 'abc': w1 = translate_alphabetic_Word_to_numeric(w) else: w1 = w v = [inverse_letter(x) for x in w1] v.reverse() v1 = Word(v) if alphabet_type == 'abc': v1 = translate_numeric_Word_to_alphabetic(v1) return v1
[docs]def is_reduced(w,check=False): r""" Return whether this word is a reduced. `w` is expected to be a ``Word`` on a numerical alphabet. A word `w` is reduced (in the group-theoretic sense) if it does not contain consecutive letters which are mutually inverse. The option ``check`` verifies whether `w` is a valid Word. INPUT: - ``w`` -- ``Word`` - ``check`` -- boolean OUTPUT: - boolean EXAMPLES :: sage: from stallings_graphs.about_words import is_reduced sage: w = Word([3,1,-2,-2,5,-3]) sage: is_reduced(w) True :: sage: u = Word([3,1,-2,2,5,-3]) sage: is_reduced(u) False """ if check == True: if not(is_valid_Word(w,alphabet_type='123')): raise ValueError('the argument is not a valid (numerical) Word: probably contains 0, which is not a letter') if len(w) < 2: return True else: return all(inverse_letter(w[i]) != w[i+1] for i in range(len(w) - 1))
[docs]def free_group_reduction(w,check=False): r""" Return the reduced word that is equivalent to this word. `w` is expected to be a ``Word`` on a numerical alphabet. The option ``check = True`` verifies that this is the case. The reduced word equivalent to a word `w` is obtained from `w` by repeatedly deleting pairs of consecutive letters which are mutually inverse. INPUT: - ``w`` -- ``Word`` - ``check`` -- boolean OUTPUT: - ``Word`` EXAMPLES :: sage: from stallings_graphs.about_words import free_group_reduction sage: w = Word([3,1,-2,-2,2,1,-1,2,5,-3]) sage: free_group_reduction(w) word: 3,1,5,-3 ALGORITHM: This method implements the classical algorithm, based on the usage of a pushdown automaton. """ if check == True: if not(is_valid_Word(w,alphabet_type='123')): raise ValueError('the argument is not a valid (numerical) Word: probably contains 0, which is not a letter') if len(w) < 2: return w else: stack = [] for i in range(len(w)): if stack == []: stack.append(w[i]) elif stack[-1] != inverse_letter(w[i]): stack.append(w[i]) else: stack = stack[:-1] return Word(stack)
[docs]def is_cyclically_reduced(w,check=False): r""" Return whether this word is cyclically reduced. `w` is expected to be a ``Word`` on a numerical alphabet. The option ``check`` verifies that it is the case. A word is cyclically reduced if it is reduced and its first and last letters are not mutually inverse. INPUT: - ``w`` -- ``Word`` - ``check`` -- boolean OUTPUT: - boolean EXAMPLES :: sage: from stallings_graphs.about_words import is_cyclically_reduced sage: w = Word([3,1,-2,-2,5,-3]) sage: is_cyclically_reduced(w) False :: sage: u = Word([3,1,-2,-2,5,3]) sage: is_cyclically_reduced(u) True """ if check == True: if not(is_valid_Word(w,alphabet_type='123')): raise ValueError('the argument is not a valid (numerical) Word. Common mistake: it contains 0, which is not a letter') if len(w) < 2: return True else: return is_reduced(w) and inverse_letter(w[0]) != w[-1]
[docs]def cyclic_reduction_of_a_word(u): r""" Return the elements of the cyclically reduced decomposition of this word. `u` is expected to be a ``Word`` on a numerical alphabet. The cyclically reduced decomposition of `u` is the pair of ``Words`` `(v,w)` such that `v` is cyclically reduced, and `u = w^{-1}vw`. INPUT: - ``w`` -- ``Word`` - ``check`` -- boolean OUTPUT: - pair of objects of class ``Word`` EXAMPLES :: sage: from stallings_graphs.about_words import cyclic_reduction_of_a_word sage: u = Word([1,-2,-2,-1,1]) sage: cyclic_reduction_of_a_word(u) (word: 1,-2,-2, word: ) :: sage: u = Word([1,-2,1,-2,1,2,-1]) sage: cyclic_reduction_of_a_word(u) (word: 1,-2,1, word: 2,-1) :: sage: u = Word([1,-2,1,-1,1]) sage: cyclic_reduction_of_a_word(u) (word: 1,-2,1, word: ) :: sage: u = Word([1,2,-2,-1,2,2,1,-1,-2]) sage: cyclic_reduction_of_a_word(u) (word: 2, word: ) :: sage: u = Word() sage: cyclic_reduction_of_a_word(u) (word: , word: ) """ v = free_group_reduction(u) if len(v) <= 1: return (v,Word()) w = Word() while v[0] == inverse_letter(v[-1]): w = Word([v[-1]]) + w v = v[1:-1] return (v,w)
################# ## random objects #################
[docs]def random_letter(r): r""" Return a random letter in the symmetric alphabet of this size. `r` is expected to be a positive integer. The symmetric alphabet of size `r` is the set of non-zero integers between `-r` and `r`. The probability distribution is uniform. INPUT: - ``r`` -- integer OUTPUT: - integer EXAMPLES :: sage: from stallings_graphs.about_words import random_letter sage: random_letter(4) # random 2 """ a = randint(0,2 * r - 1) return symmetric_alphabet(r)[a]
[docs]def random_word(n,r): r""" Return a random word of length `n` in the symmetric alphabet of size `r`. `n` is expected to be a non-negative integer and `r` is expected to be a positive integer. The word produced on the symmetric alphabet of size `r` is not necessarily reduced. The probability distribution is uniform. INPUT: - ``n`` -- integer - ``r`` -- integer OUTPUT: - ``Word`` EXAMPLES :: sage: from stallings_graphs.about_words import random_word sage: random_word(4,5) # random Word([2,-1,3,-4,-1]) """ if n == 0: return [] else: return Word([random_letter(r) for _ in range(n)])
[docs]def random_reduced_word(n,r): r""" Return a random reduced word of length `n` in the symmetric alphabet of size `r`. `n` is expected to be a non-negative integer and `r` is expected to be a positive integer. A word is reduced if it does not contain consecutive letters which are mutually inverse. The probability distribution is uniform. INPUT: - ``n`` -- integer - ``r`` -- integer OUTPUT: - ``Word`` EXAMPLES :: sage: from stallings_graphs.about_words import random_reduced_word sage: random_reduced_word(4,5) # random Word([2,-1,3,-4,-1]) """ if n == 0: return [] else: v = [random_letter(r)] for i in range(1,n): k = symmetric_alphabet(r).index(inverse_letter(v[-1])) x = randint(0,2 * r - 2) if x < k: v.append(symmetric_alphabet(r)[x]) else: v.append(symmetric_alphabet(r)[x + 1]) return Word(v)