以下记号 $S$ 均指基环 (默认其是诺特的, 且是交换幺环), $R$ 均指环 $S[x_1,\dots,x_n]$ (自然其是诺特的, 且为交换幺环). 我们约定 $>$ 为 $PP(x_1,\dots,x_n)$ (所有只包含记号 $x_1,\dots,x_n$ 的没有系数的单项式) 上面的一种全序. 满足:

  • $1$ 小于任何其他单项式.
  • 若 $p<q$, 那么 $pt<qt$.

在后文中, 若不加其他说明, 默认 "次数最高的项" 指的是在上述定义的 $<$ 意义下最高次项.

任何满足上述定义的序均满足, 对于任何下降链 $\{p_n\}_{n=1}^\infty\subset PP(x_1,\dots,x_n)$ 即 $p_1\ge p_2\ge\cdots\ge p_n\ge \cdots$, 都存在 $N\in\mathbb N^*$ 使得, $\forall n\ge N,p_n=p_N$.

这说明, 我们总可以取出不满足一个性质的多项式中, 最高次数最小的那个.

对于任意 $S[x_1,\dots,x_n]$ 中的多项式 $f$, 记 $\operatorname{Hterm}(f),\operatorname{Hmono}(f),\operatorname{Hcoef}(f)$ 分别指 $f$ 次数最高的项 (不含系数), 次数最高的项 (包含系数), 次数最高的项的系数.

Gröbner basis

Syzygy 定义

对于 $S$ 模 $M=(x_1,\dots,x_m)$, 其 Syzygy 定义为模同构

$$ \phi:\langle s_1,\dots,s_m\rangle\mapsto s_1x_1+\dots+s_mx_m $$

的 kernel, $\operatorname{ker}(\phi)$, 是一个 $S^m$ 的子模.

Gröbner basis 定义

对于集合 $F\subset R$, 记 $\operatorname{Head}(F)$ 为 $F$ 中所有多项式的 $\operatorname{Hmono}$ 在 $R$ 上生成的理想.

对于理想 $I\subset R$, $G\subset I$ 被叫做 $I$ 的 Gröbner 基, 当且仅当

$$ \operatorname{Head}(G)=\operatorname{Head}(I). $$

讨论 Gröbner 基时均假设 $0\not\in G$.

那么可证此时 $(G)=I$:

若存在 $f\in I\setminus (G), f\neq 0$ 且 $f$ 是能取出的多项式中最高次数最小的, 那么由 $\operatorname{Hmono}(f)\in \operatorname{Head}(I)=\operatorname{Head}(G)$ 可知可用 $G$ 中的多项式对 $\operatorname{Hmono}(f)$ 进行消去, 找到更小的 $f$, 矛盾!

S-polynomial

S-多项式刻画了 Gröbner 基是一组 "最小" 的基, 不能通过这组基去消出最高次数更小的多项式. 其本身还刻画了一组多项式如何作用可以抵消最高项.

对于 $(f_1,\dots,f_r)\subset_f R$, 记

$$ \{\langle s_{i,1}\dots,s_{i,r}\rangle\mid 1\le i\le m\} $$

是 $M=\left(\operatorname{Hcoef}(f_1),\dots,\operatorname{Hcoef}(f_r)\right)$ 的 syzygy 的一组基. 那么这个多项式的集合的 S-polynomial 定义为多项式集合:

$$ \left\{\left.\sum_{i=1}^r\frac{s_{k,i}\operatorname{lcm}\left(\operatorname{Hterm}(f_j),\forall j\right)}{\operatorname{Hterm}(f_i)}f_i\;\;\right|\;\;\forall 1\le k\le m\right\}. $$

Gröbner 基的刻画

TFAE (The following are equivalent):

  • $G$ 是 $(G)$ 的 Gröbner 基
  • $G$ 的任何一个有限子集的任意一个 S-polynomial $h$ 都可以表示为 $h=\sum_{j\in \mathcal J}f_jg_j$, 其中 $\mathcal J$ 有限, $\operatorname{Hterm}(f_j)\operatorname{Hterm}(g_j)\le \operatorname{Hterm}(h)$.

事实上, 第二条中 $h$ 可以换成任意一个 $I$ 中的多项式. 定义 G.h. (Gröbner Head reduction) 操作如下:

