Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

HvdH machine lemma scaleZP_top (`twD` as a register program)

Proved
NLogN.scaleZP_top

by xuanji · Oct 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

harvey-van-der-hoeven-tminteger-multiplicationturing-machines

The following holds (Lean statement, in the scope of module NLogN.HNumTwD):

theorem NLogN.scaleZP_top (s : IState HS) (h10 : s.IsInt 10) (h10' : 0 ≤ s.top 10)
    (h11 : s.IsInt 11) (h11' : 0 ≤ s.top 11) (h12 : s.IsInt 12) (h13 : s.IsInt 13)
    (h14 : s.IsInt 14) (h14' : 0 ≤ s.top 14) (hx : |s.top 12| < 2 ^ (s.top 14).toNat)
    (hy : |s.top 13| < 2 ^ (s.top 14).toNat) :
    scaleZP.ok s ∧ scaleZP.run s = (s.upd 15 (.int (scaleZ (s.top 10).toNat (s.top 11).toNat
      (s.top 12, s.top 13)).1 :: s.G 15)).upd 16 (.int (scaleZ (s.top 10).toNat (s.top 11).toNat
      (s.top 12, s.top 13)).2 :: s.G 16) ∧
    scaleZP.cost s ≤ scaleCost (s.top 10).toNat (s.top 11).toNat (s.top 14).toNat

Context. The lemma belongs to the part twD as a register program: twDP: inputs p on 28, n on 29, j on 53; pushes (twD p n j).1 on 15 and (twD p n j).2 on 16. It runs twiddleP and then scaleZP with k = 0 and the bit bound twBz p (an upper bound for the size of the twiddle factors). Uses (pushed and popped) registers 10 … 14, 17 … 19, 41 … 44, 51, 52 and those of twiddleP.

Formalization Note. This is a lemma of the Lean development NLogN, a multitape-Turing-machine implementation of the Harvey–van der Hoeven O(nlog⁡n)O(n\log n)O(nlogn) integer multiplication algorithm, used in the proof of NLogN.FIN.theorem_1_1_nlogn : IntMul.MulTimeBound fun n => n * Real.log n. All names refer to the definition bundles IntMul_HvdH_M_Defs1–IntMul_HvdH_M_Defs8 (namespace NLogN), built on the platform model Def_IntMul_MultitapeModel and the published reference Def_IntMul_HvdH_MachineRef. The machine layer: IState HS is a state of 64 item stacks; RM programs have a semantics p.run s, a definedness predicate p.ok M s and a cost p.cost M s relative to a multiplication spec M : MulSpec; zsz z is the bit length of ∣z∣|z|∣z∣.

Preamble
-- Harvey–van der Hoeven multitape-TM development (NLogN), generated by skeleton subtraction.

import Definitions.Def_IntMul_HvdH_M_Defs8

set_option autoImplicit false
set_option relaxedAutoImplicit false
set_option maxHeartbeats 1000000

set_option linter.unusedSimpArgs false
open NLogN
open IntMul RS IntMul.HvdH
Formal statement
theorem NLogN.scaleZP_top (s : IState HS) (h10 : s.IsInt 10) (h10' : 0 ≤ s.top 10)
    (h11 : s.IsInt 11) (h11' : 0 ≤ s.top 11) (h12 : s.IsInt 12) (h13 : s.IsInt 13)
    (h14 : s.IsInt 14) (h14' : 0 ≤ s.top 14) (hx : |s.top 12| < 2 ^ (s.top 14).toNat)
    (hy : |s.top 13| < 2 ^ (s.top 14).toNat) :
    scaleZP.ok s ∧ scaleZP.run s = (s.upd 15 (.int (scaleZ (s.top 10).toNat (s.top 11).toNat
      (s.top 12, s.top 13)).1 :: s.G 15)).upd 16 (.int (scaleZ (s.top 10).toNat (s.top 11).toNat
      (s.top 12, s.top 13)).2 :: s.G 16) ∧
    scaleZP.cost s ≤ scaleCost (s.top 10).toNat (s.top 11).toNat (s.top 14).toNat := by sorry
Source
D. Harvey, J. van der Hoeven, Integer multiplication in time O(n log n), Ann. of Math. 193 (2021), 563–617 (Theorem 1.1: multitape Turing machine multiplication in O(n log n)). Lemma `NLogN.scaleZP_top` of the Lean development NLogN/HNumTwD.lean (lines 18–31), written for the prove2.me integer-multiplication campaign.

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me