Machine-level form of the community construction at (PR #6453)
OpenIntMul.Kappa.pr6453_machine_polylogcomplexity-theoryinteger-multiplicationturing-machines
There is one deterministic multitape Turing machine , in the model of Def_IntMul_MultitapeModel, and a real exponent saving such that
- halts with the correct output on every input with of length , in some finite number of steps; and
- there are constants , and a threshold with
where is the worst-case step count over -bit inputs and .
This is the machine-level form of the community construction at (PR #6453 of CrocSwap/integer-mult-bounds, a third group-1091 anchor stacked on the mixed-root composition of PR #6417): the scheduling, precision and tape-movement analysis of the construction, stated with its usual polylogarithmic overhead. It is deliberately a little stronger than the exponent , since the polylogarithmic factor has to be absorbed; the platform lemma IntMul.Kappa.kappaBound_of_polylog_slack removes it and yields IntMul.Kappa.KappaBound 0.003287014.
Preamble
import Definitions.Def_IntMul_MultitapeModel set_option autoImplicit false
Formal statement
namespace IntMul.Kappa
theorem pr6453_machine_polylog :
∃ (M : MultitapeTM) (g C : ℝ) (A n₀ : ℕ),
0.0032871 < g ∧ 0 < C ∧
(∀ n : ℕ, 1 ≤ n → ∃ T : ℝ, MultipliesAt M n T) ∧
(∀ n : ℕ, n₀ ≤ n →
MultipliesAt M n (C * n * (lg n : ℝ) ^ (1 - g) * (Real.log (lg n) + 1) ^ A)) := by
sorry
end IntMul.KappaSource
CrocSwap/integer-mult-bounds, PR #6453 (third group-1091 anchor on the PR #6417 mixed-root composition), https://github.com/CrocSwap/integer-mult-bounds/pull/6453 ; the construction is stated conditionally on the five inherited framework assumptions (native_all_columns, owned_erasure, compiler, precision_tape, analytic_recovery) in the pinned revision https://github.com/CrocSwap/integer-mult-bounds/tree/56b66d58297deca1d7dd130247d720e960f77a37 . This node is those assumptions, transcribed into the multitape-machine cost model of Def_IntMul_MultitapeModel.