Staggered extraction for exact matrix multiplication over every field

1 Introduction

For a fixed field \F, the matrix multiplication exponent \omega=\omega_\F is the infimum of the real numbers \tau for which two n\times n matrices over \F can be multiplied using O(n^{\tau+o(1)}) scalar additions and multiplications. This exponent measures the asymptotic arithmetic cost of a central bilinear operation and of many algorithms built from it. The field is fixed throughout; constants in an arithmetic algorithm may depend on the field and on its chosen finite construction.

Strassen’s seven-product algorithm for 2\times2 matrices gave the subcubic exponent \log_2 7 [12]. Subsequent advances used tensors to record bilinear operations: tensor rank counts the products of linear forms needed to realize an operation. Approximate bilinear identities and their conversion to exact algorithms [4], Schönhage’s asymptotic sum inequality [10], and Strassen’s laser method [13] established the main ingredients of this approach. The sum inequality converts a low-rank direct sum of matrix tensors into an exponent bound. The laser method constructs such direct sums by restricting powers of a tensor with low asymptotic rank. Coppersmith and Winograd combined these ideas with progression-free sets and introduced the tensor family used here [5].

Passing to a larger tensor power gives more freedom in choosing the intermediate pieces before extracting matrix tensors from them. Stothers analyzed the fourth power, in work subsequently published with Davie [11, 6]. Vassilevska Williams analyzed the eighth power, and Le Gall continued through the thirty-second power [14, 9]. Alman and Vassilevska Williams then reduced the extraction loss that arises when prescribed marginal distributions permit several joint distributions, obtaining \omega<2.3728596 [2].

A further source of loss is requiring entire variable blocks to be disjoint when the final matrix tensors need only disjoint subsets of those blocks. Duan, Wu, and Zhou used asymmetric hashing to reduce this combination loss in the recursive analysis [7]. Vassilevska Williams, Xu, Xu, and Zhou allowed finer sharing of variables and extended recovery from deletions on all three sides to the restricted tensor products needed in the recursion [15]. Alman, Duan, Vassilevska Williams, Xu, Xu, and Zhou then introduced successive compatibility tests that treat all three sides differently [1]. These tests underlie the extraction studied here.

For a recent numerical comparison, Dupont et al. obtained \omega<2.371177 by optimizing the eighth-power instance of this asymmetric framework, combining modern optimization with AlphaEvolve [8]. Version 3 of More Asymmetry Yields Faster Matrix Multiplication records that improvement and credits the new parameters to Dupont et al. [1, Table 1]. We prove the following bound over every fixed field.

The construction gives exact arithmetic algorithms, including in positive characteristic. Its finite choices are independent of the input matrices. The theorem concerns asymptotic arithmetic cost; the counting arguments and parameter choices do not give bit-complexity or practical crossover estimates.

1.1 Proof overview

We use the Coppersmith–Winograd tensor with parameter 5, denoted \CW_5. Section 2 defines it and proves that the rank of its mth tensor power is at most 7^m times a polynomial in m, over the original field. A strand of length \ell is a copy of \CW_5^{\otimes\ell}. On each side the variables of \CW_5 are indexed by 0,\ldots,6, with weights 0,1,1,1,1,1,2. A strand variable is a word of these indices, and a shape records the weight sums on the three sides. We start with strands of length 8 and split them successively into lengths 4, 2, and 1. At each depth we restrict by shape. A shape with a zero coordinate already gives a matrix multiplication tensor; positive shapes pass to the next split.

Combining capacities across depths. An extraction restricts a tensor to a direct sum of specified tensor products. To make the outputs disjoint, its three side-assignment tests each impose a bound on the guaranteed logarithmic number of outputs; we call these bounds its directional capacities. The guarantee uses their minimum. The constituent-stage analysis in [1, Theorem 6.4] already combines differently prescribed populations at one depth before taking this minimum. Our joint step also combines populations at different depths, provided their priority orders agree on the physical tensor sides. For their weighted capacity vectors v_r\in\mathbb R^3, the benefit of pooling across depths is expressed by

Thus a shortage on one side at one depth can be offset by capacity from another depth.

Section 3 proves this joint extraction by following the actual order of the tests. On the first side, variables are grouped by their sequences of strand or half-strand weight sums; these groups are the coarse blocks. Each retained coarse block is assigned to a unique output. Compatibility with that assignment then determines which complete variables on the second and third sides can be retained. The result is a direct sum of the intended products with some variables deleted. Populations retain their ancestry and physical placement throughout, so each subsequent split receives its own prescribed distributions.

Recovering outputs with inherited restrictions. Some variables are missing because an earlier extraction imposed type conditions, meaning conditions on empirical distributions of variable statistics. Others are deleted to resolve competing assignments in the current extraction. Earlier recovery arguments already treat three-side deletions and inherited type conditions [15, Section 7], [1, Section 6.5]. Section 4 proves the form needed for our joint step. With N the large strand-count parameter, the extraction selects outputs in which every orbit of complete variables under the allowed position permutations loses at most C/N of its variables, uniformly over the orbits. Here C depends only on the fixed population data and tolerances. Independent symmetry shifts then cover the ideal tensor. Partitioning variables by their presence in those shifts reconstructs every coefficient exactly once, over the original field. Only a subexponential number of independent input copies is needed. The recovered products can then be subdivided and used in further extractions.

Staggering and the final rank comparison. A lot contains N length-8 strands. We stagger finitely many lots so that, at an interior time step, one lot is at each of the three splitting stages. Stage priorities balance the summed directional capacities. The work is partitioned among the six physical axis orders; one joint extraction acts on each part, and the six output counts multiply. Section 5 constructs this schedule, shown in Figure 1, and computes its finite boundary loss. Section 6 counts the common oriented dimensions of the terminal matrix tensors and combines these counts with the schedule to prove the total yield and rank comparison.

Write H_0 for the initial logarithmic yield, C_* for the contribution of the three staggered stages, and S_* for the terminal logarithmic matrix volume, all normalized per initial length-8 strand. The direct-sum rank inequality then gives

For each fixed number of lots, we first take the divisible strand count N to infinity and remove approximation losses; the number of lots tends to infinity last. Thus the boundary cost vanishes without a uniform assertion for a growing schedule. The explicit rational data in Section 7 and Appendix A certify S_*>0 and place the ratio in (1) below the bound in Theorem 1.1. The complete parameter verifier and its rational-logarithm interval certificate accompany the source. The proof requires a single feasible choice of parameters, with no assertion that this choice is optimal.

