How good can a "near-miss" polyomino packing be?

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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