Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.CookLevin.Circuitization.GeneratorTransitionDispatchMuxFalseArmAffine

Definition
PricingWithTips3DM_208b41b3680c476c9b38196f

by qmaai2907271020 · Oct 23, 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_115d16e341305c7dc06321b7
import Mathlib.Tactic
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Affine source table for dispatch-mux false arms

After the initial widened row, every later false arm is the preceding mux's
output row.  These output wires form one stride-three progression.  The fixed
descriptor recursion below emits exactly those progressions for all but the
last program label.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- First-coordinate values of an arbitrary triple progression. -/
def transitionProgressionFirstValues
    (progression : AffineUnaryTripleProgression) : List Nat :=
  (affineUnaryTripleProgressionRows progression).map fun row => row.1

/-- Output row of the mux belonging to one label at the current affine gate
offset. -/
def transitionDispatchPreviousOutputProgression
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (offset : TransitionAffineNat) (label : tm.Λ) :
    AffineUnaryTripleProgression :=
  let muxOffset := offset.add (transitionDispatchStmtGateAffine tm label)
  { base₁ := seed.start + muxOffset.eval seed.height + 3
    base₂ := 0
    base₃ := 0
    step₁ := 3
    step₂ := 0
    step₃ := 0
    count := cfgBitCount tm (workHeight tm seed.height) }

/-- Previous-mux output progressions needed by a fixed label suffix.  A
singleton suffix needs no preceding output row. -/
def transitionDispatchPreviousOutputProgressionsForLabels
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    TransitionAffineNat → List tm.Λ →
      List AffineUnaryTripleProgression
  | _, [] => []
  | _, [_] => []
  | offset, label :: next :: labels =>
      let muxOffset := offset.add (transitionDispatchStmtGateAffine tm label)
      transitionDispatchPreviousOutputProgression tm seed offset label ::
        transitionDispatchPreviousOutputProgressionsForLabels tm seed
          (muxOffset.add (transitionDispatchMuxGateAffine tm))
          (next :: labels)

/-- Complete preceding-mux output family for the canonical label list. -/
def transitionDispatchPreviousOutputProgressions
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    List AffineUnaryTripleProgression :=
  transitionDispatchPreviousOutputProgressionsForLabels tm seed
    (TransitionAffineNat.const 2) (programLabels tm)

/-- Seven fixed forms describing one preceding-mux output row. -/
def transitionDispatchPreviousOutputDescriptorBlock
    (tm : _root_.Turing.FinTM2) (offset : TransitionAffineNat)
    (label : tm.Λ) : List AffineUnaryTripleForm :=
  let muxOffset := offset.add (transitionDispatchStmtGateAffine tm label)
  [ transitionAbsoluteStartForm
      (muxOffset.add (TransitionAffineNat.const 3)),
    transitionZeroForm, transitionZeroForm,
    transitionHeightAffineForm (TransitionAffineNat.const 3),
    transitionZeroForm, transitionZeroForm,
    transitionHeightAffineForm
      ((transitionCfgBitAffine tm).shiftInput (maxPushesPerStep tm)) ]

/-- Fixed descriptor recursion parallel to the runtime progression family. -/
def transitionDispatchPreviousOutputDescriptorFormsForLabels
    (tm : _root_.Turing.FinTM2) :
    TransitionAffineNat → List tm.Λ → List AffineUnaryTripleForm
  | _, [] => []
  | _, [_] => []
  | offset, label :: next :: labels =>
      let muxOffset := offset.add (transitionDispatchStmtGateAffine tm label)
      transitionDispatchPreviousOutputDescriptorBlock tm offset label ++
        transitionDispatchPreviousOutputDescriptorFormsForLabels tm
          (muxOffset.add (transitionDispatchMuxGateAffine tm))
          (next :: labels)

/-- Complete verifier-fixed descriptor table for preceding mux outputs. -/
def transitionDispatchPreviousOutputDescriptorForms
    (tm : _root_.Turing.FinTM2) : List AffineUnaryTripleForm :=
  transitionDispatchPreviousOutputDescriptorFormsForLabels tm
    (TransitionAffineNat.const 2) (programLabels tm)