对于 $h$, 若 $\operatorname{Hmono}(h)\in \operatorname{Head}(\{g\in G\mid \operatorname{Hterm}(g)\le \operatorname{Hterm}(h)\})$ (这等价于 $\operatorname{Hcoef}(h)\in (\{\operatorname{Hcoef}(g)\in G\mid \operatorname{Hterm}(g)\le \operatorname{Hterm}(h)\})$ ). 那么通过用 $G$ 中最高项 $\le h$ 的那些多项式来消去 $h$ 的最高次项, 然后返回.

显然 $h$ 可以表示为如上的形式, 当且仅当 $h$ 可以通过某些 G.h 操作变成 $0$. 下证对 $h$ 任意进行 G.h. 操作 (只可能进行有限次) 后 $h$ 总能变为 $0$.

假设 $h$ 当前不能进行 G.h. 操作且不为 $0$, 那么由 $\operatorname{Hmono}(h)=\operatorname{Head}(G)$, 那么设 $\operatorname{Hmono}(h)=\sum_{j\in\mathcal J}f_j\operatorname{Hmono}(g_j)$. 设 $f_j^\prime$ 为 $f_j$ 中满足乘上 $\operatorname{Hterm}(g_j)$ 后 $\le \operatorname{Hterm}(h)$ 的那些项, 则 $f_j\operatorname{Hmono}(g_j)$ 中 $\le \operatorname{Hterm}(g)$ 的项即为 $f_j^\prime \operatorname{Hmono}(g_j)$. 故 $\operatorname{Hmono}(h)=\sum_{j\in\mathcal J}f_j^\prime\operatorname{Hmono}(g_j)$. 删除 $g_j$ 中那些最高次项 $>\operatorname{Hterm}(h)$ 的即可 (因为此时对应的 $f_j^\prime=0$). $h$ 依然能进行 G.h., 矛盾!

故对 $h$ 任意做 G.h. 操作总能得到 $0$. 从而有限子集的 S-polynomial ($I$ 中多项式) 可以表示为上述形式.

下证 2 推 1. 只需证 2 也可推出对任意 $h$ 任意做 G.h. 操作总能得到 $0$ 即可. 此时若存在不能进行 G.h. 的多项式 $h\in I$. 设 $h=\sum_{j\in \mathcal J} f_jg_j$. 那么 $\max\{\operatorname{Hterm}(f_j)\operatorname{Hterm}(g_j)\}=M>\operatorname{Hterm}(h)$. 设这种表示方式是使得 $M$ 最小的表示方式. 设 $\mathcal J_0\subset \mathcal J$ 为所有满足 $\operatorname{Hterm}(f_j)\operatorname{Hterm}(g_j)=M$ 的 $j$ 的集合. 则一定存在 $a\in S, t\in PP(x_1,\dots,x_n)$ 使得存在 $\mathcal J_0$ 对应的 S-polynomial $q=\sum_{j\in\mathcal{J}_0}r_jg_j$ ($r_j$ 是单项式) 满足

$$ \operatorname{Hmono}(f_j)=(a\cdot t)\cdot r_j=(a\cdot t)\cdot \frac{s_{k,j}\operatorname{lcm}\left(\operatorname{Hterm}(g_l),\forall l\in {\mathcal J_0}\right)}{\operatorname{Hterm}(g_j)}\left(\text{这里 $s_{k,j}$ 是该 S-poly 对应的 syzygy 的基}\right) $$

这是因为 S-polynomial 涵盖了所有 $g_j$ 消去高位的方式. 那么此时

$$ \sum_{j\in \mathcal{J}\setminus \mathcal J_0} f_jg_j+\sum_{j\in \mathcal J_0}\left(f_j-at\cdot r_j\right)g_j+at\cdot q $$

是一种 $M$ 更小的表示方式. (因为 $\operatorname{Hterm}(q)<\operatorname{Hterm}(r_j)\operatorname{Hterm}(g_j)=\frac{M}{at}$, 而 $q$ 作为 S-polynomial 由条件得 $q$ 可写为 $\sum_{i\in \mathcal{J}_1} \tilde f_ig_i$, 其中 $\operatorname{Hterm}(\tilde f_i)\operatorname{Hterm}(g_i)\le \operatorname{Hterm}(q)$). 从而矛盾!

