Groebner基与代数几何

为了更好的理解Groebner基及相关性质，这里给出计算代数几何与交换代数的相关介绍，但会忽略一些严格的数学证明。参考书籍：Ideals,Varieties,and Algorithms（理想，簇与算法）

几何，代数与算法

多项式与仿射空间

仿射空间：给定一个任意域$k$和一个正整数$m$，域$k$上的$n$维仿射空间为

$$k^n=\{(a_1,\dots,a_n):a_1,\dots,a_n\in k\}$$

• 对于一个在无限域$k$上的多项式$f=\sum_{\alpha}a_{\alpha}x^{\alpha} \in k[x_1,\dots,x_n]$，在多项式环$k[x_1,\dots,x_n]$上$f=0 \Longleftrightarrow f$是零多项式，即$a_{\alpha}$ 均为0
• 每个非常数多项式$f\in \mathbb{c}[x]$在复数域$\mathbb{c}$上都有根，$\mathbb{c}$是代数闭域。

仿射簇及其参数化

仿射簇：给定一个任意域$k$，$f_1,\dots,f_s$是环$k[x_1,\dots,x_n]$上的多项式。则由$f_1,\dots,f_s$定义的仿射簇$\mathbf{V}(f_1,\dots,f_s)$为：

$$\mathbf{V}(f_1,\dots,f_s)=\{(a_1,\dots,a_n)\in k^n : f_i(a_1,\dots,a_n)=0, \forall i \in [1,s]\}$$

• 每个约束使得仿射空间降一维
• 若$V,W\subset k^n$是仿射簇，那么 $V\cup W , V\cap W$也是仿射簇 $$V\cup W=\mathbf{V}(f_1,\dots,f_s,g_1,\dots,g_t) \\ V\cap W=\mathbf{V}(f_ig_j : 1\leq i \leq s,1\leq j \leq t)$$

理想

定义1：一个理想是一个子集$I \subset k[x_1,\dots,x_n]$，如果满足：
$i$. $0\in I$
$ii$. 若 $f,g \in I$，则$f+g \in I$
$iii$. 若 $f \in I$ 和 $h\in k[x_1,\dots,x_n]$，则 $hf\in I$

理想的一个重要应用是可以计算仿射簇，同时，理想也可以由有限个多项式生成。

定义2：令$f_1,\dots,f_s$是环$k[x_1,\dots,x_n]$上的多项式，则$\langle f_1,\dots,f_s\rangle$是一个由$f_1,\dots,f_s$生成的理想

$$\langle f_1,\dots,f_s\rangle=\left\{ \sum ^s_{i=1}h_if_i:h_1,\dots,h_s\in k[x_1,\dots,x_n]\right\}$$

$f_1,\dots,f_s$是理想$I$的基。另一方面，理想也可以通过代数簇来定义。一个命题如下：

• 命题：如果$f_1,\dots,f_s$和$g_1,\dots,g_t$是$k[x_1,\dots,x_n]$上相同理想的两组基，即$\langle f_1,\dots,f_s\rangle = \langle g_1,\dots,g_t\rangle$，则我们有$\mathbf{V}(f_1,\dots,f_s) = \mathbf{V}(g_1,\dots,g_t)$

定义3：另$V\subset k^n$是一个仿射簇，则$\mathbf{I}(V)$是一个理想

$$\mathbf{I}(V)={f\in k[x_1,\dots,x_n]:f(a_1,\dots,a_n)=0, \forall (a_1,\dots,a_n) \in V}$$

理想中包含的实际上是：在给定簇上“变为0”的所有多项式

• 引理：如果$V\subset k^n$是一个仿射簇，则$\mathbf{I}(V) \subset k[x_1,\dots,x_n]$是一个理想，称为$V$的理想。

• 给定一些多项式，基于多项式可以得到仿射簇，考虑所有在仿射簇上”变为0”的多项式，得到了对应的理想。因此在$f_1,\dots,f_s \in k[x_1,\dots,x_n]$上有：

  $$\begin{array}{c} 多项式 \\ f_1,\dots,f_s \end{array} \rightarrow \begin{array}{c} 仿射簇 \\ \mathbf{V}(f_1,\dots,f_s) \end{array} \rightarrow \begin{array}{c} 理想 \\ \mathbf{I}(V(f_1,\dots,f_s)) \end{array}$$

  但需要注意的是，$ \mathbf{I}(V(f_1,\dots,f_s))=\langle f_1,\dots,f_s\rangle$并不成立。