2 Rank and the basic tensor

Fix an arbitrary field \F. All tensor identities and linear maps below are over \F, and all logarithms are natural. A tensor is viewed as a trilinear form in three disjoint sets of variables. Its rank \R(T) is the least number of products of three linear forms, one on each side, whose sum is T. A restriction substitutes linear forms separately on the three sides. Restrictions cannot increase rank. A direct sum uses disjoint variables, and a tensor product pairs the variable indices on each side; rank is subadditive under direct sum and submultiplicative under tensor product. These statements follow by applying the indicated operations to rank decompositions.

For positive integers a,b,c, write

This is the tensor for multiplying an a\times b matrix by a b\times c matrix. Its volume is abc. Pairing the three matrix indices gives

Cyclically permuting the three variable spaces replaces the parameters by (b,c,a) or (c,a,b) and preserves rank.

2.1 Exact rank and the arithmetic exponent

Put R_d=\R(\langle d,d,d\rangle) and

The flattening that sends a z coordinate to its coefficient bilinear form has rank d^2: the d^2 forms \sum_jx_{ij}y_{jk} are linearly independent. A rank-one tensor has flattening rank at most one. Thus d^2\leq R_d\leq d^3 and 2\leq w\leq3. In particular,

where R_1=1 handles the unit case.

Let \omega denote the arithmetic exponent of square matrix multiplication over \F, counting scalar additions and multiplications. A fixed rank-R_d decomposition gives a bilinear matrix multiplication identity with R_d products. This identity remains valid on matrix blocks: every product has its x-linear factor before its y-linear factor, and comparison of coefficients proves the same identity for noncommuting blocks with central coefficients in \F. At size d^k the resulting arithmetic cost satisfies

The implied constant may depend on the chosen decomposition. Since R_d\geq d^2, this gives C_k=O_d(kR_d^k), including the boundary case R_d=d^2. Padding an arbitrary size to the next power of d therefore gives cost O_d(n^{\log_d R_d}\log(n+1)). The logarithmic factor is absorbed by n^\eta for every \eta>0; taking the infimum in (2) proves

We also need a uniform upper bound on exact square rank. Given \varepsilon>0, choose one integer d\geq2 with \theta=\log_d R_d<w+\varepsilon. For h\geq1, tensor powers and padding give

This argument uses one approximating dimension; it does not require the infimum defining w to be attained.

We use the following identical-summand form of Schönhage’s asymptotic sum inequality [10], with a proof from exact rank.

The hypothesis in Lemma 2.1 specifies one common oriented triple (a,b,c) for all summands. In the construction below, exact history counts and common terminal type restrictions will provide these identical dimensions.

2.2 An integer coefficient construction

The relation between approximate bilinear identities and exact algorithms was studied by Bini [4]. Here a direct coefficient calculation gives an exact rank bound over the original field, including when that field is finite.

For an integer q\geq1, define the symmetric Coppersmith–Winograd tensor [5]

We use q=5. The following exact-rank estimate makes the field independence and the polynomial overhead explicit.

2.3 Strands and shapes

Give the label 0 weight 0, the labels 1,\ldots,q weight 1, and the label q+1 weight 2. Every term of \CW_q has total weight 2. A strand of length \ell is a copy of \CW_q^{\otimes\ell}; its variable indices are words of length \ell. For a triple g=(g_0,g_1,g_2) of nonnegative integers with g_0+g_1+g_2=2\ell, let T_{\ell,g} be the restriction in which the weight sums on the three sides are g_0,g_1,g_2. The coordinates of g refer to sides, whereas the weights 0,1,2 refer to individual labels. A shape is positive if all three coordinates are positive. When \ell is even, splitting a strand into its two consecutive halves gives child shapes u and g-u, where 0\leq u\leq g coordinatewise and \sum_i u_i=\ell.

A zero coordinate gives an especially simple terminal tensor. Suppose g_0=0. The x word is then forced to be the all-zero word. In each position a label on the y side uniquely determines the z label: 0 and q+1 are exchanged, and every label i\in\{1,\ldots,q\} is fixed. Thus the other two sides are matched bijectively, and T_{\ell,g} is \langle1,1,M\rangle, where

For g_1=0 or g_2=0 the corresponding orientations are \langle M,1,1\rangle or \langle1,M,1\rangle. Restricting the matched words by corresponding type conditions on their two sides preserves this form, with M replaced by the number of allowed matched pairs; an empty matching gives the zero tensor. This observation will supply the terminal volume counts.

3 A joint extraction at several depths

The constituent-stage analysis of [1, Theorem 6.4] combines differently prescribed populations at a common depth. The extraction below also permits populations at different depths to share one hashing step, provided their priority orders agree on the physical tensor sides. Population data, strand lengths, and the constant sums defining their coarse supports may differ. The successive compatibility checks follow [1, Section 4.1], building on the asymmetric hashing and interface-tensor methods of [7, 15]. We specify the intended output first, then derive the three capacities that govern its extraction yield.

For a probability vector p on a finite alphabet, write H(p)=-\sum_a p(a)\log p(a), with 0\log0=0. A word has type p if its empirical distribution is exactly p; a type window of width \theta means coordinatewise distance at most \theta. All alphabets, populations, and positive population masses in this section are fixed as N tends to infinity.

3.1 The data of a joint step

Index the populations by a finite set \mathcal R. Population r has m_r=c_rN copies of a fixed strand tensor F_r with finite variable sets, where c_r>0 is rational. On each side its variables are partitioned into coarse blocks indexed by \{0,\ldots,16\}. Every monomial of F_r has its triple of coarse indices in an ambient support \Omega_r, whose elements u=(u_X,u_Y,u_Z) satisfy

Here X,Y,Z is one common ordering of the physical sides. In the product \bigotimes_r F_r^{\otimes m_r}, a coarse block is specified by a sequence of indices, one for every strand. A fine side variable is a complete basis variable of the product input; its coarse block records the coarse index at every strand position. The fixed strand tensor in a population is repeated identically at all its positions. Populations with different histories or physical placements are kept distinct.

