Network ancestry and previous mixing bounds

Thorp introduced the shuffle in his study of shuffling and Faro (Thorp 1973). For power-of-two decks, Morris’s 2005 preprint proved the first polynomial bound, \(O(d^{44})\), using evolving sets and a chameleon process (Morris 2008). Montenegro and Tetali’s spectral-profile and evolving-set analysis gave \(O(d^{29})\) (Montenegro and Tetali 2006, Theorems 6.14–6.15). Morris then used entropy contraction to prove \(O((\log N)^4)\) for every even deck size (Morris 2009), and sharpened the contraction over a sweep to obtain \(O(d^3)\) when \(N=2^d\) (Morris 2013, Lemma 7 and Theorem 8). These bounds concern the full permutation. Our argument bounds the joint routing densities and converts them into matrix contraction on each irreducible representation.

The reflected butterfly has the topology of the classical Beneš network (Beneš 1964). Beneš’s rearrangeability result concerns which permutations can be routed. Morris already studied the fair-switch sweep–reflection law under the name zigzag shuffle (Morris 2008, sec. 4). The expanded experiment has \(2d\) layers. Its two central layers average the same subgroup, so their product has the law of one such average and gives the usual \(2d-1\)-layer endpoint description. We retain both layers when counting internal routing choices.

Gelman and Ta-Shma analyzed this random network through its two-child recursion (Gelman and Ta-Shma 2014, sec. 4, Proposition 1). Their Theorem 4 and Lemma 5 give total-variation error at most \(k(k-1)/(2N)\) for the image of an unordered \(k\)-subset. Our estimate concerns ordered injections and a higher density moment, including dense tuples. The alternating-color calculation below is the routing structure behind the recursion; the extra work is to control its cycle counts under the actual random switch law.

Partial-permutation questions also arise in cryptography. Morris, Rogaway and Stegers bounded the joint positions of prescribed cards in their analysis of small-domain encryption (Morris et al. 2009, 2018). Czumaj and Vöcking proved that, for every fixed \(0<c<1\), the joint positions of any prescribed \(\lfloor cN\rfloor\) cards mix in \(O((\log N)^2)\) physical layers by a non-Markovian coupling (Czumaj and Vöcking 2014). Their full-permutation application pads the network with empty cards. Czumaj later obtained logarithmic-depth partial-permutation bounds for other switching networks satisfying an expansion condition (Czumaj 2015, Theorems 3.4–3.6). The fixed tracked fraction, padding, and choice of network distinguish these results from mixing the unchanged full-deck Thorp chain.

The passage from Fourier estimates to total variation follows the finite-group method of Diaconis and Shahshahani (Diaconis and Shahshahani 1981). For a conjugacy-invariant law, the Fourier matrices are scalar and can be estimated through character ratios. A directed coordinate sweep gives matrix products of projections, so its singular values and its nonnormal powers must both be controlled. The inverse-dimension summation used in the final step is a special case of Liebeck–Shalev (Liebeck and Shalev 2004, Proposition 2.5 and Theorem 2.6); we include an elementary proof of the estimates needed here. Sharp versions allowing the exponent to decrease with \(N\) are now known (Teyssier and Thévenin 2025, Proposition 1.8). Recent character bounds also yield cutoff and its profile, relative to the appropriate parity coset, for nontrivial conjugacy-class walks with a positive fraction of fixed points (Olesker-Taylor et al. 2025; Teyssier 2026). Those scalar estimates do not provide the matrix contraction required for a coordinate sweep.

Young branching, hook lengths, and Schur orthogonality connect the ordered routing densities to individual Fourier blocks (Sagan 2001; Stanley 1999; Vershik and Okounkov 2005). Later we use the commuting position and label actions on injections (Dukes et al. 2020, sec. 3.2) and the associated transposition-content formula for coordinate deletion (Araujo and Bratten 2017, Lemma 3.1 and Theorem 3.5). These algebraic identities identify the harmonic spaces; the probabilistic work is to bound the loss of harmonic level when the network splits.

The first proof and the further estimates

Splitting the reflected network at its outer coordinate leaves two independent smaller networks. Prescribing the endpoints of some cards puts two matchings on those cards: one records common input switches, the other common output switches. Their union consists of alternating paths and cycles. Each component has two possible assignments to the children, and each cycle creates one extra factor of two in the route count. Section 3 gives the exact density identity and separates uniform auxiliary colorings from the actual switch law. This distinction identifies the probability measure under which a discarded-density tail must be bounded.

Section 4 completes the first proof. We mark several cycles in distinguished slots, expose their routes, and compare the number of choices of their starts with the probability that their last paths close. A contact bound controls the switches already known at those closures. Factorial moments then bound cycles at each height. Conditional estimates over alternating height bands sum the bounds without assuming independence between heights.

The density estimate and the multiplicity cutoff cover shapes with long first rows and those with very large dimensions. To handle the remaining dimensions, replace fixed-size central subnetworks by uniform permutations, allowing identity on a small specified set of blocks. The modified density moments have arbitrarily small cost per card. The original positive central operator is bounded by a sum of these modified operators and an exponentially small remainder. This completes the dimension-power estimate. Its Fourier consequence uses submultiplicativity and Schatten norms; a power of \(T_N^*T_N\) is never identified with a power of the generally nonnormal \(T_N\).

Section 5 gives an independent certificate argument. It uses reciprocal cycle lengths to retain explicit density costs for dense tracked sets, including the margins needed at densities \(7/25\) and \(1\). Section 6 instead proves an exponential cost per tracked card by encoding a permutation while omitting the bits forced by its closing routes. Its pointwise consequence applies to both \(T_N^*T_N\) and \(T_NT_N^*\), for every injection size, after a fixed number of compositions. Section 6.6 gives a separate certificate and entropy-window proof of that density bound.

The first density theorem already implies an \(e^{Ck}\) moment bound. The later density arguments give different mechanisms and lead to pointwise smoothing and lower-diagram estimates. In particular, Section 7 proves a contact-cancellation bound uniform in the number of tracked cards. Summing out a tuple slot annihilates a representation at its first injection level; a weighted forest count turns this cancellation into sparse-level contraction.

The remaining methods retain representation data beyond dimension alone. Put \(k=N-\lambda_1\), \(\beta=(\lambda_2,\lambda_3,\ldots)\), and \(h_N(k)=k\log(eN/k)\), with \(h_N(0)=0\). The dimension \(D_\beta\) detects complexity below the first row that the level \(k\) alone cannot measure. A fixed trace moment controls the combined mass of singular values, and can therefore be used before the final amplification to the regular representation. Table 1 records these outputs; its constants are absolute and need not agree between rows.

The Casimir proof compares the transposition sum with its two child sums; the sum defect and squared imbalance require different matrix estimates. The harmonic proof bounds the loss caused by removing slots, then transfers cycle moments to either lower-diagram dimension or tuple trace. These arguments share the elementary tensor-swap estimate, but use different level recursions. The alphabet proof changes its tensor realization as descendant diagrams shrink and pays the resulting multiplicity costs across the tree. The core-cutoff proof chooses between a diagram bound and a bound using the actual trace at the current recursion frontier. Its cutoff is a projection onto small product dimensions. Each route supplies its own final passage to the full permutation law using the common Fourier preliminaries.

The companion papers use several of these interfaces while retaining their own arguments. The compatibility-entropy paper uses the shared-switch contact bound in Lemma [n:butterfly-contacts] in a sparse path second-moment estimate (OpenAI 2026a, Lemma 3.1). Prescribed-type signed tensor moments and one-sided projection-overlap bounds are developed separately in (OpenAI 2026e, Theorems 1.1 and 3.2). The row–column geometry paper combines Theorem 14 and Proposition 16 with a coherent-overlap argument to obtain a dimension-weighted fixed moment (OpenAI 2026d, Theorem 10.1). The random-subspace paper applies Corollary 15, in both positive orientations, in its Proposition 2.1; complex random-plane tests then give a regular trace at most \(1+N^{-10}\) (OpenAI 2026c, Theorem 1.1). An independent conditional-marginal proof gives the explicit bound of \(1600d\) physical shuffles for total-variation distance tending to zero (OpenAI 2026b, Theorem 1.1).

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.

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 \[T_n=\Pi_d\cdots\Pi_1,\qquad K_n=T_n^*T_n, \qquad n=2^d.\] At the one-position recursive base, the empty product gives \(T_1=K_1=I\).

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. Together with Cauchy–Schwarz, it gives the finite-group Fourier upper bound used by Diaconis and Shahshahani (Diaconis and Shahshahani 1981, sec. 2, Lemma 2; Section 3, Lemma 14). 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{1}\] 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{2}\] 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{3}\] 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{4}\] 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 conclusions below are special cases of Liebeck–Shalev (Liebeck and Shalev 2004, Proposition 2.5 and Theorem 2.6). We include an elementary proof of the estimates needed here, together with a lower bound for individual dimensions.

Alternating colors and multiplicity

Fix an ordered list of \(k\) input positions and a candidate list of \(k\) distinct output positions. At one node, make a graph on its tracked paths, joining two when they use the same outer input switch or the same outer output switch. Its degree is at most two. Input and output edges alternate; parallel edges form a cycle. If \(s\) paths are present, \(a\) is the number of edges, and \(C\) is the number of cycles, the number of proper assignments of paths to the two children is \[2^{s-a+C}.\] Indeed a path component has one more vertex than edge, whereas a cycle has equally many. Each component admits two child assignments, obtained by exchanging the colors. Thus each cycle supplies one factor of two beyond \(2^{s-a}\), as illustrated in Figure 1.

Each assignment prescribes \(2s-a\) independent outer coins, hence costs \(2^{-(2s-a)}\). Their combined factor is \(2^{-s+C}\). Recursing through the nodes and choosing proper colorings uniformly gives a density relative to the uniform injection with excess exponent \[ X=\sum_{j=1}^d C_j+\log_2\frac{(N)_k}{N^k}, \tag{5}\] where \(C_j\) totals tracked cycles at height \(j\). We distinguish the auxiliary coloring law from the actual switch law. For fixed input and output injections \(x,y\), let \(\omega\) be a legal complete tree of child colorings. At a node \(v\), write \(s_v,e_v,C_v\) for its path, edge and cycle counts, and put \(a_v=2^{s_v-e_v+C_v}\). The auxiliary weight and actual routing-event weight are respectively \[q_{xy}(\omega)=\prod_v a_v^{-1},\qquad w_{xy}(\omega)=\prod_v2^{-(2s_v-e_v)},\qquad \frac{w_{xy}(\omega)}{q_{xy}(\omega)} =N^{-k}2^{\sum_vC_v}.\] The last identity uses \(\sum_vs_v=kd\). At the leaves the routing is determined. Summing unused switch coins contributes one, so \(w_{xy}(\omega)\) is exactly the probability of the corresponding endpoint-and-coloring event. Thus \[K_N(x,y)=\sum_\omega w_{xy}(\omega) =\frac1{(N)_k}\mathbb E_{q_{xy}}2^X.\] For the certificate alternative in Section 5, one may truncate the routing event itself. Define \(A(x,y)=\sum_\omega w_{xy}(\omega)\mathbf1_{\{X\le L\}}\) and \(E=K_N-A\). Then \(A(x,y)\le2^L/(N)_k\), while \[ \sum_y E(x,y)=\sum_{y,\omega}w_{xy}(\omega)\mathbf1_{\{X>L\}} =\mathbb P_{\mathrm{actual},x}(X>L). \tag{6}\] Indeed \((y,\omega)\) partitions the actual switch experiment. The tail estimates below therefore bound discarded mass under the actual network law, without identifying that law with the auxiliary uniform-coloring law. The factor \((N)_k/N^k\) is essential: the endpoints form an injection, not a tuple sampled with replacement.

The first proof in Section 4 instead truncates the endpoint density: it retains an entry when \((N)_kK_N(x,y)\le z\). Its density moment bounds the discarded row mass by Markov’s inequality, and symmetry bounds the column mass. Both cutoffs use Lemma 7; the letter \(Q\) in that abstract lemma denotes any kernel satisfying its hypotheses.

For the routing-event cutoff above, reversal preserves the cutoff event, so a uniform discarded-row bound also bounds columns. Lemma 7 therefore gives \(2^{L/2}/\sqrt m+p\).

How often can selected paths meet?

The next deterministic fact will control the information revealed about a closing route by other paths. Its logarithm is to base two.

Closing routes and factorial cycle moments

An alternating cycle in the network can be followed by going through one child and returning through the other. After one child map is fixed, this produces a permutation containing fresh butterfly layers between fixed bijections. The following lemma counts several cycles of such a permutation at once. Its distinguished slots let us sum over all choices of cycle lengths without losing a factorial.

For later use, if \(q\ge1\) and \(J\ge1\) is an integer, cycles longer than \(J\) contribute at most \(k/J\). Expanding \(q^{\sum_{j\le J}F_j}\) in factorial moments and using \(\sum_{j\le J}j^{-1/2}\le2\sqrt J\) gives \[ \log \mathbb E q^{\sum_j F_j}\le (k/J)\log q+2q k\sqrt J/\sqrt n . \tag{8}\]

The two density estimates

Multiplicity amplification and the middle dimension range

We now use the branching multiplicity from (3): the ordered \(k\)-injection module contains \(\lambda\vdash N\) with multiplicity \(m=f^{\lambda/(N-k)}\), and for \(k=N\) this is \(D_\lambda\). The density bounds just proved will make truncation effective on these repeated copies.

For either symmetric kernel \(Q\) above, retain an entry when its density is at most \(z\). Markov’s inequality gives discarded row mass at most \(Mz^{-a}\), and symmetry gives the same column bound. The retained entries are at most \(z/(N)_k\). Applying Lemma 7 with \(B=z\) therefore gives, on an irreducible occurring with multiplicity \(m>0\), \[ \|Q(\lambda)\|\le Mz^{-a}+\sqrt{z/m}. \tag{14}\] In particular if \(\log M\le (a/4)\log m\), take \(z=\sqrt m\) to get at most \(2m^{-a/4}\).

