Logarithmic total-variation mixing of the physical Thorp shuffle

Logarithmic total-variation mixing of the physical Thorp shuffle

OpenAI's claim

The linked manuscripts present the following claims by OpenAI: A strict permanent exponent below two for almost-uniform $S_4$ laws with uniform coordinate marginals is claimed to imply optimal Thorp mixing; Compatibility-entropy estimates are claimed to show optimal-order Thorp mixing after a fixed number of coordinate sweeps; Near-uniform bounded-size line laws are claimed to satisfy conditional Schatten-moment contraction, with an analytic transfer yielding binary Thorp mixing in order $d$; After an absolute number of deterministic Thorp coordinate sweeps, further-card endpoints are claimed nearly uniform on unoccupied sites in expectation conditional on revealed card paths; With half of the Thorp trajectories revealed, the remaining conditional permutation is claimed to approach uniform after a fixed number of sweeps; Near-uniform images of a random $7n/8$ label set and a vanishing sign bias are claimed enough for two independent permutation factors to approach uniform on $S_n$; The Thorp shuffle on $2^d$ cards is claimed to mix in order $d$ physical shuffles, with upper bound $1600d$ and lower bound $2d-O(1)$; Random-coordinate-frame estimates are claimed to give full Thorp mixing by $32800d$, improved to $512d$ using the Fourier companion; An absolute number of Thorp sweeps is claimed to reduce full-law total variation below $\tfrac12 n^{-5}$ uniformly over initial decks; Routing-density contraction is claimed to give full-permutation Thorp mixing after an absolute number of sweeps, hence order $\log N$ physical steps; A row--column Fourier comparison is claimed to give the same optimal logarithmic order of Thorp mixing; A fixed number of sweeps is claimed to make the full Thorp permutation density approach uniform in squared $L^2$, implying optimal total-variation order. Together they give a claimed affirmative answer in the matching scope.

Mathematical statement of the claimed result

Result 1.

For $N=2^d$ cards, one physical Thorp shuffle pairs corresponding cards in the two deck halves, independently orders each pair by a fair coin, and interleaves. Its law is $q_d$ on $S_N$; $U_N$ is uniform. A sweep uses each binary-coordinate matching once with independent fair switches, hence costs $d$ physical shuffles. Total variation means half the sum of absolute mass differences. If $T_N(\lambda)=\mathbb E\rho_\lambda(g)$ is the sweep average on the irreducible unitary $S_N$-representation of degree $D_\lambda$, put $B_N(\lambda)=T_N(\lambda)T_N(\lambda)^*$. Absolute $\eta>0$ and an even integer $r\ge2$ satisfy \[ D_\lambda\operatorname{Tr}B_N(\lambda)^r\le D_\lambda^{1-\eta} \quad(\lambda\vdash N), \] with unnormalized trace. Consequently a fixed number $q$ of independent forward sweeps has distance from $U_N$ tending to zero as $N\to\infty$, uniformly over initial decks.

Result 2.

Let $B$ be convolution by a probability measure on a finite group $G$, and $B_\rho$ its Fourier matrix in an irreducible unitary representation of dimension $D_\rho$. Suppose fixed $p>0$, $0<\varepsilon\le1/2$ satisfy \[ \sum_{\rho\ne\mathbf1}D_\rho\operatorname{Tr}|B_\rho|^p\le\varepsilon, \qquad |B_\rho|=(B_\rho^*B_\rho)^{1/2}. \] For a sequence of such groups, assume every nonzero nonconstant block has dimension at least $D_{\min}\to\infty$. If $\mu_M$ is the law after $M$ independent convolution steps and $2M>p$, then \[ 4\|\mu_M-U_G\|_{\mathrm{TV}}^2 \le\varepsilon(\varepsilon/D_{\min})^{(2M-p)/p}\longrightarrow0. \] This is a conditional spectral-conversion result; its moment hypothesis must be supplied by the sweep estimates.

Result 3.

