21
$\begingroup$

An animal in the plane is a finite set of grid-aligned unit squares in $\mathbb{R}^2$. (The definition is the same as a polyomino, but where we relax the connectivity requirement.) One may equivalently think of them as finite subsets of $\mathbb{Z}^2$.

In Erich Friedman’s investigation of tilings of rectangles by 1D animals, it is mentioned offhandedly that Coppersmith showed every 4-celled animal tiles the plane in 1985 (and can do so without reflections); I was able to locate the paper at Coppersmith - Each four-celled animal tiles the plane (link to PDF). 6-celled animals do not, in general, since they can have a hole:

6-celled animal with hole

Has any progress been made on the 5-cell case since 1985 (either with or without reflections permitted)? I'd be interested in computational results as well, e.g. "every size-5 subset of a $7\times 7$ grid tiles the plane". (I have confirmed that every size-5 subset of a $3\times 3$ grid tiles the plane, and every size-5 subset of a $4\times 4$ grid at least covers a $10\times 10$ square.)

Since I realize the answer to this question may well be "no further progress has been made and the problem is difficult", I'm interested in any statements that can be made about restrictions of this problem to natural subcases. For instance:

  • Can every size-5 subset of $\mathbb{Z}$ tile the plane? Of $\mathbb{Z}\times \{0,1\}$?

  • I didn't specify above, but one can consider whether reflections are allowed in a tiling or not. If so, a proof may be easier (it seems Coppersmith restricted himself to the rotation case), and if not, a counterexample might be more tractable.

  • Is there expert consensus on what the likely answer is?

Previously on math.SE here, without any progress on the question.

Edit 2021-05-04: I contacted Dr. Coppersmith about the problem, and he wasn't aware of any further research in this direction.

Improve this question
$\endgroup$
7
  • $\begingroup$ At this writing, there is still an active bounty on the question at m.se. $\endgroup$
    – Gerry Myerson
    Commented Jan 5, 2021 at 22:27
  • 4
    $\begingroup$ I asked a different but somewhat related question which was solved by Vytautas Gruslys, Imre Leader, and Ta Sheng Tan. Perhaps they may have some insight into this problem. For example, in their paper they mention that the 6-celled animal XXX.XXX does not tile the plane even though the hole is not completely enclosed. $\endgroup$
    – Timothy Chow
    Commented Jan 5, 2021 at 22:41
  • 1
    $\begingroup$ Try $2 \times 2$-box plus one cell disconnected from the box. $\endgroup$
    – markvs
    Commented Jan 6, 2021 at 5:12
  • 4
    $\begingroup$ If the one cell is diagonally adjacent, this tiles the plane (as mentioned in the OP, I have checked all subsets of a $3\times 3$ grid); see here for a computer-generated covering of a $12\times 12$ square which should make clear how the tiling works. Checking several other positions of the additional cell, they all seem to work. $\endgroup$
    – RavenclawPrefect
    Commented Jan 6, 2021 at 6:30
  • 1
    $\begingroup$ @MarkSapir I think that I can prove that every animal of the form 2x2-box plus disconnected cell tiles the plane (using translations and 180 rotations only). Essentially, my strategy is to show that these animals tile a "jagged strip" whose two boundaries have infinite-dihedral symmetry. $\endgroup$
    – André Henriques
    Commented May 4, 2021 at 22:22

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .