Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Guessing Linear Recurrence Relations of Sequence Tuples and P-recursive Sequences with Linear Algebra

Jérémy Berthomieu 1 Jean-Charles Faugère 1 
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Jérémy Berthomieu Connect in order to contact the contributor
Submitted on : Wednesday, May 11, 2016 - 9:52:18 AM
Last modification on : Thursday, June 23, 2022 - 10:10:43 AM
Long-term archiving on: : Wednesday, November 16, 2016 - 12:33:36 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Jérémy Berthomieu, Jean-Charles Faugère. Guessing Linear Recurrence Relations of Sequence Tuples and P-recursive Sequences with Linear Algebra. 41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, ON, Canada. pp.95-102, ⟨10.1145/2930889.2930926⟩. ⟨hal-01314266⟩



Record views


Files downloads