For $N=2^d$ cards, one physical Thorp shuffle pairs corresponding cards in the two deck halves, independently orders each pair by a fair coin, and interleaves. Its law is $q_d$ on $S_N$; $U_N$ is uniform. A sweep uses each binary-coordinate matching once with independent fair switches, hence costs $d$ physical shuffles. Total variation means half the sum of absolute mass differences. Let $K_\lambda=\mathbb E\rho_\lambda(g)$ be the Fourier matrix of one sweep. There are absolute $g>0,d_0$ such that, for $d\ge d_0$, \[ \|K_\lambda\|_{\mathrm{op}}\le D_\lambda^{-g}\quad(\lambda\vdash 2^d). \] The sign block vanishes. For some absolute integer $w>0$, $w$ independent sweeps converge in total variation to uniform as $d\to\infty$, uniformly over deterministic starting decks.

Result 4.

For $N=2^d$ cards, one physical Thorp shuffle pairs corresponding cards in the two deck halves, independently orders each pair by a fair coin, and interleaves. Its law is $q_d$ on $S_N$; $U_N$ is uniform. A sweep uses each binary-coordinate matching once with independent fair switches, hence costs $d$ physical shuffles. Total variation means half the sum of absolute mass differences. Let $V=\mathbb F_2^d$ and follow any fixed ordered list of $k$ different labels. Uniformly over starting decks and such lists, their image law at $256d$ physical steps has distance $o(1)$ from uniform on ordered injections $[k]\to V$ whenever $k\le7N/8$. At $1024d$ steps that distance is at most $N^{-3/2}$ for $k\le15N/16$ and sufficiently large $d$. The full-deck conclusion is \[ \|q_d^{*(2048d)}-U_N\|_{\mathrm{TV}}\longrightarrow0. \]

Result 5.

For $N=2^d$ cards, one physical Thorp shuffle pairs corresponding cards in the two deck halves, independently orders each pair by a fair coin, and interleaves. Its law is $q_d$ on $S_N$; $U_N$ is uniform. A sweep uses each binary-coordinate matching once with independent fair switches, hence costs $d$ physical shuffles. Total variation means half the sum of absolute mass differences. Fix $N/2$ outside labels and condition on their full paths $\mathcal E$ through a time interval. Number the remaining slots at its endpoints in binary order; their random assignment defines a conditional permutation law $\nu_{\mathcal E}$ on $S_{N/2}$. After $40000(400+1)$ sweeps, \[ \sup_{\text{initial layouts}}\mathbb E_{\mathcal E} \|\nu_{\mathcal E}-U_{N/2}\|_{\mathrm{TV}}\longrightarrow0. \] The full deck therefore converges to uniform after $16\,040\,400d$ physical shuffles. At every integer time $t\ge0$ its distance is at least $1-2^{tN/2}/N!$, giving mixing time $\Theta(d)$.

Result 6.

Let $X$ be a finite set, $G=S_X$, and $X=M_1\sqcup\cdots\sqcup M_b$ a partition into nonempty blocks. Let $H_i=S_{M_i}$ fix the complement pointwise. Take a measure $f\ge0$ on $G$ with $f(G)\le1$. Assume \[ f(gH_i)\le B/[G:H_i]\quad(g\in G,\ 1\le i\le b). \] For an irreducible unitary $\rho$ of degree $D$, set $\widehat f(\rho)=\sum_gf(g)\rho(g)$ and \[ C_u=\sup_{m\ge1}\sum_{\lambda\vdash m}(\dim V_\lambda)^{-u}<\infty\quad(u>0). \] Then \[ \|\widehat f(\rho)\|_{\mathrm{HS}}^2\le bBC_uD^{-1+(u+2)/b},\qquad \|\widehat f(\rho)\|_{\mathrm{op}}^2\le bBC_uD^{-1+(u+2)/b}. \] The Hilbert--Schmidt norm is unnormalized. Arbitrary block sizes and restriction multiplicities are allowed.

Result 7.

For $N=2^d$ cards, one physical Thorp shuffle pairs corresponding cards in the two deck halves, independently orders each pair by a fair coin, and interleaves. Its law is $q_d$ on $S_N$; $U_N$ is uniform. A sweep uses each binary-coordinate matching once with independent fair switches, hence costs $d$ physical shuffles. Total variation means half the sum of absolute mass differences. As $d\to\infty$, \[ \|q_d^{*(1600d)}-U_N\|_{\mathrm{TV}}\to0, \qquad \|q_d^{*t}-U_N\|_{\mathrm{TV}}\ge1-2^{tN/2}/N!\quad(t\in\mathbb Z_{\ge0}). \] Thus the threshold-$1/4$ worst-start mixing time obeys \[ t_{\mathrm{mix}}(d)\ge\left\lceil\frac2N\log_2\frac{3N!}{4}\right\rceil=2d-O(1), \qquad t_{\mathrm{mix}}(d)=\Theta(d). \]

