Gilmore's crossing–nesting conjecture

What Lean checks

Lean proves the full crossing–nesting identity for the stabilized product-defined matrix, with alignment and size refinements, over every commutative ring. Canonical matching lists enumerate exactly the literal perfect matchings; their weights count the actual crossing, nesting and alignment inequalities. Fresh strict compilation, the all-owned audit of 449 declarations (346 theorem declarations, including private declarations) and all 20 required endpoints, and stock-kernel replay passed. Local receipt. The combined repository gate and hosted validation are separate.

Statement and source

Tomack Gilmore's Trees, forests, and total positivity: I. q-trees and q-forests matrices, Electronic Journal of Combinatorics 28(3) (2021), P3.54, states the following as Conjecture 6.16, equation (6.133), on printed page 65:

For every integer n>1n>1,

mn,1(r,s,1,1)=∑π∈ℳ2(n−1)rcr(π)sne(π).m_{n,1}(r,s,1,1) =\sum_{\pi\in\mathcal M_{2(n-1)}}r^{\mathop{\mathrm{cr}}(\pi)} s^{\mathop{\mathrm{ne}}(\pi)}.

Here ℳ2d\mathcal M_{2d} denotes the perfect matchings of {1,…,2d}\{1,\ldots,2d\}. Two arcs (a,b)(a,b), (c,d)(c,d), with a<ca<c, cross when a<c<b<da<c<b<d, nest when a<c<d<ba<c<d<b, and align when a<b<c<da<b<c<d.

The theorem below proves this identity for all nn, with both rr and ss indeterminate. It also identifies the parameter μ\mu with aligned arc pairs. The classical matching/Dyck-path correspondence and its continued fraction are not new results. The assertion being proved is their identification with Gilmore's product-defined matrix.

The exact matrix

Write

[h]r,s=∑j=0h−1rh−1−jsj(h≥1).[h]_{r,s}=\sum_{j=0}^{h-1}r^{h-1-j}s^j\quad(h\ge1).

All matrix indices start at zero. Let Ti=Ti(r,s,μ,y)T_i=T_i(r,s,\mu,y) be the unit-lower-triangular matrix

(Ti)a,b=(μiy)a−b∏v=b+1a[v]r,s(a≥b),(T_i)_{a,b}= (\mu^i y)^{a-b}\prod_{v=b+1}^{a}[v]_{r,s}\quad(a\ge b),

and zero if a<ba<b. Empty products are one.

Equivalently TiT_i is the inverse of the unit-lower-bidiagonal matrix with subdiagonal entries −μiy[h]r,s-\mu^i y[h]_{r,s}. This is Gilmore's T(ai)T(a_i) with ai=(μiy[h+1]r,s)h≥0a_i=(\mu^iy[h+1]_{r,s})_{h\ge0}.

Set Bi=Ii+1⊕TiB_i=I_{i+1}\oplus T_i, and define

M=⋯B2B1B0=(mn,k)n,k≥0.M=\cdots B_2B_1B_0=(m_{n,k})_{n,k\ge0}.

This is precisely the factorization in the published equation (6.108), or arXiv equation (6.105). For every fixed finite leading block, all sufficiently high-index factors are identity on that block, so the product is well-defined algebraically. In particular, m0,0=1m_{0,0}=1, mn,0=0m_{n,0}=0 for n>0n>0, and mn,k=0m_{n,k}=0 if k>nk>n.

The formula for TiT_i follows by multiplying its subdiagonal weights. In particular its power of yy is a−ba-b, consistent with Gilmore's displayed example matrix (6.110). This avoids relying on the isolated, apparently missing exponent in the printed equation (6.109).

A recurrence from the product

Each mn,km_{n,k} is homogeneous of degree n−kn-k in yy: every product term telescopes its row-to-column decreases.

Removing the rightmost factor and shifting indices down by one gives the identity

M(r,s,μ,y)=(1⊕M(r,s,μ,μy))(1⊕T0(r,s,μ,y)).M(r,s,\mu,y) =\bigl(1\oplus M(r,s,\mu,\mu y)\bigr) \bigl(1\oplus T_0(r,s,\mu,y)\bigr).

Indeed the factor with index i≥1i\ge1, after deleting the first row and column, is the factor with index i−1i-1 and yy replaced by μy\mu y.

Consequently, for 1≤k≤n1\le k\le n,

mn,k(r,s,μ,y)=∑j=knμn−jmn−1,j−1(r,s,μ,y)yj−k∏v=kj−1[v]r,s.m_{n,k}(r,s,\mu,y) =\sum_{j=k}^{n} \mu^{n-j}m_{n-1,j-1}(r,s,\mu,y) y^{j-k}\prod_{v=k}^{j-1}[v]_{r,s}. \tag{1}

