Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.7 — randomized search for two perfect matchings of opposite signs

Open
PfaffianRecognition.Recognition.Supplement.theorem_3_7

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1pfaffian

There is one randomized machine M\mathcal MM reading fair random bits, and constants C≥1C\ge1C≥1, kkk, fixed before all inputs, such that for every finite simple graph GGG on {0,…,N−1}\{0,\dots,N-1\}{0,…,N−1} and every orientation DDD of GGG, with input www the encoding of (G,D)(G,D)(G,D) and budget B=C (∣w∣+2)kB=C\,(|w|+2)^kB=C(∣w∣+2)k:

  1. on every random tape of length BBB, M\mathcal MM halts within BBB steps using at most BBB random bits;
  2. if DDD is non-Pfaffian, then with probability at least 1/21/21/2 over the BBB fair bits, the output of M\mathcal MM is the encoding of a pair (M1,M2)(M_1,M_2)(M1​,M2​) of perfect matchings of GGG with
sign⁡D(M1)≠sign⁡D(M2).\operatorname{sign}_D(M_1)\ne\operatorname{sign}_D(M_2).signD​(M1​)=signD​(M2​).

Such a pair certifies that DDD is non-Pfaffian; the theorem turns the randomized test of Theorem 3.2 into a certificate finder.

Formalization Note The machine model, input encoding, step and tape budget and fair-bit probability are those of the published computation model (as in InCoRP). The output is the concatenation of the two N2N^2N2 row-major edge-indicator vectors of M1M_1M1​ and M2M_2M2​ (matchingBits).

Differences from the source:

  • encoding: arbitrary finite simple graph G → SimpleGraph (Fin N) for every N, vertices in a fixed order; reason: every finite simple graph has such a labelling; no instance is removed
  • encoding: randomized polynomial time algorithm → one CoinMachine with RunsWithin under the single bound B = C·(|w|+2)^k (1 ≤ C) on steps and random bits, probability by fairProb over B fair bits; reason: the published bit-machine model of the base mission; polynomial time with no prescribed exponent
  • encoding: finds two perfect matchings of opposite signs → output equals matchingBits M₁ ++ matchingBits M₂ for perfect matchings with matchingSign D M₁ ≠ matchingSign D M₂; reason: signs are ±1, so different means opposite; the encoding is injective
  • reading: polynomial time algorithm given a non-Pfaffian orientation → the time and tape bound holds on every tape for every graph/orientation input, Pfaffian or not; reason: the usual meaning of a polynomial time algorithm on its input domain (graphs with orientations); the stronger of the two readings
Preamble
import Definitions.Def_PfaffianRecognition_Recognition_computation_model
Formal statement
namespace PfaffianRecognition.Recognition.Supplement

open PfaffianRecognition.Recognition

/-- Theorem 3.7, p. 11 (proof pp. 11–12). One fair-bit machine and one polynomial bound, fixed
before all inputs: on every graph/orientation encoding and every tape it halts within the bound;
on a non-Pfaffian orientation, with probability at least 1/2 its output is the encoding of two
perfect matchings of `G` of opposite signs. -/
theorem theorem_3_7 :
    ∃ M : HypergraphUnreliability.FPRAS.CoinMachine, ∃ C k : ℕ, 1 ≤ C ∧
      ∀ (N : ℕ) (G : SimpleGraph (Fin N)) (D : Orientation G),
        let w := orientedGraphBits D
        let B := C * (w.length + 2) ^ k
        (∀ ω : Fin B → Bool, ∃ out : List Bool,
          M.RunsWithin w (HypergraphUnreliability.FPRAS.tapeList ω) B out) ∧
        (¬ IsPfaffianOrientation D → (1 / 2 : ℝ) ≤ HypergraphUnreliability.FPRAS.fairProb B
          (fun ω => ∃ M₁ M₂ : Finset G.edgeSet,
            MulmuleyVV.Matching.IsPerfectMatchingEdges G M₁ ∧
            MulmuleyVV.Matching.IsPerfectMatchingEdges G M₂ ∧
            matchingSign D M₁ ≠ matchingSign D M₂ ∧
            M.RunsWithin w (HypergraphUnreliability.FPRAS.tapeList ω) B
              (CatalyticMatching.General.matchingBits M₁ ++
                CatalyticMatching.General.matchingBits M₂))) := by sorry

end PfaffianRecognition.Recognition.Supplement
Source
Priyanshu Pant, Ranveer Singh, Pfaffian Recognition is in coRP, STOC 2027 submission #858 (October 2026), Theorem 3.7, p. 11 (proof pp. 11–12); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/858.pdf

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