LeanFun RevOLVER

2.1 Chebyshev weights and orthogonality

Chebyshev expansions represent functions on \([-1,1]\) using polynomials tied to cosine series. The two Chebyshev weights give the orthogonality relations from which coefficients are computed.

2.1.1 The polynomials and their trigonometric form

The three-term recurrence defines polynomials; the cosine formula explains their use on \([-1,1]\).

Definition 2.1.1 Chebyshev polynomials Mathlib
✓
#

For a commutative ring \(R\) and every integer \(n\), define \(T_n,U_n\in R[X]\) by \(T_0=U_0=1\), \(T_1=X\), \(U_1=2X\), and the common recurrence \(p_{n+2}=2Xp_{n+1}-p_n\), run forwards for nonnegative and backwards for negative indices.

Reference: [DLMF, Table 18.9.1].

Lean Formalisation
def Polynomial.Chebyshev.T.{u_1} (R : Type u_1) [CommRing R] : ℤ → Polynomial R
Mathlib source
Theorem 2.1.2 Trigonometric form Mathlib
✓

For real \(\theta \) and integer \(n\), \(T_n(\cos \theta )=\cos n\theta \) and \(U_n(\cos \theta )\sin \theta =\sin (n+1)\theta \).

Reference: [DLMF, 18.5.1–18.5.2].

Lean Formalisation
theorem Polynomial.Chebyshev.T_real_cos (θ : ℝ) (n : ℤ) :
  Polynomial.eval (Real.cos θ) (Polynomial.Chebyshev.T ℝ n) = Real.cos (↑n * θ)
Mathlib source

2.1.2 The first-kind weight

The substitution \(x=\cos \theta \) converts integration against \(w_T\) into ordinary integration over \((0,\pi )\). The change-of-variable theorem below states this precisely.

Definition 2.1.3 Classical Chebyshev densities
✓ 🙂 human-reviewed

On the open interval \(I=(-1,1)\), define the continuous nonnegative weights \(w_U(x)=\sqrt{1-x^2}\) and \(w_T(x)=1/\sqrt{1-x^2}\).

Lean Formalisation
def Polynomial.Chebyshev.weightU : C(↑(Set.Ioo (-1) 1), NNReal)
Lean definition
/-- The second-kind density on its classical domain. -/
def weightU : C(Ioo (-1 : ℝ) 1, ℝ≥0) where
  toFun x := ⟨√(1 - (x : ℝ) ^ 2), sqrt_nonneg _⟩
  continuous_toFun := by apply Continuous.subtype_mk; fun_prop
source
Definition 2.1.4 First-kind weight measure
✓ 🙂 human-reviewed

Let \(\mu _T=\mu _{w_T}\) be the measure of Definition 1.1.2 for the weight \(w_T\) of Definition 2.1.3.

Reference: [DLMF, Table 18.3.1].

Lean Formalisation
def Polynomial.Chebyshev.classicalMeasureT : MeasureTheory.Measure ℝ
Lean definition
/-- The first-kind measure obtained from the subtype density. -/
def classicalMeasureT : Measure ℝ := openIntervalWeightMeasure (-1) 1 weightT
source
Theorem 2.1.5 First-kind integrability characterisation
✓ 🤖

A real function \(f\) is integrable for \(\mu _T\) exactly when \(x\mapsto w_T(x)f(x)\) is Lebesgue-integrable on \((-1,1)\). For \(f\in \mathcal I(\mu _T)\),

\[ \int f\, d\mu _T=\int _{x\in (-1,1)}w_T(x)f(x)\, dx. \]
Lean Formalisation
theorem Polynomial.Chebyshev.integrable_classicalMeasureT_iff (f : ℝ → ℝ) :
  MeasureTheory.Integrable f Polynomial.Chebyshev.classicalMeasureT ↔
    MeasureTheory.Integrable (fun x => ↑(Polynomial.Chebyshev.weightT x) * f ↑x) MeasureTheory.volume
Lean proof
/-- Integrability against the first-kind density. -/
theorem integrable_classicalMeasureT_iff (f : ℝ → ℝ) :
    Integrable f classicalMeasureT ↔
      Integrable (fun x : Ioo (-1 : ℝ) 1 ↦ (weightT x : ℝ) * f x) volume :=
  integrable_openIntervalWeightMeasure_iff _ _ _ _
source

Every real function continuous on \([-1,1]\) is \(\mu _T\)-integrable. For every \(f\in \mathcal I(\mu _T)\), the function \(\theta \mapsto f(\cos \theta )\) is integrable on \((0,\pi )\) and

