Tiling a rectangle with the fewest squares.

Richard Kenyon^{∗}

Abstract We show that a square-tiling of a p × q rectangle, where p and q are relatively prime integers, has at least log_{2} p squares. If q > p we construct a square-tiling with less than q/p+C log p squares of integer size, for some universal constant C.

1 Introduction

A certain store sells square tiles of arbitrary positive integer size for $1 each. You’d like to tile your kitchen (a p × q rectangle, p, q ∈ ℤ_{+}), for the least cost. What’s the cheapest way?

We show:

Theorem 1 A p×q rectangle, where p, q are relatively prime integers, p < q, requires at least max{q/p, log_{2} q} square tiles to tile. Furthermore there exists a square tiling with less than q/p + C_{1} log_{2} p squares of integer size, for some universal constant C_{1}.

Remark. For the lower bound the sizes of the squares are not restricted to be integers. Also, the quantity q/p in the two bounds is necessary for thin rectangles; for example an n × 1 rectangle requires at least n squares. If q/p is bounded then we have logarithmic upper and lower bounds.

Here for a p × q rectangle we call the aspect ratio the larger of p/q, q/p. In case the aspect ratio x > 1 of the kitchen is not rational, no tiling with

a finite number of squares is possible by a theorem of Dehn [5]; on the other hand, using squares of arbitrary real size, if you have a refrigerator to cover up the untiled portion, you can do equally well:

∗CNRS UMR 128, Ecole Normale Supérieure de Lyon, 46, allée d’Italie, 69364 Lyon, France. Research at MSRI supported in part by NSF grant no. DMS-9022140.

Theorem 2 For any ϵ > 0 and x ∈ ℝ, x > 1, one can tile all but an ϵneighborhood of a corner of an x×1 rectangle with ≤ x+C_{2} log(1/ϵ) squares, for some universal constant C_{2}.

Our proof of the lower bound in Theorem 1 uses the theory of electrical networks, which has a well-known connection with square tilings [5, 3, 2]. In particular a generalization of Theorem 1 is as follows:

Theorem 3 Let X be a resistor network with underlying graph G, with resistances 1 on each edge. If the effective resistance between two vertices is the rational number \frac{q}{p} > 1 in lowest terms, then there are at least max\{q/p, log_{2} q\} edges in G. Conversely, for any rational \frac{q}{p} > 1 there is such a network with a planar graph having at most \frac{q}{p} + C_{1} log_{2} p edges.

Here we allow multiple edges between the same vertices in the graph G.

2 The greedy algorithm

Your initial reaction is of course to tile using the greedy algorithm, that is, select the largest square that fits (a p × p tile), place it touching a shortest side of the kitchen, and repeat with the remaining untiled part, which is now p × (q − p).

This method, also known as the Euclidean algorithm, works well for certain shapes of rectangle, for example those rectangles which are F_{n}×F_{n+1}, where F_{n} is the nth Fibonacci number. Indeed such a rectangle is tiled with n ≈ log_{τ} F_{n} tiles (Figure 1).

Unfortunately for many shapes of rectangles, this algorithm is quite expensive: for a p × (p + 1) rectangle, the first square leaves a p × 1 rectangle, which requires at least p squares to tile, for a total cost of 1 + p, which much more expensive than is necessary.

We leave the reader to verify that, if the continued fraction expansion of q/p is [a_{0}; a_{1}, …, a_{k}], that is,

\frac{q}{p} = a_{0} + \frac{1}{a_{1} + _{\frac{1}{a_{2}+...+ \frac{1}{a_{k}}}}} ,

Figure 1: Tiling Fibonacci’s kitchen.

then the cost of the greedy algorithm on a p×q rectangle is a_{0} +a_{1} +…+a_{k}. (Here the integers a_{i} are called partial quotients of q/p: it is required that a_{0} ≥ 0 and for i ≥ 1 that a_{i} ≥ 1. Under these conditions the a_{i} are uniquely defined except for a_{k}, and we have [a_{0}; a_{1}, …, a_{k}] = [a_{0}; a_{1}, …, a_{k} − 1, 1] assuming a_{k} > 1.)

For the irrational rectangle x × 1, if x = [a_{0}; a_{1}, a_{2}, …] is the infinite continued fraction expansion of x, then the cost T_{ϵ}(x) to cover up all but the ϵ-neighborhood of the corner is

T_{ϵ}(x) = a_{0} + a_{1} + … + a_{k},  (1)

where the k is the first number to satisfy

|x − \frac{p_{k}}{q_{k}} | < \frac{ϵ}{q_{k}} ,

where p_{k}/q_{k} = [a_{0}; a_{1}, a_{2}, …, a_{k}] is the kth rational approximant to x. Indeed, if the untiled portion after a_{0} + … + a_{k} steps is x′ × y′, then we have

( \begin{matrix}1 & −1 \\ 0 & 1 \end{matrix} )^{a_{k}} … ( \begin{matrix}1 & 0 \\ −1 & 1 \end{matrix} )^{a_{1}} ( \begin{matrix}1 & −1 \\ 0 & 1 \end{matrix} )^{a_{0}} ( \begin{matrix}x \\ 1 \end{matrix} ) = ( \begin{matrix}x′ \\ y′ \end{matrix} ) ,

or in other words

