# Signed Shape Tilings of Squares Keywords: tile, shape, polynomial.

## 1 Introduction

In  Dehn proved that an $`a\times b`$ rectangle $`R`$ can be tiled by finitely many nonoverlapping squares if and only if $`a/b`$ is rational. More generally, suppose we allow the squares to have weights from $``$. An arrangement of weighted squares is a tiling of $`R`$ if the sum of the weights of the squares covering a region is 1 inside of $`R`$ and 0 outside. Dehn’s argument applies in this more general setting, and shows that $`R`$ has a $``$-weighted tiling by squares if and only if $`a/b`$ is rational. In  this result is generalized to give necessary and sufficient conditions for a rectangle $`R`$ to be tilable by $``$-weighted rectangles with particular shapes. In this paper we consider a related question: Given a tile $`T`$ in the plane made up of finitely many weighted rectangles, is there a weighted tiling of a square by tiles with the same shape as $`T`$?

We define a rectangle in $`\times `$ to be a product $`[b_1,b_2)\times [c_1,c_2)`$ of half-open intervals, with $`b_1<b_2`$ and $`c_1<c_2`$. Let $`A`$ be a commutative ring with unity. An $`A`$-weighted tile is represented by a finite $`A`$-linear combination $`L=a_1R_1+\mathrm{}+a_nR_n`$ of disjoint rectangles. Associated to each such $`L`$ there is a function $`f_L:^2A`$ which is supported on $`R_i`$ and whose value on $`R_i`$ is $`a_i`$. We say that $`L_1`$ and $`L_2`$ represent the same tile if $`f_{L_1}=f_{L_2}`$. An example of a $``$-weighted tile is given in Figure 1.

We may form the sum $`T_1+T_2`$ of two weighted tiles $`T_1,T_2`$ by superposing them in the natural way. For $`aA`$ the tile $`aT`$ is formed from $`T`$ by multiplying all the weights of $`T`$ by $`a`$. The set of all $`A`$-weighted tiles forms an $`A`$-module under these operations.

Let $`U`$ be an $`A`$-weighted tile and let $`\{T_\lambda :\lambda \mathrm{\Lambda }\}`$ be a set of $`A`$-weighted tiles. We say that the set $`\{T_\lambda :\lambda \mathrm{\Lambda }\}`$ $`A`$-tiles $`U`$ if there are weights $`a_1,\mathrm{},a_nA`$ and tiles $`\stackrel{~}{T}_1,\mathrm{},\stackrel{~}{T}_n`$, each of which is a translation of some $`T_{\lambda _i}`$, such that $`a_1\stackrel{~}{T}_1+\mathrm{}+a_n\stackrel{~}{T}_n=U`$. Note that we are allowed to use as many translated copies of each prototile $`T_\lambda `$ as we need, but we are not allowed to rotate or reflect the prototiles. Given an $`A`$-weighted tile $`T`$ and a real number $`\rho >0`$ we define $`T(\rho )`$ to be the image of $`T`$ under the rescaling $`(x,y)(\rho x,\rho y)`$. We say that an $`A`$-weighted tile $`T^{}`$ has the same shape as $`T`$ if there exists $`\rho >0`$ such that $`T^{}`$ is a translation of $`T(\rho )`$. We say that $`T`$ $`A`$-shapetiles $`U`$ if $`\{T(\rho ):\rho >0\}`$ $`A`$-tiles $`U`$. If $`U^{}`$ has the same shape as $`U`$ then $`T`$ $`A`$-shapetiles $`U^{}`$ if and only if $`T`$ $`A`$-shapetiles $`U`$.

In this paper we consider tiles $`T`$ constructed from rectangles whose corners have rational coordinates. We prove two main results about such tiles. First, we show that if $`T`$ is a $``$-weighted tile whose weighted area is not 0, then $`T`$ $``$-shapetiles a square. Second, if $`T`$ is a $``$-weighted tile we give necessary and sufficient conditions for $`T`$ to $``$-shapetile a square.

The author would like to thank Jonathan King for posing several questions which led to this work.

## 2 Polynomials and tiling

Say that $`T`$ is a lattice tile if $`T`$ is an $`A`$-weighted tile made up of unit squares in $`^2`$ whose corners are in $`^2`$. We will associate a (generalized) polynomial $`f_T`$ to each $`A`$-weighted lattice tile $`T`$. Our approach is similar to that used by F. W. Barnes in , except that the polynomials that we construct differ from Barnes’s polynomials by a factor $`(X1)(Y1)`$. Including this extra factor will allow us to generalize the construction to non-lattice tiles at the end of the section.

Our polynomials will be elements of the ring

$`A[X^{},Y^{}]`$ $`:=`$ $`A[X,Y,X^1,Y^1],`$   
which is naturally isomorphic to the group ring of $`\times `$ with coefficients in $`A`$. To begin we associate the polynomial $`X^iY^j(X1)(Y1)`$ to the unit square $`S_{ij}`$ with lower left corner $`(i,j)\times `$. Given an $`A`$-weighted lattice tile

$`T`$ $`=`$ $`{\displaystyle \underset{i,j}{}}w_{ij}S_{ij},`$   
by linearity we associate to $`T`$ the polynomial

$`f_T(X,Y)`$ $`=`$ $`{\displaystyle \underset{i,j}{}}w_{ij}X^iY^j(X1)(Y1).`$   
One consequence of this definition is that translating a tile by a vector $`(i,j)\times `$ corresponds to multiplying its polynomial by $`X^iY^j`$. The map $`Tf_T`$ gives an isomorphism between the $`A`$-module of $`A`$-weighted lattice tiles in the plane and the principal ideal in $`A[X^{},Y^{}]`$ generated by $`(X1)(Y1)`$.

Example 2.1 Let $`a,b,c,d`$ be integers such that $`a,b1`$ and let $`T`$ be the $`a\times b`$ rectangle whose lower left corner is at $`(c,d)`$. Then the polynomial associated to $`T`$ is

