The regular-trace statement

Index positions by \(\mathbb F_2^d\). One physical shuffle sends \[(x_1,x_2,\ldots,x_d)\longmapsto (x_2,\ldots,x_d,x_1+\xi_{x_2,\ldots,x_d}),\] with independent fair bits \(\xi\). Removing the deterministic rotations gives a sweep through the coordinate matchings. The rotation returns to the identity after \(d\) steps. Write \(Q_n\) for the law of this sweep and for its average in a representation. A permutation maps inputs to outputs; a product applies its rightmost factor first. Different sweeps use independent coins.

Every matching average is an orthogonal projection, so \(Q_n\) is a contraction. For \(|Y|=(Y^*Y)^{1/2}\), all traces and Schatten norms are unnormalized. The regular trace on the symmetric group is \[\operatorname{Tr}_{\rm reg}|Q_n|^P =\sum_{\lambda\vdash n}D_\lambda \operatorname{Tr}_{V_\lambda}|Q_n(\lambda)|^P,\] where \(V_\lambda\) is the irreducible representation of dimension \(D_\lambda\). The constant representation contributes exactly one.

Since one sweep consists of \(d\) physical shuffles, the theorem gives an \(O(d)\) mixing bound for \(n=2^d\) cards. This order is optimal: the support count in Proposition 7 shows that total-variation distance \(1/4\) requires at least \(2d-O(1)\) physical shuffles.

The regular trace contains all irreducible multiplicities, not just one copy of each Fourier block. The conclusion concerns powers of the forward sweep. Its proof uses Schatten Hölder and does not identify \((Q_n^*Q_n)^v\) with \((Q_n^v)^*Q_n^v\).

Three ranges of representations

The proof separates three ranges, as shown in Figure 1, because the geometric test has a useful, explicit domain. If \(X=\log D_\lambda\), Proposition 4 proves the overlap estimate in a window \[ne^{-A_0\sqrt{\log n}}\le X\le A_1n\] for fixed positive \(A_0,A_1\). In a balanced \(a\) by \(b\) board, take row and column Fourier projections selecting real unit carrier vectors, including every multiplicity copy. If their carrier dimensions are \(D_R,D_F\), we prove \[D_\lambda\operatorname{Tr}(E_RE_F) \le D_RD_F\exp\!\left(\frac{X}{(\log n)^{1/3}}\right).\] The test chooses independent, unitarily invariant complex \(r\)-planes in the even and odd tensor alphabets, where \(r=\lfloor n^{1/100}\rfloor\). The real assumption concerns the selected carrier vectors, and later permits real spectral decompositions of the sweep factors.

Two analytic estimates prepare the other ranges. Corollary 6.2 of the companion Routing densities and representation contraction for Thorp sweeps (OpenAI 2026) shows that a forward sweep followed by a reverse sweep, in either orientation, has a fixed power whose density on every ordered \(l\)-card injection is at most \(e^{Cl}\). This handles very large dimensions. For diagrams with a very long first row, we break the sweep into coarse coordinate lines and deform each local operator by its polar decomposition. The two orientations of smoothing control the two ends of the singular-value decomposition. Exact uniformity for one card is preserved under this deformation. Contact counts and representation multiplicities then make the sparse regular-trace contribution at most \(n^{-12}\) (Proposition 3).

The remaining representations lie in the window of the geometric estimate. Orthogonal row and column tags turn the projection overlap into the norm of an invariant tensor. The random-plane tests retain a controlled fraction of the relevant representation. On passing both tests, nearly all slots lie in a small even subspace. Compression to the distinct cell tags then produces an exponential saving. The argument bounds arbitrary tagged vectors; it does not require them to factor across slots.

The Araki–Lieb–Thirring inequality (Araki 1990; Audenaert 2008) combines the row and column estimates. An exponent increase by \(1+2(\log n)^{-1/4}\) absorbs the geometric error. These increases have bounded product along the halving of bit lengths. The finite-size strict gap provides the base cases.

