Dependencies

Test

Fix a monomial order and let \(G = \left\{ g_1, \ldots , g_t\right\} \subseteq k[x_1, \ldots , x_n]\). Given \(f \in k[x_1, \ldots , x_n]\), we say that \(f\) reduces to zero modulo \(G\), written \(f \xrightarrow {G} 0\), if \(f\) has a standard representation

which means that whenever \(A_ig_i \neq 0\), we have

Let \(G = \{ g_1, \dots , g_t\} \) be a Gröbner basis for an ideal \(I \subseteq k[x_1, \dots , x_n]\) (with respect to a given monomial order \({\gt}\)) and let \(f \in k[x_1, \dots , x_n]\). Then \(f \in I\) if and only if the remainder on division of \(f\) by \(G\) is zero.

Let \(\preceq \) be a well-partial-order on \(M\). Then every non-empty subset \(N\) of \(M\) has a unique minimal finite basis \(B\), i.e., a finite basis \(B\) such that \(B \subseteq C\) for all other bases \(C\) of \(N\). \(B\) consists of all minimal elements of \(N\).

Every well-quasi-order is well-founded.

Let \((M,\le )\) be a preordered set. Define an equivalence relation

We write \([a]\) for the equivalence class of \(a\), and denote the quotient by

Fix a monomial order \({\gt}\) on the polynomial ring \(k[x_1, \dots , x_n]\). A finite subset \(G = \{ g_1, \dots , g_t\} \) of an ideal \(I \subseteq k[x_1, \dots , x_n]\) different from \(\{ 0\} \) is said to be a Gröbner basis (or standard basis) for \(I\) if the ideal generated by the leading terms of the elements in \(G\) is equal to the ideal generated by the leading terms of all elements in \(I\). That is,

where \(\operatorname {LT}(I) = \{ \operatorname {LT}(f) \mid f \in I \setminus \{ 0\} \} \). Using the convention that \(\langle \emptyset \rangle = \{ 0\} \), we define the empty set \(\emptyset \) to be the Gröbner basis of the zero ideal \(\{ 0\} \).

Let \(I\subseteq k[x_1,\dots ,x_n]\) be an ideal other than \(\{ 0\} \), and fix a monomial ordering on \(k[x_1,\dots ,x_n]\). Then:

1. We denote by

   \[ \mathrm{LT}(I) = \{ \, c\, x^\alpha \mid \exists \, f\in I\setminus \{ 0\} \text{ with }\mathrm{LT}(f)=c\, x^\alpha \} . \]

2. We denote by \(\langle \mathrm{LT}(I)\rangle \) the ideal generated by the elements of \(\mathrm{LT}(I)\).

Let \(N\subseteq M\). An element \(b\in N\) is called minimal in \(N\) if

We denote by

the set of all minimal elements of \(N\). The min–classes of \(N\) are then

Let \(r\) be a relation on \(M\). Then \(r\) is called

1. reflexive if \(\Delta (M) \subseteq r\),

2. symmetric if \(r \subseteq r^{-1}\),

3. transitive if \(r \circ r \subseteq r\),

4. antisymmetric if \(r \cap r^{-1} \subseteq \Delta (M)\),

5. connex if \(r \cup r^{-1} = M \times M\),

6. irreflexive if \(\Delta (M) \cap r = \emptyset \),

7. strictly antisymmetric if \(r \cap r^{-1} = \emptyset \),

8. an equivalence relation on \(M\) if \(r\) is reflexive, symmetric, and transitive,

9. a quasi-order (preorder) on \(M\) if \(r\) is reflexive and transitive,

10. a partial order on \(M\) if \(r\) is reflexive, transitive and antisymmetric,

11. a (linear) order on \(M\) if \(r\) is a connex partial order on \(M\), and

12. a linear quasi-order on \(M\) if \(r\) is a connex quasi-order on \(M\).

