Interlacing for linear recurrences

Consecutive rows of a linear recurrence interlace when their roots stay in a window on which the coefficient of the derivative, or of the older row, is nonpositive, and the signs outside the window keep the next row's roots inside. Three-term, lag, delay and product recurrences are variants of this principle.

Results

In the window theorems, $P_n$ are real polynomials with $\deg P_n=D_0+n$ and positive leading coefficient, and $A_n,B_n,a_n,b_n$ are real polynomials; a sign condition on a set holds at every point of the set. When $D_0=0$ we also assume $P_0\ll P_1$.

Theorem (root window). Let $P_{n+1}=A_nP_n'+B_nP_n$ and $L\le U$. Suppose that all roots of $P_0$ are real and lie in $[L,U]$, and that for every $n$

Then $P_n\ll P_{n+1}$ for all $n$. The same holds with no lower bound: all roots of $P_0$ are at most $U$, $A_n\le0$ on $(-\infty,U]$, and $A_n\ge0$, $B_n>0$ on $(U,\infty)$.

Theorem (three-term recurrences). Let $P_{n+2}=a_nP_{n+1}+b_nP_n$ with $P_0\ll P_1$, all roots of $P_0$ and $P_1$ in $[L,U]$, and for all $n$: $b_n\le0$ on $[L,U]$; $a_n>0$ and $b_n\ge0$ on $(U,\infty)$; $a_n<0$ and $b_n\ge0$ on $(-\infty,L)$. Then $P_n\ll P_{n+1}$ for all $n$.

Theorem (delay recurrences). Let $p:\mathbb N\to\mathbb N$ be weakly increasing on $n\ge1$ with $p(n)<n$, let $w(n)\ge0$, $Q_0=1$ and $$ Q_{n+1}=Q_n+w(n+1)\,x\,Q_{p(n+1)}. $$ Then every $Q_n$ has nonnegative coefficients and is real-rooted, and $Q_i\ll Q_n$ whenever $p(n)\le i\le n$. The same holds for $F_{n+1}=a(n+1)F_n+b(n+1)\,x\,F_{p(n+1)}$ with $F_0=1$, $a(n)>0$ and $b(n)\ge0$.

The following variants also hold.

Proof

Each step is the Liu–Wang or Ma–Wang criterion: if the roots of $P_n$ lie in the window, then $A_n\le0$ at these roots gives $P_n\ll P_{n+1}$. Beyond the window $P_n$ and $P_n'$ have constant signs, and the sign conditions on $A_n$ and $B_n$ make $P_{n+1}$ nonzero there, so its roots stay in the window. The delay recurrences follow the induction of [Fis06, Example 16.10] with the interlacing cone rules of [Wag92, Section 3], and for positive affine lags $P_{n+1}-P_n$ has nonnegative coefficients, so the Liu–Wang criterion applies [LW07].

