Lean statement

One-sided angle bound for signed spin types

Lean is a language for mathematical statements and proofs that a computer can verify. This page shows one statement file from OpenAI’s release, possible paper matches and independent reports. The code-like names below identify the definitions or theorems selected by the proof-verification settings.

Theorem selected for verification: OAI.SpinAngle.TypeAngle.one_sided_type_angle

Lean statement file: SpinAngle.leanShow on the mapOpenAI’s Lean catalogue does not list this as a main result; the release’s Lean notes for family 238 link it.

See the candidate theorem Who ran the proof-verification program Report a comparison with the paper (GitHub issue)

Problems reported

Problem reported The post notes a sorry inside a definition that is a proof obligation, and that Comparator lets the rest of the definition change. Alex Meiburg, Several of the comparator challenges in the OpenAI release are broken and hackable, 2026-10-08 Source
Proof verification reported unsuccessful With the definition holes pinned, Comparator stops on a universe difference in a variable block of the challenge file; the author says they are fixing it and re-running. Jack McCarthy, Re-running Comparator with the definition holes pinned, 2026-10-09 Source
Correction Removing the three definition holes broke the check on a universe-name mismatch; a small fix to the solution makes it pass with no holes (Lean kernel only, no sandbox). Jack McCarthy, OpenAI math: Comparator fixes (mirror of openai/math at fd4aeeb), 2026-10-09 Source

The Lean statement

The lines of the Lean statement that state the theorem, then the definitions in the file that it uses.

theorem one_sided_type_angle (W : Finset (R × C))    (D : TypeLabel q) (H : C → TypeLabel q) (K : R → TypeLabel q)    (hD : D.size = W.card)    (hH : ∀ j, (H j).size = Fintype.card (TypeBlocks.Fiber (column W) j))    (hK : ∀ i, (K i).size = Fintype.card (TypeBlocks.Fiber (row W) i)) :    (‖TypeBlocks.projection (column W) H * TypeBlocks.projection (row W) K * D.projection W‖ ^ 2 ≤      min 1 (Real.exp (TypeBlocks.entropy H + TypeBlocks.entropy K - D.entropy) *        (TypeBlocks.dimension H : ℝ) * (TypeBlocks.dimension K : ℝ) * phi W)) ∧    (min 1 (Real.exp (TypeBlocks.entropy H + TypeBlocks.entropy K - D.entropy) *        (TypeBlocks.dimension H : ℝ) * (TypeBlocks.dimension K : ℝ) * phi W) ≤      min 1 (Real.exp (TypeBlocks.entropy H + TypeBlocks.entropy K - D.entropy +        (Fintype.card R * Fintype.card C - W.card : ℕ)) *        (TypeBlocks.dimension H : ℝ) * (TypeBlocks.dimension K : ℝ))) ∧    TypeBlocks.dimension H * TypeBlocks.dimension K ≤      (W.card + 1) ^ ((Fintype.card R + Fintype.card C) * q * (q - 1)) := by  sorry

A Lean statement states the theorem and leaves its proof as sorry on purpose. OpenAI’s proof is in a separate solution module, and a program called Comparator checks that proof against this statement.

Definitions needed to read it

Local definitions the statement names, followed through the definitions they name in turn. The match is by name in the source text, so a name reached only through notation can be missed; the full file is below.

definition OAI.SpinAngle.Specht.cyclic line 16

def cyclic (ρ : Representation ℂ G E) (e : E) : Subrepresentation ρ where

Show the remaining 12 lines

  toSubmodule := Submodule.span ℂ (Set.range fun g => ρ g e)  apply_mem_toSubmodule g := by    intro v hv    induction hv using Submodule.span_induction with    | mem v hv =>      obtain ⟨h, rfl⟩ := hv      exact Submodule.subset_span ⟨g * h, by simp⟩    | zero => simp    | add x y hx hy ihx ihy =>      simpa using (Submodule.span ℂ (Set.range fun h => ρ h e)).add_mem ihx ihy    | smul a x hx ih =>      simpa using (Submodule.span ℂ (Set.range fun h => ρ h e)).smul_mem a ih

definition OAI.SpinAngle.TensorRep.tensor line 35

def tensor (a : ι → Matrix n n ℂ) : Matrix (ι → n) (ι → n) ℂ :=  fun x y => ∏ i, a i (x i) (y i)

definition OAI.SpinAngle.TensorRep.action line 89

def action : Matrix n n ℂ →* Module.End ℂ (EuclideanSpace ℂ (ι → n)) where  toFun a := Matrix.toEuclideanLin (tensor (fun _ : ι => a))  map_one' := by rw [tensor_one, toEuclideanLin_one (ι := ι)]  map_mul' a b := by rw [tensor_mul, toEuclideanLin_mul (ι := ι)]

definition OAI.SpinAngle.TensorRep.rep line 94

def rep : Representation ℂ (Matrix.unitaryGroup n ℂ) (EuclideanSpace ℂ (ι → n)) :=  action.comp (Matrix.unitaryGroup n ℂ).subtype

definition OAI.SpinAngle.Specht.PermutationSpace.alternator line 130

def alternator (ι : H →* G) (χ : H →* ℂ) : Module.End ℂ (EuclideanSpace ℂ X) :=  ∑ h, χ h • rep (ι h)omit [Fintype X] in

definition OAI.SpinAngle.Specht.complexSign line 162

def complexSign : Equiv.Perm α →* ℂ where  toFun g := ((Equiv.Perm.sign g : ℤˣ) : ℤ)  map_one' := by simp  map_mul' := by intro g h; simp

abbreviation OAI.SpinAngle.Young.Cells line 174

