Ecuación p-recursiva

En matemáticas, una ecuación P-recursiva es una ecuación lineal de sucesiones donde las sucesiones de coeficientes se pueden representar como polinomios . Las ecuaciones P-recursivas son ecuaciones de recurrencia lineal (o relaciones de recurrencia lineal o ecuaciones de diferencias lineales) con coeficientes polinómicos. Estas ecuaciones juegan un papel importante en diferentes áreas de las matemáticas, específicamente en la combinatoria . Las sucesiones que son soluciones de estas ecuaciones se denominan holonómicas , P-recursivas o D-finitas.

A finales de los años 1980 se desarrollaron los primeros algoritmos para hallar soluciones a estas ecuaciones. Sergei A. Abramov, Marko Petkovšek y Mark van Hoeij describieron algoritmos para hallar soluciones polinómicas, racionales, hipergeométricas y d'Alembertianas.

Sea un cuerpo de característica cero (por ejemplo ), polinomios para , una sucesión y una sucesión desconocida. La ecuación se denomina ecuación de recurrencia lineal con coeficientes polinómicos (todas las ecuaciones de recurrencia de este artículo tienen esta forma). Si y son ambos distintos de cero, entonces se denomina orden de la ecuación. Si es cero, la ecuación se denomina homogénea; de lo contrario, se denomina no homogénea. ${\textstyle \mathbb {K}}$${\textstyle \mathbb {K} =\mathbb {Q} }$${\textstyle p_{k}(n)\in \mathbb {K} [n]}$${\textstyle k=0,\puntos ,r}$${\textstyle f\in \mathbb {K} ^{\mathbb {N} }}$${\textstyle y\in \mathbb {K} ^{\mathbb {N} }}$$${\displaystyle \sum_{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$$${\textstyle p_{0}}$${\textstyle p_{r}}$${\textstyle r}$${\textstyle f}$

Esto también se puede escribir como donde es un operador de recurrencia lineal con coeficientes polinomiales y es el operador de desplazamiento, es decir . ${\textstyle Ly=f}$${\textstyle L=\sum _ {k=0}^{r}p_{k}N^{k}}$${\textstyle N}$${\textstyle N\,y(n)=y(n+1)}$

Sea o equivalentemente una ecuación de recurrencia con coeficientes polinómicos. Existen varios algoritmos que calculan soluciones de esta ecuación. Estos algoritmos pueden calcular soluciones polinómicas, racionales, hipergeométricas y d'Alembertianas. La solución de una ecuación homogénea está dada por el núcleo del operador de recurrencia lineal: . Como subespacio del espacio de sucesiones, este núcleo tiene una base . ^[1] Sea una base de , entonces la suma formal para constantes arbitrarias se llama solución general del problema homogéneo . Si es una solución particular de , es decir , entonces es también una solución del problema no homogéneo y se llama solución general del problema no homogéneo. ${\textstyle \sum _ {k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$${\textstyle Ly=f}$${\textstyle \ker L=\{y\in \mathbb {K} ^{\mathbb {N} }\,:\,Ly=0\}}$${\textstyle \{y^{(1)},y^{(2)},\dots ,y^{(m)}\}}$${\textstyle\ker L}$${\textstyle c_{1}y^{(1)}+\dots +c_{m}y^{(m)}}$${\textstyle c_{1},\dots,c_{m}\in \mathbb {K} }$${\textstyle Ly=0}$${\textstyle {\tilde {y}}}$${\textstyle Ly=f}$${\textstyle L{\tilde {y}}=f}$${\textstyle c_{1}y^{(1)}+\dots +c_{m}y^{(m)}+{\tilde {y}}}$

A finales de los años 1980, Sergei A. Abramov describió un algoritmo que encuentra la solución polinómica general de una ecuación de recurrencia, es decir , con un lado derecho polinómico . Él (y unos años más tarde Marko Petkovšek ) dieron un límite de grado para las soluciones polinómicas. De esta manera, el problema puede resolverse simplemente considerando un sistema de ecuaciones lineales . ^{[2] [3] [4]} En 1995, Abramov, Bronstein y Petkovšek demostraron que el caso polinómico puede resolverse de manera más eficiente considerando la solución de la serie de potencias de la ecuación de recurrencia en una base de potencia específica (es decir, no la base ordinaria ). ^[5]${\textstyle y(n)\in \mathbb {K} [n]}$${\textstyle f(n)\in \mathbb {K} [n]}$${\textstyle (x^{n})_{n\in \mathbb {N} }}$

Los otros algoritmos para encontrar soluciones más generales (por ejemplo, soluciones racionales o hipergeométricas) también se basan en algoritmos que calculan soluciones polinomiales.

En 1989, Sergei A. Abramov demostró que una solución racional general, es decir , con un lado derecho polinomial , se puede encontrar utilizando la noción de denominador universal. Un denominador universal es un polinomio tal que el denominador de cada solución racional divide a . Abramov mostró cómo este denominador universal se puede calcular utilizando únicamente el primer y el último coeficiente polinomial y . Sustituyendo este denominador universal por el denominador desconocido de todas las soluciones racionales se puede encontrar calculando todas las soluciones polinomiales de una ecuación transformada. ^[6]${\textstyle y(n)\in \mathbb {K} (n)}$${\textstyle f(n)\in \mathbb {K} [n]}$${\textstyle u}$${\textstyle u}$${\textstyle p_{0}}$${\textstyle p_{r}}$${\estilo de visualización y}$

Una sucesión se denomina hipergeométrica si el cociente de dos términos consecutivos es una función racional en , es decir . Este es el caso si y solo si la sucesión es la solución de una ecuación de recurrencia de primer orden con coeficientes polinómicos. El conjunto de sucesiones hipergeométricas no es un subespacio del espacio de sucesiones ya que no es cerrado bajo la adición. ${\textstyle y(n)}$${\estilo de visualización n}$${\textstyle y(n+1)/y(n)\in \mathbb {K} (n)}$

En 1992, Marko Petkovšek presentó un algoritmo para obtener la solución hipergeométrica general de una ecuación de recurrencia donde el lado derecho es la suma de secuencias hipergeométricas. El algoritmo utiliza la forma normal de Gosper-Petkovšek de una función racional. Con esta representación específica, nuevamente es suficiente considerar soluciones polinómicas de una ecuación transformada. ^[3]${\estilo de visualización f}$

Un enfoque diferente y más eficiente se debe a Mark van Hoeij. Considerando las raíces del primer y último coeficiente polinomial y – llamadas singularidades – se puede construir una solución paso a paso haciendo uso del hecho de que cada secuencia hipergeométrica tiene una representación de la forma para algunos con para y . Aquí denota la función Gamma y el cierre algebraico del cuerpo . Entonces tienen que ser singularidades de la ecuación (es decir, raíces de o ). Además, se pueden calcular límites para los exponentes . Para valores fijos es posible hacer un ansatz que dé candidatos para . Para un valor específico se puede hacer de nuevo un ansatz para obtener la función racional mediante el algoritmo de Abramov. Considerando todas las posibilidades se obtiene la solución general de la ecuación de recurrencia. ^{[7] [8]}${\textstyle p_{0}}$${\textstyle p_{r}}$${\textstyle y(n)}$$${\displaystyle y(n)=c\,r(n)\,z^{n}\,\Gamma (n-\xi _{1})^{e_{1}}\Gamma (n-\xi _{2})^{e_{2}}\cdots \Gamma (n-\xi _{s})^{e_{s}}}$$${\textstyle c\in \mathbb {K} ,z\in {\overline {\mathbb {K} }},s\in \mathbb {N} ,r(n)\in {\overline {\mathbb {K } }}(n),\xi _{1},\dots ,\xi _{s}\in {\overline {\mathbb {K} }}}$${\textstyle \xi _{i}-\xi _{j}\notin \mathbb {Z} }$${\textstyle i\neq j}$${\textstyle e_ {1},\dots,e_ {s}\in \mathbb {Z}}$${\textstyle \Gamma (n)}$${\textstyle {\overline {\mathbb {K} }}}$${\textstyle \mathbb {K}}$${\textstyle \xi _{1},\dots ,\xi _{s}}$${\textstyle p_{0}}$${\textstyle p_{r}}$${\textstyle e_{i}}$${\textstyle \xi _{1},\dots ,\xi _{s},e_{1},\dots ,e_{s}}$${\textstyle z}$${\textstyle z}$${\textstyle r(n)}$

Una secuencia se denomina d'Alembertiana si para algunas secuencias hipergeométricas y significa que donde denota el operador de diferencia, es decir . Este es el caso si y solo si hay operadores de recurrencia lineal de primer orden con coeficientes racionales tales que . ^[4]${\displaystyle y}$${\textstyle y=h_{1}\sum h_{2}\sum \cdots \sum h_{k}}$${\textstyle h_{1},\dots ,h_{k}}$${\textstyle y=\sum x}$${\textstyle \Delta y=x}$${\textstyle \Delta }$${\textstyle \Delta y=Ny-y=y(n+1)-y(n)}$${\textstyle L_{1},\dots ,L_{k}}$${\textstyle L_{k}\cdots L_{1}y=0}$

1994 Abramov y Petkovšek describieron un algoritmo que calcula la solución d'Alembertiana general de una ecuación de recurrencia. Este algoritmo calcula soluciones hipergeométricas y reduce el orden de la ecuación de recurrencia de forma recursiva. ^[9]

El número de matrices de permutación con signo de tamaño se puede describir mediante la secuencia . Una matriz de permutación con signo es una matriz cuadrada que tiene exactamente una entrada distinta de cero en cada fila y en cada columna. Las entradas distintas de cero pueden ser . La secuencia está determinada por la ecuación de recurrencia lineal con coeficientes polinómicos y los valores iniciales . Aplicando un algoritmo para encontrar soluciones hipergeométricas se puede encontrar la solución hipergeométrica general para alguna constante . Además, considerando los valores iniciales, la secuencia describe el número de matrices de permutación con signo. ^[10]${\displaystyle n\times n}$ ${\textstyle y(n)\in \mathbb {Q} ^{\mathbb {N} }}$${\textstyle \pm 1}$$${\displaystyle y(n)=4(n-1)^{2}\,y(n-2)+2\,y(n-1)}$$${\textstyle y(0)=1,y(1)=2}$$${\displaystyle y(n)=c\,2^{n}n!}$$${\textstyle c}$${\textstyle y(n)=2^{n}n!}$

El número de involuciones de un conjunto con elementos viene dado por la ecuación de recurrencia. Aplicando por ejemplo el algoritmo de Petkovšek es posible ver que no existe una solución polinómica, racional o hipergeométrica para esta ecuación de recurrencia. ^[4]${\textstyle y(n)}$${\textstyle n}$$${\displaystyle y(n)=(n-1)\,y(n-2)+y(n-1).}$$

Una función se denomina hipergeométrica si donde denota las funciones racionales en y . Una suma hipergeométrica es una suma finita de la forma donde es hipergeométrica. El algoritmo telescópico creativo de Zeilberger puede transformar dicha suma hipergeométrica en una ecuación de recurrencia con coeficientes polinómicos. Esta ecuación puede luego resolverse para obtener, por ejemplo, una combinación lineal de soluciones hipergeométricas que se denomina solución en forma cerrada de . ^[4]${\textstyle F(n,k)}$${\textstyle F(n,k+1)/F(n,k),F(n+1,k)/F(n,k)\in \mathbb {K} (n,k)}$${\textstyle \mathbb {K} (n,k)}$${\textstyle n}$${\textstyle k}$${\textstyle f(n)=\sum _{k}F(n,k)}$${\textstyle F(n,k)}$${\textstyle f}$