Result 8.

For $N=2^d$ cards, one physical Thorp shuffle pairs corresponding cards in the two deck halves, independently orders each pair by a fair coin, and interleaves. Its law is $q_d$ on $S_N$; $U_N$ is uniform. A sweep uses each binary-coordinate matching once with independent fair switches, hence costs $d$ physical shuffles. Total variation means half the sum of absolute mass differences. The full-deck law satisfies \[ \|q_d^{*(32800d)}-U_N\|_{\mathrm{TV}}\longrightarrow0\quad(d\to\infty), \] uniformly over every deterministic initial ordering.

Result 9.

For $N=2^d$ cards, one physical Thorp shuffle pairs corresponding cards in the two deck halves, independently orders each pair by a fair coin, and interleaves. Its law is $q_d$ on $S_N$; $U_N$ is uniform. A sweep uses each binary-coordinate matching once with independent fair switches, hence costs $d$ physical shuffles. Total variation means half the sum of absolute mass differences. Write $Q_N$ for one sweep's averaging operator. For absolute $P\ge2$, \[ \operatorname{Tr}_{\mathrm{reg}}|Q_N|^P =\sum_{\lambda\vdash N}D_\lambda\operatorname{Tr}|Q_N(\lambda)|^P \le1+N^{-10}\quad(N\ge2\text{ dyadic}). \] Here $|Q|=(Q^*Q)^{1/2}$, traces are unnormalized, and the constant representation contributes one. Every integer $v$ with $2v\ge P$ gives \[ \|q_d^{*(vd)}-U_N\|_{\mathrm{TV}}\le\tfrac12N^{-5} \] from every deterministic initial deck.

Result 10.

For $N=2^d$ cards, one physical Thorp shuffle pairs corresponding cards in the two deck halves, independently orders each pair by a fair coin, and interleaves. Its law is $q_d$ on $S_N$; $U_N$ is uniform. A sweep uses each binary-coordinate matching once with independent fair switches, hence costs $d$ physical shuffles. Total variation means half the sum of absolute mass differences. Let $T_N$ average one forward sweep and $K_N=T_N^*T_N$. On the set $\mathcal X_{N,k}$ of ordered injections, let $u_{N,k}$ be uniform and define \[ R_x(y)=(N)_k\mathbb P_{K_N}(x\mapsto y),\qquad (N)_k=N!/(N-k)!. \] There exist absolute $\eta,c,C>0$ such that, for $a=1/1000$, \[ \log\mathbb E_{y\sim u_{N,k}}R_x(y)^{1+a}\le Ck(k/N)^\eta\quad(1\le k\le N), \] uniformly in $x$. For sufficiently large dyadic $N$ and each nontrivial irreducible block, \[ T_N(\lambda)=0\quad\text{or}\quad\|T_N(\lambda)\|_{\mathrm{op}}\le D_\lambda^{-c}. \] A fixed absolute number of forward sweeps consequently mixes the full deck with vanishing worst-start error.

Result 11.

For $N=2^d$ cards, one physical Thorp shuffle pairs corresponding cards in the two deck halves, independently orders each pair by a fair coin, and interleaves. Its law is $q_d$ on $S_N$; $U_N$ is uniform. A sweep uses each binary-coordinate matching once with independent fair switches, hence costs $d$ physical shuffles. Total variation means half the sum of absolute mass differences. There is an absolute $C$ such that the threshold-$1/4$ mixing time satisfies, for every $d\ge1$, \[ \left\lceil\frac2N\log_2\frac{3N!}{4}\right\rceil\le t_{\mathrm{mix}}(d)\le Cd. \] Hence its order is $d=\log_2N$, with lower bound $2d-O(1)$.

Result 12.

