# Hypercubic billiard subshifts¶

Hypercubic billiard subshifts

The construction of a billiard word in this module is made by lifting a certain set of projected sturmian sequences.

EXAMPLES:

The Fibonacci word:

sage: from slabbe import HypercubicBilliardSubshift
sage: s = HypercubicBilliardSubshift((golden_ratio,1))
sage: s.characteristic_word()
word: 0100101001001010010100100101001001010010...
sage: words.FibonacciWord()
word: 0100101001001010010100100101001001010010...


A 3-dimensional example:

sage: s = HypercubicBilliardSubshift((1,sqrt(2),pi))
sage: s.characteristic_word()
word: 2212021220122120221202122102212021220212...
sage: L = s.language(6, prefix_length=10000)
sage: len(L)
43
sage: v = [sqrt(p) for p in primes_first_n(7)]
sage: s = HypercubicBilliardSubshift(v)
sage: K = s.language(2, prefix_length=10000)
sage: len(K)
43


An open question is to find a bijection between L and K:

sage: L
{word: 022120, word: 120212, word: 022122, word: 212221, word: 212220,
word: 212021, word: 212022, word: 222102, word: 220122, word: 022210,
word: 120221, word: 022212, word: 122201, word: 122120, word: 012212,
word: 201221, word: 201222, word: 220212, word: 221022, word: 221220,
word: 012220, word: 102212, word: 122210, word: 122212, word: 122012,
word: 012221, word: 210221, word: 210222, word: 212201, word: 212202,
word: 202122, word: 222120, word: 021220, word: 102221, word: 122021,
word: 122102, word: 021222, word: 021221, word: 212212, word: 212210,
word: 202212, word: 222012, word: 221202}
sage: K
{word: 20, word: 21, word: 23, word: 24, word: 25, word: 26, word: 60,
word: 61, word: 63, word: 66, word: 64, word: 62, word: 65,
word: 30, word: 31, word: 32, word: 34, word: 35, word: 36,
word: 01, word: 02, word: 03, word: 04, word: 05, word: 06,
word: 40, word: 42, word: 41, word: 45, word: 43, word: 46,
word: 10, word: 12, word: 13, word: 14, word: 15, word: 16,
word: 51, word: 50, word: 53, word: 56, word: 52, word: 54}

sage: v = [sqrt(p) for p in primes_first_n(4)]
sage: s = HypercubicBilliardSubshift(v)
sage: L = s.language(4, prefix_length=18000)
sage: len(L)
73
sage: v = [sqrt(p) for p in primes_first_n(5)]
sage: t = HypercubicBilliardSubshift(v)
sage: K = t.language(3, prefix_length=10000)
sage: len(K)
73
sage: L
{word: 0123, word: 1330, word: 3031, word: 1332, word: 3032, word: 2303,
word: 2301, word: 2302, word: 2310, word: 3120, word: 0213, word: 0132,
word: 0133, word: 1023, word: 3123, word: 3203, word: 2313, word: 3201,
word: 2312, word: 1032, word: 2320, word: 1033, word: 3130, word: 3132,
word: 3213, word: 2323, word: 3210, word: 2321, word: 2013, word: 0231,
word: 2330, word: 2331, word: 0233, word: 0232, word: 0313, word: 0312,
word: 1203, word: 3301, word: 3302, word: 2332, word: 0321, word: 3310,
word: 0323, word: 3312, word: 3232, word: 3230, word: 3231, word: 2103,
word: 2031, word: 2032, word: 2033, word: 1303, word: 0332, word: 0331,
word: 1302, word: 3320, word: 3321, word: 1230, word: 1231, word: 1232,
word: 1233, word: 3012, word: 3013, word: 3021, word: 3102, word: 2132,
word: 3103, word: 1321, word: 1323, word: 1320, word: 3023, word: 2133,
word: 2130}
sage: K
{word: 012, word: 013, word: 014, word: 410, word: 412, word: 413, word: 414,
word: 102, word: 103, word: 104, word: 021, word: 024, word: 023, word: 341,
word: 343, word: 344, word: 342, word: 424, word: 423, word: 340, word: 421,
word: 031, word: 032, word: 034, word: 431, word: 430, word: 432, word: 434,
word: 120, word: 201, word: 041, word: 123, word: 124, word: 440, word: 441,
word: 442, word: 044, word: 042, word: 043, word: 203, word: 204, word: 443,
word: 210, word: 130, word: 132, word: 213, word: 134, word: 214, word: 301,
word: 140, word: 302, word: 142, word: 143, word: 144, word: 304, word: 310,
word: 230, word: 312, word: 231, word: 314, word: 234, word: 401, word: 402,
word: 403, word: 404, word: 320, word: 321, word: 324, word: 244, word: 243,
word: 240, word: 241, word: 420}


