Dependencies

Computes the Characteristic Set of a polynomial list \(l\).

Algorithm:

1. Set \(l_0 = l\).

2. Compute \(BS = BasicSet(l)\).

3. Compute remainders \(RS\) of \(l \setminus BS\) with respect to \(BS\).

4. If \(RS = \emptyset \), \(BS\) is the characteristic set.

5. If not, let \(l = l₀ ++ RS ++ BS\) and go to step 2.

Termination is guaranteed by the well-ordering of orders.

The interface for algorithms computing Basic Sets. Any instance of this class provides a "basicSet" function that computes a minimal ascending set contained in a given list of polynomials.

The initial of a polynomial \(p\) is the initial with respect to its class.

The initial of a polynomial \(p\) with respect to a variable \(i\). It is the coefficient of the highest power of \(x_i\) appearing in \(p\).

The product of initials of a set of polynomials.

A Triangular Set is an Ascending Set if every element is reduced with respect to its predecessors. Here "reduced" is an abstract predicate.

\(CS\) is a characteristic set of \(PS\) if every polynomial in \(PS\), \(0\) is its remainder by \(CS\), and \(Zero(PS) \subseteq Zero(CS)\).

A remainder \(r\) of \(g\) by \(f\) is a polynomial which is reduced with respect to \(f\) and satisfies \(init(f)^s \cdot g = q \cdot f + r\) for some \(s \in \mathbb {N}\) and \(q \in R[X_{\sigma }]\).

A remainder \(r\) of \(g\) by a set \(S\) is a polynomial which is reduced with respect to \(S\) and satisfies \((\prod init(S_i)^{e_i}) \cdot g = \sum q_i \cdot S_i + r\) for some \(\{ e_i\} \) and \(\{ q_i\} \).

A Triangular Set is a Standard Ascending Set if every element is reduced with respect to its predecessors.

A Triangular Set is a Weak Ascending Set if the initial of every element is reduced with respect to its predecessors.

The degree of \(p\) with respect to its class.

The order of a polynomial \(p\) is the pair \((mainVar(p), deg(p))\) ordered lexicographically.

Pseudo-division of \(g\) by \(f\) with respect to \(mainVar(f)\).

Returns a triple containing the exponent, the quotient and the remainder.

Pseudo-division of \(g\) by \(f\) with respect to \(i\).

Returns a triple containing the exponent, the quotient and the remainder.

\(q\) is reduced with respect to \(p\) if the degree of \(q\) in the main variable of \(p\) is strictly less than the main degree of \(p\).

\(q\) is reduced with respect to a polynomial set \(PS\) if it is reduced with respect to all elements of \(PS\).

Pseudo-divides \(g\) successively by elements of \(S\). Typically, this involves dividing by \(S_{l-1}\), then \(S_{l-2}\), ..., down to \(S_0\).

Returns a triple containing the exponents, the quotients and the remainder.

Computes the Standard Basic Set of a list of polynomials.

The algorithm works by:

1. Sort the list and let \(BS = \emptyset \).

2. Pick the first (minimal) element \(B\) in the list.

3. Append \(B\) to the tail of the current basic set \(BS\).

4. Filter the remaining list to keep only elements reduced w.r.t. the new \(BS\) and go to step 2.

"S.takeConcat p" tries to construct a new Triangular Set by taking a prefix of \(S\) and appending \(p\).

• If \(p\) fits naturally at the end of \(S\), it behaves like "S.concat p".

• If \(p\) conflicts with some element in \(S\) (in terms of class order), "takeConcat" finds the first element in \(S\) that has a higher or equal class than \(p\), truncates \(S\) before that element, and appends \(p\).

A Triangular Set is a finite ordered sequence of non-zero polynomials with strictly increasing classes.

The order of a Triangular Set is a lexicographic sequence of orders of its polynomials. More intuitively, \(S {\lt} T\) if one of the following two occurs:

• There exists some \(k {\lt} S.length\) such that \(S_0 \sim T_0, S_1 \sim T_1, ..., S_{k-1} \sim T_{k-1}\), while \(S_k {\lt} T_k\).

• \(S.length {\gt} T.length\) and \(\forall i {\lt} T.length, S_i \sim T_i\).

Computes the Weak Basic Set of a list of polynomials.

Difference from Standard: The filter condition includes \(mainVar(p) {\gt} mainVar(B)\).

