Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Assembling the tiered RAM rows and checks

Definition
CNFEncComplexity_RobsonMemoryTierRowAssembly

by bersubs · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorysatisfiability

Combines local emission gates over the dyadic layout and uses disjoint auxiliary names for the window checks of every tier.

Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryTierRowGates

set_option maxHeartbeats 4000000
set_option linter.all false

/- RobsonAllTiers -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

/-- All tiers read the same low. Their scratch variables occupy distinct residue classes. -/
def memoryTierWire (low levels j r : ℕ) : ℕ :=
  if r < low then r else low+levels*(r-low)+j

def memoryTierGates (t low z o : ℕ) (src : ℕ → ℕ → ℕ → ℕ) (j : ℕ) : List Gate :=
  (tierBatchGates (memoryTierRows t j) (2^j) j low z o (src j)).map
    (Gate.rename (memoryTierWire low (emitLevels t) j))

def allMemoryTierGates (t low z o : ℕ) (src : ℕ → ℕ → ℕ → ℕ) : List Gate :=
  (List.range (emitLevels t)).flatMap (memoryTierGates t low z o src)

private theorem memoryTier_pull {low levels j : ℕ} (hj : j < levels)
    (a : Assignment) (b : ℕ → Assignment)
    (hKeep : ∀ j < levels, ∀ r < low, b j r = a r) :
    (fun k => if k < low then a k
      else b ((k-low)%levels) (low+(k-low)/levels)) ∘
      memoryTierWire low levels j = b j := by
  funext r
  by_cases hr : r < low
  · simp [memoryTierWire,Function.comp_def,hr,hKeep j hj r hr]
  · have hpre : low ≤ r := by omega
    have hn : ¬ low+levels*(r-low)+j < low := by omega
    have hsub : low+levels*(r-low)+j-low = levels*(r-low)+j := by omega
    have hm : (levels*(r-low)+j)%levels = j := by
      rw [Nat.mul_add_mod, Nat.mod_eq_of_lt hj]
    have hd : (levels*(r-low)+j)/levels = r-low := by
      rw [Nat.mul_add_div (Nat.zero_lt_of_lt hj),Nat.div_eq_of_lt hj,Nat.add_zero]
    simp [memoryTierWire,Function.comp_def,hr,hn,hsub,hm,hd,Nat.add_sub_of_le hpre]

theorem allMemoryTierGates_exact (t low z o : ℕ) (src : ℕ → ℕ → ℕ → ℕ) (a : Assignment)
    (hzKey : z < low) (hoKey : o < low) (hz : a z = false) (ho : a o = true)
    (hSrc : ∀ j < emitLevels t, ∀ i < memoryTierRows t j, ∀ k < memLaneWidth (2^j) 0,
      src j i k < low) :
    ExtendsWith low (allMemoryTierGates t low z o src) a ↔
      ∀ j < emitLevels t, TierBatchCertificate (memoryGroupCap j) (memoryGroupCount t j)
        (rawMemoryRows a (2^j) (memoryTierRows t j) (src j)) (groupInitial (some j)) := by
  classical
  constructor
  · rintro ⟨b,hKeep,hG⟩ j hj
    let c := b ∘ memoryTierWire low (emitLevels t) j
    have hPre (r : ℕ) (hr : r < low) : c r = a r := by simpa [c,Function.comp_def,memoryTierWire,hr] using hKeep r hr
    have hSat : ∀ g ∈ tierBatchGates (memoryTierRows t j) (2^j) j low z o (src j), g.Holds c := by
      apply (renamedCircuit_correct _ _ _).1
      intro g hg
      exact hG g (List.mem_flatMap.mpr ⟨j,List.mem_range.mpr hj,hg⟩)
    have hc := tierBatchGates_sound _ _ _ _ _ _ _ _
      ((hPre z hzKey).trans hz) ((hPre o hoKey).trans ho) (bitTier_initial_restricted j) hSat
    apply (sorterTierCertificate_eq ..).1
    unfold sorterTierCertificate at hc ⊢
    rwa [sorterRawRows_congr _ _ _ c a (fun i hi k hk => hPre _ (hSrc j hj i hi k hk))] at hc
  · intro h
    have hExt (j : ℕ) :
      ∃ b : Assignment, (∀ r < low, b r = a r) ∧
        (j < emitLevels t → ∀ g ∈ tierBatchGates (memoryTierRows t j) (2^j) j low z o (src j), g.Holds b) := by
      by_cases hj : j < emitLevels t
      · obtain ⟨b,hKeep,hG⟩ := (tierBatch_mission_certificate t j low z o (src j) a
          hzKey hoKey (hSrc j hj) hz ho).2 (h j hj)
        exact ⟨b,fun r hr => hKeep r (.inl hr),fun _ => hG⟩
      · exact ⟨a,fun _ _ => rfl,fun hj' => (hj hj').elim⟩
    choose b hKeep hG using hExt
    let c : Assignment := fun k => if k < low then a k
      else b ((k-low)%emitLevels t) (low+(k-low)/emitLevels t)
    refine ⟨c,fun r hr => by simp [c,hr],?_⟩
    intro g hg
    obtain ⟨j,hj,hg⟩ := List.mem_flatMap.mp hg
    apply (renamedCircuit_correct _ _ _).2 _ g hg
    rw [show c ∘ memoryTierWire low (emitLevels t) j = b j from
      memoryTier_pull (List.mem_range.mp hj) a b (fun j _ => hKeep j)]
    exact hG j (List.mem_range.mp hj)

theorem allMemoryTierGates_length (t low z o : ℕ) (src : ℕ → ℕ → ℕ → ℕ) :
    (allMemoryTierGates t low z o src).length ≤
      1572864*layoutHorizon t*(trieWidth t+1)+786432*layoutHorizon t := by
  have flatLength (xs : List ℕ) :
      (xs.flatMap (memoryTierGates t low z o src)).length =
        (xs.map (fun j => (tierBatchGates (memoryTierRows t j) (2^j) j low z o (src j)).length)).sum := by
    induction xs with
    | nil => rfl
    | cons j js ih => simp [ih, memoryTierGates, List.flatMap_cons]
  unfold allMemoryTierGates
  rw [flatLength]
  have sumRange (f : ℕ → ℕ) (n : ℕ) :
      ((List.range n).map f).sum = ∑ j ∈ Finset.range n, f j := by
    induction n with
    | zero => simp
    | succ n ih => rw [List.range_succ,List.map_append,List.sum_append,Finset.sum_range_succ,← ih]; simp
  rw [sumRange]
  exact tierBatchGates_total_budget t (trieWidth t) _ fun j _ =>
    tierBatchGates_layout_budget _ _ _ _ _ _

section NativeTiers
variable {A : Type} {e : A ↪ List Bool}

