Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Block-0 gate instruction and pack-slot lemmas

Definition
IntMul_Kappa_R8_Data_BitOppbankBlock0CoreBLemmas

by Ethan Cheung Wang · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

bitnbblock0complexity-theoryinteger-multiplicationoppbankprefixqhnetrecrr8round-eight

Block-0 gate instruction and pack-slot lemmas

Instruction shape, nest-OK, MovesV at a single gate, and the correspondence between pack elements and slot-certificate records. Prefix / block-0 helper only; not a full-word W1F certificate.

Formalization Note

Lean definition name: IntMul_Kappa_R8_Data_BitOppbankBlock0CoreBLemmas.

Definition code
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankGenF
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankLab1
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankQHNetRecR
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankBlock0CoreAData
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankBlock0CoreABits
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankBlock0CoreACopy
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankBlock0CoreALeaf
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankBlock0CoreAState1
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankBlock0CoreAState2
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankBlock0CoreAState3a
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankBlock0CoreBData1
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankBlock0CoreBData2
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankBlock0CoreBDecPackBounds
import Definitions.Def_IntMul_Kappa_R8_Data_BitOppbankBlock0CoreBDecSlotMatch
import Mathlib.Data.Finset.Basic
import Mathlib.Data.Finset.Card
import Mathlib.Data.Finset.Max
import Mathlib.Tactic.ByCases
import Mathlib.Tactic.Ext

set_option autoImplicit false
set_option relaxedAutoImplicit false
set_option maxHeartbeats 8000000
set_option maxRecDepth 1000000
set_option linter.unusedSimpArgs false
set_option linter.unusedVariables false

/-!
Block-0 CoreB decide/proof split. Prefix / block-0 helper only; not a full-word W1F certificate.
-/

open IntMul.Kappa.R8.Bit.Oppbank
open IntMul.Kappa.R8.Bit.Oppbank.Gen (genF genStepF mvF)
open IntMul.Kappa.R8.Bit.Oppbank.Lab (ValidOn MovesV)
open IntMul.Kappa.R8.Bit.Oppbank.Pnd (nestOK argRel isND)
open IntMul.Kappa.R8.Bit.Oppbank.QHNetRecR

/-!
Block-0 gate instruction lemmas and pack/slot correspondence. Prefix / block-0 helper only; not a full-word W1F certificate.
-/

theorem gateAtOf_code (g : ℕ × ℕ × ℕ × ℕ × ℕ × ℕ) (start : ℕ) :
    (gateAtOf g start).1 = cND (gateN g) := rfl

theorem gateBp_ne_zero {g : ℕ × ℕ × ℕ × ℕ × ℕ × ℕ}
    (h : 1 ≤ gateBp g) : gateBp g ≠ 0 :=
  Nat.ne_of_gt (Nat.lt_of_succ_le h)

theorem gateAtOf_touch (g : ℕ × ℕ × ℕ × ℕ × ℕ × ℕ) (start : ℕ)
    (hbp : 1 ≤ gateBp g) :
    (gateAtOf g start).2.1 =
      [wS (gatePiv g), wS (gateBp g - 1)] ++
        (gateExtras g start).flatMap (fun o => [wS o, wS (gatePiv g)]) := by
  have hnz : gateBp g ≠ 0 := gateBp_ne_zero hbp
  simp [gateAtOf, mk, recEl, touch, gateExtras, hnz, List.flatMap_map]

theorem mem_gateAtOf_touch {g : ℕ × ℕ × ℕ × ℕ × ℕ × ℕ} {start x : ℕ}
    (hbp : 1 ≤ gateBp g) :
    x ∈ (gateAtOf g start).2.1 ↔
      x = wS (gatePiv g) ∨ x = wS (gateBp g - 1) ∨
        ∃ o ∈ List.range' start (gateNf g), x = wS o := by
  rw [gateAtOf_touch g start hbp]
  constructor
  · intro hx
    rcases List.mem_append.1 hx with h | h
    · simp only [List.mem_cons, List.mem_singleton, List.not_mem_nil, or_false] at h
      exact h.imp_right Or.inl
    · rcases List.mem_flatMap.1 h with ⟨o, ho, hx'⟩
      have : x = wS o ∨ x = wS (gatePiv g) := by
        simp only [List.mem_cons, List.mem_singleton, List.not_mem_nil, or_false] at hx'
        exact hx'
      rcases this with hxo | hxp
      · unfold gateExtras at ho
        rcases List.mem_cons.1 ho with hbp1 | hf
        · have : o = gateBp g - 1 := hbp1
          rw [this] at hxo
          exact Or.inr (Or.inl hxo)
        · exact Or.inr (Or.inr ⟨o, hf, hxo⟩)
      · exact Or.inl hxp
  · intro hx
    rcases hx with hxp | hxb | ⟨o, ho, hxo⟩
    · exact List.mem_append.2 (Or.inl (by simp [hxp]))
    · exact List.mem_append.2 (Or.inl (by simp [hxb]))
    · refine List.mem_append.2 (Or.inr ?_)
      refine List.mem_flatMap.2 ⟨o, ?_, ?_⟩
      · exact List.mem_cons.2 (Or.inr ho)
      · simp [hxo]


theorem exists_of_map_eq {α β γ : Type*} {A : List α} {B : List β}
    {f : α → γ} {g : β → γ} (h : A.map f = B.map g) {a : α} (ha : a ∈ A) :
    ∃ b ∈ B, f a = g b := by
  induction A generalizing B with
  | nil => cases ha
  | cons a' A ih =>
    cases B with
    | nil =>
      cases h
    | cons b' B =>
      simp only [List.map_cons, List.cons.injEq] at h
      simp only [List.mem_cons] at ha
      rcases ha with ha | ha
      · subst ha
        exact ⟨b', List.mem_cons.2 (Or.inl rfl), h.1⟩
      · rcases ih h.2 ha with ⟨b, hb, heq⟩
        exact ⟨b, List.mem_cons.2 (Or.inr hb), heq⟩

