I enjoy math problems that are easy to understand but challenging to solve. These problems are often related to various topics and are deep enough for people with diverse backgrounds to engage with and make progress. When I was a child, I grew up in Isfahan, a city with numerous tiled monuments. I used to enjoy sketching tilings in my notebooks when I wasn’t paying attention in class. I would like to introduce a tiling problem here.
A tiling is a way to put some tiles (polygons) in a 2d plane that no two tiles interleave and the whole plane is covered. For example a grid is a tiling of a square tile. If you move the grid one block to the left or up, you end up with the same tiling. Look at the image below1.
We call a tiling periodic, if moving the tiling over 2 non parallel vectors repeats the tiling. There are some tiles that it is possible to tile them in two different ways.
If for a tile there is only one tiling possible, then we call that tile monomorphic. If for a tile set there are only non-periodic tilings then we call that tile set aperiodic.
You may wonder how we can create an aperiodic tile set by now. Is it possible? Pick up a pen and take your time.
The answer is Yes! The first aperiodic tile set was constructed by Robert Berger in 1966 and used 20,426 tiles. Can we make the set smaller? What is the lower bound of the tiles needed for an aperiodic tile set? Robinson found an aperiodic tile set consisting of 6 tiles in 1971.
Roger Penrose with the famous Penrose tiling that is aperiodic and contains only two tiles in late 70s. Play with Penrose tiling here. Proof of aperiodic property of Penrose tiling is quite interesting.
Now that we have a periodic tilings with one tile:
Is it possible to create an aperiodic tiling with only one tile?
tackled this problem a few times in the last year before my thesis defense. Not that I was aiming for a solution, but it was interesting to me. Today, out of nowhere, I remembered the problem and wanted to give it another shot. I noticed that David Smith introduced an aperiodic mono-tile in March 2023! It felt good to see progress, and that was the reason I wrote this post.
Relation of aperiodic tiling problem with domino problem is also quite fascinating.
The first specific occurrence of aperiodic tilings arose in 1961, when logician Hao Wang tried to determine whether the domino problem is decidable – that is, whether there exists an algorithm for deciding if a given finite set of prototiles admits a tiling of the plane. Wang found algorithms to enumerate the tilesets that cannot tile the plane, and the tilesets that tile it periodically; by this he showed that such a decision algorithm exists if every finite set of prototiles that admits a tiling of the plane also admits a periodic tiling.
From Wikipedia page of Aperiodic tiling