Return to Answer

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 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 a square of length $k$, then two of them, which we call $p_0,p_1$, must be at distance $\leq\frac{3k}{\sqrt{l}}$: if not, the balls of center $p_i$ and radius $\frac{3k}{2\sqrt{l}}$ would be disjoint, so the area of the square of side $k$ would be $\geq\frac{9\pi}{16}\frac{k^2}{l} l>k^2$ (because each ball intersects the square in at least a quarter of its area), which is a contradiction.

So we can join the points $p_0,p_1$ using a polyomino of $<4.5\frac{k}{\sqrt{l}}$ squares, and now we use that $10k\sqrt{l}+4.5\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.

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.

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 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 a square of length $k$, then two of them, which we call $p_0,p_1$, must be at distance $\leq\frac{3k}{\sqrt{l}}$: if not, the balls of center $p_i$ and radius $\frac{3k}{2\sqrt{l}}$ would be disjoint, so the area of the square of side $k$ would be $\geq\frac{9\pi}{16}\frac{k^2}{l} l>k^2$ (because each ball intersects the square in at least a quarter of its area), which is a contradiction.

So we can join the points $p_0,p_1$ using a polyomino of $<4.5\frac{k}{\sqrt{l}}$ squares, and now we use that $10k\sqrt{l}+4.5\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$. 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.

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 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 a square of length $k$, then two of them, which we call $p_0,p_1$, must be at distance $\leq\frac{3k}{\sqrt{l}}$: if not, the balls of center $p_i$ and radius $\frac{3k}{2\sqrt{l}}$ would be disjoint, so the area of the square of side $k$ would be $\geq\frac{9\pi}{16}\frac{k^2}{l} l>k^2$ (because each ball intersects the square in at least a quarter of its area), which is a contradiction.

So we can join the points $p_0,p_1$ using a polyomino of $<4.5\frac{k}{\sqrt{l}}$ squares, and now we use that $10k\sqrt{l}+4.5\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.

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 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 a square of length $k$, then two of them, which we call $p_0,p_1$, must be at distance $\leq\frac{3k}{\sqrt{l}}$: if not, the balls of center $p_i$ and radius $\frac{3k}{2\sqrt{l}}$ would be disjoint, so the area of the square of side $k$ would be $\geq\frac{9\pi}{16}\frac{k^2}{l} l>k^2$ (because each ball intersects the square in at least a quarter of its area), which is a contradiction.

So we can join the points $p_0,p_1$ using a polyomino of $<4.5\frac{k}{\sqrt{l}}$ squares, and now we use that $10k\sqrt{l}+4.5\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$. 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))}$.

And when $n$ is big, $\frac{\log(n)}{\#B}\to0$, so for all $i=0,1,\dots,\lfloor\log(n)\rfloor-1$, $\frac{\lfloor\frac{\#B}{100}\rfloor-i}{\#B-i}<\frac{1}{99}$. So

$\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.

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 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 a square of length $k$, then two of them, which we call $p_0,p_1$, must be at distance $\leq\frac{3k}{\sqrt{l}}$: if not, the balls of center $p_i$ and radius $\frac{3k}{2\sqrt{l}}$ would be disjoint, so the area of the square of side $k$ would be $\geq\frac{9\pi}{16}\frac{k^2}{l} l>k^2$ (because each ball intersects the square in at least a quarter of its area), which is a contradiction.

So we can join the points $p_0,p_1$ using a polyomino of $<4.5\frac{k}{\sqrt{l}}$ squares, and now we use that $10k\sqrt{l}+4.5\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$. 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.