( \begin{matrix}p_{k} & p_{k±1} \\ q_{k} & q_{k±1} \end{matrix} ) ( \begin{matrix}x′ \\ y′ \end{matrix} ) = ( \begin{matrix}x \\ 1 \end{matrix} ) .

(Here the ± depends on the parity of k.) If y′ < ϵ then

ϵ > y′ = −q_{k}x + p_{k}.

Quantities related to this cost T_{ϵ}(x) for “typical” numbers have been studied in detail. Yuval Peres combined some known results to prove:

Theorem 4 (Peres) There is a constant c′ > 0 such that for any δ > 0 the Lebesgue measure of the set

\{x ∈ (0, 1) : |\frac{T_{ϵ}(x)}{log(1/ϵ) log log(1/ϵ)} − c′| ≥ δ\}

tends to zero with ϵ.

For the proof, see the appendix.

If x = [a_{0}; a_{1}, a_{2}, …] is irrational and all the a_{i} are bounded by n, then x is called n-aloof. It is not hard to see (we’ll see later in any case) that if x is n-aloof, the greedy algorithm gives a logarithmic bound T_{ϵ}(x) < const log(\frac{1}{ϵ}), where the constant depends on n.

3 The lower bound.

We give here a proof of the lower bound in Theorem 1. First, the largest square which can fit is a p × p square, which covers p/q of the area, so you need at least q/p squares to tile. We will show that you need at least log_{2} q squares to tile.

To a square tiling of a rectangle R, associate a graph G as follows [3]: let G = (V, E) be the graph with vertex set V and edges E, where V is the set of connected components of the union of the horizontal boundaries of tiles in the square-tiling, and E is the set of tiles (note that a tile connects exactly two horizontal components, and that multiple edges between two vertices are possible). The vertex corresponding to the upper boundary of R is called a, and the vertex corresponding to the lower boundary is b. It is clear that G is planar, and that a and b are on the same face (the outer face) of G.

It is helpful to direct the edges from the upper vertex to the lower vertex. Associated to G is the resistor network, obtained by assigning each edge

of G a resistance 1. By assigning potentials p_{a}, p_{b} ∈ ℝ to the vertices a and b of the network, a flow of electric current is set up in G, that is, we have maps p: V → ℝ (“potentials”) and c: E → ℝ (“currents”) which satisfy Kirchoff’s rule and Ohm’s law: the net current flow out of any vertex (except a and b) is equal to the net flow into that vertex, and the current across an edge equals the drop in potential between its endpoints. (By definition the current has a sign which depends on the direction of the edge.) The potentials and currents are the unique solution to the equations arising from Kirchoff’s and Ohm’s rules with the given boundary conditions p(a) = p_{a}, p(b) = p_{b}. If we denote by c_{b} the net current going into b, then the quantity r(a, b) = (p_{a} − p_{b})/c_{b} depends only on the graph and is independent of p_{a}, p_{b}. This quantity r(a, b) is called the effective resistance, or impedance, from a to b.

If we scale the square tiling by a homothety of ℝ^{2} and translate it so that the upper boundary is at y-coordinate p_{a} and the lower boundary is at y-coordinate p_{b} (assuming with loss of generality that p_{a} > p_{b}), then we see that a solution (hence the unique solution) of Kirchoff’s and Ohm’s equations is given by: for v ∈ V, p(v) equals the y-coordinate of the horizontal component corresponding to v, and for e ∈ E, c(e) is the size of the square tile corresponding to e. The quantity r(a, b) is simply the ratio of height to width of the rectangle.

This construction also works in the other direction. We can associate, to any planar graph G = (V, E) and choice of two vertices a, b ∈ V on the same face, a square-tiling of a rectangle R whose resistor network is G. This is proved in [3], who simply use the idea of the previous paragraph to construct the tiling from the potentials and currents.

By a result of Kirchhoff [8] (see also [3]), the resistance r(a, b) satisfies: r(a, b) = κ_{ab}/κ, where κ is the number of spanning trees in G, and κ_{ab} is the number of spanning trees in G_{ab}, the graph obtained from G by gluing together vertices a and b.

Thus if R is a p × q rectangle, we have p/q = κ_{ab}/κ, and since p and q are relatively prime, κ_{ab} ≥ p and κ ≥ q.

However the number of spanning trees in any graph of m edges is less than 2^{m}, since a tree is a subset of edges, and there are 2^{m} distinct subsets of m edges. Since G has m edges, where m is the number of tiles, we have q ≤ κ ≤ 2^{m}. We conclude that m ≥ log_{2} q.

This gives the lower bound in Theorem 1.

4 The upper bound for real rectangles.

Let R be a rectangle with aspect ratio x (recall x ≥ 1). We assume x < 2: if not, apply the greedy algorithm ⌊x⌋−1 times. The remaining untiled portion has aspect ratio x − (⌊x⌋ − 1) in the range [1, 2).

We show how to tile R quickly. Assume R is x × 1.

The idea is simple: use the greedy algorithm, getting a nested decreasing sequence of rectangles R_{j} (the untiled portions), each containing a fixed corner of R, of aspect ratios x = x_{0}, x_{1}, x_{2}, …, with

x_{j+1} = max\{x_{j} − 1, \frac{1}{x_{j} − 1}\}

