Skip to content

格行列式

Lattice determinant · Lattice covolume · 格余体积

欧氏格基本平行多面体在其实张成空间中的内在体积。

条目类型
定义

形式陈述

设秩 kΛ=L(B)Rn,其中 BRn×k 满列秩。格行列式或余体积定义为

det(Λ)=volk(P(B))=det(BTB).

右端内层的 行列式取自 k×k Gram 矩阵;平方根非负,并因满列秩而严格为正。只有在 k=nB 为方阵时,公式才化为

det(Λ)=|detB|.

若换成另一格基 B=BU,其中 UGLk(Z),则

det(BTB)=(detU)2det(BTB)=det(BTB).

所以余体积依赖格而不依赖基。术语“determinant”在此表示一个正实数,不是带符号的方阵行列式;有些文献把 Gram 行列式本身称作判别式,应留意是否差了一个平方。

直觉

余体积衡量格点的平均稀疏程度。一个基本平行多面体恰好代表一个格陪集,体积越大,每个格点平均占据的连续空间越多。它控制的是整体密度,不决定局部形状:同一余体积的格可以近乎正交,也可以细长到有极短和极长的方向。

Gram 矩阵把环境坐标消去,只记录基向量的长度与夹角。det(BTB) 是平行多面体体积的平方,因此即使格嵌在更高维空间,仍能得到正确的内在 k 维体积。直接对长方矩阵写 detB 没有定义,也不能靠随意补列获得基无关答案。

若对基做 thin QR 分解 B=QR,其中 QTQ=IkR 为上三角矩阵,则

detΛ=|detR|=i=1k|rii|=i=1kbi2,

这里 bi 是未归一化 Gram–Schmidt 向量。这个乘积公式把体积看成逐层“新高度”,也解释了某一步投影高度接近零为何意味着基近乎相关。数值计算时通常累加 log|rii|,可避免高维乘积上溢或下溢。

ΛΛ 是同秩子格,则

[Λ:Λ]=detΛdetΛ.

子格点更少,余体积反而更大;这个方向是检验同余格计算是否写反的便捷方法。

例子与边界

R3 中取

b1=(1,0,1),b2=(0,2,0),BTB=(2004).

该格秩为 2,所以

detΛ=det(BTB)=8=22.

几何上,两向量正交,面积也确为 b1b2=22。若误把环境三维体积用于这个平行四边形,会得到零;那只是二维对象在三维 Lebesgue 测度下为零,不是格余体积为零。

再看 Λ=2Z×3ZZ2。其基矩阵为 diag(2,3),余体积为 6,而商群有六个陪集,故指数公式吻合。把第二列改成 (1,3) 不改变绝对行列式,显示剪切形状与平均密度可以分离。

余体积相同不推出等距或同一个格。diag(2,1/2)Z2Z2 都有余体积 1,前者却含长度 1/2 的非零向量。更不能由 detΛ=1 推出 Λ 自对偶;自对偶还要求整数配对与点集相等。

推论与应用

Minkowski 第一定理把对称凸体的体积与 2kdetΛ 比较,从余体积推出短向量存在性。对偶格满足 det(Λ)=1/det(Λ);这一互反关系是 Poisson 求和与平滑参数估计的尺度检查。

在 q-ary 格中,线性同余约束常把 Zm 切成有限指数的子格,指数公式便可直接给出余体积。不过秩、满射性和模数因子必须实际验证:若约束矩阵模 q 不满秩,机械写成 qn 会高估指数。

余体积还提供缩放审计:对秩 k 格有 det(cΛ)=|c|kdetΛ,而正交变换不改变它。若推导中整体长度放大 c 后余体积只乘 c,除非 k=1,便说明把线性尺度和 k 维体积混在了一起。

参考资料
  • 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。
关系图谱8 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系

使用的工具