Pentagon Tiling Proof Solves Century-Old Math Problem

https://www.quantamagazine.org/pentagon-tiling-proof-solves-century-old-math-problem-20170711/

by petethomas • 9 years ago

191 42 9 years ago

quantamagazine.org

microcolonel• 9 years ago

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

surement• 9 years ago

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

steiza_2• 9 years ago

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

pfd1986• 9 years ago

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

Aissen• 9 years ago

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

bmc7505• 9 years ago

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?

DonbunEf7• 9 years ago

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.

doctoboggan• 9 years ago

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.

chriswarbo• 9 years ago

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

SOLAR_FIELDS• 9 years ago

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.

rurban• 9 years ago

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.

lordnacho• 9 years ago

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.

vanattab• 9 years ago

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

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

plopilop• 9 years ago

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.

pavel_lishin• 9 years ago

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.

euyyn• 9 years ago

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

DC-3• 9 years ago

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.

pierrebai2• 9 years ago

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.

GregBuchholz3• 9 years ago

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?

kevinwang3• 9 years ago

Squares, but each row of squares has a random offset

nimih• 9 years ago

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

Terr_2• 9 years ago

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

newtem0• 9 years ago

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

steiza_2• 9 years ago

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

pierrebai2• 9 years ago

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.

GregBuchholz3• 9 years ago

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

dwringer• 9 years ago

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.

shmolyneaux• 9 years ago

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

markegli• 9 years ago

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.

GregBuchholz3• 9 years ago

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."

droithomme• 9 years ago

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.

v64• 9 years ago

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...

kleer001• 9 years ago

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

Uptrenda• 9 years ago

Wow, these programs would make excellent screen savers.

Pentagon Tiling Proof Solves Century-Old Math Problem

Related Stories