We use classical branching, Pieri, hook-length and ordinary Schur–Weyl theory (Sagan 2001; Stanley 1999; Vershik and Okounkov 2005). The hook support of the even/odd alphabet is the classical Berele–Regev construction (Berele and Regev 1987), restated in (Regev 2013, Theorem 2.1). We derive the needed even/odd realization by applying ordinary Schur–Weyl separately to the two species and inducing, with a sign twist on the odd factors; the proof also tracks the exceptional letters needed outside the hook. The random-plane averaging is an application of unitary invariance and highest-weight dimension estimates. The compact coherent-orbit resolution used in the final compression is the one described by Perelomov (Perelomov 1972, sec. 2); the tag construction and its quantitative trace estimate are proved here.

A deformation on partial decks

Fix \(p_0\ge4u\) with \(p_0>2\), where \(u\) is from Proposition 2. Work on ordered placements of \(q\) distinguished cards. Partition the \(d\) coordinate updates into consecutive pieces of length about \(\sqrt d\). There are \(g=O(\sqrt{\log n})\) pieces, and the corresponding coarse coordinates have sizes \(b_i\le\exp(C\sqrt{\log n})\). Updating coarse coordinate \(i\) means performing a local cube sweep \(Q_{b_i}\) on every line parallel to it, independently across lines.

A single line operator \(Y\) preserves the identities of the cards in that line and the positions of all other cards. On a block with \(l\) cards in the line, it is the \(l\)-card placement operator for \(Q_{b_i}\). Once line memberships are fixed, parallel lines are tensor factors. These observations allow us to deform the local operators without losing the placement structure.

Write \(Y=W|Y|\) and set \[Y(z)=W|Y|^{p_0z/2},\qquad 0\le\Re z\le1,\] with the value zero on the nullspace. Let \(\mathcal Q(z)\) be the product of these operators in sweep order. At \(z=2/p_0\) we recover the original placement sweep. On \(\Re z=0\), every factor, and hence the product, has operator norm at most one. On \(\Re z=1\), singular-value Cauchy–Schwarz gives, within an \(l\)-card line block, \[ |Y(z)_{yx}|\le \left((|Y|^{p_0/2})_{xx}(|Y^*|^{p_0/2})_{yy}\right)^{1/2} \le\frac{e^{Cl}}{(b_i)_l}. \tag{5}\] The last inequality uses both orientations of Proposition 2: because \(p_0/2\ge2u\) and \(Y\) is a contraction, the displayed positive powers are bounded by the corresponding \(2u\) powers. For \(l=0,1\) the exponential factor is unnecessary. A single card becomes exactly uniform after all bits in a line have been updated; its line operator is therefore the uniform projection, which the deformation leaves unchanged.

Contact counts for the deformed kernel

Compare the deformed product with the kernel \(K(x,y)\) obtained by using an independent uniform permutation on each coarse line. The endpoints \(x,y\) determine all intermediate placements: each card takes its final value in a coarse coordinate exactly when that coordinate is updated. If an intermediate placement has a collision, both kernels vanish. Otherwise the uniform-line transition probability is the product of \(1/(b_i)_l\) over the lines, with \(l\) the number of distinguished cards using that line.

