arxiv: 2604.13355 · v1 · submitted 2026-04-14 · 💻 cs.DS · cs.DM

Recognition: unknown

Near-Optimal Constructive Bounds for ell₂ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence

Kunal Dutta , Agastya Vibhuti Jha , Haotian Jiang

Authors on Pith no claims yet

Pith reviewed 2026-05-10 13:35 UTC · model grok-4.3

classification 💻 cs.DS cs.DM

keywords Steinitz problemprefix discrepancyell_2 discrepancyalgorithmic discrepancyspectral independencevector balancingpartial sumssemidefinite programming

0 comments

The pith

An efficient algorithm finds orderings of vectors so that all prefix sums stay O(sqrt(d)) in Euclidean norm when dimension is polylogarithmic in n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives a polynomial-time algorithm that produces an ordering of any n vectors in R^d summing to zero such that every partial sum has ell_2 norm at most O(sqrt(d)), provided d is at least Omega(log^7 n). This matches the long-standing conjecture for the ell_2 Steinitz problem and extends to the harder ell_2 prefix discrepancy setting. A reader would care because earlier algorithmic methods incurred an extra sqrt(log n) factor and the best known proofs were non-constructive, leaving a gap between theory and usable algorithms for vector balancing tasks.

Core claim

There exists an efficient algorithm that, for vectors v_1 to v_n in R^d summing to zero with d >= Omega(log^7 n), outputs a permutation such that the ell_2 norm of every prefix sum is O(sqrt(d)). The same guarantee holds for the ell_2 prefix discrepancy problem. The algorithm simulates a discrete Brownian motion whose steps are guided by the solution of a semidefinite program; the analysis relies on the decoupling-via-affine-spectral-independence method together with a global interval tree that tracks deviations over all prefixes at once.

What carries the argument

Decoupling via affine spectral independence combined with a global interval tree data structure, which together control the maximum deviation of the discrete Brownian motion across every prefix simultaneously.

If this is right

The ell_2 Steinitz theorem now has a constructive proof achieving the conjectured O(sqrt(d)) bound under a polylogarithmic dimension assumption.
The ell_2 prefix discrepancy problem admits the same near-optimal algorithmic guarantee.
The previous best algorithmic bound of O(sqrt(d log n)) is improved to O(sqrt(d)).
The combination of SDP-guided Brownian motion with affine spectral independence yields a general template for derandomizing discrepancy orderings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same framework might be adaptable to obtain constructive bounds in lower dimensions by tightening the spectral independence estimates.
Online vector balancing and discrepancy minimization algorithms could directly use the produced ordering to reduce cumulative error.
The global interval tree technique may simplify analyses in other multi-scale discrepancy settings such as Beck-Fiala or Komlos problems.

Load-bearing premise

The dimension must be at least a high enough polylogarithmic function of n so that the affine spectral independence property and the interval tree analysis can simultaneously bound all prefix deviations.

What would settle it

An explicit collection of vectors in dimension d = O(log^6 n) for which every ordering produces at least one prefix sum whose ell_2 norm exceeds C sqrt(d) for any fixed constant C, or an instance on which the SDP-guided Brownian motion algorithm fails to stay inside the claimed bound.

Figures

Figures reproduced from arXiv: 2604.13355 by Agastya Vibhuti Jha, Haotian Jiang, Kunal Dutta.

