2d Substitutions

2d substitutions

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[0,1],[2,3]]
sage: B = [[4,5]]
sage: d = {0:A, 1:B}
sage: Substitution2d(d)
Substitution 2d: {0: [[0, 1], [2, 3]], 1: [[4, 5]]}
class slabbe.substitution_2d.Substitution2d(d)

Bases: object

INPUT:

  • d – dict, key -> value, where each value is a table such that table[x][y] refers to the tile at position (x,y) in cartesian coordinates (not in the matrix-like coordinates)

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[0,1],[2,3]]
sage: B = [[4,5]]
sage: d = {0:A, 1:B}
sage: s = Substitution2d(d)
sage: s
Substitution 2d: {0: [[0, 1], [2, 3]], 1: [[4, 5]]}
apply_matrix_transformation(M)

INPUT:

  • M – matrix in SL(2,Z)

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[0,1],[0,1]]
sage: B = [[1,0],[1,1]]
sage: d = {0:A, 1:B}
sage: s = Substitution2d(d)
sage: M = matrix(2, (1,1,0,1))
sage: s
Substitution 2d: {0: [[0, 1], [0, 1]], 1: [[1, 0], [1, 1]]}
sage: s.apply_matrix_transformation(M)
Substitution 2d: {0: [[0, None], [0, 1], [None, 1]], 1: [[1, None], [1, 0], [None, 1]]}
call_on_column(column, heights=None)

INPUT:

  • column – list

  • heights – None or list (default: None)

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[0,1],[2,3]]
sage: B = [[4],[5]]
sage: C = [[6,7,8]]
sage: d = {0:A, 1:B, 2:C}
sage: s = Substitution2d(d)
sage: s.call_on_column([0])
[[0, 1], [2, 3]]
sage: s.call_on_column([0,1])
[[0, 1, 4], [2, 3, 5]]
sage: s.call_on_column([0,1,1,0,0])
[[0, 1, 4, 4, 0, 1, 0, 1], [2, 3, 5, 5, 2, 3, 2, 3]]

It can compute the image of columns with None as entries:

sage: s.call_on_column([0,None], heights=[2,3])
[[0, 1, None, None, None], [2, 3, None, None, None]]
sage: s.call_on_column([0,None], heights=[2,2])
[[0, 1, None, None], [2, 3, None, None]]
sage: s.call_on_column([None], heights=[3])
[[None, None, None]]

TESTS:

sage: s.call_on_column([])
[]
sage: s.call_on_column([0,2])
Traceback (most recent call last):
...
ValueError: the image of 2 in the column (=[0, 2]) has width 1
but the image of another has width 2
call_on_row(row)

INPUT:

  • row – list

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[0,1],[2,3]]
sage: B = [[4,5]]
sage: C = [[6,7,8]]
sage: d = {0:A, 1:B, 2:C}
sage: s = Substitution2d(d)
sage: row = [0,1,1,0]
sage: s.call_on_row(row)
[[0, 1], [2, 3], [4, 5], [4, 5], [0, 1], [2, 3]]
sage: s.call_on_row([2])
[[6, 7, 8]]

TESTS:

sage: s.call_on_row([])
[]
sage: s.call_on_row([1,2])
Traceback (most recent call last):
...
ValueError: the image of the row contains columns of different height (={2, 3})
codomain_alphabet()

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[5,6],[7,8]]
sage: B = [[6,5],[9,8]]
sage: d = {0:A, 1:B}
sage: s = Substitution2d(d)
sage: s.codomain_alphabet()
{5, 6, 7, 8, 9}

Blank None are ignored:

sage: A = [[5,6],[7,8]]
sage: B = [[6,5],[9,None]]
sage: d = {0:A, 1:B}
sage: s = Substitution2d(d)
sage: s.codomain_alphabet()
{5, 6, 7, 8, 9}
desubstitute(tiles, function=None)

Return the Wang tile set obtained from the desubstitution of the given Wang tile set.

INPUT:

  • tiles – list of Wang tiles, each tile being a 4-tuple of (east, north, west, south) colors

  • fn – a function (default: None) to apply to the new colors which are tuple of previous colors

OUTPUT:

dict, key -> tile

domain_alphabet()

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[5,6],[7,8]]
sage: B = [[6,5],[9,8]]
sage: d = {0:A, 1:B}
sage: s = Substitution2d(d)
sage: s.domain_alphabet()
{0, 1}
fixed_point_tikz(seed, niterations=3)

Return a tikz representation of a fixed point defined by the give seed. In the image, rectangular boxes indicate the i-th image of each seed.

