Recurrences with separated characteristic parameters

If a constant-coefficient recurrence has characteristic polynomial $\prod_i(T-a_i)-x\prod_j(T-b_j)$ with $a_i\ge0\ge b_j$, then its solutions from suitable initial rows are Pólya frequency polynomials and consecutive terms interlace. The criterion can be read off from the recurrence alone.

Results

Let $h\ge1$, $m\ge0$, $a\in\mathbb R^{h+m}$, $b\in\mathbb R^m$, and let $S$ be the shift $(SP)_n=P_{n+1}$. Consider the recurrence $$ \prod_{i=1}^{h+m}(S-a_i)\,P\;=\;x\prod_{j=1}^{m}(S-b_j)\,P. $$ Let $M=M(a,b)$ be the $(h+m)\times(h+m)$ matrix over $\mathbb R[x]$ whose first $h-1$ rows are bidiagonal (diagonal entry $a_i$, entry $1$ above it), and whose remaining rows have $x$ in column $0$, diagonal entry $a_i$, and entry $a_j-b_{j-h}$ in each column $j>i$, with $b_{j-h}$ read as $0$ for $j<h$. Then $$ \det(T-M)=\prod_i(T-a_i)-x\prod_j(T-b_j), $$ so every coordinate of $M^nv$ solves the recurrence. Conversely, if $(P_{s+n})_{n\ge0}$ solves it and $P_{s+r}=(M^rv)_i$ for $0\le r<h+m$, then $P_{s+n}=(M^nv)_i$ for all $n\ge0$.

Theorem. Assume $a_i\ge0\ge b_j$ for all $i,j$, or $a_i\ge\rho\ge b_j$ with $M$ built from $a_i-\rho$ and $b_j-\rho$. Then $M$ maps interlacing sequences of nonnegative real-rooted polynomials, zero entries allowed, to such sequences. If the seed $v$ is such a sequence, then every coordinate of every $M^nv$ is a Pólya frequency polynomial or zero, and $$ (M^nv)_i\ll(M^{n+1}v)_i\qquad\text{for all }n\ge0\text{ and all }i. $$

Proof

The determinant formula and the Cayley–Hamilton theorem give the recurrence. Under the sign conditions, $M$ has nonnegative polynomial coefficients and satisfies Brändén's criterion on the matrix interlacing page.

References

