diff 56bc728..f6bf760 coordinate_sweep_contraction_v2.txt
diff --git a/coordinate_sweep_contraction_v2.txt b/coordinate_sweep_contraction_v2.txt
index 6cd2165..87ec941 100644
--- a/coordinate_sweep_contraction_v2.txt
+++ b/coordinate_sweep_contraction_v2.txt
@@ -72,7 +72,7 @@ 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
+x=(x_1,...,x_d)inF_2^d. One physical Thorp shuffle
does the following.
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
@@ -82,7 +82,7 @@ does the following.
riffles along what was the second coordinate.
-In coordinates a physical shuffle sends (x_1,u)mapsto(u,x_1+xi_u),
+In coordinates a physical shuffle sends (x_1,u)|->(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
@@ -186,7 +186,7 @@ part{Notation and the standard tools we use}
# Conventions
-All vector spaces are over mathbb CbbC and all representations are unitary.
+All vector spaces are over C 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,...
@@ -237,9 +237,9 @@ to quote.
hook perturbation in the first row. We use this repeatedly. (Sagan
2001, Thm 3.10.2.)
[(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,
+ (C^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}
+ (C^h)^{ ⊗ L}~=⊕_{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,
@@ -247,7 +247,7 @@ to quote.
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.)
-[(T6)] Signed tensor space (mathbb C^hbbC^h ⊕ mathbb C^h)^bbC^h)^{ ⊗ s}
+[(T6)] Signed tensor space (C^h ⊕ C^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
@@ -261,7 +261,7 @@ to quote.
for the induction.)
[(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.
+ CR 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
@@ -317,7 +317,7 @@ 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.
+row and a subdiagram of size ell=min(v,floor( u/2)) 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
@@ -378,12 +378,12 @@ 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
+space L=( C^hbbC^h ⊕ C^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
+L; 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
@@ -415,11 +415,11 @@ 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 LcalL and subgroup isotypic projectors
+sector projector P of L 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).
+ Tr_{V_a}(P_sigma P_theta) le Tr_{L} P Q_theta P).
]
smallskipnoindentMajorising by product states.
@@ -435,7 +435,7 @@ 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).
+bounding Tr_{L} P T P).
smallskipnoindentThe quarter-root filter.
Two normalisations are needed at once: the global sector must pay
@@ -445,14 +445,14 @@ 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
+Tr_{L}|(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).
+le exp(-H(gamma,xi)/2)·(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
@@ -465,7 +465,7 @@ 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)),
+ Tr_{L} 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
@@ -550,7 +550,7 @@ the minimised expression is nonnegative, and a=lambda shows
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
+taken inside the (h,h)-hook, h=floor( N^delta), 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
@@ -567,13 +567,13 @@ hook with t=N-|a|,
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 IcalI of
+I={G_{N-t}times G_t}^{G_N}(V_a ⊗ V_b) (possible by
+branching and decomposing the restriction). The trace on I 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 IcalI is a direct sum over the t-sets Z of the board; at Z, the
+I 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
[
@@ -602,7 +602,7 @@ 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},
+ X_{ZZ}=(D_mu)/(L_R)sum_alpha(1)/(D_alpha)P_{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
@@ -611,13 +611,13 @@ 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
+Let A_l: E'to E and B_r: 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
+For fixed l, B|->< 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
@@ -667,15 +667,15 @@ 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 EcalE the error in (eq:budget),
+Therefore, with E 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,
+ le (2-A)E_0-(1-b_0)S+E,
]
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
+child weights) leaves only the error E. 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).
@@ -689,14 +689,14 @@ part{Schatten interpolation}
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
+smaller sweep. Let 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<∞,
- W_lambda|mathcal B(M,M')calB(M,M')|_p^p
+ W_lambda|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),
@@ -706,15 +706,15 @@ Proof.
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)
+W_lambda|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
+Also |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}
+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
@@ -746,7 +746,7 @@ for an absolute C.
Proof.
-Work on ordered injective k-tuples of positions xmapsto y. Let K be
+Work on ordered injective k-tuples of positions x|-> 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
@@ -815,7 +815,7 @@ smallskipnoindentSparse range. For 1le kle N^{1-eps},
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 .
+ le N^k· N^{k},N^{-eps k p/8}·(log-factor)^kle1 .
]
smallskipnoindentThe recursive step. Suppose (eq:main-bound)
@@ -857,7 +857,7 @@ 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
+halvings d|->lceil 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.