\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern,microtype}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage[margin=1.05in]{geometry}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\TV}{TV}
\DeclareMathOperator{\HS}{HS}
\DeclareMathOperator{\Res}{Res}
\DeclareMathOperator{\Ind}{Ind}
\newcommand{\E}{\mathbb{E}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\one}{\mathbf{1}}
\begin{document}

Place $N=2^d$ cards at the vertices of the $d$-dimensional cube, one card per vertex. Each coordinate direction cuts the cube into $N/2$ disjoint pairs. A coordinate layer visits every pair and, independently on each, swaps the two cards with probability $1/2$ and leaves them alone otherwise. A sweep applies the layers in the order $1,2,\dots,d$.

One layer already makes every single card uniform over the $N$ vertices, and no later layer disturbs that: the marginal law of one card is uniform from the first layer onward. The deck is not uniform. Two cards that have not yet met occupy perfectly correlated positions, and the law of the whole permutation is supported on at most $2^{tN/2}$ points after $t$ physical shuffles, far fewer than $N!$. Randomising a single card and randomising the deck are different problems.

Thorp introduced this shuffle, under the name of the faro shuffle, while analysing nonrandom dealing procedures in card games.

./thorp-1973.pdf

A bounded number of sweeps suffices, independent of $N$. A physical shuffle performs one coordinate layer and then rotates the coordinate names cyclically; after $d$ physical shuffles the rotating layers have run through all $d$ directions exactly once, so $d$ physical shuffles make one sweep. Hence $O(\log N)$ physical shuffles randomise the deck, and the counting bound shows this order is optimal. In detail, $t$ physical shuffles toss $tN/2$ independent coins, so at most $2^{tN/2}$ permutations are reachable and
\[
\|\mu_t-U_{S_N}\|_{\TV}\ \ge\ 1-\frac{2^{tN/2}}{N!}.
\]
Requiring distance at most $1/4$ forces $2^{tN/2}/N!\ge 3/4$, that is $t\ge (2/N)\log_2(3N!/4)=2d-O(1)$.

The history of upper bounds is a history of the exponents. Morris proved $O(d^{44})$ for $N=2^d$; Montenegro and Tetali reduced it to $O(d^{29})$; Morris then obtained $O((\log N)^4)$ for every even deck size and $O(d^3)$ for dyadic decks. A four-row moment recursion reaches $O(d)$, meeting the counting bound up to a factor.

./morris-2008.pdf

./montenegro-tetali-2006.pdf

./morris-2009.pdf

./morris-2013.pdf

The engine is a permanent inequality on the symmetric group $S_4$, and the reason four rows appear is that removing two coordinate directions leaves four independent smaller cubes. To set up the inequality, write
\[
\|f\|_p=\Bigl(\frac14\sum_{j=1}^{4}f(j)^p\Bigr)^{1/p}
\]
for $f:\{1,2,3,4\}\to[0,\infty)$, and let $u$ be the uniform law on $S_4$. The expectation $\E_u\prod_{i=1}^4 f_i(\pi(i))$ equals $\operatorname{perm}(f_i(j))/4!$. Carlen, Lieb and Loss proved
\[
\operatorname{perm}(f_i(j))\le\frac{4!}{4^2}\prod_{i=1}^{4}\Bigl(\sum_{j=1}^{4}f_i(j)^2\Bigr)^{1/2},
\]
which in the present normalisation reads $\E_u\prod_i f_i(\pi(i))\le\prod_i\|f_i\|_2$, and the equality case is settled there: for nonzero nonnegative functions on four points, equality forces every $f_i$ to be constant.

./carlen-lieb-loss-2006.pdf

The exponent two is not the end of the story. Samorodnitsky proved further permanent bounds below exponent two, and Bristiel and Caputo proved the sharp bound for every $p\ge1$, which in the normalisation above gives
\[
\E_u\prod_{i=1}^{4}f_i(\pi(i))\le\prod_{i=1}^{4}\|f_i\|_p
\qquad\text{for every }p\ge p_c:=\frac{4\log 4}{\log 24}.
\]
The value $p_c$ is optimal for the uniform law, as the identity matrix shows. Since $p_c=1.7448\ldots$, the sharp threshold sits strictly between $4/3$ and $2$, which is what makes a four-row recursion possible.

./samorodnitsky-2008.pdf

./bristiel-caputo-2024.pdf

The needed statement is not the sharp one. It is a stable version: the uniform law may be perturbed slightly, provided every coordinate marginal stays exactly uniform.

\begin{theorem}\label{thm:permanent}
There are absolute constants $p_0\in(4/3,2)$ and $\varepsilon>0$ with the following property. Let $\nu$ be a probability measure on $S_4$ with $\|\nu-u\|_{\TV}<\varepsilon$ and
\[
\nu\{\pi:\pi(i)=j\}=\frac14\qquad(1\le i,j\le 4).
\]
Then every four nonnegative functions on $\{1,2,3,4\}$ satisfy
\[
\E_\nu\prod_{i=1}^{4}f_i(\pi(i))\le\prod_{i=1}^{4}\|f_i\|_{p_0}.
\]
\end{theorem}

The marginal hypothesis is not a technical convenience. Setting three of the functions equal to one reduces the inequality to $\sum_j a(j)f(j)\le\|f\|_{p_0}$ with $a(j)=\nu\{\pi(4)=j\}$. If $a-1/4$ is nonzero, take $f=1+t(a-1/4)$; the derivative at $t=0$ of the right side minus the left side equals $-\sum_j(a(j)-1/4)^2<0$, so the inequality fails for small positive $t$. Uniform coordinate marginals are forced by the inequality itself.

\begin{proof}[Proof of Theorem~\ref{thm:permanent}]
The claim is homogeneous of degree one in each $f_i$. A zero function makes both sides zero, so assume all functions are nonzero and normalise $\|f_i\|_2=1$. The set of such quadruples is compact. On it the exponent-two inequality holds, with equality only at $f_i\equiv1$ for all $i$.

Two regions must be treated. Near the constant quadruple the exponent-two inequality is useless, since equality holds there and any improvement must be extracted from a second-order expansion. Away from it there is room by compactness.

\emph{Near the constants.} Since each $f_i$ is nonnegative with mean $m_i>0$ close to one, divide by the mean and write $f_i=1+g_i$ with $\E_j g_i(j)=\frac14\sum_j g_i(j)=0$; the inequality is unaffected by this rescaling. Put
\[
V=\sum_{i=1}^{4}\|g_i\|_2^2,\qquad b=\max_i\|g_i\|_\infty .
\]
On four points $\|g\|_\infty\le 2\|g\|_2$, because $\|g\|_2^2\ge\frac14\|g\|_\infty^2$.

