0

Can we decide whether a given polygon can tile the whole plane?
First, let me briefly summarize what is known about this problem.
If we only allow translations, then the problem is always decidable in the plane (Bhattacharya), but not in higher dimensions (Greenfeld, Tao).
From now on, I assume that rotations are also allowed.
It is well-known that every triangle and quadrilateral tiles the plane.
A complete classification of pentagons is known (Rao).
Recently, a 13-gon (the hat) was found that tiles the plane only aperiodically.

This last result suggests that it might be undecidable whether an input k-gon can tile the plane if k is large enough, but I don't think a proof follows directly.
So is there anything known about this problem for some k more than five?

ps. My question is a special case of this earlier question posed here before the recent breakthroughs, the answers to it are full of excellent links to earlier works on the topic: Is it decidable to determine if a given shape can tile the plane?

domotorp
  • 13,931
  • 37
  • 93
  • I’m curious: how did you manage to format the post so that there are hard line breaks, even though no <br> tags are visible in the source? – Emil Jeřábek Mar 22 '24 at 12:45
  • 1
    @EmilJeřábek two spaces at the end of a line (a commonly used trick for web text editors that are rendered in html). – Marzio De Biasi Mar 22 '24 at 14:39
  • The Conway criterion gives a sufficient (but not necessary) condition. Everything is known about convex polygons (>=7 sides don't tile the plane). Perhaps the closest result gotten so far is in "One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece (2012)" . – Marzio De Biasi Mar 22 '24 at 15:05
  • Yes, this is included in your answer to the other question I've linked to at the end. – domotorp Mar 22 '24 at 18:28

0 Answers0