HvdH §2.4 — is a principal -th root of unity in
ProvedIntMul.HvdH.synthetic_rootcomplexity-theoryinteger-multiplication
Let be a power of two, let with basis , and let divide . Then is a principal -th root of unity in :
- ;
- for every with ;
- multiplication by preserves the norm .
Formalization note: is AdjoinRoot (X^r + 1) over , and the coefficients of an element are those of its unique representative of degree (AdjoinRoot.modByMonicHom). Item 3 is stated as: for every real , all coefficients of have modulus iff all coefficients of do, which is equivalent to . Item 2 uses natural ; since this is equivalent to the paper's condition for all integers .
Preamble
import Mathlib
Formal statement
namespace IntMul.HvdH
open Polynomial
theorem synthetic_root (r : ℕ) (hr : 2 ≤ r) (hpow : ∃ k : ℕ, r = 2 ^ k) (n : ℕ) (hn : 0 < n)
(hdiv : n ∣ 2 * r) :
let hmon : (X ^ r + C (1 : ℂ)).Monic := monic_X_pow_add_C 1 (by omega)
let ω : AdjoinRoot (X ^ r + C (1 : ℂ)) := AdjoinRoot.root _ ^ (2 * r / n)
let c : AdjoinRoot (X ^ r + C (1 : ℂ)) → ℕ → ℂ := fun u i =>
(AdjoinRoot.modByMonicHom hmon u).coeff i
ω ^ n = 1 ∧
(∀ j : ℕ, ¬ n ∣ j → ∑ k ∈ Finset.range n, (ω ^ j) ^ k = 0) ∧
(∀ (u : AdjoinRoot (X ^ r + C (1 : ℂ))) (B : ℝ),
(∀ i < r, ‖c (ω * u) i‖ ≤ B) ↔ (∀ i < r, ‖c u i‖ ≤ B)) := 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), §2.4, synthetic case (2), pp. 12–13 (with the definition of principal root of unity on p. 12 and the norm on R from §2.3).