Infinite tiling pattern could end a 60-year mathematical quest | Hacker News Reader

Infinite tiling pattern could end a 60-year mathematical quest

nature.com

64 pointspseudolus31 comments

Open articleView on HN

Some recent and related discussions:

https://news.ycombinator.com/item?id=36119920

https://news.ycombinator.com/item?id=36056488

https://news.ycombinator.com/item?id=35273707

https://news.ycombinator.com/item?id=35264965

https://news.ycombinator.com/item?id=35242458

For real, generally curious why this little tile keeps being posted here.

Only the first link refers to this, the others are the previous "hat" tile.

A rare case of cutting edge math research, but understandable to the general public, at least in its results.

Does an aperiodic tiling mean that if you take the entire infinite tiled plane, and while sliding around a copy of the plane, there are zero other places you can slide it to that matches the original?

I'm just a bit confused by the opt-repeated claim that the tiling "never repeats itself" and I'm not sure if I'm understanding the brief translational symmetry explanation correctly.

My question is, It repeats aperiodically and predictably, like a Fibonacci ? Or aperiodically and unpredictably ? Like a prime numbers ?

It'll be predictable. Other aperiodic tilings (e.g. Penrose tiles) look to have regular patterns from a quick glance, but those patterns won't have translational symmetry despite looking vaguely symmetrical.

The proof that the tiling is aperiodic comes with a recursive algorithm for generating tilings.

The proof doesn't have to be constructive

Yeah. Its like an irrational number but in 2d.

Yes, that's the definition of aperiodic tiling.

There is no translational symmetry.

no sliding symmetry - you can combine translation and rotation, and you won't find a match.

There could be a (finite) rotational symmetry. The Penrose tilings, for example, have a five-fold rotational symmetry.

Yes, exactly.

Also this video:

https://m.youtube.com/watch?v=IfVwelta1fE

Helped me understand an example of a monotile that can tile aperiodically but also has a periodic tiling.

If that's the case, does it have practical near repeats as the difference in rotation between an selected origin tile and another tile somewhere across infinity becomes bound to approach zero? I'd have guessed that with only 360 degrees of rotation at very large numbers you'd be bound to get a tile that has nearly the same rotation if not the same rotation as another tile. I'd have guessed that for a single tile aperiodic tiling there'd be a 2nd non rotational/translational requirement: that the if rotation is the same, the adjoining tiles of every case of the same rotation would not be the same, but that seems like it'd require infinite positions for two adjacent tiles to interlock, which also seems like at some point would mean two non identical positions are functionally identical for practical purposes unless the shape allows for infinite permutations of adjacency to a single tile that aren't effectively just the same at limit. Very curious about how I'm understanding or not understanding this . Do you get large subsheets as it extends to infinity that differ distinctly from other subsheets by single tiles, with some kind of corellary that subsheets can repeat but there is no subsheet that con cover the plane in totality besides the whole itself?

Unfortunately I don't have the mathematical skill to answer these questions!

It might be worth looking at the original papers - quite readable, I understand - to see how they constructed the proof that their tiles are aperiodic. After all, you cannot just try to construct a large number of tilings and claim aperiodicity.

I would imagine (although I could be wrong) that you get an infinite number of copies of each rotation of the tile. My impression would also be that there are only a small finite number of rotations. So it is less about the rotations than the local structure around each tile not repeating, no mater how large a radius you give for your neighbourhood.

Like I say, I'm not good enough with this stuff to give a clear explanation here, sadly.

So the polygon hat from a few weeks ago only worked as an aperiodic tile if you were allowed to tile it with a flipped version? I wasn't aware of that caveat at the time. I guess that sort of detail doesn't make it into the popular press.

The cool thing is that the ratio of flipped to non-flipped is p^4, where p is the golden ratio: (1+sqrt(5))/2

[head explode emoji]

Is it that the shape can be tiled so it doesn't repeat a pattern or can you only tile it like that?

It must be the latter. Many trivial shapes admit non-periodic tilings. For example a 2x1 rectangle: you tile the plane with squares, and divide each square in two in a non-periodic way.

> and divide each square in two in a non-periodic way.

That doesn't actually sound simple. Can you provide an example of how you would do that?

You traverse the squares in a spiral pattern starting from a central one. Then each square is divided vertically or horizontally according to the binary digits of pi (or whatever).

It doesn't even need to be (pseudo-) random. You can trace a spiral pattern out from the origin like so: 1 vertical up, turn right, 1 horizontal right, turn down, 2 vertical down, turn left, 2 horizontal left, turn up, 3 vertical up, turn right, 3 horizontal right, turn down, etc. The resulting spiral pattern will never repeat.

For each 2x2 block, decide randomly/arbitrarily to split it horizontally or vertically.

This solution won't be accepted without a lot more work. Flipping a coin is not guaranteed to produce an aperiodic tiling, since, in the trivial case where the coin comes up heads indefinitely, you'll be producing a periodic tiling. (You will argue it's not likely to do this, and I'd agree. In fact, I'd conjecture you'll only produce a periodic tiling with measure zero probability.) But what's required is to actually show an aperiodic tiling. If you have a proof that coin flipping will produce such a tiling with non-vanishing probability, then, presumably, embedded in your proof, you will likely find a decision procedure for producing an aperiodic tiling deterministically.

> If you have a proof that coin flipping will produce such a tiling with non-vanishing probability, then, presumably, embedded in your proof, you will likely find a decision procedure for producing an aperiodic tiling deterministically.

I'm not sure it's obvious to expect a proof that something happens with positive probability to embed a constructive proof of existence (which seems to be what you mean). The difference between these two ideas in combinatorics is exploited with the probabilistic method (https://en.wikipedia.org/wiki/Probabilistic_method).

That makes sense but now I'm more confused about Penrose tilings. My understanding was that there were rules about placement to avoid periodic tilings.

Thinking out loud, is this down to local Vs global rules? Otherwise I'm a bit confused as to why Penrose tiles were a big deal.

To be clear, I'm fully aware the confusion is because I'm missing something.

With the Penrose tiling, you can add features to the edges of the tiles which enforce the extra placement rules, so it was the first time a set of 2 tiles which tile the plane only aperiodically was known. https://en.wikipedia.org/wiki/Penrose_tiling#Rhombus_tiling_...

Ah I see! Thanks!

An aperiodic tile (a) admits a tiling (b) does not admit a periodic tiling.

Reply on news.ycombinator.com