private theorem memoryTierWire_poly {low levels j r : A → ℕ}
    (hL : ComputableTidilyInPolyTime low e encUnary)
    (hC : ComputableTidilyInPolyTime levels e encUnary)
    (hJ : ComputableTidilyInPolyTime j e encUnary)
    (hR : ComputableTidilyInPolyTime r e encUnary) :
    ComputableTidilyInPolyTime (fun x => memoryTierWire (low x) (levels x) (j x) (r x)) e encUnary := by
  have h1 := unary_sub.comp (hR.prod hL)
  have h2 := unary_mul.comp (hC.prod h1)
  have h3 := unary_add.comp (hL.prod h2)
  have h4 := unary_add.comp (h3.prod hJ)
  simpa only [memoryTierWire, decide_eq_true_eq, Function.comp_def] using (unary_lt' hR hL).ite' hR h4

def boundedMemoryTierWidth (t j : ℕ) : ℕ := 2^(min j (emitLevels t-1))

theorem boundedMemoryTierWidth_eq {t j : ℕ} (hj : j < emitLevels t) :
    boundedMemoryTierWidth t j = 2^j := by
  rw [boundedMemoryTierWidth, min_eq_left (by omega)]

private theorem memoryTierLevels_poly : ComputableTidilyInPolyTime emitLevels encUnary encUnary := by
  have hB := unary_add.comp (trieWidth_poly.prod (const 1))
  have hC := unary_size_poly.comp hB
  exact unary_add.comp (hC.prod (const 1))

theorem boundedMemoryTierWidth_poly {t j : A → ℕ}
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hJ : ComputableTidilyInPolyTime j e encUnary) :
    ComputableTidilyInPolyTime (fun a => boundedMemoryTierWidth (t a) (j a)) e encUnary := by
  have hLim := unary_sub.comp ((memoryTierLevels_poly.comp hT).prod (const 1))
  have hMin := unary_min.comp (hJ.prod hLim)
  have hH := unary_add.comp ((layoutHorizon_poly.comp hT).prod (const 1))
  have hB := unary_add.comp ((unary_mul.comp ((const 2).prod hH)).prod (const 17))
  apply unary_pow2_of_bound hMin hB
  intro a
  have hPos : 0 < emitLevels (t a) := Nat.succ_pos _
  have hm : min (j a) (emitLevels (t a)-1) < emitLevels (t a) :=
    lt_of_le_of_lt (min_le_right _ _) (by omega)
  have h := emitBlockWidth_bound hm
  change 2^(min (j a) (emitLevels (t a)-1)) ≤ 2*(layoutHorizon (t a)+1)+17
  unfold emitBlockStride at h
  omega

private def boundedMemoryTierGates (t low z o : ℕ) (src : ℕ → ℕ → ℕ → ℕ) (j : ℕ) : List Gate :=
  (tierBatchGates (memoryTierRows t j) (boundedMemoryTierWidth t j) j low z o (src j)).map
    (Gate.rename (memoryTierWire low (emitLevels t) j))

theorem allMemoryTierGates_poly {t low z o : A → ℕ} {src : A → ℕ → ℕ → ℕ → ℕ}
    (hT : ComputableTidilyInPolyTime t e encUnary)
    (hL : ComputableTidilyInPolyTime low e encUnary)
    (hZ : ComputableTidilyInPolyTime z e encUnary)
    (hO : ComputableTidilyInPolyTime o e encUnary)
    (hR : ComputableTidilyInPolyTime (fun q : A×ℕ => memoryTierRows (t q.1) q.2)
      (encPair e encUnary) encUnary)
    (hSrc : ComputableTidilyInPolyTime (fun q : ((A×ℕ)×ℕ)×ℕ => src q.1.1.1 q.1.1.2 q.1.2 q.2)
      (encPair (encPair (encPair e encUnary) encUnary) encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun a => allMemoryTierGates (t a) (low a) (z a) (o a) (src a))
      e (encList gateEnc) := by
  let ep := encPair e encUnary
  have hA := fst e encUnary
  have hJ := snd e encUnary
  have hLv := memoryTierLevels_poly.comp hT
  have hGs := tierBatchGates_polytime (A := A×ℕ) (e := ep)
    (src := fun q => src q.1 q.2) hR (boundedMemoryTierWidth_poly (hT.comp hA) hJ) hJ
    (hL.comp hA) (hZ.comp hA) (hO.comp hA) hSrc
  have hPr := fst ep encUnary
  have hName : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ =>
      memoryTierWire (low p.1.1) (emitLevels (t p.1.1)) p.1.2 p.2) (encPair ep encUnary) encUnary :=
    memoryTierWire_poly (hL.comp (hA.comp hPr)) (hLv.comp (hA.comp hPr))
      (hJ.comp hPr) (snd ep encUnary)
  have hMap : ComputableTidilyInPolyTime (fun q : A×ℕ =>
      boundedMemoryTierGates (t q.1) (low q.1) (z q.1) (o q.1) (src q.1) q.2)
      ep (encList gateEnc) :=
    mapWithInput hGs (gateRename_poly (e:=ep)
      (name:=fun p => memoryTierWire (low p.1) (emitLevels (t p.1)) p.2) hName)
  have result := flatMapWithInput (f := fun a j =>
    boundedMemoryTierGates (t a) (low a) (z a) (o a) (src a) j)
    (range.comp hLv) hMap
  convert result using 1
  funext a
  unfold allMemoryTierGates
  apply List.flatMap_congr
  intro j hj
  rw [boundedMemoryTierGates,boundedMemoryTierWidth_eq (List.mem_range.mp hj),memoryTierGates]

end NativeTiers
end CNFEncComplexity.Robson

/- RobsonEmitBank -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

abbrev EmitLane := (ℕ×ℕ)×ℕ×Bool

def emitLaneList (slots : List (ℕ×ℕ)) : List EmitLane :=
  slots.flatMap fun s => (List.range 3).flatMap (fun r => [(s,r,false),(s,r,true)])

theorem emitLaneList_length (slots : List (ℕ×ℕ)) :
    (emitLaneList slots).length = 6*slots.length := by
  induction slots with
  | nil => rfl
  | cons s ss ih =>
    simp only [emitLaneList,List.flatMap_cons,List.length_append,List.length_cons]
    have ht : (List.flatMap (fun r => [(s,r,false),(s,r,true)]) (List.range 3)).length=6 := rfl
    rw [ht,show (List.flatMap (fun s => List.flatMap (fun r => [(s,r,false),(s,r,true)]) (List.range 3))
        ss).length = (emitLaneList ss).length from rfl,ih]
    omega

theorem emitLaneList_members {xs : List (ℕ×ℕ)} {s : ℕ×ℕ} {i : ℕ} {k : Bool}
    (h : (s,i,k) ∈ emitLaneList xs) : s∈xs ∧ i < 3 := by
  obtain ⟨u,hu,ha⟩ := List.mem_flatMap.mp h
  obtain ⟨b,hb,hc⟩ := List.mem_flatMap.mp ha
  simp only [List.mem_cons,List.not_mem_nil,or_false,Prod.mk.injEq] at hc
  rcases hc with ⟨rfl,rfl,rfl⟩|⟨rfl,rfl,rfl⟩
  · exact ⟨hu,List.mem_range.mp hb⟩
  · exact ⟨hu,List.mem_range.mp hb⟩

def emitLaneKey (base region n t j z o : ℕ) (p : EmitLane) : ℕ→ℕ :=
  let u := emitInputs base n t p.1 p.2.1
  let start := emitBlockBase region t j p.1 p.2.1+8
  if p.2.2 then emitSecondRow u (2^j) z o start else emitFirstRow u (2^j) z o start

def emitSource (base region n t j z o : ℕ) (slots : List (ℕ×ℕ)) (k : ℕ) : ℕ→ℕ :=
  match (emitLaneList slots)[k]? with
  | none => fun _ => z
  | some p => emitLaneKey base region n t j z o p

