Proof overview

We use the Coppersmith–Winograd tensor with parameter \(5\), denoted \(\mathrm{CW}_5\). Section 2 defines it and proves that the rank of its \(m\)th 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 \(\mathrm{CW}_5^{\otimes\ell}\). On each side the variables of \(\mathrm{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.

Exact rank and the arithmetic exponent

Put \(R_d=\operatorname{R}(\langle d,d,d\rangle)\) and \[ w=\inf_{d\geq2}\frac{\log R_d}{\log d}, \qquad d\text{ an integer}. \tag{2}\] 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, \[ R_d\geq d^w\qquad(d\geq1), \tag{3}\] where \(R_1=1\) handles the unit case.

Let \(\omega\) denote the arithmetic exponent of square matrix multiplication over \(\mathbb 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 \(\mathbb F\). At size \(d^k\) the resulting arithmetic cost satisfies \[C_k\leq R_d C_{k-1}+O_d(d^{2k}).\] 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 \[ \omega\leq w. \tag{4}\]

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 \[ \operatorname{R}(\langle h,h,h\rangle) \leq R_d^{\lceil\log_d h\rceil} \leq C_\varepsilon h^{w+\varepsilon}, \qquad C_\varepsilon=R_d. \tag{5}\] 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 (Schönhage 1981), with a proof from exact rank.

The hypothesis in Lemma 2 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.

An integer coefficient construction

The relation between approximate bilinear identities and exact algorithms was studied by Bini (Bini 1980). 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 (Coppersmith and Winograd 1990) \[\begin{align*} \mathrm{CW}_q={}&\sum_{i=1}^q (x_0y_iz_i+x_iy_0z_i+x_iy_iz_0)\\ &+x_{q+1}y_0z_0+x_0y_{q+1}z_0+x_0y_0z_{q+1}. \end{align*}\] We use \(q=5\). The following exact-rank estimate makes the field independence and the polynomial overhead explicit.

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 \(\mathrm{CW}_q\) has total weight \(2\). A strand of length \(\ell\) is a copy of \(\mathrm{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 \[M=[z^{g_1}](1+qz+z^2)^\ell.\] 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.

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 \[ u_X+u_Y+u_Z=s_r. \tag{10}\] 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. 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. 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.

Entropy and a common modular hash

For a fixed alphabet \(\mathcal A\), the number of words of type \(p\) is \[ \frac{m!}{\prod_a(mp(a))!} =\exp\bigl(mH(p)+O(\log(m+2))\bigr). \tag{16}\] 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 \[p(i,j,k)=Z^{-1}a_i b_j c_k\quad ((i,j,k)\in\Omega_r).\] 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, \[\sum_{q(u)>0}q(u)\log\frac{p(u)}{q(u)} \le \sum_{q(u)>0}(p(u)-q(u))\le0,\] 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 \[ |\mathcal T_N|=\exp\bigl(NA_{\rm amb}+O(\log N)\bigr). \tag{17}\] 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 \[\frac{\prod_i(mp_{r,X}(i))!}{\prod_u(mq_r(u))!} =\exp\bigl(m(H(q_r)-H(p_{r,X}))+O(\log N)\bigr).\] Summing over the polynomially many types and using maximality yields the degree bound \[ \#\{\text{ambient triples at a fixed $X$ block}\} \le \exp\bigl(N(A_{\rm amb}-C_X)+O(\log N)\bigr). \tag{18}\] 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 \[ \log M=N(A_{\rm amb}-E+\delta)+O(1). \tag{19}\] There is a set \(U\subset\mathbb Z/M\mathbb Z\) with \[ \log|U|=\log M-O(\sqrt{\log M}) \tag{20}\] and no nonconstant three-term arithmetic progression. Here is a version of Behrend’s construction (Behrend 1946) 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 \[ x(I)=a+\langle v,I\rangle,\quad y(J)=b'+\langle v,J\rangle,\quad z(K)=\frac{a+b'+\langle v,S-K\rangle}{2}. \tag{21}\] 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 \[ \Pr(S_e)=h_M:=\frac{|U|}{M^2}. \tag{22}\] 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 \[t+\langle v,\Delta I\rangle,\quad t+\langle v,\Delta J\rangle,\quad t-\tfrac12\langle v,\Delta K\rangle.\] 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 \[ \Pr(S_{e'}\mid S_e)=\frac1M \quad\text{for distinct triples sharing a block}. \tag{23}\] No further hash-dependent event is included in this conditioning.

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.

Sequential assignment by variable deletion

Choose \(\eta,\chi>0\) sufficiently small that the error in Lemma 5 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 5 and (23) then give, for some constant \(c>0\), \[ \Pr(R_{e,v}\mid S_e) \le \exp(-cN), \tag{26}\] 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 6 supplies the uniform deterministic mask bound on these orbits. The completion of Theorem 4 in Section 4 combines that bound with (26), selects exponentially many good assignments using (17) and (22), and applies Lemma 7 to reconstruct their ideal outputs.

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.

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.

Completing the joint extraction

Composition and subdivision

To iterate Theorem 4, 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 \[ \bigotimes_{i=1}^j U(m_i,\nu,\eta_i) \preceq U\left(\sum_{i=1}^j m_i,\nu,\eta\right). \tag{30}\] 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 4 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.

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 \[ \mu=\sum_g A_g\rho_g,\qquad H_0=H(\mu). \tag{31}\] 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 4.

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 \[|t|=8,\qquad 0\leq t\leq g,\] 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: \[ \begin{array}{c|rrrrrr} i&0&1&2&3&4&5\\ \hline \text{weight pair}&00&01&11&02&12&22\\ r_i&0&1&2&2&3&4\\ D_i&1&10&25&2&10&1 \end{array} \qquad \kappa=(5,4,2,3,1,0). \tag{32}\] 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 \[ V_{t,W}=\sum_u p_t(u)\, v_{t,u,W}\otimes v_{t,t-u,W}. \tag{33}\] 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 4.

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 \[ (1,1,6),\quad(1,2,5),\quad(1,3,4),\quad(2,2,4),\quad(3,2,3). \tag{34}\] 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 \[ \begin{array}{c|cccc} \text{left shape}&(1,1,0)&(0,0,2)&(1,0,1)&(0,1,1)\\ \hline \text{probability}&d_{t,u}/2&d_{t,u}/2&(1-d_{t,u})/2&(1-d_{t,u})/2. \end{array} \tag{35}\] 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 \[h_b(d)=H(1-d,d)+d\log2.\] 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 6 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.

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 \[ m_t=2\sum_{\min g>0}A_gP_g(t),\qquad m_{t,u}=2m_t p_t(u)\quad(\min t>0). \tag{36}\] 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 \[\bigl(H(p_X),\ H(D_Y)-2J_Y,\ H(D_Z)-2J_Z\bigr),\] 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 \[\begin{align*} T&=\sum_{\min t>0,\,\min u>0}m_{t,u}, & B_*&=\sum_{\min t>0,\,\min u>0} m_{t,u}\frac{2\log2+h_b(d_{t,u})}{3},\\ C_*&=B_*+\frac13\sum_{i=0}^2(L_A+L_B)_i. \tag{37}\end{align*}\] Suppose, as the numerical certificate verifies, that \[ T\log2>B_*,\qquad C_*-(L_A+L_B)_i<T\log2\quad(0\leq i<3). \tag{38}\] The denominator and each numerator below are positive by (38). The numbers \[ \lambda_i= \frac{T\log2-C_*+(L_A+L_B)_i}{3(T\log2-B_*)} \qquad(0\leq i<3) \tag{39}\] sum to \(1\): their numerators sum to \(3(T\log2-B_*)\) by [eq:balance-data]. 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 \[\begin{align*} (L_C)_i &=T\log2-\lambda_i \sum_{\min t>0,\,\min u>0}m_{t,u} \bigl(\log2-h_b(d_{t,u})\bigr)\\ &=T\log2-3\lambda_i(T\log2-B_*) =C_*-(L_A+L_B)_i. \tag{40}\end{align*}\] Consequently \(L_A+L_B+L_C=(C_*,C_*,C_*)\).

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 4 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, \[ \phi=\sigma\circ\rho_h^{-1}. \tag{41}\] 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 11. 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 4 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 \[ A;\quad A+B;\quad \underbrace{A+B+C;\ \ldots;\ A+B+C}_{K-2\text{ ticks}}; \quad B+C;\quad C. \tag{42}\] 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 \[\frac16(L_A+L_B+L_C)=\frac16(C_*,C_*,C_*).\] 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 \[\min L_A,\qquad \min(L_A+L_B),\qquad \min(L_B+L_C),\qquad \min L_C,\] 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 \[ \beta=2C_*-\min L_A-\min(L_A+L_B) -\min(L_B+L_C)-\min L_C. \tag{43}\] 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 11 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.

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 3 bounds the rank of the replicated source by \[\exp(o_K(N))\,7^{8KN}\binom{24KN+2}{2}.\] Apply Lemma 2 to the identical outputs of Proposition 10, 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 \[H_0+C_*-\frac{\beta}{K}+\frac{w}{3}S_*\leq8\log7.\] Letting \(K\to\infty\) last gives the promised constraint \[ \boxed{\displaystyle H_0+C_*+\frac{w}{3}S_*\leq8\log7.} \tag{53}\] Only fixed finite schedules were used; no estimate uniform in a simultaneously growing \(K\) is required.

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 \[\mathcal B(s)=\{b\in\mathbb Z_{\ge0}^3: b_0+b_1+b_2=\ell,\ b_i\le s_i\ (0\le i<3)\}.\] The arrays are consumed as follows.

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. 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. 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. 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 \[d_{(1,3,4),(0,2,2)}=\frac{92966}{10^6},\qquad d_{(1,3,4),(1,1,2)}=\frac{1204}{10^6}.\] 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 \[\mathcal K(x)=\left(\sum_i x_i\right)\log\left(\sum_i x_i\right) -\sum_i x_i\log x_i, \qquad 0\log0=0.\] 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 \[D_W(i,j)=\sum_{b\in\mathcal B(s)}q(b)Q_{b,W}(i)Q_{s-b,W}(j).\] 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 \[ J_W=\sum_{b\in\mathcal I_W}q(b)\mathcal K(Q_{b,W}) +\sum_{k=0}^{s_W} \mathcal K\left(\sum_{\substack{b\notin\mathcal I_W\\b_W=k}} q(b)Q_{b,W}\right). \tag{56}\] The capacity vector is \[\left(\mathcal K\bigl((\sum_{b:b_X=k}q(b))_k\bigr), \mathcal K(D_Y)-2J_Y,\mathcal K(D_Z)-2J_Z\right).\] 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 9. 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.

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