Weighted three-state recurrence

Brändén's matrix criterion decides exactly when a $3\times3$ transfer matrix with two linear entries preserves interlacing sequences. Its middle coordinate then gives a family of third-order recurrences whose rows have nonnegative coefficients, only negative real roots, and interlace.

Results

Let $$ M=\begin{pmatrix}1&b&d\\0&1&1\\x&\alpha x&1\end{pmatrix} $$ act on triples by $(R,P,D)\mapsto(R+bP+dD,\;P+D,\;xR+\alpha xP+D)$.

Theorem (preservation). The matrix $M$ maps an interlacing sequence of nonnegative real-rooted polynomials (zero terms allowed) to another one if and only if $$ 0\le b,\qquad 0\le\alpha,\qquad 0\le d,\qquad d\le b,\qquad\alpha\le b. $$

Theorem (rows). Iterate from the seed $(d-\eta,1,0)$ with $\eta\le d$ and keep the middle coordinate. This gives rows $P_n$ with $P_0=P_1=1$, $P_2=1+(\alpha+d-\eta)x$ and $$ P_{n+3}=3P_{n+2}+\bigl((\alpha+d)x-3\bigr)P_{n+1}+\bigl(1+(b-\alpha-d)x\bigr)P_n . $$ Rescale to parameters $(a,b,c,\eta)$ with $c>0$, whose rows begin $1$, $c$, $c^2+(a-\eta)x$. If $a,b\ge0$, $c>0$, $ac/2\le b$ and $\eta\le\min(a,b/c)$, then every row has nonnegative coefficients, constant term $c^n$, and only real negative roots, and consecutive rows interlace.

For $a,c\ne0$ the rows equal $c^n\,Q_n(ax/c^2)$, where the normalized rows $Q_n$ with parameters $(\rho,e)=(b/(ac),\eta/a)$ satisfy $Q_0=Q_1=1$, $Q_2=1+(1-e)x$ and $$ Q_{n+3}=3Q_{n+2}+(x-3)Q_{n+1}+\bigl(1+(\rho-1)x\bigr)Q_n . $$ For $e\le\tfrac12$ and $\rho\ge0$, the rows $Q_n$ have nonnegative coefficients, positive coefficients up to degree $\lfloor n/2\rfloor$, degree exactly $\lfloor n/2\rfloor$, and only negative roots.

Proof

Preservation is Brändén's criterion [Bra15, Thm. 7.8.5] applied to the $2\times2$ submatrices of $M$. For the normalized rows, let $\rho,s>0$ and let $r\in(0,\rho)$ be the unique solution of $r^3=s(\rho-r)$; then $Q_n(-s)$ is an explicit combination of $n$-th powers of $1-r$ and $1+r/2\pm iv$ with $v^2=s+3r^2/4$, and for $e\le\tfrac12$ the complex pair dominates in amplitude. The resulting sign changes of $Q_n$ at $\lfloor n/2\rfloor+1$ points give $\lfloor n/2\rfloor$ simple negative roots.

References

[Bra15, Thm. 7.8.5].

  1. [Bra15] 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 three-state matrix [[1, b, d], [0, 1, 1], [X, αX, 1]]

    RealRooted.weightedThreeStateMatrixsource
    def weightedThreeStateMatrix (b alpha d : ℝ) : List (List ℝ[X]) :=
      [[1, C b, C d], [0, 1, 1], [X, C alpha * X, 1]]
  • The row polynomials of the weighted three-state recurrence

    RealRooted.weightedThreeStateRowsource
    def weightedThreeStateRow (a b c eta : ℝ) (n : ℕ) : ℝ[X] :=
      let A := a / c ^ 2
      let B := b / c ^ 3
      let E := eta / c ^ 2
      let d := min A B
      C (c ^ n) * (weightedThreeState B (A - d) d E n).P
  • The normalized rows Q_n with parameters (ρ, e)

    RealRooted.weightedStripRowsource
    def weightedStripRow (rho e : ℝ) (n : ℕ) : ℝ[X] :=
      (weightedThreeState rho 0 1 e n).P

