Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Correctness of the trie dictionary for RAM word labels

Definition
CNFEncComplexity_RobsonMemoryTrieDictionarySoundness

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

complexity-theorysatisfiability

The pooled trie verifies both functional dependencies. Its gates exactly certify injective packed labels for all observed memory words.

Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryTrieSlots

set_option maxHeartbeats 4000000
set_option linter.all false

/- RobsonTrieSort -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

structure TrieRowPort where
  present : ℕ
  parent : ℕ → ℕ
  digit : ℕ → ℕ
  child : ℕ → ℕ

def TrieRowPort.edge (a : Assignment) (B : ℕ) (r : TrieRowPort) : WordEdge :=
  ⟨wireValue a r.parent B,wireValue a r.digit B,wireValue a r.child B⟩

def TrieRowPort.decode (a : Assignment) (B : ℕ) (r : TrieRowPort) : Option WordEdge :=
  if a r.present then some (r.edge a B) else none

def packTrieKey (B : ℕ) (e : WordEdge) : ℕ := e.digit+2^B*e.parent

theorem packTrieKey_eq {B : ℕ} {e f : WordEdge}
    (he : e.digit < 2^B) (hf : f.digit < 2^B) :
    packTrieKey B e = packTrieKey B f ↔ e.key = f.key := by
  have hp : 0 < (2:ℕ)^B := by positivity
  constructor
  · intro h
    have hd : e.digit = f.digit := by
      have hmod := congrArg (fun n => n % 2^B) h
      simpa [packTrieKey,Nat.add_mod,Nat.mod_eq_of_lt he,Nat.mod_eq_of_lt hf] using hmod
    have hpa : e.parent = f.parent := by
      unfold packTrieKey at h
      rw [hd,Nat.add_left_cancel_iff] at h
      exact Nat.eq_of_mul_eq_mul_left hp h
    exact Prod.ext hpa hd
  · intro h
    have h1 := congrArg Prod.fst h
    have h2 := congrArg Prod.snd h
    change e.parent = f.parent at h1
    change e.digit = f.digit at h2
    simp [packTrieKey,h1,h2]

/-- Two passes order by different parts of the same edge record. -/
def trieSortPrimary (B : ℕ) (byChild : Bool) (e : WordEdge) : ℕ :=
  if byChild then e.child else packTrieKey B e

def trieSortPayload (B : ℕ) (byChild : Bool) (e : WordEdge) : ℕ :=
  trieSortPrimary B (!byChild) e

def trieSortWire (B : ℕ) (byChild : Bool) (r : TrieRowPort) : ℕ → ℕ :=
  if byChild then r.child else joinKey r.digit r.parent B

def trieSortWidth (B : ℕ) (byChild : Bool) : ℕ := if byChild then B else B+B

theorem trieSortWire_value (a : Assignment) (B : ℕ) (c : Bool) (r : TrieRowPort) :
    wireValue a (trieSortWire B c r) (trieSortWidth B c) =
      trieSortPrimary B c (r.edge a B) := by
  cases c
  · simp [trieSortWire,trieSortWidth,trieSortPrimary,TrieRowPort.edge,packTrieKey,wireValue_joinKey]
  · rfl

def trieFunctional (B : ℕ) (c : Bool) (e f : WordEdge) : Prop :=
  trieSortPrimary B c e ≤ trieSortPrimary B c f ∧
    (trieSortPrimary B c e = trieSortPrimary B c f →
      trieSortPayload B c e = trieSortPayload B c f)

def trieOptOrdered {α : Type} (r : α → α → Prop) : Option α → Option α → Prop
  | some a,some b => r a b
  | none,some _ => False
  | _,none => True

def trieRowPair (base B : ℕ) (c : Bool) (l r : TrieRowPort) : List Gate :=
  let n := trieSortWidth B c
  let m := trieSortWidth B (!c)
  let next := base+4*(n+1)
  compareCircuit base n (trieSortWire B c l) (trieSortWire B c r) ++
  compareCircuit next m (trieSortWire B (!c) l) (trieSortWire B (!c) r) ++
  [.assert [.Pos l.present,.Neg r.present],
   .assert [.Neg r.present,.Pos (ltWire base n),.Pos (eqWire base n)],
   .assert [.Neg r.present,.Neg (eqWire base n),.Pos (eqWire next m)]]

theorem trieRowPair_length (base B : ℕ) (c : Bool) (l r : TrieRowPort) :
    (trieRowPair base B c l r).length = 12*B+7 := by
  cases c <;> simp [trieRowPair,trieSortWidth,length_compareCircuit] <;> omega

private theorem trieRowPair_assertions (a : Assignment) (base B : ℕ) (c : Bool)
    (l r : TrieRowPort)
    (h1 : ∀ g ∈ compareCircuit base (trieSortWidth B c)
      (trieSortWire B c l) (trieSortWire B c r), g.Holds a)
    (h2 : ∀ g ∈ compareCircuit (base+4*(trieSortWidth B c+1)) (trieSortWidth B (!c))
      (trieSortWire B (!c) l) (trieSortWire B (!c) r), g.Holds a) :
    let n := trieSortWidth B c
    let m := trieSortWidth B (!c)
    let next := base+4*(n+1)
    (∀ g ∈ [Gate.assert [.Pos l.present,.Neg r.present],
      .assert [.Neg r.present,.Pos (ltWire base n),.Pos (eqWire base n)],
      .assert [.Neg r.present,.Neg (eqWire base n),.Pos (eqWire next m)]], g.Holds a) ↔
    trieOptOrdered (trieFunctional B c) (l.decode a B) (r.decode a B) := by
  let n := trieSortWidth B c
  let m := trieSortWidth B (!c)
  let next := base+4*(n+1)
  have hKey := compareCircuit_outputs base n _ _ a h1 n le_rfl
  have hVal := (compareCircuit_outputs next m _ _ a h2 m le_rfl).2
  have hlt : a (ltWire base n) =
      decide (trieSortPrimary B c (l.edge a B) < trieSortPrimary B c (r.edge a B)) := by
    simpa only [n,trieSortWire_value] using hKey.1
  have heq : a (eqWire base n) =
      decide (trieSortPrimary B c (l.edge a B) = trieSortPrimary B c (r.edge a B)) := by
    simpa only [n,trieSortWire_value] using hKey.2
  have hpay : a (eqWire next m) =
      decide (trieSortPayload B c (l.edge a B) = trieSortPayload B c (r.edge a B)) := by
    have he (x : TrieRowPort) : wireValue a (trieSortWire B (!c) x) m =
        trieSortPayload B c (x.edge a B) := trieSortWire_value a B (!c) x
    rwa [he l,he r] at hVal
  change (∀ g ∈ [Gate.assert [.Pos l.present,.Neg r.present],
      .assert [.Neg r.present,.Pos (ltWire base n),.Pos (eqWire base n)],
      .assert [.Neg r.present,.Neg (eqWire base n),.Pos (eqWire next m)]], g.Holds a) ↔ _
  cases hL : a l.present <;> cases hR : a r.present <;>
    simp [Gate.Holds,satisfiesClause,satisfiesLiteral,hL,hR,TrieRowPort.decode,trieOptOrdered,
      trieFunctional,hlt,heq,hpay] <;> omega

theorem trieRowPair_sound (a : Assignment) (base B : ℕ) (c : Bool) (l r : TrieRowPort)
    (h : ∀ g ∈ trieRowPair base B c l r, g.Holds a) :
    trieOptOrdered (trieFunctional B c) (l.decode a B) (r.decode a B) := by
  simp only [trieRowPair,List.forall_mem_append] at h
  exact (trieRowPair_assertions a base B c l r h.1.1 h.1.2).mp h.2

@[simp] theorem trieRowPair_exact (a : Assignment) (base B : ℕ) (c : Bool) (l r : TrieRowPort)
    (h1 : ∀ g ∈ compareCircuit base (trieSortWidth B c)
      (trieSortWire B c l) (trieSortWire B c r), g.Holds a)
    (h2 : ∀ g ∈ compareCircuit (base+4*(trieSortWidth B c+1)) (trieSortWidth B (!c))
      (trieSortWire B (!c) l) (trieSortWire B (!c) r), g.Holds a) :
    (∀ g ∈ trieRowPair base B c l r, g.Holds a) ↔
    trieOptOrdered (trieFunctional B c) (l.decode a B) (r.decode a B) := by
  simp only [trieRowPair,List.forall_mem_append]
  constructor
  · exact fun h => (trieRowPair_assertions a base B c l r h1 h2).mp h.2
  · exact fun h => ⟨⟨h1,h2⟩,(trieRowPair_assertions a base B c l r h1 h2).mpr h⟩

def trieNonzeroGates (B : ℕ) (r : TrieRowPort) : List Gate :=
  [.assert (.Neg r.present :: (List.range B).map fun i => .Pos (r.child i))]

theorem trieNonzero_exact (a : Assignment) (B : ℕ) (r : TrieRowPort) :
    (∀ g ∈ trieNonzeroGates B r, g.Holds a) ↔
      ∀ e, r.decode a B = some e → e.child ≠ 0 := by
  have hBits : wireValue a r.child B ≠ 0 ↔ ∃ i < B, a (r.child i) = true := by
    constructor
    · intro h
      by_contra! hh
      have hz : ∀ i < B, a (r.child i) = false := by
        intro i hi; cases hab : a (r.child i) <;> simp_all
      have hZero (n : ℕ) (hn : ∀ i < n, a (r.child i) = false) : wireValue a r.child n = 0 := by
        induction n with
        | zero => rfl
        | succ n ih =>
          have hv := ih (fun i hi => hn i (by omega))
          simp [wireValue,hn n (by omega),hv]
      exact h (hZero B hz)
    · rintro ⟨i,hi,ht⟩ hz
      rw [← wireValue_testBit a r.child hi,hz] at ht
      simp at ht
  cases hp : a r.present <;>
    simp [trieNonzeroGates,TrieRowPort.decode,TrieRowPort.edge,Gate.Holds,satisfiesClause,
      satisfiesLiteral,hp,List.any_map,List.any_eq_true,hBits]

end CNFEncComplexity.Robson

/- RobsonTrieOrder -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

private theorem filterNone {α : Type} (r : α → α → Prop) (rs : List (Option α))
    (h : (none::rs).IsChain (trieOptOrdered r)) : rs.filterMap id = [] := by
  induction rs with
  | nil => rfl
  | cons o os ih =>
    obtain ⟨h₁,h₂⟩ := List.isChain_cons_cons.mp h
    cases o with
    | none => simpa using ih h₂
    | some e => exact False.elim h₁

theorem trieOpt_filter_chain {α : Type} (r : α → α → Prop) (rs : List (Option α))
    (h : rs.IsChain (trieOptOrdered r)) : (rs.filterMap id).IsChain r := by
  induction rs with
  | nil => simp
  | cons a as ih =>
    cases as with
    | nil => cases a <;> simp
    | cons b bs =>
      obtain ⟨h₁,h₂⟩ := List.isChain_cons_cons.mp h
      cases a with
      | none =>
        change (List.filterMap id (b::bs)).IsChain r
        rw [filterNone _ _ h]
        simp
      | some a =>
        cases b with
        | none =>
          change (a::List.filterMap id bs).IsChain r
          rw [filterNone _ _ h₂]
          simp
        | some b =>
          change (a::b::List.filterMap id bs).IsChain r
          exact List.isChain_cons_cons.mpr ⟨h₁,ih h₂⟩

/-- The dictionary checker uses only the two permutations and their adjacent
constraints. Neither pass has to compare all pairs of word labels. -/
theorem trieDictionary_sound (B : ℕ) (input byKey byChild : List (Option WordEdge))
    (hShape : ∀ e ∈ input.filterMap id, e.digit < 2^B)
    (hZero : ∀ e ∈ input.filterMap id, e.child ≠ 0)
    (hKey : byKey.Perm input) (hChild : byChild.Perm input)
    (hKeyCheck : byKey.IsChain (trieOptOrdered (trieFunctional B false)))
    (hChildCheck : byChild.IsChain (trieOptOrdered (trieFunctional B true))) :
    WordEdge.Interned (input.filterMap id) := by
  have hk := trieOpt_filter_chain _ _ hKeyCheck
  have hc := trieOpt_filter_chain _ _ hChildCheck
  have hk' (e f : WordEdge) (h : trieFunctional B false e f) :
      packTrieKey B e ≤ packTrieKey B f ∧ (packTrieKey B e = packTrieKey B f → e.child=f.child) := h
  have hc' (e f : WordEdge) (h : trieFunctional B true e f) :
      e.child ≤ f.child ∧ (e.child=f.child → packTrieKey B e = packTrieKey B f) := h
  have hKeyFunc := functional_of_adjacent (packTrieKey B) WordEdge.child
    (hk.imp (fun {e f} h => (hk' e f h).1)).pairwise (hk.imp (fun {e f} h => (hk' e f h).2))
  have hChildFunc := functional_of_adjacent WordEdge.child (packTrieKey B)
    (hc.imp (fun {e f} h => (hc' e f h).1)).pairwise (hc.imp (fun {e f} h => (hc' e f h).2))
  refine ⟨hZero,?_,?_⟩
  · intro e he f hf hh
    exact hKeyFunc e ((hKey.filterMap id).mem_iff.mpr he) f ((hKey.filterMap id).mem_iff.mpr hf)
      ((packTrieKey_eq (hShape e he) (hShape f hf)).mpr hh)
  · intro e he f hf hh
    exact (packTrieKey_eq (hShape e he) (hShape f hf)).mp
      (hChildFunc e ((hChild.filterMap id).mem_iff.mpr he) f ((hChild.filterMap id).mem_iff.mpr hf) hh)

def trieOptionalLE (B : ℕ) (c : Bool) (e f : Option WordEdge) : Bool :=
  match e,f with
  | some e,some f => decide (trieSortPrimary B c e ≤ trieSortPrimary B c f)
  | none,some _ => false
  | _,none => true

private theorem trieOptionalLE_trans (B : ℕ) (c : Bool) (e f g : Option WordEdge)
    (hef : trieOptionalLE B c e f = true) (hfg : trieOptionalLE B c f g = true) :
    trieOptionalLE B c e g = true := by
  cases e <;> cases f <;> cases g <;> simp_all [trieOptionalLE]
  exact le_trans hef hfg

private theorem trieOptionalLE_total (B : ℕ) (c : Bool) (e f : Option WordEdge) :
    (trieOptionalLE B c e f || trieOptionalLE B c f e) = true := by
  cases e <;> cases f <;> simp [trieOptionalLE,le_total]

