A $(\log n)^{1/4}$ Bound for the Komlós Problem

技术摘要：Komlós 问题的一个 $(\log n)^{1/4}$ 界限

问题陈述
本文研究了 Komlós 猜想，该猜想指出，对于任何列的欧几里得范数至多为 1 的实矩阵 $A \in \mathbb{R}^{m \times n}$，其组合差异（combinatorial discrepancy）$\text{disc}(A) = \min_{\sigma \in \{-1,1\}^n} \|A\sigma\|_\infty$ 是一个与 $n$ 无关的绝对常数。虽然 Banaszczyk 已经建立了 $O(\sqrt{\log n})$ 的界限，但目标是将此改进为与 $n$ 无关的常数。最近的工作由 Bansal 和 Jiang [BJ25, BJ26] 提出，他们引入了仿射谱独立性（affine spectral independence）框架，实现了 $O((\log n)^{1/4}(\log \log n)^{7/4})$ 的界限。本文旨在消除 $(\log \log n)^{7/4}$ 这一因子。

方法论与框架
该构造建立在 Bansal–Jiang 框架之上，具体利用了他们的仿射谱独立性定理（定理 A.4）以及通过半正定规划（SDP）进行解耦（decoupling）的概念。核心方法论涉及一种有限轨迹构造，该构造将一个分数着色（fractional coloring）$b \in [-1, 1]^n$ 演化为一个符号化向量 $\sigma$。

关键技术组件包括：

1. 连续限制与规模类（Successive Restrictions and Size Classes）： 算法通过将行分解为基于当前“存活”（未冻结）坐标的平方质量的“规模类”来处理行。行被“剥离”（peeled），以分离大系数并确保每个类中的剩余系数是受控的。
2. 正则化差异与漂移（Regularized Discrepancy and Drift）： 对于每个符号限制，定义了一个正则化差异函数 $Z_c^\varepsilon(x)$。该函数包含一个二次能量项以诱导负漂移。构造过程确保，如果一个限制的差异超过阈值，其移动梯度将在后续步骤中被阻断，从而防止进一步增长。
3. 历史指数和（Historical Exponential Sums）： 为了控制“危险”限制（即接近其阈值的限制）的数量，本文引入了历史指数和。这些和即使在限制退役（冻结）后仍能追踪其历史。系统维护一个势函数 $\Psi_t$，它聚合了跨所有规模类和列的加权指数和。
4. 有限步分析： 不同于可能依赖极限过程的其他方法，本构造使用有限网格 $\gamma$。作者利用直到四阶的泰勒展开推导出了精确的一步指数界限（定理 5.3）。该界限依赖于：
   • 仿射谱独立性： 用于控制符号响应之和的协方差。
   • 负曲率： 由立方体边界附近的“缓冲层”提供，这确保了势函数的二阶导数为负。
   • 四阶余项： 被一致地控制，以确保势函数在单步内的期望不会增加。

主要贡献

• 消除 $(\log \log n)$ 因子： 主要贡献在于消除了 Bansal–Jiang 界限中存在的 $(\log \log n)^{7/4}$ 因子，从而得到了 $O((\log n)^{1/4})$ 的界限。
• 精确阈值和证书： 本文提供了一个关于规模类间阈值总和的显式、精确的数值证书。这使得最终界限可以是一个精确的常数，而非渐近常数。
• 预设深度的部分着色： 定理 1.2 确立了一个部分着色结果，它可以从任何预设的分数点 $b$ 开始，并在预设的“深度” $R$ 处停止。这保证了剩余的分数坐标数量被减少到至多 $\max\{\lceil q e^{-R} \rceil - 1, 8\}$，其中 $q$ 是初始的分数坐标数量。
• 在 Lean 中形式化： 整个证明，包括有限轨迹、精确阈值和、以及最终的舍入过程，都在 Lean 定理证明器中进行了形式化。唯一的外部假设是 Bansal–Jiang 定理 A.4。

主要结果
本文证明了以下显式界限（定理 1.1）：
$$\text{disc}(A) \le 2395 \left(1 + \log_+ \frac{n}{9}\right)^{1/4} + 2\sqrt{2}$$
其中 $\log_+ t = \max\{0, \log t\}$。

此外，推论 1.3 表明，对于任何具有 $q$ 个分数坐标的起始点 $b$，存在一个保持现有符号的符号化向量 $\sigma$，使得：
$$\|A(\sigma - b)\|_\infty \le 2395 \left(1 + \log_+ \frac{q}{9}\right)^{1/4} + 2\sqrt{2}$$
当 $q \le 8$ 时，通过直接的欧几里得舍入，界限优化为 $\sqrt{q}$。

意义与主张
本文声称提供了第一个在不含 $\log \log n$ 多对数因子的前提下，实现 $O((\log n)^{1/4})$ 速率的 Komlós 问题界限。四次方根指数源于平衡“存活”集合维度的对数减少与协方差预算中行阈值的四次方之间关系。

作者强调，该构造是“有限”且“精确”的，避免了极限论证。使用有限网格和显式有理常数（例如系数 2395）使得证明是严谨且经过计算机验证的。该工作将部分着色和全着色定理形式化，证明了 Bansal–Jiang 框架可以通过精炼来获得更紧凑、显式的常数，同时保持原始谱独立性论证的结构完整性。本文并未声称解决了 Komlós 猜想（这需要一个与 $\log n$ 无关的常数），但通过将对数依赖性隔离到单个根式，代表了向该目标迈出的重要一步。