Komlós' discrepancy conjecture

About 6 years old · traced to

Let nn be a positive integer, and let v1,…,vn∈Rn\bm{v}_1,\dots,\bm{v}_n\in\mathbb{R}^n satisfy ∥vi∥2≤1\|\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=1nxivi∥∞≤C.\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.

References

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.