pith. sign in

arxiv: 2511.00461 · v2 · submitted 2025-11-01 · 🧮 math.CO

A convolutional approach to bounding the number of polyominoes

Vuong Bui This is my paper

Pith reviewed 2026-05-18 01:49 UTC · model grok-4.3

classification 🧮 math.CO MSC 05B50
keywords polyominoesKlarner's constantgrowth raterecurrence relationsupper boundsconvolutionenumeration
0
0 comments X

The pith

A small system of convolution recurrences establishes an upper bound of 4.5238 on the polyomino growth rate.

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

The paper seeks to tighten the known upper bound on Klarner's constant, the growth rate of the number of polyominoes. Earlier methods enumerated enormous collections of local neighborhoods and then counted sequences of those neighborhoods. This work instead introduces a compact set of recurrence relations that limit which sequences of neighborhoods are allowed to occur. The result is a slightly better bound together with a short proof and a general technique for certifying bounds on similar recurrences by checking only a few arithmetic steps. A reader cares because the change replaces brute-force enumeration with a modeling choice that may scale to other counting problems.

Core claim

By replacing the almost-unrestricted sequence of local neighborhoods with a small system of convolution-type recurrences that constrains their allowed concatenations, the authors prove that the growth rate λ of polyominoes satisfies λ ≤ 4.5238. The same framework supplies a general method for rigorously upper-bounding the growth of any recurrence with nonnegative coefficients to arbitrary precision, where the bound is certified by exhibiting a small set of numerical parameters.

What carries the argument

A small system of convolution-type recurrences that constrains how local neighborhoods (twigs) can be concatenated to form valid polyominoes.

If this is right

  • The new bound of 4.5238 improves on the prior enumeration-based bound of 4.5252.
  • The entire proof is short, self-contained, and verifiable by direct hand calculation.
  • A small list of numerical parameters serves as a complete certificate for the bound.
  • The same bounding technique applies to any recurrence system whose coefficients are nonnegative.

Where Pith is reading between the lines

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

  • The same convolutional modeling could be tried on growth rates for polyiamonds, polycubes, or other lattice animals.
  • Adding a few more states to the recurrence system might produce a noticeably tighter numerical bound.
  • The certificate technique may simplify proofs for other combinatorial growth constants that are currently obtained by large-scale computer search.

Load-bearing premise

The chosen recurrences are assumed to correctly upper-bound every possible way that valid polyomino neighborhoods can be joined.

What would settle it

Exhibiting a concrete polyomino whose sequence of local neighborhoods violates one of the recurrence relations, or computing the exact number of polyominoes for sufficiently large n to show that the growth rate exceeds 4.5238.

read the original abstract

Although known lower bounds for the growth rate $\lambda$ of polyominoes, or Klarner's constant, are already close to the empirically estimated value $4.06$, almost no conceptual progress on upper bounds has occurred since the seminal work of Klarner and Rivest (1973). Their approach, based on enumerating millions of local neighborhoods (also called ``twigs'') yielded $\lambda \le 4.649551$, later refined by Barequet and Shalah (2022) to $\lambda \le 4.5252$ using trillions of configurations. The inefficiency lies in representing each polyomino as an almost unrestricted sequence of neighborhoods once the large set of neighborhoods is fixed. We introduce a recurrence-based approach that constrains how local neighborhoods concatenate. Using a small system of convolution-type recurrences, we obtain $\lambda \le 4.5238$. The proof is short, self-contained, and hand-checkable. Despite the marginal numerical improvement, the main contribution is methodological: replacing trillions of configurations with a concise one-page system of recurrences. In addition, we present a new technique for rigorously bounding the growth of recurrences to any precision, applicable to a broad range of settings with nonnegative coefficients. The resulting upper bound even comes with a nice feature: a small set of parameters serves as the certificate for the bound, that is, one does not need to check more than a few arithmetic calculations to trust the bound.

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 manuscript introduces a recurrence-based method for upper-bounding Klarner's constant λ, the growth rate of polyominoes. By replacing the enumeration of trillions of local neighborhoods (twigs) with a small, explicitly defined system of convolution-type recurrences that constrain neighborhood concatenations, the authors derive λ ≤ 4.5238. The proof is presented as short, self-contained, and hand-checkable, with the bound certified by a small set of numerical parameters whose verification requires only a few arithmetic steps. A general technique for rigorously upper-bounding the growth rate of nonnegative linear recurrences is also developed.

Significance. If the modeling assumption holds, the work offers a modest numerical improvement (from 4.5252 to 4.5238) but a substantial methodological advance: replacing massive configuration enumeration with a one-page recurrence system whose correctness can be verified by hand. The explicit certificate consisting of a few parameters is a clear strength, as is the new general bounding technique for recurrences with nonnegative coefficients, which may apply beyond polyomino enumeration. These features address the inefficiency noted in prior work by Klarner-Rivest and Barequet-Shalah.

major comments (2)
  1. [§2] §2 (or the section defining the recurrence system): the central claim that the chosen convolution recurrences upper-bound a_n for all n rests on the assertion that every valid sequence of neighborhoods arising from an actual polyomino is permitted by the state transitions and convolution rules. An explicit argument or small diagram showing that no valid concatenation is excluded by the neighborhood constraints is needed; without it the extracted growth rate cannot be guaranteed to dominate λ.
  2. [§3] §3, the derivation of the numerical bound: the paper states that the bound follows from solving or majorizing the recurrence system and that verification requires only a few arithmetic calculations. The explicit system of recurrences (including all coefficients and initial conditions) together with the precise majorization steps must be displayed so that the hand-checkable certificate can be directly inspected; currently the reader must reconstruct the system from the description.
