From partial permutation information to Fourier bounds

Proof. We use the classical tableau dimension and hook formulas: D_\lambda is the number of fillings of the diagram of \lambda by 1,\ldots,n increasing along each row and column, and

where h(x) counts the box x and the boxes strictly right of it or strictly below it [5, 6]. Write p(k) for the number of partitions of k, with p(0)=1. Euler’s product at x=e^{-1/\sqrt{k}} gives, for k\ge1,

If a Young diagram has a top row of length a and j\le a lower boxes, its number of standard tableaux is at least \binom aj. Put the first j labels in the first j top-row positions, choose the j lower labels from the remaining a labels, and fill the lower diagram in one fixed standard relative order. Its width is at most j, so every top-row predecessor is smaller. Fill the rest of the row increasingly. A tableau of any Young subdiagram extends to the full diagram by adding larger labels in an order respecting row and column predecessors.

Orient a longest row or column as the first row and let its length be n-j. When 1\le j\le n/3, at most 2p(j) diagrams have this value and

For each fixed j>0 the binomial coefficient diverges, and 2p(j)2^{-uj} is summable. Dominated convergence handles this range.

In the remaining range put a=\max(\lambda_1,\lambda'_1)<2n/3. If a\ge n/10, retain the first row and a lower Young order ideal of \lfloor a/2\rfloor boxes; there are enough lower boxes. Extension and the preceding construction give D_\lambda\ge2^a/(a+1), exponential in n. If a<n/10, every hook has length at most 2a, and the hook formula gives D_\lambda\ge n!/(2a)^n\ge(5/e)^n. Both bounds beat p(n)\le e^{3\sqrt n}. Thus Z_u(n)\to0. Adding the row and column shows that the full sum tends to two; finitely many smaller values are finite.□

Proof. Every block of a uniformly chosen ordered equal partition is itself a uniform n/b-subset. The expected sum of the errors is at most b\delta, so one partition has sum no larger than that expectation.□

Proof. Process the subgroup coset systems successively. Within each coset whose current mass exceeds its uniform mass, multiply all current point masses by the ratio of the cap to the current mass. The loss at stage i is at most the original positive excess on the ith quotient, namely \delta_i, because all current masses are below \mu. Later decreases preserve earlier caps.

There is also a simultaneous construction with the same guarantee. For each i, trim \mu separately to a measure f_i, and set f(g)=\min_i f_i(g). Then f\le f_i ensures every cap, while \mu-f\le\sum_i(\mu-f_i) bounds the loss by \delta. Thus these two constructions need not produce the same measure, but prove exactly the same assertion.

If a coset Q has \mu(Q)>cU(Q), then \mu(Q)\le c(\mu(Q)-U(Q))/(c-1). Summing over its heavy cosets and then over subgroup systems bounds the removed mass. A surviving coset has original mass at most cU(Q); division by 1-\eta gives the displayed cap. Conditioning deletes mass \eta and adds that same mass on the retained set, proving the variation equality.□

Proof. Expand the squared Hilbert–Schmidt norms. The regular-character identity

proves Plancherel. Apply it to f-zU, whose trivial coefficient is zero, and to f-U, whose trivial coefficient is z-1. Cauchy–Schwarz gives (2.2). Finally, \sum|f/z-f|=1-z=\sum|\mu-f|, so the triangle inequality proves the normalization claim.□

Proof. The sign term tends to zero by the preceding mass bounds. In the operator case,

In the Hilbert–Schmidt case submultiplicativity gives D\|\widehat f_n^{\,r}\|_{\HS}^2\le A^rD^{1-r\gamma}. The sums tend to zero by Lemma 2.1. The trivial coefficient tends to one. Lemma 2.4 gives convergence for f_n^{*r}; the missing mass or a telescoping replacement of the r probability factors gives convergence for \mu_n^{*r}. No normality or diagonalization is used.□

Proof. Regroup the entire \tau-isotypic space as V_\tau\otimes\mathcal A_\tau, where H acts as \tau\otimes I. If v_\tau is the component of v there, its orbit lies in the image of

The image has dimension at most (\dim\tau)^2, independently of \dim\mathcal A_\tau. Equivalently, writing v_\tau=\sum_{j=1}^{\dim\tau}e_j\otimes a_j, the orbit lies in V_\tau\otimes\Span(a_j). Sum over inequivalent types.□

Proof. The disjoint subgroups form a direct product H=H_1\times\cdots\times H_b. Its isotypic decomposition in V_\rho is an orthogonal sum of spaces

Every occurring tensor product has dimension \prod_i\dim\tau_i\le D. Assign its whole isotypic space to the least index i for which \dim\tau_i\le D^{1/b}. Group the assigned spaces to obtain V_\rho=E_1\oplus\cdots\oplus E_b. Equivalently, let P_i select the small H_i-types. These projections commute and \prod_i(I-P_i)=0. The projections Q_i=P_i\prod_{j<i}(I-P_j) are orthogonal and sum to identity: on each product type Q_i is identity exactly when i is its first small factor. Thus the explicit splitting v_i=Q_iv is precisely the least-index assignment above.

Fix v_i\in E_i and put W_i=\Span\rho(H_i)v_i. Lemma 3.1 and the definition of C_u give

The second inequality follows term by term from (\dim\tau)^2\le D^{(u+2)/b}(\dim\tau)^{-u}. It is uniform in the block size.

The remaining task is to use this dimension bound on a coefficient. Let \Pi_i be the orthogonal projection onto W_i. Since W_i is H_i-invariant, the projection onto \rho(g)W_i depends only on gH_i. The coset cap therefore gives, for every w,

Indeed \E_U\rho(g)\Pi_i\rho(g)^* commutes with \rho(G) and has trace \dim W_i, so Schur’s lemma identifies it as (\dim W_i/D)I.

Since \rho(g)v_i\in\rho(g)W_i and f has mass at most one, Cauchy–Schwarz yields

For v=\sum_i v_i, orthogonality gives \sum_i\|v_i\|\le\sqrt b\|v\|. Summing proves the claim. In particular no dimension of a multiplicity space has been discarded.□

Proof. Lemma 2.2 selects an eight-block partition with summed marginal error o(1). Lemma 2.3 supplies a common subprobability f_n\le\mu_n of mass 1-o(1) and coset cap one. Proposition 3.2 at u=1 gives \|\widehat f_n(\rho)\|_{\op}\le\sqrt{8C_1}D^{-5/16}. The nonsign Plancherel contribution after four factors is at most (8C_1)^4 Z_{1/2}(n), because 2-8(5/16)=-1/2. Sign and missing mass tend to zero by Proposition 2.5. This completes a route from averaged observations to the full law.□

Proof. Convolution with e=e_{H,\tau} acts separately in each left coset Q=xH. Since \sum_{h\in H}|e(h)|^2=a^2/|H|, the triangle inequality for a positive weighted sum of translates gives

One may equivalently normalize the weights by f(Q) and use Jensen; the zero-mass coset contributes zero. Also \sum_Q f(Q)^2\le Bz/[G:H]. Plancherel on G proves (3.2).

There is a second exact expression for the same calculation. Let f_Q(h)=f(xh) and \widehat f_Q(\tau)=\sum_hf_Q(h)\tau(h). Subgroup Plancherel yields

Unitarity gives \|\widehat f_Q(\tau)\|_{\HS}\le\sqrt a\,f(Q) and recovers the same bound. This identity makes the normalization of the Hilbert–Schmidt norm explicit.

There is also a positive-projection proof of the same bound. Right convolution by e is an orthogonal projection, since e*e=e and e^*(h)=\overline{e(h^{-1})}=e(h). With the counting inner product,

Indeed |e(h)|\le a^2U_H(h), so positivity of f bounds the absolute convolution pointwise; and (f*U_H)(g)=f(gH)/|H|\le B/|G|. This proves the estimate from idempotence and positivity, independently of the cosetwise norm calculation.□

Proof. For each i, take all H_i-isotypic projections with degree at most D^{1/b}. On every product type in the restriction to \prod_iH_i, at least one such projection is identity. The projections commute and include all multiplicities, so

Trace this inequality against the positive operator \widehat f(\rho)^*\widehat f(\rho), apply Lemma 3.4 after discarding other ambient irreducibles, and use (3.1). The resulting inequality is D\|\widehat f(\rho)\|_{\HS}^2\le Bf(G)bC_uD^{(u+2)/b}.□

Proof. Use the same partition and subprobability as in that corollary. Proposition 3.5 with u=1 gives HS squared at most 8C_1D^{-5/8}. Two powers have nonsign contribution at most (8C_1)^2 Z_{1/4}(n), since 1-2(5/8)=-1/4. Proposition 2.5 handles sign and mass.□

Proof. Schur orthogonality makes the functions \sqrt{\dim\tau}\,\tau(h)_{jk} an orthonormal basis of this coefficient space. At every h, the sum of their squared absolute values is \sum_{\tau\in\Lambda}(\dim\tau)^2, because each \tau(h) is unitary. Cauchy–Schwarz for expansion in this basis proves the assertion. Multiple copies of a representation give the same coefficient functions and do not enlarge the space.□

Proof. Let P_i project onto all H_i-types of degree at most D^{1/b}. The P_i commute, and \prod_i(I-P_i)=0 by the product-degree bound. Thus Q_i=P_i\prod_{j<i}(I-P_j) are pairwise orthogonal projections summing to identity. Write v_i=Q_iv.

For fixed g,w, the function h\mapsto\langle w,\rho(gh)v_i\rangle on H_i uses only the selected types. Lemma 4.1 gives

Average over g with mass f(g). Right averaging replaces f by f*U_{H_i}, whose density relative to U_G is at most B. Schur orthogonality on G gives

Jensen for a measure of mass at most one and \sum_i\|v_i\|\le\sqrt b\|v\| finish the proof. This argument proves the same numerical inequality as Proposition 3.2, using evaluation of functions instead of dimensions of orbit subspaces.□

Proof. Put F=|G|f. On xH, project h\mapsto F(xh) onto the conjugates of the matrix coefficients of \tau. Its uniform squared norm is

because the matrix in the norm has operator norm at most the nonnegative function’s mean, which is at most B. The entries of \rho(xh)P_{\rho,H,\tau} belong to the \tau coefficient space. Replacing F by this projection therefore preserves the tested Fourier matrix. Averaging the bound over cosets and applying full-group Plancherel proves (4.1).

For the second proof, the character bound |\chi_\tau(h)|\le a gives

The density of this convolution has squared L^2(U_G) norm at most B^2a^4. Plancherel gives (4.2). No bound on the conditional law inside a coset was required in either proof.□

Proof. Trace the covering inequality (3.4) against \widehat f^*\widehat f. Sum the corresponding estimate of Lemma 4.3 over all selected subgroup types. For j=2,4,

This proves both bounds, including every multiplicity.□

Proof. On H_i take the central projector density k_i(h)=\sum_{\dim\tau\le D^{1/b}}(\dim\tau)\overline{\chi_\tau(h)}, relative to uniform subgroup measure. Its transform is P_i. Pointwise |k_i|\le R_i, so convolution of the density |G|\eta with k_i is bounded in absolute value by BR_i. Plancherel yields the first displayed bound. Alternatively project onto all selected coefficient spaces on each coset. They are orthogonal; their squared mean sums to at most B^2R_i by the first proof of Lemma 4.3. This gives the second bound.

Use the orthogonal Q_i=P_i\prod_{j<i}(I-P_j), apply either bound to Q_iv, and sum their norms. The inequalities \sum_i\|Q_iv\|\le\sqrt b\|v\| and R_i\le C_uD^{(u+2)/b} give the conclusions.□

Proof. Young branching says that each diagram \tau occurring under restriction to a block symmetric group is contained in \lambda; conjugating a block to the standard subgroup does not change the set of occurring types [6, Theorem 9.2]. Orient a longest row or column of \lambda horizontally, transposing the restricted diagrams too if necessary. Each \tau then has at most k_\lambda boxes below its first row. Given those lower boxes and the block size, its first row is determined. Thus at most M(k_\lambda) types occur, regardless of multiplicity. Apply (3.2) to each selected small type and bound its squared degree by D^{2/b} in (3.4).□

Proof. Put h_0=|H_C|/|G|. Say g is good for C if \mu(gH_C)\le2h_0. The total \mu-mass of bad cosets is at most twice their marginal total-variation distance. Thus the set

has mass M=1-o(1) by Markov’s inequality. For every g\in R a uniform ordered equal partition (C_1',\ldots,C_q') has probability at least 1/2 that g is good for all blocks. Define \nu=\mu(\cdot\mid R).

We use Lemma 4.1: if a function F on a finite group is in the span of matrix coefficients of a collection \Lambda of irreducibles, then

The sum counts distinct types, since equivalent copies have the same space of coefficient functions.

Fix a partition and restrict \rho to its direct product of block subgroups. Decompose orthogonally into tensor-product constituents, including all multiplicity spaces. Every constituent has product of factor degrees at most D. Assign it to one factor with degree at most D^{1/q}. This splits a vector v=\sum_i v_i orthogonally, with v_i using only H_{C_i'}-types of degrees at most D^{1/q}. Fix a test vector w and set F_i(g)=\langle w,\rho(g)v_i\rangle. On a coset gH_{C_i'} it belongs to the coefficient space in (5.2), whose dimension is at most

The sum counts each irreducible type once; multiplicities do not increase the function space of matrix coefficients. Summing the coset maximum bound only over good cosets, and using Schur orthogonality on G, yields

Only a bound on total coset mass was used here.

For g\in R insert the all-good partition event, whose probability is at least 1/2, before splitting the coefficient. It follows that

Cauchy–Schwarz and (5.3), followed by \sum_i\|v_i\|\le\sqrt q\|v\|, prove (5.1). The dependence of v_i on the partition is harmless because the estimate holds for each fixed partition.

The sign coefficient obeys |\widehat\nu(\sgn)|\le(1-M)/M=o(1), since the original sign coefficient is zero. The same argument works when that coefficient is o(1). Fourier Plancherel in the normalization of Lemma 2.4 gives

For q=r=8, the nonsign sum is at most an absolute constant times

by Lemma 2.1. The sign term also vanishes, and \|\mu^{*8}-\nu^{*8}\|_{\TV}\le8(1-M)=o(1).□

Proof. A Young subdiagram is closed under moving up and left. Add its remaining boxes in row-major order with successive larger labels; every predecessor is already present. To prove the first bound, retain the whole first row and a Young subdiagram of b lower boxes. Such a subdiagram is obtained by removing lower corners. Fill the first b top boxes with 1,\ldots,b; choose the b lower labels from the remaining a labels and fill them in the relative order of one fixed standard tableau. All lower boxes lie in the first b columns, so filling the rest of the top row increasingly is valid. For the second bound, reserve only the first c top labels and choose all k lower labels from the remaining a+k-c labels.

For the ballot bound, fix a standard order of the lower boxes and interleave their additions with those of the top row. Require each prefix to have at least as many top-row additions as lower additions. The jth lower box lies in a column at most j, so its top predecessor has been inserted. Reflection at the first violating prefix counts the valid words by the displayed binomial difference. A valid balanced word with k additions of each kind, followed by a-k top additions, gives the last bound. For an actual two-row rectangle the word condition is also necessary, proving the exact count.

Finally, put successive batches of labels on increasing diagonals, in arbitrary order within each diagonal. Every row or column predecessor lies on an earlier diagonal. This gives the product of factorials. The first estimate uses t!\ge2^{t-1}; the second uses t!\ge(t/e)^t and convexity of t\log t to obtain \sum_jt_j\log t_j\ge n\log(n/q).□

Proof. The lower hooks are unchanged, and the top hooks are a-j+1+b_j, which proves the identity. The sequence b_j decreases while (a-j+1)^{-1} increases. The opposite-order rearrangement inequality therefore gives

For completeness, the rearrangement inequality follows by expanding \sum_{i,j}(b_i-b_j)(c_i-c_j)\le0 for oppositely ordered sequences b_i,c_i. Apply \log(1+x)\le x to the product. For the last estimate, b_j=0 for j>k, so every relevant denominator is at least a-k+1, and \sum_jb_j=k.□

Proof. Put L=L(\lambda) and k=n-L. If L\le n/16, every hook is at most 2L, so D_\lambda\ge(n/(2eL))^n\ge2^n. Otherwise orient the diagram with first row L, and for k\ge1 retain b=\min(k,\lfloor L/3\rfloor) lower boxes. For sufficiently large n, b\ge1, and Lemma 6.1 gives

Indeed L>n/16 implies \lfloor L/3\rfloor>n/48-1\ge k/48-1. Thus one may take c_1=1/3 and c_2=(\log3)/48 after enlarging the size threshold. For a fixed positive k, eventually b=k, and D_\lambda\ge\binom{n-k}{k}\to\infty uniformly.

There are at most 2p(k) shapes at deficit k. By (6.1) and (6.9), their total inverse uth powers are bounded by a constant depending on u times e^{3\sqrt k-uc_2k}. This is summable in k, and each fixed positive-k contribution tends to zero. Dominated convergence proves Z_u(n)\to0. The full sum tends to two; its finitely many initial values are finite, including the value one at n=1.□

A ballot proof of the summability assertions. For k\ge1 and L=n-k\ge n/2, (6.3) gives

For the second inequality, the ballot fraction is at least 1/(k+1) and \binom nk\ge(n/k)^k\ge2^k. The majorant 2p(k)(k+1)^u2^{-uk} is summable, and the first binomial expression diverges for each fixed k\ge1. If L<n/2 but L\ge n/10, retain a row of length L and L lower boxes. The ballot count \binom{2L}L/(L+1) is exponential in n. If L<n/10, the hook formula gives (5/e)^n. The subexponential bound for p(n) handles both remaining ranges. Adding the one-dimensional terms proves the uniform bound.□

Proof. Equation (6.7) has exponent k/(n-2k+1)\le1/2, proving (6.10). If k>n/4 and L\ge n/8, keep the first row and b=\lfloor n/32\rfloor lower boxes. For large n, 1\le b\le L/4. The same hook bound gives dimension at least \frac12\binom{L+b}b\ge4^b/2. If L<n/8, every hook is shorter than n/4, giving (4/e)^n. Both exceed e^{n/100} for sufficiently large n. The near-row inverse sum is bounded by 4\sum_{1\le k\le n/4}p(k)/\binom nk. Each term vanishes at fixed k and is bounded by 4p(k)4^{-k}; the remaining contribution is at most p(n)e^{-n/100}=o(1). This proves both assertions about inverse-first sums.□

Proof. The partition bounds give \log M(k)=O(\sqrt k\log(k+1))=o(k). For k>n/4, Lemma 6.4 gives \log D_\lambda\ge n/100, whereas \log M(k)=o(n) uniformly for k\le n. For k\le n/4, use D_\lambda\ge\frac12\binom nk\ge\frac12 4^k once k exceeds a fixed sufficiently large cutoff. The finitely many positive k below that cutoff are handled by the uniform divergence of \binom nk. One size threshold works for all shapes.□

Proof. We use the polytabloid realization of the Specht module of shape \lambda; see [13, 4]. Fix a labeling of its boxes. A row tabloid remembers which labels lie in each row while forgetting their order within that row; its polytabloid is the signed sum of its translates under the column stabilizer. Assign every box either to its row or to its column. Let R permute the assigned set in each row and let C permute the assigned set in each column. These sets are disjoint, so J=R\times C. Give R the trivial character and each factor of C the sign character.

Let e be the polytabloid of the labeled diagram. It transforms by sign under the full column stabilizer, hence under C. The average v=|R|^{-1}\sum_{r\in R}re is fixed by R and still transforms by sign under C. It is nonzero. Indeed the original row tabloid has coefficient one in e, since the full row and column stabilizers intersect trivially. Every element of R fixes that tabloid, so its coefficient is also one in v. This proves character occurrence for every assignment.

It remains to choose the assignment with controlled index. The arm and leg of a box count boxes strictly to its right and strictly below it. Assign a box to its row when its arm is at least its leg, and to its column otherwise. Its hook length is at most twice the length l of the line receiving it. If that line receives a boxes, then a!\ge(a/e)^a; we give a line with a=0 zero contribution below. Consequently

Here a\log(l/a)\le l/e and the total length of all rows and columns is 2n. The hook-length formula therefore gives an assignment with index

We convert the exponential factor into a power of D. Put L=\max(\lambda_1,\lambda'_1). Suppose first that n\ge64 and L\le3n/4. If L\le n/8, all hooks are at most 2L, and D\ge(n/(2eL))^n\ge(4/e)^n\ge e^{n/64}. Otherwise transpose so that the first row has length L, and retain a Young order ideal of s=\lfloor L/4\rfloor boxes below it. Such an ideal exists because n-L\ge L/3; moreover s\ge n/64. For the retained diagram, let c_j count its lower boxes in column j. Dividing its hook formula by the lower diagram’s formula gives

The first inequality also uses extension of tableaux from a subdiagram. For the second, c_j=0 for j>s and \sum_jc_j=s. Since s\le L/4, the logarithm of the last expression is at least s\log5-s/(L-s+1)\ge s. Thus \log D\ge n/64 throughout this case. Equation (7.1) now gives I\le D^{193}.

Suppose instead that L>3n/4. Orient a longest line as the top row, of length L, and write \zeta for the lower diagram of size s=n-L. Assign the entire top row to its row and use the preceding arm–leg assignment on \zeta. Hook comparison and (7.1) applied to the tail give

If s\ge1, then \binom ns\ge(n/s)^s\ge4^s and L-s+1\ge2. Hence

These bounds imply I\le D^{1024}. Transposing the assignment back preserves the subgroup index and interchanges trivial and sign factors. If s=0, take the full group and its trivial or sign character. Finally, for n<64 and D>1, the trivial subgroup has index n!\le64^{64}<2^{1024}\le D^{1024}. Degree-one representations again use the full group. This covers every case.□

Proof. Define the complex mass function e_{J,\chi} to be \overline{\chi(j)}/|J| on J and zero elsewhere. Its Fourier transform is the orthogonal projection P onto vectors satisfying \rho(j)v=\chi(j)v for all j\in J. With U_H,U_J denoting uniform probability masses on the subgroups, positivity gives

Plancherel therefore implies D\|\widehat f(\rho)P\|_{\HS}^2\le IBz. Every conjugate of (J,\chi) inside H satisfies the same bound.

Average the corresponding projections, writing \overline P=|H|^{-1}\sum_{h\in H}\rho(h)P\rho(h)^*. On the full H-isotypic space V_\eta\otimes\mathcal A_\eta, a group-algebra element acts on V_\eta tensored with the identity on the multiplicity space \mathcal A_\eta. Schur’s lemma thus gives

These scalars are nonnegative and the scalar for \eta=\tau is at least 1/d_\tau. Hence \overline P\ge d_\tau^{-1}Q_\tau. Test this positive-operator inequality against \widehat f(\rho)^*\widehat f(\rho), and average the preceding Plancherel bounds. The result is (7.2).□

Proof. For each type \tau of H_i, Lemma 7.2 and the assumed subcharacter give

Restrict \rho to the product of the H_i. In any occurring joint type, the product of the factor dimensions is at most D, including when that type has multiplicity greater than one. Some factor therefore has dimension at most R=D^{1/b}. The sum of the commuting projections Q_{i,\tau} with d_\tau\le R dominates the identity. Taking its trace against \widehat f(\rho)^*\widehat f(\rho) gives

The last inequality uses d_\tau^{a+1}\le R^{a+2}d_\tau^{-1}. Lemma 7.1 supplies a=1024.□

Proof. By branching, a type of H_i has shape \nu\subseteq\lambda and size |M_i|. Orient \lambda so that a longest line is a row. Every such \nu has at most k boxes below its first row. For a fixed lower size j, the lower partition determines the first row because |\nu|=|M_i| is fixed. There are therefore at most M(k) possibilities for each factor. If the longest line was a column, transpose all diagrams. This proves (8.2); absent tuples only reduce the count.

There are at most 2p(k) ambient diagrams with this deficit. The partition bound p(j)\le e^{3\sqrt j} gives, for a constant C_b,

By Theorem 6.3, D_\lambda\ge c_1e^{c_2k} and, at each fixed positive k, the dimensions tend uniformly to infinity. Thus the contribution at deficit k is bounded by c_1^{-\eta}e^{C_b\sqrt k-\eta c_2k}, a summable sequence, and tends to zero for fixed k. Dominated convergence proves (8.3). Multiplicities do not affect either counting step.□

Proof. First let v lie in a single H_i-isotypic space of type \tau_i. The orbit span W=\Span\{\rho_\lambda(h)v:h\in H_i\} has dimension at most d_{\tau_i}^2. To see this in the presence of multiplicity, write the full H_i-isotypic space as V_{\tau_i}\otimes\mathcal A; the orbit lies in the image of the linear map A\mapsto(A\otimes I)v from \operatorname{End}(V_{\tau_i}).

For a test vector w,

The squared projected norm is constant on each gH_i, and its uniform mean is (\dim W/D_\lambda)\|w\|^2: the average of the conjugate projections is scalar by Schur’s lemma, and its trace is \dim W. Cauchy–Schwarz for the mass function f, followed by its coset cap, gives

Thus this single-type bound holds before any joint decomposition. In a joint type of (8.1), the factor degrees satisfy \prod_i d_{\tau_i}\le D_\lambda, since the entire tensor representation occurs at least once. Choose i with d_{\tau_i}\le D_\lambda^{1/b} and apply the preceding bound. For an arbitrary v, decompose it into its K_\lambda orthogonal joint components and sum their bounds. Their norms have sum at most \sqrt{K_\lambda}\|v\|, proving (8.4).□

Proof. Theorem 8.2 gives \|\widehat f(\lambda)\|_{\op} \le\sqrt{2K_\lambda}D_\lambda^{-1/4}, and Lemma 8.1 gives \log(2K_\lambda)=O(\sqrt k). We verify directly that \log D_\lambda/\sqrt k\to\infty uniformly over k\ge1.

Orient a longest line as the first row, of length a=n-k. For 1\le k\le n/3, the tableau construction of Lemma 6.1 gives

For k above a fixed cutoff, divide the logarithm by \sqrt k and use (n-k)/k\ge2; for the finitely many smaller positive k, the same expression tends to infinity with n. For k>n/3 and a\le n/10, the hook formula gives D_\lambda\ge(n/(2ea))^n\ge(5/e)^n. If instead a>n/10, retain the first row and r=\lfloor a/2\rfloor lower boxes; there are enough lower boxes because k>n/3>a/2. Their tableaux extend to the full diagram, and the same construction gives D_\lambda\ge\binom ar\ge2^r\ge e^{cn} for an absolute c>0 and all large n. This proves the asserted uniform divergence. Consequently 2K_\lambda\le D_\lambda^{1/4} eventually, which yields the displayed operator bound.□

Proof. Here the joint-type estimate is \sqrt{2K_\lambda}D_\lambda^{-3/8}. For k\le n/3, use K_\lambda\le M(k)^8 and D_\lambda\ge\binom{n-k}k exactly as above to get \log(2K_\lambda)/\log D_\lambda\to0 uniformly. For k>n/3, the equal block sizes give the coarser count K_\lambda\le p(n/8)^8, whose logarithm is O(\sqrt n). Let a again be the longest line. If a\ge n^{3/4}, retain that line and r=\lfloor a/3\rfloor lower boxes, possible because k>n/3>a/3. Tableau extension gives D_\lambda\ge\binom ar\ge3^r, so \log D_\lambda\ge c n^{3/4}. If a<n^{3/4}, all hooks are at most 2n^{3/4}, and

Thus 2K_\lambda\le D_\lambda^{1/4} uniformly for all large n, and the result follows.□

Proof. Use densities A=|S_n|\alpha and B=|S_n|\beta with respect to uniform probability on G=S_n. Write \int_G and \int_{H_i} for normalized counting averages. The two caps read

Indeed these averages are respectively [G:H_i]\alpha(H_i g) and [G:H_i]\beta(gH_i). The density transform \int_G A(g)\rho_\lambda(g)\,dg equals the mass transform \widehat\alpha(\lambda), and similarly for B. These conventions give \widehat{\beta*\alpha}=\widehat\beta\widehat\alpha.

For a type \tau of H_i of degree d_\tau and character \chi_\tau, its full isotypic projector is

Centrality makes this scalar on each irreducible carrier, and character orthogonality identifies the scalar as one on type \tau and zero otherwise. It acts as the identity on all multiplicity copies of \tau. Consider the density

Weighted Cauchy–Schwarz and nonnegativity give

The first factor is at most B_L. The average over G of the second factor is a\int_{H_i}|\chi_\tau|^2=a. The Fourier matrix of C is P_{i,\tau}\widehat\alpha(\lambda). Plancherel, retaining the \lambda term, therefore yields

For the second inequality use d_\tau\int_{H_i}\overline{\chi_\tau(h)}B(gh^{-1})\,dh, whose transform is \widehat\beta(\lambda)P_{i,\tau}, and the second cap in (8.7).

The projectors for the different disjoint factors commute, and Q_{\boldsymbol\tau}=\prod_iP_{i,\tau_i} are the orthogonal joint projections in (8.1). On a nonzero joint space, \prod_i d_{\tau_i}\le D_\lambda, so some d_{\tau_i}\le D_\lambda^{1/b}. Since Q_{\boldsymbol\tau}\le P_{i,\tau_i}, the two bounds in (8.8) imply

Sum over the K_\lambda joint types before squaring, and then multiply by D_\lambda. This gives (8.6). The factor K_\lambda^2 is retained; no multiplicity-free restriction has been assumed.□

Proof. Use Lemma 8.1 with \eta=1-4/b>0 in Theorem 8.5. It makes the sum of the nonlinear Plancherel terms for \beta_n*\alpha_n tend to zero. Its trivial coefficient is the product of the two masses, tending to one. Domination bounds the error in each sign coefficient by the corresponding lost mass, so its sign coefficient also tends to zero. Lemma 2.4 now gives convergence to uniform in \ell^1. Finally, \beta_n*\alpha_n\le\nu_n*\mu_n and the difference has mass one minus the product of the retained masses. Adding that mass proves the conclusion.□

Proof. We first bound the deleted mass, then use each of the sixteen quotient caps on its corresponding factor. Write

On an atom with q_i(a,b)>(1+\varepsilon)/L_i, its positive excess over uniform is at least \varepsilon q_i(a,b)/(1+\varepsilon). Summing over such atoms and then averaging over a gives

Every T_i is row- and column-substochastic. A uniform starting distribution remains dominated by uniform after any product of these kernels. The average mass lost in T is consequently at most \Gamma=\sum_i\gamma_i. Also 0\le T\le K^{16} entrywise. The triangle inequality followed by Cauchy–Schwarz over all |\Omega|^2 entries gives

Fix i and first decompose only under H_i. Each quotient fiber is a regular H_i-set. After choosing one representative per fiber, the block of T_i between fibers a,b is convolution by nonnegative weights of total mass

On the multiplicity space of a regular-fiber type \alpha, of degree f_\alpha, this block is a weighted sum of unitary f_\alpha by f_\alpha matrices. Its Hilbert–Schmidt norm is at most \sqrt{f_\alpha}\,t_i(a,b). Since each row of t_i has mass at most one, the cap gives

Now decompose under the whole product H. Its \boldsymbol\alpha-isotype is

Viewed only as an H_i-space, it contributes D/f_i copies of \mathcal M_{\boldsymbol\alpha} to the multiplicity of \alpha_i. Thus (9.7) implies

Multiplying these inequalities and using Hilbert–Schmidt submultiplicativity proves (9.4).

For u>0, write \mathcal Z_u(m)=\sum_{\alpha\in\widehat S_m}(\dim\alpha)^{-u}. The degree estimate of Theorem 6.3 gives \mathcal Z_{13}(m)\to2. The total squared Hilbert–Schmidt contribution of all product types with D>1 is therefore at most

The subtracted types are precisely the products of trivial and sign representations, since eventually every m_i\ge2.

It remains to handle these 2^{16} scalar carrier types; their multiplicity spaces have not been discarded. If a product type has a sign coordinate i, its T_i block has squared Hilbert–Schmidt norm at most \beta_i by (9.3). All the other factors are operator contractions. Hence its product block has squared Hilbert–Schmidt norm at most \beta_i. The sum over these finitely many types tends to zero.

For the all-trivial type, let T_{i,0} be its multiplicity operator and let u=|\Omega|^{-1/2}\mathbf1 be the constant vector in that space. The restriction of U_\Omega is P_u=uu^*. Equation (9.7) for the trivial H_i type gives \|T_{i,0}\|_{\mathrm{HS}}^2\le1+\varepsilon, whereas

Consequently

Telescoping the product against P_u^{16}=P_u, with operator contractions on either side of each difference, gives

This is a bound on the entire all-trivial multiplicity space.

The three estimates prove \|T-U_\Omega\|_{\mathrm{HS}}\to0, so (9.6) proves average mixing. Finally, equivariance under a transitive group makes all row distances of K^{16} from uniform equal. That additional symmetry gives the worst-start conclusion.□

Proof. For fixed s, the entries of each q_i sum to one. The same is true for fixed s' by (9.11). Therefore the positive excess over uniform in either a quotient row or a quotient column is at most \delta. On an atom exceeding twice uniform, its mass is at most twice its positive excess. Each cutoff loses at most 2\delta in every row and column. Taking the union of the three deleted sets proves the loss bound 6\delta. The retained kernel is row- and column-substochastic, so its blocks are operator contractions. Also its ith quotient marginal is everywhere bounded by 2/M_i: an original atom above that value has been entirely deleted.

We check the Fourier orientation before estimating the blocks. The unitary regular decomposition of the right H-action has carrier V_\rho and multiplicity D on each fiber s. In the matrix-coefficient basis \rho(g^{-1})_{ab}, left multiplication g\mapsto hg replaces

For each fixed carrier index a, the index b, together with s, is therefore acted on by (9.15). Each such matrix occurs D times. In particular composition of the deck kernels gives powers of B_\rho, with no adjoint or reversal of the factors.

Fix s,s' and an index i. First sum over its group coordinate:

The quotient cap and unitarity give \|F(h_{-i})\|_{\mathrm{HS}}\le2\sqrt{D_i}/M_i. Applying Plancherel entry by entry on H_{-i} yields

Keep the term \sigma=\bigotimes_{j\ne i}\rho_j and sum over the M^2 pairs (s,s'). A unitary permutation of tensor factors identifies the resulting matrix with B_\rho, proving the first bound in (9.16). Choose an index with D_i\le D^{1/3}. Then

Hilbert–Schmidt submultiplicativity suffices here; no normality is assumed. By Theorem 6.3, the sum over D>1 is at most

We have controlled every carrier of dimension greater than one. The eight scalar carriers remain: one is all-trivial, six contain both a trivial and a sign factor, and one is all-sign. In every case the corresponding M by M matrix has Hilbert–Schmidt norm at most two, by (9.16).

Consider first one of the six mixed types. Choose an index i where \rho_i is trivial, so that its matrix entries are the signed sums of the retained marginal \widetilde q_i. Replacing that marginal by 1/M_i gives zero, since at least one of the other two factors is sign and its group sum vanishes. In each row and column,

Thus B_\rho has absolute row and column sums at most 8\delta, and the same Cauchy–Schwarz argument used for nonnegative kernels, applied to absolute entries, gives \|B_\rho\|_{\mathrm{op}}\le8\delta. Hence

For the all-trivial type, uniform replacement instead gives the matrix J with every entry 1/M. Write B_0=J+E. The preceding row and column estimate gives \|E\|_{\mathrm{op}}\le8\delta, while \|E\|_{\mathrm{HS}}\le\|B_0\|_{\mathrm{HS}}+\|J\|_{\mathrm{HS}} \le3. Expand (J+E)^{15} into ordered words. The word containing only J equals J, because J is an orthogonal projection. Every word containing both letters has a factor J of Hilbert–Schmidt norm one and at least one factor E of operator norm at most 8\delta, so its Hilbert–Schmidt norm tends to zero. The word E^{15} has norm at most 3(8\delta)^{14}. There are only 2^{15} words. This proves

without bounding the size M of the trivial multiplicity space.

Finally consider the all-sign type. Its untrimmed matrix is A_\chi. Deleting at most 6\delta mass from each row and column changes each corresponding absolute sum by at most 6\delta. Consequently

This is precisely where the separate all-sign hypothesis is used.

The uniform kernel has only the all-trivial block J. Summing all blocks with their carrier multiplicities D now gives \|\widetilde K^{15}-U_\Omega\|_{\mathrm{HS}}=o(1). For all sufficiently large members of the sequence 6\delta<1. Every row of \widetilde K^{15} has mass at least (1-6\delta)^{15} and is dominated by the corresponding row of K^{15}. Thus, as in (9.6),

The final transitive-equivariance assertion follows because the untrimmed kernel then has the same row distance at every state.□

Proof. Put a=1/8 and K_i=H_{R_i}. Fix an irreducible \rho of degree D>1. Every tensor type in its restriction to \prod_iK_i has product of factor degrees at most D. Assign each entire isotypic space to one factor whose degree is at most D^{1/b}. This yields an orthogonal decomposition of any unit vector v as v=\sum_i v_i, where v_i contains only these small K_i-types. For W_i=\operatorname{span}\rho(K_i)v_i, Lemma 3.1 counts each type once, including all its multiplicities. Together with Lemma 6.4, it gives

For fixed unit u,v, the score

depends only on g_{-R_i}. Its uniform second moment is \dim W_i/D by Schur averaging [4, Proposition 3.14]. Consequently

If |\langle u,\rho(g)v\rangle|>D^{-a}/2, at least one score exceeds D^{-a}/(2b), because \|v_i\|\le1 and |\langle u,\rho(g)v_i\rangle|\le H_{\rho,u,v,i}(g).

Start with the measure \nu=\mu_n. Whenever its claimed operator bound fails, choose \rho,u,v with |\langle u,\widehat\nu(\rho)v\rangle|>D^{-a}, record this test, and delete all remaining mass on

The mass deleted is greater than D^{-a}/2: outside this event the coefficient has absolute value at most D^{-a}/2, everywhere it has absolute value at most one, and the current measure has mass at most one. Since all deleted pieces are disjoint, any one representation of degree D can be selected at most 2D^a times. There are finitely many irreducibles, so the procedure terminates with all the required bounds. The choices are made from deterministic current measures; thus the eventual finite list of tests is fixed, not selected anew for a sampled permutation.

For each i, let E_i be the union of its score events in (10.1) over the complete list of recorded tests. It is a single event determined by g_{-R_i}. Counting tests for each representation gives

by Theorem 6.3. Apply the marginal hypothesis to this entire union to get \mu_n(E_i)\le U_n(E_i)+\delta_n. Every deleted point belongs to some E_i, so the total mass loss is at most \sum_i\mu_n(E_i)=o(1). This proves the theorem.□

Proof. For any probability a and uniform probability b on a finite set,

Apply this to each restriction law. Under g\sim\mu, the expected fraction of sets with e_R(g)=0 is at most 2\delta. Markov’s inequality gives \mu(E^c)\le16\delta. Conditioning on E changes the law in total variation by exactly \mu(E^c).

Conjugating H_R by a\in S_n replaces it by H_{aR} and conjugates P_R by \rho(a). Hence the average projection commutes with \rho(S_n) and is scalar. To estimate its trace, choose one partition (R_1,\ldots,R_q) into equal blocks. The restriction of V to \prod_iH_{R_i} is an orthogonal sum of tensor types, with arbitrary multiplicities. If a type has factor degrees d_1,\ldots,d_q, then \prod_i d_i\le D, since at least one copy of that type occurs in V. Consequently at most 1/\xi factors have degree greater than D^\xi. On this tensor type, I-P_{R_i} is either the identity or zero according to that inequality. Summing traces, including multiplicities, gives

All these ranks agree by conjugacy. This proves (10.2). Commutation was used only for the disjoint subgroups in this rank calculation.

For the orbit bound, Lemma 3.1 gives, with all multiplicities included,

which is (10.3).

It remains to turn the orbit estimate into a coefficient estimate. The space W=W_R(z) is H_R-invariant, so \rho(g)W depends only on gH_R. For unit u, Schur averaging and the trace give

On a coset with e_R=1, the \nu-mass is at most four times its uniform mass: the original cap is two and normalization costs at most two. Since |\langle u,\rho(g)P_Rz\rangle|\le \|\operatorname{Proj}_{\rho(g)W}u\|, Cauchy–Schwarz gives

This proves (10.4).□

Proof. Suppress n, fix \rho, and use Lemma 10.2 with q=1024 and \xi=1/16. Thus c\ge63/64, and the right side of (10.4) is A D^{-3/8}, where A=2\sqrt{C_2}. For g\in E define

The equality for F_g uses the scalar identity \E_RP_R=cI; it does not require the individual projections to commute. These are positive operators, and \|F_g\|_{\op}\le1/(8c). Put s=\lceil\log D\rceil, with natural logarithms. The finite identity

holds because Q_g/c=I-F_g.

We now bound the expected coefficient of each term while preserving its projection order. For fixed unit vectors u,w, the jth summand in (10.5) expands as an average over independently chosen R_0,\ldots,R_j, with scalar factor c^{-(j+1)}, indicator

and vector P_{R_0}P_{R_1}\cdots P_{R_j}w. Fix the sets before integrating over g. The vector z=P_{R_1}\cdots P_{R_j}w is then deterministic with norm at most one. Take absolute values and discard the failure indicators for i\ge1. Equation (10.4) now bounds the expected coefficient by c^{-(j+1)}AD^{-3/8}. In particular the argument never exchanges two projections.

The remainder has norm at most (8c)^{-s}. Summing gives

For the last inequality, c^{-s}\le c^{-1}D^{\log(1/c)} and \log(1/c)\le\log(64/63)<1/32; the remaining logarithmic factor is absorbed by D^{3/32}. Also \log(8c)>1/4. Taking the supremum over the unit vectors proves the operator bound.

To obtain the convolution conclusion, the sign coefficient of \nu_n is o(1), since the original sign coefficient is o(1) and \|\nu_n-\mu_n\|_{\TV}=o(1). Plancherel and \|B\|_{\HS}\le\sqrt D\|B\|_{\op} yield

by Lemma A.2. Replacing the eight independent factors \nu_n by \mu_n costs at most 8\|\nu_n-\mu_n\|_{\TV}=o(1).□

Proof. Use Lemma 10.2 with q=256 and \xi=1/16. In particular c\ge15/16. For a retained permutation put

Removing at most 1/8 of the projections from their scalar average gives

For fixed unit vectors u,v and every integer p\ge1,

Indeed, expand M_g^p over R_1,\ldots,R_p in that order. After taking absolute values, retain only the indicator e_{R_1}(g). For the fixed sets, apply (10.4) to the deterministic vector z=P_{R_2}\cdots P_{R_p}v, of norm at most one. This proves (10.7), even when the omitted sets overlap.

The estimates for positive powers must now recover the original vector. Put L=\lfloor(\log_2D)/8\rfloor. The identity

holds also when L=0, with an empty sum. Its remainder has norm at most 2^{-L} by (10.6). Expand each M_g(I-M_g)^j as a polynomial in M_g. The absolute values of its coefficients sum to 2^j, so (10.7) gives

Here 2^{-L}\le2D^{-1/8} and 2^L\le D^{1/8}, including L=0. This proves the asserted operator bound.

The sign coefficient is again o(1). For 32 factors the remaining Plancherel sum is at most

because D^{-6}\le D^{-2} and Lemma A.2 applies. The total-variation cost of replacing the 32 factors is at most 32\|\nu_n-\mu_n\|_{\TV}=o(1). Finally Pinsker’s inequality and Jensen’s inequality give

which proves the entropy version. In this normalization Pinsker’s inequality reads \|p-u\|_{\TV}^2\le D(p\|u)/2. To check the factor, take A=\{p\ge u\}, set a=p(A) and b=u(A), and group the entropy sum over A and its complement. The log-sum inequality gives D(p\|u)\ge D(\operatorname{Ber}(a)\| \operatorname{Ber}(b)). As a function of a, the binary relative entropy on the right vanishes with zero derivative at a=b and has second derivative 1/[a(1-a)]\ge4. It is therefore at least 2(a-b)^2=2\|p-u\|_{\TV}^2, with boundary cases obtained by limits.□

Proof. Put b=128. The claim for D=1 follows by increasing C, so assume D>1. Fix u,z and let A be the event on the left side of (11.2). There is nothing to prove if \mathbb P(A)=0. Otherwise set \sigma=\mathbb P(\,\cdot\mid A). Then \sigma is supported on the same \mathcal G as in the hypothesis, and

The reference law here remains \mathbb P, not \mathbb P(\,\cdot\mid\mathcal G). Thus this identity controls the unconditioned probability of A; the factor a^{-1} enters only when we pass to the endpoint law \eta at the end. Our goal is to lower-bound this entropy by a positive multiple of \log D. We do so using tests visible from complementary restrictions.

Fix an ordered partition (C_1,\ldots,C_b) of [n] into equal blocks. Let X_i=[n]\setminus C_i and K_i=\Sym(C_i). On V_\rho, let S_i project onto the sum of the K_i-isotypic spaces with type degree at most D^{1/b}. The subgroups K_i commute, as do their isotypic projections. On each tensor type in the product-group restriction, the product of its factor degrees is at most D. At least one factor is therefore at most D^{1/b}, giving

Consequently

Let W_i=\operatorname{span}\{\rho(h)u_i:h\in K_i\}. Lemma 3.1 bounds its dimension by the sum of the squared type degrees, independently of their multiplicities. Lemma A.1 supplies the finite constant

It follows that

where the sum counts irreducible types once, not their multiplicities.

Because W_i is K_i-invariant, \rho(g)W_i depends only on g|_{X_i}. Let E_i be the subset of injections on X_i for which

Schur averaging gives uniform mean square projection length \dim W_i/D. Markov’s inequality and (11.6) imply

For each endpoint on A, the coefficient threshold and (11.5) force at least one of these tests:

Thus, for this partition,

We have found complementary restrictions on which \sigma assigns substantial mass to events that are rare under the uniform law. To convert that fact to entropy, put p_i=\sigma_{X_i}(E_i) and q_i=U_{X_i}(E_i). Data processing for the binary test gives

The first inequality follows by expanding binary relative entropy and using that binary Shannon entropy is at most \log2; its term (1-p_i)\log(1/(1-q_i)) is nonnegative. Empty tests have p_i=q_i=0 and satisfy the displayed bound as well. The second inequality uses (11.7) and 0\le p_i\le1.

Average over i, using (11.8), and then over uniform ordered equal-block partitions. Each X_i is uniform of size n-n/b, so

Now apply (11.1) to this particular \sigma. Together with (11.4), it gives

This proves (11.2), for example with C=2eC_{20}b^2.

Finally the absolute coefficient is at most one. Split its expectation under \mathbb P(\,\cdot\mid\mathcal G) at D^{-1/8}, and use (11.2) for the upper part. This proves (11.3) after taking the supremum over the unit vectors. All partitions and tests in the proof were chosen after u,z were fixed; the hypothesis covering every law on the common event is what permits the rare-event conditioning at the first step.□

Proof. The event \mathcal G and the retained endpoint law \mu are fixed before choosing the palette. Fix now a palette on B and a coset xH, and put E=\mathcal G\cap\{g\in xH\}. If P(E)=0 the conclusion is immediate. Otherwise write Q=P(\,\cdot\mid E). The three laws are related by

Choose the reveal order independently of the setting, using the AB convention under both P and Q. Since E does not involve the order, conditioning the setting on E leaves this order uniformly distributed. For a fixed order, data processing followed by the entropy chain rule gives

For labels in A, membership in xH prescribes a singleton target; for a label in B_i it prescribes the target set xB_i. At a history that occurs under Q, let a_r\ge1 be the number of unoccupied sites in this target. The next endpoint lies in that target with Q-probability one. For any probability R supported on an event F of positive reference probability, the identity D(R\Vert P')=D(R\Vert P'(\,\cdot\mid F))-\log P'(F) shows that its entropy is at least -\log P'(F). Apply this observation to the next observation and then use (12.1). Since m=n-r\le n,

This lower bound is valid even when the displayed upper bound on the reference probability exceeds one. Averaging the chain rule over orders therefore yields

The error bound uses (12.2) pointwise on E. It does not use an average error estimate under P after the change of law to Q.

It remains to count the information lost by omitting the last v labels. If all n labels were revealed, the numerator counts would multiply to n!, while the target counts would multiply to \prod_i l_i!. The full logarithmic sum is consequently \log[S_n:H], independently of the compatible observations. The last v labels are in B. For v=0 the missing contribution is zero. For v>0, if their color counts are t_1,\ldots,t_u, it is

The inequality follows because the multinomial probability of these counts under probabilities t_i/v is at most one. The last v labels form a uniform subset of B under the order average, so \mathbb E_{AB}(t_i/v)=p_i. Concavity of entropy gives expected missing contribution at most v\mathcal H(p). Insert this bound in (12.4), exponentiate, and use \mu(xH)=P(E)/z. The BA order gives the same result for palettes on A. Every error term is independent of the chosen palette and coset, which proves simultaneous uniformity.□

Proof. Transpose the diagram if necessary, so its first row has length L. Apply the first-row hook bound (6.6) with row length L, k lower boxes, and total size b. The dimension of the lower diagram is at least one, so

If k\le b/2, the correction is O(k\log b/b) and \binom bk\ge(b/k)^k, proving the first case. If b/10\le L<b/2, the binomial coefficient has logarithm at least L\log(b/L)\ge(b/10)\log2, and the correction is O(\log b). If L<b/10, every hook is at most 2L<b/5, so D_\gamma\ge(b/e)^b/(b/5)^b=(5/e)^b. These bounds prove the second case and the stated consequence.□

Proof. Starting with \beta, remove a first row or a first column of maximal length, and repeat on the remaining partition until it is empty. The successive lengths are the l_i. Assign a trivial character to a row removal and a sign character to a column removal. If a first row is removed, the remaining partition interlaces the original one: putting back its size is a horizontal-strip addition in the Pieri rule. Transposing gives a vertical-strip addition for a first column. Iterated Pieri, transitivity of induction, and Frobenius reciprocity give the character occurrence. Conjugation supplies every placement.

Let L=l_1 and k=h-L. Every hook in a strip of length l at the time of its removal is at most 2l, because l is the longer of the current first row and first column. Its hook product is at most (2l)^l\le(2e)^l l!. For the first strip use the sharper bound L!e^k, obtained from \log(1+x)\le x and the fact that the sum of the numbers of boxes below the strip is k. Remaining hooks are unchanged by each removal. Thus, if M=h!/\prod_i l_i!, the hook formula yields

To compare this multinomial count with entropy, set f(j)=j\log j-\log j!, with f(0)=0. Then f(j)\ge0 and 0\le f(j)-f(j-1)\le1. Consequently

If k>0, Lemma 12.2 absorbs this total O(k) error into C_0\log D_\beta. If k=0, the representation is trivial or sign, and the one-color palette has entropy zero.□

Proof. Put J=\widehat\mu(\lambda) and D=D_\lambda, using a unitary model \rho_\lambda. We first bound J on each half-isotypic component, including its multiplicities. Combining the halves will bound each joint component; we then absorb the number of joint types into a small power of D. For a type \beta of S_B, choose its signed palette from Lemma 12.3. Equations (12.7) and (12.8) give, for large n,

This holds for every conjugate of the chosen subgroup within S_B.

Let P_{H,\theta} be the orthogonal projection onto the \theta-character space in the restriction to H. Define the signed mass \theta_H to equal \overline{\theta(h)}/|H| on H and zero elsewhere. Right convolution by \theta_H has Fourier matrix JP_{H,\theta}. On a coset xH each resulting mass has absolute value at most \mu(xH)/|H|. Hence

Plancherel, retaining the \lambda term, proves

Let \Pi_{B,\beta} denote the entire \beta-isotypic projection. Average P_{H,\theta} over conjugation by S_B. On the \beta carrier its rank is at least one, so Schur’s lemma makes this average at least D_\beta^{-1}I on that carrier. The group algebra acts as the identity on its multiplicity space. The average is therefore at least D_\beta^{-1}\Pi_{B,\beta} in positive semidefinite order on the full representation. Tracing against J^*J in (12.12) gives

The identical estimate holds for a type \alpha of S_A.

Every constituent of the product of the two halves has a small carrier on at least one side. Indeed, the commuting projections \Pi_{A,\alpha}\Pi_{B,\beta} decompose the identity orthogonally, and every nonzero such component has D_\alpha D_\beta\le D. Use (12.13) for the smaller degree to obtain

We verify that the number of type pairs costs only a vanishing power of D. Let L=\max(\lambda_1,\lambda'_1) and k=n-L>0. Branching forces every half-type diagram to be contained in \lambda. If the longest line is a column, transpose \lambda and every contained half-type diagram for this count. Containment and dimensions are preserved, and each resulting tail beyond the first row has at most k boxes. The number of choices for either half-type is at most B_k=\sum_{j=0}^k p(j), where p(j) is the number of partitions of j. The partition bound (6.1) gives

Lemma 12.2 implies \log B_k/\log D\to0 uniformly: if k\le\sqrt n, its denominator is at least (c_0/2)k\log n, and if k>\sqrt n, it is at least c_1k. Thus B_k^2=D^{o(1)} uniformly over the nontrivial, nonsign diagrams. Orthogonality of the domain projections in (12.14) now yields

for sufficiently large n. This proves both (12.9) and (12.10).

For four factors, Hilbert–Schmidt submultiplicativity, Plancherel and Cauchy–Schwarz give

since the nonlinear sum is Z_{1/3}(n)\to0 by Theorem 6.3. Replacing the four factors by \mu_0 costs at most 4\|\mu_0-\mu\|_{\mathrm{TV}}=o(1). Convolution contracts total variation and preserves uniform measure, so each four-factor conclusion implies its thirty-factor counterpart.

There is also a direct thirty-factor completion using only the operator bound (12.10). It gives

The sum tends to zero. To see this directly, group the diagrams by k=n-\max(\lambda_1,\lambda'_1). There are at most 2p(k) diagrams in each group. Lemma 12.2 gives the summable majorant 2e^{3\sqrt k-8c_1k}, while each fixed k>0 has D_\lambda\to\infty as n\to\infty. Dominated convergence applies. Replacing the thirty factors one at a time changes total variation by at most 30\|\mu_0-\mu\|_{\mathrm{TV}}.□

Proof. For a density p relative to a probability u, the negative part of the logarithm has expectation at most 1/e under pu, since p\max(-\log p,0)\le1/e. Consequently

For each i let p_i be the density of w_{H_i} relative to U_{G/H_i}. Restrict w to those g for which p_i(gH_i)\le e^t for every i, and call the result v. Markov’s inequality and a union bound prove (13.2); the restriction proves (13.3). Zero-density cosets have zero w-mass and create no logarithmic exception.

The convolution \check v*v is the law, with its subprobability mass, of g_1^{-1}g_2. Membership in H_i means that g_1,g_2 belong to the same left coset. Thus

We spell out the isotypic step to show exactly what the collision cap controls. Put E_\lambda=\widehat v(\lambda)^*\widehat v(\lambda). For an irreducible \tau of H_i of dimension d_\tau and character \chi_\tau, let P_{\lambda;\tau}^{H_i} be the full \tau-isotypic projection in \rho_\lambda|_{H_i}, including all multiplicity copies. Fourier inversion and the central projection formula give

Indeed \sum_{h\in H_i}\chi_\tau(h)\rho_\lambda(h^{-1}) =(|H_i|/d_\tau)P_{\lambda;\tau}^{H_i}. Every trace on the right is nonnegative, since E_\lambda and P_{\lambda;\tau}^{H_i} are positive. Since |\chi_\tau(h)|\le d_\tau, (13.4) yields

This is the collision form of Lemma 3.4.

The block subgroups form a direct product. Every irreducible constituent of its restriction has factor dimensions whose product is at most D_\lambda. At least one factor dimension is therefore at most D_\lambda^{1/q}. The commuting isotypic projections satisfy

There are at most C_uD_\lambda^{u/q} such types in each subgroup: each contributes at least D_\lambda^{-u/q} to its inverse-u degree sum. Taking traces against E_\lambda and using (13.7) proves (13.5).□

Proof. Choose the equal partition uniformly. Each block complement is uniform among sets of size n-r. Entropy of an image list is unchanged by reordering its coordinates. Therefore the expected sum of the q complement entropies is at most qK_0; one deterministic partition has sum no greater than that expectation. Agreement on the complement is exactly membership in the same left coset of its block subgroup.□

Proof. Apply Theorem 13.1 with t=d^6 and u=32. The loss bound is O(d^4)/d^6=O(d^{-2}). The logarithm of the prefactor is d^6+\log(256C_{32}), while

The latter eventually exceeds the former, proving the final bound.□

Proof. Apply the clipping construction of Theorem 13.1 with q=16, w=\mu, K=E_n, and t=b_n. It restricts \mu to the event \mathcal G on which all sixteen original quotient densities are at most e^{b_n}. The retained subprobability has mass z\ge1-\eta_n and satisfies every coset cap with constant e^{b_n}. Here \eta_n=o(1) by (14.1), so eventually z\ge1/2. Normalizing this one retained measure increases all caps by the same factor z^{-1}\le2, giving (14.2). Since the construction is an event restriction, its normalization is exactly \mu(\,\cdot\mid\mathcal G), at total-variation distance 1-z from \mu.□

Proof. If both the first row and the first column are shorter than n/8, every hook has length less than n/4. The hook formula then gives D_\lambda\ge(4/e)^n, which suffices. Otherwise transpose if necessary so the first row has length m=\max(\lambda_1,\lambda'_1)\ge n/8. The number n-m of remaining boxes is at least k/2: it is k without transposition, and after transposition the assumed bound on the number of rows gives n-m\ge n/2\ge k/2.

Retain this first row and a Young subdiagram of s=\min(n-m,\lfloor m/2\rfloor) boxes below it. For large n, s\ge k/17. To construct standard tableaux of the retained diagram, put 1,\ldots,s in the first s boxes of its top row. Choose any s of the remaining m labels for the lower diagram, placed in a fixed standard order; fill the remaining top row in increasing order. Every column of the lower diagram is under one of the first s top boxes, so these are valid tableaux. There are \binom ms\ge(m/s)^s\ge2^s choices, and each extends to the full diagram by successively adding the omitted boxes in a Young order. Thus D_\lambda\ge2^s, proving the lemma.□

Proof. Put D=D_\lambda and restrict V_\lambda to H_1\times\cdots\times H_{16}. Its irreducible types are tensor products of sixteen carriers, with arbitrary multiplicities. For an occurring tensor type, the product of its carrier dimensions is at most D, so at least one carrier has dimension at most D^{1/16}. Assign the whole isotypic component of that type to one such index j. This decomposes every unit vector v into an orthogonal sum v=\sum_{j=1}^{16}v_j, where v_j is supported only on H_j-types of dimension at most D^{1/16}.

Branching shows that each H_j-type diagram is a subdiagram of \lambda; its tail below its first row has at most k boxes. Let p(i) count the partitions of i, with p(0)=1. There are at most

such types, by the elementary multiplicity-and-list count in (6.1). Its sharper exponential bound also suffices.

Let W_j be the span of the H_j-orbit of v_j. For one type of degree a, collect all equivalent copies as V_a\otimes\mathcal M_a. The orbit of the component of v_j lies in the image of

Its dimension is at most a^2, regardless of the multiplicity. Consequently

This is the point at which grouping equivalent copies is essential: counting each copy separately would lose the degree saving.

We now use the caps to average these small orbit spaces over the full group. Since W_j is H_j-invariant, the space \rho_\lambda(x)W_j depends only on xH_j. Its projection, averaged uniformly over the group, is (\dim W_j/D)I by Schur’s lemma and the trace. For a unit vector w, Cauchy–Schwarz and the coset cap therefore give

Because \sum_j\|v_j\|\le4, summing yields the quantitative bound

It remains to absorb the growing cap and the type count. Lemma 14.2 gives \log D\ge ck, whereas \log M_n=O(n^{1/50}) and \log B_k=O(\sqrt k\log(k+1)). For k>n^{1/20}, both of the latter quantities are o(k) uniformly. Thus, for large n, \log(16M_nB_k)\le(5/24)\log D. Squaring (14.6) and using this inequality gives 16M_nB_kD^{-7/8}\le D^{-2/3}, as required.□

Proof. Put \sigma=\nu^{*12}*K^{*40}. The Fourier matrices multiply in this order. Each factor is a contraction, since it is an average of unitary matrices. For \lambda'_1\le n/2 and k>n^{1/20}, Proposition 14.3 gives \|\widehat\sigma(\lambda)\|_{\mathrm{op}}\le D_\lambda^{-4}. For more than n/2 rows, (14.8) gives zero. For 1\le k\le n^{1/20}, (14.7) gives \|\widehat\sigma(\lambda)\|_{\mathrm{op}}\le n^{-4k}. These statements use submultiplicativity and do not require normality of any Fourier matrix.

Plancherel bounds four times the squared total-variation distance by \sum_{\lambda\ne(n)}D_\lambda^2 \|\widehat\sigma(\lambda)\|_{\mathrm{op}}^2. For each fixed k, there are at most p(k) diagrams with n-\lambda_1=k, since the boxes below the first row form a partition of k. By Lemma 14.2, the contribution from the large-degree range is at most

For the small-degree range, branching shows that V_\lambda occurs in the permutation representation on ordered distinct k-tuples: its restriction to S_{n-k} contains the trivial representation because its first row has length n-k. Thus D_\lambda\le(n)_k\le n^k, and that contribution is at most

This also explains why no separate sign hypothesis is needed here: the sign diagram has more than n/2 rows and is annihilated by K. The first assertion follows. Convolution contracts total variation, so replacing twelve factors changes the distance by at most 12\|\mu-\nu\|_{\mathrm{TV}}=o(1), proving the second.□

Proof. The subgroup constructed in Lemma 7.1 is a product of symmetric groups on disjoint assigned row or column sets. Those sets partition the m labels, so after omitting empty sets it is conjugate to J=S_{s_1}\times\cdots\times S_{s_r}. The occurring character \chi is trivial or sign on each factor. The full-group and trivial-subgroup choices in that lemma have the same form.

Frobenius reciprocity now places V_\lambda in \operatorname{Ind}_J^{S_m}\chi. Its coset basis is indexed by the ordered set partitions of sizes s_1,\ldots,s_r, and each group element permutes this basis with signs because \chi takes values in \{1,-1\}. It is therefore a signed tabloid representation, with

□

Proof. Fix two tabloids of part sizes s_1,\ldots,s_r, and let E_0 be the event that a permutation takes the first to the second. For buffer B_z, let s_i^z count the elements of the first tabloid’s part i lying in B_z, and set

Relax E_0 by requiring the correct target part only for positions outside B_z. This relaxed event is determined by the corresponding image tuple. Conditional on any successful outside assignment, the unassigned target parts have sizes s_i^z, so a uniform completion succeeds with probability 1/M_z. Since U_E(E_0)=1/M, the relaxed event has uniform probability M_z/M. Its probability under \nu, and hence \nu(E_0), is at most 2M_z/M.

The product \prod_zM_z counts the ways to assign the part names inside the buffers with these fixed counts; all such assignments are among the M unrestricted assignments with totals s_i. Thus \prod_zM_z\le M, and some buffer has M_z\le M^{1/L}. We have proved the uniform entry bound

In the signed tabloid representation, each absolute entry of the averaged matrix is bounded by this probability. Each column has absolute sum at most \nu(S_E)\le1, since every group element acts by a signed permutation matrix. Its squared Hilbert–Schmidt norm is consequently at most 2M^{1/L}.

Choose the signed tabloid containing \gamma from Lemma 15.2. Orthogonal decomposition into irreducibles shows that its squared Hilbert–Schmidt norm bounds the contribution of any one copy of \gamma. Hence

The bound by one follows separately because the average of unitaries against a subprobability is a contraction.□

Proof. The Littlewood–Richardson rule counts certain tableaux of skew shape \lambda/\alpha and content \beta whose reading words satisfy the lattice condition. The word determines the tableau. Every prefix of such a word has weakly decreasing counts of the successive letters. All words of content \beta with this prefix condition are in bijection with standard tableaux of shape \beta: put the successive integers in the next available box of the row specified by the letter. The prefix condition makes each partial shape a partition. There are D_\beta such words, so the multiplicity is at most D_\beta. Interchanging the two factors gives the bound by D_\alpha.□

Proof of Theorem 15.1. Fix an irreducible \rho=\rho_\lambda of S_V, and put D=D_\lambda>1. For almost every z, let

Then

Jensen’s inequality remains valid for a subprobability by adding the zero vector with its missing mass. Since \rho(t_Z) is unitary, for every vector u we obtain

It is enough to bound the positive operator in the right side.

Fix z for the moment. The restriction to H decomposes as

On one occurring block write a=D_\alpha, b=D_\beta and c=c_{\alpha\beta}^\lambda. Because the conditional measure is a product, the block of B_z is exactly

Both factor matrices are contractions. The contribution of this block to B_z^*B_z is therefore bounded in positive-semidefinite order by the operator Q_A whose block is

and which is zero on the other blocks. In particular Q_A commutes with \rho(S_C).

If x and x' have the same ordered inverse images on A, then x'=kx for some k\in S_C. Thus \rho(x)^*Q_A\rho(x) depends only on x^{-1}|_A. It is positive, so the pointwise cap (15.1) gives an operator inequality:

Here P\preceq Q means that Q-P is positive semidefinite; the uniform average is scalar by irreducibility, and its trace determines the scalar. Dropping the A factor instead gives the same estimate with \|B_C(\beta)\|_{\mathrm{HS}}^2/b, using the cap on x^{-1}|_C. Consequently the averaged contribution of this block is bounded by

where Lemma 15.3 supplies the two normalized norms.

The weights cab/D sum to one. For blocks with \max(a,b)\ge D^{1/10}, summing (15.6) therefore costs at most 4D^{-1/20}I. On each remaining block, Lemma 15.4 gives c\le D^{1/10}, so cab/D\le D^{-7/10}. By Theorem 6.3, for all sufficiently large h the number of partitions of h with degree less than D^{1/10} is at most

There are at most 9D^{1/5} such pairs. Their total contribution to (15.6) is at most 18D^{-1/2}I. Thus, uniformly in z,

Insert this into (15.5) and take square roots. This proves (15.3).□

Proof. Write q=\theta(S_{2h}) and j=100. Convolution preserves pointwise domination of nonnegative measures, so \theta^{*j}\le\mu^{*j}, and the missing mass is 1-q^j=o(1). Also

The trivial coefficient of \theta^{*j}-U is q^j-1=o(1), and its sign coefficient is \widehat\theta(\mathrm{sgn})^j=o(1). For all other irreducibles, operator-norm submultiplicativity and \|B\|_{\mathrm{HS}}\le\sqrt D\|B\|_{\mathrm{op}} give

by Theorem 6.3. No normality assumption on the Fourier matrices is used.

Finite-group Plancherel, including the trivial and sign terms, now yields

Cauchy–Schwarz gives vanishing absolute sum of this difference. Adding the nonnegative missing measure of mass 1-q^j proves the asserted total-variation convergence for \mu^{*j}.□

Proof. Orient the first row to have length L=L(\lambda) and put k=n-L. If L<n/8, then D_\lambda\ge(4/e)^n, so the contribution is at most [2(e/4)^{20}]^n=o(1). For L\ge n/8 and k\ge1, (6.6) gives

There are at most 2\cdot2^k shapes at each k. For 1\le k\le\sqrt n, the exponent is uniformly o(1) and \binom nk\ge(n/k)^k\ge n^{k/2}. The contribution is at most

For \sqrt n<k\le7n/8, use \binom nk\ge(8/7)^k and k(1+\log L)/L\le7(1+\log n). This contribution is at most

since 2(7/8)^{20}<1. The full inverse-twentieth sum is uniformly bounded after adjoining the row and column and the finitely many small sizes. Each type of dimension at most R contributes at least R^{-20} to that sum, proving (A.1).□

Initial-row interleavings and diagonals. Orient a longest line as the first row L=n-k. For 1\le k\le n/3, the bound D_\lambda\ge\binom{n-k}{k}\ge2^k and the composition count 2p(k)\le2\cdot2^k give the majorant 2\cdot2^{-k}, with fixed-k divergence. If k>n/3 and L\ge n/8, retain \lfloor L/2\rfloor lower boxes to obtain

If L<n/8, diagonal filling gives D_\lambda\ge2^{3n/4}. The shared summation step completes this hook-free proof.

The alternative diagonal cutoff L<n/4 gives D_\lambda\ge2^{n/2}. For L\ge n/4, retain b=\min(k,\lfloor L/2\rfloor): k\le L/2 gives the same 2^k majorant, while k>L/2 gives the exponential central-binomial bound.□

Initial-row interleavings with factorial or hook tails. At k\le n/4, use \binom{n-k}k\ge3^k, with inverse-square majorant 2(2/9)^k; at k\le n/3, use 2^k and 2\cdot2^{-k}. Either binomial diverges for fixed positive k. The following rows give alternative completions of these near-row bounds. In each middle range retain the first row and b lower boxes:

Every row follows from D_\lambda\ge\binom Lb\ge(L/b)^b. There are enough lower boxes: k>n/4 implies k>L/3, and k>n/3 implies k>L/2; the stated cutoffs also ensure b\le L. The fixed-cutoff rows are exponential in n. Below L=n/10 or n/8, the factorial form of diagonal filling gives, respectively, (5/e)^n or (4/e)^n. These are hook-free completions; using the hook formula gives the same two bounds independently. For the moving cutoff, the middle bound is e^{cn^{0.6}} and hooks below the cutoff give n!/(2n^{0.6})^n. Thus every row completes the inverse-square sum.□

First-row hook ratios. For k\le n/4, (6.7) gives D_\lambda\ge e^{-1}\binom nk, so the inverse-square sum is at most

The summands inside the sum are at most 8^{-k} and vanish at fixed k. In the remainder L<3n/4, use (5/e)^n for L\le n/10; otherwise retain b=\lfloor L/4\rfloor lower boxes. The hook ratio gives D_\lambda\ge e^{-1}\binom{L+b}b\ge e^{-1}4^b, where b\ge n/50 for large n.

Two alternative hook cutoffs retain different quantitative losses. For L\ge n/2, opposite rearrangement gives

for large n. Here use 2p(k)=e^{O(\sqrt k)} for domination; the binomial gives fixed-k divergence. For n/10\le L<n/2, \binom nL is exponential in n and the logarithmic correction is O(\log n); below n/10 use (5/e)^n. Alternatively, split at L=3n/4 and n/8: the first range has short-tail loss k/(L-k+1)\le1, the middle uses the same b=\lfloor L/4\rfloor hook subdiagram, and the last uses (4/e)^n. Each choice proves the limit by the shared summation argument.□

Second-row width and two-row rectangles. Write c=\lambda_2 after orientation. At 1\le k\le n/4,

Its ratio base is at least \sqrt n/2 for k\le\sqrt n and at least three for \sqrt n<k\le n/4, so the composition count gives vanishing geometric sums. In the remainder, hooks handle L<n/10. For L\ge n/10 and c\le L/2,

The middle inequality follows by retaining \min(k,L-c) factors in the binomial product. If c>L/2, the diagram contains a two-row rectangle of width \lfloor n/20\rfloor, whose Catalan number is exponential in n. The subexponential total count finishes. The alternative near-row cutoff k\le n/3 gives majorant 2\cdot2^{-k}; in its remainder n/10\le L<2n/3, the same minimum is at least n/20, and the rectangle may have width c.□

Direct reciprocal bounds by interleaving and ballot words. Interleaving gives D_\lambda\ge\binom{n-k}k\ge3^k on 1\le k\le n/4. Use the sharper deficit count 2p(k)\le2e^{3\sqrt k} to sum 2p(k)3^{-k}. For k>n/4, hooks give 2^n if L<n/(4e); otherwise b=\min(k,\lfloor L/2\rfloor) is a positive linear fraction of n and \binom Lb\ge2^b. Equivalently, split at L=n/8, using b=\lfloor n/16\rfloor above and (4/e)^n below. Both give C_1<\infty and Z_1(n)\to0 without a near-row hook ratio.

Ballot words permit the coarser composition count near a long row. For L\ge n/2, the binomial difference in (6.3) diverges at fixed k, while its Catalan bound is at least 4^k/((k+1)(2k+1)). The reciprocal contribution is therefore dominated by a constant times (k+1)(2k+1)2^{-k}. For n/10\le L<n/2, retain L lower boxes and use their Catalan bound; below n/10, hooks give (5/e)^n.

A quarter-tail ballot completion instead splits at L=n/8 and 3n/4. The first range has hook bound (4/e)^n; in the middle, b=\lfloor L/4\rfloor lower boxes give

exponential in n. For L>3n/4, the ballot fraction is at least 1/2, so D_\lambda\ge\frac12\binom nk\ge\frac12 4^k. The deficit count and fixed-k divergence finish this version as well.□

A reciprocal hook proof. The hook estimates in Lemma 7.1 give D_\lambda\ge e^{n/64} for n\ge64 and L\le3n/4, which beats the subexponential total count. For L>3n/4 and k\ge1,

The composition count gives the reciprocal majorant 2e\,2^{-k}, and the first bound diverges at fixed k. Thus Z_1(n)\to0 and C_1<\infty follow independently from the hook comparisons used to control the subgroup index.□

Proof. If 1\le k\le n/3, the initial-row construction gives D_\lambda\ge\binom{n-k}k\ge2^k, with at most 2\cdot2^k shapes. The contribution is bounded by 2\cdot2^{-(u-1)k}, and each fixed-k contribution tends to zero. For k>n/3 and L\ge n/8, retain \lfloor L/2\rfloor lower boxes to get D_\lambda\ge2^{n/8}/(n+1). The remaining contribution in this range is at most

For L<n/8, diagonal filling gives D_\lambda\ge2^{3n/4}, and the contribution is at most 2^{(1-3u/4)n}=o(1). At u=16 these two bounds are exactly (n+1)^{16}2^{-n} and 2^{-11n}. At u=13 they vanish because 13/8>1 and 39/4>1. The finitely many small-size sums give the uniform constants.□

Proof. Let a be the largest value of i+j-1 over cells (i,j). Diagonal filling gives D_\lambda\ge2^{n-a}. Every cell satisfies ij\le n, so its smaller index is at most \sqrt n and a\le L+\sqrt n. If k<n/2, orient the first row as L. A lower cell satisfies (i-1)j\le k, whence i+j-1\le k+1\le L; thus a=L. If k\ge n/2, then n-a\ge k-\sqrt n\ge k/2 for large n. This proves the first bound in both cases. A non-row, non-column shape contains (L,1) after orientation; that hook has L tableaux, proving the second bound. For each k, at most 2p(k)\le2\cdot2^k shapes occur, so their inverse fourth powers are bounded by 2\cdot2^{-k}. At fixed positive k they tend to zero by D_\lambda\ge\sqrt n. Dominated convergence and the finite-small-size argument finish.□

Proof. Orient the longest line as the first row L\ge\sqrt n. For 1\le k<L/2, use D_\lambda\ge\binom Lk\ge2^k; the contribution at k is at most 2\cdot2^{-9k} and tends to zero for fixed k. For k\ge L/2, retain \lfloor L/2\rfloor lower boxes. The bound D_\lambda\ge2^L/(L+1) gives total contribution at most

This proves the limit and the uniform bound.□

Proof. Orient a longest line as the first row. Put b=\lambda_2 and h=\lambda'_1. For k\ge1, b(h-1)\ge k. If h-1\ge\sqrt k, the diagram contains a hook with row and column length h, because L\ge h. That hook has \binom{2h-2}{h-1}\ge2^{h-1} tableaux. Otherwise b>\sqrt k and the diagram contains a two-row rectangle of width b. Its Catalan number is at least 2^{b-1}: encode the 2^{b-1} compositions of b as distinct Dyck paths obtained by concatenating pyramids of those lengths. In this second case b\ge2, so b-1\ge b/2>\sqrt k/2. Subdiagram extension proves (A.3); the case k=0 is immediate. Finally sum over deficits using at most 2p(k) shapes:

□

A direct fourth-power proof. For power 4, one may also use the near-row majorant 2\cdot2^{-3k} on k\le n/3, the middle bound 2^L/(L+1) on n/8\le L<2n/3, and the hook bound (4/e)^n on L<n/8. This is a different use of the fourth power from the tail-adapted diagonal argument in Lemma A.4. It uses the subexponential total partition count in its last two ranges.□

An arm–leg proof of Lemma 15.2. Transposing \lambda tensors its representation with sign and does not change its dimension. We may therefore orient the diagram so that \lambda_1\ge\lambda'_1, where the prime denotes transpose, and undo this orientation by a sign twist at the end. Let k be its diagonal length, and define

The a_i count horizontal arms including their diagonal boxes; the b_i count vertical legs below those boxes. They sum to m. Use the sizes a_1,b_1,\ldots,a_k,b_k, omitting zero parts, with trivial factors on the arms and sign factors on the legs.

To check occurrence, add arm 1, leg 1, arm 2, leg 2, and so on. Immediately before arm i, rows above i have their final lengths, while row r\ge i has length \min(i-1,\lambda_r). Adding arm i completes row i and is a horizontal strip. Adding leg i then extends column i down to height \lambda'_i and is a vertical strip. Each intermediate shape is a partition. Repeated application of the horizontal and vertical Pieri rules therefore shows that the resulting induced representation contains V_\lambda.

It remains to compare its dimension with D_\lambda. The hook-length formula gives

Here is a direct verification of the identity. The hooks in the diagonal k by k square have lengths a_i+b_j. For any partition with k rows of lengths r_i, allowing zero rows, the hook lengths in row i are the integers from 1 to r_i+k-i with r_i-r_j+j-i omitted for every j>i. Indeed its hook at column t has length r_i-t+1+\#\{j>i:r_j\ge t\}; the gaps as t increases are precisely those omitted values. Apply this observation to the diagram to the right of the square, whose row lengths are \lambda_i-k, and to the transpose of the diagram below it, whose row lengths are \lambda'_i-k. Their hook products are, respectively,

Division by \prod_i a_i!b_i! proves (B.1).

When k=1, orientation gives a_1\ge b_1+1, so the ratio in (B.1) is at most two. A one-row diagram has M=D_\lambda=1. Every other such hook has D_\lambda\ge2, since the entry 2 can be placed either to the right of or below 1 and the resulting partial tableaux can be completed. The claimed bound follows in this case.

Assume now that k\ge2. All logarithms in this proof are natural. Arithmetic–geometric mean bounds the numerator in (B.1) by (m/k)^{k^2}. The two sequences a_i and b_i are strictly decreasing integers, so their two Vandermonde products are at least \prod_{j=1}^k((j-1)!)^2. For 1\le j\le k,

To see this, sum \log(r/k) for 1\le r<j, and bound that sum below by the sum for 1\le r\le k, which is at least -k by k!\ge(k/e)^k. Consequently

We need two lower bounds on D_\lambda to pay for this ratio. Every standard tableau of a contained diagram extends to \lambda by adding the remaining boxes in a fixed order compatible with rows and columns. In particular the contained k by k square gives

It follows that

For k\ge64 the displayed factorial estimate proves this directly. For 2\le k<64, the contained two-square gives D_\lambda\ge2, and 10^{-5}63^2\log63<\log2 suffices.

Orientation also gives a_1\ge m/(2k), since every arm and leg has size at most a_1. The diagram contains (a_1,k,\ldots,k) with k rows. Fill its first k top-row boxes with the smallest entries. Then interleave the rest of the top row with any fixed standard order of the k(k-1) lower boxes. Each interleaving is a standard tableau, so

If m\ge16k^3, put r=m/k^3, u=a_1-k and v=k(k-1). Then u\ge m/(4k) and k^2/2\le v\le k^2. Using \binom{u+v}{v}\ge((u+v)/v)^v gives

If m<16k^3, then \log(m/k^2)+3\le13\log k, and (B.2)–(B.3) give \log M\le(1+13/c_0)\log D_\lambda. If m\ge16k^3, write \log(m/k^2)+3=\log(m/k^3)+\log k+3 and use both degree bounds. This gives

Both coefficients are less than 2{,}000{,}000, completing the proof.□

Proof. Let p(u) count partitions of u, with p(0)=1. For u\ge1, evaluating its generating product at x=e^{-1/\sqrt u} gives

Thus p(u)\le e^{3\sqrt u}. Orient \lambda so that \lambda_1\ge\lambda'_1, and use the preceding arm–leg construction with a_1=\lambda_1 and j=m-a_1. For 1\le j\le m/2, at most 2p(j) original diagrams have this value: delete the oriented first row, and remember whether a transpose was used. The tabloid dimension satisfies M\ge\binom mj, and that construction gives

For each fixed j\ge1 this tends to zero. Since \binom mj\ge(m/j)^j\ge2^j on this range, the summable sequence 2p(j)2^{-js/C_0} dominates the contributions. They therefore sum to o(1).

If j>m/2, every arm or leg used in the tabloid has size at most a_1<m/2. Add some of these parts until their total w first reaches m/4. Then m/4\le w\le3m/4 and

The total contribution of this range is at most p(m)(4/3)^{-ms/(4C_0)}=o(1). The omitted j=0 diagrams are the row and column, whose representations are trivial and sign. They are the only one-dimensional representations for m\ge2, and their contribution to the inverse-first-degree sum is two.□

Proof. Let P_i now select factor degrees at most D^{1/8}. At most eight factors of any product type can exceed that threshold, so \bar P=32^{-1}\sum_iP_i\succeq3I/4. Lemma 4.1, the coset cap, and full-group Schur orthogonality give

Here the selected coefficient space has dimension at most C_1D^{3/8}. Thus \|\widehat fP_i\|_{\op}\le2\sqrt{C_1}D^{-5/16}. Average over i and multiply by \bar P^{-1}, whose norm is at most 4/3.□

Proof. Let P_i select degrees at most D^{2/b}. At least half the factors of every product type meet this condition, so \bar P=b^{-1}\sum_iP_i\succeq I/2. A vector in the range of P_i has orbit span of dimension at most C_{32}D^{68/b} by Lemma 3.1. The coset cap and Schur averaging, exactly as in Proposition 3.2, give

since 68/256\le1/2. Average and use \|\bar P^{-1}\|_{\op}\le2. This proof retains the geometric averaging mechanism and only uses the reciprocal power 32.□

Proof. Decompose a vector orthogonally into full product types v=\sum_{\boldsymbol\tau}v_{\boldsymbol\tau}. If d_i are the four factor degrees, their product is at most D. The sum of (\prod_i d_i)^{-1/4} over all possible product types is at most C_{1/4}^4. Thus the number T of occurring types is at most C_{1/4}^4D^{1/4}.

For one type choose i with d_i\le D^{1/4}. The coefficient function on gH_i belongs to a single type’s coefficient space, even when that type occurs repeatedly. Lemma 4.1 bounds its supremum by d_i times its uniform root mean square. Sum over cosets with cap two, then apply Cauchy–Schwarz over the uniform cosets. Full-group Schur orthogonality yields

Finally \sum_{\boldsymbol\tau}\|v_{\boldsymbol\tau}\|\le\sqrt T\|v\|, giving the claimed exponent and constant. The count here is of entire product types, unlike the blockwise assignment in Proposition 4.2.□

Proof. Remove the longer of the first row and first column of the current diagram. In a row removal, the realigned lower diagram \mu is contained in the original diagram \lambda, and \lambda/\mu is a horizontal strip: every column loses exactly its bottom box. The Pieri rule and Frobenius reciprocity show that restriction to S_s\times S_r contains V_\mu tensored with the trivial representation of S_r. For a column removal use the sign representation and the transposed argument. Iteration supplies a product subgroup and a product of trivial and sign characters occurring in the original representation.

To prove the index bound, it remains to compare dimensions at each step. Transpose so that a row is removed; then the diagram has height at most r. If c_j counts its lower boxes in column j, the hook formula gives

The case s=0 is immediate. For r\ge512 and s\ge16r, the bound c_j\le r gives

Thus R\le\binom{r+s}r^{1/2}. For 1\le s\le16r, the opposite ordering of c_j and (r-j+1)^{-1} instead gives

Since (1+\log r)/r decreases for r\ge512 and is at most \frac12\log(17/16) there, this also gives D/D'\ge\binom{r+s}r^{1/2}.

If r<512 and s>0, then r\ge2 and r+s\le r^2. Each standard ordering of the lower diagram yields two distinct standard tableaux: fill the first row before that ordering, or fill its first r-1 boxes, the first lower box, the last top-row box, and then the remaining lower boxes in that ordering. The first lower box is in column one, so the second filling is also valid. These two constructions are injective and have disjoint images. Hence D/D'\ge2, while \binom{r+s}r\le2^{r^2}\le2^{C_{\rm peel}}. This proves (C.1) in every case. Multiplying it through the successive steps telescopes the dimension ratios. The product of the binomial coefficients is exactly the index of the product subgroup constructed above, proving the assertion.□

Proof. We use p(h)\le e^{3\sqrt h}, which follows by evaluating the partition generating function at e^{-1/\sqrt h}: the logarithm of the product is at most \sqrt h\sum_{j\ge1}j^{-2}\le2\sqrt h, and the coefficient bound adds \sqrt h.

The first removed length r is at least \sqrt m because both width and height are at most r. If r<m/2, (C.1) gives

The concavity of r\log(m/r) bounds it below on [\sqrt m,m/2] by the smaller of \frac12\sqrt m\log m and \frac12m\log2. After division by \sqrt m, this lower bound tends to infinity. It therefore dominates the logarithm 3\sqrt m of the number of all diagrams, proving a vanishing inverse sum in this range.

If m/2\le r<m, put h=m-r\ge1. At most 2p(h) diagrams have this value, counting both orientations, and (C.1) gives D_\lambda\ge(m/h)^{h/C_{\rm peel}}. For fixed h their inverse-degree contribution tends to zero. It is bounded by 2e^{3\sqrt h}2^{-h/C_{\rm peel}}, a summable sequence. Dominated convergence handles this range. The remaining diagrams are the row and column, of degree one. Once the nonlinear reciprocal sum is at most one, at most Y nonlinear types have degree at most Y; adding the two linear types gives Y+2\le3Y.□

Proof. Lemma 7.2, using Lemma C.4, bounds a full H_i-isotypic projection of degree d_\tau by 2d_\tau^{C_{\rm peel}+1}/D in squared Hilbert–Schmidt norm. As in Theorem 7.3, the projections with d_\tau\le Y=D^{1/b} cover the identity. By Lemma C.5 there are at most 3Y such types for each factor. Summing gives D^{-1}\cdot2b\cdot3Y\cdot Y^{C_{\rm peel}+1}, which is (C.2).□