Row–column symmetry and contraction of coordinate sweeps

1 Introduction

A coordinate sweep of the Thorp shuffle acts on N=2^d labeled cards. It scans the d binary coordinates in order and, in each direction, independently swaps or leaves unchanged the two cards on every parallel edge. A single card is uniform after a sweep. The full permutation retains dependence because the cards have used the same switches. We prove that an absolute number of sweeps suffices to mix the full permutation. Since a sweep consists of d physical shuffles, this gives the optimal order \Theta(\log N) in physical shuffle time.

The Thorp shuffle arose in a study of nonrandom shuffling and advantageous play in Faro [22]. For N=2^d, Morris proved an O(d^{44}) bound using evolving sets [14]; Montenegro and Tetali sharpened the spectral-profile and evolving-set analysis to O(d^{29}) [13, Section 6.4]. Morris then used entropy contraction to obtain O((\log N)^4) mixing for every even deck size [15], followed by an O(d^3) bound for dyadic decks [16]. These estimates concern the full permutation and count individual physical shuffles; one coordinate sweep comprises d such steps.

The O(d^3) full-deck benchmark is also recorded in the November 2025 account of Alekseev et al. [1, Section 1]. Faster bounds for observing a fixed fraction of the cards, such as the O((\log N)^2) bound of Czumaj and Vöcking [7], concern a different projection of the permutation law. Here we obtain the order O(d) for the full permutation on a dyadic deck, together with quantitative row–column representation estimates. The support bound in Proposition 8.1 gives the matching lower order.

To see the geometric issue, split the coordinates into two consecutive groups. The positions become a rectangular board. The first part of the sweep acts within rows, and the second within columns; each part consists of independent smaller sweeps. This suggests an induction on the number of coordinates. Its obstacle is that the row and column symmetry decompositions differ, and their projections generally do not commute. We estimate how much of a vector selected by one decomposition can survive selection by the other. Three forms of this estimate lead to the same mixing conclusion while retaining different information about the representation spaces.

1.1 The sweep and its moments

Positions are vectors x=(x_1,\ldots,x_d)\in\mathbb F_2^d. A physical Thorp shuffle sends

where the 2^{d-1} bits \xi_u are independent and fair. Let q_d denote the law of this shuffle. Removing the deterministic cyclic rotation after each shuffle gives successive matching updates in the d coordinate directions. After d updates the rotation is the identity. Thus one coordinate sweep has exactly the law of d physical shuffles.

Permutations map initial positions to final positions, and gh applies h first. Let K_d=q_d^{*d} denote the law of one sweep. On the complex unitary irreducible representation V_\lambda of S_N, indexed by a partition \lambda\vdash N, put

A matching layer is an orthogonal projection, so K_d(\lambda) is a contraction. All traces are ordinary, unnormalized traces, and \|A\|_p^p=\operatorname{Tr}|A|^p. The matrix K_d(\lambda) need not be normal. On restriction to a subgroup, an irreducible type may occur several times. We call its representation space the carrier and distinguish directions within it from the different multiplicity copies.

Our first estimate attaches a positive weight to each Young diagram. When we pass from the full board to its rows and columns, the difference between the diagram weights pays for the cost of restoring deleted cells. The weights still retain a fixed power of representation dimension. Their construction appears in Section 4.

The bounded exponent gives a dimension power uniformly over all diagrams and deck sizes. It also yields a common unweighted moment: for an absolute q<\infty,

Indeed, at p=p_d the theorem gives \|K_d(\lambda)\|_{\rm op}^p\le W_\lambda^{-1}, and hence

Since the matrices are contractions, q=4p_*/3 works simultaneously. The later two routes prove a bound of the form (2) directly. Their additional information lies in the intermediate row–column estimates described below.

We use \|\mu-\nu\|_{\rm TV}=\tfrac12\sum_g|\mu(g)-\nu(g)|. Let t_{\rm mix}(d) be the least number of physical shuffles for which the distance from the uniform full-deck law is at most 1/4, from every starting deck.

The upper bound follows from finite-group Plancherel and Cauchy–Schwarz [8, Sections 2 and 3], applied to a fixed number of repeated forward sweeps. The lower bound counts the possible permutations produced by the random switches. Both deductions are given in Section 8.3, after the first moment proof.

1.2 From row–column overlap to a bounded exponent

