Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sensitivity separation: HighTypeCore (complete source module)

Definition
BS2_b3ba934b_HighTypeCore

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

block-sensitivitysensitivitysensitivity-first-two-20261025

Complete Lean source module HighTypeCore 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
/- The finite high-head type system depends only on exact guard counts.
It covers both equal-threshold and symmetric min/max targets, through any
fixed maximum tolerance. The cases q=2 and q=3 have 8 and 11 types. -/
import Mathlib.Data.Fintype.Basic
import Lean.Elab.Tactic.Omega

set_option autoImplicit false
set_option maxHeartbeats 5000000

namespace ThreeBoundHighTypes

abbrev Kind (q : ℕ) := Fin (3*q+2)

def OfKind (q : ℕ) (P G : ℕ → Prop) (k : Kind q) : Prop :=
  if k.val ≤ q then P k.val ∧ (k.val=0 ∨ ¬ G (k.val-1))
  else if k.val ≤ 2*q+1 then G (k.val-(q+1)) ∧ (k.val=2*q+1 ∨ ¬ P (k.val-q))
  else P (k.val-(2*q+1)) ∧ G (k.val-(2*q+2))

def budget (q : ℕ) (k : Kind q) : ℕ :=
  if k.val ≤ q then k.val else if k.val ≤ 2*q+1 then k.val-q else k.val-(2*q+1)

def isGuard (q : ℕ) (k : Kind q) : Bool := decide (q+1 ≤ k.val)

def positivePrefix (q b : ℕ) (k : Kind q) : Bool :=
  decide ((k.val ≤ q ∧ k.val ≤ b) ∨ (2*q+2 ≤ k.val ∧ k.val-(2*q+1) ≤ b))

theorem exists_kind (q d : ℕ) (P G : ℕ → Prop)
    (hp : ∀ b, P b → b ≤ q ∧ d=b)
    (hg : ∀ b, G b → b ≤ q ∧ d=b+1)
    (h : (∃ b, P b) ∨ ∃ b, G b) : ∃ k : Kind q, OfKind q P G k := by
  classical
  rcases h with ⟨b,hb⟩ | ⟨b,hb⟩
  · obtain ⟨hbq,hbd⟩ := hp b hb
    by_cases hz : b=0
    · subst b
      refine ⟨⟨0,by omega⟩,?_⟩
      simp only [OfKind,Fin.val_mk,Nat.zero_le,ite_true,true_or,and_true]
      simpa only [hz] using hb
    · by_cases hh : G (b-1)
      · refine ⟨⟨2*q+1+b,by omega⟩,?_⟩
        have h1 : ¬ 2*q+1+b ≤ q := by omega
        have h2 : ¬ 2*q+1+b ≤ 2*q+1 := by omega
        have he1 : 2*q+1+b-(2*q+1)=b := by omega
        have he2 : 2*q+1+b-(2*q+2)=b-1 := by omega
        simpa only [OfKind,Fin.val_mk,if_neg h1,if_neg h2,he1,he2] using And.intro hb hh
      · refine ⟨⟨b,by omega⟩,?_⟩
        simp only [OfKind,Fin.val_mk,if_pos hbq]
        exact ⟨hb,Or.inr hh⟩
  · obtain ⟨hbq,hbd⟩ := hg b hb
    by_cases hlast : b=q
    · subst b
      refine ⟨⟨2*q+1,by omega⟩,?_⟩
      have h1 : ¬ 2*q+1 ≤ q := by omega
      have he : 2*q+1-(q+1)=q := by omega
      simp [OfKind,h1,he,hb]
    · by_cases hh : P (b+1)
      · refine ⟨⟨2*q+2+b,by omega⟩,?_⟩
        have h1 : ¬ 2*q+2+b ≤ q := by omega
        have h2 : ¬ 2*q+2+b ≤ 2*q+1 := by omega
        have he1 : 2*q+2+b-(2*q+1)=b+1 := by omega
        have he2 : 2*q+2+b-(2*q+2)=b := by omega
        simpa only [OfKind,Fin.val_mk,if_neg h1,if_neg h2,he1,he2] using And.intro hh hb
      · refine ⟨⟨q+1+b,by omega⟩,?_⟩
        have h1 : ¬ q+1+b ≤ q := by omega
        have h2 : q+1+b ≤ 2*q+1 := by omega
        have he1 : q+1+b-(q+1)=b := by omega
        have he2 : q+1+b-q=b+1 := by omega
        simp only [OfKind,Fin.val_mk,if_neg h1,if_pos h2,he1,he2]
        exact ⟨hb,Or.inr hh⟩