The following illustrates that we may need to go very far to get all factors:

sage: s = HypercubicBilliardSubshift((sqrt(3),sqrt(2),sqrt(5)))
sage: L = s.language(6, prefix_length=1000000)     # not tested
WARNING: Factor complexity is p(6)=43, but only 41 factors found in
the prefix of length 1000000


AUTHORS:

• Initial version, Mélodie Andrieu et Sébastien Labbé, Novembre 7, 2022

class slabbe.billiard_nD.HypercubicBilliardSubshift(v)

Bases: object

INPUT:

• v – d-dimensional speed vector

EXAMPLES:

sage: from slabbe import HypercubicBilliardSubshift
sage: v = (1, sqrt(2), pi)
sage: s = HypercubicBilliardSubshift(v)

abelian_complexity(n)

Return the number abelian factors of length n of the hypercubic billiard word

INPUT:

• n – integer

OUTPUT:

integer

EXAMPLES:

sage: from slabbe import HypercubicBilliardSubshift
sage: s = HypercubicBilliardSubshift((1,sqrt(2),pi))
sage: [s.abelian_complexity(i) for i in range(10)]
[1, 3, 4, 4, 4, 4, 4, 4, 4, 4]


Indeed we compute 4 abelian vectors of factors of length 10:

sage: L = s.language(6, prefix_length=10000)
sage: set(tuple(w.abelian_vector()) for w in L)
{(0, 2, 4), (1, 1, 4), (1, 2, 3), (2, 1, 3)}
sage: from collections import Counter
sage: Counter(tuple(w.abelian_vector()) for w in L)
Counter({(1, 2, 3): 18,
(1, 1, 4): 18,
(2, 1, 3): 4,
(0, 2, 4): 3})

sage: s = HypercubicBilliardSubshift((1,sqrt(2),pi,sqrt(3)))
sage: [s.abelian_complexity(i) for i in range(10)]
[1, 4, 7, 8, 8, 8, 8, 8, 8, 8]

characteristic_word(verbose=False)

Return the characteristic billiard word with given speed vector

INPUT:

• verbose – boolean

OUTPUT:

infinite word over alphabet {0,1,…,d-1}

EXAMPLES:

sage: from slabbe import HypercubicBilliardSubshift
sage: s = HypercubicBilliardSubshift((1,sqrt(2),pi))
sage: s.characteristic_word()
word: 2212021220122120221202122102212021220212...


… compared to:

sage: from slabbe import BilliardCube
sage: b = BilliardCube((1,sqrt(2), pi))
sage: b.to_word(alphabet=[0,1,2])
word: 2120212202122102212021220122210221202122...

sage: v = (100+1/pi,1+1/pi^2,49+1/sqrt(2),pi)
sage: s = HypercubicBilliardSubshift(v)
sage: s.characteristic_word()
word: 0020020020020020020020020020020020020020...


TESTS:

sage: s = HypercubicBilliardSubshift((1,sqrt(2),pi))
sage: s.characteristic_word(verbose=True)
(1.00000000000000, 1.41421356237310, 3.14159265358979)
(0, 1) 1010110101101010110101101010110101101011...
(0, 2) 2220222022202220222022202220222202220222...
(1, 2) 2212212212212221221221221221222122122122...
word: 2212021220122120221202122102212021220212...


AUTHORS:

• Mélodie Andrieu et Sébastien Labbé, Novembre 7, 2022

complexity(n)

Return the number factors of length n of the hypercubic billiard word

INPUT:

• n – integer

OUTPUT:

integer

EXAMPLES:

sage: from slabbe import HypercubicBilliardSubshift
sage: s = HypercubicBilliardSubshift((1,sqrt(2),pi))
sage: [s.complexity(i) for i in range(10)]
[1, 3, 7, 13, 21, 31, 43, 57, 73, 91]


It matches the formula $$n^2+n+1$$ in dimension 3:

