THE THREE DIMENSIONAL POLYOMINOES OF MINIMAL AREA

Laurent ALONSO^{∗}

CRIN-INRIA, Loria, BP239 54506 Vandœuvre–lès–Nancy France

     Laurent.Alonso@loria.fr

Raphaël CERF

CNRS, Université Paris Sud Mathématique, Bâtiment 425 91405 Orsay Cedex, France

                                 Raphael.Cerf@math.u-psud.fr

Submitted: December 21, 1995; Accepted: September 9, 1996

Abstract. The set of the three dimensional polyominoes of minimal area and of volume n contains a polyomino which is the union of a quasicube j × (j + δ) × (j + θ), δ, θ ∈ {0, 1}, a quasisquare l × (l + ϵ), ϵ ∈ {0, 1}, and a bar k. This shape is naturally associated to the unique decomposition of n = j(j +δ)(j +θ)+l(l+ϵ)+k as the sum of a maximal quasicube, a maximal quasisquare and a bar. For n a quasicube plus a quasisquare, or a quasicube minus one, the minimal polyominoes are reduced to these shapes. The minimal area is explicitly computed and yields a discrete isoperimetric inequality. These variational problems are the key for finding the path of escape from the metastable state for the three dimensional Ising model at very low temperatures. The results and proofs are illustrated by a lot of pictures.

1991 Mathematics Subject Classification. 05B50 51M25 82C44. Key words and phrases. polyominoes, minimal area, isoperimetry, Ising model. We thank an anonymous Referee for a very thorough reading and for many useful suggestions.

∗ L. Alonso is a Tetris expert.

Typeset by AMS-TEX

1. Introduction

Suppose we are given n unit cubes. What is the best way to set them out, in order to obtain a shape having the smallest possible area?

A little thinking suggests the following answer: first build the greatest cube you can, say j × j × j. Then complete one of its side, or even two, if you can, to obtain a quasicube j × (j + δ) × (j + θ), where δ, θ ∈ {0, 1}. With the remaining cubes, build the greatest quasisquare possible, l × (l + ϵ), ϵ ∈ {0, 1}, and put it on a side of the quasicube. With the last cubes, make a bar of length k < l + ϵ and stick it against the quasisquare.

Our first main result is that this method indeed yields a three dimensional polyomino of volume n and of minimal area, which is naturally associated to the unique decomposition of n = j(j +δ)(j +θ)+l(l +ϵ)+k as the sum of a maximal quasicube, a maximal quasisquare and a bar. We can compute easily the area of these shapes and we thus obtain a discrete isoperimetric inequality. However, the structure of the set of the minimal polyominoes having a fixed volume n depends heavily on n. Our second main result is that the set of the minimal polyominoes of volume n is reduced to the polyominoes obtained by the previous method if and only if n is a quasicube plus a quasisquare or a quasicube minus one.

A striking consequence of this result is that there exists an infinite sequence of minimal polyominoes, which is increasing for the inclusion. This fact is crucial for determining the path of escape from the metastable state for the three dimensional Ising model at very low temperatures [2,5]. The system nucleates from one phase to another by creating a droplet which grows through this sequence of minimal shapes. This question was our original motivation for solving the variational problems addressed here. The corresponding two–dimensional questions have already been handled [9,10,11]. In dimension three, we need a general large deviation framework [5,7] and the answer to precise global variational problems (like the previous ones), as well as to local ones: what are the best ways (as far as area is concerned) to grow or to shrink a parallelepiped?

Neves has obtained the first important results concerning the general d–dimensional case of this question in [8]^{†}. Using an induction on the dimension, he proves the d–dimensional discrete isoperimetric inequality from which he deduces the asymptotic behaviour of the relaxation time. However to obtain full information on the exit path one needs more refined variational statements which we do prove here (for instance uniqueness of the minimal shapes for specific values of the volume) together with a precise investigation of the energy landscape near these minimal shapes. The introduction of the projection operators is a key to reduce efficiently the polyominoes and to obtain the uniqueness results. Bollobás and Leader use similar compression operators to solve another isoperimetric problem [3]. The first part of the paper deals with the two dimensional case. The two dimensional results are indeed necessary to handle the three dimensional situation, which is the subject of the second part. We expect that similar results hold in any dimension.

†We thank R. Schonmann for pointing us to this reference.

2. The two dimensional case

We denote by (e_{1}, e_{2}) the canonical basis of the integer lattice ℤ^{2}. A unit square is a square of area one, whose center belongs to ℤ^{2} and whose vertices belong to the dual lattice (ℤ+1/2)^{2}. We do not distinguish between a unit square and its center: thus (x_{1}, x_{2}) denotes the unit square of center (x_{1}, x_{2}). A two dimensional polyomino is a finite union of unit squares. It is defined up to a translation. The set of all polyominoes is denoted by C. Notice that our definition does not require that a polyomino is connected. However, except for a few exceptions, we will deal with connected polyominoes. The area |c| of the polyomino c is the number of its unit squares. We denote by C_{n} the set of all the polyominoes of area n. The perimeter P (c) of a polyomino c is the number of unit edges of the dual lattice (ℤ + 1/2)^{2} which belong only to one of the unit squares of c. Notice that the perimeter is an even integer. For instance the perimeter of c in figure 2.1 is equal to 12 and its area is equal to 6.

figure 2.1: a 2D polyomino

Our aim is to investigate the set M_{n} of the polyominoes of C_{n} having a minimal perimeter. We say that a polyomino c has minimal perimeter (or simply is minimal) if it belongs to the set M_{|c|}.

Proposition 2.1. A polyomino c has minimal perimeter if and only if there does not exist a rectangle of area greater than or equal to |c| having a perimeter smaller than P (c).

Proof. The perimeter of a polyomino is greater than or equal to the perimeter of its smallest surrounding rectangle; there is equality if and only if the polyomino is convex. □

figure 2.2: the sets M_{1}, M_{2}, M_{3}, M_{4}

This characterization of minimal polyominoes gives a very little insight into the possible shapes of minimal polyominoes. Figure 2.2 shows the sets M_{n} for small values of n. Convex polyominoes have been enumerated according to their perimeter [6] and to their perimeter and area [4]. The perimeter and area generating function of convex polyominoes contains implicitly some information on the number of minimal polyominoes.

Let us introduce some notations related to polyominoes. For the sake of clarity, we need to work here with instances of the polyominoes having a definite position on the lattice ℤ^{2} i.e. we temporarily remove the indistinguishability modulo translations. Let c be a polyomino. By c(x_{1}, x_{2}) we denote the unique polyomino obtained by translating c in such a way that

min{ y_{1} : ∃y_{2} (y_{1}, y_{2}) ∈ c(x_{1}, x_{2}) } = x_{1},
min{ y_{2} : ∃y_{1} (y_{1}, y_{2}) ∈ c(x_{1}, x_{2}) } = x_{2}.

\begin{aligned}& c(0, 0) \\ c(−3, −3) \end{aligned}

figure 2.3: translation

When dealing with polyominoes up to translations, we normally work with the polyominoes c(0, 0), for any c in C.

The lengths and the bars. Let c be a polyomino. We define its horizontal and vertical lengths l_{1}(c) and l_{2}(c) by

l_{1}(c) = 1 + max{ x_{1} ∈ ℤ : ∃ x_{2} ∈ ℤ (x_{1}, x_{2}) ∈ c },
l_{2}(c) = 1 + max{ x_{2} ∈ ℤ : ∃ x_{1} ∈ ℤ (x_{1}, x_{2}) ∈ c }.

In particular, for a connected polyomino, l_{1}(c) = card { x_{1} ∈ ℤ : ∃ x_{2} ∈ ℤ (x_{1}, x_{2}) ∈ c }. We define the horizontal and vertical bars b_{1}(c, l) and b_{2}(c, l) for l in ℤ by

b_{1}(c, l) = { (x_{1}, x_{2}) ∈ c : x_{2} = l }, b_{2}(c, l) = { (x_{1}, x_{2}) ∈ c : x_{1} = l }.

The bars are one dimensional sections of the polyomino. An horizontal bar will also be called a row and a vertical bar a column. The extreme bars b_{1}^{∗}(c) and b_{2}^{∗}(c) are the bars associated with the lengths l_{2}(c) and l_{1}(c) i.e.

b_{1}^{∗}(c) = b_{1}(c, l_{2}(c) − 1), b_{2}^{∗}(c) = b_{2}(c, l_{1}(c) − 1).

b_{2}(c, 1)

figure 2.4: a bar

Addition of polyominoes. We define an operator +_{1} from C × C to C by ∀c, d ∈ C c +_{1} d = c(0, 0) ∪ d(l_{1}(c), 0).

c d c +_1 d

figure 2.5: operator +_{1}

Similarly the operator +_{2} : C × C → C is defined by c +_{2} d = c(0, 0) ∪ d(0, l_{2}(c)). More generally, for an integer i, we set

c +_{1}^{i} d = c(0, 0) ∪ d(l_{1}(c), i), c +_{2}^{i} d = c(0, 0) ∪ d(i, l_{2}(c)).

c d c +^2_1 d

figure 2.6: operator +_{1}^{i}

Sometimes we will use the operator + without specifying the direction: it will mean that the direction is in fact indifferent i.e. the statements hold for both operators +_{1} and +_{2}. Finally, we define two operators on C × C with values in P(C), the subsets of C, by c ⊕_{1} d = { c +_{1}^{i} d : l_{2}(d) + i ≤ l_{2}(c), i ≥ 0 }, c ⊕_{2} d = { c +_{2}^{i} d : l_{1}(d) + i ≤ l_{1}(c), i ≥ 0 }. Notice that c⊕_{1}d (respectively c⊕_{2}d) is empty whenever l_{2}(c) < l_{2}(d) (resp. l_{1}(c) < l_{1}(d)).

The basic polyominoes. We will concentrate mainly on particular simple shapes. Let us first consider the rectangles. The rectangle of horizontal length l_{1} and of vertical length l_{2} is denoted by l_{1} × l_{2}. A square is a rectangle l_{1} × l_{2} with l_{1} = l_{2}. A quasisquare is a rectangle l_{1} × l_{2} with |l_{1} − l_{2}| ≤ 1. The basic polyominoes are those obtained by adding a bar to a rectangle (the length of the bar being smaller than the length of the side of the rectangle on which it is added). More precisely the set B of basic polyominoes is

B = { l_{1} × l_{2} +_{1} 1 × k : 0 ≤ k < l_{2} } ∪ { l_{1} × l_{2} +_{2} k × 1 : 0 ≤ k < l_{1} }.

figure 2.7: basic polyominoes

When we add a bar k × 1 or 1 × k to a rectangle l_{1} × l_{2}, we will sometimes shorten the notation by writing only k, the direction of the bar being then parallel to the side of the rectangle on which it is added. For instance l_{1} × l_{2} +_{1} k will mean l_{1} × l_{2} +_{1} 1 × k. We are now ready to state the first main result of this section.

