Polynomials and Polyominoes J. B. Kelly † American Mathematical Monthly 73 (1966) 464–471 1. The associated polynomial. Let S be a finite set of lattice points (i.e. points with integral coordi-

nates) 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}, ⋯, n_{k}, we associate the monomial

M(p) = x_{1}^{n_{1}}x_{2}^{n_{2}} ⋯ x_{k}^{n_{k}} .

With S itself we associate the polynomial P (S) = ∑ 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

(1)  P (R) = ∏_{i=1}^{k} \frac{x_{i}^{l_{i}} − 1}{x_{i} − 1} .

Here (l_{1} − 1, l_{2} − 1, ⋯, l_{i} − 1, ⋯, l_{k} − 1) is the point of R farthest from the origin.

Let T_{1}, T_{2}, ⋯, T_{r} be finite sets of lattice pointes in E′_{k} and let P (T_{1}), P (T_{2}), ⋯, P (T_{r}) be their associated polynomials. We say that S is covered by T_{1}, T_{2}, ⋯, T_{r} if every point of S is covered exactly once by suitable translations of T_{1}, T_{2}, ⋯, T_{r} and if no point not in S is covered by these translations. This means that there exist polynomials Q_{1}, Q_{2}, ⋯, Q_{r} in x_{1}, x_{2}, …, x_{k} with coefficients 0 or 1 such that

(2)  P (S) = ∑_{i=1}^{r} Q_{i}(x_{1}, x_{2}, ⋯, x_{k})P (T_{i}).

(We can assume that T_{1}, T_{2}, ⋯, T_{r} have at least one point on each coordinate axis. Then no negative exponents can occur in Q_{1}, Q_{2}, ⋯, Q_{r}.) It follows that P (S) must belong to the polynomial ideal generated by P (T_{1}), P (T_{2}), ⋯, 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 (ξ_{1}, ξ_{2}, ⋯, ξ_{k}) is a point in the manifold of the ideal (P (T_{1}), P (T_{2}), ⋯, 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}), ⋯, 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}, ⋯, 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.

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}), ⋯, P (T_{r})). It seems to be more difficult to take significant advantage of the requirement that the coefficients of Q_{1}, Q_{2}, ⋯, Q_{r} be 0 or 1.

Example I: 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 × 2 dominoes? If \overline{S} is the deleted checkerboard, then

P (\overline{S}) = \frac{x_{1}^{8} − 1}{x_{1} − 1} · \frac{x_{2}^{8} − 1}{x_{2} − 1} − 1 − x_{1}^{7}x_{2}^{7} .

† Arizona State University 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

\frac{x_{1}^{8} − 1}{x_{1} − 1} · \frac{x_{2}^{8} − 1}{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 (±1) on all the black squares of the checkerboard in the usual coloring, and its negative (∓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.

Example II: 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

(3)  ∏_{i=1}^{k} \frac{x_{i}^{l_{i}} − 1}{x_{i} − 1} = ∑_{i=1}^{k} Q_{i}(x_{1}, x_{2}, …, x_{k})(1 + x_{i} + x_{i}^{3} + x_{i}^{5} + x_{i}^{6}).

for some choise of the positive integers l_{1}, l_{2}, ⋯, l_{k}.

The polynomial 1 + x + x^{3} + x^{5} + x^{6} has a root, λ, between 0 and −1. If we put x_{1} = x_{2} = … = x_{k} = λ, 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.

Example III: 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

(4) P (\overline{S}) = ∏_{i=1}^{k} \frac{x_{i}^{l_{i}} − 1}{x_{i} − 1} = ∑_{i=1}^{k} Q_{i}(x_{1}, x_{2}, …, x_{k})(1 + x_{i} + x_{i}^{3} + x_{i}^{4}) = ∑_{i=1}^{k} Q_{i}(x_{1}, x_{2}, …, x_{k})(1 + x_{i})^{2}(1 − x_{i} + x_{i}^{2}).

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}, ⋯, 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}, ⋯, 1 + x_{k} has no term in

(1 + x_{1})(1 + x_{2}) ⋯ (1 + x_{k}), whereas \frac{∂^{k}P (\overline{S})}{∂x_{1} ⋯ ∂x_{k}} ≠ 0

when x_{1} = x_{2} = ⋯ = x_{k} = −1 unless some l_{i} = 1. This later case is easily excluded.