/-- One fixed descriptor block evaluates to its runtime progression. -/
theorem transitionDispatchPreviousOutputDescriptorBlock_value
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (offset : TransitionAffineNat) (label : tm.Λ) :
    affineUnaryTripleMap
        (transitionDispatchPreviousOutputDescriptorBlock tm offset label)
        (transitionTailAffineSeed seed) =
      let progression :=
        transitionDispatchPreviousOutputProgression tm seed offset label
      [ progression.base₁, progression.base₂, progression.base₃,
        progression.step₁, progression.step₂, progression.step₃,
        progression.count ] := by
  simp [transitionDispatchPreviousOutputDescriptorBlock,
    transitionDispatchPreviousOutputProgression, affineUnaryTripleMap,
    transitionAbsoluteStartForm, transitionZeroForm,
    transitionHeightAffineForm, transitionTailAffineSeed,
    affineUnaryTripleFormValue, TransitionAffineNat.eval,
    TransitionAffineNat.add, TransitionAffineNat.const,
    workHeight]
  constructor
  · ring
  · change ((transitionCfgBitAffine tm).shiftInput
        (maxPushesPerStep tm)).eval seed.height = _
    rw [TransitionAffineNat.eval_shiftInput, transitionCfgBitAffine_eval]

/-- Evaluating the fixed recursive table gives exactly the concatenated
runtime descriptors. -/
theorem transitionDispatchPreviousOutputDescriptorFormsForLabels_value
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    ∀ (offset : TransitionAffineNat) (labels : List tm.Λ),
      affineUnaryTripleMap
          (transitionDispatchPreviousOutputDescriptorFormsForLabels tm
            offset labels)
          (transitionTailAffineSeed seed) =
        (transitionDispatchPreviousOutputProgressionsForLabels tm seed
          offset labels).flatMap fun progression =>
            [ progression.base₁, progression.base₂, progression.base₃,
              progression.step₁, progression.step₂, progression.step₃,
              progression.count ] := by
  intro offset labels
  induction labels generalizing offset with
  | nil => rfl
  | cons label labels ih =>
      cases labels with
      | nil => rfl
      | cons next labels =>
          simp only [transitionDispatchPreviousOutputDescriptorFormsForLabels,
            transitionDispatchPreviousOutputProgressionsForLabels]
          rw [show affineUnaryTripleMap
              (transitionDispatchPreviousOutputDescriptorBlock tm offset label ++
                transitionDispatchPreviousOutputDescriptorFormsForLabels tm
                  ((offset.add
                    (transitionDispatchStmtGateAffine tm label)).add
                      (transitionDispatchMuxGateAffine tm))
                  (next :: labels))
              (transitionTailAffineSeed seed) =
            affineUnaryTripleMap
                (transitionDispatchPreviousOutputDescriptorBlock tm offset label)
                (transitionTailAffineSeed seed) ++
              affineUnaryTripleMap
                (transitionDispatchPreviousOutputDescriptorFormsForLabels tm
                  ((offset.add
                    (transitionDispatchStmtGateAffine tm label)).add
                      (transitionDispatchMuxGateAffine tm))
                  (next :: labels))
                (transitionTailAffineSeed seed) by
              simp [affineUnaryTripleMap, List.map_append]]
          rw [transitionDispatchPreviousOutputDescriptorBlock_value, ih]
          rfl

theorem transitionDispatchPreviousOutputDescriptorForms_value
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    affineUnaryTripleMap
        (transitionDispatchPreviousOutputDescriptorForms tm)
        (transitionTailAffineSeed seed) =
      (transitionDispatchPreviousOutputProgressions tm seed).flatMap
        fun progression =>
          [ progression.base₁, progression.base₂, progression.base₃,
            progression.step₁, progression.step₂, progression.step₃,
            progression.count ] := by
  exact transitionDispatchPreviousOutputDescriptorFormsForLabels_value
    tm seed (TransitionAffineNat.const 2) (programLabels tm)