until some x_{i} is close to 1, say x_{i} < 1 + δ for some small δ > 0. Note then that for 0 ≤ j ≤ i we have x_{j} < 1/δ.

At step i, instead of putting in a square, which would result in the new rectangle having aspect ratio x_{i+1} > 1/δ, just put in a rectangle of aspect ratio 2, with its longer side covering the shorter side of R_{i}. The remaining untiled portion is a rectangle R_{i+1} with aspect ratio x_{i+1} = 1/(x_{i} − \frac{1}{2}), and so 1 ≤ x_{i+1} < 2. Now continue.

Since for each j we have 1 < x_{j} < \frac{1}{δ}, each square added removes either a fraction at least δ of the area (in the case when one square is added to a rectangle of aspect ratio in [1 + δ, 1/δ]), or a fraction of at least \frac{1}{4(1+δ)} of the remaining area (in case a rectangle of aspect ratio 2, which is tiled by two squares, is added to a rectangle of aspect ratio < 1 + δ). So the area decreases by a factor of at least

max\{1 − δ, 1 − \frac{1}{4(1 + δ)}\}

per square added.

This quantity is minimized when δ = \frac{\sqrt{2}−1}{2} ≈ .207, and the rate is λ = 1 − δ ≈ .793.

After k squares, the untiled area is a rectangle of area at most λ^{k}x, and aspect ratio between 1 and \frac{1}{δ}, and so is contained in a neighborhood of radius xλ^{k/2}/δ of the corner.

The completes the proof of Theorem 2. □

Remark. The rate of decrease of area λ = .793 is of course not the optimal one. Optimization of similar algorithms seems to be an interesting problem, but one we won’t consider here. One might conjecture that τ^{2} = \frac{3−\sqrt{5}}{2} ≈ .381 is a lower bound for λ, since the golden rectangle seems to be most easily tiled by the greedy algorithm, which has this rate.

An alternative method for tiling an x × 1 rectangle is suggested by the following result of Hall:

Theorem 5 (Hall [7]) Any real number between \sqrt{2} − 1 and 4 + 4\sqrt{2} can be written as the sum of two 4-aloof numbers.

Here \sqrt{2} − 1 = 2 · [0; 4, 1, 4, 1, …] and 4 + 4\sqrt{2} = 2 · [4; 1, 4, 1 …] are the minimal and maximal possible sums.

So to tile a x×1 rectangle, where 1 < x ≤ 4+4\sqrt{2}, write x = x_{1}+x_{2} where x_{1}, x_{2} are 4-aloof, and divide the x × 1 rectangle into an x_{1} × 1 and an x_{2} × 1 rectangle with a single vertical line. Now tile each of the subrectangles using the greedy method; by 4-aloofness, in each subrectangle each new square added takes up at least 1/5 of the area, so that after 2n squares the remaining area is at most (4/5)^{n} of the original area there. The rate is then λ = (4/5)^{1/2}.

Our method for integral rectangles will be a variant on this method.

5 An upper bound for rational rectangles.

Let R be a p × q rectangle, with p, q ∈ ℤ, (p, q) = 1, 0 < p ≤ q. We assume as before that q/p < 2: if it is larger, use the greedy algorithm n = ⌊q/p⌋ − 1 times, so that the remaining p × (q − np) rectangle satisfies the above conditions.

We establish in this section an upper bound of C log p log log p for the number of squares needed to tile R. Section 7 refines the construction to improve the bound to C_{1} log p.

The construction proceeds as follows. Let x_{1}, x_{2} be 4-aloof numbers such that x_{1} + x_{2} = q/p (using Theorem 5). Let k_{1} = ⌊x_{1}p⌋, and k_{2} = q − k_{1}, so that |\frac{k_{i}}{p} − x_{i}| < \frac{1}{p} and

\frac{k_{1}}{p} + \frac{k_{2}}{p} = \frac{q}{p}.

We divide the rectangle R into a p×k_{1} rectangle R_{1} and a p×k_{2} rectangle R_{2}. We will show (below, after Lemma 8) that we can apply the greedy algorithm successfully to each of these rectangles for a while, that is, until the remaining untiled rectangles R′_{1}, R′_{2} each have side lengths ≤ c\sqrt{p} for some universal constant c (and R′_{1}, R′_{2} have aspect ratios ≤ 2).

We then repeat the process, using Theorem 5 again to subdivide R′_{1}, R′_{2} each in two, applying the greedy algorithm until the remainders have sides ≤ c\sqrt{cp^{1/2}} ≤ c^{2}p^{1/4}, and so on.

We show that at each stage the number of squares added in a single rectangle before we subdivide it is at most the logarithm to the base α = 6/5 of its larger side length. The side lengths decrease by at least x ↦ c\sqrt{x} before we resubdivide, and each subdivision doubles the number of rectangles. When the edge lengths of a subrectangle are less than the constant 2c^{2} in length, simply tile the subrectangle in any way you please.

We derive for the total number N of squares needed to tile:

N ≤ 2 log_{α} p+4 log_{α}(cp^{1/2})+8 log_{α}(c^{3/2}p^{1/4})+…+2^{k} log_{α}(c^{2−2^{−k+1}}p^{2^{−k}})+2^{k+1}c′,