First consider \(j=N-\lambda_1\) with \(1\le j\le\delta N\), where a sufficiently small absolute \(\delta>0\) will be used. Choose a fixed \(u_0>0\) small enough that \(\eta(1-u_0)>u_0\) and \(u_0<1\), and take \(k=\lceil j(N/j)^{u_0}\rceil\). For small \(\delta\) this gives \(N-k\ge j\), so the skew tableau of shape \(\lambda/(N-k)\) has its remaining first row independent of the entire tail shape \(\rho=(\lambda_2,\ldots)\). Consequently \[m=\binom{k}{j} f^\rho,\qquad D_\lambda\le \binom Nj f^\rho.\] Thus \(\log m\ge u_0 j\log(N/j)+\log f^\rho\), at least a fixed positive fraction of \(\log D_\lambda\) (using the elementary binomial bounds). The first density bound proved above gives \(\log M\le C' j(j/N)^{\eta(1-u_0)-u_0}\), hence at most \((a/4)\log m\) by reducing \(\delta\). By (14), and \(m\) tending uniformly to infinity here as \(d\to\infty\), we have \(\|K_N(\lambda)\|\le D_\lambda^{-c_2}\) for some constant \(c_2>0\).

By Lemma 2, shapes with more than \(N/2\) rows are annihilated by \(T_N\) and hence by \(K_N\).

All remaining shapes other than the trivial one and those already treated have \(j\ge\delta N\) and \[\log D_\lambda\ge hN\] with \(h>0\) fixed, for large \(N\). Here are details. Both first row and column are then bounded by \((1-\delta)N\) (take \(\delta<1/2\)). If both are smaller than \(N/10\), hook lengths are at most \(N/5\) and the bound follows from Stirling. Otherwise transpose if necessary (which does not change dimension) so the row has length \(s\ge N/10\). Retain only it and a subdiagram of the tail of size \(v=\lfloor\min(\delta/2,1/100)N\rfloor\), which can be obtained by removing corners. All tableaux on this diagram have extensions. Fill its first \(v\) positions in the top row first, then interleave the remaining row and a fixed tableau order on the tail; this gives \(\binom{s}{v}\) possibilities, yielding the asserted exponential lower bound.

Take a fixed large \(A_0\) so that when \(\log D_\lambda\ge A_0 N\), the first density bound on all \(N\) positions gives \(\log M\le(a/4)\log D_\lambda\). Then (14) with \(Q=K_N\) again gives \(\|K_N(\lambda)\|\le D_\lambda^{-c_3}\) for an absolute \(c_3>0\), for large \(N\).

The only remaining range is \(hN\le\log D_\lambda\le A_0 N\). Here the full-deck moment cost \(CN\) is comparable with the log dimension and need not fit the truncation threshold. We use the modified central networks to reduce that cost before invoking multiplicity. Choose \(L\) fixed sufficiently large and then \(\epsilon>0\) sufficiently small so the second of the two assertions about the \((1+a)\)-moment above gives \(\log M\le ahN/4\) whenever \(b\le\epsilon N/S\), for large \(N\). We justify the comparison in positive semidefinite order. Let \(O\) be the product of the outer butterfly layers, and let \(C\) be the parallel product of the central size-\(S\) palindrome operators. Thus, on the representation under consideration, \[K_N=O^*CO.\] By Lemma 3, each central positive contraction has norm at most a fixed \(\theta<1\) on every nontrivial irreducible of \(S_S\); increase \(\theta\) to a number in \((0,1)\) if necessary.

Restrict to \((S_S)^{N/S}\) and decompose into tensor-product irreducibles, with their multiplicity spaces. If a component is nontrivial on more than \(\epsilon N/S\) blocks, the tensor product defining \(C\) has norm at most \(\theta^{\epsilon N/S}\). This accounts for the first term below.

For \(E\subseteq[N/S]\), let \(P_E\) act as identity in blocks in \(E\) and as the projection to invariants in the other blocks. On a component whose nontrivial factors lie in a set \(F\) with \(|F|\le\epsilon N/S\), \(P_F\) is identity. Consequently \(\sum_{|E|\le\epsilon N/S}P_E\) dominates identity on all these components and therefore dominates \(C\) there. Its sandwich \[Q_E=O^*P_EO\] is precisely the modified network with identity in \(E\) and uniform central permutations elsewhere. Since \(O\) is a contraction, these two component cases give \[0\le K_N(\lambda)\le \theta^{\epsilon N/S} I+\sum_{E:\, |E|\le\epsilon N/S}Q_E(\lambda)\] where \(Q_E\) is exactly the modified palindrome with identity in \(E\) and uniform central permutations elsewhere. Each summand by (14), \(k=N\), is at most \(2D_\lambda^{-a/4}\) in norm. The log number of summands is at most \((N/S)[-\epsilon\log\epsilon-(1-\epsilon)\log(1-\epsilon)]\) by the binomial theorem (\(\epsilon<1/2\)), so we may require also that this be \(\le ah N/8\). Since \(hN\le\log D_\lambda\le A_0 N\) and all parameters now are fixed absolutely, this proves \(\|K_N(\lambda)\|\le D_\lambda^{-c_4}\) for some absolute \(c_4>0\) and sufficiently large \(N\).

We have consequently, on every nontrivial shape not killed, \(\|T_N(\lambda)\|\le D_\lambda^{-c_*}\) for an absolute \(c_*>0\). Plancherel on the finite group and Cauchy-Schwarz bound four times the squared total variation distance after \(r\) butterflies by \[\sum_{\lambda\ne (N)} D_\lambda\,\|T_N(\lambda)^r\|_{\rm HS}^2,\] independently of initial permutation by translation. For \(r\) forward sweeps, \[\|T_N(\lambda)^r\|_{\mathrm{HS}}^2 \le D_\lambda\|T_N(\lambda)^r\|_{\mathrm{op}}^2 \le D_\lambda\|T_N(\lambda)\|_{\mathrm{op}}^{2r}.\] Thus, keeping only shapes not killed, the sum is at most \(\sum D_\lambda^{2-2rc_*}\).

This last bound tends to zero for sufficiently large fixed \(r\). Medium or larger dimensions with \(\log D_\lambda\ge hN\) have at most \(2^N\) terms (bound partitions by compositions). For the small-\(j\) range, \(D_\lambda\ge \binom{N-j}{j}\): again fill \(j\) positions of the first row first and then interleave tail and remaining row. There are at most \(2^j\) shapes per \(j\). Thus, with \(s_*=2r c_*-2>0\), this range contributes at most \[\sum_{1\le j\le\delta N}2^j(j/(N-j))^{s_*j}\] tending to zero (choose \(s_*\) large for a geometric summable majorant and each fixed term vanishes). Increase \(r\) also so that \(s_* h>\log 2\). Hence \(rd\) steps suffice for the required threshold for all sufficiently large \(d\).

A fixed-certificate cycle tail

Dense tuple densities

The sparse moment estimate alone does not provide a useful exponent at fixed density. Here a bound on reciprocal cycle lengths gives a smaller explicit density exponent. Define \[h_j=\max\left\{\mathbb E(1/L):L\in\mathbb Z_{\ge1},\ \mathbb P(L=l)\le l/2^{j-1}\right\},\] and \[H(\rho)=\max\left\{\frac12\sum_{j\ge1}h_jx_j: 0\le x_j\le1,\ \sum_{j\ge1}2^{-j}x_j\le\rho\right\}.\]

The defining linear optimization fills the shortest allowed cycle lengths first. With \(M=2^{j-1}\) and \(q(q+1)\le2M<(q+1)(q+2)\), \[ h_j=\frac qM+\frac{1-q(q+1)/(2M)}{q+1}, \qquad h_j\le\sqrt{2/M}. \tag{19}\] The allocation ratios \(2^{j-1}h_j\) increase with \(j\). Indeed \(Mh(M)\) is the maximum of \(\sum_lz_l/l\) subject to \(0\le z_l\le l\) and \(\sum_lz_l=M\); increasing \(M\) permits adding positive-valued mass. Thus the budget for \(H\) is assigned at the highest indices first, with at most one partially filled index.

Here are explicit arithmetic bounds, with enough detail to reproduce the finite check. Formula (19) simplifies to \(h_j=q/(2M)+1/(q+1)\). The inequality \(h_j\le\sqrt{2/M}\) follows by putting \(x=2M\): the convex quadratic \((q+x/(q+1))^2-4x\) is nonpositive at the two endpoints \(q(q+1)\) and \((q+1)(q+2)\), hence throughout the interval. Therefore \[\frac12\sum_{j>20}h_j\le\frac{1+\sqrt2}{1024} <\frac{169}{70\cdot1024}, \qquad \sum_{j>20}2^{-j}=2^{-20}.\] Subtract this last budget, allocate the first twenty levels greedily, and add the rational value bound. Exact rational arithmetic gives \[H(1/8)<.791402,\qquad H(13/50)<1.098069, \qquad H(1)<1.958069.\] These imply the stated useful bounds \(.80\), \(1.11\) and \(1.97\). For the logarithms in the entropy correction, use \[-\ln(1-x)\le\sum_{i=1}^{80}\frac{x^i}{i} +\frac{x^{81}}{81(1-x)},\qquad \ln2=2\sum_{j=0}^{39}\frac{(1/3)^{2j+1}}{2j+1}+R, \quad 0<R\le\frac{2(1/3)^{81}}{81(1-1/9)}.\] The entropy numerator is negative, so increasing its positive denominator gives an upper bound. The resulting rational comparisons give a full bracket below \(.904054\) at \(\rho=7/25\) and below \(.515374\) at \(\rho=1\). In particular they imply the margins \(.96\) and \(.54\) used below.

These endpoint checks cover every \(0<\rho\le7/25\). For \(\rho\le1/8\), the entropy correction is nonpositive and \(H(\rho)\le H(1/8)<.80\). On \([1/8,1/4]\) and \([1/4,7/25]\), the slopes of \(H\) are respectively \(7/3\) and \(3/2\). The absolute derivative of the entropy correction is \[\frac{-\rho-\ln(1-\rho)}{\rho^2\ln2} \le\frac1{2(1-\rho)\ln2}<\frac{25}{24},\] using its series, \(\rho\le7/25\) and \(\ln2>2/3\). Thus the bracket increases on both intervals. The accompanying script support/network_bounds.py checks exactly these five rational inequalities; it does not test the probabilistic or asymptotic arguments.

From truncation to all representations

Encoding cycles by omitted switch bits

We need a counting observation on cycles. Let \(m\) be a cube size, \(D\) a fixed set of at most \(k\) positions in it, and \(\pi\) the permutation obtained using any fixed pre-permutation, fair switch layers in \(L\) distinct coordinates, and any fixed post-permutation. If \(Y\) is the number of cycles of \(\pi\) contained entirely in \(D\), there are absolute \(c,\gamma>0\) and \(L_0\) such that \[ \Pr(Y\ge t)\le 2^{-c L t} \qquad \big(L\ge L_0,\ t\text{ integer}\ge\max(1,k2^{-\gamma L})\big). \tag{22}\] The contact estimate of Lemma 8 applies after relabeling inputs by the fixed pre-permutation. If the \(L\) coordinates do not fill the whole cube, apply it separately in each \(L\)-coordinate block: \(\sum_iw_i\log_2w_i\le w\log_2w\) shows that any \(w\) selected paths still share at most \(w\log_2w/2\) switches in total.

We prove (22) with \(\gamma=1/1000\) and \(L_0=256\). The event is empty if \(t>k\). Otherwise, when \(Y\ge t\), at least \(t/2\) of its cycles have length at most \(2k/t\). Select \(s=\max(1,\lfloor t/2\rfloor)\) of these cycles; in particular \(s\ge t/3\). We will encode their routes while omitting the fresh switch bits forced by closing a cycle.

First we find starts and an exploration order that omit many bits. Choose each start uniformly in its cycle. Independently give \(D\) a uniform random priority order, and visit the selected cycles in the order of their starts, completing one cycle before the next. On a cycle of length \(w\), the closing path is uniform among its \(w\) paths. Its expected contacts with other paths of that cycle are at most \(\log_2w\) by the contact estimate. At each of the \(L\) layers, a contact outside that cycle can reveal at most one bit; conditional on the starts, the contacted selected cycle precedes it with probability \(1/2\). Therefore the number \(S\) of fresh switch bits on the closing paths satisfies \[0\le S\le Ls,\qquad \mathbb ES\ge Ls/2-s\log_2(2k/t)\ge0.4Ls.\] The last inequality uses \(k/t\le2^{\gamma L}\) and \(L\ge256\). It follows that \(\Pr\{S\ge Ls/4\}\ge1/5\). Thus at least one fifth of the priority orders admit some choices of starts saving \(Ls/4\) bits. This is an existence statement for each coin configuration, before counting configurations under fixed priorities.

Fix a priority order. A code consists of the unordered set of \(s\) starts, the cycle lengths in traversal order, and a finite bit string. The decoder keeps a table of already known switch bits. It traces nonclosing edges using the fixed pre- and post-permutations, reading a bit only at a previously unknown switch. On a closing edge, its input and required endpoint are known. A butterfly updating each coordinate at most once has at most one route between those endpoints; the decoder fills the unknown bits along that route with the forced values, rejecting inconsistencies. After completing the cycles, it reads all remaining unknown bits in a fixed order. Hence a valid code determines at most one full coin configuration. If \(S\ge Ls/4\), its bit string has length at most \(mL/2-Ls/4\). Counting all finite strings up to that length, including unequal lengths, gives at most \[\binom ks(2k/t)^s\,2^{mL/2-Ls/4+1}\] configurations for these fixed priorities.

Every configuration in the tail event has such a code for at least one fifth of all priority orders. Averaging the preceding count over priorities and dividing by the \(2^{mL/2}\) equiprobable coin configurations bounds the tail probability by \[5\,2^{1+s\{\log_2(6e)+2\gamma L-L/4\}} \le 2^{-Lt/64}\qquad(L\ge256).\] Here \(\log_2\binom ks+s\log_2(2k/t) \le s\{\log_2(6e)+2\gamma L\}\) uses \(s\ge t/3\). This proves (22).

There-and-back recursion on cube nodes

Now realize \(H_N\) as there-and-back switches (using the pass order or its reverse first, according to which product is used), all with independent coins. It is a binary tree of cube nodes: each size \(2m\) node uses switches first across one axis, then gives two children (panels of \(m\) positions, indexed by columns of the switch pairs) on which independent child there-and-back permutations act, then again switches on its original axis. Size one leaves do nothing. Call the first layers of switches over the tree its input layers, and second layers its output layers.

Within a node, write \(R(x,y)\) for the density of output placement at \(y\) for \(k\) distinguished cards starting at \(x\), relative to uniform on such placements. Write \(J(x,y)\) for the density in an ideal experiment at the node, replacing the two child permutations by independent uniforms. We use at root or any node, for \(p=1+\theta>1\), the inequality \[ \mathbb E_{\rm unif} R(x,y)^p G(y) \ \le\ \mathbb E_{\rm true}\Big[G(y)\prod_v J_v(X_v,Y_v)^\theta\Big] \tag{23}\] for any nonnegative \(G\). Left expectation is in \(y\); right uses the actual switch experiment with this input \(x\), taking \(J_v\) at this and descendant nonleaf nodes with the placements of the distinguished cards passing through them (local inputs \(X_v\) and outputs \(Y_v\)). Densities for empty placements are 1. To see (23), in the ideal node experiment take \(x_i,y_i\) the inputs into and outputs of children. Given final \(y\) (when \(J>0\)), the conditional expectation of the product of child true densities \(R_i(x_i,y_i)\) equals \(R(x,y)/J(x,y)\), by the density change to the true experiment from ideal. And \(R\) vanishes when \(J\) does. Jensen thus bounds the left side by \[\mathbb E_{\rm ideal} G(y)\,J(x,y)^\theta\,\prod_i R_i(x_i,y_i)^p.\] Condition on this node’s outer switch layers (input and output), so \(y_i\) in this formula are independent uniforms, and \(y\) is a function of them and the outer choices. Apply (23) inductively at each child (against nonnegative functions of their outputs); this gives exactly the desired inequality. The size one case is immediate.

For \(x,y\) in the size \(2m\) node, let the multigraph on the \(k\) cards have two matchings, given by sharing an input column or sharing an output column, of sizes \(a,b\) respectively. It consists of paths (possibly single vertices) and even cycles (possibly of length two); let \(c_*\) be the number of cycles. Call coloring the cards by the two children allowed if opposite along matching edges. With \(r\) the number in the first child, we have \[ J(x,y)=(2m)_k 2^{a+b-2k} \sum_{\text{allowed colors}}\frac{1}{(m)_r(m)_{k-r}} =2^{c_*}\mathbb E Z(r),\qquad Z(r)=\frac{(2m)_k}{2^k(m)_r(m)_{k-r}}. \tag{24}\] Indeed realizing a given coloring from input costs \(2^{a-k}\); given correct child output columns the final switches cost \(2^{b-k}\); the child-permutation probabilities between columns are as in the sum, with columns distinct per color by the constraints. There are \(2^{k-a-b+c_*}\) allowed choices, taken equally in the last expectation.

Every allowed coloring is feasible: it puts at most one card of each color in each of the \(m\) input columns and each output column. Each path or cycle component has two colorings. Even components contribute equally to the two colors; each odd path component contributes one independent sign to their difference.

The following bound holds uniformly: \[ \mathbb E Z(r)\le \exp\big(C k\log(2m)/m\big). \tag{25}\] To prove it, put \(z=2r-k\). Each odd-vertex path component contributes one independent uniform sign to \(z\); let \(q\) be their number. Clearly \(q\le k\). Making all odd components favor the same color is feasible, so \(k+q\le2m\) and hence \(q\le w:=2m-k\) as well. At the balanced count \(r_0=\lceil k/2\rceil\), writing \(k=2a\) or \(2a+1\) gives \[Z(r_0)=\prod_{i=0}^{a-1}\frac{2m-2i-1}{2m-2i}\le1.\] The cases \(k=0\), \(q=0\), or \(w=0\) are consequently immediate.

Suppose first that \(1\le k\le\epsilon m\), for a small absolute \(\epsilon\). The factorial ratio \[\frac{Z(r)}{Z(r_0)} =\frac{(m-r)!(m-k+r)!} {\lfloor w/2\rfloor!\lceil w/2\rceil!}\] is unchanged by replacing \(z\) by \(-z\). Moving \(i\) steps from the balanced count multiplies successive factors of the form \(1+O((i+1)/m)\). Thus it is at most \(e^{C(z^2+1)/m}\). Since \(z\) is a sum of at most \(k\) fair signs, \(\Pr\{z^2\ge v\}\le2e^{-v/(2k)}\), and for \(m>2Ck\), \[\mathbb Ee^{Cz^2/m} \le1+\frac{4Ck}{m-2Ck}.\] Choosing \(\epsilon\) small makes \(\mathbb EZ(r)\le e^{C'k/m}\), which implies (25) in this range.

For \(k>\epsilon m\) and \(w>0\), Stirling’s formula gives the uniform bound \[\frac{Z(r)}{Z(r_0)} =\frac{((w-z)/2)!((w+z)/2)!} {\lfloor w/2\rfloor!\lceil w/2\rceil!} \le e^{O(\log(2m))+wI(z/w)},\] where \(I(x)=((1-x)\log(1-x)+(1+x)\log(1+x))/2\) is extended continuously at the endpoints. The sign sum has point probabilities at most \(e^{-qI(z/q)}\). Convexity and \(I(0)=0\) give \[I(z/w)\le(q/w)I(z/q)\qquad(0<q\le w).\] The two exponential rate factors therefore cancel. Summing over at most \(2m+1\) possible values of \(z\) leaves \(e^{O(\log(2m))}\), which is at most \(e^{Ck\log(2m)/m}\) since \(k>\epsilon m\). This completes the uniform imbalance estimate, including full occupancy.

Summing cycle moments over scales

Apply (23) at root with \(G=1\) and \(l\) distinguished cards. At each height \(j\ge1\) (nodes of size \(2^j=2m\)), distinguished counts \(k_v\) at the nodes sum to \(l\), so (25) costs only \(e^{Cl}\) over the tree for fixed \(\theta\). It remains to obtain, in the true \(H_N\) runs, for some small absolute \(\theta>0\) \[ \mathbb E 2^{\theta\sum_v c_v}\le e^{C l} \tag{26}\] where \(c_v\) is the cycle count \(c_*\) of (24) for the placements there.

Indeed, the logarithm of the noncycle factor at height \(j\) is at most \(Clj/2^j\), and \(\sum_{j\ge1}j2^{-j}<\infty\). It is the cycle factor, rather than this deterministic imbalance factor, that requires the remaining multiscale argument.

Condition on all input layers, fixing the assignments and inputs throughout the tree. At a node, given \(\alpha,\beta\) the two child permutations on columns, \(c_v\) is the number of cycles of \(\beta^{-1}\alpha\) entirely contained in the set \(D_v\) of input columns with both entering positions marked (distinguished). To see this, in a cycle of the two matchings one uses both inputs of participating columns, one going through each child. Following this circuit, going through the output matching from the \(\alpha\)-card at one such input column \(i\), and then through the input matching, brings us to the \(\alpha\)-card for column \(\beta^{-1}\alpha(i)\). Conversely a cycle of the comparison contained in \(D_v\) traces such a circuit, irrespective of the outermost output switches there. In particular \(c_v\) with inputs fixed depends just on smaller height output layers.

For \(h=1,2,4,\ldots\) group node heights \(j\) in bands \(h\le j<2h\). For such \(j\) consider conditioning on all inputs as above and also all output layers at heights \(<h/2\). For large \(h\), \(\alpha\) in the above comparison has still its last \(L=h/2\) switch layers (distinct axes in this child) fresh. Indeed these output layers of a height \(j-1\) child use output coins at heights \(j-L,\ldots,j-1\); each layer runs over all the \(m\) columns in that child. Even conditioning further on everything except these layers, (22) applies to the comparison and \(D_v\), the latter of size at most \(k_v\). Consequently for sufficiently small \(\theta>0\), \[ \mathbb E\left[2^{2\theta h c_v}\mid {\rm inputs}, {\rm outputs}_{<h/2}\right]\le \exp(C k_v h 2^{-\gamma' h}) \tag{27}\] for some absolute \(\gamma'>0\); in the conditioning we mean layer coins. Indeed for positive counts at or above \(k_v 2^{-\gamma L}\), multiplication by \(2^{2\theta h t}\) still gives geometric decay in \(ht\) from (22), and for counts below threshold one bounds the moment by \(2^{2\theta h k_v 2^{-\gamma L}}\). For \(k_v\ge1\) the additive exponentially small term fits as well by taking \(\gamma'\) small; \(k_v=0\) is automatic. For bounded \(h\), (27) holds by enlarging the constant since \(c_v\le k_v\).

Conditional on the indicated layers, nodes on a fixed level have independent \(c_v\), using only their disjoint subtrees. So (27) also bounds the \(2\theta h\) moment in this notation for the level sum, with \(k_v\) replaced by \(l\). Hölder over the at most \(h\) levels in the band gives \[\mathbb E\left[2^{2\theta\sum_{j\text{ in band}}\sum_{v\text{ at }j}c_v}\mid {\rm inputs}, {\rm outputs}_{<h/2}\right]\le \exp(C l h 2^{-\gamma' h}).\] The next smaller band of the same parity of \(\log_2h\) has heights \(h/4\le j<h/2\). Its cycles depend only on output layers strictly below \(h/2\), so its exponential factor is measurable under the conditioning for the band starting at \(h\). The tower property therefore permits integrating each parity from the largest band downwards. It bounds that parity’s \(2\theta\) moment by \[\exp\left\{Cl\sum_{h=1,2,4,\ldots}h2^{-\gamma'h}\right\} \le e^{C'l}.\] Cauchy–Schwarz combines the two parities at exponent \(\theta\) and proves (26). Independence was used within a height, while the tower property handles the dependence across heights.

A fixed number of compositions gives a pointwise bound

The lower-diagram dimension factor

The density theorem also distinguishes permutations of the tracked labels. We now make that distinction explicit. This is useful when a bound involving only the number of boxes below the first row does not yet control the dimension of the lower diagram.

An alternative cycle-moment proof by entropy windows

We give a second proof of the cycle-moment estimate (26), retaining the node comparison and color imbalance estimate already established. Instead of separating dyadic bands into two parities, we control their expectation under every tilted law of the output coins. The inverse-height weights in the entropy chain rule give each layer a bounded total coefficient. We retain the fixed input layers and the node cycle counts \(c_v\) from the proof of Theorem 14.

We first give a certificate version of the cycle estimate. Consider a butterfly of \(q\) distinct-coordinate layers, with arbitrary fixed permutations before and after it, and a fixed set \(D\) of at most \(k\) positions. Let \(Y\) count the cycles of the resulting permutation contained in \(D\), and let \(r\ge1\) be an integer. Put \(\varepsilon=1/1000\). If at least \(r\) cycles lie in \(D\), with \(r>k2^{-\varepsilon q}\), at least \(r/2\) of them have length at most \(2k/r\). A uniformly chosen closing path of one of these cycles has at most \(\log_2(2k/r)\le1+\varepsilon q\) internal contacts on average, by the contact bound used in Section 6.1.

Choose one root uniformly in each short cycle, and retain each short cycle independently with probability \(1/16\). Conditional on a particular cycle being retained, its closing path has at most \(q/16\) expected contacts with paths in other retained cycles: at each layer there is only one other path at its switch, and its cycle is retained with probability at most \(1/16\). Markov’s inequality shows that the probability of more than \(q/4\) such external contacts is at most \(1/4\). The probability of more than \(q/4\) internal contacts is at most \(4/q+4\varepsilon\). For all sufficiently large absolute \(q\), the expected number of retained roots passing both tests is therefore larger than \[\frac1{16}\frac r2 \left(1-\frac14-\frac4q-4\varepsilon\right) >\frac r{64}.\] Consequently some deterministic choice contains \(R=\lceil r/64\rceil\) cycles whose closing paths share at most \(q/2\) switches with all other paths in those selected cycles. Deleting further selected cycles only improves this property.

A certificate specifies the unordered root set and the length of each selected cycle; traverse the cycles in increasing root order. There are at most \[\binom kR(2k/r)^R \le2^{R\{C_0+2\varepsilon q\}}\] certificates. Fix one certificate and expose its routes in that order. Before a closing route is queried, its initial point and target are known. The unique geometrical route between them is therefore known too. Whether it has at most \(q/2\) already exposed switches is measurable at this time. If that test succeeds, at least \(q/2\) fresh fair bits must take prescribed values for the cycle to close. Its conditional cost is at most \(2^{-q/2}\). Iterating over the \(R\) cycles and then summing certificates proves \[ \Pr\{Y\ge r\}\le e^{-cqr} \quad\text{if }r>k2^{-\varepsilon q} \text{ and }q\ge q_0, \tag{32}\] for absolute \(c>0\) and \(q_0\). This reasoning conditions only on already exposed bits; it does not condition on a subsequently discovered cycle.

Let \(b_t=\sum_{v:\,\operatorname{height}(v)=t}c_v\) be the cycle count at height \(t\) in the there-and-back tree, and put \(q=\lfloor t/2\rfloor\). Condition on all input coins and on output coins at heights below \(t-q\). First suppose that \(q\ge q_0\). At a height-\(t\) node, write the two child permutations as \(\alpha,\beta\), as in the cycle identification above. Freeze \(\beta\) and everything in \(\alpha\) except its last \(q\) output layers. These are fresh distinct-coordinate layers, so (32) applies. Integrating its tail, and decreasing a positive absolute \(a_1\) if necessary, gives \[\log\mathbb E\left[e^{a_1t c_v}\mid \text{inputs},\text{output heights}<t-q\right] \le Ck_v e^{-a_2t}.\] The factor \(t\) multiplying the exponentially small threshold is absorbed by decreasing \(a_2>0\). Small heights are covered by \(c_v\le k_v\) and increasing \(C\). Nodes at one height use disjoint remaining subtrees and \(\sum_vk_v=l\). Thus \[ \log\mathbb E\left[e^{a_1t b_t}\mid \text{inputs},\text{output heights}<t-q\right] \le Cl e^{-a_2t}. \tag{33}\]

To make the change of law precise, fix the input coins and let \(P\) be the product law of the output coins. Order those coins by increasing height. For any probability \(Q\) on this finite coin space, put \[\begin{aligned} H_s&=\mathbb E_Q D\bigl(Q(\text{height-}s\text{ coins}\mid \text{lower heights})\, \|\,P(\text{height-}s\text{ coins})\bigr),\\ H&=D(Q\|P)=\sum_sH_s. \end{aligned}\] Here \(D(\cdot\|\cdot)\) denotes relative entropy. Applying the entropy inequality conditionally to the window in (33) gives, for \(t\ge2\), \[\mathbb E_Qb_t\le \frac{Cl e^{-a_2t}+ \sum_{s=t-\lfloor t/2\rfloor}^{t-1}H_s}{a_1t}.\] Here \(b_t\) is measurable in output heights strictly below \(t\). The tilted law used in the conditional inequality is the marginal law of the window given its lower-height history, with all future coins integrated out. The entropy chain rule says that its conditional relative entropy, averaged over that history under \(Q\), is exactly the displayed sum of \(H_s\). The height-one term is at most \(l\) directly. A fixed layer \(s\) belongs only to windows with \(s+1\le t\le2s\), and \(\sum_{t=s+1}^{2s}t^{-1}\le\log2\). Summation therefore yields \[ \mathbb E_Q\sum_tb_t\le C_1l+C_2D(Q\|P). \tag{34}\] For \(0<\delta\le1/C_2\), the finite-space entropy variational formula now gives \[\log\mathbb E_Pe^{\delta\sum_tb_t} =\sup_Q\left\{\delta\mathbb E_Q\sum_tb_t-D(Q\|P)\right\} \le\delta C_1l.\] The estimate is uniform in the fixed inputs, so it also holds after averaging them. Inserting it into the exact ideal-node recursion (23), with \(\theta\log2\le\delta\), proves the density theorem by this alternative route; the smoothing and lower-diagram transfers then apply without change.

Cycle traces and tuple spreading

Our first objective is the \(L^{65/64}\) density bound. A selected cycle at a network node contributes a factor two to the number of possible routings. We therefore need an exponential moment for the sum of these cycle counts. Positive tensor traces first bound the full cycle count; a conditional estimate across levels then controls the selected cycles.

If \(\pi\) is a permutation let \(\kappa(\pi)\) denote the number of cycles, counting fixed points. Define for real \(x\ge 1\) \[Z_b(x)=\mathbb E_{\pi\sim\nu_b} x^{\kappa(\pi)}\] where \(b\) is a power of 2. We first show that there are absolute \(C<\infty\) and \(\gamma>0\) such that, for \(b=2^w\), \[ \log Z_b(1+2^{\lfloor w/8\rfloor})\le C b^{1-\gamma}. \tag{45}\] For integer \(q\ge 1\), \(Z_b(q)\) is the trace of \(K_b\) on the tensor space \((\mathbb C^q)^{\otimes b}\) with permutations acting by permuting tensor legs. In fact the trace of a permutation counts its fixed words on an alphabet of size \(q\). The following identity is the common tensor calculation underlying this proof and the harmonic cycle estimates.

A slowly growing alphabet. We now derive the stated bound for \(Z_b\) from the recursion. This proof retains the decay obtained by following the alphabet parameter until it reaches its smallest value. Let \(h_w(r)=2^{-w}\log Z_{2^w}(1+2^r)\) for integers \(r\ge 0\). For \(w\ge 1,r\ge 1\), (47) gives \[h_w(r)\le \tfrac12 h_{w-1}(r)+\tfrac12 h_{w-1}(r-1).\] At the boundary \(r=0\), concavity gives \(Z_m(3/2)\le Z_m(2)^\alpha\), where \(\alpha=\log_2(3/2)\). Consequently \[h_w(0)\le\theta h_{w-1}(0),\qquad \theta=(1+\alpha)/2<1, \qquad h_0(r)\le(r+1)\log2.\] To iterate these inequalities, start at \(r\) and, while positive, stay in place or decrement by one with equal probabilities. After reaching zero, remain there and multiply by \(\theta\) at each subsequent step. The recurrence bounds \(h_w(r)\) by \((r+1)\log2\) times the expected product of these factors over \(w\) steps.

Suppose \(r\le w/8\). If \(B\) counts successes in \(\lfloor w/2\rfloor\) independent fair trials, the probability that the process has not reached zero by that time is at most \[\Pr(B<r)\le 2^r\mathbb E2^{-B} =2^r(3/4)^{\lfloor w/2\rfloor}\le Ce^{-cw},\] since \(2^{1/8}\sqrt{3/4}<1\). On the complementary event the product of factors is at most \(\theta^{w/2}\). Thus \[h_w(r)\le(r+1)\log2\{Ce^{-cw}+\theta^{w/2}\}.\] Taking \(r=\lfloor w/8\rfloor\) proves (45), with an absolute \(\gamma>0\) decreased as necessary to absorb the linear factor in \(w\).

Conditional cycle counts. The trace bound concerns an unconditioned network of one size. To use it on the many levels of a larger network, we leave a specified interval of switch levels fresh and require a bound uniform in all other switches. We next use (45) for switches sampled in the recursion defining \(\nu_n\). Nodes of size \(2^j\) will be called level \(j\) (\(1\le j\le d\)), with \(n/2^j\) nodes at that level indexed by fixed prefixes of length \(d-j\). Regard the input and output outer switches of every node as its switch variables at that level; the raw switch variables are independent. For a realization, draw at a node the edges taken by all its cards between its input pair indices and output pair indices (two parts); the graph is bipartite 2-regular, allowing double edges. Its two full matchings, together giving the edges with multiplicity, come from the two child bijections \(A,B\) on the \(m=2^{j-1}\) pair indices: the outer switches do not change these indices and there is one card per input pair going to each child. The number of cycle components, including cycles of two edges, is \(\kappa(A^{-1}B)\) (traverse using \(B\)-edges forward, \(A\)-edges backward). Let \(C_j\) be the sum of these numbers over level \(j\). It depends only on switches at levels strictly below \(j\), regardless of card identities coming into the nodes.

Fix \(1\le k\le n\), and put \(W_j=\min(k/2,C_j)\). With \[\delta=1/64\] we claim the absolute bound \[ \log\mathbb E\,2^{\delta\sum_{j=1}^d W_j} \le C k\log(e n/k). \tag{48}\] For \(j\ge 64\) let \[w=\lfloor j/2\rfloor,\qquad b=2^w,\qquad I_j=\{j-w,\ldots,j-1\}.\] Condition on all level switch variables outside \(I_j\). We will bound the exponential moment at the higher exponent \(\delta j\). Take \(q=1+2^{\lfloor w/8\rfloor}\), so \(q\ge 2^{\delta j}\) (\(\lfloor w/8\rfloor=\lfloor j/16\rfloor\ge j/64\) for \(j\ge64\)). Within each child of size \(m=2^{j-1}\) of a node at level \(j\), the interval \(I_j\) supplies \(w\) outer layers of input switches and the corresponding output layers. We can additionally condition on all the output switch variables there. The child input switches in \(I_j\) act as independent \(w\)-bit sweeps in \(m/b\) blocks (first \(w\) bits of the child position index used, its other bits fixed within a block); the blocks are aligned across the two children. Thus for a node, \(A^{-1}B\) now has the form \[U_A^{-1} G U_B\] where \(G\) is a fixed permutation of the \(m\) slots and \(U_A,U_B\) are independent permutations with law the product of \(\mu_b\) over those blocks. Indeed each child map first applies the indicated input switches, then its deeper fixed submaps and its conditioned output switches. In the \(q\)-color tensor representation on \(m\) slots, let \(T_{\rm bl}\) be the mean operator of the input sweeps in blocks, and \(U(G)\) the representation of \(G\). Conditionally, \[\mathbb E\,q^{\kappa(A^{-1}B)} =\operatorname{Tr}\big(T_{\rm bl}^* U(G) T_{\rm bl}\big) \le \operatorname{Tr}(T_{\rm bl}T_{\rm bl}^*)=Z_b(q)^{m/b}.\] Here we bounded the absolute trace against a positive semidefinite matrix using unitarity, and used the tensor product over blocks and cyclicity. Different level-\(j\) nodes use independent remaining randomness. The bound is uniform so we can drop the extra output conditioning. We get, with \(\mathcal F_{\overline I_j}\) denoting the switches outside \(I_j\), \[ \log\mathbb E\big[2^{\delta j W_j}\mid\mathcal F_{\overline I_j}\big] \le \min\big( (\log 2)\delta j k/2,\ C n b^{-\gamma}\big). \tag{49}\] Indeed the second bound applies to \(C_j\) by multiplying over the \(n/2^j\) nodes and using (45) with \((n/2^j)(m/b)b^{1-\gamma}\le n b^{-\gamma}\).

Combining overlapping level intervals. Estimate (49) is conditional, so it does not require different cycle counts to be independent. We will use it first on collections of disjoint intervals, and then average those collections by Hölder. To combine intervals without paying a Hölder exponent of more than \(j\) on level \(j\), observe that for a fixed level \(l\), \[\sum_{j\ge 64:\ l\in I_j} \frac1j \le \sum_{j=l+1}^{2l} \frac1j \le 1 .\] Using only \(64\le j\le d\), we can find weights \(\theta_{\mathcal S}\ge 0\), summing to 1, on subcollections \(\mathcal S\) of these indices with pairwise disjoint intervals, such that \(\sum_{\mathcal S\ni j}\theta_{\mathcal S}=1/j\) for each such \(j\). For clarity, assign to each interval, in order of increasing left endpoints (ties ordered arbitrarily), a measurable subset of \([0,1]\) of length \(1/j\), disjoint from the sets of earlier overlapping intervals. This is possible because those earlier overlapping intervals all contain the current left endpoint, so their sets’ total length leaves enough room. Partition by membership in the assigned sets, taking lengths as weights. Weighted Hölder now gives \[\mathbb E\,2^{\delta\sum_{64\le j\le d} W_j} \le \prod_{\mathcal S}\left(\mathbb E\,2^{\delta\sum_{j\in\mathcal S} j W_j}\right)^{\theta_{\mathcal S}}\] (positive weights suffice in the product, and the exponents inside the expectations on the right give the one on the left when averaged with those weights). Within a collection, use (49) on the largest \(j\) first and continue downwards. The terms from smaller \(j'\) in the collection depend only on levels \(\le j'-1\), hence outside \(I_j\) since \(I_{j'}\) ends at \(j'-1\) and the intervals are disjoint with \(j'-1<j-1\). Taking logs, the resulting bounds (49) occur with factors \(1/j\). Handling \(j<64\) deterministically, we obtain an upper bound for the left hand side of (48) by \[C k + \sum_{j\ge64} \min\big(Ck,\, Cn\,2^{-\gamma\lfloor j/2\rfloor}/j\big) \le C' k\log(e n/k),\] where the sum bound can use all \(j\ge 64\): after \(j_0=\lceil (2/\gamma)\log_2(n/k)\rceil\), \(n2^{-\gamma\lfloor j/2\rfloor}\le 2^\gamma k\, 2^{-(\gamma/2)(j-j_0)}\). Thus the tail costs at most \(Ck\), and there are only \(O(\log(e n/k))\) terms before it. This proves (48).

From cycle weights to an injection density. The cycle moment is now available under the actual switch law. The next calculation relates it to the auxiliary uniform choices of legal child colors. Keeping these two probability laws separate is necessary when we estimate a power of the density. Denote by \([n]_{\ne}^k\) the ordered distinct \(k\)-tuples of positions, of cardinality \((n)_k=n(n-1)\cdots(n-k+1)\); positions can again be indexed by bit words, and \(\pi x\) denotes acting by the permutation \(\pi\) on every coordinate of \(x\). The following row bound is what we need: \[ \begin{gathered} K_{n,k}(x,y)=\Pr_{\pi\sim\nu_n}(\pi x=y),\qquad R_x(y)=(n)_kK_{n,k}(x,y)\\ \Longrightarrow\quad \|R_x\|_{1+\delta}\le\exp(Ck\log(en/k)). \end{gathered} \tag{50}\] for every such \(x\), with norm on uniform \(y\in[n]_{\ne}^k\).

Here is a partial route-counting identity. Fix the input and output tuples at a node. Draw the selected edges (the specified cards) between its input and output pair indices. Their components with edges are paths or cycles, say there are \(p_0\) paths and \(s\) cycles, with double edges forming a cycle as well. There are \(k+p_0\) vertices incident to edges (here \(k\) refers to the number of cards specified at this node). A proper edge coloring with two colors corresponds to assigning child halves, with two choices on each component by alternation. For each such coloring, the probability of the required outer switches, input and output together, is \(2^{-(k+p_0)}\): exactly one switch is prescribed per incident vertex, and the prescriptions are consistent since the tuples are distinct and the coloring is proper. In each child we now prescribe input and output tuples on the reduced indices, again distinct, for the tags of its color (keep their given order). With an empty tuple the kernel is interpreted as 1. Multiplying by \(n^k\) for a node of size \(n=2m\), the identity at that node is \[n^k K_{n,k}(x,y) =2^s\,\mathbb E_{\rm color} \left[\prod_{a=0}^1 m^{k_a} K_{m,k_a}(x'_a,y'_a)\right]\] where the proper coloring is uniform and the child data (sizes \(k_a\)) are induced by it. At size 1 the normalized kernel is 1. Recursing defines a base coloring experiment for fixed \(x,y\), with independent uniform coloring choices at each level’s nodes conditional on the already induced data there, inducing child data all the way down. Let \(S\) be the sum of selected-graph cycle counts \(s\) over its nodes. Thus \(n^k K_{n,k}=\mathbb E_{\rm base} 2^S\).

More precisely, for any outcome of this coloring tree, the probability under the actual full switches of taking \(x\) to \(y\) with those specified child assignments along the way is \(n^{-k}2^S\) times its probability in the base experiment. Indeed at each internal node \(v\), with local tuple size and component counts \(k_v,p_v,s_v\) (cards, paths with edges, cycles), the probability of the needed outer switches is \(2^{-(k_v+p_v)}\), versus \(2^{-(p_v+s_v)}\) for the designated coloring under the base experiment given its incoming data. For this fixed tree the switch requirements are prescriptions of raw coins, disjoint across the nodes, and together necessary and sufficient: tuples remain injective in each child (proper coloring) and the induced endpoints at size 1 require nothing more, with all unselected cards free of endpoint restrictions. The ratio thus multiplies to \(\prod_v 2^{s_v-k_v}=2^S n^{-k}\), since the \(k_v\)’s sum to the original \(k\) on each level. Conversely a full switch realization from \(x\) determines a unique selected endpoint and coloring tree for it (actual child routes).

On a realization of the full switches starting with tuple \(x\), call the corresponding total cycle count \(S_x\), using its actual endpoint and child routes. Any cycle in a selected partial graph is a full cycle component of that node’s graph from the realization, since its vertices already have degree 2 on the cycle. Also each uses at least two selected cards, with disjoint cards across cycles of a level. It follows that \(S_x\le\sum_j W_j\) (now with the original full tuple size \(k\)) on every realization. By convexity and the refined identity, with \(u=(n)_k/n^k\le 1\), \[\mathbb E_{y\ {\rm uniform}} R_x(y)^{1+\delta} \le \frac{u^{1+\delta}}{(n)_k}\sum_y \mathbb E_{\rm base(x,y)} 2^{(1+\delta)S} = u^\delta \,\mathbb E_{\rm actual} 2^{\delta S_x}.\] Now (48) proves (50).

A contraction measured by the transposition Casimir

The density estimate is complete. We now prove the operator contraction on the same scale \(h_n(k)\). The induction splits the positions into two halves, so its main task is to compare the parent Casimir scalar with the two child scalars seen by a vector fixed by the outer switches.

We use standard representation theory of the symmetric group over \(\mathbb C\): irreducibles are indexed by partitions \(\lambda\) of \(n\), of dimensions \(f^\lambda\) (numbers of standard Young tableaux). We use Young’s branching rule for restriction down the symmetric groups (multiplicity given by paths of successively removing single boxes while keeping diagrams of partitions), and the standard transposition-sum content formula (by the Young–Jucys–Murphy content theorem (Vershik and Okounkov 2005, Eq. (2.1), Proposition 5.3 and Theorem 5.8)), that \(\sum_{i<j}(i\,j)\) acts in \(\lambda\) by the sum of column-minus-row indices of its boxes. Indices of rows and columns here start at 1. The permutation module on ordered distinct \(k\)-tuples is the coset module with stabilizer \(S_{n-k}\), so multiplicity of \(\lambda\) is the dimension of its stabilizer-fixed space by Frobenius reciprocity. In particular for \(k=n-\lambda_1\), \(\lambda\) occurs in this module and (if \(k\ge1\)) not in the corresponding \(k-1\) tuple module. Its multiplicity at this \(k\) is \(f^{\bar\lambda}\), where \(\bar\lambda\) consists of all rows below the first: paths in the branching rule to the trivial shape \((n-k)\) must remove just that tail. Also \[ f^\lambda\le \binom{n}{k} f^{\bar\lambda} \tag{51}\] by choosing the entries of a standard tableau below the top row.

Let \(U\) denote the unitary action of \(S_n\) on the representation currently under consideration. Write \(D_{ij}=I-U((i\,j))\) on a unitary representation (indices \(i,j\) are positions). They are positive semidefinite. Put \(\mathcal C=\sum_{i<j}D_{ij}\), which in \(\lambda\) acts by \[ c=c_\lambda=\tfrac12(n^2-\textstyle\sum_i\lambda_i^2)+\sum_i(i-1)\lambda_i,\qquad nk/2\le c\le nk,\qquad k=n-\lambda_1. \tag{52}\] For the lower bound use \(\sum\lambda_i^2\le n\lambda_1\). For the upper, the sum of squares below row 1 is at least \(k\), and the sum of row-minus-one indices over tail boxes is at most \(k(k+1)/2\) (ordering tail boxes by row, the \(a\)-th has row index at most \(a+1\)). Define \[\Phi_n(c)=\frac{c}{n}\big(2+\log(n^2/c)\big),\qquad \Phi_n(0)=0.\] We prove there are absolute \(B>1,\eta>0\) such that on every nontrivial irreducible \(\lambda\) for \(n=2^d\), \[ \|K_n\|_{\lambda}\le B^{-1}\exp(-\eta\Phi_n(c_\lambda)). \tag{53}\] The norm notation means the operator norm in the indicated irreducible. In particular the bound implies \(\|K_n\|_\lambda\le\exp(-a k\log(e n/k))\) there for an absolute \(a>0\): \(k/2\le c/n\le k\) gives \(\Phi_n(c)\ge(k/2)(2+\log(n/k))\).

We will do an induction for (53) after some random-split estimates. In outline, \(K_n\) is the child product-law operator compressed by \(\Pi_1\), so we study Rayleigh values in unit vectors invariant under the bit-1 switch group. Under restriction to the two halves’ product subgroup, the induction hypothesis will contribute two child \(\Phi\)-values (evaluated at the partial Casimir scalars on the irreducibles of the factors), in place of the \(\Phi_n(c)\) in (53). The invariant vector lets us analyze the distribution of the partial Casimir values (spectral weights in the vector) by randomly flipping which member of each pair lies in each half. We control the sum of these two scalars relative to \(c/2\), and their difference, for the \(\Phi\)-comparison; we also use the high probability of two nontrivial child factors in the spectral weighting for large \(k\) so that the factor \(B^{-1}\) in (53) gives slack.

Hausdorff–Young amplification to the full permutation

We have separately proved a uniform injection-density bound and an operator contraction. To combine them, first convert the density bound into the \(65\)th trace moment in a single irreducible. Then use the operator contraction for the remaining sweep factors. The passage to powers of \(T_n\) uses Schatten Hölder, so it does not require \(T_n\) to be normal.

We view probability laws on \(S_n\) also by their densities relative to normalized uniform measure. For a density or function \(f\), use Fourier matrix \(\widehat f(\lambda)=\mathbb E_{g\ {\rm uniform}} f(g) U_\lambda(g)\), with \(U_\lambda\) a unitary irreducible of dimension \(d_\lambda=f^\lambda\). By finite group orthogonality/Plancherel, \(\|f\|_2^2=\sum_\lambda d_\lambda\|\widehat f(\lambda)\|_{\rm HS}^2\) with the (unnormalized) Hilbert–Schmidt norm; this holds with the displayed convention since one is expanding against the complex conjugates of matrix coefficients (scaled by \(\sqrt{d_\lambda}\) for an orthonormal basis). We need the single-irrep Hausdorff–Young bound (García-Cuerva and Parcet 2004, Lemma 5.1(1)), using Schatten norms \(S^s\) (the \(\ell^s\)-norms of the singular values, with \(S^\infty\) the operator norm): \[ d_\lambda^{1/s}\|\widehat f(\lambda)\|_{S^s}\le\|f\|_{p}, \qquad 1<p\le2,\quad s=p/(p-1). \tag{62}\] For completeness, at \(p=1,s=\infty\) the bound without dimension factor is unitarity, and at \(p=s=2\) it follows from Plancherel. To interpolate, pair by trace against a matrix \(A\) of \(S^p\)-norm 1 and take \(\|f\|_p=1\), ignoring the trivial zero case. In \(0\le\operatorname{Re}z\le1\), replace \(f\) by \(f_z\) using its phases times \(|f|^{p(1-z/2)}\) at nonzero entries (keep zeros); similarly in a singular value factorization of \(A\) keep both unitary factors and replace nonzero singular values \(\beta\) by \(\beta^{p(1-z/2)}\) to give \(A_z\). Apply the three-lines theorem to \(d_\lambda^{z/2}\operatorname{Tr}(A_z\widehat f_z(\lambda))\). On the first boundary use \(L^1\to S^\infty\) and the trace norm of \(A_z\), on the second \(L^2\to S^2\) and Hilbert–Schmidt; the norms of the inputs in these bounds are 1 and the analytic family is bounded on the strip. Taking \(z=2(1-1/p)\) and Schatten duality proves (62).

The injection multiplicity and the \(65\)th moment. The density estimate controls the Fourier matrix after averaging over a tuple stabilizer. Averaging these stabilizer projections in turn recovers \(K_n\) at the cost of the ratio \(D_\lambda/f^{\bar\lambda}\). This ratio is at most \(\binom nk\), even when the lower-diagram dimension \(f^{\bar\lambda}\) is large. It is this multiplicity comparison that allows a level-dependent density bound to control the dimension-weighted trace moment. Take \(p=1+\delta\) from (50), so \(s=65\). For a fixed nontrivial \(\lambda\), use \(k=n-\lambda_1\). For ordered distinct \(x\), average the density of \(\nu_n\) over right multiplication by its tuple stabilizer \(H_x\). The resulting function is \(g\mapsto R_x(g x)\), with \(L^p\)-norm bounded by (50); its Fourier matrix in \(\lambda\) is \(K_n P_x\), where \(P_x\) is the average of \(U_\lambda\) over \(H_x\). Averaging these projections in \(x\) uniformly gives \((f^{\bar\lambda}/d_\lambda)I\), by conjugation symmetry, Schur’s lemma and the fixed-space dimension above. By (62) and the triangle inequality in \(S^s\) we have in \(\lambda\) \[d_\lambda^{1/s}(f^{\bar\lambda}/d_\lambda)\|K_n\|_{S^s} =d_\lambda^{1/s}\|\mathbb E_x K_n P_x\|_{S^s} \le \exp(C k\log(e n/k)).\] Taking the \(s\)-th power and using (51) gives \[ d_\lambda \operatorname{Tr}_\lambda(K_n^s) \le \left(\frac{d_\lambda}{f^{\bar\lambda}}\right)^s \exp(C s k\log(e n/k)) \le \exp(C_2 k\log(e n/k)). \tag{63}\] Here \(K_n\) is positive semidefinite and \(C_2\) is absolute (using \(\binom{n}{k}\le(e n/k)^k\)).

Completion for directed sweeps. After \(l\) directed sweeps with integer \(l>s\), the nontrivial Fourier matrices of the position permutation law/density are \(T_n^l\). Subtracting 1 from the density keeps these and gives zero in the trivial representation. Schatten Hölder for matrix products gives \(\|T_n^s\|_{\rm HS}\le\|T_n\|_{S^{2s}}^s\), so in nontrivial \(\lambda\) \[\|T_n^l\|_{\rm HS}^2\le \|K_n\|_\lambda^{l-s}\operatorname{Tr}_\lambda(K_n^s).\] Choose a fixed absolute integer \(l>s\) sufficiently large, with \((l-s)a-C_2\ge 4\) using \(a\) from the consequence of (53). By (53), (63) and Plancherel, the squared \(L^2\) distance of the density to 1 is bounded by \[\sum_{k=1}^{n-1} 2^k \exp\big(-4 k\log(e n/k)\big)=o(1).\] We used that the number of shapes with a given \(k\) is bounded by the number of partitions of \(k\), hence by \(2^k\), and increased \(l\) so the exponent bound applies before counting shapes. The sum tends to zero, for example splitting at \(\sqrt n\) and using \(\log(e n/k)\ge1\) in the large range. Total variation is at most half the \(L^2\) distance by Cauchy–Schwarz. The estimate is independent of the starting permutation, since changing that permutation translates the law. As one sweep consists of \(d\) physical shuffles, this proves Theorem 21.

Harmonic tuple restriction

We first describe the probability law on the two child representations that arises from one maximizing vector. The law is a spectral weighting, not an independent random choice of Young diagrams. The removal estimates below hold uniformly over that weighting.

The position action of \(S_n\) on \(X_{n,k}\) commutes with the action of \(S_k\) on the tuple labels. Pieri’s rule (Sagan 2001; Stanley 1999) gives the multiplicity-free injection decomposition (Dukes et al. 2020, sec. 3.2, equation (3.1)): one copy of \(V_\mu\otimes V_\xi\) precisely when \(\mu/\xi\) is a horizontal strip of size \(n-k\). In particular the position type \((n-k,\beta)\) has label type \(\beta\) at this smallest tuple size. It does not occur on \(X_{n,k-1}\). Consequently its functions are harmonic: summing over any one tuple entry, with all the others fixed, gives zero.

Work in the position-\(\lambda\) isotypic space of \(\ell^2(X_{n,k})\), which is \(V_\lambda\otimes V_\beta\) under the commuting position and slot-permutation actions. Use counting norm here and take a unit eigenvector \(v\) attaining a positive value of \(W_n(\lambda)\). Equation (64) implies \(Pv=v\). Decompose \(v\) by the set of labels in each half and then by the two position types. The squared component norms define a probability law. Write \(a,b\) for the numbers of labels in the halves, \(a+b=k\), and \(r,s\) for their first-row deficits. Branching and the tuple realization give \[ 0\le r\le a,\quad 0\le s\le b,\quad r,s\ge k-m, \qquad W_n(\lambda)\le\mathbb E[W_m(\mu)W_m(\nu)]. \tag{71}\] The last lower bounds follow from \(\mu,\nu\subseteq\lambda\). The decompositions by label sets commute with the half-position groups, so they do not create additional types.

Three ways to close the level induction

We have controlled both the imbalance of the two tuple occupancies and the loss from an occupancy to a child representation level. The next step is to turn those two controls into the first bound in Theorem 25. Three potentials do this with different sources of strictness: a fixed multiplicative margin, a large square-root correction, or a unit square-root correction coupled to a fixed-level estimate. We first complete the constant-margin proof. The two square-root alternatives then show how to replace that margin; the last also supplies the fixed-level estimate (85).

Capped potential comparisons. The three inductions use the same elementary estimates. For \(c>0\) set \[E_c(x)=\begin{cases}x\log(ec/x),&0<x\le c,\\c,&x>c,\\0,&x=0, \end{cases} \qquad R_c(x)=\sqrt{\min(x,c)}.\] Take \(c=\alpha m\), where \(0<\alpha\le1/8\) is fixed, and write \(H=\log(en/k)\), \(D=(a-k/2)^2/k\) and \(U_1=(a-r)\mathbf1_{\{r<c\}}\), with \(U_2\) defined in the other half. The identities \(E_{2c}(k)=2E_c(k/2)\) and \(a+b=k\) give \[0\le E_{2c}(k)-E_c(a)-E_c(b) \le a\log(2a/k)+b\log(2b/k)\le4D.\] For the first inequality on the right, the magnitude of the negative second derivative of \(E_c\) is at most \(1/x\); integrating from the balanced split compares its gap with the displayed entropy gap. The last inequality is the relative-entropy bound by the corresponding chi-square divergence on two points. Concavity and \(E_c(0)=0\) also give \[E_c(a)-E_c(r) \le U_1\{1+\log_+(c/a)\}.\] When \(a\ge k/4\), the braces are at most \(H\). When \(a<k/4\), their excess over \(H\) costs at most \(a\log(k/a)\le k/e\), while \(D\ge k/16\). Thus \[ E_{2c}(k)-E_c(r)-E_c(s)\le C D+H(U_1+U_2). \tag{78}\] All these inequalities include zero occupancies by continuity.

The map \(x\mapsto\sqrt{\min(x,c)}\) is a contraction as a function of \(\sqrt x\). Hence \(|R_c(a)-R_c(k/2)|\le\sqrt{2D}\), and \(R_c(a)-R_c(r)\le\sqrt{U_1}\). With \(s_0=\min(k,2c)\) this yields \[ R_{2c}(k)-R_c(r)-R_c(s) \le-(\sqrt2-1)\sqrt{s_0}+2\sqrt{2D} +\sqrt{U_1}+\sqrt{U_2}. \tag{79}\] These comparisons separate occupancy imbalance from the loss of representation level, so the estimates in Lemma 26 can be applied without conditioning on either event.

A constant multiplicative margin.

First take \(x_*=1/100\) and define \[H_N(j)=N h(j/N),\qquad h(y)=\begin{cases}y(1+\log(x_*/y)),&0<y\le x_*,\\ x_*,&y>x_*,\\0,&y=0.\end{cases}\] The function is nondecreasing and concave, and \(H_n(k)\ge c\Lambda_n(k)\). Put \(\Delta=H_n(k)-H_m(r)-H_m(s)\ge0\). There are absolute \(\beta,C>0\) such that \[ \mathbb Ee^{\beta\Delta}\le C. \tag{80}\] Here is the loss calculation. For \(k/n\ge3/5\), the diagram containment bound gives \(r,s\ge m/5\) and the gap is zero. Otherwise introduce \(H_m(a)+H_m(b)\) and use the preceding entropy comparison. If \(a>4m/5\) but \(r<x_*m\), containment implies \(k<(1+x_*)m\). Therefore \(D\ge c m\), which bounds the entire capped loss, at most \(x_*m\). For all other occupancies the same calculation, with \(1+\log_+(4x_*m/k)\) in place of \(H\), gives \[\Delta\le CD+J(V_1+V_2),\quad D=(a-k/2)^2/k, \quad J=1+\log_+(4x_*m/k),\] where \(V_1=(a-r)\mathbf1_{\{r<x_*m,a\le4m/5\}}\), and similarly for \(V_2\). On this indicator \(m-a-r\ge m/10\). The binomial moments in (73) imply \[\mathbb Ee^{tJV_i}\le1+\sum_{l\ge1} [(e^{tJ}-1)C_{1/10}\sqrt{k/n}]^l.\] The ratio is uniformly small for a sufficiently small fixed \(t\). Hölder and (72) prove (80).

For all sufficiently large \(n\), uniformly over \(k\ge2\), the same component law satisfies \[ \Pr(r,s\ge1)\ge1/3,\qquad \Pr(r=s=0)\le1/12. \tag{81}\] For density at least \(3/5\) this is deterministic. Otherwise, when \(k\) is large the two occupancies lie between \(k/4\) and \(4m/5\) except with vanishing probability, and a zero child level would make a \(V_i\) at least \(k/4\). The preceding exponential estimate excludes this. For bounded \(k\ge2\), the probability of any removal loss tends uniformly to zero by the \(l=1\) bound. The binomial mixture has two positive occupancies with probability at least \(1-2^{1-k}\ge1/2\), and cannot have both zero.

Choose a finite base threshold for (81). Every nontrivial sweep norm at those finitely many sizes is strictly below one: equality in a product of orthogonal projections would give a vector fixed by every cube-edge transposition, hence by \(S_n\). Choose \(0<A\le1/2\) so the finite base norms are at most \(e^{-2A}\). We induct with \[ W_n(\lambda)\le e^{-A-\varepsilon H_n(k)}\quad(k\ge2). \tag{82}\] Level one is annihilated by exact one-card uniformity. Let \(G=\{r\ne1,s\ne1\}\) and \(b=\#\{r,s\text{ that are at least }2\}\). After dividing the recursive bound by the proposed right side, the remaining factor is \[\mathbb E[\mathbf1_G e^{-A(b-1)}e^{\varepsilon\Delta}].\] Without the last factor this is bounded uniformly below one: the event of two positive levels loses at least \(1-e^{-A}\), whereas only two zero levels can gain \(e^A-1\le2(1-e^{-A})\). Equations (81) bound the factor by \(1-(1-e^{-A})/6\). Moreover (80) and Hölder give \(\mathbb Ee^{\varepsilon\Delta}\le C^{\varepsilon/\beta}=1+O(\varepsilon)\). Since \(\mathbf1_Ge^{-A(b-1)}\le e^A\), reinstating \(e^{\varepsilon\Delta}\) costs only \(O(\varepsilon)\), uniformly. Also choose \(\varepsilon H_n(k)\le A\) at the base sizes. This proves (65).

A large square-root correction. A second invariant dispenses with the constant margin by inserting a square-root term. With \(\alpha=1/16\), set \[G_N(j)=N\phi(j/N),\qquad \phi(y)=\begin{cases}y\log(e\alpha/y),&0<y\le\alpha,\\ \alpha,&y\ge\alpha,\\0,&y=0,\end{cases}\] \[F_N(j)=G_N(j)+100\sqrt{\min(j,\alpha N)}.\] For \(Y=F_n(k)-F_m(r)-F_m(s)\) and \(s_0=\min(k,\alpha n)\), \[ Y\le-100(\sqrt2-1)\sqrt{s_0} +C_{100}\{1+D+H(U_1+U_2)\}, \tag{83}\] where \(H=\log(en/k)\), \(D=(a-k/2)^2/k\), and the \(U_i\) are the uncut losses in (75). Indeed (78) and (79), together with \(\sqrt D\le1+D\) and \(\sqrt{U_i}\le U_i\) for integer losses, give (83). The split and loss tails imply, for small \(\tau\ge0\), a bound \[\mathbb Ee^{\tau C_{100}\{1+D+H(U_1+U_2)\}}\le e^{C'\tau}.\] For example the tail in (75) bounds \(\mathbb Ee^{cHU_i}\) uniformly for a small fixed \(c>0\); Hölder and convexity then give the displayed bound at smaller exponents. Since \(s_0\ge\alpha k\), one fixed threshold \(K\) makes \(\mathbb Ee^{\tau Y}\le1\) for every \(k>K\) and all sufficiently small \(\tau\).

For \(2\le k\le K\), take \(n\) large enough that the potentials are uncapped at these levels. Put \(L=(a-r)+(b-s)\), and decompose the gap without conditioning on the loss event: \[Y=Q-100S+R,\qquad Q=a\log(2a/k)+b\log(2b/k),\quad S=\sqrt a+\sqrt b-\sqrt k,\] where \(0\le R\le(H+C_K)L\). The binomial mixture gives \(\mathbb EQ\le4\mathbb ED\le1\). Both occupancies are positive with probability at least \(1/2\), and then \(S\ge1/2\), so \(\mathbb ES\ge1/4\). The first removal moment gives \(\mathbb EL\le C_K e^{-H/2}\). Consequently \(\mathbb EY\le-24+o(1)\le-12\) for all sufficiently large \(n\), uniformly over these finitely many levels.

The same bound also justifies a uniform Taylor remainder. We have \(|Y|\le C_K+KH\mathbf1_{\{L>0\}}\) and \(\Pr(L>0)\le C_K e^{-H/2}\), and therefore \[M_K:=\sup\mathbb E\big[Y^2e^{|Y|/(4K)}\big]<\infty,\] where the supremum is over these levels, sizes, and component laws. For \(0<\tau\le\min\{1/(4K),12/M_K\}\), Taylor’s inequality gives \(\mathbb Ee^{\tau Y}\le1+\tau\mathbb EY+\tau^2 M_K/2\le1-6\tau\). The remaining finitely many sizes are covered by shrinking \(\tau\) using the strict norm gap. Induction now proves the invariant \(W_n(\lambda)\le e^{-\tau F_n(k)}\).

A unit correction and fixed-level bootstrap. A third version uses coefficient one instead of \(100\). Use the preceding definition of \(G_N\) with \(\alpha=1/8\), and put \(\Phi_N(j)=G_N(j)+\sqrt{\min(j,\alpha N)}\). The cut losses \(L_i\) in Lemma 26 give \[ \Phi_n(k)-\Phi_m(r)-\Phi_m(s) \le-c_0\sqrt k+C_0(a-b)^2/k+C_0H(L_1+L_2). \tag{84}\] Here are the capped cases in this comparison. Put \(c=\alpha m\). If \(a,b\in[.4k,.6k]\) and \(c/k\le.4\), both child square roots are capped, so their saving over the root is \((2-\sqrt2)\sqrt c\ge(2-\sqrt2)\sqrt k/4>.1\sqrt k\); we used \(c/k\ge1/16\). If \(c/k\ge.4\), each child square root is at least \(\sqrt{.4k}\) and the root is at most \(\sqrt k\), giving the same saving. Outside this occupancy interval, \(D\ge k/100\), and the square-root gap, at most \(\sqrt k\), is bounded by \(-.1\sqrt k+110D\). This proves the required no-loss bound.

The entropy comparison (78) and the root loss \(\sqrt{L_i}\le L_i\le HL_i\) cover the cut losses. The only omitted case has \(a>3m/4\) and \(r<m/8\), or its counterpart. Containment gives \(k<9m/8\), hence \(D>m/32\); the entire capped entropy and square-root loss is at most \(m\), and so is bounded by \(32D\). These bounds prove (84) with \(c_0=1/10\) and an absolute \(C_0\). Equations (72) and (74) imply \[\mathbb Ee^{\tau(\Phi_n(k)-\Phi_m(r)-\Phi_m(s))} \le e^{\tau(B-c_0\sqrt k)}\] for fixed \(B\) and all sufficiently small \(\tau\). One may start this induction through the additional quantitative fact \[ \max_{\lambda:n-\lambda_1=k}W_n(\lambda)=O_k(n^{-1/4}) \qquad(k\ge1\text{ fixed}). \tag{85}\] Induct on \(k\). A positive removal loss has probability \(O_k(n^{-1/2})\). Without losses, two positive child levels are smaller than \(k\) and obey the induction hypothesis. All labels in one half has probability at most \(2^{1-k}\), giving for \(k\ge2\) \(M_k(2m)\le2^{1-k}M_k(m)+O_k(m^{-1/4})\). Since \(2^{1-k}2^{1/4}<1\), this proves (85); level one vanishes. For any fixed upper level \(K\), the estimate is eventually stronger than \(e^{-\tau\Phi_n(k)}\) simultaneously for \(1\le k\le K\) if \(\tau\le1/(8K)\), since \(\Phi_n(k)=k\log n+O_K(1)\) there. Shrinking \(\tau\) handles the remaining finite sizes. Thus it supplies one common small \(\tau\) for all bounded levels, and then (84) closes induction for the larger levels. Thus all three invariants prove the first assertion of Theorem 25, while (85) records a separate fixed-level estimate.

Cycle moments from positive tensor traces

We next prove the density estimate. In a node of size \(2m\) in the recursive network, form the bipartite graph of input and output switch cells, with one edge for each tracked card. It is a union of paths and even cycles, including double edges. Let \(c_v^*\) be its cycle count; let \(c_v\) be the count when all cards are tracked. A node of size \(2^j\) has height \(j\). Write \(C_j^*,C_j\) for their sums over all nodes at height \(j\). Then \(C_j^*\le k/2\) and \(C_j^*\le C_j\). The full count at a node is the number of cycles of the relative permutation of its two children. In particular it depends only on the randomness below that node, irrespective of the tracks arriving from above.

For \(q\ge1\) put \(Z_l(q)=\mathbb E_{g\sim K_{2^l}}q^{\#\mathrm{cycles}(g)}\). This scalar generating function is defined for every real \(q\ge1\). For an integer \(q\) it is also the unnormalized trace of \(K_{2^l}\) on \((\mathbb C^q)^{\otimes2^l}\). The tensor identity in Lemma 22, specialized to this integer alphabet, gives \[ Z_l(q)\le Z_{l-1}(q)Z_{l-1}(1+(q-1)/2) \qquad(q\in\mathbb Z_{\ge1}). \tag{86}\] For completeness, divide the positive child operator by its trace and call the resulting density matrix \(D\). Expanding the crossing average over a uniformly chosen subset \(S\) of tensor positions gives \(Z_l(q)=Z_{l-1}(q)^2\mathbb E_S\operatorname{tr}(D_S^2)\). The partial trace of a permutation is its induced permutation on \(S\), multiplied by \(q\) for each cycle avoiding \(S\). Therefore its norm is at most that scalar. Bounding \(\operatorname{tr}(D_S^2)\) by \(\|D_S\|_{\mathrm{op}}\) and averaging \(S\) contributes at most \(1+(q-1)2^{-|C|}\le1+(q-1)/2\) per cycle, proving the recursion.

Two useful explicit versions are \[\begin{align*} 2^{-l}\log Z_l(1+2^h)&\le2^h(.81)^l &&(h=0,1,\ldots),\tag{87}\\ \log Z_l(1+w)&\le w(2^l)^\gamma,\qquad \gamma=\log_2(1+\log_2(3/2))<1 &&(w=2^h,\ h\in\mathbb Z_{\ge0}). \tag{88}\end{align*}\] For \(q>2\) the normalized induction factor is \(3/4\); for \(q=2\) use \(Z_l(3/2)\le Z_l(2)^{\log_2(3/2)}\), giving factor \((1+\log_2(3/2))/2<.81\). The same two cases yield the sharper exponent in (88), since \(3/2\le2^\gamma\). The base \(Z_0(q)=q\) satisfies both bounds.

Here is the conditional form needed to sum heights. Let \(\mathcal F_h\) be the sigma-field generated by all switches at heights at most \(h\), with the trivial sigma-field when \(h<1\). Reveal \(\mathcal F_{j-l-1}\). Each child of a height-\(j\) node has conditional average \(A^*UA\), with \(U\) a fixed unitary and \(A\) a tensor product of \(l\)-coordinate sweeps on \(2^l\)-slot cells. Independence of the two children and Hilbert–Schmidt Cauchy–Schwarz show \[ \mathbb E[q^{C_j}\mid\mathcal F_{j-l-1}] \le Z_l(q)^{n/(2\cdot2^l)}. \tag{89}\] Indeed, writing \(F_0,F_1\) for the two conditional tensor mean operators, \(\operatorname{tr}(F_0^*F_1)\le\operatorname{tr}((AA^*)^2) \le\operatorname{tr}(AA^*)\), and the trace factors over the cells. Fresh switches in different height-\(j\) nodes are conditionally independent.

Choose \(\delta>0\) with \(4\delta<1-\gamma\). Partition heights into bands \([b,2b-1]\) for powers of two \(b\), and separate alternating bands. For \(b\ge2\), take \(l=b/2\) and round \(2^{2\delta b}\) up to an integer alphabet, then its excess above one up to a power of two. Equations (88)–(89) give \[\mathbb E[2^{2\delta bC_j}\mid\mathcal F_{b/2-1}] \le\exp(Cn2^{-\eta b}),\qquad \eta=(1-\gamma)/2-2\delta>0.\] Conditional Hölder over the at most \(b\) heights gives the same bound for \(2^{2\delta\sum C_j}\) in the band. A smaller band of the same parity ends below \(b/2\), so its factor is measurable for this conditioning. Integrate the highest band first and iterate; Cauchy–Schwarz combines the two parities. For \(J\ge2\) the result is \[ \mathbb E2^{\delta\sum_{j\ge J}C_j} \le\exp(Cn2^{-\eta'J}),\qquad \eta'=\eta/2. \tag{90}\] The use of full counts is essential: replace tracked counts by full counts in every band where conditional integration will be used before performing that integration. Tracked lower counts can otherwise depend on the routes chosen above them.

Taking \(J\) a sufficiently large constant multiple of \(\log_2(en/k)\), the deterministic bound on lower heights and (90) give, uniformly over initial tuples, \[ \mathbb E2^{\delta\sum_jC_j^*}\le e^{C\Lambda_n(k)}. \tag{91}\] Equivalently one may use (87): in a band starting at \(b\), the conditional logarithmic bound is \((n/2)2^{\lceil2\delta b\rceil}(.81)^{\lfloor b/2\rfloor} \le Cn e^{-\gamma_0b}\) for a sufficiently small fixed \(\delta\). Using tracked deterministic bounds below \(\gamma_0^{-1}\log(n/k)\) and full counts above it proves the same estimate with explicit geometric decay in band height.

An entropy coding proof of the cycle moment

The tensor argument proves the required moment. The following coding argument also controls the cycle count under an arbitrary change of the switch law, charging its increase to relative entropy. This is the additional conclusion we retain from this alternative proof. In this subsection entropy is measured in bits.

At height \(t\) the switch array consists of both outer layers of every node of size \(2^t\); all these raw switch bits are independent under the reference fair law. Let \(Q\) be any probability law on the full array of raw switches at all heights of the \(n\)-position reflected network. Write \(\mathcal B_t\) for the vector of bits at height \(t\) and define the nonnegative number \[I_t=|\mathcal B_t|-H_Q(\mathcal B_t\mid\mathcal B_1,\ldots, \mathcal B_{t-1}),\] where conditional Shannon entropy is already averaged under \(Q\). Thus \(I_t\ge0\) and \(\sum_tI_t=D(Q\Vert\mathrm{fair})\).

Apply this to the law tilted by \(2^{\varepsilon\sum C_j^*}\). The variational identity \[\log_2\mathbb E2^{\varepsilon\sum C_j^*} =\varepsilon\mathbb E_Q\sum C_j^*-D(Q\Vert\mathrm{fair})\] proves (91) when \(\varepsilon C<1\). Thus the tensor-trace argument and the coding argument each supply a complete, separate proof of the required cycle moment.

From routed cycles to densities and multiplicities

Consider specified injective endpoints for \(h\) links in a size-\(2m\) node. Let \(e\) be the total number of shared input and output pairs, and let \(c\) be the cycle count in their union. The links admit exactly \(2^{h-e+c}\) proper child colorings. Each has switch probability \(2^{-2h+e}\). If \(R=(2m)^h p\) is the provisional transition density, the child recursion is \[ R=\sum_{\text{proper colors}}2^{-h+e}R_0R_1 =2^c\operatorname{Avg}_{\text{proper colors}}R_0R_1. \tag{94}\] Jensen with exponent \(1+\delta\) charges a factor \(2^{\delta c}\). After unrolling to one-slot leaves, \[(n^kp(x,y))^{1+\delta} \le n^k\mathbb E_{K_n}[\mathbf1_{\{\pi x=y\}} 2^{\delta\sum C_j^*}].\] The remaining coefficients are the actual switch probabilities: each link is counted once per height, and specified recursive routings are disjoint events. Summing in \(y\) and using \((n)_k/n^k\le1\) proves (67). Symmetry supplies the corresponding column estimate. We will also use the provisional normalization directly: \[ \sup_x\sum_y n^{-k}(n^kp(x,y))^{1+\delta} \le e^{C\Lambda_n(k)}. \tag{95}\] Indeed summing the preceding unrolled inequality proves this before the factor \((n)_k/n^k\) is inserted. Equivalently it follows from the density bound after enlarging \(C\), since \[\log\frac{n^k}{(n)_k} =\sum_{i=0}^{k-1}-\log(1-i/n) \le\int_0^k-\log(1-x/n)\,dx\le k.\] The integral is finite also at \(k=n\).

The row and column bounds imply bounded operators \(K_n:L^1\to L^{1+\delta}\) and \(K_n:L^{(1+\delta)/\delta}\to L^\infty\), each with norm at most \(M=e^{C\Lambda_n(k)}\) after enlarging \(C\). Riesz–Thorin interpolation decreases the reciprocal exponent by \(\delta/(1+\delta)\) at each application. After \(p_0=\lceil(1+\delta)/\delta\rceil\) applications, with probability-space inclusion for the last step, \(K_n^{p_0}:L^1\to L^\infty\) has norm at most \(M^{p_0}\). Equivalently, \[ \sup_{x,y}|X_{n,k}|K_n^{p_0}(x,y)\le e^{C\Lambda_n(k)}. \tag{96}\] The diagonal kernel bound gives (68).

There are two ways to use the label multiplicity \(f_\beta\). For the first transfer, the goal is to use the \(f_\beta\) equivalent slot copies of one position vector. Clip the entries \(p(x,y)\) of \(K_n\) above \(n^{-k}\sqrt{f_\beta}\), setting them to zero, and call the retained matrix \(M_0\). The provisional moment bound (95) and symmetry give \[ \|K_n-M_0\|_{\mathrm{op}}\le e^{C\Lambda_n(k)}f_\beta^{-\delta/2}. \tag{97}\] Since every row sum is at most one and \(|X_{n,k}|\le n^k\), \(\|M_0\|_{\mathrm{HS}}^2\le\sqrt{f_\beta}\). Clipping commutes with relabeling the tuple slots. Compressing to position type \(\lambda\), whose label type is \(\beta\), therefore repeats each singular value at least \(f_\beta\) times. Its compressed norm is at most \(f_\beta^{-1/4}\). If \(\log f_\beta\) exceeds a sufficiently large constant times \(\Lambda_n(k)\), these two estimates give \(W_n(\lambda)\le e^{-c\log f_\beta}\); otherwise (65) applies. This proves (69).

The clipping proof now gives the combined level-and-tail estimate. To obtain the explicit tail bound (66) by a different mechanism, average a matrix coefficient over all slot copies. Tensor a maximizing unit vector in \(V_\lambda\) with an orthonormal basis of \(V_\beta\), obtaining orthonormal functions \(u_j\), \(1\le j\le f_\beta\), in probability norm. Define \[F(x,y)=\frac{1}{f_\beta}\sum_j\overline{u_j(x)}u_j(y).\] Then \(\mathbb E(F\mathcal K)=W_n(\lambda)\) and \(\mathbb E|F|^2=f_\beta^{-1}\). The diagonal \(G(x)=f_\beta^{-1}\sum_j|u_j(x)|^2\) is slot-invariant and has mean one. Each orbit of the slot-permutation group is the set of \(k!\) orderings of one \(k\)-element set, so has probability \(\binom nk^{-1}\). Nonnegativity therefore gives \(G(x)\le\binom nk\). Cauchy–Schwarz gives the same bound for \(|F(x,y)|\). With \(p=1+\delta\) and \(p'=p/(p-1)>2\), Hölder gives \[ W_n(\lambda)\le\|\mathcal K\|_p\|F\|_{p'} \le e^{C\Lambda_n(k)}{n\choose k}^{1-2/p'}f_\beta^{-1/p'}. \tag{98}\] This proves (66) with \(\zeta=1/p'\). Since \(D_\lambda\le{n\choose k}f_\beta\), geometric interpolation with (65) proves (70).

Finally, the tuple trace gives a completion that needs no tail-dimension interpolation. At exact level \(k\) the multiplicity in \(X_{n,k}\) is \(f_\beta\), while the regular multiplicity is \(D_\lambda\le{n\choose k}f_\beta\). For an integer \(p>p_0\), positivity and the estimates (65) and (68) yield \[ \operatorname{tr}_{\rm reg}K_n^p-1 \le\sum_{k=1}^{n-1} e^{-[(p-p_0)c-C-1]\Lambda_n(k)}. \tag{99}\] Alternatively (70) bounds the regular Fourier sum directly by \(\sum_{k\ge1}2^k e^{-c_1M\Lambda_n(k)}\) once \(c_2M\ge2\). Both sums tend to zero for a sufficiently large fixed exponent. Schatten Hölder gives \(\|T_n^p|_{\mathbf1^\perp}\|_{\mathrm{HS}}^2\le\operatorname{tr}_{\rm reg}K_n^p-1\) without assuming normality of \(T_n\). Thus these arguments mix the entire permutation law after an absolute number of sweeps, each consisting of exactly \(d\) physical shuffles.

Compression of the transposition generator

Let \[L_n=\frac1n\sum_{i<j}(I-(ij)),\qquad T=L_n-L_0-L_1,\qquad J=L_0-L_1,\] where \(L_0\) and \(L_1\) act on the first and second halves, respectively, and each uses normalization \(1/m\) when \(n=2m\). Transpositions in these formulas denote their unitary representation matrices. The transposition content formula (Vershik and Okounkov 2005) makes \(L_n\) scalar on \(V_\lambda\), with value \[ \ell=r-\frac{\binom r2+c(\rho)}n, \qquad r/2\le\ell\le r. \tag{102}\] Here \(c(\rho)\) is the sum of the box contents of \(\rho\). The three operators in this display commute with each other before compression, although they need not commute with \(P\).

The induced tensor spaces and a single split

The level estimate is now complete. The remaining goal is the fourth-moment bound. We will prove it on larger representations containing \(V_\lambda\), because a trace of a positive power can only increase under such an enlargement.

More precisely, a list of categories with sizes \(b_j\) and representations \(V_{\eta_j}\) defines \[\mathcal M=\operatorname{Ind}_{\prod_jS_{b_j}}^{S_n} \bigotimes_jV_{\eta_j},\qquad \sum_jb_j=n.\] Its log trace is \(\sigma=\log\operatorname{Tr}_{\mathcal M}F_n^4\), with \(\sigma=-\infty\) if the trace is zero. Empty categories may be omitted. An induced module will have categories of total size \(n\). A row category consists of a diagram \(\eta\) of size \(b\), an alphabet of dimension \(q\ge\ell(\eta)\), where \(\ell(\eta)\) is its number of rows, and an orientation, ordinary or sign-twisted. A regular category consists of a spatial diagram \(\kappa\) of size \(b\) and \(b\) distinct named labels. We may designate one ordinary one-row category of alphabet dimension one as the background; it may be empty. All other categories are payload, including ordinary one-row categories of alphabet dimension one. In the application the background is the original first row of \(\lambda\). Every descendant of a payload category remains payload after restriction or a change of alphabet. There is at most one background category in each node, so its child counts are determined by the payload counts and the two half sizes. Isomorphic categories remain distinct when their labels or origins differ.

For a row category \(j\), \(\eta\) denotes the alphabet type before the sign twist. Its spatial factor \(V_{\eta_j}\) in \(\mathcal M\) is \(V_\eta\) in ordinary orientation and \(V_\eta\otimes\operatorname{sgn}_{S_b}\cong V_{\eta'}\) in sign-twisted orientation, where \(\eta'\) is the conjugate partition. In both orientations, \(q\ge\ell(\eta)\) and the multiplicity \(G_q(\eta)\) below refer to this pre-twist diagram.

Realize row categories in signed tensor powers. Each category has its own alphabet; let \(\mathcal H\) be the space spanned by words specifying one alphabet symbol at each of the \(n\) position slots, with the prescribed number of slots in each category. An adjacent swap contributes \(-1\) exactly when both symbols are odd; these adjacent swaps generate the graded permutation action. Use odd symbols precisely for sign-twisted categories. This gives the indicated representation on the stabilizer of a category allocation, and induction sums over allocations. In a regular category, each named label appears once. The commuting group is \(U(q)\) for each row alphabet and \(S_b\) acting on the names of each regular category. Let \(E\) be the product of their isotypic projections onto the row types \(\eta\) and regular types \(\kappa\). On a fixed category allocation, Schur–Weyl duality and the regular bimodule decomposition give the spatial tensor product and its multiplicity space. Summing over allocations therefore gives \[ g=\prod_{\mathrm{row}}G_q(\eta) \prod_{\mathrm{regular}}D_\kappa \tag{109}\] copies of the desired spatial induced module: \[E\mathcal H\cong\mathbb C^g\otimes\mathcal M.\] Here \(G_q\) is the dimension of the polynomial \(U(q)\) representation. Spatial permutations act trivially on \(\mathbb C^g\), so \(E\) commutes with the network operators and a spatial trace on \(E\mathcal H\) is \(g\) times the trace on \(\mathcal M\).

A child projection \(W\) specifies counts \(b_0+b_1=b\) and types \(\mu,\nu\) in the two halves of each category. For a row category, use the two child \(U(q)\) isotypic projections, which commute with the diagonal \(U(q)\) action and hence with \(E\). For a regular category first fix its subset of \(b_0\) names in the first half and project the two name groups onto \(\mu,\nu\); then sum these orthogonal projections over all \(\binom b{b_0}\) subsets. This sum preserves each name subset and is invariant under global relabeling, so it also commutes with \(E\). The projections \(W\) sum to the identity and commute with \(Q=F_m\otimes F_m\). Only types with positive Littlewood–Richardson coefficient for the parent type contribute to \(WE\); we call these choices compatible. All row types in this description are taken before their inherited sign twist. Write \(g_i\) for the multiplicity (109) evaluated on the induced module in half \(i\). Put \[\mathcal L=n\log n- \sum_{\mathrm{row}}\sum_i\eta_i\log\eta_i -\sum_{\mathrm{regular}}b\log b.\]

Take \(p=4\), and let \(Y=WQ\ge0\). The needed Schatten inequality is \[ \mathop{\mathrm{Tr}}(EPYPE)^p \le\|WPE\|^{2p-4}\mathop{\mathrm{Tr}}(PY^{p/2}P)^2. \tag{111}\] Indeed apply three-lines interpolation to \(Y^{pz/4}WPE\), extended by zero on the kernel of \(Y\), between the operator norm at \(\Re z=0\) and the fourth Schatten norm at \(\Re z=1\). At \(z=2/p\) the target norm is the \(2p\) norm. Raising the interpolation inequality to \(2p\) gives (111): at the fourth-norm endpoint first obtain \(\mathop{\mathrm{Tr}}(EPY^{p/2}PE)^2\), then drop the orthogonal compression by \(E\) using Hilbert–Schmidt contraction. Thus no commutation of \(P\) with \(Y\) is required.

We can now pass from the count-space trace to the desired spatial trace. Let \(M\) be the number of compatible child projections \(W\). For each payload category of size \(b\), the count split and two child partitions have at most \(\exp(Cb^{2/3})\) choices, by the partition bound. The single background has no type choice and its counts are determined by the payload counts. Therefore \(\log M\le C\sum_{\mathrm{payload}}b^{2/3}\). Named subsets are already aggregated in \(W\) and are not choices counted by \(M\).

Resolve \(Q=\sum_W WQ\) on \(E\mathcal H\). The Schatten triangle inequality, followed by (111) with \(p=4\), the angle bound, and (112), gives, for \(m\ge2\), \[\begin{align*} g e^\sigma &=\mathop{\mathrm{Tr}}(EPQPE)^4\\ &\le M^4\max_W\bigg\{ e^{\sigma_0+\sigma_1-(\mathcal L-\mathcal L_0-\mathcal L_1)} \left[\prod_{\mathrm{row}}G_q(\mu)G_q(\nu)\right]^2 \\[-2pt] &\hspace{5em}{}\times g_0g_1 2^{\gamma s/2} \prod_{\mathrm{regular}}2^{-b}\binom b{b_0}\bigg\}. \end{align*}\] The angle contributes two copies of each child row carrier, and the child trace contributes a third. Dividing by \(g\) and taking logarithms therefore yields the explicit bound \[\begin{align*} \sigma\le\max_W\bigg\{&\sigma_0+\sigma_1+4\log M -(\mathcal L-\mathcal L_0-\mathcal L_1)\\ &+\sum_{\mathrm{row}} [3\log G_q(\mu)+3\log G_q(\nu)-\log G_q(\eta)]\\ &+\sum_{\mathrm{regular}} [\log D_\mu+\log D_\nu-\log D_\kappa +(\gamma/2-1)b\log2+\log\tbinom b{b_0}] \bigg\}. \end{align*}\] For \(m=1\) replace \(\gamma\) by one, at an extra cost \(O(s)\). This calculation motivates the potentials that we now telescope.

For a diagram of size \(b\), put \(I(\eta)=\sum_i\eta_i\log(b/\eta_i)\) and set \(\delta=1/32\). Give categories the potentials \[ \phi(\eta)=\delta I(\eta)\quad\text{(row)},\qquad \phi(\kappa)=\log D_\kappa-\frac{1-\delta}{2}b\log b \quad\text{(regular)}. \tag{115}\] Let \(\Phi\) be their sum. For every category with child counts \(b_0+b_1=b\), define \[v_b=b\{\log2-H_2(b_0/b)\},\qquad H_2(x)=-x\log x-(1-x)\log(1-x),\] with \(v_0=0\). Thus \(H_2\) uses natural logarithms in this section, and \(v_b\) is the loss from an imbalanced count split. The preceding lemmas imply the single-split accounting inequality \[\begin{align*} \sigma\le\max\bigg\{&\sigma_0+\sigma_1 -(\Phi-\Phi_0-\Phi_1)-\sum_{\mathrm{payload\ row}}v_b \\ &+C_1\sum_{\mathrm{payload}}b^{2/3} +C_1\sum_{\substack{\mathrm{payload\ row}\\q\ge2}} q^2\log(e(1+b/q^2))+C_1s\mathbf1_{m=1}\bigg\}. \end{align*}\] Here the maximum is over compatible child counts and types. To derive this form from [rec:alphabet-master-split], use the Cauchy identity \[\sum_{\substack{\xi\vdash b\\\ell(\xi)\le q}}G_q(\xi)^2 =\binom{b+q^2-1}{q^2-1}.\] It bounds the positive child row-carrier logarithms by \(Cq^2\log(e(1+b/q^2))\); for \(q=1\) all carrier factors are one. Discarding the favorable parent carrier logarithm only increases the bound. Also \[\mathcal L-\mathcal L_0-\mathcal L_1 =\sum_{\mathrm{all}}v_b+ \sum_{\mathrm{row}}(I(\eta)-I(\mu)-I(\nu)),\] and both sums have nonnegative summands. Indeed compatibility implies that \(\mu+\nu\) dominates \(\eta\); Schur concavity followed by entropy concavity gives \(I(\eta)\ge I(\mu+\nu)\ge I(\mu)+I(\nu)\). Retain \(-v_b\) for payload rows and replace the negative row-entropy decrement by \(-\delta[I(\eta)-I(\mu)-I(\nu)]\). The unused background and regular imbalances are nonnegative and may be discarded. For a regular category the carrier ratio gives \(\log D_\mu+\log D_\nu-\log D_\kappa\), and \(\log\binom b{b_0}\le bH_2(b_0/b)\) gives \((\gamma/2-1)b\log2+bH_2(b_0/b) \le(1-\delta)bH_2(b_0/b)/2\) because \(\delta<1-\gamma\). This proves [rec:alphabet-split-budget].

Changing alphabets and paying for the changes

The case \(r=0\) is the trivial representation and satisfies both bounds with equality. Assume \(r>0\). Embed \(V_\lambda\) in the module induced from its first row as background and \(\rho\) as payload. Fix large absolute \(A\) and then a much larger \(K\). To tune a diagram of size \(b\), take its rows longer than \(K\sqrt b\) as one row category; in the remaining diagram take columns longer than \(K\sqrt b\) as another row category, with orientation reversed. Put the residual diagram \(S\) in a regular category. Here is the representation containment used in this operation. If \(R\) is the selected top-row diagram and \(\xi\) the remainder, the parent is their sorted-row union, whose Littlewood–Richardson coefficient in \(\operatorname{Ind}(V_R\otimes V_\xi)\) is one. Apply the transposed version of this fact to remove the selected columns from \(\xi\). Transitivity of induction then embeds the parent in the module of the three resulting parts. Selected rows inherit the old orientation, and selected columns reverse it. If the old orientation was twisted, the residual regular spatial diagram is \(S'\) rather than \(S\); \(D_{S'}=D_S\), so its potential is unchanged. These conventions pass the old sign twist to every spatial factor. Thus tuning enlarges the spatial module, and its positive-power trace can only increase. Choosing a new alphabet afterward changes the multiplicity space in which that spatial module is realized. At the root only, group the selected row lengths \(l\) by \(\lfloor\log_2(r/l)\rfloor\), keeping the two orientations separate. No later tuning uses this grouping.

Assign a new row category its actual oriented height \(q\). A regular category stays regular. A row category of \(q=1\) never changes. For \(q\ge2\), retain its alphabet while \(b\ge Aq^2\); when \(0<b<Aq^2\), end that phase and tune the current diagram afresh. At birth, \[ q_{\rm new}\le\sqrt b/K,\qquad b_{\rm new}\ge K^2q_{\rm new}^2;\qquad q_{\rm new}\le q/L\ \text{at an exit},\quad L=K/\sqrt A>1. \tag{116}\] Thus no immediate retuning is needed and alphabet dimensions shrink geometrically along successive phases.

Let \(b_j\) be the initial payload category sizes, \(I_0\) the sum of their row entropies, \(s_0\) the initial regular size, and \(J_{\rm in}=\sum b_j\log(r/b_j)\). Hook products and the long-row construction give \[\begin{align*} \Phi_{\rm in}&\ge\delta I_0+\tfrac\delta2s_0\log s_0-C_Kr, \tag{117}\\ \log D_\lambda&\le\log\binom nr+I_0+\tfrac12s_0\log s_0+J_{\rm in}, \tag{118}\\ \sum_{j\ \mathrm{row}}b_j\log q_j&\le I_0+r\log2,\qquad J_{\rm in}\le\epsilon I_0+C_\epsilon r. \tag{119}\end{align*}\] Here are the dimension and entropy estimates underlying these bounds. The residual diagram has every row and column of length at most \(K\sqrt r\), so its hooks are at most \(2K\sqrt r\) and \[D_S\ge s_0!/(2K\sqrt r)^{s_0}.\] Together with \(s_0\log(r/s_0)\le Cr\), this proves the first line. For the dimension upper bound, induced-module containment contributes \(\binom nr\) and the payload allocation multinomial. Bound these by their entropy expressions, each row-category dimension by \(e^{I(\eta)}\), and the residual dimension by \(\sqrt{s_0!}\). This gives (118).

Within each initial row category the positive row lengths differ by at most a factor two. Its row distribution therefore has entropy at least \(\log q_j-\log2\), proving the first assertion of (119). To prove the second, choose a uniform payload box. Its category is determined by a flag for the row, column, or residual part and, for a row or column part, a nonnegative dyadic group index \(Z\), taking \(Z=0\) on the residual part. These data have entropy \(J_{\rm in}/r\). The mean of \(Z\) is at most \((I_0+J_{\rm in})/(r\log2)\), because a row of length \(l\) contributes \(\log_2(r/l)\) before taking the integer part. For any \(\alpha>0\), relative entropy against the geometric law proportional to \(e^{-\alpha z}\) gives \(H(Z)\le\alpha\mathbb EZ+C_\alpha\). Adding the flag entropy, which is at most \(\log3\), and choosing \(\alpha\) sufficiently small gives \(J_{\rm in}\le\epsilon I_0+C_\epsilon r\) after rearrangement. This is the reason for grouping at the root; no subsequent tuning needs that extra grouping.

We detail the amortization, because using one fixed alphabet would leave a divergent carrier cost. At an exit of mass \(b\), the adverse potential jump is at most \[ C_2b+C_Ks_{\rm new}+C_2b\log_+(q^2/b). \tag{120}\] To verify this jump estimate, denote by \(R,C,S\) the new row, column, and residual parts, of respective sizes \(|R|,c_*,s\). Entropy of the part assignment gives \[I_{\rm row}(\eta)\le I_{\rm row}(R)+I_{\rm row}(C) +I_{\rm row}(S)+b\log3.\] Since the old height is at most \(q\), \[I_{\rm row}(C)-I_{\rm col}(C) \le c_*\log q-c_*\log(c_*/q),\qquad I_{\rm row}(S)\le s\log q.\] The hook bound for the residual gives \[\phi(S)\ge\frac\delta2s\log b-C_Ks -\frac{1+\delta}{2}s\log(b/s).\] Substituting these inequalities and using \(x\log(b/x)\le Cb\) for \(0<x\le b\) proves (120); empty parts contribute zero. The total mass ever converted to regular categories is at most \(r\), because a regular category never becomes a row category again. We therefore charge the \(C_Ks_{\rm new}\) term only once to each converted box, for a total at most \(C_Kr\). The linear term \(C_2b\) in (120) will be charged to the total exit mass. Only its logarithmic excess needs an imbalance saving.

Call a split balanced when both child masses are in \([b/4,3b/4]\). During a phase with \(q\ge2\) the parent mass satisfies \(b\ge Aq^2\). At an unbalanced split, \(v_b\ge\theta b\), where \(\theta=\log2-H_2(1/4)>0\). Put \[f(t)=\frac{\log(e(1+t))}{t},\qquad t>0.\] The carrier cost is \(C_1bf(b/q^2)\le C_1bf(A)\), since \(f\) is decreasing. If a child of mass \(x\) exits at this split, then \[x\log_+(q^2/x)\le q^2/e\le b/(eA).\] There are at most two exiting children. Choose \(A\ge4\) so large that \(C_1f(A)+2C_2/(eA)\le\theta/2\). The carrier cost and these logarithmic excesses are then bounded by half of the negative imbalance term. At a balanced exit, \(x\ge b/4\ge Aq^2/4\ge q^2\), so the logarithmic excess is zero. No \(K\)-dependent constant has entered this choice of \(A\).

It remains to sum carrier costs at balanced nodes of a phase, which may form a branching subtree. Distribute each such cost evenly among its \(b\) boxes. A box pays \(C_1f(b/q^2)\). Along its balanced ancestors, successive masses decrease by a factor at most \(3/4\), even if unbalanced nodes intervene. Reversing the sequence and using \(b/q^2\ge A\) gives \[\sum_{\text{balanced ancestors}}f(b/q^2) \le\sum_{j\ge0}f(A(4/3)^j) \le \frac{C\log(e(1+A))}{A}.\] Summing over boxes bounds the balanced cost by a constant times the phase’s birth mass. The constant depends on the fixed \(A\) and is independent of \(K\). The exit frontier has total mass at most that birth mass, so it also pays the linear exit cost \(C_2b\). By (116), a box initially in row category \(j\) encounters at most \(1+\log q_j/\log L\) phases: each retuning reduces the new alphabet by a factor \(L\), and regular conversion ends the sequence. Each of the total birth mass and the total exit mass is consequently at most \[\sum_{j\ \mathrm{initial\ payload\ row}}b_j (1+\log q_j/\log L).\]

The \(b^{2/3}\) term is also summable, including categories that stay small through many ambient levels. At a balanced split, \[b_0^{2/3}+b_1^{2/3}-b^{2/3}\ge c b^{2/3}.\] The power sum cannot decrease at any other split or conversion and its terminal value is \(r\), so all balanced costs sum to \(O(r)\). For unbalanced splits, the positive error satisfies the numerical bound \[\sum_{\rm unbalanced}b^{2/3} \le\sum_{\rm unbalanced}b \le\theta^{-1}\sum_{\rm unbalanced}v_b.\] To bound the last sum, the scalar count entropy \(b\log(n/b)\) at ambient size \(n\) decreases by exactly \(v_b\) at a split. A conversion increases it by \(\sum_j b_j^{\rm new}\log(b/b_j^{\rm new})\). Its terminal value is zero, so summing all the nonnegative decrements gives \[ \sum_{\mathrm{payload\ splits}}v_b =r\log(n_{\rm root}/r)+J_{\rm in} +\sum_{\rm exits}\sum_j b_j^{\rm new}\log(b/b_j^{\rm new}). \tag{121}\] This identity bounds the total positive error by the initial count entropy and the conversion entropies; it makes no further subtraction of the operator term \(-v_b\). Each exit creates at most three categories, so its last sum is at most \(b\log3\) and is covered by the phase-mass bound. Finally the \(m=1\) term costs at most \(Cr\).

Iterating [rec:alphabet-split-budget] down to single sites, whose log trace is zero, now gives \[ \sigma_{\rm in}\le-\Phi_{\rm in}+C_Kr+ C_3\{r\log(n/r)+J_{\rm in}+r\} +\frac{C_3}{\log L}\sum_{j\ \mathrm{row}}b_j\log q_j. \tag{122}\] Here \(C_3\) depends on the already fixed \(A\), but not on \(K\); all \(K\)-dependent losses are in \(C_Kr\). Choose \(K\) after \(A\) so that \(C_3/\log L\) is small compared with \(\delta\), and then choose \(\epsilon\) in (119) sufficiently small. Equations (117)– (122) yield \[\sigma_{\rm in}\le -\tfrac\delta2 I_0-\tfrac\delta2s_0\log s_0+C h_n(r).\] The dimension comparison (118) proves (101). Combining its fourth-root bound with (100), in proportions chosen to cancel the positive \(C h_n(r)\) term, proves the final assertion of Theorem 28.

For clarity, this also supplies a complete mixing consequence. Choose an absolute integer \(q\) so large that the dimension powers are absorbed in \[\operatorname{Tr}_{\rm reg}F_n^q-1 \le\sum_{r=1}^{n-1}2^r e^{-c_2q h_n(r)}=o(1),\] where \(c_2>0\) is absolute after increasing \(q\). The count \(2^r\) bounds partitions of the lower diagram. Split at \(r=\sqrt n\) to see that the sum tends to zero: below it \(h_n(r)\ge\frac12r\log n\), and above it \(h_n(r)\ge r\). Schatten Hölder bounds the squared Hilbert–Schmidt norm of the nonconstant part of \(T_n^q\) by this positive moment, without requiring normality. Plancherel and translation therefore give total-variation convergence from every initial deck after \(q\) sweeps, or \(qd\) physical shuffles.

Dimension charges and the local sparse estimate

We need two elementary inputs, uniformly over surviving nontrivial types for all sufficiently large dyadic \(n\): \[ F_\lambda\ge b k,\qquad 1\le k\le n^{1/100}\ \Longrightarrow\ \|T_n|_{V_\lambda}\|\le2^{-b_1k\log_2n}, \tag{123}\] where \(b,b_1>0\) are absolute. We prove the sparse estimate locally because its range grows with \(n\).

For the dimension estimate, write \(\tau\) for the diagram below the first row. The hook formula gives \[D_\lambda=\binom nkD_\tau \bigg/\prod_{j\le\lambda_1} \left(1+\frac{\tau'_j}{\lambda_1-j+1}\right).\] The denominator is at most \(2^k\): for an integer \(t\ge0\) and positive integer \(a\), \(1+t/a\le2^t\), and \(\sum_j\tau'_j=k\). When \(k\le n/8\), the bound \(\binom nk\ge(n/k)^k\) proves \(F_\lambda\ge2k\). For \(k\ge n/8\), first suppose that a first row or first column has length \(a\ge n/10\). Transpose if needed and retain that row together with \(v=\lfloor n/100\rfloor\) boxes below it. Such a subdiagram exists: after transposition its tail has at least \(n/8\) boxes if the chosen row was the original first row, and at least \(n/2\) if it was the first column. Tableaux of a subdiagram extend to the full diagram. The same formula on this smaller diagram gives \(D_\lambda\ge\binom{a+v}{v}2^{-v}\), exponential in \(n\). If both the first row and first column are shorter than \(n/10\), every hook is shorter than \(n/5\) and Stirling’s inequality gives \(D_\lambda\ge(5/e)^n\). These cases prove the first estimate. They also show \(F_\lambda=O(k\log n)\) on the sparse range, the upper bound following from \(D_\lambda\le\binom nkD_\tau\) and \(D_\tau\le\sqrt{k!}\).

To prove the second estimate, realize \(V_\lambda\) on ordered injections of \(k\) labels. A function of that exact position type is harmonic in each label slot, because the type does not occur on \(k-1\) slots. For distinct input positions \(x_a,x_b\), let \(h_{ab}\) be their largest differing bit index in the sweep order. For \(J\subseteq[k]\) put \[g_J(x,y)=\prod_{a<b:\,a,b\in J} \left(1-\mathbf1_{\{y_{a,<h_{ab}}=y_{b,<h_{ab}}\}} (-1)^{y_{a,h_{ab}}+y_{b,h_{ab}}}\right).\] The individual route from an input to an output is unique. Two labels can first share a switch only at \(h_{ab}\), when their earlier output bits agree. Equal output bits also at \(h_{ab}\) make the prescription impossible, giving a zero factor; opposite bits give one common fair coin in place of two, giving a factor two. Otherwise the factor is one. Thus \(n^{-|J|}g_J\) is exactly the prescribed subtuple transition probability, including zero for incompatible routes.

The number of shared switches among \(s\) compatible paths is at most \(s\log_2s/2\), by splitting at the last coordinate and adding \(\min(s_0,s_1)\) to the two child counts. The binary entropy inequality pays this addition. Hence \(0\le g_J\le k^{k/2}\). On the exact position type we may replace \(g_{[k]}\) by \[g'(x,y)=\sum_{J\subseteq[k]}(-1)^{k-|J|}g_J(x,y):\] every omitted-slot term is annihilated by harmonicity. This sum has absolute value at most \(2^kk^{k/2}\). Moreover it vanishes if some label is isolated in the potential-contact graph, whose edge \(ab\) is the event \(y_{a,<h_{ab}}=y_{b,<h_{ab}}\); the terms with and without that isolated label then cancel in pairs.

A graph without isolated vertices contains a spanning forest without isolated vertices, and such a forest has at least \(\lceil k/2\rceil\) edges. For independent uniform, unrestricted binary strings \(x,y\), declare that \(ab\) is not an edge when \(x_a=x_b\); on distinct input pairs use the potential-contact condition above. An edge constraint in a forest costs \(d/n\) when a leaf is integrated out: the possible last differing input bit \(h\) has probability \(2^{h-1}/n\), and agreement of the earlier output bits costs \(2^{-(h-1)}\). Successive leaf removal therefore multiplies these costs. There are at most \(k^{2k+1}\) forests to include in the union bound. Conditioning both endpoint tuples to be injective costs at most two on \(k\le n^{1/100}\) for large \(n\). Consequently \[\Pr(\text{no isolated label}) \le2k^{2k+1}(d/n)^{\lceil k/2\rceil} \le2^{-(2/5)k\log_2n}\qquad(k\ge2).\] The tuple kernel density relative to uniform has the additional factor \((n)_k/n^k\le1\). Its compressed Hilbert–Schmidt norm is therefore at most \(2^kk^{k/2}\) times the square root of this probability. This is \(2^{-b_1k\log_2n}\) for an absolute \(b_1>0\), after increasing the lower size threshold. The operator norm is smaller, and at level one the sweep is exactly zero. This proves (123).

The charge to the deep core has the following form: \[ \sum_{x:\,a(x)\ge R}\{L+\log_2 a(x)\} \le(1+o(1))F_\lambda\qquad(R\longrightarrow\infty), \tag{124}\] uniformly over surviving nontrivial diagrams of sufficiently large size. Here the \(o(1)\) depends only on \(R\), not on the diagram. For any straight diagram of size \(u\), a box at minimum index \(a\) has hook length at most \(2u/a\): each of its row and column lengths is at most \(u/a\). Apply this to \(\tau\) in the first-row hook formula above. The coordinates below the first row shift by one, changing \(\log a\) by at most a constant. Stirling’s bound then gives \[\sum_{x\text{ below row }1}\{L+\log_2a(x)\} \le F_\lambda+O(k).\] If \(L>\sqrt{\log_2R}\), the lower bound \(F_\lambda\ge kL-O(k)\) absorbs that error uniformly as \(R\to\infty\).

In the complementary case, remove the first \(q=\lfloor\sqrt R\rfloor\) rows and columns. Let the remaining core have size \(u\). Applying the additive-error bound just proved to boxes with \(a>q\) gives \(u=O((F_\lambda+k)/\log R)=O(F_\lambda/\log R)\). The dimension of this core is at most \(D_\lambda\), by extending its tableaux after translating it to the upper left. Its hook formula therefore pays \(\sum\log_2(a-q)\) up to \(O(u)\). For charged boxes \(a\ge R\), replacing \(\log_2(a-q)\) by \(\log_2a\) costs \(o(1)\) per box, and adding \(L\) costs at most \(u\sqrt{\log_2R}=o(F_\lambda)\). This proves (124).

Two bounds for a weighted cycle factor

The positive network recursion is \(K_n=H(K_m\otimes K_m)H\), where \(H\) is the orthogonal average of the outer matching switches. For a positive \(D\) and \(p\ge2\), \[ \mathop{\mathrm{Tr}}(HDH)^p\le\mathop{\mathrm{Tr}}(HD^{p/2}H)^2. \tag{125}\] Indeed take an eigenbasis of \(HDH\) on the range of \(H\). Scalar Jensen gives \(\langle v,Dv\rangle^{p/2} \le\langle v,D^{p/2}v\rangle\) for each basis vector. Squaring and summing is bounded by the Hilbert–Schmidt square of the compression. This proof uses scalar convexity and does not require operator convexity of the power function.

Resolve the two halves into types \(\mu,\theta\). For the moment, let \(M_\mu\) and \(M_\theta\) be arbitrary positive matrices on these two types, and put \(t_\mu=\mathop{\mathrm{Tr}}M_\mu^2\) and \(t_\theta=\mathop{\mathrm{Tr}}M_\theta^2\). In the unrestricted recursion they will be \(K_m^{p/2}\) on the respective types; allowing arbitrary positive matrices will also cover the midpoint projections below. Write \(c(g)\) for the number of cycles of a permutation \(g\), including fixed points. Expansion of the matching projection gives the regular trace bound \[ \frac{\mathop{\mathrm{Tr}}(EHEH)}{(2m)!} \le4^{-m}\sum_z|e(z)|^2\,2^{c(\alpha^{-1}\zeta)}. \tag{126}\] Here \(E\) is the element of the half-preserving group algebra whose only nonzero Fourier block is \(M_\mu\otimes M_\theta\) on the selected pair of child types, and \(E=\sum_{z=(\alpha,\zeta)\in S_m\times S_m}e(z)z\). The trace in (126) is the regular trace of \(S_{2m}\). To verify it, expand each matching average as a sum over subsets of the \(m\) matched pairs. For a term to return to the half-preserving subgroup, its two switch subsets \(J,I\) must satisfy \(\alpha(J)=\zeta(J)=I\). The permissible \(J\) are unions of cycles of \(\alpha^{-1}\zeta\), so there are \(2^{c(\alpha^{-1}\zeta)}\). The second half-preserving coefficient exchanges the two maps on \(J\), up to inversion. This operation is a bijection on the paired terms; symmetrizing \(|e(z)e(z')|\le(|e(z)|^2+|e(z')|^2)/2\) proves the bound. Schur orthogonality gives \[(m!)^2\sum_z|e(z)|^2=D_\mu t_\mu D_\theta t_\theta.\] The cycle factor is therefore averaged under the product of the two normalized squared-coefficient laws. Since \((2m)!/4^m\le(m!)^2\), the normalized half-density is \[\phi_\mu(g)= \frac{D_\mu|\mathop{\mathrm{Tr}}(M_\mu V_\mu(g))|^2}{t_\mu}.\] It is a probability density relative to uniform measure on \(S_m\), by matrix-coefficient orthogonality; we only use it when \(t_\mu>0\). For independent \(\alpha,\zeta\) with these respective densities, define \(T_{\mu\theta}=\mathbb E2^{c(\alpha^{-1}\zeta)}\). The next lemma connects this regular-trace calculation to a fixed parent representation. It also identifies the quantities retained when we later stop a recursion according to its actual traces.

The first estimate is representation theoretic. Put \[G_\mu=\sum_{b=0}^m\ \sum_{\substack{\xi\vdash b\\\zeta\vdash m-b}} (c_{\xi\zeta}^\mu)^2.\] Here \(c_{\xi\zeta}^\mu\) is the Littlewood–Richardson multiplicity of \(V_\xi\otimes V_\zeta\) in the restriction of \(V_\mu\) to \(S_b\times S_{m-b}\). Then \[ \log_2T_{\mu\theta}\le \tfrac12(\log_2G_\mu+\log_2G_\theta). \tag{128}\] The function \(2^{c(g)}\) counts the subsets fixed by \(g\), so it is the character of the direct sum of all subset permutation modules. For an irreducible summand \(V_j\) in that sum, its contribution under the two coefficient-square laws is \(\operatorname{Tr}(\widehat\phi_\mu(j)^* \widehat\phi_\theta(j))\). These Fourier matrices are positive semidefinite, because a square of a coefficient of a positive matrix is positive definite, and are contractions because the densities integrate to one.

To bound their traces, let \(Q_j\) be the \(j\)-isotypic projection in \(V_\mu\otimes\overline{V_\mu}\). Fourier orthogonality gives \[\operatorname{Tr}\widehat\phi_\mu(j) =\frac{D_\mu}{t_\mu D_j} \operatorname{Tr}[(M_\mu\otimes\overline{M_\mu})Q_j].\] Cauchy–Schwarz bounds the last trace by the geometric mean of the traces with \(M_\mu^2\) on either tensor factor. Each partial trace of \(Q_j\) is scalar by Schur’s lemma, so this is at most the multiplicity of \(j\) in \(V_\mu\otimes\overline{V_\mu}\) after the displayed normalization. Summing over subset modules, Frobenius reciprocity identifies that sum of multiplicities with \(\sum_b\sum_{\xi,\zeta}(c_{\xi\zeta}^\mu)^2=G_\mu\). Thus \(T_{\mu\theta}\) is at most either \(G_\mu\) or \(G_\theta\), and hence at most their geometric mean. This proves (128).

Let \(u_s(\mu)\) count boxes outside the first \(s\) rows and columns, and put \(k_\mu=m-\mu_1\). With \(\eta=10^{-9}\), \(\gamma=1/100\) and \(s=\lfloor k_\mu^{1/2-\eta}\rfloor\), one has \[\begin{align*} \log_2G_\mu&\le u_s(\mu)+O(k_\mu^{1-\eta/2}), &&k_\mu\ge m^\gamma,\tag{129}\\ \log_2G_\mu&\le k_\mu+O(\log m+\sqrt{k_\mu}\log k_\mu), &&k_\mu<m^\gamma. \tag{130}\end{align*}\] For the first, Pieri’s rule embeds \(V_\mu\) in the induction of its core together with at most \(2s\) one-row or one-column strips. Restrict that induced module to two half factors by recording each constituent’s size on each side. For the core, multiplication of the restriction and induction dimension bounds gives \[(c_{\xi\zeta}^{\kappa})^2\le\binom{u_s}{|\xi|}\le2^{u_s}.\] The strips restrict with multiplicity one, and each subsequent strip addition also has multiplicity at most one by Pieri. It remains to count the intermediate diagrams. A subdiagram of \(\mu\) is specified by its first row and a partition of at most \(k_\mu\) boxes below that row; its logarithmic count is \(O(\log m+\sqrt{k_\mu}\log(k_\mu+2))\). Including the size splits, the logarithm of all intermediate choices is therefore \(O((s+1)(\log m+\sqrt{k_\mu}\log(k_\mu+2)))\). For \(k_\mu\ge m^\gamma\) and \(s=\lfloor k_\mu^{1/2-\eta}\rfloor\), this is \(O(k_\mu^{1-\eta/2})\), after absorbing logarithms. Squaring and summing multiplicities changes only the implicit constant and proves (129). For the second, remove only the first row, using the whole lower diagram as the core in the same argument. The trivial type costs only \(O(\log m)\).

The second cycle estimate depends on the actual trace. Put \(r_\mu=(\mathop{\mathrm{Tr}}M_\mu)^2/t_\mu\); then \(\phi_\mu\le D_\mu r_\mu\). The uniform cycle generating product, split at cycle count \(m^{9/10}\) and evaluated at \(x=m^{89/100}\), gives \[ \log_2T_{\mu\theta}\le O(1)+m^{9/10}+ \frac{F_\mu+\log_2r_\mu}{0.88\log_2m}. \tag{131}\] The same bound holds with \(\theta\); their average can also be used. Here is the tail optimization. For a uniform permutation \(g\), \[\mathbb E x^{c(g)}=\prod_{j=0}^{m-1}\frac{x+j}{j+1},\qquad \log_2\mathbb E x^{c(g)}=O(x\log m) \quad(1\le x\le m).\] Take \(x=m^{0.89}\), \(h=\lceil m^{0.9}\rceil\), and \(A_m=0.88\log_2m\). Since \(m^{0.89}\log m=o(h\log m)\), Markov’s inequality gives, for all sufficiently large \(m\), \[\Pr_{\rm unif}\{c(g)\ge j\}\le2^{-A_m j}\qquad(j\ge h).\] The law of \(\alpha^{-1}\zeta\) has density at most \(B=D_\mu r_\mu\): conditioning on \(\zeta\) gives a translate of the first density, and averaging preserves this bound. Its cycle tail is therefore at most \(\min(1,B2^{-A_mj})\) for \(j\ge h\). Put \(j_*=h+\lceil(\log_2B)/A_m\rceil\). The tail-sum identity and \(A_m>1\) give \[\mathbb E2^{c(\alpha^{-1}\zeta)} \le2^{j_*}+\sum_{j>j_*}2^j B2^{-A_mj} \le C2^{j_*}.\] Taking logarithms proves (131). The argument with the two halves interchanged proves its symmetric version.

A preliminary trace and the cutoff allocation

There is a fixed \(p_0\) such that, with \(\delta=10^{-5}\), \[ \mathop{\mathrm{Tr}}K_n^{p_0}|_{V_\lambda}\le2^{\delta F_\lambda}. \tag{132}\] We first specify the stopping contributions. At a nontrivial sparse node of size \(m\), let \(B\) be its positive sweep operator, or any cut operator satisfying \(0\preceq B\preceq T_mT_m^*\). The local sparse estimate and \(F_\mu=O(k_\mu\log_2m)\) imply \[ \log_2\bigl(D_\mu\mathop{\mathrm{Tr}}B(\mu)^p\bigr) +\tfrac12\log_2G_\mu \le 2F_\mu-2p b_1 k_\mu\log_2m +\tfrac12\log_2G_\mu\le0 \tag{133}\] for one sufficiently large fixed \(p\), uniformly over nonzero sparse nodes. Here (130) bounds the last term by \(O(k_\mu\log_2m)\); level one is annihilated. Coordinate reversal permits the same estimate for either positive orientation. For each fixed finite set of sizes, the finite-size norm gap likewise permits one exponent making the left side of (133) nonpositive on every nontrivial type. A trivial child instead has \(D_\mu=t_\mu=1\) and \(G_\mu=m+1\); we stop it and charge its \(O(\log m)\) half-cycle cost to its nontrivial parent.

Choose a large fixed lower size cutoff, and apply Lemma 33 at each remaining nonsparse node, using the same exponent \(p_0\) throughout. Choose \(p_0\) to satisfy (133) and the finite-size stopping inequalities at this cutoff. On each selected edge use (128). A stopped nontrivial child contributes its actual \(\log_2(D_\mu t_\mu)\) together with its half of this cycle bound; their sum is nonpositive. On every active frontier, Littlewood–Richardson compatibility now gives \[\sum_v k_v\le k,\qquad \sum_vF_v\le F_\lambda,\qquad \sum_vu_s(v)\le u_s(\lambda).\] For the last inequality, consider one Littlewood–Richardson tableau of \(\lambda/\mu\) with content \(\theta\). Entries in the first \(s\) rows are at most \(s\). For each value \(j>s\), column strictness permits at most one occurrence in each of the first \(s\) columns. Thus at least \((\theta_j-s)_+\) occurrences lie beyond both the first \(s\) rows and the first \(s\) columns. These skew core boxes are disjoint from the \(u_s(\mu)\) boxes of the old core, and \(\sum_{j>s}(\theta_j-s)_+=u_s(\theta)\). Therefore \(u_s(\mu)+u_s(\theta)\le u_s(\lambda)\) at one split; iteration proves the frontier inequality. At nodes of size \(m\), use the common cutoff \(s_* =\lfloor\max(m^\gamma,\rho m)^\beta\rfloor\), where \(\beta=1/2-3\eta\) and \(\rho=k/n\) is the root payload density, kept fixed throughout this unrolling. Here is the comparison with the varying cutoff in (129). Put \(a_0=\beta/(1/2-\eta)<1\). A nonsparse node with its own cutoff smaller than \(s_*\) can occur only when \(\rho m\ge m^\gamma\), and then it has \(k_v\le C(\rho m)^{a_0}\). There are at most \(n/m\) nodes of size \(m\), so the total level of these exceptional nonsparse nodes is at most \[C(n/m)(\rho m)^{a_0} =Ck(\rho m)^{a_0-1} \le Ck m^{-\gamma(1-a_0)}.\] Their core counts are at most their levels, so this is a summable error as the bottom size cutoff increases. The sparse and finite-size stopping contributions have already been removed by (133); trivial-child costs belong to the active-parent overhead. All remaining nodes charge at most half their \(u_{s_*}\). For a parent at level \(k_v\), compatible child levels \(r,s\) satisfy \(r+s\le k_v\). Consequently \(N_\lambda\le\sum_{r+s\le k_v}p(r)p(s)\), so the partition-number bound gives \(\log_2N_\lambda=O(\sqrt{k_v}+\log(k_v+2))\). Restriction overheads and the errors in (129) are \(O(k_v^{1-\eta/3})\) on nonsparse nodes, so at size \(m\) their sum is \(O(km^{-\gamma\eta/3})\). Summing over dyadic sizes makes their total \(o(k)\) as the bottom cutoff tends to infinity. These errors are independent of \(p_0\). A box of index \(a\) is charged at at most \(O(1)+L+\beta^{-1}\log_2a\) levels. By (124) the total is at most \((1/(2\beta)+o(1))F_\lambda<(1+\delta)F_\lambda\). More explicitly, unrolling (127) gives \[F_\lambda+\log_2\mathop{\mathrm{Tr}}K_n(\lambda)^{p_0} \le \left(\frac1{2\beta}+\varepsilon(M)\right)F_\lambda, \qquad \varepsilon(M)\longrightarrow0\] as the fixed lower cutoff \(M\) tends to infinity. The stopping terms are nonpositive, and the displayed error includes the type counts and trivial-child costs. Since \(1/(2\beta)<1+\delta/2\), choose \(M\) first so that the coefficient is at most \(1+\delta\), and then choose the single finite exponent \(p_0\) as above. Subtracting \(F_\lambda\) proves (132). We may take \(M\) still larger before fixing \(p_0\) when a smaller error margin is needed below.

We now turn the preliminary trace into the midpoint projection estimate. Split the ordered coordinates as evenly as possible, and write \[T_n=C D,\] where \(D\) applies the first group of coordinates and \(C\) the second. The two coordinate groups have \(\lfloor d/2\rfloor\) and \(\lceil d/2\rceil\) coordinates, where \(d=\log_2n\). Each segment is a product of independent sweeps on its parallel subcubes, of sizes \(2^{\lfloor d/2\rfloor}\) and \(2^{\lceil d/2\rceil}\), respectively. Let \(H_D,H_C\) be the corresponding direct product permutation subgroups. The argument applies equally with the two coordinate-group sizes interchanged; their middle log sizes differ from \(d/2\) by at most \(1/2\). A product type for either subgroup is a tuple of partitions, with product dimension and hence log dimension equal to the sum of the child log dimensions. On \(V_\lambda\), let \(P_{\rm lo}^D\) and \(P_{\rm lo}^C\) be the central isotypic projections for \(H_D\) and \(H_C\), respectively, onto product types whose log dimensions sum to at most \[ X=0.50003F_\lambda. \tag{134}\]

Closing the norm induction without a circular base

Write \(P_D=P_{\rm lo}^D\) and \(P_C=P_{\rm lo}^C\). With \(T_n=CD\), \[T_n=T_nP_D+P_CT_n(I-P_D)+(I-P_C)CD(I-P_D).\] Proposition 34 bounds the first two terms by \(2^{-c_1F_\lambda}\) each. The central projections commute with their own segments, \(P_DD=DP_D\) and \(P_CC=CP_C\). On a high product type, the child dimension-power estimates multiply, and its product log dimension exceeds \(X\). Thus, if all child estimates hold with exponent \(g\), the last term has norm at most \[\|(I-P_C)C\|\,\|D(I-P_D)\| \le2^{-2gX}=2^{-1.00006gF_\lambda}.\] This uses no commutation between \(P_C\) and \(P_D\). We need a size threshold independent of the final small exponent. A crude polynomial gap supplies it. For a unit vector \(v\), put \(\varepsilon=1-\|T_nv\|^2\). If \(v_i\) is the vector after \(i\) matching projections, orthogonality gives \(\sum_i\|v_i-v_{i-1}\|^2=\varepsilon\). Hence \(v\) is within \(\sqrt{d\varepsilon}\) of every matching-fixed space. Each edge transposition in that matching moves \(v\) by at most \(2\sqrt{d\varepsilon}\). Any transposition is a product of at most \(2d-1\) cube-edge transpositions along a cube path, and any permutation is a product of at most \(n-1\) arbitrary transpositions. Telescoping therefore bounds \(\|\pi v-v\|\) by \(Cnd\sqrt{d\varepsilon}\). The average of \(\pi v\) over \(S_n\) is zero on a nontrivial irreducible, so \(1\le Cnd\sqrt{d\varepsilon}\). Together with \(F_\lambda\le n\log_2n\), this supplies an exponent \(a n^{-C_0}\) in the bound \(\|T_n\|\le2^{-gF_\lambda}\), for absolute \(a,C_0>0\); dimension-one nontrivial types are annihilated.

Fix temporarily a desired exponent \(0<c\le c_1/2\). At a parent of size \(n\), induction and this independent gap permit a common child exponent \[g=\max\{c,\min(c_1/2,a n^{-C_0})\}.\] Thus \(g\le c_1/2\) and \(g\ge a'n^{-C_0}\) for an absolute \(a'>0\). Relative to \(2^{-gF_\lambda}\), the saving in the high–high term is \(1-2^{-.00006gF_\lambda}\). It is bounded below by an inverse polynomial in \(n\), whereas the two low terms have relative size at most \(2\cdot2^{-(c_1/2)F_\lambda}\). On active roots, \(F_\lambda\ge b n^{.01}\), so one absolute large-size threshold absorbs the low terms for every such \(c\). Below that threshold choose \(c>0\) small enough to fit every finite nontrivial norm gap, and also small enough for (123) on sparse roots, where \(F_\lambda=O(k\log n)\). This closes the induction without a circular choice of its base and proves Theorem 32.

For completeness, let \(\mu_q\) be the permutation law after \(q\) sweeps and define its squared relative \(L^2\) deviation by \(\chi^2=n!\sum_{g\in S_n}|\mu_q(g)-1/n!|^2\). The regular Fourier consequence is \[ \chi^2\le\sum_{\lambda\ne(n),\ T_n(\lambda)\ne0} D_\lambda^2\,2^{-2qcF_\lambda}=o(1) \tag{144}\] for a sufficiently large absolute \(q\). There are at most \(2^{O(\sqrt k\log(k+2))}\) types at level \(k\), \(F_\lambda\ge bk\), and \(F_\lambda\to\infty\) at each fixed positive \(k\). These facts justify the last limit and give the same bound from every starting deck by translation.