$`f_T(X,Y)`$ $`=`$ $`{\displaystyle \underset{i=c}{\overset{c+a1}{}}}{\displaystyle \underset{j=d}{\overset{d+b1}{}}}X^iY^j(X1)(Y1)`$   
$`=`$ $`X^cY^d(X^a1)(Y^b1).`$   
In section 4 we will need to work with non-lattice tiles. To represent these more general tiles systematically we introduce a new set of building blocks to play the role that the unit squares $`S_{ij}`$ play in the theory of lattice tiles. For $`\alpha ,\beta ^\times `$ let $`R_{\alpha \beta }`$ denote the oriented rectangle with vertices $`(0,0)`$, $`(\alpha ,0)`$, $`(\alpha ,\beta )`$, $`(0,\beta )`$. Note that if exactly $`k`$ of $`\alpha ,\beta `$ are negative then $`R_{\alpha \beta }`$ is equal to $`(1)^k`$ times a translation of $`R_{|\alpha |,|\beta |}`$. We can express any rectangle in terms of the rectangles $`R_{\alpha \beta }`$:

Example 2.2 Let $`\alpha ,\beta >0`$ and let $`R_{\alpha \beta }^{}`$ be the translation of the rectangle $`R_{\alpha \beta }`$ by the vector $`(\sigma ,\tau )^2`$. Then $`R_{\alpha \beta }^{}=R_{\alpha +\sigma ,\beta +\tau }R_{\alpha +\sigma ,\tau }R_{\sigma ,\beta +\tau }+R_{\sigma \tau }`$. In particular, we have $`S_{ij}=R_{i+1,j+1}R_{i+1,j}R_{i,j+1}+R_{ij}`$.

In fact the following holds:

###### Lemma 2.3

Every $`A`$-weighted tile $`T`$ can be expressed uniquely as an $`A`$-linear combination of rectangles $`R_{\alpha \beta }`$ with $`\alpha ,\beta ^\times `$.

Proof: By Example 2 every rectangle is an $`A`$-linear combination of the rectangles $`R_{\alpha \beta }`$. Therefore every $`A`$-weighted tile is an $`A`$-linear combination of the $`R_{\alpha \beta }`$. Suppose

$`c_1R_{\alpha _1\beta _1}+c_2R_{\alpha _2\beta _2}+\mathrm{}+c_nR_{\alpha _n\beta _n}`$ $`=`$ $`0`$   
is a linear relation such that the pairs $`(\alpha _i,\beta _i)`$ are distinct and $`c_i0`$ for $`1in`$. Choose $`j`$ to maximize the distance from the origin to the far corner $`(\alpha _j,\beta _j)`$ of $`R_{\alpha _j\beta _j}`$. None of the other rectangles in the sum can overlap the region around $`(\alpha _j,\beta _j)`$. Since $`c_j0`$, this gives a contradiction. Therefore the set $`\{R_{\alpha \beta }:\alpha ,\beta ^\times \}`$ is linearly independent over $`A`$, which implies the uniqueness part of the lemma. $`\mathrm{}`$

In order to represent arbitrary $`A`$-weighted tiles algebraically we introduce a generalization of the polynomials $`f_T`$. Let $`A[X^{},Y^{}]`$ denote the set of “polynomials” with coefficients from $`A`$ where the exponents of $`X`$ and $`Y`$ are allowed to be arbitrary real numbers. The natural operations of addition and multiplication make $`A[X^{},Y^{}]`$ a commutative ring with unity. The ring $`A[X^{},Y^{}]`$ is naturally isomorphic to the group ring of $`\times `$ with coefficients in $`A`$, and contains $`A[X^{},Y^{}]`$ as a subring.

For $`\alpha ,\beta ^\times `$ define $`f_{R_{\alpha \beta }}=(X^\alpha 1)(Y^\beta 1)A[X^{},Y^{}]`$. By Lemma 2.3 this definition extends linearly to give a well-defined element $`f_TA[X^{},Y^{}]`$ associated to any $`A`$-weighted tile $`T`$. It follows from Example 2 that this definition agrees with that given earlier if $`T=S_{ij}`$ is a unit lattice square, and hence also if $`T`$ is any lattice tile. The map $`Tf_T`$ gives an isomorphism between the $`A`$-module of $`A`$-weighted tiles and an $`A`$-submodule of $`A[X^{},Y^{}]`$. The next lemma implies that this $`A`$-submodule is actually an ideal in $`A[X^{},Y^{}]`$.

###### Lemma 2.4

Let $`T`$ be an $`A`$-weighted tile and let $`T^{}`$ be the translation of $`T`$ by the vector $`(\sigma ,\tau )\times `$. Then $`f_T^{}=X^\sigma Y^\tau f_T`$.

Proof: Let $`R_{\alpha \beta }^{}`$ be the translation of $`R_{\alpha \beta }`$ by $`(\sigma ,\tau )`$. Using Example 2 we get

$$f_{R_{\alpha \beta }^{}}=X^\sigma Y^\tau (X^\alpha 1)(Y^\beta 1)=X^\sigma Y^\tau f_{R_{\alpha \beta }},$$

so the lemma holds for $`T=R_{\alpha \beta }`$. Therefore by Lemma 2.3 the lemma holds for all tiles $`T`$$`\mathrm{}`$

The next result gives a further relation between ideals and tiling.

###### Proposition 2.5

Let $`U`$ be a tile, let $`\{T_\lambda :\lambda \mathrm{\Lambda }\}`$ be a collection of tiles, and let $`\stackrel{~}{I}A[X^{},Y^{}]`$ be the ideal generated by the set $`\{f_{T_\lambda }:\lambda \mathrm{\Lambda }\}`$. Then $`\{T_\lambda :\lambda \mathrm{\Lambda }\}`$ $`A`$-tiles $`U`$ if and only if $`f_U\stackrel{~}{I}`$.

Proof: We have $`f_U\stackrel{~}{I}`$ if and only if

