# 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 (=set([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}

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: {8: [[3]], 9: [[4]], 5: [[0]], 6: [[1]], 7: [[2]]}
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: {8: [[1]], 7: [[0]]}


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: s.list_2x2_factors()
[[[0, 1], [0, 1]],
[[1, 0], [1, 1]],
[[1, 1], [1, 0]],
[[1, 1], [1, 1]],
[[1, 1], [0, 1]],
[[1, 1], [0, 0]],
[[0, 1], [1, 1]],
[[1, 0], [0, 1]],
[[0, 0], [1, 0]],
[[0, 1], [1, 0]],
[[1, 0], [1, 0]],
[[1, 0], [0, 0]]]


Restricting to the images of some factors:

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

prolongable_origins()
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: {8: [[1]], 7: [[0]]}


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]]}

wang_tikz(domain_tiles, codomain_tiles, domain_color=None, codomain_color=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
• 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


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)}