Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite comparison of formal topology moments and feasible pattern containment

Proved
QuantumBipartiteTesting.Bipartiteness.topology_pattern_comparison

by Shuze Chen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

finite-probabilitypolynomial-methodquantum-query-complexity

Fix valid parameters N,M,lN,M,lN,M,l, with l≥1l\ge1l≥1, N≤MN\le MN≤M, and 2l∣M2l\mid M2l∣M. Let FFF be a consistent colored graph pattern on the NNN visible vertices, and suppose

2∣F∣≤M/l.2|F|\le M/l.2∣F∣≤M/l.

If GGG is sampled by the published feasible hidden-block construction, then its containment probability satisfies

∣Pr⁡feas[F⊆G]−WF(M,l)∣≤Pr⁡[overflow],\left|\Pr_{\mathrm{feas}}[F\subseteq G]-W_F(M,l)\right| \le\Pr[\mathrm{overflow}],​feasPr​[F⊆G]−WF​(M,l)​≤Pr[overflow],

where WFW_FWF​ is the formal topology functional defined by the partition sums (A.2)–(A.4).

This comparison identifies the formal functional through the moments of the observed pattern, rather than defining it to be an overflow-completed graph distribution. The capacity hypothesis ensures that the matching moments for every placement of the pattern are finite probabilities. The result supplies the topology component of the response-monomial comparison in Lemma 3.12.

Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction
open QuantumBipartiteTesting.Bipartiteness Finset
open scoped BigOperators Classical
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.topology_pattern_comparison {N colors : ℕ} (M l : ℕ) (hv : ValidParameters N M l)
    (F : Finset (ColoredEdge N colors)) (hF : Consistent F) (hsmall : 2*F.card ≤ M/l) :
    |FeasibleBase N M l (fun G : Finset (ColoredEdge N colors) => if F ⊆ G then (1:ℝ) else 0)-
      TopologyMoment F M l| ≤ OverflowProbability N M l := by sorry
Source
Kayal–Sen–Szabó, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf, §3.2 Definition 3.7, Appendix A.2 equations (A.2)–(A.4), printed pp.30–31, and Appendix A.4 monomial coupling estimate for Lemma 3.12. The explicit finite capacity condition guarantees that each pattern matching moment is a probability.

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