LeanFun RevOLVER

2.7 Calculus and arithmetic on Chebyshev series

A coefficient representation supports evaluation, differentiation, integration and multiplication. Finite formulas come first; convergence hypotheses justify the operations on infinite series.

2.7.1 Clenshaw evaluation

A backward recurrence evaluates an expansion without forming every basis polynomial separately. The state has two entries because the basis satisfies a three-term recurrence.

Definition 2.7.1 Backward Clenshaw state
✓ 🤖
#

Let \(R\) be a ring, not necessarily commutative, and let \(a,b,c:\mathbb {N}\to R\). For \(n\) coefficients starting at index \(k\), define \(S_{0,k}=(0,0)\). If \(S_{n,k+1}=(u,v)\), set

\[ S_{n+1,k}=(c_k+b_kv,\ u+a_kv). \]

If \(S_{n,0}=(u,v)\), the evaluator returns \(u p_0+v p_1\). Here \(n\) is the number of coefficients, not the largest degree. The initial values \(p_0,p_1\) are supplied separately.

References: [Cle55]; [DLMF, 3.11(ii), 18.40(i)].

Lean Formalisation
def Polynomial.clenshawState.{u_1} {R : Type u_1} [Ring R] (a b c : ℕ → R) : ℕ → ℕ → R × R
Lean definition
/-- Backward Clenshaw state for `n` coefficients, starting at index `k`.
There is one recursive call per coefficient. If the tail state is `(u, v)`,
substituting the three-term recurrence gives the new state `(c k + b k * v, u + a k * v)`.
-/
def clenshawState (a b c : ℕ → R) : ℕ → ℕ → R × R
  | 0, _ => (0, 0)
  | n + 1, k =>
    let s := clenshawState a b c n (k + 1)
    (c k + b k * s.2, s.1 + a k * s.2)
source
Theorem 2.7.2 Clenshaw evaluation
✓ 🤖

Let \(R\) be a commutative ring. Suppose \(p_{k+2}=a_kp_{k+1}+b_kp_k\) for every \(k\in \mathbb {N}\). Then the evaluator returns exactly

\[ \sum _{i=0}^{n-1}c_i p_i. \]

More generally, if \(S_{n,k}=(u,v)\), then \(u p_k+v p_{k+1}=\sum _{i=0}^{n-1}c_{k+i}p_{k+i}\). The empty expansion is zero and a one-coefficient expansion is \(c_0p_0\). No division or orthogonality is assumed.

References: [Cle55]; [DLMF, 18.40(i)].

Lean Formalisation
theorem Polynomial.clenshawState_spec.{u_1} {R : Type u_1} [CommRing R] (a b c p : ℕ → R)
  (hp : ∀ (k : ℕ), p (k + 2) = a k * p (k + 1) + b k * p k) (n k : ℕ) :
  (Polynomial.clenshawState a b c n k).1 * p k + (Polynomial.clenshawState a b c n k).2 * p (k + 1) =
    ∑ i ∈ Finset.range n, c (k + i) * p (k + i)
