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:
doi:10.1007/s10711-018-0384-8, arXiv:1802.03265
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
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'
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}}}$
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
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$
(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$.
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)
T1.tikz(font=r'\small', size=1.2, ncolumns=13)
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)
T2.tikz(font=r'\small', size=1.2, ncolumns=20)
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)
T3.tikz(font=r'\small', size=1, ncolumns=24)
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)
T4p.tikz(font=r'\small', size=1.2, ncolumns=15)
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
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)
T4.tikz(font=r'\small', size=1.2, ncolumns=15)
omega0to4 = omega0*omega1*omega2*omega3
show(omega0to4)
omega0to4.wang_tikz(T4, T0, font=r'\scriptsize', scale=.8, codomain_color=color, ncolumns=10, direction='down', extra_space=1.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...
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$ 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)
But surprise, on tilings, the map $\pi:\Omega_5\to\Omega_4$ defines a $2$-dimensional morphism which is an embedding, i.e., injective.
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.
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)
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)
T6.tikz(font=r'\small', size=1.2, ncolumns=15)
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)
T7.tikz(font=r'\small', size=1.2)
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)
T8.tikz(font=r'\small', size=1.2)
T8.tikz(font=r'\small', size=1.2)
%time T8.find_markers(i=2, radius=2, solver=solver) # 4s with dancing_links, 2min 24s with Glucose, 15s with Gurobi
CPU times: user 3.98 s, sys: 0 ns, total: 3.98 s Wall time: 3.97 s
[[0, 1, 2, 7, 8, 9, 10, 11]]
M8 = [0, 1, 2, 7, 8, 9, 10, 11]
T9,omega8 = T8.find_substitution(M=M8, i=2, radius=2, solver=solver)
show(omega8)
T9.tikz(font=r'\small', size=1.2, ncolumns=11)
Since the colors of tiles in $\T_9$ are too long words, it is preferable to look at the Wang tile set $\T_9$ as a table:
T9.table()
Id | Right | Top | Left | Bottom |
---|---|---|---|---|
211300 | 60 | 210331 | 51 | |
211300 | 60 | 210300 | 51 | |
210300 | 60 | 203300 | 60 | |
211300 | 60 | 213300 | 60 | |
210300 | 510 | 210331 | 511 | |
210300 | 510 | 210300 | 511 | |
213300 | 600 | 210331 | 511 | |
203300 | 600 | 210331 | 510 | |
210331 | 511 | 211300 | 511 | |
21130021031 | 51 | 21030020331 | 51 | |
21030021031 | 51 | 20330020331 | 60 | |
21030021300 | 60 | 20330020331 | 60 | |
21030021300 | 60 | 20330020300 | 60 | |
21130021031 | 51 | 21330020331 | 60 | |
21030020331 | 511 | 21030021031 | 511 | |
21330020331 | 511 | 21033121331 | 511 | |
20330020331 | 511 | 21033121331 | 510 | |
21330020331 | 511 | 21030021300 | 511 | |
20330020300 | 510 | 21030020331 | 510 | |
20330020331 | 511 | 21030021300 | 510 | |
21033121331 | 511 | 21130021031 | 511 | |
20330020300 | 510 | 21330020331 | 600 |
%time T9.find_markers(i=1, radius=1, solver=solver) # 2s with dancing_links, 2min 30s with Glucose, 8s with Gurobi
CPU times: user 2.03 s, sys: 4 ms, total: 2.04 s Wall time: 2.04 s
[[0, 1, 2, 3, 9, 10, 11, 12, 13], [4, 6, 7, 15, 16, 18, 21], [5, 8, 14, 17, 19, 20]]
M9 = [0, 1, 2, 3, 9, 10, 11, 12, 13]
T10,omega9 = T9.find_substitution(M=M9, i=1, radius=1, solver=solver)
show(omega9)
T10.table()
Id | Right | Top | Left | Bottom |
---|---|---|---|---|
210331 | 511 | 211300 | 511 | |
21030020331 | 511 | 21030021031 | 511 | |
21330020331 | 511 | 21030021300 | 511 | |
21033121331 | 511 | 21130021031 | 511 | |
211300 | 51060 | 210331 | 51151 | |
211300 | 51060 | 210300 | 51151 | |
211300 | 60060 | 210331 | 51160 | |
210300 | 60060 | 210331 | 51060 | |
211300 | 51160 | 211300 | 51151 | |
21130021031 | 51151 | 21030021031 | 51151 | |
21130021031 | 51151 | 21033121331 | 51160 | |
21030021031 | 51151 | 21033121331 | 51060 | |
21030021300 | 51160 | 21033121331 | 51060 | |
21130021031 | 51151 | 21030021300 | 51160 | |
21030021300 | 51060 | 21030020331 | 51060 | |
21030021031 | 51151 | 21030021300 | 51060 | |
21030021300 | 51160 | 21030021300 | 51060 | |
21030021300 | 51060 | 21330020331 | 60060 |
%time T10.find_markers(i=2, radius=2, solver=solver) # 3s with dancing_links, 1min 52s with Glucose, 11s with Gurobi
CPU times: user 2.92 s, sys: 0 ns, total: 2.92 s Wall time: 2.92 s
[[0, 4, 5, 6, 7, 8]]
M10 = [0, 4, 5, 6, 7, 8]
T11,omega10 = T10.find_substitution(M=M10, i=2, radius=2, solver=solver)
show(omega10)
T11.table()
Id | Right | Top | Left | Bottom |
---|---|---|---|---|
21030020331 | 511 | 21030021031 | 511 | |
21330020331 | 511 | 21030021300 | 511 | |
21033121331 | 511 | 21130021031 | 511 | |
21030021300 | 51160 | 21033121331 | 51060 | |
21130021031 | 51151 | 21030021300 | 51160 | |
21030021300 | 51060 | 21030020331 | 51060 | |
21030021031 | 51151 | 21030021300 | 51060 | |
21030021300 | 51160 | 21030021300 | 51060 | |
21030021300 | 51060 | 21330020331 | 60060 | |
21030020331210331 | 511 | 21030021031211300 | 511 | |
21330020331210331 | 511 | 21030021300211300 | 511 | |
21033121331210331 | 511 | 21130021031211300 | 511 | |
21130021031211300 | 51160 | 21030021031211300 | 51151 | |
21130021031211300 | 51060 | 21033121331210331 | 51160 | |
21030021031211300 | 51060 | 21033121331210331 | 51060 | |
21030021300211300 | 60060 | 21033121331210331 | 51060 | |
21130021031211300 | 51060 | 21030021300210300 | 51160 | |
21130021031211300 | 51160 | 21030021300211300 | 51160 | |
21030021300210300 | 60060 | 21030020331210331 | 51060 | |
21030021031211300 | 51060 | 21030021300210300 | 51060 | |
21030021300210300 | 60060 | 21330020331210331 | 60060 |
%time T11.find_markers(i=1, radius=1, solver=solver) # 2s with dancing_links, 2min 15s with Glucose, 7s with Gurobi
CPU times: user 1.86 s, sys: 0 ns, total: 1.86 s Wall time: 1.86 s
[[0, 1, 2, 9, 10, 11], [3, 5, 8, 13, 14, 15, 18, 20], [4, 6, 7, 12, 16, 17, 19]]
M11 = [0, 1, 2, 9, 10, 11]
T12,omega11 = T11.find_substitution(M=M11, i=1, radius=1, solver=solver)
show(omega11)
T12.table()
Id | Right | Top | Left | Bottom |
---|---|---|---|---|
21030021300 | 51060 | 21030020331 | 51060 | |
21030021300 | 51060 | 21330020331 | 60060 | |
21030021031211300 | 51060 | 21033121331210331 | 51060 | |
21030021300211300 | 60060 | 21033121331210331 | 51060 | |
21030021300210300 | 60060 | 21030020331210331 | 51060 | |
21030021300210300 | 60060 | 21330020331210331 | 60060 | |
21330020331 | 51160511 | 21033121331 | 51060511 | |
21033121331 | 51151511 | 21030021300 | 51160511 | |
21330020331 | 51060511 | 21030020331 | 51060511 | |
21030020331 | 51151511 | 21030021300 | 51060511 | |
21330020331 | 51160511 | 21030021300 | 51060511 | |
21330020331 | 51060511 | 21330020331 | 60060511 | |
21033121331210331 | 51160511 | 21030021031211300 | 51151511 | |
21033121331210331 | 51060511 | 21033121331210331 | 51160511 | |
21030020331210331 | 51060511 | 21033121331210331 | 51060511 | |
21330020331210331 | 60060511 | 21033121331210331 | 51060511 | |
21033121331210331 | 51060511 | 21030021300210300 | 51160511 | |
21033121331210331 | 51160511 | 21030021300211300 | 51160511 | |
21030020331210331 | 51060511 | 21030021300210300 | 51060511 |
S. Labbé, A self-similar aperiodic set of 19 Wang tiles, Geometriae Dedicata, (2018)
doi:10.1007/s10711-018-0384-8.
Preprint: arXiv:1802.03265
tilesU = ['FOJO','FOHL','JMFP','DMFK','HPJP','HPHN','HKFP','HKDP','BOIO','GLEO','GLCL',
'ALIO','EPGP','EPIP','IPGK','IPIK','IKBM','IKAK','CNIP',]
tilesU = [tuple(tile) for tile in tilesU]
U = WangTileSet(tilesU)
U.tikz(size=1)
The tile sets $\mathcal{U}$ and $\mathcal{T}_{12}$ are equivalent:
is_equiv,f,g,permUtoT12 = U.is_equivalent(T12, certificate=True)
is_equiv,f,g
(True, {'J': '21030020331', 'F': '21030021300', 'H': '21330020331', 'D': '21033121331', 'I': '21033121331210331', 'B': '21030021031211300', 'A': '21030021300211300', 'E': '21030020331210331', 'C': '21330020331210331', 'G': '21030021300210300'}, {'O': '51060', 'L': '60060', 'P': '51060511', 'M': '51151511', 'K': '51160511', 'N': '60060511'})
show(permUtoT12)
U.tikz(size=1, ncolumns=20)
%time U.find_markers(i=2, radius=2, solver=solver) # 3s with dancing_links, 13s with Gurobi
CPU times: user 3.51 s, sys: 0 ns, total: 3.51 s Wall time: 3.51 s
[[0, 1, 2, 3, 4, 5, 6, 7]]
M12 = [0, 1, 2, 3, 4, 5, 6, 7]
T13,omega12 = U.find_substitution(M=M12, i=2, radius=2, solver=solver)
show(omega12)
T13.tikz(size=1.2, ncolumns=11)
T13.tikz(size=1, ncolumns=11)
%time T13.find_markers(i=1, radius=1, solver=solver) # 2s with dancing_links, 7s with Gurobi
CPU times: user 1.77 s, sys: 0 ns, total: 1.77 s Wall time: 1.77 s
[[0, 1, 2, 8, 9, 10, 11], [3, 5, 13, 14, 17, 20], [4, 6, 7, 12, 15, 16, 18, 19]]
M13 = [0, 1, 2, 8, 9, 10, 11]
T14,omega13 = T13.find_substitution(M=M13, i=1, radius=1, solver=solver)
show(omega13)
T14.tikz(size=1.2)
is_equiv,f,g,permUtoW = U.is_equivalent(T14, certificate=True)
assert is_equiv
omegaUtoU = omega12 * omega13 * permUtoW
show(omegaUtoU)
omegaUtoU.wang_tikz(U, U, font=r'\scriptsize', scale=1, codomain_color=color, ncolumns=4,
direction='right', extra_space=1.5)
M = matrix(2, [1,1,0,1])
omega5toU = omega5_sheer*omega6*omega7*omega8*omega9*omega10*omega11*permUtoT12
omega4toU = omega4_pi*omega5toU
omega5toUsheer = omega5toU.apply_matrix_transformation(M)
omega4toUsheer = omega4toU.apply_matrix_transformation(M)
omega3 = omega3p * iota
omega0to4 = omega0*omega1*omega2*omega3
omega0toU = omega0to4*omega4toUsheer
omega5toUsheer.wang_tikz(U, T5, font=r'\scriptsize', scale=.9, ncolumns=2, extra_space=1.5)
omega4toUsheer.wang_tikz(U, T4, font=r'\scriptsize', scale=.9, ncolumns=2, extra_space=1.5)
omega0toU.wang_tikz(U, T0, font=r'\scriptsize', scale=.8, codomain_color=color, id=None,
ncolumns=4, direction='right', extra_space=1.5)
from slabbe import TikzPicture
G = omegaUtoU.prolongable_origins()
TikzPicture.from_graph(G, rankdir='down')
Gh = DiGraph(T12.dominoes_with_surrounding(i=1,radius=2), format='list_of_edges')
TikzPicture.from_graph(Gh)
Gv = DiGraph(T12.dominoes_with_surrounding(i=2,radius=2), format='list_of_edges')
TikzPicture.from_graph(Gv)
Inverse of frequencies of tiles in $\Omega_4$:
M = matrix(omegaUtoU)
z = polygen(QQ, 'z')
K.<phi> = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
MK = M.change_ring(K)
v = MK.eigenvectors_right()[0][1][0]
v4 = matrix(omega4toU) * v
sorted((1/a, i) for (i,a) in enumerate(v4/sum(v4)))
[(5*phi + 3, 14), (6*phi + 4, 22), (8*phi + 5, 10), (8*phi + 5, 19), (10*phi + 6, 3), (10*phi + 6, 5), (10*phi + 6, 6), (10*phi + 6, 13), (10*phi + 6, 21), (10*phi + 6, 24), (10*phi + 6, 25), (10*phi + 6, 26), (13*phi + 8, 18), (16*phi + 10, 0), (16*phi + 10, 1), (16*phi + 10, 4), (16*phi + 10, 12), (16*phi + 10, 15), (16*phi + 10, 20), (16*phi + 10, 23), (16*phi + 10, 27), (26*phi + 16, 2), (26*phi + 16, 8), (26*phi + 16, 9), (26*phi + 16, 11), (26*phi + 16, 17), (42*phi + 26, 7), (42*phi + 26, 16)]
Inverse of frequencies of tiles in $\Omega_0$:
v0 = matrix(omega0to4) * v4
sorted((1/a, i) for (i,a) in enumerate(v0/sum(v0)))
[(12/5*phi + 14/5, 7), (2*phi + 6, 0), (2*phi + 6, 1), (2*phi + 6, 3), (2*phi + 6, 6), (2*phi + 6, 9), (5*phi + 4, 5), (8*phi + 2, 4), (8*phi + 2, 8), (8*phi + 2, 10), (18*phi + 10, 2)]