Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sensitivity separation: MinmaxPreparedChecker (complete source module)

Definition
BS2_b3ba934b_MinmaxPreparedChecker

by yousofy · Oct 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

block-sensitivitysensitivitysensitivity-first-two-20261025

Complete Lean source module MinmaxPreparedChecker from the two verified sensitivity separation proofs. The module supplies the definitions, auxiliary lemmas, and exact finite certificates used by its dependent modules. All original declarations and proof bodies are retained; only local import module paths are changed for Prove2Me. The final campaign goals are published separately as theorems with submitted solutions.

Definition code
/- Verified coefficient and prepared-record caching for the shared min/max
   numerical transfer. The cached caps are exactly the first endpoint's caps. -/
import Definitions.Def_BS2_b3ba934b_MinmaxAExpressions
import Definitions.Def_BS2_b3ba934b_PreparedRawChecker

set_option autoImplicit false
set_option maxHeartbeats 4000000

namespace ThreeBoundMinmaxA
open ThreeBoundNumeric ThreeBoundFullProfile

def computedCosts (n : ℕ) (v : Profile n) (a c : ThreeBoundMinmaxNumeric.Entry) : Array (Array ℕ) := #[
  #[(headCost n a c 0 0).eval v,(headCost n a c 0 1).eval v,(headCost n a c 0 2).eval v],
  #[(headCost n a c 1 0).eval v,(headCost n a c 1 1).eval v,(headCost n a c 1 2).eval v],
  #[(headCost n a c 2 0).eval v,(headCost n a c 2 1).eval v,(headCost n a c 2 2).eval v],
  #[(headCost n a c 3 0).eval v,(headCost n a c 3 1).eval v,(headCost n a c 3 2).eval v],
  #[(headCost n a c 4 0).eval v,(headCost n a c 4 1).eval v,(headCost n a c 4 2).eval v],
  #[(headCost n a c 5 0).eval v,(headCost n a c 5 1).eval v,(headCost n a c 5 2).eval v],
  #[(headCost n a c 6 0).eval v,(headCost n a c 6 1).eval v,(headCost n a c 6 2).eval v],
  #[(headCost n a c 7 0).eval v,(headCost n a c 7 1).eval v,(headCost n a c 7 2).eval v]
]

def coeffCheck (n : ℕ) (v : Profile n) (a c : ThreeBoundMinmaxNumeric.Entry)
    (values : CostValues) : Bool :=
  values.heads==computedCosts n v a c &&
  values.guard==(bExpr n c.guard a.guard).eval v &&
  (List.range (c.tolerance+1)).all fun k=>
    values.negative.getD k 0==(aExpr n c.guard (c.lowerAt k)).eval v

def recordCostFast (n : ℕ) (v : Profile n) (caps : Caps) (a c : ThreeBoundMinmaxNumeric.Entry)
    (costs : Array (Array ℕ)) (x : Q2Record) : ℕ :=
  x 8*(bExpr n c.guard a.guard).eval v+
  ((List.range (c.tolerance+1)).map fun k=>
    negativeCount caps c.tolerance x k*(aExpr n c.guard (c.lowerAt k)).eval v).sum+
  ((List.range 8).map fun t=>x t*readCost costs t 0+
    x (9+2*t)*(readCost costs t 1-readCost costs t 0)+
    x (10+2*t)*(readCost costs t 2-readCost costs t 0)).sum

theorem recordCostFast_eq (n : ℕ) (v : Profile n) (caps : Caps)
    (a c : ThreeBoundMinmaxNumeric.Entry) (x : Q2Record) :
    recordCostFast n v caps a c (computedCosts n v a c) x=(recordCost n caps a c x).eval v := by
  simp only [recordCostFast,recordCost,negativeExpr,highExpr,Expr.eval,Expr.eval_sum,List.map_map]
  congr 1