INPUT:

  • seed – 2x2 matrix

  • niterations – (default:3), number of iterations

OUTPUT

tikz picture

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[1,1],[1,1]]
sage: B = [[0,0]]
sage: d = {0:A, 1:B}
sage: s = Substitution2d(d)
sage: tikz = s.fixed_point_tikz([[0,0],[0,0]])
sage: _ = tikz.pdf()                              # not tested

The substitution s is not prolongable, so the boxes in the image obtained from the square of s might better:

sage: s2 = s*s
sage: tikz = s2.fixed_point_tikz([[0,0],[0,0]])
sage: _ = tikz.pdf()                              # not tested
classmethod from_1d_column_substitution(s)

INPUT:

  • s – dict

EXAMPLES:

sage: from slabbe import Substitution2d
sage: fibo = {0:[0,1], 1:[0]}
sage: s = Substitution2d.from_1d_column_substitution(fibo)
sage: s
Substitution 2d: {0: [[0, 1]], 1: [[0]]}
classmethod from_1d_row_substitution(s)

INPUT:

  • s – dict

EXAMPLES:

sage: from slabbe import Substitution2d
sage: fibo = {0:[0,1], 1:[0]}
sage: s = Substitution2d.from_1d_row_substitution(fibo)
sage: s
Substitution 2d: {0: [[0], [1]], 1: [[0]]}
classmethod from_permutation(d)

INPUT:

  • d – dict

EXAMPLES:

sage: from slabbe import Substitution2d
sage: s = Substitution2d.from_permutation({4:0, 5:1})
sage: s
Substitution 2d: {4: [[0]], 5: [[1]]}
sage: A = [[5,6],[7,8]]
sage: B = [[6,5],[9,8]]
sage: t = Substitution2d({0:A, 1:B})
sage: t
Substitution 2d: {0: [[5, 6], [7, 8]], 1: [[6, 5], [9, 8]]}
sage: t*s
Substitution 2d: {4: [[5, 6], [7, 8]], 5: [[6, 5], [9, 8]]}
sage: u = Substitution2d.from_permutation({5:0, 6:1, 7:2, 8:3, 9:4})
sage: u
Substitution 2d: {5: [[0]], 6: [[1]], 7: [[2]], 8: [[3]], 9: [[4]]}
sage: u * t
Substitution 2d: {0: [[0, 1], [2, 3]], 1: [[1, 0], [4, 3]]}
incidence_matrix()

Return the incidence matrix of self.

Some default ordering (sorted) is used for the domain and codomain alphabet.

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[0,1],[2,3]]
sage: B = [[4,5]]
sage: C = [[6,7,8]]
sage: d = {0:A, 1:B, 2:C}
sage: s = Substitution2d(d)
sage: s.incidence_matrix()
[1 0 0]
[1 0 0]
[1 0 0]
[1 0 0]
[0 1 0]
[0 1 0]
[0 0 1]
[0 0 1]
[0 0 1]
inverse()

Return the inverse of self (when self is a permutation).

EXAMPLES:

sage: from slabbe import Substitution2d
sage: d = {0:7, 1:8}
sage: s = Substitution2d.from_permutation(d)
sage: s
Substitution 2d: {0: [[7]], 1: [[8]]}
sage: s.inverse()
Substitution 2d: {7: [[0]], 8: [[1]]}

TESTS:

sage: s = Substitution2d({8: [[1]], 7: [[0,1]]})
sage: s.inverse()
Traceback (most recent call last):
...
ValueError: self must be a permutation but image of 7 is [[0, 1]]
letter_to_letter_dict(pos=0, 0)

Return the inverse of self (when self is a permutation).

INPUT:

  • pos – tuple (default:(0,0)), tuple of two integers

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[0,1],[2,3]]
sage: B = [[4,5]]
sage: s = Substitution2d({0:A, 1:B})
sage: s
Substitution 2d: {0: [[0, 1], [2, 3]], 1: [[4, 5]]}
sage: s.letter_to_letter_dict(pos=(0,0))
{0: 0, 1: 4}
lines_alphabet(direction='horizontal')

Return the possible alphabets on lines, i.e., the possible alphabet of letters that we see on a given line.

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[0,1],[0,1]]
sage: B = [[1,0],[1,1]]
sage: d = {0:A, 1:B}
sage: s = Substitution2d(d)
sage: sorted(s.lines_alphabet())
[(0,), (0, 1), (1,)]
sage: sorted(s.lines_alphabet(direction='vertical'))
[(0, 1), (1,)]
list_2x2_factors(F=None)

Return the list of 2x2 factors in the associated substitutive shift. If a list of factors F is given, it restrict to the factors inside the image of F.

