Buchberger 算法

当前生成集可视为一组定向重写规则：遇到被某个首单项式整除的项就向下约简。两条规则的首项有共同倍数时，可能从同一单项式走出两条路径并留下不同结果。S-pair 把最小的这种分叉显式制造出来；若差异能约简为零，冲突已协调，若留下非零余式，就把它加入规则集修补缺口。

算法因此不是盲目枚举理想元素。它只追踪由首项重叠产生的有限类型冲突，并用单项式理想的 Noether 性证明修补不会无限发生。pair 选择策略会显著改变中间规模，却不改变“所有必要冲突最终解决”这一正确性核心。

在 $K[x,y]$ 上取 lex 序 $x\succ y$，从

开始。首个 S-pair 给出

它不能被 $f_1,f_2$ 约简，故加入 $G$。随后 $\mathrm{LM}(g_3)=x$ 已整除 $f_2$ 的首项，pair $(f_2,g_3)$ 产生

加入 $g_4$ 后，其余 pair 均约简到零。对集合做 interreduction，$f_1,f_2$ 都可由 $g_3,g_4$ 表示，最终 reduced basis 为

这个过程还展示算法输出未必自动 reduced：停止条件只保证所有 S-pair 归零，旧的冗余元素仍可能留在 $G$ 中。

多元除法的余式在 $G$ 尚非 Gröbner 基时依赖除数次序，因此不同运行会产生不同中间多项式；正确性只要求每个选中的 S-pair得到某个合法完全余式。为避免遗漏，product criterion 和 chain criterion 只能在各自前提成立时删除 pair，不能因为“看起来相似”就跳过。

底环不是域时首系数不一定可除，算法需要环上的 Gröbner 基变体。精确有理数计算还会出现系数膨胀，常以模素数计算和 rational reconstruction 缓解。最坏情况下 Gröbner 基次数与规模可双指数增长，Buchberger 终止定理没有给出实用的多项式时间界；小例子的顺滑消元不能换成一般性能承诺。

pair 选择可以按最小总次数、糖度或预估矩阵规模排序；Buchberger 的两类经典判据能提前排除必然约简为零的 pair。对齐 homogeneous 输入时按次数处理便于控制层次，非齐次系统可用 homogenization 或 sugar strategy 模拟这一行为。无论采用哪种优化，最终仍应以 Buchberger criterion 或等价证书核验。

F4 算法公理库F4 Gröbner 基算法F4 Gröbner basis algorithm · Faugère F4 algorithm以符号预处理收集一批临界对的约简子，并用稀疏 Macaulay 矩阵消元批量产生新首项。保留同一临界 pair 框架，却把一批 S-多项式的相互约简放进稀疏矩阵消元，从而复用公共单项式倍数。后来的 signature 算法还会追踪生成表示以预判零约简。Buchberger 算法因此既是可直接实现的基线，也是判断这些改进是否保持理想与首项不变量的参照。

得到基后，可进行理想成员判定、消元和零维求解；但算法只在选定单项式序下完成符号预处理，不负责选择数值稳定的根算法。若应用只需一个消元多项式，完整 reduced lex basis 可能过度计算，resultant、FGLM 次序转换或专用结构算法可能更合适。