而可以不断任意做 G.h. 变成 $0$ 显然可以说明任意 $I$ 中多项式的 $\operatorname{Hmono}$ 都在 $\operatorname{Head}(G)$ 中.

推论 : 对于任意集合 $G$, 若多项式 $h\in (G)$ 不能在用 $G$ 消去的意义下再进行 G.h. 操作了, 那么 $\operatorname{Hmono}(h)\not\in \operatorname{Head}(G)$.

考虑 $I=\{q\in (G)\mid \operatorname{Hmono}(q)\in \operatorname{Head}(G)\}$. 那么它显然是一个理想, 且 $G$ 是 $I$ 的一组 Gröbner 基. 故 $h\not\in I$, 否则 $h$ 可以进行 G.h. 操作.

Computability & Detachability & Syzygy-Solvability

我们称一个环 $S$ 是 Computable 的, 当且仅当

加法, 乘法, 取负都有算法可以计算. 特别的, 若 $S$ 是域, 那么取逆也是可以计算的.

我们称一个环 $S$ 是 Detachable 的, 当且仅当:

对于任意 $\{x_1,\dots,x_n\}\subset_f S$, 记他们生成的理想为 $I$. 任意给定一个元素 $y\in S$, 存在一个算法, 可以计算

  • 判断 $y\in I$.
  • 若 $y\in I$, 进一步给出 $t_1,\dots,t_n\in S$ 使得 $\sum t_ix_i=y$.

我们称一个环 $S$ 是 Syzygy-Solvable 的, 当且仅当:

对于任意 $\{s_1,\dots,s_r\}\subset_f S$, 存在一个算法, 可以计算:

  • 一组 $(s_1,\dots,s_r)$ 对应的 syzygy 的基 $\{\langle t_{i,1},\dots,t_{i,r}\rangle \mid 1\le i\le m\}$.
  • 对于任意满足 $\sum p_is_i=0$ 的 $\langle p_1,\dots,p_r\rangle$, 可以计算出 $c_1,\dots,c_m\in S$ 使得 $p_i=\sum_{j=1}^mc_jt_{j,i}(\forall i)$.

一个环 $S$ 是强可计算的 (Strongly-Computable), 当且仅当 $S$ 是诺特的, 且满足以上三条性质.

我们接下来说明, 若 $S$ 是强可计算的, 那么 $R$ 也是强可计算的.

诺特性由 Hillbert 基定理给出, 可计算性也显然.

$R$ 的 Detachability

若可计算 $(f_1,\dots,f_r)$ 的一组 Gröbner 基 $G$, 以及 $G$ 中每个元素 $g_i$ 在 $f_j$ 下的表示 $g_i=\sum_{j=1}^r c_{i,j}f_j$, 那么判断 $h\in (f_1,\dots,f_r)$ 及计算表示是容易的:

对 $h$ 不断任意做 G.h. 操作. 根据前面证明的结果, $h\in (f_1,\dots,f_r)$ 当且仅当最后能得到 $0$.

这里 G.h. 操作做消去时用到了判断 $\operatorname{Hcoef}(h)\in (\{\operatorname{Hcoef}(g)\mid g\in G,\operatorname{Hterm}(g)\le \operatorname{Hterm}(h)\})$ 及计算它的表示, 即为基环 $S$ 上的 Detachability.

若 $h\in (f_1,\dots,f_r)$, 那么计算表示也是容易的. 把每一次消去的结果拼起来即得 $h$ 在 $G$ 下的表示. 利用 $G$ 在 $f$ 下的表示即得 $h$ 在 $f$ 下的表示.

那么唯一的问题变成了如何从 $\{f_1,\dots,f_r\}$ 开始得到一组 $\left(f_1,\dots,f_r\right)$ 的 Gröbner 基.

先给出计算 Gröbner 基的算法:

初始时刻令 $X=\{f_i\}$, 即当前的基集合.

循环以下操作直到没有新的元素加入 $X$ 中: 遍历 $X$ 的所有子集 $F$, 枚举 $F$ 对应的所有 S-polynomial $h_i$. 对 $h_i$ 任意做 G.h. 操作 (在用 $X$ 消去的意义下), 若最后 $h_i$ 不能变为 $0$, 那么把 $h_i$ 加入 $X$.

