Bernardi–Morales's delta-process conjecture

What Lean checks

Lean proves published Conjectures 27–28 for all admissible parameters: the literal delta-map tree count for every fixed color map, and the complete marked interval-event count and source probability determinant for every fixed surjection. Full subsets, singleton complements and the singular averaging case are included. The 13-module closure passed strict compilation with warnings treated as errors, an all-owned audit of 269 declarations (205 theorem declarations and 23 required endpoints), and independent replay by the pinned stock kernel. Only propext, Classical.choice, and Quot.sound are permitted. Receipt. Combined package gate and hosted validation remain separate.

Lean status: the complete statement in this note now has strict source, all-owned axiom, and pinned stock-kernel verification. See the formalization section for the exact definitions, endpoints and receipt. The combined package gate remains separate.

Statement and source

Bernardi and Morales state the conjecture as Conjecture 27 in Some probabilistic trees with algebraic roots, Electronic Journal of Combinatorics 23(2) (2016), P2.36, page 23, DOI 10.37236/4954. It is Conjecture 21 in arXiv:1501.01135v1.

Fix integers k≥2k\geq2 and r≥1r\geq1. Write [k]={1,…,k}[k]=\{1,\ldots,k\}, with its cyclic order. For a proper subset S⊊[k]S\subsetneq[k], define δ(i,S)=i\delta(i,S)=i when i∈Si\in S. When i∉Si\notin S, define δ(i,S)\delta(i,S) to be the next element of [k]\S[k]\setminus S after ii in cyclic order. A singleton complement therefore gives a fixed point.

For 𝐩=(p1,…,pk)∈ℤ≥0k\boldsymbol p=(p_1,\ldots,p_k)\in\mathbb Z_{\geq0}^k, let

ℛ𝐩,r={(S1,…,Sr):Sℓ⊊[k],∑ℓ=1r𝟏{j∈Sℓ}=pj for every j∈[k]}.\mathcal R_{\boldsymbol p,r} =\left\{(S_1,\ldots,S_r): S_\ell\subsetneq[k],\quad \sum_{\ell=1}^r\boldsymbol1_{\{j\in S_\ell\}}=p_j \text{ for every }j\in[k]\right\}.

The set ℛ𝐩,0\mathcal R_{\boldsymbol p,0} consists of the empty tuple if 𝐩=𝟎\boldsymbol p=\boldsymbol0, and is empty otherwise. Given a map f:[k−1]→[r]f:[k-1]\to[r], let Gδ(𝐒,f)G_\delta(\boldsymbol S,f) have arcs

i→δ(i,Sf(i)),i∈[k−1].i\longrightarrow\delta(i,S_{f(i)}),\qquad i\in[k-1].

Every nonroot vertex has one outgoing arc, while kk has none. Thus this graph is a tree exactly when every forward orbit reaches kk.

Theorem. For every fixed map f:[k−1]→[r]f:[k-1]\to[r],

#{𝐒∈ℛ𝐩,r:Gδ(𝐒,f) is a tree}=|ℛ𝐩,r−1|.\#\{\boldsymbol S\in\mathcal R_{\boldsymbol p,r}: G_\delta(\boldsymbol S,f)\text{ is a tree}\} =|\mathcal R_{\boldsymbol p,r-1}|. \tag{1}

In particular, if 1≤r<k1\leq r\lt k, ℛ𝐩,r\mathcal R_{\boldsymbol p,r} is nonempty, 𝐒\boldsymbol S is uniform in that set, and ff is an independent uniform surjection, then

Pδ(𝐩,r)=|ℛ𝐩,r−1||ℛ𝐩,r|.P_\delta(\boldsymbol p,r) =\frac{|\mathcal R_{\boldsymbol p,r-1}|} {|\mathcal R_{\boldsymbol p,r}|}. \tag{2}

Equation (2) is the full published tree-probability conjecture. The fixed-map assertion (1) is stronger: neither surjectivity nor the inequality r<kr\lt k is needed. The companion EVENT_PROOF.md proves the separate, stronger event-determinant Conjecture 28. This file gives the tree identity its own proof.

1. The cyclic Laplacian and elimination

All matrices have rows and columns indexed by [k][k] unless specified otherwise. For row and column sets I,JI,J, use M[I,J]M[I,J] with indices in increasing order. Empty determinants equal 1.

Let QQ be the matrix with Qi,i+1=1Q_{i,i+1}=1, with subscripts taken cyclically modulo kk, and all other entries zero. Set

L=I−Q.L=I-Q.

For a nonempty set C⊆[k]C\subseteq[k], let LCL_C be the Laplacian of the cyclic successor on CC, extended by zero rows and columns on [k]\C[k]\setminus C. Explicitly, its row at i∈Ci\in C is eiT−enextC(i)Te_i^T-e_{\mathop{\mathrm{next}}_C(i)}^T. If CC is a singleton, this is the zero matrix. In particular, the row of L[k]\SL_{[k]\setminus S} at ii is eiT−eδ(i,S)Te_i^T-e_{\delta(i,S)}^T.

