D_{x}(N) 系列问题的突破

· · 算法·理论

D_{x}(N) 系列问题的突破

我们熟知双曲线下点数和，即 \#\{(a,b):ab\le N\} 可以做到 \Theta(N^{1/3}\log N)，因为其凸壳上有这么多的点。
用该方法，a^{\alpha}b^{\beta}\le N 也可以更快的计算，我们记其答案为 D_{\alpha,\beta}(N)。

而三维的 D_{1,1,1}(N) 的 abc\le N，即 d_3(N) 只能用此方法做到 \widetilde O(N^{5/9})，不如 zak 筛。
一个大胆的想法是直接考虑三维凸壳，有 \widetilde O(\sqrt N) 个点，也能做到同样的时间复杂度。
这个方法的一个重大优势是在 D_{1,1,2}，可以做到 \widetilde O(N^{2/5})，也就是说 P11419 的 \pi(N)\bmod2 可以做到同样的这么快。

在 GPT 的持续推进下，D_{1,1,1} 做到了亚根号的 \widetilde O(N^{44/89})，打破了长久的认知。
似乎还能做到 \widetilde O(N^{32/65})，不过感觉没什么理论价值。

接下来两章就是 gpt 的神谕了，欢迎各位大神阅读（并理解+简化+合作写论文）。

D_{1,1,2}(N) 的独立 \widetilde O(N^{2/5}) 做法

记

D_{1,1,2}(N) =\#\{(a,b,c)\in\mathbb Z_{>0}^3:abc^2\le N\}.

这里的 \widetilde O 表示 O(\,\cdot\,\log^{O(1)}N)。下面给出的是一个理论上严格的位复杂度算法。它的“三维 SBT 筛”使用固定维凸半代数整数规划和 Barvinok 分解，所以与 zak 解析筛一样，主要意义是证明指数；它不是目前可直接参加 OI 的 divcnt1 式工程算法。

结论是

\boxed{D_{1,1,2}(N)=\widetilde O(N^{2/5}).}

1. 三维 SBT 筛

1.1 要解决的局部问题

设 K\subseteq\mathbb R^3 是一个有界凸集：

要求精确计算

\#(K\cap\mathbb Z^3).

令

P=\operatorname{conv}(K\cap\mathbb Z^3)

为 K 的整数凸包。因为 K 本身凸，所以

P\subseteq K, \qquad P\cap\mathbb Z^3=K\cap\mathbb Z^3. \tag{1}

因此只要构造 P，再数 P 中的格点即可。

1.2 整数凸包只有 O(V^{1/2}) 个面

Andrews 定理在 d 维给出

f_0(P)=O_d\!\left(\operatorname{Vol}(P)^{(d-1)/(d+1)}\right).

取 d=3，并用 P\subseteq B，得到

f_0(P)=O(V^{1/2}). \tag{2}

三维多面体的 1-骨架是平面图；由 Euler 公式，边数和面数也都是 O(f_0(P))。所以 P 的整个面格大小

h(P):=f_0(P)+f_1(P)+f_2(P)=O(V^{1/2}). \tag{3}

若 P 退化成二维或一维，就在它的仿射格上递归使用二维 SBT。设盒的三个边长均至少为 1；任意二维截面的面积至多为 O(XY+XZ+YZ)，二维 Andrews 界是面积的 1/3 次方，而

(XY)^{1/3},(XZ)^{1/3},(YZ)^{1/3}\le (XYZ)^{1/2}.

故退化情形也不会超过 (3)。

需要强调：Andrews 定理只证明输出大小，不能单独推出构造时间。下面的 normal-fan 遍历才是三维 SBT 筛的算法部分。

1.3 顶点 oracle

对任意有理方向 w\in\mathbb Q^3，定义

\operatorname{Vtx}(w) =\mathop{\mathrm{lexmax}}_{x\in K\cap\mathbb Z^3} w\cdot x. \tag{4}

先最大化 w\cdot x，再依次用三个坐标打破平局。返回点唯一，因此一定是 P 的一个顶点。

固定维凸半代数整数可行性可在输入位长的多项式时间内完成。对目标值二分，再做常数次字典序优化，便可在

L^{O(1)}

位运算内实现一次 (4)。这里维数、约束个数和多项式次数均为常数。

1.4 从一个顶点找出所有相邻顶点

对已经找到的顶点 v，考虑它的外法锥

\mathcal N(v) =\{w\in\mathbb R^3:w\cdot v\ge w\cdot x,\ \forall x\in P\}. \tag{5}

它有一个强分离 oracle。给定 w，计算 x=\operatorname{Vtx}(w)：

用六个仿射图

w_i=\pm1,\qquad |w_j|\le1

覆盖 \partial[-1,1]^3。每个

\mathcal N(v)\cap\{w_i=\pm1,\ |w_j|\le1\}

都是一个二维有理凸多边形。它的分离 oracle 已由上面给出。

现在在每张图中运行已知的二维 SBT/凸链二分：

  1. 用固定维“分离 \Rightarrow 线性优化”得到横、纵极点；
  2. 对一条候选弦 pq，沿弦的外法向做一次优化；
  3. 若最优点仍在直线 pq 上，则该弦已被证实；否则得到一个位于弧中间的新顶点，并递归处理 p r 与 r q。

每次查询或者发现一个新顶点，或者证实一条最终边。因此，一个有 k 条边的图只需

O(kL^{O(1)}) \tag{6}

时间。法锥的系数来自 v-x，坐标均在输入盒内；故所有分界线、交点和查询方向的位长仍是 L^{O(1)}。六张图去重后，就得到 \mathcal N(v) 的全部二维面。

三维对偶关系告诉我们：

\mathcal N(v)\text{ 的一个二维面} \quad\longleftrightarrow\quad P\text{ 中一条以 }v\text{ 为端点的边}. \tag{7}

设 w_F 是该法锥面的相对内部方向。w_F 在 P 上暴露出的面恰为一条边 [v,u]。加入等式

w_F\cdot x=w_F\cdot v

后，沿任意一个不与该边正交的坐标方向分别取极值，便得到两个端点，从而找到另一个端点 u。这仍只是常数次固定维整数优化。

从任意一个 \operatorname{Vtx}(w_0) 出发，对顶点图做 BFS，即可枚举 P 的全部顶点和边。由握手定理

\sum_v\deg(v)=2f_1(P)=O(h(P)),

所以法锥中被二维 SBT 处理的边数总和是 O(h(P))，总构造时间为

O(h(P)L^{O(1)})=O(V^{1/2}L^{O(1)}). \tag{8}

