An elementary proof of the Komlós conjecture
Sankeerth Rao Karingula, Shachar Lovett
math.CO, cs.CC
2026-09-18
Karingula and Lovett prove Komlós elementarily: unit Euclidean vectors admit signs with infinity-norm at most 36, relaxing an AI-found constant of about 7.5.
The Komlós conjecture is an old question in discrepancy theory, written into Spencer's lectures, with the Beck–Fiala conjecture as a special case. Given n vectors of Euclidean length at most 1, can one assign each a sign in {+1, -1} so that the infinity norm of the signed sum stays below a constant that does not grow with n or d?
Spencer's six-standard-deviations theorem gives O(√n) for set discrepancy. Banaszczyk's 1998 vector-balancing theorem pushed Komlós to O(√log n). The Gram–Schmidt walk later made that bound constructive. In 2026 Bansal and Jiang broke the square-root log for the first time, reaching O((log n)^{1/4}(log log n)^{7/4}); Ercan removed the iterated log, leaving O((log n)^{1/4}). A universal constant was still missing.
In September 2026, Guo, Fang, and Lu proved the conjecture with C = 3√(2π), about 7.5. They credit the Odin Automatic AI Research Agent with finding the argument, which uses Banaszczyk's convex-body transform and directional total variation of densities. Karingula (Agentin AI) and Lovett (UCSD) digested that proof and extracted one that uses only combinatorics, probability, and basic calculus. The constant relaxes to 36.
The working quantity is shift distance: the total variation between a finitely supported distribution P and its translate by a vector u. Small shift distance means P and the translate share most of their mass.
The proof has two parts. The first is a combinatorial induction. If P has shift distance at most 1/3 at each 6vi, some signing keeps the mean plus the signed sum inside the convex hull of the support. The inductive step splits along the last vector: mass is sent to a new 0/1 coordinate by a max/min rule, and the overlap is at least 1/3. Induction handles the first n-1 vectors. Mass is then pulled back onto the original support. States with bit 1 have two parents, so their mass can be split continuously between ±3v and finish the last sign.
The second part builds such a P. A product density on the cube [-6,6]^d, each factor the square of a tent function, has total variation at most ||v||2 / √12 under a shift by v. Rounding onto a grid that contains all the rational input vectors does not increase total variation. Since ||vi||2 ≤ 1, the shift distance is below 1/3. Rational inputs give infinity norm at most 36 directly; real inputs follow by approximation and a limit.
Relative to Guo, Fang, and Lu: they add an extra coordinate and rearrange a density toward zero. Here the extra coordinate is a single bit, and a splitting operator replaces the convex geometry. The cost is the constant, about 7.5 versus 36. The authors did not try to tighten it.
| Result | Bound | Note |
| Banaszczyk 1998 | O(√log n) | long-standing best |
| Bansal–Jiang / Ercan 2026 | O((log n)^{1/4}) | first break of the log square root |
| Guo–Fang–Lu 2026 | 3√(2π) ≈ 7.5 | found by an AI agent |
| This paper | 36 | elementary; finite construction for rationals |
The finite construction is for rational inputs and is not a polynomial-time algorithm. The strong (prefix) Komlós conjecture, which asks for the same constant on every prefix sum, is untouched here and in Guo et al. The best dimension-free prefix bound remains Banaszczyk's O(√log n). Aden-Ali gives a randomized online algorithm that hits the same prefix order with high probability.
For theorists, Komlós moves from "one log-root away" to "here is a number", and the argument can be written on a blackboard from scratch. For people watching automated theorem proving, the story is concrete: Odin found the first proof, then humans rewrote it without convex geometry. The constant got worse; the exposition got cheaper. Lovett is a coauthor of the Gram–Schmidt walk, so this reads as a human digestion of an AI proof.
Discrepancy sits under rounding, derandomization, and vector balancing in approximation algorithms. A constant of 36 is loose for practice. The content is existence.
The authors list three. The constant 36 is weaker than 3√(2π) and unoptimized. There is no polynomial-time algorithm; the rational construction can have huge support. Prefix Komlós stays open.
Odin's role is a credit line, not a reproduced system, and the paper does not compare verification cost of the AI proof against the rewrite. The authors used ChatGPT-6 Astra to iterate on the argument and the prose. Readers who want an automated-proving systems paper will not find one here. This is the cleaned mathematics.