Lemma 1. If S⊊[k]S\subsetneq[k] and C=[k]\SC=[k]\setminus S, then

detL[S,S]=1,\det L[S,S]=1,

and the Schur complement of L[S,S]L[S,S] in LL, on the remaining set CC, is

L[C,C]−L[C,S]L[S,S]−1L[S,C]=LC[C,C].L[C,C]-L[C,S]L[S,S]^{-1}L[S,C]=L_C[C,C]. \tag{3}

Proof. The successor graph restricted to a proper subset SS is a union of directed paths. Consequently Q[S,S]Q[S,S] is nilpotent. Ordering each path along its direction makes I−Q[S,S]I-Q[S,S] triangular with diagonal 1, proving the determinant assertion.

The inverse of I−Q[S,S]I-Q[S,S] is the finite sum of powers of Q[S,S]Q[S,S]. In the product L[C,S]L[S,S]−1L[S,C]L[C,S]L[S,S]^{-1}L[S,C], a contribution from i∈Ci\in C to j∈Cj\in C records the unique successor path from ii to jj whose internal vertices lie in SS. The product has coefficient +1+1 when this path has at least one internal vertex. An arc with no internal vertex is already recorded with coefficient −1-1 in L[C,C]L[C,C]. Subtracting the product therefore gives ICI_C minus the cyclic-successor matrix on CC. When CC is a singleton, the returning path cancels its diagonal entry. This proves (3). The same statement for S=⌀S=\varnothing uses empty-block conventions. ∎

2. A determinant generating identity

Introduce commuting indeterminates x1,…,xkx_1,\ldots,x_k. Put

X=diag(x1,…,xk),xS=∏i∈Sxi,X=\mathop{\mathrm{diag}}(x_1,\ldots,x_k),\qquad x^S=\prod_{i\in S}x_i,

and

F(x)=∑S⊊[k]xS=∏i=1k(1+xi)−∏i=1kxi.F(x)=\sum_{S\subsetneq[k]}x^S =\prod_{i=1}^k(1+x_i)-\prod_{i=1}^kx_i. \tag{4}

Lemma 2. For an arbitrary k×kk\times k matrix ZZ,

det(I+(X+Z)L)=∑S⊊[k]xSdet(I+ZL[k]\S).\det\bigl(I+(X+Z)L\bigr) =\sum_{S\subsetneq[k]}x^S \det\bigl(I+ZL_{[k]\setminus S}\bigr). \tag{5}

Proof. Expand the left side by multilinearity in its rows. The coefficient of xSx^S is the determinant formed by taking row ii of LL when i∈Si\in S, and row ii of I+ZLI+ZL when i∉Si\notin S.

When S=[k]S=[k], that determinant is detL=0\det L=0. Otherwise put C=[k]\SC=[k]\setminus S and place the indices of SS first by applying the same permutation to rows and columns. This does not change the determinant. From each row i∈Ci\in C, subtract the linear combination ∑j∈SZijL[j,[k]]\sum_{j\in S}Z_{ij}L[j,[k]] of the selected rows. The resulting block matrix is

(L[S,S]L[S,C]Z[C,C]L[C,S]IC+Z[C,C]L[C,C]).\begin{pmatrix} L[S,S]&L[S,C]\\ Z[C,C]L[C,S]&I_C+Z[C,C]L[C,C] \end{pmatrix}.

By Lemma 1 and the block determinant formula, its determinant is

detL[S,S]det(IC+Z[C,C](L[C,C]−L[C,S]L[S,S]−1L[S,C]))=det(IC+Z[C,C]LC[C,C]).\det L[S,S]\, \det\left(I_C+Z[C,C] \bigl(L[C,C]-L[C,S]L[S,S]^{-1}L[S,C]\bigr)\right) =\det\bigl(I_C+Z[C,C]L_C[C,C]\bigr).

Because LCL_C has zero rows and columns outside CC, this is det(I+ZLC)\det(I+ZL_C). The coefficient of every xSx^S agrees with the right side of (5). ∎

Taking Z=0Z=0 in (5) gives

A:=I+XL,detA=F.A:=I+XL,\qquad \det A=F. \tag{6}

Work for the moment over the rational-function field ℚ(x1,…,xk)\mathbb Q(x_1,\ldots,x_k), where F≠0F\ne0 and AA is invertible. Set

H=LA−1.H=LA^{-1}. \tag{7}

Factoring A+ZL=(I+ZLA−1)AA+ZL=(I+ZLA^{-1})A in (5) yields

