Skip to Main content Skip to Navigation
Journal articles

On the Connection Between Ritt Characteristic Sets and Buchberger–Gröbner Bases

Dongming Wang 1
1 PolSys - Polynomial Systems
Inria de Paris, LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : For any polynomial ideal I, let the minimal triangular set contained in the reduced Buchberger–Gröbner basis of I with respect to the purely lexicographical term order be called the W-characteristic set of I. In this paper, we establish a strong connection between Ritt’s characteristic sets and Buchberger’s Gröbner bases of polynomial ideals by showing that the W-characteristic set C of I is a Ritt characteristic set of I whenever C is an ascending set, and a Ritt characteristic set of I can always be computed from C with simple pseudo-division when C is regular. We also prove that under certain variable ordering, either the W-characteristic set of I is normal, or irregularity occurs for the jth, but not the (j+1)th, elimination ideal of I for some j. In the latter case, we provide explicit pseudo-divisibility relations, which lead to nontrivial factorizations of certain polynomials in the Buchberger–Gröbner basis and thus reveal the structure of such polynomials. The pseudo-divisibility relations may be used to devise an algorithm to decompose arbitrary polynomial sets into normal triangular sets based on Buchberger–Gröbner bases computation.
Document type :
Journal articles
Complete list of metadata
Contributor : Dongming Wang <>
Submitted on : Saturday, November 19, 2016 - 4:37:47 PM
Last modification on : Friday, January 8, 2021 - 5:44:01 PM

Links full text



Dongming Wang. On the Connection Between Ritt Characteristic Sets and Buchberger–Gröbner Bases. Mathematics in Computer Science, Springer, 2016, 10 (4), pp.479-492. ⟨10.1007/s11786-016-0279-8⟩. ⟨hal-01399579⟩



Record views