Example IV: 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 (5)

P (\overline{S}) = ∏_{i=1}^{k} \frac{x_{i}^{l_{i}} − 1}{x_{i} − 1} = ∑_{i=1}^{k} Q_{i}(x_{1}, x_{2}, …, x_{k})(1+x_{i} +x_{i}^{2} +x_{i}^{4} +x_{i}^{5} +x_{i}^{6}) = ∑_{i=1}^{k} Q_{i}(x_{1}, x_{2}, …, x_{k})\frac{(x_{i}^{4} + 1)(x_{i}^{3} − 1)}{x_{i} − 1}.

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}, ⋯, 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}, …, 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.

Example V: 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 × 12 rectangle. This is shown in Figure 1. There the polyominoes are numbered from 1 to 21 and a square numbered a, 1 ≤ a ≤ 21, is covered by the polyomino numbered a.

15 8 16 8 8 13 8 13 13 19 13 21 5 14 5 5 17 5 12 18 12 12 20 12 15 4 16 4 4 11 4 11 11 19 11 21 15 14 16 7 17 7 7 18 7 19 20 21 3 14 3 3 17 3 10 18 10 10 20 10 15 2 16 2 2 9 2 9 9 19 9 21 1 14 1 1 17 1 6 18 6 6 20 6 Fig. 1

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}, ⋯, b_{k} in a k-dimensional “room” with sides r_{1}, r_{2}, ⋯, 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}, ⋯, r_{k} must be a linear combination of b_{1}, b_{2}, ⋯, b_{k}, with nonnegative integral coefficients. We prove a demonstrably stronger necessary condition: (A) If an arbitrary integer h divides t_{h} of the integers b_{1}, b_{2}, ⋯, b_{k},

it must divide at least t_{h} of the integers r_{1}, r_{2}, ⋯, r_{k}.

It follows from (A) that, for example, a 30 × 30 square cannot be covered by 4 × 9 rectangles even though 30 × 30 is divisible by 4 × 9 and 30 = 2 · 9 + 3 · 4.

Proof of (A). From (1) and (2) we have

(6)  ∏_{i=1}^{k} \frac{x_{i}^{r_{i}} − 1}{x_{i} − 1} = ∑_{σ} Q_{σ}(x_{1}, x_{2}, …, x_{k}) ∏_{i=1}^{k} \frac{x_{σ(i)}^{b_{i}} − 1}{x_{σ(i)} − 1} ,

the summation being extended over all permutations σ of the integers 1, 2, ⋯, k. Each permutation corresponds to a different way of stacking the boxes.

Suppose that only q of the integers r_{1}, r_{2}, ⋯, r_{k} are divisible by h, where q < t_{h}. Then k − q of the integers r_{1}, r_{2}, ⋯, r_{k} are not divisible by h. We may assume that these are r_{1}, r_{2}, ⋯, r_{k−q}. In (6), let x_{1} = x_{2} = … = x_{k−q} = ω where ω is a primitive hth 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}, ⋯, x_{k}, whereas the left side does not.

Condition (A) is clearly not sufficient. For example, it is impossible to fill a 48 × 48 × 1 room with 2 × 3 × 4 boxes, although condition (A) is satisfied. What is needed is an additional condition which ensures that r_{1}, r_{2}, ⋯, r_{k} may be expressed as linear combinations, with positive integral coefficients, of b_{1}, b_{2}, ⋯, b_{k}. Such a condition is (B) r_{1}, r_{2}, ⋯, r_{k} are sufficiently large.

That is, there exists a positive integer, N, such that if r_{i} > N, i = 1, 2, ⋯, k, and the set* {r_{1}, r_{2}, ⋯, r_{k}} satisfies condition (A), then the box problem has a solution. Here N depends upon b_{1}, b_{2}, ⋯, 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

* Set stands for multiset. The b’s and r’r need not be distinct. the set b_{1}, b_{2}, ⋯, b_{k}. These smaller parallelopipeds are then obviously coverable by boxes of sides b_{1}, b_{2}, ⋯, b_{k}; hence the room is also.

Two lemmas, both well-known results, are required.

Lemma I. Let a_{1}, a_{2}, ⋯, a_{n} be any set of positive integers, and let δ be their greatest common divisor. Any sufficiently large integer which is divisible by δ may be expressed as a linear combination of a_{1}, a_{2}, ⋯, 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.