For $i\ne j$, the pair $(\pi(i),\pi(j))$ is a uniformly random ordered pair of distinct points, so
\[
\E_u\,g_i(\pi(i))g_j(\pi(j))
=\frac1{12}\sum_{r\ne s}g_i(r)g_j(s)
=-\frac13\langle g_i,g_j\rangle .
\]
Summing over pairs,
\[
\sum_{i<j}\E_u\,g_i(\pi(i))g_j(\pi(j))
=-\frac13\sum_{i<j}\langle g_i,g_j\rangle
=\frac16\Bigl(V-\Bigl\|\sum_i g_i\Bigr\|_2^2\Bigr)\le\frac V6 .
\]
Every linear term vanishes under $\nu$ and not merely under $u$, since $\E_\nu g_i(\pi(i))=\frac14\sum_j g_i(j)=0$ by the marginal hypothesis. Replacing $u$ by $\nu$ changes each quadratic expectation by at most $2\varepsilon\|g_i\|_\infty\|g_j\|_\infty\le 8\varepsilon\|g_i\|_2\|g_j\|_2$, so the total change is at most an absolute constant times $\varepsilon V$. A monomial of degree at least three involves at least three distinct $g_i$; bounding all but two factors by $b$ in sup norm and applying Cauchy--Schwarz to the remaining two, whose squared expectations are controlled by the uniform marginals, bounds each such term by an absolute constant times $bV$ once $b\le 1/2$. Therefore
\[
\E_\nu\prod_{i=1}^{4}\bigl(1+g_i(\pi(i))\bigr)
\le 1+\Bigl(\frac16+C\varepsilon+Cb\Bigr)V .
\]

On the other side, Taylor's formula on $[1/2,3/2]$, uniformly for $p\in[p_*,2]$, gives
\[
\E_j(1+g_i(j))^p=1+\frac{p(p-1)}2\|g_i\|_2^2+O\bigl(b\|g_i\|_2^2\bigr),
\]
and taking $p$th roots and multiplying the four factors,
\[
\prod_{i=1}^{4}\|1+g_i\|_p=1+\frac{p-1}{2}V+O(bV).
\]
The two displays are compatible exactly when $\frac{p-1}{2}>\frac16$, that is $p>4/3$. Fix $p_*\in(4/3,2)$ and then $b_*>0$, $\varepsilon_*>0$ small enough that the error terms fit inside the strict gap $\frac{p_*-1}{2}-\frac16$. For every $p\in[p_*,2]$, every $\nu$ with $\|\nu-u\|_{\TV}\le\varepsilon_*$ and uniform marginals, and every quadruple with $b<b_*$, the inequality holds.

\emph{Away from the constants.} The condition $b<b_*$ contains a fixed open neighbourhood $\mathcal U$ of the constant quadruple in the normalised compact set. On its complement the exponent-two inequality is strict everywhere, so by compactness it has a positive minimum gap. Both sides are continuous in the functions, in the exponent and in the probability masses of $\nu$, so choosing $p_0\in[p_*,2)$ close enough to two and then $\varepsilon\le\varepsilon_*$ small enough keeps this gap positive on the complement. The local argument covers $\mathcal U$ with the same constants. The two regions cover everything.
\end{proof}

The inequality tensorises over independent coordinates, which is how columns will be handled.

\begin{lemma}[Tensorisation]\label{lem:tensor}
Let $\pi_1,\dots,\pi_b$ be independent random permutations of $\{1,2,3,4\}$, each with a law satisfying Theorem~\ref{thm:permanent} for the same $p_0$. Then for nonnegative $F_i$ on $\{1,2,3,4\}^b$,
\[
\E\prod_{i=1}^{4}F_i(\pi_1(i),\dots,\pi_b(i))
\le\prod_{i=1}^{4}\Bigl(4^{-b}\sum_{x\in\{1,2,3,4\}^b}F_i(x)^{p_0}\Bigr)^{1/p_0}.
\]
\end{lemma}

\begin{proof}
Induction on $b$. Condition on the first $b-1$ coordinates and apply Theorem~\ref{thm:permanent} to the last one. The four resulting functions of $b-1$ coordinates are
\[
G_i(x)=\Bigl(\frac14\sum_{j=1}^{4}F_i(x,j)^{p_0}\Bigr)^{1/p_0},
\]
the induction hypothesis applies to the product of the four $G_i$, and the $p_0$th power sums are exactly the full product sums appearing in the claim.
\end{proof}

One numerical inequality converts a trace into a power strictly below one.

\begin{lemma}\label{lem:interp}
Let $U$ be a positive semidefinite stochastic matrix of order $s$. Then
\[
\Bigl(s^{-2}\sum_{x,y}U(x,y)^{p_0}\Bigr)^{1/p_0}\le s^{-1}(\Tr U)^{\theta},
\qquad \theta=1-\frac1{p_0}<\frac12 .
\]
\end{lemma}

\begin{proof}
The eigenvalues of $U$ lie in $[0,1]$, so $\sum_{x,y}U(x,y)^2=\Tr U^2\le\Tr U$. Split $U^{p_0}=U^{2-p_0}\cdot U^{2p_0-2}$ and apply H\"older with conjugate exponents $1/(2-p_0)$ and $1/(p_0-1)$:
\[
\sum_{x,y}U(x,y)^{p_0}\le\Bigl(\sum_{x,y}U(x,y)\Bigr)^{2-p_0}
\Bigl(\sum_{x,y}U(x,y)^2\Bigr)^{p_0-1}\le s^{2-p_0}(\Tr U)^{p_0-1}.
\]
Taking $p_0$th roots gives the claim.
\end{proof}

Now the shuffle as an operator. Positions are binary strings, a permutation sends input positions to output positions, and $gh$ applies $h$ first. The average of all optional edge swaps in direction $i$ is an orthogonal projection $\Pi_i$ of the group algebra, and the sweep operator is
\[
T_N=\Pi_d\cdots\Pi_1,\qquad B_N=T_NT_N^*,
\]
so that $B_N$ is a positive contraction. All statements about mixing concern $T_N$; the moment estimates concern $B_N$, and the two are separated at the end.

Physical time is bookkeeping. Let $R(x_1,\dots,x_d)=(x_2,\dots,x_d,x_1)$ and let $S_t$ be the layer in the currently first coordinate. A physical shuffle is $RS_t$. If $Y_t$ is the accumulated permutation, then $X_t=R^{-t}Y_t$ satisfies $X_{t+1}=(R^{-t}S_{t+1}R^t)X_t$; the conjugated layers visit all directions in one cyclic order, and since $R^d=I$ relabelling that order as $1,\dots,d$ turns $d$ physical shuffles into exactly $T_N$.

Two structural facts about a single sweep will be used repeatedly: it annihilates the sign representation and every diagram with more than $N/2$ rows, and at any fixed $N$ its operator norm on each remaining nontrivial irreducible is strictly less than one.

\begin{lemma}\label{lem:gap}
Every sweep kills the sign representation and every shape with more than $N/2$ rows. For fixed dyadic $N\ge 2$, the operator norm of $T_N$ on each nontrivial irreducible representation is strictly less than one.
\end{lemma}

\begin{proof}
Each layer averages the subgroup $H\cong(S_2)^{N/2}$ of coordinate-edge transpositions. The sign character averages to zero. By Young's rule an irreducible with an $H$-fixed vector must dominate the partition $(2^{N/2})$, hence has at most $N/2$ rows.

For the norm, equality in a product of orthogonal projections applied to a unit vector would force the vector to be fixed by every layer, hence by every coordinate-edge transposition. Those transpositions generate $S_N$, since the cube graph is connected. A nontrivial irreducible representation of $S_N$ has no invariant vector.
\end{proof}

