Two important discoveries by amateurs have helped combinatorial mathematics achieve a key breakthrough

In March 2023, a small team of professional mathematicians and enthusiasts published an important work in which they found a "hat" figure that can solve the "Einstein problem" in the field of plane tessellation. Just three months later, they went a step further and found non-periodic tessellation figures based on the hat that do not require mirror symmetry. And these amazing discoveries started with an amateur math enthusiast.

Written by | Jiawei

“It was hiding in plain sight.”

—Doris Schattschneider, Professor Emeritus of Mathematics, Moravian University, Pennsylvania

In mid-November 2022, retired printing technician David Smith had plenty of time to do one of his favorite things: tinkering with and designing jigsaw puzzle pieces.

Using a software package called PolyForm Puzzle Solver, he constructed a seemingly insignificant tile (paving block) in the shape of a hat to see if he could cover a flat surface with only tiles of this shape, without leaving gaps or overlaps.

“I noticed it produced a mosaic effect that I had never seen before,” he said. “It’s a tricky little tile.”

He described his work to his friend and like-minded computer scientist Craig Kaplan of the University of Waterloo in Canada, who realized something was possible. Smith and Kaplan then invited two other researchers to join their team: mathematician Chaim Goodman-Strauss of the National Museum of Mathematics and the University of Arkansas, and software engineer Joseph Samuel Myers of Cambridge, England.

Myers, who holds a Ph.D. in combinatorial mathematics, immediately devoted all his spare time to the analysis of the hat-shaped tiles and provided the key proof in just over a week. Kaplan said: "We were all shocked to see how quickly he got everything done."

On March 20, 2023, the four-member team officially announced to the mathematical community that they had found a solution to the so-called "Einstein problem": the hat-shaped tiles discovered by Smith, as well as the tile family generated by the continuous transformation of the hat-shaped tiles (excluding a few exceptions), are all single-shaped tiles that can be non-periodically tiled on the entire plane. [Why it is called the "Einstein" problem, please see below.]

Use "hats" to non-periodically tessellate the entire plane. 丨Image source: @[email protected]

The entire mathematical community was shocked. You know, in the past half century, mathematicians have not been able to find a single-shaped tile that can be non-periodically tiled on the entire plane. As a result, Smith and others found infinite sets of tiles in less than half a year.

What is also puzzling to the mathematical community is that the hat-shaped tile that served as the starting point of their research was actually such an ordinary thirteen-gon.

Hat-shaped tiles | Image source: @[email protected]

Moreover, including the four people mentioned above who made important discoveries, no one could have imagined at the time that just two months later, they would shock the mathematical world again.
Non-periodic tessellation and Einstein's problem

Tiling, generally translated as paving, tiling or tiling, is a large branch in the field of combinatorial mathematics. The general idea is to use certain shape units to cover a certain geometric area without gaps and overlaps - it can be a plane or a space; but for the latter, the units used for tiling have changed from two-dimensional tiles to three-dimensional or higher-dimensional "building blocks".

For example, we can "simply" tile a two-dimensional plane with unit square tiles. Of course, it is unrealistic to do it in practice, but mathematical thinking gives us a free possibility, allowing us to rationally realize that although the process of achieving it takes infinite time, tiling the entire two-dimensional plane with unit square tiles is essentially simple. Similarly, a straight line is a line segment extending infinitely in two directions, and we can indeed grasp the concept of a straight line involving infinity and use it as the basis of plane geometry.

If we think about it a little more, we can also find that regular hexagons can also tiling the plane. Similarly, regular triangles can also tiling. The following tiling is the simplest and most obvious example of periodic tiling.

Periodic paving pattern of regular hexagonal tiles | Source: Internet

The Einstein problem we are going to introduce belongs to aperiodic tiling, which is usually translated as "non-periodic tiling". The so-called "non-periodic tiling" means that the set of tiles used must be tiled while ensuring that the mosaic pattern is not periodic. Obviously, square and regular hexagonal tiles can only tile the plane periodically, but not non-periodic tiling. It is also easy to think intuitively that those tiles that can tile the plane non-periodically should have asymmetric characteristics, such as the hat-shaped tiles mentioned above. It should be noted here that the meaning of the pattern not being periodic is that after the shape of the tiles used is determined, no matter how they are matched, combined, or designed, they can never produce a global periodic pattern. This is called non-periodic tiling, and many tilings (tiles) are both periodic and non-periodic. Therefore, we can translate aperiodic tiling into "essentially non-periodic tiling", that is, tiling without any periodicity. Unless otherwise specified, the "non-periodic tiling" mentioned below refers to "essentially non-periodic tiling".

