Source-linked AI summary
An Exposition of the $\widetilde{O}(\log^{1/4} n)$ Bound for the Komlós Problem
Nikhil Bansal, Haotian Jiang
TL;DR
The paper addresses the Komlós discrepancy conjecture for matrices with columns of Euclidean norm at most one. It develops a process-based method using affine spectral independence and obtains an asymptotic improvement over Banaszczyk’s bound, refuting Hajela’s conjecture.
Problem
The Komlós conjecture asks whether matrices whose columns have Euclidean norm at most one always have discrepancy bounded by a universal constant.
Method
The proof tracks evolving row discrepancies, uses regularized discrepancy and affine spectral independence, and controls dangerous rows by moving orthogonally to them.
Results
The paper gives an asymptotic improvement over Banaszczyk’s bound; in a high-column-sparsity regime it obtains discrepancy b ≈ (log log n)1/2.
Takeaways & Limitations
The result refutes Hajela’s conjecture that a lower bound of order Ω(sqrt(log n)) should hold.
Takeaways & Limitations
The (log log n)7/4 factor is not optimized, and controlling rows one at a time entails an unavoidable limitation.
Abstract
from arXiv · showhide
A conjecture of Komlós states that the combinatorial discrepancy of any matrix $A\in\mathbb R^{m\times n}$ whose columns have Euclidean norm at most one is bounded by a universal constant. We prove that the combinatorial discrepancy of every such matrix is at most $O((\log n)^{1/4}(\log\log n)^{7/4})$. This is the first asymptotic improvement over the $O(\sqrt{\log n})$ bound established by Banaszczyk [Banaszczyk, Random Struct.\ Algorithms, 1998], and it refutes a conjecture of Hajela [Hajela, European J.\ Combin., 1988] that a lower bound of order $Ω(\sqrt{\log n})$ should hold.
1 Introduction
The paper studies the Komlós conjecture on constant combinatorial discrepancy for matrices with unit-norm columns, improving the prior asymptotic bound and refuting Hajela’s proposed lower bound.
- Problem: The combinatorial discrepancy is defined as disc(A) := min x∈{−1,1}n ∥Ax∥∞.It is the smallest maximum absolute row sum over all signings of the columns.
- Problem: The Komlós conjecture asserts that matrices whose columns have Euclidean norm at most one admit signings with discrepancy bounded by a universal constant.After normalization, this would imply the Beck–Fiala conjecture’s O(√k) discrepancy bound.
- Prior work: Prior methods achieved O(log n) through iterative partial coloring, while Banaszczyk’s best prior bound was O(√log n).The extra √log n factor arises from controlling rows individually and applying a union bound.
- Contribution: The paper gives an asymptotic improvement on Banaszczyk’s bound and thereby refutes Hajela’s conjecture of an Ω(√log n) lower bound.Hajela’s conjecture matched Banaszczyk’s upper-bound order, although only a weaker form had previously been established.
- Proof strategy: The new approach imposes affine spectral independence on row-discrepancy increments, enabling decoupling and orthogonal control of dangerous rows.The proof constructs a sticky stochastic process whose diffusion matrix is chosen adaptively while coordinates evolve toward ±1.
2 Preliminaries
The preliminaries develop Itô-process tools and a decoupling theorem for coordinate processes with negative drift and almost-independent martingale parts. They then apply these tools to regularized discrepancy and establish SDP-based conditions for constructing suitable diffusion matrices.
- Itô calculus: An Itô process has increment dZ_t = Σ_t dW_t + b_t dt, with quadratic variation d[Z,Z]_t = Σ_tΣ_t^⊤dt.The Itô formula describes increments of smooth functions of such processes, and optional stopping controls stopped supermartingales.
- Independent Itô processes: An (α, θ)-independent Itô process combines almost pairwise-independent martingale parts with coordinate-wise negative drift b_t(i) ≤ −θ C_t(i,i).The parameter α controls the comparison between the covariance matrix and its diagonal, while θ quantifies negative drift.
- Independent Itô processes: The decoupling bound controls the number of coordinates whose process rises by at least B, and α affects only an additive term rather than the leading m e^−λB term.This preserves the roughly expected bad-coordinate count even when martingale parts are fully independent.
- Regularized discrepancy: The coloring is generated by an Itô process driven by Brownian motion, while a regularized discrepancy vector is designed to become an (α, θ)-independent process.The regularization uses a modified matrix E_t and yields explicit increment and quadratic-variation formulas.
- Regularized discrepancy: Under suitable conditions on U_t, the regularized discrepancy satisfies a decoupling bound, while spectral independence yields a subgaussian discrepancy estimate.The construction verifies covariance comparison and negative drift before applying the decoupling corollary.
3 Proof of the Improved Koml´os Bound
The proof constructs a sticky Itô-process coloring and combines row control across logarithmically many coefficient scales to obtain the improved Komlós discrepancy bound.
- Proof setup: Theorem 1.1 establishes a coloring x ∈ {−1, 1}^n with discrepancy O((log n)^1/4(log log n)^7/4) for matrices whose columns have Euclidean norm at most one.The proof reduces the goal to bounding one-sided discrepancy and assumes n ≥ 100 and m ≤ n^2 without loss of generality.
- Proof setup: The coloring is generated by a sticky Itô process whose coordinates stop moving at ±1, producing a final vector in {−1, 1}^n.Alive coordinates form V_t, while coordinates outside V_t are frozen.
- 3.1 Overview: The argument tracks row discrepancies and chooses increments orthogonal to selected bad directions while retaining an O(1)-spectrally independent, random-like behavior.Large rows are blocked directly, small rows are controlled using their restricted ℓ1 or ℓ2 mass, and medium rows receive the main analysis.
- 3.4 Analysis: With high probability, every scale has discrepancy O(b), and a union bound gives total discrepancy O(bP) = O((log n)^1/4(log log n)^7/4).The process avoids aborting with high probability because at most |V_t|/10 rows are dangerous across all scales; conditional discrepancy control is supplied by Lemmas 3.4–3.6.