A simplification of the solution to the Komlós Conjecture

With the incredible progress on Mathematical Open Problems this past Summer, we decided to broaden the scope of our blog and also include digestions and simplifications of solutions, keeping the expository nature of the blog.

In this entry I aim to present a simplification of the proof of the Komlós Conjecture by Guo, Fang and Lu (Guo et al., 2026). This conjecture has some sentimental value, as it was the first open problem in (Bandeira, 2016) (and it is Conjecture 10 in this blog (Bandeira et al., 2025)).

Theorem (Komlós)

Let $v_1,\ldots,v_n\in\mathbb{R}^d$, where $d,n\geq1$, satisfy $\lVert v_j\rVert_2\leq1$. There are signs $\varepsilon_j\in\{-1,1\}$ such that

\[\left\lVert \sum_{j=1}^n\varepsilon_jv_j\right\rVert_\infty<9\pi.\]

In 1998, Banaszczyk (Banaszczyk, 1998) proved such a bound up to a square-root logarithmic factor by an iterative argument that we will follow quite closely below. To simplify the exposition, we show a proof of the above theorem with a worse constant than Guo–Fang–Lu (Guo et al., 2026) ($9\pi$ vs $3\sqrt{2\pi}$). Kunisky (Kunisky, 2023) showed that the constant cannot be smaller than $1+\sqrt{2}$.

Banaszczyk’s theorem was made constructive, up to an absolute constant, by Bansal, Dadush, Garg and Lovett (Bansal et al., 2019). Bansal and Jiang (Bansal & Jiang, 2025) improved the square-root logarithmic bound to $(\log n)^{1/4}$ up to powers of $\log\log n$. More closely related to the present argument, Smirnov and Vershynin (Smirnov & Vershynin, 2026) relate Fisher information and Dirichlet energy to online discrepancy with discarded steps.

For sets $K,L\subset\mathbb{R}^d$, let $K+L=\{x+y:x\in K,\ y\in L\}$ be the Minkowski sum. For a vector $u$, write $[-u,u]=\{tu:-1\leq t\leq1\}$. We call a convex set $K$ symmetric when $K=-K$.

The strategy behind Banaszczyk’s theorem can be described as follows: pick a suitable property $\mathcal{P}$ and transformations $K\mapsto\mathcal{B}_u(K)$ for symmetric convex sets such that, whenever $\lVert u\rVert_2\leq1/18$:

1. $\mathcal{B}_u(K)\subseteq(K-u)\cup(K+u)$;
2. if $K$ is symmetric, convex, and belongs to $\mathcal{P}$, then $\mathcal{B}_u(K)$ is also symmetric, convex, and belongs to $\mathcal{P}$;
3. $\emptyset\notin\mathcal{P}$.

Lemma (Implicit in (Banaszczyk, 1998))

Suppose $\mathcal{P}$ and $\mathcal{B}_u$ have the properties above. If $K$ is symmetric, convex, and belongs to $\mathcal{P}$, then for any $v_1,\ldots,v_n\in\mathbb{R}^d$ with $\lVert v_j\rVert_2\leq1$ there are signs $\varepsilon_j\in\{-1,1\}$ such that

\[\sum_{j=1}^n\varepsilon_jv_j\in18K.\]

Proof. Set $K_0=K$ and $K_j=\mathcal{B}_{v_j/18}(K_{j-1})$ for $j=1,\ldots,n$. By the properties above, $K_n$ is non-empty symmetric convex so $0 \in K_n$, thus

\[0\in K_n\subseteq \bigcup_{\varepsilon\in\{-1,1\}^n} \left(K+\frac1{18}\sum_{j=1}^n\varepsilon_jv_j\right).\]

Reversing all signs gives the conclusion. $\square$

The transformation $\mathcal{B}_u(K)$

The points from which a step $+u$ or $-u$ returns to $K$ form $(K-u)\cup(K+u)$, but this union need not be convex. Instead, Banaszczyk considers

\[\mathcal{B}_u(K)=\bigl((K-u)\cap(K+u)\bigr)+[-2u,2u].\]

The intersection consists of the centers $c$ for which the entire segment $c+[-u,u]$ lies in $K$. The transformation doubles each of these segments.

