Finite certificates for differential recurrences

A polynomial sequence with a rational generating function satisfies a pure-lag recurrence, while interlacing criteria need a first-order differential recurrence. One polynomial identity links the two, so the differential recurrence follows from the lag recurrence and finitely many seeds.

Results

Let $K$ be a field and $P_0,P_1,\dotsc\in K[x]$. A pure-lag recurrence of order $k$ with coefficients $a_i\in K[x]$ is $$ P_{n+k}=\sum_{i<k}a_i\,P_{n+i}, $$ and a lift with $d_1,d_0,A_1,A_0,B\in K[x]$ is $$ d(n)\,P_{n+1}=A(n)\,P_n+B\,P_n',\qquad d(n)=nd_1+d_0,\quad A(n)=nA_1+A_0 . $$ Let $S$ be the forward shift on sequences, and put $$ R_n=P_{n+k}-\sum_{i<k}a_iP_{n+i},\qquad L_n=d(n)P_{n+1}-A(n)P_n-BP_n', $$ the lag defect and the lift defect, and $\chi(S)=S^k-\sum_ia_iS^i$.

Theorem (defect identity). For every sequence $P$, with no recurrence assumed, $$ (\chi(S)L)_n=d(n+k)\,R_{n+1}-A(n+k)\,R_n-B\,R_n'+(J(S)P)_n, $$ where $$ J(S)=\sum_{i<k}\Bigl((k-i)\,a_id_1\,S^{i+1}-\bigl((k-i)\,a_iA_1+B\,a_i'\bigr)S^i\Bigr). $$

Corollary (propagation). Suppose $J=\gamma\,\chi$ for some $\gamma\in K[x]$.

Theorem (filtered finite check). Let $N$ multiply the $n$-th entry of a sequence by $n$, let $D$ differentiate every entry, and let $F=\sum c_{u,j,s}\,N^uS^jD^s$ be a finite combination with coefficients in $K[x]$ of weight below $h$, meaning $u+s<h$ for every word. Let $p$ be a monic polynomial of degree $k$ in $S$ with coefficients in $K[x]$, and let $f$ satisfy $p(S)f=0$. Then $p(S)^hFf=0$, and $$ Ff=0\iff (Ff)_n=0\ \text{ for all } n<hk . $$ Underlying this, if $p(S)^qf=0$ then $p(S)^{q+1}Df=0$.

Use

To prove interlacing for a sequence given by a pure-lag recurrence, it suffices to check $J=\gamma\chi$, finitely many seeds and $d(n+k)\ne0$. The derivative recurrence of the corollary then feeds the root-window theorems. See also the Sturm sequence families.

References

Finite verification of recurrences on symmetricfunctions.com.

Definitions

  • Defect of a pure-lag recurrence

    RealRooted.lagDefectsource
    def lagDefect {k : ℕ} (a : Fin k → K[X]) (P : ℕ → K[X]) (n : ℕ) : K[X] :=
      P (n + k) - ∑ i, a i * P (n + i)
  • Defect of a first-order differential lift

    RealRooted.liftDefectsource
    def liftDefect (d₁ d₀ A₁ A₀ B : K[X]) (P : ℕ → K[X]) (n : ℕ) : K[X] :=
      affineIndex d₁ d₀ n * P (n + 1) - affineIndex A₁ A₀ n * P n -
        B * (P n).derivative
  • Correction polynomial of the defect identity

    RealRooted.defectCorrectionsource
    def defectCorrection {k : ℕ} (a : Fin k → K[X]) (d₁ A₁ B : K[X]) :
        Polynomial K[X] :=
      ∑ i : Fin k, (monomial (i + 1) ((k - i : ℕ) * a i * d₁) -
        monomial i ((k - i : ℕ) * a i * A₁ + B * (a i).derivative))
  • Filtered operator built from shift, index multiplication and differentiation

    RealRooted.FilteredOperatorsource
    structure FilteredOperator where
      /-- The finite collection of words used by the operator. -/
      support : Finset RecurrenceWord
      /-- The polynomial coefficient multiplying each word. -/
      coeff : RecurrenceWord → K[X]