abbrev Cells (D : YoungDiagram) := {p : ℕ × ℕ // p ∈ D.cells}

definition OAI.SpinAngle.PolynomialCarrier.columnGroup line 208

def columnGroup (D : YoungDiagram) : Subgroup (Equiv.Perm (Cells D)) where  carrier := {g | ∀ x, (g x).val.2 = x.val.2}  one_mem' := fun _ => rfl  mul_mem' := by intro g h hg hh x; exact (hg (h x)).trans (hh x)  inv_mem' := by    intro g hg x    simpa using (hg (g⁻¹ x)).symm

abbreviation OAI.SpinAngle.PolynomialCarrier.TensorSpace line 217
```
abbrev TensorSpace := EuclideanSpace ℂ (Cells D → Fin q)
```

definition OAI.SpinAngle.PolynomialCarrier.alternating line 219

def alternating : Subrepresentation (TensorRep.rep (ι := Cells D) (n := Fin q)) where

Show the remaining 11 lines

  toSubmodule := {    carrier := {v | ∀ g : columnGroup D,      PermutationSpace.rep (g : Equiv.Perm (Cells D)) v = complexSign g.val • v}    zero_mem' := by intro g; simp    add_mem' := by intro x y hx hy g; simp [map_add, hx g, hy g, smul_add]    smul_mem' := by intro c x hx g; simp [map_smul, hx g, smul_comm c] }  apply_mem_toSubmodule a := by    intro v hv g    change PermutationSpace.rep g.val (TensorRep.action (a : Matrix (Fin q) (Fin q) ℂ) v) = _    rw [← action_site_commute, hv g, map_smul]    rfl

definition OAI.SpinAngle.PolynomialCarrier.rowColor line 234

def rowColor : Cells D → Fin q := fun x => ⟨x.val.1, by  have hm := D.up_left_mem le_rfl (Nat.zero_le x.val.2) x.property  have hl := YoungDiagram.mem_iff_lt_colLen.mp hm  exact lt_of_lt_of_le hl hq⟩

definition OAI.SpinAngle.PolynomialCarrier.highest line 239

def highest : TensorSpace D q := by  classical  exact PermutationSpace.alternator (columnGroup D).subtype    (complexSign.comp (columnGroup D).subtype)    (EuclideanSpace.single (rowColor D q hq) (1 : ℂ))

definition OAI.SpinAngle.PolynomialCarrier.ordinary line 255

def ordinary : Subrepresentation (alternating D q).toRepresentation :=  cyclic (alternating D q).toRepresentation    (⟨highest D q hq, highest_mem D q hq⟩ : (alternating D q).toSubmodule)

abbreviation OAI.SpinAngle.PolynomialCarrier.Carrier line 259
```
abbrev Carrier : Type := (ordinary D q hq).toSubmodule
```

definition OAI.SpinAngle.EntropyMonomial.entropy line 337

def entropy (n : ι → ℕ) : ℝ :=  (∑ i, n i : ℕ) * Real.log (∑ i, n i : ℕ) - ∑ i, (n i : ℝ) * Real.log (n i)

definition OAI.SpinAngle.Isotypic.space line 349

def space : Subrepresentation σ where

Show the remaining 12 lines

  toSubmodule := Submodule.span ℂ (Set.range fun z : ρ.IntertwiningMap σ × E => z.1 z.2)  apply_mem_toSubmodule := by    intro g v hv    induction hv using Submodule.span_induction with    | mem v hv =>      obtain ⟨⟨f,x⟩,rfl⟩ := hv      apply Submodule.subset_span      refine ⟨⟨f,ρ g x⟩, ?_⟩      exact Representation.IntertwiningMap.isIntertwining ρ σ f g x    | zero => simp    | add x y hx hy ihx ihy => simpa only [map_add] using Submodule.add_mem _ ihx ihy    | smul a x hx ih => simpa only [map_smul] using Submodule.smul_mem _ a ih

definition OAI.SpinAngle.Isotypic.projection line 363

def projection : F →L[ℂ] F := (space ρ σ).toSubmodule.starProjection

definition OAI.SpinAngle.SignedCarrier.dimension line 392

def dimension : ℕ := Module.finrank ℂ (Carrier a b q ha hb)

definition OAI.SpinAngle.missingCellFactor line 406

def missingCellFactor (m b : ℕ) : ℝ :=  if b < m then ((m : ℝ) / (m - b : ℕ)) ^ (m - b) else 1

definition OAI.SpinAngle.missingCellProductFactor line 409

def missingCellProductFactor {ι : Type*} [Fintype ι] (m : ℕ) (b : ι → ℕ) : ℝ :=  ∏ i, missingCellFactor m (b i)

definition OAI.SpinAngle.occupiedRow line 414

def occupiedRow (W : Finset (R × C)) (i : R) : Finset C :=  Finset.univ.filter (fun j => (i, j) ∈ W)

definition OAI.SpinAngle.missingInRow line 417

def missingInRow (W : Finset (R × C)) (i : R) : ℕ :=  Fintype.card C - (occupiedRow W i).card

abbreviation OAI.SpinAngle.BlockTensor.Fiber line 438
```
abbrev Fiber (j : J) := {i : τ // f i = j}
```

structure OAI.SpinAngle.TypeLabel line 466

structure TypeLabel (q : ℕ) where  even : YoungDiagram  odd : YoungDiagram  even_height : even.colLen 0 ≤ q  odd_height : odd.colLen 0 ≤ q

4 more definitions are reached the same way; the full file lists them.

Definitions taken from OpenAI’s library 3

Comparator compares only the name and type of each definition listed here. When a theorem is configured, its proof uses the definition in OpenAI’s solution library. Read that definition as well as the one in this file when comparing the statement with the paper.

Comparator checks the name and type of row; its definition is in OpenAI’s library, in the modules that OAI.RepresentationTheory.SpinAngle.TypeAngle imports.
Comparator checks the name and type of column; its definition is in OpenAI’s library, in the modules that OAI.RepresentationTheory.SpinAngle.TypeAngle imports.
Comparator checks the name and type of phi; its definition is in OpenAI’s library, in the modules that OAI.RepresentationTheory.SpinAngle.TypeAngle imports.

Possible paper match, with no recorded review

No paper statement clearly matched the Lean wording. Statement Map, the program that collects Atlas’s source records, selected this possible match using words in OpenAI’s catalogue and Lean note. No review of whether the statements mean the same thing is recorded.

Shared with the catalogue’s wording or OpenAI’s note, none of them matched in the Lean text: after, bound, constant, deck, distance, fixed, full, including and twelve more.

Corollary 1.3 of Compatibility entropy and the spectrum of a Thorp sweep

Corollary (Singular ranks and full-deck mixing)

For every nontrivial \lambda\vdash n and 1\le r\le D_\lambda,

s_r(T_{n,\lambda})\le(16D_\lambda r)^{-1/(2p_*)}.

If s_j(T_n) denotes the full regular singular list, including all multiplicities and zeros, then

s_j(T_n)\le j^{-1/(2p_*)}\qquad(1\le j\le n!).

The constant singular value is the first value. The physical Thorp chain has worst-start 1/4 mixing time \Theta(d); more precisely its lower bound is 2d-O(1). For every fixed integer M>p_*, the worst-start total-variation distance after Md physical shuffles tends to zero as d\to\infty.

Section 1, Introduction Read it in the paper TeX source, line 53

Show the TeX

For every nontrivial $\lambda\vdash n$ and $1\le r\le D_\lambda$,
\[
 s_r(T_{n,\lambda})\le(16D_\lambda r)^{-1/(2p_*)}.
\]
If $s_j(T_n)$ denotes the full regular singular list, including all multiplicities and zeros, then
\[
 s_j(T_n)\le j^{-1/(2p_*)}\qquad(1\le j\le n!).
\]
The constant singular value is the first value. The physical Thorp chain has worst-start $1/4$ mixing time $\Theta(d)$; more precisely its lower bound is $2d-O(1)$. For every fixed integer $M>p_*$, the worst-start total-variation distance after $Md$ physical shuffles tends to zero as $d\to\infty$.

Other possible paper matches, closest wording first

Theorem 3.2 of Signed tensor densities and diagram budgets for the Thorp shuffle. Words of the Lean statement, its names split into words, that also appear in the theorem: phi, spin, angle, missing, occupied, sided and ten more. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: global, rectangle and types.
Corollary 5.2 of Signed tensor densities and diagram budgets for the Thorp shuffle. Words of the Lean statement, its names split into words, that also appear in the theorem: angle, missing, occupied, sided, cells, min and eight more. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: rectangle, conclusion and full.
Proposition 5.3 of Signed tensor densities and diagram budgets for the Thorp shuffle. Words of the Lean statement, its names split into words, that also appear in the theorem: occupied, sided, cells, min, tensor, factors and five more. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: overlap, supported and bound.
Theorem 9.2 of From partial permutation information to Fourier bounds. Words of the Lean statement, its names split into words, that also appear in the theorem: fibers, matrix, sided, min, product, size and four more. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: mixes, total and variation.
Proposition 7.2 of Signed tensor densities and diagram budgets for the Thorp shuffle. Words of the Lean statement, its names split into words, that also appear in the theorem: min, real, entropy and exp. Found in the paper’s title, which its main theorem states: diagram, tensor and signed. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: bound.
Proposition 10.2 of Signed tensor densities and diagram budgets for the Thorp shuffle. Words of the Lean statement, its names split into words, that also appear in the theorem: cells, diagram, real, size, columns, rows and two more. Found in the paper’s title, which its main theorem states: tensor and signed. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: estimate.

How Atlas selects possible matches: it compares words in the Lean statement with every statement in the family. It also splits Lean names into words. The release’s label and note receive less weight; a main theorem wins a close match. If the Lean wording yields no clear match, Atlas uses the catalogue description. This selects passages to compare; it does not establish that they mean the same thing.

Reported Comparator runs

three independent groups report that Comparator accepted runs for this Lean statement file: Carlos Toledo’s cert-machine; MathVet; Neal McBurnett’s openai-math-lean-tooling. Each group reports its own Comparator run for this statement file. Atlas has not repeated the runs.

For a configured theorem, Comparator tests whether OpenAI’s proof proves the exact Lean statement. Some files instead configure definitions for comparison by name and type. Acceptance does not establish that the statement means the same thing as the paper’s theorem.

Carlos Toledo’s cert-machine

How they ran it, in their words

Every Comparator challenge re-run on Linux with nanoda switched on, decided by a preregistered rule; every family’s challenge statements read against OpenAI’s headline, clause by clause. Decider: Comparator (leanprover/comparator d03acab1 = tag v4.34.0, built with the release’s toolchain v4.34.1), lean4export 076e8e57, landrun 811cfff5, nanoda_lib 3a240721 — on GitHub’s Linux runners (.github/workflows/openai-math-kernel.yml), one j…

Accepted Their term: “CERTIFIED”.
Re-run through Comparator with the independent nanoda kernel switched on: Lean’s kernel and nanoda both accept OpenAI’s solution.
Reported 10 October 2026, at the release version shown here. Original verification report

MathVet

How they ran it, in their words

An independent, model-assisted, pre-referee reading of each family’s challenge statements against its headline claim under a published rubric (PROTOCOL.md), with its own Comparator runs per challenge. Its protocol describes a planned error-rate study; this import does not establish that the study has been completed.

Accepted Their term: “comparator-sandboxed-pass”.
Re-run through Comparator in a sandboxed virtual machine: accepted.
Reported 8 October 2026, at the release version shown here. Original verification report

Neal McBurnett’s openai-math-lean-tooling

How they ran it, in their words

Each challenge’s solution is built and checked by Comparator at the pinned release, on Lean leanprover/lean4:v4.34.1, recording the verdict, the check time and the peak memory; the run was still in progress at this snapshot (192 accepted, 224 pending).

Accepted Their term: “accepted”.
Re-run through Comparator with Lean’s kernel: accepted (the check took 439 s).
Reported 10 October 2026, at the release version shown here. Original verification report

What an accepted Comparator run would establish

If Comparator is run under this configuration and accepts, the solution proves the configured theorem using only the allowed axioms, and the Lean kernel accepts every step.

Definitions compared by name and type only (3): row, column, phi. Their bodies come from OpenAI’s solution library.

Allowed axioms: propext, Quot.sound, Classical.choice

Acceptance leaves open whether the Lean statement means the same thing as the paper’s theorem, whether the paper’s other claims are correct, and whether the result is new. Those questions require comparing the definitions and statements, reviewing the paper’s arguments, and reading the earlier literature.

Do family 238’s Lean statements express the advertised result?

These assessments compare all the family’s Lean statements with the whole result OpenAI describes in its catalogue. They do not assess this statement alone. Each group uses its own published rules.

MathVet and cert-machine agree on how much of the advertised result the Lean statements express.

MathVet
Finds the whole advertised result stated or implied Their term: “full”.
The challenge statements imply the headline claim after unpacking definitions or one routine step. Their record
Their note: ThorpResults.remaining_main (ThorpRemaining) is a conjunction whose last conjunct OptimalOrderMain := IsTheta atTop (mixingTime d) (log (2^d)) states exactly the Θ(log N) mixing for N = 2^d cards, with mixingTime d := sInf {t | distance d t ≤ 1/4}, distance d t := tv (law d t) (uniform d) the total-variation distance of the full permutation law (and InformationMain records that lawFrom from any starting deck has the same distance, plus distance d (2048 d) → 0); the 12 other challenge files are supporting Fourier/representation estimates (regular_trace_smoothing, binary_sweep_contraction_and_mixing, robust_permanent, ...). All of them state estimates for the same hand-built Thorp shuffle.
Definitions the group asks readers to compare with the paper: Custom Thorp shuffle and 'mixing time': step (d+1) c := (pairSwitch d c on the head bit, then rotate the coordinate order) on State d := Equiv.Perm (Fin d → Bool) with Coins (d+1) = (Fin d → Bool) → Bool iid fair coins, fairMass, tv, mixingTime d := sInf {t | distance d t ≤ 1/4}; this is the standard pair-swap-and-interleave Thorp shuffle and TV-from-uniform with ε = 1/4, but it is a hand-written model and the Θ-statement hides explicit constants (1600d, 2048d, ...). OccupiedOverlap shows an axiom_files hit (HookModel.lean) that is a doc-comment false positive.
Carlos Toledo’s cert-machine
Finds the whole advertised result stated or implied Their term: “MATCHES”.
The challenge statements state the headline as OpenAI wrote it. Their record

Read the complete assessments on the family page.

OpenAI’s own note on what this Lean statement covers

“The linked supporting angle bound controls the overlap of row, column, and global signed-type projections on an occupied rectangle, with explicit entropy, dimension, and missing-cell factors. These selected estimates support the paper's full-density argument; the full $L^2$ and total-variation mixing conclusion is outside them.”
Quoted from OpenAI’s Lean note for this family

An AI agent drafted an interpretation of that note, classifying this statement as “states a supporting result”. No human review of the draft is recorded.

Supporting material

The complete Lean statement file

539 lines, copied from release version fd4aeeb. A name defined in this file links to its line; pointing at the name shows its definition.

Declared in this fileOpenAI’s library at fd4aeebOther linked names open the current documentation for Mathlib, Lean’s mathematical library.

Links in the file: 193 to its own declarations, 313 to Mathlib’s documentation. 17 declared names also link to the same declaration in OpenAI’s library. 2 identifiers stay plain because they resolve to no single declaration: variables Lean binds automatically, notation, or names the scan of the pinned sources did not find. 1 of them could name more than one declaration. OpenAI uses Mathlib version d13f23b. The linked documentation describes the current version, so names that have since changed may be missing there.

import Mathlibnamespace OAInoncomputable sectionopen scoped BigOperators ComplexConjugate InnerProductSpace Matrix TensorProductopen scoped Matrix.Norms.L2Operator MatrixOrder ComplexOrdernamespace SpinAngle.Spechtvariable {G : Type*} [Group G]variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℂ E]def cyclic (ρ : Representation ℂ G E) (e : E) : Subrepresentation ρ where  toSubmodule := Submodule.span ℂ (Set.range fun g => ρ g e)  apply_mem_toSubmodule g := by    intro v hv    induction hv using Submodule.span_induction with    | mem v hv =>      obtain ⟨h, rfl⟩ := hv      exact Submodule.subset_span ⟨g * h, by simp⟩    | zero => simp    | add x y hx hy ihx ihy =>      simpa using (Submodule.span ℂ (Set.range fun h => ρ h e)).add_mem ihx ihy    | smul a x hx ih =>      simpa using (Submodule.span ℂ (Set.range fun h => ρ h e)).smul_mem a ihend SpinAngle.Spechtnamespace SpinAngle.TensorRepvariable {ι n : Type*} [Fintype ι] [DecidableEq ι] [Fintype n] [DecidableEq n]def tensor (a : ι → Matrix n n ℂ) : Matrix (ι → n) (ι → n) ℂ :=  fun x y => ∏ i, a i (x i) (y i)lemma tensor_mul    {ι : Type*} {n : Type*}    [Fintype ι]    [DecidableEq ι]    [Fintype n]    [DecidableEq n] (a b : ι → Matrix n n ℂ) :    tensor (fun i => a i * b i) = tensor a * tensor b := by  ext x y  simp only [tensor, Matrix.mul_apply, ← Finset.prod_mul_distrib]  symm  simpa using (Finset.sum_prod_piFinset (ι := ι) Finset.univ    (fun i j => a i (x i) j * b i j (y i)))lemma tensor_one    {ι : Type*} {n : Type*}    [Fintype ι]    [DecidableEq ι]    [Fintype n]    [DecidableEq n] : tensor (fun _ : ι => (1 : Matrix n n ℂ)) = 1 := by  ext x y  classical  by_cases h : x = y  · subst y    simp [tensor]  · obtain ⟨i, hi⟩ := Function.ne_iff.mp h    simp only [tensor, Matrix.one_apply, ite_eq_right h]    apply Finset.prod_eq_zero (Finset.mem_univ i)    simp [hi]lemma toEuclideanLin_mul    {ι : Type*} {n : Type*}    [Fintype ι]    [DecidableEq ι]    [Fintype n]    [DecidableEq n] (a b : Matrix n n ℂ) :    Matrix.toEuclideanLin (a * b) =      Matrix.toEuclideanLin a * Matrix.toEuclideanLin b := by  ext v x  change ((a * b) *ᵥ (WithLp.ofLp v)) x = (a *ᵥ (b *ᵥ (WithLp.ofLp v))) x  rw [Matrix.mulVec_mulVec]lemma toEuclideanLin_one    {ι : Type*} {n : Type*}    [Fintype ι]    [DecidableEq ι]    [Fintype n]    [DecidableEq n] : Matrix.toEuclideanLin (1 : Matrix n n ℂ) = 1 := by  ext v x  change ((1 : Matrix n n ℂ) *ᵥ (WithLp.ofLp v)) x = v x  simpdef action : Matrix n n ℂ →* Module.End ℂ (EuclideanSpace ℂ (ι → n)) where  toFun a := Matrix.toEuclideanLin (tensor (fun _ : ι => a))  map_one' := by rw [tensor_one, toEuclideanLin_one (ι := ι)]  map_mul' a b := by rw [tensor_mul, toEuclideanLin_mul (ι := ι)]def rep : Representation ℂ (Matrix.unitaryGroup n ℂ) (EuclideanSpace ℂ (ι → n)) :=  action.comp (Matrix.unitaryGroup n ℂ).subtypelemma tensor_reindex    {ι : Type*} {n : Type*}    [Fintype ι]    [DecidableEq ι]    [Fintype n]    [DecidableEq n] (a : Matrix n n ℂ) (σ : Equiv.Perm ι) (x y : ι → n) :    tensor (fun _ : ι => a) (x ∘ σ) (y ∘ σ) = tensor (fun _ : ι => a) x y := by  exact Equiv.prod_comp σ (fun i => a (x i) (y i))end SpinAngle.TensorRepnamespace SpinAngle.Spechtopen scoped Classicalvariable {G : Type*} [Group G]namespace PermutationSpaceopen scoped Classicalvariable {X : Type*} [Fintype X] [MulAction G X]def rep : Representation ℂ G (EuclideanSpace ℂ X) where  toFun g := {    toFun v := WithLp.toLp 2 (fun x => v (g⁻¹ • x))    map_add' := by intro v w; rfl    map_smul' := by intro a v; rfl }  map_one' := by ext v x; simp  map_mul' := by    intro g h    ext v x    change v ((g * h)⁻¹ • x) = v (h⁻¹ • g⁻¹ • x)    simp [mul_smul]variable {H : Type*} [Group H] [Fintype H]def alternator (ι : H →* G) (χ : H →* ℂ) : Module.End ℂ (EuclideanSpace ℂ X) :=  ∑ h, χ h • rep (ι h)omit [Fintype X] inlemma alternator_apply (ι : H →* G) (χ : H →* ℂ) (v : EuclideanSpace ℂ X) :    alternator ι χ v = ∑ h, χ h • rep (ι h) v := by  simp [alternator, LinearMap.sum_apply]lemma rep_alternator    {G : Type*} {H : Type*} {X : Type*}    [Group G]    [Group H]    [Fintype H]    [Fintype X]    [MulAction G X] (ι : H →* G) (χ : H →* ℂ) (a : H)    (v : EuclideanSpace ℂ X) :    rep (ι a) (alternator ι χ v) = χ a⁻¹ • alternator ι χ v := by  rw [alternator_apply, map_sum, Finset.smul_sum]  have he := Equiv.sum_comp (Equiv.mulLeft a)    (fun h => χ a⁻¹ • (χ h • (rep (ι h) v : EuclideanSpace ℂ X)))  rw [← he]  apply Finset.sum_congr rfl  intro h _  simp only [Equiv.coe_mulLeft, smul_smul, map_mul, map_smul]  rw [show χ a⁻¹ * (χ a * χ h) = χ h by    rw [← mul_assoc, ← map_mul, inv_mul_cancel, map_one, one_mul]]  rflend PermutationSpacevariable {α : Type*} [Fintype α]def complexSign : Equiv.Perm α →* ℂ where  toFun g := ((Equiv.Perm.sign g : ℤˣ) : ℤ)  map_one' := by simp  map_mul' := by intro g h; simp@[simp] lemma complexSign_inv (g : Equiv.Perm α) : complexSign g⁻¹ = complexSign g := by  simp [complexSign]end SpinAngle.Spechtnamespace SpinAngle.Youngabbrev Cells (D : YoungDiagram) := {p : ℕ × ℕ // p ∈ D.cells}end SpinAngle.Youngnamespace SpinAngle.PolynomialCarrieropen scoped Classical Matrixopen SpinAngle.Specht SpinAngle.Youngvariable {ι n : Type*} [Fintype ι] [DecidableEq ι] [Fintype n] [DecidableEq n]instance coloringAction : MulAction (Equiv.Perm ι) (ι → n) where  smul g x := x ∘ g.symm  one_smul _ := rfl  mul_smul _ _ _ := rfldef reindex (g : Equiv.Perm ι) : (ι → n) ≃ (ι → n) where  toFun x := x ∘ g  invFun x := x ∘ g.symm  left_inv x := by funext i; simp  right_inv x := by funext i; simplemma action_site_commute (a : Matrix n n ℂ) (g : Equiv.Perm ι)    (v : EuclideanSpace ℂ (ι → n)) :    TensorRep.action a (PermutationSpace.rep g v) =      PermutationSpace.rep g (TensorRep.action a v) := by  ext x  change (∑ y, TensorRep.tensor (fun _ : ι => a) x y * v (y ∘ g)) =    ∑ y, TensorRep.tensor (fun _ : ι => a) (x ∘ g) y * v y  rw [← Equiv.sum_comp (reindex (n := n) g)    (fun y => TensorRep.tensor (fun _ : ι => a) (x ∘ g) y * v y)]  apply Finset.sum_congr rfl  intro y _  change _ = TensorRep.tensor (fun _ : ι => a) (x ∘ g) (y ∘ g) * v (y ∘ g)  rw [TensorRep.tensor_reindex]def columnGroup (D : YoungDiagram) : Subgroup (Equiv.Perm (Cells D)) where  carrier := {g | ∀ x, (g x).val.2 = x.val.2}  one_mem' := fun _ => rfl  mul_mem' := by intro g h hg hh x; exact (hg (h x)).trans (hh x)  inv_mem' := by    intro g hg x    simpa using (hg (g⁻¹ x)).symmvariable (D : YoungDiagram) (q : ℕ)abbrev TensorSpace := EuclideanSpace ℂ (Cells D → Fin q)def alternating : Subrepresentation (TensorRep.rep (ι := Cells D) (n := Fin q)) where  toSubmodule := {    carrier := {v | ∀ g : columnGroup D,      PermutationSpace.rep (g : Equiv.Perm (Cells D)) v = complexSign g.val • v}    zero_mem' := by intro g; simp    add_mem' := by intro x y hx hy g; simp [map_add, hx g, hy g, smul_add]    smul_mem' := by intro c x hx g; simp [map_smul, hx g, smul_comm c] }  apply_mem_toSubmodule a := by    intro v hv g    change PermutationSpace.rep g.val (TensorRep.action (a : Matrix (Fin q) (Fin q) ℂ) v) = _    rw [← action_site_commute, hv g, map_smul]    rflvariable (hq : D.colLen 0 ≤ q)def rowColor : Cells D → Fin q := fun x => ⟨x.val.1, by  have hm := D.up_left_mem le_rfl (Nat.zero_le x.val.2) x.property  have hl := YoungDiagram.mem_iff_lt_colLen.mp hm  exact lt_of_lt_of_le hl hq⟩def highest : TensorSpace D q := by  classical  exact PermutationSpace.alternator (columnGroup D).subtype    (complexSign.comp (columnGroup D).subtype)    (EuclideanSpace.single (rowColor D q hq) (1 : ℂ))lemma highest_mem : highest D q hq ∈ alternating D q := by  classical  intro g  change PermutationSpace.rep g.val (PermutationSpace.alternator _ _ _) = _  have hh := PermutationSpace.rep_alternator (columnGroup D).subtype    (complexSign.comp (columnGroup D).subtype) g (EuclideanSpace.single (rowColor D q hq) (1 : ℂ))  change PermutationSpace.rep g.val (highest D q hq) = complexSign (g.val⁻¹) • highest D q hq at hh  rw [complexSign_inv] at hh  exact hhdef ordinary : Subrepresentation (alternating D q).toRepresentation :=  cyclic (alternating D q).toRepresentation    (⟨highest D q hq, highest_mem D q hq⟩ : (alternating D q).toSubmodule)abbrev Carrier : Type := (ordinary D q hq).toSubmoduleinstance carrierInner : InnerProductSpace ℂ (Carrier D q hq) :=  @Submodule.innerProductSpace ℂ (alternating D q).toSubmodule _ _ inferInstance    (ordinary D q hq).toSubmoduleend SpinAngle.PolynomialCarriernamespace SpinAngle.ExternalTensoropen Modulevariable {E F : Type*} [NormedAddCommGroup E] [InnerProductSpace ℂ E]  [NormedAddCommGroup F] [InnerProductSpace ℂ F]  [FiniteDimensional ℂ E] [FiniteDimensional ℂ F]variable {G H : Type*} [Group G] [Group H]def rep (ρ : Representation ℂ G E) (σ : Representation ℂ H F) :    Representation ℂ (G × H) (E ⊗[ℂ] F) :=  Representation.tprod (ρ.comp (MonoidHom.fst G H)) (σ.comp (MonoidHom.snd G H))end SpinAngle.ExternalTensornamespace SpinAngle.SignedTensoropen scoped Classical Matrix TensorProduct InnerProductSpaceopen Modulevariable {q : ℕ}abbrev Spin (q : ℕ) := Fin q × Boolabbrev Mat (q : ℕ) := Matrix (Fin q) (Fin q) ℂabbrev Group (q : ℕ) := Matrix.unitaryGroup (Fin q) ℂ × Matrix.unitaryGroup (Fin q) ℂdef block : (Mat q × Mat q) →* Matrix (Spin q) (Spin q) ℂ where  toFun a := Matrix.blockDiagonal (fun b : Bool => cond b a.2 a.1)  map_one' := by    convert (Matrix.blockDiagonal_one (m := Fin q) (o := Bool) (α := ℂ)) using 1    congr 1    funext b    cases b <;> rfl  map_mul' a b := by    rw [← Matrix.blockDiagonal_mul]    congr 1    funext c    cases c <;> rfllemma block_star (a : Mat q × Mat q) : block (star a) = star (block a) := by  change Matrix.blockDiagonal (fun b : Bool => cond b (star a.2) (star a.1)) = (Matrix.blockDiagonal (fun b : Bool => cond b a.2 a.1))ᴴ  rw [Matrix.blockDiagonal_conjTranspose]  congr 1  funext b  cases b <;> rfldef blockGroup : Group q →* Matrix.unitaryGroup (Spin q) ℂ where  toFun g := ⟨block (g.1.val,g.2.val), by    rw [Matrix.mem_unitaryGroup_iff', ← block_star, ← map_mul]    have he : star (g.1.val,g.2.val) * (g.1.val,g.2.val) = 1 :=      Prod.ext g.1.property.1 g.2.property.1    rw [he, map_one]⟩  map_one' := by    apply Subtype.ext    change block (1 : Mat q × Mat q) = 1    exact block.map_one  map_mul' g h := by    apply Subtype.ext    change block ((g.1.val,g.2.val) * (h.1.val,h.2.val)) =      block (g.1.val,g.2.val) * block (h.1.val,h.2.val)    exact block.map_mul _ _variable {ι κ τ : Type*} [Fintype ι] [DecidableEq ι] [Fintype κ] [DecidableEq κ]  [Fintype τ] [DecidableEq τ]abbrev Raw := EuclideanSpace ℂ (τ → Spin q)def rep : Representation ℂ (Group q) (Raw (q := q) (τ := τ)) :=  (TensorRep.rep (ι := τ)).comp blockGroupend SpinAngle.SignedTensornamespace SpinAngle.EntropyMonomialvariable {ι : Type*} [Fintype ι]def entropy (n : ι → ℕ) : ℝ :=  (∑ i, n i : ℕ) * Real.log (∑ i, n i : ℕ) - ∑ i, (n i : ℝ) * Real.log (n i)end SpinAngle.EntropyMonomialnamespace SpinAngle.Isotypicvariable {G : Type*} [Group G]variable {E F : Type*} [NormedAddCommGroup E] [InnerProductSpace ℂ E]  [NormedAddCommGroup F] [InnerProductSpace ℂ F]  [FiniteDimensional ℂ E] [FiniteDimensional ℂ F]variable (ρ : Representation ℂ G E) (σ : Representation ℂ G F)def space : Subrepresentation σ where  toSubmodule := Submodule.span ℂ (Set.range fun z : ρ.IntertwiningMap σ × E => z.1 z.2)  apply_mem_toSubmodule := by    intro g v hv    induction hv using Submodule.span_induction with    | mem v hv =>      obtain ⟨⟨f,x⟩,rfl⟩ := hv      apply Submodule.subset_span      refine ⟨⟨f,ρ g x⟩, ?_⟩      exact Representation.IntertwiningMap.isIntertwining ρ σ f g x    | zero => simp    | add x y hx hy ihx ihy => simpa only [map_add] using Submodule.add_mem _ ihx ihy    | smul a x hx ih => simpa only [map_smul] using Submodule.smul_mem _ a ihdef projection : F →L[ℂ] F := (space ρ σ).toSubmodule.starProjectionend SpinAngle.Isotypicnamespace SpinAngle.SignedCarrieropen scoped Classical TensorProduct InnerProductSpaceopen SpinAngle.Young SpinAngle.Specht PolynomialCarrier Module SignedTensorvariable (a b : YoungDiagram) (q : ℕ) (ha : a.colLen 0 ≤ q) (hb : b.colLen 0 ≤ q)abbrev Carrier := PolynomialCarrier.Carrier a q ha ⊗[ℂ] PolynomialCarrier.Carrier b q hbinstance carrierNormed : NormedAddCommGroup (Carrier a b q ha hb) :=  TensorProduct.instNormedAddCommGroup (𝕜 := ℂ)    (E := PolynomialCarrier.Carrier a q ha) (F := PolynomialCarrier.Carrier b q hb)instance carrierInner : InnerProductSpace ℂ (Carrier a b q ha hb) :=  TensorProduct.instInnerProductSpace (𝕜 := ℂ)    (E := PolynomialCarrier.Carrier a q ha) (F := PolynomialCarrier.Carrier b q hb)instance carrierFinite : FiniteDimensional ℂ (Carrier a b q ha hb) :=  inferInstanceAs (FiniteDimensional ℂ (PolynomialCarrier.Carrier a q ha ⊗[ℂ] PolynomialCarrier.Carrier b q hb))abbrev rep : Representation ℂ (Group q) (Carrier a b q ha hb) :=  ExternalTensor.rep (E := PolynomialCarrier.Carrier a q ha)    (F := PolynomialCarrier.Carrier b q hb)    (ordinary a q ha).toRepresentation (ordinary b q hb).toRepresentationdef parts : Fin q ⊕ Fin q → ℕ := Sum.elim (fun i => a.rowLen i) (fun i => b.rowLen i)def entropy : ℝ := EntropyMonomial.entropy (parts a b q)def dimension : ℕ := Module.finrank ℂ (Carrier a b q ha hb)variable {τ : Type*} [Fintype τ] [DecidableEq τ]abbrev typeProjection : Raw (q := q) (τ := τ) →L[ℂ] Raw (q := q) (τ := τ) :=  Isotypic.projection (rep a b q ha hb) SignedTensor.repdef matrixProjection : Matrix (τ → Spin q) (τ → Spin q) ℂ :=  (Matrix.toEuclideanCLM (n := τ → Spin q) (𝕜 := ℂ)).symm (typeProjection a b q ha hb)end SpinAngle.SignedCarriernamespace SpinAngledef missingCellFactor (m b : ℕ) : ℝ :=  if b < m then ((m : ℝ) / (m - b : ℕ)) ^ (m - b) else 1def missingCellProductFactor {ι : Type*} [Fintype ι] (m : ℕ) (b : ι → ℕ) : ℝ :=  ∏ i, missingCellFactor m (b i)variable {R C : Type*} [Fintype R] [DecidableEq R] [Fintype C] [DecidableEq C]def occupiedRow (W : Finset (R × C)) (i : R) : Finset C :=  Finset.univ.filter (fun j => (i, j) ∈ W)def missingInRow (W : Finset (R × C)) (i : R) : ℕ :=  Fintype.card C - (occupiedRow W i).cardend SpinAnglenamespace SpinAngle.DependentTensorvariable {ι : Type*} [Fintype ι] [DecidableEq ι]variable {ν : ι → Type*} [∀ i, Fintype (ν i)] [∀ i, DecidableEq (ν i)]abbrev Mat (n : Type*) := Matrix n n ℂdef tensor (A : ∀ i, Mat (ν i)) : Mat (∀ i, ν i) := fun x y => ∏ i, A i (x i) (y i)end SpinAngle.DependentTensornamespace SpinAngle.BlockTensoropen DependentTensorvariable {τ J n : Type*} [Fintype τ] [DecidableEq τ] [Fintype J] [DecidableEq J]  [Fintype n] [DecidableEq n]variable (f : τ → J)abbrev Fiber (j : J) := {i : τ // f i = j}def splitEquiv : (τ → n) ≃ (∀ j : J, Fiber f j → n) where  toFun x j i := x i.val  invFun y i := y (f i) ⟨i,rfl⟩  left_inv x := rfl  right_inv y := by    funext j i    rcases i with ⟨i,hi⟩    subst j    rfldef tensor (A : ∀ j, Mat (Fiber f j → n)) : Mat (τ → n) :=  fun x y => DependentTensor.tensor A (splitEquiv f x) (splitEquiv f y)end SpinAngle.BlockTensornamespace SpinAngle.MatrixAnalysisvariable {n : Type*} [Fintype n] [DecidableEq n]abbrev Mat (n : Type*) := Matrix n n ℂend SpinAngle.MatrixAnalysisnamespace SpinAngleopen SpinAngle.Youngstructure TypeLabel (q : ℕ) where  even : YoungDiagram  odd : YoungDiagram  even_height : even.colLen 0 ≤ q  odd_height : odd.colLen 0 ≤ qnamespace TypeLabelvariable {q : ℕ}def size (D : TypeLabel q) : ℕ := Fintype.card (Cells D.even) + Fintype.card (Cells D.odd)def entropy (D : TypeLabel q) : ℝ := SignedCarrier.entropy D.even D.odd qdef dimension (D : TypeLabel q) : ℕ := SignedCarrier.dimension D.even D.odd q D.even_height D.odd_heightdef projection (D : TypeLabel q) (τ : Type*) [Fintype τ] [DecidableEq τ] :    Matrix (τ → SignedTensor.Spin q) (τ → SignedTensor.Spin q) ℂ :=  SignedCarrier.matrixProjection D.even D.odd q D.even_height D.odd_heightend TypeLabelnamespace TypeBlocksuniverse uopen MatrixAnalysisvariable {q : ℕ}variable {τ : Type*} {J : Type u} [Fintype τ] [DecidableEq τ] [Fintype J] [DecidableEq J]abbrev Fiber (f : τ → J) (j : J) := BlockTensor.Fiber f jdef projection (f : τ → J) (D : J → TypeLabel q) : Mat (τ → SignedTensor.Spin q) :=  BlockTensor.tensor f (fun j => (D j).projection (Fiber f j))def entropy (D : J → TypeLabel q) : ℝ := ∑ j, (D j).entropydef dimension (D : J → TypeLabel q) : ℕ := ∏ j, (D j).dimensionend TypeBlocksend SpinAnglenamespace SpinAngle.TypeAngleopen scoped BigOperators Matrix.Norms.L2Operator MatrixOrder ComplexOrdervariable {q : ℕ} [Nonempty (Fin q)]variable {R C : Type*}variable [Fintype R] [DecidableEq R] [Fintype C] [DecidableEq C]def row (W : Finset (R × C)) (w : W) : R := w.val.1def column (W : Finset (R × C)) (w : W) : C := w.val.2def phi (W : Finset (R × C)) : ℝ :=  missingCellProductFactor (Fintype.card C) (missingInRow W)theorem one_sided_type_angle (W : Finset (R × C))    (D : TypeLabel q) (H : C → TypeLabel q) (K : R → TypeLabel q)    (hD : D.size = W.card)    (hH : ∀ j, (H j).size = Fintype.card (TypeBlocks.Fiber (column W) j))    (hK : ∀ i, (K i).size = Fintype.card (TypeBlocks.Fiber (row W) i)) :    (‖TypeBlocks.projection (column W) H * TypeBlocks.projection (row W) K * D.projection W‖ ^ 2 ≤      min 1 (Real.exp (TypeBlocks.entropy H + TypeBlocks.entropy K - D.entropy) *        (TypeBlocks.dimension H : ℝ) * (TypeBlocks.dimension K : ℝ) * phi W)) ∧    (min 1 (Real.exp (TypeBlocks.entropy H + TypeBlocks.entropy K - D.entropy) *        (TypeBlocks.dimension H : ℝ) * (TypeBlocks.dimension K : ℝ) * phi W) ≤      min 1 (Real.exp (TypeBlocks.entropy H + TypeBlocks.entropy K - D.entropy +        (Fintype.card R * Fintype.card C - W.card : ℕ)) *        (TypeBlocks.dimension H : ℝ) * (TypeBlocks.dimension K : ℝ))) ∧    TypeBlocks.dimension H * TypeBlocks.dimension K ≤      (W.card + 1) ^ ((Fintype.card R + Fintype.card C) * q * (q - 1)) := by  sorryend SpinAngle.TypeAngleendend OAI

Every extracted statement of the accompanying papers

The statements the atlas extracted automatically from each accompanying paper’s TeX source, with links to the full sources.

Optimal-order mixing of the Thorp shuffle

Theorem (Optimal-order mixing)

As d\to\infty,

\|q_d^{*(1600d)}-U_n\|_{\mathrm{TV}}\longrightarrow0.

For every integer t\ge0,

\|q_d^{*t}-U_n\|_{\mathrm{TV}} \ge 1-\frac{2^{tn/2}}{n!}.

Consequently the mixing time at distance 1/4 satisfies

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).

Section 1, Introduction Read it in the paper TeX source, line 53

Show the TeX

As $d\to\infty$,
\[
 \|q_d^{*(1600d)}-U_n\|_{\mathrm{TV}}\longrightarrow0.
\]
For every integer $t\ge0$,
\[
 \|q_d^{*t}-U_n\|_{\mathrm{TV}}
 \ge 1-\frac{2^{tn/2}}{n!}.
\]
Consequently the mixing time at distance $1/4$ satisfies
\[
 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).
\]

