Substitutive structure of Jeandel-Rao aperiodic tilings

Author: Sébastien Labbé, August 23th 2018.

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
Gurobi about 4 minutes
dancing_links about 69 minutes
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:
    solver = 'dancing_links'
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
210300 60 203300 60
211300 60 210300 51
211300 60 210331 51
211300 60 213300 60
203300 600 210331 510
210300 510 210300 511
210300 510 210331 511
210331 511 211300 511
213300 600 210331 511
21030021031 51 20330020331 60
21030021300 60 20330020300 60
21030021300 60 20330020331 60
21130021031 51 21030020331 51
21130021031 51 21330020331 60
20330020300 510 21030020331 510
20330020300 510 21330020331 600
20330020331 511 21030021300 510
20330020331 511 21033121331 510
21030020331 511 21030021031 511
21033121331 511 21130021031 511
21330020331 511 21030021300 511
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
210331 511 211300 511
210300 60060 210331 51060
211300 51060 210300 51151
211300 51060 210331 51151
211300 51160 211300 51151
211300 60060 210331 51160
21030020331 511 21030021031 511
21033121331 511 21130021031 511
21330020331 511 21030021300 511
21030021031 51151 21030021300 51060
21030021031 51151 21033121331 51060
21030021300 51060 21030020331 51060
21030021300 51060 21330020331 60060
21030021300 51160 21030021300 51060
21030021300 51160 21033121331 51060
21130021031 51151 21030021031 51151
21130021031 51151 21030021300 51160
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
21030020331 511 21030021031 511
21033121331 511 21130021031 511
21330020331 511 21030021300 511
21030021031 51151 21030021300 51060
21030021300 51060 21030020331 51060
21030021300 51060 21330020331 60060
21030021300 51160 21030021300 51060
21030021300 51160 21033121331 51060
21130021031 51151 21030021300 51160
21030020331210331 511 21030021031211300 511
21033121331210331 511 21130021031211300 511
21330020331210331 511 21030021300211300 511
21030021031211300 51060 21030021300210300 51060
21030021031211300 51060 21033121331210331 51060
21030021300210300 60060 21030020331210331 51060
21030021300210300 60060 21330020331210331 60060
21030021300211300 60060 21033121331210331 51060
21130021031211300 51060 21030021300210300 51160
21130021031211300 51060 21033121331210331 51160
21130021031211300 51160 21030021031211300 51151
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
21030021300 51060 21030020331 51060
21030021300 51060 21330020331 60060
21030020331 51151511 21030021300 51060511
21033121331 51151511 21030021300 51160511
21330020331 51060511 21030020331 51060511
21330020331 51060511 21330020331 60060511
21330020331 51160511 21030021300 51060511
21330020331 51160511 21033121331 51060511
21030021031211300 51060 21033121331210331 51060
21030021300210300 60060 21030020331210331 51060
21030021300210300 60060 21330020331210331 60060
21030021300211300 60060 21033121331210331 51060
21030020331210331 51060511 21030021300210300 51060511
21030020331210331 51060511 21033121331210331 51060511
21033121331210331 51060511 21030021300210300 51160511
21033121331210331 51060511 21033121331210331 51160511
21033121331210331 51160511 21030021031211300 51151511
21033121331210331 51160511 21030021300211300 51160511
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]: