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.

Sébastien Labbé

Factor complexity of words generated by multidimensional continued fraction algorithms