sage: [n^2+n+1 for n in range(10)]
[1, 3, 7, 13, 21, 31, 43, 57, 73, 91]

sage: s = HypercubicBilliardSubshift((1,sqrt(2),pi,sqrt(3)))
sage: [s.complexity(i) for i in range(10)]
[1, 4, 13, 34, 73, 136, 229, 358, 529, 748]

dimension()

Return the ambient dimension of the billiard table.

EXAMPLES:

sage: from slabbe import HypercubicBilliardSubshift
sage: v = (1, sqrt(2), pi)
sage: s = HypercubicBilliardSubshift(v)
sage: s.dimension()
3

language(n, prefix_length=1000)

Return the language of the hypercubic billiard word

INPUT:

• n – integer

• prefix_length – integer (default: 1000),

OUTPUT:

list of words

EXAMPLES:

sage: from slabbe import HypercubicBilliardSubshift
sage: s = HypercubicBilliardSubshift((1,sqrt(2),pi))


Two factors of length 6 appear far away in the characteristic word:

sage: s.language(6, prefix_length=10000) - s.language(6)
WARNING: Factor complexity is p(6)=43, but only 41 factors
found in the prefix of length 1000
{word: 012220, word: 022210}


Same for factors of length 15:

sage: s.characteristic_word()[8252:8292]
word: 1202122012212022120212210221220212210221
sage: s.language(15, prefix_length=8292) - s.language(15, prefix_length=8280)
WARNING: Factor complexity is p(15)=241, but only 236 factors
found in the prefix of length 8280
{word: 022122021221022,
word: 210221220212210,
word: 102212202122102,
word: 221022122021221,
word: 221220212210221}

print_factor_complexity_by_abelian(n, prefix_length=10000)

Compare the formula with the actual number of abelian classes

INPUT:

• n – integer

EXAMPLES:

Even with Fibonacci word, it does not work well:

sage: from slabbe import HypercubicBilliardSubshift
sage: s = HypercubicBilliardSubshift((golden_ratio,1))
sage: s.print_factor_complexity_by_abelian(3)
Factor Complexity:
p(3) = 4
= 1*1*1 + 1*3*1
= 1*1 + 3*1
Counting each abelian factor:
abelian vector   number of factors
+----------------+-------------------+
(1, 2)           1
(2, 1)           3
sage: s.print_factor_complexity_by_abelian(4)
Factor Complexity:
p(4) = 5
= 1*1*1 + 1*4*1
= 1*1 + 4*1
Counting each abelian factor:
abelian vector   number of factors
+----------------+-------------------+
(3, 1)           2
(2, 2)           3


In 3 dimensions:

sage: s = HypercubicBilliardSubshift((1,sqrt(2),pi))


It may seem that something makes sense between the number of factors with given abelian vector and the complexity formula:

sage: s.print_factor_complexity_by_abelian(2)
Factor Complexity:
p(2) = 7
= 1*1*1 + 1*2*2 + 2*1*1
= 1*1 + 2*2 + 2*1
Counting each abelian factor:
abelian vector   number of factors
+----------------+-------------------+
(0, 0, 2)        1
(1, 0, 1)        2
(1, 1, 0)        2
(0, 1, 1)        2

sage: s.print_factor_complexity_by_abelian(3)
Factor Complexity:
p(3) = 13
= 1*1*1 + 1*3*2 + 2*3*1
= 1*1 + 3*2 + 6*1
Counting each abelian factor:
abelian vector   number of factors
+----------------+-------------------+
(0, 0, 3)        1
(0, 1, 2)        3
(1, 0, 2)        3
(1, 1, 1)        6

sage: s.print_factor_complexity_by_abelian(4)
Factor Complexity:
p(4) = 21
= 1*1*1 + 1*4*2 + 2*6*1
= 1*1 + 4*2 + 12*1
Counting each abelian factor:
abelian vector   number of factors
+----------------+-------------------+
(0, 2, 2)        1
(1, 0, 3)        4
(0, 1, 3)        4
(1, 1, 2)        12


But everything breaks down when looking at factors of length 5 or more:

sage: s.print_factor_complexity_by_abelian(5)
Factor Complexity:
p(5) = 31
= 1*1*1 + 1*5*2 + 2*10*1
= 1*1 + 5*2 + 20*1
Counting each abelian factor:
abelian vector   number of factors
+----------------+-------------------+
(0, 2, 3)        3
(0, 1, 4)        3
(1, 2, 2)        5
(1, 1, 3)        20

