Elusive 'Einstein' Solves a Longstanding Math Problem
And it all began with a hobbyist “messing about and experimenting with shapes."
By Siobhan Roberts, NYT
March 28, 2023
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 Mr. 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 Mr. Smith and three co-authors with mathematical
and computational expertise - proves Mr. Smith's discovery true. The
researchers called their einstein "the hat," as it resembles a fedora.
(Mr. 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." Dr. 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 3-D version of the Socolar-Taylor tile.)
From 20,426 to one
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, the mathematician Hao Wang conjectured that such sets were
impossible, but his student Robert Berger soon proved the conjecture wrong.
Dr. 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?" Dr.
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 Dr. 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. Mr. 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,
Mr. 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," Mr. 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?" Mr. Smith wrote.
"It was clear that something unusual was happening with this shape," Dr.
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, Mr. Smith and Dr. Kaplan studied the tiling's hierarchical
structure by eye. Dr. 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, Dr. 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,"
Dr. 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," Dr. Berger, a retired electrical engineer in Lexington,
Mass., 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.
Dr. 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, Dr. Berger said: Is there an
einstein that will do the job without reflection?
Hiding in the hexagons
Dr. 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,"
Dr. 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." Dr. 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 the Dutch artist M.C. Escher.
Dr. 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, Mr. Smith later found a second einstein. He called it "the turtle"
- a polykite made of not eight kites but 10. It was "uncanny," Dr. Kaplan
said. He recalled feeling panicked; he was already "neck deep in the hat."
But Dr. 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.
Mr. 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," Dr. 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."
Dr. 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.
Mr. 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."