Choose a rational law p_r on \Omega_r that maximizes entropy among all laws on \Omega_r with its three marginals. The support of p_r may be smaller than \Omega_r. There are two kinds of population.

1. 1.

   An ordinary population delivers the full tensor block at each selected triple u, without further output type tests. The blocks may themselves be tensor products of child strands. This includes extraction by whole-strand shape and the final split into length-one strands.

2. 2.

   A sharing population consists of copies of T_{\ell,g}, with even \ell and \sum_Wg_W=2\ell. Its coarse index u_W is the weight sum in the left half, so

   \Omega_r=\{u:0\le u\le g,\ \textstyle\sum_Wu_W=\ell\}, \qquad T_{\ell,g}|_u=T_{\ell/2,u}\otimes T_{\ell/2,g-u}.

   Assume p_r(u)=p_r(g-u). On each side W, a statistic of the full half-strand variable takes values in a fixed finite alphabet \mathcal A_{r,W}. A map \rho_W from this alphabet to weights determines the half weight sum. For every half-shape u with p_r(u)>0, prescribe a rational law \nu_{r,u,W} supported on \rho_W^{-1}(u_W).

   When a half-shape has a zero coordinate, the full variables on the other two sides match by complementation. Require that their statistics also match by a fixed bijection and that their prescribed laws are its pushforwards. A side having a unique possible variable has its corresponding point-mass prescription. These requirements apply as well when two coordinates vanish.

Ideal outputs and inherited masks. A target triple e is a triple of coarse sequences having exact joint type p_r in each population. Start with the tensor block at e. In every sharing population, impose a positive type window around \nu_{r,u,W} separately in every class of positions of given (r,u,\text{half}), on each side. The right-half prescription in the class indexed by u is \nu_{r,g-u,W}. Leave ordinary blocks unrestricted. The resulting tensor product is the ideal output Q_e. Target triples have the same class sizes, so their ideal outputs are isomorphic by position permutations preserving the physical sides; denote a canonical such tensor by Q_N. A fine side variable in a coarse block of e is useful for e if it satisfies all these output windows; ordinary populations contribute no further condition. Thus usefulness specifies the variables of the ideal tensor. Additional input or separation tests may delete some of them.

The child windows constrain the two halves separately. Inherited conditions can also constrain how their statistics are paired at parent positions. For a sharing population, suppress r temporarily and define the mixture law, omitting all zero-mass shapes as we do below:

This is the expected pair law when, within each shape class, the left and right statistics have their prescribed laws and are independently arranged.

An input mask is always a deletion of individual side variables. For sharing populations we allow finitely many empirical tests on the ordered pair of half statistics, or a fixed function of that pair. Their centers must be the law D_{r,W} in (11), or its corresponding pushforward, and their widths must be fixed positive numbers. Ordinary input masks must already follow from the exact target coarse types and the specified ideal blocks. No other inherited masks are assumed. All masks are imposed separately in the populations just defined. A mask on a larger received class can instead be enforced separately, with tighter widths and the same center, on any fixed subdivision; the resulting partwise restrictions imply the original one.

Choose output widths small enough that replacing each prescribed child law by any law in its window leaves the expected ordered-pair law strictly inside every inherited window. This condition has a uniform positive margin: for coordinatewise child errors at most \theta, a product-law coordinate changes by at most 2\theta, and all relevant collections are finite. The same margin will be required for the additional pair tests introduced in the proof.

Compatibility groups and capacities. The extraction will first separate targets by their X coarse blocks and impose the X output windows. It then separates Y variables, imposes their output windows, and finally separates Z variables. The later-side separation tests use only those individual shape types that matching forces from an earlier side. Define their designated shapes by

A zero Z coordinate lets matching transfer the X-side output type condition to Y. For Z, a zero Y coordinate transfers the condition from X; a zero X coordinate instead uses Y, after its output windows have been imposed. If both X and Y coordinates vanish, the Z variable is forced. For the remaining shapes with a given W coordinate, the pair law D_W determines only an aggregate statistic law after the designated contributions are removed. We impose no individual compatibility test on these shapes. The exact predicate and its tolerances are given in the incidence count below. For W\in\{Y,Z\}, the partition \mathcal G_W consists of the individual groups \{u\} for u\in\mathcal I_W, and the residual groups \{u\in\supp p\setminus\mathcal I_W:u_W=i\}. Empty groups are omitted. A residual group is treated as residual even when it contains just one shape. Put p(G)=\sum_{u\in G}p(u) and define

The entropy J_W measures the choices for one half-statistic word within these groups. Counting both halves gives the cost 2J_W; comparison with the pair-word entropy H(D_W) gives the saving that controls the number of compatible targets. Accordingly, define the sharing capacities by

Only the law of half-shapes is assumed invariant under u\mapsto g-u; the two prescriptions \nu_{u,W} and \nu_{g-u,W} may differ.

For an ordinary population no compatibility restriction is needed, and the capacities are simply

The counting arguments below give a common interpretation: each C_{r,W} is the entropy saving in the bound on competitors at side W. The joint step adds these savings over populations before taking their minimum.

We first bound hash survival and assignment collisions. The sequential X,Y,Z tests then put surviving monomials in a direct sum of variable restrictions of the ideal outputs. Section 4 completes the proof by bounding the missing fraction on every full-variable orbit and restoring the ideal outputs from \exp(o(N)) input copies.

3.2 Entropy and a common modular hash

For a fixed alphabet \mathcal A, the number of words of type p is

Indeed, comparing the sum \sum_{j=1}^n\log j with its integral gives \log(n!)=n\log n-n+O(\log(n+2)). There are at most (m+1)^{|\mathcal A|} possible types. Both bounds are uniform on each fixed alphabet, including types with zero coordinates.

One convenient way to meet the entropy hypothesis is to use positive weights a_i,b_j,c_k and set

For any competing law q with the same marginals, -\sum q\log p=-\sum p\log p=H(p), because \log p is a sum of three one-coordinate functions and a constant. Further,

by \log t\le t-1. Thus H(q)\le H(p). Positive rational weights give rational laws with this same property. When the marginals specify a unique law, maximality also holds, including boundary laws with zero probabilities.

First keep, on each side, just the coarse sequences having marginal type p_{r,W} in every population. Call a triple satisfying these three filters and the support conditions ambient. The total number of target triples is