If $x=c+tu\in\mathcal{B}_u(K)$, where $-2\leq t\leq 2$ and $c\pm u\in K$, then $x-u=c+(t-1)u\in[c-u,c+u]\subset K$ when $t\geq 0$; when $t\leq0$, use $x+u$ instead. Thus the above definition of $\mathcal{B}_u(K)$ satisfies 1., and it preserves convexity and symmetry. It need not contain $K$: fibers in direction $u$ shorter than $2\lVert u\rVert_2$ disappear. The main task is therefore to find a property $\mathcal{P}$ preserved by this operation.

Banaszczyk (Banaszczyk, 1998) takes $\mathcal{P}=\{K:\gamma_d(K)\geq 1/2\}$ on closed convex bodies, where $\gamma_d$ is standard Gaussian measure; this works for steps of norm at most $1/5$, but the least side length of a cube satisfying the condition is of order of $\sqrt{\log(d)}$.

A spectral property $\mathcal{P}$

We keep the transformation and change the property $\mathcal{P}$ to one satisfied by a cube of constant side length. From now on, a domain is a nonempty bounded open convex subset of $\mathbb{R}^d$. For a real symmetric positive semidefinite matrix $A$, define

\[E_A(f)=\int_{\mathbb{R}^d}\nabla f^{\mathsf T}A\nabla f,\] \[\lambda_A(K)=\inf_{f\in H_0^1(K),\,\int f^2=1}E_A(f).\]

Functions are real-valued and extended by zero outside their domains; $H_0^1(K)$ is the Sobolev space with zero boundary values. Precisely, $H_0^1(K)$ is the closure of $C_c^\infty(K)$ in the norm $\bigl(\int_K(f^2+\lvert\nabla f\rvert^2)\bigr)^{\frac12}$. Zero extensions are in $H^1(\mathbb{R}^d)$. We find it a useful intuition to think of $\lambda_A(K)$ as measuring the thinness of $K$ in the geometry induced by $A\succeq 0$. When $A\succ 0$, $\lambda_A(K)$ is the first Dirichlet eigenvalue of $-\operatorname{div}(A\nabla)$ (For $A=I$ it can also be thought of rate of heat loss from $K$ when the boundary is set to temperature zero); for $A\succeq 0$ we use the same variational definition. In particular, enlarging the domain decreases $\lambda_A$ since the variational formula takes the infimum in a larger set. The property $\mathcal{P}$ will ask for an upper bound on $\lambda_A$ for all $A\succeq0$, this will be useful as it will allow us to measure thinness with emphasis in specific directions; for example, adding $uu^{\mathsf T}$ to $A$ measures thinness in the direction $u$ more aggressively.

Our choice of $\mathcal{P}$ is the class of domains (nonempty bounded open convex sets) satisfying \begin{equation}\label{komlos:eq:property} \lambda_A(K)\leq\operatorname{Tr}(A)\qquad\text{for every }A\succeq0, \end{equation} where $\operatorname{Tr}(A)=\sum_i A_{ii}$. By construction $\emptyset\notin\mathcal{P}$ and so 3. follows immediately.

To see that the cube $K_0=(-\pi/2,\pi/2)^d$ belongs to $\mathcal{P}$, one can use the test function

\[f(x)=(2/\pi)^{d/2}\prod_{i=1}^d\cos x_i,\]

which belongs to $H_0^1(K_0)$ (for $A=I$ the reader might recognize it as the first Dirichlet eigenfunction of the Laplacian, corresponding to the slowest-decaying “heat mode” on $(-\pi/2,\pi/2)^d$) and satisfies

\[\int f^2=1,\qquad \int\partial_i f\,\partial_j f=\delta_{ij},\]

which can be readily verified by factoring the integrals. Thus $E_A(f)=\sum_i A_{ii}=\operatorname{Tr}(A)$, proving \eqref{komlos:eq:property} for the cube.

It remains to establish property 2. The following is the main lemma.

Lemma (Preservation of $\mathcal{P}$)

If $K\in\mathcal{P}$ and $\lVert u\rVert_2\leq1/18$, then $\mathcal{B}_{u}(K)$ is nonempty and belongs to $\mathcal{P}$.

