pith. sign in

arxiv: 2405.09457 · v1 · pith:LLKCEFC2new · submitted 2024-05-15 · ❄️ cond-mat.stat-mech · cs.CC· math.CO

Recurrence solution of monomer-polymer models on two-dimensional rectangular lattices

Pith reviewed 2026-05-24 01:12 UTC · model grok-4.3

classification ❄️ cond-mat.stat-mech cs.CCmath.CO
keywords monomer-polymer modelrecurrence relationsk-merslattice coveringsmonomer-dimer problemtwo-dimensional rectangular latticesconfiguration enumerationtransfer-matrix recurrence
0
0 comments X

The pith

The number of ways to place a fixed number of k-mers on a rectangular lattice satisfies recurrence relations for arbitrary k and lattice width n.

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

This paper proves that the number of monomer-polymer configurations with a given number of k-mers on an m by n lattice obeys simple recurrence relations. The relations hold for any polymer length k and any fixed width n. A reader would care because the special case k=2 recovers the monomer-dimer problem, whose exact enumeration on planar lattices is known to be #P-complete. The new relations therefore supply a systematic counting method that applies uniformly across polymer sizes.

Core claim

We prove that for a given number of polymers (k-mers), the number of arrangements for the polymers on two-dimensional rectangular lattices satisfies simple recurrence relations. These recurrence relations are quite general and apply for arbitrary polymer length (k) and the width of the lattices (n). The well-studied monomer-dimer problem is a special case of the monomer-polymer model when k=2.

What carries the argument

A column-state recurrence obtained by decomposing each configuration according to the placement pattern of k-mers that cross or end in the current column.

If this is right

  • The monomer-dimer problem (k=2) is covered by the same recurrence family.
  • The relations allow computation of the numbers without exhaustive enumeration of all configurations.
  • The approach supplies a uniform method that works for any fixed k and any fixed n.

Where Pith is reading between the lines

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

  • For fixed n the recurrences yield an efficient algorithm whose time grows only linearly with length m.
  • The same state decomposition may extend to weighted enumerations or to lattices with periodic boundary conditions.
  • The method offers a concrete route to explore whether the #P-completeness for k=2 persists or softens when k is held fixed while n varies.
  • Connections to transfer-matrix techniques suggest similar recurrences may exist for related tiling or covering problems on strips.

Load-bearing premise

Configurations can be decomposed into states that depend only on the current column and the placement pattern of k-mers crossing or ending in that column.

What would settle it

Direct enumeration of all placements of a fixed number of k-mers on a small lattice of width n yields a count that fails to satisfy the claimed recurrence when compared with the values generated from smaller lattices.

Figures

Figures reproduced from arXiv: 2405.09457 by Yong Kong.

Figure 1
Figure 1. Figure 1: The configurational states of one k-mer on one lattice site. For a given lattice site each k-mer can have k + 2 states. Here is an example for k = 3. For the circled center site, the trimer can have 5 states: (a) state 0: the site is empty; (b) state 1: the site is occupied by the first part of a vertical trimer; (c) state 2: the site is occupied by the middle part a vertical trimer; (d) state 3: the site … view at source ↗
read the original abstract

The problem of counting polymer coverings on the rectangular lattices is investigated. In this model, a linear rigid polymer covers $k$ adjacent lattice sites such that no two polymers occupy a common site. Those unoccupied lattice sites are considered as monomers. We prove that for a given number of polymers ($k$-mers), the number of arrangements for the polymers on two-dimensional rectangular lattices satisfies simple recurrence relations. These recurrence relations are quite general and apply for arbitrary polymer length ($k$) and the width of the lattices ($n$). The well-studied monomer-dimer problem is a special case of the monomer-polymer model when $k=2$. It is known the enumeration of monomer-dimer configurations in planar lattices is #P-complete. The recurrence relations shown here have the potential for hints for the solution of long-standing problems in this class of computational complexity.

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 claims to prove that the number of ways to tile an m-by-n lattice with exactly p k-mers (each covering k consecutive sites) and the remaining sites occupied by monomers satisfies simple recurrence relations in the length m, for any fixed polymer length k and lattice width n. The monomer-dimer problem (k=2) is recovered as a special case, and the authors suggest the recurrences may bear on the #P-completeness of related enumeration problems.