\[ \int f\, d\mu _T=\int _0^\pi f(\cos \theta )\, d\theta . \]

For every integer \(n\), \(fT_n\) is also \(\mu _T\)-integrable. No continuity of \(f\) is required; integrable endpoint singularities are included.

Reference: [ATAP, Chapter 3].

Lean Formalisation
theorem Polynomial.Chebyshev.integrable_classicalMeasureT {f : ℝ → ℝ} (hf : ContinuousOn f (Set.Icc (-1) 1)) :
  MeasureTheory.Integrable f Polynomial.Chebyshev.classicalMeasureT
Lean proof
/-- Continuous inputs are integrable for the first-kind measure (DLMF 18.3). -/
theorem integrable_classicalMeasureT {f : ℝ → ℝ}
    (hf : ContinuousOn f (Icc (-1) 1)) : Integrable f classicalMeasureT := by
  rw [classicalMeasureT_eq]
  exact integrable_measureT hf
source
Theorem 2.1.7 First-kind orthogonality and norms
✓ 🤖

For natural \(n,m\), \(T_nT_m\) is integrable. For distinct \(n,m\), \(\int T_nT_m\, d\mu _T=0\). The squared norm of \(T_0\) is \(\pi \), and that of \(T_n\) for \(n{\gt}0\) is \(\pi /2\).

Reference: [DLMF, Table 18.3.1].

Lean Formalisation
theorem Polynomial.Chebyshev.classicalMeasureT_orthogonality (n m : ℕ) :
  MeasureTheory.Integrable
      (fun x => Polynomial.eval x (Polynomial.Chebyshev.T ℝ ↑n) * Polynomial.eval x (Polynomial.Chebyshev.T ℝ ↑m))
      Polynomial.Chebyshev.classicalMeasureT ∧
    ∫ (x : ℝ),
        Polynomial.eval x (Polynomial.Chebyshev.T ℝ ↑n) *
          Polynomial.eval x (Polynomial.Chebyshev.T ℝ ↑m) ∂Polynomial.Chebyshev.classicalMeasureT =
      if n = m then if n = 0 then Real.pi else Real.pi / 2 else 0
Lean proof
/-- First-kind orthogonality and squared norms, with integrability (DLMF 18.3). -/
theorem classicalMeasureT_orthogonality (n m : ℕ) :
    Integrable (fun x ↦ (T ℝ n).eval x * (T ℝ m).eval x) classicalMeasureT ∧
      (∫ x, (T ℝ n).eval x * (T ℝ m).eval x ∂classicalMeasureT) =
        if n = m then (if n = 0 then π else π / 2) else 0 := by
  refine ⟨integrable_classicalMeasureT (by fun_prop), ?_⟩
  rw [classicalMeasureT_eq]
  split_ifs with h hn
  · subst m; subst n; exact integral_eval_T_real_mul_self_measureT_zero
  · subst m; exact integral_T_real_mul_self_measureT_of_ne_zero hn
  · exact integral_eval_T_real_mul_eval_T_real_measureT_of_ne h
source
Density formulas and first-kind moments
Theorem 2.1.8 Chebyshev density characterisation
✓ 🙂 human-reviewed

For every \(x\in I\), \(w_U(x)=\sqrt{1-x^2}\) and \(w_T(x)=1/\sqrt{1-x^2}\).

Lean Formalisation
theorem Polynomial.Chebyshev.weightUT_apply (x : ↑(Set.Ioo (-1) 1)) :
  ↑(Polynomial.Chebyshev.weightU x) = √(1 - ↑x ^ 2) ∧ ↑(Polynomial.Chebyshev.weightT x) = (√(1 - ↑x ^ 2))⁻¹
Lean proof
/-- Characterization of the two classical densities. -/
theorem weightUT_apply (x : Ioo (-1 : ℝ) 1) :
    (weightU x : ℝ) = √(1 - (x : ℝ) ^ 2) ∧
      (weightT x : ℝ) = (√(1 - (x : ℝ) ^ 2))⁻¹ := ⟨rfl, rfl⟩
source
Theorem 2.1.9 First-kind moments
✓ 🤖

For integer \(k\), \(T_k\) is integrable and \(\int T_k\, d\mu _T=\pi \) if \(k=0\), and is zero otherwise.

Reference: [DLMF, Table 18.3.1].

