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.

The stronger event identity

This note proves Conjecture 28 in Bernardi and Morales, Some probabilistic trees with algebraic roots, Electronic Journal of Combinatorics 23(2) (2016), P2.36, page 23. It is Conjecture 22 in arXiv:1501.01135v1. The paper shows that this identity implies its delta-process tree-probability conjecture. The companion PROOF.md gives an independent proof of that probability formula.

The argument below was developed by the parent research agent and independently checked by the analysis agent. The checks included a direct enumeration using the paper's event definitions, without relying on the adjugate representation used in the proof.

1. Exact event formulation

Fix k≥2k\geq2, 1≤r<k1\leq r\lt k, a surjection f:[k−1]→[r]f:[k-1]\to[r], and a set D⊆[k−1]D\subseteq[k-1]. Intervals are cyclic: ]i,j]]i,j] contains the vertices strictly after ii up to and including jj, while ]i,i]=⌀]i,i]=\varnothing.

For any subset S⊆[k]S\subseteq[k], including the full set, define the zero-one matrices

(IS)ij=𝟏{]i,j]⊆S},(JS)ij={(IS)ij,i≠j,𝟏{S=[k]},i=j.(I_S)_{ij}=\boldsymbol1_{\{]i,j]\subseteq S\}}, \qquad (J_S)_{ij}= \begin{cases} (I_S)_{ij},&i\ne j,\\ \boldsymbol1_{\{S=[k]\}},&i=j. \end{cases} \tag{1}

For a tuple 𝐒=(S1,…,Sr)\boldsymbol S=(S_1,\ldots,S_r) of arbitrary subsets, let MD(𝐒,f)M^D(\boldsymbol S,f) be the ordinary numerical matrix obtained from the source's event matrix by taking event indicators:

MijD(𝐒,f)={(JSf(i))i−1,j,i∈D,(ISf(i))ij,i∈[k−1]\D,1,i=k.M^D_{ij}(\boldsymbol S,f)= \begin{cases} (J_{S_{f(i)}})_{i-1,j},& i\in D,\\ (I_{S_{f(i)}})_{ij},& i\in[k-1]\setminus D,\\ 1,&i=k. \end{cases} \tag{2}

The index i−1i-1 is read cyclically, so 00 means kk.

Write xS=∏i∈Sxix^S=\prod_{i\in S}x_i and

G(x)=∏i=1k(1+xi),F(x)=G(x)−∏i=1kxi.G(x)=\prod_{i=1}^k(1+x_i),\qquad F(x)=G(x)-\prod_{i=1}^kx_i.

Theorem. For every fixed surjection ff and every D⊆[k−1]D\subseteq[k-1],

∑S1,…,Sr⊆[k]xS1⋯xSrdetMD(𝐒,f)=F(x)r−1xD∏j∈[k−1]\D(1+xj).\boxed{ \sum_{S_1,\ldots,S_r\subseteq[k]} x^{S_1}\cdots x^{S_r}\det M^D(\boldsymbol S,f) =F(x)^{r-1}x^D \prod_{j\in[k-1]\setminus D}(1+x_j).} \tag{3}

The sums on the left include full subsets. This distinction from the proper-subset model is necessary. The proof treats those subsets explicitly.

2. Cyclic adjugates

Let Qi,i+1=1Q_{i,i+1}=1 with cyclic indices, all other entries zero. For a binary vector s=(s1,…,sk)s=(s_1,\ldots,s_k) representing SS, put

Ws=I−Qdiag(s1,…,sk).W_s=I-Q\mathop{\mathrm{diag}}(s_1,\ldots,s_k).

The determinant and adjugate are

detWs=1−∏i=1ksi,adjWs=∑a=0k−1(Qdiags)a=IS.\det W_s=1-\prod_{i=1}^ks_i, \qquad \mathop{\mathrm{adj}}W_s =\sum_{a=0}^{k-1}\bigl(Q\mathop{\mathrm{diag}}s\bigr)^a =I_S. \tag{4}

The first equality follows by expanding the cyclic matrix determinant: only the identity permutation and the complete cycle contribute. For the second, (Qdiags)k=(∏isi)I(Q\mathop{\mathrm{diag}}s)^k=(\prod_i s_i)I. Multiplication by WsW_s gives the first expression in (4) times the identity. The equality with the adjugate follows first where the determinant is nonzero and then as a polynomial identity. Entry i,ji,j of the displayed sum is the product of the indicators along the unique cyclic path ]i,j]]i,j] of length at most k−1k-1, proving the equality with ISI_S.

When SS is proper, detWs=1\det W_s=1 and IS=Ws−1I_S=W_s^{-1}. When S=[k]S=[k], every entry of ISI_S equals 1. The full-set matrix is not an inverse.

The source's two event matrices also satisfy

(JS)i−1,j=si(IS)ij.(J_S)_{i-1,j}=s_i(I_S)_{ij}. \tag{5}

For j≠i−1j\ne i-1, the interval ]i−1,j]]i-1,j] is {i}∪]i,j]\{i\}\cup]i,j]. For j=i−1j=i-1, the right side requires every vertex to belong to SS, agreeing with the special diagonal definition of JSJ_S.

