## Tiling A Rectangle With A Hint of Magic

Here's a a famous problem:

## If a rectangle $R$ is tiled by rectangles $T_i$ each of which has at least one integer sidelength, then the tiled rectangle $R$ has at least one integer side length.

$\mbox{}$

There are a number of proofs of this result (14 proofs in this particular paper). One would think this problem is a tedious exercise in combinatorics, but the broad range of solutions which do not rely on combinatorial methods makes me wonder what deeper principles are at work here. In particular, my question is about the proof using double integrals which I sketch out below:

Suppose the given rectangle $R$ has dimensions $a\times b$ and without loss of generality suppose $R$ has a corner at coordinate $(0,0)$. Notice that $\int_m^n\sin(2\pi x)dx=0$ iff $m\pm n$ is an integer. Thus, for any tile rectangle $T_i$, we have that:

$\int\int_{T_i}\sin(2\pi x)\sin(2\pi y)dA=0$

If we sum over all tile rectangles $T_i$, we get that the area integral over $R$ is also zero:

$\int\int_{R}\sin(2\pi x)\sin(2\pi y)dA=\sum_i\int\int_{T_i}\sin(2\pi x)\sin(2\pi y)dA=0$

Since the cornor of the rectangle is at $(0,0)$, it follows that either $a$ or $b$ must be an integer.

My question is as follows: where exactly does such a proof come from and how does it generalize to other questions concerning tiling? There is obviously a deeper principle at work here. What exactly is that principle?

One can pick other functions to integrate over such as $x-[x]-1/2$ and the result will follow. It just seems like black magic that this works. It's as if the functions you are integrating over tease out the geometric properties of your shape in an effortless way.

EDIT: It's likely that one doesn't necessary need integrals to think in the same flavor as this solution. You're essentially looking at both side lengths in parallel with linear test functions on individual tiles. However, this doesn't really explain the deeper principles here, in particular how one could generalize this method to more difficult questions by choosing appropriate "test functions."

-
Back in the mid 1990s during a lecture series by Alain Connes at the Newton Institute, he mentioned that one doesn't really understand the integers unless one understands this problem. – JosÃ© Figueroa-O'Farrill Feb 5 2010 at 12:31

## 2 Answers

It is not at all obvious to me that there is any deep principle at work in the double-integral proof. In my mind, the double-integral proof is really the same as the checkerboard proof. You're just trying to come up with a translation-invariant function on rectangles that is (a) additive and (b) zero if and only if the rectangle has the property of interest. All that matters is that you pick a function that cancels itself out in the same way as the checkerboard pattern does. The choice of the sine function for this purpose is amusing but not deep.

If you're looking for deeper principles then I would recommend Rick Kenyon's paper "A note on tiling with integer-sided rectangles," J. Combin. Theory Ser. A 74 (1996), no. 2, 321-332. Using this problem as an example, Kenyon demonstrates the concept of the Conway-Lagarias tiling group, a powerful tool for studying tiling problems.

-

There is an exercise in "Modern Graph Theory" by Bollobas section II.4 pg 63 that is essentially the same argument, but eliminates the trigonometric functions. For each rectangle $U = [x_1, x_2] \times [y_1, y_2]$ let $\psi(U) = (x_2 - x_1) \otimes (y_2 - y_1)$ in $\mathbb{Z}(\mathbb{R}/\mathbb{Z}) \otimes \mathbb{Z}(\mathbb{R}/\mathbb{Z})$ (viewed as a $\mathbb{Z}$ module). Then $\sum_{U} \psi(U) = 0$ so the original rectangle must have an integer side.

[Edited after Reid's comment. Here $\mathbb{Z}(\mathbb{R}/\mathbb{Z})$ is the free $\mathbb{Z}$ module with basis $\mathbb{R}/\mathbb{Z}$]

-
Isn't, say, $\pi \otimes \frac12 = \frac\pi2 \otimes 1 = 0$ in $\mathbb{R}/\mathbb{Z} \otimes \mathbb{R}/\mathbb{Z}$? So we can only conclude that the original rectangle has a rational side? – Reid Barton Feb 5 2010 at 4:06
Using $\mathbb{Z}(\mathbb{R}/\mathbb{Z})$ doesn't seem any better; now you're just counting rectangles by their dimensions mod 1, and the fact that they tile a larger rectangle has no counterpart in algebra. – Reid Barton Feb 6 2010 at 15:30