Random coordinate frames and partial permutation laws

Proof. There are at most 2^{tn/2} choices of all shuffle bits, hence at most that many possible states. If A is their support, then

If this distance is at most 1/4, the last ratio must be at least 3/4. Taking logarithms and then the least integer above the resulting lower bound proves the first part of (2.5). The integral bound \log(n!)\ge\int_1^n\log x\,dx=n\log n-n+1 and n!\le n^n give the asserted asymptotic lower bound. When t\le d, the support ratio is at most n^{n/2}/n!, which is at most (e/\sqrt n)^n. This proves the remaining statements.□

Proof. At each step a card has at most two possible successors. Its support therefore has at most 2^t positions. The uniform position law assigns that support mass at most 2^t/n, and passing from a full permutation to the position of one card cannot increase total variation. For the last assertion, undo the deterministic rotations. During the first d steps each coordinate is refreshed exactly once, with a bit that is fair conditional on the entire previous card path. These successive refreshed bits form a uniform binary string. Restoring the rotation preserves uniformity.□

Proof. For 1\le s\le T-d, the two successive bases give unique coefficients a_{s,t}\in\F, s<t<s+d, with

The coefficient of v_s cannot vanish, since otherwise v_{s+1},\ldots,v_{s+d} would be dependent; over \F it is therefore one.

We construct L_t so that its column selected at time t has the required value:

Begin with the map L_0 specified in the statement. For each time t, define a row c_t by putting a_{s,t} in column i(s) whenever 1\le s\le T-d and s<t<s+d, and putting zero in every other column. For fixed t the possible s lie within at most d-1 consecutive times, so their coordinate indices are distinct and differ from i(t). Thus c_te_{i(t)}=0. Set

Each factor squares to I and is invertible. It leaves the selected column unchanged and adds prescribed multiples of that column to the others.

Before a column’s first selection no prescribed update targets it, so (3.6) holds during the first period by the definition of L_0. If it is selected at time s and again at s+d\le T, it has value v_s after the first selection. At each intervening time t it receives a_{s,t} times the selected column, whose value is v_t by induction. Equation (3.5) gives its value v_{s+d} before its next selection. This proves (3.6), including an incomplete last period.

For this fixed schedule, define the transformed step shown in Figure 1:

In (3.8), the second factor is uniform in C_{v_t}. The first is a fixed member of that subgroup: writing f_t=c_tL_{t-1}^{-1},

The map x\mapsto x+f_t(x)v_t fixes or swaps each pair \{x,x+v_t\} because f_t is constant on the pair. Multiplication by it preserves the uniform law on C_{v_t}. Each \widetilde Q_t depends on its own independent increment Q^{\boldsymbol\iota}_t, so the transformed switches are independent. Their products telescope at every time:

This gives the joint path identity, and the cyclic specialization follows from (3.1).□

Proof. The terminal map L_T is a bijection on distinct position tuples and preserves \pi_q, which proves (3.9). The input map L_0^{-1} also preserves the uniform law on distinct lists, giving the averaged identity.□

Proof. Fix j and omit its superscript. By (4.3), revealing v_{t+1} does not update the old hidden-card law p_t. Given \mathcal F_t and this direction, the matching edges incident to observed cards are known. Their next positions reveal exactly the fresh coins on those edges. Those coins are independent of the old hidden position, so their revelation also leaves p_t unchanged; all other edge coins remain independent and fair.

An edge containing two positions of D_t averages their two masses. An edge containing exactly one position of D_t transports its mass to the unique position on that edge unoccupied by observed cards after the switch. Edges with no available position carry no hidden mass. These rules give the conditional vector at the exact field \mathcal F_{t+1} in (4.1). They also transport the uniform vector on D_t to the uniform vector on D_{t+1}. Transport preserves squared error, while averaging two masses reduces it by \frac12(p_t(x)-p_t(y))^2. This proves the exact identity.

For the expectation, split D_t=D^0\cup D^1 across J_t and put z_x=p_t(x)-1/r_j, u=|D^0|, and w=|D^1|. Since \sum z_x=0,

Every cross pair has matching probability 2/n in the hyperplane case. Combining this with the factor 1/2 in the exact decrement proves (4.5). In the proper-subspace case, every cross difference lies outside W_t and has probability 1/(n-|W_t|)\ge1/n; discard the other eligible pairs to obtain the denominator 2n. The calculation covers an empty side. The algebraic identity (4.6) holds for any real centered vector; a later use for another vector must also identify its averaging rule.□

Proof. For fixed \Lambda,\Xi, apply (4.8). At index j use the coarser field

The tower property and (4.9) give \Pr\{Z_T(c_j)=x\mid\mathcal H_j\} =\E[p_T^j(x)\mid\mathcal H_j]. The set D_T^j is \mathcal H_j-measurable, so Jensen’s inequality for the \ell^1 norm compares both vectors to the same uniform law U_{D_T^j}. Cauchy–Schwarz gives

Consequently, almost surely in the terminal data and initial data,

Averaging and applying Cauchy–Schwarz once more proves the lemma.□

Proof. Use v_i=e_i for 1\le i\le d. For d\le t<T put

and choose v_{t+1} uniformly in V\setminus J_t, with fresh direction randomness. Every d successive directions form a basis. Conditional on the complete schedule, use independent fair switches to form Z. Independently choose \mathcal M uniformly among labeled equal-size partitions. For a fixed a, let \Xi be this partition and let C be any deterministic ordering of V\setminus M_a, with q=n-m. This is the online setup above.

For each hidden index j, the available set contains the positions of all omitted labels:

Write D_t^{j,0}=D_t^j\cap J_t and D_t^{j,1}=D_t^j\setminus J_t. If J_t^0=J_t and J_t^1=V\setminus J_t, then

Fix the direction and switch history through time t, but not \mathcal M. This fixes Z_t and J_t, while Z_t(M_a) is a uniform m-subset of V.

For a uniform m-subset and a fixed half of V, let X be its count in that half. View the subset as an ordered sample without replacement. A specified set of \ell sampled indices all lie in the half with probability at most 2^{-\ell}. If I_i are the membership indicators, expansion gives

If one half contains fewer than m/4 sampled points, the other contains more than 3m/4. Markov’s inequality and a union bound therefore yield, for d\le t<T,

This bound averages the independent partition and the shuffle; it is not a concentration assertion conditional on the observed paths.

Off the event in (4.17), the conditional loss in (4.5) is at least \alpha\Delta_t^j. Its loss is always nonnegative. Applying (4.7) gives

Starting with \Delta_d^j\le1 and iterating for T-d=16kd steps, we obtain, uniformly in a,j,

Let \widetilde\delta_a(\mathbf v,\mathcal M) be the auxiliary tuple distance conditional on the complete schedule and partition. Use Lemma 4.2 with \Lambda=\mathbf v. Its terminal identification is automatic, since \mathcal F_T^j already contains the complete schedule and predecessor paths. Equations (4.10) and (4.19) give

The schedule remains inside the distance on the left.

For every fixed schedule and partition, choose \boldsymbol\iota=(1,\ldots,d) in Lemma 3.1. The first directions are v_j=e_j, so L_0=I. Corollary 3.2, followed by the terminal rotation, therefore gives the same-list identity

The frame maps enter only this fixed-schedule endpoint comparison. Summing (4.20) over a now gives \E_{\mathcal M}\sum_a\delta_a(\mathcal M)\le k\varepsilon_n. At least one deterministic partition attains this average bound. Finally, n^{3/2}e^{-2d}=\exp((\tfrac32\log2-2)d)\to0, while 2/3^{3/4}<1 makes b_n exponentially small in n. Thus \varepsilon_n\to0.□

Proof. For each a, call a coset C\in G/H_a bad if \mu(C)>2U_G(C), and let B_a be the union of its bad cosets. The identity expressing total variation as the sum of positive excesses gives

Take E=G\setminus\bigcup_a B_a. The union bound yields \varepsilon\le 2\delta<1, so conditioning is well defined. On E, the mass of \bar\mu exceeds that of \mu by total amount \varepsilon; on the complement, its mass is zero. This proves the total-variation equality in (5.1).

Fix a coset C\in G/H_a. If it is bad for this subgroup, then C\cap E=\varnothing. Otherwise,

The same estimate therefore holds for every coset in every one of the k systems. If \delta\le 1/4, then 1-\varepsilon\ge 1/2, giving the last assertion.□

Proof. Because the blocks are disjoint, their subgroups form the direct product H=H_1\times\cdots\times H_k inside G. By complete reducibility and the irreducible-representation theorem for finite direct products, the restriction of \rho to H is an orthogonal sum of isotypic spaces of the form

Here \pi_a is an irreducible representation of H_a, and \mathcal A_{\boldsymbol\pi} is a multiplicity space on which H acts trivially. These are the usual characteristic-zero representation facts; see, for example, [25, 8].

For every type \boldsymbol\pi that occurs, its tensor-product dimension is at most D. Consequently some index a satisfies \dim\pi_a\le D^{1/k}. Assign each entire isotypic space in (5.4) to one such index, choosing the least one in case of a tie. Grouping the assigned spaces yields an orthogonal decomposition

Each E_a is invariant under H, and every irreducible of H_a appearing in E_a has dimension at most D^{1/k}. The multiplicities in these restrictions are unrestricted.

For this fixed representation, put

Fix u_a\in E_a, and set

We first bound this single-vector orbit span. Regroup all copies of each H_a-irreducible, including copies coming from different H-types, into a single H_a-isotypic space. In such an isotypic space V_\pi\otimes\mathcal A_\pi, with b=\dim\pi, the group acts by \pi(h)\otimes\id. If v is the projection of u_a to this space, its orbit span is contained in the image of the linear map