• 引理：若$f_1,\dots,f_s \in k[x_1,\dots,x_n]$，则$\langle f_1,\dots,f_s\rangle \subset \mathbf{I}(V(f_1,\dots,f_s))$，尽管不需要发生相等

证明：
令$f \in \langle f_1,\dots,f_s\rangle$，由于$f_1,\dots,f_s$在仿射簇上变为0，则$\forall f$在仿射簇上也是0，故而$f \in \mathbf{I}(V(f_1,\dots,f_s))$.同时，$\mathbf{I}(V(f_1,\dots,f_s))$是严格大于$\langle f_1,\dots,f_s\rangle$的空间，例如：

$$\langle x^2,y^2\rangle \subset \mathbf{I}(V(x^2,y^2))$$

$\mathbf{I}(V(x^2,y^2))=\{(0,0)\}$，但是显然也有$\mathbf{I}(V(x^2,y^2))=\langle x,y \rangle$，由于$x \notin \langle x^2,y^2\rangle$，不能写成$h_1(x,y)x^2+h_2(x,y)y^2$的形式，因此该例子中是不存在相等关系的。

• 命题：令$V$和$W$是$k^n$上的仿射簇，则：
  (i) $V \subset W \Longleftrightarrow \mathbf{I}(V) \supset \mathbf{I}(W)$
  (ii)$V = W \Longleftrightarrow \mathbf{I}(V) = \mathbf{I}(W)$

证明(i)：
$\Longrightarrow$ : $V \subset W$表示对任意的多项式在仿射簇$W$上变为0，则一定在仿射簇$V$上变为0，则$ \mathbf{I}(V) \supset \mathbf{I}(W)$
$\Longleftarrow$ : $\mathbf{I}(V) \supset \mathbf{I}(W)$表示理想$\mathbf{I}(W)$中包含的多项式是理想$\mathbf{I}(V)$的子集，则存在部分$\mathbf{I}(V)$中的多项式在仿射簇$W$上没有变为0，则$V \subset W$

单变量多项式

算法是操纵符合和数据的一系列特定指定集合，这里主要讨论在域$k[x]$上的多项式除法

定义（首项）：对于一个非零多项式$f\in k[x]$，令

$$f=a_0x^m+a_1x^{m-1}+\dots+a_m$$

其中 $a_i \in k.a_0 \neq0$，称 $a_0x^m$ 为 $f$ 的首项，写做 $LT(f)=a_0x^m$

• 命题（除法算法）：令$k$是一个任意的域，令$g$是一个域$k[x]$上的非零多项式。则对于每一个$f \in k[x]$都可以写做$f=qg+r$其中$q,r \in k[x]$，且$r=0或deg(r) < deg(g)$，$q,r$是唯一的。

• 推论1：若$k$是一个任意的域，令$g$是一个域$k[x]$上的非零多项式，则$f$在$k$上最多有$deg(f)$个根。

• 推论2：若$k$是一个任意的域，则域$k[x]$上的每个理想都可以写成$\langle f \rangle$的形式，其中$f \in k[x]$.
  主理想：由一个非零元生成的理想。易知$k[x]$是一个主理想整环（PID）
• 推论3:令$f,g\in k[x]$,
  (i) $GCD(f,g)$存在且唯一
  (ii) $GCD(f,g)$是理想$\langle f,g \rangle$的生成元
  (iii) $GCD(f,g)$是可以通过算法找到的

定义（最大公因子）：多项式$f_1,\dots,f_s \in k[x]$的最大公因子是多项式$h=GCD(f_1,\dots,f_s)$满足：
(i) $h$整除$f_1,\dots,f_s$
(ii) 若$p$也可以整除$f_1,\dots,f_s$，则$p|h$

• 推论：令$f_1,\dots,f_s \in k[x],s \geq 2$,
  (i) $GCD(f_1,\dots,f_s)$存在且唯一
  (ii) $GCD(f_1,\dots,f_s)$是理想$\langle f_1,\dots,f_s \rangle$的生成元
  (iii) 若$s \geq 2$，则$GCD(f_1,\dots,f_s)=GCD(f_1,GCD(f_2,\dots,f_s))$
  (iv) $GCD(f_1,\dots,f_s)$是可以通过算法找到的

