# 15 高斯启发式与随机球面模型

整理日期：2026-10-16。
适用范围：欧氏格筛法中的长度尺度、角度概率与向量池规模估计。
前置笔记：[02 基本区域、格行列式与正交化](/knowledge/fundamental-region-and-orthogonalization/)、[03 逐次极小值与 Minkowski 定理](/knowledge/successive-minima-and-minkowski/)。

设 $\Lambda\subseteq\mathbb R^d$ 是满秩格，记 $\Delta=\det(\Lambda)$，使用欧氏范数。本文的 $d$ 表示当前分析空间的维数，$N$ 表示向量池大小。

本篇连接三个问题：某个长度范围内有多少格向量；两条向量相减时有多大概率变短；为了持续找到可约化向量，需要多大的向量池。

## 1. 高斯启发式：用体积估计格点数

格的基本区域体积为 $\Delta$，因此格点的平均空间密度为 $1/\Delta$。

高斯启发式将这个平均密度用于具体区域 $K$，估计

$$
\#(\Lambda\cap K)
\approx
\frac{\operatorname{vol}(K)}{\Delta}.
$$

这里的近似需要区域形状、尺度和格的几何结构适合该模型；行列式本身不能保证每个区域内的格点都按平均密度分布。这个计数表述可参见 [G6K，EUROCRYPT 2019，§2.2，PDF 第 7 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)。

对于以原点为中心的球，定义非零向量计数

$$
N_\Lambda(r)
=
\#\{v\in\Lambda:0<\|v\|\le r\}.
$$

记 $d$ 维单位球体积为

$$
V_d=\frac{\pi^{d/2}}{\Gamma(d/2+1)},
$$

其中 $\Gamma$ 是 Gamma 函数。在适合采用体积估计的尺度上，常使用

$$
N_\Lambda(r)\approx\frac{V_dr^d}{\Delta}.
$$

这里已经排除零向量；当预计只有常数个非零向量时，这个表达只适合判断长度尺度，不能当作精确计数。中心对称性还意味着 $v$ 与 $-v$ 成对出现；若只计符号对 $\{\pm v\}$，数量应再除以 $2$。

## 2. 高斯启发式给出的参考长度

令球的体积等于一个基本区域的体积：

$$
V_dr^d=\Delta.
$$

本文将对应半径定义为高斯启发式参考长度