That image has dimension at most b^2, independently of \dim\mathcal A_\pi. Each inequivalent H_a-type contributes only once. Summing over the different isotypic spaces gives the finite bound

Let \Pi_a be the orthogonal projection onto W_a. The subspace W_a is H_a-invariant, and therefore \rho(gh)W_a=\rho(g)W_a for h\in H_a. For each vector z, the nonnegative function

is thus constant on each left coset gH_a. The coset bound (5.2) implies

The uniform average of these projections is

It commutes with every \rho(g). Schur’s lemma makes it a scalar multiple of \id, and its trace is \dim W_a. Hence

Since \rho(g)u_a\in\rho(g)W_a, Cauchy–Schwarz, first for expectation and then in the representation space, gives

where the last line uses (5.5)–(5.7). For an arbitrary u=\sum_a u_a, sum the square-root form of this estimate and apply Cauchy–Schwarz in the index a:

The last equality uses the orthogonality of the E_a. Taking the supremum over unit vectors u,z and squaring proves (5.3). The argument includes zero components and one-dimensional representations; in dimension one the displayed sum does not provide decay.□

Proof. We first record two elementary counting observations. If a diagram has first row of length a and exactly b boxes below it, where 0\le b\le a, then

This is the tableau construction of Liebeck and Shalev [14, Lemma 2.1], with their parameters n=a+b and k=b. To see it directly, place 1,\ldots,b in the first b boxes of the first row. Choose any b labels from \{b+1,\ldots,a+b\} for the boxes below that row, and put them in increasing row-major order: read rows from top to bottom, and each row from left to right. Fill the rest of the first row increasingly with the remaining labels. Every box below the first row lies in one of its first b columns. Its top-row predecessor therefore has a label at most b, while all lower labels are larger than b. Row-major filling respects both row and column inequalities within the lower diagram, so this is a standard tableau. Different choices of lower labels give different tableaux. When b=0 the construction is the unique tableau of a single row.

Also, if \mu is a Young subdiagram of \lambda, every standard tableau of \mu extends to one of \lambda: retain its labels and fill the remaining boxes in row-major order with the successive larger labels. Because a Young subdiagram is closed under moving up and left, all required predecessors have already been filled. Consequently,

Write p(t) for the number of partitions of t. For t\ge 1, regarding a partition as an ordered composition gives

since a composition is specified by cuts in the t-1 gaps between t successive units. We set p(0)=1.

For a partition \lambda\vdash s, put

After transposing if necessary, assume its first row has length L. This does not change its degree. The case h=0 consists precisely of the row and column partitions, which are excluded from (6.3). We divide the other diagrams into three classes.

A long first row or column: 1\le h\le s/3. For fixed h, there are at most 2p(h) original shapes: after a possible transpose, the diagram below the first row is a partition of h. By (6.4),

Here the middle inequality follows by writing \binom{a}{b}=\prod_{j=0}^{b-1}(a-j)/(b-j) and bounding each factor below by a/b when a\ge b\ge1. Thus the total inverse-degree contribution with a given h is at most

For each fixed positive h, the binomial coefficient tends to infinity with s. The displayed geometric majorant is summable over h. Extending a contribution by zero when h>s/3, dominated convergence for this series shows that the total contribution of this class tends to zero.

Intermediate width: h>s/3 and L\ge s/8. Here L<2s/3, so h>L/2. Set b=\lfloor L/2\rfloor and take the subdiagram \mu consisting of the whole first row and the first b boxes below it in row-major order. There are enough boxes because h\ge b, and an initial segment of row-major order in the lower diagram is again a Young diagram. Applying (6.5) and (6.4) gives

The central binomial coefficient is the largest of the L+1 coefficients whose sum is 2^L. Using (6.6), the total contribution of this class is therefore at most

Small width and height: L<s/8. Number row and column indices starting at 1, and group boxes by their index sum. There are at most 2L-1 nonempty such diagonals. Fill the diagonals in increasing index-sum order, assigning the next available consecutive labels to each diagonal in any order. Every row or column predecessor has a strictly smaller index sum, so every such filling is a standard tableau. If the nonempty diagonal sizes are u_1,\ldots,u_q, then

We used u!\ge2^{u-1} for integers u\ge1, and q\le2L-1<s/4. The inverse-degree contribution of this class is at most

These three classes cover all partitions except the row and column, so they prove (6.3). For every s\ge2 those two partitions are distinct and each has degree 1. The complete sum in (6.2) consequently tends to 2 as s\to\infty. For each fixed positive s it is a finite sum of positive terms, since there are finitely many partitions and every degree is a positive integer. The tail of this convergent sequence is bounded, and its finitely many initial values have a finite maximum. This proves (6.2), including s=1, where the complete sum is 1.□

Proof. For every a, the group H_a is isomorphic to S_{|M_a|}. Hence (6.1) and Lemma 6.1 give

In the orbit construction of Proposition 5.2, this recovers \dim W_a\le C_0D^{18/k}, and the component bound (5.8) becomes

Substituting the displayed degree bound into (5.3) yields

Taking square roots proves (6.10).□

Proof. Cauchy–Schwarz bounds the left side by |G|\sum_g|\nu(g)-|G|^{-1}|^2. For any real function a on G, expansion and the regular-character identity give

Apply this to a(g)=\nu(g)-|G|^{-1}. The trivial coefficient vanishes; uniform averaging in every nontrivial irreducible is zero. These facts give (7.1).□

Proof. Condition on every switch bit except one in the final physical shuffle. Changing that bit composes the output permutation with a transposition, so its two possible signs are opposite and equally likely. The expectation of sign is therefore zero. The two perturbation estimates follow by summing against a function of absolute value one; their respective \ell^1 differences are 2\varepsilon and 1-m.□

Proof of Theorem 1.1. Fix k=64 and let d\ge6 grow. Put T=1025d and \mu=q_d^{*T}. Proposition 4.3 supplies a partition of the labels into k sets of size m=n/k for which the sum of the complementary marginal errors tends to zero. Lemma 5.1 therefore applies with their sum at most 1/4 for all sufficiently large d. It supplies a probability measure \bar\mu such that

Here H_a permutes the ath label block and fixes all other labels. Corollary 6.2 gives, simultaneously for every irreducible \rho of dimension D,

where C_0 is the absolute constant in Lemma 6.1.

Take \ell=32, a fixed number independent of d. Operator-norm submultiplicativity and \|B\|_{\HS}\le\sqrt D\|B\|_{\op} show that the contribution of the nontrivial, nonsign representations to the right side of (7.1), for \nu=\bar\mu^{*\ell}, is at most

The last conclusion follows from Lemma 6.1, since D^{-21}\le D^{-16} for D\ge1. Neither diagonalizability nor normality of the Fourier matrices is needed here.

The sign representation has dimension one, so (7.3) alone gives no decay. Lemma 7.2 shows that \widehat\mu(\sgn)=0 and therefore

Its contribution after \ell factors is therefore o(1) as well. Together with Lemma 7.1 and (7.4), this proves \|\bar\mu^{*32}-U\|_{\TV}=o(1).

Convolution by a probability measure contracts total variation. Replacing the factors one at a time and using (7.2) gives

Successive independent T-step blocks of the original shuffle have law \mu, so \mu^{*32}=q_d^{*32800d}. Equation (2.2) makes this conclusion uniform over the initial ordering. In particular the distance is at most 1/4 for all sufficiently large d, as required.□

Proof. For a variable Z in an interval of length b, put \psi(s)=\log\E e^{sZ}. Its second derivative is the variance under the exponentially tilted law, at most b^2/4. Integrating from \psi(0)=0 and \psi'(0)=\E Z gives \E e^{s(Z-\E Z)}\le e^{s^2b^2/8}. Multiplication and minimization in s prove the independent-variable bound. The conditional version, with interval length 2c_j, gives \E e^{s(M_r-M_0)}\le e^{s^2\sum_jc_j^2/2} and the martingale bound. These are the exponential-moment arguments underlying the inequalities of Hoeffding and Azuma [10, 3].

Expose a uniform subset in a uniform random order and form the Doob martingale for its final half-count. The expected final count changes by at most one at each draw: completions following two possible next draws can be coupled by exchanging those points. The initial expectation is m/2. Use r=m, c_j=1, and a=m/4.□

Proof. Fix the complete direction schedule. The direction v_{s-d} crosses the two cosets of W_s, because the d directions starting at s-d form a basis. The intervening directions lie in W_s and preserve each coset.

Condition on the observed configuration immediately before step s-d. Let a be the number of matching pairs with two available positions and b the number with one, so m=2a+b. Immediately after this crossing switch, the available count on either chosen side is a+\operatorname{Bin}(b,1/2), using b independent fair coins. Its mean is m/2. If b>0, Lemma 8.1 bounds a deviation of at least m/4 by 2\exp(-2(m/4)^2/b)\le2e^{-m/8}; if b=0 the count is exactly m/2. The intervening switches preserve the count. Remove the conditioning to obtain the claim.□

Proof. For a successive hidden-card problem, its number m of available positions is at least N/L. Off the event in (8.3), Lemma 4.1 gives conditional expected loss at least \gamma\Delta_t, where \gamma=1/(4L). The loss is always nonnegative. Equation (4.7) therefore gives, for t\ge d,

Starting from \Delta_d\le1 yields \E\Delta_T\le(1-\gamma)^{T-d}+2e^{-N/(8L)}. Apply Lemma 4.2 with terminal data \Lambda=\mathbf v. For every complete schedule, the first basis is (e_{\iota_1},\ldots,e_{\iota_d}), so L_0=I in Lemma 3.1. The same-list equality (3.9) transfers the conditional tuple bound to X^{\boldsymbol\iota}, giving (8.4).