这里需要求 S-polynomial, 所以用到了基环 $S$ 上的 Syzygy-Solvability.

易见若该算法终止, 那么该算法最后得到的 $X$ 为一组 Gröbner 基. (已证明的 Gröbner 基的等价条件). 下说明该算法会在有限时间内终止.

设 $X,X^\prime$ 分别为一次循环前后的基集合. 那么由 Gröbner 基条件等价性那里的推论有

$$ \operatorname{Head}(X)\subsetneq \operatorname{Head}(X^\prime). $$

由 Hillbert 基定理, 诺特性等价于任意理想升链是稳定的, 故在有限时间后不能再产生新的加入 $X$ 中的多项式.

$R$ 的 Syzygy-Solvability

问题: 给定 $(f_1,\dots,f_r)\subset_f R$, 求出一组基 $\{t_i=\langle t_{i,1}\dots,t_{i,r}\rangle\mid 1\le i\le m\}$, 使得

$$ p=\langle p_1,\dots,p_r\rangle,\sum_{j=1}^r p_jf_j=0\iff \exists c_1,\dots,c_m\in R,p=\sum_{i=1}^m c_it_i. $$

需要一个算法给出具体的 $t_i$, 以及在给定 $t_i$ 的情况下给出 $c_i$. (判断是否在 syzygy 里面是平凡的).

以下分两种情况给出求解 syzygy 的算法, 其中 $$

$G$ 是 $(f_1,\dots,f_r)$ 的 Gröbner 基

下直接给出一组基的构造方法: 对于任意 $F\subset G$ 且 $|F|\ge 2$, 设

$$ h_{F,i}=\sum_{j=1}^r\frac{s_{F,i,j}\operatorname{lcm}(\operatorname{Hterm}(f_l),\forall 1\le l\le r)}{\operatorname{Hterm}(f_j)}f_j $$

是 $F$ 对应的第 $i$ 个 S-polynomial. 另外, 通过 G.h. 操作, $h_{F,i}$ 也可以变为 $0$. 即存在 $g_{F,i,1},\dots,g_{F,i,r}$ 满足

$$ \sum_{j=1}^rg_{F,i,j}f_j=h_{F,i},\quad\forall 1\le j\le r,\operatorname{Hterm}(g_{F,i,j})\operatorname{Hterm}(f_j)\le \operatorname{Hterm}(h_{F,i}). $$

把 $t_{F,i}=\left\langle \operatorname{Hterm}(g_{F,i,j})- \operatorname{Hterm}\left(\frac{s_{F,i,j}\operatorname{lcm}(\operatorname{Hterm}(f_l),\forall 1\le l\le r)}{\operatorname{Hterm}(f_j)}\right),1\le j\le r\right\rangle$ 作为一个基加入 syzygy 的基里面. (易见这是 syzygy 的一部分).

注意到 $\operatorname{Hterm}(g_{F,i,j})\lneq \operatorname{Hterm}\left(\frac{s_{F,i,j}\gcd(\operatorname{Hterm}(f_l),\forall 1\le l\le r)}{\operatorname{Hterm}(f_j)}\right)$, 故 $t_{F,i}$ 是一个各分量均不为 $0$ 的基.

记 $\{\ \overline t_{k}\mid 1\le k\le l\}=\{t_{F,i}\}$ 是 syzygy 所有的基. 下证它确实是一组基.

若它不是一组基, 设 $q=\langle q_1,\dots,q_r\rangle$ 满足 $\sum q_j f_j=0$. $q$ 是 syzygy 中所有不能被基表示的中, $M:=\max\{\operatorname{Hterm}(q_jf_j)\}$ 最小的那个.

令 $\tilde{F}=\{j\mid \operatorname{Hterm}(q_jf_j)=M\}$. 那么

$$ \sum_{j\in\tilde F} \operatorname{Hcoef}(q_j)\operatorname{Hcoef}(f_j)=0,\quad\operatorname{lcm}(\operatorname{Hterm}(f_j),j\in\tilde F)\ \Big|\ M $$

