Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Construction for Theorem 7.4, part 2: decoders, trials, state preparation, serialization

Definition
TwoFoldOPI_CL_Part02

by sragavan · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

lean-formalizationquantum-algorithmstwo-fold-opi-construction

Definitions underlying the formal construction behind the algorithmic part of Theorem 7.4, part 2 (imports part 1). It contains the real decoder layout and the full decoder circuit, the trial loop (zero test, readout, retries), the subtraction circuit, the repeat-until-success state-preparation stages and their jobs, the preparation layout, and the first part of the polynomial-time realizer framework: first-order program nodes, the depth-first serializer, and polynomial realizers with their arithmetic and list combinators.

The bundle contains only definitions together with the structural lemmas these definitions require.

Definition code
import Definitions.Def_TwoFoldOPI_CL_Part01
import Mathlib
import Definitions.Def_OAIThreeMachineSched01
import Definitions.Def_CookLevin_Cost

set_option maxHeartbeats 400000
set_option linter.all false

-- ===== OPI.BfacL =====
section

/-!
# Nested factorized states

`bfacL L g = h₁ ⊗_{w₁} (h₂ ⊗_{w₂} ⋯ g)` for a list `L` of (register, state) pairs. Commutation,
support and norm lemmas.
-/

namespace OPI

open QAlgorithms

variable {n : ℕ}

/-- A state on a register. -/
structure Res (n : ℕ) where
  k : ℕ
  w : Fin k ↪ Fin n
  h : Qubits k → ℂ

/-- Nested factorized states. -/
noncomputable def bfacL : List (Res n) → (Qubits n → ℂ) → Qubits n → ℂ
  | [], g => g
  | r :: L, g => bfac r.w r.h (bfacL L g)