Each switch is an involution. Reversing the independent factors therefore identifies (X^{\boldsymbol\iota}_T)^{-1} with a coordinate chain whose first axis is i(T) and whose periodic order is reversed. This is another permitted ordering, so the same estimate applies. The relation Y_T=R^TX_T transfers the forward physical law by an output bijection. Its inverse is X_T^{-1}R^{-T}; the input bijection only changes the fixed list, and the bound is uniform in that list.

For (8.5), weaken the additive term in (8.8) to 2e^{-N/64} and sum the geometric series, giving the factor 64. At 257d keep the sharper recurrence and use (31/32)^{256d}\le e^{-8d}. More generally, at T=(1+64L)d, the weakened additive term 2e^{-N/(8L)} gives e^{-16d}+8Le^{-N/(8L)}, yielding (8.7). These rates dominate the factor N^3 in the squared tuple bound, and e^{-16d}=o(N^{-4}).□

Proof. The map S_s is an involution in C_{e_{i(s)}}, because b_se_{i(s)}=0. The increment of Z is

For fixed \Lambda, the factors S_sh_s are independent and uniform in their coordinate matching groups. Conjugation gives the asserted product-switch law, including the joint prefix identity (8.9).

Extend i(s) periodically beyond T and define the deterministic next-read time of a column by

Right multiplication by S_s leaves the selected column unchanged and adds b_{sj}v_s to column j. Thus the direction at a column’s first read, for t\le d, is

These first d directions form a triangular basis. At later reads,

In either display the coefficients used at time t are exactly the entries whose next-read time is t. Inductively, all earlier directions are functions only of entries with next-read time less than t. The batch read at t is therefore independent and fair conditional on those directions. The recurrence also shows inductively that every consecutive d directions form a basis. For t>d, its fresh d-1 coefficients make v_t uniform on v_{t-d}+W_t=V\setminus W_t.

Finally, (8.9) says that the entire virtual path prefix and \Lambda are conditionally independent given the direction prefix. Hence observing any portion of that path prefix cannot reveal the fresh batch that determines the next direction.□

Proof. Use the direct direction process with standard first basis, sampled independently of B, and take \Xi=B in the online construction. At every time the available set for a hidden card contains Z_t(B). Fix the full direction schedule and the full permutation Z_t, but not B. The set Z_t(B) is then a uniform b-subset, and each coset of the next-direction hyperplane has size N/2.

Its count in a specified half has the distribution of the number of ones among the first b of N independent fair bits, conditional on their total being N/2. This conditioning event has probability at least 1/(N+1), because the central binomial coefficient is maximal. For the unconditioned first-b count J,

The inclusion of Z_t(B) in the available set and a union bound give p_{\mathrm{bad}}=2(N+1)\theta^b as an upper bound for the probability that either available half has fewer than b/4 positions. This bound is unconditional in the observed paths.

Off this event the conditional expected loss is at least \Delta_t/32. Equations (4.7) and (4.5) give

Use Lemma 4.2 with \Lambda=\mathbf v. For each fixed schedule and B, the standard first basis gives L_0=I, so the conditional auxiliary distance equals the distance for X_T on that same complement. Averaging over B proves the bound.□

Proof. Use the direct process with the standard first basis and take \Xi=C. For a hidden label at index j, let h=N-j+1\ge m be the number of available positions. Fix the complete direction and switch history, but not C. At each fixed time, the preceding positions form a uniform ordered sample, so the available set is a uniform h-subset. The next-direction hyperplane is fixed under this conditioning.

If X is the count of a uniform h-subset in a fixed half, expand the product of 1+I_i over an ordered sample without replacement. Any specified \ell sample indices lie in that half with probability at most 2^{-\ell}. Thus

The second inequality follows by applying Markov’s inequality to the count in each half above 3h/4. It is used only after averaging out the input list, not conditional on observed paths.

On the balanced event, the conditional expected loss is at least h\Delta_s/(4N). With \gamma_j=h/(4N), the unconditional recurrence and its iteration give

Lemma 4.2, with \Lambda=\mathbf v, bounds the average distance conditional on the full schedule and list. For every fixed schedule the first basis is standard, so the same-list frame equality transfers that distance to X_t; the terminal rotation transfers it to the physical shuffle. This proves (9.2). A uniform starting deck sends any fixed ordered label list to a uniform input tuple, which proves the last assertion.□

Proof. The respective contracting times are 512d, 2048d, and 32bd, with energy factors at most e^{-8d}, e^{-32d}, and e^{-8d}. Use e^{-8d}\le N^{-8} for the first and N^{3/2}e^{-16d}=o(N^{-10}) for the second. Exponential decay in N handles the other term in each case.□

Proof. For the hidden label at index j, let h=N-j+1\ge N/8. Conditional on the full direction and switch history but not on C, its available set is a uniform h-subset. For its count in the fixed half J_t, choose each point independently with probability h/N and condition on selecting exactly h points. That size has probability at least 1/(N+1): it is a mode of the binomial size distribution, as comparison of consecutive probabilities shows. Before conditioning, the half-count has mean h/2 and is a sum of N/2 independent bounded variables. Lemma 8.1 gives

For h=N the count is deterministic and the bound is automatic.

The proper-subspace part of Lemma 4.1 gives conditional expected loss at least h\Delta_t/(8N)\ge\Delta_t/64 off this event. Hence, from time zero,

Apply the terminal tuple lemma with \Lambda=\mathbf v and then the per-schedule averaged equality (9.5). This proves (9.6).□

Proof. Use the random initial basis process above. At a hidden index, the number h of available positions is at least N/b. Conditional on the complete direction and switch history, and before sampling the list, this set is a uniform h-subset. Thus (9.3) bounds its imbalance across the chosen J_t by 2\vartheta^h.

On the balanced event the proper-subspace contraction gives loss at least \Delta_t/(8b). Using the weaker additive term 2\vartheta^{N/b} in the unconditional recurrence yields

The terminal tuple comparison and then (9.5) give

Here (1-1/(8b))^T\le e^{-4d}, so the right side tends to zero. Since T is a multiple of d, X_T=Y_T in the rotating-frame coupling, which proves the physical statement.□

Proof. Fix z with z_i=0, and set

Thus z_{d-1}=z. Replace the rth switch by

We verify that the replaced switches have exactly the original joint law. For j\ne i, T_w e_j=e_j, so conjugation by T_w maps the matching subgroup in direction e_j onto itself. Also

is a fixed member of that matching subgroup: it either swaps or fixes each pair, since x_i is constant on a coordinate-j_r pair. Therefore S_r\mapsto S'_r is a bijection of this subgroup. It depends only on r and z, so the S'_r remain independent and uniform conditional on \mathcal A.

Run the available-set and mass recursion with these replaced switches, starting from the same (B_0,p_0). We claim that at stage r its state is (T_{z_r}B_r,p_r\circ T_{z_r}^{-1}). This holds initially because T_{z_0} is the identity. Conjugation carries the matching edges at the previous stage bijectively to matching edges. An edge with two available endpoints is averaged in either recursion, and a subsequent fixed swap does not change its equal output masses. An edge with one available endpoint carries its mass to the image of that endpoint under the replaced switch. The assertion is immediate on edges with no available endpoint. These three cases prove the induction. Centering by the uniform mass on the available set transforms in the same way. Since the two switch arrays have the same conditional law, the terminal invariance follows.

Every intermediate switch preserves x_i, proving the assertion about the counts. The squared-energy decrease in the final coordinate-i layer is

Indeed, transport preserves squared norm and averaging two entries decreases it by half the square of their difference. We may average this expression after applying an independent uniform T_z, by the conditional invariance already proved. Each pair x\in B\cap H_0, y\in B\cap H_1 becomes a coordinate-i pair for exactly one of the N/2 possible values of z. Consequently

The entries of a sum to zero. With A=\sum_{x\in B\cap H_0}a(x), the last double sum equals

Taking conditional expectations proves (10.2). Empty halves give a zero lower bound and require no separate division. When d=1, the same calculation has only z=0 and remains valid.□

Proof. The degree assertions follow from [22, Theorem 6.3]. The same companion gives separate proofs at powers 1,2,10 in Lemmas 6.4, A.2, and A.5; these also justify the fixed-power sums used below. The two modifications, including their common-measure and mass claims, follow from [22, Lemma 2.3]. The normalization assertion for f follows from Lemma 11.3 below; dividing the exact cap by z gives the normalized cap.□

Proof of Proposition 11.2. Write A=\widehat f(\rho) and abbreviate S_i(D) to S_i. If z=0, then f=0 and every assertion is immediate. Assume z>0.

The common small-type cover. Disjoint supports embed H_1\times\cdots\times H_r in G: the factors commute, and a product that is identity restricts to the identity on every M_i. Complete reducibility and the direct-product description of irreducibles [8, Theorems 3.12 and 4.25 and Proposition 3.14] give

The sum is over distinct occurring product types, with their full multiplicity spaces. Each has \prod_i\dim\tau_i\le D, so some factor has degree at most D^{1/r}. Unused labels can change the occurring types and their multiplicities, but do not change this product bound.

Let P_{i,\tau} be the orthogonal projection onto all copies of the H_i-type \tau, and put

On each product-type summand, P_i is identity or zero according as the ith factor is small or large. Hence the P_i commute, and at least one is identity on each summand. Therefore

The Q_i assign a whole product type to its first small factor; the P_i may overlap. Both families retain every multiplicity. For every u>0, the definition of C_u gives