sage: s.print_factor_complexity_by_abelian(6)
Factor Complexity:
p(6) = 43
= 1*1*1 + 1*6*2 + 2*15*1
= 1*1 + 6*2 + 30*1
Counting each abelian factor:
abelian vector   number of factors
+----------------+-------------------+
(0, 2, 4)        3
(2, 1, 3)        4
(1, 2, 3)        18
(1, 1, 4)        18

sage: s.print_factor_complexity_by_abelian(7)
Factor Complexity:
p(7) = 57
= 1*1*1 + 1*7*2 + 2*21*1
= 1*1 + 7*2 + 42*1
Counting each abelian factor:
abelian vector   number of factors
+----------------+-------------------+
(2, 2, 3)        7
(2, 1, 4)        9
(1, 1, 5)        10
(1, 2, 4)        31

sage: v = [sqrt(p) for p in primes_first_n(7)]
sage: s = HypercubicBilliardSubshift(v)
sage: s.print_factor_complexity_by_abelian(2)
Factor Complexity:
p(2) = 43
= 1*1*1 + 1*2*6 + 2*1*15
= 1*1 + 2*6 + 2*15
Counting each abelian factor:
abelian vector          number of factors
+-----------------------+-------------------+
(0, 0, 0, 0, 0, 0, 2)   1
(1, 0, 1, 0, 0, 0, 0)   2
(0, 1, 1, 0, 0, 0, 0)   2
(0, 0, 1, 1, 0, 0, 0)   2
(0, 0, 1, 0, 1, 0, 0)   2
(0, 0, 1, 0, 0, 1, 0)   2
(0, 0, 1, 0, 0, 0, 1)   2
(1, 0, 0, 0, 0, 0, 1)   2
(0, 1, 0, 0, 0, 0, 1)   2
(0, 0, 0, 1, 0, 0, 1)   2
(0, 0, 0, 0, 1, 0, 1)   2
(0, 0, 0, 0, 0, 1, 1)   2
(1, 0, 0, 1, 0, 0, 0)   2
(0, 1, 0, 1, 0, 0, 0)   2
(0, 0, 0, 1, 1, 0, 0)   2
(0, 0, 0, 1, 0, 1, 0)   2
(1, 1, 0, 0, 0, 0, 0)   2
(1, 0, 0, 0, 1, 0, 0)   2
(1, 0, 0, 0, 0, 1, 0)   2
(0, 1, 0, 0, 1, 0, 0)   2
(0, 0, 0, 0, 1, 1, 0)   2
(0, 1, 0, 0, 0, 1, 0)   2

sage: v = [sqrt(p) for p in primes_first_n(8)]
sage: s = HypercubicBilliardSubshift(v)
sage: s.print_factor_complexity_by_abelian(2)
Factor Complexity:
p(2) = 57
= 1*1*1 + 1*2*7 + 2*1*21
= 1*1 + 2*7 + 2*21
Counting each abelian factor:
abelian vector             number of factors
+--------------------------+-------------------+
(0, 0, 0, 0, 0, 0, 0, 2)   1
(1, 0, 1, 0, 0, 0, 0, 0)   2
(0, 1, 1, 0, 0, 0, 0, 0)   2
(0, 0, 1, 1, 0, 0, 0, 0)   2
(0, 0, 1, 0, 1, 0, 0, 0)   2
(0, 0, 1, 0, 0, 1, 0, 0)   2
(0, 0, 1, 0, 0, 0, 1, 0)   2
(0, 0, 1, 0, 0, 0, 0, 1)   2
(1, 0, 0, 0, 0, 0, 1, 0)   2
(0, 0, 0, 0, 1, 0, 1, 0)   2
(0, 1, 0, 0, 0, 0, 1, 0)   2
(0, 0, 0, 0, 0, 0, 1, 1)   2
(0, 0, 0, 1, 0, 0, 1, 0)   2
(0, 0, 0, 0, 0, 1, 1, 0)   2
(1, 0, 0, 1, 0, 0, 0, 0)   2
(0, 1, 0, 1, 0, 0, 0, 0)   2
(0, 0, 0, 1, 1, 0, 0, 0)   2
(0, 0, 0, 1, 0, 1, 0, 0)   2
(0, 0, 0, 1, 0, 0, 0, 1)   2
(1, 0, 0, 0, 0, 0, 0, 1)   2
(0, 1, 0, 0, 0, 0, 0, 1)   2
(0, 0, 0, 0, 1, 0, 0, 1)   2
(0, 0, 0, 0, 0, 1, 0, 1)   2
(1, 1, 0, 0, 0, 0, 0, 0)   2
(1, 0, 0, 0, 1, 0, 0, 0)   2
(1, 0, 0, 0, 0, 1, 0, 0)   2
(0, 0, 0, 0, 1, 1, 0, 0)   2
(0, 1, 0, 0, 1, 0, 0, 0)   2
(0, 1, 0, 0, 0, 1, 0, 0)   2

