3
$\begingroup$

I am interested in the following question.

Are there nice characterizations of the finite sets $S\subseteq \mathbb{Z}\times\mathbb{Z}$ that tile $ \mathbb{Z}\times\mathbb{Z}$ by translations (i.e. $\mathbb{Z}\times\mathbb{Z}$ can be written as a disjoint of some translates of $S$)?

If nothing is known in general, is there anything known for some special family of interesting point sets, e.g. the convex hull of $S$ is a regular (or general) convex polygon, or points in $S$ consists of the vertices/boundary-points of a regular convex polygon?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ The only regular polygons with vertices in $\mathbb{Z}\times \mathbb{Z}$ are squares. $\endgroup$
    – Richard Stanley
    Commented Oct 25, 2022 at 18:26

1 Answer 1

Reset to default
5
$\begingroup$

Every such $S$ has a periodic tiling, in which finitely many disjoint copies form a set with one representative for each translate of some discrete lattice $L$ - see Bhattacharya 2016 or Greenfeld and Tao 2020. If $S$ is edge-connected, one can further guarantee that $S$ itself (rather than a finite number of copies) has a lattice tiling - see Wijshoff and van Leeuwen 1984 - in which case the characterization is more concrete, as every such $S$ is given by the construction of picking a lattice and selecting a representative from each of its translates (and the decision problem is fairly computationally straightforward, taking time quadratic in the length of the boundary word).

For an example of a disconnected $S$ that cannot form a lattice tiling, consider $\{(0,0),(2,0)\}$; it requires two copies to form a patch that tiles by lattice translation.

I'm not sure you'll be able to get much more than this. The structure of tiling problems in $\mathbb{Z}^d$ even in the single-tile case is in general difficult, and for sufficiently high $d$ loses the periodicity condition as recently shown in Greenfeld and Tao 2022 - see this blog post. And with more than one tile, the problem is known to become undecidable - for sufficiently high $d$ with two tiles, and already in two dimensions with $11$ tiles as shown in Ollinger 2008.

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ Even the one-dimensional finite problem of determining all the sets that tile a given cyclic group ${\bf Z}/N{\bf Z}$ is difficult; the main conjecture in this area is the Coven-Meyerowitz conjecture mathscinet.ams.org/mathscinet-getitem?mr=1670646 which remains open in general, though has been some recent progress by Laba and Londner, see e.g., arxiv.org/abs/2207.11809 $\endgroup$
    – Terry Tao
    Commented Oct 26, 2022 at 1:34
  • $\begingroup$ Surely $S=\{\langle 0,0\rangle, \langle 1,0\rangle, \langle 3,0\rangle\}$ can't tile $\mathbb{Z}\times\mathbb{Z}$ by translation? If it could then $\{0, 1, 3\}$ would translate $\mathbb{Z}$ by translation and this is clearly impossible. $\endgroup$
    – Steven Stadnicki
    Commented Oct 26, 2022 at 2:42
  • $\begingroup$ "The structure of tiling problems in $\mathbb{Z}^d$ even in the single-tile case is in general difficult, and undecidable for sufficiently high $d$ as recently shown in Greenfeld and Tao 2022 - see this blog post." is this really claimed by Greenfeld-Tao? I thought they have is a single aperiodic (singleton) tileset. $\endgroup$
    – Ville Salo
    Commented Oct 26, 2022 at 4:07
  • $\begingroup$ They explicitly say they don't address decidability issues, so hard to say whether they know how to get undecidability, but it does not look like they have a general "monotilification result" that turns anything into a single tile, and aperiodicity doesn't directly imply undecidability. Well, I see that @TerryTao has commented above already, maybe they know more than me. $\endgroup$
    – Ville Salo
    Commented Oct 26, 2022 at 4:12
  • 2
    $\begingroup$ Our methods are currently only able to demonstrate aperiodicity in high dimensions for tiling with one tile, and undecidability in high dimensions for the problem of tiling with two tiles. It seems reasonable to conjecture though that the problem of tiling with one tile is also undecidable in high dimensions. $\endgroup$
    – Terry Tao
    Commented Oct 26, 2022 at 4:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .