oai-math-revised beta

Browse › Probability and statistical mechanics › 238 Optimal logarithmic mixing of the Thorp shuffle

From partial permutation information to Fourier bounds

OpenAI · September 26, 2026

Lean

Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion

Edit NOTES.md · Existing issues · Source on GitHub

Abstract

We show how information about partial permutations controls full permutation laws. Let n tend to infinity through multiples of eight. If the images of a uniformly chosen $7n/8$ labels approach the uniform injection law in average total variation, and the sign mean tends to zero, then the product of two independent permutations with the given law converges to uniform on Sn.

If the PDF does not display here, open it directly: Open PDF.

Notes

No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.

Automatically collected notes (unreviewed)

work in progress

Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.

Follow-up works

  • acprk (GitHub), Remark R5: Thorp shuffle 1600d → 24d (openai-math-remarks, local draft, undated). Uses this paper's Theorem 1.1 (Hilbert–Schmidt transfer) with different block counts in the two factors to claim Thorp mixing after 24d shuffles; asymptotic, not formalized, reviewed only by AI. [AI-generated per source]

Formalization

  • OpenAI math release, Lean scope notes for family 238 (lean/docs/238.md, 2026). States that the formalization covers the finite estimate turning coset-mass bounds for b blocks into Hilbert–Schmidt and operator-norm Fourier bounds (PartialPermutation.lean); the asymptotic statement about the product of two random permutations is outside its scope. [family-level]

Possibly relevant literature (found by the agent, not checked)

Digests and expositions

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:From-partial-permutation-information-to-Fourier-bounds-September-26-2026,
  author = {{OpenAI}},
  title = {{From partial permutation information to Fourier bounds}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/From-partial-permutation-information-to-Fourier-bounds-September-26-2026/main.pdf}{OAI:From-partial-permutation-information-to-Fourier-bounds-September-26-2026}},
  year = {2026}
}

Lean formalization

OpenAI provides Lean files for this family: lean/docs/238.md. The Lean statements have not been checked by people against the paper's claims.

Family 238: Optimal logarithmic mixing of the Thorp shuffle

Proves that the Thorp shuffle randomizes $N=2^d$ labeled cards in $\Theta(\log N)$ physical shuffles, settling its optimal mixing order for power-of-two deck sizes. Convergence is in total variation from the worst initial ordering and concerns the entire permutation, not just individual card positions.

Other papers in this family: