Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Conditional partner counts for single-cycle weld completions

Proved
WeldedPath.single_cycle_completion_count

by dmilosch · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

countingcouplingpermutationswelded-trees

Let GGG be a valid properly three-colored welded-tree instance, with nnn even and 2≤l≤n−42\le l\le n-42≤l≤n−4. Let SSS be the finite set of edge permutations preserving the allowed edge classes whose permuted weld is a single cycle. Fix any set DDD of exposed input edges and any reference permutation hhh. Put

F={π∈S: π(d)=h(d) for all d∈D}.F=\{\pi\in S:\ \pi(d)=h(d)\text{ for all }d\in D\}.F={π∈S: π(d)=h(d) for all d∈D}.

For a weld edge e∉De\notin De∈/D, let C(e)C(e)C(e) be the weld edges of the same color as eee, and put r=∣C(e)∖D∣r=|C(e)\setminus D|r=∣C(e)∖D∣. Then, for every target edge zzz,

(r−1) ∣{π∈F:π(e)=z}∣≤∣F∣.(r-1)\,|\{\pi\in F:\pi(e)=z\}|\le |F|.(r−1)∣{π∈F:π(e)=z}∣≤∣F∣.

For F≠∅F\ne\varnothingF=∅ and r≥2r\ge2r≥2, this is precisely the conditional partner bound Pr⁡[π(e)=z∣π∈F]≤1/(r−1)\Pr[\pi(e)=z\mid\pi\in F]\le1/(r-1)Pr[π(e)=z∣π∈F]≤1/(r−1). The formal statement uses natural-number counts and truncated subtraction, so empty conditioning fibers and singleton residual classes require no separate hypotheses. A recorded or wrong-class target has zero count by injectivity or class preservation. Conditioning on nonweld records is allowed: those independent class-permutation coordinates do not affect the cycle condition.

The statement is solely a finite completion count. It asserts no coupling, random process, quantum claim, or path distribution. Counting is over colored edge permutations, not over their uncolored graph images.

Preamble
import Definitions.Def_WeldedPath_successProb
import Definitions.Def_FinitePermutationCoupling_BlockModel

set_option autoImplicit false
Formal statement
namespace WeldedPath

open Classical FinitePermutationCoupling

/-- The static conditional completion count underlying equation (76) in the
proof of Lemma 4.13, arXiv:2611.05912v1, Section 4.4. The factor uses truncated
natural subtraction, so empty fibers and one remaining partner are included.
No stochastic process, coupling, or path law is asserted here. -/
theorem single_cycle_completion_count :
    ∀ n l : ℕ, Even n → 2 ≤ l → l ≤ n - 4 →
    ∀ G : WeldedInstance n, G.IsValid →
    ∀ (D : Finset G.edges) (h : Equiv.Perm G.edges) (e z : G.edges),
      e.1 ∈ G.weldEdges → e ∉ D →
      (((Finset.univ.filter fun f : G.edges =>
          f.1 ∈ G.weldEdges ∧ G.color f.1 = G.color e.1) \ D).card - 1) *
        ((exposedFiber
          ((Finset.univ.filter (G.IsEdgePerm l)).filter G.SingleCycle) D h).filter
            fun π => π e = z).card ≤
        (exposedFiber
          ((Finset.univ.filter (G.IsEdgePerm l)).filter G.SingleCycle) D h).card := by
  sorry

end WeldedPath
Source
Carolan, Childs, Coudron, Gilani, Miloschewsky, Podder, Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard, https://arxiv.org/html/2611.05912v1#S4.SS4, Section 4.4, proof of Lemma 4.13, equation (76) and its path-deletion/insertion and endpoint-symmetry argument. The probability inequality is multiplied by the positive completion count and residual denominator; empty and singleton cases are included trivially. Arbitrary records outside the tested color are handled by conditioning on complete assignments of the other colors and averaging, with independent nonweld coordinates factored out.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me