The first route begins by choosing a subdiagram a\subseteq\lambda inside an (h,h)-hook: no box of a has both row and column index greater than h. If t=N-|a|, we let the symmetric group on the N-t occupied cells of a board act through V_a. Hook trimming and the choice of weights control the cost of making this reduction. The representation V_a occurs in a tensor space with an h-dimensional even part and an h-dimensional odd part. This hook realization is classical in signed tensor representation theory [4]; we obtain the form needed here from ordinary Schur–Weyl duality on the two parts and signed induction.

Theorem 5.1 bounds overlap on every occupied-cell pattern, summing over all orthogonal copies of a fixed row type and column type. Its proof majorizes the subgroup projections by positive mixtures of products of one-cell states. Normalizing by the average state on each side reduces the product estimate to the entropy of a uniformly chosen occupied cell relative to the product of its row and column marginals. This is where the geometry of the board enters: the entropy cost is controlled by the number of deleted cells, regardless of their arrangement. The entropy step is a finite form of the duality between product inequalities and entropy subadditivity [6, Theorem 2.1 and (2.4)].

To return to V_\lambda, choose a diagram b on the t deleted boxes such that V_\lambda occurs in the representation induced from V_a\otimes V_b. That induced representation has one copy of V_a\otimes V_b for each placement of the deleted cells. Restricting a row or column representation to the stabilizer of a placement decomposes its carrier into tensor products of surviving and deleted carrier spaces, with multiplicities. The resulting coefficient states can be entangled between these carrier factors. Lemma 6.1 transfers the occupied-cell bound to such states. Positive coefficient states have total trace one, so summing their contributions introduces no new carrier-dimension count. The remaining placement entropy is paid by the difference between the weight of \lambda and the weights of its row and column types.

Weighted Schatten interpolation then transfers the projection bound to arbitrary matrices in the row and column Fourier blocks. Its logarithmic error is independent of the Schatten exponent. Applied to the two families of smaller sweeps, the bound increases the required exponent by only a factor 1+C/d. These factors have bounded product along successive halvings of d. A direct forest estimate covers diagrams whose first row contains almost every box; a strict norm gap in finitely many small dimensions starts the induction. This proves Theorem 1.1 in Section 8.

1.3 Two further forms of the overlap estimate

Section 9 keeps track of the number of selected directions inside each row and column carrier, while including every multiplicity copy. Its Schatten-8 bound has a cost controlled by the number of boxes below the first row. A separate signed-tensor estimate has a cost controlled by the number of boxes outside a small hook. The two bounds cover complementary shapes, and a sparse estimate using short time windows completes another bounded-exponent induction.

Section 10 instead retains the deleted positions as an ordered list. Summing squared coefficients over the initial, intermediate, and final hole lists gives the explicit restoration factor e^{3l}\binom Nl, where l is the number of holes. Its occupied-cell estimate resolves the row and column projections by averaging over compact-group orbits of highest-weight vectors [19, Section 2]. A minimum-norm argument matches their averaged one-cell densities to a common density before the row–column comparison. This normalization is related to the highest-weight capacity framework of Franks and Walter [10, Sections 2 and 4]; we prove the required form locally to keep the loss from missing cells explicit. The overlap proof and moment induction are given here. The sparse part uses the partial-deck density and lower-diagram bounds of OpenAI [18, Theorem 6.1 and Proposition 6.3].

The companion Random-subspace tests and trace smoothing for coordinate sweeps [17] develops related trace-smoothing estimates. For symmetric-group and tableau conventions we follow Sagan [20], Stanley [21]; branching and content spectra are also developed by Vershik and Okounkov [23]. We use ordinary Schur–Weyl duality in the form of Etingof et al. [9, Theorem 4.57 and Corollary 4.59].

Section 2 fixes the common representation conventions. Part I constructs the weights, proves the occupied-board and restoration bounds, and completes the first moment proof and the mixing deduction. Part II develops the selected-rank frame estimates and their moment induction. Part III proves the ordered-hole estimate and closes the coherent-state induction using the cited partial-deck input.

2 Representations and subgroup projections

Throughout, logs used in estimates are natural logs. We write G_L for the symmetric group of degree L; spaces can equally well be indexed by sets of size L. Denote the representation belonging to a partition \lambda by V_\lambda, and its dimension by D_\lambda. We also write V_\mu,D_\mu for an irreducible of a product group and its dimension. We take the group of degree 0 to be trivial, and allow empty partitions where appropriate. All representations are taken unitary (over \mathbb C). The trace and Schatten norms on a single matrix space use unnormalized trace unless otherwise indicated. We use \|M\|_p=(\operatorname{Tr}|M|^p)^{1/p}, including operator norm at p=\infty.