From partial permutation information to Fourier bounds

Theorem (Complementary cosets control Fourier matrices)

Partition X into b nonempty sets M_1,\ldots,M_b. Put H_i=H_{M_i}. Suppose f is a nonnegative measure on G of mass at most one and, for every g\in G and i,

f(gH_i)\le \frac{B}{[G:H_i]}.

For every u>0 and every irreducible \rho of degree D,

\|\widehat f(\rho)\|_{\HS}^2 \le bBC_uD^{-1+(u+2)/b}.

There is also an independent orbit-span proof of the bound

\|\widehat f(\rho)\|_{\op}^2 \le bBC_uD^{-1+(u+2)/b}.

No restriction is imposed on block sizes or on the multiplicities in \rho|_{H_1\times\cdots\times H_b}.

Section 1, What partial observations can determine Read it in the paper TeX source, line 18

Show the TeX

Partition $X$ into $b$ nonempty sets $M_1,\ldots,M_b$. Put $H_i=H_{M_i}$. Suppose $f$ is a nonnegative measure on $G$ of mass at most one and, for every $g\in G$ and $i$,
\begin{equation}
 f(gH_i)\le \frac{B}{[G:H_i]}.
\end{equation}
For every $u>0$ and every irreducible $\rho$ of degree $D$,
\begin{equation}
 \|\widehat f(\rho)\|_{\HS}^2
 \le bBC_uD^{-1+(u+2)/b}.