**Figure 2.** Figure 2: Partition of the complete sliding window [ [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Figure 3: ASI-guard for prefix P, and the corresponding ASI and error components of dϕP t . Roughly speaking, we will show (see Section 3.3 for details) that the contribution from the ASIguard part dϕASI t can still be bounded as in (3), even though the ASI-guard for P might change over time — thus as long as goal (i) is achieved, one has γASI = |It | = o(d) and this suffices for bounding the ASI-guard part ϕ ASI t… view at source ↗

**Figure 4.** Figure 4: The error set grows after the interval containing [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗

**Figure 5.** Figure 5: Tree0 is a complete binary tree whose leaves correspond to all base intervals B. Note that the leaves of Tree0 correspond exactly to the first 10d/s base intervals I0 when restricted to the sliding window W0, and the rest of the leaves to base intervals not yet added to I0. We maintain this property throughout — namely, we ensure that the leaves of Treet correspond either to intervals in It , or to base in… view at source ↗

**Figure 6.** Figure 6: When a left leaf becomes small, it is deleted and mer [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗

**Figure 7.** Figure 7: When the right sibling of a small left leaf is also an [PITH_FULL_IMAGE:figures/full_fig_p017_7.png] view at source ↗

**Figure 8.** Figure 8: When the left sibling of a small right leaf has been d [PITH_FULL_IMAGE:figures/full_fig_p018_8.png] view at source ↗

**Figure 9.** Figure 9: Decomposition of prefix P based on its root-leaf path. Each node GP(k) added to GP is the left sibling of a node on the root-leaf path that is the right child of its parent’s. As mentioned in Section 2.3, we will analyze the dynamics of kϕtk 2 2 given by dkϕtk 2 2 = kϕt+dtk 2 2 − kϕtk 2 2 = 2 hdϕt , ϕti | {z } dLt + hdϕt , dϕti | {z } dQt , (6) and bound the processes Lt and Qt (with increments dLt and dQt… view at source ↗

**Figure 10.** Figure 10: The blocking-guard for prefix P in row i. The discrepancy change dϕP t (i) = dϕbad t (i) is entirely due to the set of bad columns. 5.3.2 Modified Global Interval Tree In this section, we describe the data structure T ∞ Global for maintaining the blocking constraints {Ji,t}i∈[d] . The idea is similar to TGlobal, but we include a full description here for completeness. Similar to the interval representatio… view at source ↗

read the original abstract

A classical result of Steinitz from 1913 \cite{Ste13}, answering an earlier question of Riemann and L\'evy (e.g., \cite{Lev05}), states that for any norm $\|\cdot\|$ in $\mathbb{R}^d$ and any set of vectors $v_1, \cdots, v_n \in \R^d$ satisfying $\sum_{i=1}^n v_i = 0$, there exists an ordering $\pi: [n] \rightarrow [n]$ such that every partial sum along this order is bounded by $O(d)$, i.e., $\big\| \sum_{i=1}^t v_{\pi(i)} \big\| \leq O(d)$ for all $t \in [n]$. Steinitz's bound is tight up to constants in general, but for the $\ell_2$ norm $\|\cdot\|_2$, it has been conjectured that the best bound is $O(\sqrt{d})$. Almost a century later, a breakthrough work of Banaszczyk \cite{Ban12} gave a bound of $O(\sqrt{d} + \sqrt{\log n})$ for the $\ell_2$ Steinitz problem, matching the conjecture under the mild assumption that $d \geq \Omega(\log n)$. Banaszczyk's result is non-constructive, and the previous best algorithmic bound was $O(\sqrt{d \log n})$, due to Bansal and Garg \cite{BG17}. In this work, we give an efficient algorithm that matches the conjectured $O(\sqrt{d})$ bound for the $\ell_2$ Steinitz problem under the slightly worse, yet still polylogarithmic, condition of $d \geq \Omega(\log^7 n)$. As in prior work, our result extends to the harder problem of $\ell_2$ prefix discrepancy. We employ the framework of obtaining the desired ordering via a discrete Brownian motion, guided by a semidefinite program (SDP). To obtain our results, we use the new technique of ``Decoupling via Affine Spectral Independence'', proposed by Bansal and Jiang \cite{BJ26} to achieve substantial progress on the Beck-Fiala and Koml\'os conjectures, together with a ``Global Interval Tree'' data structure that simultaneously controls the deviations for all prefixes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a constructive O(sqrt(d)) algorithm for l2 Steinitz and prefix discrepancy when d is Omega(log^7 n), closing the gap to the conjectured bound via spectral decoupling and an interval tree.

read the letter

The punchline is that this work delivers an efficient algorithm matching the O(sqrt(d)) conjecture for the Euclidean Steinitz problem and its harder prefix-discrepancy version, as long as d is at least polylog in n. It improves directly on the prior constructive O(sqrt(d log n)) bound from Bansal-Garg while staying within the non-constructive regime of Banaszczyk up to the dimension condition. The approach uses SDP-guided discrete Brownian motion, the affine spectral independence decoupling from Bansal-Jiang, and a new global interval tree to control all prefixes at once. That combination is the actual novelty, and it looks like a non-routine extension rather than a routine application. The result is clean on the surface: no extra log n in the final deviation, just the conjectured sqrt(d) under the stated condition. The citation pattern is solid, building on the right prior results without obvious gaps. The soft spot is the interface between the decoupling lemma and the interval tree. The tree has to manage deviations across dyadic intervals without introducing multiplicative factors or forcing a worse d threshold, and the claim of exactly O(sqrt(d)) with no residual logs rests on that step being tight. The log^7 n exponent is higher than the log n in the non-constructive case, so there is probably some slack in the analysis that future work could tighten. The SDP rounding and walk invariants also need careful checking to confirm nothing leaks through. Overall the argument appears coherent on its own terms. This is for discrepancy theorists and people working on constructive geometric balancing or online algorithms. A reader who cares about closing algorithmic gaps in Steinitz-type problems will get direct value. It deserves a serious referee because the result is sharp and the techniques are new enough to warrant detailed verification.

Referee Report

1 major / 1 minor

Summary. The paper claims an efficient algorithm achieving the conjectured O(√d) bound for the ℓ₂ Steinitz problem (and the harder ℓ₂ prefix discrepancy problem) when d ≥ Ω(log⁷ n). The algorithm constructs the desired ordering via an SDP-guided discrete Brownian motion, combined with the 'Decoupling via Affine Spectral Independence' technique of Bansal-Jiang and a 'Global Interval Tree' data structure that simultaneously controls deviations over all prefixes.

Significance. If the central claim holds, this would be a notable advance: it supplies the first constructive algorithm matching the conjectured O(√d) bound (up to the polylogarithmic condition on d), improving on the prior algorithmic O(√d log n) result while nearly closing the gap with Banaszczyk's non-constructive O(√d + √log n) bound. The new decoupling method and interval-tree mechanism are of independent interest for discrepancy problems.

major comments (1)

[Technical sections on the global interval tree and decoupling] The integration of the Global Interval Tree with affine spectral independence decoupling (detailed in the sections describing the tree invariants and the application of the Bansal-Jiang lemma across dyadic intervals): the analysis must explicitly verify that this combination produces a uniform O(√d) deviation bound simultaneously for every prefix, without residual multiplicative log factors from tree depth or the number of intervals. The d ≥ Ω(log⁷ n) threshold appears tuned to absorb such overhead; any unaccounted factor here would either inflate the deviation or require a stronger condition on d, directly affecting the tightness of the claimed bound.

minor comments (1)

[Abstract] The abstract states the result but does not mention the running time of the algorithm; adding a brief note on polynomial-time efficiency would clarify the constructive nature.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying the need to strengthen the explicitness of the analysis on the Global Interval Tree and decoupling technique. We address the major comment point by point below and will incorporate clarifications in the revision.

read point-by-point responses

Referee: [Technical sections on the global interval tree and decoupling] The integration of the Global Interval Tree with affine spectral independence decoupling (detailed in the sections describing the tree invariants and the application of the Bansal-Jiang lemma across dyadic intervals): the analysis must explicitly verify that this combination produces a uniform O(√d) deviation bound simultaneously for every prefix, without residual multiplicative log factors from tree depth or the number of intervals. The d ≥ Ω(log⁷ n) threshold appears tuned to absorb such overhead; any unaccounted factor here would either inflate the deviation or require a stronger condition on d, directly affecting the tightness of the claimed bound.

Authors: We appreciate the referee highlighting this aspect of the analysis. The Global Interval Tree (Section 4) maintains a set of invariants over dyadic intervals that ensure simultaneous control of all prefixes by propagating discrepancy bounds level-by-level. The affine spectral independence decoupling (Bansal-Jiang lemma, applied in Section 5 across the tree) is invoked on vector collections restricted to these intervals; the resulting concentration and union bounds over O(log n) tree levels and O(log n) intervals per prefix contribute only polylogarithmic factors in n. These overheads are explicitly tracked in the proof of the main theorem (Theorem 1.1 and its supporting lemmas), where they multiply with the logarithmic terms arising from the SDP guidance and vector norm concentrations to yield an overall requirement of d ≥ Ω(log⁷ n). Under this condition the extra factors are absorbed into the leading O(√d) term, producing a uniform bound with no residual multiplicative logs. To make this verification fully self-contained and easier to follow without cross-referencing multiple sections, we will add a short dedicated subsection (or expanded paragraph in the proof overview) that isolates and computes the precise overhead from tree depth and interval count. This revision will not alter the claimed bound or the d-threshold. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation builds on cited prior technique without reducing to self-definition or fitted inputs.

full rationale

The paper derives its O(√d) algorithmic bound for ℓ₂ Steinitz and prefix discrepancy via an SDP-guided discrete Brownian motion combined with the Decoupling via Affine Spectral Independence technique (cited from Bansal-Jiang 2026) and a new global interval tree data structure. No step in the provided abstract or description reduces the target bound to a fitted parameter, self-definition, or unverified self-citation chain; the result is presented as a constructive algorithm matching the conjecture under a polylog condition on d, with the interval tree handling simultaneous prefix control. This is a standard extension of prior non-constructive and algorithmic results rather than a tautological renaming or input-output equivalence.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review performed from abstract only; no explicit free parameters, axioms, or invented entities are identifiable in the provided text.

pith-pipeline@v0.9.0 · 5771 in / 1095 out tokens · 49936 ms · 2026-05-10T13:35:20.677254+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

7 extracted references · 6 canonical work pages

[1]

[Ban87] Wojciech Banaszczyk

doi:10.1145/3406325.3450994. [Ban87] Wojciech Banaszczyk. The steinitz constant of the p lane

work page doi:10.1145/3406325.3450994
[2]

36 [BJ25b] Nikhil Bansal and Haotian Jiang

URL: https://arxiv.org/abs/2508.01937. 36 [BJ25b] Nikhil Bansal and Haotian Jiang. Quasi-Monte Carlo Beyond Hardy-Krause. In Sym- posium on Discrete Algorithms (SODA) , pages 2051–2075. SIAM,

work page arXiv 2051
[3]

Towards a constructive version of Banaszczyk’s ve ctor bal- ancing theorem

[DGLN16] Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov. Towards a constructive version of Banaszczyk’s ve ctor bal- ancing theorem. In APPROX/RANDOM 2016 , pages 28:1–28:12,

2016
[4]

[ES18] Ronen Eldan and Mohit Singh

URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.2 8, doi:10.4230/LIPICS.APPROX-RANDOM.2016.28. [ES18] Ronen Eldan and Mohit Singh. Eﬃcient algorithms for d iscrepancy minimization in convex sets. Random Struct. Algorithms , 53(2):289–307,

work page doi:10.4230/lipics.approx-random.2016.2 2016
[5]

Online geometric discrep- ancy for stochastic arrivals with applications to envy mini mization

[JKS19] Haotian Jiang, Janardhan Kulkarni, and Sahil Singl a. Online geometric discrep- ancy for stochastic arrivals with applications to envy mini mization. arXiv preprint arXiv:1910.01073,

work page arXiv 1910
[6]

[L´ ev05] Paul L´ evy

URL: https://doi.org/10.1137/1.9781611977554.ch152, doi:10.1137/1.9781611977554.CH152. [L´ ev05] Paul L´ evy. Sur les s´ eries semi-convergentes. Nouvelles annales de math´ ematiques: journal des candidats aux ´ ecoles polytechnique et normale , 5:506–511,

work page doi:10.1137/1.9781611977554.ch152
[7]

[Rot17] Thomas Rothvoss

doi:10.1137/1.9781611977554.CH66. [Rot17] Thomas Rothvoss. Constructive discrepancy minimi zation for convex sets. SIAM Jour- nal on Computing , 46(1):224–234,

work page doi:10.1137/1.9781611977554.ch66