Compatibility entropy and the spectrum of a Thorp sweep

Proof. The sign average contains a fair transposition. For the second assertion, by Young’s rule, the permutation module induced from the trivial representation of (S_2)^{n/2} has only shapes dominating (2^{n/2}), hence at most n/2 rows.□

Proof. Equality on a unit vector would force equality at every orthogonal projection in the product. The vector would be fixed by all coordinate-pair transpositions. The edges of the cube form a connected graph, and its edge transpositions generate S_n, contradicting nontrivial irreducibility.□

Proof. At most 2^{tn/2} coin strings are available, so the law is supported on at most that many permutations. Comparing this support set with its uniform mass proves the first assertion. Distance at most 1/4 requires support mass at least 3/4, giving the exact integer lower bound. Stirling’s formula gives the final expression. In particular, for t\le d the support has size at most 2^{nd/2}=n^{n/2}.□

Proof. Schatten Hölder gives \|T^s\|_{\HS}\le\|T\|_{S^{2s}}^s, and multiplying the remaining r-s factors costs at most \|T\|_{\op}^{r-s}. Squaring proves the claim. No normality of T is used.□

Proof. Transpose if necessary so that the first row has length r=\max(\lambda_1,\lambda'_1). If r\le n/8, the hook formula gives D_\lambda\ge n!/(2r)^n, exponential in n. If n/8<r\le3n/4, retain the first row and \lfloor r/4\rfloor further boxes. Their tableaux extend to the whole diagram. A first row of length r and a tail of size j\le r have at least

tableaux: ballot interleavings of the first row with any fixed standard order of the tail respect all column inequalities. This is exponential in n in the present range. There are \exp(O(\sqrt n)) partitions, so these ranges contribute o(1) to the inverse-degree sum. If r>3n/4, write j=n-r. The same ballot bound is at least a fixed multiple of \binom nj. There are at most 2p(j) possible shapes up to transpose, and \binom nj\ge4^j for j<n/4. Since p(j)=\exp(O(\sqrt j)) and each fixed positive j gives a divergent binomial coefficient, dominated convergence proves the first assertion.

For the square-root estimate, put b=\lambda_2 and h=\lambda'_1, so b(h-1)\ge\ell. If h-1\ge\sqrt\ell, a hook with row and column length h has at least 2^{h-1} tableaux. Otherwise b>\sqrt\ell, and for \ell>0 this implies b\ge2. The two-row rectangle of width b has the Catalan number of tableaux, at least 2^{b-1}\ge2^{\sqrt\ell/2}. Subdiagram tableaux extend; the case \ell=0 is immediate. This proves the displayed bound. Finally p(j)\le e^{3\sqrt j} follows by evaluating the partition generating product at e^{-1/\sqrt j}. Summing 2e^{3\sqrt\ell}e^{-16(\log2)\sqrt\ell} proves the inverse-32 bound.□

Proof. Extend the polar partial isometries to unitaries. Removing these outside factors reduces (7) to positive matrices A=|A_2| and B=|A_1^*|. Put h=P/q. The case h=1 is equality. For h>1 use the analytic family F(z)=A^{hz}B^{hz} on 0\le\Re z\le1. A positive matrix power here is defined on each positive eigenvalue by its complex power and is zero on the kernel for every z. Thus on \Re z=0 the operator norm is at most one, while

The equality holds because the imaginary powers are unitary on the supports containing the range and domain of the middle product.

Schatten interpolation between these two boundaries gives \|F(\theta)\|_{S^{q/\theta}}\le\|A^hB^h\|_{S^q}^{\theta}. For completeness, this follows from scalar three-lines by testing against a dual matrix. If r=q/\theta and C=U\operatorname{diag}(c_i)V^* has \sum_i c_i^{r'}=1, use the analytic test V\operatorname{diag}(c_i^{r'(1-z/q)})U^*. Its boundary norms are S^1 and S^{q'}, respectively, both one; zero singular values give identically zero terms. At z=\theta it is C^*, proving the assertion by duality. Take \theta=1/h. Finally use P=2p, q=4 and cyclicity to obtain (8).

This is the form of the Araki–Lieb–Thirring comparison used below [1, 2]. In positive-matrix notation it also gives \Tr(B^{1/2}AB^{1/2})^{ra} \le\Tr(B^{r/2}A^rB^{r/2})^a for r,a\ge1.□

Proof. At u=2 this is Plancherel. At u=\infty, inversion and trace norm duality give

Interpolation gives the intermediate exponents. One may carry it out by the same three-lines test as above, using the direct sum of matrix spaces with trace \sum_\rho D_\rho\Tr and the uniform scalar measure on G. This is inverse Hausdorff–Young in the finite-group normalization of [9, Lemma 5.1(2)].□

Proof. For positive definite matrices apply three-lines to \bigwedge^j(C^{vz}A^{vz}). Its operator norm on the imaginary boundary is one. On \Re z=1 its outside imaginary powers are unitary, so its norm is \|\bigwedge^j(C^vA^v)\|_{\op}. Evaluation at z=1/v proves the claim, since the norm of an exterior power is the product of the leading singular values. Replacing A,C by A+\varepsilon I,C+\varepsilon I and letting \varepsilon\downarrow0 covers the semidefinite case.□

Proof. To see this, use the permutation representation on ordered distinct h-tuples. Every irrep in (11) occurs here and not on ordered (h-1)-tuples, by Young’s rule. Thus we may bound the sweep on functions in the tuple representation orthogonal to functions of any proper subset of the coordinates.

Take distinct input and output tuples x,y. The paths between corresponding positions in a sweep are determined (each dimension is used just once). A path at each stage uses one of the pair switches. Say two paths touch if they use the same switch at some stage. For I\subseteq [h] let

This is zero if the paths call for incompatible routes. On compatible paths it is 2^{e_I}, where e_I counts switches used by two of the paths in I: we save one bit at each such switch. In particular if one path touches none of the others in the full list, including or omitting that index has no effect on D_I.

The transition density relative to uniform on tuples is (n)_h D_{[h]}/n^h, where (n)_h=n(n-1)\cdots(n-h+1). For an operator bound on the indicated irreps, we can replace D_{[h]} here by

All terms changed act by zero on the irreps, being kernels depending on fewer tuple coordinates. And F=0 unless in the touching graph on [h] there are no isolated vertices.

We estimate the second moment of F over uniform distinct input and output tuples. Let E be the event that both tuples are distinct and their full touching graph has no isolated vertices. By Cauchy–Schwarz, it suffices, up to a factor exponential in h, to bound \mathbb E_{\rm iid}[D_I^2\mathbf1_E] for every I\subseteq[h]. Here the expectation first samples all input and output positions independently and uniformly. Passing from this law to uniform distinct tuples costs at most (n^h/(n)_h)^2\le C^h.

One factor D_I can be incorporated into the sampling law:

Under \mathbb E_{\mu_I}, sample a sweep and all input positions independently; for i\in I take the sweep’s output, and for i\notin I sample an independent uniform output. This identity uses the probability definition of D_I on all endpoint lists; its formula 2^{e_I} will be used only on E. Conditional on the sampled sweep, the individual paths are independent. A path indexed by I is uniform among the n realized deck paths, and at most two of these occupy a given switch at a given stage. For a path outside I, its independently sampled endpoints likewise make its switch uniform among the n/2 switches at each stage. In either case, its probability of touching a fixed path is at most 2l/n. Integrating the children of a specified forest after their parents therefore bounds its contact probability by (2l/n)^{\#\mathrm{edges}}.

The remaining task is to control the second density factor without paying for every possible encounter. There is a deterministic bound on the other factor D_I still left from the square. In any list of s distinct realized deck paths the number of their mutual switches is at most (s/2)\log_2 s. This is the butterfly contact lemma of [21, Lemma 3.2]; its endpoint-counted version is s\log_2s. Here each shared switch saves one coin, so we use the half-sized, shared-switch count. The following entropy argument also proves exactly the local form we need. To see the deterministic bound, let a walker start uniformly on one of the s selected paths. It follows that path except at a switch shared by two selected paths, where it chooses either continuation fairly. The walker remains uniform among the s current positions. If the paths share e switches, the expected number of fair choices is therefore 2e/s. Given the starting position, the final position determines the whole butterfly route. The chain rule for entropy consequently gives 2e/s\le\log_2 s, proving the claimed bound. Thus if the components of the full touching graph have sizes s_1,\ldots,s_c, D_I\le\prod_j s_j^{s_j/2}.

Let \Gamma be the event that the touching graph has no isolated vertices. The preceding Cauchy–Schwarz and change-of-law estimates give

where \mu_I is the sampling law obtained by weighting once by D_I. We now sum the forest witnesses while keeping the remaining density factor. For a realized graph on \Gamma, choose a rooted spanning tree in every component. If there are c components, their sizes s_1,\ldots,s_c satisfy s_j\ge2 and \sum_js_j=h. There are at most 2^h h^{h-c} rooted forests with c components: choose their roots, then give each nonroot a parent. For each such forest the probability of its edges is at most (2l/n)^{h-c}, and the density factor on the event that these are the actual components is at most \prod_js_j^{s_j/2}. After extracting this deterministic bound, discard the exact-component and distinctness restrictions only in the forest probability. Consequently

This bound is uniform in I. It also shows explicitly why the extra density factor does not consume the forest probability. For sufficiently large n, 2l\le n^{.01}; since h\le n^{.60}, the factor of a component of size s\ge8 is at most

For 2\le s\le7, use instead s^{s/2}\le n^{.01s}; then the same bound follows from -.39(s-1)+.01s\le-s/25. Thus every product in the preceding sum is at most n^{-h/25}, and

after enlarging the absolute size threshold. For h=1 the alternating kernel is identically zero. The tuple transition density has the additional factor (n)_h/n^h\le1, so its Hilbert–Schmidt norm on the new tuple constituents is at most n^{-h/100}. This proves (11), for example with b=1/100.□

Proof. First put D_R={\cal D}(Q_r\|U_R), for the joint row marginal. Call entries of the r array clumped if for their j,k the number N_{jk}=\#\{i:r_i(j)=k\} is greater than m^\epsilon, and let T(r) count clumped entries. Then

We verify the useful strength of this bound. Under U_R, \mathbb E e^{z T}\le 2 for z=c_0\log m, c_0>0 sufficiently small. To bound the contribution with some clumps, union-sum over sets of distinct cells (j,k) and lists of h_{jk}>m^\epsilon rows mapping accordingly, using the weight e^{z\sum h_{jk}}. Any compatible prescribed positions in row permutations cost probability at most (e/D)^{\sum h_{jk}}, by the falling-factorial bound. So after summing over rows, the factor per cell of size h is at most (C e^z/h)^h, negligible to arbitrary polynomial order even after summing over sizes and choosing a cell, for c_0<\epsilon. Summing products proves the exponential bound, which implies (13) by relative entropy.

Use the chain rule with r revealed first. Reveal column permutations in random order (each column k given an independent uniform priority in [0,1], earlier revealed first), and within each permutation in increasing order of i. Besides D_R the chain rule gives at least the sum of the column marginal entropies relative to uniform, that is the column relative entropy deficits {\cal D}(Q_{c_k}\|U), plus contributions from comparing successive conditional probabilities to those in Q_{c_k} alone. We next lower bound those contributions, averaged over the orders; explicitly we are using the decomposition

Here P gives probabilities for c_k(i) conditional just on c_k(i') for i'<i; P_{\rm past} conditions also on r and earlier columns in the random order. The expectation includes Q-data (and we can average freely over orders).

There are u_i=A-i+1 unused possible values inside permutation c_k. Call atoms of P heavy when P(w)>m^\epsilon/u_i, and write t for their mass. We have

In fact the relative entropy in each internal prediction (reference uniform on u_i) bounds the heavy mass times (\epsilon\log m-1), by grouping heavy and other atoms. These entropies sum to the column deficits.

Consider a step with t\le1/2, and let \mathcal L be the light class. Write P_{\rm light}=P(\,\cdot\mid\mathcal L) and let A_{\rm past} be the set of values not forbidden by the previously exposed columns. Given the row array, the unique j with r_i(j)=k determines these forbidden values: they are the output rows already obtained from original column j. Compatibility forces P_{\rm past} to be supported on A_{\rm past}. Splitting relative entropy between the light and heavy classes gives

with the product interpreted as zero when P_{\rm past}(\mathcal L)=0. After averaging over the data, the factor P_{\rm past}(\mathcal L) may be replaced by the indicator that the actual value lies in \mathcal L.

Now fix all data drawn under Q, with t\le1/2 and the actual value light, and average only over the column priorities. The internal predictor P, its light class, and P_{\rm light} are fixed during this averaging. Conditional on priority x for column k, each output row value from another column is forbidden with probability x. The exceptions have total P_{\rm light}-mass \alpha, where

The expected allowed mass is 1-x+x\alpha. Jensen’s inequality for -\log and then averaging over x give the lower bound \int_0^1-\log(1-x+x\alpha)\,dx. This argument compares with a light-class distribution to keep the loss on discarding heavy atoms proportional to their actual mass. In particular dropping t>1/2 cases and actual-heavy cases loses in expectation at most three times the expected heavy mass from the potential one nat per entry, using the marginal prediction law P. Dropping clumped entries loses at most \mathbb E T, since as i,k vary the corresponding i,j go once through the row array.

For all remaining entries the integral bound falls short of 1 by at most O(a\log(e/a)) where a=\min(1,2m^{2\epsilon}/u_i), by direct integration. Their total loss on this account is at most O(D m^{2\epsilon}\log^2 m)=O(n^{.54}). Consequently the sum of the entropy comparisons is at least

Together with D_R\ge\sum_i{\cal D}(Q_{r_i}\|U) this proves (12).□

Proof of Theorem 1.1. This is the finite-space entropy–Brascamp–Lieb duality of Carlen and Cordero-Erausquin [4, Theorem 2.1]. We give its specialization here. Suppose first that all weights are positive, and put

The finite Gibbs variational formula, with the event incorporated into the reference measure, is

Insert (12). Each row marginal then contributes at most

and the same inequality holds for each column marginal. Dropping the requirement that those marginals arise from a common compatible law only increases the supremum. Hence

Stirling’s bound gives \log(n!/(|R||C|))\le n+O(m\log n). It cancels the leading -n, and m\log n=O(n^{.54}). Exponentiating proves the claim for positive weights. Replace each zero weight by a positive number tending to zero to obtain the general case, since all spaces are finite. The error is independent of the weights.□

Proof. For a line group H_v, the coefficient identity and Parseval give

Since Z_v is positive and \mathcal L(g^{-1}) is unitary,

These prove the assertions about \rho_v. Write f(r)=\prod_i z_i(r_i) and g(c)=\prod_k z_k(c_k) for the coefficient densities of F,G. Their coefficients in the group algebra are f/|R| and g/|C|. The trace picks out words whose permutations cancel. More precisely,

The factor n! is the dimension of the full regular representation. Each subgroup coefficient contributes its density divided by its subgroup order.

Let \mathcal J=\{(r,c):rc\in CR\}. Since R\cap C=\{e\}, every (r,c)\in\mathcal J has a unique pair (r',c')\in R\times C satisfying rc\,r'c'=e. The map \Psi(r,c)=(r',c') is an involution of \mathcal J: the same equality also gives r'c'rc=e. Cauchy–Schwarz therefore gives

Finally, (r,c)\mapsto(r^{-1},c^{-1}) maps \mathcal J bijectively to the compatibility event \mathcal I=\{(r,c):cr\in RC\}. Self-adjointness gives f(r^{-1})=\overline{f(r)} and g(c^{-1})=\overline{g(c)}, so this inversion leaves the last weight unchanged. Thus

Dividing each squared line coefficient by its mass w_v gives (15).□

Proof. Write T_n=K_CK_R for the chronological row–column factorization, and set X=K_RK_R^*, Y=K_C^*K_C. The positive-power comparison (8), with p=t, gives

The line factors of X^{t/2} and Y^{t/2} have coefficient densities f_i and g_k. Lemma 3.3, in its unnormalized form (17), now bounds the right side by the weighted compatibility expectation with line weights |f_i|^2,|g_k|^2. Thus we may use (1) and need only bound norms with exponent \nu=2/\theta at each fiber. By Lemma 2.7,

(and likewise using Z_A for g_k). The child exponent is exactly t/(2-\theta). Thus t=p(2-\theta)=p(1+L/\log m) makes it p; taking a larger absolute L' also works. The norms are bounded by hypothesis, since the unpowered matrices are contractions. The product of bounds takes only \exp(O(m)), establishing (18).□

Proof of Theorem 1.2. The trace bound is not yet small. We now split it into small diagram levels, already controlled by the forest argument, and large-dimensional blocks, where regular multiplicity amplifies any increase in the moment exponent. To justify treating all remaining representations as large after (11), here are the dimension details. Those with first column of length greater than n/2 have zero sweep block: a single parallel dimension projects onto invariants of (S_2)^{n/2}, which by Young’s rule can occur only if \lambda dominates (2,\ldots,2), thus has at most n/2 rows. Among the remaining shapes, except \lambda=(n-h,\ldots) for 0\le h\le n^{.60}, we can use

for sufficiently large n. In fact if a first row or column has length at least n/10, it also has at least s=\lfloor n^{.59}\rfloor boxes off it. Transposing if needed, take the full long row and a subdiagram with s boxes below. Filling the first s boxes in the long row first, we may interleave its remaining boxes and a standard ordering below, giving (19) by tableau count and branching. If neither is long, all hook lengths are bounded by 2n/10, giving even exponential growth in n. On the other hand at levels h\le n^{.60} we may use D_\lambda\le n^{2h}, immediately by branching or the ordered tuple representation.

For large n let the baseline p in (18) be at least a sufficiently large absolute constant, so that by (11) the contribution to Z_n(p) from levels 1 through n^{.60} is o(1): for each partition at level h it is at most n^{4h-2pbh}, and there are at most 2^h such partitions. For the shapes in (19), (18) forces every squared singular value there to obey

for sufficiently large n, by multiplicity in the regular representation. Put \delta=1/\log m, and list the squared singular values in block \lambda as q_{\lambda,j}, 1\le j\le D_\lambda, including repetitions. Their total contribution over the large-dimensional blocks at exponent t(1+\delta) is bounded by

The exponent increase therefore makes both the sparse and the large-dimensional contributions small. We have therefore proved for sufficiently large n: if the two child bounds Z(p)\le 2 hold at parameter p at least the baseline constant, we get (2)’s bound at n at parameter

for an absolute L''. The sufficiently-large threshold need not depend on p.

For the remaining bounded sizes we can take a fixed baseline parameter large enough to get (2); indeed no nonconstant part has norm 1, since the sweep composes orthogonal projections and their common invariants are constants (cube swaps generate all permutations). Now the parameter increases over the dimension splitting recursion stay absolutely bounded: child log sizes are about half the parent log size, so the product of 1+L''/\log n over internal sizes above the threshold along any path is bounded. By monotonicity this proves (2).

Finally take a fixed integer M\ge p_*. After M sweeps the chi-squared distance to uniform is at most Z_n(M)-1: indeed it is the squared Hilbert-Schmidt norm of the regular convolution matrix minus constants after taking the sweeps (all starting rows have the same density norm), and Schatten Hölder bounds this on the nonconstant space by the indicated singular moment minus the constant contribution. Thus total variation is at most \tfrac12\sqrt{1/16}=1/8, giving the asserted order upper bound.□

Proof. The first r singular values in B_\rho are at least s_r(B_\rho), so their regular contribution is at least D_\rho r\,s_r(B_\rho)^p. This proves (21). It applies also when that singular value is zero.

The left side of (20) is precisely the sum of the pth powers of all nonconstant regular singular values. In particular none equals 1. Thus the distinguished constant singular value is the first value and is simple. For j\ge2,

This proves (22); at j=1 it is equality.

The power estimate uses the matrix product, rather than a spectral identification. Schatten Hölder with M factors gives

The last comparison uses s_j(B)\le1. If \mu_M is the convolution law after M steps and \Pi projects onto constants, every row of B^M-\Pi is a permutation of \mu_M-|G|^{-1}. Consequently

Cauchy–Schwarz bounds total variation by one half of this square root, uniformly over the starting group element.

For the converse the nonconstant regular moment is at most

For q>1 the last series with exponent q is at most 2^{-q}+2^{1-q}/(q-1), by integral comparison. It tends to zero as q\to\infty. Choosing q=cp' sufficiently large proves the uniform assertion.□

Proof. Equation (21) with r=1 bounds \|B_0\|_{\op}\le(\varepsilon/D_{\min})^{1/p}. Retain the extra powers in (23) and bound each by this supremum:

The preceding proof identifies this bound with an upper bound for four times total variation squared.□

Proof. Each child is at most 2/3 of its parent. Read upward from the last term above the base: the summands decrease by a factor at most (2/3)^\gamma, so their sum is bounded by a geometric series. The product assertions follow from \log(1+x)\le x and \log(1-x)\ge-2x for 0\le x\le1/2.□

Proof. Assume the child bounds at parameter p and set t=\alpha_dp. If s belongs to the second class, regular multiplicity and the rough trace estimate imply

Consequently its entire class contributes, at the increased parameter t(1+\delta_d), at most

The sums here list regular multiplicities. The first class contributes at most \varepsilon/2 by monotonicity and the first hypothesis. The constant singular value contributes exactly one. This proves the parent bound.

At the finitely many sizes d\le d_0, Lemma 2.2 allows one common parameter P_0\ge P for which the desired bound holds. Set p_d=P_0 in this base range, and above it define

The preceding parent estimate proves Z_{2^d}(p_d)\le1+\varepsilon by induction. Lemma 4.3 bounds the product of the exponent multipliers along every branch of rounded halvings. Thus p_*:=\sup_d p_d is finite; contraction and monotonicity give the asserted bound at this common parameter.□

Proof. Fix h, and expose intermediate columns according to independent continuous uniform priorities between 0 and 1. Inside each column expose edge colors in a fixed order. For a current edge let p be the color law conditional only on the previously exposed colors in that column (and h). If R colors remain in the column, mark as heavy colors those with

and write w for the light mass. The relative entropy of p from uniform on the R remaining colors is at least

Indeed the heavy terms contribute at least (1-w).04\log m, and by the log-sum inequality the rest contribute at least w\log w. The sum over edges of the expected relative entropies here, also averaged over h, is exactly J.

Call an edge bad if the multiplicity b of its (original column, intermediate column) pair is greater than m^{.04}. Averaging over h, the expected number of bad edges is O((F+1)/\log n). To see this, under uniform row permutations the number T of bad edges has \mathbb E\exp(c_0 T\log m)\le2 with some absolute c_0>0 for sufficiently large m. In detail, to count configurations with T=l>0, list the column pairs of high multiplicity and the rows producing those occurrences. For a\le l/m^{.04} such pairs, listing them costs at most (c^2)^a, and their sizes can be given in at most 2^l ways. Listing the sets of rows costs at most

by the binomial bound. The probability of the specified images is at most (e/c)^l, using (c)_x=c(c-1)\cdots(c-x+1)\ge(c/e)^x in every row. This proves the exponential estimate by summing (since r,c differ only by a bounded factor). Now use the standard entropy variational inequality with F.

By the entropy chain rule, each contribution to I in the exposure procedure is the information the earlier columns give about the current edge color beyond the local (within-column) history. We detail a lower bound on the average contribution for a nonbad edge. Fix the local history for this calculation. By also classifying the current color as light or heavy, a lower bound is w times that mutual information calculated under the condition of a light color (discard if w=0). This uses that the classification is a function of the color given the local history, and column order is independent. Under the light condition, the local color probabilities are the light part of p, normalized. Once earlier columns are seen, colors used there at this original column are forbidden. Thus relative entropy from the local light distribution is at least minus log of its mass still allowed, by the support bound for relative entropy.

Average this last estimate for a column priority t, with the other priorities random. Even given the entire valid coloring with current color light, any color at the original column that is used in a different intermediate column is forbidden with probability t, since the priorities are independent. The b colors used within the current column at the same original column have normalized local light mass at most b m^{.04}/(Rw). Jensen’s inequality for the minus log therefore bounds our information contribution below, on average, by

The bound indeed concerns information with the column order known throughout (and is averaged over it). Since \int_0^1-\log(1-t)\,dt=1, this is at least

for a nonbad edge. For example this follows directly by integrating, using a loss O(x\log(e/x)) inside the factor w when the minimum in braces is x; if the minimum is 1 the stated looser bound also suffices. Within any column the 1/R sum is O(\log(em)). The total losses of this latter form are O(m^{1.08}\log^2(em))=O(n^{.57}). The bounds on expected bad edges and summed expected heavy mass thus give (24).□

Proof. First sample h,u independently with product laws across their lines and densities, relative to uniform on H,K, bounded by q,s. We show that their compatibility probability is at most

If this probability is e^{-L}>0, condition on compatibility and use F,J,I from Lemma 5.1 for the conditioned law. The chain rule against the original product law, and then the density caps against uniform, give

Write the losses in (24) as E+\delta(F+J), where E=O(n^{.57}) and \delta=O(1/\log n). Substitution gives

Taking (1-\delta) times the first bound and \delta times the second proves (26). A zero probability needs no argument.

Apply Lemma 3.3 to the individual line projections forming A,D. Their squared coefficient masses equal their line regular ranks. The normalized squared densities have the same ranks as caps, so the products of masses and caps on the two sides are q,s. Consequently

The probability has precisely the independent product laws covered by (26). Since \log(n!/(|H||K|))=n+O(m\log m), the leading n cancels and (25) follows.□

Proof. By branching, V_\lambda occurs on ordered k-slot injections but not on (k-1)-slot injections. It therefore lies in the orthogonal complement of functions of proper subtuples. We will bound the sweep on that complement by cancellation of isolated paths.

For input and output k-tuples of distinct positions x,y, the paths in one pass are uniquely prescribed (change the input bits in sequence to the output bits). Make a graph on paths, connecting any two touching the same switch anywhere. For V\subset[1,k], let M_V be n^{|V|} times the probability that the paths indexed by V are realized. This is zero for an incompatible collection and otherwise 2^e, where e counts switches used by two members, since coins on different switches are independent. In projecting the pass to the part orthogonal to functions of proper subtuples of the k cards, we can replace the kernel entries n^{-k}M_{[1,k]} by

Terms depending on a proper subtuple do not contribute, and the irreducible in question is in this orthogonal part. If there is any isolated path the sum vanishes because adding that path does not change M_V.

Bound the squared Hilbert-Schmidt norm of this replacement. By Cauchy-Schwarz, up to factors \exp(O(k)), it suffices to bound, uniformly for V,

One factor M_V allows the following path sampling upper bound on this expression:

• •

  For V, sample a uniform input injection and run one pass, keeping those paths.

• •

  For the rest, sample independent uniform input-output slot pairs.

• •

  Take expected 2^e on the no-isolated event, with e counting shared switches among V.

This is an upper bound because the normalization factor from requiring a distinct input for V is at most 1, and restrictions on the independent pairs may be dropped.

Condition first on the complete switch settings for that pass, so V samples without replacement from n routes using those settings. For a prescribed rooted spanning forest of the touch graph with a components, the probability of the required touches is bounded by

Indeed expose outward from roots. For a child among V, given the parent path, at most 2d of the full routes can touch the path, with at least n-k routes still to choose from. For an independent input-output pair the marginal at each layer is uniform, giving the same bound by a union bound. Moreover, within a component of size l, shared switches among compatible pass routes (here the V routes) number at most l\log_2(l)/2. This deterministic bound follows by splitting after the first layer into output-bit halves and inducting over remaining layers: for child group sizes l_1,l_2 of a collection of routes the first layer contributes at most \min(l_1,l_2), at most half the binary entropy gain (l_1+l_2)\log_2(l_1+l_2)-\sum_i l_i\log_2 l_i, by concavity.

Thus, taking a union bound with spanning forest witnesses for the actual components, all of sizes l\ge2, the weight 2^e costs a factor at most \prod_l l^{l/2} (product over components). Forests can be counted by selecting roots and specifying a parent for each nonroot, at most 2^k k^{k-a} choices with a given a. These bounds give at most n^{-.02 k}, even including any of the \exp(O(k)) factors above, for sufficiently large n. To make the exponent check explicit, before those exponential factors the cost for a given number of components, allowing the worst sizes, is bounded using factors per component

For l\ge10, the power saving from (n/k)^{l-1} after paying l^{l/2} is at least n^{(.39\cdot .9-.305)l} since k\le n^{.61}. For smaller sizes l^{l/2} costs only exponential constants. Polylog factors per vertex and summing over a do not affect the stated looser bound n^{-.02 k}. Taking square roots gives (27).□

Proof of Theorem 5.4. For the sweep recursion take n=2^d, r=2^{\lceil d/2\rceil} and c=2^{\lfloor d/2\rfloor}. Fix p_0'\ge10000 and suppose the child sweeps satisfy \operatorname{Tr}|T_r|^{p_0'},\operatorname{Tr}|T_c|^{p_0'}\le1+1/8. We first obtain a rough parent bound, uniformly in p_0'. Write X=K_C for the column sweep and Y=K_R for the row sweep, so the chronological convention gives T_n=XY. We will show

for a sufficiently large absolute C_1.

Lemma 2.6 gives

We explain the summation bounding the right hand side to keep (29) uniform in p. Decompose each local positive factor (for a single row or column) by bins of singular values of the local pass, grouping singular values whose p_0'-powers lie in (e^{-j-1},e^{-j}], integer j\ge0; zero parts can be omitted. Expand into products by choosing one bin per row or column. This works within the group algebras by spectral calculus. In the local regular representation the projection rank for such a bin is at most 2 e^{j+1}, by the child moment bound. For any term in the expansion of |X|^{p/4}|Y^*|^{p/4}, let x be the sum of all its j’s. Its fourth norm power is bounded, by (25) for the two support projections and the operator norm bounds on the factors, by

Taking C_1>C+1, fourth roots can be summed by the triangle inequality at additional cost at most (O(\log n))^{O(m)}, by geometric series. This proves (29).

The projection calculation has supplied only the rough bound (29). To reduce it to a fixed small remainder, we separate the sparse levels just bounded from representations whose regular multiplicity is exponentially large.

Partitions neither having first row of length at least n-n^{.61}, nor first column that long, have dimension at least

for large n. Here is one direct check. If the longest row and column are shorter than 2n^{.61}, the hook formula suffices immediately, all hooks being at most 4n^{.61}. Otherwise (transpose if necessary) use a subdiagram with first row of length about 2n^{.61} and about n^{.61} boxes below (round down, discarding excess). By branching it suffices to lower bound dimension there. After filling the initial portion of the first row of length equal to the number of lower boxes, the remaining first row entries and lower boxes can be interleaved freely in a standard tableau (with any one standard ordering of lower boxes), giving the claimed bound.

The first-row levels 1\le k\le n^{.61} have at most 2^k shapes at each k, each of dimension at most n^k. Therefore (27) bounds their regular contribution at any exponent u\ge10000 by

The shapes with first column at least n-n^{.61} are annihilated by Lemma 2.1, since this height exceeds n/2 for large n. Together these form the first class in Lemma 4.4; its contribution is at most 1/16 above an absolute threshold, uniformly in u.

For the remaining class take H_n=n^{.60} from the dimension bound, E_n=C_2n^{.58} from (29), and \delta_d=1/\log n. Then

The common lemma applies with singular convention \nu=1, \varepsilon=1/8, P=10000, and \alpha_d=1+C_1/\log n. The combined multiplier is 1+O(1/d). It supplies one finite p_* and proves (28), including the finite initial sizes. The invariant in (28) has singular exponent p_* and remainder 1/8. Its conversion to forward sweep powers is therefore the case 2b\ge p_* of Proposition 4.1.□

Proof. To see what the condition means, write the row permutations as a_i, column permutations as b_j, and at each intermediate cell (i,j) put

Then the condition is precisely that the n pairs (X_{ij},Y_{ij}) are all distinct. In fact in a column-first factorization, all cards from any one original column must have different destination rows, and this is also sufficient, since then one can first put all cards in the correct row by column permutations, before going to their destinations by row permutations.

Fix the array X. For each j,x let M_{jx}=|\{i:X_{ij}=x\}|, and let

With only column randomness now, let p_{\rm ok} be the probability of the condition. We claim

Assume the probability is positive, and let \nu be the conditional law of the column permutations given success. Denote column laws before conditioning by \mu_j, and the marginals of \nu by \nu_j. With relative entropy denoted by D_{\rm KL}, put

We have

Estimate I by revealing inverse permutations i_j(y)=b_j^{-1}(y) in the order of colors y=1,\ldots,q (destination row is the color), and within each color in uniformly random order of columns, independent of the configuration. For each color we can order by independent uniform priorities in [0,1], low priority number revealed first. In the chain rule for I, consider the divergence contribution when i_j(y) is revealed. Under the reference product of the marginals, the prediction law u_i on possible i’s for i_j(y) is determined by the previously revealed colors in that column only. Let

Under the true conditional reveal law from \nu, the x value this color gets from column j cannot have already been used by this color in another column. So the KL contribution (conditional divergence) is at least minus the log of the total v-mass of x’s not yet used by the color.

We average this last bound. Fix a full sample from \nu, and for column j in that color fix its priority t; the vector v does not depend on the other priorities. Every x except the actual value x_* = X_{i_j(y),j} of the sample at this reveal is used by the color in another column, hence has probability t of being used earlier. By Jensen the expected lower bound on divergence from the allowed mass is at least

Integrating over t, this is

using continuous limit values. Here 0\le h(z)\le 1, and h(z)\le C z\log(e/z) on [0,1].

For the whole sum of errors h(v_{x_*}), the terms with M_{j x_*}>m^{0.05} cost at most W since all cells in each column are revealed. To bound the other errors, for column j and color y condition just on the previous colors in that column. Then under sampling from \nu the conditional law of x_* is v. Write R=q-y+1 for the number of remaining rows. For M_{jx}\le m^{0.05}:

• •

  Those x with v_x\le m^{0.1}/R have h(v_x)\le C(\log m)m^{0.1}/R, using also R\le 2m.

• •

  The total v-probability of the others with M_{jx}\le m^{0.05} is at most

where U_R is uniform among the remaining i’s in this column. Indeed under U_R, the induced probability of any such x is at most m^{0.05}/R; compare this induced law with v, writing the divergence as a sum of nonnegative terms a\log(a/b)-a+b, and use the data processing inequality. On the x’s in question we have probability ratio at least m^{0.05}.

Sum the expected errors. For the first bullet the summed bound is at most C m^{1.1}(\log m)^2\le n^{0.57} for sufficiently large m. For the second bullet we can use h\le1; the divergences in the bound sum (in expectation) to the left side of the second inequality in (32), by the chain rule for the column marginals. We conclude

Combining with (32) proves (31), since m is sufficiently large.

The inverse-color exposure has reduced the loss to repeated original column labels. We now average over the row permutations by bounding the exponential cost of W. First under uniform row permutations,

for some absolute c>0 and sufficiently large m. Here are details of the count. Groups of entries contributing to W are specified by a pair j,x, a size l>m^{0.05}, and l chosen rows where X_{ij}=x. For any collection with distinct indexing pairs j,x, fulfilling its requirements has probability at most (e/m)^{\sum l} (or zero if requirements conflict). In fact if b entries are prescribed in a row their probability is at most 1/(m)_b\le(e/m)^b, with falling factorial notation. Sum over collections with the exponential weight for their total size; this bounds the moment because we can take the collection of all actual contributing groups, and include the empty collection. We obtain the upper bound

where the sum uses integral l. By \binom ql\le(2em/l)^l, say c=0.01 suffices for (33). Changing the row laws to the ones in (30), the joint density of rows is at most \exp(L_R). Thus by Hölder, putting B=c\log m>1,

Averaging (31) in its exponential form and increasing constants gives (30).□

Proof. Regard positions as cells in the grid above, with column index coming from the first group of bits. Write H for the subgroup permuting positions independently within rows, J that within columns. The full sweep is a product of independent sweeps within rows followed by independent sweeps within columns. Let K_H,K_J denote the respective group algebra operators, lifted to the full regular representation, so that T_n=K_JK_H, with the row sweeps acting first. Products over individual lines in H or J correspond within that subgroup’s group algebra to tensor products. Use the positive semidefinite operators

Each local factor has the same positive-square moments as the corresponding child sweep. With these orientations, Lemma 2.6 gives

For the operator of a row in D_H divide positive eigenvalues \alpha into buckets indexed by nonnegative integers \ell, according to

Use its spectral projections onto the buckets, obtained as elements of the row group algebra (e.g. by polynomial calculus in the row regular representation). Do likewise for each column in D_J. For any choice of one nonempty bucket per row and per column, denote the ranks of the projections within their individual regular representations by r_z, where z ranges over lines (rows and columns). We have

by the trace moment hypothesis in the respective smaller cubes. Denote the combined row projection in the big regular representation by E, and the combined column projection by F; projections of individual lines within rows (and likewise within columns) combine by product in the subgroup. All projections and spectral restrictions can be lifted from the subgroup algebras as used here, since restriction of the regular representation to a subgroup acts by copies of its regular representation.

The spectral buckets preserve the child trace budget as a bound on regular rank. The next calculation converts the probability estimate into the overlap needed to sum those buckets:

with an absolute C_1. Apply Lemma 3.3 to these line projections. Their squared coefficient masses and the caps of their normalized squared densities are both r_z. Hence

where \rho is an independent product of line densities bounded by r_z. The lemma’s inversion step matches the chronological convention of Proposition 6.1. Applying that proposition with L_R+L_C=\sum_z\log r_z, and using

proves (37).

Expand the product in (35) according to the bucket assignments (zero eigenvalues contribute nothing). For one assignment, the term D_H^{p/4} E F D_J^{p/4} in the product has Schatten 4-norm at most

This follows by the ideal property of that norm with the outside operators restricted by the projections (using their operator norms). Use (36),(37) and the triangle inequality. Choose C_0>C_1+1. For an absolute C', we get

Since q+m=O(\sqrt n), (35) gives (34) for sufficiently large n, uniformly in s.□

Proof. Use the permutation action on ordered injective k-tuples of positions. The level k irreducibles occur there but are orthogonal to functions missing any of the coordinates, since such functions are in tuple modules for k-1. Indeed by the branching rule (or Young’s rule) the tuple module for b coordinates contains the irreducibles whose first rows have length at least n-b; it is induced from a trivial representation on n-b positions. We bound the sweep kernel on the part in question in the tuple module.

Consider an entry for input positions x and output positions y (ordered tuples). Orientation of the kernel, or taking its transpose, will not matter for the estimates. Paths of these cards through the sweep, if they realize the entry, are uniquely specified by the endpoints, since at stage r bits 1,\ldots,r have been set to their end values and the other bits have the start values. For two cards u,v in the tuple let

• •

  b_{uv} be the last bit where their starts differ;

• •

  a_{uv} be the first bit where their ends differ.

The entry probability is

In fact a>b gives impossible paths (collision), a=b means they share the switch at that bit and use distinct exits, and in the other case they do not meet at a switch. If no collision occurs, at a switch used by both cards of some pair the probability factor is 1/2 rather than the product 1/4; other used switches with one card just give the factor 1/2. This also explains (39) for any smaller tuple, using the corresponding number of cards instead of k in the prefactor.

On projecting onto the sum of the level k irreducibles we can replace Q_{[k]} by

Indeed the added matrices have entries that omit at least one tuple coordinate and vanish between the indicated projected parts. Consider the graph on tuple labels whose edges indicate that the paths specified by x,y touch a common switch, whether or not they could occur jointly. If this graph has an isolated vertex, \widetilde Q=0, by cancellation. The square of the Hilbert-Schmidt norm of the sweep on the projected part is therefore at most

Here are probabilistic bounds for (40). For fixed T, change measure using one factor Q_T. Up to a total mass factor at most 1, and dropping distinctness constraints on the additional paths for upper bounds, the law now can be sampled as follows:

• •

  Realize an independent full random sweep on all positions. Pick |T| distinct start positions uniformly and use their start/end paths for T.

• •

  For the other labels, use independent paths with starts and ends all uniform independent positions.

This follows from (39): on distinct tuples, n^{-2k}Q_T(x,y) gives exactly this weight with the factor (n)_{|T|}/n^{|T|}, (n)_a denoting the falling factorial. Only the positions within T are needed to evaluate the remaining factor Q_T, which in this construction equals 2 to the power the number of meetings at switches among the paths in T.

Condition on the full sweep realization used in this sampling. We need two bounds.

Meeting count. The number of meetings among any set of b\ge1 realized full-sweep paths is at most b\log_2(b)/2. To see this split paths by last input bit. All meetings before the last stage respect this split, and the two parts have sweeps on smaller cubes up to then. Meetings at the last stage contribute a matching between the two parts. Induction gives the bound, since for part sizes b',b-b',

(with zero summands interpreted by continuity); this follows also by concavity of binary entropy.

Forest probability. For any specified forest on the k labels, the probability all its edges indicate common switches is at most

Indeed sample its paths along the forest in parent-before-child order. If a child is one of the additional independent paths, for each stage its switch (out of n/2) is uniform, from the uniform endpoints. If it belongs to T, we sample among at least n-k remaining full-sweep paths, of which at most two at each stage use the switch in question on its parent’s path. The estimate follows by testing the edges as the child paths are sampled, since k\le n^{0.64}.

For the event with no isolates, take spanning trees in each component of the common-switch graph. For component sizes b_1,\ldots,b_j\ge2, the first bound above shows that the remaining weight Q_T is at most \prod b_i^{b_i/2}, since paths from T in different components cannot meet. For an upper bound on its expectation on the event, sum over spanning forests using this weight for forest component sizes and using the probability bound from the second estimate (we can thereby count outcomes more than once). Forests with j components number at most 2^k k^{k-j}, by choosing roots and parents. Also b^{b/2}\le C^b k^{(b-1)/2} for b\le k, since b^{(b-1)/2}\le k^{(b-1)/2} and \sqrt b\le C^b. Thus (40) is bounded by

where the constants absorb the subset counts. If there is no such j, (40) is zero. Otherwise d=\log_2 n, k^{3/2}\le n^{0.96}, and k-j\ge k/2; (41) is at most n^{-c_2 k} with some absolute c_2>0 for sufficiently large n. Since the tuple action applies the group algebra operator within the irreducibles (taking adjoints if using the other kernel orientation), we have proved (38).□

Proof. Here is one quick verification. If both row and column lengths (longest in the diagram) are smaller than n/10, every hook is bounded by n/5, giving the result by the hook-length formula. Otherwise take a direction with length at least n/10, transposing if necessary (dimension unchanged). Outside this long row there are at least \lfloor n^{0.64}\rfloor boxes by hypothesis (if transposed, by original height at most n/2). Take a subdiagram with this row and just b=\lfloor n^{0.64}\rfloor boxes below it, shrinking from corners. Its standard tableaux already give the required dimension lower bound, since they extend to the full diagram. In fact one may fill the first b places of the row first, then interleave a standard order on the lower b boxes with the rest of the first row arbitrarily. For large n this gives at least 2^{\Omega(b)} ways.□

Proof of Theorem 6.5. Choose a fixed P\ge2 with Pc_2\ge4, where c_2 is the constant in (38). At first-row level 1\le k\le n^{.64} there are at most 2^k shapes, each of dimension at most n^k. Thus for every u\ge P, their contribution to Z_n(u) is at most

Lemma 6.4 annihilates shapes of height more than n/2 and gives dimension at least \exp(n^{.62}) for all remaining shapes outside this sparse range.

Apply Lemma 4.4 with positive-square convention \nu=2 and \varepsilon=1/8. The sparse and annihilated shapes form its first class and contribute at most 1/16 for large n, uniformly above P. Proposition 6.2 supplies the rough bound from child moments at most 1+1/8<2, with

The required attenuation follows from

All size thresholds are independent of the inherited exponent, and \alpha_d(1+\delta_d)=1+O(1/d). The common lemma therefore gives a finite s_* such that Z_n(s_*)\le1+1/8 for all dyadic n.

This is a positive-square moment, with matching singular exponent 2s_*. Proposition 4.1 gives chi-square divergence at most 1/8 after every integer number l\ge s_* of forward sweeps.□

Proof. To prove this, let q be any probability law on compatible arrays, with the entropy H below computed in this law. Define the deficits

In particular D_A is for the full A array (so dominates the sum of marginal deficits in the rows). Let

The column marginal entropies here are unconditional. Thus I includes both the conditional correlation of the columns given A and the sum of their separate mutual informations with A, as in the comparison after Lemma 5.1. We claim

Reveal A and go through the columns j of B in order of iid priorities x_j uniform on [0,1] (from small to large), these priorities independent of A,B. Within each column use row order i=1,\dots,n. At cell i,j, use the marginal conditional probabilities p_b for the column B_j itself, given its prefix, as comparison. Then I is the sum over cells of the expected KL divergences of the true conditional (including A, priorities and earlier revealed B) against p. This follows from the conditional entropy chain rule in this order, since log probabilities from the p’s are just marginal-column log probabilities in total.

Use the following tilt of p. Say an atom b here is light if p_b\le m^{-3/10}. Write a=A_{ij} and let the multiplicity v be the number of times a occurs in the j-th column of A. Write y=1-x_j. If v>m^{1/10} or y<m^{-1/10}, skip the tilt, using factors t_b=1. Otherwise let t_b=1 on the non-light atoms, and on the light atoms set

These factors use only data known at this point and the normalizer Z=\sum_b p_b t_b is positive on histories of positive conditional probability (with comparisons understood for almost every priority choice), by compatibility. Thus the divergence contribution is bounded below in expectation by the expected

We can bound the normalizer cost by holding the full compatible arrays and x_j fixed and taking expectation in other priorities. In particular p has not depended on those priorities, because within-column revelation is in fixed order. Except for the v symbols paired with a in column j, any b has its pair with a in a different column, so the pair is available (not in an earlier column) with probability y. Consequently in non-skipped cases

Log-normalizer cost in expectation is then at most m^{-1/10}. On the other hand if multiplicity is not too high and the actual atom is light, we earn in expectation over priorities \int_{m^{-1/10}}^1 \log(1/y)\,dy =1-O(m^{-1/10}\log m). This use of column priorities lets the potential loss from skipping non-light atoms be counted without a large logarithmic penalty per lost cell.

The tilt has supplied almost one nat at each retained light cell, while its expected normalizing cost is small. Two exclusions remain: a heavy actual symbol, and a symbol occurring too often in its column of A. We pay for these using, respectively, D_B and the full-array deficit D_A.

• •

  Non-light actual atoms have expected count

for an absolute c>0. Indeed, we may ignore the last \lceil m^{4/5}\rceil entries in each column, counting those as losses. At any remaining cell, the non-light atoms are at most fraction O(m^{-1/2}) of the alphabet remaining in a uniform permutation. If their conditional p-mass h is at least m^{-1/4}, KL divergence versus that uniform choice is \Omega(h\log m), by divergence on the related binary event (h\log(h/p_{\mathrm{unif}}(\mathrm{event}))-h suffices for a lower bound). Else the mass is already small. The expected divergences of p versus the uniform remaining choices sum to D_B, proving (44).

• •

  For A, let J count cells at which the multiplicity in the column of the cell’s symbol exceeds m^{1/10}. We have

To see it, under independent uniform rows, for integer z\ge z_0=\lceil N m^{-1/50}\rceil,

for large m. In fact, to witness the event, in each of the m columns choose the list of symbols having high multiplicity (size at most 2m^{9/10}) and prescribe z cells to take symbols from the lists of their columns. The log number of choices of lists is O(Nm^{-1/10}\log m), and cells have log cost at most z\log(eN/z)\le z(0.02\log m+1). For a row with u prescribed cells the uniform success probability is bounded by (2m^{9/10})^u/(m)_u\le (2e m^{-1/10})^u, where subscript denotes falling factorial. (We use (m)_u\ge (m/e)^u, following e.g. from the factorial bound and prefix geometric means.) These estimates give the probability bound. Applying exponential-moment comparison by relative entropy with parameter 0.02\log m now gives (45): log of the uniform exponential moment is at most 0.02 z_0\log m+O(1), whereas D_A bounds parameter times expected J under q minus this log.

This proves (43), adjusting constants and using, say, a sufficiently small \varepsilon\in(0,1/50). The full KL divergence of q relative to U is D_A+D_B+I, so (43) implies (42) by entropy variational comparison: the divergence pays N-C_1 N m^{-\varepsilon} and still pays \alpha times the sum of the row and column marginal deficits, against which expected log weights are bounded using \alpha\log\mathbf E L_i^{1/\alpha}, \alpha\log\mathbf E M_j^{1/\alpha}. More explicitly, for a weight L_i, \mathbf E_q\log L_i minus \alpha times marginal deficit is at most the former of these log expressions, and likewise for M_j; then take the supremum over q for the left side log of (42). These variational facts follow as usual by nonnegativity of divergence from a tilted law; weights with zeros are allowed by limits or restriction. This completes the grid estimate.□

Proof. Lemma 2.6, with \bar r=2p\ge2, gives

Within their respective subgroups express X^p,Y^p by densities F,G_1 on the uniform probability measures (a density here is just a coefficient function, not required to be nonnegative). They are products over rows, respectively columns, of the individual densities for the smaller problems: F(l) uses a factor f(l_i) for each of the row permutations l_i of l\in\mathcal L, and G_1(r) uses a factor f_1(r_j) for each column permutation of r\in\mathcal R. Here f is for (T_mT_m^*)^p, and f_1 for (T_n^*T_n)^p. Both orientations have the child trace moments appearing in the hypothesis. This follows by tensor products and the fact that restriction of the regular action to a subgroup gives copies of its regular action, so these powers in a subgroup convolution algebra simply embed in the full group even when using real positive powers.

Apply Lemma 2.7 to each individual density with a=2/\alpha and a'=2/(2-\alpha). For the row density, the regular Fourier moment on its right is \mathcal Z_m(pa'), with

The column calculation uses \mathcal Z_n(pa') and pa'\ge u_n. Since the sweep operators are contractions, we get

Use Lemma 3.3, in its unnormalized form (17), on the positive line factors of X^p,Y^p. It gives

where l,r are independent subgroup uniforms. In the grid between the row move l and the column move r, the original-column labels are A_{ij}=l_i^{-1}(j) and the destination-row labels are B_{ij}=r_j(i). The event in (49) is exactly that all pairs (A_{ij},B_{ij}) are distinct. The row weights expressed in these arrays are |f(A_i^{-1})|^2, whose uniform norms equal those of |f|^2; the column weights are |f_1(B_j)|^2. Thus the weighted estimate (42) and (48) give

Also \log[ |S_N|/(|\mathcal L||\mathcal R|)]\le N+O(\log N) by applying the upper bound \log(N!)\le N\log N-N+O(\log N) to the numerator and the lower bounds \log(m!)\ge m\log m-m, \log(n!)\ge n\log n-n to the denominator. This one-sided bound is all the recursion needs. This proves (46), taking a sufficiently small fixed positive \eta (e.g. less than \varepsilon/3 and 1/4), for all sufficiently large d.□

Proof. To prove this, let \mathcal X be ordered k-tuples of distinct positions, measure \nu uniform on \mathcal X. Functions on \mathcal X are acted on by position permutations. The shape \lambda occurs here and does not occur in functions of any proper subset of the coordinates. Indeed occurrence on k-tuples is having invariants under S_{N-k}, by the action on tuples and its stabilizer, and the branching rule says this holds for shapes with first row at least N-k. Smaller coordinate subsets would require a larger first row.

For S\subseteq [k], put s=|S|, and for x,y\in\mathcal X let

using the pass permutation. The full R_{[k]} as an integral kernel against \nu represents T_N^* on tuple functions (the forward transition kernel is the adjoint under our action convention), up to the factor N^k/(N)_k. Also, in bilinear forms on a copy of \lambda, the proper subset terms give zero since they only involve those subsets of coordinates. Thus we can bound the desired norm by giving an operator norm bound on

A path of a card from one address to another in the d-layer pass is unique: at each coordinate it must go to the bit given by its destination address. It occurs with probability 1/N; it is prescribed by individual switch choices. Make a graph on [k] using x,y, putting an edge whenever the two associated paths use the same switch at some layer (in the same or different directions, including use of the same switch input). If there is an isolated vertex, Z_*=0. In fact such a path then imposes switch choices independent of those for any other subset of paths, which gives cancellation in pairs due to the scaling by N. Writing \Gamma for the event the graph has no isolated vertex, define

an upper bound on the absolute row integral. We have W(x)\le e^{Ck}, since the row integral of each R_S is N^s/(N)_s\le e^s. Likewise e^{Ck} bounds columns using the inverse pass. We will obtain much smaller bounds by controlling typical rows and showing their exceptions cannot concentrate in any column.

First, for some \gamma=\gamma(\delta)>0,

For k=1 the no-isolated-vertex event is impossible, so take k\ge 2. In bounding each average over x,y, we can take all x_i,y_i iid addresses and relax distinctness at cost at most e^{2k}, using the same R_S definition also on repeats. Weighting that iid law by R_S gives a simple sampling rule: sample a full pass network, take all x_i iid, use y_i=g(x_i) on S, and sample the other y_i iid. Conditional on this network the resulting single-card paths are independent. At each layer the switch used by each such path is uniform among N/2 switches: on S this is by uniform start through the fixed network, and outside S by iid start and finish (the address along the path uses respective bits of these). Therefore for any forest on the cards with u edges, the probability its edges are all path interactions is at most (2d/N)^u: for a leaf relative to its parent path this bound per edge follows by union over layers, and leaves can be peeled off using independence conditional on network. If \Gamma holds, there is a forest with u between k/2 and k-1 edges. At each such size there are at most (C k)^u to try, by choosing edges. Hence we have upper bound

for (51), proving the claim for the indicated range of k.

The mean estimate alone does not control a matrix norm: a small collection of input rows might carry a large operator. The next domination estimate rules this out in each fixed output column.

Next, for any set \mathcal B of x’s depending only on the unordered set of their entries, we have, for every fixed y\in\mathcal X,

To see it we can again use iid x at cost at most e^k, asking also for distinctness along with \mathcal B. Weighting by R_S amounts here to setting x_S=g^{-1}(y_S) and sampling remaining x_i iid. Under this inverse network, the set occupied by the s paths satisfies, for each set of sites T at any stage, probability of containing T at most product over T of the current site marginals. Indeed this property holds initially for the deterministic set at y_S, and remains true through each fair random transposition, which suffices as these give the layers. For T using one of the switched sites, average the previous bounds with that site exchanged, and for using both, use that product of the two site marginals is bounded by product after averaging the two; other marginals have not changed. At the end the site marginals are s/N by the uniform single-position transition. Thus probability for the set of s sites to equal any particular s-set is at most (s/N)^s, interpreted as 1 for s=0. For all of x to have as entries a given k-set, distinctly, in this law, probability is thus at most

The probability for that set under \nu is k!/(N)_k, giving (52) as desired.

Now W(x) is unordered-set measurable by simultaneous reindexing of x,y, so the rows with W>N^{-\gamma k/2} make a bad set of the kind in (52), having \nu-probability at most N^{-\gamma k/2}. For Z_* restricted to good rows, its absolute row and column integrals are at most N^{-\gamma k/2}, e^{Ck}, respectively; on bad rows, bounds e^{Ck},e^{C'k} N^{-\gamma k/2} apply respectively by (52) and |Z_*|\le \sum_S R_S. Schur’s operator norm bound (square root of product of row and column bounds) proves (50), decreasing positive constants in exponents as needed. Here in passing to the copy of \lambda we indeed multiply the integral kernel by at most 1 to account for the earlier factor N^k/(N)_k.

Finally if we twist the tuple representation by sign, for k<N/2 averaging even one network layer already gives the zero operator. For each tuple there is a switched pair fixing all its positions (i.e. using two unoccupied positions), so the signed subgroup average there cancels. This proves the sign twist claim.□

Proof of Theorem 7.4. The weak moment and the sparse operator bound are independent inputs. We now show that they cover every representation and that the exponent increases at successive splits have a bounded product.

We spell out which representations are covered by (50) and its sign version, taking \delta=\eta/4 for the \eta in (46). Write D_\lambda for dimensions. For large d, unless

we necessarily have

Here is one way to check. Put h=\max(\lambda_1,\lambda^{\mathsf t}_1), and if h\le N/10, the hook-length formula already gives at least (5/e)^N from hooks at most 2h. Else we can transpose if needed and take h as the first row length. If there are at least z=\lfloor N^{1-\delta}\rfloor boxes below the row, take a subdiagram consisting of the row and just z such boxes. The dimension of the original is at least the number of standard fillings of this subdiagram, which is at least \binom{h}{z}. In fact one can fill the first z boxes of the top row first (having z<h), then freely interleave its remainder with the lower part in a fixed standard order on that part, since all lower boxes are in columns at most z; and fillings extend to the original. This suffices for (54), proving (55) when (54) fails.

Choose a fixed r_{\min}\ge2 with 2br_{\min}\ge4, where b is the sparse constant for \delta=\eta/4. At each level k in (55) there are at most 2^{k+1} shapes, allowing transpose, and each has dimension at most N^k. The sign twists are annihilated by the sparse lemma; for the other nonconstant shapes, (50) bounds their regular contribution at every u\ge r_{\min} by

The sign representation itself also contributes zero. These are the first class in Lemma 4.4, with \varepsilon=1/5; their contribution is at most 1/10 above an absolute threshold.

The remaining class satisfies (54). Use the positive-square convention \nu=2 and set

Proposition 7.2 supplies its child-to-parent hypothesis uniformly for inherited exponents at least r_{\min}. The decisive comparison is

Also (2-\alpha)(1+d^{-1/2})=1+O(d^{-1/2}). The common lemma therefore supplies bounded recursive exponents r(d) satisfying (53), including the finite initial sizes. Its positive-square convention means the matching singular exponent is 2\sup_d r(d). Proposition 4.1 gives chi-square divergence at most 1/5 after every integer w\ge\sup_d r(d) of forward sweeps, uniformly over initial decks. Since each sweep is d physical shuffles, the stated total-variation bound follows.□

Proof.

Consider any law \zeta on arrays supported on \mathcal E, assuming D(\zeta\|\nu)<\infty. Write X_i=X_{i,\cdot} for the row permutations and Y_j=Y_{\cdot,j} for the column permutations (using single subscripts for these permutations). We use \zeta_X,\zeta_{X_i},\zeta_{Y_j}, etc., for the laws of parts of the arrays under \zeta. Put

By (65),

Indeed, decomposing the joint divergence against the product law \nu, we get J, plus D(\zeta_X\| \bigotimes_i \nu_{X_i}), plus the divergences of the \zeta_{Y_j} against their individual laws in \nu. For the X term, decompose further into D(\zeta_X\| \bigotimes_i\zeta_{X_i}) and the sum of individual marginal divergences. Applying (65) to the individual divergences and keeping at least an \epsilon fraction of D(\zeta_X\| \bigotimes_i\zeta_{X_i})\ge 0 gives (68).

To lower bound J, consider drawing the arrays from \zeta, with X revealed first. Take independent uniform priorities t_j\in[0,1], independent also of the arrays, and expose Y column by column, in order of decreasing t_j. Within each column reveal its entries in increasing order of i. For any fixed priorities (ignoring null events of ties), the chain formula for relative entropy gives J as a sum of expected conditional divergences, one per cell (i,j). In that cell the divergence is between:

• •

  the conditional distribution of Y_{ij} under \zeta, given X, earlier columns, and earlier entries in column j;

• •

  the law u with

The second (reference) law depends just on previous entries in the same column. Though we suppress its cell and history indices on u,u_y, we always take conditionals at histories arising under \zeta. Since we know X, the first distribution is supported on candidates that are not blocked, where y is blocked if (X_{ij},y) has already occurred as a pair in an earlier column.

Put

Call the cell bad if g(j,X_{ij})>a^{1/8}, good otherwise. Call a candidate y high if u_y>a^{-1/4}, low otherwise. Let R_X count bad cells, and R_Y cells whose actual Y_{ij} is high. These counts depend on the outcome arrays (and law \zeta for defining high), but not the priorities.

For a good cell in the chain formula, apply (66) to the conditional divergence, using \eta=a^{-1/16} and this potential:

On bad cells just take W(y)=0. These choices depend only on what is given before the cell, besides the priorities and the law. The actual choice under \zeta is not blocked and has u_y>0 almost surely, so the reference normalization in (66) is positive as needed.

For the log normalization term of (66), condition now on the entire outcome arrays (X,Y) and on t_j, and average over the other priorities. Assume the cell is good and write x=X_{ij}. For each y, including each low candidate, the pair (x,y) occurs exactly once in the outcome arrays, since \mathcal E holds and there are ab cells. If its occurrence is in another column, the probability the candidate is not blocked is t_j, since the priority of that column is uniform independent. The candidates occurring in the current column with x number at most g(j,x), so the total u mass of those among them which are low is at most a^{1/8} a^{-1/4}. Writing Z=\sum_y u_y e^{W(y)}, this gives

This computation uses that u is fixed in this conditioning, as the within-column order is fixed. On a bad cell Z=1. We get in particular \mathbb E\log Z\le a^{-1/16} by Jensen’s inequality.

For the expected-potential term in (66), averaging over histories under \zeta amounts to using the actual score W(Y_{ij}). For each good cell whose actual choice is low, since good/low status for the actual choice is independent of the priorities, its score with the priorities averaged is

and it is 0 on the other cells. The displayed integral lies between 0 and 1 for sufficiently large a. Since the chain formula for J holds for each fixed priority vector with distinct entries, averaging our lower bounds over priorities and summing all cells gives

The counts lost in (69) can be paid for by the deficits D_X,D_Y. First, for D_Y, use its chain formula for the marginal column laws against uniform permutations, within each column in increasing i. While the number remaining to be revealed in the column (including the current cell) is at least \sqrt a, the high subset has uniform conditional probability at most a^{-1/4}, since it has size at most a^{1/4}. Use (66) with potential (\log a)/8 on the high subset and 0 outside, to see that the conditional divergence at this cell, from u against the uniform choice among those remaining, is at least

Skipping fewer than \sqrt a cells at the end of each column (their conditional divergences are nonnegative), taking marginal expectations, and summing gives

For D_X, we claim for large a,

To verify this let \gamma=(\log a)/16 and h_0=a^{1/8}. Under U_b^{\otimes a}, the reference law for D_X, the probability of any specification of z different cells to prescribed values in X is at most (e/b)^z. For a compatible specification this follows row by row because for z_i cells in one row its probability is 1/(b(b-1)\cdots(b-z_i+1)), at most (e/b)^{z_i} by b!\ge (b/e)^b (the geometric mean in the descending product for the row is at least that from b!). Incompatible specifications have probability zero. Also,

To bound its expectation, expand this product. For each selected (j,x) with g(j,x)=s>h_0, bound by specifying s rows having X_{ij}=x, summing over the choices and using factor e^{\gamma s} (for the probability bound we do not need to require that there are no further matching entries). In a term with several selected (j,x), if the specifications conflict they have probability zero, and otherwise they require distinct cells. Thus

for all sufficiently large a. Indeed the sum inside is at most \sum_{a\ge s>h_0} (2 e^2 a^{1/16}/s)^s using a/b\le 2; this goes to zero faster than any inverse power of a. Applying (66) proves (71).

Since \epsilon\log a tends to infinity, (70)-(71) in (68) absorb the terms \mathbb E_\zeta[R_X+R_Y] from (69). We conclude

Taking \zeta=\nu(\cdot\mid\mathcal E) when \nu(\mathcal E)>0, this proves (67).□

Proof.

In fact (\pi_k(Q_n)F)(v) is the expectation of F on the tuple after moving v through a scan and then an independent reverse scan (layers in reverse order). This follows from Q_n=T_n^*T_n and the representation action. Start the tuple at v and let its ordered midpoint tuple between the scans be w. For any set D of k positions, we have

To see this, during the first scan consider just the occupied set of the k labels. At any point its law, with occupancy marginal probabilities p_x on positions, satisfies the bound \Pr(D'\ \text{all occupied})\le\prod_{x\in D'}p_x for any subset D'. This holds initially, and is preserved through any one independent fair pair swap: the marginals of the two positions are replaced by their average. For a subset containing exactly one of these positions, averaging the two previous bounds gives the new bound; for a subset containing both, the probability stays the same and the product bound can only increase; for subsets containing neither there is no change. We can apply this through the sequence of all individual swaps. At the midpoint each card separately is uniform on the positions, since in its path each bit has been randomized with a fresh fair choice. Therefore p_x=k/n for the occupancy marginals, giving (73).

Condition on w. Index the k labels in the tuple by [k]. For S\subseteq[k], consider a law \mathcal P_{S,w} of k paths in the second (reverse) scan with the following dynamics:

• •

  the labels in S follow a common reverse scan with its random switches;

• •

  every other label (omitted from S) just follows a path using its own independent choices to stay or swap in the scheduled bit at each stage.

We allow the path positions under these laws not to form injective tuples across all the labels; extend F by 0 on noninjective tuples. For S\ne[k], the expectation of F at the endpoint under \mathcal P_{S,w} is 0. Indeed any omitted label has a uniform final position independent of the others. If the other final positions are distinct we use harmonicity and the extension by 0, and if not, F is already 0. Thus applying the signed sum of path laws

to F at the endpoint gives the same expectation as the true second scan.

For any tuple of paths in these laws consider its encounter graph on [k], joining two labels if they enter the same switch in some stage (possibly at the same position). The signed sum (74) vanishes on any path tuple whose encounter graph has an isolated vertex. In fact if a vertex is isolated, toggling it in or out of S doesn’t change the path tuple probability. To realize fixed paths in the common switches just requires the corresponding values of the switch coins, with probability zero in case of conflict. The isolated path uses d switches disjoint from those of any other paths (indexing switches by stage as well as pair), so it imposes its values independently, with probability 2^{-d}, just as if using its own omitted-label choices. This proves the cancellation.

Consequently the absolute conditional endpoint expectation in the true second scan is at most \|F\|_\infty G(w), where

The function G(w) is symmetric under reordering w: all choices of S are summed and the dynamics and condition correspond under renaming labels. Therefore (73) gives

To bound the last sum, fix S and fix its entire set of common switch coins and the separate stay/swap choice coins for omitted labels, using the same coins simultaneously for any starting w. For each individual label, the map from its own starting position to its position entering any given stage is then a permutation of the n positions. This is true for a label in S by the common switch layers; for any other label the fixed choices apply bit flips or not, also giving permutations. For these coins, count the starting w’s whose encounter graph has no isolated vertex. Each such graph contains a spanning forest with c\le k/2 components each of size at least 2; take a root in each component. (If k=1 there are no such graphs.) For given c, the number of rooted forests involved is at most \binom{k}{c} k^{k-c}, by choosing roots and parents. For a fixed forest, the starting positions of its roots can be chosen in at most n^c ways. For every other vertex, once the parent’s starting position has been chosen, there are at most 2d choices, since at some stage the child’s path must enter the switch that the parent enters. At a given stage there are at most two choices of the child’s starting position by the permutation property. Hence the number of w’s satisfying all the encounters of this forest is at most n^c(2d)^{k-c}, not even needing to enforce injectivity in this bound. Using this count and averaging over coins for each S, (75) implies

In the last inequality we used 2dk/n\le 1 and can take C_*=2(4e)^2. This establishes (72).□

Proof. The ordered k-tuple module is induced from the trivial representation of S_{n-k}. Branching and Frobenius reciprocity show that V_\lambda occurs in it, by removing the k boxes below the first row. It does not occur in any (k-1)-tuple module: every diagram there has first row at least n-k+1. The span of functions lifted by omitting one coordinate therefore has no \lambda-isotypic component. Its orthogonal complement is exactly the harmonic space, because orthogonality to every such lift means that each coordinate sum vanishes.

The operator Q_n(\lambda) is positive. Every eigenvector in a copy of V_\lambda inside the harmonic space satisfies the infinity-norm bound of Proposition 8.3; dividing by its nonzero infinity norm bounds its eigenvalue. This proves the first inequality. The second follows from Q_n(\lambda)=T_n(\lambda)^*T_n(\lambda).□

Proof of Proposition 8.1.

Put s=\lfloor n^{1-\beta}\rfloor. For large d, s<n/(2d), so Corollary 8.4 applies to all first-row levels 1\le k\le s. Its positive-eigenvalue bound is

since k/n\le n^{-\beta}. There are at most 2^k shapes of level k, each of dimension r_\lambda\le n^k. Thus their complete regular contribution at any p\ge16/\beta is at most

This uses the bound at the smallest allowed p, so the size threshold is uniform over the inherited exponent.

A matching layer annihilates every shape with more than n/2 rows, as in the proof of Theorem 1.2. In particular all shapes with n-\lambda'_1\le s vanish, since n-s>n/2 for sufficiently large n.

Treat the one-row shape separately: it is the trivial representation and contributes 1 to M_n(p). All shapes not handled so far have

For them we have

for some absolute c>0 when d is sufficiently large. For if \lambda_1\ge s, we can find a subdiagram consisting of a first row of length s and s more boxes below it forming a tail partition (as there are at least s boxes available below, taking a subpartition of size s, of width necessarily at most s). The number of standard tableaux of this subdiagram is at least the Catalan number \frac{1}{s+1}\binom{2s}{s}. Indeed interleave filling the top row and filling the s-box tail in the order of any fixed standard tableau on the tail, keeping the number of filled top row boxes always at least the number of filled tail boxes. This ballot condition ensures any tail box being filled already has the required top-row box above in its column (the column index is at most the number reached in filling the tail). Each resulting tableau extends to the original shape by filling the rest after the subdiagram. This proves (78) in the case considered; the case \lambda'_1\ge s follows as well by transposing. If both lengths are smaller than s, then every hook length is at most 2s, so

which also gives (78) for large enough d, since n/(2s) tends to infinity.

Apply the one-step estimate of Lemma 4.4 with the positive-square convention \nu=2, remainder \varepsilon=1/8, low-level baseline P=16/\beta, and

Here (61) is the rough child-to-parent bound, (77) makes the low-level remainder at most 1/16, and (78) provides the regular multiplicity of every remaining block. The large-block remainder is bounded by

because \beta<\alpha. It is therefore at most 1/16 above an absolute threshold independent of q. Adding the constant contribution proves (60).□

Proof of Theorem 8.5.

The application of Lemma 4.4 just verified has exponent multiplier (1+d^{-1/2})^2=1+O(d^{-1/2}). The lemma supplies the common finite base and bounds the product of these multipliers over rounded halvings. It therefore gives the asserted bounded sequence p(d). Proposition 4.1 applies with singular exponent 2\sup_dp(d) and remainder 1/8.□

Proof. Use the permutation representation on ordered K-tuples of distinct positions, where K=\lfloor k n^{.001}\rfloor; thus K/n\le n^{-.004}. Split the coordinate sequence into chunks of lengths between \ell and 2\ell, where \ell will just be a sufficiently large constant, and e can be taken sufficiently large. So the positions are tuples of macro coordinates, ranging in sets of sizes L_j, each between 2^\ell and 2^{2\ell}. A sweep updates these macro coordinates in sequence, doing sweeps T_{L_j} independently in every fibre of coordinate j, by which we mean with all other macro coordinates fixed. For the ordered K-tuples this means the operator of a chunk is block diagonal, with a block specified by the allocation of tuple members to fibres. On such a block it is a tensor product: for a fibre with t members use T_{L_j} acting on ordered t-tuples (using fixed ordering of the members in this factor).

For any such local operator T write T=V|T| with unitary polar factor, and replace it by

Apply these replacements in every block, and let F(z) be the product of the resulting chunk operators in the sweep order. We can take Q>2 a sufficiently large constant depending on \ell. On the first line of the strip the operator norms are at most 1. On the second line T(z) is arbitrarily close to the matrix averaging uniformly on its local tuple space, since T preserves constants with all other singular values strictly less than 1 by the generation observation; only finitely many local sizes are used. For t=0,1 we have the averaging exactly on this line (a sweep gives a single point all fresh fair bits). In particular we take Q so that on this line, with L=L_j, each entry of T(z) in absolute value is at most

with (L)_t a falling factorial.

Between any given input and output ordered tuple, there is at most one trajectory of tuples through the chunk product: at each boundary of chunks, the already processed macro coordinates of each point must be its output ones and the others its input ones. A valid such trajectory, under ideal routing doing full uniform permutations independently in each fibre at each chunk, has probability given by multiplying 1/(L)_t for its fibres. Thus (81) bounds the sum of squared entries of F(z) by

Here we sample the starting K-tuple uniformly and do the ideal routing, t referring to the occupancy by those routed points; we used \prod_j L_j=n.

We detail why clustering of the K points in this estimate is harmless. Condition on the full ideal routing of all n points, let X be the uniform size K sample of input points, and use the graph on n points connecting any two that visit the same fibre at any chunk. Maximum degree is O_\ell(\log n). Consider a component Y of the induced graph on the sample, of size v. Over all chunks its fibre occupancies satisfy

In fact, group the inputs by their not-yet-processed coordinates: form the tree starting with all inputs and splitting by the input coordinate of the last chunk, then the next-to-last, and so on. Take any node specified by coordinates later than j, split into children by coordinate j. The points of Y here (say of number v_0>0) when routed up to chunk j are distributed over fibres still within the specified later coordinates, and the t in one fibre come from t different children because their j-coordinates are distinct and not yet processed. Hence the sum of t\log t over these fibres is at most v_0 times the entropy of the child proportions: average the distributions over children given by each fibre (each distribution uniform on t children with weight t/v_0) and use concavity. Summing the bounds at nodes telescopes, giving (83). There is no shared occupied fibre of two different components.

For t\ge 2,

with C absolute. Up to \sqrt L use \log(L^t/(L)_t)=O(t^2/L); above that, it suffices that this log is at most t, using the average over the full increasing sequence \log(L/(L-i)),\,0\le i<L. Choose \ell so large that by this and (83) the product in (82) is bounded by the product over nonsingleton components of v^{\zeta v}, \zeta=.0005.

With \Delta=O_\ell(\log n) a degree bound (at least 1), and u=K/n, the expectation of this last product is at most

Indeed we can sum products over collections of disjoint connected sets included in X, charging the components in particular; the probability cost for such a collection is at most u to the power of total size. The count of connected sets uses a spanning tree walk of length 2(v-1); allowing arbitrary collections with the product cost gives the exponential bound. The sum in this exponential is O(n\Delta^2 u^2): for v\ge3 compare after factoring n\Delta^2 u^2 to powers of \Delta^2 u n^{3\zeta}, which goes to zero. Thus (82) is at most \exp(O(k)), since \Delta^2 K^2/n=O(k) for our k,K.

The enlarged tuple space has now supplied a Schatten budget \exp(O(k)). Its large branching multiplicity will convert that budget into decay on each first-row level. We now interpolate. We have \|F(1+iy)\|_2^2\le\exp(O(k)), whereas F(2/Q) is the sweep operator on the K-tuple space, so its Schatten Q-norm to power Q has the same upper bound. By branching and Frobenius reciprocity for the pointwise stabilizer of K positions, the multiplicity of \lambda in this space is the number of standard tableaux of the skew shape obtained by removing the row of length n-K from \lambda. Since \lambda_2\le n-K here (for large enough n), there are at least \binom Kk such tableaux: the tail of size k is separate from the remaining K-k entries of the first row. The Schatten estimate with this multiplicity thus gives, say,

for all sufficiently large n (use K/k\ge n^{.001}/2). As d_\lambda\le n^k (it occurs even on ordered k-tuples), increasing to a suitably large constant power p_* proves (80).□

Proof. For the proof, the l-array gives a bipartite multigraph on sides of size b, with one edge from i to l_{ij} per cell; it has degree a. Call an edge bad if contained in a parallel pair or in a 4-cycle. Write L_{\rm bad} for the number of bad edges (cells).

Here is a useful moment bound for these edges under the uniform independent column assignments \mathcal U:

for some absolute c>0. Compare any law \xi of column assignments to \mathcal U by KL divergence (relative entropy). Use the chain rule revealing one cell at a time in an order given by independent uniform priorities. For a current cell, if at least b/3 values are still available in its column, test the event that its new edge closes a parallel pair or a 4-cycle with edges already visible; otherwise use an empty event as test. Under the \mathcal U-conditional distribution, chance of the test event is O(a^3/b)=O(n^{-.6}); the possible targets from paths of length 1 or 3 are bounded in number by a+a^3. Thus each conditional KL divergence is bounded below by

where the order is given (use the entropy inequality with .25\log n times the indicator as test function). For a given completed array, each bad edge will score the event with at least absolute positive probability over order. Indeed fix up to three witnessing other edges; with probability bounded below the cell priority is in (.3,.4) and these witnesses precede it, and at least b/3 column choices are still available. For the last condition one can use just concentration of the number of other cells of that column seen, with at most three additional cells forced earlier. Averaging and summing, the divergence of \xi from \mathcal U is at least c(\log n)\mathbb E_\xi L_{\rm bad}-O(n^{.9}), giving (86), for example by taking \xi the exponential tilt. Hence for our possibly nonuniform column laws, by Hölder (with exponent c\log n on \exp L_{\rm bad}, and using density at most D_L of the product law),

The short-cycle estimate controls the column geometry. We next condition on that geometry and expose the row permutations; the restriction to edges belonging to neither a parallel pair nor a four-cycle makes the blocking rows distinct.

Fix columns and upper bound the conditional probability p of distinct pairs, assuming it is positive. The conditional law of row assignments given distinct pairs has divergence -\log p from the product of the original row laws. Reveal rows in a random order, again using independent uniform priorities. At row i, a conditional divergence term is at least minus log of the original row-law mass of candidates fitting with previously revealed rows (no reused pairs), since the conditional law is supported on such candidates.

To bound these masses, fix any full realization from the law given distinct pairs. In row i let g_i be the number of cells whose column-array edge is not bad. For each such cell ij where a candidate for the row changes the h-label, the new pair (new h, l_{ij}) occurs in the full realization and must occur on some other row (as l_{ij} doesn’t repeat within row i). Moreover all the blocking rows identified this way for the candidate are distinct: otherwise two such l values connect row i and another row by a 4-cycle. If v_i is the priority of i, put

Thus for a given candidate matching the realized row permutation at M cells (total matches), the probability over remaining priorities of fitting is at most \exp(-x g_i+x M), since none of the blocking rows can have come before it. So the expected log of the mass fitting, given the realization and v_i, by Jensen is at most

where \nu_i is the original candidate law on row i. For uniform permutations the log of the moment \mathbb E\exp(tM), t\ge 0, is at most \exp(t)-1, by counting subsets of matches. Thus by Hölder using exponent .5(\log a)/x on the moment function for x>0, we get

We integrate these log mass bounds keeping in mind \mathbb E x=1-a^{-1/4}. They apply uniformly when histories are taken from the full law conditioned on distinct pairs (which can be sampled independently of the priorities). So by the divergence bound for -\log p,

This along with (87) proves (85).□

Proof. Apply Lemma 3.3 with the line projections as its positive operators. Their regular ranks and squared masses are D_i=d_{\mu_i}r_i and D'_j, so the normalized squared coefficient densities have these same caps. At an intermediate cell between row action r and column action y, the column of origin is given by r^{-1} and the row of destination by y. Thus opposite-order routing is exactly the distinct-pair event in Proposition 9.3; inversion preserves the coefficient caps. The lemma and (85) give

Finally n!/(|R||Y|)=n!/((a!)^b(b!)^a)\le e^{n+O(\log n)}, which proves (88).□

Proof. Let B\ge 1 be a fixed constant sufficiently large for (88), so we can use exponent \Gamma_n=1+B/\log n in that bound. We use a sufficiently large absolute cutoff n_0, which can be taken above all fixed thresholds as needed in the proof below (in particular the estimates requiring sufficiently large sizes in the induction step will not depend on the base choice of power). Choose p_{\rm base}\ge \max\{4,p_*\}, also sufficiently large to make the left side of (89) with p_{\rm base} at most 1 for every size up to the cutoff; this is possible by strict contraction on nontrivial sectors. Use p_{\rm base} up to the cutoff. Above, with a,b from the grid estimate, set

This is bounded absolutely: down any recursion path above the cutoff, the logs of sizes decrease by at least a constant factor (i.e. next at most, say, .95 times the current log), so the sum of their reciprocals there is bounded.

Split the coordinates into the first \log_2 a and the remaining \log_2 b, arranging the wires so that T_n=T_Y T_R with T_R a product over rows of copies of T_a, and T_Y likewise over columns with T_b. Use the ambient regular representation. Put X=|T_Y|,\ Z=|T_R^*|. We can drop outer unitary polar factors, and use

This is Lemma 2.6 with P=p_n and q=4.

The positive powers on the right factor as corresponding products commuting within the line subgroups (row factors amongst themselves, and likewise columns), since the operations factor in the respective subgroup algebras and lift to the ambient group algebra. Write p=p_n. On a line of size m (a or b), according to orientation, use the spectral projections within irrep \mu of that group’s |T_m| or |T_m^*|; write E_{\mu,t} for the projection for singular values at least t>0 (zero on other irreps), of rank r_\mu(t) on the irrep. The line power for (90) is

lifted as an element of the corresponding group algebra. Expand in all lines and use the triangle inequality and (88) on the right of (90). This gives

The spectral support cutoff supplies a negative power of a large child dimension. This compensates for the number of local partition types: a slight surplus in the parent exponent becomes a dimension saving because the integral ends before t=1. We show that each integral in (91) is O(\log n). Write W=d_\mu {\rm Tr}|T_m(\mu)|^{p_m}. Then

If W\le1 then simply integrating with the first bound gives at most p/(p-\Gamma_n p_m)=O(\log n). This applies for sizes up to the cutoff, and also in larger sizes for the trivial irrep, for the cases from (80), and for the sectors killed by the pair layer. For the remaining cases, we can use W\le H=\exp(m^{.99}) inductively and have \log d_\mu\ge m^{.995} by (84). Using the support bound as well gives at most

Since p/p_m-\Gamma_n\ge 1/\log n, this is O(\log n) as claimed (for m above the cutoff), using m^{.995}\gg m^{.99}\log n for large sizes here, as \log n=O(\log m).

The count of partitions of m is at most \exp(O(\sqrt m\log(m+1))), for example by describing rows and columns out from the diagonal. Therefore (91) with b lines of size a and a lines of size b yields

since b\sqrt{a}=O(n^{.95}), a\sqrt{b}=O(n^{.55}). All the estimates needed here for sufficiently large n have constants independent of p_{\rm base}, so a fixed cutoff as specified suffices. We have bounded the regular-representation sum, proving in particular (89) and closing the induction.□

Proof. Finally take a constant integer number of sweeps j at least twice the upper bound on the p_n’s. For nontrivial sectors with 1\le k\le n^{.995}, (80) shows for large sizes

where the first norm after the dimension factor is Hilbert-Schmidt. This is negligible even summed (there are at most 2^k partitions for a given k). For remaining sectors not already killed we similarly have by (89)

which by (84) is again negligible summed over partitions. Thus the squared Hilbert-Schmidt norm in the regular representation of T_n^j minus uniform averaging tends to zero. The identification with the squared L^2 distance of the permutation density is the one in Proposition 4.1. All powers above are controlled by operator submultiplicativity; no normality of T_n is required.□

Proof. It suffices to obtain a nontrivial estimate when k/n is sufficiently small; outside that range, choosing M_0 large will make the right side at least one. For k=1 the norm is zero: on single-site functions the switches average each bit, giving global averaging as the product.

We induct on the number of coordinates. The main step is a tail bound for the level lost after the first matching projection. Once this bound is established, we will check the constants in the norm recursion.

For induction, write n=2m, use the pairs of a dimension for the rightmost projection in T_n, and call their flip subgroup K, with projection P_K. There are two sides of size m, with the sites of each pair in opposite sides. The other factors act separately in these two sides, so that

with the tensor product here in the subgroup algebra of G_m\times G_m. We use level k realized on the injection tuples x=(x_1,\ldots,x_k). It suffices to bound the squared norm after the two side operators starting with a K-invariant unit vector f of our type there. Norms of tuple functions can use uniform counting probability. Such f has zero sum in each of its coordinates as explained above.

Restrict f to the different assignments of the k indices to sides, with j indices in the first side for a given assignment. Decompose in types within the two sides, of levels s_1,s_2, where s_1\le j, s_2\le k-j. We get a probability law on these data by squared norms of the orthogonal parts. Under it put R=k-s_1-s_2. We give two controls on this law:

• •

  j has subgaussian tails around k/2, in particular \Pr(|j-k/2|\ge t)\le 2\exp(-2t^2/k), and \Pr(j=0\ \text{or}\ k)\le 2^{1-k}.

• •

  For k/n sufficiently small, there is an absolute C_0 such that

The first property follows from K-invariance and averaging by randomizing the pair orientations for the side assignment. Each tuple then uses some double-occupied pairs contributing one index each in the first side, and singles with independent fair side assignment.

To prove (94), consider projections indexed by sets I of r indices to be ignored, that is, average the positions of those indices knowing the positions of the other indices and the sides of all indices. Write these as L_I. All these averages use the uniform injection law conditioned on the complete side-assignment vector. When an index is deleted, its side remains part of the conditioning and only its position is integrated out. Successive deletions are therefore conditional expectations onto nested sigma-algebras: their composition is the single average over the deleted set. We apply the one-slot bound on each resulting shorter tuple space, retaining the same two left representation types.

We first record why

when k/n is sufficiently small. Work conditionally on assigned sides. Within one side with a tuple of l\le k positions and left type \mu of level s, the sum of the projections which average out one coordinate has eigenvalues

on the corresponding right types \rho described by Pieri. Indeed the single-coordinate average for coordinate i, on functions of a permutation, acts on the right by (1+\sum_{l<q\le m}(iq))/(m-l+1). Sum over i\le l, and use (92) and invariance on the right under G_{m-l}. Now \rho contains the diagram \bar\mu=(\mu_2,\mu_3,\ldots) since \mu/\rho is a horizontal strip. Thus D_l(\rho)\ge D_s(\bar\mu) by adding boxes (each addition to size v to go to size v+1 has content at most v). Also D_m(\mu)-D_s(\bar\mu)=(m-s+1)s. This gives the projection sum lower bound

It holds also with zero indices and the trivial type. For both sides together, summing over the coordinate to remove thus gives squared norms summing to at least half the excess of current tuple length over total level, times the squared norm before removal. After an averaging we can work on the shorter tuples with their marginal law; the averaging preserves the left types when nonzero. On a component of total level k-R, iterating this bound through r successive deletions gives 2^{-r}(R)_r times the original squared norm, where (R)_r=R(R-1)\cdots(R-r+1). At each stage the conditional expectation acts on the shorter tuple space, with all side assignments retained. The tower property identifies the result with averaging all removed coordinates, and each set I is counted r! times through its possible deletion orders. After division by r!, the lower bound is 2^{-r}\binom Rr, which is at least 2^{-r} for R\ge r. Summing the components proves (95). All projections in (95) respect assignments and the left types of the side groups.

We have expressed a large loss of level as a large sum of coordinate-projection norms. We now bound the same sum from above using the matching-pair symmetries of f.

For the upper bound on the left hand side of (95), we can average it with the side partition randomized by K, because f is invariant under K. Write \epsilon(x_i) for the side sign of the position x_i under the random orientations. Given the retained positions z, the numerator sum in an average over the other positions constrained by a specified vector of side signs (\eta_i)_{i\in I} equals

where x|z indicates all distinct-site extensions. The equality uses the zero sums. In computing the squared norm, we sum squared absolute numerator sums divided by the number of extensions with the given side constraints, over z and (\eta_i), with the overall tuple space normalization. These denominators are at least (m-k)^r. Thus we can use this lower bound before expanding the averaged squares on the right in (96).

Two tuples in that expansion, x,y agreeing off I, must among their I-entries together hit each pair an even number of times for the sign expectation not to vanish. We bound the resulting nonnegative majorant on absolute values of f by a row sum (the matrix is symmetric). For fixed x, classify I as using u single entries in pairs and v doubles, u+2v=r, counting just x_I. The number of choices of I with these data is at most k^{u+v}/(u!\,v!): choose v full pairs in x, then the other entries. For each, the possibilities for y_I are bounded by 2^u r! n^v/v!, since they have to use the same u singleton pairs, and v doubles. The sum over sign specifications costs 2^r, with a factor 2^{-2r} in the square in (96). It follows, using r!/(u!v!v!)\le 3^r, that the left hand side of (95) is at most

for an absolute C_1 and k/n sufficiently small. This proves (94).

The lost-level tail (94) is now proved. It remains to show that its cost is smaller than the contraction supplied by the two child sweeps.

To finish the induction for (93), use the inductive bound in each side (factor 1 for level 0). For the squared output norm, divided by the desired bound, this gives the upper bound by the expectation of

where zero terms in the sum are set to zero. The sum in this exponent before multiplying by \alpha is bounded above by

for some absolute C_2. For s_1=j,s_2=k-j this follows by the binary entropy formula or Taylor expansion near k/2, and boundedness away from the middle. If j/k is in [1/4,3/4] and R< k/8, changing to s_i changes the terms by at most O(R); outside these conditions the crude upper bound O(k) suffices.

Here are details that constants can be fixed in the induction. Take h=1/20, and \alpha>0 sufficiently small, with \alpha<1/4. On R=0 and k\ge2, cases with j=0 or k contribute to the expectation at most 2^{1-k}2^{\alpha k}\le 0.6 by making \alpha small. The other cases with R=0 contribute at most 2h, by (98) and the subgaussian estimate, which by taking \alpha small gives \mathbb E \exp(2\alpha C_2(j-k/2)^2/k)\le 2. For R=r\ge1, Cauchy-Schwarz with (98), the same subgaussian estimate, and (94) bound the total contribution summed over r\ge1, for M_0\ge1, by

Choose M_0 so large that whenever h(M_0 k/n)^{\alpha k}<1, k/n is small enough to apply all the estimates and make this last contribution at most 1/5. Thus (97) gives the bound required. When h(M_0 k/n)^{\alpha k}\ge1 we need no induction by contractivity, and level 1 was settled already. This proves (93) (with the recursion starting trivially at a single site).□

Proof. For clarity, by entropy chain rules,

with H Shannon entropy. We expose all B_c, then the rows A_i in random order given by increasing independent uniform priorities t_i\in[0,1] independent of the configuration. Within each row expose the entries in column index order j=1,\ldots,a. The contribution for a cell to I is the expected relative entropy of its full conditional law given the information available before exposure (including the order), relative to p, its marginal conditional law based on just the history in the same row. Here both laws are for A_i(j), using \nu to form the laws. These expected contributions sum to I.

For this cell let the light set consist of c with p(c)\le a^{-1/2}; denote it by L, and use p_L for the conditional probability on L when it has mass. An allowed set is given by the candidates c for which B_c(i) does not appear among the previously exposed rows’ outputs B_{A_{i'}(j)}(i') for this column index j. The expected relative entropy for the cell is at least

Indeed one decomposes relative entropy according to whether the entry is light, then keeps only the divergence (weighted by conditional probability) when light, whose support condition gives the log bound. The log expression for the weight only needs to be evaluated when the entry is light and is then finite almost surely.

Say a realized cell is good if A_i(j)\in L, p(L)\ge a^{-1/8}, and

Condition on the realized configuration for a good cell and on t_i, but not on the priorities of other rows. Each candidate c giving an output distinct from the actual output is forbidden with probability t_i, since precisely one other row gives that candidate output value in column index j. The mass under p_L of candidates giving the actual output is at most a^{-1/8}, by (102) and the bounds defining light and good. Consequently the expected allowed mass is at most 1-t_i+t_i a^{-1/8}. Notice that goodness and p_L depend on data of the configuration but not on the priorities. By nonnegativity in (101) we can restrict there to good cells, and Jensen’s inequality and integration in t_i now yield the lower bound

for (101). This uses \int_0^1 -\log(1-t+t a^{-1/8})\,dt \ge 1-O(a^{-1/16}).

Each good cell has supplied almost one nat of entropy. To obtain a total saving of almost n, we must pay for the cells excluded by the three goodness conditions.

We detail how the expected number of bad cells is bounded by

For heavy actual entries, consider in each row the exposure under its marginal law, relative to drawing a uniform permutation sequentially. Ignore its last at most O(a^{3/4}) cells so that all considered draws have at least a^{3/4} positions left. Under the conditional uniform reference, the set \{c:p(c)>a^{-1/2}\} has probability at most a^{-1/4}. For any laws q,q_0 the variational inequality for divergence gives, for an event E and v\ge0,

Applying this conditionally with v=(\log a)/8 and summing by the chain rule gives the desired heavy-entry part of (104). Cases with p(L)<a^{-1/8} and a light actual entry have expectation count at most n a^{-1/8} without any entropy cost.

It remains to address (102). Its exceptional count is the same computed over i,c instead of i,j, looking at the multiplicity of the value B_c(i) in row i of the column-permutation data. For groups of cells with equal such value and multiplicity >a^{1/4}, a constant fraction of each group have already had that value appear at least a^{1/4}/2 times in earlier columns (up to harmless rounding, or use threshold a^{1/4}/3). Reveal the data of B row by row in deterministic order, with columns in order within each. Ignore rows near the end with fewer than b a^{-1/8} entries remaining available in a uniform column permutation. The conditional uniform reference probability that the revealed value has already appeared at least a^{1/4}/3 times within the row is at most 3a^{3/4}/(b a^{-1/8})\le 3a^{-1/8}. Apply (105) with v=(\log a)/16 and the chain rule for D_B. This proves the remaining exceptional count bound, hence (104).

Summing (103) and using (100), (104) proves (99), using D_B\ge\sum_c D_{B_c} once the coefficient on D_B is positive.□

Proof. This is the finite-space entropy–Brascamp–Lieb duality of Carlen and Cordero-Erausquin [4, Theorem 2.1], applied to the compatibility event. We give the specialization to fix the coefficient of every marginal deficit.

The log integral on the left is given by the entropy variational formula, maximizing the expected log product minus D_{\rm joint} over allowed laws supported on valid pairs. After (99) the remaining marginal terms are each bounded by the separate variational formulas with coefficient 1-\theta. Zero weights can also be treated by a limit.□

Proof. First, a positive-matrix trace comparison gives

Apply Lemma 2.6 with A_2=T^{\rm row}, A_1=T^{\rm col}, P=2p' and q=4. Then X=|A_2|^2, Y=|A_1^*|^2, giving exactly (109).

Write x(A)=\prod_i x_i(A_i) for the coefficients as a density relative to uniform row permutations of X^{p'/2}; similarly y(B)=\prod_c y_c(B_c) for Y^{p'/2}. The individual positive line operators are X_i^{p'/2} and Y_c^{p'/2}. Applying Lemma 3.3 to these operators, before normalizing their squared coefficient masses, gives

For the line norms we use Lemma 2.7 in each subgroup’s own regular representation. With q=2/(1+\theta), the Schatten q norm of X_i^{p'/2} in its own regular representation is at most 2^{1/q} by (107), and similarly for Y_c^{p'/2}. Consequently the individual densities in (110) have the needed 2/(1-\theta)-norms bounded by 2. Apply (106) to their absolute values. Since by Stirling’s estimate

(110) proves (108).□

Proof of Theorem 10.5. The rectangle estimate leaves a subexponential regular-trace error. We remove it by separating the low levels, controlled by Proposition 10.1, from the higher levels, whose regular multiplicities are large. For large n, use n^{0.995} as the threshold for level. On all types with 1\le k\le n^{0.995}, we already have, independently of (107), enough decay for the trace estimate (111) at a sufficiently large absolute power p_{\rm low}. Indeed each d_\lambda\le n^k by occurrence on injection tuples, and there are at most 2^k diagrams at that level. Using (93), for n sufficiently large and any s\ge p_{\rm low}, the total contribution of these types to \operatorname{Tr}|T_n|^{2s} is o(1); for example M_0 k/n\le n^{-0.004} there, so we can sum the bounds 2^k n^{2k} (n^{-0.004})^{\alpha k p_{\rm low}}.

For any type not annihilated by T_n, the number of rows of the diagram is at most n/2. Indeed it needs invariants for the flip subgroup of one dimension, a product of n/2 copies of the two-point symmetric group, so the Pieri rule builds its diagram by adding n/2 horizontal strips. For such diagrams with k> n^{0.995} and sufficiently large n, we have

with absolute c>0. One quick count of tableaux is by ordering the boxes according to increasing sum of their two coordinates, with arbitrary order within each antidiagonal. If there are l antidiagonals the factorials of their sizes give a product at least 2^{n-l}. Here l=\max_i(i+\lambda_i-1)\le\sqrt n+\max(\lambda_1,n/2) since i\lambda_i\le n, proving (112).

When (107) holds and n is sufficiently large, (108) gives

We apply Lemma 4.4 with \nu=2, \varepsilon=1/8 and P=\max(p_{\rm low},2). The low class consists of the first-row levels 1\le k\le n^{0.995} together with the annihilated blocks; its contribution is at most 1/16 above an absolute threshold. The remaining blocks satisfy (112). Thus the parameters in the common lemma are

The child bound 1+1/8 implies the bound 2 required in (107), and all size thresholds are independent of the inherited exponent. Moreover,

while \alpha_d(1+\delta_d)=1+O(1/d). The lemma supplies bounded parameters p_n and proves (111).

Proposition 4.1, with singular moment exponent 2\sup_n p_n and remainder 1/8, now gives the mixing bound after an absolute number of sweeps. The lower bound in physical shuffle units is Lemma 2.3.□

Proof. Let \eta(x) be the occupation indicator for the r jointly moved cards, and p_x=\mathbb E\eta(x). At the deterministic initial set, \mathbb E\prod_{x\in A}\eta(x)\le\prod_{x\in A}p_x for every set A. A fair switch on u,v preserves this family of inequalities. If A contains neither endpoint there is no change. If it contains one endpoint, averaging the two old inequalities replaces its marginal by (p_u+p_v)/2. If it contains both, the occupation product is unchanged and p_up_v\le((p_u+p_v)/2)^2. Disjoint switches can be applied successively, proving preservation through the sweep. At its end every p_x=r/n, because the endpoint of each individual card is uniform. Summing over distinct tested sites in the disjoint A_i therefore bounds the joint binomial moments for these cards by \prod_i(r|A_i|/n)^{h_i}/h_i!.

The independent walkers have multinomial factorial moments bounded by the same expression with s in place of r: assign the tested hits to distinct walkers, and use their uniform independent endpoints. Expand each binomial coefficient of the sum of the two counts using Vandermonde’s identity. Independence of the two populations and the binomial theorem replace r and s by r+s. This proves the stated bound. No part of this proof depends on which coordinate is updated first.□

Proof.

To see this, take the sweep kernel on k-tuples, with row variable x=(x_1,\ldots,x_k) the input tuple and column variable y the output tuple. Actions on tuples, or on functions of them, estimate the same singular values on \lambda. For two tuple labels u,v, set

for distinct tuple entries as here. Define

Then the tuple kernel is

Indeed given endpoints, paths replace one bit after another in x by the corresponding bit of y. They must remain nonoverlapping as paths through positions. For a pair, if the output bits below h (indices <h) agree, the paths would use the same switch at h, where output bits must be opposite. When compatible they use either no common switch or that one, by the bit replacement order. Thus pair conditions suffice, and each shared switch gains a factor 2 compared to probabilities for independent paths.

For J\subset [k], put

This is the restriction (to our distinct tuples) of the kernel using the joint shuffle only on labels in J, and placing the other output labels independently uniformly; likewise its transpose is restricted from using the reverse shuffle jointly only on J. In particular each of its row and column sums is at most 1. In bounding the block on \lambda we can replace (115) by

Indeed proper-subset terms can be dropped on compression to the \lambda-isotypic space. Their images or the images of their transposes are in subspaces of functions depending only on a shorter tuple, which have no \lambda part.

Make the interaction graph on [k] for (x,y) by using an edge for u,v if (y_u)_i=(y_v)_i for all i<h(u,v); the edge time is h(u,v). The sum for Z vanishes if there is an isolated label, by cancellation. Thus it suffices for norm bounds to use nonnegative kernels Q_J, summed but restricted by the coverage condition (all labels have an interaction).

Put \epsilon=.01, so that k\le n^{1-\epsilon}, and take \alpha=\epsilon/2. We use the dyadic cells from the input hierarchy: a cell of size 2^h specifies the bits of index >h. For an input x, call a label bad if it is in some such cell of size t where the label count r from x satisfies

Otherwise call the label good. Split rows into bad rows (at least k/2 bad labels) and the other rows (called good rows).

Here are two probability bounds for this split.

• •

  Given y, the column sum of Q_J over bad rows is n^{-\Omega(k)}, meaning bounded by n^{-c k} for an absolute c>0 for all sufficiently large n, uniformly. In the transpose experiment the output considered here is x. We will use factorial moment bounds on counts in cells. Lemma 11.2, with r=|J| and s=k-|J|, gives, for disjoint cells of sizes t_i and required counts r_i,

  \Pr\{N_i\ge r_i\text{ for all }i\} \le\prod_i\frac{(kt_i/n)^{r_i}}{r_i!}. \tag{116}

  This bound is used before restriction to distinct output tuples; that restriction can only decrease a column sum of the nonnegative kernel.

  A bad row gives a family of disjoint cells (take maximal ones from the bad-label definition), where

  r_i\ge 2,\qquad t_i/r_i\le n^\alpha,\qquad k/2\le R_0=\sum r_i\le k

  with r_i their counts. We spell out a union bound. For choices of ordered sizes and counts, multiplying (116) by \prod_i n/t_i allows the choices of locations. Using r!\ge(r/e)^r, the result is at most

  \prod_i \left[e^{r_i}\frac{k}{r_i} \left(\frac{k t_i}{n r_i}\right)^{r_i-1}\right] \le e^k k^L n^{-(\epsilon-\alpha)(R_0-L)}.

  In summing over ordered lists we divide by L!, since we seek unordered families of distinct cells. The factor k^L/L! is at most e^k. The remaining number of size and count lists over lengths and totals is bounded by (C(d+1))^{Ck} using compositions, for some absolute C. Since R_0-L\ge R_0/2\ge k/4, this proves the column bound.

• •

  Given x in a good row, the row sum of Q_J subject to coverage is n^{-\Omega(k)}, uniformly. Simulate Q_J before restriction by using independent personal fair bits for each label at each time. Labels outside J just use these bits; labels in J also do, except that when two in J use the same switch we use one of their bits (chosen, say, by label index) and its opposite for the two respective new position bits. This generates the kernel since placements of the J labels need only this joint use of bits, independently at each switch. Only J-labels count for this bit-sharing rule.

  We track the first interaction of a label in the interaction graph (now defined by the output bits whether or not all outputs end up distinct). Until its first interaction its output bits come from its own personal bits. Indeed an actual J-pair at a switch at time h must have highest differing input bit h and matching lower output bits, as the J-positions have stayed distinct.

  If all good labels have interactions, we can select a subset D of them of size at least half the number of good labels, and for each u\in D specify a partner v(u) witnessing its first interaction, so that if the partner also belongs to D, its first time is strictly earlier. To justify the selection, look at labels having their first interaction at a given switch, defined by its time h, the fixed higher input bits, and the common lower output bits. On either of the two sides of this switch there is at most one label having its first interaction there. Two labels on that same side, arriving with the same lower output bits, would have an interaction at their own highest differing input bit, which would be earlier. Hence at most two have their first interaction there. In case two good labels first interact there, we can omit one to avoid ties; one good label alone with first interaction there needs no omission (partners not required to be selected).

  For fixed specifications with times h_u=h(u,v(u)), the probability of these witnesses with the stated first-time property is bounded by

  \prod_{u\in D} 2^{-(h_u-1)}. \tag{117}

  To see this without independence assumptions about the partners, take labels in D of largest specified time h, and compare with the simulation deleting those labels, using the same personal bits of the rest. On the witness event the rest follow the deletion simulation through time h-1, since no deleted label has interacted before then. Earlier witnessing events persist in that simulation. Each deleted label must match its specified partner on the first h-1 output bits, and on the event uses personal bits up to then. Its partner belongs to the rest by the selection condition. With the rest’s personal bits given, these necessary matches have probability 2^{-(h-1)} per deleted label, independently for the purpose of this bound. This gives (117) by successive deletion; equivalently we sum specifications only where within D partners are of strictly earlier specified time.

  For one good label u, the sum over possible partners of 2^{-(h(u,v)-1)} is at most 2d n^{-\alpha}. For a contributing level h, the cell of size 2^h containing u contains a partner and so contains at most 2^h n^{-\alpha} labels since u is good. Because in a good row there must be a witness specification with |D|\ge k/4 if coverage holds, summing (117) over the subsets and partners gives the row bound for large n.

For Z we can sum these bounds with a 2^k factor. On the good-row portion, one has small row sums in absolute value by the second bound and at most 2^k for absolute column sums. On the bad-row portion, the first bound gives small column sums, and row sums in absolute value are at most 2^k. The row-column sum bound on operator norm now gives \|Z\|_{\rm op}\le n^{-\Omega(k)}. This proves (114).□

Proof.

For given j, make a bipartite multigraph between left vertices u and right vertices v, both sets indexing columns. Each initial site (r,u) gives an edge, of row r, from u to v=j_r(u). Each vertex has degree a. Color this edge by h_v(r), a color from [a], so colors are all used once at each right vertex. If hj\in J_0 H, every left vertex also sees every color once, since cards of each initial column must go one to each final row. Call this a valid coloring. (This condition also suffices, though necessity is enough.)

Condition the experiment on the event in (118), assuming positive probability. Its log inverse probability is the relative entropy of this new law with respect to the original experiment. Write it as

where:

• •

  L_j is the relative entropy paid for the new marginal of j;

• •

  L_h is the sum, averaged over this marginal of j, of relative entropies paid for the individual column permutation marginals conditional on j, versus their original independent laws;

• •

  L_{\rm corr} is the conditional total correlation among the column permutations given j, i.e., the relative entropy against the product of their conditional marginals (averaged over j).

All are nonnegative. Write z_j,z_h for the parts of z from the row, column factors, respectively. The relative entropy of the new marginal of j versus independent uniform row permutations is at most L_j+z_j. The sum of relative entropies of the column permutation marginals given j, each versus uniform, is in expectation at most L_h+z_h. These comparisons follow from the density upper bounds.

Estimate L_{\rm corr} by exposing right vertices one by one. In this argument we are in the conditioned experiment, in particular the coloring is valid. Fix j, and take an order from independent uniform priorities in [0,1] for the right vertices, independent of everything else. By the chain rule, the conditional total correlation is the sum of the mutual informations between each h_v and the preceding h-variables (for fixed order, given j). Within h_v expose entries in row order 1,\ldots,a and use the chain rule again. Consider the entry corresponding to a particular edge, from left vertex u to v, and condition also on earlier entries at v, but not yet other columns’ information. Denote by p_c, c\in[a], the conditional law of this entry. We use mutual information of the color with the preceding vertices, for the conditional law (and average over these conditionings). For a fixed set of preceding vertices, if the color is c, none of those vertices can have color c on an edge from u. Thus, writing mutual information as the average relative entropy of the preceding vertices’ variables given the color versus their marginal here, a lower bound for this term is

This uses the marginal not given the color inside the -\log, with the conditioning on j and earlier entries at v still in force; the bound follows from relative entropy for a law supported on an event.

If v’s priority is t, average the preceding set over the other priorities. For color c, write

in the same conditional law not given the entry. Validity implies that the survival probability inside (119), averaged over priorities at the other vertices, is 1-t+t\delta_c. Jensen’s inequality and integrating in t now lower bound the expected term by

For \delta_c=0 the integral is 1. For all 0\le s\le1, the integral with \delta_c=s is nonnegative and at least 1-C\sqrt s: the loss from 1 in the interior is s\log(1/s)/(1-s).

Call an edge heavy in parallelism if its endpoints have edge multiplicity greater than a^{1/2}. We may discard (120) for these edges. On another edge \sum_c\delta_c\le a^{1/2}. For the colors with p_c\le a^{-.7}, we have

For the other colors we allow a loss up to their total p_c-mass instead in (120). Consequently, summed over edges and averaged, (120) bounds L_{\rm corr} below by n, less the expected number of edges heavy in parallelism, the sum of the exceptional masses with p_c>a^{-.7} (averaged), and C n a^{-.1}.

We check the sizes of these losses using the marginal divergences above. We use the elementary estimate

for s>0 and an event F, by the entropy inequality (or just projecting to F). For h_v given j, in the chain of exposing entries use as reference a uniform permutation. Except at most \lceil a^{.9}\rceil late entries per column, it has at least a^{.9} remaining possibilities. The uniform conditional chance to hit the exceptional set for the current p is then at most a^{-.2} (there are at most a^{.7} such colors). Use (121) with s=.09\log a at these exposures, with the set fixed conditional on earlier entries and j. The relative entropies sum by the chain rule. This bounds the total expected exceptional mass over the edges, including the late-entry loss, by

For parallelism, consider the new marginal law of j against the reference of independent uniform permutations. Expose j by rows (all of one row permutation, then the next) and within each by successive entries. For an entry corresponding to left vertex u, count a hit if the target vertex has occurred as target from u already at least a^{.4} times before the entry. There are at most a^{.6} possible hit targets given the earlier entries. At least half the edges heavy in parallelism give hits (in the sense that their endpoint pairs with multiplicity above a^{1/2} give hits on at least half those occurrences, for large a). Again discount at most \lceil b^{.9}\rceil late exposures per permutation where the number of possibilities under uniform may be small. Otherwise the uniform conditional chance of a hit is at most C b^{-.3}, since a,b are comparable. Applying (121) with s=.09\log b as before, the expected number of edges heavy in parallelism is at most

This bounds the loss even if j acquires strong correlations upon conditioning.

The lower bound from (120), with (122) and (123), gives

where we use comparability and have loosened the numerical power. In L, the losses involving L_h,L_j are paid for by those terms themselves. Thus for sufficiently large n this proves (118).□

Proof.

It suffices to bound the full regular trace of PQPQ, since its irreducible contributions are nonnegative fourth powers with regular multiplicity. Lemma 3.3, applied to the local projections, gives

Here the line permutations are independent under their normalized squared-coefficient laws, each with density bounded by its local regular rank. These ranks multiply to r_Hr_J=e^z, so (118) applies with exactly the chosen z. Finally

by Stirling’s formula. Combining in (125) proves (124), allowing adjustment of the constant in C n^{.98}. The main exponential here is why we used the coloring estimate in addition to ranks.□

Proof of Theorem 11.1.

We perform the singular-value induction. The preceding fourth-moment estimate has an error independent of the eventual Schatten exponent. We retain that property while summing the spectral bands; it lets the induction begin from any sufficiently large finite exponent without changing the cutoff in n. Suppose for the two smaller sizes the bound in (113) holds with p_0 (in place of p_*), where we can take the larger of the two parameters, always at least 2. We will show how along induction it suffices to increase this parameter by factors at most 1+O(1/\log n) for all sufficiently large sizes.

Take

with C_0 large enough, absolute. For each \lambda, we will bound a Schatten trace of A B on the irreducible. Write X=A^* A, Y=B B^*. Lemma 2.6, applied on the irreducible block with A_2=A, A_1=B, P=2p and q=4, gives

Decompose in the subgroup algebras to bound the right side. For X, on each of the b column factors take the irreducible matrix-block decomposition and, within each irreducible, the eigenbasis of the corresponding factor of X, in order of decreasing eigenvalue. Group indices within this matrix-block into dyadic intervals [R,2R) truncated at its dimension (here R=1,2,4,\ldots). Each such interval gives a projection in that factor group algebra of regular rank

where m is the dimension of this smaller irreducible. Taking tensor products gives projections P as in (124) for H that sum to identity. By the smaller-size hypothesis, for each such choice

where the norm bound holds also after lifting to G. Indeed squared singular values from an interval on a factor are at most (m R)^{-1/p_0}; the interval length is at most R. The analogous decomposition of Y over row factors gives Q with \|Q Y^{p/4}\|_{\rm op}\le r_J^{-p/(4p_0)}.

The total number of pairs P,Q in these decompositions is at most

In fact per factor of size a or b, the number of partitions for its irreducibles is at most \exp(C\sqrt a) or \exp(C\sqrt b), and the number of dyadic intervals in each is at most polynomial in the factor size since dimensions are at most the factorial. The partition bound here is the standard elementary one; for example it follows by using s=1/\sqrt a and bounding the partition generating function at e^{-s} by \exp(C/s), using its product formula (and likewise with b).

Use the triangle inequality for Schatten 4-norm to sum terms on the right of (126), inserting these projections. For each P,Q, by (124), (127) and the ideal property of Schatten norm, we have, on \lambda,

with our choice of C_0. Now summing by (128) (triangle inequality before taking fourth powers) still gives by (126)

where C_1 is absolute. The placement of the Schatten powers in this proof means we do not have a loss from summing norm bounds raised later to a possibly very large p.

To use (129) and finish the induction, we record simple dimension bounds. For shapes of height exceeding n/2 the singular bound was automatic. For the rest with k=n-\lambda_1\ge n^{.99}, we have

for large n, with an absolute c>0. Here and later we can see this type of lower bound as follows. Transpose a partition if needed and let u be its first row length after taking the larger of width and height. If u<n/8, the hook lengths are at most 2u, so the dimension is at least (n/(2eu))^n by the hook formula. For u\ge n/8, put t=n-u. The hook formula gives at least

since we may drop the dimension (a factor at least 1) of the partition below that row, and the correction to row factorial uses log factors \log(1+c_j/(u-j+1)), where c_j counts cells below in column j. Indeed jc_j\le t, and

This proves the displayed correction, including the range in which the tail is not small. For n/8\le u\le n/2, (131) gives log dimension of order at least c' n. For u>n/2 under our height restriction before transposition, u=\lambda_1, so t=k; (130) follows using (131) and \binom{n}{t}\ge (n/t)^t.

Hence in this dense case (129) yields

where we can take p'=p(1+C_2/\log n) for a suitable absolute C_2 and sufficiently large n, by (130).

For 1\le k\le n^{.99}, (114) suffices, with a fixed absolute induction parameter, since D_\lambda i\le n^{2k} using occurrence on tuples and i\le D_\lambda. And for k=0 the induction bound just says 1\le 1. This completes the bounds used in the induction step.

To formalize uniformity, use a fixed threshold for sufficiently large sizes, and below that threshold take a common finite induction parameter making the singular inequality true. This is possible by the strict finite-size gap in Lemma 2.2. Enlarge this starting parameter if necessary to be at least 2 and to handle the fixed parameter from (114). For n=2^d above threshold, by the step just proved the desired parameter need only multiply the larger child parameter (children of bit lengths \lfloor d/2\rfloor,\lceil d/2\rceil) by at most 1+C/d, changing absolute constants. Their product is uniformly bounded by Lemma 4.3 with \gamma=1. Thus an absolute p_* works for all sizes. This proves (113).□

Proof.

Write the ordinary group algebra coefficients of the projections as p(h),w(y) on H,J, so their sums give the operators without a uniform-measure prefactor. Lemma 3.3, applied to the local projections in this normalization, bounds \|P_HP_J\|_{4,\mathrm{reg}(G)}^4 by

The condition has a useful description. In the grid of middle positions in a product hy, the column permutation step leading up to a middle position gives a source-row symbol, and the row permutation step from it gives a target-column symbol. Thus there is one column symbol at each cell (i,b), with these symbols a permutation of [m] along each row i; and there is one row symbol there, a permutation of [q] along each column b. The condition is that the pairs of symbols cover the m q=n possibilities once each. In fact, to go back by another product in HJ, each target column must send the ending row indices to the prescribed source rows by a permutation, which requires and, for this part, is ensured by this pair condition. Then within any resulting source row we get the prescribed permutation to restore the source columns as well.

The same lemma normalizes the squared line coefficients as independent probability laws whose densities relative to uniform are bounded by the local regular ranks. Consequently (137) is at most

where permutations across rows and columns are independent with tilted laws, each having density against uniform bounded by the local regular rank (we can use its upper bound; the laws come from the normalized squares). Inverses of permutations in setting up the array of symbols are immaterial.

Here is the needed estimate for the probability. Suppose it is positive, and consider the law of the entire array conditioned on pair covering; in the entropy argument this law already includes the tilts. Let \mathcal E denote entropy, using X for the array; let X_i denote the vector of column symbols along row i, and Y_b the vector of row symbols down column b. For a density against uniform, its expected log at any law is bounded above by that law’s relative entropy against uniform. It is also bounded above by the log of the sup of the density. Using weights 1-\epsilon,\epsilon on these two bounds, writing the log of the probability from (138) by entropy of the conditioned law gives

We bound the entropy difference here by exposing cells in random order. The following details, in particular keeping the marginal entropies, help make the rank power loss in (136) small. Give every cell an independent uniform [0,1] priority, exposing in decreasing order. At cell e=(i,b), for given order, use the conditional distributions

• •

  u of its column symbol given just the previous column symbols along row i;

• •

  v of its row symbol given just the previous row symbols along column b.

These are for the marginal laws appearing in (139). They are supported on at most M_e,Q_e choices respectively, the counts not already used in that row or column, including the current symbol. By the entropy chain rule and the variational bound for log sums, the contribution in the entropy difference from exposing this cell is at most the expectation of

where we also require that the pair has not been used in any previous cell. Indeed the conditional array law uses only available possibilities, and the negative marginal entropy contributions are computed exactly by averaging logs of u,v.

The unrestricted sum divided by (M_e Q_e)^\epsilon is at most 1. Condition on the full array assignment, the priority x of cell e, and priorities in its row or column. The distributions u,v depend, given the assignment, only on the respective in-row, in-column previous data; they do not depend on the remaining priorities. Take the cell owning each pair in this full assignment. Owners outside row i and column b leave their pair still unused with probability x. The contribution of owners inside row i to the normalized sum is at most Q_e^{-\epsilon}, since each c has only one such pair there. That of owners in column b is at most M_e^{-\epsilon}. Therefore Jensen bounds the conditional expectation of (140) minus \epsilon\log(M_e Q_e) by

We can always replace a positive bound on this difference by 0.

Averaging this last estimate gives, uniformly as n gets large, at most

To see this, when x\ge x_0=\exp(-L^{2/3}), except with probability smaller than \exp(-n^{c_0}) for some c_0>0, both remaining counts are at least n^{1/5}, by usual binomial bounds. Thus on the range x\ge x_0 the result follows by comparison with the integral of \log x, since 2\exp(-L^{4/5}/5) is sufficiently small; the negligible binomial error can use the bound 0, as can x<x_0, with the missing integral there of order x_0(1+|\log x_0|).

Summing (140), the terms \epsilon\log(M_e Q_e) sum to \epsilon\log(|H||J|) in any order. We obtain from (139)

Finally n!/(|H||J|)\le \exp(n+O(\log n)) by factorial estimates. This proves (136).□

Proof.

We first identify the harmonic part through the spectrum of coordinate deletion, then bound the lifting loss uniformly over the full range 0\le t\le M.

The tuple representation is that on cosets of S_{M-t}, with commuting slot action. Multiplicity space for \mu is given, up to dual convention, by the S_{M-t}-invariants, and under the slot group S_t it has types \nu\vdash t with \mu/\nu a horizontal strip of size s=M-t, by Pieri, each once. This in particular requires j\le t. Let Q_t be the sum of projections ignoring one slot, over the t slots. It acts within \mu,\nu with eigenvalue

where \mathrm{ct} is the content sum. In fact in the coset model each projection averages the identity and swapping the slot with any of the s unused ones; the cross-transposition sum in Q_t is the full transposition sum minus those of the two sets of slots.

For strip columns c, using one-based column numbers, put

Then (141) is at least

since the contribution to the content difference in each such column is c-\mu'_c, and the total excess of heights over 1 is j. Thus Q_t>0 on the indicated components with t>j. When j=t, the shape does not occur if we drop a slot, and here the strip removes one box in every column so the multiplicity is D_{\bar\mu}. This proves the statement about harmonic functions (also immediate at t=0).

Within shape \mu in \mathcal I_{M,u}, let L_S be the isometric lift from the slots in S, and put

Here j\le u\le t, and \mathcal A_j=I. For u>j, let L_i lift from all slots except i, and let \mathcal A_{u-1}^{(i)} be the corresponding operator on those slots. Each j-subset omits exactly u-j slots, so

All lifts preserve the label type \mu. Thus a_u is bounded below by a_{u-1} times the minimum of (141) at slot count u, divided by u-j. We show that the product of these lower factors, capped at 1 if desired, is at least \exp(-Ct).

Here is the product check. Shape \mu stays fixed. Write w=M-j, the width, and at a slot count u with j<u\le t, write s_u=M-u, l=u-j=w-s_u. By (142), the lower factor is at least

taking the worst allowable strip, now of size s_u. If t<M/4, the last band of columns of \mu, of height 1, has length b\ge M-2j. In any band of equal height removed columns must form a suffix. Thus the sum of the l unremoved column numbers is at most the sum from taking the first l columns of the last band (using l\le b). Consequently

The product therefore loses at most a constant to the power t.

If t\ge M/4, we bound the total log loss by O(M)=O(t). View each size s_u as a cut after column s_u, and let b_r be the band lengths, indexed by height r. If a cut lies inside a band, let v be its distance to the nearer boundary; at a boundary put v=0. Compare a permissible strip with the first s_u columns. The number h of missed columns before the cut equals the number of selected columns after it. Within the band the selected columns form a suffix, so either all columns before the cut are missed or all columns after it are selected. Hence h\ge v. Even the cheapest exchange of h columns across the cut increases the column sum by h^2, giving

A bound for the logarithmic loss in (143) is therefore

Summing within each band, including its endpoints, gives O(\sum_r b_r\log(eM/b_r)) by a factorial estimate. To bound this sum, put \pi_r=b_r/w. This probability distribution on positive heights has mean M/w. Comparison with the geometric law of that mean gives its entropy \mathcal E(\pi)=-\sum_r\pi_r\log\pi_r\le\log(eM/w). Therefore

Since M\le4t, the product has the required lower bound \exp(-Ct).

Let \mathcal L add the lifts from the direct sum of the j-slot spaces to the t-slot space, within shape \mu. Then \mathcal L\mathcal L^*=\mathcal A_t, so \mathcal L^*\mathcal A_t^{-1} selects coefficients linearly, with squared norm at most a_t^{-1}\le\exp(Ct). This map is label-equivariant and hence preserves the image of every group algebra projection on the shape. This proves the lifting facts.□

Proof.

Consider the harmonic representation in \mathcal I_{n,k}. It contains D_{\bar\lambda} copies of \lambda, so suffices for getting the estimate with this multiplicity taken into account. Both projections preserve this representation. We estimate their angle operator: that between their ranges, with entries given by inner product, whose singular values are those for the product apart from zeros.

Tuples will have row and column vectors a=(a_i)_{i=1}^k, b=(b_i)_{i=1}^k respectively, and put D(a,b)=1 if the cells are distinct and 0 otherwise. We compare norms and probabilities to the model with a,b independent uniform, including across slots (called iid sampling below). Within row r suppose the specified shape of P_H is \mu_r, of deficit j_r, with local projection rank l_r^* in that shape. Fixing a, let t_r be the number of slots in row r. On a tuple fiber with this assignment the row group acts just on the corresponding injection of t_r columns. For P_H to be nonzero here we need j_r\le t_r; in particular we can assume

(and analogously in columns).

For f in the harmonic representation in the range of P_H, we can therefore expand on distinct tuples into lifts of the form

indexed by sets S of slots of size \sum_r j_r. Each term only uses assignments a whose restriction a_S has exactly j_r slots in each row; outside such assignments take it as zero. As a function of b_S, it uses the projection range on the respective j_r fine slots over each row, in the corresponding shape there. In particular that range, taking all these rows together and extending by zero off distinct column values in the same row among the indicated slots, is a space W(a_S) of rank

We will give this fine-slot space the iid b_S norm. It depends only on the assignments a_S. It is the natural relabeling to those slots of a tensor product of row spaces, each invariant under slot permutations there (group algebra on positions commutes with slot permutations).

The expansion (146) follows by the injection lifting fact, used given the row assignment, with the coefficient maps tensored within that assignment. Ranging over assignments and using iid norms, the terms are obtained linearly with

For this, conditional tuple measure on a possible assignment gives independent uniform injections over the row fibers, and assignment weights are comparable to uniform iid weights up to \exp(Ck) on possible assignments: the ratio is given by the falling factorials within rows and the overall one, so we can use (135). We use zero on impossible assignments; extension by zero for the fine-slot functions also respects the norm bound. The product of the lifting bounds over all rows costs only \exp(C\sum_r t_r)=\exp(Ck).

Similarly expand harmonic g in the range of P_J into lifts

where, using letters c for columns, column shapes are \gamma_c of deficits d_c^* and T has \sum_c d_c^*\le k slots. Required b_T assignments use these counts. The analogous fine-slot space W'(b_T) has rank T_J\le R_J/\prod_c B_{\gamma_c}.

We now express the overlap through the coefficient spaces of these expansions. For each S, let \mathcal H_S consist of functions F(a,b_S) whose fine section lies in W(a_S), with zero values unless a_S has the required row counts. Give it the norm

under iid sampling. Define \mathcal K_T analogously for E(b,a_T) with fine sections in W'(b_T). Outside the marked slots, the coarse assignments are unrestricted. Orthonormal fine-slot bases identify these norms with Euclidean coefficient norms averaged over the coarse vectors.

Let A_Sf=F_S and B_Tg=G_T be the linear coefficient selections above, on the harmonic ranges of P_H and P_J, respectively. Equation (148) and its column analogue give

Their individual operator norms are therefore at most e^{Ck}, after adjusting the constant.

Write \mathsf C_U=\prod_{i\in U}(\mathrm{Id}-\mathbb E_{b_i}). The zero extension of harmonic f is centered in every whole cell-slot under iid sampling. Against it, we may first center each G_T(b,a_T) in the slots outside T. Since G_T is independent of a_i there, this applies exactly \mathsf C_{[k]\setminus T}. Now expand f on distinct tuples. For each S,T, put

The independence of F_S from b_I and self-adjointness of centering give

The remaining centering acts only on coarse coordinates outside T. It is a contraction on \mathcal K_T and leaves W'(b_T) unchanged.

Define \mathcal M_{S,T}:\mathcal K_T\to\mathcal H_S, abbreviated to \mathcal M when the pair is fixed, by

In orthonormal fine-slot bases, its kernel entries from coarse b to coarse a are C_I(a,b) times the conjugate and unconjugated fine basis evaluations at b_S,a_T. With c_k=n^k/(n)_k, the angle operator between the two harmonic projection ranges is therefore

Here c_k\le e^{Ck}, and there are at most 4^k pairs S,T.

The purpose of the two norm estimates below is the inequality

The residual slots will supply a factor (k/n)^{i_0/2} in each squared norm. Counting the marked slots will supply the remaining factor (k/n)^{|S\cup T|} in the Hilbert–Schmidt estimate, together with R_HR_J. Since i_0+|S\cup T|=k, their product gives (k/n)^k. Finally, the D_{\bar\lambda} copies of \lambda in the harmonic representation convert this estimate to the D_\lambda denominator in (144). All coefficient maps and subset sums will cost only \exp(Ck).

First, with \delta=k/n, uniformly given the values in all marked slots S\cup T, there is the residual estimate

For clarity, expand the centering operators using independent alternatives to b_i,\ i\in I. In the alternating differences, if a slot i\in I cannot create a duplicate cell with some other slot (allowing the displayed and alternative values in any slots with alternatives), the difference sum is zero. The squared quantity can thus be bounded with a factor at most 4^k by the probability of the potential-duplicate coverage event, using also Jensen over alternatives. The residual slots are sampled independently, with their alternatives (same row in the two values for the slot). In the collision graph every one of these slots must be incident to an edge. To bound the probability, in components with a connection to a marked slot use edges of a forest leading to marked roots, and in other components use a forest leading to a free root; there are at least two slots in any free component. If the number of edges chosen is e, then e\ge i_0/2. The choices are bounded by 2^{O(k)}k^e, for example by giving nonroots parents. Ordered from the roots, edge conditions each have probability at most 4/n for a new slot, since each allowed cell-value version in it is uniform. A union bound proves (152), also when the desired estimate is loose because \delta is not small.

Fix all marked cell values. In the residual variables, F depends only on a_I and E only on b_I, so

Apply (152), then average over the marked values and use Cauchy–Schwarz once more. The resulting norms are exactly \|F\|_{\mathcal H_S} and \|E\|_{\mathcal K_T}, since marked coordinates absent from a function integrate out. Hence

The full Hilbert-Schmidt bound takes more accounting for marks. In a normalized finite sampling measure it is the expected squared kernel size (sum of squared entries in the bases), thus uses

where U,V are the sums of squared basis evaluations of the fine-slot spaces, set to zero at assignments not having the required counts. After integrating out residual slots we are bounded using (152), leaving the expectation involving just U,V.

Write

We evaluate this expectation by fixing the a_S,b_T assignments and averaging the fine evaluations in the non-overlap coordinates b_{S\setminus T}, a_{T\setminus S}. Suppose the counts of the overlap slots in those assignments are h_r\le j_r in rows and v_c\le d_c^* in columns. The numbers of non-overlap assignments, given overlap assignments, are

The averaged U value is T_H m^z times the probability of the evaluation values b_O in a probability distribution on those slots. Indeed U/T_H is a probability density on b_S against iid measure. Moreover this is a product over rows, supported on distinct values per row before and after marginalization, with the overlap distribution permutation invariant within each row. And per row it is always the same distribution up to slot naming for the given h_r, regardless of which overlap slots were assigned or how the assignment was extended to the non-overlap slots. These properties follow from the tensor description and slot invariance of the spaces giving sums of squared basis evaluations. Similarly the averaged V is T_J q^z times a probability of a_O, with the analogous properties over columns.

In summing over overlap assignments a_O,b_O at fixed counts h_r,v_c, the sum of products of these two probabilities is at most

To verify this, each contributing overlap with positive products forms a simple bipartite graph between the rows and columns with edges labeled by overlap slots: no repeated cell is allowed by the supports. A given simple graph with these degrees has z! labelings. The row-side probability of the ordered column values is the probability of the corresponding unordered neighbor choices independently by rows, divided by \prod h_r!; likewise on the other side. Summing products of the unordered probabilities over such graphs costs at most 1.

The normalization for a_S,b_T is q^{-(x+z)}m^{-(y+z)}, which with the m^z q^z above leaves q^{-x}m^{-y}. Thus (154), after all averaging, is bounded by a sum over overlap counts h_r,v_c using terms at most

There are at most \exp(Ck) count choices, using (145). Use (147) and its analogue, with B_{\mu_r}\ge \exp(-Cj_r)m^{j_r}/j_r! by (134), (135), and likewise in columns. Since \sum j_r=x+z,\ \sum d_c^*=y+z, (157) shows

Here x! y! z!\le k^{x+y+z}, and the split factorials within rows or columns versus their combined factorials only cost \exp(Ck).

Now (153), (158) give

Apply the Schatten ideal and triangle inequalities to (151). The coefficient-map bounds, centering contractions, injection normalization and at most 4^k pairs give

This bounds the angle operator in the harmonic representation, which contains D_{\bar\lambda} copies of \lambda. Since D_\lambda/D_{\bar\lambda}\le(en/k)^k by (134), division by that multiplicity proves (144).□

Proof.

We prove this on the harmonic part of \mathcal I_{n,k}. Use distinct input and output tuples \xi,\zeta. Given them a card has a unique required path through the sweep (it changes each bit to the output value when that bit is handled). For A\subseteq[k] write p_A for the probability the cards in A get the required outputs, and r_A=n^{|A|}p_A. These probabilities are just obtained by imposing switch outcomes along paths. Two paths can pose conditions on a common switch only if they use the same switch in some layer. Call such paths adjacent, also when the needed outcomes may conflict. When the demands are compatible, the card paths being used cannot occupy the same wire at a time, and there is a factor of 2 in r_A for each shared switch, with no more than two cards sharing; a pair of cards in a compatible routing shares at most once (once they take opposite outputs on a switch, they stay different in that bit).

The centered kernel

can be used instead of r_{[k]} on harmonic functions of \zeta, since dropped-slot terms integrate to zero. This is for the slot transition forward on cards, acting on functions by output averaging (using an adjoint convention if necessary). The kernel r_{[k]} itself is the transition kernel against uniform on injections up to the factor from n^k versus (n)_k. Thus for (159) it is enough to bound the Hilbert-Schmidt norm from (160), ignoring such a factor or allowing \exp(Ck). The centered kernel is zero unless every slot’s path is adjacent to some other: isolated slots give cancellation since their normalized path factor is 1 and independent of the conditions on others.

It remains to bound the integrals of r_A^2 on this coverage event for each A, since this controls the squared norm up to \exp(Ck). We can do the integral against iid inputs and outputs restricted to distinct tuples, at cost \exp(Ck) by (135). One power of r_A gives a sampling using actual routed paths for the slots in A: take a random full routing (choose all switches), and sample those input cards uniformly without replacement. Indeed under this sampling outputs for those cards have the probability p_A given their distinct inputs. Other slots can still just use iid input and output samples, ignoring distinctness for upper bounds. The factors from these measure comparisons can again be allowed as \exp(Ck). In this setting the remaining weight r_A on distinct tuples just counts factors 2 as above. Condition on the full routing. For probability bounds on constraints involving sampled paths, the actual routed paths can also be compared to sampling from them with replacement with a factor \exp(Ck), still evaluating any weight bound for distinct samples.

There are two useful observations here:

Conditional path adjacency. Given a path of either type (from the actual full routing or from independent endpoints), a new independent choice of a path of either type, using with-replacement sampling conditional on the full routing, has probability at most 2\log_2(n)/n to be adjacent to it. Per switch of the given path there are only two paths in the full routing using that switch, and for independently sampled endpoints the path goes through a uniform position at any fixed layer.

Shared-switch count. For any b distinct members of a full routing the number of switches shared within that set is at most (b/2)\log_2 b. Indeed split inputs into halves according to the last bit handled in the sweep. Within halves before the last layer use induction, and for the last layer cross edges add at most the smaller half-count within the set. The bound follows since the binary entropy at any proportion is at least twice the smaller proportion.

For each component of the path adjacency graph of size b' the weight r_A therefore uses at most a factor (b')^{b'/2}, using observation 2 on actual slots. On the coverage event all components have size at least two. Use spanning forests of these components to bound the probabilities: with l total tree edges they can be counted with a bound 2^{O(k)} k^l by orienting toward roots, and for any one forest the edge requirements cost probability at most (2\log_2(n)/n)^l, by observation 1 under with-replacement sampling. Here we may sum by forests describing the exact components from the event for which the weight bound is used, and just drop non-edge constraints for the probability upper bound.

These give a power saving n^{-c' k} even with the weights for components and all \exp(Ck) factors. Explicitly 2k\log_2(n)/n\le n^{-0.47} for n large. In a component of size 2 we use one such factor and weight at most 2; in one of size b'\ge 3 we use b'-1 such factors, and weight bounded by n^{0.255 b'}. This comparison applies uniformly in the forest count bound (multiply the maximum of each bound with l edges by the number of such forests). It proves the required Hilbert-Schmidt estimate and hence (159).□

Proof of Theorem 12.1.

We now combine the estimates. We only need to give the large-n induction step, with some absolute threshold for it chosen large enough throughout.

As before set L=\log n. We organize the cases as follows apart from (133):

• •

  Very small deficits as in (159) can already use (132) with any sufficiently small absolute a>0, since, for example, D_\lambda\le n^k by occurring in the tuple representation.

• •

  For remaining shapes with k\le n\exp(-L^{1/4}) use the sparse-deficit overlap estimate (144). Here k>n^{0.51}, and

by (134).

• •

  For the other shapes not killed by (133), we can use the regular trace overlap estimate (136); we have

To justify the last dimension assertion, we give the elementary checks. If \max(\lambda_1,\lambda'_1)< n/(4e), the hook bound gives exponential dimension since hook lengths are less than n/(2e). Otherwise take width w\ge n/(4e) using one of the shape or its transpose. If the number of remaining boxes is at least \lfloor w/8\rfloor, we may just keep the full width and that many more boxes in a subshape; dimension is nondecreasing under adding boxes of a shape, and (134) gives exponential dimension for the subshape. The case with fewer than that many remaining boxes in the transposed orientation would be killed by (133). With fewer in the original orientation we again get the claimed lower bound from (134) when k> n\exp(-L^{1/4}). This proves (162).

Suppose (132) holds for the smaller sizes m,q with exponents at least a_*, where without loss a_*\le 1/8. In any row factor take its matrix singular decomposition in each shape, and similarly in columns. We need the bases meeting in multiplying across the two factors of T_n. That is, removing outside unitaries, we bound singular values of the product of positive factors, using on one side left singular projections of its component operators and on the other right singular projections. This can all be done in the respective group algebras and then taken inside shape \lambda, by ordinary group Fourier decomposition (the polar unitaries can be completed on nullspaces). Equivalently, in restriction of \lambda to the product subgroup, each component operator acts on its own irreducible by the corresponding matrix with identity on multiplicities.

In each component group and shape \mu, group singular indices into dyadic blocks from r_0 through at most 2r_0-1, r_0 a power of 2. Use the projections onto these blocks in the meeting bases just described. Take R=D_\mu r_0 as upper bound of regular rank in our estimates. Thus on the two sides we have orthogonal decompositions by the P_H,P_J, respectively, with the regular rank product bounds R_H,R_J; and the positive singular-value factors can use eigenvalue upper bounds

on the respective blocks. In fact for purposes of bounding any singular value of the product we can replace the factors by the indicated weights: individually the singular-value factors are then the weighted projection sums times commuting contractions, which can be taken to the outsides.

In shape \lambda consider the analytic matrix product of projection sums with weights, in the product order needed, i.e. of

Use either overlap estimate, with \beta chosen according to it:

• •

  For shapes using (136), \beta=(1+\epsilon)/4. On the line \operatorname{Re} z=1, Schatten 4 norm of the product is bounded by

Indeed expand in projection pairs and use the triangle inequality and (136), with regular trace paying for D_\lambda copies. The number of pairs can be absorbed with the additive O(n^{4/5}) in the exponent. For a group of size-parameter M=m or q, there are just \exp(O(\sqrt M)) shapes and at most O(M\log M) dyad choices for each. We use here the usual partition count bound, also seen directly by using \exp(-1/\sqrt M) as argument in the partition generating function \prod_{i\ge 1}(1-x^i)^{-1}, whose log at this argument is O(\sqrt M).

• •

  For shapes using (144) in the sparse range, take \beta=1/4, and (165) holds instead with exponent

Here (145) on both sides is necessary for nonzero terms, by restriction in the tuple calculation. Vectors of local deficits summing to at most k have at most \exp(O(k)) choices since k>n^{0.51} exceeds both m,q for large n. For positive deficit j, shape choices cost at most 2^j, and dyad choices at most O(j\log n) by the dimension bound n^j; for zero deficit there is just the trivial rank and shape. So the claimed exponent absorbs the number of terms and (144)’s losses.

On \operatorname{Re} z=0, (164) gives operator norm at most 1 with no counting, by orthogonality within each of the two projection sums. We interpolate the whole product, which in particular allows counting costs in (165) to be scaled by the interpolation parameter. By standard three-lines Schatten interpolation (between operator norm and Schatten 4), at parameter

we obtain the bound (165), raised to power \theta, in Schatten 4/\theta. The dual-matrix three-lines argument is the one given in the proof of Lemma 2.6; here its analytic family is the full product (164).

This parameter gives just the weights (163), so ranking the resulting singular values at the root shows

Use (162) in the case using (136), or (161) in the case using (144). With an absolute C, say we conclude for all sufficiently large n the desired bound (132) at the root with exponent at least

provided we keep initial exponents small enough to allow the very small deficits as well. Crucially the choice of large-size threshold in these comparisons of exponents can be absolute and independent of how small a_* might be.

Finally these induction steps give (132) with uniform positive exponent. Choose a large absolute base threshold, also large enough that the factors in (167) are positive and, say, at least 1/2. At or below the threshold, Lemma 2.2 gives (132) with a common positive exponent, chosen small enough for the very small deficits. Lemma 4.3, with \gamma=1/10, then bounds the product of the losses in (167) away from zero. This proves (132).□

Proof. Use the representation on k distinguished cards, that is, on tuples of distinct positions. The representation in (170) occurs here and does not occur for k-1 cards. Thus we need only work on the space orthogonal to functions dropping at least one coordinate. Write x,y for input and output tuples, P(x,y) for the sweep kernel on the tuples and P_I for the marginals on subtuples indexed by I\subset[k]. The kernel, between these orthogonal-complement spaces with counting measure, can be replaced by

Paths in the sweep between specified endpoints are unique. Draw the k paths and put an interaction between two indices if their paths use any common two-way gate, irrespective of feasibility. If there is an isolated index, D=0: in every term that index if included multiplies path probability independently by 1/N.

Here are bounds for the absolute kernel thus obtained. Put p=k/N. For distinct input tuple x write r(x_i,x_j)\in[1,d] for the largest coordinate in which the two positions differ. Call x good if, except at fewer than k/20 of the indices,

On a good input row x, fix I\subseteq[k] and sample the nonnegative kernel P_I N^{-(k-|I|)} before restricting the outputs to be distinct. The labels in I use one common switch field; the other labels use independent fair bits. Let \Gamma be the event that their complete path interaction graph has no isolated vertex. We prove

uniformly in I. Restricting the final tuple to be injective can only decrease this row sum.

First fix an order in which to reveal the full paths. Given the paths already exposed, the switch coins used by the exposed labels in I are fixed, and all other switch coins remain independent and fair. This follows directly from the path specification: it prescribes a value for each visited switch, and imposes no condition on any other switch. The exposed independent walkers prescribe only their own private bits. Explore the next path i until it first reaches a switch visited by an exposed path. Before that time, its updated bits are fresh fair bits, whether i uses the common field or private bits.

For an earlier path j, the two paths cannot share a switch before r(x_i,x_j): a higher unupdated bit still separates them. At time t\ge r(x_i,x_j), reaching that path’s switch requires one specified prefix of t-1 updated bits. The event that this is a first encounter is a subset of that prefix event in the stopped exploration. Its conditional probability is therefore at most 2^{-(t-1)}. We have not conditioned on avoiding the earlier switches; that avoidance remains part of the event being bounded. A union bound gives

For every index satisfying (171), this is at most p^{1/8}. Thus these encounter indicators have a uniform conditional upper bound in every fixed revelation order.

Now choose the revelation order uniformly, independently of the sampled paths. In any fixed graph without isolated vertices, each vertex has an earlier neighbor with probability at least 1/2. The number A of vertices with an earlier neighbor therefore has mean at least k/2 and is at most k. It follows that \Pr\{A\ge k/4\}\ge1/3. On a good row fewer than k/20 indices violate (171); hence, with this probability over the order, at least k/6 indices satisfying that inequality meet an earlier path.

For a fixed order and any prescribed set of h such indices, successive conditioning in revelation order bounds the probability that all their encounters occur by p^{h/8}. Take h=\lceil k/6\rceil and sum over the at most 2^k possible sets. Averaging the order and using the preceding 1/3 bound gives

for sufficiently large N, since p\le N^{-\delta}. This proves the required good-row estimate. The backward occupation estimate below will supply the corresponding column bound on the exceptional input rows.

For the bad rows we give the corresponding small bound on column sum, even without requiring any interactions. Running any of the I-processes backwards from the column tuple y, the probability that any specified set of h distinct input sites are all occupied among the k paths is at most p^h. Apply Lemma 11.2 to singleton sets, using |I| jointly switched cards and k-|I| independent walkers in the reverse coordinate order. The bound counts all endpoints before restriction to distinct input tuples, so it remains an upper bound for the restricted kernel.

We include details that, on distinct input sites, having too many violations of (171) has probability at most p^{c_2 k} under this bound. Dyadic boxes of size 2^r consist of vectors agreeing in coordinates above r. Every violating site is in some such box with occupancy h\ge 2 and with

Take maximal such boxes. If a bad row is produced, they are disjoint and together witness total occupancy q\ge k/20. For l\le q/2 boxes with sizes a_i=2^{r_i}, occupancies h_i, sum q, union bound over occupied sites costs at most the sum, with box lists counted unordered, of

Thus summing ordered specifications of sizes and occupancies we divide by l!. Using a_i/h_i\le 8d p^{-1/8}, the site-cost sum at fixed q,l is at most

In the last bound we used N=k/p,\ k^l/l!\le \exp(O(q)) in this range. This proves the stated bad-row probability with room to spare.

The terms of the absolute bound on D have row and column sums trivially at most 1 (per term); on good rows with required interactions, or on columns when keeping just the bad rows, we have the small bounds on one of these two sums. Therefore the matrix norm is at most 2^{k+1}p^{c_3 k}, with fixed c_3>0, by the row/column test. This proves (170).□

Proof. Let q_K,q_L be the coefficient densities of the two projections on their own groups. Their squared masses are R,S. Lemma 3.3, in its projection case, gives

where now k,l are drawn independently with densities |q_K|^2/R,\ |q_L|^2/S. The n column permutations in l are independent with individual densities at most their projection ranks S_v, \prod S_v=S.

For clarity, using row moves followed by column moves to describe compatibility, fix k. It gives a bipartite multigraph from old to new columns, with one edge per row at each column: how the card in that row moves to a new column. Degree is m. The permutations in l assign colors (new rows) to edges at the new-column vertices, giving each color once there. Compatibility is exactly that each color also appears once at each old-column vertex. Indeed this permits performing the two moves in the opposite order, coloring at old columns and then moving within the new rows. Other composition conventions give the same estimate with harmless inversions.

We will need the following entropy bound. Take any distribution Y on proper such colorings (each-side requirement), writing Y_v for the incident permutation at each new-column vertex. Write D_v=\log(m!)-H(Y_v), using nats. Put u=\log m,\ L_*=\exp(\sqrt{u}), calling edge bundles (parallel sets) bad if their size exceeds L_*; let b_* be the number of edges in bad bundles. For sufficiently large sizes the total correlation satisfies

We give details to get power-saving error along with the small coefficient of the deficits.

Order the edges within a vertex v with bundles contiguous, and compare revealing its permutation alone versus revealing after previously exposed vertices in a uniform random order of vertices given by iid [0,1] priorities. For an edge e=(v,w) let a be the number of remaining colors when it is revealed locally, P its conditional law given the earlier local colors. Put d_e=D(P\|\mathrm{unif}_a) (random from these earlier colors), so \sum_{e\text{ at }v}\mathbb E d_e=D_v. The entropy gap in (174) sums the conditional entropy drops on knowing the earlier vertices, which equal expected conditional relative entropies to these P’s. The global conditional law has to avoid colors used by earlier vertices at w; hence the drop is at least the expectation of minus log of the P-mass available after this exclusion. Condition to evaluate this latter expectation on the entire actual coloring and on priority z of v, and use Jensen on other priorities. Any color at w whose edge there is from a different vertex is excluded with probability z, giving at least

with continuous endpoint conventions. The cost lost here is at most 1. Discard the bad bundles, and also each good bundle meeting the last \lceil m^{.8}\rceil edges at its vertex. The latter removal costs at most O(m^{.8}+L_*) edges per vertex and leaves at least m^{.8} colors at every edge of each retained bundle. We bound the loss for each other edge in a good bundle as follows.

Call colors heavy for P if P(c)>m^{-.3}. If heavy mass is T, we have

Indeed a\ge m^{.8}, and one may use D(P\|U)=\sum_i[P_i\log(aP_i)-P_i+1/a] with nonnegative summands. The contribution of light colors to t_e is at most L_*m^{-.3}. If T\ge L_*^{-5}, the bound t_e\le T+L_*m^{-.3}, monotonicity of F, and (175) show

For a good bundle, write \mathcal B for its edge set and put b=|\mathcal B|\le L_*. For a current edge e\in\mathcal B, let \mathcal F_e be the local history just before revealing it, and let a_e be the number of remaining colors. Write P_e for the current conditional law and T_e for its heavy mass. The heavy set H_e=\{c:P_e(c)>m^{-.3}\} is determined by \mathcal F_e and has size at most m^{.3}. If the heavy mass is less than L_*^{-5}, the loss is O(m^{-.1}) unless some still unrevealed edge f\in\mathcal B has color in H_e; on that event the loss is at most C L_*^{-4}.

Let P_{f|e} be the conditional law of the color of f given \mathcal F_e. The same entropy estimate used above gives

The histories are nested. Conditional entropy decreases between \mathcal F_e and \mathcal F_f, while contiguity of the bundle gives 0\le a_e-a_f\le L_*. Since the retained edges have a_f\ge m^{.8},

A union bound over the remaining edges and then a sum over current edges therefore charge each \mathbb E d_f at most L_* times. The small-heavy-mass losses satisfy

Here \mathrm{loss}_e denotes the bounded loss F(t_e) after the light-color error has been included in the displayed additive term. This proves the asserted small-heavy-mass contribution. Together with (176) and the discarded edges, it proves (174).

Consequently, for fixed k, under the possibly weighted column laws used in (173), we have

Indeed take the distribution conditioned on compatibility as Y in (174), if it has positive probability. Minus log of that probability is the relative entropy to the product column laws, equaling the total correlation plus sum of local relative entropies to the respective laws. Each D_v is bounded by the latter local relative entropy plus \log S_v.

It remains to average the bad-edge factor over k. Under uniform row permutations,

for a fixed c_4>0. To verify, we can choose bad cells in the table of old against new columns, each with h>L_* rows moving accordingly. For total q such prescriptions, assignment probabilities in the independent row permutations are at most (e/n)^q, by the falling factorial bound (or are zero). Lists of cell sizes summing to q can be counted with 2^q; choices of cells with factor at most (n^2)^{q/L_*}; choices of rows with factor at most (em/L_*)^q. Applying this also for the event b_*=q proves (178). Thus under weighted rows (density bounded by R), averaging \exp b_* costs at most \exp(O(1+\log R/\sqrt u)), by Hölder. Finally |G|/(|K||L|)\le\exp(N+O(\sqrt N\log N)) by factorial estimates. Equations (173), (177), (178) yield (172).□

Proof of Theorem 13.1. Fix thresholds with room between the preceding power exponents; we use

We show (169) by an induction with a small summable exponent loss. More precisely, there will be exponents c_N bounded away from zero, \le a_0=1/32 (and chosen sufficiently small absolutely), giving (169) at each size.

Split the bit list into halves as close as possible, forming the m-by-n array of (row, column), column bits those updated first. The sweep factors as independent row sweeps then independent column sweeps; their sizes meet the assumption of (172). Work in the regular representation of G. By singular/polar decompositions the singular numbers of T_N are those of E D, where D,E are positive semidefinite contractions: the output-side singular magnitude for the first factor, respectively the input-side singular magnitude for the second factor (with the unitary pieces on the outside removed). In particular, the operators D and E are induced from tensor products of such operators on the row subgroup and column subgroup, respectively.

Suppose we have child bounds (169) with common c'\le a_0, the smaller of our exponents available for m,n. To keep cutoffs in this proof independent of the possibly tiny size of c', first bound E^r D^r with

We will show, for x=\log j\ge X_N,

Decompose D,E into spectral bands, tensor factor by tensor factor. Here are useful conventions to accommodate repetitions and regular representation projections. Separately for each row or column site-group operator use a band per dyadic range of ending indices of distinct nonzero eigenvalues in its regular list, taking index 1 (the constant eigenvalue) by itself. Eigenvalue 1 is simple in such regular lists: attaining norm 1 in a sweep product of switch-averaging projections requires belonging to their common invariant space, and all cube-edge swaps together generate the symmetric group. If rank in one band is t, every eigenvalue in it is at most (t/2)^{-c'}, by the ending-index convention. The projections themselves are convolution operators, including for bands constructed this way. Take tensor combinations of bands over rows for D and over columns for E, obtaining projections Q_K,Q_L as in (172), of ranks R,S on the subgroups. Write y=\log(RS) in this paragraph and the next one (distinct from output tuples earlier). There are at most M=\exp(O(\sqrt N\log N)) pairs of tensor combinations, by e.g. counting dyadic bands. Thus E^r D^r is the sum of these pieces (ignoring zero eigenvalues). Each piece is, up to contractions on the outside, Q_L Q_K times a scale of at most

The fourth-power singular sum of Q_L Q_K on G is the trace (172).

To check (179), approximate each piece to error

in norm. It can be dropped if W\le\zeta; otherwise by (172) its necessary rank for this approximation is at most

In this second case

Including the sum over at most M pieces, the logarithm of the necessary rank is at most

To obtain the last inequality, use 1-4a_0>0 and substitute the upper bound on y. The errors are o(\epsilon_N x) because x\ge N^{.998} and a_0=1/32 is fixed. This gives a total rank less than j and proves (179). All large-size conditions here are independent of c'.

Lemma 2.8 transfers the powered estimate to the original positive product: for every j,

Hence (179), geometric averaging over first j (using trivial contraction on earlier indices), gives for x=\log j\ge2X_N

with an absolute C_0. For example, all but O(j e^{-\epsilon_N x/4}) of the indices up to j have log index at least (1-\epsilon_N/2)x and are covered by (179).

The induction now controls all indices whose logarithm is at least 2X_N. We still have to control the beginning of the regular list. Multiplicity forces a large irreducible block to reach the range just handled. The remaining small-dimensional blocks have a long first row or column, where the sparse estimate or annihilation applies. Any singular value on an irrep of dimension f occurs with multiplicity at least f. Thus irreps with f\ge\exp(2X_N) can always have their singular values tested by (180) at least at that threshold, even for values contributing to the start of the regular list. Smaller dimensions come only from shapes near row or column, and (170) (or vanishing) handles these.

Here are details of these statements about smaller dimensions. For sufficiently large N, if dimension <\exp(2X_N), either first row or first column has length N-k with k\le N^{.999}. Indeed if longest length out of both is less than N/10, the hook formula already gives dimension exponentially large in N. Otherwise put a length at least N/10 first as a row, transposing if needed. If at least \lfloor N^{.999}\rfloor boxes are left in the tail, take a subdiagram retaining exactly that many in the tail and the same first row; its dimension is a lower bound. Writing row length l, new tail size a, the hook formula gives at least \binom{l+a}{a}\exp(-O(a/(l-a))): tail hook lengths give at least dimension 1 there, and the first-row hook additions are on the first a (leftmost) boxes with total addition a, giving the correction displayed relative to l!. This suffices. These arguments use equality of dimensions on transposing. If first column has length N-k in that range, the switches annihilate the representation: there are no invariants on the matching subgroup of one layer, since the partition does not dominate the content (2,2,\ldots,2), by Young’s rule (take N large here). Shapes with first row N-k, 1\le k\le N^{.999}, are covered by (170). The constant shape contributes just the singular number at 1.

For 2\le j with x=\log j<2X_N, take the exponent c''=c'(1-C_1\epsilon_N), with C_1\ge C_0. Irreps of dimension with log at least 2X_N have norm at most \exp(-c'' x), by (180) with their multiplicity (ceiling/real thresholds can equivalently use integer indices). It suffices to count singular values exceeding this test among row shapes of smaller dimensions. Those levels would require by (170) 1\le k < c'' x/(b\log N). The total dimension in the regular list of nonconstant shapes through any such level k is at most N^{4k}, say, just by occurrence in tuple representations or dimension bounds and counting shapes. Taking our exponents restricted once for all to less than b/16, the number exceeding the test including the trivial value is then less than j (if the range of levels is empty just use 1<j). So (169) holds at all indices with c''.

This proves the induction step, with conditions that N be larger than an absolute cutoff and exponent loss by a factor 1-C_1\epsilon_N. We emphasize that no cutoff for the array or spectral-band estimates was dependent on the choice of starting exponent in this induction. For finitely many smaller powers of two there is a common positive starting exponent, as small as required, by simplicity of norm 1 noted above. We can take cutoff already large enough that loss factors used are at least 1/2. Lemma 4.3, with \gamma=1/4, bounds the product of the loss factors away from zero along every recursive branch. Thus the induction proves (169) as claimed.□

Proof. Apply the converse direction of Proposition 4.1 to (169), choosing a singular moment with nonconstant remainder at most 1/4. The forward direction then gives total variation at most 1/4 after an absolute number of sweeps. A sweep costs d physical steps, and Lemma 2.3 gives the matching-order lower bound.□

Proof. To prove this, first invert the permutations: hk\in KH if and only if k^{-1}h^{-1}\in HK. The latter event concerns a row move h^{-1} followed by a column move k^{-1}. Inversion preserves independence of the component laws and their supremum density bounds. We describe this event as a constraint on two arrays. For intermediate cell (i,t) (after h^{-1} and before k^{-1}), let J_i(t) be its column of origin and R_t(i) its row of destination. Thus J_i, i\in[l], are permutations of [m], and R_t, t\in[m], are permutations of [l]. Constraint (181) says that the pairs

are all distinct. Indeed this is necessary to be obtainable with a column layer first and a row layer second; if it holds, the column layer can first give every point its intended destination row, after which a row layer can give the intended columns. Here by row or column layer we mean a permutation in H or K, respectively. Call arrays satisfying the constraint valid.

The random-order exposure below is related to Radhakrishnan’s entropy proof of Brégman’s theorem [22] and its higher-dimensional development by Linial and Luria [13, Sections 2.2–3.2]. Here the conditional predictions need not be uniform: the estimate retains the component entropy deficits and separately charges concentrated entries.

Use now an arbitrary distribution \nu supported on valid arrays; entropies, denoted by \mathsf h, are in nats. Write D_\mathrm{u} for relative entropy to uniform on permutations (or product uniform when applied to a group of array components), using the marginal under \nu in this notation. We will show

Fix \eta=1/100, B=\lceil n^\eta\rceil, and write

There is an absolute c>0 (we can use c=\eta/4) such that

In fact, consider first independent uniform column permutations. A bundle consists of a row i, a row value r, and B columns, with a prescription that all those columns have R_t(i)=r. A disjoint family of bundles means the prescribed cells do not overlap. For any such family of size s, the probability of satisfying it is at most (e/l)^{Bs}. Indeed, each column with a cells specified gives either probability zero or 1/(l)_a, where (l)_a denotes a falling factorial, and (l)_a\ge (l/e)^a. For any outcome we can pack bundles it satisfies so as to have 2B times their number at least W: use disjoint bundles for each row and value with count at least B. Thus n^{c W} is at most the sum of n^{2cBs} over satisfied disjoint families, including the empty family. Its expectation under product uniform is bounded by

for large n, by m/l\le 2. This moment bound gives (184) by the relative entropy inequality (or changing measure and using Jensen’s inequality).

The bundle estimate charges repeated destination values to the joint entropy deficit of the column array. We now expose the row array to obtain one nat of compatibility saving per cell, except for these repetitions and for heavy conditional atoms.

We bound the conditional entropy for J given R by revealing its rows sequenced by independent uniform priorities in [0,1], independent of the arrays. Use decreasing priority, so given the current row’s priority x, each other row has probability x of being later. Within a row reveal cells in fixed order. For cell (i,t), use p_j to denote the conditional probabilities for its value J_i(t)=j under the marginal law of J_i, given the previously revealed part of just that row. There are u remaining columns to fill in the row, so p is supported on u remaining values (allowed to have zero probabilities there). The sum of expected -\log p_j for the true values over cells gives \sum_i\mathsf h(J_i).

We give the savings in the entropy upper bound arising from earlier rows. Call a candidate j heavy if p_j>B/u, and otherwise light. Let their class masses be P_\mathrm{heavy},P_\mathrm{light}. For light candidates, consider availability, meaning that the pair with this j and current R_t(i) has not appeared in earlier rows. Use as test probabilities for the entropy bound p_j unchanged for heavy candidates; for light candidates redistribute their class mass on available light candidates proportionally to p_j. If no such positive mass is available, omit the light class. These probabilities (possibly a subprobability) use only the permitted history with R known, and the true value has positive test probability almost surely. By the entropy or cross-entropy inequality at every step, this gives the upper bound on conditional entropy equal to the base terms from -\log p_j, plus terms of the following form:

• •

  a contribution zero if the true value is heavy;

• •

  for a light true value, the logarithm of the fraction of P_\mathrm{light} available in positive-probability light candidates.

Here and below it is the expectation of such contributions that enters the bound.

The cell gives an expected contribution of about -1 outside of some losses, as follows. Fix the full arrays first, and suppose the true value is light, P_\mathrm{light}\ge 1/2, and b_{it}<B. Every pair in question occurs exactly once in the valid arrays. The total fraction in the light class from pairs located within row i is at most 2B^2/u: there are at most b_{it} of them and each light mass is at most B/u. For pairs outside this row the probability of availability is x, given the current priority. Hence the average log fraction, bounding by Jensen’s inequality and integrating priority, is at most

with an absolute C'; this follows by integration, for large n, also when 2B^2/u>1. We have used the independence of the row priorities from the full arrays.

Always, the contribution is at most zero. The losses (missed savings of 1) on summing from b_{it}\ge B can thus be charged to \mathbb E_\nu W; the total losses from heavy true value or P_\mathrm{light}<1/2 are bounded by 3 times the sum of expected P_\mathrm{heavy}. Conditionally using just the row history, heavy mass is bounded by

for large n, using \operatorname{Unif}_u on the remaining values. To see this use z\log z-z+1\ge 0 with z=u p_j in the divergence, and bound it below by z(\log B-1) for heavy values. The sum of these expected conditional divergences (the numerators) is \sum_i D_\mathrm{u}(J_i).

Applying the entropy chain rule (with independent priorities) now gives

The double sum error with its prefactor is at most C'' n^{0.55}, as l=O(\sqrt n) and B=\lceil n^{1/100}\rceil. In adding \mathsf h(R), use

Then (184) shows we get (183) (the positive error coming from \mathcal C_R/(c\log n) is absorbed by the saving of \mathcal C_R). This proves the entropy claim.

To conclude (182), take \nu to be the law of the independent components conditioned on validity, assuming positive probability. Write \rho=\bigotimes_v \rho_v for the independent law before conditioning, and \nu_v for the marginal at v. In passing between permutation components and the arrays we may have taken inverses, which does not affect the given supremum bounds. Minus the log probability of validity equals

In (183), the individual deficits D_\mathrm{u} are at most D(\nu_v\|\rho_v)+\log L_v. Using (183) and C/\log n\le 1 for sufficiently large n, we get (182).□

Proof. Set X=F_H F_H^*,\ Y=F_K^*F_K, positive operators. Since T_n^*T_n=F_H^*YF_H, the positive operators T_n^*T_n, \mathcal Q_n, and Y^{1/2}XY^{1/2} have the same eigenvalues, including zeros. Their p-th powers therefore have the same trace. Lemma 2.6, with exponent p\ge2, gives

Use x(h),y(k) for the kernels of X^{p/2}, Y^{p/2}, respectively, normalized on their own groups, meaning that X^{p/2} acts by convolution with x(h)/|H|, and similarly for Y^{p/2}. The powers here indeed come from these groups, as extension to G acts by the same matrix blocks on corresponding cosets. Both x and y factor as products over permutation components in their respective groups. Apply Lemma 3.3 to the positive line powers composing X^{p/2} and Y^{p/2}. In the present orientation compatibility is hk\in KH; the lemma gives the unnormalized squared-coefficient form

where expectation is independent uniform. This is where we can apply the grid estimate, but the kernels should first be split into sizes.

Each permutation component v of H,K uses a group of degree a=m or l. Its kernel factor in x or y is for D_v^{p/2}, where D_v is a copy of T_a^*T_a or T_a T_a^* on the regular representation of the component. Split according to spectral bins indexed by b=0,1,\ldots, grouping eigenvalues of D_v^{q_a} in

Only nonzero eigenvalues matter. These pieces, also of convolution form by spectral calculus, have ranks r_{v,b}\le 2 e^{b+1} by the input trace bound. Write z_{v,b} for the normalized kernel for D_v^{p/2} restricted to the bin, zero on the orthogonal complement. For expectation uniform on the component group, using the stated child trace bounds, we have

In the first inequality we used that uniform mean square equals the squared Hilbert-Schmidt norm (ordinary, for the convolution matrix in the regular representation). Also, for each nonempty bin,

This is the rank bound for a positive coefficient density in Lemma 3.3, applied to the bin operator.

Each nonempty bin now supplies a probability density |z_{v,b}|^2/w_{v,b} bounded by its rank. Its total mass before normalization is w_{v,b}. These are exactly the two quantities needed in the grid estimate.

Expand x(h)y(k) using the bins in each component. For a term with a single bin b_v in each (take nonempty bins), its squared norm for the expectation on the right of (186), including the indicator, is by (182) at most

where C,C_1 are absolute, and A can now be fixed greater than C+2. Indeed (182) applies to the independent laws given by the squared kernels in the bins, normalized to probabilities. By triangle inequality on taking square roots for the sum over bins, geometric summation, and squaring again, we obtain

with another absolute C_2. Finally,

Substitution in (186) proves (185).□

Proof. To prove (187), let R_j^* in this paragraph and the derivation denote a number, namely the trace of \mathcal Q_n on the permutation representation on ordered j-tuples of distinct positions (including j=0). By branching, for j\le n/2 we have

Indeed the representation on tuples is induced from the trivial representation on a subgroup permuting n-j points. By Frobenius reciprocity and branching the multiplicity of \lambda is the number of standard tableaux for the skew diagram left by omitting a first row segment of length n-j (zero if the segment does not fit). Here if k\le j the skew part of the top row does not interact with \bar\lambda as j\le n/2, giving the formula. Consequently

There is a path expression for these tuple traces. Perform one pass on all the labels, and in its collision graph place an edge between two labels when they face each other at a switch. Labels may for this purpose be identified with their initial positions. This is a simple graph: once two paths face each other they differ in the bit produced there, which is not changed again, so they cannot face again. For s\ge 0 let h_s for this graph be the number of edge subsets with exactly s vertices in their support (thus h_0=1). We claim the polynomial identity

In computing the tuple trace, we sum squared probabilities for the j-tuple to move between prescribed positions over a pass, since its operator from the pass is multiplied by its adjoint. For a tuple start, sample a finish by using the switches. Given this start and finish, the trajectory of every marked label is determined, because each bit is used exactly once. The probability of the sampled tuple finish from the given start is

This follows since each marked path determines a bit at each layer, each a 1/2 factor, except that two facing paths use the same coin. Compatibility at collisions holds since we took a sampled finish. Taking the mean of this probability exactly gives the sum of squared probabilities for that start. Now choose an ordered uniform tuple start, so the marked set M is a uniform j-set independent of the collision graph in the full shuffle, and there are (n)_j tuple starts. Expanding 2^{\,\#\{\text{edges in }M\}} by counting edge subsets, the expansion multiplies h_s, in expectation over M, by (j)_s/(n)_s (interpreted as zero for s>j). Including factors (n)_j n^{-j} and summing proves (189).

For any realized graph the maximum degree is at most d, and the number of induced edges within any set of u vertices is at most

For (190), consider each layer, grouping these vertices by their common initial suffix of bits after the layer coordinate. The suffix and the current layer coordinate are not yet updated before that layer. Within each suffix group every collision then is between the two subgroups for the values of that coordinate, with number at most \min(a,b) if their sizes are a,b. Use

by concavity of binary entropy, taking zero terms as zero. Summing these bounds telescopes through the groupings by suffix and proves (190).

The exact generating identity has reduced the weighted representation trace to edge subsets in one collision graph. The induced-edge bound controls the connected edge subsets on each support. We use it next to estimate the degree-k coefficient uniformly over the required range.

For coefficient k we may truncate (189) by omitting s>k. Bound the resulting expression times e^{-z} on |z|=r=k n^{0.015}. Here 1\le k\le n^{0.62} and r<n/2 for large n. Its modulus is at most

bounding e^{-z}(1+z/n)^n and |n+z|^{-1}. To control the sum, the number of connected edge subsets of support size u\ge 2, in any of the graphs above, is at most

Indeed the connected vertex sets can be found by walks of length 2(u-1) through a spanning tree, and given the set use (190). A general edge subset is a collection of connected edge subsets. Dropping disjointness and truncation on totals, but still using u\le k for individual components, shows that the sum inside the expectation in (191) is at most

The exponent here is o(k) uniformly. For 2\le u<40 the total is O(n(d^2 r/n)^2)=o(k), since d=O(\log n) and k\le n^{0.62}; for u\ge 40 the number inside the parentheses raised to u, before taking that power, is at most n^{-0.05} for all sufficiently large n, so the total for those u is o(1). Also r^2/n=o(k). By Cauchy’s coefficient bound in (188), we get B_k\le k! r^{-k}\exp(o(k)), proving (187).□

Proof. The small-level input to the common moment closure is the positive mass B_k, rather than a separate bound on each block. We first convert that mass into a bound for the low-level regular trace.

First, the total contribution in the regular trace of \mathcal Q_n^q, for any q\ge 300, from levels 1\le k\le n^{0.62}, tends to zero. Indeed each such representation occurs in the corresponding k-tuple representation, so f^\lambda\le n^k. The sum of the single-copy positive traces of \mathcal Q_n at level k is at most B_k, hence the sum of their traces for the power q is at most B_k^q. Thus the contributions including multiplicities are at most \sum_{1\le k\le n^{0.62}} n^k B_k^q=o(1).

If the transposed partition has level k\le n^{0.62}, the original diagram has height n-k>n/2 for large n, and its block vanishes by Lemma 2.1.

All remaining diagrams, other than the trivial representation, have dimension at least \exp(n^{0.60}) for large n. Here are details of this coarse dimension bound. Let b=\lfloor n^{0.62}\rfloor; the numbers outside the first row and outside the first column both exceed b. If neither the first row nor first column has length 5b or greater, all hook lengths are at most 10b, so the hook length formula gives a sufficient lower bound. Otherwise transpose if needed, which does not change dimension, to suppose the first row has length at least 5b. Use a subdiagram with first row of length 4b and b more cells below it, chosen forming a partition there. This is possible by selecting a subdiagram of that size below the top row; in particular those cells have width at most b. Its tableau dimension is a lower bound for the full dimension by extension of tableaux. By filling the first b cells in the top row first, and then interleaving a standard filling order in the lower b cells with the remaining top row cells, we get at least \binom{4b}b standard tableaux. This suffices as well.

Apply Lemma 4.4 with \nu=2, \varepsilon=1/8 and P=300, since \operatorname{Tr}\mathcal Q_n^q=\operatorname{Tr}|T_n|^{2q}. The low class consists of the levels 1\le k\le n^{0.62} and the annihilated blocks. Its contribution is at most 1/16 for all large n, uniformly for q\ge300. The dimension calculation above and Proposition 14.2 supply

With \delta_d=1/\log n,

and \alpha_d(1+\delta_d)=1+O(1/d). All thresholds are independent of the child exponent. The lemma therefore proves (192) with bounded q_n.

Taking an integer s\ge\sup_nq_n, the Schatten-power estimate (23) bounds the nonconstant regular squared norm of T_n^s by 1/8. For convolution this is the chi-square divergence from uniform; Proposition 4.1 gives total variation less than 1/4. Thus an absolute number of sweeps suffices. Lemma 2.3 gives the lower bound 2d-O(1) in physical shuffle units.□

Proof. Let K and L be the row and column permutation subgroups. A line projection of type \rho and carrier rank r has regular rank D_\rho r. Its coefficient density f therefore satisfies \E|f|^2=D_\rho r, and |f|^2/(D_\rho r) is a probability density bounded by D_\rho r, by Lemma 3.3. Applying that lemma to the tensor products gives

where row and column permutations are independent, their line laws are these squared-coefficient densities, and \mathcal S is their compatibility event. The lemma includes the unique-completion and inversion changes that identify this event with the four-factor trace.

Fix the column permutations. Write j_i(t) for the original column in row i sent by the row permutation to column t, and k_t(i) for the subsequent output row under the column permutation. Success requires the pairs (k_t(i),j_i(t)), over all cells (i,t), to be distinct. Put r_{ik}^{\circ}=|\{t:k_t(i)=k\}|. Call a cell bad if r_{i,k_t(i)}^{\circ}>b^{1/8}, and let H count the bad cells. This designation depends only on the fixed column permutations.

Let \rho_i be the original law of row i, with density at most K_i relative to its uniform law U_i. Put p=\Pr_{\otimes_i\rho_i}(\mathcal S) and assume p>0; the zero-probability case needs no estimate. Let Q=(\otimes_i\rho_i)(\,\cdot\mid\mathcal S), and write Q_i for its row marginals. Define

The relative-entropy chain rule and the density caps give the exact identity and inequality

Indeed \KL(Q\Vert\otimes_i\rho_i)=-\log p, and L_i=\KL(Q_i\Vert\rho_i)+ \E_{Q_i}\log(d\rho_i/dU_i). These formulas retain the extra relative entropy created by conditioning on success.

Reveal rows in independent continuous uniform priority order, and within each row use an independent uniform order of its cells. At a cell of row i, let P(j) be the prediction under Q_i given only the already exposed cells of that row. A symbol is called heavy at this revelation when P(j)>b^{-1/2}. Heavy symbols are different from the bad cells defined above. Except at the last \lceil b^{4/5}\rceil revelations of a row, the uniform permutation prediction assigns each available symbol probability at most b^{-4/5}. On a heavy symbol, the nonnegative divergence term u\log(u/v)-u+v is at least c u\log b. Summing the prediction divergences by the chain rule therefore gives

Consider a good cell (i,t) and write y=1-\text{priority}(i). In the chain-rule expression for I, the reference prediction is P, whereas the actual prediction conditions on the full past. Only symbols not already used at output row k_t(i) are allowed. Use the unnormalized reference P_*(j)=yP(j) on heavy symbols and P_*(j)=P(j) on the others. If A is the set of allowed symbols and q is the actual conditional prediction, normalization of P_*\mathbf1_A gives

Conditional on the complete successful assignment, the within-row order, and y, every symbol at this output row belongs to exactly one packet. If that packet comes from a different input row, its row has not yet been exposed with probability y. There are at most b^{1/8} exceptions coming from the current row. Their light symbols contribute at most b^{1/8}b^{-1/2}; their heavy symbols are covered by the factor y. Thus the conditional expected allowed mass is at most y+b^{-3/8}. Jensen’s inequality and integration over y\in[0,1] make the first term at least 1-O(b^{-1/4}). The expected cost of the second term is the heavy-outcome probability, since the assignment and within-row order are independent of the row priority and \int_0^1\log y\,dy=-1.

For bad cells retain the nonnegative raw conditional KL contribution and charge no unit saving. Summing good cells and using (196) yields I\ge n-H-Cn^{1-1/40}-a_b\sum_iL_i, where a_b=C/\log b. Consequently (195) gives

For sufficiently large b, a_b<1. Discarding the nonnegative last term proves the conditional success estimate

In particular the main saving remains exactly -n.

It remains to average the factor e^H over the biased columns. We give the required bundle count. Put B=\lfloor b^{1/8}\rfloor+1. A bundle chooses an input row i, a destination row k, and B columns in which k_t(i)=k. A family of bundles is disjoint if its prescribed cells are disjoint. Under independent uniform column permutations, a fixed family of s bundles has probability at most (e/a)^{Bs}: a column with u consistent prescribed images has probability 1/(a)_u\le(e/a)^u. For each repeated row value with count v\ge B, pack \lfloor v/B\rfloor disjoint bundles. Thus every outcome has a satisfied disjoint family with 2Bs\ge H. For c=1/64, summing over all possible such families, including the empty one, proves

for sufficiently large b. Indeed the expression in braces is at most a^2(2e^2b^{2c}/B)^B, which tends to zero. The joint biased column law has a density \rho bounded by e^{x_C}, where x_C is the column part of D_c, and has mean one. Hölder with r=c\log b>1 yields

Together with (198), this supplies a compatibility probability at most \exp\{-n+Cn^{1-1/40}+CD_c/\log n\}. The exact -n cancels the factorial factor, since \log(n!/(|K||L|))=n+O((a+b)\log n). Multiplication by e^{D_c} from the squared coefficient masses proves the claimed bound for all sufficiently large b. For bounded n\ge2, the same constant can be enlarged uniformly over all local projections. Indeed R_\lambda,S_\lambda are orthogonal projections, so

Since D_c\ge0, a fixed multiple of n^{39/40} absorbs \log(n!) over the finitely many remaining sizes. This includes the grid (a,b)=(1,2); a one-site line has only the trivial carrier. No estimate with denominator \log1 is needed.□

Proof. This is Lemma 2.8, including its continuity argument at zero eigenvalues.□

Proof of Theorem 15.1. Write \eta=10^{-8} and u_0=3/1000. Fix a constant c_s\in(0,1/100) for which (201) holds above an absolute cutoff, and put

In particular 12c_0<1/4. We will specify an absolute starting exponent d_0 after estimating the errors; its choice will depend on c_0 and the absolute constants in the two overlap estimates, but not on the exponent supplied by the finite base cases.

Induct on d=\log_2n. Denote the available exponents for the two child sizes by c_{\lfloor d/2\rfloor} and c_{\lceil d/2\rceil}, and set

All these exponents will lie in (0,c_0], so v\ge1. Fix a nontrivial \lambda=(n-k,\beta) that is not annihilated and put M=k\log n. Since \mathcal W(M,D)\le4D\le8M, the range k\le n^{3/5} already follows from (201), with any exponent at most c_0. We henceforth assume k>n^{3/5}.

Here is the band decomposition used at a split. For a child size m\in\{a,b\} and a type \rho\vdash m, let h=m-\rho_1, q=D_\rho, and M_\rho=h\log m. Choose an orthonormal eigenbasis, in decreasing eigenvalue order, of the appropriate absolute value |T_m| or |T_m^*| of the child sweep. For each integer 0\le t\le\lfloor\log_2q\rfloor, the tth band is the span of the eigenvectors with indices

Its starting index r=2^t bounds its carrier rank from above. Associate to it the number D_\rho(r)=\log(qr). The induction hypothesis bounds the operator norm on this band by

For the trivial type there is one band, with M_\rho=D_\rho(1)=0. An annihilated type contributes the zero operator and may be omitted. The bound q\le m^h shows that every band satisfies 0\le D_\rho(r)\le2M_\rho.

A row profile specifies a type and a band on each of the a rows; a column profile does the same on each of the b columns. We keep only product types occurring in the restriction of V_\lambda. If their total levels are k_A and k_B, respectively, the Littlewood–Richardson rule gives k_A,k_B\le k. Indeed a constituent of an induced product of the local types has first row at most the sum of their first rows. For a pair of profiles write

The sums include both directions. Thus D_c\le2M'\le2M, and (194) gives F_c\ge\mathcal W(M,D_c).

We will need a count of these profiles before using any decay exponent. There are at most (k+1)^a row-level lists. For any such list (h_i) with \sum h_i\le k, the number of row types is at most

Here p(0)=1 and p(h)\le e^{3\sqrt h} for h\ge1. On each line the number of bands is at most 1+\log_2(m!)\le n^2 for n\ge4. Since \log(k+1)\le2\log n, the number of row profiles is at most \exp(4a\log n+3\sqrt{ak}). The same count for columns shows that the number L of pairs of nonzero profiles satisfies

If there are no nonzero pairs, the required operator is zero and the conclusion is immediate. Hence assume L\ge1.

Take polar decompositions in the row and column group algebras, writing X=A U_X and Y=U_Y C, where A=|X^*| and C=|Y|. The partial isometries can be extended to unitaries in each local carrier space. Thus T_n=U_YCAU_X has the singular values of CA. Put Z=C^vA^v. If R and S are the projections of a row and a column profile, respectively, then

The projections commute with the positive factors in their own direction. The local band estimates therefore give, for every index r\ge1,

This also follows directly by factoring out the two band norms and using s_r(B_1HB_2)\le\|B_1\|_{\op}\|B_2\|_{\op}s_r(H). If a band’s actual rank is less than its starting index, the overlap estimates are still applicable: their actual parameter \sum_i\log(D_{\rho_i}\operatorname{rank}R_i) is at most D_c, and each displayed upper bound increases with that parameter.

For 1\le j\le D_\lambda set

The singular-value sum inequality, or rank-(r_j-1) approximations to all L summands, gives

In fact the sum of those approximations has rank at most L(r_j-1)<j, which verifies the index in this inequality even when j<L.

First suppose \log D_\lambda\ge n^{99/100}. Since \Tr(RSRS)=\|SR\|_{S^4}^4, Lemma 15.2 implies

for an absolute C_4. Combining this with (208) and (209) yields the indexed bound

As usual a zero singular value satisfies every such upper bound.

The function f(u)=\max(\eta u,u^3) is increasing and is 12-Lipschitz on [0,2]. If D_c\ge D, Jensen’s inequality already gives F_c\ge\mathcal W(M,D). Otherwise put x=D-D_c>0 and

Jensen and the Lipschitz bound give F_c\ge\mathcal W(M,D)-12x. Since 12c_0\le1/4,

Thus both cases of D_c in (210) imply

To quantify this error, use k\le n, a+b\le3\sqrt n and \sqrt a+\sqrt b\le3n^{1/4}. Above an absolute cutoff, B\le C_B n^{3/4} for an absolute C_B. Since \mathcal W(M,D)\ge\eta D and D\ge n^{99/100}, there is an absolute K_4, depending only on the already fixed c_0,\eta and C_4, such that

In particular none of these constants depends on c.

We next justify exactly the dimension range in the other case. Suppose \log D_\lambda<n^{99/100}. The surviving shape has height at most n/2. It must have first row longer than n/2 once n is sufficiently large. Indeed, otherwise both its width and height are at most n/2. Transpose if necessary so that the first row has length q=\max(\lambda_1,\lambda'_1). If q\le n/8, every hook has length at most 2q\le n/4, and the hook formula gives D_\lambda\ge(4/e)^n. If q>n/8, retain that first row and a subdiagram of t=\lfloor q/4\rfloor tail boxes. Such a subdiagram exists because n-q\ge n/2\ge t. Its tableaux extend to the full shape. Applying (6) to the retained diagram gives

For large n, t\ge q/8>n/64. Both alternatives give \log D_\lambda\ge c_1n for an absolute c_1>0, contradicting the assumed upper bound. Hence k<n/2.

If nevertheless k\ge n^{249/250}, retain the first row of length q=n-k>n/2 and t=\lfloor n^{249/250}\rfloor tail boxes. For sufficiently large n we have t\le q/2, so the same hook estimate implies

For the middle inequality, use t\ge n^{249/250}/2 and \log(q/t)\ge(\log n)/250-\log2\ge(\log n)/500, and increase the cutoff to absorb the subtracted 1. We have proved k<n^{249/250}. Moreover (6), now applied to \lambda itself, gives

Here k/(n-2k+1)\le1 for all sufficiently large n, and k>n^{3/5} makes 1/M\le1/1000. In particular \eta u<u^3, so \mathcal W(M,D)=Mu^3 throughout this range.

We can therefore apply (199). Write \ell=\log n, b_0=\log(n/k), \Delta=M-M'\ge0, and \tau=k-(k_A+k_B)/2. If \varepsilon=(\log b-\log a)/2\in[0,(\log2)/2], then

By (213), b_0/\ell\le u+1/M. Consequently

The identity \Tr(RS)=\|SR\|_{S^2}^2, the second-moment overlap estimate, and rank allocation now give

where C_2 is the absolute constant in (199).

For clarity, the required tangent inequality follows directly from x^3\ge u^3+3u^2(x-u) for x\ge0. Since f(x)\ge x^3 and f(u)=u^3, multiplication by each M_i and summation give

Zero-mass terms contribute zero. Put H=D-D_c-\tfrac12u\Delta. The exact relation G=H-u\Delta/6\le H is favorable in the direction needed here. If H\le E_2, the tangent inequality gives F_c\ge Mu^3-3u^2E_2. If H>E_2, it gives

because u\le2 and 12c_0<1/4. Thus in either case (215) implies

The count (207) and k>n^{3/5} give the explicit bounds

Since \mathcal W(M,D)=Mu^3\ge u_0^3M, an absolute K_2 therefore satisfies

Again the bound is independent of c.

We can now make all choices in the induction. Let A\ge1 be an absolute constant and enlarge d_0\ge5 so that, whenever d>d_0 and n=2^d, both right sides of (212) and (218) are at most Ad^{-1/8}. This is possible because their ratios to d^{-1/8} tend to zero. Enlarge d_0 further to include all previous absolute cutoffs, to have 2Ad_0^{-1/8}\le1/2, and to ensure

in both remaining regimes. The last choice is uniform in j: in the dense regime the weight is at least \eta n^{99/100}, and in the middle regime it is at least u_0^3n^{3/5}\log n. The two error inequalities prove, simultaneously for every 1\le i\le D_\lambda,

Apply Lemma 15.3 and use that a decreasing singular-value sequence satisfies s_j(CA)^j\le\prod_{i=1}^j s_i(CA). We obtain

No individual-singular-value interpolation is being assumed. The same 12-Lipschitz bound used above gives

Since \log(j!)\ge j\log j-j, the average of \log(j/i) over 1\le i\le j is at most 1. Thus the average weight is at least \mathcal W(M,\log(D_\lambda j))-12. In view of (219), this proves the inductive conclusion with exponent

The small-level estimate, considered at the start, also holds with this exponent.

For 1\le d\le d_0 choose a common c_*\in(0,c_0] so small that the desired inequality holds for every nontrivial type and every singular index. Such a choice exists by Lemma 2.2, because there are only finitely many matrices, \mathcal W\le8k\log n, and zero operators need no restriction on c_*. Define c_d=c_* on this finite range and use (221) thereafter. This does not change the previously chosen cutoff.

Every multiplier in (221) is at least 1/2 by the choice of d_0. The minimum selects a branch of rounded halvings. Lemma 4.3, with \gamma=1/8, therefore gives \inf_d c_d>0. Taking this infimum as the theorem’s exponent completes the proof.□

Proof. For k=0 the type is trivial and the assertion is 1\le1. We specify the tuple kernels and their normalization first. Let \mathcal X_k be the ordered injective k-tuples of sites. Write P(x,y) for the forward sweep transition probability on this space, with input index x and output index y. As an operator on tuple functions this is the adjoint of the homomorphic sweep action, and has the same singular values on every irreducible block. For I\subseteq[k], define

Before restriction to injective outputs, this kernel moves the I-labels with one common sweep and moves every other label by its own independent fair bit at each coordinate. The latter endpoints are independent uniform sites. Thus Q_I has row sums at most 1. Its transpose has the same description using the reversed sweep, and has row sums at most 1 as well. All sums here are counting sums of transition probabilities. Rescaling the tuple inner product to uniform probability does not change the operator or its norm.

The block \lambda=(n-k,\beta) occurs on \mathcal X_k and does not occur on any proper subset of its slots. For I\ne[k], both the range of Q_I and the range of Q_I^* consist of functions of the I-coordinates. These ranges have no \lambda-part by branching. Consequently

Here and below a restriction to \lambda may include all its copies in the tuple module.

Given endpoints x,y, the path of each label through a sweep is unique: its updated coordinates have their values in y and its remaining coordinates have their values in x. Join two labels when these paths use the same switch at some time, including an inconsistent use of the same switch input. Let \Gamma(x,y) mean that this graph has no isolated vertex. If a label is isolated, its prescribed switches are independent of those prescribed by all the other labels. Adding this label to I therefore multiplies its joint endpoint probability by 1/n, exactly canceled by the change in the prefactor in (223). Pairing terms with and without that label proves

For k=1 the two terms are identical, so Z=0 and the assertion follows. Henceforth take k\ge2.

On the \lambda-part, PZ^*=PP^* is positive semidefinite. An absolute row-sum bound for PZ^* therefore bounds \|P|_\lambda\|_{\op}^2: apply the operator to an eigenvector of PP^*|_\lambda and choose a coordinate of maximum absolute value. By (225), it suffices to bound, uniformly in an initial injective tuple, the following experiment for each I. Run a full sweep, obtaining an injective intermediate tuple z; then run a partially coupled reversed sweep, jointly on I and independently on the other labels, and ask for \Gamma in this second sweep. Dropping injectivity of the final tuple only increases the nonnegative bound. This description follows exactly by multiplying P(x,z)Q_I(y,z) and summing over z,y; no replacement of the two-sweep law is made.

The occupied set of z satisfies

for every fixed set of sites A. This is the case r=k, s=0 of Lemma 11.2, applied to singleton test sets. Its hypotheses hold because this first sweep moves all k labels jointly from distinct sites.

Put L=\lfloor\delta d/2\rfloor and partition the second sweep’s chronological coordinate list into J=\lceil d/L\rceil nonempty consecutive chunks, each of length at most L. For sufficiently large d, L\ge1 and J\le J_\delta:=\lceil4/\delta\rceil+1. A chunk of length \ell partitions sites into bins of size s=2^\ell\le n^{\delta/2}, according to all the coordinates outside that chunk. Each path stays in its bin throughout the chunk. Every contact therefore lies in a bin containing at least two labels at the start of that chunk.

On \Gamma, every label is in such a bin in at least one chunk. Thus some chunk has at least k/J labels in bins of occupancy at least two. Define

If k\ge2J, then 2r\le k/J. If there are at least r multiply occupied bins, take any r of them. Otherwise take all of them and pad to r bins: their total occupancy is still at least k/J\ge2r. If k<2J, coverage supplies at least one contact, so some chunk has one bin with two labels and the same conclusion holds with r=1. There are enough bins for padding, since n/s\ge n^{1-\delta/2}>k\ge r for large n. In all cases

Fix a chunk and a specified union A of r of its bins. Then |A|=rs. Presample the partially coupled motion from the beginning of the second sweep to this chunk. Use one common random permutation \phi for the I-labels. Independently, for every possible starting site v, sample one independent walk with endpoint \xi_v after that prefix. If z_i=v and i\notin I, use this walk for label i. The z_i are distinct, so this site-indexed construction gives exactly independent walks for those labels. All these random maps are independent of the first sweep.

Put C=\phi^{-1}(A) and D=\{v:\xi_v\in A\}. The number of labels in A at the start of the chunk is at most the number of occupied intermediate sites in C\cup D. We have |C|=rs, while W=|D| is a sum of independent Bernoulli variables with mean rs. Indeed the transition matrix of any coordinate prefix is doubly stochastic, so \sum_v\Pr(\xi_v\in A)=|A|. Consequently \E\binom Wj\le(rs)^j/j!. Conditioning on the presampled maps and using (226), then averaging, gives

This is an unconditional preimage calculation. It does not condition the intermediate tuple on previous contacts. Summing over choices of the r bins yields

Now ks/n\le n^{-\delta/2}. For all sufficiently large n, depending only on \delta, this last bound is at most n^{-\delta r/4}\le n^{-\delta k/(16J_\delta)}. Union over the J chunks and the 2^k choices of I therefore gives

The positive-block eigenvalue argument above and a square root prove (222), for example with c_\delta=\delta/(64J_\delta) after increasing the starting size. The separate k=1 argument supplies the smallest level without any padding or rounding exception.□