For a fixed X coarse sequence, each possible ambient joint type q_r has the prescribed marginals. Its number of completions in population r is

Summing over the polynomially many types and using maximality yields the degree bound

Here and below the coarse counts ignore all fine masks, thereby bounding every interaction that could actually occur.

Fix a small slack \delta>0. Since C_X\le A_{\rm amb} and E\le C_X, choose a power M=37^k with

There is a set U\subset\mathbb Z/M\mathbb Z with

and no nonconstant three-term arithmetic progression. Here is a version of Behrend’s construction [3] that also rules out modular wraparound. Put h=\lfloor\sqrt{\log M}\rfloor, b=\lfloor M^{1/h}/2\rfloor, and encode d\in\{0,\ldots,b-1\}^h as n(d)=\sum_{j=0}^{h-1}d_j(2b)^j. Choose a largest class with fixed \sum_jd_j^2. Every encoded integer is less than (2b)^h/2\le M/2, so a modular progression among them is an integer progression. In n(d)+n(e)=2n(f) all digit sums are at most 2b-2, so there is no carry and d+e=2f. Equal squared norms now give \|d-e\|^2=2\|d\|^2+2\|e\|^2-\|d+e\|^2=0. There are at most 1+h(b-1)^2 norm classes, whence |U|\ge b^h/(1+hb^2). The inequalities b\ge M^{1/h}/4 and b\le M^{1/h} imply (20).

Concatenate all d=\sum_r m_r strand positions to form coarse words I,J,K. Let S have entry s_r at positions in population r. Every ambient triple satisfies I+J+K=S, even though the entries of S can vary. Choose independent uniform offsets a,b' and a uniform vector v over \mathbb Z/M\mathbb Z, and set

Division by 2 is defined since M is odd. Keep only coarse blocks whose hashes lie in U. Since x+y=2z, a surviving triple has x=y=z.

For a fixed ambient triple e, let S_e be its full hash-survival event. For every v and t\in U there is exactly one offset pair giving x=y=z=t, so

Conditional on S_e, (v,t) is uniform on (\mathbb Z/M\mathbb Z)^d\times U. A second triple with differences (\Delta I,\Delta J,\Delta K) has hashes

If it shares X with e, survival is equivalent to \langle v,\Delta J\rangle=0; if it shares Y or Z, it is equivalent to \langle v,\Delta I\rangle=0. In the shared-Z case use \Delta J=-\Delta I. Distinct triples cannot share two blocks, by their common sum S. Thus the tested difference vector has a nonzero coordinate of absolute value at most 16, which is a unit modulo 37^k. Conditioning on the other coordinates of v shows, in all three cases, that

No further hash-dependent event is included in this conditioning.

3.3 The finite compatibility count

In a sharing population, prefilter side W\in\{Y,Z\} by requiring its empirical ordered-pair law to be within width \eta of D_W. A fine side variable is compatible with a target triple if its statistic type is within width \chi of the prescribed law in every designated shape class, separately on the two halves. On the left these are the positions with u\in\mathcal I_W, using \nu_{u,W}; on the right they are the positions with g-u\in\mathcal I_W, using \nu_{g-u,W}. No individual compatibility test is imposed on a residual group, including a residual group with one shape. The positions of each tested class are read from the target triple. Ordinary populations impose no compatibility test. A variable for the whole product is compatible exactly when it is compatible in every population.

3.4 Sequential assignment by variable deletion

Choose \eta,\chi>0 sufficiently small that the error in Lemma 3.2 is below \delta/4. Next choose output widths \theta>0 smaller than \chi and small enough for the positive margins required by all inherited and pair tests. Complementary prescribed laws ensure that usefulness of one side transfers to the compatibility window on a matching side. Every choice here is fixed before N grows.

First delete an X coarse block unless it belongs to exactly one ambient hash survivor and that survivor is a target triple. Call the retained triples eligible. Freeze this list for all subsequent tests. By (18), (19), and (23), a target triple e fails this test, conditional only on S_e, with probability at most \exp(-\delta N+O(\log N)). Each retained X block now has an unambiguous assignment. In that block retain only the fine variables useful for its assigned triple, that is, those satisfying its output windows.

On Y, apply its pair filters and delete every fine variable having other than exactly one compatible eligible triple containing its coarse block. Assign it to that triple and impose usefulness for that assignment. Apply the same procedure to Z, using the designated classes \mathcal I_Z. Include all inherited masks as side-variable deletions; their application does not change the frozen eligible list or the definitions of the compatible lists.

We verify that these operations produce a direct sum, rather than merely a list of proposed components. Take an actual monomial surviving every deletion, and let e be its ambient coarse triple. Its X block survived, so e is that block’s unique eligible triple and its X variable is useful for e. In every sharing half with u_Z=0, the Y statistics are complementary to the X statistics. Thus the actual Y variable is compatible with e; deterministic sides satisfy their point-mass tests as well. The Y uniqueness test therefore assigns this variable to e. Its usefulness is now known for the actual triple.

For Z, a half with u_Y=0 transfers the required statistics from X. A half with u_X=0 and u_Y>0 transfers them from the already useful Y variable. With both u_X=u_Y=0, the remaining variable is forced. These cases prove compatibility with e on every designated shape class in \mathcal I_Z. Its uniqueness test then assigns the actual Z variable to e as well. Ordinary populations add no compatibility conditions in either argument. All three variables of every retained monomial therefore have the same assignment.

Different assignments share no retained fine variable on any side. Within assignment e, usefulness restricts precisely to Q_e; all other tests delete individual variables of Q_e. Consequently the surviving tensor is a direct sum of tensors Q_e^{\rm hole}, each obtained from its ideal Q_e solely by variable deletion. This statement concerns complete variables of the population product; sharing a local coordinate factor between two complete variables does not identify those variables.

Here is the probability estimate needed to repair these holes. For a fixed e and a fixed variable v of Q_e passing all its deterministic inherited and pair masks, own-triple compatibility and usefulness hold. Let R_{e,v} be the union of the X eligibility-failure event and, when v is on side Y or Z, the events that another compatible target triple sharing its coarse block survives the hash. Every random deletion of v is contained in R_{e,v}. Bound those competitors among all target triples before eligibility and other deletions. Lemma 3.2 and (23) then give, for some constant c>0,

