Computing the algebraic relations of \(C\)-finite sequences and multisequences (Q2517807)

A \(C\)-finite sequence over a field \(K\) is a function \(a:\mathbb{Z}\to K\) satisfying a linear homogeneous recurrence \(c_0a(n)+\cdots+c_sa(n+s)=0\) with \(c_0,\ldots,c_s\in K\) and \(c_0,c_s\not=0\). An algebraic relation over \(K\) among \(r\) \(C\)-finite sequences \(a_1,\ldots,a_r\) over \(K\) is a polynomial \(P(x_1,\ldots,x_r)\in K[x_1,\ldots,x_r]\) such that \(P(a_1(n),\ldots,a_r(n))=0\) for all \(n\in\mathbb{Z}\). All algebraic relations among \(a_1,\ldots,a_r\) form an ideal \(I=I(a_1,\ldots,a_r;K)\) of the ring \(K[x_1,\ldots,x_r]\). The authors present an algorithm for computing generators of \(I\) when \(K\) is the rational field \(\mathbb{Q}\). Combining this with the Gröbner basis method, the authors can determine whether a given sequence can be represented in terms of other given sequences.