theorem ofKind_count (q d : ℕ) (P G : ℕ → Prop) (k : Kind q)
    (hp : ∀ b, P b → d=b) (hg : ∀ b, G b → d=b+1) (hk : OfKind q P G k) :
    d=budget q k := by
  unfold OfKind at hk
  unfold budget
  split_ifs at hk ⊢ with h1 h2
  · exact hp _ hk.1
  · have h := hg _ hk.1
    omega
  · exact hp _ hk.1

theorem ofKind_high (q : ℕ) (P G : ℕ → Prop) (k : Kind q) (hk : OfKind q P G k) :
    (∃ b, P b) ∨ ∃ b, G b := by
  unfold OfKind at hk
  split_ifs at hk
  · exact Or.inl ⟨_,hk.1⟩
  · exact Or.inr ⟨_,hk.1⟩
  · exact Or.inl ⟨_,hk.1⟩

theorem budget_le (q : ℕ) (k : Kind q) : budget q k ≤ q+1 := by
  have hk := k.isLt
  unfold budget
  split_ifs <;> omega

theorem guard_iff (q d : ℕ) (P G : ℕ → Prop) (k : Kind q)
    (hp : ∀ b, P b → b ≤ q ∧ d=b)
    (hg : ∀ b, G b → b ≤ q ∧ d=b+1) (hk : OfKind q P G k) :
    (∃ b, G b) ↔ isGuard q k = true := by
  unfold OfKind at hk
  simp only [isGuard,decide_eq_true_eq]
  split_ifs at hk with h1 h2
  · constructor
    · rintro ⟨b,hb⟩
      obtain ⟨_,hdp⟩ := hp _ hk.1
      obtain ⟨_,hdg⟩ := hg _ hb
      rcases hk.2 with hz | hn
      · omega
      · have he : b=k.val-1 := by omega
        exact False.elim (hn (he ▸ hb))
    · omega
  · exact ⟨fun _ => by omega,fun _ => ⟨_,hk.1⟩⟩
  · exact ⟨fun _ => by omega,fun _ => ⟨_,hk.2⟩⟩

theorem positivePrefix_iff (q d b : ℕ) (P G : ℕ → Prop) (k : Kind q)
    (hp : ∀ c, P c → c ≤ q ∧ d=c)
    (hg : ∀ c, G c → c ≤ q ∧ d=c+1) (hk : OfKind q P G k) :
    (∃ c, c ≤ b ∧ P c) ↔ positivePrefix q b k = true := by
  unfold OfKind at hk
  simp only [positivePrefix,decide_eq_true_eq]
  split_ifs at hk with h1 h2
  · have hd := (hp _ hk.1).2
    constructor
    · rintro ⟨c,hcb,hc⟩
      have hdc := (hp _ hc).2
      exact Or.inl ⟨h1,by omega⟩
    · intro hh
      refine ⟨k.val,?_,hk.1⟩
      rcases hh with hh | hh <;> omega
  · constructor
    · rintro ⟨c,hcb,hc⟩
      have hdc := hp _ hc
      have hdg := hg _ hk.1
      rcases hk.2 with hz | hn
      · omega
      · have he : c=k.val-q := by omega
        exact False.elim (hn (he ▸ hc))
    · intro hh
      rcases hh with hh | hh <;> omega
  · have hd := (hp _ hk.1).2
    constructor
    · rintro ⟨c,hcb,hc⟩
      have hdc := (hp _ hc).2
      exact Or.inr ⟨by omega,by omega⟩
    · intro hh
      refine ⟨k.val-(2*q+1),?_,hk.1⟩
      rcases hh with hh | hh <;> omega

end ThreeBoundHighTypes

#print axioms ThreeBoundHighTypes.exists_kind
#print axioms ThreeBoundHighTypes.positivePrefix_iff
Source
Attached verified checkpoint block_sensitivity_three_bounds; lean_project/HighTypeCore.lean; original SHA-256 52f6a181be2fcb17f9b44bc27d99100f93c6edef7d4e31921bd74c65a489647b; 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