%Article: - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - %Author: J. B. Kelly %Title: Polynomials and Polyominoes \hoffset=-5mm \voffset=-5mm \hsize=17cm \vsize=25cm \parskip=2pt \font\sc=cmcsc10 \centerline{{\bf Polynomials and Polyominoes}} \centerline{{\sc J. B. Kelly} \footnote{\dag}% {Arizona State University}} \centerline{American Mathematical Monthly 73 (1966) 464--471} {\bf 1. The associated polynomial.} Let $S$ be a finite set of lattice points (i.e. points with integral coordinates) in $k$-dimensional Euclidean space, $E_k$. There will be no loss in generality in assuming that $S$ is contained in $E'_k$, where $E'_k$ is that portion of $E_k$ in which all points have nonnegative coordinates. With the point $p$ of $S$ having the integral coordinates $n_1, n_2, \cdots, n_k$, we associate the monomial $$ M(p) = x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k} \;. $$ With $S$ itself we associate the polynomial $P(S) = \sum M(p)$, the summation being extended over all points of $S$. In particular, with the lattice points of the rectangluar parallelopiped $R$, which has one vertex at the origin and lies in $E'_k$, we associate the polynomial, $P(R)$, where $$ P(R) = \prod_{i=1}^{k} {x_i^{l_i} - 1 \over x_i - 1} \;. \leqno(1) $$ Here $(l_1 - 1, l_2 - 1, \cdots, l_i - 1, \cdots, l_k - 1)$ is the point of $R$ farthest from the origin. Let $T_1, T_2, \cdots, T_r$ be finite sets of lattice pointes in $E'_k$ and let $P(T_1), P(T_2), \cdots, P(T_r)$ be their associated polynomials. We say that $S$ is covered by $T_1, T_2, \cdots, T_r$ if every point of $S$ is covered exactly once by suitable translations of $T_1, T_2, \cdots, T_r$ and if no point not in $S$ is covered by these translations. This means that there exist polynomials $Q_1, Q_2, \cdots, Q_r$ in $x_1, x_2, \dots, x_k$ with coefficients 0 or 1 such that $$ P(S) = \sum_{i=1}^{r} Q_i(x_1, x_2, \cdots, x_k) P(T_i). \leqno(2) $$ (We can assume that $T_1, T_2, \cdots, T_r$ have at least one point on each coordinate axis. Then no negative exponents can occur in $Q_1, Q_2, \cdots, Q_r$.) It follows that $P(S)$ must belong to the polynomial ideal generated by $P(T_1), P(T_2), \cdots, P(T_r)$. The ring of coefficients may be any ring containing a subring isomorphic to the ring of rational integers; we shall find it convenient to employ the fields of real and complex numbers. If $(\xi_1, \xi_2, \cdots, \xi_k)$ is a point in the manifold of the ideal $(P(T_1), P(T_2), \cdots, P(T_r))$, i.e. a point with coordinates in a suitable extension of the ring of coefficients at which $P(T_1), P(T_2), \cdots, P(T_r)$ all vanish, then $P(S)$ must vanish there also. This is not, of course, a sufficient condition that $P(S)$ belong to the ideal. To every lattice point $p$ in $E_k$ there corresponds a unique $k$-dimensional unit cube having vertices with integral coordinates, $p$ being one of them, with no vertex having any coordinate less than the corresponding coordinate of $p$. (For example, in the two-dimensional case, we have a square with horizontal and vertical sides, and with $p$ as its southwest corner.) Hence to every configuration $S$ of lattice points there corresponds a solid region, $\overline{S}$, composed of these cubes. We set $P(\overline{S}) = P(S)$. Thus any problem involving the covering of such solid regions by other such regions may be reduced to a problem involving the corresponding configurations of lattice points. Note that (1) gives the associated polynomial of a solid rectangular parallelopiped with one vertex at the origin and sides parallel to the coordinate axes of length $l_1, l_2, \cdots, l_k$. In the case $k=2$, such a ``solid'' region, when ``rookwise'' connected, was called a ``polyomino'' by Golomb, in his interesting paper [1] on checkerboard recreations. Here we shall use the word, ``polyomino,'' to mean any such solid region, for any value of $k$. Golomb discusses problems of covering a full or deleted checkerboard with polyominoes of prescribed form. His principal tool is a ``coloring'' of the checkerboard. As will readily be seen, this corresponds to assigning certain values to $x_1$ and $x_2$ in our formulation. \smallskip {\bf 2. Examples.} In this section we shall show how (2) may be used to obtain necessary conditions for the existence of a solution of various problems involving coverings by polyominoes. Primarily we shall use the fact that $P(\overline{S})$ must vanish on the manifold of $(P(T_1), P(T_2), \cdots, P(T_r))$. It seems to be more difficult to take significant advantage of the requirement that the coefficients of $Q_1, Q_2, \cdots, Q_r$ be 0 or 1. {\it Example I:} %% (X X) We begin with a well-known checkerboard problem from [1] which may easily be solved without recourse to our method of associated polynomials. Can one cover a checkerboard with one pair of opposite corners removed, with $1 \times 2$ dominoes? If $\overline{S}$ is the deleted checkerboard, then $$ P(\overline{S}) = {x_1^{8} - 1 \over x_1 - 1} \cdot {x_2^{8} - 1 \over x_2 - 1} - 1 - x_1^7 x_2^7 \;. $$ If $\overline{T}_1$ is the domino in its horizontal position and $\overline{T}_2$ is the domino in its vertical position then $P(\overline{T}_1) = 1 + x_1$ and $P(\overline{T}_2) = 1 + x_2$. From (2) we have $$ {x_1^{8} - 1 \over x_1 - 1} \cdot {x_2^{8} - 1 \over x_2 - 1} - 1 - x_1^7 x_2^7 = Q_1(x_1,x_2) (1 + x_1) + Q_2(x_1,x_2) (1 + x_2) \;. $$ Setting $x_1 = -1$, $x_2 = -1$, we arrive at a contradiction, so that the desired covering is impossible. Notice that with these values of $x_1$ and $x_2$, $x_1^{n_1} x_2^{n_2}$ has one value $(\pm 1)$ on all the black squares of the checkerboard in the usual coloring, and its negative $(\mp 1)$ on the white squares. This observation relates our solution of the problem to the more elementary solution which consists simply in remarking that the proposed covering is impossible because the deleted checkerboard does not contain equal numbers of black and white squares. The remaining examples in this section deal with the covering of rectangular $k$-dimensional parallelopipeds by ``straight'' polyominoes. By a straight polyomino we shall mean the solid region corresponding to a set of lattice points in $E_k$ lying on a straight line parallel to one of the coordinate axes. A straight polyomino is not necessarily connected. A straight polyomino is symmetric if it is invariant under reflection in its center. {\it Example II:} %% (X X . X . X X) Is there some rectangular parallelopiped which can be covered by the straight symmetric polyomino formed by taking seven adjacent cubes and deleting the third and fifth? (In this, and in the subsequent examples, we agree that the polyominoes may be placed parallel to any axis.) If the polyomino is parallel to the $x_i$-axis, the associated polynomial for this position is $1 + x_i + x_i^3 + x_i^5 + x_i^6$. If the problem has a solution, we see, from (1) and (2), that we must have $$ \prod_{i=1}^{k} {x_i^{l_i} - 1 \over x_i - 1} = \sum_{i=1}^{k} Q_i(x_1, x_2, \dots, x_k) (1 + x_i + x_i^3 + x_i^5 + x_i^6). \leqno(3) $$ for some choise of the positive integers $l_1, l_2, \cdots, l_k$. The polynomial $1 + x + x^3 + x^5 + x^6$ has a root, $\lambda$, between $0$ and $-1$. If we put $x_1 = x_2 = \dots = x_k = \lambda$, we obtain a contradiction from (3), inasmuch as all roots of $x_i^{l_i} - 1$ lie on the unit circle. Therefore the problem has no solution. We have made implicit use here of the theorem that a real function continuous on a closed interval assumes in that interval all values between its values at the end-points of the interval. The method of associated polynomials makes available some of the simpler theorems analysis for the handling of problems involving lattice point configurations. {\it Example III:} %% (X X . X X) Is there a rectangular $k$-dimensional parallelopiped which can be covered by the straight polyomino formed by taking five consecutive cubes and deleting the middle one? Proceeding as in example II, we obtain the condition $$ P(\overline{S}) = \prod_{i=1}^{k} {x_i^{l_i} - 1 \over x_i - 1} = \sum_{i=1}^{k} Q_i(x_1, x_2, \dots, x_k) (1 + x_i + x_i^3 + x_i^4) = \sum_{i=1}^{k} Q_i(x_1, x_2, \dots, x_k) (1 + x_i)^2 (1 - x_i + x_i^2). \leqno(4) $$ The remainder of the argument cannot be the same as in example II because all the roots of the polynomial $1 + x + x^3 + x^4$ are roots of unity. Thus it is possible to select the sides $l_i$ so that $P(S)$ vanishes on the manifold of the ideal $(1 + x_1 + x_1^3 + x_1^4, \cdots, 1 + x_k + x_k^3 + x_k^4)$. But nevertheless $P(S)$ does not belong to this ideal, for any polynomial in the ideal, when expanded in powers of $1 + x_1, 1 + x_2, \cdots, 1 + x_k$ has no term in $$ (1 + x_1)(1 + x_2) \cdots (1 + x_k), \quad \hbox{whereas} \quad { \partial^k P(\overline{S}) \over \partial x_1 \cdots \partial x_k } \ne 0 $$ when $x_1 = x_2 = \cdots = x_k = -1$ unless some $l_i = 1$. This later case is easily excluded. {\it Example IV:} %% (X X X . X X X) Is there a rectangular $k$-dimensional parallelopiped which can be covered by the straight polyomino formed by taking seven adjacent cubes and deleting the middle one? Proceeding just as before, we obtain $$ P(\overline{S}) = \prod_{i=1}^{k} {x_i^{l_i} - 1 \over x_i - 1} = \sum_{i=1}^{k} Q_i(x_1, x_2, \dots, x_k) (1 + x_i + x_i^2 + x_i^4 + x_i^5 + x_i^6) = \sum_{i=1}^{k} Q_i(x_1, x_2, \dots, x_k) { (x_i^4 + 1) (x_i^3 - 1) \over x_i - 1} . \leqno(5) $$ Again, the roots of $1 + x + x^2 + x^4 + x^5 + x^6$ are all roots of unity. In this case, however, $P(\overline{S})$ will belong to the ideal $(1 + x_1 + x_1^2 + x_1^4 + x_1^5 + x_1^6, \cdots, 1 + x_k + x_k^2 + x_k^4 + x_k^5 + x_k^6)$ if the integers $l_i$ are divisible by 24. This follows from the fact that $x^{24} - 1$ is divisible by $(x^3 - 1) (x^4 + 1)$. To handle the problem it is necessary then to make use of the condition that the coefficients of the polynomials $Q_i(x_1, x_2, \dots, x_k)$ be 0 or 1, or possibly, of the weaker condition, that they be nonnegative. We have had no success with this; we can say only that no solution exists when $k = 2$, a fact established by trail and error. The case $k > 2$ is open. {\it Example V:} %% (X . X X . X) The preceding examples may lead one to suspect that any straight, symmetric polyomino which cannot cover any segment, cannot cover any rectangular parallelopiped. A polyomino formed by taking six adjacent cubes and removing the second and fifth obviously cannot cover any segment, but such a polyomino can cover a $7 \times 12$ rectangle. This is shown in Figure 1. There the polyominoes are numbered from 1 to 21 and a square numbered $a$, $1 \leq a \leq 21$, is covered by the polyomino numbered $a$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 15 08 16 08 08 13 08 13 13 19 13 21 % % 05 14 05 05 17 05 12 18 12 12 20 12 % % 15 04 16 04 04 11 04 11 11 19 11 21 % % 15 14 16 07 17 07 07 18 07 19 20 21 % % 03 14 03 03 17 03 10 18 10 10 20 10 % % 15 02 16 02 02 09 02 09 09 19 09 21 % % 01 14 01 01 17 01 06 18 06 06 20 06 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% $$\vbox{ \halign{ \strut \vrule height 4mm depth 2mm \hbox to 6mm { \hfil # \hfil } \vrule && \hbox to 6mm { \hfil # \hfil } \vrule \cr \noalign{\hrule} 15& 8&16& 8& 8&13& 8&13&13&19&13&21\cr \noalign{\hrule} 5&14& 5& 5&17& 5&12&18&12&12&20&12\cr \noalign{\hrule} 15& 4&16& 4& 4&11& 4&11&11&19&11&21\cr \noalign{\hrule} 15&14&16& 7&17& 7& 7&18& 7&19&20&21\cr \noalign{\hrule} 3&14& 3& 3&17& 3&10&18&10&10&20&10\cr \noalign{\hrule} 15& 2&16& 2& 2& 9& 2& 9& 9&19& 9&21\cr \noalign{\hrule} 1&14& 1& 1&17& 1& 6&18& 6& 6&20& 6\cr \noalign{\hrule} } } \atop \hbox{Fig. 1}% $$ \smallskip {\bf 3. The box problem.} Most of the results in the preceding section were of a negative character. In this section we shall discuss what is perhaps the simplest problem of polyomino coverings, obtain a necessary condition for its solvability by means of the method of associated polynomials and then show that this necessary condition, together with an auxiliary condition, is sufficiently strong to guarantee the existence of a solution. The problem, which we have called the box problem, is the following: Under what circumstances is it possible to stack $k$-dimensional ``boxes'' with integral sides $b_1, b_2, \cdots, b_k$ in a $k$-dimensional ``room'' with sides $r_1, r_2, \cdots, r_k$ so that the room is completely filled? Clearly, the volume of one of the boxes must divide the volume of the room and each of the numbers $r_1, r_2, \cdots, r_k$ must be a linear combination of $b_1, b_2, \cdots, b_k$, with nonnegative integral coefficients. We prove a demonstrably stronger necessary condition: \item{(A)} %%% Property A %%% {\it If an arbitrary integer $h$ divides $t_h$ of the integers $b_1, b_2, \cdots, b_k$, \par it must divide at least $t_h$ of the integers $r_1, r_2, \cdots, r_k$.} It follows from (A) that, for example, a $30 \times 30$ square cannot be covered by $4 \times 9$ rectangles even though $30 \times 30$ is divisible by $4 \times 9$ and $30 = 2 \cdot 9 + 3 \cdot 4$. {\it Proof of} (A). From (1) and (2) we have $$ \prod_{i=1}^{k} {x_i^{r_i} - 1 \over x_i - 1} = \sum_{\sigma} Q_{\sigma}(x_1, x_2, \dots, x_k) \prod_{i=1}^{k} {x_{\sigma(i)}^{b_i} - 1 \over x_{\sigma(i)} - 1} \, , \leqno(6) $$ the summation being extended over all permutations $\sigma$ of the integers $1, 2, \cdots, k$. Each permutation corresponds to a different way of stacking the boxes. Suppose that only $q$ of the integers $r_1, r_2, \cdots, r_k$ are divisible by $h$, where $q < t_h$. Then $k-q$ of the integers $r_1, r_2, \cdots, r_k$ are not divisible by $h$. We may assume that these are $r_1, r_2, \cdots, r_{k-q}$. In (6), let $x_1 = x_2 = \dots = x_{k-q} = \omega$ where $\omega$ is a primitive $h$th root of unity. In each product on the right side of (6) there is at least one factor which vanishes, since $k-q+t_h > k-q+q=k$. Thus the right side of (6) vanishes identically in $x_{k-q+1}, \cdots, x_k$, whereas the left side does not. Condition (A) is clearly not sufficient. For example, it is impossible to fill a $48 \times 48 \times 1$ room with $2 \times 3 \times 4$ boxes, although condition (A) is satisfied. What is needed is an additional condition which ensures that $r_1, r_2, \cdots, r_k$ may be expressed as linear combinations, with positive integral coefficients, of $b_1, b_2, \cdots, b_k$. Such a condition is \item{(B)} %%% Property B %%% {\it $r_1, r_2, \cdots, r_k$ are sufficiently large. } That is, there exists a positive integer, $N$, such that if $r_i > N$, $i = 1, 2, \cdots, k$, and the set\footnote{*}% {Set stands for multiset. The $b$'s and $r$'r need not be distinct.} $\{ r_1, r_2, \cdots, r_k \}$ satisfies condition (A), then the box problem has a solution. Here $N$ depends upon $b_1, b_2, \cdots, b_k$. We prove that condition (A) and (B) are sufficient for the existence of a solution of the box problem. Our plan is to split the room into smaller parallelopipeds, each of whose sides is divisible by a different number in the set $b_1, b_2, \cdots, b_k$. These smaller parallelopipeds are then obviously coverable by boxes of sides $b_1, b_2, \cdots, b_k$; hence the room is also. Two lemmas, both well-known results, are required. {\sc Lemma I.} %% Frobenius Problem. {\it Let $a_1, a_2, \cdots, a_n$ be any set of positive integers, and let $\delta$ be their greatest common divisor. Any sufficiently large integer which is divisible by $\delta$ may be expressed as a linear combination of $a_1, a_2, \cdots, a_n$ with positive coefficients. } An account of recent work based upon this lemma may be found in [2]. It was known to Frobenius, and may have been noticed by earlier mathematicians. {\sc Lemma II.} %% marriage theorem of Hall {\it Given $k$ objects, each of which possesses one or more of the attributes $P_1, P_2, \cdots, P_k$. For any set of $j$ attributes, let there exists $j$ objects each possessing at least one attribute of the set. Then it is possible to pair each object with one of its attributes in such a way that no two objects are paired with the same attribute. } This lemma is due to P. Hall [3]. Let us order all nonempty subsets of $b_1, b_2, \cdots, b_k$ by means of an index $j$, running from $1$ to $2^k - 1$. Let $b_{j_1}, b_{j_2}, \cdots, b_{j_{m_j}}$ be the elements of the $j$th subset. Let $\delta_j$ be the greatest common divisor of $b_{j_1}, b_{j_2}, \cdots, b_{j_{m_j}}$. Condition (A) implies that $\delta_j$ divides at least $m_j$ of the integers $r_1, r_2, \cdots, r_k$. Suppose that ${j_1}, {j_2}, \cdots, {j_{\alpha_i}}$ are the indices of those greatest common divisors which divide $r_i$. Condition (A) gives $\alpha_i \geq 1$. Then we may write $$ r_i = \sum A^{(i)}({j_1, l_1}, {j_2, l_2}, \cdots, {j_{\alpha_i}, l_{\alpha_i}}) , \leqno(7) $$ where the summation extends over all possible sets of values of ${l_1}, {l_2}, \cdots, {l_{\alpha_i}}$ such that $$ 1 \leq l_1 \leq m_{j_1}, \; 1 \leq l_2 \leq m_{j_2}, \; \cdots , \; 1 \leq l_{\alpha_i} \leq m_{j_{\alpha_i}} , $$ and where the positive integer $A^{(i)}({j_1, l_1}, {j_2, l_2}, \cdots, {j_{\alpha_i}, l_{\alpha_i}})$ is divisible by each of the integers $b_{j_1 l_1}, b_{j_2 l_2}, \cdots$, $ b_{j_{\alpha_i} l_{\alpha_i}}$. This result follows at once from the fact that the positive integers form a distributive lattice under the operations $\cap =$ least common multiple and $\cup =$ greatest common divisor. One infers that $r_i$ is divisible by the greatest common divisor of all the least common multiples one can form by taking one $b$ from each set associated with the $\alpha_i$ $\delta$'s dividing $r_i$. If we apply Lemma I, identifying the integers $a_1, a_2, \cdots, a_n$ with these least common multiples, we see that the integers $A^{(i)}({j_1, l_1}, {j_2, l_2}, \cdots, {j_{\alpha_i}, l_{\alpha_i}})$ may be chosen to be positive if $r_i$ is sufficiently large. We now divide our $k$-dimensional room into smaller parallelopipeds by splitting the sides as indicated by (7). The sides of a representative smaller parallelopiped will be $$ A^{(1)} ({j_1, l_1}, {j_2, l_2}, \cdots, {j_{\alpha_1}, l_{\alpha_1}}) \cdots A^{(k)} ({j'_1, l'_1}, {j'_2, l'_2}, \cdots, {j'_{\alpha_k}, l'_{\alpha_k}}) . \leqno(8) $$ We apply Lemma II, the $k$ objetcs being the sides of the smaller parallelopiped and the $k$ attributes being divisibility by $b_1, b_2, \cdots, b_k$. We show that the hypothesis of Lemma II is fulfilled. Let $\delta_j$ be the greatest common divisor of some set of $m_j$ $b$'s. Then $\delta_j$ will divide at least $m_j$ of the positive integers $r_1, r_2, \cdots, r_k$; by our construction, therefore, at least $m_j$ of the positive integers (8) are divisible by at least one member of the given set of $b$'s. From Lemma II we conclude that it is possible to pair each side of the smaller parallelopiped with a distinct member of the set $b_1, b_2, \cdots, b_k$ which will divide it. Thus this parallelopiped may be covered with boxes of sides $b_1, b_2, \cdots, b_k$. The larger room with sides $r_1, r_2, \cdots, r_k$ may then also be so covered. N. G. de~Bruijn, in a problem published in the Hungarian journal, {\it Mathematikai Lapok}\footnote{\dag}% {12 (1961) 110 Problem 109 and 13 (1962) 314 Problem 119}, around 1960, dealt with an interesting aspect of the box-problem. He showed that if the box problem has a solution and if $b_1$ divides $b_2$, $b_2$ divides $b_3$, etc., then the boxes may all be given the same orientation. Moreover, if every room covered by boxes of dimensions $b_1 \leq b_2 \leq b_3 \leq \cdots \leq b_k$ may be covered by boxes with the same orientation, then $b_1$ divides $b_2$, $b_2$ divides $b_3$, etc. In the course of his proof, de~Bruijn established the necessary portion of our box problem for boxes with dimensions $1 \times 1 \times 1 \times \cdots \times m$. His method was similar to ours and may be extended to the more general case. \smallskip {\bf Conclusion.} Certain mathematical games involving ``jumping'' may be discussed by means of associated polynomials. One allows the associated polynomials to have coefficients $-1, 0, 1$ in such a case. In treating questions involving multiple covering of lattice points, the sole restriction that one need place on $Q_1, Q_2, \cdots, Q_r$ is that they have nonnegative integral coefficients. Interesting problems arise when one considers infinite sets of lattice points. Here the associated polynomial becomes an associated formal power series. If one substitutes real or complex numbers for the indeterminates, convergence difficulties present themselves, particularly if the configuration extends from $-\infty$ to $+\infty$ in some direction. Fundamentally, the method of attack in this paper goes back to Descartes. The associated polynomial is merely the ``coordinate'' of the polyomino. \bigbreak % - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - \def\bib{\par\noindent\hangindent 20pt} \centerline{ {\bf References} } \bib [1] \enspace Solomon W. Golomb, Checkerboards and polyominoes, American Mathematical Monthly, 61 (Dec. 1954) 675--682. Zbl. 57.1005. \bib [1*] \enspace Solomon W. Golomb, Polyominoes, New York: Scribners, 1965. \bib [2] \enspace Alfred Brauer and James E. Shockley, On a problem of Frobenius, Journal f\"ur die Reine und Angewandte Mathematik, 211 (1962) 215--220. Zbl. 108.4604. \bib [3] \enspace P. Hall, On representatives of subsets, Journal of the London Mathematical Society, 10 (part I) (1935) 26--30. Zbl. 10.34503. \bib [4*] \enspace Nicholas G. de~Bruijn, Filling boxes with bricks, American Mathematical Monthly, 76 (Jan. 1969) 37--40. Zbl. 174.25501. \smallskip \noindent References indicated with a star are additions. \bye