Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Ceiling logarithm and next-power correctness

Definition
QMAPerfectCompleteness_Proof_UnaryNextPowerCorrectness

by Dorian Rudolph · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

qma-perfect-completeness-bbe19ef

Defines the total unary compiler interface for a ceiling logarithm and the corresponding power of two. The complete execution, output encoding and polynomial bound are proved for the finite doubling machine.

Definition code
/- Generated from Solutions.UnaryNextPowerCorrectness by authoritative Stage-2 skeleton subtraction.
Original explanatory text, declaration names and scoped commands are retained.
Only selected proof cuts, import rewrites and fact-indexed platform edits are applied. -/
import Definitions.Def_QMAPerfectCompleteness_Main_Cyclic
import Definitions.Def_QMAPerfectCompleteness_Main_Compiler
import Definitions.Def_QMAPerfectCompleteness_Main_Classes
import Definitions.Def_QAlgorithms_ClassicalStringComputability
import Definitions.Def_QMAPerfectCompleteness_Proof_BinaryComposition
import Definitions.Def_QMAPerfectCompleteness_Proof_BlockEncoding
import Definitions.Def_QMAPerfectCompleteness_Proof_CircuitUnitary
import Definitions.Def_QMAPerfectCompleteness_Proof_ConcreteUniformity
import Definitions.Def_QMAPerfectCompleteness_Proof_ControlCircuits
import Definitions.Def_QMAPerfectCompleteness_Proof_Cyclic
import Definitions.Def_QMAPerfectCompleteness_Proof_EuclideanStates
import Definitions.Def_QMAPerfectCompleteness_Proof_PolyTimeComposition
import Definitions.Def_QMAPerfectCompleteness_Proof_RawCircuitEncoding
import Definitions.Def_QMAPerfectCompleteness_Proof_Repetition
import Definitions.Def_QMAPerfectCompleteness_Proof_RepetitionCircuit
import Definitions.Def_QMAPerfectCompleteness_Proof_RepetitionEncoding
import Definitions.Def_QMAPerfectCompleteness_Proof_ReversibleGadgets
import Definitions.Def_QMAPerfectCompleteness_Proof_UnaryNextPowerPhases
import Definitions.Def_QMAPerfectCompleteness_Proof_UnaryNextPowerTM
import Definitions.Def_QMAPerfectCompleteness_Proof_VerifierEncoding

/- Namespace registrations retained from original proof-only imports. -/
namespace QMAPerfectCompleteness.Main.DiagonalProof
end QMAPerfectCompleteness.Main.DiagonalProof
namespace QMAPerfectCompleteness.Uniformity.Expansion
end QMAPerfectCompleteness.Uniformity.Expansion
namespace QMAPerfectCompleteness.Uniformity.UnaryNatArithmetic
end QMAPerfectCompleteness.Uniformity.UnaryNatArithmetic



/-! Correctness and polynomial execution time of the finite unary ceiling-log2 machine. -/
set_option backward.isDefEq.respectTransparency false
set_option maxHeartbeats 1500000
open Turing StateTransition
namespace QMAPerfectCompleteness.Uniformity.UnaryNextPowerTM
open QAlgorithms.Complexity (Str encNat)

def loopData (d : Data) (a p : ℕ) : Data :=
  {d with target := a,power := p,savedTarget := 0,savedPower := 0,doubled := 0}

def loopTime (a p h : ℕ) : ℕ := 6*p*(2^h-1)+5*h+3*a+3

lemma loopTime_succ (a p h : ℕ) :
    loopTime a p (h+1) = (3*p+3)+((3*p+2)+loopTime a (2*p) h) := by
  have hp : 0<2^h := pow_pos (by decide : 0<2) h
  have he : 2^(h+1)-1 = 2*(2^h-1)+1 := by rw [pow_succ]; omega
  unfold loopTime
  rw [he]
  ring

