$k$-Convex Polyominoes by Semi-perimeter

Andrew R. Conway; Anthony J. Guttmann

REVIEW 3 major objections 3 minor 16 references

$k$-Convex Polyominoes by Semi-perimeter

T0 review · 3 major / 3 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper conjectures a single closed-form generating function, built from Chebyshev polynomials, that gives the exact semi-perimeter counts of k-convex polyominoes for every k and reproduces all enumerated coefficients through k=7.

desk verdict A transparent, data-driven conjecture for the generating function of k-convex polyominoes (k≥2) that is worth a serious referee, but the enumeration data are not formally verified. read the letter →

arxiv 2607.12448 v2 pith:KQV7FOQZ submitted 2026-07-14 math.CO math-phmath.MP

Andrew R. Conway , Anthony J. Guttmann This is my paper · ORCID

classification math.COmath-phmath.MP MSC 05A1505B50

keywords k-convexpolyominoessemi-perimeterenumerationgeneratingfunctionChebyshevpolynomialstransfermatrixconvexasymptoticconjecturedclosedform

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper tries to establish a complete semi-perimeter enumeration for k-convex polyominoes: it conjectures that the generating function for every k has one closed form Q_k(x)=Q_{1,k}(x)−Q_{2,k}(x), written entirely through Chebyshev polynomials. The form was found by feeding transfer-matrix counts for k=3,...,7 through a nonlinear change of variable and reading off rational functions; the known case of fully convex polyominoes is recovered as k→∞. The authors are explicit that this is a conjecture, not a proof: the enumeration algorithm's correctness is asserted rather than justified, and the closed form is checked against series rather than derived. If the conjecture is right, all k-convex polyomino counts are known exactly, and their large-n behaviour begins with 4^n[n(k−1)/(8(k+1)) − √n/(2√π(k+1))].

What carries the argument

The central object is the two-term ansatz Q_k=Q_{1,k}−Q_{2,k}, with both pieces sharing the denominator d_k(x)=x^k U_k((1−2x)/(2x)); Chebyshev polynomials of the second kind, U_k, arise from solving the recurrence d_k=(1−2x)d_{k−1}−x^2 d_{k−2}, while the first-kind polynomials T_k enter through the perfect-square numerator r_k(x)^2=[2x^{k/2}T_k(1/(2√x))]^2. The transfer-matrix algorithm supplies the coefficient data; the change of variable y=1−√(1−4x) turns the algebraic piece into a rational function, so the polynomial families can be identified by rational-function interpolation and then solved in closed form.

What would settle it

Enumerate 8-convex polyominoes of semi-perimeter up to 25 by an independent algorithm—for example, exhaustive generation of convex polyominoes with a direct pairwise minimum-bend check—and compare with the coefficient series obtained by expanding Q_8(x) from the conjectured formula; the paper only provides data through k=7, so a mismatch at k=8 would falsify the conjecture, while a match would transfer the evidentiary weight to the extrapolation.

Watch

Extended reading notes

Core claim

For fixed k, the paper claims the semi-perimeter generating function is Q_k(x)=Q_{1,k}(x)−Q_{2,k}(x), where Q_{1,k} is a rational function with denominator (1−4x)^2 d_k(x) and Q_{2,k} carries the factor (1−4x)^{−3/2} d_k(x), with d_k(x)=x^k U_k((1−2x)/(2x)). The numerator of Q_{1,k} is expressed through U_k and U_{k−1}, while the numerator of Q_{2,k} is a perfect square whose root is expressed through T_k. The authors report that this formula reproduces all 25 coefficients for each k=3,...,7 and reduces to the known convex-polyomino generating function as k→∞. They label the result as conjectured and base it on data analysis.

Load-bearing premise

The load-bearing premise is that the transfer-matrix state—a tuple (VN,VH,HN,HH) for each tracked cell plus the dominance rule—stores exactly the minimum-bend information needed to certify k-convexity as columns are added; Appendix A asserts this but gives no proof, and a polyomino needing richer state would invalidate every inferred coefficient and the conjectured formula.