Lean Formalisation
theorem Polynomial.Chebyshev.classicalMeasureT_moments (n : ℤ) :
  MeasureTheory.Integrable (fun x => Polynomial.eval x (Polynomial.Chebyshev.T ℝ n))
      Polynomial.Chebyshev.classicalMeasureT ∧
    ∫ (x : ℝ), Polynomial.eval x (Polynomial.Chebyshev.T ℝ n) ∂Polynomial.Chebyshev.classicalMeasureT =
      if n = 0 then Real.pi else 0
Lean proof
/-- First-kind moments, with integrability, for all integer indices (DLMF 18.3). -/
theorem classicalMeasureT_moments (n : ℤ) :
    Integrable (fun x ↦ (T ℝ n).eval x) classicalMeasureT ∧
      (∫ x, (T ℝ n).eval x ∂classicalMeasureT) = if n = 0 then π else 0 := by
  refine ⟨integrable_classicalMeasureT (by fun_prop), ?_⟩
  rw [classicalMeasureT_eq]
  split_ifs with h
  · subst n; exact integral_eval_T_real_measureT_zero
  · exact integral_eval_T_real_measureT_of_ne_zero h
source

2.1.3 The second-kind weight

The second-kind family uses \(w_U\) instead. Its squared norms are the same at every nonnegative degree.

Definition 2.1.10 Second-kind weight measure
✓ 🙂 human-reviewed

Let \(\mu _U=\mu _{w_U}\) be the measure of Definition 1.1.2 for the weight \(w_U\) of Definition 2.1.3.

Reference: [DLMF, Table 18.3.1].

Lean Formalisation
def Polynomial.Chebyshev.measureU : MeasureTheory.Measure ℝ
Lean definition
/-- The second-kind measure obtained from the subtype density. -/
def measureU : Measure ℝ := openIntervalWeightMeasure (-1) 1 weightU
source
Lemma 2.1.11 Weighted integral formula
✓ 🤖

For \(f\in \mathcal I(\mu _U)\),

\[ \int f\, d\mu _U=\int _{x\in (-1,1)} f(x)\sqrt{1-x^2}\, dx. \]

The function \(x\mapsto f(x)\sqrt{1-x^2}\) is Lebesgue-integrable on \((-1,1)\). Reference: [DLMF, Table 18.3.1].

Lean Formalisation
theorem Polynomial.Chebyshev.integral_measureU (f : MeasureTheory.IntegrableInput Polynomial.Chebyshev.measureU) :
  ∫ (x : ℝ), ↑f x ∂Polynomial.Chebyshev.measureU = ∫ (x : ↑(Set.Ioo (-1) 1)), ↑f ↑x * ↑(Polynomial.Chebyshev.weightU x)
Lean proof
/-- The classical second-kind integral formula for an integrable input. -/
theorem integral_measureU (f : IntegrableInput measureU) :
    ∫ x, f.val x ∂measureU =
      ∫ x : Ioo (-1 : ℝ) 1, f.val x * (weightU x : ℝ) := by
  exact (integral_openIntervalWeightMeasure _ _ _ f).trans
    (integral_congr_ae (Filter.Eventually.of_forall (fun _ ↦ mul_comm _ _)))
source
Theorem 2.1.12 Second-kind orthogonality
✓ 🤖

For distinct \(n,m\in \mathbb {N}\),

\[ \int U_n(x)U_m(x)\, d\mu _U(x)=0. \]

Reference: [DLMF, Table 18.3.1].

Lean Formalisation
theorem Polynomial.Chebyshev.integral_eval_U_real_mul_eval_U_real_measureU_of_ne {n m : ℕ} (h : n ≠ m) :
  ∫ (x : ℝ),
      Polynomial.eval x (Polynomial.Chebyshev.U ℝ ↑n) *
        Polynomial.eval x (Polynomial.Chebyshev.U ℝ ↑m) ∂Polynomial.Chebyshev.measureU =
    0
Lean proof
/-- Distinct second-kind Chebyshev polynomials are orthogonal (DLMF Table 18.3.1). -/
theorem integral_eval_U_real_mul_eval_U_real_measureU_of_ne {n m : ℕ} (h : n ≠ m) :
    ∫ x, (U ℝ n).eval x * (U ℝ m).eval x ∂measureU = 0 := by
  rw [integral_eval_U_real_mul_eval_U_real_measureU, classicalMeasureT_eq,
    integral_eval_T_real_measureT_of_ne_zero (by omega),
    integral_eval_T_real_measureT_of_ne_zero (by omega)]
  simp
source
Theorem 2.1.13 Second-kind squared norms
✓ 🤖

For every \(n\in \mathbb {N}\),

\[ \int U_n(x)^2\, d\mu _U(x)=\frac\pi 2. \]

Reference: [DLMF, Table 18.3.1].

