The symmetric functions catalog

#Polynomial recurrences and derivatives

A polynomial sequence can have several useful recurrences. A relation using many consecutive polynomials may be replaced by one using fewer polynomials and their derivatives. We study when this is possible, how to describe all relations with prescribed coefficient bounds, and how to prove an identity found by exact linear algebra.

Throughout, \(P_n(x)\in\setQ[x]\) and \(n\geq0.\) A linear differential–difference equation of order \(r\) in the index and derivative order at most \(m\) has the form \[\delta(n,x)P_{n+r}(x) =\sum_{j=0}^{r-1}\sum_{s=0}^{m}A_{j,s}(n,x)P_{n+j}^{(s)}(x), \qquad \delta\ne0.\] The superscript denotes differentiation in \(x.\) For \(m=0\) this is an ordinary linear recurrence. An identity determines the next polynomial only at indices where its leading coefficient is nonzero. We shall distinguish polynomial coefficients with prescribed degree bounds, arbitrary rational coefficients, and the restriction \(\delta=\delta(n).\)

The general operator framework is the \(\partial\)-finite theory of F. Chyzak and B. Salvy [CS98, Sec. 2]; see also C. Koutschan’s account of the holonomic systems approach [Kou09]. The criteria below are direct consequences of linear algebra and rational generating functions. Real-rootedness is an additional application.

#Reducing recurrence order using derivatives

Consider \[P_n(x)=1+x^n+(x+1)^n.\] It satisfies three different recurrences: \[\begin{aligned} P_{n+3} &=(2x+2)P_{n+2}-(x^2+3x+1)P_{n+1}+x(x+1)P_n,\\ 2nP_{n+2} &=3n(x+1)P_{n+1}-n(3x+1)P_n-x(x-1)(x+1)P_n',\\ n(n-1)P_{n+1} &=n(n-1)P_n+(n-1)x(3x+1)P_n'-2x^2(x+1)P_n''. \end{aligned}\] Each identity follows by substituting the three summands separately. They hold for every \(n\geq0,\) including the indices where the leading coefficient vanishes.