References

  1. [LW07] Lily L. Liu & Yi Wang. A unified approach to polynomial sequences with only real zeros. Advances in Applied Mathematics, 38(4), 542-560, 2007.
    BibTeX
    @article{LiuWang2007,
      doi = {10.1016/j.aam.2006.02.003},
      url2 = {https://doi.org/10.1016/j.aam.2006.02.003},
      year = {2007},
      month = may,
      publisher = {Elsevier {BV}},
      volume = {38},
      number = {4},
      pages = {542--560},
      author = {Lily L. Liu and Yi Wang},
      title = {A unified approach to polynomial sequences with only real zeros},
      journal = {Advances in Applied Mathematics}
    }
  2. [MW08] Shi-Mei Ma & Yi Wang. $q$-Eulerian polynomials and polynomials with only real zeros. The Electronic Journal of Combinatorics, 15(1), Research Paper 17, 2008.
    BibTeX
    @article{MaWang2008,
      doi = {10.37236/741},
      url2 = {https://doi.org/10.37236/741},
      year = {2008},
      month = jan,
      publisher = {The Electronic Journal of Combinatorics},
      volume = {15},
      number = {1},
      author = {Shi-Mei Ma and Yi Wang},
      title = {$q$-{E}ulerian Polynomials and Polynomials with Only Real Zeros},
      pages = {Research Paper 17},
      journal = {The Electronic Journal of Combinatorics}
    }
  3. [Fis06] Steve Fisk. Polynomials, roots, and interlacing. arXiv e-prints, 2006.
    BibTeX
    @article{Fisk2006x,
      Author = {Steve Fisk},
      Title = {Polynomials, roots, and interlacing},
      Year = {2006},
      Eprint = {arXiv:math/0612833},
      journal = {arXiv e-prints}
    }
  4. [Wag92] David G Wagner. Total positivity of Hadamard products. Journal of Mathematical Analysis and Applications, 163(2), 459-483, 1992.
    BibTeX
    @article{Wagner1992,
      doi = {10.1016/0022-247x(92)90261-b},
      url2 = {https://doi.org/10.1016/0022-247x(92)90261-b},
      year = {1992},
      month = jan,
      publisher = {Elsevier {BV}},
      volume = {163},
      number = {2},
      pages = {459--483},
      author = {David G Wagner},
      title = {Total positivity of {H}adamard products},
      journal = {Journal of Mathematical Analysis and Applications}
    }
  5. [Bra06] Petter Brändén. On linear transformations preserving the Pólya frequency property. Transactions of the American Mathematical Society, 358(8), 3697-3716, 2006.
    BibTeX
    @article{Branden2006,
      title = {On linear transformations preserving the {P}{\'{o}}lya frequency property},
      volume = {358},
      ISSN = {1088-6850},
      url = {http://dx.doi.org/10.1090/S0002-9947-06-03856-6},
      DOI = {10.1090/s0002-9947-06-03856-6},
      number = {8},
      journal = {Transactions of the American Mathematical Society},
      publisher = {American Mathematical Society (AMS)},
      author = {Br{\"a}nd{\'e}n, Petter},
      year = {2006},
      month = feb,
      pages = {3697--3716}
    }

Definitions

  • The normalized fixed derivatives (r!)⁻¹ D^r (X^r (1 + X)^n)

    RealRooted.binomialDerivativeRowsource
    @[expose] noncomputable def binomialDerivativeRow (r n : ℕ) : ℝ[X] :=
      C (r.factorial : ℝ)⁻¹ * derivative^[r] (X ^ r * (1 + X) ^ n)

Theorems

  • Rows of P_{n+1} = A_n P_n′ + B_n P_n interlace if their roots stay in a windowMain result

    RealRooted.derivativeRecurrence_interlaces_of_roots_mem_Iccsource
    theorem derivativeRecurrence_interlaces_of_roots_mem_Icc {L U : ℝ}
        (hrec : ∀ n, P (n + 1) = A n * (P n).derivative + B n * P n)
        (hdeg : ∀ n, (P n).natDegree = D₀ + n) (hpos : ∀ n, 0 < (P n).leadingCoeff)
        (hA : ∀ n x, L ≤ x → x ≤ U → (A n).eval x ≤ 0)
        (hAU : ∀ n x, U < x → 0 ≤ (A n).eval x) (hBU : ∀ n x, U < x → 0 < (B n).eval x)
        (hAL : ∀ n x, x < L → 0 ≤ (A n).eval x) (hBL : ∀ n x, x < L → (B n).eval x < 0)
        (h0 : (P 0).Splits) (hW0 : ∀ t ∈ (P 0).roots, L ≤ t ∧ t ≤ U)
        (h01 : D₀ = 0 → Interlaces (P 0) (P 1)) (n : ℕ) :
        Interlaces (P n) (P (n + 1))
  • Interlacing with an upper root bound

    RealRooted.derivativeRecurrence_interlaces_of_roots_lesource
    theorem derivativeRecurrence_interlaces_of_roots_le {U : ℝ}
        (hrec : ∀ n, P (n + 1) = A n * (P n).derivative + B n * P n)
        (hdeg : ∀ n, (P n).natDegree = D₀ + n) (hpos : ∀ n, 0 < (P n).leadingCoeff)
        (hA : ∀ n x, x ≤ U → (A n).eval x ≤ 0)
        (hAU : ∀ n x, U < x → 0 ≤ (A n).eval x) (hBU : ∀ n x, U < x → 0 < (B n).eval x)
        (h0 : (P 0).Splits) (hW0 : ∀ t ∈ (P 0).roots, t ≤ U)
        (h01 : D₀ = 0 → Interlaces (P 0) (P 1)) (n : ℕ) :
        Interlaces (P n) (P (n + 1))
  • Degree-bounded interlacing in a root window

    RealRooted.derivativeRecurrence_interlaces_of_roots_mem_Icc_of_degreesource
    theorem derivativeRecurrence_interlaces_of_roots_mem_Icc_of_degree {L U : ℝ}
        (hrec : ∀ n, P (n + 1) = A n * (P n).derivative + B n * P n)
        (hdeg : ∀ n, (P n).natDegree = D₀ + n) (hpos : ∀ n, 0 < (P n).leadingCoeff)
        (hA : ∀ n x, L ≤ x → x ≤ U → (A n).eval x ≤ 0)
        (hABU : ∀ n x, U < x → 0 < (B n).eval x * (x - U) + min ((A n).eval x) 0 * (D₀ + n))
        (hABL : ∀ n x, x < L → 0 < (B n).eval x * (x - L) + min ((A n).eval x) 0 * (D₀ + n))
        (h0 : (P 0).Splits) (hW0 : ∀ t ∈ (P 0).roots, L ≤ t ∧ t ≤ U)
        (h01 : D₀ = 0 → Interlaces (P 0) (P 1)) (n : ℕ) :
        Interlaces (P n) (P (n + 1))
  • Interlacing with a moving lower bound

    RealRooted.derivativeRecurrence_interlaces_of_roots_mem_Icc_mono_divsource
    theorem derivativeRecurrence_interlaces_of_roots_mem_Icc_mono_div {p q : ℕ → ℝ} {U : ℝ}
        (hrec : ∀ n, P (n + 1) = A n * (P n).derivative + B n * P n)
        (hdeg : ∀ n, (P n).natDegree = D₀ + n) (hpos : ∀ n, 0 < (P n).leadingCoeff)
        (hq : ∀ n, 0 < q n) (hL : ∀ n, p (n + 1) * q n ≤ p n * q (n + 1))
        (hA : ∀ n x, p n ≤ q n * x → x ≤ U → (A n).eval x ≤ 0)
        (hAU : ∀ n x, U < x → 0 ≤ (A n).eval x) (hBU : ∀ n x, U < x → 0 < (B n).eval x)
        (hAL : ∀ n x, q n * x < p n → 0 ≤ (A n).eval x)
        (hBL : ∀ n x, q (n + 1) * x < p (n + 1) → (B n).eval x < 0)
        (h0 : (P 0).Splits) (hW0 : ∀ t ∈ (P 0).roots, p 0 ≤ q 0 * t ∧ t ≤ U)
        (h01 : D₀ = 0 → Interlaces (P 0) (P 1)) (n : ℕ) :
        Interlaces (P n) (P (n + 1))
  • Interlacing with a moving upper bound

    RealRooted.derivativeRecurrence_interlaces_of_roots_le_mono_divsource
    theorem derivativeRecurrence_interlaces_of_roots_le_mono_div {p q : ℕ → ℝ} {r : ℝ}
        (hrec : ∀ n, P (n + 1) = A n * (P n).derivative + B n * P n)
        (hdeg : ∀ n, (P n).natDegree = D₀ + n) (hpos : ∀ n, 0 < (P n).leadingCoeff)
        (hq : ∀ n, 0 < q n) (hU : ∀ n, p n * q (n + 1) ≤ p (n + 1) * q n)
        (hA : ∀ n x, q n * x ≤ p n → (A n).eval x ≤ 0)
        (hAB : ∀ n x, p (n + 1) < q (n + 1) * x → x ≤ r →
          0 ≤ (A n).eval x ∧ 0 < (B n).eval x)
        (hD : ∀ n x, r < x → (A n).eval x ≤ 0 ∧
          0 < (B n).eval x * (q (n + 1) * x - p (n + 1)) + q (n + 1) * (A n).eval x * (D₀ + n))
        (h0 : (P 0).Splits) (hW0 : ∀ t ∈ (P 0).roots, q 0 * t ≤ p 0)
        (h01 : D₀ = 0 → Interlaces (P 0) (P 1)) (n : ℕ) :
        Interlaces (P n) (P (n + 1))
  • Two-sided moving windows, either condition on each side

    RealRooted.derivativeRecurrence_interlaces_of_roots_mem_Icc_mono_of_orsource
    theorem derivativeRecurrence_interlaces_of_roots_mem_Icc_mono_of_or {L U : ℕ → ℝ}
        (hrec : ∀ n, P (n + 1) = A n * (P n).derivative + B n * P n)
        (hdeg : ∀ n, (P n).natDegree = D₀ + n) (hpos : ∀ n, 0 < (P n).leadingCoeff)
        (hL : ∀ n, L (n + 1) ≤ L n) (hU : ∀ n, U n ≤ U (n + 1))
        (hA : ∀ n x, L n ≤ x → x ≤ U n → (A n).eval x ≤ 0)
        (hABU : ∀ n x, U (n + 1) < x → (0 ≤ (A n).eval x ∧ 0 < (B n).eval x) ∨
          0 < (B n).eval x * (x - U (n + 1)) + min ((A n).eval x) 0 * (D₀ + n))
        (hABL : ∀ n x, x < L (n + 1) → (0 ≤ (A n).eval x ∧ (B n).eval x < 0) ∨
          0 < (B n).eval x * (x - L (n + 1)) + min ((A n).eval x) 0 * (D₀ + n))
        (h0 : (P 0).Splits) (hW0 : ∀ t ∈ (P 0).roots, L 0 ≤ t ∧ t ≤ U 0)
        (h01 : D₀ = 0 → Interlaces (P 0) (P 1)) (n : ℕ) :
        Interlaces (P n) (P (n + 1))
  • Three-term interlacing in a fixed root window

    RealRooted.threeTerm_interlaces_of_roots_mem_Iccsource
    theorem threeTerm_interlaces_of_roots_mem_Icc {L U : ℝ}
        (hrec : ∀ n, P (n + 2) = a n * P (n + 1) + b n * P n)
        (hdeg : ∀ n, (P n).natDegree = D₀ + n) (hpos : ∀ n, 0 < (P n).leadingCoeff)
        (hb : ∀ n x, L ≤ x → x ≤ U → (b n).eval x ≤ 0)
        (haU : ∀ n x, U < x → 0 < (a n).eval x) (hbU : ∀ n x, U < x → 0 ≤ (b n).eval x)
        (haL : ∀ n x, x < L → (a n).eval x < 0) (hbL : ∀ n x, x < L → 0 ≤ (b n).eval x)
        (hW0 : ∀ t ∈ (P 0).roots, L ≤ t ∧ t ≤ U)
        (hW1 : ∀ t ∈ (P 1).roots, L ≤ t ∧ t ≤ U)
        (h01 : Interlaces (P 0) (P 1)) (n : ℕ) :
        Interlaces (P n) (P (n + 1))
  • Three-term interlacing from a ratio barrier

    RealRooted.threeTerm_interlaces_of_roots_le_of_ratiosource
    theorem threeTerm_interlaces_of_roots_le_of_ratio {U : ℝ} {ρ : ℕ → ℝ}
        (hrec : ∀ n, P (n + 2) = a n * P (n + 1) + b n * P n)
        (hdeg : ∀ n, (P n).natDegree = D₀ + n) (hpos : ∀ n, 0 < (P n).leadingCoeff)
        (hb : ∀ n x, x ≤ U → (b n).eval x ≤ 0)
        (hρ : ∀ n, ρ n * (P n).leadingCoeff ≤ (P (n + 1)).leadingCoeff)
        (ha : ∀ n x, U < x → 0 ≤ (a n).eval x)
        (hab : ∀ n x, U < x → 0 < (a n).eval x * ρ n * (x - U) + (b n).eval x)
        (hW0 : ∀ t ∈ (P 0).roots, t ≤ U) (hW1 : ∀ t ∈ (P 1).roots, t ≤ U)
        (h01 : Interlaces (P 0) (P 1)) (n : ℕ) :
        Interlaces (P n) (P (n + 1))
  • Three-term interlacing with a barrier

    RealRooted.threeTerm_interlaces_of_roots_mem_Icc_of_barriersource
    theorem threeTerm_interlaces_of_roots_mem_Icc_of_barrier {L U : ℝ} {ρ : ℝ → ℝ}
        (hrec : ∀ n, P (n + 2) = a n * P (n + 1) + b n * P n)
        (hdeg : ∀ n, (P n).natDegree = D₀ + n) (hpos : ∀ n, 0 < (P n).leadingCoeff)
        (hb : ∀ n x, L ≤ x → x ≤ U → (b n).eval x ≤ 0)
        (hρ : ∀ x, U < x → 0 < ρ x) (haU : ∀ n x, U < x → ρ x ≤ (a n).eval x)
        (habU : ∀ n x, U < x → ρ x ^ 2 ≤ (a n).eval x * ρ x + (b n).eval x)
        (h1U : ∀ x, U < x → ρ x * (P 0).eval x ≤ (P 1).eval x)
        (haL : ∀ n x, x < L → (a n).eval x < 0) (hbL : ∀ n x, x < L → 0 ≤ (b n).eval x)
        (hW0 : ∀ t ∈ (P 0).roots, L ≤ t ∧ t ≤ U)
        (hW1 : ∀ t ∈ (P 1).roots, L ≤ t ∧ t ≤ U)
        (h01 : Interlaces (P 0) (P 1)) (n : ℕ) :
        Interlaces (P n) (P (n + 1))
  • Pairwise interlacing for lag-feedback windows

    RealRooted.strictInterl_of_lagFeedbacksource
    theorem strictInterl_of_lagFeedback {P : ℕ → ℝ[X]} {p : ℕ} {α : ℝ} {c : ℕ → ℝ}
        (hp : 2 ≤ p) (hα : 0 < α) (hc : ∀ n, 0 < c n)
        (hrec : ∀ n, P (n + p) = C α * P (n + (p - 1)) + C (c n) * X * P n)
        (h0 : ∀ i j, i < j → j < p → StrictInterl (P i) (P j))
        (hnn0 : ∀ i, i < p → HasNonnegCoeffs (P i)) :
        ∀ n i j, i < j → j < p → StrictInterl (P (n + i)) (P (n + j))
  • Splitting for lag-feedback recurrences

    RealRooted.splits_of_lagFeedbacksource
    theorem splits_of_lagFeedback {P : ℕ → ℝ[X]} {p : ℕ} {α : ℝ} {c : ℕ → ℝ}
        (hp : 2 ≤ p) (hα : 0 < α) (hc : ∀ n, 0 < c n)
        (hrec : ∀ n, P (n + p) = C α * P (n + (p - 1)) + C (c n) * X * P n)
        (h0 : ∀ i, i < p → ∃ a : ℝ, 0 < a ∧ P i = C a) (n : ℕ) : (P n).Splits
  • Parity products represented by an order-three recurrence

    RealRooted.eq_parityProduct_of_thirdOrderRecurrencesource
    theorem eq_parityProduct_of_thirdOrderRecurrence
        (hP : ∀ n, P (n + 3) =
          (β + μ) * P (n + 2) - (μ ^ 2 + μ * β) * P (n + 1) + μ ^ 3 * P n)
        (hs : ∀ m, s (m + 2) = β * s (m + 1) - μ ^ 2 * s m)
        (ht : ∀ m, t (m + 2) = β * t (m + 1) - μ ^ 2 * t m)
        (h0 : P 0 = s 0 * t 0) (h1 : P 1 = s 1 * t 0) (h2 : P 2 = s 1 * t 1)
        (hc : s 1 * t 1 - s 2 * t 0 = μ * (s 1 * t 0 - s 0 * t 1)) :
        ∀ m, P (2 * m) = s m * t m ∧ P (2 * m + 1) = s (m + 1) * t m
  • Interlacing of parity products

    RealRooted.interlaces_of_parityProductsource
    theorem interlaces_of_parityProduct
        (hPst : ∀ m, P (2 * m) = s m * t m ∧ P (2 * m + 1) = s (m + 1) * t m)
        (hs : ∀ m, Interlaces (s m) (s (m + 1))) (ht : ∀ m, Interlaces (t m) (t (m + 1)))
        (n : ℕ) : Interlaces (P n) (P (n + 1))
  • Reflection of a second-order derivative recurrence

    RealRooted.eq_reflect_of_secondOrderDerivativeRecurrencesource
    theorem eq_reflect_of_secondOrderDerivativeRecurrence
        {P R A₂ A₁ A₀ B₂ B₁ B₀ : ℕ → ℝ[X]} {D₀ : ℕ}
        (hP : ∀ n, P (n + 1) =
          A₂ n * derivative (derivative (P n)) + A₁ n * derivative (P n) + A₀ n * P n)
        (hR : ∀ n, R (n + 1) =
          B₂ n * derivative (derivative (R n)) + B₁ n * derivative (R n) + B₀ n * R n)
        (hA₂ : ∀ n, (A₂ n).natDegree ≤ 3) (hA₁ : ∀ n, (A₁ n).natDegree ≤ 2)
        (hA₀ : ∀ n, (A₀ n).natDegree ≤ 1)
        (hB₂ : ∀ n, B₂ n = X ^ 2 * reflect 3 (A₂ n))
        (hB₁ : ∀ n, B₁ n =
          -(X * (C (2 * ((D₀ + n : ℕ) : ℝ) - 2) * reflect 3 (A₂ n) + reflect 2 (A₁ n))))
        (hB₀ : ∀ n, B₀ n =
          C (((D₀ + n : ℕ) : ℝ) * (((D₀ + n : ℕ) : ℝ) - 1)) * reflect 3 (A₂ n) +
            C ((D₀ + n : ℕ) : ℝ) * reflect 2 (A₁ n) + reflect 1 (A₀ n))
        (hRdeg : ∀ n, (R n).natDegree ≤ D₀ + n) (h0 : P 0 = reflect D₀ (R 0)) :
        ∀ n, P n = reflect (D₀ + n) (R n)
  • Reflection of a three-term recurrence

    RealRooted.eq_reflect_of_threeTermsource
    theorem eq_reflect_of_threeTerm {P R a b a' b' : ℕ → ℝ[X]} {D₀ : ℕ}
        (hP : ∀ n, P (n + 2) = a n * P (n + 1) + b n * P n)
        (hR : ∀ n, R (n + 2) = a' n * R (n + 1) + b' n * R n)
        (ha : ∀ n, (a n).natDegree ≤ 1) (hb : ∀ n, (b n).natDegree ≤ 2)
        (ha' : ∀ n, a' n = reflect 1 (a n)) (hb' : ∀ n, b' n = reflect 2 (b n))
        (hRdeg : ∀ n, (R n).natDegree ≤ D₀ + n) (h0 : P 0 = reflect D₀ (R 0))
        (h1 : P 1 = reflect (D₀ + 1) (R 1)) :
        ∀ n, P n = reflect (D₀ + n) (R n)
  • Interlacing transferred through reversal

    RealRooted.interlaces_of_eq_reflectsource
    theorem interlaces_of_eq_reflect {P R : ℕ → ℝ[X]} {D₀ : ℕ}
        (hPR : ∀ n, P n = reflect (D₀ + n) (R n)) (hdeg : ∀ n, (R n).natDegree = D₀ + n)
        (hnn : ∀ n, HasNonnegCoeffs (R n)) (hPdeg : ∀ n, (P n).natDegree = D₀ + n)
        (hPpos : ∀ n, 0 < (P n).leadingCoeff)
        (hR : ∀ n, Interlaces (R n) (R (n + 1))) (n : ℕ) : Interlaces (P n) (P (n + 1))
  • Splitting transferred through reversal

    RealRooted.splits_of_eq_reflectsource
    theorem splits_of_eq_reflect {P R : ℕ → ℝ[X]} {D₀ : ℕ}
        (hPR : ∀ n, P n = reflect (D₀ + n) (R n)) (hdeg : ∀ n, (R n).natDegree ≤ D₀ + n)
        (hR : ∀ n, (R n).Splits) (n : ℕ) : (P n).Splits
  • Interlacing from a quadratic division remainder

    RealRooted.strictInterl_quadratic_of_remaindersource
    theorem strictInterl_quadratic_of_remainder {a b c p d α β : ℝ}
        (ha : 0 < a) (hp : 0 < p) (hα : α < 0)
        (hcert : a * β ^ 2 - b * α * β + c * α ^ 2 < 0) :
        StrictInterl (C a * X ^ 2 + C b * X + C c)
          ((C a * X ^ 2 + C b * X + C c) * (C p * X + C d) +
            (C α * X + C β))
  • Interlacing from a linear division remainder

    RealRooted.strictInterl_linear_of_remaindersource
    theorem strictInterl_linear_of_remainder {a b p d β : ℝ} (ha : 0 < a)
        (hp : 0 < p) (hβ : β < 0) :
        StrictInterl (C a * X + C b)
          ((C a * X + C b) * (C p * X + C d) + C β)
  • Power-factor rows from a quadratic remainder criterion

    RealRooted.Interlaces.pow_mul_of_quadratic_remaindersource
    theorem Interlaces.pow_mul_of_quadratic_remainder {q R S : ℝ[X]} (m : ℕ)
        {a b c p d α β : ℝ} (hR : R = C a * X ^ 2 + C b * X + C c)
        (hqS : q * S = R * (C p * X + C d) + (C α * X + C β))
        (hq : q.Splits) (hq0 : q ≠ 0) (ha : 0 < a) (hp : 0 < p) (hα : α < 0)
        (hcert : a * β ^ 2 - b * α * β + c * α ^ 2 < 0) :
        Interlaces (q ^ m * R) (q ^ (m + 1) * S)
  • Power-factor rows from a linear remainder criterion

    RealRooted.Interlaces.pow_mul_of_linear_remaindersource
    theorem Interlaces.pow_mul_of_linear_remainder {q R S : ℝ[X]} (m : ℕ)
        {a b p d β : ℝ} (hR : R = C a * X + C b)
        (hqS : q * S = R * (C p * X + C d) + C β)
        (hq : q.Splits) (hq0 : q ≠ 0) (ha : 0 < a) (hp : 0 < p) (hβ : β < 0) :
        Interlaces (q ^ m * R) (q ^ (m + 1) * S)
  • Interlacing when each next row has its roots in the next window

    RealRooted.derivativeRecurrence_interlaces_of_endpoint_windowssource
    theorem derivativeRecurrence_interlaces_of_endpoint_windows (W : ℕ → ℝ → Prop)
        (hrec : ∀ n, P (n + 1) = A n * (P n).derivative + B n * P n)
        (hdeg : ∀ n, (P n).natDegree = D₀ + n) (hpos : ∀ n, 0 < (P n).leadingCoeff)
        (hA : ∀ n x, W n x → (A n).eval x ≤ 0)
        (hW : ∀ n, (P n).Splits → (∀ t ∈ (P n).roots, W n t) →
          Interlaces (P n) (P (n + 1)) → ∀ t ∈ (P (n + 1)).roots, W (n + 1) t)
        (h0 : (P 0).Splits) (hW0 : ∀ t ∈ (P 0).roots, W 0 t)
        (h01 : D₀ = 0 → Interlaces (P 0) (P 1)) :
        ∀ n, Interlaces (P n) (P (n + 1))
  • Variable-delay recurrences have real-rooted rows

    RealRooted.splits_of_variableDelay_recurrencesource
    theorem splits_of_variableDelay_recurrence
        (Q : ℕ → ℝ[X]) (p : ℕ → ℕ) (w : ℕ → ℝ)
        (hpmono : ∀ {i j}, 1 ≤ i → i ≤ j → p i ≤ p j)
        (hplt : ∀ n, 1 ≤ n → p n < n)
        (hw : ∀ n, 0 ≤ w n)
        (hQ0 : Q 0 = 1)
        (hrec : ∀ n, Q (n + 1) = Q n + C (w (n + 1)) * X * Q (p (n + 1)))
        (n : ℕ) :
        (Q n).Splits
  • Row i interlaces row n whenever p(n) ≤ i ≤ n

    RealRooted.strictInterl_of_variableDelay_recurrencesource
    theorem strictInterl_of_variableDelay_recurrence
        (Q : ℕ → ℝ[X]) (p : ℕ → ℕ) (w : ℕ → ℝ)
        (hpmono : ∀ {i j}, 1 ≤ i → i ≤ j → p i ≤ p j)
        (hplt : ∀ n, 1 ≤ n → p n < n)
        (hw : ∀ n, 0 ≤ w n)
        (hQ0 : Q 0 = 1)
        (hrec : ∀ n, Q (n + 1) = Q n + C (w (n + 1)) * X * Q (p (n + 1)))
        {n i : ℕ} (hpi : p n ≤ i) (hin : i ≤ n) :
        StrictInterl (Q i) (Q n)
  • Variable-delay rows have nonnegative coefficients

    RealRooted.hasNonnegCoeffs_of_variableDelay_recurrencesource
    theorem hasNonnegCoeffs_of_variableDelay_recurrence
        (Q : ℕ → ℝ[X]) (p : ℕ → ℕ) (w : ℕ → ℝ)
        (hpmono : ∀ {i j}, 1 ≤ i → i ≤ j → p i ≤ p j)
        (hplt : ∀ n, 1 ≤ n → p n < n)
        (hw : ∀ n, 0 ≤ w n)
        (hQ0 : Q 0 = 1)
        (hrec : ∀ n, Q (n + 1) = Q n + C (w (n + 1)) * X * Q (p (n + 1)))
        (n : ℕ) :
        HasNonnegCoeffs (Q n)
  • The same interlacing for the scaled recurrence a(n+1) F(n) + b(n+1) X F(p(n+1))

    RealRooted.strictInterl_of_scaled_variableDelay_recurrencesource
    theorem strictInterl_of_scaled_variableDelay_recurrence
        (F : ℕ → ℝ[X]) (p : ℕ → ℕ) (a b : ℕ → ℝ)
        (hpmono : ∀ {i j}, 1 ≤ i → i ≤ j → p i ≤ p j)
        (hplt : ∀ n, 1 ≤ n → p n < n)
        (ha : ∀ n, 0 < a n)
        (hb : ∀ n, 0 ≤ b n)
        (hF0 : F 0 = 1)
        (hrec : ∀ n,
          F (n + 1) = C (a (n + 1)) * F n + C (b (n + 1)) * X * F (p (n + 1)))
        {n i : ℕ} (hpi : p n ≤ i) (hin : i ≤ n) :
        StrictInterl (F i) (F n)
  • Fixed delay L: rows A and B interlace when A ≤ B ≤ A + L

    RealRooted.strictInterl_of_fixedDelay_recurrencesource
    theorem strictInterl_of_fixedDelay_recurrence
        (Q : ℕ → ℝ[X]) (w : ℕ → ℝ) (L : ℕ) (hL : 1 ≤ L)
        (hw : ∀ n, 0 ≤ w n)
        (hQ0 : Q 0 = 1)
        (hrec : ∀ n, Q (n + 1) = Q n + C (w (n + 1)) * X * Q (n + 1 - L))
        {A B : ℕ} (hAB : A ≤ B) (hBA : B ≤ A + L) :
        StrictInterl (Q A) (Q B)
  • Scaled fixed delay L: rows A and B interlace when A ≤ B ≤ A + L

    RealRooted.strictInterl_of_scaled_fixedDelay_recurrencesource
    theorem strictInterl_of_scaled_fixedDelay_recurrence
        (P : ℕ → ℝ[X]) (a b : ℕ → ℝ) (L : ℕ) (hL : 1 ≤ L)
        (ha : ∀ n, 0 < a n) (hb : ∀ n, 0 ≤ b n)
        (hP0 : P 0 = 1)
        (hrec : ∀ n,
          P (n + 1) = C (a (n + 1)) * P n + C (b (n + 1)) * X * P (n + 1 - L))
        {A B : ℕ} (hAB : A ≤ B) (hBA : B ≤ A + L) :
        StrictInterl (P A) (P B)
  • Fixed-delay recurrences started from a constant prefix: interlacing of rows

    RealRooted.strictInterl_of_constant_prefix_fixed_delay_recurrencesource
    theorem strictInterl_of_constant_prefix_fixed_delay_recurrence
        (P : ℕ → ℝ[X]) (c a b : ℕ → ℝ) (L : ℕ) (hL : 1 ≤ L)
        (hc : ∀ i, i < L → 0 < c i) (ha : ∀ n, 0 < a n) (hb : ∀ n, 0 ≤ b n)
        (hprefix : ∀ i, i < L → P i = C (c i))
        (hrec : ∀ n,
          P (n + L) = C (a n) * P (n + L - 1) + C (b n) * X * P n)
        {A B : ℕ} (hAB : A ≤ B) (hBA : B ≤ A + L) :
        StrictInterl (P A) (P B)
  • Constant-prefix rows have only negative roots

    RealRooted.roots_neg_of_constant_prefix_fixed_delay_recurrencesource
    theorem roots_neg_of_constant_prefix_fixed_delay_recurrence
        (P : ℕ → ℝ[X]) (c a b : ℕ → ℝ) (L : ℕ) (hL : 1 ≤ L)
        (hc : ∀ i, i < L → 0 < c i) (ha : ∀ n, 0 < a n) (hb : ∀ n, 0 ≤ b n)
        (hprefix : ∀ i, i < L → P i = C (c i))
        (hrec : ∀ n,
          P (n + L) = C (a n) * P (n + L - 1) + C (b n) * X * P n)
        (n : ℕ) :
        ∀ r ∈ (P n).roots, r < 0
  • Constant-prefix rows have degree n / L

    RealRooted.natDegree_of_constant_prefix_fixed_delay_recurrencesource
    theorem natDegree_of_constant_prefix_fixed_delay_recurrence
        (P : ℕ → ℝ[X]) (c a b : ℕ → ℝ) (L : ℕ) (hL : 1 ≤ L)
        (hc : ∀ i, i < L → 0 < c i) (ha : ∀ n, 0 < a n) (hb : ∀ n, 0 < b n)
        (hprefix : ∀ i, i < L → P i = C (c i))
        (hrec : ∀ n,
          P (n + L) = C (a n) * P (n + L - 1) + C (b n) * X * P n)
        (n : ℕ) :
        (P n).natDegree = n / L
  • Products of real-rooted factors are real-rooted

    RealRooted.isRealRooted_of_product_factor_sequencesource
    theorem isRealRooted_of_product_factor_sequence
        {P F : Nat → ℝ[X]}
        (hbase : P 0 ≠ 0 ∧ (P 0).Splits)
        (hfactor : ∀ n : Nat, F n ≠ 0 ∧ (F n).Splits)
        (hstep : ∀ n : Nat, P (n + 1) = F n * P n) :
        ∀ n : Nat, P n ≠ 0 ∧ (P n).Splits
  • Multiplying by linear factors gives consecutive interlacing

    RealRooted.productSequence_interlacessource
    theorem productSequence_interlaces (hL : ∀ n, (L n).natDegree = 1)
        (h0 : P 0 ≠ 0) (hs0 : (P 0).Splits) (hstep : ∀ n, P (n + 1) = L n * P n) (n : ℕ) :
        Interlaces (P n) (P (n + 1))
  • Degree growth of a product sequence

    RealRooted.productSequence_natDegreesource
    theorem productSequence_natDegree (hL : ∀ n, (L n).natDegree = 1)
        (h0 : P 0 ≠ 0) (hs0 : (P 0).Splits) (hstep : ∀ n, P (n + 1) = L n * P n) :
        ∀ n, (P n).natDegree = (P 0).natDegree + n
  • Affine-factor product closure

    RealRooted.isRealRooted_of_product_affine_sequencesource
    theorem isRealRooted_of_product_affine_sequence
        {P : Nat → ℝ[X]} {s t : Nat → ℝ}
        (hbase : P 0 ≠ 0 ∧ (P 0).Splits)
        (hs : ∀ n : Nat, s n ≠ 0)
        (hstep : ∀ n : Nat, P (n + 1) = (C (s n) * X + C (t n)) * P n) :
        ∀ n : Nat, P n ≠ 0 ∧ (P n).Splits
  • Powered affine product closure

    RealRooted.isRealRooted_of_product_X_add_C_pow_sequencesource
    theorem isRealRooted_of_product_X_add_C_pow_sequence
        {P : Nat → ℝ[X]} {t : Nat → ℝ} {m : Nat → Nat}
        (hbase : P 0 ≠ 0 ∧ (P 0).Splits)
        (hstep : ∀ n : Nat, P (n + 1) = (X + C (t n)) ^ (m n) * P n) :
        ∀ n : Nat, P n ≠ 0 ∧ (P n).Splits
  • Row-wise product lifts

    RealRooted.isRealRooted_of_product_lift_sequencesource
    theorem isRealRooted_of_product_lift_sequence
        {P Q F : Nat → ℝ[X]}
        (hquot : ∀ n : Nat, Q n ≠ 0 ∧ (Q n).Splits)
        (hfactor : ∀ n : Nat, F n ≠ 0 ∧ (F n).Splits)
        (hrow : ∀ n : Nat, P n = F n * Q n) :
        ∀ n : Nat, P n ≠ 0 ∧ (P n).Splits
  • Scalar-monomial lifts

    RealRooted.isRealRooted_of_scalar_monomial_lift_sequencesource
    theorem isRealRooted_of_scalar_monomial_lift_sequence
        {P Q : Nat → ℝ[X]} {c : Nat → ℝ} {m : Nat → Nat}
        (hmodel : ∀ n : Nat, Q n ≠ 0 ∧ (Q n).Splits)
        (hc : ∀ n : Nat, c n ≠ 0)
        (hrow : ∀ n : Nat, P n = C (c n) * (X ^ (m n) * Q n)) :
        ∀ n : Nat, P n ≠ 0 ∧ (P n).Splits
  • Alternating scalar-linear closure

    RealRooted.isRealRooted_of_product_scalar_linear_sequencesource
    theorem isRealRooted_of_product_scalar_linear_sequence
        {P : Nat → ℝ[X]} {a b : Nat → ℝ}
        (hbase : P 0 ≠ 0 ∧ (P 0).Splits)
        (ha : ∀ n : Nat, a n ≠ 0)
        (hscalar : ∀ n : Nat, P (2 * n + 1) = C (a n) * P (2 * n))
        (hlinear : ∀ n : Nat, P (2 * n + 2) = (X + C (b n)) * P (2 * n + 1)) :
        ∀ n : Nat, P n ≠ 0 ∧ (P n).Splits
  • Alternating powered-affine closure

    RealRooted.isRealRooted_of_product_scalar_X_add_C_pow_sequencesource
    theorem isRealRooted_of_product_scalar_X_add_C_pow_sequence
        {P : Nat → ℝ[X]} {a b : Nat → ℝ} {m : Nat → Nat}
        (hbase : P 0 ≠ 0 ∧ (P 0).Splits)
        (ha : ∀ n : Nat, a n ≠ 0)
        (hscalar : ∀ n : Nat, P (2 * n + 1) = C (a n) * P (2 * n))
        (hstep : ∀ n : Nat, P (2 * n + 2) = (X + C (b n)) ^ (m n) *
          P (2 * n + 1)) :
        ∀ n : Nat, P n ≠ 0 ∧ (P n).Splits
  • Endpoint-pair strict interlacing

    RealRooted.strictInterl_endpoint_sum_then_X_pair_sequencesource
    theorem strictInterl_endpoint_sum_then_X_pair_sequence
        {A B : Nat → ℝ[X]}
        (hbase : StrictInterl (A 0) (B 0))
        (hA0_nonneg : HasNonnegCoeffs (A 0))
        (hB0_nonneg : HasNonnegCoeffs (B 0))
        (hstepA : ∀ n : Nat, A (n + 1) = A n + B n)
        (hstepB : ∀ n : Nat, B (n + 1) = B n + X * A (n + 1)) :
        ∀ n : Nat, StrictInterl (A n) (B n)
  • Endpoint-pair real-rootedness

    RealRooted.isRealRooted_of_endpoint_sum_then_X_pair_sequencesource
    theorem isRealRooted_of_endpoint_sum_then_X_pair_sequence
        {A B : Nat → ℝ[X]}
        (hbase : StrictInterl (A 0) (B 0))
        (hA0_nonneg : HasNonnegCoeffs (A 0))
        (hB0_nonneg : HasNonnegCoeffs (B 0))
        (hstepA : ∀ n : Nat, A (n + 1) = A n + B n)
        (hstepB : ∀ n : Nat, B (n + 1) = B n + X * A (n + 1)) :
        ∀ n : Nat, (A n ≠ 0 ∧ (A n).Splits) ∧ (B n ≠ 0 ∧ (B n).Splits)
  • Endpoint-power pair lift

    RealRooted.isRealRooted_of_endpoint_sum_then_X_pair_lift_sequencesource
    theorem isRealRooted_of_endpoint_sum_then_X_pair_lift_sequence
        {P A B : Nat → ℝ[X]} {t : ℝ} {mA mB : Nat → Nat}
        (hbase : StrictInterl (A 0) (B 0))
        (hA0_nonneg : HasNonnegCoeffs (A 0))
        (hB0_nonneg : HasNonnegCoeffs (B 0))
        (hstepA : ∀ n : Nat, A (n + 1) = A n + B n)
        (hstepB : ∀ n : Nat, B (n + 1) = B n + X * A (n + 1))
        (hrowA : ∀ n : Nat, P (2 * n) = (X + C t) ^ (mA n) * A n)
        (hrowB : ∀ n : Nat, P (2 * n + 1) = (X + C t) ^ (mB n) * B n) :
        ∀ n : Nat, P n ≠ 0 ∧ (P n).Splits
  • Interlacing after one linear factor

    RealRooted.interlaces_self_mul_of_natDegree_eq_onesource
    theorem interlaces_self_mul_of_natDegree_eq_one {f L : ℝ[X]} (hf : f ≠ 0) (hs : f.Splits)
        (hL : L.natDegree = 1) : Interlaces f (L * f)
  • Finite products of linear factors

    RealRooted.isRealRooted_finset_prod_X_sub_Csource
    theorem isRealRooted_finset_prod_X_sub_C
        {ι : Type*} (s : Finset ι) (root : ι → ℝ) :
        (∏ j ∈ s, (X - C (root j))) ≠ 0 ∧
          (∏ j ∈ s, (X - C (root j))).Splits
  • Finite linear product sequences

    RealRooted.finiteLinearProductSequence_realRootedsource
    theorem finiteLinearProductSequence_realRooted
        {P : Nat → ℝ[X]} {root : Nat → Nat → ℝ}
        (hroot : ∀ n : Nat,
          P n = ∏ j ∈ Finset.range n, (X - C (root n j))) :
        ∀ n : Nat, P n ≠ 0 ∧ (P n).Splits
  • Fixed derivatives of q (X - a)^n and q (X - a)^(n+1) interlace

    RealRooted.strictInterl_iterate_derivative_mul_X_sub_C_pow_succsource
    theorem strictInterl_iterate_derivative_mul_X_sub_C_pow_succ
        {q : ℝ[X]} (hq_pos : HasPosLeadingCoeff q) (hq : q.Splits)
        {r : ℕ} (hr : r ≤ q.natDegree) (a : ℝ) (n : ℕ) :
        StrictInterl
          (derivative^[r] (q * (X - C a) ^ n))
          (derivative^[r] (q * (X - C a) ^ (n + 1)))
  • Fixed derivatives of q (X - a)^n are real-rooted with positive leading coefficient

    RealRooted.iterate_derivative_mul_X_sub_C_pow_standardsource
    theorem iterate_derivative_mul_X_sub_C_pow_standard
        {q : ℝ[X]} (hq_pos : HasPosLeadingCoeff q) (hq : q.Splits)
        {r : ℕ} (hr : r ≤ q.natDegree) (a : ℝ) (n : ℕ) :
        HasPosLeadingCoeff (derivative^[r] (q * (X - C a) ^ n)) ∧
          derivative^[r] (q * (X - C a) ^ n) ≠ 0 ∧
          (derivative^[r] (q * (X - C a) ^ n)).Splits ∧
          (derivative^[r] (q * (X - C a) ^ n)).natDegree = q.natDegree + n - r
  • Fixed derivatives have roots in any interval containing a and the roots of q

    RealRooted.roots_iterate_derivative_mul_X_sub_C_pow_mem_Iccsource
    theorem roots_iterate_derivative_mul_X_sub_C_pow_mem_Icc
        {q : ℝ[X]} (hq_pos : HasPosLeadingCoeff q) (hq : q.Splits)
        {r : ℕ} (hr : r ≤ q.natDegree) {a u v : ℝ}
        (ha : a ∈ Set.Icc u v) (hroots : ∀ x ∈ q.roots, x ∈ Set.Icc u v)
        (n : ℕ) :
        ∀ x ∈ (derivative^[r] (q * (X - C a) ^ n)).roots, x ∈ Set.Icc u v
  • A pure-lag recurrence for fixed derivatives of q (X - a)^n

    RealRooted.sum_pow_mul_iterate_derivative_mul_X_sub_C_pow_eq_zerosource
    theorem sum_pow_mul_iterate_derivative_mul_X_sub_C_pow_eq_zero
        (q : ℝ[X]) (a : ℝ) (r n : ℕ) :
        ∑ i ∈ Finset.range (r + 2),
          (-1 : ℝ[X]) ^ i * (Nat.choose (r + 1) i : ℝ[X]) *
            (X - C a) ^ i *
              derivative^[r] (q * (X - C a) ^ (n + r + 1 - i)) = 0
  • Binomial derivative rows: the coefficients are C(n, k) C(k + r, r)

    RealRooted.coeff_binomialDerivativeRowsource
    theorem coeff_binomialDerivativeRow (r n k : ℕ) :
        (binomialDerivativeRow r n).coeff k =
          (n.choose k : ℝ) * ((k + r).choose r : ℝ)
  • Binomial derivative rows: a three-term recurrence in n

    RealRooted.binomialDerivativeRow_add_twosource
    theorem binomialDerivativeRow_add_two (r n : ℕ) :
        C (n + 2 : ℝ) * binomialDerivativeRow r (n + 2) =
          (C (2 * n + 3 : ℝ) + C (n + r + 2 : ℝ) * X) *
              binomialDerivativeRow r (n + 1) -
            C (n + 1 : ℝ) * (1 + X) * binomialDerivativeRow r n
  • Consecutive binomial derivative rows interlace

    RealRooted.strictInterl_binomialDerivativeRow_succsource
    theorem strictInterl_binomialDerivativeRow_succ (r n : ℕ) :
        StrictInterl (binomialDerivativeRow r n) (binomialDerivativeRow r (n + 1))
  • Binomial derivative rows have roots in [-1, 0]

    RealRooted.roots_binomialDerivativeRow_mem_Iccsource
    theorem roots_binomialDerivativeRow_mem_Icc (r n : ℕ) :
        ∀ x ∈ (binomialDerivativeRow r n).roots, x ∈ Set.Icc (-1 : ℝ) 0
  • Coefficient positivity of a three-term recurrence through weighted differencesRealRooted original

    RealRooted.hasNonnegCoeffs_and_sub_mul_of_threeTermsource
    theorem hasNonnegCoeffs_and_sub_mul_of_threeTerm
        {P A B : ℕ → ℝ[X]} {R : ℝ[X]}
        (hrec : ∀ n, P (n + 2) = A n * P (n + 1) + B n * P n)
        (hR : HasNonnegCoeffs R)
        (hA : ∀ n, HasNonnegCoeffs (A n - R))
        (hB : ∀ n, HasNonnegCoeffs (R * (A n - R) + B n))
        (hzero : HasNonnegCoeffs (P 0))
        (hone : HasNonnegCoeffs (P 1 - R * P 0))
        (n : ℕ) : HasNonnegCoeffs (P n) ∧
          HasNonnegCoeffs (P (n + 1) - R * P n)
  • Positive affine lags: nonnegative coefficients and successive differencesRealRooted original

    RealRooted.PositiveAffineLag.coefficients_and_degreesource
    theorem coefficients_and_degree
        {P : ℕ → ℝ[X]} {p q : ℝ} {b c d : ℕ → ℝ}
        (hp : 0 < p) (hpq : p ≤ q)
        (hb : ∀ n, 0 ≤ b n) (hc : ∀ n, 0 ≤ c n) (hd : ∀ n, 0 < d n)
        (hP0 : P 0 = C p) (hP1 : P 1 = C q)
        (hrec : ∀ n, P (n + 2) =
          C (1 + b n + c n) * P (n + 1) + (C (d n) * X - C (b n)) * P n) :
        ∀ n, HasNonnegCoeffs (P n) ∧ HasNonnegCoeffs (P (n + 1) - P n) ∧
          0 < (P n).eval 0 ∧ (P n).natDegree = n / 2 ∧ HasPosLeadingCoeff (P n)
  • Positive affine lags: rows interlace, with simple negative rootsRealRooted original

    RealRooted.PositiveAffineLag.interlacing_and_rootssource
    theorem interlacing_and_roots
        {P : ℕ → ℝ[X]} {p q : ℝ} {b c d : ℕ → ℝ}
        (hp : 0 < p) (hpq : p ≤ q)
        (hb : ∀ n, 0 ≤ b n) (hc : ∀ n, 0 ≤ c n) (hd : ∀ n, 0 < d n)
        (hP0 : P 0 = C p) (hP1 : P 1 = C q)
        (hrec : ∀ n, P (n + 2) =
          C (1 + b n + c n) * P (n + 1) + (C (d n) * X - C (b n)) * P n) :
        (∀ n, StrictInterl (P n) (P (n + 1))) ∧ (∀ n, HasSimpleRoots (P n)) ∧
          (∀ n r, (P n).IsRoot r → r < 0) ∧
          (∀ n r, (P (n + 1)).IsRoot r → ¬ (P n).IsRoot r)
  • Positive affine lags: the same conclusions under weaker ratio hypothesesRealRooted original

    RealRooted.PositiveAffineLag.ratio_interlacing_and_rootssource
    theorem ratio_interlacing_and_roots
        {P : ℕ → ℝ[X]} {p q rho : ℝ} {a b d : ℕ → ℝ}
        (hp : 0 < p) (hrho : 0 < rho) (hpq : rho * p ≤ q)
        (hb : ∀ n, 0 ≤ b n) (hd : ∀ n, 0 < d n)
        (ha : ∀ n, rho + b n / rho ≤ a n)
        (hP0 : P 0 = C p) (hP1 : P 1 = C q)
        (hrec : ∀ n, P (n + 2) =
          C (a n) * P (n + 1) + (C (d n) * X - C (b n)) * P n) :
        (∀ n, StrictInterl (P n) (P (n + 1))) ∧ (∀ n, HasSimpleRoots (P n)) ∧
          (∀ n r, (P n).IsRoot r → r < 0) ∧
          (∀ n r, (P (n + 1)).IsRoot r → ¬ (P n).IsRoot r)

Lean source RealRooted/Challenges/Interlacing/RecurrenceRootWindows.lean at revision d6670742. Formalized 2026-10-01.