Integer Tiles: Unveiling the Rectangle's Inner Workings

Tiling a Rectangle

Here's a simple-sounding challenge.

Problem. Imagine that you have a number of rectangles, each of which has at least one integer side. If they come together to tile a larger rectangle, must it also have one integer side?

It looks like high school combinatorics, but at the 1985 Summer Meeting of the Mathematical Association of America, Hugh Montgomery and other mathematicians decided it was worth their time to come up with fourteen solutions.

And when the easiest one involves a complex double integral, I get curious.

It turns out, the modest rectangle hides many secrets, and its tessellation isn't as trivial as it seems. This tiling problem is different from the rest: there aren't any restrictions to the length of the non-integer side of each tile, adding new layers of intricacy.

What's more, the conception and design of the answer is so elegant that no mathematical experience can be complete without it. But for those unacquainted with standard undergraduate-level math, even hearing the mention of a "complex double integral" may be enough to induce feelings of despair.

So before presenting the main proof, I'll break down the bare minimum you need to know about double integrals on complex values. If you're familiar with these concepts, feel free to skip ahead.

Either way, I have no doubt that this rectangular tiling conundrum will top your list of favorite problems. Stick around, and I'll make sure to leave no tile untouched.

Double Integrals

Picture yourself with a freshly baked cake. Its sides and base are flat, but at the top, it's allowed to expand and display slight irregularities. To savor a piece, you press a rectangular cookie-cutter right in the middle, extracting your dessert.

Congratulations, you've just performed a double integral.

Well, this isn't true in the literal sense. I didn't specify a function, so there wasn't any integral to compute. However, the cake analogy does provide an accurate visualization for what double integrals are. If standard integrals represent area, double integrals portray volume.

With multivariable functions like \(z=f(x,y)\), both \(x\) and \(y\) are free variables, so the \(xy\)-plane is fully filled with points. And for each point on this plane, a certain quantity shoots out or pokes in: the value of \(z\) that depends on \(x\) and \(y\).

What you get is a surface. To integrate it, calculate the areas under the graph for many thin slices along one axis. Then, sum them up along the other. Put another way, this process finds the volume under a surface given a specific rectangle in the \(x y\)-plane.

Ergo, dissected cakes yield double integrals.

Within the aforementioned "cake" model, the additive property of double integrals is obvious. If you split your cookie-cutter into two or more parts but press at the same location, you get the same volume of cake. So if you partition the rectangle you're integrating over, you get the same result.

Your tasty confection also justifies Fubini's theorem: the formal statement that the order of integration doesn't matter. When you slice your cake horizontally, you acquire a different integral than if you had sliced it vertically. Yet for "well-behaved" pastries, the volumes, and by proxy the integrals, are equal.

Fubini tells you that for as long as your function is sufficiently nice, as almost all functions are, determining a double integral is no less straightforward than determining two regular integrals in succession.

Complex Values

You might not know it, but you have a deep relationship with \(\R\). When you first learned fingertip arithmetic or explored the never-ending decimal expansion of \(\pi\), you played with objects that belonged to this set of all real numbers.

The same is true in calculus. At a fundamental level, functions are just machines that return an output for any given input. In most cases, both the domain and codomain of any function you need to differentiate or integrate happens to be \(\R\).

What happens when I replace the codomain with \(\mathbb{C}\)?

Consider, for instance, the function \(f(x)=i x^2\). The \(x\)'s that you're allowed to put in must be real, but it's clear that any output \(f\) spits back will be imaginary. In situations like this, is \(f'(x)\) still \(2 i x\)? And are you still confident that \(\int f(x)\ d x=\frac{1}{3} i x^3\)?

In other words, can you treat \(i\) as a constant?

There's more subtlety to this technical detail than most people give credit for. To comprehend why the answer is, in fact, yes, you'll need to backtrack to the bedrock of calculus: limits.

Recall the epsilon-delta definition of a limit. The limit of \(f(x)\) as \(x\) approaches \(x_0\) is \(L\), i.e. \[\lim_{x\to x_0} f(x)=L,\] if for every \(\epsilon >0\), there exists a \(\delta >0\) such that for all \(x\), \[0<|x-x_0|<\delta \implies |f(x)-L|<\epsilon.\]

