Disproving the quasi-uniformity of the Halton sequences and of some Halton-type sequences

Each language version is independently generated for its own context, not a direct translation.

这篇文章主要讲了一个关于**“如何把点均匀地撒在空间里”**的数学故事。虽然标题看起来很吓人（涉及“拟均匀性”、“Halton 序列”等术语），但我们可以用一个生动的比喻来理解它的核心内容。

🍕 核心比喻：撒芝麻的艺术家

想象你是一位披萨大师，你的任务是在一个正方形的披萨盒（代表数学中的 $[0,1]^d$ 空间）里撒芝麻（代表数据点）。

目标：你希望芝麻撒得既均匀又不重叠。
- 均匀：盒子里任何地方都不能有“空荡荡”的死角（这叫做覆盖半径，Covering Radius）。
- 不重叠：芝麻之间也不能挤得太近，否则就粘在一起了（这叫做分离半径，Separation Radius）。
- 完美状态（拟均匀性）：如果随着你撒的芝麻越来越多，它们既能填满所有空隙，又能保持彼此间距适中，就像完美的网格一样，那就叫**“拟均匀”**。
主角：Halton 序列
- 在数学界，Halton 序列（以及它的亲戚 Faure 序列、Sobol 序列）是著名的“撒芝麻大师”。它们被设计用来在计算机模拟中生成非常均匀的随机点，常用于计算复杂的积分或模拟物理现象。
- 大家一直认为：只要维度够高，这些序列撒出来的芝麻就是完美的“拟均匀”分布。

🚫 这篇文章的发现：大师也有“手抖”的时候

这篇文章（由 Goda, Hofer 和 Suzuki 三位作者撰写）做了一个**“打假”**工作。他们证明了：

Halton 序列并不是完美的“拟均匀”撒芝麻大师！

具体来说，他们发现：

当维度 $d \ge 2$ （也就是在二维平面或更高维空间）时，Halton 序列撒出来的点，虽然能很好地填满空间（没有大空隙），但是有些芝麻会靠得异常近。
这种“靠得太近”的现象，比理论预期的最优速度还要快。也就是说，随着点数 $N$ 增加，点与点之间的最小距离缩小得太快了，导致它们在某些地方“挤作一团”。
结论：因为存在这种“过度拥挤”的情况，Halton 序列不是拟均匀的。

🔍 他们是怎么发现的？（简单的逻辑）

作者们没有用复杂的计算机模拟，而是用了数学推导（就像用逻辑推理来预测披萨上的芝麻分布）：

寻找“双胞胎”：他们构造了特殊的两个数字 $n$ 和 $m$ ，这两个数字在 Halton 序列的生成规则下，会生成两个位置非常非常接近的点。
证明距离过近：通过数学公式（利用数论中的欧拉定理等工具），他们证明了这两个点之间的距离，会随着总点数 $N$ 的增加，以比 $1/N^{1/d}$ 更快的速度缩小。
打破幻想：既然存在这样“挤在一起”的点，那么“拟均匀性”这个完美的标签就被撕掉了。

🧩 扩展：不仅仅是 Halton

文章还顺带“打击”了 Halton 序列的亲戚们：

Faure 序列（一种在有限域上定义的序列）：也被证明不是拟均匀的。
Sobol 序列（在二维情况下）：之前已经被证明有问题，这篇文章用新的角度（Halton 类型的视角）再次确认了这一点。

💡 这对我们意味着什么？

理论上的修正：以前大家觉得 Halton 序列是“全能冠军”，现在知道它在“点与点间距”这个指标上是有缺陷的。
实际应用的影响：
- 如果你只是用 Halton 序列做积分计算（算面积、算体积），它依然非常优秀，因为它的“均匀性”（覆盖能力）很好。
- 但是，如果你用它来做散点数据插值（比如用稀疏的点去预测整个区域的温度分布，或者在机器学习中做采样），这种“点挤在一起”的缺陷可能会导致计算结果不稳定，或者误差变大。这时候，你可能需要换一种更“拟均匀”的序列。

📝 总结

这就好比：

以前我们以为 Halton 序列是**“完美的撒芝麻机”，撒出来的芝麻既均匀又疏密得当。
现在这篇文章告诉我们：“不，它在某些维度下，撒出来的芝麻会莫名其妙地挤成一团，虽然整体看着挺满，但局部太拥挤了。”**

这是一个关于**“完美并不存在”**的数学发现，提醒我们在选择数学工具时，要看清它的具体优缺点，而不是盲目迷信它的“低差异”名声。

