Structure substitutive des pavages apériodiques de Jeandel-Rao

Sébastien Labbé, version 1 of arXiv:1808.07768, August 2018

Sébastien Labbé, version 2 of arXiv:1808.07768, April 2019

Sébastien Labbé, first online version in DCG, November 2019. We did changes to make the code work in Python 3 which is used in Sage starting from version 9.0.

Références:

• A self-similar aperiodic set of 19 Wang tiles, Geometriae Dedicata, (2018)
  doi:10.1007/s10711-018-0384-8, arXiv:1802.03265

• Substitutive structure of Jeandel-Rao aperiodic tilings, August 2018, 38 p. arXiv:1808.07768

Prerequisites

Sage version 8.7 or above should work:

version()

'SageMath version 9.0.beta6, Release Date: 2019-11-18'

The installation of the optional Sage package slabbe is a prerequisite. Remove the dash sign (#) and evaluate the following cell to install slabbe optional package.

The installation of graphviz and of the optional Sage package dot2tex is a prerequisite to construct the graphs at the end of the notebook.

Finally, I am using rise for the presentation and tikzmagic in Jupyter cells.

#!sage -pip install slabbe>=0.4.4
#!sage -pip install dot2tex
#!sage -pip install rise
#!sage -pip install git+git://github.com/robjstan/tikzmagic.git

Choosing a solver

The time it takes to evaluate all cells of this notebook depend on the chosen available solver.

Solver	Type	Time to run this notebook
dancing_links	Exact cover solver	about 2 minutes
Gurobi	MILP solver	about 4 minutes
Glucose	SAT solver	about 30 minutes (estimated)

The above timing were computed on a 2019 computer with 8 available cpus.

Dancing links is an algorithm proposed by D. Knuth to solve the Exact Cover Problem and is available in plain Sage.

Gurobi is a MILP solver. It is a proprietary software, but it is free for researchers and students. See this tutorial to make Gurobi available through Sage.

Glucose is a SAT solver developped at LaBRI (Bordeaux). It can be installed in sage>=8.7.beta0 easily:

sage -i glucose

from sage.misc.package import is_package_installed
from sage.doctest.external import has_gurobi
if has_gurobi():
    solver = 'gurobi'
elif is_package_installed('glucose'):
    solver = 'glucose'
else:
    solver = 'dancing_links'
solver = 'dancing_links' # more time efficient
print("We are using solver = '{}'".format(solver))

We are using solver = 'dancing_links'

Setup

Colors setup:

from collections import defaultdict
color = defaultdict(lambda : 'white')
color.update({0:'white', 1:'red', 2:'cyan', 3:'green', 4:'lightgray'})
color.update({str(k):v for k,v in color.items()})

Loading modules from slabbe and tikzmagic.

If needed, here is the command to install tikzmagic:

sage -pip install git+git://github.com/robjstan/tikzmagic.git

from slabbe import WangTileSet, Substitution2d
import tikzmagic

Latex macros:

$\newcommand{T}{{\mathcal{T}}}$ $\newcommand{U}{{\mathcal{U}}}$ $\newcommand{N}{{\mathbb{N}}}$ $\newcommand{Z}{{\mathbb{Z}}}$ $\newcommand{R}{{\mathbb{R}}}$

Definition of Jeandel-Rao Tiles $\mathcal{T}_0$

tiles = [(2,4,2,1), (2,2,2,0), (1,1,3,1), (1,2,3,2), (3,1,3,3), (0,1,3,1), (0,0,0,1), (3,1,0,2), (0,2,1,2), (1,2,1,4), (3,3,1,2)]
tiles = [[str(a) for a in t] for t in tiles]
T0 = WangTileSet(tiles)
T0.tikz(font=r'\small', size=1.2, ncolumns=11, color=color)

Let $$\Omega_0=\Omega_{\T_0}=\{w:\Z\times\Z\to\T_0\mid w \text{ is a valid Wang tiling}\}$$ be the set of tilings made with the 11 Jeandel-Rao tiles.

%time solution = T0.solver(30,15).solve(solver='glucose')

CPU times: user 248 ms, sys: 4 ms, total: 252 ms
Wall time: 478 ms

solution.tikz(color=color)

The substitutive structure of Jeandel-Rao tilings $\Omega_0$ looks like this:

%tikz -i subs-struct.tikz --no-wrap

The current Jupyter notebook computes

• the Wang tile sets $\T_i$ for each $i\in\{1,\dots,12\}$
• the Wang shifts $\Omega_i=\Omega_{\T_i}=\{w:\Z\times\Z\to\T_i\mid w \text{ is a valid Wang tiling}\}$ for each $i\in\{1,\dots,12\}$
• the 2-dimensional morphisms $\omega_i:\Omega_{i+1}\to\Omega_i$ for each $i\in\{1,\dots,12\}\setminus\{4,5\}$
• the embedding $\pi:\Omega_5\to\Omega_4$
• the topological conjugacy $\eta:\Omega_6\to\Omega_5$

Algorithm.

INPUTS: $\T$ is a Wang tile set; $i\in\{1,2\}$ is a direction $e_i$; $r\in\N$ is some radius.

FindMarkers($\mathcal{T}$, $i$, $r$)

• $j\gets 3-i$
• $D_j \gets \left\{(u,v)\in\T^2\mid u\odot^jv\text{ admits a surrounding or radius } r\text{ in }\Omega_\T \right\}$
• $U \gets $UnionFindDataStructure$(\T)$
• For All $(u,v) \in D_j$
  • Union$(u, v)$ (Merge $u$ and $v$ in the data structure $U$)
• EndFor
• $D_i \gets \left\{(u,v)\in\T^2\mid u\odot^iv \text{ admits a surrounding or radius } r \text{ in }\Omega_\T\right\}$

• Return ${S \in\textbf{Subsets}(U) \mid

                   \left(S\times S\right) \cap D_i=\varnothing\}$

• The output contains zero, one or more subsets of markers in the direction $i$.

Computing $\mathcal{T}_1$

T0.tikz(font=r'\small', ncolumns=11, size=1.2, color=color)

%time T0.find_markers(i=2, radius=1, solver=solver) # 229ms with dancing_links, 32s with Glucose, 1.4s with Gurobi

CPU times: user 260 ms, sys: 0 ns, total: 260 ms
Wall time: 258 ms

[[0, 1]]

M0 = [0,1]
T1,omega0 = T0.find_substitution(M=M0, i=2, side='left', solver=solver)

show(omega0)

$$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{array}{llllllll} 0\mapsto \left(2\right) ,& 1\mapsto \left(3\right) ,& 2\mapsto \left(4\right) ,& 3\mapsto \left(5\right) ,& 4\mapsto \left(6\right) ,& 5\mapsto \left(7\right) ,& 6\mapsto \left(8\right) ,& 7\mapsto \left(10\right) ,\\ 8\mapsto \left(\begin{array}{r} 9 \\ 0 \end{array}\right) ,& 9\mapsto \left(\begin{array}{r} 3 \\ 1 \end{array}\right) ,& 10\mapsto \left(\begin{array}{r} 7 \\ 1 \end{array}\right) ,& 11\mapsto \left(\begin{array}{r} 8 \\ 1 \end{array}\right) ,& 12\mapsto \left(\begin{array}{r} 10 \\ 1 \end{array}\right) . \end{array}$$

T1.tikz(font=r'\small', size=1.2, ncolumns=13)

Computing $\mathcal{T}_2$

T1.tikz(font=r'\small', ncolumns=20, size=1.2)

%time T1.find_markers(i=2, radius=1, solver=solver) #385ms with dancing_links, 46s with Glucose, 2s with Gurobi

CPU times: user 416 ms, sys: 0 ns, total: 416 ms
Wall time: 413 ms

[[8, 9, 10, 11, 12]]

M1 = [8, 9, 10, 11, 12]
T2,omega1 = T1.find_substitution(M=M1, i=2, side='left', solver=solver)

show(omega1)

$$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{array}{llllllll} 0\mapsto \left(0\right) ,& 1\mapsto \left(1\right) ,& 2\mapsto \left(2\right) ,& 3\mapsto \left(3\right) ,& 4\mapsto \left(4\right) ,& 5\mapsto \left(5\right) ,& 6\mapsto \left(6\right) ,& 7\mapsto \left(7\right) ,\\ 8\mapsto \left(\begin{array}{r} 1 \\ 8 \end{array}\right) ,& 9\mapsto \left(\begin{array}{r} 5 \\ 8 \end{array}\right) ,& 10\mapsto \left(\begin{array}{r} 6 \\ 8 \end{array}\right) ,& 11\mapsto \left(\begin{array}{r} 7 \\ 8 \end{array}\right) ,& 12\mapsto \left(\begin{array}{r} 1 \\ 9 \end{array}\right) ,& 13\mapsto \left(\begin{array}{r} 5 \\ 9 \end{array}\right) ,& 14\mapsto \left(\begin{array}{r} 6 \\ 9 \end{array}\right) ,& 15\mapsto \left(\begin{array}{r} 0 \\ 10 \end{array}\right) ,\\ 16\mapsto \left(\begin{array}{r} 3 \\ 10 \end{array}\right) ,& 17\mapsto \left(\begin{array}{r} 5 \\ 11 \end{array}\right) ,& 18\mapsto \left(\begin{array}{r} 7 \\ 11 \end{array}\right) ,& 19\mapsto \left(\begin{array}{r} 2 \\ 12 \end{array}\right) . \end{array}$$

T2.tikz(font=r'\small', size=1.2, ncolumns=20)

Computing $\mathcal{T}_3$

T2.tikz(font=r'\small', size=1, ncolumns=20)

%time T2.find_markers(i=2, radius=2, solver=solver) # 4s with dancing_links, 2min 23s with Glucose, 15s with Gurobi

CPU times: user 4.04 s, sys: 0 ns, total: 4.04 s
Wall time: 4.04 s

[[8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]]

M2 = [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
T3,omega2 = T2.find_substitution(M=M2, i=2, side='left', radius=2, solver=solver)

show(omega2)

$$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{array}{llllllll} 0\mapsto \left(2\right) ,& 1\mapsto \left(3\right) ,& 2\mapsto \left(4\right) ,& 3\mapsto \left(5\right) ,& 4\mapsto \left(\begin{array}{r} 1 \\ 8 \end{array}\right) ,& 5\mapsto \left(\begin{array}{r} 5 \\ 8 \end{array}\right) ,& 6\mapsto \left(\begin{array}{r} 6 \\ 8 \end{array}\right) ,& 7\mapsto \left(\begin{array}{r} 0 \\ 9 \end{array}\right) ,\\ 8\mapsto \left(\begin{array}{r} 3 \\ 9 \end{array}\right) ,& 9\mapsto \left(\begin{array}{r} 5 \\ 10 \end{array}\right) ,& 10\mapsto \left(\begin{array}{r} 7 \\ 10 \end{array}\right) ,& 11\mapsto \left(\begin{array}{r} 2 \\ 11 \end{array}\right) ,& 12\mapsto \left(\begin{array}{r} 5 \\ 12 \end{array}\right) ,& 13\mapsto \left(\begin{array}{r} 6 \\ 12 \end{array}\right) ,& 14\mapsto \left(\begin{array}{r} 4 \\ 13 \end{array}\right) ,& 15\mapsto \left(\begin{array}{r} 5 \\ 14 \end{array}\right) ,\\ 16\mapsto \left(\begin{array}{r} 3 \\ 15 \end{array}\right) ,& 17\mapsto \left(\begin{array}{r} 3 \\ 16 \end{array}\right) ,& 18\mapsto \left(\begin{array}{r} 4 \\ 16 \end{array}\right) ,& 19\mapsto \left(\begin{array}{r} 3 \\ 17 \end{array}\right) ,& 20\mapsto \left(\begin{array}{r} 2 \\ 18 \end{array}\right) ,& 21\mapsto \left(\begin{array}{r} 0 \\ 19 \end{array}\right) ,& 22\mapsto \left(\begin{array}{r} 3 \\ 19 \end{array}\right) ,& 23\mapsto \left(\begin{array}{r} 4 \\ 19 \end{array}\right) . \end{array}$$

T3.tikz(font=r'\small', size=1, ncolumns=24)

Computing $\mathcal{T}_4'$

T3.tikz(font=r'\small', size=1, ncolumns=24)

%time T3.find_markers(i=2, radius=3, solver=solver) # 13s with dancing_links, 4min 55s with Glucose, 59s with Gurobi

CPU times: user 14.8 s, sys: 0 ns, total: 14.8 s
Wall time: 14.8 s

[[0, 1, 2, 3]]

M3 = [0, 1, 2, 3]
T4p,omega3p = T3.find_substitution(M=M3, i=2, side='right', radius=3, solver=solver)

show(omega3p)

$$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{array}{llllllll} 0\mapsto \left(5\right) ,& 1\mapsto \left(8\right) ,& 2\mapsto \left(11\right) ,& 3\mapsto \left(12\right) ,& 4\mapsto \left(14\right) ,& 5\mapsto \left(15\right) ,& 6\mapsto \left(16\right) ,& 7\mapsto \left(17\right) ,\\ 8\mapsto \left(18\right) ,& 9\mapsto \left(19\right) ,& 10\mapsto \left(20\right) ,& 11\mapsto \left(22\right) ,& 12\mapsto \left(23\right) ,& 13\mapsto \left(\begin{array}{r} 3 \\ 4 \end{array}\right) ,& 14\mapsto \left(\begin{array}{r} 2 \\ 5 \end{array}\right) ,& 15\mapsto \left(\begin{array}{r} 3 \\ 6 \end{array}\right) ,\\ 16\mapsto \left(\begin{array}{r} 1 \\ 7 \end{array}\right) ,& 17\mapsto \left(\begin{array}{r} 2 \\ 7 \end{array}\right) ,& 18\mapsto \left(\begin{array}{r} 1 \\ 8 \end{array}\right) ,& 19\mapsto \left(\begin{array}{r} 2 \\ 8 \end{array}\right) ,& 20\mapsto \left(\begin{array}{r} 1 \\ 9 \end{array}\right) ,& 21\mapsto \left(\begin{array}{r} 0 \\ 10 \end{array}\right) ,& 22\mapsto \left(\begin{array}{r} 2 \\ 11 \end{array}\right) ,& 23\mapsto \left(\begin{array}{r} 2 \\ 12 \end{array}\right) ,\\ 24\mapsto \left(\begin{array}{r} 3 \\ 13 \end{array}\right) ,& 25\mapsto \left(\begin{array}{r} 2 \\ 15 \end{array}\right) ,& 26\mapsto \left(\begin{array}{r} 2 \\ 16 \end{array}\right) ,& 27\mapsto \left(\begin{array}{r} 2 \\ 20 \end{array}\right) ,& 28\mapsto \left(\begin{array}{r} 2 \\ 21 \end{array}\right) ,& 29\mapsto \left(\begin{array}{r} 2 \\ 22 \end{array}\right) . \end{array}$$

T4p.tikz(font=r'\small', size=1.2, ncolumns=15)

Check that we can remove 2 tiles (tiles #24 and #28) from $\mathcal{T}_4'$

T4p.tikz(font=r'\small', size=1.2, ncolumns=15)

We check that tiles #24 and #28 can be removed from T4p. Since tile #28 is always to the left of #24, it suffices to check that the tile #24 does not admit a large enough surrounding (here of width 71 and heigth 9).

Gurobi or Glucose can solve this in a reasonable amount of time (<6s):

%%time
assert T4p[24] == ('21103', '1', '23310', '0')
S = T4p.solver(width=71, height=9, preassigned_tiles={(35,4):24})
print(S.has_solution(solver='glucose'))          # 6s with Gurobi, 4s with Glucose

False
CPU times: user 2.48 s, sys: 60 ms, total: 2.54 s
Wall time: 4.43 s

Computing $\mathcal{T}_4$

forbidden = ('21103', '1', '23310', '0'), ('23310', '0', '21330', '0')
id_tiles = [(i,t) for (i,t) in enumerate(T4p) if t not in forbidden]
indices,tiles = zip(*id_tiles)
d = dict(enumerate(indices))
iota = Substitution2d.from_permutation(d)
T4 = WangTileSet(tiles)

omega3 = omega3p * iota
show(omega3)

$$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{array}{llllllll} 0\mapsto \left(5\right) ,& 1\mapsto \left(8\right) ,& 2\mapsto \left(11\right) ,& 3\mapsto \left(12\right) ,& 4\mapsto \left(14\right) ,& 5\mapsto \left(15\right) ,& 6\mapsto \left(16\right) ,& 7\mapsto \left(17\right) ,\\ 8\mapsto \left(18\right) ,& 9\mapsto \left(19\right) ,& 10\mapsto \left(20\right) ,& 11\mapsto \left(22\right) ,& 12\mapsto \left(23\right) ,& 13\mapsto \left(\begin{array}{r} 3 \\ 4 \end{array}\right) ,& 14\mapsto \left(\begin{array}{r} 2 \\ 5 \end{array}\right) ,& 15\mapsto \left(\begin{array}{r} 3 \\ 6 \end{array}\right) ,\\ 16\mapsto \left(\begin{array}{r} 1 \\ 7 \end{array}\right) ,& 17\mapsto \left(\begin{array}{r} 2 \\ 7 \end{array}\right) ,& 18\mapsto \left(\begin{array}{r} 1 \\ 8 \end{array}\right) ,& 19\mapsto \left(\begin{array}{r} 2 \\ 8 \end{array}\right) ,& 20\mapsto \left(\begin{array}{r} 1 \\ 9 \end{array}\right) ,& 21\mapsto \left(\begin{array}{r} 0 \\ 10 \end{array}\right) ,& 22\mapsto \left(\begin{array}{r} 2 \\ 11 \end{array}\right) ,& 23\mapsto \left(\begin{array}{r} 2 \\ 12 \end{array}\right) ,\\ 24\mapsto \left(\begin{array}{r} 2 \\ 15 \end{array}\right) ,& 25\mapsto \left(\begin{array}{r} 2 \\ 16 \end{array}\right) ,& 26\mapsto \left(\begin{array}{r} 2 \\ 20 \end{array}\right) ,& 27\mapsto \left(\begin{array}{r} 2 \\ 22 \end{array}\right) . \end{array}$$

T4.tikz(font=r'\small', size=1.2, ncolumns=15)

The morphism $\omega_0\omega_1\omega_2\omega_3:\Omega_{4}\to\Omega_{0}$

omega0to4 = omega0*omega1*omega2*omega3
show(omega0to4)

$$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{array}{llllllll} 0\mapsto \left(\begin{array}{r} 7 \\ 3 \\ 9 \\ 0 \end{array}\right) ,& 1\mapsto \left(\begin{array}{r} 5 \\ 7 \\ 9 \\ 0 \end{array}\right) ,& 2\mapsto \left(\begin{array}{r} 4 \\ 10 \\ 9 \\ 0 \end{array}\right) ,& 3\mapsto \left(\begin{array}{r} 7 \\ 3 \\ 3 \\ 1 \end{array}\right) ,& 4\mapsto \left(\begin{array}{r} 6 \\ 7 \\ 3 \\ 1 \end{array}\right) ,& 5\mapsto \left(\begin{array}{r} 7 \\ 8 \\ 3 \\ 1 \end{array}\right) ,& 6\mapsto \left(\begin{array}{r} 5 \\ 2 \\ 7 \\ 1 \end{array}\right) ,& 7\mapsto \left(\begin{array}{r} 5 \\ 5 \\ 7 \\ 1 \end{array}\right) ,\\ 8\mapsto \left(\begin{array}{r} 6 \\ 5 \\ 7 \\ 1 \end{array}\right) ,& 9\mapsto \left(\begin{array}{r} 5 \\ 7 \\ 8 \\ 1 \end{array}\right) ,& 10\mapsto \left(\begin{array}{r} 4 \\ 10 \\ 8 \\ 1 \end{array}\right) ,& 11\mapsto \left(\begin{array}{r} 5 \\ 4 \\ 10 \\ 1 \end{array}\right) ,& 12\mapsto \left(\begin{array}{r} 6 \\ 4 \\ 10 \\ 1 \end{array}\right) ,& 13\mapsto \left(\begin{array}{r} 7 \\ 3 \\ 3 \\ 9 \\ 0 \end{array}\right) ,& 14\mapsto \left(\begin{array}{r} 6 \\ 7 \\ 3 \\ 9 \\ 0 \end{array}\right) ,& 15\mapsto \left(\begin{array}{r} 7 \\ 8 \\ 3 \\ 9 \\ 0 \end{array}\right) ,\\ 16\mapsto \left(\begin{array}{r} 5 \\ 2 \\ 7 \\ 9 \\ 0 \end{array}\right) ,& 17\mapsto \left(\begin{array}{r} 6 \\ 2 \\ 7 \\ 9 \\ 0 \end{array}\right) ,& 18\mapsto \left(\begin{array}{r} 5 \\ 5 \\ 7 \\ 9 \\ 0 \end{array}\right) ,& 19\mapsto \left(\begin{array}{r} 6 \\ 5 \\ 7 \\ 9 \\ 0 \end{array}\right) ,& 20\mapsto \left(\begin{array}{r} 5 \\ 7 \\ 8 \\ 9 \\ 0 \end{array}\right) ,& 21\mapsto \left(\begin{array}{r} 4 \\ 10 \\ 8 \\ 9 \\ 0 \end{array}\right) ,& 22\mapsto \left(\begin{array}{r} 6 \\ 4 \\ 10 \\ 9 \\ 0 \end{array}\right) ,& 23\mapsto \left(\begin{array}{r} 6 \\ 7 \\ 3 \\ 3 \\ 1 \end{array}\right) ,\\ 24\mapsto \left(\begin{array}{r} 6 \\ 7 \\ 8 \\ 3 \\ 1 \end{array}\right) ,& 25\mapsto \left(\begin{array}{r} 6 \\ 5 \\ 2 \\ 7 \\ 1 \end{array}\right) ,& 26\mapsto \left(\begin{array}{r} 6 \\ 4 \\ 10 \\ 8 \\ 1 \end{array}\right) ,& 27\mapsto \left(\begin{array}{r} 6 \\ 5 \\ 4 \\ 10 \\ 1 \end{array}\right) . \end{array}$$

omega0to4.wang_tikz(T4, T0, font=r'\scriptsize', scale=.8, codomain_color=color, ncolumns=10, direction='down', extra_space=1.5)

Trying to compute $\T_5$ ...

T4.tikz(font=r'\small', size=1, ncolumns=15)

%time T4.find_markers(i=1, radius=1, solver=solver)

CPU times: user 4.12 s, sys: 0 ns, total: 4.12 s
Wall time: 4.12 s

[]

%time T4.find_markers(i=2, radius=1, solver=solver)

CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 126 µs

[]

We have a problem: the Wang tile set $\T_4$ has markers neither in the direction $e_1$ nor $e_2$

So increasing the surrounding radius will not help here.

Even worse, we have two problems...

Defining $\mathcal{T}_5$

The first problem is the presence of horizontal fracture lines which we can break by adding decorations on the horizontal edges of few tiles. We have to do it in a way that we forbid sliding along fracture lines and without destroying the overall structure of Wang tilings in $\Omega_4$.

We create the tile set $\mathcal{T}_5$ by adding decorations on $\mathcal{T}_4$.

For few tiles, the horizontal color 0 is replaced by color 6.

For few tiles, the horizontal color 1 is replaced by color 5.

tiles5 = [('2113', '5', '2130', '1'),
 ('2130', '1', '2103', '5'),
 ('2133', '1', '2113', '1'),
 ('2113', '5', '2330', '0'),
 ('2130', '6', '2300', '0'),
 ('2103', '5', '2310', '0'),
 ('2310', '1', '2033', '6'),
 ('2300', '1', '2033', '6'),
 ('2300', '0', '2030', '6'),
 ('2030', '1', '2103', '0'),
 ('2033', '1', '2113', '0'),
 ('2330', '1', '2133', '6'),
 ('2330', '0', '2130', '6'),
 ('21113', '5', '21330', '1'),
 ('21130', '6', '21300', '1'),
 ('21103', '5', '21310', '1'),
 ('21310', '1', '21033', '5'),
 ('21310', '0', '21030', '5'),
 ('21300', '1', '21033', '5'),
 ('21300', '0', '21030', '5'),
 ('21030', '1', '21103', '1'),
 ('21033', '1', '21113', '1'),
 ('21330', '0', '21130', '1'),
 ('21330', '0', '21130', '5'),
 ('21130', '6', '23300', '0'),
 ('21030', '6', '23100', '0'),
 ('23100', '0', '20330', '6'),
 ('20330', '0', '21130', '0'),
 ('23300', '0', '21330', '6')]
T5 = WangTileSet(tiles5)
T5.tikz(font=r'\small', size=1.2, ncolumns=15)

The morphism $\pi:\mathcal{T}_5\to\mathcal{T}_4$

The morphism $\pi$ erases the decorations on tiles of $\mathcal{T}_5$.

It projects the horizontal color 6 back to color 0, and the horizontal color 5 back to color 1.

On tiles, the map $\pi:\mathcal{T}_5\to\mathcal{T}_4$ is not injective as it maps two tiles (#22 and #23) onto the same (#22).

def project_56(t, p56='10'):
    L = []
    d = dict(zip('56', p56))
    for w in t:
        for a in '56':
            w = w.replace(a, d[a])
        L.append(w)
    return tuple(L)

T4_tiles_list = T4.tiles()
d = {}
for i,t in enumerate(T5):
    pt = project_56(t, p56='10')
    j = T4_tiles_list.index(pt)
    d[i] = j
omega4_pi = Substitution2d.from_permutation(d)
show(omega4_pi)

$$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{array}{llllllll} 0\mapsto \left(0\right) ,& 1\mapsto \left(1\right) ,& 2\mapsto \left(2\right) ,& 3\mapsto \left(3\right) ,& 4\mapsto \left(4\right) ,& 5\mapsto \left(5\right) ,& 6\mapsto \left(6\right) ,& 7\mapsto \left(7\right) ,\\ 8\mapsto \left(8\right) ,& 9\mapsto \left(9\right) ,& 10\mapsto \left(10\right) ,& 11\mapsto \left(11\right) ,& 12\mapsto \left(12\right) ,& 13\mapsto \left(13\right) ,& 14\mapsto \left(14\right) ,& 15\mapsto \left(15\right) ,\\ 16\mapsto \left(16\right) ,& 17\mapsto \left(17\right) ,& 18\mapsto \left(18\right) ,& 19\mapsto \left(19\right) ,& 20\mapsto \left(20\right) ,& 21\mapsto \left(21\right) ,& 22\mapsto \left(22\right) ,& 23\mapsto \left(22\right) ,\\ 24\mapsto \left(23\right) ,& 25\mapsto \left(24\right) ,& 26\mapsto \left(25\right) ,& 27\mapsto \left(26\right) ,& 28\mapsto \left(27\right) . \end{array}$$

But surprise, on tilings, the map $\pi:\Omega_5\to\Omega_4$ defines a $2$-dimensional morphism which is an embedding, i.e., injective.

Trying to compute $\T_6$ from $\T_5$ ...

T5.tikz(font=r'\small', size=1, ncolumns=15)

%time T5.find_markers(i=1, radius=1, solver=solver)

CPU times: user 4.74 s, sys: 4 ms, total: 4.74 s
Wall time: 4.74 s

[]

%time T5.find_markers(i=2, radius=1, solver=solver)

CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 70.6 µs

[]

We still have a problem: the Wang tile set $\T_5$ has markers neither in the direction $e_1$ nor $e_2$

So increasing the surrounding radius will not help here.

Tilings in $\Omega_5$

Let's look at tilings in $\Omega_5$.

tiling = T5.solver(30,10).solve(solver='glucose')

P = tiling.tile_positions([1, 6, 7, 8, 11, 12, 16, 17, 18, 19, 23, 26, 28])
s = '\n'.join([r'\fill[yellow] {} rectangle {};'.format((a,b), (a+1,b+1)) for (a,b) in P])
tiling.tikz(extra_before=s)

Computing $\mathcal{T}_6$ and the shear topological conjugacy $\eta:\Omega_6\to\Omega_5$

The second problem is that $\T_5$ does not have markers, it has diagonal markers, i.e., markers appears on lines of slope 1.

To fix this, instead of introducing the notion of diagonal markers, we choose to transform the Wang tile set in a way that it shears the tiling by the matrix $\left(\begin{smallmatrix} 1 & -1 \\ 0 & 1\end{smallmatrix}\right)$ so that markers become vertical.

%tikz -i shear.tikz -p amssymb --no-wrap

This transformation on tiles yields a homeomorphism $\eta:\Omega_6\to\Omega_5$ which commutes the normal shift on $\Omega_5$ into the sheared shift on $\Omega_6$.

%time T6,omega5_sheer = T5.shear(radius=2, solver=solver) # 6s with dancing_links, 3min 12s with Glucose, 22s with Gurobi

CPU times: user 6.38 s, sys: 0 ns, total: 6.38 s
Wall time: 6.38 s

show(omega5_sheer)

$$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{array}{llllllll} 0\mapsto \left(0\right) ,& 1\mapsto \left(1\right) ,& 2\mapsto \left(2\right) ,& 3\mapsto \left(3\right) ,& 4\mapsto \left(4\right) ,& 5\mapsto \left(5\right) ,& 6\mapsto \left(6\right) ,& 7\mapsto \left(7\right) ,\\ 8\mapsto \left(8\right) ,& 9\mapsto \left(9\right) ,& 10\mapsto \left(10\right) ,& 11\mapsto \left(11\right) ,& 12\mapsto \left(12\right) ,& 13\mapsto \left(13\right) ,& 14\mapsto \left(14\right) ,& 15\mapsto \left(15\right) ,\\ 16\mapsto \left(16\right) ,& 17\mapsto \left(17\right) ,& 18\mapsto \left(18\right) ,& 19\mapsto \left(19\right) ,& 20\mapsto \left(20\right) ,& 21\mapsto \left(21\right) ,& 22\mapsto \left(22\right) ,& 23\mapsto \left(23\right) ,\\ 24\mapsto \left(24\right) ,& 25\mapsto \left(25\right) ,& 26\mapsto \left(26\right) ,& 27\mapsto \left(27\right) ,& 28\mapsto \left(28\right) . \end{array}$$

T6.tikz(font=r'\small', size=1.2, ncolumns=15)

Computing $\mathcal{T}_7$

T6.tikz(font=r'\small', size=1.2, ncolumns=15)

%time T6.find_markers(i=1, radius=1, solver=solver) # 5s with dancing_links, 4min 25s with Glucose, 17s with Gurobi

CPU times: user 4.79 s, sys: 4 ms, total: 4.8 s
Wall time: 4.8 s

[[0, 3, 4, 5, 13, 14, 15, 24, 25],
 [1, 6, 7, 8, 11, 12, 16, 17, 18, 19, 23, 26, 28],
 [2, 9, 10, 20, 21, 22, 27]]

Youpi! The tile set $\T_6$ has 3 subsets of markers in the direction $e_1$. Thus, we may chose one, desubstitute and compute $\T_7$.

M6 = [1, 6, 7, 8, 11, 12, 16, 17, 18, 19, 23, 26, 28]
T7,omega6 = T6.find_substitution(M=M6, i=1, radius=1, side='left', solver=solver)

show(omega4_pi*omega5_sheer*omega6)

$$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{array}{llllllll} 0\mapsto \left(2\right) ,& 1\mapsto \left(9\right) ,& 2\mapsto \left(10\right) ,& 3\mapsto \left(20\right) ,& 4\mapsto \left(21\right) ,& 5\mapsto \left(22\right) ,& 6\mapsto \left(26\right) ,& 7\mapsto \left(1,\,0\right) ,\\ 8\mapsto \left(6,\,5\right) ,& 9\mapsto \left(7,\,4\right) ,& 10\mapsto \left(8,\,4\right) ,& 11\mapsto \left(11,\,3\right) ,& 12\mapsto \left(12,\,3\right) ,& 13\mapsto \left(16,\,15\right) ,& 14\mapsto \left(17,\,15\right) ,& 15\mapsto \left(18,\,14\right) ,\\ 16\mapsto \left(19,\,14\right) ,& 17\mapsto \left(22,\,13\right) ,& 18\mapsto \left(25,\,24\right) ,& 19\mapsto \left(27,\,23\right) . \end{array}$$

T7.tikz(font=r'\small', size=1.2)

Computing $\mathcal{T}_8$

T7.tikz(font=r'\small', size=1.2)

%time T7.find_markers(i=1, radius=1, solver=solver) # 2s with dancing_links, 2min with Glucose, 6s with Gurobi

CPU times: user 1.53 s, sys: 0 ns, total: 1.53 s
Wall time: 1.53 s

[[0, 1, 2, 3, 4, 5, 6]]

M7 = [0, 1, 2, 3, 4, 5, 6]
T8,omega7 = T7.find_substitution(M=M7, i=1, radius=1, solver=solver)

show(omega7)

$$\newcommand{\Bold}[1]{\mathbf{#1}}\begin{array}{llllllll} 0\mapsto \left(8\right) ,& 1\mapsto \left(9\right) ,& 2\mapsto \left(10\right) ,& 3\mapsto \left(15\right) ,& 4\mapsto \left(16\right) ,& 5\mapsto \left(18\right) ,& 6\mapsto \left(19\right) ,& 7\mapsto \left(7,\,0\right) ,\\ 8\mapsto \left(7,\,2\right) ,& 9\mapsto \left(8,\,1\right) ,& 10\mapsto \left(11,\,2\right) ,& 11\mapsto \left(12,\,2\right) ,& 12\mapsto \left(13,\,3\right) ,& 13\mapsto \left(14,\,3\right) ,& 14\mapsto \left(15,\,5\right) ,& 15\mapsto \left(15,\,6\right) ,\\ 16\mapsto \left(16,\,5\right) ,& 17\mapsto \left(16,\,6\right) ,& 18\mapsto \left(17,\,4\right) ,& 19\mapsto \left(19,\,6\right) . \end{array}$$

T8.tikz(font=r'\small', size=1.2)