Saturday, April 01, 2023

Elusive ‘einstein’ solves a long-standing math problem

An image provided by David Smith, a self-described shape hobbyist who lives in Bridlington, England, of his ‘aperiodic monotile’ shape.
 [David Smith via The New York Times]

Siobhan Roberts
29.03.2023 • 03:10

Last November, after a decade of failed attempts, David Smith, a self-described shape hobbyist of Bridlington in East Yorkshire, England, suspected that he might have finally solved an open problem in the mathematics of tiling: That is, he thought he might have discovered an “einstein.”

In less poetic terms, an einstein is an “aperiodic monotile,” a shape that tiles a plane, or an infinite two-dimensional flat surface, but only in a nonrepeating pattern. (The term “einstein” comes from the German “ein stein,” or “one stone” – more loosely, “one tile” or “one shape.”) Your typical wallpaper or tiled floor is part of an infinite pattern that repeats periodically; when shifted, or “translated,” the pattern can be exactly superimposed on itself. An aperiodic tiling displays no such “translational symmetry,” and mathematicians have long sought a single shape that could tile the plane in such a fashion. This is known as the einstein problem.

“I’m always messing about and experimenting with shapes,” said Smith, 64, who worked as a printing technician, among other jobs, and retired early. Although he enjoyed math in high school, he didn’t excel at it, he said. But he has long been “obsessively intrigued” by the einstein problem.

And now a new paper – by Smith and three co-authors with mathematical and computational expertise – proves Smith’s discovery true. The researchers called their einstein “the hat,” as it resembles a fedora. (Smith often sports a bandanna tied around his head.) The paper has not yet been peer reviewed.

“This appears to be a remarkable discovery!” Joshua Socolar, a physicist at Duke University who read an early copy of the paper provided by The New York Times, said in an email. “The most significant aspect for me is that the tiling does not clearly fall into any of the familiar classes of structures that we understand.”

“The mathematical result begs some interesting physics questions,” he added. “One could imagine encountering or fabricating a material with this type of internal structure.” Socolar and Joan Taylor, an independent researcher in Burnie, Tasmania, previously found a hexagonal monotile made of disconnected pieces, which according to some, stretched the rules. (They also found a connected 3D version of the Socolar-Taylor tile.)

From 20,426 to 1


Initially, mathematical tiling pursuits were motivated by a broad question: Was there a set of shapes that could tile the plane only nonperiodically? In 1961, mathematician Hao Wang conjectured that such sets were impossible, but his student Robert Berger soon proved the conjecture wrong. Berger discovered an aperiodic set of 20,426 tiles, and thereafter a set of 104.

Then the game became: How few tiles would do the trick? In the 1970s, Sir Roger Penrose, a mathematical physicist at University of Oxford who won the 2020 Nobel Prize in physics for his research on black holes, got the number down to two.

Others have since hit upon shapes for two tiles. “I have a pair or two of my own,” said Chaim Goodman-Strauss, another of the paper’s authors, a professor at the University of Arkansas, who also holds the title of outreach mathematician at the National Museum of Mathematics in New York.

He noted that black and white squares also can make weird nonperiodic patterns, in addition to the familiar, periodic checkerboard pattern. “It’s really pretty trivial to be able to make weird and interesting patterns,” he said. The magic of the two Penrose tiles is that they make only nonperiodic patterns – that’s all they can do.

“But then the Holy Grail was, could you do with one – one tile?” Goodman-Strauss said.

As recently as a few years ago, Sir Roger was in pursuit of an einstein, but he set that exploration aside. “I got the number down to two, and now we have it down to one!” he said of the hat. “It’s a tour de force. I see no reason to disbelieve it.”

The paper provided two proofs, both executed by Joseph Myers, a co-author and a software developer in Cambridge, England. One was a traditional proof, based on a previous method, plus custom code; another deployed a new technique, not computer assisted, devised by Myers.

Sir Roger found the proofs “very complicated.” Nonetheless, he was “extremely intrigued” by the einstein, he said: “It’s a really good shape, strikingly simple.”

Imaginative tinkering


The simplicity came honestly. Smith’s investigations were mostly by hand; one of his co-authors described him as an “imaginative tinkerer.”

To begin, he would “fiddle about” on the computer screen with PolyForm Puzzle Solver, software developed by Jaap Scherphuis, a tiling enthusiast and puzzle theorist in Delft, the Netherlands. But if a shape had potential, Smith used a Silhouette cutting machine to produce a first batch of 32 copies from card stock. Then he would fit the tiles together, with no gaps or overlaps, like a jigsaw puzzle, reflecting and rotating tiles as necessary.

“It’s always nice to get hands-on,” Smith said. “It can be quite meditative. And it provides a better understanding of how a shape does or does not tessellate.”

When in November he found a tile that seemed to fill the plane without a repeating pattern, he emailed Craig Kaplan, a co-author and a computer scientist at the University of Waterloo.

“Could this shape be an answer to the so-called ‘einstein problem’ – now wouldn’t that be a thing?” Smith wrote.

“It was clear that something unusual was happening with this shape,” Kaplan said. Taking a computational approach that built on previous research, his algorithm generated larger and larger swaths of hat tiles. “There didn’t seem to be any limit to how large a blob of tiles the software could construct,” he said.

With this raw data, Smith and Kaplan studied the tiling’s hierarchical structure by eye. Kaplan detected and unlocked telltale behavior that opened up a traditional aperiodicity proof – the method mathematicians “pull out of the drawer anytime you have a candidate set of aperiodic tiles,” he said.