Thus (2) uses row ii of ISf(i)I_{S_{f(i)}}, multiplied by sis_i when i∈Di\in D, and has a fixed last row of ones.

3. A row-replacement lemma that includes the singular case

Let A⊆[k−1]A\subseteq[k-1] be a nonempty set of selected rows. Fix all other rows in a matrix RR, whose last row is 𝟏T\boldsymbol1^T. Let U=A∩DU=A\cap D.

For a binary vector ss, form TsT_s by taking row ii from ISI_S for i∈Ai\in A and from RR otherwise, then multiplying each selected row i∈Ui\in U by sis_i. Put Ac=[k]\AA^c=[k]\setminus A.

Lemma. Suppose the sis_i are independent Bernoulli variables with parameters qiq_i. Put

Wq=I−Qdiag(q1,…,qk),Δ=detWq=1−∏i=1kqi,W_q=I-Q\mathop{\mathrm{diag}}(q_1,\ldots,q_k),\qquad \Delta=\det W_q=1-\prod_{i=1}^kq_i,

and assume Δ≠0\Delta\ne0. Let T¯\overline T retain the rows of RR outside AA and use row ii of Wq−1W_q^{-1} inside AA, multiplied by qiq_i when i∈Ui\in U. Then

𝔼detTs=ΔdetT¯.\mathbb E\det T_s=\Delta\det\overline T. \tag{6}

Proof. First omit the factors sis_i on the selected rows, and call the resulting matrix Ts0T_s^0. We claim the exact binary identity

detTs0=det((RWs)[Ac,Ac]).\det T_s^0 =\det\bigl((RW_s)[A^c,A^c]\bigr). \tag{7}

If SS is proper, multiply Ts0T_s^0 by WsW_s. The selected rows become the standard rows eiTe_i^T, while the other rows become those of RWsRW_s. Since detWs=1\det W_s=1, expanding along the selected standard rows proves (7). The sign is positive because the same index set is removed from rows and columns.

If S=[k]S=[k], a selected row of Ts0T_s^0 equals 𝟏T\boldsymbol1^T, as does the last row. Hence the left side of (7) is zero. On the right, the last row of RWsRW_s is 𝟏T(I−Q)=0\boldsymbol1^T(I-Q)=0, and that row is retained because k∉Ak\notin A. The right side is also zero. Thus (7) holds even at the singular full-set matrix.

Restore the marked row factors. Equation (7) gives

detTs=(∏i∈Usi)det((RWs)[Ac,Ac]).\det T_s =\left(\prod_{i\in U}s_i\right) \det\bigl((RW_s)[A^c,A^c]\bigr). \tag{8}

Column jj of RWsRW_s is column jj of RR minus sjs_j times column j−1j-1 of RR. The determinant on the right of (8) therefore depends only on the variables sjs_j with j∈Acj\in A^c, and is affine in each of them. These variables are disjoint from those in the prefactor. Independence and multilinearity in the columns yield

𝔼detTs=(∏i∈Uqi)det((RWq)[Ac,Ac]).\mathbb E\det T_s =\left(\prod_{i\in U}q_i\right) \det\bigl((RW_q)[A^c,A^c]\bigr). \tag{9}

Finally, multiply the unmarked version of T¯\overline T by WqW_q and expand along its selected standard rows. Now the multiplication contributes detWq=Δ\det W_q=\Delta. Restoring the factors qiq_i shows that the right side of (9) is ΔdetT¯\Delta\det\overline T. This proves (6). ∎

The nonempty condition on AA is used when S=[k]S=[k]. It is supplied by surjectivity in the next step. The proof never assumes that ISI_S itself is an inverse or determinant preserving at a full subset.

4. Replace the colors and evaluate the determinant

For each color ℓ∈[r]\ell\in[r], sample a vector s(ℓ)s^{(\ell)} with independent Bernoulli coordinates of parameters q1,…,qkq_1,\ldots,q_k. All colors are independent.

Apply the lemma to the nonempty row set A=f−1(ℓ)A=f^{-1}(\ell). Condition on the other colors while doing so. The last row remains 𝟏T\boldsymbol1^T throughout. Each replacement contributes a factor Δ\Delta. After all rr replacements, the first k−1k-1 rows are the corresponding rows of

