P-recursive equation

Further information: Holonomic function

In mathematics a P-recursive equation is a linear equation of sequences where the coefficient sequences can be represented as polynomials. P-recursive equations are linear recurrence equations (or linear recurrence relations or linear difference equations) with polynomial coefficients. These equations play an important role in different areas of mathematics, specifically in combinatorics. The sequences which are solutions of these equations are called holonomic, P-recursive, or D-finite.

From the late 1980s, the first algorithms were developed to find solutions for these equations. Sergei A. Abramov, Marko Petkovšek and Mark van Hoeij described algorithms to find polynomial, rational, hypergeometric and d'Alembertian solutions.

Definition

Let ${\textstyle \mathbb {F} }$ be a field of characteristic zero, meaning there is no ${\textstyle m\in \mathbb {N} }$ such that ${\textstyle 0=\sum _{k=1}^{m}1}$, and ${\textstyle n\in \mathbb {N} }$.

A sequence ${\textstyle (x_{k})_{k\in \mathbb {N} _{0}}\in \mathbb {F} ^{\mathbb {N} _{0}}}$ is called P-recursive if it satisfies a linear recursive equation with coefficients in ${\textstyle \mathbb {F} [n]}$ meaning there exists a sequence ${\textstyle (p_{k}(n))_{k\in \mathbb {N} _{0}}\in (\mathbb {F} [n])^{\mathbb {N} _{0}}}$ a polynomial ${\textstyle y(n)\in \mathbb {F} [n]}$ such that $$\sum \limits _{k=0}^{\infty }p_{k}(n)\cdot x_{n+k}=y(n).$$Linear equations of this form are called P-recursive equations. Solutions to this equation are generally in ${\textstyle x_{n}\in {\overline {\mathbb {F} [n]}}}$ meaning the completion of ${\textstyle \mathbb {F} [n]}$, More specifically a equation$$\sum \limits _{k=0}^{m}p_{k}(n)\cdot x_{n+k}=y(n)$$ for a ${\textstyle m\in \mathbb {N} }$ is said to be of order ${\textstyle m}$ if and only if ${\textstyle p_{0},\,p_{m}}$ are non-zero.

Some authors further more require the equation to be homogenous, meaning ${\textstyle y}$ to be zero, for it to be called P-recursive. Further more a power series is called D-finite if it's coefficients are P-recursive.

Closed form solutions

Let ${\textstyle \sum _{k=0}^{r}p_{k}(n)\cdot y_{n+k}=f(n)}$ or equivalently ${\textstyle L\cdot y=f}$, where ${\textstyle y=(y_{k})_{k\in \mathbb {N} _{0}}}$, ${\textstyle f=(f_{k})_{k\in \mathbb {N} _{0}}}$ and ${\textstyle L=(p_{k}(g))_{(k,\,g)\in \{0,\,1,\,\ldots ,\,r\}\times \mathbb {N} _{0}}}$acts as a linear operator, be a P-recurrence equation. There exist several algorithms which compute solutions of this equation. These algorithms can compute polynomial, rational, hypergeometric and d'Alembertian solutions. The solution of a homogeneous equation is given by the kernel of the linear recurrence operator: ${\textstyle \ker(L)={\big \{}y\in \mathbb {F} ^{\mathbb {N} _{0}}\mid L\cdot y=0{\big \}}}$. As a subspace of the space of sequences this kernel has a basis. Let ${\textstyle \{y^{(k)}\mid k\in \mathbb {N} _{\leq m}\}}$ be a basis of ${\textstyle \ker(L)}$, then the formal sum ${\textstyle y_{h}=\sum _{k=1}^{m}c_{k}\cdot y^{(k)}}$ for arbitrary constants ${\textstyle (c_{k})_{k\in \mathbb {N} _{\leq m}}\in \mathbb {F} ^{m}}$ is called a homogeneous solutiion to ${\textstyle L\cdot y=f}$, meaning ${\textstyle L\cdot y=0}$. If ${\textstyle y_{p}}$ is a particular solution of ${\textstyle L\cdot y=f}$, meaning ${\textstyle L\cdot y_{p}=f}$, then ${\textstyle y_{h}+y_{p}}$ is also a solution of the inhomogeneous problem. This means a general solution is gven by ${\textstyle y=y_{h}+y_{p}}$.

