Guessing Gröbner bases of structured ideals of relations of sequences. (July 2022)

• Record Type: Journal Article
• Authors: Berthomieu, Jérémy; Safey El Din, Mohab
• Is Part Of: Journal of symbolic computation. Volume 111(2022)
• Page Start: 1
• Page End: 26
• Publication Date: 2022-07
• Subjects: Linear recurrence relations -- Gröbner bases -- Symmetries -- Change of orderings; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2021.11.001
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: Assuming sufficiently many terms of an n -dimensional table defined over a field are given, we aim at guessing the linear recurrence relations with either constant or polynomial coefficients they satisfy. In many applications, the table terms come along with a structure: for instance, they may be zero outside of a cone, they may be built from a Gröbner basis of an ideal invariant under the action of a finite group. Thus, we show how to take advantage of this structure to reduce both the number of table queries and the number of operations in the base field to recover the ideal of relations of the table. In applications like in combinatorics, where all these zero terms make us guess many fake relations, this allows us to drastically reduce these wrong guesses. These algorithms have been implemented and, experimentally, they let us handle examples that we could not manage otherwise. Furthermore, we show which kind of cone and lattice structures are preserved by skew-polynomial multiplication. This allows us to speed the guessing of linear recurrence relations with polynomial coefficients up by computing sparse Gröbner bases or Gröbner bases of an ideal invariant under the action of a finite group in a ring of skew-polynomials.