26
$\begingroup$

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!

$\endgroup$
22
  • $\begingroup$ 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 $\endgroup$
    – Saúl RM
    Commented Apr 22, 2022 at 22:22
  • $\begingroup$ You can at least get $S_n=\Omega(n\log n)$ by a simple argument based on the rectangles. $\endgroup$ Commented Apr 23, 2022 at 1:56
  • 2
    $\begingroup$ 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 $\endgroup$
    – domotorp
    Commented Apr 23, 2022 at 5:13
  • 2
    $\begingroup$ @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. $\endgroup$
    – domotorp
    Commented Apr 23, 2022 at 8:53
  • 1
    $\begingroup$ I've asked about something similar about free polyominoes on Code Golf Stack Exchange and Math Stack Exchange. $\endgroup$ Commented Apr 24, 2022 at 2:11

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Ville Salo
    Commented May 24, 2022 at 7:30
  • $\begingroup$ @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|$. $\endgroup$
    – fedja
    Commented May 24, 2022 at 11:06
  • $\begingroup$ @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? $\endgroup$
    – fedja
    Commented May 24, 2022 at 11:11
  • $\begingroup$ 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. $\endgroup$
    – Ville Salo
    Commented May 24, 2022 at 13:17
  • $\begingroup$ 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! $\endgroup$
    – a3nm
    Commented Nov 3, 2022 at 20:23
6
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – a3nm
    Commented May 6, 2022 at 9:24
  • $\begingroup$ (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. :) $\endgroup$
    – a3nm
    Commented May 6, 2022 at 9:26
  • $\begingroup$ You are welcome! I will edit the things you mention with a bit more detail. $\endgroup$
    – Saúl RM
    Commented May 6, 2022 at 11:44
  • 1
    $\begingroup$ 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! $\endgroup$
    – a3nm
    Commented May 6, 2022 at 14:40
  • 1
    $\begingroup$ 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 $\endgroup$
    – Saúl RM
    Commented May 6, 2022 at 18:44
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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) $\endgroup$
    – a3nm
    Commented Apr 24, 2022 at 15:10
  • $\begingroup$ @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$ $\endgroup$
    – AnttiP
    Commented Apr 25, 2022 at 7:17
  • $\begingroup$ 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) $\endgroup$
    – a3nm
    Commented Apr 25, 2022 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.