On the Number of Distinct Tilings of Finite Subsets of ${\mathbb{Z}}^d$ With Tiles of Fixed Size

In this work, we study the number of finite tiles $A\subset {\mathbb{Z}}^d$ of size $\alpha$ that translationally tile a finite $C\subset {\mathbb{Z}}^d$. We consider two tiles $A$ and $A^{\mathrm{\prime }}$ to be congruent if and only if one can be transformed into the other via some translation. We make several significant contributions to the study of this problem. For any $\alpha \in {\mathbb{Z}}^{+}$ and $C=[x_1]\times [x_2]\times \dots [x_d]$ where $x_1,\dots ,x_d\in {\mathbb{Z}}^{+}$ (which we refer to as a finite contiguous $C$), we give an efficient method for enumerating all elements of $\mathcal{T}(\alpha ,C)$, where $(A,B)\in \mathcal{T}(\alpha ,C)$ if and only if $A,B\subset {\mathbb{Z}}^d$, the Minkowsji sum of $A$ and $B$ equals $C$, the size of $A$ equals $\alpha$, and $\mathrm{\mid }C\mathrm{\mid }=\alpha \mathrm{\mid }B\mathrm{\mid }$. We then use this to prove a partial order on $\mathrm{\mid }\mathcal{T}(\alpha ,C)\mathrm{\mid }$ with respect to $\alpha$ for any finite contiguous $C$. We then study the extremal question as to the the growth rate of ${\text{max}}_{\alpha ,C}[\mathrm{\mid }\mathcal{T}(\alpha ,C)\mathrm{\mid }]$ with respect to $\mathrm{\mid }C\mathrm{\mid }$. For finite contiguous $C$, we improve the trivial lower and upper bounds of $\log n$ and $\left(\genfrac{}{}{0px}{}{n}{n\mathrm{/}2}\right)$ respectively to an upper bound of $$n^{\frac{(1+\epsilon )\log n}{\log \log n}}$$ and an infinitely often super-polynomial lower bound such that, for all constants $c$ and some infinite $N\subset {\mathbb{Z}}^{+}$, $$\mathrm{\forall }n\in N,\mathrm{\exists }\alpha \in {\mathbb{Z}}^{+}(\mathrm{\mid }\mathcal{T}(\alpha ,C)\mathrm{\mid }>n^c),$$ where $n=\mathrm{\mid }C\mathrm{\mid }$. We conjecture that the number of tilings of any finite contiguous $C$ by tiles of size $\alpha$ is an upper bound on the number of tilings of any finite $C^{\mathrm{\prime }}\subset {\mathbb{Z}}^d$ by tiles of size $\alpha$. To begin working towards this, we prove that any $A$ of size $\alpha$ that tiles some finite contiguous $C$ itself has at most as many tilings by tiles of size ${\alpha }^{\mathrm{\prime }}$ as there are tilings of $[\alpha ]$ by tiles of size ${\alpha }^{\mathrm{\prime }}$.