A tight lower bound on the minimal dispersion

技术摘要：“关于最小离散度的紧下界”

问题陈述
本文研究了 $d$ 维单位立方体 $[0, 1]^d$ 中点集的最小离散度问题。集合 $X$ 的离散度 $\text{disp}(X)$ 定义为不与 $X$ 相交的最大轴平行矩形的体积。作者研究了具有基数 $n$ 的集合的最小离散度 $\text{disp}^*(n, d)$，及其反函数 $N(\varepsilon, d)$，该函数表示确保离散度至多为 $\varepsilon$ 所需的最少点数。

虽然已知的平凡下界为 $N(\varepsilon, d) \ge 1/\varepsilon - 1$，但其对维度 $d$ 的依赖关系一直是近期研究的主题。前人的工作建立了上界，如 $N(\varepsilon, d) \le C \cdot d^2 \log d / \varepsilon$，以及最近的 $N(\varepsilon, d) \le C \cdot \log d \cdot \log(1/\varepsilon) / \varepsilon^2$（Litvak [11]，在 [21] 中得到改进）。一个核心的开放性问题是，后者中 $\varepsilon^{-2}$ 这一因子究竟是证明方法的产物，还是该问题的一个必要特征。

方法论
作者通过构造一类特定的、受限的测试矩形，而非考虑所有可能的轴平行矩形，解决了这一问题。其核心方法论包括：

1. 归约为极值集合论：作者将估计离散度的几何问题转化为关于 $r$-覆盖自由族（$r$-cover-free families）的组合问题。若一个集合族 $\mathcal{F}$ 是 $r$-覆盖自由的，则意味着 $\mathcal{F}$ 中的任何一个集合都不包含在其他任意 $r$ 个集合的并集中。
2. 构造测试矩形：对于固定的 $\varepsilon$，他们定义了一个轴平行矩形集合 $\mathcal{B}$。每个矩形 $B_{A,j}$ 的构造方式是：一个坐标区间很小（接近 0），而另外特定的 $2k-2$ 个坐标远离 0（接近 1），其中 $k$ 的选取满足 $2^{-(k+1)} < \varepsilon \le 2^{-k}$。
3. 覆盖自由映射：他们将任何与 $\mathcal{B}$ 中所有矩形都相交的点集 $X$，与一个集合族 $\{F_1, \dots, F_d\}$ 相关联，其中 $F_j$ 包含第 $j$ 个坐标较小的点。他们证明，如果 $X$ 与所有矩形 $B \in \mathcal{B}$ 相交，则该集合族 $\{F_j\}$ 是 $r$-覆盖自由的，其中 $r = 2k-2$。
4. 应用组合界限：作者利用了 Alon 和 Asodi [2]（基于 Ruszinkó [17]）建立的关于 $r$-覆盖自由族基集的下界。该界限将基集的大小（对应于点集大小 $|X|$）与参数 $d$ 和 $r$ 联系起来。

主要贡献与结果
主要贡献在于证明了在 $\varepsilon$ 足够大时，上界中的 $\varepsilon^{-2}$ 依赖性是优化的，这反驳了认为该二次项可能是概率证明方法产物的直觉。

• 定理 1：作者证明存在一个绝对常数 $c > 0$，使得对于任何满足 $\frac{1}{4\sqrt{d}} \le \varepsilon \le \frac{1}{4}$ 的整数 $d \ge 2$ 和实数 $\varepsilon$，以下下界成立：
  $$N(\varepsilon, d) > \frac{c \log d}{\varepsilon^2 \cdot \log(1/\varepsilon)}$$
  该结果在对数项范围内与最近获得的上界（Litvak [11], [21]）相匹配，证实了在该区间内 $\varepsilon^{-2}$ 依赖性的最优性。

• 推论 2：将其重新表述为关于最小离散度，对于正整数 $d$ 和 $n$，当 $2 \log d \le n \le c_1 d$ 时，最小离散度满足：
  $$\text{disp}^*(n, d) \ge c_2 \left(\frac{\log d}{n}\right)^{1/2} \cdot \left(\log\left(\frac{n}{\log d}\right)\right)^{-1/2}$$

意义与主张
本文声称该结果是“令人惊讶的”，因为它表明线性依赖于 $1/\varepsilon$ 与对数依赖于 $d$ 不能同时存在；对 $1/\varepsilon$ 的二次依赖是必要的。作者强调，通过仅考虑相对于总轴平行矩形数量而言“非常小的一类”测试矩形，便实现了这一强下界。

这项工作依赖于这样一个洞察：具有大量远离零的坐标的矩形是最难被随机生成的点“击中”的，这一现象在 Litvak [11] 和 [21] 的分析中有所观察。通过专注于这些特定的困难情况，作者将问题简化为已知的组合结构（$r$-覆盖自由系统），从而推导出紧致的下界。作者指出，其证明中的常数 $c$ 可以取为 $1/1920$，尽管他们并未尝试对其进行优化。作者留下了一个开放性问题，即该方法是否可以推广到更小的 $\varepsilon$ 值。