The preservation criterion is [Bra15, Thm. 7.8.5]; see the matrix interlacing page.

  1. [Bra15, Thm. 7.8.5] Petter Brändén. Unimodality, Log-Concavity, Real-Rootedness and Beyond. Handbook of enumerative combinatorics, 437-483, 2015.
    BibTeX
    @incollection{Branden2015,
      doi = {10.1201/b18255-10},
      year = {2015},
      month = mar,
      publisher = {Chapman and Hall/{CRC}},
      pages = {437--483},
      author = {Petter Br{\"{a}}nd{\'{e}}n},
      title = {Unimodality, Log-Concavity, Real-Rootedness and Beyond},
      booktitle = {Handbook of Enumerative Combinatorics}
    }

Definitions

  • The companion-type polynomial matrix of a separated-characteristic recurrence

    RealRooted.separatedCharacteristicFinMatrixsource
    def separatedCharacteristicFinMatrix {h m : ℕ}
        (a : Fin (h + m) → ℝ) (b : Fin m → ℝ) :
        Matrix (Fin (h + m)) (Fin (h + m)) ℝ[X] := fun i j ↦
      if _hi : (i : ℕ) + 1 < h then
        (if j = i then C (a i) else 0) +
          if (j : ℕ) = i + 1 then 1 else 0
      else
        (if (j : ℕ) = 0 then X else 0) +
          (if j = i then C (a i) else 0) +
            if i < j then C (a j - separatedCharacteristicTailCoeff b j) else 0
  • Iterated rows of the matrix from a seed vector

    RealRooted.separatedCharacteristicRowssource
    def separatedCharacteristicRows {h m : ℕ}
        (a : Fin (h + m) → ℝ) (b : Fin m → ℝ)
        (seed : Fin (h + m) → ℝ[X]) : ℕ → Fin (h + m) → ℝ[X]
      | 0 => seed
      | n + 1 => (separatedCharacteristicFinMatrix a b).mulVec
          (separatedCharacteristicRows a b seed n)

Theorems

  • The matrix preserves interlacing sequences when a_i ≥ 0 and b_j ≤ 0RealRooted original

    RealRooted.PreservesInterlacingSeq0.separatedCharacteristicMatrixsource
    theorem PreservesInterlacingSeq0.separatedCharacteristicMatrix {h m : ℕ}
        {a : Fin (h + m) → ℝ} {b : Fin m → ℝ}
        (ha : ∀ i, 0 ≤ a i) (hb : ∀ j, b j ≤ 0) :
        PreservesInterlacingSeq0 (h + m) (RealRooted.separatedCharacteristicMatrix a b)
  • The shifted form: a_i ≥ ρ and b_j ≤ ρRealRooted original

    RealRooted.PreservesInterlacingSeq0.separatedCharacteristicMatrix_shiftsource
    theorem PreservesInterlacingSeq0.separatedCharacteristicMatrix_shift
        {h m : ℕ} {a : Fin (h + m) → ℝ} {b : Fin m → ℝ} {ρ : ℝ}
        (ha : ∀ i, ρ ≤ a i) (hb : ∀ j, b j ≤ ρ) :
        PreservesInterlacingSeq0 (h + m)
          (RealRooted.separatedCharacteristicMatrix (fun i ↦ a i - ρ) (fun j ↦ b j - ρ))
  • Every coordinate of every iterate of an ordered PF seed is a PF polynomialRealRooted original

    RealRooted.separatedCharacteristicRows_isPFPolynomialsource
    theorem separatedCharacteristicRows_isPFPolynomial {h m : ℕ}
        {a : Fin (h + m) → ℝ} {b : Fin m → ℝ}
        (ha : ∀ i, 0 ≤ a i) (hb : ∀ j, b j ≤ 0)
        {seed : Fin (h + m) → ℝ[X]}
        (hseed : IsInterlacingSeq0NonnegRealRooted (List.ofFn seed))
        (n : ℕ) (i : Fin (h + m)) :
        IsPFPolynomial (separatedCharacteristicRows a b seed n i)
  • Each coordinate interlaces the same coordinate after one stepMain resultRealRooted original

    RealRooted.separatedCharacteristicRows_interl_succsource
    theorem separatedCharacteristicRows_interl_succ {h m : ℕ}
        {a : Fin (h + m) → ℝ} {b : Fin m → ℝ}
        (ha : ∀ i, 0 ≤ a i) (hb : ∀ j, b j ≤ 0)
        {seed : Fin (h + m) → ℝ[X]}
        (hseed : IsInterlacingSeq0NonnegRealRooted (List.ofFn seed))
        (n : ℕ) (i : Fin (h + m)) :
        Interl (separatedCharacteristicRows a b seed n i)
          (separatedCharacteristicRows a b seed (n + 1) i)
  • Iterates of an interlacing seed remain interlacing sequencesRealRooted original

    RealRooted.separatedCharacteristicRows_interlacingsource
    theorem separatedCharacteristicRows_interlacing {h m : ℕ}
        {a : Fin (h + m) → ℝ} {b : Fin m → ℝ}
        (ha : ∀ i, 0 ≤ a i) (hb : ∀ j, b j ≤ 0)
        {seed : Fin (h + m) → ℝ[X]}
        (hseed : IsInterlacingSeq0NonnegRealRooted (List.ofFn seed)) (n : ℕ) :
        IsInterlacingSeq0NonnegRealRooted
          (List.ofFn (separatedCharacteristicRows a b seed n))
  • The characteristic polynomial is ∏(T - a_i) - X ∏(T - b_j)RealRooted original

    RealRooted.separatedCharacteristicFinMatrix_charpolysource
    theorem separatedCharacteristicFinMatrix_charpoly {h m : ℕ} (hh : 0 < h)
        (a : Fin (h + m) → ℝ) (b : Fin m → ℝ) :
        (separatedCharacteristicFinMatrix a b).charpoly =
          ∏ i, (X - C (C (a i))) -
            C (X : ℝ[X]) * ∏ j, (X - C (C (b j)))
  • A scalar solution with matching initial rows is a coordinate of the matrix orbitRealRooted original

    RealRooted.eq_separatedCharacteristicRows_coordinate_fromsource
    theorem eq_separatedCharacteristicRows_coordinate_from {h m : ℕ}
        (a : Fin (h + m) → ℝ) (b : Fin m → ℝ)
        (seed : Fin (h + m) → ℝ[X]) (i : Fin (h + m))
        (P : ℕ → ℝ[X]) (start : ℕ)
        (hP : (LinearRecurrence.ofMatrix
          (separatedCharacteristicFinMatrix a b)).IsSolution
            (fun n ↦ P (start + n)))
        (hinitial : ∀ r < h + m,
          P (start + r) = separatedCharacteristicRows a b seed r i) :
        ∀ n, P (start + n) = separatedCharacteristicRows a b seed n i

Lean source RealRooted/Challenges/Matrices/SeparatedCharacteristicRecurrence.lean at revision d6670742. Formalized 2026-11-01.