The orbit estimate. For v\in V_\rho, write v_i=Q_iv and W_i=\Span\{\rho(h)v_i:h\in H_i\}. The single-vector orbit lemma [22, Lemma 3.1] gives \dim W_i\le S_i. Indeed, in all copies of a type \tau, the orbit of its component is contained in the image of

whose dimension is at most (\dim\tau)^2, independently of the multiplicity.

Let \Pi_i project onto W_i. Since W_i is H_i-invariant, the projection onto \rho(g)W_i depends only on gH_i. The coset cap and Schur averaging yield

Here the uniform average of \rho(g)\Pi_i\rho(g)^* is (\dim W_i/D)I, by its trace and irreducibility. Weighted Cauchy–Schwarz retains the mass z:

The v_i are orthogonal. Summing and applying Cauchy–Schwarz over i gives

This proves (11.1). Its specialization u=2, with z\le1, is (11.3); the condition r>4 makes that dimension exponent negative.

The isotypic estimate. For a subgroup H\le G and an irreducible H-type \tau of degree a, define

Its transform is the projection P_{\sigma,H,\tau} onto all copies of \tau in \sigma|_H. Thus \widehat{f*e_{H,\tau}}(\sigma)= \widehat f(\sigma)P_{\sigma,H,\tau}: a bound on the left cosets gH controls a projection on the right of the Fourier matrix. The companion’s cosetwise isotypic lemma [22, Lemma 3.4] applies to every subgroup H. If f(gH)\le K[G:H]^{-1}, it gives

This is the central-projection step; it retains the whole projected Fourier matrix and the mass factor.

Trace the first inequality of (11.6) against A^*A, and apply (11.7) to each selected H_i-type after discarding the other ambient irreducibles. Then

The trace inequality uses positivity of A(\sum_iP_i-I)A^*; it does not require A^*A to commute with the projections. This proves (11.2) using the overlapping P_i, rather than the orbit assignment Q_i.

The coefficient alternative. The independent coefficient calculation in [22, Lemma 4.3] bounds each coset separately. Its norm and orientation give the selected-type refinement in (11.4). For one subgroup H\le G, put F=|G|f, so \E_{h\sim U_H}F(xh)=[G:H]f(xH)\le K. For an H-type \tau of degree a, choose one representative x of each coset and set

The function q on this coset is the orthogonal projection of F onto the conjugate coefficient space of \tau. Schur orthogonality and the nonnegative weights F(xh) give

Expanding T_x and using, for h,k\in H, \overline{\chi_\tau(k^{-1}h)}=\chi_\tau(kh^{-1}) shows that these coset projections form the single function q=|G|(f*e_{H,\tau}). Thus their tested Fourier matrix is \widehat f(\sigma)P_{\sigma,H,\tau}, with the same right-hand orientation as above. Averaging the preceding norm bound over cosets and applying complex finite-group Plancherel gives

The calculation counts a type once, regardless of its multiplicity, and assumes no pointwise bound inside the coset. The same positive trace comparison now gives \|A\|_{\HS}^2\le K^2D^{-1}\sum_iS_i. Using S_i\le C_{10}D^{12/r} proves (11.4), including its original sum over the types of the unmodified subgroups H_i.

The branching refinement. Each H_i is conjugate to the standard subgroup S_{|M_i|} of S_N. Young branching [11, Theorem 9.2] shows that every occurring type \tau\vdash |M_i| is a subdiagram of \lambda; different corner-removal sequences can give arbitrary multiplicity. If \lambda_1\ge\lambda'_1, the diagram \tau has at most k_\lambda boxes below its first row. Its lower diagram, together with its fixed size, determines the first row, so at most M(k_\lambda) distinct types can occur. If \lambda'_1>\lambda_1, transpose both diagrams for this count. Transposition preserves degrees and does not replace f or its Fourier matrix by a sign-twisted law.

Nonoccurring isotypic projections are zero. In the positive trace comparison, apply (11.7) only to the occurring selected types and use (\dim\tau)^2\le D^{2/r}. There are at most M(k_\lambda) of them for each support, giving (11.5). The same argument includes k_\lambda=0, where the representation is trivial or sign, D=1, and M(0)=1. It also includes all unequal nonempty supports and every restriction multiplicity.□

Proof. The regular-character expansion in Lemma 7.1, with coefficients a(g)\overline{a(h)}, proves (11.10). Apply it to \xi-mU_G and \xi-U_G. Their trivial coefficients are respectively 0 and m-1, and their nontrivial coefficients are those of \xi. Cauchy–Schwarz gives (11.12). If \xi\le\mu, the nonnegative difference has mass 1-m. Also \sum_g|\xi(g)/m-\xi(g)|=1-m; the triangle inequality and the factor 1/2 in TV prove the normalization claim.□

Proof. Let T=256d and \mu=q_d^{*T}. For d\ge3, partition the labels into eight sets M_i of size N/8. The fixed-list estimate (8.5) bounds each complementary image-tuple error by

Exact trimming by Proposition 11.1 gives 0\le f\le\mu with mass z, where 1-z\le8\delta_N=o(1), and cap one on all eight coset systems.

For this covering partition, the companion isotypic estimate [22, Proposition 3.5], with inverse-degree parameter 1, gives \|\widehat f(\rho)\|_{\HS}^2\le8zC_1D^{-5/8}\le8C_1D^{-5/8}. Consequently

since 1-2(5/8)=-1/4 and [22, Theorem 6.3] gives the inverse-quarter limit. The sign coefficient of f is at most 1-z in magnitude, and the trivial coefficient of f^{*2} is z^2. Lemma 11.3 therefore gives

Adding back the missing mass 1-z^2=o(1) proves \|\mu^{*2}-U_G\|_{\TV}=o(1). The two physical blocks take 2T=512d shuffles, and (2.2) gives uniformity over starts.□

Proof. For T=256d, let \mu=q_d^{*T} and use eight equal label parts. The error \delta_N in the preceding proof bounds each complementary marginal. Deleting heavy cosets loses \eta\le16\delta_N=o(1) and produces a probability \nu with cap K\le4 for large d. Equation (11.3) with r=8 gives

For eight factors the nonsign, nontrivial Plancherel contribution is at most

The sign contribution is at most (2\eta)^{16}, and the trivial coefficient is one. Thus \nu^{*8} tends to uniform in TV. Restoring the true factors costs at most 8\eta=o(1), and 8T=2048d physical shuffles.

For the fixed-list subprobability route take T=257d. Equation (8.6) makes the summed error on any partition into eight equal parts o(1). Exact trimming gives f\le\mu=q_d^{*T} of mass z=1-o(1) and cap one. The orbit bound is \|\widehat f(\rho)\|_{\op}\le\sqrt{8C_2}D^{-1/4}. In (11.13), the trivial term is (z^8-1)^2, the sign term is at most (1-z)^{16}, and the remaining sum is at most (8C_2)^8Z_2(N). These terms and the restored mass 1-z^8 all vanish. The eight time blocks take 2056d physical shuffles.

For the random omitted set route, Proposition 9.1 and the partition averaging above give a partition into eight equal parts with summed error o(1) at T=257d. Heavy-coset deletion loses \eta=o(1) and gives cap K=2/(1-\eta). The orbit bound is \sqrt{16C_2/(1-\eta)}D^{-1/4}. The eight-factor nonsign sum is at most [16C_2/(1-\eta)]^8Z_2(N)=o(1), the sign term is at most (2\eta)^{16}, and restoring the true factors costs 8\eta=o(1). Again 8T=2056d. Equation (2.2) handles every start.□

Proof. The ordinary marginal assertion is Lemma 9.5, specifically (9.8). The partition averaging above selects 64 equal parts whose complementary errors sum to o(1). Exact trimming by Proposition 11.1 gives 0\le f\le\mu_T, of mass z=1-o(1), with cap one for all 64 coset systems. This is the stated domination of the complementary marginals.

Use the direct inverse-tenth input cited in Proposition 11.1 and the orbit estimate (11.1) with r=64, u=10, and z\le1. It gives

At sixteen factors the nonsign, nontrivial Plancherel sum is at most

because the displayed exponent is -11. The sign contribution is at most (1-z)^{32}, and the trivial term is (z^{16}-1)^2. Equation (11.13) and restoration of the missing mass 1-z^{16}=o(1) prove convergence for \mu_T^{*16}. The block length T=2048d is a multiple of d, so these are 16T=32768d physical shuffles. Equation (2.2) gives the assertion from every deterministic start.□

Proof. Use 32 equal label parts. Equation (8.7) makes all complementary errors o(1). Exact trimming gives f\le\mu=q_d^{*T} of mass z=1-o(1). Its normalization \nu=f/z is within 1-z of \mu in TV and has cap at most two for large d. The coefficient estimate (11.4), with r=32 and K=2, gives

For 32 factors the nonsign, nontrivial Plancherel sum is at most

The sign term is at most [2(1-z)]^{64}, and the trivial coefficient is one. Restoring the true factors costs 32(1-z)=o(1). The physical time is 32T=32(2049d)=65568d; translation invariance gives the same conclusion from every deterministic start.□

Proof. At T=1024d, choose eight equal label parts whose summed complementary error is o(1). Heavy-coset deletion produces a probability \nu within \eta=o(1) of \mu=q_d^{*T}, with cap at most four. For every \lambda\notin\{(N),(1^N)\}, the branching estimate and (11.16), with r=8, give

Four factors therefore leave the inverse-first Plancherel sum:

The displayed sign term uses (11.14); the trivial coefficient is one. Restoring the four true factors costs 4\eta=o(1). Their physical time is 4T=4096d, and (2.2) gives the same conclusion from every start.□

