Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Local Boolean relations for RAM tier updates

Definition
CNFEncComplexity_RobsonMemoryTierRowGates

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

complexity-theorysatisfiability

Bounds-aware width flags, row encoding and update gates for the optional chronological records of one RAM slot.

Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryTrieSlots
import Definitions.Def_CNFEncComplexity_RobsonMemoryParameters

set_option maxHeartbeats 4000000
set_option linter.all false

/- RobsonLocalTierGates -/

namespace CNFEncComplexity.Robson
open CookLevin

/-- Two fixed chronological lanes per raw observation. A write cancels its old
tier entry before it inserts its new one. When the tier stays the same, the first
lane is a single replacement. Inactive slots and irrelevant tiers emit nothing. -/
def emitTier (j : ℕ) : Option ObservedAccess → List (Option LocalRecord)
  | none => [none,none]
  | some r =>
    let a := r.action.address
    let v := r.action.value
    let dest := bitTier a v = j
    let src := bitTier a r.old = j
    if r.action.writes then
      [if src then some ⟨a,some r.old,if dest then some v else none⟩ else none,
       if dest ∧ ¬src then some ⟨a,none,some v⟩ else none]
    else [if dest then some ⟨a,some v,some v⟩ else none,none]

@[simp] theorem emitTier_length (j : ℕ) (o : Option ObservedAccess) :
    (emitTier j o).length = 2 := by
  cases o with
  | none => rfl
  | some r => cases e : r.action.writes <;> simp [emitTier,e]

theorem emitTier_exact (j : ℕ) (o : Option ObservedAccess) :
    (emitTier j o).filterMap id =
      atTier j (o.toList.flatMap (fun r => tieredAccess bitTier r.action r.old)) := by
  cases o with
  | none => rfl
  | some r =>
    let a := r.action.address
    let v := r.action.value
    have ht : ((bitTier a r.old,a) = (bitTier a v,a)) ↔ bitTier a r.old = bitTier a v := by simp
    cases hw : r.action.writes
    · by_cases hj : bitTier a v = j <;>
        simp [emitTier,tieredAccess,hw,atTier,a,v,hj,localRecord]
    · by_cases hSrc : bitTier a r.old = j <;> by_cases hDest : bitTier a v = j
      · have same : bitTier a r.old = bitTier a v := hSrc.trans hDest.symm
        simp [emitTier,tieredAccess,hw,atTier,a,v,hSrc,hDest,same,localRecord]
      · have diff : bitTier a r.old ≠ bitTier a v := fun h => hDest (h.symm.trans hSrc)
        simp [emitTier,tieredAccess,hw,atTier,a,v,hSrc,hDest,Ne.symm hDest,diff,localRecord]
      · have diff : bitTier a r.old ≠ bitTier a v := fun h => hSrc (h.trans hDest)
        simp [emitTier,tieredAccess,hw,atTier,a,v,hSrc,hDest,diff,localRecord]
      · by_cases he : bitTier a r.old = bitTier a v <;>
          simp [emitTier,tieredAccess,hw,atTier,a,v,hSrc,hDest,he,List.filter_cons]

open RobsonCNF

/-- The suffix query at an index beyond the word width reads the false sentinel. -/
def tierAbove (n base k : ℕ) : ℕ := widthFlagWire base (min n k)

theorem tierAbove_exact (a : Assignment) (n base : ℕ) (key : ℕ → ℕ) (k : ℕ)
    (hg : ∀ g ∈ widthCircuit base n key, g.Holds a) :
    a (tierAbove n base k) = decide (k < (wireValue a key n).size) := by
  rw [tierAbove,widthCircuit_exact base n key a hg (min_le_left _ _)]
  have h := Nat.size_le.mpr (wireValue_lt a key n)
  by_cases hk : k ≤ n
  · rw [min_eq_right hk]
  · have h₁ : ¬ k < (wireValue a key n).size := by omega
    rw [min_eq_left (by omega),decide_eq_false (show ¬ n < _ from by omega),decide_eq_false h₁]

/-- Once suffix flags have been made, deciding one tier takes a constant
number of gates, regardless of the original word widths. -/
def tierTestGates (j aBase vBase n out : ℕ) : List Gate :=
  let aboveA := tierAbove n aBase
  let aboveV := tierAbove n vBase
  let hi := 2^j - 1
  if j=0 then
    [.disj out (aboveA hi) (aboveV hi), .inv (out+1) out]
  else
    let lo := 2^(j-1)-1
    [.disj out (aboveA hi) (aboveV hi), .inv (out+1) out,
      .disj (out+2) (aboveA lo) (aboveV lo), .conj (out+3) (out+1) (out+2)]

def tierTestOutput (j out : ℕ) : ℕ := if j=0 then out+1 else out+3

private theorem tier_size_zero (a v : ℕ) :
    bitTier a v = 0 ↔ ¬ (0 < a.size ∨ 0 < v.size) := by
  unfold bitTier
  simp only [Nat.size_eq_zero,not_or,not_lt]
  omega

private theorem tier_size_pos (a v j : ℕ) (hj : 0 < j) :
    bitTier a v = j ↔ (2^(j-1)-1 < a.size ∨ 2^(j-1)-1 < v.size) ∧
      ¬(2^j-1 < a.size ∨ 2^j-1 < v.size) := by
  unfold bitTier
  have h0 : 0 < (2:ℕ)^j := Nat.two_pow_pos _
  have h1 : 0 < (2:ℕ)^(j-1) := Nat.two_pow_pos _
  have e : j-1+1=j := by omega
  constructor
  · intro h
    have hLo := Nat.lt_size.mp (show j-1 < (max a.size v.size).size by omega)
    have hHi := Nat.size_le.mp (show (max a.size v.size).size ≤ j from h.le)
    omega
  · rintro ⟨hLo,hHi⟩
    have hl : j-1 < (max a.size v.size).size := Nat.lt_size.mpr (by omega)
    have hh : (max a.size v.size).size ≤ j := Nat.size_le.mpr (by omega)
    omega

