## Factor complexity of words generated by multidimensional continued fraction algorithms

03 novembre 2022 | Catégories: sage | View Comments

I was asked by email how to compute with SageMath the factor complexity of words generated by multidimensional continued fraction algorithms. I'm copying my answer here so that I can more easily share it.

**A) How to calculate the factor complexity of a word**

To compute the complexity in factors, we need a finite word and *not* an
infinite infinite word. In the example below, I take a prefix of the Fibonacci
word and I compute the number of factors of size 100 and of size 0 to 19:

sage: w = words.FibonacciWord() sage: w word: 0100101001001010010100100101001001010010... sage: prefix = w[:100000] sage: prefix.number_of_factors(100) 101 sage: [prefix.number_of_factors(i) for i in range(20)] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

The documentation for the number_of_factors method contains more examples, etc.

**B) How to construct an S-adic word in SageMath**

The method words.s_adic in SageMath allows to construct an S-adic sequence from a directive sequence, a set of substitutions and a sequence of first letters.

For example, we may use Kolakoski word as a directive sequence:

sage: directive_sequence = words.KolakoskiWord() sage: directive_sequence word: 1221121221221121122121121221121121221221...

Then, I define the Thue-Morse and Fibonacci substitutions:

sage: tm = WordMorphism('a->ab,b->ba') sage: fib = WordMorphism('a->ab,b->a') sage: tm WordMorphism: a->ab, b->ba sage: fib WordMorphism: a->ab, b->a

Then, to define an S-adic sequence, I also need to define the sequence of first letters. Here, it is always the constant sequence a,a,a,a,...:

sage: from itertools import repeat sage: letters = repeat('a')

I associate the letter 1 in the Kolakoski sequence to the Thue-Morse morphism and 2 to the Fibonacci morphism, this allows to construct an S-adic sequence:

sage: w = words.s_adic(directive_sequence, letters, {1:tm, 2:fib}) sage: w word: abbaababbaabbaabbaababbaabbaababbaababba...

Then, as above, I can take a prefix and compute its factor complexity:

sage: prefix = w[:100000] sage: [prefix.number_of_factors(i) for i in range(20)] [1, 2, 4, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 34, 38]

**C) Creating an S-adic sequence from Brun algorithm**

With the package slabbe, you can construct an S-adic sequence from some of the known Multidimensional Continued Fraction Algorithm.

One can install it by running `sage -pip install slabbe` in a terminal where
sage command exists. Sometimes this does not work.

Then, one may do:

sage: from slabbe.mult_cont_frac import Brun sage: algo = Brun() sage: algo Brun 3-dimensional continued fraction algorithm sage: D = algo.substitutions() sage: D {312: WordMorphism: 1->12, 2->2, 3->3, 321: WordMorphism: 1->1, 2->21, 3->3, 213: WordMorphism: 1->13, 2->2, 3->3, 231: WordMorphism: 1->1, 2->2, 3->31, 123: WordMorphism: 1->1, 2->23, 3->3, 132: WordMorphism: 1->1, 2->2, 3->32}

sage: directive_sequence = algo.coding_iterator((1,e,pi)) sage: [next(directive_sequence) for _ in range(10)] [123, 312, 312, 321, 132, 123, 312, 231, 231, 213]

Construction of the s-adic word from the substitutions and the directive sequence:

sage: from itertools import repeat sage: D = algo.substitutions() sage: directive_sequence = algo.coding_iterator((1,e,pi)) sage: words.s_adic(directive_sequence, repeat(1), D) word: 1232323123233231232332312323123232312323...

Shortcut:

sage: algo.s_adic_word((1,e,pi)) word: 1232323123233231232332312323123232312323...

There are some more examples in the documentation.

This code was used in the creation of the 3-dimensional Continued Fraction Algorithms Cheat Sheets 7 years ago during my postdoc at Université de Liège, Belgium.