Guessing Gröbner bases of structured ideals of relations of sequences (Q2066951)

Linear relations satisfied by the finite subset of terms is a fundamental problem which appears in many applications, as coding theory, combinatorics, sparse linear systems, sparse polynomial interpolation, etc. In one dimension, this problem is efficiently solved by the well-known Berlekamp-Massey algorithm. In the multidimensional case, focusing only on the algorithms used in this article, in [\textit{J. Berthomieu} and \textit{J.-C. Faugère}, in: Proceedings of the 43rd international symposium on symbolic and algebraic computation, ISSAC 2018, New York, NY, USA, July 16--19, 2018. New York, NY: Association for Computing Machinery (ACM). 79--86 (2018; Zbl 1467.13044); J. Symb. Comput. 109, 1--30 (2022; Zbl 1481.68050)], the authors designed an algorithm extending both the Berlekamp-Massey-Sakata and the Scalar-FGLM algorithms using polynomial arithmetic and in [\textit{J. Berthomieu} and \textit{J.-C. Faugère}, in: Proceedings of the 41st international symposium on symbolic and algebraic computation, ISSAC 2016, Waterloo, Canada, July 20--22, 2016. New York, NY: Association for Computing Machinery (ACM). 95--102 (2016; Zbl 1362.13026)], they introduced the Adaptive Scalar-FGLM algorithm for guessing relations with polynomial coefficients, computing the Gröbner basis of an ideal of relations by using just linear algebra techniques. In this paper, variants of the Scalar-FGLM algorithm that guess linear recurrence relations for an n-dimensional table are introduced, taking the table structure into account. Section 2 recalls the Scalar-FGLM and the Adaptive Scalar-FGLM algorithm. In Section 3, the authors first prove that restraining the Scalar-FGLM algorithm to terms of a table lying on a cone makes it compute a sparse Gröbner basis of the ideal of relations of the table (see Theorem 3.2); second, they introduce the Lattice Scalar-FGLM which computes a reduced Gröbner basis of the ideal of relations when terms lie on a lattice (see Theorem 3.4) and as an application, they provide a modification of the Sparse-FGLM algorithm [\textit{J.-C. Faugère} and \textit{C. Mou}, in: Proceedings of the 36th international symposium on symbolic and algebraic computation, ISSAC 2011, San Jose, CA, USA, June 7--11, 2011. New York, NY: Association for Computing Machinery (ACM). 115--122 (2011; Zbl 1323.68596); J. Symb. Comput. 80, Part 3, 538--569 (2017; Zbl 1404.13031)] whenever the ideal is globally invariant under the action of a finite group. Section 4 introduces the Lattice Adaptive Scalar-FGLM algorithm. Finally, experiments are presented in Section 5.