Prescribed-order Euclidean prefix discrepancy O(sqrt d), independent of length (Bansal-Jiang-Meka-Singla-Sinha Conjecture 6.3)
Given vectors in the Euclidean unit ball of in a fixed order, choose signs to keep every prefix sum small. Banaszczyk proved a bound , which grows with the length when is large compared with . Bansal, Jiang, Meka, Singla and Sinha (2021, Section 6, Conjecture 6.3), following Banaszczyk, conjectured the length-free square-root bound. Is there an absolute such that every such sequence has signs with all prefix sums of norm at most ?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Discrepancy theory; vector balancing
- Posed by
- Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla and Makrand Sinha, Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing, arXiv 2111.07049 (2021), Conjecture 6.3
- Year posed
- 2021
- Years open
- 5y
- Solved
- 2026-09-24
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 22 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: an absolute constant such that every finite sequence in the Euclidean unit ball of , in prescribed order, has one signing with every prefix of norm at most , independent of . This removes the term from Banaszczyk's bound and is optimal up to the constant. It is existential: no efficient or online algorithm is given, so the algorithmic and online versions of the question remain open.
What the AI did
The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author.
Verification
No independent mathematician has checked this yet. Checked here: Theorem 1.1 of the manuscript was read against the prescribed-order signing question as the paper cites it from Bansal et al.; the manuscript's citation was not checked against the 2021 preprint's own wording. The proof was not refereed. lean/formalization.yaml lists a main result for this manuscript (comparator SteinitzBergstrom, declaration OAI.EuclideanSteinitzBergstrom.main); its SignedPrefixBound part, read here, states exactly the length-free prefix-signing bound for every finite sequence in the unit ball. Not rebuilt here.