Heesch numbers, Part 1

I love tiling theory. It’s a branch of mathematics that brings together many beautiful ideas, and that offers a lot of open questions for exploration. And of course, it gives us tools to apply mathematics in the world of art and design.

Normally, in my research as a computer scientist I apply tiling theory to create interesting pictures. But when I can, I also enjoy probing at the underlying mathematics. Recently I made a few small discoveries as part of my interest in Heesch numbers, and I thought I’d share them on this blog. I’ll do so in posts to follow. But first, here’s a preliminary post that introduces the ideas that are needed to understand what’s coming.

Surrounding a polygon

Let be a shape in the plane. Under what circumstances can be surrounded by transformed copies of itself? Specifically, I’m looking for a collection of copies of with the following properties:

1. and its copies form a single connected blob in the plane containing no internal holes. (A mathematician might say that and its copies form a “topological disk”.)
2. Every copy of meets in at least one point. In other words, every copy is doing useful work as part of surrounding .
3. Every point of is completely inside the blob. No point of ‘s boundary makes contact with the outside world, not even at corners.

Here’s a visualization of the different ways that a collection of copies might fail to make a surround, followed by an example of a successful surround (bottom right):

If can be completely surrounded in this way, we refer to the copies defined above as a “corona” of . My earlier study of coronas is also what led to the development of the game Good Fences; in fact, I originally called the game “Corona” but didn’t want to release it under that name for fear of incurring the wrath of Anheuser-Busch InBev.

Heesch numbers

Once we can surround a shape with a corona, it’s natural ask whether we can surround that by a second layer, a third layer, and so on. In mathematical terms, we generalize the definition of corona to a -corona: a -corona of is itself, and a -corona is any surround of any -corona of , still using transformed copies of .

We’re now ready to define the Heesch number of a shape as the largest for which has a -corona but not a -corona. We’ve built up a bit of mathematical machinery to get to this point, but a shape’s Heesch number is easy to understand intuitively: it’s the maximum number of complete layers you can place around the shape before you run out of every possible opportunity to build another layer.

It’s easy to observe that there are shapes with Heesch number 0. A circle can’t be surrounded even once—there’s no way for copies of a circle to cover more than six points on its boundary, much less the whole thing! Polygons can also be unsurroundable—a bit of experimentation will convince you that a regular pentagon must have Heesch number 0. At the other extreme, any shape that tiles the plane is defined to have Heesch number : any tiling by that shape provides you with a “template” from which you can trace out as many coronas as you want. (The converse is also true. If you can devise a means of adding layers forever, then the shape tiles the plane. Perhaps surprisingly, the proof of this fact is much more subtle.)

Heesch’s problem

What’s less obvious is whether there’s anything in between 0 and . Is there some shape (for simplicity, let’s assume it’s a polygon) that can be surrounded by layers for some finite , but never more?

Heinrich Heesch first demonstrated a shape with Heesch number 1 in 1968. His shape was a convex pentagon, which can be seen as a square with an equilateral triangle glued to one side and a 30-60-90 triangle glued to another. It’s possible to surround this pentagon with copies of itself in a few distinct ways, but in no case can that first corona be further surrounded:

Note that any drawing of a corona doesn’t settle the question of the shape’s Heesch number! The corona could be surroundable, or perhaps a different corona could be. The diagram shows that the Heesch number is at least 1; you’d need a more thorough argument to know that it can’t be higher.

Since then, a few mathematicians and computer scientists have expanded what we know about Heesch numbers, in particular trying to find shapes that permit more coronas. But in nearly 50 years since 1968 we’ve gone from 1 to… 5. In his PhD dissertation, Casey Mann showed that the “5-hexapillar” has Heesch number 5, with a beautiful but somewhat daunting diagram of five coronas:

Today we refer to Heesch’s problem: for which finite does there exist a shape with Heesch number ? We can ask a whole host of related questions. Is there an upper bound on finite Heesch numbers? Are there positive integers that can’t be Heesch numbers? Are there limitations on Heesch numbers for specific classes of shapes, e.g., polyominoes?

At this point, it would be natural to ask: if non-trivial Heesch numbers are all about shapes that don’t tile the plane, then what do they have to do with tiling theory? Well, if you know something about a shape’s Heesch number, you also know whether it tiles. So let’s say that somebody managed to prove that no shape could ever have a Heesch number bigger than, say, 17. Suddenly, we have a nice algorithm to check whether a shape tiles: just surround it 18 times! Either you fail to reach 18 coronas, in which case you know the shape doesn’t tile, or you succeed, in which case the shape must tile, because you were told that every shape that didn’t tile reached at most 17 coronas. That would be a big deal, because at present we don’t know of any systematic way to check whether a single shape tiles the plane. I guess that there ought to be some relationship between “tiling theory” and “non-tiling theory”, after all.

For my part, I find the topic endlessly fascinating. A high finite Heesch number represents a kind of spooky action at a distance. How is it that we can “program” the boundary of a shape in order to determine—and limit—what happens five layers out? How can we get control over that behaviour in order to construct shapes with desired Heesch numbers? I find it amazing that the geometric structure of the plane allows us to play such wonderful games.

Armed with the definition of Heesch number, and a few simple examples, I’m ready to offer a few new discoveries in the posts to follow. I’ll need a small amount of additional terminology from tiling theory, which I’ll introduce as necessary. Next up, simple polyforms with non-trivial Heesch numbers.