Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Stable canonical coefficients for arbitrary recorded forests

Proved
WeldedPath.forest_coefficient_stability

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

coefficient-stabilityquantum-query-complexitywelded-trees

Let H be any valid abstract forest on k vertices, G a valid welded-tree instance, n≥16 and 2≤l≤n−4. Let B contain V_bd and be disjoint from the weld. Assume

4k∣B∣2n≤12,192(n+1)k32n≤12.\frac{4k|B|}{2^n}\le\frac12,\qquad \frac{192(n+1)k^3}{2^n}\le\frac12.2n4k∣B∣​≤21​,2n192(n+1)k3​≤21​.

For each valid canonical description of H, form its assignment amplitude before imposing injectivity: sqrt(μ_ref(φ)) when its fixed Wfix data agree and every vertex outside its selected tree components avoids B, and zero otherwise. Let S be the complex span of these amplitudes, including all descriptions, all components and all boundary patterns.

For every f₀ in S there exists f in S such that

f(ϕ)=f0(ϕ)for every injective ϕ,∥f∥22≤2∑ϕ  injective∣f0(ϕ)∣2.f(\phi)=f_0(\phi)\quad\text{for every injective }\phi, \qquad\|f\|_2^2\le2\sum_{\phi\;\mathrm{injective}}|f_0(\phi)|^2.f(ϕ)=f0​(ϕ)for every injective ϕ,∥f∥22​≤2ϕinjective∑​∣f0​(ϕ)∣2.

The constant is independent of the number and sizes of connected components. This is the stable coefficient representative needed to remove noninjective assignments in the good-space analysis.

Preamble
import Definitions.Def_WeldedPath_Supplement_projGood

set_option autoImplicit false
Formal statement
namespace WeldedPath

open Classical Supplement
open scoped BigOperators

theorem forest_coefficient_stability :
    ∀ n l : ℕ, 16 ≤ n → 2 ≤ l → l ≤ n - 4 →
    ∀ G : WeldedInstance n, G.IsValid →
    ∀ H : AbsForest n, H.IsValid →
    ∀ B : Finset ℕ, Vbd n l ⊆ B → Disjoint B (Vweld n) →
      (H.k : ℝ) * (B.card : ℝ) * (4 / (2 : ℝ) ^ n) ≤ 1 / 2 →
      2 * (H.k : ℝ) ^ 3 * (96 * ((n : ℝ) + 1) / (2 : ℝ) ^ n) ≤ 1 / 2 →
    let amplitude := fun (sel : Finset (Fin H.k)) (φ₀ : Fin H.k → Label n) =>
      (WithLp.toLp 2 (fun φ : Fin H.k → Label n =>
        if (∀ s ∈ sel, H.Wfix φ s = H.Wfix φ₀ s) ∧
          (∀ s ∈ sel, ∀ u, H.graph.Reachable s u → u ∉ H.Ctree φ s → (φ u).val ∉ B)
        then (Real.sqrt (H.muRef l G φ) : ℂ) else 0) : Hil (Fin H.k → Label n))
    let S := Submodule.span ℂ {f | ∃ sel φ₀,
      (Description.mk H sel φ₀).IsValid ∧ f = amplitude sel φ₀}
    ∀ f₀ : Hil (Fin H.k → Label n), f₀ ∈ S →
    ∃ f : Hil (Fin H.k → Label n), f ∈ S ∧
      (∀ φ, Function.Injective φ → f φ = f₀ φ) ∧
      ‖f‖ ^ 2 ≤ 2 * ∑ φ, if Function.Injective φ then ‖f₀ φ‖ ^ 2 else 0 := 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.SS1, Section 4.1, Lemmas 4.3-4.5. This states the coefficient-stability conclusion for the literal canonical Description span, with explicit constants and arbitrary disconnected forests.

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