uniformly in e and the passing variable, for all large N. Indeed, the exponent for side W is at most N(E-C_W-\delta+\xi)+O(\log N) and C_W\ge E. This estimate is conditioned only on S_e, never on eligibility or on passing a hash-dependent test.

For reference in the recovery argument, let G_e act by independent position permutations in every ideal child class (r,u,\text{half}), simultaneously on all three sides. In ordinary whole-strand blocks use their position permutations; for a factorized ordinary block one may also permute its child factors independently. These are automorphisms of Q_e. The full variable alphabets in its finitely many classes are fixed, so G_e has only polynomially many orbits of variables. Lemma 4.1 supplies the uniform deterministic mask bound on these orbits. The completion of Theorem 3.1 in Section 4 combines that bound with (26), selects exponentially many good assignments using (17) and (22), and applies Lemma 4.2 to reconstruct their ideal outputs.

4 Recovering the ideal outputs and composing extractions

The assignment procedure in Section 3 leaves a direct sum of variable restrictions of the intended outputs. We now select sufficiently many of these outputs and recover them exactly. Two different probability spaces occur: permutations of an ideal output control inherited masks, whereas the random hash controls assignment collisions. Keeping these spaces separate is essential when a received population already has type restrictions. Recovery from deletions on all three sides appears in [15, Section 7, especially Property 7.1 and Theorem 7.2]; its interface-tensor consequence is Corollary 4.2 there. The constituent-stage analysis in [1, Section 6.5] also accounts for inherited approximate type restrictions. Here we establish uniform loss on every full-variable orbit of each selected heterogeneous output and reconstruct its coefficients by an exact linear restriction.

4.1 Uniform control of inherited masks

Fix all population masses, rational laws, and positive tolerances before letting the divisible integer N grow. Classes of zero mass are omitted. For a target coarse triple e, write Q_e for its ideal child product, including its prescribed child-side type windows, but before inherited input masks and global pair-frequency masks. Keep distinct the population, its previous history, its exact parent split triple, and its left or right half. Each resulting child class c has n_c=c_cN positions, with c_c>0 fixed. At an ordinary extraction the corresponding whole-strand classes, or the unrestricted child classes of an ordinary split, are used instead.

Let G_e be the product of the symmetric groups on these classes. A permutation acts simultaneously on the three sides of a child tensor, and different child classes, including opposite halves, are permuted independently. This action preserves both the tensor factors and the child-side type windows, so it consists of coefficient-preserving automorphisms of Q_e. The action is on complete variables: a symbol records the entire child word, including its weight-one labels.

4.2 Exact repair

We next give an algebraic recovery statement. A variable restriction of a tensor means that some basis variables are set to zero; all coefficients on the remaining variables retain their original values.

4.3 Completing the joint extraction

4.4 Composition and subdivision

To iterate Theorem 3.1, we record the two algebraic operations explicitly. Write D_r(T)=\bigoplus_{i=1}^r T, and write A\preceq B when A is a linear restriction of B.

There is also an exact way to subdivide a received population before its next use. Let B be its strand tensor, let \nu_W be the prescribed statistic law on side W, and denote by U(m,\nu,\eta) the restriction of B^{\otimes m} to the three coordinatewise type windows with tolerance \eta. Partition the positions into fixed parts of sizes m_1,\ldots,m_j, and on each part use the same laws and a positive tolerance \eta_i\leq\eta. There is an exact variable restriction

To see this, the empirical law of a concatenated variable is the weighted average of its partwise empirical laws, with error at most \sum_i(m_i/\sum_jm_j)\eta_i\leq\eta. Hence every retained variable satisfies the original window; after the partwise masks are imposed, no condition couples different parts, giving exactly the displayed product. Different side tolerances are handled in the same way. Apply this argument separately within every received history class; classes with different prescriptions remain distinct.

Equation (30) need not retain a large fraction of the earlier variables. The next application of Theorem 3.1 starts from this exact product, with its new positive population masses and its consistent inherited laws. Thus it supplies its own yield and mask analysis. Together with canonicalization after repair, this explains why arbitrary fixed finite subdivisions and heterogeneous populations can be used in a subsequent joint step. All such subdivisions and tolerances are fixed before N grows; no assertion of uniformity in a number of populations growing with N is needed.

The required tolerance hierarchy exists for any fixed finite calculation. At a step first make its global and compatibility tolerances small enough for the entropy errors allowed by its hash slack. Then choose its child windows smaller than all those tests and all inherited windows that they must satisfy. Repeat toward the descendants. There are finitely many constraints, each allowing a strictly positive choice. All constants in this section may depend on this fixed calculation; the strand limit is taken only after these choices.

5 Staggering the three extraction stages

A lot consists of N strands of length 8, hence of 8N copies of \CW_5. Its positive shapes pass successively through three stages: A splits length 8 into length 4, B splits length 4 into length 2, and C splits length 2 into length 1. Every shape with a zero coordinate terminates immediately as a matrix tensor. Theorem 3.1 lets one extraction act on populations from different stages. We specify their data first, then give the finite schedule that exploits this freedom.

5.1 Shapes, prescriptions, and the three stages

All coordinate labels in this section belong to \{0,1,2\}. A shape is positive if all its coordinates are positive. Choose a symmetric product-weight law on the ordered shapes of size 16: its probability at (a,b,c) is proportional to \alpha_a\alpha_b\alpha_c, where every \alpha_j>0 and a+b+c=16. Write A_g for the resulting probability of the sorted shape g. Thus the multiplicity of its distinct permutations is included in A_g. If \rho_g gives mass 1/3 to each coordinate of g, counting multiplicities, the common marginal and initial ordinary yield are

The product-weight hypothesis verifies maximum entropy at the given marginals. The initial ordinary extraction therefore yields \exp(N(H_0-o(1))) identical products of shape tensors, after the arbitrarily small losses of Theorem 3.1.

Give each sorted g canonical labels 0,1,2. Its six placements of these labels on the three physical sides will each have amount NA_g/6. To implement this when g has ties, let s_g be the number of label permutations fixing g. There are 6/s_g distinct physical shapes, each with NA_gs_g/6 positions. Divide its positions into s_g equal classes and assign the distinct tied-label placements to them. This is a regrouping of full tensor factors: no fine mask has yet been imposed. For example, each physical arrangement of (4,6,6) has two such classes. Later laws may distinguish its two labels of weight 6. Descendants retain these canonical labels and are never re-sorted.