K=diag(v1,…,vk)Wq−1,vi={qi,i∈D,1,i∉D,K=\mathop{\mathrm{diag}}(v_1,\ldots,v_k)W_q^{-1}, \qquad v_i= \begin{cases} q_i,&i\in D,\\ 1,&i\notin D, \end{cases}

and the last row is 𝟏T\boldsymbol1^T. Call this final matrix MqM_q. Thus

𝔼detMD(𝐒,f)=ΔrdetMq.\mathbb E\det M^D(\boldsymbol S,f)=\Delta^r\det M_q. \tag{10}

Multiplication of MqM_q by WqW_q turns row i∈[k−1]i\in[k-1] into vieiTv_ie_i^T. Its last row becomes

𝟏TWq=(1−q1,…,1−qk).\boldsymbol1^TW_q=(1-q_1,\ldots,1-q_k).

Expansion along the first k−1k-1 diagonal rows gives

ΔdetMq=(1−qk)∏i∈Dqi.\Delta\det M_q =(1-q_k)\prod_{i\in D}q_i.

Combining this with (10) proves

𝔼detMD(𝐒,f)=Δr−1(1−qk)∏i∈Dqi.\mathbb E\det M^D(\boldsymbol S,f) =\Delta^{r-1}(1-q_k)\prod_{i\in D}q_i. \tag{11}

5. Membership coefficients and the conjecture

Set qi=xi/(1+xi)q_i=x_i/(1+x_i). One can first take all xi>0x_i>0, so every probability and inverse used above is defined. The probability weight of a subset is then xS/G(x)x^S/G(x), and

Δ=F(x)G(x).\Delta=\frac{F(x)}{G(x)}.

Multiplying (11) by G(x)rG(x)^r gives

G(x)rΔr−1(1−qk)∏i∈Dqi=F(x)r−1xD∏j∈[k−1]\D(1+xj).G(x)^r\Delta^{r-1}(1-q_k)\prod_{i\in D}q_i =F(x)^{r-1}x^D\prod_{j\in[k-1]\setminus D}(1+x_j).

This proves (3) for positive xix_i. Both sides of (3) are polynomials, so it proves the polynomial identity without restrictions on the indeterminates.

For the original membership vector 𝐩\boldsymbol p, define 𝒮𝐩,r\mathcal S_{\boldsymbol p,r} as the set of tuples of arbitrary subsets with those counts. Define ℛ𝐩,r\mathcal R_{\boldsymbol p,r} by requiring every subset to be proper, as in PROOF.md. The coefficient of x𝐩x^{\boldsymbol p} on the right of (3) is

ND=#{𝐒∈ℛ𝐩,r:k∉S1,D⊆S1}.N_D=\#\{\boldsymbol S\in\mathcal R_{\boldsymbol p,r}: k\notin S_1,\ D\subseteq S_1\}. \tag{12}

Indeed, the factor xD∏j∈[k−1]\D(1+xj)x^D\prod_{j\in[k-1]\setminus D}(1+x_j) enumerates the choices for the distinguished first subset, while Fr−1F^{r-1} enumerates the other proper subsets.

The probability determinant in the source is the expectation of the determinant of the numerical event-indicator matrix. This follows directly from its Leibniz expansion: each product of indicators is the indicator of the corresponding intersection of events. Taking coefficients in (3), dividing by |𝒮𝐩,r||\mathcal S_{\boldsymbol p,r}|, and averaging over the surjections therefore gives

ℙdet(MD)=ND|𝒮𝐩,r|=|ℛ𝐩,r||𝒮𝐩,r|ℙ(k∉S1,D⊆S1∣𝐒∈ℛ𝐩,r).\mathbb P\det(M^D) =\frac{N_D}{|\mathcal S_{\boldsymbol p,r}|} =\frac{|\mathcal R_{\boldsymbol p,r}|}{|\mathcal S_{\boldsymbol p,r}|} \mathbb P\bigl(k\notin S_1,\ D\subseteq S_1 \mid\boldsymbol S\in\mathcal R_{\boldsymbol p,r}\bigr). \tag{13}

This is the full published Conjecture 28. It holds before averaging over surjections, for each fixed surjection separately. The conditional-probability notation in (13) assumes ℛ𝐩,r≠⌀\mathcal R_{\boldsymbol p,r}\ne\varnothing, as in the source setting; the polynomial identity (3) and the count (12) require no such restriction. ∎

Relation to the tree identity

The source obtains its delta event matrix by summing the matrices in (2) over DD, with sign (−1)|D|(-1)^{|D|} in the determinant expansion. Summing the right side of (3) with those signs gives

F(x)r−1∑D⊆[k−1](−1)|D|xD∏j∈[k−1]\D(1+xj)=F(x)r−1∏j=1k−1((1+xj)−xj)=F(x)r−1.F(x)^{r-1} \sum_{D\subseteq[k-1]}(-1)^{|D|}x^D \prod_{j\in[k-1]\setminus D}(1+x_j) =F(x)^{r-1}\prod_{j=1}^{k-1}\bigl((1+x_j)-x_j\bigr) =F(x)^{r-1}.

This recovers the tree-count polynomial for surjections, consistent with the independent Schur-complement proof. Both results belong to the same named conjecture investigation; the stronger identity and its specializations are not counted as extra named conjectures.

Exact check

Run python verify_events.py from this directory. The verifier implements (1)–(2) literally and computes signed integer determinants. It compares every membership coefficient with (12) for 342 pairs (f,D)(f,D) and 438,952 subset-tuple determinants: all r<kr\lt k through k=4k=4, and (k,r)=(5,2)(k,r)=(5,2). All comparisons passed. No adjugate or Bernoulli identity is used by that verifier, and no part of the proof relies on the finite range checked.