$`f_U(X,Y)`$ $`=`$ $`{\displaystyle \underset{i=1}{\overset{k}{}}}a_iX^{\sigma _i}Y^{\tau _i}f_{T_{\lambda _i}}(X,Y)`$   
for some $`a_iA`$, $`\sigma _i,\tau _i`$, and $`\lambda _i\mathrm{\Lambda }`$. Since $`X^{\sigma _i}Y^{\tau _i}f_{T_{\lambda _i}}(X,Y)`$ is the polynomial associated to the translation of $`T_{\lambda _i}`$ by the vector $`(\sigma _i,\tau _i)`$, we have $`f_U\stackrel{~}{I}`$ if and only if $`U=a_1\stackrel{~}{T}_1+\mathrm{}+a_k\stackrel{~}{T}_k`$, with $`\stackrel{~}{T}_i`$ a translation of $`T_{\lambda _i}`$. Therefore $`f_U\stackrel{~}{I}`$ if and only if $`\{T_\lambda :\lambda \mathrm{\Lambda }\}`$ $`A`$-tiles $`U`$. $`\mathrm{}`$

###### Corollary 2.6

Let $`\{T_\lambda :\lambda \mathrm{\Lambda }\}`$ be a collection of lattice tiles, let $`I`$ be the ideal in $`A[X^{},Y^{}]`$ generated by the set $`\{f_{T_\lambda }:\lambda \mathrm{\Lambda }\}`$, and let $`U`$ be a lattice tile such that $`f_UI`$. Then $`\{T_\lambda :\lambda \mathrm{\Lambda }\}`$ $`A`$-tiles $`U`$.

The last result in this section shows what happens to $`f_T`$ when we replace $`T`$ by a rescaling.

###### Lemma 2.7

Let $`T`$ be an $`A`$-weighted tile and let $`\rho `$ be a positive real number. Then $`f_{T(\rho )}=f_T(X^\rho ,Y^\rho )`$.

Proof: Let $`\alpha ,\beta ^\times `$. Then $`R_{\alpha \beta }(\rho )=R_{\rho \alpha ,\rho \beta }`$ and hence

$$f_{R_{\alpha \beta }(\rho )}=(X^{\rho \alpha }1)(Y^{\rho \beta }1)=f_{R_{\alpha \beta }}(X^\rho ,Y^\rho ).$$

Therefore the lemma holds for $`T=R_{\alpha \beta }`$. It follows from Lemma 2.3 that the lemma holds for all tiles $`T`$$`\mathrm{}`$

## 3 Tiling with rational weights

This section is devoted to proving the following theorem:

###### Theorem 3.1

Let $`T`$ be a $``$-weighted tile made up of rectangles whose corners all have rational coordinates. Then $`T`$ $``$-shapetiles a square if and only if the weighted area of $`T`$ is not zero.

Proof: It is clear that if the weighted area of $`T`$ is zero then $`T`$ cannot shapetile a square with nonzero area. Assume conversely that $`T`$ has nonzero weighted area. By rescaling and translation we may assume that $`T`$ is a lattice tile in the first quadrant. Let $`T()`$ denote the set $`\{T(k):k\}`$ of positive integer rescalings of $`T`$. To complete the proof of Theorem 3.1 it suffices to prove that $`T()`$ $``$-tiles a square. First we will prove that $`T()`$ $``$-tiles a square; from this it will follow easily that $`T()`$ $``$-tiles a square.

Since $`T`$ is a lattice tile in the first quadrant, $`f_T[X,Y]`$ is a polynomial in the ordinary sense. We begin by interpreting the hypothesis that the weighted area of $`T`$ is nonzero in terms of $`f_T`$.

###### Lemma 3.2

There is a polynomial $`f_T^{}[X,Y]`$ such that

$`f_T(X,Y)`$ $`=`$ $`(X1)(Y1)f_T^{}(X,Y).`$   
Moreover, the weighted area of $`T`$ is equal to $`f_T^{}(1,1)`$, and hence $`f_T^{}(1,1)0`$.

Proof: Since the polynomial associated to the unit square $`S_{ij}`$ is

$`f_{S_{ij}}(X,Y)`$ $`=`$ $`X^iY^j(X1)(Y1),`$   
the lemma holds for $`S_{ij}`$. It follows by linearity that the lemma holds for all lattice tiles in the first quadrant. $`\mathrm{}`$

Let $`I`$ denote the ideal in $`[X^{},Y^{}]`$ generated by $`\{f_{T(k)}:k\}`$ and let

$`g_l(X,Y)`$ $`=`$ $`(X^l1)(Y^l1)`$   
be the polynomial associated to an $`l\times l`$ square with lower left corner $`(0,0)`$. To show that $`T()`$ $``$-tiles a square it suffices by Corollary 2.6 to show that $`g_lI`$ for some positive integer $`l`$. In order to get information about $`I`$ we consider the set $`V(I)^\times \times ^\times `$ of common zeros of the elements of $`I`$. The set $`V(I)`$ is essentially the union of the lines $`X=1`$ and $`Y=1`$ with the “shape variety” of $`T()`$ as defined by Barnes \[2, §3\].

We wish to determine which points $`(\alpha ,\beta )^\times \times ^\times `$ might be in $`V(I)`$. Let $`m`$ be the $`X`$-degree of $`f_T`$, let $`n`$ be the $`Y`$-degree of $`f_T`$, and define $`\mathrm{{\rm Y}}^\times `$ by

$`\mathrm{{\rm Y}}`$ $`=`$ $`\{\zeta ^\times :\zeta ^k=1\text{ for some }1k2mn\}.`$   
###### Lemma 3.3

$`V(I)(^\times \times \mathrm{{\rm Y}})(\mathrm{{\rm Y}}\times ^\times )`$.

Proof: Let $`(\alpha ,\beta )V(I)`$, and suppose neither $`\alpha `$ nor $`\beta `$ is in $`\mathrm{{\rm Y}}`$. By Lemma 2.7 and Lemma 3.2 we have

$$0=f_{T(k)}(\alpha ,\beta )=f_T(\alpha ^k,\beta ^k)=(\alpha ^k1)(\beta ^k1)f_T^{}(\alpha ^k,\beta ^k)$$

for all $`k1`$. Since $`\alpha `$ and $`\beta `$ aren’t in $`\mathrm{{\rm Y}}`$ this implies $`f_T^{}(\alpha ^k,\beta ^k)=0`$ for $`1k2mn`$. Therefore by Lemma 3.4 below there exist $`c,d`$ such that $`f_T^{}(X^c,X^d)=0`$. It follows that $`f_T^{}(1,1)=0`$, contrary to Lemma 3.2. We conclude that if $`(\alpha ,\beta )V(I)`$ then at least one of $`\alpha ,\beta `$ must be in $`\mathrm{{\rm Y}}`$$`\mathrm{}`$