\end{equation}
There is also an independent orbit-span proof of the bound
\begin{equation}
 \|\widehat f(\rho)\|_{\op}^2
 \le bBC_uD^{-1+(u+2)/b}.
\end{equation}
No restriction is imposed on block sizes or on the multiplicities in $\rho|_{H_1\times\cdots\times H_b}$.

Conditional permutations in a revealed switching environment

Theorem (Conditional permutation and full-deck mixing)

Let n=2^d, and start the shuffle from any deterministic deck. After J(s_0+1) sweeps, where s_0=400 and J=40000, the conditional free-slot law defined above satisfies

\sup_{\text{initial layouts}}\E_{\mathcal E} \|\nu_{\mathcal E}-U_{n/2}\|_{\TV}\longrightarrow0 \qquad(d\longrightarrow\infty).

Consequently the full-deck law approaches uniform, uniformly in the starting deck, after 16\,040\,400d physical shuffles. For every integer t\ge0, after t physical shuffles the full-deck distance from uniform is at least 1-2^{tn/2}/n!. Thus the full-deck mixing time is of order d.

Section 1, Introduction Read it in the paper TeX source, line 11

Show the TeX

Let $n=2^d$, and start the shuffle from any deterministic deck.
After $J(s_0+1)$ sweeps, where $s_0=400$ and $J=40000$, the conditional free-slot law defined above satisfies
\[
 \sup_{\text{initial layouts}}\E_{\mathcal E}
       \|\nu_{\mathcal E}-U_{n/2}\|_{\TV}\longrightarrow0
       \qquad(d\longrightarrow\infty).
\]
Consequently the full-deck law approaches uniform, uniformly in the starting deck, after $16\,040\,400d$ physical shuffles. For every integer $t\ge0$, after $t$ physical shuffles the full-deck distance from uniform is at least
$1-2^{tn/2}/n!$. Thus the full-deck mixing time is of order $d$.