Editorial extensions

If this is right

For each fixed k, the exact coefficient sequence for semi-perimeter n+2 can be computed from Q_k(x) to any order without further enumeration.
The leading asymptotics 4^n[n(k−1)/(8(k+1)) − √n/(2√π(k+1))] give a one-parameter family of growth rates interpolating between the known 2-convex rate n/24 and the fully convex rate n/8.
The k→∞ limit of the formula reproduces the known generating function for all convex polyominoes, providing an independent consistency check.
Existing exact results for 2-convex and fully convex polyominoes fit the same two-piece template, so the conjecture unifies the earlier semi-perimeter solutions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper mentions area enumeration up to 65 cells but does not analyse it; a parallel closed form for area counts is the most obvious next target and would test the same ansatz in a different regime.
The conjectured asymptotic has the sub-leading √n term vanish as k→∞, whereas the exact convex-polyomino result retains it; this signals that the k→∞ and n→∞ limits do not commute and invites a matched-asymptotics analysis.
Because d_k, r_k, and p_k are each defined by three-term recurrences in k, the generating functions might satisfy recurrences in k as well as n; finding them could turn the data-supported conjecture into an inductive proof.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First thing you should know: this paper is a conjecture, not a theorem, and it may well be right. The authors give a closed-form generating function, built from Chebyshev polynomials, for k-convex polyominoes by semi-perimeter for k≥2. Prior to this, only the k=2 and fully convex cases were known; k>2 was open. That makes this a real advance, even as a conjecture.

The paper is honest about its status. The solution is reverse-engineered from exact enumerations for k=3..7, with recurrences for the numerator and denominator polynomials extrapolated to all k. The recurrences are simple, the k→∞ limit recovers the known convex polyomino generating function (verified by Rinaldi), and the coefficient checks give resounding agreement. They ship the code on GitLab, which is good diligence.

Soft spots, in proportion. The main one is the transfer-matrix algorithm in Appendix A. The state is a 4-tuple per site, and the paper asserts rather than proves that this captures all minimum-bend information. The dominance check is described as 'fiddly and error-prone' and the implementation is admitted to be imperfect. If the state space is insufficient, every count is wrong and the conjectured formula collapses. This is not a demonstrated flaw, but it is a load-bearing assumption in the evidence base. A referee should either prove the state sufficiency or cross-check against another method and provide k=8 data. Second, the paper sometimes says 'all k' but the formula clearly does not include k=1 (L-convex has a different structure); the k≥2 restriction needs to be explicit. Minor quibble: the asymptotics are stated with little derivation, but they follow from the generating function.

For a colleague working in polyomino enumeration, this is a worthwhile read and a plausible answer to an open problem. It deserves to go to peer review; the conjecture is specific, falsifiable, and the evidence is solid enough to merit referee time. I would encourage the referees to ask for a proof of the recurrences or at least a convincing heuristic, and for a formal or independent check of the enumeration algorithm. The k=1 wording should be fixed before publication.

Referee Report

3 major / 3 minor

Summary. The paper reports a conjectured closed-form generating function Q_k(x) = Q_{1,k}(x) - Q_{2,k}(x) for k-convex polyominoes counted by semi-perimeter. The authors first fit explicit generating functions to enumeration data for k = 3,...,7, then extrapolate recurrences for the polynomials d_k, r_k, p_k to all k and solve them in terms of Chebyshev polynomials. The k→∞ limit is reported to reproduce the known convex-polyomino generating function, and asymptotics for the coefficients are derived. The paper is explicitly computational and conjectural: no proof of the transfer-matrix algorithm or of the recurrences is offered.