There is no identity \(P_{n+1}=AP_n+BP_n'\) even with coefficients in \(\setQ(n,x).\) Indeed, independence of the three exponential sequences would imply \[A=1,\qquad B=\frac{x(x-1)}{n},\qquad B=\frac{x(x+1)}{n},\] simultaneously. There is also no second-order recurrence without derivatives over this field. Thus the pairs \((3,0),(2,1),(1,2)\) are optimal: neither recurrence order nor derivative order can be reduced while keeping the other fixed.

#Recurrences with bounded coefficient degrees

Suppose the sequence is specified by \(P_0,\dotsc,P_{k-1}\) and \[P_{n+k}=\sum_{i=0}^{k-1}a_i(x)P_{n+i},\qquad a_i(x)\in\setQ[x].\] Here the coefficients are independent of \(n\); they need not be constant in \(x.\) Such recurrences arise, for example, from the transfer matrix method.

Let \(S\) shift the index, so \((SP)_n=P_{n+1},\) and let \(\partial_x\) differentiate each polynomial. Fix a finite set of allowed monomials and consider operators \[L=\sum_{j,s,u,v}c_{j,s,u,v}x^v n^u S^j\partial_x^s, \qquad c_{j,s,u,v}\in\setQ.\] All indices in this sum are nonnegative. Coefficients act on the left, so \((nS P)_n=nP_{n+1}.\) These operators form a finite-dimensional vector space.

To compute the matrix, substitute an unknown coefficient for each allowed monomial, evaluate these \(hk\) residuals, and equate coefficients of \(x.\) For \(M\) unknowns and \(R\) scalar equations, exact elimination uses \(O(RM^2+M^3)\) rational field operations; coefficient sizes affect bit complexity.

A recurrence with \(\delta\ne0\) exists in the prescribed space if and only if the kernel has nonzero projection to the \(\delta\) coordinates. Vectors with \(\delta=0\) are relations among the earlier polynomials and their derivatives.

#A recurrence for the residual

There is also a finite induction proof. Put \[\chi(z)=z^k-\sum_{i\lt{}k}a_i(x)z^i,\qquad T=\chi(S),\] and let \(\mathsf N\) multiply a sequence by its index. The commutators satisfy \[[T,\mathsf N]=(z\chi_z)(S),\qquad [\partial_x,T]=\chi_x(S).\] Both right-hand sides commute with \(T.\) If \(T^qf=0,\) the commutator identities imply \(T^{q+1}(\mathsf Nf)=0\) and \(T^{q+1}(\partial_xf)=0.\) Shifts and multiplication by \(x\) commute with \(T,\) so every allowed residual satisfies \[\chi(S)^h(LP)=0.\] This is a monic recurrence of order \(hk.\) Its first \(hk\) zero polynomials therefore force all subsequent residuals to vanish. The coefficients of \(\chi(z)^h\) and the initial residuals determine a proof by recurrence induction.

#First derivatives and generating functions

For a proposed identity \[(d_0+d_1n)P_{n+1} =(A_0(x)+nA_1(x))P_n+B(x)P_n',\] where \(d_0,d_1\in\setQ\) and \(A_0,A_1,B\in\setQ[x],\) summation gives the following equivalent equation: \[t(d_1-tA_1)F_t-tBF_x+(d_0-d_1-tA_0)F=(d_0-d_1)P_0.\] This is a first-order linear partial differential equation. If the derivative coefficient is instead \(B_0(x)+nB_1(x),\) the equation contains the additional term \(-t^2B_1F_{xt}\) and is generally of second order.

There is an exact criterion involving the reduced denominator. Define \[V=t(d_1-tA_1)\partial_t-tB\partial_x,\qquad C=d_0-d_1-tA_0,\qquad H=(d_0-d_1)P_0.\]

In particular, the pole curves must be invariant under the vector field \(V.\) The numerator condition records the initial polynomials; the denominator alone does not determine whether the derivative recurrence holds.

#Rational coefficients and repeated poles

We now allow coefficients in \(\setQ(n,x)\) and consider identities for all sufficiently large indices. Divide the reduced rational generating function into a polynomial part \(U(x,t)\) and a proper rational part. Partial fractions over a finite splitting field \(E\) of \(\setQ(x)\) give \[P_n^{\mathrm{tail}}=\sum_{i=1}^d a_i(n,x)\lambda_i(x)^n.\] The \(\lambda_i\) are distinct nonzero characteristic roots, and \(a_i\in E[n]\) is nonzero. A pole of multiplicity \(m_i\) gives \(\deg_n a_i=m_i-1,\) since \[[t^n](1-\lambda_i t)^{-m_i} =\binom{n+m_i-1}{m_i-1}\lambda_i^n.\] Thus repeated poles change the amplitudes, while the number \(d\) counts distinct characteristic roots with nonzero amplitudes.

On \(E(n)^d,\) with amplitude vector \(a=(a_i),\) define \[(\mathsf Sv)_i=\lambda_i v_i(n+1,x),\qquad (\nabla v)_i=\partial_xv_i+n\frac{\lambda_i'}{\lambda_i}v_i.\] Differentiation includes the algebraic dependence on \(x\) in \(E.\) These operators commute and represent shift and differentiation of the corresponding exponential sums.

This gives a finite test for every pair \((r,m)\) and determines all minimal combinations of recurrence order and derivative order over \(\setQ(n,x).\) The least order of a recurrence without derivatives is \(d\) when rational index dependence is allowed, and \(\sum_i m_i\) when the coefficients must be independent of \(n.\) Both assertions concern eventual identities.

For example, \((n+1)x^n\) has a double pole at \(t=1/x\) and satisfies both \[P_{n+2}=2xP_{n+1}-x^2P_n, \qquad (n+1)P_{n+1}=(n+2)xP_n.\]

#The annihilating ideal

In the Ore algebra \(\setQ(n,x)\langle S,\partial_x\rangle,\) operators satisfy \[S f(n,x)=f(n+1,x)S,\qquad \partial_x f=f\partial_x+\partial_x(f),\qquad S\partial_x=\partial_xS.\] The operators annihilating the sequence eventually form its annihilating ideal. Expressing \(\mathsf S^da\) and \(\nabla a\) in the shift basis gives two generators: \[S^d-\sum_{j\lt{}d}r_j(n,x)S^j,\qquad \partial_x-\sum_{j\lt{}d}b_j(n,x)S^j.\] To see this, reduce derivatives using the second relation and then shifts using the first. The remaining operator is a linear combination of \(1,S,\dotsc,S^{d-1},\) and independence forces an annihilating remainder to be zero.

The polynomial part \(U\) records the finite initial contribution discarded by eventual equality. After clearing denominators, a polynomial-coefficient tail identity holds from \(n=0\) exactly when it also annihilates the finite coefficient sequence of \(U.\) Checking \(0\leq n\leq\deg_tU\) suffices, since forward shifts and \(x\)-derivatives cannot enlarge this support.

#Beraha–Kahane–Weiss and limiting zeros

The same characteristic roots also control where zeros accumulate as \(n\to\infty.\) This is the content of the Beraha–Kahane–Weiss theorem [BKW75], also used in the transfer-matrix setting. We now let \(x\) be complex and work on a domain where the characteristic roots and amplitudes are single-valued analytic functions.

This is the convenient stronger-hypothesis form of [Sok04, Thm. 1.5]; Sokal only excludes constant unit-modulus ratios when the corresponding branches are dominant on a set with nonempty interior.

The derivative-recurrence criterion uses the values and logarithmic derivatives of the characteristic roots; BKW uses their relative moduli. Both depend on the nonzero amplitudes, which are determined by the initial polynomials. Equal modulus alone does not give a limiting zero unless the tied branches are dominant.

For repeated poles the amplitudes \(a_i(n,x)\) depend polynomially on \(n,\) so the displayed theorem does not apply directly. A common scalar factor in \(n\) can be removed for large \(n\); general polynomial-in-\(n\) amplitudes require an extension. The repeated-pole rank criteria above do not need this analytic extension.

#When does one derivative suffice?

For the exponential sum above, put \[\eta_i=\frac{\partial_xa_i}{a_i} +n\frac{\lambda_i'}{\lambda_i},\qquad \rho_i=\lambda_i\frac{a_i(n+1,x)}{a_i(n,x)}.\]

For simple poles the amplitudes are independent of \(n,\) and the criterion has a more explicit form. Write \(u_i=a_i'/a_i\) and \(v_i=\lambda_i'/\lambda_i.\) A first-order differential recurrence exists if and only if \[u_i=\alpha_0+\beta_0\lambda_i,\qquad v_i=\alpha_1+\beta_1\lambda_i\] for all \(i,\) with \(\alpha_0,\alpha_1,\beta_0,\beta_1\in\setQ(x)\) and \((\beta_0,\beta_1)\ne(0,0).\) In that case \[A=-\frac{\alpha_0+n\alpha_1}{\beta_0+n\beta_1},\qquad B=\frac{1}{\beta_0+n\beta_1}.\] Indeed, \(\lambda_i=A+B(u_i+nv_i)\) is equivalent to these conditions after comparing coefficients of \(n\) modulo the span of \(1\) and \(\lambda.\) In particular, all characteristic roots satisfy the same Riccati equation \(\lambda_i'=\alpha_1\lambda_i+\beta_1\lambda_i^2.\)

Repeated poles still give a degree bound. If \(M=\max_i(m_i-1)\) and a first-order differential recurrence exists, it has a polynomial form \[\Delta(n,x)P_{n+1}=C(n,x)P_n+G(n,x)P_n'\] with index degrees at most \(2M+1,2M+1,2M,\) respectively, for the proper tail. To obtain it, put \(p(z)=\prod_i(z-\lambda_i)\) and use a basis of \(\setQ(x)[z]/(p(z)).\) The vectors \(a,\nabla a,\mathsf Sa\) have index degrees at most \(M,M+1,M.\) A nonzero two-by-two minor and Cramer’s rule give the stated bounds; clearing denominators in \(x\) preserves them.

#Why the coefficient class matters

More derivatives do not always shorten a recurrence. For \[P_n(x)=(1+2^n)x^n,\] every derivative is a rational multiple of \(P_n,\) whereas \(P_{n+1}\) is not. The two characteristic roots \(x\) and \(2x\) have the same logarithmic derivative. Thus no finite number of derivatives of \(P_n\) can express \(P_{n+1}\) with rational coefficients.

Requiring the coefficient of \(P_{n+1}\) to depend only on \(n\) creates another obstruction. For each integer \(\ell\geq1,\) the sequence \[P_n(x)=1+(2+x^\ell)^n\] has two simple poles. Over \(\setQ(n,x),\) one derivative suffices: \[P_{n+1}=P_n+ \frac{(1+x^\ell)(2+x^\ell)}{n\ell x^{\ell-1}}P_n'.\] With polynomial right-hand coefficients and a nonzero leading coefficient \(\delta(n),\) the least derivative order is instead exactly \(\ell.\)

The bound \(m\leq d-r\) consequently applies to rational coefficients, not to the restriction \(\delta=\delta(n)\) with polynomial right-hand coefficients. With prescribed coefficient-degree bounds, the matrix kernel still describes exactly the recurrences satisfying those restrictions.

#Computing recurrences

The Polytool recurrence finder provides comparison and complete-space modes. A useful report records the allowed coefficient degrees and derivatives, the starting index, a basis of the recurrence space, and formulas with \(\delta\ne0.\) Recurrence order and derivative order alone do not measure the cost of a formula: coefficient degrees and singular initial indices matter.

With a given recurrence and initial polynomials, the finite verification theorem proves the identities and completeness within the specified bounds. With finitely many input polynomials alone, a successful fit is an identity on those inputs. If every kernel vector has \(\delta=0,\) no recurrence with \(\delta\ne0\) and the allowed monomials can hold at every index: it would have to satisfy the same finite constraints. A computation stopped by a resource bound gives no such nonexistence conclusion.

For given recurrences whose coefficients depend polynomially on \(n,\) the rational generating-function argument need not apply. One can instead differentiate the given recurrence and form a finite state of shifted polynomials and their derivatives. A scalar recurrence for the residual, together with checks at singular indices and enough initial zeros, supplies a finite verification argument. Its bound depends on that state system.

#An application to real-rootedness

Suppose an exact identity has the form \[\delta(n)P_{n+1}=A(n,x)P_n+B(n,x)P_n',\qquad \delta(n)\gt{}0.\] If \(P_n\) is real-rooted, both \(P_n,P_{n+1}\) have positive leading coefficients, \(\deg P_{n+1}\in\{\deg P_n,\deg P_n+1\},\) and \(B(n,\xi)\leq0\) at every root \(\xi\) of \(P_n,\) then the Ma–Wang criterion [MW08, Thm. 2] gives real-rootedness of \(P_{n+1}\) and \(P_n\interl P_{n+1}.\) For example, \(B(n,x)=\kappa_n(x-a)(x-b)\) has the required sign on \([a,b]\) when \(a\lt{}b\) and \(\kappa_n\geq0.\) An induction using that interval also needs a proof that the new roots remain in it.

Bibliography

1. [BKW75]S. Beraha, J. Kahane and N. J. Weiss. Limits of zeroes of recursively defined polynomials. Proceedings of the National Academy of Sciences, 72(11):4209–4209, 1975.
   .bib

   Copy Download

   @article{Beraha75limits,
     author = {S. Beraha and J. Kahane and N. J. Weiss},
     title = {Limits of zeroes of recursively defined polynomials},
     journal = {Proceedings of the National Academy of Sciences},
     year = {1975},
     volume = {72},
     number = {11},
     pages = {4209--4209},
     doi = {10.1073/pnas.72.11.4209},
     url = {https://doi.org/10.1073/pnas.72.11.4209}
   }
   

2. [CS98]Frédéric Chyzak and Bruno Salvy. Non-commutative elimination in Ore algebras proves multivariate identities. Journal of Symbolic Computation, 26(2):187–227, 1998.
   .bib

   Copy Download

   @article{ChyzakSalvy1998,
     author = {Frédéric Chyzak and Bruno Salvy},
     title = {Non-commutative Elimination in {Ore} Algebras Proves Multivariate Identities},
     journal = {Journal of Symbolic Computation},
     year = {1998},
     volume = {26},
     number = {2},
     pages = {187--227},
     doi = {10.1006/jsco.1998.0207},
     url = {https://mathexp.eu/chyzak/Publications/ChyzakSalvy-1998-NCE.pdf}
   }
   

3. [Kou09]Christoph Koutschan. Advanced applications of the holonomic systems approach. Johannes Kepler University Linz, 2009.
   .bib

   Copy Download

   @phdthesis{Koutschan2009Thesis,
     author = {Christoph Koutschan},
     title = {Advanced Applications of the Holonomic Systems Approach},
     school = {Johannes Kepler University Linz},
     year = {2009},
     month = sep,
     url = {https://www.risc.jku.at/publications/download/risc_3886/thesisKoutschan.pdf}
   }
   

4. [MW08]Shi-Mei Ma and Yi Wang. $q$-Eulerian polynomials and polynomials with only real zeros. The Electronic Journal of Combinatorics, 15(1):Research Paper 17, January 2008.
   .bib

   Copy Download

   @article{MaWang2008,
     doi = {10.37236/741},
     url2 = {https://doi.org/10.37236/741},
     year = {2008},
     month = jan,
     publisher = {The Electronic Journal of Combinatorics},
     volume = {15},
     number = {1},
     author = {Shi-Mei Ma and Yi Wang},
     title = {$q$-{E}ulerian Polynomials and Polynomials with Only Real Zeros},
     pages = {Research Paper 17},
     journal = {The Electronic Journal of Combinatorics}
   }
   

5. [Sok04]Alan D. Sokal. Chromatic roots are dense in the whole complex plane. Combinatorics, Probability and Computing, 13(2):221–261, 2004.
   .bib

   Copy Download

   @article{Sokal2004ChromaticRoots,
     author = {Alan D. Sokal},
     title = {Chromatic roots are dense in the whole complex plane},
     year = {2004},
     journal = {Combinatorics, Probability and Computing},
     volume = {13},
     number = {2},
     pages = {221--261},
     doi = {10.1017/S0963548303006023},
     url = {https://doi.org/10.1017/S0963548303006023},
     eprint = {cond-mat/0012369}
   }