Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Correctness of the rational projected round-or-cut oracle

Proved
Lax263307Proofs.ProjectedOracle.run_correct_native

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

algorithmscomputational-complexitygraph-theory

Fix a positive-order graph, a positive structural constant, precision denominator at least four, and the other published algorithm parameters. Assume the LP function always returns valid certificates and that the near branch, including its supplied child procedure, satisfies its complete correctness contract. For every rational moment-coordinate query center xxx, the actual functional projected procedure returns a correct rounded-oracle reply:

CorrectReply⁡G,k,h,a,K,B,D(x,ProjectedOracle⁡(x)).\operatorname{CorrectReply}_{G,k,h,a,K,B,D}\bigl(x,\operatorname{ProjectedOracle}(x)\bigr).CorrectReplyG,k,h,a,K,B,D​(x,ProjectedOracle(x)).

This is a reusable source interface for composing the complete finite-program implementation.

Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces
namespace Lax263307Proofs.ProjectedOracle
end Lax263307Proofs.ProjectedOracle
Formal statement
theorem Lax263307Proofs.ProjectedOracle.run_correct_native : ∀ {n : Nat} (lp flow : List Nat → List Nat) (a K B D : Nat) (G : SimpleGraph (Fin n))
  [inst : @DecidableRel (Fin n) (Fin n) (@SimpleGraph.Adj (Fin n) G)] (k h : Nat),
  @LT.lt Nat instLTNat (@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) K →
    @LT.lt Nat instLTNat (@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) n →
      @LE.le Nat instLENat (@OfNat.ofNat Nat (nat_lit 4) (instOfNatNat (nat_lit 4))) D →
        (∀ (m N : Nat) (P : Lax109476.LinearProgram.Program Rat m N),
            @Lax109476.RationalCertificates.IsValidCertificate m N P (@Lax263307.RegisteredLP.certificate m N lp P)) →
          ∀ (child : Finset (Fin n) → Nat → Option (Finset (Fin n))),
            (∀ (y : Lax263307.RationalConditioning.RationalVector n (Lax263307.AlgorithmParameters.level a K B n D)),
                @Lax263307.LinearRelaxation.IsFeasible n G k (Lax263307.AlgorithmParameters.level a K B n D)
                    (@Lax263307.RationalConditioning.realVector n (Lax263307.AlgorithmParameters.level a K B n D) y) →
                  ∀ (x : Lax263307.LinearRelaxation.MomentVector n (Lax263307.AlgorithmParameters.level a K B n D)),
                    (∀ (T : Lax263307.LinearRelaxation.Coordinate n (Lax263307.AlgorithmParameters.level a K B n D)),
                        @LE.le Real Real.instLE
                          (@abs Real Real.lattice Real.instAddGroup
                            (@HSub.hSub Real Real Real (@instHSub Real Real.instSub) (x T)
                              (@Lax263307.RationalConditioning.realVector n
                                (Lax263307.AlgorithmParameters.level a K B n D) y T)))
                          (@HDiv.hDiv Real Real Real (@instHDiv Real (@DivInvMonoid.toDiv Real Real.instDivInvMonoid))
                            (@HMul.hMul Real Real Real (@instHMul Real Real.instMul)
                              (@Rat.cast Real Real.instRatCast (Lax263307.AlgorithmParameters.momentFloor a K B n D))
                              (@HPow.hPow Real Nat Real
                                (@instHPow Real Nat (@NPow.toPow Real (@Monoid.toNPow Real Real.instMonoid)))
                                (@HDiv.hDiv Real Real Real
                                  (@instHDiv Real (@DivInvMonoid.toDiv Real Real.instDivInvMonoid))
                                  (@OfNat.ofNat Real (nat_lit 1) (@One.toOfNat1 Real Real.instOne))
                                  (@Nat.cast Real Real.instNatCast D))
                                (@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
                            (@HMul.hMul Real Real Real (@instHMul Real Real.instMul)
                              (@OfNat.ofNat Real (nat_lit 32)
                                (@instOfNatAtLeastTwo Real (nat_lit 32) Real.instNatCast
                                  (@Nat.instAtLeastTwoHAddOfNat
                                    (@OfNat.ofNat Nat (nat_lit 31) (instOfNatNat (nat_lit 31)))
                                    (@Nat.instNeZeroSucc (@OfNat.ofNat Nat (nat_lit 30) (instOfNatNat (nat_lit 30)))))))
                              (@HPow.hPow Real Nat Real
                                (@instHPow Real Nat (@NPow.toPow Real (@Monoid.toNPow Real Real.instMonoid)))
                                (@Nat.cast Real Real.instNatCast n)
                                (@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))))) →
                      @Lax263307.NearOracle.Correct n (Lax263307.AlgorithmParameters.level a K B n D) G k h D
                        (@Rat.cast Real Real.instRatCast (Lax263307.AlgorithmParameters.momentFloor a K B n D)) x
                        (@Lax263307.NearOracle.run n flow a K B D G inst k y child)) →
              ∀ (center : Lax263307.MomentLP.Index n (Lax263307.AlgorithmParameters.level a K B n D) → Rat),
                @Lax263307.ProjectedOracle.Correct n G k h a K B D center
                  (@Lax263307.ProjectedOracle.run n lp flow a K B D G inst k child center) := by sorry
Source
https://github.com/EdouardBonnet/lax-263307/blob/68b2d26aa2075e2ef80fd9d355ea748d2a818fd1/proofs/Lax263307Proofs/ProjectedOracle.lean, theorem run_correct (lines 63–194)

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