Each language version is independently generated for its own context, not a direct translation.

这是一篇关于低差异序列（Low-discrepancy sequences）几何性质的学术论文的详细技术总结。

论文标题

推翻 Halton 序列及部分 Halton 型序列的准均匀性 (Disproving the Quasi-uniformity of the Halton Sequences and of Some Halton-type Sequences)

作者：Takashi Goda, Roswitha Hofer, Kosuke Suzuki
日期：2026 年 3 月 6 日

1. 研究背景与问题 (Problem)

背景：

Halton 序列是数值积分和拟蒙特卡洛方法中最著名的低差异序列之一，在 $d$ 维单位立方体 $[0, 1]^d$ 中定义。
在散乱数据逼近（如径向基函数近似）中，点集的几何性质（如覆盖半径和分离半径）比差异度（discrepancy）更为关键，直接影响近似误差界和数值稳定性。
准均匀性 (Quasi-uniformity) 是衡量点集几何质量的重要指标。一个点集序列被称为准均匀的，如果其覆盖半径 $h(P_N)$ 和分离半径 $q(P_N)$ 的比值有界。理论上，对于 $N$ 个点，这两个半径的最优衰减率均为 $N^{-1/d}$ 。

核心问题：

已知 Halton 序列的覆盖半径 $h(P_N)$ 达到了最优衰减率 $O(N^{-1/d})$ 。
然而，Halton 序列的分离半径 $q(P_N)$ 是否也达到最优衰减率 $O(N^{-1/d})$ 尚不清楚。
如果分离半径衰减得比 $N^{-1/d}$ 更快（即点与点之间过于拥挤），则序列不是准均匀的。
尽管数值实验（如图 1 所示）暗示 Halton 序列在 $d \ge 2$ 时可能不是准均匀的，但此前缺乏理论证明。

研究目标：

从理论上证明：对于任意维度 $d \ge 2$ 和任意互质底数，Halton 序列不是准均匀的。
推广结论：证明某些Halton 型序列（包括 $p$ 维 Faure 序列）也不是准均匀的，并提供新的证明视角。

2. 方法论 (Methodology)

作者采用了构造性证明的方法，通过寻找序列中特定的点对，证明它们之间的距离（分离半径）衰减速度超过了 $N^{-1/d}$ 。

2.1 针对经典 Halton 序列 (第 2 节)