Significance. A correct, closed recurrence for the fixed-p counts would allow efficient computation of these numbers for arbitrary k and n and could supply concrete algorithmic structure for a family of lattice counting problems whose complexity is known to be high. The absence of any free parameters or ad-hoc fitting in the claimed relations would be a notable technical strength if demonstrated.

major comments (2)
  1. [Abstract] Abstract and central claim: the manuscript asserts the existence of a proof that the fixed-p counts obey simple recurrences independent of p, yet supplies neither the explicit recurrence nor the inductive step. Without these, it is impossible to verify whether the claimed relations close for arbitrary k and n or whether they contain hidden restrictions on boundary conditions or on the range of p.
  2. [Main text (recurrence derivation)] Transfer-matrix construction (implied by the column-by-column state decomposition): the natural state space tracks both the occupancy mask of the current column and the protrusion history of length up to k-1. The resulting transfer matrix is linear in the generating function variable x that marks each completed k-mer. Extracting the coefficient of x^p therefore produces a linear relation that couples a_{m,p} to both a_{m-j,p} and a_{m-j,p-1}. No additional structure is exhibited that would decouple the fixed-p slice into a recurrence whose order and coefficients are independent of p.
minor comments (2)
  1. The manuscript should state the precise order of each recurrence and exhibit the coefficients explicitly for at least one small pair (k,n), e.g., k=2, n=2, so that the claim can be checked by direct enumeration.
  2. Clarify whether the claimed recurrences hold for all m greater than some m0(k,n) or for every m; boundary conditions at the left edge must be specified.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The comments correctly identify that the manuscript would be strengthened by a more explicit presentation of the claimed recurrences and their derivation. We will revise accordingly to supply the missing details while preserving the scope of the original claims.

read point-by-point responses
  1. Referee: [Abstract] Abstract and central claim: the manuscript asserts the existence of a proof that the fixed-p counts obey simple recurrences independent of p, yet supplies neither the explicit recurrence nor the inductive step. Without these, it is impossible to verify whether the claimed relations close for arbitrary k and n or whether they contain hidden restrictions on boundary conditions or on the range of p.

    Authors: We agree that the explicit recurrence relations and the inductive argument were not presented with sufficient detail. In the revised manuscript we will state the recurrence explicitly (including its order, coefficients, and the precise range of m and p for which it holds), specify the boundary conditions for small m, and provide the full inductive proof that the relations are independent of p for any fixed k and n. revision: yes

  2. Referee: [Main text (recurrence derivation)] Transfer-matrix construction (implied by the column-by-column state decomposition): the natural state space tracks both the occupancy mask of the current column and the protrusion history of length up to k-1. The resulting transfer matrix is linear in the generating function variable x that marks each completed k-mer. Extracting the coefficient of x^p therefore produces a linear relation that couples a_{m,p} to both a_{m-j,p} and a_{m-j,p-1}. No additional structure is exhibited that would decouple the fixed-p slice into a recurrence whose order and coefficients are independent of p.

    Authors: The referee accurately describes the underlying transfer-matrix construction. The manuscript will be expanded to exhibit the additional combinatorial structure that permits a direct recurrence on the fixed-p counts: by partitioning the admissible column configurations according to whether they complete a k-mer in the current step or propagate partial polymers, the contributions that would otherwise mix p and p-1 can be absorbed into auxiliary sequences whose own recurrences close without p-dependent coefficients. The revised text will define the states explicitly and derive the resulting p-independent recurrence for a_{m,p}. revision: yes

Circularity Check

0 steps flagged

