Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.GeneralCircuit.ToSAT.Machine.Normalizer.RejectBounds

Definition
PricingWithTips3DM_bbf6bc57f7678f916a5e40b5

by qmaai2907271020 · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorypricing-with-tipsthree-dimensional-matching

A private, kernel-checked dependency module used by the formal NP-hardness proof for three-dimensional matching and Theorems 4.1 and 4.2 of arXiv:2507.10872.

Definition code
import Definitions.Def_PricingWithTips3DM_59253dea2fb8d974bdec5e81
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Guarded circuit normalizer: malformed and invalid route bounds

Local parser bounds are kept separate from total semantics.  Later sections
combine these linear/quadratic route estimates under the public sextic budget.
-/

namespace CLRS.Chapter34.Turing.GeneralCircuitToSAT.Normalizer

open Computability StateTransition

/-- Linear storage envelope for a malformed unary field and its eventual
cleanup.  The coefficient eight pays for the two staged copies made by an
output operand tick. -/
def malformedFieldBound (input : List CircuitSym)
    (output rows : List NormalizedCircuitSym)
    (inputCount gateCount operand saved outputIndex : Nat) : Nat :=
  8 * input.length + output.length + rows.length + inputCount + gateCount +
    operand + saved + outputIndex + 32

/-- A malformed first unary field rejects within the shared linear storage
envelope. -/
theorem malformedInputCount_rejectsIn (state : State)
    (input : List CircuitSym) (output rows : List NormalizedCircuitSym)
    (inputCount gateCount operand saved outputIndex : Nat)
    (hdecode : decNat input = none) :
    RejectsIn
      (cfg (some .inputCount) state input output rows inputCount gateCount
        operand saved outputIndex)
      (malformedFieldBound input output rows inputCount gateCount operand saved
        outputIndex) := by
  induction input generalizing state inputCount with
  | nil =>
      have hreject := rejectsInAfterCleanupStep
        { state with inputBuffer := none } [] output rows inputCount gateCount
        operand saved outputIndex
        (input_count_empty_step state output rows inputCount gateCount operand
          saved outputIndex)
      exact RejectsIn.mono hreject (by
        simp [clearAndEmitInvalidSteps, malformedFieldBound]
        omega)
  | cons symbol input ih =>
      cases symbol with
      | argMark =>
          simp only [decNat] at hdecode
          have htail : decNat input = none := by
            cases h : decNat input <;> simp_all
          have hreject := ih { state with inputBuffer := some .argMark }
            (inputCount + 1) htail
          have hfull := RejectsIn.before_step
            (input_count_arg_step state input output rows inputCount gateCount
              operand saved outputIndex) hreject
          exact RejectsIn.mono hfull (by
            simp [malformedFieldBound]
            omega)
      | endMark => simp [decNat] at hdecode
      | inputMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .inputMark } input output rows
            inputCount gateCount operand saved outputIndex
            (input_count_bad_step state .inputMark (by decide) (by decide) input
              output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)
      | constFalseMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .constFalseMark } input output rows
            inputCount gateCount operand saved outputIndex
            (input_count_bad_step state .constFalseMark (by decide) (by decide)
              input output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)
      | constTrueMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .constTrueMark } input output rows
            inputCount gateCount operand saved outputIndex
            (input_count_bad_step state .constTrueMark (by decide) (by decide)
              input output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)
      | notMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .notMark } input output rows
            inputCount gateCount operand saved outputIndex
            (input_count_bad_step state .notMark (by decide) (by decide) input
              output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)
      | andMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .andMark } input output rows
            inputCount gateCount operand saved outputIndex
            (input_count_bad_step state .andMark (by decide) (by decide) input
              output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)
      | orMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .orMark } input output rows
            inputCount gateCount operand saved outputIndex
            (input_count_bad_step state .orMark (by decide) (by decide) input
              output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)
      | outputMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .outputMark } input output rows
            inputCount gateCount operand saved outputIndex
            (input_count_bad_step state .outputMark (by decide) (by decide) input
              output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)

/-- Every malformed gate/output operand rejects within the same linear
storage envelope. -/
theorem malformedOperand_rejectsIn (state : State) (ret : Return)
    (input : List CircuitSym) (output rows : List NormalizedCircuitSym)
    (inputCount gateCount operand saved outputIndex : Nat)
    (hdecode : decNat input = none) :
    RejectsIn
      (cfg (some (.parseOperand ret)) state input output rows inputCount
        gateCount operand saved outputIndex)
      (malformedFieldBound input output rows inputCount gateCount operand saved
        outputIndex) := by
  induction input generalizing state operand rows outputIndex with
  | nil =>
      have hreject := rejectsInAfterCleanupStep
        { state with inputBuffer := none } [] output rows inputCount gateCount
        operand saved outputIndex
        (operand_empty_step state ret output rows inputCount gateCount operand
          saved outputIndex)
      exact RejectsIn.mono hreject (by
        simp [clearAndEmitInvalidSteps, malformedFieldBound]
        omega)
  | cons symbol input ih =>
      cases symbol with
      | argMark =>
          simp only [decNat] at hdecode
          have htail : decNat input = none := by
            cases h : decNat input <;> simp_all
          let nextRows := operandTickRows ret rows
          let nextOutputIndex := operandTickOutputIndex ret outputIndex
          have hreject := ih
            (state := { state with inputBuffer := some .argMark })
            (operand := operand + 1) (rows := nextRows)
            (outputIndex := nextOutputIndex) htail
          have hfirst := operand_arg_step state ret input output rows inputCount
            gateCount operand saved outputIndex
          have hfirst' :
              step (cfg (some (.parseOperand ret)) state (.argMark :: input)
                output rows inputCount gateCount operand saved outputIndex) =
              some (cfg (some (.parseOperand ret))
                { state with inputBuffer := some .argMark } input output nextRows
                inputCount gateCount (operand + 1) saved nextOutputIndex) := by
            cases ret <;>
              simpa [nextRows, nextOutputIndex, operandTickRows,
                operandTickOutputIndex] using hfirst
          have hfull := RejectsIn.before_step hfirst' hreject
          exact RejectsIn.mono hfull (by
            cases ret <;> simp [malformedFieldBound, nextRows, nextOutputIndex,
              operandTickRows, operandTickOutputIndex] <;> omega)
      | endMark => simp [decNat] at hdecode
      | inputMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .inputMark } input output rows
            inputCount gateCount operand saved outputIndex
            (operand_bad_step state ret .inputMark (by decide) (by decide) input
              output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)
      | constFalseMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .constFalseMark } input output rows
            inputCount gateCount operand saved outputIndex
            (operand_bad_step state ret .constFalseMark (by decide) (by decide)
              input output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)
      | constTrueMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .constTrueMark } input output rows
            inputCount gateCount operand saved outputIndex
            (operand_bad_step state ret .constTrueMark (by decide) (by decide)
              input output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)
      | notMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .notMark } input output rows
            inputCount gateCount operand saved outputIndex
            (operand_bad_step state ret .notMark (by decide) (by decide) input
              output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)
      | andMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .andMark } input output rows
            inputCount gateCount operand saved outputIndex
            (operand_bad_step state ret .andMark (by decide) (by decide) input
              output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)
      | orMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .orMark } input output rows
            inputCount gateCount operand saved outputIndex
            (operand_bad_step state ret .orMark (by decide) (by decide) input
              output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)
      | outputMark =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := some .outputMark } input output rows
            inputCount gateCount operand saved outputIndex
            (operand_bad_step state ret .outputMark (by decide) (by decide) input
              output rows inputCount gateCount operand saved outputIndex)
          exact RejectsIn.mono hreject (by
            simp [clearAndEmitInvalidSteps, malformedFieldBound]
            omega)

