AI Proof WatchKeep up with AI contributions

Transposition is Nearly Optimal for IID List Update

Christian Coester

In the IID request model, the stationary expected access cost of Transposition is at most OPT+1, where OPT orders items by decreasing request probability. GPT-5 Pro proposed the central inequality sⱼ≤pⱼ and a coefficient-nonnegativity route; Christian Coester supplied the final proof.

Sources for this record

What was already known

The previous general bound was (π/2)OPT. Earlier favorable results covered special distributions; an additive one cannot be removed in the cited example.

AI involvement AI-centered

GPT-5 Pro suggested the inequality and coefficient route, which Coester calls essential. Coester developed the polynomial reduction and combinatorial injection and revised the manuscript.

The author explicitly calls the model’s proposed inequality and coefficient-nonnegativity route essential, while reserving the decisive injection and proof to his own work.

Importance Notable

Improves the general IID Transposition guarantee to within one unit of optimal cost.

Limitations

The model did not prove its conjectural inequality or the decisive sign-eliminating injection. A completed separate check of the final argument is not documented.

Technical verification Reported

The paper presents a full proof, but the model’s small-n experiments motivated a conjecture and no completed check of the final argument is documented. Reported is the missing-check default.

Human understanding Full

Coester explains the excess-cost decomposition, gap-variable polynomial, and sign-eliminating injection that establish the central inequality; the model’s unproved suggestion is not treated as human proof.

Correction and publication history