Positive blocks and stabilizer coefficients

The block trace for \(X Y\) only uses pairs \(Z,Z'\) with both profiles the same between them. In bounding the absolute sum of block contributions for one layout class, we can use \(L_{RC}^2\) times the maximum diagonal-block overlap \(\operatorname{Tr}(X_{ZZ}Y_{ZZ})\) in that class. In fact an off-diagonal block of a positive matrix has the form \(X_{ZZ}^{1/2} U X_{Z'Z'}^{1/2}\) for a contraction \(U\), and likewise for \(Y\); thus \(|\operatorname{Tr}(X_{ZZ'}Y_{Z'Z})|\) is bounded using Hilbert-Schmidt by the geometric mean of the corresponding diagonal-block overlap traces.

For fixed \(Z\), the row stabilizer \(R_Z\) in \(R\) acts separately on its sites outside and inside \(Z\). Write its types as \(\alpha=(\sigma,\tau)\) for the two parts respectively. The diagonal block \(X_{ZZ}\) has the following formula: on the fiber it is \[ \frac{D_\mu}{L_R}\sum_{\alpha}\frac{1}{D_\alpha}\, \mathcal P_{\alpha,M_\alpha}. \tag{13}\] Here \(\mathcal P_{\alpha,M_\alpha}\) denotes a matrix action supported on \(\alpha\) for \(R_Z\), where the \(M_\alpha\) are positive matrices of total trace 1. More explicitly, write \[V_\mu\!\downarrow_{R_Z}=\bigoplus_\alpha V_\alpha\otimes\mathcal M_{\mu,\alpha},\qquad e=\bigoplus_\alpha e_\alpha,\qquad M_\alpha=\operatorname{Tr}_{\mathcal M_{\mu,\alpha}}|e_\alpha\rangle\langle e_\alpha|.\] Then \(M_\alpha\succeq0\) and \(\sum_\alpha\operatorname{Tr}M_\alpha=\sum_\alpha\|e_\alpha\|^2=1\). Keeping just permutations in \(R_Z\) in the matrix coefficient formula for \(P_{\mu,e}\), and using \(|R|=L_R|R_Z|\), gives (13) by orthogonality. The multiplicity spaces have been traced out, not counted. Similarly for \(Y_{ZZ}\) we use column stabilizer types \(\zeta=(\theta,\pi)\) with factor \(D_\nu/L_C\). Only types occurring in the corresponding restrictions and the fiber need be considered.

The positive states in (13) need not be product states on the surviving and deleted carriers. The following elementary estimate is the reason this causes no extra dimension factor.

For these fiber actions, take any pure unit states on the carriers \(V_\sigma\otimes V_\tau\) and \(V_\theta\otimes V_\pi\), denoted by \(w,w'\) as vectors. The corresponding overlap trace on the fiber is of the form \[ \sum_{l,r} |\langle w,(A_l\otimes B_r) w'\rangle|^2. \tag{14}\] Here \(A_l\) range over the products \(I_{\sigma,u}^* I_{\theta,v}\) for the two decompositions of \(V_a\) as in (7), and \(B_r\) analogously use \(V_b\), for types \(\tau,\pi\). This follows by writing the projection directions in every pair of copies in the restricted representations.

On \(Z\) itself, the within-row and within-column groups have trivial intersection. For unit vectors \(x,y\) of the two relevant carriers there, Plancherel gives \[ \sum_r |\langle x,B_r y\rangle|^2 \ \le\ \frac{D_\tau D_\pi}{D_b}\frac{t!}{\prod_i v_i!\prod_j u_j!} \ \le\ \frac{D_\tau D_\pi}{D_b}\exp(E_0+O(t)). \tag{15}\] Indeed the sum is a trace of a product of projections on \(V_b\), hence also the squared Hilbert-Schmidt norm of the product. The squared group-coefficient sum for the product of the two subgroup matrix elements used to give the projections (as group algebra elements) is the product of their squared coefficient sums, since the pairwise products of group elements use unique factorizations from those two subgroups. This gives the first bound using Plancherel in \(G_t\). The log factorial ratio is bounded as stated using \(E_0=t\log t-\sum_i v_i\log v_i-\sum_j u_j\log u_j\) and elementary factorial bounds.

Lemma 5 bounds (14) by the right side of (15) times \(\sum_l\|A_l\|_\infty^2\), for arbitrary, possibly entangled, carrier vectors. We next keep the gain from the minimum in Theorem 4; it is needed when the placement entropy is paid.

Denote \[S=\max\{0,\log(D_\sigma D_\theta/D_a)\}.\] Using (7), (14), and (15), after dividing by \(D_\alpha D_\zeta\) from the diagonal-block formulas, the pure-state bound becomes \[ \frac{1}{D_aD_b} \exp\{E_0-S+O(t+(m+n+1)h^2\log(N+2))\}. \tag{16}\] The matrices within (13) and the column counterpart are handled by positive combinations of the pure states with total weights 1. Thus we can take upper bounds for the possible stabilizer types without a count-factor here. Multiplying by \(D_\mu D_\nu L_{RC}^2/(L_R L_C)\), and using \(D_\lambda\le L_0 D_a D_b\) and (12), bounds the overlap for each layout class using (16), by a bound of the form \[ \frac{D_\mu D_\nu}{D_\lambda} \exp\{2E_0-S+O(t+(m+n+1)h^2\log(N+2))\}, \tag{17}\] taking the largest needed over contributing types.

The budget pays for layout entropy

The restored-cell estimate still contains the cost \(2E_0-S\). We now compare it with the difference between the parent and child diagram weights.

To apply (4), each \(\sigma_i\) for a complement row of size \(n-v_i\) is a subpartition of \(\mu_i\), due to restriction, and likewise \(\theta_j\subseteq\nu_j\) has size \(m-u_j\). Hence, denoting the sums of \(J\)’s by \(J(\mu),J(\nu)\), we have \[J(\mu)+J(\nu)\ \le\ b_0\log(D_\sigma D_\theta)+b_1 t\log N -A\left(\sum_i F_n(v_i)+\sum_j F_m(u_j)\right).\] Together with (6) this gives \[ J(\lambda)-J(\mu)-J(\nu) \ \ge\ -b_0 S + A E_0 -O\big(h^2+(m n^{1-\eta}+n m^{1-\eta})\log(N+2)\big). \tag{18}\] Indeed the cap in the parent \(F_N\) term does not hurt this lower bound, and the amounts dropped from the row contributions to \(H_R\) come only from positive \(v_i\) less than \(n^{1-\eta}\), with a similar bound for \(H_C\).

Indeed, if \(\mathcal E\) denotes the error on the right of (18), then \[2E_0-S-[J(\lambda)-J(\mu)-J(\nu)] \le (2-A)E_0-(1-b_0)S+\mathcal E\le\mathcal E.\] Here \(A\ge2\), \(b_0\le1\), and \(E_0,S\ge0\). Thus the negative dimension term survives the off-diagonal count and is exactly strong enough when the ratio \(D_\mu D_\nu/D_\lambda\) is replaced by \(W_\mu W_\nu/W_\lambda\). All the log errors so far and the log count of possible profile choices, the latter \(O((m+n)\log(N+2))\), are bounded by \(O((\log D_\lambda)/d)\). Indeed \(t\) satisfies (6), \(h\le N^{1/16}\), \(m,n\) are of order \(\sqrt N\), and we have (3) with \(\epsilon<\eta/2\). These estimates are for all sufficiently large \(d\) under (10). This proves (11).

A sparse forest estimate

Write \(k=N-\lambda_1\). For \(k\ge 1\) we have the bound \[ \|K_d(\lambda)\|_\infty \ \le\ (C d)^k (k/N)^{k/8} \tag{21}\] for an absolute \(C\). We prove it using the sweep kernel \(K\) on ordered injective \(k\)-tuples. Consider the subspace of functions \(f\) of the tuples with sum zero over any one component when all the others are fixed. This space is invariant for the position-permutation action. The module on the tuples contains \(V_\lambda\) by branching (invariants upon restriction to \(G_{N-k}\)). Since \(V_\lambda\) does not occur on \((k-1)\)-tuples, the isotypic space for \(\lambda\) on \(k\)-tuples belongs to the indicated zero-sum subspace. The kernel acts using the sweep in this representation or its adjoint convention.

In a transition \(x\mapsto y\) of tuples, a path for each component is specified just by its start and end: the successive coordinates at the end replace those of the start. For two components, let \(l\) be the last differing bit at the start, and \(r\) the first differing bit at the end. Give this pair weight \(w=0\) if \(r>l\), weight 2 if \(r=l\), and weight 1 otherwise. Then \[K(x,y)=N^{-k}\prod_{\text{pairs}}w.\] Indeed, the paths have no conflict (two at the same position at the same stage boundary) exactly when \(r\le l\) for all pairs. When there is no conflict, a switch used by two paths instead of one is used by a pair with \(r=l\), at that bit, giving the factor 2. The same formula works for any subset of components.

Acting on the specified functions \(f\), we can replace the kernel by \[D(x,y)=N^{-k}\sum_{B\subseteq [k]}(-1)^{k-|B|}\prod_{\text{pairs in }B}w,\] because all terms for proper subsets use zero marginal sums. This expression vanishes unless the graph of pairs with \(w\ne 1\) has no isolated vertex. Also, its absolute column sums are at most \(2^k\), since each subset term in absolute value uses the nonnegative sweep kernel on that subset (doubly stochastic), with the other start components summed subject to injectivity.

Use this replacement in \(K^* K\), using row \(z\) of \(K^*\) to sample \(x\). For the set \(S\) of positions occupied in \(x\), we have for every fixed set \(F\) \[ \Pr(S\supset F)\le (k/N)^{|F|}. \tag{22}\] In fact the upper product-of-marginals bounds for inclusions hold at the start of \(K^*\), which uses a reverse scan, from a fixed tuple \(z\). Such bounds are preserved by a random switch: for an inclusion testing just one of the switched sites, average the two bounds, and for one testing both, their product of marginals at these sites can only increase under averaging. At the end, the marginals are \(k/N\), since a single position is exactly uniform after all bit updates. This is the particular negative-dependence property needed here; stronger preservation results for partial symmetrizations are proved in (Borcea et al. 2009, Theorems 4.9 and 4.20).

For a given \(B\), to bound the row sum using the term with weight product on \(B\) and the no-isolated-vertex condition, use true sweep paths for \(B\) and independent paths with uniform ends for the other components (we can disregard the final injectivity restriction for upper bounding the probability). If \(w\ne 1\), the two specified paths go through the same switch at a stage. We may pre-sample, independently of \(S\), two options at every starting position: a path using a common sweep permutation with its specified routing, and a path from independent uniform bits (independent paths for this option at different positions). Thus we only need upper bound the probability of a no-isolated-vertex interaction graph on \(S\) using some assignment of these types.

Such a graph contains a spanning forest with \(c\le k/2\) rooted trees of size at least 2, which we may take as ordered trees arranged in order of their root positions. The number of forest shapes needed for each \(c\) is at most \(C_0^k\), for an absolute \(C_0\) (e.g. by the traversal encoding of plane forests). Choose distinct roots in at most \(\binom Nc\) ways and path types in at most \(2^k\) ways. For these choices the expected number of embeddings with distinct positions and meetings along the tree edges is at most \((2d)^{k-c}\). To see this, condition on the full common routing and enumerate children after their parents, exposing independent paths as needed. For a child of common routing type, at each possible meeting stage there are at most two starting positions since the full routing sends exactly two paths through the switch. For a child of independent type, summed over fresh positions the expected number meeting a given parent at stage \(i\) is at most \(2^i 2^{-(i-1)}\): the suffix after \(i\) at the start must agree with the parent path there, and the new prefix of length \(i-1\) must agree. These estimates apply to the sums of extension probabilities conditional on the paths for a partial embedding, by independence for unused positions of the independent type. Each embedding uses \(k\) sites, so we may multiply the expected counts by \((k/N)^k\) by (22). Summing over \(B\), shapes and embeddings gives, for the signed kernel \(K^*D\), an absolute row sum bounded by \[(C_1 d)^k (k/N)^{k/2},\] using \(\binom Nc\le (C_2 N/k)^{k/2}\) for \(c\le k/2\). An empty set of such forests gives zero probability. The column sum bound for \(D\) still works for \(K^*D\). The row-column sum bound on the \(\ell^2\) operator norm now bounds \(K^*K\) on the specified subspace, proving (21).

The bounded-exponent induction

Full-deck mixing

In particular for nontrivial \(\lambda\) with length at most \(N/2\) we have \[\|K_d(\lambda)\|_\infty\le D_\lambda^{-(1-b_0)/p_*}.\] For an absolute sufficiently large number \(j\) of sweeps, by Plancherel and Cauchy–Schwarz (Diaconis and Shahshahani 1981, sec. 2 and 3), the squared total variation distance to uniform of their product law is at most \[\frac14\sum_{\lambda\ne(N)} D_\lambda \|K_d(\lambda)^j\|_2^2 \ \le\ \frac14\sum_{\substack{\lambda\ne(N)\\ \lambda^{\rm tr}_1\le N/2}} D_\lambda^{-2},\] where we took \(j\) large enough for the last exponent, using the operator norm to bound the Hilbert-Schmidt norm. The sum bound tends to zero. Indeed for \(k>N^{1-\epsilon}\) this follows from (3) and the partition count, and for \(1\le k\le N^{1-\epsilon}\), \(D_\lambda\ge e^{-1}(N/k)^k\) for large \(N\). The latter follows by the top-row hook estimate in the proof of Lemma 3, now with \(k\) boxes outside the row. There are at most \(2^k\) partitions of the tail of size \(k\). Since the permutation product law determines the deck from any fixed starting deck, the bound is a worst-case bound. Thus a fixed number \(j\) of sweeps gives total variation distance at most \(1/4\) for all sufficiently large \(d\). For each of the finitely many remaining \(d\), the strict nontrivial Fourier norm gap established above gives convergence under repeated forward sweeps. Increasing \(j\) to cover these sizes yields one absolute sweep count for every \(d\ge1\); further convolution cannot increase total variation distance. As a sweep consists of \(d\) physical shuffles, this proves the upper bound in Corollary 2.

Two transverse product estimates

Write \(n=2^d\) in this section, and write \(\mu_d=K_d\) for the sweep. The two product estimates below measure different features of the same representation: its first-row deficit, and its size outside a small hook. Neither alone supplies the error needed at every shape. Their combination gives the following unweighted conclusion. Here \(f^\lambda=D_\lambda\), and subscripts denote Fourier matrices.

We use the branching rule (Sagan 2001, Theorem 2.8.3), Pieri’s rule (Stanley 1999, Theorem 7.15.7), and the Littlewood–Richardson rule (James 1978, Theorem 16.4), together with the hook-length formula (Sagan 2001, Theorem 3.10.2). Ordinary Schur–Weyl duality (Etingof et al. 2011, Theorem 4.57 and Corollary 4.59) supplies the tensor realizations. Recall the following consequences and conventions:

• The space of functions on injections of \(j\) distinct indices into \(h\) positions carries the representation induced from the trivial representation of \(\mathfrak S_{h-j}\). It contains only shapes with first row at least \(h-j\). For \(\lambda_1=h-j\), the multiplicity is \(f^{\lambda_*}\), where \(\lambda_*\) is the shape after the first row. In this case \[ e^{-j}\binom hj f^{\lambda_*}\ \le\ f^\lambda\ \le\ \binom hj f^{\lambda_*}. \tag{24}\] Indeed the hook correction to the first-row factorial has log at most \(j\).

• For polynomial irreducibles of the unitary group in \(s\) dimensions, indexed by partitions \(u\) of degree \(\le n\) with at most \(s\) rows, we use dimension \(\le (n+s+1)^{O(s^2)}\) and the highest weight \(u\). Thus a positive semidefinite matrix with ordered eigenvalues \(x_i\) decreasing acts (by polynomial extension) with operator norm \(\prod_i x_i^{u_i}\), which is also a lower bound for the trace of that action. The Schur character and dimension formulas are given in Etingof et al. (2011, Theorem 4.63); the largest monomial follows from the tableau description and the highest weight.

• All group algebra blocks can be prescribed separately. Projections selecting a subspace in one irreducible block and zero elsewhere are orthogonal projections in every unitary representation. For a transitive permutation representation (uniform probability normalization on the orbit), the squared norm of evaluation at a point on the subspace selected by such a projection \(B\) in type \(\alpha\) is \[f^\alpha \operatorname{Tr}(B Q_\alpha),\] where \(Q\) is the average on the stabilizer of the point. This follows by matrix-entry orthogonality or the regular representation formula, realizing functions on cosets inside the regular representation.

Constants and big-O in estimates below are absolute, and logs in estimates can be taken natural. We give some matrix product estimates for the induction. Split the bits of a large sweep into two consecutive groups of nearly equal sizes. This gives a board of \(b\) rows and \(m\) columns, \(bm=n\), both within a constant factor of \(\sqrt n\). The two parts of the sweep operate along the rows and along the columns, respectively; write \[H=\mathfrak S_m^b,\qquad K=\mathfrak S_b^m\] for the corresponding groups (the estimates work in either product order). The logarithms of the numbers of types (irreducibles) for \(H,K\) are \(O(n^{3/4}\log n)\), by standard partition bounds, or simply by splitting each partition diagram according to a square of side about the square root of its size. We denote the dimension of a subgroup type by \(h_A\) when the type is \(A\).

Here are the two estimates. Suppose \(X\in\mathbb C H,\ Y\in\mathbb C K\) satisfy \[ h_A\|X_A\|_v^v\le 1,\qquad h_B\|Y_B\|_v^v\le 1 \tag{25}\] on all their types. Put \(j=n-\lambda_1\), \(j>0\).

• With \(v=8\), we have \[ f^\lambda\|(XY)_\lambda\|_8^8 \ \le\ \exp\{O(j+n^{0.8})\}. \tag{26}\]

• Put \(s=\lfloor n^{0.01}\rfloor\), and let \(k\) be the number of boxes of \(\lambda\) outside its first \(s\) rows and first \(s\) columns (outside their union). With \(v=2\), we have \[ f^\lambda\|(XY)_\lambda\|_2^2 \ \le\ \binom nk \exp\{O(k+n^{0.8})\}. \tag{27}\] Bounds with adjoints or reversed order follow the same way. We prove the estimates in detail.

A deletion frame for injection spaces

The selected-rank estimate will resolve a row-type vector into functions that remember only a prescribed number of marked positions in each row. The following lemma gives a bounded resolution before any row-column comparison is made.

Projection overlap on marked indices

We now use the deletion frame on each row and column. The selected ranks below count directions inside subgroup carriers; each ambient projection includes every multiplicity copy.

To get (26), split (25) at \(v=8\) into types and dyadic singular value bands on each side. For a term with values \(\le w_R,w_C\) (upper endpoints of the bands), use the selected projections on the inner sides of the two maps and (30), multiplying the norm bound by \(w_R w_C\). Within a type, \(\sum w_R(h_R r_R)^{1/8}=O(\log(n!)+1)\) since each term is bounded by (25), and an extreme small-value tail is geometric using \(r_R\le h_R\le n!\); likewise for columns. Summing including type counts proves (26).

The signed-tensor estimate

The selected-rank estimate costs an exponential in the first-row deficit. We now obtain a different cost, depending on boxes outside a small hook. This is a separate signed-tensor argument; it will complement the first estimate when the deficit is large.

Separate the diagram of \(\lambda\) into its first \(s\) rows (shape \(\alpha\)), then the first \(s\) columns of the remaining diagram (transpose shape \(\beta\), i.e., \(\beta\) lists their lengths), then the remaining shape \(\gamma\) of size \(k\). Let \(N'=n-k\) and write \(H_0\) for the entropy in natural log units of the list \((\alpha,\beta)/N'\) (entries are parts). By interleaving tableaux respecting just the indicated rows and columns and the subtableau on \(\gamma\), \[ f^\lambda\ \le\ f^\gamma \binom nk \exp(N'H_0). \tag{36}\]

Use a mixed tensor space over placements of \(k\) distinct special labels on the board. On the other sites use \(W=\mathbb C^s\oplus\mathbb C^s\), even and odd respectively. Permuting sites uses the usual signed tensor permutation (a minus for interchanging two odd factors); special labels count as even. Explicitly one takes a direct sum of the remaining tensor spaces indexed by the placements and permutes symbols with the sign of the reordering on the odd symbols. This is a representation of \(\mathfrak S_n\). Block diagonal simultaneous unitaries in \(\mathcal G=U(s)\times U(s)\) commute with it. Use the projection \(P\) to \(\mathcal G\)-type \((\alpha,\beta)\). This space contains \(\lambda\) with multiplicity at least \(f^\gamma\). Indeed by ordinary Schur–Weyl applied on each species of tensor factors we have induction of \(\alpha\), the conjugate \(\beta^\intercal\) (because of the sign), and the regular representation for the \(k\) labels. The triple Littlewood–Richardson coefficient with \(\gamma\) is positive: combine \(\beta^\intercal,\gamma\) by row sums, then with \(\alpha\) by column sums (the highest weight sum rule and its conjugate). This yields \(\lambda\).

Write \(Q_H=X^*X,\ Q_K=YY^*\). To bound the trace for the product on \(P\) we use \[\operatorname{Tr}(Q_H P Q_K P).\] Since \(P\) preserves placements, only diagonal placement blocks of \(Q_H,Q_K\) occur: in returning each special label one factor preserves its row and the other its column. For any placement the diagonal block \(R_H\) is given by the restriction of the group-algebra coefficients of \(Q_H\) to the subgroup fixing the special positions pointwise. This restriction is positive there (compression in the regular representation). If \(a_i\) special positions occur in row \(i\), its norm on a tuple of types \(\delta_i\vdash m-a_i\) is bounded by \[ \frac{\exp(O(n^{0.8}))}{\prod_i (m)_{a_i}\, f^{\delta_i}} . \tag{37}\] Indeed by (25) with \(v=2\) the full-group identity coefficient times \(|H|\) is at most the type count. On the subgroup the same coefficient times subgroup order bounds dimension times trace on each block. There is an analogous \(R_K\).

We explain a positive-operator majorization for \(R_H\), on this placement. Up to a factor \(\exp(O(n^{0.8}))/\prod_i(m)_{a_i}\), it is majorized by an average of \[ \bigotimes_{\text{remaining sites }(i,j')} \tau_i , \tag{38}\] where the \(\tau_i\) are block diagonal positive matrices on \(W\) of trace one. To verify it use separate block-diagonal unitary types on each row. For \(M=m-a_i\) remaining sites of one row, a type \((u,v')\) with total degree \(M\) corresponds under \(\mathfrak S_M\) to constituents of induction from \(u\) and \((v')^\intercal\), with \(u,v'\) each of length at most \(s\). This again follows by using ordinary Schur–Weyl on the separate species. Signed reorderings used to group factors together do not affect the argument and respect products of even operators. Every such \(\mathfrak S_M\) constituent \(\delta\) satisfies \[u_i\le\delta_i\le u_i+s,\qquad v'_i\le\delta^\intercal_i\le v'_i+s,\] with zero padding. For example \((v')^\intercal\) can be obtained by successive induction of at most \(s\) single columns, so Pieri gives the first bound, and the conjugate gives the other. Its hook-length product off the top left \(s\times s\) box is bounded using the horizontal pieces of lengths at most \(u_i\) with hook extensions down by at most \(s\), and the vertical pieces for \(v'_i\) similarly. Thus \[ f^\delta\ \ge\ \exp\{-O(s^2\log(n+1))\}\ \exp\{M H((u,v')/M)\}, \tag{39}\] by the hook formula and factorial estimates; here \(H(\cdot)\) in an entropy expression denotes Shannon entropy. For instance the hook product is at most \((n+s+1)^{O(s^2)}\prod_i u_i!\,v'_i!\). Empty rows of sites give trivial estimates.

On the other hand take a trace-one matrix of spectrum \((u,v')/M\) in the two blocks and conjugate by Haar block-diagonal unitaries. The expected tensor power of order \(M\) on this type is scalar and at least \(\exp\{-M H((u,v')/M)-O(s^2\log(n+1))\}\), by the highest weight and dimension bounds. One can average also over type choices at logarithmic cost \(O(s^2\log(n+1))\). Applying this independently in each row gives (38) from (37), (39): the accumulated costs fit in \(O(n^{0.8})\) since \(b,m=O(\sqrt n)\). We likewise use a column average of products of \(\sigma_{j'}\).

Density normalization on the remaining cells

For these majorizing averages, by positivity it suffices to bound uniformly \[ \left\| (\bigotimes \tau_i^{1/2})\ P\ (\bigotimes \sigma_{j'}^{1/2}) \right\|_2^2 \tag{40}\] on the remaining sites of the placement. Use the uniform average over all \(b\) rows, \[D_0=\frac1b\sum_{i=1}^b\tau_i+\varepsilon I,\qquad\varepsilon>0.\] This averages the full board, including the row states at deleted positions. Insert \((D_0^{-1/2})^{\otimes N'}\) before \((D_0^{1/2})^{\otimes N'} P\) in the middle. The latter operator can be expanded as an integral of the simultaneous \(\mathcal G\) actions, with total absolute coefficient bounded by \[(n+s+1)^{O(s^2)} \left((\operatorname{Tr}D_0)^{N'} e^{-N'H_0}\right)^{1/2}.\] Indeed this is Fourier expansion on one isotypic type by unitary matrix orthogonality (the extension to \(D_0^{1/2}\) acts there by the same representation with its multiplicity); its operator norm uses the ordered eigenvalues on the two blocks to powers given by the two partitions, bounded by the displayed entropy factor using their sum \(\operatorname{Tr}D_0\). For a simultaneous block unitary \(U\), the remaining tensor product in (40) after this insertion and expansion has squared Hilbert–Schmidt norm \[\prod_{\text{remaining }(i,j')} \operatorname{Tr}(D_0^{-1/2}\tau_i D_0^{-1/2} U \sigma_{j'} U^*) .\] Denote these nonnegative entries by \(W_{ij'}\) and put \(\bar\sigma=m^{-1}\sum_{j'}\sigma_{j'}\). Their full-board average satisfies \[\frac1n\sum_{i,j'}W_{ij'} =\operatorname{Tr}\!\left[ D_0^{-1/2}(D_0-\varepsilon I)D_0^{-1/2} U\bar\sigma U^*\right]\le1.\] The sum over surviving cells is therefore at most \(n\). Arithmetic–geometric mean on those \(N'\) cells gives \[\prod_{\text{remaining }(i,j')}W_{ij'} \le(n/N')^{N'}\le e^k.\] Sending \(\varepsilon\) to zero makes \(\operatorname{Tr}D_0\to1\) and bounds (40) by \(\exp\{-N'H_0+O(k+n^{0.8})\}\).

It remains to sum the diagonal placement blocks. If \(a_i\) and \(a'_{j'}\) are their row and column loads, then \[\prod_i(m)_{a_i}\prod_{j'}(b)_{a'_{j'}} \ge(m/e)^k(b/e)^k=e^{-2k}n^k.\] There are \((n)_k\le n^k\) ordered placements. Thus their number cancels the factor \(n^{-k}\) supplied by the two majorizations, at cost \(e^{O(k)}\). Combining (38), (40) and the column estimate, we conclude that \[f^\gamma\|(XY)_\lambda\|_2^2 \le \exp\{-N'H_0+O(k+n^{0.8})\}.\] This proves (27) by (36).

The sparse estimate in short time windows

The two static estimates will close the recursion away from the first row. To finish the argument, we need the following direct estimate for the actual sweep. We retain its time-window proof because it uses a different cancellation from the weighted forest argument.

We record a direct bound, for all sufficiently large \(d\): \[ \|(\mu_d)_\lambda\|_\infty\ \le\ n^{-c j} \quad\text{if }1\le j=n-\lambda_1\le n^{0.9}, \tag{41}\] where \(c>0\) is absolute. Work on \(j\)-point injections \(x,y\) again, with the cube coordinates now and the iid normalization (functions are extended by zero). Any card traveling from \(x_i\) to \(y_i\) in a sweep must use a unique path of sites. For any subset \(I\) of the cards let \(K_I(x,y)\) denote the density on their \(y\) positions relative to uniform independent sampling, given their \(x\) positions. On injections this is a product of pair factors within \(I\): the factor is 1 for non-encounter, and for paths coming to the same switch from opposite sides it is 2 if they split, 0 if they conflict. Such potential encounters for a pair can only start at the step updating their last differing input coordinate. Indeed the unupdated suffixes are fixed. If paths are invalid there is a first failure leading to a zero factor, and on valid paths the formula counts the required fair coins.

In pairing functions of type \(\lambda\) only the part \[\sum_{I\subseteq[j]} (-1)^{j-|I|} K_I\] is needed for the full density \(K_{[j]}\), by the top-degree property. This expression vanishes unless every vertex is covered by potential encounters (the paths are determined for all vertices, regardless of validity). We bound the operator norm of each nonnegative \(K_I\) restricted to that event and to injections.

Divide the times into a bounded number of windows updating coordinates \(a+1,\ldots,g\), with \(g-a\le d/32\). For large \(d\) these windows can cover the whole scan. A contact in this window requires the two paths to have the same suffix of \(x\) after coordinate \(g\) and the same prefix of \(y\) through coordinate \(a\). Call each such suffix-prefix pair a window cell. Coverage of all vertices by contacts therefore implies that, in some window, at least \(c_0j\) vertices lie in nonsingleton window cells, for an absolute \(c_0>0\).

At least one of \(a,d-g\) is at least \(0.4d\). We first treat \(a\ge0.4d\). Group the input points by their suffix after \(g\), and call a group dense when its count is at least \[T=2^a n^{-1/64}.\] Split the window event into two parts. Let \(\mathcal E_{\rm dense}\) be the event that dense suffix groups contain at least \(c_0j/2\) vertices. Let \(\mathcal E_{\rm light}\) be window coverage with fewer than that many vertices in dense groups. We will prove, for the mixed sampling associated with each \(K_I\), \[ \sup_y\Pr_{\rm reverse}(\mathcal E_{\rm dense}\mid y) \le e^{Cj}n^{-c_1j},\qquad \sup_x\Pr_{\rm forward}(\mathcal E_{\rm light}\mid x) \le e^{Cj}n^{-c_1j}. \tag{42}\] These are respectively a column-sum and a row-sum bound for the two positive restricted kernels.

Given \(x\), mixed sampling uses genuine sweep paths for \(I\) and independent uniform destination bits for the other indices. Reverse sampling is defined in the same way given \(y\). Discarding noninjective outputs only decreases the kernel mass. For counts \(Z_\nu\) in disjoint site groups at an intermediate or final time, both unrestricted mixed laws satisfy \[ \mathbb E\prod_\nu(Z_\nu)_{r_\nu} \le\prod_\nu(\mathbb E Z_\nu)^{r_\nu}. \tag{43}\] For the genuine sweep subset, inclusion of any specified distinct sites has probability at most the product of the one-site probabilities. This holds initially and is preserved by random switches: a test set containing one endpoint uses the average of the two old bounds, while a test set containing both uses that their old marginal product is at most the square of their averaged marginal. Summing the site inequalities gives (43). Independent extra paths have the same factorial bounds, and independent addition preserves them by the falling-factorial binomial formula.

In reverse sampling from fixed \(y\), every suffix group of \(x\) has mean \(j/2^{d-g}\). The deficit assumption and the window length give \[\frac{j/2^{d-g}}{T} =\frac{j}{n}\,2^{g-a}n^{1/64} \le n^{0.9-1+1/32+1/64}=n^{-17/320}.\] There are at most \(j/T\) dense groups. Their possible choices cost at most \(\exp(O(j\log n/T))\); if \(j<T\), the event is impossible. Since \(T\ge n^{0.4-1/64}\), this cost is absorbed by \(e^{O(j)}\). The union of any fixed choice of at most \(j/T\) groups has mean at most \(j n^{-17/320}\). Applying (43) to a factorial moment of order \(\lceil c_0j/2\rceil\) proves the first bound in (42).

For forward sampling from fixed \(x\), each window cell in a nondense suffix group has mean \(\mu_\nu\le T/2^a=n^{-1/64}\) at time \(a\). On \(\mathcal E_{\rm light}\) at least \(c_0j/2\) vertices lie in nonsingleton cells of this kind. A cell with \(r\ge2\) vertices supplies \(\lfloor r/2\rfloor\ge r/3\) disjoint pairs, so there are at least \(c_2j\) disjoint co-located pairs, with an absolute \(c_2>0\). Since \[\sum_\nu\mu_\nu^2\le n^{-1/64}\sum_\nu\mu_\nu\le j n^{-1/64},\] (43) bounds the expected number of sets of \(u=\lceil c_2j\rceil\) such pairs by \[\frac{(\sum_\nu\mu_\nu^2)^u}{2^u u!} \le e^{O(j)}n^{-u/64}.\] Reducing \(c_2\) if necessary handles integer rounding and proves the second bound in (42).

If instead \(d-g\ge0.4d\), transpose the kernel by exchanging \(x,y\) and reverse the coordinate names. The window then has endpoints \(a'=d-g\), \(g'=d-a\), so the preceding argument applies with \(a'\ge0.4d\). This exchanges the row and column bounds and leaves the operator norm unchanged.

Each restricted positive kernel thus has one sum bounded by \(e^{O(j)}n^{-c_1j}\) and the other by one. The Schur bound gives its operator norm at most \(e^{O(j)}n^{-c_1j/2}\). Summing over the bounded number of windows and the \(2^j\) subsets \(I\) proves (41), with a smaller absolute \(c\). For \(j=1\) the cancelled kernel is zero because there can be no contact.

A uniform Schatten exponent

We supply details on uniformity of the Schatten exponent. At any fixed range of sizes a sufficiently large exponent in (23) suffices. In fact the sweep matrix is a product of orthogonal projections (matching subgroup averages), with norm strictly below one on every nontrivial irreducible: equality would require a joint invariant vector, and all the edges together generate the symmetric group.

Split a large \(d\) into \(\lfloor d/2\rfloor,\lceil d/2\rceil\) bits. Each part of the board update is a product of independent smaller sweeps. If (23) holds in the smaller problems with exponent \(\le p'\), taking \(p'\ge8\), their independent products on the factor groups have \[h_A\|X_A\|_{p'}^{p'}\le1,\qquad h_B\|Y_B\|_{p'}^{p'}\le1,\] by tensoring (norms are contractions). Either product estimate (26), (27) with right hand log \(\mathcal E\) then gives \[ f^\lambda\|(XY)_\lambda\|_{p'}^{p'} \le \exp(\mathcal E). \tag{44}\] For clarity this transference uses ordinary Schatten norm complex interpolation: take analytic families in the two group algebras replacing singular values \(x\) by \(x^{z p'/v}\) (zeros held zero), preserving singular vectors. At real part 1 use (26) or (27) with its given exponent \(v\), and at real part 0 use product operator norm at most 1. Interpolation at \(v/p'\) gives (44), by the three-lines Schatten inequality between operator norm and \(v\)-norm. Thus the log costs do not grow with the starting exponent.

It remains to make one of the two logarithmic costs small relative to \(F=\log f^\lambda\). Types of length greater than \(n/2\) are annihilated by one matching layer, as noted in Section 2. For the remaining nontrivial types, Lemma 3 gives \(F\ge c_6j\). We now assume \(j\ge n^{0.9}\), leaving the sparse range to (41).

With \(k,s\) as in (27), the hook formula on the lower diagram of size \(j\), followed by (24), gives \[ F\ge\log\binom nj+k\log(s/2)-O(j). \tag{45}\] Indeed all hooks of the lower diagram are at most \(j\), while the indicated \(k\) interior boxes have hooks at most \(2j/s\) by their row and column indices there. Comparing their product with \(j!\) gives a lower dimension bound \(e^{-O(j)}(s/2)^k\).

If \(F\ge j d^{1/4}\), choose the selected-rank product estimate (26). Its logarithmic cost is \[O(j+n^{0.8})\le O(d^{-1/4}F),\] since \(j\ge n^{0.9}\).

If \(F<j d^{1/4}\), use (45) and \(F\ge c_6j\) to obtain \[\log(n/j)=O(d^{1/4}),\qquad k=O(F/d).\] When \(k\ge j/d^2\), we have \(\log(n/k)\le\log(n/j)+2\log d=O(d^{1/4}+\log d)\), and hence \(k\log(n/k)+k=O(Fd^{-3/4})\). When \(0<k<j/d^2\), the crude bound \(\log(n/k)\le\log n=O(d)\) gives \(k\log(n/k)+k=O(j/d)=O(F/d)\). At \(k=0\) these terms vanish. The signed-tensor estimate (27) therefore has logarithmic cost at most \(O(d^{-1/4}F)\) as well; its \(n^{0.8}\) term is absorbed using \(F\ge c_6n^{0.9}\).

For large enough \(d\), the cost in (44) is consequently at most \(\varepsilon_d F\) with \(\varepsilon_d=O(d^{-c})\le1/2\), uniformly in these shapes. This also bounds the operator norm to the \(p'\) power by \(\exp(-(1-\varepsilon_d)F)\), so increasing \(p'\) by a factor \(1+O(d^{-c})\) restores (23). For \(1\le j\le n^{0.9}\), (41) and \(f^\lambda\le n^j\) give, at any sufficiently large absolute exponent \(p\), \[f^\lambda\|(\mu_d)_\lambda\|_p^p \le(f^\lambda)^2\|(\mu_d)_\lambda\|_\infty^p \le n^{(2-cp)j}\le1.\] The trivial representation satisfies (23) exactly.

Thus starting with a large enough finite base exponent covering fixed small \(d\) and the direct-bound requirement, it is enough at each large \(d\) to multiply the maximum of the two required smaller exponents by \(1+O(d^{-c})\). These factors have bounded product along bit-length halvings. This proves (23) with a uniform exponent.

Full-deck amplification

Equation (23) gives \(\|(\mu_d)_\lambda\|_\infty\le(f^\lambda)^{-1/p}\). The Plancherel and dimension-sum argument of Section 6.3 therefore applies to repeated forward sweeps, giving worst-start mixing after an absolute number of sweeps, or \(O(d)\) physical shuffles. Proposition 6 supplies the matching lower order. This completes the frame route to the common mixing conclusion.

Two sparse estimates

For a nontrivial \(\lambda=(n-k,\beta)\) with \(k=n-\lambda_1\ge1\), the two inputs are \[\begin{align*} \|B_n|_{V_\lambda}\|^2 &\le C^k(1+d)^{Ck}(k/n)^{k/2}, \tag{47}\\ \|B_n|_{V_\lambda}\|^2 &\le e^{Ck}D_\beta^{-a} \tag{48}\end{align*}\] for absolute \(a>0\). For the first estimate we use the square of the fully cancelled kernel. Work with counting-measure matrices on ordered injective \(k\)-tuples. For \(A\subseteq[k]\), let \(K_A^{\rm prob}\) be the sweep transition kernel on the coordinates in \(A\), and set \[L_A(x,y)=n^{-(k-|A|)}K_A^{\rm prob}(x_A,y_A),\qquad D(x,y)=\sum_{A\subseteq[k]}(-1)^{k-|A|}L_A(x,y).\] Both arguments of \(L_A\) are restricted to injective full tuples. Its row and column sums are at most one: the coordinates in \(A\) follow a genuine sweep and the others are sampled independently uniformly, after which noninjective outcomes are discarded. Consider the subspace of functions whose sum over any one tuple coordinate is zero when the other coordinates are fixed. All proper-coordinate marginals vanish on this subspace, so \(D\) acts exactly as the full sweep kernel \(K=L_{[k]}\). The type \(\lambda=(n-k,\beta)\) belongs to it by the branching argument in Section 6.1.

The product-of-pair-factors formula for the sweep shows that \(D(x,y)=0\) if one of the \(k\) unique start-to-end paths has no potential switch contact with another path. Write \(\mathcal E(x,y)\) for the event that this contact graph has no isolated vertex. By discarding this condition on the first leg only, \[|(D^*D)(x,y)| \le\sum_{A,B\subseteq[k]}\ \sum_{z\text{ injective}} L_A(z,x)L_B(z,y)\mathbf1_{\mathcal E(z,y)}.\] For fixed \(x,A\), the first-leg mass in \(z\) is bounded by the law obtained from a reverse sweep of the labels in \(A\) and independent uniform positions for the others. Under this unrestricted mixed law, the occupied set \(S\) satisfies \[\Pr(F\subseteq S)\le(k/n)^{|F|}\] for every fixed site set \(F\). For the sweep subset this follows from the negative-inclusion argument in (22). Adding the independent uniform positions preserves the bound: partition the tested sites between the two sources and sum the resulting product bounds. Restriction to injective \(z\) only decreases these probabilities; it is retained in the kernel sum, so the relevant \(S\) always has exactly \(k\) sites.

Independently presample a complete common routing for the second leg and one private uniform path from each site. Any assignment of the labels in \(B\) to common paths and the other labels to private paths is covered by the \(2^k\) choices of path type on a \(k\)-site set. Thus no factor \(k!\) is needed. The expected number of such typed unordered sets with no isolated contact is at most \[ \sum_{1\le j\le k/2}C^k\binom nj(Cd)^{k-j}. \tag{49}\] Indeed choose roots, ordered forest shapes and path types. Every nontrivial component has a rooted spanning tree. A new common-path child has at most two possible starts per switch; summing over private-path starts gives at most two expected choices per switch. Expose independent paths only at unused sites and sum successively over the tree extensions. This bounds each extension by \(4d\) and proves the display, with the number of forest shapes absorbed into \(C^k\).

Multiply the expected count by \((k/n)^k\), using the first-leg inclusion bound independently of the second-leg fields, and sum the at most \(4^k\) choices of \(A,B\). The elementary bound \(\binom nj\le(Cn/k)^{k/2}\) for \(1\le j\le k/2\) shows that every absolute row sum of \(D^*D\) is at most \[R_k=C^k(1+d)^{Ck}(k/n)^{k/2}.\] For \(k=1\) the contact event is empty and the same assertion is immediate. Since \(D^*D\) is self-adjoint, the column sums obey the same bound, and the Schur test gives \(\|D^*D\|\le R_k\). On that zero-marginal subspace, \(D=K\), so \(\|K\|^2\le R_k\). This proves (47) without another square-root loss.

The second estimate is Proposition 6.3 of OpenAI (2026b), applied with \(T_N=B_n\) and \(N=n\). Its input, Theorem 6.1 of that companion, is the stronger density statement \[ \sup_x n^{-k}\sum_y \{n^k\Pr_{B_n^*B_n}(x\mapsto y)\}^{1+\delta} \le e^{Ck} \tag{50}\] for a fixed absolute \(0<\delta\le1\), all \(0\le k\le n\), and every ordered injection \(x\). Repeated-site output tuples contribute zero. The companion gives the displayed power normalization as well as the normalization by \((n)_k\), in both orientations and for both rows and columns. Its Proposition 6.3 transfers this bound through the right \(S_k\) label action to obtain exactly (48), with \(a=\delta/(1+\delta)\). Section 6.6 there also proves the density estimate by the distinct cycle-window certificate and entropy argument. Only these partial-deck statements are used here; the moment induction below remains local.

For sufficiently large \(d\), put \(s=\log(n/k)\) and suppose \(s\ge d^{3/4}\). The first bound then gives \(\log\|B_n|_{V_\lambda}\|^2\le-ks/4\). Taking the geometric mean of this bound and (48), and increasing the fixed lower threshold on \(d\), gives \[\log\|B_n|_{V_\lambda}\|^2 \le-ks/8+Ck/2-(a/2)\log D_\beta \le-ks/16-(a/2)\log D_\beta.\] Since \(\log D_\lambda\le k(1+s)+\log D_\beta\), there is an absolute \(c>0\) such that \(\|B_n|_{V_\lambda}\|^2\le D_\lambda^{-c}\) in this range. In particular, \[D_\lambda\mathop{\mathrm{Tr}}(B_n^*B_n)^p \le D_\lambda^2\|B_n|_{V_\lambda}\|^{2p}\le1 \qquad(p\ge2/c).\] This supplies the trace moment directly for the sparse diagrams.

A coherent overlap on a punctured grid

We first estimate the overlap before restoring the holes. The projections below select a single carrier direction in each line, while retaining every multiplicity copy.

By positive spectral decomposition and group Plancherel, the same inequality gives, for group-algebra coefficients that factor over lines, \(w=\bigotimes_i w_i\in\mathbb C K\) and \(z=\bigotimes_j z_j\in\mathbb C J\), \[ D_\mu\|(zw)_\mu\|_{\mathrm{HS}}^2 \le e^{l+C(1+M+R)Q^2\log(2n)} \left(|K|\sum_{g\in K}|w_g|^2\right) \left(|J|\sum_{g\in J}|z_g|^2\right). \tag{56}\] The decomposition is applied to \(ww^*\) and \(z^*z\), so every summand is positive.

General diagrams by ordered holes

We now return to the full \(M\) by \(R\) grid and reset the groups to \(K=S_R^M\) on rows and \(J=S_M^R\) on columns. Keeping the holes ordered makes the intermediate list unique when the initial and final lists are prescribed. The resulting coefficient-square sum has the following explicit cost.

Closing the uniform moment