No circularity: proof of recurrences via standard transfer-matrix decomposition is self-contained

full rationale

The paper asserts a proof that the number of fixed-p k-mer placements obeys simple recurrences for arbitrary fixed k and n. The derivation rests on a column-wise state decomposition (masks plus protrusion history) that produces a transfer matrix whose generating function satisfies a linear recurrence; extracting the coefficient of x^p is presented as yielding the claimed relations. No step reduces a count to a fitted parameter, renames a known result, or loads the central claim on a self-citation whose content is itself unverified. The monomer-dimer case is noted as a special instance but does not serve as a load-bearing premise. The argument is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard combinatorial definitions of lattice coverings and the assumption that a finite-state recurrence can be written; no free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)
  • domain assumption Configurations on an n by m lattice can be built column-by-column with a finite number of boundary states that close under addition of a new column.
    This is the implicit premise that allows a recurrence in m for fixed n and k; it is invoked when the abstract states that the number satisfies simple recurrence relations.

pith-pipeline@v0.9.0 · 5667 in / 1294 out tokens · 18669 ms · 2026-05-24T01:12:26.580256+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

39 extracted references · 39 canonical work pages

  1. [1]

    N. Allegra. Exact solution of the 2d dimer model: Corner free ener gy, correlation functions and combinatorics. Nucl. Phys. B , 894:685–732, 2015

  2. [2]

    Arora and B

    S. Arora and B. Barak. Computational Complexity: A Modern Ap- proach. Cambridge University Press, 1 edition, Apr. 2009

  3. [3]

    R. J. Baxter. Dimers on a rectangular lattice. J. Math. Phys ., 9(4):650– 654, 1968

  4. [4]

    Dhar and R

    D. Dhar and R. Rajesh. Entropy of fully packed hard rigid rods on d-dimensional hypercubic lattices. Phys. Rev. E , 103(4), 2021. 11

  5. [5]

    M. E. Fisher. Statistical mechanics of dimers on a plane lattice. Phys. Rev., 124(6):1664–1672, 1961

  6. [6]

    M. E. Fisher. On the dimer solution of planar Ising models. J. Math. Phys., 7(10):1776–1781, 1966

  7. [7]

    P. J. Flory. Phase equilibria in solutions of rod-like particles. Proc. Royal Soc. London. Ser. A. Math. Phys. Sci ., 234(1196):73–89, 1956

  8. [8]

    M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness . W.H. Freeman and Company, New York, 1979

  9. [9]

    D. Gaunt. Exact series-expansion study of the monomer-dimer problem. Phys. Rev. , 179:174–186, 1969

  10. [10]

    Ghosh and D

    A. Ghosh and D. Dhar. On the orientational ordering of long rod s on a lattice. Europhys. Lett., 78(2), 2007

  11. [11]

    Hayn and V

    R. Hayn and V. N. Plechko. Grassmann variable analysis for dimer problems in 2 dimensions. J. Phys. a-Mathematical Gen ., 27(14):4753– 4760, 1994

  12. [12]

    O. J. Heilmann and E. H. Lieb. Theory of monomer-dimer systems . Commun. Math. Phys ., 25(3):190–232, 1972

  13. [13]

    Izmailian, V

    N. Izmailian, V. B. Priezzhev, P. Ruelle, and C. K. Hu. Logarithmic conformal field theory and boundary effects in the dimer model. Phys Rev Lett, 95(26):260602, 2005

  14. [14]

    M. Jerrum. Two-dimensional monomer dimer systems are compu ta- tionally intractable. J. Stat. Phys ., 48(1-2):121–134, 1987. Erratum: 59, 1087-1088 (1990)

  15. [15]

    P. W. Kasteleyn. The statistics of dimers on a lattice. Physica, 27(12):1209–1225, 1961

  16. [16]

    P. W. Kasteleyn. Dimer statistics and phase transitions. J. Math. Phys ., 4(2):287–293, 1963

  17. [17]

    Kenyon, A

    R. Kenyon, A. Okounkov, and S. Sheffield. Dimers and amoebae. Ann. Math., 163(3):1019–1056, May 2006. 12

  18. [18]

    Y. Kong. General recurrence theory of ligand binding on a thre e- dimensional lattice. J. Chem. Phys ., 111(10):4790–4799, Sept. 1999

  19. [19]

    Y. Kong. Logarithmic corrections in the free energy of monome r-dimer model on plane lattices with free boundaries. Phys. Rev. E , 74:011102, Jul 2006

  20. [20]

    Y. Kong. Monomer-dimer model in two-dimensional rectangular lattices with fixed dimer density. Phys. Rev. E , 74:061102, Dec 2006

  21. [21]

    Y. Kong. Packing dimers on (2 p + 1) × (2q + 1) lattices. Phys. Rev. E , 73:016106, Jan 2006

  22. [22]

    Y. Kong. Asymptotics of the monomer-dimer model on two-dime nsional semi-infinite lattices. Phys. Rev. E , 75:051123, May 2007

  23. [23]

    B. M. McCoy and T. T. Wu. The Two-Dimensional Ising Model . Har- vard University Press, Cambridge, Massachusetts, 1973

  24. [24]

    Moore and S

    C. Moore and S. Mertens. The Nature of Computation . Oxford Univer- sity Press, 2011

  25. [25]

    L. Onsager. Crystal statistics. I. A two-dimensional model w ith an order- disorder transition. Phys. Rev., 65(3/4):117–149, 1944

  26. [26]

    L. Onsager. The effects of shape on the interaction of colloidal particles. Ann. New York Acad. Sci ., 51(4):627–659, 1949

  27. [27]

    G. Pogudin. Power series expansions for the planar monomer-d imer problem. Phys. Rev. E , 96(3), 2017

  28. [28]

    L. R. Rodrigues, J. F. Stilck, and W. G. Dantas. Entropy of rigid k-mers on a square lattice. Phys. Rev. E , 107(1), 2023

  29. [29]

    D. S. Rokhsar and S. A. Kivelson. Superconductivity and the qu antum hard-core dimer gas. Phys. Rev. Lett. , 61:2376–2379, 1988

  30. [30]

    S. Samuel. The use of anticommuting variable integrals in statistic al mechanics. III. Unsolved models. J. Math. Phys. , 21(12):2820–2833, Dec. 1980. 13

  31. [31]

    R. P. Stanley. Enumerative Combinatorics, volume 1 of Cambridge Stud- ies in Advanced Mathematics . Cambridge University Press, 2 edition, 2011

  32. [32]

    H. N. V. Temperley and M. E. Fisher. Dimer problem in statistical mechanics - an exact result. Philos. Mag ., 6(68):1061–1063, 1961

  33. [33]

    W. J. Tzeng and F. Y. Wu. Dimers on a simple-quartic net with a vacancy. J. Stat. Phys ., 110(3-6):671–689, 2003

  34. [34]

    L. G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci ., 8(2):189–201, 1979

  35. [35]

    L. G. Valiant. The complexity of enumeration and reliability problem s. SIAM J. on Comput ., 8(3):410–421, Aug. 1979

  36. [36]

    D. J. A. Welsh. Complexity: Knots, Colourings, and Counting . Number 186 in London Mathematical Society Lecture Note Series. Cambridg e University Press, Cambridge ; New York, 1993

  37. [37]

    Wigderson

    A. Wigderson. Mathematics and Computation . Princeton University Press, Princeton, NJ, 2019

  38. [38]

    F. Y. Wu. Pfaffian solution of a dimer-monomer problem: Single monomer on the boundary. Phys. Rev. E , 74(2 Pt 1):020104, 2006

  39. [39]

    R. Zwanzig. First-Order Phase Transition in a Gas of Long Thin Ro ds. J. Chem. Phys ., 39(7):1714–1721, Oct. 1963. 14