theorem trieOptionalLE_functional {B : ℕ} {c : Bool} {e f : Option WordEdge}
    {edges : List WordEdge} (hDict : WordEdge.Interned edges)
    (hShape : ∀ e ∈ edges, e.digit < 2^B)
    (he : ∀ r, e = some r → r ∈ edges) (hf : ∀ r, f = some r → r ∈ edges)
    (h : trieOptionalLE B c e f = true) :
    trieOptOrdered (trieFunctional B c) e f := by
  cases e <;> cases f <;> simp_all [trieOptionalLE,trieOptOrdered]
  rename_i p q
  refine ⟨h,?_⟩
  cases c
  · exact fun hEq => hDict.keyFn _ he _ hf
      ((packTrieKey_eq (hShape _ he) (hShape _ hf)).mp hEq)
  · exact fun hEq => (packTrieKey_eq (hShape _ he) (hShape _ hf)).mpr
      (hDict.childFn _ he _ hf hEq)

/-- Choose a routing permutation by sorting source indices. Sorting indices
retains duplicates in the values, so no cardinality or tie ambiguity arises. -/
theorem trieSort_exists_permutation {N : ℕ} (B : ℕ) (c : Bool)
    (rows : Fin N → Option WordEdge)
    (hDict : WordEdge.Interned ((List.ofFn rows).filterMap id))
    (hShape : ∀ e ∈ (List.ofFn rows).filterMap id, e.digit < 2^B) :
    ∃ σ : Fin N ≃ Fin N,
      (List.ofFn (fun i => rows (σ.symm i))).IsChain (trieOptOrdered (trieFunctional B c)) := by
  let le := fun i j : Fin N => trieOptionalLE B c (rows i) (rows j)
  let sorted := (List.finRange N).mergeSort le
  have hp := List.mergeSort_perm (List.finRange N) le
  have hL : sorted.length = N := hp.length_eq.trans List.length_finRange
  have hn : sorted.Nodup := hp.nodup_iff.mpr (List.nodup_finRange N)
  let f : Fin N → Fin N := fun i => sorted.get (Fin.cast hL.symm i)
  have hf : Function.Injective f := by
    intro i j h
    exact (Fin.cast_injective hL.symm) ((List.Nodup.get_inj_iff hn).mp h)
  let σ := Equiv.ofBijective f ⟨hf,Finite.injective_iff_surjective.mp hf⟩
  refine ⟨σ.symm,?_⟩
  have hindices := List.pairwise_mergeSort
    (fun i j k => trieOptionalLE_trans B c (rows i) (rows j) (rows k))
    (fun i j => trieOptionalLE_total B c (rows i) (rows j)) (List.finRange N)
  have hSorted : (sorted.map rows).IsChain (trieOptOrdered (trieFunctional B c)) := by
    apply List.Pairwise.isChain
    rw [List.pairwise_map]
    exact hindices.imp (fun {i j} hij =>
      trieOptionalLE_functional hDict hShape (fun e he =>
        List.mem_filterMap.mpr ⟨rows i,List.mem_ofFn.mpr ⟨i,rfl⟩,he⟩)
        (fun e he => List.mem_filterMap.mpr ⟨rows j,List.mem_ofFn.mpr ⟨j,rfl⟩,he⟩)
        hij)
  have he : List.ofFn (fun i => rows (σ.symm.symm i)) = sorted.map rows := by
    simp only [Equiv.symm_symm]
    apply List.ext_getElem
    · simp [hL]
    · intro i hi hj
      simp only [List.getElem_ofFn,List.getElem_map]
      rfl
  rw [he]
  exact hSorted

end CNFEncComplexity.Robson

/- RobsonTrieSortList -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

def TrieRowPort.below (r : TrieRowPort) (B base : ℕ) : Prop :=
  r.present < base ∧ ∀ i < B, r.parent i < base ∧ r.digit i < base ∧ r.child i < base

theorem TrieRowPort.below_mono {r : TrieRowPort} {B base base' : ℕ} (h : r.below B base)
    (hbase : base ≤ base') : r.below B base' :=
  ⟨h.1.trans_le hbase, fun i hi =>
    let hi' := h.2 i hi
    ⟨hi'.1.trans_le hbase,hi'.2.1.trans_le hbase,hi'.2.2.trans_le hbase⟩⟩

theorem TrieRowPort.decode_frame {r : TrieRowPort} {B base : ℕ} {a b : Assignment} (h : r.below B base)
    (hAgree : ∀ i < base, a i = b i) : r.decode a B = r.decode b B := by
  have hp := wireValue_congr (n := B) (key := r.parent) (fun i hi => hAgree _ (h.2 i hi).1)
  have hd := wireValue_congr (n := B) (key := r.digit) (fun i hi => hAgree _ (h.2 i hi).2.1)
  have hc := wireValue_congr (n := B) (key := r.child) (fun i hi => hAgree _ (h.2 i hi).2.2)
  simp [TrieRowPort.decode,TrieRowPort.edge,hAgree _ h.1,hp,hd,hc]

private theorem trieSortWire_below {r : TrieRowPort} {B base : ℕ} (h : r.below B base) (c : Bool)
    (i : ℕ) (hi : i < trieSortWidth B c) :
    trieSortWire B c r i < base := by
  cases c
  · change i < B+B at hi
    change joinKey r.digit r.parent B i < base
    by_cases him : i < B
    · exact show (if i < B then r.digit i else r.parent (i-B)) < base from
        by rw [if_pos him]; exact (h.2 i him).2.1
    · exact show (if i < B then r.digit i else r.parent (i-B)) < base from
        by rw [if_neg him]; exact (h.2 (i-B) (by omega)).1
  · exact (h.2 i hi).2.2

def triePairSpan (B : ℕ) := 12*B+8

private theorem trieSortWidth_sum (B : ℕ) (c : Bool) :
    trieSortWidth B c + trieSortWidth B (!c) = 3*B := by
  cases c <;> simp [trieSortWidth] <;> omega

theorem trieRowPair_names (base B : ℕ) (c : Bool) (l r : TrieRowPort)
    (hL : l.below B base) (hR : r.below B base)
    (g : Gate) (hg : g ∈ trieRowPair base B c l r) (i : ℕ)
    (hi : i ∈ RobsonCNF.Gate.names g) : i < base+triePairSpan B := by
  let n := trieSortWidth B c
  let m := trieSortWidth B (!c)
  let next := base+4*(n+1)
  have hSum : n+m=3*B := trieSortWidth_sum _ _
  have hN : base ≤ next := Nat.le_add_right _ _
  simp only [trieRowPair,List.mem_append] at hg
  rcases hg with (hg|hg)|hg
  · have h := compareCircuit_names_lt base n _ _ (trieSortWire_below hL c)
      (trieSortWire_below hR c) g hg i hi
    unfold triePairSpan
    omega
  · have h := compareCircuit_names_lt next m _ _ (trieSortWire_below (TrieRowPort.below_mono hL hN) (!c))
      (trieSortWire_below (TrieRowPort.below_mono hR hN) (!c)) g hg i hi
    change i < base+4*(n+1)+4*m+2 at h
    unfold triePairSpan
    omega
  · have ha := hL.1
    have hb := hR.1
    simp only [List.mem_cons,List.mem_nil_iff,or_false] at hg
    rcases hg with rfl|rfl|rfl <;>
      simp only [RobsonCNF.Gate.names,List.map_cons,List.map_nil,Literal.var,List.mem_cons,
        List.mem_nil_iff,or_false,ltWire,eqWire] at hi <;>
      unfold triePairSpan <;>
      dsimp only [n,m,next] at hSum <;>
      omega

/-- Both scratch comparators for a pair extend below-scratch rows and preserve
all names outside their allocated interval. -/
theorem trieRowPair_extend (a : Assignment) (base B : ℕ) (c : Bool) (l r : TrieRowPort)
    (hL : l.below B base) (hR : r.below B base)
    (hCheck : trieOptOrdered (trieFunctional B c) (l.decode a B) (r.decode a B)) :
    ∃ b : Assignment, (∀ i, i < base ∨ base+triePairSpan B ≤ i → b i = a i) ∧
      ∀ g ∈ trieRowPair base B c l r, g.Holds b := by
  let n := trieSortWidth B c
  let m := trieSortWidth B (!c)
  let next := base+4*(n+1)
  have hSum : n+m=3*B := trieSortWidth_sum _ _
  have hN : base ≤ next := Nat.le_add_right _ _
  obtain ⟨a₁,hFrame₁,hFirst⟩ := compareCircuit_extends_interval base n _ _ a
    (trieSortWire_below hL c) (trieSortWire_below hR c)
  obtain ⟨a₂,hFrame₂,hSecond⟩ := compareCircuit_extends_interval next m _ _ a₁
    (trieSortWire_below (TrieRowPort.below_mono hL hN) (!c)) (trieSortWire_below (TrieRowPort.below_mono hR hN) (!c))
  have hNext : next = base+4*(n+1) := rfl
  have hFr (i : ℕ) (hi : i < base ∨ base+triePairSpan B ≤ i) : a₂ i = a i := by
    unfold triePairSpan at hi
    rcases hi with h|h
    · exact (hFrame₂ _ (.inl (h.trans_le hN))).trans (hFrame₁ _ (.inl h))
    · exact (hFrame₂ _ (.inr (by omega))).trans (hFrame₁ _ (.inr (by omega)))
  refine ⟨a₂,hFr,?_⟩
  have hFirst' : ∀ g ∈ compareCircuit base n (trieSortWire B c l) (trieSortWire B c r),
      g.Holds a₂ := by
    intro g hg
    refine (g.holds_congr a₂ a₁ (fun i hi => hFrame₂ i (.inl ?_))).mpr (hFirst g hg)
    have h := compareCircuit_names_lt base n _ _ (trieSortWire_below hL c)
      (trieSortWire_below hR c) g hg i hi
    omega
  apply (trieRowPair_exact a₂ base B c l r hFirst' hSecond).mpr
  rw [TrieRowPort.decode_frame hL (fun i hi => hFr i (.inl hi)),
    TrieRowPort.decode_frame hR (fun i hi => hFr i (.inl hi))]
  exact hCheck

/-- Consecutive positions have disjoint comparator scratch intervals. -/
def trieSortCheckGates (B : ℕ) (c : Bool) : ℕ → List TrieRowPort → List Gate
  | base,l::r::rs => trieRowPair base B c l r ++ trieSortCheckGates B c (base+triePairSpan B) (r::rs)
  | _,_ => []

theorem trieSortCheckGates_length (B : ℕ) (c : Bool) (base : ℕ) (rows : List TrieRowPort) :
    (trieSortCheckGates B c base rows).length ≤ rows.length*(12*B+7) := by
  induction rows generalizing base with
  | nil => simp [trieSortCheckGates]
  | cons l xs ih =>
    cases xs with
    | nil => simp [trieSortCheckGates]
    | cons r rs =>
      have h := ih (base+triePairSpan B)
      rw [trieSortCheckGates,List.length_append,trieRowPair_length,List.length_cons,Nat.add_mul,Nat.one_mul]
      omega

theorem trieSortCheckGates_sound (a : Assignment) (B : ℕ) (c : Bool) (base : ℕ) (rows : List TrieRowPort)
    (h : ∀ g ∈ trieSortCheckGates B c base rows, g.Holds a) :
    (rows.map (TrieRowPort.decode a B)).IsChain (trieOptOrdered (trieFunctional B c)) := by
  induction rows generalizing base with
  | nil => simp
  | cons l xs ih =>
    cases xs with
    | nil => simp
    | cons r rs =>
      rw [trieSortCheckGates,List.forall_mem_append] at h
      exact List.isChain_cons_cons.mpr ⟨trieRowPair_sound a base B c l r h.1,ih _ h.2⟩

theorem trieSortCheckGates_extend (a : Assignment) (B : ℕ) (c : Bool) (base : ℕ)
    (rows : List TrieRowPort) (hN : ∀ r ∈ rows, r.below B base)
    (hCheck : (rows.map (TrieRowPort.decode a B)).IsChain (trieOptOrdered (trieFunctional B c))) :
    ∃ b : Assignment,
      (∀ i, i < base ∨ base+rows.length*triePairSpan B ≤ i → b i = a i) ∧
      ∀ g ∈ trieSortCheckGates B c base rows, g.Holds b := by
  induction rows generalizing base a with
  | nil => exact ⟨a,fun _ _ => rfl,by simp [trieSortCheckGates]⟩
  | cons l xs ih =>
    cases xs with
    | nil => exact ⟨a,fun _ _ => rfl,by simp [trieSortCheckGates]⟩
    | cons r rs =>
      let next := base+triePairSpan B
      have hNext : base ≤ next := Nat.le_add_right _ _
      have hL := hN l List.mem_cons_self
      have hR := hN r (List.mem_cons_of_mem _ List.mem_cons_self)
      obtain ⟨hLocal,hRest⟩ := List.isChain_cons_cons.mp hCheck
      obtain ⟨a₁,hF₁,hPair⟩ := trieRowPair_extend a base B c l r hL hR hLocal
      have hR' : ((r::rs).map (TrieRowPort.decode a₁ B)).IsChain
          (trieOptOrdered (trieFunctional B c)) := by
        convert hRest using 1
        apply List.map_congr_left
        intro d hd
        exact TrieRowPort.decode_frame (hN d (List.mem_cons_of_mem _ hd)) (fun i hi => hF₁ i (.inl hi))
      obtain ⟨a₂,hF₂,hSuffix⟩ := ih a₁ next
        (fun d hd => TrieRowPort.below_mono (hN d (List.mem_cons_of_mem _ hd)) hNext) hR'
      refine ⟨a₂,?_,?_⟩
      · intro i hi
        rcases hi with h|h
        · exact (hF₂ _ (.inl (h.trans_le hNext))).trans (hF₁ _ (.inl h))
        · dsimp [next] at hF₂
          rw [List.length_cons,Nat.add_mul,Nat.one_mul] at h
          have hh : base+triePairSpan B+(r::rs).length*triePairSpan B ≤ i := by omega
          exact (hF₂ _ (.inr hh)).trans (hF₁ _ (.inr (by omega)))
      · rw [trieSortCheckGates,List.forall_mem_append]
        refine ⟨?_,hSuffix⟩
        intro g hg
        apply (g.holds_congr a₂ a₁ (fun i hi =>
          hF₂ i (.inl (trieRowPair_names base B c l r hL hR g hg i hi)))).mpr
        exact hPair g hg

end CNFEncComplexity.Robson

/- RobsonTrieRoutePass -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

def trieRowWidth (B : ℕ) : ℕ := 1+3*B

def trieRowFromNat (B : ℕ) (src : ℕ → ℕ) : TrieRowPort :=
  ⟨src 0,fun i => src (1+i),fun i => src (1+B+i),fun i => src (1+2*B+i)⟩

def trieRouteName (base B h : ℕ) (v : RouteVar h (Fin (trieRowWidth B))) : ℕ :=
  base+(routeLabel h (trieRowWidth B) v).val

def trieRouteEnd (base B h : ℕ) : ℕ :=
  base+(2^h*trieRowWidth B+(2^h*trieRowWidth B+auxCount (trieRowWidth B) h))

def trieRouteOut (base B h q i : ℕ) : ℕ :=
  base+2^h*trieRowWidth B+q*trieRowWidth B+i

def trieRouteIn (base B q i : ℕ) : ℕ := base+q*trieRowWidth B+i

theorem trieRouteName_in (base B h : ℕ) (q : Fin (2^h)) (i : Fin (trieRowWidth B)) :
    trieRouteName base B h (.input ((wireLabel h).symm q) i) =
        trieRouteIn base B q.val i.val := by
  rw [trieRouteName,← nodeRouteName_root]
  simp [nodeRouteName,rootRouteNode,routeNodeInput,routeNodeDepth,routeNodeStride,
    trieRouteIn,Nat.add_assoc]
  exact Or.inl (congrArg Fin.val ((wireLabel h).apply_symm_apply q))

theorem trieRouteName_out (base B h : ℕ) (q : Fin (2^h)) (i : Fin (trieRowWidth B)) :
    trieRouteName base B h (.output ((wireLabel h).symm q) i) =
        trieRouteOut base B h q.val i.val := by
  rw [trieRouteName,← nodeRouteName_root]
  simp [nodeRouteName,rootRouteNode,routeNodeOutput,routeNodeDepth,routeNodeStride,
    trieRouteOut,Nat.add_assoc]
  exact Or.inl (congrArg Fin.val ((wireLabel h).apply_symm_apply q))

theorem trieRouteName_range (base B h : ℕ) (i : RouteVar h (Fin (trieRowWidth B))) :
    base ≤ trieRouteName base B h i ∧ trieRouteName base B h i < trieRouteEnd base B h :=
  ⟨Nat.le_add_right _ _, Nat.add_lt_add_left (routeLabel h (trieRowWidth B) i).isLt _⟩

def trieRouteCopy (base B h : ℕ) (src : ℕ → ℕ → ℕ) : List Gate :=
  (List.range (2^h)).flatMap (fun q => wordCopy (trieRowWidth B) (trieRouteIn base B q) (src q))

def trieRouteRows (base B h : ℕ) : List TrieRowPort :=
  List.ofFn (fun q : Fin (2^h) => trieRowFromNat B (trieRouteOut base B h q.val))

def trieSortPass (base B h : ℕ) (c : Bool) (src : ℕ → ℕ → ℕ) : List Gate :=
  trieRouteCopy base B h src ++ routeNamedGates (trieRouteName base B h) ++
    trieSortCheckGates B c (trieRouteEnd base B h) (trieRouteRows base B h)

def trieSortPassEnd (base B h : ℕ) : ℕ :=
  trieRouteEnd base B h+2^h*triePairSpan B

def trieSourceRows (a : Assignment) (B h : ℕ) (src : ℕ → ℕ → ℕ) : List (Option WordEdge) :=
  List.ofFn (fun q : Fin (2^h) => (trieRowFromNat B (src q.val)).decode a B)

private theorem trieNatRow_congr (a : Assignment) (B : ℕ) {x y : ℕ → ℕ}
    (h : ∀ i < trieRowWidth B, a (x i) = a (y i)) :
    (trieRowFromNat B x).decode a B = (trieRowFromNat B y).decode a B := by
  have hOn : a (x 0) = a (y 0) := h 0 (by unfold trieRowWidth; omega)
  have hP : wireValue a (fun i => x (1+i)) B = wireValue a (fun i => y (1+i)) B :=
    (wireValue_eq_iff ..).2 (fun i hi => h _ (by unfold trieRowWidth; omega))
  have hD : wireValue a (fun i => x (1+B+i)) B = wireValue a (fun i => y (1+B+i)) B :=
    (wireValue_eq_iff ..).2 (fun i hi => h _ (by unfold trieRowWidth; omega))
  have hC : wireValue a (fun i => x (1+2*B+i)) B = wireValue a (fun i => y (1+2*B+i)) B :=
    (wireValue_eq_iff ..).2 (fun i hi => h _ (by unfold trieRowWidth; omega))
  simp [trieRowFromNat,TrieRowPort.decode,TrieRowPort.edge,hOn,hP,hD,hC] <;> rfl

private def trieReadBits (B : ℕ) (bs : Fin (trieRowWidth B) → Bool) : Option WordEdge :=
  let a : Assignment := fun i => if h : i < trieRowWidth B then bs ⟨i,h⟩ else false
  (trieRowFromNat B id).decode a B

private theorem trieReadBits_names (a : Assignment) (B : ℕ) (src : ℕ → ℕ) :
    trieReadBits B (fun i => a (src i.val)) = (trieRowFromNat B src).decode a B := by
  let a' : Assignment := fun i => if h : i < trieRowWidth B then a (src i) else false
  have h (i : ℕ) (hi : i < trieRowWidth B) : a' i = a (src i) := by simp [a',hi]
  have hOn : a' 0 = a (src 0) := h 0 (by unfold trieRowWidth; omega)
  have hp (k : ℕ) (hk : k ≤ 1+2*B) :
      wireValue a' (fun i => k+i) B = wireValue a (fun i => src (k+i)) B := by
    apply Nat.eq_of_testBit_eq
    intro i
    by_cases hi : i < B
    · rw [wireValue_testBit _ _ hi,wireValue_testBit _ _ hi]
      exact h _ (by unfold trieRowWidth; omega)
    · have hh : 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 hh),
        Nat.testBit_lt_two_pow ((wireValue_lt _ _ _).trans_le hh)]
  change (trieRowFromNat B id).decode a' B = _
  simp [trieRowFromNat,TrieRowPort.decode,TrieRowPort.edge,hOn,
    hp 1 (by omega),hp (1+B) (by omega),hp (1+2*B) le_rfl] <;> rfl

