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

前置笔记：基本区域、格行列式与正交化、逐次极小值与 Minkowski 定理。

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

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

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

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

高斯启发式将这个平均密度用于估计具体区域 $K$ 中的格点数 [1, p. 7]。

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

这里的近似需要区域形状、尺度和格的几何结构适合该模型；行列式本身不能保证每个区域内的格点都按平均密度分布。

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

$$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}$ [1, sec. 2.2]。比较具体数值时需要先统一约定；这里也不把参考长度等同于某个随机格分布下的精确期望。

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

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

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

与已有内容的关系是：

• Minkowski 定理提供存在性保证。 将逐次极小值与 Minkowski 定理的凸体定理用于欧氏球，并令半径趋近临界值，可严格推出 $$\lambda_1(\Lambda)\le 2\operatorname{gh}(\Lambda).$$ 这是由球体积公式和 Minkowski 定理得到的推论 [2, p. 7]。
• 离散高斯指定采样分布。 离散高斯的 $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 的早期分析明确假设每轮相关向量在球壳内均匀分布 [3, p. 14]。

#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)}. }$$

上面的积分式由球面模型推导；指数规模与 BDGL 论文中的球帽估计一致 [4, p. 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}, }$$

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

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

$$\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 的球壳分析同时考虑列表规模、向量缩短与运行成本 [3, pp. 14–16]。

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

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

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

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

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

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

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

#参考文献