Groebner基

主要问题介绍

通过Groebner基方法，可以解决在算法或计算方式上多项式理想的相关问题。

问题

1. 理想描述问题：是否每个理想$I\subset k[x_1,\dots,x_n]$都有有限个生成元？或者，是否可以用一些多项式$f_i\in k[x_1,\dots,x_n]$表示理想 $I=\langle f_1,\dots,f_s\rangle$
2. 理想成员问题：给定一个多项式$f\in k[x_1,\dots,x_n]$和一个理想$I=\langle f_1,\dots,f_s\rangle$，判定是否$f\in I$。从几何上看，判断$\mathbf{V}(f)$是否在$\mathbf{V}(f_1,\dots,f_s)$
3. 解多项式方程问题：找到多项式方程系统在$k^n$上的所有解$f_1(x_1,\dots,x_n)=\dots=f_s(x_1,\dots,x_n)=0$同样的，该问题也相当于找仿射簇$\mathbf{V}(f_1,\dots,f_s)$的所有点集
4. 隐含问题：设$V$是$k^n$上的子集，其参数为$x_1=g_1(t_1,\dots,t_m),\\ \vdots \\ x_n=g_n(t_1,\dots,t_m).$其中$g_i$是关于变量$t_j$的多项式，则$V$是一个仿射簇。寻找一个多项式方程系统（关于$x_i$）可以表示这个仿射簇。

$k[x_1,\dots,x_n]$上的单项式序

可以将除法和行归约推广到任意多变量多项式的一个关键是多项式项的排序。单项式序需要具有如下性质：

定义1（单项式序）：$k[x_1,\dots,x_n]$上的单项式序$>$是一个$\mathbb{Z}^n_{\geq 0}$上的关系$>$。或者等价的，是单项式集合$x^\alpha,\alpha \in \mathbb{Z}^n_{\geq 0}$上的一个关系，满足：
(i) $>$是$\mathbb{Z}^n_{\geq 0}$上的一个完全（线性）序
(ii) 若$\alpha > \beta$，且$\gamma \in \mathbb{Z}^n_{\geq 0}$，则$\alpha+\gamma > \beta+\gamma$
(iii) $>$是$\mathbb{Z}^n_{\geq 0}$上的一个良序。这表示每个$\mathbb{Z}^n_{\geq 0}$上的非空子集在$>$下都有一个最小的项。也就是说，若$A\subseteq \mathbb{Z}^n_{\geq 0}$是非空的，存在$\alpha \in A$满足$\forall \beta\neq \alpha \in A, \beta > \alpha$

• 定义说明：

  • （i）该性质保证了任意一对单项式（$x^\alpha$和$x^\beta$）间有明确的关系：大于，等于，小于；同时序是需要可以传递的。 $$x^\alpha > x^\beta, x^\alpha = x^\beta, x^\alpha < x^\beta \\ x^\alpha > x^\beta, x^\beta > x^\gamma \Longrightarrow x^\alpha > x^\gamma$$
  • （ii） 保证多项式的运算正确性
  • （iii）见如下引理

• 引理：一个$\mathbb{Z}^n_{\geq 0}$上的顺序关系$>$是良序当且仅当每一个$\mathbb{Z}^n_{\geq 0}$上的严格递减序列最终可终止

  $$\alpha(1)>\alpha(2)>\alpha(3)>\cdots$$

  该引理将用于证明各种算法一定会终止，因为在算法的每一步都有一些项严格递减(相对于固定的单项顺序)。

通常的数字顺序就是一个简单的单项式序，因此$k[x]$中的单项式的次数序就是一个单项式序。在n元组上排序的一个示例是字典序(lex序)。

$$\cdots > m+1>m>\cdots>3>2>1>0$$

定义2（字典序）：在$\mathbb{Z}^n_{\geq 0}$上，令$\alpha=(\alpha_1,\dots,\alpha_n),\beta=(\beta_1,\dots,\beta_n)$，若向量差的最左侧非零项 $\alpha-\beta \in \mathbb{Z}^n$是正的，则$\alpha >_{lex} \beta$。若$\alpha >_{lex} \beta$，则写作$x^\alpha >_{lex} x^\beta$