What is the smallest size of a shape in which all fixed $n$-polyominos can fit?

Question

Let $n$ be an integer and consider all fixed $n$-polyominos, i.e., without rotation or reflection. I am interested in finding a shape in which all polyominos can embed. (It is OK if multiple polyominos overlap.)

For instance, for $n=3$, the fixed 3-polyominos are:

###  #..  ##.  ##.  #..  .#.
...  #..  #..  .#.  ##.  ##.
...  #..  ...  ...  ...  ...

and these polyominos all embed in the following shape with 5 cells, which is the best possible:

.#.
###
.#.

More generally, a suitable shape for arbitrary $n$ is the $n \times n$ square (with $n^2$ cells) and a naive lower bound would be $2n-1$ cells (necessary to embed the horizontal and vertical line $n$-polyomino).

I define an integer sequence $S_n$ to be the minimal number of cells of a shape in which all $n$-polyominos embed, and I am interested in understanding this sequence. In particular, specific questions are:

• Can we always find an optimal shape that fits into an $n \times n$ square? (this seems intuitively reasonable but I do not know how to prove it)
• Can we prove that, asymptotically, $S_n = \Theta(n^2)$? (the challenge is to show an $\Omega(n^2)$ lower bound -- maybe this is already possible by simply looking at a subset of the polyominos, but I couldn't see how to do it)

More generally, has this sequence already been studied?

To understand what happens here, I was able to compute by bruteforce computer search the first values of $S_n$, making the assumption that optimal shapes always fit in an $n$ by $n$ square (first point above) -- these values may turn out not to be optimal if this assumption is wrong:

• We have $S_1 = 1$, $S_2 = 3$ (easily), and $S_3 = 5$ (see above)
• We have $S_4=9$ with a surprising shape:

..#.
.##.
####
.##.

• We have $S_5 = 13$, with the unsurprising shape:

..#..
.###.
#####
.###.
..#..

• We have $S_6 = 18$ with a surprising shape:

..##..
..##..
######
#####.
..##..
..#...

• We have $S_7 = 24$, the shape is similar to $n=5$ but with a hole:

...#...
..###..
.#.###.
#######
.#####.
..###..
...#...

• I do not know $S_8$

There are matching sequences for these terms in OEIS, but their definitions do not seem relevant... Edit: maybe https://oeis.org/A203567 https://www.sciencedirect.com/science/article/pii/S0012365X01003570 would be worth investigating.

Acknowledgement: This question is by Thomas Colcombet and Antonio Casares.

Edit: fixed the values of $S_5$ and $S_7$, many thanks to @RobPratt for noticing and reporting the errors!

Answer 1

It is actually $\ge cn^2$ with some $c>0$. The value of $c$ I'll obtain is pretty dismal but I tried to trade the precision for the argument simplicity everywhere I could, so it can be certainly improved quite a bit. I have no doubt that it is written somewhere (perhaps, in the continuous form: the $2$-dimensional measure of a set containing a shift of every rectifiable curve of length $1$ is at least some positive constant) but I'll leave it to more educated people to provide the reference.

We shall work on the 2D $n\times n$ lattice torus $T$ whose size $n$ is a power of $2$. Clearly, wrapping around makes the set only smaller. Define $K$ to be the integer such that $2^{K^3+K}\le n< 2^{(K+1)^3+K+1}$ (I assume that $n$ is large enough, so $K$ is not too small either).

Put $\varepsilon_k=2^{-k}, M_k=2^{k^3}$ ($k\ge 4$). Note that $\frac 12+3\sum_{k\ge 4}\varepsilon_k=\frac 78<1$. Put $\mu_k=\frac 12+3\sum_{m=4}^{k}\varepsilon_m$ (so $\mu_3=\frac 12$).

Now take any set $E\subset T$ of density $d(E,T)=\frac{|E|}{|T|}=1/2$. Our aim will be to construct a connected set $P$ of cardinality $|P|\le Cn$ such that no its lattice shift of $E$ on $T$ contains $P$.

Start with dividing $T$ into $M_4^2$ equal squares $Q_4$. Notice that the portion of squares $Q_4$ with density $d(E,Q_4)=\frac{|E\cap Q_4|}{|Q_4|}>\mu_3+\varepsilon_4$ is at most $\mu_3/(\mu_3+\varepsilon_4)\le 1-\varepsilon_4$. Now choose $N_4=\frac{2\log_2 (M_4/\varepsilon_4)}{\varepsilon_4}=2\cdot(4^3+4)\cdot 2^4$ squares $Q_4$ independently at random. The probability that none of them has density $d(E,Q_4)\le \mu_3+\varepsilon_4$ is at most $(1-\varepsilon_4)^{N_4}< \left(\frac{\varepsilon_4}{M_4}\right)^2$. This means that if we consider not only the standard partition but also all its shifts $E'$ by multiples of $\varepsilon_4 n/M_4$, then there exists a configuration $P_4$ of $N_4$ squares $Q_4$ such that for each such shift, the density of $E'$ in at least one square $Q_4$ in $P_4$ is $d(E',Q_4)\le \mu_3+\varepsilon_4$. However, every lattice shift can be approximated by such shifts with precision $\varepsilon_4 n/M_4=\varepsilon_4\ell(Q_4)$, so we conclude that for any shift $E'$ of $E$, the configuration $P_4$ contains a square $Q_4$ with density $d(E',Q_4)\le\mu_3+3\varepsilon_4=\mu_4$.

Our $P$ will be essentially contained in $\bigcup_{Q_4\in P_4}Q_4$. Notice that we can construct some set in each square $Q_4$ and the cost of joining them afterwords will be at most $ 2n N_4 $. Notice also that the sidelength $\ell(Q_4)$ of each $Q_4$ is $n/M_4$.

Now partition the torus into $M_5^2$ equal squares $Q_5$ and consider shifts by multiples of $\varepsilon_5 n/M_5$. Fix one square $Q_4\in P_4$ and choose $N_5=\frac{2\log_2 (M_5/\varepsilon_5)}{\varepsilon_5}=2\cdot(5^3+5)\cdot 2^5$ independent random squares in it creating some configuration $P'_5$. Repeat the same configuration in all other squares $Q_4$ to get a configuration $P_5$ of $N_4N_5$ squares $Q_5$ with sidelength $\ell(Q_5)=n/M_5$. Since for all such shifts at least one square $Q_4$ in $P_4$ satisfies $d(E',Q_4)\le\mu_4$, the same probabilistic argument results in the conclusion that one can choose $P_5'$ so that for every shift $E'$ by multiples of $\varepsilon_5n/M_5$ there will be a square $Q_5$ in $P_5$ with $d(E',Q_5)\le\mu_4+\varepsilon_5$, which, by approximation, yields again that for every shift $E'$ we shall have some $Q_5\in P_5$ with $d(E',Q_5)\le\mu_5$. The extra joining cost is now $2nN_4N_5/M_4$.

Continue the same way until we reach $P_K$ consisting of $N_4\dots N_K$ squares $Q_K$ of sidelength $n/M_K\le 2^{3K^2+4K+2}$. Now just fill these squares completely. This will create $$ 2^{O(K^2)}N_4\dots N_K\le 2^{O(K^2)}N_K^K=2^{O(K^2)}[2(K^3+K)2^K]^K=2^{O(K^2)}<Cn $$ cells out of which one is not covered for any shift of $E$.

It remains to estimate the joining cost. It is $2n$ times the series whose general term is (putting $M_3=1$) $$ \frac{N_4\dots N_k}{M_{k-1}}\le\frac{N_k^k}{M_{k-1}}=\frac{2^{O(k^2)}}{2^{(k-1)^3}}\, $$ so we are fine again.

This construction is a bit cumbersome and rather unpleasant to write down (though the idea is fairly simple), so I apologize in advance for somewhat awkward exposition. As usual, feel free to ask questions if something is unclear.

Answer 2

It seems $S_n$ is $\geq\displaystyle\Theta\left(\frac{n^2}{\log(n)}\right)$.

In the following, I will consider polyominos as subsets of $\mathbb{Z}^2$ (so, a polyomino is represented by the set of centers of its squares). Thus two polyominos which are translates of each other will be considered different.

Fix $n$ and let $P$ be a set of $n$-polyominos which contain the point $0\in\mathbb{Z}^2$ (we will specify $P$ later). For any $X\subseteq\mathbb{Z}^2$, we define $P_X=\{p\in P;p\subseteq X\}$. Then the set of polyominos of $P$ such that some translate of them is contained in $X$ will be $\bigcup_{x\in X}P_{X-x}$.

If $A\subset\mathbb{Z}^2$ is a set which contains some translate of all polyominos of $P$, then $P=\bigcup_{a\in A}P_{A-a}$. So for some $a\in A$, $\#P_{A-a}\geq\frac{\#P}{\#A}$. So if we want $A$ to have few elements, $P_{A-a}$ will contain a lot of polyominos. This in turn can be used to obtain a lower bound for $\#A$.

Now let's define our specific choice of the set $P$.

Let $B=\{(x,y)\in\mathbb{Z}^2;x,y\text{ are even};|x|,|y|<\frac{n}{20\sqrt{\log(n)}}\}$, so $\#B=\left(1+2\lfloor\frac{n}{40\sqrt{\log(n)}}\rfloor\right)^2$.

We will need a lemma:

Lemma: Given $l$ points $p_i=(x_i,y_i)_{i=1}^l$ contained in a square $Q$ of side $k$, there is a polyomino of length $<10k\sqrt{l}$ containing all the points $p_i$.

Proof: The statement is true if $l=1$, so we can use induction on $l$. If we have $l+1$ points inside $Q$, then two of them, which we call $p_0,p_1$, must be at distance $<\frac{3k}{\sqrt{l}}$: if not, the $L_1$ balls of center $p_i$ and radius $\frac{3k}{2\sqrt{l}}$ would be disjoint, so as each ball intersects $Q$ in at least a quarter of its area, the area of $Q$ would be $\geq l\cdot\frac{9k^2}{8l}>k^2$, a contradiction.

So we can join the points $p_0,p_1$ using a polyomino of $<4\frac{k}{\sqrt{l}}$ squares, and now we use that $10k\sqrt{l}+4\frac{k}{\sqrt{l}}<10k\sqrt{l+1}.\square$

Now suppose we have a subset $C$ of $B$ with $\lfloor\log(n)\rfloor$ elements. As in the lemma above, we can choose a $n$-polyomino $p_C$ with $p_C\cap B=C$: the proof is the same as the proof of the lemma except that we have to make sure the polyomino joining $p_0$ to $p_1$ is disjoint from $B$ except in the ends. This adds at most $2$ squares to the polyomino, so the bounds from the lemma still work.

We will let $P=\{p_C;C\subseteq B,\# C=\lfloor\log(n)\rfloor\}$, so $\#P=\binom{\#B}{\lfloor\log(n)\rfloor}$.

Now suppose $A\subseteq\mathbb{Z}^2$ contains translates of all the polyominos of $P$ and $\#A<\frac{n^2}{10^{10}\log(n)}$. Then, for some $a\in A$ we have $\#P_{A-a}\geq\frac{\#P}{n^2}$. But on the other hand, $\#(A-a)\cap B\leq\#A<\lfloor\frac{\#B}{100}\rfloor$. Thus $P_{A-a}$ has $\binom{\#((A-a)\cap B)}{\lfloor\log(n)\rfloor}<\binom{\lfloor\frac{\#B}{100}\rfloor}{\lfloor\log(n)\rfloor}$ elements.

So $\frac{\#P_{A-a}}{\#P}<\frac{\binom{\lfloor\frac{\#B}{100}\rfloor}{\lfloor\log(n)\rfloor}}{\binom{\#B}{\lfloor\log(n)\rfloor}} = \frac{\lfloor\frac{\#B}{100}\rfloor\left(\lfloor\frac{\#B}{100}\rfloor-1\right)\dots\left(\lfloor\frac{\#B}{100}\rfloor-\lfloor\log(n)\rfloor+1\right)}{\#B(\#B-1)\dots(\#B-\lfloor\log(n)\rfloor+1))}$.

Moreover, as $\lfloor\frac{\#B}{100}\rfloor<\#B$, for any $i=0,\dots,\lfloor\log(n)\rfloor-1$ we have $\frac{\lfloor\frac{\#B}{100}\rfloor-i}{\#B-i}\leq\frac{\lfloor\frac{\#B}{100}\rfloor}{\#B}\leq\frac{1}{100}$

So $\frac{\#P_{A-a}}{\#P}\leq\left(\frac{1}{100}\right)^{\lfloor\log(n)\rfloor}<\frac{1}{n^2}$, a contradiction.

Maybe a better choice of $P$ or other changes to this method could improve the bound on the asymptotic growth of $S_n$ a bit more.

Answer 3

Proof outline for $\Omega(n^{2-\varepsilon})$

Choose a positive integer $k$ which will determine that $\varepsilon=\frac{1}{k}$.

Now consider the problem of embedding the 1 dimensional $k$-block shapes, where the maximum separation is $n$. For example, with $n=4$ and $k=2$ we can do the following:

   xx
  x x
x  x
x   x

E EEE

^{(Here E denotes the embedding and the rows containing x's are the 1D $k$-block shapes)}

This uses only 4 blocks, instead of the naïve 5 blocks. There is a relatively simple combinatorial lower bound on the size of the minimal embedding, which is roughly $n^{1-\frac{1}{k}}$.

This bound can be derived from the fact that we have roughly $\frac{{n \choose k}}{n}$ unique shapes. If $x$ is the size of the embedding, then $\frac{{n \choose k}}{n}\le{x \choose k}$ and thus a lower bound for $x$ is $x\approx n^{1-\frac{1}{k}}$

Now we just extend this to 2 dimensions.

For example, we can turn x x x ($n=6$,$k=3$) into the following polymino

x   x x
x   x x
xxxxxxx
x   x x
x   x x
x   x x

Note that the height is equal to $n$. The number of blocks required depends linearly on n, since k is fixed.

Now, we know that every row will have an amount of blocks (at least) proportional to $n^{1-1/k}$ and the amount of rows will be proportional to $n$, which means that the number of blocks in the polymino embedding must (roughly) be at least $n\cdot n^{1-1/k}=n^{2-\varepsilon}$.

It should be noted that vertical translations are not really useful when restricted to the aforementioned polyminoes. This should be intuitively obvious.