We will write \(\overline{f}^F\) for the remainder(normalform) on division of \(f\) by the ordered \(s\)-tuple

If \(F\) is a Gröbner basis for the ideal \(\langle f_1,\dots ,f_s\rangle \), then by Proposition 1 we may regard \(F\) as a set (without any particular order).

Let \(f,g\in k[x_1,\dots ,x_n]\) be nonzero polynomials.

1. If \(\operatorname {multideg}(f)=\alpha \) and \(\operatorname {multideg}(g)=\beta \), then let

   \[ \gamma = (\gamma _1,\dots ,\gamma _n), \quad \gamma _i = \max (\alpha _i,\beta _i) \quad \text{for each }i. \]

   We call \(x^\gamma \) the least common multiple of \(\mathrm{LM}(f)\) and \(\mathrm{LM}(g)\), written

   \[ x^\gamma \; =\; \mathrm{lcm}\bigl(\mathrm{LM}(f),\, \mathrm{LM}(g)\bigr). \]

2. The \(S\)-polynomial of \(f\) and \(g\) is the combination

   \[ S(f,g) \; =\; \frac{x^\gamma }{\mathrm{LT}(f)}\, f \; -\; \frac{x^\gamma }{\mathrm{LT}(g)}\, g. \]

Let \(r\) be a relation on \(M\) with strict part \(r_s\), and let \(N \subseteq M\).

1. Then an element \(a\) of \(N\) is called \(r\)-minimal (\(r\)-maximal) in \(N\) if there is no \(b \in N\) with \(b \, r_s \, a\) (with \(a \, r_s \, b\)). For \(N = M\) the reference to \(N\) is omitted.

2. A strictly descending (strictly ascending) \(r\)-chain in \(M\) is an infinite sequence \(\{ a_n\} _{n \in \mathbb {N}}\) of elements of \(M\) such that \(a_{n+1} \, r_s \, a_n\) (such that \(a_n \, r_s \, a_{n+1}\)) for all \(n \in \mathbb {N}\).

3. The relation \(r\) is called well-founded (noetherian) if every non-empty subset \(N\) of \(M\) has an \(r\)-minimal (an \(r\)-maximal) element. \(r\) is a well-order on \(M\) if \(r\) is a well-founded linear order on \(M\).

Let \(\preceq \) be a quasi-order on \(M\) and let \(N \subseteq M\). Then a subset \(B\) of \(N\) is called a Dickson basis, or simply basis of \(N\) w.r.t. \(\preceq \), if for every \(a \in N\) there exists some \(b \in B\) with \(b \preceq a\).

1. We say that \(\preceq \) has the Dickson property, or is a well-quasi-order(wqo), if every subset \(N\) of \(M\) has a finite basis w.r.t. \(\preceq \).

2. A well partial order, or a wpo, is a wqo that is a proper ordering relation, i.e., it is antisymmetric.

Suppose we have a sum \(\sum _{i=1}^s p_i,\) where \(\operatorname {multideg}(p_i)=\delta \in \mathbb Z_{\ge 0}^n\) for all \(i\). If \(\operatorname {multideg}\Bigl(\sum _{i=1}^s p_i\Bigr){\lt}\delta ,\) then \(\sum _{i=1}^s p_i\) is a linear combination, with coefficients in \(k\), of the \(S\)-polynomials \(S(p_j,p_l)\quad \text{for }1\le j,\, l\le s\). Furthermore, each \(S(p_j,p_l)\) has multidegree \({\lt}\delta \).

Let \(G\) be a Gröbner basis of \(I \subseteq k[x_1, \ldots , x_n]\). Let \(p \in G\) be a polynomial such that \(\operatorname {LT}(p) \in \langle \operatorname {LT}(G \setminus \{ p\} ) \rangle .\) Then \(G \setminus \{ p\} \) is also a Gröbner basis for \(I\).