/-- Exact budget of the shared failed strict-bound comparison. -/
def firstInvalidRejectBound (ret : Return)
    (bound extra inputCount gateCount outputIndex : Nat)
    (input : List CircuitSym) (output rows : List NormalizedCircuitSym) : Nat :=
  clearAndEmitInvalidSteps input output rows
      (withBound ret 0 inputCount gateCount).1
      (withBound ret 0 inputCount gateCount).2 extra.pred bound outputIndex +
    1 + bound

/-- A parsed operand at least its selected bound rejects within the named
comparison-and-cleanup budget. -/
theorem firstInvalidGate_rejectsIn (state : State) (ret : Return)
    (bound extra inputCount gateCount outputIndex : Nat)
    (input : List CircuitSym) (output rows : List NormalizedCircuitSym) :
    RejectsIn
      (cfg (some (.compareOperand ret)) state input output rows
        (withBound ret bound inputCount gateCount).1
        (withBound ret bound inputCount gateCount).2
        (bound + extra) 0 outputIndex)
      (firstInvalidRejectBound ret bound extra inputCount gateCount outputIndex
        input output rows) := by
  rcases compareBoundPrefix_phase state ret bound extra 0 inputCount gateCount
      outputIndex input output rows with ⟨s₁, h₁⟩
  have h₁' : (flip Option.bind step)^[bound]
      (some (cfg (some (.compareOperand ret)) state input output rows
        (withBound ret bound inputCount gateCount).1
        (withBound ret bound inputCount gateCount).2
        (bound + extra) 0 outputIndex)) =
      some (cfg (some (.compareOperand ret)) s₁ input output rows
        (withBound ret 0 inputCount gateCount).1
        (withBound ret 0 inputCount gateCount).2
        extra bound outputIndex) := by
    simpa using h₁
  have hstep := boundZero_reject_step s₁ ret extra inputCount gateCount bound
    outputIndex input output rows
  have hcleanup := rejectsInAfterCleanupStep
    { s₁ with counterPresent := false } input output rows
    (withBound ret 0 inputCount gateCount).1
    (withBound ret 0 inputCount gateCount).2 extra.pred bound outputIndex hstep
  have hfull := RejectsIn.before_steps bound h₁' hcleanup
  simpa [firstInvalidRejectBound, Nat.add_assoc, Nat.add_comm,
    Nat.add_left_comm] using hfull

/-- Budget for parsing one canonical but out-of-range operand and rejecting it. -/
def invalidOperandRejectBound (ret : Return)
    (bound extra inputCount gateCount outputIndex : Nat)
    (input : List CircuitSym) (output rows : List NormalizedCircuitSym) : Nat :=
  firstInvalidRejectBound ret bound extra inputCount gateCount
      (operandOutputIndex ret (bound + extra) outputIndex) input output
      (operandRows ret (bound + extra) rows) +
    (bound + extra + 1)

theorem invalidOperand_rejectsIn (state : State) (ret : Return)
    (hret : ret ≠ .outputGate) (bound extra inputCount gateCount outputIndex : Nat)
    (input : List CircuitSym) (output rows : List NormalizedCircuitSym) :
    RejectsIn
      (cfg (some (.parseOperand ret)) state
        (encNat (bound + extra) ++ input) output rows
        (withBound ret bound inputCount gateCount).1
        (withBound ret bound inputCount gateCount).2 0 0 outputIndex)
      (invalidOperandRejectBound ret bound extra inputCount gateCount outputIndex
        input output rows) := by
  rcases operand_phase state ret (bound + extra) 0 input output rows
      (withBound ret bound inputCount gateCount).1
      (withBound ret bound inputCount gateCount).2 0 outputIndex with
    ⟨s₁, hparse⟩
  have hparse' : (flip Option.bind step)^[bound + extra + 1]
      (some (cfg (some (.parseOperand ret)) state
        (encNat (bound + extra) ++ input) output rows
        (withBound ret bound inputCount gateCount).1
        (withBound ret bound inputCount gateCount).2 0 0 outputIndex)) =
      some (cfg (some (.compareOperand ret)) s₁ input output
        (operandRows ret (bound + extra) rows)
        (withBound ret bound inputCount gateCount).1
        (withBound ret bound inputCount gateCount).2
        (bound + extra) 0
        (operandOutputIndex ret (bound + extra) outputIndex)) := by
    have hlabel : afterOperandLabel ret = .compareOperand ret := by
      cases ret <;> simp_all [afterOperandLabel]
    simpa [hlabel] using hparse
  have hreject := firstInvalidGate_rejectsIn s₁ ret bound extra inputCount
    gateCount (operandOutputIndex ret (bound + extra) outputIndex) input output
    (operandRows ret (bound + extra) rows)
  simpa [invalidOperandRejectBound] using
    RejectsIn.before_steps (bound + extra + 1) hparse' hreject

/-- Tail garbage is rejected in one transition plus exact cleanup. -/
theorem trailingGarbage_rejectsIn (state : State) (head : CircuitSym)
    (input : List CircuitSym) (output rows : List NormalizedCircuitSym)
    (inputCount gateCount operand saved outputIndex : Nat) :
    RejectsIn
      (cfg (some .checkTrailing) state (head :: input) output rows inputCount
        gateCount operand saved outputIndex)
      (clearAndEmitInvalidSteps input output rows inputCount gateCount operand
        saved outputIndex + 1) := by
  exact rejectsInAfterCleanupStep { state with inputBuffer := some head } input
    output rows inputCount gateCount operand saved outputIndex
    (check_trailing_nonempty_step state head input output rows inputCount
      gateCount operand saved outputIndex)

/-- Generous local envelope for rejecting one canonical invalid gate. -/
def gateLocalRejectBound (capacity : Nat)
    (input : List CircuitSym) (output rows : List NormalizedCircuitSym)
    (inputCount gateIndex : Nat) : Nat :=
  4096 * (capacity + input.length + output.length + rows.length + inputCount +
    gateIndex + 1) ^ 2 + 4096

theorem linear_le_gateLocal (capacity : Nat)
    (input : List CircuitSym) (output rows : List NormalizedCircuitSym)
    (inputCount gateIndex cost : Nat)
    (hcost : cost ≤ 64 * (capacity + input.length + output.length +
      rows.length + inputCount + gateIndex + 1)) :
    cost ≤ gateLocalRejectBound capacity input output rows inputCount
      gateIndex := by
  exact hcost.trans (by
    simp only [gateLocalRejectBound]
    nlinarith)

