“对同余条件定义的子格,先通过格余体积或指数求出 $\det\Lambda$,再应用本定理,常能证明某个非零短整数解存在。这是 SIS 存在性分析的几何核心之一;还需另行确保找到的向量模 $q…”
形式陈述 ​
设秩
右端内层的 行列式取自
若换成另一格基
所以余体积依赖格而不依赖基。术语“determinant”在此表示一个正实数,不是带符号的方阵行列式;有些文献把 Gram 行列式本身称作判别式,应留意是否差了一个平方。
直觉
余体积衡量格点的平均稀疏程度。一个基本平行多面体恰好代表一个格陪集,体积越大,每个格点平均占据的连续空间越多。它控制的是整体密度,不决定局部形状:同一余体积的格可以近乎正交,也可以细长到有极短和极长的方向。
Gram 矩阵把环境坐标消去,只记录基向量的长度与夹角。
若对基做 thin QR 分解
这里
若
子格点更少,余体积反而更大;这个方向是检验同余格计算是否写反的便捷方法。
例子与边界
在
该格秩为
几何上,两向量正交,面积也确为
再看
余体积相同不推出等距或同一个格。
推论与应用
Minkowski 第一定理把对称凸体的体积与
在 q-ary 格中,线性同余约束常把
余体积还提供缩放审计:对秩
参考资料
- Daniele Micciancio and Shafi Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective, Kluwer, 2002, Secs. 1.1–1.2。
- John H. Conway and Neil J. A. Sloane, Sphere Packings, Lattices and Groups, 3rd ed., Springer, 1999, Ch. 1。
- J. W. S. Cassels, An Introduction to the Geometry of Numbers, Springer, 1959, Ch. I。