We use the following characteristic-zero facts and normalization conventions.

• •

  We use tableau dimensions, the branching rule, and the hook-length formula for symmetric groups [20, Theorems 2.6.5, 2.8.3, and 3.10.2]. Thus restriction to a symmetric group of smaller degree has shapes given by box deletions. Transposition of a partition corresponds to tensoring with the sign [11, Theorem 6.7], and induction from two factors of a Young subgroup uses the Littlewood–Richardson coefficients [11, Theorem 16.4].

• •

  We will also use ordinary Schur–Weyl duality on a complex tensor power, with the unitary group action on the factors and permutations of slots [9, Theorem 4.57 and Corollary 4.59]. For a local dimension h, the factors in the decomposition for tensor degree l are the polynomial unitary-group representation with highest weight \gamma and V_\gamma, for \gamma\vdash l of length at most h. We use Schur characters in their semistandard-tableau form [21, Definition 7.10.1]. In particular a positive operator acting identically in the slots has, on type \gamma, largest eigenvalue given by the monomial of exponents \gamma on its eigenvalues sorted in decreasing order. This follows also by column strictness in the tableaux and the presence of the highest weight. The statement for zero eigenvalues can be taken by a limit.

• •

  Given an irreducible \mu of a subgroup R and a matrix M on V_\mu, we can use a group algebra element of R with matrix M there, and zero matrix on its other types, viewed also in any larger group. Its coefficient at g\in R is

  \frac{D_\mu}{|R|}\operatorname{Tr}\big(M \rho_\mu(g^{-1})\big),

  where \rho_\mu denotes the representation. We refer to the images of this element as matrix actions supported on \mu. For M the orthogonal projector onto a unit vector e, denote such an image by P_{\mu,e}, specifying or taking as understood the ambient representation. On restriction to R, this is an orthogonal projection using one direction of the carrier and acting identically on the corresponding multiplicity space. A full isotypic projection instead uses I_{V_\mu}. We use the standard orthogonality and Plancherel formulas. In particular the sum of squared absolute values of the above coefficients is D_\mu\operatorname{Tr}(M^*M)/|R|.

Write K_d(\lambda) for the Fourier matrix (expectation of the representing matrix) on V_\lambda, \lambda\vdash N, N=2^d. The length of any partition we need to consider with K_d(\lambda)\ne 0 is at most N/2: one matching of switches already projects to invariants of a Young subgroup with N/2 parts of size 2. The corresponding permutation module only has partitions of length at most N/2 (for example, it occurs in an ordinary slot permutation tensor power with local dimension N/2).

Part I Weighted contraction

3 Dimensions away from a long first row

Write k=N-\lambda_1 for the number of boxes below the first row. The following dimension estimate will be used in all three moment arguments.

In particular, for fixed small \epsilon>0, if k>N^{1-\epsilon} and \lambda has length at most N/2, then

4 Weights from hook trimming

The weights balance the dimension of a subdiagram against the number of boxes removed. Their parent–child difference will pay for the entropy of restoring deleted cells, while retaining a favorable dimension term. For L\ge2, fix

and define

For a Young diagram \lambda\vdash L, a subdiagram a\subseteq\lambda is itself a Young diagram. Put

Empty diagrams have dimension one. For sizes zero and one put J=0 and W=1. Since AF_L(r)\le(b_1/2)r\log L, the expression minimized is nonnegative; taking a=\lambda gives 0\le J(\lambda)\le\frac14\log D_\lambda.

On a tuple of partitions for a product of same-size groups, we sum the J values and multiply the W values. We next show that the minimizing subdiagram can be chosen in a hook at a controlled cost.

We will need that at L=N, at additive cost at most O(h^2) in the minimum of (4), we can take a in the h,h-hook, i.e. with no box of indices i>h,\ j>h, for h=\lfloor N^\delta\rfloor and N sufficiently large. To show it, take a minimizing partition a_1 and trim off the boxes with both indices >h leaving a. Write x for the number trimmed and M=|a_1|, supposing x>0. The hook length formula gives

Here the log factorial gain for a_1 is at least x(\log M-1), and hooks in the trimmed boxes are at most 2M/h. Hooks within a changing length due to horizontal extensions are bounded in their log ratio sum by

where p is the number of rows of the trimmed portion and x_i their lengths within that portion, decreasing weakly. If p\ge h, linearize by \log(1+v)\le v, and use that the sum of reciprocals over j increases with i; its average over i is at most 2 (bound the double sum of reciprocals by extending to p columns and summing on diagonals). Thus pairing with decreasing x_i gives a bound 2x. If p<h, the sum of the row contributions is at most