Significance. If correct, this result would solve the semi-perimeter enumeration of all k-convex polyominoes and provide exact asymptotics, generalizing the known L-, Z-, and fully convex cases. The paper has several genuine strengths: explicit formulas for k = 3,...,7, internal checks from series coefficients beyond those used for fitting, a consistency check at k→∞, and a publicly available implementation. The main weakness is that the supporting enumeration data are produced by a dynamic-programming algorithm whose correctness is asserted rather than proved, so the empirical evidence is not yet conclusive.

major comments (3)

[Appendix A.3, 'Full problem: k-convex polyominoes'] The central evidence for the conjecture is the enumeration data, and the load-bearing assumption is that the per-site tuple (VN, VH, HN, HH) together with the dominance rule exactly captures the information needed to compute the minimum number of bends to every future cell. The manuscript asserts this but does not prove it. In particular, the update retains only one 'best route' per starting orientation; a route with more bends before crossing the current vertical border B may nevertheless lead to a smaller global minimum-bend path to a later column because it crosses at a more favorable height. Similarly, the claim that only the top cell of the new column needs to be checked when updating the global maximum is not justified. Since every fitted polynomial and recurrence is derived from these counts, an error here would invalidate the central conjecture. Please provide a formal invariant
[§4.1, recurrences for d_k, r_k, p_k] The universal formulas are obtained by observing recurrences for k ≤ 7 and then solving them. Even though the paper carefully labels the result as conjectured, the claim for all k rests entirely on the assumption that these recurrences persist. The k→∞ check attributed to Rinaldi tests the limit of the closed form, not the recurrences at finite k. To make the conjecture robust, the authors should either (i) prove the recurrences from the combinatorial definition, (ii) check k = 8 and, if possible, k = 9 with a few more coefficients, or (iii) state precisely how many coefficients would be needed to determine p_k and q_k for general k. I would also ask for a quantitative statement of the 'extra terms confirm the result' claim: for each k = 3,...,7, how many coefficients are used to fit and how many are checked?
[§4.2, Eq. for Q_k] The final closed form is an interpolation of the fitted k = 3,...,7 cases; the structural decomposition Q = Q_1 - Q_2 and the square form of q_k are assumed rather than derived. This is acceptable if the paper is clearly a conjecture paper, but it should be made explicit what additional evidence would be needed to turn the conjecture into a theorem. In particular, the exact form of p_k and the squareness of q_k are empirical. A short derivation or a combinatorial interpretation of at least one of the recurrences would materially strengthen the paper.

minor comments (3)

[Appendix A.1] There is a typographical error 'they don?t affect anything' where 'don't' is intended. Figure 1's caption also has 'polyonimo' instead of 'polyomino'.
[§3.1–§3.5] The series coefficients are printed as one long parenthesized expression times x^2. A table listing the coefficients in increasing powers would be much easier to verify and would help readers compare the formulas with the data.
[§4.2] The k→∞ consistency check is attributed to 'Rinaldi S.: Private communication'. Since this check is used as evidence for the conjecture, including the short calculation as an appendix or as a cited published reference would make the paper self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the conjectured generating functions are empirical fits that are honestly labeled and checked against held-out series coefficients.

full rationale

The paper's central object is explicitly a conjecture inferred from enumeration data, not a derivation from the definition. The closed forms for 3<=k<=7 are obtained by fitting rational/algebraic forms to the first N coefficients and then verifying against additional coefficients; the paper states: 'if we have polynomials of degrees that require say, 15 terms for their specification, and we have 25 terms, the extra 10 terms provide resounding confirmation of our conjectured results.' That is a genuine out-of-sample check, not a fitted input renamed as a prediction. The recurrences for d_k, r_k and p_k are inferred from the fitted polynomials and then solved, so the general k formula is an extrapolation/conjecture rather than a circular derivation. The k->infinity check is attributed to Rinaldi (private communication) and correctly recovers the known convex-polyomino generating function; this is consistency checking, not self-citation. The only notable weakness is Appendix A.3, where the transfer-matrix state is asserted sufficient and the dominance check is admitted to be imperfect ('The program used does not do a perfect job of this as the check is fiddly and error-prone'). That is a correctness/robustness concern about the enumeration data, not a circularity: the data are generated independently of the fitted formula, and the formula does not reduce to the algorithm's state by construction. No load-bearing self-citation, imported uniqueness theorem, or definitional equivalence was found.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new particles, forces, or entities. The central claim rests on three unproved structural choices: the ansatz form, the recurrences inferred from finite data, and the correctness of the enumeration algorithm. These are the costs of a data-driven conjecture.

