Improved logarithmic bound advances control of vector discrepancy
A $(\log n)^{1/4}$ Bound for the Komlós Problem
Discrete MathematicsData Structures and Algorithms
Summary
This paper finds a better way to balance certain numerical differences in mathematical matrices. The authors show that for matrices whose columns have length at most one, the maximum row discrepancy is smaller than previously proven bounds, specifically limited by a factor tied to the fourth root of a logarithm of the number of columns. They build on prior methods but remove extra terms that made the bounds less tight. Their approach uses a structured balance of thresholds and formal verification to ensure correctness.
What this means in practice
- •For algorithm designers: Use the tighter discrepancy bound to improve approximation guarantees in combinatorial optimization and rounding algorithms reliant on vector balancing.
- •For coding theorists: Incorporate the refined control of vector discrepancy into error correction code constructions that require balanced sign assignments for improved performance.
A theory result. No direct application yet.
Authors
Eren Ercan
Abstract
Let $A\in\mathbb{R}^{m\times n}$ have columns of Euclidean norm at most one. We prove that $\operatorname{disc}(A)\le2395\left(1+\log_+\frac n9\right)^{1/4}+2\sqrt2$. Here $\log_+t=\max\{0,\log t\}$. Building on Bansal and Jiang's affine spectral independence framework, we remove the $(\log\log n)^{7/4}$ factor from their bound. The fourth root comes from balancing the logarithmic decrease in the alive dimension against the fourth power of the row thresholds. Historical exponential sums control the covariance budget across size classes with summable thresholds. An exact threshold-sum certificate gives the coefficient $2395$, and rounding at most eight remaining fractional coordinates costs $2\sqrt2$. The finite construction also gives partial colourings from any prescribed starting point and at any prescribed depth, preserving existing signs. We formalize the partial- and full-colouring theorems in Lean, including the finite trajectory, exact threshold sum and final rounding, with Bansal--Jiang Theorem A.4 as the sole external research theorem assumption.