/-- Any satisfying pass permutes the exact optional records and certifies
adjacent order and functional consistency in its output. -/
theorem trieSortPass_sound (a : Assignment) (base B h : ℕ) (c : Bool) (src : ℕ → ℕ → ℕ)
    (hSat : ∀ g ∈ trieSortPass base B h c src, g.Holds a) :
    ∃ rows : List (Option WordEdge), rows.Perm (trieSourceRows a B h src) ∧
      rows.IsChain (trieOptOrdered (trieFunctional B c)) := by
  simp only [trieSortPass,List.forall_mem_append] at hSat
  obtain ⟨⟨hAtt,hRoute⟩,hSort⟩ := hSat
  let rOut := trieRouteRows base B h
  let D := trieRowWidth B
  have hInput (q : Fin (2^h)) (i : Fin D) :
      a (trieRouteName base B h (.input ((wireLabel h).symm q) i)) = a (src q.val i.val) := by
    rw [trieRouteName_in]
    exact hAtt (.copy (trieRouteIn base B q.val i.val) (src q.val i.val))
      (List.mem_flatMap.mpr ⟨q.val,List.mem_range.mpr q.isLt,List.mem_map.mpr
        ⟨i.val,List.mem_range.mpr i.isLt,rfl⟩⟩)
  have hp := routeNamedGates_perm (trieRouteName base B h) (trieReadBits B) a hRoute
  refine ⟨rOut.map (TrieRowPort.decode a B),?_,trieSortCheckGates_sound a _ _ _ _ hSort⟩
  have hl : (List.ofFn fun i : Fin (2^h) => trieReadBits B
      (fun j => a (trieRouteName base B h (.output ((wireLabel h).symm i) j)))) =
      rOut.map (TrieRowPort.decode a B) := by
    unfold rOut trieRouteRows
    rw [List.map_ofFn]
    congr 1
    funext q
    simp only [trieRouteName_out,trieReadBits_names,Function.comp_def]
  have hr : (List.ofFn fun i : Fin (2^h) => trieReadBits B
      (fun j => a (trieRouteName base B h (.input ((wireLabel h).symm i) j)))) =
      trieSourceRows a B h src := by
    unfold trieSourceRows
    congr 1
    funext q
    simp only [hInput,trieReadBits_names]
  simpa only [hl,hr] using hp

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

private theorem trieOutputRow_below (base B h : ℕ) (q : Fin (2^h)) :
    (trieRowFromNat B (trieRouteOut base B h q.val)).below B (trieRouteEnd base B h) := by
  have hh (i : ℕ) (hi : i < trieRowWidth B) :
      trieRouteOut base B h q.val i < trieRouteEnd base B h := by
    have eq := trieRouteName_out base B h q ⟨i,hi⟩
    rw [← eq]
    exact (trieRouteName_range _ _ _ _).2
  refine ⟨hh _ (by unfold trieRowWidth; omega),?_⟩
  intro i hi
  exact ⟨hh _ (by unfold trieRowWidth; omega),hh _ (by unfold trieRowWidth; omega),
    hh _ (by unfold trieRowWidth; omega)⟩

private theorem trieRouteGateNames (base B h : ℕ) (g : Gate)
    (hg : g ∈ routeNamedGates (trieRouteName base B h)) :
    ∀ i ∈ RobsonCNF.Gate.names g, i < trieRouteEnd base B h := by
  obtain ⟨r,hr,rfl⟩ := List.mem_map.mp hg
  cases r with
  | copy o s => simpa [RouteGate.named,RobsonCNF.Gate.names] using
      ⟨(trieRouteName_range base B h o).2,(trieRouteName_range base B h s).2⟩
  | mux o s y n => simpa [RouteGate.named,RobsonCNF.Gate.names] using
      ⟨(trieRouteName_range base B h o).2,(trieRouteName_range base B h s).2,
       (trieRouteName_range base B h y).2,(trieRouteName_range base B h n).2⟩

