Question

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."

Answer 1

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.

Answer 2

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}$]