The transpose handles vertical extensions. This proves (5). The change upwards in b_1 r\log N-A F_N(r) from increasing r by x is at most (b_1\log N+A)x, by the bound -1 on how negative a slope of F_N can be. Since b_1<b_0\delta, the asserted near-minimum property follows.

For such an a, put t=N-|a|. We will use

where the second estimate uses the cap in F_N. We allow the empty partition, with dimension 1.

We next prepare an estimate for transverse decompositions of a representation in this hook. This will later be used on a set of cells of a grid excluding t cells.

5 Signed representations on occupied cells

6 The row-column Fourier estimate

Split a sweep of dimension d into two parts, each scanning consecutive coordinates, with block sizes d_1=\lfloor d/2\rfloor and d_2=d-d_1. Index positions as a grid, so these parts use the within-row and the within-column subgroups, denoted R,C_{\rm col}. Write n for the size of a row and m for that of a column, so mn=N, m,n both within a constant factor of \sqrt N. We take d large. Suppose henceforth in the estimate that

For irreducibles \mu,\nu of R,C_{\rm col}, each a tuple, and unit carrier vectors e,f, we claim the following bound on projections in V_\lambda:

All constants are independent of the types and of d.

Use the hook a from (6) and choose a partition b\vdash t such that

contains V_\lambda, possible by branching and decomposing the restriction. We bound the trace of X Y on \mathcal I, for X=P_{\mu,e}, Y=P_{\nu,f} acting here; this bounds the desired trace before multiplying by W_\lambda, as the trace on each contributing G_N-type is nonnegative. Use the direct sum structure of \mathcal I with a fiber at each t-set Z of the grid. Its stabilizer acts on this fiber by V_a on the complement and V_b on Z.

Let v_i be the counts of Z in rows and u_j in columns. The full row and column orbit sizes and overall size we denote by

Let L_{RC} be the number of sets with the indicated two profiles. Use untruncated quantities

Here again terms at zero count are zero. For nonempty layout classes E_0\ge 0; for t>0 it is t times the relative entropy of the uniform distribution on Z with respect to the product of its marginals. We have

Indeed \log L_R\ge H_R,\log L_C\ge H_C,\log L_0\le H_0+t by binomial bounds. For a uniform random set with the two profiles, subadditivity bounds \log L_{RC} by the sum of marginal indicator entropies. To bound that sum, choose a cell uniformly and call its indices I,J and its random indicator V. As I,J are independent,

in ordinary entropy notation (by nonnegativity of conditional mutual information). Multiplying by N, the terms on the right give an upper bound at most (H_R+t)+(H_C+t)-H_0, since the complementary term to v_i\log(n/v_i) in row binary entropy times row size is at most v_i, and similarly for columns. Thus \log L_{RC}\le E_0+2t. Combining this with the three binomial bounds gives

which proves (12).

6.1 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

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

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

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

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 6.1 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 5.1; it is needed when the placement entropy is paid.

Denote

Using (7), (14), and (15), after dividing by D_\alpha D_\zeta from the diagonal-block formulas, the pure-state bound becomes

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

taking the largest needed over contributing types.

6.2 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

Together with (6) this gives

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

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

7 Weighted Schatten interpolation

The row part and the column part of the sweep, as group algebra elements, multiply to give K_d in the order specified by the scan (either product order will be fine for estimates). Within each row, the row part is an independent sweep in its smaller number of bits, and analogously for the columns. This holds because a group of consecutive bit updates in this sweep uses matchings confined to the indicated sets of positions, independently across the sets.

