Rows of P_{n+1} = A_n P_n′ + B_n P_n interlace if their roots stay in a windowMain result
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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))
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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)
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
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
theorem strictInterl_binomialDerivativeRow_succ (r n : ℕ) :
StrictInterl (binomialDerivativeRow r n) (binomialDerivativeRow r (n + 1))
Binomial derivative rows have roots in [-1, 0]
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
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
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
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
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)