Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_ad2f6a0f56affeb774827237

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_e21fd01d42817c93da25cf29
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Absolute coordinates of finite one-hot pair-map outputs

The binary lookup used by `peek` and `pop` first emits one AND gate for each
source pair, then performs an ordinary one-hot map.  Consequently its output
coordinates are again a fixed family translated by the current gate start.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

/-- Zero-based output coordinate of a fixed binary one-hot lookup. -/
def oneHotPairMapWireOffset {n p m : Nat}
    (f : Fin n → Fin p → Fin m) (target : Fin m) : Nat :=
  n * p + oneHotMapWireOffset (oneHotPairFunction f) target

theorem oneHotPairAndBodyGateTrace_length
    {n p : Nat} (start : Nat) (left : Fin n → CircuitBuilder.Wire)
    (right : Fin p → CircuitBuilder.Wire) :
    ∀ (k : Nat) (hk : k ≤ n * p),
      (oneHotPairAndBodyGateTrace start left right k hk).gates.length = k := by
  intro k
  induction k with
  | zero =>
      intro hk
      rfl
  | succ k ih =>
      intro hk
      simp [oneHotPairAndBodyGateTrace, ih]

theorem oneHotPairAndGateTrace_length
    {n p : Nat} (start : Nat) (left : Fin n → CircuitBuilder.Wire)
    (right : Fin p → CircuitBuilder.Wire) :
    (oneHotPairAndGateTrace start left right).gates.length = n * p := by
  exact oneHotPairAndBodyGateTrace_length start left right
    (n * p) (Nat.le_refl _)

private theorem oneHotPairAndBodyGateTrace_wire_eq_start_add_val
    {n p : Nat} (start : Nat) (left : Fin n → CircuitBuilder.Wire)
    (right : Fin p → CircuitBuilder.Wire) :
    ∀ (k : Nat) (hk : k ≤ n * p) (q : Fin k),
      (oneHotPairAndBodyGateTrace start left right k hk).wires q =
        start + q.val := by
  intro k
  induction k with
  | zero =>
      intro hk q
      exact Fin.elim0 q
  | succ k ih =>
      intro hk q
      by_cases hq : q.val < k
      · simp only [oneHotPairAndBodyGateTrace, dif_pos hq]
        exact ih (by omega) ⟨q.val, hq⟩
      · simp only [oneHotPairAndBodyGateTrace, dif_neg hq]
        rw [oneHotPairAndBodyGateTrace_length]
        have hqEq : q.val = k :=
          Nat.le_antisymm (Nat.le_of_lt_succ q.isLt)
            (Nat.le_of_not_gt hq)
        rw [hqEq]

/-- Pair materialization emits one gate per pair in flattened pair order, so
fresh pair wire `q` is exactly `start + q.val`. -/
theorem oneHotPairAndGateTrace_wire_eq_start_add_val
    {n p : Nat} (start : Nat) (left : Fin n → CircuitBuilder.Wire)
    (right : Fin p → CircuitBuilder.Wire) (q : Fin (n * p)) :
    (oneHotPairAndGateTrace start left right).wires q = start + q.val :=
  oneHotPairAndBodyGateTrace_wire_eq_start_add_val start left right
    (n * p) (Nat.le_refl _) q

theorem oneHotPairAndGateTrace_wires_eq_start_add_val
    {n p : Nat} (start : Nat) (left : Fin n → CircuitBuilder.Wire)
    (right : Fin p → CircuitBuilder.Wire) :
    (oneHotPairAndGateTrace start left right).wires =
      fun q => start + q.val := by
  funext q
  exact oneHotPairAndGateTrace_wire_eq_start_add_val start left right q

/-- Every binary lookup output coordinate is the gate start plus its fixed
pair-table offset. -/
theorem oneHotPairMapGateTrace_wire_eq_start_add_offset
    {n p m : Nat} (start : Nat)
    (left : Fin n → CircuitBuilder.Wire)
    (right : Fin p → CircuitBuilder.Wire)
    (f : Fin n → Fin p → Fin m) (target : Fin m) :
    (oneHotPairMapGateTrace start left right f).wires target =
      start + oneHotPairMapWireOffset f target := by
  simp only [oneHotPairMapGateTrace]
  rw [oneHotMapGateTrace_wire_eq_start_add_offset,
    oneHotPairAndGateTrace_length]
  simp [oneHotPairMapWireOffset, Nat.add_assoc]

/-- Function-level pair-map coordinate equation used by state replacement. -/
theorem oneHotPairMapGateTrace_wires_eq_offset
    {n p m : Nat} (start : Nat)
    (left : Fin n → CircuitBuilder.Wire)
    (right : Fin p → CircuitBuilder.Wire)
    (f : Fin n → Fin p → Fin m) :
    (oneHotPairMapGateTrace start left right f).wires =
      fun target => start + oneHotPairMapWireOffset f target := by
  funext target
  exact oneHotPairMapGateTrace_wire_eq_start_add_offset
    start left right f target

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