我们在Lean 4中正式化了Kannan-Bachem Smith标准形式算法，针对非奇异的平方整数矩阵。该程序返回 $S,U,U^{-1},V,V^{-1}$，并证明了 $UAV=S$、$U^{-1}SV^{-1}=A$ 四个逆身份，Smith可分性条件，以及 $S$ 与标准参考矩阵的相等性。
由于每次递归调用严格减少了活动主元的二进制大小，稳定化过程终止；外部算法在右下块上递归。计算还会生成指定符号-幅度算术叶子的平面追踪。分支条件、商、Bezout数据和矩阵条目均来自记录的原始运行。
复合阶段通过连接执行子程序返回的电荷列表来形成其追踪。经过验证的自定界编解码器定义了输入和输出大小。系数和工作递归通过核检查的多项式包络计算而闭合，为追踪成本和五个输出矩阵的编码长度提供了固定的多项式界限。该定理涉及这些算术原语；结构操作和编译的Lean运行时则不在模型之内。
博主点评： 该研究通过在Lean 4中形式化Kannan-Bachem的Smith标准形式算法，展示了数学与计算机科学的紧密结合，尤其是在机器检查算术复杂度方面的贡献，推动了形式验证技术在算法设计中的应用前景。