Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes

Autor: Gill Barequet, Mira Shalah
Rok vydání: 2022
Předmět:
Zdroj: Algorithmica. 84:3559-3586
ISSN: 1432-0541
0178-4617
DOI: 10.1007/s00453-022-00948-6
Popis: A $d$-dimensional polycube is a facet-connected set of cells (cubes) on the $d$-dimensional cubical lattice $\mathbb{Z}^d$. Let $A_d(n)$ denote the number of $d$-dimensional polycubes (distinct up to translations) with $n$ cubes, and $\lambda_d$ denote the limit of the ratio $A_d(n{+}1)/A_d(n)$ as $n \to \infty$. The exact value of $\lambda_d$ is still unknown rigorously for any dimension $d \geq 2$; the asymptotics of $\lambda_d$, as $d \to \infty$, also remained elusive as of today. In this paper, we revisit and extend the approach presented by Klarner and Rivest in 1973 to bound $A_2(n)$ from above. Our contributions are: Using available computing power, we prove that $\lambda_2 \leq 4.5252$. This is the first improvement of the upper bound on $\lambda_2$ in almost half a century; We prove that $\lambda_d \leq (2d-2)e+o(1)$ for any value of $d \geq 2$, using a novel construction of a rational generating function which dominates that of the sequence $\left(A_d(n)\right)$; For $d=3$, this provides a subtantial improvement of the upper bound on $\lambda_3$ from 12.2071 to 9.8073; However, we implement an iterative process in three dimensions, which improves further the upper bound on $\lambda_3$to $9.3835$.
Comment: preliminary version
Databáze: OpenAIRE
Externí odkaz: