The RegularChains library in MAPLE

Abstract

Performing calculations modulo a set of relations is a basic technique in algebra. For instance, computing the inverse of an integer modulo a prime integer or computing the inverse of the complex number 3 + 2<i>t</i> modulo the relation ℓ<sup>2</sup> + 1 = 0. Computing modulo a set <i>S</i> containing more than one relation requires from <i>S</i> to have some mathematical structure. For instance, computing the inverse of <i>p</i> = <i>x</i> + <i>y</i> modulo <i>S</i> = {<i>x</i><sup>2</sup> + <i>y</i> + 1,<i>y</i><sup>2</sup> + <i>x</i> + 1} is difficult unless one realizes that this question is equivalent to computing the inverse of <i>p</i> modulo <i>C</i> = {<i>x</i><sup>4</sup> + 2<i>x</i><sup>2</sup> + <i>x</i> + 2,<i>y</i> + <i>x</i><sup>2</sup> + 1}. Indeed, from there one can simplify <i>p</i> using <i>y</i> = -<i>x</i><sup>2</sup> - 1 leading to <i>q</i> = -<i>x</i><sup>2</sup> + <i>x</i> - 1 and compute the inverse of <i>q</i> modulo <i>x</i><sup>4</sup> + 2<i>x</i><sup>2</sup> + <i>x</i> + 2 (using the extended Euclidean algorithm) leading to -1/2<i>x</i><sup>3</sup> - 1/2<i>x</i>. One commonly used mathematical structure for a set of algebraic relations is that of a <i>Gröbner basis.</i> It is particularly well suited for deciding whether a quantity is null or not modulo a set of relations. For inverse computations, the notion of a <i>regular chain</i> is more adequate. For instance, computing the inverse of <i>p</i> = <i>x</i> + <i>y</i> modulo the set <i>C</i> = {<i>y</i><sup>2</sup> - 2<i>x</i> + 1,<i>x</i><sup>2</sup> - 3<i>x</i> + 2}, which is both a Gröbner basis and a regular chain, is easily answered in this latter point of view. Indeed, it naturally leads to consider the GCD of <i>p</i> and <i>C<inf>y</inf></i> = <i>y</i><sup>2</sup> - 2<i>x</i> + 1 modulo the relation <i>C<inf>x</inf></i> = <i>x</i><sup>2</sup> - 3<i>x</i> + 2 = 0, which is [EQUATION] This shows that <i>p</i> has no inverse if <i>x</i> = 1 and has an inverse (which can be computed and which is -<i>y</i> + 2) if <i>x</i> = 2.