Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Trie constraints for bounded RAM word slots

Definition
CNFEncComplexity_RobsonMemoryTrieSlots

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

complexity-theorysatisfiability

Local Boolean constraints for normalizing bounded RAM words, with witness construction and shared-port framing.

Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryWindowGates

set_option maxHeartbeats 4000000
set_option linter.all false

/- RobsonTrieChunk -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

/-- The bits of a decoded word agree with the source wires throughout its width. -/
theorem wireValue_testBit (a : Assignment) (src : ℕ → ℕ) {w i : ℕ} (hi : i < w) :
    (wireValue a src w).testBit i = a (src i) := by
  let e := Cslib.BitString.equivFin w
  let f : Fin w → Bool := fun j => a (src j.val)
  have he := Cslib.BitString.equivFin_symm_apply (e f) ⟨i,hi⟩
  change e.symm (e f) ⟨i,hi⟩ = (e f).val.testBit i at he
  rw [Equiv.symm_apply_apply] at he
  rw [wireValue_eq_bitString]
  exact he.symm

/-- An aligned B-bit slice has exactly the expected digit in base 2^B. -/
theorem wireValue_chunk (a : Assignment) (src : ℕ → ℕ) {w B k : ℕ} (h : k*B+B ≤ w) :
    wireValue a (fun i => src (k*B+i)) B = (wireValue a src w / (2^B)^k) % 2^B := by
  apply Nat.eq_of_testBit_eq
  intro i
  rw [Nat.testBit_mod_two_pow]
  by_cases hi : i < B
  · have hi' : k*B+i < w := by omega
    simp only [hi,decide_true,Bool.true_and]
    rw [wireValue_testBit _ _ hi,← Nat.pow_mul,Nat.testBit_div_two_pow,
      Nat.mul_comm B k,Nat.add_comm i (k*B),wireValue_testBit _ _ hi']
  · have eq : (wireValue a (fun i => src (k*B+i)) B).testBit i = false :=
      Nat.testBit_lt_two_pow ((wireValue_lt a _ B).trans_le
        (Nat.pow_le_pow_right (by decide) (Nat.le_of_not_gt hi)))
    simp [hi,eq]

/-- A significant digit exists at k exactly when a bit at offset k*B or greater is set. -/
theorem chunk_index_lt_iff {x k B : ℕ} (hB : 0 < B) :
    k < (Nat.digits (2^B) x).length ↔ k*B < x.size := by
  have hbase : 1 < (2:ℕ)^B := one_lt_pow₀ (by decide) hB.ne'
  rw [Nat.lt_digits_length_iff hbase,← Nat.pow_mul,Nat.mul_comm B k]
  exact (Nat.lt_size).symm

/-- The digit list implementation and binary slices use the same least significant order. -/
theorem chunk_getElem {x k B : ℕ} (hB : 0 < B)
    (hk : k < (Nat.digits (2^B) x).length) :
    (Nat.digits (2^B) x)[k] = (x / (2^B)^k) % 2^B := by
  have hbase : 1 < (2:ℕ)^B := one_lt_pow₀ (by decide) hB.ne'
  induction k generalizing x with
  | zero =>
    have h0 : x ≠ 0 := by intro he; subst x; simp at hk
    apply Option.some.inj
    rw [← List.getElem?_eq_getElem hk, Nat.digits_eq_cons_digits_div hbase h0]
    simp
  | succ k ih =>
    have h0 : x ≠ 0 := by intro he; subst x; simp at hk
    have hd := Nat.digits_eq_cons_digits_div hbase h0
    have hk' : k < (Nat.digits (2^B) (x / 2^B)).length := by simpa [hd] using hk
    apply Option.some.inj
    rw [← List.getElem?_eq_getElem hk,hd,List.getElem?_cons_succ,List.getElem?_eq_getElem hk',
       ih hk',Nat.div_div_eq_div_mul,pow_succ,Nat.mul_comm (2^B) ((2^B)^k)]

/-- The false padding bits after the encoded word is truncated do not change its value. -/
theorem wireValue_prefix_eq (a : Assignment) (src : ℕ → ℕ) {n B : ℕ}
    (hBn : B ≤ n) (h : (wireValue a src n).size ≤ B) :
    wireValue a src B = wireValue a src n := by
  apply Nat.eq_of_testBit_eq
  intro i
  by_cases hi : i < B
  · rw [wireValue_testBit _ _ hi,wireValue_testBit _ _ (hi.trans_le hBn)]
  · have hp : 2^B ≤ (2:ℕ)^i := Nat.pow_le_pow_right (by decide) (Nat.le_of_not_gt hi)
    rw [Nat.testBit_lt_two_pow ((wireValue_lt a _ B).trans_le hp),
      Nat.testBit_lt_two_pow ((Nat.size_le.mp h).trans_le hp)]

/-- One low tag bit precedes the little-endian payload. -/
theorem wireValue_tag (a : Assignment) (src : ℕ → ℕ) (n : ℕ) :
    wireValue a src (n+1) = 2*wireValue a (fun i => src (i+1)) n + (a (src 0)).toNat := by
  induction n with
  | zero => cases h : a (src 0) <;> simp [wireValue,h]
  | succ n ih =>
    simp only [wireValue] at ih ⊢
    rw [pow_succ]
    cases h : a (src (n+1)) <;> simp only [h, if_true,if_false,Bool.false_eq_true] <;> omega

end CNFEncComplexity.Robson

/- RobsonTrieLocal -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

/-- A word-level multiplexer introduces one local gate per bit. -/
def trieMux (w sel : ℕ) (out yes no : ℕ → ℕ) : List Gate :=
  (List.range w).map (fun i => .mux (out i) sel (yes i) (no i))

@[simp] theorem length_trieMux (w sel : ℕ) (out yes no : ℕ → ℕ) :
    (trieMux w sel out yes no).length = w := by simp [trieMux]

theorem trieMux_exact (a : Assignment) (w sel : ℕ) (out yes no : ℕ → ℕ) :
    (∀ g ∈ trieMux w sel out yes no, g.Holds a) ↔
      wireValue a out w = if a sel then wireValue a yes w else wireValue a no w := by
  cases h : a sel <;>
  simp only [trieMux,List.forall_mem_map,List.mem_range,Gate.Holds,h,Bool.false_eq_true,
    if_false,if_true,wireValue_eq_iff]

theorem wireValue_const_false (a : Assignment) (f w : ℕ) (h : a f = false) :
    wireValue a (fun _ => f) w = 0 := by
  induction w with
  | zero => rfl
  | succ w ih => simp [wireValue,ih,h]

/-- The scratch wire names for one word. Width flags are stored consecutively.
All other names are supplied by the surrounding layout. -/
structure TrieWordWires where
  raw : ℕ → ℕ
  present : ℕ
  flags : ℕ
  usesTrie : ℕ
  emit : ℕ → ℕ
  parent : ℕ → ℕ → ℕ
  child : ℕ → ℕ → ℕ
  label : ℕ → ℕ

def TrieWordWires.mark (w : TrieWordWires) (i : ℕ) : ℕ := widthFlagWire w.flags i

/-- At the end of the allocated chunk range the successor is the constant zero. -/
def TrieWordWires.nextChild (w : TrieWordWires) (B K k i : ℕ) : ℕ :=
  if k+1 < K then w.child (k+1) i else w.mark (B*K)

def trieStepGates (w : TrieWordWires) (B K k : ℕ) : List Gate :=
  .conj (w.emit k) w.usesTrie (w.mark (k*B)) ::
    trieMux B (w.mark ((k+1)*B)) (w.parent k) (w.nextChild B K k) (fun _ => w.mark (B*K))

def longTrieGates (w : TrieWordWires) (B K : ℕ) : List Gate :=
  widthCircuit w.flags (B*K) w.raw ++
    [.conj w.usesTrie w.present (w.mark B), .copy (w.label 0) (w.mark B)] ++
    trieMux B (w.mark B) (fun i => w.label (i+1)) (w.child 0) w.raw ++
    (List.range K).flatMap (trieStepGates w B K)

def shortTrieGates (w : TrieWordWires) (n : ℕ) : List Gate :=
  .pin (w.label 0) false :: wordCopy n (fun i => w.label (i+1)) w.raw

/-- An edge's digit uses the existing raw input wires, so no copy gates are needed. -/
def trieEdge (a : Assignment) (w : TrieWordWires) (B k : ℕ) : WordEdge :=
  ⟨wireValue a (w.parent k) B,wireValue a (fun i => w.raw (k*B+i)) B,
     wireValue a (w.child k) B⟩

def trieWordRows (a : Assignment) (w : TrieWordWires) (B K : ℕ) : List WordEdge :=
  ((List.range K).filter fun k => a (w.emit k)).map (trieEdge a w B)

theorem shortTrieGates_sound (a : Assignment) (w : TrieWordWires) (n B : ℕ)
    (hn : n ≤ B)
    (h : ∀ g ∈ shortTrieGates w n, g.Holds a) (dict : List WordEdge) :
    WordLabel B dict (wireValue a w.raw n) (wireValue a w.label (n+1)) := by
  have tag : a (w.label 0) = false := h _ (List.mem_cons_self)
  have hcopy : wireValue a (fun i => w.label (i+1)) n = wireValue a w.raw n :=
    (wordCopy_exact _ _ _ _).mp (fun g hg => h g (List.mem_cons_of_mem _ hg))
  have hsize := (Nat.size_le.mpr (wireValue_lt a w.raw n)).trans hn
  rw [wireValue_tag,hcopy,tag]
  simpa using (WordLabel.small (dict := dict) hsize)

theorem length_shortTrieGates (w : TrieWordWires) (n : ℕ) :
    (shortTrieGates w n).length = n+1 := by simp [shortTrieGates]

theorem length_longTrieGates (w : TrieWordWires) (B K : ℕ) (hK : 0 < K) (hB : 0 < B) :
    (longTrieGates w B K).length ≤ 8*(B*K) := by
  have stepLength (ks : List ℕ) :
      (ks.flatMap (trieStepGates w B K)).length = ks.length*(B+1) := by
    induction ks with
    | nil => simp
    | cons k ks ih =>
      simp [List.flatMap_cons,trieStepGates,ih,Nat.add_mul,Nat.add_comm] <;> omega
  have hKB : K ≤ B*K := by simpa using Nat.mul_le_mul_right K hB
  have hBK : B ≤ B*K := by simpa using Nat.mul_le_mul_left B hK
  simp only [longTrieGates,List.length_append,length_widthCircuit,List.length_cons,
    List.length_nil,length_trieMux,stepLength,List.length_range]
  rw [Nat.mul_add,Nat.mul_one,Nat.mul_comm K B]
  omega

/-- The semantic obligations are also sufficient for satisfying the exact gate list. -/
theorem longTrieGates_realize (a : Assignment) (w : TrieWordWires) (B K : ℕ)
    (hwidth : ∀ g ∈ widthCircuit w.flags (B*K) w.raw, g.Holds a)
    (hUses : a w.usesTrie = (a w.present && a (w.mark B)))
    (hTag : a (w.label 0) = a (w.mark B))
    (hLabel : ∀ i < B, a (w.label (i+1)) = if a (w.mark B) then a (w.child 0 i) else a (w.raw i))
    (hEmit : ∀ k < K, a (w.emit k) = (a w.usesTrie && a (w.mark (k*B))))
    (hParent : ∀ k < K, ∀ i < B, a (w.parent k i) =
      if a (w.mark ((k+1)*B)) then a (w.nextChild B K k i) else a (w.mark (B*K))) :
    ∀ g ∈ longTrieGates w B K, g.Holds a := by
  simp only [longTrieGates,List.forall_mem_append]
  refine ⟨⟨⟨hwidth,?_⟩,?_⟩,?_⟩
  · simpa [Gate.Holds] using And.intro hUses hTag
  · intro g hg
    obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
    exact hLabel _ (List.mem_range.mp hi)
  · intro g hg
    obtain ⟨k,hk,hg⟩ := List.mem_flatMap.mp hg
    rcases List.mem_cons.mp hg with rfl | hg
    · exact hEmit _ (List.mem_range.mp hk)
    · obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
      exact hParent _ (List.mem_range.mp hk) _ (List.mem_range.mp hi)

end CNFEncComplexity.Robson

/- RobsonTrieChain -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

private theorem chainOfArray {dict : List WordEdge} (ds : List ℕ) (ids : ℕ → ℕ)
    (he : ∀ k (hk : k < ds.length),
      (⟨if k+1 < ds.length then ids (k+1) else 0,ds[k],ids k⟩ : WordEdge) ∈ dict) :
    WordEdge.Represents dict ds (if ds.isEmpty then 0 else ids 0) := by
  induction ds generalizing ids with
  | nil => exact .nil
  | cons d ds ih =>
    have atHead := he 0 (by simp)
    have hRest : WordEdge.Represents dict ds (if ds.isEmpty then 0 else ids (0+1)) := by
      apply ih (fun k => ids (k+1))
      intro k hk
      have hh := he (k+1) (by simp; omega)
      have hr : k+1 < ds.length ↔ k+1+1 < (d::ds).length := by simp
      simpa [List.getElem_cons_succ,hr,Nat.add_assoc] using hh
    change WordEdge.Represents dict (d::ds) (ids 0)
    apply WordEdge.Represents.cons hRest
    cases ds <;> simpa using atHead

/-- Convert an existing canonical trie path to exactly the child-ID array used
by the local gates. This also supplies bounds for every relevant ID. -/
theorem WordEdge.Represents.childArray {dict : List WordEdge} {ds : List ℕ} {id : ℕ}
    (h : WordEdge.Represents dict ds id) {B : ℕ}
    (hBound : ∀ e ∈ dict, e.child < 2^B) :
    ∃ ids : ℕ → ℕ, (if ds.isEmpty then 0 else ids 0) = id ∧
      (∀ k (hk : k < ds.length),
        (⟨if k+1 < ds.length then ids (k+1) else 0,ds[k],ids k⟩ : WordEdge) ∈ dict) ∧
      ∀ k, ids k < 2^B := by
  induction h with
  | nil =>
    refine ⟨fun _ => 0,rfl,?_,fun _ => by positivity⟩
    simp
  | @cons d ds par id hp he ih =>
    obtain ⟨ids,hFirst,hMem,hb⟩ := ih
    let out : ℕ → ℕ
      | 0 => id
      | k+1 => ids k
    refine ⟨out,rfl,?_,?_⟩
    · intro k hk
      cases k with
      | zero =>
        have htop : (if 0+1 < (d::ds).length then out (0+1) else 0) = par := by
          cases ds <;> simpa [out] using hFirst
        change (⟨if 0+1 < (d::ds).length then out (0+1) else 0,d,id⟩ : WordEdge) ∈ dict
        rw [htop]
        exact he
      | succ k =>
        have hk' : k < ds.length := by simpa using hk
        have hif : (k+1+1 < (d::ds).length) = (k+1 < ds.length) := by simp
        simpa [out,hif] using hMem k hk'
    · intro k
      cases k with
      | zero => exact hBound _ he
      | succ k => exact hb k

private theorem trieWordDigit_fits (a : Assignment) (w : TrieWordWires) (B K : ℕ)
    (hB : 0 < B) :
    (Nat.digits (2^B) (wireValue a w.raw (B*K))).length ≤ K := by
  have hb : 1 < (2:ℕ)^B := one_lt_pow₀ (by decide) hB.ne'
  apply (Nat.digits_length_le_iff hb _).mpr
  rw [← Nat.pow_mul]
  exact wireValue_lt ..

theorem longTrieGates_sound (a : Assignment) (w : TrieWordWires) (B K : ℕ)
    (hB : 0 < B) (hK : 0 < K)
    (h : ∀ g ∈ longTrieGates w B K, g.Holds a) (hLive : a w.present = true)
    (dict : List WordEdge) (hSub : ∀ e ∈ trieWordRows a w B K, e ∈ dict) :
    WordLabel B dict (wireValue a w.raw (B*K)) (wireValue a w.label (B+1)) := by
  let val := wireValue a w.raw (B*K)
  let ds := Nat.digits (2^B) val
  let ids := fun k => wireValue a (w.child k) B
  have hb : B ≤ B*K := by simpa using Nat.mul_le_mul_left B hK
  simp only [longTrieGates,List.forall_mem_append] at h
  obtain ⟨⟨⟨hW,hInit⟩,hLabels⟩,hRows⟩ := h
  have hf (i : ℕ) (hi : i ≤ B*K) : a (w.mark i) = decide (i < val.size) :=
    widthCircuit_exact _ _ _ _ hW hi
  have hUse : a w.usesTrie = a (w.mark B) := by
    have he : a w.usesTrie = (a w.present && a (w.mark B)) :=
      hInit (.conj w.usesTrie w.present (w.mark B)) (by simp)
    simp [he,hLive]
  have hTag : a (w.label 0) = a (w.mark B) :=
    hInit (.copy (w.label 0) (w.mark B)) (by simp)
  have hLabelPayload := (trieMux_exact _ _ _ _ _ _).mp hLabels
  have hTotal := trieWordDigit_fits a w B K hB
  rw [wireValue_tag,hTag,hLabelPayload]
  by_cases hx : B < val.size
  · simp only [hf B hb,hx,decide_true,if_true]
    have hNonempty : ds ≠ [] := by
      intro he
      have h1 := (chunk_index_lt_iff (x := val) (k := 1) hB).2 (by simpa using hx)
      simp [ds,he] at h1
    have hRowsIn (k : ℕ) (hk : k < ds.length) :
        (⟨if k+1 < ds.length then ids (k+1) else 0,ds[k],ids k⟩ : WordEdge) ∈ dict := by
      have hkK : k < K := hk.trans_le hTotal
      have hkW : k*B ≤ B*K := by
        rw [Nat.mul_comm B K]
        exact Nat.mul_le_mul_right B hkK.le
      have hnW : (k+1)*B ≤ B*K := by
        rw [Nat.mul_comm B K]
        exact Nat.mul_le_mul_right B (Nat.succ_le_iff.mpr hkK)
      have hkOn := (chunk_index_lt_iff hB).mp hk
      have hStep : ∀ g ∈ trieStepGates w B K k, g.Holds a :=
        fun g hg => hRows _ (List.mem_flatMap.mpr ⟨k,List.mem_range.mpr hkK,hg⟩)
      have hemit : a (w.emit k) = true := by
        change a (w.emit k) = _
        have hg : a (w.emit k) = (a w.usesTrie && a (w.mark (k*B))) := hStep _ (List.mem_cons_self)
        rw [hg,hUse,hf _ hb,hf _ hkW]
        simp [hx,hkOn]
      apply hSub
      have hMem : trieEdge a w B k ∈ trieWordRows a w B K := by
        apply List.mem_map.mpr
        exact ⟨k,List.mem_filter.mpr ⟨List.mem_range.mpr hkK,hemit⟩,rfl⟩
      have hEqDigit : wireValue a (fun i => w.raw (k*B+i)) B = ds[k] := by
        have hw : k*B+B ≤ B*K := by simpa [Nat.succ_mul] using hnW
        exact (wireValue_chunk a w.raw hw).trans (chunk_getElem hB hk).symm
      have hEqParent : wireValue a (w.parent k) B =
          if k+1 < ds.length then ids (k+1) else 0 := by
        have hMux := (trieMux_exact a B (w.mark ((k+1)*B)) (w.parent k)
           (w.nextChild B K k) (fun _ => w.mark (B*K))).mp
            (fun g hg => hStep _ (List.mem_cons_of_mem _ hg))
        refine hMux.trans ?_
        rw [hf _ hnW]
        by_cases hn : k+1 < ds.length
        · have hn' : k+1 < K := hn.trans_le hTotal
          have htest := (chunk_index_lt_iff hB).mp hn
          simp only [htest,hn,decide_true,if_true]
          apply wireValue_key_congr
          intro i hi
          exact if_pos hn' 
        · have htest := (chunk_index_lt_iff (x := val) (k := k+1) hB).not.mp hn
          have hz : a (w.mark (B*K)) = false := by
            have hxw : val.size ≤ B*K := Nat.size_le.mpr (wireValue_lt a w.raw (B*K))
            rw [hf _ le_rfl]
            simp [not_lt.mpr hxw]
          simp [hn,htest,wireValue_const_false a _ _ hz]
      simpa [trieEdge,hEqDigit,hEqParent,ids] using hMem
    have hRep := chainOfArray ds ids hRowsIn
    have hempty : ds.isEmpty = false := by simpa using hNonempty
    have hRep' : WordEdge.Represents dict ds (ids 0) := by simpa [hempty] using hRep
    exact WordLabel.wide hx hRep' 
  · simp only [hf B hb,hx,decide_false,Bool.false_eq_true,if_false]
    have hs : val.size ≤ B := Nat.le_of_not_gt hx
    rw [wireValue_prefix_eq a w.raw hb hs]
    simpa using (WordLabel.small (dict := dict) hs)

end CNFEncComplexity.Robson

/- RobsonTrieRows -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

theorem longTrieGates_emit (a : Assignment) (w : TrieWordWires) (B K : ℕ)
    (hB : 0 < B) (hK : 0 < K)
    (h : ∀ g ∈ longTrieGates w B K, g.Holds a)
    (k : ℕ) (hk : k < K) :
    a (w.emit k) = true ↔ a w.present = true ∧ B < (wireValue a w.raw (B*K)).size ∧
      k < (Nat.digits (2^B) (wireValue a w.raw (B*K))).length := by
  have hb : B ≤ B*K := by simpa using Nat.mul_le_mul_left B hK
  have hwk : k*B ≤ B*K := by rw [Nat.mul_comm B K]; exact Nat.mul_le_mul_right B hk.le
  simp only [longTrieGates,List.forall_mem_append] at h
  obtain ⟨⟨⟨hWidth,hInit⟩,_⟩,hRows⟩ := h
  have hf (i : ℕ) (hi : i ≤ B*K) :
      a (w.mark i) = decide (i < (wireValue a w.raw (B*K)).size) :=
    widthCircuit_exact _ _ _ _ hWidth hi
  have hUse : a w.usesTrie = (a w.present && a (w.mark B)) :=
    hInit (.conj w.usesTrie w.present (w.mark B)) (by simp)
  have hStep : ∀ g ∈ trieStepGates w B K k, g.Holds a :=
    fun g hg => hRows _ (List.mem_flatMap.mpr ⟨k,List.mem_range.mpr hk,hg⟩)
  have hemit : a (w.emit k) = (a w.usesTrie && a (w.mark (k*B))) := hStep _ List.mem_cons_self
  rw [hemit,hUse,hf _ hb,hf _ hwk,chunk_index_lt_iff hB]
  simp [and_assoc]

theorem longTrieGates_edge (a : Assignment) (w : TrieWordWires) (B K : ℕ)
    (hB : 0 < B) (h : ∀ g ∈ longTrieGates w B K, g.Holds a)
    {k : ℕ} (hk : k < K)
    (hd : k < (Nat.digits (2^B) (wireValue a w.raw (B*K))).length) :
    let ds := Nat.digits (2^B) (wireValue a w.raw (B*K))
    trieEdge a w B k = ⟨
      if k+1 < ds.length then wireValue a (w.child (k+1)) B else 0,
      ds[k], wireValue a (w.child k) B⟩ := by
  let val := wireValue a w.raw (B*K)
  let ds := Nat.digits (2^B) val
  have hn : (k+1)*B ≤ B*K := by
    rw [Nat.mul_comm B K]
    exact Nat.mul_le_mul_right B (Nat.succ_le_iff.mpr hk)
  have hw : k*B+B ≤ B*K := by simpa [Nat.succ_mul] using hn
  simp only [longTrieGates,List.forall_mem_append] at h
  obtain ⟨⟨⟨hWidth,_⟩,_⟩,hRows⟩ := h
  have hs : ∀ g ∈ trieStepGates w B K k, g.Holds a := fun g hg =>
    hRows _ (List.mem_flatMap.mpr ⟨k,List.mem_range.mpr hk,hg⟩)
  have hf (i : ℕ) (hi : i ≤ B*K) : a (w.mark i) = decide (i < val.size) :=
    widthCircuit_exact _ _ _ _ hWidth hi
  have hDigit : wireValue a (fun i => w.raw (k*B+i)) B = ds[k] :=
    (wireValue_chunk a w.raw hw).trans (chunk_getElem hB hd).symm
  have hMux := (trieMux_exact a B (w.mark ((k+1)*B)) (w.parent k) (w.nextChild B K k)
      (fun _ => w.mark (B*K))).mp (fun g hg => hs _ (List.mem_cons_of_mem _ hg))
  have hFit : ds.length ≤ K := by
    have hb : 1 < (2:ℕ)^B := one_lt_pow₀ (by decide) hB.ne'
    apply (Nat.digits_length_le_iff hb _).mpr
    rw [← Nat.pow_mul]
    exact wireValue_lt ..
  have hParent : wireValue a (w.parent k) B =
      if k+1 < ds.length then wireValue a (w.child (k+1)) B else 0 := by
    rw [hMux,hf _ hn]
    by_cases hD : k+1 < ds.length
    · have hp := (chunk_index_lt_iff (x := val) (k := k+1) hB).mp hD
      simp only [hp,hD,decide_true,if_true]
      apply wireValue_key_congr
      intro i hi
      exact if_pos (hD.trans_le hFit)
    · have hp := (chunk_index_lt_iff (x := val) (k := k+1) hB).not.mp hD
      have hv : val.size ≤ B*K := Nat.size_le.mpr (wireValue_lt a w.raw (B*K))
      have hz : a (w.mark (B*K)) = false := by rw [hf _ le_rfl]; simp [not_lt.mpr hv]
      simp [hp,hD,wireValue_const_false a _ _ hz]
  change trieEdge a w B k = ⟨if k+1 < ds.length then wireValue a (w.child (k+1)) B else 0,
    ds[k],wireValue a (w.child k) B⟩
  simp only [trieEdge,hDigit,hParent]

theorem longTrieGates_payload (a : Assignment) (w : TrieWordWires) (B K : ℕ)
    (hK : 0 < K) (h : ∀ g ∈ longTrieGates w B K, g.Holds a) :
    wireValue a w.label (B+1) =
      if B < (wireValue a w.raw (B*K)).size then 2*wireValue a (w.child 0) B+1
      else 2*wireValue a w.raw (B*K) := by
  have hb : B ≤ B*K := by simpa using Nat.mul_le_mul_left B hK
  simp only [longTrieGates,List.forall_mem_append] at h
  obtain ⟨⟨⟨hWidth,hInit⟩,hLabels⟩,_⟩ := h
  have hTag : a (w.label 0) = a (w.mark B) :=
    hInit (.copy (w.label 0) (w.mark B)) (by simp)
  have hf : a (w.mark B) = decide (B < (wireValue a w.raw (B*K)).size) :=
    widthCircuit_exact _ _ _ _ hWidth hb
  rw [wireValue_tag,hTag,(trieMux_exact _ _ _ _ _ _).mp hLabels,hf]
  by_cases hu : B < (wireValue a w.raw (B*K)).size
  · simp [hu]
  · have hs := Nat.le_of_not_gt hu
    simp [hu,wireValue_prefix_eq a w.raw hb hs]

end CNFEncComplexity.Robson

/- RobsonTrieWitness -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

inductive TrieRest (B K : ℕ) where
  | used
  | emit (k : Fin K)
  | parent (k : Fin K) (i : Fin B)
  | child (k : Fin K) (i : Fin B)
  | label (i : Fin (B+1))

def TrieWordWires.restName (w : TrieWordWires) {B K : ℕ} : TrieRest B K → ℕ
  | .used => w.usesTrie
  | .emit k => w.emit k.val
  | .parent k i => w.parent k.val i.val
  | .child k i => w.child k.val i.val
  | .label i => w.label i.val

private def trieRestValue (a : Assignment) (w : TrieWordWires) (B K : ℕ) (ids : ℕ → ℕ) :
    TrieRest B K → Bool
  | .used => a w.present && a (w.mark B)
  | .emit k => (a w.present && a (w.mark B)) && a (w.mark (k.val*B))
  | .parent k i =>
    if a (w.mark ((k.val+1)*B)) then
      if k.val+1 < K then (ids (k.val+1)).testBit i.val else a (w.mark (B*K))
    else a (w.mark (B*K))
  | .child k i => (ids k.val).testBit i.val
  | .label i =>
    match i.val with
    | 0 => a (w.mark B)
    | j+1 => if a (w.mark B) then (ids 0).testBit j else a (w.raw j)

/-- Given fitted identifiers, the local verifier has a satisfying extension
which modifies only the interval for flags and the explicitly reserved names. -/
theorem longTrieGates_witnessIds (a : Assignment) (w : TrieWordWires) (B K : ℕ)
    (hK : 0 < K) (ids : ℕ → ℕ) (hIds : ∀ k < K, ids k < 2^B)
    (hRaw : ∀ i < B*K, w.raw i < w.flags) (hPresent : w.present < w.flags)
    (hName : Function.Injective (w.restName (B := B) (K := K)))
    (hAlloc : ∀ p : TrieRest B K, w.flags+B*K+1 ≤ w.restName p) :
    ∃ a' : Assignment,
      (∀ i, (i < w.flags ∨ w.flags+B*K+1 ≤ i) →
        (¬∃ p : TrieRest B K, w.restName p = i) → a' i = a i) ∧
      (∀ i < w.flags, a' i = a i) ∧
      (∀ g ∈ longTrieGates w B K, g.Holds a') ∧
      (∀ k < K, wireValue a' (w.child k) B = ids k) := by
  obtain ⟨a0,ha0,hw0⟩ := widthCircuit_extends_interval w.flags (B*K) w.raw a hRaw
  let a' : Assignment := Function.extend (w.restName (B := B) (K := K))
    (trieRestValue a0 w B K ids) a0
  have he (p : TrieRest B K) : a' (w.restName p) = trieRestValue a0 w B K ids p :=
    hName.extend_apply _ _ _
  have horig (i : ℕ) (hi : i < w.flags+B*K+1) : a' i = a0 i := by
    apply Function.extend_apply'
    rintro ⟨p,hp⟩
    have := hAlloc p
    omega
  have hbelow (i : ℕ) (hi : i < w.flags) : a' i = a i :=
    (horig i (by omega)).trans (ha0 i (.inl hi))
  have hFlag (i : ℕ) (hi : i ≤ B*K) : a' (w.mark i) = a0 (w.mark i) :=
    horig _ (by unfold TrieWordWires.mark widthFlagWire; omega)
  have hW : ∀ g ∈ widthCircuit w.flags (B*K) w.raw, g.Holds a' := by
    intro g hg
    have hs := hw0 g hg
    rcases List.mem_cons.mp hg with rfl | hg
    · change a' (w.mark (B*K)) = false
      exact (hFlag _ le_rfl).trans hs
    · obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
      have hi' := List.mem_range.mp hi
      change a' (w.mark i) = (a' (w.raw i) || a' (w.mark (i+1)))
      rw [hFlag _ hi'.le,hFlag _ hi',horig _ (by have := hRaw i hi'; omega)]
      exact hs
  have hBK : B ≤ B*K := by simpa using Nat.mul_le_mul_left B hK
  have hUse : a' w.usesTrie = (a' w.present && a' (w.mark B)) := by
    rw [hFlag _ hBK,horig w.present (by omega)]
    exact he .used
  have hTag : a' (w.label 0) = a' (w.mark B) := by
    rw [hFlag _ hBK]
    exact he (.label ⟨0,by omega⟩)
  have hChild (k : ℕ) (hk : k < K) (i : ℕ) (hi : i < B) :
      a' (w.child k i) = (ids k).testBit i :=
    he (.child ⟨k,hk⟩ ⟨i,hi⟩)
  have hSat : ∀ g ∈ longTrieGates w B K, g.Holds a' := by
    apply longTrieGates_realize a' w B K hW hUse hTag
    · intro i hi
      rw [hFlag _ hBK,hChild _ hK _ hi,horig (w.raw i) (by have := hRaw i (hi.trans_le hBK); omega)]
      exact he (.label ⟨i+1,by omega⟩)
    · intro k hk
      have hmul : k*B ≤ B*K := by rw [Nat.mul_comm B K]; exact Nat.mul_le_mul_right B hk.le
      rw [hUse,hFlag _ hBK,hFlag _ hmul,horig w.present (by omega)]
      exact he (.emit ⟨k,hk⟩)
    · intro k hk i hi
      have hmul : (k+1)*B ≤ B*K := by rw [Nat.mul_comm B K]; exact Nat.mul_le_mul_right B hk
      rw [hFlag _ hmul,hFlag _ le_rfl]
      have he' : a' (w.parent k i) =
          (if a0 (w.mark ((k+1)*B)) then
            if k+1 < K then (ids (k+1)).testBit i else a0 (w.mark (B*K))
          else a0 (w.mark (B*K))) := he (.parent ⟨k,hk⟩ ⟨i,hi⟩)
      rw [he']
      by_cases hNext : k+1 < K
      · simp only [TrieWordWires.nextChild,hNext,if_true,hChild _ hNext _ hi]
      · simp only [TrieWordWires.nextChild,hNext,if_false,hFlag _ le_rfl]
  refine ⟨a',?_,hbelow,hSat,?_⟩
  · intro i hi hi'
    exact (Function.extend_apply' _ _ _ hi').trans (ha0 i hi)
  · intro k hk
    apply Nat.eq_of_testBit_eq
    intro i
    by_cases hi : i < B
    · rw [wireValue_testBit _ _ hi,hChild _ hk _ hi]
    · have hp : 2^B ≤ (2:ℕ)^i := Nat.pow_le_pow_right (by decide) (Nat.le_of_not_gt hi)
      rw [Nat.testBit_lt_two_pow ((wireValue_lt _ _ _).trans_le hp),
        Nat.testBit_lt_two_pow ((hIds k hk).trans_le hp)]

end CNFEncComplexity.Robson

/- RobsonTrieBlock -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

private theorem wordLabel_short {B : ℕ} {dict : List WordEdge} {x y : ℕ}
    (h : WordLabel B dict x y) (hb : x.size ≤ B) : y = 2*x := by
  cases h with
  | small _ => rfl
  | wide he _ => omega

private theorem wordLabel_long {B : ℕ} {dict : List WordEdge} {x y : ℕ}
    (h : WordLabel B dict x y) (hb : B < x.size) :
    ∃ id, y = 2*id+1 ∧ WordEdge.Represents dict (Nat.digits (2^B) x) id := by
  cases h with
  | small he => omega
  | wide _ h => exact ⟨_,rfl,h⟩

/-- Construct the full local witness from fitted canonical dictionary labels.
The result's emitted rows are a subset of the very same dictionary. -/
theorem longTrieGates_complete (a : Assignment) (w : TrieWordWires) (B K : ℕ)
    (hB : 0 < B) (hK : 0 < K)
    (dict : List WordEdge) (label : ℕ)
    (hDict : ∀ e ∈ dict, e.child < 2^B)
    (hLabel : a w.present = true → WordLabel B dict (wireValue a w.raw (B*K)) label)
    (hRaw : ∀ i < B*K, w.raw i < w.flags) (hPresent : w.present < w.flags)
    (hName : Function.Injective (w.restName (B := B) (K := K)))
    (hAlloc : ∀ p : TrieRest B K, w.flags+B*K+1 ≤ w.restName p) :
    ∃ a' : Assignment,
      (∀ i, (i < w.flags ∨ w.flags+B*K+1 ≤ i) →
        (¬∃ p : TrieRest B K, w.restName p = i) → a' i = a i) ∧
      (∀ i < w.flags, a' i = a i) ∧
      (∀ g ∈ longTrieGates w B K, g.Holds a') ∧
      (a w.present = true → wireValue a' w.label (B+1) = label) ∧
      ∀ e ∈ trieWordRows a' w B K, e ∈ dict := by
  classical
  let x := wireValue a w.raw (B*K)
  let digits := Nat.digits (2^B) x
  have hArray : ∃ ids : ℕ → ℕ, (∀ k, ids k < 2^B) ∧
      (a w.present = true → B < x.size →
        label = 2*ids 0+1 ∧
        ∀ k (hk : k < digits.length),
          (⟨if k+1 < digits.length then ids (k+1) else 0,digits[k],ids k⟩ : WordEdge) ∈ dict) := by
    by_cases hwide : a w.present = true ∧ B < x.size
    · obtain ⟨id,he,hRep⟩ := wordLabel_long (hLabel hwide.1) hwide.2
      obtain ⟨ids,hf,hr,hfit⟩ := hRep.childArray hDict
      have hn : digits.isEmpty = false := by
        apply List.isEmpty_eq_false_iff.mpr
        intro hh
        have hh' : 1 < digits.length :=
          (chunk_index_lt_iff (x := x) (k := 1) hB).2 (by simpa using hwide.2)
        simp [hh] at hh'
      have hz : ids 0 = id := by
        change (if digits.isEmpty then 0 else ids 0) = id at hf
        simpa only [hn,Bool.false_eq_true,if_false] using hf
      exact ⟨ids,hfit,fun _ _ => ⟨by rw [hz]; exact he,hr⟩⟩
    · exact ⟨fun _ => 0,fun _ => by positivity, fun hp hw => False.elim (hwide ⟨hp,hw⟩)⟩
  obtain ⟨ids,hFit,hCertified⟩ := hArray
  obtain ⟨a',hFrame,hLow,hSat,hChild⟩ :=
    longTrieGates_witnessIds a w B K hK ids (fun k _ => hFit k) hRaw hPresent hName hAlloc
  have hVal : wireValue a' w.raw (B*K) = x :=
    wireValue_congr (fun i hi => hLow _ (hRaw i hi))
  have hOn : a' w.present = a w.present := hLow _ hPresent
  refine ⟨a',hFrame,hLow,hSat,?_,?_⟩
  · intro ha
    rw [longTrieGates_payload a' w B K hK hSat,hVal,hChild 0 hK]
    by_cases hw : B < x.size
    · simp [hw,(hCertified ha hw).1]
    · simpa [hw,wordLabel_short (hLabel ha) (Nat.le_of_not_gt hw),x]
  · intro e he
    obtain ⟨k,hk,rfl⟩ := List.mem_map.mp he
    obtain ⟨hm,hen⟩ := List.mem_filter.mp hk
    have hv : k < K := List.mem_range.mp hm
    have hc := (longTrieGates_emit a' w B K hB hK hSat k hv).mp hen
    rw [hOn,hVal] at hc
    obtain ⟨ha,hw,hd⟩ := hc
    have hEdge := longTrieGates_edge a' w B K hB hSat hv
    have hk' : k < (Nat.digits (2^B) (wireValue a' w.raw (B*K))).length := by simpa [hVal] using hd
    have hRewrite : trieEdge a' w B k =
        (⟨if k+1 < digits.length then wireValue a' (w.child (k+1)) B else 0,
          digits[k], wireValue a' (w.child k) B⟩ : WordEdge) := by
      have hs := hEdge hk'
      have hDigit (q : ℕ) :
          (Nat.digits (2^B) (wireValue a' w.raw (B*K)))[q]? = digits[q]? := by rw [hVal]
      have hqd := hDigit k
      rw [List.getElem?_eq_getElem hk',List.getElem?_eq_getElem hd] at hqd
      have hsz : (Nat.digits (2^B) (wireValue a' w.raw (B*K))).length = digits.length := by rw [hVal]
      dsimp only at hs
      rw [hs]
      simp only [hsz,Option.some.inj hqd] <;> rfl
    rw [hRewrite,hChild k hv]
    have hh := (hCertified ha hw).2 k hd
    by_cases hNext : k+1 < digits.length
    · have hMax : digits.length ≤ K := by
        have hb : 1 < (2:ℕ)^B := one_lt_pow₀ (by decide) hB.ne'
        apply (Nat.digits_length_le_iff hb _).2
        rw [← Nat.pow_mul]
        exact wireValue_lt ..
      simpa [hNext,hChild _ (hNext.trans_le hMax)] using hh
    · simpa [hNext] using hh

/-- Short literals also have a fresh-wire extension. No trie payload is emitted. -/
theorem shortTrieGates_witness (a : Assignment) (w : TrieWordWires) (n : ℕ)
    (hName : Function.Injective (fun i : Fin (n+1) => w.label i.val))
    (hFresh : ∀ i < n, ¬∃ k : Fin (n+1), w.label k.val = w.raw i) :
    ∃ a' : Assignment,
      (∀ v, (¬∃ k : Fin (n+1), w.label k.val = v) → a' v = a v) ∧
      (∀ g ∈ shortTrieGates w n, g.Holds a') ∧
      wireValue a' w.label (n+1) = 2*wireValue a w.raw n := by
  classical
  let f : Fin (n+1) → Bool := fun i =>
    match i.val with
    | 0 => false
    | k+1 => a (w.raw k)
  let a' : Assignment := Function.extend (fun i : Fin (n+1) => w.label i.val) f a
  have he (i : Fin (n+1)) : a' (w.label i.val) = f i := hName.extend_apply f a i
  have hFrame (v : ℕ) (hv : ¬∃ k : Fin (n+1), w.label k.val = v) : a' v = a v :=
    Function.extend_apply' f a v hv
  have hTag : a' (w.label 0) = false := he ⟨0,by omega⟩
  have hCopy : wireValue a' (fun i => w.label (i+1)) n = wireValue a w.raw n := by
    rw [show wireValue a w.raw n = wireValue a' w.raw n from
      (wireValue_congr (fun i hi => hFrame _ (hFresh i hi))).symm]
    exact (wireValue_eq_iff _ _ _ _).2 (fun i hi =>
      (he ⟨i+1,by omega⟩).trans (hFrame _ (hFresh i hi)).symm)
  refine ⟨a',hFrame,?_,?_⟩
  · intro g hg
    rcases List.mem_cons.mp hg with rfl | hg
    · exact hTag
    · have hh := (wordCopy_exact n (fun i => w.label (i+1)) w.raw a').2
        (hCopy.trans (wireValue_congr (fun i hi => hFrame _ (hFresh i hi))).symm)
      exact hh _ hg
  · simp [wireValue_tag,hTag,hCopy]

end CNFEncComplexity.Robson

/- RobsonTrieAlloc -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

/-- Static consecutive blocks within a word's reserved interval. -/
def trieWiresAt (base width K : ℕ) (B : ℕ) (raw : ℕ → ℕ) (on : ℕ) : TrieWordWires :=
  { raw := raw, present := on, flags := base, usesTrie := base+width+1
    emit := fun k => base+width+2+k
    parent := fun k j => base+width+2+K+k*B+j
    child := fun k j => base+2*width+2+K+k*B+j
    label := fun i => base+3*width+2+K+i }

theorem trieWiresAt_labels {D base W K B on : ℕ} {raw : ℕ → ℕ} :
    Function.Injective (fun i : Fin D => (trieWiresAt base W K B raw on).label i.val) := by
  intro i j he
  apply Fin.ext
  simpa [trieWiresAt,Nat.add_left_cancel_iff] using he

private theorem flattenFin_lt {B K : ℕ} (k : Fin K) (i : Fin B) :
    k.val*B+i.val < B*K := by
  have h := Nat.mul_le_mul_right B (Nat.succ_le_iff.mpr k.isLt)
  rw [Nat.succ_mul,Nat.mul_comm K B] at h
  have := i.isLt
  omega

private theorem flattenFin_inj {B K : ℕ} {k k' : Fin K} {i i' : Fin B}
    (h : k.val*B+i.val = k'.val*B+i'.val) :
    k = k' ∧ i = i' := by
  have hp : 0 < B := Nat.zero_lt_of_lt i.isLt
  have hk := congrArg (fun n => n / B) h
  have hi := congrArg (fun n => n % B) h
  have hk0 : k.val*B+i.val = i.val+k.val*B := Nat.add_comm ..
  have hk1 : k'.val*B+i'.val = i'.val+k'.val*B := Nat.add_comm ..
  rw [hk0,hk1,Nat.add_mul_div_right _ _ hp,Nat.add_mul_div_right _ _ hp,
    Nat.div_eq_of_lt i.isLt,Nat.div_eq_of_lt i'.isLt,Nat.zero_add,Nat.zero_add] at hk
  rw [hk0,hk1,Nat.add_mul_mod_self_right,Nat.add_mul_mod_self_right,
    Nat.mod_eq_of_lt i.isLt,Nat.mod_eq_of_lt i'.isLt] at hi
  exact ⟨Fin.ext hk,Fin.ext hi⟩

theorem trieWiresAt_rest_injective (base B K on : ℕ) (raw : ℕ → ℕ) :
    Function.Injective ((trieWiresAt base (B*K) K B raw on).restName (B := B) (K := K)) := by
  intro x y he
  cases x <;> cases y <;> simp only [TrieWordWires.restName,trieWiresAt] at he
  all_goals try rfl
  all_goals try (exfalso; omega)
  case emit.emit i j => exact congrArg TrieRest.emit (Fin.ext (by omega))
  case parent.parent k i k' i' =>
    obtain ⟨rfl,rfl⟩ := flattenFin_inj (k := k) (k' := k') (i := i) (i' := i') (by omega)
    rfl
  case parent.child k i k' i' =>
    have := flattenFin_lt k i
    have := flattenFin_lt k' i'
    exfalso; omega
  case parent.label k i j =>
    have := flattenFin_lt k i
    exfalso; omega
  case child.parent k i k' i' =>
    have := flattenFin_lt k i
    have := flattenFin_lt k' i'
    exfalso; omega
  case child.child k i k' i' =>
    obtain ⟨rfl,rfl⟩ := flattenFin_inj (k := k) (k' := k') (i := i) (i' := i') (by omega)
    rfl
  case child.label k i j =>
    have := flattenFin_lt k i
    exfalso; omega
  case label.parent j k i =>
    have := flattenFin_lt k i
    exfalso; omega
  case label.child j k i =>
    have := flattenFin_lt k i
    exfalso; omega
  case label.label i j => exact congrArg TrieRest.label (Fin.ext (by omega))

theorem trieWiresAt_rest_bounds (base B K on : ℕ) (raw : ℕ → ℕ)
    (hB : 0 < B) (hK : 0 < K) (r : TrieRest B K) :
    let w := trieWiresAt base (B*K) K B raw on
    base+B*K+1 ≤ w.restName r ∧ w.restName r < base+6*(B*K)+4 := by
  have h₁ : K ≤ B*K := by simpa using Nat.mul_le_mul_right K hB
  have h₂ : B ≤ B*K := by simpa using Nat.mul_le_mul_left B hK
  dsimp only
  cases r with
  | used => simp [TrieWordWires.restName,trieWiresAt]; omega
  | emit k => have := k.isLt; simp [TrieWordWires.restName,trieWiresAt]; omega
  | parent k i => have := flattenFin_lt k i; simp [TrieWordWires.restName,trieWiresAt]; omega
  | child k i => have := flattenFin_lt k i; simp [TrieWordWires.restName,trieWiresAt]; omega
  | label i => have := i.isLt; simp [TrieWordWires.restName,trieWiresAt]; omega

theorem wireValue_portWord (a : Assignment) (n t : ℕ) (s : ℕ × ℕ) (field : ℕ) :
    wireValue a (port n t s field) (2^s.2) = portWord a n t s field := by
  rw [wireValue_eq_sum]
  unfold portWord
  congr 1

end CNFEncComplexity.Robson

/- RobsonTrieSlot -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

def normalizeWidth (b : ℕ) (s : ℕ × ℕ) : ℕ := min (2^s.2) (2^b)+1

def normalizeStride (t : ℕ) : ℕ := 6*layoutHorizon t+4

def normalizeWordBase (base t : ℕ) (s : ℕ × ℕ) (r f : ℕ) : ℕ :=
  base+(((s.1*(layoutHeight t+1)+s.2)*3+r)*3+f)*normalizeStride t

def normalizeSlotWires (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ) : TrieWordWires :=
  trieWiresAt (normalizeWordBase base t s r f) (2^s.2) (2^(s.2-b)) (2^b)
    (port n t s (5+5*r+f)) (port n t s (3+5*r) 0)

def normalizeWordGates (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ) : List Gate :=
  let w := normalizeSlotWires base n t b s r f
  if b ≤ s.2 then longTrieGates w (2^b) (2^(s.2-b))
  else shortTrieGates w (2^s.2)

def normalizeSlotGates (base n t b : ℕ) (s : ℕ × ℕ) : List Gate :=
  (List.range 3).flatMap fun r =>
    (List.range 3).flatMap fun f => normalizeWordGates base n t b s r f

def normalizeSlotLabel (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ) : ℕ :=
  wireValue a (normalizeSlotWires base n t b s r f).label (normalizeWidth b s)

def normalizeWordRows (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ) :
    List WordEdge :=
  if b ≤ s.2 then trieWordRows a (normalizeSlotWires base n t b s r f) (2^b) (2^(s.2-b))
  else []

def slotCompactMemory (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) (i : ℕ) :
    Option ObservedAccess :=
  if a (port n t s (3+5*i) 0) then some
    ⟨⟨normalizeSlotLabel a base n t b s i 0, normalizeSlotLabel a base n t b s i 1,
      a (port n t s (3+5*i+1) 0)⟩,normalizeSlotLabel a base n t b s i 2⟩
  else none

def slotCompactRows (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) : List ObservedAccess :=
  (List.range 3).filterMap (slotCompactMemory a base n t b s)

theorem normalizeChunkGeometry {b j : ℕ} (h : b ≤ j) : 2^b*2^(j-b) = (2:ℕ)^j := by
  rw [← pow_add,Nat.add_sub_of_le h]

theorem normalizeWordGates_length (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ) :
    (normalizeWordGates base n t b s r f).length ≤ 8*2^s.2 := by
  unfold normalizeWordGates
  split
  · rename_i h
    rw [← normalizeChunkGeometry h]
    exact length_longTrieGates _ _ _ (by positivity) (by positivity)
  · rw [length_shortTrieGates]
    have h : 0 < (2:ℕ)^s.2 := by positivity
    omega

theorem normalizeSlotGates_length (base n t b : ℕ) (s : ℕ × ℕ) :
    (normalizeSlotGates base n t b s).length ≤ 72*2^s.2 := by
  have hs (rows : List ℕ) (F : ℕ → List Gate) (m : ℕ)
      (h : ∀ i ∈ rows, (F i).length ≤ m) : (rows.flatMap F).length ≤ rows.length*m := by
    induction rows with
    | nil => simp
    | cons i r ih =>
      have hr := ih (fun j hj => h j (List.mem_cons_of_mem _ hj))
      have hi := h i List.mem_cons_self
      rw [List.flatMap_cons,List.length_append,List.length_cons,Nat.add_mul,Nat.one_mul]
      omega
  unfold normalizeSlotGates
  have h := hs (List.range 3) _ (24*2^s.2) (fun r _ => by
    have hh := hs (List.range 3) (normalizeWordGates base n t b s r) (8*2^s.2)
      (fun f _ => normalizeWordGates_length base n t b s r f)
    simpa only [List.length_range,← Nat.mul_assoc] using hh)
  simpa only [List.length_range,← Nat.mul_assoc] using h

/-- Decode one compact word from the actual gate list and the verified
dictionary containing that word's emitted rows. -/
theorem normalizedWord_sound (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
    (ha : a (port n t s (3+5*r) 0) = true)
    (h : ∀ g ∈ normalizeWordGates base n t b s r f, g.Holds a)
    (dict : List WordEdge) (hSub : ∀ e ∈ normalizeWordRows a base n t b s r f, e ∈ dict) :
    WordLabel (2^b) dict (portWord a n t s (5+5*r+f)) (normalizeSlotLabel a base n t b s r f) := by
  let w := normalizeSlotWires base n t b s r f
  by_cases hb : b ≤ s.2
  · have hLong : ∀ g ∈ longTrieGates w (2^b) (2^(s.2-b)), g.Holds a := by
      simpa only [normalizeWordGates,if_pos hb] using h
    have hS : ∀ e ∈ trieWordRows a w (2^b) (2^(s.2-b)), e ∈ dict := by
      simpa only [normalizeWordRows,if_pos hb] using hSub
    have hw := longTrieGates_sound a w _ _ (by positivity) (by positivity) hLong ha dict hS
    rw [normalizeChunkGeometry hb] at hw
    change WordLabel _ _ (wireValue a (port n t s _) _) (wireValue a w.label _) at hw
    rw [wireValue_portWord] at hw
    have hOrder := Nat.pow_le_pow_right (n := 2) (by decide : 0 < 2) hb
    simpa only [normalizeSlotLabel,normalizeWidth,min_eq_right hOrder] using hw
  · have hShort : ∀ g ∈ shortTrieGates w (2^s.2), g.Holds a := by
      simpa only [normalizeWordGates,if_neg hb] using h
    have hOrder := Nat.pow_le_pow_right (n := 2) (by decide : 0 < 2) (by omega : s.2 ≤ b)
    have hw := shortTrieGates_sound a w _ _ hOrder hShort dict
    change WordLabel _ _ (wireValue a (port n t s _) _) (wireValue a w.label _) at hw
    rw [wireValue_portWord] at hw
    simpa only [normalizeSlotLabel,normalizeWidth,min_eq_left hOrder] using hw

/-- All selected compact rows have the same order and the same flags as the
original slot. The three values are decoded from the local labeled words. -/
theorem normalizedSlot_sound (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ)
    (h : ∀ g ∈ normalizeSlotGates base n t b s, g.Holds a)
    (dict : List WordEdge)
    (hSub : ∀ r < 3, ∀ f < 3, ∀ e ∈ normalizeWordRows a base n t b s r f, e ∈ dict) :
    List.Forall₂ (ObservedLabels (2^b) dict) (slotRows a n t s) (slotCompactRows a base n t b s) := by
  have hWord (r f : ℕ) (hr : r < 3) (hf : f < 3) (hv : a (port n t s (3+5*r) 0) = true) :
      WordLabel (2^b) dict (portWord a n t s (5+5*r+f)) (normalizeSlotLabel a base n t b s r f) :=
    normalizedWord_sound a base n t b s r f hv
      (fun g hg => h g (List.mem_flatMap.mpr ⟨r,List.mem_range.mpr hr,
        List.mem_flatMap.mpr ⟨f,List.mem_range.mpr hf,hg⟩⟩)) dict (hSub r hr f hf)
  have aux (rows : List ℕ) (hR : ∀ i ∈ rows, i < 3) :
      List.Forall₂ (ObservedLabels (2^b) dict) (rows.filterMap (portMemory a n t s))
        (rows.filterMap (slotCompactMemory a base n t b s)) := by
    induction rows with
    | nil => exact List.Forall₂.nil
    | cons r rows ih =>
      have hr := hR r List.mem_cons_self
      have ht := ih (fun k hk => hR _ (List.mem_cons_of_mem _ hk))
      by_cases hv : a (port n t s (3+5*r) 0) = true
      · rw [List.filterMap_cons, List.filterMap_cons]
        have h0 := hWord r 0 hr (by decide) hv
        have h1 := hWord r 1 hr (by decide) hv
        have h2 := hWord r 2 hr (by decide) hv
        have he0 : 5+5*r+0 = 3+5*r+2 := by omega
        have he1 : 5+5*r+1 = 3+5*r+3 := by omega
        have he2 : 5+5*r+2 = 3+5*r+4 := by omega
        rw [he0] at h0
        rw [he1] at h1
        rw [he2] at h2
        simp only [portMemory,slotCompactMemory,hv,if_true]
        exact .cons ⟨⟨h0,h1,rfl⟩,fun _ => h2⟩ ht
      · simpa only [List.filterMap_cons,portMemory,slotCompactMemory,hv,Bool.false_eq_true,if_false] using ht
  exact aux (List.range 3) (fun _ hi => List.mem_range.mp hi)

end CNFEncComplexity.Robson

/- RobsonTrieSlotWitness -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

theorem normalizeWordBase_ge (base t : ℕ) (s : ℕ × ℕ) (r f : ℕ) :
    base ≤ normalizeWordBase base t s r f := Nat.le_add_right _ _

theorem normalizeWord_complete (a : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
    (hBase : sharedLimit n t ≤ base) (hs : s ∈ layoutSlots t) (hr : r < 3) (hf : f < 3)
    (dict : List WordEdge) (label : ℕ) (hDict : ∀ e ∈ dict, e.child < 2^(2^b))
    (hLabel : a (port n t s (3+5*r) 0) = true →
      WordLabel (2^b) dict (portWord a n t s (5+5*r+f)) label) :
    let l := normalizeWordBase base t s r f
    ∃ a' : Assignment,
      (∀ i, (i < l ∨ l+normalizeStride t ≤ i) → a' i = a i) ∧
      (∀ g ∈ normalizeWordGates base n t b s r f, g.Holds a') ∧
      (a (port n t s (3+5*r) 0) = true → normalizeSlotLabel a' base n t b s r f = label) ∧
      ∀ e ∈ normalizeWordRows a' base n t b s r f, e ∈ dict := by
  let W := (2:ℕ)^s.2
  let B := (2:ℕ)^b
  let K := (2:ℕ)^(s.2-b)
  let l := normalizeWordBase base t s r f
  let w := normalizeSlotWires base n t b s r f
  have hWpos : 0 < W := by unfold W; positivity
  have hsGeom := layout_mem.mp hs
  have hW : W ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) hsGeom.2.1
  have hLb : sharedLimit n t ≤ l := hBase.trans (normalizeWordBase_ge _ _ _ _ _)
  have hRaw (i : ℕ) (hi : i < W) : w.raw i < l := by
    change port n t s (5+5*r+f) i < l
    rcases s with ⟨u,j⟩
    exact (port_lt_shared hsGeom.1 hsGeom.2.1 (by omega) (hi.trans_le hW)).trans_le hLb
  have hOn : w.present < l := by
    change port n t s (3+5*r) 0 < l
    rcases s with ⟨u,j⟩
    exact (port_lt_shared hsGeom.1 hsGeom.2.1 (by omega) (hWpos.trans_le hW)).trans_le hLb
  by_cases hLong : b ≤ s.2
  · have he : B*K = W := normalizeChunkGeometry hLong
    have hw : w = trieWiresAt l (B*K) K B (port n t s (5+5*r+f)) (port n t s (3+5*r) 0) := by
      rw [he]
      rfl
    have hUniq : Function.Injective (w.restName (B := B) (K := K)) :=
      hw.symm ▸ trieWiresAt_rest_injective l B K _ _
    have hAlloc (p : TrieRest B K) :
        l+B*K+1 ≤ w.restName p ∧ w.restName p < l+6*(B*K)+4 := by
      rw [hw]
      exact trieWiresAt_rest_bounds _ _ _ _ _ (by unfold B; positivity) (by unfold K; positivity) p
    obtain ⟨a',hFrame,_,hSat,hExact,hRows⟩ :=
      longTrieGates_complete a w B K (by unfold B; positivity) (by unfold K; positivity)
        dict label hDict
        (fun h => by rw [he]; exact wireValue_portWord a n t s _ ▸ hLabel h)
        (fun i hi => hRaw i (he ▸ hi)) hOn hUniq (fun p => (hAlloc p).1)
    refine ⟨a',?_,?_,?_,?_⟩
    · intro i hi
      have hTop : B*K ≤ layoutHorizon t := he ▸ hW
      have hFrame' : (i < w.flags ∨ w.flags+B*K+1 ≤ i) := by
        change i < l ∨ l+B*K+1 ≤ i
        unfold normalizeStride at hi
        rcases hi with hl | hh
        · exact .inl hl
        · exact .inr (by omega)
      exact hFrame i hFrame' (by
        rintro ⟨p,he⟩
        obtain ⟨hl,hu⟩ := hAlloc p
        unfold normalizeStride at hi
        change i < l ∨ l+6*layoutHorizon t+4 ≤ i at hi
        omega)
    · simpa only [normalizeWordGates,if_pos hLong] using hSat
    · have hBW : B ≤ W := Nat.pow_le_pow_right (by decide) hLong
      have hWidth : normalizeWidth b s = B+1 := by
        unfold normalizeWidth
        change min W B+1 = B+1
        rw [min_eq_right hBW]
      intro h
      rw [normalizeSlotLabel,hWidth]
      exact hExact h
    · simpa only [normalizeWordRows,if_pos hLong] using hRows
  · have hWidth : W ≤ B := Nat.pow_le_pow_right (by decide) (by omega)
    have hK : K=1 := by unfold K; rw [Nat.sub_eq_zero_of_le (by omega),pow_zero]
    have hAlloc (i : Fin (W+1)) : l ≤ w.label i.val ∧ w.label i.val < l+normalizeStride t := by
      have hi := i.isLt
      change l ≤ l+3*W+2+K+i.val ∧ l+3*W+2+K+i.val < l+6*layoutHorizon t+4
      omega
    obtain ⟨a',hFrame,hSat,hExact⟩ := shortTrieGates_witness a w W trieWiresAt_labels
      (fun i hi => by
        rintro ⟨k,hEq⟩
        have hL := (hAlloc k).1
        have hR := hRaw i hi
        omega)
    refine ⟨a',?_,?_,?_,?_⟩
    · intro i hi
      apply hFrame
      rintro ⟨p,he⟩
      obtain ⟨hl,hu⟩ := hAlloc p
      omega
    · simpa only [normalizeWordGates,if_neg hLong] using hSat
    · intro he
      have hLab : label = 2*portWord a n t s (5+5*r+f) := by
        have hs := (portWord_size a n t s (5+5*r+f)).trans hWidth
        have h := hLabel he
        cases h with
        | small _ => rfl
        | wide hu _ => omega
      have hw' : normalizeWidth b s = W+1 := by
        unfold normalizeWidth
        change min W B+1 = W+1
        rw [min_eq_left hWidth]
      rw [normalizeSlotLabel,hw',hLab,← wireValue_portWord]
      exact hExact
    · simp [normalizeWordRows,hLong]

end CNFEncComplexity.Robson

/- RobsonTrieFrame -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

/-- The names touched by a word are raw shared inputs or scratch variables
within that word's private interval. -/
def normalizeWordFrame (base n t : ℕ) (s : ℕ × ℕ) (r f k : ℕ) : Prop :=
  k < sharedLimit n t ∨
    normalizeWordBase base t s r f ≤ k ∧ k < normalizeWordBase base t s r f+normalizeStride t

theorem normalizeWordFrame_raw (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
    (hs : s ∈ layoutSlots t) (hr : r < 3) (hf : f < 3) :
    (∀ i < 2^s.2, (normalizeSlotWires base n t b s r f).raw i < sharedLimit n t) ∧
    (normalizeSlotWires base n t b s r f).present < sharedLimit n t := by
  rcases s with ⟨a,j⟩
  obtain ⟨ha,hj,-⟩ := layout_mem.mp hs
  have hj' : (2:ℕ)^j ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) hj
  refine ⟨?_,?_⟩
  · intro i hi
    exact port_lt_shared ha hj (by omega) (hi.trans_le hj')
  · exact port_lt_shared ha hj (by omega) (by unfold layoutHorizon; positivity)

theorem normalizeWordFrame_label (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
    (hs : s ∈ layoutSlots t) (i : ℕ) (hi : i < normalizeWidth b s) :
    normalizeWordBase base t s r f ≤ (normalizeSlotWires base n t b s r f).label i ∧
    (normalizeSlotWires base n t b s r f).label i <
      normalizeWordBase base t s r f+normalizeStride t := by
  let u := normalizeWordBase base t s r f
  let W := (2:ℕ)^s.2
  let K := (2:ℕ)^(s.2-b)
  have hk : K ≤ W := Nat.pow_le_pow_right (by decide) (Nat.sub_le ..)
  have hw : W ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) (layout_mem.mp hs).2.1
  have hi' : i ≤ W := le_trans (Nat.lt_succ_iff.mp hi) (min_le_left ..)
  change u ≤ u+3*W+2+K+i ∧ u+3*W+2+K+i < u+6*layoutHorizon t+4
  refine ⟨Nat.le_trans (Nat.le_trans (Nat.le_trans (Nat.le_add_right _ _) (Nat.le_add_right _ _))
    (Nat.le_add_right _ _)) (Nat.le_add_right _ _),?_⟩
  omega

theorem normalizedLongFrame_child (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
    (hs : s ∈ layoutSlots t) (hb : b ≤ s.2) (k i : ℕ)
    (hk : k < 2^(s.2-b)) (hi : i < 2^b) :
    normalizeWordBase base t s r f ≤ (normalizeSlotWires base n t b s r f).child k i ∧
    (normalizeSlotWires base n t b s r f).child k i <
      normalizeWordBase base t s r f+normalizeStride t := by
  have h := trieWiresAt_rest_bounds (normalizeWordBase base t s r f) (2^b) (2^(s.2-b))
    (port n t s (3+5*r) 0) (port n t s (5+5*r+f)) (by positivity) (by positivity)
    (.child ⟨k,hk⟩ ⟨i,hi⟩)
  simp only [TrieWordWires.restName] at h
  rw [normalizeChunkGeometry hb] at h
  have hw : (2:ℕ)^s.2 ≤ layoutHorizon t :=
    Nat.pow_le_pow_right (by decide) (layout_mem.mp hs).2.1
  exact ⟨(Nat.le_add_right _ _).trans (Nat.le_add_right _ _ |>.trans h.1),
    h.2.trans_le (by unfold normalizeStride; omega)⟩

theorem normalizeWordGates_frame (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
    (hs : s ∈ layoutSlots t) (hr : r < 3) (hf : f < 3)
    (g : Gate) (hg : g ∈ normalizeWordGates base n t b s r f) (name : ℕ)
    (hName : name ∈ CNFEncComplexity.Robson.Gate.names g) :
    normalizeWordFrame base n t s r f name := by
  let w := normalizeSlotWires base n t b s r f
  let u := normalizeWordBase base t s r f
  let B := (2:ℕ)^b
  let K := (2:ℕ)^(s.2-b)
  let W := (2:ℕ)^s.2
  let inside := normalizeWordFrame base n t s r f
  have hRaw (i : ℕ) (hi : i < W) : inside (w.raw i) :=
    .inl ((normalizeWordFrame_raw base n t b s r f hs hr hf).1 i hi)
  have hOn : inside w.present := .inl (normalizeWordFrame_raw base n t b s r f hs hr hf).2
  have hW : W ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) (layout_mem.mp hs).2.1
  have hFlag (i : ℕ) (hi : i ≤ W) : inside (w.mark i) := by
    right
    change u ≤ u+i ∧ u+i < u+6*layoutHorizon t+4
    omega
  have hLabel (i : ℕ) (hi : i < normalizeWidth b s) : inside (w.label i) :=
    .inr (normalizeWordFrame_label base n t b s r f hs i hi)
  by_cases hb : b ≤ s.2
  · have he : B*K=W := normalizeChunkGeometry hb
    have hx : B ≤ W := Nat.pow_le_pow_right (by decide) hb
    have hw : normalizeWidth b s = B+1 := by
      change min W B+1 = B+1
      rw [min_eq_right hx]
    have hRest (a : TrieRest B K) : inside (w.restName a) := by
      right
      have hh := trieWiresAt_rest_bounds u B K (port n t s (3+5*r) 0)
        (port n t s (5+5*r+f)) (by unfold B; positivity) (by unfold K; positivity) a
      rw [he] at hh
      change u+W+1 ≤ w.restName a ∧ w.restName a < u+6*W+4 at hh
      change u ≤ _ ∧ _ < u+6*layoutHorizon t+4
      exact ⟨(Nat.le_add_right _ _).trans ((Nat.le_add_right _ _).trans hh.1),hh.2.trans_le (by omega)⟩
    have hG : g ∈ longTrieGates w B K := by simpa [normalizeWordGates,hb] using hg
    simp only [longTrieGates,List.mem_append] at hG
    rcases hG with hG | hG
    · rcases hG with hG | hG
      · rcases hG with hG | hG
        · rcases List.mem_cons.mp hG with rfl|hA
          · have hm : name = w.mark (B*K) := by simpa [CNFEncComplexity.Robson.Gate.names,TrieWordWires.mark] using hName
            rw [hm]
            exact hFlag _ (le_of_eq he)
          · obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hA
            have hi' : i < W := by simpa [he] using List.mem_range.mp hi
            simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
            rcases hName with rfl|rfl|rfl
            · exact hFlag _ hi'.le
            · exact hRaw _ hi'
            · exact hFlag _ hi'
        · simp only [List.mem_cons,List.mem_nil_iff,or_false] at hG
          rcases hG with rfl|rfl
          · simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
            rcases hName with rfl|rfl|rfl
            · exact hRest .used
            · exact hOn
            · exact hFlag _ hx
          · simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
            rcases hName with rfl|rfl
            · exact hLabel _ (by rw [hw]; first | exact Nat.zero_lt_succ _ | exact Nat.succ_lt_succ hi')
            · exact hFlag _ hx
      · obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hG
        have hi' := List.mem_range.mp hi
        simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
        rcases hName with rfl|rfl|rfl|rfl
        · exact hLabel _ (by rw [hw]; first | exact Nat.zero_lt_succ _ | exact Nat.succ_lt_succ hi')
        · exact hFlag _ hx
        · exact hRest (.child ⟨0,by unfold K; positivity⟩ ⟨i,hi'⟩)
        · exact hRaw _ (hi'.trans_le hx)
    · obtain ⟨k,hk,hg⟩ := List.mem_flatMap.mp hG
      have hk' : k < K := List.mem_range.mp hk
      have hMul (j : ℕ) (hj : j ≤ K) : j*B ≤ W := by rw [← he,Nat.mul_comm B K]; exact Nat.mul_le_mul_right B hj
      rcases List.mem_cons.mp hg with rfl | hG
      · simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
        rcases hName with rfl|rfl|rfl
        · exact hRest (.emit ⟨k,hk'⟩)
        · exact hRest .used
        · exact hFlag _ (hMul _ hk'.le)
      · obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hG
        have hi' : i < B := List.mem_range.mp hi
        simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
        rcases hName with rfl|rfl|rfl|rfl
        · exact hRest (.parent ⟨k,hk'⟩ ⟨i,hi'⟩)
        · exact hFlag _ (hMul _ hk')
        · by_cases hNext : k+1 < K
          · change inside (if k+1 < K then w.child (k+1) i else w.mark (B*K))
            rw [if_pos hNext]
            exact hRest (.child ⟨k+1,hNext⟩ ⟨i,hi'⟩)
          · change inside (if k+1 < K then w.child (k+1) i else w.mark (B*K))
            rw [if_neg hNext]
            exact hFlag _ (le_of_eq he)
        · exact hFlag _ (le_of_eq he)
  · have hx : W ≤ B := Nat.pow_le_pow_right (by decide) (by omega)
    have hw : normalizeWidth b s = W+1 := by
      change min W B+1 = W+1
      rw [min_eq_left hx]
    have hG : g ∈ shortTrieGates w W := by simpa [normalizeWordGates,hb] using hg
    rcases List.mem_cons.mp hG with rfl|hA
    · have he : name = w.label 0 := by simpa [CNFEncComplexity.Robson.Gate.names,TrieWordWires.mark] using hName
      rw [he]
      exact hLabel _ (by rw [hw]; first | exact Nat.zero_lt_succ _ | exact Nat.succ_lt_succ hi')
    · obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hA
      have hi' := List.mem_range.mp hi
      simp only [CNFEncComplexity.Robson.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hName
      rcases hName with rfl|rfl
      · exact hLabel _ (by rw [hw]; first | exact Nat.zero_lt_succ _ | exact Nat.succ_lt_succ hi')
      · exact hRaw _ hi'

end CNFEncComplexity.Robson

/- RobsonTrieGlobalFrame -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

/-- End of the region reserved for all compact normalization words. -/
def normalizeAfter (base t : ℕ) : ℕ :=
  base+((layoutHorizon t*(layoutHeight t+1))*9)*normalizeStride t

def NormalizeKey (t : ℕ) := {s : ℕ × ℕ // s ∈ layoutSlots t} × Fin 3 × Fin 3

private def normalizeKeyIdx {t : ℕ} (k : NormalizeKey t) : ℕ :=
  ((k.1.val.1*(layoutHeight t+1)+k.1.val.2)*3+k.2.1.val)*3+k.2.2.val

private theorem normalize_key_mul_bounds {t : ℕ} (k : NormalizeKey t) :
    normalizeKeyIdx k+1 ≤ (layoutHorizon t*(layoutHeight t+1))*9 := by
  have hg := layout_mem.mp k.1.property
  have ha : (k.1.val.1+1)*(layoutHeight t+1) ≤ layoutHorizon t*(layoutHeight t+1) :=
    Nat.mul_le_mul_right _ hg.1
  rw [Nat.add_mul,Nat.one_mul] at ha
  have hj : k.1.val.2 ≤ layoutHeight t := hg.2.1
  have hr := k.2.1.isLt
  have hf := k.2.2.isLt
  unfold normalizeKeyIdx
  omega

def normalizeKeyBase (base t : ℕ) (k : NormalizeKey t) : ℕ :=
  normalizeWordBase base t k.1.val k.2.1.val k.2.2.val

theorem normalizeKeyBase_range (base t : ℕ) (k : NormalizeKey t) :
    base ≤ normalizeKeyBase base t k ∧ normalizeKeyBase base t k+normalizeStride t ≤ normalizeAfter base t := by
  refine ⟨normalizeWordBase_ge _ _ _ _ _,?_⟩
  have h := Nat.mul_le_mul_right (normalizeStride t) (normalize_key_mul_bounds k)
  rw [Nat.add_mul,Nat.one_mul] at h
  simpa [normalizeKeyBase,normalizeWordBase,normalizeAfter,normalizeKeyIdx,Nat.add_assoc] using
    Nat.add_le_add_left h base

private theorem numeral_injective {d a b i j : ℕ} (hi : i < d) (hj : j < d)
    (h : a*d+i = b*d+j) : a=b ∧ i=j := by
  have hp := Nat.zero_lt_of_lt hi
  have h' := congrArg (fun n => n / d) h
  have h'' := congrArg (fun n => n % d) h
  rw [Nat.add_comm (a*d) i,Nat.add_comm (b*d) j] at h' h''
  rw [Nat.add_mul_div_right _ _ hp,Nat.add_mul_div_right _ _ hp,
    Nat.div_eq_of_lt hi,Nat.div_eq_of_lt hj,Nat.zero_add,Nat.zero_add] at h'
  rw [Nat.add_mul_mod_self_right,Nat.add_mul_mod_self_right,Nat.mod_eq_of_lt hi,Nat.mod_eq_of_lt hj] at h''
  exact ⟨h',h''⟩

private theorem normalizeKeyIdx_injective (t : ℕ) : Function.Injective (@normalizeKeyIdx t) := by
  intro a b he
  unfold normalizeKeyIdx at he
  obtain ⟨h,j⟩ := numeral_injective a.2.2.isLt b.2.2.isLt he
  obtain ⟨h,i⟩ := numeral_injective a.2.1.isLt b.2.1.isLt h
  obtain ⟨ha,hb⟩ := numeral_injective
    (Nat.lt_succ_iff.mpr (layout_mem.mp a.1.property).2.1)
    (Nat.lt_succ_iff.mpr (layout_mem.mp b.1.property).2.1) h
  exact Prod.ext (Subtype.ext (Prod.ext ha hb)) (Prod.ext (Fin.ext i) (Fin.ext j))

theorem normalizeBlocks_unique {base t i : ℕ} {a b : NormalizeKey t}
    (ha : normalizeKeyBase base t a ≤ i ∧ i < normalizeKeyBase base t a+normalizeStride t)
    (hb : normalizeKeyBase base t b ≤ i ∧ i < normalizeKeyBase base t b+normalizeStride t) : a = b := by
  have hNo_lt (a b : NormalizeKey t) (h : normalizeKeyIdx a < normalizeKeyIdx b) :
      normalizeKeyBase base t a+normalizeStride t ≤ normalizeKeyBase base t b := by
    have h' : normalizeKeyIdx a+1 ≤ normalizeKeyIdx b := h
    have hh := Nat.mul_le_mul_right (normalizeStride t) h'
    rw [Nat.add_mul,Nat.one_mul] at hh
    simpa [normalizeKeyBase,normalizeWordBase,normalizeKeyIdx,Nat.add_assoc] using
      Nat.add_le_add_left hh base
  apply normalizeKeyIdx_injective t
  by_contra hh
  rcases Nat.lt_or_gt_of_ne hh with hh|hh
  · exact (not_lt_of_ge ((hNo_lt _ _ hh).trans hb.1)) ha.2
  · exact (not_lt_of_ge ((hNo_lt _ _ hh).trans ha.1)) hb.2

/-- Agreement on shared input names and the current word's interval suffices
to preserve every emitted numerical edge. -/
theorem normalizeWordRows_congr (a a' : Assignment) (base n t b : ℕ) (s : ℕ × ℕ) (r f : ℕ)
    (hs : s ∈ layoutSlots t) (hr : r < 3) (hf : f < 3)
    (h : ∀ i, normalizeWordFrame base n t s r f i → a i = a' i) :
    normalizeWordRows a base n t b s r f = normalizeWordRows a' base n t b s r f := by
  let w := normalizeSlotWires base n t b s r f
  let u := normalizeWordBase base t s r f
  let B := (2:ℕ)^b
  let K := (2:ℕ)^(s.2-b)
  let W := (2:ℕ)^s.2
  by_cases hb : b ≤ s.2
  · have he : B*K=W := normalizeChunkGeometry hb
    have hW : W ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) (layout_mem.mp hs).2.1
    have hRest (a : TrieRest B K) : normalizeWordFrame base n t s r f (w.restName a) := by
      right
      have hh := trieWiresAt_rest_bounds u B K (port n t s (3+5*r) 0)
        (port n t s (5+5*r+f)) (by unfold B; positivity) (by unfold K; positivity) a
      rw [he] at hh
      change u+W+1 ≤ w.restName a ∧ w.restName a < u+6*W+4 at hh
      exact ⟨(Nat.le_add_right _ _).trans ((Nat.le_add_right _ _).trans hh.1),
        hh.2.trans_le (by unfold normalizeStride; omega)⟩
    simp only [normalizeWordRows,if_pos hb,trieWordRows]
    change ((List.range K).filter fun k => a (w.emit k)).map (trieEdge a w B) =
      ((List.range K).filter fun k => a' (w.emit k)).map (trieEdge a' w B)
    have hSame : ((List.range K).filter fun k => a (w.emit k)) =
        ((List.range K).filter fun k => a' (w.emit k)) := by
      apply List.filter_congr
      intro k hk
      exact h _ (hRest (.emit ⟨k,List.mem_range.mp hk⟩))
    rw [hSame]
    apply List.map_congr_left
    intro k hk
    have hk' := List.mem_range.mp (List.mem_filter.mp hk).1
    have hBound : k*B+B ≤ W := by
      have hn := Nat.mul_le_mul_right B hk'
      simpa [Nat.succ_mul,Nat.mul_comm K B,he] using hn
    have hp : wireValue a (w.parent k) B = wireValue a' (w.parent k) B :=
      wireValue_congr (fun i hi => h _ (hRest (.parent ⟨k,hk'⟩ ⟨i,hi⟩)))
    have hc : wireValue a (w.child k) B = wireValue a' (w.child k) B :=
      wireValue_congr (fun i hi => h _ (hRest (.child ⟨k,hk'⟩ ⟨i,hi⟩)))
    have hg : wireValue a (fun i => w.raw (k*B+i)) B = wireValue a' (fun i => w.raw (k*B+i)) B :=
      wireValue_congr (fun i hi => h _ (.inl ((normalizeWordFrame_raw base n t b s r f hs hr hf).1
        (k*B+i) (by omega))))
    simp only [trieEdge,hp,hc,hg]
  · simp [normalizeWordRows,hb]

end CNFEncComplexity.Robson

/- RobsonTrieNative -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF Turing.MultiTapeTM
open Turing.MultiTapeTM.ComputableTidilyInPolyTime

section
variable {α : Type} {enc : α ↪ List Bool}

theorem trieMux_polytime {w sel : α → ℕ} {out yes no : α → ℕ → ℕ}
    (hw : ComputableTidilyInPolyTime w enc encUnary)
    (hsel : ComputableTidilyInPolyTime sel enc encUnary)
    (hout : ComputableTidilyInPolyTime (fun p : α × ℕ => out p.1 p.2) (encPair enc encUnary) encUnary)
    (hyes : ComputableTidilyInPolyTime (fun p : α × ℕ => yes p.1 p.2) (encPair enc encUnary) encUnary)
    (hno : ComputableTidilyInPolyTime (fun p : α × ℕ => no p.1 p.2) (encPair enc encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun x => trieMux (w x) (sel x) (out x) (yes x) (no x))
      enc (encList gateEnc) := by
  exact mapWithInput (f := fun x i => Gate.mux (out x i) (sel x) (yes x i) (no x i))
    (range.comp hw) (gate_mux hout (hsel.comp (fst enc encUnary)) hyes hno)

theorem normalizeShort_polytime {base W K B on : α → ℕ} {raw : α → ℕ → ℕ}
    (hBase : ComputableTidilyInPolyTime base enc encUnary)
    (hW : ComputableTidilyInPolyTime W enc encUnary)
    (hK : ComputableTidilyInPolyTime K enc encUnary)
    (hRaw : ComputableTidilyInPolyTime (fun p : α × ℕ => raw p.1 p.2) (encPair enc encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun x => shortTrieGates (trieWiresAt (base x) (W x) (K x)
      (B x) (raw x) (on x)) (W x)) enc (encList gateEnc) := by
  let L := fun x => base x + 3*W x + 2 + K x
  have hL : ComputableTidilyInPolyTime L enc encUnary := by
    unfold L
    fun_prop
  have hLabel : ComputableTidilyInPolyTime (fun p : α×ℕ => L p.1+(p.2+1))
      (encPair enc encUnary) encUnary := by fun_prop
  have hBlock := mapWithInput (f := fun x i => Gate.copy (L x+(i+1)) (raw x i))
    (range.comp hW) (gate_copy hLabel hRaw)
  simpa [shortTrieGates,trieWiresAt,wordCopy,L] using cons' (gate_pin false hL) hBlock

theorem normalizeLong_polytime {base B K on : α → ℕ} {raw : α → ℕ → ℕ}
    (hBase : ComputableTidilyInPolyTime base enc encUnary)
    (hB : ComputableTidilyInPolyTime B enc encUnary)
    (hK : ComputableTidilyInPolyTime K enc encUnary)
    (hOn : ComputableTidilyInPolyTime on enc encUnary)
    (hRaw : ComputableTidilyInPolyTime (fun p : α × ℕ => raw p.1 p.2) (encPair enc encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun x => longTrieGates
      (trieWiresAt (base x) (B x*K x) (K x) (B x) (raw x) (on x)) (B x) (K x))
      enc (encList gateEnc) := by
  let W := fun x => B x*K x
  let P := fun x => base x+W x+2+K x
  let C := fun x => base x+2*W x+2+K x
  let L := fun x => base x+3*W x+2+K x
  let U := fun x => base x+W x+1
  have hW : ComputableTidilyInPolyTime W enc encUnary := unary_mul.comp (hB.prod hK)
  have hP : ComputableTidilyInPolyTime P enc encUnary := by unfold P; fun_prop
  have hC : ComputableTidilyInPolyTime C enc encUnary := by unfold C; fun_prop
  have hL : ComputableTidilyInPolyTime L enc encUnary := by unfold L; fun_prop
  have hU : ComputableTidilyInPolyTime U enc encUnary := by unfold U; fun_prop
  have hWide : ComputableTidilyInPolyTime (fun x => base x+B x) enc encUnary := unary_add.comp (hBase.prod hB)
  have hWidth := widthCircuit_polytime hBase hW hRaw
  have hInit := cons' (gate_conj hU hOn hWide) (cons' (gate_copy hL hWide) (const []))
  have hLabel : ComputableTidilyInPolyTime (fun p : α×ℕ => L p.1+(p.2+1))
      (encPair enc encUnary) encUnary := by fun_prop
  have hFirst : ComputableTidilyInPolyTime (fun p : α×ℕ => C p.1+p.2)
      (encPair enc encUnary) encUnary := by fun_prop
  have hSelectLabel := trieMux_polytime (out := fun x i => L x+(i+1))
    (yes := fun x i => C x+i) (no := raw) hB hWide hLabel hFirst hRaw
  let e := encPair enc encUnary
  let e₂ := encPair e encUnary
  have hX := fst enc encUnary
  have hI := snd enc encUnary
  have hY := fst e encUnary
  have hJ := snd e encUnary
  have hX₂ := hX.comp hY
  have hI₂ := hI.comp hY
  have hEmit : ComputableTidilyInPolyTime (fun p : α×ℕ => base p.1 + W p.1 + 2 + p.2) e encUnary := by
    unfold e
    fun_prop
  have hUsed := hU.comp hX
  have hThis : ComputableTidilyInPolyTime (fun p : α×ℕ => base p.1+p.2*B p.1) e encUnary := by
    unfold e
    fun_prop
  have hNext : ComputableTidilyInPolyTime (fun p : α×ℕ => base p.1+(p.2+1)*B p.1) e encUnary := by
    unfold e
    fun_prop
  have hEnd : ComputableTidilyInPolyTime (fun p : α×ℕ => base p.1+W p.1) e encUnary := by
    unfold e
    fun_prop
  have hParent : ComputableTidilyInPolyTime (fun p : (α×ℕ)×ℕ =>
      P p.1.1+p.1.2*B p.1.1+p.2) e₂ encUnary := by
    unfold e₂ e
    fun_prop
  have hChild : ComputableTidilyInPolyTime (fun p : (α×ℕ)×ℕ =>
      C p.1.1+(p.1.2+1)*B p.1.1+p.2) e₂ encUnary := by
    unfold e₂ e
    fun_prop
  have hIsNext : ComputableTidilyInPolyTime (fun p : (α×ℕ)×ℕ => decide (p.1.2+1 < K p.1.1)) e₂ encBool :=
    unary_lt' (unary_add.comp (hI₂.prod (const 1))) (hK.comp hX₂)
  have hEnd₂ : ComputableTidilyInPolyTime (fun p : (α×ℕ)×ℕ => base p.1.1+W p.1.1)
      e₂ encUnary := hEnd.comp hY
  have hChildOrZero : ComputableTidilyInPolyTime (fun p : (α×ℕ)×ℕ =>
      if p.1.2+1 < K p.1.1 then C p.1.1+(p.1.2+1)*B p.1.1+p.2 else base p.1.1+W p.1.1) e₂ encUnary := by
    simpa only [decide_eq_true_eq] using hIsNext.ite' hChild hEnd₂
  have hStep := cons' (gate_conj hEmit hUsed hThis)
    (trieMux_polytime (out := fun p j => P p.1+p.2*B p.1+j)
      (yes := fun p j => if p.2+1 < K p.1 then C p.1+(p.2+1)*B p.1+j
        else base p.1+W p.1)
      (no := fun p _ => base p.1+W p.1)
      (hB.comp hX) hNext hParent hChildOrZero hEnd₂)
  have hAllSteps := flatMapWithInput
    (f := fun x k => trieStepGates (trieWiresAt (base x) (W x) (K x) (B x) (raw x) (on x))
      (B x) (K x) k) (range.comp hK)
    (by
      convert hStep using 1 <;> rfl)
  simpa [longTrieGates,trieWiresAt,TrieWordWires.mark,widthFlagWire,L,C,W,U] using
    listAppend' (listAppend' (listAppend' hWidth hInit) hSelectLabel) hAllSteps

end

end CNFEncComplexity.Robson

/- RobsonTrieNativeSlot -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

section
variable {A : Type} {enc : A ↪ List Bool}

theorem normalizeWordGates_polytime {base n t b a j r f : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base enc encUnary)
    (hN : ComputableTidilyInPolyTime n enc encUnary)
    (hT : ComputableTidilyInPolyTime t enc encUnary)
    (hB : ComputableTidilyInPolyTime b enc encUnary)
    (hA : ComputableTidilyInPolyTime a enc encUnary)
    (hJ : ComputableTidilyInPolyTime j enc encUnary)
    (hR : ComputableTidilyInPolyTime r enc encUnary)
    (hF : ComputableTidilyInPolyTime f enc encUnary)
    (hJL : ∀ x, j x ≤ layoutHeight (t x))
    (hBL : ∀ x, b x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x =>
      normalizeWordGates (base x) (n x) (t x) (b x) (a x,j x) (r x) (f x))
      enc (encList gateEnc) := by
  have hH := layoutHeight_poly.comp hT
  have hW := layoutHorizon_poly.comp hT
  have hL : ComputableTidilyInPolyTime (fun x => normalizeWordBase (base x) (t x) (a x,j x) (r x) (f x))
      enc encUnary := by
    unfold normalizeWordBase normalizeStride
    dsimp
    fun_prop
  have hOn : ComputableTidilyInPolyTime (fun x => port (n x) (t x) (a x,j x) (3+5*r x) 0) enc encUnary :=
    slotPort_poly hN hT hA hJ (by fun_prop) (const 0)
  have hX := fst enc encUnary
  have hI := snd enc encUnary
  have hField : ComputableTidilyInPolyTime (fun x => 5+5*r x+f x) enc encUnary := by fun_prop
  have hRaw := slotPort_poly (hN.comp hX) (hT.comp hX) (hA.comp hX) (hJ.comp hX)
    (hField.comp hX) hI
  have hPowJ := unary_pow2_of_bound hJ hW (fun x => Nat.pow_le_pow_right (by decide) (hJL x))
  have hPowB := unary_pow2_of_bound hB hW (fun x => Nat.pow_le_pow_right (by decide) (hBL x))
  have hExpK := unary_sub.comp (hJ.prod hB)
  have hPowK := unary_pow2_of_bound hExpK hW
    (fun x => Nat.pow_le_pow_right (by decide) ((Nat.sub_le (j x) (b x)).trans (hJL x)))
  let raw := fun x i => port (n x) (t x) (a x,j x) (5+5*r x+f x) i
  have hShort := normalizeShort_polytime (raw := raw) (B := fun x => 2^b x) (on := fun x =>
    port (n x) (t x) (a x,j x) (3+5*r x) 0) hL hPowJ hPowK hRaw
  have hLong := normalizeLong_polytime (raw := raw) hL hPowB hPowK hOn hRaw
  have hChoice := (unary_le' hB hJ).ite' hLong hShort
  convert hChoice using 1
  funext x
  by_cases hj : b x ≤ j x
  · simp [normalizeWordGates,normalizeSlotWires,hj,normalizeChunkGeometry hj,raw,Function.comp_def]
  · simp [normalizeWordGates,normalizeSlotWires,hj,raw,Function.comp_def]

theorem normalizeSlotGates_polytime {base n t b a j : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base enc encUnary)
    (hN : ComputableTidilyInPolyTime n enc encUnary)
    (hT : ComputableTidilyInPolyTime t enc encUnary)
    (hB : ComputableTidilyInPolyTime b enc encUnary)
    (hA : ComputableTidilyInPolyTime a enc encUnary)
    (hJ : ComputableTidilyInPolyTime j enc encUnary)
    (hJL : ∀ x, j x ≤ layoutHeight (t x))
    (hBL : ∀ x, b x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x =>
      normalizeSlotGates (base x) (n x) (t x) (b x) (a x,j x))
      enc (encList gateEnc) := by
  let e := encPair enc encUnary
  have hX := fst enc encUnary
  have hR := snd enc encUnary
  have hY := fst e encUnary
  have hF := snd e encUnary
  let left := hX.comp hY
  exact flatMapWithInput (f := fun x r =>
    (List.range 3).flatMap fun f =>
      normalizeWordGates (base x) (n x) (t x) (b x) (a x,j x) r f) (const (List.range 3))
    (flatMapWithInput (f := fun (p : A×ℕ) f =>
      normalizeWordGates (base p.1) (n p.1) (t p.1) (b p.1) (a p.1,j p.1) p.2 f)
      (const (List.range 3))
      (normalizeWordGates_polytime (hBase.comp left) (hN.comp left) (hT.comp left)
        (hB.comp left) (hA.comp left) (hJ.comp left) (hR.comp hY) hF
        (fun p => hJL p.1.1) (fun p => hBL p.1.1)))

end

def normalizeLayoutGates (base n t b : ℕ) : List Gate :=
  (layoutSlots t).flatMap (normalizeSlotGates base n t b)

theorem normalizeLayoutGates_polytime {A : Type} {enc : A ↪ List Bool} {base n t b : A → ℕ}
    (hBase : ComputableTidilyInPolyTime base enc encUnary)
    (hN : ComputableTidilyInPolyTime n enc encUnary)
    (hT : ComputableTidilyInPolyTime t enc encUnary)
    (hB : ComputableTidilyInPolyTime b enc encUnary)
    (hBL : ∀ x, b x ≤ layoutHeight (t x)) :
    ComputableTidilyInPolyTime (fun x => normalizeLayoutGates (base x) (n x) (t x) (b x))
      enc (encList gateEnc) := by
  let e := encPair encUnary encUnary
  have hX := fst enc e
  have hS := snd enc e
  have hA := (fst encUnary encUnary).comp hS
  have hJ := (snd encUnary encUnary).comp hS
  have hH := layoutHeight_poly.comp (hT.comp hX)
  have hMin := unary_min.comp (hJ.prod hH)
  have hList : ComputableTidilyInPolyTime (fun x => layoutSlots (t x)) enc (encList e) :=
    layoutSlots_poly.comp hT
  have hGate := normalizeSlotGates_polytime (hBase.comp hX) (hN.comp hX) (hT.comp hX)
    (hB.comp hX) hA hMin (fun _ => min_le_right ..) (fun p => hBL p.1)
  have hAll := flatMapWithInput (f := fun x (s : ℕ×ℕ) => normalizeSlotGates (base x) (n x) (t x)
    (b x) (s.1,min s.2 (layoutHeight (t x)))) hList hGate
  convert hAll using 1
  funext x
  apply List.flatMap_congr
  intro s hs
  have hj := (layout_mem.mp hs).2.1
  simp [min_eq_left hj]

end CNFEncComplexity.Robson

/- RobsonTrieGlobal -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

/-- The independently allocated per-word witnesses combine while keeping the
original shared interface and every subsequent circuit region fixed. -/
theorem normalizeLayout_complete (a : Assignment) (base n t b : ℕ)
    (hBase : sharedLimit n t ≤ base) (dict : List WordEdge) (lab : ℕ → ℕ)
    (hDict : ∀ e ∈ dict, e.child < 2^(2^b))
    (hLab : ∀ s ∈ layoutSlots t, ∀ r < 3, ∀ f < 3, a (port n t s (3+5*r) 0) = true →
      WordLabel (2^b) dict (portWord a n t s (5+5*r+f)) (lab (portWord a n t s (5+5*r+f)))) :
    ∃ a' : Assignment,
      (∀ i, i < base ∨ normalizeAfter base t ≤ i → a' i = a i) ∧
      (∀ g ∈ normalizeLayoutGates base n t b, g.Holds a') ∧
      (∀ s ∈ layoutSlots t, ∀ r < 3, ∀ f < 3, a (port n t s (3+5*r) 0) = true →
        normalizeSlotLabel a' base n t b s r f = lab (portWord a n t s (5+5*r+f))) ∧
      ∀ s ∈ layoutSlots t, ∀ r < 3, ∀ f < 3, ∀ e ∈ normalizeWordRows a' base n t b s r f, e ∈ dict := by
  classical
  let contains (k : NormalizeKey t) (i : ℕ) : Prop :=
    normalizeKeyBase base t k ≤ i ∧ i < normalizeKeyBase base t k+normalizeStride t
  have hh (k : NormalizeKey t) :
      ∃ β : Assignment, (∀ i, ¬contains k i → β i = a i) ∧
        (∀ g ∈ normalizeWordGates base n t b k.1.val k.2.1.val k.2.2.val, g.Holds β) ∧
        (a (port n t k.1.val (3+5*k.2.1.val) 0) = true →
          normalizeSlotLabel β base n t b k.1.val k.2.1.val k.2.2.val =
            lab (portWord a n t k.1.val (5+5*k.2.1.val+k.2.2.val))) ∧
        ∀ e ∈ normalizeWordRows β base n t b k.1.val k.2.1.val k.2.2.val, e ∈ dict := by
    obtain ⟨β,hFr,hs,hl,hE⟩ :=
      normalizeWord_complete a base n t b k.1.val k.2.1.val k.2.2.val hBase k.1.property
        k.2.1.isLt k.2.2.isLt dict _ hDict
        (hLab _ k.1.property _ k.2.1.isLt _ k.2.2.isLt)
    refine ⟨β,?_,hs,hl,hE⟩
    intro i hI
    apply hFr
    change ¬(normalizeKeyBase base t k ≤ i ∧ i < normalizeKeyBase base t k + normalizeStride t) at hI
    change i < normalizeKeyBase base t k ∨ normalizeKeyBase base t k + normalizeStride t ≤ i
    omega
  choose assign hFrame hHold hExact hRows using hh
  let a' : Assignment := fun i => if h : ∃ k, contains k i then assign h.choose i else a i
  have hFr (i : ℕ) (hi : i < base ∨ normalizeAfter base t ≤ i) : a' i = a i := by
    unfold a'
    apply dif_neg
    rintro ⟨k,hk⟩
    have hBounds := normalizeKeyBase_range base t k
    change normalizeKeyBase base t k ≤ i ∧ i < _ at hk
    omega
  have hA (k : NormalizeKey t) (i : ℕ)
      (hI : normalizeWordFrame base n t k.1.val k.2.1.val k.2.2.val i) : a' i = assign k i := by
    rcases hI with hLow | hIn
    · have hbl : i < base := hLow.trans_le hBase
      rw [hFr i (.inl hbl)]
      apply (hFrame k i ?_).symm
      intro h
      exact (not_le_of_gt (hbl.trans_le (normalizeKeyBase_range base t k).1)) h.1
    · have hI : contains k i := hIn
      have hEx : ∃ c, contains c i := ⟨k,hI⟩
      have hEq : hEx.choose = k := normalizeBlocks_unique hEx.choose_spec hI
      simp [a',hEx,hEq]
  refine ⟨a',hFr,?_,?_,?_⟩
  · intro g hg
    obtain ⟨s,hs,hg⟩ := List.mem_flatMap.mp hg
    obtain ⟨r,hr,hg⟩ := List.mem_flatMap.mp hg
    obtain ⟨f,hf,hg⟩ := List.mem_flatMap.mp hg
    let k : NormalizeKey t := (⟨s,hs⟩,⟨r,List.mem_range.mp hr⟩,⟨f,List.mem_range.mp hf⟩)
    refine (gate_congr (α := a') (β := assign k) g ?_).mpr (hHold k g hg)
    intro i hi
    exact hA k i (normalizeWordGates_frame base n t b s r f hs (List.mem_range.mp hr)
      (List.mem_range.mp hf) g hg i hi)
  · intro s hs r hr f hf hv
    let k : NormalizeKey t := (⟨s,hs⟩,⟨r,hr⟩,⟨f,hf⟩)
    refine Eq.trans ?_ (hExact k hv)
    apply wireValue_congr
    intro i hi
    exact hA k _ (.inr (normalizeWordFrame_label base n t b s r f hs i hi))
  · intro s hs r hr f hf e hE
    let k : NormalizeKey t := (⟨s,hs⟩,⟨r,hr⟩,⟨f,hf⟩)
    have hEq := normalizeWordRows_congr a' (assign k) base n t b s r f hs hr hf (hA k)
    exact hRows k e (hEq ▸ hE)

theorem normalizeLayoutGates_length (base n t b : ℕ) :
    (normalizeLayoutGates base n t b).length ≤ 72*(layoutHorizon t*(layoutHeight t+1)) := by
  have aux (ls : List (ℕ×ℕ)) : (ls.flatMap (normalizeSlotGates base n t b)).length ≤
      72*(ls.map fun s => 2^s.2).sum := by
    induction ls with
    | nil => simp
    | cons s ls ih =>
      rw [List.flatMap_cons,List.length_append,List.map_cons,List.sum_cons,Nat.mul_add]
      exact Nat.add_le_add (normalizeSlotGates_length base n t b s) ih
  unfold normalizeLayoutGates
  have h := layoutSlots_totalWidth_le t
  exact (aux _).trans (Nat.mul_le_mul_left _ (by simpa only [Nat.mul_comm] using h))

end CNFEncComplexity.Robson

/- RobsonTrieIntegration -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

theorem normalizedWord_mem_input (a : Assignment) (n t : ℕ) (s : ℕ×ℕ) (hs : s ∈ layoutSlots t)
    (r f : ℕ) (hr : r < 3) (hf : f < 3)
    (hv : a (port n t s (3+5*r) 0) = true) :
    portWord a n t s (5+5*r+f) ∈ observationWords (memoryStream a n t) := by
  let row : ObservedAccess :=
    ⟨⟨portWord a n t s (3+5*r+2),portWord a n t s (3+5*r+3),
      a (port n t s (3+5*r+1) 0)⟩,portWord a n t s (3+5*r+4)⟩
  have hr' : portMemory a n t s r = some row := by simp [portMemory,hv,row]
  have hPos : row ∈ (List.range 3).filterMap (portMemory a n t s) :=
    List.mem_filterMap.mpr ⟨r,List.mem_range.mpr hr,hr'⟩
  have hMem : row ∈ memoryStream a n t :=
    List.mem_flatMap.mpr ⟨s,hs,hPos⟩
  apply List.mem_flatMap.mpr
  refine ⟨row,hMem,?_⟩
  interval_cases f <;> simp [row] <;> first
  | left; congr 1; omega
  | right; left; congr 1; omega
  | right; right; congr 1; omega

theorem normalizeWord_name_below {base n t : ℕ}
    (hs : sharedLimit n t ≤ base) {s : ℕ×ℕ} (hS : s ∈ layoutSlots t) {r f i : ℕ}
    (hr : r < 3) (hf : f < 3) (hi : normalizeWordFrame base n t s r f i) :
    i < normalizeAfter base t := by
  have hBounds := normalizeKeyBase_range base t (⟨s,hS⟩,⟨r,hr⟩,⟨f,hf⟩)
  rcases hi with hh | hh
  · exact (hh.trans_le hs).trans_le (hBounds.1.trans ((Nat.le_add_right _ _).trans hBounds.2))
  · exact hh.2.trans_le hBounds.2

theorem normalizeSlotLabel_frame (a α : Assignment) (base n t b : ℕ)
    (hBase : sharedLimit n t ≤ base) (s : ℕ×ℕ)
    (hs : s ∈ layoutSlots t) (r f : ℕ) (hr : r < 3) (hf : f < 3)
    (hFrame : ∀ i < normalizeAfter base t, a i = α i) :
    normalizeSlotLabel a base n t b s r f = normalizeSlotLabel α base n t b s r f := by
  unfold normalizeSlotLabel
  apply wireValue_congr
  intro i hi
  exact hFrame _ (normalizeWord_name_below hBase hs hr hf
    (.inr (normalizeWordFrame_label base n t b s r f hs i hi)))

theorem slotCompactMemory_witness (a α : Assignment) (base n t b : ℕ) (s : ℕ×ℕ)
    (hs : s ∈ layoutSlots t) (r : ℕ) (hr : r < 3) (lab : ℕ → ℕ)
    (hFrame : ∀ i < sharedLimit n t, α i = a i)
    (hLabel : ∀ f < 3, a (port n t s (3+5*r) 0)=true →
      normalizeSlotLabel α base n t b s r f = lab (portWord a n t s (5+5*r+f))) :
    slotCompactMemory α base n t b s r = (portMemory a n t s r).map (compactRow lab) := by
  have hPort (f : ℕ) (hF : f < 19) : port n t s f 0 < sharedLimit n t := by
    rcases s with ⟨start,j⟩
    have hh := layout_mem.mp hs
    exact port_lt_shared hh.1 hh.2.1 hF (by unfold layoutHorizon; positivity)
  unfold slotCompactMemory portMemory
  rw [hFrame _ (hPort _ (by omega)), hFrame _ (hPort _ (by omega))]
  by_cases h : a (port n t s (3+5*r) 0) = true
  · have h0 := hLabel 0 (by decide) h
    have h1 := hLabel 1 (by decide) h
    have h2 := hLabel 2 (by decide) h
    have hh0 : 5+5*r+0 = 3+5*r+2 := by omega
    have hh1 : 5+5*r+1 = 3+5*r+3 := by omega
    have hh2 : 5+5*r+2 = 3+5*r+4 := by omega
    rw [hh0] at h0
    rw [hh1] at h1
    rw [hh2] at h2
    simp only [h,if_true,Option.map_some,h0,h1,h2,compactRow]
  · simp only [h,Bool.false_eq_true,if_false,Option.map_none]

end CNFEncComplexity.Robson

/- RobsonMemLanesLocal -/

namespace CNFEncComplexity.Robson

open CookLevin

def memoryTierSlots (t j : ℕ) : List (ℕ × ℕ) :=
  (layoutSlots t).filter fun s => j-2 ≤ s.2

def memoryTierRows (t j : ℕ) : ℕ := 6*(memoryTierSlots t j).length

def memoryGroupCap (j : ℕ) : ℕ := 2^(2^j)

def memoryGroupCount (t j : ℕ) : ℕ := memoryTierRows t j / memoryGroupCap j + 1

theorem memoryTierRows_width (t j : ℕ) : memoryTierRows t j * 2^j ≤ 48*layoutHorizon t := by
  have h := slotsAtLeast_bound t (j-2)
  have hD := Nat.div_mul_le_self (2*layoutHorizon t) (2^(j-2))
  have hW : 2^j ≤ 4*2^(j-2) := by
    have hh : j ≤ 2+(j-2) := by omega
    simpa [pow_add] using Nat.pow_le_pow_right (by decide : 0 < (2:ℕ)) hh
  unfold memoryTierRows memoryTierSlots
  calc
    6 * _ * 2^j ≤ 6 * ((2*layoutHorizon t)/2^(j-2)) * (4*2^(j-2)) :=
      Nat.mul_le_mul (Nat.mul_le_mul_left _ h) hW
    _ = 24*(((2*layoutHorizon t)/2^(j-2))*2^(j-2)) := by ring
    _ ≤ 48*layoutHorizon t := (Nat.mul_le_mul_left 24 hD).trans_eq (by ring)

theorem memoryGroupCount_cap (t j : ℕ) :
    memoryTierRows t j ≤ memoryGroupCap j * memoryGroupCount t j := by
  have hq : 0 < memoryGroupCap j := by unfold memoryGroupCap; positivity
  have hMod := Nat.mod_lt (memoryTierRows t j) hq
  have hDiv := Nat.div_add_mod (memoryTierRows t j) (memoryGroupCap j)
  unfold memoryGroupCount
  rw [Nat.mul_add,Nat.mul_one]
  omega

/-- Compressed observations retain the source chronology and are small enough
to use both the global label bound and the original slot width. -/
structure PackedSlots (α : Assignment) (n t b : ℕ) (dict : List WordEdge)
    (packed : (ℕ×ℕ) → List ObservedAccess) : Prop where
  labels : ∀ s ∈ layoutSlots t, List.Forall₂ (ObservedLabels b dict) (slotRows α n t s) (packed s)
  widths : ∀ s ∈ layoutSlots t, ∀ r ∈ packed s,
    r.action.address.size ≤ min (2^s.2) b+1 ∧
    r.action.value.size ≤ min (2^s.2) b+1 ∧ r.old.size ≤ min (2^s.2) b+1

def packMemoryStream (t : ℕ) (packed : (ℕ×ℕ) → List ObservedAccess) : List ObservedAccess :=
  (layoutSlots t).flatMap packed

private theorem atTier_append' (j : ℕ) (ps qs : List TierRecord) :
    atTier j (ps++qs) = atTier j ps ++ atTier j qs := by
  simp [atTier,List.filter_append]

private theorem tieredObs_append (l r : List ObservedAccess) :
    tieredObservations bitTier (l++r) = tieredObservations bitTier l ++ tieredObservations bitTier r := by
  simp [tieredObservations,List.flatMap_append]

private theorem lane_padding {A : Type} (l : List A) (n : ℕ) :
    ((l.map some) ++ List.replicate n none).filterMap id = l := by
  rw [List.filterMap_append,List.filterMap_map]
  have hx : (List.replicate n (none : Option A)).filterMap id = [] := by
    apply List.filterMap_eq_nil_iff.mpr
    intro a ha
    exact List.eq_of_mem_replicate ha
  simp [hx]

def perSlotTierRows (j : ℕ) (rows : List ObservedAccess) : List (Option LocalRecord) :=
  let l := atTier j (tieredObservations bitTier rows)
  (l.map some) ++ List.replicate (6-l.length) none

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

private theorem packed_length {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
    {p : (ℕ×ℕ) → List ObservedAccess} (h : PackedSlots α n t b dict p)
    {s : ℕ×ℕ} (hs : s ∈ layoutSlots t) : (p s).length ≤ 3 := by
  have hL := (h.labels s hs).length_eq
  rw [← hL]
  simpa [slotRows] using (List.length_filterMap_le (f := portMemory α n t s) (l:=List.range 3))

theorem memoryTierLanes_length {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
    {p : (ℕ×ℕ) → List ObservedAccess} (h : PackedSlots α n t b dict p) (j : ℕ) :
    (memoryTierLanes t j p).length = memoryTierRows t j := by
  have hLength (xs : List (ℕ×ℕ)) (hx : ∀ s ∈ xs, s ∈ layoutSlots t) :
      (xs.flatMap (fun s => perSlotTierRows j (p s))).length = 6*xs.length := by
    induction xs with
    | nil => rfl
    | cons s ss ih =>
      have hS := packed_length h (hx s (by simp))
      have hh := tieredObservations_length bitTier (p s)
      have hF : (atTier j (tieredObservations bitTier (p s))).length ≤
          (tieredObservations bitTier (p s)).length := by
        simpa [atTier] using List.length_filter_le
          (fun r : TierRecord => r.addr.1=j) (tieredObservations bitTier (p s))
      rw [List.flatMap_cons,List.length_append,List.length_cons,
        ih (fun s hs => hx s (List.mem_cons_of_mem _ hs))]
      simp only [perSlotTierRows,List.length_append,List.length_map,List.length_replicate]
      omega
  exact hLength _ (fun s hs => (List.mem_filter.mp hs).1)

private theorem packed_eligible {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
    {p : (ℕ×ℕ) → List ObservedAccess} (h : PackedSlots α n t b dict p)
    {s : ℕ×ℕ} (hs : s ∈ layoutSlots t) {r : TierRecord}
    (hr : r ∈ tieredObservations bitTier (p s)) : r.addr.1 ≤ s.2+2 := by
  obtain ⟨obs,ho,hMem⟩ := List.mem_flatMap.mp hr
  obtain ⟨ha,hv,hold⟩ := h.widths s hs obs ho
  have hm : min (2^s.2) b + 1 ≤ 2^s.2+1 := Nat.add_le_add_right (min_le_left _ _) _
  have hx := tieredRow_eligible (s:=s) (r:=obs) (f:=id) (ha.trans hm) (hv.trans hm) (hold.trans hm)
  exact hx r hMem

theorem memoryTierLanes_projection {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
    {p : (ℕ×ℕ) → List ObservedAccess} (h : PackedSlots α n t b dict p) (j : ℕ) :
    (memoryTierLanes t j p).filterMap id =
      atTier j (tieredObservations bitTier (packMemoryStream t p)) := by
  have hProj (xs : List (ℕ×ℕ)) (hx : ∀ s ∈ xs, s ∈ layoutSlots t) :
      (((xs.filter fun s => j-2 ≤ s.2).flatMap (fun s => perSlotTierRows j (p s))).filterMap id) =
        atTier j (tieredObservations bitTier (xs.flatMap p)) := by
    induction xs with
    | nil => rfl
    | cons s ss ih =>
      have ht := ih (fun r hr => hx r (List.mem_cons_of_mem _ hr))
      rw [List.flatMap_cons,tieredObs_append,atTier_append']
      by_cases hj : j-2 ≤ s.2
      · simp only [List.filter_cons,decide_eq_true_eq,hj,if_true,List.flatMap_cons,
          List.filterMap_append,ht]
        have he : (perSlotTierRows j (p s)).filterMap id =
            atTier j (tieredObservations bitTier (p s)) := lane_padding _ _
        rw [he]
      · have hEmpty : atTier j (tieredObservations bitTier (p s)) = [] := by
          unfold atTier
          have hFilter : ((tieredObservations bitTier (p s)).filter fun r => r.addr.1=j) = [] := by
            apply List.filter_eq_nil_iff.mpr
            intro r hr
            have hh := packed_eligible h (hx s (by simp)) hr
            have hne : r.addr.1 ≠ j := by omega
            simp [hne]
          simp [hFilter]
        simp only [List.filter_cons,decide_eq_true_eq,hj,if_false,ht,hEmpty,List.nil_append]
  exact hProj _ (fun _ hs => hs)

private theorem related_append {A B : Type} {R : A → B → Prop}
    {l m : List A} {l' m' : List B} (h : List.Forall₂ R l l') (h' : List.Forall₂ R m m') :
    List.Forall₂ R (l++m) (l'++m') := by
  induction h with
  | nil => exact h'
  | cons hr _ ih => exact .cons hr ih

private theorem packMemory_labels {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
    {p : (ℕ×ℕ) → List ObservedAccess} (h : PackedSlots α n t b dict p) :
    List.Forall₂ (ObservedLabels b dict) (memoryStream α n t) (packMemoryStream t p) := by
  have hJoin (ls : List (ℕ×ℕ)) (hm : ∀ s ∈ ls, s ∈ layoutSlots t) :
      List.Forall₂ (ObservedLabels b dict) (ls.flatMap (slotRows α n t)) (ls.flatMap p) := by
    induction ls with
    | nil => exact .nil
    | cons s ss ih =>
      exact related_append (h.labels s (hm s (by simp)))
        (ih (fun r hr => hm r (List.mem_cons_of_mem _ hr)))
  exact hJoin _ (fun _ hs => hs)

theorem memoryTierLanes_exact {α : Assignment} {n t b : ℕ} {dict : List WordEdge}
    {p : (ℕ×ℕ) → List ObservedAccess} (h : PackedSlots α n t b dict p)
    (good : WordEdge.Interned dict) :
    observedMemoryValid (fun _ => 0) (memoryStream α n t) ↔
      ∀ j < (b+1).size+1,
        TierBatchCertificate (memoryGroupCap j) (memoryGroupCount t j) (memoryTierLanes t j p)
          (fun a => liveMemory bitTier (fun _ => 0) (j,a)) := by
  have hFits : ∀ r ∈ tieredObservations bitTier (packMemoryStream t p), TierRecordFits (b+1) r := by
    intro r hr
    obtain ⟨o,ho,hex⟩ := List.mem_flatMap.mp hr
    obtain ⟨s,hs,ho'⟩ := List.mem_flatMap.mp ho
    obtain ⟨ha,hv,hold⟩ := h.widths s hs o ho'
    have hm : min (2^s.2) b+1 ≤ b+1 := Nat.add_le_add_right (min_le_right _ _) _
    exact tieredAccess_fits (ha.trans hm) (hv.trans hm) (hold.trans hm) r hex
  exact observed_compactBatches_iff good (packMemory_labels h) hFits (memoryGroupCount t)
    (fun j => memoryTierLanes t j p) (fun j _ => memoryTierLanes_projection h j)
    (fun j _ => (memoryTierLanes_length h j).trans_le (memoryGroupCount_cap t j))

end CNFEncComplexity.Robson

/- RobsonTierBridge -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

theorem sorterTierCertificate_eq (R w tier : ℕ) (src : ℕ → ℕ → ℕ) (a : Assignment) :
    sorterTierCertificate R w tier src a ↔
    TierBatchCertificate (2^w) (R/2^w+1) (rawMemoryRows a w R src) (groupInitial (some tier)) := by
  by_cases hs : R ≤ 2^w
  · simp [sorterTierCertificate,TierBatchCertificate,rawMemoryRows,hs]
  · simp [sorterTierCertificate,TierBatchCertificate,rawMemoryRows,hs,sorterCount_split hs]

theorem tierBatch_mission_certificate (t j base z o : ℕ) (src : ℕ → ℕ → ℕ) (a : Assignment)
    (hzBase : z < base) (hoBase : o < base)
    (hData : ∀ i < memoryTierRows t j, ∀ k < memLaneWidth (2^j) 0, src i k < base)
    (hz : a z = false) (ho : a o = true) :
    (∃ b : Assignment,
      (∀ k, k < base ∨ sorterTierTop (memoryTierRows t j) (2^j) base ≤ k → b k = a k) ∧
      (∀ g ∈ tierBatchGates (memoryTierRows t j) (2^j) j base z o src, g.Holds b)) ↔
    TierBatchCertificate (memoryGroupCap j) (memoryGroupCount t j)
      (rawMemoryRows a (2^j) (memoryTierRows t j) src) (groupInitial (some j)) :=
  (tierBatchGates_exact _ _ _ _ _ _ _ _ hzBase hoBase hData hz ho (bitTier_initial_restricted j)).trans
    (sorterTierCertificate_eq ..)

theorem tierBatchGates_layout_budget (t j base z o : ℕ) (src : ℕ → ℕ → ℕ) :
    (tierBatchGates (memoryTierRows t j) (2^j) j base z o src).length ≤ 393216*layoutHorizon t*2^j := by
  calc
    _ ≤ 8192*memoryTierRows t j*2^j*2^j := tierBatchGates_budget _ _ _ _ _ _ _ (Nat.two_pow_pos _)
    _ = (8192*(memoryTierRows t j*2^j))*2^j := by ring
    _ ≤ (8192*(48*layoutHorizon t))*2^j :=
      Nat.mul_le_mul_right _ (Nat.mul_le_mul_left _ (memoryTierRows_width t j))
    _ = _ := by ring

private theorem sorter_sum_geometric (n : ℕ) : (∑ j ∈ Finset.range n, (2:ℕ)^j) ≤ 2^n := by
  induction n with
  | zero => simp
  | succ n ih =>
    rw [Finset.sum_range_succ,pow_succ]
    omega

theorem tierBatchGates_total_budget (t b : ℕ) (cost : ℕ → ℕ)
    (hCost : ∀ j < (b+1).size+1, cost j ≤ 393216*layoutHorizon t*2^j) :
    (∑ j ∈ Finset.range ((b+1).size+1), cost j) ≤ 1572864*layoutHorizon t*(b+1)+786432*layoutHorizon t := by
  have h := Nat.size_pos.mpr (show 0 < b+1 by omega)
  have hp : 2^(b+1).size ≤ 2*(b+1)+1 := by
    have hk : (b+1).size-1 < (b+1).size := by omega
    have hsmall := Nat.lt_size.mp hk
    calc
      _ = 2^((b+1).size-1)*2 := by conv_lhs => rw [show (b+1).size = (b+1).size-1+1 by omega]; rw [pow_succ]
      _ ≤ _ := by omega
  calc
    _ ≤ ∑ j ∈ Finset.range ((b+1).size+1), 393216*layoutHorizon t*2^j :=
      Finset.sum_le_sum fun j hj => hCost j (Finset.mem_range.mp hj)
    _ = (393216*layoutHorizon t)*(∑ j ∈ Finset.range ((b+1).size+1), 2^j) := by rw [Finset.mul_sum]
    _ ≤ (393216*layoutHorizon t)*2^((b+1).size+1) :=
      Nat.mul_le_mul_left _ (sorter_sum_geometric _)
    _ = (786432*layoutHorizon t)*2^(b+1).size := by rw [pow_succ]; ring
    _ ≤ (786432*layoutHorizon t)*(2*(b+1)+1) := Nat.mul_le_mul_left _ hp
    _ = _ := by ring

end CNFEncComplexity.Robson

/- RobsonTierBatchNative -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

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

set_option maxHeartbeats 1000000 in
theorem tierWindowGates_polytime {R w tier base z o g : A → ℕ} {src : A → ℕ → ℕ → ℕ}
    (hr : ComputableTidilyInPolyTime R e encUnary)
    (hw : ComputableTidilyInPolyTime w e encUnary)
    (ht : ComputableTidilyInPolyTime tier e encUnary)
    (hb : ComputableTidilyInPolyTime base e encUnary)
    (hz : ComputableTidilyInPolyTime z e encUnary)
    (ho : ComputableTidilyInPolyTime o e encUnary)
    (hg : ComputableTidilyInPolyTime g e encUnary)
    (hs : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => src p.1.1 p.1.2 p.2)
      (encPair (encPair e encUnary) encUnary) encUnary) :
    ComputableTidilyInPolyTime
      (fun a => tierWindowGates (R a) (w a) (tier a) (base a) (z a) (o a) (src a) (g a)) e
      (encList gateEnc) := by
  let e₁ := encPair e encUnary
  let e₂ := encPair e₁ encUnary
  let e₃ := encPair e₂ encUnary
  let e₄ := encPair e₃ encUnary
  let e₅ := encPair e₄ encUnary
  let f₁ := fst e encUnary
  let f₂ := fst e₁ encUnary
  let f₃ := fst e₂ encUnary
  let f₄ := fst e₃ encUnary
  let f₅ := fst e₄ encUnary
  let a := f₁.comp f₂
  let i := (snd e encUnary).comp f₂
  let j := snd e₁ encUnary
  let p := a.comp (f₃.comp (f₄.comp f₅))
  let k := (snd e₂ encUnary).comp (f₄.comp f₅)
  let u := (snd e₃ encUnary).comp f₅
  let b := snd e₄ encUnary
  have hSnap : ComputableTidilyInPolyTime
      (fun q : (((((A×ℕ)×ℕ)×ℕ)×ℕ)×ℕ) =>
        sorterSnapshotName (R q.1.1.1.1.1) (w q.1.1.1.1.1) (base q.1.1.1.1.1) q.1.1.2 q.1.2 q.2)
      e₅ encUnary :=
    sorterSnapshotName_poly (hr.comp p) (hw.comp p) (hb.comp p) k u b
  let proj : ComputableTidilyInPolyTime
      (fun q : (((A×ℕ)×ℕ)×ℕ)×ℕ => ((q.1.1.1.1,q.1.2),q.2)) e₄ e₂ :=
    (((a.comp (f₃.comp f₄)).prod ((snd e₂ encUnary).comp f₄))).prod (snd e₃ encUnary)
  have hData := hs.comp proj
  have hSrc : ComputableTidilyInPolyTime (fun q : (A×ℕ)×ℕ =>
        memoryWindowSource (w q.1.1) (tier q.1.1) (sorterCappedCap (R q.1.1) (w q.1.1))
          (R q.1.1) (g q.1.1) (z q.1.1) (o q.1.1) (src q.1.1)
          (sorterSnapshotName (R q.1.1) (w q.1.1) (base q.1.1)) q.1.2 q.2) e₂ encUnary :=
    memoryWindowSource_poly (A := (A×ℕ)×ℕ) (e := e₂) (src := fun p => src p.1.1)
      (snap := fun p => sorterSnapshotName (R p.1.1) (w p.1.1) (base p.1.1))
      (hw.comp a) (ht.comp a) ((sorterCappedCap_poly hr hw).comp a)
      (hr.comp a) (hg.comp a) (hz.comp a) (ho.comp a) i j hData hSnap
  unfold tierWindowGates
  exact memSortGates_polytime (A := A) (e := e)
    (src := fun a i j => memoryWindowSource (w a) (tier a) (sorterCappedCap (R a) (w a))
      (R a) (g a) (z a) (o a) (src a) (sorterSnapshotName (R a) (w a) (base a)) i j)
    hw (sorterHeight_poly hr hw) (sorterGroupBase_poly hr hw hb hg) (sorterTierCode_poly hr hw ht)
    (sorterWires_poly hr hw) hSrc

theorem tierBatchGates_polytime {R w tier base z o : A → ℕ} {src : A → ℕ → ℕ → ℕ}
    (hr : ComputableTidilyInPolyTime R e encUnary)
    (hw : ComputableTidilyInPolyTime w e encUnary)
    (ht : ComputableTidilyInPolyTime tier e encUnary)
    (hb : ComputableTidilyInPolyTime base e encUnary)
    (hz : ComputableTidilyInPolyTime z e encUnary)
    (ho : ComputableTidilyInPolyTime o e encUnary)
    (hs : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => src p.1.1 p.1.2 p.2)
      (encPair (encPair e encUnary) encUnary) encUnary) :
    ComputableTidilyInPolyTime
      (fun a => tierBatchGates (R a) (w a) (tier a) (base a) (z a) (o a) (src a)) e
      (encList gateEnc) := by
  let e₁ := encPair e encUnary
  let e₂ := encPair e₁ encUnary
  let a := fst e encUnary
  let f₁ := fst e₁ encUnary
  let f₂ := fst e₂ encUnary
  have hData := hs.comp (((a.comp (f₁.comp f₂)).prod ((snd e₁ encUnary).comp f₂)).prod
    (snd e₂ encUnary))
  unfold tierBatchGates
  exact flatMapWithInput
    (f := fun a g => tierWindowGates (R a) (w a) (tier a) (base a) (z a) (o a) (src a) g)
    (range.comp (sorterCount_poly hr hw))
    (tierWindowGates_polytime (A := A×ℕ) (e := e₁) (src := fun p => src p.1)
      (hr.comp a) (hw.comp a) (ht.comp a) (hb.comp a) (hz.comp a)
      (ho.comp a) (snd e encUnary) hData)

end
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