theorem tierTestGates_exact (a : Assignment) (j aBase vBase n out : ℕ) (ka kv : ℕ → ℕ)
    (ha : ∀ g ∈ widthCircuit aBase n ka,g.Holds a)
    (hv : ∀ g ∈ widthCircuit vBase n kv,g.Holds a)
    (hg : ∀ g ∈ tierTestGates j aBase vBase n out, g.Holds a) :
    a (tierTestOutput j out) = decide (bitTier (wireValue a ka n) (wireValue a kv n) = j) := by
  have ha' := fun k => tierAbove_exact a n aBase ka k ha
  have hv' := fun k => tierAbove_exact a n vBase kv k hv
  by_cases h0 : j = 0
  · subst j
    simp only [tierTestGates,if_true,tierTestOutput,pow_zero,Nat.sub_self, List.forall_mem_cons,
      List.not_mem_nil,false_implies,implies_true,and_true,Gate.Holds] at hg ⊢
    rw [hg.2,hg.1,ha',hv']
    apply Bool.eq_iff_iff.mpr
    simp [tier_size_zero]
  · simp only [tierTestGates,tierTestOutput,if_neg h0,List.forall_mem_cons,List.not_mem_nil,
      false_implies,implies_true,and_true,Gate.Holds] at hg ⊢
    rw [hg.2.2.2,hg.2.1,hg.1,hg.2.2.1,ha',hv',ha',hv']
    apply Bool.eq_iff_iff.mpr
    simp [tier_size_pos _ _ _ (Nat.pos_of_ne_zero h0),and_comm]

theorem tierTestGates_length (j aBase vBase n out : ℕ) :
    (tierTestGates j aBase vBase n out).length ≤ 4 := by
  unfold tierTestGates
  by_cases h : j=0 <;> simp [h]

/-- Output flag keys are packed in eight fresh positions. The only
data-dependent word in the result is the first lane's before value. -/
def emissionControl (base live writes src dst : ℕ) : List Gate :=
  [.mux base writes src dst, .conj (base+1) live base, .inv (base+2) src,
   .conj (base+3) writes dst, .conj (base+4) (base+2) (base+3),
   .conj (base+5) live (base+4), .inv (base+6) writes,
   .disj (base+7) (base+6) dst]

theorem emissionControl_exact (a : Assignment) (base live writes src dst : ℕ)
    (hg : ∀ g ∈ emissionControl base live writes src dst, g.Holds a) :
    a (base+1) = (a live && (if a writes then a src else a dst)) ∧
    a (base+5) = (a live && (!a src && (a writes && a dst))) ∧
    a (base+7) = (!a writes || a dst) := by
  simp only [emissionControl,List.forall_mem_cons,List.not_mem_nil,false_implies,implies_true,
    and_true,Gate.Holds] at hg
  obtain ⟨h0,h1,h2,h3,h4,h5,h6,h7⟩ := hg
  exact ⟨by rw [h1,h0],by rw [h5,h4,h2,h3],by rw [h7,h6]⟩

def emissionMux (base w writes : ℕ) (old value : ℕ → ℕ) : List Gate :=
  (List.range w).map (fun i => .mux (base+8+i) writes (old i) (value i))

theorem emissionMux_exact (a : Assignment) (base w writes : ℕ) (old value : ℕ→ℕ)
    (hg : ∀ g ∈ emissionMux base w writes old value, g.Holds a) :
    wireValue a (fun i => base+8+i) w =
      if a writes then wireValue a old w else wireValue a value w := by
  cases he : a writes
  · simp only [he,Bool.false_eq_true,if_false]
    apply (wireValue_eq_iff _ _ _ _).2
    intro i hi
    have h := hg (.mux _ _ _ _) (List.mem_map.mpr ⟨i,List.mem_range.mpr hi,rfl⟩)
    simpa [Gate.Holds,he] using h
  · simp only [he,if_true]
    apply (wireValue_eq_iff _ _ _ _).2
    intro i hi
    have h := hg (.mux _ _ _ _) (List.mem_map.mpr ⟨i,List.mem_range.mpr hi,rfl⟩)
    simpa [Gate.Holds,he] using h

end CNFEncComplexity.Robson

/- RobsonEmitFormat -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

theorem wireValue_take_of_fit (a : Assignment) (key : ℕ → ℕ) {n w : ℕ}
    (hwn : w ≤ n) (hFit : wireValue a key n < 2^w) :
    wireValue a key w = wireValue a key n := by
  induction n generalizing w with
  | zero =>
    have e : w=0 := by omega
    subst w
    rfl
  | succ n ih =>
    by_cases e : w=n+1
    · rw [e]
    · have hSub : w ≤ n := by omega
      have hN : (2:ℕ)^w ≤ 2^n := Nat.pow_le_pow_right (by decide) hSub
      cases hBit : a (key n)
      · have hE : wireValue a key (n+1) = wireValue a key n := by simp [wireValue,hBit]
        rw [hE] at hFit ⊢
        exact ih hSub hFit
      · have hSum : wireValue a key (n+1) = wireValue a key n + 2^n := by
          simp [wireValue,hBit]
        rw [hSum] at hFit
        omega

theorem wireValue_clip (a : Assignment) (key : ℕ → ℕ) (n w z : ℕ) (hz : a z=false)
    (hfit : (wireValue a key n).size ≤ w) :
    wireValue a (paddedKey n z key) w = wireValue a key n := by
  rcases le_total n w with hn|hw
  · exact wireValue_pad a n z key hz w hn
  · have h : wireValue a (paddedKey n z key) w = wireValue a key w := by
      apply wireValue_key_congr
      intro i hi
      simp [paddedKey,hi.trans_le hw]
    exact h.trans (wireValue_take_of_fit a key hw (Nat.size_le.mp hfit))