/-- The descriptor bytes are exactly the generic progression-family input. -/
theorem encode_transitionDispatchPreviousOutputDescriptorForms
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    encodeUnaryFrame
        (affineUnaryTripleMap
          (transitionDispatchPreviousOutputDescriptorForms tm)
          (transitionTailAffineSeed seed)) =
      encodeAffineUnaryTripleProgressionFamily
        (transitionDispatchPreviousOutputProgressions tm seed) := by
  rw [transitionDispatchPreviousOutputDescriptorForms_value]
  unfold encodeUnaryFrame
  induction transitionDispatchPreviousOutputProgressions tm seed with
  | nil => rfl
  | cons progression rest ih =>
      simp only [List.flatMap_cons,
        encodeAffineUnaryTripleProgressionFamily,
        encodeAffineUnaryTripleProgression, List.flatMap_append]
      rw [ih]
      simp [encodeUnaryFrame, List.append_assoc]

/-- One preceding-output progression is exactly the canonical arithmetic mux
output row. -/
theorem transitionDispatchPreviousOutputProgression_values
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (offset : TransitionAffineNat) (start : Nat) (label : tm.Λ)
    (hstart : start = seed.start + offset.eval seed.height)
    (hwork : 0 < workHeight tm seed.height) :
    transitionProgressionFirstValues
        (transitionDispatchPreviousOutputProgression tm seed offset label) =
      transitionCfgWireValues tm (workHeight tm seed.height)
        (arithmeticMuxCfgWires tm (workHeight tm seed.height)
          (start + compileStmtGateCost tm (workHeight tm seed.height)
            (tm.m label))) := by
  unfold transitionProgressionFirstValues transitionCfgWireValues
    transitionDispatchPreviousOutputProgression arithmeticMuxCfgWires
  rw [affineUnaryTripleProgressionRows_eq_ofFn, List.map_ofFn]
  apply List.ofFn_inj.mpr
  funext coordinate
  simp only [Function.comp_apply, Equiv.apply_symm_apply]
  rw [TransitionAffineNat.eval_add,
    transitionDispatchStmtGateAffine_eval tm label seed.height hwork]
  rw [hstart]
  ring

/-- The generated preceding-output progressions are exactly the false-arm
rows of the remaining label suffix. -/
theorem transitionDispatchPreviousOutputProgressionsForLabels_values
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (source : CfgWires tm (workHeight tm seed.height))
    (hwork : 0 < workHeight tm seed.height) :
    ∀ (offset : TransitionAffineNat) (start : Nat)
      (label : tm.Λ) (labels : List tm.Λ),
      start = seed.start + offset.eval seed.height →
      (transitionDispatchPreviousOutputProgressionsForLabels tm seed
          offset (label :: labels)).flatMap
          transitionProgressionFirstValues =
        (transitionDispatchFalseArmRowsForLabels tm seed.height source
          (start + compileStmtGateCost tm (workHeight tm seed.height)
              (tm.m label) +
            (3 * cfgBitCount tm (workHeight tm seed.height) + 1))
          (arithmeticMuxCfgWires tm (workHeight tm seed.height)
            (start + compileStmtGateCost tm (workHeight tm seed.height)
              (tm.m label))) labels).flatten := by
  intro offset start label labels hstart
  induction labels generalizing offset start label with
  | nil => rfl
  | cons next labels ih =>
      simp only [transitionDispatchPreviousOutputProgressionsForLabels,
        List.flatMap_cons, transitionDispatchFalseArmRowsForLabels,
        List.flatten_cons]
      rw [transitionDispatchPreviousOutputProgression_values tm seed offset
        start label hstart hwork]
      congr 1
      apply ih
      rw [TransitionAffineNat.eval_add, TransitionAffineNat.eval_add,
        transitionDispatchStmtGateAffine_eval tm label seed.height hwork,
        transitionDispatchMuxGateAffine_eval tm seed.height, hstart]
      omega

/-- Complete false-arm progression family: canonical widened row followed by
the output rows of every mux except the final one. -/
def transitionDispatchFalseArmProgressions
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    List AffineUnaryTripleProgression :=
  transitionWidenedFallbackProgressions tm seed ++
    transitionDispatchPreviousOutputProgressions tm seed

/-- Complete fixed descriptor table for the false-arm family. -/
def transitionDispatchFalseArmDescriptorForms
    (tm : _root_.Turing.FinTM2) : List AffineUnaryTripleForm :=
  transitionWidenedFallbackDescriptorForms tm ++
    transitionDispatchPreviousOutputDescriptorForms tm

