Display paper

A d-dimensional polycube is a facet-connected set of cells (cubes) on the d-dimensional cubical lattice. The size of a polycube is the number of cubes it contains, and A_d(n) denotes the number of d-dimensional polycubes (distinct up to translations) of size n. The growth constant of a sequence a(n) is the limit, if it exists, of a(n+1)/a(n), as n tends to infinity. Although it is known that λ_d, the growth constant of A_d(n), exists in any fixed dimension d, its exact value is unknown to-date in any dimension d > 1 dimensions. Setting rigorous lower and upper bounds on λ_d is an extremely challenging combinatorial problem. While significant progress has been made along the years with improving the lower bound on λ_2, very little progress was made for the upper bounds. The known rigorous upper bounds are quite far from the estimated values of λ_d, and the only known method for setting nontrivial upper bounds was so far limited to two dimensions. First, we explore this method, and use available computing power to improve the upper bound on λ_2 (a.k.a. Klarner’s constant) from 4.6496 to 4.5252. This is the first improvement of the upper bound on λ_2 in about 45 years. Second, we present a nontrivial generalization of this approach to any dimension d, showing constructively a rational generating function which dominates the one of the sequence A_d(n). The generalized method immediately improves the upper bound on λ_3 from 12.2071 to 9.8073. As in two dimensions, this method is highly amenable to systematic improvement. As a result, we further improve the upper bound, showing that λ_3 ≤ 8.8782, while the value predicted for λ3 is about 8.344.