Ordinary polynomial products and charged finite-tape time bounds
DefinitionFastMul_BinaryTaskFor each positive coefficient length , binary inputs represent ordinary polynomials over . The output word lists every coefficient of their ordinary product in ascending degree order, including zero coefficients, and has exactly bits.
For a rational , the time predicate requires one fixed deterministic finite-tape machine, a constant and a threshold , chosen before every input. Every positive input must halt with the complete literal output; for its transition count is at most .
The extension predicate fixes each finite field of characteristic two before choosing a positive bit width, an injective coefficient encoding, a machine and its constants. It counts coefficient length and encodes every output coefficient in the same fixed width.
The generic machine and its actual transitions are reused from the published IntMul_MultitapeModel definition. Its integer-value and integer-product predicates are not used. These definitions state tasks and do not prove existence of a fast algorithm.
import Definitions.Def_IntMul_MultitapeModel
set_option autoImplicit false
universe u
namespace FastMulPlatform
noncomputable def polynomialOf {F : Type u} [Semiring F] {n : ℕ}
(f : Fin n → F) : Polynomial F :=
∑ i : Fin n, Polynomial.C (f i) * Polynomial.X ^ i.val
def bitCoefficient (b : Bool) : ZMod 2 := if b then 1 else 0
noncomputable def binaryProductWord {n : ℕ} (f g : Fin n → Bool) : List Bool :=
List.ofFn fun j : Fin (2 * n - 1) =>
decide (((polynomialOf (fun i => bitCoefficient (f i))) *
(polynomialOf (fun i => bitCoefficient (g i)))).coeff j.val = 1)
def logScale (n : ℕ) : ℕ := max (Nat.clog 2 n) 1
noncomputable def timeEnvelope (κ : ℚ) (n : ℕ) : ℝ :=
(n : ℝ) * (logScale n : ℝ) ^ (1 - (κ : ℝ))
def BinaryTimeBound (κ : ℚ) : Prop :=
0 ≤ κ ∧ κ ≤ 1 ∧
∃ (M : IntMul.MultitapeTM) (C : ℝ) (n₀ : ℕ),
0 < C ∧
∀ n : ℕ, 1 ≤ n → ∀ f g : Fin n → Bool,
∃ t : ℕ,
M.HaltsWithOutput (List.ofFn f) (List.ofFn g) t (binaryProductWord f g) ∧
(n₀ ≤ n → (t : ℝ) ≤ C * timeEnvelope κ n)
def encodeCoefficients {F : Type u} {n w : ℕ}
(encode : F → Fin w → Bool) (f : Fin n → F) : List Bool :=
(List.ofFn f).flatMap fun a => List.ofFn (encode a)
noncomputable def fieldProductWord {F : Type u} [Semiring F] {n w : ℕ}
(encode : F → Fin w → Bool) (f g : Fin n → F) : List Bool :=
encodeCoefficients encode
(fun j : Fin (2 * n - 1) => ((polynomialOf f) * (polynomialOf g)).coeff j.val)
def FixedCharTwoTimeBound (κ : ℚ) : Prop :=
0 ≤ κ ∧ κ ≤ 1 ∧
∀ (F : Type u) [Field F] [Fintype F] [CharP F 2],
∃ (w : ℕ) (encode : F → Fin w → Bool),
0 < w ∧ Function.Injective encode ∧
∃ (M : IntMul.MultitapeTM) (C : ℝ) (n₀ : ℕ),
0 < C ∧
∀ n : ℕ, 1 ≤ n → ∀ f g : Fin n → F,
∃ t : ℕ,
M.HaltsWithOutput (encodeCoefficients encode f)
(encodeCoefficients encode g) t (fieldProductWord encode f g) ∧
(n₀ ≤ n → (t : ℝ) ≤ C * timeEnvelope κ n)
end FastMulPlatform
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.