Theorem 2.2. For any n, the set M_{n} of the polyominoes of area n having a minimal perimeter contains a basic polyomino of the form

(l + ϵ) × l +_{2} k × 1 where ϵ ∈ {0, 1}, 0 ≤ k < l + ϵ, n = l(l + ϵ) + k.

Remark. Notice that this statement also says that any integer n may be decomposed as n = l(l + ϵ) + k, which is a purely arithmetical fact.

Proof. We choose an arbitrary polyomino c belonging to M_{n} (which is not empty!) and we apply to c a sequence of transformations in order to obtain a polyomino of the desired shape. The point is that the transformations never increase the perimeter of a polyomino nor change its area. Thus the perimeter remains constant during the whole sequence and the final polyomino still belongs to M_{n}. We first describe separately each transformation.

Projections p_{1} and p_{2}. The projections are defined for any polyomino. Let c be a polyomino. The vertical projection p_{2} consists in letting all the unit squares of c fall down vertically (along the direction of e_{2}, in the sense of −e_{2}) on a fixed horizontal line as shown on figure 2.8.

figure 2.8: vertical projection p_{2}

The horizontal projection p_{1} is defined in the same way, working with the vector e_{1}: we push horizontally all the unit squares towards the left against a fixed vertical line (see figure 2.9).

figure 2.9: horizontal projection p_{1}

Clearly, the projections do not change the area. They are projections in the sense that p_{1} ∘ p_{1} = p_{1}, p_{2} ∘ p_{2} = p_{2}. They never increase the perimeter. Consider for instance the vertical projection p_{2}. Focusing on two adjacent vertical bars, we see that the effect of the projection is to increase the number of vertical edges belonging simultaneously to both bars. Moreover, the projection p_{2} decreases the number of horizontal edges of a bar which belong to only one unit square: after projection, this number is equal to 2. The set F = p_{2} ∘ p_{1}(C) of all projected polyominoes is the set of Ferrers diagrams. Ferrers diagrams are convex polyominoes so that for c in F we have P (c) = 2(l_{1}(c) + l_{2}(c)).