where k is chosen so that p^{2^{−k}} ≈ 2, that is, k ≈ log_{2} log_{2} p, and c′ is the number of squares needed to tile an integer-sided rectangle whose sidelengths are bounded by 2c^{2}. (Note that c^{b}p^{β} → c^{1+b/2}p^{β/2} under the map x ↦ c\sqrt{x}.)

Thus the number of squares is bounded above by

N ≤ 2k log_{α}(c^{2}p) + 2^{k+1}c′ ≤ 2 log_{α}(c^{2}p) log_{2} log_{2} p + 2c′ log_{2} p.

It remains to prove our claim that we can tile a p × k_{1} rectangle quickly using the greedy algorithm until the remining untiled rectangle has edges ≤ c\sqrt{p}.

Recall that a Farey interval I is a subinterval of (0, ∞) with rational endpoints (\frac{p_{1}}{q_{1}} , \frac{p_{2}}{q_{2}} ) which satisfy p_{2}q_{1} − p_{1}q_{2} = 1. (Notationally we allow p_{2}/q_{2} = ∞ = “\frac{1}{0}” and p_{1}/q_{1} = 0 = “\frac{0}{1}”.) Each Farey interval I gives rise to two Farey subintervals L(I) = (\frac{p_{1}}{q_{1}} , \frac{p_{1}+p_{2}}{q_{1}+q_{2}} ) and R(I) = (\frac{p_{1}+p_{2}}{q_{1}+q_{2}} , \frac{p_{2}}{q_{2}} ), and the set of all Farey intervals form a binary tree in this way with the root being I_{0} = (0, ∞) = (\frac{0}{1}, \frac{1}{0}). A Farey interval has a label indicating the unique descending path to I from the root; this label is a finite word in the letters ‘L’ and ‘R’. thus for example LRL(I_{0}) = LR((\frac{0}{1}, \frac{1}{1})) = L((\frac{1}{2}, \frac{1}{1})) = (\frac{1}{2}, \frac{2}{3}). The Farey interval I = R^{a_{0}}L^{a_{1}}R^{a_{2}}L^{a_{3}} … R^{a_{2k}}(I_{0}) has the property that for x ∈ I, the continued fraction expansion of x begins x = [a_{0}; a_{1}, a_{2}, …, a_{2k}, …], and similarly for words ending in L^{a_{2k+1}}. We call a Farey interval finite if q_{2} > 0.

Lemma 6 If I = (\frac{p_{1}}{q_{1}} , \frac{p_{2}}{q_{2}} ) is a finite Farey interval and contains a 4-aloof number, then 1/5 ≤ \frac{q_{1}}{q_{2}} ≤ 5.

Proof. If x ∈ I is 4-aloof, the word w such that I = w(I_{0}) has no more than 4 consecutive L’s or R’s. In particular 1/5 < x < 5, so x is in one of the intervals

(\frac{1}{5}, \frac{1}{4}), (\frac{1}{4}, \frac{1}{3}), (\frac{1}{3}, \frac{1}{2}), (\frac{1}{2}, \frac{1}{1}), (\frac{1}{1}, \frac{2}{1}), (\frac{2}{1}, \frac{3}{1}), (\frac{3}{1}, \frac{4}{1}), (\frac{4}{1}, \frac{5}{1}),

for which the result is true.

Now if I = L(J), then clearly q_{1} ≤ q_{2}, and so each of R(I), R^{2}(I), R^{3}(I), R^{4}(I) satisfy the property. If I = R(J), then q_{1} ≥ q_{2} and so each of L(I), L^{2}(I), L^{3}(I), L^{4}(I) have the desired property. The result easily follows. □

Let |I| denote the length of I: if I = (\frac{p_{1}}{q_{1}} , \frac{p_{2}}{q_{2}} ) then |I| = 1/q_{1}q_{2}.

Corollary 7 If I is a finite Farey interval containing a 4-aloof number, then 1/5 ≤ |L(I)|/|R(I)| ≤ 5.

Proof. If I = (\frac{p_{1}}{q_{1}} , \frac{p_{2}}{q_{2}} ) then

\frac{|L(I)|}{|R(I)|} = \frac{|\frac{p_{1}}{q_{1}} − \frac{p_{1}+p_{2}}{q_{1}+q_{2}} |}{|\frac{p_{2}}{q_{2}} − \frac{p_{1}+p_{2}}{q_{1}+q_{2}} |} = \frac{q_{2}}{q_{1}} .

□

The following lemma is the key fact which makes the construction work.

Lemma 8 If x is 4-aloof and |\frac{k}{p}−x| < \frac{1}{p} then there is a Farey interval (\frac{p_{1}}{q_{1}} , \frac{p_{2}}{q_{2}} ) containing both x and k/p with q_{1} > c_{2}\sqrt{p} for some universal constant c_{2}.

Proof. The Farey intervals nesting down to x decrease geometrically in size (with scale at most 6) by Corollary 7. So there is a Farey interval I containing x, with 5/p ≤ |I| < 30/p. By backing up at most 5 stages towards the root, there is a Farey interval J with I ⊂ J such that the distance of I to the endpoints of J is at least 1/p (because in the last 5 letters of w there is at least one L and one R). Thus J contains both x and k/p. Furthermore \frac{5}{p} ≤ |I| ≤ |J| ≤ \frac{30}{p} · 6^{5} again by Corollary 7. So if J = (\frac{p_{1}}{q_{1}} , \frac{p_{2}}{q_{2}} ), we have

