Regular structures of an intractable enumeration problem: a diagonal recurrence relation of monomer-polymer coverings on two-dimensional rectangular lattices
Pith reviewed 2026-05-23 17:35 UTC · model grok-4.3
The pith
The number of ways to place exactly s polymers on an n by m lattice obeys the recurrence sum from i=0 to 2s of (-1)^i times binom(2s,i) times a sub n-i,m-i equals 2^s times (2s)! over s!.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The number a_{n,m} of coverings of an n by m rectangular lattice by exactly s polymers satisfies the identity sum_{i=0}^{2s} (-1)^i binom(2s,i) a_{n-i,m-i} = 2^s (2s)! / s!.
What carries the argument
The diagonal recurrence that subtracts binomial-weighted counts on lattices reduced by the same amount in each dimension.
If this is right
- The recurrence supplies a relation that must hold for any correct enumeration function a_{n,m} of s-polymer placements.
- Values of a_{n,m} on large grids are linearly determined by values on grids smaller by up to 2s in each direction.
- The right-hand side depends only on s, so the same numerical target applies to every lattice size once n and m exceed 2s.
- The identity is independent of the individual polymer length k.
Where Pith is reading between the lines
- The relation may be used to derive generating functions or closed-form expressions for the total number of coverings summed over s.
- Similar diagonal recurrences might be tested on lattices with periodic boundaries or on higher-dimensional grids.
- The independence from polymer length suggests the identity arises from an inclusion or matching argument that treats the polymers as indistinguishable objects of any size.
Load-bearing premise
The quantity a_{n,m} counts placements of exactly s non-overlapping linear polymers on the n by m grid with open boundaries and no site shared by more than one polymer.
What would settle it
Compute a_{3,3} and a_{2,2} and a_{1,1} by hand for s=1 and check whether the left-hand side of the sum equals 2^1 * 2! / 1! = 4.
Figures
read the original abstract
In the monomer-polymer model, a linear rigid polymer covers $k$ adjacent lattice sites, with no lattice site occupied by more than one polymer. The polymers are called $k$-mers, and those unoccupied lattice sites are called monomers. The well-known monomer-dimer model is a special case of the monomer-polymer model with $k=2$. The enumeration of polymer coverings on two-dimensional rectangular lattices is considered as "intractable". We prove that the number of coverings of $s$ polymer satisfies a simple recurrence relation $\sum_{i=0}^{2s} (-1)^i \binom{2s}{i} a_{n-i, m-i} = 2^s {(2s)!} / {s!}$ on a $n \times m$ rectangular lattice with open boundary conditions in both directions.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims to prove that the number a_{n,m} of exact-s polymer coverings on an n×m rectangular lattice with open boundaries satisfies the recurrence ∑_{i=0}^{2s} (-1)^i binom(2s,i) a_{n-i,m-i} = 2^s (2s)! / s! for all positive integers n,m (with a_{k,l}=0 when k or l is too small to admit s polymers).
Significance. A correct recurrence of this form, even with domain restrictions, would be a useful closed-form relation for an otherwise intractable enumeration problem in statistical mechanics and combinatorics. The manuscript supplies neither explicit proof steps nor verification data, and the central identity is stated without size restrictions on n and m.
major comments (1)
- [Abstract] Abstract (recurrence relation): the identity is asserted to hold for all n,m without qualification. For s=1 the RHS equals 4. Using the explicit formula a_{n,m}=2nm−n−m together with a_{k,l}=0 for invalid indices and a_{0,0}=1, the case n=m=2 yields LHS= a_{2,2}−2a_{1,1}+a_{0,0}=4−0+1=5≠4. The same substitution for n=m=3 yields 4, which matches. The stated claim is therefore false; any proof must contain an implicit lower bound (n,m≳2s) that is absent from the theorem statement. This is load-bearing for the central result.
Simulated Author's Rebuttal
We thank the referee for their careful reading and for identifying an important omission regarding the domain of the central recurrence. We agree that the statement requires explicit lower bounds on n and m and will revise the manuscript accordingly.
read point-by-point responses
-
Referee: [Abstract] Abstract (recurrence relation): the identity is asserted to hold for all n,m without qualification. For s=1 the RHS equals 4. Using the explicit formula a_{n,m}=2nm−n−m together with a_{k,l}=0 for invalid indices and a_{0,0}=1, the case n=m=2 yields LHS= a_{2,2}−2a_{1,1}+a_{0,0}=4−0+1=5≠4. The same substitution for n=m=3 yields 4, which matches. The stated claim is therefore false; any proof must contain an implicit lower bound (n,m≳2s) that is absent from the theorem statement. This is load-bearing for the central result.
Authors: We accept the referee's counterexample for s=1 and n=m=2; the calculation is correct and demonstrates that the recurrence does not hold unconditionally for all positive integers n and m. The relation is valid only when the lattice is large enough to place the s polymers, specifically for n, m ≥ 2s. We will revise the abstract, the theorem statement, and all relevant sections to include this explicit lower bound (with a_{k,l}=0 retained for smaller indices). The explicit formula a_{n,m}=2nm−n−m cited in the comment appears to describe a different enumeration problem; our a_{n,m} counts exact-s polymer coverings, but we accept the numerical discrepancy shown and will correct the domain of the claimed identity. revision: yes
Circularity Check
No circularity; direct proof claim with no self-referential reduction
full rationale
The paper states it proves the recurrence identity directly from the definition of a_{n,m} as the count of exact-s polymer placements on an n×m open-boundary lattice. No steps reduce the claimed relation to a fitted parameter, self-citation chain, or definitional tautology. The derivation is presented as an independent combinatorial argument. The noted domain restriction issue (failure at small n,m) is a potential correctness gap, not a circularity pattern.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Monomer-polymer coverings consist of linear rigid k-mers each occupying exactly k adjacent sites with no overlaps, on rectangular lattices with open boundaries.
Reference graph
Works this paper leans on
-
[1]
M. Apagodu and D. Zeilberger. Multi-variable zeilberger and almkvist–zeilberger algorithms and the sharpening of wilf–zeilberger the- ory. Adv. Appl. Math ., 37(2):139–152, Aug. 2006
work page 2006
-
[2]
D. Dhar and R. Rajesh. Entropy of fully packed hard rigid rods on d-dimensional hypercubic lattices. Phys. Rev. E , 103(4), 2021
work page 2021
-
[3]
M. E. Fisher. On the dimer solution of planar Ising models. J. Math. Phys., 7(10):1776–1781, 1966
work page 1966
- [4]
-
[5]
R. W. Gosper. Decision procedure for indefinite hypergeometric sum- mation. Proc. National Acad. Sci ., 75(1):40–42, Jan. 1978
work page 1978
- [6]
-
[7]
M. Jerrum. Two-dimensional monomer dimer systems are comput ation- ally intractable. J. Stat. Phys ., 48(1-2):121–134, 1987. Erratum: 59, 1087-1088 (1990)
work page 1987
-
[8]
P. W. Kasteleyn. Dimer statistics and phase transitions. J. Math. Phys ., 4(2):287–293, 1963
work page 1963
-
[9]
Y. Kong. Logarithmic corrections in the free energy of monomer -dimer model on plane lattices with free boundaries. Phys. Rev. E , 74:011102, Jul 2006
work page 2006
-
[10]
Y. Kong. Monomer-dimer model in two-dimensional rectangular lattices with fixed dimer density. Phys. Rev. E , 74:061102, Dec 2006
work page 2006
-
[11]
Y. Kong. Packing dimers on (2 p + 1) × (2q + 1) lattices. Phys. Rev. E , 73:016106, Jan 2006
work page 2006
-
[12]
Y. Kong. Asymptotics of the monomer-dimer model on two-dime nsional semi-infinite lattices. Phys. Rev. E , 75:051123, May 2007
work page 2007
-
[13]
Y. Kong. Recurrence solution of monomer-polymer models on tw o- dimensional rectangular lattices. Phys. Rev. E , 2024. accepted
work page 2024
-
[14]
B. M. McCoy and T. T. Wu. The Two-Dimensional Ising Model . Har- vard University Press, Cambridge, Massachusetts, 1973
work page 1973
-
[15]
L. Onsager. Crystal statistics. I. A two-dimensional model w ith an order- disorder transition. Phys. Rev., 65(3/4):117–149, 1944
work page 1944
-
[16]
L. Onsager. The effects of shape on the interaction of colloidal particles. Ann. New York Acad. Sci ., 51(4):627–659, 1949
work page 1949
-
[17]
M. Petkovˇ sek, H. Wilf, and D. Zeilberger. A=B. AK Peters, Ltd., Wellesley, MA, USA, 1996. 55
work page 1996
-
[18]
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
work page 2023
-
[19]
H. S. Wilf and D. Zeilberger. An algorithmic proof theory for hype rge- ometric (ordinary and “ q”) multisum/integral identities. Invent. Math ., 108(3):575–633, June 1992
work page 1992
-
[20]
D. Zeilberger. The Method of Creative Telescoping. J. Symb. Comput ., 11(3):195–204, Mar. 1991. 56
work page 1991
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.