Recursive structures in involutive bases theory. (September 2023)

• Record Type: Journal Article
• Authors: Hashemi, Amir; Orth, Matthias; Seiler, Werner M.
• Is Part Of: Journal of symbolic computation. Volume 118(2023)
• Page Start: 32
• Page End: 68
• Publication Date: 2023-09
• Subjects: 13P10 -- 13D02 -- 68W30; Involutive bases -- Janet-like bases -- Janet trees -- Pommaret-like bases -- Generic positions -- Schreyer's theorem; 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.2023.01.003
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We study characterisations of involutive bases using a recursion over the variables in the underlying polynomial ring and corresponding completion algorithms. Three key ingredients are (i) an old result by Janet recursively characterising Janet bases for which we provide a new and simpler proof, (ii) the Berkesch–Schreyer variant of Buchberger's algorithm and (iii) a tree representation of sets of terms also known as Janet trees. We start by extending Janet's result to a recursive criterion for minimal Janet bases leading to an algorithm to minimise any given Janet basis. We then extend Janet's result also to Janet-like bases as introduced by Gerdt and Blinkov. Next, we design a novel recursive completion algorithm for Janet bases. We study then the extension of these results to Pommaret bases. It yields a novel recursive characterisation of quasi-stability which we use for deterministically constructing "good" coordinates more efficiently than in previous works. A small modification leads to a novel deterministic algorithm for putting an ideal into Nœther position. Finally, we provide a general theory of involutive-like bases with special emphasis on Pommaret-like bases and study the syzygy theory of Janet-like and Pommaret-like bases.