Interlacing of quadratics

Two quadratics with positive leading coefficients have alternating roots above a point $L$ exactly when four polynomial inequalities in their coefficients hold. The criterion involves no square roots, so it applies directly to quadratics whose coefficients depend on parameters.

Results

Theorem (criterion). Let $f=ax^2+bx+c$ and $g=Ax^2+Bx+d$ with $a,A>0$, and let $L\in\mathbb R$. Put $u=aB-Ab$ and $v=ad-Ac$, so that $ag-Af=ux+v$. There are roots $r_1,r_2$ of $f$ and $s_1,s_2$ of $g$ with $$ L<r_1<s_1<r_2<s_2 $$ if and only if $$ u<0,\qquad a v^2-b\,u\,v+c\,u^2<0,\qquad f(L)>0,\qquad f'(L)<0 . $$ The second inequality says $u^2f(-v/u)<0$, that is, the root $-v/u$ of the remainder lies strictly between the roots of $f$. Under these inequalities, $f\ll g$, both $f$ and $g$ have simple roots, they have no common root, and $f\ll(x-L)\,g$ with a degree gap of one.

Example (a one-parameter family). For $y\in[0,1/3]$ let $$ H_y(x)=x^2+\frac{6+11y-3y^2}{7}\,x+\frac{1+3y+3y^2}{7}. $$ Each $H_y$ has simple real roots, all in $[-1,0)$. For $y,z\in[0,1/3]$, $$ H_y\ll H_z\iff z\le y\iff H_y\ll(x+1)H_z . $$ For a sequence $y_n\in[0,1/3]$, the row $(x+1)^nH_{y_n}$ has degree $n+2$, positive coefficients, and all roots in $[-1,0)$. Consecutive rows satisfy $$ (x+1)^nH_{y_n}\ll(x+1)^{n+1}H_{y_{n+1}}\iff y_{n+1}\le y_n . $$

References

For interlacing in general, see [Fis06].

  1. [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}
    }

Definitions

  • The monic quadratic family H_y

    RealRooted.normalizedQuadraticFamilysource
    @[expose] def normalizedQuadraticFamily (y : ℝ) : ℝ[X] :=
      C 1 * X ^ 2 + C ((6 + 11 * y - 3 * y ^ 2) / 7) * X +
        C ((1 + 3 * y + 3 * y ^ 2) / 7)