###### Lemma 3.4

Let $`K`$ be a field and let $`f^{}K[X,Y]`$ be a nonzero polynomial with $`X`$-degree $`m1`$ and $`Y`$-degree $`n1`$. Assume there are $`\alpha ,\beta K^\times `$ such that

1. $`\alpha `$ and $`\beta `$ are not $`k`$th roots of 1 for any $`1k2mn`$, and
2. $`f^{}(\alpha ^k,\beta ^k)=0`$ for all $`1k2mn`$.

Then there exist relatively prime integers $`c,d`$ with $`1cn1`$ and $`1|d|m1`$ such that $`f^{}(X^c,X^d)=0`$.

Proof: Define an $`mn\times mn`$ matrix $`M`$ whose columns are indexed by pairs $`(i,j)`$ with $`0im1`$ and $`0jn1`$ by letting the $`k`$th entry in the $`(i,j)`$ column of $`M`$ be $`\alpha ^{ik}\beta ^{jk}`$. Since $`f^{}(\alpha ^k,\beta ^k)=0`$ for $`1kmn`$, the coefficients of $`f^{}`$ give a nontrivial element of the nullspace of $`M`$. Since $`M`$ is essentially a Vandermonde matrix this implies

$$0=det(M)=\alpha ^{nm(m1)/2}\beta ^{mn(n1)/2}\underset{(i,j)<(i^{},j^{})}{}(\alpha ^i^{}\beta ^j^{}\alpha ^i\beta ^j)$$

for an appropriate ordering of the pairs $`(i,j)`$. It follows that $`\alpha ^i^{}\beta ^j^{}=\alpha ^i\beta ^j`$ for some $`(i^{},j^{})(i,j)`$, so $`\alpha ^{d_0}=\beta ^{c_0}`$ for some $`(c_0,d_0)(0,0)`$ with $`|c_0|n1`$ and $`|d_0|m1`$. The first assumption implies that $`c_00`$ and $`d_00`$, so we may assume without loss of generality that $`c_01`$.

Let $`e=\mathrm{gcd}(c_0,d_0)`$ and set $`c=c_0/e`$ and $`d=d_0/e`$. Then since $`(\alpha ^e)^d=(\beta ^e)^c`$ with $`\mathrm{gcd}(c,d)=1`$ there is a unique $`\gamma K`$ such that $`\gamma ^c=\alpha ^e`$ and $`\gamma ^d=\beta ^e`$. Let $`q`$ be an integer such that $`1q2mn/e`$. Then by the second assumption we have

$$0=f^{}(\alpha ^{eq},\beta ^{eq})=f^{}(\gamma ^{cq},\gamma ^{dq}),$$

and so $`f^{}(X^c,X^d)K[X,X^1]`$ has zeros at $`X=\gamma ^q`$ for $`1q2mn/e`$. If these zeros are not distinct then for some $`1r2mn/e`$ we have $`\gamma ^r=1`$ and hence $`1=\gamma ^{cr}=\alpha ^{er}`$, which violates the first assumption. Therefore $`f^{}(X^c,X^d)`$ has at least $`2mn/e`$ distinct zeros. On the other hand the degree of the rational function $`f^{}(X^c,X^d)`$ is at most $`(m1)|c|+(n1)|d|`$, and since $`|c|=|c_0/e|(n1)/e`$ and $`|d|=|d_0/e|(m1)/e`$ we have

$$(m1)|c|+(n1)|d|\mathrm{\hspace{0.33em}\hspace{0.33em}2}(m1)(n1)/e<2mn/e.$$

Therefore $`f^{}(X^c,X^d)=0`$$`\mathrm{}`$

Let $`l1`$ and recall that $`g_l(X,Y)=(X^l1)(Y^l1)`$ is the polynomial associated to an $`l\times l`$ square with lower left corner $`(0,0)`$. The set $`V(g_l)^\times \times ^\times `$ of zeros of $`g_l`$ is the union of the lines $`X=\zeta `$ and $`Y=\zeta `$ as $`\zeta `$ ranges over the $`l`$th roots of 1. It follows from Lemma 3.3 that if we choose $`l`$ appropriately (say $`l=(2mn)!`$) then $`V(g_l)V(I)`$. This need not imply that $`g_l`$ is in $`I`$, but by Hilbert’s Nullstellensatz \[5, VII, Th. 14\] we do have $`g_l^kI`$ for some $`k1`$.

To show there exists $`l`$ such that $`g_lI`$ we use the theory of primary decompositions (see, e. g., chapters 4 and 7 of ). Let $`A`$ be a commutative ring with 1. We say that the ideal $`QA`$ is a primary ideal if whenever $`xyQ`$ with $`xQ`$ there exists $`a1`$ such that $`y^aQ`$. By the Hilbert basis theorem, $`[X^{},Y^{}]`$ is a Noetherian ring \[1, Cor. 7.7\]. Therefore there are primary ideals $`Q_1,\mathrm{},Q_r`$ in $`[X^{},Y^{}]`$ such that $`I=Q_1\mathrm{}Q_r`$ \[1, Th. 7.13\]. The radical ideal

$$P_i=\sqrt{Q_i}=\{f[X^{},Y^{}]:f^rQ_i\text{ for some }r1\}$$

of the primary ideal $`Q_i`$ is automatically prime, and is called the prime associated to $`Q_i`$. We may also characterize $`P_i`$ as the smallest prime ideal containing $`Q_i`$.

Since $`I=Q_1\mathrm{}Q_r`$ we need to show that there exists $`l1`$ such that $`g_lQ_i`$ for all $`1ir`$. Observe that if $`l|l^{}`$ then $`g_l|g_l^{}`$. Therefore it is enough to show that for each $`i`$ there is $`l_i`$ such that $`g_{l_i}Q_i`$, since in that case we have $`g_lI`$ with $`l=\text{lcm}\{l_1,\mathrm{},l_r\}`$. To accomplish this we first restrict the possibilities for the prime ideals $`P_i`$.