\frac{1}{q_{1}^{2}} ≤ \frac{5}{q_{1}q_{2}} = 5|J| ≤ \frac{5^{2}6^{6}}{p} ,

and so taking square roots

q_{1} ≥ \frac{\sqrt{p}}{5 · 6^{3}}

and similarly for q_{2}. □

If the word labelling J = (\frac{p_{1}}{q_{1}} , \frac{p_{2}}{q_{2}} ) has length ℓ, then after adding ℓ squares to a k × p rectangle using the greedy algorithm, we find the remaining rectangle is a × b, where

( \begin{matrix}a \\ b \end{matrix} ) = ( \begin{matrix}p_{2} & p_{1} \\ q_{2} & q_{1} \end{matrix} )^{−1} ( \begin{matrix}k \\ p \end{matrix} ) ,

and so

a = q_{1}k − p_{1}p = (\frac{k}{p} − \frac{p_{1}}{q_{1}} )pq_{1} ≤ |J|pq_{1} = p/q_{2} ≤ 5 · 6^{3}\sqrt{p},

and similarly for b.

Now if the aspect ratio a/b or b/a is x ≥ 5, then backing up one step gives a rectangle of aspect ratio in [1, 2) and sides bounded by 6 · 6^{3}\sqrt{p}.

This completes the construction.

6 Tiling an “ell”

By an ell we mean a rectilinear polygon (polygon with sides parallel to the axes) with 6 sides. We give here a method for tiling (partially) an ell as in Figure 2 with integer side lengths a, b, c, d as indicated, so that the remaining

Figure 2:

untiled portion is an ell with side lengths a′, b′, c′, d′ of ratios bounded by 8 (i.e. the ratios are all in [1/8, 8]). This construction is a subroutine in the algorithm we will devise in the next section.

Let L be an ell as in Figure 2. In what follows we describe an ell with four edge lengths a, b, c, d: these are the lengths of the four edges corresponding to the edges marked a, b, c, d of Figure 2.

Let a, b, c, d be given. If either of b/a or c/d (say b/a) is ≥ 2 we add a square of side a adjacent to the edge of length a, giving a new ell with b/a reduced by 1; this does not increase the largest ratio of a, b, c, d. So in what follows we assume b/a, c/d < 2. By symmetry we may assume either a or b is the longest edge. There are a number of cases to consider^{1}: Case 1. Suppose a is the longest edge. Case 1a. Each of the lengths a, b, c, d is in the interval [d, a]. We can assume d < a/3 or else we are done.

Add 3 squares of side length d as in Figure 3. The new ell has sides b, 3d − c, d, a + c − 3d. Each of these is in the interval [d, a], since 3d − c = d + (2d − c) ≥ d and 3d − c ≤ 3d < a, and a > a + (c − 3d) = c + (a − 3d) > c.

Figure 3:

Case 1b. All edges are in [c, a]. Suppose also that c < a/3.

• If d − c ≥ c, then add a square of side d adjacent to edge d. This gives a new ell with edges b, d − c, d, a + c − d, each in [c, a].

• If d − c < c and a + c − 2d > c, add 2 squares as in Figure 4; the remaining ell has edges b, 2d − c, d, a + c − 2d, and a > 2d > 2d − c > d by hypothesis and so each of these is in [c, a].

• If d − c < c and a + c − 2d ≤ c then a ≤ 2d ≤ 4c and so [c, a] ⊂ [c, 4c].

Case 1c. Edges are in [b, a], and b < a/3.

• If d − c ≥ b, add a square of size d adjacent to side d. The new ell has sides b, d − c, d, a + c − d, each is in [b, a] (a + c − d = c + (a − d) ≥ c ≥ b and a + c − d < a).

1We apologize for the clumsiness of this algorithm.

Figure 4:

• If c > d, add squares adjacent to b and d as in Figure 5; the new ell has edges a − b, b, c + b − d, d, each of which is in [b, a]. (Note c ≥ c + b − d = b + (c − d) ≥ b.)

Figure 5:

• If c ≤ d and d − c < b, add three squares as in Figure 6; the new ell has edges a − 2b, b, c + 2b − d, d, each of which is in [b, a] (note c + 2b − d < 2b < a).

Figure 6:

Case 2. Suppose b is the longest edge. Case 2a. Edges are in [a, b]. Since b/a < 2, we are done. Case 2b. Edges are in [c, b].

• If a ≤ 2d, then b < 2a ≤ 4d < 8c and so [c, b] ⊂ [c, 8c] and we’re done.

• If a > 2d and d − c > c, then add a square to edge d, giving b, d − c, d, a + c − d.

• If a > 2d and d−c < c, then add two squares as in Figure 7, leaving an ell with edges b, 2d−c, d, a+c−2d. Note 2d−c = 2(d−c)+c < 3c < b, and a + c − 2d = a + (c − d) − d < a < b so each edge is in [c, b].

Figure 7:

Case 2c. Edges are in [d, b].

• If a + c − 3d ≥ d add three squares as in Figure 3; the ell has edges b, 3d − c, d, a + c − 3d ∈ [d, b].

• If a+c−3d < d then 3b/2 ≤ a+b < a+c < 4d, and so [d, b] ⊂ [d, 8d/3].