Routing densities and representation contraction for Thorp sweeps

Theorem (Routing density and representation contraction)

There are absolute constants \eta,c,C>0 such that, with a=1/1000,

\log\E_{y\sim u_{N,k}}R_x(y)^{1+a} \le Ck(k/N)^\eta \qquad(1\le k\le N),

uniformly over every starting injection x. For every sufficiently large dyadic N and every nontrivial irreducible representation,

T_N(\lambda)=0\quad\hbox{or}\quad \|T_N(\lambda)\|_{\op}\le D_\lambda^{-c}.

Consequently an absolute number of forward sweeps has worst-start total-variation distance from uniform tending to zero as d\to\infty.

Section 1, Introduction Read it in the paper TeX source, line 30

Show the TeX

There are absolute constants $\eta,c,C>0$ such that, with $a=1/1000$,
\[
 \log\E_{y\sim u_{N,k}}R_x(y)^{1+a}
 \le Ck(k/N)^\eta
 \qquad(1\le k\le N),
\]
uniformly over every starting injection $x$. For every sufficiently
large dyadic $N$ and every nontrivial irreducible representation,
\[
 T_N(\lambda)=0\quad\hbox{or}\quad
 \|T_N(\lambda)\|_{\op}\le D_\lambda^{-c}.
\]
Consequently an absolute number of forward sweeps has worst-start
total-variation distance from uniform tending to zero as $d\to\infty$.