slabbe.billiard_nD.check_open_question(d, n, prefix_length=10000)

INPUT:

• d – integer, dimension of billiard table

• n – integer, length of words

• prefix_length – integer (default:10000)

EXAMPLES:

sage: from slabbe.billiard_nD import check_open_question
sage: check_open_question(5, 5, prefix_length=180000)   # long time
WARNING: Factor complexity is p(5)=501, but only 496 factors found in the prefix of length 180000
Factor Complexity:
p(5) = 501
= 1*1*1 + 1*5*4 + 2*10*6 + 6*10*4 + 24*5*1
= 1*1 + 5*4 + 20*6 + 60*4 + 120*1
Counting each abelian factor:
WARNING: Factor complexity is p(5)=501, but only 496 factors found in the prefix of length 180000
abelian vector    number of factors
+-----------------+-------------------+
(0, 0, 2, 2, 1)   3
(0, 2, 1, 1, 1)   6
(0, 0, 2, 1, 2)   7
(0, 1, 2, 1, 1)   10
(1, 0, 2, 1, 1)   10
(0, 1, 0, 2, 2)   15
(0, 0, 1, 2, 2)   15
(1, 0, 0, 2, 2)   15
(1, 1, 0, 2, 1)   20
(0, 1, 1, 2, 1)   20
(1, 0, 1, 2, 1)   20
(1, 1, 1, 0, 2)   55
(1, 1, 0, 1, 2)   60
(1, 0, 1, 1, 2)   60
(0, 1, 1, 1, 2)   60
(1, 1, 1, 1, 1)   120
Factor Complexity:
p(4) = 501
= 1*1*1 + 1*4*5 + 2*6*10 + 6*4*10 + 24*1*5
= 1*1 + 4*5 + 12*10 + 24*10 + 24*5
Counting each abelian factor:
WARNING: Factor complexity is p(4)=501, but only 476 factors found in the prefix of length 180000
abelian vector       number of factors
+--------------------+-------------------+
(0, 0, 0, 2, 1, 1)   2
(0, 0, 0, 0, 2, 2)   3
(1, 0, 0, 0, 2, 1)   4
(0, 1, 0, 0, 2, 1)   4
(0, 0, 0, 1, 2, 1)   4
(0, 0, 1, 0, 2, 1)   4
(1, 1, 0, 0, 0, 2)   6
(1, 0, 1, 0, 0, 2)   7
(0, 1, 0, 1, 0, 2)   8
(0, 0, 1, 1, 0, 2)   8
(0, 1, 1, 0, 0, 2)   9
(1, 0, 0, 1, 0, 2)   9
(1, 0, 0, 0, 1, 2)   12
(0, 1, 0, 0, 1, 2)   12
(0, 0, 1, 0, 1, 2)   12
(0, 0, 0, 1, 1, 2)   12
(1, 1, 1, 1, 0, 0)   24
(1, 1, 1, 0, 1, 0)   24
(1, 1, 1, 0, 0, 1)   24
(1, 1, 0, 1, 0, 1)   24
(1, 1, 0, 1, 1, 0)   24
(1, 1, 0, 0, 1, 1)   24
(1, 0, 1, 0, 1, 1)   24
(1, 0, 0, 1, 1, 1)   24
(0, 1, 0, 1, 1, 1)   24
(0, 1, 1, 0, 1, 1)   24
(1, 0, 1, 1, 0, 1)   24
(1, 0, 1, 1, 1, 0)   24
(0, 1, 1, 1, 1, 0)   24
(0, 1, 1, 1, 0, 1)   24
(0, 0, 1, 1, 1, 1)   24