/-- A canonical gate violating its range/dependency condition rejects within a
quadratic envelope in the available raw capacity and live storage. -/
theorem invalidGate_rejectsIn (state : State) (gate : CircuitGate)
    (gateIndex inputCount capacity : Nat)
    (hinvalid : ¬ gate.ValidAt inputCount gateIndex)
    (input : List CircuitSym) (output rows : List NormalizedCircuitSym)
    (hcapacity : (encodeCircuitGate gate ++ input).length ≤ capacity) :
    RejectsIn
      (cfg (some .gates) state (encodeCircuitGate gate ++ input) output rows
        inputCount gateIndex 0 0 0)
      (gateLocalRejectBound capacity input output rows inputCount gateIndex) := by
  cases gate with
  | input inputIndex =>
      simp only [CircuitGate.ValidAt] at hinvalid
      have hle : inputCount ≤ inputIndex := Nat.not_lt.mp hinvalid
      obtain ⟨extra, hindex⟩ := Nat.exists_eq_add_of_le hle
      rcases gatePrefix_phase state .input (encNat inputIndex ++ input) output
          rows inputCount gateIndex with ⟨s₁, hprefix⟩
      have hreject := invalidOperand_rejectsIn s₁ .inputGate (by decide)
        inputCount extra 0 gateIndex 0 input output
        (afterRowPrefixRows .input
          (.fieldEnd ::
            (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
      have hfull := RejectsIn.before_steps (2 * gateIndex + 3)
        (by simpa [encodeCircuitGate, rawGateTag, afterRowPrefixLabel,
          afterRowPrefixGateCount, hindex] using hprefix) hreject
      have hfull' : RejectsIn
          (cfg (some .gates) state
            (encodeCircuitGate (.input inputIndex) ++ input) output rows
            inputCount gateIndex 0 0 0)
          (invalidOperandRejectBound .inputGate inputCount extra 0 gateIndex 0
            input output
            (afterRowPrefixRows .input
              (.fieldEnd ::
                (List.replicate gateIndex .tick ++ .gateRowMark :: rows))) +
            (2 * gateIndex + 3)) := by
        simpa [encodeCircuitGate, hindex] using hfull
      exact RejectsIn.mono hfull' (linear_le_gateLocal capacity input output
        rows inputCount gateIndex _ (by
        simp [invalidOperandRejectBound,
          firstInvalidRejectBound, clearAndEmitInvalidSteps, operandRows,
          operandOutputIndex, afterRowPrefixRows, withBound, encodeCircuitGate,
          encNat, hindex] at hcapacity ⊢
        omega))
  | const value => simp [CircuitGate.ValidAt] at hinvalid
  | not source =>
      simp only [CircuitGate.ValidAt] at hinvalid
      have hle : gateIndex ≤ source := Nat.not_lt.mp hinvalid
      obtain ⟨extra, hsource⟩ := Nat.exists_eq_add_of_le hle
      rcases gatePrefix_phase state .not (encNat source ++ input) output rows
          inputCount gateIndex with ⟨s₁, hprefix⟩
      have hreject := invalidOperand_rejectsIn s₁ .notGate (by decide)
        gateIndex extra inputCount 0 0 input output
        (afterRowPrefixRows .not
          (.fieldEnd ::
            (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
      have hfull := RejectsIn.before_steps (2 * gateIndex + 3)
        (by simpa [encodeCircuitGate, rawGateTag, afterRowPrefixLabel,
          afterRowPrefixGateCount, withBound, hsource] using hprefix) hreject
      have hfull' : RejectsIn
          (cfg (some .gates) state (encodeCircuitGate (.not source) ++ input)
            output rows inputCount gateIndex 0 0 0)
          (invalidOperandRejectBound .notGate gateIndex extra inputCount 0 0
            input output
            (afterRowPrefixRows .not
              (.fieldEnd ::
                (List.replicate gateIndex .tick ++ .gateRowMark :: rows))) +
            (2 * gateIndex + 3)) := by
        simpa [encodeCircuitGate, hsource] using hfull
      exact RejectsIn.mono hfull' (linear_le_gateLocal capacity input output
        rows inputCount gateIndex _ (by
        simp [invalidOperandRejectBound,
          firstInvalidRejectBound, clearAndEmitInvalidSteps, operandRows,
          operandOutputIndex, afterRowPrefixRows, withBound, encodeCircuitGate,
          encNat, hsource] at hcapacity ⊢
        omega))
  | and left right =>
      simp only [CircuitGate.ValidAt, not_and_or] at hinvalid
      rcases gatePrefix_phase state .and
          (encNat left ++ encNat right ++ input) output rows inputCount gateIndex
        with ⟨s₁, hprefix⟩
      rcases hinvalid with hleft | hright
      · have hle : gateIndex ≤ left := Nat.not_lt.mp hleft
        obtain ⟨extra, hleftEq⟩ := Nat.exists_eq_add_of_le hle
        have hreject := invalidOperand_rejectsIn s₁ .andLeft (by decide)
          gateIndex extra inputCount 0 0 (encNat right ++ input) output
          (afterRowPrefixRows .and
            (.fieldEnd ::
              (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
        have hfull := RejectsIn.before_steps (2 * gateIndex + 3)
          (by simpa [encodeCircuitGate, rawGateTag, afterRowPrefixLabel,
            afterRowPrefixGateCount, withBound, hleftEq, List.append_assoc]
            using hprefix)
          hreject
        have hfull' : RejectsIn
            (cfg (some .gates) state
              (encodeCircuitGate (.and left right) ++ input) output rows
              inputCount gateIndex 0 0 0)
            (invalidOperandRejectBound .andLeft gateIndex extra inputCount 0 0
              (encNat right ++ input) output
              (afterRowPrefixRows .and
                (.fieldEnd ::
                  (List.replicate gateIndex .tick ++ .gateRowMark :: rows))) +
              (2 * gateIndex + 3)) := by
          simpa [encodeCircuitGate, hleftEq, List.append_assoc] using hfull
        exact RejectsIn.mono hfull' (linear_le_gateLocal capacity input output
          rows inputCount gateIndex _ (by
          simp [invalidOperandRejectBound,
            firstInvalidRejectBound, clearAndEmitInvalidSteps, operandRows,
            operandOutputIndex, afterRowPrefixRows, withBound,
            encodeCircuitGate, encNat, hleftEq] at hcapacity ⊢
          omega))
      · by_cases hleftValid : left < gateIndex
        · obtain ⟨leftSlack, hleftEq⟩ := Nat.exists_eq_add_of_lt hleftValid
          have hle : gateIndex ≤ right := Nat.not_lt.mp hright
          obtain ⟨rightExtra, hrightEq⟩ := Nat.exists_eq_add_of_le hle
          rcases boundedOperand_phase s₁ .andLeft (by decide) left leftSlack
              inputCount 0 0 (encNat right ++ input) output
              (afterRowPrefixRows .and
                (.fieldEnd ::
                  (List.replicate gateIndex .tick ++ .gateRowMark :: rows))) with
            ⟨s₂, hleftRun⟩
          have hreject := invalidOperand_rejectsIn s₂ .andRight (by decide)
            gateIndex rightExtra inputCount 0 0 input output
            (afterBoundRows .andLeft
              (operandRows .andLeft left
                (afterRowPrefixRows .and
                  (.fieldEnd ::
                    (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))))
          have hbound : left + leftSlack + 1 = gateIndex := hleftEq.symm
          have hprefix' := hprefix
          simp [rawGateTag, afterRowPrefixLabel, afterRowPrefixGateCount,
            List.append_assoc] at hprefix'
          have hleftRun' : (flip Option.bind step)^[3 * left + 4]
              (some (cfg (some (.parseOperand .andLeft)) s₁
                (encNat left ++ (encNat right ++ input)) output
                (afterRowPrefixRows .and
                  (.fieldEnd ::
                    (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
                inputCount gateIndex 0 0 0)) =
              some (cfg (some (.parseOperand .andRight)) s₂
                (encNat right ++ input) output
                (afterBoundRows .andLeft
                  (operandRows .andLeft left
                    (afterRowPrefixRows .and
                      (.fieldEnd ::
                        (List.replicate gateIndex .tick ++
                          .gateRowMark :: rows)))))
                inputCount gateIndex 0 0 0) := by
            simpa [afterBoundLabel, afterBoundGateCount, operandOutputIndex,
              withBound, hbound] using hleftRun
          have hreject' : RejectsIn
              (cfg (some (.parseOperand .andRight)) s₂
                (encNat right ++ input) output
                (afterBoundRows .andLeft
                  (operandRows .andLeft left
                    (afterRowPrefixRows .and
                      (.fieldEnd ::
                        (List.replicate gateIndex .tick ++
                          .gateRowMark :: rows)))))
                inputCount gateIndex 0 0 0)
              (invalidOperandRejectBound .andRight gateIndex rightExtra
                inputCount 0 0 input output
                (afterBoundRows .andLeft
                  (operandRows .andLeft left
                    (afterRowPrefixRows .and
                      (.fieldEnd ::
                        (List.replicate gateIndex .tick ++
                          .gateRowMark :: rows)))))) := by
            simpa [hrightEq, withBound] using hreject
          have hfull := RejectsIn.before_steps
            ((2 * gateIndex + 3) + (3 * left + 4))
            (step_comp _ _ hprefix' hleftRun') hreject'
          have hfull' : RejectsIn
              (cfg (some .gates) state
                (encodeCircuitGate (.and left right) ++ input) output rows
                inputCount gateIndex 0 0 0)
              (invalidOperandRejectBound .andRight gateIndex rightExtra
                inputCount 0 0 input output
                (afterBoundRows .andLeft
                  (operandRows .andLeft left
                    (afterRowPrefixRows .and
                      (.fieldEnd ::
                        (List.replicate gateIndex .tick ++
                          .gateRowMark :: rows))))) +
                ((2 * gateIndex + 3) + (3 * left + 4))) := by
            simpa [encodeCircuitGate, hrightEq, List.append_assoc] using hfull
          exact RejectsIn.mono hfull' (linear_le_gateLocal capacity input output
            rows inputCount gateIndex _ (by
            simp [invalidOperandRejectBound,
              firstInvalidRejectBound, clearAndEmitInvalidSteps, operandRows,
              operandOutputIndex, afterRowPrefixRows, afterBoundRows, withBound,
              encodeCircuitGate, encNat, hleftEq, hrightEq]
              at hcapacity ⊢
            omega))
        · have hle : gateIndex ≤ left := Nat.not_lt.mp hleftValid
          obtain ⟨extra, hleftEq⟩ := Nat.exists_eq_add_of_le hle
          have hreject := invalidOperand_rejectsIn s₁ .andLeft (by decide)
            gateIndex extra inputCount 0 0 (encNat right ++ input) output
            (afterRowPrefixRows .and
              (.fieldEnd ::
                (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
          have hfull := RejectsIn.before_steps (2 * gateIndex + 3)
            (by simpa [encodeCircuitGate, rawGateTag, afterRowPrefixLabel,
              afterRowPrefixGateCount, withBound, hleftEq, List.append_assoc]
              using hprefix)
            hreject
          have hfull' : RejectsIn
              (cfg (some .gates) state
                (encodeCircuitGate (.and left right) ++ input) output rows
                inputCount gateIndex 0 0 0)
              (invalidOperandRejectBound .andLeft gateIndex extra inputCount 0 0
                (encNat right ++ input) output
                (afterRowPrefixRows .and
                  (.fieldEnd ::
                    (List.replicate gateIndex .tick ++ .gateRowMark :: rows))) +
                (2 * gateIndex + 3)) := by
            simpa [encodeCircuitGate, hleftEq, List.append_assoc] using hfull
          exact RejectsIn.mono hfull' (linear_le_gateLocal capacity input output
            rows inputCount gateIndex _ (by
            simp [invalidOperandRejectBound,
              firstInvalidRejectBound, clearAndEmitInvalidSteps, operandRows,
              operandOutputIndex, afterRowPrefixRows, withBound,
              encodeCircuitGate, encNat, hleftEq] at hcapacity ⊢
            omega))
  | or left right =>
      simp only [CircuitGate.ValidAt, not_and_or] at hinvalid
      rcases gatePrefix_phase state .or
          (encNat left ++ encNat right ++ input) output rows inputCount gateIndex
        with ⟨s₁, hprefix⟩
      rcases hinvalid with hleft | hright
      · have hle : gateIndex ≤ left := Nat.not_lt.mp hleft
        obtain ⟨extra, hleftEq⟩ := Nat.exists_eq_add_of_le hle
        have hreject := invalidOperand_rejectsIn s₁ .orLeft (by decide)
          gateIndex extra inputCount 0 0 (encNat right ++ input) output
          (afterRowPrefixRows .or
            (.fieldEnd ::
              (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
        have hfull := RejectsIn.before_steps (2 * gateIndex + 3)
          (by simpa [encodeCircuitGate, rawGateTag, afterRowPrefixLabel,
            afterRowPrefixGateCount, withBound, hleftEq, List.append_assoc]
            using hprefix)
          hreject
        have hfull' : RejectsIn
            (cfg (some .gates) state
              (encodeCircuitGate (.or left right) ++ input) output rows
              inputCount gateIndex 0 0 0)
            (invalidOperandRejectBound .orLeft gateIndex extra inputCount 0 0
              (encNat right ++ input) output
              (afterRowPrefixRows .or
                (.fieldEnd ::
                  (List.replicate gateIndex .tick ++ .gateRowMark :: rows))) +
              (2 * gateIndex + 3)) := by
          simpa [encodeCircuitGate, hleftEq, List.append_assoc] using hfull
        exact RejectsIn.mono hfull' (linear_le_gateLocal capacity input output
          rows inputCount gateIndex _ (by
          simp [invalidOperandRejectBound,
            firstInvalidRejectBound, clearAndEmitInvalidSteps, operandRows,
            operandOutputIndex, afterRowPrefixRows, withBound,
            encodeCircuitGate, encNat, hleftEq] at hcapacity ⊢
          omega))
      · by_cases hleftValid : left < gateIndex
        · obtain ⟨leftSlack, hleftEq⟩ := Nat.exists_eq_add_of_lt hleftValid
          have hle : gateIndex ≤ right := Nat.not_lt.mp hright
          obtain ⟨rightExtra, hrightEq⟩ := Nat.exists_eq_add_of_le hle
          rcases boundedOperand_phase s₁ .orLeft (by decide) left leftSlack
              inputCount 0 0 (encNat right ++ input) output
              (afterRowPrefixRows .or
                (.fieldEnd ::
                  (List.replicate gateIndex .tick ++ .gateRowMark :: rows))) with
            ⟨s₂, hleftRun⟩
          have hreject := invalidOperand_rejectsIn s₂ .orRight (by decide)
            gateIndex rightExtra inputCount 0 0 input output
            (afterBoundRows .orLeft
              (operandRows .orLeft left
                (afterRowPrefixRows .or
                  (.fieldEnd ::
                    (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))))
          have hbound : left + leftSlack + 1 = gateIndex := hleftEq.symm
          have hprefix' := hprefix
          simp [rawGateTag, afterRowPrefixLabel, afterRowPrefixGateCount,
            List.append_assoc] at hprefix'
          have hleftRun' : (flip Option.bind step)^[3 * left + 4]
              (some (cfg (some (.parseOperand .orLeft)) s₁
                (encNat left ++ (encNat right ++ input)) output
                (afterRowPrefixRows .or
                  (.fieldEnd ::
                    (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
                inputCount gateIndex 0 0 0)) =
              some (cfg (some (.parseOperand .orRight)) s₂
                (encNat right ++ input) output
                (afterBoundRows .orLeft
                  (operandRows .orLeft left
                    (afterRowPrefixRows .or
                      (.fieldEnd ::
                        (List.replicate gateIndex .tick ++
                          .gateRowMark :: rows)))))
                inputCount gateIndex 0 0 0) := by
            simpa [afterBoundLabel, afterBoundGateCount, operandOutputIndex,
              withBound, hbound] using hleftRun
          have hreject' : RejectsIn
              (cfg (some (.parseOperand .orRight)) s₂
                (encNat right ++ input) output
                (afterBoundRows .orLeft
                  (operandRows .orLeft left
                    (afterRowPrefixRows .or
                      (.fieldEnd ::
                        (List.replicate gateIndex .tick ++
                          .gateRowMark :: rows)))))
                inputCount gateIndex 0 0 0)
              (invalidOperandRejectBound .orRight gateIndex rightExtra
                inputCount 0 0 input output
                (afterBoundRows .orLeft
                  (operandRows .orLeft left
                    (afterRowPrefixRows .or
                      (.fieldEnd ::
                        (List.replicate gateIndex .tick ++
                          .gateRowMark :: rows)))))) := by
            simpa [hrightEq, withBound] using hreject
          have hfull := RejectsIn.before_steps
            ((2 * gateIndex + 3) + (3 * left + 4))
            (step_comp _ _ hprefix' hleftRun') hreject'
          have hfull' : RejectsIn
              (cfg (some .gates) state
                (encodeCircuitGate (.or left right) ++ input) output rows
                inputCount gateIndex 0 0 0)
              (invalidOperandRejectBound .orRight gateIndex rightExtra
                inputCount 0 0 input output
                (afterBoundRows .orLeft
                  (operandRows .orLeft left
                    (afterRowPrefixRows .or
                      (.fieldEnd ::
                        (List.replicate gateIndex .tick ++
                          .gateRowMark :: rows))))) +
                ((2 * gateIndex + 3) + (3 * left + 4))) := by
            simpa [encodeCircuitGate, hrightEq, List.append_assoc] using hfull
          exact RejectsIn.mono hfull' (linear_le_gateLocal capacity input output
            rows inputCount gateIndex _ (by
            simp [invalidOperandRejectBound,
              firstInvalidRejectBound, clearAndEmitInvalidSteps, operandRows,
              operandOutputIndex, afterRowPrefixRows, afterBoundRows, withBound,
              encodeCircuitGate, encNat, hleftEq, hrightEq]
              at hcapacity ⊢
            omega))
        · have hle : gateIndex ≤ left := Nat.not_lt.mp hleftValid
          obtain ⟨extra, hleftEq⟩ := Nat.exists_eq_add_of_le hle
          have hreject := invalidOperand_rejectsIn s₁ .orLeft (by decide)
            gateIndex extra inputCount 0 0 (encNat right ++ input) output
            (afterRowPrefixRows .or
              (.fieldEnd ::
                (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
          have hfull := RejectsIn.before_steps (2 * gateIndex + 3)
            (by simpa [encodeCircuitGate, rawGateTag, afterRowPrefixLabel,
              afterRowPrefixGateCount, withBound, hleftEq, List.append_assoc]
              using hprefix)
            hreject
          have hfull' : RejectsIn
              (cfg (some .gates) state
                (encodeCircuitGate (.or left right) ++ input) output rows
                inputCount gateIndex 0 0 0)
              (invalidOperandRejectBound .orLeft gateIndex extra inputCount 0 0
                (encNat right ++ input) output
                (afterRowPrefixRows .or
                  (.fieldEnd ::
                    (List.replicate gateIndex .tick ++ .gateRowMark :: rows))) +
                (2 * gateIndex + 3)) := by
            simpa [encodeCircuitGate, hleftEq, List.append_assoc] using hfull
          exact RejectsIn.mono hfull' (linear_le_gateLocal capacity input output
            rows inputCount gateIndex _ (by
            simp [invalidOperandRejectBound,
              firstInvalidRejectBound, clearAndEmitInvalidSteps, operandRows,
              operandOutputIndex, afterRowPrefixRows, withBound,
              encodeCircuitGate, encNat, hleftEq] at hcapacity ⊢
            omega))

@[simp] private theorem afterRowPrefixLabel_binary (isAnd : Bool) :
    afterRowPrefixLabel (binaryKind isAnd) =
      .parseOperand (binaryLeftReturn isAnd) := by
  cases isAnd <;> rfl

@[simp] private theorem afterRowPrefixGateCount_binary (isAnd : Bool)
    (gateIndex : Nat) :
    afterRowPrefixGateCount (binaryKind isAnd) gateIndex = gateIndex := by
  cases isAnd <;> rfl

@[simp] private theorem afterBoundLabel_binaryLeft (isAnd : Bool) :
    afterBoundLabel (binaryLeftReturn isAnd) =
      .parseOperand (binaryRightReturn isAnd) := by
  cases isAnd <;> rfl

@[simp] private theorem afterBoundGateCount_binaryLeft (isAnd : Bool)
    (gateIndex : Nat) :
    afterBoundGateCount (binaryLeftReturn isAnd) gateIndex = gateIndex := by
  cases isAnd <;> rfl

@[simp] private theorem withBound_binaryLeft (isAnd : Bool)
    (bound inputCount gateCount : Nat) :
    withBound (binaryLeftReturn isAnd) bound inputCount gateCount =
      (inputCount, bound) := by
  cases isAnd <;> rfl

@[simp] private theorem withBound_binaryRight (isAnd : Bool)
    (bound inputCount gateCount : Nat) :
    withBound (binaryRightReturn isAnd) bound inputCount gateCount =
      (inputCount, bound) := by
  cases isAnd <;> rfl

@[simp] private theorem afterBoundRows_binaryLeft (isAnd : Bool)
    (rows : List NormalizedCircuitSym) :
    afterBoundRows (binaryLeftReturn isAnd) rows = rows := by
  cases isAnd <;> rfl

@[simp] private theorem operandRows_binaryLeft (isAnd : Bool) (count : Nat)
    (rows : List NormalizedCircuitSym) :
    operandRows (binaryLeftReturn isAnd) count rows =
      .fieldEnd :: (List.replicate count .tick ++ rows) := by
  cases isAnd <;> rfl

@[simp] private theorem operandOutputIndex_binaryLeft (isAnd : Bool)
    (count outputIndex : Nat) :
    operandOutputIndex (binaryLeftReturn isAnd) count outputIndex =
      outputIndex := by
  cases isAnd <;> rfl

@[simp] private theorem afterRowPrefixRows_binary_length (isAnd : Bool)
    (rows : List NormalizedCircuitSym) :
    (afterRowPrefixRows (binaryKind isAnd) rows).length = rows.length + 1 := by
  cases isAnd <;> simp [binaryKind, afterRowPrefixRows]

private theorem binaryGateDecode_rejectsIn (state : State) (isAnd : Bool)
    (symbols : List CircuitSym) (inputCount gateIndex capacity : Nat)
    (output rows : List NormalizedCircuitSym)
    (hcapacity : (rawGateTag (binaryKind isAnd) :: symbols).length ≤ capacity)
    (hdecode : decodeCircuitGate
      (rawGateTag (binaryKind isAnd) :: symbols) = none) :
    RejectsIn
      (cfg (some .gates) state
        (rawGateTag (binaryKind isAnd) :: symbols) output rows
        inputCount gateIndex 0 0 0)
      (gateLocalRejectBound capacity symbols output rows inputCount gateIndex) := by
  cases hleft : decNat symbols with
  | none =>
      rcases gatePrefix_phase state (binaryKind isAnd) symbols output rows
          inputCount gateIndex with ⟨s₁, hprefix⟩
      have hreject := malformedOperand_rejectsIn s₁
        (binaryLeftReturn isAnd) symbols output
        (afterRowPrefixRows (binaryKind isAnd)
          (.fieldEnd ::
            (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
        inputCount gateIndex 0 0 0 hleft
      have hprefix' : (flip Option.bind step)^[2 * gateIndex + 3]
          (some (cfg (some .gates) state
            (rawGateTag (binaryKind isAnd) :: symbols) output rows
            inputCount gateIndex 0 0 0)) =
          some (cfg (some (.parseOperand (binaryLeftReturn isAnd))) s₁
            symbols output
            (afterRowPrefixRows (binaryKind isAnd)
              (.fieldEnd ::
                (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
            inputCount gateIndex 0 0 0) := by
        simpa using hprefix
      have hfull := RejectsIn.before_steps (2 * gateIndex + 3) hprefix' hreject
      exact RejectsIn.mono hfull (linear_le_gateLocal capacity symbols output
        rows inputCount gateIndex _ (by
          simp [malformedFieldBound] at hcapacity ⊢
          omega))
  | some decoded =>
      rcases decoded with ⟨left, middle⟩
      have hright : decNat middle = none := by
        apply Option.eq_none_iff_forall_ne_some.mpr
        rintro ⟨right, rest⟩ hsome
        cases isAnd with
        | false =>
            change decodeCircuitGate (.orMark :: symbols) = none at hdecode
            simp [decodeCircuitGate, hleft, hsome] at hdecode
        | true =>
            change decodeCircuitGate (.andMark :: symbols) = none at hdecode
            simp [decodeCircuitGate, hleft, hsome] at hdecode
      have hsymbols := eq_encNat_append_of_decNat_eq_some hleft
      rcases gatePrefix_phase state (binaryKind isAnd)
          (encNat left ++ middle) output rows inputCount gateIndex with
        ⟨s₁, hprefix⟩
      by_cases hvalid : left < gateIndex
      · obtain ⟨slack, hleftEq⟩ := Nat.exists_eq_add_of_lt hvalid
        have hbound : left + slack + 1 = gateIndex := hleftEq.symm
        rcases boundedOperand_phase s₁ (binaryLeftReturn isAnd) (by
            cases isAnd <;> decide) left slack inputCount 0 0 middle output
            (afterRowPrefixRows (binaryKind isAnd)
              (.fieldEnd ::
                (List.replicate gateIndex .tick ++ .gateRowMark :: rows))) with
          ⟨s₂, hleftRun⟩
        have hreject := malformedOperand_rejectsIn s₂
          (binaryRightReturn isAnd) middle output
          (afterBoundRows (binaryLeftReturn isAnd)
            (operandRows (binaryLeftReturn isAnd) left
              (afterRowPrefixRows (binaryKind isAnd)
                (.fieldEnd ::
                  (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))))
          inputCount gateIndex 0 0 0 hright
        have hprefix' : (flip Option.bind step)^[2 * gateIndex + 3]
            (some (cfg (some .gates) state
              (rawGateTag (binaryKind isAnd) :: encNat left ++ middle)
              output rows inputCount gateIndex 0 0 0)) =
            some (cfg (some (.parseOperand (binaryLeftReturn isAnd))) s₁
              (encNat left ++ middle) output
              (afterRowPrefixRows (binaryKind isAnd)
                (.fieldEnd ::
                  (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
              inputCount gateIndex 0 0 0) := by
          simpa using hprefix
        have hleftRun' : (flip Option.bind step)^[3 * left + 4]
            (some (cfg (some (.parseOperand (binaryLeftReturn isAnd))) s₁
              (encNat left ++ middle) output
              (afterRowPrefixRows (binaryKind isAnd)
                (.fieldEnd ::
                  (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
              inputCount gateIndex 0 0 0)) =
            some (cfg (some (.parseOperand (binaryRightReturn isAnd))) s₂
              middle output
              (afterBoundRows (binaryLeftReturn isAnd)
                (operandRows (binaryLeftReturn isAnd) left
                  (afterRowPrefixRows (binaryKind isAnd)
                    (.fieldEnd ::
                      (List.replicate gateIndex .tick ++
                        .gateRowMark :: rows)))))
              inputCount gateIndex 0 0 0) := by
          simpa [hbound] using hleftRun
        have hfull := RejectsIn.before_steps
          ((2 * gateIndex + 3) + (3 * left + 4))
          (step_comp _ _ hprefix' hleftRun') hreject
        have hfull' : RejectsIn
            (cfg (some .gates) state
              (rawGateTag (binaryKind isAnd) :: symbols) output rows
              inputCount gateIndex 0 0 0)
            (malformedFieldBound middle output
                (afterBoundRows (binaryLeftReturn isAnd)
                  (operandRows (binaryLeftReturn isAnd) left
                    (afterRowPrefixRows (binaryKind isAnd)
                      (.fieldEnd ::
                        (List.replicate gateIndex .tick ++
                          .gateRowMark :: rows)))))
                inputCount gateIndex 0 0 0 +
              ((2 * gateIndex + 3) + (3 * left + 4))) := by
          simpa [hsymbols, List.append_assoc] using hfull
        exact RejectsIn.mono hfull' (linear_le_gateLocal capacity symbols output
          rows inputCount gateIndex _ (by
            simp [malformedFieldBound, hsymbols, encNat] at hcapacity ⊢
            omega))
      · have hle : gateIndex ≤ left := Nat.not_lt.mp hvalid
        obtain ⟨extra, hleftEq⟩ := Nat.exists_eq_add_of_le hle
        have hreject := invalidOperand_rejectsIn s₁
          (binaryLeftReturn isAnd) (by cases isAnd <;> decide)
          gateIndex extra inputCount 0 0 middle output
          (afterRowPrefixRows (binaryKind isAnd)
            (.fieldEnd ::
              (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
        have hprefix' : (flip Option.bind step)^[2 * gateIndex + 3]
            (some (cfg (some .gates) state
              (rawGateTag (binaryKind isAnd) :: encNat left ++ middle)
              output rows inputCount gateIndex 0 0 0)) =
            some (cfg (some (.parseOperand (binaryLeftReturn isAnd))) s₁
              (encNat (gateIndex + extra) ++ middle) output
              (afterRowPrefixRows (binaryKind isAnd)
                (.fieldEnd ::
                  (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
              inputCount gateIndex 0 0 0) := by
          simpa [hleftEq] using hprefix
        have hreject' : RejectsIn
            (cfg (some (.parseOperand (binaryLeftReturn isAnd))) s₁
              (encNat (gateIndex + extra) ++ middle) output
              (afterRowPrefixRows (binaryKind isAnd)
                (.fieldEnd ::
                  (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
              inputCount gateIndex 0 0 0)
            (invalidOperandRejectBound (binaryLeftReturn isAnd) gateIndex extra
              inputCount 0 0 middle output
              (afterRowPrefixRows (binaryKind isAnd)
                (.fieldEnd ::
                  (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))) := by
          simpa using hreject
        have hfull := RejectsIn.before_steps (2 * gateIndex + 3)
          hprefix' hreject'
        have hfull' : RejectsIn
            (cfg (some .gates) state
              (rawGateTag (binaryKind isAnd) :: symbols) output rows
              inputCount gateIndex 0 0 0)
            (invalidOperandRejectBound (binaryLeftReturn isAnd) gateIndex extra
                inputCount 0 0 middle output
                (afterRowPrefixRows (binaryKind isAnd)
                  (.fieldEnd ::
                    (List.replicate gateIndex .tick ++ .gateRowMark :: rows))) +
              (2 * gateIndex + 3)) := by
          simpa [hsymbols, List.append_assoc] using hfull
        exact RejectsIn.mono hfull' (linear_le_gateLocal capacity symbols output
          rows inputCount gateIndex _ (by
            simp [invalidOperandRejectBound, firstInvalidRejectBound,
              clearAndEmitInvalidSteps, hsymbols, hleftEq, encNat]
              at hcapacity ⊢
            omega))

/-- A non-output gate whose structural decoder fails rejects within the local
quadratic gate envelope. -/
theorem gateDecode_rejectsIn (state : State) (symbol : CircuitSym)
    (symbols : List CircuitSym) (inputCount gateIndex capacity : Nat)
    (output rows : List NormalizedCircuitSym)
    (hcapacity : (symbol :: symbols).length ≤ capacity)
    (houtput : symbol ≠ .outputMark)
    (hdecode : decodeCircuitGate (symbol :: symbols) = none) :
    RejectsIn
      (cfg (some .gates) state (symbol :: symbols) output rows
        inputCount gateIndex 0 0 0)
      (gateLocalRejectBound capacity symbols output rows inputCount gateIndex) := by
  cases symbol with
  | inputMark =>
      have hnat : decNat symbols = none := by
        apply Option.eq_none_iff_forall_ne_some.mpr
        rintro ⟨n, rest⟩ hsome
        simp [decodeCircuitGate, hsome] at hdecode
      rcases gatePrefix_phase state .input symbols output rows inputCount
          gateIndex with ⟨s₁, hprefix⟩
      have hreject := malformedOperand_rejectsIn s₁ .inputGate symbols output
        (afterRowPrefixRows .input
          (.fieldEnd ::
            (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
        inputCount gateIndex 0 0 0 hnat
      have hfull := RejectsIn.before_steps (2 * gateIndex + 3)
        (by simpa [rawGateTag, afterRowPrefixLabel, afterRowPrefixGateCount]
          using hprefix) hreject
      exact RejectsIn.mono hfull (linear_le_gateLocal capacity symbols output
        rows inputCount gateIndex _ (by
          simp [malformedFieldBound, afterRowPrefixRows] at hcapacity ⊢
          omega))
  | constFalseMark => simp [decodeCircuitGate] at hdecode
  | constTrueMark => simp [decodeCircuitGate] at hdecode
  | notMark =>
      have hnat : decNat symbols = none := by
        apply Option.eq_none_iff_forall_ne_some.mpr
        rintro ⟨n, rest⟩ hsome
        simp [decodeCircuitGate, hsome] at hdecode
      rcases gatePrefix_phase state .not symbols output rows inputCount
          gateIndex with ⟨s₁, hprefix⟩
      have hreject := malformedOperand_rejectsIn s₁ .notGate symbols output
        (afterRowPrefixRows .not
          (.fieldEnd ::
            (List.replicate gateIndex .tick ++ .gateRowMark :: rows)))
        inputCount gateIndex 0 0 0 hnat
      have hfull := RejectsIn.before_steps (2 * gateIndex + 3)
        (by simpa [rawGateTag, afterRowPrefixLabel, afterRowPrefixGateCount]
          using hprefix) hreject
      exact RejectsIn.mono hfull (linear_le_gateLocal capacity symbols output
        rows inputCount gateIndex _ (by
          simp [malformedFieldBound, afterRowPrefixRows] at hcapacity ⊢
          omega))
  | andMark =>
      simpa [binaryKind, rawGateTag] using
        binaryGateDecode_rejectsIn state true symbols inputCount gateIndex
          capacity output rows hcapacity hdecode
  | orMark =>
      simpa [binaryKind, rawGateTag] using
        binaryGateDecode_rejectsIn state false symbols inputCount gateIndex
          capacity output rows hcapacity hdecode
  | outputMark => exact False.elim (houtput rfl)
  | argMark =>
      have hreject := rejectsInAfterCleanupStep
        { state with inputBuffer := some .argMark } symbols output rows inputCount
        gateIndex 0 0 0
        (gates_bad_step state .argMark (Or.inl rfl) symbols output rows
          inputCount gateIndex 0 0 0)
      exact RejectsIn.mono hreject (linear_le_gateLocal capacity symbols output
        rows inputCount gateIndex _ (by
          simp [clearAndEmitInvalidSteps] at hcapacity ⊢
          omega))
  | endMark =>
      have hreject := rejectsInAfterCleanupStep
        { state with inputBuffer := some .endMark } symbols output rows inputCount
        gateIndex 0 0 0
        (gates_bad_step state .endMark (Or.inr rfl) symbols output rows
          inputCount gateIndex 0 0 0)
      exact RejectsIn.mono hreject (linear_le_gateLocal capacity symbols output
        rows inputCount gateIndex _ (by
          simp [clearAndEmitInvalidSteps] at hcapacity ⊢
          omega))

/-- Fixed magnitude for all one-gate work inside a stream of bounded raw
capacity.  `baseStorage` is the output/row storage present before the stream. -/
def streamMagnitude (capacity baseStorage : Nat) : Nat :=
  baseStorage + 8 * (capacity + 1) ^ 2 + 1

def streamUnitBound (capacity baseStorage : Nat) : Nat :=
  4096 * (streamMagnitude capacity baseStorage) ^ 2 + 4096

/-- A fuel-indexed envelope for a malformed remaining gate stream. -/
def gateStreamRejectBound (capacity baseStorage fuel : Nat) : Nat :=
  (fuel + 1) * streamUnitBound capacity baseStorage

theorem gateLocal_le_streamUnit (capacity baseStorage : Nat)
    (input : List CircuitSym) (output rows : List NormalizedCircuitSym)
    (inputCount gateIndex : Nat)
    (hinput : input.length ≤ capacity)
    (hinputCount : inputCount ≤ capacity)
    (hgateIndex : gateIndex ≤ capacity)
    (hstorage : output.length + rows.length ≤
      baseStorage + gateIndex * (2 * capacity + 3)) :
    gateLocalRejectBound capacity input output rows inputCount gateIndex ≤
      streamUnitBound capacity baseStorage := by
  have hproduct : gateIndex * (2 * capacity + 3) ≤
      capacity * (2 * capacity + 3) :=
    Nat.mul_le_mul_right (2 * capacity + 3) hgateIndex
  have hbase : capacity + input.length + output.length + rows.length +
      inputCount + gateIndex + 1 ≤ streamMagnitude capacity baseStorage := by
    simp only [streamMagnitude]
    nlinarith
  simp only [gateLocalRejectBound, streamUnitBound]
  exact Nat.add_le_add_right
    (Nat.mul_le_mul_left 4096 (Nat.pow_le_pow_left hbase 2)) 4096

theorem gateSteps_le_streamUnit (capacity baseStorage gateIndex : Nat)
    (gate : CircuitGate)
    (hgate : (encodeCircuitGate gate).length ≤ capacity)
    (hindex : gateIndex ≤ capacity) :
    gateSteps gateIndex gate ≤ streamUnitBound capacity baseStorage := by
  have hsteps := gateSteps_le_encoding gateIndex gate
  have hlinear : gateSteps gateIndex gate ≤
      64 * streamMagnitude capacity baseStorage := by
    apply hsteps.trans
    simp [streamMagnitude]
    nlinarith
  exact hlinear.trans (by
    simp [streamUnitBound]
    nlinarith)

/-- A structurally malformed remaining gate stream rejects within a uniform
fuel-times-unit bound.  The row-storage invariant records exactly the indexed
rows accumulated by already-consumed gates. -/
theorem gateStreamDecodeNone_rejectsIn (state : State) (fuel : Nat)
    (symbols : List CircuitSym) (inputCount gateIndex : Nat)
    (output rows : List NormalizedCircuitSym) (capacity baseStorage : Nat)
    (hfuel : symbols.length ≤ fuel)
    (hcapacity : symbols.length ≤ capacity)
    (hinputCount : inputCount ≤ capacity)
    (hindexFuel : gateIndex + fuel ≤ capacity)
    (hstorage : output.length + rows.length ≤
      baseStorage + gateIndex * (2 * capacity + 3))
    (hdecode : decodeCircuitGates fuel symbols = none) :
    RejectsIn
      (cfg (some .gates) state symbols output rows inputCount gateIndex 0 0 0)
      (gateStreamRejectBound capacity baseStorage fuel) := by
  induction fuel generalizing state symbols gateIndex rows with
  | zero =>
      have hempty : symbols = [] := by
        cases symbols <;> simp_all
      subst symbols
      have hreject := rejectsInAfterCleanupStep
        { state with inputBuffer := none } [] output rows inputCount gateIndex
        0 0 0 (gates_empty_step state output rows inputCount gateIndex 0 0 0)
      have hlocal : RejectsIn
          (cfg (some .gates) state [] output rows inputCount gateIndex 0 0 0)
          (gateLocalRejectBound capacity [] output rows inputCount gateIndex) :=
        RejectsIn.mono hreject (linear_le_gateLocal capacity [] output rows
          inputCount gateIndex _ (by
            simp [clearAndEmitInvalidSteps]
            omega))
      have hunit := gateLocal_le_streamUnit capacity baseStorage [] output rows
        inputCount gateIndex (by simp) hinputCount (by omega) hstorage
      exact RejectsIn.mono hlocal (by
        simpa [gateStreamRejectBound] using hunit)
  | succ fuel ih =>
      cases symbols with
      | nil =>
          have hreject := rejectsInAfterCleanupStep
            { state with inputBuffer := none } [] output rows inputCount gateIndex
            0 0 0 (gates_empty_step state output rows inputCount gateIndex 0 0 0)
          have hlocal : RejectsIn
              (cfg (some .gates) state [] output rows inputCount gateIndex 0 0 0)
              (gateLocalRejectBound capacity [] output rows inputCount gateIndex) :=
            RejectsIn.mono hreject (linear_le_gateLocal capacity [] output rows
              inputCount gateIndex _ (by
                simp [clearAndEmitInvalidSteps]
                omega))
          have hunit := gateLocal_le_streamUnit capacity baseStorage [] output
            rows inputCount gateIndex (by simp) hinputCount (by omega) hstorage
          exact RejectsIn.mono hlocal (by
            simp [gateStreamRejectBound]
            exact hunit.trans (Nat.le_mul_of_pos_left _ (by omega)))
      | cons symbol symbols =>
          by_cases hout : symbol = .outputMark
          · subst symbol
            have hnat : decNat symbols = none := by
              apply Option.eq_none_iff_forall_ne_some.mpr
              rintro ⟨n, rest⟩ hsome
              simp [decodeCircuitGates, hsome] at hdecode
            have hreject := malformedOperand_rejectsIn
              { state with inputBuffer := some .outputMark } .outputGate symbols
              output rows inputCount gateIndex 0 0 0 hnat
            have htag := gates_output_step state symbols output rows inputCount
              gateIndex 0 0 0
            have hfull := RejectsIn.before_step htag hreject
            have hlocal : RejectsIn
                (cfg (some .gates) state (.outputMark :: symbols) output rows
                  inputCount gateIndex 0 0 0)
                (gateLocalRejectBound capacity symbols output rows inputCount
                  gateIndex) :=
              RejectsIn.mono hfull (linear_le_gateLocal capacity symbols output
                rows inputCount gateIndex _ (by
                  simp [malformedFieldBound]
                  omega))
            have hsymbolsCapacity : symbols.length ≤ capacity :=
              (Nat.le_succ symbols.length).trans (by simpa using hcapacity)
            have hunit := gateLocal_le_streamUnit capacity baseStorage symbols
              output rows inputCount gateIndex hsymbolsCapacity hinputCount
              (by omega) hstorage
            exact RejectsIn.mono hlocal (by
              calc
                gateLocalRejectBound capacity symbols output rows inputCount
                    gateIndex ≤ streamUnitBound capacity baseStorage := hunit
                _ ≤ gateStreamRejectBound capacity baseStorage (fuel + 1) := by
                  simp [gateStreamRejectBound]
                  exact Nat.le_mul_of_pos_left _ (by omega))
          · cases hgate : decodeCircuitGate (symbol :: symbols) with
            | none =>
                have hlocal := gateDecode_rejectsIn state symbol symbols
                  inputCount gateIndex capacity output rows hcapacity hout hgate
                have hsymbolsCapacity : symbols.length ≤ capacity :=
                  (Nat.le_succ symbols.length).trans (by simpa using hcapacity)
                have hunit := gateLocal_le_streamUnit capacity baseStorage
                  symbols output rows inputCount gateIndex hsymbolsCapacity
                  hinputCount (by omega) hstorage
                exact RejectsIn.mono hlocal (by
                  calc
                    gateLocalRejectBound capacity symbols output rows inputCount
                        gateIndex ≤ streamUnitBound capacity baseStorage := hunit
                    _ ≤ gateStreamRejectBound capacity baseStorage
                        (fuel + 1) := by
                      simp [gateStreamRejectBound]
                      exact Nat.le_mul_of_pos_left _ (by omega))
            | some decoded =>
                rcases decoded with ⟨gate, rest⟩
                have hrestDecode : decodeCircuitGates fuel rest = none := by
                  cases symbol <;> simp_all [decodeCircuitGates]
                  all_goals
                    exact Option.eq_none_iff_forall_ne_some.mpr (by
                      rintro ⟨gates, outputIndex, trailing⟩ hsome
                      exact hdecode gates outputIndex trailing hsome)
                have hsymbols :=
                  eq_encodeCircuitGate_append_of_decodeCircuitGate_eq_some hgate
                have hgateLength : 1 ≤ (encodeCircuitGate gate).length := by
                  cases gate with
                  | input i => simp [encodeCircuitGate]
                  | const value => cases value <;> simp [encodeCircuitGate]
                  | not source => simp [encodeCircuitGate]
                  | and left right => simp [encodeCircuitGate]
                  | or left right => simp [encodeCircuitGate]
                have hrestFuel : rest.length ≤ fuel := by
                  have hlength := congrArg List.length hsymbols
                  simp only [List.length_cons, List.length_append] at hlength hfuel
                  omega
                have hrestCapacity : rest.length ≤ capacity := by
                  have hrestLe : rest.length ≤ (symbol :: symbols).length := by
                    rw [hsymbols]
                    simp
                  exact hrestLe.trans hcapacity
                have hgateCapacity : (encodeCircuitGate gate).length ≤
                    capacity := by
                  have hgateLe : (encodeCircuitGate gate).length ≤
                      (symbol :: symbols).length := by
                    rw [hsymbols]
                    simp
                  exact hgateLe.trans hcapacity
                have hcombinedCapacity :
                    (encodeCircuitGate gate ++ rest).length ≤ capacity := by
                  rw [← hsymbols]
                  exact hcapacity
                rw [hsymbols]
                by_cases hvalid : gate.ValidAt inputCount gateIndex
                · rcases gate_phase state gate gateIndex inputCount hvalid rest
                      output rows with ⟨s₁, hrun⟩
                  have hnextStorage : output.length +
                      ((encodeNormalizedGateRow gateIndex gate).reverse ++
                        rows).length ≤
                      baseStorage + (gateIndex + 1) * (2 * capacity + 3) := by
                    rw [List.length_append, List.length_reverse,
                      encodeNormalizedGateRow_length]
                    nlinarith
                  have htail := ih s₁ rest (gateIndex + 1)
                    ((encodeNormalizedGateRow gateIndex gate).reverse ++ rows)
                    hrestFuel hrestCapacity (by omega) hnextStorage hrestDecode
                  have hfull := RejectsIn.before_steps
                    (gateSteps gateIndex gate) hrun htail
                  have hstepBound := gateSteps_le_streamUnit capacity baseStorage
                    gateIndex gate hgateCapacity (by omega)
                  exact RejectsIn.mono hfull (by
                    simp only [gateStreamRejectBound]
                    nlinarith)
                · have hlocal := invalidGate_rejectsIn state gate gateIndex
                      inputCount capacity hvalid rest output rows
                      hcombinedCapacity
                  have hunit := gateLocal_le_streamUnit capacity baseStorage rest
                    output rows inputCount gateIndex hrestCapacity hinputCount
                    (by omega) hstorage
                  exact RejectsIn.mono hlocal (by
                    calc
                      gateLocalRejectBound capacity rest output rows inputCount
                          gateIndex ≤ streamUnitBound capacity baseStorage := hunit
                      _ ≤ gateStreamRejectBound capacity baseStorage
                          (fuel + 1) := by
                        simp [gateStreamRejectBound]
                        exact Nat.le_mul_of_pos_left _ (by omega))

end CLRS.Chapter34.Turing.GeneralCircuitToSAT.Normalizer
Source
https://github.com/tanktechnology/CLRS-Lean

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