For each positive sorted g of size 16, choose a positive product-weight law P_g(t) on

with P_g(t)=P_g(g-t). For every positive ordered t of size 8, likewise choose a positive product-weight law p_t(u) on |u|=4, 0\leq u\leq t, with p_t(u)=p_t(t-u). The numerical data in Section 7 specify these laws, as well as the parameters d_{t,u}\in[0,1] and terminal laws z_t used below. Infeasible subscripts always have probability zero.

The length-2 statistic on one side is its unordered pair of weights. We use the following fixed coding; D_i counts the actual index words with statistic i, including the q=5 choices at a weight-1 site:

Here r_i is the sum of the two weights, and \kappa is the image list for complementation. For positive t and a feasible child u, define the law v_{t,u,W} on these six statistics, for each canonical label W, by requiring support on r_i=u_W. If u_W\ne2 this determines the law. If u_W=2, put masses 1-d_{t,u} and d_{t,u} on 11 and 02, respectively. A parameter is needed precisely when u is a permutation of 022 or 112.

On a length-4 strand the statistic is the ordered pair of the statistics of its length-2 halves. For positive t prescribe

For a zero-coordinate t, let W_* be its first canonical label attaining \max t. Choose z_t on the ordered pairs (i,j) with r_i+r_j=\max t. Prescribe V_{t,W_*}=z_t, prescribe the point mass at (0,0) on zero coordinates, and prescribe the coordinatewise \kappa-image of z_t on the remaining nonzero coordinate, if any. The laws of the two matched sides therefore agree under complementation. The same property holds for zero-coordinate u: 01 complements 12, while 11 and 02 complement themselves. These are exactly the zero-side consistency requirements of Theorem 3.1.

Stage A is a sharing split of T_{8,g} with coarse law P_g, child laws V_{t,W}, and canonical priority (0,1,2). Stage B is a sharing split of T_{4,t} with coarse law p_t, child laws v_{t,u,W}, and canonical priority \pi(t). This priority is the lexicographically first permutation of the labels that reads t as one of

These represent every positive size-8 shape up to permutation. The last representative intentionally gives the middle priority to the coordinate of weight 2: for t=(2,3,3) the priority is (1,0,2). The symbols here remain inherited labels.

Stage C is an ordinary split of a positive T_{2,u}. Such u is a permutation of 112. Write its labels as (a,b,c), where c is the distinguished label of weight 2. In this order, the four possible left shapes and their probabilities are

The right shape is u minus the left one. The distinguished marginal fixes the first two probabilities, and the two Bernoulli-1/2 marginals fix the other two. Thus the coupling is uniquely determined by its marginals, also at d=0 or 1, and has the required maximum entropy. Put

Its three ordinary capacities are \log2,\log2,h_b(d_{t,u}), with the last at label c. Every delivered length-1 shape has a zero coordinate and is already a matrix tensor.

This also verifies the inherited masks. At A to B, the input law required by B is exactly the mixture (33) prescribed by A; the orbit-mask estimate of Lemma 4.1 applies with smaller child tolerances. At B to C, an exact type in (35) forces unordered frequency d_{t,u} on 02 and 1-d_{t,u} on 11 at the distinguished label, and forces 01 at the other labels. Hence it satisfies the received v_{t,u,W} masks exactly. Complementary children may have different d parameters: each is a separate factor, and both actual laws appear in (33).

After Stage B is repaired, its ideal children carry the prescribed v_{t,u,W} windows. The earlier V_{t,W} masks were constraints on the input to B; their holes have been repaired, so they are not additional constraints on the recovered children. Thus the exact Stage C types need only satisfy the v_{t,u,W} windows, as verified above. The permutation group used for repair preserves the ideal child tensor, without needing to preserve the historical pattern of input holes.

A history records the lot, initial g, its label placement, every coarse split, its left/right provenance, and any subsequent part. We keep all these populations separate, even when their present shapes coincide. In particular equal u from different t never merge their d_{t,u} values. The sums below record total amounts; they do not combine differently prescribed populations.

5.2 Capacity balance

Stages A and B have fixed capacities in their chosen priority orders. At Stage C, each positive length-2 population has two capacities equal to \log2 and one equal to h_b(d_{t,u}). We may assign the latter to any priority position by choosing the extraction order. We use this freedom to make the sum of the three stages’ capacity vectors have equal coordinates.

Amounts throughout are measured per initial length-8 strand. After summing over histories while retaining their specifications, the amounts of the smaller shapes are

The factors 2 count the left and right children; reflection symmetry of the coarse laws justifies each equality. A parent split is charged only once when computing its capacity.

Let L_A\in\mathbb R^3 be the sharing-capacity vectors of Stage A, weighted by A_g and summed over positive g, with entries in priority order. Likewise let L_B be the Stage B vectors weighted by m_t and read in the order \pi(t). More explicitly, for each parent its vector is

using its own coarse law and child prescriptions in the definitions of Section 3. Thus the two vectors are fully determined by the data just specified. Let T be the total positive length-2 amount, and let B_* be the sum of those populations’ average capacities, weighted by their amounts. The average over priority positions of the total stage capacity is C_*, where

Suppose, as the numerical certificate verifies, that

The denominator and each numerator below are positive by (38). The numbers

sum to 1: their numerators sum to 3(T\log2-B_*) by (). Divide each positive length-2 history class into these proportions. In part i, place its distinguished label in priority position i and order the other labels increasingly in the remaining positions. This changes the extraction order only; it keeps the same parent-specific d_{t,u} and masks. The resulting Stage C capacity vector satisfies

Consequently L_A+L_B+L_C=(C_*,C_*,C_*).

5.3 Physical orders and the finite schedule

Apply the subdivision restriction (30) separately within each received history class, keeping the same prescribed laws and using smaller positive windows. Different parts may use different widths. The resulting tensor is exactly the product of the partwise restrictions; no retained-fraction estimate is required, since Theorem 3.1 acts on this specified product directly. After each repair, exact coarse counts let simultaneous position permutations put its ideal child classes in a canonical order. All selected summands therefore have identical future inputs. These permutations are made after repair and need not preserve the earlier hole patterns.

