PR #6453: the register-machine glue to
OpenIntMul.Kappa.pr6453_kappaBound_of_RMThe machine-level statement for the PR #6453 construction, modelled on the campaign's NLogN.Top.hv_mulTimeBound.
Let be a register machine satisfying the campaign's step-cost interface StepOK with linear part and recursive call list , and let be its worst-case cost, equal to at . Suppose the local work at each node is below and that one level of the recursion costs at most a fraction of the product it produces:
Then the construction meets the platform bound KappaBound 0.003287014, i.e. there is a deterministic multitape Turing machine computing exact products in time .
The first cost condition is the campaign's hL (local work), the second is the hR contraction that my Pr6453.recursion discharges from the invoice's price inequality. The missing ingredient is the machine itself: this node states the interface a machine proof must meet, exactly as hv_mulTimeBound does for .
import Definitions.Def_IntMul_HvdH_M_Defs4 import Definitions.Def_IntMul_MultitapeModel set_option autoImplicit false set_option maxHeartbeats 1000000 open NLogN open NLogN.Top open IntMul NLogN
namespace IntMul.Kappa
theorem pr6453_kappaBound_of_RM {n₀ : ℕ} {st : RM} {lin : ℕ → ℕ} {calls : ℕ → List (ℕ × ℕ)}
(hst : StepOK st n₀ lin calls) (K D : ℕ) (hD : 1 ≤ D) (T : ℕ → ℝ) (hT : 0 < K)
(hcost : ∀ N, n₀ ≤ N →
T N = (N : ℝ) * ((IntMul.lg N : ℝ) ^ (1 - (0.003287014 : ℝ))))
(hL : ∀ N, n₀ ≤ N → (topCost n₀ N : ℝ) + (lin N : ℝ) + 2 ≤ (K : ℝ) * T N)
(hR : ∀ N, n₀ ≤ N →
(D : ℝ) * (((calls N).map fun q => (q.1 : ℝ) * T q.2).sum) + T N ≤ (D : ℝ) * T N) :
IntMul.KappaBound (0.003287014 : ℝ) := by
sorry
end IntMul.Kappa