For AI agents: the complete documentation index is available at https://shijin.space/llms.txt, the full documentation bundle is available at https://shijin.space/llms-full.txt, and this page is available as Markdown at https://shijin.space/knowledge/dual-lattices/index.md.
ShiJin

    07 对偶格与对偶基

    整理日期：2026-10-16。 前置笔记：01 格与格基、02 基本区域、格行列式与正交化。算法联系见 06 Babai 最近平面算法与近似 CVP。

    本篇先讨论满秩格：

    B=(b1,…,bn)∈Rn×n,Λ=L(B),B=(b_1,\ldots,b_n)\in\mathbb R^{n\times n}, \qquad \Lambda=\mathcal L(B),

    其中 BB 可逆，基向量按列排列。

    记 Λ∗\Lambda^* 为对偶格，对偶基记为 D=(d1,…,dn)D=(d_1,\ldots,d_n)；bi∗b_i^* 仍沿用前文的 Gram–Schmidt 正交化记号。

    1. 对偶格与对偶基

    对偶格定义为

    Λ∗={y∈Rn:⟨x,y⟩∈Z对所有 x∈Λ}.\boxed{ \Lambda^* = \left\{ y\in\mathbb R^n: \langle x,y\rangle\in\mathbb Z \quad\text{对所有 }x\in\Lambda \right\}. }

    也就是说，对偶向量与每一个原格向量的内积都是整数。

    判断一个向量是否属于对偶格，只需检查它与各个基向量的内积：

    y∈Λ∗  ⟺  BTy∈Zn.y\in\Lambda^* \iff B^Ty\in\mathbb Z^n.

    原因是任意格点都可以写成 x=Bzx=Bz，其中 z∈Znz\in\mathbb Z^n，于是

    ⟨x,y⟩=zTBTy.\langle x,y\rangle=z^TB^Ty.

    由此直接得到

    Λ∗=L(B−T),D=B−T:=(BT)−1.\boxed{ \Lambda^*=\mathcal L(B^{-T}), \qquad D=B^{-T}:=(B^T)^{-1}. }

    矩阵 DD 称为 BB 的对偶基，满足

    BTD=I,⟨bi,dj⟩=δij.B^TD=I, \qquad \langle b_i,d_j\rangle=\delta_{ij}.

    因此，djd_j 与其余的 bib_i 正交，与对应的 bjb_j 内积为 11。这个条件约束两组基之间的配对关系，d1,…,dnd_1,\ldots,d_n 本身一般并不两两正交。见 Regev《Lecture 8: Dual Lattices》，Fall 2004，第 1–2 页，Definition 1–2、Claim 1。

    对偶基还有一个直接作用：通过内积读出原基坐标。若

    x=Bz,x=Bz,

    则

    DTx=z,⟨x,di⟩=zi.\boxed{ D^Tx=z, \qquad \langle x,d_i\rangle=z_i. }

    于是，同一个格可以用两种方式描述：

    Λ=BZn={x∈Rn:DTx∈Zn}.\Lambda=B\mathbb Z^n = \{x\in\mathbb R^n:D^Tx\in\mathbb Z^n\}.

    前一种写法用整数系数组合生成格点；后一种写法用整数内积约束刻画格点。见 Micciancio《The dual lattice》，Fall 2017，§1，PDF 第 2–3 页，Theorem 2 及其后说明。

    2. 基本性质

    对偶具有对称性：

    (Λ∗)∗=Λ.\boxed{(\Lambda^*)^*=\Lambda.}

    格行列式互为倒数：

    det⁡(Λ∗)=1det⁡(Λ).\boxed{ \det(\Lambda^*)=\frac1{\det(\Lambda)}. }

    在满秩情形，这两条可以直接由 D=B−TD=B^{-T} 推出。第二条联系的是基本区域的体积，并不表示对应基向量的长度逐个互为倒数。见 Regev，第 2 页，Claim 2–3。

    此外，缩放和包含关系分别满足

    (aΛ)∗=1aΛ∗,a>0,(a\Lambda)^*=\frac1a\Lambda^*, \qquad a>0,

    以及

    Λ1⊆Λ2  ⟺  Λ2∗⊆Λ1∗,\Lambda_1\subseteq\Lambda_2 \iff \Lambda_2^*\subseteq\Lambda_1^*,

    其中 Λ1,Λ2\Lambda_1,\Lambda_2 都是 Rn\mathbb R^n 中的满秩格。

    包含关系反向，是因为原格中的向量越多，对整数内积的要求就越多，满足条件的对偶向量集合越小。见 Micciancio，§1，PDF 第 2 页，Exercise 2–3。

    3. 对偶向量、格点分层与最近平面

    取对偶基的最后一个向量 dnd_n。对任意格点 x=Bzx=Bz，

    ⟨x,dn⟩=zn∈Z.\langle x,d_n\rangle=z_n\in\mathbb Z.

    因此，格点按照最后一个整数坐标，分布在一组平行超平面上：

    Hk={x∈Rn:⟨x,dn⟩=k},k∈Z.H_k=\{x\in\mathbb R^n:\langle x,d_n\rangle=k\}, \qquad k\in\mathbb Z.

    每一层中的格点恰好是

    Λ∩Hk=kbn+L(b1,…,bn−1).\Lambda\cap H_k = k b_n+\mathcal L(b_1,\ldots,b_{n-1}).

    这些平面的法向量为 dnd_n，相邻平面间距为

    1∥dn∥.\frac1{\|d_n\|}.

    这就是第六篇使用的分层。对偶基与正交化之间满足

    dn=bn∗∥bn∗∥2,\boxed{ d_n=\frac{b_n^*}{\|b_n^*\|^2}, }

    所以

    1∥dn∥=∥bn∗∥.\frac1{\|d_n\|}=\|b_n^*\|.

    于是，Babai 算法第一轮的选层操作也可以写成

    cn=round⁡(⟨t,dn⟩)=round⁡(⟨t,bn∗⟩∥bn∗∥2).c_n = \operatorname{round}\bigl(\langle t,d_n\rangle\bigr) = \operatorname{round} \left( \frac{\langle t,b_n^*\rangle}{\|b_n^*\|^2} \right).

    对偶基给出了整数层编号，正交化给出了计算层间距离所需的方向和长度。这里的公式针对最后一个向量；一般不能直接把每个 did_i 都写成 bi∗/∥bi∗∥2b_i^*/\|b_i^*\|^2。见 Micciancio，§3，PDF 第 6 页，Corollary 6 及其后的分层解释。

    4. 一个二维例子

    沿用第二篇和第六篇的基：

    B=(2102).B= \begin{pmatrix} 2&1\\ 0&2 \end{pmatrix}.

    其对偶基为

    D=B−T=(120−1412).D=B^{-T} = \begin{pmatrix} \frac12&0\\ -\frac14&\frac12 \end{pmatrix}.

    因此

    d1=(12,−14),d2=(0,12),Λ∗=L(d1,d2).d_1=\left(\frac12,-\frac14\right), \qquad d_2=\left(0,\frac12\right), \qquad \Lambda^*=\mathcal L(d_1,d_2).

    若原格点写成

    x=z1b1+z2b2=(2z1+z2, 2z2),x=z_1b_1+z_2b_2=(2z_1+z_2,\,2z_2),

    则

    ⟨x,d1⟩=z1,⟨x,d2⟩=z2.\langle x,d_1\rangle=z_1, \qquad \langle x,d_2\rangle=z_2.

    同时，

    det⁡Λ=4,det⁡Λ∗=14.\det\Lambda=4, \qquad \det\Lambda^*=\frac14.

    由 d2=(0,12)d_2=(0,\tfrac12)，整数等值平面在二维中表现为直线

    ⟨x,d2⟩=k  ⟺  x2=2k.\langle x,d_2\rangle=k \iff x_2=2k.

    相邻直线间距为 22，与第六篇中的分层一致。

    第二篇的正交化向量是

    b1∗=(2,0),b2∗=(0,2),b_1^*=(2,0),\qquad b_2^*=(0,2),

    而这里的对偶基是 d1,d2d_1,d_2。两者是不同的对象：正交化用于分解正交方向，对偶基用于建立整数内积配对。

    原基把整数坐标映射为格点，对偶基通过内积读回这些坐标；这也是用对偶格理解格点分层的出发点。

    引用此笔记