Take $N=4m$ and use the last two coordinates as a row index, so the cube becomes a $4\times m$ array. The first $d-2$ directions are independent sweeps inside the four rows; the last two directions act as a two-axis sweep inside each of the $m$ columns, independently across columns. Writing $M$ for the column operator and $A=B_m^{\otimes 4}$ for the product of the four row sweeps,
\[
B_N=MAM^*,\qquad A=B_m^{\otimes 4}.
\]
The row group is $H=(S_m)^4$ and the column group is $(S_4)^m$, whose factors act on disjoint columns.

Fix an even integer $r\ge 2$ and define
\[
F_r(\lambda)=D_\lambda\Tr B_{|\lambda|}(\lambda)^r ,
\]
the unnormalised trace of the $r$th power of the sweep moment in the irreducible $V_\lambda$; the dimension factor $D_\lambda$ is the multiplicity of $V_\lambda$ in the regular representation. The subscript $r$ is suppressed while the recursion is derived. Put $X=A^{r/2}$ and $Y=(M^*M)^{r/2}$, both positive. The Araki--Lieb--Thirring inequality, published by Araki in Letters in Mathematical Physics 19 (1990) 167--170 and applied with exponent $r/2\ge1$ and outer power two, together with the identity of the nonzero spectra of $MAM^*$ and $A^{1/2}M^*MA^{1/2}$, give
\[
F(\lambda)\le D_\lambda\Tr(XYXY)_\lambda
=D_\lambda\bigl\|Y^{1/2}X_\lambda Y^{1/2}\bigr\|_{\HS}^2 .
\]

./audenaert-2007.pdf

The operator $X$ is a positive element of the group algebra of $H$. Let $\mathcal I(\lambda)$ be the set of tuples $\boldsymbol\alpha=(\alpha_1,\dots,\alpha_4)$, each $\alpha_i\vdash m$, that occur in $\Res_H V_\lambda$. For such a tuple let $X_{\boldsymbol\alpha}$ be $X$ multiplied by the central isotype projection for that row type; the projection commutes with $X$, so $X_{\boldsymbol\alpha}$ is positive in every unitary representation, and on $V_\lambda$ it acts on all copies of the row type at once rather than on a chosen copy. The Hilbert--Schmidt triangle inequality then gives
\[
F(\lambda)^{1/2}\le\sum_{\boldsymbol\alpha\in\mathcal I(\lambda)}
\bigl(D_\lambda\Tr(X_{\boldsymbol\alpha}Y X_{\boldsymbol\alpha}Y)_\lambda\bigr)^{1/2}.
\]

Each term is now estimated inside the regular representation. Write $X_{\boldsymbol\alpha}=\sum_{p\in H}\xi(p)p$ with $\xi(p)=\prod_i\xi_i(p_i)$, where each row factor has Fourier block $B_m(\alpha_i)^{r/2}$ on $\alpha_i$ and vanishes elsewhere. Plancherel on $S_m$ gives
\[
m!\sum_{p_i}|\xi_i(p_i)|^2=D_{\alpha_i}\Tr B_m(\alpha_i)^r=F(\alpha_i).
\]
If one of these is zero the tuple contributes nothing, so assume all four are positive and let $u_i(p_i)=|\xi_i(p_i)|^2/\sum|\xi_i|^2$ be probability laws on the four row groups, with product law $u$.

Since $r/2$ is an integer, $Y=(M^*M)^{r/2}$ is convolution by a probability law $\omega$ on the column group. Expanding the regular trace gives
\[
N!\sum_{p,q\in H}\sum_{b,c}\xi(p)\xi(q)\omega(b)\omega(c)\one_{\{pbqc=e\}} .
\]
Bounding $|\xi(p)\xi(q)|\le\frac12(|\xi(p)|^2+|\xi(q)|^2)$ and noting that the two square terms have equal sums by the cyclic interchange of $(p,b)$ with $(q,c)$ reduces the estimate to the single case: for fixed $p,b,c$ there is at most one $q$, and it lies in $H$ exactly when $b^{-1}p^{-1}c^{-1}\in H$. Both $Y$ and the laws $u_i$ are invariant under inversion, so all three variables may be inverted, and the Plancherel normalisations above give
\[
\Tr_{\mathrm{reg}}(X_{\boldsymbol\alpha}Y X_{\boldsymbol\alpha}Y)
\le\prod_{i=1}^{4}F(\alpha_i)\cdot\frac{N!}{(m!)^4}\,\PP\{bpc\in H\},
\]
with $p\sim u$ and $b,c$ independent column permutations of law $\omega$.

It remains to bound the overlap probability, uniformly in the laws $u_i$. Let $a(z)$ be the row index of position $z$ and define two colourings
\[
\eta(z)=a(c^{-1}z),\qquad\zeta(z)=a(bz).
\]
Substituting $z=cw$ in $a(bpcw)=a(w)$ shows that $bpc\in H$ is equivalent to $\zeta(pz)=\eta(z)$ for every $z$. In each column either colouring uses the four colours exactly once, distinct columns are independent, and the two colourings are independent of each other.

For row $i$ define the transition matrix on the $4^m$ colour strings by
\[
U_i(x,y)=\PP_{p_i\sim u_i}\{y(p_i z)=x(z)\ \text{for every }z\text{ in row }i\}.
\]
Each $U_i$ averages the permutation action of a row group on strings. Conditional on the two colourings the four row permutations are independent, so with $\eta_i,\zeta_i$ the restrictions to row $i$,
\[
\PP\{bpc\in H\}=\E\prod_{i=1}^{4}U_i(\eta_i,\zeta_i).
\]

The matrices $U_i$ are stochastic and symmetric, and positive semidefinite. Positivity comes from the specific origin of $u_i$: Fourier inversion writes $\xi_i(g)=(D_{\alpha_i}/m!)\Tr(Q\rho_{\alpha_i}(g^{-1}))$ with $Q=B_m(\alpha_i)^{r/2}\ge0$, so $\xi_i$ and then $|\xi_i|^2$ are positive definite, the Fourier transforms are positive semidefinite, and so is the average of $u_i$ in the colour-string representation.

The remaining hypothesis of Theorem~\ref{thm:permanent} is that the column law has uniform marginals. The four-site law of $M$ sends every site exactly uniformly to the four sites, its adjoint does the same, and the same remains true of every positive power of $M^*M$. Also the support of $M^*M$ contains the identity and the four edge transpositions of the square, which generate $S_4$, so its convolution powers converge to the uniform law on $S_4$. Choosing the even integer $r$ large enough therefore makes the column law of $Y$ satisfy Theorem~\ref{thm:permanent}, and every larger even $r$ works as well.

