Binary positions and sweep operators

Number positions by \(x=(x_1,\ldots,x_d)\in\mathbb F_2^d\), most significant bit first. One shuffle sends \[x\longmapsto(x_2,\ldots,x_d,x_1+\xi_{x_2,\ldots,x_d}),\] where the \(2^{d-1}\) bits \(\xi\) are independent and fair. Write \(R\) for the cyclic rotation and \(h_t\) for the pair switches at physical time \(t\), so the time-\(t\) permutation is \(Rh_t\cdots Rh_1\). Factoring out \(R^t\) conjugates the switches into the successive coordinate directions. This deterministic left multiplication preserves distance to uniform. At time \(d\), \(R^d=I\), and one sweep has exactly the law of \(d\) physical shuffles. Write \(q_d\) for the law of one physical shuffle and \(U_{S_n}\) for the uniform measure. We use \[t_{\mathrm{mix}}(d)=\min\{t\ge0: \|q_d^{*t}-U_{S_n}\|_{\mathrm{TV}}\le1/4\}.\] Translation by the starting permutation shows that this is also the worst-initial-state mixing time.

Permutations send each input position to its output. A product \(gh\) applies \(h\) first. For measures, \(\mu*\nu\) denotes the law of \(gh\) for independent \(g\sim\mu,h\sim\nu\). In a unitary representation \(\rho_\lambda\), define \[\widehat\mu(\lambda)=\sum_g\mu(g)\rho_\lambda(g), \qquad\widehat{\mu*\nu}=\widehat\mu\,\widehat\nu.\] A fair switch layer averages the subgroup generated by its disjoint transpositions, and hence is an orthogonal projection \(\Pi_i\). With chronological coordinate order \(1,\ldots,d\), put \[B_n=\Pi_d\cdots\Pi_1,\qquad Q_n=B_n^*B_n, \qquad n=2^d.\] The layered switching network for this product is the butterfly network. In later sections, a butterfly means this same complete coordinate sweep, both as a random permutation and as its average operator.

Plancherel and powers of a nonnormal sweep

All matrix traces and Schatten norms are unnormalized. Thus \(\|A\|_{S^p}^p=\mathop{\mathrm{Tr}}|A|^p\), with \(S^2=\mathrm{HS}\) and \(S^\infty=\mathrm{op}\). If \(D_\lambda\) is the irreducible dimension, finite-group orthogonality gives \[|G|\sum_g|\mu(g)|^2=\sum_\lambda D_\lambda\|\widehat\mu(\lambda)\|_{\mathrm{HS}}^2.\] It applies to signed measures and subprobabilities as well as probabilities. For a measure \(v\) of mass \(m\), \[ \|v-mU_G\|_1^2\le \sum_{\lambda\ne\mathbf1}D_\lambda\|\widehat v(\lambda)\|_{\mathrm{HS}}^2. \tag{4}\] For a probability the left side is \(4\|v-U_G\|_{\mathrm{TV}}^2\). If \(0\le v\le\mu\) and \(\mu\) is a probability, then \[ \|\mu-U_G\|_{\mathrm{TV}}\le1-m+\tfrac12\|v-mU_G\|_1. \tag{5}\] Both follow from Cauchy–Schwarz and the triangle inequality, respectively.

Injection multiplicities and inverse-degree sums