1F∑S⊊[k]xSdet(I+ZL[k]\S)=det(I+ZH).\frac1F\sum_{S\subsetneq[k]}x^S \det(I+ZL_{[k]\setminus S}) =\det(I+ZH). \tag{8}

3. All minors, and the replacement of a block of rows

For any function gg of a proper subset define the normalized formal average

𝔼xg(S)=1F∑S⊊[k]xSg(S).\mathbb E_x g(S)=\frac1F\sum_{S\subsetneq[k]}x^Sg(S).

This notation is a linear functional on a finite sum. No analytic probability assumption on the indeterminates is needed.

Lemma 3. For all equally sized row and column sets I,J⊆[k]I,J\subseteq[k],

𝔼xdet(L[k]\S[I,J])=detH[I,J].\mathbb E_x\det\bigl(L_{[k]\setminus S}[I,J]\bigr) =\det H[I,J]. \tag{9}

Proof. In (8), let all entries of ZZ be independent indeterminates. The principal-minor expansion followed by Cauchy–Binet gives, for any matrix MM,

det(I+ZM)=∑a=0k∑I,J⊆[k]|I|=|J|=adetZ[I,J]detM[J,I].\det(I+ZM) =\sum_{a=0}^k\ \sum_{\substack{I,J\subseteq[k]\\|I|=|J|=a}} \det Z[I,J]\det M[J,I]. \tag{10}

The polynomials detZ[I,J]\det Z[I,J] appearing here are linearly independent: their monomials have distinct sets of row indices and column indices for distinct pairs (I,J)(I,J). Equating their coefficients in (8) proves (9), after exchanging the names I,JI,J. In particular, the size-one assertion gives 𝔼xL[k]\S=H\mathbb E_x L_{[k]\setminus S}=H. ∎

The all-minor property in (9) is commonly called the determinant-preserving property. Its general closure rules are known; see Dereziński, Liang and Mahoney, arXiv:1912.04533v3, Definition 4 and Lemma 4. Here (5) proves that property for the cyclic matrices required by this conjecture. The following short argument supplies the precise closure step needed, without taking it as an external assumption.

Lemma 4. Suppose a square determinant has a specified set of rows taken from L[k]\SL_{[k]\setminus S}, with a fixed common set of columns. Its other rows are independent of SS. Applying 𝔼x\mathbb E_x to that determinant has the same effect as replacing the specified rows by the corresponding rows of HH.

Proof. Expand the determinant along the specified rows. Each term is a signed product of a square minor of L[k]\SL_{[k]\setminus S} and a complementary minor using the other rows. The latter factor is independent of SS. Apply (9) to the former factor and sum the Laplace expansion again. ∎

It follows that independently averaged matrices can be replaced one color at a time, even when the different colors occupy several interspersed rows. Entrywise expectations alone would not justify this step; (9) for all row and column sets does.

4. The cofactor of the mean matrix

Let 𝟏\boldsymbol1 be the all-ones column vector. The cycle Laplacian satisfies

L𝟏=0,𝟏TL=0,adjL=𝟏𝟏T.L\boldsymbol1=0,\qquad \boldsymbol1^T L=0,\qquad \mathop{\mathrm{adj}}L=\boldsymbol1\boldsymbol1^T. \tag{11}

Indeed, Lemma 1 gives a principal cofactor equal to 1, so LL has rank k−1k-1. Its left and right nullspaces are spanned by 𝟏T\boldsymbol1^T and 𝟏\boldsymbol1. Hence the adjugate is a scalar multiple of 𝟏𝟏T\boldsymbol1\boldsymbol1^T, and the principal cofactor fixes that scalar at 1.

Since A𝟏=𝟏A\boldsymbol1=\boldsymbol1, the adjugate multiplication identity and (6)–(7) give

adjH=adj(A−1)adjL=AF𝟏𝟏T=1F𝟏𝟏T.\mathop{\mathrm{adj}}H =\mathop{\mathrm{adj}}(A^{-1})\mathop{\mathrm{adj}}L =\frac{A}{F}\boldsymbol1\boldsymbol1^T =\frac1F\boldsymbol1\boldsymbol1^T. \tag{12}

Writing R=[k−1]R=[k-1], we therefore have

detH[R,R]=1F.\det H[R,R]=\frac1F. \tag{13}

5. A fixed map and the tree indicator

Fix f:[k−1]→[r]f:[k-1]\to[r]. For a tuple of proper subsets 𝐒=(S1,…,Sr)\boldsymbol S=(S_1,\ldots,S_r), form the (k−1)×(k−1)(k-1)\times(k-1) matrix Bf(𝐒)B_f(\boldsymbol S) whose row at i∈Ri\in R is row ii of L[k]\Sf(i)L_{[k]\setminus S_{f(i)}}, restricted to the columns in RR. Thus its row is eiT−eδ(i,Sf(i))Te_i^T-e_{\delta(i,S_{f(i)})}^T, after deleting the root column.