INPUT:

  • self – expansive and primitive 2d substitution

  • F – list of factors in the domain or None, if given the output is restricted to the factors in F

OUTPUT:

list of tables

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[0,1],[0,1]]
sage: B = [[1,0],[1,1]]
sage: d = {0:A, 1:B}
sage: s = Substitution2d(d)
sage: sorted(s.list_2x2_factors())
[[[0, 0], [1, 0]],
 [[0, 1], [0, 1]],
 [[0, 1], [1, 0]],
 [[0, 1], [1, 1]],
 [[1, 0], [0, 0]],
 [[1, 0], [0, 1]],
 [[1, 0], [1, 0]],
 [[1, 0], [1, 1]],
 [[1, 1], [0, 0]],
 [[1, 1], [0, 1]],
 [[1, 1], [1, 0]],
 [[1, 1], [1, 1]]]

Restricting to the images of some factors:

sage: sorted(s.list_2x2_factors([A]))
[[[0, 1], [0, 1]], [[1, 0], [1, 1]], [[1, 1], [1, 0]], [[1, 1], [1, 1]]]
sage: sorted(s.list_2x2_factors([B]))
[[[0, 0], [1, 0]],
 [[0, 1], [0, 1]],
 [[0, 1], [1, 0]],
 [[0, 1], [1, 1]],
 [[1, 0], [0, 1]],
 [[1, 0], [1, 1]],
 [[1, 1], [1, 0]]]
sage: sorted(s.list_2x2_factors([A,B]))
[[[0, 0], [1, 0]],
 [[0, 1], [0, 1]],
 [[0, 1], [1, 0]],
 [[0, 1], [1, 1]],
 [[1, 0], [0, 1]],
 [[1, 0], [1, 1]],
 [[1, 1], [1, 0]],
 [[1, 1], [1, 1]]]
sage: s.list_2x2_factors([])
[]
list_dominoes(direction)

Return the list of 1x2 or 2x1 factors in the language of the associated substitutive shift.

INPUT:

  • self – expansive and primitive 2d substitution

  • direction – string, 'horizontal' or 'vertical'

OUTPUT:

list of tables

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[0,1],[0,1]]
sage: B = [[1,0],[1,1]]
sage: d = {0:A, 1:B}
sage: s = Substitution2d(d)
sage: sorted(s.list_dominoes(direction='horizontal'))
[(0, 0), (0, 1), (1, 0), (1, 1)]
sage: sorted(s.list_dominoes(direction='vertical'))
[(0, 0), (0, 1), (1, 0), (1, 1)]
sage: A = [[3]]
sage: B = [[3],[2]]
sage: C = [[3,1]]
sage: D = [[3,1],[2,0]]
sage: d = {0:A, 1:B, 2:C, 3:D}
sage: s = Substitution2d(d)
sage: sorted(s.list_dominoes(direction='horizontal'))
[(0, 1), (1, 0), (1, 1), (2, 3), (3, 2), (3, 3)]
sage: sorted(s.list_dominoes(direction='vertical'))
[(0, 2), (1, 3), (2, 0), (2, 2), (3, 1), (3, 3)]
prolongable_origins()

Deprecated: Use prolongable_seeds_graph() instead. See trac ticket #123456 for details.

prolongable_seeds_graph()

Return the directed graph of 2x2 factors where (u,v) is an edge if v is the seed at the origin of the image of u under self.

OUTPUT:

list of tuple (2x2 matrix, integer)

EXAMPLES:

sage: d = {0: [[17]],
....:  1: [[16]],
....:  2: [[15], [11]],
....:  3: [[13], [9]],
....:  4: [[17], [8]],
....:  5: [[16], [8]],
....:  6: [[15], [8]],
....:  7: [[14], [8]],
....:  8: [[14, 6]],
....:  9: [[17, 3]],
....:  10: [[16, 3]],
....:  11: [[14, 2]],
....:  12: [[15, 7], [11, 1]],
....:  13: [[14, 6], [11, 1]],
....:  14: [[13, 7], [9, 1]],
....:  15: [[12, 6], [9, 1]],
....:  16: [[18, 5], [10, 1]],
....:  17: [[13, 4], [9, 1]],
....:  18: [[14, 2], [8, 0]]}
sage: from slabbe import Substitution2d
sage: omega = Substitution2d(d)
sage: G = omega.prolongable_seeds_graph()
sage: G
Looped digraph on 50 vertices
prolongable_seeds_list()

Return the list of seed which are prolongable for some power of self.

OUTPUT:

list of cycles

EXAMPLES:

