Double Square Tiles¶
Double Square tiles
If a polyomino P tiles the plane by translation, then there exists a regular tiling of the plane by P [WVL1984], i.e., where the set of translations forms a lattice. Such a polyomino was called exact by Wijshoff and van Leeuven. There are two types of regular tiling of the plane : square and hexagonal. These are characterized by the Beauquier-Nivat condition [BN1991]. Deciding whether a polyomino is exact can be done efficiently from the boundary and in linear time for square tiling [BFP2009]. Brlek, Fédou, Provençal also remarked that there exist polyominoes leading to more than one regular tilings but conjectured that any polyomino produces at most two regular square tilings. This conjecture was proved in [BBL2012]. In [BBGL2011], two infinite families of double square tiles were provided, that is polyominoes having exactly two distinct regular square tilings of the plane, namely the Christoffel tiles and the Fibonacci tiles. Finally, in [BGL2012], it was shown that any double square tile can be constructed using two simple combinatorial rules: EXTEND and SWAP.
This module is about double square tiles. Notations are chosen according to [BGL2012]. It allows to construct, study and show double square tiles. Operations TRIM, SWAP and EXTEND are implemented. Double square tiles can be shown using Sage 2D Graphics objects or using tikz.
REFERENCES:
- WVL1984
Wijshoff, H. A. G, et J. Van Leeuwen. Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino. INFORM. AND CONTROL 62 (1984): 1-25.
- BN1991
Beauquier, D., and M. Nivat. On translating one polyomino to tile the plane. Discrete & Computational Geometry 6 (1991): 575-592. doi:10.1007/BF02574705
- BFP2009
S. Brlek, J.-M Fédou, X. Provençal, On the Tiling by Translation Problem, Discrete Applied Mathematics 157 Issue 3 (2009) 464-475. doi:10.1016/j.dam.2008.05.026
- BBL2012
A. Blondin Massé, S. Brlek, S. Labbé, A parallelogram tile fills the plane by translation in at most two distinct ways, Discrete Applied Mathematics 160 (2012) 1011-1018. doi:10.1016/j.dam.2011.12.023
- BBGL2011(1,2)
A. Blondin Massé, S. Brlek, A. Garon, S. Labbé, Two infinite families of polyominoes that tile the plane by translation in two distinct ways, Theoret. Comput. Sci. 412 (2011) 4778-4786. doi:10.1016/j.tcs.2010.12.034
- BGL2012(1,2,3,4,5)
A. Blondin Massé, A. Garon, S. Labbé, Combinatorial properties of double square tiles, Theoretical Computer Science, Available online 2 November 2012. doi:10.1016/j.tcs.2012.10.040
AUTHORS:
Sébastien Labbé, 2008: initial version
Alexandre Blondin Massé, 2008: initial version
Sébastien Labbé, March 2013: rewrite for inclusion into Sage
EXAMPLES:
Double Square tile from the boundary word of a known double square:
sage: from slabbe import DoubleSquare
sage: DoubleSquare(words.fibonacci_tile(2))
Double Square Tile
w0 = 32303010 w4 = 10121232
w1 = 30323 w5 = 12101
w2 = 21232303 w6 = 03010121
w3 = 23212 w7 = 01030
(|w0|, |w1|, |w2|, |w3|) = (8, 5, 8, 5)
(d0, d1, d2, d3) = (10, 16, 10, 16)
(n0, n1, n2, n3) = (0, 0, 0, 0)
sage: from slabbe import christoffel_tile
sage: DoubleSquare(christoffel_tile(4,7))
Double Square Tile
w0 = 03 w4 = 21
w1 = 0103010103010301010301030 w5 = 2321232321232123232123212
w2 = 10103010 w6 = 32321232
w3 = 1 w7 = 3
(|w0|, |w1|, |w2|, |w3|) = (2, 25, 8, 1)
(d0, d1, d2, d3) = (26, 10, 26, 10)
(n0, n1, n2, n3) = (0, 2, 0, 0)
Double Square tile from the lengths of the \(w_i\):
sage: DoubleSquare((4,7,4,7))
Double Square Tile
w0 = 3232 w4 = 1010
w1 = 1212323 w5 = 3030101
w2 = 2121 w6 = 0303
w3 = 0101212 w7 = 2323030
(|w0|, |w1|, |w2|, |w3|) = (4, 7, 4, 7)
(d0, d1, d2, d3) = (14, 8, 14, 8)
(n0, n1, n2, n3) = (0, 0, 0, 0)
DoubleSquare tile from the words \((w_0, w_1, w_2, w_3)\):
sage: DoubleSquare(([3,2], [3], [0,3], [0,1,0,3,0]))
Double Square Tile
w0 = 32 w4 = 10
w1 = 3 w5 = 1
w2 = 03 w6 = 21
w3 = 01030 w7 = 23212
(|w0|, |w1|, |w2|, |w3|) = (2, 1, 2, 5)
(d0, d1, d2, d3) = (6, 4, 6, 4)
(n0, n1, n2, n3) = (0, 0, 0, 1)
Reduction of a double square tile:
sage: D = DoubleSquare(christoffel_tile(4,7))
sage: D.reduction()
['TRIM_1', 'TRIM_1', 'TRIM_2', 'TRIM_1', 'TRIM_0', 'TRIM_2']
sage: D.apply_reduction()
Double Square Tile
w0 = w4 =
w1 = 0 w5 = 2
w2 = w6 =
w3 = 1 w7 = 3
(|w0|, |w1|, |w2|, |w3|) = (0, 1, 0, 1)
(d0, d1, d2, d3) = (2, 0, 2, 0)
(n0, n1, n2, n3) = (0, NaN, 0, NaN)
The intermediate steps of the reduction of a double square tile:
sage: E,op = D.reduce()
sage: E
Double Square Tile
w0 = 03 w4 = 21
w1 = 010301010301030 w5 = 232123232123212
w2 = 10103010 w6 = 32321232
w3 = 1 w7 = 3
(|w0|, |w1|, |w2|, |w3|) = (2, 15, 8, 1)
(d0, d1, d2, d3) = (16, 10, 16, 10)
(n0, n1, n2, n3) = (0, 1, 0, 0)
sage: op
'TRIM_1'
sage: D.reduce_ntimes(3)
Double Square Tile
w0 = 03 w4 = 21
w1 = 01030 w5 = 23212
w2 = 10 w6 = 32
w3 = 1 w7 = 3
(|w0|, |w1|, |w2|, |w3|) = (2, 5, 2, 1)
(d0, d1, d2, d3) = (6, 4, 6, 4)
(n0, n1, n2, n3) = (0, 1, 0, 0)
Plot a double square tile and plot its reduction:
sage: D = DoubleSquare((34,21,34,21))
sage: _ = D.plot() # long time (1s)
sage: _ = D.plot_reduction() # long time (1s)
It is not said clear enough in the articles, but double square reduction also works for double square tiles that are 8-connected polyominoes:
sage: D = DoubleSquare((55,34,55,34))
sage: _ = D.plot() # long time (1s)
sage: _ = D.plot_reduction() # long time (1s)
- class slabbe.double_square_tile.DoubleSquare(data, rot180=None, steps=None)¶
Bases:
sage.structure.sage_object.SageObject
A double square tile.
We represent a double square tile by its boundary, that is a finite sequence on the alphabet \(A=\{0,1,2,3\}\) where \(0\) is a East step, \(1\) is a North step, \(2\) is a West step and \(3\) is a South step.
INPUT:
data
- can be one of the following:word - word over over the alphabet A representing the boundary of a double square tile
tuple - tuple of 4 elements (w0,w1,w2,w3) or 8 elements (w0,w1,w2,w3,w4,w5,w6,w7) such that each wi is a sequence over the alphabet A. The condition \(w_iw_{i+1} = hat(w_{i+4}w_{i+5})\) must be verified for all \(i\) modulo 8.
tuple - tuple of 4 integers, the lengths of (w0,w1,w2,w3)
rot180
- WordMorphism (default: None), involution on the alphabet A and representing a rotation of 180 degrees. If None, the morphism 0->2, 1->3, 2->0, 3->1 is considered.steps
- dict (default: None), mapping letters of A to steps in the plane. If None, the corresondance 0->(1,0), 1->(0,1), 2->(-1,0), 3->(0,-1) is considered.
EXAMPLES:
From a double square:
sage: from slabbe import DoubleSquare sage: DoubleSquare(words.fibonacci_tile(1)) Double Square Tile w0 = 32 w4 = 10 w1 = 3 w5 = 1 w2 = 03 w6 = 21 w3 = 0 w7 = 2 (|w0|, |w1|, |w2|, |w3|) = (2, 1, 2, 1) (d0, d1, d2, d3) = (2, 4, 2, 4) (n0, n1, n2, n3) = (1, 0, 1, 0) sage: DoubleSquare(words.fibonacci_tile(2)) Double Square Tile w0 = 32303010 w4 = 10121232 w1 = 30323 w5 = 12101 w2 = 21232303 w6 = 03010121 w3 = 23212 w7 = 01030 (|w0|, |w1|, |w2|, |w3|) = (8, 5, 8, 5) (d0, d1, d2, d3) = (10, 16, 10, 16) (n0, n1, n2, n3) = (0, 0, 0, 0)
sage: from slabbe import christoffel_tile sage: DoubleSquare(christoffel_tile(9,7)) Double Square Tile w0 = 03 w4 = 21 w1 = 0101030101030101030 w5 = 2323212323212323212 w2 = 101010301010301010301010 w6 = 323232123232123232123232 w3 = 1 w7 = 3 (|w0|, |w1|, |w2|, |w3|) = (2, 19, 24, 1) (d0, d1, d2, d3) = (20, 26, 20, 26) (n0, n1, n2, n3) = (0, 0, 1, 0)
From the \(w_i\):
sage: D = DoubleSquare(([],[],[0,1,0,1],[0,1])) sage: D.rot180 WordMorphism: 0->2, 1->3, 2->0, 3->1 sage: D._steps {0: (1, 0), 1: (0, 1), 2: (-1, 0), 3: (0, -1)} sage: D Double Square Tile w0 = w4 = w1 = w5 = w2 = 0101 w6 = 3232 w3 = 01 w7 = 32 (|w0|, |w1|, |w2|, |w3|) = (0, 0, 4, 2) (d0, d1, d2, d3) = (2, 4, 2, 4) (n0, n1, n2, n3) = (0, 0, 2, 0)
One may also provide strings as long as other arguments are consistent:
sage: steps = {'0':(1,0), '1':(0,1), '2':(-1,0), '3': (0,-1)} sage: rot180 = WordMorphism('0->2,2->0,3->1,1->3') sage: DoubleSquare(('','','0101','01','','','3232','32'), rot180, steps) Double Square Tile w0 = w4 = w1 = w5 = w2 = 0101 w6 = 3232 w3 = 01 w7 = 32 (|w0|, |w1|, |w2|, |w3|) = (0, 0, 4, 2) (d0, d1, d2, d3) = (2, 4, 2, 4) (n0, n1, n2, n3) = (0, 0, 2, 0)
The first four words wi are sufficient:
sage: steps = {'0':(1,0), '1':(0,1), '2':(-1,0), '3': (0,-1)} sage: rot180 = WordMorphism('0->2,2->0,3->1,1->3') sage: DoubleSquare(('','','0101','01'), rot180, steps) Double Square Tile w0 = w4 = w1 = w5 = w2 = 0101 w6 = 3232 w3 = 01 w7 = 32 (|w0|, |w1|, |w2|, |w3|) = (0, 0, 4, 2) (d0, d1, d2, d3) = (2, 4, 2, 4) (n0, n1, n2, n3) = (0, 0, 2, 0)
- alphabet()¶
Returns the python set of the letters that occurs in the boundary word.
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.alphabet() {0, 1, 2, 3}
- apply(L)¶
Return the double square obtained after the application of a list of operations.
INPUT:
L
- list, list of strings
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.apply(['SWAP_0', 'EXTEND_3', 'TRIM_3']) Double Square Tile w0 = 01030323 w4 = 23212101 w1 = 21232303010 w5 = 03010121232 w2 = 30323212 w6 = 12101030 w3 = 10121232303 w7 = 32303010121 (|w0|, |w1|, |w2|, |w3|) = (8, 11, 8, 11) (d0, d1, d2, d3) = (22, 16, 22, 16) (n0, n1, n2, n3) = (0, 0, 0, 0)
sage: D.apply(D.reduction()) Double Square Tile w0 = w4 = w1 = 3 w5 = 1 w2 = w6 = w3 = 2 w7 = 0 (|w0|, |w1|, |w2|, |w3|) = (0, 1, 0, 1) (d0, d1, d2, d3) = (2, 0, 2, 0) (n0, n1, n2, n3) = (0, NaN, 0, NaN)
- apply_morphism(m)¶
INPUT:
m
- a WordMorphism
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: m = WordMorphism({0:[0],1:[1,0,1],2:[2],3:[3,2,3]}) sage: D.apply_morphism(m) Double Square Tile w0 = 3232 w4 = 1010 w1 = 323 w5 = 101 w2 = 0323 w6 = 2101 w3 = 0 w7 = 2 (|w0|, |w1|, |w2|, |w3|) = (4, 3, 4, 1) (d0, d1, d2, d3) = (4, 8, 4, 8) (n0, n1, n2, n3) = (1, 0, 1, 0)
- apply_reduction()¶
Apply the reduction algorithm on self.
This is equivalent to
self.apply(self.reduction())
.EXAMPLES:
sage: from slabbe import DoubleSquare, christoffel_tile sage: D = DoubleSquare(christoffel_tile(9,7)) sage: D.apply_reduction() Double Square Tile w0 = w4 = w1 = 0 w5 = 2 w2 = w6 = w3 = 1 w7 = 3 (|w0|, |w1|, |w2|, |w3|) = (0, 1, 0, 1) (d0, d1, d2, d3) = (2, 0, 2, 0) (n0, n1, n2, n3) = (0, NaN, 0, NaN)
sage: D = DoubleSquare((5,7,4,13)) sage: D.apply_reduction() Double Square Tile w0 = w4 = w1 = w5 = w2 = 1 w6 = 0 w3 = w7 = (|w0|, |w1|, |w2|, |w3|) = (0, 0, 1, 0) (d0, d1, d2, d3) = (0, 1, 0, 1) (n0, n1, n2, n3) = (NaN, 0, NaN, 0)
sage: D = DoubleSquare((5,2,4,13)) sage: D.reduce_ntimes(3) Double Square Tile w0 = 0 w4 = 0 w1 = 12 w5 = 32 w2 = 01 w6 = 03 w3 = 2 w7 = 2 (|w0|, |w1|, |w2|, |w3|) = (1, 2, 2, 1) (d0, d1, d2, d3) = (3, 3, 3, 3) (n0, n1, n2, n3) = (0, 0, 0, 0) sage: D.apply_reduction() Traceback (most recent call last): ... ValueError: not reducible, because self is nondegenerate and d_0 == d_1 == 3
- boundary_word()¶
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.boundary_word() Path: 3230301030323212323032321210121232121010...
- d(i)¶
Return the integer d_i.
The value of \(d_i\) is defined as \(d_i=|w_{i-1}|+|w_{i+1}|\).
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: [D.d(i) for i in range(8)] [10, 16, 10, 16, 10, 16, 10, 16]
- extend(i)¶
Apply \(EXTEND_i\) on self.
This adds a period of length \(d_i\) to \(w_i\) and \(w_{i+4}\).
INPUT:
i
- integer
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.extend(3) Double Square Tile w0 = 32303010 w4 = 10121232 w1 = 30323 w5 = 12101 w2 = 21232303 w6 = 03010121 w3 = 232121012123230323212 w7 = 010303230301012101030 (|w0|, |w1|, |w2|, |w3|) = (8, 5, 8, 21) (d0, d1, d2, d3) = (26, 16, 26, 16) (n0, n1, n2, n3) = (0, 0, 0, 1)
- factorization_points()¶
Returns the eight factorization points of this configuration
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: D.factorization_points() [0, 2, 3, 5, 6, 8, 9, 11]
- hat()¶
Return the hat function returning the reversal of a word path.
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.w(0) Path: 32303010 sage: D.hat(D.w(0)) Path: 23212101
- height()¶
Returns the width of this polyomino, i.e. the difference between its uppermost and lowermost coordinates
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.height() 9
sage: D = DoubleSquare((34,21,34,21)) sage: D.height() 23
- is_degenerate()¶
Return whether self is degenerate.
A double square is degenerate if one of the \(w_i\) is empty.
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: D.is_degenerate() False
sage: rot180 = WordMorphism('0->2,2->0,3->1,1->3') sage: D = DoubleSquare(('','0','10','1'), rot180) sage: D.is_degenerate() True
- is_flat()¶
Return whether self is flat.
A double square is flat if one of the \(w_iw_{i+1}\) is empty.
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: D.is_flat() False
sage: rot180 = WordMorphism('0->2,2->0,3->1,1->3') sage: D = DoubleSquare(('','','0101','01'), rot180) sage: D.is_flat() True
- is_morphic_pentamino()¶
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: D.is_morphic_pentamino() True
- is_singular()¶
Return whether self is singular.
A double square is singular if there exists \(i\) such that \(w_{i-1}\) and \(w_{i+1}\) are empty, equivalently if \(d_i=0\).
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: D.is_singular() False
sage: rot180 = WordMorphism('0->2,2->0,3->1,1->3') sage: D = DoubleSquare(('','03010','','1011'), rot180) sage: D.is_singular() True
- latex_8_tuple()¶
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.latex_8_tuple() ('{\\bf 32303010}', '{\\bf 30323}', '{\\bf 21232303}', '{\\bf 23212}', '{\\bf 10121232}', '{\\bf 12101}', '{\\bf 03010121}', '{\\bf 01030}')
- latex_array()¶
Return a LaTeX array of self.
This code was used to create Table 1 in [BGL2012].
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: print(D.latex_array()) \begin{array}{lllllll} i & w_i & u_i & v_i & |w_i| & d_i & n_i \\ \hline 0 & {\bf 32} & {\bf } & {\bf 32} & 2 & 2 & 1\\ 1 & {\bf 3} & {\bf 3} & {\bf 032} & 1 & 4 & 0\\ 2 & {\bf 03} & {\bf } & {\bf 03} & 2 & 2 & 1\\ 3 & {\bf 0} & {\bf 0} & {\bf 103} & 1 & 4 & 0\\ 4 & {\bf 10} & {\bf } & {\bf 10} & 2 & 2 & 1\\ 5 & {\bf 1} & {\bf 1} & {\bf 210} & 1 & 4 & 0\\ 6 & {\bf 21} & {\bf } & {\bf 21} & 2 & 2 & 1\\ 7 & {\bf 2} & {\bf 2} & {\bf 321} & 1 & 4 & 0\\ \hline \end{array}
- latex_table()¶
Returns a Latex expression of a table containing the parameters of this double square.
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.latex_table() \begin{tabular}{|c|} \hline \\ \begin{tikzpicture} [first/.style={circle,draw=black,fill=gray, inner sep=0pt, minimum size=3pt}, second/.style={rectangle,draw=black,fill=white, inner sep=0pt, minimum size=3pt}] ... \end{tikzpicture} \\[1ex] \hline\\ $(w_0,w_1,w_2,w_3) = (8,5,8,5)$ \\ $u_0 = 32303010$\quad $u_1 = 30323$\\$u_2 = 21232303$\quad $u_3 = 23212$\\ $v_0 = 30$\quad $v_1 = 21232303010$\\$v_2 = 23$\quad $v_3 = 10121232303$\\ $(n_0,n_1,n_2,n_3) = (0,0,0,0)$ \\ Turning number = -1\\ Self-avoiding = True\\ \hline \end{tabular}
- n(i)¶
Return the integer n_i.
The value of \(n_i\) is defined as the quotient of \(|w_i|\) by \(d_i\).
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: [D.n(i) for i in range(8)] [0, 0, 0, 0, 0, 0, 0, 0]
sage: A = D.extend(1).extend(1).extend(1).extend(1) sage: [A.n(i) for i in range(8)] [0, 4, 0, 0, 0, 4, 0, 0]
If \(d_i=0\) then \(n_i\) is not defined:
sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: B = D.reduce_ntimes(2) sage: [B.n(i) for i in range(8)] [0, NaN, 0, NaN, 0, NaN, 0, NaN]
- plot(pathoptions={'rgbcolor': 'black', 'thickness': 3}, fill=True, filloptions={'rgbcolor': 'black', 'alpha': 0.2}, startpoint=True, startoptions={'rgbcolor': 'black', 'pointsize': 100}, endarrow=True, arrowoptions={'rgbcolor': 'black', 'arrowsize': 5, 'width': 3}, gridlines=False, gridoptions={}, axes=False)¶
Returns a 2d Graphics illustrating the double square tile associated to this configuration including the factorizations points.
INPUT:
pathoptions
- (dict, default:dict(rgbcolor=’red’,thickness=3)), options for the path drawingfill
- (boolean, default: True), if fill is True and if the path is closed, the inside is coloredfilloptions
- (dict, default:dict(rgbcolor=’red’,alpha=0.2)), ptions for the inside fillingstartpoint
- (boolean, default: True), draw the start point?startoptions
- (dict, default:dict(rgbcolor=’red’,pointsize=100)) options for the start point drawingendarrow
- (boolean, default: True), draw an arrow end at the end?arrowoptions
- (dict, default:dict(rgbcolor=’red’,arrowsize=20, width=3)) options for the end point arrowgridlines
- (boolean, default: False), show gridlines?gridoptions
- (dict, default: {}), options for the gridlinesaxes
- (boolean, default: False), options for the axes
EXAMPLES:
The cross of area 5 together with its double square factorization points:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: _ = D.plot() # long time (1s)
- plot_reduction(ncols=3, options={})¶
Return a graphics array of the reduction.
INPUT:
ncols
- integer (default:3
), number of columnsoptions
- dict (default:{}
), options given to the plot method of each double square
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: _ = D.plot_reduction() # long time (1s)
Using the color options:
sage: p = dict(rgbcolor='red', thickness=1) sage: q = dict(rgbcolor='blue', alpha=1) sage: options = dict(endarrow=False,startpoint=False,pathoptions=p,filloptions=q) sage: _ = D.plot_reduction(options=options) # long time (1s)
- reduce()¶
Reduces self by the application of TRIM or otherwise SWAP.
INPUT:
self
- non singular double square tile on the alphabet \({0,1,2,3}\) such that its turning number is +1 or -1.
OUTPUT:
DoubleSquare - the reduced double square
string - the operation which was performed
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare((34,21,34,21)) sage: E,op = D.reduce() sage: E Double Square Tile w0 = 32303010 w4 = 10121232 w1 = 303232123230301030323 w5 = 121010301012123212101 w2 = 21232303 w6 = 03010121 w3 = 232121012123230323212 w7 = 010303230301012101030 (|w0|, |w1|, |w2|, |w3|) = (8, 21, 8, 21) (d0, d1, d2, d3) = (42, 16, 42, 16) (n0, n1, n2, n3) = (0, 1, 0, 1) sage: op 'SWAP_1'
sage: D = DoubleSquare((1,2,2,1)) sage: D Double Square Tile w0 = 1 w4 = 1 w1 = 23 w5 = 03 w2 = 12 w6 = 10 w3 = 3 w7 = 3 (|w0|, |w1|, |w2|, |w3|) = (1, 2, 2, 1) (d0, d1, d2, d3) = (3, 3, 3, 3) (n0, n1, n2, n3) = (0, 0, 0, 0) sage: D.reduce() Traceback (most recent call last): ... ValueError: not reducible, because self is nondegenerate and d_0 == d_1 == 3
TESTS:
sage: D = DoubleSquare((5,4,3,4)) sage: D.reduce() Traceback (most recent call last): ... ValueError: not reducible, because self is nondegenerate and d_0 == d_1 == 8
- reduce_ntimes(iteration=1)¶
Reduces the double square self until it is singular.
INPUT:
iteration
- integer (default:1
), number of iterations to perform
OUTPUT:
DoubleSquare
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare((34,21,34,21)) sage: D.reduce_ntimes(10) Double Square Tile w0 = w4 = w1 = 3 w5 = 1 w2 = w6 = w3 = 2 w7 = 0 (|w0|, |w1|, |w2|, |w3|) = (0, 1, 0, 1) (d0, d1, d2, d3) = (2, 0, 2, 0) (n0, n1, n2, n3) = (0, NaN, 0, NaN)
- reduction()¶
Return the list of operations to reduce self to a singular double square.
OUTPUT:
list of strings
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare((34,21,34,21)) sage: D.reduction() ['SWAP_1', 'TRIM_1', 'TRIM_3', 'SWAP_1', 'TRIM_1', 'TRIM_3', 'TRIM_0', 'TRIM_2']
sage: from slabbe import christoffel_tile sage: D = DoubleSquare(christoffel_tile(9,7)) sage: D.reduction() ['TRIM_2', 'TRIM_1', 'TRIM_1', 'TRIM_1', 'TRIM_0', 'TRIM_2', 'TRIM_2']
- reverse()¶
Apply \(REVERSE\) on self.
This reverses the words \(w_i\).
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D Double Square Tile w0 = 32303010 w4 = 10121232 w1 = 30323 w5 = 12101 w2 = 21232303 w6 = 03010121 w3 = 23212 w7 = 01030 (|w0|, |w1|, |w2|, |w3|) = (8, 5, 8, 5) (d0, d1, d2, d3) = (10, 16, 10, 16) (n0, n1, n2, n3) = (0, 0, 0, 0) sage: D.reverse() Double Square Tile w0 = 21232 w4 = 03010 w1 = 30323212 w5 = 12101030 w2 = 32303 w6 = 10121 w3 = 01030323 w7 = 23212101 (|w0|, |w1|, |w2|, |w3|) = (5, 8, 5, 8) (d0, d1, d2, d3) = (16, 10, 16, 10) (n0, n1, n2, n3) = (0, 0, 0, 0) sage: D.reverse().reverse() == D True
- shift()¶
Apply \(SHIFT\) on self.
This replaces \(w_i\) by \(w_{i+1}\).
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D Double Square Tile w0 = 32303010 w4 = 10121232 w1 = 30323 w5 = 12101 w2 = 21232303 w6 = 03010121 w3 = 23212 w7 = 01030 (|w0|, |w1|, |w2|, |w3|) = (8, 5, 8, 5) (d0, d1, d2, d3) = (10, 16, 10, 16) (n0, n1, n2, n3) = (0, 0, 0, 0) sage: D.shift() Double Square Tile w0 = 30323 w4 = 12101 w1 = 21232303 w5 = 03010121 w2 = 23212 w6 = 01030 w3 = 10121232 w7 = 32303010 (|w0|, |w1|, |w2|, |w3|) = (5, 8, 5, 8) (d0, d1, d2, d3) = (16, 10, 16, 10) (n0, n1, n2, n3) = (0, 0, 0, 0) sage: D.shift().shift().shift().shift().shift().shift().shift().shift() == D True sage: D.shift().shift().shift().shift() == D False
- swap(i)¶
Apply \(SWAP_i\) on self.
This replaces \(w_j\) by \(\hat{w_{j+4}}\) for each \(j=i,i+2,i+4,i+6\) and \(w_j=(u_j*v_j)^{n_j}u_j\) by \((v_j*u_j)^{n_j}v_j\) for each \(j=i+1,i+3,i+5,i+7\). This is an involution if the \(u_j\) are non empty.
INPUT:
i
- integer
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D Double Square Tile w0 = 32303010 w4 = 10121232 w1 = 30323 w5 = 12101 w2 = 21232303 w6 = 03010121 w3 = 23212 w7 = 01030 (|w0|, |w1|, |w2|, |w3|) = (8, 5, 8, 5) (d0, d1, d2, d3) = (10, 16, 10, 16) (n0, n1, n2, n3) = (0, 0, 0, 0) sage: D.swap(1) Double Square Tile w0 = 30 w4 = 12 w1 = 32303 w5 = 10121 w2 = 23 w6 = 01 w3 = 21232 w7 = 03010 (|w0|, |w1|, |w2|, |w3|) = (2, 5, 2, 5) (d0, d1, d2, d3) = (10, 4, 10, 4) (n0, n1, n2, n3) = (0, 1, 0, 1)
- tikz_boxed(scale=1, boxsize=10)¶
Return a tikzpicture of self included in a box.
INPUT:
scale
- number (default:1
), tikz scaleboxsize
- integer (default:10
), size of the box. If the width and height of the double square is less than the boxsize, then unit step are of size1
and the \((w_i)\) 8-tuple is added below the figure. Otherwise, if the width or height is larger than the boxsize, then the unit step are made smaller to fit the box and the \((w_i)\) 8-tuple is not shown.
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: D.tikz_boxed() \begin{tabular}{c} \begin{tikzpicture} [scale=1] \filldraw[-to, very thick, draw=black, fill=black!20] (0.000, 0.000) -- (0.000, -1.00) -- (-1.00, -1.00) -- (-1.00, -2.00) -- (0.000, -2.00) -- (0.000, -3.00) -- (1.00, -3.00) -- (1.00, -2.00) -- (2.00, -2.00) -- (2.00, -1.00) -- (1.00, -1.00) -- (1.00, 0.000) -- (0.000, 0.000); \node[first] at (0.0000, 0.0000) {}; \node[first] at (-1.000, -2.000) {}; \node[first] at (1.000, -3.000) {}; \node[first] at (2.000, -1.000) {}; \node[second] at (-1.000, -1.000) {}; \node[second] at (0.0000, -3.000) {}; \node[second] at (2.000, -2.000) {}; \node[second] at (1.000, 0.0000) {}; \end{tikzpicture} \\ $({\bf 32},{\bf 3},{\bf 03},{\bf 0},$ \\ $\phantom{((}{\bf 10},{\bf 1},{\bf 21},{\bf 2})$ \\ \end{tabular}
Smaller boxsize:
sage: D.tikz_boxed(boxsize=1.5) \begin{tikzpicture} [scale=1] \filldraw[-to, very thick, draw=black, fill=black!20] (0.000, 0.000) -- (0.000, -0.500) -- (-0.500, -0.500) -- (-0.500, -1.00) -- (0.000, -1.00) -- (0.000, -1.50) -- (0.500, -1.50) -- (0.500, -1.00) -- (1.00, -1.00) -- (1.00, -0.500) -- (0.500, -0.500) -- (0.500, 0.000) -- (0.000, 0.000); \node[first] at (0.0000, 0.0000) {}; \node[first] at (-0.5000, -1.000) {}; \node[first] at (0.5000, -1.500) {}; \node[first] at (1.000, -0.5000) {}; \node[second] at (-0.5000, -0.5000) {}; \node[second] at (0.0000, -1.500) {}; \node[second] at (1.000, -1.000) {}; \node[second] at (0.5000, 0.0000) {}; \end{tikzpicture}
- tikz_commutative_diagram(tile, N=1, scale=(1, 1), labels=True, newcommand=True)¶
Return a tikz commutative diagram for the composition.
INPUT:
tile
- WordMorphism, a square tileN
- integer (default:1
), length of the diagramscale
- tuple of number (default:(1,1)
), one for each linelabels
- arrow labels (default:True
). It may take the following values:True
- prints TRIM, SWAP, etc.'T'
- prints T_i, etc.False
- print nothing
newcommand
- bool (default:True
), whether newcommand which defines\SWAP
,\TRIM
, etc.
EXAMPLES:
The following command creates the tikz code for Figure 16 in [BGL2012]:
sage: from slabbe import DoubleSquare sage: fibo2 = words.fibonacci_tile(2) sage: S = WordMorphism({0:[0,0],1:[1,0,1],2:[2,2],3:[3,2,3]}, codomain=fibo2.parent()) sage: cfibo2 = DoubleSquare(fibo2) sage: options = dict(tile=S,N=3,scale=(0.25,0.15),labels=True,newcommand=True) sage: s = cfibo2.tikz_commutative_diagram(**options) # long time (2s) sage: s # long time \documentclass[tikz]{standalone} \begin{document} \newcommand{\TRIM}{\textsc{trim}} \newcommand{\EXTEND}{\textsc{extend}} \newcommand{\SWAP}{\textsc{swap}} \newcommand{\SHIFT}{\textsc{shift}} \newcommand{\REVERSE}{\textsc{reverse}} ... 105 lines not printed (12001 characters in total). ... \path[thick, ->] (q0) edge node[midway, left] {$\varphi$} (r0); \path[thick, ->] (q1) edge node[midway, left] {$\varphi$} (r1); \path[thick, ->] (q2) edge node[midway, left] {$\varphi$} (r2); \path[thick, ->] (q3) edge node[midway, left] {$\varphi$} (r3); \end{tikzpicture} \end{document}
- tikz_reduction(scale=1, ncols=3, gridstep=5, labels=True, newcommand=True)¶
INPUT:
scale
- numberncols
- integer, number of columns displaying the reductiongridstep
- number (default:5
), the gridstep for the snake node positionslabels
- arrow labels (default:True
). It may take the following values:True
- prints TRIM, SWAP, etc.'T'
- prints T_i, etc.False
- print nothing
newcommand
- bool (default:True
), whether newcommand which defines\SWAP
,\TRIM
, etc.
EXAMPLES:
sage: from slabbe import DoubleSquare sage: fibo2 = words.fibonacci_tile(2) sage: cfibo2 = DoubleSquare(fibo2) sage: s = cfibo2.tikz_reduction(scale=0.5,ncols=4,labels=True) sage: s \documentclass[tikz]{standalone} \usetikzlibrary{pgfplots.groupplots} \begin{document} \newcommand{\TRIM}{\textsc{trim}} \newcommand{\EXTEND}{\textsc{extend}} \newcommand{\SWAP}{\textsc{swap}} \newcommand{\SHIFT}{\textsc{shift}} \newcommand{\REVERSE}{\textsc{reverse}} ... 103 lines not printed (6363 characters in total). ... \path[->] (q1) edge node[midway, rectangle, fill=white, rotate=90] {$\TRIM_1$} (q2); \path[->] (q2) edge node[midway, rectangle, fill=white, rotate=90] {$\TRIM_3$} (q3); \path[->] (q3) edge node[midway, rectangle, fill=white] {$\TRIM_0$} (q4); \path[->] (q4) edge node[midway, rectangle, fill=white, rotate=90] {$\TRIM_2$} (q5); \end{tikzpicture} \end{document}
sage: S = WordMorphism({0:[0,0],1:[1,0,1],2:[2,2],3:[3,2,3]}, codomain=fibo2.parent()) sage: cSfibo2 = cfibo2.apply_morphism(S) sage: s = cSfibo2.tikz_reduction(scale=0.15,ncols=4,labels='T') sage: s \documentclass[tikz]{standalone} \usetikzlibrary{pgfplots.groupplots} \begin{document} \newcommand{\TRIM}{\textsc{trim}} \newcommand{\EXTEND}{\textsc{extend}} \newcommand{\SWAP}{\textsc{swap}} \newcommand{\SHIFT}{\textsc{shift}} \newcommand{\REVERSE}{\textsc{reverse}} ... 93 lines not printed (9437 characters in total). ... \path[thick, ->] (q1) edge node[midway, above] {$T_2$} (q2); \path[thick, ->] (q2) edge node[midway, above] {$T_3$} (q3); \path[thick, ->] (q3) edge node[midway, above] {$T_4$} (q4); \path[thick, ->] (q4) edge node[midway, above] {$T_5$} (q5); \end{tikzpicture} \end{document}
- tikz_tiling(nx=2, ny=2, kind=1, rectangle=None, clip=None)¶
Return a tikz of the tiling.
INPUT:
nx
– integerny
– integerkind
– integer, 1 or 2, first or second tilingrectangle
– list of two points (to practice for the clip)clip
– list of two points
EXAMPLES:
sage: from slabbe import DoubleSquare sage: d = DoubleSquare((5,8,5,8)) sage: t = d.tikz_tiling(nx=4, ny=4) sage: t = d.tikz_tiling(nx=4, ny=4, kind=2)
- tikz_trajectory(step=1, arrow='->')¶
Returns a tikz string describing the double square induced by this configuration together with its factorization points
The factorization points respectively get the tikz attribute ‘first’ and ‘second’ so that when including it in a tikzpicture environment, it is possible to modify the way those points appear.
INPUT:
step
- integer (default:1
)arrow
- string (default:->
), tikz arrow shape
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: D.tikz_trajectory() \filldraw[->, very thick, draw=black, fill=black!20] (0.000, 0.000) -- (0.000, -1.00) -- (-1.00, -1.00) -- (-1.00, -2.00) -- (0.000, -2.00) -- (0.000, -3.00) -- (1.00, -3.00) -- (1.00, -2.00) -- (2.00, -2.00) -- (2.00, -1.00) -- (1.00, -1.00) -- (1.00, 0.000) -- (0.000, 0.000); \node[first] at (0.0000, 0.0000) {}; \node[first] at (-1.000, -2.000) {}; \node[first] at (1.000, -3.000) {}; \node[first] at (2.000, -1.000) {}; \node[second] at (-1.000, -1.000) {}; \node[second] at (0.0000, -3.000) {}; \node[second] at (2.000, -2.000) {}; \node[second] at (1.000, 0.0000) {};
- translation_vectors()¶
Returns two pairs of translation vectors of the two associated tiling.
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: D.translation_vectors() (((-1, -2), (2, -1)), ((1, -2), (2, 1)))
- trim(i)¶
Apply \(TRIM_i\) on self.
This removes a period of length \(d_i\) to \(w_i\) and \(w_{i+4}\).
INPUT:
i
- integer
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare((3,6,3,2)) sage: D.trim(1) Double Square Tile w0 = 212 w4 = 030 w1 = w5 = w2 = 303 w6 = 121 w3 = 03 w7 = 21 (|w0|, |w1|, |w2|, |w3|) = (3, 0, 3, 2) (d0, d1, d2, d3) = (2, 6, 2, 6) (n0, n1, n2, n3) = (1, 0, 1, 0)
sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.extend(3).trim(3) Double Square Tile w0 = 32303010 w4 = 10121232 w1 = 30323 w5 = 12101 w2 = 21232303 w6 = 03010121 w3 = 23212 w7 = 01030 (|w0|, |w1|, |w2|, |w3|) = (8, 5, 8, 5) (d0, d1, d2, d3) = (10, 16, 10, 16) (n0, n1, n2, n3) = (0, 0, 0, 0)
- turning_number()¶
Return the turning number of self.
INPUT:
self
- double square defined on the alphabet of integers \(\{0,1,2,3\}\)
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: D.turning_number() 1 sage: D.reverse().turning_number() -1
Turning number of a degenerate double square:
sage: D = DoubleSquare(([],[0],[1,0],[1])) sage: D.turning_number() 1
Turning number of a singular double square:
sage: D = DoubleSquare(([],[0,3,0,1,0],[],[1,0,1,1])) sage: D.turning_number() 1
Turning number of a flat double square:
sage: D = DoubleSquare(([],[],[0,1,0,1],[0,1])) sage: D.turning_number() 0
- u(i)¶
Return the word u_i.
The word \(u_i\) is the unique word such that \(w_i=(u_i*v_i)^{n_i}u_i\) where \(0\leq |u_i| < d_i\).
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.u(1) Path: 30323
sage: rot180 = WordMorphism('0->2,2->0,3->1,1->3') sage: steps = {'0':(1,0), '1':(0,1), '2':(-1,0), '3': (0,-1)} sage: D = DoubleSquare(('','03010','','1011'), rot180, steps) sage: D.u(0) word: sage: D.u(1) Traceback (most recent call last): ... ValueError: u_1 is not defined when d_1 == 0
- v(i)¶
Return the word v_i.
The word \(v_i\) is the unique word such that \(w_i=(u_i*v_i)^{n_i}u_i\) where \(0\leq |u_i| < d_i\), \(\hat{w_{i-3}}w_{i-1}=u_iv_i\) and \(0 < |u_i| \leq d_i\).
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.v(1) Path: 21232303010
sage: rot180 = WordMorphism('0->2,2->0,3->1,1->3') sage: steps = {'0':(1,0), '1':(0,1), '2':(-1,0), '3': (0,-1)} sage: D = DoubleSquare(('','03010','','1011'), rot180, steps) sage: D.v(0) word: 030103323 sage: D.v(1) Traceback (most recent call last): ... ValueError: v_1 is not defined when d_1 == 0
- verify_definition()¶
Checks that the input verifies the definition.
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.verify_definition()
sage: DoubleSquare(([],[0],[0,1,0,1],[0,1])) Traceback (most recent call last): ... AssertionError: wiwi+1 = hat(wi+4,wi+5) is not verified for i=1
- w(i)¶
Return the factor w_i
This corresponds to the new definition of configuration (solution).
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(1)) sage: [D.w(i) for i in range(8)] [Path: 32, Path: 3, Path: 03, Path: 0, Path: 10, Path: 1, Path: 21, Path: 2]
sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: [D.w(i) for i in range(8)] [Path: 32303010, Path: 30323, Path: 21232303, Path: 23212, Path: 10121232, Path: 12101, Path: 03010121, Path: 01030]
- width()¶
Returns the width of this polyomino, i.e. the difference between its rightmost and leftmost coordinates
EXAMPLES:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(words.fibonacci_tile(2)) sage: D.width() 9
sage: D = DoubleSquare((34,21,34,21)) sage: D.width() 23
- slabbe.double_square_tile.christoffel_tile(p, q)¶
Returns the \((p,q)\) Christoffel Tile [BBGL2011].
EXAMPLES:
sage: from slabbe import christoffel_tile sage: christoffel_tile(7,9) Path: 0301030101030101030101030103010103010103… sage: christoffel_tile(9,7) Path: 0301010301010301010301010103010103010103… sage: christoffel_tile(2,3) Path: 03010301010301012123212323212323 sage: christoffel_tile(0,1) Path: 03012123 sage: print(christoffel_tile(4,5)) 03010301010301010301010301012123212323212323212323212323
- slabbe.double_square_tile.double_hexagon_from_boundary_word(ds)¶
Creates a double square object from the boundary word of a double square tile.
INPUT:
ds
- word, the boundary of a double square. The parent alphabet is assumed to be in the order : East, North, West, South.
OUTPUT:
tuple - tuple of 8 words over the alphabet A
WordMorphism, involution on the alphabet A and representing a rotation of 180 degrees.
dict - mapping letters of A to steps in the plane.
EXAMPLES:
sage: from slabbe.double_square_tile import double_square_from_boundary_word sage: fibo = words.fibonacci_tile sage: W, rot180, steps = double_square_from_boundary_word(fibo(1)) sage: [len(w) for w in W] [2, 1, 2, 1, 2, 1, 2, 1] sage: W, rot180, steps = double_square_from_boundary_word(fibo(2)) sage: [len(w) for w in W] [8, 5, 8, 5, 8, 5, 8, 5] sage: W, rot180, steps = double_square_from_boundary_word(fibo(3)) # long time (6s) sage: [len(w) for w in W] # long time [34, 21, 34, 21, 34, 21, 34, 21] sage: rot180 # long time WordMorphism: 0->2, 1->3, 2->0, 3->1
- slabbe.double_square_tile.double_hexagon_from_integers(l0, l1, l2, l3, l4, l5)¶
Creates a double hexagon from the lengths of the \(w_i\).
INPUT:
l0
- integer, length of \(w_0\)l1
- integer, length of \(w_1\)l2
- integer, length of \(w_2\)l3
- integer, length of \(w_3\)l4
- integer, length of \(w_4\)l5
- integer, length of \(w_5\)
OUTPUT:
tuple - tuple of 12 words over alphabet A
WordMorphism, involution on the alphabet A and representing a rotation of 180 degrees.
dict - mapping letters of A to steps in the plane.
EXAMPLES:
It seems difficult to find examples that do not overlap. Here are some on the square grid:
sage: from slabbe.double_square_tile import double_hexagon_from_integers sage: w,rot180,steps = double_hexagon_from_integers(1,3,1,6,1,6) sage: w # alphabet is random (Path: 2, Path: 222, Path: 2, Path: 323232, Path: 3, Path: 030303, Path: 0, Path: 000, Path: 0, Path: 101010, Path: 1, Path: 212121) sage: w,rot180,steps = double_hexagon_from_integers(1,10,1,5,1,10)
On the hexagonal grid:
sage: w,rot180,steps = double_hexagon_from_integers(1,2,1,2,1,2) sage: w,rot180,steps = double_hexagon_from_integers(2,5,2,5,2,5) sage: w,rot180,steps = double_hexagon_from_integers(5,14,5,14,5,14) # une fleur! sage: w,rot180,steps = double_hexagon_from_integers(5,22,5,22,5,22) sage: w,rot180,steps = double_hexagon_from_integers(5,38,5,38,5,38)
To plot them:
sage: prod(w).plot() # long time Graphics object consisting of 4 graphics primitives
- slabbe.double_square_tile.double_square_from_boundary_word(ds)¶
Creates a double square object from the boundary word of a double square tile.
INPUT:
ds
- word, the boundary of a double square. The parent alphabet is assumed to be in the order : East, North, West, South.
OUTPUT:
tuple - tuple of 8 words over the alphabet A
WordMorphism, involution on the alphabet A and representing a rotation of 180 degrees.
dict - mapping letters of A to steps in the plane.
EXAMPLES:
sage: from slabbe.double_square_tile import double_square_from_boundary_word sage: fibo = words.fibonacci_tile sage: W, rot180, steps = double_square_from_boundary_word(fibo(1)) sage: [len(w) for w in W] [2, 1, 2, 1, 2, 1, 2, 1] sage: W, rot180, steps = double_square_from_boundary_word(fibo(2)) sage: [len(w) for w in W] [8, 5, 8, 5, 8, 5, 8, 5] sage: W, rot180, steps = double_square_from_boundary_word(fibo(3)) # long time (6s) sage: [len(w) for w in W] # long time [34, 21, 34, 21, 34, 21, 34, 21] sage: rot180 # long time WordMorphism: 0->2, 1->3, 2->0, 3->1
- slabbe.double_square_tile.double_square_from_four_integers(l0, l1, l2, l3)¶
Creates a double square from the lengths of the \(w_i\).
INPUT:
l0
- integer, length of \(w_0\)l1
- integer, length of \(w_1\)l2
- integer, length of \(w_2\)l3
- integer, length of \(w_3\)
OUTPUT:
tuple - tuple of 8 words over alphabet A
WordMorphism, involution on the alphabet A and representing a rotation of 180 degrees.
dict - mapping letters of A to steps in the plane.
EXAMPLES:
sage: from slabbe.double_square_tile import double_square_from_four_integers sage: w,rot180,steps = double_square_from_four_integers(2,1,2,1) sage: w (Path: 21, Path: 2, Path: 32, Path: 3, Path: 03, Path: 0, Path: 10, Path: 1) sage: rot180 WordMorphism: 0->2, 1->3, 2->0, 3->1 sage: sorted(steps.items()) [(0, (1, 0)), (1, (0, 1)), (2, (-1, 0)), (3, (0, -1))]
If the input integers do not define a double square uniquely, the alphabet might be larger than 8:
sage: w,rot180,steps = double_square_from_four_integers(4,2,4,2) sage: w (Path: 7601, Path: 76, Path: 5476, Path: 54, Path: 2354, Path: 23, Path: 0123, Path: 01) sage: rot180 WordMorphism: 0->4, 1->5, 2->6, 3->7, 4->0, 5->1, 6->2, 7->3 sage: sorted(steps.items()) [(0, (1, 0)), (1, (1/2*sqrt(2), 1/2*sqrt(2))), (2, (0, 1)), (3, (-1/2*sqrt(2), 1/2*sqrt(2))), (4, (-1, 0)), (5, (-1/2*sqrt(2), -1/2*sqrt(2))), (6, (0, -1)), (7, (1/2*sqrt(2), -1/2*sqrt(2)))]
- slabbe.double_square_tile.figure_11_BGL2012(scale=0.5, boxsize=10, newcommand=True)¶
Return the tikz code of the Figure 11 for the article [BGL2012].
INPUT:
scale
- number (default:0.5
), tikz scaleboxsize
- integer (default:10
), size of box the double squares must fit innewcommand
- bool (default:True
), whether to include latex newcommand for TRIM, EXTEND and SWAP
EXAMPLES:
sage: from slabbe.double_square_tile import figure_11_BGL2012 sage: s = figure_11_BGL2012() sage: s \newcommand{\TRIM}{\textsc{trim}} \newcommand{\EXTEND}{\textsc{extend}} \newcommand{\SWAP}{\textsc{swap}} \begin{tikzpicture} [first/.style={circle,draw=black,fill=black, inner sep=0pt, minimum size=3pt}, second/.style={circle,draw=black,fill=white, inner sep=0pt, minimum size=3pt}, >=latex, node distance=3cm] \node (A) at (15,0) { \begin{tabular}{c} \begin{tikzpicture} [scale=0.5] ... \end{tikzpicture} }; \path[<-] (A) edge node[midway, rectangle, fill=white] {$\TRIM_2$} (B); \path[<-] (B) edge node[midway, rectangle, fill=white] {$\TRIM_0$} (C); \path[<-] (C) edge node[midway, rectangle, fill=white] {$\TRIM_1$} (D); \path[<-] (D) edge node[midway, rectangle, fill=white] {$\TRIM_3$} (E); \path[<-] (E) edge node[midway, rectangle, fill=white] {$\SWAP_1$} (F); \path[<-] (F) edge node[midway, rectangle, fill=white] {$\TRIM_1$} (G); \path[<-] (G) edge node[midway, rectangle, fill=white,rotate=90] {$\TRIM_3$} (H); \path[<-] (H) edge node[midway, rectangle, fill=white,rotate=90] {$\SWAP_1$} (I); \path[<-] (D) edge node[midway, rectangle, fill=white] {$\TRIM_2$} (E2); \end{tikzpicture}
- slabbe.double_square_tile.find_square_factorisation(ds, factorisation=None, alternate=True)¶
Return a square factorisation of the double square ds, distinct from the given factorisation.
INPUT:
ds
- word, the boundary word of a square tilefactorisation
- tuple (default:None
), a known factorisationalternate
- bool (default:True
), if True the search for the second factorisation is restricted to those who alternates with the first factorisation
OUTPUT:
tuple of four positions of a square factorisation
EXAMPLES:
sage: from slabbe.double_square_tile import find_square_factorisation sage: find_square_factorisation(words.fibonacci_tile(0)) (0, 1, 2, 3) sage: find_square_factorisation(words.fibonacci_tile(1)) (0, 3, 6, 9) sage: find_square_factorisation(words.fibonacci_tile(2)) (0, 13, 26, 39) sage: find_square_factorisation(words.fibonacci_tile(3)) (0, 55, 110, 165)
sage: f = find_square_factorisation(words.fibonacci_tile(3)) sage: f (0, 55, 110, 165) sage: find_square_factorisation(words.fibonacci_tile(3),f) # long time (6s) (34, 89, 144, 199) sage: find_square_factorisation(words.fibonacci_tile(3),f,False) # long time (11s) (34, 89, 144, 199)
sage: from slabbe import christoffel_tile sage: find_square_factorisation(christoffel_tile(4,5)) (0, 7, 28, 35) sage: find_square_factorisation(christoffel_tile(4,5),_) (2, 27, 30, 55)
TESTS:
sage: find_square_factorisation(Words('abcd')('aaaaaa')) Traceback (most recent call last): ... ValueError: no square factorization found sage: find_square_factorisation(Words('abcd')('aaaaaa'),(1,2,3,4)) Traceback (most recent call last): ... ValueError: no second square factorization found
- slabbe.double_square_tile.snake(i, ncols=2)¶
Return the coordinate of the ith node of a snake.
This is used for the tikz drawing of a double square reduction.
INPUT:
i
- integer, the ith nodencols
- integer (default2
), number of columns
EXAMPLES:
sage: from slabbe.double_square_tile import snake sage: for i in range(8): snake(i, 3) (0, 0) (1, 0) (2, 0) (2, -1) (1, -1) (0, -1) (0, -2) (1, -2)
- slabbe.double_square_tile.triple_square_example(i)¶
Return a triple square factorisation example.
These words having three square factorisations were provided by Xavier Provençal.
INPUT:
i
- integer, accepted values are 1, 2 or 3.
EXAMPLES:
sage: from slabbe.double_square_tile import triple_square_example sage: triple_square_example(1) Path: abaBAbabaBAbabaBAbabABABabABABabABAB sage: triple_square_example(2) Path: abaBABaabaBABaabaBABaabABAAbabABAAbabABA... sage: triple_square_example(3) Path: aabAAbaabAAbaabAAbaaBAABaaBAABaaBAAB
Triple square tile do not exist. Hence the example provided by Xavier Provençal can not be the boundary word of a tile. One can see it by plotting it or by the fact that the turning number is zero:
sage: from slabbe import DoubleSquare sage: D = DoubleSquare(triple_square_example(1)) sage: D Double Square Tile w0 = a w4 = a w1 = baBA w5 = bABA w2 = babaB w6 = BabAB w3 = AbabaBAb w7 = ABabABAB (|w0|, |w1|, |w2|, |w3|) = (1, 4, 5, 8) (d0, d1, d2, d3) = (12, 6, 12, 6) (n0, n1, n2, n3) = (0, 0, 0, 1) sage: D.turning_number() 0