d-dimensional Sturmian Configurations

d-dimensional Sturmian Configurations

The \(d\)-dimensional Sturmian configuration is a function \(\mathbb{Z}^d\to\{0,1,\dots,d\}\) as follows. Given \(\boldsymbol{\alpha}=(\alpha_1,\dots,\alpha_d)\in\mathbb{R}^d\), we define

\[\begin{split}\begin{array}{rccl} s_{\boldsymbol{\alpha}\rho}:&\mathbb{Z}^d & \to & \{0,1,\dots,d\}\\ &\boldsymbol{n} & \mapsto & \sum_{i=1}^d \left(\lfloor\alpha_i+\boldsymbol{n}\cdot\boldsymbol{\alpha}+\rho\rfloor -\lfloor\boldsymbol{n}\cdot\boldsymbol{\alpha}+\rho\rfloor\right),\\ \end{array}\end{split}\]

and

\[\begin{split}\begin{array}{rccl} s'_{\boldsymbol{\alpha}\rho}:&\mathbb{Z}^d & \to & \{0,1,\dots,d\}\\ &\boldsymbol{n} & \mapsto & \sum_{i=1}^d \left(\lceil\alpha_i+\boldsymbol{n}\cdot\boldsymbol{\alpha}+\rho\rceil -\lceil\boldsymbol{n}\cdot\boldsymbol{\alpha}+\rho\rceil\right),\\ \end{array}\end{split}\]

When \(d=1\), this corresponds to Sturmian sequences, or more precisely, the lower mechanical word and the upper mechanical word. When \(d=2\), this definition is equivalent to discrete planes as defined in cite{MR1782038,MR1906478}.

EXAMPLES:

sage: z = polygen(QQ, 'z')
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()

sage: from slabbe import dSturmianConfiguration
sage: c_ceil = dSturmianConfiguration((phi^-1, sqrt(2)-1), 0, ceil_or_floor='ceil')
sage: c_floor = dSturmianConfiguration((phi^-1, sqrt(2)-1), 0, ceil_or_floor='floor')
sage: c_ceil.rectangular_subword_matrix(((-1,10), (-1,10)))
[0 2 0 2 1 0 2 1 0 2 0]
[2 0 2 1 0 2 1 0 2 0 2]
[0 2 1 0 2 0 2 2 0 2 1]
[2 1 0 2 0 2 1 0 2 1 0]
[1 0 2 0 2 1 0 2 1 0 2]
[0 2 0 2 1 0 2 0 2 2 0]
[2 0 2 1 0 2 0 2 1 0 2]
[0 2 1 0 2 0 2 1 0 2 1]
[2 1 0 2 0 2 1 0 2 0 2]
[0 2 2 0 2 1 0 2 0 2 1]
[2 1 0 2 1 0 2 0 2 1 0]
sage: c_floor.rectangular_subword_matrix(((-1,10), (-1,10)))
[0 2 0 2 1 0 2 1 0 2 0]
[2 0 2 1 0 2 1 0 2 0 2]
[0 2 1 0 2 0 2 2 0 2 1]
[2 1 0 2 0 2 1 0 2 1 0]
[1 0 2 0 2 1 0 2 1 0 2]
[0 2 0 2 1 0 2 0 2 2 0]
[2 0 2 1 0 2 0 2 1 0 2]
[0 2 1 0 2 0 2 1 0 2 1]
[2 1 0 2 0 2 1 0 2 0 2]
[1 0 2 0 2 1 0 2 0 2 1]
[2 2 0 2 1 0 2 0 2 1 0]
sage: window = ((0,30),(0,30))
sage: sorted(c_floor.rectangular_subwords_matrix((2,2), window))
[
[0 2]  [0 2]  [1 0]  [1 0]  [2 0]  [2 1]  [2 1]  [2 2]
[2 0], [2 1], [0 2], [2 2], [0 2], [0 2], [1 0], [1 0]
]
sage: len(_)
8
class slabbe.ddim_sturmian_configuration.dSturmianConfiguration(normal_vector, rho, ceil_or_floor='floor')

Bases: object

INPUT:

  • normal_vector – tuple of coordinates

  • rho – real number

  • ceil_or_floor – string (default: 'floor') 'ceil' or 'floor'

EXAMPLES:

sage: from slabbe import dSturmianConfiguration
sage: dSturmianConfiguration((.34, .72), 0)
2-dim Sturmian Configuration: alpha=(0.340000000000000, 0.720000000000000), rho=0 using floor
bispecial_patterns(n)

Return the vectors of L-shaped bispecial patterns of size up to n.

INPUT:

  • n – integer, maximum size

EXAMPLES:

sage: z = polygen(QQ, 'z')
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((phi^-1, phi^-2), 0)
sage: c.bispecial_patterns(5)
{(0, 0): [()],
 (0, 1): [()],
 (0, 3): [(2, 0)],
 (1, -2): [(0, 2)],
 (1, 0): [()],
 (1, 1): [(0,)],
 (2, -4): [(0, 2, 1, 0, 2)],
 (2, -1): [(0, 2)],
 (2, 2): [(0, 2, 0)],
 (3, -3): [(0, 2, 1, 0, 2)],
 (3, 0): [(0, 2)],
 (3, 3): [(0, 2, 1, 2, 0)],
 (4, -2): [(0, 2, 1, 0, 2)],
 (4, 4): [(0, 2, 1, 0, 1, 2, 0)]}

With totally irrational normal vector:

sage: c = dSturmianConfiguration((phi^-1, sqrt(2)), 0)
sage: c.bispecial_patterns(5)
{(0, 0): [()],
 (0, 1): [()],
 (0, 2): [(3,)],
 (0, 3): [(2, 3), (3, 1)],
 (1, -4): [(1, 3, 1, 3)],
 (1, -3): [(3, 1, 3)],
 (1, -2): [(1, 3)],
 (1, -1): [(3,)],
 (1, 0): [()],
 (1, 1): [(1,), (3,)],
 (1, 2): [(3, 1)],
 (1, 3): [(1, 3, 1)],
 (1, 4): [(3, 1, 2, 3)],
 (2, -3): [(3, 1, 3, 2)],
 (2, -2): [(1, 3, 2), (3, 1, 3)],
 (2, -1): [(1, 3)],
 (2, 0): [(3,)],
 (2, 1): [(1, 3)],
 (2, 2): [(1, 3, 1)],
 (2, 3): [(3, 1, 3, 1)],
 (2, 4): [(1, 3, 1, 3, 1)],
 (3, -2): [(3, 1, 3, 2)],
 (3, -1): [(1, 3, 2)],
 (3, 0): [(1, 3)],
 (3, 1): [(3, 1, 3)],
 (3, 2): [(1, 3, 2, 3)],
 (3, 4): [(3, 1, 3, 1, 3, 1)],
 (4, -4): [(1, 3, 2, 1, 3, 1, 3)],
 (4, 0): [(3, 1, 3)],
 (4, 1): [(1, 3, 2, 1)],
 (4, 2): [(3, 1, 3, 2, 3)],
 (4, 3): [(1, 3, 2, 1, 2, 3)]}
bispecial_patterns_of_Lshape(v)

Return the patterns of a given L-shape bispecial of vector v

INPUT:

  • v – vector

EXAMPLES:

sage: z = polygen(QQ, 'z')
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((phi^-1, sqrt(2)), 0)
sage: c.bispecial_patterns_of_Lshape((3,1))
[(3, 1, 3)]
sage: c.bispecial_patterns_of_Lshape((0,7))
[(3, 1, 3, 1, 2, 3)]
sage: c.bispecial_patterns_of_Lshape((7,0))
[(3, 1, 3, 2, 1, 3)]
bispecial_patterns_of_shape(shape, a, b)

Return the patterns of a given shape bispecial at positions a and b

INPUT:

  • shape – list, list of coordinates

  • a – position

  • b – position

EXAMPLES:

sage: z = polygen(QQ, 'z')
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((phi^-1, phi^-2), 0)
sage: shape = [(0,0), (1,0), (0,1), (1,1)]
sage: c.bispecial_patterns_of_shape(shape, (-1,0), (2,1))
[]

With totally irrational normal vector:

sage: c = dSturmianConfiguration((phi^-1, sqrt(2)), 0)
sage: shape = [(0,0), (1,0), (0,1), (1,1)]
sage: c.bispecial_patterns_of_shape(shape, (-1,0), (2,1))
[(3, 1, 1, 3)]
language(shape)

Return the language of a given shape.

INPUT:

  • shape – list, list of coordinates

OUTPUT:

list of tuples

EXAMPLES:

sage: sqrt2 = AA(sqrt(2))
sage: sqrt3 = AA(sqrt(3))
sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((sqrt2/2, sqrt3/4), 0)
sage: shape = [(0,0), (1,0), (0,1), (1,1)]
sage: sorted(c.language(shape))
[(0, 2, 1, 0),
 (0, 2, 2, 0),
 (0, 2, 2, 1),
 (1, 0, 2, 1),
 (1, 0, 2, 2),
 (2, 0, 0, 2),
 (2, 1, 0, 2),
 (2, 2, 1, 0)]
sage: len(set(c.language(shape)))
8
sage: c.pattern_complexity_upper_bound(shape)
8
pattern_complexity(shape, window, avoid_border=0, verbose=False)

Return the number of patterns having a given shape inside of a rectangular window box.

INPUT:

  • shape – list, list of coordinates

  • window – tuple of 2-tuples

  • avoid_border – integer (default: 0), the size of the border

    to avoid during the computation

  • verbose – bool (default: False), print the theoretical upper-bound

OUTPUT

integer

EXAMPLES:

sage: z = polygen(QQ, 'z')
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((phi^-1, phi^-2), 0)
sage: shape = [(0,0), (1,0), (0,1), (1,1)]
sage: window = ((0,10),(0,10))
sage: c.pattern_complexity(shape, window)
5

Totally irrational normal vector:

sage: c = dSturmianConfiguration((phi^-1, sqrt(2)), 0)
sage: shape = [(0,0), (1,0), (0,1), (1,1)]
sage: window = ((0,10),(0,10))
sage: c.pattern_complexity(shape, window)
8
pattern_complexity_upper_bound(shape)

Return the known upper bound for the number of patterns of given shape it may have.

INPUT:

  • shape – list, list of coordinates

OUTPUT

integer

EXAMPLES:

sage: z = polygen(QQ, 'z')
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((phi^-1, phi^-2), 0)
sage: shape = [(0,0), (1,0), (0,1), (1,1)]
sage: c.pattern_complexity_upper_bound(shape)
8

Totally irrational normal vector:

sage: c = dSturmianConfiguration((phi^-1, sqrt(2)), 0)
sage: shape = [(0,0), (1,0), (0,1), (1,1)]
sage: c.pattern_complexity_upper_bound(shape)
8
pattern_number_occurrences(shape, window, avoid_border=0)

Return the number of occurrences of every pattern having a given shape inside of a rectangular window box.

INPUT:

  • shape – list, list of coordinates

  • window – tuple of 2-tuples

  • avoid_border – integer (default: 0), the size of the border

    to avoid during the computation

OUTPUT

a dict where each key is a tuple giving the tiles at each coordinate of the shape (in the same order) and values are integers

EXAMPLES:

sage: z = polygen(QQ, 'z')
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((phi^-1, phi^-2), 0)
sage: shape = [(0,0), (1,0), (0,1), (1,1)]
sage: window = ((0,10),(0,10))
sage: c.pattern_number_occurrences(shape, window)
Counter({(0, 2, 1, 0): 20, (1, 0, 2, 1): 18, (2, 1, 0, 2): 18, 
         (2, 0, 0, 2): 13, (0, 2, 2, 0): 12})

Totally irrational normal vector:

sage: c = dSturmianConfiguration((phi^-1, sqrt(2)), 0)
sage: shape = [(0,0), (1,0), (0,1), (1,1)]
sage: window = ((0,10),(0,10))
sage: len(c.pattern_number_occurrences(shape, window))
8
rectangular_subword(window)

Return the rectangular subword appearing in the given rectangular window.

INPUT:

  • window – tuple of 2-tuples

OUTPUT:

list of list with euclidean coordinates

EXAMPLES:

sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((.34, .72), 0)
sage: window = ((0,3),(0,4))
sage: sorted(c.rectangular_subword(window))
[[0, 2, 1, 0], [1, 0, 2, 1], [2, 1, 0, 2]]
rectangular_subword_discrete_plane_tikz(window, fill_color=None, extra_code_before='', extra_code_after='')

Return the rectangular subword appearing in the given rectangular window (as a TikzPicture).

INPUT:

  • window – tuple of 2-tuples (start, stop)

  • fill_color – dict (default: None), if None, it is replaced by {0:'black!10',1:'black!30',2:'black!50'}. Rhombus of type a have color fill_color[a]. If tuple (i,j) is in fill_color, then fill_color[(i,j)] gives the color of the rhombus at position (i,j).

  • extra_code_before – string (default: '')

  • extra_code_after – string (default: '')

OUTPUT:

TikzPicture

EXAMPLES:

sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((.34, .72), 0)
sage: tikz = c.rectangular_subword_discrete_plane_tikz(((0,3),(0,4)))
sage: tikz.pdf()    # not tested

A workaround using a convention based on the ordering of the normal vector was found to fix the overlaps of rhombus. I should understand and clean this hack some day:

sage: c = dSturmianConfiguration((.72, .34), 0)
sage: tikz = c.rectangular_subword_discrete_plane_tikz(((0,3),(0,4)))
sage: tikz.pdf()    # not tested
rectangular_subword_matrix(window)

Return the rectangular subword appearing in the given rectangular window (as a matrix).

INPUT:

  • window – tuple of 2-tuples (start, stop)

OUTPUT:

matrix

EXAMPLES:

sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((.34, .72), 0)
sage: c.rectangular_subword_matrix(((0,3),(0,4)))
[0 1 2]
[1 2 0]
[2 0 1]
[0 1 2]
rectangular_subword_tikz(window, node_format=None, extra_code_after='')

Return the rectangular subword appearing in the given rectangular window (as a TikzPicture).

INPUT:

  • window – tuple of 2-tuples (start, stop)

  • node_format – function or None, a function giving the format for the matrix node at coordinate (i,j) like lambda i,j:r"{{\color{{black!60}}\symb{{{}}}}}". If None, it gets replaced by a function which put red at positions \((0,...,0)\) and \(-e_i\) and black elsewhere.

  • extra_code_after – string (default: '')

OUTPUT:

TikzPicture

EXAMPLES:

sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((.34, .72), 0)
sage: tikz = c.rectangular_subword_tikz(((0,3),(0,4)))
sage: tikz.pdf()    # not tested
rectangular_subwords(sizes, window)

Return the list of rectangular subword appearing in the configuration.

INPUT:

  • sizes – tuple of integers

  • window – tuple of 2-tuples

OUTPUT:

list of euclidean coordinate tables

EXAMPLES:

sage: z = polygen(QQ, 'z')
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((phi^-1, sqrt(2)), 0)
sage: c.rectangular_subwords((2,3), ((0,30),(0,30)))
[[[1, 2, 3], [3, 1, 2]],
 [[2, 3, 1], [1, 2, 3]],
 [[3, 1, 3], [2, 3, 1]],
 [[1, 3, 1], [3, 1, 3]],
 [[3, 1, 2], [1, 3, 1]],
 [[1, 2, 3], [3, 1, 3]],
 [[2, 3, 2], [1, 3, 1]],
 [[3, 2, 3], [3, 1, 2]],
 [[3, 1, 3], [2, 3, 2]],
 [[1, 3, 1], [3, 2, 3]],
 [[3, 1, 3], [1, 3, 1]]]
rectangular_subwords_matrix(sizes, window)

Return the list of rectangular subword appearing under the form of matrices.

INPUT:

  • sizes – tuple of integers

  • window – tuple of 2-tuples

OUTPUT:

list of matrices

EXAMPLES:

sage: z = polygen(QQ, 'z')
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()

sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((phi^-1, sqrt(2)), 0)
sage: c.rectangular_subwords_matrix((2,3), ((0,30),(0,30)))
[
[3 2]  [1 3]  [3 1]  [1 3]  [2 1]  [3 3]  [2 1]  [3 2]  [3 2]  [1 3]
[2 1]  [3 2]  [1 3]  [3 1]  [1 3]  [2 1]  [3 3]  [2 1]  [1 3]  [3 2]
[1 3], [2 1], [3 2], [1 3], [3 1], [1 3], [2 1], [3 3], [3 2], [1 3],
<BLANKLINE>
[3 1]
[1 3]
[3 1]
]
sage: len(_)
11
slabbe.ddim_sturmian_configuration.matrix_to_tikz(M, node_format=None, boundary_dash_line=False, extra_code_after='')

Return the matrix as a nice TikzPicture.

INPUT:

  • M – matrix

  • node_format – format for the node or None. If None, it gets replaced by lambda i,j:r"{{\color{{black!60}}\symb{{{}}}}}"

  • boundary_dash_line – boolean (default: False)

  • extra_code_after – string (default: '')

OUTPUT:

TikzPicture

Note

The tikz code below comes from Sebastián Barbieri.

EXAMPLES:

sage: from slabbe.ddim_sturmian_configuration import matrix_to_tikz
sage: M = identity_matrix(4)
sage: matrix_to_tikz(M)
\documentclass[tikz]{standalone}
\newcommand{\symb}[1]{\mathtt{#1}}  % Symbol
\usetikzlibrary{matrix}
\usetikzlibrary{fit}
\begin{document}
\begin{tikzpicture}
[baseline=-\the\dimexpr\fontdimen22\textfont2\relax,ampersand replacement=\&]
  \matrix[matrix of math nodes,nodes={
       minimum size=1.2ex,text width=1.2ex,
       text height=1.2ex,inner sep=3pt,draw={gray!20},align=center,
...
4 lines not printed (790 characters in total).
...
};
\end{tikzpicture}
\end{document}
slabbe.ddim_sturmian_configuration.table_to_discrete_plane_tikz(table, fill_color=None, extra_code_before='', extra_code_after='', convention='increasing')

Return a discrete plane representation of the table over alphabet \(0\), \(1\) and \(2\).

INPUT:

  • table – list of list (cartesian-like coordinates) over alphabet \(0\), \(1\) and \(2\)

  • extra_code_before – string (default: '')

  • extra_code_after – string (default: '')

  • fill_color – dict (default: None), if None, it is replaced by {0:'black!10',1:'black!30',2:'black!50'}. Rhombus of type a have color fill_color[a]. If tuple (i,j) is in fill_color, then fill_color[(i,j)] gives the color of the rhombus at position (i,j).

  • convention – string, 'decreasing' or 'increasing', the convention for drawing the rhombus according to increasing or decreasing normal vectors

OUTPUT:

TikzPicture

EXAMPLES:

sage: from slabbe.ddim_sturmian_configuration import table_to_discrete_plane_tikz
sage: from slabbe import dSturmianConfiguration
sage: c = dSturmianConfiguration((.34, .72), 0)
sage: table = c.rectangular_subword(((0,3),(0,4)))
sage: table_to_discrete_plane_tikz(table)
\documentclass[tikz]{standalone}
\begin{document}
\begin{tikzpicture}
\draw[fill=black!10] (0.000000000000000, 0.000000000000000) -- (0.866025403784439, 0.500000000000000) -- (0.000000000000000, 1.00000000000000) -- (-0.866025403784439, 0.500000000000000) -- (0.000000000000000, 0.000000000000000);
\draw[fill=black!70] (0.000000000000000, 0.000000000000000) -- ++ (30:1.7mm) arc (30:150:1.7mm);
\node[label=90:0] at (0.000000000000000, 0.000000000000000) {};
\draw[fill=black!50] (0.000000000000000, 1.00000000000000) -- (0.866025403784439, 0.500000000000000) -- (0.866025403784439, 1.50000000000000) -- (0.000000000000000, 2.00000000000000) -- (0.000000000000000, 1.00000000000000);
...
28 lines not printed (4613 characters in total).
...
\node[label=90:0] at (1.73205080756888, 3.00000000000000) {};
\draw[fill=black!50] (1.73205080756888, 4.00000000000000) -- (2.59807621135332, 3.50000000000000) -- (2.59807621135332, 4.50000000000000) -- (1.73205080756888, 5.00000000000000) -- (1.73205080756888, 4.00000000000000);
\draw[fill=black!70] (1.73205080756888, 4.00000000000000) -- ++ (-30:1.7mm) arc (-30:90:1.7mm);
\node[label=30:2] at (1.73205080756888, 4.00000000000000) {};
\end{tikzpicture}
\end{document}