We have been exploring properties of Penrose’s aperiodic tilings with kites and darts using Haskell.
Previously in Diagrams for Penrose tiles we implemented tools to draw finite tilings using Haskell diagrams. There we also noted that legal tilings are only correct tilings if they can be continued infinitely and are incorrect otherwise. In Graphs, Kites and Darts we introduced a graph representation for finite tilings (Tgraphs) which enabled us to implement operations that use neighbouring tile information. In particular we implemented a
force operation to extend a Tgraph on any boundary edge where there is a unique choice for adding a tile.
In this note we find a limitation of
force, show a way to improve on it (
superForce), and introduce boundary coverings which are used to implement
superForce and calculate empires.
Properties of Tgraphs
A Tgraph is a collection of half-tile faces representing a legal tiling and a half-tile face is either an
LD (left dart) ,
RD (right dart),
LK (left kite), or
RK (right kite) each with 3 vertices to form a triangle. Faces of the Tgraph which are not half-tile faces are considered external regions and those edges round the external regions are the boundary edges of the Tgraph. The half-tile faces in a Tgraph are required to be connected and locally tile-connected which means that there are exactly two boundary edges at any boundary vertex (no crossing boundaries).
As an example Tgraph we show
kingGraph (the three darts and two kites round a king vertex), where
kingGraph = makeTgraph [LD (1,2,3),RD (1,11,2),LD (1,4,5),RD (1,3,4),LD (1,10,11) ,RD (1,9,10),LK (9,1,7),RK (9,7,8),RK (5,7,1),LK (5,6,7) ]
This is drawn in figure 1 using
hsep 1 [dashJVGraph kingGraph, drawGraph kingGraph]
which shows vertex labels and dashed join edges (left) and without labels and join edges (right). (
hsep 1 provides a horizontal seperator of unit length.)
Properties of forcing
We know there are at most two legal possibilities for adding a half-tile on a boundary edge of a Tgraph. If there are zero legal possibilities for adding a half-tile to some boundary edge, we have a stuck tiling/incorrect Tgraph.
Forcing deals with all cases where there is exactly one legal possibility for extending on a boundary edge. That means forcing either fails at some stage with a stuck Tgraph (indicating the starting Tgraph was incorrect) or it enlarges the starting Tgraph until every boundary edge has exactly two legal possibilities for adding a half-tile so a choice would need to be made to grow the Tgraph any further.
Figure 2 shows
force kingGraph with
kingGraph shown red.
g is a correct Tgraph, then
force g succeeds and the resulting Tgraph will be common to all infinite tilings that extend the finite tiling represented by
g. However, we will see that
force g is not a greatest lower bound of (infinite) tilings that extend
g. Firstly, what is common to all extensions of
g may not be a connected collection of tiles. This leads to the concept of empires which we discuss later. Secondly, even if we only consider the connected common region containing g, we will see that we need to go beyond
force g to find this, leading to an operation we call
superForce operations are implemented using boundary coverings which we introduce next.
Boundary edge covering
Given a successfully forced Tgraph
fg, a boundary edge covering of
fg is a list of successfully forced extensions of
fg such that
- no boundary edge of
fgremains on the boundary in each extension, and
- the list takes into account all legal choices for extending on each boundary edge of
[Technically this is a covering of the choices round the boundary, but each extension is also a cover of the boundary edges.] Figure 3 shows a boundary edge covering for a forced
force kingGraph is shown red in each extension).
In practice, we do not need to explore both choices for every boundary edge of
fg. When one choice is made, it may force choices for other boundary edges, reducing the number of boundary edges we need to consider further.
The main function is
boundaryECovering working on a
BoundaryState (which is a Tgraph with extra boundary information). It uses
covers which works on a list of extensions each paired with the remaining set of the original boundary edges not yet covered. (Initially
covers is given a singleton list with the starting boundary state and the full set of boundary edges to be covered.) For each extension in the list, if its uncovered set is empty, that extension is a completed cover. Otherwise
covers replaces the extension with further extensions. It picks the (lowest numbered) boundary edge in the uncovered set, tries extending with a half-dart and with a half-kite on that edge, forcing in each case, then pairs each result with its set of remaining uncovered boundary edges before adding the resulting extensions back at the front of the list to be processed again. If one of the choices for a dart/kite leads to an incorrect tiling (a stuck tiling) when forced, that choice is dropped (provided the other choice succeeds). The final list returned consists of all the completed covers.
boundaryECovering:: BoundaryState -> [BoundaryState] boundaryECovering bs = covers [(bs, Set.fromList (boundary bs))] covers:: [(BoundaryState, Set.Set Dedge)] -> [BoundaryState] covers  =  covers ((bs,es):opens) | Set.null es = bs:covers opens -- bs is complete | otherwise = covers (newcases ++ opens) where (de,des) = Set.deleteFindMin es newcases = fmap (\b -> (b, commonBdry des b)) (atLeastOne $ tryDartAndKite bs de)
Here we have used
type Try a = Either String a tryDartAndKite:: BoundaryState -> Dedge -> [Try BoundaryState] atLeastOne :: [Try a] -> [a]
We frequently use
Try as a type for results of partial functions where we need to continue computation if there is a failure. For example we have a version of
tryForce) that returns a
Try Tgraph so it does not fail by raising an error, but returns a result indicating either an explicit failure situation or a successful result with a final forced Tgraph. The function
tryDartAndKite tries adding an appropriate half-dart and half-kite on a given boundary edge, then uses
tryForceBoundary (a variant of
tryForce which works with boundary states) on each result and returns a list of
Try results. The list of
Try results is converted with
atLeastOne which collects the successful results but will raise an error when there are no successful results.
Boundary vertex covering
You may notice in figure 3 that the top right cover still has boundary vertices of
kingGraph on the final boundary. We use a boundary vertex covering rather than a boundary edge covering if we want to exclude these cases. This involves picking a boundary edge that includes such a vertex and continuing the process of growing possible extensions until no boundary vertices of the original remain on the boundary.
A partial example of an empire was shown in a 1977 article by Martin Gardner 1. The full empire of a finite tiling would consist of the common faces of all the infinite extensions of the tiling. This will include at least the force of the tiling but it is not obviously finite. Here we confine ourselves to the empire in finite local regions.
For example, we can calculate a local empire for a given Tgraph
g by finding the common faces of all the extensions in a boundary vertex covering of
force g (which we call
This requires an efficient way to compare Tgraphs. We have implemented guided intersection and guided union operations which, when given a common edge starting point for two Tgraphs, proceed to compare the Tgraphs face by face and produce an appropriate relabelling of the second Tgraph to match the first Tgraph only in the overlap where they agree. These operations may also use geometric positioning information to deal with cases where the overlap is not just a single connected region. From these we can return a union as a single Tgraph when it exists, and an intersection as a list of common faces. Since the (guided) intersection of Tgraphs (the common faces) may not be connected, we do not have a resulting Tgraph. However we can arbitrarily pick one of the argument Tgraphs and emphasise which are the common faces in this example Tgraph.
Figure 4 (left) shows
empire1 kingGraph where the starting
kingGraph is shown in red. The grey-filled faces are the common faces from a boundary vertex covering. We can see that these are not all connected and that the
force kingGraph from figure 2 corresponds to the connected set of grey-filled faces around and including the
kingGraph in figure 4.
We call this a level 1 empire because we only explored out as far as the first boundary covering. We could instead, find further boundary coverings for each of the extensions in a boundary covering. This grows larger extensions in which to find common faces. On the right of figure 4 is a level 2 empire (
empire2 kingGraph) which finds the intersection of the combined boundary edge coverings of each extension in a boundary edge covering of
force kingGraph. Obviously this process could be continued further but, in practice, it is too inefficient to go much further.
We might hope that (when not discovering an incorrect tiling),
force g produces the maximal connected component containing
g of the common faces of all infinite extensions of
g. This is true for the
kingGraph as noted in figure 4. However, this is not the case in general.
The problem is that forcing will not discover if one of the two legal choices for extending a resulting boundary edge always leads to an incorrect Tgraph. In such a situation, the other choice would be common to all infinite extensions.
We can use a boundary edge covering to reveal such cases, leading us to a
superForce operation. For example, figure 5 shows a boundary edge covering for the forced Tgraph shown in red.
This example is particularly interesting because in every case, the leftmost end of the red forced Tgraph has a dart immediately extending it. Why is there no case extending one of the leftmost two red edges with a half-kite? The fact that such cases are missing from the boundary edge covering suggests they are not possible. Indeed we can check this by adding a half-kite to one of the edges and trying to force. This leads to a failure showing that we have an incorrect tiling. Figure 6 illustrates the Tgraph at the point that it is discovered to be stuck (at the bottom left) by forcing.
superForce operation starts by forcing a Tgraph. After a successful force, it creates a boundary edge covering for the forced Tgraph and checks to see if there is any boundary edge of the forced Tgraph for which each cover has the same choice. If so, that choice is made to extend the forced Tgraph and the process is repeated by applying
superForce to the result. Otherwise, just the result of forcing is returned.
Figure 7 shows a chain of examples (rockets) where
superForce has been used. In each case, the starting Tgraph is shown red, the additional faces added by forcing are shown black, and any further extension produced by
superForce is shown in blue.
We still do not know if forcing decides that a Tgraph is correct/incorrect. Can we conclude that if
force g succeeds then
force g) are correct? We found examples (rockets in figure 7) where force succeeds but one of the 2 legal choices for extending on a boundary edge leads to an incorrect Tgraph. If we find an example
force g succeeds but both legal choices on a boundary edge lead to incorrect Tgraphs we will have a counter-example. If such a
g exists then
superForce g will raise an error. [The calculation of a boundary edge covering will call
atLeastOne where both branches have led to failure for extending on an edge.]
This means that when
superForce succeeds every resulting boundary edge has two legal extensions, neither of which will get stuck when forced.
I would like to thank Stephen Huggett who suggested the idea of using graphs to represent tilings and who is working with me on proof problems relating to the kite and dart tilings.
Reference  Martin Gardner (1977) MATHEMATICAL GAMES. Scientific American, 236(1), (pages 110 to 121). http://www.jstor.org/stable/24953856