HvdH Theorem 4.1 (first part) — Gaussian resampling
ProvedIntMul.HvdH.theorem_4_1_icomplexity-theoryinteger-multiplication
Let and . Let and be integers with and . Let be an integer with , put , and assume for every . Then there exist -linear maps and with such that
In the paper are tensor products of the one-dimensional maps of Proposition 4.7(i). The theorem's second assertion (numerical approximations and their cost) concerns Turing-machine costs and is not part of this statement.
Formalization note: arrays are functions on with the supremum norm; is dftN from IntMul_HvdH_Tensor and is theta from IntMul_HvdH_Resampling.
Preamble
import Mathlib import Definitions.Def_IntMul_HvdH_Resampling import Definitions.Def_IntMul_HvdH_Tensor
Formal statement
namespace IntMul.HvdH
theorem theorem_4_1_i (d p : ℕ) (hd : 1 ≤ d) (hp : 100 ≤ p) (s t : Fin d → ℕ)
[∀ i, NeZero (s i)] [∀ i, NeZero (t i)] (hs : ∀ i, 2 ≤ s i) (hst : ∀ i, s i < t i)
(htp : ∀ i, t i < 2 ^ p) (hcop : ∀ i, Nat.Coprime (s i) (t i)) (α : ℕ) (hα : 2 ≤ α)
(hαp : (α : ℝ) < Real.sqrt p) (hθ : ∀ i, (p : ℝ) / α ^ 4 ≤ theta (s i) (t i)) :
∃ A : (TIdx s → ℂ) →L[ℂ] (TIdx t → ℂ), ∃ B : (TIdx t → ℂ) →L[ℂ] (TIdx s → ℂ),
‖A‖ ≤ 1 ∧ ‖B‖ ≤ 1 ∧
dftN s = ((2 : ℂ) ^ (2 * d * α ^ 2)) • (B.comp ((dftN t).comp A)) := by sorry
end IntMul.HvdHSource
D. Harvey, J. van der Hoeven, Integer multiplication in time O(n log n), Ann. of Math. 193 (2021), https://doi.org/10.4007/annals.2021.193.2.4 (preprint https://hal.science/hal-02070778v2), Theorem 4.1, first assertion, p. 23 (precision p ≥ 100 from §2.2, p. 8).