HvdH Proposition 5.4, step (3) — final error estimate
ProvedIntMul.HvdH.proposition_5_4_step3complexity-theoryinteger-multiplication
Let be natural numbers with
and let be vectors in a finite-dimensional space (supremum norm) with
Then, with ,
This is the numerical heart of step (3) of the proof of Proposition 5.4: the bound is the error guarantee of Proposition 5.3, and the conclusion lets one recover the integer array exactly by rounding . (The paper's chain: , using , and .)
Preamble
import Mathlib
Formal statement
namespace IntMul.HvdH
theorem proposition_5_4_step3 (n b p γ T S : ℕ) (hb : 4096 ≤ b) (hp : p = 6 * b)
(hγ : (γ : ℝ) < 8 * (b : ℝ) ^ ((2 : ℝ) / 3)) (hT1 : 1 ≤ T) (hTn : T < n) (hn : n ≤ 2 ^ b)
(hTb : T * b < 8 * n) (hS : S ≤ T) {ι : Type*} [Fintype ι] (w w' : ι → ℂ)
(herr : (2 : ℝ) ^ p * ‖w' - w‖ < (2 : ℝ) ^ (γ + 8) * (T : ℝ) ^ 2 * Real.logb 2 T) :
‖((2 : ℂ) ^ (2 * b) * S) • w - ((2 : ℂ) ^ (2 * b) * S) • w'‖ < 1 / 4 := 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), proof of Proposition 5.4, step (3), p. 41 (the displayed estimates leading to ‖H'' − 2^{2b} S w̃‖ < 1/4), with (5.5), (5.6), (5.9).