HvdH Proposition 4.7(i) — one-dimensional Gaussian resampling
ProvedIntMul.HvdH.proposition_4_7_icomplexity-theoryinteger-multiplication
Let (the working precision) and let be integers with and . Let be an integer with , put , and assume . Then there exist -linear maps and with such that
Here is the normalised DFT and norms are operator norms for the supremum norm. In the paper and , built from the maps of §4.1–4.2; the proof combines Theorem 4.2, Lemma 4.5 and Lemma 4.6 (all on the platform). Part (ii) of the proposition (fast numerical approximations of ) is a statement about Turing-machine costs and is not part of this theorem.
Formalization note: dft and theta are from IntMul_HvdH_Resampling.
Preamble
import Mathlib import Definitions.Def_IntMul_HvdH_Resampling
Formal statement
namespace IntMul.HvdH
theorem proposition_4_7_i (p s t : ℕ) [NeZero s] [NeZero t] (hp : 100 ≤ p) (hs : 2 ≤ s)
(hst : s < t) (htp : t < 2 ^ p) (hcop : Nat.Coprime s t) (α : ℕ) (hα : 2 ≤ α)
(hαp : (α : ℝ) < Real.sqrt p) (hθ : (p : ℝ) / α ^ 4 ≤ theta s t) :
∃ A : (ZMod s → ℂ) →L[ℂ] (ZMod t → ℂ), ∃ B : (ZMod t → ℂ) →L[ℂ] (ZMod s → ℂ),
‖A‖ ≤ 1 ∧ ‖B‖ ≤ 1 ∧ dft s = ((2 : ℂ) ^ (2 * α ^ 2)) • (B.comp ((dft 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), Proposition 4.7, part (i), p. 29 (precision p ≥ 100 from §2.2, p. 8).