For $N=2^d$ cards, one physical Thorp shuffle pairs corresponding cards in the two deck halves, independently orders each pair by a fair coin, and interleaves. Its law is $q_d$ on $S_N$; $U_N$ is uniform. A sweep uses each binary-coordinate matching once with independent fair switches, hence costs $d$ physical shuffles. Total variation means half the sum of absolute mass differences. Let $B_N$ denote the sweep operator. For $u+v+l=N$, partitions $\alpha\vdash u$, $\beta\vdash v$, $\gamma\vdash l$, and $\lambda\vdash N$, suppose the restriction of $V_\lambda$ to $S_u\times S_v\times S_l$ contains $V_\alpha\otimes V_{\beta^{\mathrm t}}\otimes V_\gamma$, with arbitrary multiplicity. Set \[ F(\alpha,\beta)=\sum_{\alpha_i>0}\alpha_i\log\frac{u+v}{\alpha_i} +\sum_{\beta_j>0}\beta_j\log\frac{u+v}{\beta_j}, \] interpreted as zero for $u+v=0$. For each sufficiently small fixed $\bar\eta>0$ and sufficiently small $0<\bar\kappa<\bar\eta/256$, there exists an integer $r\ge1$ such that every occurrence above satisfies \[ \log\left(D_\lambda\operatorname{Tr}_{V_\lambda}(B_N^*B_N)^r\right) \le\eta_dF(\alpha,\beta)+g_N(l), \] \[ \eta_d=\bar\eta(1-1/(2\sqrt d)),\quad\kappa_d=\bar\kappa(1-1/(2\sqrt d)),\quad g_N(l)=\max\{0,\kappa_dl\log N-l\log(N/l)\}. \] Use $g_N(0)=0$ and $\log0=-\infty$; empty representation factors have dimension one.

Outline of the argument

The permanent inequality feeds a four-row moment recursion. Squared multiplicities are controlled through hook deficits, while encounter forests bound sparse stopping costs; summing these against representation dimensions and using independent forward sweeps gives full-law contraction. Entropy of compatible placements bounds regular representation moments and singular ranks. Conditional column exposures, inverse-color traces, and fractional-density interpolation give contraction through the different sparse and dense ranges, including asymmetric grids. Prescribed trajectories are assigned explicit costs in the representation calculation. Positive tensor densities and a hook-level moment induction establish a common perturbation interval, allowing analytic transfer from larger coordinate lines to the physical binary sweep. An adapted-noise argument tracks joint endpoint information against the revealed base trajectories. Predictable-domain and Walsh-coordinate estimates account for the cyclic schedule, and two-block autocorrelation plus Fourier transfer yields the stated $2048d$ full-deck bound.

A revealed switching environment defines a permutation kernel. Preparation and active intervals are truncated with controlled costs, then trace estimates give chunk contraction; a second route uses reset minorization and central relative increments to reach conditional uniformity. Central projections retain full Fourier matrices when information is taken over disjoint coset systems. Common trimming and branching degree counts bound the permitted coefficient spaces; keeping the observed partition random allows the partial information to control convolution globally. A conditional flow retains one sweep of memory and shows contraction of recent switching noise. Representation-degree estimates lift eight large marginals to the full group, and convolution comparison gives the total-variation bound; counting possible outputs gives the lower bound. Changing position frames makes online partial-card observations comparable to ordinary injection marginals. Representation-degree sums turn large-marginal control into full-law control, and independent shear comparisons strengthen the fixed-list estimate used by Fourier transfer.

Coarse smoothing handles dense representations, while a partial-deck deformation controls almost-full first rows. Angles between grid subgroup projections are tested on random subspaces, and a uniform moment induction sums their regular-trace contributions. Routing certificates and factorial moments control repeated irreducible copies. Tail smoothing treats all partial decks, while exact-injection contact cancellation and cycle traces give representation contraction that can be summed over dimensions. Signed representations on occupied cells are weighted by hook trimming. Row and column subgroup projections bound their Fourier operators, and Schatten interpolation combines dense contraction with separate sparse-representation estimates to control the whole permutation law. Signed tensor densities encode stabilizers and marked spin occurrences. Hook-entropy and marked-site trace bounds are combined with minimized tag and deletion budgets; inverse-density interpolation and paired diagram accounting control the complete Fourier sum.

Formal verification

For family 238, the documented entries include the $1600d$ full-deck mixing theorem, finite partial-permutation Fourier bounds, and routing, conditional, signed-moment, and trace estimates. The partial-permutation entry alone does not assert the two-factor asymptotic transfer; a separate conditional route has the larger $16040400d$ bound. The listed Comparator files are BinarySweep.lean, CoordinateSweeps.lean, CoordinateTrace.lean, FourRowPermanent.lean, OccupiedOverlap.lean, PartialPermutation.lean, SignedSweepMoment.lean, SpinAngle.lean, ThorpFirstReciprocal.lean, ThorpRemaining.lean, ThorpRouting.lean, ThorpWeightedCompatibility.lean, WeightedSweepMoments.lean. Named declarations include OAI.CoordinateSweeps.conditional_main, OAI.ThorpCompatibility.weightedCompatibility_main, OAI.ThorpNine.main, OAI.binary_sweep_contraction_and_mixing. This site has not executed the Lean code. The scope descriptions do not certify the remaining manuscript arguments.