/-- The bounded doubling loop uses exactly the geometric amount of unary work. -/
lemma loop_run (h a p : ℕ) (v : Option Bool) (d : Data) (hp : 0<p)
    (hbefore : ∀ i, i<h → p*2^i<a) (hdone : a≤p*2^h) :
    run (loopTime a p h) (some (cfg .compare v (loopData d a p))) =
      some (cfg .reverseTail none {loopData d a (p*2^h) with exponent := d.exponent+h}) := by
  induction h generalizing p v d with
  | zero =>
    have ha : a≤p := by simpa using hdone
    have hc := compare_restore_run v {d with doubled := 0} a p
    simpa [loopTime,loopData,Nat.min_eq_left ha,show ¬p<a by omega] using hc
  | succ h ih =>
    have hlt : p<a := by simpa using hbefore 0 (by omega)
    let dc : Data := {loopData d a p with exponent := d.exponent+1}
    let dn : Data := {d with exponent := d.exponent+1}
    have hc : run (3*p+3) (some (cfg .compare v (loopData d a p))) = some (cfg .double none dc) := by
      simpa [loopData,dc,Nat.min_eq_right hlt.le,hlt] using
        compare_restore_run v {d with doubled := 0} a p
    have hd : run (3*p+2) (some (cfg .double none dc)) =
        some (cfg .compare none (loopData dn a (2*p))) := by
      simpa only [dc,dn,loopData] using doubling_run none dc p
    have hi := ih (p := 2*p) (v := none) (d := dn) (by omega)
      (by
        intro i hi
        have h' := hbefore (i+1) (by omega)
        simpa only [pow_succ,Nat.mul_assoc,Nat.mul_comm,Nat.mul_left_comm] using h')
      (by simpa only [pow_succ,Nat.mul_assoc,Nat.mul_comm,Nat.mul_left_comm] using hdone)
    have hr := run_trans hc (run_trans hd hi)
    rw [← loopTime_succ] at hr
    simpa only [dc,dn,loopData,pow_succ,Nat.mul_assoc,Nat.mul_comm,Nat.mul_left_comm,
      Nat.add_assoc,Nat.add_comm,Nat.add_left_comm] using hr

lemma finish_run (v : Option Bool) (a p c : ℕ) (tail : Str) :
    run (2*tail.length+p+c+a+5)
      (some (cfg .reverseTail v {input := tail,target := a,power := p+1,exponent := c})) =
      some (haltList machine (encNat c++encNat p++tail)) := by
  let ellCode := encNat p++tail
  let output := encNat c++ellCode
  have h1 : run (tail.length+1)
      (some (cfg .reverseTail v {input := tail,target := a,power := p+1,exponent := c})) =
      some (cfg .outputTail none {target := a,power := p+1,exponent := c,tail := tail.reverse}) := by
    simpa only [List.append_nil] using reverseTail_run v {target := a,power := p+1,exponent := c} tail
  have h2 : run (tail.length+1)
      (some (cfg .outputTail none {target := a,power := p+1,exponent := c,tail := tail.reverse})) =
      some (cfg .outputPower none {target := a,power := p,exponent := c,output := false::tail}) := by
    simpa only [List.length_reverse,List.reverse_reverse,List.append_nil] using
      outputTail_run none {target := a,power := p+1,exponent := c} tail.reverse p
  have h3 : run (p+1)
      (some (cfg .outputPower none {target := a,power := p,exponent := c,output := false::tail})) =
      some (cfg .outputExponent none {target := a,exponent := c,output := false::ellCode}) := by
    simpa only [ellCode,encNat,List.append_assoc,List.singleton_append] using
      outputPower_run none {target := a,exponent := c,output := false::tail} p
  have h4 : run (c+1)
      (some (cfg .outputExponent none {target := a,exponent := c,output := false::ellCode})) =
      some (cfg .clearTarget none {target := a,output := output}) := by
    simpa only [output,encNat,List.append_assoc,List.singleton_append] using
      outputExponent_run none {target := a,output := false::ellCode} c
  have h5 := clearTarget_run none a output
  have hr := run_trans h1 (run_trans h2 (run_trans h3 (run_trans h4 h5)))
  have ht : (tail.length+1)+((tail.length+1)+((p+1)+((c+1)+(a+1)))) = 2*tail.length+p+c+a+5 := by omega
  rw [ht] at hr
  simpa only [output,ellCode,List.append_assoc] using hr

/-- Exact output bytes; the source payload after the first unary field is retained verbatim. -/
def outputCode (a : ℕ) (tail : Str) : Str :=
  encNat (Nat.clog 2 a) ++ encNat (2^(Nat.clog 2 a)-1) ++ tail

def time (a : ℕ) (tail : Str) : ℕ :=
  5*a+7*2^(Nat.clog 2 a)+6*(Nat.clog 2 a)+2*tail.length+3

lemma init_step (s : Str) : machine.step (initList machine s) =
    some (cfg .read none {input := s,power := 1}) := by
  simp [FinTM2.step,TM2.step,machine,cfg,Data.stacks,TM2.stepAux,initList]
  congr 1; funext k; fin_cases k <;> rfl

/-- Actual execution of the finite machine, including cleanup of all eight auxiliary stacks. -/
theorem full_run (a : ℕ) (tail : Str) :
    run (time a tail) (some (initList machine (encNat a++tail))) =
      some (haltList machine (outputCode a tail)) := by
  let c := Nat.clog 2 a
  let p := 2^c
  have hp : 0<p := pow_pos (by decide : 0<2) c
  have h1 : run 1 (some (initList machine (encNat a++tail))) =
      some (cfg .read none {input := encNat a++tail,power := 1}) := init_step _
  have h2 : run (a+1) (some (cfg .read none {input := encNat a++tail,power := 1})) =
      some (cfg .compare (some false) {input := tail,target := a,power := 1}) := by
    simpa only [Nat.zero_add] using read_run none {power := 1} a tail
  have h3 : run (loopTime a 1 c)
      (some (cfg .compare (some false) {input := tail,target := a,power := 1})) =
      some (cfg .reverseTail none {input := tail,target := a,power := p,exponent := c}) := by
    simpa only [loopData,Nat.one_mul,Nat.zero_add,p] using
      loop_run c a 1 (some false) {input := tail} (by decide)
        (fun i hi => by simpa using Nat.pow_lt_of_lt_clog hi)
        (by simpa using Nat.le_pow_clog (by decide : 1<2) a)
  have h4 : run (2*tail.length+(p-1)+c+a+5)
      (some (cfg .reverseTail none {input := tail,target := a,power := p,exponent := c})) =
      some (haltList machine (outputCode a tail)) := by
    simpa only [Nat.sub_add_cancel (by omega : 1≤p),outputCode,c,p] using finish_run none a (p-1) c tail
  have hr := run_trans h1 (run_trans h2 (run_trans h3 h4))
  have ht : 1+((a+1)+(loopTime a 1 c+(2*tail.length+(p-1)+c+a+5))) = time a tail := by
    unfold loopTime time
    change 1+(a+1+(6*1*(2^c-1)+5*c+3*a+3+(2*tail.length+(p-1)+c+a+5))) =
      5*a+7*p+6*c+2*tail.length+3
    have he : 2^c=p := rfl
    rw [he]
    omega
  rw [ht] at hr
  exact hr

lemma clog_bound (a : ℕ) : Nat.clog 2 a ≤ a :=
  Nat.clog_le_of_le_pow (Nat.lt_pow_self (by decide : 1<2)).le

lemma power_bound (a : ℕ) : 2^(Nat.clog 2 a) ≤ 2*a+1 := by
  by_cases hc : Nat.clog 2 a=0
  · simp [hc]
  · have hp : 0<Nat.clog 2 a := by omega
    have hs := Nat.pow_lt_of_lt_clog (show Nat.clog 2 a-1<Nat.clog 2 a by omega)
    have he : 2^(Nat.clog 2 a)=2*2^(Nat.clog 2 a-1) := by
      calc
        2^(Nat.clog 2 a) = 2^((Nat.clog 2 a-1)+1) := by congr 1; omega
        _ = 2*2^(Nat.clog 2 a-1) := by rw [pow_succ]; omega
    rw [he]
    omega

noncomputable def timePolynomial : Polynomial ℕ := 100*(Polynomial.X+1)

lemma time_bound (a : ℕ) (tail : Str) :
    time a tail ≤ timePolynomial.eval (encNat a++tail).length := by
  have hc := clog_bound a
  have hp := power_bound a
  simp only [timePolynomial,Polynomial.eval_mul,Polynomial.eval_ofNat,Polynomial.eval_add,
    Polynomial.eval_X,Polynomial.eval_one,List.length_append,Main.Encoding.encNat_length]
  unfold time
  omega

/-- An actual polynomially timed FinTM2 witness, on every encoded unary field and payload. -/
noncomputable def outputs (a : ℕ) (tail : Str) :
    TM2OutputsInTime machine (encNat a++tail) (some (outputCode a tail))
      (timePolynomial.eval (encNat a++tail).length) where
  steps := time a tail
  evals_in_steps := full_run a tail
  steps_le_m := time_bound a tail

/-- Total string interface; valid source streams use its exact unary-prefix equation below. -/
def compile (s : Str) : Str :=
  match Main.Encoding.parseNat s with
  | none => []
  | some (a,tail) => outputCode a tail







end QMAPerfectCompleteness.Uniformity.UnaryNextPowerTM
Source
Formalization auxiliary for ~/research/qma1z/main.tex, the uniform circuit implementation supporting Section 3.3 and the proof of Theorem 1.1. Original Lean source: commit bbe19efbde567e5c8f7fe21655fd0c4da3573e4d, Solutions/UnaryNextPowerCorrectness.lean, retained declaration span lines 10–169.

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