Theorems

  • Alternating root order of two quadratics is equivalent to four sign conditionsMain resultRealRooted original

    RealRooted.exists_ordered_quadratic_roots_iff_remainder_signssource
    theorem exists_ordered_quadratic_roots_iff_remainder_signs
        {a b c A B d L : ℝ} (ha : 0 < a) (hA : 0 < A) :
        (∃ r₁ r₂ s₁ s₂ : ℝ,
          L < r₁ ∧ r₁ < s₁ ∧ s₁ < r₂ ∧ r₂ < s₂ ∧
          (C a * X ^ 2 + C b * X + C c : ℝ[X]).IsRoot r₁ ∧
          (C a * X ^ 2 + C b * X + C c : ℝ[X]).IsRoot r₂ ∧
          (C A * X ^ 2 + C B * X + C d : ℝ[X]).IsRoot s₁ ∧
          (C A * X ^ 2 + C B * X + C d : ℝ[X]).IsRoot s₂) ↔
        a * B - A * b < 0 ∧
          a * (a * d - A * c) ^ 2 - b * (a * B - A * b) * (a * d - A * c) +
            c * (a * B - A * b) ^ 2 < 0 ∧
          0 < (C a * X ^ 2 + C b * X + C c : ℝ[X]).eval L ∧
          (C a * X ^ 2 + C b * X + C c : ℝ[X]).derivative.eval L < 0
  • The sign conditions give interlacing, simple roots and no common rootsRealRooted original

    RealRooted.strictInterl_quadratics_of_remainder_signssource
    theorem strictInterl_quadratics_of_remainder_signs
        {a b c A B d L : ℝ} (ha : 0 < a) (hA : 0 < A)
        (hu : a * B - A * b < 0)
        (hN : a * (a * d - A * c) ^ 2 - b * (a * B - A * b) * (a * d - A * c) +
          c * (a * B - A * b) ^ 2 < 0)
        (hfL : 0 < (C a * X ^ 2 + C b * X + C c : ℝ[X]).eval L)
        (hfL' : (C a * X ^ 2 + C b * X + C c : ℝ[X]).derivative.eval L < 0) :
        StrictInterl (C a * X ^ 2 + C b * X + C c)
          (C A * X ^ 2 + C B * X + C d) ∧
          HasSimpleRoots (C a * X ^ 2 + C b * X + C c : ℝ[X]) ∧
          HasSimpleRoots (C A * X ^ 2 + C B * X + C d : ℝ[X]) ∧
          ∀ r, (C a * X ^ 2 + C b * X + C c : ℝ[X]).IsRoot r →
            ¬ (C A * X ^ 2 + C B * X + C d : ℝ[X]).IsRoot r
  • The sign conditions give differ-by-one interlacing with a linear multipleRealRooted original

    RealRooted.interlaces_quadratic_mul_X_sub_C_of_remainder_signssource
    theorem interlaces_quadratic_mul_X_sub_C_of_remainder_signs
        {a b c A B d L : ℝ} (ha : 0 < a) (hA : 0 < A)
        (hu : a * B - A * b < 0)
        (hN : a * (a * d - A * c) ^ 2 - b * (a * B - A * b) * (a * d - A * c) +
          c * (a * B - A * b) ^ 2 < 0)
        (hfL : 0 < (C a * X ^ 2 + C b * X + C c : ℝ[X]).eval L)
        (hfL' : (C a * X ^ 2 + C b * X + C c : ℝ[X]).derivative.eval L < 0) :
        Interlaces (C a * X ^ 2 + C b * X + C c)
          ((X - C L) * (C A * X ^ 2 + C B * X + C d))
  • H_y has simple real roots in [-1, 0) for 0 ≤ y ≤ 1/3RealRooted original

    RealRooted.normalizedQuadraticFamily_splits_simple_roots_mem_Icosource
    theorem normalizedQuadraticFamily_splits_simple_roots_mem_Ico
        {y : ℝ} (hy₀ : 0 ≤ y) (hy₁ : y ≤ 1 / 3) :
        (normalizedQuadraticFamily y).Splits ∧
          HasSimpleRoots (normalizedQuadraticFamily y) ∧
          ∀ r ∈ (normalizedQuadraticFamily y).roots, -1 ≤ r ∧ r < 0
  • H_y interlaces H_z exactly when z ≤ yRealRooted original

    RealRooted.normalizedQuadraticFamily_strictInterl_iffsource
    theorem normalizedQuadraticFamily_strictInterl_iff
        {y z : ℝ} (hy₀ : 0 ≤ y) (hy₁ : y ≤ 1 / 3) (hz₀ : 0 ≤ z) (hz₁ : z ≤ 1 / 3) :
        StrictInterl (normalizedQuadraticFamily y) (normalizedQuadraticFamily z) ↔ z ≤ y
  • H_y interlaces (X + 1) H_z exactly when z ≤ yRealRooted original

    RealRooted.normalizedQuadraticFamily_interlaces_mul_X_add_one_iffsource
    theorem normalizedQuadraticFamily_interlaces_mul_X_add_one_iff
        {y z : ℝ} (hy₀ : 0 ≤ y) (hy₁ : y ≤ 1 / 3) (hz₀ : 0 ≤ z) (hz₁ : z ≤ 1 / 3) :
        Interlaces (normalizedQuadraticFamily y)
          ((X + C 1) * normalizedQuadraticFamily z) ↔ z ≤ y
  • Consecutive rows (X + 1)^n H_{y_n} interlace exactly when y_{n+1} ≤ y_nRealRooted original

    RealRooted.normalizedQuadraticRows_interlaces_iffsource
    theorem normalizedQuadraticRows_interlaces_iff
        (y : ℕ → ℝ) (hy₀ : ∀ n, 0 ≤ y n) (hy₁ : ∀ n, y n ≤ 1 / 3) (n : ℕ) :
        Interlaces ((X + C 1) ^ n * normalizedQuadraticFamily (y n))
          ((X + C 1) ^ (n + 1) * normalizedQuadraticFamily (y (n + 1))) ↔
          y (n + 1) ≤ y n
  • Rows have degree n + 2, positive coefficients and roots in [-1, 0)RealRooted original

    RealRooted.normalizedQuadraticRow_degree_coeff_rootssource
    theorem normalizedQuadraticRow_degree_coeff_roots
        {y : ℝ} (hy₀ : 0 ≤ y) (hy₁ : y ≤ 1 / 3) (n : ℕ) :
        ((X + C 1) ^ n * normalizedQuadraticFamily y).natDegree = n + 2 ∧
          (∀ k ≤ n + 2, 0 < ((X + C 1) ^ n * normalizedQuadraticFamily y).coeff k) ∧
          ∀ r ∈ ((X + C 1) ^ n * normalizedQuadraticFamily y).roots, -1 ≤ r ∧ r < 0

Lean source RealRooted/Challenges/Interlacing/QuadraticInterlacingCriterion.lean at revision d6670742. Formalized 2026-11-01.