Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

HvdH §2.4 — y2r/ny^{2r/n}y2r/n is a principal nnn-th root of unity in C[y]/(yr+1)\mathbb C[y]/(y^r+1)C[y]/(yr+1)

Proved
IntMul.HvdH.synthetic_root

by avi · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinteger-multiplication

Let r≥2r\ge2r≥2 be a power of two, let R=C[y]/(yr+1)\mathcal R=\mathbb C[y]/(y^r+1)R=C[y]/(yr+1) with basis 1,y,…,yr−11,y,\dots,y^{r-1}1,y,…,yr−1, and let n≥1n\ge1n≥1 divide 2r2r2r. Then ω:=y2r/n\omega:=y^{2r/n}ω:=y2r/n is a principal nnn-th root of unity in R\mathcal RR:

  1. ωn=1\omega^n=1ωn=1;
  2. ∑k=0n−1(ωj)k=0\sum_{k=0}^{n-1}(\omega^j)^k=0∑k=0n−1​(ωj)k=0 for every j≥0j\ge0j≥0 with n∤jn\nmid jn∤j;
  3. multiplication by ω\omegaω preserves the norm ∥λ0+λ1y+⋯+λr−1yr−1∥=max⁡i∣λi∣\|\lambda_0+\lambda_1y+\dots+\lambda_{r-1}y^{r-1}\|=\max_i|\lambda_i|∥λ0​+λ1​y+⋯+λr−1​yr−1∥=maxi​∣λi​∣.

Formalization note: R\mathcal RR is AdjoinRoot (X^r + 1) over C\mathbb CC, and the coefficients λi\lambda_iλi​ of an element are those of its unique representative of degree <r<r<r (AdjoinRoot.modByMonicHom). Item 3 is stated as: for every real BBB, all coefficients of ωu\omega uωu have modulus ≤B\le B≤B iff all coefficients of uuu do, which is equivalent to ∥ωu∥=∥u∥\|\omega u\|=\|u\|∥ωu∥=∥u∥. Item 2 uses natural jjj; since ωn=1\omega^n=1ωn=1 this is equivalent to the paper's condition for all integers jjj.

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.HvdH
Source
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).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me