← All problems

Square-root law for online discrepancy of sparse random vectors

Let x1,x2,…,xT∈{0,1}nx_1,x_2,\ldots,x_T\in\{0,1\}^n be independent random vectors, each uniformly distributed among the vectors with exactly ss nonzero coordinates. An online algorithm chooses signs εt∈{−1,1}\varepsilon_t\in\{-1,1\} when xtx_t arrives, possibly knowing nn, ss, and TT. Define the prefix discrepancy by DTpref=max⁡1≤t≤T∥∑i=1tεixi∥∞D_T^{\mathrm{pref}}=\max_{1\le t\le T}\left\|\sum_{i=1}^t\varepsilon_i x_i\right\|_\infty. For every fixed s≥3s\ge 3 and c>0c>0, is the optimal prefix discrepancy, with high probability uniformly over n≤T≤ecnn\le T\le e^{cn}, of order log⁡log⁡n+(log⁡Tlog⁡n)1/2\log\log n+\left(\frac{\log T}{\log n}\right)^{1/2}? Equivalently, does there exist an online algorithm achieving DTpref=O ⁣(log⁡log⁡n+(log⁡Tlog⁡n)1/2)D_T^{\mathrm{pref}}=O\!\left(\log\log n+\left(\frac{\log T}{\log n}\right)^{1/2}\right) and does every online algorithm incur DTpref=Ω ⁣(log⁡log⁡n+(log⁡Tlog⁡n)1/2)D_T^{\mathrm{pref}}=\Omega\!\left(\log\log n+\left(\frac{\log T}{\log n}\right)^{1/2}\right) with high probability?

References

Progress summary

Refreshed
Open · progress reported

A new unrefereed preprint claims to settle the end-point question and the two-sparse case, but the conjectured law remains open for sparsity three or more.

The problem asks whether online discrepancy of sparse random vectors has a sharp square-root dependence over exponentially long horizons, distinguishing prefix from terminal behavior.

October 2026 preprint

Nicola Wengiel’s preprint claims to resolve the terminal-time question, obtain matching prefix behavior for sparsity two, and prove only a nonmatching upper bound for fixed sparsity at least three. Thus it advances but does not settle the full conjecture.

Current status (as of October 2026): The terminal-time question and sparsity-two prefix behavior are claimed in an unrefereed preprint, while the full square-root law for fixed sparsity at least three remains open.

Sources

Solutions 0

No solutions have been posted yet.