sage: d = {0: [[17]],
....:  1: [[16]],
....:  2: [[15], [11]],
....:  3: [[13], [9]],
....:  4: [[17], [8]],
....:  5: [[16], [8]],
....:  6: [[15], [8]],
....:  7: [[14], [8]],
....:  8: [[14, 6]],
....:  9: [[17, 3]],
....:  10: [[16, 3]],
....:  11: [[14, 2]],
....:  12: [[15, 7], [11, 1]],
....:  13: [[14, 6], [11, 1]],
....:  14: [[13, 7], [9, 1]],
....:  15: [[12, 6], [9, 1]],
....:  16: [[18, 5], [10, 1]],
....:  17: [[13, 4], [9, 1]],
....:  18: [[14, 2], [8, 0]]}
sage: from slabbe import Substitution2d
sage: omega = Substitution2d(d)
sage: omega.prolongable_seeds_list()
[[
 [ 9 14]  [17 13]
 [ 1  6], [16 15]
 ],
 [
 [ 9 14]  [17 13]
 [ 8 16], [ 6  5]
 ],
 [
 [10 12]  [16 15]
 [ 9 14], [ 3  7]
 ],
 [
 [10 14]  [16 13]
 [11 17], [ 2  4]
 ]]
relabel_domain(other)

Return a permutation p such that self*p == other, if it exists.

INPUT:

  • other – substitution 2d

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[0,1],[0,1]]
sage: B = [[1,0],[1,1]]
sage: s = Substitution2d({0:A, 1:B})
sage: t = Substitution2d({7:A, 8:B})
sage: s.relabel_domain(t)
Substitution 2d: {7: [[0]], 8: [[1]]}

TESTS:

sage: s = Substitution2d({0:A, 1:B})
sage: s.relabel_domain(s)
Substitution 2d: {0: [[0]], 1: [[1]]}
sage: s = Substitution2d({0:A, 1:B})
sage: t = Substitution2d({7:A, 8:B, 9:[[4]]})
sage: t.relabel_domain(s)
Traceback (most recent call last):
...
ValueError: image of letter 9 is [[4]] and is not in other
sage: s.relabel_domain(t)
Traceback (most recent call last):
...
AssertionError: problem: self * p == other not satisfied
reversal()

Return the reversal of self.

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[1,2],[3,4]]
sage: B = [[5,6],[7,8]]
sage: d = {0:A, 1:B}
sage: s = Substitution2d(d)
sage: s.reversal()
Substitution 2d: {0: [[4, 3], [2, 1]], 1: [[8, 7], [6, 5]]}
stone_inflation_shapes()

Return a dictionary of letters of the domain alphabet associated to pairs (width, height) describing the rectangular shape associated to the given letter.

Those rectangular shapes are such that the 2d substitution can be seen as stone inflation, see section 5.6 of [BG13].

INPUT:

  • self – expansive and primitive 2d substitution

OUTPUT:

  • horizontal expansion in X-axis

  • vertical expansion in Y-axis

  • dictionary of letter:(width, height)

EXAMPLES:

sage: from slabbe import Substitution2d
sage: A = [[3]]
sage: B = [[3],[2]]
sage: C = [[3,1]]
sage: D = [[3,1],[2,0]]
sage: d = {0:A, 1:B, 2:C, 3:D}
sage: s = Substitution2d(d)
sage: rootX, rootY, stone_shapes = s.stone_inflation_shapes()
sage: stone_shapes
{0: (1, 1), 1: (rootX, 1), 2: (1, rootY), 3: (rootX, rootY)}
sage: {a:(w.n(),h.n()) for a,(w,h) in stone_shapes.items()}
{0: (1.00000000000000, 1.00000000000000),
 1: (1.61803398874989, 1.00000000000000),
 2: (1.00000000000000, 1.61803398874989),
 3: (1.61803398874989, 1.61803398874989)}
wang_tikz(domain_tiles, codomain_tiles, domain_color=None, codomain_color=None, domain_color_by_id=None, codomain_color_by_id=None, size=1, scale=1, font='\\\\normalsize', rotate=None, label_shift=0.2, id=True, edges=True, ncolumns=4, direction='right', extra_space=1)

Return the tikz code showing what the substitution A->B* does on Wang tiles.

