VibeMathedMath problems solved with AI

An optimal, deterministic, polynomial time sorting adversary

A sorting adversary answers the comparisons of a sorting algorithm online and is legal if every finite sequence of its answers is consistent with some total order. Atallah and Kosaraju (1981) gave an efficient deterministic adversary forcing every correct sorter to make 12nlog⁡2n\frac12 n\log_2 n comparisons, and Kaplan, Zamir and Zwick (SODA 2019) raised this to 3764nlog⁡2n\frac{37}{64}n\log_2 n. Kaplan, Zamir and Zwick ask whether an efficient (polynomial-time) deterministic adversary can force (1−ε)nlog⁡2n(1-\varepsilon)n\log_2 n comparisons for every ε>0\varepsilon>0 and all sufficiently large nn, matching the information-theoretic bound. Does one exist?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Theoretical computer science
Posed by
Haim Kaplan, Or Zamir and Uri Zwick, The amortized cost of finding the minimum (SODA 2015), Section 7, as cited by the manuscript
Year posed
2015
Years open
11y
Solved
2026-11-06
Model
GPT 6 Astra (Codex)
Vendor
OpenAI
Collaborators
Nicholas Nash
Verification
Lean-checked, statement unaudited
Publication
Preprint
Significance
15 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: there is a deterministic legal adversary, initialized using only nn, that uses polynomially many bit operations per query and forces every correct sorter to make at least (1−o(1))nlog⁡2n(1-o(1))n\log_2 n comparisons. Previous efficient deterministic adversaries forced 12nlog⁡2n\frac12 n\log_2 n (Atallah and Kosaraju 1981) and 3764nlog⁡2n≈0.578 nlog⁡2n\frac{37}{64}n\log_2 n\approx0.578\,n\log_2 n (Kaplan, Zamir and Zwick 2019). Polynomial time is proved in Lean in an explicit arithmetic cost model (a counted primitive-operation charge on exact rationals), not as an instruction-level bound for a machine model, and the degrees are enormous. The paper also derives consequences for sorting under partial information and partial order production.

What the AI did

Per the paper's methodological disclosure, the adversary and its analysis are due to AI (GPT 6 Astra, run in Codex with the optimal adversary as the goal; about 27 hours according to the submission). The human author shaped the exposition and abstractions and reviewed the paper except for the appendices, which are marked as raw AI-generated work. The Lean formalization is part of the same project.

Verification

No independent mathematician has checked this yet. Checked here on 15 November 2026: the paper's introduction and disclosure (Hexagon 2611.00196v2, sole author Nicholas Nash, ORCID-linked), and the Lean repository nicknash/sorting-adversary-proofs at commit 0a46d06 (12 Nov 2026, Lean 4.33.1). The headline SortingAdversary.Continuous.UniformEfficient.asymptoticallyOptimal_and_polynomial was read with the definitions it rests on: DecisionTree.Correct (every ranking recovered), legality (every run consistent with some ranking), and for every delta > 0 a lower bound of (1 - delta) n log2 n comparisons for all large n, plus fixed polynomial charges for initialization and every reachable query in the project's own arithmetic cost model. A grep of the Lean sources found no sorry, admit or axiom declarations; native_decide appears only in the older StrengthenedCurvature development, outside the headline. The project's CI run 43209728075 on that commit passed the placeholder check, full build, leanchecker replay and an all-declaration axiom audit of the continuous development allowing only propext, Classical.choice and Quot.sound. Not rebuilt here. The paper's appendices are unreviewed AI output by the author's own statement.

Sources

Submitted by SwiftRaven874 on

Changelog2 changes

Discussion