Guessing Linear Recurrence Relations of Sequence Tuples and P-recursive Sequences with Linear Algebra
Résumé
Given several $n$-dimensional sequences, we first present an algorithm
for computing the Gröbner basis of their module of linear recurrence
relations.
A P-recursive sequence $(u_{\mathbf{i}})_{\mathbf{i}\in\mathbb{N}^n}$
satisfies linear recurrence relations with polynomial coefficients in
$\mathbf{i}$, as defined by Stanley in 1980. Calling directly
the aforementioned algorithm on the tuple of
sequences $\left((\mathbf{i}^{\mathbf{j}}\,u_{\mathbf{i}})_{\mathbf{i}\in\mathbb{N}^n}\right)_{\mathbf{j}}$
for retrieving the relations yields redundant relations.
Since the module of relations of a
P-recursive sequence also has an extra structure of a $0$-dimensional right
ideal of an Ore algebra, we design a more efficient algorithm that takes
advantage of this extra structure for
computing the relations.
Finally, we show how to incorporate Gröbner bases computations in an
Ore algebra $\mathbb{K}\langle t_1,\ldots,t_n,x_1,\ldots,x_n\rangle$, with
commutators $x_k\,x_{\ell}-x_{\ell}\,x_k=t_k\,t_{\ell}-t_{\ell}\,t_k=t_k\,x_{\ell}-x_{\ell}\,t_k=0$ for $k\neq\ell$ and
$t_k\,x_k-x_k\,t_k=x_k$, into the algorithm designed for P-recursive
sequences. This allows us to compute faster the Gr\"obner basis of the ideal spanned by the first relations,
such as in \textsc{2D}/\textsc{3D}-space walks examples.
Domaines
Calcul formel [cs.SC]
Origine : Fichiers produits par l'(les) auteur(s)