The reason why mathematicians have made such a strict definition of non-periodicity is, firstly, to exclude some geometric structures that are too mundane and boring, and secondly, it is related to the historical origin of non-periodic tiling. The first mathematician in history to systematically study non-periodic tiling was the outstanding Chinese mathematical logician Wang Hao.

While studying Turing computable functions, Wang Hao discovered that a certain decidability proposition is closely related to non-periodic tiling. He once tried to prove the following conjecture: if there is a non-periodic tiling (in the general sense) for a certain type of tile, then there must also be a periodic tiling.

But soon after, Wang Hao's student Robert Berger constructed a counterexample. He used 20,426 different tiles to construct an essentially non-periodic tiling - no matter how it was rearranged, no periodic structure would appear. Since then, mathematicians have continued to pay attention to essentially non-periodic tiling. The mathematical community is eager to understand whether it is possible to construct non-periodic tilings with a smaller number of tile sets.

Later people managed to reduce the number 20,426 to a set of 92 tiles, then 6, and finally 2, the famous Penrose tiles, after Roger Penrose, a future Nobel Prize winner in physics.

The last major discovery of essential non-periodic tiling dates back to 1974, when mathematician Roger Penrose discovered the Penrose rhombus tiling: a kite (light yellow) and a dart (red). Technical details: A small change is needed to avoid the formation of the rhombus on the right (congruent rhombuses can of course periodically cover the plane) to meet the definition of essential "non-periodic tiling". 丨Image source:
https://math.berkeley.edu/~kpmann/penrose%20reading.pdf

So, is it possible to reduce the number to 1?

This is the famous Einstein problem: Is there a single shape of tile that can be used to tile the entire plane non-periodically?

The Einstein here has nothing to do with the famous physicist. It is simply a pun by the German geometer Ludwig Danzer: in German, "ein stein" means "a piece of stone."

Now back to the beginning of the story, at the end of March 2023, David Smith, Joseph Samuel Myers, Craig S. Kaplan and Chaim Goodman-Strauss put an end to the Einstein problem.

But the story doesn’t end there.

Art, inspiration and the final piece of the puzzle

In fact, when Smith et al. used hat-shaped tiles for non-periodic tiling, they needed to use hat-shaped mirror-symmetric tiles. In the current context, we assume that two mirror-symmetric tiles are tiles of the same type and shape.

All the tiles above have the same shape (they are all so-called hats). However, some structure can be revealed by coloring: the dark blue tile is mirror-symmetrical to the other tiles. Each dark blue tile is surrounded by three other light blue tiles in the same way. 丨Image source: @[email protected]

Just like the left and right hands are mirror-symmetrical, and cannot be rotated and translated to make the left and right hands overlap, two mirror-symmetrical tiles cannot be transformed into each other through rotation and translation. In this case, can they really be called "single" tiles?

After the mathematical community generally recognized the results of Smith and others, a new question immediately surfaced: Is it possible to find tiles of a truly single shape that can be non-periodicly tiled without the help of mirror symmetry, only through rotation and translation?

At the time, everyone thought that this follow-up problem would be extremely difficult, and no one expected a breakthrough in the near future. No one could have imagined that the answer was right under everyone's noses...

In the early morning of May 30, 2023 Beijing time, David Smith, Joseph Samuel Myers and four others published a 23-page new paper Achiral aperiodic monotile (the previous paper on "hat" shaped tiles was 89 pages long), announcing that they had found the final answer.

They found tiles of a true single shape that can be non-periodically tiled by rotation and translation alone, without the aid of mirror symmetry. They named it "Spectre".

The magical and simple ghost tile is a strictly chiral non-periodic simplex, that is, it can only be tiled with non-repeating patterns by translation and rotation; even if you want to use mirror-reflected tiles, you can't use them. 丨Image source: @[email protected]

After uploading the paper, Kaplan was still not satisfied and excitedly shared a lot of details of their latest work on the mathematics online community mathstodon, including sources of inspiration, ways of thinking, proof ideas, etc.

As mentioned earlier, what they discovered was not a single tile simplex that satisfies Einstein’s problem, but an infinite set of tiles, all of which are polygonal tiles that satisfy Einstein’s problem. After constructing a hat that satisfies the conditions, they then subtly adjusted the edges of the hat to generate similar shapes that also satisfy the conditions.

Kaplan et al. found that under certain rules, the shapes of these polygonal tiles can actually be uniquely determined by the lengths of two of their sides. They therefore used Tile (a, b) to represent these polygons, where a and b are the values ​​of specific side lengths.