Polynomial solutions

Main article: Polynomial solutions of P-recursive equations

In the late 1980s Sergei A. Abramov described an algorithm which finds the general polynomial solution of a recurrence equation, i.e. ${\textstyle y(n)\in \mathbb {F} [n]}$, with a polynomial right-hand side${\textstyle f(n)\in \mathbb {K} [n]}$. He (and a few years later Marko Petkovšek) gave a degree bound for polynomial solutions. This way the problem can simply be solved by considering a system of linear equations. In 1995 Abramov, Bronstein and Petkovšek showed that the polynomial case can be solved more efficiently by considering power series solution of the recurrence equation in a specific power basis (i.e. not the ordinary basis ${\textstyle (x^{n})_{n\in \mathbb {N} }}$).

The other algorithms for finding more general solutions (e.g. rational or hypergeometric solutions) also rely on algorithms which compute polynomial solutions.

Rational solutions

Main article: Abramov's algorithm

In 1989 Sergei A. Abramov showed that a general rational solution, i.e. ${\textstyle y(n)\in \mathbb {K} (n)}$, with polynomial right-hand side ${\textstyle f(n)\in \mathbb {K} [n]}$, can be found by using the notion of a universal denominator. A universal denominator is a polynomial ${\textstyle u}$ such that the denominator of every rational solution divides ${\textstyle u}$. Abramov showed how this universal denominator can be computed by only using the first and the last coefficient polynomial ${\textstyle p_{0}}$ and ${\textstyle p_{r}}$. Substituting this universal denominator for the unknown denominator of $y$ all rational solutions can be found by computing all polynomial solutions of a transformed equation.

Hypergeometric solution

Main article: Petkovšek's algorithm

A sequence ${\textstyle y(n)}$ is called hypergeometric if the ratio of two consecutive terms is a rational function in $n$, i.e. ${\textstyle y(n+1)/y(n)\in \mathbb {F} (n)}$ where ${\textstyle \mathbb {F} (n)={\text{Quot}}(\mathbb {F} [n])}$ is the quotient of the polynomial ring ${\textstyle \mathbb {F} [n]}$. This is the case if and only if the sequence is the solution of a first-order recurrence equation with polynomial coefficients. The set of hypergeometric sequences is not a subspace of the space of sequences as it is not closed under addition.

In 1992 Marko Petkovšek gave an algorithm to get the general hypergeometric solution of a recurrence equation where the right-hand side $f$ is the sum of hypergeometric sequences. The algorithm makes use of the Gosper-Petkovšek normal-form of a rational function. With this specific representation it is again sufficient to consider polynomial solutions of a transformed equation.

A different and more efficient approach is due to Mark van Hoeij. Considering the roots of the first and the last coefficient polynomial ${\textstyle p_{0}}$ and ${\textstyle p_{r}}$ – called singularities – one can build a solution step by step making use of the fact that every hypergeometric sequence ${\textstyle y(n)}$ has a representation of the form $$y(n)=c\cdot r(n)\cdot z^{n}\cdot \prod \limits _{k=1}^{s}\Gamma (n-\xi _{k})^{e_{k}}$$ for some ${\textstyle c\in \mathbb {F} ,\,z\in {\overline {\mathbb {F} }},\,s\in \mathbb {N} ,r(n)\in {\overline {\mathbb {F} (n)}},\,(\xi _{k})_{k\in \mathbb {N} _{\leq s}}\in {\overline {\mathbb {F} }}^{s}}$ with ${\textstyle \xi _{i}-\xi _{j}\notin \mathbb {Z} }$ for ${\textstyle i\neq j}$ and ${\textstyle e_{1},\dots ,e_{s}\in \mathbb {Z} }$. Here ${\textstyle \Gamma (n)}$ denotes the Gamma function. Then the ${\textstyle \xi _{1},\dots ,\xi _{s}}$ have to be singularities of the equation (i.e. roots of ${\textstyle p_{0}}$ or ${\textstyle p_{r}}$). Furthermore one can compute bounds for the exponents ${\textstyle e_{i}}$. For fixed values ${\textstyle \xi _{1},\dots ,\xi _{s},e_{1},\dots ,e_{s}}$ it is possible to make an ansatz which gives candidates for ${\textstyle z}$. For a specific ${\textstyle z}$ one can again make an ansatz to get the rational function ${\textstyle r(n)}$ by Abramov's algorithm. Considering all possibilities one gets the general solution of the recurrence equation.

