Conditional coordinate sweeps and analytic transfer

1 Introduction

Revealing the paths of selected cards can separate a shuffle’s remaining randomness into local choices, but it also changes the law of those choices. In an ordered coordinate sweep, conditioning still separates by coordinate lines; each residual choice is a bijection between the slots left free by the prescribed paths at that stage. This paper controls the entire remaining bijection while retaining the exact cost of prescribing distinct positions without replacement. That cost makes the estimate stable when further card paths are revealed during the proof.

Fix a positive integer d and put N=2^d. A binary coordinate sweep acts on the slots \{0,1\}^d. In each coordinate direction it independently fixes or swaps the two cards on every parallel edge, with probability 1/2 each, and visits the coordinates in order. Write B_N for its law. One card is uniform after a sweep, but the joint permutation retains dependence because cards can use the same switches.

The physical model comes from Thorp’s study of nonrandom shuffling and Faro [15]. Split a deck into equal halves, pair corresponding cards, and use an independent fair coin to order each pair before interleaving. On binary position strings one physical Thorp shuffle is

where addition is modulo two and the bits \xi are independent and fair. Undoing the deterministic coordinate rotation makes successive switch layers act in successive coordinate directions. After d physical shuffles the rotation is the identity, so one binary sweep costs exactly d physical steps; see also Morris [9, Section 1.1] for the coordinate representation.

Let q_d be the law of one physical step and U_N the uniform probability on S_N. We use

Translation by a deterministic initial deck preserves the distance to uniform, so this definition is the same for every deterministic initial deck.

For the irreducible unitary representation \rho_\lambda of S_N indexed by \lambda\vdash N, put

The binary consequence of our argument is the following dimension bound.

The number of random bits supplies a matching lower bound in order.

Theorem 1.1 and Proposition 1.2 give t_{\rm mix}(d)=\Theta(d) in physical shuffle steps. In each fixed dimension, convergence also holds. A sweep can be the identity or any single cube-edge transposition with positive probability, and the edge transpositions of a connected graph generate S_N. Padding products with identities therefore gives a power of the sweep law with full support. Its positive minimum probability gives a uniform minorization and convergence by iteration.

1.1 Earlier work

Morris’s July 2005 author version, published in journal form in 2008, gave the polynomial upper bound O(d^{44}) physical shuffles for N=2^d cards [9]. Montenegro and Tetali sharpened this to O(d^{29}) [8]. Morris then obtained O((\log N)^4) physical shuffles for every even deck size N [10], followed by O(d^3) for power-of-two decks [11].

Earlier analyses already use information revealed about card motion. Morris’s chameleon identity represents a tagged-card law conditioned on the trajectory of an unordered occupied set [9, Section 4, Lemma 3]. In his later entropy proof, complete labeled trajectories in two coupled runs of the reverse Thorp shuffle are exposed successively, and the expected entropy changes are summed to obtain contraction after d physical shuffles [11, Section 4, proof of Lemma 7]. Morris, Rogaway and Stegers analyze selected-card Thorp marginals by averaged conditional one-card bounds and a coupling along the evolution [12, Section 3 and Appendix A, Lemma 2]. Hoang, Morris and Rogaway use a related conditional squared-discrepancy calculation for the distinct swap-or-not shuffle [7, Section 3, proof of Theorem 3 and Lemma 4].

Czumaj and Vöcking also studied partial Thorp permutations through non-Markovian coupling. For dyadic decks and each fixed 0<\varepsilon<1, their result gives nearly uniform joint positions for a fraction 1-\varepsilon of the labeled cards after O(d^2) physical shuffles [4]; equivalently, O(d) complete coordinate sweeps [3, Section 1.5]. That result concerns the endpoint law of selected cards after repeated binary sweeps. Our conditional theorem concerns the entire residual bijection for each feasible fixed family of paths under line laws close to uniform.

The representation ingredients are classical branching, Pieri’s rule, the hook-length formula, and ordinary Schur–Weyl duality [13, 14]. The signed tensor action and its hook support belong to the hook theory of Berele and Regev [1]. Positive domination by mixtures of tensor powers also underlies the postselection method of Christandl, König and Renner [2]. We derive the quantitative signed projection estimate needed here from the ordinary Schur–Weyl sectors. The analytic ingredient is the classical subharmonic maximum principle; Section 7 gives the local barrier argument.