Let \(U(x,y)\) be the sum of \(l\mathbf1_{\{l\ge2\}}\) over these lines, and set it to zero for invalid paths. Thus \(U\) counts card visits to lines shared with another distinguished card. The local estimate and the exact one-card bound imply, on \(\Re z=1\), \[|\mathcal Q(z)_{yx}|\le K(x,y)e^{CU(x,y)}, \qquad K(x,y)\le n^{-q}e^{CU(x,y)}.\] For the second inequality, compare each denominator with \(b_i^l\) and use \(b_i^l/(b_i)_l\le l^l/l!\le e^l\), with ratio one when \(l\le1\). Squaring the first bound and using the second for one factor of \(K\) yields \[\|\mathcal Q(z)\|_{\rm HS}^2 \le\frac{(n)_q}{n^q}\,\mathbb E e^{C'U}.\] Here the expectation uses a uniform input placement and the independent uniform line permutations defining \(K\).

To bound this expectation, condition on all line permutations and follow the paths of all \(n\) inputs. Join two input paths if they use the same line in some piece. The resulting graph has maximum degree at most \[\sum_i(b_i-1)\le e^{C''\sqrt{\log n}}.\] The distinguished paths are a uniform \(q\)-subset of its vertices. If \(R_*\) counts selected vertices having a selected neighbor, then \(U\le gR_*\).

For a degree bound \(\Delta\ge1\), there are at most \(n\Delta^{2(w-1)}\) connected vertex sets of size \(w\): encode one by a rooted spanning-tree traversal of length \(2(w-1)\). Any fixed union of \(v\le q\) vertices is entirely selected with probability \[\frac{(q)_v}{(n)_v}\le(q/n)^v.\] For \(v>q\), that probability is zero. The actual nontrivial components of the selected graph form a disjoint family of connected sets of sizes at least two. Consequently \(e^{C'gR_*}\) is bounded by the sum, over all such contained families, of the products of their weights \(e^{C'g w}\). Apply the preceding containment bound, then drop disjointness and bound the family sum by the exponential of the sum over single sets. For a sufficiently large absolute \(C_2\), if \[(q/n)e^{C_2\sqrt{\log n}}\le\tfrac12,\] this gives \[\mathbb E e^{C'gR_*} \le\exp\!\left(n\sum_{w\ge2} \big((q/n)e^{C_2\sqrt{\log n}}\big)^w\right) \le\exp\!\left((q^2/n)e^{C_3\sqrt{\log n}}\right).\] This argument uses sampling without replacement; it does not require independent contact events.

Interpolate the operator-norm bound on \(\Re z=0\) with this Hilbert–Schmidt bound on \(\Re z=1\). At \(z=2/p_0\) the Schatten exponent is \(p_0\), so \[ \operatorname{Tr}_{q\text{ placements}}|Q_n|^{p_0} \le\exp\!\left((q^2/n)e^{C_3\sqrt{\log n}}\right). \tag{6}\] For completeness, the three-lines argument pairs \(\mathcal Q(z)\) against a dual Schatten unit matrix of exponent \(p_0'=p_0/(p_0-1)\). Keep its singular vectors fixed and raise its singular values to \(p_0'(1-z/2)\), leaving zeros zero. The pairing matrix has trace norm one at the first boundary and Hilbert–Schmidt norm one at the second, and returns to the original dual matrix at \(z=2/p_0\). Raising the interpolated norm bound to \(p_0\) gives (6).

From placements to regular multiplicities

Tagged realization and overlap normalization

Put \(r=\lfloor n^{1/100}\rfloor\). For a partition \(\nu\), let \(s(\nu)\) be the number of boxes below its first \(r\) rows and to the right of its first \(r\) columns. With \(s=s(\lambda)\), we first have \[ s\le C X/\log n. \tag{12}\] To see this, tile the diagram by \(r\) by \(r\) squares. Each tile meeting the counted boxes has a full tile one step up and to the left; these full tiles contain at least \(s\) boxes in total. Their standard tableau counts multiply to a lower bound for \(D_\lambda\): order the tiles by row and then column, and fill partial tiles in any fixed legal way. This respects the Young order. The hook formula gives logarithmic tableau count at least \(r^2(\log r-O(1))\) for each full square, proving (12).

We use Hilbert tensor powers of an alphabet with even and odd letter spaces. An adjacent transposition acts on homogeneous letters by \[u\otimes v\longmapsto(-1)^{p(u)p(v)}v\otimes u,\] where \(p\) is parity. This graded permutation action is unitary. Whenever nonconsecutive slots are grouped together, we use the same graded reordering. In particular it carries actions within those slot sets to tensor-product actions, and carries parity-stable tag subspaces to the corresponding reordered tag subspaces.

An alphabet with \(r\) even and \(r\) odd good letters realizes precisely the shapes contained in the \(r\)-hook. With additional exceptional even letters, a shape \(\nu\) can be realized using exactly \(s(\nu)\) exceptional slots, provided at least \(s(\nu)\) exceptional letters are available; it cannot be realized using fewer exceptional slots. Here a fixed letter content gives an induced representation with trivial factors for even letters and sign factors for odd letters. By Pieri, the good even letters first supply at most \(r\) rows, and the good odd letters add at most \(r\) vertical strips. Each exceptional slot adds at most one box outside the resulting hook. Conversely, build the top \(r\) rows by the even letters, then the remaining hook columns by the odd letters, and finally the outside boxes with distinct exceptional letters. This proves both assertions.

Realize \(\lambda\) with \(s\) exceptional slots and restrict to \(R\). If the chosen \(R\)-type has row shapes \(\mu_1,\ldots,\mu_a\), it occurs in some sector splitting these exceptional slots among the rows. The necessary exceptional count for each row gives \[ h_A:=\sum_i s(\mu_i)\le s. \tag{13}\] The same argument applies to the column shapes.

For row \(i\), take a separate alphabet \(A_i\) with \(r\) good letters of each parity and \(s(\mu_i)\) exceptional even letters, and set \(A=\bigoplus_i A_i\). Embed each row representation in its own alphabet tensor power, with its required exceptional count. The tensor product of these embeddings realizes the whole chosen \(R\)-representation, so it also realizes the possibly entangled vector \(v_R\). Denote its image by \(\psi\). It is a unit vector with exactly \(h_A\) exceptional slots, and the slot in row \(i\) has tag \(A_i\). For \(g\in R\), its matrix coefficient is \[f_R(g)=\langle v_R,g v_R\rangle,\] where \(g\) acts in the chosen row representation. Outside \(R\) the coefficient is zero, because a permutation not preserving the rows changes a tag. Construct a unit column-tagged vector \(\eta\) in \(B^{\otimes n}\), \(B=\bigoplus_j B_j\), in the same way. Its exceptional count is \(h_B\le s\), and its coefficient on \(F\) is \(f_F(g)=\langle v_F,g v_F\rangle\), with \(v_F\) the real unit vector defining \(E_F\). It is zero outside \(F\).

On \(A^{\otimes n}\otimes B^{\otimes n}\), let \(P_*\) be projection onto diagonal invariants and let \(P_A^\lambda,P_B^\lambda\) be the isotypic projections on the respective sides. Put \[e=\psi\otimes\eta,\qquad \phi=\sqrt{n!}\,P_*e.\] Only the identity contributes to the diagonal coefficient average, since \(R\cap F=\{1\}\). Hence \(\|\phi\|=1\). On diagonal invariants the \(A\)-action of \(g\) equals the \(B\)-action of \(g^{-1}\). The character formulas therefore show that the two isotypic projections agree there. Moreover, \[ \|P_A^\lambda\phi\|^2 =\frac{|R||F|}{D_RD_Fn!}\, D_\lambda\operatorname{Tr}_{V_\lambda}(E_RE_F). \tag{14}\] Indeed \(P_*\) commutes with \(P_A^\lambda\), and the two averaging formulas give the left-hand side as \[\frac{D_\lambda}{n!} \sum_{x\in F,\ z\in R} \chi_\lambda(z^{-1}x)f_R(z)f_F(x).\] The group-algebra coefficients of \(E_R\) are \((D_R/|R|)f_R(g)\), and similarly for \(E_F\). The coefficients are real and unchanged by inversion because the selected carrier vectors are real. Taking the trace of the product gives (14).

Retention under random-plane tests

The good even and good odd spaces of \(A\) each have dimension \(H=ar\). Choose an independent unitarily invariant complex \(r\)-plane in each, and let \(V_A\) be their sum. Let \(T_A\) project onto tensors with at most \[L_A=3s+2rH\] slots outside \(V_A\). Every exceptional slot counts as outside. Write \(\overline T_A\) for the average over the two planes.

Use independent planes on the column side, with \(H'=br\), \(L_B=3s+2rH'\), and the corresponding projector \(T_B\). Diagonal averaging preserves the exceptional counts, so \(\phi\) lies in both sectors to which the lemma applies. The two positive operator inequalities tensor together. Since \(P_A^\lambda P_B^\lambda\phi=P_A^\lambda\phi\), they yield \[ \alpha_H\alpha_{H'}\|P_A^\lambda\phi\|^2 \le \mathbb E\|(T_A\otimes T_B)\phi\|^2. \tag{16}\] This is the lower bound for the tested norm. We next obtain its upper bound for every fixed choice of planes.

Compression to orthogonal cell tags

Regroup the two alphabets into \(D^{\otimes n}\), where \(D=A\otimes B\) has parity equal to the sum of the two parities. The identification is unitary and uses graded signs: moving a \(B\)-letter past a later-slot \(A\)-letter contributes a minus sign when both are odd. Checking adjacent transpositions shows that the diagonal action becomes the graded permutation action on \(D\). The parity-preserving slot tests are identified without additional signs.

The slot in cell \((i,j)\) now has tag \(D_{ij}=A_i\otimes B_j\). These \(n\) tag spaces are mutually orthogonal, and \(e\) lies in their product tag subspace. No factorization of \(e\) across the slots is asserted.

Passing both tests leaves at most \(L_A+L_B\) slots outside \(W=V_A\otimes V_B\). The tests preserve diagonal invariants. In an invariant graded tensor, the number of slots in the odd part of \(W\) is at most its dimension: after fixing their positions and grouping them, those factors alternate. Let \(W_0\) be the even part of \(W\), and let \(\Delta_*\) test that at most \[T=L_A+L_B+4r^2\] slots lie outside \(W_0\). We obtain \[ \|(T_A\otimes T_B)\phi\|^2 \le\|\Delta_*\phi\|^2 =n!\|P_*\Delta_*e\|^2. \tag{17}\] The final equality uses the commutation of \(\Delta_*\) with the diagonal action. Also \[\dim W_0\le4r^2,\qquad T\le C X/\log n<n/2\] for large \(n\): the terms in \(T\) not involving \(s\) are \(O(n^{0.52})\), and the lower endpoint of (9) absorbs them.

Covering the representation ranges

A representation of height greater than \(n/2\) is annihilated by one coordinate matching. Indeed, that matching average projects onto invariants of its pair-switching subgroup. By Pieri, induction from \(n/2\) trivial \(S_2\) factors produces only shapes of height at most \(n/2\).

For \(X=\log D_\lambda\ge A_1n\), choose the absolute constant \(A_1\) large enough that Proposition 2 gives \[\operatorname{Tr}_{V_\lambda}|Q_n(\lambda)|^{2u} \le e^{Cn}/D_\lambda\le D_\lambda^{-1/2}.\] A larger fixed power makes the sum of the regular contributions in this range at most \(n^{-12}\). Here we use the bound \(e^{O(\sqrt n)}\) on the number of partitions of \(n\), which also follows by evaluating the partition generating product at \(e^{-1/\sqrt n}\). Proposition 3 supplies the same aggregate bound for long first rows. Since all singular values are at most one, we may choose a common fixed power \(P_c\ge2\) for these two estimates.

Every remaining nontrivial representation satisfies (9), for a fixed \(A_0\) chosen sufficiently large in terms of \(M\). Only the lower endpoint needs proof. Suppose first that the first row or first column has length \(L\ge n/8\). Transpose if necessary, preserving dimension, and retain the first row together with a subdiagram of \[t=\lfloor ne^{-M\sqrt{\log n}}\rfloor\] boxes below it. There are enough boxes: in the row case we have excluded the sparse range of Proposition 3; in the column case the original height is at most \(n/2\), so the transposed tail has at least \(n/2\) boxes. Since \(t=o(L)\), the hook comparison (8), applied to this smaller diagram, gives logarithmic dimension at least \(t\) for large \(n\). Branching bounds this dimension by \(D_\lambda\). If both the first row and first column have length less than \(n/8\), every hook is at most \(n/4\), and the hook formula instead gives \[D_\lambda\ge\frac{n!}{(n/4)^n},\qquad \log D_\lambda\ge cn.\] Both cases imply the required lower endpoint after choosing \(A_0>M\).

Closing the induction

An absolute number of sweeps is \(O(d)\) physical shuffles. The following support obstruction gives the matching lower order.