pith. sign in

arxiv: 1906.11447 · v2 · pith:735BWN3Qnew · submitted 2019-06-27 · 💻 cs.DM · cs.CG· math.CO

Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes

Gill Barequet , Mira Shalah This is my paper

Pith reviewed 2026-05-25 14:10 UTC · model grok-4.3

classification 💻 cs.DM cs.CGmath.CO
keywords polycubespolyominoesgrowth constantsenumerationgenerating functionsupper boundslattice animalsasymptotics
0
0 comments X

The pith

The growth constants of d-dimensional polycubes satisfy λ_d ≤ (2d-2)e + o(1) for every d ≥ 2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a rational generating function whose coefficients are at least as large as the number of polycubes of size n in d dimensions. This construction immediately implies that the growth constant λ_d is bounded above by (2d-2)e plus a quantity that goes to zero with d. For the square lattice the same method gives the concrete bound 4.5252. In three dimensions an iterative improvement of the construction produces the bound 9.3835. These results extend a 1973 technique of Klarner and Rivest with modern computation to obtain the first improvement on the two-dimensional case in nearly fifty years.

Core claim

We prove λ_d ≤ (2d−2)e + o(1) for d ≥ 2 by exhibiting a rational generating function that dominates the polycube counting series. The construction generalizes the Klarner-Rivest method and supplies the first improvement on the two-dimensional bound in nearly fifty years, reaching λ_2 ≤ 4.5252. In three dimensions the bound is reduced to 9.3835 by an iterative refinement of the dominating series.

What carries the argument

A novel rational generating function whose series expansion majorizes the polycube enumeration sequence A_d(n).

If this is right

  • The number of n-cube polycubes grows at most as roughly [(2d-2)e]^n for large n.
  • λ_d itself grows at most linearly with the dimension d.
  • Enumeration algorithms for polycubes can prune their search trees using the new analytic bounds.
  • The same dominating series works uniformly for every dimension without separate case analysis.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The linear growth in d suggests that high-dimensional polycube counting is dominated by independent local attachment choices.
  • Similar majorizing series could be built for polycubes with holes or for other lattice connectivities.
  • The remaining gap between the new upper bounds and existing lower bounds for small d points to possible further improvements by tighter majorants.
  • If the o(1) term can be made explicit, the bound becomes directly usable for entropy calculations in statistical-mechanics models of lattice animals.

Load-bearing premise

The rational generating function constructed in the paper has coefficients that are at least as large as A_d(n) for all n and all d.

What would settle it

Computing the exact number of polycubes A_d(n) for a sufficiently large n and finding that it exceeds the nth coefficient of the proposed dominating generating function.

Figures

Figures reproduced from arXiv: 1906.11447 by Gill Barequet, Mira Shalah.