1.2 The conditional estimate and the proof

The main conditional input is Theorem 3.1. It treats an ordered product grid whose coordinate sizes lie in a fixed interval [R,R^2] of powers of two. On a coordinate line of size m, the law is a mixture (1-z)U_m+zB_m of a uniform permutation and a binary sweep. The theorem holds on a small real interval 0\le z\le z_*, where these line laws are uniformly comparable to U_m.

In one ordered sweep, a card’s input and output determine its whole path: after stage j, the first j coordinates have their output values and the remaining coordinates still have their input values. On the small real interval, a prescribed family is feasible exactly when these forced paths occupy distinct slots at every layer. The conditional theorem bounds a Schatten moment of the remaining random bijection, in every irreducible representation, for each such family. Its bound has a negative term proportional to the logarithm of the representation dimension, an allowance for the number of prescribed cards, and a negative correction for sampling their positions without replacement. On a line of size m with u prescribed assignments, this correction is \log(m^u/(m)_u), where (m)_u=m(m-1)\cdots(m-u+1) and (m)_0=1. For a prescribed family \mathcal H, let C(\mathcal H) be the sum of these corrections over all stage lines.

The correction is the invariant that permits more paths to be revealed. When a placement of additional cards augments \mathcal H to \mathcal H^+, its transition probability is bounded using the difference C(\mathcal H^+)-C(\mathcal H) of the summed line corrections. Later, branching realizes the removal of boxes from a Young diagram by recording such additional placements. A cyclic trace expansion and Hölder’s inequality use that difference to return the original -C(\mathcal H) after the placements are summed. Because these fibers carry augmented path constraints, the induction must hold simultaneously for the conditioned laws.

The proof first treats sparse representation levels: types that first appear when only a short list of cards is tracked, together with their sign twists. Alternating the placement probabilities over subsets of the list cancels any tracked path whose stage lines are untouched by all other tracked or prescribed paths. With many coordinates, a count using rooted forests makes it unlikely that every tracked path shares a line. With a bounded number of coordinates, lines are larger and this count is too weak. At z=0, an inverse-gamma moment identity expresses the falling-factorial ratios as expectations. A tracked path may now share lines: if it shares no layer slot with another tracked or prescribed path, and the number of tracked and prescribed paths using each of its lines is a small fraction of that line’s size, alternation produces small differences of the line factors. Factors from particles sharing a line are grouped before their moments are bounded. Once R is fixed, only finitely many grids have this bounded number of coordinates, so continuity extends the estimate to a common small real interval.

To handle the remaining types of large dimension, choose p and first prove an auxiliary estimate for every diagram whose boxes lie in the first p rows or the first p columns, uniformly over all admitted path families on the current grid. Split the coordinate list into two blocks and regard the grid as a rectangle: the first block sweeps within rows, and the second within columns. At their junction the prescribed paths have removed some sites. In the signed tensor representation, each row or column isotypic projection is bounded by a controlled multiple of a probability mixture of tensor powers of positive trace-one matrices. Averaging the chosen row matrices supplies a trace-one reference matrix for bounding the overlap of the row and column projections on the free sites. The child moment estimates then cancel the cost of the subgroup dimensions in that overlap, leaving a strengthened estimate for the full hook type with the same trajectory correction. Finally, adding the boxes outside the hook creates the additional path fibers described above. Branching supplies a factor equal to the dimension of the removed diagram; together with the remaining dimension saving, this pays for the extra paths.

We then set \mathcal H=\varnothing. The unconditioned sweep operator is a matrix polynomial in z, and the conditional theorem gives a dimension saving on a short real segment. For the finitely many allowed line sizes, the binary line averages have a strict norm gap away from their invariant vectors. This bounds the full polynomial operator by one on a complex disk of radius greater than one. Applying the subharmonic maximum principle to scalar matrix coefficients on the disk with the segment removed transfers the dimension saving to z=1, where the sweep is binary. Finite-group Fourier analysis then gives the fixed number of sweeps in Theorem 1.1.

