# Substitutive structure of Jeandel-Rao aperiodic tilings¶

## Prerequisites¶

Sage version 8.3 or above should work:

In [1]:
version()

Out[1]:
'SageMath version 8.4.beta1, Release Date: 2018-08-14'

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

In [2]:
#!sage -pip install slabbe==0.4.3


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

In [3]:
#!sage -pip install dot2tex


## Choosing a solver¶

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

Solver Time to run this notebook
other MILP solver unknown

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

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

In [4]:
from sage.doctest.external import has_gurobi
if has_gurobi():
solver = 'gurobi'
else:
print("We are using solver = '{}'".format(solver))

We are using solver = 'gurobi'


## Colors setup¶

In [5]:
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()})


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

In [6]:
from slabbe import WangTileSet, Substitution2d
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 = [map(str,t) for t in tiles]
T0 = WangTileSet(tiles)
T0.tikz(font=r'\small', size=1, ncolumns=11, color=color)

Out[6]:

## Computing $\mathcal{T}_1$¶

In [7]:
%time T0.find_markers(i=2, radius=1, solver=solver) # 47s with dancing_links, 1.4s with Gurobi

CPU times: user 1.06 s, sys: 196 ms, total: 1.26 s
Wall time: 1.23 s

Out[7]:
[[0, 1]]
In [8]:
M0 = [0,1]
T1,s0,_ = T0.find_substitution(M=M0, i=2, side='left', solver=solver)

In [9]:
T1.tikz(font=r'\small', size=1.2)

Out[9]:
In [10]:
show(s0)


## Computing $\mathcal{T}_2$¶

In [11]:
%time T1.find_markers(i=2, radius=1, solver=solver) #1min 16s with dancing_links, 2s with Gurobi

CPU times: user 1.64 s, sys: 240 ms, total: 1.88 s
Wall time: 1.85 s

Out[11]:
[[8, 9, 10, 11, 12]]
In [12]:
M1 = [8, 9, 10, 11, 12]
T2,s1,_ = T1.find_substitution(M=M1, i=2, side='left', solver=solver)

In [13]:
T2.tikz(font=r'\small', size=1.2)

Out[13]:
In [14]:
show(s1)


## Computing $\mathcal{T}_3$¶

In [15]:
%time T2.find_markers(i=2, radius=2, solver=solver) # 5min 25s with dancing_links, 15s with Gurobi

CPU times: user 13.3 s, sys: 752 ms, total: 14.1 s
Wall time: 13.9 s

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

In [17]:
T3.tikz(font=r'\small', size=1.2)

Out[17]:
In [18]:
show(s2)


## Computing $\mathcal{T}_4'$¶

In [19]:
%time T3.find_markers(i=2, radius=3, solver=solver) # 10min 12s with dancing_links, 59s with Gurobi

CPU times: user 1min 7s, sys: 1.66 s, total: 1min 9s
Wall time: 54.1 s

Out[19]:
[[0, 1, 2, 3]]
In [20]:
M3 = [0, 1, 2, 3]
T4p,s3p,_ = T3.find_substitution(M=M3, i=2, side='right', radius=3, solver=solver)

In [21]:
T4p.tikz(font=r'\small', size=1.2)

Out[21]:
In [22]:
show(s3p)


## Check that we can remove 2 tiles from $\mathcal{T}_4'$¶

Only Gurobi can solve this in a reasonable amount of time (6s)

In [23]:
def check_2_tiles_to_remove_from_T4p():
assert T4p[18] == ('21103', '1', '23310', '0')
S = T4p.solver(width=71, height=9, preassigned_tiles={(35,4):18})
return S.has_solution(solver='Gurobi')
%time check_2_tiles_to_remove_from_T4p()

CPU times: user 14.4 s, sys: 352 ms, total: 14.8 s
Wall time: 5.45 s

Out[23]:
False

## Computing $\mathcal{T}_4$¶

In [24]:
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)
T4.tikz(font=r'\small', size=1.2)

Out[24]:
In [25]:
show(iota)

In [26]:
s3 = s3p * iota
show(s3)


## Defining $\mathcal{T}_5$¶

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

Out[27]:

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

In [28]:
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)

In [29]:
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
s4_pi = Substitution2d.from_permutation(d)
show(s4_pi)


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

In [30]:
%time T6,s5_sheer = T5.shear(radius=2) # 20s with dancing_links, 22s with Gurobi
T6.tikz(font=r'\small', size=1.2)

CPU times: user 19 s, sys: 712 ms, total: 19.7 s
Wall time: 19.5 s

Out[30]:
In [31]:
show(s5_sheer)