Let $`q=(2mn)!`$. We observed above that $`g_q^kI`$ for some positive integer $`k`$. Since $`P_iQ_iI`$ this implies that $`g_q^kP_i`$. Therefore some irreducible factor of

$`g_q(X,Y)^k`$ $`=`$ $`{\displaystyle \underset{\zeta ^q=1}{}}(X\zeta )^k(Y\zeta )^k`$   
lies in the prime ideal $`P_i`$. It follows that $`X\zeta P_i`$ or $`Y\zeta P_i`$ for some $`\zeta ^\times `$ such that $`\zeta ^q=1`$.

Assume without loss of generality that $`X\zeta P_i`$. Then $`P_i`$ contains the prime ideal $`(X\zeta )`$ generated by the irreducible polynomial $`X\zeta `$. If $`P_i(X\zeta )`$ let $`h`$ be an element of $`P_i`$ which is not in $`(X\zeta )`$. By dividing $`X\zeta `$ into $`h(X,Y)`$ we see that $`h(\zeta ,Y)P_i`$. Since $`P_i`$ is prime and $``$ is algebraically closed this implies that some linear factor $`Y\alpha `$ of $`h(\zeta ,Y)`$ is in $`P_i`$. Therefore $`P_i`$ contains the maximal ideal $`(X\zeta ,Y\alpha )`$, so in fact $`P_i=(X\zeta ,Y\alpha )`$. Moreover, we must have $`\alpha 0`$ since $`Y`$ is a unit in $`[X^{},Y^{}]`$. It follows that if $`X\zeta P_i`$ then either $`P_i=(X\zeta )`$ or $`P_i=(X\zeta ,Y\alpha )`$ for some $`\alpha ^\times `$.

We will make repeated use of the following elementary fact about primary ideals.

###### Lemma 3.5

Let $`Q`$ be a primary ideal and set $`P=\sqrt{Q}`$. If $`ghQ`$ with $`hP`$ then $`gQ`$.

Proof: Since $`hP`$ we have $`h^aQ`$ for all $`a1`$. Therefore by the definition of primary ideal we have $`gQ`$$`\mathrm{}`$

Assume now that $`P_i=(X\zeta )`$ with $`\zeta ^q=1`$. Then $`X^q1`$ has a simple zero at $`X=\zeta `$. Therefore by Lemma 2.7 and Lemma 3.2 we have

$`f_{T(q)}(X,Y)`$ $`=`$ $`f_T(X^q,Y^q)`$   
$`=`$ $`(X^q1)(Y^q1)f_T^{}(X^q,Y^q)`$   
$`=`$ $`(X\zeta )h(X,Y)`$   
for some $`h[X,Y]`$. Moreover we have $`h(\zeta ,Y)0`$, since otherwise $`0=f_T^{}(\zeta ^q,Y^q)=f_T^{}(1,Y^q)`$, which would imply $`f_T^{}(1,1)=0`$, contrary to Lemma 3.2. Therefore $`hP_i=(X\zeta )`$. It follows by Lemma 3.5 that $`X\zeta Q_i`$, and hence that $`g_qQ_i`$.

Now assume $`P_i=(X\zeta ,Y\alpha )`$. If $`\alpha `$ is an $`r`$th root of 1 for some $`r1`$ then $`X^{qr}1`$ has a simple zero at $`X=\zeta `$ and $`Y^{qr}1`$ has a simple zero at $`Y=\alpha `$. As in the previous case this implies

$`f_{T(qr)}(X,Y)`$ $`=`$ $`(X^{qr}1)(Y^{qr}1)f_T^{}(X^{qr},Y^{qr})`$   
$`=`$ $`(X\zeta )(Y\alpha )h(X,Y)`$   
for some $`h[X,Y]`$. Since $`f_T^{}(\zeta ^{qr},\alpha ^{qr})=f_T^{}(1,1)0`$, we have $`h(\zeta ,\alpha )0`$, and hence $`hP_i`$. Applying Lemma 3.5 we get $`(X\zeta )(Y\alpha )Q_i`$, and hence $`g_{qr}Q_i`$. If $`\alpha `$ is not a root of 1 we may choose $`r1`$ so that $`f_T^{}(\zeta ^{qr},\alpha ^{qr})=f_T^{}(1,\alpha ^{qr})0`$, since $`f_T^{}(1,1)0`$ implies that $`f_T^{}(1,Y)`$ has only finitely many zeros. Then $`X^{qr}1`$ has a simple zero at $`X=\zeta `$ and $`Y^{qr}1`$ is nonzero at $`Y=\alpha `$. By an argument similar to those used above we have $`f_{T(qr)}(X,Y)=(X\zeta )h(X,Y)`$ for some $`h[X,Y]`$ such that $`h(\zeta ,\alpha )0`$. This implies $`hP_i`$, so by Lemma 3.5 we get $`X\zeta Q_i`$, and hence $`g_qQ_i`$.

We’ve shown now that for each $`1ir`$ there is $`l_i1`$ such that $`g_{l_i}Q_i`$. Therefore we have $`g_lI`$ with $`l=\text{lcm}\{l_1,\mathrm{},l_r\}`$. It follows from Corollary 2.6 that $`T()`$ $``$-tiles an $`l\times l`$ square. To prove that $`T()`$ $``$-tiles a square it is sufficient to prove that $`g_l`$ is in the ideal $`I_0`$ in $`[X^{},Y^{}]`$ generated by $`T()`$. Equivalently, we need to show that $`g_l`$ is in the $``$-span of the set

$``$ $`=`$ $`\{X^iY^jf_{T(k)}:i,j,k,k1\}.`$   
We have shown that $`g_l`$ is in the $``$-span of $``$. Since $`g_l`$ and the elements of $``$ are all in $`[X^{},Y^{}]`$, and

$`[X^{},Y^{}]`$ $``$ $`[X^{},Y^{}]_{},`$   
it follows immediately that $`g_l`$ is in the $``$-span of $``$. This completes the proof of Theorem 3.1$`\mathrm{}`$

###### Corollary 3.6

