Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sensitivity separation: MinmaxRecordAllowed (complete source module)

Definition
BS2_b3ba934b_MinmaxRecordAllowed

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

block-sensitivitysensitivitysensitivity-first-two-20261025

Complete Lean source module MinmaxRecordAllowed 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
/- Recipe-dependent min/max filters hold for every actual record. -/
import Definitions.Def_BS2_b3ba934b_MinmaxKindCost
import Definitions.Def_BS2_b3ba934b_RecordAllowedAlgorithm
import Definitions.Def_BS2_b3ba934b_TypeCountSums

set_option autoImplicit false
set_option maxHeartbeats 7000000
set_option maxRecDepth 20000

namespace ThreeBoundMinmaxA
open OAI.Paper320 ThreeBoundWitness ThreeBoundProfiles
open ThreeBoundMinmaxTransfer ThreeBoundMinmaxCandidates ThreeBoundMinmaxQ2
open ThreeBoundMinmaxNumeric (EntryMatch)
open ThreeBoundNumeric ThreeBoundFullProfile ThreeBoundAccounting ThreeBoundTypeCounts
open scoped Classical BigOperators
noncomputable section
variable {n : ℕ} {I V : Type} [Fintype I] [Fintype V]

theorem recordAllowedFor_of (caps : Caps) (a c : ThreeBoundMinmaxNumeric.Entry) (r : Q2Record)
    (hallowed : allowedRecord caps c.tolerance r=true)
    (hguard : ∀ b, b ≤ c.tolerance → b < a.tolerance →
      a.lowerAt (b+1) ≤ c.lowerAt b → a.upperAt (b+1) ≤ c.upperAt b →
      r (3+b)=0 ∧ (b=0 → r 6=0) ∧ (b=1 → r 7=0))
    (hpositive : ∀ b, b ≤ c.tolerance → r b≠0 →
      ¬ (c.guard=a.lowerAt b ∧ c.guard=a.upperAt b)) :
    recordAllowedFor caps a c r=true := by
  unfold recordAllowedFor
  simp only [Bool.and_eq_true]
  constructor
  · refine ⟨hallowed,?_⟩
    apply List.all_eq_true.mpr
    intro b hb
    have hb' : b ≤ c.tolerance := Nat.le_of_lt_succ (List.mem_range.mp hb)
    by_cases he : b < a.tolerance ∧ a.lowerAt (b+1) ≤ c.lowerAt b ∧ a.upperAt (b+1) ≤ c.upperAt b
    · obtain ⟨hg,h0,h1⟩ := hguard b hb' he.1 he.2.1 he.2.2
      simp only [he,decide_true,Bool.not_true,Bool.false_or,hg,beq_self_eq_true,Bool.true_and]
      split_ifs with hz ho
      · simp [h0 hz]
      · simp [h1 ho]
      · rfl
    · simp [he]
  · apply List.all_eq_true.mpr
    intro b hb
    have hb' : b ≤ c.tolerance := Nat.le_of_lt_succ (List.mem_range.mp hb)
    by_cases hz : r b=0
    · simp [hz]
    · have he := hpositive b hb' hz
      simp [hz]
      tauto