## Computing $\mathcal{T}_7$¶

In [32]:
%time T6.find_markers(i=1, radius=1, solver=solver) #14min 31s with dancing_links, 17s with Gurobi

CPU times: user 14.2 s, sys: 1.33 s, total: 15.5 s
Wall time: 15.4 s

Out[32]:
[[2, 3, 4, 5, 14, 17, 18, 19, 20],
[6, 8, 9, 10, 11, 12, 21, 22, 23, 24, 26, 27, 28],
[0, 1, 7, 13, 15, 16, 25]]
In [33]:
M6 = [6, 8, 9, 10, 11, 12, 21, 22, 23, 24, 26, 27, 28]
T7,s6,_ = T6.find_substitution(M=M6, i=1, radius=1, side='left', solver=solver)

In [34]:
T7.tikz(font=r'\small', size=1.2)

Out[34]:
In [35]:
show(s6)


## Computing $\mathcal{T}_8$¶

In [36]:
%time T7.find_markers(i=1, radius=1, solver=solver) #4min 44s with dancing_links, 6s with Gurobi

CPU times: user 5.21 s, sys: 660 ms, total: 5.87 s
Wall time: 5.8 s

Out[36]:
[[0, 1, 2, 9, 10, 11, 12]]
In [37]:
M7 = [0, 1, 2, 9, 10, 11, 12]
T8,s7,_ = T7.find_substitution(M=M7, i=1, radius=1, solver=solver)

In [38]:
T8.tikz(font=r'\small', size=1.2)

Out[38]:
In [39]:
show(s7)


## Computing $\mathcal{T}_9$¶

In [40]:
%time T8.find_markers(i=2, radius=2, solver=solver) # 5min 9s with dancing_links, 15s with Gurobi

CPU times: user 13.4 s, sys: 632 ms, total: 14.1 s
Wall time: 13.9 s

Out[40]:
[[0, 1, 2, 3, 4, 5, 6, 7]]
In [41]:
M8 = [0, 1, 2, 3, 4, 5, 6, 7]
T9,s8,_ = T8.find_substitution(M=M8, i=2, radius=2, solver=solver)

In [42]:
T9.table()

Out[42]:
Id Right Top Left Bottom
$0$ 210300 60 203300 60
$1$ 211300 60 210300 51
$2$ 211300 60 210331 51
$3$ 211300 60 213300 60
$4$ 203300 600 210331 510
$5$ 210300 510 210300 511
$6$ 210300 510 210331 511
$7$ 210331 511 211300 511
$8$ 213300 600 210331 511
$9$ 21030021031 51 20330020331 60
$10$ 21030021300 60 20330020300 60
$11$ 21030021300 60 20330020331 60
$12$ 21130021031 51 21030020331 51
$13$ 21130021031 51 21330020331 60
$14$ 20330020300 510 21030020331 510
$15$ 20330020300 510 21330020331 600
$16$ 20330020331 511 21030021300 510
$17$ 20330020331 511 21033121331 510
$18$ 21030020331 511 21030021031 511
$19$ 21033121331 511 21130021031 511
$20$ 21330020331 511 21030021300 511
$21$ 21330020331 511 21033121331 511
In [43]:
show(s8)


## Computing $\mathcal{T}_{10}$¶

In [44]:
%time T9.find_markers(i=1, radius=1, solver=solver) # 6min 23s with dancing_links, 8s with Gurobi

CPU times: user 6.91 s, sys: 700 ms, total: 7.61 s
Wall time: 7.55 s

Out[44]:
[[0, 1, 2, 3, 9, 10, 11, 12, 13],
[5, 7, 16, 18, 19, 20],
[4, 6, 8, 14, 15, 17, 21]]
In [45]:
M9 = [0, 1, 2, 3, 9, 10, 11, 12, 13]
T10,s9,_ = T9.find_substitution(M=M9, i=1, radius=1, solver=solver)

In [46]:
T10.table()

Out[46]:
Id Right Top Left Bottom
$0$ 210331 511 211300 511
$1$ 210300 60060 210331 51060
$2$ 211300 51060 210300 51151
$3$ 211300 51060 210331 51151
$4$ 211300 51160 211300 51151
$5$ 211300 60060 210331 51160
$6$ 21030020331 511 21030021031 511
$7$ 21033121331 511 21130021031 511
$8$ 21330020331 511 21030021300 511
$9$ 21030021031 51151 21030021300 51060
$10$ 21030021031 51151 21033121331 51060
$11$ 21030021300 51060 21030020331 51060
$12$ 21030021300 51060 21330020331 60060
$13$ 21030021300 51160 21030021300 51060
$14$ 21030021300 51160 21033121331 51060
$15$ 21130021031 51151 21030021031 51151
$16$ 21130021031 51151 21030021300 51160
$17$ 21130021031 51151 21033121331 51160
In [47]:
show(s9)


