Pith. sign in

REVIEW 5 minor 25 references

Log-concavity and log-convexity in the theory of the Graham--Knuth--Patashnik recurrences

T0 review · 0 major / 5 minor · reviewed 2026-07-11 · grok-4.5

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

Pith's one-line read Indeterminate GKP triangles are coefficientwise strongly log-concave in each row, and their row polynomials are strongly log-convex (hence Hankel-TP of order 2).

desk verdict Clean coefficientwise upgrade of classical GKP inequalities that settles Hankel-TP2 for the full six-parameter family. read the letter →

arxiv 2607.04217 v1 pith:TKQP2JLN submitted 2026-07-05 math.CO

Jesús Salas This is my paper · ORCID
classification math.CO MSC 05A2011B3711B8313F20
keywords Graham–Knuth–Patashnikrecurrencecoefficientwiselog-concavitylog-convexityHankeltotalpositivitypartiallyorderedringsrow-generatingpolynomialstriangulararrays
topics The Collatz Conjecture
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 Graham–Knuth–Patashnik (GKP) recurrence produces a triangular array of polynomials in six indeterminate parameters. This paper proves that every fixed row of that array is strongly log-concave when positivity is understood coefficientwise: every 2-by-2 minor formed by consecutive entries has nonnegative coefficients. The same argument, lifted to the ordinary generating polynomials of the rows, shows that the sequence of those polynomials is strongly log-convex coefficientwise in the seven variables consisting of the indeterminate x together with the six parameters. Strong log-convexity immediately implies that every 2-by-2 Hankel minor is nonnegative, so the sequence is coefficientwise Hankel-totally positive of order 2. The results recover and strengthen classical real-parameter theorems of Kurtz, Liu–Wang and Chen–Wang–Yang by removing all numerical inequalities on the parameters and working purely inside the polynomial ring.

What carries the argument

The mixed comparison R(n,m,k,ℓ,r)=T(n,k)T(m,ℓ-r)-T(n,ℓ)T(m,k-r) ≽ 0 (Lemma 3.2), proved by induction on the second index m and used to cancel negative terms when the derivative identity for the log-convexity difference is expanded.

What would settle it

Exhibit a concrete monomial that appears with a negative coefficient in any of the polynomials T(n,k)T(n,ℓ)-T(n,k-1)T(n,ℓ+1) or P_{n-1}P_{m+1}-P_n P_m for small n,m; or find a numerical specialization of the parameters that violates the classical real inequalities yet still produces a negative Hankel 2-minor.

Watch

Extended reading notes

Core claim

When the six GKP parameters are treated as indeterminates, each row sequence (T(n,k))_k is coefficientwise strongly log-concave, and the sequence of row-generating polynomials (P_n(x))_n is coefficientwise strongly log-convex (hence Hankel-totally positive of order 2) jointly in x and the six parameters.

Load-bearing premise

The inductive step that produces a nonnegative multiple of (ℓ-k) must stay inside the polynomial ring and never require division by a non-unit.

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.

Referee Report

0 major / 5 minor