structure EmitInput where
  width : ℕ
  live : ℕ
  writes : ℕ
  address : ℕ → ℕ
  value : ℕ → ℕ
  old : ℕ → ℕ

def EmitInput.read (u : EmitInput) (a : Assignment) : Option ObservedAccess :=
  if a u.live then some ⟨⟨wireValue a u.address u.width,wireValue a u.value u.width,a u.writes⟩,
    wireValue a u.old u.width⟩ else none

/-- The untagged row format consumed by the fixed stable sorter. -/
def emissionRow (w z active beforeFlag afterFlag : ℕ) (addr before after : ℕ → ℕ) (k : ℕ) : ℕ :=
  if k=0 then active
  else if k < 1+w then addr (k-1)
  else if k=1+w then beforeFlag
  else if k < 2+2*w then before (k-(2+w))
  else if k=2+2*w then afterFlag
  else if k < 3+3*w then after (k-(3+2*w)) else z

theorem emissionRow_read (a : Assignment) (w z active beforeFlag afterFlag : ℕ)
    (addr before after : ℕ → ℕ) :
    laneRecord a w 0 (emissionRow w z active beforeFlag afterFlag addr before after) =
      (if a active then some ⟨wireValue a addr w,memoryOpt a beforeFlag before w,
        memoryOpt a afterFlag after w⟩ else none) := by
  have hAddr (i : ℕ) (hi : i < w) :
      laneAddress 0 (emissionRow w z active beforeFlag afterFlag addr before after) i = addr i := by
    have h : 1+i < 1+w := by omega
    change emissionRow w z active beforeFlag afterFlag addr before after (1+i) = _
    unfold emissionRow
    rw [if_neg (by omega),if_pos (by omega)]
    simp
  have hB (i : ℕ) (hi : i < w) :
      laneBefore w 0 (emissionRow w z active beforeFlag afterFlag addr before after) i = before i := by
    unfold laneBefore
    rw [show 1+0+w+1+i=2+w+i by omega]
    unfold emissionRow
    rw [if_neg (by omega),if_neg (by omega),if_neg (by omega),if_pos (by omega)]
    rw [show 2+w+i-(2+w)=i by omega]
  have hF (i : ℕ) (hi : i < w) :
      laneAfter w 0 (emissionRow w z active beforeFlag afterFlag addr before after) i = after i := by
    have he : 1+0+w+(1+w)+1+i = 3+2*w+i := by omega
    unfold laneAfter
    rw [he]
    unfold emissionRow
    rw [if_neg (by omega),if_neg (by omega),if_neg (by omega),if_neg (by omega),if_neg (by omega),
      if_pos (by omega),show 3+2*w+i-(3+2*w)=i by omega]
  have hBF : laneBeforeFlag w 0 (emissionRow w z active beforeFlag afterFlag addr before after) = beforeFlag := by
    unfold laneBeforeFlag emissionRow
    rw [if_neg (by omega),if_neg (by omega),if_pos (by omega)]
  have hAF : laneAfterFlag w 0 (emissionRow w z active beforeFlag afterFlag addr before after) = afterFlag := by
    unfold laneAfterFlag emissionRow
    rw [if_neg (by omega),if_neg (by omega),if_neg (by omega),if_neg (by omega),if_pos (by omega)]
  have hA := wireValue_key_congr a (n:=w) hAddr
  have hB' := wireValue_key_congr a (n:=w) hB
  have hF' := wireValue_key_congr a (n:=w) hF
  have hk : laneActive (emissionRow w z active beforeFlag afterFlag addr before after) = active := by
    simp [laneActive,emissionRow]
  unfold laneRecord
  rw [hk,hA]
  unfold memoryOpt
  rw [hBF,hAF,hB',hF']

def emitFirstRow (u : EmitInput) (w z o base : ℕ) : ℕ → ℕ :=
  emissionRow w z (base+1) o (base+7) (paddedKey u.width z u.address)
    (fun i => base+8+i) (paddedKey u.width z u.value)

def emitSecondRow (u : EmitInput) (w z o base : ℕ) : ℕ → ℕ :=
  emissionRow w z (base+5) z o (paddedKey u.width z u.address)
    (fun _ => z) (paddedKey u.width z u.value)

theorem emitRows_exact (a : Assignment) (u : EmitInput) (j z o base s d : ℕ)
    (hz : a z=false) (ho : a o=true)
    (hs : a s = decide (bitTier (wireValue a u.address u.width) (wireValue a u.old u.width) = j))
    (hd : a d = decide (bitTier (wireValue a u.address u.width) (wireValue a u.value u.width) = j))
    (hc : ∀ g ∈ emissionControl base u.live u.writes s d, g.Holds a)
    (hm : ∀ g ∈ emissionMux base (2^j) u.writes (paddedKey u.width z u.old)
      (paddedKey u.width z u.value),g.Holds a) :
    [laneRecord a (2^j) 0 (emitFirstRow u (2^j) z o base),
     laneRecord a (2^j) 0 (emitSecondRow u (2^j) z o base)] = emitTier j (u.read a) := by
  set addr := wireValue a u.address u.width with hA
  set value := wireValue a u.value u.width with hV
  set old := wireValue a u.old u.width with hO
  have hAddr (h : bitTier addr value=j ∨ bitTier addr old=j) :
      wireValue a (paddedKey u.width z u.address) (2^j) = addr := by
    refine wireValue_clip _ _ _ _ _ hz ?_
    rcases h with h|h
    · exact (h ▸ (bitTier_width addr value).1).le
    · exact (h ▸ (bitTier_width addr old).1).le
  have hValue (h : bitTier addr value=j) :
      wireValue a (paddedKey u.width z u.value) (2^j) = value :=
    wireValue_clip _ _ _ _ _ hz (h ▸ (bitTier_width addr value).2.le)
  have hOld (h : bitTier addr old=j) :
      wireValue a (paddedKey u.width z u.old) (2^j) = old :=
    wireValue_clip _ _ _ _ _ hz (h ▸ (bitTier_width addr old).2.le)
  have hC := emissionControl_exact a base u.live u.writes s d hc
  have hM := emissionMux_exact _ _ _ _ _ _ hm
  simp only [emitFirstRow,emitSecondRow,emissionRow_read,memoryOpt,hz,ho,if_true,
    Bool.false_eq_true,if_false,hC.1,hC.2.1,hC.2.2,hM,hs,hd,EmitInput.read,← hA,← hV,← hO]
  cases hL : a u.live
  · simp [hL,emitTier]
  · cases hW : a u.writes
    · by_cases hd : bitTier addr value=j
      · simp [hL,hW,emitTier,hd,hAddr (.inl hd),hValue hd]
      · simp [hL,hW,emitTier,hd]
    · by_cases hs : bitTier addr old=j <;> by_cases hd : bitTier addr value=j
      · simp [hL,hW,emitTier,hs,hd,hAddr (.inr hs),hValue hd,hOld hs]
      · simp [hL,hW,emitTier,hs,hd,hAddr (.inr hs),hOld hs]
      · simp [hL,hW,emitTier,hs,hd,hAddr (.inl hd),hValue hd]
      · simp [hL,hW,emitTier,hs,hd]