## Computing $\mathcal{T}_{11}$¶

In [48]:
%time T10.find_markers(i=2, radius=2, solver=solver) # 3min 37s with dancing_links, 11s with Gurobi

CPU times: user 9.94 s, sys: 604 ms, total: 10.5 s
Wall time: 10.4 s

Out[48]:
[[0, 1, 2, 3, 4, 5]]
In [49]:
M10 = [0, 1, 2, 3, 4, 5]
T11,s10,_ = T10.find_substitution(M=M10, i=2, radius=2, solver=solver)

In [50]:
T11.table()

Out[50]:
Id Right Top Left Bottom
$0$ 21030020331 511 21030021031 511
$1$ 21033121331 511 21130021031 511
$2$ 21330020331 511 21030021300 511
$3$ 21030021031 51151 21030021300 51060
$4$ 21030021300 51060 21030020331 51060
$5$ 21030021300 51060 21330020331 60060
$6$ 21030021300 51160 21030021300 51060
$7$ 21030021300 51160 21033121331 51060
$8$ 21130021031 51151 21030021300 51160
$9$ 21030020331210331 511 21030021031211300 511
$10$ 21033121331210331 511 21130021031211300 511
$11$ 21330020331210331 511 21030021300211300 511
$12$ 21030021031211300 51060 21030021300210300 51060
$13$ 21030021031211300 51060 21033121331210331 51060
$14$ 21030021300210300 60060 21030020331210331 51060
$15$ 21030021300210300 60060 21330020331210331 60060
$16$ 21030021300211300 60060 21033121331210331 51060
$17$ 21130021031211300 51060 21030021300210300 51160
$18$ 21130021031211300 51060 21033121331210331 51160
$19$ 21130021031211300 51160 21030021031211300 51151
$20$ 21130021031211300 51160 21030021300211300 51160
In [51]:
show(s10)


## Computing $\mathcal{T}_{12}$¶

In [52]:
%time T11.find_markers(i=1, radius=1, solver=solver) # 5min 25s with dancing_links, 7s with Gurobi

CPU times: user 6 s, sys: 668 ms, total: 6.66 s
Wall time: 6.6 s

Out[52]:
[[0, 1, 2, 9, 10, 11],
[3, 6, 8, 12, 17, 19, 20],
[4, 5, 7, 13, 14, 15, 16, 18]]
In [53]:
M11 = [0, 1, 2, 9, 10, 11]
T12,s11,_ = T11.find_substitution(M=M11, i=1, radius=1, solver=solver)

In [54]:
T12.table()

Out[54]:
Id Right Top Left Bottom
$0$ 21030021300 51060 21030020331 51060
$1$ 21030021300 51060 21330020331 60060
$2$ 21030020331 51151511 21030021300 51060511
$3$ 21033121331 51151511 21030021300 51160511
$4$ 21330020331 51060511 21030020331 51060511
$5$ 21330020331 51060511 21330020331 60060511
$6$ 21330020331 51160511 21030021300 51060511
$7$ 21330020331 51160511 21033121331 51060511
$8$ 21030021031211300 51060 21033121331210331 51060
$9$ 21030021300210300 60060 21030020331210331 51060
$10$ 21030021300210300 60060 21330020331210331 60060
$11$ 21030021300211300 60060 21033121331210331 51060
$12$ 21030020331210331 51060511 21030021300210300 51060511
$13$ 21030020331210331 51060511 21033121331210331 51060511
$14$ 21033121331210331 51060511 21030021300210300 51160511
$15$ 21033121331210331 51060511 21033121331210331 51160511
$16$ 21033121331210331 51160511 21030021031211300 51151511
$17$ 21033121331210331 51160511 21030021300211300 51160511
$18$ 21330020331210331 60060511 21033121331210331 51060511
In [55]:
show(s11)


## Definition of $\mathcal{U}$¶

In [56]:
tilesU = ['FOJO','FOHL','JMFP','DMFK','HPJP','HPHN','HKFP','HKDP','BOIO','GLEO','GLCL',
'ALIO','EPGP','EPIP','IPGK','IPIK','IKBM','IKAK','CNIP',]
tilesU = map(tuple, tilesU)
U = WangTileSet(tilesU)
U.tikz(size=1.2)

Out[56]:

## Equivalence of $\mathcal{U}$ and $\mathcal{T}_{12}$¶