We have the elementary indicator identity

detBf(𝐒)=𝟏{Gδ(𝐒,f) is a tree}.\det B_f(\boldsymbol S) =\boldsymbol1_{\{G_\delta(\boldsymbol S,f)\text{ is a tree}\}}. \tag{14}

To see this directly, if the graph contains a directed cycle, the rows indexed by that cycle sum to zero. A loop supplies a zero row. Either way the determinant is zero. If there is no directed cycle, every vertex reaches kk. Order the nonroot vertices by their distance from kk, and apply the same order to rows and columns. The matrix becomes triangular with diagonal 1, so its determinant is 1. This also proves (14) without invoking the matrix-tree theorem.

Apply the formal product average 𝔼x⊗r\mathbb E_x^{\otimes r}, giving each SℓS_\ell its own independent sum with weight xSℓ/Fx^{S_\ell}/F. The word independent refers to this product of finite sums; the sets will be conditioned on the membership counts only at the end.

For each color ℓ\ell, use Lemma 4 on the row set f−1(ℓ)f^{-1}(\ell). Replace the rows belonging to that color by the corresponding rows of HH. Other colors are fixed during this step. A color with no assigned rows simply contributes the average of 1. After all rr replacements, the matrix is H[R,R]H[R,R]. Equations (13)–(14) give

1Fr∑S1,…,Sr⊊[k]xS1⋯xSr𝟏{Gδ(𝐒,f) is a tree}=1F.\frac1{F^r}\sum_{S_1,\ldots,S_r\subsetneq[k]} x^{S_1}\cdots x^{S_r} \boldsymbol1_{\{G_\delta(\boldsymbol S,f)\text{ is a tree}\}} =\frac1F.

Clearing denominators proves the polynomial identity

∑S1,…,Sr⊊[k]xS1⋯xSr𝟏{Gδ(𝐒,f) is a tree}=F(x)r−1.\boxed{ \sum_{S_1,\ldots,S_r\subsetneq[k]} x^{S_1}\cdots x^{S_r} \boldsymbol1_{\{G_\delta(\boldsymbol S,f)\text{ is a tree}\}} =F(x)^{r-1}.} \tag{15}

The coefficient of x1p1⋯xkpkx_1^{p_1}\cdots x_k^{p_k} on the left counts the trees in (1). By (4), its coefficient on the right is |ℛ𝐩,r−1||\mathcal R_{\boldsymbol p,r-1}|. This proves (1).

When r<kr\lt k, averaging (1) over surjections gives (2). Finally, the map that deletes an empty first set is a bijection from the tuples in ℛ𝐩,r\mathcal R_{\boldsymbol p,r} with S1=⌀S_1=\varnothing to ℛ𝐩,r−1\mathcal R_{\boldsymbol p,r-1}. Thus the ratio in (2) also has the interpretation stated in the source. ∎

6. Color-weight refinement

Summing (15) over all maps ff, with weight ∏i=1k−1tf(i)\prod_{i=1}^{k-1}t_{f(i)}, gives

∑S1,…,Sr⊊[k]xS1⋯xSrdet[(∑ℓ=1rtℓL[k]\Sℓ)[R,R]]=F(x)r−1(t1+⋯+tr)k−1.\sum_{S_1,\ldots,S_r\subsetneq[k]} x^{S_1}\cdots x^{S_r} \det\left[\left(\sum_{\ell=1}^r t_\ell L_{[k]\setminus S_\ell}\right)[R,R]\right] =F(x)^{r-1}(t_1+\cdots+t_r)^{k-1}. \tag{16}

The determinant notation on the left means the determinant of the submatrix indexed by R,RR,R after taking the indicated sum. Its row-multilinear expansion is the sum over maps used above. In particular, prescribing color fiber sizes n1+⋯+nr=k−1n_1+\cdots+n_r=k-1 gives the exact tree count

(k−1n1,…,nr)|ℛ𝐩,r−1|.\binom{k-1}{n_1,\ldots,n_r}\,|\mathcal R_{\boldsymbol p,r-1}|.

Positive fiber sizes recover surjections. Formula (16) and the fixed-map theorem are refinements of the same conjecture, not separate conjectures counted as additional results.

Audit and verification

The parent research agent independently checked the source definition, Lemmas 1–3, the independent-color replacement, the adjugate evaluation, and coefficient extraction. The parent also proposed the fixed-map refinement, proved here by Lemma 4. The companion verify.py independently checks 71 fixed maps and 111,721 literal process pairs, along with 25 arbitrary-matrix instances of (5). Those finite calculations are checks of implementation and conventions; the proof above has no upper bound on kk, rr, or the membership counts.