HvdH §5.1 — parameter estimates (5.1)–(5.9)
ProvedIntMul.HvdH.parameters_5_1complexity-theoryinteger-multiplication
Let and . Define
let be the power of two with , and let be the power of two with . Then:
- (5.1), (5.2): and ;
- (5.4): ;
- (5.5): ;
- (5.8): ;
- (5.9): and ;
- the factorisation: there is with (so with and ), and , so every .
Formalization note: is Nat.clog 2 n; real powers are Real.rpow; is natural-number division (exact, since is a power of two). and are universally quantified but uniquely determined by the hypotheses.
Preamble
import Mathlib
Formal statement
namespace IntMul.HvdH
theorem parameters_5_1 (d : ℕ) (hd : 2 ≤ d) (n : ℕ) (hn : 2 ^ (d ^ 12) ≤ n)
(b p α γ T r : ℕ) (hb : b = Nat.clog 2 n) (hp : p = 6 * b)
(hα : α = ⌈((12 * d ^ 2 * b : ℕ) : ℝ) ^ ((1 : ℝ) / 4)⌉₊) (hγ : γ = 2 * d * α ^ 2)
(hTpow : ∃ k : ℕ, T = 2 ^ k) (hT1 : 4 * (n : ℝ) / b ≤ T) (hT2 : (T : ℝ) < 8 * (n : ℝ) / b)
(hrpow : ∃ j : ℕ, r = 2 ^ j) (hr1 : (T : ℝ) ^ ((1 : ℝ) / d) ≤ r)
(hr2 : (r : ℝ) < 2 * (T : ℝ) ^ ((1 : ℝ) / d)) :
-- (5.1), (5.2)
(d ^ 12 ≤ b ∧ 4096 ≤ b ∧ 100 ≤ p) ∧
-- (5.4)
(2 ≤ α ∧ (α : ℝ) < 2 * (b : ℝ) ^ ((7 : ℝ) / 24) ∧
2 * (b : ℝ) ^ ((7 : ℝ) / 24) < Real.sqrt p) ∧
-- (5.5)
(γ : ℝ) < 8 * (b : ℝ) ^ ((2 : ℝ) / 3) ∧
-- (5.8)
2 ^ (d ^ 10) ≤ r ∧
-- (5.9)
(T < n ∧ n ≤ 2 ^ b ∧ T < 2 ^ p) ∧
-- the factorisation `T = t₁ ⋯ t_d` with `t₁ = ⋯ = t_{d'} = r/2`, `t_{d'+1} = ⋯ = t_d = r`
(∃ d' : ℕ, d' < d ∧ (r / 2) ^ d' * r ^ (d - d') = T) ∧ 4 ≤ r := 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), §5 preamble and §5.1 Parameter selection, equations (5.1), (5.2), (5.3), (5.4), (5.5), (5.6), (5.7), (5.8), (5.9) and the factorisation T = t1···td, pp. 36–37.