Section 2 fixes the representation conventions. Section 3 defines the conditional law and states its moment bound. Section 4 proves the sparse estimate, and Section 5 constructs positive tensor densities for the signed action. Section 6 combines these inputs and completes the moment induction by adding trajectory constraints. Section 7 carries the unconditioned estimate to the binary sweep and proves the mixing consequence.

2 Representation facts and normalization

A permutation sends each input position to its output, and a product gh applies h first. Thus convolution is the law of composition, and

We use ordinary, unnormalized matrix traces: \|A\|_p^p=\Tr|A|^p, where |A|=(A^*A)^{1/2}.

The group acts on slots, meaning positions for cards. A random bijection between two slot sets of the same size becomes a random permutation after identifying each set with a fixed reference set. Changing either identification multiplies its average in a unitary representation by unitaries on the two sides, so its singular values do not change. We will use this convention when prescribed paths leave different free slot sets at successive layers.

All representations are over \mathbb C. For a partition \lambda\vdash l, write [\lambda] for the irreducible representation of S_l, D_\lambda for its dimension, and F(\lambda)=\log D_\lambda. The empty diagram, for l=0, has dimension one. All logarithms in the proof are natural. We use the following classical representation facts.

• •

  The dimension D_\lambda is the number of standard tableaux of shape \lambda, given by the hook-length formula. Conjugating the diagram, denoted by \lambda', twists the representation by sign. For 0\le j\le l, on restriction to S_{l-j} the multiplicity of [\sigma] is the number of standard tableaux of the skew shape \lambda/\sigma when \sigma\subseteq\lambda, and is zero otherwise. These are the branching and tableau rules; see Sagan and Stanley [13, 14] and Vershik–Okounkov [16, Theorem 5.8 and Corollary 7.1]. In particular, the representation on placements of j distinguishable cards in l slots contains [\lambda] exactly when \lambda_1\ge l-j.

• •

  Pieri’s rule says that inducing with a trivial representation adds a horizontal strip, while inducing with a sign representation adds a vertical strip [13, 14].

• •

  In ordinary Schur–Weyl duality, for integers p\ge1 and t\ge0, the S_t-types in (\mathbb C^p)^{\otimes t} are the partitions \sigma\vdash t with at most p rows. Their multiplicity spaces are the polynomial irreducibles of highest weight \sigma for the commuting linear group action [13, 14]. Section 5 uses this decomposition separately on two parity classes and records the quantitative multiplicity and weight estimates there.

The induction separates representations close to a row or column from those with exponentially large dimension. For large l, put

If 0<k\le l/3, then

Indeed, after transposing if necessary, the first row has length l-k. Let \mu be the diagram of k boxes below it. The hook formula gives

Only j\le k can contribute a nontrivial factor. Since \sum_j\mu'_j=k, the product is at least \exp(-k/(l-2k))\ge e^{-1}, proving (1).

If k>l/3, then

for an absolute c_{\rm dim}>0 and all large l. If both the first row and first column have length below l/8, every hook is shorter than l/4, and the hook formula with Stirling’s bound gives this conclusion. Otherwise transpose if needed so that the first row has length v\in[l/8,2l/3]. Retain that row and a subdiagram of \lfloor v/4\rfloor boxes below it. The preceding large-row bound makes the dimension of this retained shape exponential in v, and hence in l. Branching shows that D_\lambda is at least that dimension.

Reducing c_{\rm dim} if necessary, these estimates imply F(\lambda)\ge c_{\rm dim}k for every k. Conversely the placement criterion, with a sign twist if necessary, places [\lambda] inside a representation of dimension (l)_k\le l^k. Thus

for large l. These are the bounds used to enter the sparse range; (1) also controls the sum over representations in the final mixing argument.

3 Prescribed trajectories and their cost

Fix a power of two R\ge2, to be chosen sufficiently large. Let \Omega=\Omega_1\times\cdots\times\Omega_b be an ordered product grid with b\ge1, where m_j=|\Omega_j| is a power of two in [R,R^2], and put s=|\Omega|=\prod_jm_j. Each \Omega_j is identified with \{0,1\}^{\log_2m_j}. A sweep first permutes the lines parallel to coordinate 1, then those parallel to coordinate 2, and so on, independently on all lines. A line always belongs to its particular stage.

On a line of size m, use