Figure 1
Figure 1. Figure 1: Polyominoes of sizes 1 ≤ n ≤ 4 The size of a polyomino is the number of squares it contains. All poly￾ominoes of size up to 4 are shown in [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Eden’s set of twigs [19, Figure 3] [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: L-contexts of [19, [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Twig set L [19, [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: [19, Figure 8] [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The +L context (bold black lines) of a cell o on the 3D cubical lattice We generalize the twigs idea to three dimensions as follows. Refer to [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: 3-dimensional twigs 3.2 d > 3 Our construction in three dimensions can be applied inductively for d > 3. The base of the induction is d=2, where we fix a square in the x1x2 plane (as in [PITH_FULL_IMAGE:figures/full_fig_p007_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: A twig with one open cell Klarner and Rivest [19] developed their idea further, noting that it is possible to start with a con￾figuration containing a single open cell (as shown in [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The tree modeling the algorithm that generates Ci . The root r is a twig with one open cell; its L-context is shown in [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: The only two twigs with two dead cells and no open cells [PITH_FULL_IMAGE:figures/full_fig_p017_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Concatenation of L2 and L3. 17 [PITH_FULL_IMAGE:figures/full_fig_p018_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Concatenation of L3 and L3 [PITH_FULL_IMAGE:figures/full_fig_p019_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: A pentomino 18 [PITH_FULL_IMAGE:figures/full_fig_p019_13.png] view at source ↗
read the original abstract

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

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims improved upper bounds on the growth constants λ_d of d-dimensional polycubes A_d(n). For d=2 it proves λ_2 ≤ 4.5252 by computer-assisted methods extending Klarner-Rivest; for general d≥2 it constructs a novel rational generating function G_d(x) whose coefficients dominate those of the polycube sequence, yielding the asymptotic λ_d ≤ (2d-2)e + o(1); and for d=3 an iterative refinement gives λ_3 ≤ 9.3835.

Significance. If the domination and computer-assisted arguments hold, the results are significant: the 2D bound is the first improvement in nearly 50 years, the general construction supplies the first explicit asymptotic upper bound of this form, and the 3D improvement is substantial. The explicit dominating rational GF is a methodological strength that could be reusable.

major comments (2)
  1. [§3] §3 (novel rational GF construction): the central claim that [x^n]G_d(x) ≥ A_d(n) for all n (required for the radius-of-convergence bound to be valid) rests on an injection or recurrence comparison whose details must be fully explicit; any gap for even a single n would falsify the general λ_d ≤ (2d-2)e + o(1) result.
  2. [§4] §4 (2D computer-assisted bound): the proof that λ_2 ≤ 4.5252 depends on a specific enumeration or matrix-power computation whose implementation, termination criterion, and independent verifiability are not described at a level allowing reproduction; this is load-bearing for the claimed improvement over the 1973 bound.
minor comments (2)
  1. [Abstract] Abstract: 'subtantial' is a typo for 'substantial'.
  2. [Abstract] Abstract: the two 3D bounds (9.8073 from the general method and 9.3835 from the iterative process) should be clearly distinguished with a sentence explaining which construction produces each.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for greater explicitness in two key arguments. We address each major comment below and will revise the manuscript to incorporate the requested details.

read point-by-point responses

  1. Referee: [§3] §3 (novel rational GF construction): the central claim that [x^n]G_d(x) ≥ A_d(n) for all n (required for the radius-of-convergence bound to be valid) rests on an injection or recurrence comparison whose details must be fully explicit; any gap for even a single n would falsify the general λ_d ≤ (2d-2)e + o(1) result.

    Authors: We agree that the domination [x^n]G_d(x) ≥ A_d(n) must be established with fully explicit details to support the radius-of-convergence argument. The manuscript constructs the rational generating function G_d(x) and compares it to the polycube sequence via a recurrence that overcounts polycubes. To eliminate any possible gap, we will expand §3 with an explicit verification of the inequality for all n up to a small threshold (by direct enumeration) followed by a complete inductive step showing that the recurrence preserves the domination for larger n. This will make the comparison fully rigorous and reproducible. revision: yes

  2. Referee: [§4] §4 (2D computer-assisted bound): the proof that λ_2 ≤ 4.5252 depends on a specific enumeration or matrix-power computation whose implementation, termination criterion, and independent verifiability are not described at a level allowing reproduction; this is load-bearing for the claimed improvement over the 1973 bound.

    Authors: The 2D upper bound is obtained by extending the Klarner–Rivest matrix method with additional states and computer-assisted enumeration of small polyominoes to tighten the transfer-matrix bound. We will revise §4 to include a precise description of the state space, the matrix construction, the powering algorithm used to extract the growth rate, the termination criterion for the enumeration, and high-level pseudocode sufficient for independent implementation. If space permits we will also indicate how the computation was cross-checked on smaller instances against known values of A_2(n). revision: yes

Circularity Check

0 steps flagged

No circularity detected: bounds obtained from explicit dominating rational GFs with independent combinatorial proofs

full rationale

The derivation constructs a novel rational generating function G_d(x) that dominates the polycube counting sequence A_d(n) and extracts the growth bound from its radius of convergence. This domination is established by a direct combinatorial encoding (extension of the external Klarner-Rivest 1973 method) via injection or recurrence comparison, not by fitting parameters to A_d(n) data or by any self-referential definition. No load-bearing step reduces to a self-citation, ansatz smuggling, or renaming of a known result; the central inequality [x^n]G_d(x) ≥ A_d(n) for all n is proven independently of the target growth constant λ_d. The result is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters or invented entities are introduced. The work relies on standard combinatorial constructions and the known existence of the growth-rate limit.

axioms (1)
  • domain assumption The limit λ_d = lim A_d(n+1)/A_d(n) exists for each fixed d.
    This is a standard result for polyomino and polycube sequences in the literature.

pith-pipeline@v0.9.0 · 5838 in / 1192 out tokens · 40195 ms · 2026-05-25T14:10:15.265839+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    The On-line Encyclopedia of Integer Sequences, published on-line at http://oeis.org

    work page

  2. [2]

    The Open Problems Project, published on-line at http://cs.smith.edu/~jorourke/TOPP

    work page

  3. [3]

    Aleksandrowicz and G

    G. Aleksandrowicz and G. Barequet. Counting d-dimensional polycubes and nonrectangular planar polyominoes. Int. J. of Computational Geometry and Applications , 19:215–229, 2009

    work page 2009

  4. [4]

    Aleksandrowicz and G

    G. Aleksandrowicz and G. Barequet. Counting polycubes without the dimensionality curse. Discrete Mathematics, 309:576–583, 2009

    work page 2009

  5. [5]

    Barequet and R

    G. Barequet and R. Barequet. An improved upper bound on the growth constant of polyominoes. Electronic Notes in Discrete Mathematics, 49(Supplement C):167–172, 2015. The 8th European Conf. on Combinatorics, Graph Theory, and Applications

    work page 2015

  6. [6]

    Barequet, M

    G. Barequet, M. Moffie, A. Rib´ o, and G. Rote. Counting polyominoes on twisted cylinders. INTE- GERS: Electronic J. of Combinatorial Number Theory , 6, 2006

    work page 2006

  7. [7]

    Barequet, G

    G. Barequet, G. Rote, and M. Shalah. λ >4 : An improved lower bound on the growth constant of polyominoes. Comm. of the ACM , 59:88–95, July 2016

    work page 2016

  8. [8]

    Barequet, G

    R. Barequet, G. Barequet, and G. Rote. Formulae and growth rates of high-dimensional polycubes. Combinatorica, 30:257–275, 2010

    work page 2010

  9. [9]

    A. Conway. Enumerating 2d percolation series by the finite-lattice method: Theory. J. of Physics, A: Mathematical and General , 28:335–349, 1995

    work page 1995

  10. [10]

    Derrida and H.J

    B. Derrida and H.J. Herrmann. Collapse of branched polymers. Le Journal de Physique, 44:1365–1376, 1983

    work page 1983

  11. [11]

    M. Eden. A two-dimensional growth process. In Proc. of the 4th Berkeley Symp. on Mathematical Statistics and Probability, volume 4, pages 223–239, Berkeley, CA, 1961

    work page 1961

  12. [12]

    Flesia, D.S

    S. Flesia, D.S. Gaunt, C.E. Soteros, and S.G. Whittington. Statistics of collapsing lattice animals. J. of Physics, A: Mathematical and General , 27:5831–5846, 1994

    work page 1994

  13. [13]

    D.S. Gaunt. The critical dimension for lattice animals. J. of Physics, A: Mathematical and General , 13:L97–L101, 1980

    work page 1980

  14. [14]

    Gaunt, M.F

    D.S. Gaunt, M.F. Sykes, and H. Ruskin. Percolation processes in d-dimensions. J. of Physics A: Mathematical and General, 9:1899–1911, 1976

    work page 1911

  15. [15]

    Guttmann, editor

    A.J. Guttmann, editor. Polygons, Polyominoes, and Polycubes , volume 775. Springer Netherlands, 2009

    work page 2009

  16. [16]

    I. Jensen. Counting polyominoes: A parallel implementation for cluster computing. In Proc. of the Int. Conf. on Computational Science, part III , volume 2659, pages 203–212. Springer, June 2003

    work page 2003

  17. [17]

    D.A. Klarner. Some results concerning polyominoes. Fibonacci Quarterly, 3:9–20, 1965

    work page 1965

  18. [18]

    D.A. Klarner. Cell growth problems. Canadian J. of Mathematics , 19:851–863, 1967

    work page 1967

  19. [19]

    Klarner and R.L

    D.A. Klarner and R.L. Rivest. A procedure for improving the upper bound for the number of n- ominoes. Canadian J. of Mathematics , 25:585–602, 1973. 13

    work page 1973

  20. [20]

    Lubensky and J

    T.C. Lubensky and J. Isaacson. Statistics of lattice animals and dilute branched polymers. Physical Review A, 20:2130–2146, 1979

    work page 1979

  21. [21]

    Luther and S

    S. Luther and S. Mertens. Counting lattice animals in high dimensions. J. of Statistical Mechanics: Theory and Experiment, 9:546–565, 2011

    work page 2011

  22. [22]

    N. Madras. A pattern theorem for lattice clusters. Annals of Combinatorics , 3:357–384, 1999

    work page 1999

  23. [23]

    Madras, C.E

    N. Madras, C.E. Soteros, S.G. Whittington, J.L. Martin, M.F. Sykes, S. Flesia, and D.S. Gaunt. The free energy of a collapsing branched polymer. J. of Physics, A: Mathematical and General , 23:5327– 5350, 1990

    work page 1990

  24. [24]

    J.L. Martin. The impact of large-scale computing on lattice statistics. J. of Statistical Physics , 58:749–774, 1990

    work page 1990

  25. [25]

    Mertens and M.E

    S. Mertens and M.E. Lautenbacher. Counting lattice animals: A parallel attack. J. of Statistical Physics, 66:669–678, 1992

    work page 1992

  26. [26]

    Rands and D.J.A

    B.M.I. Rands and D.J.A. Welsh. Animals, trees and renewal sequences. IMA J. of Applied Mathe- mathics, 27:1–17, 1981

    work page 1981

  27. [27]

    R.C. Read. Contributions to the cell growth problem. Canadian J. of Mathematics , 14:1–20, 1962

    work page 1962

  28. [28]

    Redelmeier

    D.H. Redelmeier. Counting polyominoes: Yet another attack. Discrete Mathematics , 36:191–203, 1981

    work page 1981

  29. [29]

    Sykes and M

    M.F. Sykes and M. Glen. Percolation processes in two dimensions: I. low-density series expansions. J. of Physics, A: Mathematical and General , 9:87–95, 1976. 14 A Comparison of Results |Ci| 1/σi Time (Hours) i Ref. [19] Ours Ref. [19] Ours Ours 1 5 5 4.828428 4.828427124 2 21 21 4.828428 4.828427124 3 93 93 4.828428 4.828427124 4 409 409 4.796156 4.79615...

    work page 1976

  30. [30]

    15 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ L2∗L1 L4∗L1 Figure 10: The only two twigs with two dead cells and no open cells

    There is only one twig (L1∈ L, shown in Figure 4) with one dead cell and no open cells. 15 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ L2∗L1 L4∗L1 Figure 10: The only two twigs with two dead cells and no open cells

    work page

  31. [31]

    There are only two twigs (see Figure 10) with two dead cells and no open cells

    work page

  32. [32]

    The sequences corresponding to these six twigs are L2∗L2∗L1,L2∗L4∗L1,L3∗L1∗L1,L4∗L2∗L1,L4∗L4∗L1, and L5∗L1∗L1

    There are only six twigs with three dead cells and no open cells. The sequences corresponding to these six twigs are L2∗L2∗L1,L2∗L4∗L1,L3∗L1∗L1,L4∗L2∗L1,L4∗L4∗L1, and L5∗L1∗L1. We now show that there are 400 twigs with 4 dead cells. Each such twig T corresponds to a se- quence (α,β,γ,δ ) of four elements of L (Figure 4), such that T = α∗β∗γ∗δ. Trivially, ...

    work page