Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes
share
A d-dimensional polycube is a facet-connected set of cells (cubes) on the d-dimensional cubical lattice Z^d. Let A_d(n) denote the number of d-dimensional polycubes (distinct up to translations) with n cubes, and λ_d denote the limit of the ratio A_d(n+1)/A_d(n) as n →∞. The exact value of λ_d is still unknown rigorously for any dimension d ≥ 2; the asymptotics of λ_d, as d →∞, 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 λ_2 ≤ 4.5252. This is the first improvement of the upper bound on λ_2 in almost half a century; We prove that λ_d ≤ (2d-2)e+o(1) for any value of d ≥ 2, using a novel construction of a rational generating function which dominates that of the sequence (A_d(n)); For d=3, this provides a subtantial improvement of the upper bound on λ_3 from 12.2071 to 9.8073; three dimensions, which improves further the upper bound on λ_3to 9.3835;
READ FULL TEXT