What type of study is this?

This is a Quantitative Study study.

October 2, 2025Open Access

Undecidability of Translational Tiling of the Plane with Four Tiles

Key Points

Translational tiling with four tiles is shown to be undecidable, expanding on previous findings.
The main result reveals that the number of polyominoes needed for undecidability can be minimized to four.
This research builds upon earlier work that reduced necessary polyominoes from 11 to 5, highlighting accrued advancements.
The findings contribute to combinatorial complexity, suggesting further implications in discrete geometry.

Abstract

The translational tiling problem, dated back to Wang's domino problem in the 1960s, is one of the most representative undecidable problems in the field of discrete geometry and combinatorics. Ollinger initiated the study of the undecidability of translational tiling with a fixed number of tiles in 2009, and proved that translational tiling of the plane with a set of 11 polyominoes is undecidable. The number of polyominoes needed to obtain undecidability was reduced from 11 to 7 by Yang and Zhang, and then to 5 by Kim. We show that translational tiling of the plane with a set of 4 (disconnected) polyominoes is undecidable in this paper.

Undecidability of Translational Tiling of the Plane with Four Tiles

Key Points

Abstract

Cite This Study