/-- A correct dictionary always extends to a satisfying sorted pass. -/
theorem trieSortPass_extend (a : Assignment) (base B h : ℕ)
    (c : Bool) (src : ℕ → ℕ → ℕ)
    (hSrc : ∀ q < 2^h, ∀ i < trieRowWidth B, src q i < base)
    (hDict : WordEdge.Interned ((trieSourceRows a B h src).filterMap id)) :
    ∃ a' : Assignment, (∀ i, i < base ∨ trieSortPassEnd base B h ≤ i → a' i = a i) ∧
      ∀ g ∈ trieSortPass base B h c src, g.Holds a' := by
  let D := trieRowWidth B
  let name := trieRouteName base B h
  let rows := fun q : Fin (2^h) => (trieRowFromNat B (src q.val)).decode a B
  have hD : ∀ e ∈ (trieSourceRows a B h src).filterMap id, e.digit < 2^B := by
    intro e he
    obtain ⟨o,ho,hEq⟩ := List.mem_filterMap.mp he
    obtain ⟨q,rfl⟩ := List.mem_ofFn.mp ho
    change (if a (src q.val 0) then some _ else none) = some e at hEq
    split at hEq
    · obtain rfl := Option.some.inj hEq
      exact wireValue_lt ..
    · contradiction
  obtain ⟨σ,hSorted⟩ := trieSort_exists_permutation B c rows hDict hD
  have hInj : Function.Injective name := by
    intro i j hh
    apply (routeLabel h D).injective
    exact Fin.ext (Nat.add_left_cancel hh)
  obtain ⟨a₁,hFr₁,haRoute,hInputs,hOutputs⟩ :=
    routeNamedGates_extend name hInj a (fun i j => a (src i.val j.val)) σ
  have hCopy : ∀ g ∈ trieRouteCopy base B h src, g.Holds a₁ := by
    intro g hg
    obtain ⟨q,hq,hg⟩ := List.mem_flatMap.mp hg
    obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
    have hq' := List.mem_range.mp hq
    have hi' := List.mem_range.mp hi
    have hEq := hInputs ⟨q,hq'⟩ ⟨i,hi'⟩
    change a₁ (trieRouteName base B h (.input ((wireLabel h).symm ⟨q,hq'⟩) ⟨i,hi'⟩)) = _ at hEq
    rw [trieRouteName_in] at hEq
    have hFrSrc : a₁ (src q i) = a (src q i) := by
      apply hFr₁
      intro v eq
      apply (not_le_of_gt (hSrc q hq' i hi'))
      rw [← eq]
      exact (trieRouteName_range base B h v).1
    change a₁ (trieRouteIn base B q i) = a₁ (src q i)
    rw [hFrSrc]
    exact hEq
  have hDecoded (q : Fin (2^h)) :
      (trieRowFromNat B (trieRouteOut base B h q.val)).decode a₁ B = rows (σ.symm q) := by
    rw [← trieReadBits_names a₁,show rows (σ.symm q) =
      trieReadBits B (fun i => a (src (σ.symm q).val i.val)) from (trieReadBits_names a B _).symm]
    apply congrArg (trieReadBits B)
    funext j
    have hx := hOutputs (σ.symm q) j
    rw [Equiv.apply_symm_apply] at hx
    change a₁ (trieRouteName base B h (.output ((wireLabel h).symm q) j)) = _ at hx
    rw [trieRouteName_out] at hx
    exact hx
  have hSort : ((trieRouteRows base B h).map (TrieRowPort.decode a₁ B)).IsChain
      (trieOptOrdered (trieFunctional B c)) := by
    unfold trieRouteRows
    rw [List.map_ofFn]
    simpa only [Function.comp_def,hDecoded] using hSorted
  have hBelow (r : TrieRowPort) (hr : r ∈ trieRouteRows base B h) : r.below B (trieRouteEnd base B h) := by
    obtain ⟨q,rfl⟩ := List.mem_ofFn.mp hr
    exact trieOutputRow_below base B h q
  obtain ⟨a₂,hFr₂,hCheck⟩ :=
    trieSortCheckGates_extend a₁ B c (trieRouteEnd base B h) (trieRouteRows base B h) hBelow hSort
  have hEnd : base ≤ trieRouteEnd base B h := Nat.le_add_right _ _
  have hFrame (i : ℕ) (hi : i < base ∨ trieSortPassEnd base B h ≤ i) : a₂ i = a i := by
    rcases hi with hi|hi
    · exact (hFr₂ _ (.inl (hi.trans_le hEnd))).trans (hFr₁ _
        (fun v hh => (not_le_of_gt hi) (hh ▸ (trieRouteName_range base B h v).1)))
    · have hi' : trieRouteEnd base B h+(trieRouteRows base B h).length*triePairSpan B ≤ i := by
        simpa [trieRouteRows,trieSortPassEnd] using hi
      have he : trieRouteEnd base B h ≤ i := (Nat.le_add_right _ _).trans hi'
      exact (hFr₂ _ (.inr hi')).trans (hFr₁ _ (fun v hh =>
        (not_lt_of_ge he) (hh ▸ (trieRouteName_range base B h v).2)))
  refine ⟨a₂,hFrame,?_⟩
  simp only [trieSortPass,List.forall_mem_append]
  refine ⟨⟨?_,?_⟩,hCheck⟩
  · intro g hg
    obtain ⟨q,hq,hg⟩ := List.mem_flatMap.mp hg
    obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hg
    have hq' := List.mem_range.mp hq
    have hj' := List.mem_range.mp hj
    have hn (q : Fin (2^h)) (j : Fin D) : trieRouteIn base B q.val j.val < trieRouteEnd base B h := by
      rw [← trieRouteName_in base B h q j]
      exact (trieRouteName_range base B h _).2
    change a₂ (trieRouteIn base B q j) = a₂ (src q j)
    rw [hFr₂ _ (.inl (hn ⟨q,hq'⟩ ⟨j,hj'⟩)),hFr₂ _ (.inl ((hSrc q hq' j hj').trans_le hEnd))]
    exact hCopy _ (List.mem_flatMap.mpr ⟨q,hq,List.mem_map.mpr ⟨j,hj,rfl⟩⟩)
  · intro g hg
    exact (g.holds_congr a₂ a₁ (fun i hi =>
      hFr₂ _ (.inl (trieRouteGateNames base B h g hg i hi)))).mpr (haRoute g hg)

end CNFEncComplexity.Robson

/- RobsonGatherLift -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime

inductive GatherOutput (w count : ℕ) where
  | active
  | acc (i : Fin (count+1))
  | bit (i : Fin w)

def gatherOutputName {w count : ℕ} (active : ℕ) (acc : ℕ → ℕ) (out : Fin w → ℕ) :
    GatherOutput w count → ℕ
  | .active => active
  | .acc i => acc i.val
  | .bit i => out i

/-- A deterministic witness for the local pooling circuit, conditional only
on the presence bits selecting at most one candidate. -/
theorem gatherGates_extends (a : Assignment) {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
    (out : Fin w → ℕ) (cs : List (GatherCandidate w))
    (hUnique : ∀ i j : Fin cs.length, a cs[i.val].1=true → a cs[j.val].1=true → i=j)
    (hInjective : Function.Injective (gatherOutputName (count := cs.length) active acc out))
    (hFreshOn : ∀ i : Fin cs.length, ¬∃ z : GatherOutput w cs.length,
      gatherOutputName active acc out z = cs[i.val].1)
    (hFreshBits : ∀ i : Fin cs.length, ∀ k : Fin w, ¬∃ z : GatherOutput w cs.length,
      gatherOutputName active acc out z = cs[i.val].2 k) :
    ∃ b : Assignment,
      (∀ i, (¬∃ z : GatherOutput w cs.length, gatherOutputName active acc out z = i) → b i = a i) ∧
      (∀ g ∈ gatherGates active acc out cs, g.Holds b) := by
  classical
  let dest : GatherOutput w cs.length → ℕ := gatherOutputName active acc out
  let on : Prop := ∃ i : Fin cs.length, a cs[i.val].1 = true
  let val : GatherOutput w cs.length → Bool
    | .active => decide on
    | .acc i => decide (GatherSeen a cs i.val)
    | .bit k => if hi : on then a (cs[hi.choose.val].2 k) else false
  let b : Assignment := Function.extend dest val a
  have hDest (v : GatherOutput w cs.length) : b (dest v) = val v := hInjective.extend_apply _ _ _
  have hFr (i : ℕ) (hi : ¬∃ z, dest z=i) : b i = a i := Function.extend_apply' _ _ _ hi
  have hOn (i : Fin cs.length) : b cs[i.val].1 = a cs[i.val].1 := hFr _ (hFreshOn i)
  have hBit (i : Fin cs.length) (k : Fin w) : b (cs[i.val].2 k) = a (cs[i.val].2 k) :=
    hFr _ (hFreshBits i k)
  refine ⟨b,hFr,?_⟩
  apply gatherGates_complete b active acc out cs
  · change b (dest .active) = true ↔ _
    rw [hDest]
    change decide on = true ↔ _
    simp only [decide_eq_true_eq,hOn,on]
  · intro i j hi hj
    exact hUnique i j ((hOn i).symm ▸ hi) ((hOn j).symm ▸ hj)
  · intro i hi k
    have hi' : a cs[i.val].1=true := (hOn i).symm ▸ hi
    have hex : on := ⟨i,hi'⟩
    have hl : i = hex.choose := hUnique _ _ hi' hex.choose_spec
    change b (cs[i.val].2 k) = b (dest (.bit k))
    rw [hBit,hDest]
    dsimp [val]
    rw [dif_pos hex]
    exact congrArg (fun j : Fin cs.length => a (cs[j.val].2 k)) hl
  · intro j hj
    have he : b (acc j) = decide (GatherSeen a cs j) := hDest (.acc ⟨j,by omega⟩)
    rw [he]
    have he' : GatherSeen b cs j ↔ GatherSeen a cs j := by simp only [GatherSeen,hOn]
    rw [he']
    exact ⟨of_decide_eq_true,decide_eq_true⟩

/-- Non-dependent presentation of the same gather template for uniform gate
generation from unary arithmetic and index functions. -/
def gatherArray (w count active : ℕ) (acc out enable : ℕ → ℕ) (payload : ℕ → ℕ → ℕ) : List Gate :=
  [.pin (acc 0) false,.copy active (acc count)] ++
    (List.range count).flatMap (fun j =>
      [.disj (acc (j+1)) (acc j) (enable j),.assert [.Neg (acc j),.Neg (enable j)]] ++
      (List.range w).flatMap (fun i => guardEqual (enable j) (payload j i) (out i)))

private theorem finrange_flatmap_eq_range {α : Type} (n : ℕ) (F : ℕ → List α) :
    (List.finRange n).flatMap (fun i => F i.val) = (List.range n).flatMap F := by
  rw [← List.flatMap_map]
  simp

private theorem gatherGates_range {w : ℕ} (active : ℕ) (acc : ℕ → ℕ)
    (out : Fin w → ℕ) (cs : List (GatherCandidate w)) :
    gatherGates active acc out cs = .pin (acc 0) false :: .copy active (acc cs.length) ::
      (List.range cs.length).flatMap (fun j => gatherEntry acc out j (cs[j]?.getD (0,fun _ => 0))) := by
  unfold gatherGates
  rw [← finrange_flatmap_eq_range]
  congr 2
  apply List.flatMap_congr
  intro j hj
  rw [List.getElem?_eq_getElem j.isLt,Option.getD_some]

theorem gatherArray_exact (w count active : ℕ) (acc out enable : ℕ → ℕ) (payload : ℕ → ℕ → ℕ) :
    gatherArray w count active acc out enable payload = gatherGates active acc
      (fun i : Fin w => out i.val) (List.ofFn (fun i : Fin count => (enable i.val,fun k => payload i.val k.val))) := by
  rw [gatherGates_range]
  simp only [gatherArray,List.length_ofFn,List.cons_append,List.nil_append,List.cons.injEq,true_and]
  apply List.flatMap_congr
  intro j hj
  have hj' : j < count := List.mem_range.mp hj
  rw [List.getElem?_eq_getElem (by simpa using hj'),List.getElem_ofFn,Option.getD_some,gatherEntry]
  have hh := finrange_flatmap_eq_range w (fun i => guardEqual (enable j) (payload j i) (out i))
  simpa only [Prod.fst,Prod.snd,Fin.val_mk,List.cons.injEq,true_and] using hh.symm

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

private theorem negNeg_poly {r s : A → ℕ}
    (hr : ComputableTidilyInPolyTime r e encUnary)
    (hs : ComputableTidilyInPolyTime s e encUnary) :
    ComputableTidilyInPolyTime
      (fun x => Gate.assert [.Neg (r x),.Neg (s x)]) e gateEnc := by
  exact gate_assert (cons' (unary_mul.comp ((const 2).prod hr))
    (cons' (unary_mul.comp ((const 2).prod hs)) (const [])))

theorem guardEqual_poly {g s d : A → ℕ}
    (hg : ComputableTidilyInPolyTime g e encUnary)
    (hs : ComputableTidilyInPolyTime s e encUnary)
    (hd : ComputableTidilyInPolyTime d e encUnary) :
    ComputableTidilyInPolyTime (fun x => guardEqual (g x) (s x) (d x)) e (encList gateEnc) := by
  have mul := fun {f : A → ℕ} (h : ComputableTidilyInPolyTime f e encUnary) =>
    unary_mul.comp ((const 2).prod h)
  have hg' := mul hg
  have hs' := mul hs
  have hd' := mul hd
  have hS := unary_add.comp (hs'.prod (const 1))
  have hD := unary_add.comp (hd'.prod (const 1))
  exact cons' (gate_assert (cons' hg' (cons' hs' (cons' hD (const [])))))
    (cons' (gate_assert (cons' hg' (cons' hS (cons' hd' (const []))))) (const []))

theorem gatherArray_poly {w m active : A → ℕ} {acc out enable : A → ℕ → ℕ} {payload : A → ℕ → ℕ → ℕ}
    (hw : ComputableTidilyInPolyTime w e encUnary)
    (hm : ComputableTidilyInPolyTime m e encUnary)
    (ha : ComputableTidilyInPolyTime active e encUnary)
    (hac : ComputableTidilyInPolyTime (fun p : A×ℕ => acc p.1 p.2) (encPair e encUnary) encUnary)
    (hOut : ComputableTidilyInPolyTime (fun p : A×ℕ => out p.1 p.2) (encPair e encUnary) encUnary)
    (hen : ComputableTidilyInPolyTime (fun p : A×ℕ => enable p.1 p.2) (encPair e encUnary) encUnary)
    (hP : ComputableTidilyInPolyTime (fun p : (A×ℕ)×ℕ => payload p.1.1 p.1.2 p.2)
      (encPair (encPair e encUnary) encUnary) encUnary) :
    ComputableTidilyInPolyTime (fun x => gatherArray (w x) (m x) (active x)
      (acc x) (out x) (enable x) (payload x)) e (encList gateEnc) := by
  let e₁ := encPair e encUnary
  let e₂ := encPair e₁ encUnary
  have hX := fst e encUnary
  have hI := snd e encUnary
  have hY := fst e₁ encUnary
  have hJ := snd e₁ encUnary
  have hEnd := hac.comp ((id' (encIn := e)).prod hm)
  have hZero := hac.comp ((id' (encIn := e)).prod (const 0))
  have hHead := cons' (gate_pin false hZero) (cons' (gate_copy ha hEnd) (const []))
  have hNext := hac.comp (hX.prod (unary_add.comp (hI.prod (const 1))))
  have hLead := cons' (gate_disj hNext hac hen) (cons' (negNeg_poly hac hen) (const []))
  have hOut' := hOut.comp ((hX.comp hY).prod hJ)
  have hBody := flatMapWithInput (f := fun (p : A×ℕ) i =>
      guardEqual (enable p.1 p.2) (payload p.1 p.2 i) (out p.1 i))
    (range.comp (hw.comp hX)) (guardEqual_poly (hen.comp hY) hP hOut')
  have hTail := flatMapWithInput (f := fun x j =>
      [.disj (acc x (j+1)) (acc x j) (enable x j),.assert [.Neg (acc x j),.Neg (enable x j)]] ++
      (List.range (w x)).flatMap (fun i => guardEqual (enable x j) (payload x j i) (out x i)))
    (range.comp hm) (listAppend' hLead hBody)
  exact listAppend' hHead hTail

end
end CNFEncComplexity.Robson

/- RobsonTriePool -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

def triePoolWidth (b : ℕ) : ℕ := 3*2^b

def triePoolLanes (t b : ℕ) : ℕ := 2^(layoutHeight t-b)

def triePoolHeight (t b : ℕ) : ℕ := layoutHeight t-b+4

def triePoolLevels (t b : ℕ) : ℕ := layoutHeight t+1-b

def triePoolCount (t b q : ℕ) : ℕ :=
  if q/triePoolLanes t b < 9 then triePoolLevels t b else 0

def triePoolStride (t b : ℕ) : ℕ := triePoolWidth b+triePoolLevels t b+2

def triePoolRowBase (pool t b q : ℕ) : ℕ := pool+q*triePoolStride t b

def triePoolBit (pool t b q i : ℕ) : ℕ := triePoolRowBase pool t b q+1+i

def triePoolAcc (pool t b q j : ℕ) : ℕ := triePoolRowBase pool t b q+1+triePoolWidth b+j

def triePoolAfter (pool t b : ℕ) : ℕ := pool+2^(triePoolHeight t b)*triePoolStride t b

def triePoolPort (pool t b q : ℕ) : TrieRowPort :=
  ⟨triePoolRowBase pool t b q, triePoolBit pool t b q,
    fun i => triePoolBit pool t b q (2^b+i),fun i => triePoolBit pool t b q (2*2^b+i)⟩

def triePoolRowWords (a : Assignment) (pool t b : ℕ) : List (Option WordEdge) :=
  List.ofFn (fun q : Fin (2^(triePoolHeight t b)) => (triePoolPort pool t b q.val).decode a (2^b))

def triePoolSource (t b q j : ℕ) : (ℕ × ℕ) × ℕ × ℕ × ℕ :=
  let x := chunkLaneSource b (b+j) (q%triePoolLanes t b)
  let f := q/triePoolLanes t b
  (x.1,f/3,f%3,x.2)

def triePoolWire (base n t b q j : ℕ) : TrieWordWires :=
  let x := triePoolSource t b q j
  normalizeSlotWires base n t b x.1 x.2.1 x.2.2.1

def triePoolEnable (base n t b q j : ℕ) : ℕ :=
  (triePoolWire base n t b q j).emit (triePoolSource t b q j).2.2.2

def triePoolPayload (base n t b q j i : ℕ) : ℕ :=
  let w := triePoolWire base n t b q j
  let k := (triePoolSource t b q j).2.2.2
  let B := (2:ℕ)^b
  if i < B then w.parent k i else
    if i < 2*B then w.raw (k*B+(i-B)) else w.child k (i-2*B)

def triePoolLaneGates (base pool n t b q : ℕ) : List Gate :=
  gatherArray (triePoolWidth b) (triePoolCount t b q)
    (triePoolRowBase pool t b q) (triePoolAcc pool t b q) (triePoolBit pool t b q)
    (triePoolEnable base n t b q) (triePoolPayload base n t b q)

def triePoolGateList (base pool n t b : ℕ) : List Gate :=
  (List.range (2^(triePoolHeight t b))).flatMap (triePoolLaneGates base pool n t b)

theorem triePoolLanes_eq {t b : ℕ} (h : b ≤ layoutHeight t) :
    triePoolLanes t b = layoutHorizon t/2^b := by
  have he := normalizeChunkGeometry h
  unfold layoutHorizon triePoolLanes
  rw [← he,Nat.mul_div_cancel_left]
  positivity

theorem triePoolSource_valid {t b q j : ℕ} (h : b ≤ layoutHeight t)
    (hj : j < triePoolCount t b q) :
    let d := triePoolSource t b q j
    d.1 ∈ layoutSlots t ∧ d.2.1 < 3 ∧ d.2.2.1 < 3 ∧
      b ≤ d.1.2 ∧ d.2.2.2 < 2^(d.1.2-b) := by
  have hCases : q/triePoolLanes t b < 9 := by
    by_contra he
    simp [triePoolCount,he] at hj
  have he : b+j ≤ layoutHeight t := by
    simp only [triePoolCount,hCases,if_true,triePoolLevels] at hj
    omega
  have hPos : 0 < triePoolLanes t b := by unfold triePoolLanes; positivity
  have hPool : q%triePoolLanes t b < layoutHorizon t/2^b := by
    rw [← triePoolLanes_eq h]
    exact Nat.mod_lt _ hPos
  have hj' : b ≤ b+j := Nat.le_add_right _ _
  have hs := chunkLaneSource_mem hj' he hPool
  have hk := chunkLaneSource_chunk_lt b (b+j) (q%triePoolLanes t b)
  refine ⟨hs,?_,Nat.mod_lt _ (by decide),hj',hk⟩
  change q/triePoolLanes t b/3 < 3
  exact (Nat.div_lt_iff_lt_mul (by decide)).mpr hCases

theorem triePoolSource_hits {t b : ℕ} (hb : b ≤ layoutHeight t) {s : ℕ × ℕ}
    (hs : s ∈ layoutSlots t) (hbs : b ≤ s.2) {r f k : ℕ} (hr : r < 3) (hf : f < 3)
    (hk : k < 2^(s.2-b)) :
    ∃ q < 2^(triePoolHeight t b), ∃ j < triePoolCount t b q,
      triePoolSource t b q j = (s,r,f,k) := by
  rcases s with ⟨a,d⟩
  let N := triePoolLanes t b
  let i := physicalChunkLane b a k
  let q := (3*r+f)*N+i
  have hp : 0 < N := by unfold N triePoolLanes; positivity
  have hi : i < N := by
    change i < triePoolLanes t b
    rw [triePoolLanes_eq hb]
    exact physicalChunkLane_lt hs hbs hk
  have hdiv : q/N = 3*r+f := by
    unfold q
    rw [Nat.mul_comm (3*r+f) N,Nat.mul_add_div hp,Nat.div_eq_of_lt hi,Nat.add_zero]
  have hmod : q%N = i := by
    unfold q
    rw [Nat.add_comm,Nat.add_mul_mod_self_right,Nat.mod_eq_of_lt hi]
  have hBnd : q < 2^(triePoolHeight t b) := by
    have hmul : (3*r+f+1)*N ≤ 16*N := Nat.mul_le_mul_right N (by omega)
    unfold q
    have he : 2^(triePoolHeight t b) = 16*N := by
      unfold triePoolHeight N triePoolLanes
      rw [pow_add,Nat.mul_comm]
      rfl
    rw [he]
    rw [Nat.add_mul,Nat.one_mul] at hmul
    omega
  have hslot := layout_mem.mp hs
  refine ⟨q,hBnd,d-b,?_,?_⟩
  · change d-b < if q/N < 9 then triePoolLevels t b else 0
    rw [hdiv,if_pos (by omega)]
    unfold triePoolLevels
    change b ≤ d at hbs
    have hd : d ≤ layoutHeight t := hslot.2.1
    omega
  · have hd : b+(d-b) = d := Nat.add_sub_of_le hbs
    have hrw : (3*r+f)/3 = r := by rw [Nat.mul_add_div (by decide),
      Nat.div_eq_of_lt hf,Nat.add_zero]
    have hfw : (3*r+f)%3 = f := by rw [Nat.mul_comm,Nat.add_comm,Nat.add_mul_mod_self_right,
      Nat.mod_eq_of_lt hf]
    change ((chunkLaneSource b (b+(d-b)) (q%N)).1,(q/N)/3,(q/N)%3,
      (chunkLaneSource b (b+(d-b)) (q%N)).2) = ((a,d),r,f,k)
    rw [hd,hmod,hdiv,hrw,hfw,chunkLaneSource_inverse hbs hslot.2.2 hk]

end CNFEncComplexity.Robson

/- RobsonTriePoolSemantics -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

theorem triePoolCands_eq (base pool n t b q : ℕ) :
    triePoolLaneGates base pool n t b q =
      gatherGates (triePoolRowBase pool t b q) (triePoolAcc pool t b q)
        (fun i : Fin (triePoolWidth b) => triePoolBit pool t b q i.val)
        (List.ofFn (fun j : Fin (triePoolCount t b q) =>
          (triePoolEnable base n t b q j.val,fun i => triePoolPayload base n t b q j.val i.val))) := by
  exact gatherArray_exact .. 

private theorem triePoolLane_local (a : Assignment) (base pool n t b q : ℕ)
    (h : ∀ g ∈ triePoolLaneGates base pool n t b q, g.Holds a) :
    (a (triePoolRowBase pool t b q) = true ↔ ∃ j : Fin (triePoolCount t b q),
      a (triePoolEnable base n t b q j.val) = true) ∧
    (∀ j : Fin (triePoolCount t b q), a (triePoolEnable base n t b q j.val) = true →
      ∀ i : Fin (triePoolWidth b),
        a (triePoolPayload base n t b q j.val i.val) = a (triePoolBit pool t b q i.val)) := by
  have hg := (triePoolCands_eq base pool n t b q) ▸ h
  let cs := List.ofFn (fun j : Fin (triePoolCount t b q) =>
    (triePoolEnable base n t b q j.val,fun i : Fin (triePoolWidth b) =>
      triePoolPayload base n t b q j.val i.val))
  have hL : cs.length = triePoolCount t b q := by simp [cs]
  have hs := gatherGates_sound a _ _ _ cs hg
  refine ⟨?_,?_⟩
  · rw [hs.1]
    constructor
    · rintro ⟨j,hj⟩
      refine ⟨Fin.cast hL j,?_⟩
      simpa only [cs,List.getElem_ofFn,Fin.val_cast] using hj
    · rintro ⟨j,hj⟩
      refine ⟨Fin.cast hL.symm j,?_⟩
      simpa only [cs,List.getElem_ofFn,Fin.val_cast] using hj
  · intro j hj i
    have ho := hs.2.2 (Fin.cast hL.symm j) (by simpa only [cs,List.getElem_ofFn,Fin.val_cast] using hj) i
    simpa only [cs,List.getElem_ofFn,Fin.val_cast] using ho

theorem triePoolLane_decode (a : Assignment) (base pool n t b q j : ℕ)
    (h : ∀ g ∈ triePoolLaneGates base pool n t b q, g.Holds a)
    (hj : j < triePoolCount t b q) (ha : a (triePoolEnable base n t b q j) = true) :
    (triePoolPort pool t b q).decode a (2^b) = some
      (trieEdge a (triePoolWire base n t b q j) (2^b) (triePoolSource t b q j).2.2.2) := by
  let w := triePoolWire base n t b q j
  let k := (triePoolSource t b q j).2.2.2
  let B := (2:ℕ)^b
  obtain ⟨hOn,hV⟩ := triePoolLane_local a base pool n t b q h
  have hp := hOn.mpr ⟨⟨j,hj⟩,ha⟩
  have hgParent (i : ℕ) (hi : i < B) :
      a (w.parent k i) = a (triePoolBit pool t b q i) := by
    have hh := hV ⟨j,hj⟩ ha ⟨i,by unfold triePoolWidth; change i < 3*B; omega⟩
    change a (if i < B then w.parent k i else _) = _ at hh
    simpa only [if_pos hi] using hh
  have hgDigit (i : ℕ) (hi : i < B) :
      a (w.raw (k*B+i)) = a (triePoolBit pool t b q (B+i)) := by
    have hh := hV ⟨j,hj⟩ ha ⟨B+i,by unfold triePoolWidth; change B+i < 3*B; omega⟩
    change a (if B+i < B then _ else if B+i < 2*B then w.raw (k*B+(B+i-B))
      else _) = _ at hh
    simpa [show ¬ B+i < B by omega,show B+i < 2*B by omega] using hh
  have hgChild (i : ℕ) (hi : i < B) :
      a (w.child k i) = a (triePoolBit pool t b q (2*B+i)) := by
    have hh := hV ⟨j,hj⟩ ha ⟨2*B+i,by unfold triePoolWidth; change 2*B+i < 3*B; omega⟩
    change a (if 2*B+i < B then _ else if 2*B+i < 2*B then _ else w.child k (2*B+i-2*B)) = _ at hh
    simpa [show ¬ 2*B+i < B by omega,show ¬ (2*B+i < 2*B) by omega] using hh
  have hd : (triePoolPort pool t b q).edge a B = trieEdge a w B k := by
    unfold TrieRowPort.edge triePoolPort trieEdge
    change WordEdge.mk _ _ _ = WordEdge.mk _ _ _
    have hhP := (wireValue_eq_iff a (w.parent k) (triePoolBit pool t b q) B).2 hgParent
    have hhD := (wireValue_eq_iff a (fun i => w.raw (k*B+i)) (fun i => triePoolBit pool t b q (B+i)) B).2 hgDigit
    have hhC := (wireValue_eq_iff a (w.child k) (fun i => triePoolBit pool t b q (2*B+i)) B).2 hgChild
    rw [hhP,hhD,hhC]
  exact if_pos hp |>.trans (congrArg some hd)

theorem triePool_contains (a : Assignment) (base pool n t b : ℕ)
    (hb : b ≤ layoutHeight t)
    (h : ∀ g ∈ triePoolGateList base pool n t b, g.Holds a)
    (s : ℕ × ℕ) (hs : s ∈ layoutSlots t) (r f : ℕ) (hr : r < 3) (hf : f < 3) :
    ∀ e ∈ normalizeWordRows a base n t b s r f, e ∈ (triePoolRowWords a pool t b).filterMap id := by
  by_cases hj : b ≤ s.2
  · intro e he
    simp only [normalizeWordRows,if_pos hj,trieWordRows] at he
    obtain ⟨k,hk,rfl⟩ := List.mem_map.mp he
    obtain ⟨hIn,hon⟩ := List.mem_filter.mp hk
    obtain ⟨q,hq,i,hi,hSrc⟩ := triePoolSource_hits hb hs hj hr hf (List.mem_range.mp hIn)
    have hEnable : a (triePoolEnable base n t b q i) = true := by
      simpa [triePoolEnable,triePoolWire,hSrc] using hon
    have hLane (g : Gate) (hg : g ∈ triePoolLaneGates base pool n t b q) : g.Holds a :=
      h g (List.mem_flatMap.mpr ⟨q,List.mem_range.mpr hq,hg⟩)
    have hDecode := triePoolLane_decode a base pool n t b q i hLane hi hEnable
    apply List.mem_filterMap.mpr
    refine ⟨(triePoolPort pool t b q).decode a (2^b),List.mem_ofFn.mpr ⟨⟨q,hq⟩,rfl⟩,?_⟩
    simpa [triePoolWire,hSrc] using hDecode
  · simp [normalizeWordRows,hj]

theorem triePool_sound_subset (a : Assignment) (base pool n t b : ℕ)
    (hb : b ≤ layoutHeight t)
    (h : ∀ g ∈ triePoolGateList base pool n t b, g.Holds a)
    (dict : List WordEdge)
    (hSub : ∀ s ∈ layoutSlots t, ∀ r < 3, ∀ f < 3,
      ∀ e ∈ normalizeWordRows a base n t b s r f, e ∈ dict) :
    ∀ e ∈ (triePoolRowWords a pool t b).filterMap id, e ∈ dict := by
  intro e he
  obtain ⟨y,hy,hEq⟩ := List.mem_filterMap.mp he
  obtain ⟨q,rfl⟩ := List.mem_ofFn.mp hy
  have hp : a (triePoolRowBase pool t b q.val) = true := by
    change (if a (triePoolRowBase pool t b q.val) then some _ else none) = some e at hEq
    split at hEq
    · assumption
    · contradiction
  have hLane (g : Gate) (hg : g ∈ triePoolLaneGates base pool n t b q.val) : g.Holds a :=
    h g (List.mem_flatMap.mpr ⟨q.val,List.mem_range.mpr q.isLt,hg⟩)
  have ⟨j,hj⟩ := (triePoolLane_local a base pool n t b q.val hLane).1.mp hp
  have hd := triePoolLane_decode a base pool n t b q.val j.val hLane j.isLt hj
  have heq := Option.some.inj (hd.symm.trans hEq)
  let d := triePoolSource t b q.val j.val
  obtain ⟨hs,hr,hf,hb',hk⟩ := triePoolSource_valid hb j.isLt
  rw [← heq]
  apply hSub d.1 hs d.2.1 hr d.2.2.1 hf
  have hd : b ≤ d.1.2 := hb'
  rw [normalizeWordRows,if_pos hd,trieWordRows]
  exact List.mem_map.mpr ⟨d.2.2.2,List.mem_filter.mpr ⟨List.mem_range.mpr hk,hj⟩,rfl⟩

end CNFEncComplexity.Robson

/- RobsonTriePoolWitness -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

theorem triePoolInput_below {base pool n t b q j : ℕ}
    (hL : sharedLimit n t ≤ base) (hPool : normalizeAfter base t ≤ pool)
    (hb : b ≤ layoutHeight t) (hj : j < triePoolCount t b q) :
    triePoolEnable base n t b q j < pool ∧
      ∀ i < triePoolWidth b, triePoolPayload base n t b q j i < pool := by
  let d := triePoolSource t b q j
  let k := d.2.2.2
  let s := d.1
  let r := d.2.1
  let f := d.2.2.1
  let B := (2:ℕ)^b
  let K := (2:ℕ)^(s.2-b)
  let W := (2:ℕ)^s.2
  let u := normalizeWordBase base t s r f
  let w := normalizeSlotWires base n t b s r f
  obtain ⟨hs,hr,hf,hbs,hk⟩ := triePoolSource_valid hb hj
  have he : B*K = W := normalizeChunkGeometry hbs
  have hK : k < K := hk
  have hKey := normalizeKeyBase_range base t (⟨s,hs⟩,⟨r,hr⟩,⟨f,hf⟩)
  have hu : u+normalizeStride t ≤ normalizeAfter base t := hKey.2
  have hW : W ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) (layout_mem.mp hs).2.1
  have hScratch (p : TrieRest B K) : w.restName p < pool := by
    have h := 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) p
    rw [he] at h
    change u+W+1 ≤ w.restName p ∧ w.restName p < u+6*W+4 at h
    refine h.2.trans_le (?_ : u+6*W+4 ≤ pool)
    unfold normalizeStride at hu
    omega
  refine ⟨hScratch (.emit ⟨k,hK⟩),?_⟩
  intro i hi
  change i < 3*B at hi
  change (if i < B then w.parent k i else
    if i < 2*B then w.raw (k*B+(i-B)) else w.child k (i-2*B)) < pool
  by_cases hpa : i < B
  · rw [if_pos hpa]
    exact hScratch (.parent ⟨k,hK⟩ ⟨i,hpa⟩)
  · rw [if_neg hpa]
    by_cases hd : i < 2*B
    · rw [if_pos hd]
      have hAll : k*B+B ≤ W := by
        have h := Nat.mul_le_mul_right B hK
        simpa [Nat.succ_mul,Nat.mul_comm K B,he] using h
      have hh : k*B+(i-B) < W := by omega
      have hr' := (normalizeWordFrame_raw base n t b s r f hs hr hf).1 _ hh
      exact hr'.trans_le (hL.trans (hKey.1.trans (by unfold normalizeStride at hu; omega)))
    · rw [if_neg hd]
      exact hScratch (.child ⟨k,hK⟩ ⟨i-2*B,by omega⟩)

private theorem triePoolEnabled_live (a : Assignment) {base n t b q j : ℕ}
    (hShape : SlotsWellFormed a n t)
    (hNorm : ∀ g ∈ normalizeLayoutGates base n t b, g.Holds a)
    (hb : b ≤ layoutHeight t) (hj : j < triePoolCount t b q)
    (hEn : a (triePoolEnable base n t b q j) = true) :
    (triePoolSource t b q j).1 ∈ liveSlots a n t := by
  let d := triePoolSource t b q j
  let s := d.1
  let w := triePoolWire base n t b q j
  obtain ⟨hs,hr,hf,hbs,hk⟩ := triePoolSource_valid hb hj
  have hLong : ∀ g ∈ longTrieGates w (2^b) (2^(s.2-b)), g.Holds a := by
    intro g hg
    apply hNorm
    apply List.mem_flatMap.mpr
    refine ⟨s,hs, List.mem_flatMap.mpr ⟨d.2.1,List.mem_range.mpr hr,
      List.mem_flatMap.mpr ⟨d.2.2.1,List.mem_range.mpr hf,?_⟩⟩⟩
    change b ≤ s.2 at hbs
    simp only [normalizeWordGates,if_pos hbs]
    exact hg
  have h := (longTrieGates_emit a w (2^b) (2^(s.2-b))
    (by positivity) (by positivity) hLong d.2.2.2 hk).mp hEn
  have hOn : a (port n t s (3+5*d.2.1) 0) = true := h.1
  apply List.mem_filter.mpr
  refine ⟨hs,?_⟩
  by_contra! hNot
  have hOff : slotLive a n t s = false := by
    change slotLive a n t s ≠ true at hNot
    simpa using hNot
  have hEmpty := (hShape.2 s hs hOff).2
  have hMem : ∃ e, portMemory a n t s d.2.1 = some e := by
    simp [portMemory,hOn]
  obtain ⟨e,he⟩ := hMem
  have hRow : e ∈ slotRows a n t s :=
    List.mem_filterMap.mpr ⟨d.2.1,List.mem_range.mpr hr,he⟩
  simp [hEmpty] at hRow

private theorem triePoolOutput_injective (pool t b q : ℕ) :
    Function.Injective (gatherOutputName (count := triePoolCount t b q)
      (triePoolRowBase pool t b q) (triePoolAcc pool t b q)
      (fun i : Fin (triePoolWidth b) => triePoolBit pool t b q i.val)) := by
  intro p p' he
  cases p <;> cases p' <;>
    simp only [gatherOutputName,triePoolBit,triePoolAcc] at he
  all_goals try rfl
  all_goals try (exfalso; omega)
  case acc.acc i j => exact congrArg GatherOutput.acc (Fin.ext (by omega))
  case bit.bit i j => exact congrArg GatherOutput.bit (Fin.ext (by omega))

private theorem triePoolOutput_range (pool t b q : ℕ)
    (i : GatherOutput (triePoolWidth b) (triePoolCount t b q)) :
    let v := gatherOutputName (triePoolRowBase pool t b q) (triePoolAcc pool t b q)
      (fun i : Fin (triePoolWidth b) => triePoolBit pool t b q i.val) i
    triePoolRowBase pool t b q ≤ v ∧ v < triePoolRowBase pool t b q+triePoolStride t b := by
  have hC : triePoolCount t b q ≤ triePoolLevels t b := by unfold triePoolCount; split <;> omega
  cases i with
  | active => simp [gatherOutputName,triePoolStride] <;> omega
  | acc i => have := i.isLt; simp [gatherOutputName,triePoolAcc,triePoolStride]; omega
  | bit i => have := i.isLt; simp [gatherOutputName,triePoolBit,triePoolStride]; omega

theorem triePoolLane_extend (a : Assignment) (base pool n t b q : ℕ)
    (hL : sharedLimit n t ≤ base) (hPool : normalizeAfter base t ≤ pool)
    (hb : b ≤ layoutHeight t) (hShape : SlotsWellFormed a n t)
    (hNorm : ∀ g ∈ normalizeLayoutGates base n t b, g.Holds a) :
    ∃ a' : Assignment,
      (∀ i, i < triePoolRowBase pool t b q ∨ triePoolRowBase pool t b q+triePoolStride t b ≤ i →
        a' i = a i) ∧
      (∀ g ∈ triePoolLaneGates base pool n t b q, g.Holds a') := by
  let cs := List.ofFn (fun j : Fin (triePoolCount t b q) =>
    (triePoolEnable base n t b q j.val,fun i : Fin (triePoolWidth b) =>
      triePoolPayload base n t b q j.val i.val))
  let out := fun i : Fin (triePoolWidth b) => triePoolBit pool t b q i.val
  let active := triePoolRowBase pool t b q
  let acc := triePoolAcc pool t b q
  have hc : cs.length = triePoolCount t b q := by simp [cs]
  have hSome (i : Fin cs.length) : cs[i.val].1 = triePoolEnable base n t b q i.val := by
    simp [cs]
  have hPayload (i : Fin cs.length) (k : Fin (triePoolWidth b)) :
      cs[i.val].2 k = triePoolPayload base n t b q i.val k.val := by simp [cs]
  have hU (j k : Fin cs.length) (hj : a cs[j.val].1 = true) (hk : a cs[k.val].1 = true) :
      j=k := by
    have hpJ : j.val < triePoolCount t b q := hc ▸ j.isLt
    have hpK : k.val < triePoolCount t b q := hc ▸ k.isLt
    have hJ := triePoolEnabled_live a hShape hNorm hb hpJ ((hSome j) ▸ hj)
    have hK := triePoolEnabled_live a hShape hNorm hb hpK ((hSome k) ▸ hk)
    have eq := chunkLaneSource_unique hShape (Nat.le_add_right b j.val)
      (Nat.le_add_right b k.val) hJ hK
    exact Fin.ext (Nat.add_left_cancel eq)
  have hN : Function.Injective (gatherOutputName (count := cs.length) active acc out) := by
    rw [hc]
    exact triePoolOutput_injective pool t b q
  have hRange (p : GatherOutput (triePoolWidth b) cs.length) :
      active ≤ gatherOutputName active acc out p ∧
        gatherOutputName active acc out p < active+triePoolStride t b := by
    have hCc : cs.length ≤ triePoolLevels t b := by
      rw [hc]; unfold triePoolCount; split <;> omega
    cases p with
    | active => simp [gatherOutputName,triePoolStride,active] <;> omega
    | acc j =>
      have hj := j.isLt
      simp [gatherOutputName,triePoolAcc,triePoolStride,active,acc]
      omega
    | bit j => have hj := j.isLt; simp [gatherOutputName,triePoolBit,triePoolStride,active,out]; omega
  have hAP : pool ≤ active := Nat.le_add_right _ _
  obtain ⟨a',hFr,hSat⟩ := gatherGates_extends a active acc out cs hU hN
    (fun j => by
      rintro ⟨p,he⟩
      have hj : j.val < triePoolCount t b q := hc ▸ j.isLt
      have h := (triePoolInput_below hL hPool hb hj).1
      have hp := (hRange p).1
      rw [he,hSome] at hp
      exact (not_lt_of_ge (hAP.trans hp)) h)
    (fun j k => by
      rintro ⟨p,he⟩
      have hj : j.val < triePoolCount t b q := hc ▸ j.isLt
      have h := (triePoolInput_below hL hPool hb hj).2 _ k.isLt
      have hp := (hRange p).1
      rw [he,hPayload] at hp
      exact (not_lt_of_ge (hAP.trans hp)) h)
  refine ⟨a',?_,?_⟩
  · intro i hi
    apply hFr
    rintro ⟨p,he⟩
    obtain ⟨hl,hh⟩ := hRange p
    rw [he] at hl hh
    change i < active ∨ active+triePoolStride t b ≤ i at hi
    omega
  · simpa only [triePoolCands_eq] using hSat

end CNFEncComplexity.Robson

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

/-- All enumerated physical pool lanes are independently writable. Active
candidate bits and payload bits below the pool are preserved. -/
theorem triePool_complete (a : Assignment) (base pool n t b : ℕ)
    (hL : sharedLimit n t ≤ base) (hPool : normalizeAfter base t ≤ pool)
    (hb : b ≤ layoutHeight t) (hShape : SlotsWellFormed a n t)
    (hNorm : ∀ g ∈ normalizeLayoutGates base n t b, g.Holds a) :
    ∃ a' : Assignment,
      (∀ i, i < pool ∨ triePoolAfter pool t b ≤ i → a' i = a i) ∧
      (∀ g ∈ triePoolGateList base pool n t b, g.Holds a') := by
  classical
  choose pick hFrame hGate using fun q =>
    triePoolLane_extend a base pool n t b q hL hPool hb hShape hNorm
  let step := triePoolStride t b
  have hStep : 0 < step := by unfold step triePoolStride; omega
  let top := triePoolAfter pool t b
  let a' : Assignment := fun i => if pool ≤ i ∧ i < top then pick ((i-pool)/step) i else a i
  have hFix (i : ℕ) (hi : i < pool ∨ top ≤ i) : a' i = a i := by
    unfold a'
    rw [if_neg]
    omega
  have hLocal (q i : ℕ) (hq : q < 2^(triePoolHeight t b))
      (h : triePoolRowBase pool t b q ≤ i ∧ i < triePoolRowBase pool t b q+step) :
      a' i = pick q i := by
    have hq' : q+1 ≤ 2^(triePoolHeight t b) := hq
    have hp := Nat.mul_le_mul_right step hq'
    rw [Nat.add_mul,Nat.one_mul] at hp
    change pool+q*step ≤ i ∧ i < pool+q*step+step at h
    have htop : top = pool+2^(triePoolHeight t b)*step := rfl
    have hd : pool ≤ i ∧ i < top := by omega
    have hDecomp : i-pool = (i-(pool+q*step))+q*step := by omega
    have hh : i-(pool+q*step) < step := by omega
    unfold a'
    rw [if_pos hd,hDecomp,Nat.add_mul_div_right _ _ hStep,Nat.div_eq_of_lt hh,Nat.zero_add]
  refine ⟨a',hFix,?_⟩
  intro g hg
  obtain ⟨q,hq,hqg⟩ := List.mem_flatMap.mp hg
  have hq' := List.mem_range.mp hq
  let cs := List.ofFn (fun j : Fin (triePoolCount t b q) =>
    (triePoolEnable base n t b q j.val,
      fun i : Fin (triePoolWidth b) => triePoolPayload base n t b q j.val i.val))
  let active := triePoolRowBase pool t b q
  let out := fun i : Fin (triePoolWidth b) => triePoolBit pool t b q i.val
  let acc := triePoolAcc pool t b q
  have hc : cs.length = triePoolCount t b q := by simp [cs]
  have hC : triePoolCount t b q ≤ triePoolLevels t b := by unfold triePoolCount; split <;> omega
  have hQA : pool ≤ active := Nat.le_add_right _ _
  have hActive : a' active = pick q active := by apply hLocal q _ hq'; exact ⟨le_rfl,by omega⟩
  have hAcc (i : ℕ) (hi : i ≤ cs.length) : a' (acc i) = pick q (acc i) := by
    apply hLocal q _ hq'
    change active ≤ active+1+triePoolWidth b+i ∧ active+1+triePoolWidth b+i < active+step
    unfold step triePoolStride
    omega
  have hOut (i : Fin (triePoolWidth b)) : a' (out i) = pick q (out i) := by
    apply hLocal q _ hq'
    change active ≤ active+1+i.val ∧ active+1+i.val < active+step
    have := i.isLt
    unfold step triePoolStride
    omega
  have hEnabled (i : Fin cs.length) : a' cs[i.val].1 = pick q cs[i.val].1 := by
    have hi : i.val < triePoolCount t b q := hc ▸ i.isLt
    have hp := (triePoolInput_below hL hPool hb hi).1
    have he : cs[i.val].1 = triePoolEnable base n t b q i.val := by simp [cs]
    rw [he,hFix _ (.inl hp),hFrame q _ (.inl (hp.trans_le hQA))]
  have hPayload (j : Fin cs.length) (i : Fin (triePoolWidth b)) :
      a' (cs[j.val].2 i) = pick q (cs[j.val].2 i) := by
    have hj : j.val < triePoolCount t b q := hc ▸ j.isLt
    have hp := (triePoolInput_below hL hPool hb hj).2 _ i.isLt
    have he : cs[j.val].2 i = triePoolPayload base n t b q j.val i.val := by simp [cs]
    rw [he,hFix _ (.inl hp),hFrame q _ (.inl (hp.trans_le hQA))]
  have hqSat : ∀ g ∈ gatherGates active acc out cs, g.Holds (pick q) := by
    simpa only [triePoolCands_eq] using hGate q
  obtain ⟨h0,hL,hLoc⟩ := (gatherGates_local (pick q) active acc out cs).mp hqSat
  apply (gatherGates_local a' active acc out cs).mpr ?_ g
  · exact (triePoolCands_eq base pool n t b q) ▸ hqg
  · refine ⟨?_,?_,?_⟩
    · rwa [hAcc _ (Nat.zero_le _)]
    · rwa [hActive,hAcc _ le_rfl]
    · intro i
      rw [hAcc _ i.isLt,hAcc _ i.isLt.le,hEnabled i]
      refine ⟨(hLoc i).1,(hLoc i).2.1,?_⟩
      intro hOn k
      rw [hPayload i k,hOut k]
      exact (hLoc i).2.2 hOn k

theorem triePoolGateList_length (base pool n t b : ℕ) (hb : b ≤ layoutHeight t) :
    (triePoolGateList base pool n t b).length ≤ 160*(layoutHorizon t*(layoutHeight t+1)) := by
  let B := (2:ℕ)^b
  let N := triePoolLanes t b
  let C := layoutHeight t+1
  have hp : 0 < B := by unfold B; positivity
  have he : B*N = layoutHorizon t := normalizeChunkGeometry hb
  have hN : N ≤ layoutHorizon t := by
    rw [← he,Nat.mul_comm]
    simpa using Nat.mul_le_mul_left N hp
  have hC : 0 < C := by unfold C; omega
  have hNpool : 2^(triePoolHeight t b) = 16*N := by
    unfold triePoolHeight N triePoolLanes
    rw [pow_add,Nat.mul_comm]
    rfl
  have hSingle (q : ℕ) : (triePoolLaneGates base pool n t b q).length ≤ 2+(8*B)*C := by
    have hq : triePoolCount t b q ≤ C := by unfold triePoolCount triePoolLevels C; split <;> omega
    rw [triePoolCands_eq,gatherGates_length,List.length_ofFn]
    apply Nat.add_le_add_left
    exact Nat.mul_le_mul (by unfold triePoolWidth; change 2+2*(3*B) ≤ 8*B; omega) hq
  have hSum (xs : List ℕ) :
      (xs.flatMap (triePoolLaneGates base pool n t b)).length ≤ xs.length*(2+(8*B)*C) := by
    induction xs with
    | nil => simp
    | cons x xs ih =>
      rw [List.flatMap_cons,List.length_append,List.length_cons,Nat.add_mul,Nat.one_mul,Nat.add_comm]
      exact Nat.add_le_add ih (hSingle x)
  unfold triePoolGateList
  refine (hSum _).trans ?_
  rw [List.length_range,hNpool]
  have hExpand : (16*N)*(2+(8*B)*C) = 32*N+128*((B*N)*C) := by ring
  rw [hExpand,he]
  have hSmall : 32*N ≤ 32*(layoutHorizon t*C) := by
    exact Nat.mul_le_mul_left _ (hN.trans (by simpa using Nat.mul_le_mul_left (layoutHorizon t) hC))
  change 32*N+128*(layoutHorizon t*C) ≤ 160*(layoutHorizon t*C)
  omega

end CNFEncComplexity.Robson

/- RobsonTrieDictionary -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

private theorem trieSortCheckNames (base B : ℕ) (c : Bool) (rows : List TrieRowPort)
    (hN : ∀ r ∈ rows, r.below B base)
    (g : Gate) (hg : g ∈ trieSortCheckGates B c base rows) (i : ℕ) (hi : i ∈ RobsonCNF.Gate.names g) :
    i < base+rows.length*triePairSpan B := by
  induction rows generalizing base with
  | nil => simp [trieSortCheckGates] at hg
  | cons l rows ih =>
    cases rows with
    | nil => simp [trieSortCheckGates] at hg
    | cons r rs =>
      simp only [trieSortCheckGates,List.mem_append] at hg
      cases hg with
      | inl hl =>
        have hlt := trieRowPair_names base B c l r (hN l List.mem_cons_self)
          (hN r (List.mem_cons_of_mem _ List.mem_cons_self)) g hl i hi
        exact hlt.trans_le (by
          rw [List.length_cons,Nat.add_mul,Nat.one_mul]
          omega)
      | inr hr =>
        have hN' (r' : TrieRowPort) (hh : r' ∈ r::rs) : r'.below B (base+triePairSpan B) :=
          TrieRowPort.below_mono (hN _ (List.mem_cons_of_mem _ hh)) (Nat.le_add_right _ _)
        have hh := ih _ hN' hr
        rw [List.length_cons,Nat.add_mul,Nat.one_mul]
        omega

private theorem trieDataBelow (base B h : ℕ) (src : ℕ→ℕ→ℕ)
    (hS : ∀ q < 2^h, ∀ i < trieRowWidth B, src q i < base) (q : Fin (2^h)) :
    (trieRowFromNat B (src q.val)).below B base := by
  refine ⟨hS _ q.isLt _ (by unfold trieRowWidth; omega), ?_⟩
  intro i hi
  exact ⟨hS _ q.isLt _ (by unfold trieRowWidth; omega),
    hS _ q.isLt _ (by unfold trieRowWidth; omega),
    hS _ q.isLt _ (by unfold trieRowWidth; omega)⟩

private theorem trieSourceRows_frame (a a' : Assignment) (base B h : ℕ) (src : ℕ→ℕ→ℕ)
    (hS : ∀ q < 2^h, ∀ i < trieRowWidth B, src q i < base) (hFrame : ∀ i < base, a i = a' i) :
    trieSourceRows a B h src = trieSourceRows a' B h src := by
  unfold trieSourceRows
  congr 1
  funext q
  exact TrieRowPort.decode_frame (trieDataBelow base B h src hS q) hFrame

private theorem trieRouteOut_below' (base B h : ℕ) (q : Fin (2^h)) :
    (trieRowFromNat B (trieRouteOut base B h q.val)).below B (trieRouteEnd base B h) := by
  have hh (i : ℕ) (hi : i < trieRowWidth B) :
      trieRouteOut base B h q.val i < trieRouteEnd base B h := by
    rw [← trieRouteName_out base B h q ⟨i,hi⟩]
    exact (trieRouteName_range _ _ _ _).2
  refine ⟨hh _ (by unfold trieRowWidth; omega),?_⟩
  intro i hi
  exact ⟨hh _ (by unfold trieRowWidth; omega),hh _ (by unfold trieRowWidth; omega),
    hh _ (by unfold trieRowWidth; omega)⟩

private theorem trieSortPass_names_lt (base B h : ℕ) (c : Bool) (src : ℕ→ℕ→ℕ)
    (hS : ∀ q < 2^h, ∀ i < trieRowWidth B, src q i < base)
    (g : Gate) (hg : g ∈ trieSortPass base B h c src) (i : ℕ)
    (hi : i ∈ RobsonCNF.Gate.names g) : i < trieSortPassEnd base B h := by
  have hR : trieRouteEnd base B h ≤ trieSortPassEnd base B h := Nat.le_add_right _ _
  have hBase : base ≤ trieRouteEnd base B h := Nat.le_add_right _ _
  simp only [trieSortPass,List.mem_append] at hg
  rcases hg with (hg|hg)|hg
  · obtain ⟨q,hq,hg⟩ := List.mem_flatMap.mp hg
    obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hg
    have hv : trieRouteIn base B q j < trieRouteEnd base B h := by
      rw [← trieRouteName_in base B h ⟨q,List.mem_range.mp hq⟩ ⟨j,List.mem_range.mp hj⟩]
      exact (trieRouteName_range _ _ _ _).2
    simp only [RobsonCNF.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hi
    rcases hi with rfl|rfl
    · exact hv.trans_le hR
    · exact (hS _ (List.mem_range.mp hq) _ (List.mem_range.mp hj)).trans_le (hBase.trans hR)
  · obtain ⟨g,hg,rfl⟩ := List.mem_map.mp hg
    have hv (r : RouteVar h (Fin (trieRowWidth B))) :
        trieRouteName base B h r < trieSortPassEnd base B h :=
      ((trieRouteName_range _ _ _ _).2).trans_le hR
    cases g with
    | copy _ _ =>
      simp only [RouteGate.named,RobsonCNF.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hi
      rcases hi with rfl|rfl <;> exact hv _
    | mux _ _ _ _ =>
      simp only [RouteGate.named,RobsonCNF.Gate.names,List.mem_cons,List.mem_nil_iff,or_false] at hi
      rcases hi with rfl|rfl|rfl|rfl <;> exact hv _
  · have hBound (r : TrieRowPort) (hr : r ∈ trieRouteRows base B h) :
        r.below B (trieRouteEnd base B h) := by
      obtain ⟨q,rfl⟩ := List.mem_ofFn.mp hr
      exact trieRouteOut_below' base B h q
    have hf := trieSortCheckNames _ _ c _ hBound g hg i hi
    simpa [trieSortPassEnd,trieRouteRows] using hf

def trieNonzeroList (B h : ℕ) (src : ℕ→ℕ→ℕ) : List Gate :=
  (List.range (2^h)).flatMap (fun q => trieNonzeroGates B (trieRowFromNat B (src q)))

def trieDictionaryGates (base B h : ℕ) (src : ℕ→ℕ→ℕ) : List Gate :=
  trieNonzeroList B h src ++ trieSortPass base B h false src ++
    trieSortPass (trieSortPassEnd base B h) B h true src

def trieDictionaryEnd (base B h : ℕ) : ℕ := trieSortPassEnd (trieSortPassEnd base B h) B h

theorem trieDictionaryGates_sound (a : Assignment) (base B h : ℕ) (src : ℕ→ℕ→ℕ)
    (hG : ∀ g ∈ trieDictionaryGates base B h src, g.Holds a) :
    WordEdge.Interned ((trieSourceRows a B h src).filterMap id) := by
  simp only [trieDictionaryGates,List.forall_mem_append] at hG
  obtain ⟨⟨hZ,hK⟩,hC⟩ := hG
  obtain ⟨key,hKey,hKeyC⟩ := trieSortPass_sound a base B h false src hK
  obtain ⟨child,hChild,hChildC⟩ := trieSortPass_sound a _ B h true src hC
  refine trieDictionary_sound B _ key child ?_ ?_ hKey hChild hKeyC hChildC
  · intro e he
    obtain ⟨o,ho,hEq⟩ := List.mem_filterMap.mp he
    obtain ⟨q,rfl⟩ := List.mem_ofFn.mp ho
    change (if a (src q.val 0) then some _ else none) = some e at hEq
    split at hEq
    · obtain rfl := Option.some.inj hEq
      exact wireValue_lt ..
    · contradiction
  · intro e he
    obtain ⟨o,ho,hEq⟩ := List.mem_filterMap.mp he
    obtain ⟨q,rfl⟩ := List.mem_ofFn.mp ho
    exact (trieNonzero_exact a B (trieRowFromNat B (src q.val))).mp
      (fun g hg => hZ g (List.mem_flatMap.mpr ⟨q.val,List.mem_range.mpr q.isLt,hg⟩)) _ hEq

theorem trieDictionaryGates_extend (a : Assignment) (base B h : ℕ) (src : ℕ→ℕ→ℕ)
    (hS : ∀ q < 2^h, ∀ i < trieRowWidth B, src q i < base)
    (hW : WordEdge.Interned ((trieSourceRows a B h src).filterMap id)) :
    ∃ a' : Assignment,
      (∀ i, i < base ∨ trieDictionaryEnd base B h ≤ i → a' i = a i) ∧
      (∀ g ∈ trieDictionaryGates base B h src, g.Holds a') := by
  let next := trieSortPassEnd base B h
  have hNext : base ≤ next := (Nat.le_add_right _ _).trans (Nat.le_add_right _ _)
  obtain ⟨a₁,hF₁,hFirst⟩ := trieSortPass_extend a base B h false src hS hW
  have hW₁ : WordEdge.Interned ((trieSourceRows a₁ B h src).filterMap id) := by
    rw [trieSourceRows_frame a₁ a base B h src hS (fun i hi => hF₁ _ (.inl hi))]
    exact hW
  have hS' (q : ℕ) (hq : q < 2^h) (i : ℕ) (hi : i < trieRowWidth B) : src q i < next :=
    (hS q hq i hi).trans_le hNext
  obtain ⟨a₂,hF₂,hSecond⟩ := trieSortPass_extend a₁ next B h true src hS' hW₁
  have hB : next ≤ trieSortPassEnd next B h := (Nat.le_add_right _ _).trans (Nat.le_add_right _ _)
  have hF (i : ℕ) (hi : i < base ∨ trieDictionaryEnd base B h ≤ i) : a₂ i = a i := by
    rcases hi with hi | hi
    · exact (hF₂ _ (.inl (hi.trans_le hNext))).trans (hF₁ _ (.inl hi))
    · exact (hF₂ _ (.inr hi)).trans (hF₁ _ (.inr (hB.trans hi)))
  refine ⟨a₂,hF,?_⟩
  simp only [trieDictionaryGates,List.forall_mem_append]
  refine ⟨⟨?_,?_⟩,hSecond⟩
  · intro g hg
    obtain ⟨q,hq,hg⟩ := List.mem_flatMap.mp hg
    apply (trieNonzero_exact a₂ B (trieRowFromNat B (src q))).2 ?_ _ hg
    intro e he
    let q' : Fin (2^h) := ⟨q,List.mem_range.mp hq⟩
    have hD := TrieRowPort.decode_frame (trieDataBelow base B h src hS q') (a := a₂) (b := a)
      (fun i hi => hF _ (.inl hi))
    have hh := hD ▸ he
    exact hW.nonzero _ (List.mem_filterMap.mpr ⟨_,List.mem_ofFn.mpr ⟨q',rfl⟩,hh⟩)
  · intro g hg
    exact (g.holds_congr a₂ a₁ (fun i hi =>
      hF₂ _ (.inl (trieSortPass_names_lt base B h false src hS g hg i hi)))).mpr (hFirst g hg)

/-- The dictionary check reads its source and two consecutive private sorting areas. -/
theorem trieDictionaryGates_names_lt (base B h : ℕ) (src : ℕ → ℕ → ℕ)
    (hSource : ∀ q < 2^h, ∀ i < trieRowWidth B, src q i < base)
    (g : Gate) (hg : g ∈ trieDictionaryGates base B h src)
    (i : ℕ) (hi : i ∈ RobsonCNF.Gate.names g) : i < trieDictionaryEnd base B h := by
  have hPass (n : ℕ) : n ≤ trieSortPassEnd n B h :=
    (Nat.le_add_right _ _).trans (Nat.le_add_right _ _)
  have hEnd : trieSortPassEnd base B h ≤ trieDictionaryEnd base B h := hPass _
  simp only [trieDictionaryGates,List.mem_append] at hg
  rcases hg with (hg|hg)|hg
  · obtain ⟨q,hq,hg⟩ := List.mem_flatMap.mp hg
    simp only [trieNonzeroGates,List.mem_singleton] at hg
    subst g
    simp only [RobsonCNF.Gate.names,List.map_cons,List.mem_cons] at hi
    rcases hi with hi | hi
    · subst i
      exact (hSource q (List.mem_range.mp hq) 0 (by simp [trieRowWidth])).trans_le
        ((hPass _).trans hEnd)
    · obtain ⟨lit,hlit,rfl⟩ := List.mem_map.mp hi
      obtain ⟨bit,hbit,rfl⟩ := List.mem_map.mp hlit
      change src q (1+2*B+bit) < trieDictionaryEnd base B h
      have hbit := List.mem_range.mp hbit
      have hRange : 1+2*B+bit < trieRowWidth B := by unfold trieRowWidth; omega
      exact (hSource q (List.mem_range.mp hq) _ hRange).trans_le ((hPass _).trans hEnd)
  · exact (trieSortPass_names_lt base B h false src hSource g hg i hi).trans_le hEnd
  · exact trieSortPass_names_lt _ B h true src
      (fun q hq k hk => (hSource q hq k hk).trans_le (hPass _)) g hg i hi

end CNFEncComplexity.Robson

/- RobsonTrieComponent -/

namespace CNFEncComplexity.Robson

open CookLevin RobsonCNF

/-- Finite packed shape shared by the pool and the two sorted permutations. -/
def triePoolSourceWire (pool t b q i : ℕ) : ℕ :=
  triePoolRowBase pool t b q+i

theorem triePoolSourceWire_below (pool t b : ℕ) (q : ℕ) (hq : q < 2^(triePoolHeight t b))
    (i : ℕ) (hi : i < trieRowWidth (2^b)) :
    triePoolSourceWire pool t b q i < triePoolAfter pool t b := by
  have hMq := Nat.mul_le_mul_right (triePoolStride t b) hq
  change ((q+1)*triePoolStride t b) ≤ 2^(triePoolHeight t b)*triePoolStride t b at hMq
  rw [Nat.add_mul,Nat.one_mul] at hMq
  unfold triePoolSourceWire triePoolAfter triePoolRowBase at *
  unfold triePoolStride trieRowWidth triePoolWidth at *
  omega

private theorem triePoolSourceWire_row (pool t b q : ℕ) :
    trieRowFromNat (2^b) (triePoolSourceWire pool t b q) = triePoolPort pool t b q := by
  simp [trieRowFromNat,triePoolPort,triePoolSourceWire,triePoolBit,Nat.add_assoc]
  funext i
  simp [triePoolBit,Nat.add_assoc]

theorem triePoolSourceWords (a : Assignment) (pool t b : ℕ) :
    trieSourceRows a (2^b) (triePoolHeight t b) (triePoolSourceWire pool t b) =
    triePoolRowWords a pool t b := by
  unfold trieSourceRows triePoolRowWords
  apply congrArg List.ofFn
  funext q
  rw [triePoolSourceWire_row]

def normalizeMemoryGates (base n t b : ℕ) : List Gate :=
  let pool := normalizeAfter base t
  normalizeLayoutGates base n t b ++ triePoolGateList base pool n t b ++
    trieDictionaryGates (triePoolAfter pool t b) (2^b) (triePoolHeight t b) (triePoolSourceWire pool t b)

def normalizeMemoryEnd (base t b : ℕ) : ℕ :=
  trieDictionaryEnd (triePoolAfter (normalizeAfter base t) t b) (2^b) (triePoolHeight t b)

theorem normalizeMemoryGates_sound (a : Assignment) (base n t b : ℕ)
    (hb : b ≤ layoutHeight t) (h : ∀ g ∈ normalizeMemoryGates base n t b, g.Holds a) :
    ∃ dict : List WordEdge, WordEdge.Interned dict ∧
      PackedSlots a n t (2^b) dict (slotCompactRows a base n t b) := by
  simp only [normalizeMemoryGates,List.forall_mem_append] at h
  obtain ⟨⟨hNorm,hPool⟩,hDict⟩ := h
  let pool := normalizeAfter base t
  let dict := (triePoolRowWords a pool t b).filterMap id
  have hD := trieDictionaryGates_sound a (triePoolAfter pool t b) (2^b) (triePoolHeight t b)
    (triePoolSourceWire pool t b) hDict
  rw [triePoolSourceWords] at hD
  refine ⟨dict,hD,⟨?_,?_⟩⟩
  · intro s hs
    exact normalizedSlot_sound a base n t b s
      (fun g hg => hNorm g (List.mem_flatMap.mpr ⟨s,hs,hg⟩)) dict
      (fun r hr f hf => triePool_contains a base pool n t b hb hPool s hs r f hr hf)
  · intro s hs r hr
    obtain ⟨i,_,hi⟩ := List.mem_filterMap.mp hr
    unfold slotCompactMemory at hi
    split at hi
    · obtain rfl := Option.some.inj hi
      exact ⟨Nat.size_le.mpr (wireValue_lt ..),Nat.size_le.mpr (wireValue_lt ..),Nat.size_le.mpr (wireValue_lt ..)⟩
    · contradiction

theorem normalizePoolGates_frame (a α : Assignment) (base pool n t b : ℕ)
    (hBase : sharedLimit n t ≤ base) (hP : normalizeAfter base t ≤ pool) (hb : b ≤ layoutHeight t)
    (hFr : ∀ i < triePoolAfter pool t b, α i = a i)
    (h : ∀ g ∈ triePoolGateList base pool n t b, g.Holds a) :
    ∀ g ∈ triePoolGateList base pool n t b, g.Holds α := by
  intro g hg
  obtain ⟨q,hq,hg⟩ := List.mem_flatMap.mp hg
  have hq' := List.mem_range.mp hq
  have hM := Nat.mul_le_mul_right (triePoolStride t b) hq'
  change (q+1)*triePoolStride t b ≤ 2^(triePoolHeight t b)*triePoolStride t b at hM
  rw [Nat.add_mul,Nat.one_mul] at hM
  let acc := triePoolAcc pool t b q
  let on := triePoolRowBase pool t b q
  let out := fun j : Fin (triePoolWidth b) => triePoolBit pool t b q j.val
  let cs := List.ofFn (fun i : Fin (triePoolCount t b q) =>
      (triePoolEnable base n t b q i.val,fun j : Fin (triePoolWidth b) =>
        triePoolPayload base n t b q i.val j.val))
  have hCL : cs.length = triePoolCount t b q := by simp [cs]
  have hC : triePoolCount t b q ≤ triePoolLevels t b := by unfold triePoolCount; split <;> omega
  have hOn : α on = a on := by
    apply hFr
    change pool+q*triePoolStride t b < _
    unfold triePoolAfter
    have hp : 0 < triePoolStride t b := by unfold triePoolStride; omega
    omega
  have hAcc (i : ℕ) (hi : i ≤ cs.length) : α (acc i) = a (acc i) := by
    apply hFr
    change pool+q*triePoolStride t b+1+triePoolWidth b+i < _
    unfold triePoolAfter triePoolStride at *
    omega
  have hOut (i : Fin (triePoolWidth b)) : α (out i) = a (out i) := by
    apply hFr
    change pool+q*triePoolStride t b+1+i.val < _
    have := i.isLt
    unfold triePoolAfter triePoolStride at *
    omega
  have hLow : pool ≤ triePoolAfter pool t b := Nat.le_add_right _ _
  have hEn (i : Fin cs.length) : α cs[i.val].1 = a cs[i.val].1 := by
    apply hFr
    have hi : i.val < triePoolCount t b q := hCL ▸ i.isLt
    simpa [cs] using (triePoolInput_below hBase hP hb hi).1.trans_le hLow
  have hData (i : Fin cs.length) (j : Fin (triePoolWidth b)) :
      α (cs[i.val].2 j) = a (cs[i.val].2 j) := by
    apply hFr
    have hi : i.val < triePoolCount t b q := hCL ▸ i.isLt
    simpa [cs] using ((triePoolInput_below hBase hP hb hi).2 _ j.isLt).trans_le hLow
  have hSat : ∀ g ∈ gatherGates on acc out cs, g.Holds a := by
    intro g hg
    apply h g (List.mem_flatMap.mpr ⟨q,hq,?_⟩)
    rwa [triePoolCands_eq]
  obtain ⟨h0,hLast,hStep⟩ := (gatherGates_local a on acc out cs).mp hSat
  apply (gatherGates_local α on acc out cs).mpr ?_ g
  · exact (triePoolCands_eq base pool n t b q) ▸ hg
  · refine ⟨?_,?_,?_⟩
    · rwa [hAcc _ (Nat.zero_le _)]
    · rwa [hOn,hAcc _ le_rfl]
    · intro k
      rw [hAcc _ k.isLt,hAcc _ k.isLt.le,hEn k]
      refine ⟨(hStep k).1,(hStep k).2.1,?_⟩
      intro hp i
      rw [hOut i,hData k i]
      exact (hStep k).2.2 hp i

end CNFEncComplexity.Robson

/- RobsonTrieComponentComplete -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

private theorem trieSlots_frame (a β : Assignment) (n t : ℕ)
    (hFr : ∀ i < sharedLimit n t, β i = a i) (h : SlotsWellFormed a n t) :
    SlotsWellFormed β n t := by
  apply (slotShapeGates_exact β n t).mp
  intro g hg
  exact (gate_congr g (fun i hi => hFr i (slotShapeGates_shared hg hi))).mpr
    ((slotShapeGates_exact a n t).mpr h g hg)

theorem normalizeMemoryGates_complete (a : Assignment) (base n t b : ℕ)
    (hBase : sharedLimit n t ≤ base) (hb : b ≤ layoutHeight t)
    (hShape : SlotsWellFormed a n t) (dict : List WordEdge) (lab : ℕ → ℕ)
    (hGood : WordEdge.Interned dict) (hDict : ∀ e ∈ dict, e.child < 2^(2^b))
    (hLab : ∀ x ∈ observationWords (memoryStream a n t), WordLabel (2^b) dict x (lab x)) :
    ∃ α : Assignment,
      (∀ i, i < base ∨ normalizeMemoryEnd base t b ≤ i → α i = a i) ∧
      (∀ g ∈ normalizeMemoryGates base n t b, g.Holds α) ∧
      ∀ s ∈ layoutSlots t, ∀ r < 3,
        slotCompactMemory α base n t b s r = (portMemory a n t s r).map (compactRow lab) := by
  let pool := normalizeAfter base t
  let top := triePoolAfter pool t b
  have hbP : base ≤ pool := Nat.le_add_right _ _
  have hpT : pool ≤ top := Nat.le_add_right _ _
  have hPass (start : ℕ) : start ≤ trieSortPassEnd start (2^b) (triePoolHeight t b) :=
    (Nat.le_add_right _ _).trans (Nat.le_add_right _ _)
  have htD : top ≤ normalizeMemoryEnd base t b :=
    (hPass top).trans (hPass (trieSortPassEnd top (2^b) (triePoolHeight t b)))
  obtain ⟨β,hFβ,hGβ,hLβ,hRβ⟩ := normalizeLayout_complete a base n t b hBase dict lab hDict
    (fun s hs r hr f hf hOn => hLab _ (normalizedWord_mem_input a n t s hs r f hr hf hOn))
  have hSβ := trieSlots_frame a β n t
    (fun i hi => hFβ i (.inl (hi.trans_le hBase))) hShape
  obtain ⟨γ,hFγ,hGγ⟩ := triePool_complete β base pool n t b hBase le_rfl hb hSβ hGβ
  have hRγ (s : ℕ×ℕ) (hs : s ∈ layoutSlots t) (r : ℕ) (hr : r < 3) (f : ℕ) (hf : f < 3)
      (e : WordEdge) (he : e ∈ normalizeWordRows γ base n t b s r f) : e ∈ dict := by
    have heq := normalizeWordRows_congr γ β base n t b s r f hs hr hf
      (fun i hi => hFγ _ (.inl (normalizeWord_name_below hBase hs hr hf hi)))
    exact hRβ s hs r hr f hf e (heq ▸ he)
  have hDγ : WordEdge.Interned ((trieSourceRows γ (2^b) (triePoolHeight t b)
      (triePoolSourceWire pool t b)).filterMap id) := by
    rw [triePoolSourceWords]
    exact hGood.of_subset (triePool_sound_subset γ base pool n t b hb hGγ dict hRγ)
  obtain ⟨α,hFα,hGα⟩ := trieDictionaryGates_extend γ top (2^b) (triePoolHeight t b)
    (triePoolSourceWire pool t b) (triePoolSourceWire_below pool t b) hDγ
  have hF (i : ℕ) (hi : i < base ∨ normalizeMemoryEnd base t b ≤ i) : α i = a i := by
    rcases hi with hi|hi
    · exact (hFα _ (.inl (hi.trans_le (hbP.trans hpT)))).trans
        ((hFγ _ (.inl (hi.trans_le hbP))).trans (hFβ _ (.inl hi)))
    · exact (hFα _ (.inr hi)).trans
        ((hFγ _ (.inr (htD.trans hi))).trans (hFβ _ (.inr ((hpT.trans htD).trans hi))))
  have hLow (i : ℕ) (hi : i < pool) : α i = β i :=
    (hFα _ (.inl (hi.trans_le hpT))).trans (hFγ _ (.inl hi))
  refine ⟨α,hF,?_,?_⟩
  · simp only [normalizeMemoryGates,List.forall_mem_append]
    refine ⟨⟨?_,normalizePoolGates_frame γ α base pool n t b hBase le_rfl hb
      (fun i hi => hFα _ (.inl hi)) hGγ⟩,hGα⟩
    intro g hg
    obtain ⟨s,hs,hm⟩ := List.mem_flatMap.mp hg
    obtain ⟨r,hr,hm⟩ := List.mem_flatMap.mp hm
    obtain ⟨f,hf,hm⟩ := List.mem_flatMap.mp hm
    apply (gate_congr g (fun i hi => hLow _ (normalizeWord_name_below hBase hs
      (List.mem_range.mp hr) (List.mem_range.mp hf)
      (normalizeWordGates_frame base n t b s r f hs (List.mem_range.mp hr)
        (List.mem_range.mp hf) g hm i hi)))).mpr
    exact hGβ g hg
  · intro s hs r hr
    apply slotCompactMemory_witness a α base n t b s hs r hr lab
      (fun i hi => hF _ (.inl (hi.trans_le hBase)))
    intro f hf hOn
    exact (normalizeSlotLabel_frame α β base n t b hBase s hs r f hr hf hLow).trans
      (hLβ s hs r hr f hf hOn)

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