Lean Formalisation
theorem Polynomial.Chebyshev.integral_eval_U_real_mul_self_measureU (n : ℕ) :
  ∫ (x : ℝ),
      Polynomial.eval x (Polynomial.Chebyshev.U ℝ ↑n) *
        Polynomial.eval x (Polynomial.Chebyshev.U ℝ ↑n) ∂Polynomial.Chebyshev.measureU =
    Real.pi / 2
Lean proof
/-- Squared norms of second-kind Chebyshev polynomials (DLMF Table 18.3.1). -/
theorem integral_eval_U_real_mul_self_measureU (n : ℕ) :
    ∫ x, (U ℝ n).eval x * (U ℝ n).eval x ∂measureU = π / 2 := by
  rw [integral_eval_U_real_mul_eval_U_real_measureU, classicalMeasureT_eq, sub_self,
    integral_eval_T_real_measureT_zero,
    integral_eval_T_real_measureT_of_ne_zero (by omega), sub_zero]
source
Integrability, comparison of weights and product reduction
Theorem 2.1.14 Second-kind integrability characterisation
✓ 🤖

A real function \(f\) is \(\mu _U\)-integrable exactly when \(x\mapsto \sqrt{1-x^2}f(x)\) is Lebesgue-integrable on the open interval \((-1,1)\).

Lean Formalisation
theorem Polynomial.Chebyshev.integrable_measureU_iff (f : ℝ → ℝ) :
  MeasureTheory.Integrable f Polynomial.Chebyshev.measureU ↔
    MeasureTheory.Integrable (fun x => ↑(Polynomial.Chebyshev.weightU x) * f ↑x) MeasureTheory.volume
Lean proof
/-- Integrability against the second-kind density. -/
theorem integrable_measureU_iff (f : ℝ → ℝ) :
    Integrable f measureU ↔
      Integrable (fun x : Ioo (-1 : ℝ) 1 ↦ (weightU x : ℝ) * f x) volume :=
  integrable_openIntervalWeightMeasure_iff _ _ _ _
source
Lemma 2.1.15 Integrability
✓ 🤖

Every real-valued function continuous on \([-1,1]\) is integrable for \(\mu _U\).

Reference: the second-kind weight in [DLMF, Table 18.3.1].

Lean Formalisation
theorem Polynomial.Chebyshev.integrable_measureU {f : ℝ → ℝ} (hf : ContinuousOn f (Set.Icc (-1) 1)) :
  MeasureTheory.Integrable f Polynomial.Chebyshev.measureU
Lean proof
/-- Continuous functions are integrable for the second-kind weight (DLMF Table 18.3.1). -/
theorem integrable_measureU {f : ℝ → ℝ} (hf : ContinuousOn f (Set.Icc (-1) 1)) :
    Integrable f measureU := by
  have hi : IntervalIntegrable (fun x ↦ √(1 - x ^ 2) * f x) volume (-1) 1 :=
    ContinuousOn.intervalIntegrable (by
      rw [Set.uIcc_of_le (by norm_num : (-1 : ℝ) ≤ 1)]
      exact (by fun_prop : ContinuousOn (fun x : ℝ ↦ √(1 - x ^ 2)) _).mul hf)
  rw [intervalIntegrable_iff, Set.uIoc_of_le (by norm_num : (-1 : ℝ) ≤ 1)] at hi
  rw [integrable_measureU_iff]
  rw [IntegrableOn, ← restrict_Ioo_eq_restrict_Ioc] at hi
  exact (integrableOn_iff_comap_subtypeVal measurableSet_Ioo).1 hi
source
Lemma 2.1.16 Comparison of weights
✓ 🤖

For \(f\in \mathcal I(\mu _U)\), the function \(x\mapsto f(x)(1-x^2)\) is \(\mu _T\)-integrable and

\[ \int f\, d\mu _U=\int f(x)(1-x^2)\, d\mu _T(x). \]

Reference: [DLMF, Table 18.3.1].

Lean Formalisation
theorem Polynomial.Chebyshev.integral_measureU_eq_classicalMeasureT
  (f : MeasureTheory.IntegrableInput Polynomial.Chebyshev.measureU) :
  MeasureTheory.Integrable (fun x => ↑f x * (1 - x ^ 2)) Polynomial.Chebyshev.classicalMeasureT ∧
    ∫ (x : ℝ), ↑f x ∂Polynomial.Chebyshev.measureU =
      ∫ (x : ℝ), ↑f x * (1 - x ^ 2) ∂Polynomial.Chebyshev.classicalMeasureT