Proof of the Komlós theorem, assuming the Lemma (Preservation of $\mathcal{P}$). Apply the Lemma (Implicit in (Banaszczyk, 1998)) with $K=(-\pi/2,\pi/2)^d$. The resulting signed sum belongs to $(-9\pi,9\pi)^d$. $\square$

To prove the preservation of $\mathcal{P}$ we will construct a subset of $\mathcal{B}_u(K)$ that is naturally written as a Minkowski sum of two convex sets and then make use of the following version of a theorem of Brascamp and Lieb (Brascamp & Lieb, 1976), Theorem 6.2.

Theorem (Brascamp–Lieb (Brascamp & Lieb, 1976))

For domains $K,L$, a real symmetric positive semidefinite matrix $A$, and $0\leq t\leq1$, \begin{equation}\label{komlos:eq:BL} \lambda_A((1-t)K+tL) \leq(1-t)\lambda_A(K)+t\lambda_A(L). \end{equation}

For $A=I_d$, this is (Brascamp & Lieb, 1976), Theorem 6.2; see also (Bryan et al., 2026), Theorem 1.2 and the discussion following Theorem 1.3, for a modern proof and the extension to nonsmooth convex domains. The matrix version for $A\succ0$ follows by the change of variables $\lambda_A(K)=\lambda_{I_d}(A^{-1/2}K)$ and the extension to singular $A$ by approximation: one can take $A+\epsilon I$ for arbitrarily small $\epsilon> 0$.

Proof of the Lemma (Preservation of $\mathcal{P}$). Fix $K\in\mathcal{P}$ and $\lVert u\rVert_2\leq1/18$. Set

\[K_M=K+[-3u,3u],\qquad K_m=(K-3u)\cap(K+3u).\]

The goal of this proof is to show that $K_m$ is nonempty and that, furthermore, for every $A\succeq0$, \begin{equation}\label{komlos:eq:target} \frac23\lambda_A(K_M)+\frac13\lambda_A(K_m)\leq\operatorname{Tr}(A). \end{equation}

This would be enough since, by construction of $K_M,K_m$ and convexity of $K$, \begin{equation}\label{komlos:eq:containment} \frac23K_M+\frac13K_m\subseteq\mathcal{B}_{u}(K), \end{equation} and so, as long as $K_m$ is nonempty, Brascamp–Lieb (the Brascamp–Lieb theorem above) implies

\[\lambda_A(\mathcal{B}_{u}(K)) \leq \lambda_A\left(\frac23K_M+\frac13K_m\right) \leq\frac23\lambda_A(K_M)+\frac13\lambda_A(K_m).\]

We now focus on proving that $K_m$ is non-empty, and subsequently on establishing \eqref{komlos:eq:target}.

Note that the infimum in the definition of $\lambda_A(K)$ is unchanged if one restricts to nonnegative $C_c^\infty(K)$ functions, by taking absolute values and smooth approximations. From now on we call a test function a nonnegative function $f\in C_c^\infty(K)$ with $\int f^2=1$. For a test function $f$, write

\[f_\pm(x)=f(x\pm3u),\qquad f_M=\max\\{f_+,f_-\\},\quad f_m=\min\\{f_+,f_-\\}.\]

The functions $f_M,f_m$ have compact supports contained in $K_M,K_m$, respectively. They are Lipschitz, so they are legitimate Dirichlet test functions whenever nonzero. Taking the maximum and minimum simply exchanges the two gradients almost everywhere, thus \begin{equation}\label{komlos:eq:sorting} E_A(f_M)+E_A(f_m)=2E_A(f),\qquad \lVert f_M\rVert_2^2+\lVert f_m\rVert_2^2=2. \end{equation}

Writing $\partial_u f=u^{\mathsf T}\nabla f$, the fundamental theorem of calculus gives

\[f_+(x)-f_-(x)=\int_{-3}^{3}\partial_u f(x+tu)\,dt\]

and thus

\[\lVert f_+-f_-\rVert_2 \leq \int_{-3}^{3}\lVert\partial_u f(\cdot+tu)\rVert_2\,dt = 6\lVert \partial_u f\rVert_2.\]