Separating the term j=kj=k from this sum proves

mn,k=y[k]r,smn,k+1+μn−kmn−1,k−1.\boxed{ m_{n,k}=y[k]_{r,s}m_{n,k+1} +\mu^{n-k}m_{n-1,k-1}.} \tag{2}

No division or nonvanishing parameter assumption is used. The boundary values and (2) determine every row uniquely by descending induction on kk.

Weighted paths

For n≥1n\ge1 and 1≤k≤n1\le k\le n, consider paths with unit up-steps and down-steps that:

  • start at height zero and never go below zero;
  • have exactly n−1n-1 up-steps and n−kn-k down-steps;
  • therefore have length 2n−k−12n-k-1 and finish at height k−1k-1.

Give a down-step from height hh weight y[h]r,sy[h]_{r,s}. Give an up-step weight μd\mu^d, where dd is the number of down-steps preceding it. Let Pn,kP_{n,k} be the sum of these path weights.

The empty path gives P1,1=1P_{1,1}=1. The all-up path gives Pn,n=1P_{n,n}=1. A path ending with a down-step has a predecessor counted by Pn,k+1P_{n,k+1}, and its final step has weight y[k]r,sy[k]_{r,s}. A path ending with an up-step has a predecessor counted by Pn−1,k−1P_{n-1,k-1}. This predecessor has n−kn-k down-steps, so its final up-step has weight μn−k\mu^{n-k}. The second possibility is absent at k=1k=1.

Thus the Pn,kP_{n,k} satisfy (2) with the same boundary values, and

mn,k=Pn,k(n≥1,1≤k≤n).m_{n,k}=P_{n,k} \quad(n\ge1,\ 1\le k\le n). \tag{3}

This is an all-entry path interpretation of Gilmore's matrix. The exponent of μ\mu is the number of ordered pairs of steps in which a down-step occurs before an up-step.

Perfect matchings and the proof

For k=1k=1, the paths in (3) are Dyck excursions with n−1n-1 up-steps and n−1n-1 down-steps.

Read a perfect matching from left to right. An arc's left endpoint is an up-step; its right endpoint is a down-step. At a right endpoint with current height hh, there are exactly hh open arcs. Order their left endpoints increasingly and suppose the arc being closed has position jj.

Of the other open arcs:

  • the j−1j-1 arcs opened earlier will close later, and nest around the closing arc;
  • the h−jh-j arcs opened later will close later, and cross the closing arc.

This right endpoint therefore contributes

rh−jsj−1r^{h-j}s^{j-1}

to the crossing–nesting weight. Each crossing or nesting is counted exactly once, at the first right endpoint of its two arcs. Summing over the hh choices gives

∑j=1hrh−jsj−1=[h]r,s.\sum_{j=1}^{h}r^{h-j}s^{j-1}=[h]_{r,s}.

A Dyck path together with these closing choices uniquely specifies a matching, and every matching has exactly one such encoding.

Moreover, each down-step occurring before a later up-step records exactly one aligned pair: the earlier arc has closed before the later arc opens. Thus the path's exponent of μ\mu equals the number al(π)\mathop{\mathrm{al}}(\pi) of aligned arc pairs. There is one factor yy per down-step.

We conclude, as an identity in ℤ[r,s,μ,y]\mathbb Z[r,s,\mu,y], that

mn,1(r,s,μ,y)=yn−1∑π∈ℳ2(n−1)rcr(π)sne(π)μal(π).\boxed{ m_{n,1}(r,s,\mu,y) =y^{n-1}\sum_{\pi\in\mathcal M_{2(n-1)}} r^{\mathop{\mathrm{cr}}(\pi)} s^{\mathop{\mathrm{ne}}(\pi)} \mu^{\mathop{\mathrm{al}}(\pi)}.} \tag{4}

This holds also for n=1n=1, using the empty matching. Setting μ=y=1\mu=y=1 proves Gilmore's crossing–nesting conjecture in full.

Checks and limits

Run python3 results/gilmore-crossing-nesting/verify.py from the repository root. The companion verifier compares three independently implemented objects: the defining matrix product, the recurrence, and literal enumeration of perfect matchings with crossing/nesting/alignment statistics. All 64 entries of the leading 8-by-8 matrix agree exactly, and the first-column identities agree through matchings on 12 vertices (10,395 matchings at the last size), with all four variables formal. These are finite consistency checks; the argument above proves the unrestricted identity.

A second research agent independently derived the block self-similarity, recurrence, path coordinates, closing-choice weights, and alignment statistic. No gap was found in that internal audit.

The neighboring shifted reverse Bessel Hankel-total-positivity conjecture is different. It concerns all finite minors formed from the entire row-polynomial sequence after a column twist and parameter shifts. Equation (4) does not settle it.