Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Snap displacement versus the recorded margin (margin–ledger joint)

Proved
QMCLeafB.SnapLedger.ledger_round_ok

by marwahaha · Nov 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-optimizationnumerical-analysisquantum-max-cut

A separation loop that runs its oracle at a snapped (rational) centre, while its engine's recorded centre is the exact iterate, must account for the displacement when it records the round's margin.

Let ccc be the cut normal, aaa the snapped centre at which the oracle was evaluated, and a′a'a′ the engine's recorded centre. Suppose the cut separates a set SSS around aaa with margin mmm:

−m≤⟨c,z−a⟩for all z∈S.-m \le \langle c, z-a\rangle \quad\text{for all } z\in S.−m≤⟨c,z−a⟩for all z∈S.

Suppose moreover ∥c∥≤C\lVert c\rVert \le C∥c∥≤C and ∥a−a′∥≤ε\lVert a-a'\rVert \le \varepsilon∥a−a′∥≤ε. Then Cauchy–Schwarz gives

⟨c,z−a′⟩=⟨c,z−a⟩+⟨c,a−a′⟩≥−m−Cε,\langle c, z-a'\rangle = \langle c, z-a\rangle + \langle c, a-a'\rangle \ge -m - C\varepsilon,⟨c,z−a′⟩=⟨c,z−a⟩+⟨c,a−a′⟩≥−m−Cε,

so the cut separates SSS around a′a'a′ with the inflated margin m+Cεm + C\varepsilonm+Cε.

Consequently the bookkeeping pair a ledger needs for the round holds at del := m + Cε: the margin is nonnegative, it fits the quadratic room del2≤ρ2σ\text{del}^2 \le \rho^2\sigmadel2≤ρ2σ, and the separation clause holds around the recorded centre.

The sign matters: the displacement can only weaken the guaranteed separation, so the recorded margin must be m+Cεm + C\varepsilonm+Cε, not m−Cεm - C\varepsilonm−Cε. Recording the smaller value would be unsound, and the ledger's room must therefore contain the snap cost on top of the oracle's own margin.

Preamble
import Mathlib
open Finset
Formal statement
theorem QMCLeafB.SnapLedger.ledger_round_ok {k : ℕ} {S : Set (Fin k → ℝ)} {c a a' : Fin k → ℝ} {m C ε rho sigma : ℝ}
    (hsep : ∀ z ∈ S, -m ≤ ∑ i, c i * (z i - a i))
    (hC : Real.sqrt (∑ i, (c i) ^ 2) ≤ C)
    (hε : Real.sqrt (∑ i, (a i - a' i) ^ 2) ≤ ε)
    (hm : 0 < m) (hε0 : 0 ≤ ε) (hrho : 0 ≤ rho) (hsigma : 0 ≤ sigma)
    (hroom : (m + C * ε) ^ 2 ≤ rho ^ 2 * sigma) :
    0 ≤ m + C * ε ∧ (m + C * ε) ^ 2 ≤ rho ^ 2 * sigma ∧
      ∀ z ∈ S, -(m + C * ε) ≤ ∑ i, c i * (z i - a' i) := by sorry
Source
Internal: ellipsoid/separation-loop ledger accounting for the Quantum Max-Cut 0.53 formalisation (BOV rank-three rounding campaign); no external source — elementary Cauchy–Schwarz argument.

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