theorem actual_recordAllowedFor (S : Stage (Fin n) I V)
    (F : Fin n → (I → Bool) → Bool) (hF : Nested F)
    (i j : Fin n) (P : PairData S F i j) (a c : ThreeBoundMinmaxNumeric.Entry)
    (hm : EntryMatch S F i j P a c)
    (input : ((V × Bool) × I) → Bool) (hoff : parent S F i input=false)
    (hQ : S.tolerance j ≤ 2) (tag : V → Fin 8)
    (hk : ∀ w ∈ highHeads S F P.strongLower P.strongUpper j input,
      ThreeBoundHighTypes.OfKind 2
        (PositiveCandidate S F P.strongLower P.strongUpper j input w)
        (GuardCandidate S F P.strongLower P.strongUpper j input w) (tag w))
    (caps : Caps) (r : Q2Record)
    (hx : ∀ k : Fin 8, r k.val=typeCount (highHeads S F P.strongLower P.strongUpper j input) tag k)
    (hprefix : ∀ b, b ≤ c.tolerance → positivePrefix r b ≤ capPrefix caps r b) :
    recordAllowedFor caps a c r=true := by
  let H := highHeads S F P.strongLower P.strongUpper j input
  have hcQ : c.tolerance ≤ 2 := by rw [← hm.strongTolerance]; exact hQ
  have hz (kind : Fin 8) (h : ∀ w ∈ H, tag w≠kind) : r kind.val=0 :=
    (hx kind).trans (typeCount_zero_of_forbidden H tag kind h)
  have hguardZero (b : ℕ) (hba : b < a.tolerance)
      (ht : a.lowerAt (b+1) ≤ c.lowerAt b) (hu : a.upperAt (b+1) ≤ c.upperAt b)
      (kind : Fin 8) (hkind : 3 ≤ kind.val) (hlevel : guardLevel kind.val=b) : r kind.val=0 := by
    apply hz kind
    intro w hw he
    have hkw := hk w hw
    rw [he] at hkw
    have hg := kind_guard _ _ kind hkw hkind
    rw [hlevel] at hg
    have hbi : b+1 ≤ S.tolerance i := by rw [hm.weakTolerance]; omega
    apply guard_forbidden_next S F hF i j P input hoff w b hg hbi
    · change (P.weakLower (b+1)).val ≤ (P.strongLower b).val
      rw [hm.weakLower (b+1) hbi,hm.strongLower b hg.1]
      exact ht
    · change (P.weakUpper (b+1)).val ≤ (P.strongUpper b).val
      rw [hm.weakUpper (b+1) hbi,hm.strongUpper b hg.1]
      exact hu
  apply recordAllowedFor_of caps a c r
  · apply ThreeBoundRecordAllowedAlgorithm.allowedRecord_of caps c.tolerance r
    · intro hq1
      have hS : S.tolerance j ≤ 1 := by rw [hm.strongTolerance,hq1]
      have hne (kind : Fin 8) (he : kind.val=2 ∨ kind.val=5 ∨ kind.val=7) : r kind.val=0 := by
        apply hz kind
        intro w hw heq
        have h := kind_tolerance_one S F P.strongLower P.strongUpper j input w hS (tag w) (hk w hw)
        have hv := congrArg Fin.val heq
        rcases he with h2 | h5 | h7 <;> omega
      exact ⟨hne ⟨2,by omega⟩ (Or.inl rfl),
        hne ⟨5,by omega⟩ (Or.inr (Or.inl rfl)),hne ⟨7,by omega⟩ (Or.inr (Or.inr rfl))⟩
    · exact hprefix
  · intro b hb hba ht hu
    refine ⟨?_,?_,?_⟩
    · exact hguardZero b hba ht hu ⟨3+b,by omega⟩ (by change 3 ≤ 3+b; omega)
        (by simp [guardLevel]; omega)
    · intro hb0
      subst b
      exact hguardZero 0 hba ht hu ⟨6,by omega⟩ (by change 3 ≤ 6; decide) (by norm_num [guardLevel])
    · intro hb1
      subst b
      exact hguardZero 1 hba ht hu ⟨7,by omega⟩ (by change 3 ≤ 7; decide) (by norm_num [guardLevel])
  · intro b hb hnz he
    let kind : Fin 8 := ⟨b,by omega⟩
    have hpos : 0 < typeCount H tag kind := by rw [← hx kind]; exact Nat.pos_of_ne_zero hnz
    obtain ⟨w,hw,heq⟩ := nonempty_type_of_count_pos H tag kind hpos
    have hkw := hk w hw
    rw [heq] at hkw
    have hp := kind_positive 2 _ _ kind hkw (by dsimp [kind]; omega)
    have hbj : b ≤ S.tolerance j := by rw [hm.strongTolerance]; exact hb
    have hbi := hbj.trans P.tolerances
    have ht : S.guard j=P.weakLower b := Fin.ext (by rw [hm.strongGuard,hm.weakLower b hbi]; exact he.1)
    have hu : S.guard j=P.weakUpper b := Fin.ext (by rw [hm.strongGuard,hm.weakUpper b hbi]; exact he.2)
    have hmm : mm F (P.weakLower b) (P.weakUpper b) (child input w false) (child input w true)=true := by
      rw [← ht,← hu]
      simp only [mm,hp.2 false,hp.2 true,Bool.and_self,Bool.or_self]
    have hf := weak_target_false S F hF i j P input hoff w b hbj hp.1.2.1.le
    rw [hf] at hmm
    contradiction

end
end ThreeBoundMinmaxA

#print axioms ThreeBoundMinmaxA.actual_recordAllowedFor
Source
Attached verified checkpoint block_sensitivity_three_bounds; lean_project/MinmaxRecordAllowed.lean; original SHA-256 e94c1d2ab7f451c36fcea68eb3808e3c048928ad2c56489bf22b7d0d20f2b92f; 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