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

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!

• Seems like the "straight polyominos" (those obtained as a union of the squares touching a given segment, which need not be horizontal or vertical) should give the $\Omega(n^2)$ lower bound, I'll write something tomorrow if no one has answered that part of the question Commented Apr 22, 2022 at 22:22
• You can at least get $S_n=\Omega(n\log n)$ by a simple argument based on the rectangles. Commented Apr 23, 2022 at 1:56
• The case of the "straight polyominos" proposed by Saúl is the digital equivalent of the celebrated Kakeya problem: en.wikipedia.org/wiki/Kakeya_set Commented Apr 23, 2022 at 5:13
• @a3nm Take a nice set $S$ whose area is $<0.01n^2$ and contains a length $n$ segment in every direction. Such a set $S$ exists by the constructions given on Wikipeida for the Kakeya set. Now pixelize $S$ by checking which unit squares it intersects from the unit grid. The number of these squares is $0.01n^2 +O(n)$ as the perimeter of $S$ is nice. As $n\to \infty$, this gives an upper bound of $0.01n^2$, and we can pick $0.01$ as small as we want to. Commented Apr 23, 2022 at 8:53
• I've asked about something similar about free polyominoes on Code Golf Stack Exchange and Math Stack Exchange. Commented Apr 24, 2022 at 2:11

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)} 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.

• Could you spell out why it suffices to find a connected set of size $Cn$ which is not contained in any shift of $E$? I figured this is supposed to prove that the optimal shape inside $Cn \times Cn$ has to have large density somewhere. I see that you are individually cheating the boundedly many subrectangles, but what if the $P$ that cheats one subrectangle is covered by another? Commented May 24, 2022 at 7:30
• @VilleSalo Suppose that we have any set $E_0$ on the plane whose shifts can cover any $Cn$-mino on the plane. Then $E$ that is obtained by wrapping $E_0$ to the $n\times n$ torus should have the property that its shifts on the torus cover any $Cn$-mino contained in an $n\times n$ square placed on the torus. But we have proved that it is impossible if $E$ has fewer than $n^2/2$ cells and, obviously, $|E_0|\ge |E|$. Commented May 24, 2022 at 11:06
• @VilleSalo As to the second question, $P_K$ only has the property that every shift $E'$ of $E$ cannot fill at least one of the squares $Q_K$ but which one depends on the shift. Or, perhaps, I misunderstand what you are asking there? Commented May 24, 2022 at 11:11
• Oh, duh. I guess in terms of how I imagined this, the short explanation is you do not cheat the finitely many subrectangles separately, you cheat their union. Commented May 24, 2022 at 13:17
• I am very late in reacting to this, but thanks for your answer. I did not redo the calculations but I think I see the overall idea. It is a very nice argument, and very striking that this can be shown to be $\Theta(n^2)$. Thanks a lot for your work!
– a3nm
Commented Nov 3, 2022 at 20:23

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.

• Thanks a lot! Points that confused me: (i) "two of them must be" in the lemma is by the pigeonhole principle on squares of side sqrt(l). (ii) The lemma says that the polyomino contains all points $x_i, y_i$, but you use it to get polyominos $p_C$ whose intersection with the set $B$ is exactly some subset $C$. For this you need to ensure that the polyomino given by the lemma doesn't contain other points from $B$. I guess this is doable without increasing the length too much: none of the neighbors of squares in $B$ are in $B$ by the "even" requirement so you can work around them.
– a3nm
Commented May 6, 2022 at 9:24
• (iii) The "Thus $P_{A-a}$" is because, if a polyomino is in $P_{A-a}$, then its intersection with B is a subset of $(A-a) \cap B$. (iv) unfortunately I didn't get the very last step; after the "As when $n$ is big" I don't see why this can derive the bound that follows and gives the contradiction? Other than that I was able to follow the argument at a high level (I didn't check the precise calculations), I think I got the idea. This is very elegant and not at all the kind of techniques I would be used to. Thanks again. :)
– a3nm
Commented May 6, 2022 at 9:26
• You are welcome! I will edit the things you mention with a bit more detail. Commented May 6, 2022 at 11:44
• Yeah my point is that you can consider the balls for Manhattan distance, which seems to make more intuitive sense given that the polynomino lengths follow the Manhattan distance. But I agree that this works no matter the distance up to changing the constants. Thanks a lot again for the insights!
– a3nm
Commented May 6, 2022 at 14:40
• You are right, I edited that. I wanted to use the "normal" distance but I guess if someone reaches that point of the proof they won't be scared of an $L1$ norm Commented May 6, 2022 at 18:44

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

• Thanks for the proof! this looks convincing to me except that I don't get how $x≈n^{1−1/k}$ is derived from the previous inequality (which property of the binomial coefficient do you use for this?). Other than that, the one-dimensional non-connected case looks already interesting, it looks like the problem of sparse rulers which is already studied en.wikipedia.org/wiki/Sparse_ruler (and for which we may get more precise asymptotics)
– a3nm
Commented Apr 24, 2022 at 15:10
• @a3nm Yes, it seems that for $k=2$ the sparse rulers are the optimal embedding. But anyways, the bound can be derived from the fact that for a fixed $k$, ${n \choose k}$ is a polynomial of degree $k$. Thus $\frac{{n \choose k}}{n}$ is approximately a polynomial of degree $k-1$. Now we want to find some function $f(n)$ so that ${f(n) \choose k}$ grows like a polynomial of degree $k-1$. This means that $f(n)$ has to grow like a polynomial of degree ${1-\frac{1}{k}}$ since if you multiply that by $k$ you get the desired growth rate of $k-1$ Commented Apr 25, 2022 at 7:17
• I see, this makes sense, thanks a lot for explaining. And thanks for clarifying that the connection to sparse rulers is only for k=2 -- I don't know if there is an analogous notion for all k-tuples with maximal separation $\leq n$. (Here as in your post "maximal separation" is the maximal total span, i.e., the difference between the min and max)
– a3nm
Commented Apr 25, 2022 at 9:56