Komlós' discrepancy conjecture

Let nn be a positive integer, and let v1,,vnRn\bm{v}_1,\dots,\bm{v}_n\in\mathbb{R}^n satisfy vi21\|\bm{v}_i\|_2\leq 1 for i[n]i\in[n]. Komlós' conjecture. There exists a constant CC such that one can choose signs x1,,xn{1,1}x_1,\dots,x_n\in\{-1,1\} with

i=1nxiviC.\left\|\sum_{i=1}^n x_i\bm{v}_i\right\|_\infty\leq C.

This is a central open problem in discrepancy theory, asking whether vectors with uniformly bounded Euclidean norm always admit a signing whose coordinate discrepancies are bounded independently of the dimension.

Sources & referencesView supporting material

Primary source

Victor Reis, “Balancing Polynomials in the Chebyshev Norm”, arXiv:2009.05692 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.