Theorems

  • The three-state matrix preserves interlacing sequences exactly in an explicit regionMain resultRealRooted original

    RealRooted.PreservesInterlacingSeq0.weightedThreeStateMatrix_iffsource
    theorem PreservesInterlacingSeq0.weightedThreeStateMatrix_iff (b alpha d : ℝ) :
        PreservesInterlacingSeq0 3 (weightedThreeStateMatrix b alpha d) ↔
          0 ≤ b ∧ 0 ≤ alpha ∧ 0 ≤ d ∧ d ≤ b ∧ alpha ≤ b
  • Consecutive rows interlaceRealRooted original

    RealRooted.weightedThreeStateRow_interl_succsource
    theorem weightedThreeStateRow_interl_succ
        {a b c eta : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b) (hc : 0 < c)
        (hbac : a * c / 2 ≤ b) (heta : eta ≤ min a (b / c)) (n : ℕ) :
        Interl (weightedThreeStateRow a b c eta n)
          (weightedThreeStateRow a b c eta (n + 1))
  • Every row is real-rootedRealRooted original

    RealRooted.weightedThreeStateRow_isRealRootedsource
    theorem weightedThreeStateRow_isRealRooted
        {a b c eta : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b) (hc : 0 < c)
        (hbac : a * c / 2 ≤ b) (heta : eta ≤ min a (b / c)) (n : ℕ) :
        weightedThreeStateRow a b c eta n ≠ 0 ∧
          (weightedThreeStateRow a b c eta n).Splits
  • All roots of every row are negativeRealRooted original

    RealRooted.weightedThreeStateRow_roots_negsource
    theorem weightedThreeStateRow_roots_neg
        {a b c eta : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b) (hc : 0 < c)
        (hbac : a * c / 2 ≤ b) (heta : eta ≤ min a (b / c)) (n : ℕ) :
        ∀ r ∈ (weightedThreeStateRow a b c eta n).roots, r < 0
  • The third-order recurrence satisfied by the middle coordinateRealRooted original

    RealRooted.weightedThreeState_P_add_threesource
    theorem weightedThreeState_P_add_three
        (b alpha d eta : ℝ) (n : ℕ) :
        (weightedThreeState b alpha d eta (n + 3)).P =
          3 * (weightedThreeState b alpha d eta (n + 2)).P +
            ((C (alpha + d) * X - 3) *
              (weightedThreeState b alpha d eta (n + 1)).P) +
            ((1 + C (b - (alpha + d)) * X) *
              (weightedThreeState b alpha d eta n).P)
  • In the half-height range η ≤ a/2 the n-th row has degree ⌊n/2⌋RealRooted original

    RealRooted.weightedThreeStateRow_natDegree_halfHeightsource
    theorem weightedThreeStateRow_natDegree_halfHeight
        {a b c eta : ℝ} (ha : 0 < a) (hb : 0 ≤ b) (hc : 0 < c)
        (heta : eta ≤ a / 2) (n : ℕ) :
        (weightedThreeStateRow a b c eta n).natDegree = n / 2
  • Normalized rows have nonnegative coefficients for ρ ≥ 0 and e ≤ 1/2RealRooted original

    RealRooted.weightedStripRow_hasNonnegCoeffssource
    theorem weightedStripRow_hasNonnegCoeffs {rho e : ℝ}
        (hrho : 0 ≤ rho) (he : e ≤ 1 / 2) (n : ℕ) :
        HasNonnegCoeffs (weightedStripRow rho e n)
  • Rescaling of the physical family (a, b, c, η) to the normalized strip rowsRealRooted original

    RealRooted.weightedThreeStateRow_eq_strip_compsource
    theorem weightedThreeStateRow_eq_strip_comp {a b c eta : ℝ}
        (ha : a ≠ 0) (hc : c ≠ 0) (n : ℕ) :
        weightedThreeStateRow a b c eta n =
          C (c ^ n) *
            (weightedStripRow (b / (a * c)) (eta / a) n).comp
              (C (a / c ^ 2) * X)
  • Sign changes at ⌊n/2⌋ + 1 points force a normalized row to split with simple rootsRealRooted original

    RealRooted.weightedStripRow_roots_of_sign_changessource
    theorem weightedStripRow_roots_of_sign_changes {rho e : ℝ}
        (hrho : 0 ≤ rho) (he : e ≤ 1 / 2) (n : ℕ)
        (x : Fin (n / 2 + 1) → ℝ) (hx : StrictMono x)
        (hsign : ∀ i : Fin (n / 2),
          (weightedStripRow rho e n).eval (x i.castSucc) *
            (weightedStripRow rho e n).eval (x i.succ) < 0) :
        (weightedStripRow rho e n).Splits ∧
          (weightedStripRow rho e n).roots.Nodup ∧
          ∀ z ∈ (weightedStripRow rho e n).roots,
            x 0 < z ∧ z < x (Fin.last (n / 2))
  • Positive characteristic parametrization of the evaluation pointRealRooted original

    RealRooted.existsUnique_characteristicScale_eqsource
    theorem existsUnique_characteristicScale_eq {rho s : ℝ}
        (hrho : 0 < rho) (hs : 0 < s) :
        ∃! r, 0 < r ∧ r < rho ∧ characteristicScale rho r = s
  • Q_n(-s) is an explicit expansion in the three characteristic rootsRealRooted original

    RealRooted.weightedStripRow_eval_eq_expansionsource
    theorem weightedStripRow_eval_eq_expansion {rho e r s v : ℝ}
        (hs : 0 < s) (hv : 0 < v)
        (hcubic : r ^ 3 = s * (rho - r))
        (hvsq : v ^ 2 = s + 3 * r ^ 2 / 4) (n : ℕ) :
        (((weightedStripRow rho e n).eval (-s : ℝ) : ℝ) : ℂ) =
          weightedThreeStateExpansion e r s v n
  • Amplitude inequality for the complex-root contributionRealRooted original

    RealRooted.weightedThreeStateAmplitude_gap_possource
    theorem weightedThreeStateAmplitude_gap_pos {r v e k : ℝ}
        (hr : 0 < r) (hv : 0 < v) (hk : 0 < k)
        (hehalf : e ≤ 1 / 2)
        (hvk : v ^ 2 = r ^ 2 * (k + 3 / 4)) :
        0 < 4 * Complex.normSq
            (weightedThreeStateAmplitudeB r v (weightedThreeStateAmplitudeA e k)) -
          weightedThreeStateAmplitudeA e k ^ 2 *
            (1 + 9 * r ^ 2 / (4 * v ^ 2))

Lean source RealRooted/Challenges/Matrices/WeightedThreeStateRecurrence.lean at revision d6670742. Formalized 2026-10-29.