7
$\begingroup$

Given a polyomino $P$ with $n$ cells, we can ask about its maximal packing density $\delta_P$ in the plane (perhaps the limsup if we are concerned about convergence issues, though I don't think this actually comes up).

If $\delta_P=1$, then $P$ tiles the plane: having arbitrarily good packings implies that $P$ can cover arbitrarily large $N\times N$ squares, and from there the result follows via a compactness argument.

We can then ask: among polyominoes on $n\ge 7$ cells that do not tile the plane, which one achieves the highest density? Call this maximal value $\Delta_n$. For each $n$, $\Delta_n<1$, though of course in the limit for large $n$ it approaches $1$.

As a simple lower bound, we always have $\Delta_n\ge n/(n+1)$, as exhibited by the polyomino given by taking all but the first square in a spiral of length $n+1$ around the origin; once we plug the hole, it tiles the plane without gaps, but the hole cannot be filled. For instance, with $n=7$:

enter image description here

In contrast, putting remotely nontrivial upper bounds on $\Delta_n$ in general should be exceedingly difficult or impossible, since any computable upper bound less than 1 would yield an algorithm to decide the tiling problem for polyominoes, which is suspected not to exist. (Non-computable upper bounds on the order of $1-1/\text{BB}(k\cdot n)$ can be done, of course, but these are rather silly.)

However, improved lower bounds and exact values for small $n$ seem pretty tractable, and I'm curious what is known in this direction. Some questions:

  • Is the sequence $\Delta_7,\Delta_8,\ldots$ monotonically increasing? I suspect not.

  • When does $\Delta_n$ first exceed $n/(n+1)$? I don't actually know that it does, but I strongly suspect so for reasons described above. When $n=7$ I have not found any packings of density greater than $7/8$, although only for one of the four non-tiling heptominoes (the one pictured above) have I proven this is optimal. (All four obtain $7/8$ by adding one square to yield a tiling octomino.)

  • Can $\Delta_7$ be proven to equal $7/8$, if indeed it does so? Exhausting all tilings of an $N\times N$ square by each of the four non-tiling polyominoes and counting the max density therein would at least yield an upper bound; if $\Delta_7$ exceeds $7/8$, I would guess it does so via finding a tiling $15$-omino which is the union of two copies of a non-tiling heptomino and an additional cell.

  • [Subjective] What are some examples of interesting "near-miss" tilings?

$\endgroup$
6
  • 1
    $\begingroup$ Can you elaborate a bit on the compactness argument that shows that $\Delta_n$ can't approach $1$? $\endgroup$ – Carl Schildkraut Dec 24 '20 at 1:14
  • $\begingroup$ Yes! Suppose, for a fixed $n$, there is a polyomino $P$ that achieves arbitrarily good packings. Then for every $N$, that polyomino can cover an $N\times N$ square (if not, its density would be at most $1-1/N^2$). We can then construct a tiling of the plane by this polyomino as follows. Cover a $k\times k$ square by copies of $P$ in a way that can be extended arbitrarily far around the square (such a covering must exist, since there are arbitrarily large squares containing a $k\times k$ square in the center and only finitely many coverings to choose from - they can't all be bounded). (1/2) $\endgroup$ – RavenclawPrefect Dec 24 '20 at 1:54
  • $\begingroup$ Then, among the fintely many ways to extend this to a covering of a $(k+2)\times (k+2)$ square centered at the first square, we know at least one must extend arbitrarily far in all directions; take that extension. Repeat, at each stage fixing the previous while allowing for arbitrary further extension, and we get a tiling of the plane. (Importantly, we're requiring that the extensions be able to fully surround the current tiling in all directions at once for as far as we like; if we can extend in one direction, but are stuck in another, that's not permitted.) (2/2) $\endgroup$ – RavenclawPrefect Dec 24 '20 at 1:55
  • $\begingroup$ What does "in a way that can be extended arbitrarily far around the square" mean? Does it mean that, for all $n$, there is a way to extend it to a covering of a $(k+2n)\times (k+2n)$ square centered at that $k\times k$ square? $\endgroup$ – Carl Schildkraut Dec 24 '20 at 2:02
  • 1
    $\begingroup$ Yes, exactly. Sorry if that was ambiguous! $\endgroup$ – RavenclawPrefect Dec 24 '20 at 2:02
6
$\begingroup$

Here's a tiling of the plane using a $29$-omino that can be partitioned into $4$ heptominoes plus a single cell, giving that $\Delta_7\geq 28/29$.

tiling

$\endgroup$
5
  • 1
    $\begingroup$ Fantastic! I used some tiling software to confirm (I think) that this particular hexomino cannot cover the $37$-celled region given by a $7\times 7$ chessboard with all corners and cells edge-adjacent to a corner removed. So that bounds the density of this polyomino above by $36/37$, which annoyingly doesn't rule out a $36$-omino construction using five copies and a single hole. (I didn't try to optimize this very hard, though; it's possible much better could be done.) $\endgroup$ – RavenclawPrefect Dec 24 '20 at 3:09
  • 1
    $\begingroup$ @RavenclawPrefect Nice! It's also theoretically possible, say, for nine copies to tile a $65$-celled region with two holes to give something between $28/29$ and $35/36$, right? $\endgroup$ – Carl Schildkraut Dec 24 '20 at 5:15
  • 1
    $\begingroup$ Yeah, I think any bound of this form short of exactly $28/29$ (which might well be possible?) will leave open the possibility that any intermediate density could be achieved. $\endgroup$ – RavenclawPrefect Dec 24 '20 at 6:00
  • 1
    $\begingroup$ @RavenclawPrefect Could you attach/give a link to your code? It might be useful to have others tinker with it. $\endgroup$ – Carl Schildkraut Dec 24 '20 at 8:34
  • 1
    $\begingroup$ The code is not mine; I used the open-source software BurrTools, which allows one to build and solve tiling puzzles in 2D or 3D. I constructed a puzzle with "variable" voxels in a thick border around the shape, which can be left unfilled in a solution. The built-in algorithm was very slow without any guaranteed empty cells to go off of, however, so I manually deleted cells in the target for each of the possible positions of a piece touching the center, and checked that each of these restricted puzzles had no solutions. $\endgroup$ – RavenclawPrefect Dec 24 '20 at 8:53
3
$\begingroup$

Here's a very simple heptomino tiling that is indeed "a tiling 15-omino which is the union of two copies of a non-tiling heptomino and an additional cell."

enter image description here

$\endgroup$
1
  • $\begingroup$ Ah, thanks! I feel silly for having missed this one. So $\Delta_7\ge 14/15$; I wonder if $20/21$ can be managed. $\endgroup$ – RavenclawPrefect Dec 24 '20 at 0:15
3
$\begingroup$

After getting frustrated with existing tiling software, I coded up some simple algorithms myself, from which I can establish an upper bound of $64/65$ on $\Delta_7$.

Note that if copies of a polyomino $P$ cannot cover a region $R$ of size $k$ with no overlaps, then any packing of $P$ has density at most $1-1/k$.

Label the four non-tiling heptominoes $H_1,H_2,H_3,H_4$ in the order below:

enter image description here

Then we have (as shown via exhaustive computer search):

  • $H_1$ does not cover a $7\times 11$ rectangle with L-trominoes removed at the corners (image), and so $\delta(H_1)\le64/65$. Fascinatingly, $H_1$ does cover a $10\times 10$ square, as shown in the following rotationally symmetric configuration:

                                               enter image description here

  • $\delta(H_2)=7/8$, as discussed in the OP.

  • $H_3$ does not cover a size-$33$ region given by deleting $2\times 2$ squares from the corners of a $7\times 7$ grid, so $\delta(H_3)\le 32/33$.

  • $H_4$ does not cover a $6\times 7$ rectangle with the corners removed, so $\delta(H_4)\le 37/38$.

For all of these regions, I tried a few ways to shrink them and found tilings for every smaller region investigated. While the bounds on the other three polyominoes are reasonably close to the $28/29$ obtained by Carl Schildkraut, $H_1$ seems to present a serious obstacle. Perhaps this is because it really can tile the plane in a very dense manner not yet discovered? Either way, it seems like further investigation of $H_1$ tilings is the route to good bounds on $\Delta_7$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.