Proof. Lemma 2.1 gives distance at least 1-(e/\sqrt N)^N>1/4 for every integer t\le d when d is large. Lemma 2.2 gives the stated one-card bound for every d. The upper bound follows from Corollary 11.4; (2.5) gives the sharper lower asymptotic 2d-O(1).□

Proof. Lemma 3.1 gives exactly the asserted path-law identity, with L_0e_i=v_i. Its construction applies to every fixed schedule with consecutive basis windows and permits an arbitrary initial basis. It remains to check what happens to trajectory labels.

If labels a,b are paired in the cyclic process just before layer t, then g_{t-1}(b)=g_{t-1}(a)+w_t. The column identity in that frame construction is L_{t-1}w_t=v_t. Hence their transformed positions, with initial labels changed by L_0, differ by v_t and are paired in the transformed process. The implication reverses because L_{t-1} is invertible. When L_0=I, the labels themselves do not change. For general L_0, its bijection preserves the uniform law of the input list. The terminal bijection L_T preserves uniform injections and total variation. This proves both assertions.□

Proof. The online averaging and transport rules are those of Lemma 4.1; here we must also justify conditioning on complete observed paths. A feasible specification of those paths prescribes precisely the coins on the visited time-edge pairs. Necessity is immediate. Conversely, those prescribed coins force the paths, by induction over the layers. The path event is therefore a cylinder in the independent coin array. All other coins remain independent and fair, including unvisited coins at earlier times.

On an edge used by an observed label the coin is fixed; on an edge with two unobserved positions it remains fair. Future path constraints use later time-edge pairs and do not alter this earlier recursion. Thus the conditional vector equals the same forward averaging and transport flow obtained from the observed prefix. Applying the exact decrement in Lemma 4.1, with its available set equal to F_{t-1}, proves the displayed identity and transports the uniform comparison vector as stated.□

Proof. First fix the list, the complete schedule, and feasible complete trajectories of the preceding labels. Lemma 12.3 identifies the conditional mass on the left of (12.4) with the forward mass computed from the list, the direction prefix, and the observed path prefix through t. It is therefore already \mathcal F_t^{C,j}-measurable. The tower property, using \mathcal F_t^{C,j}\subseteq\mathcal H^{C,j}, proves (12.4).

Conditional on the complete schedule, the observed path prefix depends only on the direction prefix, by the product-switch hypothesis. Since the list is independent, its observation and that of the preceding paths do not change the next-direction law K_t. Also, the field generated by \mathcal F_t^{C,j} and v_{t+1} is contained in \mathcal H^{C,j}. Taking the tower of (12.4) to this intermediate field shows that the hidden mass remains p_t after v_{t+1} is revealed. Combining these two statements proves (12.5).□

Proof. Apply the energy calculation in Lemma 4.1 to the available set F_0\cup F_1 and the centered vector z. That proof uses only \sum_xz_x=0, not positivity of a probability vector. In its notation, take D^0=F_0 and D^1=F_1; the exact cross-pair loss is the displayed sum divided by n. When the forbidden subspace is smaller than J, every cross-coset difference remains allowed and has probability at least 1/n, instead of 2/n. Its averaging loss is still half the squared difference, giving the denominator 2n.□

Proof. The transverse-layer proof of Lemma 8.2 is uniform over the entire fixed direction schedule. It therefore applies here even though the first basis is prescribed. Explicitly, fix all directions and the observed-label configuration just before layer t-d. The direction at that layer crosses the cosets of J_t, because v_{t-d},\ldots,v_{t-1} form a basis. The following d-1 directions lie in J_t and preserve the two coset counts. If a crossing pairs contain two unobserved positions, one count after the crossing is a+\operatorname{Binomial}(m-2a,1/2). The conditional fair-coin law is unchanged by fixing the directions. The binomial tail from that lemma is at most 2e^{-m/8}; if m=2a the count is deterministic. Removing this conditioning proves the stated unconditional bound.

Equation (12.4) makes the energy vector measurable in the chronological field, and (12.5) permits averaging the next direction there. Lemma 12.5 then contracts energy by at least \alpha=1/(4r) whenever the two counts are at least m/4. We use the balance estimate only after taking expectations. Since 0\le E\le1,

Iterate from E_d\le1 and sum the geometric series. This proves (12.8) without asserting concentration conditional on the subsequently observed paths.□

Proof. Markov’s inequality and a union bound give the lost mass. For each complete direction schedule the law of L_T^{-1}Z_T is \mu, so restricting to \mathcal G_{\mathcal P} gives 0\le\nu\le\mu. For an order, its j-th energy event is measurable from all directions and the preceding paths. On it, every endpoint has conditional probability at most

To bound a specified list of distinct outputs intersected with \mathcal G_{\mathcal P}, first discard requirements belonging to other orders. Condition on all directions and the first q-1 paths, bound the final target on its own energy event, and then discard that event. Continue downwards through the list. Each remaining target event and energy constraint is measurable in the conditioning data at its turn. The target in variable coordinates is known because L_T is determined by all directions. We obtain

These output specifications are precisely the left cosets gK_i. Normalization costs 1/a, at most two eventually. The total-variation bound for \bar\nu follows from Lemma 11.3.□

Proof. Take d\ge5, which suffices for all block sizes in this proposition. For the first assertion take r=8 and T=512d. Equation (12.8) is at most n^{-12} for large d, since (31/32)^{511d}\le e^{-511d/32}. The exceptional mass is at most 8n\,n^6n^{-12}=o(1). Use the normalized law \bar\nu in Lemma 12.7 and the direct inverse-square estimate of Lemma A.2. Proposition 3.2, with p=2, gives \|\widehat{\bar\nu}(\rho)\|_{\rm op}\le\sqrt{32C_2}D^{-1/4}. Eight convolutions have Plancherel exponent 2-16/4=-2. The original block has unbiased sign because one independent switch already has fair parity; the normalized modification has sign mean o(1). Proposition 2.5 applies. Since T=512d is a whole number of coordinate sweeps, eight physical blocks give 8T=4096d.

For the second construction take r=32 and T=(1+80r)d. The first term in (12.8) is at most e^{-20d}\le n^{-20}, so the exceptional mass is at most 32n^7(n^{-20}+2e^{-n/256})=o(1). Keep the unnormalized subprobability, whose coset factor is K=2. The paragraph “Central-binomial powers eight and twenty” following Lemma A.5 in Subsection A.3 of [22] gives

Applying Proposition 3.2 of the same companion with p=8, K=2, and r=32 gives exponent -1/2+10/64=-11/32 and prefactor \sqrt{64C_8}. Sixteen convolutions leave exponent 2-32(11/32)=-9. The retained measure is dominated by the physical block law, whose sign mean is zero. Proposition 2.5, including its trivial and sign terms, therefore applies. Here T=2561d is again a whole number of sweeps, so 16T=40976d physical shuffles suffice.□

Proof. Start with the standard basis and generate directions by independent fair coefficients

Write \mathbf c=(c_{s,t}:d<t\le T,\ t-d<s<t) for the complete coefficient array. Conditional on this array, let Z_0=I and Z_t=\zeta_tZ_{t-1}, where the \zeta_t are independent uniform switches in directions v_t. This is the same conditional uniform-complement schedule as before. For each fixed \mathbf c, the frame comparison starts at L_0=I. Thus the distance for the fixed endpoint list is unchanged by the output relabeling, and equals the average over \mathbf c of the conditional auxiliary distance.

For later use, let

This field fixes the directions and the complete switch history through layer h. The conditional law of these switches uses only the directions through h, hence only coefficients with target time at most h. Coefficients with later target times therefore remain independent fair bits given \mathcal A_h.

Fix the input list a_1,\ldots,a_q, write Y_t(j)=Z_t(a_j), and let F_{j,t}=V\setminus\{Y_t(i):i<j\}, of size n_j=n-j+1\ge m. Define the chronological field

The conditional path law given \mathbf c depends only on its direction sequence. Equations (12.4) and (12.6), with \Lambda=\mathbf c, therefore identify the two versions of the hidden mass:

Put

Thus E_{j,t} is measurable in \mathcal F_{j,t}, even though its first definition uses the complete coefficient array and complete preceding paths. For t>d set J_t=\operatorname{span}(v_{t-d+1},\ldots,v_{t-1}). Say that step (j,t) is balanced if both its cosets contain at least m/4 members of F_{j,t-1}. Let \mathcal B_j(t) require this for all steps 2d,\ldots,t, with no requirement when t=2d-1. The event \mathcal B_j(t) is \mathcal F_{j,t-1}-measurable, before the direction at t is revealed. Equation (12.5) and Lemma 12.5, followed by \mathcal B_j(t)\subseteq\mathcal B_j(t-1), give

Thus, for \mathcal B_j=\mathcal B_j(T),

The events decrease as j increases because the hole sets shrink and the common threshold m/4 stays fixed.

The energy on the nested balance events is now controlled. It remains to estimate the probability that the smallest reservoir fails balance; this will be the only exceptional-event cost in the tuple comparison. Fix t\ge2d and write h=t-d. Let \ell_t be the unique linear form vanishing on J_t and taking value one on v_h. Given \mathcal A_h, this form is uniform among the forms with \ell_t(v_h)=1. Indeed use the past basis v_{h-d+1},\ldots,v_h. The equations \ell_t(v_{h+i})=0, 1\le i<d, give

Solve backwards from i=d-1 to i=1. At each stage the term c_{h,h+i}\ell_t(v_h)=c_{h,h+i} is a fresh fair bit, independent of the coefficients at later stages, of the other coefficients in the current equation, and of \mathcal A_h. This proves the uniformity claim.