According to this notation, the hat is Tile (1, √3). In addition, Tile (√3, 1) is also a very popular configuration, and it has a popular name - turtle (referring to its intuitive appearance). Turtles can also achieve non-periodic tiling. For Tile (a, b), when a and b vary continuously within a certain range, the resulting tile configuration is always non-periodic tiling.

On the other hand, it can be shown that the polygon Tile (1, 1) with equal sides is a notable exception to the previous construction of hat-like tiles (using mirror-symmetric tiles), and it is not essentially aperiodic.

But the above knowledge alone is not enough to bring about a breakthrough. The inspiration for a breakthrough comes from completely unexpected artistic fields.

Yoshiaki Araki, a Japanese mosaic artist and graphic and three-dimensional installation designer, is very interested in tile mosaics and tessellation patterns derived from the hat series. He shared a demo program that shows the tiling effect of Tile (1, 1.01).

Although David Smith, one of the four members of the team, had no background in mathematics work or education, he had an exceptionally good intuition about geometric puzzles (don’t forget that it was he who first came up with the hat shape). When he saw Yoshiaki Araki’s demonstration program, he keenly realized that Tile (1, 1) might have properties that could be further explored.

Once they found the right direction, everything seemed to become clear. They discovered that the final answer was right at their fingertips: if only translation and rotation were allowed to be used to lay tiles, then Tile (1, 1) could be non-periodic and densely tiled!

The reason why Tile (1, 1) was not successful at first was that they put it in a configuration that allowed mirror symmetry, which is the same as the hat shape. If you restrict the use of mirror symmetric Tile (1, 1), you can achieve aperiodic tiling! They call Tile (1, 1) "weakly chirality-preserving aperiodic single tile". Because if you require the addition of mirror symmetric tiles, it must not be intrinsically aperiodic! This is the meaning of "weak" in "weak chirality".
So far, they have truly found a single-shaped tile that can be non-periodically tiled without the help of mirror symmetry, only through rotation and translation.

But several mathematicians were not satisfied yet. They tried to find a "strong chirality-preserving non-periodic single tile", which roughly means that even if you are allowed to add mirror-symmetric tiles, you can't use them! To tile the plane densely, we can only use tiles of a single chirality, and they must be non-periodic. They took advantage of the convenient property of Tile (1, 1) being equilateral, and cleverly modified its edges as shown in the figure below, and got Spectre, "ghost".

Image source: Reference [3]

In order to prove that ghosts meet the conditions, at first, they thought it would be challenging to do calculations on ghosts because they are not polygons like hats and turtles. But Joseph found that every tiling of ghosts is equivalent to a mixed tiling of hats and turtles, which allows them to work in the beautiful discrete world of kite grids.

This shows the equivalence between the ghost described above and the hat + turtle combination. 丨Source: A chiral aperiodic monotile (uwaterloo.ca) [Please go to the "Fanpu" official account to watch the video]

They showed that ghosts can be assembled into a hierarchical substitution system, that is, in any tile formed by ghosts, each ghost is contained in an infinite hierarchy of unique, increasingly larger supertiles. Supertiles are larger shapes formed by combining multiple ghosts according to certain rules. This hierarchical substitution system ensures that ghosts are non-periodic, that is, it is impossible to form a tile with repeating units.
The strict definition of the "alternative tiling" technique here is difficult for even experts in the field to clearly express, but the essential idea is very easy to understand: use a set of rules to piece small blocks into large blocks, and then use the same rules to piece large blocks into larger blocks, and so on, eventually forming a pattern that covers the entire plane. Alternative tiling is sometimes also used to define non-periodic tiling.

Instead of tiling technology, multiple small blocks are used to form similar large blocks. 丨Image source: arXiv:
https://arxiv.org/abs/2305.17743.

The four-member team named the problem they had just solved the "Vampire Einstein problem." What does that mean?
Vampire originally means vampire, and it is said that vampires have no image in the mirror. So, the above witty saying translates to "Einstein problem without mirror image".

Thinking and Supplementary Notes

David Smith and his team submitted their paper not too long ago, so its correctness still needs some time to be rigorously reviewed. However, mathematical research that directly constructs specific objects is often enough to determine its correctness in a short period of time. At present, it seems that the mathematical community has recognized their conclusions.

As early as the end of March, when they published the first paper on Einstein's problem, it attracted widespread attention. The attention was not only from mathematicians, but also from a large number of artists. In addition to graphic designers and puzzle lovers, there were even composers who tried to transform the algorithm for achieving non-periodic tessellation into a melody, experimenting with a new form of music.