Lemma II. Given k objects, each of which possesses one or more of the attributes P_{1}, P_{2}, ⋯, 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}, ⋯, b_{k} by means of an index j, running from 1 to 2^{k} − 1. Let b_{j_{1}}, b_{j_{2}}, ⋯, b_{j_{m_{j}}} be the elements of the jth subset. Let δ_{j} be the greatest common divisor of b_{j_{1}}, b_{j_{2}}, ⋯, b_{j_{m_{j}}}. Condition (A) implies that δ_{j} divides at least m_{j} of the integers r_{1}, r_{2}, ⋯, r_{k}.

Suppose that j_{1}, j_{2}, ⋯, j_{α_{i}} are the indices of those greatest common divisors which divide r_{i}. Condition (A) gives α_{i} ≥ 1. Then we may write

(7)  r_{i} = ∑ A^{(i)}(j_{1}, l_{1}, j_{2}, l_{2}, ⋯, j_{α_{i}}, l_{α_{i}}),

where the summation extends over all possible sets of values of l_{1}, l_{2}, ⋯, l_{α_{i}} such that

1 ≤ l_{1} ≤ m_{j_{1}}, 1 ≤ l_{2} ≤ m_{j_{2}}, ⋯, 1 ≤ l_{α_{i}} ≤ m_{j_{α_{i}}} ,

and where the positive integer A^{(i)}(j_{1}, l_{1}, j_{2}, l_{2}, ⋯, j_{α_{i}}, l_{α_{i}}) is divisible by each of the integers b_{j_{1}l_{1}}, b_{j_{2}l_{2}}, ⋯, b_{j_{α_{i}} l_{α_{i}}}. This result follows at once from the fact that the positive integers form a distributive lattice under the operations ∩ = least common multiple and ∪ = 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 α_{i} δ’s dividing r_{i}. If we apply Lemma I, identifying the integers a_{1}, a_{2}, ⋯, a_{n} with these least common multiples, we see that the integers A^{(i)}(j_{1}, l_{1}, j_{2}, l_{2}, ⋯, j_{α_{i}}, l_{α_{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

(8)  A^{(1)}(j_{1}, l_{1}, j_{2}, l_{2}, ⋯, j_{α_{1}}, l_{α_{1}}) ⋯ A^{(k)}(j′_{1}, l′_{1}, j′_{2}, l′_{2}, ⋯, j′_{α_{k}}, l′_{α_{k}}).

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}, ⋯, b_{k}. We show that the hypothesis of Lemma II is fulfilled. Let δ_{j} be the greatest common divisor of some set of m_{j} b’s. Then δ_{j} will divide at least m_{j} of the positive integers r_{1}, r_{2}, ⋯, 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}, ⋯, b_{k} which will divide it. Thus this parallelopiped may be covered with boxes of sides b_{1}, b_{2}, ⋯, b_{k}. The larger room with sides r_{1}, r_{2}, ⋯, r_{k} may then also be so covered.

N. G. de Bruijn, in a problem published in the Hungarian journal, Mathematikai Lapok†, 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} ≤ b_{2} ≤ b_{3} ≤ ⋯ ≤ 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 × 1 × 1 × ⋯ × m. His method was similar to ours and may be extended to the more general case.

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}, ⋯, 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,

† 12 (1961) 110 Problem 109 and 13 (1962) 314 Problem 119 convergence difficulties present themselves, particularly if the configuration extends from −∞ to +∞ 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.

References

[1] Solomon W. Golomb, Checkerboards and polyominoes, American Mathematical Monthly, 61 (Dec. 1954) 675–682. Zbl. 57.1005.

[1*] Solomon W. Golomb, Polyominoes, New York: Scribners, 1965.

[2] Alfred Brauer and James E. Shockley, On a problem of Frobenius, Journal für die Reine und Angewandte Mathematik, 211 (1962) 215–220. Zbl. 108.4604.

[3] P. Hall, On representatives of subsets, Journal of the London Mathematical Society, 10 (part I) (1935) 26–30. Zbl. 10.34503.

[4*] Nicholas G. de Bruijn, Filling boxes with bricks, American Mathematical Monthly, 76 (Jan. 1969) 37–40. Zbl. 174.25501.

References indicated with a star are additions.