HvdH machine lemma AX.tmpP_all (One resampling axis, part 7: derived scalars and table removal for the)
ProvedNLogN.AX.tmpP_allThe following holds (Lean statement, in the scope of module NLogN.HAx7):
theorem NLogN.AX.tmpP_all (e s α B : ℕ) (st : IState HS) (hα : 1 ≤ α)
(hNR : ∃ L, st.G bNR = .int ((2 * e + 1 : ℕ) : ℤ) :: L) (hS : ∃ L, st.G bS = .int (s : ℤ) :: L)
(hA : ∃ L, st.G bI = .int ((α ^ 2 : ℕ) : ℤ) :: L)
(hB1 : 2 * e + 2 < 2 ^ B) (hB2 : s ^ 2 < 2 ^ B) (hB3 : 2 * α ^ 2 + 2 < 2 ^ B) :
tmpP.ok st ∧ tmpP.run st = tmpSt e s α st ∧ tmpP.cost st ≤ 16 * 10 ^ 7 * (B + 2) ^ 2
Context. The lemma belongs to the part One resampling axis, part 7: derived scalars and table removal for the B̃ axis.
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 NLogN.AX open IntMul NLogN IntMul.HvdH.Ref NLogN.GL NLogN.Rsp
theorem NLogN.AX.tmpP_all (e s α B : ℕ) (st : IState HS) (hα : 1 ≤ α)
(hNR : ∃ L, st.G bNR = .int ((2 * e + 1 : ℕ) : ℤ) :: L) (hS : ∃ L, st.G bS = .int (s : ℤ) :: L)
(hA : ∃ L, st.G bI = .int ((α ^ 2 : ℕ) : ℤ) :: L)
(hB1 : 2 * e + 2 < 2 ^ B) (hB2 : s ^ 2 < 2 ^ B) (hB3 : 2 * α ^ 2 + 2 < 2 ^ B) :
tmpP.ok st ∧ tmpP.run st = tmpSt e s α st ∧ tmpP.cost st ≤ 16 * 10 ^ 7 * (B + 2) ^ 2 := by sorry