private theorem mapIndex_source {A B : Type} (l : List A) (f : A→B) (default : B) :
    ((List.range l.length).map (fun i => (l[i]?.map f).getD default)) = l.map f := by
  apply List.ext_getElem
  · simp
  · intro i hi hj
    have hi' : i < l.length := by simpa using hi
    simp only [List.getElem_map,List.getElem_range,List.getElem?_eq_getElem hi',Option.map_some,Option.getD_some]

def compactSlotOptions (a : Assignment) (base n t : ℕ) (s : ℕ×ℕ) : List (Option ObservedAccess) :=
  (List.range 3).map (slotCompactMemory a base n t (trieLevel t) s)

theorem compactSlotOptions_filter (a : Assignment) (base n t : ℕ) (s : ℕ×ℕ) :
    (compactSlotOptions a base n t s).filterMap id =
      slotCompactRows a base n t (trieLevel t) s := by
  simp [compactSlotOptions,slotCompactRows,List.filterMap_map,Function.comp_def]

theorem emitBank_exact (a : Assignment) (base region n t j z o : ℕ) (slots : List (ℕ×ℕ))
    (hz : a z=false) (ho : a o=true)
    (hWidth : ∀ s ∈ slots, ∀ r < 3, (emitFlags region t s r).valid (emitInputs base n t s r) a)
    (hCore : GateSat a (emitTierGateList base region n t j z slots)) :
    rawMemoryRows a (2^j) (6*slots.length) (emitSource base region n t j z o slots) =
      slots.flatMap (fun s => (compactSlotOptions a base n t s).flatMap (emitTier j)) := by
  let ds := emitLaneList slots
  let decode := fun p => laneRecord a (2^j) 0 (emitLaneKey base region n t j z o p)
  have hLen : ds.length = 6*slots.length := emitLaneList_length slots
  have he : rawMemoryRows a (2^j) (6*slots.length) (emitSource base region n t j z o slots) =
      ds.map decode := by
    unfold rawMemoryRows
    rw [← hLen]
    have hh : ∀ i : ℕ, laneRecord a (2^j) 0 (emitSource base region n t j z o slots i) =
        ((ds[i]?).map decode).getD none := by
      intro i
      unfold emitSource
      change laneRecord a (2^j) 0 (match ds[i]? with
        | none => fun _ => z | some p => emitLaneKey base region n t j z o p) = _
      cases ds[i]? <;> simp [laneRecord,laneActive,hz,decode]
    simp_rw [hh]
    exact mapIndex_source ds decode _
  rw [he]
  unfold ds emitLaneList
  rw [List.map_flatMap]
  apply List.flatMap_congr
  intro s hs
  rw [List.map_flatMap,compactSlotOptions,List.flatMap_map]
  apply List.flatMap_congr
  intro r hr
  have hr' := List.mem_range.mp hr
  have hG : GateSat a (emitOne base region n t j z s r) := by
    intro g hg
    exact hCore g (List.mem_flatMap.mpr ⟨s,hs,List.mem_flatMap.mpr ⟨r,hr,hg⟩⟩)
  have hql := EmitInput.coreGates_sound (emitInputs base n t s r) (emitFlags region t s r) a j z o
    (emitBlockBase region t j s r) hz ho (hWidth s hs r hr') hG
  simp only [List.map_cons,List.map_nil,Function.comp_apply]
  rw [← emitInputs_eq a base n t s r]
  exact hql

end CNFEncComplexity.Robson

/- RobsonMemoryEmitFrame -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

/-- Install local assignments in separate, equally sized scratch intervals. -/
theorem emitBank_assembleBlocks {I : Type} (a : Assignment) (base top stride count : ℕ)
    (index : I → ℕ) (hi : Function.Injective index) (hc : ∀ k, index k < count)
    (ht : base+count*stride ≤ top) (gates : I → List Gate)
    (frame : ∀ k, GateFrame (gates k) base
      (base+index k*stride) (base+index k*stride+stride))
    (extend : ∀ k, ∃ b, Keeps a b (base+index k*stride) (base+index k*stride+stride) ∧
      GateSat b (gates k)) :
    ∃ b, Keeps a b base top ∧ ∀ k, GateSat b (gates k) := by
  classical
  choose witness hw hs using extend
  let lower : I → ℕ := fun k => base+index k*stride
  let upper : I → ℕ := fun k => lower k+stride
  have hordered (k k' : I) (h : index k < index k') : upper k ≤ lower k' := by
    have hm := Nat.mul_le_mul_right stride (Nat.succ_le_of_lt h)
    rw [Nat.succ_eq_add_one,Nat.add_mul,Nat.one_mul] at hm
    unfold upper lower
    omega
  have hbounds (k : I) : base ≤ lower k ∧ upper k ≤ top := by
    refine ⟨Nat.le_add_right ..,?_⟩
    have hm := Nat.mul_le_mul_right stride (Nat.succ_le_of_lt (hc k))
    rw [Nat.succ_eq_add_one,Nat.add_mul,Nat.one_mul] at hm
    exact (show upper k ≤ base+count*stride by
      unfold upper lower
      omega).trans ht
  let covers (i : ℕ) (k : I) : Prop := lower k ≤ i ∧ i < upper k
  have hunique {i : ℕ} {k k' : I} (hk : covers i k) (hk' : covers i k') : k=k' := by
    apply hi
    rcases lt_trichotomy (index k) (index k') with h|h|h
    · exact False.elim (Nat.not_lt_of_ge ((hordered k k' h).trans hk'.1) hk.2)
    · exact h
    · exact False.elim (Nat.not_lt_of_ge ((hordered k' k h).trans hk.1) hk'.2)
  let b : Assignment := fun i => if h : ∃ k, covers i k then witness h.choose i else a i
  have hkeep : Keeps a b base top := by
    intro i hi
    have hnone : ¬∃ k, covers i k := by
      rintro ⟨k,hk⟩
      have ⟨hl,hu⟩ := hbounds k
      have ⟨hki,hik⟩ := hk
      omega
    simp [b,hnone]
  refine ⟨b,hkeep,fun k => (hs k).congr_framed (frame k) ?_⟩
  intro i hi
  rcases hi with hi|hi
  · exact (hw k i (.inl (hi.trans_le (hbounds k).1))).trans (hkeep i (.inl hi)).symm
  · have hEx : ∃ j, covers i j := ⟨k,hi⟩
    have heq : hEx.choose = k := hunique hEx.choose_spec hi
    simp [b,hEx,heq]

theorem emitWidthCircuit_frame (common lo w : ℕ) (key : ℕ → ℕ)
    (hkey : ∀ i < w, key i < common) :
    GateFrame (widthCircuit lo w key) common lo (lo+w+1) := by
  intro g hg i hi
  rcases List.mem_cons.mp hg with rfl|hg
  · simp only [RobsonCNF.Gate.names,List.mem_singleton] at hi
    subst i
    exact .inr ⟨by unfold widthFlagWire; omega,by unfold widthFlagWire; omega⟩
  · obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hg
    have hj' := List.mem_range.mp hj
    simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hi
    rcases hi with rfl|rfl|rfl
    · exact .inr ⟨by unfold widthFlagWire; omega,by unfold widthFlagWire; omega⟩
    · exact .inl (hkey _ hj')
    · exact .inr ⟨by unfold widthFlagWire; omega,by unfold widthFlagWire; omega⟩

theorem emitNormalizeLabel_lt {base t region : ℕ} (n : ℕ)
    (hregion : normalizeAfter base t ≤ region) {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
    {r f : ℕ} (hr : r < 3) (hf : f < 3) {i : ℕ} (hi : i < normalizeWidth (trieLevel t) s) :
    (normalizeSlotWires base n t (trieLevel t) s r f).label i < region := by
  let k : NormalizeKey t := (⟨s,hs⟩,⟨r,hr⟩,⟨f,hf⟩)
  exact (normalizeWordFrame_label base n t (trieLevel t) s r f hs i hi).2.trans_le
    ((normalizeKeyBase_range base t k).2.trans hregion)

abbrev EmitWidthBlock (t : ℕ) := {s : ℕ×ℕ // s ∈ layoutSlots t} × Fin 3 × Fin 3

theorem emitWidthLayout_frame {base region n t : ℕ} (hregion : normalizeAfter base t ≤ region) :
    GateFrame (emitWidthLayoutGates base region n t) region region (emitFlagTop region t) := by
  intro g hg i hi
  obtain ⟨s,hs,r,hr,f,hf,hg⟩ := by
    simpa only [emitWidthLayoutGates,List.mem_flatMap,List.mem_range] using hg
  have hb := emitFlagBlock_bounds (base:=region) hs hr hf
  have hwidth := emitFlagWidth_bound hs
  have hW := emitWidthCircuit_frame region (emitFlagBase region t s r f)
    (normalizeWidth (trieLevel t) s) (normalizeSlotWires base n t (trieLevel t) s r f).label
    (fun _ hi => emitNormalizeLabel_lt n hregion hs hr hf hi)
  exact (hW.mono le_rfl hb.1 (by omega)) g hg i hi

theorem emitWidthLayout_extend {base region n t : ℕ} (a : Assignment)
    (hregion : normalizeAfter base t ≤ region) :
    ∃ b, Keeps a b region (emitFlagTop region t) ∧ GateSat b (emitWidthLayoutGates base region n t) := by
  let index : EmitWidthBlock t → ℕ := fun ⟨s,r,f⟩ => emitFlagIndex t s r f
  let gates : EmitWidthBlock t → List Gate := fun ⟨s,r,f⟩ => emitWidthGates base region n t s r f
  have hu : Function.Injective index := by
    intro ⟨s,r,f⟩ ⟨s',r',f'⟩ h
    obtain ⟨h₁,h₂,h₃⟩ := emitFlagIndex_injective s.property s'.property
      r.isLt r'.isLt f.isLt f'.isLt h
    exact Prod.ext (Subtype.ext h₁) (Prod.ext (Fin.ext h₂) (Fin.ext h₃))
  have hc (k : EmitWidthBlock t) : index k < 9*emitSlotSpan t := by
    rcases k with ⟨s,r,f⟩
    have h := emitSlotIndex_bound s.property
    have hr := r.isLt
    have hf := f.isLt
    change emitFlagIndex t s r f < _
    unfold emitFlagIndex
    omega
  have frame (k : EmitWidthBlock t) :
      GateFrame (gates k) region (region+index k*emitFlagStride t)
        (region+index k*emitFlagStride t+emitFlagStride t) := by
    rcases k with ⟨s,r,f⟩
    have hwidth := emitFlagWidth_bound s.property
    exact (emitWidthCircuit_frame region (emitFlagBase region t s r f)
      (normalizeWidth (trieLevel t) s) (normalizeSlotWires base n t (trieLevel t) s r f).label
      (fun _ hi => emitNormalizeLabel_lt n hregion s.property r.isLt f.isLt hi)).mono
        le_rfl le_rfl (by
          change emitFlagBase region t s r f+normalizeWidth (trieLevel t) s+1 ≤
            emitFlagBase region t s r f+emitFlagStride t
          omega)
  have extend (k : EmitWidthBlock t) :
      ∃ b, Keeps a b (region+index k*emitFlagStride t)
        (region+index k*emitFlagStride t+emitFlagStride t) ∧ GateSat b (gates k) := by
    rcases k with ⟨s,r,f⟩
    have hbounds := emitFlagBlock_bounds (base:=region) s.property r.isLt f.isLt
    have hwidth := emitFlagWidth_bound s.property
    obtain ⟨b,hb,hg⟩ := widthCircuit_extends_interval (emitFlagBase region t s r f)
      (normalizeWidth (trieLevel t) s) (normalizeSlotWires base n t (trieLevel t) s r f).label a
      (fun _ hi => (emitNormalizeLabel_lt n hregion s.property r.isLt f.isLt hi).trans_le hbounds.1)
    refine ⟨b,fun i hi => hb i ?_,hg⟩
    change i < emitFlagBase region t s r f ∨ emitFlagBase region t s r f+emitFlagStride t ≤ i at hi
    omega
  obtain ⟨b,hk,hb⟩ := emitBank_assembleBlocks a region (emitFlagTop region t) (emitFlagStride t)
    (9*emitSlotSpan t) index hu hc (by rfl) gates frame extend
  refine ⟨b,hk,fun g hg => ?_⟩
  obtain ⟨s,hs,r,hr,f,hf,hg⟩ := by
    simpa only [emitWidthLayoutGates,List.mem_flatMap,List.mem_range] using hg
  exact hb (⟨s,hs⟩,⟨r,hr⟩,⟨f,hf⟩) g hg

theorem emitWidthLayout_valid {a : Assignment} {base region n t : ℕ}
    (h : GateSat a (emitWidthLayoutGates base region n t)) {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
    {r : ℕ} (hr : r < 3) :
    (emitFlags region t s r).valid (emitInputs base n t s r) a := by
  have hG (f : ℕ) (hf : f < 3) : GateSat a (emitWidthGates base region n t s r f) := by
    intro g hg
    apply h g
    simp only [emitWidthLayoutGates,List.mem_flatMap,List.mem_range]
    exact ⟨s,hs,r,hr,f,hf,hg⟩
  exact ⟨hG 0 (by decide),hG 1 (by decide),hG 2 (by decide)⟩

theorem emitFlagQuery_lt {region t : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
    {r f : ℕ} (hr : r < 3) (hf : f < 3) (k : ℕ) :
    tierAbove (normalizeWidth (trieLevel t) s) (emitFlagBase region t s r f) k < emitFlagTop region t := by
  have hp := emitFlagWidth_bound hs
  have hb := (emitFlagBlock_bounds (base:=region) hs hr hf).2
  have hk := min_le_left (normalizeWidth (trieLevel t) s) k
  unfold tierAbove widthFlagWire
  omega

theorem emitBlock_bounds {region t j r : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
    (hj : j < emitLevels t) (hr : r < 3) :
    emitFlagTop region t ≤ emitBlockBase region t j s r ∧
    emitBlockBase region t j s r+emitBlockStride t ≤ emitBlockTop region t := by
  have hm := Nat.mul_le_mul_right (emitBlockStride t)
    (Nat.succ_le_of_lt (emitBlockIndex_bound hs hj hr))
  rw [Nat.succ_eq_add_one,Nat.add_mul,Nat.one_mul] at hm
  unfold emitBlockBase emitBlockTop
  omega

theorem EmitInput.coreGates_frame (u : EmitInput) (f : EmitFlags) (j z common b : ℕ)
    (_hc : common ≤ b) (hz : z < common) (hl : u.live < common) (hw : u.writes < common)
    (ha : ∀ k, tierAbove u.width f.addr k < common)
    (hv : ∀ k, tierAbove u.width f.value k < common)
    (ho : ∀ k, tierAbove u.width f.old k < common)
    (ho' : ∀ i < u.width, u.old i < common) (hv' : ∀ i < u.width, u.value i < common) :
    GateFrame (u.coreGates f j z b) common b (b+16+2^j) := by
  have hp := Nat.two_pow_pos j
  have frame (d x y : ℕ) (hd : d ≤ 4)
      (hx : ∀ k, tierAbove u.width x k < common) (hy : ∀ k, tierAbove u.width y k < common) :
      GateFrame (tierTestGates j x y u.width (b+d)) common b (b+16+2^j) := by
    intro g hg r hr
    rcases tierTestGates_names j u.width x y (b+d) g hg r hr with hh|⟨k,rfl⟩|⟨k,rfl⟩
    · exact .inr ⟨by omega,by omega⟩
    · exact .inl (hx k)
    · exact .inl (hy k)
  have htest1 := frame 0 f.addr f.old (by decide) ha ho
  have htest2 := frame 4 f.addr f.value (by decide) ha hv
  let src := tierTestOutput j b
  let dst := tierTestOutput j (b+4)
  have hsrc : b ≤ src ∧ src < b+8 := by unfold src tierTestOutput; split <;> omega
  have hdst : b ≤ dst ∧ dst < b+8 := by unfold dst tierTestOutput; split <;> omega
  have hctrl : GateFrame (emissionControl (b+8) u.live u.writes src dst) common b (b+16+2^j) := by
    intro g hg r hr
    simp only [emissionControl,List.mem_cons,List.not_mem_nil,or_false] at hg
    rcases hg with rfl|rfl|rfl|rfl|rfl|rfl|rfl|rfl <;>
      simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hr <;> omega
  have padded (f : ℕ→ℕ) (h : ∀ i < u.width, f i < common) (i : ℕ) :
      paddedKey u.width z f i < common := by
    unfold paddedKey
    split
    · exact h _ ‹_›
    · exact hz
  have hmux : GateFrame
      (emissionMux (b+8) (2^j) u.writes (paddedKey u.width z u.old) (paddedKey u.width z u.value))
      common b (b+16+2^j) := by
    intro g hg r hr
    obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
    have hi' := List.mem_range.mp hi
    have hol := padded u.old ho' i
    have hvl := padded u.value hv' i
    simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hr
    omega
  simp only [EmitInput.coreGates,GateFrame.append]
  exact ⟨⟨⟨by simpa only [Nat.add_zero] using htest1,htest2⟩,hctrl⟩,hmux⟩

theorem emitInputs_flags_lt {base n t : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
    {r : ℕ} (hr : r < 3) :
    (emitInputs base n t s r).live < sharedLimit n t ∧
    (emitInputs base n t s r).writes < sharedLimit n t := by
  rcases s with ⟨s,k⟩
  obtain ⟨hs,hk,_⟩ := layout_mem.mp hs
  exact ⟨port_lt_shared hs hk (by omega) (Nat.two_pow_pos _),
    port_lt_shared hs hk (by omega) (Nat.two_pow_pos _)⟩

theorem emitInputs_label_lt {base region n t : ℕ}
    (h : normalizeAfter base t ≤ region) {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
    {r : ℕ} (hr : r < 3) :
    let u := emitInputs base n t s r
    (∀ i < u.width, u.address i < region) ∧ (∀ i < u.width, u.value i < region) ∧
      (∀ i < u.width, u.old i < region) :=
  ⟨fun _ hi => emitNormalizeLabel_lt n h hs hr (by decide : 0 < 3) hi,
   fun _ hi => emitNormalizeLabel_lt n h hs hr (by decide : 1 < 3) hi,
   fun _ hi => emitNormalizeLabel_lt n h hs hr (by decide : 2 < 3) hi⟩

theorem emitOne_local_frame {base region n t j z : ℕ}
    (hreg : normalizeAfter base t ≤ region) (hshared : sharedLimit n t ≤ region)
    (hz : z < region) {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
    {r : ℕ} (hr : r < 3) (hj : j < emitLevels t) :
    GateFrame (emitOne base region n t j z s r) (emitFlagTop region t)
      (emitBlockBase region t j s r) (emitBlockBase region t j s r+emitBlockStride t) := by
  have hreg' : region ≤ emitFlagTop region t := by unfold emitFlagTop; omega
  obtain ⟨hl,hw⟩ := emitInputs_flags_lt (base:=base) (n:=n) hs hr
  obtain ⟨ha,hv,ho⟩ := emitInputs_label_lt (n:=n) hreg hs hr
  have hb := emitBlock_bounds (region:=region) hs hj hr
  have h := EmitInput.coreGates_frame (emitInputs base n t s r) (emitFlags region t s r)
    j z (emitFlagTop region t) (emitBlockBase region t j s r) hb.1 (hz.trans_le hreg')
    ((hl.trans_le hshared).trans_le hreg') ((hw.trans_le hshared).trans_le hreg')
    (emitFlagQuery_lt (region:=region) hs hr (by decide : 0 < 3))
    (emitFlagQuery_lt (region:=region) hs hr (by decide : 1 < 3))
    (emitFlagQuery_lt (region:=region) hs hr (by decide : 2 < 3))
    (fun i hi => (ho i hi).trans_le hreg') (fun i hi => (hv i hi).trans_le hreg')
  exact h.mono le_rfl le_rfl (by have q := emitBlockWidth_bound hj; omega)

theorem emitOne_local_extend {base region n t j z : ℕ} (a : Assignment)
    (hreg : normalizeAfter base t ≤ region) (hshared : sharedLimit n t ≤ region)
    (hz : z < region) {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
    {r : ℕ} (hr : r < 3) (hj : j < emitLevels t) :
    ∃ b, Keeps a b (emitBlockBase region t j s r)
        (emitBlockBase region t j s r+emitBlockStride t) ∧ GateSat b (emitOne base region n t j z s r) := by
  have hreg' : region ≤ emitFlagTop region t := by unfold emitFlagTop; omega
  obtain ⟨hl,hw⟩ := emitInputs_flags_lt (base:=base) (n:=n) hs hr
  obtain ⟨ha,hv,ho⟩ := emitInputs_label_lt (n:=n) hreg hs hr
  have hb := emitBlock_bounds (region:=region) hs hj hr
  have hp := hreg'.trans hb.1
  let u := emitInputs base n t s r
  let f := emitFlags region t s r
  obtain ⟨b,hk,hg⟩ := u.coreGates_extend f a j z (emitBlockBase region t j s r)
    ((hl.trans_le hshared).trans_le hp) ((hw.trans_le hshared).trans_le hp) (hz.trans_le hp)
    (fun i hi => (ho i hi).trans_le hp) (fun i hi => (hv i hi).trans_le hp)
    (fun i => (emitFlagQuery_lt (region:=region) hs hr (by decide : 0 < 3) i).trans_le hb.1)
    (fun i => (emitFlagQuery_lt (region:=region) hs hr (by decide : 1 < 3) i).trans_le hb.1)
    (fun i => (emitFlagQuery_lt (region:=region) hs hr (by decide : 2 < 3) i).trans_le hb.1)
  have hlen := emitBlockWidth_bound hj
  exact ⟨b,fun i hi => hk i (by omega),hg⟩

abbrev EmitCoreBlock (t : ℕ) := Fin (emitLevels t) × {s : ℕ×ℕ // s ∈ layoutSlots t} × Fin 3

def emitCoreLayoutGates (base region n t z : ℕ) (slots : ℕ → List (ℕ×ℕ)) : List Gate :=
  (List.range (emitLevels t)).flatMap fun j => emitTierGateList base region n t j z (slots j)

theorem emitCoreLayout_frame {base region n t z : ℕ}
    (hreg : normalizeAfter base t ≤ region) (hshared : sharedLimit n t ≤ region)
    (hz : z < region) (slots : ℕ → List (ℕ×ℕ)) (hslots : ∀ j, slots j ⊆ layoutSlots t) :
    GateFrame (emitCoreLayoutGates base region n t z slots) (emitFlagTop region t)
      (emitFlagTop region t) (emitBlockTop region t) := by
  intro g hg i hi
  obtain ⟨j,hj,s,hs,r,hr,hg⟩ := by
    simpa only [emitCoreLayoutGates,emitTierGateList,List.mem_flatMap,List.mem_range] using hg
  have hs' := hslots j hs
  obtain ⟨hl,hh⟩ := emitBlock_bounds (region:=region) hs' hj hr
  exact ((emitOne_local_frame hreg hshared hz hs' hr hj).mono le_rfl hl hh) g hg i hi

theorem emitCoreLayout_extend {base region n t z : ℕ} (a : Assignment)
    (hreg : normalizeAfter base t ≤ region) (hshared : sharedLimit n t ≤ region)
    (hz : z < region) (slots : ℕ → List (ℕ×ℕ)) (hslots : ∀ j, slots j ⊆ layoutSlots t) :
    ∃ b, Keeps a b (emitFlagTop region t) (emitBlockTop region t) ∧
      GateSat b (emitCoreLayoutGates base region n t z slots) := by
  let index : EmitCoreBlock t → ℕ := fun ⟨j,s,r⟩ => emitBlockIndex t j s r
  let gates : EmitCoreBlock t → List Gate := fun ⟨j,s,r⟩ => emitOne base region n t j z s r
  have hu : Function.Injective index := by
    intro ⟨j,s,r⟩ ⟨j',s',r'⟩ h
    obtain ⟨h₁,h₂,h₃⟩ := emitBlockIndex_injective s.property s'.property r.isLt r'.isLt h
    exact Prod.ext (Fin.ext h₁) (Prod.ext (Subtype.ext h₂) (Fin.ext h₃))
  have hc (k : EmitCoreBlock t) : index k < 3*(emitLevels t*emitSlotSpan t) := by
    rcases k with ⟨j,s,r⟩
    exact emitBlockIndex_bound s.property j.isLt r.isLt
  have frame (k : EmitCoreBlock t) :
      GateFrame (gates k) (emitFlagTop region t)
        (emitFlagTop region t+index k*emitBlockStride t)
        (emitFlagTop region t+index k*emitBlockStride t+emitBlockStride t) := by
    rcases k with ⟨j,s,r⟩
    exact emitOne_local_frame hreg hshared hz s.property r.isLt j.isLt
  have extend (k : EmitCoreBlock t) :
      ∃ b, Keeps a b (emitFlagTop region t+index k*emitBlockStride t)
        (emitFlagTop region t+index k*emitBlockStride t+emitBlockStride t) ∧ GateSat b (gates k) := by
    rcases k with ⟨j,s,r⟩
    exact emitOne_local_extend a hreg hshared hz s.property r.isLt j.isLt
  obtain ⟨b,hk,hb⟩ := emitBank_assembleBlocks a (emitFlagTop region t) (emitBlockTop region t)
    (emitBlockStride t) (3*(emitLevels t*emitSlotSpan t)) index hu hc (by rfl) gates frame extend
  refine ⟨b,hk,fun g hg => ?_⟩
  obtain ⟨j,hj,s,hs,r,hr,hg⟩ := by
    simpa only [emitCoreLayoutGates,emitTierGateList,List.mem_flatMap,List.mem_range] using hg
  exact hb (⟨j,hj⟩,⟨s,hslots j hs⟩,⟨r,hr⟩) g hg

theorem emitCoreLayout_tier {a : Assignment} {base region n t z j : ℕ}
    {slots : ℕ → List (ℕ×ℕ)} (h : GateSat a (emitCoreLayoutGates base region n t z slots))
    (hj : j < emitLevels t) : GateSat a (emitTierGateList base region n t j z (slots j)) :=
  fun g hg => h g (List.mem_flatMap.mpr ⟨j,List.mem_range.mpr hj,hg⟩)

theorem emissionRow_key_lt {w z active beforeFlag afterFlag bound : ℕ}
    {addr before after : ℕ → ℕ} (hz : z < bound) (hact : active < bound)
    (hb : beforeFlag < bound) (ha : afterFlag < bound)
    (haddr : ∀ i < w, addr i < bound) (hbv : ∀ i < w, before i < bound)
    (hav : ∀ i < w, after i < bound) (i : ℕ) :
    emissionRow w z active beforeFlag afterFlag addr before after i < bound := by
  unfold emissionRow
  split
  · exact hact
  split
  · exact haddr _ (by omega)
  split
  · exact hb
  split
  · exact hbv _ (by omega)
  split
  · exact ha
  split
  · exact hav _ (by omega)
  · exact hz

theorem emitSource_lt {base region n t j z o : ℕ}
    (hregion : normalizeAfter base t ≤ region)
    (hz : z < region) (ho : o < region) (hj : j < emitLevels t)
    {slots : List (ℕ×ℕ)} (hslots : slots ⊆ layoutSlots t) (lane bit : ℕ) :
    emitSource base region n t j z o slots lane bit < emitBlockTop region t := by
  have hreg' : region ≤ emitFlagTop region t := by unfold emitFlagTop; omega
  have hreg'' : emitFlagTop region t ≤ emitBlockTop region t := by unfold emitBlockTop; omega
  have htop := hreg'.trans hreg''
  unfold emitSource
  cases hm : (emitLaneList slots)[lane]? with
  | none => exact hz.trans_le htop
  | some p =>
    obtain ⟨s,r,f⟩ := p
    obtain ⟨hs,hr⟩ := emitLaneList_members (List.mem_of_getElem? hm)
    have hs' := hslots hs
    let u := emitInputs base n t s r
    let b := emitBlockBase region t j s r
    have hb : b+emitBlockStride t ≤ emitBlockTop region t := (emitBlock_bounds hs' hj hr).2
    have hw := emitBlockWidth_bound hj
    have hp := Nat.two_pow_pos j
    obtain ⟨had,hval,hold⟩ := emitInputs_label_lt (n:=n) hregion hs' hr
    have padded (key : ℕ → ℕ) (h : ∀ i < u.width, key i < region) (i : ℕ) :
        paddedKey u.width z key i < emitBlockTop region t := by
      unfold paddedKey
      split
      · exact (h i ‹_›).trans_le htop
      · exact hz.trans_le htop
    cases f
    · change emitFirstRow u (2^j) z o (b+8) bit < emitBlockTop region t
      apply emissionRow_key_lt (hz.trans_le htop) (by omega) (ho.trans_le htop) (by omega)
        (fun i _ => padded _ had i) (fun i hi => by omega) (fun i _ => padded _ hval i)
    · change emitSecondRow u (2^j) z o (b+8) bit < emitBlockTop region t
      apply emissionRow_key_lt (hz.trans_le htop) (by omega) (hz.trans_le htop) (ho.trans_le htop)
        (fun i _ => padded _ had i) (fun _ _ => hz.trans_le htop) (fun i _ => padded _ hval i)

def emitAllGates (base region n t z : ℕ) (slots : ℕ → List (ℕ×ℕ)) : List Gate :=
  emitWidthLayoutGates base region n t ++ emitCoreLayoutGates base region n t z slots

theorem emitAll_frame {base region n t z : ℕ}
    (hreg : normalizeAfter base t ≤ region) (hshared : sharedLimit n t ≤ region)
    (hz : z < region) (slots : ℕ → List (ℕ×ℕ)) (hslots : ∀ j, slots j ⊆ layoutSlots t) :
    GateFrame (emitAllGates base region n t z slots) region region (emitBlockTop region t) := by
  have hp : region ≤ emitFlagTop region t := by unfold emitFlagTop; omega
  have hq : emitFlagTop region t ≤ emitBlockTop region t := by unfold emitBlockTop; omega
  apply GateFrame.append.mpr
  refine ⟨(emitWidthLayout_frame hreg).mono le_rfl le_rfl hq,?_⟩
  intro g hg i hi
  rcases emitCoreLayout_frame hreg hshared hz slots hslots g hg i hi with low|⟨hl,hh⟩
  · by_cases ht : i < region
    · exact .inl ht
    · exact .inr ⟨by omega,low.trans_le hq⟩
  · exact .inr ⟨hp.trans hl,hh⟩

theorem emitAll_extend {base region n t z : ℕ} (a : Assignment)
    (hreg : normalizeAfter base t ≤ region) (hshared : sharedLimit n t ≤ region)
    (hz : z < region) (slots : ℕ → List (ℕ×ℕ)) (hslots : ∀ j, slots j ⊆ layoutSlots t) :
    ∃ b, Keeps a b region (emitBlockTop region t) ∧ GateSat b (emitAllGates base region n t z slots) := by
  have hp : region ≤ emitFlagTop region t := by unfold emitFlagTop; omega
  have hq : emitFlagTop region t ≤ emitBlockTop region t := by unfold emitBlockTop; omega
  obtain ⟨b,hk,hWidth⟩ := emitWidthLayout_extend (n:=n) a hreg
  obtain ⟨c,hk',hCore⟩ := emitCoreLayout_extend b hreg hshared hz slots hslots
  refine ⟨c,hk.trans hk' hp hq,GateSat.append.mpr ⟨?_,hCore⟩⟩
  apply hWidth.congr_framed (emitWidthLayout_frame hreg)
  intro i hi
  exact (hk' i (.inl (by omega))).symm

theorem emitAll_exact {a : Assignment} {base region n t z o j : ℕ} {slots : ℕ → List (ℕ×ℕ)}
    (h : GateSat a (emitAllGates base region n t z slots))
    (hslots : ∀ j, slots j ⊆ layoutSlots t) (hj : j < emitLevels t) (hz : a z = false) (ho : a o = true) :
    rawMemoryRows a (2^j) (6*(slots j).length) (emitSource base region n t j z o (slots j)) =
      (slots j).flatMap (fun s => (compactSlotOptions a base n t s).flatMap (emitTier j)) :=
  emitBank_exact a base region n t j z o (slots j) hz ho
    (fun s hs r hr => emitWidthLayout_valid (GateSat.append.mp h).1 (hslots j hs) hr)
    (emitCoreLayout_tier (GateSat.append.mp h).2 hj)

private theorem emit_flatMap_length_uniform {I G : Type} (gates : I → List G) (xs : List I) (bound : ℕ)
    (h : ∀ i ∈ xs, (gates i).length ≤ bound) : (xs.flatMap gates).length ≤ xs.length*bound := by
  induction xs with
  | nil => simp
  | cons i is ih =>
    have hi := h i (.head _)
    have hh := ih (fun j hj => h j (.tail _ hj))
    simp only [List.flatMap_cons,List.length_cons,List.length_append,Nat.add_mul,Nat.one_mul]
    omega

theorem emitTierGateList_length (base region n t j z : ℕ) (slots : List (ℕ×ℕ)) :
    (emitTierGateList base region n t j z slots).length ≤ 51*(slots.length*2^j) := by
  have hl (s : ℕ×ℕ) : ((List.range 3).flatMap (emitOne base region n t j z s)).length ≤ 51*2^j := by
    have h := emit_flatMap_length_uniform (emitOne base region n t j z s) (List.range 3)
      (17*2^j) (fun r _ => EmitInput.coreGates_length _ _ _ _ _)
    simpa only [List.length_range,← Nat.mul_assoc] using h
  have h := emit_flatMap_length_uniform (fun s => (List.range 3).flatMap (emitOne base region n t j z s))
    slots (51*2^j) (fun s _ => hl s)
  unfold emitTierGateList
  exact h.trans_eq (by ac_rfl)

theorem emitCoreLayout_length (base region n t z : ℕ) (slots : ℕ → List (ℕ×ℕ))
    (hb : ∀ j < emitLevels t, (slots j).length*2^j ≤ 8*layoutHorizon t) :
    (emitCoreLayoutGates base region n t z slots).length ≤ 408*(layoutHorizon t*emitLevels t) := by
  have h := emit_flatMap_length_uniform (fun j => emitTierGateList base region n t j z (slots j))
    (List.range (emitLevels t)) (408*layoutHorizon t)
    (fun j hj => (emitTierGateList_length base region n t j z (slots j)).trans
      (by simpa only [← Nat.mul_assoc] using Nat.mul_le_mul_left 51 (hb j (List.mem_range.mp hj))))
  unfold emitCoreLayoutGates
  rw [List.length_range] at h
  exact h.trans_eq (by ac_rfl)

theorem emitWidthLayout_length (base region n t : ℕ) :
    (emitWidthLayoutGates base region n t).length ≤
      27*((layoutSlots t).map fun s => 2^s.2).sum := by
  let gates := fun s => (List.range 3).flatMap fun r =>
    (List.range 3).flatMap (emitWidthGates base region n t s r)
  have hg (s : ℕ×ℕ) : (gates s).length ≤ 27*2^s.2 := by
    have hr (r : ℕ) : ((List.range 3).flatMap (emitWidthGates base region n t s r)).length ≤ 9*2^s.2 := by
      have h := emit_flatMap_length_uniform (emitWidthGates base region n t s r) (List.range 3)
        (3*2^s.2) (fun f _ => emitWidthGates_length base region n t s r f)
      simpa only [List.length_range,← Nat.mul_assoc] using h
    have h := emit_flatMap_length_uniform (fun r => (List.range 3).flatMap (emitWidthGates base region n t s r))
      (List.range 3) (9*2^s.2) (fun r _ => hr r)
    simpa only [List.length_range,← Nat.mul_assoc,gates] using h
  have main (xs : List (ℕ×ℕ)) :
      (xs.flatMap gates).length ≤ 27*(xs.map fun s => 2^s.2).sum := by
    induction xs with
    | nil => simp
    | cons s ss ih =>
      have hs := hg s
      simp only [List.flatMap_cons,List.map_cons,List.sum_cons,List.length_append,Nat.mul_add]
      omega
  exact main (layoutSlots t)

end CNFEncComplexity.Robson

/- RobsonMemEmitLocal -/

namespace CNFEncComplexity.Robson
open CookLevin


private theorem memoryEmitAtTierAppend (j : ℕ) (us vs : List TierRecord) :
    atTier j (us++vs) = atTier j us ++ atTier j vs := by
  simp [atTier,List.filter_append]

private theorem memoryEmitTieredObsAppend (us vs : List ObservedAccess) :
    tieredObservations bitTier (us++vs) = tieredObservations bitTier us ++ tieredObservations bitTier vs := by
  simp [tieredObservations,List.flatMap_append]

def emitSlotTier (j : ℕ) (slots : List (Option ObservedAccess)) : List (Option LocalRecord) :=
  slots.flatMap (emitTier j)

@[simp] theorem emitSlotTier_length (j : ℕ) (slots : List (Option ObservedAccess)) :
    (emitSlotTier j slots).length = 2*slots.length := by
  induction slots with
  | nil => rfl
  | cons s ss ih =>
    rw [emitSlotTier,List.flatMap_cons,List.length_append,emitTier_length,
      show ss.flatMap (emitTier j) = emitSlotTier j ss from rfl,ih,List.length_cons]
    omega

theorem emitSlotTier_exact (j : ℕ) (slots : List (Option ObservedAccess)) :
    (emitSlotTier j slots).filterMap id =
      atTier j (tieredObservations bitTier (slots.filterMap id)) := by
  induction slots with
  | nil => rfl
  | cons s ss ih =>
    rw [emitSlotTier,List.flatMap_cons,List.filterMap_append,emitTier_exact,
      show ss.flatMap (emitTier j) = emitSlotTier j ss from rfl,ih]
    cases s with
    | none => simp [tieredObservations,atTier]
    | some r =>
      simp only [Option.toList_some,List.flatMap_cons,List.flatMap_nil,List.append_nil,List.filterMap_cons,
        id_eq]
      exact (memoryEmitAtTierAppend j _ _).symm

def memoryEmitLanes (t j : ℕ) (packed : (ℕ×ℕ) → List (Option ObservedAccess)) :
    List (Option LocalRecord) :=
  (memoryTierSlots t j).flatMap fun s => emitSlotTier j (packed s)

theorem memoryEmitLanes_length (t j : ℕ) (packed : (ℕ×ℕ) → List (Option ObservedAccess))
    (hb : ∀ s ∈ layoutSlots t, (packed s).length = 3) :
    (memoryEmitLanes t j packed).length = memoryTierRows t j := by
  have hLen (xs : List (ℕ×ℕ)) (h : ∀ s ∈ xs, s ∈ layoutSlots t) :
      (xs.flatMap fun s => emitSlotTier j (packed s)).length = 6*xs.length := by
    induction xs with
    | nil => rfl
    | cons s ss ih =>
      rw [List.flatMap_cons,List.length_append,emitSlotTier_length,hb _ (h _ (by simp)),
        ih (fun s hs => h s (List.mem_cons_of_mem _ hs)),List.length_cons]
      omega
  exact hLen _ (fun s hs => (List.mem_filter.mp hs).1)

theorem memoryEmitLanes_projection (t j : ℕ) (packed : (ℕ×ℕ) → List (Option ObservedAccess)) :
    (memoryEmitLanes t j packed).filterMap id =
      ((memoryTierSlots t j).flatMap fun s =>
        atTier j (tieredObservations bitTier ((packed s).filterMap id))) := by
  unfold memoryEmitLanes
  induction memoryTierSlots t j with
  | nil => rfl
  | cons s ss ih =>
    rw [List.flatMap_cons,List.filterMap_append,emitSlotTier_exact,ih,List.flatMap_cons]

theorem memoryEmitLanes_sameProjection {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
    (packed : (ℕ×ℕ) → List (Option ObservedAccess))
    (hb : ∀ s ∈ layoutSlots t, (packed s).length = 3)
    (hx : PackedSlots α n t b dict (fun s => (packed s).filterMap id)) (j : ℕ) :
    (memoryEmitLanes t j packed).length = (memoryTierLanes t j (fun s => (packed s).filterMap id)).length ∧
    (memoryEmitLanes t j packed).filterMap id =
      (memoryTierLanes t j (fun s => (packed s).filterMap id)).filterMap id := by
  refine ⟨(memoryEmitLanes_length t j packed hb).trans (memoryTierLanes_length hx j).symm,?_⟩
  rw [memoryEmitLanes_projection]
  unfold memoryTierLanes
  induction memoryTierSlots t j with
  | nil => rfl
  | cons s ss ih =>
    rw [List.flatMap_cons,List.flatMap_cons,List.filterMap_append,← ih]
    congr 1
    unfold perSlotTierRows
    rw [List.filterMap_append,List.filterMap_map]
    have he : (List.replicate (6-(atTier j (tieredObservations bitTier ((packed s).filterMap id))).length)
        (none : Option LocalRecord)).filterMap id = [] := by
      apply List.filterMap_eq_nil_iff.mpr
      intro a ha
      exact List.eq_of_mem_replicate ha
    simp [he]

theorem memoryEmitLanes_exact {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
    (packed : (ℕ×ℕ) → List (Option ObservedAccess))
    (hb : ∀ s ∈ layoutSlots t, (packed s).length = 3)
    (hx : PackedSlots α n t b dict (fun s => (packed s).filterMap id))
    (good : WordEdge.Interned dict) :
    observedMemoryValid (fun _ => 0) (memoryStream α n t) ↔
      ∀ j < (b+1).size+1,
        TierBatchCertificate (memoryGroupCap j) (memoryGroupCount t j) (memoryEmitLanes t j packed)
          (fun a => liveMemory bitTier (fun _ => 0) (j,a)) := by
  refine (memoryTierLanes_exact hx good).trans ?_
  refine forall_congr' (fun j => forall_congr' (fun _ => ?_))
  let ys := memoryTierLanes t j (fun s => (packed s).filterMap id)
  let xs := memoryEmitLanes t j packed
  have hp := memoryEmitLanes_sameProjection packed hb hx j
  have hl : ys.length ≤ memoryGroupCap j*memoryGroupCount t j :=
    (memoryTierLanes_length hx j).trans_le (memoryGroupCount_cap t j)
  have hl' : xs.length ≤ memoryGroupCap j*memoryGroupCount t j := hp.1.trans_le hl
  have hfits : ∀ r ∈ tieredObservations bitTier (packMemoryStream t (fun s => (packed s).filterMap id)),
      TierRecordFits (b+1) r := by
    intro r hr
    obtain ⟨o,ho,hor⟩ := List.mem_flatMap.mp hr
    obtain ⟨s,hs,ho⟩ := List.mem_flatMap.mp ho
    obtain ⟨ha,hv,hold⟩ := hx.widths s hs o ho
    have h := Nat.add_le_add_right (min_le_right (2^s.2) b) 1
    exact tieredAccess_fits (ha.trans h) (hv.trans h) (hold.trans h) r hor
  have hR : ∀ r ∈ ys.filterMap id, r.addr < memoryGroupCap j := by
    rw [show ys.filterMap id = _ from memoryTierLanes_projection hx j]
    exact atTier_address_bounded hfits
  have hR' : ∀ r ∈ xs.filterMap id, r.addr < memoryGroupCap j := hp.2.symm ▸ hR
  rw [tierBatchCertificate_iff _ _ _ _ hl hR (bitTier_initial_restricted j),
    tierBatchCertificate_iff _ _ _ _ hl' hR' (bitTier_initial_restricted j),hp.2]

end CNFEncComplexity.Robson
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).

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