The variables $(\eta_i,\zeta_i)$ are $2m$ independent four-colour column assignments. Applying Lemma~\ref{lem:tensor} to these assignments with the four functions $U_i$, and then Lemma~\ref{lem:interp} with $s=4^m$,
\[
\PP\{bpc\in H\}\le\prod_{i=1}^{4}\Bigl(s^{-2}\sum_{x,y}U_i(x,y)^{p_0}\Bigr)^{1/p_0}
\le s^{-4}\prod_{i=1}^{4}(\Tr U_i)^{\theta},\qquad \theta=1-\frac1{p_0}<\frac12 .
\]
Since $N!/(m!)^4\le 4^N=s^4$, the exponential prefactor cancels exactly against the four factors $s^{-1}$. What survives is a power of four colour-string traces. Writing $c^{\alpha}_{\boldsymbol\beta}$ for the multiplicity of $\bigotimes_{i=1}^4 V_{\beta_i}$ in the restriction of $V_\alpha$ to $\prod_i S_{|\beta_i|}$ and
\[
C(\alpha)=\sum_{\boldsymbol\beta}\bigl(c^{\alpha}_{\boldsymbol\beta}\bigr)^2 ,
\]
the sum running over all weak four-part compositions of $m$ and all irreducible tuples for the corresponding Young subgroup, the trace bound $\Tr U_i\le C(\alpha_i)$ of Lemma~\ref{lem:color} turns the overlap estimate into the recursion
\[
F(\lambda)^{1/2}\le\sum_{\boldsymbol\alpha\in\mathcal I(\lambda)}
\prod_{i=1}^{4}\bigl(F(\alpha_i)\,C(\alpha_i)^{\theta}\bigr)^{1/2}.
\]
Every restriction multiplicity is retained: multiplicities are carried by the regular trace and by $C(\alpha)$, not discarded by choosing one copy.

The cost $C(\alpha)$ has a clean interpretation: it is the trace of the colour-string operator generated by any rank-one positivity, and it counts squared restriction multiplicities.

