Hobbyist Finds Math’s Elusive ‘Einstein’ Tile
To make the tiling, slice an ordinary hexagonal grid into segments, then glue together adjoining segments.
Samuel Velasco/Quanta Magazine
Introduction
In mid-November of last year, David Smith, a retired print technician and an aficionado of jigsaw puzzles, fractals and road maps, was doing one of his favorite things: playing with shapes. Using a software package called the PolyForm Puzzle Solver, he had constructed a humble-looking hat-shaped tile. Now he was experimenting to see how much of the screen he could fill with copies of that tile, without overlaps or gaps.
Usually when he created tiles, they would either settle into some repeating pattern or fail to tile much of the screen. But the hat tile seemed to do neither. Smith cut out 30 copies of the hat on cardstock and assembled them on a table. Then he cut out 30 more and kept going. “I noticed that it was producing a tessellation that I had not seen before,” he said. “It’s a tricky little tile.” He sent a description of his tile to Craig Kaplan, an acquaintance and computer scientist at the University of Waterloo in Canada, who immediately started investigating its properties.
On March 20, Smith and Kaplan, together with two more researchers, announced that the hat tile was something mathematicians have been seeking for more than five decades: a single tile whose copies can fill the entire plane, but only in patterns that don’t consist of a repeating block of tiles. Mathematicians call such a tile, or set of tiles, “aperiodic,” in contrast to shapes like squares or hexagons that can cover the plane in a repeating (or periodic) fashion.
The hat tile embodies “enough complexity to forcibly disrupt periodic order at all scales,” the researchers wrote in their paper. What’s more, they realized, the hat is one of infinitely many different tiles of this type.
“It’s hiding in plain sight,” said Doris Schattschneider, an emerita mathematics professor at Moravian University in Pennsylvania. She described herself as “flabbergasted.”
Mathematicians have been searching for a tile like the hat since the 1960s, when Robert Berger constructed a set of 20,426 shapes that, combined, aperiodically tile the plane. Berger’s work set off a race to construct smaller aperiodic tile sets, culminating in Roger Penrose’s discovery in the 1970s of sets containing just two aperiodic tiles. In 1982, Dan Shechtman discovered that symmetries akin to the ones in Penrose tilings show up in nature in the form of structures called quasicrystals, in work that earned him the 2011 Nobel Prize in chemistry.
Since then, mathematicians have been trying to find a single tile that fills the two-dimensional plane aperiodically, without gaps or overlaps. Ludwig Danzer, a German geometer, playfully dubbed such a tile an “einstein” — a pun on the German phrase “ein stein,” which means “one piece.”
In the 1990s, two groups found ways to overlap adjacent copies of a single 10-sided tile to aperiodically cover the plane. About a decade later, Joan Taylor, an amateur mathematician in Tasmania, discovered a shape with multiple disconnected pieces. She and Joshua Socolar, a physicist at Duke University, showed in a 2010 paper that it aperiodically tiles the plane. And just last year, the mathematicians Rachel Greenfeld of the Institute for Advanced Study and Terence Tao of the University of California, Los Angeles discovered a high-dimensional shape that aperiodically tiles space, without even needing to be rotated or reflected.
But no one could find a true einstein — a simple two-dimensional shape that tiles aperiodically. Eventually, mathematicians started wondering whether such a tile even exists, said Marjorie Senechal, a tiling researcher and emerita professor at Smith College. The fact that an einstein as simple as Smith’s hat was out there all along is “just mind-boggling,” she said.
Perhaps, she speculated, the reason the hat has evaded discovery until now is because many mathematicians have focused on shapes with “forbidden” symmetries — ones that can’t appear in periodic tilings. Penrose’s tilings, for instance, have fivefold symmetries, like those found in pentagons and five-pointed stars. Regular pentagons cannot tile the plane, so fivefold symmetries are a natural place to look for tilings that can’t be periodic.
The hat, by contrast, has no symmetry and is “almost mundane in its simplicity,” the authors wrote. What its tilings do have is a deep relationship with a particular periodic tiling: the honeycomb lattice of hexagons. To get a hat tiling from a hexagonal tiling, first connect the midpoints of the opposite sides of the hexagons. This divides every hexagon into six “kites.” Each hat is made of eight adjacent kites, combined from neighboring hexagons. With just a little work, anyone with a magic marker and a hexagonally tiled bathroom floor can trace out a hat tiling.
The hat tile, Senechal said, shows that periodic and aperiodic tiles are more closely linked than mathematicians had realized.
In the days since the announcement, mathematicians and tiling hobbyists have rushed to get their hands on the new tiles, making paper cutouts, 3D-printing them, and making hat quilts and cookies. The excitement the tiles have generated has felt “a bit surreal,” said Smith, who lives in the coastal town of Bridlington in northern England. “I’m not used to this kind of thing.”
But this is far from the first time a hobbyist has made a serious breakthrough in tiling geometry. Robert Ammann, who worked as a mail sorter, discovered one set of Penrose’s tiles independently in the 1970s. Marjorie Rice, a California housewife, found a new family of pentagonal tilings in 1975. And then there was Joan Taylor’s discovery of the Socolar-Taylor tile. Perhaps hobbyists, unlike mathematicians, are “not burdened with knowing how hard this is,” Senechal said.
Shapes Within Shapes
It’s easy to make tilings that aren’t periodic from tiles that also form periodic tilings. You can, for instance, use a couple of vertical dominoes while otherwise filling the plane with horizontal dominoes. “The real art is finding a shape that will allow you to tile the whole plane, but won’t let you do it in a periodic way,” Socolar said.
It’s impossible to create an algorithm that can determine, for every possible collection of tiles, whether they tile the plane (let alone whether they are aperiodic). So after Smith told Kaplan about the hat tile, Kaplan turned to a program he’d written that simply places copies of a tile around an initial seed tile in ever-growing rings. Apart from tiles that create repeating patterns, which have infinitely many rings, no one had ever found a tile that could keep going for more than six rings. This time, the program kept going and going. It filled 16 rings with hats before Kaplan told it to stop, figuring they had enough data to work with.
Meanwhile, to Kaplan’s shock, Smith made another discovery: a second tile, shaped like a turtle, that also appeared to be aperiodic. “The idea of identifying two einsteins back-to-back seemed too good to be true,” the researchers wrote.
By mid-January, Smith and Kaplan had enlisted two more researchers: Chaim Goodman-Strauss, a mathematician at the National Museum of Mathematics and the University of Arkansas, and Joseph Samuel Myers, a software engineer in Cambridge, England, with a doctorate in combinatorics. Myers started devoting all his spare time to the hat tile, and in just over a week, he had proved that it is aperiodic. “We were all pretty blown away by how quickly he nailed this all down,” Kaplan said.
The proof adapted an approach originated by Berger in the 1960s, which involves piecing together tiles into larger versions of themselves, creating a hierarchical structure. Myers began by identifying four intermediate shapes built of hats, which he called H, T, P and F. An H, for example, is made of four hats, joined together to form a shape roughly like a triangle with its tips chopped off. Myers showed that you can put together combinations of the four shapes to make bigger ones. You can make a bigger H, for instance, by surrounding one T with three H’s, then surrounding this object with a combination of P’s and F’s.
Merrill Sherman/Quanta Magazine
This provided a way to make bigger and bigger hat tilings. You can start with an H, increase its size, then fill it with the above combination of the four shapes. Next, you can inflate this whole assembly and fill all the shapes inside the (now huge) H with assortments of H, T, P and F shapes. You can repeat these steps indefinitely, building an increasingly large hierarchy of shapes within shapes. At the bottom level of the hierarchy is the hat.
The researchers proved that the tilings created by these hierarchical constructions are never periodic. They also proved that hierarchical constructions are the only way to make hat tilings. Therefore, a hat tiling can never be periodic. “It’s a very cool result,” Socolar said.
Resizing the Hat
That left the other tile Smith had found: the turtle. Was it just an amazing coincidence that he had come up with two different aperiodic tiles, when no one had found any for 50 years? The hat and turtle tilings looked strikingly similar, making the researchers suspect that the turtle was also aperiodic. But their suspicions were not a proof.
Then Myers made a discovery that the researchers describe in their paper as “both a relief and a revelation.” The hat and the turtle, he realized, belong to an infinite family of tiles that all tile the plane in the same way.
Each hat has 13 sides: six long ones and six short ones that correspond to kite edges, plus one more that’s made of two short kite edges. By tweaking the lengths of these sides, you can create a continuum of new shapes. Imagine a slider bar: As you move it left, the short sides get shorter (as does the solitary double-short side); as you move it right, the long sides get shorter. The turtle is somewhere off to the right of the hat, but there are also infinitely many other shapes.
If you push the slider all the way to the left, the short sides of the hat disappear, leaving a six-sided chevron shape; if you push it all the way to the right, the long sides disappear, leaving a seven-sided shape the researchers called a comet. Unlike the hat, the chevron and comet can tile the plane periodically. So can the shape at the center of the slider bar, where the long and short sides are equal.
Craig Kaplan, a computer scientist at the University of Waterloo in Canada.
Joe Petrik
But Myers realized that he could use the geometry of the chevron and comet to prove that all the shapes along the slider are aperiodic, except for the two ends and the midpoint. This argument, which Kaplan called a “mathematical rabbit out of a hat,” is new to the tiling world. Prior to its discovery, the field had only three main approaches for proving aperiodicity, Goodman-Strauss said. “Now we have a fourth.”
Mathematicians are trying to wrap their heads around this new method. “I have to sit down with this thing and spend serious time on it,” Senechal said.
A natural next question, Greenfeld said, is whether mathematicians can identify some sort of source for the new tilings. In 1981, Nicolaas de Bruijn showed that Penrose tilings are the two-dimensional shadows of pieces of periodic five-dimensional tilings. “If the dynamics or the structure of these [new] tilings correspond to some higher-dimensional regular tiling, this will be extremely interesting to know,” Greenfeld said.
Socolar, as a physicist, has begun exploring the tilings’ material properties. The diffraction pattern that emerges if you shine a light through one of these tilings, he has found, has the same kind of sharp peaks researchers have observed in quasicrystals. Even so, the hat tiling “looks to me to be different from anything else I’ve seen before,” he said.
Meanwhile, Smith isn’t done with his “tricky little tile.” He intends to explore its artistic possibilities and figure out how to use colors to bring out the patterns the tile appears to insist upon. “It seems to have an attitude, if you like,” he said. “I think it should be treated with respect.”
