HvdH machine lemma exp_inv_all (`expBits` as a register program)
ProvedNLogN.exp_inv_allThe following holds (Lean statement, in the scope of module NLogN.HNumExp):
theorem NLogN.exp_inv_all (n : ℕ) (x y : ℤ) (s : IState HS) (L5 L6 L7 : List Item)
(h5 : s.G 5 = .int n :: L5) (h6 : s.G 6 = .int x :: L6) (h7 : s.G 7 = .int y :: L7) :
∀ k ≤ 2 * n + 13, expInv (2 * n + 9) (2 * n + 13) (x * 2 ^ (n + 9)) (y * 2 ^ (n + 9)) s k
(NLogN.RS.repSt 39 eKE expBody (expPre.run s) k)
Context. The lemma belongs to the part expBits as a register program: Inputs n on register 5, x on 6, y on 7; the two components of expBits n x y are
pushed on registers 8 and 9. Scratch registers 30 … 39.
Formalization Note. This is a lemma of the Lean development NLogN, a multitape-Turing-machine implementation of the Harvey–van der Hoeven 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 .
-- 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
theorem NLogN.exp_inv_all (n : ℕ) (x y : ℤ) (s : IState HS) (L5 L6 L7 : List Item)
(h5 : s.G 5 = .int n :: L5) (h6 : s.G 6 = .int x :: L6) (h7 : s.G 7 = .int y :: L7) :
∀ k ≤ 2 * n + 13, expInv (2 * n + 9) (2 * n + 13) (x * 2 ^ (n + 9)) (y * 2 ^ (n + 9)) s k
(NLogN.RS.repSt 39 eKE expBody (expPre.run s) k) := by sorry