Kitchen Tile Catalog Complete

All tessellating convex polygons found

Cropped and combined from src1, src2.

Michaël Rao and Marjorie Rice are linked in this month’s news. Rao has just released a paper (see also slides and code here) completing the catalog of convex polygons that tile the plane. Rice, who passed away on July 2 (obit), had expanded the pentagon catalog from 9 to 13 while working in her kitchen in 1975. Rolf Stein found a fourteenth in 1985 and Casey Mann led a team of programmers to find a fifteenth in 2015. Rao has closed the book at 15.

Today Dick and I hail their accomplishments, which we noted from two articles by Natalie Wolchover in Quanta this past Tuesday. We also emphasize some related problems.

We especially are impressed by Rice, who was a true amateur. She had no advanced training in mathematics of any kind. After reading a 1975 Scientific American article on tessellations she started her search for new types. She succeeded and found ones that had been missed by everyone—that includes Johannes Kepler who worked on tessellations in 1691. She maintained a website named, “Intriguing Tessellations.”

In recent decades, computers have become an essential tool. This raises the possibility of a new kind of amateur: one who can code. Computing power is more accessible than ever before. The fact that having advanced degrees doesn’t make your code run faster levels the playing field. As it happens, Mann led a team that included a student and Rao wrote his own code.

Some Tiling Basics

If you draw any triangle in the plane, then you can place a 180 rotated copy against it on an edge to make a parallelogram. That can be replicated to make an infinite strip, and those strips complete a tiling of the plane. That tiling is periodic with only two different orientations of the triangle.

A little more thought will tell you that any quadrilateral—not just a parallelogram—can be made to tile the plane. The reason is that the four interior angles add up to 360—even if the quadrilateral is not convex. Make three copies and orient them so that the four different angles come together at a corner of the original and its two adjoining edges are shared. Then the same orientations work at the opposite corner and this suffices to see that the clump of four tiles the whole plane, indeed two of them do.

Combined from Math and the Art of M. C. Escher wiki source.

Convex polygons with 7 or more sides cannot tile the plane—whatever their shape—because their interior angles sum so high that the average number of polygons meeting at a vertex would fall below 3. Regular hexagons can tile, of course. Karl Reinhardt in 1918 showed that convex hexagons can tile in three ways that use 2, 3, or 4 different orientations (the first not being a special case of the third).

That left the case of pentagons. Of course a regular pentagon cannot tile the plane, but ones shaped like a baseball home plate can mesh in a sawtooth pattern using two orientations. You can get this by cutting each strip of a regular hexagonal tiling in half:

Mathematical Tourist source.

The idea of cutting tiles to make new ones animates the mathematics. The following figure taken from a 2015 story in Britain’s Guardian newspaper shows the now-complete list of distinct pentagonal tilings.

Note that the version of this diagram used in a February 2013 post on Rice had only the 14 tilings known then.

Wallpaper, Flooring, and Kitchen Counters

All known tilings by single connected pieces are periodic like wallpaper. There is an algebraic theory of wallpaper symmetries and corresponding groups. Note that pentagonal symmetry is excluded. The periodic clumps in tilings by pentagons, if they have any rotational symmetry other than the full circle, must have one of order 2, 3, 4, or 6.

Flooring, however, can choose to have a radial pattern. Here are two tilings found by Sir Roger Penrose of Oxford with five-fold symmetry that can be extended infinitely far:

Modified from Martin Gardner article source.

Both use the same two quadrilateral tiles and a special restriction: the two centrally symmetric vertices of one cannot touch a centrally symmetric vertex of the other. Cutting each tile into two triangles facilitates defining a self-recursion that proves how the pattern can be extended infinitely. Our diagram also shows a mutual recursion between the “sun” and “star” patterns.

The limit ratio of the convex “kite” tiles to the concave “dart” tiles in the recursions is the golden ratio, … To see why, note that each larger orange-bordered kite at right is made of two kites plus two halves of a dart, while the larger darts have just one kite and the halves of a dart. The recursion thus involves powers of the matrix , whose entries yield consecutive Fibonacci numbers, whose ratio approaches . Because is irrational, the tilings are not periodic.

Penrose found a related tiling using two convex shapes—a thin lozenge and a fatter one—with a similar restriction that enforces aperiodicity. John Conway suggested enforcing these restrictions by matching up colored lines, as illustrated by the entrance to Oxford’s new Mathematical Institute building. This is my own photo from two years ago:

The restriction can be enforced without markings by notching the sides allowed to match up in the manner of jigsaw puzzle pieces, but this creates non-convex polygons. Robert Ammann found a way to cut Penrose’s lozenges and assemble them into three convex polygons that can only tile aperiodically. This figure from a paper last year by Teruhisa Sugimoto shows how:

Here is a color version of Ammann’s tiling posted by John Lindner. It too could be an attractive floor, but how about as a kitchen counter?

Two of Ammann’s tiles are pentagonal. Can a single pentagon carry out an aperiodic tiling? That question may have boarded the train of Rice’s thinking as she worked at her kitchen counter. It took until Sugimoto’s paper to prove this impossible when the pentagons must share entire edges. Rao’s results completes a definite no answer.

Why Care About Tilings?

Understanding tilings of the plane is an intriguing mathematical problem. Finding new ones, as Rice did, requires cleverness and insight. Showing that certain types of tilings are impossible, as Rao did, requires another type of cleverness: the ability to prove that something cannot exist. This is interesting because it reminds us of lower bound problems that are well documented to be difficult.