/-- Two registers are disjoint. -/
def Res.Disj (r r' : Res n) : Prop := ∀ i j, r.w i ≠ r'.w j

















end OPI

namespace OPI

open QAlgorithms

variable {n : ℕ}





end OPI

namespace OPI

open QAlgorithms

variable {n : ℕ}

/-- Clear all registers of a list. -/
noncomputable def clrL (L : List (Res n)) (y : Qubits n) : Qubits n := L.foldr (fun r y => clrE r.w y) y







end OPI

namespace OPI

open QAlgorithms

variable {n : ℕ}



end OPI
end

-- ===== OPI.RWires =====
section

/-!
# Wires of reversible circuits

`WiresIn P L`: every gate of `L` touches only wires satisfying `P`. Such circuits commute with
factorized states on registers outside `P` (`revCirc_bfac`). Wire bounds for the builders
`mcx`, `flipZeros`, `eqFlip`, `cxOut`, `lookup`, `lookupF`, `swapRegs`, `permGad`.
-/

namespace OPI

open QAlgorithms

variable {N : ℕ}

/-- Wires of a reversible gate. -/
def RGate.wires : RGate N → List (Fin N)
  | .x q => [q]
  | .cx c t => [c, t]
  | .ccx a b t => [a, b, t]

/-- All gates touch only wires satisfying `P`. -/
def WiresIn (P : Fin N → Prop) (L : List (RGate N)) : Prop := ∀ g ∈ L, ∀ q ∈ g.wires, P q













/-! ## Builders -/

















/-! ## Commutation with factorized states -/

section Comm

variable {k : ℕ} (w : Fin k ↪ Fin N)













end Comm

end OPI
end

-- ===== OPI.DecReal =====
section

/-!
# The real decoder: `QFT_q` gadgets with `|u_p⟩` resources

The ideal decoder `allOps` uses exact `Q_q` on the symbol registers. The real one uses the
`QFT_q` gadgets `Q i c` (`QQ`), which consume `|u_p⟩` resources in their `B` registers. With all
resources prepared (`RSL`), the real decoder is within `2 m ε` of the ideal one.
-/

namespace OPI

namespace SymEnc

open QAlgorithms TwoFoldOPI Matrix

variable (F : AvgCaseTI.FieldPres) {n b t m : ℕ}

/-- The resources of a `QFT_q` gadget. -/
noncomputable def resQ (Q : QQ n b F t) : List (Res n) :=
  Q.Gs.map fun G => ⟨Fq.w F, G.bE, fvec F.p (Fq.w F) 0⟩



/-- Constrained wires of a `QFT_q` gadget. -/
def cWire (Q : QQ n b F t) (q : Fin n) : Prop :=
  q ∈ Q.ZR ++ Q.asR ++ [Q.fR] ∨
    ∃ G ∈ Q.Gs, q ∈ Set.range G.bE ∨ q ∈ Set.range G.cE ∨ q ∈ G.acc ∨ q ∈ G.cl

/-- Scratch wires of the `E` and `P_β` gadgets of a coordinate. -/
def epWire {reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n} {i : Fin m} (W : CoordWires F reg i)
    (q : Fin n) : Prop :=
  q = W.aE ∨ q = W.fE ∨ q ∈ W.ZE ∨ q ∈ W.asE ∨ q = W.fP ∨ q ∈ W.ZP ∨ q ∈ W.asP

/-- **Layout of the real decoder.** -/
structure RealDec (reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n) (b t : ℕ) where
  W : ∀ i, CoordWires F reg i
  Q : Fin m → Bool → QQ n b F t
  hQX : ∀ i c, (Q i c).X = bReg reg i c
  hres : ∀ i c i' c', (i, c) ≠ (i', c') → ∀ r ∈ resQ F (Q i c), ∀ r' ∈ resQ F (Q i' c'), r.Disj r'
  hcw : ∀ i c q, cWire F (Q i c) q → (∀ p, reg p ≠ q) ∧
    ∀ i' c', (i, c) ≠ (i', c') → ∀ r ∈ resQ F (Q i' c'), q ∉ Set.range r.w
  hep : ∀ i i' c', ∀ r ∈ resQ F (Q i' c'), ∀ q, epWire F (W i) q → q ∉ Set.range r.w

variable {F}
variable {reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n} (D : RealDec F reg b t)





/-- The resources of all gadgets. -/
def RealDec.isRes (r : Res n) : Prop := ∃ i c, r ∈ resQ F (D.Q i c)



/-! ## Commutation of the exact gadgets with resources -/

/-- Circuits commuting with a factor. -/
def CommRes {k : ℕ} (w : Fin k ↪ Fin n) (C : Circuit htcxGateSet n) : Prop :=
  ∀ h g, (Circuit.unitary C).mulVec (bfac w h g) = bfac w h ((Circuit.unitary C).mulVec g)







variable {D}









/-! ## Supports of resource-dressed symbol states -/



variable (D) in
/-- Resources of gadgets other than `(i, c)`. -/
def OtherRes (i : Fin m) (c : Bool) (L : List (Res n)) : Prop :=
  ∀ r ∈ L, ∃ i' c', (i, c) ≠ (i', c') ∧ r ∈ resQ F (D.Q i' c')







/-! ## One coordinate of the real decoder -/



variable (D) in
/-- Resources of a coordinate. -/
noncomputable def resC (i : Fin m) : List (Res n) := resQ F (D.Q i false) ++ resQ F (D.Q i true)

variable (D) in
/-- The real operator of a coordinate. -/
noncomputable def actC (i : Fin m) (β : F.F) : Mat n :=
  QQ.U (D.Q i true) * QQ.U (D.Q i false) *
    Circuit.unitary (eGad (reg := reg) i (D.W i).ZE (D.W i).asE (D.W i).aE (D.W i).fE) *
    Circuit.unitary (revCirc (pGad reg (elemBits F) i (D.W i).ZP (D.W i).asP (D.W i).fP (fun x => β - x)))

variable (F b t) in
/-- Error of one `QFT_q` gadget. -/
noncomputable def epsQ : ℝ := (F.f.natDegree : ℝ) * (2 * Real.pi / 2 ^ b + 2 * (F.p / Real.sqrt (2 ^ t)))

lemma resQ_pairwise (Q : QQ n b F t) : (resQ F Q).Pairwise Res.Disj := by
  unfold resQ
  rw [List.pairwise_map]
  refine Q.hpair.imp (fun {G G'} h => ?_)
  intro i j e
  exact h.2.1 i (Or.inr (Or.inl ⟨j, e.symm⟩))







/-! ## Normalization of the product states -/







/-! ## All coordinates -/

variable (D) in
/-- The real operators of the coordinates in a list, head applied last. -/
noncomputable def actOps (β : Fin m → F.F) : List (Fin m) → Mat n
  | [] => 1
  | i :: is => actC D i (β i) * actOps β is









/-! ## Decoding probability of the real decoder -/



variable (D) in
/-- All resources. -/
noncomputable def RSall (g : Qubits n → ℂ) : Qubits n → ℂ := bfacL ((List.finRange m).flatMap (resC D)) g



end SymEnc

end OPI
end

-- ===== OPI.TrialCore =====
section

/-!
# The trial of the A-domain Regev reduction, on the register level

The register `R` (embedding `wR`) holds an encoding `enc d` of `d`; the decoder's output register is
read by `out` (a function of the configuration that ignores `R`). The subtraction `R ⊖= O` is a
permutation `σ` that acts only on `R`:

  `σ z = setE wR z (sub (z ∘ wR) (out z))`, with `sub (enc d) o = enc 0 ↔ o = d`.

Then, for `Ψ = Σ_d |enc d⟩_R ⊗ φ_d`, the `R = 0` part of `σ Ψ` is `|enc 0⟩_R ⊗ Σ_d P_{out = d} φ_d`.
With `φ_d = U ψ_d` (a decoder `U` acting off `R`) and `U†` afterwards, this is `|enc 0⟩ ⊗ vAcc`.
-/

namespace OPI

open QAlgorithms Matrix

variable {n k : ℕ} {δ : Type*} [DecidableEq δ]

/-- Restriction to configurations whose register `w` holds `y0`. -/
def projReg (w : Fin k ↪ Fin n) (y0 : Qubits k) (f : Qubits n → ℂ) : Qubits n → ℂ :=
  fun z => if z ∘ w = y0 then f z else 0

/-- The delta function of a register value. -/
def delta (y0 : Qubits k) : Qubits k → ℂ := fun y => if y = y0 then 1 else 0

section Sub

variable (wR : Fin k ↪ Fin n) (enc : δ → Qubits k) (d0 : δ) (out : Qubits n → δ)
  (sub : Qubits k → δ → Qubits k) (subInv : Qubits k → δ → Qubits k)
  (hout : ∀ z y, out (setE wR z y) = out z)
  (hinv1 : ∀ y o, subInv (sub y o) o = y) (hinv2 : ∀ y o, sub (subInv y o) o = y)
  (hzero : ∀ d o, sub (enc d) o = enc d0 ↔ o = d)

/-- The subtraction permutation. -/
noncomputable def subEquiv : Qubits n ≃ Qubits n where
  toFun z := setE wR z (sub (z ∘ wR) (out z))
  invFun z := setE wR z (subInv (z ∘ wR) (out z))
  left_inv z := by
    simp only [setE_comp, hout]
    rw [hinv1, setE_setE, setE_comp_self]
  right_inv z := by
    simp only [setE_comp, hout]
    rw [hinv2, setE_setE, setE_comp_self]



end Sub

/-! ## Operators acting off the register -/

section Off

variable (wR : Fin k ↪ Fin n)

/-- `U` acts off the register `wR`: it commutes with factorization and with register tests. -/
def OffReg (U : Mat n) : Prop :=
  (∀ (h : Qubits k → ℂ) (g : Qubits n → ℂ), U.mulVec (bfac wR h g) = bfac wR h (U.mulVec g)) ∧
    ∀ (y0 : Qubits k) (f : Qubits n → ℂ), U.mulVec (projReg wR y0 f) = projReg wR y0 (U.mulVec f)











end Off

/-! ## The trial core -/

section Core

variable (wR : Fin k ↪ Fin n) (enc : δ → Qubits k) (d0 : δ) (out : Qubits n → δ)
  (sub : Qubits k → δ → Qubits k) (subInv : Qubits k → δ → Qubits k)
  (hout : ∀ z y, out (setE wR z y) = out z)
  (hinv1 : ∀ y o, subInv (sub y o) o = y) (hinv2 : ∀ y o, sub (subInv y o) o = y)
  (hzero : ∀ d o, sub (enc d) o = enc d0 ↔ o = d)





end Core

end OPI
end

-- ===== OPI.OffRegOps =====
section

/-!
# Operators acting off a register

`OffReg w` (commutation with `w`-factorizations and `w`-restrictions) for permutations of
reversible gate lists that avoid `w`, diagonal operators that ignore `w`, and their adjoints. Wire
bounds for the arithmetic builders `incr`, `addInto`, `rdList`, `tauList`, `csList`.
-/

namespace OPI

open QAlgorithms Matrix

variable {N : ℕ}

/-! ## Wire bounds -/











/-! ## `OffReg` closure -/

section Off

variable {k : ℕ} (w : Fin k ↪ Fin N)











end Off

/-! ## Two-sided `OffReg` -/

section Two

variable {n : ℕ} {k : ℕ} (w : Fin k ↪ Fin n)

/-- `U` and `U†` act off `w`. -/
def OffReg2 (U : Mat n) : Prop := OffReg w U ∧ OffReg w Uᴴ













/-- The wires of a `QFT_p` gadget's system unitary. -/
def QG.sysWire {b p ww t : ℕ} (G : QG n b p ww t) (q : Fin n) : Prop :=
  q ∈ Set.range G.aE ∨ q ∈ Set.range G.bE ∨ q ∈ Set.range G.cE ∨ q ∈ G.top ∨ q = G.lh ∨
    q ∈ G.lrest ∨ q ∈ G.Z ∨ q ∈ G.as ∨ q = G.f





/-- The wires of a `QFT_q` gadget's system unitary. -/
def QQ.sysWire {F : AvgCaseTI.FieldPres} {b t : ℕ} (Q : QQ n b F t) (q : Fin n) : Prop :=
  q ∈ Set.range Q.X ∨ q ∈ Q.ZR ∨ q ∈ Q.asR ∨ q = Q.fR ∨ ∃ G ∈ Q.Gs, G.sysWire q









end Two

end OPI
end

-- ===== OPI.Trial =====
section

/-!
# The trial on the program level: readout, the flag test, retries

* `copyCirc`: the Boolean circuit that outputs designated memory slots.
* `measAll`: measure a list of qubits into memory slots; followed by `halt`, its law is
  `Σ_z [event (output z)] |f z|²`.
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI Matrix

variable {N c out : ℕ}

/-! ## Output circuits -/

/-- Output memory slot `slot j` as output bit `j`. -/
def copyCirc (slot : Fin out → Fin c) : BoolCircuit c out where
  gates := []
  outputs j := slot j

lemma copyCirc_wf (slot : Fin out → Fin c) : (copyCirc slot).WellFormed := by
  refine ⟨fun k => k.elim0, fun j => ?_⟩
  simp [copyCirc]



/-! ## Measuring a register -/

/-- Measure each qubit into its memory slot. -/
def measAll : List (Fin N × Fin c) → Prog N c out → Prog N c out
  | [], P => P
  | (q, d) :: L, P => .measure q d fun _ => measAll L P

/-- The memory after the measurements of `L` on configuration `z`. -/
def writeMem : List (Fin N × Fin c) → Qubits N → (Fin c → Bool) → Fin c → Bool
  | [], _, mem => mem
  | (q, d) :: L, z, mem => writeMem L z (Function.update mem d (z q))







/-- The readout list: output bit `j` is the measurement of qubit `qOf j` into slot `slot j`. -/
def readList (qOf : Fin out → Fin N) (slot : Fin out → Fin c) : List (Fin N × Fin c) :=
  List.ofFn fun j => (qOf j, slot j)



/-! ## Retries -/

/-- `k` trials, then `fail`; `T P` is a trial that continues with `P` on rejection. -/
def retry (T : Prog N c out → Prog N c out) : ℕ → Prog N c out
  | 0 => .fail
  | k + 1 => T (retry T k)



/-! ## Measurements on the system part of the layout -/





/-! ## Resetting the whole system register -/



/-- All system wires of the layout `n + b`. -/
def sysWires (n b : ℕ) : List (Fin (n + b)) := (List.finRange n).map (Fin.castAdd b)





/-- The all-zero system state. -/
def sysZero (n : ℕ) : Qubits n → ℂ := fun z => if z = fun _ => false then 1 else 0

variable {n b : ℕ}



/-! ## The zero test -/

/-- Measure the wires `qs` one by one; on the first `1` continue with `Rj`, and if all are `0`
continue with `A`. -/
def zeroTest (dz : Fin c) : List (Fin N) → Prog N c out → Prog N c out → Prog N c out
  | [], A, _ => A
  | q :: qs, A, Rj => .measure q dz fun β => if β then Rj else zeroTest dz qs A Rj

/-- Restriction to configurations where the wires `qs` are `0`. -/
def zeroPart (qs : List (Fin n)) (φ : Qubits n → ℂ) : Qubits n → ℂ :=
  fun z => if ∀ a ∈ qs, z a = false then φ z else 0







/-! ## The gradient register is normalized -/





/-! ## The trial middle: decoder, subtraction, inverse decoder, zero test -/

section Middle

variable {k : ℕ} {δ : Type*} [DecidableEq δ]
  (wR : Fin k ↪ Fin n) (enc : δ → Qubits k) (d0 : δ) (out' : Qubits n → δ)
  (sub : Qubits k → δ → Qubits k) (subInv : Qubits k → δ → Qubits k)
  (hout : ∀ z y, out' (setE wR z y) = out' z)
  (hinv1 : ∀ y o, subInv (sub y o) o = y) (hinv2 : ∀ y o, sub (subInv y o) o = y)
  (hzero : ∀ d o, sub (enc d) o = enc d0 ↔ o = d) (henc0 : enc d0 = fun _ => false)

















end Middle

/-! ## Numerics of the retry loop -/



/-! ## The trial loop -/

/-- One trial: the preparation `pre`, the middle circuit, and the zero test with readout on
acceptance and reset-and-continue on rejection. -/
def trialStep (pre : Prog (n + b) c out → Prog (n + b) c out) (C : Circuit htcxGateSet (n + b))
    (dz : Fin c) (Rw : List (Fin n)) (Acc : Prog (n + b) c out) (P : Prog (n + b) c out) :
    Prog (n + b) c out :=
  pre ((circSeg C).prog (zeroTest dz (Rw.map (Fin.castAdd b)) Acc (resets (sysWires n b) P)))

section Loop

variable {k : ℕ} {δ : Type*} [DecidableEq δ]
  (wR : Fin k ↪ Fin n) (enc : δ → Qubits k) (d0 : δ) (out' : Qubits n → δ)
  (sub : Qubits k → δ → Qubits k) (subInv : Qubits k → δ → Qubits k)
  (hout : ∀ z y, out' (setE wR z y) = out' z)
  (hinv1 : ∀ y o, subInv (sub y o) o = y) (hinv2 : ∀ y o, sub (subInv y o) o = y)
  (hzero : ∀ d o, sub (enc d) o = enc d0 ↔ o = d) (henc0 : enc d0 = fun _ => false)



end Loop

end OPI
end

-- ===== OPI.CatComm =====
section

/-!
# Catalysed operators commute with states on registers they avoid

If `C` implements `U` on clean states (`Cat cl C U`) and the gates of `C` avoid the register `w`,
then `U (h ⊗_w g) = h ⊗_w (U g)` (for `g`, `h ⊗_w g` clean).
-/

namespace OPI

open QAlgorithms Matrix

variable {n b k : ℕ}













end OPI

namespace OPI

open QAlgorithms Matrix

variable {n : ℕ}

/-- The clean subspace. -/
def cleanSub (cl : List (Fin n)) : Submodule ℂ (Qubits n → ℂ) where
  carrier := {ψ | ∀ x, ψ x ≠ 0 → ∀ a ∈ cl, x a = false}
  add_mem' := by
    intro f g hf hg x hx
    by_cases h : f x = 0
    · exact hg x (by simpa [h] using hx)
    · exact hf x h
  zero_mem' := by intro x hx; simp at hx
  smul_mem' := by
    intro c f hf x hx
    exact hf x (fun h => hx (by simp [h]))



end OPI
end

-- ===== OPI.DecFull =====
section

/-!
# The full decoder: `Cat`, `PresClean`, `OffReg`

The decoder circuit applies, coordinate by coordinate, `P_β`, `E`, `QFT_q` on `S_i` and on `T_i`,
and finally the compiled classical decoder. All `QFT_q` gadgets share their clean scratch `clQ`.
-/

namespace OPI

open QAlgorithms Matrix

variable {N : ℕ}









/-! ## Wires of compiled straight-line programs -/



namespace SymEnc

open TwoFoldOPI

variable {F : AvgCaseTI.FieldPres} {n b t m : ℕ}
  {reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n}

/-- Wires of the `E` and `P_β` gadgets of a coordinate (including its symbol registers). -/
def epAll {i : Fin m} (W : CoordWires F reg i) (q : Fin n) : Prop :=
  epWire F W q ∨ q ∈ List.ofFn (bReg reg i false) ∨ q ∈ List.ofFn (bReg reg i true)





/-- **The full decoder layout.** -/
structure DecFull (F : AvgCaseTI.FieldPres) (reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n)
    (b t k k2 kR : ℕ) where
  D : RealDec F reg b t
  C : ClsLay reg (elemBits F) (decodeElem F) (Fq.decode_elemBits F) k k2
  clQ : List (Fin n)
  hclQ : ∀ i c, (D.Q i c).cl = clQ
  wR : Fin kR ↪ Fin n
  hep : ∀ i q, epAll (D.W i) q → q ∉ clQ ∧ q ∉ Set.range wR
  hqR : ∀ i c q, (D.Q i c).sysWire q → q ∉ Set.range wR
  hcls : ∀ q, ((∃ x < nIds m k k2, q ∈ C.rs x) ∨ q ∈ C.as ∨ q = C.f0) → q ∉ clQ ∧ q ∉ Set.range wR

variable {k k2 kR : ℕ} (X : DecFull F reg b t k k2 kR)

/-- The circuit of one coordinate. -/
noncomputable def DecFull.cCirc (i : Fin m) (β : F.F) : Circuit htcxGateSet (n + b) :=
  relocCirc sysEmb (revCirc (pGad reg (elemBits F) i (X.D.W i).ZP (X.D.W i).asP (X.D.W i).fP
    (fun x => β - x))) ++
  relocCirc sysEmb (eGad (reg := reg) i (X.D.W i).ZE (X.D.W i).asE (X.D.W i).aE (X.D.W i).fE) ++
  (X.D.Q i false).circ ++ (X.D.Q i true).circ

/-- The circuits of a list of coordinates, head last. -/
noncomputable def DecFull.dCirc (β : Fin m → F.F) : List (Fin m) → Circuit htcxGateSet (n + b)
  | [] => []
  | i :: is => DecFull.dCirc β is ++ X.cCirc i (β i)

/-- The full decoder circuit. -/
noncomputable def DecFull.circ (β : Fin m → F.F) (bD : Fin k → Fin m → F.F) (bW : Fin k2 → Fin m → F.F) :
    Circuit htcxGateSet (n + b) :=
  X.dCirc β (List.finRange m) ++ relocCirc sysEmb (revCirc (clsGates X.C bD bW))

/-- The system unitary of the decoder. -/
noncomputable def DecFull.U (β : Fin m → F.F) (bD : Fin k → Fin m → F.F) (bW : Fin k2 → Fin m → F.F) :
    Mat n :=
  Circuit.unitary (revCirc (clsGates X.C bD bW)) * actOps X.D β (List.finRange m)













end SymEnc

end OPI
end

-- ===== OPI.RSub =====
section

/-!
# The register `R` and the subtraction `R ⊖= O`

`R` holds a word `d ∈ K^m`, block `i` (bits `fPF (i, ·)`) encoding `d_i` by `elemBits`.
The subtraction acts blockwise: a valid block `y_i` becomes `y_i − o_i`; invalid blocks are kept.
-/

namespace OPI

namespace SymEnc

open QAlgorithms TwoFoldOPI

variable (F : AvgCaseTI.FieldPres) (m : ℕ)

set_option hygiene false in
local notation "L" => bitsPerSymbol F

/-- Block `i` of a register of `m` symbols. -/
def blk (y : Qubits (m * L)) (i : Fin m) : Qubits L := fun j => y (finProdFinEquiv (i, j))

/-- Assemble blocks. -/
def unblk (v : Fin m → Qubits L) : Qubits (m * L) := fun x =>
  v (finProdFinEquiv.symm x).1 (finProdFinEquiv.symm x).2





/-- The encoding of a word. -/
noncomputable def encW (d : Fin m → F.F) : Qubits (m * L) := unblk F m fun i => elemBits F (d i)





open Classical in
/-- Blockwise shift by `±o` on valid blocks. -/
noncomputable def shiftW (s : F.F) (y : Qubits (m * L)) (o : Fin m → F.F) : Qubits (m * L) :=
  unblk F m fun i => if Fq.Valid F (blk F m y i) then elemBits F (decodeElem F (blk F m y i) + s * o i)
    else blk F m y i









/-! ## The subtraction circuit -/

/-- Bits as a symbol register value. -/
def toQ (bs : List Bool) : Qubits L := fun j => bs.getD j false



open Classical in
/-- Shift an encoded symbol by `s · dec c`. -/
noncomputable def fShift (s : F.F) (c B : List Bool) : List Bool :=
  if Fq.Valid F (toQ F B) then List.ofFn (elemBits F (decodeElem F (toQ F B) + s * decodeElem F (toQ F c)))
  else B





variable {F m} {n : ℕ}

/-- The subtraction gadget of coordinate `i`. -/
noncomputable def subGad (Os : List (Fin n)) (Ri : Fin L ↪ Fin n) (Z as : List (Fin n)) (f : Fin n) :
    List (RGate n) :=
  permGad Os (List.ofFn Ri) Z as f (fShift F (-1)) (fShift F 1)



/-! ## All coordinates -/

section All

variable (Rr : Fin m → (Fin L ↪ Fin n))
  (hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')

/-- The register `R` as one embedding. -/
def wRof : Fin (m * L) ↪ Fin n :=
  ⟨fun x => Rr (finProdFinEquiv.symm x).1 (finProdFinEquiv.symm x).2, fun x x' h => by
    obtain ⟨h1, h2⟩ := hRd _ _ _ _ h
    exact finProdFinEquiv.symm.injective (Prod.ext h1 h2)⟩



/-- The decoded output word. -/
noncomputable def outOf (Os : Fin m → List (Fin n)) (z : Qubits n) : Fin m → F.F :=
  fun i => decodeElem F (toQ F ((Os i).map z))

/-- The subtraction circuit. -/
noncomputable def subAll (Rr : Fin m → (Fin L ↪ Fin n)) (Os : Fin m → List (Fin n)) (Z as : List (Fin n))
    (f : Fin n) (is : List (Fin m)) : List (RGate n) :=
  is.flatMap fun i => subGad (F := F) (Os i) (Rr i) Z as f

variable (Os : Fin m → List (Fin n)) (Z as : List (Fin n)) (f : Fin n)



variable (hnd : ∀ i, (Os i ++ List.ofFn (Rr i) ++ Z ++ as ++ [f]).Nodup) (hZ : L = Z.length)
  (hlen : ∀ i, (Os i).length + L ≤ as.length + 2)
  (hOs : ∀ i i' j, ∀ q ∈ Os i', Rr i j ≠ q)
  (hsc : ∀ i j, Rr i j ≠ f ∧ (∀ q ∈ Z, Rr i j ≠ q) ∧ ∀ q ∈ as, Rr i j ≠ q)





end All

/-! ## Reversible circuits agreeing with a permutation on clean configurations -/



end SymEnc

end OPI
end

-- ===== OPI.PrepR =====
section

/-!
# Preparing `Σ_{d ∈ D} |d⟩` in the register `R`

`G` is a basis of `D` in reduced row-echelon form with pivots `piv` (`G j (piv j') = [j = j']`).
After the pivot symbols of `R` hold a uniformly random `a ∈ K^k` (repeat-until-success), the shifts
`R_i += G_{j i} · R_{piv j}` (non-pivot `i`) produce `R = a G`.
-/

namespace OPI

namespace SymEnc

open QAlgorithms TwoFoldOPI

variable {F : AvgCaseTI.FieldPres} {n : ℕ}

set_option hygiene false in
local notation "L" => bitsPerSymbol F

/-- The shift gadget `R_i += s · dec (c)`. -/
noncomputable def shGad (s : F.F) (Os : List (Fin n)) (Ri : Fin L ↪ Fin n) (Z as : List (Fin n)) (f : Fin n) :
    List (RGate n) :=
  permGad Os (List.ofFn Ri) Z as f (fShift F s) (fShift F (-s))





/-! ## The linear map `R_i += Σ_j G_{j i} R_{piv j}` -/

section Lin

variable {m kd : ℕ} (G : Fin kd → Fin m → F.F) (piv : Fin kd → Fin m)
  (Rr : Fin m → (Fin L ↪ Fin n)) (hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')
  (Z as : List (Fin n)) (f : Fin n)

/-- The shift of one pair `(j, i)`. -/
noncomputable def linGad (p : Fin kd × Fin m) : List (RGate n) :=
  shGad (G p.1 p.2) (List.ofFn (Rr (piv p.1))) (Rr p.2) Z as f

/-- Effect of a list of shifts on a word. -/
noncomputable def linWord (ps : List (Fin kd × Fin m)) (v : Fin m → F.F) : Fin m → F.F :=
  ps.foldl (fun v p => Function.update v p.2 (v p.2 + G p.1 p.2 * v (piv p.1))) v

variable (hnd : ∀ p : Fin kd × Fin m, (∀ j', piv j' ≠ p.2) → (List.ofFn (Rr (piv p.1)) ++ List.ofFn (Rr p.2) ++ Z ++ as ++ [f]).Nodup)
  (hZ : L = Z.length) (hlen : L + L ≤ as.length + 2)
  (hsc : ∀ i j, Rr i j ≠ f ∧ (∀ q ∈ Z, Rr i j ≠ q) ∧ ∀ q ∈ as, Rr i j ≠ q)







open Classical in
/-- The shift pairs: every row `j`, every non-pivot column `i`. -/
noncomputable def linPairs : List (Fin kd × Fin m) :=
  (List.finRange kd).flatMap fun j =>
    ((List.finRange m).filter fun i => ∀ j', piv j' ≠ i).map fun i => (j, i)



end Lin

end SymEnc

end OPI
end

-- ===== OPI.Prep =====
section

/-!
# Preparation laws

`PreLaw pre f f' w e`: running `pre P` from `f` yields at least `w · K − e` whenever `P` yields at
least `K` from `f'`. Composition, circuits, repeat-until-success, scaling, perturbation.
-/

namespace OPI

open QAlgorithms Matrix

variable {N c out : ℕ} (event : Option (Fin out → Bool) → Prop)

/-- A preparation law. -/
def PreLaw (pre : Prog N c out → Prog N c out) (f f' : Qubits N → ℂ) (w e : ℝ) : Prop :=
  ∀ P K, (∀ mem, K ≤ lawP P event f' mem) → ∀ mem, w * K - e ≤ lawP (pre P) event f mem

variable {event}















end OPI

namespace OPI

open QAlgorithms

variable {N c out : ℕ} {event : Option (Fin out → Bool) → Prop}



end OPI
end

-- ===== OPI.PrepState =====
section

/-!
# States of the preparation

* `rusOut_eq_bfac`: a repeat-until-success output is a factorized state on its register;
* `perm_bfac_delta`: a permutation that moves basis words of a register moves factorized states;
* `bfac_sum_delta`: a factor on a register is the sum of its basis words.
-/

namespace OPI

open QAlgorithms

variable {N : ℕ}









/-! ## The uniform pivot state -/

namespace SymEnc

open TwoFoldOPI

variable {F : AvgCaseTI.FieldPres} {n m kd : ℕ}

set_option hygiene false in
local notation "L" => bitsPerSymbol F

variable (Rr : Fin m → (Fin L ↪ Fin n)) (hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')
  (piv : Fin kd → Fin m) (hpivi : Function.Injective piv)

open Classical in
/-- The word with pivot values `a` and zeros elsewhere. -/
noncomputable def vPiv (a : Fin kd → F.F) : Fin m → F.F :=
  fun i => if h : ∃ j, piv j = i then a (Classical.choose h) else 0





/-- The pivot registers with a factor `h` each. -/
noncomputable def pivRes (h : Qubits L → ℂ) : List (Res n) :=
  (List.finRange kd).map fun j => (⟨L, Rr (piv j), h⟩ : Res n)







/-! ## The linear map on basis words -/

section LinBasis

variable (G : Fin kd → Fin m → F.F) (hpiv : ∀ j j', G j (piv j') = if j = j' then 1 else 0)
  (Z as : List (Fin n)) (f : Fin n)
  (hnd : ∀ p : Fin kd × Fin m, (∀ j', piv j' ≠ p.2) → (List.ofFn (Rr (piv p.1)) ++ List.ofFn (Rr p.2) ++ Z ++ as ++ [f]).Nodup)
  (hZ : L = Z.length) (hlen : L + L ≤ as.length + 2)
  (hsc : ∀ i j, Rr i j ≠ f ∧ (∀ q ∈ Z, Rr i j ≠ q) ∧ ∀ q ∈ as, Rr i j ≠ q)

/-- Clean scratch. -/
def scrClean (z : Qubits n) : Prop := z f = false ∧ (∀ q ∈ as, z q = false) ∧ ∀ q ∈ Z, z q = false

/-- The linear-map circuit. -/
noncomputable def linCirc : List (RGate n) := (linPairs piv).flatMap (linGad G piv Rr Z as f)



end LinBasis

end SymEnc

end OPI
end

-- ===== OPI.PrepPhase =====
section

/-!
# The phase `Z^d` on `(R_i, S_i)`

The table `(r, s) ↦ ⌊2^b · tr(r s)/p⌋` on `L + L` bits, with kickback into the gradient register, is
within `2π/2^b` of `ψ(r s) = ω_p^{tr(r s)}` on encoded symbols.
-/

namespace OPI

namespace SymEnc

open QAlgorithms TwoFoldOPI

variable (F : AvgCaseTI.FieldPres) (b : ℕ)

set_option hygiene false in
local notation "L" => bitsPerSymbol F

/-- The phase table of one coordinate. -/
noncomputable def zTab : List (List Bool × List Bool) :=
  funTable (L + L) fun pat =>
    natBits b (2 ^ b * (Fq.tr F (decodeElem F (toQ F (pat.take L)) * decodeElem F (toQ F (pat.drop L)))).val / F.p)





end SymEnc

end OPI

namespace OPI

open QAlgorithms Matrix

variable {n : ℕ}





end OPI
end

-- ===== OPI.PrepChain =====
section

/-!
# Chains of repeat-until-success stages

`rusChain js` runs one repeat-until-success stage per job (register, membership test); on a state
clean on all job registers and the shared flag/ancillas it prepares `bfacL (js.map res) f`.
-/

namespace OPI

open QAlgorithms

variable {n b c out : ℕ} {event : Option (Fin out → Bool) → Prop}

/-- A repeat-until-success job. -/
structure RJob (n : ℕ) where
  k : ℕ
  w : Fin k ↪ Fin n
  memT : List Bool → Bool

/-- The factor a job prepares. -/
noncomputable def RJob.res (j : RJob n) : Res n :=
  ⟨j.k, j.w, fun v => if j.memT (List.ofFn v) then ((Real.sqrt 2 : ℂ))⁻¹ ^ j.k else 0⟩

/-- The chain of stages, head first. -/
noncomputable def rusChain (fl f0 : Fin n) (as : List (Fin n)) (dst : Fin c) (R : ℕ) :
    List (RJob n) → Prog (n + b) c out → Prog (n + b) c out
  | [], P => P
  | j :: js, P => rusProg (List.ofFn (j.w.trans (sysEmb (b := b)))) (Fin.castAdd b fl) (Fin.castAdd b f0)
      (as.map (Fin.castAdd b)) j.memT dst R (rusChain fl f0 as dst R js P)

/-- The weight of a chain. -/
noncomputable def RJob.wt (j : RJob n) (R : ℕ) : ℝ :=
  ∑ t ∈ Finset.range R, rusFail (List.ofFn (j.w.trans (sysEmb (b := b)))) j.memT ^ t





end OPI
end

-- ===== OPI.PrepJ =====
section

/-!
# Symbol registers prepared factor by factor are `J`-states

If each `S_i` carries a factor `h_i` supported on encodings and everything else is `0`, the state is
`J (⊗_i (h_i ∘ enc) ⊗ δ₀)`.
-/

namespace OPI

namespace SymEnc

open QAlgorithms TwoFoldOPI

variable {F : AvgCaseTI.FieldPres} {n m : ℕ} (reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n)

/-- Factors on the `S` registers. -/
noncomputable def sRes (h : Fin m → Qubits (bitsPerSymbol F) → ℂ) : List (Res n) :=
  (List.finRange m).map fun i => (⟨bitsPerSymbol F, bReg reg i false, h i⟩ : Res n)



/-- The product state of `S`-factors and `T = 0`. -/
noncomputable def sProd (h : Fin m → Qubits (bitsPerSymbol F) → ℂ) : Fin m → F.F × F.F → ℂ :=
  fun i w => if w.2 = 0 then h i (elemBits F w.1) else 0



end SymEnc

end OPI
end

-- ===== OPI.PrepZ =====
section

/-!
# The ideal phase on the prepared state

`Dideal_d z = Π_i ψ(d_i · dec(z_{S_i}))` maps `J (⊗ aState ⊗ δ₀)` to `J (⊗ Z^{d_i} aState ⊗ δ₀)`;
it commutes with factors on other registers.
-/

namespace OPI

namespace SymEnc

open QAlgorithms TwoFoldOPI CoordSym

variable {F : AvgCaseTI.FieldPres} {n m : ℕ} (reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n)

/-- The ideal phase of a word `d` on the `S` registers. -/
noncomputable def phS (d : Fin m → F.F) (z : Qubits n) : ℂ :=
  ∏ i, Fq.ψ F (d i * decodeElem F (z ∘ bReg reg i false))



/-- The unphased pair states. -/
noncomputable def gA (β : Fin m → F.F) : Fin m → F.F × F.F → ℂ :=
  fun i => withZero F (aState F (β i))







/-! ## The phase on `R ⊗ S` -/

section RS

set_option hygiene false in
local notation "L" => bitsPerSymbol F

variable (Rr : Fin m → (Fin L ↪ Fin n)) (hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')

/-- The ideal phase `Π_i ψ(dec R_i · dec S_i)`. -/
noncomputable def phRS (z : Qubits n) : ℂ :=
  ∏ i, Fq.ψ F (decodeElem F (z ∘ Rr i) * decodeElem F (z ∘ bReg reg i false))



/-- The real phase of the table circuits. -/
noncomputable def phReal (b : ℕ) {N' : ℕ} (scr : List (Fin N')) (z : Qubits n) : ℂ :=
  ∏ i, kickPhase b (tableNat scr (zTab F b) (List.ofFn (z ∘ Rr i) ++ List.ofFn (z ∘ bReg reg i false)))



/-! ## The phase circuit -/

variable {b : ℕ} (scr as : List (Fin n)) (f : Fin n)

/-- The table-phase gates of one coordinate. -/
noncomputable def tpg (i : Fin m) : List (RGate (n + b)) :=
  tablePhaseGates (List.ofFn (Rr i) ++ List.ofFn (bReg reg i false)) scr as f (zTab F b)

/-- The phase circuit for a list of coordinates. -/
noncomputable def phCirc : List (Fin m) → Circuit htcxGateSet (n + b)
  | [] => []
  | i :: is => phCirc is ++ revCirc (tpg reg Rr (b := b) scr as f i)

variable (hsl : scr.length = b) (hbl : 1 + b ≤ as.length + 2) (hxl : L + L ≤ as.length + 2)
  (hnd : ∀ i, (List.ofFn (Rr i) ++ List.ofFn (bReg reg i false) ++ scr ++ as ++ [f]).Nodup)



end RS

end SymEnc

end OPI
end

-- ===== OPI.PrepJobs =====
section

/-!
# The repeat-until-success jobs of the preparation and their factors

Up to explicit scalars, the factors are `aState β_i` on `S_i` (via `elemBits`), `|u_p⟩` on the
resource registers, and the uniform valid symbol on the pivot registers.
-/

namespace OPI

open QAlgorithms TwoFoldOPI

variable {n : ℕ}





/-- Scale the factors of a list. -/
def Res.scale (c : Res n → ℂ) (r : Res n) : Res n := ⟨r.k, r.w, fun v => c r * r.h v⟩





end OPI

namespace OPI

namespace SymEnc

open QAlgorithms TwoFoldOPI CoordSym

variable {F : AvgCaseTI.FieldPres} {n m : ℕ}

set_option hygiene false in
local notation "L" => bitsPerSymbol F

open Classical in
/-- The repeat-until-success job of `S_i`: valid and `≠ β_i`. -/
noncomputable def sJob (reg : Fin m × Bool × Fin L ↪ Fin n) (β : Fin m → F.F) (i : Fin m) : RJob n :=
  ⟨L, bReg reg i false, fun bits => decide (Fq.Valid F (toQ F bits) ∧ decodeElem F (toQ F bits) ≠ β i)⟩

open Classical in
/-- The unnormalized `aState` factor on encodings. -/
noncomputable def hA (β : Fin m → F.F) (i : Fin m) (v : Qubits L) : ℂ :=
  if Fq.Valid F v then aState F (β i) (decodeElem F v) else 0

/-- The scalar of the `S` jobs. -/
noncomputable def cS (F : AvgCaseTI.FieldPres) : ℂ :=
  ((Real.sqrt 2 : ℂ))⁻¹ ^ bitsPerSymbol F * (Real.sqrt ((Fintype.card F.F : ℝ) - 1) : ℂ)





open Classical in
/-- The repeat-until-success job of a resource register: value `< p`. -/
noncomputable def rJob (F : AvgCaseTI.FieldPres) (r : Res n) : RJob n :=
  ⟨r.k, r.w, fun bits => decide (bitsVal bits < F.p)⟩

/-- The scalar of a resource job. -/
noncomputable def cR (F : AvgCaseTI.FieldPres) (k : ℕ) : ℂ :=
  ((Real.sqrt 2 : ℂ))⁻¹ ^ k * (Real.sqrt F.p : ℂ)



end SymEnc

end OPI
end

-- ===== OPI.PrepAll =====
section

/-!
# The state after the repeat-until-success stages

The jobs run pivots, then resources, then `S`; the state is, up to an explicit scalar,
`Σ_a |vPiv a⟩_R ⊗ RSall (J (⊗ gA β))`.
-/

namespace OPI

open QAlgorithms TwoFoldOPI

variable {n : ℕ}

/-- `g` vanishes unless wire `q` is clear. -/
def OffW (g : Qubits n → ℂ) (q : Fin n) : Prop := ∀ z, g z ≠ 0 → z q = false

















namespace SymEnc

variable {F : AvgCaseTI.FieldPres} {m kd : ℕ}

set_option hygiene false in
local notation "L" => bitsPerSymbol F



open Classical in
/-- The repeat-until-success job of a pivot register: valid. -/
noncomputable def pJob (Rr : Fin m → (Fin L ↪ Fin n)) (piv : Fin kd → Fin m) (j : Fin kd) : RJob n :=
  ⟨L, Rr (piv j), fun bits => decide (Fq.Valid F (toQ F bits))⟩



section RusState

variable {b t : ℕ} {reg : Fin m × Bool × Fin L ↪ Fin n} (D : RealDec F reg b t)

/-- All resource factors. -/
noncomputable def resAll : List (Res n) := (List.finRange m).flatMap (resC D)



/-- All jobs: pivots, then resources, then `S`. -/
noncomputable def allJobs (Rr : Fin m → (Fin L ↪ Fin n)) (piv : Fin kd → Fin m) (β : Fin m → F.F) :
    List (RJob n) :=
  (List.finRange kd).map (pJob Rr piv) ++ (resAll D).map (rJob F) ++ (List.finRange m).map (sJob reg β)

/-- The scalar of all jobs. -/
noncomputable def cAll (kd : ℕ) : ℂ :=
  (((Real.sqrt 2 : ℂ))⁻¹ ^ L) ^ kd * ((resAll D).map fun r => cR F r.k).prod * cS F ^ m



end RusState

end SymEnc

end OPI
end

-- ===== OPI.PrepStages =====
section

/-!
# The linear-map and phase stages of the preparation, and the reindexing onto `D`
-/

namespace OPI

open QAlgorithms TwoFoldOPI

variable {n b : ℕ}

/-- Splitting the layout `n + b`. -/
def splitNB : Qubits n × Qubits b ≃ Qubits (n + b) :=
  (Equiv.sumArrowEquivProdArrow (Fin n) (Fin b) Bool).symm.trans
    (Equiv.arrowCongr finSumFinEquiv (Equiv.refl Bool))















namespace SymEnc

variable {F : AvgCaseTI.FieldPres} {m kd : ℕ}

set_option hygiene false in
local notation "L" => bitsPerSymbol F

section Stages

variable {t : ℕ} {reg : Fin m × Bool × Fin L ↪ Fin n} (D : RealDec F reg b t)
  (Rr : Fin m → (Fin L ↪ Fin n)) (hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')
  (piv : Fin kd → Fin m) (hpivi : Function.Injective piv)

/-- `g` vanishes unless the listed wires are clear. -/
def OffL (g : Qubits n → ℂ) (qs : List (Fin n)) : Prop := ∀ q ∈ qs, OffW g q

/-- The unphased inner state. -/
noncomputable def Y0 (β : Fin m → F.F) : Qubits n → ℂ := RSall D (J reg (elemBits F) (prodF (gA β)))















end Stages

end SymEnc

end OPI
end

-- ===== OPI.PrepNorm =====
section

/-!
# Normalization facts for the prepared state, and the reindexing onto `D`
-/

namespace OPI

open QAlgorithms TwoFoldOPI

variable {n : ℕ}







namespace SymEnc

variable {F : AvgCaseTI.FieldPres} {m kd b t : ℕ}

set_option hygiene false in
local notation "L" => bitsPerSymbol F

section Norm

variable {reg : Fin m × Bool × Fin L ↪ Fin n} (D : RealDec F reg b t)



lemma resAll_pairwise : (resAll D).Pairwise Res.Disj := by
  unfold resAll
  rw [List.pairwise_flatMap]
  refine ⟨fun i _ => ?_, ?_⟩
  · unfold resC
    rw [List.pairwise_append]
    exact ⟨resQ_pairwise _, resQ_pairwise _, fun r hr r' hr' =>
      D.hres i false i true (by simp) r hr r' hr'⟩
  · refine (List.nodup_finRange m).pairwise_of_forall_ne (fun i _ i' _ hii r hr r' hr' => ?_)
    simp only [resC, List.mem_append] at hr hr'
    rcases hr with hr | hr <;> rcases hr' with hr' | hr' <;>
      exact D.hres _ _ _ _ (by simp [hii]) r hr r' hr'







end Norm



end SymEnc

end OPI
end

-- ===== OPI.PrepLaw =====
section

/-!
# The full preparation law

From `|0⟩ ⊗ grad` the preparation (repeat-until-success stages, the linear map `R ↦ R G`, the table
phase) reaches, with weight `W · |cAll|² |D|` and phase error `2 m (2π / 2^b)` times that weight,
`Σ_{d ∈ D} |d⟩_R ⊗ ψ_d ⊗ grad` with `ψ_d = |D|^{-1/2} RSall (J (⊗ g0 β d))`.
-/

namespace OPI

open QAlgorithms TwoFoldOPI

variable {n b : ℕ}







namespace SymEnc

variable {F : AvgCaseTI.FieldPres} {m t : ℕ}

set_option hygiene false in
local notation "L" => bitsPerSymbol F

/-- **The layout of the preparation.** -/
structure PrepLay {reg : Fin m × Bool × Fin L ↪ Fin n} (D : RealDec F reg b t) (kd : ℕ) where
  Rr : Fin m → (Fin L ↪ Fin n)
  hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j'
  piv : Fin kd → Fin m
  hpivi : Function.Injective piv
  G : Fin kd → Fin m → F.F
  hpiv : ∀ j j', G j (piv j') = if j = j' then 1 else 0
  fl : Fin n
  f0 : Fin n
  asR : List (Fin n)
  Z : List (Fin n)
  asL : List (Fin n)
  fL : Fin n
  scr : List (Fin n)
  asP : List (Fin n)
  fP : Fin n
  hRreg : ∀ i j p, reg p ≠ Rr i j
  hRres : ∀ r ∈ resAll D, ∀ i j, Rr i j ∉ Set.range r.w
  hjob : ∀ β, ∀ j ∈ allJobs D Rr piv β, (List.ofFn j.w ++ [fl] ++ asR ++ [f0]).Nodup ∧ j.k ≤ asR.length + 2
  hjpair : ∀ β, ((allJobs D Rr piv β).map RJob.res).Pairwise Res.Disj
  hndL : ∀ p : Fin kd × Fin m, (∀ j', piv j' ≠ p.2) → (List.ofFn (Rr (piv p.1)) ++ List.ofFn (Rr p.2) ++ Z ++ asL ++ [fL]).Nodup
  hZ : L = Z.length
  hlenL : L + L ≤ asL.length + 2
  hscL : ∀ i j, Rr i j ≠ fL ∧ (∀ q ∈ Z, Rr i j ≠ q) ∧ ∀ q ∈ asL, Rr i j ≠ q
  hLoff : ∀ q ∈ fL :: asL ++ Z, (∀ p, reg p ≠ q) ∧ ∀ r ∈ resAll D, q ∉ Set.range r.w
  hsl : scr.length = b
  hscr : scr.Nodup
  hbl : 1 + b ≤ asP.length + 2
  hxl : L + L ≤ asP.length + 2
  hndP : ∀ i, (List.ofFn (Rr i) ++ List.ofFn (bReg reg i false) ++ scr ++ asP ++ [fP]).Nodup
  hPoff : ∀ q ∈ scr ++ asP ++ [fP], (∀ p, reg p ≠ q) ∧ (∀ r ∈ resAll D, q ∉ Set.range r.w) ∧ ∀ i j, Rr i j ≠ q

variable {reg : Fin m × Bool × Fin L ↪ Fin n} {D : RealDec F reg b t} {kd : ℕ}

/-- The preparation program. -/
noncomputable def PrepLay.pre {c out : ℕ} (X : PrepLay D kd) (β : Fin m → F.F) (dst : Fin c) (R : ℕ)
    (P : Prog (n + b) c out) : Prog (n + b) c out :=
  rusChain X.fl X.f0 X.asR dst R (allJobs D X.Rr X.piv β)
    ((circSeg (relocCirc sysEmb (revCirc (linCirc X.Rr X.piv X.G X.Z X.asL X.fL)))).prog
      ((circSeg (phCirc reg X.Rr (b := b) X.scr X.asP X.fP (List.finRange m))).prog P))

/-- The weight of the repeat-until-success stages. -/
noncomputable def PrepLay.W (X : PrepLay D kd) (β : Fin m → F.F) (R : ℕ) : ℝ :=
  ((allJobs D X.Rr X.piv β).map fun j => RJob.wt (b := b) j R).prod

/-- The normalized target states. -/
noncomputable def psiN (D : RealDec F reg b t) (Ds : Finset (Fin m → F.F)) (β d : Fin m → F.F) : Qubits n → ℂ :=
  ((Real.sqrt Ds.card)⁻¹ : ℂ) • RSall D (J reg (elemBits F) (prodF (g0 (F := F) β d)))





end SymEnc

end OPI
end

-- ===== OPI.SerI =====
section

/-!
# First-order nodes for the serializer

Every node code of `programNodeTable` has the form `serializeWords (tag :: fields ++ rs)`, where
`rs` are the table indices of the children. A node is therefore represented by the first-order
triple `(tag, fields, children)` (`INode`), and the memoized traversal `trav` is computed by the
uniform traversal `travI` on such triples.
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI QAlgorithms.Complexity

/-- A first-order node: tag, fields, children (DAG indices). -/
abbrev INode := ℕ × List ℕ × List ℕ

/-- The code of a node whose children have table indices `rs`. -/
def codeI (nd : INode) (rs : List ℕ) : Str := serializeWords (nd.1 :: (nd.2.1 ++ rs))

/-- The node read at a missing index. -/
def failI : INode := (1, [], [])

lemma serializeWords_append (a b : List ℕ) :
    serializeWords (a ++ b) = serializeWords a ++ serializeWords b := by
  simp [serializeWords]

lemma serializeWords_cons (k : ℕ) (a : List ℕ) :
    serializeWords (k :: a) = encNat k ++ serializeWords a := by
  simp [serializeWords]

@[simp] lemma serializeWords_nil : serializeWords [] = [] := rfl



/-- The uniform memoized traversal. -/
def travI (dag : List INode) (i : ℕ) (memo : ℕ → Option ℕ) (T : List Str) : TravRes :=
  match memo i with
  | some k => (k, T, memo)
  | none =>
    let nd := dag[i]?.getD failI
    let r : List ℕ × List Str × (ℕ → Option ℕ) := nd.2.2.foldl (fun acc j =>
      if j < i then
        let t := travI dag j acc.2.2 acc.2.1
        (acc.1 ++ [t.1], t.2.1, t.2.2)
      else
        let u := internProgramNode failCode acc.2.1
        (acc.1 ++ [u.1], u.2, acc.2.2)) ([], T, memo)
    let res := internProgramNode (codeI nd r.1) r.2.1
    (res.1, res.2, Function.update r.2.2 i (some res.1))
termination_by i
decreasing_by all_goals assumption

section ToI
variable {N c out : ℕ}

open Classical in
/-- The first-order form of a node. -/
noncomputable def toI : Node N c out → INode
  | .halt D _ => (0, [D.gates.length] ++ D.gates.flatMap (fun g => [Learning.boolOpCode g.op, g.a, g.b]) ++
      List.ofFn D.outputs, [])
  | .fail => (1, [], [])
  | .gate g j => (2, (if g.gate = Gate.ofMatrix1 hadamard then 0
      else if g.gate = Gate.ofMatrix1 gateT then 1 else 2) :: List.ofFn (fun i => (g.wires i).val), [j])
  | .measure q dst j0 j1 => (4, [q.val, dst.val], [j0, j1])
  | .prepare q j => (5, [q.val], [j])
  | .coin dst j0 j1 => (6, [dst.val], [j0, j1])
  | .setBit dst b j => (7, [dst.val, if b then 1 else 0], [j])
  | .boolean op dst x y j => (8, [Learning.boolOpCode op, dst.val, x.val, y.val], [j])
  | .branch src j0 j1 => (9, [src.val], [j0, j1])





end ToI

end OPI
end

-- ===== OPI.DFS =====
section

/-!
# The memoized traversal as an explicit-stack machine

`stepM` performs one step of a depth-first traversal with an explicit stack of frames
`(node, next child position, child results)`, a memo list and the code table. Iterating it
`fuelM dag root` times from the initial state computes `travI dag root`.
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI QAlgorithms.Complexity

abbrev Frame := ℕ × ℕ × List ℕ
abbrev MState := List Frame × List (Option ℕ) × List Str × ℕ

/-- Hand a child result to the parent frame. -/
def deliver (k : ℕ) : List Frame → List Frame
  | [] => []
  | (i, ph, rs) :: S => (i, ph, rs ++ [k]) :: S

/-- The memo list as a function. -/
def mf (memo : List (Option ℕ)) (j : ℕ) : Option ℕ := memo.getD j none

/-- One step of the traversal. -/
def stepM (dag : List INode) : MState → MState
  | ([], s) => ([], s)
  | ((i, ph, rs) :: S, memo, T, res) =>
    match (if ph = 0 then mf memo i else none) with
    | some k => (deliver k S, memo, T, k)
    | none =>
      match (dag.getD i failI).2.2[ph]? with
      | some j =>
        if j < i then ((j, 0, []) :: (i, ph + 1, rs) :: S, memo, T, res)
        else ((i, ph + 1, rs ++ [(internProgramNode failCode T).1]) :: S, memo,
          (internProgramNode failCode T).2, res)
      | none =>
        ((deliver (internProgramNode (codeI (dag.getD i failI) rs) T).1 S),
          memo.set i (some (internProgramNode (codeI (dag.getD i failI) rs) T).1),
          (internProgramNode (codeI (dag.getD i failI) rs) T).2,
          (internProgramNode (codeI (dag.getD i failI) rs) T).1)

/-- The number of unset memo entries. -/
def nones (memo : List (Option ℕ)) : ℕ := memo.count none

lemma mf_set (memo : List (Option ℕ)) (i : ℕ) (v : Option ℕ) (hi : i < memo.length) :
    mf (memo.set i v) = Function.update (mf memo) i v := by
  funext j
  unfold mf
  by_cases h : j = i
  · subst h; simp [List.getD_eq_getElem?_getD, hi]
  · rw [Function.update_of_ne h]
    simp only [List.getD_eq_getElem?_getD, List.getElem?_set, Ne.symm h, if_false]

lemma nones_set (k : ℕ) : ∀ (memo : List (Option ℕ)) (i : ℕ), i < memo.length →
    mf memo i = none → nones (memo.set i (some k)) + 1 = nones memo := by
  intro memo
  induction memo with
  | nil => intro i hi; simp at hi
  | cons x xs ih =>
    intro i hi hn
    cases i with
    | zero =>
      have hx : x = none := by simpa [mf] using hn
      subst hx
      simp [nones, List.count_cons]
    | succ i =>
      have := ih i (by simpa using hi) (by simpa [mf] using hn)
      simp only [nones, List.set_cons_succ, List.count_cons] at this ⊢
      omega

/-- The memoized traversal only changes the memo at indices `≤ i`. -/
lemma travI_memo_of_gt (dag : List INode) (i : ℕ) :
    ∀ memo T l, i < l → (travI dag i memo T).2.2 l = memo l := by
  induction i using Nat.strong_induction_on with
  | _ i IH =>
  intro memo T l hl
  rw [travI]
  cases hm : memo i with
  | some k => rfl
  | none =>
    simp only
    rw [Function.update_of_ne (by omega)]
    generalize (dag[i]?.getD failI).2.2 = cs
    suffices h : ∀ (cs : List ℕ) (acc : List ℕ × List Str × (ℕ → Option ℕ)), acc.2.2 l = memo l →
        (cs.foldl (fun acc j => if j < i then
          ((acc.1 ++ [(travI dag j acc.2.2 acc.2.1).1], (travI dag j acc.2.2 acc.2.1).2.1,
            (travI dag j acc.2.2 acc.2.1).2.2))
          else (acc.1 ++ [(internProgramNode failCode acc.2.1).1], (internProgramNode failCode acc.2.1).2,
            acc.2.2)) acc).2.2 l = memo l from h cs _ rfl
    intro cs
    induction cs with
    | nil => intro acc h; exact h
    | cons j cs ih =>
      intro acc h
      rw [List.foldl_cons]
      apply ih
      split
      · rename_i hj; simp only; rw [IH j hj _ _ l (by omega)]; exact h
      · exact h

section Run
variable (dag : List INode) (W : ℕ) (hW : ∀ nd ∈ dag, 2 * nd.2.2.length ≤ W)
include hW

lemma children_le (i : ℕ) : 2 * (dag.getD i failI).2.2.length ≤ W := by
  rw [List.getD_eq_getElem?_getD]
  cases h : dag[i]? with
  | none => simp [failI]
  | some nd => exact hW nd (List.mem_of_getElem? h)

/-- **One node.** -/
theorem run_node (i : ℕ) : ∀ (S : List Frame) (memo : List (Option ℕ)) (T : List Str) (res : ℕ),
    i < memo.length →
    ∃ n memo', memo'.length = memo.length ∧ mf memo' = (travI dag i (mf memo) T).2.2 ∧
      (stepM dag)^[n] ((i, 0, []) :: S, memo, T, res) =
        (deliver (travI dag i (mf memo) T).1 S, memo', (travI dag i (mf memo) T).2.1,
          (travI dag i (mf memo) T).1) ∧
      n + (W + 2) * nones memo' ≤ (W + 2) * nones memo + 1 := by
  induction i using Nat.strong_induction_on with
  | _ i IH =>
  intro S memo T res hi
  cases hm : mf memo i with
  | some k =>
    refine ⟨1, memo, rfl, ?_, ?_, by omega⟩
    · rw [travI, hm]
    · rw [travI, hm]
      simp only [Function.iterate_one, stepM, if_pos, hm]
  | none =>
    -- the children loop
    have loop : ∀ (cs : List ℕ) (ph : ℕ) (rs : List ℕ) (memo : List (Option ℕ)) (T : List Str) (res : ℕ),
        memo.length > i → mf memo i = none → (dag.getD i failI).2.2.drop ph = cs →
        ∃ n memo' res', memo'.length = memo.length ∧ mf memo' i = none ∧
          let r := cs.foldl (fun acc j => if j < i then
            ((acc.1 ++ [(travI dag j acc.2.2 acc.2.1).1], (travI dag j acc.2.2 acc.2.1).2.1,
              (travI dag j acc.2.2 acc.2.1).2.2))
            else (acc.1 ++ [(internProgramNode failCode acc.2.1).1], (internProgramNode failCode acc.2.1).2,
              acc.2.2)) (rs, T, mf memo)
          mf memo' = r.2.2 ∧
          (stepM dag)^[n] ((i, ph, rs) :: S, memo, T, res) =
            ((i, ph + cs.length, r.1) :: S, memo', r.2.1, res') ∧
          n + (W + 2) * nones memo' ≤ (W + 2) * nones memo + 2 * cs.length := by
      intro cs
      induction cs with
      | nil =>
        intro ph rs memo T res hl hmi _
        exact ⟨0, memo, res, rfl, hmi, rfl, by simp, by simp⟩
      | cons j cs ih =>
        intro ph rs memo T res hl hmi hd
        have hj : (dag.getD i failI).2.2[ph]? = some j := by
          rw [← List.head?_drop, hd]; rfl
        have hd' : (dag.getD i failI).2.2.drop (ph + 1) = cs := by
          rw [← List.drop_drop, hd]; rfl
        have hcheck : (if ph = 0 then mf memo i else none) = none := by split <;> simp [hmi]
        by_cases hji : j < i
        · -- push the child, run it, continue
          have s1 : stepM dag ((i, ph, rs) :: S, memo, T, res) =
              ((j, 0, []) :: (i, ph + 1, rs) :: S, memo, T, res) := by
            simp only [stepM, hcheck, hj, hji, if_true]
          obtain ⟨n1, memo1, hl1, hmf1, hrun1, hb1⟩ := IH j hji ((i, ph + 1, rs) :: S) memo T res (by omega)
          have hmi1 : mf memo1 i = none := by
            rw [hmf1, travI_memo_of_gt dag j _ _ i hji]; exact hmi
          obtain ⟨n2, memo2, res2, hl2, hmi2, hmf2, hrun2, hb2⟩ :=
            ih (ph + 1) (rs ++ [(travI dag j (mf memo) T).1]) memo1 (travI dag j (mf memo) T).2.1
              (travI dag j (mf memo) T).1 (by omega) hmi1 hd'
          refine ⟨n2 + n1 + 1, memo2, res2, by omega, hmi2, ?_, ?_, ?_⟩
          · rw [hmf2, hmf1, List.foldl_cons]; simp only [hji, if_true]
          · rw [Function.iterate_add_apply, Function.iterate_add_apply, Function.iterate_one, s1, hrun1]
            simp only [deliver]
            rw [hrun2, hmf1]
            simp only [List.foldl_cons, hji, if_true, List.length_cons]
            rw [show ph + 1 + cs.length = ph + (cs.length + 1) by omega]
          · simp only [List.length_cons]; omega
        · -- a child that is not earlier: intern the failure code
          have s1 : stepM dag ((i, ph, rs) :: S, memo, T, res) =
              ((i, ph + 1, rs ++ [(internProgramNode failCode T).1]) :: S, memo,
                (internProgramNode failCode T).2, res) := by
            simp only [stepM, hcheck, hj, hji, if_false]
          obtain ⟨n2, memo2, res2, hl2, hmi2, hmf2, hrun2, hb2⟩ :=
            ih (ph + 1) (rs ++ [(internProgramNode failCode T).1]) memo (internProgramNode failCode T).2
              res hl hmi hd'
          refine ⟨n2 + 1, memo2, res2, hl2, hmi2, ?_, ?_, ?_⟩
          · rw [hmf2, List.foldl_cons]; simp only [hji, if_false]
          · rw [Function.iterate_add_apply, Function.iterate_one, s1, hrun2]
            simp only [List.foldl_cons, hji, if_false, List.length_cons]
            rw [show ph + 1 + cs.length = ph + (cs.length + 1) by omega]
          · simp only [List.length_cons]; omega
    obtain ⟨n1, memo1, res1, hl1, hmi1, hmf1, hrun1, hb1⟩ :=
      loop (dag.getD i failI).2.2 0 [] memo T res hi hm (by simp)
    set r := (dag.getD i failI).2.2.foldl (fun acc j => if j < i then
            ((acc.1 ++ [(travI dag j acc.2.2 acc.2.1).1], (travI dag j acc.2.2 acc.2.1).2.1,
              (travI dag j acc.2.2 acc.2.1).2.2))
            else (acc.1 ++ [(internProgramNode failCode acc.2.1).1], (internProgramNode failCode acc.2.1).2,
              acc.2.2)) ([], T, mf memo) with hr
    have htrav : travI dag i (mf memo) T =
        ((internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1,
          (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).2,
          Function.update r.2.2 i (some (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1)) := by
      rw [travI, hm, hr, List.getD_eq_getElem?_getD]
    have hnone : (dag.getD i failI).2.2[0 + (dag.getD i failI).2.2.length]? = none := by simp
    have s2 : stepM dag ((i, 0 + (dag.getD i failI).2.2.length, r.1) :: S, memo1, r.2.1, res1) =
        (deliver (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1 S,
          memo1.set i (some (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1),
          (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).2,
          (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1) := by
      have hc : (if 0 + (dag.getD i failI).2.2.length = 0 then mf memo1 i else none) = none := by
        split <;> simp [hmi1]
      simp only [stepM, hc, hnone]
    have hcw := children_le dag W hW i
    have hns := nones_set (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1 memo1 i
      (by omega) hmi1
    refine ⟨1 + n1, memo1.set i (some (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1),
      by simp [hl1], ?_, ?_, ?_⟩
    · rw [mf_set _ _ _ (by omega), htrav, hmf1]
    · rw [Function.iterate_add_apply, hrun1, Function.iterate_one, s2, htrav]
    · have : (W + 2) * nones memo1 = (W + 2) * nones (memo1.set i
          (some (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1)) + (W + 2) := by
        rw [← hns]; ring
      omega

end Run

/-- The step bound for a DAG. -/
def wM (dag : List INode) : ℕ := 2 * (dag.flatMap (fun nd => nd.2.2)).length

lemma wM_spec (dag : List INode) : ∀ nd ∈ dag, 2 * nd.2.2.length ≤ wM dag := by
  intro nd hnd
  unfold wM
  have : nd.2.2.length ≤ (dag.flatMap (fun nd => nd.2.2)).length := by
    rw [List.length_flatMap]
    exact List.le_sum_of_mem (List.mem_map.mpr ⟨nd, hnd, rfl⟩)
  omega

/-- The fuel of the machine. -/
def fuelM (dag : List INode) (root : ℕ) : ℕ := (wM dag + 2) * (root + 1) + 1

/-- The initial state. -/
def initM (root : ℕ) : MState := ([(root, 0, [])], List.replicate (root + 1) none, [], 0)

lemma stepM_nil (dag : List INode) (s : List (Option ℕ) × List Str × ℕ) (n : ℕ) :
    (stepM dag)^[n] ([], s) = ([], s) := by
  induction n with
  | zero => rfl
  | succ n ih => rw [Function.iterate_succ_apply', ih]; rfl

/-- **The machine computes the traversal.** -/
theorem run_root (dag : List INode) (root : ℕ) :
    ((stepM dag)^[fuelM dag root] (initM root)).2.2.1 = (travI dag root (fun _ => none) []).2.1 ∧
    ((stepM dag)^[fuelM dag root] (initM root)).2.2.2 = (travI dag root (fun _ => none) []).1 := by
  have hmf : mf (List.replicate (root + 1) none) = fun _ => none := by
    funext j; unfold mf; rw [List.getD_eq_getElem?_getD]
    cases h : (List.replicate (root + 1) (none : Option ℕ))[j]? with
    | none => rfl
    | some v => simp only [List.getElem?_replicate] at h; split at h <;> simp_all
  obtain ⟨n, memo', hl, hmf', hrun, hb⟩ := run_node dag (wM dag) (wM_spec dag) root [] (List.replicate (root + 1) none) [] 0 (by simp)
  rw [hmf] at hrun
  have hnn : nones (List.replicate (root + 1) (none : Option ℕ)) = root + 1 := by
    simp [nones, List.count_replicate]
  have hle : n ≤ fuelM dag root := by
    unfold fuelM; rw [hnn] at hb
    have : 0 ≤ (wM dag + 2) * nones memo' := Nat.zero_le _
    omega
  obtain ⟨d, hd⟩ := Nat.exists_eq_add_of_le hle
  unfold initM
  rw [hd, Nat.add_comm, Function.iterate_add_apply, hrun]
  simp [deliver, stepM_nil]

end OPI
end

-- ===== OPI.PR =====
section

/-!
# Polynomial realizers

An OAI `Realizer` bundled with a monotone polynomial bound on its charge and on the volume of
its output (both as functions of the input volume). The combinators compute the bounds, so a
generator assembled from them is polynomial by construction.
-/

namespace OPI.W6

open OAI.ThreeMachine.StackCompiler

/-- Monotone functions with a polynomial upper bound. -/
def Poly (T : ℕ → ℕ) : Prop := Monotone T ∧ ∃ c d : ℕ, ∀ n, T n ≤ c * (n + 1) ^ d

namespace Poly



lemma const (k : ℕ) : Poly (fun _ => k) :=
  ⟨fun _ _ _ => le_rfl, k, 0, fun n => by simp⟩

lemma id : Poly (fun n => n) :=
  ⟨fun _ _ h => h, 1, 1, fun n => by simp⟩

lemma add {T S : ℕ → ℕ} (hT : Poly T) (hS : Poly S) : Poly (fun n => T n + S n) := by
  obtain ⟨mT, c, d, h⟩ := hT
  obtain ⟨mS, c', d', h'⟩ := hS
  refine ⟨fun a b hab => Nat.add_le_add (mT hab) (mS hab), c + c', d + d', fun n => ?_⟩
  have e1 : (n + 1) ^ d ≤ (n + 1) ^ (d + d') := Nat.pow_le_pow_right (by omega) (by omega)
  have e2 : (n + 1) ^ d' ≤ (n + 1) ^ (d + d') := Nat.pow_le_pow_right (by omega) (by omega)
  calc T n + S n ≤ c * (n + 1) ^ d + c' * (n + 1) ^ d' := Nat.add_le_add (h n) (h' n)
    _ ≤ c * (n + 1) ^ (d + d') + c' * (n + 1) ^ (d + d') :=
        Nat.add_le_add (Nat.mul_le_mul_left _ e1) (Nat.mul_le_mul_left _ e2)
    _ = (c + c') * (n + 1) ^ (d + d') := by ring

lemma mul {T S : ℕ → ℕ} (hT : Poly T) (hS : Poly S) : Poly (fun n => T n * S n) := by
  obtain ⟨mT, c, d, h⟩ := hT
  obtain ⟨mS, c', d', h'⟩ := hS
  refine ⟨fun a b hab => Nat.mul_le_mul (mT hab) (mS hab), c * c', d + d', fun n => ?_⟩
  calc T n * S n ≤ (c * (n + 1) ^ d) * (c' * (n + 1) ^ d') := Nat.mul_le_mul (h n) (h' n)
    _ = c * c' * (n + 1) ^ (d + d') := by ring

lemma comp {T S : ℕ → ℕ} (hT : Poly T) (hS : Poly S) : Poly (fun n => S (T n)) := by
  obtain ⟨mT, c, d, h⟩ := hT
  obtain ⟨mS, c', d', h'⟩ := hS
  refine ⟨fun a b hab => mS (mT hab), c' * (c + 1) ^ d', d * d', fun n => ?_⟩
  have h1 : T n + 1 ≤ (c + 1) * (n + 1) ^ d := by
    have := h n
    have : 1 ≤ (n + 1) ^ d := Nat.one_le_pow _ _ (by omega)
    nlinarith
  calc S (T n) ≤ c' * (T n + 1) ^ d' := h' _
    _ ≤ c' * ((c + 1) * (n + 1) ^ d) ^ d' := Nat.mul_le_mul_left _ (Nat.pow_le_pow_left h1 _)
    _ = c' * (c + 1) ^ d' * (n + 1) ^ (d * d') := by rw [mul_pow, ← pow_mul]; ring

lemma smul (k : ℕ) {T : ℕ → ℕ} (hT : Poly T) : Poly (fun n => k * T n) :=
  (const k).mul hT

lemma succ {T : ℕ → ℕ} (hT : Poly T) : Poly (fun n => T n + 1) := hT.add (const 1)



lemma mono {T : ℕ → ℕ} (hT : Poly T) {a b : ℕ} (h : a ≤ b) : T a ≤ T b := hT.1 h

end Poly

variable {α β γ δ ε : Type} [Coding α] [Coding β] [Coding γ] [Coding δ] [Coding ε]

/-- A realizer with a polynomial bound on its charge and on its output volume. -/
structure PR (f : α → β) where
  R : Realizer f
  T : ℕ → ℕ
  poly : Poly T
  time_le : ∀ x, R.time x ≤ T (volume x)
  vol_le : ∀ x, volume (f x) ≤ T (volume x)

namespace PR

variable {f : α → β} {g : β → γ}



def congr {f' : α → β} (P : PR f) (h : ∀ x, f x = f' x) : PR f' :=
  ⟨P.R.congr h, P.T, P.poly, fun x => by rw [Realizer.time_congr]; exact P.time_le x,
    fun x => by rw [← h]; exact P.vol_le x⟩

def id : PR (fun x : α => x) :=
  ⟨Realizer.id, fun n => n + 2, Poly.id.add (Poly.const 2), fun x => by simp, fun x => by omega⟩

def fst : PR (Prod.fst : α × β → α) :=
  ⟨Realizer.fst, fun n => n + 2, Poly.id.add (Poly.const 2), fun x => by simp,
    fun x => by rcases x with ⟨a, b⟩; simp only [volume_pair]; omega⟩

def snd : PR (Prod.snd : α × β → β) :=
  ⟨Realizer.snd, fun n => n + 2, Poly.id.add (Poly.const 2), fun x => by simp,
    fun x => by rcases x with ⟨a, b⟩; simp only [volume_pair]; omega⟩

def reinterpret (f : α → β) (h : ∀ x, enc (f x) = enc x) : PR f :=
  ⟨Realizer.reinterpret f h, fun n => n + 2, Poly.id.add (Poly.const 2), fun x => by simp,
    fun x => by simp only [volume, h]; omega⟩

def const (b : β) : PR (fun _ : α => b) :=
  ⟨Realizer.constant b, fun n => (2 * volume b + 1) * (20 * n + (50 * volume b + 50)),
    Poly.smul _ ((Poly.smul 20 Poly.id).add (Poly.const _)),
    fun x => by
      change (2 * volume b + 1) * (20 * volume x + 50 * volume b + 50) ≤ _
      rw [Nat.add_assoc],
    fun x => by nlinarith⟩

def comp (P : PR f) (Q : PR g) : PR (fun x => g (f x)) :=
  ⟨P.R.comp Q.R, fun n => P.T n + Q.T (P.T n) + 10 * (P.T n + 1),
    (P.poly.add (P.poly.comp Q.poly)).add (Poly.smul 10 P.poly.succ),
    fun x => by
      rw [Realizer.time_comp]
      have h1 := P.time_le x
      have h2 := P.vol_le x
      have h3 := Q.time_le (f x)
      have h4 := Q.poly.mono h2
      omega,
    fun x => (Q.vol_le (f x)).trans (Q.poly.mono (P.vol_le x)) |>.trans (by omega)⟩

def pair {g : α → γ} (P : PR f) (Q : PR g) : PR (fun x => (f x, g x)) :=
  ⟨P.R.pair Q.R, fun n => P.T n + Q.T n + 20 * (n + P.T n + Q.T n + 1),
    (P.poly.add Q.poly).add (Poly.smul 20 (((Poly.id.add P.poly).add Q.poly).succ)),
    fun x => by
      rw [Realizer.time_pair]
      have := P.time_le x; have := Q.time_le x; have := P.vol_le x; have := Q.vol_le x
      omega,
    fun x => by
      simp only [volume_pair]
      have := P.vol_le x; have := Q.vol_le x
      omega⟩



def nil : PR (fun _ : α => ([] : List β)) := (const ([] : List β)).congr (fun _ => rfl)

def cons : PR (fun x : α × List α => x.1 :: x.2) := reinterpret _ (fun _ => rfl)


/-! ### Folds -/

lemma foldTime_le' {F : α × β → β} (R : Realizer F) (T V : ℕ) :
    ∀ (xs : List α) (b : β),
      (∀ k, volume ((xs.take k).foldl (fun b a => F (a, b)) b) ≤ V) →
      (∀ a ∈ xs, ∀ k, R.time (a, (xs.take k).foldl (fun b a => F (a, b)) b) ≤ T) →
      Realizer.foldTime R b xs ≤ xs.length * (T + 20 * (volume xs + 2 * V + 1)) + 1
  | [], b, _, _ => by simp [Realizer.foldTime]
  | a :: xs, b, hV, hT => by
    have ih := foldTime_le' R T V xs (F (a, b))
      (fun k => by simpa using hV (k + 1))
      (fun a' ha' k => by simpa using hT a' (List.mem_cons_of_mem _ ha') (k + 1))
    have h0 := hV 0
    have h1 := hV 1
    have ht := hT a (List.mem_cons_self) 0
    simp only [List.take_zero, List.foldl_nil, List.take_succ_cons, List.foldl_cons] at h0 h1 ht
    simp only [Realizer.foldTime, List.length_cons, volume_cons] at ih ⊢
    have hx : xs.length * (T + 20 * (volume xs + 2 * V + 1)) ≤
        xs.length * (T + 20 * (volume a + volume xs + 1 + 2 * V + 1)) :=
      Nat.mul_le_mul_left _ (by omega)
    nlinarith

/-- Folds, given a polynomial bound `G` on all intermediate accumulators. -/
def fold {F : α × β → β} (P : PR F) (G : ℕ → ℕ) (hG : Poly G)
    (hacc : ∀ (xs : List α) (b : β) k,
      volume ((xs.take k).foldl (fun b a => F (a, b)) b) ≤ G (volume (xs, b))) :
    PR (fun x : List α × β => x.1.foldl (fun b a => F (a, b)) x.2) :=
  ⟨P.R.fold, fun n => 2 * n + 6 + (n * (P.T (n + G n + 1) + 20 * (n + 2 * G n + 1)) + 1) + G n,
    ((((Poly.smul 2 Poly.id).add (Poly.const 6)).add
      ((Poly.id.mul ((((Poly.id.add hG).succ).comp P.poly).add
        (Poly.smul 20 ((Poly.id.add (Poly.smul 2 hG)).succ)))).succ)).add hG),
    fun x => by
      rcases x with ⟨xs, b⟩
      rw [Realizer.time_fold]
      have hl : xs.length ≤ volume (xs, b) := by
        have : xs.length ≤ volume xs := by
          clear hacc; induction xs with
          | nil => simp
          | cons a xs ih => simp only [List.length_cons, volume_cons]; have := volume_pos a; omega
        simp only [volume_pair]; omega
      have hxs : volume xs ≤ volume (xs, b) := by simp only [volume_pair]; omega
      have key := foldTime_le' P.R (P.T (volume (xs, b) + G (volume (xs, b)) + 1)) (G (volume (xs, b)))
        xs b (fun k => hacc xs b k)
        (fun a ha k => by
          refine (P.time_le _).trans (P.poly.mono ?_)
          have hva : volume a ≤ volume xs := by
            obtain ⟨l1, l2, rfl⟩ := List.append_of_mem ha
            clear hacc hl hxs ha; induction l1 with
            | nil => simp only [List.nil_append, volume_cons]; omega
            | cons c l1 ih => simp only [List.cons_append, volume_cons]; omega
          have := hacc xs b k
          simp only [volume_pair] at this hxs ⊢; omega)
      generalize volume (xs, b) = n at *
      have e1 : xs.length * (P.T (n + G n + 1) + 20 * (volume xs + 2 * G n + 1)) ≤
          n * (P.T (n + G n + 1) + 20 * (n + 2 * G n + 1)) :=
        Nat.mul_le_mul hl (by omega)
      simp only at key ⊢
      omega,
    fun x => by
      rcases x with ⟨xs, b⟩
      have := hacc xs b xs.length
      rw [List.take_length] at this
      simp only
      omega⟩

/-- Accumulator bound for folds whose step adds at most `c (|a| + 1)` to the volume. -/
lemma hacc_add {F : α × β → β} (c : ℕ) (h : ∀ a b, volume (F (a, b)) ≤ volume b + c * (volume a + 1)) :
    ∀ (xs : List α) (b : β) k,
      volume ((xs.take k).foldl (fun b a => F (a, b)) b) ≤ (fun n => n + c * n) (volume (xs, b)) := by
  have key : ∀ (xs : List α) (b : β) k,
      volume ((xs.take k).foldl (fun b a => F (a, b)) b) + 1 ≤ volume b + c * volume xs + 1 := by
    intro xs
    induction xs with
    | nil => intro b k; simp
    | cons a xs ih =>
      intro b k
      cases k with
      | zero =>
        simp only [List.take_zero, List.foldl_nil, volume_cons]
        have : 0 ≤ c * (volume a + volume xs + 1) := Nat.zero_le _
        omega
      | succ k =>
        simp only [List.take_succ_cons, List.foldl_cons, volume_cons]
        have h1 := ih (F (a, b)) k
        have h2 := h a b
        have e : c * (volume a + volume xs + 1) = c * (volume a + 1) + c * volume xs := by ring
        rw [e]; omega
  intro xs b k
  have h1 := key xs b k
  simp only [volume_pair]
  have e : c * (volume xs + volume b + 1) = c * volume xs + c * (volume b + 1) := by ring
  rw [e]; omega

/-- Iteration, given a polynomial bound on all iterates. -/
def iterate {f : α → α} (P : PR f) (G : ℕ → ℕ) (hG : Poly G)
    (hacc : ∀ (m : ℕ) (a : α) j, j ≤ m → volume (f^[j] a) ≤ G (volume (m, a))) :
    PR (fun x : ℕ × α => f^[x.1] x.2) :=
  ⟨P.R.iterate, fun n => 10000 * ((n + 1) * (P.T (G n) + G n + n + 1)) + G n,
    ((Poly.smul 10000 (Poly.id.succ.mul ((((hG.comp P.poly).add hG).add Poly.id).succ))).add hG),
    fun x => by
      rcases x with ⟨m, a⟩
      have hm : m ≤ volume (m, a) := by simp only [volume_pair, volume_nat]; omega
      have := Realizer.time_iterate_le P.R m a (P.T (G (volume (m, a)))) (G (volume (m, a)))
        (fun j hj => (P.time_le _).trans (P.poly.mono (hacc m a j hj.le)))
        (fun j hj => hacc m a j hj)
      have e : (m + 1) * (P.T (G (volume (m, a))) + G (volume (m, a)) + m + 1) ≤
          (volume (m, a) + 1) * (P.T (G (volume (m, a))) + G (volume (m, a)) + volume (m, a) + 1) :=
        Nat.mul_le_mul (by omega) (by omega)
      rw [Nat.mul_assoc] at this
      show _ ≤ 10000 * ((volume (m, a) + 1) * _) + _
      omega,
    fun x => by
      rcases x with ⟨m, a⟩
      have := hacc m a m le_rfl
      simp only
      omega⟩


/-! ### Volume facts -/

lemma length_le_volume (xs : List α) : xs.length ≤ volume xs := by
  induction xs with
  | nil => simp
  | cons a xs ih => simp only [List.length_cons, volume_cons]; have := volume_pos a; omega

lemma volume_lt_of_mem {a : α} {xs : List α} (h : a ∈ xs) : volume a < volume xs := by
  induction xs with
  | nil => simp at h
  | cons b xs ih =>
    simp only [volume_cons]
    rcases List.mem_cons.mp h with rfl | h
    · omega
    · have := ih h; omega

/-! ### Choice -/

def choose {g : α → β} (P : PR f) (Q : PR g) : PR (fun x : Bool × α => if x.1 then f x.2 else g x.2) :=
  ⟨P.R.choose Q.R, fun n => (n + 2 + P.T n + 10 * (n + 1)) + (n + 2 + Q.T n + 10 * (n + 1)) +
      30 * (n + P.T n + Q.T n + 1),
    (((Poly.id.add (Poly.const 2)).add P.poly).add (Poly.smul 10 Poly.id.succ)).add
      (((Poly.id.add (Poly.const 2)).add Q.poly).add (Poly.smul 10 Poly.id.succ)) |>.add
      (Poly.smul 30 ((Poly.id.add P.poly).add Q.poly).succ),
    fun x => by
      rcases x with ⟨c, a⟩
      rw [Realizer.time_choose, Realizer.time_comp, Realizer.time_comp]
      simp only [Realizer.time_snd, volume_pair]
      have h1 := P.time_le a; have h2 := Q.time_le a; have h3 := P.vol_le a; have h4 := Q.vol_le a
      have hc := volume_bool c
      have m1 := P.poly.mono (show volume a ≤ volume c + volume a + 1 by omega)
      have m2 := Q.poly.mono (show volume a ≤ volume c + volume a + 1 by omega)
      omega,
    fun x => by
      rcases x with ⟨c, a⟩
      simp only [volume_pair]
      have h3 := P.vol_le a; have h4 := Q.vol_le a
      have m1 := P.poly.mono (show volume a ≤ volume c + volume a + 1 by omega)
      have m2 := Q.poly.mono (show volume a ≤ volume c + volume a + 1 by omega)
      split_ifs <;> omega⟩

def ite {p : α → Bool} {g : α → β} (Pp : PR p) (P : PR f) (Q : PR g) :
    PR (fun x => if p x then f x else g x) :=
  ((Pp.pair id).comp (P.choose Q)).congr (fun _ => rfl)

/-! ### Map -/

def map {f : α × γ → β} (P : PR f) : PR (fun x : List α × γ => x.1.map (fun a => f (a, x.2))) :=
  ⟨(Uniform.map (P.R.uniform Unit)).specialize (),
    fun n => 30000 * ((n + 1) * (P.T n + n + n + (n * (P.T n + 1) + 1) + 1)) + (n * (P.T n + 1) + 1),
    (Poly.smul 30000 (Poly.id.succ.mul
      ((((P.poly.add Poly.id).add Poly.id).add (Poly.id.mul P.poly.succ).succ).succ))).add
      (Poly.id.mul P.poly.succ).succ,
    fun x => by
      rcases x with ⟨xs, e⟩
      have hb : ∀ a ∈ xs, volume (a, e) ≤ volume (xs, e) := fun a ha => by
        have := volume_lt_of_mem ha; simp only [volume_pair]; omega
      have hT : ∀ a ∈ xs, (P.R.uniform Unit).time () (a, e) ≤ P.T (volume (xs, e)) := fun a ha => by
        rw [Uniform.time_uniform]; exact (P.time_le _).trans (P.poly.mono (hb a ha))
      have hm := Uniform.time_map (P.R.uniform Unit) () xs e _ hT
      have hv := volume_list_le (xs.map (fun a => f (a, e))) (P.T (volume (xs, e))) (fun b hb' => by
        obtain ⟨a, ha, rfl⟩ := List.mem_map.mp hb'
        exact (P.vol_le _).trans (P.poly.mono (hb a ha)))
      have hl := length_le_volume xs
      simp only [List.length_map] at hv
      have hm' : ((Uniform.map (P.R.uniform Unit)).specialize ()).time (xs, e) ≤ _ := hm
      clear hm
      generalize hn : volume (xs, e) = n at *
      have hxe : volume xs + volume e + 1 = n := by rw [← hn, volume_pair]
      have e1 : 30000 * (xs.length + 1) * (P.T n + volume xs + volume e +
          volume (xs.map (fun a => f (a, e))) + 1) ≤
          30000 * ((n + 1) * (P.T n + n + n + (n * (P.T n + 1) + 1) + 1)) := by
        rw [Nat.mul_assoc]
        refine Nat.mul_le_mul_left _ (Nat.mul_le_mul (by omega) ?_)
        have : xs.length * (P.T n + 1) ≤ n * (P.T n + 1) := Nat.mul_le_mul_right _ (by omega)
        omega
      omega,
    fun x => by
      rcases x with ⟨xs, e⟩
      have hb : ∀ a ∈ xs, volume (a, e) ≤ volume (xs, e) := fun a ha => by
        have := volume_lt_of_mem ha; simp only [volume_pair]; omega
      have hv := volume_list_le (xs.map (fun a => f (a, e))) (P.T (volume (xs, e))) (fun b hb' => by
        obtain ⟨a, ha, rfl⟩ := List.mem_map.mp hb'
        exact (P.vol_le _).trans (P.poly.mono (hb a ha)))
      have hl := length_le_volume xs
      simp only [List.length_map] at hv
      have : xs.length * (P.T (volume (xs, e)) + 1) ≤ volume (xs, e) * (P.T (volume (xs, e)) + 1) :=
        Nat.mul_le_mul_right _ (by simp only [volume_pair]; omega)
      simp only
      omega⟩

/-! ### List primitives -/

def revOnto : PR (fun x : List α × List α => x.1.foldl (fun b a => a :: b) x.2) :=
  ((cons : PR (fun x : α × List α => x.1 :: x.2)).fold (fun n => n + 1 * n)
    (Poly.id.add (Poly.smul 1 Poly.id))
    (hacc_add (F := fun x : α × List α => x.1 :: x.2) 1 (fun a b => by simp only [volume_cons]; omega))).congr (fun _ => rfl)

def reverse : PR (fun xs : List α => xs.reverse) :=
  ((id.pair (nil : PR (fun _ : List α => ([] : List α)))).comp revOnto).congr
    (fun xs => by simp only [Realizer.fold_cons_eq, List.append_nil])

def append : PR (fun x : List α × List α => x.1 ++ x.2) :=
  (((fst.comp reverse).pair snd).comp revOnto).congr
    (fun x => by simp only [Realizer.fold_cons_eq, List.reverse_reverse])

lemma volume_revOnto (xs ys : List α) :
    volume (xs.foldl (fun b a => a :: b) ys) + 1 = volume xs + volume ys := by
  rw [Realizer.fold_cons_eq, volume_append, volume_reverse]

def flatten : PR (fun xs : List (List α) => xs.flatten) :=
  ((((id.pair nil).comp (revOnto.fold (fun n => n + 1 * n) (Poly.id.add (Poly.smul 1 Poly.id))
    (hacc_add (F := fun x : List α × List α => x.1.foldl (fun b a => a :: b) x.2) 1 (fun zs acc => by
      have := volume_revOnto zs acc; dsimp only; omega)))).comp reverse).congr
    (fun xs => by
      simp only
      rw [show (fun (b : List α) (a : List α) => a.foldl (fun b a => a :: b) b) =
        (fun ys zs => zs.foldl (fun ys a => a :: ys) ys) from rfl]
      rw [Uniform.flatten_fold_eq (I := Unit) (α := fun _ => α) () xs [], List.append_nil,
        List.reverse_reverse]))

def flatMap {f : α × γ → List β} (P : PR f) :
    PR (fun x : List α × γ => x.1.flatMap (fun a => f (a, x.2))) :=
  (P.map.comp flatten).congr (fun x => by simp [List.flatMap])

def length : PR (fun xs : List α => xs.length) :=
  ((id.pair (const 0)).comp
    ((⟨Realizer.snd.comp Realizer.succ, fun n => (n + 2) + 200 * (n + 1) + 10 * (n + 1),
        ((Poly.id.add (Poly.const 2)).add (Poly.smul 200 Poly.id.succ)).add (Poly.smul 10 Poly.id.succ),
        fun x => by
          rcases x with ⟨a, k⟩
          rw [Realizer.time_comp]
          simp only [Realizer.time_snd, volume_pair, volume_nat]
          have := Realizer.time_succ_le k
          omega,
        fun x => by rcases x with ⟨a, k⟩; simp only [volume_pair, volume_nat]; omega⟩ :
      PR (fun x : α × ℕ => x.2 + 1)).fold (fun n => n + 2 * n) (Poly.id.add (Poly.smul 2 Poly.id))
      (hacc_add (F := fun x : α × ℕ => x.2 + 1) 2 (fun a k => by simp only [volume_nat]; omega)))).congr (fun xs => by
    simp only
    have : ∀ (ys : List α) (k : ℕ), ys.foldl (fun b _ => b + 1) k = k + ys.length := by
      intro ys; induction ys with
      | nil => simp
      | cons a ys ih => intro k; simp [ih]; omega
    rw [this]; simp)

end PR

end OPI.W6
end

-- ===== OPI.PRArith =====
section

/-!
# Polynomial realizers: arithmetic, Booleans, and the Cook–Levin bridge
-/

namespace OPI.W6

open OAI.ThreeMachine.StackCompiler

variable {α β γ : Type} [Coding α] [Coding β] [Coding γ]

namespace PR

/-- Quadratic-time binary operations on unary numbers. -/
def ofQuad {f : ℕ × ℕ → β} (R : Realizer f) (C : ℕ) (ht : ∀ a b, R.time (a, b) ≤ C * (a + b + 1) ^ 2)
    (hv : ∀ a b, volume (f (a, b)) ≤ 2 * (a + b) + 3) : PR f :=
  ⟨R, fun n => C * (n * n) + n, (Poly.smul C (Poly.id.mul Poly.id)).add Poly.id,
    fun x => by
      rcases x with ⟨a, b⟩
      have h := ht a b
      simp only [volume_pair, volume_nat]
      have : (a + b + 1) ^ 2 ≤ (2 * a + 1 + (2 * b + 1) + 1) * (2 * a + 1 + (2 * b + 1) + 1) := by
        rw [sq]; exact Nat.mul_le_mul (by omega) (by omega)
      have := Nat.mul_le_mul_left C this
      omega,
    fun x => by
      rcases x with ⟨a, b⟩
      have := hv a b
      simp only [volume_pair, volume_nat]
      omega⟩

def add : PR (fun x : ℕ × ℕ => x.1 + x.2) :=
  ofQuad Realizer.add _ Realizer.time_add_le (fun a b => by simp only [volume_nat]; omega)

def sub : PR (fun x : ℕ × ℕ => x.1 - x.2) :=
  ofQuad Realizer.sub _ Realizer.time_sub_le (fun a b => by simp only [volume_nat]; omega)

def le : PR (fun x : ℕ × ℕ => decide (x.1 ≤ x.2)) :=
  ofQuad Realizer.le _ Realizer.time_le_le (fun a b => by have := volume_bool (decide (a ≤ b)); dsimp only; omega)

def eqNat : PR (fun x : ℕ × ℕ => decide (x.1 = x.2)) :=
  ofQuad Realizer.eqNat _ Realizer.time_eqNat_le (fun a b => by have := volume_bool (decide (a = b)); dsimp only; omega)

def succ : PR (fun n : ℕ => n + 1) :=
  ⟨Realizer.succ, fun n => 200 * (n + 1), Poly.smul 200 Poly.id.succ,
    fun x => by have := Realizer.time_succ_le x; simp only [volume_nat]; omega,
    fun x => by simp only [volume_nat]; omega⟩



def not : PR (fun b : Bool => !b) :=
  ⟨Realizer.not, fun _ => 10000, Poly.const _, fun x => Realizer.time_not_le x,
    fun x => by have := volume_bool (!x); omega⟩

def and : PR (fun x : Bool × Bool => x.1 && x.2) :=
  ⟨Realizer.and, fun _ => 10000, Poly.const _, fun x => Realizer.time_and_le x,
    fun x => by have := volume_bool (x.1 && x.2); omega⟩

def or : PR (fun x : Bool × Bool => x.1 || x.2) :=
  ⟨Realizer.or, fun _ => 10000, Poly.const _, fun x => Realizer.time_or_le x,
    fun x => by have := volume_bool (x.1 || x.2); omega⟩

def isZero : PR (fun n : ℕ => decide (n = 0)) :=
  ((id.pair (const 0)).comp eqNat).congr (fun _ => rfl)

/-- Multiplication by repeated addition. -/
def mul : PR (fun x : ℕ × ℕ => x.1 * x.2) :=
  (((fst.pair (snd.pair (const 0))).comp
    ((fst.pair ((snd.pair fst).comp add) : PR (fun y : ℕ × ℕ => (y.1, y.2 + y.1))).iterate
      (fun n => 4 * (n * n) + 4 * n + 4)
      (((Poly.smul 4 (Poly.id.mul Poly.id)).add (Poly.smul 4 Poly.id)).add (Poly.const 4))
      (fun m a j hj => by
        rcases a with ⟨b, c⟩
        have e : ∀ j, (fun y : ℕ × ℕ => (y.1, y.2 + y.1))^[j] (b, c) = (b, c + j * b) := by
          intro j; induction j with
          | zero => simp
          | succ j ih => rw [Function.iterate_succ_apply', ih]; simp only [Prod.mk.injEq, true_and]; ring
        rw [e]
        simp only [volume_pair, volume_nat]
        have : j * b ≤ m * b := Nat.mul_le_mul_right _ hj
        have : m * b ≤ (2 * m + 1 + (2 * b + 1 + (2 * c + 1) + 1) + 1) *
            (2 * m + 1 + (2 * b + 1 + (2 * c + 1) + 1) + 1) := Nat.mul_le_mul (by omega) (by omega)
        omega))).comp snd).congr (fun x => by
    rcases x with ⟨a, b⟩
    have e : ∀ j, (fun y : ℕ × ℕ => (y.1, y.2 + y.1))^[j] (b, 0) = (b, j * b) := by
      intro j; induction j with
      | zero => simp
      | succ j ih => rw [Function.iterate_succ_apply', ih]; simp only [Prod.mk.injEq, true_and]; ring
    simp only [e])

end PR

/-! ### The bridge to Cook–Levin machines -/

lemma volume_bools_le (x : List Bool) : volume x ≤ 4 * x.length + 1 := by
  induction x with
  | nil => simp
  | cons b x ih => simp only [volume_cons, List.length_cons]; have := volume_bool b; omega



end OPI.W6
end

-- ===== OPI.PRList =====
section

/-!
# Polynomial realizers: list operations
-/

namespace OPI.W6

open OAI.ThreeMachine.StackCompiler

variable {α β γ : Type} [Coding α] [Coding β] [Coding γ]

namespace PR

/-- Accumulator bound for folds carrying a frozen part of volume `inv b`. -/
lemma hacc_env {F : α × β → β} (c : ℕ) (inv : β → ℕ) (hinv : ∀ a b, inv (F (a, b)) = inv b)
    (hle : ∀ b, inv b ≤ volume b)
    (h : ∀ a b, volume (F (a, b)) ≤ volume b + c * (volume a + 1) + inv b) :
    ∀ (xs : List α) (b : β) k,
      volume ((xs.take k).foldl (fun b a => F (a, b)) b) ≤
        (fun n => n + c * n + n * n) (volume (xs, b)) := by
  have key : ∀ (xs : List α) (b : β) k,
      volume ((xs.take k).foldl (fun b a => F (a, b)) b) + 1 ≤
        volume b + c * volume xs + xs.length * inv b + 1 ∧
      inv ((xs.take k).foldl (fun b a => F (a, b)) b) = inv b := by
    intro xs
    induction xs with
    | nil => intro b k; simp
    | cons a xs ih =>
      intro b k
      cases k with
      | zero =>
        simp only [List.take_zero, List.foldl_nil, volume_cons, List.length_cons]
        refine ⟨?_, by simp⟩
        have : 0 ≤ c * (volume a + volume xs + 1) := Nat.zero_le _
        have : 0 ≤ (xs.length + 1) * inv b := Nat.zero_le _
        omega
      | succ k =>
        simp only [List.take_succ_cons, List.foldl_cons, volume_cons, List.length_cons]
        obtain ⟨h1, h1'⟩ := ih (F (a, b)) k
        have h2 := h a b
        rw [hinv] at h1 h1'
        refine ⟨?_, h1'⟩
        have e : c * (volume a + volume xs + 1) = c * (volume a + 1) + c * volume xs := by ring
        have e' : (xs.length + 1) * inv b = xs.length * inv b + inv b := by ring
        rw [e, e']; omega
  intro xs b k
  have h1 := (key xs b k).1
  have hl := length_le_volume xs
  have hi := hle b
  simp only [volume_pair]
  have e1 : xs.length * inv b ≤ (volume xs + volume b + 1) * (volume xs + volume b + 1) :=
    Nat.mul_le_mul (by omega) (by omega)
  have e : c * (volume xs + volume b + 1) = c * volume xs + c * (volume b + 1) := by ring
  rw [e]; omega

/-! ### Basic list access -/

def tail : PR (fun xs : List α => xs.tail) :=
  ⟨(Uniform.tail (I := Unit) (α := fun _ => α)).specialize (), fun n => n + 2,
    Poly.id.add (Poly.const 2), fun x => le_rfl,
    fun x => by cases x <;> simp only [List.tail_nil, List.tail_cons, volume_cons] <;> omega⟩

def head? : PR (fun xs : List α => xs.head?) :=
  ⟨(Uniform.head? (I := Unit) (α := fun _ => α)).specialize (), fun n => 10000 * (n + 1) + (n + 2),
    (Poly.smul 10000 Poly.id.succ).add (Poly.id.add (Poly.const 2)),
    fun x => (Uniform.time_head?_le (I := Unit) (α := fun _ => α) () x).trans (by omega),
    fun x => by cases x <;> simp only [List.head?_nil, List.head?_cons, volume_none, volume_some,
      volume_cons] <;> omega⟩

def drop : PR (fun x : List α × ℕ => x.1.drop x.2) :=
  ((snd.pair fst).comp (tail.iterate (fun n => n) Poly.id (fun m xs j _ => by
    have : ∀ j (xs : List α), volume ((fun xs : List α => xs.tail)^[j] xs) ≤ volume xs := by
      intro j; induction j with
      | zero => intro xs; simp
      | succ j ih => intro xs; rw [Function.iterate_succ_apply]; refine (ih _).trans ?_
                     cases xs <;> simp only [List.tail_nil, List.tail_cons, volume_cons] <;> omega
    have := this j xs
    simp only [volume_pair]; omega))).congr (fun x => by
    simp only
    have h : ∀ (n : ℕ) (xs : List α), (fun xs : List α => xs.tail)^[n] xs = xs.drop n := by
      intro n; induction n with
      | zero => intro xs; rfl
      | succ n ih => intro xs; rw [Function.iterate_succ_apply, ih, List.drop_tail]
    rw [h])

def getElem? : PR (fun x : List α × ℕ => x.1[x.2]?) :=
  (drop.comp head?).congr (fun x => by simp only [List.head?_drop])

def optGetD : PR (fun x : Option α × α => x.1.getD x.2) :=
  ⟨(Uniform.getD (I := Unit) (α := fun _ => α)).specialize (), fun n => 10000 * (n + 1) + n,
    (Poly.smul 10000 Poly.id.succ).add Poly.id,
    fun x => by
      rcases x with ⟨o, a⟩
      have := Uniform.time_getD_le (I := Unit) (α := fun _ => α) () o a
      exact this.trans (by simp only [volume_pair]; omega),
    fun x => by
      rcases x with ⟨o, a⟩
      cases o <;> simp only [Option.getD_none, Option.getD_some, volume_pair, volume_none, volume_some] <;>
        omega⟩

def listGetD : PR (fun x : (List α × ℕ) × α => x.1.1.getD x.1.2 x.2) :=
  (((fst.comp getElem?).pair snd).comp optGetD).congr (fun x => by
    simp only [List.getD_eq_getElem?_getD])

def isCons : PR (fun xs : List α => !xs.isEmpty) :=
  ⟨(Uniform.isCons (I := Unit) (α := fun _ => α)).specialize (), fun n => 10000 * (n + 1) + 3,
    (Poly.smul 10000 Poly.id.succ).add (Poly.const 3),
    fun x => (Realizer.time_test_le (α := List α) (fun xs => !xs.isEmpty)
      (by intro xs; cases xs <;> rfl) x).trans (by omega),
    fun x => by have := volume_bool (!x.isEmpty); omega⟩

def isSome : PR (fun o : Option α => o.isSome) :=
  ⟨(Uniform.optionIsSome (I := Unit) (α := fun _ => α)).specialize (), fun n => 10000 * (n + 1) + 3,
    (Poly.smul 10000 Poly.id.succ).add (Poly.const 3),
    fun x => (Realizer.time_test_le (α := Option α) (fun o => o.isSome)
      (by intro o; cases o <;> rfl) x).trans (by omega),
    fun x => by have := volume_bool x.isSome; omega⟩

/-- Head with a default. -/
def headD : PR (fun x : List α × α => x.1.headD x.2) :=
  (((fst.comp head?).pair snd).comp optGetD).congr (fun x => by cases x.1 <;> rfl)

/-! ### Folds with environments -/

/-- `any` with an environment. -/
def any {p : α × γ → Bool} (P : PR p) : PR (fun x : List α × γ => x.1.any (fun a => p (a, x.2))) :=
  (((fst.pair (snd.pair (const false))).comp
    ((((snd.comp fst).pair (((snd.comp snd).pair ((fst.pair (snd.comp fst)).comp P)).comp or)) :
      PR (fun y : α × (γ × Bool) => (y.2.1, y.2.2 || p (y.1, y.2.1)))).fold
      (fun n => n + 2 * n + n * n) ((Poly.id.add (Poly.smul 2 Poly.id)).add (Poly.id.mul Poly.id))
      (hacc_env (F := fun y : α × (γ × Bool) => (y.2.1, y.2.2 || p (y.1, y.2.1))) 2 (fun _ => 0)
        (fun _ _ => rfl) (fun _ => Nat.zero_le _)
        (fun a b => by
          rcases b with ⟨e, c⟩
          have := volume_bool c; have := volume_bool (c || p (a, e))
          have := volume_pos c; have := volume_pos a
          simp only [volume_pair]; omega)))).comp snd).congr (fun x => by
    simp only
    rw [Uniform.any_fold_eq (I := Unit) (α := fun _ => α) (γ := fun _ => γ) (fun _ => p) () x.1 x.2 false]
    simp)

/-- The step of `setL`. -/
def setStep : PR (fun y : α × (α × ℕ × ℕ × List α) =>
    (y.2.1, y.2.2.1, y.2.2.2.1 + 1, (if y.2.2.2.1 = y.2.2.1 then y.2.1 else y.1) :: y.2.2.2.2)) :=
  let vP : PR (fun y : α × (α × ℕ × ℕ × List α) => y.2.1) := snd.comp fst
  let iP : PR (fun y : α × (α × ℕ × ℕ × List α) => y.2.2.1) := (snd.comp snd).comp fst
  let cP : PR (fun y : α × (α × ℕ × ℕ × List α) => y.2.2.2.1) := ((snd.comp snd).comp snd).comp fst
  let accP : PR (fun y : α × (α × ℕ × ℕ × List α) => y.2.2.2.2) := ((snd.comp snd).comp snd).comp snd
  let chP := (((cP.pair iP).comp eqNat).pair (vP.pair fst)).comp (choose fst snd)
  (vP.pair (iP.pair ((cP.comp succ).pair ((chP.pair accP).comp cons)))).congr (fun y => by
    simp only [decide_eq_true_eq])

/-- `List.set`. -/
def setL : PR (fun x : (List α × ℕ) × α => x.1.1.set x.1.2 x.2) :=
  let init : PR (fun x : (List α × ℕ) × α => (x.1.1, (x.2, x.1.2, 0, ([] : List α)))) :=
    (fst.comp fst).pair (snd.pair ((fst.comp snd).pair ((const 0).pair nil)))
  let body := setStep.fold
      (fun n => n + 3 * n + n * n) ((Poly.id.add (Poly.smul 3 Poly.id)).add (Poly.id.mul Poly.id))
      (hacc_env (F := fun y : α × (α × ℕ × ℕ × List α) =>
          (y.2.1, y.2.2.1, y.2.2.2.1 + 1, (if y.2.2.2.1 = y.2.2.1 then y.2.1 else y.1) :: y.2.2.2.2))
        3 (fun b => volume b.1) (fun _ _ => rfl)
        (fun b => by rcases b with ⟨v, r⟩; simp only [volume_pair]; omega)
        (fun a b => by
          rcases b with ⟨v, i, c, acc⟩
          simp only [volume_pair, volume_cons, volume_nat]
          split_ifs <;> omega))
  let fin : PR (fun y : α × ℕ × ℕ × List α => y.2.2.2.reverse) := ((snd.comp snd).comp snd).comp reverse
  ((init.comp body).comp fin).congr (fun x => by
    rcases x with ⟨⟨xs, i⟩, v⟩
    simp only
    have key : ∀ (xs acc : List α) (c : ℕ), xs.foldl (fun b a =>
        (b.1, b.2.1, b.2.2.1 + 1, (if b.2.2.1 = b.2.1 then b.1 else a) :: b.2.2.2)) (v, i, c, acc) =
        (v, i, c + xs.length, (xs.mapIdx (fun k a => if c + k = i then v else a)).reverse ++ acc) := by
      intro xs; induction xs with
      | nil => intro acc c; simp
      | cons a xs ih =>
        intro acc c
        rw [List.foldl_cons, ih]
        simp only [List.length_cons, List.mapIdx_cons, List.reverse_cons, List.append_assoc,
          List.singleton_append, Nat.add_zero, Prod.mk.injEq, true_and]
        refine ⟨by omega, ?_⟩
        congr 2
        refine List.mapIdx_eq_mapIdx_iff.mpr (fun k hk => ?_)
        simp only [show c + 1 + k = c + (k + 1) by omega]
    rw [key]
    simp only [Nat.zero_add, List.append_nil, List.reverse_reverse]
    refine List.ext_getElem (by simp) (fun k h1 h2 => ?_)
    rw [List.getElem_mapIdx, List.getElem_set]
    by_cases h : k = i
    · subst h; simp
    · simp only [Nat.zero_add, h, if_false, Ne.symm h])

lemma iter_rep (a : α) : ∀ (j : ℕ) (acc : List α),
    (fun y : α × List α => (y.1, y.1 :: y.2))^[j] (a, acc) = (a, List.replicate j a ++ acc) := by
  intro j; induction j with
  | zero => intro acc; simp
  | succ j ih => intro acc; rw [Function.iterate_succ_apply', ih]; simp only [List.replicate_succ, List.cons_append]

lemma volume_rep_append (a : α) (acc : List α) : ∀ j,
    volume (List.replicate j a ++ acc) = volume acc + j * (volume a + 1) := by
  intro j; induction j with
  | zero => simp
  | succ j ih => simp only [List.replicate_succ, List.cons_append, volume_cons, ih]; ring

/-- `List.replicate`. -/
def replicate : PR (fun x : ℕ × α => List.replicate x.1 x.2) :=
  let step : PR (fun y : α × List α => (y.1, y.1 :: y.2)) := fst.pair cons
  let it := step.iterate (fun n => n + n * n) (Poly.id.add (Poly.id.mul Poly.id)) (fun m b j hj => by
    rcases b with ⟨a, acc⟩
    rw [iter_rep]
    simp only [volume_pair, volume_nat, volume_rep_append]
    have : j * (volume a + 1) ≤ (2 * m + 1 + (volume a + volume acc + 1) + 1) *
        (2 * m + 1 + (volume a + volume acc + 1) + 1) := Nat.mul_le_mul (by omega) (by omega)
    omega)
  let init : PR (fun x : ℕ × α => (x.1, (x.2, ([] : List α)))) := fst.pair (snd.pair nil)
  ((init.comp it).comp snd).congr (fun x => by
    rcases x with ⟨n, a⟩
    simp only [iter_rep, List.append_nil])

end PR

end OPI.W6
end

-- ===== OPI.PRStr =====
section

/-!
# Polynomial realizers: bit strings, interning, node codes
-/

namespace OPI.W6

open OAI.ThreeMachine.StackCompiler QAlgorithms QAlgorithms.OPI QAlgorithms.Complexity

namespace PR

def beqBool : PR (fun p : Bool × Bool => p.1 == p.2) :=
  ((and.pair (((fst.comp not).pair (snd.comp not)).comp and)).comp or).congr (fun p => by
    rcases p with ⟨a, b⟩; cases a <;> cases b <;> rfl)

/-- The step of string comparison. -/
def beqF (b : List Bool × Bool) (a : Bool) : List Bool × Bool :=
  (b.1.tail, b.2 && (!b.1.isEmpty && (b.1.headD false == a)))

def beqStep : PR (fun y : Bool × (List Bool × Bool) => beqF y.2 y.1) :=
  let ysP : PR (fun y : Bool × (List Bool × Bool) => y.2.1) := snd.comp fst
  let hdP : PR (fun y : Bool × (List Bool × Bool) => y.2.1.headD false == y.1) :=
    (((ysP.pair (const false)).comp headD).pair fst).comp beqBool
  let okP : PR (fun y : Bool × (List Bool × Bool) => y.2.2 && (!y.2.1.isEmpty && (y.2.1.headD false == y.1))) :=
    ((snd.comp snd).pair (((ysP.comp isCons).pair hdP).comp and)).comp and
  ((ysP.comp tail).pair okP).congr (fun _ => rfl)

lemma beq_fold (xs : List Bool) : ∀ (ys : List Bool) (ok : Bool),
    xs.foldl beqF (ys, ok) = (ys.drop xs.length, ok && decide (xs = ys.take xs.length)) := by
  induction xs with
  | nil => intro ys ok; simp
  | cons x xs ih =>
    intro ys ok
    rw [List.foldl_cons, ih]
    cases ys with
    | nil =>
      simp only [beqF, List.tail_nil, List.isEmpty_nil, Bool.not_true, Bool.false_and, Bool.and_false,
        List.drop_nil, List.take_nil, List.length_cons]
      simp
    | cons y ys =>
      simp only [beqF, List.tail_cons, List.isEmpty_cons, Bool.not_false, List.headD_cons, Bool.true_and,
        List.length_cons, List.drop_succ_cons, List.take_succ_cons]
      rw [Bool.and_assoc]
      congr 2
      by_cases hxy : x = y
      · subst hxy; simp
      · have : (y == x) = false := by simpa using Ne.symm hxy
        rw [this]; simp [hxy]

/-- Equality of bit strings. -/
def beqStr : PR (fun x : List Bool × List Bool => decide (x.1 = x.2)) :=
  let r : PR (fun x : List Bool × List Bool => x.1.foldl beqF (x.2, true)) :=
    ((fst.pair (snd.pair (const true))).comp
      (beqStep.fold (fun n => n + 3 * n) (Poly.id.add (Poly.smul 3 Poly.id))
        (hacc_add (F := fun y : Bool × (List Bool × Bool) => beqF y.2 y.1) 3 (fun a b => by
          rcases b with ⟨ys, ok⟩
          have := volume_bool ok
          have := volume_bool (ok && (!ys.isEmpty && (ys.headD false == a)))
          have : volume ys.tail ≤ volume ys := by
            cases ys <;> simp only [List.tail_nil, List.tail_cons, volume_cons] <;> omega
          simp only [beqF, volume_pair]; omega)))).congr (fun _ => rfl)
  let fin : PR (fun r : List Bool × Bool => r.2 && r.1.isEmpty) :=
    ((snd.pair ((fst.comp isCons).comp not)).comp and).congr (fun r => by simp only [Bool.not_not])
  (r.comp fin).congr (fun x => by
    rcases x with ⟨xs, ys⟩
    simp only [beq_fold, Bool.true_and]
    by_cases h : xs = ys
    · subst h; simp
    · have : ¬ (xs = ys.take xs.length ∧ ys.drop xs.length = []) := by
        rintro ⟨h1, h2⟩
        apply h
        rw [← List.take_append_drop xs.length ys, h2, List.append_nil, ← h1]
      rw [decide_eq_false h]
      cases h1 : decide (xs = List.take xs.length ys)
      · rfl
      · have e1 : xs = ys.take xs.length := of_decide_eq_true h1
        have e2 : ys.drop xs.length ≠ [] := fun e => this ⟨e1, e⟩
        rw [Bool.true_and]
        cases h2 : ys.drop xs.length with
        | nil => exact absurd h2 e2
        | cons _ _ => rfl)

/-- The step of the search for a string in a table. -/
def idxF (b : List Bool × Bool × ℕ) (a : List Bool) : List Bool × Bool × ℕ :=
  (b.1, b.2.1 || decide (a = b.1), if b.2.1 || decide (a = b.1) then b.2.2 else b.2.2 + 1)

def idxStep : PR (fun y : List Bool × (List Bool × Bool × ℕ) => idxF y.2 y.1) :=
  let fP : PR (fun y : List Bool × (List Bool × Bool × ℕ) => y.2.2.1 || decide (y.1 = y.2.1)) :=
    (((snd.comp snd).comp fst).pair ((fst.pair (snd.comp fst)).comp beqStr)).comp or
  let iP : PR (fun y : List Bool × (List Bool × Bool × ℕ) => y.2.2.2) := (snd.comp snd).comp snd
  ((snd.comp fst).pair (fP.pair ((fP.pair (iP.pair (iP.comp succ))).comp (choose fst snd)))).congr
    (fun _ => rfl)

lemma idx_true (x : List Bool) : ∀ (T : List (List Bool)) (i : ℕ), T.foldl idxF (x, true, i) = (x, true, i) := by
  intro T; induction T with
  | nil => intro i; rfl
  | cons t T ih => intro i; rw [List.foldl_cons]; exact ih i

lemma idx_fold (x : List Bool) : ∀ (T : List (List Bool)) (i : ℕ),
    T.foldl idxF (x, false, i) = (x, decide (x ∈ T), i + T.idxOf x) := by
  intro T
  induction T with
  | nil => intro i; simp
  | cons t T ih =>
    intro i
    rw [List.foldl_cons]
    by_cases h : t = x
    · subst h
      rw [show idxF (t, false, i) t = (t, true, i) by simp [idxF], idx_true]
      simp [List.idxOf_cons_self]
    · rw [show idxF (x, false, i) t = (x, false, i + 1) by simp [idxF, h], ih (i + 1),
        List.idxOf_cons_ne _ h]
      simp only [List.mem_cons, Ne.symm h, false_or, Prod.mk.injEq, true_and]
      omega

/-- Interning a code. -/
def intern : PR (fun x : List Bool × List (List Bool) => internProgramNode x.1 x.2) :=
  let r : PR (fun x : List Bool × List (List Bool) => x.2.foldl idxF (x.1, false, 0)) :=
    ((snd.pair (fst.pair ((const false).pair (const 0)))).comp
      (idxStep.fold (fun n => n + 4 * n) (Poly.id.add (Poly.smul 4 Poly.id))
        (hacc_add (F := fun y : List Bool × (List Bool × Bool × ℕ) => idxF y.2 y.1) 4 (fun a b => by
          rcases b with ⟨x, f, i⟩
          have := volume_bool f; have := volume_bool (f || decide (a = x)); have := volume_pos a
          simp only [idxF, volume_pair, volume_nat]; split_ifs <;> omega)))).congr (fun _ => rfl)
  -- context (r, x)
  let ctx : PR (fun x : List Bool × List (List Bool) => (x.2.foldl idxF (x.1, false, 0), x)) := r.pair id
  let idxP : PR (fun c : (List Bool × Bool × ℕ) × (List Bool × List (List Bool)) => c.1.2.2) :=
    fst.comp (snd.comp snd)
  let memP : PR (fun c : (List Bool × Bool × ℕ) × (List Bool × List (List Bool)) => c.1.2.1) :=
    fst.comp (snd.comp fst)
  let TP : PR (fun c : (List Bool × Bool × ℕ) × (List Bool × List (List Bool)) => c.2.2) := snd.comp snd
  let appP : PR (fun c : (List Bool × Bool × ℕ) × (List Bool × List (List Bool)) => c.2.2 ++ [c.2.1]) :=
    (TP.pair (((snd.comp fst).pair nil).comp cons)).comp append
  (ctx.comp (idxP.pair ((memP.pair (TP.pair appP)).comp (choose fst snd)))).congr (fun x => by
    rcases x with ⟨c, T⟩
    simp only [idx_fold, Nat.zero_add]
    unfold internProgramNode
    by_cases hc : c ∈ T
    · simp [hc]
    · simp [hc, List.idxOf_eq_length hc])

def encNatP : PR (fun k : ℕ => encNat k) :=
  (((((id.pair (const true)).comp replicate).pair (const [false])).comp append)).congr (fun k => rfl)

def serWords : PR (fun w : List ℕ => serializeWords w) :=
  ((id.pair (const ())).comp ((fst.comp encNatP : PR (fun y : ℕ × Unit => encNat y.1)).flatMap)).congr
    (fun w => by simp [serializeWords, List.flatMap])

def codeIP : PR (fun x : INode × List ℕ => codeI x.1 x.2) :=
  ((((fst.comp fst).pair ((((fst.comp snd).comp fst).pair snd).comp append)).comp cons).comp
    serWords).congr (fun x => rfl)

end PR

end OPI.W6
end
Source
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/Definitions/Def_TwoFoldOPI_CL_Part02.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