where U_m is uniform on the permutations of that line and B_m is a binary sweep on its \log_2m bits. Both laws send each individual slot to a uniform slot. Both also have expected sign zero: for B_m, toggling one of its independent fair switches reverses the sign. At z=1, the full grid sweep is the binary sweep with consecutive bits grouped into these coordinates.

Until the analytic argument, z is real, nonnegative, and small. For the fixed R, let

where m ranges over the allowed line sizes. There are finitely many such sizes, so z_{\rm cmp}(R)>0. For 0\le z\le z_{\rm cmp}(R),

as measures.

The order of the coordinates determines a path from its endpoints. If a card starts at u=(u_1,\ldots,u_b) and ends at v=(v_1,\ldots,v_b), then its slot after stage j must be

We may therefore prescribe a family \mathcal H of h such paths. We require their slots to be distinct at every layer, including input and output. These occupied slots will be called holes. For a stage line L of size m, let h_L count the prescribed paths using it, and let E_L(\mathcal H) be the event that the line permutation realizes their assignments from input to output. Layer disjointness makes these assignments injective, and (3) makes E_L(\mathcal H) have positive probability. The conditioning event is the intersection of these events over independent lines. Thus the residual line laws are the original laws L_m(z) conditioned on their prescribed assignments, and they remain independent. Each acts as a random bijection between the unoccupied input and output slots of its line.

Put M=s-h. After the paths in \mathcal H are removed, the sweep gives a random bijection between the M remaining input and output slots. For \lambda\vdash M, let K_\lambda^{\mathcal H} be its average in [\lambda], using any fixed identifications of the two slot sets as in Section 2.

For an integer 0\le u\le m, define the line cost

and set

The summands in \phi_m(u)=\sum_{r=0}^{u-1}\log(m/(m-r)) are nonnegative and increasing. For u\ge1, their mean over the first u terms is at most their mean over all m terms, which is at most one because m!\ge(m/e)^m. The case u=0 is immediate. Hence 0\le\phi_m(u)\le u, and

since the h_L sum to h at each stage.

For a nonnegative integer t, a placement of t distinguishable cards is an injection from [t]=\{1,\ldots,t\} into the available slots; for t=0 there is one empty placement. Let x,y be placements in the remaining input and output slots, and write p_{\mathcal H}(x,y) for their conditional transition probability. If this probability is positive, the endpoint pairs determine additional paths that, together with \mathcal H, form a disjoint family \mathcal H^+ of size h+t. Let v_L count the added paths on line L, so h_L+v_L\le |L|. Figure 1 shows how a prescribed path and an added path can share a line while occupying distinct slots at every layer.

On a line used by the added paths, with m=|L| and v=v_L>0, the conditional probability is

Indeed the corresponding uniform ratio is exactly (m-h_L)_v^{-1}; (3) changes its numerator and denominator by factors between 1/2 and 2. The uniform ratio records the increment of the line cost:

Unused lines contribute one, and at most tb lines are used. Each added path contributes \prod_jm_j^{-1}=s^{-1}. Multiplying the line bounds gives

The difference of potentials is the part of this estimate that permits further paths to be revealed during the induction.

For a positive integer q to be fixed, define the unnormalized Schatten moment

For \mathcal H=\varnothing, the estimate is T_\lambda^\varnothing\le D_\lambda^{-c(s)}; Section 7 uses this estimate for small real parameters in the analytic transfer. For general \mathcal H, the term -C(\mathcal H) is retained because (4) expresses the cost of prescribing additional paths as a difference of potentials. Section 6 uses that difference to recover the original potential after summing over the added placements.

4 Contraction at sparse representation levels

We now contract an irreducible that first appears on a short list of cards, even after a comparable number of trajectories has been prescribed. The row case uses an alternating placement kernel. The column case uses the same placement representation twisted by sign.

5 Positive tensor densities for hook diagrams

The sparse estimate settles small representation dimensions. For the remaining diagrams, the induction will compare row and column symmetry on a rectangle with holes. We construct positive tensor densities that dominate the projections for hook diagrams. Their trace-one normalization will permit that comparison even after sites have been removed.