Suppress the physical placement in a fixed canonical history h. At each of its six placements \phi, its amount is a_hN/6 for the same a_h. This is true initially by the tied-label subdivision. Every child split and part allocation multiplies it by a number depending only on the canonical history, so it remains true inductively. If \rho_h maps priority positions to canonical labels, the physical priority is \phi\circ\rho_h. For any prescribed physical order \sigma there is exactly one contributing placement,

Thus the six physical orders give a disjoint partition of the work, with one sixth of every history’s priority-capacity vector in each factor. This applies to the Stage C parts as well as to A and B.

Assume that L_A,L_B,L_C have positive entries, as verified in Proposition 7.1. Then each vector obtained by summing any nonempty subset of the active stages also has positive minimum capacity. This supplies the condition E>0 of Theorem 3.1 for each physical-order factor at every tick of the following schedule. Its finite applications will use the rational choices made in Section 6.1.

Fix an integer K\geq2 and perform the initial ordinary extraction on each of K lots. Within every resulting summand, launch lot j at A on tick j, at B on tick j+1, and at C on tick j+2. The active stage patterns are

Every lot is processed once at each of its three depths. We first compute the rates for the prescribed data. The rational approximations and arbitrarily small extraction losses are handled in Section 6.1.

At a tick, collect all currently active populations with one physical priority into one tensor factor, using (30) if a received type class needs subdivision. Apply one joint step to each of the six factors. A full tick has, in each factor, total priority-capacity vector

Its minimum is C_*/6, so multiplying the six output counts gives log-yield approaching NC_*. The four boundary ticks similarly have log-yields divided by N approaching

where \min x=\min_{0\leq i<3}x_i for a vector x. All four minima are strictly positive by the entrywise positivity assumption. Relative to K full-tick contributions, their deficit is

Using L_A+L_B+L_C=C_*\mathbf1, this is equivalently \beta=(\max L_A-\min L_A)+(\max L_C-\min L_C)\geq0. The certificate in Proposition 7.1 also verifies \beta<1. Thus the K-2 full ticks and four boundary ticks contribute KC_*-\beta, and the initial extractions add KH_0.

Figure 1 shows the distinction between progression of one lot and joint extraction of three distinct lots.

Finished matrix factors are carried through subsequent operations by tensor product. After the last tick, every lot has terminated, and exact coarse counts fix the number of terminal factors in every oriented history class. The next section computes their dimensions and then combines that count with the yield K(H_0+C_*)-\beta to obtain the rank constraint.

6 Terminal dimensions and the rank comparison

The terminal factors have either a zero coordinate or length one. Their dimensions can be counted directly, including the restrictions on their prescribed statistics. We first show that the completed ideal outputs restrict to one common oriented matrix tensor. We then combine its volume with the finite schedule’s yield and compare ranks. Write

for the number of labeled weight words of length \ell and weight sum j. With the amounts and laws of Section 5, define

where g is sorted, t and u retain their coordinate labels, and

In these sums, infeasible or zero-mass populations are omitted.

6.1 Finite extraction and the rank comparison

We now combine the schedule of Section 5 with the terminal dimensions just established. The finite statement records both the boundary deficit and the order in which the data are fixed.

Lemma 2.2 bounds the rank of the replicated source by

Apply Lemma 2.1 to the identical outputs of Proposition 6.2, divide its logarithm by KN, and first let divisible N\to\infty. For fixed K let the approximation and tolerance losses tend to zero. The result is

Letting K\to\infty last gives the promised constraint

Only fixed finite schedules were used; no estimate uniform in a simultaneously growing K is required.

7 Exact parameters and numerical certification

We now evaluate the logarithmic yield rate H_0+C_* and terminal logarithmic volume rate S_* for one choice of distributions. The same calculation verifies positive entries of the stage-capacity vectors, the balance conditions, and S_*>0, then bounds the exponent ratio obtained from (53). Five integer arrays in Appendix A, followed by rational operations, specify this choice; no optimization procedure is part of the certificate.

For an integer argument n, define the rational weight

The initial weights, the two split-weight arrays, and the terminal weights use 223 distinct arguments of F, including the implicit zero, all between -120770 and 45052. The binary-parameter array instead supplies the fractions n/10^6 and is not passed to F. For the 223 weight arguments, exact rational evaluation gives

The truncated series is positive directly as well: for nonnegative arguments all terms are nonnegative, and for negative arguments the even Taylor partial sum lies above the positive exponential. This observation concerns ordinary real arithmetic used to choose probabilities, and imposes no restriction on the field of the tensor construction.

Complete decoding rules. All shapes and pairs below are traversed in increasing lexicographic order, and coordinate labels and array indices start at zero. For a shape s of size 2\ell, write

The arrays are consumed as follows.

