Signed tilings by ribbon L n-ominoes, n odd, via Gro¨bner bases Viorel Niticaa aDepartment of Mathematics, West Chester University, PA 19383, USA Abstract 6 We show that a rectangle can be signed tiled by ribbon L n-ominoes, n odd, if and only if it has a side 1 divisible by n. A consequence of our technique, based on the exhibition of an explicit Gröbner basis, is that 0 any k-inflated copy of the skewed L n-omino has a signed tiling by skewed L n-ominoes. We also discuss 2 regular tilings by ribbon L n-ominoes, n odd, for rectangles and more general regions. We show that in this r case obstructions appear that are not detected by signed tilings. a M Keywords: replicating tile; L-shaped polyomino; skewed L-shaped polyomino; signed tilings; Gröbner basis 6 ] 1. Introduction O C In this article we study tiling problems for regions in a square lattice by certain symmetries of an L- . shaped polyomino. Polyominoes were introduced by Solomon W. Golomb in [9] and the standard reference h about this subject is the book Polyominoes [11]. The L-shaped polyomino we study is placed in a square t a lattice and is made out of n,n ≥ 3, unit squares, or cells. See Figure 1a. In an a×b rectangle, a is the m height and b is the base. We consider translations (only!) of the tiles shown in Figure 1b. They are ribbon [ L-shaped n-ominoes. A ribbon polyomino [14] is a simply connected polyomino with no two unit squares lying along a line parallel to the first bisector y =x. We denote the set of tiles by T . 2 n v 8 5 5 0 0 T T . (a)AnLn-omino 3 4 1 with n cells. T T 0 1 2 6 (b) The set of tiles T . 1 n : v Figure 1 i X TilingsbyT ,neven,arestudiedin[5],[13],with[5]coveringthecasen=4. Werecallthatareplicating r n a tile is one that can make larger copies of itself. The order of replication is the number of initial tiles that fit inthelargercopy. ReplicatingtileswereintroducedbyGolombin[10]. In[12]westudyreplicationofhigher orders for several replicating tiles introduced in [10]. In particular, it is suggested there that the skewed L-tetromino showed in Figure 2a is not replicating of order k2 for any odd k. The question is equivalent to thatoftilingak-inflatedcopyofthestraightL-tetrominousingonlyfour, outofeightpossible, orientations of an L-tetromino, namely those that are ribbon. The question is solved in [5], where it is shown that the L-tetromino is not replicating of any odd order. This is a consequence of a stronger result: a tiling of the first quadrant by T always follows the rectangular pattern, that is, the tiling reduces to a tiling by 4×2 4 and 2×4 rectangles, each tiled in turn by two tiles from T . 4 The results in [5] are generalized in [13] to T ,n even. The main result shows that any tiling of the n first quadrant by T reduces to a tiling by 2×n and n×2 rectangles, with each rectangle covered by two n Email address: vnitica@wcupa.edu(ViorelNitica) Preprint submitted to Elsevier · · · (a) Skewed L-tetromino. (b) Skewed L n-omino. Figure 2: Skewed polyominoes ribbon L-shaped n-ominoes. An application is the characterization of all rectangles that can be tiled by T ,n even: a rectangle can be tiled if and only if both sides are even and at least one side is divisible by n. n Another application is the existence of the local move property for an infinite family of sets of tiles: T ,n n even, has the local move property for the class of rectangular regions with respect to the local moves that interchange a tiling of an n×n square by n/2 vertical rectangles, with a tiling by n/2 horizontal rectangles, eachvertical/horizontalrectanglebeingcoveredbytworibbonL-shapedn-ominoes. Oneshowsthatneither of these results are valid for any odd n. The rectangular pattern of a tiling of the first quadrant persists if one adds an extra 2×2 tile to T ,n even. A rectangle can be tiled by the larger set of tiles if and only if n it has both sides even. It is also shown in the paper that the main result implies that a skewed L-shaped n-omino, n even, (see Figure 2b) is not a replicating tile of order k2 for any odd k. (n,n+1) (n+1,n) (2n,n) (2n,n) (2n−2,n) (n,n+1) Figure 3: A tiling of a (3n,3n+1) rectangle by T . n We investigate in this paper tiling properties of T ,n odd. Parallel results with [13] are not possible due n to the fact, already observed in [13], that there are rectangles that have tilings by T ,n odd, that do not n follow the rectangular pattern. See Figure 3. Instead of regular tilings one can study signed tilings. These arefiniteplacementsoftilesonaplane,withweights+1or-1assignedtoeachofthetiles. Wesaythatthey tile a region R if the sum of the weights of the tiles is 1 for every cell inside R and 0 for every cell elsewhere. AusefultoolinthestudyofsignedtilingsisaGröbnerbasisassociatedtothepolynomialidealgenerated by the tiling set. If the coordinates of the lower left corner of a cell are (α,β), one associates to the cell the monomial xαyβ. This correspondence associates to any bounded tile placed in the square lattice a Laurent polynomial with all coefficients 1. The polynomial associated to a tile P is denoted by f . The polynomial P associatedtoatiletranslatedbyanintegervector(γ,δ)istheinitialpolynomialmultipliedbythemonomial xγyδ. If the region we want to tile is bounded and if the tile set consists of bounded tiles, then the whole problemcanbetranslatedinthefirstquadrantviaatranslationbyanintegervector,andonecanworkonly with regular polynomials in Z[X,Y]. See Theorem 13 below. Our main result is the following: Theorem 1. A rectangle can be signed tiled by T ,n≥5 odd, if and only if it has a side divisible by n. n 2 Theorem 1 is proved in Section 4 using a Gröbner basis for the tiling set computed in Section 3. For completeness, we briefly discuss regular tilings by T ,n≥5 odd. n Theorem 1 gives for regular tilings by T ,n≥5 odd, a corollary already known (see [Lemma 2][13]): n Theorem 2. If n≥5 odd, a rectangle with neither side divisible by n cannot be tiled by T . n If one of the sides of the rectangle is divisible by n, we recall first the following result of Herman Chau, mentioned in [13], which is based on a deep result of Pak [14]: Theorem 3. A rectangle with both sides odd cannot be tiled by T ,n≥5 odd. n If one of the sides of the rectangle is even, one has the following result. Theorem 4. Let n≥5, odd and assume that a rectangle has a side divisible by n and a side of even length. 1. If one side is divisible by n and the other side is of even length, then the rectangle can be tiled by T . n 2. If the side divisible by n is of length at least 3n+1 and even, and the other side is of length at least 3n and odd, then the rectangle can be tiled by T . n Proof. 1) The rectangle can be tiled by 2×n or n×2 rectangles, which can be tiled by two tiles from T . n (even,M(2n)) (3n,3n+1) (3n,even) Figure 4: A tiling of an (odd, even) rectangle by T . n 2) We use the tiling shown in Figure 4. The (3n,3n+1) rectangle is tiled as in Figure 3, and the other two rectangles can be tiled by 2×n or n×2 rectangles, which in turn can be tiled by two tiles from T . n A consequence of the technique used in the proof of Theorem 1 is: Proposition 5. If n≥5 odd, a k-inflated copy of the L n-omino has a signed tiling by ribbon L n-ominoes. Proposition 5 is proved in Section 5. As any 2n×2n square can be tiled by T , it follows that if k is divisible by 2n then the skewed L n n-omnino is replicating of order k2. Information about other orders of replication can be found using Pak’s invariant [14]. Proposition 6. Let n≥5 odd. 1) If k ≥1 is odd and divisible by n, then the skewed L n-omino is not replicating of order k2. 2) If k ≥1 is even and not divisible by n, then the skewed L n-omino is not replicating of order k2. Proposition 6 is proved in Section 6. Proposition6leavesopenthequestionofreplicationoftheskewedLn-ominoifk isoddandnotdivisible byn. SomecasescanbesolvedusingPak’shigherinvariantsf ,...f [14], whichareallzerofortilesinT . 2 m n For example, if n=5, a 3-inflated copy of the L pentomino has f =−1, showing the impossibility of tiling. 2 A general result for regular tilings is out of reach due to the fact that for k odd and congruent to 1 modulo n, the leftover region that appears (see the proof of Proposition 6) is just an L n-omino, that has all higher invariants f ,...f equal to zero. This is in contrast to the case of regular tilings by T ,n even, 2 m n discussed in [13], which is very well understood. For completeness, we also consider the tiling set T˜ , consisting of T ,n odd, and an extra 2×2 square. n n 3 Theorem 7. If n≥5 odd, any region in a square lattice can be signed tiled by T˜ . n Theorem 7 is proved in Section 7. Barnes developed in [1, 2] a general method for solving signed tiling problems with complex weights. In Section8wereviewthemethodofBarnesandofferanalternativeproofofTheorem1basedonthismethod. Having available a Gröbner basis for the tiling set helps even if Barnes method is used. Theorem 8. If complex or rational weights are allowed to replace the integral weights ±1, a rectangle can be signed tiled by T ,n≥5 odd, if and only if it has a side divisible by n. n Signed tilings by T ,n even, are more complicated then in the odd case. We will discussed them in a n forthcoming paper [8]. Afinalcommentaboutthepaper. Whilethemethodsthatweusearewellknown, andalgorithmicwhen applied to a particular tiling problem, here we apply them uniformly to solve simultaneously an infinite collection of problems. 2. Summary of Gröbner basis theory AnintroductiontosignedtilingscanbefoundinthepaperofConwayandLagarias[6]. Oneinvestigates there signed tilings by the 3-bone, a tile consisting of three adjacent regular hexagons. The Gröbner basis approach to signed polyomino tilings was proposed by Bodini and Nouvel [4]. In [7] one uses this approach to study signed tilings by the n-bone. Let R[X]=R[X ,...,X ] be the ring of polynomials with coefficients in a principal ideal domain (PID) 1 k R. The only (PID) of interest in this paper is Z, the ring of integers. A term in the variables x ,...,x 1 k is a power product xα1xα2...xα(cid:96) with α ∈ N,1 ≤ i ≤ (cid:96); in particular 1 = x0...x0 is a term. A term 1 2 (cid:96) i 1 (cid:96) with an associated coefficient from R is called monomial. We endow the set of terms with the total degree- lexicographical order, in which we first compare the degrees of the monomials and then break the ties by means of lexicographic order for the order x >x >···>x on the variables. If the variables are only x,y 1 2 (cid:96) and x>y, this gives the total order: 1degP , so divisibility does not hold. If p+q−1≥n, we look at P as p,q p,q a sum of p polynomials with all coefficients equal to 1: P (x)=1+x+x2+x3+···+xp−1+xp+...+xq−1+xq+xq+1+···+xp+q−4+xp+q−3+xp+q−2 p,q +x+x2+x3+···+xp−1+xp+...+xq−1+xq+xq+1+xp+q−4+···+xp+q−3 +x3+···+xp−1+xp+...+xq−1+xq+xq+1+···+xp+q−4 ............ +xp+...+xq−1. (18) Assume that p+q−1 = nm+r,0 ≤ r < n, and p = ns+t,0 ≤ t < n. The remainder R (x) of the p,q division of P (x) by Q(x) is the sum of the remainders of the division of the p polynomials above by Q(x). p,q 9 If r is odd, one has the following sequence of remainders, each remainder written in a separate pair of parentheses: R (x)=(1+x+x2+···+xr−1) p,q +(x+x2+···+xr−2) +(x2+···+xr−3) ......... r−1 r+1 r−1 r+1 +(x 2 +x 2 )+(0)−(x 2 +x 2 ) ......... −(x+x2+···+xr−2) −(1+x+x2+···+xr−1) (19) +(xr+1+xr+3+···+xn−3+xn−2) +(xr+2+···+xn−3) ......... r+n r+n +(x 2 )−(x 2 ) ......... −(xr+2+···+xn−3) −(xr+1+xr+3+···+xn−3+xn−2) ......... If p ≥ n, the sequence of remainders above is periodic with period n, given by the part of the sequence shown above, and the sum of any subsequence of n consecutive remainders is 0. So if p is divisible by n, P (x) is divisible by Q(x). If p is not divisible by n, then doing first the cancellation as above and then p,q using the symmetry of the sequence of remainders about the remainder equal to 0, the sum of the sequence of remainders equals 0 only if r+1=t, that is, only if q is divisible by n. If r is even, one has the following sequence of remainders, each remainder written in a separate pair of parentheses: R (x)=(1+x+x2+···+xr−1) p,q +(x+x2+···+xr−2) +(x2+···+xr−3) ......... +(xr2)−(xr2) ......... −((x+x2+···+xr−2)) −(1+x+x2+···+xr−1) (20) +(xr+1+xr+2+···+xn−3+xn−2) +(xr+2+···+xn−3) ......... r+n−1 r+n+1 r+n−1 r+n+1 +(x 2 +x 2 )+(0)−(x 2 +x 2 ) ......... −(xr+2+···+xn−3) −(xr+1+xr+2+···+xn−3+xn−2) ......... If p ≥ n, the sequence of remainders above is periodic with period n, given by the part of the sequence shown above, and the sum of any subsequence of n consecutive remainders is 0. So if p is divisible by n, 10

Signed tilings by ribbon L n-ominoes, n odd, via Groebner bases

Similar Signed tilings by ribbon L n-ominoes, n odd, via Groebner bases