Tiling a rectangle with a hint of magic

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 side length, then the tiled rectangle $R$ has at least one integer side length.

There are a number of proofs of this result (14 proofs in this particular paper by Stan Wagon). 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 corner 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}$]

Answer 3

There is an unpublished note on this theorem from 1987 by Edgser W. Dijkstra, On a Problem transmitted by Doug McIlroy, see also this summary. He explains how the proof that uses complex double integrals (number 1 in Wagon's paper) naturally follows from an initial choice of formalizing the tiling property, and in particular, how the complex numbers come up. In the end he speculates about the general applicability of such an approach.

As an aside, there is also a proof with contour integrals in a much later note of Dijkstra: Ulrich Berger’s argument rephrased. ("Ulrich Berger’s argument" is essentially the sweep-line proof, number 12 in Wagon's paper, see EWD1023, Ulrich Berger's solution to the rectangle problem.)

Answer 4

IMHO the "deeper principle at work here" is assigning a convenient measure to the objects being combinatorially combined. The closest example that comes to mind is this problem:

Is it possible to cover a 2-D disk of diameter 10 with 9 rectangles of length 10 and width 1?

One solves the above by projecting the disk cover onto 1/2 sphere above it, noting that each rectangle's intersection with the disk projects to the area of the 1/2 sphere equal to 1/10th of the 1/2 sphere area, this proving that 9 rectangles won't be enough.

Both problems - the one in the question and the above one - chose a measure density (a signed one in the case of the rectangle R cover) that would have a convenient integration property.