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](https://www.irif.fr/%7Ecolcombe/) and [Antonio Casares](https://www.labri.fr/perso/acasaressant/).


**Edit:** fixed the values of $S\_5$ and $S\_7$, many thanks to @RobPratt for noticing and reporting the errors!



What is the smallest size of a shape in which all fixed $n$-polyominos can fit?
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.