end CNFEncComplexity.Robson

/- RobsonEmitWitness -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

def tierFlagValues (a : Assignment) (j n xBase yBase : ℕ) : List Bool :=
  let hi := a (tierAbove n xBase (2^j-1)) || a (tierAbove n yBase (2^j-1))
  let lo := a (tierAbove n xBase (2^(j-1)-1)) || a (tierAbove n yBase (2^(j-1)-1))
  [hi,!hi,lo,!hi && lo]

/-- Install a short list of private boolean outputs. -/
def fillBits (a : Assignment) (base : ℕ) (bits : List Bool) : Assignment := fun r =>
  if base ≤ r ∧ r < base+bits.length then bits.getD (r-base) false else a r

theorem fillBits_at (a : Assignment) (base : ℕ) (bits : List Bool) {i : ℕ} (hi : i < bits.length) :
    fillBits a base bits (base+i) = bits[i] := by
  simp [fillBits,hi,List.getD]

theorem fillBits_frame (a : Assignment) (base : ℕ) (bits : List Bool) {r : ℕ}
    (h : r < base ∨ base+bits.length ≤ r) : fillBits a base bits r = a r := by
  have hn : ¬ (base ≤ r ∧ r < base+bits.length) := by omega
  simp [fillBits,hn]

theorem tierTestGates_extend (a : Assignment) (j n x y b : ℕ)
    (hx : ∀ k, tierAbove n x k < b) (hy : ∀ k, tierAbove n y k < b) :
    ∃ a' : Assignment, (∀ r, r < b ∨ b+4 ≤ r → a' r = a r) ∧
      (∀ g ∈ tierTestGates j x y n b,g.Holds a') := by
  let bits := tierFlagValues a j n x y
  let a' := fillBits a b bits
  have hl : bits.length=4 := rfl
  have hKeep (r : ℕ) (h : r < b ∨ b+4 ≤ r) : a' r = a r :=
    fillBits_frame a b bits (hl.symm ▸ h)
  have hB (i : ℕ) (hi : i < 4) : a' (b+i) = bits[i]'(by omega) :=
    fillBits_at a b bits (by omega)
  have hx' (k : ℕ) := hKeep _ (Or.inl (hx k))
  have hy' (k : ℕ) := hKeep _ (Or.inl (hy k))
  refine ⟨a',hKeep,?_⟩
  have h0 : a' b = (a (tierAbove n x (2^j-1)) || a (tierAbove n y (2^j-1))) := by
    simpa [bits,tierFlagValues] using hB 0 (by decide)
  have h1 : a' (b+1) = !a' b := by
    rw [h0]
    simpa [bits,tierFlagValues] using hB 1 (by decide)
  have h2 : a' (b+2) = (a (tierAbove n x (2^(j-1)-1)) || a (tierAbove n y (2^(j-1)-1))) := by
    simpa [bits,tierFlagValues] using hB 2 (by decide)
  have h3 : a' (b+3) = (a' (b+1) && a' (b+2)) := by
    rw [h1,h0,h2]
    simpa [bits,tierFlagValues] using hB 3 (by decide)
  by_cases h : j=0
  · simp only [tierTestGates,h,if_true,List.forall_mem_cons,List.not_mem_nil,false_implies,
      implies_true,and_true,Gate.Holds]
    subst j
    exact ⟨by rw [h0,hx',hy'],h1⟩
  · simp only [tierTestGates,h,if_false,List.forall_mem_cons,List.not_mem_nil,false_implies,
      implies_true,and_true,Gate.Holds]
    exact ⟨by rw [h0,hx',hy'],h1,by rw [h2,hx',hy'],h3⟩

def emissionControlValues (a : Assignment) (live writes src dst : ℕ) : List Bool :=
  let pick := if a writes then a src else a dst
  let cancel := !a src
  let insert := a writes && a dst
  let move := cancel && insert
  let reading := !a writes
  [pick,a live && pick,cancel,insert,move,a live && move,reading,reading || a dst]

theorem emissionControl_extend (a : Assignment) (b live writes src dst : ℕ)
    (hl : live < b) (hw : writes < b) (hs : src < b) (hd : dst < b) :
    ∃ a' : Assignment, (∀ r, r < b ∨ b+8 ≤ r → a' r = a r) ∧
      (∀ g ∈ emissionControl b live writes src dst,g.Holds a') := by
  let bits := emissionControlValues a live writes src dst
  let a' := fillBits a b bits
  have hLen : bits.length=8 := rfl
  have hKeep (r : ℕ) (h : r < b ∨ b+8 ≤ r) : a' r = a r :=
    fillBits_frame a b bits (hLen.symm ▸ h)
  have hB (i : ℕ) (hi : i < 8) : a' (b+i) = bits[i]'(by omega) :=
    fillBits_at a b bits (by omega)
  have hL := hKeep _ (Or.inl hl)
  have hW := hKeep _ (Or.inl hw)
  have hS := hKeep _ (Or.inl hs)
  have hD := hKeep _ (Or.inl hd)
  have o0 : a' b = (if a writes then a src else a dst) := by
    simpa [bits,emissionControlValues] using hB 0 (by decide)
  have o1 : a' (b+1) = (a live && (if a writes then a src else a dst)) :=
    hB 1 (by decide)
  have o2 : a' (b+2) = !a src := hB 2 (by decide)
  have o3 : a' (b+3) = (a writes && a dst) := hB 3 (by decide)
  have o4 : a' (b+4) = (!a src && (a writes && a dst)) := hB 4 (by decide)
  have o5 : a' (b+5) = (a live && (!a src && (a writes && a dst))) := hB 5 (by decide)
  have o6 : a' (b+6) = !a writes := hB 6 (by decide)
  have o7 : a' (b+7) = (!a writes || a dst) := hB 7 (by decide)
  refine ⟨a',hKeep,?_⟩
  simp only [emissionControl,List.forall_mem_cons,List.not_mem_nil,false_implies,implies_true,and_true,
    Gate.Holds,hL,hW,hS,hD,o0,o1,o2,o3,o4,o5,o6,o7]
  
theorem emissionMux_extend (a : Assignment) (b w writes : ℕ) (old value : ℕ→ℕ)
    (hw : writes < b+8) (ho : ∀ i < w,old i < b+8) (hv : ∀ i < w,value i < b+8) :
    ∃ a' : Assignment, (∀ r, r < b+8 ∨ b+8+w ≤ r → a' r = a r) ∧
      (∀ g ∈ emissionMux b w writes old value,g.Holds a') := by
  let bits := (List.range w).map (fun i => if a writes then a (old i) else a (value i))
  let a' := fillBits a (b+8) bits
  have hlen : bits.length=w := by simp [bits]
  have hKeep (r : ℕ) (h : r < b+8 ∨ b+8+w ≤ r) : a' r = a r :=
    fillBits_frame a (b+8) bits (hlen.symm ▸ h)
  refine ⟨a',hKeep,?_⟩
  intro g hg
  obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
  have hI := List.mem_range.mp hi
  change a' (b+8+i) = (if a' writes then a' (old i) else a' (value i))
  have hB : a' (b+8+i) = bits[i]'(by omega) := fillBits_at a (b+8) bits (by omega)
  rw [hKeep _ (.inl hw),hKeep _ (.inl (ho i hI)),hKeep _ (.inl (hv i hI)),hB]
  simp [bits]

