A central objective of this project is the creation of an interactive (one player) game to explore properties of the hat tile . One can combine jigsaw-like hat tiles to larger and larger clusters. The game contains a few tools that help to analyse the structure of such cluster. First explorations with the HatGame were helpful to cut down the number of possible initial configurations and allowed to extend “The ten vertex theorem” of [1]. The hat tile is the first solution that has been found for the so-called “EinStein” problem, which was the search for one single shape (tile) that can fill the entire plane with only aperiodic patterns (tiling). A tiling is valid and aperiodic, when it has the following properties:
1.) It covers the entire plane without gaps or holes.
2.) There is no translation that maps the pattern onto itself, i.e. there are no translational symmetries.
Remark: A tile is an “EinStein” (an aperiodic mono-tile), when ALL its valid tilings are aperiodic.
1.) It covers the entire plane without gaps or holes.
2.) There is no translation that maps the pattern onto itself, i.e. there are no translational symmetries.
Remark: A tile is an “EinStein” (an aperiodic mono-tile), when ALL its valid tilings are aperiodic.
Hands-on the HatGame
Hands-on the HatGame
In[]:=
(*HatGame*)(*!!!Startthegamewiththisfunctioncall!!!*)
Before you dive into this community post, we recommend that you just try to create your own tiling. You do not need to purchase or print your own set of tiles. Just download this notebook and run the function HatGame.
Click on any of the patterns of tiles below the control panel as a possible starting configuration. When you click with the mouse at any vertex on the boundary of the initial pattern, the game will try to place another tile at the selected location. In general there will be more than one possibility to place the tile. These choices are managed inside the tree in the panel of the right hand side. You can click on any of the nodes to switch between choices.
Click on any of the patterns of tiles below the control panel as a possible starting configuration. When you click with the mouse at any vertex on the boundary of the initial pattern, the game will try to place another tile at the selected location. In general there will be more than one possibility to place the tile. These choices are managed inside the tree in the panel of the right hand side. You can click on any of the nodes to switch between choices.
A Tiny Overview
A Tiny Overview
Historical Hat Hunters
Historical Hat Hunters
To really appreciate the “glory” of the hat tile, we have to turn back time for a few decades. In 1961 Hao Wang investigated formal systems that could be represented by square tiles with colors.
Wang=
Out[]=
The rules of the systems could be restated by the question, whether these squares can be laid out in the plane obeying the rules that:
1.) neighbouring squares have to match with their adjacent colors.
2.) The resulting pattern of colors should be periodic.
1.) neighbouring squares have to match with their adjacent colors.
2.) The resulting pattern of colors should be periodic.
He stated the following conjecture: If a finite set of Wang tiles can tile the plane, then there exists a periodic tiling. Due to the finite amount of tiles and periodicity of the tiling it follows immediately that any periodic tessellation could in principle be confirmed by an algorithm, since it would only require a finite amount of steps.
Five years later his student Robert Berger showed that any Turing machine can be mapped into a set of Wang tiles. Consequently, it follows that any periodic tiling of the entire plane translates into a Turing machine that never stops, i.e. it would run forever. Since the halting problem is undecidable, there cannot exist an algorithm that decides whether a set of Wang tiles covers the entire plane periodically. Since there a finite set of Wang tiles that fill the plane, there is only one way to make the problem is undecidable. There must also exist aperiodic tilings!!!
Initially, Berger found a set of 20,426 Wang tiles that cover the plane only in an aperiodical way. In the course of the years, this number was steadily decreased. In 2015 Emmanuel Jeandel and Michael Rao found a set with only 11 tiles and 4 colors. They also showed that below these numbers aperiodicity cannot be enforced.
Instead of using different colors, the edges of the squares can be deformed uniquely. Now the color-replacing deformations have to match as shown in the figure:
Five years later his student Robert Berger showed that any Turing machine can be mapped into a set of Wang tiles. Consequently, it follows that any periodic tiling of the entire plane translates into a Turing machine that never stops, i.e. it would run forever. Since the halting problem is undecidable, there cannot exist an algorithm that decides whether a set of Wang tiles covers the entire plane periodically. Since there a finite set of Wang tiles that fill the plane, there is only one way to make the problem is undecidable. There must also exist aperiodic tilings!!!
Initially, Berger found a set of 20,426 Wang tiles that cover the plane only in an aperiodical way. In the course of the years, this number was steadily decreased. In 2015 Emmanuel Jeandel and Michael Rao found a set with only 11 tiles and 4 colors. They also showed that below these numbers aperiodicity cannot be enforced.
Instead of using different colors, the edges of the squares can be deformed uniquely. Now the color-replacing deformations have to match as shown in the figure:
Graphics,,,TranslationTransform[{0.05,0}]@,
Out[]=
Now the problem of smaller and smaller sets of Wang tiles translates into few and fewer different possibly more complicated shapes of tiles . The quest for the "EinStein" had begun. By the way, this phrase has no relation to the Albert Einstein. It is just a play of words. The words “ein Stein” translate from German into “one piece” or “one stone”, and obviously it is used synonymously for the one possible tile that can be used to fill the plane.
Aperiodic tilings made out of only two different shapes were found in 1975 by Roger Penrose . They marked a long lasting mile stone in the quest for the "Aperiodic Mono-Tile" . You might expect that the shape of these tiles needs to be bewilderingly peculiar . Well, there exists a Wolfram demonstration project to such Penrose tilings . If you have not seen them before, have a look there. Perhaps you will be surprised by the simple nature of these tiles and how they marvellously fit together creating a subtle glimpse of non-periodicity.
https://demonstrations.wolfram.com/PenroseTiles/
Aperiodic tilings made out of only two different shapes were found in 1975 by Roger Penrose . They marked a long lasting mile stone in the quest for the "Aperiodic Mono-Tile" . You might expect that the shape of these tiles needs to be bewilderingly peculiar . Well, there exists a Wolfram demonstration project to such Penrose tilings . If you have not seen them before, have a look there. Perhaps you will be surprised by the simple nature of these tiles and how they marvellously fit together creating a subtle glimpse of non-periodicity.
https://demonstrations.wolfram.com/PenroseTiles/
Finally, almost 50 years later and only a few months ago this quest has finally come to an end. Let me present to you the first discovered aperiodic mono-tile [4]:
Labeledshow,Axes->True,
Out[]=
The Hat Tile |
The hat tile was discovered by the hobby mathematician David Smith in 2022. It’s property of being an aperiodic mono-tile was proven only this year by a team of mathematicians [4].
You can leave your Hat on
You can leave your Hat on
Now that we have given a short story how the hat tile came into existence and why it is worth to think about it, let’s sketch how the HatGame can help to learn more about this special creature and the aperiodic tilings that it generates.
In the section Hello Hat
◼
we will have a closer look at the shape of the hat tile and break it into eight smaller pieces that are easier to cope with,
◼
we will introduce a short hand notation that lays out coordinates in the space of configurations of the hat tile,
◼
and we will give a brief summary about the algorithms that power the game.
In the section Lessons Learned
◼
we will explain how additional constraints and symmetries can be imposed on the space of possible configurations
◼
and we will also present a few methods that we applied on our journey through the hat tiles’ universe.
Hello Hat
Hello Hat
The Hidden Shape
The Hidden Shape
At first sight the shape of the hat tile might seem dizzyingly bizarre and a bit arbitrary. However, it is less random than you would expect from just looking at it. In fact it is made of eight congruent kites. These kites are uncovered, when the hat tile is covered with two sets of grid lines. The first set is a hexagonal grid that looks like a honeycomb. The second grid is obtained when all midpoints of the hexagons are connected by grid lines. These grid lines break down the hat tile into eight kites of alike shape.
Out[]=
For the sake of completeness, we also show a coordinate representation of the hat tile. You probably never want to work with these coordinates explicitly. And they are not really needed. The hat tiles in this notebook are always generated by a function. The input for this function is a set of numbers that store all pieces of information. The arguments capture, where the hat tile is located, how it is rotated and reflected. The last number of the “code” marks the pivot point among the set of vertices. This code is explained in the next section.
Showshow,Graphics,
Out[]=
Just in case that someone wants to know the coordinates of the 13 points, here they are.
A Convenient Code
A Convenient Code
Since we want to handle a large number of hat tiles conveniently inside Wolfram language, we somehow have to store the information of each tile as concisely as possible. There are three different pieces of information needed, the state of rotation, the state of reflection and the position of one of the hats vertices. These three pieces are collected inside a list of the form {pos, rotation, reflection, vertex}. The hat tile can only be rotated in steps of 30°, so rotations can be represented by integers from 0 to 11. There are only two states of reflection True or False. And finally, the vertices are labelled by integers through 0 to 12. Let’s have a look at tiles with the codes:
hat1={{0,0},0,False,0};hat2={{6,2},3,False,6};Showshow{hat1,hat2},,
Out[]=
The tile on the left hand side is in its “normal” form. The vertex 0 is placed at the origin, there is no rotation and no reflection. The second tile is rotated by 330° and the vertex with index 6 is selected to be the pivot point, located at the position provided by the first entry of the code.
How Hats fit Together
How Hats fit Together
If a person wants to build a large jigsaw out of hat tiles she or he just brings them close together and rotates them until they fit together. This all takes place under supervision of the person’s neural network formerly known as brain. The feedback is provided by an arcane sensory system heavily relying on the presence of electromagnetic radiation in a ridiculously small window of frequencies. In fact, during one of the dinner meetings we discussed the idea to simulate this process. One would have to build and train a neural network, which could eventually learn, similar to a game of chess, which local moves would pay off in the end and create a spacefilling tiling. But due to time constraints, we fell back to a more simple-minded and brute-force implementation that just computes the possible overlap between a tile and an existing cluster of tiles. We investigated a few methods, such as making use of triangulations or index theorems. But we always ran into trouble with vertices that were located on edges.
Last but not least we implemented a sophisticated polygon fragmentation algorithm that is partially described in [2]. In the tiling game, the user selects a vertex, where he or she wants to put the next tile. In a simple preselection process, all configurations of tiles are collected that match with the boundary of the cluster to cover all 360°. These configurations are checked with the polygon fragmentation algorithm and the results are shown in the following table.
Last but not least we implemented a sophisticated polygon fragmentation algorithm that is partially described in [2]. In the tiling game, the user selects a vertex, where he or she wants to put the next tile. In a simple preselection process, all configurations of tiles are collected that match with the boundary of the cluster to cover all 360°. These configurations are checked with the polygon fragmentation algorithm and the results are shown in the following table.
cluster=Polygon;(*index=19;(*indexofthepointofthecluster,wherethehattileisgoingtobeadded*)locations=Sort[Mod[findOpenLocs[cluster,index],12]];cases=Flatten[Outer[{cluster[[1,index]],#1,#2,#3}&,Range[0,11],{True,False},Keys[Length[locations]/.openLocationsAngleMap],1],2];reduced=cases[[Flatten[Position[HatAnglesCovered@@@(Rest[#]&/@cases),locations]]]];candidates=Tiles@@@reduced;result=PlanarPolygonFragmentation[cluster,#]&/@candidates;//AbsoluteTiming*)
Out[]=
{0.474713,Null}
This is a part of the function GrowTiling, which is invoked, whenever the user wants to add another hat. The heart of the game is calling the PlanarPolygonFragmentation function, developed and kindly provided by Brad Klee. It reliably detects overlapping hat tiles and selects admissible rotations and reflections, even when vertices of the new tile and cluster only meet at the edges. It involves the solution of many intersection problems and is therefore rather expensive. To compensate this inconvenience a preselection is performed. First the range of angles is determined that is not covered by the cluster at the selected vertex point (19 in our example). The open angles are stored in the list location ({6,7,8,9}}.
With
Out[]=
Let us see, how the algorithm works for this particular example.The hat tile covers interior angles of 120° at five different vertices {1, 3, 5, 11, 12}. Combined with 12 possible rotations and 2 reflections, this leads to a total of 120 possible states that are collected in the list cases. But only 10 of them match with the open angles {6, 7, 8, 9}. From these matches stored in the list named “reduce” finally the polygons are constructed. This list of polygons named “candidates” is one by one fed into the PlanarPolygonFragmentation function. From the 10 results a selection is shown in the table below.
This table shows a selection of cases that are investigated at a particular point (highlighted in orange) by the action of the PlanarPolyFragmentation function. We are looking for the situation, when there is no intersection. These cases are colored in green. It is also a good place for a warning. When you want to explore tilings exhaustively with the HatGame, you must not select the vertices {11, 13, 9, 8, 5 ,2, 28, ...}. At these vertices two more tiles can be placed and this possibility is not taken into account by this version of the HatGame. Make sure that you only select vertices, where the cluster covers 120° more than 180°.
Lessons Learned (while playing the HatGame)
Lessons Learned (while playing the HatGame)
Local No-Gos
Local No-Gos
Although hat tiles may perfectly fit together locally, there is no guarantee that one is able to continue the tiling in a way that the full plane will be covered eventually. Therefore it is important to find additional local constraints that have to be fulfilled in every valid tessellation. Let’s just focus on vertex combinations with three hat tiles. The color codes for the 10 possible configurations have been taken from [1]. The numbers in the labels are the collection of vertex indices. Each of them corresponds to a different hat.
At the common point of intersection, the red and green tile meet with their vertex with the label 11. Whereas the blue tile is located with the vertex 12 at the intersection point.
If you investigate, which of these combinations actually occur in valid tilings, as they can for instance be generated with the resource functions in [3], only the first eight of them can be found. With the tiling game it is now possible to proof that the last two vertex combinations (11-11-11) and (5-5-5) do not lead to tilings that can be extended to infinity.
Let’s start with the (11-11-11) vertex combination. The concave regions are uniquely filled with the reflected version of the hat tile.
There are a few degrees of freedom for the next tile. However, after a few more tiles every of the first possible choices will lead to a dead end, meaning that the tiling cannot be completed to cover the entire Euclidean plane. The following graph captures the exhaustive search of all possible tilings.
This graph illustrates that the locally valid combination (11-11-11) of initial tiles cannot be completed to a valid tiling that covers the full two dimensional plane. Up to the fourth level the continuation of the tiling is unique. The fifth row includes all possible choices that can be made on the top of the tiling at the parent node. In the rest of the graph it is shown that each of the possible choices will eventually lead to a dead end.
Unfortunately, this process cannot be applied as easily for the (5-5-5) vertex combination. It turns out that this vertex combination can be grown consistently to a very large cluster size. Therefore, some additional simplifications have to be utilized. We can observe that the initial pattern exhibits rotational symmetry. Consequently, any generated non-symmetric pattern will occur three times always rotated by 120°.
The tree shows the growth of the initial vertex configuration (5-5-5) after two hat tiles have been added.
Let’s focus on the patterns in the last row. It’s not so easy to spot but the fourth and the fifth pattern are rotationally symmetric. The first, fifth and the seventh are related by rotation of 120° or 240° and similar relations hold for the second, third and eighth pattern. Don’t be distracted by the cyan color of the most recent tile. If you imagine it gray the second and the third are actually rotationally symmetric. Everything that is observed on the second branch will be observed on the third branch only rotated by 120°. Without loss of generality the branches of these related patterns can be combined into one branch. This cuts the amount of book-keeping to half.
Reduce the space of configurations by exploiting symmetries. The common shape always displays the configuration of the last branch. To make the symmetry more apparent, the information about the latest hat is made invisible. Out of eight possible configurations only four of them have to be investigated. The remaining ones are related by rotational symmetry. In what follows, each of the cases will be explored independently, denoted in the order of their appearance in the last row as case I, II, III and IV.
Let us start with the symmetric cases . The information of every configuration is stored in the global association graphData . Each case can be investigated separately. One only has to reset the {{0}} state of this association with the state that one wants to take a closer look at.
◼
Case III:
After a few tiles, a dead end is reached for the first of the symmetric cases. The large concave region cannot be filled.
◼
Case IV:
Although it is grown much further than the configuration of case III, also this symmetric tiling reaches a dead end at the positions indicated by the arrows and it therefore cannot give rise to an aperiodic tiling of the plane .
◼
Case II:
This case quickly runs into trouble and all possible combinations are readily exhausted. You might argue that it is possible to continue the tiling in a lot of places and of course you are right. But the important point is, that each configuration contains at least one area, where the tiling cannot be continued into. This is all we need since after all we are interested in tiling that can grow everywhere without holes or gaps.
◼
Case I:
Now the fate of the vertex combination (5-5-5) seems to be almost sealed and it looks like a trivial exercise to deliver the death blow. However for a short period of time, we have had a glimpse of hope that there was something exciting to discover. The tiling could be grown consistently and more importantly uniquely turning into a rotationally symmetric tilling. The pieces fell so nicely into place that it was really a big disappointment, when suddenly the intricately woven tissue was torn apart at two places. Well, c’est la vie, and this is especially true for mathematics. You cannot count on something to be persistent or even eternal, when you have just watched it for a brief period of time. When you want to talk about infinity, you have to aim for hidden structures. You have to explore patterns and you have to find rules that can be applied infinitely often as it is presented in the analyses of [4] and [3].
This configuration can be rotated by 180° around the central (2-2-8-8) vertex combination. It is the largest configuration that is uniquely. For any further tiles there are at least two choices.
Is the hat tiling unique?
Is the hat tiling unique?
The energy that we spent to disprove the appearance of the (5-5-5) and (11-11-11) vertex configurations was well invested. We can now use these results to reduce the number of possible branches, when the tilings are built from valid start configurations. My first choice for this quest is the vertex configuration (3-3-3) with the hope that the symmetry might help again to reduce the number of branches even further. Since everybody is now familiar with the procedure, only a schematic version of the tree graph is plotted.
The last states correspond the the following configurations:
As before, each of the four cases should be investigated separately. The results can be summarized as follows. Unfortunately, even for the symmetric cases there is usually more than one possibility at each step of the tiling. Many of these branches do not lead to dead-ends even after a considerable amount of steps. This makes an exhaustive investigation of the hat tiling at this point impossible. It also indicates that the number of different possible tilings increases with the size of the existing patch. This growing space of possibilities may reflect the aperiodic nature and the fractal-like behavior of the hat tilings. The larger the size of the cluster the more intricate details have to be generated as you continue.
Concluding remarks
Concluding remarks
This project to this post was carried out during the three weeks of Wolfram summer school 2023. The notes are sketchy and the content always has to be read with a healthy amount of scepticism. It would have been good, if there had been more time for a more thorough exploration. But taking into account that the author of this post never had seriously been engaged with any sort of tilings before, the achievements of the three week’s boot camp seem quite reasonable. Nevertheless, many statements are a bit vague and they are far from being rigorous results. If you, dear reader, find time to do some explorations on your own, you are invited to do so. Do not hesitate to restate things that we have said as replies to this post.
The graphical user interface that we provide with this blog post can be viewed as a tool to become familiar with the geometric structure of the hat tile and to get a basic feeling how to start tilings. We could use it to “proof” that certain vertex combinations that are allowed locally, will eventually lead to inconsistencies.
For a systematic bottom up study of hat tilings improved tools are required. Due to the growing amount of branches, an automatic search combined with a backtracking algorithm and a fast intersection test seems required. Bowen has developed algorithms that can automatically grow tilings. His results are shown here: https://community.wolfram.com/groups/-/m/t/2957268 .
The graphical user interface that we provide with this blog post can be viewed as a tool to become familiar with the geometric structure of the hat tile and to get a basic feeling how to start tilings. We could use it to “proof” that certain vertex combinations that are allowed locally, will eventually lead to inconsistencies.
For a systematic bottom up study of hat tilings improved tools are required. Due to the growing amount of branches, an automatic search combined with a backtracking algorithm and a fast intersection test seems required. Bowen has developed algorithms that can automatically grow tilings. His results are shown here: https://community.wolfram.com/groups/-/m/t/2957268 .
Keywords
Keywords
◼
Hat tile
◼
Aperiodic tilings
Acknowledgment
Acknowledgment
The foundation for this project was created by Brad Klee, who developed the functionality to investigate intersections of polygons. As our Mentor he was heavily engaged in formulating the objectives, he supervised the development and progress of this project. He provided the key to unlock the door to this mathematical wonderland. He created a very pleasant, constructive and interactive atmosphere in our small research group also consisting of Ben, Bowen, Russel and Zsombor. Vivid discussions, joint task forces and some relaxing games were inspiring and rewarding.
This project is closely related to Bowen’s project https://community.wolfram.com/groups/-/m/t/2957268. To some extent we raced side by side trying to uncover the hidden treasures of the hat tile. His help frequently saved me from despair. Very helpful support I also received from Mark Greenberg, Bob Nachbar and Eric Parfitt, who patiently tracked down any problems with convoluted lists, graphs and associations.
This project can also be viewed as a first step towards addressing the problem 158: Aperiodic Tilings as Multiway Aggregation Systems from Stephen Wolfram’s list of problems.
Last but not least I want to thank all of the organizers and participants, who turned this summer school for me into a stimulating, incredibly exciting and unforgettable experience.
This project is closely related to Bowen’s project https://community.wolfram.com/groups/-/m/t/2957268. To some extent we raced side by side trying to uncover the hidden treasures of the hat tile. His help frequently saved me from despair. Very helpful support I also received from Mark Greenberg, Bob Nachbar and Eric Parfitt, who patiently tracked down any problems with convoluted lists, graphs and associations.
This project can also be viewed as a first step towards addressing the problem 158: Aperiodic Tilings as Multiway Aggregation Systems from Stephen Wolfram’s list of problems.
Last but not least I want to thank all of the organizers and participants, who turned this summer school for me into a stimulating, incredibly exciting and unforgettable experience.
References
References
1
.Brad Klee, Hat combinatorics: the ten vertex theorem,
https://community.wolfram.com/groups/-/m/t/2935078, Wolfram Community, STAFF PICKS, June 12 2023
https://community.wolfram.com/groups/-/m/t/2935078, Wolfram Community, STAFF PICKS, June 12 2023
2
.Brad Klee, Checking a dodecagon mistake at OEIS,
https://community.wolfram.com/groups/-/m/t/2932082, Wolfram Community, STAFF PICKS, June 8, 2023
https://community.wolfram.com/groups/-/m/t/2932082, Wolfram Community, STAFF PICKS, June 8, 2023
3
.Brad Klee, Hat triality tree, https://resources.wolframcloud.com/FunctionRepository/resources/HatTrialityTree/, Apri 10, 2023
4
.David Smith, Joseph Samuel Myers, Craig S. Kaplan and Chaim Goodman-Strauss, An Aperiodic Monotile, arxiv preprint, March 20, 2023.
5
.Joshua E. S. Socolar, Quasicrystalline structure of the Smith monotile tilings, arxiv preprint, May 8, 2023
Libraries
Libraries
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
HatGame: a journey through the hat tile configuration space
by Johannes Martin
Wolfram Community, STAFF PICKS, July 12, 2023
https://community.wolfram.com/groups/-/m/t/2958428
by Johannes Martin
Wolfram Community, STAFF PICKS, July 12, 2023
https://community.wolfram.com/groups/-/m/t/2958428