Heesch's Problem

Heesch's Problem asks the following
question: How many times can a tile be surrounded by congruent copies of
itself? That is, how many *layers* made of copies of the tile can you
place around the tile. The layers are called *coronas*, and the
maximum number of coronas that can surround a tile is called the *Heesch
number* of the tile.

Here are some examples of tiles with Heesch number 1. The first one is by Heesch himself.

Heesch number 2 examples:

Heesch number 3 examples (The first one was discovered by Robert Ammann, and it was the record holder for a long time):

The proof that Amman's tile has Heesch number 3 is quite nice, and this proof stimulated some research on my part. The basic idea of the proof is to notice that each tile has 3 "innies" and 2 "outies" so each tile has an excess "charge". In any configuration of these tiles, the excess charge must appear on the boundary of the configuration. The area of the configuration is propotional to the amount of excess charge, and so grows on the order of a quadratic polynomial (area is quadratic). But, the number of edges on the boundary of a configuration, which is where the excess charges are stored, grows linearly (think circumference). Thus eventually there is not enough room on the boundary to put the excess charges. By simply counting in this example you can see that a fourth corona is impossible because the boundary of the fourth corona doesn't have enough edges to hold all of the innies that would have to be there.

I have extended this basic argument to other more complicated tiles made of hexagons. This work, which I won't go into here, actually predicts the following examples. This work should be submitted soon, though.

Heesch number 4 example (First discovered by W.R. Marshall, and then independently by me)

Heesch number 5 example (discovered by me):

This last example has the largest known finite
Heesch number. Of course, a prototile that can be used to tile the entire
plane has *infinite* Heesch number, but I am interested in those prototiles
that cannot be used to tile the plane.

Also, it has been customary in the past to require that the coronal configurations be simply connected (that is, there are no holes), but if we relax this condition, we see some can have even higher Heesch numbers. For example, several people have noticed that Ammann's example under the relaxed rules has Heesch number 4:

The Heesch number 5 example from above cannot, however, attain 6 coronas, even if we relax the simple connectivity requirement.

So the big question is this: Is there a maximum Heesch number? That is, is there some number N so that when any tile surrounds itself N times, then it must tile the plane? If so, what is N?

At present, there is not an answer to this question. It has been conjectured by well-known and talented people in the field of tiling theory that there is a maximum (although they cannot say what that maximum is). I have also heard it conjectured that there is no bound on the Heesch number! I am reluctant to make a conjecture myself. But I can say that after Ammann's example was given, many people thought that there would not be another example with higher Heesch number.

Heesch's problem has connections to a few
well-known unsolved problems -- the *domino problem* and the *"Einstein"
problem. *The domino problem asks if there exists an algorithm that,
when given a prototile as input, decides if the prototile can be used tile the
entire plane. If the Heesch number is in fact bounded, this gives a simple
algorithm for deciding if a prototile can be used to tile the plane:
Suppose the maximum Heesch number is N. One just places tiles in a
systematic fashion until either he cannot proceed any further, in which case the
prototile cannot be used to tile the plane, or until he has placed more than N
coronas of tiles, in which case the tile must tile the plane. The domino
problem in turn has a deep connection with the "Einstein"
problem. The Einstein problem asks if there exists a single aperiodic
prototile (Ein = one, stein = tile). The nonexistence of a single
aperiodic prototile implies the the existence of a decision method for the
domino problem.