Row–column symmetry and contraction of coordinate sweeps

Theorem (Weighted sweep moments)

There are positive weights W_\lambda, an absolute finite p_*, and real exponents 2\le p_d\le p_* such that, for every d\ge1 and every \lambda\vdash2^d,

D_\lambda^{3/4}\le W_\lambda\le D_\lambda, \qquad W_\lambda\|K_d(\lambda)\|_{p_d}^{p_d}\le1.

Consequently \|K_d(\lambda)\|_{\rm op}\le D_\lambda^{-3/(4p_*)}.

Section 1, Introduction Read it in the paper TeX source, line 60

Show the TeX

There are positive weights $W_\lambda$, an absolute finite $p_*$, and real
exponents $2\le p_d\le p_*$ such that, for every $d\ge1$ and every
$\lambda\vdash2^d$,
\begin{equation}
 D_\lambda^{3/4}\le W_\lambda\le D_\lambda,
 \qquad W_\lambda\|K_d(\lambda)\|_{p_d}^{p_d}\le1.
\end{equation}
Consequently $\|K_d(\lambda)\|_{\rm op}\le D_\lambda^{-3/(4p_*)}$.

Corollary (Optimal order of mixing)

There is an absolute constant C such that, for every d\ge1,

\left\lceil\frac2N\log_2\frac{3N!}{4}\right\rceil \le t_{\rm mix}(d)\le Cd, \qquad N=2^d.