For F=F_{q,h} put Z=\sum_{x\in F}(-1)^{\ell_t(x)}. The set F is \mathcal A_h-measurable, and \mathbb E[Z^2\mid\mathcal A_h]\le|F|=n_q: diagonal terms are one, off-diagonal terms with difference v_h are minus one, and every other off-diagonal term has mean zero. The directions at times h+1,\ldots,t-1 lie in J_t, so the coset counts from the post-step-h configuration to time t-1 are preserved. A count below m/4 forces |Z|>n_q-m/2\ge n_q/2. Chebyshev and a union bound give

We finish by coupling the endpoint lists, conditional on \mathbf c. Write \pi_q for the uniform injection law on q positions, and put

At stage j, prescribe the real endpoint kernel to be p_{j,T}, evaluated on the preceding real paths. This prescription is used for every joint coupling history; it is not replaced by a law conditioned on earlier coupling success. Prescribe the comparison kernel to be uniform on the positions not yet used by the comparison list.

On previous success the two lists have the same preceding endpoints, so their available endpoint sets agree. If \mathcal B_j holds, maximally couple the prescribed kernels, declaring failure if their endpoints differ. If balance fails, declare failure and use any coupling of them. Once a failure has occurred, continue using any coupling of the prescribed kernels, with the comparison list’s own remaining set. After choosing the real endpoint, sample its full real path from the conditional path law given that endpoint, \mathbf c, and the preceding real paths. These prescriptions preserve the real path law and the uniform comparison-list law at every stage. The probability of a balance failure before any mismatch is at most \Pr(\mathcal B_q^c\mid\mathbf c) by nesting. The mismatch probability on a balanced, previously successful stage is bounded by \tfrac12\sqrt{n_jE_{j,T}}. Averaging over \mathbf c and dropping the preceding-success indicator gives the total bound

by (12.11), (12.12), and Cauchy–Schwarz. The fixed-list frame comparison identifies the left side with the physical marginal distance, proving (12.9). Finally the exponential factor is at most e^{-5d/2}, so n^{3/2}e^{-5d/2}\to0, and T/m\to0.□

Proof. Use any fixed partition into sixteen equal blocks and apply Proposition 12.9 to its complements. Theorem 10.1 gives exponent a=1/8 with constant one. Sixteen convolutions have exponent 2-2(16)/8=-2. The original block has zero sign mean, and Proposition 2.5 applies to its pruned subprobability. The total number of physical steps is 16(322d)=5152d.□

Proof. The conditioned paths are feasible, because they come from g. Their complement at time t is exactly the set of available positions g_t(F). Lemma 12.3 gives the conditional mass flow on these positions. We express its three edge cases in the reference indices.

If a matching edge has one position in g_{t-1}(F), its coin is fixed by the path of the observed card on that edge. It is therefore the coin used by the reference history, and it carries the available position g_{t-1}(v) to g_t(v). Its mass keeps index v. If both endpoints belong to g_{t-1}(F), say with reference indices v,v', the two conditional output masses are the average of the preceding two masses. They are equal, so the reference history’s choice to swap or fix that edge does not change the two indexed output values. An edge with no available position has no coordinate in the row. These cases give r_t^{u,F}=r_{t-1}^{u,F}B_t^F. Initially card u is at u, so the initial row is e_u^{\mathsf T}. Iteration proves the row formula, and the index of the realized endpoint g_T(u) is u.□

Proof. We estimate the distribution of these matching functionals using the directly generated variable-direction process. Start its directions with the standard basis, and choose each later direction uniformly outside the span of its preceding d-1 directions. At each layer use fresh independent fair switch coins. Denote its cumulative permutation by \widetilde g_t. Lemma 12.2 says that, for each complete direction schedule, its matching sequence on trajectory labels has the same law as the cyclic matching sequence. Thus every functional Z_T^F of those matchings has the same law in the two models. For the following calculation, B_t^F, Q_t^F, and Z_t^F denote these same matrix functions evaluated on the auxiliary matching sequence.

Take F uniform of a fixed size m\ge n/L, independently of this auxiliary process. Condition on F, the directions through time t-1, and the complete switch history through that time. For a row of Q_{t-1}^F-J_F, write its entries as z_u, u\in F. This row is known under the conditioning and has sum zero. Transfer it to the current positions by

The label pairs averaged by B_t^F correspond exactly to the position pairs contained in \widetilde g_{t-1}(F) in the new matching. Thus the squared row loss is the position-space loss in Lemma 12.5.

For t>d, let J_t be the span of the preceding d-1 directions, and let h,h' be the sizes of \widetilde g_{t-1}(F)\cap J_t and \widetilde g_{t-1}(F)\setminus J_t. The next direction is fresh under the conditioning above. Applying the lemma to each row and summing gives

Now fix the generated past but leave F unobserved. The map \widetilde g_{t-1} and the half-space J_t are fixed, and \widetilde g_{t-1}(F) is a uniform m-subset. The elementary half-count estimate gives

For example, expansion of the product for a uniform sample without replacement gives \mathbb E2^X\le(3/2)^m for either half-count X; Markov’s inequality applied to the larger half yields this bound. Set c=-\log\theta>0. With Z_{t-1}^F\le n and m\ge n/L, the unconditional recurrence is

There are T-d=100Ld useful layers. Starting with Z_d^F\le n, the initial contribution is at most ne^{-25d} and the accumulated error is exponentially small in n. Hence \mathbb E Z_T^F\le n^{-20} for large d, uniformly in m.

The equality of matching laws proved at the start transfers this expectation to the cyclic histories on which \mathcal G_{\mathrm{ent}} was defined. For each m, Markov’s inequality applied to the subset average at threshold n^{-8} gives failure probability at most n^{-12}. There are at most n sizes, so \mathbb P(\mathcal G_{\mathrm{ent}}^c)\le n^{-11}=o(1).□

Proof. Fix an ordered list i_1,\ldots,i_q. Let \tau_j and y_j be the complete trajectory and endpoint of i_j. For the current history let p_j be the conditional probability under \mathbb P of its realized endpoint y_j, given \tau_1,\ldots,\tau_{j-1}. Relative-entropy chain rule and conditional data processing give

The second inequality uses that the preceding endpoints are functions of the preceding trajectories. Put F_j=V\setminus\{i_1,\ldots,i_{j-1}\} and m_j=|F_j|=n-j+1. The uniform injection assigns each endpoint list mass \prod_jm_j^{-1}, so the last inequality is

Lemma 12.11 applies with observed complement V\setminus F_j and gives p_j=Q_T^{F_j}(i_j,i_j) on each realized history. For a uniform ordered input list, F_j is a uniform subset of size m_j. The bound (12.15) is independent of which i_j\in F_j is chosen. On every history in \mathcal G_{\mathrm{ent}}, Jensen’s inequality therefore gives

All these sizes are at least n/L. Sum over q\le n indices and average the preceding entropy inequality over lists and over \nu. The induced set X is uniform of size q, and ordering its coordinates does not change its relative entropy from a uniform injection. This proves the claimed error n^{-2}.□

Proof. If a=\mathbb P(\mathcal G_{\mathrm{ent}})=0, the probability on the left side of (12.18) is zero. Otherwise apply the all-tilt coefficient theorem, [22, Theorem 11.1]. Its reference probability is the law \mathbb P of cyclic switch histories, its endpoint map is g_T, and its common event is \mathcal G_{\mathrm{ent}} from Lemma 12.12. Lemma 12.13 verifies the theorem’s hypothesis for every probability \nu supported on that same event, with q=n-n/128 and additive error n^{-2}. The theorem therefore gives the tail exponent 1/256=1/(2L) at threshold D^{-1/8}. For a>0, splitting each absolute coefficient at D^{-1/8} under \mathbb P(\,\cdot\mid\mathcal G_{\mathrm{ent}}) gives the stated operator bound with factor C/a. By Lemma 12.12, a=1-o(1), so a\ge1/2 eventually. Since L=128 and D\ge1, D^{-1/8}\le D^{-1/(2L)}, which gives C'=1+2C.□

Proof. For all sufficiently large d, put a=\mathbb P(\mathcal G_{\mathrm{ent}})>0 and \eta=\mathcal L(g_T\mid\mathcal G_{\mathrm{ent}}). The original block law \mu=\mathcal L(g_T) has zero sign mean, so

For the nonlinear irreducibles, Proposition 12.14 gives the operator bound with the absolute constant C'. The trivial coefficient of \eta^{*b} is one. Plancherel therefore gives

Indeed 2-b/L=-30, and the nonlinear sum vanishes by [22, Lemma A.1]. Cauchy–Schwarz gives total-variation convergence. The b independent histories all belong to \mathcal G_{\mathrm{ent}} with probability a^b. Removing their conditioning costs at most 1-a^b\le b(1-a)=o(1), because b is fixed. The physical block length is a multiple of d, and its b-fold product is the actual shuffle at time 32L(1+100L)d.□

Proof. Set A_i=B_i^{-1}. Since S_i is an involution, A_i=A_{i-1}S_i and w_i=A_{i-1}e_{\iota_i}, which are the forward frame and selected directions of Lemma 8.4. Remark 8.5 gives the inverse coupled identity X_i=B_iY_i and the conditional coordinate-switch law. The prefix product-switch law and consecutive-basis property are conclusions of that lemma for the same periodic axis order. The prefix law makes the old virtual path and the next direction conditionally independent given the direction prefix; Corollary 12.4 records the resulting hidden-position factorization after specified virtual path prefixes through layer i-1 are observed. The uniform-complement law for i>d is the lemma’s fresh-direction conclusion.

In particular, the conditional law of the full virtual trajectory given \Lambda depends on \Lambda only through W. Thus the trajectory and \Lambda are conditionally independent given W. Conditioning also on a fixed observed part of the trajectory preserves this factorization for the remaining trajectories.□