Let p\in[1,s] be an integer and let V=E\oplus O, where E and O each have dimension p. On V^{\otimes l}, l\le s, let S_l permute the slots with signs: interchanging two neighboring odd factors (vectors in O) incurs a minus sign, and the other neighboring interchanges do not. On parity-homogeneous tensors the sign is therefore the sign of the induced reordering of the odd factors. This defines a unitary action. An even density is a positive semidefinite operator on V of trace one that is block diagonal for E\oplus O.

The signed tensor action and its hook support are classical in the hook theory of Berele and Regev [1]. Positive domination by mixtures of tensor powers also underlies the postselection technique of Christandl, König and Renner [2]. We derive the needed signed form from ordinary Schur–Weyl sectors, keeping the irreducible dimension D_\alpha explicit.

When sites are partitioned into blocks, signed unitary reordering makes the action of their product subgroup a tensor product. Applying (14) in each block therefore gives products of densities constant within the blocks. Each density is even, so undoing the signed reordering carries this to the ordinary tensor product with its sites relabeled. In particular, a constant tensor power of an even density commutes with the full signed symmetric-group action.

6 The conditional moment induction

We prove Theorem 3.1 by induction on the number b of coordinates, simultaneously for every allowed grid, path family, and representation. First fix the constants in the order required by the sparse estimate. Take \theta=a/16 and K_0=10/e_0 in Lemma 4.1. Its exponent \rho is uniform for sufficiently large R, so we may next choose an integer

and only then choose a sufficiently large power of two R. Every largeness requirement below will hold uniformly for s\ge R. In particular, require

Since b\le\log s/\log R and C(\mathcal H)\le bh, these choices give

Further increases of R will absorb the displayed errors below. After R is fixed, choose z_*>0 small enough for (3), Lemma 4.1, and the base case.

Every conditional average is a contraction. Thus when F(\lambda)=0, its moment is at most one and the nonnegative allowance above proves the theorem. This covers the empty diagram, M=1, and all one-dimensional types. A zero moment satisfies the bound by the convention \log0=-\infty.

For b=1 and z=0, conditioning on the prescribed assignments leaves a uniform bijection of the remaining slots. Every nontrivial average is therefore zero. Once R is fixed there are only finitely many one-coordinate grids, path families, and representations, and their conditional operators are continuous at zero. Decreasing z_* gives the base case on a common interval.

Now assume b\ge2 and the theorem for fewer coordinates. The contraction bound gives T_\lambda^{\mathcal H}\le D_\lambda, so the desired inequality is automatic whenever