minor comments (2)
  1. Notation for the convolution operators and state variables should be introduced once with a compact table or diagram; repeated re-definition in later sections reduces readability.
  2. The general technique for bounding recurrence growth (Theorem X) is stated for nonnegative coefficients; a one-sentence remark on whether the same argument extends to recurrences with a finite number of negative coefficients would clarify its scope.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the helpful suggestions for improving the clarity of the presentation. We have revised the manuscript to address both major comments.

read point-by-point responses

  1. Referee: [§2] §2 (or the section defining the recurrence system): the central claim that the chosen convolution recurrences upper-bound a_n for all n rests on the assertion that every valid sequence of neighborhoods arising from an actual polyomino is permitted by the state transitions and convolution rules. An explicit argument or small diagram showing that no valid concatenation is excluded by the neighborhood constraints is needed; without it the extracted growth rate cannot be guaranteed to dominate λ.

    Authors: We agree with the referee that an explicit argument is necessary to confirm that the recurrence system captures all valid neighborhood concatenations. In the revised version, we have inserted a new paragraph in §2 that provides a direct argument based on the definition of the states and transitions, accompanied by a small illustrative diagram. This diagram demonstrates that every possible valid adjacency between polyomino cells is accounted for in the allowed convolutions, thereby ensuring that the growth rate of the recurrence system dominates λ. revision: yes

  2. Referee: [§3] §3, the derivation of the numerical bound: the paper states that the bound follows from solving or majorizing the recurrence system and that verification requires only a few arithmetic calculations. The explicit system of recurrences (including all coefficients and initial conditions) together with the precise majorization steps must be displayed so that the hand-checkable certificate can be directly inspected; currently the reader must reconstruct the system from the description.

    Authors: We appreciate this comment, as making the certificate fully explicit enhances the hand-checkable nature of the proof. We have now included in §3 the complete explicit system of recurrences, listing all coefficients and initial conditions, followed by the precise sequence of majorization steps used to obtain λ ≤ 4.5238. These additions allow the reader to verify the bound through direct arithmetic without needing to reconstruct the system. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via explicit majorization

full rationale

The paper defines a finite system of convolution-type recurrences whose states and transitions are chosen to dominate all valid neighborhood concatenations of polyominoes. The growth rate of this system is then shown to upper-bound λ by direct comparison of the recurrence counts to the actual enumeration. The certificate consists of a small explicit set of parameters whose arithmetic verification is claimed to be hand-checkable and independent of the target bound. No step reduces a claimed prediction to a fitted parameter by construction, no load-bearing self-citation is invoked, and the modeling assumptions are stated as inequalities that must be verified rather than tautologically true. The result therefore remains non-circular even if the modeling choice is later shown to be imperfect.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the correctness of a small system of linear recurrences with nonnegative coefficients that dominate polyomino concatenation; no explicit free parameters are named in the abstract, but the recurrence coefficients themselves function as chosen constants that must be verified to produce a valid majorant.

axioms (1)
  • domain assumption The chosen convolution-type recurrences correctly upper-bound the growth of all valid sequences of neighborhoods.
    This modeling premise is required for the recurrence system to imply the claimed bound on λ.

pith-pipeline@v0.9.0 · 5788 in / 1357 out tokens · 23128 ms · 2026-05-18T01:49:16.262122+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

  1. [1]

    Gill Barequet, G¨ unter Rote, and Mira Shalah.λ >4: An improved lower bound on the growth constant of polyominoes.Communications of the ACM, 59(7):88–95, 2016

    work page 2016

  2. [2]

    Counting polyominoes: A parallel implementation for cluster computing

    Iwan Jensen. Counting polyominoes: A parallel implementation for cluster computing. InInternational Conference on Computational Science, pages 203–212. Springer, 2003

    work page 2003

  3. [3]

    A two-dimensional growth process

    Murray Eden. A two-dimensional growth process. InProc. 4th Berkeley Sympos. Math. Statist. and Prob., volume 4, pages 223–239, 1961

    work page 1961

  4. [4]

    An asymptotic lower bound on the number of polyominoes.Annals of Combinatorics, 28(2):459–484, 2024

    Vuong Bui. An asymptotic lower bound on the number of polyominoes.Annals of Combinatorics, 28(2):459–484, 2024

    work page 2024

  5. [5]

    A procedure for improving the upper bound for the number of n-ominoes.Canadian Journal of Mathematics, 25(3):585–602, 1973

    David A Klarner and Ronald L Rivest. A procedure for improving the upper bound for the number of n-ominoes.Canadian Journal of Mathematics, 25(3):585–602, 1973

    work page 1973

  6. [6]

    Bounding Klarner’s constant from above using a simple recurrence.Archiv der Mathematik, 124:517–523, 2025

    Vuong Bui. Bounding Klarner’s constant from above using a simple recurrence.Archiv der Mathematik, 124:517–523, 2025

    work page 2025

  7. [7]

    Improved upper bounds on the growth constants of polyominoes and polycubes.Algorithmica, 84(12):3559–3586, 2022

    Gill Barequet and Mira Shalah. Improved upper bounds on the growth constants of polyominoes and polycubes.Algorithmica, 84(12):3559–3586, 2022. 15

    work page 2022