Still under (10), let \mathcal B(M,M') on V_\lambda be the product of matrix actions, one for each subgroup, using arbitrary matrices M_\mu and M'_\nu on their respective irreducibles. Each subgroup action here is the sum over its irreducibles. By (11) we have

For a single pair of types this follows by writing the squared norm as a trace of a product of positive matrix actions (using the matrices times their adjoints or the reverse, as appropriate), then diagonalizing and using (11). To sum in (19) use the triangle and Cauchy-Schwarz inequalities, absorbing log count factors into the given error. The log counts of the tuples of partitions for the two groups are O(N^{3/4}\log(N+2)), using e.g. the partition count bound \exp(O(\sqrt n\log(n+2))) (split a partition according to parts of size greater than \sqrt n and the rest). So (3) suffices. Also

by unitary restriction. For 2\le p<\infty, interpolation therefore gives

with the coefficient in the log error bounded independently of p.

For details, let E=C(\log D_\lambda)/d be a common logarithmic error bound in (19). The direct-sum Schatten norms use traces weighted blockwise by the given positive numbers and the output norm similarly. The bilinear map has norm at most e^{E/2} at the 2 endpoint and at most one at the \infty endpoint. Normalize both inputs to norm 1 at p, and test the output using the output weighted trace with a dual-norm-one matrix at p'=p/(p-1). In the strip with value taken at z=2/p, extend the inputs analytically blockwise using their polar factors and exponent p z/2 on their absolute values (zero singular directions may be kept zero). Their norms on the two boundaries, at \infty and 2 respectively, are then bounded by 1. Extend the matrix used in the trace test similarly (analytic for the matrix appearing in the trace), with exponent p'(1-z/2) for boundary norms at 1 and 2. At \theta=2/p, the three-lines inequality applied to the weighted trace with the bilinear product gives the factor e^{(E/2)\theta}=e^{E/p}. Taking the p-th power gives e^E in (20), with no growth of the logarithmic error coefficient in p.

8 Sparse representations and completion

We have established the matrix inequality needed for the recursive range. A direct estimate handles representations whose first row contains almost all boxes. We prove that estimate here, then close the induction.

8.1 A sparse forest estimate

Write k=N-\lambda_1. For k\ge 1 we have the bound

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

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

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

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 [5, 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

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

8.2 The bounded-exponent induction

8.3 Full-deck mixing

In particular for nontrivial \lambda with length at most N/2 we have

For an absolute sufficiently large number j of sweeps, by Plancherel and Cauchy–Schwarz [8, Sections 2 and 3], the squared total variation distance to uniform of their product law is at most

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.1, 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 1.2.

Part II Deletion frames

9 Marked-index frames and transverse tensor projections

This section proves a uniform unweighted Schatten bound. Two complementary row-column estimates are needed. One resolves functions by subsets of marked indices and uses cancellation of isolated contacts; the other realizes a diagram in a signed tensor space and normalizes row densities before comparing them with columns. All notation introduced below is local to this section. Traces are unnormalized, logarithms are natural, and a sweep on 2^d positions takes d physical shuffles. The representation-theoretic conventions are those of Section 2.

9.1 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 [20, Theorem 2.8.3], Pieri’s rule [21, Theorem 7.15.7], and the Littlewood–Richardson rule [11, Theorem 16.4], together with the hook-length formula [20, Theorem 3.10.2]. Ordinary Schur–Weyl duality [9, 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. [9, 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

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

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.

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

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

9.4 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,

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

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

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

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

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

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'}.

9.5 Density normalization on the remaining cells

For these majorizing averages, by positivity it suffices to bound uniformly

on the remaining sites of the placement. Use the uniform average over all b rows,

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

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

Denote these nonnegative entries by W_{ij'} and put \bar\sigma=m^{-1}\sum_{j'}\sigma_{j'}. Their full-board average satisfies

The sum over surviving cells is therefore at most n. Arithmetic–geometric mean on those N' cells gives

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

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

This proves (27) by (36).

9.6 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:

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

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

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,

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

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

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

(43) bounds the expected number of sets of u=\lceil c_2j\rceil such pairs by

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.

9.7 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

by tensoring (norms are contractions). Either product estimate (26), (27) with right hand log \mathcal E then gives

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

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

since j\ge n^{0.9}.

If F<j d^{1/4}, use (45) and F\ge c_6j to obtain

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,

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.

9.8 Full-deck amplification

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

Part III Coherent states

10 Coherent overlap and a uniform trace moment

We next ask how the overlap changes when missing positions are retained as an ordered list. Write n=2^d and B_n=K_d for d\ge1; for d=0 put B_1=\id, the empty sweep. The method proves a dimension-weighted trace bound with right side one. It combines a partial-mapping density estimate with a coherent-state overlap on a grid with holes. The coherent overlap uses a moment-matching change of basis; we include that step because it explains why the grid factors have mean at most one even after cells are removed.

10.1 Two sparse estimates

For a nontrivial \lambda=(n-k,\beta) with k=n-\lambda_1\ge1, the two inputs are

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

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 8.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,

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

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

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

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 [18], applied with T_N=B_n and N=n. Its input, Theorem 6.1 of that companion, is the stronger density statement

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

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,

This supplies the trace moment directly for the sparse diagrams.

10.2 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,

The decomposition is applied to ww^* and z^*z, so every summand is positive.

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

10.4 Closing the uniform moment