Let $`T`$ be a $``$-weighted tile made up of rectangles whose corners all have rational coordinates. Assume that the weighted area of $`T`$ is not zero. Then there exists a positive integer $`w`$ such that $`T()`$ $``$-tiles a square with weight $`w`$.

Proof: By Theorem 3.1 we know that $`T()`$ $``$-tiles a square $`R`$, so there are rational numbers $`a_1,\mathrm{},a_n`$ and tiles $`T_1,\mathrm{},T_n`$, each a translation of some $`T(k_i)T()`$, such that $`R=a_1T_1+\mathrm{}+a_nT_n`$. Let $`w1`$ be a common denominator for $`a_1,\mathrm{},a_n`$. Then $`wR=wa_1T_1+\mathrm{}+wa_nT_n`$, and $`wa_i`$ for $`1in`$. Therefore $`T()`$ $``$-tiles $`wR`$$`\mathrm{}`$

## 4 Tiling with integer weights

Let $`T`$ be a $``$-weighted lattice tile, and assume that the weighted area of $`T`$ is not zero. By Corollary 3.6 we know that $`T`$ $``$-shapetiles a square with weight $`w`$ for some positive integer $`w`$. We wish to find necessary and sufficient conditions for $`T`$ to $``$-shapetile a square with weight 1. To express these conditions we need a definition. Given $`\mu \{\mathrm{}\}`$ we say that two lattice squares $`S_{ij}`$ and $`S_{i^{}j^{}}`$ belong to the same $`\mu `$-slope class if the line joining their centers has slope $`\mu `$. The tile $`T`$ can be decomposed into a sum $`T=C_1+\mathrm{}+C_k`$ of lattice tiles such that for each $`i`$ the unit lattice squares which make up $`C_i`$ all belong to the same $`\mu `$-slope class.

###### Proposition 4.1

Let $`T`$ be a $``$-weighted lattice tile and let $`n`$ be a positive integer. Let $`c`$ and $`d`$ be relatively prime integers and set $`\mu =c/d`$. Then the $`\mu `$-slope classes of $`T`$ all have weighted area divisible by $`n`$ if and only if $`f_T`$ is an element of the ideal $`((X^dY^c)(X1)(Y1),n(X1)(Y1))`$ in $`[X^{},Y^{}]`$.

Proof: The $`\mu `$-slope classes of $`T`$ all have weighted area divisible by $`n`$ if and only if we can write $`T=T_1+nT_2`$, where $`T_1`$ and $`T_2`$ are $``$-weighted lattice tiles such that the $`\mu `$-slope classes of $`T_1`$ all have weighted area zero. Write the decomposition of $`T_1`$ into its $`\mu `$-slope classes as $`T_1=C_1+\mathrm{}+C_k`$. Since $`\mu =c/d`$ with $`c`$ and $`d`$ relatively prime, the lattice squares $`S_{ij}`$ and $`S_{i^{}j^{}}`$ are in the same $`\mu `$-slope class if and only if $`S_{i^{}j^{}}`$ is the translation of $`S_{ij}`$ by $`(dr,cr)`$ for some $`r`$. Therefore if $`C_t`$ is the $`\mu `$-slope class of $`T_1`$ containing $`S_{ij}`$ we have

$`f_{C_t}(X,Y)`$ $`=`$ $`g(X^dY^c)X^iY^j(X1)(Y1)`$   
for some $`g[X^{}]`$. Since the weighted area of $`C_t`$ is zero we see that $`0=f_{C_t}^{}(1,1)=g(1)`$, which implies $`X1|g(X)`$. It follows that $`(X^dY^c1)(X1)(Y1)`$ divides $`f_{C_t}`$ for $`1tk`$, and hence also that $`(X^dY^c1)(X1)(Y1)`$ divides $`f_{T_1}`$. Conversely, if $`(X^dY^c1)(X1)(Y1)`$ divides $`f_{T_1}`$, it is easy to check that the $`\mu `$-slope classes of $`T_1`$ all have weighted area zero. It follows that the $`\mu `$-slope classes of $`T`$ all have area divisible by $`n`$ if and only if we can write

$`f_T(X,Y)`$ $`=`$ $`(X^dY^c1)(X1)(Y1)h_1(X,Y)+n(X1)(Y1)h_2(X,Y)`$   
for some $`h_1,h_2[X^{},Y^{}]`$. Since $`Y^c`$ is a unit in $`[X^{},Y^{}]`$ this is equivalent to $`f_T((X^dY^c)(X1)(Y1),n(X1)(Y1))`$$`\mathrm{}`$

###### Theorem 4.2

Let $`T`$ be a $``$-weighted lattice tile. Then $`T`$ $``$-shapetiles a square if and only if the following two conditions hold:

1. The weighted area of $`T`$ is not zero.
2. For every $`\mu ^\times `$ the gcd of the weighted areas of the $`\mu `$-slope classes of $`T`$ is 1.

Proof: Let $`T`$ be a tile which satisfies conditions 1 and 2. To show that $`T`$ $``$-shapetiles a square it is sufficient by Corollary 3.6 to show that $`T()\{wR\}`$ $``$-tiles a square, where $`R`$ is an $`l\times l`$ square and $`l,w`$ are positive integers. Let $`S=S_{00}`$ be the unit lattice square with lower left corner $`(0,0)`$. If $`T()\{wS\}`$ $``$-tiles an $`a\times a`$ square then by rescaling we see that $`T()\{wR\}`$ $``$-tiles an $`la\times la`$ square. Therefore it is sufficient to show that $`T()\{wS\}`$ $``$-tiles a square. Let $`J`$ be the ideal in $`[X^{},Y^{}]`$ generated by $`\{f_{T(k)}:k\}\{w(X1)(Y1)\}`$. By Corollary 2.6 it is sufficient to show that $`g_lJ`$ for some $`l1`$.