In [57]:
U.is_equivalent(T12, certificate=True)

Out[57]:
(True,
{'A': '21030021300211300',
'B': '21030021031211300',
'C': '21330020331210331',
'D': '21033121331',
'E': '21030020331210331',
'F': '21030021300',
'G': '21030021300210300',
'H': '21330020331',
'I': '21033121331210331',
'J': '21030020331'},
{'K': '51160511',
'L': '60060',
'M': '51151511',
'N': '60060511',
'O': '51060',
'P': '51060511'},
Substitution 2d: {0: [[0]], 1: [[1]], 2: [[2]], 3: [[3]], 4: [[4]], 5: [[5]], 6: [[6]], 7: [[7]], 8: [[8]], 9: [[9]], 10: [[10]], 11: [[11]], 12: [[12]], 13: [[13]], 14: [[14]], 15: [[15]], 16: [[16]], 17: [[17]], 18: [[18]]})

## Computing $\mathcal{T}_{13}$¶

In [58]:
%time U.find_markers(i=2, radius=2, solver=solver) # 4min 39s with dancing_links, 13s with Gurobi

CPU times: user 11.6 s, sys: 736 ms, total: 12.3 s
Wall time: 12.2 s

Out[58]:
[[0, 1, 2, 3, 4, 5, 6, 7]]
In [59]:
M12 = [0, 1, 2, 3, 4, 5, 6, 7]
T13,s12,_ = U.find_substitution(M=M12, i=2, radius=2, solver=solver)

In [60]:
T13.tikz(size=1.2)

Out[60]:
In [61]:
show(s12)


## Computing $\mathcal{T}_{14}$¶

In [62]:
%time T13.find_markers(i=1, radius=1, solver=solver) # 5min 34s with dancing_links, 7s with Gurobi

CPU times: user 6.16 s, sys: 684 ms, total: 6.84 s
Wall time: 6.74 s

Out[62]:
[[0, 1, 3, 8, 9, 14, 15],
[4, 5, 6, 11, 16, 17, 18, 20],
[2, 7, 10, 12, 13, 19]]
In [63]:
M13 = [0, 1, 3, 8, 9, 14, 15]
T14,s13,_ = T13.find_substitution(M=M13, i=1, radius=1, solver=solver)

In [64]:
T14.tikz(size=1.2)

Out[64]:
In [65]:
show(s13)


## The self-similarity $\omega_{12}:\Omega_{12}\to\Omega_{12}$¶

In [66]:
is_equiv,f,g,permUtoT14 = U.is_equivalent(T14, certificate=True)
assert is_equiv
s12to12 = s12 * s13 * permUtoT14

In [67]:
show(s12to12)

In [68]:
s12to12.wang_tikz(U, U, font=r'\scriptsize', scale=1, codomain_color=color, ncolumns=4,
direction='right', extra_space=1.5)

Out[68]:

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

In [69]:
s0to4 = s0*s1*s2*s3p*iota
s0to4.wang_tikz(T4, T0, font=r'\scriptsize', scale=.8, codomain_color=color, ncolumns=10, direction='down',
extra_space=1.5)

Out[69]:

## The morphism $\eta\omega_6\omega_7\omega_8\omega_9\omega_{10}\omega_{11}:\Omega_{12}\to\Omega_{5}$¶

In [70]:
s5to12 = s5_sheer*s6*s7*s8*s9*s10*s11
M = matrix(2, [1,1,0,1])
s5to12sheer = s5to12.apply_matrix_transformation(M)
s5to12sheer.wang_tikz(U, T5, font=r'\scriptsize', scale=.9, ncolumns=2, extra_space=1.5)

Out[70]:

## The morphism $\pi\eta\omega_6\omega_7\omega_8\omega_9\omega_{10}\omega_{11}:\Omega_{12}\to\Omega_{4}$¶

In [71]:
s4to12 = s4_pi*s5to12
M = matrix(2, [1,1,0,1])
s4to12sheer = s4to12.apply_matrix_transformation(M)
s4to12sheer.wang_tikz(U, T4, font=r'\scriptsize', scale=.9, ncolumns=2, extra_space=1.5)

Out[71]:

## The morphism $\omega_0\omega_1\omega_2\omega_3\pi\eta\omega_6\omega_7\omega_8\omega_9\omega_{10}\omega_{11}:\Omega_{12}\to\Omega_{0}$¶

In [72]:
s0to12 = s0to4*s4to12sheer
s0to12.wang_tikz(U, T0, font=r'\scriptsize', scale=.8, codomain_color=color, id=None,
ncolumns=4, direction='right', extra_space=1.5)

Out[72]: