diff b1f9bc4..56bc728 coordinate_sweep_contraction_v2.txt
diff --git a/coordinate_sweep_contraction_v2.txt b/coordinate_sweep_contraction_v2.txt
index 3224a34..6cd2165 100644
--- a/coordinate_sweep_contraction_v2.txt
+++ b/coordinate_sweep_contraction_v2.txt
@@ -55,9 +55,9 @@ allowdisplaybreaks[1]
maketitle
Abstract:
-The Thorp shuffle on $N=2^d$ labeled cards mixes the full permutation to
-uniform in $Θ(log N)$ physical shuffles. The upper bound uses an
-absolute number of coordinate sweeps (each sweep = $d$ physical
+The Thorp shuffle on N=2^d labeled cards mixes the full permutation to
+uniform in Θ(log N) physical shuffles. The upper bound uses an
+absolute number of coordinate sweeps (each sweep = d physical
shuffles). This document gives the complete proof, following the
weighted-contraction route. Everything the proof uses from representation
theory is collected in Part~part:toolkit as a precise, quotable list.
@@ -71,76 +71,74 @@ part{What is the problem}
# The shuffle, in plain words
-Take a deck of $N=2^d$ cards. Label the $d$ positions of a card by bits
-$x=(x_1,...,x_d)inmathbb F_2^d$.bbF_2^d$. One physical Thorp shuffle
+Take a deck of N=2^d cards. Label the d positions of a card by bits
+x=(x_1,...,x_d)inmathbb F_2^d.bbF_2^d. One physical Thorp shuffle
does the following.
-
-
-item Deal the deck into the $N/2$ unordered pairs of positions that differ
+ Deal the deck into the N/2 unordered pairs of positions that differ
only in the first bit, and in each pair independently swap the two
- cards with probability $1/2$. (This is a "riffle" along the first
+ cards with probability 1/2. (This is a "riffle" along the first
coordinate: it is the classical Thorp move.)
-item Rotate the $d$ coordinates cyclically, so that the next shuffle
+ Rotate the d coordinates cyclically, so that the next shuffle
riffles along what was the second coordinate.
-In coordinates a physical shuffle sends $(x_1,u)mapsto(u,x_1+xi_u)$,
-where $u=(x_2,...,x_d)$ and the bits $xi_u$ are independent and fair.
-After $d$ physical shuffles the
-rotation has come back to the identity, so $d$ physical shuffles are the
+In coordinates a physical shuffle sends (x_1,u)mapsto(u,x_1+xi_u),
+where u=(x_2,...,x_d) and the bits xi_u are independent and fair.
+After d physical shuffles the
+rotation has come back to the identity, so d physical shuffles are the
same as the same matching applied independently along each of the
-$d$ coordinate directions, once. We call that object a
+d coordinate directions, once. We call that object a
coordinate sweep.
A single card is already uniform after one sweep (it has been swapped
-according to $d$ independent fair coins). The subtlety is that the
+according to d independent fair coins). The subtlety is that the
joint law of all the cards is not uniform: the cards have used the
same switches, so they are correlated. The theorem says that an
-absolute constant number of sweeps (i.e. $O(d)$ physical shuffles)
+absolute constant number of sweeps (i.e. O(d) physical shuffles)
destroys every trace of this correlation, measured in total variation
distance from the uniform permutation.
# Statement of the theorem
-Let $S_N$ be the symmetric group. A permutation $gin S_N$ acts on
-positions, and the product $gh$ means "apply $h$ first, then $g$".
-Let $q_d$ be the law of one physical shuffle; it is a probability measure
-on $S_N$. Then $K_d=q_d^{*d}$, the law of one coordinate sweep, is the
-$d$-fold convolution. We write $K_d(lambda)$ for the expectation of the
-representing matrix $rho_lambda(g)$ of the irreducible unitary
-representation labelled by the partition $lambda⊢ N$:
+Let S_N be the symmetric group. A permutation gin S_N acts on
+positions, and the product gh means "apply h first, then g".
+Let q_d be the law of one physical shuffle; it is a probability measure
+on S_N. Then K_d=q_d^{*d}, the law of one coordinate sweep, is the
+d-fold convolution. We write K_d(lambda) for the expectation of the
+representing matrix rho_lambda(g) of the irreducible unitary
+representation labelled by the partition lambda⊢ N:
K_d(lambda)=sum_{gin S_N} K_d(g),rho_lambda(g).
-Write $D_lambda=dimrho_lambda$. Because one matching layer averages
+Write D_lambda=dimrho_lambda. Because one matching layer averages
the (self-adjoint unitary) action of a product of disjoint transpositions,
its Fourier matrix is an orthogonal projection; therefore every
-$K_d(lambda)$ is a contraction.
+K_d(lambda) is a contraction.
[Main; weighted sweep moments]
-There exist positive weights $W_lambda$ (one per partition
-$lambda⊢ 2^d$) and an absolute constant $p_*<∞$ such that, for
-every $dge1$ and every $lambda⊢ 2^d$,
+There exist positive weights W_lambda (one per partition
+lambda⊢ 2^d) and an absolute constant p_*<∞ such that, for
+every dge1 and every lambda⊢ 2^d,
D_lambda^{3/4} le W_lambda le D_lambda,
-qquad
+
W_lambda,|K_d(lambda)|_{p_d}^{p_d}le 1
quadfor some 2le p_dle p_*.
-Consequently $|K_d(lambda)|_{op}le D_lambda^{-3/(4p_*)}$, and there
-is an absolute $q=4p_*/3<∞$ with the unweighted bound
-$D_lambda|K_d(lambda)|_q^qle1$.
+Consequently |K_d(lambda)|_{op}le D_lambda^{-3/(4p_*)}, and there
+is an absolute q=4p_*/3<∞ with the unweighted bound
+D_lambda|K_d(lambda)|_q^qle1.
[Optimal order of mixing]
-Let $t_{rm mix}(d)$ be the least number of physical shuffles after which
-the distance from uniform is at most $1/4$, uniformly over the starting
-deck, and put $N=2^d$. There is an absolute constant $C$ with
+Let t_{rm mix}(d) be the least number of physical shuffles after which
+the distance from uniform is at most 1/4, uniformly over the starting
+deck, and put N=2^d. There is an absolute constant C with
[
Biglceil(2)/(N)log_2(3N!)/(4)Bigrceil
le t_{rm mix}(d) le C,d .
]
-In particular $t_{rm mix}(d)=Θ(log N)$.
+In particular t_{rm mix}(d)=Θ(log N).
The upper bound is the hard direction and occupies Parts
@@ -149,29 +147,29 @@ Part~part:lower.
# The plan, in plain words
-Split the $d$ coordinate directions into two blocks of $approx d/2$ each.
-The positions become a rectangular board of $m$ rows by $n$ columns
-($mn=N$). The first block of directions shuffles within rows; the
+Split the d coordinate directions into two blocks of approx d/2 each.
+The positions become a rectangular board of m rows by n columns
+(mn=N). The first block of directions shuffles within rows; the
second shuffles within columns. Each block is itself a collection of
smaller, independent coordinate sweeps (one independent copy inside each
row, and one inside each column).
-Induction on $d$. Suppose we already understand the two smaller
+Induction on d. Suppose we already understand the two smaller
sweeps on the row group and the column group. The full sweep is the
product of the row part and the column part. In any irreducible
-representation $V_lambda$, the operator norm of a product is not simply
+representation V_lambda, the operator norm of a product is not simply
the product of the norms; the overlap between the row decomposition and
the column decomposition gets in the way. Part~part:overlap is
exactly the estimate of this overlap: how much of a vector that lives in
a single row-type can survive projection onto a single column-type inside
-$V_lambda$.
+V_lambda.
-The key engineering idea is the weight $W_lambda$. It is a number
-between $D_lambda^{3/4}$ and $D_lambda$, built so that the ratio
-$W_lambda/(W_mu W_nu)$ exactly pays for the overlap cost of going from
-a row-type $mu$ and a column-type $nu$ up to $lambda$. This is what
+The key engineering idea is the weight W_lambda. It is a number
+between D_lambda^{3/4} and D_lambda, built so that the ratio
+W_lambda/(W_mu W_nu) exactly pays for the overlap cost of going from
+a row-type mu and a column-type nu up to lambda. This is what
makes the induction close with a bounded Schatten exponent
-$p_dle p_*$, independent of $d$.
+p_dle p_*, independent of d.
Three independent ways to prove the overlap estimate are known. This
document gives one of them completely: the weighted contraction
@@ -188,119 +186,108 @@ part{Notation and the standard tools we use}
# Conventions
-All vector spaces are over $mathbb C$bbC$ and all representations are unitary.
-For a partition $lambda$ of $N$ (a Young diagram with $N$ boxes) let
-$V_lambda$ be the irreducible $S_N$-representation and
-$D_lambda=dim V_lambda$. On a product of groups, $mu,nu,...$
-denote tuples of partitions and $V_mu,D_mu$ are the tensor products and
+All vector spaces are over mathbb CbbC and all representations are unitary.
+For a partition lambda of N (a Young diagram with N boxes) let
+V_lambda be the irreducible S_N-representation and
+D_lambda=dim V_lambda. On a product of groups, mu,nu,...
+denote tuples of partitions and V_mu,D_mu are the tensor products and
products of dimensions. Traces on a single matrix space are
unnormalised; Schatten norms are
-$|A|_p^p=Tr(|A|^p)$ for $2le p<∞$ and $|A|_∞$ is the
+|A|_p^p=Tr(|A|^p) for 2le p<∞ and |A|_∞ is the
operator norm. All logarithms in estimates are natural; we write
-$flesssim g$ or $f=O(g)$ when $fle Cg$ for an absolute constant $C$,
+flesssim g or f=O(g) when fle Cg for an absolute constant C,
and constants are relabelled freely.
-We use the symmetric group $S_L$ of degree $L$ and allow $L=0$ (the
-trivial group) and the empty partition (dimension $1$). Box coordinates
-are $(i,j)$ with $i$ the row and $j$ the column; the width of
-$lambda$ is $lambda_1$ and $k:=N-lambda_1$ counts the boxes below the
+We use the symmetric group S_L of degree L and allow L=0 (the
+trivial group) and the empty partition (dimension 1). Box coordinates
+are (i,j) with i the row and j the column; the width of
+lambda is lambda_1 and k:=N-lambda_1 counts the boxes below the
first row.
# The toolkit
These are the classical facts used in the proof. Each is precise and ready
to quote.
-
-
-item[(T1)] Regard irreducibles on subgroups. Restricting $V_lambda$
- to a Young subgroup $S_{L_1}times...times S_{L_r}$ decomposes into
- tensor products $V_{lambda^{(1)}} ⊗ ... ⊗ V_{lambda^{(r)}}$,
- with the $lambda^{(i)}$ running over all tuples with
- $|lambda^{(1)}|+...+|lambda^{(r)}|=N$ and a nonnegative integer
+[(T1)] Regard irreducibles on subgroups. Restricting V_lambda
+ to a Young subgroup S_{L_1}times...times S_{L_r} decomposes into
+ tensor products V_{lambda^{(1)}} ⊗ ... ⊗ V_{lambda^{(r)}},
+ with the lambda^{(i)} running over all tuples with
+ |lambda^{(1)}|+...+|lambda^{(r)}|=N and a nonnegative integer
multiplicity (the Littlewood--Richardson coefficient). In particular
- restriction to $S_{N-1$ is "delete one box"}: $V_lambda$
- restricted to $S_{N-1}$ is the direct sum of $V_{lambda^-}$ over all
+ restriction to S_{N-1 is "delete one box"}: V_lambda
+ restricted to S_{N-1} is the direct sum of V_{lambda^-} over all
ways to remove a corner box. (Branching; see Sagan 2001, Thm 2.8.3,
or James 1978.)
-
-item[(T2)] Two subgroups at once. If $V_sigma$ is an irreducible of
- $S_{m}$ and $V_tau$ of $S_{n}$, then
- $Ind_{S_mtimes S_n}^{S_{m+n}}(V_sigma ⊗ V_tau)$ contains
- $V_chi$ with multiplicity given by the Littlewood--Richardson
- coefficient for the skew shape $chi/sigma$ filled by the content of
- $tau$. (Littlewood--Richardson; James 1978, Thm 16.4.)
-
-item[(T3)] Pieri's rule. Induction of a single row (or single
+[(T2)] Two subgroups at once. If V_sigma is an irreducible of
+ S_{m} and V_tau of S_{n}, then
+ Ind_{S_mtimes S_n}^{S_{m+n}}(V_sigma ⊗ V_tau) contains
+ V_chi with multiplicity given by the Littlewood--Richardson
+ coefficient for the skew shape chi/sigma filled by the content of
+ tau. (Littlewood--Richardson; James 1978, Thm 16.4.)
+[(T3)] Pieri's rule. Induction of a single row (or single
column) adds boxes to the first (or first column) subject to the diagram
staying a partition. (Stanley EC2, Thm 7.15.7.)
-
-item[(T4)] Hook-length formula, with the correction we keep. For
- $lambda⊢ L$,
- $D_lambda=L!/prod_{boxes}hook(b)$. If $lambda$ is the
- diagram $alpha$ decorated by a single extra long top row of length
- $L-|alpha|$, the ratio of the top-row factorial to the hooks it creates
- is at least $binom{L}{|alpha|}exp(-|alpha|/(L-|alpha|+1))$, obtained
- by comparing the top-row part with $binom{L}{|alpha|}$ and bounding the
+[(T4)] Hook-length formula, with the correction we keep. For
+ lambda⊢ L,
+ D_lambda=L!/prod_{boxes}hook(b). If lambda is the
+ diagram alpha decorated by a single extra long top row of length
+ L-|alpha|, the ratio of the top-row factorial to the hooks it creates
+ is at least binom{L}{|alpha|}exp(-|alpha|/(L-|alpha|+1)), obtained
+ by comparing the top-row part with binom{L}{|alpha|} and bounding the
hook perturbation in the first row. We use this repeatedly. (Sagan
2001, Thm 3.10.2.)
-
-item[(T5)] Ordinary Schur--Weyl duality. On the tensor power
- $(mathbb C^h)^bbC^h)^{ ⊗ L}$ the groups $U(h)$ and $S_L$ act and commute,
+[(T5)] Ordinary Schur--Weyl duality. On the tensor power
+ (mathbb C^h)^bbC^h)^{ ⊗ L} the groups U(h) and S_L act and commute,
and
- $(mathbb C^h)^bbC^h)^{ ⊗ L}cong⊕_{gamma⊢ L, ell(gamma)le h}
- W_gamma ⊗ V_gamma$ with $W_gamma$ the polynomial
- $U(h)$-representation of highest weight $gamma$. A positive matrix $P$
- acting identically on all $L$ factors has, on the $U(h)$-type $gamma$,
+ (mathbb C^h)^bbC^h)^{ ⊗ L}cong⊕_{gamma⊢ L, ell(gamma)le h}
+ W_gamma ⊗ V_gamma with W_gamma the polynomial
+ U(h)-representation of highest weight gamma. A positive matrix P
+ acting identically on all L factors has, on the U(h)-type gamma,
largest eigenvalue given by the highest-weight monomial
- $prod_i x_i^{gamma_i}$ in the eigenvalues of $P$ sorted decreasingly;
- this is also a lower bound for $Tr(P^gamma)$. (Etingof et al.,
+ prod_i x_i^{gamma_i} in the eigenvalues of P sorted decreasingly;
+ this is also a lower bound for Tr(P^gamma). (Etingof et al.,
Thm 4.57 and Cor 4.59; Schur characters in Stanley EC2 Thm 7.10.3.)
-
-item[(T6)] Signed tensor space $(mathbb C^hbbC^h ⊕ mathbb C^h)^bbC^h)^{ ⊗ s}$
- (the "even" block and the "odd" block). The group $S_s$ acts by
+[(T6)] Signed tensor space (mathbb C^hbbC^h ⊕ mathbb C^h)^bbC^h)^{ ⊗ s}
+ (the "even" block and the "odd" block). The group S_s acts by
permuting factors and inserting a sign equal to the sign of the
- reordering of the odd factors. This $S_s$-action commutes with a diagonal
- $U(h)times U(h)$ action, one $U(h)$ per block. Fixing the number $s_e$ of
- even slots and $s_o$ of odd, a $U(h)times U(h)$-sector with top weights
- $(gamma,xi)$ has multiplicity space, as an $S_s$-representation,
- $Ind_{S_{s_e}times S_{s_o}}^{S_s}(V_gamma ⊗ V_{xi^{rm tr}})$,
- where $xi^{rm tr}$ means the transpose because the odd block contributes
+ reordering of the odd factors. This S_s-action commutes with a diagonal
+ U(h)times U(h) action, one U(h) per block. Fixing the number s_e of
+ even slots and s_o of odd, a U(h)times U(h)-sector with top weights
+ (gamma,xi) has multiplicity space, as an S_s-representation,
+ Ind_{S_{s_e}times S_{s_o}}^{S_s}(V_gamma ⊗ V_{xi^{rm tr}}),
+ where xi^{rm tr} means the transpose because the odd block contributes
a sign. This is the standard "sign twist and induction" combination.
(Etingof et al., with James 1978 Thm 6.7 for the sign and Thm 16.4
for the induction.)
-
-item[(T7)] Group-algebra matrix actions. Given a matrix $M$ on an
- irreducible $V_mu$ of a subgroup $R⊆ S_N$, form the element of
- $mathbb CR$bbCR$ with matrices $M$ on the $V_mu$-block and $0$ elsewhere.
- Viewed in any larger representation, its restriction to $R$ acts as
+[(T7)] Group-algebra matrix actions. Given a matrix M on an
+ irreducible V_mu of a subgroup R⊆ S_N, form the element of
+ mathbb CRbbCR with matrices M on the V_mu-block and 0 elsewhere.
+ Viewed in any larger representation, its restriction to R acts as
"the chosen matrix on one copy of the carrier, and identity on every
- multiplicity copy". Its coefficient at $gin R$ is
- $(D_mu)/(|R|)Tr(Mrho_mu(g^{-1}))$. (Orthogonality and
+ multiplicity copy". Its coefficient at gin R is
+ (D_mu)/(|R|)Tr(Mrho_mu(g^{-1})). (Orthogonality and
Plancherel; Etingof et al.) We call this a matrix action
- supported on $mu$. When $M$ is the rank-one projector onto a unit
- vector $e$, it is an orthogonal projection on the $R$-part and is written
- $P_{mu,e}$; it uses one direction of the carrier and is the identity on
+ supported on mu. When M is the rank-one projector onto a unit
+ vector e, it is an orthogonal projection on the R-part and is written
+ P_{mu,e}; it uses one direction of the carrier and is the identity on
multiplicity copies.
-
-item[(T8)] Cauchy--Schwarz for sums of projections. When a positive
+[(T8)] Cauchy--Schwarz for sums of projections. When a positive
operator is a sum of orthogonal projections onto orthogonal subspaces,
comparison between two such decompositions is controlled by
Cauchy--Schwarz, and nonnegativity of each irreducible's contribution
lets one take traces representation by representation. We use this
without further comment.
-
-item[(T9)] Entropy of an occupation law. For a probability vector
- $(omega_{ij})$ supported on the cells of a board and marginals
- $(p_i),(q_j)$, the relative entropy of $omega$ from the product
- $(p_iq_j)$ is at most $log(mn/s)$ when $omega$ is uniform on $s$
- occupied cells of an $mtimes n$ board. (Standard; the argument is
+[(T9)] Entropy of an occupation law. For a probability vector
+ (omega_{ij}) supported on the cells of a board and marginals
+ (p_i),(q_j), the relative entropy of omega from the product
+ (p_iq_j) is at most log(mn/s) when omega is uniform on s
+ occupied cells of an mtimes n board. (Standard; the argument is
the entropy/subadditivity duality of Carlen--Cordero-Erausquin 2009,
Thm 2.1.)
-
-item[(T10)] Interpolation of a bilinear Schatten map. If a bilinear
- map has norm $le e^{E/2}$ at the $2$-Schatten endpoint and $le1$ at the
- operator-norm endpoint, then it has norm $le e^{E/p}$ at the
- $p$-Schatten norm for $2le p<∞$, with $E$ independent of $p$.
+[(T10)] Interpolation of a bilinear Schatten map. If a bilinear
+ map has norm le e^{E/2} at the 2-Schatten endpoint and le1 at the
+ operator-norm endpoint, then it has norm le e^{E/p} at the
+ p-Schatten norm for 2le p<∞, with E independent of p.
(Complex interpolation of Schatten classes / three-lines; see the
computation in Part~part:interp. We spell it out.)
@@ -311,42 +298,42 @@ part{A dimension lower bound}
# Every nontrivial type that survives is large
-One matching layer kills every partition of length $>N/2$: averaging a
+One matching layer kills every partition of length >N/2: averaging a
swap along one coordinate projects onto the invariants of a Young subgroup
-$S_2^{N/2}$, and only partitions of length $le N/2$ survive. So we only
-need to bound types $lambda$ with at most $N/2$ rows. Below, $k=N-lambda_1$
+S_2^{N/2}, and only partitions of length le N/2 survive. So we only
+need to bound types lambda with at most N/2 rows. Below, k=N-lambda_1
is the number of boxes below the first row.
[Dimension away from the first row]
-There is an absolute $c>0$ such that, for every $Nge2$ and every
-nontrivial partition $lambda⊢ N$ with at most $N/2$ rows,
+There is an absolute c>0 such that, for every Nge2 and every
+nontrivial partition lambda⊢ N with at most N/2 rows,
[
- log D_lambda ge c,k,qquad k=N-lambda_1.
+ log D_lambda ge c,k, k=N-lambda_1.
]
Proof.
-If both width and height are $<N/10$, every hook length is $le N/5$, so
-the hook formula gives $log D_lambdage cNge ck$.
-
-Otherwise pass to $lambda$ or its transpose so the first row has length
-$uge N/10$; let $v=N-u$ be the remaining boxes. Keep that whole first
-row and a subdiagram of size $ell=min(v,lfloor u/2rfloor)$ below it.
-By branching (T1) $D_lambda$ is at least the dimension of that
-subdiagram. For a diagram with first row $u$ and any fixed lower part of
-size $ell$, the hook formula plus (T4) bounds
+If both width and height are <N/10, every hook length is le N/5, so
+the hook formula gives log D_lambdage cNge ck.
+
+Otherwise pass to lambda or its transpose so the first row has length
+uge N/10; let v=N-u be the remaining boxes. Keep that whole first
+row and a subdiagram of size ell=min(v,lfloor u/2rfloor) below it.
+By branching (T1) D_lambda is at least the dimension of that
+subdiagram. For a diagram with first row u and any fixed lower part of
+size ell, the hook formula plus (T4) bounds
[
D_lambda ge binom{u+ell}{ell},exp!Big(-(ell)/(u-ell+1)Big).
]
-The lower part has width $leell$, so it adds at most $ell$ to each top-row
+The lower part has width leell, so it adds at most ell to each top-row
hook; the correction is the displayed exponential. In the original case
-$ellge c_1 k$ (large $N$); in the transpose case the height hypothesis
-gives $vge N/2ge k$, so again $ellge c_1 k$. With $ellle u/2$ the
-logarithm is $ge(log3-1)ellge c_2 k$. Finite small $N$ are covered by
-decreasing $c$; the only one-dimensional irreducibles are trivial and
+ellge c_1 k (large N); in the transpose case the height hypothesis
+gives vge N/2ge k, so again ellge c_1 k. With ellle u/2 the
+logarithm is ge(log3-1)ellge c_2 k. Finite small N are covered by
+decreasing c; the only one-dimensional irreducibles are trivial and
sign, both excluded here.
-In particular, if $k>N^{1-eps}$ for a small fixed $eps>0$ then
+In particular, if k>N^{1-eps} for a small fixed eps>0 then
log D_lambda ge c_0,N^{1-eps}.
@@ -357,140 +344,140 @@ part{The overlap theorem}
# A board with deleted cells
-This is the technical heart. Picture an $mtimes n$ board, $mn=N$. Colour
-some cells occupied (there are $s$ of them) and the rest
-deleted (there are $t=N-s$). Put the symmetric group $G_s$ on the
-occupied cells. Restricting a representation $V_a$ of $G_s$ to the
-within-row group $S_{n}^m$, and also to the within-column group $S_m^n$,
+This is the technical heart. Picture an mtimes n board, mn=N. Colour
+some cells occupied (there are s of them) and the rest
+deleted (there are t=N-s). Put the symmetric group G_s on the
+occupied cells. Restricting a representation V_a of G_s to the
+within-row group S_{n}^m, and also to the within-column group S_m^n,
gives two decompositions that do not commute. The theorem bounds how a
row-type direction and a column-type direction can overlap.
[Overlap on an arbitrary occupied board]
-Let $a⊢ s$ be a partition lying in the $(h,h)$-hook, i.e. no box of
-$a$ has both row index and column index greater than $h$; here $1le hle N$.
-Decompose $V_a$ under the row group and, separately, under the column
-group. For row-types $sigma$ (a tuple of partitions) and column-types
-$theta$, let $I_{sigma,u}colon V_sigmato V_a$ and
-$I_{theta,v}colon V_thetato V_a$ be isometries onto orthogonal copies,
-over all copies $u$ and $v$, chosen so that their images span the
+Let a⊢ s be a partition lying in the (h,h)-hook, i.e. no box of
+a has both row index and column index greater than h; here 1le hle N.
+Decompose V_a under the row group and, separately, under the column
+group. For row-types sigma (a tuple of partitions) and column-types
+theta, let I_{sigma,u}colon V_sigmato V_a and
+I_{theta,v}colon V_thetato V_a be isometries onto orthogonal copies,
+over all copies u and v, chosen so that their images span the
corresponding isotypic parts. Then
sum_{u,v}|I_{sigma,u}^* I_{theta,v}|_{op}^2
le exp!big{C[(m+n+1)h^2log(N+2)+t]big},
minBig{1, (D_sigma D_theta)/(D_a)Big}.
-Here $C$ is absolute. When $s=0$ the empty representation has dimension $1$.
+Here C is absolute. When s=0 the empty representation has dimension 1.
In plain words. The overlaps between the two decompositions are
tiny: the total squared overlap is bounded by an explicit factor (the
-exponential) times the "quantum" ratio $D_sigma D_theta/D_a$, never
-more than $1$. The exponential depends on the hook width $h$ and on the
-number $t$ of deleted cells, which is exactly the cost of having a
+exponential) times the "quantum" ratio D_sigma D_theta/D_a, never
+more than 1. The exponential depends on the hook width h and on the
+number t of deleted cells, which is exactly the cost of having a
non-rectangular occupied region.
Proof. [Proof of Theorem~thm:occupied]
-For $s=0$ there is nothing to prove. Throughout we use the signed tensor
-space $mathcal L=(calL=(mathbb C^hbbC^h ⊕ mathbb C^h)^bbC^h)^{ ⊗ s}$ and the
-signed $S_s$-action (T6).
+For s=0 there is nothing to prove. Throughout we use the signed tensor
+space mathcal L=(calL=(mathbb C^hbbC^h ⊕ mathbb C^h)^bbC^h)^{ ⊗ s} and the
+signed S_s-action (T6).
smallskipnoindentRealisation.
-By (T5)--(T7) the standard signed realization carries $V_a$ inside
-$mathcal L$;calL$; concretely, at fixed parity counts $s_e,s_o$ and sector top
-weights $(gamma,xi)$ (both of length $le h$, degrees $s_e,s_o$), the
-sector's multiplicity space is $Ind_{S_{s_e}times S_{s_o}}^{S_s}(V_gamma ⊗
- V_{xi^{rm tr}})$. There is a sector containing $V_a$: take $gamma$ as the
-first $h$ rows of $a$ and $xi^{rm tr}$ as the rest (a diagram of width
-$le h$), so that the relevant Littlewood--Richardson coefficient is
+By (T5)--(T7) the standard signed realization carries V_a inside
+mathcal L;calL; concretely, at fixed parity counts s_e,s_o and sector top
+weights (gamma,xi) (both of length le h, degrees s_e,s_o), the
+sector's multiplicity space is Ind_{S_{s_e}times S_{s_o}}^{S_s}(V_gamma ⊗
+ V_{xi^{rm tr}}). There is a sector containing V_a: take gamma as the
+first h rows of a and xi^{rm tr} as the rest (a diagram of width
+le h), so that the relevant Littlewood--Richardson coefficient is
positive. This sector is the arena for the rest of the proof.
smallskipnoindentSize and entropy of sectors.
-The dimensions of the $U(h)times U(h)$ carriers, and the number of
-sectors, are at most $exp(O(h^2log(N+2)))$ (count symbol occupations row
-by row in a semistandard tableau). The multiplicity of any $S_s$-type
-$chi$ in the signed action is also $leexp(O(h^2log(N+2)))$: given
-$(gamma,xi)$ contributing to $chi$, the skew shape $chi/xi^{rm tr}$
-has content $gamma$ and its part in the first $h$ columns has at most
-$h^2$ boxes, beyond which columns are determined. Hence (with
-$u=|gamma|+|xi|$)
+The dimensions of the U(h)times U(h) carriers, and the number of
+sectors, are at most exp(O(h^2log(N+2))) (count symbol occupations row
+by row in a semistandard tableau). The multiplicity of any S_s-type
+chi in the signed action is also leexp(O(h^2log(N+2))): given
+(gamma,xi) contributing to chi, the skew shape chi/xi^{rm tr}
+has content gamma and its part in the first h columns has at most
+h^2 boxes, beyond which columns are determined. Hence (with
+u=|gamma|+|xi|)
D_chi le exp(H(gamma,xi)) le D_chiexp(O(h^2log(N+2))),
- qquad
+
H(gamma,xi)=sum_igamma_ilog(u/gamma_i)+sum_jxi_jlog(u/xi_j).
-The first inequality is $D_chilebinom{u}{|gamma|}D_gamma D_xi$ (from
+The first inequality is D_chilebinom{u}{|gamma|}D_gamma D_xi (from
T2 and transposition-invariance of dimension) with multinomial bounds; the
-second is (T4) applied to the hooks in the first $h$ rows and columns
-together with $|gammacapxi^{rm tr}|le h^2$.
+second is (T4) applied to the hooks in the first h rows and columns
+together with |gammacapxi^{rm tr}|le h^2.
smallskipnoindentTurning overlap into a trace.
-Let $P_sigma,P_theta$ be the row- and column-isotypic projections inside
-$V_a$, and expand the embeddings: the sum of squared Hilbert--Schmidt norms
-$sum_{u,v}|I_{sigma,u}^*I_{theta,v}|_2^2=Tr_{V_a}(P_sigma P_theta)$,
+Let P_sigma,P_theta be the row- and column-isotypic projections inside
+V_a, and expand the embeddings: the sum of squared Hilbert--Schmidt norms
+sum_{u,v}|I_{sigma,u}^*I_{theta,v}|_2^2=Tr_{V_a}(P_sigma P_theta),
which dominates the required sum of squared operator norms. Lift to a
-sector projector $P$ of $mathcal L$calL$ and subgroup isotypic projectors
-$Q_sigma,Q_theta$. Since $P$ commutes with the signed permutations and
+sector projector P of mathcal LcalL and subgroup isotypic projectors
+Q_sigma,Q_theta. Since P commutes with the signed permutations and
each irreducible contributes nonnegatively,
[
Tr_{V_a}(P_sigma P_theta) le Tr_{mathcal L}calL(Q_sigma P Q_theta P).
]
smallskipnoindentMajorising by product states.
-We bound $Q_sigma$ in the positive semidefinite order by a probability
-mixture of tensor products $S=⊗_{cells} S_i$, with the same
-even state $S_i$ in every cell of row $i$. The prefactor is
-$D_sigmaexp(Cm,h^2log(N+2))$. On one row of length $l$, bound the
-projection for a partition $chi$ by the sum over compatible sector top
-weights $(gamma_0,xi_0)$; in each sector, average by
-$U(h)times U(h)$ the identical-cell product of the diagonal state with
-entries $(gamma_{0,i}/l,xi_{0,j}/l)$. After averaging this product acts
-as a scalar $geexp(-H(gamma_0,xi_0))/dim(carrier)$ on that
+We bound Q_sigma in the positive semidefinite order by a probability
+mixture of tensor products S=⊗_{cells} S_i, with the same
+even state S_i in every cell of row i. The prefactor is
+D_sigmaexp(Cm,h^2log(N+2)). On one row of length l, bound the
+projection for a partition chi by the sum over compatible sector top
+weights (gamma_0,xi_0); in each sector, average by
+U(h)times U(h) the identical-cell product of the diagonal state with
+entries (gamma_{0,i}/l,xi_{0,j}/l). After averaging this product acts
+as a scalar geexp(-H(gamma_0,xi_0))/dim(carrier) on that
sector (highest-weight eigenvalue via T5), and the dimensions are folded
-into the prefactor. Do the same for $Q_theta$ with column states $T_j$ and
-prefactor $D_thetaexp(Cn,h^2log(N+2))$. Positivity then reduces us to
-bounding $Tr_{mathcal L}calL(S P T P)$.
+into the prefactor. Do the same for Q_theta with column states T_j and
+prefactor D_thetaexp(Cn,h^2log(N+2)). Positivity then reduces us to
+bounding Tr_{mathcal L}calL(S P T P).
smallskipnoindentThe quarter-root filter.
Two normalisations are needed at once: the global sector must pay
-$exp(-H(gamma,xi))$ in the squared norm, and the per-cell overlaps must
-average to $le1$ under the row- and column-marginals. Let $barbar S,S,barbar T$T$
-be the average cell-states over the $s$ occupied cells, put
-$X=barbar S^S^{1/2}$, $Y=barbar T^T^{1/2}$, and set
-$S_i'=X^{-1/2}S_iX^{-1/2}$, $T_j'=Y^{-1/2}T_jY^{-1/2}$ (inverses on
-supports). With $L=(X^{1/2})^{ ⊗ s}P(Y^{1/2})^{ ⊗ s}$ we have
-$Tr_{mathcal L}calL(SPTP)=|(S')^{1/2}L(T')^{1/2}|_2^2$. The matrix $L$ acts
-on the sector with operator norm $leexp(-H(gamma,xi)/2)$: indeed
-$(X^{1/2})^{ ⊗ s}=(barbar S^S^{1/4})^{ ⊗ s}$ has norm
-$leexp(-H(gamma,xi)/4)$ on that sector by the largest-weight monomial
-in the eigenvalues of $barbar S$S$ (whose sum is $1$); the same for $barbar T$.T$.
-By matrix-coefficient orthogonality for the block-unitary group, $L$ is an
-integral of $U^{ ⊗ s}$ over block unitaries with total coefficient
-$le exp(-H(gamma,xi)/2)cdot(squared carrier dimension)$.
+exp(-H(gamma,xi)) in the squared norm, and the per-cell overlaps must
+average to le1 under the row- and column-marginals. Let barbar S,S,barbar TT
+be the average cell-states over the s occupied cells, put
+X=barbar S^S^{1/2}, Y=barbar T^T^{1/2}, and set
+S_i'=X^{-1/2}S_iX^{-1/2}, T_j'=Y^{-1/2}T_jY^{-1/2} (inverses on
+supports). With L=(X^{1/2})^{ ⊗ s}P(Y^{1/2})^{ ⊗ s} we have
+Tr_{mathcal L}calL(SPTP)=|(S')^{1/2}L(T')^{1/2}|_2^2. The matrix L acts
+on the sector with operator norm leexp(-H(gamma,xi)/2): indeed
+(X^{1/2})^{ ⊗ s}=(barbar S^S^{1/4})^{ ⊗ s} has norm
+leexp(-H(gamma,xi)/4) on that sector by the largest-weight monomial
+in the eigenvalues of barbar SS (whose sum is 1); the same for barbar T.T.
+By matrix-coefficient orthogonality for the block-unitary group, L is an
+integral of U^{ ⊗ s} over block unitaries with total coefficient
+le exp(-H(gamma,xi)/2)cdot(squared carrier dimension).
smallskipnoindentThe cell product and an entropy bound.
-For a block unitary $U$ let $z_{ij}=Tr(S_i'UT_j'U^*)ge0$. The weighted
-squared Hilbert--Schmidt norm of $U^{ ⊗ s}$ on the occupied cells is
-$prod_{cells}z_{ij}$. Under the product of row-marginals $p_i$ and
-column-marginals $q_j$ (uniform occupation of the $s$ cells), the mean is
-$Tr(barbar S^S^{1/2}Ubarbar T^T^{1/2}U^*)le1$ by Cauchy--Schwarz. So the
-$omega$-average of $log z_{ij}$ is at most the relative entropy of the
-occupation law $omega$ from $p_iq_j$, which is $lelog(mn/s)lelog(N/s)$
-(T9). Hence $prod z_{ij}leexp(slog(N/s))leexp(t)$. Inserting the
-integral for $L$ and the triangle inequality,
+For a block unitary U let z_{ij}=Tr(S_i'UT_j'U^*)ge0. The weighted
+squared Hilbert--Schmidt norm of U^{ ⊗ s} on the occupied cells is
+prod_{cells}z_{ij}. Under the product of row-marginals p_i and
+column-marginals q_j (uniform occupation of the s cells), the mean is
+Tr(barbar S^S^{1/2}Ubarbar T^T^{1/2}U^*)le1 by Cauchy--Schwarz. So the
+omega-average of log z_{ij} is at most the relative entropy of the
+occupation law omega from p_iq_j, which is lelog(mn/s)lelog(N/s)
+(T9). Hence prod z_{ij}leexp(slog(N/s))leexp(t). Inserting the
+integral for L and the triangle inequality,
[
Tr_{mathcal L}calL(SPTP) le exp{C h^2log(N+2)+t},exp(-H(gamma,xi)),
]
-and $D_aleexp(H(gamma,xi))$ by (eq:sector-entropy). Multiplying by
-the mixture prefactors $D_sigma D_theta$ and dividing by $D_a$ gives
-(eq:occupied), with $min{1,D_sigma D_theta/D_a}$ recording that
-the overlap can never exceed $1$.
+and D_aleexp(H(gamma,xi)) by (eq:sector-entropy). Multiplying by
+the mixture prefactors D_sigma D_theta and dividing by D_a gives
+(eq:occupied), with min{1,D_sigma D_theta/D_a} recording that
+the overlap can never exceed 1.
A second, independent proof of an overlap bound uses deletion frames:
-resolve a row-type vector by remembering only $t$ marked positions per row,
-control the resulting marked kernels with a Schatten-$8$ estimate, and use
-a signed-tensor Schatten-$2$ estimate for the complementary shapes. It gives
+resolve a row-type vector by remembering only t marked positions per row,
+control the resulting marked kernels with a Schatten-8 estimate, and use
+a signed-tensor Schatten-2 estimate for the complementary shapes. It gives
a uniform Schatten exponent without weights.
@@ -498,7 +485,7 @@ A third proof, on coherent states, keeps the deleted positions as an
ordered list and compares row and column projections by averaging
highest-weight coherent vectors and matching their one-cell densities by a
minimum-norm (Kempf--Ness type) argument. It yields an explicit restoration
-factor $e^{3t}binom{N}{t}$. These routes are not needed below.
+factor e^{3t}binom{N}{t}. These routes are not needed below.
%=========================================================================
@@ -507,30 +494,30 @@ part{From overlap to the row-column Fourier estimate}
# The weighted overlap
-Now fix the split of the sweep. Write $N=2^d$ as $mn$ with $m,n$ both of
-order $sqrt N$ (they are the sizes of a column and a row for a balanced
-split of the $d$ bits). The row part acts within rows, the column part
+Now fix the split of the sweep. Write N=2^d as mn with m,n both of
+order sqrt N (they are the sizes of a column and a row for a balanced
+split of the d bits). The row part acts within rows, the column part
within columns; both are products of smaller independent sweeps.
-We assume for the estimate that the current $lambda$ is not sparse, in the
+We assume for the estimate that the current lambda is not sparse, in the
sense
- k=N-lambda_1>N^{1-eps},qquad lambda^{rm tr}_1le N/2,
+ k=N-lambda_1>N^{1-eps}, lambda^{rm tr}_1le N/2,
-with the small $eps$ of (eq:dim-large); the sparse range is handled
-in Part~part:sparse. The weights $W_lambda$ are built in
+with the small eps of (eq:dim-large); the sparse range is handled
+in Part~part:sparse. The weights W_lambda are built in
(eq:Jdef) below; for the moment only their two properties matter,
-$D_lambda^{3/4}le W_lambdale D_lambda$, and the exact minimisation
+D_lambda^{3/4}le W_lambdale D_lambda, and the exact minimisation
formula (eq:Jdef).
[Weighted overlap]
-Under (eq:not-sparse), for irreducibles $mu$ of the row group and
-$nu$ of the column group and unit carrier vectors $e,f$,
+Under (eq:not-sparse), for irreducibles mu of the row group and
+nu of the column group and unit carrier vectors e,f,
W_lambda,Tr_{V_lambda}(P_{mu,e}P_{nu,f})
le W_mu W_nu,exp!big{O((log D_lambda)/d)big},
-with an absolute implied constant independent of the types and of $d$.
+with an absolute implied constant independent of the types and of d.
The proof needs the weight formula, so we state it now.
@@ -541,136 +528,136 @@ The weight is a small ``tax'' on each diagram designed so that the tax of
a parent equals the tax of its children plus exactly enough to pay
for restoring deleted cells. Fix absolute constants
[
- b_0=tfrac14,quad delta=tfrac1{16},quad b_1=(b_0delta)/(4),quad
- A=10,quad eta=(b_1)/(2A),quad eps=(eta)/(8),
+ b_0=tfrac14, delta=tfrac1{16}, b_1=(b_0delta)/(4),
+ A=10, eta=(b_1)/(2A), eps=(eta)/(8),
]
and the penalty function
[
- F_L(r)=rmin{log(L/r), etalog L}qquad(1le rle L),qquad F_L(0)=0.
+ F_L(r)=rmin{log(L/r), etalog L}(1le rle L), F_L(0)=0.
]
-For a diagram $lambda⊢ L$ and a subdiagram $a⊆lambda$
-(itself a Young diagram) let $r=L-|a|$ and define
+For a diagram lambda⊢ L and a subdiagram a⊆lambda
+(itself a Young diagram) let r=L-|a| and define
J(lambda)=min_{a⊆lambda}big{b_0log D_a+b_1 rlog L-AF_L(r)big},
- qquad W_lambda=D_lambda,e^{-J(lambda)}.
+ W_lambda=D_lambda,e^{-J(lambda)}.
-Empty diagrams have $J=0$, $W=1$. Since $AF_L(r)le(b_1)/(2)rlog L$,
-the minimised expression is nonnegative, and $a=lambda$ shows
-$0le J(lambda)letfrac14log D_lambda$; hence
+Empty diagrams have J=0, W=1. Since AF_L(r)le(b_1)/(2)rlog L,
+the minimised expression is nonnegative, and a=lambda shows
+0le J(lambda)letfrac14log D_lambda; hence
D_lambda^{3/4} le W_lambda le D_lambda.
-On tuples (product groups) $J$ is summed and $W$ multiplied.
+On tuples (product groups) J is summed and W multiplied.
-The point of $J$ is this trimming lemma: the minimising $a$ can be
-taken inside the $(h,h)$-hook, $h=lfloor N^deltarfloor$, at additive
-cost $O(h^2)$ in the minimum of (eq:Jdef). Indeed, trimming the boxes
-with both indices $>h$ from any minimiser $a_1$ to get $a$ changes
-$log D_{a_1}-log D_a$ by at least $x(log h-C)-Ch^2$ where $x$ is the
-number trimmed, while the penalty changes by at most $(b_1log N+A)x$; as
-$b_1<b_0delta$ the trim is favorable. Consequently, taking $a$ in the
-hook with $t=N-|a|$,
+The point of J is this trimming lemma: the minimising a can be
+taken inside the (h,h)-hook, h=lfloor N^deltarfloor, at additive
+cost O(h^2) in the minimum of (eq:Jdef). Indeed, trimming the boxes
+with both indices >h from any minimiser a_1 to get a changes
+log D_{a_1}-log D_a by at least x(log h-C)-Ch^2 where x is the
+number trimmed, while the penalty changes by at most (b_1log N+A)x; as
+b_1<b_0delta the trim is favorable. Consequently, taking a in the
+hook with t=N-|a|,
b_0log D_a+b_1tlog N-AF_N(t)=J(lambda)+O(h^2),
- qquad tlog Nle C(log D_lambda+h^2).
+ tlog Nle C(log D_lambda+h^2).
# Proof of the weighted overlap
Proof. [Proof of Proposition~prop:weighted-overlap]
-Take the hook subdiagram $a$ from (eq:trim), and choose a diagram
-$b⊢ t$ so that $V_lambda$ occurs in
-$mathcal I=calI=Ind_{G_{N-t}times G_t}^{G_N}(V_a ⊗ V_b)$ (possible by
-branching and decomposing the restriction). The trace on $mathcal I$calI$ of
-$XY$, for $X=P_{mu,e}$ and $Y=P_{nu,f}$, bounds the wanted trace on
-$V_lambda$, since each $G_N$-type contributes nonnegatively.
+Take the hook subdiagram a from (eq:trim), and choose a diagram
+b⊢ t so that V_lambda occurs in
+mathcal I=calI=Ind_{G_{N-t}times G_t}^{G_N}(V_a ⊗ V_b) (possible by
+branching and decomposing the restriction). The trace on mathcal IcalI of
+XY, for X=P_{mu,e} and Y=P_{nu,f}, bounds the wanted trace on
+V_lambda, since each G_N-type contributes nonnegatively.
smallskipnoindentFibers at deleted sets.
-$mathcal I$calI$ is a direct sum over the $t$-sets $Z$ of the board; at $Z$, the
-stabiliser acts as $V_a$ on the complement of $Z$ and $V_b$ on $Z$. Let
-$v_i$ count $Z$ in row $i$ and $u_j$ in column $j$, and set
+mathcal IcalI is a direct sum over the t-sets Z of the board; at Z, the
+stabiliser acts as V_a on the complement of Z and V_b on Z. Let
+v_i count Z in row i and u_j in column j, and set
[
- L_R=prod_ibinom{n}{v_i},quad
- L_C=prod_jbinom{m}{u_j},quad
- L_0=binom{N}{t},quad
+ L_R=prod_ibinom{n}{v_i},
+ L_C=prod_jbinom{m}{u_j},
+ L_0=binom{N}{t},
E_0=H_R+H_C-H_0,
]
-$H_R=sum_i v_ilog(n/v_i)$, $H_C=sum_j u_jlog(m/u_j)$,
-$H_0=tlog(N/t)$ (zero terms are $0$). For a nonempty profile $E_0ge0$ (it
-is $t$ times a relative entropy). The layout count is controlled by
+H_R=sum_i v_ilog(n/v_i), H_C=sum_j u_jlog(m/u_j),
+H_0=tlog(N/t) (zero terms are 0). For a nonempty profile E_0ge0 (it
+is t times a relative entropy). The layout count is controlled by
logfrac{L_{RC}^2L_0}{L_RL_C} le E_0+O(t),
-where $L_{RC}$ is the number of $t$-sets with the given row- and
-column-profiles: $log L_Rge H_R$, $log L_Cge H_C$,
-$log L_0le H_0+t$ by binomial bounds, and subadditivity of entropy gives
-$log L_{RC}le E_0+2t$ (take a uniformly random occupied cell with
-independent row index $I$ and column index $J$, and use
-$H(Vmid I,J)le H(Vmid I)+H(Vmid J)-H(V)$).
+where L_{RC} is the number of t-sets with the given row- and
+column-profiles: log L_Rge H_R, log L_Cge H_C,
+log L_0le H_0+t by binomial bounds, and subadditivity of entropy gives
+log L_{RC}le E_0+2t (take a uniformly random occupied cell with
+independent row index I and column index J, and use
+H(Vmid I,J)le H(Vmid I)+H(Vmid J)-H(V)).
smallskipnoindentDiagonal blocks.
-The block trace of $XY$ pairs $Z,Z'$ with equal profiles; off-diagonal
+The block trace of XY pairs Z,Z' with equal profiles; off-diagonal
blocks are bounded by the geometric mean of diagonal overlaps (Cauchy--
-Schwarz for $X^{1/2}UX'^{1/2}$). For a diagonal block at $Z$, the row
-stabiliser $R_Z$ acts separately off and on $Z$; if $alpha=(sigma,tau)$
-denotes the two parts, then (T7, orthogonality, $|R|=L_R|R_Z|$)
+Schwarz for X^{1/2}UX'^{1/2}). For a diagonal block at Z, the row
+stabiliser R_Z acts separately off and on Z; if alpha=(sigma,tau)
+denotes the two parts, then (T7, orthogonality, |R|=L_R|R_Z|)
[
X_{ZZ}=(D_mu)/(L_R)sum_alpha(1)/(D_alpha)mathcal P_calP_{alpha,M_alpha},
]
-the $M_alphasucceq0$ with $sum_alphaTr M_alpha=1$ obtained by tracing
-out the multiplicity space. Similarly $Y_{ZZ}$ with $D_nu/L_C$ and column
-stabiliser types $zeta=(theta,pi)$. The only subtlety is that $M_alpha$
+the M_alphasucceq0 with sum_alphaTr M_alpha=1 obtained by tracing
+out the multiplicity space. Similarly Y_{ZZ} with D_nu/L_C and column
+stabiliser types zeta=(theta,pi). The only subtlety is that M_alpha
need not be a product of a surviving-cell state and a deleted-cell state;
the next lemma (which needs no independence) removes this worry.
[Arbitrary carrier vectors]
-Let $A_lcolon E'to E$ and $B_rcolon F'to F$ be finite families with
-$sum_r|< x,B_r y>|^2le C|x|^2|y|^2$. Then for unit
-$win E ⊗ F$ and $w'in E' ⊗ F'$,
-$sum_{l,r}|< w,(A_l ⊗ B_r)w'>|^2le Csum_l|A_l|_op^2$.
+Let A_lcolon E'to E and B_rcolon F'to F be finite families with
+sum_r|< x,B_r y>|^2le C|x|^2|y|^2. Then for unit
+win E ⊗ F and w'in E' ⊗ F',
+sum_{l,r}|< w,(A_l ⊗ B_r)w'>|^2le Csum_l|A_l|_op^2.
Proof.
-For fixed $l$, $Bmapsto< w,(A_l ⊗ B)w'>$ has operator
-norm $le|A_l|_op$; by trace-norm duality it is
-$sum_s c_s< x_s,By_s>$ with unit $x_s,y_s$, $c_sge0$,
-$sum_s c_sle|A_l|_op$. The triangle inequality in $ell^2(r)$, then
-squaring and summing in $l$, finishes.
+For fixed l, Bmapsto< w,(A_l ⊗ B)w'> has operator
+norm le|A_l|_op; by trace-norm duality it is
+sum_s c_s< x_s,By_s> with unit x_s,y_s, c_sge0,
+sum_s c_sle|A_l|_op. The triangle inequality in ell^2(r), then
+squaring and summing in l, finishes.
-The fiber overlap for arbitrary pure carrier vectors $w,w'$ therefore has
-the form $sum_{l,r}|< w,(A_l ⊗ B_r)w'>|^2$ with $A_l$ the
-row-decomposition overlaps and $B_r$ the column ones. On $Z$ itself the
+The fiber overlap for arbitrary pure carrier vectors w,w' therefore has
+the form sum_{l,r}|< w,(A_l ⊗ B_r)w'>|^2 with A_l the
+row-decomposition overlaps and B_r the column ones. On Z itself the
row and column subgroups intersect trivially, so the pairwise products of
-their group elements use unique factorisations; Plancherel in $G_t$ gives
-for unit $x,y$
+their group elements use unique factorisations; Plancherel in G_t gives
+for unit x,y
sum_r|< x,B_ry>|^2 le (D_tau D_pi)/(D_b)
(t!)/(prod_i v_i!prod_j u_j!) le (D_tau D_pi)/(D_b)e^{E_0+O(t)}
-(using $E_0=tlog t-sum v_ilog v_i-sum u_jlog u_j$ and factorial
+(using E_0=tlog t-sum v_ilog v_i-sum u_jlog u_j and factorial
bounds). Lemma~lem:entangled upgrades this to arbitrary carrier
-vectors, and Theorem~thm:occupied bounds $sum_l|A_l|_op^2$.
+vectors, and Theorem~thm:occupied bounds sum_l|A_l|_op^2.
smallskipnoindentPutting the pieces together.
-Write $S=max{0,log(D_sigma D_theta/D_a)}$. Combining
+Write S=max{0,log(D_sigma D_theta/D_a)}. Combining
(eq:occupied), the fiber bound via Lemma~lem:entangled, and
-(eq:on-Z), and dividing by $D_alpha D_zeta$ from the diagonal-block
+(eq:on-Z), and dividing by D_alpha D_zeta from the diagonal-block
formulas, the pure-state bound becomes
[
(1)/(D_aD_b)exp{E_0-S+O(t+(m+n+1)h^2log(N+2))}.
]
-The positive mixtures have total weight $1$, so no extra count appears.
-Multiply by $D_mu D_nu L_{RC}^2/(L_RL_C)$ and use
-$D_lambdale L_0D_aD_b$ and (eq:layout):
+The positive mixtures have total weight 1, so no extra count appears.
+Multiply by D_mu D_nu L_{RC}^2/(L_RL_C) and use
+D_lambdale L_0D_aD_b and (eq:layout):
(D_mu D_nu)/(D_lambda)
exp{2E_0-S+O(t+(m+n+1)h^2log(N+2))}.
-smallskipnoindentThe weight budget pays $2E_0-S$.
-Restrict $mu_i$ to its complement row of size $n-v_i$: the surviving type
-$sigma_i$ is a subpartition of $mu_i$ of that size; likewise $theta_j$
-is a subpartition of $nu_j$ of size $m-u_j$. So
+smallskipnoindentThe weight budget pays 2E_0-S.
+Restrict mu_i to its complement row of size n-v_i: the surviving type
+sigma_i is a subpartition of mu_i of that size; likewise theta_j
+is a subpartition of nu_j of size m-u_j. So
[
J(mu)+J(nu)le b_0log(D_sigma D_theta)+b_1tlog N
-ABig(sum_i F_n(v_i)+sum_j F_m(u_j)Big).
@@ -680,17 +667,17 @@ Together with (eq:trim), this gives
J(lambda)-J(mu)-J(nu) ge -b_0 S+AE_0
-Obig(h^2+(mn^{1-eta}+nm^{1-eta})log(N+2)big).
-Therefore, with $mathcal E$calE$ the error in (eq:budget),
+Therefore, with mathcal EcalE the error in (eq:budget),
[
2E_0-S-[J(lambda)-J(mu)-J(nu)]
le (2-A)E_0-(1-b_0)S+mathcal EcalElemathcal E,calE,
]
-since $Age2$, $b_0le1$, $E_0,Sge0$. This is exactly the statement that
-replacing $D_mu D_nu/D_lambda$ by $W_mu W_nu/W_lambda$ (i.e.
-dividing (eq:pref-final) by $D_lambda e^{-J}$ and multiplying by the
-child weights) leaves only the error $mathcal E$.calE$. All error terms and the
-count of profiles are $O((log D_lambda)/d)$ by (eq:dim-large), and
-$hle N^{1/16}$, $m,nasympsqrt N$, $eps<eta/2$. This is
+since Age2, b_0le1, E_0,Sge0. This is exactly the statement that
+replacing D_mu D_nu/D_lambda by W_mu W_nu/W_lambda (i.e.
+dividing (eq:pref-final) by D_lambda e^{-J} and multiplying by the
+child weights) leaves only the error mathcal E.calE. All error terms and the
+count of profiles are O((log D_lambda)/d) by (eq:dim-large), and
+hle N^{1/16}, m,nasympsqrt N, eps<eta/2. This is
(eq:weighted-overlap).
@@ -698,45 +685,45 @@ $hle N^{1/16}$, $m,nasympsqrt N$, $eps<eta/2$. This is
part{Schatten interpolation}
%=========================================================================
-# A $p$-moment bilinear estimate
+# A p-moment bilinear estimate
The row part and the column part of the sweep multiply (in the scan order)
-to give $K_d$. Each part, inside a row or a column, is an independent
-smaller sweep. Let $mathcal B(M,M')$calB(M,M')$ on $V_lambda$ be the product of the
-two subgroup matrix actions, using arbitrary matrices $M_mu$, $M'_nu$ on
+to give K_d. Each part, inside a row or a column, is an independent
+smaller sweep. Let mathcal B(M,M')calB(M,M') on V_lambda be the product of the
+two subgroup matrix actions, using arbitrary matrices M_mu, M'_nu on
their irreducibles.
-Under (eq:not-sparse), for $2le p<∞$,
+Under (eq:not-sparse), for 2le p<∞,
W_lambda|mathcal B(M,M')calB(M,M')|_p^p
le e^{O((log D_lambda)/d)}
Big(sum_mu W_mu|M_mu|_p^pBig)Big(sum_nu W_nu|M'_nu|_p^pBig),
-with the constant in the exponent independent of $p$.
+with the constant in the exponent independent of p.
Proof.
-For a single pair of types, the squared $2$-norm is a trace of a product of
+For a single pair of types, the squared 2-norm is a trace of a product of
positive matrix actions; diagonalising and using (eq:weighted-overlap)
gives
-$W_lambda|mathcal B(M,M')calB(M,M')|_2^2le e^{E}(sum_mu W_mu|M_mu|_2^2)
-(sum_nu W_nu|M'_nu|_2^2)$ with $E=O((log D_lambda)/d)$. Summing over
+W_lambda|mathcal B(M,M')calB(M,M')|_2^2le e^{E}(sum_mu W_mu|M_mu|_2^2)
+(sum_nu W_nu|M'_nu|_2^2) with E=O((log D_lambda)/d). Summing over
type tuples with triangle and Cauchy--Schwarz absorbs the log counts
-(which are $O(N^{3/4}log N)$, covered by (eq:dim-large)) into $E$.
-Also $|mathcal B(M,M')calB(M,M')|_oplemax_mu|M_mu|_opmax_nu|M'_nu|_op$
+(which are O(N^{3/4}log N), covered by (eq:dim-large)) into E.
+Also |mathcal B(M,M')calB(M,M')|_oplemax_mu|M_mu|_opmax_nu|M'_nu|_op
by unitary restriction.
-Now interpolate. Let the bilinear map $Phi$ carry $(M,M')$ to
-$mathcal B(M,M')$calB(M,M')$ with output weighted trace-norm. It has norm $le e^{E/2}$
-at the $2$-Schatten endpoint and $le1$ at the operator-norm endpoint.
-Normalise inputs to $p$-norm $1$; test the output against a dual-norm-one
-matrix. On the strip with value at $z=2/p$, extend the inputs blockwise by
-polar factors with exponent $pz/2$ on absolute values (zero singular values
-kept zero) and the test matrix with exponent $p'(1-z/2)$,
-$p'=p/(p-1)$. Boundary norms are $le1$; the three-lines inequality gives
-factor $e^{(E/2)theta}=e^{E/p}$ at $theta=2/p$. Raising to the $p$-th
+Now interpolate. Let the bilinear map Phi carry (M,M') to
+mathcal B(M,M')calB(M,M') with output weighted trace-norm. It has norm le e^{E/2}
+at the 2-Schatten endpoint and le1 at the operator-norm endpoint.
+Normalise inputs to p-norm 1; test the output against a dual-norm-one
+matrix. On the strip with value at z=2/p, extend the inputs blockwise by
+polar factors with exponent pz/2 on absolute values (zero singular values
+kept zero) and the test matrix with exponent p'(1-z/2),
+p'=p/(p-1). Boundary norms are le1; the three-lines inequality gives
+factor e^{(E/2)theta}=e^{E/p} at theta=2/p. Raising to the p-th
power gives (eq:interp), and the exponent coefficient does not grow
-with $p$.
+with p.
%=========================================================================
@@ -746,70 +733,70 @@ part{The sparse shapes}
# Representations whose first row is almost the whole diagram
-When $k=N-lambda_1$ is small, the general machinery is overkill; a direct
+When k=N-lambda_1 is small, the general machinery is overkill; a direct
combinatorial estimate is better. This is the range that seeds the
induction.
-For $k=N-lambda_1ge1$,
+For k=N-lambda_1ge1,
|K_d(lambda)|_op le (Cd)^k,(k/N)^{k/8}
-for an absolute $C$.
+for an absolute C.
Proof.
-Work on ordered injective $k$-tuples of positions $xmapsto y$. Let $K$ be
-the sweep transition kernel. On functions of $k$-tuples that sum to zero
-over any one coordinate (all others fixed), $K$ acts; this subspace contains
-$V_lambda$ because $V_lambda$ occurs on $k$-tuples (invariants upon
-restriction to $G_{N-k}$, branching T1) but not on $(k-1)$-tuples.
+Work on ordered injective k-tuples of positions xmapsto y. Let K be
+the sweep transition kernel. On functions of k-tuples that sum to zero
+over any one coordinate (all others fixed), K acts; this subspace contains
+V_lambda because V_lambda occurs on k-tuples (invariants upon
+restriction to G_{N-k}, branching T1) but not on (k-1)-tuples.
smallskipnoindentThe pair-factor formula.
A sweep sends each card along a path; the path of a card is fixed by its
start and end, since the successive end coordinates replace the start ones.
-For two cards, let $ell$ be the last coordinate where they differ at the
-start and $r$ the first coordinate where they differ at the end. Give the
-pair weight $w=0$ if $r>ell$, $w=2$ if $r=ell$, $w=1$ otherwise. Then
-$K(x,y)=N^{-k}prod_{pairs}w$. (Paths do not collide iff
-$rleell$ for all pairs; a switch used by two paths rather than one
-contributes the factor $2$ exactly when a pair has $r=ell$.) This works for
+For two cards, let ell be the last coordinate where they differ at the
+start and r the first coordinate where they differ at the end. Give the
+pair weight w=0 if r>ell, w=2 if r=ell, w=1 otherwise. Then
+K(x,y)=N^{-k}prod_{pairs}w. (Paths do not collide iff
+rleell for all pairs; a switch used by two paths rather than one
+contributes the factor 2 exactly when a pair has r=ell.) This works for
any subset of cards.
smallskipnoindentCancelled kernel.
Because the zero-sum subspace forces all proper-coordinate marginals to
-vanish, we may replace $K$ by the fully cancelled
+vanish, we may replace K by the fully cancelled
[
D(x,y)=N^{-k}sum_{B⊆[k]}(-1)^{k-|B|}prod_{pairs in B}w .
]
-This vanishes unless the contact graph (pairs with $wne1$) has no isolated
-vertex, and its absolute column sums are $le2^k$ (each subset term in
+This vanishes unless the contact graph (pairs with wne1) has no isolated
+vertex, and its absolute column sums are le2^k (each subset term in
absolute value is the nonnegative doubly stochastic sweep kernel).
smallskipnoindentInclusion of occupied sets.
-In $K^*K$ we sample $x$ from the row $z$ of $K^*$ (a reverse scan). The
-occupied set $S$ of $x$ satisfies, for every fixed $F$,
+In K^*K we sample x from the row z of K^* (a reverse scan). The
+occupied set S of x satisfies, for every fixed F,
Pr(S⊇ F)le(k/N)^{|F|}.
This is the upper product-of-marginals property: true at the reverse scan
start, and preserved by a random switch (test one switched site, average
the two bounds; test both, and the product of marginals can only grow under
-averaging). The final marginals are $k/N$ (one position is uniform after
+averaging). The final marginals are k/N (one position is uniform after
all coordinates).
smallskipnoindentA spanning forest.
-A no-isolated-vertex graph on $S$ contains a spanning forest with $cle k/2$
-rooted trees of size $ge2$. There are $le C_0^k$ forest shapes, choose
-roots in $binom Nc$ ways and path types in $2^k$ ways. Conditioned on the
+A no-isolated-vertex graph on S contains a spanning forest with cle k/2
+rooted trees of size ge2. There are le C_0^k forest shapes, choose
+roots in binom Nc ways and path types in 2^k ways. Conditioned on the
common routing, expose children after parents: a common-routing child has
at most two possible start positions per meeting switch, and an
independent-path child summed over fresh positions meets a given parent at
-stage $i$ with expectation $le2^i2^{-(i-1)}$. Each embedding uses $k$ sites,
-so multiply by $(k/N)^k$ via (eq:inclusion). Summing gives, for the
-signed kernel $K^*D$, absolute row sum $le(C_1d)^k(k/N)^{k/2}$ using
-$binom Ncle(C_2N/k)^{k/2}$ for $cle k/2$. The $ell^2$-operator (Schur)
-bound on this subspace bounds $K^*K$ there, proving (eq:sparse).
+stage i with expectation le2^i2^{-(i-1)}. Each embedding uses k sites,
+so multiply by (k/N)^k via (eq:inclusion). Summing gives, for the
+signed kernel K^*D, absolute row sum le(C_1d)^k(k/N)^{k/2} using
+binom Ncle(C_2N/k)^{k/2} for cle k/2. The ell^2-operator (Schur)
+bound on this subspace bounds K^*K there, proving (eq:sparse).
%=========================================================================
@@ -819,59 +806,59 @@ part{The induction that proves the main moment bound}
# Closing the induction
Proof. [Proof of Theorem~thm:main]
-All $K_d(lambda)$ are contractions. Partitions of length $>N/2$ are killed
+All K_d(lambda) are contractions. Partitions of length >N/2 are killed
by one matching layer; the trivial one satisfies (eq:main-bound) at any
exponent.
-smallskipnoindentSparse range. For $1le kle N^{1-eps}$,
-(eq:sparse) with $W_lambdale D_lambdale N^k$ gives, for all large
-$d$ and any sufficiently large absolute exponent $p$,
+smallskipnoindentSparse range. For 1le kle N^{1-eps},
+(eq:sparse) with W_lambdale D_lambdale N^k gives, for all large
+d and any sufficiently large absolute exponent p,
[
W_lambda|K_d(lambda)|_p^p
le N^kcdot N^{k},N^{-eps k p/8}cdot(log-factor)^kle1 .
]
smallskipnoindentThe recursive step. Suppose (eq:main-bound)
-holds at the two smaller bit sizes $d_1,d_2lelceil d/2rceil$ with their
-exponents. Apply (eq:interp) at $p=max(p_{d_1},p_{d_2})ge2$, feeding
+holds at the two smaller bit sizes d_1,d_2lelceil d/2rceil with their
+exponents. Apply (eq:interp) at p=max(p_{d_1},p_{d_2})ge2, feeding
in the two subgroup sweep parts. Each input on a tuple is a tensor product of
-smaller sweeps, so each weighted $p$-th power term of the inputs is $le1$
+smaller sweeps, so each weighted p-th power term of the inputs is le1
by the inductive hypothesis, and the sums over type tuples use only the
count bounds. Thus
[
W_lambda|K_d(lambda)|_p^pleexp{C(log D_lambda)/d}
]
-with $C$ absolute. Since $W_lambdage D_lambda^{3/4}$,
+with C absolute. Since W_lambdage D_lambda^{3/4},
[
|K_d(lambda)|_p^p le D_lambda^{-3/4}e^{C(log D_lambda)/d}
le D_lambda^{-1/2}
]
-for large $d$ (so $C/dle1/4$), which gives $|K|_op^ple|K|_p^ple D_lambda^{-1/2}$.
+for large d (so C/dle1/4), which gives |K|_op^ple|K|_p^ple D_lambda^{-1/2}.
-Push the exponent by a small factor $1+theta$. Interpolation of Schatten norms
-gives $|K|_{p(1+theta)}^{p(1+theta)}le|K|_op^{theta p}|K|_p^p$ for
-$thetage0$. Write $E=C(log D_lambda)/d$, so that $W_lambda|K|_p^ple e^{E}$
-and $|K|_op^{theta p}le(D_lambda^{-3/4}e^{E})^{theta}$ (using
-$W_lambdage D_lambda^{3/4}$). Then
+Push the exponent by a small factor 1+theta. Interpolation of Schatten norms
+gives |K|_{p(1+theta)}^{p(1+theta)}le|K|_op^{theta p}|K|_p^p for
+thetage0. Write E=C(log D_lambda)/d, so that W_lambda|K|_p^ple e^{E}
+and |K|_op^{theta p}le(D_lambda^{-3/4}e^{E})^{theta} (using
+W_lambdage D_lambda^{3/4}). Then
[
W_lambda|K|_{p(1+theta)}^{p(1+theta)}
le D_lambda^{-3theta/4},e^{E(1+theta)}le1
]
-once $thetage C'/d$ with an absolute $C'$ (take $C'=2C$). Take
-$p_d=p(1+C'/d)$; then (eq:main-bound) holds at $p_d$.
+once thetage C'/d with an absolute C' (take C'=2C). Take
+p_d=p(1+C'/d); then (eq:main-bound) holds at p_d.
-smallskipnoindentBase case. For each fixed small $d$, a nontrivial
+smallskipnoindentBase case. For each fixed small d, a nontrivial
sweep matrix is a product of orthogonal projections that together generate
-$S_N$, so its operator norm is strictly below $1$ on every nontrivial
-$V_lambda$ (equality would need a common invariant vector for all matching
-switches, whose generated group is all of $S_N$). Hence a finite absolute
-base exponent $p_0$ exists covering the finitely many $dle d_0$, chosen also
+S_N, so its operator norm is strictly below 1 on every nontrivial
+V_lambda (equality would need a common invariant vector for all matching
+switches, whose generated group is all of S_N). Hence a finite absolute
+base exponent p_0 exists covering the finitely many dle d_0, chosen also
large enough for the sparse range.
smallskipnoindentBounded exponent. The recurrence multiplies the
-two child exponents by $1+C'/d$ and then takes a maximum. Along repeated
-halvings $dmapstolceil d/2rceil$ the sum of $1/d$ is a convergent
-geometric series, so $p_dle p_*<∞$ with $p_*$ absolute. This proves
+two child exponents by 1+C'/d and then takes a maximum. Along repeated
+halvings dmapstolceil d/2rceil the sum of 1/d is a convergent
+geometric series, so p_dle p_*<∞ with p_* absolute. This proves
(eq:main-bound), hence Theorem~thm:main.
@@ -881,32 +868,32 @@ part{From the moment bound to mixing}
# Plancherel and Cauchy--Schwarz
-Let $pi$ be the uniform permutation distribution, and let $Pr_j$ be the law
-of $j$ independent forward sweeps. Finite-group Plancherel and
+Let pi be the uniform permutation distribution, and let Pr_j be the law
+of j independent forward sweeps. Finite-group Plancherel and
Cauchy--Schwarz (Diaconis--Shahshahani 1981, Sections 2--3) give
4,|Pr_j-pi|_{TV}^2 le sum_{lambdane(N)} D_lambda|K_d(lambda)^j|_{HS}^2 .
-We bound $|K_d(lambda)^j|_{HS}^2le D_lambda|K_d(lambda)|_op^{2j}$.
-By Theorem~thm:main and $W_lambdage D_lambda^{3/4}$,
-$|K_d(lambda)|_ople D_lambda^{-3/(4p_*)}$. Hence
+We bound |K_d(lambda)^j|_{HS}^2le D_lambda|K_d(lambda)|_op^{2j}.
+By Theorem~thm:main and W_lambdage D_lambda^{3/4},
+|K_d(lambda)|_ople D_lambda^{-3/(4p_*)}. Hence
[
D_lambda|K_d(lambda)^j|_{HS}^2 le D_lambda^2,D_lambda^{-3j/(2p_*)}.
]
-Taking $j=8p_*/3$ (an absolute number of sweeps) gives
-$D_lambda^2D_lambda^{-4}=D_lambda^{-2}$. So
+Taking j=8p_*/3 (an absolute number of sweeps) gives
+D_lambda^2D_lambda^{-4}=D_lambda^{-2}. So
[
4|Pr_j-pi|_{TV}^2 le sum_{substack{lambdane(N) lambda^{rm tr}_1le N/2}} D_lambda^{-2}.
]
-This sum tends to $0$ as $dto∞$: for $k>N^{1-eps}$ it is bounded by
-(eq:dim-large) and the partition count; for $1le kle N^{1-eps}$,
-$D_lambdage e^{-1}(N/k)^k$ (top-row hook estimate as in Lemma~lem:dim)
-and there are at most $2^k$ such diagrams. Since the product law determines
+This sum tends to 0 as dto∞: for k>N^{1-eps} it is bounded by
+(eq:dim-large) and the partition count; for 1le kle N^{1-eps},
+D_lambdage e^{-1}(N/k)^k (top-row hook estimate as in Lemma~lem:dim)
+and there are at most 2^k such diagrams. Since the product law determines
the deck from any fixed starting deck, this is a worst-case bound. Thus an
-absolute number $j$ of sweeps gives TV distance $le1/4$ uniformly in $d$
-(large $d$; the finitely many small $d$ converge by the strict Fourier gap
+absolute number j of sweeps gives TV distance le1/4 uniformly in d
+(large d; the finitely many small d converge by the strict Fourier gap
and only increase the absolute sweep count, and convolution cannot increase
-TV). One sweep is $d$ physical shuffles, so $t_{rm mix}(d)le Cd$. This is
+TV). One sweep is d physical shuffles, so t_{rm mix}(d)le Cd. This is
the upper bound of Corollary~cor:mix.
%=========================================================================
@@ -916,25 +903,25 @@ part{The matching lower bound}
# Counting reachable permutations
[Support obstruction]
-Let $q_d$ be one physical shuffle. For every integer $tge0$,
+Let q_d be one physical shuffle. For every integer tge0,
[
|q_d^{*t}-U_{S_N}|_{TV} ge 1-frac{2^{tN/2}}{N!}.
]
-Thus TV distance $le1/4$ needs at least
-$lceil(2/N)log_2(3N!/4)rceil=2d-O(1)$ physical shuffles.
+Thus TV distance le1/4 needs at least
+lceil(2/N)log_2(3N!/4)rceil=2d-O(1) physical shuffles.
Proof.
-One physical shuffle uses $N/2$ independent fair bits (one per pair), so
-$t$ shuffles use $tN/2$ fair bits and can produce at most $2^{tN/2}$
+One physical shuffle uses N/2 independent fair bits (one per pair), so
+t shuffles use tN/2 fair bits and can produce at most 2^{tN/2}
permutations. Testing against the uniform measure (which weighs every
permutation and every non-reachable point in the complement),
-$|q_d^{*t}-U_{S_N}|_{TV}ge1-2^{tN/2}/N!$. The threshold
-$2^{tN/2}/N!le3/4$ rearranges to the stated lower bound; Stirling gives the
-$2d-O(1)$ form.
+|q_d^{*t}-U_{S_N}|_{TV}ge1-2^{tN/2}/N!. The threshold
+2^{tN/2}/N!le3/4 rearranges to the stated lower bound; Stirling gives the
+2d-O(1) form.
This is the lower bound of Corollary~cor:mix. Combined with the upper
-bound, $t_{rm mix}(d)=Θ(d)=Θ(log N)$.
+bound, t_{rm mix}(d)=Θ(d)=Θ(log N).
%=========================================================================
{99}
@@ -944,7 +931,7 @@ applications to the game of Faro, J. Amer. Statist. Assoc. 68 (1973),
bibitem[Morris(2008)]{Morris2008} B.~Morris, The mixing time of the Thorp
shuffle, SIAM J. Comput. 38 (2008), 484--504.
bibitem[Morris(2009)]{Morris2009} B.~Morris, Improved mixing time bounds for
-the Thorp shuffle and the $L$-reversal chain, Ann. Probab. 37 (2009),
+the Thorp shuffle and the L-reversal chain, Ann. Probab. 37 (2009),
453--477.
bibitem[Morris(2013)]{Morris2013} B.~Morris, Improved mixing time bounds for
the Thorp shuffle, Combin. Probab. Comput. 22 (2013), 118--132.