Pentagon Tiling Proof Solves Century-Old Math Problem | Hacker News Reader

Pentagon Tiling Proof Solves Century-Old Math Problem

quantamagazine.org

191 pointspetethomas42 comments

I love how there's a mix of simple things like why you can't tile things with more than 6 edges and really complex things like what the headline is about.

For those that don't see why it's so simple.

https://plus.maths.org/content/trouble-five

Unless I'm wrong, the link you gave only speaks about impossibility for regular convex polygons, whereas the original links deals with the more general impossibility for any convex polygon with more than 6 sides.

I believe he links it for a bit of general background, but it is older so naturally it wouldn't include the latest finding

I loved that part. As soon as I read that you can't tile a plane with septagons, I wondered why - and scrolled down to see the answer.

When it came to the description of "einsteins" (a single tile aperiodic tessellation), I couldn't help but think of the images in the 3rd edition of The Scheme Programming Language:

http://www.scheme.com/tspl3/binding.html#./binding:h0

http://www.scheme.com/tspl3/examples.html#./examples:h0

...Are there holes in those "tilings", or are the tiles not all the same shape, or am I misunderstanding what non-periodic means in this context?

And what is the name for those types of "self-surrounding" tiles on the cover:

http://www.scheme.com/tspl3/canned/large-cover.png

The spiral images have tiles that are reflected, not just rotated. You'd otherwise need a third dimension to do another rotation. I think that might be considered two different tiles by the rules laid out in the article.

The banner image in the article appears to include reflected tiles.

The tiles in an aperiodic tiling must guarantee that the tiling is not periodic simply by their shape.

https://en.wikipedia.org/wiki/Aperiodic_tiling

All three of the Scheme examples can be tiled periodically even though they aren't tiled periodically in the examples. How to tile them periodically is left as an exercise to the reader, but it's not hard.

Got to love this quote from the "Einstein Problem" page on Wikipedia:

https://en.wikipedia.org/wiki/Einstein_problem

"Depending on the particular definitions of nonperiodicity and the specifications of what sets may qualify as tiles and what types of matching rules are permitted, the problem is either open or solved."

There's definitely something Douglas Adams-esque about that phrasing.

Marjorie Jeuck Rice, who was the real key to this breakthrough by finding new tilings that had been claimed impossible, passed away only last week.

I didn't know about Marjorie Rice; interesting and uplifting "underdog" story.

Me neither - then I googled her and found that she had died just over a week ago (02/07/17). As sad as this is, it seems that she was a remarkably bright woman who lived a long and fruitful life. It's satisfying that in the seemingly ultra-inaccessible world of modern mathematics that (for want of a better term) normal people can still make headway.

I was recently watching some Computerphile videos and was surprised to learn that several geometric problems have fundamental applications outside the physical sciences, such as geometric sphere packing and error correcting codes. Does tiling research have any known applications in CS or information theory?

Wang tiles, mentioned only at the end of the article, encode Turing-equivalent computation in their simple color-matching rule. It is unknown exactly how useful Wang tiles are to theory of computation, other than as a wonderful demonstration of how easily Turing-complete systems arise naturally.

I suspect that tiling may have applications in resource management, particularly when allocating resources like memory which have an underlying topological structure.

Edit: https://arxiv.org/pdf/1506.06492.pdf is worth considering, but I don't yet know what its relevance is.

Greg Egan explores the concept of Wang tiles as a naturally occurring computer in his excellent novel "Diaspora":

http://www.gregegan.net/DIASPORA/DIASPORA.html

It gets a bit dense at times, but I would highly recommend it, especially if you are interested in turing complete systems.

Wang tiles made from DNA (using bases to encode the "colours", so matching up base pairs enforces the rules) have been used to perform computation.

AFAIK it's not yet a practical tool, but the choice of Wang tiles was practical for the experimenters since they're known to be Turing complete, and hence make for a more compelling demonstration.

http://www.dna.caltech.edu/Papers/FOE_2003_final.pdf

Working with geographic systems, using tiling is a way to perform spatial indexing. If there are novel approaches to nonstandard (rectangular) tiling that better group geographic data for analysis, this could potentially lead to faster geographic computations in an area that is well known for having quite expensive approaches.

Material physics obviously. If can aperiodically pack molecules better than before you got a new super material. With an "Einstein" (single molecul) it would be easiest, of course. Penrose like tilers need two and they are not so easy to arrange.

I love that pattern where the pentagons make up hexagons. When I own a house that's going in the kitchen.

Are you referring to this? https://en.wikipedia.org/wiki/Pentagonal_tiling#Pentagonal.2...

Many aperiodic tilings rely on "substitutions" which let you express very complicated patterns with some simple recursion.

I've found this maps well to express them in programming languages, like PostScript (although most implementations limit the stack at some point).

For an example of expressing these patterns in PostScript, and what it looks like on closet doors, check out https://github.com/steiza/postscript_fractals

you might also enjoy playing with 'ghost diagrams':http://logarithmic.net/pfh/ghost-diagrams

When they talk about the einstein, I assume they mean a shape that can only tile the plane non-periodically. If the tile is allowed to tile the plane both periodically and non-periodically, the solution would be obvious.

>If the tile is allowed to tile the plane both periodically and non-periodically, the solution would be obvious.

Maybe you can draw a sketch for those of us who aren't immediately seeing the obvious?

Squares, but each row of squares has a random offset

Or triangles, with similar "slide along the seam" changes.

That is a periodic tiling (just think about what happens if you follow the tiling along the rows instead of along the columns, you'll periodically see the same pattern).

No, you wouldn't necessarily

https://en.wikipedia.org/wiki/Euclidean_tilings_by_convex_re...

It's listed as a periodic tiling. If you move the whole plane one square to the left or right you'll find that everything fits into place nicely, making this a periodic tiling.

Hm, I'm not knowledgeable about this subject but this seems like the offset on each row is NOT random, but it's instead repeating. Imagine instead that each time I added a new row, I chose the offset to be, say, a completely new value.

Doesn't matter, because your new row will still be offset with the same random value to existing rows after moving one square to the left or right.

If you allow reflections of the single tile, an easy counterexample is the pinwheel tiling[1], which is a non-periodic tiling composed entirely of isometric triangles.

An (imo less satisfying) example which does not require reflection of the tile would be as follows: Take a rectangle with width equal to twice the height. You can use this tile to create squares which are either split vertically or horizontally. Put a single horizontally split square at the origin, then tile the remainder of the plane with vertically split squares: this tiling is (rather trivially) not periodic.

[1]https://en.wikipedia.org/wiki/Pinwheel_tiling

> I assume they mean a shape that can only tile the plane non-periodically.

Yes, they probably [0] mean aperiodic, or "exclusively non-periodic".

[0] https://en.wikipedia.org/wiki/Einstein_problem

Here's [1] an article from 2015 describing Casey Mann, Jennifer McLoud, and David Von Derau's discovery of the 15th type of pentagon.

[1] https://www.theguardian.com/science/alexs-adventures-in-numb...

Fascinating. And the fact that it's been confirmed by a competing team makes it really believable.

I wonder if it has a Conway's Life glider like Penrose tiles.

Wow, these programs would make excellent screen savers.

I would really like to see a website dedicated to showcasing beautiful visual manifestations of tiling

You might enjoy http://tilings.math.uni-bielefeld.de/

You could try Taprats: https://sourceforge.net/projects/taprats/

The UI is not perfect, especially the tiling designer (but once you master the keyboard shortcut it works okay). And sin of sins, it's written in Java! But I do think some of the built-in example are nice. I'm biased.

Reply on news.ycombinator.com