Here's the kicker. At no point in this definition are real numbers mentioned at all. Let the unknowns inside the second modulus be complex, and the formulation still works.

Differentiation is the limit of a difference quotient, and integration is the limit of a Riemann sum. So when limits are defined for outputs in the complex world, the rest of calculus is as well. And since \(i\) is just another number in \(\mathbb{C}\), it's safe to tolerate its existence inside differentials and integrals.

Now, it's easy to prove Euler's formula: \(e^{i x}=\cos x+i \sin x\). Let \(f\) be the function \[f( x) =e^{-i x}(\cos x+i \sin x).\] When you differentiate \(f\) with the product rule and work through the necessary simplifications, you get \(f'(x)=0\), so \(f\) is constant. Then, \[e^{-i x}(\cos x+i\sin x)=f(0)=1,\] and the required identity follows.

An Impossible Proof

The wait is over. I hereby bestow upon you the solution to the rectangular tiling problem.

Solution. Given a tiling that works, let \(R\) denote the ambient rectangle. Assume, without loss of generality, that \(R\) is in standard position, that is, its lower left corner is at the origin, and its sides are parallel to the coordinate axes in the \(xy\)-plane.

Construct the function \(f(x,y)=e^{2\pi i(x+y)}\) and assign its value to each point \((x,y)\) on \(R\). Then, take the integral of \(f\) over an arbitrary rectangle \(A \in R\) with intervals \(x\in [a,b]\) and \(y\in [c,d]\).

Fubini's theorem suggests that this double integral can be split into a product of two ordinary integrals. It's evaluated as follows: \[\iint\limits _{[ a,b] \times [ c,d]} f\ d A =\int _{a}^{b}\int _{c}^{d} e^{2\pi i( x+y)} \ d y d x \]\[=\left(\int _{a}^{b} e^{2\pi i x} \ d x\right)\left(\int _{c}^{d} e^{2\pi i y} \ d y\right)\]\[=\left(\frac{e^{2\pi i b} -e^{2\pi i a}}{2\pi i}\right)\left(\frac{e^{2\pi i d} -e^{2\pi i c}}{2\pi i}\right).\]

By comparing real and imaginary components, you can verify, using Euler's formula, that \[e^{2\pi i n}=1\Longleftrightarrow n\in \mathbb{Z}.\] So if \(A\) has one integer side, one of \(b-a\) or \(d-c\), say \(b-a\), is an integer. Hence, \[e^{2\pi i b} -e^{2\pi i a}=e^{2\pi i a}\left( e^{2\pi i( b-a)} -1\right)=0,\] and it follows that the entire integral is zero.

The converse statement is also true. Starting from the double integral being zero, the logic works in reverse to imply that the rectangle has one integer side.

In the end, the problem indicates that the double integral over each tile vanishes and therefore, by additivity of integrals, the double integral over \(R\) is zero. The converse statement then allows you to conclude that \(R\) has one integer side. Q.E.D.

Many aspects of this proof may appear unfair and miraculous at first, but they're all motivated by a desire to translate problem details into a more palatable format. It's hard to manipulate unknown rectangles, but exponentials exploit their integer side with brilliance.

And while it might be simplest for the human mind to come up with \(f(x,y)=e^{2\pi i(x+y)}\), other suitable functions exist. If you have a personal vendetta against complex numbers, just take the double integral over \[f_1(x,y)=\sin 2\pi x \cdot \sin 2\pi y.\]

Or to keep things discrete, the rounding function can be applied. If \([x]\) rounds \(x\) to the nearest whole number, \[f_2(x,y)=(-1)^{[2 x]}(-1)^{[2 y]}\] gives rise to a nice checkerboard proof.

Seeking Simplicity

What's shown above is refined and exquisite, but having to know about complex double integrals beforehand spoils the fun. Indeed, it was this imperfection that ignited the search for elementary solutions.

And nothing is more elementary than the building blocks of the integers: the primes.

Solution. Place \(R\) in standard position as before. Choose some prime \(p\), and scale the entire tiling up by a factor of \(p\) in the positive \(x\) and \(y\) directions.

Next, think about what happens when you replace all tile corners \((x,y)\) in the scaled-up tiling by \(([x],[y])\). Zoom in on a border between two tiles, and you'll notice that the corners at both ends will be shifted following the same procedure towards nearby lattice points.

Once the smoke clears, convince yourself that there's now a new integer-sided rectangle tiled by integer-sided rectangles. On top of that, each tile has one side a multiple of \(p\), so the sum of the tiled areas is a multiple of \(p\).

Thus, the area of the large integer-sided rectangle is a multiple of \(p\), so one of its sides must be a multiple of \(p\). Plus, only applying the rounding function ensures that the dimensions of this rectangle differ from the dimensions of the scaled-up rectangle by less than 1.

So upon dividing out \(p\) and scaling down, you'd be able to deduce that \(R\) has a side \(\ell\) that differs from an integer by less than \(\frac{1}{p}\).

But \(p\) could've been any prime. If \(\ell\) isn't an integer, it has a fractional part \(\{\ell\}\), and I can always choose a prime \(p\) large enough so that \[\frac{1}{p} < \{\ell\}.\] This insinuates that \(\ell\) isn't within \(\frac{1}{p}\) of an integer, which is a contradiction. It follows that \(\ell\), a side of \(R\), is an integer. Q.E.D.

For those insisting on a combinatorial solution, another avenue of attack utilizes bipartite graphs: graphs with edges that only join vertices in disjoint sets.

Solution. Insert \(R\) in standard position as usual. Let \(S\) be the set of corners of tiles having both coordinates integers, and let \(T\) be the set of tiles.

Form a bipartite graph by connecting each point in \(S\) to all the tiles in \(T\) of which it is a corner. You can check that it's not possible for a tile to have exactly 1 or 3 corners in \(S\). For this reason, each tile has 0, 2, or 4 corners in \(S\), and the graph has an even number of edges.

In particular, every point in \(S\) that's not a corner of \(R\) lies on either 2 or 4 tiles.

Since \((0,0)\), which lies on only one tile, is in \(S\), there must be another point in \(S\) lying on an odd number of tiles for the total number of edges to be even. This can happen only if another corner of \(R\) lies in \(S\), which is to say that one side of \(R\) has integer length. Q.E.D.

As emeritus mathematician Mark Meyerson notes in Quanta Magazine, "It's often of value in math to think up new ways of getting an answer — even to a problem that has been solved before." Although they're harder to grasp, the two proofs in this section demonstrate why.

Pushing Boundaries

Tiling is a staple in combinatorics. But when a problem isn't cracked by coloring, counting, or induction, its solution falls outside of what's conventional. When rectangles create masterpieces, it's natural to reflect on what comes after.

Don't know where to begin? Here are possible starting points:

  1. Is the conclusion still true if the tiles possess rational or algebraic sides rather than integer ones?
  2. How would you generalize to three, or more, dimensions?
  3. What transpires when you tile not a plane, but a cylinder or torus?

As you ruminate over these follow-up questions, examine the solutions above one more time. Will prime numbers be the key to packing boxes in higher dimensions? Will complex double integrals justify the hypothesis on weirder surfaces? The algebra is sure to be tougher, but core plans may remain effective.

If you fail at first, that's okay. What matters is establishing a routine for creative mathematical thought. Because once you resolve mysteries in their purest form, you're capable of expanding core ideas to conquer any trickier variations thrown your way.

Paul Erdos once suggested that "God has a transfinite book of theorems in which the best proofs are written." Although it's unclear what the definition of "best" is, I'm positive that a solution in this post qualifies.

You've successfully subscribed to Jarell
Great! Next, complete checkout for full access to Jarell
Welcome back! You've successfully signed in.
Unable to sign you in. Please try again.
Success! Your account is fully activated, you now have access to all content.
Error! Stripe checkout failed.
Success! Your billing info is updated.
Error! Billing info update failed.