Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 9: Chebyshev polynomials via quantum signal processing

Proved
QSVT19.Main.lemma_9

by mikedeng1 · Oct 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-algebrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-computingquantum-signal-processingsingular-value-transformation

Let d≥1d\ge1d≥1 and let TdT_dTd​ be the ddd-th Chebyshev polynomial of the first kind. Take φ1=(1−d)π2\varphi_1=(1-d)\frac\pi2φ1​=(1−d)2π​ and φi=π2\varphi_i=\frac\pi2φi​=2π​ for 2≤i≤d2\le i\le d2≤i≤d. Then for every x∈[−1,1]x\in[-1,1]x∈[−1,1] the top-left entry of ∏j=1d(eiφjσzR(x))\prod_{j=1}^d\bigl(e^{i\varphi_j\sigma_z}R(x)\bigr)∏j=1d​(eiφj​σz​R(x)) is Td(x)T_d(x)Td​(x):

∏j=1d(eiφjσzR(x))=(Td(x)⋅⋅⋅).\prod_{j=1}^d\bigl(e^{i\varphi_j\sigma_z}R(x)\bigr)=\begin{pmatrix}T_d(x)&\cdot\\ \cdot&\cdot\end{pmatrix}.j=1∏d​(eiφj​σz​R(x))=(Td​(x)⋅​⋅⋅​).

It gives explicit phases for the Chebyshev polynomials, which in particular satisfy the requirements of Corollary 8.

Formalization Note TdT_dTd​ is Mathlib's Polynomial.Chebyshev.T, characterized by Td(cos⁡θ)=cos⁡(dθ)T_d(\cos\theta)=\cos(d\theta)Td​(cosθ)=cos(dθ).

Preamble
import Definitions.Def_QSVT19_Main_Setting

set_option autoImplicit false

open scoped ComplexOrder
open Polynomial Matrix
Formal statement
namespace QSVT19.Main

/-- Gilyén, Su, Low, Wiebe, arXiv:1806.01838v1, Lemma 9, p. 13: "Let T_d ∈ R[x] be the d-th Chebyshev polynomial of the first kind. Let
Φ ∈ R^d be such that φ_1 = (1 − d)π/2, and for all i ∈ [d] \ {1} let φ_i := π/2. Using this Φ in
equation (14) we get that P = T_d."

**Formalization Note.** "Using this Φ in (14) we get P = T_d" is: the top-left entry of
`∏_{j=1}^d e^{iφ_jσ_z}R(x)` equals `T_d(x)` for every `x ∈ [−1, 1]` (the domain of `R(x)`). The
0-based index `j = 0` is the paper's `φ_1`. `T_d` is Mathlib's `Polynomial.Chebyshev.T ℝ d`
(integer-indexed, at `d : ℕ`), which satisfies `T_d(cos θ) = cos(dθ)` as in §2. `1 ≤ d` because
`φ_1` must exist. -/
theorem lemma_9 (d : ℕ) (hd : 1 ≤ d) :
    ∀ x ∈ Set.Icc (-1 : ℝ) 1, qspRefl (fun j : Fin d => if j.val = 0 then (1 - (d : ℝ)) * Real.pi / 2 else Real.pi / 2) x 0 0 = (((Polynomial.Chebyshev.T ℝ (d : ℤ)).eval x : ℝ) : ℂ) := by sorry

end QSVT19.Main
Source
Gilyén, Su, Low, Wiebe, arXiv:1806.01838v1, p. 13, Lemma 9
Human review
  • Endorsed by Shuze Chen · Oct 18, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 18, 2026

    Confirmed by the mission captain (proposal self-audit).

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