$$
\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)](https://ir.cwi.nl/pub/28539/2019-089.pdf)。比较具体数值时需要先统一约定；这里也不把参考长度等同于某个随机格分布下的精确期望。

用 $\operatorname{gh}(\Lambda)$ 归一化长度，可以得到简洁的计数形式：

$$
\boxed{
N_\Lambda\bigl(\alpha\operatorname{gh}(\Lambda)\bigr)
\approx \alpha^d.
}
$$

这说明：在该模型下，半径按固定比例增加，球内向量数会按维数指数增长。

与已有内容的关系是：

- **Minkowski 定理提供存在性保证。** 将第 03 篇的凸体定理用于欧氏球，并令半径趋近临界值，可严格推出
  $$
  \lambda_1(\Lambda)\le 2\operatorname{gh}(\Lambda).
  $$
  这是由球体积公式得到的推论，所用定理见 [Regev，Fall 2004，Lecture 1，§3.1，Theorem 9，PDF 第 7 页](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/introduction.pdf)。
- **离散高斯指定采样分布。** [第 09 篇](/knowledge/gaussian-functions-and-discrete-gaussians/)的 $D_{\Lambda,s}$ 按高斯权重分配概率；高斯启发式用于估计格点数量和长度尺度。二者不能相互替代。

## 3. 从球内模型到球面模型

把非零向量写成

$$
x=r u,\qquad r=\|x\|,\qquad
u=\frac{x}{\|x\|}\in S^{d-1},
$$

其中 $S^{d-1}$ 是 $\mathbb R^d$ 中的单位球面。这样可以分别描述长度 $r$ 与方向 $u$。

先考虑一个连续模型：$X$ 在半径为 $R$ 的球体内均匀分布。由体积比直接得到

$$
\Pr[\|X\|\le aR]=a^d,\qquad 0\le a\le1.
$$

因此，对固定 $\varepsilon\in(0,1)$，

$$
\Pr[(1-\varepsilon)R<\|X\|\le R]
=
1-(1-\varepsilon)^d
\longrightarrow1.
$$

高维球体的大部分体积集中在外层薄壳。同时，由旋转对称性，$X/\|X\|$ 在球面上均匀分布，且方向与长度独立。

薄壳集中描述了大多数样本的位置；对于指数级小概率事件，将所有长度直接替换成 $R$ 的误差仍需单独检查。

这些结论对上述连续均匀模型成立。把它用于筛法中的格向量池，需要额外假设：

1. **长度模型**：向量长度集中在某个半径附近，或服从指定的径向分布。
2. **方向模型**：归一化后的方向近似球面均匀。
3. **依赖模型**：在当前计算中，将哪些向量或事件视为独立。

高斯启发式的计数估计并不自动蕴含这三点。Nguyen–Vidick 的早期分析明确假设每轮相关向量在球壳内均匀分布；参见 [Nguyen–Vidick，2008，作者稿 §4.1，PDF 第 14 页的 Heuristic](https://people.csail.mit.edu/vidick/JoMC08.pdf)。

## 4. 两向量约化与 60° 阈值

设两条非零格向量 $x,y$ 的长度分别为 $a,b$，夹角为 $\theta$。由余弦定理，

$$
\|x-y\|^2
=
a^2+b^2-2ab\cos\theta.
$$

因此，对目标长度 $r$，

$$
\boxed{
\|x-y\|\le r
\iff
\cos\theta\ge
\frac{a^2+b^2-r^2}{2ab}.
}
$$

这给出了将长度条件转化为角度条件的基本公式。

当 $a=b=R$ 时，

$$
\|x-y\|<R
\iff
\cos\theta>\frac12
\iff
\theta<\frac{\pi}{3}.
$$

所以，**两条等长向量的夹角小于 $60^\circ$ 时，相减得到更短的向量**；等于 $60^\circ$ 时，新向量与原向量等长。

若同时允许 $x-y$ 和 $x+y$，则

$$
\min\{\|x-y\|,\|x+y\|\}<R
\iff
|\cos\theta|>\frac12.
$$

若要求从长度 $R$ 缩短到 $\gamma R$，其中 $0<\gamma<1$，相减对应的阈值进一步变为 $\cos\theta\ge1-\gamma^2/2$。

这些都是确定的几何关系。实际长度不同时，应代入 $a,b$ 计算阈值；只保存归一化方向会丢失这部分信息。筛法还需要排除重复或互为相反数的输入所产生的零向量。

## 5. 球帽概率：有多少方向满足约化条件

设 $d\ge2$，$U,V$ 是两个独立的球面均匀随机向量，记

$$
Z=\langle U,V\rangle=\cos\theta.
$$

由旋转对称性，可以固定 $U$。对阈值 $t\in(0,1)$，满足 $\langle U,V\rangle\ge t$ 的方向形成一个球帽，半张角为 $\arccos t$。

记其相对面积为

$$
p_d(t)=\Pr[Z\ge 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$ 时，对积分作端点估计可得

$$
p_d(t)
\sim
\frac{(1-t^2)^{(d-1)/2}}
{t\sqrt{2\pi d}}.
$$

只保留指数主项，可写为

$$
\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 页](https://ir.cwi.nl/pub/23692/23692.pdf) 一致。这里的渐近式要求 $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},
}
$$

最后一个近似省略了多项式因子。连续球面模型中，边界的概率为零，因此严格或非严格不等式给出同一概率。

若同时检查加法与减法，由对称性，

$$
\Pr[|Z|>1/2]=2p_d(1/2).
$$

因子 $2$ 不改变渐近指数，但在具体概率和操作计数中应保留。

## 6. 从约化概率到向量池规模

先考虑一个理想化模型：固定一条长度为 $R$ 的目标向量，另有 $N$ 条同样长度、方向独立且球面均匀的候选向量，只检查相减。

记 $p=p_d(1/2)$，令 $K$ 为能够约化目标的候选数量，则

$$
\mathbb E[K]=Np,
\qquad
\Pr[K\ge1]=1-(1-p)^N.
$$

这两个式子的要求不同：期望公式只需要每个候选的成功概率为 $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 页](https://people.csail.mit.edu/vidick/JoMC08.pdf)。

若对这样的向量池进行一次全对扫描，向量对检查次数为 $\Theta(N^2)$，其指数主项为

$$
N^2=2^{0.4150\ldots d+o(d)}.
$$

这只是全对扫描的成本尺度。近邻搜索和分桶要解决的问题，就是减少寻找可约化向量对所需的检查；完整筛法的时间还取决于采样、更新、轮数和具体实现。

## 7. 后续使用这些模型时需要保留什么

进行筛法概率或成本分析时，至少保留以下信息：

- **维数与长度分布。** 明确当前使用的 $d$，以及向量位于球面、球壳还是球体；长度不同时使用一般约化阈值。
- **条件与依赖。** 进入同一桶、经过多层筛选或共享源向量后，联合分布可能改变，不能直接将无条件概率相乘。已两两约化的向量池还具有夹角限制，不能直接视为独立球面样本。
- **计数对象。** 不同的可约化源向量对可能产生同一个新向量；重复命中的源向量对、新向量数量和向量池的更新进度需要分别计数。
- **近似精度。** 渐近指数适合比较维数增长趋势；具体参数选择还需要球帽概率的有限维数值、长度分布及实现成本。

本文得到的长度与概率公式，将作为后续筛法分析的共同基础。下一篇《16 投影格、BKZ 与局部 SVP》说明这些量如何应用到投影格，并区分全格维数、块大小与实际筛法维数。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [16 投影格、BKZ 与局部 SVP](/knowledge/projected-lattices-bkz-and-local-svp/)
- [17 筛法的基本框架与两向量约化](/knowledge/lattice-sieving-basics/)
- [18 Nguyen–Vidick、ListSieve 与 GaussSieve](/knowledge/nguyen-vidick-listsieve-and-gausssieve/)
- [19 筛法中的近邻搜索与分桶](/knowledge/nearest-neighbor-search-and-bucketing/)
- [20 角度 LSH 与多表搜索](/knowledge/angular-lsh-and-multiple-tables/)
- [21 球面 LSF 与过滤器](/knowledge/spherical-lsf-and-filters/)
- [25 渐进筛法与向量池复用](/knowledge/progressive-sieving-and-vector-pool-reuse/)