Let \(I = \langle x^\alpha \mid \alpha \in A \rangle \) be a monomial ideal. Then a monomial \(x^\beta \) lies in \(I\) if and only if \(x^\beta \) is divisible by \(x^\alpha \) for some \(\alpha \in A\).

Let \(I \subseteq k[x_1,\dots ,x_n]\) be an ideal and let \(G = \{ g_1,\dots ,g_t\} \) be a Gröbner basis for \(I\). Then given \(f \in k[x_1,\dots ,x_n]\) there is a unique \(r \in k[x_1,\dots ,x_n]\) with the following two properties:

1. No term of \(r\) is divisible by any of \(\mathrm{LT}(g_1),\dots ,\mathrm{LT}(g_t)\).

2. There is \(g\in I\) such that \(f = g + r\).

In particular, \(r\) is the remainder on division of \(f\) by \(G\) no matter how the elements of \(G\) are listed when using the division algorithm.

Let \(\preceq \) be a well- quasi-order on \(M\), and let \(\{ a_n\} _{n \in \mathbb {N}}\) be a sequence of elements of \(M\). Then there exists a strictly ascending sequence \(\{ n_i\} _{i \in \mathbb {N}}\) of natural numbers such that \(a_{n_i} \preceq a_{n_j}\) for all \(i {\lt} j\).

Let \(\preceq \) be a quasi-order on \(M\) with associated equivalence relation \(\sim \). Then the following are equivalent:

1. \(\preceq \) is a well-quasi-order.

2. Whenever \(\{ a_n\} _{n \in \mathbb {N}}\) is a sequence of elements of \(M\), then there exist \(i {\lt} j\) with \(a_i \preceq a_j\).

3. For every nonempty subset \(N\) of \(M\), the number of min-classes in \(N\) is finite and non-zero.

Let \(I\) be a polynomial ideal in \(k[x_1, \dots , x_n]\). Then a basis \(G = \{ g_1, \dots , g_t\} \) of \(I\) is a Gröbner basis for \(I\) (with respect to a given monomial order \({\gt}\)) if and only if for all pairs \(i \neq j\), the remainder on division of the \(S\)-polynomial \(S(g_i, g_j)\) by \(G\) (listed in some order) is zero.

Let \((\mathbb {N}^n, \le ')\) be the direct product of \(n\) copies of the natural numbers \((\mathbb {N}, \le )\) with their natural ordering. Then \((\mathbb {N}^n, \le ')\) is a Dickson partially ordered set. More explicitly, every subset \(S \subseteq \mathbb {N}^n\) has a finite subset \(B\) such that for every \((m_1, \dots , m_n) \in S\), there exists \((k_1, \dots , k_n) \in B\) with

Let \(I = \langle x^{\alpha } | \alpha \in A \rangle \subseteq k[x_1, \ldots , x_n]\) be a monomial ideal. Then \(I\) can be written in the form \(I = \langle x^{\alpha (1)}, \ldots , {\alpha (s)} \rangle \), where \(\alpha (1), \ldots , \alpha (s) \in A\). In particular, \(I\) has a finite basis.

Let \(P\) be a subset of \(K[X]\) and \(f\in K[X]\). Then there exists a normal form \(g\in K[X]\) of \(f\) modulo \(P\) and a family \(\mathcal{F}=\{ q_{p}\} _{p\in P}\) of elements of \(K[X]\) with

If \(P\) is finite, the ground field is computable, and the term order on \(T\) is decidable, then \(g\) and \(\{ q_{p}\} _{p\in P}\) can be computed from \(f\) and \(P\).

Let \(I \subseteq k[x_1, \ldots , x_n]\) be an ideal different from \(\{ 0 \} \).

1. \(\langle \operatorname {LT}(I)\rangle \) is a monomial ideal.

2. There are \(g_1, \ldots , g_t \in I\) such that \(\langle \operatorname {LT}(I)\rangle = \langle \operatorname {LT}(g_1), \ldots , \operatorname {LT}(g_t)\rangle \).