Signed Toeplitz perturbations of the Chebyshev rows

The Chebyshev polynomials of the second kind are the rows of $1/(1-tz+z^2)$. Their real-rootedness and interlacing survive a perturbation of the denominator by higher powers of $z$ with coefficients of either sign, under explicit size bounds.

Results

For real $c_2,\dots,c_s$ define monic polynomials $P_n(t)$ of degree $n$ by $$ \sum_{n\ge0}P_n(t)\,z^n=\frac1{1-tz+z^2+\sum_{j=2}^sc_jz^{j+1}} . $$ For $c=0$ these are the Chebyshev polynomials of the second kind in the variable $t=2\cos\theta$. For $R>0$ put $$ A(R)=\sum_{j=2}^s j\,|c_j|\,R^{j+1},\qquad B(R)=\sum_{j=2}^s j(j-1)\,|c_j|\,R^{j+1}. $$

Theorem. Let $R>0$ with $A(R)\le R^2-1$ and $B(R)\le1$. Then every $P_n$ is real-rooted with simple roots, $P_n\ll P_{n+1}$, and $P_n,P_{n+1}$ have no common root.

Corollary (bandwidth criterion). Let $s\ge2$. If $$ \sum_{j=2}^s j\,|c_j|\le\frac1s\Bigl(1-\frac1s\Bigr)^{(s-1)/2}, $$ then $P_n\ll P_{n+1}$ for all $n$.

Proof

With $b(z)=z^{-1}+z+\sum_jc_jz^j$, the real values of $b$ along the curve $\operatorname{Im}b(\rho e^{i\theta})=0$ are strictly decreasing in the angle $\theta\in(0,\pi)$ under the two hypotheses.

References

The unperturbed rows satisfy $P_{n+1}=tP_n-P_{n-1}$; see Favard recurrences.

Definitions

  • The denominator 1 - t z + z² + ∑ c_j z^(j+1) as a series with polynomial coefficients

    RealRooted.ToeplitzPerturbation.denominatorsource
    def denominator : PowerSeries ℝ[X] :=
      1 - PowerSeries.C X * PowerSeries.X + PowerSeries.X ^ 2 +
        ∑ j ∈ Finset.Icc 2 s, PowerSeries.C (Polynomial.C (c j)) * PowerSeries.X ^ (j + 1)
  • The rows P_n, the coefficients of the reciprocal of the denominator

    RealRooted.ToeplitzPerturbation.rowsource
    def row (n : ℕ) : ℝ[X] := PowerSeries.coeff n (rowSeries s c)
  • A(R) = ∑ j |c_j| R^(j+1)

    RealRooted.ToeplitzPerturbation.perturbationAsource
    def perturbationA (R : ℝ) : ℝ := ∑ j ∈ Finset.Icc 2 s, j * |c j| * R ^ (j + 1)
  • B(R) = ∑ j (j - 1) |c_j| R^(j+1)

    RealRooted.ToeplitzPerturbation.perturbationBsource
    def perturbationB (R : ℝ) : ℝ := ∑ j ∈ Finset.Icc 2 s, j * (j - 1) * |c j| * R ^ (j + 1)

Theorems

  • If A(R) ≤ R² - 1 and B(R) ≤ 1, consecutive rows strictly interlaceMain resultRealRooted original

    RealRooted.ToeplitzPerturbation.strictInterl_row_succsource
    theorem strictInterl_row_succ (hR : 0 < R) (hA : perturbationA s c R ≤ R ^ 2 - 1)
        (hB : perturbationB s c R ≤ 1) (n : ℕ) :
        RealRooted.StrictInterl (row s c n) (row s c (n + 1))
  • Every row has only simple rootsRealRooted original

    RealRooted.ToeplitzPerturbation.hasSimpleRoots_rowsource
    theorem hasSimpleRoots_row (hR : 0 < R) (hA : perturbationA s c R ≤ R ^ 2 - 1)
        (hB : perturbationB s c R ≤ 1) (n : ℕ) : RealRooted.HasSimpleRoots (row s c n)
  • Every row is real-rootedRealRooted original

    RealRooted.ToeplitzPerturbation.splits_rowsource
    theorem splits_row (hR : 0 < R) (hA : perturbationA s c R ≤ R ^ 2 - 1)
        (hB : perturbationB s c R ≤ 1) (n : ℕ) : (row s c n).Splits
  • Consecutive rows have no common rootRealRooted original

    RealRooted.ToeplitzPerturbation.eval_row_ne_zero_of_isRoot_row_succsource
    theorem eval_row_ne_zero_of_isRoot_row_succ (hR : 0 < R) (hA : perturbationA s c R ≤ R ^ 2 - 1)
        (hB : perturbationB s c R ≤ 1) (n : ℕ) {x : ℝ} (hx : (row s c (n + 1)).IsRoot x) :
        (row s c n).eval x ≠ 0
  • The bandwidth criterion ∑ j |c_j| ≤ (1/s)(1 - 1/s)^((s-1)/2) sufficesRealRooted original

    RealRooted.ToeplitzPerturbation.strictInterl_row_succ_of_sum_lesource
    theorem strictInterl_row_succ_of_sum_le (hs : 2 ≤ s)
        (hS : ∑ j ∈ Finset.Icc 2 s, (j : ℝ) * |c j| ≤ 1 / s * (1 - 1 / (s : ℝ)) ^ (((s : ℝ) - 1) / 2))
        (n : ℕ) : RealRooted.StrictInterl (row s c n) (row s c (n + 1))
  • The row P_n is monic of degree nRealRooted original

    RealRooted.ToeplitzPerturbation.isMonicOfDegree_rowsource
    theorem isMonicOfDegree_row (n : ℕ) : (row s c n).IsMonicOfDegree n
  • The real values of b along the curve Im b = 0 are strictly decreasing in the angleRealRooted original

    RealRooted.ToeplitzPerturbation.strictAntiOn_reB_rhosource
    theorem strictAntiOn_reB_rho (hR : 0 < R) (hA : perturbationA s c R ≤ R ^ 2 - 1)
        (hB : perturbationB s c R ≤ 1) :
        StrictAntiOn (fun θ => reB s c θ (rho s c R θ)) (Set.Ioo 0 Real.pi)

Lean source RealRooted/Challenges/Interlacing/SignedToeplitzPerturbations.lean at revision d6670742. Formalized 2026-11-09.