Filling fill(2 → 1). These transformations are defined on the set F of Ferrers diagrams. Let c belong to F. The filling fill(2 → 1) proceeds as follows. While there remains a row below the top row (i.e. the extreme bar b_{1}^{∗}(c)) which is strictly shorter than the length of the base row (that is the l_{1}–length of c), we remove the rightmost unit square of the top row (i.e. the square (|b_{1}^{∗}(c)| − 1, l_{2}(c) − 1) and we put it into the leftmost empty cell of the lowest incomplete row. The mechanism ends whenever there is a full rectangle below the top row (see figure 2.10). More precisely, let l^{∗} = min{ l : l < l_{2}(c) : |b_{1}(c, l)| < l_{1}(c) }. If l^{∗} < l_{2}(c) − 1 we take the square (|b_{1}^{∗}(c)| − 1, l_{2}(c) − 1) and we put it at (|b_{1}(c, l^{∗})|, l^{∗}). We do this until l^{∗} equals l_{2}(c) − 1 (there is a rectangle below the top row) or l^{∗} is infinite (c is a rectangle).

figure 2.10: filling(2 → 1)

Clearly, the filling does not change the area and never increase the perimeter. It ends with a basic polyomino (the addition of a rectangle and a bar).

Dividing. The domain of dividing is the set V of the basic vertical polyominoes

V = { l_{1} × l_{2} +_{2} k × 1 : 0 ≤ k < l_{1} ≤ l_{2} }.

figure 2.11: dividing Let c = l_{1} × l_{2} +_{2} k × 1 with k < l_{1} ≤ l_{2} be an element of V. Let l_{2} − l_{1} = 2q + ϵ be the euclidean division of l_{2} − l_{1} by 2. The divided polyomino is then (see figure 2.11)

dividing(c) = (l_{1} × l_{1} +_{2} l_{1} × q +_{2} k × 1) +_{1} (q + ϵ) × l_{1}.

We check easily that the dividing does not change the area nor the perimeter. In fact, the rectangle surrounding dividing(c) is a quasisquare of perimeter 2(2l_{1} + 2q + ϵ + 1_{k≠0}) = 2(l_{1} + l_{2} + 1_{k≠0}) = P (c).

The sequence of transformations. The whole sequence of transformations is depicted in figure 2.12. Let us start with a polyomino c belonging to M_{n}. We first apply the projections p_{1} and p_{2}. Let d = p_{2} ∘ p_{1}(c). We consider two cases according whether d is ”vertical” or ”horizontal”. Let s_{Δ} be the symmetry with respect to the diagonal x_{1} = x_{2}.

• If l_{1}(d) ≤ l_{2}(d) we set e = d.

• If l_{1}(d) > l_{2}(d) we set e = s_{Δ}(d). Now we have l_{1}(e) ≤ l_{2}(e). Next we apply the filling fill(2 → 1) to e and we obtain a polyomino f. Since the perimeter cannot decrease, the polyomino f is necessarily a basic ”vertical” polyomino. Therefore we can apply the dividing to f. Let g = dividing(f). Finally let h = fill(2 → 1)(g). Since the perimeter has not decreased during this last filling, h is a basic ”vertical” polyomino. Because of the previous dividing operation, its associated rectangle is in fact a quasisquare. Thus h has the desired shape. □

cd e with l_{1}(e) ≤ l_{2}(e) fg h p_{2} ∘ p_{1} s_{Δ} or nothing filling(2 → 1) dividing filling(2 → 1)

figure 2.12: the sequence of transformations

c  d  e = fg h

figure 2.13: an example

Figure 2.13 shows the action of the sequence of transformations. Notice that the starting polyomino c is not minimal: it has been chosen so to emphasize the role of the projections.

Lemma 2.3. For each integer n there exists a unique 3–tuple (l, k, ϵ) such that

ϵ ∈ {0, 1}, 0 ≤ k < l + ϵ and n = l(l + ϵ) + k.

Proof. Fix a value of l. When ϵ and k vary in {0, 1}×{0 ⋯ l+ϵ−1} the quantity l(l+ϵ)+k takes exactly all the values in {l^{2} ⋯ (l+1)^{2}−1}. Thus the decomposition exists. Moreover l is unique, necessarily equal to ⌊\sqrt{n}⌋. We remark finally that k is the remainder of the euclidean division of n by l + ϵ. □

Corollary 2.4. The polyomino obtained at the end of the sequence of transformations does not depend on the polyomino initially chosen in the set M_{n}.

Throughout the section, the decomposition of an integer n given by lemma 2.3 will be called ”the decomposition” of the integer, without further detail. We can now easily compute the minimal perimeter.

Corollary 2.5. The minimal perimeter of a polyomino of area n is

min \{ P (c) : c ∈ C_{n} \} = \{ \begin{matrix}4l + 2 & if l^{2} + 1 ≤ n ≤ l(l + 1) \\ 4l + 4 & if l^{2} + l + 1 ≤ n ≤ (l + 1)^{2} \end{matrix}

where (l, k, ϵ) is the unique 3–tuple satisfying n = l(l + ϵ) + k, ϵ ∈ {0, 1}, k < l + ϵ.

The canonical, standard and principal polyominoes. Lemma 2.3 and corollary 2.4 allow us to define a canonical polyomino m_{n} belonging to M_{n}. Let n = l(l + ϵ) + k be the decomposition of n. We set

m_{n} = \{ \begin{matrix}l × l +_{1} 1 × k & if ϵ = 0 \\ (l + 1) × l +_{2} k × 1 & if ϵ = 1 \end{matrix}

This polyomino m_{n} is called the canonical polyomino of area n.

figure 2.14: the canonical polyominoes m_{28}, m_{23}

For c a polyomino, we denote by \overline{c} its equivalence class modulo the planar isometries which leave the integer lattice ℤ^{2} invariant, that is modulo the symmetries s_{Δ} (with respect to the diagonal Δ), s_{1} (with respect to the axis orthogonal to e_{1}), s_{2} (with respect to the axis perpendicular to e_{2}). By \overline{c}^{12} we denote the equivalence class modulo the two symmetries s_{1} and s_{2}. If A is a subset of C, we put

\overline{A} = ⋃_{c∈A} \overline{c}, \overline{A}^{12} = ⋃_{c∈A} \overline{c}^{12}.

The set S_{n} of the standard polyominoes is

S_{n} = \{ \begin{matrix}\overline{l × l ⊕_{1} 1 × k} & if ϵ = 0 \\ \overline{(l + 1) × l ⊕_{2} k × 1} & if ϵ = 1 \end{matrix}

The set M̃_{n} of the principal polyominoes is

M̃_{n} = \overline{l × (l + ϵ) ⊕_{1} 1 × k} ⋃ \overline{l × (l + ϵ) ⊕_{2} k × 1}.

The sets S_{n} and M̃_{n} coincide only when ϵ is zero. Clearly {m_{n}} ⊂ S_{n} ⊂ M̃_{n} ⊂ M_{n}. Figure 2.15 shows that the inclusions may be strict.

figure 2.15: elements of {m_{13}}, S_{13} \ {m_{13}}, M̃_{13} \ S_{13}, M_{13} \ M̃_{13}

In general, the set M_{n} is much larger than M̃_{n}. It turns out that it is not the case for specific values of n. This is the content of the second main result of this section.

Theorem 2.6. The set of minimal polyominoes M_{n} coincides with the set of principal polyominoes M̃_{n} if and only if the integer n is of the form l^{2} or l(l+1)−1, l(l+1), (l+1)^{2}−1.

Proof. First note that M_{n} = M̃_{n} implies that k ∈ {0, l + ϵ − 1}. If k ≠ 0, then the polyomino (l + ϵ − 1) × 1 +_{2}^{−1} (l + ϵ) × (l − 1) +_{2} (k + 1) × 1 belongs to M_{n}. Moreover if k ≠ l + ϵ − 1, this polyomino is not in the set M̃_{n}. Thus if M_{n} is equal to M̃_{n} then k = 0 or k = l + ϵ − 1 and the integer n is of the form l(l + ϵ) or l(l + ϵ) − 1.

figure 2.16: two elements of M_{23}

Conversely, we will examine for these particular values of n the possible actions of the sequence of transformations. That is, we will seek the antecedents of the final polyomino obtained at the end of the sequence. The main idea is that we started the sequence of transformations with a polyomino belonging to M_{n} so that the perimeter of the polyomino cannot change throughout the whole sequence.

• n = l^{2}. We have fill(2 → 1)^{−1}(l × l) ∩ M_{n} = { l × l } (if the filling has emptied a row to yield a square, there must have been a decrease of perimeter). Moreover,

dividing^{−1}(l × l) ∩ M_{n} = { l × l }, (p_{2}op_{1})^{−1}(l × l) ∩ M_{n} = { l × l }.

Thus M_{l^{2}} = { l × l }.

• n = l(l + 1) − 1 = l^{2} + l − 1. We have

fill(2 → 1)^{−1}(l × l +_{2} (l − 1) × 1) = { l × l +_{2} (l − 1) × 1 }
dividing^{−1}(l × l +_{2} (l − 1) × 1) = { l × l +_{2} (l − 1) × 1 },
s_{Δ}^{−1}(l × l +_{2} (l − 1) × 1) = { l × l +_{1} 1 × (l − 1) },

and also (p_{2}op_{1})^{−1}({ l × l +_{2} (l − 1) × 1, l × l +_{1} 1 × (l − 1) }) ∩ M_{n} = M̃_{l^{2}+l−1} so that finally M_{l(l+1)−1} = M̃_{l(l+1)−1}.

• n = l(l + 1). This case is similar to the previous one.

• n = (l + 1)^{2} − 1 = l(l + 1) + l. We have

fill(2 → 1)^{−1}(l × (l + 1) +_{2} l × 1) = { l × (l + 1) +_{2} l × 1 }
dividing^{−1}(l × (l + 1) +_{2} l × 1) = { l × (l + 1) +_{2} l × 1 },
(s_{Δ} ∘ p_{1} ∘ p_{2})^{−1}(l × (l + 1) +_{2} l × 1) = M̃_{(l+1)^{2}−1}.

We have thus checked that M_{n} = M̃_{n} for all these values of n. □

Corollary 2.7. The set M_{n} is reduced to { m_{n} } if and only if n is of the form l^{2}. The set M_{n} coincides with S_{n} if and only if n is of the form l^{2} or l(l + 1) − 1, l(l + 1), in which case S_{n} = \overline{m}_{n}.

Moves through the minimal polyominoes. We are interested in moving through the polyominoes by adding or removing one unit square at a time. How far is it possible to travel in this way through the minimal polyominoes? Let us define three matrices q, q_{−}, q_{+} indexed by C × C. First

∀c, d ∈ C q_{−}(c, d) = \{ \begin{matrix}1 & if d ⊂ c and |c \ d| = 1 \\ 0 & otherwise \end{matrix}

that is, q_{−}(c, d) = 1 if d may be obtained by removing a unit square from c, and q_{−}(c, d) = 0 otherwise. Next, we put q_{+}(c, d) = q_{−}(d, c), that is q_{+}(c, d) = 1 if d may be obtained by adding a unit square to c, and q_{+}(c, d) = 0 otherwise. Finally we set q(c, d) = q_{−}(c, d) + q_{+}(c, d) so that q(c, d) = 1 if the polyominoes differ by a unit square, and q(c, d) = 0 otherwise. Two polyominoes c, d are said to communicate if q(c, d) = 1. If Y is a subset of C and c is a polyomino, we set q(c, Y) = 1 if c communicates with at least one element of Y and q(c, Y) = 0 otherwise. The quantities q_{−}(c, Y), q_{+}(c, Y) are defined similarly.

Definition 2.8. A corner of a polyomino c is a unit square of c having at least two edges belonging to the boundary of c.

Proposition 2.9. Let l_{1}, l_{2} be two integers such that the rectangle l_{1} × l_{2} is minimal. Let l_{1}l_{2} = l(l + ϵ) + k be the decomposition of l_{1}l_{2}. Any polyomino obtained by removing successively m < k corners from l_{1} × l_{2} is minimal.

Proof. The removal of a corner cannot increase the perimeter of a polyomino. The perimeter of the canonical polyomino of area l_{1}l_{2} − m (with m < k) is 2(2l + ϵ) + 2 = 2(l_{1} + l_{2}), so that a polyomino obtained after the removal of m < k corners from l_{1} × l_{2} is minimal. □

Proposition 2.10. (characterization of the minimal polyominoes) A minimal polyomino is either a minimal rectangle or can be obtained by removing successively m corners from a minimal rectangle l_{1} × l_{2}, where m < k, l_{1}l_{2} = l(l + ϵ) + k.

Proof. The polyominoes of the above list are minimal by proposition 2.9. Conversely, let c belong to M_{n}. The smallest rectangle l_{1} ×l_{2} surrounding c is minimal (by proposition 2.1). Let l_{1}l_{2} = l(l+ϵ)+k be the decomposition of l_{1}l_{2}. Either n = l(l+ϵ) and c is a quasisquare or l(l+ϵ) < n ≤ l_{1}l_{2}, so that c can be obtained by removing m < k corners from l_{1} ×l_{2}. □

The next lemmas describe the way we can move starting from a canonical polyomino m_{n}.

Lemma 2.11. Let ι be a planar isometry. For any n not of the form l^{2} or l(l+1), ι(m_{n+1}) is the unique polyomino of M_{n+1} which communicates with ι(m_{n}).

Lemma 2.12. For n of the form l^{2} or l(l + 1), we have

{ c ∈ M_{n−1} : q_{−}(M_{n}, c) = 1 } = S_{n−1},
{ c ∈ M_{n+1} : q_{+}(M_{n}, c) = 1 } = M̃_{n+1}.

Lemma 2.13. For n not of the form l^{2} or l(l + 1), we have

{ c ∈ M_{n−1} : q_{−}(S_{n}, c) = 1 } ⊃ S_{n−1},
{ c ∈ M_{n+1} : q_{+}(S_{n}, c) = 1 } = S_{n+1},
{ c ∈ M_{n−1} : q_{−}(M̃_{n} \ S_{n}, c) = 1 } ⊃ M̃_{n−1} \ S_{n−1},
{ c ∈ M_{n+1} : q_{+}(M̃_{n} \ S_{n}, c) = 1 } = M̃_{n+1} \ S_{n+1}.

Lemma 2.14. The rectangle l × (l + 2) is minimal but cannot grow and stay minimal. More precisely, we have q_{+}(l × (l + 2), M_{l(l+2)+1}) = 0.

Proposition 2.15. Except the quasisquares, no rectangle can grow and stay minimal.

Proof. Let l_{1} × l_{2} = l_{1} × (l_{1} + r) be a minimal rectangle. Such a rectangle can grow and stay minimal if and only if the decomposition of l_{1} × l_{2} is l_{1}(l_{1} + r) = m(m + ϵ), and 2l_{1} + r = 2m + ϵ. Thus l_{1}^{2} + rl_{1} − m(m + ϵ) = 0. Solving this equation, we get 2l_{1} = −r + \sqrt{r^{2} + 4m(m + ϵ)} whence 2m + ϵ = \sqrt{(2m + ϵ)^{2} + r^{2} − ϵ^{2}}, implying finally r = 0 or r = 1. □

Definition 2.16. A sequence c_{n}, ⋯, c_{m} of polyominoes is increasing if q_{+}(c_{j}, c_{j+1}) = 1 for all j in {n ⋯ m − 1}.

Lemma 2.17. Suppose n = l(l+1). Let c belong to S_{n} and suppose there is an increasing sequence of minimal polyominoes c_{n}, ⋯, c_{m} such that c_{n} = c. Either c_{n+1} belongs to S_{n+1} or m is strictly less than (l + 1)^{2}; in the latter case, none of the polyominoes c_{n+1}, ⋯, c_{m} is standard, and they are all principal.

Proof. Suppose c_{n+1} is not standard i.e. c_{n+1} ∉ S_{n+1}. Thus, we have c_{n+1} = ι((l + 1) × l +_{1}^{i} 1 × 1) for some isometry ι and for some i, 0 ≤ i ≤ l − 1. Necessarily, for all k smaller than max(l−1, m−n), c_{n+k} = ι((l+1)×l)+_{1}^{i} 1×k for some i, 0 ≤ i ≤ l−k. None of these polyominoes is standard. Moreover lemma 2.14 implies that m ≤ n + l = (l + 1)^{2} − 1. □

We next state a straightforward consequence of lemma 2.17.

Corollary 2.18. Let c_{0}, ⋯, c_{n} be an increasing sequence of minimal polyominoes starting from the empty polyomino (c_{0} = ∅). If c_{n} is a standard polyomino (i.e. belongs to S_{n}) then all the polyominoes of the sequence are standard (i.e. c_{j} ∈ S_{j} for all j ≤ n).

We eventually sum up several facts of interest in the next propositions.

Proposition 2.19. The principal polyominoes can be completely shrunk through the principal polyominoes: for any integer n and for any principal polyomino c in M̃_{n}, there exists an increasing sequence c_{0}, ⋯, c_{n} of principal polyominoes such that c_{0} = ∅, c_{n} = c.

Proposition 2.20. The standard polyominoes can be grown or shrunk arbitrarily far through the standard polyominoes: for any integers m ≤ n and for any standard polyomino c in S_{m}, there exists an increasing sequence c_{0}, ⋯, c_{n} of standard polyominoes such that c_{0} = ∅, c_{m} = c.

Proposition 2.21. The infinite sequence S_{0}, ⋯, S_{n}, ⋯ of the sets of standard polyominoes is the greatest sequence of subsets of the infinite sequence M_{0}, ⋯, M_{n}, ⋯ of the sets of minimal polyominoes enjoying the properties stated in proposition 2.20.

Proof. Let S′_{0}, ⋯, S′_{n}, ⋯ be a sequence included in M_{0}, ⋯, M_{n}, ⋯ for which proposition 2.20 holds. Suppose there exists n such that S′_{n} ⊄ S_{n}. Let c belong to S′_{n} \ S_{n}. Let l_{1} × l_{2} be the smallest rectangle surrounding c. A growing sequence of minimal polyominoes starting from c necessarily reaches l_{1} × l_{2}. By proposition 2.15, this rectangle can grow and stay minimal if and only if it is a quasisquare. Thus l_{1} × l_{2} has to be a quasisquare. Suppose for instance l_{1} × l_{2} = l × (l + 1) (the other cases are similar). Since c can be obtained by growing the empty polyomino through minimal polyominoes, it contains necessarily the square l^{2} i.e. l^{2} ⊂ c ⊂ l(l + 1). It follows that c is standard. □

Shrinking or growing a rectangle. We finally investigate the following problem. What is the best way to shrink or to grow a rectangle? Let l_{1}, l_{2}, k be positive integers. We define

M(l_{1} × l_{2}, −k) = { c ∈ C_{l_{1}l_{2}−k} : c ⊂ l_{1} × l_{2}, P (c) minimal }.

More precisely, a polyomino c belongs to M(l_{1} × l_{2}, −k) if and only if

c ∈ C_{l_{1}l_{2}−k}, c ⊂ l_{1} × l_{2}, P (c) = min{ P (d) : d ∈ C_{l_{1}l_{2}−k}, d ⊂ l_{1} × l_{2} }.

Similarly, we define

M(l_{1} × l_{2}, k) = { c ∈ C_{l_{1}l_{2}+k} : l_{1} × l_{2} ⊂ c, P (c) minimal } ,

i.e. a polyomino c belongs to M(l_{1} × l_{2}, k) if and only if

c ∈ C_{l_{1}l_{2}+k}, l_{1} × l_{2} ⊂ c, P (c) = min{ P (d) : d ∈ C_{l_{1}l_{2}+k}, l_{1} × l_{2} ⊂ d }.

A natural way to remove (add) k squares (for k < l_{1}, k < l_{2}) is to remove (add) a bar on a side of the rectangle; thus we define

S(l_{1} × l_{2}, −k) = \overline{(l_{1} − 1) × l_{2} ⊕_{1} 1 × (l_{2} − k)}^{12} ⋃ \overline{l_{1} × (l_{2} − 1) ⊕_{2} (l_{1} − k) × 1}^{12} ,
S(l_{1} × l_{2}, k) = \overline{\{ l_{1} × l_{2} ⊕_{2} k × 1, l_{1} × l_{2} ⊕_{1} 1 × k \}}^{12}.

figure 2.17: the set M(6 × 4, −1)

Figure 2.17 shows the set M(6 × 4, −1). Figure 2.18 shows the set M(5 × 5, −2) which contains the set S_{23}. In these cases, we see that M(6 × 4, −1) = S(6 × 4, −1) but this does not occur in general : for instance M(5 × 5, −2) ⊋ S(5 × 5, −2).

figure 2.18: the set M(5 × 5, −2) ⊋ S_{23}

Proposition 2.22. Let l_{1}, l_{2}, k be positive integers such that k < l_{1}, k < l_{2}. The set M(l_{1} × l_{2}, −k) is the set of the polyominoes obtained by removing successively k corners from l_{1} × l_{2}. In particular, S(l_{1} × l_{2}, −k) is included in M(l_{1} × l_{2}, −k).

Proof. Such an operation leaves the perimeter unchanged. Moreover, the perimeter of a polyomino of M(l_{1} × l_{2}, −k) is necessarily 2(l_{1} + l_{2}) since there remains at least one square in each row and each column of the rectangle after the removal of k squares. □

Proposition 2.23. Let l_{1}, l_{2}, k be positive integers such that k < l_{1}, k < l_{2}. The set M(l_{1} × l_{2}, k) is equal to the set S(l_{1} × l_{2}, k).

Proof. The perimeter of a polyomino of M(l_{1}×l_{2}, k) is greater than or equal to 2(l_{1}+l_{2})+2 (since it contains l_{1} × l_{2}). The polyominoes of S(l_{1} × l_{2}, k) have this perimeter, so that the minimal perimeter is exactly 2(l_{1} + l_{2}) + 2 and S(l_{1} × l_{2}, k) ⊂ M(l_{1} × l_{2}, k). Obviously, the polyominoes of S(l_{1} × l_{2}, k) are the only ones satisfying the requirements. □

3. The three dimensional case

We denote by (e_{1}, e_{2}, e_{3}) the canonical basis of the integer lattice ℤ^{3}. A unit cube is a cube of volume one, whose center belongs to ℤ^{3} and whose vertices belong to the dual lattice (ℤ + 1/2)^{3}. We do not distinguish between a unit cube and its center: thus (x_{1}, x_{2}, x_{3}) denotes the unit cube of center (x_{1}, x_{2}, x_{3}). A three dimensional polyomino is a finite union of unit cubes. It is defined up to a translation. We denote by C_{n} the set of the polyominoes of volume n and by C the set of all polyominoes. The area A(c) of a polyomino c is the number of two dimensional unit squares belonging to the boundary of only one unit cube of c. Notice that the area is an even integer.

figure 3.1: a 3D polyomino

We wish to investigate the set M_{n} of the polyominoes of C_{n} having a minimal area. A polyomino c is said to be minimal if it belongs to the set M_{|c|}. Figure 3.2 shows elements of the sets M_{n} for small values of n.

figure 3.2: the sets M_{1}, ⋯, M_{8}

When n becomes larger, the structure of M_{n} becomes very complex:

figure 3.3: some elements of M_{30}

For the sake of clarity, we need to work here with instances of the polyominoes having a definite position on the lattice ℤ^{3} i.e. we temporarily remove the indistinguishability modulo translations. Let c be a polyomino. By c(x_{1}, x_{2}, x_{3}) we denote the unique polyomino obtained by translating c in such a way that

min{ y_{1} : ∃ (y_{2}, y_{3}) (y_{1}, y_{2}, y_{3}) ∈ c(x_{1}, x_{2}, x_{3}) } = x_{1},
min{ y_{2} : ∃ (y_{1}, y_{3}) (y_{1}, y_{2}, y_{3}) ∈ c(x_{1}, x_{2}, x_{3}) } = x_{2},
min{ y_{3} : ∃ (y_{1}, y_{2}) (y_{1}, y_{2}, y_{3}) ∈ c(x_{1}, x_{2}, x_{3}) } = x_{3}.

When we deal with polyominoes up to translations, we normally work with the polyominoes c(0, 0, 0), for any c in C.

The lengths, the bars and the slices. Let c be a polyomino. We define its lengths j_{1}(c), j_{2}(c), j_{3}(c) along each axis by

j_{1}(c) = 1 + max{ x_{1} ∈ ℤ : ∃ (x_{2}, x_{3}) (x_{1}, x_{2}, x_{3}) ∈ c },
j_{2}(c) = 1 + max{ x_{2} ∈ ℤ : ∃ (x_{1}, x_{3}) (x_{1}, x_{2}, x_{3}) ∈ c },
j_{3}(c) = 1 + max{ x_{3} ∈ ℤ : ∃ (x_{1}, x_{2}) (x_{1}, x_{2}, x_{3}) ∈ c }.

For a connected polyomino, we have j_{1}(c) = card { x_{1} ∈ ℤ : ∃ (x_{2}, x_{3}) (x_{1}, x_{2}, x_{3}) ∈ c }. A three dimensional polyomino is said to be planar with normal vector e_{i} if its j_{i}–length is equal to one. Such a polyomino might effectively be seen as a two dimensional polyomino by transforming its unit cubes into unit squares (and keeping the orientation induced in the plane by the vector e_{i}). Conversely, given a vector e_{i} of the basis, we may see any two dimensional polyomino as a planar three dimensional polyomino with normal vector e_{i}. We simply transform the unit squares into unit cubes and rotate the polyomino so that its normal vector becomes e_{i}. This trick will be used several times in the sequel. Let α, β be two integers. We define the bars b_{1}(c, α, β), b_{2}(c, α, β), b_{3}(c, α, β) by

b_{1}(c, α, β) = { (x_{1}, x_{2}, x_{3}) ∈ c : (x_{2}, x_{3}) = (α, β) },
b_{2}(c, α, β) = { (x_{1}, x_{2}, x_{3}) ∈ c : (x_{1}, x_{3}) = (α, β) },
b_{3}(c, α, β) = { (x_{1}, x_{2}, x_{3}) ∈ c : (x_{1}, x_{2}) = (α, β) }.

Let γ be an integer. We define the slices s_{1}(c, γ), s_{2}(c, γ), s_{3}(c, γ) by

s_{1}(c, γ) = { (x_{1}, x_{2}, x_{3}) ∈ c : x_{1} = γ },
s_{2}(c, γ) = { (x_{1}, x_{2}, x_{3}) ∈ c : x_{2} = γ },
s_{3}(c, γ) = { (x_{1}, x_{2}, x_{3}) ∈ c : x_{3} = γ }.

e_{1}  e_{3} e_{2}
figure 3.4: the bar b_{1}(c, 2, 7) and the slice s_{2}(c, 4)

The bars (respectively the slices) are one (resp. two) dimensional sections of the polyomino. The extreme slices s_{1}^{∗}(c), s_{2}^{∗}(c), s_{3}^{∗}(c) are the slices associated to the lengths j_{1}(c), j_{2}(c), j_{3}(c)

s_{1}^{∗}(c) = s_{1}(c, j_{1}(c) − 1), s_{2}^{∗}(c) = s_{2}(c, j_{2}(c) − 1), s_{3}^{∗}(c) = s_{3}(c, j_{3}(c) − 1).

Addition of polyominoes. We define an operator +_{1} from C × (C ∪ C) to C (we recall that C is the set of two dimensional polyominoes). First, on C × C, we set

∀c, d ∈ C c +_{1} d = c(0, 0, 0) ∪ d(j_{1}(c), 0, 0).

Let now c belong to C and d belong to C (that is, d is a two dimensional polyomino). We define the three dimensional polyomino c+_{1}d as follows. First, we transform d into a planar three dimensional polyomino d′ by replacing its squares by unit cubes. We rotate d′ so that its normal unit vector becomes e_{1} (as if the two dimensional polyomino d was initially included in the plane (e_{2}, e_{3})). Then we use the previous definition to set c +_{1} d = c +_{1} d′. The operators +_{2} and +_{3} from C ×(C ∪C) to C are defined similarly. For instance, on C ×C, we set c +_{2} d = c(0, 0, 0) ∪ d(0, j_{2}(c), 0) and c +_{3} d = c(0, 0, 0) ∪ d(0, 0, j_{3}(c)). More generally, given two integers α and β, we put for c, d in C

c +_{1} (α, β) d = c(0, 0, 0) ∪ d(j_{1}(c), α, β),
c +_{2} (α, β) d = c(0, 0, 0) ∪ d(α, j_{2}(c), β),
c +_{3} (α, β) d = c(0, 0, 0) ∪ d(α, β, j_{3}(c)).

In the case d is a two dimensional polyomino, c +_{i} (α, β) d is defined analogously, working with the translated polyomino d(α, β) (this is a translation into the plane containing d). Sometimes we will use the operator + without specifying the direction: it will mean that this direction is in fact indifferent i.e. the statements hold for +_{1}, +_{2}, +_{3} simultaneously. Finally we define three operators ⊕_{1}, ⊕_{2}, ⊕_{3} from C × (C ∪ C) to P(C), the set of subsets of C, by

c ⊕_{1} d = { c +_{1} (α, β) d : j_{2}(d) + α ≤ j_{2}(c), j_{3}(d) + β ≤ j_{3}(c), α ≥ 0, β ≥ 0 },
c ⊕_{2} d = { c +_{2} (α, β) d : j_{1}(d) + α ≤ j_{1}(c), j_{3}(d) + β ≤ j_{3}(c), α ≥ 0, β ≥ 0 },
c ⊕_{3} d = { c +_{3} (α, β) d : j_{1}(d) + α ≤ j_{1}(c), j_{2}(d) + β ≤ j_{2}(c), α ≥ 0, β ≥ 0 }.

Notice that c ⊕_{1} d (respectively c ⊕_{2} d, c ⊕_{3} d) is empty whenever j_{2}(d) > j_{2}(c) or j_{3}(d) > j_{3}(c) (resp. j_{1}(d) > j_{1}(c) or j_{3}(d) > j_{3}(c), j_{1}(d) > j_{1}(c) or j_{2}(d) > j_{2}(c)).

The basic polyominoes. We describe here some simple shapes of polyominoes of particular interest. Let j_{1}, j_{2}, j_{3} be three integers. By j_{1} ×j_{2} ×j_{3} we denote the parallelepiped whose lengths (with respect to the axis e_{1}, e_{2}, e_{3}) are j_{1}, j_{2}, j_{3}. A parallelepiped j_{1} ×j_{2} ×j_{3} is a cube if j_{1} = j_{2} = j_{3}. It is a quasicube if |j_{1} − j_{2}| ≤ 1, |j_{2} − j_{3}| ≤ 1, |j_{3} − j_{1}| ≤ 1. Thus the quasicubes are the parallelepipeds (j + ϵ_{1}) × (j + ϵ_{2}) × (j + ϵ_{3}) where the ϵ_{i}’s belong to {0, 1}. The basic three dimensional polyominoes are the polyominoes obtained by adding a two dimensional basic polyomino (i.e. an element of B) to a parallelepiped. More precisely, the set B of the basic polyominoes is

B = { j_{1} × j_{2} × j_{3} +_{1} d : d ∈ B, d ⊂ j_{2} × j_{3} } ∪ { j_{1} × j_{2} × j_{3} +_{2} d : d ∈ B, d ⊂ j_{1} × j_{3} } ∪ { j_{1} × j_{2} × j_{3} +_{3} d : d ∈ B, d ⊂ j_{1} × j_{2} }.

(where B is the set of two dimensional basic polyominoes). We are now in position to state the first main result concerning the three dimensional minimal polyominoes.

Theorem 3.1. For any integer n, the set M_{n} of the minimal polyominoes of volume n contains a basic polyomino of the form j × (j + δ) × (j + θ) +_{3} (l × (l + ϵ) +_{2} k) (i.e. the addition of a quasicube, a quasisquare and a bar) where ϵ, δ, θ ∈ {0, 1}, 0 ≤ k < l + ϵ, l(l + ϵ) + k < (j + δ)(j + θ), n = j(j + δ)(j + θ) + l(l + ϵ) + k.

Remark. This statement asserts also the existence of a decomposition of any integer n as n = j(j + δ)(j + θ) + l(l + ϵ) + k where j, l, k, δ, θ, ϵ satisfy the above conditions.

Remark. The corresponding generalization in any dimension has been proved by Neves [8]. However, our method of proof will allow us to get quite easily the corresponding uniqueness statement (theorem 3.5 below).

Proof. The proof is done in the same spirit as the corresponding two dimensional proof. We choose a polyomino belonging to M_{n} and we apply to it a sequence of transformations which regularize the shape of the polyomino until we get a polyomino of the desired form. These transformations leave the volume unchanged and never increase the area, so that the area is constant during the whole process and the final polyomino is still in M_{n}. We first describe separately each transformation.

Projections p_{1}, p_{2}, p_{3}. These transformations are defined on the set C of all the polyominoes. Let c belong to C. The projection p_{3} consists in letting all the unit cubes of c fall (in the sense of −e_{3}) on a fixed plane orthogonal to e_{3}, as shown on figure 3.5.

figure 3.5: projection p_{3}

The projections p_{1} and p_{2} are defined similarly, using the vectors e_{1} and e_{2} instead of e_{3}. The projections satisfy p_{i} ∘p_{i} = p_{i}, 1 ≤ i ≤ 3. Moreover they do not change the volume nor increase the area. A formal proof would rely on a tedious induction and would consist in counting the number of cubes in contact before and after the projections. It is obvious that the number of horizontal contacts is maximal after application of p_{3}. Moreover the number of vertical contacts between two adjacent columns is also maximal after application of p_{3}. The set G = p_{3} ∘ p_{2} ∘ p_{1}(C) of all projected polyominoes is the set of plane partitions [1].

Slice–remodelling (sli-rem). This transformation is applied to a polyomino belonging to the set G of plane partitions. Let c belong to G. We cut c into slices according to the direction of e_{3} i.e. we consider all its intersections with the planes of equations x_{3} = γ, which are the slices s_{3}(c, γ). Such a slice s_{3}(c, γ) may be seen as a two dimensional polyomino of area |s_{3}(c, γ)| (we simply transform the unit cubes of s_{3}(c, γ) into unit squares). We then replace s_{3}(c, γ) by the associated two dimensional canonical polyomino m_{|s_{3}(c,γ)|} (in which all the unit squares have been transformed into unit cubes), the orientation being specified by (e_{1}, e_{2}). We finally stack up all these new slices i.e. we build the polyomino sli–rem(c) = m_{|s_{3}(c,0)|} +_{3} m_{|s_{3}(c,1)|} +_{3} ⋯ +_{3} m_{|s_{3}^{∗}(c)|}.

figure 3.6: slice–remodelling

The slice–remodelling does not change the volume nor increase the area. In fact, the number of horizontal contacts between two slices is maximal (equal to the number of cubes of the smallest slice) if the two slices are associated to two dimensional canonical polyominoes. Moreover the image of sli–rem is included in G = p_{3} ∘ p_{2} ∘ p_{1}(C).

Cube–moving. This transformation moves individually cubes of the polyomino. Let c belong to G. Let (x_{1}, x_{2}, x_{3}) be the empty cell of smallest coordinate for the (e_{3}, e_{1}, e_{2}) lexicographical order such that there are three cubes at (x_{1} − 1, x_{2}, x_{3}), (x_{1}, x_{2} − 1, x_{3}), (x_{1}, x_{2}, x_{3} − 1). The cell (x_{1}, x_{2}, x_{3}) is the cell where a cube of c will be moved. In case x_{3} = j_{3}(c) − 1 the cube–moving does nothing. Suppose x_{3} < j_{3}(c) − 1. We now define the unit cube of c which is to be moved. We consider the extremal section s_{3}^{∗}(c) as a two dimensional polyomino. As such, it is a Ferrers diagram i.e. it belongs to the set F (see the two dimensional projections). The extreme bars b_{1}^{∗}(s_{3}^{∗}(c)) and b_{2}^{∗}(s_{3}^{∗}(c)) are well defined as well as the lengths l_{1}(s_{3}^{∗}(c)), l_{2}(s_{3}^{∗}(c)). We omit c and s_{3}^{∗}(c) in these notations and write b_{1}^{∗}, b_{2}^{∗}, l_{1}, l_{2} in the following lines. Several cases arise according to the lengths of these bars.

• If |b_{1}^{∗}| < |b_{2}^{∗}| we move (|b_{1}^{∗}| − 1, l_{2} − 1, j_{3} − 1).

• If |b_{1}^{∗}| > |b_{2}^{∗}| we move (l_{1} − 1, |b_{2}^{∗}| − 1, j_{3} − 1).

• If |b_{1}^{∗}| = |b_{2}^{∗}| and l_{1} ≤ l_{2} we move (|b_{2}^{∗}| − 1, l_{2} − 1, j_{3} − 1).

• If |b_{1}^{∗}| = |b_{2}^{∗}| and l_{1} > l_{2} we move (l_{1} − 1, |b_{1}^{∗}| − 1, j_{3} − 1). We repeat this elementary operation until exhaustion of any possibility (that is, until the smallest empty cell belongs to the extreme slice s_{3}^{∗}). The procedure necessarily ends since the number of available empty cells below the extreme slice s_{3}^{∗} decreases.

figure 3.7: cube–moving

The cube–moving does not change the volume nor increase the area.

Example. Suppose we apply the cube–moving to a polyomino c belonging to sli–rem(G): thus each two dimensional section s_{3}(c, γ) of c is a canonical two dimensional polyomino. Putting n(x_{3}) = |s_{3}(c, x_{3})| we have n(0) ≥ ⋯ ≥ n(j_{3}(c) − 1). In this situation, the elementary cube–moving operation amounts to take the only cube belonging to s_{3}^{∗}(c) so that s_{3}^{∗}(c) becomes m_{n(j_{3}(c)−1)−1} and to put it at the smallest empty cell (x_{1}, x_{2}, x_{3}) such that there are three cubes at (x_{1} − 1, x_{2}, x_{3}), (x_{1}, x_{2} − 1, x_{3}), (x_{1}, x_{2}, x_{3} − 1). Notice that the section s_{3}(c, x_{3}) = m_{n(x_{3})} then becomes m_{n(x_{3})+1} so that the polyomino still belongs to sli–rem(G). When the cube–moving ends, we obtain a polyomino such that

∃ r ≥ 0, n(0) = ⋯ = n(r), ∀i, r < i < j_{3} − 1, n(i) is a quasisquare,

and all the slices along e_{3} are two dimensional canonical polyominoes. Figure 3.8 shows the typical shape of the polyominoes we obtain after having completed the cube–moving.

figure 3.8: after cube–moving

Bar–moving. The bar–moving transformation is defined on the set cube–moving(G). This transformation moves bars of the polyomino. Let c belong to cube–moving(G). The bar to be moved is one of the two extreme bars b_{1}^{∗} or b_{2}^{∗} of the extreme slice s_{3}^{∗}. We first define the bar b which is to be moved.

• if |b_{1}^{∗}| < |b_{2}^{∗}| we choose b = b_{1}^{∗}.

• if |b_{1}^{∗}| > |b_{2}^{∗}| we choose b = b_{2}^{∗}.

• if |b_{1}^{∗}| = |b_{2}^{∗}| and l_{1} ≤ l_{2} we choose b = b_{2}^{∗}.

• if |b_{1}^{∗}| = |b_{2}^{∗}| and l_{1} > l_{2} we choose b = b_{1}^{∗}. Notice that the cube chosen to start the cube–moving operation would belong to this bar b. We next search for an appropriate place to move b. Let b′_{1} be the smallest empty bar b_{1}(c, x_{2}, x_{3}) for the (e_{3}, e_{2}) lexicographical order such that the two bars b_{1}(c, x_{2} −1, x_{3}) and b_{1}(c, x_{2}, x_{3} − 1) have a length greater than or equal to the length of the bar b. We define b′_{2} similarly, using the vectors (e_{3}, e_{1}). We define b′_{3} using the vectors (e_{1}, e_{2}) (thus b′_{3} is a vertical bar) and we impose the additional condition that |b′_{3}| is strictly less than j_{3}(c). Notice that these bars might not exist. If none of these bars exist, the bar–moving does nothing. If only the bar b′_{3} exists we move b to b′_{3}. If only one bar among b′_{1}, b′_{2} exists, we move b to this bar. Suppose finally that both bars b′_{1} and b′_{2} do exist. Let x_{3}(b′_{1}), x_{3}(b′_{2}) be the e_{3}–coordinate of the bars b′_{1}, b′_{2} (the bars b′_{1}, b′_{2} are one dimensional sections of c along the vectors e_{1} and e_{2}). Several cases arise according to these coordinates and, in case of equality, according to the lengths of the s_{3}–section of c.

• If x_{3}(b′_{1}) < x_{3}(b′_{2}) we move b to b′_{1}.

• If x_{3}(b′_{1}) > x_{3}(b′_{2}) we move b to b′_{2}.

• If x_{3}(b′_{1}) = x_{3}(b′_{2}) and l_{1}(s_{3}(c, x_{3})) < l_{2}(s_{3}(c, x_{3})) we move b to b′_{1}.

• If x_{3}(b′_{1}) = x_{3}(b′_{2}) and l_{1}(s_{3}(c, x_{3})) ≥ l_{2}(s_{3}(c, x_{3})) we move b to b′_{2}.

figure 3.9: bar–moving

The choices of the empty bar and of the bar which is moved are done in such a way that bar–moving∘cube–moving∘sli–rem(G) is included in sli–rem(G). As usual, the bar–moving does not alter the volume nor increase the area.

Filling. The transformation filling(e_{3}) is the application, until exhaustion of any possibility, of the transformation bar–moving ∘ cube–moving. Thus it is applied to polyominoes belonging to the set G. The transformations filling(e_{1}) and filling(e_{2}) are defined in the same way: we just make a circular permutation of the axis so that e_{1} or e_{2} becomes the third vector of the basis and we apply the same scheme. When filling(e_{3}) is completed, we obtain a polyomino of the form j_{1} × j_{2} × j_{3} +_{1} c +_{2} d +_{3} e where e is a two dimensional polyomino of F and c, d are either empty or they are rectangles such that no bar–moving operation can take place. In case the starting polyomino belongs to sli–rem(G), we obtain a polyomino of the form (j + ϵ) × j × j_{3} +_{2} d +_{3} e where e is a two dimensional canonical polyomino, and d is a rectangle such that no bar–moving from e is possible.

figure 3.10: filling(e_{3})

Trividing. This transformation is defined for a polyomino c of the form c = (j + ϵ) × j × j_{3} ⊕_{3} d where ϵ ∈ {0, 1}, j_{3} > j +ϵ, and d is a non empty two dimensional polyomino which is included in the quasisquare (j +ϵ)×j (d might be equal to (j +ϵ)×j). We decompose j_{3} as j_{3} = j +ϵ+3a+δ +θ where δ, θ are in {0, 1} and δ ≤ θ. This decomposition is obviously unique.

figure 3.11: trividing

The trivided polyomino trivided(c) is then

(j + ϵ) × j × (j + ϵ) +_{1} (a + ϵ′) × j × (j + ϵ) +_{2} (j + ϵ) × (a + ϵ′′) × j +_{3} (j + ϵ) × j × a +_{3} d where (ϵ′, ϵ′′) = (θ, δ) if ϵ = 0 and (ϵ′, ϵ′′) = (δ, θ) if ϵ = 1. Considering separately each case, we have:

• If ϵ = 0, trivided(c) = j × j × j +_{1} (a + θ) × j × j +_{2} j × (a + δ) × j +_{3} j × j × a +_{3} d.

• If ϵ = 1, trivided(c) = (j + 1) × j × (j + 1) +_{1} (a + δ) × j × (j + 1) +_{2} (j + 1) × (a + θ) × j +_{3} (j + 1) × j × a +_{3} d. Once more, the trividing does not alter the volume and does not increase the area.

Swivelling. The swivelling is defined for a polyomino c of the form c = j_{1} × j_{2} × j_{3} +_{i} d where 1 ≤ i ≤ 3 and d is a two dimensional polyomino which is included in the rectangle j_{1}× j_{2}. The aim of the swivelling is to move d on the side j_{1} × j_{2} of the parallelepiped. Thus swivelling(c) = j_{1} × j_{2} × j_{3} +_{3} d.

figure 3.12: swivelling

The sequence of transformations. We start with a polyomino c of M_{n}. We first apply the three projections p_{1}, p_{2}, p_{3}. Let c_{1} = p_{3} ∘ p_{2} ∘ p_{1}(c). We next apply a rotation to c_{1} to obtain a polyomino c_{2} such that j_{3}(c_{2}) ≥ j_{1}(c_{2}) and j_{3}(c_{2}) ≥ j_{2}(c_{2}). We next apply the slice–remodelling and get a polyomino c_{3}. We then apply the filling filling(e_{3}) and obtain a polyomino c_{4} of the form c_{4} = (j + ϵ) × j × j_{3} +_{2} d +_{3} e. If d is empty, we set c_{5} = c_{4}. If not, we apply the filling filling(e_{2}), obtaining a polyomino c′_{4} = (j + ϵ) × j × (j_{3} + 1) +_{2} d′ where d′ is included in the quasisquare (j + ϵ) × j (if the result of the filling was different, the area would necessarily have decreased) and we then set c_{5} = swivelling(c′_{4}). In both cases, we have now a polyomino c_{5} of the form c_{5} = (j + ϵ) × j × j_{3} +_{3} e. We replace e by the corresponding two dimensional canonical polyomino m_{|e|}, obtaining a polyomino c_{6} (this amounts to apply the slice–remodelling). We apply the trividing to c_{6} and obtain c_{7} = trividing(c_{6}). We end the sequence by a filling filling(e_{3}): c_{8} = filling(e_{3})(c_{7}). We claim that c_{8} has the desired shape. □

c c_{1} c_{2} with j_{3}(c_{2}) ≥ max(j_{1}(c_{2}), j_{2}(c_{2})) c_{3} c_{4} = (j + ϵ) × j × j_{3} +_{2} d +_{3} e c′_{4} c_{5} = (j + ϵ) × j × j_{3} +_{3} e c_{6} c_{7} c_{8} d = ∅ nothing  p_{3} ∘ p_{2} ∘ p_{1} rotation slice–remodelling filling(e_{3}) d ≠ ∅, fill(e_{2}) swivelling slice–remodelling trividing filling(e_{3})

figure 3.13: the sequence of transformations

rotation  sli–rem trividing fill(e_{3})

p_{2}  p_{3} ∘ p_{1}  fill(e_{3}) swivel  fill(e_{2})

figure 3.14: two examples Lemma 3.2. For each integer n there exists a unique 6–tuple (j, l, k, δ, θ, ϵ) such that δ, θ, ϵ ∈ {0, 1}, δ ≤ θ, k < l+ϵ, l(l+ϵ)+k < (j+δ)(j+θ) and n = j(j+δ)(j+θ)+l(l+ϵ)+k.

Corollary 3.3. The polyomino obtained at the end of the sequence of transformations does not depend on the polyomino initially chosen in the set M_{n}.

Throughout the sequel, we will refer to this decomposition as ”the decomposition” of the integer n, without further detail. We thus have a method for computing the minimal area of a polyomino of volume n.

Corollary 3.4. The minimal area of a polyomino of volume n is

min { A(c) : c ∈ C_{n} } = 2(j(j + δ) + j(j + θ) + (j + δ)(j + θ)) + 2(2l + ϵ) + 2×1_{{k>0}}

where n = j(j + δ)(j + θ) + l(l + ϵ) + k is the decomposition of n given by lemma 3.2.

The canonical, standard and principal polyominoes. Lemma 3.2 and corollary 3.3 allow us to define a canonical polyomino 𝔪_{n} belonging to M_{n}. Let n = j(j +δ)(j +θ)+l(l+ϵ)+k be the decomposition of n. We put r = l(l+ϵ)+k. The canonical polyomino 𝔪_{n} is obtained by adding the two dimensional canonical polyomino m_{r} to the right side of a right quasicube of volume j(j + δ)(j + θ).

• If δ = θ = 0 we set 𝔪_{n} = j × j × j +_{1} m_{r}.

• If δ = 0, θ = 1 we set 𝔪_{n} = (j + 1) × j × j +_{2} m_{r}.

• If δ = θ = 1 we set 𝔪_{n} = (j + 1) × (j + 1) × j +_{3} m_{r}.

figure 3.15: the canonical polyominoes 𝔪_{194}, 𝔪_{230}, 𝔪_{266}

We may give a general formula:

𝔪_{n} = (j + θ) × (j + δ) × j +_{1+δ+θ} ((l + ϵ) × l +_{1+ϵ} k).

The polyomino 𝔪_{n} is called the canonical polyomino of volume n. For c a polyomino, we denote by \overline{c} its equivalence class modulo the spatial isometries which leave the integer lattice ℤ^{3} invariant. By \overline{c}^{123} we denote the equivalence class modulo the three symmetries s_{1}, s_{2}, s_{3} with respect to the planes (e_{2}, e_{3}), (e_{1}, e_{3}), (e_{1}, e_{2}). If A is a subset of C, we put

\overline{A} = ⋃_{c∈A} \overline{c}, \overline{A}^{123} = ⋃_{c∈A} \overline{c}^{123}.

the electronic journal of combinatorics 3 (1996), #R27 32

The set S_{n} of the standard polyominoes is

S_{n} = \overline{(j + θ) × (j + δ) × j ⊕_{1+δ+θ} \overline{(l + ϵ) × l ⊕_{1+ϵ} k}}

and the set M̃_{n} of the principal polyominoes is

M̃_{n} = ⋃_{{t=1,2,3 \atop u=1,2}} \overline{(j + θ) × (j + δ) × j ⊕_{t} \overline{(l + ϵ) × l ⊕_{u} k}}

figure 3.16: polyominoes in {𝔪_{112}}, S_{112} \ {𝔪_{112}}.

figure 3.17: polyominoes in M̃_{112} \ S_{112}, M_{112} \ M̃_{112}.

The sets S_{n} and M̃_{n} coincide if δ = θ = ϵ = 0. Moreover we have

{𝔪_{n}} ⊂ S_{n} ⊂ M̃_{n} ⊂ M_{n}.

However, the inclusions might be strict, as shown by the examples of figures 3.16, 3.17.

Theorem 3.5. The set M_{n} of minimal polyominoes of volume n coincides with the set M̃_{n} of principal polyominoes if and only if n is of the form quasicube+quasisquare

\begin{matrix}j^{3} & j^{3} + l^{2} & j^{3} + l(l + 1) \\ j^{2}(j + 1) & j^{2}(j + 1) + l^{2} & j^{2}(j + 1) + l(l + 1) \\ j(j + 1)^{2} & j(j + 1)^{2} + l^{2} & j(j + 1)^{2} + l(l + 1) \end{matrix}

(where 1 ≤ l < j) or quasicube minus one j^{3} − 1, j^{2}(j + 1) − 1, j(j + 1)^{2} − 1.

Proof. Suppose first that M_{n} is equal to M̃_{n}. This means that, modulo spatial isometries and moves of the two dimensional polyomino l × (l + ϵ) + k on one side of the quasicube j × (j + δ) × (j + θ), or moves of the bar k × 1 along one side of the quasisquare l × (l + ϵ) the set M_{n} is reduced to the six polyominoes

\begin{matrix}(j + θ) × (j + δ) × j +_{1} (l + ϵ) × l +_{1} k , & (j + θ) × (j + δ) × j +_{1} (l + ϵ) × l +_{2} k \\ (j + θ) × (j + δ) × j +_{2} (l + ϵ) × l +_{1} k , & (j + θ) × (j + δ) × j +_{2} (l + ϵ) × l +_{2} k \\ (j + θ) × (j + δ) × j +_{3} (l + ϵ) × l +_{1} k , & (j + θ) × (j + δ) × j +_{3} (l + ϵ) × l +_{2} k \end{matrix}

(which are isometric when δ = θ = ϵ = 0). The corresponding two dimensional result implies that k = 0 or k = l + ϵ − 1. For k = 0 we obtain the quasicubes plus the quasisquares. Suppose k = l + ϵ − 1. If (l + ϵ)(l + 1) is not equal to (j + θ)(j + δ), then the polyomino ((j + θ − 1) × (j + δ) +_{1} (j + δ − 1)) +_{3} (j + θ) × (j + δ) × (j − 1) +_{3} (l + ϵ) × (l + 1) belongs to the set M_{n} and is not principal. Thus (l+ϵ)(l+1) necessarily equals (j+θ)(j+δ) so that n = (j + θ)(j + δ)(j + 1) − 1 is a quasicube minus one.

figure 3.18: an element of M_{195}

Conversely, we examine for these particular values of n the possible actions of the sequence of transformations. That is, we seek the antecedents of the final polyomino obtained at the end of the sequence of transformations. The main idea is that we started the sequence of transformations with a polyomino belonging to M_{n} so that the area of the polyomino cannot change throughout the whole sequence. We first notice that for all these shapes the last filling fill(e_{3}) between c_{7} and c_{8} had necessarily no effect. When n is of the form j^{3} or j^{3} + l^{2}, j^{3} + l(l + 1), the transformation between c_{6} and c_{7} was also effectless; when n is of the form j^{2}(j + 1) or j^{2}(j + 1) + l^{2}, j^{2}(j + 1) + l(l + 1) or j(j + 1)^{2}, j(j + 1)^{2} + l^{2}, j(j + 1)^{2} +l(l+1), the trividing could have swivelled l^{2}, l(l+1) from one face to another, yielding a principal polyomino of M̃_{n}. Moreover, for all these values of n, we have

∀i ∈ {1, 2, 3} fill(e_{i})^{−1}(M̃_{n}) ∩ M_{n} = M̃_{n}

i.e. the antecedents of a principal polyomino through a filling operation which are minimal are also principal. Finally we check that the same is true for the slice–remodelling: its only possible effect when the final shape is principal is to have swivelled or rotated l×l or l×(l+1) from one face to another, or to have applied an isometry to the cube j^{3},j^{2}(j + 1),j(j + 1)^{2}. The same kind of results hold concerning the first two transformations i.e. the projections between c and c_{1} and the rotation between c_{1} and c_{2}. Putting these facts together, we see that for the values of n listed in the theorem, the sets of the minimal antecedents through the sequence of transformations of the canonical polyomino coincides with the set of principal polyominoes. □

As a by–product, we obtain the following results.

Corollary 3.6. The set M_{n} is reduced to {𝔪_{n}} if and only if n is of the form j^{3}. The set M_{n} is equal to S_{n} if and only if n is of the form j^{3} or j^{2}(j + 1), j(j + 1)^{2} or j^{3} − 1, j^{2}(j + 1) − 1, j(j + 1)^{2} − 1 (in which case S_{n} = \overline{𝔪}_{n}), or j^{3} + l^{2}, j^{3} + l(l + 1).

We were not able to prove or disprove results characterizing the three dimensional minimal polyominoes, comparable to propositions 2.1 and 2.10. We propose two conjectures instead.

Conjecture 3.7. If a polyomino is minimal then its smallest surrounding parallelepiped is also minimal.

Definition 3.8. A corner of a polyomino c is a unit cube of c having at least three sides belonging to the boundary of c.

Conjecture 3.9. All the minimal polyominoes can be obtained by removing successively m corners from a minimal parallelepiped j_{1} × j_{2} × j_{3}, in such a way that the number of bars removed from the parallelepiped is maximal, where m < l(l + ϵ) + k, j_{1}j_{2}j_{3} = j(j + δ)(j + θ) + l(l + ϵ) + k.

Moves through the minimal polyominoes. We are interested in moving through the polyominoes by adding or removing one unit cube at a time. How far is it possible to travel in this way through the minimal polyominoes? Let us define three matrices q, q_{−}, q_{+} indexed by C × C. First

∀c, d ∈ C q_{−}(c, d) = \{ \begin{matrix}1 & if d ⊂ c and |c \ d| = 1 \\ 0 & otherwise \end{matrix}

that is, q_{−}(c, d) = 1 if d may be obtained by removing a unit cube from c, and q_{−}(c, d) = 0 otherwise. Next, we put q_{+}(c, d) = q_{−}(d, c), that is q_{+}(c, d) = 1 if d may be obtained by adding a unit cube to c and q_{+}(c, d) = 0 otherwise. Finally we set q(c, d) = q_{−}(c, d) + q_{+}(c, d) so that q(c, d) = 1 if the polyominoes differ by a unit cube, and q(c, d) = 0 otherwise. Two polyominoes c, d are said to communicate if q(c, d) = 1. If Y is a subset of C and c is a polyomino, we set q(c, Y) = 1 if c communicates with at least one element of Y and q(c, Y) = 0 otherwise. The quantities q_{−}(c, Y), q_{+}(c, Y) are defined similarly. The next lemmas describe the way we can move starting from a canonical polyomino 𝔪_{n}.

Lemma 3.10. Let ι be a spatial isometry. For any n which is not a quasicube plus a quasisquare, that is not of the form

j^{3} + l^{2} or j^{3} + l(l + 1), j^{2}(j + 1) + l^{2}, j^{2}(j + 1) + l(l + 1), j(j + 1)^{2} + l^{2}, j(j + 1)^{2} + l(l + 1)

(where l < j), ι(𝔪_{n+1}) is the unique polyomino of M_{n+1} which communicates with ι(𝔪_{n}).

Lemma 3.11. For n a quasicube i.e. of the form j^{3} or j^{2}(j + 1), j(j + 1)^{2}, we have

{ c ∈ M_{n−1} : q_{−}(M_{n}, c) = 1 } = S_{n−1},
{ c ∈ M_{n+1} : q_{+}(M_{n}, c) = 1 } = M̃_{n+1}.

Lemma 3.12. For n a quasicube plus a quasisquare i.e. of the form j(j +δ)(j +θ)+l(l+ϵ) (where 0 < l(l + ϵ) < (j + δ)(j + θ)) we have

{ c ∈ M_{n−1} : q_{−}(M̃_{n} \ S_{n}, c) = 1 } ⊃ M̃_{n−1} \ S_{n−1},
{ c ∈ M_{n−1} : q_{−}(S_{n}, c) = 1 } ⊃ S_{n−1},
{ c ∈ M_{n+1} : q_{+}(M_{n}, c) = 1 } = M̃_{n+1}.

Lemma 3.13. For the remaining integers i.e. the values of n which are not a quasicube or a quasicube plus a quasisquare we have

{ c ∈ M_{n−1} : q_{−}(S_{n}, c) = 1 } ⊃ S_{n−1},
{ c ∈ M_{n+1} : q_{+}(S_{n}, c) = 1 } = S_{n+1},
{ c ∈ M_{n−1} : q_{−}(M̃_{n} \ S_{n}, c) = 1 } ⊃ M̃_{n−1} \ S_{n−1},
{ c ∈ M_{n+1} : q_{+}(M̃_{n} \ S_{n}, c) = 1 } = M̃_{n+1} \ S_{n+1}.

Lemma 3.14. Suppose that j × (j + δ) × (j + θ) + l × (l + r), r ≥ 2 is minimal. It cannot be grown through the minimal polyominoes.

Lemma 3.15. The parallelepipeds j ×j ×(j +2), j ×(j +1)×(j +2) cannot grow through the minimal polyominoes.

Lemma 3.16. Suppose n is not of the form j^{2}(j + 1) or j(j + 1)^{2}, j^{3} + l(l + 1), j^{2}(j + 1) + l(l + 1), j(j + 1)^{2} + l(l + 1). Then

{ c ∈ M_{n+1} : q(S_{n}, c) = 1 } = S_{n+1},
{ c ∈ M_{n+1} : q_{+}(M̃_{n} \ S_{n}, c) = 1 } = M̃_{n+1} \ S_{n+1}.

Definition 3.17. A sequence c_{n}, ⋯, c_{m} of polyominoes is increasing if q_{+}(c_{j}, c_{j+1}) = 1 for all j in {n ⋯ m − 1}.

Lemma 3.18. Suppose n is of the form j^{3}+l(l+1) or j^{2}(j+1)+l(l+1), j(j+1)^{2}+l(l+1) (where 0 < l < j). Let c belong to S_{n} and suppose there is an increasing sequence of minimal polyominoes c_{n}, ⋯, c_{m} such that c_{n} = c. Either c_{n+1} belongs to S_{n+1} or m is less than n + l; in this last case, none of the polyominoes c_{n+1}, ⋯, c_{m} is standard, and they are all principal.

Lemma 3.19. Suppose n is a quasicube of the form j^{2}(j + 1) (respectively j(j + 1)^{2}). Let c belong to S_{n} and suppose there is an increasing sequence of minimal polyominoes c_{n}, ⋯, c_{m} such that c_{n} = c. Either c_{n+1} belongs to S_{n+1} or m is less than n + j^{2} (resp. n + j(j + 1)); in this last case, none of the polyominoes c_{n+1}, ⋯, c_{m} is standard, and they are all principal.

The next propositions sum up several results which are consequences of the preceding lemmas together with theorem 3.1 and corollary 3.6.

Proposition 3.20. Let n be an integer between the two cubes j^{3}, (j + 1)^{3} and let c be a principal polyomino belonging to M̃_{n} which is not standard i.e. it does not belong to S_{n}. Suppose there exists an increasing sequence of minimal polyominoes c_{n}, ⋯, c_{m} such that c_{n} = c. Then necessarily m < (j + 1)^{3} and none of the polyominoes c_{n}, ⋯, c_{m} is standard.

Proposition 3.21. Let c_{0}, ⋯, c_{n} be an increasing sequence of minimal polyominoes starting from the empty polyomino (c_{0} = ∅). If c_{n} is a standard polyomino (i.e. belongs to S_{n}) then all the polyominoes of the sequence are standard (i.e. c_{j} ∈ S_{j} for all j ≤ n).

Proposition 3.22. The principal polyominoes can be completely shrunk through the principal polyominoes: for any integer n and for any principal polyomino c in M̃_{n}, there exists an increasing sequence c_{0}, ⋯, c_{n} of principal polyominoes such that c_{0} = ∅, c_{n} = c.

Proposition 3.23. The standard polyominoes can be grown or shrunk arbitrarily far through the standard polyominoes: for any integers m ≤ n and for any standard polyomino c in S_{m}, there exists an increasing sequence c_{0}, ⋯, c_{n} of standard polyominoes such that c_{0} = ∅, c_{m} = c.

Proposition 3.24. The infinite sequence S_{0}, ⋯, S_{n}, ⋯ of the sets of standard polyominoes is the greatest infinite sequence of subsets of the sequence M_{0}, ⋯, M_{n}, ⋯ of the sets of minimal polyominoes enjoying the properties stated in proposition 3.23.

Proof. Let S′_{0}, ⋯, S′_{n}, ⋯ be a sequence included in M_{0}, ⋯, M_{n}, ⋯ for which proposition 3.23 holds. Suppose there exists n such that S′_{n} ⊄ S_{n}. Let n be the smallest such index and let c belong to S′_{n} \ S_{n}. There exists d in S′_{n−1} ⊂ S_{n−1} such that q_{+}(d, c) = 1. Hence c is principal. Several cases arise: if n = j(j + δ)(j + θ) + l(l + 1) + k (with (l, k) ≠ (0, 0)), the corresponding two dimensional proposition 2.21 together with lemma 3.18 imply the result; if n = j(j + δ)(j + θ), we have necessarily (δ, θ) ≠ (0, 0) (otherwise c would be standard) and lemma 3.19 shows that c cannot be grown indefinitely through the minimal polyominoes. □

Shrinking or growing a parallelepiped. We investigate next the best way to shrink or to grow a parallelepiped plus a rectangle. Let c be either a parallelepiped or a parallelepiped plus a rectangle and let k be a positive integer. We define

M(c, −k) = { d ∈ C_{|c|−k} : d ⊂ c, A(d) minimal } ,

i.e. a polyomino d belongs to M(c, −k) if and only if

d ∈ C_{|c|−k}, d ⊂ c, A(d) = min{ A(d′) : d′ ∈ C_{|c|−k}, d′ ⊂ c }.

Similarly, we define

M(c, k) = { d ∈ C_{|c|+k} : c ⊂ d, A(d) minimal } ,

i.e. a polyomino d belongs to M(c, k) if and only if

d ∈ C_{|c|+k}, c ⊂ d, A(d) = min{ A(d′) : d′ ∈ C_{|c|+k}, c ⊂ d′ }.

A natural way to remove (add) r cubes (for r < j_{1}j_{2}, r < j_{2}j_{3}, r < j_{1}j_{3}) is to remove (add) the cubes on only one side of the parallelepiped.

Proposition 3.25. Let j_{1}, j_{2}, j_{3}, r be positive integers such that r < j_{1}j_{2}, r < j_{2}j_{3}, r < j_{3}j_{1}. The set M(j_{1} × j_{2} × j_{3}, −r) is the set of the polyominoes obtained by removing from j_{1} × j_{2} × j_{3} as many bars as possible, and then removing a succession of corners (see definition 3.8) until reaching the volume j_{1}j_{2}j_{3} − r.

Corollary 3.26. Let j_{1}, j_{2}, j_{3}, r be positive integers such that r < j_{1}j_{2}, r < j_{2}j_{3}, r < j_{3}j_{1}. A polyomino obtained from j_{1} × j_{2} × j_{3} by the successive removal of r cubes, in such a way that each cube removal takes place on a bar of minimal length of the polyomino is in the set M(j_{1} × j_{2} × j_{3}, −r).

Corollary 3.27. Suppose j_{1} × j_{2} is the side of j_{1} × j_{2} × j_{3} of smallest area. If j_{1}j_{2} − r ≤ j_{1}^{2} and r ≤ j_{1}j_{2}, then j_{1} × j_{2} × (j_{3} − 1) ⊕ m_{j_{1}j_{2}−r} ⊂ M(j_{1} × j_{2} × j_{3}, −r). If j_{1}j_{2} − r > j_{1}^{2}, then j_{1} × j_{2} × (j_{3} − 1) ⊕ (j_{1} × q + s) ⊂ M(j_{1} × j_{2} × j_{3}, −r), where j_{1}j_{2} − r = j_{1}q + s, 0 ≤ s < j_{1}.

Proposition 3.28. Let j_{1}, j_{2}, j_{3}, r be positive integers such that r ≤ min(j_{1}^{2}, j_{2}^{2}, j_{3}^{2}). The best way to add r cubes to the parallelepiped j_{1}×j_{2}×j_{3} is to add a minimal two dimensional polyomino of M_{r} on one side of the parallelepiped. Equivalently, we have

M(j_{1} × j_{2} × j_{3}, r) = \overline{\{ j_{1} × j_{2} × j_{3} ⊕_{i} d, 1 ≤ i ≤ 3, d ∈ M_{r} \}}^{123}.

In particular, j_{1} × j_{2} × j_{3} ⊕ m_{r} ⊂ M(j_{1} × j_{2} × j_{3}, r).

Proof. Let c belong to M(j_{1} × j_{2} × j_{3}, r). Let d be the polyomino obtained by removing from c the slices s_{1}(c, j), j ≥ j_{1}(c) or j < 0. Let c_{1} be a two dimensional polyomino formed by the union of all these slices laid out in ℤ^{2} in such a way that no two of them intersect. We have A(c) ≥ A(d) + P (c_{1}) (here P is the two dimensional perimeter). Let e be the polyomino obtained by removing from d all the slices s_{2}(d, j), j ≥ j_{2}(c) or j < 0. Let c_{2} be a two dimensional polyomino formed by the union of all these slices laid out in ℤ^{2} in such a way that no two of them intersect. We have A(d) ≥ A(e)+P (c_{2}). Removing all the slices s_{3}(e, j), j ≥ j_{3}(c) or j < 0 from e, we obtain the parallelepiped j_{1} × j_{2} × j_{3}. Let c_{3} be a two dimensional polyomino formed by the disjoint union of all these slices. Clearly, A(e) ≥ A(j_{1} × j_{2} × j_{3}) + P (c_{3}). We have A(c) ≥ A(j_{1} × j_{2} × j_{3}) + P (c_{1}) + P (c_{2}) + P (c_{3}). It follows that A(c) ≥ A(j_{1} × j_{2} × j_{3}) + P (c_{4}) where c_{4} is a polyomino which is the disjoint union of c_{1}, c_{2}, c_{3}. Yet c_{4} has area r, so that P (c_{4}) ≥ P (m_{r}); since A(j_{1} × j_{2} × j_{3} ⊕ m_{r}) = A(j_{1} × j_{2} × j_{3}) + P (m_{r}) we see that the area of an element of M(j_{1} × j_{2} × j_{3}, r) is exactly A(j_{1} × j_{2} × j_{3}) + P (m_{r}); in particular c_{4} must be a minimal two dimensional polyomino: thus c_{4} belongs to M_{r} and c is necessarily in

\overline{\{ j_{1} × j_{2} × j_{3} ⊕_{i} d, 1 ≤ i ≤ 3, d ∈ M_{r} \}}^{123}.

Conversely, this set is clearly included in M(j_{1} × j_{2} × j_{3}, r). □

We finally state the results describing the best ways of growing and shrinking a parallelepiped plus a rectangle. Let j_{1}, j_{2}, j_{3}, l_{1}, l_{2}, r be integers. We consider a polyomino c of the set j_{1} × j_{2} × j_{3} ⊕ l_{1} × l_{2}. We suppose that the rectangle is added on a compatible side of the parallelepiped (i.e. l_{1} × l_{2} is included in this side). We suppose also that r < min(l_{1}, l_{2}) ≤ min(j_{1}, j_{2}, j_{3}). As before, we let

M(c, −r) = { d ∈ C_{|c|−r} : d ⊂ c, A(d) minimal },
M(c, r) = { d ∈ C_{|c|+r} : c ⊂ d, A(d) minimal }.

Proposition 3.29. The set M(c, −r) is the set of the polyominoes obtained by removing successively r corners from c. The set M(c, r) is equal to the set of the polyominoes obtained by adding a bar of length r against a compatible side of the rectangle l_{1} × l_{2} (in such a way that l_{1} × l_{2} ⊕ r fits into the side of the parallelepiped).

References

1. G.E. Andrews, The theory of partitions, Encyclopedia of Mathematics and its Applications, Addison– Wesley, 1976.

2. G. Ben Arous and R. Cerf, Metastability of the three dimensional Ising model on a torus at very low temperatures, Electronic Journal of Probability 1 (1996), 1–55.

3. B. Bollobás and I. Leader, Compressions and isoperimetric inequalities, J. Combinatorial Theory Series A 56 (1991), 47–62.

4. M. Bousquet–Mélou and J.M. Fédou, The generating function of convex polyominoes: the resolution of a q–differential system, Discrete Math. 137 (1995), 53–75.

5. O. Catoni and R. Cerf, The exit path of a Markov chain with rare transitions, ESAIM: Probabilités et Statistique (1996) (to appear).

6. M.–P. Delest and G. Viennot, Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci. 34 (1984), 169–206.

7. M.I. Freidlin and A.D. Wentzell, Random perturbations of dynamical systems, Springer–Verlag, New York, 1984.

8. E.J. Neves, A discrete variational problem related to Ising droplets at low temperatures, Jour. Stat. Phys. 80 nos 1/2 (1995), 103–123.

9. E.J. Neves and R.H. Schonmann, Critical droplets and metastability for a Glauber dynamics at very low temperatures, Commun. Math. Phys. 137 (1991), 209–230.

10. E.J. Neves and R.H. Schonmann, Behaviour of droplets for a class of Glauber dynamics at very low temperatures, Prob. Th. Related Fields 91 (1992), 331–354.

11. R.H. Schonmann, The pattern of escape from metastability of a stochastic Ising model, Commun. Math. Phys 147 (1992), 231–240.

L. Alonso, CRIN-INRIA, Loria, BP239, 54506 Vandœuvre–lès–Nancy, France R. Cerf, Université Paris Sud, Mathématique, Bâtiment 425, 91405 Orsay Cedex–France E-mail address: Laurent.Alonso@loria.fr – Raphael.Cerf@math.u-psud.fr