最后对已经列出的顶点跑一次普通三维凸包，代价 O(h(P)\log h(P))，不改变 (8)。

这就是本文所称的三维 SBT 筛：二维 SBT 遍历的对象不再是原曲线，而是每个整数凸包顶点的二维法锥截面；法锥的二维面给出相邻边，进而遍历整个三维整数凸包。

1.5 从凸包精确计数

对 P 的每个顶点取切锥，先把非单纯锥三角剖分。三维中所有顶点度数之和为 O(h(P))，故总共只有 O(h(P)) 个单纯锥。

再对每个单纯锥使用固定维 Barvinok 有符号幺模锥分解。每个锥产生 L^{O(1)} 项；用 Brion 公式相加并在 (1,1,1) 处取极限，得到 P\cap\mathbb Z^3 的精确大小。总时间仍为

O(h(P)L^{O(1)})=O(V^{1/2}L^{O(1)}). \tag{9}

结合 (1)，三维 SBT 筛得到局部结论：

\boxed{\#(K\cap\mathbb Z^3)=O(V^{1/2}\log^{O(1)}N).} \tag{10}

2. 把 D_{1,1,2} 分成小 c 与三维中心区

取截断

C=\lfloor N^{1/5}\rfloor.

2.1 小 c：调用已知的朴素 SBT 筛

设

D_{1,1}(M)=\#\{(a,b)\in\mathbb Z_{>0}^2:ab\le M\}.

已知 divcnt1/二维 SBT 筛满足

D_{1,1}(M)\text{ 的计算时间} =O(M^{1/3}\log^{O(1)}M).

于是

\begin{aligned} T_{\rm tail} &=\sum_{c\le C}O\!\left((N/c^2)^{1/3}\log^{O(1)}N\right)\\ &=O\!\left(N^{1/3}\log^{O(1)}N \sum_{c\le C}c^{-2/3}\right)\\ &=O\!\left(N^{1/3}C^{1/3}\log^{O(1)}N\right)\\ &=O\!\left(N^{2/5}\log^{O(1)}N\right). \tag{11} \end{aligned}

这一部分精确贡献为

\sum_{c=1}^{C}D_{1,1}\!\left(\left\lfloor\frac N{c^2}\right\rfloor\right).

2.2 大 c：倍增盒分块

只剩 c>C。由于有解时 c\le\sqrt N、a,b\le N，分别把

[1,N],\quad[1,N],\quad[C+1,\lfloor\sqrt N\rfloor]

分成端点比至多 2 的半开整数区间。考虑一个盒

B=[X,2X)\times[Y,2Y)\times[Z,2Z), \tag{12}

最后一段不足两倍时照常截断。

对边界盒，区间端点相差至多 2 倍，所以

XYZ^2\asymp N. \tag{13}

固定 X,Z 后，满足 (13) 的 Y 档只有 O(1) 个。因此边界盒总数为

O(\log^2 N). \tag{14}

3. 每个边界盒是一个三维凸集计数

在边界盒 B 中定义补集

K_B^+ =\{(x,y,z)\in B:xyz^2\ge N+1\}. \tag{15}

使用 N+1 而不是严格不等号，保证整数边界完全精确。盒内所求点数为

\#(B\cap\mathbb Z^3)-\#(K_B^+\cap\mathbb Z^3). \tag{16}

集合 (15) 是凸的。事实上，在正象限中可写成上图集

y\ge f(x,z):=\frac{N+1}{xz^2}.

其 Hessian 为

\nabla^2 f =f\begin{pmatrix} 2/x^2&2/(xz)\\ 2/(xz)&6/z^2 \end{pmatrix},

两个顺序主子式均为正，因为

\det(\nabla^2 f) =\frac{8f^2}{x^2z^2}>0.

故 f 严格凸，(15) 是凸集；它也可直接由常次数整数多项式不等式 xyz^2\ge N+1 和盒约束描述。

盒体积满足

V_B\asymp XYZ \overset{(13)}{\asymp}\frac N Z \le\frac N C =O(N^{4/5}). \tag{17}

将三维 SBT 筛 (10) 用于 K_B^+，单个边界盒耗时

O(V_B^{1/2}\log^{O(1)}N) =O(N^{2/5}\log^{O(1)}N). \tag{18}

再乘 (14) 的 O(\log^2N) 个盒，仍为

T_{\rm centre} =O(N^{2/5}\log^{O(1)}N). \tag{19}

4. 为什么截断正好是 N^{1/5}

更一般地令 C=N^\gamma。小 c 部分的指数为

\frac13+\frac\gamma3,

而三维中心区最大盒的体积是 N/C，三维 SBT 的指数为

\frac{1-\gamma}{2}.

令二者相等：

\frac13+\frac\gamma3=\frac{1-\gamma}{2} \quad\Longrightarrow\quad \gamma=\frac15,

共同指数为

\frac13+\frac1{15}=\frac25.

由 (11) 与 (19)，最终得到

\boxed{T_{D_{1,1,2}}(N)=O(N^{2/5}\log^{O(1)}N).}

空间复杂度为保存当前最大边界盒整数凸包所需的

O(N^{2/5}\log^{O(1)}N)

位；逐盒处理即可，无须同时保存所有盒。

5. 伪代码

D112(N):
    C <- floor(N^(1/5))
    ans <- 0

    for c = 1..C:
        ans += DivCnt1(floor(N / c^2))

    partition a, b, c>C into ratio-at-most-2 integer intervals
    for every box B = A x B x C_interval:
        lo <- min_{(a,b,c) in B} a*b*c^2
        hi <- max_{(a,b,c) in B} a*b*c^2

        if hi <= N:
            ans += number_of_integer_points(B)
        else if lo > N:
            continue
        else:
            Kplus <- {(a,b,c) in B : a*b*c^2 >= N+1}
            ans += number_of_integer_points(B) - SBT3_Count(Kplus)

    return ans

其中 SBT3_Count 的完整内容就是：顶点 oracle \to 二维 SBT 构造各顶点法锥 \to 沿法锥邻接 BFS 枚举整数凸包 \to 三维 Barvinok 精确计数。

6. 依赖的定理与资料

D_{1,1,1}(N) 的确定性亚平方根算法

本文给出三维除数计数函数

D_{1,1,1}(N) =\#\{(a,b,c)\in\mathbb Z_{>0}^3:abc\le N\} =\sum_{n\le N}d_3(n)

的一个自包含算法说明。全文除明确列出的公开定理外，不依赖其他研究笔记； 算法、误差认证和复杂度分析形成一条完整的证明链。

主定理。 在确定性位复杂度模型中，D_{1,1,1}(N) 可以在

\boxed{\widetilde O(N^{44/89})}

时间和同阶空间内精确计算。这里 \widetilde O 只隐藏固定次幂的

oracle。

所谓“精确计算”，是指先用向外舍入的实球计算得到一个包含

--- ## 1. 记号和计算模型 记 $$ e(t)=\exp(2\pi i t),\qquad x=N+\frac12. $$ 所有整数阈值均向有利于覆盖的方向取整；这只改变绝对常数。若 $A,B,C$ 是 dyadic 尺度，则 $a\asymp A$ 表示 $a$ 落在一个固定常数比 的平滑 dyadic 窗内。三个坐标始终是有标号的；分析中把尺度重排成 $A\le B\le C$，不等于限制整数满足 $a\le b\le c$。 本文采用下列约定。 1. 基本整数和实数的位长为 $O(\log N)$；乘法、除法、初等函数和球算术 的 polylog 位成本均吸收到 $\widetilde O$ 中。 2. 每个解析展开只取依赖最终误差指标的固定阶；这个阶数不随 $N$ 增长。 3. 一共有至多 $N^{O(1)}$ 个算术对象和 polylog 个尺度盒。因此，只要每个 局部尾项分配到 $N^{-E-C}$，取固定 $E>2$ 和足够大的固定 $C$，总误差 就小于 $N^{-E}$。 4. 以下复杂度论证只写充分大的 $N$。有限多个较小输入可由同一算法或 直接枚举处理，其成本吸收到大 $O$ 常数中。 --- ## 2. 使用的公开定理 本算法只把下列结果当作黑盒；这里给出实际调用所需的精确形式。 ### 2.1 固定维多面体带权求和 在固定维数中，可以用 Barvinok 有理生成函数在输入位长的多项式时间内 表示有理多面体的整数点生成函数。对次数为 $R$ 的多项式权，也可以在 $\operatorname{poly}(R,\text{输入位长})$ 时间求其整数点加权和。因此当 $R=\log^{O(1)}N$ 时，每个固定维多面体的带权和成本为 $\log^{O(1)}N$。 参考： [Barvinok 的固定维整数点算法](https://doi.org/10.1287/moor.19.4.769)， [固定维多项式权生成函数](https://www.math.ucdavis.edu/~deloera/RECENT_WORK/fptasNLIP.pdf)。 ### 2.2 双曲线整数包 对有理参数给出的双曲线上图集及其与常数条有理直线的裁剪， Alcántara、Blanco、Criado 和 Santos 的算法可以从任意中间横坐标开始， 用 $O(\log^2X)$ 次算术操作初始化，随后每个整数包顶点使用 $O(\log X)$ 次算术操作。相关链的顶点数为 $$ O(X^{1/3}\log X). $$ 平移、交换坐标和有理渐近线只改变输入位长中的 polylog 因子。 参考：[Integer hulls of convex sets and a special case of the hyperbola](https://arxiv.org/abs/2501.19193)。 完整标准链的匹配数量级见 [Balog--Bárány](https://arxiv.org/abs/2602.06897)；下界只说明逐顶点方法在 输出意义下最优，不参与本算法的上界证明。 ### 2.3 最小同时分母的矩 把一个固定二维紧矩形划成边长 $1/M$ 的半开方格。对每个格 $Q$，令 $d(Q)$ 为其中某个有理点 $(a/d,b/d)$ 的最小正公共分母。Marklof 的 Proposition 6 在二维离散网格、格宽 $1/M$ 的对角极限下给出：对任意 固定 $\alpha<3$， $$ \sum_Q d(Q)^\alpha=O(M^{2+2\alpha/3}). $$ 本文只使用 $$ \sum_Qd(Q)=O(M^{8/3}),\qquad \sum_Qd(Q)^2=O(M^{10/3}). \tag{2.1} $$ 固定矩形边界相交的 $O(M)$ 个格可直接处理，不影响这两个界。 参考：[Marklof, Smallest denominators](https://arxiv.org/abs/2310.11251)。 ### 2.4 任意系数二次指数和 Hiary 的 Theorem 2.1 能对任意实数 $\alpha,\beta$、整数 $K,j\ge0$，计算 $$ K^{-j}\sum_{k=0}^{K}k^j e(\alpha k+\beta k^2) $$ 到绝对误差 $\varepsilon$。其复杂度是 $\nu=(j+1)\log(K/\varepsilon)$ 的多项式，中间数长为 $O(\nu^2)$。 本文的 $j=\log^{O(1)}N$ 且 $\log(1/\varepsilon)=O(\log N)$，所以每次调用 均为 $\log^{O(1)}N$ 位成本。本文不调用该文的三次和算法。 参考：[Hiary, Fast methods to compute the Riemann zeta function](https://arxiv.org/abs/0711.5005)。 ### 2.5 短区间分解和 $d_3$ 输出界 Helfgott 的确定性短区间分解算法在 $Y\gg X^{1/3}\log^{2/3}X$ 时，可在 $\widetilde O(Y)$ 时间内分解 $(X,X+Y]$ 中的全部整数。Shiu 的短区间乘性函数定理给出，在本算法所需的 $Y\ge X^{1/4}$ 范围内， $$ \sum_{X<n\le X+Y}d_3(n)\ll Y\log^2X. \tag{2.2} $$ 参考： [Helfgott 的短区间分解](https://arxiv.org/abs/1712.09130)， [Shiu 的短区间定理](https://doi.org/10.1515/crll.1980.313.161)。 ### 2.6 参数一致的有限阶驻相 本文使用固定维、紧支撑、非退化驻点的有限阶驻相定理：若相位与振幅在 一个固定复邻域中一致解析，Hessian 一致非退化，则任意固定阶展开的系数 由有限 Taylor jet 显式给出，余项对全部外参数一致。所需系数可由复 Gaussian 矩递推计算，不作为 oracle。 参考：[Vasy 的驻相讲义](https://math.stanford.edu/~andras/205C-2.pdf)。 --- ## 3. 平滑分割和总体算法 取三个主参数 $$ H=N^{44/89},\qquad L_0=N^{43/178},\qquad A_0=N^{28/89},\qquad \delta=H/x. \tag{3.1} $$ 令 $\Phi$ 为标准正态分布函数，取 $$ \sigma=(D_0\log(2N))^{-1/2}, \tag{3.2} $$ 其中 $D_0$ 是后面按误差目标选定的固定常数。对所有 dyadic $A=2^k$ 定义 $$ w_A(t)= \Phi\!\left(\frac{\log(t/A)}\sigma\right) -\Phi\!\left(\frac{\log(t/(2A))}\sigma\right). \tag{3.3} $$ 于是 $w_A(t)\ge0$，且对每个 $t>0$ 有严格望远镜恒等式 $$ \sum_{A=2^k}w_A(t)=1. \tag{3.4} $$ 高斯尾允许只保留与 $[1,N]$ 相交的 polylog 个扩张尺度；丢弃部分的总 贡献可压到任意指定的 $N^{-d}$。每个 $w_A$ 的对数坐标导数均为 $\log^{O(1)}N$。 为使后面的 $ABC\asymp N$ 条件没有遗漏，先说明远离乘积边界的盒。把每个 Gaussian 窗在其常数比有效区间外的尾计入误差球后： - 若盒内所有 $abc$ 都满足 $abc\le xe^{-\delta L_s}$，则 (3.7) 可替换为 $1$，误差由 Gaussian 尾 控制；此时三维和分离成三个一维和。每个一维解析权用 polylog 次 多项式逼近，再用 Faulhaber 公式求幂和，成本为 polylog。 - 若盒内所有 $abc$ 都满足 $abc\ge xe^{\delta L_s}$，则 (3.7) 可替换为 $0$，同样只留下已认证的 Gaussian 尾。 - 其余盒与乘积边界相交，必有 $ABC\asymp x$，才交给第 6--9 节的解析 算法。 全部 dyadic 尺度组合仍只有 $\log^{O(1)}N$ 个，所以远离边界的整盒不会 改变总复杂度。 再定义平滑下截断 $$ U_T(t)=\Phi\!\left(\frac{\log(t/T)}\sigma\right). \tag{3.5} $$ 对每个三元组使用逐点恒等分割 $$ \begin{aligned} W_{\rm small}(a,b,c) &=1-U_{L_0}(a)U_{L_0}(b)U_{L_0}(c),\\ W_{\rm mid}(a,b,c) &=U_{L_0}(a)U_{L_0}(b)U_{L_0}(c) -U_{A_0}(a)U_{A_0}(b)U_{A_0}(c),\\ W_{\rm cen}(a,b,c) &=U_{A_0}(a)U_{A_0}(b)U_{A_0}(c). \end{aligned} \tag{3.6} $$ 三者非负且和为 $1$。小坐标段保留硬边界 $abc\le N$；中段和中央段计算 高斯平滑边界 $$ \Phi\!\left(\frac{\log(x/(abc))}{\delta}\right) =\Pr\{abc\le xe^{\delta Z}\},\qquad Z\sim N(0,1). \tag{3.7} $$ 因此 $$ \begin{aligned} D_{1,1,1}(N) ={}&\sum_{a,b,c\ge1}W_{\rm small}(a,b,c)1_{abc\le N}\\ &+\sum_{a,b,c\ge1} \bigl(W_{\rm mid}+W_{\rm cen}\bigr)(a,b,c) \Phi\!\left(\frac{\log(x/(abc))}{\delta}\right)\\ &+\sum_{a,b,c\ge1}U_{L_0}(a)U_{L_0}(b)U_{L_0}(c) \left[ 1_{abc\le N}- \Phi\!\left(\frac{\log(x/(abc))}{\delta}\right) \right]. \end{aligned} \tag{3.8} $$ 这是一条精确恒等式。以下分别计算三行，并把所有截断误差装入实球半径。 总体伪代码如下。 ```text CountD111(N): x <- N + 1/2 H, L0, A0, delta, sigma <- (3.1), (3.2) Ssmall <- SmallHardPart(N, L0, sigma) Smid <- 0 add all fully-inside separable mid boxes to Smid; discard certified upper tails for every remaining labelled dyadic box (A,B,C) intersecting abc ~ N: reorder only the three scales so that A <= B <= C if L0 <= A < A0: Smid += AStarBox(A,B,C, corresponding signed weights) Scen <- 0 add all fully-inside separable central boxes to Scen; discard certified upper tails for every remaining labelled dyadic box (A,B,C) intersecting abc ~ N: reorder only the three scales so that A <= B <= C if A >= A0: Scen += CentralFareyBox(A,B,C, corresponding weights) Corr <- ExactProductShellCorrection(N, H, L0, sigma) S <- Ssmall + Smid + Scen + Corr return the unique integer in the certified ball S ``` 式 (3.6) 中的差权拆成常数个可分离的带符号乘积。因此伪代码中的 “corresponding weights”不隐藏随 $N$ 增长的组合数。 --- ## 4. 乘积短壳：从平滑答案恢复硬答案 取 $$ L_s=\sqrt{C_s(d)\log(2N)} $$ 并只在 $$ xe^{-\delta L_s}\le m\le xe^{\delta L_s} \tag{4.1} $$ 内计算 (3.8) 的最后一行。该区间的整数长度为 $\widetilde O(x\delta)=\widetilde O(H)$。壳外用 $$ D_{1,1,1}(y)\le y(1+\log y)^2 \tag{4.2} $$ 和高斯尾界，选择足够大的固定 $C_s(d)$，即可把遗漏压到 $N^{-d}$。 本算法先用 Helfgott 算法分解 (4.1) 内的全部整数。若 $m=\prod p_i^{e_i}$，枚举每个 $e_i$ 在三个有标号因子中的全部分配，便得到 所有 $abc=m$。对每个三元组累加 $$ U_{L_0}(a)U_{L_0}(b)U_{L_0}(c) \left[ 1_{m\le N}-\Phi\!\left(\frac{\log(x/m)}\delta\right) \right]. \tag{4.3} $$ 由 (2.2)，全部枚举叶子的数量为 $\widetilde O(H)$；每个叶子只做 polylog 位球算术。因此 $$ T_{\rm shell}=\widetilde O(H). \tag{4.4} $$ 注意这一步是按乘积 $m$ 枚举一个短壳，不是筛到 $\sqrt N$。 --- ## 5. 小坐标段：双曲线整数包 令 $U=U_{L_0}$。为避免“至少一个坐标小”造成重计，使用严格恒等式 $$ 1-U(a)U(b)U(c) =(1-U(a))+U(a)(1-U(b))+U(a)U(b)(1-U(c)). \tag{5.1} $$ 三个带标号情形分别指定 $a,b,c$ 为第一个小坐标，因而没有容斥重叠。 以第一项为例，高斯尾允许把 $a$ 截断到 $a\le K_sL_0$，其中 $K_s=\log^{O(1)}N$；截断后误差小于 $N^{-d}$。 固定 $a$，令 $$ X=\left\lfloor\frac Na\right\rfloor. $$ 再用 (3.3) 把 $(b,c)$ 分成 dyadic 矩形。矩形内硬条件的补集 $$ bc\ge X+1 \tag{5.2} $$ 是凸的双曲线上图集。把它与矩形边界裁剪后，利用第 2.2 节算法枚举其 整数包顶点，再三角剖分。矩形内满足 $bc\le X$ 的带权和等于整个矩形的 带权和减去补集整数包的带权和。 出现在权中的 $U_T$ 和 $w_A$ 在常数比矩形的缩放坐标上解析。用次数 $R=\log^{O(1)}N$ 的 Chebyshev 多项式作一致复球逼近；把误差先除以粗点数 $N(1+\log N)^2$ 和盒数，即可使所有逼近误差之和小于 $N^{-d}$。每个 三角形上的多项式矩由第 2.1 节固定维带权生成函数精确求和。 三角剖分采用固定的半开边约定；共边只归属于一个三角形，所以边界格点不会 重复计数。 固定 $a$ 的顶点枚举和多面体求和成本为 $$ \widetilde O(1+X^{1/3}). $$ 三个带标号分支只有常数倍差异，所以 $$ \begin{aligned} T_{\rm small} &=\widetilde O\left( \sum_{a\le K_sL_0}\left(1+(N/a)^{1/3}\right) \right)\\ &=\widetilde O(N^{1/3}L_0^{2/3}+L_0) =\widetilde O(N^{44/89}). \end{aligned} \tag{5.3} $$ 这一步使用二维整数包，但没有使用 Pick 定理；三角片的整数点多项式矩由 生成函数计算。 --- ## 6. 单盒解析接口 A* 本节给出中段和中央段共同使用的 Poisson--驻相接口。固定一个尺度盒 $$ A\le B\le C,\qquad ABC\asymp x, \tag{6.1} $$ 其典型目标是 $$ S_{A,B,C} =\sum_{a,b,c\ge1} g_A(a)g_B(b)g_C(c) \Phi\!\left(\frac{\log(x/(abc))}{\delta}\right), \tag{6.2} $$ 其中 $g_A,g_B,g_C$ 是 $w_A,w_B,w_C$ 与常数个 $U_T$ 或 $1-U_T

的乘积。它们具有相同的解析性和导数界。

由 (3.7)，(6.2) 是

\mathbb E_Z\sum_{abc\le xe^{\delta Z}}g_A(a)g_B(b)g_C(c). \tag{6.3}

对内层三维格点和使用 Poisson 求和。先对第三坐标积分，并对每个非零 第三频率 h 做 R_c 次分部积分：

\begin{aligned} \int_0^Tg_C(c)e(-hc)\,dc ={}&-e(-hT)\sum_{r=0}^{R_c-1} \frac{g_C^{(r)}(T)}{(2\pi ih)^{r+1}}\\ &+(2\pi ih)^{-R_c} \int_0^Tg_C^{(R_c)}(c)e(-hc)\,dc. \end{aligned} \tag{6.4}

这里 T=xe^{\delta Z}/(ab)。对 a,b 再作 Poisson 后得到频率 (p,q,h)。

6.1 零频和非驻相频率

这些项均可直接逐个或按几何尾求和，成本只贡献 polylog 或低于后述主项。

6.2 同号频率的唯一驻点

只需写 p,q,h>0 的扇区；全负扇区由共轭给出。相位的唯一驻点满足

F=(yhpq)^{1/3},\qquad a_0=F/p,quad b_0=F/q,quad c_0=F/h,\qquad y=xe^{\delta Z}. \tag{6.5}

只有

p\asymp hC/A,\qquad q\asymp hC/B \tag{6.6}

时驻点落在盒内。令 a=a_0u,b=b_0v，归一化相位为

F\left(u+v+\frac1{uv}\right).

在 (u,v)=(1,1) 处 Hessian 为

\begin{pmatrix}2&1\\1&2\end{pmatrix},\qquad \det=3. \tag{6.7}

故第 r 个边界项的二维积分具有一致展开

\frac{-ia_0b_0}{\sqrt3F}e(-3F) \sum_{j=0}^{J_{\rm sp}-1}F^{-j} \mathcal D_j \left[ g_A(a_0u)g_B(b_0v) g_C^{(r)}\!\left(\frac{c_0}{uv}\right) \right]_{u=v=1}, \tag{6.8}

并乘上 (6.4) 的显式因子 -(2\pi ih)^{-r-1}。

对全部保留频率求和后，(6.8) 的截断余项为 $$ O(C^{1-J_{\rm sp}}\log^{O(1)}N). \tag{6.9} $$ ### 6.3 Gaussian 平均和 $h$ 截断 在 (6.8) 中 $$ F=F_xe^{\delta Z/3},\qquad F_x=(xhpq)^{1/3}. $$ 当 $h$ 超过 $$ h_{\max}=\widetilde O\left(\frac{AB}{H}\right), \tag{6.10} $$ 时，$Z$ 积分可通过复平移或对 $Z$ 分部积分压到 $N^{-d}$。在保留范围内， 由 (6.6) 有 $F\delta\ll\log N$，并且 $$ F\delta^2=O(N^{-1/2}\log^{O(1)}N). \tag{6.11} $$ 因此把 $e^{\delta Z/3}$ 在 $Z$ 中展开到固定 $J_Z$ 阶，所有 $Z$ 矩都化为 显式 Hermite--Gaussian 因子；尾项由 (6.11) 控制。 ### 6.4 横向二次和收费 固定 $h,q$ 后，$p$ 的有效区间长度为 $$ P\asymp hC/A. $$ 将它分成长度 $$ B_p\asymp\frac{P}{1+(hC)^{1/3}} \tag{6.12} $$ 的块。在每块上，相位保留到二次项；更高阶解析余项和振幅用 polylog 次 Taylor 展开。每一项成为任意实系数的多项式加权二次指数和， 由第 2.4 节算法在 polylog 位成本内求出。 固定 $h$ 的 $q$ 数量为 $\widetilde O(hC/B)$，每个 $q$ 的 $p$ 块数为 $\widetilde O(1+(hC)^{1/3})$。把 $h$ 求和到 (6.10)，并使用 $ABC\asymp N$， 得到单盒成本 $$ T_{A^*}(A,B,C) =\widetilde O\left(1+N^{4/3}A H^{-7/3}\right). \tag{6.13} $$ ### 6.5 固定阶误差预算 若要求每盒误差至多 $N^{-d}$，可显式取 $$ \begin{aligned} D_0&=\lceil8(d+10)\rceil,\\ R_c&=\lceil3d+12\rceil,\\ J_{\rm sp}&=\lceil3d+10\rceil,\\ K_Z&=\lceil2d+8\rceil,\\ K_{\rm ns}&=\left\lceil\frac{d+4}{43/178}\right\rceil,\\ J_Z&=\lceil2d+10\rceil. \end{aligned} \tag{6.14} $$ 相应的六类尾分别由 Gaussian 窗尾、$C^{3-R_c}$、$C^{1-J_{\rm sp}}$、 $\delta^{K_Z-2}$、$NA^{-K_{\rm ns}}$ 和 $N(N^{-1/2}\log^{O(1)}N)^{J_Z+1}$ 控制。因为中段 $A\ge L_0=N^{43/178}$，这些选择把每类尾压到 $N^{-d-3}$，且不会改变 任何 $N$ 的幂指数。 --- ## 7. 中段收费 中段满足 $$ L_0\lesssim A<A_0. $$ 把 $W_{\rm mid}$ 写成 (3.6) 中两个可分离乘积之差，并对每个尺度盒调用 A*。由于 (6.13) 随 $A$ 增长，dyadic 求和由 $A\asymp A_0$ 支配： $$ T_{\rm mid} =\widetilde O(N^{4/3}A_0H^{-7/3}) =\widetilde O(N^{44/89}). \tag{7.1} $$ --- ## 8. 中央段：同时最小分母与 Taylor--FFT 中央段 $A\ge A_0$。若继续直接使用 (6.13)，最坏收费仍然过大；下面把 驻相展开中 $(p,q,h)$ 的三重求和成批计算。 固定倍增块 $$ h\asymp T,\qquad T\le AB/H. \tag{8.1} $$ 由于尺度是 dyadic，可把常数因子吸收后令 $$ \kappa_1=C/A,\qquad \kappa_2=C/B $$ 为整数。定义归一化频率 $$ u=\frac p{\kappa_1h},\qquad v=\frac q{\kappa_2h}. \tag{8.2} $$ 由 (6.6)，$(u,v)$ 落在一个固定紧矩形。驻相相位严格写成 $$ F=R_\phi h(uv)^{1/3},\qquad R_\phi=(x\kappa_1\kappa_2)^{1/3}\asymp C. \tag{8.3} $$ 令 $$ M=\left\lceil(R_\phi T)^{1/3}\right\rceil,\qquad L=T/M. \tag{8.4} $$ ### 8.1 最小分母方格 把 $(u,v)$ 矩形切成边长 $1/M$ 的全局半开方格。在每个格 $Q$ 内选择 最小公共分母中心 $$ (u_0,v_0)=(a/d,b/d),\qquad d=d(Q). \tag{8.5} $$ Marklof 矩 (2.1) 给出 $$ \sum_Qd(Q)=O(M^{8/3}),\qquad \sum_Qd(Q)^2=O(M^{10/3}). \tag{8.6} $$ 中心可以按候选分母 $s=1,2,\ldots,d(Q)$ 试探并用整数区间交判断构造；全体构造成本 由第一矩控制。记分母恰在 $[D,2D)$ 的格数为 $A_D$，则还同时有 $$ A_D\le O(D^3),\qquad A_D\le O(M^{10/3}D^{-2}), \tag{8.7} $$ 第一式来自分母不超过 $2D$ 的有理点个数，第二式来自二阶矩。 ### 8.2 数字射线的无重参数化 对属于中心 $(a/d,b/d)$ 的频率定义 $$ \ell=dp-a\kappa_1h,\qquad m=dq-b\kappa_2h. \tag{8.8} $$ 固定剩余类 $h\equiv r\pmod d$ 后，$(\ell,m,r)$ 唯一确定一条数字射线； 反过来每个原频率三元组也唯一落入一个方格和一条射线。因此这是有限频率 集合的双射重排，没有近似和重计。 一个 $1/M$ 方格在 $h\asymp T$ 中允许的偏移数量分别为 $$ U_1=1+\kappa_1L,\qquad U_2=1+\kappa_2L,\qquad U=U_1U_2. \tag{8.9} $$ 每条射线与倍增块的交是一个整数区间。若 $d>T$，每个剩余类至多含一个 源点，直接求值；若 $d\le T$，用 dyadic range tree 把移动区间拆成 $O(\log T)$ 个标准结点。 ### 8.3 射线上的相位正规形 把 $$ s=\frac{\ell}{d\kappa_1},\qquad t=\frac{m}{d\kappa_2}. $$ 代回 (8.3)，在方格中心对 $(s/h,t/h)$ 作有限 Taylor 展开。线性项和 纯 $h$ 项合并后，精确相位可写成 $$ \alpha h+\beta+\frac{C_1}{h}+E(h),\qquad |C_1|\ll C_0:=R_\phi L^2\asymp CL^2. \tag{8.10} $$ 按 (8.4) 有 $R_\phi T/M^3\asymp1$，故三阶及以上的余项 $E(h)$ 在一个 宽度 $1/\log^{O(1)}N$ 的复带中一致有界解析。式 (6.8) 的振幅、固定阶 微分算子以及 Gaussian 因子在同一缩放变量中也一致解析。张量 Chebyshev 截断到 $O(\log^2N)$ 次后，它们成为 polylog 个 $$ \text{只依赖源 }h\quad\times\quad \text{只依赖目标 }(Q,\ell,m,r) $$ 的乘积，所有截断误差总和可压到 $N^{-d}$。 固定 $(d,r)$ 后，需要批量计算的纯核因此化为 $$ \sum_n c_n e\!\left(\xi_1n+\xi_2\frac{T}{r+dn}\right). \tag{8.11} $$ ### 8.4 Taylor--FFT 引理 考虑一般双线性相位 $sx$。若源变量跨度为 $X$、目标变量跨度为 $S$，取 长度 $$ K=2^{\lceil\log_2(8(1+XS))\rceil} $$ 的对偶网格，把 $x$ 和 $s$ 写成最近格点加余数。相位 $sx$ 分解为一个 $K$ 点 DFT 相位与三个绝对值有界的余数乘积。将三个余数指数分别截断到 $$ q=O(\log(\|c\|_1/\varepsilon)) $$ 阶，便只需 polylog 次普通 FFT，误差至多 $\varepsilon$。二维张量化给出 $$ \widetilde O(P+Q+(1+X_1S_1)(1+X_2S_2)) \tag{8.12} $$ 的成本，其中 $P,Q$ 是源和目标的个数。 对 (8.11)，两个方向可取 $$ X_1\asymp T/d,quad S_1\asymp1,\qquad X_2\asymp1,quad S_2\asymp C_0/T. \tag{8.13} $$ 在 range tree 的一个长度 $K'$ 的结点上，第二源跨度进一步只有 $O(dK'/T)$。对同一层的结点和所有剩余类求和后，固定 FFT 网格的总成本为 $\widetilde O(T+C_0)$，而不是每个移动区间各付一次整网格。 ### 8.5 按分母收费 设最小分母为 $d$ 的方格数为 $n_d$。输出数量由 (8.9) 控制；结合 $d\le T$ 的 range tree 和 $d>T$ 的单源分支，分母 $d$ 的收费统一为 $$ \widetilde O\left( d n_dU+\min(C_0,n_dUT) \right). \tag{8.14} $$ 第一项由第一矩求和： $$ U\sum_Qd(Q)=O(UM^{8/3}). \tag{8.15} $$ 第二项在分母倍增段 $D\le d<2D$ 上，由 (8.7) 满足 $$ \min(DC_0,UT A_D) \le C_0^{2/3}(UTM^{10/3})^{1/3}. \tag{8.16} $$ 式 (8.16) 可直接由两上界的几何插值验证；所有分母段只增加 $O(\log M)$ 因子。 ### 8.6 一般 $T$ 的八项成本 把 $$ M\asymp(CT)^{1/3},\quad L=T/M,quad U=(1+(C/A)L)(1+(C/B)L),\quad C_0\asymp CL^2 $$ 代入 (8.15)--(8.16)，展开 $U$ 的四项，得到输出成本 $$ \begin{aligned} Q_0(T)&=C^{8/9}T^{8/9},\\ Q_A(T)&=C^{14/9}A^{-1}T^{14/9},\\ Q_B(T)&=C^{14/9}B^{-1}T^{14/9},\\ Q_{AB}(T)&=C^{20/9}(AB)^{-1}T^{20/9}, \end{aligned} \tag{8.17} $$ 以及固定 FFT 网格成本 $$ \begin{aligned} B_0(T)&=C^{16/27}T^{43/27},\\ B_A(T)&=C^{22/27}A^{-1/3}T^{49/27},\\ B_B(T)&=C^{22/27}B^{-1/3}T^{49/27},\\ B_{AB}(T)&=C^{28/27}(AB)^{-1/3}T^{55/27}. \end{aligned} \tag{8.18} $$ 这一步没有假设 $L\ge1$。当 $L<1$ 时，$U_1,U_2$ 中的常数项自动保留， 而 $d>T$ 已由单源分支覆盖。八个 $T$ 指数全部为正，因此所有倍增块的和 由顶块 $$ T=AB/H \tag{8.19} $$ 支配。 利用 $ABC\asymp N$，(8.17) 在顶块变为 $$ \begin{aligned} Q_0&=(N/H)^{8/9},\\ Q_A&=N^{14/9}A^{-1}H^{-14/9},\\ Q_B&=N^{14/9}B^{-1}H^{-14/9},\\ Q_{AB}&=CN^{11/9}H^{-20/9}, \end{aligned} \tag{8.20} $$ 而 (8.18) 变为 $$ \begin{aligned} B_0&=N^{43/27}C^{-1}H^{-43/27},\\ B_A&=N^{49/27}C^{-1}A^{-1/3}H^{-49/27},\\ B_B&=N^{49/27}C^{-1}B^{-1/3}H^{-49/27},\\ B_{AB}&=N^{46/27}C^{-2/3}H^{-55/27}. \end{aligned} \tag{8.21} $$ --- ## 9. 中央段指数核算 写 $$ A=N^a,\qquad B=N^b,\qquad C=N^c. $$ 忽略常数比误差，有 $$ a+b+c=1,\qquad a\le b\le c,\qquad a\ge\frac{28}{89}. \tag{9.1} $$ 于是 $$ c\le1-2a\le\frac{33}{89},\qquad c+\frac a3\ge\frac49,\qquad c\ge\frac13. \tag{9.2} $$ 把 $H=N^{44/89}$ 和 (9.2) 代入 (8.20)，四项指数依次不超过 $$ \frac{40}{89},\qquad \frac{42}{89},\qquad \frac{42}{89},\qquad \frac{44}{89}. \tag{9.3} $$ 例如最后一项的指数为 $$ c+\frac{11}{9}-\frac{20}{9}\frac{44}{89} =c+\frac{11}{89} \le\frac{44}{89}. $$ 同理，(8.21) 的四项指数依次不超过 $$ \frac{42}{89},\qquad \frac{379}{801},\qquad \frac{379}{801},\qquad \frac{380}{801}, \tag{9.4} $$ 全部严格低于或等于 $44/89$。dyadic 尺度、$h$ 块、分母块和固定阶展开 只产生 polylog 因子。因此 $$ T_{\rm cen}=\widetilde O(N^{44/89}). \tag{9.5} $$ --- ## 10. 参数优化为何得到 $44/89

令一般参数为

H=N^\rho,\qquad L_0=N^\ell,\qquad A_0=N^\alpha.

四个主模块给出以下必要收费约束。

  1. 短壳：\rho。
  2. 小坐标段：1/3+2\ell/3\le\rho，故可取 \ell=\frac{3\rho-1}{2}. \tag{10.1}
  3. 中段 A*：4/3+\alpha-7\rho/3\le\rho，故至多取 \alpha=\frac{10\rho-4}{3}. \tag{10.2}
  4. 中央段最坏项 Q_{AB}。由 c\le1-2\alpha，要求 1-2\alpha+\frac{11}{9}-\frac{20\rho}{9}\le\rho. \tag{10.3}

将 (10.2) 代入 (10.3)，得到

\frac{44}{9}-\frac{80\rho}{9}\le\rho,

即

\rho\ge\frac{44}{89}. \tag{10.4}

取等号时，(10.1)--(10.2) 正好给出

\ell=\frac{43}{178},\qquad \alpha=\frac{28}{89},

也就是 (3.1)。其余中央八项已由第 9 节验证不成为新瓶颈。故

收费体系内部的最优平衡；本文不声称它是所有可能算法的下界。 --- ## 11. 正确性证明 ### 引理 11.1：三段与短壳合并后等于硬计数 式 (3.6) 逐点和为 $1$。对 $W_{\rm small}$ 使用硬指示函数；对另外两段 使用 (3.7)，再加上 (3.8) 最后一行，逐个三元组的系数恰为 $1_{abc\le N}$。壳外只丢弃显式高斯尾，并记录在误差球中。因此三段结果 与修正之和包含精确的 $D_{1,1,1}(N)$。 ### 引理 11.2：小坐标段无漏计、无重计 式 (5.1) 是逐点恒等式，给每个三元组唯一的第一个小坐标分支。固定该 坐标后，矩形减去 (5.2) 的整数包，恰好留下 $bc\le X$ 的全部格点。 整数包和三角剖分只改变求和表示，不改变格点集合。多项式逼近误差由球 半径覆盖。 ### 引理 11.3：A* 返回单盒平滑和的认证球 对紧支撑解析权，Poisson 求和成立。式 (6.4) 是有限次精确分部积分恒等式； 零频、非驻相频率和同号驻相频率穷尽全部频率。式 (6.8) 的有限阶余项、 $h$ 截断和 Gaussian Taylor 尾分别由 (6.9)--(6.14) 覆盖。Hiary 算法只 改变有限横向和的求值方式，并按指定误差返回近似。因此 A* 的输出球包含 (6.2)。 ### 引理 11.4：中央批处理与 A* 的保留频率和相同 半开方格给每个 $(u,v)$ 唯一归属；最小分母中心选取确定。式 (8.8) 在 固定剩余类上是双射，所以没有丢失或重复频率。Chebyshev 分离、 Taylor--FFT 和 range tree 只批量求同一有限和；每个截断误差均向外加入 球半径。$d>T$ 的单源分支和 $d\le T$ 的 range-tree 分支覆盖所有分母， $L<1$ 时也成立。因此中央算法返回与逐项 A* 相同的认证球。 ### 定理 11.5：算法输出精确答案 由引理 11.1--11.4，最终实球包含 $D_{1,1,1}(N)$。第 12 节选择精度使其 半径小于 $1/2$，故球中只有一个整数，取该整数即得到精确答案。 --- ## 12. 位精度、时间和空间 设全部盒、目标、FFT 网格和固定展开项的个数有粗界 $N^{C_1}$，全部中间 量的绝对值有粗界 $N^{C_2}$；$C_1,C_2$ 是与 $N$ 无关的固定常数。先选 固定 $E>2$，再在 (6.14) 中令 $$ d=E+C_1+20. \tag{12.1} $$ 外层复球使用至少 $$ p\ge(E+C_1+2C_2+20)\log_2N \tag{12.2} $$ 位尾数，并把每类窗口、Taylor、Chebyshev、驻相、非驻相和 FFT 误差 分配为至多 $N^{-E-C_1-10}$。全部误差和小于 $N^{-E}<1/2$。 Hiary 子程序所需的 $O(\nu^2)=\log^{O(1)}N$ 位数长可能高于 (12.2) 的 最低值，但仍只贡献 polylog 因子。 各模块的时间为 $$ \begin{array}{c|c} \text{模块}&\text{位复杂度}\\ \hline \text{小坐标整数包}&\widetilde O(N^{44/89})\\ \text{中段 A*}&\widetilde O(N^{44/89})\\ \text{中央 Farey--Taylor--FFT}&\widetilde O(N^{44/89})\\ \text{乘积短壳修正}&\widetilde O(N^{44/89}) \end{array} $$ 所以总时间为 $$ \boxed{\widetilde O(N^{44/89})}. \tag{12.3} $$ 逐盒处理并及时释放临时数组时，最大对象是中央块的源、目标或 FFT 网格； 它们已包含在第 9 节的收费中。因此空间同样可取 $$ \boxed{\widetilde O(N^{44/89})}. \tag{12.4} $$ --- ## 13. 更细的实现伪代码 ### 13.1 小坐标部分 ```text SmallHardPart(N, L0, sigma): ans <- 0-ball for branch in [(1-U(a)), U(a)(1-U(b)), U(a)U(b)(1-U(c))]: t <- the designated small coordinate of this branch for t <= Ks*L0: X <- floor(N/t) for every dyadic rectangle of the other two coordinates: P <- rectangle intersect {uv >= X+1} enumerate the integer hull vertices of P triangulate P approximate all analytic weights by certified polynomials ans += weighted sum over rectangle ans -= weighted sums over the hull triangles add all Gaussian truncation radii to ans return ans ``` ### 13.2 A* 单盒 ```text AStarBox(A,B,C,weights): form the Gaussian expectation of the hard box count apply 3-dimensional Poisson summation evaluate the zero frequency integrate the c-coordinate by parts Rc times bound all nonstationary sectors after Kns integrations for r < Rc and j < Jsp: retain h <= polylog(N)*AB/H form the explicit stationary-phase coefficient D_j expand the Z dependence to order Jz for each (h,q) range: split p into blocks of length (6.12) evaluate the resulting weighted quadratic sums with Hiary's algorithm add every analytic and numerical remainder radius return the resulting complex ball's real part ``` ### 13.3 中央盒 ```text CentralFareyBox(A,B,C,weights): form the same fixed-order A* expansion for every dyadic h-block T <= AB/H: M <- ceil((C*T)^(1/3)); L <- T/M partition the normalized (u,v)-domain into half-open 1/M cells find one minimum-denominator centre (a/d,b/d) in every cell for every centre and residue r mod d: parameterize all frequencies by the unique offsets (ell,m) if d > T: evaluate the at-most-one source directly else: insert its active h-interval into a dyadic range tree at every range-tree node: Chebyshev-separate source and target factors evaluate the curve kernel by Taylor-grid 2D FFTs accumulate outward-rounded errors return the certified real ball ``` ### 13.4 短壳修正 ```text ExactProductShellCorrection(N,H,L0,sigma): I <- [x*exp(-delta*Ls), x*exp(delta*Ls)] intersect integers factor every integer m in I by deterministic short-interval factoring ans <- 0-ball for m in I: for every ordered factorization a*b*c = m: ans += U_L0(a) U_L0(b) U_L0(c) * (1[m <= N] - Phi(log(x/m)/delta)) add the certified outside-shell Gaussian tail return ans ``` --- ## 14. 结论的范围 本文证明的是一个确定性的位复杂度上界和可实现的认证算法。公开定理只在 第 2 节列出的形式下使用；其余步骤均已给出有限展开阶数、误差分配和收费。 特别地： - 不把三维 Pick 定理当作工具；小坐标段只在二维切片上使用双曲线整数包， 多项式矩由固定维生成函数计算。 - 不假设“一般三次指数和可以快速算”；中段只调用任意系数二次和，中央段 使用最小分母、数字射线和普通 FFT。 - 不把浮点近似当作精确答案；所有近似均进入向外舍入球，最终靠唯一整数 恢复答案。 - $44/89$ 是本文组合方法的平衡点，不是问题本身的条件下界。