<p>Can we decide whether a given polygon can tile the whole plane?<br />
First, let me briefly summarize what is known about this problem.<br />
If we only allow translations, then the problem is always decidable in the plane (<a href="https://arxiv.org/abs/1602.05738" rel="nofollow noreferrer">Bhattacharya</a>), but not in higher dimensions (<a href="https://arxiv.org/abs/2309.09504" rel="nofollow noreferrer">Greenfeld, Tao</a>).<br />
From now on, I assume that rotations are also allowed.<br />
It is well-known that every triangle and quadrilateral tiles the plane.<br />
A complete classification of pentagons is known (<a href="https://arxiv.org/abs/1708.00274" rel="nofollow noreferrer">Rao</a>).<br />
Recently, a 13-gon (<a href="https://If%20we%20only%20allow%20translations,%20then%20the%20problem%20is%20always%20decidable%20in%20the%20plane%20(%5BBhattacharya%5D%5B1%5D)" rel="nofollow noreferrer">the hat</a>) was found that tiles the plane only aperiodically.</p>
<p>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.<br />
So is there anything known about this problem for some k more than five?</p>
<p>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:
<a href="https://cstheory.stackexchange.com/questions/32538/is-it-decidable-to-determine-if-a-given-shape-can-tile-the-plane">Is it decidable to determine if a given shape can tile the plane?</a></p>

CC BY-SA 4.0
2024-03-22T12:45:21.560Z
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
CC BY-SA 4.0
2024-03-22T14:39:58.503Z
@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
CC BY-SA 4.0
2024-03-22T15:05:57.343Z
The [Conway criterion](https://en.wikipedia.org/wiki/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
CC BY-SA 4.0
2024-03-22T18:28:19.917Z
Yes, this is included in your answer to the other question I've linked to at the end.
domotorp
<undecidability><tilings>
For which k can we decide whether an input k-gon tiles?
domotorp
# For which k can we decide whether an input k-gon tiles?

(Asked by: username_0 on 2024-03-22)

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](https://arxiv.org/abs/1602.05738)), but not in higher dimensions ([Greenfeld, Tao](https://arxiv.org/abs/2309.09504)).  
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](https://arxiv.org/abs/1708.00274)).  
Recently, a 13-gon ([the hat](https://If%20we%20only%20allow%20translations,%20then%20the%20problem%20is%20always%20decidable%20in%20the%20plane%20(%5BBhattacharya%5D%5B1%5D))) 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?](https://cstheory.stackexchange.com/questions/32538/is-it-decidable-to-determine-if-a-given-shape-can-tile-the-plane)

**Tags:** undecidability, tilings

> **Comments:**
> **username_1**: 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?  
> **username_2**: @EmilJeřábek two spaces at the end of a line (a commonly used trick for web text editors that are rendered in html).  
> **username_2**: The [Conway criterion](https://en.wikipedia.org/wiki/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)" .  
> **username_0**: Yes, this is included in your answer to the other question I've linked to at the end.  

---

## 0 answers