核心思路：构造两个索引 $n$ 和 $m$ ，使得它们在 Halton 序列中的对应点 $x_n$ 和 $x_m$ 非常接近。
数学工具：
- 欧拉定理 (Euler's Theorem)：利用底数 $b_1$ 的欧拉函数 $\phi(b_1)$ 构造同余关系。
- 引理 1 (Lemma 1)：证明若 $p \equiv 1 \pmod q$ ，则 $pq^k - 1$ 能被 $q^{k+1}$ 整除。这是构造特定索引的关键。
- 命题 1 (Proposition 1)：构造特定的 $n$ $n$ 和 $m$ $m$ ，使得它们在各个底数 $b_j$ $b_{j}$ 下的根逆函数 $\phi_{b_j}$ $ϕ_{b_{j}}$ 的值非常接近。
  - 对于 $j \ge 2$ ，利用 $n$ 和 $m$ 在 $b_j$ 进制下前几位数字相同来限制距离。
  - 对于 $j=1$ ，利用二项式展开和引理 1 控制距离。
- 命题 2 (Proposition 2)：利用狄利克雷同时逼近定理 (Dirichlet's simultaneous approximation theorem)，证明存在整数系数，使得不同底数下的距离上界能够平衡（即所有维度的距离衰减率一致）。
推导过程：
- 定义 $N$ 和特定的索引 $n, m < N$ 。
- 计算两点间的欧几里得距离 $\|x_n - x_m\|$ 。
- 证明该距离的上界为 $O(N^{-1/d} (\log N)^{-1/(d(d-1))})$ 。
- 由于 $(\log N)$ 项的存在，该衰减速度严格快于 $N^{-1/d}$ ，从而证明分离半径 $q(P_N)$ 不满足准均匀性要求。

2.2 针对 Halton 型序列 (第 3 节)

背景：Halton 型序列基于有限域 $\mathbb{F}_p$ 上的多项式环 $\mathbb{F}_p[X]$ 定义，是 Hofer 提出的概念。
核心思路：利用多项式环中的代数性质（如 $(a+b)^p = a^p + b^p$ ）构造索引。
数学工具：
- 定义 1 & 2：引入 $b(X)$ -adic 根逆函数和 Halton 型序列的定义。
- 引理 2 (Lemma 2)：若多项式 $b(X)^\ell$ 整除 $(n(X) - m(X))$ ，则对应的点距离 $\le p^{-e\ell}$ 。
- 具体案例构造：
  1. $d=2$ 情况：构造 $n_1, n_2$ 使得在 $b_1(X)$ 和 $b_2(X)$ 下距离极小。
  2. $d=3, p=2$ 情况：对应三维 Sobol' 序列，利用多项式 $X, X+1, X^2+X+1$ 构造。
  3. $d=p$ 情况：对应 $p$ 维 Faure 序列。利用 $X^{p-1}-1$ 的根性质构造索引，证明分离半径衰减率为 $O(N^{-1/(p-1)})$ 。

3. 主要结果 (Key Results)

3.1 定理 1 (Theorem 1)：Halton 序列非准均匀

结论：对于任意维度 $d \ge 2$ 和任意互质底数 $b_1, \dots, b_d$ ，Halton 序列不是准均匀的。
定量结果：存在常数 $c > 0$ ，使得对于无穷多个 $N$ ，分离半径满足：
$q(P_N) \le \frac{c}{N^{1/d} (\log N)^{1/(d(d-1))}}$
意义：这推翻了 Halton 序列在 $d \ge 2$ 时具有准均匀性的假设。虽然其覆盖半径是最优的，但点集内部存在“过密”区域，导致分离半径衰减过快。

3.2 定理 2 (Theorem 2)：Halton 型序列非准均匀

结论：证明了以下三类 Halton 型序列不是准均匀的：
1. 二维情况： $b_1(X) = X+a, b_2(X) = X+a+1$ （包含 Faure 序列的二维投影）。
2. 三维情况 ( $p=2$ )：对应三维 Sobol' 序列。
3. $p$ 维情况： $p$ 维 Faure 序列（底数为 $p$ ）。
定量结果：对于上述情况，分离半径满足 $q(P_N) \le c N^{-1/(d-1)}$ （对于 Faure 序列， $d=p$ 时衰减率为 $N^{-1/(p-1)}$ ）。
对比：最优衰减率应为 $N^{-1/d}$ 。由于 $1/(d-1) > 1/d$，这些序列的分离半径衰减速度远快于最优速率，因此严重偏离准均匀性。

3.3 覆盖半径性质

作者还证明了 Halton 型序列的覆盖半径 $h(P_N)$ 依然保持最优衰减率 $O(N^{-1/d})$ 。因此，准均匀性的失效完全由分离半径的过快衰减引起。

4. 贡献与意义 (Contributions & Significance)

理论突破：
- 首次从理论上严格证明了 Halton 序列在 $d \ge 2$ 时不是准均匀的。此前这一结论仅基于数值实验的猜想。
- 填补了低差异序列几何性质研究中的空白，特别是关于分离半径的理论界限。
应用指导：
- 在散乱数据逼近（如径向基函数插值）中，准均匀性对于保证插值矩阵的条件数和收敛性至关重要。
- 该结果表明，在高维数值积分中表现优异的 Halton 序列，直接用于散乱数据逼近时可能不是最佳选择，因为其点分布不够均匀（存在局部过密）。
- 这解释了为什么在某些应用中需要寻找替代方案（如网格点、特定的拟蒙特卡洛点集或经过优化的序列）。
方法论创新：
- 将数论工具（欧拉定理、狄利克雷逼近）与多项式环代数（有限域上的多项式运算）结合，为分析低差异序列的几何性质提供了新的分析框架。
- 为 Faure 序列和 Sobol' 序列的非准均匀性提供了替代证明（Alternative proof），特别是从 Halton 型序列的角度重新审视了 Faure 序列。
开放问题：
- 文章提出了开放问题：是否所有 $d \ge 2$ 的 Halton 型序列都不是准均匀的？
- 对于任意给定的 Halton 型序列，是否存在通用的索引构造方法来证明其非准均匀性？

总结

这篇文章通过严谨的数论和代数构造，揭示了 Halton 序列及其变体在高维空间中几何分布的内在缺陷（即分离半径衰减过快）。这一发现对数值分析、计算机图形学及机器学习中的采样策略选择具有重要的理论指导意义，提示研究者在处理高维散乱数据问题时需谨慎使用标准的 Halton 序列。