Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Correctness of the rational projected round-or-cut oracle

Open
Lax263307Proofs.ProjectedOracle.run_correct

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.

Retired because the namespace-wrapped declaration compiled during publication but the proof-comparison parser rejects that header (expected token / unknown full theorem identifier). The mathematically identical, fully qualified declaration is Lax263307Proofs.ProjectedOracle.run_correct_native.

Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces
Formal statement
namespace Lax263307Proofs.ProjectedOracle
theorem run_correct : ∀ {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),
  Nat.lt ((0:Nat)) K →
    Nat.lt ((0:Nat)) n →
      Nat.le ((4:Nat)) 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))
                                ((2:Nat))))
                            (@HMul.hMul Real Real Real (@instHMul Real Real.instMul)
                              (@OfNat.ofNat Real (nat_lit 32)
                                (@instOfNatAtLeastTwo Real (nat_lit 32) Real.instNatCast
                                  (@Nat.instAtLeastTwoHAddOfNat
                                    ((31:Nat))
                                    (@Nat.instNeZeroSucc ((30:Nat))))))
                              (@HPow.hPow Real Nat Real
                                (@instHPow Real Nat (@NPow.toPow Real (@Monoid.toNPow Real Real.instMonoid)))
                                (@Nat.cast Real Real.instNatCast n)
                                ((2:Nat)))))) →
                      @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
end Lax263307Proofs.ProjectedOracle
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