Skip to main content
2 of 6
added 535 characters in body
Saúl RM
  • 10.6k
  • 2
  • 28
  • 48

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 $(x_i,y_i)_{i=1}^l$ contained in a square of side $k$, there is a polyomino of length $<10k\sqrt{l}$ containing all the points $x_i,y_i$.

Proof: The statement is true if $l=1$, so we can use induction on $l$. If we have $l+1$ points inside a square of length $k$, then two of them must be at distance $\leq\frac{2k}{\sqrt{l}}$, so we can join them using $<4\frac{k}{\sqrt{l}}$ squares, and now we use that $10k\sqrt{l}+4\frac{k}{\sqrt{l}}<10k\sqrt{l+1}.\square$

So for each subset $C$ of $B$ with $\lfloor\log(n)\rfloor$ elements we can choose a $n$-polyomino $p_C$ with $p_C\cap B=C$. 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{\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))}$. As when $n$ is big, $\frac{\log(n)}{\#B}\to0$,

$\frac{\#P_{A-a}}{\#P}<\left(\frac{1}{99}\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.

Saúl RM
  • 10.6k
  • 2
  • 28
  • 48