end CNFEncComplexity.Robson

/- RobsonEmitBlock -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

structure EmitFlags where
  addr : ℕ
  value : ℕ
  old : ℕ

def EmitFlags.valid (u : EmitInput) (f : EmitFlags) (a : Assignment) : Prop :=
  GateSat a (widthCircuit f.addr u.width u.address) ∧
  GateSat a (widthCircuit f.value u.width u.value) ∧
  GateSat a (widthCircuit f.old u.width u.old)

def EmitInput.coreGates (u : EmitInput) (f : EmitFlags) (j z b : ℕ) : List Gate :=
  let source := tierTestOutput j b
  let dest := tierTestOutput j (b+4)
  tierTestGates j f.addr f.old u.width b ++ tierTestGates j f.addr f.value u.width (b+4) ++
  emissionControl (b+8) u.live u.writes source dest ++
  emissionMux (b+8) (2^j) u.writes (paddedKey u.width z u.old) (paddedKey u.width z u.value)

theorem EmitInput.coreGates_length (u : EmitInput) (f : EmitFlags) (j z b : ℕ) :
    (u.coreGates f j z b).length ≤ 17*2^j := by
  have hS := tierTestGates_length j f.addr f.old u.width b
  have hD := tierTestGates_length j f.addr f.value u.width (b+4)
  have hW := Nat.two_pow_pos j
  simp only [EmitInput.coreGates,List.length_append,emissionControl,emissionMux,
    List.length_cons,List.length_nil,List.length_map,List.length_range]
  omega

theorem EmitInput.coreGates_sound (u : EmitInput) (f : EmitFlags) (a : Assignment)
    (j z o b : ℕ) (hz : a z=false) (ho : a o=true) (hW : f.valid u a)
    (h : GateSat a (u.coreGates f j z b)) :
    [laneRecord a (2^j) 0 (emitFirstRow u (2^j) z o (b+8)),
     laneRecord a (2^j) 0 (emitSecondRow u (2^j) z o (b+8))] = emitTier j (u.read a) := by
  simp only [EmitInput.coreGates,GateSat.append] at h
  obtain ⟨⟨⟨hs,hd⟩,hc⟩,hm⟩ := h
  exact emitRows_exact a u j z o (b+8) (tierTestOutput j b) (tierTestOutput j (b+4)) hz ho
    (tierTestGates_exact a j f.addr f.old u.width b u.address u.old hW.1 hW.2.2 hs)
    (tierTestGates_exact a j f.addr f.value u.width (b+4) u.address u.value hW.1 hW.2.1 hd)
    hc hm