Since $f\geq 0$, $2f_m^2=f_+^2+f_-^2-|f_+^2-f_-^2|$, and $\lVert f_++f_-\rVert_2\leq2$, Cauchy–Schwarz implies \begin{equation}\label{komlos:eq:overlap} 1-\lVert f_m\rVert_2^2 =\frac12\int|f_+^2-f_-^2| \leq\frac12\lVert f_+-f_-\rVert_2\lVert f_++f_-\rVert_2 \leq6\lVert \partial_u f\rVert_2. \end{equation} To show that $K_m$ is nonempty one uses the fact that $K\in\mathcal{P}$ and applies \eqref{komlos:eq:property} to $A=uu^{\mathsf T}$. Since

\[\lambda_A(K)\leq\operatorname{Tr}(A) =\lVert u\rVert_2^2 \leq\frac1{18^2}<\frac1{6^2},\]

the definition of $\lambda_A(K)$ gives a nonnegative $f\in C_c^\infty(K)$ with $\int f^2=1$ and $E_A(f)<1/6^2$. For this choice,

\[\lVert \partial_u f\rVert_2^2 \leq E_A(f)<\frac1{6^2}.\]

Thus \eqref{komlos:eq:overlap} gives $1-\lVert f_m\rVert_2^2<1$, so $f_m\ne0$. Since $f_m$ is supported in $K_m$, this proves $K_m\ne\emptyset$, which also implies that $\mathcal{B}_u(K)$ is nonempty.

It remains to prove \eqref{komlos:eq:target}. Fix $A\succeq0$ and define the energy gap between $K_m$ and $K_M$ as

\[\Delta=\lambda_A(K_m)-\lambda_A(K_M)\geq0.\]

For any normalized nonnegative smooth test function $f$ (even if $f_m=0$), the variational formula for $\lambda_A$ and the identity \eqref{komlos:eq:sorting} give, for every $A\succeq 0$, \begin{equation}\label{komlos:eq:EAfandLambdaKm} E_A(f) = \frac12E_A(f_M)+\frac12E_A(f_m) \geq\frac12\lambda_A(K_M)\lVert f_M\rVert_2^2+\frac12\lambda_A(K_m)\lVert f_m\rVert_2^2=\lambda_A(K_M)+\frac{\Delta}{2}\lVert f_m\rVert_2^2. \end{equation}

Our target \eqref{komlos:eq:target} can be rewritten as $\operatorname{Tr}(A)\geq \lambda_A(K_M)+\frac{\Delta}{3}$. If $\lVert\partial_u f\rVert < 1/18$ then, by \eqref{komlos:eq:overlap}, $\lVert f_m\rVert^2 >2/3$, and so $\lambda_A(K_M)+\frac{\Delta}{3}\leq \lambda_A(K_M)+\frac{\Delta}{2}\lVert f_m\rVert_2^2\leq E_A(f)$. If this held for all test functions we would have that $\lambda_A(K_M)+\frac{\Delta}{3}\leq \lambda_A(K)$, which together with $K\in\mathcal{P}$ would give us \eqref{komlos:eq:target}.

The remaining key idea is that, while we can’t ensure this directional derivative bound holds for all test functions, we can (in a sense) force it on competitive test functions by using $K\in\mathcal{P}$ for $A+cuu^{\mathsf T}$ where $c\geq 0$. Indeed, adding $cuu^{\mathsf T}$ to $A$ increases $E_A(f)$ by $c\lVert\partial_u f\rVert^2$ and $\operatorname{Tr}(A)$ by $c\lVert u\rVert^2\leq c/18^2$.

More precisely, we have (the $\inf$ is taken over all test functions),

\[\inf_f \left(E_{A}(f)+c\lVert\partial_u f\rVert^2\right) = \inf_f E_{A+cuu^{\mathsf T}}(f) \leq \operatorname{Tr}(A+cuu^{\mathsf T}) = \operatorname{Tr}(A) + c\lVert u\rVert^2 \leq \operatorname{Tr}(A) + c/18^2.\]

Thus, to prove \eqref{komlos:eq:target}, we need to show

\[\inf_f \left(E_{A}(f)+c\lVert\partial_u f\rVert^2-c/18^2\right) \geq \lambda_A(K_M)+\frac{\Delta}3.\]

This corresponds to showing this inequality for every test function. Due to \eqref{komlos:eq:EAfandLambdaKm}, it suffices to show that for all test functions