private theorem transitionWidenedFallbackProgressions_firstValues
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    (transitionWidenedFallbackProgressions tm seed).flatMap
        transitionProgressionFirstValues =
      transitionWidenedFallbackValues tm seed := by
  unfold transitionWidenedFallbackProgressions
  rw [List.flatMap_map]
  change (transitionWidenedFallbackSegments tm).flatMap
      (transitionWidenedFallbackSegmentValues seed) = _
  exact transitionWidenedFallbackSegments_values tm seed

/-- The complete generated first-track stream is exactly the flattened
semantic false-arm rows of the seed-derived dispatch. -/
theorem transitionDispatchFalseArmProgressions_values
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (hwork : 0 < workHeight tm seed.height) :
    (transitionDispatchFalseArmProgressions tm seed).flatMap
        transitionProgressionFirstValues =
      (transitionDispatchFalseArmRowsFromSeed tm seed).flatten := by
  unfold transitionDispatchFalseArmProgressions
    transitionDispatchPreviousOutputProgressions
    transitionDispatchFalseArmRowsFromSeed
  rw [List.flatMap_append,
    transitionWidenedFallbackProgressions_firstValues]
  cases hlabels : programLabels tm with
  | nil => exact False.elim (programLabels_nonempty tm hlabels)
  | cons label labels =>
      simp only [transitionDispatchFalseArmRowsForLabels, List.flatten_cons]
      rw [show transitionCfgWireValues tm (workHeight tm seed.height)
          (arithmeticWidenedCfgWires tm seed.height seed.start seed.rowBase) =
          transitionWidenedFallbackValues tm seed by
        unfold transitionCfgWireValues
        exact (transitionWidenedFallbackValues_eq_canonical tm seed).symm]
      congr 1
      apply transitionDispatchPreviousOutputProgressionsForLabels_values
        tm seed
        (arithmeticWidenedCfgWires tm seed.height seed.start seed.rowBase)
        hwork (TransitionAffineNat.const 2) (seed.start + 2) label labels
      simp

/-- Evaluating the complete fixed descriptor table gives the combined runtime
progression family. -/
theorem transitionDispatchFalseArmDescriptorForms_value
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    affineUnaryTripleMap (transitionDispatchFalseArmDescriptorForms tm)
        (transitionTailAffineSeed seed) =
      (transitionDispatchFalseArmProgressions tm seed).flatMap
        fun progression =>
          [ progression.base₁, progression.base₂, progression.base₃,
            progression.step₁, progression.step₂, progression.step₃,
            progression.count ] := by
  unfold transitionDispatchFalseArmDescriptorForms
    transitionDispatchFalseArmProgressions
  rw [show affineUnaryTripleMap
      (transitionWidenedFallbackDescriptorForms tm ++
        transitionDispatchPreviousOutputDescriptorForms tm)
      (transitionTailAffineSeed seed) =
    affineUnaryTripleMap (transitionWidenedFallbackDescriptorForms tm)
        (transitionTailAffineSeed seed) ++
      affineUnaryTripleMap
        (transitionDispatchPreviousOutputDescriptorForms tm)
        (transitionTailAffineSeed seed) by
      simp [affineUnaryTripleMap, List.map_append]]
  rw [transitionWidenedFallbackDescriptorForms_value,
    transitionDispatchPreviousOutputDescriptorForms_value,
    List.flatMap_append]

/-- The combined descriptor bytes are the exact generic family encoding. -/
theorem encode_transitionDispatchFalseArmDescriptorForms
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    encodeUnaryFrame
        (affineUnaryTripleMap (transitionDispatchFalseArmDescriptorForms tm)
          (transitionTailAffineSeed seed)) =
      encodeAffineUnaryTripleProgressionFamily
        (transitionDispatchFalseArmProgressions tm seed) := by
  rw [transitionDispatchFalseArmDescriptorForms_value]
  unfold encodeUnaryFrame
  induction transitionDispatchFalseArmProgressions tm seed with
  | nil => rfl
  | cons progression rest ih =>
      simp only [List.flatMap_cons,
        encodeAffineUnaryTripleProgressionFamily,
        encodeAffineUnaryTripleProgression, List.flatMap_append]
      rw [ih]
      simp [encodeUnaryFrame, List.append_assoc]

end CLRS.Chapter34.Turing.CookLevin
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