theorem tierTestGates_names (j n x y b : ℕ)
    (g : Gate) (hg : g ∈ tierTestGates j x y n b) (r : ℕ) (hr : r ∈ RobsonCNF.Gate.names g) :
    b ≤ r ∧ r < b+4 ∨ (∃ k,r=tierAbove n x k) ∨ ∃ k,r=tierAbove n y k := by
  by_cases hj : j=0
  · simp only [tierTestGates,hj,if_true,List.mem_cons,List.not_mem_nil,or_false] at hg
    rcases hg with rfl|rfl <;>
      simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hr
    · rcases hr with rfl|rfl|rfl
      · exact .inl ⟨by omega,by omega⟩
      · exact .inr (.inl ⟨_,rfl⟩)
      · exact .inr (.inr ⟨_,rfl⟩)
    · rcases hr with rfl|rfl <;> exact .inl ⟨by omega,by omega⟩
  · simp only [tierTestGates,hj,if_false,List.mem_cons,List.not_mem_nil,or_false] at hg
    rcases hg with rfl|rfl|rfl|rfl <;>
      simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hr
    · rcases hr with rfl|rfl|rfl
      · exact .inl ⟨by omega,by omega⟩
      · exact .inr (.inl ⟨_,rfl⟩)
      · exact .inr (.inr ⟨_,rfl⟩)
    · rcases hr with rfl|rfl <;> exact .inl ⟨by omega,by omega⟩
    · rcases hr with rfl|rfl|rfl
      · exact .inl ⟨by omega,by omega⟩
      · exact .inr (.inl ⟨_,rfl⟩)
      · exact .inr (.inr ⟨_,rfl⟩)
    · rcases hr with rfl|rfl|rfl <;> exact .inl ⟨by omega,by omega⟩

theorem tierTestGates_names_lt (j n x y b : ℕ)
    (hx : ∀ k,tierAbove n x k < b) (hy : ∀ k,tierAbove n y k < b) :
    ∀ g ∈ tierTestGates j x y n b, ∀ r ∈ RobsonCNF.Gate.names g, r < b+4 := by
  intro g hg r hr
  rcases tierTestGates_names j n x y b g hg r hr with hh|⟨k,rfl⟩|⟨k,rfl⟩
  · exact hh.2
  · exact (hx k).trans_le (by omega)
  · exact (hy k).trans_le (by omega)

theorem emissionControl_names_lt (b live writes src dst : ℕ)
    (hl : live < b) (hw : writes < b) (hs : src < b) (hd : dst < b) :
    ∀ g ∈ emissionControl b live writes src dst, ∀ r ∈ RobsonCNF.Gate.names g, r < b+8 := by
  intro g hg r hr
  simp only [emissionControl,List.mem_cons,List.not_mem_nil,or_false] at hg
  rcases hg with rfl|rfl|rfl|rfl|rfl|rfl|rfl|rfl <;>
    simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hr <;>
    omega

theorem emissionMux_names_lt (b w writes : ℕ) (old value : ℕ→ℕ)
    (hw : writes < b+8) (ho : ∀ i < w,old i < b+8) (hv : ∀ i < w,value i < b+8) :
    ∀ g ∈ emissionMux b w writes old value, ∀ r ∈ RobsonCNF.Gate.names g, r < b+8+w := by
  intro g hg r hr
  obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
  have hi' := List.mem_range.mp hi
  have h1 := ho i hi'
  have h2 := hv i hi'
  simp only [RobsonCNF.Gate.names,List.mem_cons,List.not_mem_nil,or_false] at hr
  omega