D'Alembertian solutions

A sequence $y$ is called d'Alembertian if ${\textstyle y=h_{1}\sum h_{2}\sum \cdots \sum h_{k}}$ for some hypergeometric sequences ${\textstyle h_{1},\dots ,h_{k}}$ and ${\textstyle y=\sum x}$ means that ${\textstyle \Delta y=x}$ where ${\textstyle \Delta }$ denotes the forward fininite difference operator, i.e. ${\textstyle (\Delta y){:}\,n\mapsto y(n+1)-y(n)}$. This is the case if and only if there are first-order linear recurrence operators ${\textstyle (L_{k})_{k\in \mathbb {N} _{\leq m}}}$ with rational coefficients such that ${\textstyle (\prod _{k=1}^{m}L_{k})\cdot y=0}$.

1994 Abramov and Petkovšek described an algorithm which computes the general d'Alembertian solution of a recurrence equation. This algorithm computes hypergeometric solutions and reduces the order of the recurrence equation recursively.

Examples

Signed permutation matrices

The number of signed permutation matrices of size $n\times n$ can be described by the function ${\textstyle y{:}\,\mathbb {N} _{0}\to \mathbb {Q} }$. A signed permutation matrix is a square matrix which has exactly one nonzero entry in every row and in every column. The nonzero entries can be ${\textstyle \pm 1}$. The sequence is determined by the linear recurrence equation with polynomial coefficients $$y(n)=4\cdot (n-1)^{2}\cdot y(n-2)+2\cdot y(n-1)$$ and the initial values ${\textstyle y(0)=1,\,y(1)=2}$. Applying an algorithm to find hypergeometric solutions one can find the general hypergeometric solution $$y(n)=c\cdot 2^{n}\cdot n!$$ for some constant ${\textstyle c}$. Also considering the initial values, the sequence ${\textstyle y(n)=2^{n}\cdot n!}$ describes the number of signed permutation matrices.

Applications

Hypergeometric functions

A sequence ${\textstyle (x_{k})_{k\in \mathbb {N} _{0}}}$ is called hypergeometric if ${\textstyle {\frac {x_{n+1}}{x_{n}}}\in \mathbb {F} (n)}$ meaning a quotient that reduces to the quotient of two polynomials. A hypergeometric function ${\textstyle f}$ is a function in the broad class of analytc functions that can be represented as a power series with hypergeometric coefficients ${\textstyle (f_{k})_{k\in \mathbb {N} _{0}}}$ such that ${\textstyle f{:}\,\mathbb {F} \to \mathbb {F} ,\,x\mapsto \sum _{k=0}^{\infty }f_{k}\cdot x^{k}}$. This means that that there exists a pair ${\textstyle p(n),\,q(n)\in \mathbb {F} [n]}$ such that ${\textstyle {\frac {x_{n+1}}{x_{n}}}={\frac {p_{n}}{q_{n}}}\in \mathbb {F} (n)}$ giving us ${\textstyle q_{n}\cdot x_{n+1}-p_{n}\cdot x_{n}=0}$, a P-recurrence equation to recursively calculate the coefficients of that function.