free parameters (3)

Ansatz structure (Q1-Q2 with polynomial d_k and singular factors) = Q1 has denominator (1-4x)^2 d_k; Q2 has denominator (1-4x)^{3/2} d_k
This form is assumed from the k=2 and fully convex cases and imposed on all k; it is not derived from the definition of k-convex.
Recurrences for d_k, r_k, p_k = d_k=(1-2x)d_{k-1}-x^2 d_{k-2}; r_k=r_{k-1}-x r_{k-2}; p_k=(1-x)p_{k-1}+(x^2-x)p_{k-2}+x^3 p_{k-3}
The recurrences are inferred by inspecting the fitted polynomials for k≤7; they are data-driven choices, not proven consequences.
Initial polynomials for recurrences = p0=4x^3+5x^2-6x+1; p1=-16x^3+20x^2-8x+1; p2=-4x^5+19x^4-48x^3+35x^2-10x+1; d0=1,d1=1-2x; r0=2,r1=1
These initials are chosen to match known L/Z/convex data or to make the recursion consistent; they are inputs rather than derived quantities.

assumptions (5)

domain assumption The transfer-matrix algorithm in Appendix A exactly enumerates k-convex polyominoes by semi-perimeter.
No proof is given that the four-number tuple per site and dominance elimination capture the minimum-bend path for all pairs of cells; the algorithm's correctness is the foundation of all numerical data.
ad hoc to paper The generating function has the form Q1-Q2 with denominator (1-4x)^2 d_k and (1-4x)^{3/2} d_k for all k.
This ansatz is inferred from the known k=2 and fully convex cases, not proven; §4.2 assumes it for all k.
ad hoc to paper The recurrences for d_k, r_k, p_k observed for k≤7 hold for all k.
The closed form is obtained by solving these recurrences; their validity for all k is the conjecture itself, not established.
standard math Standard results on Chebyshev polynomials U_k, T_k and their identities are used.
Used in §4.1-4.2 to rewrite d_k, r_k, p_k in Chebyshev form.
domain assumption The known generating functions for L-convex, Z-convex, and fully convex polyominoes are correct.
Used as benchmarks to fit initial conditions and to test the k→∞ limit; they are cited from prior literature.

how reviews work

0 comments

Cite this review

Pith. "Pith review of $k$-Convex Polyominoes by Semi-perimeter." pith.science (2026). https://pith.science/paper/KQV7FOQZ

@misc{pith2026260712448,
  author       = {Pith},
  title        = {Pith review of: $k$-Convex Polyominoes by Semi-perimeter},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KQV7FOQZ}},
  note         = {Machine review of arXiv:2607.12448}
}

abstract

We give the conjectured solution for the generating function of $k$-convex polyominoes, enumerated by semi-perimeter. The solution was obtained from the analysis of enumeration data that we generated.

Figures

Figures reproduced from arXiv: 2607.12448 by the authors.

**Figure 2.** Example addition of a new column. 3. Completing the algorithm. After executing step 2, replace L by LL and repeat step 2. Iterate until the list of elements is empty. As the variable use will be increased by at least one for each application of step 2, eventually all elements will exceed the maximum area constraint and will be discarded resulting in an empty list. After one iteration of step 2, R will contain all th… view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 3 canonical work pages

[1]

Castiglione, A

G. Castiglione, A. Frosini, A. Restivo & S. Rinaldi (2005):Enumeration of L-convex polyominoes by rows and columns.Theoretical Computer Science347(1), pp. 336–352, doi:10.1016/j.tcs.2005.06.031

