# How good can a “near-miss” polyomino packing be?

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$$:

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?

• Can you elaborate a bit on the compactness argument that shows that $\Delta_n$ can't approach $1$? – Carl Schildkraut Dec 24 '20 at 1:14
• 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) – RavenclawPrefect Dec 24 '20 at 1:54
• 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) – RavenclawPrefect Dec 24 '20 at 1:55
• 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? – Carl Schildkraut Dec 24 '20 at 2:02
• Yes, exactly. Sorry if that was ambiguous! – RavenclawPrefect Dec 24 '20 at 2:02

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$$.

• 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.) – RavenclawPrefect Dec 24 '20 at 3:09
• @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? – Carl Schildkraut Dec 24 '20 at 5:15
• 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. – RavenclawPrefect Dec 24 '20 at 6:00
• @RavenclawPrefect Could you attach/give a link to your code? It might be useful to have others tinker with it. – Carl Schildkraut Dec 24 '20 at 8:34
• 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. – RavenclawPrefect Dec 24 '20 at 8:53

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."

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

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:

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:

• $$\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$$.