In particular t_{\rm mix}(d)=\Theta(d), and its lower bound is 2d-O(1).

Section 1, Introduction Read it in the paper TeX source, line 93

Show the TeX

There is an absolute constant $C$ such that, for every $d\ge1$,
\[
 \left\lceil\frac2N\log_2\frac{3N!}{4}\right\rceil
 \le t_{\rm mix}(d)\le Cd,
 \qquad N=2^d.
\]
In particular $t_{\rm mix}(d)=\Theta(d)$, and its lower bound is
$2d-O(1)$.

Random-subspace tests and trace smoothing for coordinate sweeps

Theorem (Regular-trace smoothing)

There is an absolute P\ge2 such that for every dyadic n\ge2,

\operatorname{Tr}_{\rm reg}|Q_n|^P\le1+n^{-10}.

If v is an integer with 2v\ge P, then v independent sweeps have total-variation distance at most \frac12n^{-5} from uniform, from every deterministic initial deck. Here \|\mu-\nu\|_{\rm TV}=\tfrac12\sum_g|\mu(g)-\nu(g)|.

Section 1, Introduction Read it in the paper TeX source, line 24

Show the TeX

There is an absolute $P\ge2$ such that for every dyadic $n\ge2$,
\begin{equation}
 \operatorname{Tr}_{\rm reg}|Q_n|^P\le1+n^{-10}.
\end{equation}
If $v$ is an integer with $2v\ge P$, then $v$ independent sweeps have total-variation distance at most $\frac12n^{-5}$ from uniform, from every deterministic initial deck. Here $\|\mu-\nu\|_{\rm TV}=\tfrac12\sum_g|\mu(g)-\nu(g)|$.

Compatibility entropy and the spectrum of a Thorp sweep

Theorem (Weighted compatibility)

There are absolute constants L,C_0>0 such that the following holds. Put m=\sqrt n, assume m/2\le A,D\le2m, and take m sufficiently large that \theta=1-L/\log m>0. For all nonnegative functions w_i:S_D\to[0,\infty) and v_k:S_A\to[0,\infty),

\frac{n!}{|R||C|}\, \mathbb E_U\!\left[\mathbf1_{\mathcal I} \prod_{i=1}^A w_i(r_i)\prod_{k=1}^D v_k(c_k)\right] \le e^{C_0n^{.54}} \prod_{i=1}^A(\mathbb E w_i^{1/\theta})^\theta \prod_{k=1}^D(\mathbb E v_k^{1/\theta})^\theta .

The expectations on the right are uniform on the indicated symmetric groups, and logarithms are natural.

Section 1, Introduction Read it in the paper TeX source, line 24

Show the TeX

There are absolute constants $L,C_0>0$ such that the following holds. Put $m=\sqrt n$, assume $m/2\le A,D\le2m$, and take $m$ sufficiently large that $\theta=1-L/\log m>0$. For all nonnegative functions $w_i:S_D\to[0,\infty)$ and $v_k:S_A\to[0,\infty)$,
\begin{equation}
 \frac{n!}{|R||C|}\,
 \mathbb E_U\!\left[\mathbf1_{\mathcal I}
       \prod_{i=1}^A w_i(r_i)\prod_{k=1}^D v_k(c_k)\right]
 \le e^{C_0n^{.54}}
       \prod_{i=1}^A(\mathbb E w_i^{1/\theta})^\theta
       \prod_{k=1}^D(\mathbb E v_k^{1/\theta})^\theta .
\end{equation}
The expectations on the right are uniform on the indicated symmetric groups, and logarithms are natural.

Theorem (A bounded regular moment)

There is an absolute finite p_*>0 such that, for every dyadic n,

Z_n(p_*)\le1+\frac1{16}.

For every integer M\ge p_*, M independent forward sweeps have worst-start total-variation distance at most 1/8 from uniform.

Section 1, Introduction Read it in the paper TeX source, line 45

Show the TeX

There is an absolute finite $p_*>0$ such that, for every dyadic $n$,
\begin{equation}
 Z_n(p_*)\le1+\frac1{16}.
\end{equation}
For every integer $M\ge p_*$, $M$ independent forward sweeps have worst-start total-variation distance at most $1/8$ from uniform.

Corollary (Singular ranks and full-deck mixing)

For every nontrivial \lambda\vdash n and 1\le r\le D_\lambda,

s_r(T_{n,\lambda})\le(16D_\lambda r)^{-1/(2p_*)}.

If s_j(T_n) denotes the full regular singular list, including all multiplicities and zeros, then

s_j(T_n)\le j^{-1/(2p_*)}\qquad(1\le j\le n!).