Tilings are special compared to other classification problems—that is problems that show that the following list consist of all ways to create some mathematical object. They are different because tilings can be used to build real objects. One measure of this is that there are a number of patents for various types of tilings. Penrose thought to patent his tiles before publicizing them. We quote the introduction to his US patent 4133152 titled, “Set of tiles for covering a surface”:

[The field of this invention] has found practical application not only to the design of paving and wall-coverings but also in the production of toys and games. In both instances, not only is the purely geometric aspect of complete covering of the surface of importance, but the esthetic appeal of the completed tessellation has equal significance in the eye of the beholder. … [T]he pattern which they form is necessarily non-repetitive, giving a considerable esthetic appeal to the eye.

We especially like his equal regard for esthetics. What emerged in greater force than even he may have imagined—while expressly thinking of crystals—is how strongly Nature shares this regard. Dan Shechtman received the 2011 Nobel Prize in Chemistry for discovering quasicrystals. We covered some of this history going back to Hao Wang’s first proof of the existence of finite sets of non-convex tiles that can only tessellate aperiodically in a post four years ago. It is also neat that this was initially a consequence of Wang’s proof that whether a given can tessellate is undecidable, because by compactness, if the only tessellations are periodic then this fact is detectable in finite time.

One- and Two-Tile Problems Still Open

If you don’t insist on convex tiles for your kitchen counter, then the question of aperiodic tilings by one piece remains open. This is called the Einsteinproblem. The name is not for Albert Einstein but derives from ein Stein being German for one stone. German uses “Stein” in many game contexts (besides Go) where we in English say “piece.”

Joan Taylor of Tasmania, another amateur mathematician, discovered in early 2010 that a single hexagonal tile could be forced to tile hierarchically—and only aperiodically—if a more complicated set of marking rules is stipulated. These rules cannot be enforced by jigsaw notching. However, followup work with Joshua Socolar discovered how to realize the hierarchical scheme by a single non-connected tile:

The three lines are just for show; the shape alone enforces the structure which the lines make clear. This is not quite an einstein—not one stone—but an allusion to Albert is warranted by the combination of cleverness, esthetics, and amazement that this fact brings. Taylor maintains a website with other striking designs.

There is also the problem of proving the widely-voiced belief that for square tiles with notches, the set of six discovered by Raphael Robinson has the minimum size to force aperiodicity.

If you prefer to stay with convex tilings, what emerges from Sugimoto’s paper vis-à-vis Ammann’s tiles discussed above is that the following question remains open:

Are there two convex tiles that tessellate but only aperiodically?

We have not even taken time to consider tilings in three (or higher) dimensions, in which a single bi-prism is known to give only tight packings of space that are aperiodic in one of their three dimensions. Whether a single 3D tile can squeeze periodicity out of all three dimensions seems to be open. We have also glommed over whether to allow tiles to be reflected or flipped over as well as rotated, and whether the number of different rotation angles in an aperiodic tiling is infinite, as happens for the irrational twist angles (in degree units) for the bi-prism packings. We invite you, our readers, to contribute your own favorite open tiling problems.

Open Problems

How would you “bet” on the open tiling problems? How would you have bet before 2010? We’ve discussed estimates of how people would bet on open problems in complexity but we have no idea here.

[sourced first two diagrams in section 2]

Eric and Mike Turn 60

Birthday workshop at Rutgers last January

Combined from source

Eric Allender and Michael Saks have been leading lights in computing theory for four decades. They have both turned 60 this year. I greatly enjoyed the commemorative workshop held in their honor last January 28–29 at DIMACS on the Rutgers campus.

Today Dick and I salute Eric and Mike on this occasion.

Oded Wins The Knuth Prize

Just announced

Oded Goldreich is one of the top researchers in cryptography, randomness, and complexity theory.

Today Ken and I wish to thank the Knuth Prize Committee for selecting Oded as the winner of the 2017 Knuth Prize.

TOC In The Future

Results of the panel at the Theory Fest

Géraud Sénizergues proved in 1997 that equivalence of deterministic pushdown automata (DPDAs) is decidable. Solving this decades-open problem won him the 2002 Gödel Prize.

Today Ken and I want to ponder how theory of computing (TOC) has changed over the years and where it is headed.

Of course we have some idea of how it has changed over the years, since we both have worked in TOC for decades, but the future is a bit more difficult to tell. Actually the future is also safer: people may feel left out and disagree about the past, but the future is yet to happen so who could be left out?

Does Logic Apply To Hearings?

The problem of mining text for implications

2016 RSA Conference bio, speech

Michael Rogers, the head of the National Security Agency, testified before the Senate Intelligence Committee the other day about President Donald Trump. He was jointed by other heads of other intelligence agencies who also testified. Their comments were, as one would expect, widely reported.

In real time, I heard Admiral Rogers’s comments. Then I heard and read the reports about them. I am at best puzzled about what happened.

Goldilocks Principle And P vs. NP

The rule of three

Wikimedia Commons source

Robert Southey was the Poet Laureate of Britain from 1813 until his death in 1843. He published, anonymously, “The Story of the Three Bears” in 1837.

Today Ken and I want to talk about the state of versus and the relationship to this story.

Stopped Watches and Data Analytics

Is this a new or old paradox?

UK Independent source—and “a gentle irony”

Roger Bannister is a British neurologist. He received the first Lifetime Achievement Award from the American Academy for Neurology in 2005. Besides his extensive research and many papers in neurology, his 25 years of revising and expanding the bellwether text Clinical Neurology culminated in being added as co-author. Oh by the way, he is that Bannister who was the first person timed under 4:00 in a mile race.

Today I cover another case of “Big Data Blues” that has surfaced in my chess work, using a race-timing analogy to make it general.