This completes the construction. Suppose that originally the ratios of a, b, c, d were bounded by N. Each square added at the first step in this algorithm has side length at least the length of the shortest of a, b, c, d. Furthermore, the shortest of a, b, c, d never gets any shorter. So each square added takes up at least 1/(N^{2} + N + 1) of the area.

7 A better upper bound for rational rectangles.

We give in this section a refinement of the construction of section 5, yielding a logarithmic bound.

The refinement is based on the following theorem, a two-dimensional version of Theorem 5.

Let C_{n} be the Cantor set of n-aloof numbers.

Theorem 9 For any M > 0 there is an n = n(M) with the following property. For any positive real numbers a, b, c, d with ratios bounded by M there exists t ∈ [0, a] and r_{1}, r_{2}, r_{3} ∈ C_{n} such that :

r_{1} = \frac{t}{b + d}, r_{2} = \frac{a − t}{b}, r_{3} = \frac{a + c − t}{d}.

For the proof, see the Section 8.

The correct interpretation of this theorem is as follows: Given the ell of Figure 8, where the sides a, b, c, d have lengths in ratios less than M, we can find a t ∈ [0, a] so that, for the subdivision indicated, the rectangles R_{1}, R_{2}, R_{3} have aspect ratios in C_{n}. The quantities r_{i} of the theorem are the aspect ratios of the R_{i} as a function of t.

Figure 8: Subdividing an ell into three easy rectangles.

Let R be a p×q rectangle, p, q ∈ ℤ, with (p, q) = 1 and again 1 < q/p ≤ 2. The construction now proceeds as follows. Let n = n(M) with M = 8 in Theorem 9. As before, use Theorem 5 to divide R into two rectangles R_{1}, R_{2}, respectively p × k_{1} and p × k_{2}, with k_{i} ∈ ℤ and k_{i}/p within 1/p of an n-aloof number (We assume n ≥ 4).

Apply the greedy algorithm to R_{1} and R_{2} as before, until the sides of the untiled rectangles R′_{1}, R′_{2} have length ≤ c\sqrt{p}, and aspect ratios < 2. (Now the constant c here depends on n). It is easy to arrange that R′_{1} and R′_{2} are adjacent, and so the union of the untiled regions R′_{1} ∪ R′_{2} then forms an ell.

We claim that we can also arrange so that the ratios of edge lengths of R′_{1} and R′_{2} are at most n: simply back up the greedy algorithm if necessary for the smaller of R′_{1}, R′_{2} until it is approximately the same size as the other. Since the change in scale between the time the aspect ratio is in [1, 2] and the next time it is in [1, 2] is at most n, this proves the claim.

Using the subroutine of section 6, we can tile this ell “easily” (that is, each square added takes up a definite proportion 1/(n^{2} + n + 1) of the area) until all the ratios of sides are less than 8.

We then apply Theorem 9 with M = 8: this subdivides the ell into three rectangles with aspect ratios in C_{n}. By choosing t′ to be the integer closest to the t of the theorem, we can subdivide the ell into three rectangles R_{3}, R_{4}, R_{5} each with integer sides of length ≤ c\sqrt{p} and with aspect ratios \frac{t′}{b+d}, \frac{a−t′}{b} , \frac{a+c−t′}{d} within \frac{1}{b+d}, \frac{1}{b}, \frac{1}{d} respectively of points in C_{n}.

We can now use the greedy algorithm on the R_{3}, R_{4}, R_{5}, until the edge lengths are less than c^{3/2}p^{1/4}, and the untiled rectangles R′_{3}, R′_{4} of R_{3}, R_{4} respectively, are adjacent, have aspect ratios < 2, and are the same size to within a factor of n. (The R′_{3}, R′_{4} are not necessarily adjacent to R′_{5}).

At the next step the ell formed by R′_{3} ∪ R′_{4} is tiled using the ell method of section 6 and then is subdivided into 3 “easy” rectangles (using Theorem 9 again), and R′_{5} is subdivided using Theorem 5 into two easy rectangles. As we continue this process, each ell gives rise to an ell and a single rectangle, and each single rectangle gives rise to an ell.

So the total number of untiled rectangles at the nth stage of the construction is just the nth Fibonacci number: letting f_{n}, g_{n} be the number of ells and single rectangles, after one iteration we have

( \begin{matrix}f_{n+1} \\ g_{n+1} \end{matrix} ) = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}f_{n} \\ g_{n} \end{matrix} ) .

As a consequence the number of squares needed to tile is N, where:

N ≤ 2 log_{α} p+3 log_{α}(cp^{1/2})+5 log_{α}(c^{3/2}p^{1/4})+…+F_{k} log_{α}(c^{2−2^{−k+1}}p^{2^{−k}})+F_{k+1}c′,

where as before k ≤ log_{2} log_{2} p, c′ is a bound on the number of squares needed to tile a rectangle of edge bounded by 2c^{2}, and α is a constant depending on n. This is a convergent geometric series, since F_{m} ≈ τ^{m} and τ ≈ 1.618 < 2. We have N ≤ C_{1} log p for some universal constant C_{1}. This completes Theorem 1. □

8 Proof of Theorem 9

We will prove a stronger result (Theorem 11).

