Ordered PF states for cubic and quartic recurrences

A recurrence of order three or four has Pólya frequency rows with consecutive interlacing when it is the action of a matrix that preserves ordered triples of Pólya frequency polynomials. This extends the interlacing theory of three-term recurrences to higher order, with sharp parameter ranges.

Results

A polynomial is PF if it is zero or has nonnegative coefficients and only real, nonpositive roots. Here the zero polynomial interlaces and is interlaced by every polynomial. A triple $(q,p,r)$ is an ordered PF triple if $q,p,r$ are PF and $q\ll p$, $q\ll r$, $p\ll r$.

Theorem (matrix criterion). Let $\lambda>0$ and let $a,b,c,d$ be real. The map $$ (p,u,r)\ \longmapsto\ \bigl(r,\ r+\lambda x\,p,\ c\,x\,p+d\,x\,u+(a+bx)\,r\bigr), $$ given by the matrix $\begin{pmatrix}0&0&1\\\lambda x&0&1\\cx&dx&a+bx\end{pmatrix}$, sends every ordered PF triple to an ordered PF triple if and only if $a,b,d\ge0$ and $c\ge a\lambda$.

Corollary (third-order recurrences). Let $a_s,b_s,d_s\ge0$ and $e_s$ be real, and let $P_{-1}=P_0=0$, $P_1=1$ and $$ P_{s+2}=(a_s+b_sx)P_{s+1}+e_s\,x\,P_s+d_s\,x^2P_{s-1}. $$ Suppose that $a_s\kappa^2-e_s\kappa+d_s\le0$ for all $s$, for a fixed $\kappa>0$; for $\kappa=1$ this reads $e_s\ge a_s+d_s$. Then $(P_s,\ P_s+\kappa xP_{s-1},\ P_{s+1})$ is an ordered PF triple for every $s$. In particular every $P_s$ is PF and $P_s\ll P_{s+1}$.

Theorem (cubic transition). For real $\alpha,\gamma,w$, the map $(q,p,r)\mapsto(\alpha q+p,\ r,\ \gamma r+w\,x\,q)$ sends every ordered PF triple to an ordered PF triple if and only if $\alpha,\gamma,w\ge0$. Let $P_0=1$ and let $P_{n+1}$ be the middle coordinate after $n$ steps, started from $(1,\gamma,\gamma^2)$. Then $$ P_{n+3}=(\alpha+\gamma)P_{n+2}-\alpha\gamma P_{n+1}+w\,x\,P_n , $$ with $P_1=\gamma$, $P_2=\gamma^2$, constant term $\gamma^n$ in $P_n$, and $P_n=\gamma^n$ if $w=0$. If $\alpha,\gamma,w\ge0$, every $P_n$ is PF and $P_n\ll P_{n+1}$, $P_n\ll P_{n+2}$, $P_n\ll P_{n+3}$. If $\gamma>0$, all roots are negative. If $\gamma,w>0$, then $\deg P_n=\lfloor n/3\rfloor$, and $P_{3n+j}$ interlaces $P_{3(n+1)+j}$ with a degree gap of one for $j=0,1,2$.

Theorem (quartic transition). For real $u,v,w$, consider states $S=(f_0,f_1,f_2,d,s)$ of five polynomials and the transition $$ \begin{aligned} f_0&\mapsto f_1, & f_1&\mapsto f_2,\\ f_2&\mapsto f_2+u\,s+(u+v-w)\,x\,f_1+w\,x\,f_0, & &\\ d&\mapsto d+s+x f_1, & s&\mapsto s+x f_1 . \end{aligned} $$ Call $S$ admissible if all five coordinates are nonzero PF polynomials, $$ f_0\ll f_1,\quad f_0\ll f_2,\quad f_1\ll f_2,\quad f_1\ll d,\quad f_1\ll s,\quad f_2\ll s,\quad d\ll s, $$ and $f_2=u\,d+v\,s-w\,x\,f_0$. If $0\le w\le v\le u$ and $u>0$, the transition maps admissible states to admissible states. Hence, for an admissible initial state, the rows $R_n=f_0^{(n)}$ of the iterated state are nonzero PF polynomials and $R_n\ll R_{n+1}$. For every initial state, $$ R_{n+4}=2R_{n+3}+\bigl((u+v-w)x-1\bigr)R_{n+2}+(2w-v)\,x\,R_{n+1}-w\,x\,R_n . $$

