用户: Guoh064/Gröbner 基

Gröbner 基是域上多项式环的理想的一组生成元, 使得理想对应的首项理想由这些生成元的首项生成. Gröbner 基的计算是求解多项式方程组的有效工具之一.

由 Hilbert 基定理, 域上多项式环的理想都有限生成. 由理想的给定生成元计算其 Gröbner 基的过程推广了 Euclid 辗转相除法, 解线性方程组中的 Gauß 消元法以及线性规划中的单纯形算法.

1前置

单项式序

参见: 单项式序

令 $K$ 为域, 考虑 $K$ 上的 $n$ 元多项式环 $K[x_1,\dots ,x_n]$.

定义 1.1 (单项式序). $K[x_1,\dots ,x_n]$ 上的单项式序是其上所有 (首一) 单项式 $x^a=x_1^{a_1}\dots x_n^{a_n}$ 之间满足如下两条性质的全序 $<$ :

1.	常数多项式为最小元. 也即对任意的 $a\in {\mathbb{N}}^n\setminus \{0\}$, $1<x^a$.
2.	对任意的 $a,b,c\in {\mathbb{N}}^n$, 若 $x^a<x^b$ 则有 $x^{a+c}<x^{b+c}$.

对于一般的单项式来说, 差一个非零常数因子意义下相同的单项式在序关系 $<$ 下相等. 这也就是同类项在多项式的典范表示中合并的道理.

注 1.2. 由定义, 一元多项式环 $K[x]$ 上只有唯一的单项式序, 也即单项式的次数作为自然数诱导的序$$1<x<x^2<\cdots <x^m<x^{m+1}<\cdots$$

给定多项式环 $K[x_1,\dots ,x_n]$ 上的单项式序 $<$ 后, 每个多项式 $f$ 都有唯一的首项, 也就是在 $f$ 中出现的非零系数的 $<$-最大的单项式 ${\lambda }_a{x}^a$, 记为 ${\mathrm{LT}}_{<}(f)$. 首项系数 ${\lambda }_a$ 记为 ${\mathrm{LC}}_{<}(f)$, 对应的首一单项式 $x^a$ 记为 ${\mathrm{LM}}_{<}(f)$. 在不引起混淆时也可以省略 $<$ 记号.

约化

首项理想

定义 1.3 (首项理想). 给定多项式环 $K[x_1,\dots ,x_n]$ 上的单项式序 $<$ 以及理想 $I$, $I$ 的首项理想是由 $I$ 中所有多项式的首项生成的理想, 记为 ${\mathrm{LT}}_{<}(I)$.

例 1.4. $K[x_1,\dots ,x_n]$ 上的理想 $I=⟨x_1+1⟩$ 对应的首项理想是 $⟨x_1⟩$.

这说明理想与其对应的首项理想之间一般不存在相互包含关系.

2定义

定义 2.1 (Gröbner 基). 给定域 $K$ 上的多项式环 $R=K[x_1,\dots ,x_n]$, $R$ 上的序 $<$, 以及 $R$ 的理想 $I$, $I$ 关于 $<$ 的 Gröbner 基是 $I$ 的一组生成元 $f_1,\dots ,f_m$, 使得首项理想 ${\mathrm{LT}}_{<}(I)$ 由 ${\mathrm{LT}}_{<}(f_i)$ 生成, $i=1,\dots ,m$.