\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\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 $baudenaert-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: jn/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 $K0$ 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 $K0$,
\[
\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 $K0$, 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}