Central limit theorem for the random assignment problem
Let be the minimum cost of a perfect matching in an matrix of independent uniform random variables. Aldous proved in 1992 that converges, later identifying the limit as via the Poisson-weighted infinite tree; Parisi's exact finite- formula for exponential costs was then proved by Linusson-Wästlund and independently by Nair, Prabhakar and Sharma. The fluctuations resisted. Talagrand applied product-space concentration, Wästlund computed the exponential model's variance as , and Chatterjee proved an order- lower bound under tail hypotheses that exclude the bounded uniform law - but no central limit theorem for was known. This paper claims one: .
- Result
- Proved(see note)
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Random combinatorial optimization
- Posed by
- —
- Year posed
- 1992
- Years open
- 34y
- Solved
- 2026-08-06
- Model
- ChatGPT 5.6 and Opus 5
- Vendor
- OpenAI; Anthropic
- Collaborators
- Gilles Mordant
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 32 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Claims the central limit theorem for the bipartite random assignment problem with bounded uniform costs: . The limiting constant is not itself new - Wästlund had computed exactly for the mean-one exponential model, and Malatesta, Parisi and Sicuro derived the non-bipartite analogue by replicas - but neither is a proof for the bounded bipartite model, and Wästlund's zero-free-disk conjecture, which would imply a Gaussian limit, remains open. So the value was expected; the proof of convergence to it is what is claimed. The route is an exact change of variables on an optimal dual potential, after which the residual dependence is a single directed-tree factor whose matrix-tree determinant becomes triangular once the potentials are ordered.
What the AI did
The paper carries its AI disclosure as section 1.1, before the mathematics rather than buried after it, and it is precise enough to be worth quoting rather than paraphrasing: "This proof is not a one-prompt exploit: I have been working for quite some time on optimal transport and matching problems. I somehow forced the AI to help me explore a geometric intuition that I had come up with a few months ago, even before the models reached their current level. Funnily, during the interaction, I had to force the AI not to drift to attempts involving the Stein method and force it to stick to my ideas. AI was then used to complete the proofs, catch mistakes and verify the paper (both via numerical simulations and general 'thinking'), as well as to improve the exposition. The models ChatGPT 5.6 and Opus 5 (as well as previous versions) were used." The conceptual core is claimed by the author and the steering was his, including steering the model away from a wrong direction; completing the proofs is substantive mathematics, which is why this sits at co-developed rather than assisted.
Verification
An arXiv preprint (v1, 5 August 2026), unrefereed and with no independent endorsement. No mathematics was checked here, and there is nothing mechanical to check it against: a long probabilistic argument with no formalization and no computational certificate. What was verified on 24 August 2026: the paper exists at arXiv:2608.05123, its title, author and limiting variance match this entry, and its AI disclosure is genuine, first-party and quoted above in full. Its history section was read to establish novelty - it surveys Kurtzberg, Walkup, Karp, Aldous, Linusson-Wästlund, Nair-Prabhakar-Sharma, Talagrand, Wästlund, Chatterjee and Cao, and states that none of the first-order, concentration, exact-moment or replica results supplies the central limit theorem for bounded uniform costs. That is the author's own characterization of what was open, recorded as such; no independent literature search was run here.
Sources
Submitted by SpryRaven345 on