private theorem preserves_prefix_sat {a a' : Assignment} {gates : List Gate} {n : ℕ}
    (h : GateSat a gates) (hn : ∀ g ∈ gates, ∀ r ∈ RobsonCNF.Gate.names g, r < n)
    (ha : ∀ r < n, a' r = a r) : GateSat a' gates := by
  intro g hg
  exact (g.holds_congr a' a (fun r hr => ha _ (hn g hg r hr))).2 (h g hg)

theorem EmitInput.coreGates_extend (u : EmitInput) (f : EmitFlags) (a : Assignment) (j z b : ℕ)
    (hLive : u.live < b) (hWrites : u.writes < b) (hZ : z < b)
    (hOld : ∀ i < u.width,u.old i < b) (hValue : ∀ i < u.width,u.value i < b)
    (hAddr : ∀ k,tierAbove u.width f.addr k < b)
    (hVO : ∀ k,tierAbove u.width f.value k < b)
    (hOO : ∀ k,tierAbove u.width f.old k < b) :
    ∃ beta, Keeps a beta b (b+16+2^j) ∧ GateSat beta (u.coreGates f j z b) := by
  let w := 2^j
  let s := tierTestOutput j b
  let d := tierTestOutput j (b+4)
  have hS : s < b+8 := by unfold s tierTestOutput; split <;> omega
  have hD : d < b+8 := by unfold d tierTestOutput; split <;> omega
  have hPad (k : ℕ→ℕ) (hk : ∀ i < u.width,k i < b) : ∀ i < w, paddedKey u.width z k i < b+16 := by
    intro i hi
    unfold paddedKey
    split
    · exact (hk i ‹i < u.width›).trans_le (by omega)
    · omega
  have hLive' : u.live < b+8 := by omega
  have hWrites' : u.writes < b+8 := by omega
  have hWrites'' : u.writes < b+8+8 := by omega
  have hAddress' (k : ℕ) : tierAbove u.width f.addr k < b+4 := (hAddr k).trans_le (by omega)
  have hVO' (k : ℕ) : tierAbove u.width f.value k < b+4 := (hVO k).trans_le (by omega)
  obtain ⟨a₁,h1,g1⟩ := tierTestGates_extend a j u.width f.addr f.old b hAddr hOO
  obtain ⟨a₂,h2,g2⟩ := tierTestGates_extend a₁ j u.width f.addr f.value (b+4) hAddress' hVO'
  obtain ⟨a₃,h3,g3⟩ := emissionControl_extend a₂ (b+8) u.live u.writes s d hLive' hWrites' hS hD
  obtain ⟨a₄,h4,g4⟩ := emissionMux_extend a₃ (b+8) w u.writes
    (paddedKey u.width z u.old) (paddedKey u.width z u.value)
    hWrites'' (hPad _ hOld) (hPad _ hValue)
  have hkeep : Keeps a a₄ b (b+16+w) := by
    intro i hi
    rcases hi with hi|hi
    · rw [h4 i (.inl (by omega)),h3 i (.inl (by omega)),h2 i (.inl (by omega)),h1 i (.inl hi)]
    · have h16 : b+16 ≤ i := (Nat.le_add_right _ w).trans hi
      have hu : b+8+8+w ≤ i := by
        rw [show b+8+8+w=b+16+w by omega]
        exact hi
      rw [h4 i (.inr hu),h3 i (.inr (by omega)),h2 i (.inr (by omega)),h1 i (.inr (by omega))]
  have hg2 := preserves_prefix_sat g2
    (tierTestGates_names_lt _ _ _ _ _ hAddress' hVO')
    (fun r hr => h3 r (.inl (by omega)))
  have hgg1 := preserves_prefix_sat g1
    (tierTestGates_names_lt _ _ _ _ _ hAddr hOO)
    (fun r hr => (h3 r (.inl (by omega))).trans (h2 r (.inl hr)))
  have hf1 := preserves_prefix_sat hgg1
    (tierTestGates_names_lt _ _ _ _ _ hAddr hOO) (fun r hr => h4 r (.inl (by omega)))
  have hf2 := preserves_prefix_sat hg2
    (tierTestGates_names_lt _ _ _ _ _ hAddress' hVO') (fun r hr => h4 r (.inl (by omega)))
  have hf3 := preserves_prefix_sat g3
    (emissionControl_names_lt _ _ _ _ _ hLive' hWrites' hS hD) (fun r hr => h4 r (.inl hr))
  refine ⟨a₄,hkeep,?_⟩
  simp only [EmitInput.coreGates,GateSat.append]
  exact ⟨⟨⟨hf1,hf2⟩,hf3⟩,g4⟩

end CNFEncComplexity.Robson

/- RobsonEmitLayout -/

namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF

def emitSlotSpan (t : ℕ) : ℕ := layoutHorizon t*(layoutHeight t+1)

def emitSlotIndex (t : ℕ) (s : ℕ×ℕ) : ℕ := s.1*(layoutHeight t+1)+s.2

theorem emitSlotIndex_bound {t : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t) :
    emitSlotIndex t s < emitSlotSpan t := by
  rcases s with ⟨a,j⟩
  have ⟨ha,hj,_⟩ := layout_mem.mp hs
  have hMul := Nat.mul_le_mul_right (layoutHeight t+1) (Nat.succ_le_of_lt ha)
  rw [Nat.succ_eq_add_one,Nat.add_mul,Nat.one_mul] at hMul
  unfold emitSlotIndex emitSlotSpan
  dsimp only
  omega

private theorem linearIndex_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 hPos : 0 < d := by omega
  have h₁ : (a*d+i)/d = a := by
    rw [Nat.mul_comm a d,Nat.mul_add_div hPos,Nat.div_eq_of_lt hi,Nat.add_zero]
  have h₂ : (b*d+j)/d = b := by
    rw [Nat.mul_comm b d,Nat.mul_add_div hPos,Nat.div_eq_of_lt hj,Nat.add_zero]
  have hA := h₁.symm.trans ((congrArg (fun n => n/d) h).trans h₂)
  subst b
  exact ⟨rfl,by omega⟩

theorem emitSlotIndex_injective {t : ℕ} {s u : ℕ×ℕ}
    (hs : s ∈ layoutSlots t) (hu : u ∈ layoutSlots t)
    (h : emitSlotIndex t s = emitSlotIndex t u) : s=u := by
  rcases s with ⟨a,j⟩
  rcases u with ⟨c,k⟩
  have ⟨hA,hB⟩ := linearIndex_injective
    (Nat.lt_succ_of_le (layout_mem.mp hs).2.1) (Nat.lt_succ_of_le (layout_mem.mp hu).2.1) h
  exact Prod.ext hA hB

def emitInputs (base n t : ℕ) (s : ℕ×ℕ) (row : ℕ) : EmitInput :=
  let b := trieLevel t
  ⟨normalizeWidth b s,port n t s (3+5*row) 0,port n t s (3+5*row+1) 0,
    (normalizeSlotWires base n t b s row 0).label,
    (normalizeSlotWires base n t b s row 1).label,
    (normalizeSlotWires base n t b s row 2).label⟩

theorem emitInputs_eq (a : Assignment) (base n t : ℕ) (s : ℕ×ℕ) (row : ℕ) :
    (emitInputs base n t s row).read a = slotCompactMemory a base n t (trieLevel t) s row := rfl

def emitFlagStride (t : ℕ) : ℕ := layoutHorizon t+2

def emitFlagIndex (t : ℕ) (s : ℕ×ℕ) (r f : ℕ) : ℕ :=
  9*emitSlotIndex t s+3*r+f

def emitFlagBase (base t : ℕ) (s : ℕ×ℕ) (r f : ℕ) : ℕ :=
  base+emitFlagIndex t s r f*emitFlagStride t

def emitFlagTop (base t : ℕ) : ℕ :=
  base+9*emitSlotSpan t*emitFlagStride t

def emitFlags (base t : ℕ) (s : ℕ×ℕ) (r : ℕ) : EmitFlags :=
  ⟨emitFlagBase base t s r 0,emitFlagBase base t s r 1,emitFlagBase base t s r 2⟩

theorem emitFlagWidth_bound {t : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t) :
    normalizeWidth (trieLevel t) s+1 ≤ emitFlagStride t := by
  rcases s with ⟨a,j⟩
  have hW : 2^j ≤ layoutHorizon t := Nat.pow_le_pow_right (by decide) (layout_mem.mp hs).2.1
  have hh := min_le_left (2^j) (2^trieLevel t)
  unfold normalizeWidth emitFlagStride
  dsimp only
  omega

theorem emitFlagBlock_bounds {base t r f : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t)
    (hr : r < 3) (hf : f < 3) :
    base ≤ emitFlagBase base t s r f ∧
      emitFlagBase base t s r f+emitFlagStride t ≤ emitFlagTop base t := by
  have hi := emitSlotIndex_bound hs
  have hI : emitFlagIndex t s r f+1 ≤ 9*emitSlotSpan t := by unfold emitFlagIndex; omega
  have h := Nat.mul_le_mul_right (emitFlagStride t) hI
  rw [Nat.add_mul,Nat.one_mul] at h
  unfold emitFlagBase emitFlagTop
  omega

theorem emitFlagIndex_injective {t r r' f f' : ℕ} {s u : ℕ×ℕ}
    (hs : s ∈ layoutSlots t) (hu : u ∈ layoutSlots t) (hr : r < 3) (hr' : r'<3) (hf : f < 3) (hf' : f'<3)
    (h : emitFlagIndex t s r f = emitFlagIndex t u r' f') :
    s=u ∧ r=r' ∧ f=f' := by
  have h1 : 3*r+f < 9 := by omega
  have h2 : 3*r'+f'<9 := by omega
  have hI : emitSlotIndex t s*9+(3*r+f)=emitSlotIndex t u*9+(3*r'+f') := by
    unfold emitFlagIndex at h
    omega
  obtain ⟨hi,hj⟩ := linearIndex_injective h1 h2 hI
  have ht : r*3+f=r'*3+f' := by omega
  exact ⟨emitSlotIndex_injective hs hu hi,linearIndex_injective hf hf' ht⟩

def emitWidthGates (base region n t : ℕ) (s : ℕ×ℕ) (r f : ℕ) : List Gate :=
  widthCircuit (emitFlagBase region t s r f) (normalizeWidth (trieLevel t) s)
    (normalizeSlotWires base n t (trieLevel t) s r f).label

def emitWidthLayoutGates (base region n t : ℕ) : List Gate :=
  (layoutSlots t).flatMap fun s =>
    (List.range 3).flatMap fun r =>
      (List.range 3).flatMap (emitWidthGates base region n t s r)

theorem emitWidthGates_length (base region n t : ℕ) (s : ℕ×ℕ) (r f : ℕ) :
    (emitWidthGates base region n t s r f).length ≤ 3*2^s.2 := by
  have hp := Nat.two_pow_pos s.2
  have hMin := min_le_left (2^s.2) (2^trieLevel t)
  simp [emitWidthGates,length_widthCircuit,normalizeWidth]
  omega

def emitLevels (t : ℕ) : ℕ := (trieWidth t+1).size+1

def emitBlockStride (t : ℕ) : ℕ := 2*(layoutHorizon t+1)+17

def emitBlockIndex (t j : ℕ) (s : ℕ×ℕ) (r : ℕ) : ℕ :=
  3*(j*emitSlotSpan t+emitSlotIndex t s)+r

def emitBlockBase (base t j : ℕ) (s : ℕ×ℕ) (r : ℕ) : ℕ :=
  emitFlagTop base t+emitBlockIndex t j s r*emitBlockStride t

def emitBlockTop (base t : ℕ) : ℕ :=
  emitFlagTop base t+3*(emitLevels t*emitSlotSpan t)*emitBlockStride t

theorem emitBlockWidth_bound {t j : ℕ} (hj : j < emitLevels t) :
    16+2^j ≤ emitBlockStride t := by
  let b := trieWidth t+1
  have hm : b ≤ layoutHorizon t+1 := Nat.succ_le_succ (trieWidth_in_horizon t)
  have hx : 2^b.size ≤ 2*b+1 := pow2_size_le b
  have hk : j ≤ b.size := Nat.le_of_lt_succ hj
  have h := Nat.pow_le_pow_right (by decide : 0<(2:ℕ)) hk
  unfold emitBlockStride
  omega

theorem emitBlockIndex_bound {t j r : ℕ} {s : ℕ×ℕ} (hs : s ∈ layoutSlots t) (hj : j < emitLevels t) (hr : r < 3) :
    emitBlockIndex t j s r < 3*(emitLevels t*emitSlotSpan t) := by
  have hI := emitSlotIndex_bound hs
  have h := Nat.mul_le_mul_right (emitSlotSpan t) (Nat.succ_le_of_lt hj)
  rw [Nat.succ_eq_add_one,Nat.add_mul,Nat.one_mul] at h
  unfold emitBlockIndex
  omega

theorem emitBlockIndex_injective {t j j' r r' : ℕ} {s u : ℕ×ℕ}
    (hs : s ∈ layoutSlots t) (hu : u ∈ layoutSlots t) (hr : r < 3) (hr' : r'<3)
    (h : emitBlockIndex t j s r = emitBlockIndex t j' u r') : j=j' ∧ s=u ∧ r=r' := by
  have hp : (j*emitSlotSpan t+emitSlotIndex t s)*3+r =
      (j'*emitSlotSpan t+emitSlotIndex t u)*3+r' := by
    simp only [Nat.mul_comm _ 3]
    exact h
  obtain ⟨hIJ,hR⟩ := linearIndex_injective hr hr' hp
  obtain ⟨hJ,hS⟩ := linearIndex_injective (emitSlotIndex_bound hs) (emitSlotIndex_bound hu) hIJ
  exact ⟨hJ,emitSlotIndex_injective hs hu hS,hR⟩

def emitOne (base region n t j z : ℕ) (s : ℕ×ℕ) (r : ℕ) : List Gate :=
  (emitInputs base n t s r).coreGates (emitFlags region t s r) j z (emitBlockBase region t j s r)

def emitTierGateList (base region n t j z : ℕ) (slots : List (ℕ×ℕ)) : List Gate :=
  slots.flatMap fun s => (List.range 3).flatMap (emitOne base region n t j z s)

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