# 07 对偶格与对偶基

整理日期：2026-10-16。
前置笔记：[01 格与格基](/knowledge/lattices-and-bases/)、[02 基本区域、格行列式与正交化](/knowledge/fundamental-region-and-orthogonalization/)。算法联系见 [06 Babai 最近平面算法与近似 CVP](/knowledge/babai-nearest-plane/)。

本篇先讨论满秩格：

$$
B=(b_1,\ldots,b_n)\in\mathbb R^{n\times n},
\qquad
\Lambda=\mathcal L(B),
$$

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

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

## 1. 对偶格与对偶基

对偶格定义为

$$
\boxed{
\Lambda^*
=
\left\{
y\in\mathbb R^n:
\langle x,y\rangle\in\mathbb Z
\quad\text{对所有 }x\in\Lambda
\right\}.
}
$$

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

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

$$
y\in\Lambda^*
\iff
B^Ty\in\mathbb Z^n.
$$

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

$$
\langle x,y\rangle=z^TB^Ty.
$$

由此直接得到

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

矩阵 $D$ 称为 $B$ 的**对偶基**，满足

$$
B^TD=I,
\qquad
\langle b_i,d_j\rangle=\delta_{ij}.
$$

因此，$d_j$ 与其余的 $b_i$ 正交，与对应的 $b_j$ 内积为 $1$。这个条件约束两组基之间的配对关系，$d_1,\ldots,d_n$ 本身一般并不两两正交。见 [Regev《Lecture 8: Dual Lattices》，Fall 2004，第 1–2 页，Definition 1–2、Claim 1](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/DualLattice.pdf)。

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

$$
x=Bz,
$$

则

$$
\boxed{
D^Tx=z,
\qquad
\langle x,d_i\rangle=z_i.
}
$$

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

$$
\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 及其后说明](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/lec3.pdf)。

## 2. 基本性质

对偶具有对称性：

$$
\boxed{(\Lambda^*)^*=\Lambda.}
$$

格行列式互为倒数：

$$
\boxed{
\det(\Lambda^*)=\frac1{\det(\Lambda)}.
}
$$

在满秩情形，这两条可以直接由 $D=B^{-T}$ 推出。第二条联系的是基本区域的体积，并不表示对应基向量的长度逐个互为倒数。见 [Regev，第 2 页，Claim 2–3](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/DualLattice.pdf)。

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

$$
(a\Lambda)^*=\frac1a\Lambda^*,
\qquad a>0,
$$

以及

$$
\Lambda_1\subseteq\Lambda_2
\iff
\Lambda_2^*\subseteq\Lambda_1^*,
$$

其中 $\Lambda_1,\Lambda_2$ 都是 $\mathbb R^n$ 中的满秩格。

包含关系反向，是因为原格中的向量越多，对整数内积的要求就越多，满足条件的对偶向量集合越小。见 [Micciancio，§1，PDF 第 2 页，Exercise 2–3](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/lec3.pdf)。

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

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

$$
\langle x,d_n\rangle=z_n\in\mathbb Z.
$$

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

$$
H_k=\{x\in\mathbb R^n:\langle x,d_n\rangle=k\},
\qquad k\in\mathbb Z.
$$

每一层中的格点恰好是

$$
\Lambda\cap H_k
=
k b_n+\mathcal L(b_1,\ldots,b_{n-1}).
$$

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

$$
\frac1{\|d_n\|}.
$$

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

$$
\boxed{
d_n=\frac{b_n^*}{\|b_n^*\|^2},
}
$$

所以

$$
\frac1{\|d_n\|}=\|b_n^*\|.
$$

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

$$
c_n
=
\operatorname{round}\bigl(\langle t,d_n\rangle\bigr)
=
\operatorname{round}
\left(
\frac{\langle t,b_n^*\rangle}{\|b_n^*\|^2}
\right).
$$

对偶基给出了整数层编号，正交化给出了计算层间距离所需的方向和长度。这里的公式针对最后一个向量；一般不能直接把每个 $d_i$ 都写成 $b_i^*/\|b_i^*\|^2$。见 [Micciancio，§3，PDF 第 6 页，Corollary 6 及其后的分层解释](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/lec3.pdf)。

## 4. 一个二维例子

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

$$
B=
\begin{pmatrix}
2&1\\
0&2
\end{pmatrix}.
$$

其对偶基为

$$
D=B^{-T}
=
\begin{pmatrix}
\frac12&0\\
-\frac14&\frac12
\end{pmatrix}.
$$

因此

$$
d_1=\left(\frac12,-\frac14\right),
\qquad
d_2=\left(0,\frac12\right),
\qquad
\Lambda^*=\mathcal L(d_1,d_2).
$$

若原格点写成

$$
x=z_1b_1+z_2b_2=(2z_1+z_2,\,2z_2),
$$

则

$$
\langle x,d_1\rangle=z_1,
\qquad
\langle x,d_2\rangle=z_2.
$$

同时，

$$
\det\Lambda=4,
\qquad
\det\Lambda^*=\frac14.
$$

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

$$
\langle x,d_2\rangle=k
\iff
x_2=2k.
$$

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

第二篇的正交化向量是

$$
b_1^*=(2,0),\qquad b_2^*=(0,2),
$$

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

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

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [08 覆盖半径与转移定理](/knowledge/covering-radius-and-transference/)
- [10 傅里叶变换与 Poisson 求和公式](/knowledge/fourier-transform-and-poisson-summation/)
- [12 q 元格与模线性方程](/knowledge/q-ary-lattices/)