Lean proof
/-- Comparison of weights preserves integrability as well as the integral value. -/
theorem integral_measureU_eq_classicalMeasureT
    (f : IntegrableInput measureU) :
    Integrable (fun x ↦ f.val x * (1 - x ^ 2)) classicalMeasureT ∧
      (∫ x, f.val x ∂measureU) =
        ∫ x, f.val x * (1 - x ^ 2) ∂classicalMeasureT := by
  have h : Integrable (fun x ↦ f.val x * (1 - x ^ 2)) classicalMeasureT := by
    rw [integrable_classicalMeasureT_iff]
    convert (integrable_measureU_iff _).1 f.property using 1
    ext x
    rw [weightU_eq_weightT_mul]
    ring
  refine ⟨h, ?_⟩
  rw [integral_measureU]
  have he := integral_openIntervalWeightMeasure (-1) 1 weightT
    (⟨_, h⟩ : IntegrableInput classicalMeasureT)
  apply Eq.trans _ he.symm
  apply integral_congr_ae
  filter_upwards [] with x
  rw [weightU_eq_weightT_mul]
  ring
source
Lemma 2.1.17 Product reduction
✓ 🤖

For integers \(n,m\),

\[ \int U_n U_m\, d\mu _U=\frac12\left(\int T_{n-m}\, d\mu _T -\int T_{n+m+2}\, d\mu _T\right). \]

Reference: [DLMF, Table 18.3.1 and equations 18.5.1–18.5.2].

Lean Formalisation
theorem Polynomial.Chebyshev.integral_eval_U_real_mul_eval_U_real_measureU (n m : ℤ) :
  ∫ (x : ℝ),
      Polynomial.eval x (Polynomial.Chebyshev.U ℝ n) *
        Polynomial.eval x (Polynomial.Chebyshev.U ℝ m) ∂Polynomial.Chebyshev.measureU =
    (∫ (x : ℝ), Polynomial.eval x (Polynomial.Chebyshev.T ℝ (n - m)) ∂Polynomial.Chebyshev.classicalMeasureT -
        ∫ (x : ℝ), Polynomial.eval x (Polynomial.Chebyshev.T ℝ (n + m + 2)) ∂Polynomial.Chebyshev.classicalMeasureT) /
      2
Lean proof
/-- Product integral reduction to first-kind Chebyshev moments; DLMF Table 18.3.1
and the trigonometric representations in DLMF 18.5.1--18.5.2. -/
theorem integral_eval_U_real_mul_eval_U_real_measureU (n m : ℤ) :
    ∫ x, (U ℝ n).eval x * (U ℝ m).eval x ∂measureU =
      ((∫ x, (T ℝ (n - m)).eval x ∂classicalMeasureT) -
       (∫ x, (T ℝ (n + m + 2)).eval x ∂classicalMeasureT)) / 2 := by
  rw [classicalMeasureT_eq]
  have h := (integral_measureU_eq_classicalMeasureT
    ⟨fun x ↦ (U ℝ n).eval x * (U ℝ m).eval x, integrable_measureU (by fun_prop)⟩).2
  rw [classicalMeasureT_eq] at h
  rw [h]
  rw [← MeasureTheory.integral_sub (integrable_measureT (by fun_prop))
    (integrable_measureT (by fun_prop)), ← MeasureTheory.integral_div]
  rw [integral_measureT_eq_integral_cos, integral_measureT_eq_integral_cos]
  apply intervalIntegral.integral_congr
  intro θ hθ
  simp only [T_real_cos]
  have hn := U_real_cos (n := n) (θ := θ)
  have hm := U_real_cos (n := m) (θ := θ)
  have hs := Real.sin_sq_add_cos_sq θ
  have hp := Real.two_mul_sin_mul_sin (((n : ℝ) + 1) * θ) (((m : ℝ) + 1) * θ)
  have hsub : ((n : ℝ) + 1) * θ - ((m : ℝ) + 1) * θ = (n - m) * θ := by ring
  have hadd : ((n : ℝ) + 1) * θ + ((m : ℝ) + 1) * θ = (n + m + 2) * θ := by ring
  rw [hsub, hadd] at hp
  push_cast
  calc
    _ = ((U ℝ n).eval (cos θ) * sin θ) * ((U ℝ m).eval (cos θ) * sin θ) := by
      rw [show 1 - cos θ ^ 2 = sin θ ^ 2 by nlinarith [hs]]
      ring
    _ = sin (((n : ℝ) + 1) * θ) * sin (((m : ℝ) + 1) * θ) := by rw [hn, hm]
    _ = _ := by linarith [hp]
source