theorem cachedRecordCost_eq (n : ℕ) (v : Profile n) (caps : Caps)
    (a c : ThreeBoundMinmaxNumeric.Entry) (values : CostValues)
    (h : coeffCheck n v a c values=true) (x : Q2Record) :
    cachedRecordCost caps c.tolerance values x=(recordCost n caps a c x).eval v := by
  have hparts : values.heads=computedCosts n v a c ∧
      values.guard=(bExpr n c.guard a.guard).eval v ∧
      ∀ k<c.tolerance+1, values.negative.getD k 0=(aExpr n c.guard (c.lowerAt k)).eval v := by
    simpa [coeffCheck,List.all_eq_true,Nat.lt_succ_iff,and_assoc] using h
  obtain ⟨hh,hg,hn⟩ := hparts
  rw [← recordCostFast_eq]
  unfold cachedRecordCost recordCostFast
  rw [hh,hg]
  congr 1
  congr 1
  apply congrArg List.sum
  apply List.map_congr_left
  intro k hk
  rw [hn k (List.mem_range.mp hk)]

def recordStateAllowed (a c : ThreeBoundMinmaxNumeric.Entry) (r : Q2Record) : Bool :=
  (List.range (c.tolerance+1)).all (fun b =>
      !(b<a.tolerance ∧ a.lowerAt (b+1)≤c.lowerAt b ∧ a.upperAt (b+1)≤c.upperAt b) ||
        (r (3+b)==0 && (if b=0 then r 6==0 else if b=1 then r 7==0 else true))) &&
    (List.range (c.tolerance+1)).all (fun b =>
      r b==0 || !(c.guard==a.lowerAt b && c.guard==a.upperAt b))

theorem recordAllowed_factor (caps : Caps) (a c : ThreeBoundMinmaxNumeric.Entry) (x : Q2Record) :
    recordAllowedFor caps a c x=(allowedRecord caps c.tolerance x && recordStateAllowed a c x) := by
  simp only [recordAllowedFor,recordStateAllowed,Bool.and_assoc]

def preparedRecordCheck (a c : ThreeBoundMinmaxNumeric.Entry) (p : PreparedValues)
    (values : CostValues) (bound : ℕ) (xs : List ℕ) : Bool :=
  let x:=recordOfList xs
  if p.feasible && recordStateAllowed a c x then preparedCost c.tolerance p values x≤bound else true

def indexedPreparedCheck (table : RecordLookup) (pre : ℕ → PreparedValues)
    (a c : ThreeBoundMinmaxNumeric.Entry) (values : CostValues) (bound k : ℕ) : Bool :=
  preparedRecordCheck a c (pre k) values bound (table.get k)

theorem record_bound_of_prepared (n : ℕ) (v : Profile n) (caps : Caps)
    (a c : ThreeBoundMinmaxNumeric.Entry) (p : PreparedValues) (values : CostValues)
    (bound : ℕ) (xs : List ℕ)
    (hp : PreparedOK caps c.tolerance (recordOfList xs) p)
    (hc : coeffCheck n v a c values=true)
    (h : preparedRecordCheck a c p values bound xs=true)
    (ha : recordAllowedFor caps a c (recordOfList xs)=true) :
    (recordCost n caps a c (recordOfList xs)).eval v≤bound := by
  rw [recordAllowed_factor,← hp.1] at ha
  have hf : p.feasible=true := by
    have hh := ha
    simp only [Bool.and_eq_true] at hh
    exact hh.1
  have hh : preparedCost c.tolerance p values (recordOfList xs)≤bound := by
    simpa only [preparedRecordCheck,ha,if_true,decide_eq_true_eq] using h
  rw [preparedCost_eq caps c.tolerance p values (recordOfList xs) hp hf,
    cachedRecordCost_eq n v caps a c values hc] at hh
  exact hh