On July 20, 2023, I was surprised to find that White Hag, a famous Irish beer brand, launched a beer can packaged in a non-periodic tile "hat" design.

This widespread attention ultimately brought unexpected benefits to the development of mathematics - the final proof was inspired by the work of Japanese artist Yoshiaki Araki.

Now, apart from the authors of the paper, the happiest person is this Japanese artist. One day after the paper was published, he happily shared a screenshot of the paper on social media because several authors put his name in the acknowledgments.

Another thing worth thinking about is the key role played by David Smith, an amateur mathematician, in this major mathematical breakthrough.

In fact, this is far from the first time that amateurs have made major breakthroughs in tiling geometry. In the 1970s, Robert Ammann, a mail sorter, independently discovered several non-periodic tilings and a systematic method for generating them called Ammann bars; in 1975, California housewife Marjorie Rice discovered a new family of pentagonal tiles; and then Joan Taylor discovered what became known as the Socolar-Taylor tiles.

So much so that one mathematician joked that in a specific field of mathematics (the "specific mathematics" here is a term similar to "applied mathematics", which is a category. It refers to mathematical content that is intuitively visible and related to computers), perhaps the biggest difference between amateurs and professional mathematicians is that the former "do not need to know how difficult the problem is", so they can make unexpected and wonderful discoveries.

Here I will simply leave you with a question to think about, a classic domino tiling problem that essentially does not require any mathematical knowledge to solve:

Finally, there is still a lot to say about tessellation. For example, although this time we focus on non-periodic tessellation, it does not mean that periodic tessellation is an unimportant topic. It was not until 2015 that mathematicians used computers to discover the 15th and last pentagon that can be periodically tessellated, thus finding all the periodic single tessellation polygons.

Periodic tessellation and non-periodic tessellation are like rational numbers and irrational numbers. Although rational numbers are indeed simpler than irrational numbers, there is still a lot of unknown content to be explored.

In addition to plane tiling, there are also many noteworthy results in non-periodic tiling in high-dimensional space. For example, in November 2022, Terence Tao and Rachel Greenfeld announced the overthrow of a "periodic tiling conjecture" in high-dimensional space. As for Einstein problem tiles, there are also so-called three-dimensional Einstein problem tiles (as shown below).

Image source: Socolar–Taylor tile Wikipedia

Non-periodic tiling has important applications and research value in many mathematical fields, such as automata theory, combinatorial mathematics, discrete geometry, dynamical systems, group theory, harmonic analysis and number theory, as well as crystallography and chemistry. The most famous application in crystals and chemistry is to provide theoretical mathematical and physical explanations for the structure and properties of quasicrystals. (If we are wise after the event, we can even say that non-periodic tiling reveals the existence of quasicrystals - it's just that no one realized this before quasicrystals were discovered in nature.) The relationship between non-periodic tiling and quasicrystals is a wonderful topic that spans mathematics, physics, chemistry, materials and other fields.

References

[1] Hobbyist Finds Math's Elusive 'Einstein' Tile | Quanta Magazine

[2] Craig S. Kaplan (@[email protected]) - Mathstodon

[3] Achiral aperiodic monotile, https://arxiv.org/abs/2305.17743

[4] Anaperiodic monotile, https://arxiv.org/pdf/2303.10798.pdf

[5] Software used by David Smith (PolyForm Puzzle Solver (jaapsch.net)):
https://www.jaapsch.net/puzzles/polysolver.htm

[6] Tools shared by Craig S. Kaplan:
https://cs.uwaterloo.ca/~csk/spectre/

We would like to thank Professor Yi Ni of the Department of Mathematics at California Institute of Technology for reviewing and correcting this article.

This article is supported by the Science Popularization China Starry Sky Project

Produced by: China Association for Science and Technology Department of Science Popularization

Producer: China Science and Technology Press Co., Ltd., Beijing Zhongke Xinghe Culture Media Co., Ltd.

Special Tips

1. Go to the "Featured Column" at the bottom of the menu of the "Fanpu" WeChat public account to read a series of popular science articles on different topics.

2. Fanpu provides a function to search articles by month. Follow the official account and reply with the four-digit year + month, such as "1903", to get the article index for March 2019, and so on.

Copyright statement: Personal forwarding is welcome. Any form of media or organization is not allowed to reprint or excerpt without authorization. For reprint authorization, please contact the backstage of the "Fanpu" WeChat public account.