Paperlane

no. 15 · Monday 16 November 2026

Two Tiling is Undecidable

Jack Stade

math.CO · v2 · 38 pp

Abstract

We show that the following problem is undecidable: given two polygonal prototiles, determine whether the plane can be tiled with rotated and translated copies of them. This improves a result of Demaine and Langerman [SoCG 2025], who showed undecidability for three tiles. Along the way, we show that tiling with one prototile is undecidable if there can be edge-to-edge matching rules. This is the first result to show undecidability for monotiling with only local matching constraints.

comments
38 pages, 48 figures
fields
Combinatorics, Metric Geometry
pdf ↗ page arXiv:2506.11628 ↗