Finally, if $H_{n+3}=pH_{n+2}-qH_{n+1}+uH_n$ in a commutative ring, then every residue class modulo three satisfies $$ H_{3(n+3)+j}=(p^3-3pq+3u)H_{3(n+2)+j}-(q^3-3pqu+3u^2)H_{3(n+1)+j}+u^3H_{3n+j}, $$ whose coefficients are the elementary symmetric functions of the cubes of the characteristic roots. With $p=\alpha+\gamma$, $q=\alpha\gamma$ and $u=wx$, this is the recurrence of the residue classes of the cubic family.

Use

To show that a recurrence has PF rows with consecutive interlacing, it suffices to realize it as a transition on a short state of polynomials that preserves a class of ordered PF tuples, with the sequence as one coordinate of the state.

Proof

Sufficiency follows from the cone lemmas of Wagner: if $h\ll f_i$ for all $i$, then $h\ll\sum_ic_if_i$ for $c_i\ge0$; if $f_i\ll h$ for all $i$, then $\sum_ic_if_i\ll h$; and $f\ll g$ implies $g\ll xf$. Necessity follows by applying the map to the triples $(1,0,0)$, $(0,1,0)$, $(0,0,1)$ and $(K,0,1)$ for large $K$. For the subsequence recurrence, the cubic characteristic polynomial $z^3-pz^2+qz-u$ divides $z^9-(p^3-3pq+3u)z^6+(q^3-3pqu+3u^2)z^3-u^3$.

References

[Wag92]

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

Definitions

  • Ordered PF triple

    RealRooted.IsOrderedPFTriplesource
    @[expose] def IsOrderedPFTriple (q p r : ℝ[X]) : Prop :=
      IsPFPolynomial q ∧ IsPFPolynomial p ∧ IsPFPolynomial r ∧
        Interl q p ∧ Interl q r ∧ Interl p r
  • The cubic transition preserves ordered PF triples

    RealRooted.PreservesCubicTransitionsource
    @[expose] def PreservesCubicTransition (α γ w : ℝ) : Prop :=
      ∀ q p r : ℝ[X], IsOrderedPFTriple q p r →
        IsOrderedPFTriple (C α * q + p) r (C γ * r + C w * (X * q))
  • The matrix [[0,0,1],[x,0,1],[cx,dx,a+bx]] preserves ordered PF triples

    RealRooted.PreservesPFTriplesource
    @[expose] def PreservesPFTriple (a b c d : ℝ) : Prop :=
      ∀ p u r : ℝ[X], IsOrderedPFTriple p u r →
        IsOrderedPFTriple r (r + X * p) (C c * (X * p) + C d * (X * u) + (C a + C b * X) * r)
  • The scaled matrix [[0,0,1],[lx,0,1],[cx,dx,a+bx]] preserves ordered PF triples

    RealRooted.PreservesScaledPFTriplesource
    @[expose] def PreservesScaledPFTriple (l a b c d : ℝ) : Prop :=
      ∀ p u r : ℝ[X], IsOrderedPFTriple p u r →
        IsOrderedPFTriple r (r + C l * (X * p))
          (C c * (X * p) + C d * (X * u) + (C a + C b * X) * r)
  • The row family of the cubic transition

    RealRooted.cubicTransitionFamilysource
    def cubicTransitionFamily (α γ w : ℝ) : ℕ → ℝ[X]
      | 0 => 1
      | n + 1 => (cubicTransitionIterate α γ w n).p
  • One step of the five-coordinate quartic state

    RealRooted.quarticInterlacingStepsource
    def quarticInterlacingStep (u v w : ℝ)
        (S : QuarticInterlacingState) : QuarticInterlacingState where
      f0 := S.f1
      f1 := S.f2
      f2 := S.f2 + C u * S.s + C (u + v - w) * (X * S.f1) + C w * (X * S.f0)
      d := S.d + (S.s + X * S.f1)
      s := S.s + X * S.f1
  • Admissible quartic state: PF coordinates, seven comparisons and a balance identity

    RealRooted.QuarticInterlacingState.IsAdmissiblesource
    structure QuarticInterlacingState.IsAdmissible (u v w : ℝ)
        (S : QuarticInterlacingState) : Prop where
      /-- The oldest row is PF. -/
      f0_pf : IsPFPolynomial S.f0
      /-- The oldest row is nonzero. -/
      f0_ne : S.f0 ≠ 0
      /-- The middle row is PF. -/
      f1_pf : IsPFPolynomial S.f1
      /-- The middle row is nonzero. -/
      f1_ne : S.f1 ≠ 0
      /-- The newest row is PF. -/
      f2_pf : IsPFPolynomial S.f2
      /-- The newest row is nonzero. -/
      f2_ne : S.f2 ≠ 0
      /-- The first auxiliary coordinate is PF. -/
      d_pf : IsPFPolynomial S.d
      /-- The first auxiliary coordinate is nonzero. -/
      d_ne : S.d ≠ 0
      /-- The cumulative auxiliary coordinate is PF. -/
      s_pf : IsPFPolynomial S.s
      /-- The cumulative auxiliary coordinate is nonzero. -/
      s_ne : S.s ≠ 0
      /-- The oldest row precedes the middle row. -/
      f0_interl_f1 : Interl S.f0 S.f1
      /-- The oldest row precedes the newest row. -/
      f0_interl_f2 : Interl S.f0 S.f2
      /-- The middle row precedes the newest row. -/
      f1_interl_f2 : Interl S.f1 S.f2
      /-- The middle row precedes the first auxiliary coordinate. -/
      f1_interl_d : Interl S.f1 S.d
      /-- The middle row precedes the cumulative auxiliary coordinate. -/
      f1_interl_s : Interl S.f1 S.s
      /-- The newest row precedes the cumulative auxiliary coordinate. -/
      f2_interl_s : Interl S.f2 S.s
      /-- The first auxiliary coordinate precedes the cumulative one. -/
      d_interl_s : Interl S.d S.s
      /-- The newest row is the balanced combination of the auxiliary coordinates. -/
      balance : S.f2 = C u * S.d + C v * S.s - C w * (X * S.f0)
  • The row sequence of an iterated quartic state

    RealRooted.quarticInterlacingRowsource
    def quarticInterlacingRow (u v w : ℝ) (S : QuarticInterlacingState)
        (n : ℕ) : ℝ[X] :=
      (quarticInterlacingIterate u v w S n).row