By the Hilbert basis theorem $`[X^{},Y^{}]`$ is a Noetherian ring. Therefore the ideal $`J`$ has a primary decomposition $`J=Q_1\mathrm{}Q_t`$. We need to show that there exists $`l1`$ such that $`g_lQ_i`$ for all $`i`$. As in the proof of Theorem 3.1 it is enough to show that for each $`i`$ there is $`l_i1`$ such that $`g_{l_i}Q_i`$. Let $`P_i=\sqrt{Q_i}`$ be the prime associated to $`Q_i`$, and suppose $`wP_i`$. Then since $`w(X1)(Y1)Q_i`$, by Lemma 3.5 we see that $`(X1)(Y1)=g_1`$ is in $`Q_i`$. If $`wP_i`$ then since $`P_i`$ is a prime ideal it follows that $`P_i`$ contains a prime integer $`p`$ which divides $`w`$, and hence that $`P_i=p`$.

For $`f[X^{},Y^{}]`$ let $`\overline{f}𝔽_p[X^{},Y^{}]`$ be the reduction of $`f`$ modulo $`p`$, where $`𝔽_p=/p`$ is the field with $`p`$ elements. Let $`\overline{P}_i`$ be the ideal in $`𝔽_p[X^{},Y^{}]`$ consisting of the reductions modulo $`p`$ of the elements of $`P_i`$. Since $`pP_i`$ the ideal $`\overline{P}_i`$ is prime. Let $`\overline{J}𝔽_p[X^{},Y^{}]`$ be the ideal consisting of the reductions modulo $`p`$ of the elements of $`J`$. Then $`\overline{J}`$ is generated by $`\{\overline{f}_{T(k)}:k1\}`$. Since $`P_iJ`$, we have $`\overline{P}_i\overline{J}`$.

Let $`K`$ be an algebraic closure of $`𝔽_p`$ and let $`V(\overline{J})K^\times \times K^\times `$ be the set of common zeros of the elements of $`\overline{J}`$. Let $`m`$ be the $`X`$-degree of $`\overline{f}_T`$, let $`n`$ be the $`Y`$-degree of $`\overline{f}_T`$, and define $`\overline{\mathrm{{\rm Y}}}K^\times \times K^\times `$ by

$`\overline{\mathrm{{\rm Y}}}`$ $`=`$ $`\{\zeta K^\times :\zeta ^k=1\text{ for some }1k2mn\}.`$   
###### Lemma 4.3

$`V(\overline{J})(K^\times \times \overline{\mathrm{{\rm Y}}})(\overline{\mathrm{{\rm Y}}}\times K^\times )`$.

Proof: Let $`(\alpha ,\beta )V(\overline{J})`$ and suppose neither $`\alpha `$ nor $`\beta `$ is in $`\overline{\mathrm{{\rm Y}}}`$. Then for $`1k2mn`$ we have

$$0=\overline{f}_{T(k)}(\alpha ,\beta )=\overline{f}_T(\alpha ^k,\beta ^k)=(\alpha ^k1)(\beta ^k1)\overline{f}_T^{}(\alpha ^k,\beta ^k).$$

Since $`\alpha `$ and $`\beta `$ aren’t in $`\overline{\mathrm{{\rm Y}}}`$ this implies that $`\overline{f}_T^{}(\alpha ^k,\beta ^k)=0`$ for $`1k2mn`$. Therefore by Lemma 3.4 there are relatively prime integers $`c,d`$ with $`c1`$ and $`d0`$ such that $`\overline{f}_T^{}(X^c,X^d)=0`$. Let $`𝒜`$ be the quotient ring $`𝔽_p[X^{},Y^{}]/(X^dY^c)`$, and let $`x,y`$ denote the images of $`X,Y`$ in $`𝒜`$. Then $`x`$ and $`y`$ are units in $`𝒜`$ satisfying $`x^d=y^c`$ with $`\mathrm{gcd}(c,d)=1`$, so there is $`z=x^ay^b`$ in $`𝒜^\times `$ such that $`x=z^c`$ and $`y=z^d`$. Therefore the image of $`\overline{f}_T^{}`$ in $`𝒜`$ is given by $`\overline{f}_T^{}(x,y)=\overline{f}_T^{}(z^c,z^d)`$, which equals zero since $`\overline{f}_T^{}(X^c,X^d)=0`$. It follows that $`X^dY^c`$ divides $`\overline{f}_T^{}`$, and hence that $`f_T^{}`$ is in the ideal $`(X^dY^c,p)`$ in $`[X^{},Y^{}]`$. Therefore $`f_T=(X1)(Y1)f_T^{}`$ is in the ideal

$$((X^dY^c)(X1)(Y1),p(X1)(Y1))$$

in $`[X^{},Y^{}]`$. Proposition 4.1 now implies that every $`\mu `$-slope class of $`T`$ has area divisible by $`p`$. This violates condition 2 of the theorem, so we have a contradiction. $`\mathrm{}`$

Set $`q=(2mn)!`$ and let $`V(\overline{g}_q)K^\times \times K^\times `$ be the set of zeros of $`\overline{g}_q`$. Since $`X^q1`$ has zeros at all elements of $`\overline{\mathrm{{\rm Y}}}`$, we have $`V(\overline{g}_q)(K^\times \times \overline{\mathrm{{\rm Y}}})(\overline{\mathrm{{\rm Y}}}\times K^\times )`$. Therefore Lemma 4.3 implies $`V(\overline{g}_q)V(\overline{J})`$. Since $`\overline{P}_i\overline{J}`$ we have $`V(\overline{J})V(\overline{P}_i)`$, and hence $`V(\overline{g}_q)V(\overline{P}_i)`$. As in Section 3 Hilbert’s Nullstellensatz implies that $`\overline{g}_q^k\overline{P}_i`$ for some $`k1`$. Since $`\overline{P}_i`$ is prime and

$`\overline{g}_q(X,Y)^k`$ $`=`$ $`(X^q1)^k(Y^q1)^k`$   
we have either $`X^q1\overline{P}_i`$ or $`Y^q1\overline{P}_i`$. It follows that $`P_i`$ contains one of the ideals $`(X^q1,p)`$ or $`(Y^q1,p)`$. We may assume without loss of generality that $`P_i(X^q1,p)`$.

By \[1, Prop. 7.14\] we have $`Q_iP_i^u`$ for some $`u1`$. Therefore it is enough to prove that for every $`u1`$ there is $`l1`$ such that $`g_lP_i^u`$. Let $`t`$ be a positive integer. Expanding $`X^{qt}1`$ in powers of $`X^q1`$ gives