Proof. Lemma 13.2 gives the conditional product-switch law and the fresh direction in the field \mathcal F_{i-1}^j. Apply Lemma 4.1 with initial datum \mathcal O, t=i-1, available set D_{i-1}, and hidden mass q_{i-1}. Its averaging and transport rules preserve the uniform comparison law on the holes and give

In particular 0\le E_i\le E_{i-1}\le1 for every realization.

Suppose now that i>d. Before its direction is drawn, put J_i=\operatorname{span}(w_{i-d+1},\ldots,w_{i-1}) and split D_{i-1}=D^0\cup D^1 across its two cosets, with sizes h_0,h_1. Lemma 13.2 makes the next direction uniform outside J_i, so each cross pair has conditional matching probability 2/n. The cross-pair calculation in Lemma 4.1, with centered vector z_{i-1}, gives

The inequality is (4.6); it also covers an empty part.

We use a simultaneous balance estimate for every affine half-space. At a fixed time, condition on \Lambda and the complete virtual switch history but not on \mathcal O. The permutation Y_{i-1} is then fixed, and the independent ordering makes D_{i-1} a uniform m-subset of V. The simultaneous estimate below is valid even for a half-space chosen after that subset is seen.

For m<n, a uniform m-subset has the law of independent Bernoulli choices of parameter m/n, conditional on making exactly m choices. This conditioning event has probability at least 1/(n+1): m is a mode of the binomial distribution and that distribution has n+1 values. In a specified affine half-space let X be the unconditioned number of choices. It has mean m/2, and

where the last inequality uses \log2<3/4. There are fewer than 2n affine half-spaces arising as a linear hyperplane or its other coset. Since m\ge n/r, a union bound after conditioning gives

For m=n the balance assertion is deterministic.

On the complement of the event in (13.6), the conditional loss in (13.5) is at least mE_{i-1}/(4n)\ge E_{i-1}/(4r). On the exceptional event we retain the deterministic energy nonincrease and the bound E_{i-1}\le1. Taking expectations consequently gives

Only the unconditional estimate (13.6) has been used. Iterating over T-d=100rd layers, starting from E_d\le1, yields

□

Proof. For each j<k, the terminal factorization in Lemma 13.2 and (12.6) give

Thus the terminal-data hypothesis of Lemma 4.2 holds with initial datum \mathcal O and terminal datum \Lambda. Write

for the conditional virtual tuple distance. The lemma’s coarsening to preceding endpoints and sequential comparison, together with Lemma 13.3, give

For each fixed \Lambda and \mathcal O, applying B_T to every output preserves \pi_k and total variation. The conditional law of X_T given \Lambda is \mu, and the independent ordering contributes no further information about that law. Hence \delta_{\rm virt}(\Lambda,\mathcal O) equals the distance under \mu for the specified list C. Averaging proves (13.7). Finally, n=2^d gives n^{3/2}e^{-25d/2}\to0, while \delta_n is exponentially small in n up to a polynomial factor. Hence \varepsilon_n=o(1).□

Proof. The proof of Lemma A.1 bounds the complete inverse-twentieth sum by K_0. Apply Proposition 3.2 with p=20, K=2, and r=128. That proposition assigns a component v_i of a given vector to the small H_i-types and sets W_i=\operatorname{span}\{\rho(h)v_i:h\in H_i\}. Its orbit bound is

The sum counts each irreducible subgroup type once: the orbit of a fixed vector in all copies of a type of degree f has dimension at most f^2. Combining this estimate with the coset cap and Schur averaging in that proposition gives \sqrt{2rK_0}D^{-1/2+11/r}.□

Proof. For d\ge4, put m=n/16, T=513d, and \mu=q_d^{*T}. Corollary 9.3 gives \mathbb E_{|A|=n-m}\|\mu_A-U_A\|_{\TV}\le\varepsilon_n=o(1). In a uniformly chosen ordered partition (M_1,\ldots,M_{16}) into sets of size m, each complement V\setminus M_i is uniform. Hence the expected sum of the sixteen complementary errors is at most 16\varepsilon_n, and some partition has sum at most this value.

For that partition, the restriction to V\setminus M_i identifies the left coset gH_i. Delete the union of all cosets whose original \mu-mass exceeds twice uniform. The calculation in the proof of Lemma 5.1 gives a common subprobability f\le\mu of mass z=1-\eta, with \eta\le32\varepsilon_n=o(1), such that f(gH_i)\le2/[G:H_i] for every g,i. Equation (14.1), with z\le1, therefore gives \|\widehat f(\rho)\|_{\HS}^2\le32C_2D^{-3/4}. Hilbert–Schmidt submultiplicativity yields

The trivial coefficient of f^{*4} is z^4. Lemma 7.2 gives |\widehat f(\sgn)|\le\eta, since the original block has sign mean zero. Plancherel and (14.2) now imply

Cauchy–Schwarz gives \|f^{*4}-z^4U_n\|_1=o(1). Positivity gives f^{*4}\le\mu^{*4}, and their mass difference is 1-z^4=o(1). Consequently

The four independent physical blocks have total length 4T=2052d and law \mu^{*4}=q_d^{*(2052d)}. Equation (2.2) gives the stated maximum over starts.□

Proof. For sufficiently large d, in particular d\ge4, set T=2049d, \mu=q_d^{*T}, and K=P_d^T. The identity K(g,z)=\mu(zg^{-1}) shows that K is doubly stochastic and that it commutes with the right action of every label permutation. A uniform source state in X_i places the specified labels outside M_i at a uniform injection. Their output law is the quotient row p_i(x,\cdot), so Corollary 9.3 gives

Choose \epsilon=n^{-1} in (14.3). A removed quotient atom has positive excess over uniform at least \epsilon/(1+\epsilon) times its mass. Thus the mean mass removed is

Each T_i is row- and column-substochastic because 0\le T_i\le K. Moreover H_i is normal in H, and right equivariance gives p_i(xh,yh)=p_i(x,y) for h\in H. The cutoff therefore preserves the action of the whole product H.

We now verify the sign condition with its full multiplicity. Fix i and choose a deck g_x in each fiber x\in X_i. For a,b,c\in H_i, put w_{xy}(c)=T_i(g_x,g_yc). Right equivariance gives

On fiber x, define the normalized sign vector by \phi_x(g_xa)=\sgn(a)/\sqrt{m!}, and set it to zero off that fiber. Each fiber is a regular H_i-set, so these L orthonormal vectors span the full sign isotypic space of \ell^2(G). In this basis the multiplicity operator has entries

Suppose the ignored positions in x contain a matched pair of the first physical shuffle, and let s be its position transposition. Then \tau=g_x^{-1}sg_x\in H_i is an odd transposition and g_x\tau=sg_x. In the first physical step RS, the switch S is uniform in C_{e_1}. Since s\in C_{e_1}, one has Ss\stackrel{\mathrm{law}}=S. The first-step laws from g_x\tau and g_x are therefore identical, and so K(g_x\tau,z)=K(g_x,z) for every output deck z. The cutoff depends only on the source and target quotient states, so the same identity holds for T_i. Right equivariance now gives

Since \sgn(\tau)=-1, the signed sum in (14.4) is its own negative. Every outgoing sign coefficient from this fiber is zero.

For a uniform fiber x, its ignored positions form a uniform m-subset of V. The fraction of these sets containing no full first-layer pair is

After j positions have been sampled without a partner, exactly j partners are forbidden among the n-j remaining positions. The product follows, and \log(1-u)\le-u gives the exponential bound. Only these La_{n,m} fiber rows can contribute to the sign matrix. For each such row the quotient cap gives

Consequently the squared Hilbert–Schmidt norm on the entire sign multiplicity space is

Here m=n/16\to\infty and \delta_n/\epsilon=n^{-9}\to0. The companion theorem therefore gives mean row error o(1) for K^{16}. The right action of all label permutations is transitive on decks and commutes with K, so every row has the same error. Finally K^{16}=P_d^{16T} and 16T=32784d, proving the assertion.□

Proof. For sufficiently large d, in particular d\ge10, set b=1024, T=(1+32b)d, and \mu=q_d^{*T}. Corollary 9.3, in the set form established at the start of this section, gives the displayed hypothesis with \delta_n=o(1). Let \nu be the resulting nearby probability. Lemma 7.2 gives |\widehat\nu(\sgn)|\le2\|\nu-\mu\|_{\TV}=o(1). For eight factors, Plancherel and \|A\|_{\HS}\le\sqrt D\,\|A\|_{\op} give

using (14.2); the nonlinear exponent is 2-16(1/4)=-2. Replacing the eight factors one at a time costs at most 8\|\nu-\mu\|_{\TV}=o(1). Thus \mu^{*8} converges to uniform. These physical blocks have total length 8T=8(1+32\cdot1024)d=262152d, so \mu^{*8}=q_d^{*(262152d)}. Equation (2.2) gives the same error from every start.□

Proof. Proposition 8.3 covers every periodic ordering of the standard axes, including every starting phase, and the inverse product obtained by reversing independent involutive layers. With its omitted-block parameter equal to 2 and time T=100d, it gives, for \eta=\pi or \eta=\pi^{-1},

where \pi_q is the uniform ordered injection law. The fixed-list estimate uses the hidden-card vector from the chronological field (4.1). The terminal comparison uses (4.9) with \Lambda=\mathbf v, disclosing the complete schedule and only the complete predecessor paths.

For the independent shear realization of the coordinate chain, (8.13) gives the local block identity