theorem exists_slot_of_pack {g : ℕ × ℕ × ℕ × ℕ × ℕ × ℕ} (hg : g ∈ gatePack) :
    ∃ p ∈ gateSlotCert,
      gateTp g = slotTp p ∧ gatePiv g = slotPiv p ∧
        gateTb g = slotTb p ∧ gateBp g - 1 = slotBp1 p := by
  rcases exists_of_map_eq gateSlotCert_matches_pack hg with ⟨p, hp, heq⟩
  refine ⟨p, hp, ?_⟩
  exact ⟨congrArg Prod.fst heq,
    congrArg (fun x => x.2.1) heq,
    congrArg (fun x => x.2.2.1) heq,
    congrArg (fun x => x.2.2.2) heq⟩

theorem nestOK_of_argRel_owners {t n : ℕ}
    (ht : t < v) (hn : n ≤ 20278) (harg : argRel t n = true) :
    nestOK (cND t) (cND n) = true := by
  have hv : v = 1771 := rfl
  have ht' : t < 62478 := by omega
  have hn' : n < 62478 := by omega
  exact nestOK_of_argRel_ND (isND_cND ht') (isND_cND hn') harg

theorem MovesV_gateAt (f : ℕ → ℕ) (g : ℕ × ℕ × ℕ × ℕ × ℕ × ℕ) (start : ℕ)
    (hbp : 1 ≤ gateBp g)
    (htp : gateTp g < v) (htb : gateTb g < v)
    (hP : f (wS (gatePiv g)) = cND (gateTp g))
    (hB : f (wS (gateBp g - 1)) = cND (gateTb g))
    (hF : ∀ o ∈ List.range' start (gateNf g), f (wS o) = 0)
    (hargP : argRel (gateTp g) (gateN g) = true)
    (hargB : argRel (gateTb g) (gateN g) = true)
    (hn : gateN g ≤ 20278)
    (hf : ∀ x, f x < SupG.codeBound) :
    MovesV (genF f [gateAtOf g start]).2 ∧
      ∀ x, (genF f [gateAtOf g start]).1 x < SupG.codeBound := by
  have hgen := genF_singleton f (gateAtOf g start)
  have hcode := gateAtOf_code g start
  have hcB : cND (gateN g) < SupG.codeBound := cND_lt_bound_of_le hn
  have hold := (foldl_mvF_old (cND (gateN g)) (gateAtOf g start).2.1 f).1
  have hmem := foldl_mvF_mem (cND (gateN g)) (gateAtOf g start).2.1 f
  rw [hgen, hcode]
  constructor
  · intro ch hch mv hmv
    simp only [List.mem_singleton] at hch
    subst ch
    have hmv' : mv ∈ ((gateAtOf g start).2.1.foldl (mvF (cND (gateN g))) (f, [])).2 :=
      List.mem_reverse.1 hmv
    have hold0 : mv.2 = f mv.1 := hold mv hmv'
    have hin := hmem mv hmv'
    have hcases := (mem_gateAtOf_touch (x := mv.1) hbp).1 hin
    rcases hcases with hxp | hrest
    · have holdv : mv.2 = cND (gateTp g) := by rw [hold0, hxp, hP]
      rw [holdv]
      exact ⟨nestOK_of_argRel_owners htp hn hargP, cND_lt_bound htp, hcB⟩
    · rcases hrest with hxb | hf
      · have holdv : mv.2 = cND (gateTb g) := by rw [hold0, hxb, hB]
        rw [holdv]
        exact ⟨nestOK_of_argRel_owners htb hn hargB, cND_lt_bound htb, hcB⟩
      · rcases hf with ⟨o, ho, hxo⟩
        have holdz : mv.2 = 0 := by rw [hold0, hxo]; exact hF o ho
        rw [holdz]
        refine ⟨nestOK_of_le1 (Or.inl (Nat.zero_le 1)), ?_, hcB⟩
        have : SupG.codeBound = 64251 := SupG.codeBound_eq
        omega
  · intro x
    have hx := (foldl_mvF_old (cND (gateN g)) (gateAtOf g start).2.1 f).2 x
    rcases hx with hx | hx
    · rw [hx]; exact hf x
    · rw [hx]; exact hcB


theorem gate_bounds_of_mem {g : ℕ × ℕ × ℕ × ℕ × ℕ × ℕ} (hg : g ∈ gatePack) :
    gatePiv g < leafSlotBound ∧
      1 ≤ gateBp g ∧ gateBp g - 1 < leafSlotBound ∧
      gateNf g ≤ 5 ∧
      gateTp g < v ∧ gateTb g < v ∧
      gateN g ≤ 20278 := by
  have h := gatePack_simple_bounds g hg
  have hv : v = 1771 := rfl
  have hb : leafSlotBound = 11099 := rfl
  refine ⟨?_, h.2.1, ?_, h.2.2.2.1, ?_, ?_, h.2.2.2.2.2.2⟩
  · exact hb ▸ h.1
  · exact hb ▸ h.2.2.1
  · exact hv ▸ h.2.2.2.2.1
  · exact hv ▸ h.2.2.2.2.2.1

Source
IntMul Kappa R8 Bit Oppbank FormalOK: IntMul_Kappa_R8_Data_BitOppbankBlock0CoreBLemmas split. Prefix / block-0 helper only; not a full-word W1F certificate.

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