VibeMathedMath problems solved with AI
Sign in

Optimal-order mixing of the Thorp shuffle on 2d2^d cards: is the mixing time O(log⁡n)O(\log n)?

The Thorp shuffle on n=2dn=2^d cards cuts the deck into two halves, pairs the cards in corresponding positions, orders each pair by an independent fair coin, and interleaves the pairs. Each card is uniform after dd shuffles and a counting argument gives a lower bound of order dd for the whole permutation, while the known upper bounds were O(d44)O(d^{44}) (Morris 2008), O(d29)O(d^{29}) (Montenegro-Tetali) and O(d3)O(d^3) (Morris 2013). Is the total-variation mixing time of the full permutation O(d)=O(log⁡n)O(d)=O(\log n)?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Markov chain mixing times; card shuffling
Posed by
Line of work begun by Ben Morris (2008); the logarithmic order is discussed as the target in Johan Jonasson's notes (2009). The model is due to Edward O. Thorp (1973)
Year posed
—
Years open
—
Solved
2026-09-26
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
24 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Principal Theorem 1.1: for n=2dn=2^d, ∥qd∗1600d−Un∥TV→0\|q_d^{*1600d}-U_n\|_{TV}\to0 as d→∞d\to\infty, uniformly over initial decks, and ∥qd∗t−Un∥TV≥1−2tn/2/n!\|q_d^{*t}-U_n\|_{TV}\ge1-2^{tn/2}/n!, so tmix(d)≥2d−O(1)t_{mix}(d)\ge2d-O(1) and tmix(d)=Θ(d)t_{mix}(d)=\Theta(d). Companions give alternative proofs with other constants and the supporting Fourier and coordinate-sweep estimates. The constant 1600 is not claimed sharp; no cutoff or leading constant is determined, and the optimal-order question for general even deck sizes is explicitly not addressed.

What the AI did

The release README says all results were produced by an unreleased internal OpenAI model using one fixed procedure, about three hours of ChatGPT Pro thinking compute per result on average. 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 whose write-up was human-edited). All eleven manuscripts are authored 'OpenAI' and name no human author. They give several routes to O(d) mixing with different constants (1600d in the principal paper; 512d, 2048d and unspecified absolute multiples in companions), plus supporting representation-theoretic estimates.

Verification

No independent mathematician has checked this yet. Checked here: the introduction and Theorem 1.1 of the principal manuscript were read against the question. lean/docs/238.md lists thirteen challenges. The headline is in ThorpRemaining.json (OAI.ThorpResults.remaining_main, module OAI.Probability.ThorpResults.FullDevelopment): its conjunct OptimalOrderMain states that the distance-1/4 mixing time of the physical shuffle model (coin switch on the top bit, then bit rotation, which is the Thorp interleave on 2^d positions) is Theta(log 2^d), and FrameMain gives total variation tending to 0 after 32800d steps uniformly over starts. The solution file exists at the pinned commit. ThorpRemaining is not in the formalization catalogue; the catalogued BinarySweep, CoordinateSweeps, ThorpRouting and ThorpWeightedCompatibility state supporting sweep estimates, not the physical-shuffle mixing time. The statement was read here. Not rebuilt. Only deck sizes 2^d are covered.

Sources

Changelog1 change

Discussion