theorem gradedA_le_of_prepared_checks (n : ℕ) (v : Profile n) (caps : Caps)
    (records : List (List ℕ)) (table : RecordLookup) (pre : ℕ → PreparedValues)
    (a c : ThreeBoundMinmaxNumeric.Entry) (values : CostValues) (bound : ℕ)
    (hvalid : table.valid) (hrows : table.rows=records)
    (hc : coeffCheck n v a c values=true)
    (hp : ∀ k, k<table.rows.length → PreparedOK caps c.tolerance (recordOfList (table.get k)) (pre k))
    (h : ∀ k, k<table.rows.length → indexedPreparedCheck table pre a c values bound k=true) :
    (gradedAExpr n caps records a c).eval v≤bound := by
  rw [gradedAExpr,Expr.eval_maximum]
  apply maximum_le
  intro value hv
  obtain ⟨e,he,rfl⟩ := List.mem_map.mp hv
  obtain ⟨xs,hxs,he⟩ := List.mem_filterMap.mp he
  obtain ⟨k,hk⟩ := List.mem_iff_get.mp hxs
  have hlen : k.val<table.rows.length := by simpa only [hrows] using k.isLt
  have heq : table.get k.val=xs := by
    rw [table.get_correct hvalid k.val hlen,hrows,List.getElem?_eq_getElem k.isLt]
    exact hk
  have hp' := hp k.val hlen
  have h' := h k.val hlen
  rw [heq] at hp'
  change preparedRecordCheck a c (pre k.val) values bound (table.get k.val)=true at h'
  rw [heq] at h'
  by_cases ha : recordAllowedFor caps a c (recordOfList xs)=true
  · simp only [ha,if_true] at he
    have he' : recordCost n caps a c (recordOfList xs)=e := Option.some.inj he
    rw [← he']
    exact record_bound_of_prepared n v caps a c (pre k.val) values bound xs hp' hc h' ha
  · simp [ha] at he

theorem rawA_le_graded (n : ℕ) (v : Profile n) (caps : Caps)
    (records : List (List ℕ)) (a c : ThreeBoundMinmaxNumeric.Entry)
    (hplain : (a.plain && c.plain)=false) (hpos : c.tolerance≠0) :
    (rawAExpr n caps records a c).eval v≤(gradedAExpr n caps records a c).eval v := by
  simp only [rawAExpr,hplain,Bool.false_eq_true,if_false,hpos]
  by_cases ho : c.ordinary=true
  · simp only [ho,if_true,Expr.eval_minimum]
    exact foldl_min_le _ _
  · simp only [ho,if_false]
    exact le_rfl

theorem rawA_le_of_prepared_checks (n : ℕ) (v : Profile n) (caps : Caps)
    (records : List (List ℕ)) (table : RecordLookup) (pre : ℕ → PreparedValues)
    (a c : ThreeBoundMinmaxNumeric.Entry) (values : CostValues) (bound : ℕ)
    (hvalid : table.valid) (hrows : table.rows=records)
    (hplain : (a.plain && c.plain)=false) (hpos : c.tolerance≠0)
    (hc : coeffCheck n v a c values=true)
    (hp : ∀ k, k<table.rows.length → PreparedOK caps c.tolerance (recordOfList (table.get k)) (pre k))
    (h : ∀ k, k<table.rows.length → indexedPreparedCheck table pre a c values bound k=true) :
    (rawAExpr n caps records a c).eval v≤bound :=
  (rawA_le_graded n v caps records a c hplain hpos).trans
    (gradedA_le_of_prepared_checks n v caps records table pre a c values bound hvalid hrows hc hp h)

end ThreeBoundMinmaxA

#print axioms ThreeBoundMinmaxA.rawA_le_of_prepared_checks
Source
Attached verified checkpoint block_sensitivity_three_bounds; lean_project/MinmaxPreparedChecker.lean; original SHA-256 5c6f89817f9c1b3d561eaecfe3041d3aa847d0621dfb9f57dff1d625168d76c3; campaign https://prove2.me/campaigns/block-sensitivity-vs-sensitivity

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