故设 $(\operatorname{Hcoef}(f_j),j\in\tilde F)$ 有 $m$ 个 syzygy-基 $\{\langle s_{\tilde F,i,1},\dots,s_{\tilde F,i,r}\rangle \mid1\le i\le m\}$ (每个基对应一个 S-polynomial ), 则存在 $c_1,\dots,c_m$ 使得 $\sum_jc_js_{\tilde F,i,j}=\operatorname{Hcoef}(q_j)$.

令 $q^\prime=q+(M/\operatorname{lcm})\sum_{j}c_jt_{\tilde F,j}$. 则 $\operatorname{Hterm}(q^\prime_j)\operatorname{Hterm}(f_j)<M$ (由于所有次数为 $M$ 的项都被抵消掉了), 且 $q^\prime$ 依旧在 syzygy 里面, 不能被 $\overline t_k$ 表示 (否则 $q$ 也能被表示). 与 $M$ 的最小性矛盾!

故 syzygy 里所有元素均可以被这组基表示.

根据以上推理过程, 我们可以很简单地得到一个元素在该基下的表示.

对于 $\sum_{j} q_jf_j=0$, 计算 $M=\max\{\operatorname{Hterm}(q_jf_j)\}$, 记 $\tilde {F}=\{j\mid \operatorname{Hterm}(q_jf_j)=M\}$, 然后用下标集 $\tilde F$ 对应的 S-polynomial 和基环上的 syzygy-solvability 去消去, 然后降低 $M$, 直到 $q_j=0,\forall j$.

General Case

设 $G=\{g_1,\dots,g_s\}$ 是一组 $(f_1,\dots,f_r)$ 的 Gröbner 基, 且有

$$ [g_1,\dots,g_s]^\top=X[f_1,\dots,f_r]^\top,\quad [f_1,\dots,f_r]^\top=Y[g_1,\dots,g_s]^\top $$

其中 $X,Y$ 对应的矩阵在计算 Gröbner 基时都可以直接得到. 那么若 $G$ 对应的基为 $T$ (一行为一个基), 则

$$ \begin{bmatrix}I_r-YX\\TX\end{bmatrix} $$

是一组基: 易证上面右乘 $f$ 得 $0$. 下说明所有解都可以被表示.

设 $q=\langle q_1,\dots,q_r\rangle $ 为一个解. 那么 $q f^\top=0$, 从而 $qYg^\top=0 $. 设 $qY=\nu T$ (由 Gröbner 基的情况 $\nu$ 是容易计算的), 那么 $qYX=\nu TX$, 故

$$ \begin{bmatrix}q&\nu\end{bmatrix}\begin{bmatrix}I_r-YX\\TX\end{bmatrix}=q-qYX+\nu TX=q. $$

故 $q$ 在这组基下的表示为 $\left[q\;\;\nu\right]$, 这样我们就解决了一般的情况.

应用

计算理想论

理想的交

计算 $I\cap J$, 其中 $I,J$ 是理想.

设 $I=(f_1,\dots,f_r),J=(g_1,\dots,g_s)$. 那么 $x\in I\cap J$ 当且仅当存在 $t_1,\dots,t_r,p_1,\dots,p_{s}\in R$ 满足
$$\sum_{i=1}^rt_if_i-\sum_{j=1}^sp_jg_j=0. $$
解 syzygy $(f_1,\dots,f_r,g_1,\dots,g_s)$. 对于每个解 $\langle\xi_1,\dots,\xi_r,\eta_1,\dots,\eta_s\rangle$, $\sum_{i}\xi_if_i$ 即为交理想的一个生成元.

理想的商

计算 $I:J:=\{a\mid aJ\subset I\}$.

先假设 $J=(f)$, 那么 $aJ\subset (g_1,\dots,g_s)$ 当且仅当存在 $r_1,\dots,r_s$ 使得 $\sum r_ig_i=af$.

求解 syzygy $(f,-g_1,\dots,-g_r)$ 得到 $\{\langle \eta_i,\xi_{i,1},\dots,\xi_{i,r}\rangle\mid 1\le i\le m\}$ 为一组基, 那么 $I:J=I:(f)=(\eta_1,\dots,\eta_m)$.

设 $J=(f_1,\dots,f_s)$, 则 $I:J=\bigcap_{i=1}^s (I:(f_i))$.