work page doi:10.1016/j.tcs.2005.06.031 2005
[2]

169–206, doi:10.1016/0304-3975(84)90116-6

Marie-Pierre Delest & Gérard Viennot (1984):Algebraic languages and polyominoes enumeration.Theoreti- cal Computer Science34(1), pp. 169–206, doi:10.1016/0304-3975(84)90116-6

work page doi:10.1016/0304-3975(84)90116-6 1984
[3]

54–72, doi:10.1016/j.aam.2006.07.004

Enrica Duchi, Simone Rinaldi & Gilles Schaeffer (2008):The number of Z-convex polyominoes.Advances in Applied Mathematics40(1), pp. 54–72, doi:10.1016/j.aam.2006.07.004

doi:10.1016/j.aam.2006.07.004 2008
[4]

I. G. Enting, A. J. Guttmann, L. B. Richmond & N. C. Wormald (1992):Enumeration of Almost-Convex Poly- gons on the Square Lattice.Random Structures & Algorithms3(4), pp. 445–461, doi:10.1002/rsa.3240030407

work page doi:10.1002/rsa.3240030407 1992
[5]

Massazza (2022):On counting k-convex polyominoes

P. Massazza (2022):On counting k-convex polyominoes. In Ugo Dal Lago & Daniele Gorla, editors:Proc. of the 23rd Italian Conference on Theoretical Computer Science,CEUR Workshop Proceedings3284, CEUR- WS, Aachen, pp. 116–121

2022
[6]

A Description of the algorithm for countingk-convex polyominoes

Rinaldi S.:Private communication. A Description of the algorithm for countingk-convex polyominoes. A fairly standard dynamic programming/transfer matrix algorithm is used. For explanatory purposes we will start with a description of a well known algorithm to enumerate column-convex polyominoes. This 74k-Convex Polyominoes by Semi-perimeter will then be mo...
[7]

Make a list Lof each of these, containing three values: •Signature: The height of the column (1 toA)