Theorems

  • The cubic transition preserves ordered PF triples iff its three parameters are nonnegativeRealRooted original

    RealRooted.PreservesCubicTransition.iff_nonnegsource
    theorem PreservesCubicTransition.iff_nonneg (α γ w : ℝ) :
        PreservesCubicTransition α γ w ↔ 0 ≤ α ∧ 0 ≤ γ ∧ 0 ≤ w
  • Consecutive rows of the cubic family interlaceRealRooted original

    RealRooted.cubicTransitionFamily_interl_add_onesource
    theorem cubicTransitionFamily_interl_add_one {α γ w : ℝ}
        (hα : 0 ≤ α) (hγ : 0 ≤ γ) (hw : 0 ≤ w) (n : ℕ) :
        Interl (cubicTransitionFamily α γ w n)
          (cubicTransitionFamily α γ w (n + 1))
  • Consecutive rows of an admissible quartic state interlaceRealRooted original

    RealRooted.interl_quarticInterlacingRow_succsource
    theorem interl_quarticInterlacingRow_succ
        {u v w : ℝ} {S : QuarticInterlacingState}
        (hS : S.IsAdmissible u v w) (hu : 0 < u)
        (hw : 0 ≤ w) (hwv : w ≤ v) (hvu : v ≤ u) (n : ℕ) :
        Interl (quarticInterlacingRow u v w S n)
          (quarticInterlacingRow u v w S (n + 1))
  • The three-coordinate matrix preserves ordered PF triples iff a, b, d ≥ 0 and c ≥ aRealRooted original

    RealRooted.PreservesPFTriple.iffsource
    theorem PreservesPFTriple.iff (a b c d : ℝ) :
        PreservesPFTriple a b c d ↔ 0 ≤ a ∧ 0 ≤ b ∧ 0 ≤ d ∧ a ≤ c
  • The scaled matrix preserves ordered PF triples iff a, b, d ≥ 0 and c ≥ a lMain resultRealRooted original

    RealRooted.PreservesScaledPFTriple.iffsource
    theorem PreservesScaledPFTriple.iff {l : ℝ} (hl : 0 < l) (a b c d : ℝ) :
        PreservesScaledPFTriple l a b c d ↔ 0 ≤ a ∧ 0 ≤ b ∧ 0 ≤ d ∧ a * l ≤ c
  • Third-order recurrences with a, b, d ≥ 0 and e ≥ a + d have PF rows and ordered statesRealRooted original

    RealRooted.isOrderedPFTriple_of_recurrencesource
    theorem isOrderedPFTriple_of_recurrence
        (ha : ∀ s, 0 ≤ a s) (hb : ∀ s, 0 ≤ b s) (hd : ∀ s, 0 ≤ d s)
        (he : ∀ s, a s + d s ≤ e s)
        (hrec : ∀ s, P (s + 2) = (C (a s) + C (b s) * X) * P (s + 1) + C (e s) * X * P s +
          C (d s) * X ^ 2 * P (s - 1))
        (h0 : P 0 = 0) (h1 : P 1 = 1) (s : ℕ) :
        IsOrderedPFTriple (P s) (P s + X * P (s - 1)) (P (s + 1))
  • Consecutive rows of such a third-order recurrence interlaceRealRooted original

    RealRooted.interl_of_recurrencesource
    theorem interl_of_recurrence
        (ha : ∀ s, 0 ≤ a s) (hb : ∀ s, 0 ≤ b s) (hd : ∀ s, 0 ≤ d s)
        (he : ∀ s, a s + d s ≤ e s)
        (hrec : ∀ s, P (s + 2) = (C (a s) + C (b s) * X) * P (s + 1) + C (e s) * X * P s +
          C (d s) * X ^ 2 * P (s - 1))
        (h0 : P 0 = 0) (h1 : P 1 = 1) (s : ℕ) : Interl (P s) (P (s + 1))
  • The scaled state: a κ² − e κ + d ≤ 0 for some κ > 0 sufficesRealRooted original

    RealRooted.isOrderedPFTriple_of_recurrence_scaledsource
    theorem isOrderedPFTriple_of_recurrence_scaled {κ : ℝ} (hκ : 0 < κ)
        (ha : ∀ s, 0 ≤ a s) (hb : ∀ s, 0 ≤ b s) (hd : ∀ s, 0 ≤ d s)
        (hq : ∀ s, a s * κ ^ 2 - e s * κ + d s ≤ 0)
        (hrec : ∀ s, P (s + 2) = (C (a s) + C (b s) * X) * P (s + 1) + C (e s) * X * P s +
          C (d s) * X ^ 2 * P (s - 1))
        (h0 : P 0 = 0) (h1 : P 1 = 1) (s : ℕ) :
        IsOrderedPFTriple (P s) (P s + C κ * (X * P (s - 1))) (P (s + 1))
  • Nonnegative parameters make the cubic transition preserve ordered PF triplesRealRooted original

    RealRooted.PreservesCubicTransition.of_nonnegsource
    theorem PreservesCubicTransition.of_nonneg {α γ w : ℝ}
        (hα : 0 ≤ α) (hγ : 0 ≤ γ) (hw : 0 ≤ w) :
        PreservesCubicTransition α γ w
  • The cubic family satisfies a constant-coefficient cubic recurrenceRealRooted original

    RealRooted.cubicTransitionFamily_recurrencesource
    theorem cubicTransitionFamily_recurrence (α γ w : ℝ) (n : ℕ) :
        cubicTransitionFamily α γ w (n + 3) =
          C (α + γ) * cubicTransitionFamily α γ w (n + 2) -
          C (α * γ) * cubicTransitionFamily α γ w (n + 1) +
          C w * X * cubicTransitionFamily α γ w n
  • Every row of the cubic family is PFRealRooted original

    RealRooted.cubicTransitionFamily_isPFPolynomialsource
    theorem cubicTransitionFamily_isPFPolynomial {α γ w : ℝ}
        (hα : 0 ≤ α) (hγ : 0 ≤ γ) (hw : 0 ≤ w) (n : ℕ) :
        IsPFPolynomial (cubicTransitionFamily α γ w n)
  • Rows of the cubic family at distance two interlaceRealRooted original

    RealRooted.cubicTransitionFamily_interl_add_twosource
    theorem cubicTransitionFamily_interl_add_two {α γ w : ℝ}
        (hα : 0 ≤ α) (hγ : 0 ≤ γ) (hw : 0 ≤ w) (n : ℕ) :
        Interl (cubicTransitionFamily α γ w n)
          (cubicTransitionFamily α γ w (n + 2))
  • Rows of the cubic family at distance three interlaceRealRooted original

    RealRooted.cubicTransitionFamily_interl_add_threesource
    theorem cubicTransitionFamily_interl_add_three {α γ w : ℝ}
        (hα : 0 ≤ α) (hγ : 0 ≤ γ) (hw : 0 ≤ w) (n : ℕ) :
        Interl (cubicTransitionFamily α γ w n)
          (cubicTransitionFamily α γ w (n + 3))
  • For γ, w > 0 the nth row of the cubic family has degree ⌊n/3⌋RealRooted original

    RealRooted.cubicTransitionFamily_natDegreesource
    theorem cubicTransitionFamily_natDegree {α γ w : ℝ}
        (hα : 0 ≤ α) (hγ : 0 < γ) (hw : 0 < w) (n : ℕ) :
        (cubicTransitionFamily α γ w n).natDegree = n / 3
  • For γ > 0 all roots of the cubic family are negativeRealRooted original

    RealRooted.cubicTransitionFamily_roots_negsource
    theorem cubicTransitionFamily_roots_neg {α γ w : ℝ}
        (hα : 0 ≤ α) (hγ : 0 < γ) (hw : 0 ≤ w) (n : ℕ) :
        ∀ x ∈ (cubicTransitionFamily α γ w n).roots, x < 0
  • For γ, w > 0 consecutive rows in each residue class modulo three interlaceRealRooted original

    RealRooted.cubicTransitionFamily_residue_interlacessource
    theorem cubicTransitionFamily_residue_interlaces {α γ w : ℝ}
        (hα : 0 ≤ α) (hγ : 0 < γ) (hw : 0 < w) {j : ℕ} (hj : j < 3) (n : ℕ) :
        Interlaces (cubicTransitionFamily α γ w (3 * n + j))
          (cubicTransitionFamily α γ w (3 * (n + 1) + j))
  • Residue-class subsequences satisfy the cubic recurrence with cubed rootsRealRooted original

    RealRooted.cubicTransitionFamily_residue_recurrencesource
    theorem cubicTransitionFamily_residue_recurrence (α γ w : ℝ) (j n : ℕ) :
        let p : ℝ[X]
  • Every-third subsequence of a cubic recurrence: the cubed-roots recurrenceRealRooted original

    RealRooted.cubicRecurrence_residue_threesource
    theorem cubicRecurrence_residue_three {R : Type*} [CommRing R]
        (p q u : R) (H : ℕ → R)
        (hrec : ∀ n, H (n + 3) = p * H (n + 2) - q * H (n + 1) + u * H n)
        (j n : ℕ) :
        H (3 * (n + 3) + j) =
          (p ^ 3 - 3 * p * q + 3 * u) * H (3 * (n + 2) + j) -
          (q ^ 3 - 3 * p * q * u + 3 * u ^ 2) * H (3 * (n + 1) + j) +
          u ^ 3 * H (3 * n + j)
  • Factor certificate for the characteristic polynomial of every-third subsequencesRealRooted original

    RealRooted.cubicCharacteristic_mul_certificatesource
    theorem cubicCharacteristic_mul_certificate {R : Type*} [CommRing R]
        (p q u z : R) :
        (z ^ 3 - p * z ^ 2 + q * z - u) *
            (z ^ 6 + p * z ^ 5 + (p ^ 2 - q) * z ^ 4 + (p * q - 2 * u) * z ^ 3 +
              (q ^ 2 - p * u) * z ^ 2 + q * u * z + u ^ 2) =
          z ^ 9 - (p ^ 3 - 3 * p * q + 3 * u) * z ^ 6 +
            (q ^ 3 - 3 * p * q * u + 3 * u ^ 2) * z ^ 3 - u ^ 3
  • The quartic transition preserves admissibility when 0 ≤ w ≤ v ≤ u and u > 0RealRooted original

    RealRooted.QuarticInterlacingState.IsAdmissible.stepsource
    theorem QuarticInterlacingState.IsAdmissible.step
        {u v w : ℝ} {S : QuarticInterlacingState}
        (hS : S.IsAdmissible u v w) (hu : 0 < u)
        (hw : 0 ≤ w) (hwv : w ≤ v) (hvu : v ≤ u) :
        (quarticInterlacingStep u v w S).IsAdmissible u v w
  • Every row of an admissible quartic state is PFRealRooted original

    RealRooted.quarticInterlacingRow_isPFPolynomialsource
    theorem quarticInterlacingRow_isPFPolynomial
        {u v w : ℝ} {S : QuarticInterlacingState}
        (hS : S.IsAdmissible u v w) (hu : 0 < u)
        (hw : 0 ≤ w) (hwv : w ≤ v) (hvu : v ≤ u) (n : ℕ) :
        IsPFPolynomial (quarticInterlacingRow u v w S n)
  • The rows of a quartic state satisfy a fourth-order recurrenceRealRooted original

    RealRooted.quarticInterlacingRow_add_foursource
    theorem quarticInterlacingRow_add_four
        (u v w : ℝ) (S : QuarticInterlacingState) (n : ℕ) :
        quarticInterlacingRow u v w S (n + 4) =
          C 2 * quarticInterlacingRow u v w S (n + 3) +
            (C (u + v - w) * X - 1) * quarticInterlacingRow u v w S (n + 2) +
            (C (2 * w - v) * X) * quarticInterlacingRow u v w S (n + 1) -
            (C w * X) * quarticInterlacingRow u v w S n

Lean source RealRooted/Challenges/Interlacing/HigherOrderRecurrenceStates.lean at revision d6670742. Formalized 2026-11-03.