Summary. The paper studies the triangular array T(n,k;µ) defined by the Graham–Knuth–Patashnik recurrence with six indeterminate parameters µ=(α,β,γ,α',β',γ'). It proves that each fixed-n sequence (T(n,k;µ))_{k≥0} is coefficientwise strongly log-concave in the six parameters (Theorem 1.4 / Theorem 2.1 and Corollary 2.2). It then proves that the sequence of row-generating polynomials (P_n(x;µ))_{n≥0} is coefficientwise strongly log-convex jointly in x and the six parameters (Theorem 1.5 / Theorem 4.1), and therefore that the associated Hankel matrix is coefficientwise totally positive of order 2 (Corollary 1.7). The arguments are elementary inductions that stay inside the polynomial rings Z[µ] and Z[x,µ] equipped with the coefficientwise partial order; two general lattice-theoretic propositions of Sokal (Propositions 2.3 and 4.2) convert ordinary strong inequalities into the multi-step versions used in the statements.

Significance. The results give a uniform, parameter-free strengthening of the classical real-variable log-concavity theorems of Kurtz and of the coefficientwise log-convexity theorems of Liu–Wang and Chen–Wang–Yang. By working throughout with indeterminates and the coefficientwise order, the paper obtains the strongest possible positivity statements that specialize to all previously known numerical cases. The Hankel-TP2 corollary is a concrete partial advance toward Sokal’s open conjecture of full coefficientwise Hankel-total positivity for the same family. The proofs are self-contained, avoid division by non-units, and make the algebraic identities completely explicit, so the contribution is both technically solid and immediately usable by other workers in combinatorial positivity.

minor comments (5)
  1. In the statement of Theorem 1.4 the range is written “ℓ≥k≥0 and r≥1”; the accompanying Remark 2 correctly notes that one should also have k≥r, but the text never makes this restriction explicit. A single clarifying sentence would remove any ambiguity for readers who do not consult the remark.
  2. The same notational issue appears for the range of Theorem 1.5 (n≥r is required). The remark already warns about the danger of setting P_{-k}=0, yet the theorem statement itself still writes m≥n≥r≥1 without further comment; aligning the statement with the remark would improve readability.
  3. In the inductive step of Theorem 2.1 the author writes “≻” after applying the induction hypothesis (display (2.11)). While the final claim is only ≻0, the intermediate inequalities are actually ≻0 only when the relevant indices stay inside the triangle; a brief parenthetical remark that the boundary cases are handled separately (as is done later) would make the chain of inequalities fully rigorous at first reading.
  4. The paper cites Sokal’s unpublished notes [18,19] for the general lattice-theoretic propositions and for the Hankel-total-positivity conjecture. Since both propositions are proved in full inside the manuscript, the dependence is harmless, but a short footnote indicating that the proofs of Propositions 2.3 and 4.2 are self-contained would be helpful to readers who cannot access the notes.
  5. Typographical consistency: the author sometimes writes “β′” and sometimes “(β′)^{2}”; a uniform style for squared primed parameters would improve the visual appearance of the longer displays (especially (2.9) and (4.12)).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: self-contained inductive proofs of coefficientwise strong log-concavity/log-convexity for GKP arrays over indeterminates.

full rationale

The paper proves Theorems 1.4/2.1 (strong log-concavity of each row T(n,·;µ) in the coefficientwise order on Z[µ]), Lemma 3.2 (the mixed inequality R), Theorems 1.5/4.1 (strong log-convexity of the row polynomials Pn(x;µ) in Z[x,µ]), and the Hankel-TP2 corollary by direct induction on the GKP recurrence itself. Base cases are trivial (n=0 or m=n) or reduce to already-established single-row positivity via re-indexing (Lemma 3.1). Inductive steps substitute the recurrence, apply the induction hypothesis, and obtain non-negative polynomial factors (e.g., β^{2}(ℓ+1-k), (ℓ-k)[βT+eta'T], (p-2k)^{2}T[eta T+eta'T]) with no division and no appeal to the target inequalities as hypotheses. The two general lattice propositions of Sokal are proved in full inside the paper (Props. 2.3 and 4.2). Classical real-variable theorems of Kurtz, Liu–Wang and Chen–Wang–Yang are cited only for motivation and are not used as load-bearing premises. There are no fitted parameters, no self-referential normalizations, and no uniqueness claims imported from prior work by the same author. The derivation is therefore independent of its conclusions by construction.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The paper works entirely inside the polynomial ring Z[α,β,γ,α',β',γ',x] equipped with the coefficient-wise partial order. No free parameters are fitted; the only background axioms are the definition of the GKP recurrence, the standard ring axioms, and two elementary lattice-theoretic facts about strongly log-concave/convex sequences that are proved in the text.

assumptions (2)
  • domain assumption The GKP recurrence T(n,k)=(αn+βk+γ)T(n-1,k)+(α'n+β'k+γ')T(n-1,k-1) with T(0,k)=δk0 defines a unique triangular array of polynomials in Z[µ].
    Taken as the definition of the objects under study (Eq. (1.1)).
  • standard math In a partially ordered commutative ring, strong log-concavity implies the r-step inequalities anaℓ-an-raℓ+r≽0 (and the dual statement for log-convexity).
    Proved as Propositions 2.3 and 4.2; used only to upgrade the r=1 statements to the full Theorems 1.4 and 1.5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Log-concavity and log-convexity in the theory of the Graham--Knuth--Patashnik recurrences." pith.science (2026). https://pith.science/paper/TKQP2JLN

@misc{pith2026260704217,
  author       = {Pith},
  title        = {Pith review of: Log-concavity and log-convexity in the theory of the Graham--Knuth--Patashnik recurrences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TKQP2JLN}},
  note         = {Machine review of arXiv:2607.04217}
}
abstract

We study the triangular array $T(n,k;\mu)$ defined by the Graham--Knuth--Patashnik recurrences $$ T(n,k) \;=\; (\alpha n + \beta k + \gamma) \, T(n-1,k) + (\alpha' n + \beta' k + \gamma') \, T(n-1,k-1) $$ with initial condition $T(0,k)=\delta_{k,0}$ and parameters $\mu=(\alpha,\beta,\gamma,\alpha',\beta',\gamma')$, which are considered to be indeterminates. We first prove that, for any fixed $n\ge 0$, the sequence $(T(n,k;\mu))_{k\ge 0}$ is strongly log-concave with the coefficientwise partial order in the variables $\alpha,\beta,\gamma,\alpha',\beta',\gamma'$. Moreover, we show that the sequence of the corresponding row-generating polynomials $(P_n(x;\mu))_{n\ge 0}$ is strongly log-convex with the coefficientwise partial order in the variables $x$ and $\alpha,\beta,\gamma,\alpha',\beta',\gamma'$. Finally, we show that this sequence is coefficientwise Hankel-totally positive of order 2 with the same partial order.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 7 linked inside Pith

  1. [1]

    Aubert and B

    V.M.R. Aubert and B. Randrianirina, Explicit formulas and combinatorial in- terpretation of triangular arrays,arXiv:2511.18351[math.CO]

    arXiv

  2. [2]

    Barbero G., J

    J.F. Barbero G., J. Salas, and E.J.S. Villase˜ nor, Bivariate generating functions for a class of linear recurrences: General structure, J. Combin. Theory A125, 146–165 (2014),arXiv:1307.2010[math.CO]

    arXiv 2014

  3. [3]

    Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, Contemp

    F. Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, Contemp. Math.178(1994) 71–89

    1994

  4. [4]

    Chen, L.X.W

    W.Y.C. Chen, L.X.W. Wang, and A.L.B. Yang, Recurrence relations for stronglyq-log-convex polynomials, Canad. Math. Bull. 54, 217–229 (2011), arXiv:0806.3641[math.CO]

    arXiv 2011

  5. [5]

    Fallat and C.R

    S.M. Fallat and C.R. Johnson,Totally Nonnegative Matrices(Princeton Univer- sity Press, Princeton NJ, 2011)

    2011

  6. [6]

    Fuchs,Partially Ordered Algebraic Systems(Dover Publications Inc., Mineola NY, 2011)

    L. Fuchs,Partially Ordered Algebraic Systems(Dover Publications Inc., Mineola NY, 2011)

    2011

  7. [7]

    Gantmacher and M.G

    F.R. Gantmacher and M.G. Krein,Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems(AMS Chelsea Publishing, Providence RI, 2002)

    2002

  8. [8]

    Graham, D.E

    R.L. Graham, D.E. Knuth and O. Patashnik,Concrete Mathematics: A Foun- dation for Computer Science, 2nd ed. (Addison-Wesley, Reading MA, 1994)

    1994

Show all 25 references
  1. [9]

    Karlin,Total Positivity(Stanford University Press, Stanford CA, 1968)

    S. Karlin,Total Positivity(Stanford University Press, Stanford CA, 1968)

    1968

  2. [10]

    Kurtz, A note on concavity properties of triangular arrays of numbers, J

    D.C. Kurtz, A note on concavity properties of triangular arrays of numbers, J. Combin. Theory A13, 135–139 (1972)

    1972

  3. [11]

    Liu and Y

    L.L. Liu and Y. Wang, On the log-convexity of combinatorial sequences, Adv. Appl. Math.39, 453–476 (2007),arXiv:math/0602672

    2007 arXiv

  4. [12]

    Maier, Triangular recurrences, generalized Eulerian numbers, and related number triangles, Adv

    R.S. Maier, Triangular recurrences, generalized Eulerian numbers, and related number triangles, Adv. Appl. Math.146, 102485 (2023),arXiv:2207.10224

    2023 arXiv

  5. [13]

    Mansour and M

    T. Mansour and M. Shattuck, A combinatorial approach to a general two-term recurrence, Discrete Appl. Math.161, 2084–2094 (2013). 15

  6. [14]

    Neuwirth, Recursively defined combinatorial functions: extending Galton’s boards, Discrete Math.132, 33–51 (2001)

    E. Neuwirth, Recursively defined combinatorial functions: extending Galton’s boards, Discrete Math.132, 33–51 (2001)

    2001

  7. [15]

    Pinkus,Totally Positive Matrices(Cambridge University Press, Cambridge, UK, 2010)

    A. Pinkus,Totally Positive Matrices(Cambridge University Press, Cambridge, UK, 2010)

    2010

  8. [16]

    Salas and A.D

    J. Salas and A.D. Sokal, The Graham-Knuth-Patashnik recurrence: Sym- metries and continued fractions, Electron. J. Combin.28, #P2.18 (2021), arXiv:2008.03070[math.CO]

    2021 arXiv

  9. [17]

    Saumard and J.A

    A. Saumard and J.A. Wellner, Log-concavity and strong log-concavity: A review, Statist. Surv.8, 45-114 (2014),arXiv:1404.5886

    2014 arXiv

  10. [18]

    Sokal, unpublished (2014)

    A.D. Sokal, unpublished (2014)

    2014

  11. [19]

    Sokal, Coefficientwise Hankel-total positivity, in preparation (2026)

    A.D. Sokal, Coefficientwise Hankel-total positivity, in preparation (2026)

    2026

  12. [20]

    Spivey, On solutions to a general combinatorial recurrence, J

    M.Z. Spivey, On solutions to a general combinatorial recurrence, J. Integer Seq. 14, article 11.9.7 (2011)

    2011

  13. [21]

    Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Ann

    R.P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Ann. N.Y. Acad. Sci.576(1989) 500–534

    1989

  14. [22]

    P. Th´ eorˆ et, Hyperbinomiales: Doubles suites satisfaisant ` a des ´ equations aux diff´ erences partielles de dimension et d’ordre deux de la formeH(n, k) = p(n, k)H(n−1, k) +q(n, k)H(n−1, k−1), Th` ese de doctorat, Universit´ e du Qu´ ebec ` a Montr´ eal (1994)

    1994

  15. [23]

    Th´ eorˆ et, Fonctions g´ en´ eratrices pour une classe d’´ equations aux diff´ erences partielles, Ann

    P. Th´ eorˆ et, Fonctions g´ en´ eratrices pour une classe d’´ equations aux diff´ erences partielles, Ann. Sci. Math. Qu´ ebec19, 91–105 (1995)

    1995

  16. [24]

    Th´ eorˆ et, Relations matricielles pour hyperbinomiales, Ann

    P. Th´ eorˆ et, Relations matricielles pour hyperbinomiales, Ann. Sci. Math. Qu´ ebec 19, 197–212 (1995)

    1995

  17. [25]

    Wilf, The method of characteristics, and ‘problem 89’ of Graham, Knuth and Patashnik, preprint 2004,arXiv:math/0406620

    H.S. Wilf, The method of characteristics, and ‘problem 89’ of Graham, Knuth and Patashnik, preprint 2004,arXiv:math/0406620. 16

    2004 arXiv

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.