Here Q_t are the original coordinate layers and M_t the virtual layers coupled to them. Conditional on the independent shears, the M_t are independent uniform matching switches. The known terminal B_L relabels only final positions, so the specified input list is unchanged. Equation (8.11) identifies its virtual terminal posterior with its chronological vector after all shears are disclosed. The independent shear realization starts with B_0=I; the general first-basis realization retains the input map L_0^{-1} from (3.9).□

Proof. Let Y' be an independent copy and put u=(Y')^{-1}Y. Independence and unitarity give

If f counts the fixed points of u, then, for 1\le k\le b,

Indeed, condition on Y' and prescribe Y(x)=Y'(x) at a chosen set of k inputs. Each input-output pair determines one route because each coordinate is updated once. A consistent family of routes visits at least hk/2 distinct switch bits: a switch serves at most two routes. It therefore has probability at most 2^{-hk/2}=b^{-k/2}. A union bound over the input set proves (15.5).

Write D=D_\alpha. The assertion is immediate for D=1. For D>1 set

Since D^2\le b!, one has \kappa\le b/4, so k\le b for large b. For k\ge b^{9/10} and sufficiently large b,

Outside an event of probability at most D^{-1/8}, therefore, f\le b^{9/10} or f\le\kappa. The first case is covered by (15.3). In the second, restrict \rho_\alpha to the symmetric group on the b-f moving points. Every irreducible constituent of degree E satisfies

For the first inequality, translates of one constituent subspace by coset representatives span a nonzero S_b-invariant subspace and hence the whole irreducible representation. Since f\le\kappa\le b/4, the moving-point group has size tending uniformly to infinity. The permutation has no fixed points there. Applying (15.3) to each constituent and averaging with its dimension weight, including multiplicity, bounds the normalized character by D^{-1/100}. On the exceptional event use the bound one. Thus the normalized trace is at most D^{-1/100}+D^{-1/8}\le2D^{-1/100}.□

Proof. For a permutation of m points with at most m^{4/5} fixed points, one has e_1\le4/5 and hence E(g)\le9/10. Applying (15.2) with slack 1/20 yields

for all sufficiently large m, uniformly in g and \alpha.

Let G_s' be an independent copy, put u=(G_s')^{-1}G_s, let f count its fixed points, and write D=D_\alpha. As in the preceding trace calculation, q_\alpha=\mathbb E\chi_\alpha(u)/D. The case D=1 is immediate. When f\le s^{4/5}, (15.6) bounds the absolute normalized character by D^{-1/20}. Suppose instead that

Since D\le s!\le s^s, one has \kappa\le s/2 and hence f\le s/2 in this case. The moving-point group therefore has size tending uniformly to infinity. Iterated Young branching [11, Theorem 9.2] expresses the restriction to that group as at most s^f irreducible summands counted with multiplicity. If their degrees are E_1,\ldots,E_r, then \sum_jE_j=D. The permutation is fixed-point-free on this group. Applying (15.6) there and using concavity gives

For the remaining event take k=\lfloor\max\{s^{4/5},\kappa\}\rfloor+1, which lies in [1,s] for large s. The unique-route tail (15.5), with s in place of b, gives for large s

The normalized trace is consequently at most D^{-1/40}+D^{-1/10}\le2D^{-1/40}. This proves the stated existence with the distinct branching conclusion a=1/40 and C_1=2.□

Proof. Restrict to the elementary abelian subgroup generated by a fixed matching of n/2 transpositions. If every constituent assigns the same sign to all these generators, their representing matrices are equal. Conjugation then makes any two disjoint transpositions have equal matrices. A third transposition disjoint from two overlapping ones exists when n\ge6, so all transpositions have the same matrix. The image is generated by one involution, and irreducibility gives the trivial or sign representation. Otherwise a constituent assigns negative sign to exactly r generators, with 1\le r\le n/2-1. The normalizer permutes the matching pairs, so all \binom{n/2}{r}\ge n/2 reordered characters occur. Their eigenspaces are linearly independent.□

Proof. Let G_j be the symmetric group supported on J_j and put H=G_0\times G_1. If a positive operator Q commutes with \rho(G_{1-j}), then \rho(\pi)^*Q\rho(\pi) is determined by Q_j(\pi). Indeed, equal ordered preimages of J_j mean \pi'\pi^{-1}\in G_{1-j}. The separate marginal cap and positivity therefore give, for every unit vector v,

The final equality is Schur averaging. This comparison uses one capped preimage marginal at a time; it imposes no joint density bound.

Set A_j=\mathbb E\rho(\sigma_j) and A=A_0A_1. These factors and their adjoints commute, and they are contractions. Independence and convexity give

For each j, let P_{j,\le} select the full G_j-isotypic spaces of degree at most D^{1/100}, and put P_{j,>}=I-P_{j,\le}. These projections commute with H and with each other. On a joint half-type, write X_j=A_j^*A_j. The X_j are positive contractions on separate tensor factors. If type j is large, X_0X_1\preceq X_j; if both types are small, X_0X_1\preceq I. Hence

Every term is positive. The first two commute with the complementary half group, and the last commutes with both groups, so (15.7) applies to each.

On each G_j-type selected by P_{j,>}, Lemma 15.3 bounds the normalized trace by 2D_\alpha^{-1/100}\le2D^{-1/10000}. Averaging with the restriction dimension weights, including all multiplicities, gives

It remains to bound the fraction of the space on which both half-types are small. If m_{\alpha\beta} is the multiplicity of \alpha\otimes\beta in \rho|_H, then

By Frobenius reciprocity [8, Theorem 4.33], m_{\alpha\beta} is the multiplicity of \rho in W=\operatorname{Ind}_H^{S_n}(\alpha\otimes\beta), so m_{\alpha\beta}^2\le\dim\operatorname{End}_{S_n}(W). Realize W in fibers of dimension D_\alpha D_\beta over S_n/H. An equivariant block map at one representative ordered pair of cosets determines its transported maps on that pair orbit. The stabilizer can impose linear constraints on the representative map and can only reduce the number of choices. Cosets correspond to b-subsets, and intersection size classifies their ordered-pair orbits, of which there are b+1. Each representative map has at most (D_\alpha D_\beta)^2 parameters. This proves (15.11).

The complete inverse-first sum gives

Lemma 15.5 gives b\le D. Therefore

Equations (15.7)–(15.12) bound the squared operator norm by 16D^{-1/10000}+O(D^{-1/2+6/100}). Taking square roots proves the stated exponent. Finally, the pass \sigma contains an independent fair switch for large d. Toggling it changes sign, and its independence from the modified \pi gives zero sign coefficient for the block.□

Proof of Theorem 15.1. Take r=60000 successive blocks, modifying their long segments independently. The product law \mu differs from the unmodified product by at most r\,o(1)=o(1). The block phases may differ, but the estimates are uniform. Their Fourier matrices multiply in chronological order, and Proposition 15.6 gives

The sign coefficient is zero. Plancherel, the Hilbert–Schmidt inequality, and Lemma 15.5 yield

Restoring the modified segments still costs o(1).

The unmodified coordinate product has t=60000(101d-1) layers and equals R^{-t}Y_t in the notation of Section 3. Restoring the one terminal rotation preserves uniform measure and total variation even when t is not divisible by d. A deterministic initial deck is a right translate, so it has the same distance. Since t\le6060000d, the upper bound follows. The lower bound is the earlier one-card or support lower bound.□

Proof. Write S=(S_1,S_2) for an output partition and p,u for its actual and uniform laws. For fixed S, a permutation is a pair of bijections J_i\to S_i. Let \mu_S be their conditional joint law, with marginals \mu_{i,S}, and let U_{i,S} be uniform on the ith bijection space. Either injection determines S completely. The uniform injection law has partition marginal u and conditional bijection law U_{i,S}. Replacing u by p in this target changes it by exactly \epsilon_{\mathrm{part}} in total variation. The triangle inequality therefore gives

For every S with p(S)>0, take a maximal coupling of \mu_{i,S} with U_{i,S} for each i. Given the original pair, apply the two coupling kernels using separate auxiliary randomness. Each resulting coordinate has its prescribed uniform marginal. The probability that the pair changes is at most the sum of the two marginal coupling errors. Thus replacing the conditional joint laws while retaining p costs at most \epsilon_1+\epsilon_2+2\epsilon_{\mathrm{part}}. On partitions of zero p-mass choose any joint law with uniform marginals. Finally replace p by u, retaining these conditional joint laws. This costs exactly \epsilon_{\mathrm{part}} and proves (16.1).□

Proof of Theorem 16.1. Choose C from the shared half-list lemma and a fixed positive integer K with K\delta>3. Take K successive blocks, repairing each A_0 independently. The phases and omitted coordinates may differ, but the estimates above are uniform over these choices. Let \mu be the product law of the repaired blocks. Its Fourier matrix is a product of K matrices satisfying (16.6). Using submultiplicativity of the operator norm and \|Q\|_{\mathrm{HS}}\le\sqrt D\|Q\|_{\mathrm{op}}, Plancherel gives

Indeed 2-K\delta<-1, and the inverse-first-degree sum outside the trivial and sign representations tends to zero. The sign term vanishes exactly. This estimate uses no normality of the Fourier matrices.

Undoing all K repairs costs o(1) by coupling the independent blocks, since K is fixed. Their original total length is K((d-1)+Cd) coordinate layers. At that single terminal time, the relation Y_t=R^tX_t from Section 3 restores the deterministic coordinate rotation. It preserves uniform measure and total variation, whether or not the block length is divisible by d. Each coordinate layer represents one physical shuffle. Finally, applying the position permutation to any fixed deck is a bijection of the state spaces, so the same convergence holds with the stated worst-start quantifier.□