\begin{lemma}\label{lem:color}
Let $\alpha\vdash m$, let $Q\ge0$ be a nonzero operator on $V_\alpha$, and let
\[
u(g)=\frac{D_\alpha}{m!\,\Tr Q^2}\bigl|\Tr(Q\rho_\alpha(g))\bigr|^2\qquad(g\in S_m).
\]
If $U$ is the average action of $u$ on strings of length $m$ over four colours, then
\[
\Tr U\le\bigl\langle \chi_\alpha^2,\,4^{\#\mathrm{cycles}}\bigr\rangle_{S_m}
=\sum_{\boldsymbol\beta}\bigl(c^{\alpha}_{\boldsymbol\beta}\bigr)^2=C(\alpha),
\]
where $\langle f,g\rangle_{S_m}=(m!)^{-1}\sum_{x}f(x)\overline{g(x)}$.
\end{lemma}

\begin{proof}
Schur orthogonality normalises $u$ to total mass one. Decompose $V_\alpha\otimes\overline{V_\alpha}=\bigoplus_\nu V_\nu\otimes\mathbb{C}^{a_\nu}$ and let $P_\nu$ be the isotypic projection. Character orthogonality gives
\[
\sum_g u(g)\chi_\nu(g)=\frac{D_\alpha\Tr\bigl((Q\otimes\bar Q)P_\nu\bigr)}{D_\nu\Tr Q^2}.
\]
The commuting positive operators $Q\otimes I$ and $I\otimes\bar Q$ satisfy $Q\otimes\bar Q\le\frac12(Q^2\otimes I+I\otimes\bar Q^2)$. The partial trace of $P_\nu$ over either factor commutes with the irreducible action on the other and has trace $a_\nu D_\nu$, hence equals $(a_\nu D_\nu/D_\alpha)I$. Substituting, the character average is at most $a_\nu$.

A permutation fixes exactly $4^{\#\mathrm{cycles}(g)}$ colour strings, so the fixed-point count is a permutation character and its expansion in irreducible characters has nonnegative integer coefficients. Applying the previous inequality termwise to that expansion gives the first bound, since $a_\nu$ is the multiplicity of $\nu$ in $\chi_\alpha^2$.

For the second, the colour-string representation is the direct sum over compositions $m_1+\dots+m_4=m$ of $\Ind_{S_{m_1}\times\dots\times S_{m_4}}^{S_m}\one$. Frobenius reciprocity identifies its inner product with $\chi_\alpha^2$ as the sum, over these compositions, of the dimensions of the commuting algebras of the corresponding restrictions of $V_\alpha$. Those dimensions are precisely the sums of squared multiplicities displayed.
\end{proof}

For a partition $\alpha\vdash m$ put
\[
k(\alpha)=m-\max(\alpha_1,\alpha'_1),\qquad
t_h(\alpha)=\bigl|\{(i,j)\in\alpha:\ i>h,\ j>h\}\bigr|\quad(h\ge1),
\]
so $t_h(\alpha)$ counts the boxes outside the union of the first $h$ rows and first $h$ columns. The recursion cost is controlled by these two quantities.

\begin{lemma}\label{lem:cost}
There is an absolute $C$ such that for every $\alpha\vdash m$ and every integer $h\ge1$,
\[
\log C(\alpha)\le t_h(\alpha)\log 4+C(1+h)\bigl(1+\sqrt{k(\alpha)}\bigr)\log(2m).
\]
\end{lemma}

\begin{proof}
The basic estimate for a shape $\delta\vdash t$ is
\[
\bigl(c^{\delta}_{\gamma_1,\dots,\gamma_4}\bigr)^2
\le\binom{t}{|\gamma_1|,\dots,|\gamma_4|}\le 4^t .
\]
Indeed, if $c$ is the multiplicity before squaring, then restriction and induction dimensions give respectively
\[
c\prod_i D_{\gamma_i}\le D_\delta,\qquad
c\,D_\delta\le\binom{t}{|\gamma_1|,\dots,|\gamma_4|}\prod_i D_{\gamma_i},
\]
and multiplying and cancelling the positive dimensions proves the estimate. One restriction and one induction estimate are both essential.

Both $C(\alpha)$ and $t_h(\alpha)$ are invariant under conjugation, so orient $\alpha$ with first row of length $m-k$, where $k=k(\alpha)$. Remove the first $h$ rows, then the first $h$ columns of what remains. The residual straight diagram $\delta$ has size $t=t_h(\alpha)$. Deleting a first row leaves an interlacing partition, so reversing that deletion adds a horizontal strip; deleting a first column gives the vertical analogue.

Explicitly, let $\ell\le 2h$ be the number of nonempty removed lines, with lengths $a_1,\dots,a_\ell$, and let $\xi_j$ be the trivial character of $S_{a_j}$ for a removed row and the sign character for a removed column. By the Pieri rules,
\[
W=\Ind_{S_t\times S_{a_1}\times\dots\times S_{a_\ell}}^{S_m}
\bigl(V_\delta\otimes\xi_1\otimes\dots\otimes\xi_\ell\bigr)
\]
contains $V_\alpha$. Only tuples $\boldsymbol\beta$ occurring in the original restriction of $V_\alpha$ matter. For those, the first-row inequality of the Littlewood--Richardson rule gives $\alpha_1\le\sum_i\beta_{i,1}$, hence
\[
\sum_i\bigl(|\beta_i|-\beta_{i,1}\bigr)\le k .
\]
Every intermediate diagram in a Pieri chain ending at such a $\beta_i$ sits inside $\beta_i$ and therefore has at most $k$ boxes below its first row. The number of partitions of size at most $m$ with that property is at most
\[
Q_m(k)=(m+1)^{1+2\lceil\sqrt k\rceil},
\]
because the first-row length can be chosen freely and the tail is encoded by its row and column lengths along a Durfee square of side at most $\sqrt k$, padded to length $\lceil\sqrt k\rceil$; for $k=0$ only the first-row length is needed.

Fix such a final tuple $\boldsymbol\beta$ and put $H_{\boldsymbol\beta}=\prod_{i=1}^4 S_{|\beta_i|}$. Mackey's formula expresses $\Res_{H_{\boldsymbol\beta}}W$ as a sum over allocations of the residual factor and the $\ell$ strip factors among the four classes, and there are at most $(m+1)^{4(\ell+1)}$ allocation matrices. For a fixed allocation, restrict $V_\delta$ to the four allocated subsets and add the allocated horizontal or vertical strips inside each class by Pieri. Every chain ending at $\beta_i$ consists of diagrams contained in $\beta_i$, so each step is counted by $Q_m(k)$; choosing the residual tuple and all later diagrams costs at most $Q_m(k)^{4(\ell+1)}$. Each Pieri transition is multiplicity free, and the basic estimate bounds the residual multiplicity by $4^{t/2}$. Hence
\[
c^{\alpha}_{\boldsymbol\beta}
\le\operatorname{mult}_{\boldsymbol\beta}\bigl(\Res_{H_{\boldsymbol\beta}}W\bigr)
\le (m+1)^{4(\ell+1)}Q_m(k)^{4(\ell+1)}4^{t/2}.
\]
There are at most $Q_m(k)^4$ final tuples, so squaring, summing, and using $\ell\le 2h$ produces $4^t$ times $\exp\{C(1+h)(1+\sqrt k)\log(2m)\}$, which is the claim. No tail estimate for the other constituents of $W$ is required.
\end{proof}

Hook deficits add up along a level of the recursion, which is what makes the leading cost summable.

\begin{lemma}\label{lem:deficit}
If $c^{\lambda}_{\alpha_1,\dots,\alpha_4}>0$, then for every integer $h\ge1$,
\[
\sum_{i=1}^{4}t_h(\alpha_i)\le t_h(\lambda),
\qquad
\sum_{i=1}^{4}k(\alpha_i)\le k(\lambda).
\]
\end{lemma}

\begin{proof}
For $k$, orient the parent with its longest side as first row. The first-row inequality bounds the sum of the child row deficits by the parent row deficit, and each child's $k$ is no larger than its own row deficit. If the longest side of the parent is a column, transpose every partition, which preserves Littlewood--Richardson multiplicities.

For $t_h$, write $s_\nu$ for the ordinary Schur function and $s_\nu(X\mid Y)$ for the hook-Schur specialisation. Take $h$ ordinary variables $X$, $h$ transpose variables $Y$, and an unlimited ordinary alphabet $Z$, giving variables in $X\cup Y$ degree zero and variables in $Z$ degree one. The positive hook-Schur tableau rule uses ordinary entries weakly along rows and strictly down columns, and transpose entries strictly along rows and weakly down columns. Ordering all $X$ letters before all $Y$ letters makes the ordinary entries occupy a subdiagram, and the rule gives $s_\nu(X\mid Y)\ne0$ exactly when $\nu_{h+1}\le h$. A tableau over $h$ ordinary and $h$ transpose letters cannot fill an $(h+1)\times(h+1)$ square, since the ordinary part has at most $h$ rows and the transpose-filled remainder has at most $h$ columns in each remaining row; conversely, filling the first $h$ rows with ordinary row letters and the remaining boxes with transpose column letters realises every diagram in that hook.

With $p_j$ the $j$th power sum, the supersymmetric substitution $p_j\mapsto p_j(X)+(-1)^{j-1}p_j(Y)$ applied to the Schur coproduct gives
\[
s_\lambda(X+Z\mid Y)=\sum_{\nu\subseteq\lambda}s_\nu(X\mid Y)\,s_{\lambda/\nu}(Z),
\]
whose coefficients are nonnegative. The largest subdiagram of $\lambda$ inside the $(h,h)$ hook is the union of the first $h$ rows and first $h$ columns, so the smallest $Z$-degree on the left is exactly $t_h(\lambda)$, and the corresponding skew Schur function is nonzero on an unlimited alphabet.

Apply the substitution to $\prod_i s_{\alpha_i}=\sum_\lambda c^{\lambda}_{\boldsymbol\alpha}s_\lambda$. The left side has minimum $Z$-degree $\sum_i t_h(\alpha_i)$, every summand on the right has nonnegative coefficients, and therefore an occurring parent cannot have smaller minimum degree.
\end{proof}

The recursion stops for diagrams close to a single row or column. The bound is proved from the paths of a small collection of tagged cards, and its content is that a binomial inversion cancels every contribution supported on fewer than all tags.

\begin{lemma}\label{lem:sparse}
There is an absolute $N_0$ such that for $n=2^d\ge N_0$ and $1\le k\le n^{1/100}$,
\[
\sum_{\mu\vdash k}D_\mu\Tr B_{(n-k,\mu)}\le n^{-3k/10}.
\]
Consequently, for $n\ge N_0$ and every $\lambda\vdash n$ with $k(\lambda)=n-\max\{\lambda_1,\lambda'_1\}\le n^{1/100}$,
\[
D_\lambda\Tr B_\lambda^r\le 1\qquad(r\ge 4).
\]
There is a fixed even $r_0\ge4$ for which the second assertion holds at every power of two $n\ge2$ and every such $\lambda$.
\end{lemma}

\begin{proof}
\emph{Isolating the first-row deficit.} Let $\mathcal I_s$ be the set of ordered injections of $[s]$ into the $n$ positions, with $\mathcal I_0$ a singleton, and let $T_s$ be the transition matrix induced by a sweep. Put
\[
a_s=\Tr_{\mathbb{C}^{\mathcal I_s}}(T T^*)=\sum_{x,y\in\mathcal I_s}T_s(x,y)^2 ,
\]
the unnormalised trace on that permutation module. The module is $\Ind_{S_{n-s}}^{S_n}\one$, so by repeated branching the multiplicity of $V_\lambda$ in it is the number of standard tableaux of skew shape $\lambda/(n-s)$. Assume $s\le k$ and $n\ge 2k$. Every occurring partition is $\lambda=(n-j,\mu)$ with $0\le j\le s$ and $\mu\vdash j$; the skew shape is the tail $\mu$ together with a row of $s-j$ cells whose columns exceed $n-s\ge k\ge\mu_1$, and the two parts share neither row nor column. Choosing the $j$ entries of the tail and then a standard tableau on it gives multiplicity $\binom{s}{j}D_\mu$, so
\[
a_s=\sum_{j=0}^{s}\binom{s}{j}b_j,\qquad
b_j=\sum_{\mu\vdash j}D_\mu\Tr B_{(n-j,\mu)} .
\]
Binomial inversion gives
\[
b_k=\sum_{s=0}^{k}(-1)^{k-s}\binom{k}{s}a_s .
\]
The same quantity is a sum of nonnegative terms by its definition, so it is nonnegative. It remains to bound the alternating sum without destroying its cancellation.

For fixed initial and final positions of one card there is exactly one possible route through the successive layers: at layer $i$ its first $i$ processed coordinates already hold the final values and the rest still hold the initial ones. Fixed endpoints for $s$ cards therefore prescribe every path. If two tagged cards use the same switch, the two prescribed coin values either disagree, making the endpoints impossible, or agree, saving one coin. If $e$ is the number of switches shared by two tagged cards during a realised sweep, the transition probability to the realised endpoint is $2^{-ds+e}=n^{-s}2^{e}$, and averaging first over the endpoint and then over a uniform initial injection gives the exact identity
\[
a_s=\frac{(n)_s}{n^s}\,\E\,2^{e},\qquad (n)_s=n(n-1)\cdots(n-s+1).
\]

Choose $k$ distinct uniform initial tags $X_1,\dots,X_k$, independently of the coins of one complete sweep. For the realised sweep form a graph $G$ on all $n$ initial positions, joining two positions when the cards at those positions share a switch. Every vertex has degree $d$, and the graph is simple: once two cards meet at coordinate $i$ the positions differ there forever, so no second meeting is possible at a later coordinate. Let $G_X$ be the induced graph on the tags and $e(S)$ the number of its edges inside $S\subseteq[k]$. The marginal initial positions of any subset form a uniform injection, so with
\[
w(S)=\frac{(n)_{|S|}}{n^{|S|}}=\prod_{i\in S}\Bigl(1-\frac{\#\{j\in S: j<i\}}{n}\Bigr)
\]
the two preceding identities give
\[
b_k=\E\sum_{S\subseteq[k]}(-1)^{k-|S|}w(S)\,2^{e(S)} .
\]

Call a predecessor selection a set $D$ of directed pairs $(i,j)$ with $1\le j<i\le k$, at most one pair having a given first coordinate. Let $|D|$ be the number of pairs and $\operatorname{supp}D$ the set of endpoints. Expanding the product defining $w(S)$ gives
\[
w(S)=\sum_{D:\ \operatorname{supp}D\subseteq S}(-n^{-1})^{|D|},
\]
and $2^{e(S)}=\sum_{H\subseteq E(G_X[S])}1$. Summing over $S$ produces the exact cancellation identity
\[
b_k=\E\sum_{H\subseteq E(G_X)}\ \sum_{D:\ \operatorname{supp}H\cup\operatorname{supp}D=[k]}(-n^{-1})^{|D|},
\]
because a term supported on $U$ has coefficient $\sum_{S\supseteq U}(-1)^{k-|S|}$, which vanishes unless $U=[k]$. Only an encounter-edge set together with a predecessor selection that jointly cover every tag survives, and the surviving sum may be bounded in absolute value.

\emph{Counting the covering configurations.} Two facts control the encounter subgraphs. First, any set of $v$ vertices spans at most $\frac v2\log_2 v$ edges, with $0\log_2 0=0$. Induction on $d$ proves it: split the positions according to the last processed coordinate, which keeps the two halves separate until the last layer; induction bounds the earlier encounters by $\frac12 v_0\log_2 v_0+\frac12 v_1\log_2 v_1$ and the last matching adds at most $\min(v_0,v_1)$ edges, and this is at most $\frac12 v\log_2 v$ since the binary entropy $H_2(p)$ satisfies $H_2(p)\ge 2\min(p,1-p)$ by concavity on each half of $[0,1]$.

Second, if $F$ is a specified forest on $v$ tags with $c$ components, then conditional on the whole sweep
\[
\Pr(F\subseteq G_X\mid G)\le\frac{n^{c}d^{\,v-c}}{(n)_v}\le 2\Bigl(\frac dn\Bigr)^{v-c},
\]
by choosing one root position per component and then placing each child at one of at most $d$ neighbours of its parent, which gives the first inequality even when some placements fail to be injective, and by
\[
\frac{(n)_v}{n^v}=\prod_{i=0}^{v-1}\Bigl(1-\frac in\Bigr)\ge 1-\frac{v(v-1)}{2n}\ge\frac12 ,
\]
valid for $v\le k\le n^{1/100}$ and large $n$.

Let $H$ use $v$ vertices and have $c$ nontrivial components. Then $2c\le v$ and $H$ contains a spanning forest with $v-c$ edges. For fixed $v,c$ there are at most $(2k)^{2v}$ choices of vertex set and forest, since one may root each component at its least vertex and record a parent or a root marker for each vertex. Given a forest, the number of edge sets extending it is at most
\[
2^{e(G_X[V])}\le v^{v/2}\le k^{v/2}
\]
by the edge count, so overcounting all spanning forests bounds the expected number of such $H$ by $2(2k)^{2v}k^{v/2}(d/n)^{v-c}$; the empty edge set satisfies the same bound. There are at most $\binom{k}{q}k^{q}\le(2k)^{2q}$ predecessor selections with $q$ pairs. The covering condition forces $v+2q\ge k$. Since $d/n\le1$ and $v-c\ge v/2$, and since there are at most $(k+1)^3$ triples $(v,c,q)$,
\[
b_k\le 2\!\!\sum_{\substack{0\le v,c,q\le k\\ 2c\le v,\ v+2q\ge k}}
\bigl(4k^{5/2}\sqrt{d/n}\bigr)^{v}\bigl(4k^2/n\bigr)^{q}.
\]
Impossible triples only enlarge the bound. For $1\le k\le n^{1/100}$ and large $n$,
\[
4k^{5/2}\sqrt{d/n}\le n^{-2/5},\qquad 2k/\sqrt n\le n^{-2/5},\qquad 2(k+1)^3\le n^{k/10},
\]
the first because $4\sqrt{\log_2 n}\,n^{-19/40}$ dominates the left side, the third because $16n^{3/100}$ does. Every term is then at most $n^{-2(v+2q)/5}\le n^{-2k/5}$, and $b_k\le n^{-3k/10}$.

\emph{From the trace bound to stopping.} If $\lambda_1=n-k$ with $1\le k\le n^{1/100}$, its term in $b_k$ carries $D_\mu\ge1$, so $\Tr B_\lambda\le n^{-3k/10}$. Eigenvalues are nonnegative, hence $\Tr B_\lambda^r\le(\Tr B_\lambda)^r$. Choosing the labels of the $k$ cells below the first row and then an order gives $D_\lambda\le\binom nk k!\le n^{k}$, so
\[
D_\lambda\Tr B_\lambda^r\le n^{(1-3r/10)k}\le1\qquad(r\ge4).
\]
If instead $\lambda'_1=n-k>n/2$, every matching projection vanishes on $V_\lambda$: the fixed-space dimension is the multiplicity of $V_\lambda$ in $\Ind_{S_2^{n/2}}^{S_n}\one$, and repeated horizontal Pieri shows every constituent arises by adding $n/2$ horizontal strips of size two, each adding at most one cell to the first column. Hence $B_\lambda=0$ there. For $k=0$ the trivial representation has value one and the sign representation is annihilated by a matching projection.

Lemma~\ref{lem:gap} supplies operator norm strictly below one on each nontrivial irreducible at each fixed $n$. There are finitely many powers of two below $N_0$ and finitely many irreducibles at each of them, so increasing $r$ to one fixed even $r_0\ge4$ covers those sizes as well, and larger powers preserve the estimate because $B$ is a positive contraction.
\end{proof}

The recursion is now summed along a tree. Write $\log^+x=\max\{0,\log x\}$ and fix a root $\lambda\vdash N$ with $K=k(\lambda)>0$. A node $\alpha\vdash m$ is expanded only if $m$ exceeds a fixed cutoff $M$ and $k(\alpha)>m^{.01}$; otherwise it is stopped. The even moment $r$ is chosen large enough for Lemma~\ref{lem:sparse} and, using Lemma~\ref{lem:gap}, large enough that $F(\alpha)\le1$ whenever $\alpha$ is a stopped diagram of size at most $M$.

Squaring the recursion and bounding a sum by the number of terms times the largest term gives
\[
\log F(\alpha)\le 2\log|\mathcal I(\alpha)|
+\max_{\boldsymbol\beta\in\mathcal I(\alpha)}\sum_{i=1}^{4}\bigl\{\log F(\beta_i)+\theta\log C(\beta_i)\bigr\},
\]
with $\log 0=-\infty$. Iterating is a maximum over finite four-ary trees of occurring restrictions: each expanded node contributes a choice cost $2\log|\mathcal I(\alpha)|$ and each of its four children contributes $\theta\log C(\beta_i)$, the latter even when the child is stopped. The tail count inside the proof of Lemma~\ref{lem:cost} gives $\log|\mathcal I(\alpha)|\le C(1+\sqrt{k(\alpha)})\log(2m)$, by orienting along the longest side and counting each child's tail with the parent deficit; child sizes are prescribed. This choice cost therefore fits inside the lower-order term of Lemma~\ref{lem:cost} and may be charged at the parent, including the root.

For $H>2$ put
\[
R_H(\lambda)=\sum_{(i,j)\in\lambda}\log^+\frac{\min(i,j)}{H}.
\]
The quantity counts, box by box, the levels at which a root box lies outside the chosen hook.

\begin{lemma}\label{lem:budget}
Fix $\delta\in(0,1/2)$, put $a=1/2-\delta$. For every $H>2$ and $\epsilon>0$, a sufficiently large fixed cutoff $M$ makes every recursion tree satisfy
\[
\log F(\lambda)\le\epsilon K+\frac{\theta}{a}\Bigl\{R_H(\lambda)+\frac K2\log\frac NK\Bigr\}.
\]
The cutoff and all constants are independent of the final even moment $r$.
\end{lemma}

\begin{proof}
At a level whose nodes have size $m$, let $q_m$ be the number of charged nodes and $k_1,\dots,k_{q_m}$ the corresponding deficits. By Lemma~\ref{lem:deficit} the deficits sum to at most $K$; expanded nodes have $k_i>m^{.01}$, so the number of expanded nodes is at most $K/m^{.01}$; a charged child of size $m$ has an expanded parent of size $4m$ and there are four children per parent. Hence, after one change of absolute constant,
\[
q_m\le CKm^{-.01},\qquad q_m\le N/m,\qquad \sum_i k_i\le K .
\]
The root obeys the same bounds when expanded; a stopped root already has $F\le1$.

At that level take $h_m=\lceil m^{a}\sqrt{K/N}\rceil$. The lower-order costs are at most $C\sum_i(1+h_m)(1+\sqrt{k_i})\log(2m)$. By Cauchy--Schwarz $\sum_i\sqrt{k_i}\le\sqrt{q_mK}$, so the terms from the ceiling and from the constant one are at most $CKm^{-.005}\log(2m)$, while the terms involving $m^a$ satisfy, using both bounds on $q_m$,
\[
m^a\sqrt{K/N}\sqrt{q_mK}\le Km^{-\delta},
\qquad
m^a\sqrt{K/N}\,q_m\le CKm^{-\delta-.005},
\]
the second because $q_m\le\sqrt{(N/m)(CK/m^{.01})}$. Level sizes differ by a factor four, so these costs form summable geometric tails, and since every charged node has size above $M/4$, choosing $M$ large makes the total at most $\epsilon K$.

The leading hook terms are summed last. Iterating Lemma~\ref{lem:deficit} bounds the sum of $t_{h_m}$ over the charged nodes of a level by $t_{h_m}(\lambda)$. A root box $(i,j)$ with $s=\min(i,j)$ can contribute only if $s>h_m\ge m^a\sqrt{K/N}$. The eligible sizes form part of a geometric progression of ratio four, all above $M/4$, so after increasing $M$ until $(M/4)^a\ge4^aH$ the number of such sizes is at most
\[
\frac{\log^+(s/H)+\tfrac12\log(N/K)}{a\log 4},
\]
which is the logarithm of the ratio of the upper endpoint $(s\sqrt{N/K})^{1/a}$ to the lower endpoint $M/4$, divided by $\log 4$, with the additive one absorbed by $M$. Boxes in the longest first row or column never contribute, since $h_m\ge1$. Exactly $K$ boxes remain, and multiplying the level counts by $\theta\log4$ and adding the lower-order costs gives the stated bound.
\end{proof}

What remains is diagrammatic: $R_H$ must be compared with the hook-length formula. The comparison keeps a first-row entropy term, which matters when $K$ is small relative to $N$.

\begin{lemma}\label{lem:hook}
Orient $\lambda\vdash N$ with first row a longest side, put $K=N-\lambda_1>0$ and $\zeta=(\lambda_2,\lambda_3,\dots)\vdash K$. For $H>2$,
\[
\log D_\lambda\ge K\log\frac NK+\log D_\zeta-E_{N,K},
\qquad
R_H(\lambda)\le\log D_\zeta+\frac{4K}{H},
\]
where $E_{N,K}=O(K/N)$ for $K<N/3$ and $E_{N,K}=O(\sqrt N\log(2N))$ for $K\ge N/3$. There is also an absolute $c>0$ with $\log D_\lambda\ge cK$ for all sufficiently large $N$ and every nontrivial, nonsign $\lambda$.
\end{lemma}

\begin{proof}
The hook-length formula separates the first row exactly:
\[
D_\lambda=\binom NK D_\zeta\prod_{j=1}^{\lambda_1}
\Bigl(1+\frac{\lambda'_j-1}{\lambda_1-j+1}\Bigr)^{-1}.
\]
If $K<N/3$, a nonzero numerator occurs only for $j\le K$, so the logarithm of the inverted product is at most $K/(N-2K+1)$. If $K\ge N/3$, split the columns at height $\sqrt N$: at most $\sqrt N$ columns are taller, each contributing at most $\log(1+N)$, and in the remaining columns $\log(1+x)\le x$ with harmonic summation of denominators contributes at most $\sqrt N(1+\log N)$. Since $\binom NK\ge(N/K)^K$, the first inequality follows.

Every box contributing to $R_H$ lies in $\zeta$. At root coordinates $(i,j)$ its hook inside $\zeta$ has length at most
\[
\frac{K}{i-1}+\frac{K}{j}\le\frac{4K}{\min(i,j)} .
\]
Number the boxes of $\zeta$ from $1$ to $K$ by a reverse linear extension of the Young diagram order. The number assigned to a box is at least its hook length, because all boxes to its right and below precede it, and the product of all number-to-hook ratios is exactly $D_\zeta$ with every ratio at least one.

Suppose $t$ boxes contribute to $R_H$. The assigned numbers are distinct, so the product is at least $t!$, and keeping only these ratios in the hook product gives, for $t>0$,
\[
\log D_\zeta\ge R_H-t\log\frac{4eK}{tH}\ge R_H-\frac{4K}{H},
\]
the last step by maximising $t\log(4eK/(tH))$ over $t>0$; for $t=0$ the bound is immediate.

For the degree lower bound, the case $K<N/3$ is already covered. Put $L=\lambda_1=\max(\lambda_1,\lambda'_1)$ and suppose $K\ge N/3$. If $L\ge N/8$, retain the first row and an order ideal of $b=\lfloor N/32\rfloor$ boxes below it, place $1,\dots,b$ in the first $b$ boxes of the top row, choose any $b$ of the remaining $L$ labels for the lower ideal, fill that ideal in a fixed standard order, and fill the rest of the top row increasingly; every such tableau of the retained diagram extends to $\lambda$, and there are $\binom Lb\ge4^b$ of them. If $L<N/8$, every hook is shorter than $N/4$, so $D_\lambda\ge N!/(N/4)^N\ge(4/e)^N$. Both cases give one absolute positive $c$.
\end{proof}

\begin{theorem}\label{thm:moment}
There are an even integer $r\ge2$ and $\eta>0$, independent of $N$, such that for every dyadic $N$ and every $\lambda\vdash N$,
\[
D_\lambda\Tr B_N(\lambda)^r\le D_\lambda^{1-\eta}.
\]
Consequently there is an absolute integer $q$ for which $q$ independent forward sweeps are at total variation distance tending to zero from uniform as $N\to\infty$, uniformly over the starting deck.
\end{theorem}

\begin{proof}
Fix the constants in logical order. Theorem~\ref{thm:permanent} gives $p_0$ and $\theta<1/2$. Choose $\delta>0$ so small that
\[
b:=\frac{\theta}{1/2-\delta}<1 .
\]
The constant $c$ of Lemma~\ref{lem:hook} is independent of this choice. Choose $H$ large and $\epsilon$ small so that $\epsilon+4b/H<(1-b)c/4$, then choose the cutoff $M$ required by Lemma~\ref{lem:budget}, increasing it until the errors $E_{N,K}$ of Lemma~\ref{lem:hook} are below $(1-b)cK/(4b)$ for $N>M$; this is uniform, since $E_{N,K}/K$ is $O(1/N)$ in the first range and $O(\log N/\sqrt N)$ in the second.

Only now choose the even moment $r$. It must make the four-site column law admissible for Theorem~\ref{thm:permanent}, enforce the stopping rule of Lemma~\ref{lem:sparse}, and make $F_r\le1$ for all nontrivial shapes of all dyadic sizes at most $M$. These are finitely many conditions or fixed thresholds, by Lemmas~\ref{lem:gap} and \ref{lem:sparse}, and all persist as $r$ increases.

For an expanded root, Lemma~\ref{lem:budget} and Lemma~\ref{lem:hook} give
\[
\log F_r(\lambda)\le b\log D_\lambda+\epsilon K+\frac{4bK}{H}+bE_{N,K}
\le\frac{1+b}{2}\log D_\lambda,
\]
the last step after discarding the negative term $-\tfrac12 bK\log(N/K)$. Hence $\eta=(1-b)/2>0$ works at every expanded root. At a stopped root $F_r\le1\le D_\lambda^{1-\eta}$. The trivial representation has $F_r=1$ and the sign representation is killed by Lemma~\ref{lem:gap}. This proves the moment bound for every dyadic $N$.
\end{proof}

The moment concerns the positive operator $B_N=T_NT_N^*$, while repeated shuffles use powers of $T_N$. The passage between the two is separate and explicit.

First, the degree estimates give, for every fixed $A>0$,
\[
\sum_{\lambda\ne(N),(1^N)}D_\lambda^{-A}\longrightarrow0 .
\]
There are at most $2p(k)$ partitions with $k(\lambda)=k$, since deleting the longer first row or column leaves a partition of $k$, and the partition generating function gives $p(k)\le e^{3\sqrt k}$ by evaluating at $x=e^{-1/\sqrt k}$ and bounding its logarithm by
\[
\sum_{j\ge1}\frac{1}{j(e^{j/\sqrt k}-1)}\le\sqrt k\sum_{j\ge1}j^{-2}\le 2\sqrt k .
\]
Lemma~\ref{lem:hook} bounds $D_\lambda^{-A}$ by $e^{-Ac k}$ for large $N$, so the bound $2e^{3\sqrt k-Ack}$ is summable in $k$. For each fixed $k\ge1$ the first-row hook identity gives $D_\lambda\to\infty$ as $N\to\infty$ uniformly over the finitely many tails of that size, and dominated convergence proves the sum vanishes. Mild degree estimates of this kind are classical in the study of coverings and random walks on symmetric groups.

./liebeck-shalev-2004.pdf

From the moment bound, $\|B_N(\lambda)\|_{\mathrm{op}}^r\le\Tr B_N(\lambda)^r\le D_\lambda^{-\eta}$. For any integer $q\ge r$, Schatten H\"older and the operator norm bound give
\[
\|T_N(\lambda)^q\|_{\HS}^2\le\|T_N(\lambda)\|_{\mathrm{op}}^{2(q-r)}\|T_N(\lambda)\|_{2r}^{2r}
=\|B_N(\lambda)\|_{\mathrm{op}}^{q-r}\Tr B_N(\lambda)^r,
\]
so
\[
D_\lambda\|T_N(\lambda)^q\|_{\HS}^2\le D_\lambda^{1-\eta q/r}.
\]
Choosing once and for all an integer $q>r/\eta$, the degree sum shows that the total over all nontrivial nonsign representations tends to zero; the sign block vanishes.

Finite-group Plancherel and Cauchy--Schwarz state that every probability $\sigma$ on $S_N$ satisfies
\[
4\|\sigma-U_{S_N}\|_{\TV}^2\le N!\sum_g\bigl|\sigma(g)-1/N!\bigr|^2
=\sum_{\lambda\ne(N)}D_\lambda\|\widehat\sigma(\lambda)\|_{\HS}^2 .
\]
Applying this to $\sigma=\mu_N^{*q}$, whose Fourier matrix is $T_N(\lambda)^q$, proves convergence to the uniform law after $q$ forward sweeps. Translating the law by a deterministic starting deck preserves total variation, so the convergence is uniform over starting states, and since a sweep is $d$ physical shuffles this gives the $O(\log N)$ bound. The counting estimate supplies the matching lower order.

No step identifies $(T_NT_N^*)^q$ with $T_N^q(T_N^*)^q$. The positive moment carries singular-value information, and H\"older is the separate passage to forward evolution. The Fourier route to mixing, with matrix norms retained because a sweep is generally nonnormal, is the classical method of Diaconis and Shahshahani.

./diaconis-shahshahani-1981.pdf

Three ingredients are standard and used without further comment: branching, induction and restriction of symmetric-group representations with the Littlewood--Richardson and Pieri rules, and the hook-length formula; the textbook accounts of James and of Stanley cover them. The hook and hook-Schur conventions, and the supersymmetric specialisation that compares hook deficits, originate with Berele and Regev in Advances in Mathematics 64 (1987) 118--175, whose notation is followed through the modern treatments of Orellana and Zabrocki and of Mason and Niese.

./james-1978.pdf

./stanley-1999.pdf

./orellana-zabrocki-2000.pdf

./mason-niese-2016.pdf

\end{document}