Lean proof
/-- The backward state reconstructs the corresponding suffix of a finite expansion. -/
theorem clenshawState_spec (a b c p : ℕ → R)
    (hp : ∀ k, p (k + 2) = a k * p (k + 1) + b k * p k) (n k : ℕ) :
    (clenshawState a b c n k).1 * p k +
        (clenshawState a b c n k).2 * p (k + 1) =
      ∑ i ∈ Finset.range n, c (k + i) * p (k + i) := by
  induction n generalizing k with
  | zero => simp [clenshawState]
  | succ n ih =>
    rw [Finset.sum_range_succ']
    simp only [Nat.add_zero]
    have ht := ih (k + 1)
    simp only [Nat.add_assoc, Nat.add_comm 1] at ht
    rw [← ht]
    simp only [clenshawState, hp]
    ring
source

This is an exact-arithmetic theorem; no floating-point error or stability estimate is asserted.

Theorem 2.7.3 Chebyshev Clenshaw evaluation
✓ 🤖

For any commutative ring and any \(x\), use \(a_k=2x\), \(b_k=-1\), \(p_0=1\) and \(p_1=x\). The resulting executable evaluator returns \(\sum _{i=0}^{n-1}c_iT_i(x)\). The coefficient \(c_0\) is the full constant term; unlike [DLMF, 3.11(ii)], it is not halved.

References: [Cle55]; [DLMF, 3.11(ii)].

Lean Formalisation
theorem Polynomial.Chebyshev.clenshawT_eq_sum.{u_1} {R : Type u_1} [CommRing R] (c : ℕ → R) (x : R) (n : ℕ) :
  Polynomial.Chebyshev.clenshawT c x n = ∑ i ∈ Finset.range n, c i * Polynomial.eval x (Polynomial.Chebyshev.T R ↑i)
Lean proof
/-- Exact evaluation, with a full (not halved) constant coefficient. -/
theorem clenshawT_eq_sum (c : ℕ → R) (x : R) (n : ℕ) :
    clenshawT c x n = ∑ i ∈ Finset.range n, c i * (T R (i : ℤ)).eval x := by
  have hp (k : ℕ) : (T R ((k + 2 : ℕ) : ℤ)).eval x =
      (2 * x) * (T R ((k + 1 : ℕ) : ℤ)).eval x +
        (-1) * (T R (k : ℤ)).eval x := by
    simp only [Nat.cast_add, Nat.cast_one, Nat.cast_ofNat, T_add_two,
      eval_sub, eval_mul, eval_ofNat, eval_X]
    ring
  simpa [clenshawT] using
    clenshaw_eq_sum (fun _ ↦ 2 * x) (fun _ ↦ -1) c
      (fun k ↦ (T R (k : ℤ)).eval x) hp n
source

Example (Julia).

The backward state can be compared with direct cosine summation at an interval point. Both evaluations use the full constant coefficient.


function clenshaw(c, a, b, p0, p1)  # backward state of the definition
    u, v = zero(p0), zero(p0)
    for k in length(c)-1:-1:0
        u, v = c[k+1] + b(k)*v, u + a(k)*v
    end
    u*p0 + v*p1
end
c = [1/(1 + k^2) for k in 0:20]
x = 0.3
direct = sum(c[k+1]*cos(k*acos(x)) for k in 0:20)
clenshaw(c, k -> 2x, k -> -1.0, 1.0, x) - direct   # compare the two evaluations
Finite-array and stream formulations
Theorem 2.7.4 Chebyshev recurrence Mathlib
✓

Over a commutative ring, \(T_0=1\), \(T_1=X\) and \(T_{k+2}=2XT_{k+1}-T_k\) for every integer \(k\).

Reference: [DLMF, Table 18.9.1].

Lean Formalisation
theorem Polynomial.Chebyshev.T_zero.{u_1} (R : Type u_1) [CommRing R] : Polynomial.Chebyshev.T R 0 = 1
Mathlib source
Definition 2.7.5 Clenshaw evaluation from finite data
✓ 🤖

Over a ring, take \(n\) coefficients \(c_0,\ldots ,c_{n-1}\) and recurrence coefficients \(a_k,b_k\) only for \(0\le k{\lt}n-2\). Define the states for zero, one and two coefficients by \((0,0)\), \((c_0,0)\) and \((c_0,c_1)\), respectively. For \(n\ge 3\), shift all three finite arrays by one index, compute the suffix state \((u,v)\) recursively, and return \((c_0+b_0v,u+a_0v)\). The evaluator applied to the resulting state \((u,v)\) returns \(up_0+vp_1\). Thus no recurrence coefficient is evaluated for an expansion with at most two coefficients.

References: [Cle55]; [DLMF, 18.40(i)].

Lean Formalisation
def Polynomial.finiteClenshawState.{u_1} {R : Type u_1} [Ring R] (n : ℕ) :
  (Fin (n - 2) → R) → (Fin (n - 2) → R) → (Fin n → R) → R × R
Lean definition
/-- Finite backward state using only the recurrence indices below `n - 2`.
The last two coefficients need no recurrence evaluation (Clenshaw 1955). -/
def finiteClenshawState : (n : ℕ) → (Fin (n - 2) → R) → (Fin (n - 2) → R) →
    (Fin n → R) → R × R
  | 0, _, _, _ => (0, 0)
  | 1, _, _, c => (c 0, 0)
  | 2, _, _, c => (c 0, c 1)
  | n + 3, a, b, c =>
    let s := finiteClenshawState (n + 2)
      (fun i ↦ a ⟨i.val + 1, by omega⟩)
      (fun i ↦ b ⟨i.val + 1, by omega⟩)
      (fun i ↦ c ⟨i.val + 1, by omega⟩)
    (c 0 + b ⟨0, by omega⟩ * s.2, s.1 + a ⟨0, by omega⟩ * s.2)
source
Theorem 2.7.6 Finite and stream Clenshaw states agree
✓ 🤖

For any ring and streams \(a,b,c:\mathbb {N}\to R\), restricting them to the finite indices used by an \(n\)-coefficient expansion gives the same state and evaluation as the backward Clenshaw recurrence. The state identity also holds for every suffix starting at an arbitrary index \(k\).

Lean Formalisation
theorem Polynomial.finiteClenshawState_eq.{u_1} {R : Type u_1} [Ring R] (a b c : ℕ → R) (n k : ℕ) :
  (Polynomial.finiteClenshawState n (fun i => a (k + ↑i)) (fun i => b (k + ↑i)) fun i => c (k + ↑i)) =
    Polynomial.clenshawState a b c n k
Lean proof
/-- Finite data give the same suffix state as the stream-based recurrence. -/
theorem finiteClenshawState_eq (a b c : ℕ → R) (n k : ℕ) :
    finiteClenshawState n (fun i ↦ a (k + i.val)) (fun i ↦ b (k + i.val))
      (fun i ↦ c (k + i.val)) = clenshawState a b c n k := by
  induction n using Nat.strong_induction_on generalizing k with
  | h n ih =>
    match n with
    | 0 => rfl
    | 1 => simp [finiteClenshawState, clenshawState]
    | 2 => simp [finiteClenshawState, clenshawState]
    | n + 3 =>
      have ht := ih (n + 2) (by omega) (k + 1)
      simp only [finiteClenshawState]
      simp only [Nat.add_assoc, Nat.add_comm 1] at ht
      rw [ht]
      simp [clenshawState]
source

2.7.2 Integration of coefficients

Primitives of individual modes give primitives of finite expansions. Their endpoint differences give the moments used in Clenshaw–Curtis quadrature.

Definition 2.7.7 Admissible degrees for Chebyshev primitives
✓ 🤖
#

For a field \(K\) and degree \(n\), call \(n\) an admissible primitive degree when the denominators in the adjacent-degree formula are nonzero: there is no condition at \(n=0\), one requires \(4\ne 0\) at \(n=1\), and for \(n=m+2\) one requires \(2(m+3)\ne 0\) and \(2(m+1)\ne 0\) in \(K\).

Lean Formalisation
def Polynomial.Chebyshev.PrimitiveInput.{u_2} (K : Type u_2) [Field K] : ℕ → Prop
Lean definition
/-- The precise nonzero denominators needed by the adjacent-degree primitive. -/
def PrimitiveInput (K : Type*) [Field K] : ℕ → Prop
  | 0 => True
  | 1 => (4 : K) ≠ 0
  | n + 2 => (2 * (n + 3 : K)) ≠ 0 ∧ (2 * (n + 1 : K)) ≠ 0
source
Definition 2.7.8 Chebyshev primitives
✓ 🤖

Over a field \(K\), for an admissible primitive degree \(n\) as in Definition 2.7.7, define \(Q_0=T_1\), \(Q_1=T_2/4\), and

\[ Q_n=\frac{T_{n+1}}{2(n+1)}-\frac{T_{n-1}}{2(n-1)}\quad (n\ge 2). \]

The anchored polynomial is \(Q_n-Q_n(a)\).

Reference: [ATAP, Chapter 19].

Lean Formalisation
def Polynomial.Chebyshev.primitiveT.{u_2} (K : Type u_2) [Field K] (n : ℕ)
  (_d : Polynomial.Chebyshev.PrimitiveInput K n := by exact Polynomial.Chebyshev.PrimitiveInput.ofCharZero _ _) :
  Polynomial K
Lean definition
/-- An antiderivative with only adjacent Chebyshev degrees; the constant of
integration is free (ATAP, Chapter 19). -/
noncomputable def primitiveT (K : Type*) [Field K] (n : ℕ)
    (_d : PrimitiveInput K n := by exact Polynomial.Chebyshev.PrimitiveInput.ofCharZero _ _) : K[X] :=
  match n with
  | 0 => T K 1
  | 1 => Polynomial.C (1 / 4) * T K 2
  | n + 2 => Polynomial.C (1 / (2 * (n + 3 : K))) * T K (n + 3 : ℕ) -
      Polynomial.C (1 / (2 * (n + 1 : K))) * T K (n + 1 : ℕ)
source

Over a characteristic-zero field, \(Q_n'=T_n\), so differentiating \(\sum _{n\in s}a_nQ_n\) recovers \(\sum _{n\in s}a_nT_n\). Anchored primitives have the same derivative and vanish at their anchor. The negative endpoint derivative is \(T_{n+1}'(-1)=(-1)^n(n+1)^2\).

Reference: [ATAP, Chapters 19 and 21].

Lean Formalisation
theorem Polynomial.Chebyshev.derivative_primitiveT.{u_1} {K : Type u_1} [Field K] [CharZero K] (n : ℕ) :
  Polynomial.derivative (Polynomial.Chebyshev.primitiveT K n ⋯) = Polynomial.Chebyshev.T K ↑n
Lean proof
/-- The two adjacent terms differentiate exactly to the original Chebyshev
polynomial, including degrees zero and one. -/
theorem derivative_primitiveT (n : ℕ) : derivative (primitiveT K n) = T K n := by
  rcases n with _ | _ | n
  · simp [primitiveT, T_one]
  · simp only [primitiveT, derivative_C_mul, T_derivative_eq_U,
      Int.reduceSub, U_one, Int.cast_ofNat]
    norm_num [← mul_assoc, ← C_ofNat, ← map_mul]
    rw [← C_ofNat 4, ← map_mul]
    norm_num
  · simp only [primitiveT, derivative_sub, derivative_C_mul, T_derivative_eq_U]
    have h₁ : (1 / (2 * (n + 3 : K))) * (n + 3 : K) = 1 / 2 := by
      have hn : (n + 3 : K) ≠ 0 := by exact_mod_cast (show n + 3 ≠ 0 by omega)
      field_simp
    have h₂ : (1 / (2 * (n + 1 : K))) * (n + 1 : K) = 1 / 2 := by
      have hn : (n + 1 : K) ≠ 0 := by exact_mod_cast (show n + 1 ≠ 0 by omega)
      field_simp
    simp only [Nat.cast_add, Nat.cast_one, Nat.cast_ofNat, Int.cast_add,
      Int.cast_natCast, Int.cast_ofNat, Int.cast_one, ← C_eq_natCast, ← C_ofNat, ← C_1,
      ← map_add, ← mul_assoc, ← map_mul]
    rw [h₁, h₂]
    have hu := two_mul_T_eq_U_sub_U K (n : ℤ)
    have hi₁ : (n : ℤ) + 3 - 1 = n + 2 := by omega
    have hi₂ : (n : ℤ) + 1 - 1 = n := by omega
    rw [hi₁, hi₂, ← mul_sub, ← hu]
    rw [show (n : ℤ) + 1 + 1 = n + 2 by omega, ← mul_assoc, ← C_ofNat 2, ← map_mul]
    norm_num
source
Definition 2.7.10 Unweighted Chebyshev moments
✓ 🤖
#

For a natural index \(n\), define \(m_1=0\) and, for \(n\ne 1\),

\[ m_n=\frac{1+(-1)^n}{1-n^2}. \]

The exceptional odd mode is defined separately, without division by zero.

Lean Formalisation
def Polynomial.Chebyshev.integralMoment (n : ℕ) : ℝ
Lean definition
/-- The exact unweighted Chebyshev moment; the odd mode of index one is explicit.
Reference: ATAP, Chapter 19. -/
noncomputable def integralMoment (n : ℕ) : ℝ :=
  if n = 1 then 0 else (1 + (-1 : ℝ) ^ n) / (1 - (n : ℝ) ^ 2)
source
Theorem 2.7.11 Unweighted integration of Chebyshev coefficients
✓ 🤖

With respect to Lebesgue measure,

\[ \int _{-1}^1T_n(x)\, dx=\begin{cases} 2/(1-n^2),& n\text{ even},\\ 0,& n\text{ odd}.\end{cases} \]

Integration of a finite Chebyshev expansion is the corresponding weighted sum of its coefficients.

Reference: [ATAP, equation (19.6) and Theorem 19.2].

Lean Formalisation
theorem Polynomial.Chebyshev.integral_sum_eval_T (s : Finset ℕ) (a : ℕ → ℝ) :
  ∫ (x : ℝ) in -1..1, ∑ n ∈ s, a n * Polynomial.eval x (Polynomial.Chebyshev.T ℝ ↑n) =
    ∑ n ∈ s, a n * Polynomial.Chebyshev.integralMoment n
Lean proof
/-- Integration of a finite Chebyshev expansion is a weighted coefficient sum. -/
theorem integral_sum_eval_T (s : Finset ℕ) (a : ℕ → ℝ) :
    (∫ x in (-1 : ℝ)..1, ∑ n ∈ s, a n * (T ℝ n).eval x) =
      ∑ n ∈ s, a n * integralMoment n := by
  rw [intervalIntegral.integral_finsetSum]
  · simp only [intervalIntegral.integral_const_mul, integral_eval_T]
  · intro n _
    exact (continuous_const.mul (T ℝ n).continuous).intervalIntegrable _ _
source
Primitive domains and moment identities
Theorem 2.7.12 Admissible primitive degrees in characteristic zero
✓ 🤖

Over a field of characteristic zero, every \(n\in \mathbb {N}\) is an admissible primitive degree: \(4\ne 0\), and \(2(m+3)\ne 0\), \(2(m+1)\ne 0\) for every \(m\in \mathbb {N}\).

Lean Formalisation
theorem Polynomial.Chebyshev.PrimitiveInput.ofCharZero.{u_2} (K : Type u_2) [Field K] [CharZero K] (n : ℕ) :
  Polynomial.Chebyshev.PrimitiveInput K n
Lean proof
/-- Characteristic zero supplies every primitive denominator. -/
theorem PrimitiveInput.ofCharZero (K : Type*) [Field K] [CharZero K] (n : ℕ) :
    PrimitiveInput K n := by
  rcases n with _ | _ | n
  · trivial
  · norm_num [PrimitiveInput]
  · constructor <;> apply mul_ne_zero (by norm_num)
    · exact_mod_cast (show n + 3 ≠ 0 by omega)
    · exact_mod_cast (show n + 1 ≠ 0 by omega)
source

For \(n\ne 1\), the denominator \(1-n^2\) is nonzero. For every \(n\ge 0\),

\[ m_n=\int _{-1}^1T_n(x)\, dx =Q_n(1)-Q_n(-1) =\begin{cases} 2/(1-n^2),& n\text{ even},\\ 0,& n\text{ odd}.\end{cases} \]

Reference: [ATAP, equation (19.6)].

Lean Formalisation
theorem Polynomial.Chebyshev.integralMoment_denominator_ne_zero (n : { n // n ≠ 1 }) : 1 - ↑↑n ^ 2 ≠ 0
Lean proof
/-- The nonexceptional moment formula has a nonzero denominator. -/
theorem integralMoment_denominator_ne_zero (n : {n : ℕ // n ≠ 1}) :
    1 - (n.val : ℝ) ^ 2 ≠ 0 := by
  have h := Nat.cast_nonneg (α := ℝ) n.val
  have hn : (n.val : ℝ) ≠ 1 := by exact_mod_cast n.property
  intro he
  have : (n.val : ℝ) = 1 := by nlinarith
  exact hn this
source

2.7.3 Differentiating and integrating infinite series

Write \(S_a\) for the convergent Chebyshev series of Definition 2.5.26. Differentiation uses the second-kind basis, also denoted \(C_n^{(1)}=U_n\); the precise bridge is Theorem 4.2.16. Geometric coefficient decay justifies differentiation on smaller ellipses.

The derivative is defined on the domain where it exists, as in Definition 1.1.10; geometric decay supplies that existence (Theorem 2.7.19).

If \(|a_n|\le C\rho ^{-n}\), \(\rho {\gt}1\), then on \(E_\rho \),

\[ S_a'(z)=\sum _{n\ge 0}a_nT_n'(z) =\sum _{n\ge 0}(n+1)a_{n+1}C_n^{(1)}(z). \]

For \(1{\lt}r{\lt}\rho \), derivatives of partial sums converge uniformly on every compact subset of \(E_r\).

References: [ATAP, Chapter 21]; [DLMF, 18.9.21].

Lean Formalisation
theorem Polynomial.Chebyshev.hasSum_derivative_complexChebyshevSeries {a : ℕ → ℂ} {C ρ : ℝ} (hρ : 1 < ρ)
  (ha : ∀ (n : ℕ), ‖a n‖ ≤ C / ρ ^ n) (z : ↑(Complex.bernsteinEllipse ⟨ρ, hρ⟩)) :
  HasSum (fun n => a n * Polynomial.eval (↑z) (Polynomial.derivative (Polynomial.Chebyshev.T ℂ ↑n)))
    (iteratedDerivOnOpen (Polynomial.Chebyshev.complexChebyshevSeriesDerivInput hρ ha 1) z)
Lean proof
/-- The differentiated terms sum to the actual classical derivative. -/
theorem hasSum_derivative_complexChebyshevSeries {a : ℕ → ℂ} {C ρ : ℝ}
    (hρ : 1 < ρ) (ha : ∀ n, ‖a n‖ ≤ C / ρ ^ n)
    (z : bernsteinEllipse ⟨ρ, hρ⟩) :
    HasSum (fun n ↦ a n * (T ℂ n).derivative.eval z.val)
      (iteratedDerivOnOpen (complexChebyshevSeriesDerivInput hρ ha 1) z) := by
  rw [iteratedDeriv_complexChebyshevSeries_eq, iteratedDeriv_one]
  obtain ⟨r, hr, hrρ, hzr⟩ := exists_smaller_bernsteinEllipse hρ z.property
  exact hasSum_derivative_series (isOpen_bernsteinEllipse ⟨r, hr⟩)
    ((summable_geometric_of_lt_one (by positivity : 0 ≤ r / ρ)
      ((div_lt_one (by linarith : 0 < ρ)).2 hrρ)).mul_left C)
    (norm_chebyshev_term_le_geometric hρ hr ha) hzr
source

Assume \(\rho {\gt}1\) and \(|a_n|\le C\rho ^{-n}\) for every \(n\). Let \(1{\lt}r{\lt}\rho \) and \(\delta {\gt}0\). If \(z\in E_r\) and the radius-\(\delta \) circle about \(z\) lies in \(E_r\), then

\[ \left|S_a'(z)-\sum _{n{\lt}N}a_nT_n'(z)\right| \le \frac{C(r/\rho )^N}{\delta (1-r/\rho )}. \]

Every compact \(K\subset E_r\) admits one \(\delta {\gt}0\) for which this bound holds for all \(z\in K\) and all \(N\ge 0\), in particular for the real interval.

Reference: [ATAP, Theorem 21.1].

Lean Formalisation
theorem Polynomial.Chebyshev.norm_derivative_complexChebyshevSeries_sub_sum_le {a : ℕ → ℂ} {C ρ r δ : ℝ} (hρ : 1 < ρ)
  (hr : 1 < r) (hrρ : r < ρ) (ha : ∀ (n : ℕ), ‖a n‖ ≤ C / ρ ^ n) (z : ↑(Complex.bernsteinEllipse ⟨ρ, hρ⟩))
  (hz : ↑z ∈ Complex.bernsteinEllipse ⟨r, hr⟩) (hδ : 0 < δ)
  (hball : Metric.sphere (↑z) δ ⊆ Complex.bernsteinEllipse ⟨r, hr⟩) (N : ℕ) :
  ‖iteratedDerivOnOpen (Polynomial.Chebyshev.complexChebyshevSeriesDerivInput hρ ha 1) z -
        ∑ n ∈ Finset.range N, a n * Polynomial.eval (↑z) (Polynomial.derivative (Polynomial.Chebyshev.T ℂ ↑n))‖ ≤
    C * (r / ρ) ^ N / (1 - r / ρ) / δ
Lean proof
/-- First-order Cauchy truncation bound for the actual derivative value. -/
theorem norm_derivative_complexChebyshevSeries_sub_sum_le {a : ℕ → ℂ} {C ρ r δ : ℝ}
    (hρ : 1 < ρ) (hr : 1 < r) (hrρ : r < ρ) (ha : ∀ n, ‖a n‖ ≤ C / ρ ^ n)
    (z : bernsteinEllipse ⟨ρ, hρ⟩) (hz : z.val ∈ bernsteinEllipse ⟨r, hr⟩) (hδ : 0 < δ)
    (hball : Metric.sphere z.val δ ⊆ bernsteinEllipse ⟨r, hr⟩) (N : ℕ) :
    ‖iteratedDerivOnOpen (complexChebyshevSeriesDerivInput hρ ha 1) z -
      ∑ n ∈ Finset.range N, a n * (T ℂ n).derivative.eval z.val‖ ≤
      C * (r / ρ) ^ N / (1 - r / ρ) / δ := by
  rw [iteratedDeriv_complexChebyshevSeries_eq, iteratedDeriv_one]
  have hq0 : 0 ≤ r / ρ := by positivity
  have hq1 : r / ρ < 1 := (div_lt_one (by linarith : 0 < ρ)).2 hrρ
  have h := norm_derivative_series_sub_sum_le (P := fun n ↦ T ℂ n) (a := a)
    (isOpen_bernsteinEllipse ⟨r, hr⟩) ((summable_geometric_of_lt_one hq0 hq1).mul_left C)
    (norm_chebyshev_term_le_geometric hρ hr ha) hz hδ hball N
  simpa only [tsum_geometric_majorant_tail hq0 hq1 N] using h
source
Theorem 2.7.16 Anchored integration of absolute Chebyshev expansions
✓ 🤖

Write \(A_n\) for the existing primitive of \(T_n\) anchored by \(A_n(-1)=0\). For \(x\in [-1,1]\), \(A_n(x)=\int _{-1}^xT_n(t)\, dt\) and \(|A_n(x)|\le 2\). If \(\sum _n|a_n|{\lt}\infty \) and \(f\) agrees with \(S_a\) on \([-1,1]\), then \(f\) is integrable on every \([-1,x]\), \(x\in [-1,1]\), and

\[ \int _{-1}^x f(t)\, dt=\sum _{n\ge 0}a_n A_n(x). \]

Reference: [ATAP, Chapters 19 and 21].

Lean Formalisation
theorem Polynomial.Chebyshev.eval_primitiveTAt_eq_integral (n : ℕ) (x : ℝ) :
  Polynomial.eval (↑x) (Polynomial.Chebyshev.primitiveTAt (-1) n ⋯) =
    ∫ (t : ℝ) in -1..x, Polynomial.eval (↑t) (Polynomial.Chebyshev.T ℂ ↑n)
Lean proof
/-- The existing complex anchored primitive evaluates to the real-path integral. -/
theorem eval_primitiveTAt_eq_integral (n : ℕ) (x : ℝ) :
    (primitiveTAt (-1 : ℂ) n).eval (x : ℂ) = ∫ t in (-1 : ℝ)..x, (T ℂ n).eval (t : ℂ) := by
  have h := intervalIntegral.integral_eq_sub_of_hasDerivAt (a := (-1 : ℝ)) (b := x)
    (fun t _ ↦ ((primitiveT ℂ n).hasDerivAt (t : ℂ)).comp_ofReal)
    (f' := fun t : ℝ ↦ (primitiveT ℂ n).derivative.eval (t : ℂ))
    (by apply Continuous.intervalIntegrable; fun_prop)
  simpa only [derivative_primitiveT, primitiveTAt, eval_sub, eval_C, ofReal_neg, ofReal_one] using h.symm
source

Let \(f\) agree with \(S_a\) on \([-1,1]\), and let \(A_n\) be the primitive of \(T_n\) anchored at \(-1\). If \(\sum _n|a_n|{\lt}\infty \), \(\sum _{n{\lt}N}a_n A_n(x)\) converges to \(\int _{-1}^x f(t)\, dt\) uniformly on \([-1,1]\), with error at most \(2\sum _{n\ge N}|a_n|\) after the first \(N\) modes. If \(|a_n|\le C\rho ^{-n}\), \(\rho {\gt}1\), this is at most \(2C\rho ^{-N}/(1-\rho ^{-1})\).

Reference: [ATAP, Chapter 21].

Lean Formalisation
theorem Polynomial.Chebyshev.norm_integral_sub_sum_primitiveTAt_le {a : ℕ → ℂ} (ha : Summable fun n => ‖a n‖) {f : ℝ → ℂ}
  (hf : ∀ (x : ↑(Set.Icc (-1) 1)), HasSum (fun n => a n * Polynomial.eval (↑↑x) (Polynomial.Chebyshev.T ℂ ↑n)) (f ↑x))
  (x : ↑(Set.Icc (-1) 1)) (N : ℕ) :
  ‖(∫ (t : ℝ) in -1..↑x, f t) -
        ∑ n ∈ Finset.range N, a n * Polynomial.eval (↑↑x) (Polynomial.Chebyshev.primitiveTAt (-1) n ⋯)‖ ≤
    2 * ∑' (n : ℕ), ‖a (n + N)‖
Lean proof
/-- The same absolute-tail bound for the actual anchored integral. -/
theorem norm_integral_sub_sum_primitiveTAt_le {a : ℕ → ℂ}
    (ha : Summable (fun n ↦ ‖a n‖)) {f : ℝ → ℂ}
    (hf : ∀ x : Icc (-1 : ℝ) 1, HasSum (fun n ↦ a n * (T ℂ n).eval (x.val : ℂ)) (f x.val))
    (x : Icc (-1 : ℝ) 1) (N : ℕ) :
    ‖(∫ t in (-1 : ℝ)..x.val, f t) -
      ∑ n ∈ Finset.range N, a n * (primitiveTAt (-1 : ℂ) n).eval (x.val : ℂ)‖ ≤
      2 * ∑' n, ‖a (n + N)‖ := by
  have h := norm_series_sub_sum_le_tail (hasSum_primitiveTAt ha hf x).2 (ha.mul_left 2)
    (fun n ↦ by rw [norm_mul]; simpa only [mul_comm] using
      mul_le_mul_of_nonneg_left (norm_eval_primitiveTAt_le_two n x.property) (norm_nonneg (a n))) N
  simpa only [tsum_mul_left] using h
source
Derivative domains and normal convergence
Definition 2.7.18 Derivative inputs of geometric Chebyshev expansions
✓ 🤖

For \(\rho {\gt}1\), \(|a_n|\le C\rho ^{-n}\) and \(k\ge 0\), regard \(S_a|_{E_\rho }\) as an element of \(\mathcal D^k(E_\rho )\). Its order-\(k\) derivative value is \(D_{E_\rho }^kS_a\).

Lean Formalisation
def Polynomial.Chebyshev.complexChebyshevSeriesDerivInput {a : ℕ → ℂ} {C ρ : ℝ} (hρ : 1 < ρ)
  (ha : ∀ (n : ℕ), ‖a n‖ ≤ C / ρ ^ n) (k : ℕ) :
  IteratedDerivInput { carrier := Complex.bernsteinEllipse ⟨ρ, hρ⟩, is_open' := ⋯ } k
Lean definition
/-- Geometric data supply an actual derivative input, at every finite order. -/
def complexChebyshevSeriesDerivInput {a : ℕ → ℂ} {C ρ : ℝ}
    (hρ : 1 < ρ) (ha : ∀ n, ‖a n‖ ≤ C / ρ ^ n) (k : ℕ) :
    IteratedDerivInput ⟨bernsteinEllipse ⟨ρ, hρ⟩, isOpen_bernsteinEllipse ⟨ρ, hρ⟩⟩ k :=
  .ofAnalytic _ (analyticOnOpen_complexChebyshevSeries hρ ha) k
source
Theorem 2.7.19 Geometric-series derivative input characterisation
✓ 🤖

For \(\rho {\gt}1\), \(|a_n|\le C\rho ^{-n}\) and \(k\ge 0\), the function \(S_a|_{E_\rho }\) admits an order-\(k\) derivative chain on \(E_\rho \). The chain starts at \(S_a|_{E_\rho }\) and ends at \(D_{E_\rho }^kS_a\).

Lean Formalisation
theorem Polynomial.Chebyshev.complexChebyshevSeriesDerivInput_spec {a : ℕ → ℂ} {C ρ : ℝ} (hρ : 1 < ρ)
  (ha : ∀ (n : ℕ), ‖a n‖ ≤ C / ρ ^ n) (k : ℕ) :
  HasIteratedDerivOnOpen { carrier := Complex.bernsteinEllipse ⟨ρ, hρ⟩, is_open' := ⋯ } k
    (fun z =>
      Polynomial.Chebyshev.complexChebyshevSeries a
        (Polynomial.Chebyshev.ComplexChebyshevSeriesPoint.ofGeometric hρ ha z))
    (iteratedDerivOnOpen (Polynomial.Chebyshev.complexChebyshevSeriesDerivInput hρ ha k))
Lean proof
/-- The geometric derivative input carries the actual chain of the series. -/
theorem complexChebyshevSeriesDerivInput_spec {a : ℕ → ℂ} {C ρ : ℝ}
    (hρ : 1 < ρ) (ha : ∀ n, ‖a n‖ ≤ C / ρ ^ n) (k : ℕ) :
    HasIteratedDerivOnOpen ⟨bernsteinEllipse ⟨ρ, hρ⟩, isOpen_bernsteinEllipse ⟨ρ, hρ⟩⟩ k
      (fun z ↦ complexChebyshevSeries a (.ofGeometric hρ ha z))
      (iteratedDerivOnOpen (complexChebyshevSeriesDerivInput hρ ha k)) :=
  iteratedDerivOnOpen_spec (complexChebyshevSeriesDerivInput hρ ha k)
source

Let \(U\subseteq \mathbb C\) be open. If \(\sum _n u_n{\lt}\infty \) and \(|a_nT_n(z)|\le u_n\) for every \(n\) and \(z\in U\), then \(U\subseteq D_a\) and \(S_a|_U\) is analytic.

Lean Formalisation
theorem Polynomial.Chebyshev.ComplexChebyshevSeriesPoint.ofNormal_val {a : ℕ → ℂ} {u : ℕ → ℝ} {U : TopologicalSpace.Opens ℂ}
  (hu : Summable u) (hb : ∀ (n : ℕ), ∀ z ∈ U, ‖a n * Polynomial.eval z (Polynomial.Chebyshev.T ℂ ↑n)‖ ≤ u n) (z : ↥U) :
  ↑(Polynomial.Chebyshev.ComplexChebyshevSeriesPoint.ofNormal hu hb z) = ↑z
Lean proof
@[simp] theorem ComplexChebyshevSeriesPoint.ofNormal_val {a : ℕ → ℂ} {u : ℕ → ℝ}
    {U : TopologicalSpace.Opens ℂ} (hu : Summable u)
    (hb : ∀ n z, z ∈ U → ‖a n * (T ℂ n).eval z‖ ≤ u n) (z : U) :
    (ComplexChebyshevSeriesPoint.ofNormal hu hb z).val = z.val := rfl
source

2.7.4 Multiplication of series

The product formula \(T_mT_n=\tfrac 12(T_{m+n}+T_{|m-n|})\) groups pairs of modes by their output degree. Both terms contribute when those degrees coincide.

Definition 2.7.21 Infinite Chebyshev product coefficients
✓ 🤖

For coefficient sequences \(a,b\) such that \((a_mb_n)_{|m-n|=k}\) is summable, define

\[ c_k=\frac12\left(\sum _{m+n=k}a_mb_n+ \sum _{|m-n|=k}a_mb_n\right),\qquad m,n\ge 0. \]

Both sums contribute when their output degrees coincide. This retains the full-constant convention, including multiplication by \(T_0\).

References: [DLMF, 18.18.21]; [OT13, Section 2.2, equation (2.7)].

Lean Formalisation
def Polynomial.Chebyshev.chebyshevProductCoefficients {k : ℕ} (d : Polynomial.Chebyshev.ChebyshevProductInput k) : ℂ
Lean definition
/-- The product coefficient in the full-constant convention, on its classical domain
(DLMF 18.18.21; Olver--Townsend, Section 2.2). -/
noncomputable def chebyshevProductCoefficients {k : ℕ} (d : ChebyshevProductInput k) : ℂ :=
  (Polynomial.regroupCoefficients d.addInput +
    Polynomial.regroupCoefficients
      (e := fun p : ℕ × ℕ ↦ ((p.1 : ℤ) - p.2).natAbs)
      ⟨fun p ↦ d.left p.1 * d.right p.2, d.difference_summable⟩) / 2
source

If \(\sum |a_n|\) and \(\sum |b_n|\) are finite, then \(c\) is absolutely summable,

\[ \sum _k|c_k|\le \left(\sum _m|a_m|\right)\left(\sum _n|b_n|\right), \qquad S_a(x)S_b(x)=\sum _{k\ge 0}c_kT_k(x)\quad (x\in [-1,1]). \]

Moreover any \(f\in \mathcal I_k^{\mathbb {C}}\) agreeing with \(S_aS_b\) on \([-1,1]\) has coefficient \(c_k\).

References: [DLMF, 18.18.21]; [OT13, Section 2.2].

Lean Formalisation
theorem Polynomial.Chebyshev.summable_norm_chebyshevProductCoefficients {a b : ℕ → ℂ} (ha : Summable fun n => ‖a n‖)
  (hb : Summable fun n => ‖b n‖) :
  Summable fun k =>
    ‖Polynomial.Chebyshev.chebyshevProductCoefficients
        (Polynomial.Chebyshev.ChebyshevProductInput.ofSummableNorm ha hb k)‖
Lean proof
/-- Products preserve absolute coefficient summability. -/
theorem summable_norm_chebyshevProductCoefficients {a b : ℕ → ℂ}
    (ha : Summable (fun n ↦ ‖a n‖)) (hb : Summable (fun n ↦ ‖b n‖)) :
    Summable (fun k ↦ ‖chebyshevProductCoefficients (ChebyshevProductInput.ofSummableNorm ha hb k)‖) := by
  exact (((Polynomial.summable_norm_regroupCoefficients (ha.mul_norm hb) _).of_norm.add
    (Polynomial.summable_norm_regroupCoefficients (ha.mul_norm hb) _).of_norm).div_const 2).norm
source

If \(\sum _n|a_n|{\lt}\infty \) and \(\sum _n|b_n|{\lt}\infty \), with \(c\) defined by the product-coefficient formula of Definition 2.7.21, uniformly for \(x\in [-1,1]\),

\[ \left|S_a(x)S_b(x)-\sum _{k{\lt}N}c_kT_k(x)\right|\le \sum _{k\ge N}|c_k|. \]

The right side tends to zero.

Reference: [ATAP, Chapter 3].

Lean Formalisation
theorem Polynomial.Chebyshev.norm_product_series_sub_sum_le {a b : ℕ → ℂ} (ha : Summable fun n => ‖a n‖)
  (hb : Summable fun n => ‖b n‖) (x : ↑(Set.Icc (-1) 1)) (N : ℕ) :
  ‖Polynomial.Chebyshev.complexChebyshevSeries a (Polynomial.Chebyshev.ComplexChebyshevSeriesPoint.ofAbsolute ha x) *
          Polynomial.Chebyshev.complexChebyshevSeries b
            (Polynomial.Chebyshev.ComplexChebyshevSeriesPoint.ofAbsolute hb x) -
        ∑ k ∈ Finset.range N,
          Polynomial.Chebyshev.chebyshevProductCoefficients
              (Polynomial.Chebyshev.ChebyshevProductInput.ofSummableNorm ha hb k) *
            Polynomial.eval (↑↑x) (Polynomial.Chebyshev.T ℂ ↑k)‖ ≤
    ∑' (k : ℕ),
      ‖Polynomial.Chebyshev.chebyshevProductCoefficients
          (Polynomial.Chebyshev.ChebyshevProductInput.ofSummableNorm ha hb (k + N))‖
Lean proof
/-- Truncating the product coefficients has error at most their absolute tail. -/
theorem norm_product_series_sub_sum_le {a b : ℕ → ℂ}
    (ha : Summable (fun n ↦ ‖a n‖)) (hb : Summable (fun n ↦ ‖b n‖))
    (x : Icc (-1 : ℝ) 1) (N : ℕ) :
    ‖complexChebyshevSeries a (.ofAbsolute ha x) * complexChebyshevSeries b (.ofAbsolute hb x) -
      ∑ k ∈ Finset.range N, chebyshevProductCoefficients (ChebyshevProductInput.ofSummableNorm ha hb k) * (T ℂ k).eval (x : ℂ)‖ ≤
      ∑' k, ‖chebyshevProductCoefficients (ChebyshevProductInput.ofSummableNorm ha hb (k + N))‖ := by
  apply norm_series_sub_sum_le_tail (hasSum_chebyshevProductCoefficients ha hb x)
    (summable_norm_chebyshevProductCoefficients ha hb)
  intro k
  rw [norm_mul]
  exact mul_le_of_le_one_right (norm_nonneg _) (norm_eval_T_complex_le_one k x.property)
source
Regrouping and product-coefficient domains
Definition 2.7.24 Domain of a collected coefficient
✓ 🤖
#

For an index map \(e:I\to \mathbb {N}\) and output index \(k\), consider coefficient families \(c:I\to \mathbb {C}\) whose restriction to \(\{ i:e(i)=k\} \) is summable. Convergence is required only in this fibre.

Lean Formalisation
def Polynomial.RegroupCoefficientInput.{u_1} {ι : Type u_1} (e : ι → ℕ) (k : ℕ) : Type u_1
Lean definition
/-- Coefficient data with a convergent sum in the specified output fibre. -/
def RegroupCoefficientInput {ι : Type*} (e : ι → ℕ) (k : ℕ) :=
  {c : ι → ℂ // Summable (fun i : {i // e i = k} ↦ c i)}
source

For an index map \(e:I\to \mathbb {N}\), a summable family \((c_i)_{i\in I}\) restricts to a summable family on every fibre \(\{ i:e(i)=k\} \). In particular, absolute summability of \((c_i)\) suffices. More generally, if \(|P_k|\le w_k\) and \(\sum _i|c_i|w_{e(i)}{\lt}\infty \), then \((c_iP_{e(i)})_{i\in I}\) and each of its fibre restrictions are summable. This includes fibres with \(P_k=w_k=0\).

Lean Formalisation
theorem Polynomial.summable_mul_mode.{u_1} {ι : Type u_1} {c : ι → ℂ} (e : ι → ℕ) {P : ℕ → ℂ} {w : ℕ → ℝ}
  (hu : Summable fun i => ‖c i‖ * w (e i)) (hP : ∀ (k : ℕ), ‖P k‖ ≤ w k) : Summable fun i => c i * P (e i)
Lean proof
/-- A weighted norm majorant makes the contribution family summable. -/
theorem summable_mul_mode {ι : Type*} {c : ι → ℂ}
    (e : ι → ℕ) {P : ℕ → ℂ} {w : ℕ → ℝ}
    (hu : Summable (fun i ↦ ‖c i‖ * w (e i))) (hP : ∀ k, ‖P k‖ ≤ w k) :
    Summable (fun i ↦ c i * P (e i)) := by
  apply Summable.of_norm
  apply Summable.of_nonneg_of_le (fun _ ↦ norm_nonneg _) _ hu
  intro i
  rw [norm_mul]
  exact mul_le_mul_of_nonneg_left (hP (e i)) (norm_nonneg _)
source

This includes fibres with \(P_k=w_k=0\); no convergence of the unweighted coefficient fibre is asserted in this more general case.

Definition 2.7.26 Collecting coefficients by output mode
✓ 🤖
#

For a coefficient family \(c:I\to \mathbb C\) summable on \(\{ i:e(i)=k\} \), define \(c^{[e]}_k=\sum _{i:e(i)=k}c_i\).

Reference: elementary regrouping, used for the aliasing formula [ATAP, Theorem 4.2].

Lean Formalisation
def Polynomial.regroupCoefficients.{u_1} {ι : Type u_1} {e : ι → ℕ} {k : ℕ} (c : Polynomial.RegroupCoefficientInput e k) : ℂ
Lean definition
/-- Collect coefficients in one certified convergent output fibre. -/
noncomputable def regroupCoefficients {ι : Type*} {e : ι → ℕ} {k : ℕ}
    (c : RegroupCoefficientInput e k) : ℂ :=
  ∑' i : {i // e i = k}, c.val i
source
Theorem 2.7.27 Characterization of the collected coefficient
✓ 🤖

If \((c_i)_{e(i)=k}\) is summable, its sum is \(c^{[e]}_k\).

Lean Formalisation
theorem Polynomial.hasSum_regroupCoefficients.{u_1} {ι : Type u_1} {e : ι → ℕ} {k : ℕ}
  (c : Polynomial.RegroupCoefficientInput e k) : HasSum (fun i => ↑c ↑i) (Polynomial.regroupCoefficients c)
Lean proof
/-- The collected coefficient is the classical sum of its fibre. -/
theorem hasSum_regroupCoefficients {ι : Type*} {e : ι → ℕ} {k : ℕ}
    (c : RegroupCoefficientInput e k) :
    HasSum (fun i : {i // e i = k} ↦ c.val i) (regroupCoefficients c) :=
  c.property.hasSum
source

If \(\sum _i|c_i|{\lt}\infty \), then \(\sum _k|c^{[e]}_k|\le \sum _i|c_i|\). For mode values \(P_k\) with \(|P_k|\le w_k\) and \(\sum _i|c_i|w_{e(i)}{\lt}\infty \), grouping the contributions preserves the represented value:

\[ \sum _k\left(\sum _{i:e(i)=k}c_iP_{e(i)}\right)=\sum _i c_iP_{e(i)}. \]

Every inner contribution family is summable, even when \(w_k=P_k=0\). If each unweighted coefficient fibre is also summable, this becomes

\[ \sum _k c^{[e]}_kP_k=\sum _i c_iP_{e(i)}. \]

In particular, absolute coefficient summability suffices for a uniformly bounded family. Degree-dependent weights allow growing Jacobi mode norms.

Reference: elementary regrouping, used for the aliasing formula [ATAP, Theorem 4.2].

Lean Formalisation
theorem Polynomial.summable_norm_regroupCoefficients.{u_1} {ι : Type u_1} {c : ι → ℂ} (hc : Summable fun i => ‖c i‖)
  (e : ι → ℕ) :
  Summable fun k => ‖Polynomial.regroupCoefficients (Polynomial.RegroupCoefficientInput.ofSummableNorm hc e k)‖
Lean proof
/-- Collecting modes preserves absolute summability. -/
theorem summable_norm_regroupCoefficients {ι : Type*} {c : ι → ℂ}
    (hc : Summable (fun i ↦ ‖c i‖)) (e : ι → ℕ) :
    Summable (fun k ↦ ‖regroupCoefficients (RegroupCoefficientInput.ofSummableNorm hc e k)‖) := by
  have h := hc.hasSum.tsum_fiberwise e
  apply Summable.of_nonneg_of_le (fun _ ↦ norm_nonneg _) _ h.summable
  intro k
  exact norm_tsum_le_tsum_norm (hc.subtype (fun i ↦ e i = k))
source
Definition 2.7.29 Domain of a Chebyshev product coefficient
✓ 🤖
#

At output index \(k\), consider pairs of coefficient sequences \(a,b\) for which the family \((a_mb_n)_{|m-n|=k}\) is summable. This condition concerns only the chosen output index.

Lean Formalisation
inductive Polynomial.Chebyshev.ChebyshevProductInput (k : ℕ) : Type
Lean definition
/-- Two coefficient sequences with convergence in the chosen difference fibre.
The addition fibre is finite, so requires no assumption (DLMF 18.18.21). -/
structure ChebyshevProductInput (k : ℕ) where
  left : ℕ → ℂ
  right : ℕ → ℂ
  difference_summable : Summable (fun p : {p : ℕ × ℕ // ((p.1 : ℤ) - p.2).natAbs = k} ↦
    left p.val.1 * right p.val.2)
source

For \(k\in \mathbb {N}\), the set \(\{ (m,n)\in \mathbb {N}^2:m+n=k\} \) is finite, so \(\sum _{m+n=k}a_mb_n\) exists for any sequences \(a,b\). If both sequences are absolutely summable, then \((a_mb_n)_{|m-n|=k}\) is summable for every \(k\), and \((a,b)\) belongs to the product-coefficient domain of Definition 2.7.29.

Lean Formalisation
theorem Polynomial.Chebyshev.finite_add_fibre (k : ℕ) : Finite { p // p.1 + p.2 = k }
Lean proof
/-- Only finitely many natural pairs have a prescribed sum. -/
theorem finite_add_fibre (k : ℕ) : Finite {p : ℕ × ℕ // p.1 + p.2 = k} := by
  apply Finite.of_injective
    (fun p : {p : ℕ × ℕ // p.1 + p.2 = k} ↦ (⟨p.val.1, by have := p.property; omega⟩ : Fin (k+1)))
  intro p q h
  apply Subtype.ext
  apply Prod.ext
  · exact congrArg Fin.val h
  · have h1 := congrArg Fin.val h
    have hp := p.property
    have hq := q.property
    dsimp at h1
    omega
source
Theorem 2.7.31 Characterization of a Chebyshev product coefficient
✓ 🤖

For \(k\in \mathbb {N}\) and sequences \(a,b\) such that \((a_mb_n)_{|m-n|=k}\) is summable, the product coefficient is

\[ c_k=\frac12\left(\sum _{m+n=k}a_mb_n+\sum _{|m-n|=k}a_mb_n\right). \]

The first sum is finite. The formula includes \(k=0\).

Lean Formalisation
theorem Polynomial.Chebyshev.chebyshevProductCoefficients_eq {k : ℕ} (d : Polynomial.Chebyshev.ChebyshevProductInput k) :
  Polynomial.Chebyshev.chebyshevProductCoefficients d =
    (∑' (p : { p // p.1 + p.2 = k }), d.left (↑p).1 * d.right (↑p).2 +
        ∑' (p : { p // (↑p.1 - ↑p.2).natAbs = k }), d.left (↑p).1 * d.right (↑p).2) /
      2
Lean proof
/-- Both classical fibres contribute to the full-constant product coefficient. -/
theorem chebyshevProductCoefficients_eq {k : ℕ} (d : ChebyshevProductInput k) :
    chebyshevProductCoefficients d =
      ((∑' p : {p : ℕ × ℕ // p.1 + p.2 = k}, d.left p.val.1 * d.right p.val.2) +
        ∑' p : {p : ℕ × ℕ // ((p.1 : ℤ) - p.2).natAbs = k},
          d.left p.val.1 * d.right p.val.2) / 2 := rfl
source

2.7.5 Other intervals

An affine coordinate maps \([-1,1]\) to \([a,b]\) when \(a{\lt}b\). It preserves approximation errors and supplies the scale factors for differentiation and integration.

Definition 2.7.32 Affine interval coordinates
✓ 🤖

For arbitrary \(a,b\) define \(A\); for \(a\ne b\) define its inverse coordinate \(B\):

\[ A(t)=\frac{b-a}{2}t+\frac{a+b}{2},\qquad B(x)=\frac{2x-a-b}{b-a}. \]

References: Chebfun interval scaling [DHT14]; [DLMF, 3.11.12].

Lean Formalisation
def Polynomial.Chebyshev.intervalMap (a b t : ℝ) : ℝ
Lean definition
/-- The affine map from `[-1,1]` to `[a,b]` used for Chebfun interval scaling. -/
noncomputable def intervalMap (a b t : ℝ) : ℝ := (b - a) / 2 * t + (a + b) / 2
source

For \(a{\lt}b\), \(A\) and \(B\) are inverse maps between \([-1,1]\) and \([a,b]\), with \(A(-1)=a\) and \(A(1)=b\). Composition \(p\circ B\) is ordinary polynomial composition and preserves degree. Uniform approximation errors transfer unchanged. At points where \(g\) has derivative \(d\) at \(B(x)\), \(g\circ B\) has derivative \(2d/(b-a)\) at \(x\). Moreover,

\[ \int _a^b f(x)\, dx=\frac{b-a}{2}\int _{-1}^1 f(A(t))\, dt. \]

The integral identity assumes that \(f\) is integrable between \(a\) and \(b\) and also asserts integrability of \(f\circ A\) on \([-1,1]\). It holds for either orientation and for equal endpoints. The approximation and interval-membership assertions assume \(a{\lt}b\); the coordinate \(B\) requires distinct endpoints.

Reference: affine change of variables, as in [DLMF, 3.11.12].

Lean Formalisation
theorem Polynomial.Chebyshev.intervalMap_neg_one (a b : ℝ) : Polynomial.Chebyshev.intervalMap a b (-1) = a
Lean proof
@[simp] theorem intervalMap_neg_one (a b : ℝ) : intervalMap a b (-1) = a := by
  unfold intervalMap
  ring
source
Oriented integrals and termwise operations
Definition 2.7.34 Integrable functions between two endpoints
✓ 🤖
#

For real endpoints \(a,b\), consider real functions \(f\) with finite Lebesgue integral of \(|f|\) between the endpoints. Either orientation is allowed. At equal endpoints every function is admitted.

Lean Formalisation
def MeasureTheory.IntervalIntegrableInput (a b : ℝ) : Type
Lean definition
/-- Classical interval-integrable real input, including either orientation and equal endpoints. -/
abbrev _root_.MeasureTheory.IntervalIntegrableInput (a b : ℝ) := {f : ℝ → ℝ // IntervalIntegrable f volume a b}
source
Theorem 2.7.35 Interval-input characterisation
✓ 🤖

If \(f\) belongs to the interval-integrability domain for endpoints \(a,b\), then \(f\) is integrable on the interval between \(a\) and \(b\); its oriented integral \(\int _a^b f(x)\, dx\) therefore exists.

Lean Formalisation
theorem MeasureTheory.IntervalIntegrableInput.integrable {a b : ℝ} (f : MeasureTheory.IntervalIntegrableInput a b) :
  IntervalIntegrable (↑f) MeasureTheory.volume a b
Lean proof
/-- Bundled interval data have genuine oriented integrals. -/
theorem _root_.MeasureTheory.IntervalIntegrableInput.integrable {a b : ℝ} (f : IntervalIntegrableInput a b) :
    IntervalIntegrable f.val volume a b := f.property
source
Theorem 2.7.36 Series tail and product error bounds
✓ 🤖

If \(\sum f_n=s\), \(|f_n|\le v_n\) and \(\sum v_n{\lt}\infty \), then \(|s-\sum _{n{\lt}N}f_n|\le \sum _{n\ge N}v_n\). For complex numbers with \(|f|\le A\), \(|q|\le B\), \(|f-p|\le \varepsilon \) and \(|g-q|\le \eta \), one has \(|fg-pq|\le A\eta +B\varepsilon \).

Reference: elementary estimates, used for the products and calculus of [ATAP, Chapters 3 and 21].

Lean Formalisation
theorem Polynomial.norm_series_sub_sum_le_tail {f : ℕ → ℂ} {v : ℕ → ℝ} {s : ℂ} (hs : HasSum f s) (hv : Summable v)
  (hb : ∀ (n : ℕ), ‖f n‖ ≤ v n) (N : ℕ) : ‖s - ∑ n ∈ Finset.range N, f n‖ ≤ ∑' (n : ℕ), v (n + N)
Lean proof
/-- Any norm-majorized series has a truncation bound by the corresponding tail.
This is shared by derivative, primitive and product expansions. -/
theorem norm_series_sub_sum_le_tail {f : ℕ → ℂ} {v : ℕ → ℝ} {s : ℂ}
    (hs : HasSum f s) (hv : Summable v) (hb : ∀ n, ‖f n‖ ≤ v n) (N : ℕ) :
    ‖s - ∑ n ∈ Finset.range N, f n‖ ≤ ∑' n, v (n + N) := by
  have he := hs.summable.sum_add_tsum_nat_add N
  rw [hs.tsum_eq] at he
  have ht : s - ∑ n ∈ Finset.range N, f n = ∑' n, f (n + N) := by
    rw [← he]; abel
  rw [ht]
  have hn : Summable (fun n ↦ ‖f (n + N)‖) :=
    Summable.of_nonneg_of_le (fun _ ↦ norm_nonneg _) (fun n ↦ hb (n + N))
      ((summable_nat_add_iff N).2 hv)
  exact (norm_tsum_le_tsum_norm hn).trans
    (hn.tsum_le_tsum (fun n ↦ hb (n + N)) ((summable_nat_add_iff N).2 hv))
source
Theorem 2.7.37 Differentiation of normally convergent polynomial expansions
✓ 🤖

Let \(P_n\in \mathbb C[X]\), \(a_n\in \mathbb C\) and \(U\subseteq \mathbb C\) be open. Suppose \(|a_nP_n(z)|\le u_n\) on \(U\), with \(\sum u_n{\lt}\infty \). Then \(S(z)=\sum a_nP_n(z)\) satisfies \(S'(z)=\sum a_nP_n'(z)\) on \(U\), and derivatives of partial sums converge uniformly on each compact \(K\subset U\). If \(z\in U\) and the circle of radius \(\delta {\gt}0\) about \(z\) lies in \(U\), then

\[ \left|S'(z)-\sum _{n{\lt}N}a_nP_n'(z)\right| \le \delta ^{-1}\sum _{n\ge N}u_n. \]

No orthogonality hypothesis is needed.

Reference: Weierstrass’s theorem on locally uniform limits of analytic functions.

Lean Formalisation
theorem Polynomial.hasSum_derivative_series {P : ℕ → Polynomial ℂ} {a : ℕ → ℂ} {u : ℕ → ℝ} {U : Set ℂ} (hU : IsOpen U)
  (hu : Summable u) (hb : ∀ (n : ℕ), ∀ z ∈ U, ‖a n * Polynomial.eval z (P n)‖ ≤ u n) {z : ℂ} (hz : z ∈ U) :
  HasSum (fun n => a n * Polynomial.eval z (Polynomial.derivative (P n)))
    (deriv (fun w => ∑' (n : ℕ), a n * Polynomial.eval w (P n)) z)
Lean proof
/-- A summable uniform majorant permits differentiation of a complex polynomial
expansion on an open set. No orthogonality or interval hypothesis is needed. -/
theorem hasSum_derivative_series {P : ℕ → ℂ[X]} {a : ℕ → ℂ} {u : ℕ → ℝ}
    {U : Set ℂ} (hU : IsOpen U) (hu : Summable u)
    (hb : ∀ n z, z ∈ U → ‖a n * (P n).eval z‖ ≤ u n) {z : ℂ} (hz : z ∈ U) :
    HasSum (fun n ↦ a n * (P n).derivative.eval z)
      (deriv (fun w ↦ ∑' n, a n * (P n).eval w) z) := by
  have h := Complex.hasSum_deriv_of_summable_norm hu
    (fun n ↦ ((P n).differentiable.const_mul (a n)).differentiableOn) hU hb hz
  simpa only [deriv_const_mul_field, Polynomial.deriv] using h
source
Theorem 2.7.38 Termwise integration under a uniform majorant
✓ 🤖
#

For continuous \(F_n:\mathbb R\to \mathbb C\), suppose \(|F_n(x)|\le u_n\) between \(a\) and \(b\), \(\sum u_n{\lt}\infty \), and \(\sum F_n(x)=f(x)\) there. Then \(\sum _n\int _a^b F_n(x)\, dx=\int _a^b f(x)\, dx\). Either orientation of the interval is allowed.

Reference: dominated convergence for series.

Lean Formalisation
theorem Polynomial.hasSum_integral_series {F : ℕ → ℝ → ℂ} {f : ℝ → ℂ} {u : ℕ → ℝ} {a b : ℝ} (hF : ∀ (n : ℕ), Continuous (F n))
  (hu : Summable u) (hb : ∀ (n : ℕ), ∀ x ∈ Set.uIcc a b, ‖F n x‖ ≤ u n)
  (hf : ∀ x ∈ Set.uIcc a b, HasSum (fun n => F n x) (f x)) :
  HasSum (fun n => ∫ (x : ℝ) in a..b, F n x) (∫ (x : ℝ) in a..b, f x)
Lean proof
/-- A summable uniform majorant permits termwise integration on any compact
real interval, for complex-valued expansions. -/
theorem hasSum_integral_series {F : ℕ → ℝ → ℂ} {f : ℝ → ℂ} {u : ℕ → ℝ} {a b : ℝ}
    (hF : ∀ n, Continuous (F n)) (hu : Summable u)
    (hb : ∀ n x, x ∈ uIcc a b → ‖F n x‖ ≤ u n)
    (hf : ∀ x ∈ uIcc a b, HasSum (fun n ↦ F n x) (f x)) :
    HasSum (fun n ↦ ∫ x in a..b, F n x) (∫ x in a..b, f x) := by
  exact intervalIntegral.hasSum_integral_of_dominated_convergence (fun n _ ↦ u n)
    (fun n ↦ (hF n).aestronglyMeasurable)
    (fun n ↦ Eventually.of_forall fun x hx ↦ hb n x (uIoc_subset_uIcc hx))
    (Eventually.of_forall fun _ _ ↦ hu) intervalIntegrable_const
    (Eventually.of_forall fun x hx ↦ hf x (uIoc_subset_uIcc hx))
source

If \(\sum _n|a_n|{\lt}\infty \), then \(S_a\) is continuous on \([-1,1]\), \(|S_a(x)|\le \sum _n|a_n|\), and its integral Chebyshev coefficient at index \(k\) is exactly \(a_k\), including the full constant coefficient. More precisely, any \(f\in \mathcal I_k^{\mathbb {C}}\) agreeing with \(S_a\) on \([-1,1]\) has coefficient \(a_k\). All interval points belong to \(D_a\).

Reference: [ATAP, Chapters 3 and 4].

Lean Formalisation
theorem Polynomial.Chebyshev.norm_eval_T_complex_le_one (n : ℕ) {x : ℝ} (hx : x ∈ Set.Icc (-1) 1) :
  ‖Polynomial.eval (↑x) (Polynomial.Chebyshev.T ℂ ↑n)‖ ≤ 1
Lean proof
/-- Complex Chebyshev modes have norm at most one on the real interval. -/
theorem norm_eval_T_complex_le_one (n : ℕ) {x : ℝ} (hx : x ∈ Icc (-1 : ℝ) 1) :
    ‖(T ℂ n).eval (x : ℂ)‖ ≤ 1 := by
  rw [← complex_ofReal_eval_T, Complex.norm_real, Real.norm_eq_abs]
  exact abs_eval_T_real_le_one _ (abs_le.mpr hx)
source