Recall that a gap of a Cantor set C ⊂ ℝ is a connected component of ℝ−C. A Cantor set C is called (K, ϵ)-thick if C is obtained from an interval J by removing successively open subintervals of J which are gaps of C, with the property: when an gap I is removed from a connected subinterval J, leaving intervals I′, I′′ on either side with J = I′ ∪ I ∪ I′′, then |I| ≤ ϵ|J| and |I′|/|I′′| ∈ [1/K, K].

Recall that C_{n} is the Cantor set of n-aloof numbers. The following lemma is essentially due to Hall [7] (he studied the case n = 4, but his methods extend to any n).

Lemma 10 For any ϵ > 0 there is an integer n such that C_{n} is (3, ϵ)-thick.

Theorem 11 Given M_{1}, M_{2} > 1 there exists an ϵ > 0 with the following property. Let E_{1}, E_{2}, E_{3} be three (3, ϵ)-thick Cantor sets in ℝ with diameters in ratios bounded by M_{1}. Let S be the orthogonal projection of E = E_{1} × E_{2} × E_{3} ⊂ ℝ^{3} to ℝ^{2} along a vector v ∈ ℝ^{3} whose coordinates have ratios in absolute value bounded by M_{2}. Then S contains every point in ℝ^{2} in the convex hull of S which is not within a small neighborhood of the boundary of the convex hull of S.

Remark. Let us show that this theorem implies Theorem 9. Take E_{i} to be the Cantor set C_{n}. For n sufficiently large this Cantor set is (3, ϵ)-thick, by Lemma 10. The set

ℓ = \{(\frac{t}{b + d}, \frac{a − t}{b}, \frac{a + c − t}{d}) | t ∈ [0, a]\} ⊂ ℝ^{3}

is a line segment which passes completely through the convex hull of E. The direction of ℓ is

v = (\frac{1}{b + d}, \frac{−1}{b}, \frac{−1}{d}),

whose coordinate ratios are bounded in absolute value by 9 by hypothesis (recall b/d, d/b ≤ 8). We need to show that ℓ intersects E.

Let π be the projection π: ℝ^{3} → ℝ^{2} given by

π(x, y, z) = (x + \frac{zd}{b + d}, y + \frac{zd}{b})

(which is not the orthogonal projection, but is orthogonal projection followed by a linear map of bounded distortion). Then π(ℓ) is the single point (\frac{a+c}{b+d}, \frac{2a+c}{b}), which is contained in the square Q = [1/8, 8] × [3/8, 24] because the ratios of any two of a, b, c, d are bounded by 8, and Q is in turn contained and not close to the boundary of the convex hull of π(E) for n large (n > 24). Thus π(ℓ) ⊂ π(E), and so ℓ intersects E.

Lemma 12 Fix N > 0. If a Cantor set C ⊂ ℝ is (3, ϵ)-thick for some ϵ < 1/5 then for some k we can remove gaps I_{1}, I_{2}, …, I_{k} from the convex hull of C, leaving subintervals J_{1}, J_{2}, …, J_{k+1}, with |I_{i}|/|C| < ϵ and for each i,

\frac{|C|}{5N} < |J_{i}| ≤ \frac{|C|}{N}.

Proof: Since C is (3, ϵ)-thick with ϵ < 1/5, each gap I removed from a subinterval J leaves two subintervals I′, I′′ of length at least 1/5th of the length of J (since |J| = |I′| + |I| + |I′′| ≤ |I′| + |J|/5 + 3|I′|).

So one simply removes gaps from the convex hull until the remaining subintervals J_{i} have length between |C|/N and |C|/5N. □

Proof of Theorem 11. Our proof remains at a qualitative level for simplicity. In particular we won’t try to estimate the best ϵ.

Let I_{1}, I_{2}, I_{3} be the convex hulls of E_{1}, E_{2}, E_{3}. The projection of I_{1}×I_{2}×I_{3}, the convex hull of E, is a hexagon with opposite sides parallel. For such a hexagon H, define U(H) to be the set of points in the interior of H and at distance more than a/10 from any boundary edge of length a (see Figure 9). Call U(H) the inner neighborhood of H.

Figure 9: The inner neighborhood of a hexagon.

Define subdivisions of the E_{i} as in Lemma 12 for some large N: so that for i = 1, 2, 3 we have E_{i} = E_{i1} ∪E_{i2} ∪…∪E_{in_{i}} and |E_{ij}|/|E_{i}| ∈ [1/5N, 1/N). The projection of the union of the convex hulls of the E_{1i_{1}} × E_{2i_{2}} × E_{3i_{3}} is a “stack” of hexagons as in Figure 10. By Lemma 13 below, U(E) is contained in the union of the inner neighborhoods of the “blocks” E_{1i_{1}} × E_{2i_{2}} × E_{3i_{3}}. Furthermore each block again satisfies the hypotheses of Lemmas 12 and 13, and so we can subdivide it again, and repeat. For each point x ∈ U(E), we obtain in this way a sequence of blocks converging to x. By compactness U(E) is contained in π(E). □

Lemma 13 Suppose the same hypotheses as in Theorem 9. For some N large define subdivisions {E_{1i}}, {E_{2j}}, {E_{3k}}, of E_{1}, E_{2}, E_{3} respectively as in Lemma 12. If N is sufficiently large and ϵ sufficiently small, then

U(E) ⊂ ⋃_{i,j,k} U(E_{1i} × E_{2j} × E_{3k}).