We use the standard indexing of complex irreducibles of \(S_n\) by partitions \(\lambda\vdash n\), with \(D_\lambda=f^\lambda\) equal to the number of standard tableaux (Sagan 2001; Stanley 1999). Write \(k=n-\lambda_1\) and \(\bar\lambda=(\lambda_2,\lambda_3,\ldots)\). Young branching and Frobenius reciprocity show that the representation on ordered distinct \(r\)-tuples contains \(\lambda\) with multiplicity \[f^{\lambda/(n-r)}.\] At \(r=k\) this is \(f^{\bar\lambda}\), and \(\lambda\) does not occur on fewer slots. If \(k\le r\le n-k\), the remaining first-row boxes are separated from the tail, giving \[ m_\lambda(r)=\binom rk f^{\bar\lambda},\qquad D_\lambda\le\binom nk f^{\bar\lambda}. \tag{6}\] The inequality follows by choosing the entries below the first row and forgetting cross-row tableau constraints. The same hook formula gives the useful quantitative refinement \[ D_\lambda\ge\binom nk f^{\bar\lambda} \exp\left(-\frac{k}{n-2k+1}\right) \qquad(0\le k\le n/2). \tag{7}\] Indeed the hook inflation along the top row, relative to \((n-k)!\), is \[\prod_{j\le\lambda_2}\left(1+ \frac{\lambda'_j-1}{n-k-j+1}\right).\] The denominators are at least \(n-2k+1\) and \(\sum_j(\lambda'_j-1)=k\). Taking logarithms bounds this product by \(\exp(k/(n-2k+1))\). The remaining hooks are exactly those of \(\bar\lambda\). In particular for \(k\le.14n\) the loss is \(\exp(O(k/n))\), which also supplies the weaker \(\exp(O(k\log n/n+k/n))\) loss when that form is convenient.

The inverse-degree convergence below is the case \(s=1\) of the stronger estimate of Liebeck and Shalev (Liebeck and Shalev 2004, Theorem 2.6). We include an elementary proof together with the pointwise bound needed later. These estimates specify which negative dimension powers are available to the different proofs.

Hook dimensions and the local trace

Labeled-hole traces and the local entropy factor

The pointwise-stabilizer lemma can be inserted into the signed tensor trace without any implicit normalized trace. Let \(n=sm\), let \(l\) distinct labels mark the holes, and let \(p=n-l\). The direct sum of spin spaces over all ordered hole placements is \[\operatorname{Ind}_{S_p\times S_l}^{S_n} (V^{\otimes p}\otimes\mathbb C[S_l]).\] Here \(S_l\) acts regularly because every hole has its own label. Its global spin type \((\alpha,\beta)\) has permutation representation \[\operatorname{Ind}_{S_{|\alpha|}\times S_{|\beta|}\times S_l}^{S_n} (V_\alpha\otimes V_{\beta^t}\otimes\mathbb C[S_l]) \quad\hbox{with carrier factor }\mathcal U_\alpha\otimes\mathcal U_\beta.\] For group-algebra elements \(X,Y\) that are products of positive elements over columns and rows respectively, let \(X_z,Y_z\) be their diagonal blocks at placement \(z\). Let \(P\) be the global \((\alpha,\beta)\)-type projection on the direct sum over hole placements, and let \(P_z\) be its block at \(z\). If \(V_\alpha\otimes V_{\beta^t}\otimes V_\gamma\) occurs in the restriction of \(V_\lambda\), its multiplicity in this space is at least \(D_\gamma u(\alpha,\beta)\). Consequently, \[ D_\gamma u(\alpha,\beta)\operatorname{Tr}_\lambda(XY) \le\operatorname{Tr}(PXY) =\sum_z\operatorname{Tr}(P_zX_zY_z). \tag{15}\] Every irreducible trace of \(XY\) is nonnegative, since it is the trace of a product of two positive matrices. Thus one may discard both other irreducibles and any additional multiplicity copies. The last identity follows from a geometric constraint: a nonzero block \(X_{z,w}\) preserves each hole’s column, while a nonzero \(Y_{w,z}\) preserves each hole’s row. Both constraints force \(w=z\). At fixed \(z\), each factor of \(X_z\) is exactly a coefficient restriction to the subgroup fixing the labels in its column. In the moment induction we retain only \(D_\gamma\) on the left; this is legitimate because \(u(\alpha,\beta)\ge1\).

For clarity, one useful quantitative consequence of Lemma 10 is recorded next.

Dimensions outside the sparse range

The induction needs a lower bound on dimension to absorb its counting errors. Shapes with more than \(n/2\) rows are already annihilated by Lemma 3; the following estimate treats the others.

The sparse weighted-forest estimate

Here is the operator estimate for small levels. For any fixed \(0<\delta<1\), for \(1\le k=n-\lambda_1\le n^{1-\delta}\), \[ \|B_n\|_{V_\lambda}\le e^{O(k)} (2dk/n)^{k/4} \tag{17}\] for large \(n\), where the notation on the left means operator norm in \(V_\lambda\).

Let \(\Omega_k\) be the ordered \(k\)-tuples of distinct positions. By branching, \(V_\lambda\) occurs in \(\ell^2(\Omega_k)\) and is orthogonal to every function that omits at least one tuple coordinate. We may use either the sweep kernel or its adjoint, since their norms agree. For \(A\subseteq\{1,\ldots,k\}\) and any tuple \(x\) whose \(A\)-coordinates are distinct, define \[F_A(x,y)=n^{|A|}\mathbb P\{B_n(x_i)=y_i\text{ for all }i\in A\}, \qquad L_A(x,y)=n^{-k}F_A(x,y).\] In this probability \(B_n\) denotes a random sweep permutation. Allowing arbitrary \(y\in(\mathbb F_2^d)^k\), \(L_A(x,\cdot)\) is the probability law obtained by running all labels in \(A\) through one sweep and sending each other label independently to a uniform position. Thus \(L_A\) is a Markov kernel on tuples whose \(A\)-coordinates are distinct; its restriction to \(\Omega_k\) can lose mass. In particular, \(L_{\{1,\ldots,k\}}\) is the tuple kernel.

Given endpoints \(x,y\), each label has a unique path through a sweep, because each coordinate is processed once. Join two labels when their paths use the same switch location. If label \(i\) is isolated, its switch prescriptions are independent of those of all other labels. Hence \(F_{A\cup\{i\}}(x,y)=F_A(x,y)\) whenever \(i\notin A\). On \(V_\lambda\) we can therefore compute matrix coefficients with \[n^{-k}\sum_A (-1)^{k-|A|} F_A(x,y)\] since all proper subsets give zero there. It vanishes if there is an isolated vertex. Consequently we bound the norm by the sum of norms of nonnegative kernels \[K_A(x,y)=n^{-k}F_A(x,y) {\bf1}_{\{\text{the encounter graph has no isolated vertex}\}}.\]

We next bound \(K_A\) by a two-trip experiment. Draw \(y\) from \(L_A(x,\cdot)\). From \(y\), run a fresh reversed sweep for the labels in \(A\), and an independent fresh reversed sweep for each other label; call the resulting tuple \(x'\). For distinct \(y,x'\), the transition weight of this second trip is \(L_A(x',y)\): the coupled tuple sweep is replaced by its adjoint, and the one-label weights remain \(1/n\). Let \(\mathcal E_2\) be the event that the second-trip paths have no isolated label. Removing the first-trip encounter requirement and both distinctness requirements gives \[\sum_{x'\in\Omega_k}(K_AK_A^*)(x,x') =\sum_{y,x'\in\Omega_k}K_A(x,y)K_A(x',y) \le\mathbb P_x(\mathcal E_2).\] The coupled labels remain distinct in either trip; the dropped constraints concern the full tuple, including the independent labels.

Condition only on the switch settings of the second trip. There is one fixed permutation network for \(A\) and one for each label outside \(A\); the first-trip endpoints \(y\) remain random with their original law. Make a graph with one vertex for every starting position in each of these networks. Join distinct vertices when their fixed paths use the same switch location at a layer, also across networks. A vertex has at most \(2d\) neighbors in any one network.

Let \(S\) be the set of the \(k\) occupied vertices. For every set \(T\) of distinct graph vertices we have \[\mathbb P\{T\subseteq S\}\le\prod_{w\in T}p_w, \qquad p_w=\begin{cases}|A|/n,&w\text{ in the }A\text{-network},\\ 1/n,&w\text{ in a one-label network}. \end{cases}\] To see the assertion for the \(A\)-network, track its position subset during the first trip. Initially it is fixed, so the joint-inclusion bound by products of the one-site marginals holds. A fair independent swap preserves this property. A test set containing exactly one swapped site uses linearity of the two probabilities; for a set containing both, the old product \(p_up_v\) is at most the new product \(((p_u+p_v)/2)^2\). Sets containing neither are unchanged. At the end every marginal is \(|A|/n\), because each label is uniform. The occupied starting positions in the one-label networks are independent of this subset and of one another; selecting two vertices in one such network has probability zero. This proves the displayed joint-inclusion bound. For a deterministic starting subset, this inclusion bound is also a consequence of the stronger negative-dependence theory for random swap-or-retain operations (Borcea et al. 2009, Theorems 4.20 and 4.9).

In this weighted graph the total mass is \(k\), and the weighted neighbor sum is bounded by \(\Delta=2dk/n\). To have no isolated vertices, the \(k\) occupied vertices must contain a forest on \(k\) vertices with component sizes at least two. Counting rooted plane trees for the components, the sum of product weights for candidates is bounded by \[e^{O(k)}\sum_{1\le j\le k/2}\frac{k^j}{j!}\Delta^{k-j}.\] Indeed the plane forest shapes (ordered components) are at most exponentially many, and for any ordered shape the weight sum is bounded by \(k^j\Delta^{k-j}\) by descending from its \(j\) roots. One can divide by \(j!\) for the possible orders, since witnessing vertices are distinct. In the sparse range \(\Delta\le1\) for large \(n\), and \[\sum_{1\le j\le k/2}\frac{k^j}{j!}\Delta^{k-j} \le\Delta^{k/2}\sum_{j\ge0}\frac{k^j}{j!} =e^k\Delta^{k/2}.\] For \(k=1\) the encounter event is empty. For the symmetric nonnegative matrix \(K_AK_A^*\), the maximum row sum bounds the spectral radius. Therefore \[\|K_A\|_{\mathrm{op}}^2 \le\|K_AK_A^*\|_{\infty\to\infty} \le e^{Ck}\Delta^{k/2}.\] Taking square roots and summing the \(2^k\) subset kernels gives \(e^{O(k)}\Delta^{k/4}\), proving (17).

Parameters and the induction range

We now turn to (3). Take a fixed small \(\epsilon\), say \(1/64\), and use \[\eta_d=\bar\eta(1-1/(2\sqrt d)),\qquad \kappa_d=\bar\kappa(1-1/(2\sqrt d)).\] Take \(\bar\eta<1\) and \(\bar\kappa>0\) sufficiently small that \(\bar\kappa<\epsilon\bar\eta/4\); both can be fixed as absolute constants. Set \(\kappa_-=\bar\kappa/2\). Fix \(\xi>0\) sufficiently small, e.g. \(\min(1/32,\kappa_-/4)\), and use the small-level estimate with \(\delta=\xi/4\). In the range of (17), \(D_\lambda\le n^k\), so (3) holds with \(J_n(\lambda)\le 1\) for sufficiently large fixed \(r\). For any fixed finite range of sizes, Lemma 4 and \(J_n(\lambda)\le D_\lambda^2\|B_n\|_{V_\lambda}^{2r}\) allow one \(r\) to make every nontrivial weighted moment at most one. The trivial moment is one.

We prove (3) by induction on \(d\), using a split into nearly equal numbers of coordinates. We only need to perform the induction step for sufficiently large \(d\), with all largeness bounds independent of \(r\); the same \(r\), taken as a positive integer, can then be used throughout. In view of the previous bounds we assume \[ \lambda_1^t\le n/2,\qquad k=n-\lambda_1>n^{1-\delta}, \qquad \log D_\lambda\ \ge c n^{1-\delta}. \tag{18}\] (The trivial case is already covered.) Put \(s=2^{\lfloor d/2\rfloor}\), \(m=2^{\lceil d/2\rceil}\), so positions form \(m\) columns of size \(s\), and \(s\) rows of size \(m\). Take the columns and rows corresponding to the consecutive parts of the sweep. Let \(B_{\mathrm{col}}\) be the product of the size \(s\) column sweeps and \(B_{\mathrm{row}}\) the product of the size \(m\) row sweeps, so \(B_n=B_{\mathrm{row}}B_{\mathrm{col}}\). Put \(U=B_{\mathrm{row}}^*B_{\mathrm{row}}\) and \(V=B_{\mathrm{col}}B_{\mathrm{col}}^*\). The matrices \(B_n^*B_n\) and \(U^{1/2}VU^{1/2}\) have the same nonzero spectrum: they are \(T^*T\) and \(TT^*\) for \(T=U^{1/2}B_{\mathrm{col}}\). Applying the Araki–Lieb–Thirring trace inequality \(\operatorname{Tr}(U^{1/2} V U^{1/2})^r\le\operatorname{Tr}(U^r V^r)\) for positive matrices and \(r\ge1\) gives \[ \operatorname{Tr}_\lambda (B_n^* B_n)^r \ \le\ \operatorname{Tr}_\lambda(XY), \tag{19}\] where \(X=V^r=(B_{\mathrm{col}}B_{\mathrm{col}}^*)^r\) and \(Y=U^r=(B_{\mathrm{row}}^*B_{\mathrm{row}})^r\) are positive group algebra operators in the columns and rows respectively. They are products over their blocks, with single-block factors \((B_sB_s^*)^r\) in columns and \((B_m^*B_m)^r\) in rows. The two orientations of a child’s positive square have the same trace, so both use the child moment in (3).

Write \(\eta'=\eta_{\lceil d/2\rceil}\) and \(\kappa'=\kappa_{\lceil d/2\rceil}\), the larger coefficients of the two child sizes.

Signed spins and holes

We can first assume that both \(\alpha,\beta\) have length \(\le q=\lceil n^\epsilon\rceil\). Indeed, truncate each after \(q\) parts and move the remaining boxes into the number \(l\), say increasing it to \(L\). By branching and (1) the new pair of diagrams works with some diagram on \(L\) positions. If \(F'\) is the new entropy, \(F-F'\ge (L-l)\log q\) since removed parts have size at most \((u+v)/q\). And \(g_n(L)-g_n(l)\le (\kappa_d\log n+1)(L-l)\). Thus the bound with the new data implies the desired one, for large \(d\).

For data with these bounded lengths, our next objective is \[\log J_n(\lambda) \le\eta' F(\alpha,\beta)+\kappa'l\log n-l\log(n/l) +O(l+n^{1-\xi}).\] The local stabilizer traces will retain the child entropies; the angle estimate will convert them to the prescribed global entropy. Counting the labeled placements will produce the negative remainder term. The increments from \(\eta',\kappa'\) to the parent coefficients will then absorb the displayed error.

Use the signed space \(V=\mathbb C^q\oplus\mathbb C^q\) and its commuting group \(U(q)\times U(q)\) from Section 2. For a local spin type \((a,b)\) its permutation representation is \[ \operatorname{Ind}_{S_{|a|}\times S_{|b|}}^{S_{|a|+|b|}} (V_a\otimes V_{b^t})\otimes\mathcal U_a\otimes\mathcal U_b, \tag{20}\] by (8). Its compact carrier has dimension at most \((n+1)^{q(q-1)}\). Tensor positions may be regrouped by the signed permutation unitaries; parity-preserving spin matrices regroup in the usual way.

Allow \(l\) holes in addition, specially marked by distinct labels, one assignment \(z\) specifying distinct sites for these holes. The space is the orthogonal sum over \(z\) of spin spaces on the remaining sites, with holes permuting along with positions (holes count as plus in the sign convention). Project to global spin type \((\alpha,\beta)\) under the simultaneous \(U(q)\times U(q)\); call this projector \(P\), with its diagonal blocks at fixed assignments also denoted \(P\). Its space as a permutation representation contains \(V_\lambda\) with multiplicity at least \(D_\gamma\), by (20), (1), and the regular permutation space for ordering the \(l\) holes. Since (19) involves a trace of a product of positive elements, each irreducible contributes nonnegatively, so \[ D_\gamma \operatorname{Tr}_\lambda(XY) \le \operatorname{Tr}(PXY) =\sum_z \operatorname{Tr}(P X_z Y_z). \tag{21}\] Here \(X_z,Y_z\) are the diagonal blocks at \(z\), both positive. This diagonal-block reduction holds because \(X\) preserves the column of every hole label, \(Y\) the row, and hence in the trace the intermediate location must equal the specified location for each label. The projectors for the global spin group leave assignments fixed. At fixed \(z\), \(X_z\) factors in the column spin blocks on remaining sites, and \(Y_z\) similarly in the row spin blocks. Write \(h_j\) for the number of holes in column \(j\), and \(b_i\) for the number in row \(i\).

Local stabilizer trace bounds

We give local trace bounds for (21). Use local column spin-unitary type projectors \(P_H\), one type specified in each column, and local row type projectors \(P_K\). For these choices let \(F_H,F_K\) be the sums of the entropies (2) of their respective types, using each block’s own total spin-site count. All these projectors commute with \(P\); \(X_z\) commutes with \(P,P_H\) and \(Y_z\) with \(P,P_K\). Then for each fixed set of column types, \[ \operatorname{Tr}(X_z P_H) \le \left(\prod_j(s)_{h_j}^{-1}\right) \exp\left(-(1-\eta')F_H+\sum_j g_s(h_j)+O(n^{1-\xi})\right), \tag{22}\] where \((s)_h=s(s-1)\cdots(s-h+1)\). There is the analogous row bound with \(m,b_i\).

Apply Lemma 12 to each column with \(t=s\), \(h=h_j\), \(N=n\), \(G=g_s(h_j)\), and its specified local type \((a,b)\). For every constituent \(\rho\) the exact restriction step is \[ \operatorname{Tr}_\rho(E_{S_{s-h}}x) \le\frac{1}{(s)_hD_\rho}\sum_{\mu\supseteq\rho}J_s(\mu). \tag{23}\] Every extension \(\mu\) has an occurrence of \(a,b\) together with some \(h\)-box diagram, as proved in that lemma. Thus the every-occurrence induction hypothesis applies, with the larger child coefficients \(\eta',\kappa'\). Lemma 11 gives \[ \log D_\rho\ge F(a,b)-O(q^2\log(n+1)). \tag{24}\] The local trace lemma has already included the multiplicities and the compact carrier; these must not be inserted a second time. Its remaining factor is the partition count \(\mathsf p(s)\). Multiplying over lines, the logarithms of all carrier factors, partition counts, and choices of local types total \[O\bigl(n^{1/2+2\epsilon}\log(n+1) +n^{3/4}\log(n+1)\bigr)=O(n^{1-\xi}).\] The same calculation applies to rows. This proves (22), including full columns of holes and empty spin types. Every constant is independent of the moment \(r\).

An angle estimate from support inverses

Next we need the following angle bound on the type projectors on the spin space at fixed \(z\), writing \(F=F(\alpha,\beta)\): \[ \|P_H P_K P\|^2 \le \min\{1,\ \exp(F_H+F_K-F+ l+O(n^{1-\xi}))\}. \tag{25}\] To apply Theorem 9, take its occupied board to be the complement of the fixed hole assignment \(z\). Its global type is \((\alpha,\beta)\), its column types are the specified \(P_H\), and its row types are the specified \(P_K\). The local carrier product is at most \[(n+1)^{(s+m)q(q-1)}=\exp(O(n^{1/2+2\epsilon}\log(n+1))).\] This is absorbed by \(O(n^{1-\xi})\) because \(\epsilon=1/64\) and \(\xi\le1/32\). The theorem’s missing-cell factor is at most \(e^l\), with no assumption on the arrangement of the holes. Its entropy terms are exactly \(F_H,F_K,F\). This proves (25).

Combining the two positive traces

Using positivity, expansion into pairs of types in (21) bounds each term by \[\|P_H P_KP\|^2\,\operatorname{Tr}(X_z P_H)\operatorname{Tr}(Y_z P_K).\] Indeed spectral decompositions of the positive restrictions (also restricting to the global projector) give the angle squared as an upper bound for squared scalar products. Using (22), its row version, and (25) gains the exponent \(-(1-\eta')F\), since for \(w=F_H+F_K\) \[-(1-\eta') w+\min(0,w-F)\le -(1-\eta')F .\] Summing over type choices within our log errors, we obtain \[ \begin{aligned} \operatorname{Tr}(P X_z Y_z) &\le \prod_j(s)_{h_j}^{-1}\prod_i(m)_{b_i}^{-1}\\ &\quad\times\exp\left(-(1-\eta')F+\sum_j g_s(h_j)+\sum_i g_m(b_i) +O(l+n^{1-\xi})\right). \end{aligned} \tag{26}\]

Entropy of the hole assignments

We detail the count over hole assignments; it is important to keep the entropy terms from \(g_s,g_m\). First the falling factorials give a bound \(n^{-l} e^{O(l)}\) for the prefactor (one can use \((a)_p\ge a^p e^{-O(p)}\) for \(p\le a\)). Also \[ \sum_j g_s(h_j)+\sum_i g_m(b_i) \le \kappa' l\log n -\sum_j h_j\log(s/h_j)-\sum_i b_i\log(m/b_i) +O(n^{1-\xi}). \tag{27}\] In fact taking a maximum with zero in a column expression can raise it by at most \(O(s^{1-\kappa_-}\log n)\) since it is only needed at \(h_j\le s^{1-\kappa_-}\); use the similar row error. Finally \[ \sum_z n^{-l}\exp\left(-\sum_j h_j\log(s/h_j)-\sum_i b_i\log(m/b_i)\right) \le \exp\left(-2l\log(n/l)+O(n^{1-\xi})\right). \tag{28}\] Drop distinctness, so normalized counting uses independent column and row assignments with replacement to cells. For \(l>0\) the column negative sum exponent is \(-l\log(n/l)+l D(h/l\ \|\ \mathrm{unif}_m)\) with \(D\) the relative entropy of proportions (\(h=(h_j)\)). Each possible histogram has probability at most the exponential of minus the divergence term \(lD\), by the multinomial formula. The row count is analogous and independent, and the log numbers of histograms fit the error. More explicitly the normalized sum is at most \[e^{-2l\log(n/l)} \binom{l+m-1}{m-1}\binom{l+s-1}{s-1}.\] The logarithm of the two histogram counts is \(O((s+m)\log(n+1))\), within the stated error. For \(l=0\) the sum and the histogram product are one. All formulas omit zero-count terms.

Using \(D_\lambda\le \binom n l e^F D_\gamma\) by (1), we conclude from (19), (21), (26)–(28) that \[ \log J_n(\lambda) \le \eta' F+\kappa'l\log n-l\log(n/l)+O(l+n^{1-\xi}). \tag{29}\] It remains to absorb the error in (29). Put \(\Delta\eta=\eta_d-\eta'\) and \(\Delta\kappa=\kappa_d-\kappa'\). Both are bounded below by a positive constant times \(d^{-1/2}\) for large \(d\). By (18) and the same dimension upper bound, now using \(D_\gamma\le l!\), we have \(F+l\log n\ge c n^{1-\delta}\). The available increment can be divided into two parts: \[\tfrac12\Delta\kappa\,l\log n\ge c l\sqrt d, \qquad \Delta\eta F+\tfrac12\Delta\kappa\,l\log n \ge c\frac{n^{1-\delta}}{\sqrt d}.\] The first dominates \(O(l)\), and the second dominates \(O(n^{1-\xi})\) because \(\delta<\xi\). This proves the desired bound: replacing \(\kappa_d l\log n-l\log(n/l)\) by its maximum with zero only increases the right-hand side.

The order of choices is now explicit. First choose a threshold \(d_0\) large enough for every large-size comparison above; all its constants are independent of \(r\). Next choose one integer \(r\) exceeding the sparse threshold and all finitely many thresholds from Lemma 4 for \(d\le d_0\). Enlarging \(r\) decreases all moments. Together with the truncation argument, this completes the induction proving (3).

Full-deck amplification

The every-occurrence estimate is now proved. To turn it into a bound for the whole permutation law, we choose a zero-hole occurrence whose entropy is controlled by the irreducible dimension.

Guide to the later estimates

Write \(Q_n=B_n^*B_n\) and \(\lvert B_n\rvert=Q_n^{1/2}\). All traces in this guide are unnormalized; in particular, \(\operatorname{Tr}Q_n^r=\operatorname{Tr}\lvert B_n\rvert^{2r}\). The linked statements give the exact domains and constants. Theorem [s:spin-moment] bounds \(D_\lambda\operatorname{Tr}_{V_\lambda}Q_n^r\) for every prescribed signed occurrence, retaining its concatenated entropy and clipped remainder cost. The table compares the information retained by later estimates and the arguments that prove them.

Full symmetric-group isotypes

The conversion from compact types to full symmetric-group isotypes is static and uses no moment estimate. Here \(V=\mathbb C^q\oplus\mathbb C^q\) again has one even and one odd summand, for any integer \(q\ge1\). A full symmetric-group isotype collects the copies of its Specht module from every compatible compact color type. It includes all those multiplicity copies, whereas \(Q_{a,b}\) fixes one compact type.

Positive factorizations and missing cells

Extracting one compact type by matrix coefficients

The alternate density arguments below use a global compact-type projection between two products of local densities. The following matrix-coefficient formula turns that middle operator into an integral of tensor actions, with its carrier dimension explicit.

A marked recurrence with the full error term

The full-isotypic overlap now gives a recurrence for a prescribed marked complement. The estimate retains the hook parameter and the real Schatten exponent. This is useful when a subdiagram permitted at a parent scale is larger than those permitted in the child induction. In particular, no relation between the hook parameter and the child size is imposed.

Let \(B_m\) be one coordinate sweep on \(m\) positions, for \(m\) a power of two, and put \[H_\xi=\log D_\xi,\qquad E_m(\xi;p)=\log\bigl(D_\xi\operatorname{Tr}_\xi|B_m|^p\bigr), \qquad j_m(l)=l\log(m/l).\] We set \(j_m(0)=0\), \(H_\varnothing=0\), and \(E_m(\xi;p)=-\infty\) when the trace vanishes. All traces are unnormalized. A partition \(\eta\) lies in the \(q\)-hook if \(\eta_{q+1}\le q\). Thus this definition includes the empty partition.

In particular, taking \(\theta=1/2\), \(c=1/100\) and \(q\le n^{1/16}\) gives the inverse-grid estimate with its full stated error and its additive child allowances. Section 6 also derives this specialization through its ordered density product.

The common recurrence exposes the child-dimension penalty and mark entropy before a budget is chosen. It does not by itself supply the sparse estimate or the scale comparison needed to close an induction. We begin the later bounds with named objects, whose budget still prescribes a signed occurrence. Its direct deduction from the first theorem fixes the scope; the rest of that section develops a second proof through crowded cells and coefficient integrals.

A budget for named objects

We use representation theory and a trace induction for a whole sweep of switches. Two features of the induction are:

• For a trace test one can use a mixture of named objects and tensor spins, not just the regular representation or just spins. The named objects will have to return to the very same cells of a rectangular array. There is an angle saving on the remaining spin space.

• It suffices to propagate bounds which can be quite large, but must be small compared with the dimension of an irrep. It helps in doing this to give the named objects a budget per object which decreases at low density (but is clipped at zero).

We use partitions with irreps \([\lambda]\), dimensions \(D_\lambda\), and transposed diagrams \(\lambda^{\rm t}\). For partitions of separate sizes we denote induction from the Young subgroup by a product notation such as \(\mu*\xi\), also used with more factors; membership denotes occurrence. Transposing all diagrams preserves occurrence. Throughout, diagrams of size zero and their representations are allowed.

If \(z\) is a list of nonnegative numbers with total \(u\), put \[\mathcal S(z)=\sum_{j:z_j>0} z_j\log(u/z_j);\] we allow empty lists and use zero when the total is zero. With two partitions as arguments this takes the concatenated list of row lengths, not the entropy of each separately.

We bound matrices for a single sweep in terms of a spin and named-object budget. Define \[ W_n(\lambda)=D_\lambda\operatorname{Tr}|B_n([\lambda])|^{2h}, \tag{36}\] where we will choose an absolute integer \(h\), possibly very large. Here \(|\cdot|\) takes the operator absolute value.

Fix the numerical budget parameters \[\delta=.00001,\qquad \beta_n=.18-\frac{.04}{1+\log n}.\] Write \([x]_+=\max\{0,x\}\) and define \[ R_n(z)= z[\,\delta\log n-\log(n/z)-C_0\,]_+ \qquad(0\le z\le n), \tag{37}\] with \(R_n(0)=0\) and a sufficiently large absolute \(C_0\) to be fixed.

Signed-spin representations

For the separate proof, we recall the representation facts used below:

• We use the regular representation/Fourier formula (in particular Plancherel), Schur-Weyl duality with polynomial \(GL\) irreps, the Young branching, Pieri and Littlewood-Richardson rules, the hook and Weyl dimension formulas, and unitary Schur orthogonality. Recall that if \(\lambda\) occurs in a two-factor product, it contains each factor’s diagram. When a diagram contains another as upper left subdiagram, the bigger occurs in the product of the smaller with some diagram of the remaining size, by branching.

• We use the polynomial irreps of \(GL(q)\) also as \(U(q)\) types. Their dimensions, on degrees bounded by \(n\), are \(\exp(O(q^2\log(n+2)))\) when \(q\le n\). The matrix of a positive diagonal with descending spectrum \(y_1,\ldots,y_q\) on a type with partition \(\alpha\) has norm \(\prod_j y_j^{\alpha_j}\). We can use the Hilbert spaces as in unitary Schur-Weyl duality; this formula follows, for instance, by highest weight and dominance of the weights by the highest weight. A spectrum including zeros follows by continuity.

Here are two useful descriptions of spin types. Take a space \[V=\mathbb C^q_+\ \oplus\ \mathbb C^q_-\] of plus and minus spins, and take \(G=U(q)\times U(q)\), acting by its two defining representations. Let position permutations act on tensor slots by graded permutations: the minus slots incur signs, that is, an interchange of two minus spins has an additional \(-1\). This commutes with \(G\). On \(V^{\otimes u}\), the \(G\)-types are indexed by pairs \(w=(\alpha,\gamma)\) of partitions with at most \(q\) parts each, with total size \(u\). We use the full isotypic spaces. As a module over the symmetric group, the space of such a type consists of copies of \(\alpha*\gamma^{\rm t}\), the number of copies being the dimension of the \(G\)-irrep. Indeed, one takes plus and minus counts, uses ordinary Schur-Weyl on both, with the sign twist on the latter positions, and induces.

For \(u\le n\), any \(\eta\) in \(\alpha*\gamma^{\rm t}\) satisfies \[ \log D_\eta\ \ge\ \mathcal S(\alpha,\gamma)-C q^2\log(n+2) \qquad (q\le n). \tag{39}\] Here and in coarse errors, \(C\) denotes an absolute constant that may change. To see this, one can reach \(\eta\) from \(\alpha\) by adding at most \(q\) vertical strips (since \(\gamma^{\rm t}\) occurs in a product of that many column diagrams). And similarly one can reach \(\eta^{\rm t}\) from \(\gamma\). In particular \(\eta\) lives in the \(q,q\) hook, and its long row and column lengths agree with those of \(\alpha,\gamma\) within \(O(q)\) each. In the dimension formula, use at most \(O(q^2)\) factors bounded by \(2n\) for the square region, and in a row protruding to the right of it bound hook lengths by the remaining row counts (including the current box), each increased by \(q\); similarly below the square by columns. Their factorial products are bounded by the products of row factorials of \(\alpha\) and of \(\gamma\), times \(\exp(C q^2\log(n+2))\). This and the factorial estimate for entropy give (39). In the other direction, total dimension of \(\alpha*\gamma^{\rm t}\) is at most \(\exp(\mathcal S(\alpha,\gamma))\), by the dimension formula for induction and the elementary factorial-quotient bounds for the two Specht dimensions and for multinomial coefficients. Thus multiplicities in a spin type, including \(G\)-dimensions, cost at most \(\exp(C q^2\log(n+2))\).

Sparse path cancellation

We give first a separate lemma for those representations for which an estimate using few cards will suffice. Take any fixed \(c\in(0,1)\). For all sufficiently large \(n\), if \(1\le k=n-\lambda_1\le n^{1-c}\), we have \[ \|B_n([\lambda])\|\ \le\ \exp\{-c' k\log(n/k)\} \tag{40}\] with some fixed \(c'>0\). Constants in this lemma can use \(c\).

Use the action on \(k\)-tuples of distinct positions. The irrep occurs here but not with fewer positions, by branching. For tuples \(x,y\), for \(J\subseteq\{1,\ldots,k\}\), write \(K_J(x,y)\) for \(n^{|J|}\) times the probability that the sweep takes \(x_J\) to \(y_J\), and put \[L(x,y)=\sum_J(-1)^{k-|J|} K_J(x,y).\] For fixed \(x_i,y_i\) a path in the switch network is specified: each refreshed bit has its required final value. If one of the paths in \(x,y\) does not even share a switch with any other, \(L=0\). Indeed it costs \(1/n\) in all the relevant sweep probabilities, with independent switches. On the other hand, \(L\), as a kernel with multiplier \(n^{-k}\) on the distinct tuples, gives the action of the sweep on \([\lambda]\) after compression to it: the proper-subset terms vanish, as their ranges or co-ranges involve fewer entries. Thus we will bound the op norm of the matrix \(n^{-k}L\). If \(k=1\) the lemma is immediate, so take \(k\ge 2\).

We use the dyadic cells on starts \(x\) in which bits not yet swept are fixed; on the end positions \(y\) use the corresponding cells for the reverse order. Each is a family nested as a binary tree. Put \[p_*=(k/n)^{1/10}.\] Call a position in the tuple crowded if it lies in a cell containing at least two of the entries and with entry density at least \(p_*\). A tuple is bad if at least \(k/4\) entries are crowded. For a noncrowded start entry \(i\) there is a useful first-contact bound: \[ \sum_{j=1}^d 2^{-(j-1)} \#\left\{\begin{array}{l} \text{other starts whose bits remaining}\\ \text{after step }j\text{ agree with entry }i \end{array}\right\}\ \le\ 2 d p_*. \tag{41}\] Indeed a contributing cell has size \(2^j\).

Think of \(n^{-k}K_J\) in a row as generating paths: actual shuffled paths for the entries in \(J\), and independent uniform ends (with the corresponding paths) for the others, even allowing nondistinct ends until restricting the matrix. For any order of inspecting paths, the conditional probability the next path of a noncrowded start will hit any earlier paths, meaning share any switch, is bounded by (41). Until its first hit it makes free uniform choices. For shuffled cards, the earlier shuffled paths condition only their own visited switches. And at layer \(j\) a possible hit with any fixed earlier path requires the first \(j-1\) generated bits to agree with that path at the given switch, as well as agreement on the unswept bits other than bit \(j\), just as counted in (41).

If \(x\) is not bad, the row probability of all vertices of the path contact graph being nonisolated costs \(\exp(-\Omega(k\log(n/k)))\), uniformly for each \(J\). For clarity, inspect in an independently random order. Given this graph without isolated vertices, at least \(3k/4\) noncrowded starts each have probability at least \(1/2\) of an earlier neighbor, so with probability bounded below there are at least \(k/8\) such hits. In any inspection order, conditional hit bounds and a union bound over choices give probability at most \(2^k(2d p_*)^{k/8}\) for this many hits. The column statement with the reverse sweep and nonbad \(y\) is identical. This proves exponentially small absolute row or column sums on these parts of \(L\), since factors \(\exp(O(k))\) from summing over \(J\) are affordable. Arbitrary absolute row and column sums are bounded by \(2^k\).

We also need a dispersion observation: from any \(x\), the absolute mass from each \(n^{-k}K_J\) to bad distinct \(y\) is \(\exp(-\Omega(k\log(n/k)))\). We include the details because the same unfavorable starts cannot just be treated as dispersed. For a fixed set \(E\) of end positions, occupation counts here satisfy the upper tail bound from independent cards with success probability \(|E|/n\), in the sense of the ordinary Chernoff estimate. For positive common test factors on end positions we have a product upper bound on expectation by single-card expectations. To see this for \(J\), work backwards through the layers: for tracked entries occupying both inputs of a switch, the product of the two test factors on outputs is at most the square of their arithmetic mean. Thus products propagate as upper bounds with the common factor averaged at each switch. At the start the single-path propagations are all equal, since one sweep sends each start to a uniform end. This gives the needed generating function domination, also after including the independent entries outside \(J\).

If \(y\) is bad, take the maximal witnessing cells (having the density and count conditions). They are disjoint; there are \(l\le k/2\) of them, with total volume at most \(k/p_*\), and at least \(\max(k/4,2l)\) of the entries in their union. There are at most \(\binom{2n}{l}\) choices. Using the just-proved count bound, the costs for a given \(l\) are bounded by \[\binom{2n}{l} \left(\frac{C k}{n p_*}\right)^{\max(k/4,2l)}\] for an absolute \(C\). These sum to the claimed dispersion estimate; for example, in the combinatorial prefactor the logs are bounded by \(l\log(n/k)+O(k)\), absorbed with room in the other exponent.

Partition \(L\) according to bad starts and ends. On the bad-bad block the dispersion estimate is available, and on the other blocks we have the nonbad estimates using cancellation of isolated paths. The row/column sum bound for operator norm (using the coarse \(2^k\) for the opposite estimate if necessary) proves (40).

We will also use the zero bound when \(\lambda\) has more than \(n/2\) rows. Indeed a layer is the projection averaging a product of pair groups. Only diagrams in the product of \(n/2\) two-box row diagrams can survive, so this follows from Pieri.

An angle estimate on an incomplete rectangle

We state the form of the estimate to be used in the induction. Consider \(n=b s\) slots in \(b\) rows, \(s\) columns. In the application both \(b,s\) are within a factor two of \(\sqrt n\). Let \(m\) slots be holes, arbitrary but fixed for the estimate, and use \(V\) as above on the \(u=n-m\) remaining slots, with \(q\le n\). Take:

1. projections \(E,F\) specifying \(G\)-type in each row, respectively each column, of non-hole slots (each row and column can have its own type),

2. a projection \(Q\) to one global \(G\)-type \((\mu,\nu)\), with \(S=\mathcal S(\mu,\nu)\).

The row and column projections are for actions constant in the respective row or column. Write \(S_H,S_K\) for sums of the type entropies in the specification for the rows, columns, respectively. Then \[ \| E Q F\|^2 \le \min\left(1,\ \exp\{S_H+S_K-S+C m+C(1+b+s)q^2\log(n+2)\} \right). \tag{42}\] These type spaces and \(Q\) do not require coordinates to be arranged contiguously for rows or columns. Using graded slot order instead of ordinary order to regroup the factors also respects the type definitions, by block-diagonality for plus/minus. In particular \(E,F\) commute with \(Q\).

Here is a proof. For a row with \(v>0\) slots after omitting holes and type \(w=(\alpha,\gamma)\), take a block-diagonal density matrix \(A_i\) on \(V\) with block spectra given by \(\alpha/v,\gamma/v\). Then the projection to the type is bounded above in positive order by \[ \exp\{\mathcal S(w)+C q^2\log(n+2)\}\ \int_G (g A_i g^*)^{\otimes v}\,dg. \tag{43}\] Here \(dg\) is normalized Haar measure. Indeed, on that type the integral is scalar, with the scalar given by taking trace on the \(G\)-irrep and dividing by its dimension. The density tensor action has the standard polynomial action and is the same on all copies; this holds also for singular densities by continuity. By highest weight this trace is at least \(\exp(-\mathcal S(w))\), proving (43). Use arbitrary densities on fully holed rows. We have the analogous bounds with column densities \(A'_j\).

Let \(w_i,w'_j\) be the row and column types, including the trivial type on a fully holed line, and choose one sufficiently large absolute \(C\) in the local bounds. Put \[\begin{aligned} c_i&=\exp\{\mathcal S(w_i)+Cq^2\log(n+2)\},\\ d_j&=\exp\{\mathcal S(w'_j)+Cq^2\log(n+2)\},\\ c_H&=\prod_i c_i,\\ c_K&=\prod_j d_j. \end{aligned}\] For a fully holed line the projection and tensor power are scalar one, so the same coefficient, which is at least one, is valid. Let \(\mu_H,\mu_K\) be the products of normalized Haar measures on \(G\), with one factor per row and column, respectively. For orientation tuples \(\mathbf g=(g_i)_i\), \(\mathbf h=(h_j)_j\), put \[\begin{aligned} R_{\mathbf g}&=\bigotimes_{(i,j)\text{ occupied}}g_i A_i g_i^*,\\ C_{\mathbf h}&=\bigotimes_{(i,j)\text{ occupied}}h_j A'_j h_j^*. \end{aligned}\] The parity-preserving graded regrouping identifies these positive tensors with products of the local row or column tensor powers. Tensoring (43) within each family gives \[E\preceq c_H\int R_{\mathbf g}\,d\mu_H,\qquad F\preceq c_K\int C_{\mathbf h}\,d\mu_K.\] Both measures are probabilities, and \(c_H=\exp\{S_H+Cbq^2\log(n+2)\}\), \(c_K=\exp\{S_K+Csq^2\log(n+2)\}\). Apply Lemma 19 with its positive operators equal to \(E,F\) and its middle operator equal to \(Q\). Since \(E,F\) are projections, it gives exactly \[\|EQF\|\le\sqrt{c_Hc_K}\, \sup_{\mathbf g,\mathbf h} \|R_{\mathbf g}^{1/2}Q C_{\mathbf h}^{1/2}\|.\] The square roots of these tensor products are the tensor products of the individual density square roots. Thus, after the displayed factor \(\sqrt{c_Hc_K}\), it suffices to bound \[ \left\| \left(\bigotimes_{\rm slots} A_i^{1/2}\right) Q \left(\bigotimes_{\rm slots} {A'}_j^{1/2}\right)\right\| \tag{44}\] uniformly in orientations of the densities, absorbing the \(G\)-actions into the notation.

Let \(M=b^{-1}\sum_i A_i\). Use \(Y=(M+\rho I)^{1/2}\), \(\rho>0\), to flatten on the left in (44). On the global type, \(Y^{\otimes u}\) has norm at most \[(1+2q\rho)^{u/2}\exp(-S/2).\] This follows from the highest-weight density estimate in Lemma 8, after normalizing \(M+\rho I\) by its trace \(1+2q\rho\). Let \(\pi\) be the compact carrier representation for \((\mu,\nu)\). The operator \(Y^{\otimes u}Q\) acts as \(\pi(Y)\) on that carrier and as the identity on its multiplicity space, and is zero on all other types. Lemma 21 therefore gives \[Y^{\otimes u}Q=\int_G f(g)g^{\otimes u}\,dg, \qquad \int_G|f(g)|\,dg \le(\dim\pi)(1+2q\rho)^{u/2}e^{-S/2}.\] The carrier dimension is at most \(\exp(Cq^2\log(n+2))\).

Insert \((Y^{-1})^{\otimes u}\) on the left of that integral to get \(Q\). We bound the remaining norm in the integrand, on the squared scale, by a product over cells of \[\operatorname{tr}\big( Y^{-1} A_i Y^{-1}\, g A'_j g^*\big)\] by Hilbert-Schmidt on each cell. On the full rectangle these nonnegative quantities sum to at most \(n\), by flattening and the unit traces on the other side. Thus the product over the \(u\) cells is at most \((n/u)^u\le \exp(Cm)\), with empty products harmless. This proves the desired bound on (44) by letting \(\rho\) tend to zero, and gives (42).

The independent trace induction

We now complete the separate proof using the preceding crowded-cell sparse estimate (40), the coefficient-integral proof of (42), and a three-regime closure with one fixed \(C_0\).

For this proof, fix \[a=.02,\qquad q_n=\lfloor n^a\rfloor,\qquad c=\delta/40.\] We take (40) available up to \(k=n^{1-c}\). We use constants and asymptotic estimates below independent of \(h\).

Proving it for \(\mu,\nu\) of lengths at most \(q_n\) at any sufficiently large \(n\) suffices at that size. Indeed, if either has more rows, trim each after \(q_n\) rows, sending \(w_*\) boxes in total to the named count. By containment and associativity, there is an occurrence with the trimmed \(\mu,\nu\) and some new partition of size \(m+w_*\). The entropy at the old size \(n-m\) exceeds the trimmed entropy by at least \(w_*\log q_n\), since trimmed row counts were each at most \((n-m)/q_n\), and separating out the trimmed counts only lowers the contribution from the kept counts upon renormalizing the latter. On the range in (37), \(R_n\) can increase by at most \(w_* (\delta\log n+1)\). This proves the sufficiency for large \(n\).

We will work with sufficiently large dyadic \(n\), assuming (38) for smaller sizes. Consequently, all estimates using subproblem sizes are allowed to use any lengths for spin partitions there. Also, regardless of the right-hand side in (38), in the range of (40) we can make \(W_n(\lambda)\le 1\) for nontrivial irreps, by taking \(h\) large depending on \(c\), since \(D_\lambda\le n^k\). And this inequality holds already above height \(n/2\). We explain the treatment of finite sizes after the induction estimates.

Use \(b\) rows of size \(s\), with \(b,s\) powers of two and within a factor two of \(\sqrt n\). Split a sweep at this scale. We have sweep operators supported on \[H=(\mathfrak S_s)^b,\qquad K=(\mathfrak S_b)^s,\] using rows and columns, respectively; inside a group each acts by independent smaller sweeps. The order will not matter to the estimates. In the product representing \(B_n\), apply the Araki-Lieb-Thirring trace inequality for positive matrices (at power \(h\)). Thus a trace of singular values to \(2h\) on any representation is bounded above by \[ \operatorname{Tr} A_H A_K, \tag{45}\] where \(A_H,A_K\) are the corresponding tensor products within \(H,K\) of the positive group-algebra elements from the subproblem singular squares taken to \(h\) (using \(BB^*\) or \(B^*B\) as appropriate). In particular, on a factor of size \(s\), the regular traces by irrep of that positive element are \(W_s\). Positivity here and below can equivalently be defined by the regular representation.

Fix an occurrence in (38), with lengths now at most \(q=q_n\), and write \(S=\mathcal S(\mu,\nu)\). Use a representation \(X\) with \(m\) slots taken by distinct named objects, one of each name, and the other slots carrying \(V\) as above with this \(q\). Names can be treated as additional plus objects for permuting the factors (no sign cost for them). Use the whole Hilbert space allowing the names in any slots and order, with each fixed placement carrying \(V^{\otimes(n-m)}\). Use \(Q\) selecting global type \((\mu,\nu)\); it fixes placements of names. It commutes with the position shuffle. This space with \(Q\) contains at least \(D_\tau\) copies of \([\lambda]\). This follows from inducing from the name and spin subsets and the description of spin types; in particular the names alone carry a regular representation on their slots. And \[ \frac{D_\lambda}{D_\tau} \le \binom{n}{m}\exp(S) \tag{46}\] by the dimension upper estimates for induction. It follows from (45) that \(W_n(\lambda)\) is bounded by \(D_\lambda/D_\tau\) times \[\operatorname{Tr}_X Q A_H A_K .\]

Here we analyze this last trace, which need not single out \(\tau\) or \(\lambda\). Expand in group elements. For a contribution with the \(m\) names in cells \(T\), \(|T|=m\), the product of a row and a column permutation must fix these individual cells, not just setwise. Hence each of the two permutations must fix these cells pointwise. The trace contribution for \(T\) is therefore \(m!\) times \[ \operatorname{Tr} Q\ a_H a_K \tag{47}\] on the remaining spins. In this expression:

• \(a_H\) is given by using in each row only the group-algebra coefficients on the subgroup fixing the named positions pointwise, acting by graded permutations on the other spins. Likewise \(a_K\) in the columns.

• These give positive operators. Indeed coefficient restriction of a positive element to a subgroup is positive, for instance by taking a principal submatrix. Each commutes with global \(G\) and hence with \(Q\). Within its family of rows or columns, each can be treated in tensor product order by using graded regrouping of tensor factors. Such regroupings intertwine the position and spin-type descriptions above; the graded signs track only the two spin summands, which are preserved by the \(G\) actions. Thus, for example, its trace estimates on specified types in that family can use ordinary products of the estimates.

Local stabilizer traces

We give the local trace bound needed for (47). In a row, write \(r=|T\cap\text{row}|\). For the part of its operator on a \(G\)-type \(w_i=(\alpha_i,\gamma_i)\) on the \(s-r\) slots, put \(S_i=\mathcal S(w_i)\). Then the trace of this positive part is bounded by \[ \frac{1}{(s)_r} \exp\left\{ -(1-\beta_s) S_i + R_s(r) + C (q^2+\sqrt{s})\log(n+2) \right\}, \tag{48}\] where \((s)_r=s!/(s-r)!\).

For details, consider an \(\eta\) in \(\alpha_i*\gamma_i^{\rm t}\). Its block of the coefficient restriction only gets contributions from Fourier components in size \(s\) that extend \(\eta\) upon restricting to \(\mathfrak S_{s-r}\). This follows immediately also by viewing coefficients of Fourier components as matrix coefficients and restricting them. Keep just those components in size \(s\). A diagram extending \(\eta\) here occurs in \(\eta*\xi\) for some \(\xi\) on \(r\) slots, so the induction hypothesis bounds each regular trace from these components by \(\exp(\beta_s S_i+R_s(r))\). Coefficient restriction changes the total regular trace of the kept positive element by the group order ratio \(1/(s)_r\), using the identity coefficient. Consequently this bounds the trace on the \(\eta\)-block after multiplying by \(D_\eta\), and allowing also the number of kept partitions, at most \(\exp(C\sqrt{s}\log(n+2))\). But \(D_\eta\) itself has lower estimate (39), and the multiplicities to be included on the spin representation, as well as enumerating its \(\eta\) here, are absorbed in the displayed error. This proves (48). This argument pays only for diagrams which can go through the type and the \(r\) other slots. In particular, the small named-object budget in (38) applies here even if \(r\) is just a local count and the global count is much larger.

Within (47), take a type specification \(E\) for the rows and \(F\) for the columns as in (42). The operators \(a_H,a_K\) break into positive parts according to their own families’ specifications, since they commute with the family actions of \(G\). Also, \(Q\) commutes with the types of either family. By (48), the traces of the two corresponding parts are bounded on the exponential scale using \[-(1-\bar\beta)(S_H+S_K) \quad\text{in their product},\qquad \bar\beta=\max(\beta_s,\beta_b),\] besides the falling factorials, \(R\) terms and errors, where \(S_H,S_K\) are sums of the \(S_i\)’s and the analogous column entropies. One more factor in bounding (47) is at most \(\|E Q F\|^2\): one can use eigenvectors of the positive parts and insert \(Q\) again since the operators commute with it. Combining (42) with the traces, we can replace the exponent just shown by \[ -(1-\bar\beta) S + C m + C(1+b+s)q^2\log(n+2). \tag{49}\] Indeed if the sum entropies reach \(S\) the trace term suffices, and otherwise the squared angle makes up the difference with rate 1.

Counting the named positions

All errors here other than \(O(m)\), and enumerations of the type specifications, cost \(O(n^{.85})\) in the exponent for large \(n\). For example (48) is used on \(O(\sqrt n)\) fibers, and even using the partition count per fiber on this scale is affordable. Thus with \(r_i=|T\cap\text{row }i|\) and \(t_j=|T\cap\text{column }j|\), equations (46)–(49) give \[ \begin{split} W_n(\lambda)\ \le\ & \binom{n}{m} \exp\{\,\bar\beta S+C_1 m+C_1 n^{.85}\,\}\\ &{}\times m!\sum_{T:\, |T|=m} \frac{\exp\{ \sum_i R_s(r_i)+\sum_j R_b(t_j)\}} {\prod_i(s)_{r_i}\prod_j(b)_{t_j}}, \end{split} \tag{50}\] with an absolute \(C_1\). We emphasize that this constant does not use \(C_0\) in (37). The elementary falling factorial bounds \((s)_r\ge s^r\exp(-C r)\) and \(m!\binom{n}{m}\le n^m\) can be used to treat the last line simply as an expectation over uniform \(T\), with at most \(\exp(Cm)\) extra factor. The \(\binom{n}{m}\) on the first line, which could still be expensive, is why we propagate with the particular \(R\) in (37).

Closing the budget in three regimes

We verify (38) from (50). First suppose \[m\ge n^{1-\delta/4}.\] If \(n\) is sufficiently large (permitting dependence on \(C_0\)), then \(\delta\log s-\log(n/m)-C_0>0\), and analogously for \(b\). Hence for instance \[R_s(r_i)\le r_i\left(\delta\log s-\log(n/m)-C_0+ [\log(r_i/(m/b))]_+\right).\] The extra positive-part terms for both families together can be paid for in (50) with cost \(\exp(Cm)\). To see this, compare uniform \(T\) with iid cells before requiring distinctness, at likelihood cost bounded by \(\exp(Cm)\). Row and column counts of these iid cells arise independently. The row profile probability is bounded by \(\exp(-\sum r_i\log(r_i/(m/b)))\), and likewise for columns. The negative-log entries discarded in using the positive part cost \(O(m)\) in each family (by \(z\log(1/z)\le C\) applied to ratios). And enumerating profiles costs \(\exp(Cm)\) here. Thus the budget terms on the last line cost in the exponent at most \[m(\delta\log n-2\log(n/m)-2C_0)+C m,\] with constants independent of \(C_0\). Using \(\log\binom{n}{m}\le m\log(n/m)+m\), (50) now fits into (38), including its \(R_n(m)\), by fixing \(C_0\) sufficiently large and taking \(n\) sufficiently large. The size errors \(C_1 n^{.85}\) in this case can be treated just as \(O(m)\).

Next, if \(m<n^{1-\delta/4}\) but \(S\ge n^{1-\delta/6}\), we can use crude cost \(O(m\log n)\) for the budget and binomial terms together. All overheads then fit in \((\beta_n-\bar\beta)S\); the coefficient difference is, in particular, at least a constant times \(1/(1+\log n)\) for large \(n\).

In the remaining case (\(m<n^{1-\delta/4}\) and \(S<n^{1-\delta/6}\)), one of the entries of \((\mu,\nu)\) differs from \(n-m\) by \(O(n^{1-\delta/6})\), just by entropy. Thus because \(\lambda\) contains both \(\mu\) and \(\nu^{\rm t}\), either it is above the height cutoff, or its level \(n-\lambda_1\) is in the sparse range used for (40), for large \(n\). This gives (38) by the sparse bound in (36) or the zero bound, the trivial irrep also satisfying (38).

This closes the trace induction. To make the choices with fixed \(h\) explicit as regards dependencies, choose \(C_0\) to meet the absolute constant requirements in the verification, use the arguments just given (and the trimming observation) above some absolute finite size, and take \(h\) to meet the requirement for the sparse bound and to give (38) on all needed finite sizes. The comparisons above for sufficiently large \(n\) can choose their thresholds independently of further increases in \(h\). For the finite sizes a fixed such \(h\) exists: in any nontrivial irrep the sweep has strict contraction. Indeed, it is a product of orthogonal projections, and equality in norm would require a common fixed vector. The pair interchanges in the coordinate lines generate the symmetric group. We include subproblems of one slot as trivial. These choices prove (38) with absolute constants.

Dimension savings and full-deck mixing

We show why the propagated budget suffices to mix, in particular that it handles shapes with many rows and also many columns. Continue to use \(c=\delta/40\). Small levels and diagrams above the height cutoff are already handled. For any remaining diagram \(\lambda\), take the following occurrence for use in (38):

• take the first up to \(q_n\) rows as \(\mu\);

• below them take the diagram within the first \(q_n\) columns, transposed, as \(\nu\);

• the remaining southeast boxes, number \(m\), can be assigned a partition factor on \(m\) slots.

More precisely, let \(\eta\) be the hook portion kept here. We have \(\eta\) in \(\mu*\nu^{\rm t}\); this uses adjoining the diagram \(\nu^{\rm t}\) under upper rows whose lengths cover its width (or follows directly by the Littlewood-Richardson rule). And since \(\lambda\) contains \(\eta\), some \(m\)-slot extension suffices. In particular branching and (39) give \[\log D_\lambda\ge S-C q_n^2\log(n+2), \qquad S=\mathcal S(\mu,\nu).\] If \(m\ge n^{1-2\delta}\), we also have \(\log D_\lambda\ge (a/2)m\log n\) for large \(n\). Indeed the remaining boxes alone form, upon translation, a diagram of size \(m\) with every row and column length at most \(n/q_n\). We have at least its dimension in the tableau count for \(\lambda\), just by filling it after the hook part. The estimate follows by the hook and factorial formulas.

Here at least one of \(m,S\) is \(\ge n^{1-2\delta}\) for large \(n\). Otherwise we would again be above the height cutoff or in the sparse range (recall that the remaining irreps under discussion have level greater than \(n^{1-c}\)). Thus \(D_\lambda\) is at least \(\exp(n^{.9})\) for large \(n\), and all additive errors in these dimension estimates are harmless. Since \(R_n(m)=0\) unless \(m\) is large enough for the second estimate, and \(\delta\) is tiny compared with \(a\), we see that \[W_n(\lambda)\le D_\lambda^{1/2}\] on all these remaining diagrams, for sufficiently large \(n\). In particular the sweep on them has norm at most \(D_\lambda^{-1/(4h)}\).

Use now an absolute constant number \(L\) of sweeps, repeating in the same order. In squared \(L^2\) distance of density from uniform on the permutation group, Plancherel uses, for each nontrivial irrep, the squared Hilbert-Schmidt norm times \(D_\lambda\), and thus we can bound by summing \[D_\lambda^2\,\|B_n([\lambda])\|^{2L}.\] On the large dimensions just treated, this gives \(o(1)\) in total for \(L\) sufficiently large, even allowing the partition count \(\exp(O(\sqrt n\log(n+2)))\). On the sparse range \(1\le k\le n^{1-c}\), use (40), \(D_\lambda\le n^k\), and for example \(2^{O(k)}\) partitions per level. This sum also tends to zero for large absolute \(L\). This proves in particular the required TV upper bound by \(O(d)\) steps, from every fixed initial order.

The two quantitative bounds

The bound is valid throughout the displayed range; it gives a contraction when \(c\log(n/k)>C\).

Here is the second target. Fix \[\beta=\tfrac1{10},\qquad \delta=10^{-3},\qquad \alpha=10^{-6},\] with \(\alpha\) decreased further if needed, and set \(q_n=\lfloor n^\delta\rfloor\). A \(q\)-hook diagram has no cell \((q+1,q+1)\). For a diagram \(\eta\) of size \(N\), let \(a\) be its Durfee index and use its Frobenius parts \[a_i=\eta_i-i+1,\qquad b_i=\eta'_i-i\qquad(1\le i\le a).\] These parts sum to \(N\). Define \[F(\eta)=\sum_{i:a_i>0}a_i\log(N/a_i) +\sum_{i:b_i>0}b_i\log(N/b_i), \qquad F(\varnothing)=0,\] and the clipped remainder cost \[ G_n(t)=t\max\{0,\alpha\log n+\log(t/n)\}\quad(0<t\le n), \qquad G_n(0)=0. \tag{52}\]

The minimum includes the empty diagram. Equivalently, the moment is bounded by the cost of every permitted hook subdiagram. This quantifier will allow us to use the inherited subdiagram in each child block, after shrinking its hook parameter when necessary. The moment proof uses the norm estimate at \(k\le n^{1-\alpha/16}\). All notation in the rest of this section is local; traces and tensor norms remain unnormalized.

Ordinary tensors and the backward split

We first prove Proposition 25. Split the sites into two halves of size \(m=n/2\). The intermediate object will be a probability law on the half excitation counts \(l_i\) and half defects \(j_i\), \(i=0,1\). We will show that \(l_0\) is concentrated around \(k/2\) and that the loss \(k-j_0-j_1\) has a small upper tail. Those two facts will close the norm induction.

The tensors in this part carry the ordinary permutation action. The signed color action used for Proposition 26 will be introduced after the norm proof. All tensor words are orthonormal, so the norms below are counting norms, with no probability normalization depending on the excitation sector. For the sweep application fix \(n=2^d\) and \(\lambda=(n-k,\xi)\) with \(2\le k\le n/2\).

Let \(q\ge1\) be an integer, let \(V=\mathbb C^q\), with orthonormal basis \(e_1,\ldots,e_q\), and put \(\mathcal A=\mathbb C e_0\oplus V\). For a finite set \(X\) of sites write \(\mathcal H_X=\mathcal A^{\otimes X}\), and let \(\mathcal H_{X,l}\) be the span of words with exactly \(l\) entries in \(V\). A permutation \(g\) of \(X\) sends the letter at \(x\) to \(g(x)\). In particular it introduces no signs. We use the zero space when \(l<0\) or \(l>|X|\).

For \(c\in\{1,\ldots,q\}\), let \[a_{x,c}=|e_0\rangle\langle e_c|_x,\qquad L_{Y,c}=\sum_{x\in Y}a_{x,c}\quad(Y\subseteq X).\] Thus \(L_{X,c}:\mathcal H_{X,l}\longrightarrow\mathcal H_{X,l-1}\). Its adjoint for the stated norms is the restriction of \(\sum_{x\in X}|e_c\rangle\langle e_0|_x\) in the reverse direction. More generally its half version has source and target \[L_{Y,c}:\mathcal H_{Y,l}\otimes\mathcal H_{X\setminus Y,r} \longrightarrow \mathcal H_{Y,l-1}\otimes\mathcal H_{X\setminus Y,r},\] with adjoint \(\sum_{x\in Y}|e_c\rangle\langle e_0|_x\) in the reverse direction. Conjugation gives \(\rho(g)L_{Y,c}\rho(g)^{-1}=L_{gY,c}\). All the \(a_{x,c}\) commute: on different sites they act on separate factors, while on one site either product of two of them is zero. Hence all lowerings just defined commute. The global case is the standard diagonal matrix-unit action (Etingof et al. 2011, Theorem 4.55).

The norms of these maps are also explicit. On a nonzero displayed sector, so \(0\le r\le|X\setminus Y|\), and for \(1\le l\le |Y|\), \[\|L_{Y,c}\|_{\mathrm{op}}^2=l(|Y|-l+1),\] and the map is zero at \(l=0\). To see this, fix the sites and values of all letters other than \(0,c\). If \(h\) sites carry \(c\), the remaining map is the incidence matrix from \(h\)-subsets to \((h-1)\)-subsets. It has \(h\) ones in each column and \(|Y|-l+1\) in each row. Cauchy–Schwarz gives squared norm \(h(|Y|-l+1)\), attained on constant vectors; maximizing at \(h=l\) gives the formula. It applies to the global map with \(Y=X\) and, when \(|X|=2m\), to a half map with \(|Y|=m\).

Here is the relation to the tuple realization and the multiplicities that will be retained below. If \(|X|=N\), fixing the \(l\) excited sites gives the ordinary induced representation \[\mathcal H_{X,l}\simeq \operatorname{Ind}_{S_{N-l}\times S_l}^{S_N} \bigl(\mathbf1\otimes V^{\otimes l}\bigr).\] The direct sum over the excited subsets has its orthogonal tensor norm. Ordinary Schur–Weyl duality (Etingof et al. 2011, Theorem 4.57 and Corollary 4.59) and the Pieri rule, the one-row Littlewood–Richardson case (Sam and Snowden 2012, sec. 2.10, equation (2.10.1)), give the unitary decomposition \[ \mathcal H_{X,l}\simeq \bigoplus_{\mu\vdash N}V_\mu\otimes\mathcal M_{\mu,l}, \qquad \mathcal M_{\mu,l}= \bigoplus_{\substack{\tau\vdash l,\ \ell(\tau)\le q\\ \mu/\tau\text{ a horizontal strip of size }N-l}} \mathbf S_\tau(V). \tag{54}\] Each pair \((\mu,\tau)\) in this sum has Pieri multiplicity one. The full Schur color module \(\mathbf S_\tau(V)\) is retained. The hook-content formula (Sam and Snowden 2012, sec. 3.6, equation (3.6.1), and §4.3) gives \[\dim\mathbf S_\tau(\mathbb C^q) =\prod_{(r,c)\in\tau}\frac{q+c-r}{h_\tau(r,c)}.\] Here \(h_\tau(r,c)\) is the hook length of the indicated cell. At \(l=0\) this is trivial induction and the empty partition contributes one copy of the trivial representation; at \(l=N\) it is identity induction. If \(\mu=(N-j,\xi)\) occurs, the horizontal-strip interlacing inequalities give \(\tau_r\ge\mu_{r+1}=\xi_r\). Consequently \(j=|\xi|\le l\).

For a global defect \(k\), take \(q=k\). The subspace of \(\mathcal H_{X,k}\) in which each of the letters \(1,\ldots,k\) occurs once is isometric to the counting-norm space on ordered injections: \[\mathbf e_{(x_1,\ldots,x_k)}\longmapsto \text{the word with letter \(c\) at \(x_c\) and \(0\) elsewhere}.\] This isometry intertwines the position actions. More generally, for a set \(A\) of distinct excited names let \(\mathcal I_{X,A}\) be the sector in which every name in \(A\) occurs once and no other excited name occurs. For \(c\in A\), the restriction \(L_{X,c}:\mathcal I_{X,A}\to\mathcal I_{X,A\setminus\{c\}}\) and its adjoint in the reverse direction act on counting-norm injection coefficients exactly as \[(L_{X,c}f)(y)=\sum_{z\in X\setminus y(A\setminus\{c\})} f(y\cup\{c\mapsto z\}),\qquad (L_{X,c}^*g)(x)=g(x|_{A\setminus\{c\}}).\] Thus the restricted squared norm is \(N-|A|+1\), the size of each deletion fiber; if \(c\notin A\), the restriction is zero. For a fixed assignment of the present names to two halves of size \(m\), the same formulas hold inside a half, with squared norm \(m-l+1\) when that half contains \(l\) names including \(c\). This identifies the operation with raw tuple deletion, including its adjoint and its normalization.

In \(\mathcal I_{X,[k]}\), the shape \(\lambda=(N-k,\xi)\) occurs with the minimum-slot multiplicity \(f^\xi\) from Section 1. It occurs on no sector \(\mathcal H_{X,l}\) with \(l<k\), also directly by (54). Each \(L_{X,c}\) intertwines \(S_N\), so it is zero on the entire \(\lambda\)-isotypic subspace of \(\mathcal H_{X,k}\). This proves the needed global cancellation with the tensor adjoints and norms fixed above.

Removing prefactor losses

The tail estimate now closes the induction without accumulating a loss at each split. Write \[W_n(\lambda)=\|B_n\|_\lambda^2, \qquad h_*=\frac1{20},\qquad c_{\rm s}=\frac1{64}.\] We will choose an absolute \(M_*\ge1\) and prove the stronger bound \[ W_n(\lambda)\le h_*\left(\frac{M_*k}{n}\right)^{c_{\rm s}k} \qquad(2\le k\le n/2). \tag{64}\] This is the potential \(V(n,k)=k\log(n/k)-Ak+B\mathbf1_{\{k>0\}}\) written with \(M_*=e^A\) and \(h_*=e^{-c_{\rm s}B}\); as usual \(V(n,0)=0\). The fixed factor \(h_*\) supplies a margin when both halves retain positive defect.

If \(W_n(\lambda)=0\), the estimate is immediate; otherwise use the component law above. Suppose the proposed right side in (64) is less than one; otherwise contractivity proves the estimate. Put \(y=k/n\) and \[D=\frac{(l_0-k/2)^2}{k},\qquad u=k-j_0-j_1,\qquad b=\#\{i:j_i>0\}.\] We will choose \(M_*\) so that this nontrivial case has \(y<\delta_*\), where \(0<\delta_*\le1/8\). Then \(k<m/4\), so every child defect \(j_i\ge2\) lies in the range of the induction hypothesis. The trivial child has norm one, and a child with defect one has norm zero. For a component with neither child defect equal to one, the product of the two child bounds divided by the proposed parent bound is exactly \[ h_*^{b-1}(M_*y)^{-c_{\rm s}u} \exp\left(c_{\rm s}\sum_{i=0}^1j_i\log(2j_i/k)\right), \tag{65}\] with zero summands at \(j_i=0\).

The exponent in this ratio has a simple uniform bound. Using \(\log z\le z-1\) and \(j_0+j_1=k-u\) gives \[\begin{align*} \sum_i j_i\log(2j_i/k) &\le \frac{2(j_0^2+j_1^2)}k-(k-u)\\ &=\frac{(j_0-j_1)^2}{k}-\frac{u(k-u)}k \le\frac{(j_0-j_1)^2}{k}. \end{align*}\] Since \(j_0-j_1=(l_0-l_1)-(h_0-h_1)\) and \(|h_0-h_1|\le u\le k\), the last expression is at most \[ 8D+2u. \tag{66}\] The split tail in (56) implies \(\Pr(D>z)\le2e^{-2z}\) for \(z\ge0\). Consequently, for \(0\le t<2\), \[\mathbb E e^{tD} =1+t\int_0^\infty e^{tz}\Pr(D>z)\,dz \le1+\frac{2t}{2-t}.\] In particular \(\mathbb E e^{16c_{\rm s}D}\le9/7<2\).

On the event \(u=0\), the child defects equal their excitation counts. If \(b=1\), all excitations lie in one half, so (56) and the exact exponent \(\sum_i j_i\log(2j_i/k)=k\log2\) bound this part of the expectation of (65) by \[2^{1-k}2^{c_{\rm s}k} \le2^{2c_{\rm s}-1}<\frac35.\] If \(b=2\), (66) bounds its contribution by \(h_*\mathbb E e^{8c_{\rm s}D}\le2h_*=1/10\).

It remains to bound positive loss. Since \(M_*\ge1\) and \(h_*^{b-1}\le h_*^{-1}\), Cauchy–Schwarz and (63), in the form \(\Pr(u\ge r)\le4(8y)^{r/4}\), bound the total contribution from \(u\ge1\) by \[\begin{align*} \frac1{h_*}\sum_{r\ge1}y^{-c_{\rm s}r}e^{2c_{\rm s}r} \mathbb E[\mathbf1_{\{u=r\}}e^{8c_{\rm s}D}] &\le\frac{2\sqrt2}{h_*}\sum_{r\ge1} \left(e^{2c_{\rm s}}8^{1/8}y^{1/8-c_{\rm s}}\right)^r. \end{align*}\] Here \(1/8-c_{\rm s}=7/64>0\). Choose \(0<\delta_*\le1/8\) so that the last geometric series, with \(y\) replaced by \(\delta_*\), is at most \(1/5\). Then choose \[M_*\ge\delta_*^{-1}h_*^{-1/(2c_{\rm s})}.\] If \(y\ge\delta_*\) and \(k\ge2\), this choice makes \(h_*(M_*y)^{c_{\rm s}k}\ge1\). Thus every nontrivial case indeed has \(y<\delta_*\), as required for the tail estimate and child range.

The three contributions to the ratio are now less than \(3/5+1/10+1/5=9/10\). Components with a defect-one child contribute zero. Applying (55) proves the inductive step. The range \(2\le k\le n/2\) is empty at \(n=2\), and all cases with a proposed bound at least one were already covered by contractivity. Strong induction on \(d\) proves (64). Dropping \(h_*<1\) gives (51) with the absolute choices \(c=c_{\rm s}>0\) and \(C=c_{\rm s}\log M_*\).

Signed types and the inherited hook budget

We now prove Proposition 26. The norm estimate settles small first-row defects. At the other shapes we will split a sweep into a rectangle, weight each local signed type by its entropy, and interpolate a trace bound with an operator bound. The following comparisons connect those local types with the subdiagrams in \(L_n(\lambda)\).

First, for a \(q\)-hook diagram \(\eta\) of size at most \(n\), \[ \log D_\eta=F(\eta)+O(q^2\log(n+2)). \tag{67}\] Here is the hook-formula comparison, including the choice of Frobenius parts. Put \(A_i=a_i-1\), \(B_i=b_i\), with \(r\le q\) the Durfee index. The Frobenius form of the hook formula is \[D_\eta=|\eta|!\, \frac{\prod_{i<j}(A_i-A_j)(B_i-B_j)} {\prod_i A_i!B_i!\prod_{i,j}(A_i+B_j+1)}.\] It follows by splitting the hook product at the Durfee square; compare the row form in (Etingof et al. 2011, sec. 4.17, formula (5) and Theorem 4.53). All the displayed cross and Vandermonde factors are positive integers at most \(2n+1\), and there are \(O(q^2)\) of them. Replacing \(A_i!\) by \(a_i!\) costs another \(O(q\log(n+2))\) in logarithms. Finally the multinomial logarithm for the parts \(a_i,b_i\) differs from their entropy by \(O(q\log(n+2))\). This proves (67), with the empty shape treated as dimension one and entropy zero.

Use now the signed alphabet with \(q\) even and \(q\) odd colors from Section 2. A compact type is a pair \(\gamma=(\gamma^+,\gamma^-)\); write \(F_\gamma\) for the entropy of its concatenated parts. Lemma 11 gives all the needed conversion facts. The occurring permutation types are exactly the \(q\)-hook shapes, their full signed-tensor multiplicities are \(\exp(O(q^2\log(n+2)))\), and, whenever \(\eta\) occurs with compact type \(\gamma\), \[F_\gamma-O(q^2\log(n+2))\le\log D_\eta\le F_\gamma.\] Combining this with (67) yields \[F_\gamma=F(\eta)+O(q^2\log(n+2)).\] Thus both the compact carrier and the permutation multiplicities fit the same error, and every permitted hook can be realized by at least one compact type.

The parent uses \(q_n\) colors, whereas a child moment at size \(m\) is stated with the smaller hook parameter \(q_m\). The next comparison justifies using the larger inherited types in that child estimate.

The range requiring a moment induction

The moment bound (53) holds automatically on the trivial module. At any fixed finite collection of sizes, Lemma 4 allows one exponent to make every nontrivial weighted moment at most one. We will choose that exponent after fixing the threshold for the large-size argument.

Let us also dispense with some representations. Diagrams of height \(>n/2\) don’t survive even one layer (invariants under disjoint switches require dominance over the content with \(n/2\) twos, by the Young/Pieri rule). For \(k\le n^{1-\alpha/16}\) (first row defect), (53) at large sizes follows already with an absolute power taken sufficiently large, by (51), since \(D_\lambda\le n^{2k}\). All constants, even ones depending on our small fixed parameters, are meant to be absolute. For remaining shapes write \(S=\log D_\lambda\); we note \[S\gtrsim n^{1-\alpha/16}.\] Here is one verification. If height and width are both \(< n/10\), use the hook bound. Otherwise by transposing take a dimension at least \(n/10\) as width. Below the first row still lie at least \(c n^{1-\alpha/16}\) cells (using the height restriction in the transposed case). Take a subdiagram consisting of the first row shortened if necessary but still length \(\lfloor n/10\rfloor\), and \(l=\lfloor c' n^{1-\alpha/16}\rfloor\) cells below, \(c'\) small. It has exponentially many tableaux on scale \(l\): for instance fill the first \(l\) places of row one, then interleave the rest of that row freely with a tableau below. Branching proves the bound.

Moreover on these remaining shapes \[ L_n(\lambda)<\tfrac12 S \tag{70}\] at large sizes. Take the intersection with the \(q_n\)-hook for \(\eta\). Its dimension is at most \(D_\lambda\). If \(t=n-|\eta|\) is below \(n^{1-\alpha/4}\), (70) is immediate. Otherwise the \(t\) cells cut away themselves give a diagram (after translation) contained in \(\lambda\), of width and height at most \(n/q_n\), giving \(S\ge (\delta/2)t\log n\) by the hook bound. This proves (70).

Weighted interpolation on a rectangle

For the classical Schatten three-lines interpolation principle used here, see the Stein–Hirschman formulation in (Sutter et al. 2017, sec. 3.1, Theorem 3.1); uniform boundary bounds give the form needed below. The weighted family and its estimates are developed here.

Split the chronological coordinate order into two nearly equal groups. The first gives rows of size \(m_1\) and the second columns of size \(m_2\), where \(m_1m_2=n\) and both sizes are within a factor two of \(\sqrt n\). Write \[B_n=CR,\] where \(R\) is the product of the independent row sweeps and \(C\) the product of the independent column sweeps. Take \(p=\max(p_{m_1},p_{m_2})\); the child bounds remain valid at this larger power.

Choose a minimizing hook \(\eta\) in (53) and put \(t=n-|\eta|\). Let \(V=E\oplus O\) have \(q=q_n\) even and \(q\) odd colors, and let \(H\) be the even space with basis \(h_1,\ldots,h_t\). The compact group \(G_q\) acts on \(V\) and trivially on \(H\). Let \(W\subseteq(V\oplus H)^{\otimes n}\) be the span of words in which each marker \(h_a\) appears exactly once. Choose a global compact type \(\Gamma\) that occurs with permutation shape \(\eta\) on the \(n-t\) unmarked sites, and let \(P=P_\Gamma\). In \(PW\), the target shape \(\lambda\) occurs with multiplicity at least \(f^{\lambda/\eta}\), by branching with the distinct markers. In particular \(P\) reduces both \(R\) and \(C\).

The positive operators needed at the middle of this product are \[A=(RR^*)^{1/2},\qquad B=(C^*C)^{1/2}.\] To see their orientation explicitly, extend polar partial isometries to unitaries within each irreducible block of the corresponding subgroup algebra. Then \(R=AU_R\), \(C=U_CB\), and \(CR=U_CBAU_R\). These unitaries commute with \(P\), so the sweep restricted to \(PW\) has Schatten \(p\) norm \(\|BPA\|_p\). This remains true when either sweep has a kernel.

For a local block \(X\) of size \(m\), let \(Q_{X,\gamma}\) be its full \(G_q\)-isotypic projection on \((V\oplus H)^{\otimes X}\), where \(\gamma=(\gamma^+,\gamma^-)\) has total size at most \(m\) and each partition has at most \(q\) parts. The total size of \(\gamma\) is the number of clean letters. This projection includes every compatible marker word and every placement of its letters. Define \[F_X=\sum_\gamma F_\gamma Q_{X,\gamma},\qquad F_A=\sum_{X\text{ row}}F_X,\qquad F_B=\sum_{X\text{ column}}F_X,\] and restrict the resulting operators to \(W\). Each local sweep preserves marker contents and commutes with the color action. Thus \(F_A,F_B\) commute with their own positive operators \(A,B\), respectively, and both commute with the global compact-type projection \(P\). We interpolate a trace boundary carrying weights \(\sigma^{p/2}e^{(1-\beta)F_\gamma/2}\) with an operator boundary carrying weights \(e^{-(1-\beta)F_\gamma/(p-2)}\). Here \(\sigma\) is the local singular value operator, with the orientation just specified.

For \(p>2\) put \[h(z)=(1-\beta)\left(\frac z2-\frac{1-z}{p-2}\right),\qquad \mathcal Z(z)=B^{pz/2}e^{h(z)F_B}P e^{h(z)F_A}A^{pz/2}.\] At \(\vartheta=2/p\) one has \(h(\vartheta)=0\) and \(\mathcal Z(\vartheta)=BPA\). On both boundaries the imaginary powers lie on the outside and have norm at most one. Zero singular spaces stay zero throughout. Schatten interpolation from the operator norm to the Hilbert–Schmidt norm gives \[ \|BPA\|_p^p\le\|\mathcal Z(1)\|_2^2\|\mathcal Z(0)\|_\infty^{p-2}. \tag{71}\] We will choose \(p\) large enough that \(2(1-\beta)/(p-2)\le1\).

Positive compression at marked sites

We first bound the Hilbert–Schmidt norm squared. We may discard \(P_\Gamma\), by global equivariance, and are bounding the trace of the product of the two squared-weight operators. Terms in this trace must have identical hole positions between the two matrices: each hole must stay in its row and in its column. At a fixed ordered marker placement, \(Q_{X,\gamma}\) restricts to the clean compact-type projection, with the same entropy weight \(F_\gamma\). The following local estimate is what we need. If a block holds \(l\) holes, the trace over remaining clean letters, on diagonal compression fixing the positions of these holes, of the positive squared-weight operator in the block (all types) is at most \[ (m)_l^{-1}\exp\{G_m(l)+O(q^2\log(n+2)+\sqrt m)\}, \tag{72}\] where falling factorials are used.

To see this, decompose the local singular power by permutation shapes \(\mu\) at size \(m\). For a positive matrix coefficient operator supported on \(\mu\), with matrix there \(T\ge0\), the diagonal compression just uses its convolution coefficients restricted to the subgroup on \(m-l\) positions. Signs from the tensor convention are harmless or are absorbed by putting the hole positions last (signed tensor reordering). In Fourier terms, on a shape \(\eta'\) of this subgroup the result of restriction of coefficients is positive, of trace at most \[\frac{D_\mu\operatorname{Tr}T}{(m)_l D_{\eta'}},\] and requires \(\eta'\subset\mu\). Indeed restriction with normalized convolution scaling takes the partial trace on the multiplicity factor of the \(\eta'\) part of \(T\), with exactly the displayed dimension and factorial factor, by Schur orthogonality. Apply this in the clean module, using \(T=\sigma^p|_\mu\), and take trace on a given clean type, multiplying by its squared color weight factor at this boundary. Now (69), the induction, and the entropy and dimension approximations \(F(\eta')=F_\gamma+O(q^2\log(n+2)),\ \log D_{\eta'}=F_\gamma+O(q^2\log(n+2))\), pay the entire color weight. Summing types and \(\mu\)’s with their possible clean multiplicities gives (72); we have used the standard \(\exp(O(\sqrt m))\) partition-number bound. For disjoint local blocks we can multiply the bounds. More explicitly in signed tensor space, one reorders sites to group blocks to see the tensor product, and on fixed hole positions the reordered positive operators have the same trace. For the row diagonal compression and column diagonal compression, bound trace of their product by product of their traces.

Write \[E=n^{3/4} \log^2(n+2)+n^{1/2+2\delta}\log^2(n+2).\] A uniform bound for the log of this boundary Hilbert–Schmidt norm squared is \[ t(\alpha\log n-2\log(n/t))+O\big(t+E+n^{1-\alpha/3}\log(n+2)\big), \tag{73}\] with the main term zero for \(t=0\). We detail summation. Replace falling factorial reciprocals by \(m^{-l}\) costing \(O(t)\) in the log per side. The number of placed distinct holes is at most \(n^t\), canceling the \(m\)-powers, so average the remaining exponential over \(t\) uniform distinct sites. In \(G_m(l)\) we can remove the truncation: total error is \(O(n^{1-\alpha/3}\log(n+2))\), using \(m\asymp\sqrt n\) and that discrepancies occur only at \(l\le m^{1-\alpha}\). Let \(x,y\) be empirical row and column proportions of the hole sites. The sum of the log terms is then the main term in (73), plus \(t\) times the two relative entropies of \(x,y\) versus uniform. The latter exponential factors cost only \(O(t+E)\) in the log. Indeed replacing distinct sampling by independent samples costs at most \(e^{O(t)}\), and the two marginal histograms are then independent with probability for given histograms bounded by the inverse entropy factors; there are at most \((t+1)^{m_1+m_2}\) choices. This proves (73), the \(E\) term also counting all the local errors.

Density normalization at the operator boundary

For the operator boundary we explain a whitening estimate. It will give, in logs after raising to \(p-2\), at most \[ -(1-\beta) F_\Gamma + O(t+E). \tag{74}\] It suffices to work at magnitude weights \(e^{-F_\gamma/2}\), then steepness can be reduced to \((1-\beta)/(p-2)\le1/2\), by operator-norm interpolation between these weights and identity bounds, scaling the log estimate. Outside supported projections may only decrease the bound. Aim then for log norm \(-F_\Gamma/2+O(t+E)\).

We first construct one positive mixture for the entire local weight \(e^{-F_X}\). Fix a clean type \(\gamma\) and write \[s=|\gamma^+|+|\gamma^-|,\qquad \mathcal U_\gamma=\mathcal U_{\gamma^+}\otimes\mathcal U_{\gamma^-}, \qquad u_\gamma=\dim\mathcal U_\gamma.\] For \(s>0\), take the even density \(D_\gamma\) on \(V\) with eigenvalues \(\gamma_i^+/s\) on \(E\) and \(\gamma_j^-/s\) on \(O\), padded by zeroes. For \(s=0\) choose any even density. For \(g\in G_q\) put \[\widehat D_{\gamma,g}=(gD_\gamma g^*)\oplus I_H.\] Only the clean restriction has trace one; each marker has eigenvalue one.

Here is why this single choice controls every marker fiber with type \(\gamma\). Fix the clean positions and the letters at all other positions. Reordering the clean factors gives the decomposition \(\mathcal M_\gamma\otimes\mathcal U_\gamma\) of (8). On this space \((D_\gamma\oplus I_H)^{\otimes X}\) acts as \(I_{\mathcal M_\gamma}\otimes\pi_\gamma(D_\gamma)\), where \(\pi_\gamma\) is the polynomial color action. Summing these orthogonal spaces over clean positions and marker words only enlarges the multiplicity factor. Denote this full multiplicity space by \(\mathcal N_{X,\gamma}\). On the whole \(Q_{X,\gamma}\) range the action is \[I_{\mathcal N_{X,\gamma}}\otimes\pi_\gamma(D_\gamma).\] Thus Haar averaging is the same scalar on every copy of \(\mathcal U_\gamma\), independently of marker labels and placements. Lemma 8 identifies that scalar as at least \(e^{-F_\gamma}/u_\gamma\). The average preserves every compact type and is positive there, so on the full local tensor space \[e^{-F_\gamma}Q_{X,\gamma}\preceq u_\gamma\int_{G_q}\widehat D_{\gamma,g}^{\otimes X}\,dg.\] The same assertion includes the empty clean type: its carrier is one-dimensional and all its factors are markers.

We can now add these inequalities over clean types. There are at most \((m+1)^{2q}\) pairs of partitions of total size at most \(m\), and \(u_\gamma\le(m+1)^{q(q-1)}\). Consequently \[e^{-F_X}\preceq \sum_\gamma u_\gamma\int_{G_q}\widehat D_{\gamma,g}^{\otimes X}\,dg, \qquad c_X:=\sum_\gamma u_\gamma\le(m+1)^{q^2+q}.\] This sum charges each clean type once, with all its marker fibers already included in \(Q_{X,\gamma}\). Tensor these positive inequalities over the rows or the columns. Every factor preserves the sector \(W\), so restriction to \(W\) gives positive mixtures dominating \(e^{-F_A}\) and \(e^{-F_B}\). After dividing by their masses, the index measures are probabilities, and the two masses satisfy \[\log c_A+\log c_B \le (q^2+q)(m_1+m_2)\log(n+2).\] Apply Lemma 19 to these two entropy weights, with middle operator \(P_\Gamma\). It bounds \(\|e^{-F_B/2}P_\Gamma e^{-F_A/2}\|\) by \(\sqrt{c_Ac_B}\) times the supremum of \[\|T_{\rm col}^{1/2}P_\Gamma T_{\rm row}^{1/2}\|,\] where \(T_{\rm col}\) and \(T_{\rm row}\) are sitewise tensor products of extended densities, one clean density for each column or row, repeated along that line. This comparison acts on arbitrary vectors in \(W\). Its logarithmic mass cost is \(O(q^2(m_1+m_2)\log(n+2))\).

For one pair of mixture terms, write \(R_i\) for its clean row densities and \(C_j\) for its clean column densities. Put \(Z=m_2^{-1}\sum_{i=1}^{m_2}R_i\), a positive trace-one matrix on \(V\). Use inverse powers on its support, and extend all powers by identity on \(H\). In the middle write \[P_\Gamma=(P_\Gamma (Z^{1/2})^{\otimes n}) (Z^{-1/2})^{\otimes n}\] on the support needed when applied to the row product. The same identity-on-multiplicity decomposition applies to the global type \(\Gamma\), with \(n-t\) clean letters. Its first factor therefore has norm at most \(e^{-F_\Gamma/2}\) by Lemma 8. Apply Lemma 21 to the carrier matrix \(A=\pi_\Gamma(Z^{1/2})\). The factor \(P_\Gamma(Z^{1/2})^{\otimes n}\), zero on all other compact types, is an integral of global color actions with absolute coefficient integral at most \[(\dim\pi_\Gamma)e^{-F_\Gamma/2} \le e^{-F_\Gamma/2}\exp(O(q^2\log(n+2))).\] The extended densities, the global color actions and \(P_\Gamma\) preserve each ordered marker placement. Their product is therefore an orthogonal direct sum over placements, and its operator norm is the supremum of the norms on those summands. On clean sites we need the tensor over occupied cells (non-hole sites) of \[C_j^{1/2}\, U Z^{-1/2}\, R_i^{1/2}\] with \(U\in G_q\). The sum over all \(n\) cells of their squared Frobenius norms is at most \(n\): summing the whitened row factors gives \(m_2\) times the support projection of \(Z\), and each \(C_j\) has trace one. Lemma 20 therefore bounds the product of the one-cell norms on any \(n-t\) occupied cells by \(e^{t/2}\). The empty product is one when all sites are holes. This bound is uniform over marker placements, so taking their supremum adds no factor. Together with the mixture masses and the global carrier factor, it proves \[\log\|e^{-F_B/2}P_\Gamma e^{-F_A/2}\| \le-F_\Gamma/2+O(t+E).\] To obtain the precise operator boundary, interpolate \(e^{-zF_B/2}P_\Gamma e^{-zF_A/2}\) between this estimate and the norm-one boundary at \(\Re z=0\). At \(\vartheta=2(1-\beta)/(p-2)\le1\) the result is \[\log\|\mathcal Z(0)\|\le \frac{-(1-\beta)F_\Gamma+O(t+E)}{p-2}.\] Raising to the power \(p-2\) in (71) therefore gives (74) with an error constant independent of \(p\). This order of interpolation permits the finite-base power to be chosen after all size thresholds.

Closing the moment induction

Putting together (73), (74) and interpolation, and using multiplicity at least \(f^{\lambda/\eta}\), we obtain \[ \begin{split} \log( D_\lambda\operatorname{Tr}_\lambda |B_n|^p ) \le {}&\log(D_\lambda/f^{\lambda/\eta})-(1-\beta) F_\Gamma\\ &+t(\alpha\log n-2\log(n/t)) +O(t+E+n^{1-\alpha/3}\log(n+2)). \end{split} \tag{75}\] We address a dimension detail here: \(D_\lambda\) compared to \(D_\eta f^{\lambda/\eta}\) need not be estimated by counting orderings through \(\eta\) alone without any loss. We need an upper bound at cost \(\binom{n}{t}\) times at most exponential in \(t\). In fact \[D_\lambda\le \binom{n}{t} D_\eta f^{\lambda/\eta}.\] A standard tableau determines the subset of its entries in \(\eta\), their ordering there and the ordering on the skew complement, proving exactly this bound. Hence (75) gives \[ \log( D_\lambda\operatorname{Tr}_\lambda |B_n|^p ) \le L_n(\lambda)+O(t+E+n^{1-\alpha/3}\log(n+2)). \tag{76}\] It was relevant both to transfer the clean dimension through the middle and to have the negative log-sparsity term in (52), so that two contributions at subsizes can accommodate this binomial cost.

Write the error in (76) as \(\varepsilon_n\). For the remaining shapes, \[\varepsilon_n\le K\frac{S}{\log n},\qquad S=\log D_\lambda,\] with \(K\) independent of \(p\). To see this for its \(O(t)\) term, if \(t<n^{1-\alpha/8}\) use \(S\gtrsim n^{1-\alpha/16}\). Otherwise the minimizing cost contains \[G_n(t)\ge\frac{7\alpha}{8}t\log n, \qquad G_n(t)\le L_n(\lambda)<S/2,\] so \(t\le4S/(7\alpha\log n)\). The terms \(E+n^{1-\alpha/3}\log(n+2)\) are \(o(S/\log n)\) in both cases.

Take a size threshold above which \(K/\log n\le1/4\). Equation (76) and \(L_n(\lambda)<S/2\) imply, for each singular value \(s\) of \(B_n|_{V_\lambda}\), \[s^p\le\operatorname{Tr}_\lambda|B_n|^p \le\exp\{L_n(\lambda)+\varepsilon_n-S\} \le e^{-S/4}.\] Consequently, for \(A\ge4K\), \[\log\!\left(D_\lambda\operatorname{Tr}_\lambda |B_n|^{p(1+A/\log n)}\right) \le L_n(\lambda)+\varepsilon_n-\frac{AS}{4\log n} \le L_n(\lambda).\] This is the exponent increase needed for the parent estimate.

Choose an integer \(d_0\ge2\) large enough for all preceding large-size and child-size comparisons. The constants \(A,d_0\) depend only on the fixed budget parameters; the scaled operator-boundary estimate (74) keeps them independent of the base exponent. Now choose one \(P_*\ge8\) that meets the sparse requirement and makes every nontrivial weighted moment at sizes \(2^d\), \(1\le d\le d_0\), at most one, using Lemma 4. The trivial moment is one and every candidate in \(L_n\) is nonnegative. Define \[\begin{aligned} p_{2^d}&=P_* &&(1\le d\le d_0),\\ p_{2^d}&=\left(1+\frac{A}{d\log2}\right) \max\{p_{2^{\lfloor d/2\rfloor}}, p_{2^{\lceil d/2\rceil}}\} &&(d>d_0). \end{aligned}\] The preceding estimates prove the induction with these powers. Along a branch of rounded halvings, the sum of reciprocal bit lengths above \(d_0\) is at most \(2/d_0\). Therefore \[p_{2^d}\le P_*\exp\!\left(\frac{2A}{d_0\log2}\right) \qquad(d\ge1).\] This proves the uniform bound on the exponents and completes Proposition 26.

Amplification to full-deck mixing

Finally, the estimates imply TV convergence in constantly many butterflies. To state the details, at sparse levels (51) in the range used before and the elementary dimension bound show, on increasing a fixed absolute power if necessary, that the sum of \(D_\lambda\) times the power traces off the trivial diagram in this range tends to zero. Here one may sum at defect \(k\) over at most the partition number of \(k\) tails, and get for example \(n^{-2k}\) bounds per shape; defect 1 vanished exactly. For remaining levels (53), (70) give the same conclusion with a sufficiently large fixed power, by the lower bound on log dimensions, height cutoff and partition count. Take the power even, \(2a\); increasing powers throughout is harmless. The density relative to uniform after \(a\) complete butterflies has squared \(L^2\)-distance at most this vanishing sum, by Plancherel (products of \(a\) butterfly matrices in Fourier space have Hilbert–Schmidt norm bounded by the product of Schatten-\(2a\) norms). This holds from any starting order, hence gives the required upper bound.

The budget and the moment statement

For a list \(v\) of part sizes write \(h(v)=\sum v_i\log(\sum_j v_j/v_i)\), omitting zeros. Whenever \(M>0\), we use the continuous convention \(x\log(M/x)=0\) at \(x=0\). Define a budget \[L_n(\lambda)=\min\{ b h(\mu,\xi)+ c t\log n-t\log(n/t)\}.\] Here the diagrams \(\mu,\xi\) have total size \(n-t\), and \(\lambda\) occurs in the representation induced by \(\mu,\xi^\top\) on disjoint blocks with the remaining \(t\) sites freely labeled (a regular factor). Use absolute positive constants \(b\) sufficiently small, \(c\) sufficiently small compared with \(b\).

Three budget properties

Here are useful budget facts.

• \(L_n\le\frac12\log D_\lambda\). Peel off successively the longer of the first row and first column. Write \(\mathbf r=(r_i)\) for the row lengths peeled, \(\mathbf c=(c_j)\) for the column lengths peeled, and \(v\) for all these lengths in their peeling order. A row peel leaves an interlacing partition, so its reversal adds a horizontal strip; a column peel reverses to a vertical strip. Pieri’s rule therefore gives a trivial factor for a row peel and an alternating factor for a column peel. Put \(n_+=\sum_i r_i\), \(n_-=\sum_j c_j\), and \[M_{\mathbf r}=\operatorname{Ind}_{\prod_i S_{r_i}}^{S_{n_+}}\mathbf1, \qquad M_{\mathbf c}=\operatorname{Ind}_{\prod_j S_{c_j}}^{S_{n_-}}\mathbf1.\] Induction by stages, grouping the row and column factors, shows that \(V_\lambda\) occurs in \[\operatorname{Ind}_{S_{n_+}\times S_{n_-}}^{S_n} \bigl(M_{\mathbf r}\otimes (\operatorname{sgn}_{n_-}\otimes M_{\mathbf c})\bigr).\] Decompose \(M_{\mathbf r}\) and \(M_{\mathbf c}\) into irreducibles and choose constituents \(V_\mu\) and \(V_\xi\) whose corresponding induced summand still contains \(V_\lambda\). Since \(\operatorname{sgn}_{n_-}\otimes V_\xi\simeq V_{\xi^\top}\), this is an admissible pair for the budget with \(t=0\). An empty list uses the trivial representation of \(S_0\). Young’s rule (James 1978, 14.1, pp. 51–52) says that \(\mu\) and \(\xi\) dominate the decreasing rearrangements of \(\mathbf r\) and \(\mathbf c\), respectively. Convexity of \(x\log x\), applied separately at the fixed totals \(n_+,n_-\), gives \[\begin{aligned} h(\mu,\xi) &=n\log n-\sum_i\mu_i\log\mu_i-\sum_j\xi_j\log\xi_j\\ &\le n\log n-\sum_i r_i\log r_i-\sum_j c_j\log c_j =h(v). \end{aligned}\] Thus \(L_n\le b h(v)\).

  To bound \(h(v)\), write \(\ell=v_1,\ s=n-\ell\). If \(s=0\), then \(h(v)=0\). The hook product on the first removed line is at most \(\ell!\exp(s)\), by adding the \(s\) excess lengths; on every later one it is at most \((2v_i)^{v_i}\). Stirling or factorial estimates thus give \(\log D_\lambda\ge h(v)-O(s)\) (the ratio \(n!/\ell!\) has log at least \(n\log n-\ell\log\ell-O(s)\)). Also \(\log D_\lambda=\Omega(s)\) for growing \(n\): if \(\ell\) is a sufficiently small fraction of \(n\) this follows directly; otherwise keep the first line and a subdiagram below (or beside) it of size \(u=\min(s,\lfloor\ell/3\rfloor)\); interleavings of its fixed tableau with the line respecting the two-list ballot condition already give exponentially many in \(s\). Bounded small sizes can equivalently be handled separately. Hence \(h(v)\le C_0\log D_\lambda\) uniformly for an absolute \(C_0\), and fixing \(b\le1/(2C_0)\) proves the claimed budget bound.

• Every minimizing choice has at most \(q=\lceil n^{1/16}\rceil\) parts in each of \(\mu,\xi\), for large \(n\). Otherwise removing one end box from a smallest part and making it a tag (increasing \(t\)) saves \(b((1/16)\log n-O(1))\) while costing at most \(c\log n+1\). Branching permits this choice.

• \(L_n\ge -O(n^{1-c/2})\), and at the minimum \(t=O(n^{1-c/2}+\log D_\lambda/\log n)\).

For the last property, isolate the raw tag term on the real interval \(0\le t\le n\): \[\begin{aligned} \phi_n(0)&=0,\\ \phi_n(t)&=ct\log n-t\log(n/t)\\ &=t\log(t/n^{1-c})\quad(0<t\le n). \end{aligned}\] Its derivative is \(\log(t/n^{1-c})+1\), so its minimum occurs at \(t=n^{1-c}/e\) and equals \(-n^{1-c}/e\). For \(t\ge n^{1-c/2}\), we instead have \(\phi_n(t)\ge(c/2)t\log n\). Since \(bh\ge0\), the first bound gives \(L_n\ge-n^{1-c}/e\ge-n^{1-c/2}/e\). At a minimizing choice above the second threshold, \((c/2)t\log n\le L_n\le\frac12\log D_\lambda\), so \(t\le\log D_\lambda/(c\log n)\); below that threshold, \(t<n^{1-c/2}\). These are the two assertions in the last bullet.

In the dense-level case \(n-\lambda_1\ge n^{1-\eta}\), where \(\eta>0\) is fixed sufficiently small compared with \(c\), only \(\ell(\lambda)\le n/2\) matters: taller diagrams have no invariant vector for the first matching (Young’s rule). Here \(\log D_\lambda\gtrsim n^{1-\eta}\) by the preceding estimates. Consequently multiplicative losses \(\exp O(t+n^{1-c/6})\) in proving (77) at such levels can be absorbed (even to give the bound without the \(C n^{1-c/2}\)) by raising the exponent by a factor \(1+O(1/d)\), since the bound itself then forces each singular value to power \(p_d\) to be at most \(\exp(-\Omega(\log D_\lambda))\).

Sparse mixed-particle paths

First we record the sparse-level estimate for \(1\le k=n-\lambda_1<n^{1-\eta}\): \[ \|\rho_\lambda(B_n)\|\le n^{-a k} \tag{78}\] for large \(d\), some \(a(\eta)>0\). Work on the module of injections of \(k\) tracked labels. Lower-coordinate kernels (depending on fewer than all the labels of the output) kill the isotype in question, by branching. Analyze \(B_n B_n^* B_n\); in the middle sweep replace the joint kernel by the alternating inclusion-exclusion sum over subsets \(I\) of labels, in each term updating \(I\) together and each of its complement by private independent randomness. Use only distinct endpoints. Proper subsets give lower-coordinate kernels since a single particle finishes exactly uniformly. Given start and finish the paths are forced within the sweep. Draw their contact graph (using a common switch location at the same time). If some label is isolated the inclusion-exclusion entries cancel exactly (factorization on disjoint switches), so restrict every summand to no isolates. Each resulting nonnegative matrix, including the flanking sweeps, has column sums at most 1 (without restriction the independent-group updates preserve counting measure on their product space).

Its row sums are at most \(n^{-\Omega_\eta(k)}\), as follows. After the first sweep the tracked occupied sites have joint occupation upper bounds \((k/n)^r\) for every set of \(r\) sites. Indeed joint occupancy bounded by products of one-site probabilities persists from deterministic sets under fair transpositions (average the products, using arithmetic-geometric mean when both sites occur).

Fix the original injection, the common subset \(I\), a time \(\theta\) in the mixed middle sweep, and an ordered list of targets \(\mathbf y=(y_1,\ldots,y_r)\), where \(r\ge1\) and repetitions are allowed. Let \(Z_i(\theta)\) be the position of label \(i\) after the first true sweep and the indicated middle layers. For \(J\subseteq\{1,\ldots,r\}\), define the following sums over tracked labels: \[\begin{aligned} N_J(\mathbf y)&= \sum_{\substack{i_1,\ldots,i_r\text{ distinct}\\ i_h\in I\ \Longleftrightarrow\ h\in J}} \prod_{h=1}^r \mathbf1\{Z_{i_h}(\theta)=y_h\},\\ N(\mathbf y)&=\sum_JN_J(\mathbf y). \end{aligned}\] Thus \(N\) counts ordered distinct labels, not necessarily distinct target sites.

Temporarily condition on \(\mathcal F_0\), the sigma-field generated by the random starting configuration of the middle sweep. The coordinates updated by time \(\theta\) partition the sites into blocks \(C\) of a common size \(v\). In block \(C\), let \(A_C,F_C\) be the initial common and private particle counts, and let \(j_C,\ell_C\) count target indices in \(J,J^c\). If two common targets coincide, then \(N_J=0\), because common particles remain at distinct sites. Otherwise the fair-switch occupation bound applies to the \(j_C\) common targets; the distinct private labels have independent uniform positions and contribute the falling factorial \((F_C)_{\ell_C}\). Conditional independence between blocks and between the common and private randomness gives \[\begin{split} \mathbb E[N_J(\mathbf y)\mid\mathcal F_0] &\le \prod_C \frac{\mathbf1_{\{A_C\ge j_C\}}A_C^{j_C}(F_C)_{\ell_C}} {v^{j_C+\ell_C}}\\ &\le \prod_C \frac{e^{j_C}(A_C+F_C)_{j_C+\ell_C}} {v^{j_C+\ell_C}}. \end{split}\] Private targets may repeat, and a common and private target may coincide. We use \((a)_0=a^0=1\), with infeasible falling factorials zero. For \(A\ge j\), the second inequality follows from \(A^j/(A)_j\le j^j/j!\le e^j\) and \((A)_j(F)_\ell\le(A+F)_{j+\ell}\), with the evident convention at \(j=0\).

Put \(r_C=j_C+\ell_C\). Averaging over the first true sweep now gives \[\mathbb E\prod_C(A_C+F_C)_{r_C} \le \left(\prod_C(v)_{r_C}\right)(k/n)^r \le v^r(k/n)^r.\] Indeed the factorial product counts ordered distinct occupied starting sites within disjoint blocks, and each set of \(r\) such sites has joint occupation probability at most \((k/n)^r\). Averaging the conditional bound and summing over \(J\) therefore proves \[\mathbb E N(\mathbf y) \le (1+e)^r(k/n)^r \le (2e k/n)^r.\] This final expectation includes the first true sweep and the middle randomness; it conditions only on the original injection and \(I\), with \(\theta\) and \(\mathbf y\) prescribed.

Divide the middle sweep into a constant (depending on \(\eta\)) number of pieces each varying a block of bits of volume at most \(n^{\eta/2}\). No isolates forces in some piece \(\Omega_\eta(k)\) particles sharing their fixed-bit classes with peers at its start, hence at least \(r=\Omega_\eta(k)\) disjoint pairs there (round with \(r\ge1\), excluding the impossible case). Counting ordered target pairs, applying the preceding occupation bound to their \(2r\) ordered endpoints, and dividing by \(r!\), probability at most \[(n^{1+\eta/2})^r(2ek/n)^{2r}/r!.\] This proves the assertion. The matrix row-column sum bound and \(2^k\) terms now bound the cubed singular norm, proving (78). Since \(D_\lambda\le n^k\), this suffices both for (77) and for stronger decay with a fixed exponent.

The dense-level trace induction

We detail the dense-level induction. Use the two halves of the bits to arrange the sites in a rectangle with side lengths \(m=2^{\lfloor d/2\rfloor},m'=n/m\). (Call the row length \(m\).) The sweep factors are products of independent smaller sweeps on rows and on columns. With \(p=\max(p_{\lfloor d/2\rfloor},p_{\lceil d/2\rceil})\), bound the left trace without \(D_\lambda\) by \({\rm tr}_\lambda AB\), where \(A,B\) are positive subgroup algebras on rows and columns respectively, absolute powers \(p\) as in the trace inequality. Each is a tensor product, with regular trace budgets (77) per isotype per line.

Use minimizing \(\mu,\xi,t\), choosing \(\nu\vdash t\) such that induction with the tag block of type \(\nu\) contains \(\lambda\); in particular \[D_\lambda\le \binom{n}{t}e^{h(\mu,\xi)}D_\nu .\] Majorize the trace by using induction with regular tag block divided by \(D_\nu\), allowed by positivity of irrep traces. In expanding \(AB\), a trace contribution fixes all tagged sites individually. Since row and column lines intersect once, each factor permutation must fix them individually. Thus the upper bound is \(t!/D_\nu\) times a sum over tag sets \(T\) of size \(t\), of \({\rm tr}_{\mathcal H} A_0 B_0\). Here \(A_0,B_0\) are coefficient restrictions to row and column groups avoiding \(T\), and \(\mathcal H\) on the remaining grid sites is the representation induced by \(\mu,\xi^\top\). Restrictions are positive (compress regular matrices).

Write \(r_i\) for row tag counts and \(s_j\) for column counts. Let \(H\) be the product of the full row groups and \(H_0\) its subgroup fixing the tags pointwise; write \(J,J_0\) for columns. A row type is an irreducible representation \(V_\gamma=\bigotimes_iV_{\gamma_i}\) of \(H_0\), of dimension \(D_\gamma=\prod_iD_{\gamma_i}\). The element \(A_0\in\mathbb C[H_0]\) acts by the same matrix on every copy of this type. In the next display, \(\operatorname{tr}(A_0)_\gamma\) denotes the unnormalized trace on one such copy. For each row type occurring on \(\mathcal H\), \[ D_\gamma {\rm tr}(A_0)_\gamma \le \frac{|H_0|}{|H|} \exp\{b\log D_\gamma+c t\log m-\sum_i r_i\log(m/r_i) +O(n^{1-c/6})\}. \tag{79}\] The column estimate is identical. To prove the row estimate, apply Lemma 10 in each row, with \(G=S_m\), its subgroup \(S_{m-r_i}\), and the positive local factor \(A_i\) of \(A\). It gives \[D_{\gamma_i}\operatorname{tr}_{\gamma_i} (E_{S_{m-r_i}}A_i) \le\frac1{(m)_{r_i}} \sum_{\alpha_i\supseteq\gamma_i} D_{\alpha_i}\operatorname{tr}_{\alpha_i}A_i.\] Thus only extending parent types contribute, and there is no branching-multiplicity factor in this sum. Multiplying over rows gives \(\prod_i(m)_{r_i}^{-1}=|H_0|/|H|\). The number of extension choices is at most \(\exp O(n^{3/4}\log n)\) by the partition bound.

Each \(\gamma_i\) occurs in induction of a signed pair \(\delta,\epsilon^\top\), both of length at most \(q\): restrict the global signed tensor realization to the row and split its two parity classes. Every extension \(\alpha_i\) can then use this pair and \(r_i\) regular tags as a candidate in \(L_m(\alpha_i)\). The minimum is at most this candidate cost, so the child bound (77) applies with \[ h(\delta,\epsilon)\le\log D_{\gamma_i}+O(q^2\log n). \tag{80}\] For clarity, any Littlewood-Richardson result \(\gamma_i\) of \(\delta,\epsilon^\top\) contains both diagrams. Outside their union it adds at most \(q^2\) boxes since that bounds their intersection. In the first \(q\) rows and columns where they overlap or interact (the \(q\times q\) corner) hook costs are polynomial per box; in the horizontal arm, for boxes of \(\delta\), downward hook contributions within first \(q\) rows cost at most \(O(q^2\log n)\) extra log over row factorials. Extra boxes outside \(\delta,\epsilon^\top\) also modify hooks by \(O(\log n)\) per box (harmonic sums along their lines); boxes of \(\epsilon^\top\) do not extend into the horizontal arm, but can lengthen rows there only via the corner, already within the row extent of \(\delta\) if that row has arm boxes. The vertical arm works symmetrically. Thus hook product is at most \(\prod\delta_i!\prod\epsilon_j!\exp O(q^2\log n)\), giving (80).

The child allowances sum over the \(n/m\) rows to \(C(n/m)m^{1-c/2}=O(n^{1-c/4})\). Together with the type-entropy errors and extension counts, this fits \(O(n^{1-c/6})\) for the fixed small \(c\). The remaining child terms sum to \(b\log D_\gamma+ct\log m-\sum_i r_i\log(m/r_i)\), which proves (79) with constants independent of the moment exponent.

The signed-tensor overlap

We next retain the ranks needed to combine the one-copy traces in (79). Fix a row type \(V_\gamma\) of \(H_0\) and a column type \(V_\beta\) of \(J_0\). Let \(P\in\mathbb C[H_0]\) be an orthogonal projection supported on type \(\gamma\), of rank \(r\) on \(V_\gamma\), and let \(S\in\mathbb C[J_0]\) be supported on type \(\beta\), of rank \(s\) on \(V_\beta\). On \(\mathcal H\) each acts on every multiplicity copy of its type. In particular \(r,s\) are ranks on the respective product-group irreducibles, not ranks on \(\mathcal H\) or on compact color carriers. We claim \[ e^{(1-b)h(\mu,\xi)}{\rm tr}_{\mathcal H}(PS) \le r s (D_\gamma D_\beta)^{1-b}\exp O(t+n^{4/5}). \tag{81}\] Zero ranks give zero overlap. For the other cases use the signed tensor space on the non-tag sites, with \(q\) even and \(q\) odd colors. Its global compact type \((\mu,\xi)\) is a tensor product of a compact carrier and \(\mathcal H\), by (8). Restricted to row groups, multiplicities in the entire tensor space are \(\exp O(n^{4/5})\). Indeed, on each line the sum of squared multiplicities is the commutant dimension. The signed action on matrix units bounds that dimension by the number of orbits, at most \((n+1)^{(2q)^2}\). There are \(O(\sqrt n)\) lines and \(q=O(n^{1/16})\). It follows that \(\operatorname{tr}_{\mathcal H}(PS)\le rs\exp O(n^{4/5})\). We will interpolate this with a bound for the full row and column type projections. Its proof keeps the compact carrier visible.

We give the full covariance calculation, including the unitary multiplicity. This also explains why the comparison is valid for noncommuting densities.

If \(n-t=0\), the untagged representation \(\mathcal H\) is one dimensional, \(h(\mu,\xi)=0\), and all local permutation types have dimension one. The overlap bound is immediate (a zero rank gives zero, and otherwise both ranks are one). We henceforth assume \(n-t>0\).

Write \(h=h(\mu,\xi)\) and let \(\mathcal U\) be the irreducible representation of \(U(q)\times U(q)\) of type \(\tau=(\mu,\xi)\), with dimension \(M\). On the global \(\tau\)-sector the tensor space is \[\mathcal U\otimes\mathcal H.\] The symmetric-group action, and hence every row or column permutation projector, acts on \(\mathcal H\) and as the identity on \(\mathcal U\). For a tensor product \(R\) of row densities and a tensor product \(U\) of column densities, let \(R_\tau,U_\tau\) be their diagonal blocks on this sector. Define the ordinary, unnormalized partial traces \[R'=\operatorname{Tr}_{\mathcal U}R_\tau, \qquad U'=\operatorname{Tr}_{\mathcal U}U_\tau.\] Although \(R\) and \(U\) need not preserve the sector, their diagonal blocks are positive.

Let \(\bar\sigma_R,\bar\sigma_C\) be the averages of the row and column densities over all corresponding line indices. First make the densities positive definite; the result for singular densities follows by approximation on their supports. Write \[K_R=\rho_\tau(\bar\sigma_R^{-1/2}),\qquad K_C=\rho_\tau(\bar\sigma_C^{-1/2}).\] The highest-weight bound for a trace-one matrix gives \[\rho_\tau(\bar\sigma_R)\le e^{-h}I_{\mathcal U}, \qquad K_R^2\ge e^h I_{\mathcal U},\] and the same statements hold for \(\bar\sigma_C\) and \(K_C\). For every positive operator \(A\) on \(\mathcal U\otimes\mathcal H\), \[ \operatorname{Tr}_{\mathcal U} \big((K_R\otimes I)A(K_R\otimes I)\big) \ge e^h\operatorname{Tr}_{\mathcal U}A. \tag{82}\] To verify the positive order, test a vector \(v\in\mathcal H\). Its compression \(A_v\) on \(\mathcal U\) is positive, and the scalar on the left is \(\operatorname{Tr}(K_R A_vK_R) =\operatorname{Tr}(A_vK_R^2) \ge e^h\operatorname{Tr}A_v\). In particular, the comparison does not require \(K_R\) to commute with \(A\).

Choose a parity-preserving matrix \(Z_0\) with squared singular values \((\mu_i/(n-t),\xi_j/(n-t))\) and put \(Z=gZ_0h_0\), with \(g,h_0\) independent Haar block unitaries. In the complete tensor space use \(X=\bar\sigma_R^{-1/2}Z\bar\sigma_C^{-1/2}\). The product formula and Lemma 20 give \[ \operatorname{Tr}\big(RX^{\otimes(n-t)} U(X^*)^{\otimes(n-t)}\big)\le e^{O(t)}. \tag{83}\] Indeed the full-grid average of the one-site factors is \(\operatorname{Tr}(\bar\sigma_R X\bar\sigma_C X^*)= \operatorname{Tr}(ZZ^*)=1\).

Averaging independently over \(g,h_0\) eliminates terms between inequivalent global unitary types by Schur orthogonality. Every surviving type contributes a nonnegative scalar. For the selected type \(\tau\), the contribution is exactly \[ \frac{\|\rho_\tau(Z_0)\|_{\rm HS}^2}{M^2} \operatorname{Tr}_{\mathcal H} \left[ \operatorname{Tr}_{\mathcal U}(K_R R_\tau K_R) \operatorname{Tr}_{\mathcal U}(K_C U_\tau K_C) \right]. \tag{84}\] Here the carrier matrices are understood to be tensored with the identity. The formula follows twice from \(\int\rho(g)A\rho(g)^*\,dg=(\operatorname{Tr}A/M)I\); expanding matrix entries on the multiplicity space gives the ordinary partial traces displayed above. The highest-weight monomial gives \(\|\rho_\tau(Z_0)\|_{\rm HS}^2\ge e^{-h}\). Apply (82) to both positive blocks, and use positive trace comparison successively. Thus (84) is at least \[\frac{e^h}{M^2}\operatorname{Tr}_{\mathcal H}(R'U').\] Combining this with (83) yields \[ \operatorname{Tr}_{\mathcal H}(R'U') \le M^2e^{-h+O(t)}. \tag{85}\]

We now specify the local density mixtures. In a row with \(M_i>0\) untagged sites and permutation type \(\gamma_i\), list all compatible polynomial type pairs \((\delta,\epsilon)\), each of length at most \(q\), of total degree \(M_i\), for which \(\gamma_i\) occurs in \(\delta*\epsilon^\top\). For each pair choose the parity-preserving trace-one matrix with combined spectrum \((\delta/M_i,\epsilon/M_i)\) and conjugate it by independent Haar unitaries in the two parity spaces. Its tensor power on the corresponding polynomial sector has, before averaging, highest-weight eigenvalue \(e^{-h(\delta,\epsilon)}\). After averaging it is scalar there, with scalar at least that eigenvalue divided by the polynomial carrier dimension. It remains positive on every other sector.

By (80), \(h(\delta,\epsilon)\le\log D_{\gamma_i}+O(q^2\log n)\). The carrier dimensions and the number of type pairs are both \(\exp(O(q^2\log n))\). Mix uniformly over this finite list of pairs. The resulting density average therefore dominates \(D_{\gamma_i}^{-1}e^{-O(q^2\log n)}\) times the full \(\gamma_i\) projector on this row’s signed tensor space: that projector is contained in the sum of the compatible polynomial sectors. A row with no untagged sites has scalar tensor power one and can use any parity-preserving density. Tensoring the independent row mixtures, and using the graded regrouping of sites, gives domination by \(D_\gamma^{-1}e^{-O(n^{4/5})}\) times the full row-type projector. Indeed there are \(O(\sqrt n)\) lines and \(q=O(n^{1/16})\), so all line errors fit in \(O(n^{4/5})\). Construct the column mixture in exactly the same way with its local permutation types. It gives the corresponding factor with \(D_\beta\). The row and column mixtures are independent. On the global sector these projectors have the form \(I_{\mathcal U}\otimes P_\gamma\) and \(I_{\mathcal U}\otimes P_\beta\). Their unnormalized partial traces are \(M P_\gamma\) and \(M P_\beta\). Independence of the two density mixtures and positivity therefore give the lower bound \[\mathbb E\operatorname{Tr}(R'U') \ge \frac{M^2e^{-O(n^{4/5})}}{D_\gamma D_\beta} \operatorname{Tr}_{\mathcal H}(P_\gamma P_\beta).\] The two factors \(M\) cancel the \(M^2\) in (85), proving the full-type endpoint \[\operatorname{Tr}_{\mathcal H}(P_\gamma P_\beta) \le D_\gamma D_\beta\,e^{-h+O(t+n^{4/5})}.\]

Finally let \(P,S\) have ranks \(r,s>0\) in the respective irreducible symmetric-group spaces, as in the statement. Positive trace comparison bounds their overlap by the full-type endpoint. The multiplicity estimate supplies the independent bound \(\operatorname{Tr}(PS)\le rs\,e^{O(n^{4/5})}\). For \(0<b<1\), interpolate these two scalar upper bounds using \(\min(A,B)\le A^bB^{1-b}\); since \((rs)^b\le rs\), the result is \[e^{(1-b)h}\operatorname{Tr}_{\mathcal H}(PS) \le rs(D_\gamma D_\beta)^{1-b}e^{O(t+n^{4/5})},\] which is the stated overlap estimate. The case of a zero rank is immediate.

Counting the tag layouts

Spectrally expanding \(A_0,B_0\) into positive weighted projections and summing (81) using (79) (numbers of types absorbed), we conclude \[\begin{split} D_\lambda {\rm tr}_\lambda AB &\le \exp\{b h(\mu,\xi)+c t\log n+O(t+n^{1-c/6})\}\\ &\qquad{}\cdot \sum_{|T|=t}\exp\{-\sum_i r_i\log(m/r_i)-\sum_j s_j\log(m'/s_j)\}. \end{split}\] Here per table we used \(\binom nt t!(|H_0||J_0|)/(|H||J|)\le e^{O(t)}\), by falling factorial bounds. Group the tables by margins (subexponentially many, \(\exp O(n^{4/5})\)). With given margins their number is at most \[\exp\{\sum_i r_i\log(m/r_i)+\sum_j s_j\log(m'/s_j)-t\log(n/t)+O(t)\}.\] Indeed order the \(t\) entries arbitrarily, use multinomials for the two coordinate sequences separately and divide by \(t!\). This gives precisely the desired budget with absorbable losses.

Closing the exponent recursion

Fix \(b\), then \(c\), and then \(\eta\) in the ranges required above, in particular with \(\eta<c/6\). The raw tag calculation gives \(L_n\ge-n^{1-c/2}/e\). Fix the theorem’s allowance \(C\ge1/e\) now, so \(L_n+C n^{1-c/2}\ge0\) at every size and for every diagram.

For a dense block that is not annihilated, write \(W=\log D_\lambda\). The bounds on \(t\) and \(W\), together with \(\log n=d\log2\) and \(\eta<c/6\), give \(t+n^{1-c/6}\le K_0W/d\) above a fixed size. Consequently the preceding trace and layout estimates, with this \(C\) fixed, give \[\begin{aligned} D_\lambda {\rm tr}|\rho_\lambda(B_n)|^p &\le \exp\{L_n(\lambda)+K W/d\},\\ p&=\max(p_{\lfloor d/2\rfloor},p_{\lceil d/2\rceil}), \end{aligned}\] whenever the child bounds hold with exponents at least two. Here \(K\) is independent of \(p\): the trace inequality has unit constant, and the coefficients in the remaining errors above depend only on the fixed budget constants and allowance. Increase the size cutoff so that \(K/d\le1/4\). Since \(L_n\le W/2\), the last display makes every singular value \(s\) satisfy \(s^p\le e^{-W/4}\). Hence \[\begin{aligned} D_\lambda {\rm tr}|\rho_\lambda(B_n)|^{p(1+A/d)} &\le \exp\{L_n(\lambda)+(K-A/4)W/d\}\\ &\le e^{L_n(\lambda)} \end{aligned}\] when \(A\ge4K\). Choose an integer cutoff \(d_0\ge1\) large enough for this argument, the minimizing-part and sparse estimates, and all child-size thresholds used above. Both \(A\) and \(d_0\) have now been fixed independently of the base power.

Choose one real \(P_*\ge2\) above the fixed sparse requirement, including the stronger sparse decay, and large enough for every nontrivial block with \(1\le d\le d_0\). This is possible by Lemma 4: there are finitely many such blocks, their sweep norms are strictly below one, and \[\begin{aligned} D_\lambda {\rm tr}|\rho_\lambda(B_n)|^{P_*} &\le D_\lambda^2\|\rho_\lambda(B_n)\|^{P_*}\\ &\le1 \end{aligned}\] once \(P_*\) is large enough. Trivial blocks have weighted trace one and are covered by the already fixed nonnegative allowance. Set \[\begin{aligned} p_d&=P_*\quad(1\le d\le d_0),\\ p_d&=(1+A/d)\max(p_{\lfloor d/2\rfloor},p_{\lceil d/2\rceil}) \quad(d>d_0). \end{aligned}\] Every \(p_d\) is at least \(P_*\), so the sparse estimate remains available. Along a rounded-halving branch above the cutoff, a parent \(u\) and child \(v\) satisfy \(u-1\ge2(v-1)\). Thus the sum of \(1/u\) along that branch is at most \(2/d_0\), and \(p_d\le P_*\exp(2A/d_0)\). This proves (77) with bounded exponents.

After a sufficiently large absolute constant number of sweeps, Plancherel now gives vanishing squared relative \(L^2\) distance to uniform: for dense types (77) gives individual norm to bounded power \(\le e^{-\Omega(\log D_\lambda)}\), dominating both \(D_\lambda^2\) and the partition count; for sparse types use (78) and \(D_\lambda\le n^k\), with at most \(2^k\) diagrams per level. This implies the total variation bound, independent of the starting order. The support obstruction is Lemma 5.

Moment normalization and simultaneous targets

We work over \(\mathbb C\), using unitary representations of symmetric groups. For a dyadic size \(m=2^a\), use the sweep \(B_m\) of Section 1. Partition indices of irreducibles are denoted \(\lambda\), the representations by \([\lambda]\), their dimensions by \(D_\lambda\), and traces in them by \(\operatorname{tr}_\lambda\). Use also the empty partition in size zero, of dimension 1. From this point through the end of this section, \(p\ge1\) denotes an integer square-moment index; Proposition 29 later chooses \(p\) to be an absolute power of two. For \(\lambda\vdash m=2^a\), set \[\begin{aligned} B_\lambda&=H_\lambda=\log D_\lambda,\\ \mathcal L_\lambda&=\operatorname{tr}_\lambda Q_m^p =\operatorname{tr}_\lambda|B_m|^{2p},\\ e_\lambda&=B_\lambda+\log\mathcal L_\lambda =E_m(\lambda;2p). \end{aligned}\] Use \(e_\lambda=-\infty\) if the trace is zero. \(B_\lambda\) will also be used in sizes other than powers of 2.

The general marked recurrence will be used at real Schatten order \(2p\). The simultaneous induction below needs its sparse estimate, a dimension lower bound, and a comparison when the permitted hook shrinks. After completing that induction, we give an alternative derivation of its recurrence using weight projections and a trace inequality for powers of two. That derivation reuses the ordinary representation-theoretic conventions but supplies its own density and marked-trace argument.

The aim is to bound \(\mathcal L_\lambda\) for one fixed large \(p\). Near a single long row we do this directly using functions of a sparse set of labels. Otherwise we split a sweep in half, into independent operations on rows of a grid and then on the transversal columns, and recurse on traces. A graded tensor space handles diagrams in a small hook: it gives a weight-entropy bound from log dimension, and product states on rows and columns permit an overlap bound using the transversality. Distinct marked slots handle cells outside a hook. To keep the errors small relative to dimension the induction will track both log dimension on the hook and a budget for the marks. Constants in estimates below may increase from one bound to the next and are absolute once the indicated numerical parameters are fixed.

Take \(p\) to be a power of 2; its size will be fixed after all thresholds. Use \(\gamma=1/40,\ \eta=9/10\), and \(K_n=\lfloor n^\gamma\rfloor\). Define \[J(t,n)=t\log(n/t),\qquad W(t,n)=t\log n\] (zero at \(t=0\)). Let \(n=2^d\) be sufficiently large, and split the sweep into first \(\lfloor d/2\rfloor\) and last \(\lceil d/2\rceil\) coordinates, with \(r,s\) the respective powers of 2. The first part \(X\) acts by copies of \(B_r\) within the \(s\) rows of the grid, the second \(Y\) by copies of \(B_s\) in the \(r\) columns: averages factor across the disjoint groups in each part. So \(B_n=YX\). Index these groups together by \(g\), of sizes \(m_g\).

Suppose \(\lambda\vdash n\) has \(\mathcal L_\lambda>0\), and choose any subpartition \(\mu\subseteq\lambda\) of size \(M=n-t\) fitting the \(K_n\)-hook. Proposition 22, with real Schatten order \(2p\) and hook parameter \(q=K_n\), gives \[ e_\lambda+J(t,n) \ \le\ \max\ \Big\{ \sum_g \big(e_{\alpha_g}+J(h_g,m_g)\big) -\big(\sum_g B_{\delta_g}-B_\mu\big)_+ \Big\}+ C(t+n^\eta). \tag{86}\] Here one can take the max over choices with integers \(0\le h_g\le m_g\) summing to \(t\) in each of the two branches (rows, columns); \(\alpha_g\vdash m_g,\ \mathcal L_{\alpha_g}>0\); and \(\delta_g\subseteq\alpha_g\) of size \(m_g-h_g\) fitting the \(K_n\)-hook. The constants and size threshold do not depend on \(p\).

Indeed its error is \(O(t+n^{9/10})\), since \((r+s)(K_n^2+n^{1/4})\log(n+1)=O(n^{9/10})\). The alternative weight-space proof appears at the end of this section.

The simultaneous estimates

Fix \(u=10^{-5}\), \(\delta=u/4\); the sparse and dimension estimates below will use this value of \(\delta\). Call \(t\) high in size \(n\) if \(t>0\) and \(\log(n/t)\le u\log n\). Use bit-length levels \(d\le 2^l D\), \(l\ge0\), with an absolute integer \(D\) sufficiently large. Set \[A_0=1/4,\qquad b_0=\gamma/100,\qquad A_l-A_{l-1}=b_l-b_{l-1}=(2^{l-1}D)^{-1/2}\quad(l\ge1).\] Take \(D\) large enough that the sum of increments is less than \(b_0\); in particular \(A_l<1/2,\ 3u<b_l\le 2b_0<A_0\gamma/2\). Further sufficiently-large requirements below on \(D\) will be independent of the eventual moment exponent.

Sparse harmonic-tuple coupling

Here first allow any fixed \(0<\delta<1/2\); the simultaneous induction uses the value chosen above.

There is a \(p_0=p_0(\delta)\) such that, for any integer \(p\ge p_0\) and sufficiently large \(m=2^a\) (threshold depending only on \(\delta\)), \[ 1\le k=m-\lambda_1\le m^{1-\delta} \quad\Longrightarrow\quad e_\lambda\le -2k\log m. \tag{88}\] For this consider the space of functions on ordered injections \(x=(x_1,\ldots,x_k)\) of positions, with the uniform inner product, under permutation of positions (\((\pi f)(x)=f(\pi^{-1}x)\)). Call a function harmonic here if summing over the choices of any one coordinate, with the others fixed, gives zero. These functions form an invariant subspace: it is the orthogonal complement of the span of the functions independent of at least one coordinate. Applying the branching rule (Vershik and Okounkov 2005, Theorem 5.8) and Frobenius reciprocity (Etingof et al. 2011, Theorem 4.33), \([\lambda]\) with first row \(m-k\) occurs on the injection space (the stabilizer is \(S_{m-k}\)), but does not occur on \((k-1)\)-injections, since it does not contain the subpartition \((m-k+1)\). Its isotypic subspace is therefore harmonic.

Let \(T=(B_m^* B_m)^p\) act on these functions. Evaluation of \(g=T f\) is the expectation of \(f\) by evolving positions through \(p\) blocks, each consisting of two sweeps (one in reverse order; reversing the factors for action on positions still has the two-sweep property). We keep layers as separate random layers even where a projection is repeated. For disjoint injections \(x,y\) (all \(2k\) positions distinct, possible for these sizes when \(m\) is sufficiently large), consider the alternating sum \(\Delta g(x,y)\) of \(g\) on the \(2^k\) injections choosing \(x_i\) or \(y_i\) for each \(i\), with sign \((-1)^{\#\{i:y_i\text{ chosen}\}}\).

Couple all these evolutions by a skeleton with two alternative paths per label \(i\), initially at \(x_i,y_i\). They can coalesce within a label, in which case we use one path thereafter. Paths of distinct labels stay distinct. At a layer, call a label clean if none of its paths occupies a switch pair shared with a path of a different label. For each clean label choose a fresh uniform destination bit in the active coordinate, the same for both its paths, directing each to that endpoint of its pair. (This can direct both to the same endpoint.) For pairs involving unclean labels use the usual swap coins. All coins except the sharing just specified are fresh and independent. Pairs shared across labels always use a common usual swap, so preserve distinctness. For any fixed selection of alternatives, conditionally on the skeleton so far its paths have exactly the correct one-step transition: sharing a destination bit within a clean label causes no required correlation to fail, since only one of its paths is selected; among the pairs seen by the selection there are independent coins and a shared pair makes complementary outputs. Consequently from any fixed skeleton at a block start the trajectory of a fixed selection has the standard shuffle-path law.

Once any label coalesces, the alternating sum of the final \(f\) evaluations cancels pointwise in this coupling (its expectation is \(\Delta g\)), by toggling that label’s choice. To have no coalescence through a block starting with none, every label must be unclean at least once in the last sweep of the block: clean updates all through that sweep give identical bits in every coordinate for its paths. In such a skeleton, a uniformly random selection of alternatives has in expectation at least \(k/4\) distinct labels that participate in selected-path pair collisions in this sweep. Indeed for each label take a witnessing shared pair; selection of the two paths at that pair has probability \(1/4\) since they belong to distinct labels. In particular some selection has at least \(k/4\) participants. We union bound this last event over the \(2^k\) fixed selections, without conditioning their laws on what happens during the block.

For one fixed selection, we can do the trajectory probability calculation in its standard path law starting from deterministic positions conditionally at the block start. At the start of the last sweep the occupied subset satisfies \[\mathbb P(A\text{ all occupied})\le (k/m)^{|A|}\] for any set \(A\). To see this, the same product bound using individual marginal occupation probabilities holds initially from deterministic positions and is preserved by a layer. Pull \(A\) back through the independent swaps; the expected product of old marginals factors by pairs. A single endpoint in \(A\) yields the averaged marginal, and both endpoints yield the old product at most the square of the average. After the first sweep the averaged marginals are all \(k/m\), by averaging along every coordinate. Independently of this subset, full shuffle coins in the last sweep define a graph on the \(m\) positions at the start of that sweep. Trace paths starting at all positions, connecting starting positions whose paths occupy a switch pair at any layer just before its update. The graph has maximum degree at most \(a\). Participants are exactly the occupied vertices with an occupied neighbor.

In a fixed such graph, the nontrivial connected components of the induced occupied graph, if they have \(v\ge k/4\) vertices total, give a collection of \(c\le v/2\) nontrivial connected sets. The number of possibilities for given \(v,c\) is at most \(\binom mc 2^v a^{2v}\): choose roots in order (say the least elements, sorted), sizes, and describe each connected set by a walk traversing a spanning tree from its root using \(2(\text{size}-1)\) steps. Apply the occupied-set bound to each such collection (with \(v\) distinct vertices). Since \((em/c)^c\) is increasing up to \(c=m\), we can bound the root count by \((2em/v)^{v/2}\). Summing in \(c\) (at most \(v\le 2^v\) terms), the probability for a fixed selection is at most \[\sum_{v=\lceil k/4\rceil}^{k} [C a^2\sqrt{k/m}]^v\] for an absolute \(C\), using \(v\ge k/4\). For sufficiently large \(m\) and \(q=k/m\le m^{-\delta}\), the bracket is at most \(q^{1/4}\), giving sum at most \(2q^{k/16}\). Including the \(2^k\) selections, the conditional probability of no coalescence through the block is at most \(q^{k/32}\) (absorbing \(2^{k+1}\) for sufficiently large \(m\)). This bound repeats conditionally at each block. It gives \[|\Delta g(x,y)|\le 2^k q^{pk/32}\|f\|_\infty .\]

If \(f\) is harmonic so is \(g\). Average the alternating difference over a uniform \(y\) disjoint from \(x\). For a nonempty subset \(S\) of coordinates replaced, of size \(j\), summing \(g\) over distinct choices for these outside all of \(x\) can be done by inclusion-exclusion starting with choices just avoiding the positions of \(x\) in coordinates outside \(S\) (and still distinct). Expand \(\prod_{i\in S}(1-\mathbf 1_{\{y_i\in x_S\}})\) where \(x_S\) here is the set of corresponding positions. Terms with any unrestricted variable coordinate vanish on summing in that coordinate by harmonicity. The result is \((-1)^j\) times the sum with a permutation of the \(j\) positions \(x_S\) used, divided by \((m-k)_j\) for averaging. Thus the average alternating difference differs from \(g(x)\) by at most \(\|g\|_\infty\sum_{j=1}^k (k)_j/(m-k)_j\), where \((m)_j=m(m-1)\cdots(m-j+1)\), with \((m)_0=1\). The sum is at most \(1/2\) for sufficiently large \(m\) here (bound by a geometric sum with ratio \(k/(m-2k)\)). We conclude that \(\|T f\|_\infty\le 2^{k+1} q^{pk/32}\|f\|_\infty\) on the harmonic subspace. Applied to eigenvectors, this bounds the eigenvalues on \([\lambda]\); \(T\) is positive semidefinite. Also \(D_\lambda\le m^k\) by its occurrence, so \(e_\lambda\le 2k\log m+(k+1)\log 2-(p\delta/32)k\log m\). We get (88), for example taking \(p_0\ge 192/\delta\).

Dimensions in the nonsparse range

If \(\mathcal L_\lambda>0\), the length of \(\lambda\) is at most \(m/2\). In fact invariants for the first coordinate pair-swap subgroup \(S_2^{m/2}\) must occur, and induction of its trivial module builds the partition by \(m/2\) horizontal 2-strips. We claim for sufficiently large \(m\), \[ \mathcal L_\lambda>0,\quad m-\lambda_1>m^{1-\delta} \quad\Longrightarrow\quad B_\lambda\ge c m^{1-\delta} \tag{89}\] with \(c>0\). If \(\lambda_1\ge m/2\), interleave the first row with one fixed standard order of the \(k=m-\lambda_1\) tail cells, ensuring row count at least tail count in every prefix; this suffices for all column conditions (a tail cell in column \(j\) appears no earlier than the \(j\)-th tail step). The ballot count is at least \(\binom mk/(m+1)\) (subtract \(\binom m{k-1}\) by reflection at the first bad prefix), and \(\binom mk\ge(m/k)^k\ge2^k\). Otherwise both maximum row and column are at most \(m/2\). If their maximum \(b\) is at least \(m/(4e)\) (here \(e\) is the base of natural logarithms), orient the partition, by transposing if needed, with row size \(b\) and take a subpartition with that row and tail size \(b\). The same interleavings have log count \(\Omega(m)\). Dimension does not decrease in extending a subpartition (extend tableaux), nor change in transposing. If the maximum is smaller, all hooks are at most \(m/(2e)\) and the hook formula gives dimension at least \(2^m\). This proves (89).

Shrinking the allowed hook

We need a quantitative dimension estimate when shrinking the permitted hook. Let \(\theta\) have size \(M\le m\), let \(K=K_m\), and remove its cells with both indices \(>K\), obtaining \(\widehat\theta\) by removing \(v\) cells. Always \(B_\theta\ge B_{\widehat\theta}\). For sufficiently large \(m\), \[ M\ge K^3\quad\Longrightarrow\quad B_\theta-B_{\widehat\theta}\ge (\gamma/2)v\log m. \tag{90}\] For \(v>0\), write \(a,b\) for width and height of the removed region, taking \(a\ge b\) by symmetry. The dimension ratio by hooks has numerator \((M)_v\); the denominator consists of the removed hooks (at most \(2a\) each) and the inflation factors of the preserved hooks.

For the top \(K\) rows only columns \(K+j,\ 1\le j\le a\), have inflation. Let \(b_j\) be the decreasing (nonincreasing) heights added there. The hooks before adding are at least \(a-j+u,\ u=1,\ldots,K\), since the full rectangle there in the top rows was present. Per column the log inflations thus sum to at most \(\log\binom{K+b_j}{b_j}\le b_j(1+\log(1+K/b_j))\), just using the denominator bound \(u\). Summing by concavity gives at most \(v(1+\log(1+Ka/v))\). Another bound using \(\log(1+x)\le x\) is \[\sum_j b_j\sum_{u=1}^K\frac1{a-j+u} \ \le\ \frac va\sum_{j,u}\frac1{a-j+u} \ \le\ v(2+\log(1+K/a)).\] The first bound here averages oppositely ordered sequences; the double sum is at most \(\sum_{i=1}^a 1/i+\log\binom{a+K-1}{a}\) by summing in \(u\) with an integral.

Similarly for the left \(K\) columns with \(b\) in place of \(a\): choosing the better of the concavity and opposite-order bounds gives log inflation per removed cell at most \(2+\log(1+K/\max(v/b,b))\). For the top rows we can just use \(2+\log(1+K/a)\). The total log denominator per removed cell is therefore at most \[C+\log\!\big[ a \max(1,K/a)\max(1,K/\sqrt a)\big],\] using \(\max(b,v/b)\ge\sqrt v\ge\sqrt a\). The bracket is at most \(\max(M/K,K^2)\): \(a\le M/K\), and consider \(a\ge K^2,\ K\le a\le K^2,\ a\le K\) respectively. For \(M\ge K^3\), comparison with \((M/e)^v\) for the numerator proves a gain per cell of \(\log K-C-1\), giving (90). Nondecrease without the size assumption is by tableau extension.

Proof of the simultaneous estimates

Full-deck amplification

For a positive integer \(z\), Schatten Hölder gives \(\|B_n^z\|_{\rm HS}^2\le \operatorname{tr}((B_n^*B_n)^z)\) in each irreducible (use Schatten exponent \(2z\) on each factor). Take \(z=4p\). In the nonsparse positive-trace types, this trace is at most \(\mathcal L_\lambda^4\), so its product with \(D_\lambda\) is at most \(\exp(-B_\lambda)\) by (G) and \(A_l<1/2\). Their sum tends to zero by (89) and the Durfee-square bound on the number of partitions. In the nontrivial sparse types use just the trace at \(p\) as upper bound (sweep norm at most 1), giving products at most \(n^{-2k}\) by (88), summable to \(o(1)\) since there are at most \(2^k\) tail partitions of size \(k\). Zero traces contribute nothing.

Shuffle distributions act the same on positions from any starting deck; uniform orders correspond to uniform permutations. At \(zd\) shuffles the position law is \(B_n^z\), \(n=2^d\). Finite group Plancherel (or the regular trace applied to the squared norm of the group-algebra difference from uniform) identifies \(n!\) times the coefficient-wise squared distance with \(\sum_{\lambda\ne(n)}D_\lambda\|B_n^z\|_{{\rm HS},\lambda}^2\). By Cauchy–Schwarz its total variation distance from uniform is at most one half the square root of this sum, which tends to zero. This gives the upper mixing bound.

An alternative recurrence proof through weight projections

For completeness, we now derive (86) by a second overlap mechanism. The preceding induction used the general full-isotypic recurrence. The argument here instead resolves the global hook type into torus weights and extracts its entropy from those weights. We retain the notation \(B_\theta=\log D_\theta\), the grid and marked counts in (86), and the fixed power-of-two square-moment index \(p\).

The sweep moments

Use the sweep \(B_n\) of Section 1, with \(n=2^d\ge2\). For a one-position grid factor set \(B_1=I\), the empty product of coordinate layers. There is a grid decomposition for \(n=ab\) with \(a,b\) powers of two. Take \(a\) rows of length \(b\), so the first axes of the sweep are inside rows and the remaining ones inside columns. Then \(B_n=C R\), where \(R\) is a tensor product in the row permutation subgroup of \(a\) copies of \(B_b\), and \(C\) is analogously made from \(b\) copies of \(B_a\) in the column subgroup.

We use unitary representations. For a diagram (partition) \(\lambda\) of \(m\), write \(D_\lambda=f^\lambda\) for the dimension of the corresponding irreducible of \(S_m\), \(H_\lambda=\log D_\lambda\) (logs natural). Use dimension 1 for the empty diagram; \(f^{\lambda/\omega}\) counts standard tableaux of the indicated skew shape. The moments used in the proof are \[J_m(\lambda,p)=D_\lambda\,{\rm Tr}_\lambda |B_m|^p,\qquad |A|=(A^*A)^{1/2}.\] Here and below a trace with diagram subscript is in one copy of the irreducible. We prove bounds for these moments with bounded \(p\). We use standard representation theory of symmetric groups: in particular the branching rule, Schur-Weyl duality, the Littlewood-Richardson (LR) rule, and the hook length formula. Matrix inequalities used below include the Araki-Lieb-Thirring trace inequality (for positive matrices \(L,M\) and \(v\ge1\), \({\rm Tr}(L^{1/2}M L^{1/2})^v\le {\rm Tr}(L^v M^v)\), trace of powers on the left) and Schatten Hölder.

Roughly, at sparse levels we use the small probability of path encounters for all the cards on which there must be nontrivial dependence. At the other levels we propagate trace-moment bounds from the rows and columns. In that argument a spin representation (with two parities so as to cover both long rows and long columns of a diagram), augmented by distinct marks, permits testing for global permutation types with losses that combine well in entropy scale.

The optimized hook budget

The grid estimate will be used with a hook that grows with the deck. Fix \[\epsilon=\frac1{1000},\qquad c_0=\frac1{100},\qquad \theta=\frac12,\qquad Q_m=\lfloor m^{1/16}\rfloor.\] For a partition \(\xi\vdash m\), define \[G_m(\xi)=\min_{\substack{\alpha\subseteq\xi\\ \alpha_{Q_m+1}\le Q_m}} \left\{\theta H_\alpha+c_0(m-|\alpha|)\log m -(m-|\alpha|)\log\frac{m}{m-|\alpha|}\right\},\] where the last term is zero when \(|\alpha|=m\). Call \(\xi\) large-level when \(m-\xi_1>m^{1-\epsilon}\). The minimum retains the full, unclipped entropy cost of the deleted positions; at the other levels we will use a separate sparse estimate.

The sparse path estimate proves the second branch. For the first branch, we prove a marked-grid estimate at a prescribed parent hook, extend the child budgets to that inherited hook, and absorb the resulting error by a bounded increase in the Schatten exponent. The grid estimate is also the fixed-parameter consequence of Corollary 23; the proof here retains the alternative calculation with an ordered product of inverse densities.

Sparse path forests

Let \(k=m-\lambda_1\), using \(\lambda_i\) for row lengths. For an absolute \(\epsilon>0\) fixed at \(1/1000\), all sufficiently large \(m\), and \(1\le k\le m^{1-\epsilon}\), we have \[ J_m(\lambda,p)\le m^{-10k} \tag{94}\] for \(p\) larger than an absolute constant. Here are details of a contraction giving this estimate.

Use ordered \(k\)-tuples of distinct positions, containing the representation \(\lambda\) by branching (and in particular \(D_\lambda\le m^k\)). Here this module is induced from the trivial representation of \(S_{m-k}\), since that is the stabilizer. In this module every copy of \(\lambda\) is in the orthocomplement of the subspaces of functions omitting any one coordinate: the \((k-1)\)-tuple module has no copy. Thus such functions sum to zero over each coordinate given all others. In a one-sweep transition between distinct tuples \(x,y\), use the candidate paths on the cube that take their successive updated bits from \(y\), starting at \(x\). For each pair \(i,j\), let \(h_{ij}=0\) unless their paths at an update are at opposite sites of a common gate (matched pair), at the axis of their last starting-bit difference in update order. In the latter case set \(h_{ij}=1\) if they take opposite exits and \(-1\) if they take the same exit. The transition probability is \[m^{-k}F_{[k]},\qquad F_L=\prod_{i<j\ {\rm in}\ L}(1+h_{ij}).\] Indeed any path conflict must first arise at a common gate with different entry sites, then necessarily at the indicated axis for that pair if this is their first conflict. With no conflicts, each gate used twice saves a factor of two in probability. Also \(m^{-k}F_L\) is the path probability for true sweep paths on coordinates of \(L\) with independent fair-bit paths on all others (restricted here to distinct endpoints).

For the action on zero-sum functions as above we may replace \(F_{[k]}\) in the expectation kernel (from earlier \(x\) to later \(y\)) by \(G=\sum_{L\subseteq[k]}(-1)^{k-|L|}F_L\), since for every proper subset the sum against such a function in \(y\) vanishes by summing a missing coordinate first. This alternating sum cancels by toggling inclusion of any isolated vertex, so it is zero unless in the interaction graph (\(h_{ij}\ne0\) edges) there are no isolated vertices. Use this replacement at the later of two successive sweeps when taking the expectation of a function of the final tuple. The orders of the two sweeps need not agree. For the sup norm contraction it suffices to bound, uniformly in the start and \(L\), the probability of this covering event after the first true sweep and then the \(F_L\) experiment for the second sweep, paying a factor \(2^k\). We need only upper bound the event, so can drop the distinct-endpoint requirement of that experiment, testing if every path shared some gate with another.

After the first sweep the random occupied \(k\)-set \(U\) satisfies \[\Pr(V_0\subseteq U)\le (k/m)^{|V_0|}\] for each set \(V_0\). In fact the inequality bounding joint inclusion probability by the product of one-site marginals holds starting from a fixed set and persists after independent fair matching switches: average the old product bound over the switches on pairs. On a fully tested pair the product of old marginals is at most the square of their mean. And the sweep makes the one-site marginals constant.

Generate the following graph independently of \(U\) on all \(m\) sites. At each site start two potential paths, one using a common random sweep switching system, the other having its own independent random fair-bit path. Join sites if any two paths (one from each) share a gate at the same update, allowing any choices of their two types. Regardless of the coordinate labeling of \(U\), the second experiment can use a path of the requested type at each site, so our event requires \(U\) to induce a graph with no isolates.

Such a graph contains a spanning forest without singleton components. For a fixed forest on \(k\) indices with \(j\) edges, the expected number of ordered distinct site placements realizing all its edges is at most \(m^k(8\log_2 m/m)^j\).

To count, condition on the common switching system, sum over which of the two paths at each endpoint and which layer on each edge witnesses the encounter, and upper bound distinct placements by iid uniform placements times \(m^k\), using separate independent tapes for the private type per index (correct for distinct placements). Before imposing edge constraints the individual two-type records of positions are then independent across indices and each path has uniform one-site marginals. Peeling leaves gives probability at most \((2/m)^j\) for those constraints. Using the joint inclusion bound and dividing the labeled count (summed over forests) by \(k!\), since a successful induced graph has some witnessing forest for each indexing of the occupied sites, the required sup norm contraction is bounded by \[2^k \frac{k^k}{k!}\sum_{\lceil k/2\rceil\le j\le k-1} \binom{\binom{k}{2}}{j}(8\log_2 m/m)^j.\] For the empty sum use zero. Use one forward and one adjoint sweep so this bounds the spectral radius of \(B_m^*B_m\) on the indicated isotypic space by the sup norm estimate (permutation action on functions, or expectations for the self-adjoint kernel). For large \(m\) in the range of (94) the bound is at most \(m^{-\epsilon k/3}\) since \(\binom{\binom{k}{2}}j\le(O(k))^j\). Thus the singular values there are at most \(m^{-\epsilon k/6}\), proving (94) by the dimension bound.

Two other dimension facts we use are as follows. If \(\lambda\) has more than \(m/2\) rows, even one axis update annihilates it: matching-swaps invariants occur only for diagrams dominating the partition made from \(m/2\) parts of size 2, by Young’s rule. For remaining \(\lambda\), if \(k>m^{1-\epsilon}\), then \(H_\lambda\gtrsim m^{1-\epsilon}\) for large \(m\). Indeed if \(k\le m/4\), the hook formula gives \(D_\lambda\ge e^{-1}\binom mk\): the leg corrections to first-row hook lengths inflate their product over \(\lambda_1!\) by at most \(\exp(k/(\lambda_1-\lambda_2+1))\). Otherwise width and height are both at most \(3m/4\). If their sum is at most \(m/(2e)\), the hook formula suffices. Else transpose if necessary to have first row \(s\ge m/(4e)\), and restrict to a subshape with first row \(s\) and another \(\lfloor s/4\rfloor\) cells, using the previous first-row argument and branching.

The spin and marked-site estimate

If one grid factor has size \(1\), balance and \(n\ge2\) force \(n=2\), and the other factor has size \(m=n\). Apply (95) to that factor with \((\xi,\eta,l)=(\lambda,\omega,t)\). The allowance in (96) is \(\mathcal B_2+2\mathcal B_1\), so the conclusion already holds with zero error because \(\mathcal B_1\ge0\). We may now assume \(a,b\ge2\).

To prove this, in the irreducible \(\lambda\) bound \({\rm Tr}_\lambda|CR|^p\) by \({\rm Tr}_\lambda XY\), where \(X=|R^*|^p,\ Y=|C|^p\), by Araki-Lieb-Thirring and cyclic invariance for the trace of powers. These are positive subgroup elements, each a tensor product. They may each first be split into a sum by the diagrams \(\xi\) on the local symmetric groups (compressions by central subgroup isotypic projections). Use \(X,Y\) also for a fixed resulting pair of terms, still positive group algebra elements.

Use an induced module of cell states as follows. There are \(t\) distinct labeled holes, one site each, and the other \(g\) sites carry spins with value space \(V=V_+\oplus V_-\) (dimensions \(q,q\)). Site permutations act by permuting and using the sign on the odd spins, i.e. a relative-order sign on the \(V_-\) factors in the usual graded tensor permutation. Holes are even, without signs. Equivalently one takes a direct sum over hole positions and plus/minus patterns, transporting the spin tensors by permutations with that sign. Projection to one placement \(z\) of labeled holes is denoted \(D_z\), leaving free spins. In products computed with reordered site factors the graded reordering is a unitary identification; all subgroup operations within disjoint blocks preserve grading and act as usual tensor products after grouping their sites.

With chosen plus and minus counts and local Schur-Weyl types \(\alpha,\beta\) for the two spin spaces, spectra on these types correspond to highest weights \(\alpha,\beta\), both of length \(\le q\). For \(s\) spins, the permutation module on this sector consists (apart from the general-linear representation spaces) of induction from the symmetric-group types \(\alpha,\beta'\), with prime denoting transpose, by the odd-factor sign. In the presence of \(l\) additional labeled holes the whole representation induces further from \(S_s\) to \(S_{s+l}\).

Choose a global sector of this kind with plus type \(\mu\) made of the first \(q\) rows of \(\omega\) and minus type \(\nu\) the transpose of the remaining rows. Write \(Z\) for its orthogonal projector (full isotypic under the block-unitary or equivalently general-linear action). The spin module within \(g\) sites contains \(\omega\), since \(c_{\mu,\nu'}^\omega\ge1\) by the LR rule (the skew part \(\omega/\mu\) just consists of the lower rows). With the holes the sector thus has \(\lambda\)-multiplicity at least \(f^{\lambda/\omega}\) by branching. Also \[D_\lambda\le \binom nt D_\omega f^{\lambda/\omega}\] by splitting standard tableau fillings into these two cell sets. Let \(P_\lambda\) denote the global group-type projector.

We detail the trace estimate on this module. For any block-diagonal positive definite spin density \(D\) of trace 1 (blocks for \(+,-\)), put \(h=D^{-1}\), with \(h_{[g]}\) acting by \(h\) on all spins, same matrix independent of which sites, and identity transport (no change) on hole locations. On the sector \(Z\), \(h_{[g]}\) has minimum eigenvalue \(\ge\exp(J)\), where \[J=g\,\mathsf H\big((\mu_i/g)_i,(\nu_j/g)_j\big)\] and \(\mathsf H\) is Shannon entropy in natural logarithms (use \(J=0\) for \(g=0\)). In fact weights in each general-linear representation are majorized by its highest weight, so the maximum eigenvalue of the density power on the sector is bounded by its product of sorted block eigenvalues raised to highest-weight powers, which is at most \(\exp(-J)\) by the entropy/product inequality with eigenvalues summing in total to 1. The multinomial bound gives \(e^J\ge\binom g{|\mu|} D_\mu D_\nu\ge D_\omega\). Thus with \(u=1-\theta\), \[ ZP_\lambda\le D_\omega^{-u} h_{[g]}^u. \tag{97}\] Both sides commute with group algebra elements.

Local polynomial dimensions

Some local polynomial factors used below are recalled here. On \(s\le m\) spins of plus/minus types \(\alpha,\beta\), an occurring permutation type \(\eta\) has \[ D_\eta \ \ge\ (m+q+1)^{-O(q^2)} \exp\big(s\,\mathsf H(\alpha/s,\beta/s)\big). \tag{98}\] Indeed LR implies \(\eta_i\le\alpha_i+q,\ \eta'_j\le\beta_j+q\), and \(\eta\) fits the \(q\)-hook. For the first inequality a row of an LR tableau with content \(\beta'\) has at most \(\beta'_1\) boxes: match each entry \(>1\) to a distinct preceding entry of value one less by the lattice word property. Predecessors must be in strictly earlier rows, so the chains ending for boxes of this row use distinct ones. Transposition gives the other inequality. The product of hook lengths off the \(q\times q\) square in the first \(q\) rows is at most \((s+q+1)^{O(q^2)}\prod\alpha_i!\): the leg lengths there are at most \(q\), and row portions there have lengths at most \(\alpha_i\). Use the analogous column estimate, and hooks \(\le s\) on the square. The hook formula and multinomial estimate now give (98), trivially also for \(s=0\). Consequently the multiplicity of \(\eta\) in this sector is at most \((m+q+1)^{O(q^2)}\) since its LR coefficient is at most \(\binom{s}{|\alpha|}D_\alpha D_\beta / D_\eta\), and general-linear dimensions satisfy this polynomial-factor bound by the Weyl formula.

Twirl the rows before splitting the columns

Split \(X\) additionally by projecting orthogonally according to the number \(l_i\) of holes per row \(i\), and by plus/minus counts and general-linear types of spins there, and symmetric-group type \(\eta_i\) on the nonhole sites there. For the latter use a direct sum of the spin permutation-type projectors over hole placements. All local sectors are equivariant under the rows subgroup, and \(X\) preserves them, giving positive terms. Whenever nonzero, \(\eta_i\) is contained in the previously specified total row type \(\xi_i\) by branching: within each assignment of labels to blocks, a block’s sector over all placements is induced from its sector of stabilizer representation at one placement. Before using (97) we perform a twirl decomposition of each positive row-sector term. For row \(i\) with \(s_i=b-l_i>0\) and spin types \(\alpha_i,\beta_i\), take a random block-unitarily conjugated density \(\rho_i\) on \(V\) with block spectra \(\alpha_i/s_i,\beta_i/s_i\) (zeros allowed), independent Haar rotations. The average of its spin tensor power with exponent \(u\) per density (using \((\rho_i^u)^{\otimes s_i}\)) acts scalarly on the specified sector with scalar at least \[(n+1)^{-O(q^2)}\exp(-u\, s_i\mathsf H(\alpha_i/s_i,\beta_i/s_i)).\] This follows by Haar averaging, taking at least the highest-weight eigenvalue divided by the general-linear dimensions. Indeed the power acts by the general-linear representation, identically in every multiplicity copy, and its conjugation average over \(U(q)\times U(q)\) replaces each general-linear irrep matrix by a scalar by Schur’s lemma. For an empty spin set take scalar 1 and any density. The row term itself commutes with all such powers in its own row. Thus it is an average, with normalization the reciprocal scalar, of positive terms obtained by sandwiching it with the spin powers having exponent \(u/2\). We use the product over rows, and call the normalized integrand \(X'\), so the normalization consists of the product of those reciprocal scalars. Use positive definite approximations, if needed, at factors tending to 1 in the estimates by adding small positive scalar matrices to the densities and renormalizing, then taking limits.

Choose \(D=\sum_i\rho_i/a\) in (97).

Positive compression with labeled holes

On a single local block of size \(m\), with \(l\) holes at specified sites, write \(\xi,\eta,\alpha,\beta\) for its total permutation type, nonhole spin permutation type, and spin general-linear types. Before inserting \(h\) and before the spin-power sandwiching and normalization, the compressed PSD operator in the selected sector has trace at most \[ (m+q+1)^{O(q^2)} \frac{J_m(\xi,p)}{(m)_l D_\eta}. \tag{99}\] Here \((m)_l=m!/(m-l)!\). To see this, taking the diagonal with labeled holes fixed retains only coefficients in the stabilizer \(S_{m-l}\) of those positions from the local group algebra term of \(X\) or \(Y\) on type \(\xi\). Here we can identify the local module independently for each assigned set of hole labels, grouping the sites blockwise using the graded permutation identification. On fixed placements the action of the retained coefficients is thus via the spin permutation action in this block. The coefficient restriction remains positive (conditional expectation in group algebra, or compression of the regular matrix). Its identity coefficient is \(J_m(\xi,p)/m!\), unchanged, so by regular trace on \(S_{m-l}\) its trace on type \(\eta\) is at most \(J_m(\xi,p)/((m)_l D_\eta)\). Now apply the local multiplicity bound. All sector compressions here besides the original total-type restriction use projectors preserving fixed placements and commuting there with the retained subgroup action.

The interpolated density product

For clarity, discard terms with a zero bound and divide out the product of the trace bounds (99) over blocks on each respective side, including polynomial factors, so the remaining spin operators on each side prior to the sandwiches are positive \(X_0,Y_0\) with trace and norm at most 1 (formed locally for the spin system for \(z\), with graded grouping). In terms of tensor densities on occupied spin sites formed from the row matrices and the column matrices, denoted by \(\rho_R,\sigma_C\), and \(h_* = h^{\otimes g}\), the needed extra trace factor is bounded by \[ \left\| X_0^{1/2}\rho_R^{u/2} h_*^{u/2}\sigma_C^{u/2}Y_0^{1/2}\right\|_{\rm HS}^2 \le e^t . \tag{100}\]

Entropy accounting for the marks

For fixed vectors of hole counts with sums \(t\) on each side, the number of placements is at most \((t!/\prod l_i!)(t!/\prod l'_j!)\). Across both sides the product of \(1/(m)_l\) is at most \(n^{-t}e^{2t}\), using \((m)_l\ge (m/e)^l\). We record the entropy accounting: on the row side, \[\log(t!/\prod l_i!)\le t\log a+\sum_i e_b(l_i)-e_n(t)\] and analogously on columns. Thus the \(\sum e_m(l)\) terms cancel those of (95), and \(\binom nt\le\exp(e_n(t)+t)\). Also \(\sum l\log m=t\log n\). These estimates apply including zero counts. Finally the number of count and type choices and the polynomial factors combined are bounded by \(\exp(O((a+b)(q^2+n^{1/4})\log(n+1)))\), using at most \((m+1)^{O(\sqrt m)}\) diagrams of size \(\le m\) (e.g. describe by Durfee square and row/column lengths along it). There is no extra sum over hole-label allocations besides placements. This proves (96).

Extending the child estimate to an inherited hook

In this subsection \(E_m(\xi;p)=\log J_m(\xi,p)\) and \(j_m(l)=e_m(l)\), as in the marked recurrence.

The parent uses its own hook parameter when invoking the marked recurrence. It is therefore necessary to extend the child induction from the child’s smaller hook to every hook inherited from the parent. The extension below in fact applies to every subpartition of the child diagram.

Use \(\epsilon,c_0,\theta,Q_m\) and \(G_m\) from Proposition 30.

If the two children have different already established exponents, use their maximum \(p\). Each sweep is a contraction, so increasing the real Schatten exponent only decreases every \(E_m(\xi;p)\). Apply the lemma with that common \(p\) and then the marked recurrence with the parent parameter \(q=Q_n\). This verifies the all-subdiagram quantifier in the child hypothesis; restricting it to \(Q_m\)-hook diagrams would not suffice.

The bounded-exponent induction

From moments to forward sweeps

Put \(P=\sup_d p_d<\infty\) and choose an integer \(r\ge4P\). At large levels, the bound \(G_n(\lambda)\le0.6H_\lambda\) and the moment-slack inequality give \[\log J_n(\lambda,2r) \le\left(1-0.4\frac{2r}{p_d}\right)H_\lambda \le-2H_\lambda.\] Consequently \[\sum_{\lambda\ne(n)} J_n(\lambda,2r)=o(1).\] The large-level bound is summable with negligible total by the partition count and dimension bound. At the others use (94) (at most \(2^k\) diagrams per sparse \(k\)). By Schatten Hölder, the analogous regular-representation Hilbert-Schmidt sum with \({\rm Tr}_\lambda|B_n^r|^2\) in place of \({\rm Tr}_\lambda|B_n|^{2r}\) is no larger. This sum excluding the trivial diagram is the squared \(L^2\) distance of the permutation density from 1 relative to uniform, by the regular action trace formula. By Cauchy-Schwarz, \(rd\) shuffles therefore suffice in total variation at large \(d\), uniformly over starting orders by relabeling.

Whitening a graded tensor overlap

Consider an \(a_0\) by \(b_0\) grid with \(n=a_0b_0\) and \(t\) deleted cells. Put \(s=n-t\). When \(s=0\), the surviving representation is one-dimensional and the overlap bound below is immediate; thus the whitening argument assumes \(s>0\). Suppose \(\mu\vdash s\) lies in an \((r,r)\) hook, where \(1\le r\le n^{1/16}\) is an integer. Let \(X,Y\) be products of positive row and column group-algebra elements, supported on the local type tuples \(\gamma,\delta\), respectively. Then \[ \mathop{\mathrm{Tr}}_{V_\mu}XY\le\mathop{\mathrm{Tr}}_{V_\gamma}X\,\mathop{\mathrm{Tr}}_{V_\delta}Y\, \exp\{O((a_0+b_0+1)r^2\log(n+1)+t)+\min(0,W_\gamma+W_\delta-W_\mu)\}. \tag{103}\] Here local dimensions and traces multiply over the lines, so \(W_\gamma=\sum_i\log D_{\gamma_i}\) and \(W_\delta=\sum_j\log D_{\delta_j}\). For the balanced grids used in the induction, \(a_0+b_0=O(\sqrt n)\), the error is \(O(n^{4/5}+t)\). The displayed formula retains the error for arbitrary rectangular geometry.

We supply the entropy gain in this inequality. Realize the hook inside signed tensors over \(\mathbb C^r\oplus\mathbb C^r\), with the second summand odd. A compatible compact type has even and odd weight lists \(\xi,\eta\). Its entropy \(h\) differs from the symmetric group log dimension by \(O(r^2\log n)\); carrier dimensions and the number of compatible types cost \(\exp O(r^2\log n)\). Over all grid lines these errors are \(O((a_0+b_0+1)r^2\log(n+1))\). The complete positive-factor estimate, including all carrier multiplicities, is Proposition 18, applied with \(q=r\). Its local hook hypothesis causes no additional restriction here: a local type that occurs in the restriction of \(V_\mu\) is a subdiagram of \(\mu\) by the Littlewood–Richardson rule, and hence is itself an \((r,r)\)-hook shape. Any other local type acts as zero on \(V_\mu\). Thus the proposition proves (103). We retain the following deformation calculation to explain the entropy gain; the proposition supplies the passage to arbitrary positive factors and their multiplicities.

For a local type with list of weights \((p_i)\) and \(u\) sites, use the strictly positive density matrix with spectrum \((p_i+1)/(u+2r)\). Twirl it over the even and odd unitary groups. The highest-weight term in the twirl dominates the local type projection with loss \(e^{W_\gamma+O((a_0+b_0+1)r^2\log(n+1))}\), and similarly in the other direction. This regularization permits inverse square roots even when some weights vanish.

Work in one compatible global compact sector at a time. For each pair \((\xi,\eta)\) with at most \(r\) parts in each partition and \(|\xi|+|\eta|=s\) for which \(V_\mu\) occurs in \(\operatorname{Ind}_{S_{|\xi|}\times S_{|\eta|}}^{S_s} (V_\xi\otimes V_{\eta^{\mathsf t}})\), put \[\begin{gathered} K_r=U(r)_{\rm even}\times U(r)_{\rm odd},\\ \mathcal U_\tau= \mathbf S_\xi(\mathbb C^r)\otimes\mathbf S_\eta(\mathbb C^r),\\ \tau=\tau_{(\xi,\eta)}:K_r\longrightarrow U(\mathcal U_\tau). \end{gathered}\] Here \(\mathbf S_\xi\) and \(\mathbf S_\eta\) denote the irreducible polynomial carrier representations. The action \(\tau\) extends polynomially to the invertible parity-preserving block matrices. Write \(\chi_\tau(B)=\mathop{\mathrm{Tr}}_{\mathcal U_\tau}\tau(B)\) for its character, and \[h=s\log s-\sum_i\xi_i\log\xi_i-\sum_j\eta_j\log\eta_j,\] with zero summands omitted. On the whole signed tensor space let \(\rho_s(B)=B^{\otimes s}\) be the color action. It is distinct from the carrier action \(\tau(B)\); the position action remains the signed permutation action. Let \(Z=Z_\tau\) be the full compact \(\tau\)-isotypic projection in this tensor space, including every multiplicity copy.

Let \(\mathcal W\) be the set of \(s\) occupied cells. For the row and column densities from the local twirls, write \[\begin{gathered} R_{\mathcal W}=\bigotimes_{(i,j)\in\mathcal W}\rho_i,\\ C_{\mathcal W}=\bigotimes_{(i,j)\in\mathcal W}\sigma_j,\\ \bar\rho=a_0^{-1}\sum_{i=1}^{a_0}\rho_i,\qquad A=\bar\rho^{-1/2}. \end{gathered}\] An empty line may be assigned any strictly positive parity-preserving density of trace one. The regularized densities make \(\bar\rho\) strictly positive, so \(A\) is an invertible parity-preserving block matrix. With \(dg\) denoting normalized Haar measure on \(K_r\), the deformed character formula is \[ Z=(\dim\tau)\int_{K_r} \chi_\tau((Ag)^{-1})\rho_s(Ag)\,dg. \tag{104}\] Apply Lemma 21 with carrier matrix \(\tau(A)^{-1}\). Its coefficient integral acts as \(\tau(A)^{-1}\) on the carrier of every copy of \(\tau\) and as zero on the other compact types. Multiplication on the left by \(\rho_s(A)\) therefore gives \(Z\), proving the displayed formula. For unitary \(g\), the character factor is \[\begin{gathered} \chi_\tau((Ag)^{-1}) =\mathop{\mathrm{Tr}}_{\mathcal U_\tau}\bigl(\tau(g)^*\tau(A)^{-1}\bigr),\\ |\chi_\tau((Ag)^{-1})|\le(\dim\tau)e^{-h/2}. \end{gathered}\] The bound follows by evaluating the highest-weight monomials of \(A^{-1}\) and using the entropy maximizing proportions. The factor \(\dim\tau\) outside the integral is separate from the one in this character bound.

For each cell define the squared Hilbert–Schmidt quantity \[\begin{aligned} z_{ij}(g)&=\|\rho_i^{1/2}Ag\sigma_j^{1/2}\|_{\mathrm{HS}}^{\,2}\\ &=\mathop{\mathrm{Tr}}(A\rho_iA\,g\sigma_jg^*)\ge0. \end{aligned}\] Since \(A\bar\rho A=I\) and every \(\sigma_j\) has trace one, its sum over the full grid is \[\begin{aligned} \sum_{i=1}^{a_0}\sum_{j=1}^{b_0}z_{ij}(g) &=a_0\sum_{j=1}^{b_0}\mathop{\mathrm{Tr}}(g\sigma_jg^*)\\ &=a_0b_0=n. \end{aligned}\] Arithmetic–geometric means on the occupied cells therefore give \[\begin{aligned} \left\|\bigotimes_{(i,j)\in\mathcal W} \rho_i^{1/2}Ag\sigma_j^{1/2}\right\|_{\mathrm{HS}}^{\,2} &=\prod_{(i,j)\in\mathcal W}z_{ij}(g)\\ &\le(n/s)^s\le e^t. \end{aligned}\] Thus the tensor coefficient has Hilbert–Schmidt norm at most \(e^{t/2}\). The triangle inequality in (104), together with the character bound, gives the exact scale \[\|R_{\mathcal W}^{1/2}ZC_{\mathcal W}^{1/2}\|_{\mathrm{HS}} \le(\dim\tau)^2e^{-h/2+t/2}.\] Its square is at most \((\dim\tau)^4e^{-h+t}\). The two local twirl domination coefficients enter the overlap norm through their square roots. After squaring, their logarithms add \(W_\gamma+W_\delta+O((a_0+b_0+1)r^2\log(n+1))\) to this squared logarithmic bound. Applying this estimate to each compatible global type, retaining all carrier dimensions and the number of such types, and using \(h=W_\mu+O(r^2\log(n+1))\) gives the entropy exponent \(W_\gamma+W_\delta-W_\mu+O((a_0+b_0+1)r^2\log(n+1)+t)\).

The other branch of the minimum also needs the carrier factors. On the signed tensor space, let \(P_\mu\) be the full symmetric-group isotypic projection and let \(w_\mu\ge1\) be its multiplicity. Since \(P_\mu\) commutes with \(X\) and \(Y\), \[w_\mu\mathop{\mathrm{Tr}}_{V_\mu}(XY) =\mathop{\mathrm{Tr}}(P_\mu XY)\le(\mathop{\mathrm{Tr}}X)(\mathop{\mathrm{Tr}}Y).\] Each trace on the right is a product of local signed-tensor traces. A local trace is its one-copy irreducible trace multiplied by the local carrier multiplicity, which is at most \((n+r+1)^{10r^2}\) by Lemma 11. Keeping these multiplicities converts the global signed-tensor traces to the local irreducible traces in (103), and gives its zero entropy branch with the same allowed error.

The sparse bound and near-optimal deletion

For \(\lambda=(n-k,\beta)\), a separate path argument gives \[ \|B_n^*B_n|_{V_\lambda}\|_{\mathrm{op}} \le e^{Ck}(2kd/n)^{k/2},\qquad 2kd/n\le1. \tag{105}\] Apply the detailed weighted-forest proof of (17), with \(\Delta=2kd/n\). Its inclusion-probability argument and weighted neighbor bound hold for every \(k\le n/(2d)\), not only for a fixed polynomial sparse range. In that proof the sum over forests is \[e^{Ck}\sum_{1\le j\le k/2}\frac{k^j}{j!}\Delta^{k-j}.\] When \(\Delta\le1\), this is at most \(e^{Ck}\Delta^{k/2}\sum_{j\ge0}k^j/j! \le e^{(C+1)k}\Delta^{k/2}\). Thus the same row-sum estimate gives \(\|B_n\|^2\le e^{C'k}\Delta^{k/2}\) throughout the full displayed range. Since \(\|B_n^*B_n\|=\|B_n\|^2\), this proves (105). For \(k=1\) the centered kernel is zero, as its one-vertex encounter graph is isolated; for \(k=0\) the claimed sparse estimate is unnecessary.

The budget has the elementary bounds \[ E_n^+\le aW_\lambda,\qquad 0\le E_n^+-E_n\le Cn^{1-b}. \tag{106}\] The second follows by minimizing \(bt\log n-t\log(n/t)\) over \(0\le t\le n\). A near-minimizing diagram can be chosen in the \((r,r)\) hook with \(r=\lfloor n^{1/16}\rfloor\), at additional cost \(O(n^{99/100})\), and its deletion size obeys \[ t\le n^{1-b/2}+C(W_\lambda+n^{99/100})/\log n. \tag{107}\] To prove this carefully, set \(g_n(t)=bt\log n-t\log(n/t)\), with \(g_n(0)=0\). For \(t>0\), \[g_n'(t)=b\log n+\log(t/n)+1\le b\log n+1.\] Choose an exact minimizer \(\mu_0\subseteq\lambda\), and let \(v_j\) be the number of its boxes below row \(j\) and right of column \(j\). They form a translated straight partition \(\nu_j\). Let \(\mu^{(j)}\) be the diagram left after deleting that core. Filling \(\mu^{(j)}\) first and then \(\nu_j\) gives \(D_{\mu_0}\ge D_{\mu^{(j)}}D_{\nu_j}\). Among the \(v_j\) core boxes, the \(v_{2j}\) boxes beyond its first \(j\) rows and columns have hooks at most \(2v_j/j\); all other hooks are at most \(v_j\). Thus the hook formula and \(v!\ge(v/e)^v\) yield \[\log D_{\nu_j}\ge v_{2j}\log(j/2)-v_j.\] If \(v_{2j}\ge v_j/2>0\), deleting this core changes the objective by at most \[-a\{(v_j/2)\log(j/2)-v_j\}+v_j(b\log n+1).\] For \(j\ge\lceil n^{1/32}\rceil\) this is negative at all sufficiently large \(n\), since \(b-a/64<0\). Exact minimality therefore forces \(v_{2j}<v_j/2\) whenever \(v_j>0\). Starting at \(j_0=\lceil n^{1/32}\rceil\) and iterating dyadically to the largest \(j_h\le r\) gives \(j_h>r/2\) and \[v_r\le v_{j_h}\le n2^{-h}\le2nj_0/r=O(n^{31/32}).\] Truncate \(\mu_0\) once at \(r\). Its dimension decreases, while the derivative bound makes the increase of \(g_n\) at most \(O(n^{31/32}\log n)=O(n^{99/100})\). For its deletion size \(t\ge n^{1-b/2}\) one has \(g_n(t)\ge(b/2)t\log n\). The new objective is at most \(E_n(\lambda)+O(n^{99/100})\le aW_\lambda+O(n^{99/100})\), and its dimension term is nonnegative. This proves (107). Finally \(g_n\) has minimum \(-n^{1-b}/e\), establishing the second bound in (106) even when \(E_n\) is negative.

The cancellation of named-point factors

Induce from the selected hook diagram \(\mu\) on the remaining \(n-t\) points, fixing each of \(t\) distinct named points individually. The multiplicity of \(V_\lambda\) in this induced module is \(f^{\lambda/\mu}\) by branching. Splitting tableau entries also gives \[ D_\lambda\le\binom nt D_\mu f^{\lambda/\mu}. \tag{108}\] We specify precisely the coefficient restriction used on a row group. Let \(G=\prod_i S_{l_i}\), let \(\alpha\) be a tuple of row types, and let \(X\) be a positive group-algebra element whose only nonzero Fourier block is \(X_\alpha\ge0\). Use the conventions \[\widehat x(\alpha)=\sum_{g\in G}x(g)\rho_\alpha(g),\qquad x(g)=\frac{D_\alpha}{|G|} \mathop{\mathrm{Tr}}\{X_\alpha\rho_\alpha(g^{-1})\}.\] For a fixed set \(S\) of named positions, with \(s_i=|S\cap\operatorname{row}_i|\), let \(H=\{g\in G:g(s)=s\text{ for every }s\in S\}\) be its pointwise stabilizer. Thus \(H=\prod_i S_{l_i-s_i}\). Define \[ X_S=E_HX=\sum_{h\in H}x(h)h,\qquad X_{S,\gamma}=\sum_{h\in H}x(h)\rho_\gamma(h). \tag{109}\] This keeps the original coefficients on the subgroup \(H\); it neither prescribes arbitrary ordered images nor averages coefficients over other cosets.

The restriction is positive. Indeed the matrix of regular convolution by \(X\) has entries \(x(g_1g_2^{-1})\). Its compression to the basis indexed by \(H\) is exactly regular convolution by \(E_HX\), and a compression of a positive operator is positive. Equivalently, write the subgroup restriction as \(V_\alpha|_H=\bigoplus_\gamma V_\gamma\otimes M_{\alpha\gamma}\) and let \(\Pi_\gamma\) be the corresponding projection. Matrix coefficient orthogonality gives the exact formula \[X_{S,\gamma}= \frac{D_\alpha|H|}{|G|D_\gamma} \mathop{\mathrm{Tr}}_{M_{\alpha\gamma}} (\Pi_\gamma X_\alpha\Pi_\gamma),\] which is positive and is zero unless every \(\gamma_i\subseteq\alpha_i\). Fourier inversion at the identity, or summing this partial-trace formula, gives \[ \sum_\gamma D_\gamma\mathop{\mathrm{Tr}}X_{S,\gamma} =|H|x(e) =\frac{|H|}{|G|}D_\alpha\mathop{\mathrm{Tr}}X_\alpha. \tag{110}\] Each summand is nonnegative. Since \(|G|/|H|=\prod_i(l_i)_{s_i}\), it follows that \[ D_\gamma\mathop{\mathrm{Tr}}X_{S,\gamma}\le \frac{D_\alpha\mathop{\mathrm{Tr}}X_\alpha}{\prod_i(l_i)_{s_i}}. \tag{111}\] For factorizable \(X\), coefficient restriction factors over the rows. The column operator \(Y\) has the identical construction with column counts \(s'_j\) and its own pointwise stabilizer.

These are exactly the restrictions required by the induced trace. Its diagonal coset blocks are indexed by ordered positions of the \(t\) named points. A product of a row and a column permutation, in either order, can return a named point \((i,j)\) to itself only if both fix it: the row permutation changes only the column coordinate, and the column permutation changes only the row coordinate. Neither can undo a coordinate change made by the other, so the intermediate position must also be \((i,j)\). This holds for every named point simultaneously. Consequently, in the diagonal block associated with the position set \(S\), only the pointwise-stabilizing coefficients of both operators occur. Identifying the other positions with the carrier of \(\mu\) gives that block’s trace as \(\mathop{\mathrm{Tr}}_{V_\mu}(X_SY_S)\). The choice of coset representative merely conjugates this identification. Thus \[ \mathop{\mathrm{Tr}}_{\operatorname{Ind}V_\mu}(XY) =t!\sum_{|S|=t}\mathop{\mathrm{Tr}}_{V_\mu}(X_SY_S). \tag{112}\] All these traces are nonnegative because \(X_S,Y_S\ge0\). Likewise the irreducible traces of \(XY\) are nonnegative. The branching multiplicity therefore implies \(f^{\lambda/\mu}\mathop{\mathrm{Tr}}_{V_\lambda}(XY) \le\mathop{\mathrm{Tr}}_{\operatorname{Ind}V_\mu}(XY)\). Together with (108), this supplies the factor \(D_\mu\binom nt t!\) used below. In particular, the argument uses diagonal induced blocks and positivity of the pointwise-stabilizer expectation, rather than positivity of an arbitrary off-diagonal coset restriction.

For each child type \(\alpha\) and every prescribed stabilizer subshape \(\gamma\subseteq\alpha\) with \(h\) deleted positions, the minimum defining the child budget and its clipping bound give \[E_m^+(\alpha)\le aW_\gamma+bh\log m-h\log(m/h)+Cm^{1-b}.\] The candidate \(\gamma\) need not minimize the child objective. Summing over the two balanced axes gives a total clipping error \(O(n^{1-b/2})\). Consequently the sum of child budgets is at most \[ aU+bt\log n-J+O(n^{1-b/2}), \qquad U=W_\gamma+W_\delta, \tag{113}\] where the count entropy is \[J=\sum_i s_i\log(b_0/s_i)+\sum_j s'_j\log(a_0/s'_j).\] Each margin sums to \(t\), and zero summands are omitted. The number of compatible marked-cell sets with these margins is at most \[ \frac{t!}{\prod_i s_i!\prod_j s'_j!} \le\exp\{J-t\log(n/t)+O(t)\}. \tag{114}\] This is the usual assignment count: assign the labels to row slots and column slots, then forget their order within each line. Stirling gives the second inequality. The factor \(\binom nt t!\) from (108) cancels the falling factorials in (111), up to \(e^{O(t)}\). More precisely, \((m)_h\ge(m/e)^h\) and both margins sum to \(t\), so \[\frac{\binom nt t!} {\prod_i(b_0)_{s_i}\prod_j(a_0)_{s'_j}} \le e^{2t}.\] The cancellation must precede the estimate of the number of profiles; otherwise it would leave a spurious factorial cost.

Apply (103). Its raw trace bound has gain \(\min(0,U-W_\mu)\). The child quantities being propagated are dimension-weighted traces. Dividing their dimensions out and restoring the parent dimension multiplies this raw bound by \(e^{W_\mu-U}\). The resulting exponent is \(W_\mu-U+\min(0,U-W_\mu)=\min(0,W_\mu-U)\). It combines with (113) by the elementary inequality \[aU+\min(0,W_\mu-U)\le aW_\mu\qquad(0<a<1).\] Together with (114), this recovers exactly the expression minimized in (102), with errors \(O(n^{1-b/2}+t+n^{99/100})\). The logarithm of the number of remaining types and profiles is \(O(n^{3/4}+\sqrt n\log(n+1))\): the full child partitions and stabilizer subpartitions each contribute \(O(a_0\sqrt{b_0}+b_0\sqrt{a_0})\) by the partition bound, and the row and column margins contribute \(O((a_0+b_0)\log(n+1))\). These terms are included in the stated errors.

Interpolation with a fixed counting exponent

The two-strip argument below uses classical Schatten three-lines interpolation; see (Sutter et al. 2017, sec. 3.1, Theorem 3.1). This reference concerns the interpolation principle, while the profile count and angle inequality below are proved here.

Write the sweep as \(B_n=CR\), with \(R\) the product of row sweeps and \(C\) the product of column sweeps. Set \[A=(RR^*)^{1/2},\qquad B=(C^*C)^{1/2}.\] These positive group-algebra operators still factor over their respective lines. Within each irreducible block of the corresponding row or column subgroup algebra choose unitary extensions of the polar factors, so that \(R=AU_R\) and \(C=U_CB\). These extensions remain in their subgroup algebras. Then \(CR=U_CBAU_R\), and \(BA\) has the same singular values as the sweep. This identifies the positive operators used throughout the interpolation argument.

Let a representation \(\mathcal H\) contain at least \(L_\lambda\ge1\) copies of \(V_\lambda\) in a global \(S_n\)-invariant subspace \(S\), with the same letter denoting its orthogonal projection. In particular \(S\) commutes with the row and column operators. Suppose the row and column profiles give finite families \(\{E_\alpha\}\) and \(\{F_\beta\}\) of projections on \(\mathcal H\). Within each family the projections are mutually orthogonal, and \(\sum_\alpha E_\alpha=\sum_\beta F_\beta=I_{\mathcal H}\). Each projection commutes with \(S\); \(E_\alpha\) commutes with the row operator \(A\), and \(F_\beta\) with the column operator \(B\). Set \[J=\#\{(\alpha,\beta):F_\beta E_\alpha S\ne0\},\qquad w_{\alpha\beta}=\|F_\beta E_\alpha S\|.\] The two projection resolutions and \(S\ne0\) imply \(J\ge1\). Then, for \(p\ge p_0>1\), \[ T_n^\lambda(p)\le \frac{D_\lambda}{L_\lambda}J^{2p_0} \max_{\alpha,\beta} w_{\alpha\beta}^{2(p_0-1)} \mathop{\mathrm{Tr}}_{\mathcal H}(B_\beta^{2p}A_\alpha^{2p}). \tag{123}\] Here \(A_\alpha=AE_\alpha\), \(B_\beta=BF_\beta\). In particular \([S,A]=[S,B]=0\). Put \(r=p/p_0\). For \(r>1\), the first analytic family is \[Z(z)=B^{rz}A^{rz}S,\qquad0\le\Re z\le1.\] On the operator boundary its norm is at most one. On the other boundary, \(Z(1+it)=B^{irt}(B^rA^rS)A^{irt}\); this equality uses \([S,A]=0\). Imaginary powers are contractions on their supports. Interpolating at \(1/r\) with exponent \(2p_0\) on the right boundary gives \[\|BAS\|_{2p}^{2p}\le\|B^rA^rS\|_{2p_0}^{2p_0}.\] For \(r=1\) the assertion is equality. The projection resolutions give \(B^rA^rS=\sum_{\alpha,\beta}B_\beta^rA_\alpha^rS\). Only the \(J\) counted pairs contribute, since \(B_\beta^rA_\alpha^rS=B_\beta^r(F_\beta E_\alpha S)A_\alpha^r\). At the fixed exponent \(2p_0\), the triangle inequality bounds the last norm by \(J\max_{\alpha,\beta}\|B_\beta^rA_\alpha^rS\|_{2p_0}\). For a pair of profiles use the second family \[Z_{\alpha\beta}(z)=B_\beta^{pz}A_\alpha^{pz}S.\] At \(z=it\) this equals \(B_\beta^{ipt}(F_\beta E_\alpha S)A_\alpha^{ipt}\), with norm at most \(w_{\alpha\beta}\). On the other boundary the outer imaginary powers again disappear. Its squared Hilbert–Schmidt norm is at most \[\operatorname{Tr}(S A_\alpha^pB_\beta^{2p}A_\alpha^pS) \le\operatorname{Tr}(B_\beta^{2p}A_\alpha^{2p}).\] Interpolation at \(1/p_0\) therefore yields \[\|B_\beta^rA_\alpha^rS\|_{2p_0}^{2p_0} \le w_{\alpha\beta}^{2(p_0-1)} \operatorname{Tr}(B_\beta^{2p}A_\alpha^{2p}).\] Complex powers remain zero on zero singular spaces throughout. The trace on \(S\mathcal H\) contains at least \(L_\lambda\) identical copies of the target block. Positivity of the singular power gives \(L_\lambda\operatorname{Tr}_\lambda|B_n|^{2p} \le\|BAS\|_{2p}^{2p}\). These inequalities prove (123). Both counting powers depend only on \(p_0\). In the tuple application \(S\) is a central \(S_n\)-isotype; in the signed-color application it is a global color isotype. Both commute with the full permutation action and hence reduce \(A,B\) as required.

The finite starting range can be made entirely explicit. Put \(n_0=2^{d_0}\) and let \(\mathcal E_d\) be the hypercube edge transpositions. The identity and each member of \(\mathcal E_d\) have a specified sweep realization of probability \(\varepsilon_n=2^{-nd/2}\). For a unit vector \(v\) in a nontrivial irreducible, the variance identity for two independent sweep permutations gives \[1-\|B_nv\|^2 =\frac12\mathbb E_{g,h}\|\rho(g)v-\rho(h)v\|^2 \ge\varepsilon_n^2\sum_{e\in\mathcal E_d} \|(\rho(e)-I)v\|^2.\] Every permutation is a word of at most \(2n^2\) edge transpositions: a vertex transposition uses a path of length at most \(d\) and its return, and at most \(n-1\) vertex transpositions suffice. Telescoping along such a word and using Cauchy–Schwarz, then averaging uniformly over \(S_n\), gives \[2=\mathbb E_{g\in S_n}\|\rho(g)v-v\|^2 \le(2n^2)^2\sum_{e\in\mathcal E_d}\|(\rho(e)-I)v\|^2.\] The equality uses the absence of invariant vectors in a nontrivial irreducible. Thus the exact squared-norm gap is \[\|B_n\|_{\mathrm{op}}^2\le1-\frac{2^{-nd}}{2n^4}.\] It is therefore enough to take, after the absolute threshold \(d_0\) has been fixed, \[ p\ge2^{n_0d_0+1}n_0^5(\Lambda+2)\log n_0. \tag{124}\] Indeed, with \(\Gamma_0=2^{-n_0d_0}/(2n_0^4)\), every nontrivial starting block has squared norm at most \(e^{-\Gamma_0}\). The unnormalized trace has \(D_\lambda\) eigenvalues, and \(D_\lambda\le n!\le n_0^{n_0}\), so \[\log T_n^\lambda(p)\le2n_0\log n_0-p\Gamma_0 \le-\Lambda n_0\log n_0.\] The level-budget exponent is at least \(-\Lambda n_0\log n_0\) on these sizes, and the diagram budget is nonnegative; zero blocks are automatic. This deliberately crude choice therefore proves both starting targets and makes the order of choices noncircular.

Small levels by path cancellation

For all sufficiently large \(d\) and \(1\le k\le n^{3/5}\) we claim \[ \|B_n|_{V_\lambda}\|_{\mathrm{op}}\le e^{-c_s k\log n} \tag{125}\] for an absolute \(c_s>0\). We prove this on the injective \(k\)-tuple module. Its \(\lambda\)-isotype has multiplicity \(D_{\bar\lambda}\), where \(\bar\lambda\) is the diagram below the first row. Zero extension to all \(k\)-tuples, with uniform product measure, multiplies every squared norm by the same factor \((n)_k/n^k\). An isotype vector has zero average in each separate coordinate: otherwise its averaging would give a nonzero copy of \(\lambda\) in the \((k-1)\)-tuple module, contrary to branching.

Let \(x,y\) be independent uniform \(k\)-tuples. For \(I\subseteq[k]\), let \(g_I(x,y)\) be \(n^{|I|}\) times the endpoint transition probability for the labels in \(I\), extended by zero when either restricted tuple is noninjective and then lifted to all coordinates. Set \(g_\varnothing=1\). On injective \(x,y\), define a potential contact between two labels as follows. If \(t\) is their last differing input bit in sweep order, their output prefixes of length \(t-1\) must agree. Their prescribed paths then enter opposite sides of the same switch at time \(t\). The prescribed routes are incompatible if their output bits also agree at time \(t\). Otherwise the shared switch saves one of the \(|I|d\) independent coin requirements. It follows that \(g_I=0\) on incompatible routes and \(g_I=2^{e_I}\) on compatible routes, where \(e_I\) counts potential contacts within \(I\). Indeed, the input suffix and output prefix specify the position before every layer; a collision of prescribed positions would already give an incompatible potential contact.

In a bilinear form between the zero-extended isotype vectors, we may replace \(g_{[k]}\) by \(\sum_{I\subseteq[k]}(-1)^{k-|I|}g_I\). Each omitted-coordinate term vanishes by the preceding zero-average property. On injective \(x,y\) this centered kernel vanishes unless the potential-contact graph has no isolated vertex: toggle any isolated label in the sum. Its squared Hilbert–Schmidt norm is consequently at most \[ 4^k\max_{I\subseteq[k]} \mathbb E_{x,y}\!\left[ {\bf1}_{\{x,y\ {\rm injective}\}} {\bf1}_{\{\text{every label has a potential contact}\}}g_I^2 \right]. \tag{126}\] All expectations in this display use uniform product measure.

Use one factor of \(g_I\) as a change of measure. Namely, sample the \(q=|I|\) input sites uniformly without replacement and move them through an independent complete switch field \(\omega\); labels outside \(I\) retain independent uniform inputs and outputs. The probability that the original independent inputs in \(I\) were injective is at most one, so it can be discarded in an upper bound. The remaining factor is \(2^{e_I}\), now counting encounters of the \(q\) sampled actual paths. We may also discard injectivity conditions on outside labels. When their inputs coincide we define no potential edge between them; this convention agrees with the original event whenever all inputs are injective.

Fix \(\omega\). Its encounter graph \(\mathcal G_\omega\) has the \(n\) initial sites as vertices; two vertices are adjacent when their actual paths share a switch. A path has at most one such contact per layer, so the degree is at most \(d\). Two paths meet at most once: after a meeting they differ in the edited bit, which is never edited again. For any \(s\) vertices there are at most \(s\log_2s/2\) induced edges. To verify this, merge the input suffix classes in a binary tree. At a merge with selected child counts \(h,s-h\), the new contacts form a matching, of size at most \(\min(h,s-h)\). The inequality \[2\min(h,s-h)\le s\log_2s-h\log_2h-(s-h)\log_2(s-h)\] telescopes over the tree. Thus a sampled component of size \(s\) has weight at most \(s^{s/2}\).

For the uniform injective sample of size \(q\le k\), let \(L\) be the number of sampled vertices in nonsingleton induced components, let \(J\) be the number of these components, and let \(E_I\) be the number of sampled induced edges. We prove the precise weighted estimate \[ \mathbb E\!\left[{\bf1}_{\{L=l,J=j\}}2^{E_I} \,\middle|\,\omega\right] \le e^{Ck\log(d+1)}\frac{k^{3l/2-2j}}{n^{l-j}}. \tag{127}\] The case \(l=j=0\) has right-hand side at least one. For \(j>0\), enumerate ordered disjoint connected vertex sets of sizes \(s_1,\ldots,s_j\ge2\), with sum \(l\). There are at most \(2^l\) size lists. A connected set of size \(s\) can be encoded by a rooted plane spanning tree, a root vertex, and a neighbor index for each tree edge. There are at most \(4^{s-1}\) plane tree shapes, so at most \(n(4d)^{s-1}\) such encodings. An encoding may be redundant; it is used only for an upper bound.

Assign distinct sample labels to the chosen vertices in at most \(k^l\) ways. Prescribed distinct placements of those labels have probability \(1/(n)_l\). On the event \(L=l,J=j\), the actual components give at least \(j!\) ordered witnesses. Each such witness, weighted by \(\prod_h s_h^{s_h/2}\), bounds \(2^{E_I}\). Hence the expectation is at most \[\frac{2^l n^j(4d)^{l-j}k^l}{j!(n)_l} \max_{s_1+\cdots+s_j=l}\prod_hs_h^{s_h/2}.\] For \(2\le s\le k\), \(s^{s/2}=s\,s^{(s-2)/2}\le e^s k^{(s-2)/2}\), so the product is at most \(e^l k^{(l-2j)/2}\). Moreover \((n)_l\ge(n/e)^l\) and \(1/j!\le e^{Ck}k^{-j}\), the latter following from \(j!\ge(j/e)^j\) and \(j\log(k/j)\le k/e\). These bounds prove (127), uniformly in the fixed switch field.

Put \(z=\log k/\log n\le3/5\). The logarithm of the ratio in (127), divided by \(\log n\), is \[(3z/2-1)l+(1-2z)j\le-l/10.\] For \(z\ge1/2\) both coefficients have the required sign; for \(z<1/2\), use \(j\le l/2\) to obtain the stronger bound \(-(1-z)l/2\). Thus \(l\ge k/4\) supplies a saving of order \(k\log n\).

If \(l<k/4\) and \(q\ge k/2\), expose the outside endpoints before sampling the \(q\) base paths. Each prescribed outside path has at most \(d\) possible base-path neighbors: at every layer exactly one base path occupies the opposite pre-switch site. Coverage therefore requires at least \(h=\lceil k/4\rceil\) further sampled labels, outside the nonsingleton components, to belong to a set of at most \(kd\) initial sites. In the preceding witness count, choose these labels in at most \(2^k\) ways and prescribe their sites in at most \((kd)^h\) ways, using \(1/(n)_{l+h}\) for the joint distinct placements. Since \(l+h\le q\le k\), this inserts the factor \(e^{O(k)}(kd/n)^h\) in the same weighted bound.

If \(q<k/2\), condition on all sampled trajectories. Let \(o=k-q\). To cover the outside vertices choose a rooted forest whose components either end at a sampled label or have one free outside root. Every component of the second kind contains at least two outside vertices, so there are at most \(o/2\) free roots and at least \(o/2\) forest edges. Root choices cost at most \(2^o\) and each other vertex has at most \(k\) parent choices. Expose each parent before its child. For a fixed contact time, the child’s required input suffix, opposite input bit, and output prefix jointly have probability \(1/n\); summing over times gives \(d/n\). Thus, uniformly in the sampled trajectories, coverage costs at most \(2^o(kd/n)^{o/2}\) for all large \(d\).

In each case the additional power of \(kd/n\) or the bound \(n^{-l/10}\) saves a fixed multiple of \(k\log n\). The costs \(O(k\log(d+1))\), the at most \((k+1)^2\) choices of \(l,j\), and the \(4^k\) in (126) are smaller than that saving when \(d\) is large. The resulting Hilbert–Schmidt bound for the centered kernel proves (125), after decreasing \(c_s\). When \(k=1\) the centered kernel is zero. Finally \(D_\lambda\le\binom nkD_{\bar\lambda}\le n^k\), so \(T_n^\lambda(p)\le n^{2k}e^{-2pc_s k\log n}\). Choosing a fixed \(p\) sufficiently large in terms of \(\Lambda,c_s\) proves the level budget in this range; it also proves the nonnegative diagram budget there.

A tuple frame that includes full rows

The sparse estimate settles the small levels. For larger levels we need both the angle and the trace endpoint in (123). We first construct a frame with total norm cost \(e^{Ck}\); the entropy saving will come from centering the resulting pieces.

For definiteness take the first bit batch to have \(\lfloor d/2\rfloor\) bits. Thus the grid has \(a=2^{\lceil d/2\rceil}\) rows and \(b=2^{\lfloor d/2\rfloor}\) columns; put \(m=b\). For larger \(k\), work on the injective \(k\)-tuple module. Here \(E_\alpha\) and \(F_\beta\) are products of the local row and column Specht-isotypic projections, with full shape profiles \(\alpha=(\mu_i)_i\) and \(\beta=(\nu_j)_j\), where \(\mu_i\vdash b\) and \(\nu_j\vdash a\). Let the local levels be \(s_i=b-(\mu_i)_1\) and \(t_j=a-(\nu_j)_1\), with totals \(J_s,J_t\le k\), and put \(C_1=\sum_i s_i\log(b/s_i)+\sum_jt_j\log(a/t_j)\). The required angle estimate is \[ \log w\le Ck-\tfrac14\{k\log(n/k)-C_1\}_+. \tag{128}\] We give the full frame construction, including completely occupied rows. Fix the tuple’s row assignment. In one row let \(b\) be the number of sites, \(u\) the number of tuple labels, and \(s=b-\mu_1\) the local level. Branching requires \(0\le s\le u\le b\). Identify its observed labels with \([u]\) and embed its function isometrically in \(L^2(S_b)\) by completing to \(b\) labels and ignoring those outside \([u]\). All measures here are uniform probability measures.

For \(Z\subseteq[b]\), let \(P_Z\) be conditional averaging given the values at labels in \(Z\). This is a right-subgroup average, commuting with the left action on values. The sum over \(|Z|=s\) is right central. In the regular representation, the whole left \(\mu\)-isotypic space is \(V_\mu\otimes V_\mu^*\), with right action on the paired carrier. The invariant dimension for a subgroup permuting the \(b-s\) complementary labels is \(D_{\bar\mu}\) by branching, where \(\bar\mu\) is the lower diagram. Taking the trace on that right carrier therefore proves \[ \sum_{|Z|=s}P_Z=\kappa I,\qquad \kappa=\binom bs\frac{D_{\bar\mu}}{D_\mu}\ge1 \tag{129}\] on the entire left isotypic space, including its multiplicity. The inequality follows by choosing the entries below the first row of a standard tableau. Each \(P_Zf\) remains in this left type and is harmonic in its \(s\) selected values: a function of fewer selected labels cannot contain a type of level \(s\).

Since \(P_{[u]}f=f\), recover the original function by applying \(P_{[u]}\) to (129). Put \(l=|Z\setminus[u]|\) and \(v=b-u\). The only possible indices satisfy \[ 0\le l\le\min(s,v),\qquad |Z\cap[u]|=s-l. \tag{130}\] For such \(l\), conditional averaging of the unobserved values in \(P_Zf\) is precisely \[ P_{[u]}P_Zf =\frac{(-1)^l}{(v)_l} \sum_{\varphi:Z\setminus[u]\hookrightarrow[u]\setminus Z} (P_Zf)\big|_{x_z=x_{\varphi(z)},\ z\in Z\setminus[u]}. \tag{131}\] To prove this identity, average the \(l\) unobserved arguments injectively over the values not used by the observed \(u\) labels. Starting with distinctness among the selected arguments, use inclusion–exclusion to forbid also the values at \([u]\setminus Z\). Every term leaving an argument unassigned to one of these values vanishes by harmonicity. The surviving assignments are exactly the injections \(\varphi\) in the display, each with sign \((-1)^l\). Their number is \((u-s+l)_l\le(u)_l\). Every reassigned function has the same norm as \(P_Zf\), since its \(s\) distinct observed values have the same uniform injective marginal distribution.

Use \((v)_0=(u)_0=1\), also when \(v=0\). For \(l>0\) in (130), \(v\ge l\), so the denominator is strictly positive. In particular, for a full row \(u=b\) only \(l=0\) occurs; no quotient with a zero falling factorial is evaluated. By Cauchy–Schwarz and \(\sum_{|Z|=s}\|P_Zf\|^2=\kappa\|f\|^2\), the sum of the norms of the reassigned pieces, after division by \(\kappa\), is bounded by \(C_{b,u,s}\|f\|\), where \[ C_{b,u,s}=\kappa^{-1/2} \left[\sum_{l=0}^{\min(s,v)} \binom u{s-l}\binom vl \left(\frac{(u)_l}{(v)_l}\right)^2\right]^{1/2} \le e^{Cu}. \tag{132}\] An empty row has \(u=s=0\) and cost one. For a full row, the expression is \(\kappa^{-1/2}\binom bs^{1/2}\le2^{u/2}\). More generally, if \(v<2u\), then for every feasible \(l\) \((u)_l/(v)_l=\binom ul/\binom vl\le2^u\). Vandermonde’s identity bounds the sum of the binomial factors by \(\binom bs\le2^b\le2^{3u}\), proving the stated cost in this dense case. If \(v\ge2u\), then \(l\le u\le v/2\) and, for \(l>0\), \[\binom vl\left(\frac{(u)_l}{(v)_l}\right)^2 \le\left(\frac{4e u^2}{vl}\right)^l.\] Using \(\binom u{s-l}\le2^u\) and \(\sum_{l\ge0}(A/l)^l\le e^A\) with the \(l=0\) term defined as one (termwise, \(l!\le l^l\)), where \(A=4eu^2/v\le2eu\), proves (132) in the sparse case as well.

The construction also applies to entangled row vectors. With the fixed row assignment denoted by \(\mathbf u\), take \(P_{\mathbf Z}=\prod_iP_{Z_i}\) on the completed-label product space. The product of the central sums acts as \(\prod_i\kappa_i\) times identity on the full product isotypic space. Consequently \[f_{\mathbf u}=(\prod_i\kappa_i)^{-1} \sum_{\mathbf Z}(\prod_iP_{[u_i]})P_{\mathbf Z}f_{\mathbf u}, \qquad \sum_{\mathbf Z}\|P_{\mathbf Z}f_{\mathbf u}\|^2 =(\prod_i\kappa_i)\|f_{\mathbf u}\|^2.\] Conditional averaging and harmonicity hold with all other row variables fixed. Weighted Cauchy–Schwarz in this identity therefore multiplies the costs in (132), without any assumption that \(f_{\mathbf u}\) is a tensor product. Since \(\sum_i u_i=k\), the total cost is \(e^{Ck}\).

Group the reassigned pieces by their global exceptional subset \(X\subseteq[k]\). In the independent-coordinate extension they have the form \(H_X(\mathbf u,\mathbf v_X)\mathbf1_{\rm distinct}\), with \(|X|=J_s\) and at most \(2^k\) subsets. In each supported row pattern, exactly \(s_i\) labels of \(X\) lie in row \(i\). Set the raw function to zero on unsupported row patterns and on collisions among its selected columns. Conditional on a row pattern, the selected injective columns have the same marginals as under full row injectivity. Moreover the probability of full row injectivity is \(\prod_i(b)_{u_i}/b^{u_i}\ge e^{-k}\). Thus the raw independent-coordinate norms still cost at most \(e^{Ck}\). A column-isotype vector has the analogous pieces \(G_Y(\mathbf u_Y,\mathbf v)\mathbf1_{\rm distinct}\), where \(|Y|=J_t\) and exactly \(t_j\) labels of \(Y\) lie in column \(j\).

Conditional collisions and localization

The frame has paid only \(e^{Ck}\) and has not yet produced the saving in (128). We now use centering to force collisions among omitted labels, and localize the selected labels using their row and column counts.

The vectors in the global level-\(k\) type are harmonic after zero extension. Insert the centering projection \(\Pi=\prod_{\ell=1}^k(I-M_\ell)\) into their inner product, where \(M_\ell\) averages the independent cell of label \(\ell\). For labels in \(X\cup Y\), expand this product and let \(I\subseteq X\cup Y\) be the subset on which the identity factor is chosen. Write the cells supplied to the two functions as \((U_\ell^H,V_\ell^H)\) and \((U_\ell^G,V_\ell^G)\). For \(\ell\in I\) these are the same uniform cell. For \(\ell\in(X\cup Y)\setminus I\) they are independent uniform cells. Different labels are independent. In particular a label in \((X\cap Y)\setminus I\) supplies two independent selected cells; it is not a shared selected cell.

For each missing label in \(Z=[k]\setminus(X\cup Y)\), couple its two choices using main row and column variables \((U_\ell,V_\ell)\) and independent alternates \((U'_\ell,V'_\ell)\). The identity choice uses \((U_\ell,V_\ell)\) on both sides; the averaging choice uses \((U_\ell,V'_\ell)\) in \(H_X\) and \((U'_\ell,V_\ell)\) in \(G_Y\). The raw functions always see the same needed row \(U_\ell\) and column \(V_\ell\). Hence toggling a missing label changes only the two distinctness indicators. Their alternating sum cancels unless that label has a possible same-cell collision in some choice of side and cell version. Put \(M=|Z|\) and condition first on all nonmissing variables. The raw functions have separated remaining variables \(H(U),G(V)\). Whenever the alternating sum is nonzero, the graph of possible collisions has a forest covering the missing vertices. In every component meeting nonmissing vertices, grow a forest from all those vertices as separate roots; then each tree has exactly one nonmissing root. Span each wholly missing component by one tree, which has at least two vertices and needs one free root. Thus every child exposed along a forest edge is missing, and there are at least \(M/2\) edges. Choosing parents, sides, and cell versions costs \(e^{O(k)}k^{\text{number of edges}}\). Exposing parent before child, each specified child cell is independent uniform, so every edge costs \(1/n\). Uniformly under the conditioning, the coverage probability is at most \(e^{O(k)}(k/n)^{M/2}\).

Let \(K(U,V)\) be the alternating sum after averaging alternate coordinates. Jensen’s inequality and its \(2^M\) summands give \(\mathbb E|K|^2\le4^M\Pr(\text{coverage})\). It vanishes unless the cells in \(O=X\cap Y\cap I\) are distinct. Writing \(A_1=(\mathbb E_U|H|^2)^{1/2}\) and \(B_1=(\mathbb E_V|G|^2)^{1/2}\), the conditional Cauchy–Schwarz bound is therefore \[ e^{O(k)}(k/n)^{M/4}{\bf1}_{\{O\text{ distinct}\}}A_1B_1. \tag{133}\] Here the factorization \(\mathbb E_{U,V}|H(U)G(V)|^2=A_1^2B_1^2\) is essential: an unconditional probability estimate alone would not control the weighted functions.

The dependence of these two weights will also matter in the next step. Put \(N=X\cup Y\). After averaging the missing rows, \(A_1\) is measurable with respect to \[\mathcal F_H=\sigma\big((U_\ell^H)_{\ell\in N}, (V_\ell^H)_{\ell\in X}\big).\] Similarly, after averaging the missing columns, \(B_1\) is measurable with respect to \[\mathcal F_G=\sigma\big((V_\ell^G)_{\ell\in N}, (U_\ell^G)_{\ell\in Y}\big).\] Only the cells in \(O=X\cap Y\cap I\) are selected on both sides with a shared value. Given \(\mathcal F_H\), the columns \((V_\ell^G)_{\ell\in Y\setminus O}\) are still independent and uniform; given \(\mathcal F_G\), the rows \((U_\ell^H)_{\ell\in X\setminus O}\) have the analogous property. For a label selected on both sides but outside \(I\), this follows from the independent versions just specified.

Stratify the nonmissing variables by the row and column counts \(p_i,q_j\) of \(O\), whose size is \(o\). There are at most \((k+1)^{a+b}=e^{O(k)}\) strata because \(k\ge n^{3/5}\) and the grid is balanced. On a realizable stratum \(p_i\le s_i,q_j\le t_j\). For \(o>0\), the entropy of the uniform measure on its distinct cells is \(\log o\), bounded by the sum of its marginal entropies. Hence \[\sum_i p_i\log(b/p_i)+\sum_jq_j\log(a/q_j) \ge o\log(n/o).\] Using \(\sum_i p_i\log(s_i/p_i)\le J_s/e\) and its column analogue, with zero terms interpreted continuously, gives \[ \sum_i p_i\log(b/s_i)+\sum_jq_j\log(a/t_j) \ge o\log(n/k)-2k/e. \tag{134}\] This is also true when \(o=0\).

We make the localization step explicit. In the average of \(A_1B_1\) on a stratum, apply Cauchy–Schwarz, keeping the stratum and the \(Y\)-column profile in the \(A_1^2\) factor and the stratum and the \(X\)-row profile in the \(B_1^2\) factor. Given \(\mathcal F_H\), the cells of \(O\) are known and the columns seen by \(G\) on \(Y\setminus O\) remain independent uniform columns. The probability of the remaining column counts \(r_j=t_j-q_j\), with \(N_Y=|Y|-o\), is multinomial. Its logarithm is at most \[\begin{align*} \log\frac{N_Y!}{\prod_jr_j!}-N_Y\log b &\le-N_Y\log(n/k)+\sum_jr_j\log(a/t_j)+O(k). \end{align*}\] Indeed \(N_Y!\le k^{N_Y}\), \(r!\ge(r/e)^r\), and \(\sum_jr_j\log(t_j/r_j)\le J_t/e\). For the other factor the same argument gives the probability bound \[\exp\left\{-(|X|-o)\log(n/k) +\sum_i(s_i-p_i)\log(b/s_i)+O(k)\right\}.\] The unweighted second moments are the squared raw norms. Taking square roots of the two probabilities and using (134) bounds the localization factor by \[\|H\|_2\|G\|_2 \exp\left\{O(k)-\tfrac12[(|X|+|Y|-o)\log(n/k)-C_1]\right\}.\] Also \(|X|+|Y|-o\ge|X\cup Y|=k-M\), and the trivial Cauchy–Schwarz bound is available. We thus obtain the positive-part saving \(\tfrac12((k-M)\log(n/k)-C_1)_+\). Finally, for \(L=\log(n/k)\ge0\), \[ML/4+((k-M)L-C_1)_+/2\ge(kL-C_1)_+/4.\] Combining this with (133), and summing the strata, centering choices, and frame pieces, proves (128).

The tuple trace endpoint

The angle estimate (128) is now complete. It remains to bound the positive trace endpoint, including the global copy count and all row and column assignment factors. We now estimate the trace endpoint in (123). Write \(n=ab\), with \(a\) rows of size \(b\) and \(b\) columns of size \(a\). Put \(X=A_\alpha^{2p}\) and \(Y=B_\beta^{2p}\) on the injective tuple module. In a diagonal entry of \(YX\), an intermediate tuple must have both the starting row assignment, because \(X\) preserves rows, and the starting column assignment, because \(Y\) preserves columns. It is therefore the starting tuple itself. Consequently \[\mathop{\mathrm{Tr}}(YX)=\sum_{z\ {\rm injective}}Y(z,z)X(z,z),\] and both diagonals are nonnegative.

For a tuple with column counts \(v_j\), consider the local positive group-algebra element of \(Y\) in column \(j\). Its identity coefficient is \(T_a^{\nu_j}(p)/a!\) and the modulus of every coefficient is at most this value, by positivity in the regular representation. The diagonal entry in the local tuple action sums coefficients on the pointwise stabilizer of its \(v_j\) labels, of size \((a-v_j)!\). It is thus at most \(T_a^{\nu_j}(p)/(a)_{v_j}\). Equivalently this is positive coefficient restriction to that stabilizer. Since \(\sum_jv_j=k\) and \((a)_v\ge(a/e)^v\), \[ Y(z,z)\le(e/a)^k\prod_jT_a^{\nu_j}(p). \tag{135}\]

Fix the complete row assignment of the labeled tuple, with counts \(u_i\). The local row tuple module is \(\operatorname{Ind}_{S_{b-u_i}}^{S_b}{\bf1}\), in which the multiplicity of \(\mu_i=(b-s_i,\bar\mu_i)\) is \(f^{\mu_i/(b-u_i)}\). It is zero if \(u_i<s_i\). Otherwise separating the entries below the first row gives \[f^{\mu_i/(b-u_i)}\le\binom{u_i}{s_i}D_{\bar\mu_i}.\] The hook formula also gives \[ D_{\mu_i}\ge e^{-s_i}\binom b{s_i}D_{\bar\mu_i}. \tag{136}\] Indeed the hooks below the first row are exactly those of \(\bar\mu_i\). If \(r=b-s_i\), the first-row hook product divided by \(r!\) is \(\prod_{h=1}^r(1+(\bar\mu_i)'_h/(r-h+1))\); its logarithm is at most \(\sum_h(\bar\mu_i)'_h=s_i\).

The trace of the local row operator is its irreducible trace times this multiplicity. Hence, for the fixed row assignment, its total row trace equals \[\prod_i T_b^{\mu_i}(p) \frac{f^{\mu_i/(b-u_i)}}{D_{\mu_i}}.\] Using (136), \(\binom b{s}\ge(b/s)^s\), and \(\binom u{s}\le(eu/s)^s\), the product of ratios is at most \[\exp\left\{-C_H+O(k)\right\},\qquad C_H=\sum_i s_i\log(b/s_i).\] Here \(\sum_i s_i\log(u_i/s_i)\le\sum_i u_i/e=k/e\) and \(\sum_i s_i\le k\); zero terms are interpreted continuously.

The number of row assignments with every \(u_i\ge s_i\) is at most \[ a^k\exp\{C_H-J_s\log(n/k)+O(k)\}. \tag{137}\] For a uniform independent row assignment, choose disjoint witness sets of \(s_i\) labels required to hit row \(i\). There are at most \(k^{J_s}/\prod_i s_i!\) such choices, each of probability \(a^{-J_s}\). The union bound and \(s!\ge(s/e)^s\) give \[\log\Pr(u_i\ge s_i\ \forall i) \le J_s\log(k/a)-\sum_i s_i\log s_i+O(k) = C_H-J_s\log(n/k)+O(k),\] which proves (137).

Combine the trace per assignment, the count of assignments, and (135). The \(a^k\) cancels and gives \[\mathop{\mathrm{Tr}}(YX)\le \left(\prod_iT_b^{\mu_i}(p)\prod_jT_a^{\nu_j}(p)\right) e^{-J_s\log(n/k)+O(k)}.\] Interchanging rows and columns gives the same inequality with \(J_t\). The global tuple multiplicity is \(L_\lambda=D_{\bar\lambda}\), and \(D_\lambda/L_\lambda\le\binom nk\le(en/k)^k\). Thus the full normalized endpoint satisfies \[ \log\left(\frac{D_\lambda}{L_\lambda} \mathop{\mathrm{Tr}}(YX)\right) \le\sum_i\log T_b^{\mu_i}(p)+\sum_j\log T_a^{\nu_j}(p) +(k-\max(J_s,J_t))\log(n/k)+O(k). \tag{138}\] Pairs with zero endpoint require no logarithmic estimate. There are only \(e^{O(k)}\) relevant profile pairs in this range. Indeed the level lists have at most \((k+1)^{a+b}\) choices, and, for fixed lists, the partition bound gives at most \(\exp(C\sum_i\sqrt{s_i}+C\sum_j\sqrt{t_j})\) tail choices. Cauchy–Schwarz bounds the exponent by \(O(\sqrt{ak}+\sqrt{bk})\). Since \(a,b\asymp\sqrt n\) and \(k\ge n^{3/5}\), both this exponent and \((a+b)\log(k+1)\) are \(O(k)\).

Closing the level budget

In both inductions, a trivial child has \(T=1\) and zero level and diagram budgets. If a child sweep block is zero, its profile has zero trace endpoint and can be discarded. Every remaining child satisfies the height condition by Lemma 3, so the stated induction hypotheses apply to all child terms retained below.

Insert the angle (128), the endpoint bound (138), and the profile count into (123). The remaining task is to compare the sum of child level budgets with the parent budget. Write \(\delta=\log(n/k)/\log n\), let \(\omega_i=(s_i/k)(\log b/\log n)\) for row factors and use the corresponding column weights. For a positive local level \(s_i\) in a block of size \(m_i\), put \(\delta_i=\log(m_i/s_i)/\log m_i\), where \(m_i=b\) on rows and \(m_i=a\) on columns (with \(s_i\) replaced by \(t_i\) there). At level zero set \(\delta_i=0\); its weight is zero and the trivial child moment is one. Put \[\bar u=\max\{u_{\lfloor d/2\rfloor},u_{\lceil d/2\rceil}\}, \qquad W_0=\sum\omega_i, \qquad \xi=(\delta-\sum\omega_i\delta_i)_+.\] Then \[W_0\le\max(J_s,J_t)/k,\qquad \sum\omega_i\delta_i^2\ge(2-W_0)\delta^2-2\xi.\] For the second inequality, expand \(\sum_i\omega_i(\delta_i-\delta)^2\ge0\) and use \(\sum_i\omega_i\delta_i\ge\delta-\xi\). This gives \(\sum_i\omega_i\delta_i^2\ge(2-W_0)\delta^2-2\delta\xi\); since \(0\le\delta\le1\), it implies the displayed bound. Subtracting the target level budget and dividing by \(k\log n\) leaves at most \[ -(\bar u+\Lambda\delta^2-\delta)(1-W_0) +(2\Lambda-(p_0-1)/2)\xi -(u_d-\bar u)+O(p_0/\log n). \tag{139}\] The first two terms are nonpositive by (119); the parameter increment, of order \(d^{-1/3}\) at a balanced split, pays the last error. This proves (121).

Long chains and the diagram dimension

It remains to treat \(\delta<\epsilon\), so \(k\ge n^{1-\epsilon}\). For the two moment inequalities we may assume the parent block is nonzero, since zero moments were handled above. Throughout this subsection the theorem’s height condition is \(\lambda'_1\le n/2\). Put \(T=n^{1-\gamma_d}\) and let \(a_1,b_1\) be the numbers of full rows and full columns of \(\lambda\) of length at least \(T\). Split the diagram into all boxes in its top \(a_1\) rows, then all boxes in its first \(b_1\) columns below those rows, and the translated straight diagram \(\theta\) remaining in the lower right (Figure 2). The first two regions are disjoint chains, with lengths \(\eta_i=\lambda_i\) and \(\zeta_j=(\lambda'_j-a_1)_+\), respectively. Write \[R=|\theta|,\qquad M=n-R,\qquad G=\sum_{l\ {\rm in}\ \eta,\zeta}l\log(M/l),\qquad D_0=1+a_1+b_1=O(n^{0.01}).\] The bound on \(D_0\) follows from \(a_1,b_1\le n/T=n^{\gamma_d}\) and \(\gamma_d<0.01\). Set \(G=0\) when \(M=0\).

Every tail cell pays the cap \(v_d\log n\), since both of its full line lengths are below \(T\). In a top row, replacing the maximum of the full row and column lengths by the row length can change the contribution only in the first \(b_1\) columns, at most \(a_1b_1\) cells. This has total cost \(O(c_d a_1b_1\log(en))\). Below the top rows, in a long column the maximum is its full column height. Replacing that height \(\zeta_j+a_1\) by its chain length \(\zeta_j\) changes the logarithmic sum by at most \[\zeta_j\log(1+a_1/\zeta_j)\le a_1\] for each nonempty chain. Thus the chain contribution is \(c_d\sum_l l\log(n/l)\) up to the same stated error. Finally \(\sum_l l\log(n/l)=G+M\log(n/M)\) and \(M\log(n/M)\le R\). We have proved \[ \mathcal D_d(\lambda) =c_dG+v_dR\log n+O(c_d(R+D_0^2\log(en))). \tag{140}\]

We also need a hook-product bound for an arbitrary diagram \(\mu\vdash L\), \(L\le n\), using these same values of \(a_1,b_1\). Let \(l\) be its top-row and lower-column chain lengths, and let \(\vartheta\) be its translated residual diagram of size \(q\). Then \[ D_\mu\ge\frac{L!D_\vartheta}{q!\prod_l l!} \exp\{-C(q+D_0^2\log^2(en))\}. \tag{141}\] Here is the hook comparison in detail. Tail hooks are exactly those of \(\vartheta\). On a top row, compare each hook with the baseline number of cells remaining in that row, including the current cell. Cells in the first \(b_1\) columns cost at most \(O(a_1b_1\log(en))\) altogether. In the other columns, the extra leg has at most \(a_1\) boxes in the top region plus the height of the corresponding tail column. The first addition costs \(O(a_1\log(en))\) per row by the harmonic sum; the two additions can be separated using \(\log(1+x+y)\le\log(1+x)+\log(1+y)\).

Let the tail have width \(w\) and nonincreasing column heights \(h_1,\ldots,h_w\), of sum \(q\). If \(q>0\), every top row extends at least through column \(b_1+w\), so the tail addition for that row is bounded by \[\sum_{t=1}^w\log\left(1+\frac{h_t}{w-t+1}\right).\] When \(w\le D_0\log(en)\), there are at most \(a_1w\) affected top-row cells, each costing at most \(\log(en)\), for a total \(O(D_0^2\log^2(en))\). When \(w>D_0\log(en)\), use \[\sum_{t=1}^w\frac{h_t}{w-t+1} \le \frac{2q}{w} +\frac{2q}{w}\sum_{r=1}^{\lceil w/2\rceil}\frac1r =O\!\left(\frac q w\log(en)\right).\] For the first half of the sum the denominators are at least \(w/2\); for the second half monotonicity gives \(h_t\le2q/w\). After multiplication by the at most \(a_1\) top rows, this is \(O(q)\).

For the lower-column chains compare hooks with the number of remaining cells in their column. The extra arm has at most \(b_1\) boxes in the left region plus the appropriate tail row length. The \(b_1\) addition has total cost \(O(b_1^2\log(en))\). The tail addition has the identical bound with width and height interchanged: every left column extends through the tail’s rows, and its row lengths are nonincreasing with sum \(q\). If \(q=0\), both tail-addition terms are absent. The resulting total logarithmic inflation over the product \((q!/D_\vartheta)\prod_l l!\) is \(O(q+D_0^2\log^2(en))\), proving (141).

At the parent, every hook of \(\theta\) is at most \(2n^{1-\gamma_d}\), because all its full row and column lengths are below the threshold. Therefore \(D_\theta/R!\ge(2n^{1-\gamma_d})^{-R}\). Also \((n)_R\ge(n/e)^R\) and factorial estimates give \(\log(M!/\prod_l l!)=G+O(D_0\log(en))\). Applying (141) yields \[ \log D_\lambda\ge G+\gamma_dR\log n-O(R+D_0^2\log^2(en)), \qquad G+R\log n\ge k/2 . \tag{142}\] For the second assertion, if \(M>0\) and \(l_{\max}\) is the largest chain length, \(-\log x\ge1-x\) gives \[G\ge M-\frac{\sum_l l^2}{M}\ge M-l_{\max}.\] Every top chain has length at most \(\lambda_1=n-k\), and every lower-column chain has length at most \(\lambda'_1\le n/2\). Consequently \(G+R\ge n-l_{\max}\ge\min(k,n/2)\ge k/2\). If \(M=0\) the same inequality is immediate from \(R=n\). For sufficiently large \(d\), \(\log n\ge1\), proving the displayed version.

Color multiplicities and the marked trace

The arm comparison has expressed the parent budget in terms of \(G\) and \(R\), and (142) supplies its dimension scale. To apply (123), we still need the local copy counts, the positive trace with distinct markers, the child diagram costs, and the color angle. We establish them in that order.

Let \(\mathcal H\) be the space of configurations of \(R\) distinctly labeled even markers and signed colors in \(\mathbb C^{a_1}\oplus\mathbb C^{b_1}\). Every marker is used exactly once. Thus \(\mathcal H\) is the orthogonal sum, over the ordered marker-position tuples, of the signed tensor spaces on the remaining \(M\) sites. The compact group \(K=U(a_1)\times U(b_1)\) acts only on colors; zero factors are omitted. The selected global type is the irreducible representation \[\begin{gathered} \pi=\pi_{(\eta,\zeta)}:K\longrightarrow U(\mathcal U_{\eta,\zeta}),\\ \mathcal U_{\eta,\zeta} =\mathbf S_\eta(\mathbb C^{a_1}) \otimes\mathbf S_\zeta(\mathbb C^{b_1}), \end{gathered}\] where the carrier factor belonging to a zero group factor is also omitted. Its carrier action extends polynomially to the invertible parity-preserving block matrices. Take \(S\) to be the full compact \(\pi\)-isotypic projection on \(\mathcal H\), including all multiplicity copies. No additional projection is put on the marker labels.

Indeed, by fixing the even, odd, and marker site pattern and then inducing, Schur–Weyl duality identifies this color isotype on the permutation side with induction from the Specht factors \(V_\eta,V_{\zeta^{\mathsf t}}\), with the markers fixed pointwise. Stacking \(\zeta^{\mathsf t}\) below \(\eta\) gives precisely the unmarked hook subdiagram. Its Littlewood–Richardson coefficient is at least one: the skew part below \(\eta\) is a translated straight diagram with its row-constant Littlewood–Richardson tableau. Adding the \(R\) ordered markers by branching then gives at least \(f^{\lambda/(\text{unmarked hook})}=D_\theta\) copies of \(V_\lambda\). The compact carrier dimension can only increase this multiplicity, so in (123) we may take \(L_\lambda=D_\theta\). Separating the entry sets in the chains and the tail of a standard tableau gives \[ \frac{D_\lambda}{L_\lambda} \le \binom nR\frac{M!}{\prod_h l_h!} \le \binom nR e^G. \tag{143}\] The last inequality is the elementary multinomial entropy bound.

In each row include both the local permutation isotype \(\mu_i\) and local color isotype \((\eta^{(i)},\zeta^{(i)})\) in \(E_\alpha\); use \((\nu_j,\eta^{[j]},\zeta^{[j]})\) in each column for \(F_\beta\). The superscripts \((i)\) and \([j]\) distinguish row and column partitions; subscripts denote their parts. Local color projectors commute with local permutations. They also commute with the global color projection because they commute with every element of their local color group, including the corresponding factor of every diagonal global rotation. Thus these projections have all the commutations needed in (123). Their degrees fix the marker counts \[x_i=b-|\eta^{(i)}|-|\zeta^{(i)}|,\qquad y_j=a-|\eta^{[j]}|-|\zeta^{[j]}|,\qquad \sum_i x_i=\sum_jy_j=R.\] Only nonnegative counts contribute. For \(M_i=b-x_i\) define \[G_i=\sum_{l\ {\rm in}\ \eta^{(i)},\zeta^{(i)}}l\log(M_i/l), \qquad G_H=\sum_iG_i,\] and define \(G'_j,G_V\) analogously in columns. Empty entropies are zero.

We need the local multiplicity with one fixed assignment of marker labels to a row, while their positions within that row still vary. The unmarked permutation shapes \(\rho\vdash M_i\) have coefficients \(c_{\eta^{(i)},(\zeta^{(i)})^{\mathsf t}}^\rho\). The full local multiplicity of \(\mu_i\) is therefore \[ \operatorname{mult}_i =(\dim\eta^{(i)})(\dim\zeta^{(i)}) \sum_{\rho\subseteq\mu_i} c_{\eta^{(i)},(\zeta^{(i)})^{\mathsf t}}^\rho f^{\mu_i/\rho}. \tag{144}\] Here the two dimensions are compact-group carrier dimensions, and the sum includes only shapes with nonzero coefficient.

For clarity, we record the size bounds used in this sum. Every such \(\rho\) contains \(\eta^{(i)}\) and \((\zeta^{(i)})^{\mathsf t}\) and lies in the \((a_1,b_1)\) hook. For the latter assertion use a Littlewood–Richardson tableau of \(\rho/(\zeta^{(i)})^{\mathsf t}\) with content \(\eta^{(i)}\). Beyond column \(b_1\) its columns have at most \(a_1\) boxes, by column strictness. Let \(l^0\) be the vector of its top-row and lower-column chain lengths, padded by zeros. Its top counts dominate the parts of \(\eta^{(i)}\), while the deficit of each lower-column count from the corresponding part of \(\zeta^{(i)}\) is at most \(a_1\). Since the two vectors have the same total \(M_i\), their total absolute discrepancy is at most \(2a_1b_1\). It follows that \[ \sum_h l_h^0\log(M_i/l_h^0) =G_i+O(D_0^2\log(en)). \tag{145}\] One may bound the entropy change per changed integer unit by \(O(\log(en))\), including the transition between zero and one.

The same tableau argument bounds the coefficient in (144). The top \(a_1\) rows of \(\rho\) contain at least \(|\eta^{(i)}|\) boxes, and at most \(a_1b_1\) of those belong to the base shape \((\zeta^{(i)})^{\mathsf t}\). Thus at most \(a_1b_1\) boxes of the skew tableau lie below the top region. In the top region, a weakly increasing row is specified by its counts of the at most \(a_1\) letters, giving at most \((n+1)^{a_1^2}\) choices. Below it there are at most \(\max(1,a_1)^{a_1b_1}\) choices. The number of possible hook shapes \(\rho\) is at most \((n+1)^{a_1+b_1}\), and the compact carrier dimensions are \(e^{O(D_0^2\log(en))}\) by the Weyl dimension formula. All these factors therefore fit that exponential bound. In particular, (141) and (145) give \[ \log D_\rho\ge G_i-O(D_0^2\log^2(en)). \tag{146}\]

For each contributing \(\rho\subseteq\mu_i\), let \(l_{ih}\) be the full chain lengths of \(\mu_i\), and let \(l^0_{ih}\) be those of \(\rho\). Write \[e_{ih}=l_{ih}-l^0_{ih}\ge0,\qquad K_i(\rho)=\sum_h\log\binom{l_{ih}}{e_{ih}}.\] If the tail of \(\mu_i\) has shape \(\theta_i\) and size \(q_i\), then \(q_i+\sum_he_{ih}=x_i\). Separating the entries in its tail and chain extensions yields \[f^{\mu_i/\rho}\le \frac{x_i!D_{\theta_i}}{q_i!\prod_he_{ih}!}.\] Dividing by (141), with \(L=b\), leaves \(x_i!\prod_hl_{ih}!/(b!\prod_he_{ih}!)\) times \(e^{O(x_i+D_0^2\log^2(en))}\). Factor out the chain binomials and use (145) to obtain \[ \frac{\operatorname{mult}_i}{D_{\mu_i}} \le\binom b{x_i}^{-1} \exp\{K_i-G_i+O(x_i+D_0^2\log^2(en))\}, \tag{147}\] where, once and for all, choose a contributing \(\rho_i\) maximizing \(K_i(\rho)\) and set \(K_i=K_i(\rho_i)\). The identity behind the entropy term is \(\prod_h(l^0_{ih})!/M_i!\) after extracting the inverse binomial; factorial errors and the sum in (144) have the stated size. Zero local spaces can be discarded.