Suppose F(\lambda)<s^{1-a/4} and (16) fails. The positive allowance above then gives h\log s\le K_0F(\lambda), and M=s-h\ge s/2 for large R. Put k=\min(M-\lambda_1,M-\lambda'_1). The dimension estimates from Section 2 give c_{\rm dim}k\le F(\lambda)\le k\log s. Hence h\le K_0k, and

for large R, because \theta=a/16<a/4. Also k\ge1, since F(\lambda)>0. Lemma 4.1 applies. There are D_\lambda singular values, so

This settles the sparse-dimension range.

We are left with b\ge2 and the large-dimension range

6.1 The hook estimate on the current grid

Removing the boxes outside a hook will record extra card trajectories. We therefore first prove an estimate that is uniform over the resulting path families. Set

Under the induction hypothesis for fewer than b coordinates, we claim that every family \mathcal H' of h' prescribed trajectories on the current grid, with distinct slots at every layer and satisfying the coordinate rule of Section 3, and every (p,p)-hook diagram \gamma\vdash s-h', satisfy

There is no lower bound on F(\gamma) in this claim. It retains the full trajectory potential and improves both coefficients slightly. We will derive it from two shorter coordinate sweeps, then use its dimension reserve when the removed boxes are restored.

Split the coordinate list into consecutive parts of \lfloor b/2\rfloor and \lceil b/2\rceil coordinates, with products s_1 and s_2. Each coordinate contributes between \log R and 2\log R, so

In particular p\le s_u. Regard the grid as s_2 rows of length s_1. The first part of the sweep acts within rows and the second within columns. At their junction, the middle positions of \mathcal H' are removed, leaving a fixed board of s-h' free sites. Splitting each prescribed trajectory there gives the path constraints in each row and each column.

Use the signed tensor representation of Section 5 on the free sites at each layer. Let X be the conditional row average from the input layer to the junction, and Y the conditional column average from the junction to the output. The row and column randomizations are conditionally independent under the fixed path constraints, so YX is the full conditional average. At the junction let P_\gamma be the full-group isotypic projection, and let P_\alpha^R,P_\beta^C be the row and column subgroup projections. Here \alpha_i partitions the number of free sites in row i, and \beta_j partitions the number of free sites in column j; a row or column with no free sites has the empty type. The sums below range over the local types occurring in the signed tensor representation. Put

The full projection commutes with both subgroup projections. Bijections between the layers intertwine their full isotypic projections. Thus, under compatible unitary identifications, the restriction of Y P_\gamma X from the input \gamma-isotypic space to the output \gamma-isotypic space is K_\gamma^{\mathcal H'}\otimes I, where the identity acts on the tensor multiplicity space. The hook type occurs by Lemma 5.1, so this multiplicity is at least one. Inserting the subgroup decompositions at the junction gives

The first inequality uses the unnormalized trace on at least one copy of \gamma. The second uses the triangle inequality and the product norm inequality, followed by \|A\|_{\rm op}\le\|A\|_{2q} for an outer factor. We now bound the two child moments and the middle overlap.

Ordering the free sites by rows at both ends of the first part makes X=\bigotimes_i X_i; signed unitary reordering justifies this tensor product. Write \mathcal H_i for the path constraints in row i and \operatorname{mult}(\alpha_i) for the tensor multiplicity. Then

The column formula is identical. Lemma 5.1 bounds each multiplicity by \exp(O(p^2\log(s+1))). Apply the induction hypothesis to every local constrained sweep and put

Each stage line belongs to exactly one child subproblem, so their potentials add to C(\mathcal H'). Each part has h' prescribed trajectories, and their size weights add as \log s_1+\log s_2=\log s. Hence

The middle factor in (19) depends only on the fixed free-site board. Its estimate does not use the trajectory probabilities.

We now combine the two estimates. Write W for the right side of (21), including its error. Terms with zero middle factor in (19) contribute nothing. For a nonzero middle factor, its norm is at most one as well as satisfying (21). Since c_*\le2c_0<1\le q,

Adding this to (20) cancels F_R+F_C. The number of lists of local hook types contributes only O_q((s_1+s_2)p^2\log(s+1)) when the sum in (19) is raised to 2q. We obtain

The size split gives the reserves in the claimed coefficients. With L=\log s,

The hats use only 1/(20\sqrt L) of each reserve. The remaining hole reserve is at least h'\sqrt L/20, which absorbs c_*h' for large R. Also

For fixed q, the corresponding O_q error is at most s^{9/10} once R is large. These comparisons prove (18) for every allowed \mathcal H' and hook type, including the types of small dimension.

6.2 Adding the cells outside the hook

Return to the diagram \lambda in (17). Keep its (p,p)-hook part \gamma, which is a Young diagram. Translate the remaining boxes by subtracting p from both indices to obtain an ordinary partition \delta, and put k=|\delta|. The skew shape \lambda/\gamma is a translate of \delta, so branching and Frobenius reciprocity give multiplicity D_\delta for \lambda in the representation induced from [\gamma] on S_{M-k} to S_M. That induced space has dimension (M)_kD_\gamma. In particular,

Realize the induced space with one fiber of type [\gamma] for each placement of k distinguishable cards in the free slots. A bijection moves the placement and acts on its fiber by the bijection of the remaining slots; consistent identifications of those slot sets change the fiber maps only by unitaries. The average block from placement x to placement y is p_{\mathcal H}(x,y) times the conditional operator in [\gamma] after those extra trajectories have been prescribed. If this probability is positive, the endpoints force a feasible augmented family \mathcal H' of h+k trajectories. Thus (18) applies to every nonzero block, with no dimension condition on \gamma.

The 2q-moment of the induced average is the sum of the irreducible moments with their multiplicities, and hence is at least D_\delta T_\lambda^{\mathcal H}. Expand its trace as a sum over cyclic placement indices with 2q edges, alternating between the input and output placement sets. Let p_j be the transition entry on edge j, using the transposed transition matrix on an adjoint edge. The fiber map on an adjoint edge is the adjoint of its corresponding forward conditional operator. It has the same singular values and uses the same forward path potential. For a nonzero cyclic term, write \mathcal H'_j for these augmented paths on edge j. The triangle inequality and matrix trace Hölder give

The sum may be restricted to nonzero cyclic terms.

Apply (18). Apart from the potential -C(\mathcal H'_j), its terms depend only on s,h+k,\gamma, so the same bound applies on every edge. To handle the potentials, apply (4) to a 1/(2q) power of each p_j. Multiplication over the edges yields

The augmented potentials have disappeared, leaving the potential of the original path family.

It remains to sum the last product. Put n_k=(M)_k and label the 2q placement variables x_1,\ldots,x_{2q} cyclically. Each edge matrix is the placement transition matrix or its transpose. Both row and column sums are one, because the transition averages bijections of the free slots. For each r, let A_r be the product of all edge entries except the rth. Then

Deleting an edge opens the cycle into a chain. Successive summation over an endpoint of that chain uses a row or column sum equal to one; the last placement has n_k possible values. Hence \sum A_r=n_k for every r, and scalar Hölder gives

Restricting to the nonzero cyclic terms only decreases this sum. The net counting factor in (23) is therefore s^{-k}(M)_k\le1. We have proved

We finish by comparing the cost of the extra trajectories with the dimension gained from the removed boxes and from the hook estimate. Since \widehat c>0, (22) gives

The positive k-terms in the bracket are the cost of changing the dimension term from \gamma to \lambda and prescribing k extra trajectories. The coefficient of k\log s is

Every row of \delta is no longer than the (p+1)st row of \lambda, and likewise for columns. Those two lengths are at most s/(p+1) by the total size of \lambda. Thus every hook of \delta has length at most 2s/(p+1). If k\ge s^{1-a/2}, the hook formula and k!\ge(k/e)^k give

This dominates the bracket’s positive k-terms for large R, because a/50<a/2 and b/\log s\le1/\log R. If instead k<s^{1-a/2}, discard -F(\delta)\le0; the bracket is then at most O(s^{1-a/2}\log s).

Finally, (17) gives

For sufficiently large R, the dimension reserve therefore absorbs the remaining errors. Since \widehat e<e(s), the old hole allowance also improves. This proves (5).

The induction is complete. All scale requirements, including the error absorptions for every s\ge R, hold after fixing a sufficiently large absolute power of two R after q. The final small-real-z interval is obtained by choosing z_*>0 for (3), the sparse estimate, and the finite base case.

7 Analytic transfer and repeated binary sweeps

We now use Theorem 3.1 with no prescribed paths to bound binary sweeps. Write K_\lambda(z) for the resulting sweep operator. It is a product of the line averages in (2), hence a matrix polynomial in z. All complex parameters below refer to this unconditioned polynomial. Put a_0=c_0/(2q)>0. Since c(s)\ge c_0, (5) gives

A second estimate holds on a disk of radius greater than one. For an allowed line size m, averaging by B_m in an irreducible representation is a product of orthogonal projections, one for each independent-switch layer. If the product had norm one, finite dimensionality would give a unit vector attaining that norm. Equality through the successive projections would force this vector to be fixed by every switch group. These groups contain the transpositions along all edges of the connected cube and hence generate S_m. Thus the norm is strictly less than one in every nontrivial irreducible. Let \kappa<1 be the maximum of these norms over the finitely many allowed m and their nontrivial irreducibles.

Restrict [\lambda] to a line subgroup S_m, and let P,Q be the averages of U_m,B_m there. The operator P is the orthogonal projection onto the line invariants, and PQ=QP=P, because uniform averaging absorbs every group element. Relative to \operatorname{ran}P\oplus\ker P,

Indeed Q|_{\ker P} is a direct sum of the nontrivial line averages, with arbitrary multiplicities, so its norm is at most \kappa. Choose r=2 if \kappa=0, and otherwise choose 1<r<\kappa^{-1}. Every line average is then contractive for |z|\le r. Independence makes each stage average the product of its commuting line averages, and the full operator is the ordered product of the stage averages. Submultiplicativity gives \|K_\lambda(z)\|_{\op}\le1 for |z|\le r, uniformly in the grid and \lambda.

To compare this disk bound with the stronger real bound, choose 0<u<v<\min\{z_*,1,r-1\} and set \Omega=\{z\in\mathbb C:|z|<r\}\setminus[u,v]. For \varepsilon_0>0, the function

is harmonic off the segment. Direct integration of the logarithm gives a continuous extension across the segment, including its endpoints. On |z|=r, the inequality |z-t|\ge r-v>1 gives G(z)\le0. Its values on the closed segment are bounded, so choose \varepsilon_0>0 small enough that G\le1 there. Also G(1)>0, since 0<1-t<1 for every t\in[u,v].

Fix unit vectors u_0,v_0 and put f(z)=u_0^*K_\lambda(z)v_0. This is a scalar polynomial. We may assume f\not\equiv0, since an identically zero coefficient has |f(1)|=0. Then \log|f| is subharmonic, with value -\infty at its zeros. Put A=a_0\log D_\lambda\ge0. The function H=\log|f|+AG is subharmonic on \Omega. The real and disk estimates, together with continuity at the slit, give

The second line includes both sides of the slit and its endpoints; if f(\xi)=0, the logarithm tends to -\infty. The boundary-limsup maximum principle for subharmonic functions [5, Chapter I, Section 4.C.1, Theorem (4.14)] gives H\le0 on \Omega. Since 1\in\Omega, it follows that \log|f(1)|\le-A G(1). Taking the supremum over the two unit vectors yields

The constants R,q,z_* were fixed in Theorem 3.1; the choices of \kappa,r,u,v,\varepsilon_0 depend only on them. Thus g is independent of the grid, its number of coordinates, and \lambda.

It remains to pass from this operator bound to the full permutation law. Let \ell=\log_2R. For d\ge\ell, write d=b\ell+t with 0\le t<\ell, and split the consecutive bits into one block of \ell+t bits and b-1 blocks of \ell bits. Their line sizes lie in [R,R^2]. At z=1, the binary sweeps on disjoint lines within a block can be interleaved by bit direction, so the grid sweep is exactly B_N for N=2^d. Its sign coefficient is zero: the sign of any one fair switch is independent of the remaining switches and has mean zero.

For \mu_w=B_N^{*w}, the convolution convention in Section 2 gives \widehat\mu_w(\lambda)=K_\lambda(1)^w. The classical finite-group Fourier argument of Diaconis and Shahshahani [6, Section 2, Lemma 2, and the proof of Lemma 14] combines Cauchy–Schwarz with matrix Plancherel to give

The second inequality uses the sign cancellation and \|K_\lambda(1)^w\|_2^2\le D_\lambda\|K_\lambda(1)\|_{\op}^{2w}. A deterministic initial deck translates \mu_w and leaves its distance from uniform unchanged.

Put \beta=2gw-2 and k(\lambda)=\min(N-\lambda_1,N-\lambda'_1). For a fixed 1\le k\le N/3, a diagram with k(\lambda)=k has first row N-k after transposing if necessary; its remaining k boxes form a partition of k. There are therefore at most 2\cdot2^k such diagrams, and (1) gives D_\lambda\ge e^{-1}(N/k)^k. For k>N/3 and sufficiently large N, Section 2 gives \log D_\lambda\ge c_{\rm dim}N, and there are at most 2^N partitions of N. Consequently, for \beta>0 and sufficiently large N,

For each fixed k, the summand in the first bound tends to zero, and it is at most (2\cdot3^{-\beta})^k throughout its range. Thus the first sum tends to zero when \beta>\log2/\log3, by domination by a summable geometric sequence. The second tends to zero when \beta c_{\rm dim}>\log2. Choose an absolute integer w so that \beta=2gw-2>\max\{\log2/\log3,\log2/c_{\rm dim}\}. The total variation distance then tends to zero as d\to\infty, uniformly over deterministic initial decks.

One binary sweep is exactly d physical Thorp shuffles, as shown in the introduction. Hence the distance is at most 1/4 after wd physical steps for all sufficiently large d, giving t_{\rm mix}(d)=O(d). Proposition 1.2 gives t_{\rm mix}(d)\ge2d-O(1), so the mixing time has the optimal order \Theta(d).