Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy

技术摘要：逆星差异（Inverse Star Discrepancy）的最优多项式可解性指数

问题陈述
本文研究了确定逆星差异 $n^*(d, \varepsilon)$ 的最优多项式可解性指数的问题。该量表示在 $d$ 维单位立方体 $[0, 1)^d$ 中，为实现星差异 $D^*_N(P) \le \varepsilon$ 所需的最少点数 $N$。

此前的研究表明，$n^*(d, \varepsilon)$ 对维度 $d$ 呈线性依赖，对 $\varepsilon^{-1}$ 呈多项式依赖。Heinrich, Novak, Wasilkowski, 和 Woźniakowski (2001) 证明了上界 $n^*(d, \varepsilon) \lesssim d \varepsilon^{-2}$，而 Hinrichs (2004) 确立了下界 $n^*(d, \varepsilon) \gtrsim d \varepsilon^{-1}$。虽然对 $d$ 的线性依赖关系已得到确认，但 $\varepsilon^{-1}$ 在上界中的精确指数仍是一个悬而未决的问题：幂次 2 是否可以降低为更小的值 $p < 2$？

方法论
本文通过证明即使允许对维度进行任意固定的多项式依赖，上界中的指数 2 也是最优的，从而解决了这一问题。其核心方法包括：

1. 多项式区间分析（Polynomial Regime Analysis）： 作者并非试图在所有 $d$ 和 $\varepsilon$ 下统一加强下界，而是分析了 $n^*(d, \varepsilon)$ 在特定“多项式条带”中的行为，即维度随误差倒数的幂增长，即 $d \asymp \varepsilon^{-\alpha}$，其中 $0 < \alpha < 1$。
2. 格矩阵构造（Gram Matrix Construction）： 证明利用了格矩阵论证。作者构造了一族中心化一维阶梯函数 h(t) = 3\mathbb{1}_{[0}_{[0, 1/3)}(t) - 1/\sqrt{2} 的张量积。
   • 这些函数的选择使得它们在不同坐标集上的张量积相对于勒贝格测度是正交的。
   • 较小的星差异意味着这些函数在点集 $P$ 上的经验内积必须接近它们的理论勒贝格内积。
3. 迹-秩不等式（Trace-Rank Inequality）： 将这些张量函数在 $N$ 个点处求值会生成一组 $\mathbb{R}^N$ 中的向量。作者证明了这些向量的格矩阵具有较大的迹以及受控的平方迹。通过应用初等迹-秩不等式 $\text{rank}(G) \ge (\text{tr } G)^2 / \text{tr}(G^2)$，作者推导出了一个关于秩的下界，而该秩对应于点数 $N$。

主要贡献与结果
主要结果是定理 1.1，它确立了在 $A\varepsilon^{-\alpha} \le d \le B\varepsilon^{-\alpha}$ 区间内的 $n^*(d, \varepsilon)$ 的新下界。具体而言，对于任何 $0 < \alpha < 1$，存在常数使得：
$$n^*(d, \varepsilon) \ge c_{\alpha, B} \, d \, \varepsilon^{-(2-\alpha)}$$
在这些条带内，右侧项的行为表现为 $\varepsilon^{-2}$。

由此得出的定理 1.2 定义了最优多项式可解性指数：

• 精度指数 $p^* = \inf \{ p : n^*(d, \varepsilon) \le C d^q \varepsilon^{-p} \}$ 恰好为 2。
• 维度指数 $q^* = \inf \{ q : n^*(d, \varepsilon) \le C d^q \varepsilon^{-p} \}$ 恰好为 1。

因此，Heinrich 等人 (2001) 提供的上界 $n^*(d, \varepsilon) \le C d \varepsilon^{-2}$ 在两个指数上都是各自最优的。

意义与主张
本文声称，即使允许对维度 $d$ 进行任意固定的多项式依赖，$\varepsilon^{-1}$ 的指数 2 也不可能被改进。这解决了先前已知的下界 ($\varepsilon^{-1}$) 与上界 ($\varepsilon^{-2}$) 之间关于精度指数的差距。

作者指出关于其结果范围的若干细微差别：

• 与 Hinrichs 的互补性： 在维度随 $\varepsilon^{-1}$ 多项式增长的中间区间（即 $d \ll \varepsilon^{-1}$）中，新的格矩阵下界比 Hinrichs 的界 ($d\varepsilon^{-1}$) 更强。然而，对于固定维度或当 $d \gg \varepsilon^{-1}$ 时，Hinrichs 的界仍然是更强的估计。
• 无逐点改进： 该结果并不意味着对于每一对 $(d, \varepsilon)$ 都存在逐点下界 $n^*(d, \varepsilon) \gtrsim d\varepsilon^{-2}$。对于固定的 $d$，经典的低差异构造显示 $n^*(d, \varepsilon)$ 可以低至 $O(\varepsilon^{-1} (\log \varepsilon^{-1})^{d-1})$，这是 $o(\varepsilon^{-2})$。指数 2 的最优性是跨维度的统一多项式可解性的属性。
• 开放问题： 虽然指数已确定为最优，但在特定联合区间内 $d$ 和 $\varepsilon$ 的精确混合依赖关系（即精确常数和低阶项）仍是一个开放问题。

总而言之，本文证明了 Heinrich–Novak–Wasilkowski–Woźniakowski 上界在其渐近指数上是紧致的，证实了在统一的多项式意义下，逆星差异的计算速率无法优于 $\varepsilon^{-2}$。