INPUT:

  • domain_tiles – tiles of the domain

  • codomain_tiles – tiles of the codomain

  • domain_color – dict (default: None) from tile values -> tikz colors

  • codomain_color – dict (default: None) from tile values -> tikz colors

  • domain_color_by_id – dict (default: None) from tile values -> tikz colors

  • codomain_color_by_id – dict (default: None) from tile values -> tikz colors

  • size – number (default: 1), size of the tile

  • scale – number (default: 1), scale of tikzpicture

  • font – string (default: r'\normalsize'

  • rotate – list or None (default:None) list of four angles in degrees like (0,0,0,0), the rotation angle to apply to each label of Wang tiles. If None, it performs a 90 degres rotation for left and right labels taking more than one character.

  • label_shift – number (default: .2) translation distance of the label from the edge

  • id – boolean (default: True), presence of the tile id

  • ncolumns – integer (default: 4)

  • edges – bool (default: True)

  • direction – string (default: 'right') or 'down'

  • extra_space – number (default: 1), space between the tile and its image

OUTPUT:

dict, key -> tile

EXAMPLES:

sage: from slabbe import WangTileSet, Substitution2d
sage: A = [[0,1,2],[1,0,0]]
sage: B = [[0,1,2]]
sage: d = {4:A, 5:B}
sage: s = Substitution2d(d)
sage: codomain_tiles = [(0,3,1,4), (1,4,0,3), (5,6,7,8)]
sage: W = WangTileSet(codomain_tiles)
sage: fn = lambda colors:''.join(map(str, colors))
sage: domain_tiles = W.desubstitute(s, fn)
sage: tikz = s.wang_tikz(domain_tiles, codomain_tiles, rotate=(90,0,90,0))
sage: _ = tikz.pdf(view=False)      # long time

Color tiles by their id:

sage: domain_color_by_id = {4:'red', 5:'blue'}
sage: codomain_color_by_id = {0:'orange', 1:'green', 2:'yellow'}
sage: tikz = s.wang_tikz(domain_tiles, codomain_tiles,
....: domain_color_by_id=domain_color_by_id,
....: codomain_color_by_id=codomain_color_by_id)
sage: _ = tikz.pdf(view=False)      # long time

Applying a transformation matrix:

sage: M = matrix(2, [1,1,0,1])
sage: sM = s.apply_matrix_transformation(M)
sage: tikz = sM.wang_tikz(domain_tiles, codomain_tiles)
sage: _ = tikz.pdf(view=False)      # long time

Down direction:

sage: tikz = s.wang_tikz(domain_tiles, codomain_tiles,
....:                      direction='down')
sage: _ = tikz.pdf(view=False)      # long time
wang_tiles_codomain_tikz(codomain_tiles, color=None, size=1, scale=1, font='\\\\normalsize', rotate=None, id=True, label=True, label_shift=0.2, edges=True, ncolumns=4, direction='right')

Return the tikz code of the image of the letters as a table of tikz tilings.

INPUT:

  • domain_tiles – tiles of the domain

  • codomain_tiles – tiles of the codomain

  • domain_color – dict (default: None) from tile values -> tikz colors

  • codomain_color – dict (default: None) from tile values -> tikz colors

  • size – number (default: 1), size of the tile

  • scale – number (default: 1), scale of tikzpicture

  • font – string (default: r'\normalsize'

  • rotate – list or None (default:None) list of four angles in degrees like (0,0,0,0), the rotation angle to apply to each label of Wang tiles. If None, it performs a 90 degres rotation for left and right labels taking more than one character.

  • id – boolean (default: True), presence of the tile id

  • label – boolean (default: True)

  • label_shift – number (default: .2) translation distance of the label from the edge

  • edges – bool (default: True)

  • ncolumns – integer (default: 4)

OUTPUT:

tikzpicture

EXAMPLES:

sage: from slabbe import WangTileSet, Substitution2d
sage: A = [[0,1,2],[1,0,0]]
sage: B = [[0,1,2]]
sage: d = {4:A, 5:B}
sage: s = Substitution2d(d)
sage: codomain_tiles = [(0,3,1,4), (1,4,0,3), (5,6,7,8)]
sage: W = WangTileSet(codomain_tiles)
sage: t = s.wang_tiles_codomain_tikz(W)
sage: _ = t.pdf(view=False)
slabbe.substitution_2d.set_of_factors(table, shape, avoid_border=0)

Return the set of factors of given shape in the table.

INPUT

  • table – list of lists

  • shape – list, list of coordinates

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

    to avoid during the computation

OUTPUT:

set of tuple of integers

EXAMPLES:

sage: from slabbe.substitution_2d import set_of_factors
sage: table = [[0,1,2], [3,4,5], [6,7,8]]
sage: set_of_factors(table, shape=[(0,0), (1,0), (0,1), (1,1)])
{(0, 3, 1, 4), (1, 4, 2, 5), (3, 6, 4, 7), (4, 7, 5, 8)}