\[\frac{\Delta}2\lVert f_m\rVert^2+c\lVert\partial_u f\rVert^2-c/18^2 \geq \frac{\Delta}3.\]

Since, by \eqref{komlos:eq:overlap}, $1-\lVert f_m\rVert^2\leq 6\lVert\partial_u f\rVert$, it suffices to show \begin{equation}\label{komlos:eq:target3} \frac{\Delta}2\lVert f_m\rVert^2+\frac{c}{6^2}\left(1-\lVert f_m\rVert^2\right)^2-c/18^2 \geq \frac{\Delta}3. \end{equation}

At $\lVert f_m\rVert_2^2=2/3$, the two terms involving $c$ in \eqref{komlos:eq:target3} cancel, so its left-hand side equals $\Delta/3$. We choose $c$ so that the quadratic in $\lVert f_m\rVert_2^2$ has its minimum there. Its derivative at $2/3$ is $\Delta/2-c/54$, which gives $c=27\Delta$. Indeed,

\[\frac{\Delta}{2}\lVert f_m\rVert_2^2 +\frac{27\Delta}{6^2}\left(1-\lVert f_m\rVert_2^2\right)^2-\frac{27\Delta}{18^2}=\frac{\Delta}{3} +\frac{3\Delta}{4}\left(\lVert f_m\rVert_2^2-\frac23\right)^2 \geq\frac{\Delta}{3}.\]

This proves \eqref{komlos:eq:target3} for every nonnegative $f\in C_c^\infty(K)$ with $\int f^2=1$, establishing \eqref{komlos:eq:target}. $\square$

The interested reader can reconstruct the argument with the bound $\lVert u\rVert\leq \delta$ and verify that $\delta=1/18$ is the optimal choice, for this particular argument.

Acknowledgements

The author thanks the audience in an internal seminar at ETH where this argument was presented. Particular thanks to Antoine Maillard and Spas Dimitrov for insightful suggestions.

References

1. Guo, S., Fang, E. X., & Lu, J. (2026). Vector balancing via directional total variation. ArXiv Preprint ArXiv:2609.11189v1. https://arxiv.org/abs/2609.11189v1
2. Bandeira, A. S. (2016). Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science. Available at \Urlhttps://People.math.ethz.ch/ Abandeira/TenLecturesFortyTwoProblems.pdf.
3. Bandeira, A. S., Kireeva, A., Maillard, A., & Rödder, A. (2025). Randomstrasse101: Open Problems of 2024. ArXiv Preprint ArXiv:2504.20539.
4. Banaszczyk, W. (1998). Balancing vectors and Gaussian measures of n-dimensional convex bodies. Random Structures Algorithms, 12(4), 351–360. https://doi.org/10.1002/(SICI)1098-2418(199807)12:4<351::AID-RSA3>3.0.CO;2-S
5. Kunisky, D. (2023). The discrepancy of unsatisfiable matrices and a lower bound for the Komlós conjecture constant. SIAM J. Discrete Mathematics (SIDMA), 37(2).
6. Bansal, N., Dadush, D., Garg, S., & Lovett, S. (2019). The Gram–Schmidt walk: A cure for the Banaszczyk blues. Theory Comput., 15(21), 1–27. https://doi.org/10.4086/toc.2019.v015a021
7. Bansal, N., & Jiang, H. (2025). Decoupling via affine spectral-independence: Beck–Fiala and Komlós bounds beyond Banaszczyk. ArXiv Preprint ArXiv:2508.03961v2. https://arxiv.org/abs/2508.03961v2
8. Smirnov, G., & Vershynin, R. (2026). Discrepancy and Fisher information. ArXiv Preprint ArXiv:2605.13107v1. https://arxiv.org/abs/2605.13107v1
9. Brascamp, H. J., & Lieb, E. H. (1976). On extensions of the Brunn–Minkowski and Prékopa–Leindler theorems, including inequalities for log concave functions, and with an application to the diffusion equation. J. Funct. Anal., 22(4), 366–389. https://doi.org/10.1016/0022-1236(76)90004-5
10. Bryan, P., Clutterbuck, J., & Rankin, C. (2026). Convexity inequalities for eigenvalues and log-concavity of eigenfunctions. ArXiv Preprint ArXiv:2605.01334v1. https://arxiv.org/abs/2605.01334v1