1. Introduction
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 Golomb in [1] and the standard reference about this subject is the book Polyominoes [2] . The L-shaped polyomino we study is placed in a square lattice and is made out of
, unit squares, or cells. See Figure 1(a). In a
rectangle, a is the height and b is the base. We consider translations (only!) of the tiles shown in Figure 1(b). They are ribbon L-shaped n-ominoes. A ribbon polyomino [3] 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
.
Tilings by
even are studied in [4] and [5] , with [4] covering the case n = 4. We recall that a replicating tile is one that can make larger copies of itself. The order of replication is the number of initial tiles that fit in the larger copy. Replicating tiles were introduced by Golomb in [6] . In [7] , we study replication of higher orders for several
![]()
Figure 1. An L n-omino and the tile set Tn.
replicating tiles introduced in [6] . In particular, it is suggested there that the skewed L-tetromino shown in Figure 2(a) is not replicating of order
for any odd k. The question is equivalent to that of tiling a k-inflated copy of the straight L-tetromino using only four, out of eight possible, orientations of an L-tetromino, namely those that are ribbon. The question is solved in [4] , 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
always follows the rectangular pattern, that is, the tiling reduces to a tiling by
and
rectangles, each tiled in turn by two tiles from
.
The results in [4] are generalized in [5] to
even. The main result shows that any tiling of the first quadrant by
reduces to a tiling by
and
rectangles, with each rectangle covered by two ribbon L-shaped n-ominoes. An application is the characterization of all rectangles that can be tiled by
even: a rectangle can be tiled if and only if both sides are even and at least one side is divisible by n. Another application is the existence of the local move property for an infinite family of sets of tiles:
even, has the local move property for the class of rectangular regions with respect to the local moves that interchange a tiling of an
square by
vertical rectangles, with a tiling by
horizontal rectangles, each vertical/horizontal rectangle being covered by two ribbon L-shaped n-ominoes. One shows that neither of these results is valid for any odd n. The rectangular pattern of a tiling of the first quadrant persists if one adds an extra
tile to
even. A rectangle can be tiled by the larger set of tiles if and only if 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 2(b)) is not a replicating tile of order
for any odd k.
We investigate in this paper tiling properties of
odd. Parallel results with [8] are not possible due to the fact, already observed in [5] , that there are rectangles that have tilings by
odd, which do not follow the rectangular pattern. See Figure 3. Instead of regular tilings, one can study signed tilings. These are finite placements of tiles on a plane, with weights +1 or −1 assigned to each of the tiles. We say that they 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.
A useful tool in the study of signed tilings is a Gröbner basis associated to the polynomial ideal generated by the tiling set. If the coordinates of the lower left corner of a cell are (α, β), one associates to the cell the monomial
. 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
. The polynomial associated to a tile translated by an integer vector
is the initial polynomial multiplied by the monomial
. If the region we want to tile is bounded and if the tile set consists of bounded tiles, then the whole problem can be translated in the first quadrant via a translation by an integer vector, and one can work only with regular polynomials in
. See Theorem 13 below.
Our main result is the following:
Theorem 1. A rectangle can be signed tiled by
odd, if and only if it has a side divisible by n.
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
odd.
Theorem 1 gives for regular tilings by
odd, a corollary already known (see Lemma 2 in [5] ):
Theorem 2. If
odd, a rectangle with neither side divisible by n cannot be tiled by
.
If one of the sides of the rectangle is divisible by n, we recall first the following result of Herman Chau, mentioned in [5] , which is based on a deep result of Pak [3] .
Theorem 3. A rectangle with both sides odd cannot be tiled by
odd.
If one of the sides of the rectangle is even, one has the following result.
Theorem 4. Let
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
.
2) If the side divisible by n is of length at least
and even, and the other side is of length at least
and odd, then the rectangle can be tiled by
.
Proof. 1) The rectangle can be tiled by
or
rectangles, which can be tiled by two tiles from
.
2) We use the tiling shown in Figure 4. The
rectangle is tiled as in Figure 3, and the other two rectangles can be tiled by
or
rectangles, which in turn can be tiled by two tiles from
.
A consequence of the technique used in the proof of Theorem 1 is:
Proposition 5. If
odd and
, then 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
square can be tiled by
, it follows that if k is divisible by 2n then the skewed Ln-omnino is replicating of order
. Information about other orders of replication can be found by using Pak’s invariant [3] .
Proposition 6. Let
odd.
1) If
is odd and divisible by n, then the skewed L n-omino is not replicating of order
.
2) If
is even and not divisible by n, then the skewed L n-omino is not replicating of order
.
Proposition 6 is proved in Section 6. Proposition 6 leaves open the question of replication of the skewed L n-omino if k is odd and not divisible by n. Some cases can be solved by using Pak’s higher invariants
[3] , which are all zero for tiles in
. For example, if
, a 3-inflated copy of the L pentomino has
, showing the impossibility of tiling. 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
equal to zero. This is in contrast to the case of regular tilings by
even, discussed in [5] , which is very well understood.
![]()
Figure 4. A tiling of an (odd, even) rectangle by
.
For completeness, we also consider the tile set
, consisting of
odd, and an extra
square. For n even, the tile set
is studied in [5] . It is shown there that there is a similarity between the regular tiling properties of
and
.
Theorem 7. If
odd, any region in a square lattice can be signed tiled by ![]()
Theorem 7 is proved in Section 7.
Barnes developed in [9] [10] a general method for solving signed tiling problems with complex weights. In Section 8, we review the method of Barnes and offer an alternative proof of Theorem 1 based on this method. 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, a rectangle can be signed tiled by
odd, if and only if it has a side divisible by n.
Signed tilings by
even, are more complicated than in the odd case. They are discussed in [11] .
We make a final comment about the paper. While the methods that we use are well known, and algorithmic when applied to a particular tiling problem, here we apply them to solve simultaneously an infinite collection of tiling problems.
2. Summary of Gröbner Basis Theory
An introduction to signed tilings can be found in the paper of Conway and Lagarias [12] . One investigates 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 [13] . In [8] one uses this approach to study signed tilings by the n-bone, a tile consisting of n collinear adjacent regular hexagons.
Let
be the ring of polynomials with coefficients in a principal ideal domain (PID) R. The only (PID) of interest in this paper is ℤ, the ring of integers. A term in the variables
is a power product
with
; in particular
is a term. A term 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
on the variables. If the variables are only
and
, this gives the total order:
(1)
For
we denote by
the leading term in P with respect to the above order and by
the monomial of
. We denote by
the coefficient of the leading monomial in P. We denote by
the set of terms appearing in P, which we assume to be in simplest form. We denote by
the set of monomials in P. For a given ideal
an associated Gröbner basis may be introduced for example as in Chapters 5, 10 [14] . Our summary follows the approach there. If
is a finite set, we denote by
the ideal generated by G in
.
Definition 1. Let
. We say that f D-reduces to g modulo p and write
if there exists
with
, say
, and
. For a finite set
, we denote by
the reflexive-transitive closure of
,
. We say that g is a normal form for f with respect to G if
and no further D-reduction is possible. We say that f is D-reducible modulo G if
.
It is clear that if
, then f belongs to the ideal generated by G in
. The converse is also true if G is a Gröbner basis.
Definition 2. A D-Gröbner basis is a finite set G in
with the property that all D-normal forms modulo G of elements of
equal zero. If
is an ideal, then a D-Gröbner basis of I is a D-Gröbner basis that generates the ideal I.
Proposition 9. Let G be a finite set of
. Then the following statements are equivalent:
1) G is a Gröbner basis.
2) Every
, is D-reducible modulo G.
Note that if R is only a (PID), the normal form of the division of f by G is not unique. We introduce now the notions of S-polynomial and G-polynomial.
Definition 3. Let
with
,
. Let
with
, and
with
. Let
such that
. Then:
(2)
Remark. If
, then
can be chosen to be
.
Theorem 10. Let G be a finite set of
. Assume that for all
,
and
is top-D-reducible modulo G. Then G is a Gröbner basis.
Assume now that R is a Euclidean domain with unique remainders (see page 463 [14] ). This is the case for the ring of integers ℤ if we specify remainders upon division by
to be in the interval
.
Definition 4. Let
. We say that f E-reduces to g modulo p and write
if there exists
with
, say
, and
where
is the quotient of a upon division with unique remainder by
.
Proposition 11. E-reduction extends D-reduction, i.e., every D-reduction step in an E-reduction step.
Theorem 12. Let R be an Euclidean domain with unique remainders, and assume G is a finite set of
and a D-Gröbner basis. Then the following hold:
1)
for all
, where
denotes the E-reduction modulo G.
2) E-reduction modulo G has unique normal forms.
The following result connects signed tilings and Gröbner bases. See [13] and [8] for a proof.
Theorem 13. A polyomino P admits a signed tiling by translates of prototiles
if and only if for some (test) monomial
the polynomial
is in the ideal generated in
by the polynomials
. Moreover, the set of test monomials
can be indexed by any set of multi-indices which is cofinal in
.
3. Gröbner Basis for Tn,n Odd
We write
. The polynomials (in condensed form) associated to the tiles in
are:
(3)
We show in the rest of this section that a Gröbner basis for the ideal generated in
by
is given by the polynomials (written in condensed from):
(4)
It is convenient to look at the elements of the basis geometrically, as signed tiles, see Figure 5. The presence of
in the basis allows reducing the algebraic proofs to combinatorial considerations. Indeed, using addition by a multiple of
, one can translate, along a vector parallel to the first bisector
, cells labeled by +1 from one
position in the square lattice to another. See Figure 6. We will use this property repeatedly to check certain algebraic identities.
Proposition 14.
are in the ideal generated by
.
Proof. The geometric proofs appear in Figure 7. First we translate one of the tiles
multiplying by a power of x or a power of y, and then rearrange the cells from
using diagonal translations given by multiples of
. The initial tiles
have the cells marked by a +, and the final tiles
are colored in light gray.
Proposition 15.
are in the ideal generated by
.
Proof. We first show that
belongs to the ideal generated by
. One has:
(5)
Using (3), the RHS of Equation (5) becomes:
![]()
After we obtain
, polynomials
can be obtained geometrically by reversing the processes in Figure 7. Reversing the process in Figure 7(a), we first obtain a copy of
. This copy can be translated to the right using multiplication by
, and then can be pulled back with the corner in the origin using a translation by a vector parallel to
. Reversing the process in Figure 7(c), we first obtain a copy of
. This copy can be translated up using multiplication by
, and then can be pulled back with the corner in the origin using a translation by a vector parallel to
.
A step by step geometric proof of formula (5) for
is shown in Figure 8. All cells in the square lattice without any label have weight zero. The proof can be easily generalized for any odd n.
Proposition 16.
and
generate the same ideal in
.
Proof. This follows from Propositions 14, 15.
Proposition 17. One has the following D-reductions
![]()
![]()
![]()
Consequently,
is a Grӧbner basis.
![]()
Figure 8. The polynomial
is generated by
.
Proof. The leading monomial of
is
, the leading monomial of
is
and the leading monomial of
is
. We reduce the S-polynomials related to the set
:
![]()
![]()
![]()
We show now that all above reductions are D-reductions by looking at the elimination of the terms of highest degree in the S-polynomials.
The terms of highest degrees in
, after the initial reduction
![]()
are (in this order)
![]()
The terms
are contained in
![]()
which does not contains terms of higher degree then
.
The remaining terms
are contained in
![]()
which also does not contain terms of higher degree then
.
The term of highest degrees in
, after the initial reduction
![]()
is
. This term is contained in
![]()
which does not contain terms of higher degree then ![]()
The term of highest degrees in
, after the initial reduction
![]()
is
. This term is contained in
, which does not contain terms of higher degree then
.
As all higher coefficients are equal to 1, we do not need to consider the G-polyno- mials.
4. Proof of Theorem 1
Consider a
, rectangle. Using the presence of
in the Gröbner basis, and Theorem 13, the existence of a signed tiling becomes equivalent to deciding when the polynomial:
![]()
is divisible by the polynomial:
![]()
If
, then
, so divisibility does not hold. If
we look at
as a sum of p polynomials with all coefficients equal to 1:
![]()
Assume that
, and
. The remainder
of the division of
by
is the sum of the remainders of the division of the p polynomials above by
.
If r is odd, one has the following sequence of remainders, each remainder written in a separate pair of parentheses:
![]()
If
, 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,
is divisible by
. If p is not divisible by n, then doing first the cancellation as above and then 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
, 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:
![]()
If
, 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,
is divisible by
. If p is not divisible by n, then doing first the cancellation as above and then 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
, that is, only if q is divisible by n.
5. Proof of Proposition 5
Consider a k-inflated copy of the L n-omino. Using the presence of
in the Gröbner basis, and Theorem 13, the existence of a signed tiling of the copy becomes equivalent to deciding when a
rectangle has a signed tiling by
. Theorem 1 implies that this is always the case.
6. Proof of Proposition 6
1) We employ a ribbon tiling invariant introduced by Pak [3] . Each ribbon tile of length n can be encoded uniquely as a binary string of length
, denoted
, where a 1 represents a down movement and a
represents a right movement. The encoding of a
bar is
, for a
bar is
, and for the tiles in
the encodings are shown in Figure 9. Pak showed that the function
is an invariant of the set of ribbon tiles made of n-cells, which contains as a subset the tile set
. In particular, one has that
![]()
for any tile in
. The area of a k-inflated copy of the L n-omino is an odd multiple of n and can be easily covered by
and
bars, each one having the invariant equal to zero. If we try to tile by
, then the invariant is zero only if we use an even number of tiles. But this is impossible because the area is odd.
2) Let
. After cutting from a k-inflated copy a region that can be covered by
and
bars, and which has the
invariant equal to zero, we are left with one of the regions shown in Figure 10. Case a) appears if
and case b) appears if
. Both of these regions can be tiled by r ribbon tiles of area n as in Figure 11. In the first case the sequence of r encodings of the ribbon tiles is:
![]()
![]()
Figure 9. The four L-shaped ribbon pentominoes and their encodings.
![]()
Figure 11. Tiling the leftover region by ribbon n tiles, cases
, and
.
where we start with
ones and r zeros, and then shift the zeroes to the left by 1 at each step, completing the sequence at the end with ones. As
, the subsequence of zeroes does not reach the left side, so the
invariant of the region is equal to 1.
In the second case, the sequence of r encodings of the ribbon tiles starts as above, but now the subsequence of zeroes reaches the left side. Then we have a jump of
units of the sequence of zeroes to the left, the appearance of an extra one at the right, and a completion of the sequence by zeroes to the right. Then the subsequence of ones that appears start shifting to the right till it reaches the right edge. The
invariant of the region is equal to −1.
So in both cases the
invariant is an odd number. Nevertheless, if the k-copy is tiled by
, one has to use an even number of tiles and the invariant is an even number. Therefore we have a contradiction.
7. Proof of Theorem 7
It is enough to generate the tile consisting of a single cell. We show the proof for
in Figure 12. The proof can be easily generalized to any
odd. First we construct a domino with both cells having the same sign (as in Figure 12(c)), and then we use it to reduce the L n-omino until a single cell is left.
8. The Method of Barnes
In this section we give a proof of Theorem 8 following a method developed by Barnes. The reader of this section should be familiar with [9] [10] . We apply the method to the
infinite collection of tiling sets
odd.
Let
odd. Consider the polynomials (3) associated to the tiles in
and denote by I the ideal generated by
. We show that the algebraic variety V defined by I is zero dimensional and consists only of the pairs of points
(6)
where
is an n-th root of identity different from 1.
Separate x from
and replace in
to have:
![]()
Eliminating the denominators gives:
![]()
which can be factored as:
![]()
It is clear that all roots of the polynomial above, and of the corresponding polynomial in the variable x, are roots of unity of order
and
. Using the system of equations that defines V, the roots of order
can be eliminated. Moreover, the only solutions of the system are given by (6).
We show now that I is a radical ideal. For this we use an algorithm of Seidenberg which can be applied to find the radical ideal of a zero dimensional algebraic variety over an algebraically closed field. See Lemma 92 in [15] . Compare also with Theorem 7.1 in [9] . As V is zero dimensional, one can find
and
that belong to the radical ideal. We consider the square free polynomials:
![]()
![]()
If
are square free, then the ideal generated by I and
is radical. So, in order to show that I itself is radical, it is enough to show that
belong to I. It is easier to generate
using the Gröbner basis, so we will use this approach.
Proposition 18. The polynomials
belong to the ideal I.
Proof. It is enough to generate
. One has:
![]()
We can apply now the main result in Lemma 3.8, [9] : a region R is signed tiled by
if and only if the polynomial
associated to R evaluates to zero in any point of the variety V. If R is a rectangle of dimensions
in the square lattice, then
![]()
which clearly evaluates to zero in all points of V if and only if one of
is divisible by n.
The fact that Theorem 8 implies Theorem 1 follows the idea of Theorem 4.2 in [9] . Indeed, a set of generators for the regions that are signed tiled with rational numbers by
is given by the polynomials
above. Both of them can be generated by the Gröbner basis using only integer coefficients.
9. Conclusion
We show that a rectangle can be signed tiled by ribbon L n-ominoes, n odd, if and only if it has a side divisible by n. A consequence of our technique, based on the exhibition of an explicit Grӧbner basis, is that any k-inflated copy of the skewed L n-omino has a signed tiling by skewed L n-ominoes.
Acknowledgements
V. Nitica was partially supported by Simons Foundation Grant 208729.