Status caveat

OpenAI attributes these manuscripts to work by an internal model. Its release cautions that arguments without formalization can contain mistakes. This catalogue has not independently checked the proofs; the labels report the mathematical claims attributed to OpenAI.

Sources

• OpenAI, A strict four-row permanent inequality and permutation moments, 2026-09-26; citation key OAI:A-strict-four-row-permanent-inequality-and-permutation-moments-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:moment.
• OpenAI, Compatibility entropy and the spectrum of a Thorp sweep, 2026-09-26; citation key OAI:Compatibility-entropy-and-the-spectrum-of-a-Thorp-sweep-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: e:vanishing-mixing.
• OpenAI, Conditional coordinate sweeps and analytic transfer, 2026-09-26; citation key OAI:Conditional-coordinate-sweeps-and-analytic-transfer-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:binary.
• OpenAI, Conditional information under deterministic coordinate sweeps, 2026-09-26; citation key OAI:Conditional-information-under-deterministic-coordinate-sweeps-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:first-main.
• OpenAI, Conditional permutations in a revealed switching environment, 2026-09-26; citation key OAI:Conditional-permutations-in-a-revealed-switching-environment-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:methods.
• OpenAI, From partial permutation information to Fourier bounds, 2026-09-26; citation key OAI:From-partial-permutation-information-to-Fourier-bounds-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: l:main.
• OpenAI, Optimal-order mixing of the Thorp shuffle, 2026-09-26; citation key OAI:Optimal-order-mixing-of-the-Thorp-shuffle-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:mixing.
• OpenAI, Random coordinate frames and partial permutation laws, 2026-09-26; citation key OAI:Random-coordinate-frames-and-partial-permutation-laws-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main.
• OpenAI, Random-subspace tests and trace smoothing for coordinate sweeps, 2026-09-26; citation key OAI:Random-subspace-tests-and-trace-smoothing-for-coordinate-sweeps-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: ten:lowplanes:main.
• OpenAI, Routing densities and representation contraction for Thorp sweeps, 2026-09-26; citation key OAI:Routing-densities-and-representation-contraction-for-Thorp-sweeps-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: fac:main.
• OpenAI, Row–column symmetry and contraction of coordinate sweeps, 2026-09-26; citation key OAI:Row-column-symmetry-and-contraction-of-coordinate-sweeps-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: cor:optimal-mixing.
• OpenAI, Signed tensor densities and diagram budgets for the Thorp shuffle, 2026-09-26; citation key OAI:Signed-tensor-densities-and-diagram-budgets-for-coordinate-sweeps-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: ten:spin:main.
• Family 238: Lean scope.
• Comparator BinarySweep.json.
• Comparator BinarySweep.lean.
• Comparator CoordinateSweeps.json.
• Comparator CoordinateSweeps.lean.
• Comparator CoordinateTrace.json.
• Comparator CoordinateTrace.lean.
• Comparator FourRowPermanent.json.
• Comparator FourRowPermanent.lean.
• Comparator OccupiedOverlap.json.
• Comparator OccupiedOverlap.lean.
• Comparator PartialPermutation.json.
• Comparator PartialPermutation.lean.
• Comparator SignedSweepMoment.json.
• Comparator SignedSweepMoment.lean.
• Comparator SpinAngle.json.
• Comparator SpinAngle.lean.
• Comparator ThorpFirstReciprocal.json.
• Comparator ThorpFirstReciprocal.lean.
• Comparator ThorpRemaining.json.
• Comparator ThorpRemaining.lean.
• Comparator ThorpRouting.json.
• Comparator ThorpRouting.lean.
• Comparator ThorpWeightedCompatibility.json.
• Comparator ThorpWeightedCompatibility.lean.
• Comparator WeightedSweepMoments.json.
• Comparator WeightedSweepMoments.lean.
• OpenAI catalogue entry.