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: s = Substitution2d(d)
sage: s
Substitution 2d: {0: [[0, 1], [2, 3]], 1: [[4, 5]]}

Notice here that we are using Cartesian-like coordinates as opposed to matrix-like coordinates:

sage: image = s([[0]])
sage: image
[[0, 1], [2, 3]]
sage: x = 1
sage: y = 0
sage: image[x][y]
2

Computing the image of a 2-dimensional word:

sage: A = [[0,1],[2,3]]
sage: B = [[4,5],[6,7]]
sage: C = [[8,9]]
sage: d = {0:A, 1:B, 2:C}
sage: s = Substitution2d(d)
sage: table = [[0,1],[1,1]]
sage: s(table)
[[0, 1, 4, 5], [2, 3, 6, 7], [4, 5, 4, 5], [6, 7, 6, 7]]
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]]}

Computing the iterative images of a letter under a 2-dimensional substitution:

sage: A = [[0,1],[2,0]]
sage: B = [[2,1],[2,0]]
sage: C = [[1,2],[1,1]]
sage: d = {0:A, 1:B, 2:C}
sage: s = Substitution2d(d)
sage: s([[0]])
[[0, 1], [2, 0]]
sage: s([[0]], 2)
[[0, 1, 2, 1], [2, 0, 2, 0], [1, 2, 0, 1], [1, 1, 2, 0]]
sage: s([[0]], 3)
[[0, 1, 2, 1, 1, 2, 2, 1],
[2, 0, 2, 0, 1, 1, 2, 0],
[1, 2, 0, 1, 1, 2, 0, 1],
[1, 1, 2, 0, 1, 1, 2, 0],
[2, 1, 1, 2, 0, 1, 2, 1],
[2, 0, 1, 1, 2, 0, 2, 0],
[2, 1, 2, 1, 1, 2, 0, 1],
[2, 0, 2, 0, 1, 1, 2, 0]]

Computing the product of two 2-dimensional substitutions:

sage: t = s*s

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_column_substitutions(s_row, s_column)

INPUT:

  • s_row – dict

  • s_column – dict

EXAMPLES:

sage: from slabbe import Substitution2d
sage: fibo = {0:[0,1], 1:[0]}
sage: s = Substitution2d.from_1d_row_column_substitutions(fibo, fibo)
sage: s
Substitution 2d: {0: [[0, 1], [2, 3]], 1: [[0], [2]], 2: [[0, 1]], 3: [[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]]}
has_unique_self_similar_subshift(verbose=False)

Return whether there is a unique self-similar subshift associated to this substitution.

INPUT:

  • verbose – bool (default:False), if True prints information why there is no unique self-similar subshift

OUTPUT:

boolean

EXAMPLES:

sage: from slabbe import Substitution2d
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: omega = Substitution2d(d)
sage: omega.has_unique_self_similar_subshift()
False
horizontal_structure_substitution()

Return the horizontal substitution obtained after quotient by the equivalence relation defined by letters appearing in the same column.

INPUT:

  • self – expansive and primitive 2d substitution

OUTPUT:

  • substitution \(B\to B^*\)

  • dictionary \(A\to B\)

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: s.horizontal_structure_substitution()
(WordMorphism: 2->3, 3->32, {0: 2, 1: 3, 2: 2, 3: 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)]
periodic_horizontal_domino_seeds_graph(clean_sources=False)

Return the directed graph of horizontal dominoes where (u,v) is an edge if the domino v appears in the image of the domino u under self on the separation between the image of the two letters of the domino.

INPUT:

  • clean_sources – bool (default:False)

OUTPUT:

graph

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.periodic_horizontal_domino_seeds_graph()
Looped digraph on 79 vertices
sage: omega.periodic_horizontal_domino_seeds_graph(clean_sources=True)
Looped digraph on 51 vertices
periodic_vertical_domino_seeds_graph(clean_sources=False)