Decomposes the zero set of a polynomial list into a union of zero sets of triangular sets. The algorithm recursively computes the characteristic set \(CS\) and adds branches for the initials of \(CS\).

The algorithm computes a minimal standard ascending set contained in the input list.

The set of Triangular Sets is well-founded under the lexicographic order ordering. This guarantees the termination of the Characteristic Set Algorithm.

The algorithm computes a minimal weak ascending set contained in the input list.

\(deg_i(p + q) {\lt} deg_i(p)\) if \(deg_i(p) = deg_i(q)\) and \(init_i(p) + init_i(q) = 0\).

\(\forall i j, deg_j(init_i(p)) \le deg_j(p)\)

\(deg_i(init_i(p)) = 0\).

The remainder \(r\) of \(g\) by \(f\) satisfies \(deg_i(r) \le deg_i(g)\) if \(deg_i(f) = 0\)

\(deg_i(r) {\lt} deg_i(g)\) where \(r\) is the remainder of \(g\) by \(f\) w.r.t. \(i\) if \(deg_i(f) \ne 0\).

\(init_i(p)\) is reduced w.r.t. \(q\) if \(p\) is reduced w.r.t. to \(q\).

\(init_i(p)\) is reduced w.r.t. \(p\) for non-constant \(p\).

\(init_i(p) = p\) if \(deg_i(p) = 0\) (i.e. \(x_i\) does not appear in \(p\)).

\(init_i(init_i(p)) = init_i(p)\).

\(mainVar(init(p)) {\lt} mainVar(p)\) for non-constant \(p\).

\(mainVar(p) {\lt} mainVar(q)\) if \(p ≤ q\) and \(q\) is reduced with respect to \(p\).

If \(mainVar(p) = mainVar(q)\), then \(q\) is reduced with respect to \(p\) if and only if \(q {\lt} p\).

\(q\) is reduced w.r.t. \(p\) if \(mainVar(q) {\lt} mainVar(p)\).

Appending an element which is reduced w.r.t. the basic set of list strictly decreases the order. Crucial for proving termination of characteristic set and zero decomposition algorithms.

The computed characteristic set is an ascending set.

The algorithm computes a valid characteristic set for the input list.

The order of computed characteristic set \(\le \) the order of the input list.

If \(p\) is in \(S\) and \(mainVar(p) \neq \bot \), then \(init(p)\) is in \(S\).

\(p = init_i(p) x_i ^d + q\), where \(deg_i(q) {\lt} d = deg_i(p)\).

\(init_i(p)\) is the leading coefficient when viewing \(p\) as a univariate polynomial in \(x_i\).

\(init_i(p \cdot q) = init_i(p) \cdot init_i(q)\) if there is no zero divisors in the coefficient ring.

The remainder of \(g\) by \(f\) is \(g\) if \(deg_c(g) = 0\) where \(c = mainVar(f)\).

The remainder of \(g\) by \(f\) is \(0\) if \(f\) is a divisor of \(g\).

The remainder \(r\) of \(g\) by \(f\) is reduced with respect to \(f\) and satisfies \(init(f)^s \cdot g = q \cdot f + r\) for some \(s \in \mathbb {N}\) and \(q \in R[X_{\sigma }]\).

The remainder of \(p\) by a set \(S\) is \(0\) if \(p\) is in \(S\).

The remainder \(r\) of \(g\) by a set \(S\) is reduced with respect to \(S\) and satisfies \((\prod S_i^{e_i}) \cdot g = \sum q_i \cdot S_i + r\) for some \(\{ e_i\} \) and \(\{ q_i\} \).

If \(p \neq 0\) and is reduced with respect to \(S\), then modifying \(S\) by appending \(p\) (using "takeConcat") strictly decreases the order of \(S\).

Well-ordering principle (3):

.

Well-ordering principle (2): \(Zero(CS/IP) = Zero(PS/IP)\), where \(IP\) is the initial-product of \(CS\).

Well-ordering principle (1): \(Zero(CS/IP) \subseteq Zero(PS)\), where \(IP\) is the initial-product of \(CS\).

Zero Decomposition Theorem: The zero set of a polynomial system \(PS\) is the union of the zero sets of the triangular systems computed by the algorithm:

.

\(\forall CS \in \mathcal{ZD}(PS), g \in PS\), \(0\) is the remainder of \(g\) by \(CS\).