整理日期：2026-10-16。 适用范围：欧氏格筛法中的长度尺度、角度概率与向量池规模估计。 前置笔记：02 基本区域、格行列式与正交化、03 逐次极小值与 Minkowski 定理。
设 \(\Lambda\subseteq\mathbb R^d\) 是满秩格，记 \(\Delta=\det(\Lambda)\)，使用欧氏范数。本文的 \(d\) 表示当前分析空间的维数，\(N\) 表示向量池大小。
本篇连接三个问题：某个长度范围内有多少格向量；两条向量相减时有多大概率变短；为了持续找到可约化向量，需要多大的向量池。
1. 高斯启发式：用体积估计格点数#
格的基本区域体积为 \(\Delta\)，因此格点的平均空间密度为 \(1/\Delta\)。
高斯启发式将这个平均密度用于具体区域 \(K\)，估计
这里的近似需要区域形状、尺度和格的几何结构适合该模型；行列式本身不能保证每个区域内的格点都按平均密度分布。这个计数表述可参见 G6K，EUROCRYPT 2019，§2.2，PDF 第 7 页。
对于以原点为中心的球，定义非零向量计数
$$ N_\Lambda(r)#
#{v\in\Lambda:0<|v|\le r}. $$
记 \(d\) 维单位球体积为
其中 \(\Gamma\) 是 Gamma 函数。在适合采用体积估计的尺度上，常使用
这里已经排除零向量；当预计只有常数个非零向量时，这个表达只适合判断长度尺度，不能当作精确计数。中心对称性还意味着 \(v\) 与 \(-v\) 成对出现；若只计符号对 \(\{\pm v\}\)，数量应再除以 \(2\)。
2. 高斯启发式给出的参考长度#
令球的体积等于一个基本区域的体积：
本文将对应半径定义为高斯启发式参考长度
$$ \boxed{ \operatorname{gh}(\Lambda)#
\left(\frac{\Delta}{V_d}\right)^{1/d}#
\frac{\Gamma(d/2+1)^{1/d}}{\sqrt{\pi}}\Delta^{1/d}. } $$
由 Stirling 公式，
$$ \operatorname{gh}(\Lambda)#
\sqrt{\frac{d}{2\pi e}}, \Delta^{1/d}(1+o(1)), \qquad d\to\infty. $$
常见预测是 \(\lambda_1(\Lambda)\approx\operatorname{gh}(\Lambda)\)。这是典型行为的估计；对一个给定格，它既不是确定的上界，也不是确定的下界。
本文采用单位体积球半径的定义。有些文献直接以渐近式定义 \(\operatorname{gh}\)，例如 G6K，§2.2，Definition 2、式 (1)。比较具体数值时需要先统一约定；这里也不把参考长度等同于某个随机格分布下的精确期望。
用 \(\operatorname{gh}(\Lambda)\) 归一化长度，可以得到简洁的计数形式：
这说明：在该模型下，半径按固定比例增加，球内向量数会按维数指数增长。
与已有内容的关系是：
- Minkowski 定理提供存在性保证。 将第 03 篇的凸体定理用于欧氏球，并令半径趋近临界值，可严格推出\[ \lambda_1(\Lambda)\le 2\operatorname{gh}(\Lambda). \]这是由球体积公式得到的推论，所用定理见 Regev，Fall 2004，Lecture 1，§3.1，Theorem 9，PDF 第 7 页。
- 离散高斯指定采样分布。 第 09 篇的 \(D_{\Lambda,s}\) 按高斯权重分配概率；高斯启发式用于估计格点数量和长度尺度。二者不能相互替代。
3. 从球内模型到球面模型#
把非零向量写成
其中 \(S^{d-1}\) 是 \(\mathbb R^d\) 中的单位球面。这样可以分别描述长度 \(r\) 与方向 \(u\)。
先考虑一个连续模型：\(X\) 在半径为 \(R\) 的球体内均匀分布。由体积比直接得到
因此，对固定 \(\varepsilon\in(0,1)\)，
$$ \Pr[(1-\varepsilon)R<|X|\le R]#
1-(1-\varepsilon)^d \longrightarrow1. $$
高维球体的大部分体积集中在外层薄壳。同时，由旋转对称性，\(X/\|X\|\) 在球面上均匀分布，且方向与长度独立。
薄壳集中描述了大多数样本的位置；对于指数级小概率事件，将所有长度直接替换成 \(R\) 的误差仍需单独检查。
这些结论对上述连续均匀模型成立。把它用于筛法中的格向量池，需要额外假设：
- 长度模型：向量长度集中在某个半径附近，或服从指定的径向分布。
- 方向模型：归一化后的方向近似球面均匀。
- 依赖模型：在当前计算中，将哪些向量或事件视为独立。
高斯启发式的计数估计并不自动蕴含这三点。Nguyen–Vidick 的早期分析明确假设每轮相关向量在球壳内均匀分布；参见 Nguyen–Vidick，2008，作者稿 §4.1，PDF 第 14 页的 Heuristic。
4. 两向量约化与 60° 阈值#
设两条非零格向量 \(x,y\) 的长度分别为 \(a,b\)，夹角为 \(\theta\)。由余弦定理，
$$ |x-y|^2#
a^2+b^2-2ab\cos\theta. $$
因此，对目标长度 \(r\)，
这给出了将长度条件转化为角度条件的基本公式。
当 \(a=b=R\) 时，
所以，两条等长向量的夹角小于 \(60^\circ\) 时，相减得到更短的向量；等于 \(60^\circ\) 时，新向量与原向量等长。
若同时允许 \(x-y\) 和 \(x+y\)，则
若要求从长度 \(R\) 缩短到 \(\gamma R\)，其中 \(0<\gamma<1\)，相减对应的阈值进一步变为 \(\cos\theta\ge1-\gamma^2/2\)。
这些都是确定的几何关系。实际长度不同时，应代入 \(a,b\) 计算阈值；只保存归一化方向会丢失这部分信息。筛法还需要排除重复或互为相反数的输入所产生的零向量。
5. 球帽概率：有多少方向满足约化条件#
设 \(d\ge2\)，\(U,V\) 是两个独立的球面均匀随机向量，记
由旋转对称性，可以固定 \(U\)。对阈值 \(t\in(0,1)\)，满足 \(\langle U,V\rangle\ge t\) 的方向形成一个球帽，半张角为 \(\arccos t\)。
记其相对面积为
由球面面积元，\(Z\) 的密度正比于 \((1-z^2)^{(d-3)/2}\)，归一化后得到精确公式
$$ \boxed{ p_d(t)#
\frac{\Gamma(d/2)} {\sqrt{\pi},\Gamma((d-1)/2)} \int_t^1(1-z^2)^{(d-3)/2},dz. } $$
当 \(t\in(0,1)\) 固定、\(d\to\infty\) 时，对积分作端点估计可得
只保留指数主项，可写为
$$ \boxed{ p_d(t)#
2^{,\frac d2\log_2(1-t^2)+O(\log d)}. } $$
上面的积分式由球面模型推导；指数规模与 Becker–Ducas–Gama–Laarhoven，SODA 2016，§2，Lemma 2.1，PDF 第 3 页 一致。这里的渐近式要求 \(t\) 固定；若 \(t\) 随维数趋近于 \(0\) 或 \(1\)，需要重新检查近似。
代入两向量等长约化的阈值 \(t=1/2\)，
$$ \boxed{ p_d(1/2)#
2^{-\frac12\log_2(4/3),d+O(\log d)} \approx 2^{-0.2075d}, } $$
最后一个近似省略了多项式因子。连续球面模型中，边界的概率为零，因此严格或非严格不等式给出同一概率。
若同时检查加法与减法，由对称性，
因子 \(2\) 不改变渐近指数，但在具体概率和操作计数中应保留。
6. 从约化概率到向量池规模#
先考虑一个理想化模型：固定一条长度为 \(R\) 的目标向量，另有 \(N\) 条同样长度、方向独立且球面均匀的候选向量，只检查相减。
记 \(p=p_d(1/2)\)，令 \(K\) 为能够约化目标的候选数量，则
这两个式子的要求不同：期望公式只需要每个候选的成功概率为 \(p\)；第二个式子还需要这些命中事件独立。
要让单个目标以常数概率找到伙伴，需要 \(Np\) 达到常数量级。因此，在这个模型中，
$$ N\asymp\frac1p#
(4/3)^{d/2+o(d)}#
2^{0.2075\ldots d+o(d)}. $$
这解释了经典两向量筛法中常见的向量池指数。覆盖更多目标、维持多轮缩短及控制失败概率，还需要相应分析和额外因子。原始球壳分析见 Nguyen–Vidick，§4.1，Lemma 4.1 及其后的复杂度讨论，PDF 第 14–16 页。
若对这样的向量池进行一次全对扫描，向量对检查次数为 \(\Theta(N^2)\)，其指数主项为
这只是全对扫描的成本尺度。近邻搜索和分桶要解决的问题，就是减少寻找可约化向量对所需的检查；完整筛法的时间还取决于采样、更新、轮数和具体实现。
7. 后续使用这些模型时需要保留什么#
进行筛法概率或成本分析时，至少保留以下信息：
- 维数与长度分布。 明确当前使用的 \(d\)，以及向量位于球面、球壳还是球体；长度不同时使用一般约化阈值。
- 条件与依赖。 进入同一桶、经过多层筛选或共享源向量后，联合分布可能改变，不能直接将无条件概率相乘。已两两约化的向量池还具有夹角限制，不能直接视为独立球面样本。
- 计数对象。 不同的可约化源向量对可能产生同一个新向量；重复命中的源向量对、新向量数量和向量池的更新进度需要分别计数。
- 近似精度。 渐近指数适合比较维数增长趋势；具体参数选择还需要球帽概率的有限维数值、长度分布及实现成本。
本文得到的长度与概率公式，将作为后续筛法分析的共同基础。下一篇《16 投影格、BKZ 与局部 SVP》说明这些量如何应用到投影格，并区分全格维数、块大小与实际筛法维数。