The first step, Kaplan said, was to “define a set of four ‘metatiles,’ simple shapes that stand in for small groupings of one, two, or four hats.” The metatiles assemble into four larger shapes that behave similarly. This assembly, from metatiles to supertiles to supersupertiles, ad infinitum, covered “larger and larger mathematical ‘floors’ with copies of the hat,” Kaplan said. “We then show that this sort of hierarchical assembly is essentially the only way to tile the plane with hats, which turns out to be enough to show that it can never tile periodically.”

“It’s very clever,” Berger, a retired electrical engineer in Lexington, Massachusetts, said in an interview. At the risk of seeming picky, he pointed out that because the hat tiling uses reflections – the hat-shaped tile and its mirror image – some might wonder whether this is a two-tile, not one-tile, set of aperiodic monotiles.

Goodman-Strauss had raised this subtlety on a tiling listserv: “Is there one hat or two?” The consensus was that a monotile counts as such even using its reflection. That leaves an open question, Berger said: Is there an einstein that will do the job without reflection?

Hiding in the hexagons


Kaplan clarified that “the hat” was not a new geometric invention. It is a polykite – it consists of eight kites. (Take a hexagon and draw three lines, connecting the center of each side to the center of its opposite side; the six shapes that result are kites.)

“It’s likely that others have contemplated this hat shape in the past, just not in a context where they proceeded to investigate its tiling properties,” Kaplan said. “I like to think that it was hiding in plain sight.”

Marjorie Senechal, a mathematician at Smith College, said, “In a certain sense, it has been sitting there all this time, waiting for somebody to find it.” Senechal’s research explores the neighboring realm of mathematical crystallography, and connections with quasicrystals.

“What blows my mind the most is that this aperiodic tiling is laid down on a hexagonal grid, which is about as periodic as you can possibly get,” said Doris Schattschneider, a mathematician at Moravian University, whose research focuses on the mathematical analysis of periodic tilings, especially those by Dutch artist M.C. Escher.

Senechal agreed. “It’s sitting right in the hexagons,” she said. “How many people are going to be kicking themselves around the world wondering, why didn’t I see that?”

The einstein family

Incredibly, Smith later found a second einstein. He called it “the turtle” – a polykite made of not eight kites but 10. It was “uncanny,” Kaplan said. He recalled feeling panicked; he was already “neck deep in the hat.”

But Myers, who had done similar computations, promptly discovered a profound connection between the hat and the turtle. And he discerned that, in fact, there was an entire family of related einsteins – a continuous, uncountable infinity of shapes that morph one to the next.

Smith wasn’t so impressed by some of the other family members. “They looked a bit like impostors, or mutants,” he said.

But this einstein family motivated the second proof, which offers a new tool for proving aperiodicity. The math seemed “too good to be true,” Myers said in an email. “I wasn’t expecting such a different approach to proving aperiodicity – but everything seemed to hold together as I wrote up the details.”

Goodman-Strauss views the new technique as a crucial aspect of the discovery; to date, there were only a handful of aperiodicity proofs. He conceded it was “strong cheese,” perhaps only for hard-core connoisseurs. It took him a couple of days to process. “Then I was thunderstruck,” he said.

Smith was amazed to see the research paper come together. “I was no help, to be honest.” He appreciated the illustrations, he said: “I’m more of a pictures person.”

This shape never existed before (and I'm mesmerised)

New design shape; an optical illusion
(Image credit: Smith et al. (2023)
Just when you think you've seen it all, mathematicians go and discover the existence of a new shape. That's right a new shape. The new 13-sided two-dimensional shape has been called the 'Hat' and could open up all manner of new design and graphic design challenges and ideas.

You may be asking what makes this 'new'? And why can't anyone just doodle a shape and call it a discovery? The difference between the Hat and any other shape you may draw is it can be used indefinitely in a pattern without ever repeating. This was previously only a theoretical shape, but now it's a reality.

So what does this mean for design and graphic design? Well, for one designers and artists have a new shape to play with, one that has never been used before. The circle is considered the most overused shape in graphic design, and can be found in everything from the Twitter logo to the Apple logo, so a new shape could spark ideas in the best graphic designers.


The Hat is a new 13-sided polykite shape that can be reused in a pattern without ever repeating (Image credit: Smith et al. (2023))


Here's a bit of maths detail: the new Hat shape is known as an aperiodic monotile, which is a maths way of saying a single tile can be used across an entire surface without ever repeating. Once just a theoretical shape, a 13-sided polykite shape made up of eight kites connected at their edges, was discovered by mathematician David Smith and his team when they published a research paper this month.


Co-author Chaim Goodman-Strauss, a mathematician at the National Museum of Mathematics, told the New Scientist(opens in new tab): "You’re literally looking for like a one in a million thing. You filter out the 999,999 of the boring ones, then you’ve got something that’s weird, and then that’s worth further exploration."

What's amazing is the team had to turn off their computers and work out the shape by hand and eye: "And then by hand you start examining them and try to understand them, and start to pull out the structure. That’s where a computer would be worthless as a human had to be involved in constructing a proof that a human could understand."

What will graphic designers do with this new shape? (Image credit: Smith et al. (2023))

The Hat isn't the most accessible shape for design, its angles and 13-sides could make it a tricky one to work into new logos and projects. But I find this new shape absolutely mesmerising. I can already imagine crafters being eager to break out the best laser cutters and Cricut machines and start creating abstract and geometric designs.

Interior designers may want to explore how the shape can be used in tiled floors, fabric patterns and designer wallpaper. But can the maths behind this new shape inform a generation of logo designers to explore a new trend in design? The discovery of an actual new shape, no matter how abstract, is exciting. And for once, it wasn't created by AI.


No comments:

Post a Comment