2
$\begingroup$

I’m thinking about the well known pattern generated by constructing a series of squares with side lengths following the Fibonacci sequence. Each time we add in a new square, we choose a side of the current rectangle for it to be ‘branching off from’, for lack of a better term. If we loop around so that we first choose the right side, the top, the left and then the bottom side in that order repeatedly, we obtain something like the image below.

Fibonacci tiling

It is often stated that this iterative procedure will ‘tile the plane’. I take this to mean that given any point on the infinite two-dimensional Euclidean plane, there exists at least one (or possibly exactly one, depending on our definition) square that contains this point. More loosely: in the limit (as the number of squares approaches infinity), the whole plane is covered by this pattern of squares.

Here it is fairly obvious that this is going to be the case, and yet as always I’m wondering if there is a more formal way that we can prove this, or whether such a proof is even a sensible notion.

Could we perhaps show that the function (from the set of squares to 2D Euclidean space) mapping a given square to the set of points that it contains is a surjection in the sense that all of the points in the plane exist in at least one of these sets? Or, I suppose, show that there exists a function from the points to the squares with the opposite relation that is defined on the whole plane?

Maybe we could start by observing that the space occupied by the first square is covered, and then use an induction step to show that given any point on the plane, the surrounding points (in some sense) are also covered at some point in the iteration.

In order to even construct such a proof we would need a more rigorous definition of ‘tiles the plane’ than ‘it covers the whole thing after a long enough time’. Does such a definition exist? Surely it must, and yet I can’t find it anywhere.

$\endgroup$
  • 1
    $\begingroup$ To speak very crudely, one might define for these purposes, the radius of a configuration such as this to be the minimum distance from the first square to the boundary of the union. Then, I suppose that the radius is an increasing function, indeed somewhat exponential, thus going to $\infty$. With a few more words, the argument should complete. (I promised crude.) $\endgroup$ – Lubin Apr 9 '19 at 0:03
  • $\begingroup$ @Lubin, makes sense. So I take it there does not really exist a standard rigorous definition of ‘tiling the plane’, and that these types of proofs are rarely used? $\endgroup$ – 雨が好きな人 Apr 9 '19 at 0:10
  • $\begingroup$ Sorry, but I’m way outside the field, so I don’t know what counts as “standard”. $\endgroup$ – Lubin Apr 9 '19 at 0:14
1
$\begingroup$

I believe you had a good idea for a definition, which I will phrase this way:

A collection of regions in the plane covers the entire plane if for each point $P$ in the plane, $P$ is a member of at least one region in the collection.

Making a narrower definition by adding an obviously desirable condition:

A countable collection of regions in the plane tiles the entire plane if the collection covers the plane and the intersection of any two regions has measure zero.

The "measure zero" part is a way of saying that it's OK for two regions to intersect along their boundaries (that is, it's OK for their intersection to be a line segment or other curve), but not OK for their intersection to be a region with a non-zero area.

There are other ways to define a tiling, for example, a countable collection of open topological disks such that no two disks intersect but the closure of the union of all disks is the entire plane, and one of these definitions might be more elegant or better in some other way, but I think the definition based on your idea is good enough and easy to work with.

To show that your tiling tiles the plane, consider how it is constructed. You start by placing a single square on the plane; we can apply Cartesian coordinates to the plane so that the square has lower left corner $(0,0)$ and upper right corner $(1,1).$ That's step $0.$ At each subsequent step, assuming the union of squares previously placed is a rectangle, you place a square adjacent to one side of the rectangle so that the union this square and the previous ones forms a larger rectangle. This satisfies the assumption required to take the next step, so by induction there is one such square for every non-negative integer: a countably infinite collection of squares.

The specific rule for placing the next square is that for $n = 1, 2, 3, \ldots,$ on step $4n - 3$ you adjoin a square to the right side of the rectangle, on step $4n - 2$ you adjoin a square to the top of the rectangle, on step $4n - 1$ you adjoin a square to the left side of the rectangle, and on step $4n$ you adjoin a square to the bottom of the rectangle.

Moreover, at each step the side of the added square is at least $1.$ It's almost always a lot more than $1,$ but that's still at least $1.$

So after the next $4$ steps, the squares placed so far (which are a subset of the entire countably infinite collection) cover a rectangle that extends at least one unit farther to the right, at least one unit farther upward, at least one unit farther to the left, and at least one unit farther downward. By induction, you can show that after $4n$ steps the rightmost $x$ coordinate and topmost $y$ coordinate are each at least $n + 1$ (they will almost always be much larger, but we don't care about that) and the leftmost $x$ coordinate and bottommost $y$ coordinate are each no greater than $-n$ (they will actually be less than that, but again we don't care).

Given an arbitrary point in the plane, if its coordinates are $(x,y)$ then we can set $n = \lceil \max\{\lvert x\rvert,\lvert y\rvert\}\rceil,$ that is, set $n$ to an integer greater than the larger of the absolute values of the two coordinates, and we are guaranteed that one of the first $4n$ squares in the collection (counted according to the procedure above) will cover the coordinates $(x,y).$ (In most cases we'll actually cover the coordinates long before the $4n$th square, but it doesn't matter exactly when we cover them, just that they are covered.) Therefore the plane is tiled.

As to whether a formal proof is "necessary," it seems that much of the work on tilings does not use anything nearly as formal as the argument above. In a case like this, the argument may just be too "obvious" to take the trouble to state.

$\endgroup$
  • $\begingroup$ I had a similar idea actually but you wrote it out in a more logical fashion. The topological definition is interesting too, although I know very little about that kind of thing so far! $\endgroup$ – 雨が好きな人 Apr 16 '19 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.