Section 1, Introduction Read it in the paper TeX source, line 53

Show the TeX

For every nontrivial $\lambda\vdash n$ and $1\le r\le D_\lambda$,
\[
 s_r(T_{n,\lambda})\le(16D_\lambda r)^{-1/(2p_*)}.
\]
If $s_j(T_n)$ denotes the full regular singular list, including all multiplicities and zeros, then
\[
 s_j(T_n)\le j^{-1/(2p_*)}\qquad(1\le j\le n!).
\]
The constant singular value is the first value. The physical Thorp chain has worst-start $1/4$ mixing time $\Theta(d)$; more precisely its lower bound is $2d-O(1)$. For every fixed integer $M>p_*$, the worst-start total-variation distance after $Md$ physical shuffles tends to zero as $d\to\infty$.

Signed tensor densities and diagram budgets for the Thorp shuffle

Theorem (A moment bound for every signed occurrence)

For each sufficiently small fixed \bar\eta>0, choose a sufficiently small \bar\kappa>0 with \bar\kappa<\bar\eta/256. There is an integer r\ge1, depending only on these fixed constants, such that for every d\ge1, every \lambda\vdash n=2^d, and every occurrence (ten:spin:eq:1),

\log\!\left(D_\lambda\operatorname{Tr}_{V_\lambda}(B_n^*B_n)^r\right) \le\eta_d F(\alpha,\beta)+g_n(l),

where

\eta_d=\bar\eta\left(1-\frac1{2\sqrt d}\right),\qquad \kappa_d=\bar\kappa\left(1-\frac1{2\sqrt d}\right),\qquad g_n(l)=\max\{0,\kappa_d l\log n-l\log(n/l)\}.

Set g_n(0)=0 and interpret the logarithm of a zero trace as -\infty.

Section 1, Introduction Read it in the paper TeX source, line 48

Show the TeX

For each sufficiently small fixed $\bar\eta>0$, choose a sufficiently
small $\bar\kappa>0$ with $\bar\kappa<\bar\eta/256$. There is an
integer $r\ge1$, depending only on these fixed constants, such that for
every $d\ge1$, every $\lambda\vdash n=2^d$, and every
occurrence~\eqref{ten:spin:eq:1},
\begin{equation}
 \log\!\left(D_\lambda\operatorname{Tr}_{V_\lambda}(B_n^*B_n)^r\right)
 \le\eta_d F(\alpha,\beta)+g_n(l),
\end{equation}
where
\[
 \eta_d=\bar\eta\left(1-\frac1{2\sqrt d}\right),\qquad
 \kappa_d=\bar\kappa\left(1-\frac1{2\sqrt d}\right),\qquad
 g_n(l)=\max\{0,\kappa_d l\log n-l\log(n/l)\}.
\]
Set $g_n(0)=0$ and interpret the logarithm of a zero trace as $-\infty$.

Corollary (Fixed-sweep convergence of the full deck)

There is an absolute positive integer L such that

\mathbb E_{U_{S_n}}|f_{d,L}-1|^2\longrightarrow0 \qquad(d\longrightarrow\infty).

The convergence is uniform over starting orders. Moreover t_{\mathrm{mix}}(d)=\Theta(d).

Section 1, Introduction Read it in the paper TeX source, line 82

Show the TeX

There is an absolute positive integer $L$ such that
\[
 \mathbb E_{U_{S_n}}|f_{d,L}-1|^2\longrightarrow0
 \qquad(d\longrightarrow\infty).
\]
The convergence is uniform over starting orders. Moreover
$t_{\mathrm{mix}}(d)=\Theta(d)$.

Conditional coordinate sweeps and analytic transfer

Theorem (Binary sweep contraction)

There are absolute constants g>0 and d_0 such that, for d\ge d_0 and every \lambda\vdash 2^d,

\|K_\lambda\|_{\op}\le D_\lambda^{-g}.

The sign representation is annihilated. There is an absolute positive integer w such that the law after w independent sweeps converges to uniform in total variation as d\to\infty, uniformly over deterministic initial decks.

Section 1, Introduction Read it in the paper TeX source, line 54

Show the TeX

There are absolute constants \(g>0\) and \(d_0\) such that, for \(d\ge d_0\)
and every \(\lambda\vdash 2^d\),
\[
 \|K_\lambda\|_{\op}\le D_\lambda^{-g}.
\]
The sign representation is annihilated. There is an absolute positive integer \(w\)
such that the law after \(w\) independent sweeps converges to uniform in
total variation as \(d\to\infty\), uniformly over deterministic initial
decks.

Proposition (Support obstruction)

For every integer t\ge0,

\|q_d^{*t}-U_N\|_{\TV}\ge1-\frac{2^{tN/2}}{N!}.

Consequently,

t_{\rm mix}(d)\ge \left\lceil\frac2N\log_2\!\left(\frac{3N!}{4}\right)\right\rceil =2d-O(1).

Section 1, Introduction Read it in the paper TeX source, line 68

Show the TeX

For every integer \(t\ge0\),
\[
 \|q_d^{*t}-U_N\|_{\TV}\ge1-\frac{2^{tN/2}}{N!}.
\]
Consequently,
\[
 t_{\rm mix}(d)\ge
 \left\lceil\frac2N\log_2\!\left(\frac{3N!}{4}\right)\right\rceil
 =2d-O(1).
\]

A strict four-row permanent inequality and permutation moments

Theorem (A robust four-row inequality)

There are absolute constants p_0\in(4/3,2) and \varepsilon>0 with the following property. Let \nu be a probability measure on S_4 such that

\|\nu-u\|_{\TV}<\varepsilon, \qquad \nu\{\pi:\pi(i)=j\}=\frac14\quad(1\le i,j\le4).

Then every four nonnegative functions on \{1,2,3,4\} satisfy

\E_\nu\prod_{i=1}^4f_i(\pi(i))\le\prod_{i=1}^4\|f_i\|_{p_0}.

Section 1, Introduction Read it in the paper TeX source, line 14

Show the TeX

There are absolute constants $p_0\in(4/3,2)$ and $\varepsilon>0$ with the following property. Let $\nu$ be a probability measure on $S_4$ such that
\[
 \|\nu-u\|_{\TV}<\varepsilon,
 \qquad
 \nu\{\pi:\pi(i)=j\}=\frac14\quad(1\le i,j\le4).
\]
Then every four nonnegative functions on $\{1,2,3,4\}$ satisfy
\begin{equation}
 \E_\nu\prod_{i=1}^4f_i(\pi(i))\le\prod_{i=1}^4\|f_i\|_{p_0}.
\end{equation}

Theorem (A fixed moment with a degree saving)

There exist an even integer r\ge2 and \eta>0, independent of N, such that for every dyadic N and every \lambda\vdash N,

D_\lambda\Tr B_N(\lambda)^r\le D_\lambda^{1-\eta}.

Consequently there is an absolute integer q for which the total-variation distance of q independent forward sweeps from uniform tends to zero as N\to\infty, uniformly over the starting deck.

Section 1, Introduction Read it in the paper TeX source, line 46

Show the TeX

There exist an even integer $r\ge2$ and $\eta>0$, independent of $N$, such that for every dyadic $N$ and every $\lambda\vdash N$,
\begin{equation}
 D_\lambda\Tr B_N(\lambda)^r\le D_\lambda^{1-\eta}.
\end{equation}
Consequently there is an absolute integer $q$ for which the total-variation distance of $q$ independent forward sweeps from uniform tends to zero as $N\to\infty$, uniformly over the starting deck.

Configuration and file facts

File: lean/ComparatorChallenges/SpinAngle.lean
OpenAI’s Lean catalogue: OpenAI’s Lean catalogue does not list this as a main result; the release’s Lean notes for family 238 link it.
Solution module: OAI.RepresentationTheory.SpinAngle.TypeAngle
Allowed axioms: propext, Quot.sound, Classical.choiceThe axioms this configuration allows a proof to use. A replay shows which of them a proof uses.
Imports: Mathlib
Imports from outside Mathlib: None
Local vocabulary: 61 local vocabulary declarations
Lines of Lean, without comments or blank lines: 329
Second proof-verification program (nanoda): Off in OpenAI's configuration.

A shareable summary of this page: the proposed paper match, what the Lean statement expresses, and which reviews are recorded.

Plectis Atlas