1. 1.

   The 17 entries a_0,\ldots,a_{16} define the initial sorted law by

   A_g=\frac{\operatorname{mult}(g)\prod_{i=0}^2F(a_{g_i})} {\sum_{h_0\le h_1\le h_2,\,\sum h_i=16} \operatorname{mult}(h)\prod_{i=0}^2F(a_{h_i})}, \qquad \operatorname{mult}(g)=\frac{3!}{\prod_j\bigl(\#\{i:g_i=j\}\bigr)!}.

   Thus the law on ordered shapes, before coalescing permutations, is a product of three one-coordinate weights.

2. 2.

   The 118 entries in the Stage A array are read over all positive sorted g of size 16. The 54 entries in the Stage B array are read over all positive ordered t of size 8. At either parent s, set \ell=\frac12\sum_i s_i. For coordinate i=0,1,2, with k=s_i, read one integer n_{s,i}(j) for each

   \max(0,k-\ell)\le j<\lfloor k/2\rfloor, \qquad n_{s,i}(\lfloor k/2\rfloor)=0

   (the final zero consumes no entry). For b\in\mathcal B(s) put

   w_s(b)=\prod_{i=0}^2F\bigl(n_{s,i}(\min(b_i,s_i-b_i))\bigr), \qquad q_s(b)=\frac{w_s(b)}{\sum_{c\in\mathcal B(s)}w_s(c)}.

   Use P_g=q_g at Stage A and p_t=q_t at Stage B. Each is a positive product-weight law and satisfies q_s(b)=q_s(s-b) exactly.

3. 3.

   Read the 75 entries of the fourth array over positive ordered t of size 8, and then over u\in\mathcal B(t) with \max u=2. An entry n means d_{t,u}=n/10^6. These include both the zero-coordinate 022 shapes and the positive 112 shapes. The range is 0\le d_{t,u}\le0.110106.

4. 4.

   Read the 36 entries of the fifth array over all ordered t of size 8 with a zero coordinate. For each t, list the pairs

   (i,j),\qquad 0\le i\le j\le5,\qquad r_i+r_j=\max t.

   Read an integer for each pair except the last, whose integer is zero. Assign its F-weight to both (i,j) and (j,i) and normalize over ordered pairs to obtain z_t. Hence an off-diagonal weight occurs twice in the denominator, while a diagonal weight occurs once. The multiplicities D_iD_j count words at the leaf and are not included in this probability normalization.

There are 30 sorted initial shapes, 21 positive sorted initial shapes, 21 positive ordered size-8 shapes, and 24 size-8 shapes with a zero. All specified parents consume their entries, including parents whose eventual amount is zero. For example, (6,1,1) is included in the Stage B and binary traversals. Skipping it, or a zero-amount parent in the z traversal, would change the meaning of the arrays. The exact types in this construction are rational, because (54) and every normalization are rational. Only the balance fractions, and limiting tolerance choices, require subsequent rational approximation.

The complement prescriptions in Section 5 can be checked without logarithms. On the six statistic slots, \kappa is an involution with D_{\kappa(i)}=D_i and r_{\kappa(i)}=4-r_i. At a 022 child it fixes both slots 2 and 3, so the common parameter on the two nonzero sides gives exactly matching laws. At zero-coordinate length-four shapes the other side receives the pushforward of z_t in both slots. These identities, including all zero-axis cases, are checked with exact integers and fractions by the archived verifier. Complementary child shapes need not have equal parameters: for instance

They retain their separate prescriptions throughout the contractions.

Finite contractions. Here is an explicit evaluation rule for the conditional entropies appearing in the capacities. For a finite nonnegative vector x, let

Thus \mathcal K(x)=M H(x/M) when M=\sum_i x_i>0, and \mathcal K(0)=0. Given a parent s, its split law q, a priority (X,Y,Z), and half-laws Q_{b,W}, form the ordered pair law

For W=Y, let \mathcal I_W=\{b:b_Z=0\}; for W=Z, let \mathcal I_W=\{b:b_Xb_Y=0\}. The grouped entropy is exactly

The capacity vector is

At A substitute (s,q,Q)=(g,P_g,V) and weight by A_g; at B substitute (t,p_t,v_{t,\cdot,\cdot}) and weight by m_t, with the priorities already specified. This rule uses each parent once. Child amounts and leaf volumes use both halves as in Proposition 6.1. Along with the formulas for H_0,B_*,T,S_0,S_1,S_2, it specifies only finite additions, multiplications, divisions, and logarithms of rational numbers.

The integer tables and their full traversal are sufficient to reproduce this comparison. The verification package includes a readable assignment table and both interval outputs; verification requires Python 3.10 or later and mpmath 1.3.0, with no optimization software or external data.

A Exact integer parameter tables

These five arrays, with the traversals in Section 7, specify all rational distributions used in the construction. Every integer is exact; line breaks carry no meaning. Array indices start at zero.

Initial shape weights: 17 entries (a).

 -55839  -36137  -17449   -1780   11561   22640   31188   36731   38593   35898
  29051   18387    3823  -14569  -39776  -38598  -23708

Stage A split weights: 118 entries (P).

  -3070     295  -20546   -1514  -38211   -9654   -7530   -2765  -55230  -16412
 -14246   -5912  -78106  -32809   -7009  -26324  -13519   -3592  -96458  -47439
 -16217  -46871  -25058   -9643  -95643  -62269  -28725   -8576   -2535   -2550
 -34711   -7207   -3270   -6376  -53221  -15352   -3477  -14828   -4187  -74924
 -32439   -7231   -3578  -24599   -8700  -92989  -46655  -16926   -3517  -42976
 -20283   -5132 -107049  -63201  -31013   -9730   -3705  -67421  -35684  -13735
 -68829  -36752  -13993   -7658   -7586  -76746  -33496   -7329   -7447  -17336
  -4721  -96770  -49297  -17874   -7143  -30044  -10107 -116558  -68325  -33467
 -10424   -7476  -51341  -24711   -5530  -76548  -41988  -15608  -17266   -4357
 -17106   -4343 -120770  -70820  -34294  -10580  -16819   -4315  -32943   -9992
 -83616  -44202  -16154  -17098   -4371  -56609  -25990   -5564  -56356  -25900
  -5561  -33052   -9918  -32951   -9906  -57255  -26128   -5560

Stage B split weights: 54 entries (p).

 -39594   -5561  -55254  -15178  -62331  -19672  -54917  -18539  -16455  -32184
  -5716  -11688   -5527  -53009   -6669   -6669  -64938  -20286   -6616  -26336
 -26429   -6696  -60888  -19760   -6690   -5724  -32216  -15829  -58477  -18987
 -26339   -6619  -26393  -26340  -26359   -6620  -16239  -55176  -18587  -55107
 -18571  -16272  -60868  -19755   -6696   -6692  -55133  -18580  -16247  -32128
  -5727  -32138   -5725    -122

Binary parameters: 75 entries (d).

     63   97655       0   42132   92966    1204   42148   95604   41743    3057
 109933   42092    3747   41991       1  100622   42166  103562    9039   42157
 103577   42165   63582  110082    4584   42175  104091   38838  102383  104793
  42126   11814   63338   42165  104864    3587   42166  110086    2207   94768
  42166  104185    4735   38889  110065   42166  102372  104314   38956    4876
 102395   42166  110068    2953   42166   96000   41863   95723    3031   63321
  42040   42174  104662   11860  104902   42189    2967   96042   42047  109872
   3986   42200    3834  110106   60257

Terminal length-four weights: 36 entries (z).

 -11037  -36170   -4779   23107  -12831   29263   45052   22289   -6216   23895
 -14326  -40670   -9623  -34674  -12708  -36610   -2174   21564   -5587   22521
  -9766   28961   43809   22299  -12216   28778   44147   22176   -7811   21870
  -6053   23786    -166      94     -52      17