Initialization.Start with the leftmost column and consider all columns of length 1 toA. Make a list Lof each of these, containing three values: •Signature: The height of the column (1 toA). •V ariable Use: The total area used so far (which will be the same as the height at this point). •Multiplicity: The number of ways of getting to this point (which will...
[8]

The next column may be empty - the polyomino is finished

Next column.Next take each elemente∈Lof the list produced by the previous step and consider what could go in the next column. The next column may be empty - the polyomino is finished. In this case add the multiplicity ofeto the results vector in the position indicated by the variable use ofe. The next column may be non-empty. Consider all possible column ...

Show all 16 references

[9]

Iterate until the list of elements is empty

Completing the algorithm.After executing step 2, replaceLbyLLand repeat step 2. Iterate until the list of elements is empty. As the variable use will be increased by at least one for each application of step 2, eventually all elements will exceed the maximum area constraint an...
[10]

Enumerating by other variables.The same algorithm can be used to enumerate by other variables - just replace the variable use computation appropriately. For instance, if counting by perimeter, the step 1 variable used for a column of heighthwould be 2h+2 (including the minimum...
[11]

Suppose there are S possible signatures and V possible variable uses

Complexity of the algorithm.Step 2 is the main complexity. Suppose there are S possible signatures and V possible variable uses. For enumerating convex poly- ominoes by area both V and S are O(A). For step 2, there are O(A) possible next columns and O(A) possible relative posi...
[12]

Each vertical bond should then go as far as possible up, and each horizontal bond should go as far as possible to the right

What the best route means.What information do we need for each point in the polyomino? The best route to a point could potentially start with either a vertical bond or a horizontal bond. Each vertical bond should then go as far as possible up, and each horizontal bond should g...
[13]

In this case there is no point keeping track of the discardable site.Sis said to dominate the other sites

Eliminating dominated information.There are some sites whose best route information can be discarded as some other siteSdominates them - that is, it is always harder to get fromSto somewhere than from the discardable site. In this case there is no point keeping track of the di...
[14]

Start state.For a start column of heightH,the initial state will be a single cell (the bottom one) with (VN=2,VH=H−1,HN=1,HH=0). Note that theVN=2 limit start means the algorithm cannot distinguish betweenLconvex polyomi- noes (1 bend) and the trivial case of polyominoes with ...
[15]

All prior cells’ information must be updated

Update.Consider a new column of heightH ′ starting at a height ofδabove the prior column of heightH.If the new column starts below the old column(δ<0),a new cell must be added with the same values as the start state(VN=2,VH=H−1,HN=1,HH=0). All prior cells’ information must be ...
[16]

In practice the number of states (and thus the time and memory use) seem to grow exponentially with the size of the enumeration

Complexity.The number of possible cells that are not dominated is hard to characterise. In practice the number of states (and thus the time and memory use) seem to grow exponentially with the size of the enumeration. 78k-Convex Polyominoes by Semi-perimeter In practice, to cou...

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.

[1] [1]

Castiglione, A

G. Castiglione, A. Frosini, A. Restivo & S. Rinaldi (2005):Enumeration of L-convex polyominoes by rows and columns.Theoretical Computer Science347(1), pp. 336–352, doi:10.1016/j.tcs.2005.06.031

work page doi:10.1016/j.tcs.2005.06.031 2005

[2] [2]

169–206, doi:10.1016/0304-3975(84)90116-6

Marie-Pierre Delest & Gérard Viennot (1984):Algebraic languages and polyominoes enumeration.Theoreti- cal Computer Science34(1), pp. 169–206, doi:10.1016/0304-3975(84)90116-6

work page doi:10.1016/0304-3975(84)90116-6 1984

[3] [3]

54–72, doi:10.1016/j.aam.2006.07.004

Enrica Duchi, Simone Rinaldi & Gilles Schaeffer (2008):The number of Z-convex polyominoes.Advances in Applied Mathematics40(1), pp. 54–72, doi:10.1016/j.aam.2006.07.004

doi:10.1016/j.aam.2006.07.004 2008

[4] [4]

I. G. Enting, A. J. Guttmann, L. B. Richmond & N. C. Wormald (1992):Enumeration of Almost-Convex Poly- gons on the Square Lattice.Random Structures & Algorithms3(4), pp. 445–461, doi:10.1002/rsa.3240030407

work page doi:10.1002/rsa.3240030407 1992

[5] [5]

Massazza (2022):On counting k-convex polyominoes

P. Massazza (2022):On counting k-convex polyominoes. In Ugo Dal Lago & Daniele Gorla, editors:Proc. of the 23rd Italian Conference on Theoretical Computer Science,CEUR Workshop Proceedings3284, CEUR- WS, Aachen, pp. 116–121

2022

[6] [6]

A Description of the algorithm for countingk-convex polyominoes

Rinaldi S.:Private communication. A Description of the algorithm for countingk-convex polyominoes. A fairly standard dynamic programming/transfer matrix algorithm is used. For explanatory purposes we will start with a description of a well known algorithm to enumerate column-convex polyominoes. This 74k-Convex Polyominoes by Semi-perimeter will then be mo...

[7] [7]

Make a list Lof each of these, containing three values: •Signature: The height of the column (1 toA)

Initialization.Start with the leftmost column and consider all columns of length 1 toA. Make a list Lof each of these, containing three values: •Signature: The height of the column (1 toA). •V ariable Use: The total area used so far (which will be the same as the height at this point). •Multiplicity: The number of ways of getting to this point (which will...

[8] [8]

The next column may be empty - the polyomino is finished

Next column.Next take each elemente∈Lof the list produced by the previous step and consider what could go in the next column. The next column may be empty - the polyomino is finished. In this case add the multiplicity ofeto the results vector in the position indicated by the variable use ofe. The next column may be non-empty. Consider all possible column ...