Theorems

  • Universal source-and-lift defect identityRealRooted original

    RealRooted.lagDefect_liftDefectsource
    theorem lagDefect_liftDefect {k : ℕ} (a : Fin k → K[X])
        (d₁ d₀ A₁ A₀ B : K[X]) (P : ℕ → K[X]) (n : ℕ) :
        lagDefect a (liftDefect d₁ d₀ A₁ A₀ B P) n =
          affineIndex d₁ d₀ (n + k) * lagDefect a P (n + 1) -
            affineIndex A₁ A₀ (n + k) * lagDefect a P n -
            B * (lagDefect a P n).derivative +
            LinearRecurrence.shiftAction (defectCorrection a d₁ A₁ B) P n
  • A source recurrence and k seeds give the differential liftRealRooted original

    RealRooted.liftDefect_eq_zero_of_lagDefect_eq_zerosource
    theorem liftDefect_eq_zero_of_lagDefect_eq_zero {k : ℕ} (a : Fin k → K[X])
        (d₁ d₀ A₁ A₀ B gamma : K[X]) (P : ℕ → K[X])
        (hsource : ∀ n, lagDefect a P n = 0)
        (hfactor : defectCorrection a d₁ A₁ B = C gamma * lagCharacteristic a)
        (hseed : ∀ n < k, liftDefect d₁ d₀ A₁ A₀ B P n = 0) :
        liftDefect d₁ d₀ A₁ A₀ B P = 0
  • A differential lift and one seed give the pure-lag recurrenceRealRooted original

    RealRooted.lagDefect_eq_zero_of_liftDefect_eq_zerosource
    theorem lagDefect_eq_zero_of_liftDefect_eq_zero {k : ℕ} (a : Fin k → K[X])
        (d₁ d₀ A₁ A₀ B gamma : K[X]) (P : ℕ → K[X])
        (hlift : ∀ n, liftDefect d₁ d₀ A₁ A₀ B P n = 0)
        (hfactor : defectCorrection a d₁ A₁ B = C gamma * lagCharacteristic a)
        (hseed : lagDefect a P 0 = 0)
        (hleader : ∀ n, affineIndex d₁ d₀ (n + k) ≠ 0) :
        lagDefect a P = 0
  • A zero lift defect with a scalar leader is the derivative recurrenceRealRooted original

    RealRooted.derivativeRecurrence_of_liftDefect_eq_zerosource
    theorem derivativeRecurrence_of_liftDefect_eq_zero
        (d₁ d₀ A₁ A₀ B : K[X]) (P : ℕ → K[X]) (delta : ℕ → K)
        (hlift : ∀ n, liftDefect d₁ d₀ A₁ A₀ B P n = 0)
        (hdelta : ∀ n, affineIndex d₁ d₀ n = C (delta n))
        (hdelta_ne : ∀ n, delta n ≠ 0) (n : ℕ) :
        P (n + 1) = C (delta n)⁻¹ * B * (P n).derivative +
          C (delta n)⁻¹ * affineIndex A₁ A₀ n * P n
  • Differentiation raises the annihilating power of a shift polynomial by oneRealRooted original

    RealRooted.shiftAction_pow_succ_sequenceDerivative_eq_zerosource
    theorem shiftAction_pow_succ_sequenceDerivative_eq_zero (p : Polynomial K[X]) (q : ℕ)
        (f : ℕ → K[X]) (hf : LinearRecurrence.shiftAction (p ^ q) f = 0) :
        LinearRecurrence.shiftAction (p ^ (q + 1)) (sequenceDerivative f) = 0
  • A filtered operator of weight below h maps solutions into the kernel of the h-th powerRealRooted original

    RealRooted.FilteredOperator.shiftAction_pow_apply_eq_zerosource
    theorem FilteredOperator.shiftAction_pow_apply_eq_zero
        (L : FilteredOperator (K := K))
        (p : Polynomial K[X]) (h : ℕ) (f : ℕ → K[X])
        (hf : LinearRecurrence.shiftAction p f = 0)
        (hweight : ∀ w ∈ L.support, w.indexOrder + w.derivativeOrder < h) :
        LinearRecurrence.shiftAction (p ^ h) (L.apply f) = 0
  • Filtered finite check: vanishing of the first h·k terms sufficesMain resultRealRooted original

    RealRooted.FilteredOperator.apply_eq_zero_iffsourcestatement on symmetricfunctions.com
    theorem FilteredOperator.apply_eq_zero_iff (L : FilteredOperator (K := K))
        (p : Polynomial K[X]) (h k : ℕ) (f : ℕ → K[X]) (hp : p.Monic)
        (hdegree : p.natDegree = k) (hf : LinearRecurrence.shiftAction p f = 0)
        (hweight : ∀ w ∈ L.support, w.indexOrder + w.derivativeOrder < h) :
        L.apply f = 0 ↔ ∀ n < h * k, L.apply f n = 0

Lean source RealRooted/Challenges/Interlacing/RecurrenceSpaceCertificates.lean at revision d6670742. Formalized 2026-10-21.