Return the directed graph of vertical dominoes where (u,v) is an edge if the domino v appears in the image of the domino u under self on the separation between the image of the two letters of the domino.

INPUT:

  • clean_sources – bool (default:False)

OUTPUT:

graph

EXAMPLES:

sage: from slabbe import Substitution2d
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: omega = Substitution2d(d)
sage: omega.periodic_vertical_domino_seeds_graph()
Looped digraph on 93 vertices
sage: omega.periodic_vertical_domino_seeds_graph(clean_sources=True)
Looped digraph on 56 vertices
prolongable_seeds_graph(clean_sources=False)

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.

INPUT:

  • clean_sources – bool (default:False)

OUTPUT:

graph

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_graph()
Looped digraph on 1344 vertices
sage: omega.prolongable_seeds_graph(clean_sources=True)
Looped digraph on 256 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)

Here there are many seeds:

sage: seeds = flatten(omega.prolongable_seeds_list())
sage: len(seeds)
256

If all seeds belong to the language of the substitution (computed from the letters), then there exists a unique subshift which is self-similar with respect to the substitution. In this example, it is not true:

sage: seeds_as_table = [[list(col[::-1]) for col in m.columns()] for m in seeds]
sage: F = omega.list_2x2_factors()
sage: all(seed in F for seed in seeds_as_table)
False

Indeed, only 8 of the 256 seeds belong to the language of the substitution:

sage: [seed for seed in seeds_as_table if seed in F]
[[[1, 9], [6, 14]],
 [[16, 17], [15, 13]],
 [[8, 9], [16, 14]],
 [[6, 17], [5, 13]],
 [[9, 10], [14, 12]],
 [[3, 16], [7, 15]],
 [[11, 10], [17, 14]],
 [[2, 16], [4, 13]]]

This means that all the other 248 seeds give rise to configurations which are fixed by the substitution but are not uniformly recurrent. In particular, if a subshift is self-similar with respect to that substitution, we can not conclude that it is minimal.

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]]}
split_letters_randomly(n_copies)

Return a substitution 2d obtained by spliting letters.

INPUT:

  • n_copies – dict, letters to integers indicating the number of copies of each letter

OUTPUT

Substitution 2d

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: n_copies = {0:2, 1:1}
sage: s.split_letters_randomly(n_copies)  # random
Substitution 2d: {0: [[2, 2], [2, 2]], 1: [[2, 2], [2, 2]], 2: [[1, 0]]}
sage: n_copies = {0:2,1:3}
sage: s.split_letters_randomly(n_copies)  # random
Substitution 2d: {0: [[3, 3], [4, 3]], 1: [[4, 2], [2, 2]], 
2: [[0, 0]], 3: [[0, 1]], 4: [[1, 0]]}
sage: from slabbe import Substitution2d
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS
sage: fibo = {0:[0,1], 1:[0]}
sage: s = Substitution2d.from_1d_row_column_substitutions(fibo, fibo)
sage: n_copies = {0:2,1:1,2:1,3:1}
sage: t = s.split_letters_randomly(n_copies)
sage: ifs = GIFS.from_two_dimensional_substitution(t)
sage: _ = ifs.galois_conjugate().plot(n_iterations=9)
sage: n_copies = {0:2,1:2,2:2,3:2}
sage: t = s.split_letters_randomly(n_copies)
sage: ifs = GIFS.from_two_dimensional_substitution(t)
sage: _ = ifs.galois_conjugate().plot(n_iterations=9)
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)}
vertical_structure_substitution()

Return the vertical substitution obtained after quotient by the equivalence relation defined by letters appearing in the same row.

INPUT:

  • self – expansive and primitive 2d substitution

OUTPUT:

  • substitution \(B\to B^*\)

  • dictionary \(A\to B\)

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: s.vertical_structure_substitution()
(WordMorphism: 1->3, 3->31, {0: 1, 1: 1, 2: 3, 3: 3})
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)}