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.

Status: full proofs with separate internal reviews. No previous resolution was found in the documented literature search of 20 November 2026. External peer review has not been obtained.

The targets are Conjectures 27 and 28, page 23, in Olivier Bernardi and Alejandro H. Morales, Some probabilistic trees with algebraic roots, Electronic Journal of Combinatorics 23(2) (2016), P2.36, DOI 10.37236/4954. The original arXiv preprint numbers them Conjectures 21 and 22. Both are included under this one named conjecture investigation.

Result

Let ℛ𝐩,r\mathcal R_{\boldsymbol p,r} consist of rr proper subsets of [k][k] such that vertex jj occurs in exactly pjp_j subsets. For each nonroot vertex ii, a map f:[k−1]→[r]f:[k-1]\to[r] chooses one of the subsets. The delta rule fixes ii if ii belongs to that subset, and otherwise sends ii to the next element of its complement in cyclic order. These choices define a directed graph with root kk.

For every fixed map ff, the number of tuples producing a tree is exactly

#{𝐒∈ℛ𝐩,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}|.

Consequently the original experiment, with a uniform tuple and an independent uniform surjection, has tree probability

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

The proof covers all admissible k,r,𝐩k,r,\boldsymbol p. The stronger fixed-map statement allows nonsurjective maps and arbitrary r≥1r\geq1.

The source's stronger event-determinant Conjecture 28 is also proved. For every fixed surjection ff and every marked set D⊆[k−1]D\subseteq[k-1], its event matrix satisfies the complete polynomial identity

∑S1,…,Sr⊆[k]xS1⋯xSrdetMD(𝐒,f)=F(x)r−1xD∏j∈[k−1]\D(1+xj),F(x)=∏i=1k(1+xi)−∏i=1kxi.\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), \qquad F(x)=\prod_{i=1}^k(1+x_i)-\prod_{i=1}^kx_i.

Here MDM^D uses the paper's interval-event rows, with a fixed last row of ones. EVENT_PROOF.md gives their precise definitions. Membership coefficient extraction yields exactly the source's conjectured probability determinant for every DD. The original paper had already proved the two endpoint cases D=⌀D=\varnothing and D=[k−1]D=[k-1]; this proof covers all marked sets at once.

Proof mechanism

Write LL for the directed-cycle Laplacian. Eliminating a proper subset SS by a Schur complement gives the cyclic-successor Laplacian on its complement, exactly the delta map. All proper principal minors of LL equal 1. This gives an identity with an arbitrary auxiliary matrix, rather than just a diagonal one, and therefore preserves the averages of all square minors.

The subsets become independent after introducing membership variables and postponing coefficient extraction. The all-minor identity permits replacement of each color's rows inside the determinant by a common matrix H=L(I+XL)−1H=L(I+XL)^{-1}. Every principal cofactor of HH equals 1/F1/F, where

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

The determinant is the indicator that the functional graph reaches the root. Thus the weighted tree count is Fr−1F^{r-1}, and its membership coefficients give the result.

The separate event proof represents interval indicators by the adjugate of a cyclic matrix. Multiplying selected rows by that matrix reduces the determinant to complementary columns. At the full subset, both sides vanish because of the fixed last row of ones. This exact cancellation permits independent Bernoulli averaging even at the singular case. Replacing one color at a time and evaluating the final determinant proves the stronger identity.

Lean formalization

The complete published Conjectures 27–28 are formalized. The root endpoints are BernardiMorales.bernardi_morales_delta and BernardiMorales.bernardi_morales_event in BernardiMorales.lean. The parameters n and r encode every k=n+2 ≥ 2 and every positive number r+1 of subsets. Membership counts range over arbitrary nonnegative integer vectors. The tree identity permits every fixed color map, including nonsurjections; the marked-event identity uses every fixed surjection and every marked set avoiding the root.

The definitions use actual Boolean subset tuples, the source's cyclic intervals with ]i,i] empty, the full-subset diagonal rule, and the literal next-complement delta map. The delta graph is a rooted tree precisely when all nonroot forward orbits reach the root. Its determinant is proved to be the exact zero-one indicator. source_probability_determinant also identifies the source's signed-intersection probability determinant with the normalized target count. The singular full-subset case is proved within the row-replacement argument.

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, complete declaration inventory, and strict source records.

Run the registered full gate from the repository root with scripts/verify_lean.sh. This local result-level checkpoint does not claim that the combined repository gate or hosted validation has passed.

Files and verification

  • PROOF.md: complete argument, including the fixed-map theorem and color-weight identity.
  • EVENT_PROOF.md: full proof of the stronger event-determinant conjecture, including full subsets and all marked sets.
  • NOVELTY.md: source identification, author status pages, later citations, mechanism searches, access limits, and precise novelty claim.
  • verify.py: independent exact enumeration and determinant-identity checks using Python's standard library.
  • verify_events.py: literal interval-event determinants and complete membership coefficient comparisons.

Run python verify.py. The recorded run passed all membership coefficients for 71 fixed maps and 111,721 process pairs, including nonsurjective maps and cases with r≥kr\geq k. It also passed 25 dense arbitrary-matrix checks of the Schur generating identity for k=2,…,6k=2,\ldots,6. These finite checks verify conventions and arithmetic; the mathematical proof is unrestricted.

Run python verify_events.py. The recorded run passed 342 pairs of a fixed surjection and a marked set, involving 438,952 signed integer determinants. The implementation uses the source's interval events directly and does not use the adjugate or Bernoulli formulas. Both verifiers use only Python's standard library.

Coordination and audit: issue #85. The Python verifiers remain independent finite checks; the Lean theorems cover the unrestricted stated parameters.