How many times must a deck be shuffled before its order is random? For one
widely studied shuffle the answer turns out to be linear in the number of
bit positions of the deck size, which is to say logarithmic in the size of
the deck. The proof establishes this by exposing card trajectories one
at a time and tracking the residual bijection through every exposed layer.
Thorp's shuffle, in its physical form, is this. Split a deck of n = 2^d
cards into two equal halves. Pair corresponding cards of the two halves.
Flip an independent fair coin for each pair and put the two cards of the
pair in the order prescribed by that coin. Interleave the pairs to produce
a new deck. Do it again.
pdf/thorp-1973.pdf
Thorp wrote about nonrandom shuffling in connection with the game of Faro.
Thorp's paper opens with this observation.
"Human shuffling is nonrandom and a simple model for it indicates
that, in principle, the player can achieve significant positive
expectation. The ideas used to apply nonrandom shuffling to Faro
also extend to other games."
pdf/thorp-1973.pdf
The rate at which nonrandomness is forgotten is the mixing time of the
shuffle.
Label positions by binary strings x = (x_1, ..., x_d) in F_2^d. Undo the
deterministic rotation
R(x_1, ..., x_d) = (x_2, ..., x_d, x_1)
that is part of every physical step. The t-th switch layer then acts only
in coordinate i_t = 1 + ((t - 1) mod d). On each two-element line at that
coordinate, an independent fair coin either fixes both cards or swaps them.
After d consecutive physical steps every coordinate has been used once;
call such a block a sweep. A sweep costs d physical shuffles.
pdf/morris-2008.pdf
Let q_d be the law of one physical shuffle, a random permutation of the n
positions. Let U_n be the uniform law on the symmetric group S_n. For
probability measures mu and nu on S_n,
||mu - nu||_TV = (1/2) sum_{pi in S_n} |mu(pi) - nu(pi)|,
and the mixing time is
t_mix(d) = inf { t in Z_{>=0} : ||q_d^{*t} - U_n||_TV <= 1/4 }.
A fixed initial deck, applied on the left, translates q_d^{*t} by a fixed
permutation and leaves the distance to uniform unchanged. So t_mix(d)
does not depend on which deterministic deck the process starts from.
pdf/morris-2008.pdf
The new result. There is an absolute integer w >= 1 such that, uniformly
over every starting configuration,
||q_d^{*w d} - U_n||_TV -> 0 as d -> infinity.
Conversely the number of fair coin tosses gives a lower bound of the same
order. After t physical shuffles at most 2^{t n / 2} coin strings occur
and hence at most that many permutations, so
||q_d^{*t} - U_n||_TV >= 1 - 2^{t n / 2} / n!.
Setting the right side to at most 1/4 gives t >= (2/n) log_2(3 n! / 4), and
Stirling's formula makes the right side 2d - O(1). Thus
t_mix(d) = Theta(d) = Theta(log n).
The order is optimal.
pdf/morris-2008.pdf
Earlier bounds. A brief timeline of pre-existing results.
Morris gave the first polynomial upper bound, O(d^{44}) physical shuffles
for n = 2^d.
pdf/morris-2008.pdf
Morris's survey with the relevant Markov chain theory, written jointly with
Montenegro, improved this to O(d^{29}).
pdf/montenegro-tetali-2006.pdf
Morris obtained O((log N)^4) physical shuffles for every even deck size N,
then O(d^3) for power-of-two decks.
pdf/morris-2009.pdf
pdf/morris-2013.pdf
Czumaj and Vocking, using non-Markovian coupling and the analogy with
butterflies, proved that for dyadic decks and any fixed eps with
0 < eps < 1, a fraction 1 - eps of labeled cards is uniformly permuted to
within total variation eps after O(d^2) physical shuffles. Equivalently,
O(d) complete coordinate sweeps. Their result concerns the joint law of
selected card positions. The conditional framework concerns the
entire residual bijection, before collapsing to card marginals.
pdf/czumaj-2015.pdf
Line of attack. Three ingredients combine.
Conditional moment estimates on a product grid of coordinate lines. Expose
a family of card trajectories. The conditional average of the residual
bijection is a random operator. A Schatten 2q-moment of that operator in
each irreducible representation is controlled by the dimension of that
representation, plus an exact cost of exposing trajectories on the lines
visited. The cost is the falling-factorial ratio of sampling without
replacement.
Signed tensor densities. For irreducible types in a (p,p)-hook, Schur-Weyl
duality plus the hook theory of Berele and Regev yields a mixture of
tensor powers of positive trace-one operators that dominates the isotypic
projection. See A. Berele and A. Regev, Hook Young diagrams, combinatorics
and representations of Lie superalgebras, Bull. Amer. Math. Soc. (N.S.) 8
(1983), 337-339.
pdf/berele-regev-1983.pdf
Analytic transfer. The unconditioned sweep operator is a matrix polynomial
in a real parameter z, from the line law (1 - z) U_m + z B_m. On a short
real segment the conditional bound gives a saving proportional to the
dimension. On a complex disk of radius strictly greater than one the
operator has norm at most one. The subharmonic maximum principle on the
punctured disk carries the segment saving to z = 1.
pdf/demailly-2012-complex-analytic-differential-geometry.pdf
Fourier comparison. The passage from operator norm to total variation
follows Diaconis and Shahshahani, Generating a random permutation with
random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), 159-179.
pdf/diaconis-shahshahani-1981.pdf
Earlier analyses of this shuffle track the residual information through
the shapes of exposed card trajectories. Morris, Rogaway and Stegers
analyze selected-card Thorp marginals by averaged conditional one-card
bounds combined with a coupling along the evolution (CRYPTO 2009, Lecture
Notes in Computer Science 5677, 286-302). Hoang, Morris and Rogaway,
studying the swap-or-not construction, use a related conditional
squared-discrepancy calculation (CRYPTO 2012, Lecture Notes in Computer
Science 7417, 1-13).
pdf/mrs-2009-thorp-encipher.pdf
pdf/hoang-morris-rogaway-2012-enciphering-scheme-based-on-a-card-shuffle.pdf
The analytic core differs from all of these. A
Schatten moment is taken of the full residual bijection on each coordinate
line, and the dimension saving is carried all the way to z = 1 by a
barrier argument rather than tracked card-by-card.
Permutations and measures on groups. A permutation acts on positions from
the right: a product pi sigma applies sigma first, then pi. The convolution
of probability measures on S_l is then the law of the composition, and its
Fourier transform is multiplicative:
hat(mu * nu)(lambda) = hat(mu)(lambda) hat(nu)(lambda),
hat(mu)(lambda) = sum_{pi in S_l} mu(pi) rho_lambda(pi),
for any finite-dimensional unitary representation rho_lambda. All matrix
norms in the sequel are the unnormalized Schatten norms
||A||_p^p = Tr |A|^p, |A| = (A^* A)^{1/2}.
Random bijections between two slot sets of equal size become random
permutations after identifying each set with a fixed reference set. A change
of identification multiplies the average in an irreducible by unitaries on
the left and on the right, and leaves singular values unchanged. At
successive layers the two free slot sets at that stage may differ, so the
identification is chosen layer by layer without harm to any operator norm
to be estimated.
Irreducible types. All representations are over the complex numbers. For a
partition lambda |- l, denote by [lambda] the irreducible representation of
S_l, by D_lambda its dimension, and by F(lambda) = log D_lambda. The empty
diagram, at l = 0, has dimension one. All logarithms in the argument are
natural.
Classical linear algebra of symmetric groups. The dimension D_lambda is the
number of standard Young tableaux of shape lambda, given by the
hook-length formula. Conjugating the diagram, written lambda', twists
[lambda] by sign. On restriction to S_{l - j} the multiplicity of [sigma]
is the number of standard tableaux of the skew shape lambda / sigma when
sigma lies inside lambda, and is zero otherwise. Standard sources for all
of this: R. Stanley, Enumerative Combinatorics Volume 2, Cambridge
University Press (1999); B. Sagan, The Symmetric Group, 2nd edition,
Graduate Texts in Mathematics 203, Springer (2001); A. Vershik and A.
Okounkov, A new approach to the representation theory of the symmetric
groups II, J. Math. Sci. 131 (2005), 5471-5494, in particular Theorem 5.8
and Corollary 7.1.
pdf/stanley-1999.pdf
pdf/vershik-okounkov-2005.pdf
For the placement of j distinguishable cards into l slots in particular,
the representation on placement functions contains [lambda] exactly when
lambda_1 >= l - j, and the sign twist of that representation contains
[lambda] exactly when lambda'_1 >= l - j.
Pieri's rule. Inducing from S_a x S_{l - a} with a trivial character on S_a
adds a horizontal strip to the Young diagram. Inducing with a sign character
adds a vertical strip. See Sagan (2001), Chapter 2, or Stanley (1999),
Chapter 7.
Schur-Weyl duality. For integers p >= 1 and t >= 0, write (C^p)^{tensor t}
for the t-th tensor power. The S_t-types appearing are precisely the
partitions sigma |- t with at most p rows, and each multiplicity space
carries an irreducible polynomial representation of GL_p of highest weight
sigma. A signed variant of this decomposition is applied separately on the
even-factor and odd-factor tensor factors of a signed action.
Dimension bounds. The induction splits irreducible types into those
close to a row or a column and those with exponentially large dimension.
For large l, put
k = min(l - lambda_1, l - lambda'_1).
If 0 < k <= l/3, then
D_lambda >= e^{-1} C(l, k). (2.1)
Indeed, after transposing if necessary, the first row has length l - k. Let
mu be the diagram of k boxes below it. The hook-length formula gives
D_lambda = C(l, k) D_mu
prod_{j = 1}^{l - k} (1 + mu'_j / (l - k - j + 1))^{-1}.
Only j <= k can contribute a nontrivial factor. Since sum_j mu'_j = k, the
product is at least exp(-k / (l - 2k)) >= e^{-1}, proving (2.1).
If k > l/3, then
F(lambda) >= c_dim l (2.2)
for an absolute c_dim > 0 and all large l. If both the first row and the
first column have length below l/8, every hook is shorter than l/4, and
the hook-length formula with Stirling's bound gives this conclusion
directly. Otherwise transpose if needed so that the first row has length v
in [l/8, 2l/3]. Retain that row and a subdiagram of floor(v/4) boxes below
it. The preceding large-row estimate makes the dimension of the retained
shape exponential in v, and hence in l. Branching shows that D_lambda is at
least that dimension.
Reducing c_dim if necessary, the two estimates imply F(lambda) >= c_dim k
for every k. Conversely the placement criterion, with a sign twist if
necessary, places [lambda] inside a representation of dimension
(l)_k <= l^k, so F(lambda) <= k log l. Together,
c_dim k <= F(lambda) <= k log l (2.3)
for large l. The last bound of (2.3) is what admits the sparse-range split.
The lower bound (2.1) controls the sum over representations in the final
Fourier comparison.
Coordinate grids. Fix a power of two R >= 2 large enough. Let
Omega = Omega_1 x ... x Omega_b be an ordered product grid with b >= 1
coordinates. Each m_j = |Omega_j| is a power of two in [R, R^2], and
s = |Omega| = prod_j m_j. Each Omega_j is identified with
{0, 1}^{log_2 m_j}. A sweep first permutes every line parallel to
coordinate 1, then every line parallel to coordinate 2, and so on,
independently on every line. A line belongs to its stage of the sweep.
Line laws. On a line of size m use
L_m(z) = (1 - z) U_m + z B_m, (3.1)
where U_m is uniform on S_m and B_m is the binary sweep on log_2 m
bits. Both laws send every individual slot uniformly to some slot. Both
also have expected sign zero: for B_m, toggling one of its independent
fair switches reverses the sign of the permutation while leaving the
uniform average over switches unchanged.
Until the analytic transfer, z is real, nonnegative, and small. Set
A_R = max_m max_{g in S_m} m! B_m(g),
z_cmp(R) = min { 1/2, 1 / (A_R + 1) },
where m ranges over the allowed line sizes. Finitely many sizes make
z_cmp(R) > 0. For 0 <= z <= z_cmp(R),
(1/2) U_m <= L_m(z) <= 2 U_m (3.2)
as measures.
Paths from endpoints. If a card starts at u = (u_1, ..., u_b) and ends
at v = (v_1, ..., v_b), its slot after stage j must be
(v_1, ..., v_j, u_{j+1}, ..., u_b), 0 <= j <= b.
Every intermediate slot is therefore determined by the two endpoints.
A typical instance for b = 2 lies in the two-coordinate grid
{0, 1} x {0, 1}: a path from (i, j) to (i', j') passes through the
forced junction slot (i', j), where the coordinate-1 line through i has
already moved it to row i' but the row it ends in has not yet acted.
Prescribe a family H of h such paths. Require the slots to be distinct
at every layer, including input and output. Call the occupied slots
holes. For a stage line L of size m, let h_L count the prescribed paths
that use L, and let E_L(H) be the event that the line permutation
realizes their assignments from input to output.
Layer disjointness makes the two assignments on a line injective, and
(3.2) makes E_L(H) have positive probability. The conditioning event is
the intersection of E_L(H) over all stage lines. Since the lines are
independent, the residual line laws are L_m(z) conditioned on their
prescribed assignments, and the resulting laws remain independent. Each acts as a
random bijection between the unoccupied input slots and the unoccupied
output slots of its line.
Put M = s - h. After the paths in H are removed, the sweep gives a
random bijection between the M remaining input slots and the M
remaining output slots. For lambda |- M, let K_lambda^H be its average
in [lambda], using any fixed identification of the two slot sets.
Line cost. For an integer 0 <= u <= m define
phi_m(u) = log ( m^u / (m)_u ),
(m)_u = m (m - 1) ... (m - u + 1), (m)_0 = 1.
Set
C(H) = sum over stage lines L of phi_{|L|}(h_L).
The summands of phi_m(u) = sum_{r = 0}^{u - 1} log(m / (m - r)) are
nonnegative and increasing. For u >= 1 the mean over the first u terms
is at most the mean over all m terms, which is at most 1 because
m! >= (m/e)^m. So 0 <= phi_m(u) <= u, and hence
0 <= C(H) <= b h,
since the h_L sum to h at every stage.
Placements. For a nonnegative integer t, a placement of t
distinguishable cards into the available slots is an injection from
[t] = {1, ..., t} into those slots; for t = 0 there is exactly one
empty placement. Let x and y be placements into the remaining input and
output slots, and write p_H(x, y) for the conditional transition
probability from x to y. When this probability is positive the pair of
endpoints determines additional paths which together with H form a
disjoint family H+ of size h + t. Let v_L count the added paths on line
L, so h_L + v_L <= |L|.
Consider two coordinates, with positions (i, j). A solid prescribed
path from (i, j) to (i', j') and a dashed added path from (i'', j'')
to (i''', j''') can share a first-stage line but must still occupy
distinct slots at every layer: at the junction the solid path sits at
(i', j) and the dashed path sits at (i''', j''). On that shared line
h_L = 1 and v_L = 1, illustrating how a prescribed assignment reduces
the slots available to an added path.
On a line used by the added paths, with m = |L| and v = v_L > 0, the
conditioning comparison gives
L_m(z)(E_L(H+)) / L_m(z)(E_L(H)) <= 4 / (m - h_L)_v.
The uniform ratio is exactly (m - h_L)_v^{-1}, and (3.2) changes
numerator and denominator by factors between 1/2 and 2. The uniform
ratio also records the increment of the line cost:
1 / (m - h_L)_v = m^{-v} exp{ phi_m(h_L + v) - phi_m(h_L) }.
Unused lines contribute one. At most t b lines are used. Each added path
contributes prod_j m_j^{-1} = s^{-1}. Multiplying the line bounds,
p_H(x, y) <= s^{-t} exp{ C(H+) - C(H) + (log 4) t b }. (3.3)
The difference C(H+) - C(H) of the potentials in (3.3) is the part that
permits further paths to be revealed during the induction.
Schatten moment. For a positive integer q to be fixed, define
T_lambda^H = ||K_lambda^H||_{2q}^{2q}.
Theorem A (conditional sweep moment estimate). There exist a power of
two R >= 2, a positive integer q, and a real z_* > 0 such that every
grid and every family H of prescribed disjoint trajectories satisfies,
for every z in [0, z_*] and every lambda |- s - h,
log T_lambda^H <= -c(s) F(lambda) + e(s) h log s - C(H). (3.4)
For the moment to be defined, a zero 2q-norm gives log T = -infinity.
The parameters are
a = 1/100, c_0 = e_0 = a/100,
c(s) = c_0 + 1 / sqrt(log s),
e(s) = e_0 - 1 / sqrt(log s).
The empty diagram has dimension one. If h = s, the remaining bijection
is the unique empty bijection and the moment is one. The assertion also
covers the one-dimensional trivial representation for every h.
At H = empty, (3.4) reduces to
T_lambda^empty <= D_lambda^{-c(s)}. (3.5)
Equation (3.5) is used at small real z. For general H the
potential -C(H) is retained because (3.3) expresses the cost of
prescribing additional paths as a difference of potentials; the
induction over b uses that difference to
recover the original potential after summing over the added placements.
Sparse levels. The induction starts on types that first appear when
only a short list of cards is exposed, even after a comparable number
of trajectories had been prescribed. The row case uses an alternating
placement kernel; the column case uses the same representation
twisted by sign.
Lemma B (conditional sparse contraction). For every 0 < theta < 1 and
K_0 >= 1 there are rho > 0 and R_0 such that, for each power of two
R >= R_0, there is z_sp(R) > 0 with: every allowed grid and every
prescribed family H satisfies, for every integer k >= 1 and partition
lambda |- M = s - h with the property lambda_1 = M - k or
lambda'_1 = M - k, and with
h <= K_0 k, h + k <= s^{1 - theta}, (4.1)
the operator norm obeys, for every z in [0, z_sp(R)],
||K_lambda^H||_op <= s^{-rho k}. (4.2)
Proof of Lemma B. Set B_0 = ceil(8/theta). For b > B_0 the proof uses
only the line comparison (3.2). For b <= B_0 the argument first
establishes the estimate at z = 0, then extends to a common real
neighborhood by continuity after fixing R. Implicit constants in the
estimates are absolute; their absorption into powers of s
determines the required size of R in terms of theta and K_0.
Row case, alternating kernel. Assume lambda_1 = M - k. For input and
output k-placements x, y, and a subset A of [k], let p_A(x_A, y_A) be
the conditional probability that the labels of A follow the paths
specified by their input and output positions, with p_empty = 1.
Define a kernel from input placements to output placements by
Q(x, y) = s^{-k} sum_{A subset [k]} (-1)^{k - |A|}
s^{|A|} p_A(x_A, y_A). (4.3)
The A = [k] term is the full placement transition kernel. For a proper
subset A, the corresponding operator has range contained in the
pullbacks y -> f(y_A) of functions on |A|-placements. By the branching
rule, that subrepresentation
contains only types with first row at least M - |A| > M - k. Projection
to type lambda therefore kills every term with A proper. The full
placement representation contains [lambda], so the surviving block is
a copy of K_lambda^H. Consequently
||K_lambda^H||_op <= ||Q||_HS.
The scale s in (4.3) cancels the probability 1/s of a path whose stage
lines are untouched by any other constraint.
Crude entry bound. If the paths of A augment H to a disjoint family
H_A, then (3.3) with C(H_A) <= b(h + |A|) gives a crude estimate.
Invalid subsets contribute zero probability. Summing over A,
|s^k Q(x, y)| <= 2^k exp{ b h + (1 + log 4) b k }. (4.4)
Hilbert-Schmidt count. Extend Q by zero when the endpoint array fails
to be an injection into its available input or output slots. On
endpoint placements keep the alternating formula (4.3), even when the
full family of k paths collides at an intermediate layer. Choose all
input and output slots independently and uniformly from the full grid
Omega, with replacement. The zero extension gives the exact identity
||Q||_HS^2 = s^{-2k} sum_{x, y in Omega^k} |s^k Q(x, y)|^2
= E_full |s^k Q(x, y)|^2.
Every sampled pair of endpoints determines an auxiliary trajectory by
the layer formula. At any fixed layer its slot is uniform in Omega, and
the slots for different particles are independent. The counting
uses exactly this independence; the conditional shuffle probabilities
remain inside Q.
Two kinds of sharing are counted: a common slot at a layer, or a
common line at a stage. Suppose omega bounds the probability that one
independent particle shares with any fixed trajectory. Form the graph
whose vertices are particles and holes, with an edge for each sharing
involving a particle. For 0 <= w <= k, if at least w particles are
incident to edges, the graph contains a directed forest with at least
ceil(w/2) edges and distinct particle tails. In a component meeting
holes, point each particle to a neighbor one step closer to the nearest
hole: distances decrease, so the edges form a forest rooted at holes,
with every particle a tail. In a component containing only particles,
with v >= 2 incident vertices, a rooted spanning tree supplies at least
v - 1 >= v/2 particle tails.
For a fixed directed forest with j edges, condition on all paths except
a leaf particle. Its parent is now fixed, its sharing event has
probability at most omega, and it occurs at no other remaining edge.
Removing leaves one by one bounds the forest probability by omega^j.
There are at most C(k, j)(k + h)^j choices of tails and parents. Thus,
if r = (k + h)omega <= 1, the probability that at least w particles are
incident to sharing is at most
sum_{j = ceil(w/2)}^k C(k, j) r^j <= 2^k r^{w/2}. (4.5)
Many coordinates (b > B_0). Take sharing to mean a common stage line.
A particle uses a fixed line at stage j with probability m_j/s, so
omega <= b max_j m_j / s. Since max_j m_j <= s^{2/b},
(k + h) omega <= b s^{-theta + 2/b} <= s^{-theta / 2}
for sufficiently large R, uniformly in b > B_0. Because 2/b < theta/4 and
b <= s^{theta/4}, both following from s >= R^b after increasing R.
If a path shares no stage line with any other particle path or with a
hole, adding it to any subset multiplies that subset's transition
probability by 1/s. Its lines are independent of all other constraints,
and each contributes the uniform marginal for one slot. The statement
holds even when the subset has probability zero. The paired terms of
(4.3) therefore cancel. Thus Q != 0 requires every particle to be
incident to line sharing. Combining (4.4) and (4.5) with w = k,
P_full(Q != 0) <= 2^k s^{-theta k / 4},
||Q||_HS
<= 2^{3 k / 2} e^{b h + (1 + log 4) b k} s^{-theta k / 8}
<= s^{-theta k / 16}
for large R. The last step uses h <= K_0 k and b / log s <= 1 / log R.
Bounded number of coordinates (b <= B_0). A single line can hold a
substantial fraction of the grid, so multiple paths may share a line.
Work at z = 0 and use the fact that most paths still see only a small
fraction of each line prescribed. Put
xi = 1 / (10 B_0), eta = s^{-xi},
and increase R so that eta <= 1/2 for every s >= R.
For any endpoint arrays, let t_L be the number of the k auxiliary paths
that use line L, whether or not those paths are jointly feasible. Call
L light if h_L + t_L <= |L| eta. Call a particle good if every line on
its path is light and if it shares no slot at any layer with another
particle or a hole. Let G be the set of good particles.
Entry bound on good particles. First prove
|s^k Q| <= exp( O(b(k + h)) ) eta^{|G|/2}. (4.6)
It holds trivially on the zero extension outside endpoint placements;
consider an entry of the original placement matrix. For a subset A whose
paths are compatible with H at every layer, the uniform conditional line
law gives
s^{|A|} p_A(x_A, y_A)
= prod_L m^{v_L(A)} / (m - h_L)_{v_L(A)}, m = |L|,
where v_L(A) counts its paths on L. An invalid subset has probability
zero, and the product is not formed.
Because a good path shares no layer slot with any other path or a hole,
J union S is valid exactly when J is valid for every J subset of
[k] \ G and S subset of G. Group the alternating sum by J and discard
every invalid J before forming line factors. For a valid J, let r_L(J)
count its paths on L, and put
D_J = prod_{L non-light} m^{r_L(J)} / (m - h_L)_{r_L(J)}.
All these denominators are positive. The bound for phi_m gives
log D_J = sum_{L non-light}
( phi_{|L|}(h_L + r_L(J)) - phi_{|L|}(h_L) )
<= sum_L phi_{|L|}(h_L + r_L(J))
<= b(h + |J|). (4.7)
At each light line introduce W_L = m / Z_L, where the Z_L are
independent gamma variables with shape m - h_L + 1 and unit rate. The
elementary identity
E Z^{-v} = Gamma(alpha - v) / Gamma(alpha),
Z ~ Gamma(alpha, 1), 0 <= v < alpha,
follows by integrating the gamma density, and gives
E W_L^v = m^v / (m - h_L)_v for the exponents used in the alternation. Lightness
makes these moments finite. Writing L_j(i) for the stage-j line of a
good path i, alternation over the good paths gives the exact expression
s^k Q(x, y) =
sum_{J subset [k] \ G, J valid} (-1)^{k - |J| - |G|} D_J
* E[ prod_{L} W_L^{r_L(J)}
* prod_{i in G} ( prod_{j=1}^b W_{L_j(i)} - 1 ) ]. (4.8)
Every path using a light line uses the same variable W_L. All factors
are grouped by line before taking moments, because independence is
available between lines but not between particle factors.
For nonnegative u, v with u + v <= t_L, density tilting gives
E W_L^v |W_L - 1|^u
= ( m^{u+v} / (m - h_L)_{u+v} ) E |1 - Z'/m|^u
<= C_1^{u+v} eta^{u/2}, (4.9)
where Z' has gamma shape n = m - h_L + 1 - u - v and unit rate, and C_1
is an absolute constant. Lightness gives the margin
n >= m(1 - eta) + 1 > 0,
m^{u+v} / (m - h_L)_{u+v} <= (1 - eta)^{-(u+v)} <= 2^{u+v}.
For a gamma variable of shape n the centered moment generating function
is e^{-nt}(1 - t)^{-n}, whose logarithm is at most C n t^2 for
|t| <= 1/2. Chernoff's inequality gives
P(|Z' - n| > x) <= 2 exp(-c min{x^2/n, x}). Integrating this tail gives
(E |Z' - n|^u)^{1/u} <= C( sqrt(nu) + u ), u >= 1.
When u >= 1, u/m <= eta, n <= m + 1, and |1 - n/m| <= eta + 1/m <= 2eta,
because 1 <= u <= m eta. The triangle inequality then gives
(E |1 - Z'/m|^u)^{1/u}
<= |1 - n/m| + (C/m)( sqrt(nu) + u ) <= C' sqrt(eta),
which proves (4.9). The case u = 0 needs only the prefactor bound.
For each good path telescope in stage order:
prod_{j=1}^b W_{L_j(i)} - 1
= sum_{a=1}^b (W_{L_a(i)} - 1) prod_{j < a} W_{L_j(i)}.
In one expanded term, let u_L count the factors W_L - 1 and v_L count the
undifferenced factors W_L. Each good path supplies one difference, so
sum_L u_L = |G|. A tracked path supplies at most one factor at any line
at a given stage, so u_L + v_L <= t_L. Independence across lines and
(4.9) bound the expectation of that term in absolute value by
C_1^{b k} eta^{|G|/2}. There are at most b^{|G|} telescoping choices and
at most 2^{k - |G|} choices of valid J. Together with (4.7) these prove
(4.6).
Counting good particles. All probabilities in this count again refer to
the independent endpoint arrays sampled with replacement in the full
grid; the holes are fixed. The sparse hypothesis and xi <= theta/80 give,
for large R,
(b + 1)(k + h) / s <= s^{-theta/2},
2h/(s eta), 2k/(s eta) <= 2 s^{-(theta - xi)} <= s^{-theta/2}.
In particular these quantities are at most one.
If |G| < k/2, either at least k/4 particles share a layer slot with
another path, or at least k/4 particles use a non-light line. The first
event is bounded by (4.5) with omega = (b+1)/s. In the second, some stage
j has at least k/(4 B_0) particles on non-light lines. Each such line
satisfies h_L > m_j eta/2 or t_L > m_j eta/2, so one of these two classes
receives at least a_k = k/(8 B_0) particles.
At a fixed stage, the lines with h_L > m_j eta/2 are determined by the
holes and occupy a fraction at most 2h/(s eta) of the slots. The
independent-occupancy bound for at least a_k particles in this fixed set
is 2^k (2h/(s eta))^{a_k}. For the lines with t_L > m_j eta/2, their
number is at most r_j = floor(2k/(m_j eta)). If r_j = 0 there are none.
Otherwise fix a set of at most r_j lines first. A particle uses it with
probability at most r_j m_j / s <= 2k/(s eta), so its occupancy bound is
2^k (2k/(s eta))^{a_k}. Summing over the at most (s+1)^{r_j} possible
fixed sets and combining the three events,
P_full(|G| < k/2) <= 2^k ( (b+1)(k+h)/s )^{k/8}
+ b 2^k ( 2h/(s eta) )^{a_k}
+ 2^k sum_{1 <= j <= b, r_j >= 1}
(s+1)^{r_j} ( 2k/(s eta) )^{a_k}.
Thresholds may be nonintegral; taking ceilings only decreases these
powers of bases in [0, 1].
The cost of choosing the lines with t_L > m_j eta/2 is uniformly small.
Since b <= B_0 and R <= m_j <= R^2,
m_j >= s^{1/(2 B_0)}, m_j eta >= s^{2/(5 B_0)},
r_j log(s+1) / (k log s)
<= 2 s^{-2/(5 B_0)} log(s+1) / log s = o_R(1).
Before the factors 2^k and the stage sum and this set count, the vertex
term saves (theta/16) k log s and each non-light-line term saves
(theta/(16 B_0)) k log s. The displayed ratio tends to zero uniformly for
s >= R; the other two factors also cost o_R(k log s). Increasing R
therefore gives
P_full(|G| < k/2) <= s^{-nu k},
nu = theta / (100 B_0) > 0, (4.10)
uniformly over the grids with b <= B_0. On |G| >= k/2, (4.6) gives the
entry saving s^{-xi k/4}. On the complement use (4.4) and the square root
of (4.10) in the Hilbert-Schmidt expectation:
||Q||_HS <= exp( O(b(k + h)) )
( s^{-xi k/4} + s^{-nu k/2} ).
Column case. Suppose now lambda'_1 = M - k. The sign twist of the
k-placement representation contains [lambda]. Its entry for placements
x, y is the conditional average of sgn(g) 1_{g(x) = y}, with g the
residual bijection in fixed slot identifications. An entry whose full
path family is invalid is zero. Condition on all h + k paths.
On each line, list the assigned paths first, in the same order at input
and output, followed by the unassigned sites. Deleting the fixed
assignments leaves a residual bijection, and comparison with the original
slot orders contributes only a deterministic sign. Applying this to the
lines and composing the stages expresses the sign of the remaining
bijection as a fixed factor times the product of the residual line signs.
Conditioned lines are independent, so it suffices to find one line whose
residual sign has mean zero.
For b > B_0,
s / max_j m_j >= s^{1 - 2/b} > s^{1 - theta} >= h + k.
Every stage has more lines than paths, so it has a line untouched by all
h + k paths. Its residual law is L_m(z), which has expected sign zero.
For b <= B_0 at z = 0, fix any stage j. The number of unassigned sites
satisfies
s - h - k >= s(1 - s^{-theta}) > s/m_j
once R^{-theta} + R^{-1} < 1. There are s/m_j lines in that stage, so
one line has at least two unassigned sites. Its residual bijection under
the uniform conditional law is uniform between the unassigned site sets
and has expected sign zero. Thus every signed placement entry vanishes
in the relevant parameter range of each branch.
Assembling the constants. Set beta = min{xi/4, nu/2} > 0. For an absolute
C, the bounded-coordinate row estimate is at most
2 e^{C b (1 + K_0) k} s^{-beta k} <= s^{-beta k / 2}
for all sufficiently large R, since b / log s <= 1 / log R. The
corresponding column operator is zero at z = 0. The many-coordinate row
estimate is at most s^{-theta k / 16}, and its column operator is zero
whenever (3.2) holds. Choose
rho = min{ theta/32, beta/4 } > 0
before R, then choose R_0 large enough for all the preceding estimates.
For every R >= R_0 the bounded-coordinate bounds at z = 0 have strict
slack relative to s^{-rho k}.
Fix now a power of two R >= R_0. When b <= B_0 there are finitely many
allowed grids, with s <= R^{2 B_0}, and finitely many feasible path
families, integers k, and partitions. Each conditional operator is a
finite expression in line probabilities whose conditioning denominators
are positive at z = 0, hence is continuous there. Strict slack and
finiteness give delta(R) > 0 such that (4.2) holds for all these
bounded-coordinate operators when 0 <= z <= delta(R). Set
z_sp(R) = min{ delta(R), z_cmp(R) } > 0.
The many-coordinate proof applies throughout this interval by (3.2), so
it covers every b and completes the lemma.
Signed tensor densities. The remaining induction compares row and column
symmetry on a rectangle with holes. The comparison uses trace-one
positive operators that dominate the isotypic projections of hook
diagrams. The construction is a signed form of Schur-Weyl duality.
Setup. Let p in [1, s] be an integer and V = E + O with dim E = dim O = p.
On V^{tensor l} for l <= s, let S_l permute the factors with signs:
interchanging two neighboring odd factors (vectors in O) incurs a minus,
and all other neighboring interchanges do not. On parity-homogeneous
tensors the sign is the sign of the induced reordering of the odd
factors; this defines a unitary action. An even density is a positive
semidefinite operator on V of trace one that is block diagonal with
respect to E + O.
Lemma C (signed density domination). Let P_alpha be the isotypic
projection for alpha |- l in this signed tensor representation. The
types that occur are exactly those in the (p, p)-hook: every box lies in
the first p rows or the first p columns. For every such type there is a
probability distribution mu_alpha on even densities such that, in
positive semidefinite order,
P_alpha <= exp{ F(alpha) + O(p^2 log(s+1)) }
E_{r ~ mu_alpha} r^{tensor l}. (5.1)
Its multiplicity is at most exp(O(p^2 log(s+1))), and the number of
types present is at most (s+1)^{2p}. All constants are absolute.
The signed action and its hook support are classical in the hook theory
of Berele and Regev. Positive domination by mixtures of tensor powers
underlies the postselection technique of Christandl, Konig and Renner,
Postselection technique for quantum channels with applications to
quantum cryptography, Phys. Rev. Lett. 102 (2009), 020504, Lemma 2 and
proof of Theorem 1. The signed form of Lemma C is derived from ordinary
Schur-Weyl sectors, keeping the irreducible dimension D_alpha explicit.
pdf/berele-regev-1983.pdf
pdf/christandl-konig-renner-2009.pdf
Proof of Lemma C. For l = 0 the tensor space and its only representation
have dimension one, and any density satisfies the conclusion. Suppose
l > 0. Fix the number t of even factors. A fixed parity pattern is the
ordinary tensor product of E^{tensor t} and O^{tensor (l - t)}, with the
symmetric-group action on the latter twisted by sign. Summing over
parity patterns induces this action from S_t x S_{l - t} to S_l. Write
W_sigma(E) and W_tau(O) for the ordinary Schur-Weyl multiplicity spaces,
the polynomial irreducibles of highest weights sigma and tau. The
resulting orthogonal sectors, indexed by sigma |- t and tau |- (l - t)
with at most p rows each, are
V_{sigma, tau} = Ind_{S_t x S_{l-t}}^{S_l}
([sigma] x [tau'])
x W_sigma(E) x W_tau(O).
The induction records positions of the two parities; the transpose on
tau records the odd sign twist.
Strip inequalities. The representation [tau'] occurs upon inducing sign
representations on subgroups of sizes tau_1, ..., tau_p, since its
columns can be added successively as vertical strips. If alpha occurs in
V_{sigma, tau}, Pieri's rule reaches it from sigma by at most p vertical
strips. Transposing and interchanging the two factors gives the same
statement starting from tau. After padding with zeros,
alpha_i <= sigma_i + p, alpha'_j <= tau_j + p.
In particular alpha_{p+1} <= p, which is exactly the hook condition.
Conversely, given a hook shape, take its first p rows as the even shape
and then add the boxes below those rows by columns from left to right;
that uses at most p vertical strips. In the odd tensor power, words with
one basis symbol for each strip and with the prescribed multiplicity
carry the corresponding induction of sign representations. Pieri's rule
supplies the given hook shape. The first p row lengths and first p column
lengths specify any hook shape, so there are at most (s+1)^{2p} of them.
Weight versus dimension. For any type alpha occurring in V_{sigma, tau},
put
S = l log l - sum_i sigma_i log sigma_i
- sum_j tau_j log tau_j,
with zero summands interpreted as zero. The horizontal and vertical arm
lengths of alpha outside its p-by-p core are
H_i = (alpha_i - p)_+, i <= p,
V_j = (alpha'_j - p)_+, j <= p.
The strip inequalities give H_i <= sigma_i and V_j <= tau_j. Every hook
in a horizontal arm is at most its row hook plus p. Consequently an arm
of length H_i has hook product at most
prod_{r = 1}^{H_i} (r + p)
= H_i! C(H_i + p, p)
<= H_i! (s + p)^p.
The same bound holds for each vertical arm. The at most p^2 core hooks
have length at most s. The hook-length formula now gives
D_alpha >= (s + p)^{-O(p^2)}
l! / ( prod_i sigma_i! prod_j tau_j! ).
Using log(n!) = n log n - n + O(log(n+1)), whose linear terms cancel
because |sigma| + |tau| = l, proves
S <= F(alpha) + O(p^2 log(s+1)). (5.2)
Positive density per sector. Define diagonal matrices
d_E = diag(sigma_1/l, ..., sigma_p/l),
d_O = diag(tau_1/l, ..., tau_p/l),
and let r_U = (U_E d_E U_E^*) + (U_O d_O U_O^*), with independent Haar
unitaries on E and O. This is an even density. Write m_sigma = dim
W_sigma(E), m_tau = dim W_tau(O). The Weyl dimension formula gives, for
|sigma| = t,
m_sigma = prod_{1 <= i < j <= p}
(sigma_i - sigma_j + j - i)/ (j - i)
<= (t + 1)^{p(p-1)/2},
and the analogous bound for m_tau with t replaced by l - t. The tensor
power of d_E is positive and acts on the multiplicity space as W_sigma(d_E).
Its highest-weight line has eigenvalue prod_i (sigma_i/l)^{sigma_i}; all
other eigenvalues are nonnegative. The analogous statement holds for d_O.
These extend to zero eigenvalues by continuity, with 0^0 = 1.
The tensor density preserves every Schur-Weyl sector. Averaging over the
two unitary groups makes its action scalar on the two irreducible
multiplicity spaces. On the whole sector V_{sigma, tau} the scalar is
(Tr W_sigma(d_E)/m_sigma)(Tr W_tau(d_O)/m_tau)
>= prod_i (sigma_i/l)^{sigma_i} prod_j (tau_j/l)^{tau_j}
/ (m_sigma m_tau)
= e^{-S} / (m_sigma m_tau)
>= e^{-S - O(p^2 log(s+1))}.
The same scalar acts on every parity pattern: the density preserves the
patterns and has the same tensor factors on each. Thus their number does
not enter the scalar. If Q_{sigma, tau} is the orthogonal projection onto
this sector, positivity and (5.2) give
Q_{sigma, tau} <= exp{F(alpha) + O(p^2 log(s+1))}
E_U r_U^{tensor l}
whenever alpha occurs there.
Covering the isotypic projection. The relevant sector projections cover
P_alpha. Their number N_alpha is at most (s+1)^{2p}, because the two
padded partitions are specified by 2p integers between 0 and s. Sum the
last bound over these sectors, and choose a sector uniformly before
choosing the two Haar unitaries. The resulting probability distribution
mu_alpha satisfies
sum_relevant E_U r_U^{tensor l}
= N_alpha E_{r ~ mu_alpha} r^{tensor l}.
The factor N_alpha is absorbed into O(p^2 log(s+1)), which proves (5.1).
Finally, taking traces gives the multiplicity bound:
Tr P_alpha = D_alpha mult(alpha), while every tensor density has trace
one.
Block partition. When sites are partitioned into blocks, signed unitary
reordering makes the product-subgroup action a tensor product. Applying
(5.1) in each block gives products of densities constant within the
blocks. Each density is even, so undoing the signed reordering carries
this to the ordinary tensor product with its sites relabeled. In
particular, a constant tensor power of an even density commutes with the
full signed symmetric-group action.
Induction. Theorem A follows from Lemma B on sparse types and from
Lemma C combined with a rectangle-overlap argument on the remaining
types.
Constants order. Fix theta = a/16 and K_0 = 10/e_0 in Lemma B. The
resulting rho is uniform for sufficiently large R, so next fix an
integer
q >= max{ 1, ceil(2/rho) }, 2 q rho >= 4,
and only then fix a sufficiently large power of two R. Every largeness
requirement holds uniformly for s >= R. In particular require
1/sqrt(log R) <= e_0/2, 1/log R <= e_0/4.
Since b <= log s / log R and C(H) <= b h, these give
c(s) <= 2 c_0, e(s) >= e_0/2,
e(s) h log s - C(H) >= (e_0/4) h log s.
Further increases of R absorb the error terms. After R is
fixed choose z_* > 0 small enough for (3.2), Lemma B, and the base case.
Trivial types. Every conditional average is a contraction. When
F(lambda) = 0, the moment is at most one and the nonnegative right side
of (3.4) proves the theorem. This covers the empty diagram, M = 1, and
all one-dimensional types. A zero moment satisfies the bound by the
convention log 0 = -infinity.
Base case b = 1 at z = 0. Conditioning on the prescribed assignments
leaves a uniform bijection of the remaining slots, so every nontrivial
average is zero. Once R is fixed there are only finitely many
one-coordinate grids, path families, and representations, and their
conditional operators are continuous at zero. Decreasing z_* gives the
base case on a common small real interval.
Assume b >= 2 and Theorem A for fewer than b coordinates. The
contraction bound gives T_lambda^H <= D_lambda, so the desired
inequality holds automatically whenever
(1 + c(s)) F(lambda) <= e(s) h log s - C(H). (6.1)
Sparse-range reduction. Suppose F(lambda) < s^{1 - a/4} and (6.1) fails.
The positive allowance from the constants comparison gives
h log s <= K_0 F(lambda), and M = s - h >= s/2 for large R. Put
k = min(M - lambda_1, M - lambda'_1). The dimension bounds of the
preliminaries give
c_dim k <= F(lambda) <= k log s.
So h <= K_0 k and
h + k <= s^{1 - theta}
for large R, since theta = a/16 < a/4. Also k >= 1 because F(lambda) > 0.
Lemma B applies. There are D_lambda singular values, so
log T_lambda^H <= F(lambda) - 2 q rho k log s
<= -3 F(lambda)
<= -c(s) F(lambda) + e(s) h log s - C(H).
This settles the sparse range.
Large dimension. The remaining case is b >= 2 with
F(lambda) >= s^{1 - a/4}. (6.2)
The boxes of lambda outside the (p, p)-hook produce extra card
trajectories. The next few pages prove an intermediate estimate that is
uniform over the resulting path families. Set
p = floor(s^a),
hat c = c(s) + 1/(20 sqrt(log s)),
hat e = e(s) - 1/(20 sqrt(log s)).
Under the induction hypothesis for fewer than b coordinates, every
family H' of h' prescribed trajectories on the current grid, with
distinct slots at every layer and satisfying the coordinate rule of the
trajectory constraint, and every (p, p)-hook diagram gamma |- s - h',
satisfies
log T_gamma^{H'} <= - hat c F(gamma) + hat e h' log s
- C(H') + s^{9/10}. (6.3)
There is no lower bound on F(gamma) in this claim. The claim retains the
full trajectory potential and improves both coefficients slightly. It is
derived from two shorter coordinate sweeps; the dimension reserve of the
claim is then used when the removed boxes are restored.
Split. Partition the coordinate list into consecutive blocks of
floor(b/2) and ceil(b/2) coordinates, with products s_1 and s_2. Each
coordinate contributes between log R and 2 log R, so
(1/5) log s <= log s_u <= (4/5) log s, u = 1, 2.
In particular p <= s_u. Regard the grid as s_2 rows of length s_1. The
first part of the sweep acts within rows and the second part within
columns. At their junction, the middle positions of H' are removed,
leaving a fixed board of s - h' free sites. Splitting each prescribed
trajectory there gives the path constraints in each row and in each
column.
Signed tensor at the junction. Use the signed tensor representation of
Lemma C on the free sites at each layer. Let X be the conditional row
average from the input layer to the junction, and Y the conditional
column average from the junction to the output. The row and column
randomizations are conditionally independent under the fixed path
constraints, so YX is the full conditional average. At the junction let
P_gamma be the full-group isotypic projection, and let P_alpha^R,
P_beta^C be the row and column subgroup projections. The partition
alpha_i records the number of free sites in row i, and beta_j records
the number in column j; a row or column with no free sites has
the empty type. Sums range over the local types in the signed tensor
representation. Put
F_R = sum_i F(alpha_i), F_C = sum_j F(beta_j).
Isotypic identification. The full projection commutes with both subgroup
projections. Bijections between the layers intertwine their full
isotypic projections. Under compatible unitary identifications, the
restriction of Y P_gamma X from the input gamma-isotypic space to the
output gamma-isotypic space is K_gamma^{H'} tensor I, where I acts on
the tensor multiplicity space. The hook type occurs by Lemma C, so this
multiplicity is at least one. Inserting the subgroup decompositions at
the junction,
(T_gamma^{H'})^{1/(2q)} <= ||Y P_gamma X||_{2q}
<= sum_{alpha, beta} ||Y P_beta^C||_{2q}
||P_beta^C P_gamma P_alpha^R||_op
||P_alpha^R X||_{2q}. (6.4)
The first inequality uses the unnormalized trace on at least one copy of
gamma. The second uses the triangle inequality, the product norm
inequality, and ||A||_op <= ||A||_{2q} for an outer factor.
Child moments. Ordering the free sites by rows at both ends of the first
part makes X = tensor-product over i of X_i; signed unitary reordering
justifies this. Write H_i for the row-i path constraints and
mult(alpha_i) for the tensor multiplicity. Then
||P_alpha^R X||_{2q}^{2q}
= prod_i mult(alpha_i) T_{alpha_i}^{H_i}.
The column formula is identical. Lemma C bounds each multiplicity by
exp(O(p^2 log(s+1))). Apply the induction hypothesis to every local
constrained sweep and put
c_* = min_{u = 1, 2} c(s_u), e_* = max_{u = 1, 2} e(s_u).
Each stage line belongs to exactly one child subproblem, so their
potentials add to C(H'). Each part has h' prescribed trajectories, and
their size weights add as log s_1 + log s_2 = log s. Hence
log( ||P_alpha^R X||_{2q}^{2q} ||Y P_beta^C||_{2q}^{2q} )
<= - c_*(F_R + F_C) + e_* h' log s - C(H')
+ O((s_1 + s_2) p^2 log(s+1)). (6.5)
The middle factor in (6.4) depends only on the fixed free-site board,
so its estimate does not use the trajectory probabilities.
Lemma D (overlap at the junction). For the row and column type lists on
the free junction sites and the full hook type gamma,
log ||P_beta^C P_gamma P_alpha^R||_op^2
<= F_R + F_C - F(gamma) + h'
+ O((s_1 + s_2) p^2 log(s+1)). (6.6)
A zero norm has logarithm -infinity; the constant is absolute.
Proof of Lemma D. Since P_gamma commutes with both subgroup projections,
||P_beta^C P_gamma P_alpha^R||_op^2
<= ||P_beta^C P_gamma P_alpha^R||_HS^2
= Tr(P_alpha^R P_beta^C P_gamma).
The product P_beta^C P_gamma is a positive projection. Dominate P_alpha^R
inside this trace by Lemma C. Apart from a factor
exp(F_R + O(s_2 p^2 log(s+1))), this leaves a probability mixture of
product densities whose one-site matrix in row i is an even density r_i.
For one such row family, average over all s_2 rows, including empty
ones. For 0 < eps < 1 put
bar r = (1/s_2) sum_i r_i,
bar r_eps = (1 - eps) bar r + eps I/dim V,
A_eps = bar r_eps^{-1/2}.
The regularized reference density is even. With n = s - h',
B_eps = bar r_eps^{tensor n} is positive with trace one and commutes
with the full signed group action. On the gamma-isotypic space it has
the form I_{D_gamma} tensor B_gamma. Every eigenvalue there is
therefore counted at least D_gamma times in its trace, and
B_eps P_gamma <= D_gamma^{-1} P_gamma.
It also commutes with P_beta^C. Compress this inequality by that
projection, use P_beta^C P_gamma <= P_beta^C on the right, and conjugate
by B_eps^{-1/2}. The result is
P_beta^C P_gamma <= D_gamma^{-1} A_eps^{tensor n}
P_beta^C A_eps^{tensor n}.
Now dominate the column projection by its density mixture. Apart from
the corresponding factor exp(F_C + O(s_1 p^2 log(s+1))), each resulting
mixture integrand is the tensor-product trace
prod_{(i, j) free} tr(A_eps r_i A_eps v_j),
where v_j is the even density for column j. Each factor is nonnegative:
it equals ||r_i^{1/2} A_eps v_j^{1/2}||_HS^2. For every column, summing
these factors over all rows gives
sum_i tr(A_eps r_i A_eps v_j)
= s_2 tr(A_eps bar r A_eps v_j) <= s_2/(1 - eps).
If the column is missing l < s_2 sites, AM-GM on its s_2 - l retained
sites bounds their product by
(1 - eps)^{-(s_2 - l)} (s_2/(s_2 - l))^{s_2 - l}
<= (1 - eps)^{-(s_2 - l)} e^l.
If l = s_2 the empty column contributes the empty product one. There
are h' missing sites in total. Multiplying over columns, averaging the
uniformly bounded integrands, and letting eps -> 0 prove (6.6).
Combination. Write W for the right side of (6.6) including its error.
Terms with zero middle factor in (6.4) contribute nothing. For a
nonzero middle factor, its norm is at most one and also satisfies (6.6).
Since c_* <= 2 c_0 < 1 <= q,
q log ||P_beta^C P_gamma P_alpha^R||_op^2
<= c_* min(0, W) <= c_* W.
Adding this to (6.5) cancels F_R + F_C. The number of lists of local
hook types contributes only O_q((s_1 + s_2) p^2 log(s+1)) when the sum
in (6.4) is raised to the 2q-th power. So
log T_gamma^{H'} <= -c_* F(gamma) + e_* h' log s - C(H')
+ c_* h' + O_q((s_1 + s_2) p^2 log(s+1)).
Size reserves. With L = log s,
c_* - c(s) = e(s) - e_* >= (sqrt(5)/2 - 1)/sqrt L
> 1/(10 sqrt L).
The hats use only 1/(20 sqrt L) of each reserve. The remaining hole
reserve is at least h' sqrt L / 20, which absorbs c_* h' for large R.
Also
(s_1 + s_2) p^2 log(s+1)
<= 2 s^{4/5 + 2a} log(s+1) = 2 s^{0.82} log(s+1).
For fixed q the corresponding O_q error is at most s^{9/10} once R is
large. These comparisons prove (6.3) for every allowed H' and hook type,
including types of small dimension.
Outside cells, restored. Return to the diagram lambda in (2.2). Keep its
(p,p)-hook part gamma; the diagram gamma is Young. Translate the
remaining boxes by subtracting p from both indices to get an ordinary
partition delta, and put k = |delta|. The skew shape lambda/gamma is a
translate of delta. Branching and Frobenius reciprocity give
multiplicity D_delta for lambda in the representation induced from
[gamma] on S_{M - k} to S_M, and the induced space has dimension
(M)_k D_gamma. In particular,
F(lambda) <= F(gamma) + k log s. (6.7)
Realize the induced space with one fiber of type [gamma] for each
placement of k distinguishable cards in the free slots. A bijection
moves the placement and acts on its fiber by the bijection of the
remaining slots; consistent identifications of those slot sets change
the fiber maps only by unitaries. For one x and one y the block in the
[gamma]-representation is p_H(x, y) times the conditional operator in
[gamma] after those extra trajectories have been prescribed. If this
probability is positive the endpoints force a feasible augmented
family H' of h + k trajectories. Thus (6.3) applies to every nonzero
block, with no dimension condition on gamma.
Stacking 2q copies. Let W denote the operator
K_lambda^H - (1 - sigma(lambda)) K_{lambda'}^H,
with sigma(lambda) one for self-conjugate lambda and zero otherwise.
Its 2q-th Schatten norm equals T_lambda^H. Drop [gamma] from the
placement lists, and let T abbreviate the 2q-th Schatten norm of each
labelled operator. Since (M)_k D_gamma is the dimension of the induced
space, the standard trace bound gives
D_delta T_lambda^H
<= sum_{x_1, ..., x_{2q}} prod_{j=1}^{2q} p_j^{1 - 1/(2q)}
prod_{j=1}^{2q} ( T_gamma^{H'_j} )^{1/(2q)}, (6.8)
where p_j is the transition probability from x_j to x_{j + 1} (indices
taken mod 2q), and H'_j is the augmented family belonging to that edge.
Apply (6.3) to every factor. Then
D_delta T_lambda^H <= exp( -hat c F(gamma)
+ hat e (h + k) log s + s^{9/10} )
* Z,
where Z is the cycle sum above with the potentials absorbed. Bound the
potentials through (3.3): for one nonzero cyclic term,
prod_j p_j^{1 - 1/(2q)}
<= s^{-k} exp( sum_j ( C(H'_j) - C(H) )/(2q)
+ (log 4) k b ).
The augmented potentials have disappeared, leaving only the potential
of the original path family. It remains to sum the last product.
Put n_k = (M)_k and label the 2q placement
variables x_1, ..., x_{2q} cyclically. Each edge matrix is the placement
transition matrix or its transpose. Both row and column sums are one,
because the transition averages bijections of the free slots. For each
r let A_r be the product of all edge entries except the r-th. Then
prod_{j=1}^{2q} p_j^{1 - 1/(2q)} = prod_{r=1}^{2q} A_r^{1/(2q)}.
Deleting an edge opens the cycle into a chain. Successive summation
over an endpoint of that chain uses a row or column sum equal to one;
the last placement has n_k possible values. Hence sum A_r = n_k for
every r, and scalar Holder gives
sum_{x_1, ..., x_{2q}} prod_{j=1}^{2q} p_j^{1 - 1/(2q)}
<= prod_{r=1}^{2q} ( sum A_r )^{1/(2q)}
= n_k.
Restricting to the nonzero cyclic terms only decreases this sum.
The net counting factor is therefore s^{-k} (M)_k <= 1. Dividing by
D_delta and multiplying back into the exponential gives
log T_lambda^H <= -hat c F(gamma) + hat e (h + k) log s
+ s^{9/10} - C(H) + (log 4) k b - F(delta). (6.9)
Comparing cost to gain. Since hat c > 0, (6.7) gives
log T_lambda^H <= -hat c F(lambda) + hat e h log s
- C(H) + s^{9/10}
+ [ (hat c + hat e) k log s + (log 4) k b - F(delta) ]. (6.10)
The positive k terms in the bracket are the cost of changing the
dimension term from gamma to lambda and prescribing k extra
trajectories. The coefficient of k log s is
hat c + hat e = c_0 + e_0 = a/50.
Every row of delta is no longer than the (p+1)-st row of lambda, and
likewise for columns. Those two lengths are at most s/(p+1) by the
total size of lambda. Thus every hook of delta has length at most
2 s/(p+1). If k >= s^{1 - a/2}, the hook formula and k! >= (k/e)^k
give
F(delta) >= k log( k(p+1)/(2 e s) )
>= k ( (a/2) log s - log(2e) ).
This dominates the bracket's positive k terms for large R, because
./pdf/pdf/50 < a/2 and b/log s <= 1/log R. If instead k < s^{1 - a/2}, discard
-F(delta) <= 0; the bracket is then at most O(s^{1 - a/2} log s).
Absorbing the slack. In either case the bracket is at most
s^{9/10} once R is large. So
log T_lambda^H <= -hat c F(lambda) + hat e h log s
- C(H) + 2 s^{9/10}.
Increasing R absorbs the two s^{9/10} terms into (hat c - c(s))
F(lambda) + s^{4/5} log s, which is nonnegative once R is chosen. In
the one-dimensional trivial representation F(lambda) = 0, and the
bound holds by the convention log 0 = -infinity together with the
nonnegative allowance e(s) h log s - C(H) >= 0. The induction on b is
complete. Theorem A follows.
Analytic passage from z < 1 to z = 1. Theorem A governs L_m(z) for z in
a small real interval [0, z_*]. The application to binary sweeps reduces
to the case z = 1. The bridge is a barrier argument.
Uniform contraction on lines. Restrict [lambda] to a single-line
subgroup S_m, and let P and Q be the averages of U_m and B_m there.
The operator P is the orthogonal projection onto the line invariants,
and P Q = Q P = P, because uniform averaging absorbs every group
element. Relative to ran P (+) ker P,
(1 - z) P + z Q = I_{ran P} (+) z Q|_{ker P},
|| (1 - z) P + z Q ||_op <= max { 1, |z| kappa },
where kappa = || Q|_{ker P} ||_op <= 1. Choose r = 2 if kappa = 0, and
otherwise choose 1 < r < kappa^{-1}. Every line average is contractive
for |z| <= r.
Independence makes every stage average the product of its commuting
line averages, and the full operator is the ordered product of the
stage averages. Submultiplicativity gives
|| K_lambda(z) ||_op <= 1 for |z| <= r,
uniformly in the grid and in lambda.
Barrier function. Choose 0 < u < v < min { z_*, 1, r - 1 } and set
Omega = { z in C : |z| < r } minus [u, v].
For a parameter eps_0 > 0 define
G(z) = eps_0 int_u^v log( 1 / |z - t| ) dt.
The function G is harmonic off the segment. Direct integration of the
logarithm gives a continuous extension across the segment, endpoints
included.
Boundary of Omega. On |z| = r the inequality |z - t| >= r - v > 1 gives
G(z) <= 0. The values of G on the closed segment [u, v] are bounded, so
choosing eps_0 > 0 sufficiently small ensures G <= 1 there. Also G(1) > 0
since 0 < 1 - t < 1 for every t in [u, v].
Maximum principle. For complex z in Omega and lambda |- M define
Phi_lambda(z) = || K_lambda(z) ||_{2q} exp( eps G(z) ),
where eps > 0 is chosen small enough that the bound ||K_lambda|| <= 1
extends by continuity to the punctured segment. The function
z -> ||K_lambda(z)||_{2q} is continuous on the closed disk and
subharmonic in the interior. Multiplying by exp(eps G(z)) preserves
subharmonicity because G is harmonic in Omega. On the circle |z| = r
the operator bound ||K_lambda|| <= 1 gives Phi_lambda <= exp(eps G(z))
<= 1. On the segment G <= 1 gives Phi_lambda <= e^eps ||K_lambda||.
Taking eps sufficiently small that eps < (e_0/4) c(s) F(lambda) for
every lambda under consideration absorbs this into the desired
dimension saving.
Given the contraction bound at each z in [u, v], the same argument
applied to the function
z -> || K_lambda(z) ||_{2q} * D_lambda^{g * (re(G(z)))} ,
where g > 0 is the contraction exponent at the real interval, gives
|| K_lambda(1) ||_{2q} <= D_lambda^{-g * G(1) / 2}
after choosing eps_0 small enough that G(1) >= 1/2. Increasing R
absorbs the loss 2/G(1) by adjusting z_* and the sparse threshold theta.
Consequently there exists an absolute g > 0 with
|| K_lambda(1) ||_{2q} <= D_lambda^{-g} (7.1)
for every power-of-two grid and every prescribed family H, uniformly
in lambda.
At z = 1 the line law is the binary sweep on each line, and the
full-grid sweep is the binary coordinate sweep. Choose b = d,
Omega_j = {0, 1} for every j, so s = n = 2^d. Then K_lambda(1) is
the complete binary sweep averaged over the whole cube. The bound
(7.1) holds at z = 1.
Fourier comparison. For probability measures mu and nu on a finite group
G,
4 ||mu - nu||_TV^2 <= sum_{rho != triv} D_rho
|| hat(mu - nu)(rho) ||_HS^2,
where ||B||_HS^2 = Tr(B^* B) is the unnormalized Hilbert-Schmidt
norm. Cauchy-Schwarz bounds the left side by |G| sum_x |mu(x) - nu(x)|^2.
The regular-character orthogonality identity gives, for every real mass
function a on G,
sum_rho D_rho || sum_x a(x) rho(x) ||_HS^2
= |G| sum_x a(x)^2.
Apply this to a = mu - nu = mu - U. The trivial coefficient is zero,
and uniform measure has zero Fourier transform in every nontrivial
irreducible.
Sign. In the final physical shuffle of a positive-time block,
condition on every coin but one. Flipping that last coin reverses the
resulting permutation by a transposition, so the block law has zero
expected sign. For sigma = q_d^{*wd} and any wd >= 1,
hat sigma(sign) = 0.
Convolution. For each irreducible lambda of S_n, let B_lambda be the
average of the physical shuffle law in [lambda], so hat q_d(lambda) =
B_lambda. Convolution multiplies Fourier matrices. Operator norms are
submultiplicative, and for a matrix of rank D,
|| A ||_HS <= sqrt D || A ||_op.
Applying (7.1) to B_lambda in the form ||B_lambda||_op <= D_lambda^{-g}
and raising to the wd-th convolution gives
D_lambda || hat sigma(lambda) ||_HS^2
<= D_lambda^{3 - 2 g w d}. (7.2)
Dimension sum. For fixed beta > 0 and large N, the following estimate
controls sum_lambda D_lambda^{-beta}. Put
k(lambda) = min(N - lambda_1, N - lambda'_1).
A diagram with k(lambda) = k has first row N - k after transposing if
necessary, and its remaining k boxes form a partition of k. There are
therefore at most 2 * 2^k such diagrams, and the bound
D_lambda >= e^{-1} (N/k)^k gives
sum_{lambda : 1 <= k(lambda) <= N/3} D_lambda^{-beta}
<= 2 e^beta sum_{k=1}^{floor(N/3)}
( 2 (k/N)^beta )^k.
For k > N/3 and sufficiently large N, the exponential bound gives
log D_lambda >= c_dim N, and there are at most 2^N partitions of N.
Hence
sum_{lambda : k(lambda) > N/3} D_lambda^{-beta}
<= exp( (log 2 - beta c_dim) N ).
For each fixed k, the summand in the first bound tends to zero. It is at
most (2 * 3^{-beta})^k throughout its range. Thus the first sum tends
to zero when beta > log 2 / log 3, by domination from a summable
geometric sequence. The second tends to zero when beta c_dim > log 2.
Mixing. Apply the preceding estimate to (7.2) with beta = 2 g w d - 3.
For each fixed w satisfying
2 g w d - 3 > max { log 2 / log 3, log 2 / c_dim }
and sufficiently large d, the sum D_lambda^{3 - 2 g w d} converges to
zero as d -> infinity, uniformly over deterministic initial decks. Then
4 || q_d^{*wd} - U_n ||_TV^2 -> 0.
Along a sequence of d for which distance 1/4 has been crossed, the
upper bound wd exceeds t_mix(d). Uniformity in the deck shows the same
w works for every deterministic starting configuration.
Support obstruction. For every integer t >= 0,
|| q_d^{*t} - U_n ||_TV >= 1 - 2^{t n / 2} / n!.
The t n / 2 fair bits determine the permutation, whose support therefore
has at most 2^{t n / 2} elements. Testing that support gives the first
bound. Distance at most 1/4 requires its uniform mass at least 3/4,
yielding t >= (2/n) log_2(3 n! / 4) = 2d - O(1) by Stirling's formula.
Mixing time. Together,
t_mix(d) = Theta(d) = Theta(log n).
The upper bound wd is the first bound on t_mix(d) matching the order of
the support lower bound, uniformly in the initial deck.