Proof. The proof by picture is the most illuminating. The direction of the diagonal edge of the hexagon in Figure 10 (i.e. the vector π(0, 0, 1) = (\frac{d}{b+d}, \frac{d}{b}))

Figure 10: The inner neighborhoods (3 of which are shaded) of the blocks cover the inner neighborhood of the whole stack.

has slope (b + d)/b between 1 and M_{1}. Using also the fact that the boxes E_{1i} × E_{2j} × E_{3k} have edge-lengths of ratios bounded by a constant (5M_{1}), their projections are hexagons with edge lengths of ratios bounded by another constant C(M_{1}, M_{2}).

Now if N, the approximate number of blocks per edge in the stack, is sufficiently large and ϵ is sufficiently small compared to the size of the smallest block, we see that the inner neighborhoods of all the boxes U(E_{1i}×E_{2j} ×E_{3k}) cover all of the convex hull of π(E) except in a small neighborhood of the boundary; in particular they cover U(E). □

9 Problems

Problem 1 What are the best constants in the upper and lower bound of Theorem 1?

Our constructions leave lots of room for improvement in the constant appearing in the upper bound. The lower bound of log_{2} max(p, q) can also be improved, however. This is another interesting problem in itself:

Problem 2 Among all graphs with m edges, which graph G has the largest number of spanning trees κ(G)? What is the sup of κ(G)^{1/m} over all graphs? Over planar graphs?

We used the trivial bound 2^{m} for the number of spanning trees of a planar graph. This bound can be improved; N. Young indicated to us an upper bound of λ^{m} for some λ < 2, which comes from taking into account the vertex degrees.

On the other hand the n × n planar grid graph has κ(G)^{1/m} converging to ≈ 1.79 (see [4]) as n → ∞, and this is the largest value we know of. So the actual largest value is somewhere in the range (1.79, 2).

Problem 3 How many cubes does it take to tile a p × q × r box?

None of our methods work for this case; even the greedy algorithm is difficult to define.

10 Appendix

We give here a proof of Theorem 4, which Yuval Peres has kindly allowed us to include.

Recall the notation: x ∈ (0, 1) and has continued fraction expansion x = [0; a_{1}, a_{2}, …] with nth approximants p_{n}/q_{n}.

Let S_{N}(x) be the sum of the first N partial quotients of x. Diamond and Vaaler [6] showed that for almost all x,

S_{N}(x) = (1 + o(1))N log_{2} N + θ max_{1≤k≤N} a_{k}(x),  (2)

where θ ∈ [0, 1] (and θ depends on both x and N).

We are interested in N_{ϵ}(x) = min{N : |q_{N}x − p_{N}| < ϵ}. By a result of Khinchin and Levy (cf [1]), for almost every x

\frac{1}{N} log |q_{N}x − p_{N}| → −c_{1} = −\frac{π^{2}}{12 log 2}.

By discarding a set of measure δ for any small δ > 0, this convergence is uniform, i.e. on a set A ⊂ (0, 1) with μ(A) > 1 − δ, we have

sup_{A}\{\frac{1}{N} log |q_{N}x − p_{N}| + c_{1}\} → 0.

We conclude that log \frac{1}{ϵ}/N_{ϵ}(x) converges uniformly to c_{1} on A.

Using the Gauss-Kuz’min measure we have μ{x : a_{i}(x) ≥ k} < c_{2}/k for a constant c_{2}; and so on A we have (using M_{ϵ} = \frac{1}{c_{1}} log \frac{1}{ϵ}):

μ \{x ∈ A | max_{1≤k≤M_{ϵ}} a_{k} ≥ M_{ϵ}\sqrt{log M_{ϵ}}\} ≤ M_{ϵ}μ \{x ∈ A | a_{1} ≥ M_{ϵ}\sqrt{log M_{ϵ}}\}
≤ c_{2}/\sqrt{log M_{ϵ}}.

Letting B be the complement of this set in A, using (2) and M_{ϵ} = \frac{1}{c_{1}} log \frac{1}{ϵ} we have for all x ∈ B

T_{ϵ}(x) = S_{N_{ϵ}(x)} = (1 + o(1))N_{ϵ}(x) log N_{ϵ}(x) + θM_{ϵ}\sqrt{log M_{ϵ}}
= (1 + o(1))c_{3} log \frac{1}{ϵ} log log \frac{1}{ϵ}

for some constant c_{3} > 0. □

References

[1] P. Billingsley, Ergodic Theory and Information. New York: Wiley 1965.

[2] B. Bollobas, Graph theory: an introductory course. New York: Springer Verlag 1979.

[3] Brooks, Smith, Stone, Tutte; The dissection of rectangles into squares. Duke Math J. 7, (1940), 312-340.

[4] R. Burton, R. Pemantle; Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, preprint.

[5] M. Dehn; Zerlegung von Rechtecke in Rechtecken, Math. Annalen, 57 (1903) 314-332.

[6] H. G. Diamond and J. D. Vaaler; Estimates for partial sums of continued fraction partial quotients. Pacific J. Math. 122 (1986):73-82.

[7] M. Hall; On the sum and product of continued fractions. Annals of Math, 48 (1947):966-993.

[8] G. Kirchhoff; Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilen galvanisher Ströme geführt wird, Ann. Phys. Chem. 72 (1847):497-508.