$`X^{qt}1`$ $`=`$ $`1+((X^q1)+1)^t`$   
$`=`$ $`{\displaystyle \underset{j=1}{\overset{t}{}}}(\begin{array}{c}t\\ j\end{array})(X^q1)^j.`$   
If we choose $`t`$ to be divisible by a large power of $`p`$ then for small values of $`j1`$ the binomial coefficient $`(\begin{array}{c}t\\ j\end{array})`$ is divisible by a large power of $`p`$. Thus every term in this expansion is divisible either by a large power of $`p`$ or a large power of $`X^q1`$. It follows that there exists $`t1`$ such that $`X^{qt}1(X^q1,p)^u`$. Since $`P_i^u(X^q1,p)^u`$ we get $`g_{qt}P_i^u`$, as required.

Assume conversely that $`T`$ $``$-shapetiles a square. Then the weighted area of $`T`$ is clearly not equal to zero, so condition 1 of Theorem 4.2 is satisfied. We need to show that for every $`\mu ^\times `$ the gcd of the weighted areas of the $`\mu `$-slope classes of $`T`$ is equal to 1. If we knew that the scale factors and the coordinates of the translation vectors used in shapetiling the square were all in $``$, or even in $``$, we could prove this using polynomials in $`[X^{},Y^{}]`$. Since we have no right to make this assumption, we need to work in the ring $`[X^{},Y^{}]`$.

We may assume that the square which is shapetiled by $`T`$ is $`S=S_{00}`$, the unit square with lower left corner $`(0,0)`$. We have then $`S=a_1T_1+\mathrm{}+a_kT_k`$, where $`a_i`$ and each $`T_i`$ is a translation of some $`T(\rho _i)`$. Let $`p`$ be prime and suppose that for some $`\mu ^\times `$ the areas of the $`\mu `$-slope classes of $`T`$ are all divisible by $`p`$. Let $`c,d`$ be integers such that $`\mathrm{gcd}(c,d)=1`$ and $`\mu =c/d`$. Let $`\overline{f}_T𝔽_p[X^{},Y^{}]`$ be the reduction of $`f_T`$ modulo $`p`$, and for $`1in`$ let $`\overline{f}_{T_i}𝔽_p[X^{},Y^{}]`$ be the reduction of $`f_{T_i}`$. Then by Proposition 4.1 we see that $`(X^dY^c)(X1)(Y1)`$ divides $`\overline{f}_T`$ (in $`𝔽_p[X^{},Y^{}]`$, and hence also in $`𝔽_p[X^{},Y^{}]`$). Therefore by Lemma 2.7 and Lemma 2.4 we see that $`\overline{f}_{T_i}`$ is divisible by

$$(X^{\rho _id}Y^{\rho _ic})(X^{\rho _i}1)(Y^{\rho _i}1).$$

Define a ring homomorphism $`\mathrm{\Psi }:𝔽_p[X^{},Y^{}]𝔽_p[X^{}]`$ by setting $`\mathrm{\Psi }(f)=f(X^c,X^d)`$. Since $`\mathrm{\Psi }(X^{\rho _id}Y^{\rho _ic})=0`$, the divisibility relation from the preceding paragraph implies that $`\mathrm{\Psi }(\overline{f}_{T_i})=0`$ for $`1in`$. On the other hand, since $`\overline{f}_S=\overline{g}_1=(X1)(Y1)`$, we have

$`\mathrm{\Psi }(\overline{f}_S)`$ $`=`$ $`X^{c+d}X^cX^d+1,`$   
which is nonzero since $`c`$ and $`d`$ are nonzero. Since $`S=a_1T_1+\mathrm{}+a_kT_k`$ we have $`\overline{f}_S=\overline{a}_1\overline{f}_{T_1}+\mathrm{}+\overline{a}_k\overline{f}_{T_k}`$ with $`\overline{a}_i𝔽_p`$, which gives a contradiction. Therefore the areas of the $`\mu `$-slope classes of $`T`$ can’t all be divisible by $`p`$, so condition 2 is satisfied. This completes the proof of Theorem 4.2$`\mathrm{}`$

Example 4.5 Let $`T`$ be the lattice tile pictured in Figure 2a. Since $`T`$ has area $`40`$, it follows from Theorem 3.1 that $`T`$ $``$-shapetiles a square. But since the nonempty 1-slope classes of $`T`$ both have area 2, Theorem 4.2 implies that $`T`$ does not $``$-shapetile a square.

Example 4.6 Let $`a,b,c,d`$ be positive integers with $`a>c`$ and $`b>d`$. We construct a lattice tile $`T`$ by removing a $`c\times d`$ rectangle from the upper right corner of an $`a\times b`$ rectangle, as in Figure 2b. The area of $`T`$ is $`abcd>0`$, so the first condition of Theorem 4.2 is satisfied. If $`\mu >0`$ there is a $`\mu `$-slope class of $`T`$ consisting of just the upper left corner square, while if $`\mu <0`$ there is a $`\mu `$-slope class of $`T`$ consisting of just the lower left corner square. In either case $`T`$ has a $`\mu `$-slope class whose area is 1. Therefore the second condition of Theorem 4.2 is also satisfied, so $`T`$ $``$-shapetiles a square.

Example 4.7 The simplest case of Example 2 occurs when $`a=b=2`$ and $`c=d=1`$. In this case we have $`f_T(X,Y)=(1+X+Y)(X1)(Y1)`$. A straightforward calculation shows that

$$\begin{array}{c}XYg_3(X,Y)=(X^3Y^3X^2Y^2X^4X^4YX^4Y^2Y^4XY^4X^2Y^4)f_T(X,Y)\\ +(XY1)f_{T(2)}(X,Y)+f_{T(3)}(X,Y).\end{array}$$

This gives the $``$-tiling of a $`3\times 3`$ square with lower left corner $`(1,1)`$ depicted in Figure 3. The left side of Figure 3 has tiles with weight 1 and the right side has tiles with weight $`1`$. The total weights of the tiles covering each region are indicated.