Introduction
For a fixed field F \mathbb{F} F ω = ω F \omega= \omega_{\mathbb{F}} ω = ω F τ \tau τ n × n n \times n n × n F \mathbb{F} F O ( n τ + o ( 1 ) ) O(n^{\tau+o(1)}) O ( n τ + o ( 1 ) )
Strassen’s seven-product algorithm for 2 × 2 2 \times2 2 × 2 log 2 7 \log_2 7 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 ω < 2.3728596 \omega< 2.3728596 ω < 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 ω < 2.371177 \omega< 2.371177 ω < 2.371177 [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.
Table 1.
Theorem 1.1. Over every fixed field F \mathbb{F} F the arithmetic exponent of square matrix multiplication satisfies
ω F < 2.371054886006746 < 2.371054887. \omega_{\mathbb{F}} < 2.371054886006746 < 2.371054887. ω F < 2.371054886006746 < 2.371054887. 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.
Proof overview
We use the Coppersmith–Winograd tensor with parameter 5, denoted C W 5 \mathrm{CW}_5 CW 5 m m m 7 m 7^m 7 m m m m strand of length ℓ \ell ℓ C W 5 ⊗ ℓ \mathrm{CW}_5^{\otimes\ell} CW 5 ⊗ ℓ C W 5 \mathrm{CW}_5 CW 5 0 , … , 6 0,\ldots,6 0 , … , 6 0 , 1 , 1 , 1 , 1 , 1 , 2 0,1,1,1,1,1,2 0 , 1 , 1 , 1 , 1 , 1 , 2 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 ∈ R 3 \mathbf{v}_r \in\mathbb{R}^3 v r ∈ R 3
∑ r min W v r , W ≤ min W ∑ r v r , W . \sum_r \min_W v_{r,W} \leq\min_W \sum_r v_{r,W}. r ∑ W min v r , W ≤ W min r ∑ v r , W . 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 N N C / N C/N C / N C C C
Staggering and the final rank comparison. A lot contains N N N 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.
Figure 1. Mixed-depth extraction with finite boundaries (K ≥ 2 K \ge2 K ≥ 2 σ \sigma σ (42) ; they incur only the fixed deficit β \beta β K = 2 K = 2 K = 2
Write H 0 H_0 H 0 C ∗ C_* C ∗ S ∗ S_* S ∗
ω F ≤ 3 ( 8 log 7 − H 0 − C ∗ ) S ∗ . (1) \omega_F \le\frac{3(8\log7-H_0-C_*)}{S_*}. \tag*{(1)} ω F ≤ S ∗ 3 ( 8 log 7 − H 0 − C ∗ ) . (1) For each fixed number of lots, we first take the divisible strand count N N N S ∗ > 0 S_* > 0 S ∗ > 0 (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.
Rank and the basic tensor
Fix an arbitrary field F \mathbb{F} F F \mathbb{F} F R ( T ) R(T) R ( T ) T T T 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 a,b,c a , b , c
⟨ a , b , c ⟩ = ∑ i = 1 a ∑ j = 1 b ∑ k = 1 c x i j y j k z k i . \langle a,b,c\rangle=\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c}x_{ij}y_{jk}z_{ki}. ⟨ a , b , c ⟩ = i = 1 ∑ a j = 1 ∑ b k = 1 ∑ c x ij y j k z k i . This is the tensor for multiplying an a × b a \times b a × b b × c b \times c b × c volume is a b c abc ab c
⟨ a , b , c ⟩ ⊗ ⟨ a ′ , b ′ , c ′ ⟩ ≅ ⟨ a a ′ , b b ′ , c c ′ ⟩ . \langle a,b,c\rangle\otimes\langle a',b',c'\rangle\cong\langle aa',bb',cc'\rangle. ⟨ a , b , c ⟩ ⊗ ⟨ a ′ , b ′ , c ′ ⟩ ≅ ⟨ a a ′ , b b ′ , c c ′ ⟩ . Cyclically permuting the three variable spaces replaces the parameters by ( b , c , a ) (b,c,a) ( b , c , a ) ( c , a , b ) (c,a,b) ( c , a , b )
Exact rank and the arithmetic exponent
Put R d = R ( ⟨ d , d , d ⟩ ) R_d=R(\langle d,d,d\rangle) R d = R (⟨ d , d , d ⟩)
w = inf d ≥ 2 log R d log d , d an integer . (2) w=\inf_{d\ge2}\frac{\log R_d}{\log d},\qquad d\text{ an integer}. \tag*{(2)} w = d ≥ 2 inf log d log R d , d an integer . (2) The flattening that sends a z z z d 2 d^2 d 2 d 2 d^2 d 2 ∑ j x i j y j k \sum_j x_{ij}y_{jk} ∑ j x ij y j k d 2 ≤ R d ≤ d 3 d^2 \le R_d \le d^3 d 2 ≤ R d ≤ d 3 2 ≤ w ≤ 3 2 \le w \le3 2 ≤ w ≤ 3
R d ≥ d w ( d ≥ 1 ) , (3) R_d \ge d^w \qquad(d \ge1), \tag*{(3)} R d ≥ d w ( d ≥ 1 ) , (3) where R 1 = 1 R_1=1 R 1 = 1
Let ω \omega ω F \mathbb{F} F R d R_d R d R d R_d R d x x x y y y F \mathbb{F} F d k d^k d k
C k ≤ R d C k − 1 + O d ( d 2 k ) . C_k \le R_d C_{k-1} + O_d(d^{2k}). C k ≤ R d C k − 1 + O d ( d 2 k ) . The implied constant may depend on the chosen decomposition. Since R d ≥ d 2 R_d \ge d^2 R d ≥ d 2 C k = O d ( k R d k ) C_k = O_d(kR_d^k) C k = O d ( k R d k ) R d = d 2 R_d=d^2 R d = d 2 d d d O d ( n log d R d log ( n + 1 ) ) O_d(n^{\log_d R_d}\log(n+1)) O d ( n l o g d R d log ( n + 1 )) n η n^\eta n η η > 0 \eta>0 η > 0
ω ≤ w . (4) \omega\le w. \tag*{(4)} ω ≤ w . (4) We also need a uniform upper bound on exact square rank. Given ε > 0 \varepsilon>0 ε > 0 d ≥ 2 d\ge2 d ≥ 2 θ = log d R d < w + ε \theta=\log_d R_d<w+\varepsilon θ = log d R d < w + ε h ≥ 1 h\ge1 h ≥ 1
R ( ⟨ h , h , h ⟩ ) ≤ R d ⌈ log d h ⌉ ≤ C ε h w + ε , C ε = R d . (5) R(\langle h,h,h\rangle) \le R_d^{\lceil\log_d h\rceil} \le C_\varepsilon h^{w+\varepsilon}, \qquad C_\varepsilon=R_d. \tag*{(5)} R (⟨ h , h , h ⟩) ≤ R d ⌈ l o g d h ⌉ ≤ C ε h w + ε , C ε = R d . (5) This argument uses one approximating dimension; it does not require the infimum defining w w w
We use the following identical-summand form of Schönhage’s asymptotic sum inequality [10 ] , with a proof from exact rank.
Lemma 2.1 (Direct sums of identical matrix tensors). Let s , a , b , c s,a,b,c s , a , b , c
R ( ⨁ j = 1 s ⟨ a , b , c ⟩ ) ≤ R ∗ , R\left(\bigoplus_{j=1}^{s}\langle a,b,c\rangle\right) \le R_*, R ( j = 1 ⨁ s ⟨ a , b , c ⟩ ) ≤ R ∗ , then
s ( a b c ) w / 3 ≤ R ∗ . (6) s(abc)^{w/3} \le R_*. \tag*{(6)} s ( ab c ) w /3 ≤ R ∗ . (6) Proof. First consider s s s ⟨ d , d , d ⟩ \langle d,d,d\rangle ⟨ d , d , d ⟩ s = 1 s=1 s = 1 s d w ≤ R ∗ sd^w\le R_* s d w ≤ R ∗ d = 1 d=1 d = 1 ∑ j = 1 s x j y j z j \sum_{j=1}^{s}x_jy_jz_j ∑ j = 1 s x j y j z j s s s s , d ≥ 2 s,d\ge2 s , d ≥ 2
Fix ε > 0 \varepsilon>0 ε > 0 k k k
h k = ⌊ ( s k C ε ) 1 / ( w + ε ) ⌋ . h_k=\left\lfloor\left(\frac{s^k}{C_\varepsilon}\right)^{1/(w+\varepsilon)}\right\rfloor. h k = ⌊ ( C ε s k ) 1/ ( w + ε ) ⌋ . Then h k ≥ 2 h_k\ge2 h k ≥ 2 R ( ⟨ h k , h k , h k ⟩ ) ≤ s k R(\langle h_k,h_k,h_k\rangle)\le s^k R (⟨ h k , h k , h k ⟩) ≤ s k
lim k → ∞ log h k k = log s w + ε . \lim_{k\to\infty}\frac{\log h_k}{k}=\frac{\log s}{w+\varepsilon}. k → ∞ lim k log h k = w + ε log s . The k k k s k s^k s k ⟨ d k , d k , d k ⟩ \langle d^k,d^k,d^k\rangle ⟨ d k , d k , d k ⟩ R ∗ k R_*^k R ∗ k r r r ⟨ h k , h k , h k ⟩ \langle h_k,h_k,h_k\rangle ⟨ h k , h k , h k ⟩ r ≤ s k r\le s^k r ≤ s k r r r ⟨ d k , d k , d k ⟩ \langle d^k,d^k,d^k\rangle ⟨ d k , d k , d k ⟩ ⟨ d k h k , d k h k , d k h k ⟩ \langle d^kh_k,d^kh_k,d^kh_k\rangle ⟨ d k h k , d k h k , d k h k ⟩
R ∗ k ≥ ( d k h k ) w . R_*^k \ge(d^kh_k)^w. R ∗ k ≥ ( d k h k ) w . Taking logarithms, dividing by k k k k → ∞ k \to\infty k → ∞ ε \varepsilon ε
log R ∗ ≥ w log d + w w + ε log s . \log R_* \ge w\log d+\frac{w}{w+\varepsilon}\log s. log R ∗ ≥ w log d + w + ε w log s . Letting ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 s d w ≤ R ∗ sd^w \le R_* s d w ≤ R ∗
For the rectangular case, let U = ⨁ j = 1 s ⟨ a , b , c ⟩ U=\bigoplus_{j=1}^s\langle a,b,c\rangle U = ⨁ j = 1 s ⟨ a , b , c ⟩ U U U s 3 s^3 s 3
⟨ a , b , c ⟩ ⊗ ⟨ b , c , a ⟩ ⊗ ⟨ c , a , b ⟩ ≅ ⟨ a b c , a b c , a b c ⟩ , \langle a,b,c\rangle\otimes\langle b,c,a\rangle\otimes\langle c,a,b\rangle\cong\langle abc,abc,abc\rangle, ⟨ a , b , c ⟩ ⊗ ⟨ b , c , a ⟩ ⊗ ⟨ c , a , b ⟩ ≅ ⟨ ab c , ab c , ab c ⟩ , and the product has rank at most R ∗ 3 R_*^3 R ∗ 3 s 3 ( a b c ) w ≤ R ∗ 3 s^3(abc)^w\le R_*^3 s 3 ( ab c ) w ≤ R ∗ 3 a b c = 1 abc=1 ab c = 1
The hypothesis in Lemma 2.1 specifies one common oriented triple ( a , b , c ) (a,b,c) ( a , b , c )
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 ≥ 1 q\ge1 q ≥ 1 [5 ]
CW q = ∑ i = 1 q ( x 0 y i z i + x i y 0 z i + x i y i z 0 ) + x q + 1 y 0 z 0 + x 0 y q + 1 z 0 + x 0 y 0 z q + 1 . \operatorname{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}. CW q = i = 1 ∑ q ( x 0 y i z i + x i y 0 z i + x i y i z 0 ) + x q + 1 y 0 z 0 + x 0 y q + 1 z 0 + x 0 y 0 z q + 1 . We use q = 5 q=5 q = 5
Lemma 2.2 (Rank bound for powers of the basic tensor). Over every field and for every integer m ≥ 0 m\ge0 m ≥ 0
R ( CW q ⊗ m ) ≤ ( q + 2 ) m ( 3 m + 2 2 ) . (7) \operatorname{R}(\operatorname{CW}_q^{\otimes m})\le(q+2)^m\binom{3m+2}{2}. \tag*{(7)} R ( CW q ⊗ m ) ≤ ( q + 2 ) m ( 2 3 m + 2 ) . (7) Proof. We use the Laurent-polynomial identity of Coppersmith and Winograd [5 ] , Section 7, equation (10), over the integers, with a formal variable t t t X 1 = ∑ i = 1 q x i X_1=\sum_{i=1}^{q}x_i X 1 = ∑ i = 1 q x i Y 1 = ∑ i = 1 q y i Y_1=\sum_{i=1}^{q}y_i Y 1 = ∑ i = 1 q y i Z 1 = ∑ i = 1 q z i Z_1=\sum_{i=1}^{q}z_i Z 1 = ∑ i = 1 q z i
P ( t ) = t − 2 ∑ i = 1 q ( x 0 + t x i ) ( y 0 + t y i ) ( z 0 + t z i ) − t − 3 ( x 0 + t 2 X 1 ) ( y 0 + t 2 Y 1 ) ( z 0 + t 2 Z 1 ) + ( t − 3 − q t − 2 ) ( x 0 + t 3 x q + 1 ) ( y 0 + t 3 y q + 1 ) ( z 0 + t 3 z q + 1 ) . (8) \begin{aligned}
P(t)={}&t^{-2}\sum_{i=1}^{q}(x_0+tx_i)(y_0+ty_i)(z_0+tz_i)\\
&-t^{-3}(x_0+t^2X_1)(y_0+t^2Y_1)(z_0+t^2Z_1)\\
&+(t^{-3}-qt^{-2})(x_0+t^3x_{q+1})(y_0+t^3y_{q+1})(z_0+t^3z_{q+1}). \tag*{(8)}
\end{aligned} P ( t ) = t − 2 i = 1 ∑ q ( x 0 + t x i ) ( y 0 + t y i ) ( z 0 + t z i ) − t − 3 ( x 0 + t 2 X 1 ) ( y 0 + t 2 Y 1 ) ( z 0 + t 2 Z 1 ) + ( t − 3 − q t − 2 ) ( x 0 + t 3 x q + 1 ) ( y 0 + t 3 y q + 1 ) ( z 0 + t 3 z q + 1 ) . (8) The only possible negative degrees are − 3 -3 − 3 − 2 -2 − 2 − 1 -1 − 1
( − 1 + 1 ) x 0 y 0 z 0 , ( q − q ) x 0 y 0 z 0 , ( 1 − 1 ) ( X 1 y 0 z 0 + x 0 Y 1 z 0 + x 0 y 0 Z 1 ) . (-1+1)x_0y_0z_0,\qquad(q-q)x_0y_0z_0,\qquad(1-1)(X_1y_0z_0+x_0Y_1z_0+x_0y_0Z_1). ( − 1 + 1 ) x 0 y 0 z 0 , ( q − q ) x 0 y 0 z 0 , ( 1 − 1 ) ( X 1 y 0 z 0 + x 0 Y 1 z 0 + x 0 y 0 Z 1 ) . The degree-zero coefficient is precisely C W q \mathrm{CW}_q CW q P ( t ) = C W q + t Q ( t ) P(t)=\mathrm{CW}_q+tQ(t) P ( t ) = CW q + tQ ( t ) Q Q Q
[ t 0 ] P ( t ) ⊗ m = C W q ⊗ m . (9) [t^0]P(t)^{\otimes m}=\mathrm{CW}_q^{\otimes m}. \tag*{(9)} [ t 0 ] P ( t ) ⊗ m = CW q ⊗ m . (9) These coefficient identities remain valid after reduction to any field.
Regard (8) as q + 2 q+2 q + 2 x x x x x x
{ − 2 , − 1 } , { − 3 , − 1 } , { − 3 , − 2 , 0 , 1 } . \{-2,-1\},\qquad\{-3,-1\},\qquad\{-3,-2,0,1\}. { − 2 , − 1 } , { − 3 , − 1 } , { − 3 , − 2 , 0 , 1 } . The last set includes both terms of t − 3 − q t − 2 t^{-3}-qt^{-2} t − 3 − q t − 2
Expanding P ( t ) ⊗ m P(t)^{\otimes m} P ( t ) ⊗ m ( q + 2 ) m (q+2)^m ( q + 2 ) m A ( t ) B ( t ) C ( t ) A(t)B(t)C(t) A ( t ) B ( t ) C ( t )
A ( t ) = ∑ a = − 3 m m A a t a , B ( t ) = ∑ b = 0 3 m B b t b , C ( t ) = ∑ c = 0 3 m C c t c . A(t)=\sum_{a=-3m}^{m}A_at^a,\qquad B(t)=\sum_{b=0}^{3m}B_bt^b,\qquad C(t)=\sum_{c=0}^{3m}C_ct^c. A ( t ) = a = − 3 m ∑ m A a t a , B ( t ) = b = 0 ∑ 3 m B b t b , C ( t ) = c = 0 ∑ 3 m C c t c . Here each coefficient is one linear form in the corresponding tensor-product variables. The constant coefficient of this product is
∑ b , c ≥ 0 b + c ≤ 3 m A − b − c B b C c , \sum_{\substack{b,c\geq0\\b+c\leq3m}}A_{-b-c}B_bC_c, b , c ≥ 0 b + c ≤ 3 m ∑ A − b − c B b C c , a sum of at most ( 3 m + 2 2 ) \binom{3m+2}{2} ( 2 3 m + 2 ) ( q + 2 ) m (q+2)^m ( q + 2 ) m (9) proves (7) . For m = 0 m=0 m = 0 □ \square □
Strands and shapes
Give the label 0 weight 0, the labels 1 , … , q 1,\ldots,q 1 , … , q q + 1 q+1 q + 1 C W q \mathrm{CW}_q CW q strand of length ℓ \ell ℓ C W q ⊗ ℓ \mathrm{CW}_q^{\otimes\ell} CW q ⊗ ℓ ℓ \ell ℓ g = ( g 0 , g 1 , g 2 ) g=(g_0,g_1,g_2) g = ( g 0 , g 1 , g 2 ) g 0 + g 1 + g 2 = 2 ℓ g_0+g_1+g_2=2\ell g 0 + g 1 + g 2 = 2 ℓ T ℓ , g T_{\ell,g} T ℓ , g g 0 , g 1 , g 2 g_0,g_1,g_2 g 0 , g 1 , g 2 g g g positive if all three coordinates are positive. When ℓ \ell ℓ u u u g − u g-u g − u 0 ≤ u ≤ g 0\leq u\leq g 0 ≤ u ≤ g ∑ i u i = ℓ \sum_i u_i=\ell ∑ i u i = ℓ
A zero coordinate gives an especially simple terminal tensor. Suppose g 0 = 0 g_0=0 g 0 = 0 x x x y y y z z z q + 1 q+1 q + 1 i ∈ { 1 , … , q } i\in\{1,\ldots,q\} i ∈ { 1 , … , q } T ℓ , g T_{\ell,g} T ℓ , g ⟨ 1 , 1 , M ⟩ \langle1,1,M\rangle ⟨ 1 , 1 , M ⟩
M = [ z g 1 ] ( 1 + q z + z 2 ) ℓ . M=[z^{g_1}](1+qz+z^2)^\ell. M = [ z g 1 ] ( 1 + q z + z 2 ) ℓ . For g 1 = 0 g_1=0 g 1 = 0 g 2 = 0 g_2=0 g 2 = 0 ⟨ M , 1 , 1 ⟩ \langle M,1,1\rangle ⟨ M , 1 , 1 ⟩ ⟨ 1 , M , 1 ⟩ \langle1,M,1\rangle ⟨ 1 , M , 1 ⟩ M M M
The constituent-stage analysis of [1 ] 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 ] , 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 p p H ( p ) = − ∑ a p ( a ) log p ( a ) H(p) = -\sum_a p(a)\log p(a) H ( p ) = − ∑ a p ( a ) log p ( a ) 0 log 0 = 0 0\log0 = 0 0 log 0 = 0 type p p p p p p θ \theta θ θ \theta θ N N N
The data of a joint step
Index the populations by a finite set R \mathcal{R} R r r r m r = c r N m_r = c_rN m r = c r N F r F_r F r c r > 0 c_r > 0 c r > 0 { 0 , … , 16 } \{0,\ldots,16\} { 0 , … , 16 } F r F_r F r Ω r \Omega_r Ω r u = ( u X , u Y , u Z ) u = (u_X,u_Y,u_Z) u = ( u X , u Y , u Z )
u X + u Y + u Z = s r . (10) u_X + u_Y + u_Z = s_r. \tag*{(10)} u X + u Y + u Z = s r . (10) Here X , Y , Z X,Y,Z X , Y , Z ⨂ r F r ⊗ m r \bigotimes_r F_r^{\otimes m_r} ⨂ r F r ⊗ m r
Choose a rational law p r p_r p r Ω r \Omega_r Ω r Ω r \Omega_r Ω r p r p_r p r Ω r \Omega_r Ω r
An ordinary population delivers the full tensor block at each selected triple u u u
A sharing population consists of copies of T ℓ , g T_{\ell,g} T ℓ , g ℓ \ell ℓ ∑ W g W = 2 ℓ \sum_W g_W = 2\ell ∑ W g W = 2 ℓ u W u_W u W
Ω r = { u : 0 ≤ u ≤ g , ∑ W u W = ℓ } , T ℓ , g ∣ u = T ℓ / 2 , u ⊗ T ℓ / 2 , g − u . \Omega_r = \{u : 0 \le u \le g,\ \sum_W u_W = \ell\}, \qquad T_{\ell,g}|_u = T_{\ell/2,u} \otimes T_{\ell/2,g-u}. Ω r = { u : 0 ≤ u ≤ g , W ∑ u W = ℓ } , T ℓ , g ∣ u = T ℓ /2 , u ⊗ T ℓ /2 , g − u . Assume p r ( u ) = p r ( g − u ) p_r(u) = p_r(g-u) p r ( u ) = p r ( g − u ) W W W A r , W \mathcal{A}_{r,W} A r , W ρ W \rho_W ρ W u u u p r ( u ) > 0 p_r(u) > 0 p r ( u ) > 0 ν r , u , W \nu_{r,u,W} ν r , u , W ρ W − 1 ( u W ) \rho_W^{-1}(u_W) ρ 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 e e p r p_r p r e e e ν r , u , W \nu_{r,u,W} ν r , u , W ( r , u , half ) (r,u,\text{half}) ( r , u , half ) u u u ν r , g − u , W \nu_{r,g-u,W} ν r , g − u , W ideal output Q e Q_e Q e Q N Q_N Q N e e e useful for e e e
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 r r
D W = ∑ u ∈ Ω r p ( u ) ν u , W ⊗ ν g − u , W . (11) D_W=\sum_{u\in\Omega_r}p(u)\,\nu_{u,W}\otimes\nu_{g-u,W}. \tag*{(11)} D W = u ∈ Ω r ∑ p ( u ) ν u , W ⊗ ν g − u , W . (11) 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 D_{r,W} D r , W (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 θ 2 θ 2\theta 2 θ
Compatibility groups and capacities. The extraction will first separate targets by their X X X X X X Y Y Y Z Z Z
I Y = { u ∈ supp p : u Z = 0 } , I Z = { u ∈ supp p : u X u Y = 0 } . (12) I_Y=\{u\in\operatorname{supp}p:u_Z=0\},\qquad I_Z=\{u\in\operatorname{supp}p:u_Xu_Y=0\}. \tag*{(12)} I Y = { u ∈ supp p : u Z = 0 } , I Z = { u ∈ supp p : u X u Y = 0 } . (12) A zero Z Z Z X X X Y Y Y Z Z Z Y Y Y X X X X X X Y Y Y X X X Y Y Y Z Z Z W W W D W D_W D W W ∈ { Y , Z } W\in\{Y,Z\} W ∈ { Y , Z } G W \mathcal{G}_W G W { u } \{u\} { u } u ∈ I W u\in I_W u ∈ I W { u ∈ supp p ∖ I W : u W = i } \{u\in\operatorname{supp}p\setminus I_W:u_W=i\} { u ∈ supp p ∖ I W : u W = i } p ( G ) = ∑ u ∈ G p ( u ) p(G)=\sum_{u\in G}p(u) p ( G ) = ∑ u ∈ G p ( u )
J W = ∑ G ∈ G W p ( G ) H ( ∑ u ∈ G p ( u ) ν u , W p ( G ) ) , W ∈ { Y , Z } . (13) J_W=\sum_{G\in\mathcal{G}_W}p(G)H\left(\frac{\sum_{u\in G}p(u)\nu_{u,W}}{p(G)}\right),\qquad W\in\{Y,Z\}. \tag*{(13)} J W = G ∈ G W ∑ p ( G ) H ( p ( G ) ∑ u ∈ G p ( u ) ν u , W ) , W ∈ { Y , Z } . (13) The entropy J W J_W J W 2 J W 2J_W 2 J W H ( D W ) H(D_W) H ( D W )
C r , X = H ( p r , X ) , C r , Y = H ( D r , Y ) − 2 J r , Y , C r , Z = H ( D r , Z ) − 2 J r , Z . (14) C_{r,X}=H(p_{r,X}),\qquad C_{r,Y}=H(D_{r,Y})-2J_{r,Y},\qquad C_{r,Z}=H(D_{r,Z})-2J_{r,Z}. \tag*{(14)} C r , X = H ( p r , X ) , C r , Y = H ( D r , Y ) − 2 J r , Y , C r , Z = H ( D r , Z ) − 2 J r , Z . (14) Only the law of half-shapes is assumed invariant under u ↦ g − u u\mapsto g-u u ↦ g − u ν u , W \nu_{u,W} ν u , W ν g − u , W \nu_{g-u,W} ν g − u , W
For an ordinary population no compatibility restriction is needed, and the capacities are simply
C r , X = H ( p r , X ) , C r , Y = H ( p r , Y ) , C r , Z = H ( p r , Z ) . C_{r,X}=H(p_{r,X}),\qquad C_{r,Y}=H(p_{r,Y}),\qquad C_{r,Z}=H(p_{r,Z}). C r , X = H ( p r , X ) , C r , Y = H ( p r , Y ) , C r , Z = H ( p r , Z ) . The counting arguments below give a common interpretation: each C r , W C_{r,W} C r , W W W W
Theorem 3.1 (Heterogeneous joint step). Let $B_N) be the restriction of ⨂ r ∈ R F r ⊗ m r \bigotimes_{r\in\mathcal{R}}F_r^{\otimes m_r} ⨂ r ∈ R F r ⊗ m r by the inherited masks just specified, with the population data above. Set
A a m b = ∑ r ∈ R c r H ( p r ) , C W = ∑ r ∈ R c r C r , W , E = min { C X , C Y , C Z } . (15) A_{\mathrm{amb}}=\sum_{r\in\mathcal{R}}c_rH(p_r),\qquad C_W=\sum_{r\in\mathcal{R}}c_rC_{r,W},\qquad E=\min\{C_X,C_Y,C_Z\}. \tag*{(15)} A amb = r ∈ R ∑ c r H ( p r ) , C W = r ∈ R ∑ c r C r , W , E = min { C X , C Y , C Z } . (15) If E > 0 E>0 E > 0 then for every ε > 0 \varepsilon>0 ε > 0 one can choose positive output widths, as small as desired, such that for all sufficiently large N N N divisible by the fixed type denominators, a direct sum of exp ( o ( N ) ) \exp(o(N)) exp ( o ( N )) independent copies of B N B_N B N has a linear restriction to at least ⌊ exp ( N ( E − ε ) ) ⌋ \lfloor\exp(N(E-\varepsilon))\rfloor ⌊ exp ( N ( E − ε ))⌋ independent copies of Q N Q_N Q N
The choices of populations, rational laws, positive widths, and divisibility requirements precede the limit N → ∞ N\to\infty N → ∞ In particular, the assertion does not require common strand lengths.
We first bound hash survival and assignment collisions. The sequential X , Y , Z X,Y,Z X , Y , Z exp ( o ( N ) ) \exp(o(N)) exp ( o ( N ))
Entropy and a common modular hash
For a fixed alphabet A \mathcal{A} A p p p
m ! ∏ a ( m p ( a ) ) ! = exp ( m H ( p ) + O ( log ( m + 2 ) ) ) . (16) \frac{m!}{\prod_{a}(mp(a))!}=\exp\left(mH(p)+O(\log(m+2))\right). \tag*{(16)} ∏ a ( m p ( a ))! m ! = exp ( m H ( p ) + O ( log ( m + 2 )) ) . (16) Indeed, comparing the sum ∑ j = 1 n log j \sum_{j=1}^{n}\log j ∑ j = 1 n log j log ( n ! ) = n log n − n + O ( log ( n + 2 ) ) \log(n!)=n\log n-n+O(\log(n+2)) log ( n !) = n log n − n + O ( log ( n + 2 )) ( m + 1 ) ∣ A ∣ (m+1)^{|\mathcal{A}|} ( m + 1 ) ∣ A ∣
One convenient way to meet the entropy hypothesis is to use positive weights a i a_i a i b j b_j b j c k c_k c k
p ( i , j , k ) = Z − 1 a i b j c k ( ( i , j , k ) ∈ Ω r ) . p(i,j,k)=Z^{-1}a_i b_j c_k\qquad((i,j,k)\in\Omega_r). p ( i , j , k ) = Z − 1 a i b j c k (( i , j , k ) ∈ Ω r ) . For any competing law q q q − ∑ q log p = − ∑ p log p = H ( p ) -\sum q\log p=-\sum p\log p=H(p) − ∑ q log p = − ∑ p log p = H ( p ) log p \log p log p
∑ q ( u ) > 0 q ( u ) log p ( u ) q ( u ) ≤ ∑ q ( u ) > 0 ( p ( u ) − q ( u ) ) ≤ 0. \sum_{q(u)>0}q(u)\log\frac{p(u)}{q(u)}\le\sum_{q(u)>0}(p(u)-q(u))\le0. q ( u ) > 0 ∑ q ( u ) log q ( u ) p ( u ) ≤ q ( u ) > 0 ∑ ( p ( u ) − q ( u )) ≤ 0. by log t ≤ t − 1 \log t\le t-1 log t ≤ t − 1 H ( q ) ≤ H ( p ) H(q)\le H(p) H ( q ) ≤ H ( p )
First keep, on each side, just the coarse sequences having marginal type p r , W p_{r,W} p r , W ambient . The total number of target triples is
∣ T N ∣ = exp ( N A a m b + O ( log N ) ) . (17) |\mathcal{T}_N|=\exp(NA_{\mathrm{amb}}+O(\log N)). \tag*{(17)} ∣ T N ∣ = exp ( N A amb + O ( log N )) . (17) For a fixed X X X q r q_r q r r r r
∏ i ( m p r , X ( i ) ) ! ∏ u ( m q r ( u ) ) ! = exp ( m ( H ( q r ) − H ( p r , X ) ) + O ( log N ) ) . \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). ∏ u ( m q r ( u ))! ∏ i ( m p r , X ( i ))! = exp ( m ( H ( q r ) − H ( p r , X )) + O ( log N ) ) . Summing over the polynomially many types and using maximality yields the degree bound
# { ambient triples at a fixed X block } ≤ exp ( N ( A a m b − C X ) + O ( log N ) ) . (18) \#\{\text{ambient triples at a fixed }X\text{ block}\}\le\exp\bigl(N(A_{\mathrm{amb}}-C_X)+O(\log N)\bigr). \tag*{(18)} # { ambient triples at a fixed X block } ≤ exp ( N ( A amb − C X ) + O ( log N ) ) . (18) Here and below the coarse counts ignore all fine masks, thereby bounding every interaction that could actually occur.
Fix a small slack δ > 0 \delta>0 δ > 0 C X ≤ A a m b C_X\le A_{\mathrm{amb}} C X ≤ A amb E ≤ C X E\le C_X E ≤ C X M = 37 k M=37^k M = 3 7 k
log M = N ( A a m b − E + δ ) + O ( 1 ) . (19) \log M=N(A_{\mathrm{amb}}-E+\delta)+O(1). \tag*{(19)} log M = N ( A amb − E + δ ) + O ( 1 ) . (19) There is a set U ⊂ Z / M Z U\subset\mathbb{Z}/M\mathbb{Z} U ⊂ Z / M Z
log ∣ U ∣ = log M − O ( log M ) (20) \log|U|=\log M-O(\sqrt{\log M}) \tag*{(20)} log ∣ U ∣ = log M − O ( log M ) (20) and no nonconstant three-term arithmetic progression. Here is a version of Behrend’s construction [3 ] that also rules out modular wraparound. Put h = ⌊ log M ⌋ h=\lfloor\sqrt{\log M}\rfloor h = ⌊ log M ⌋ b = ⌊ M 1 / h / 2 ⌋ b=\lfloor M^{1/h}/2\rfloor b = ⌊ M 1/ h /2 ⌋ d ∈ { 0 , … , b − 1 } h d\in\{0,\ldots,b-1\}^{h} d ∈ { 0 , … , b − 1 } h n ( d ) = ∑ j = 0 h − 1 d j ( 2 b ) j n(d)=\sum_{j=0}^{h-1}d_j(2b)^j n ( d ) = ∑ j = 0 h − 1 d j ( 2 b ) j ∑ j d j 2 \sum_jd_j^2 ∑ j d j 2 ( 2 b ) h / 2 ≤ M / 2 (2b)^h/2\le M/2 ( 2 b ) h /2 ≤ M /2 n ( d ) + n ( e ) = 2 n ( f ) n(d)+n(e)=2n(f) n ( d ) + n ( e ) = 2 n ( f ) 2 b − 2 2b-2 2 b − 2 d + e = 2 f d+e=2f d + e = 2 f ∥ d − e ∥ 2 = 2 ∥ d ∥ 2 + 2 ∥ e ∥ 2 − ∥ d + e ∥ 2 = 0 \|d-e\|^2=2\|d\|^2+2\|e\|^2-\|d+e\|^2=0 ∥ d − e ∥ 2 = 2∥ d ∥ 2 + 2∥ e ∥ 2 − ∥ d + e ∥ 2 = 0 1 + h ( b − 1 ) 2 1+h(b-1)^2 1 + h ( b − 1 ) 2 ∣ U ∣ ≥ b h / ( 1 + h b 2 ) |U|\ge b^h/(1+hb^2) ∣ U ∣ ≥ b h / ( 1 + h b 2 ) b ≥ M 1 / h / 4 b\ge M^{1/h}/4 b ≥ M 1/ h /4 b ≤ M 1 / h b\le M^{1/h} b ≤ M 1/ h
Concatenate all d = ∑ r m r d=\sum_r m_r d = ∑ r m r I , J , K I,J,K I , J , K S S S s r s_r s r r r r I + J + K = S I+J+K=S I + J + K = S S S S a , b ′ a,b' a , b ′ v v v Z / M Z \mathbb{Z}/M\mathbb{Z} Z / M Z
x ( I ) = a + ⟨ v , I ⟩ , y ( J ) = b ′ + ⟨ v , J ⟩ , z ( K ) = a + b ′ + ⟨ v , S − K ⟩ 2 . (21) x(I)=a+\langle v,I\rangle,\qquad y(J)=b'+\langle v,J\rangle,\qquad z(K)=\frac{a+b'+\langle v,S-K\rangle}{2}. \tag*{(21)} x ( I ) = a + ⟨ v , I ⟩ , y ( J ) = b ′ + ⟨ v , J ⟩ , z ( K ) = 2 a + b ′ + ⟨ v , S − K ⟩ . (21) Division by 2 2 2 M M M U U U x + y = 2 z x+y=2z x + y = 2 z x = y = z x=y=z x = y = z
For a fixed ambient triple e e e S e S_e S e v v v t ∈ U t \in U t ∈ U x = y = z = t x=y=z=t x = y = z = t
Pr ( S e ) = h M ≔ ∣ U ∣ M 2 . (22) \Pr(S_e)=h_M\coloneqq\frac{\lvert U\rvert}{M^2}. \tag*{(22)} Pr ( S e ) = h M : = M 2 ∣ U ∣ . (22) Conditional on S e S_e S e ( v , t ) (v,t) ( v , t ) ( Z / M Z ) d × U (\mathbb{Z}/M\mathbb{Z})^d\times U ( Z / M Z ) d × U ( Δ I , Δ J , Δ K ) (\Delta I,\Delta J,\Delta K) ( Δ I , Δ J , Δ K )
t + ⟨ v , Δ I ⟩ , t + ⟨ v , Δ J ⟩ , t − 1 2 ⟨ v , Δ K ⟩ . t+\langle v,\Delta I\rangle,\quad t+\langle v,\Delta J\rangle,\quad t-\frac{1}{2}\langle v,\Delta K\rangle. t + ⟨ v , Δ I ⟩ , t + ⟨ v , Δ J ⟩ , t − 2 1 ⟨ v , Δ K ⟩ . If it shares X with e e e ⟨ v , Δ J ⟩ = 0 \langle v,\Delta J\rangle=0 ⟨ v , Δ J ⟩ = 0 ⟨ v , Δ I ⟩ = 0 \langle v,\Delta I\rangle=0 ⟨ v , Δ I ⟩ = 0 Δ J = − Δ I \Delta J=-\Delta I Δ J = − Δ I S S S 37 k 37^k 3 7 k v v v
Pr ( S e ′ ∣ S e ) = 1 M (23) \Pr(S_{e'}\mid S_e)=\frac{1}{M} \tag*{(23)} Pr ( S e ′ ∣ S e ) = M 1 (23) for distinct triples sharing a block.
No further hash-dependent event is included in this conditioning.
The finite compatibility count
In a sharing population, prefilter side W ∈ { Y , Z } W\in\{Y,Z\} W ∈ { Y , Z } η \eta η D W D_W D W compatible with a target triple if its statistic type is within width χ \chi χ u ∈ I W u\in I_W u ∈ I W ν u , W \nu_{u,W} ν u , W g − u ∈ I W g-u\in I_W g − u ∈ I W ν g − u , W \nu_{g-u,W} ν g − u , W
Lemma 3.2 (Compatibility incidence count). For fixed population data, there is a function ξ ( η , χ ) → 0 \xi(\eta,\chi)\to0 ξ ( η , χ ) → 0 ( η , χ ) → ( 0 , 0 ) (\eta,\chi)\to(0,0) ( η , χ ) → ( 0 , 0 )
exp ( N ( A a m b − C W + ξ ( η , χ ) ) + O ( log N ) ) , W ∈ { Y , Z } , (24) \exp\bigl(N(A_{\mathrm{amb}}-C_W+\xi(\eta,\chi))+O(\log N)\bigr),\qquad W\in\{Y,Z\}, \tag*{(24)} exp ( N ( A amb − C W + ξ ( η , χ )) + O ( log N ) ) , W ∈ { Y , Z } , (24) target triples containing its coarse block, before hashing. The estimate is uniform in the variable and the target arrangement.
Proof. Consider first one sharing population of size m m m W W W k = ( k 1 , … , k m ) k=(k_1,\ldots,k_m) k = ( k 1 , … , k m ) k k k p W p_W p W C \mathcal{C} C ( u 1 , … , u m ) (u_1,\ldots,u_m) ( u 1 , … , u m ) p p p u j , W = k j u_{j,W}=k_j u j , W = k j z = ( ( a j , b j ) ) j = 1 m z=((a_j,b_j))_{j=1}^m z = (( a j , b j ) ) j = 1 m D ′ D' D ′ B \mathcal{B} B
Γ k = ∏ i Sym { j : k j = i } . \Gamma_k=\prod_i\operatorname{Sym}\{j:k_j=i\}. Γ k = i ∏ Sym { j : k j = i } . This group acts transitively on B \mathcal{B} B C \mathcal{C} C a = # { z ∈ B : z compatible with c } a=\#\{z\in\mathcal{B}:z\text{ compatible with }c\} a = # { z ∈ B : z compatible with c } b = # { c ∈ C : z compatible with c } b = \#\{c \in C : z\text{ compatible with }c\} b = # { c ∈ C : z compatible with c } c c c z z z
∣ C ∣ a = ∣ B ∣ b . (25) |C|a = |B|b. \tag*{(25)} ∣ C ∣ a = ∣ B ∣ b . (25) Since the statistic determines the half weight,
∣ C ∣ = ∏ i ( m p W ( i ) ) ! ∏ u ( m p ( u ) ) ! , log ∣ C ∣ = m ( H ( p ) − H ( p W ) ) + O ( log ( m + 2 ) ) , |C| = \frac{\prod_i(mp_W(i))!}{\prod_u(mp(u))!}, \qquad\log|C| = m(H(p) - H(p_W)) + O(\log(m + 2)), ∣ C ∣ = ∏ u ( m p ( u ))! ∏ i ( m p W ( i ))! , log ∣ C ∣ = m ( H ( p ) − H ( p W )) + O ( log ( m + 2 )) , ∣ B ∣ = ∏ i ( m p W ( i ) ) ! ∏ a , b ( m D ′ ( a , b ) ) ! , log ∣ B ∣ = m ( H ( D ′ ) − H ( p W ) ) + O ( log ( m + 2 ) ) . |B| = \frac{\prod_i(mp_W(i))!}{\prod_{a,b}(mD'(a,b))!}, \qquad\log|B| = m(H(D') - H(p_W)) + O(\log(m + 2)). ∣ B ∣ = ∏ a , b ( m D ′ ( a , b ))! ∏ i ( m p W ( i ))! , log ∣ B ∣ = m ( H ( D ′ ) − H ( p W )) + O ( log ( m + 2 )) . To bound a a a c ∈ C c \in C c ∈ C χ \chi χ D ′ D' D ′ ρ W ( a j ) = k j \rho_W(a_j) = k_j ρ W ( a j ) = k j i i i
∑ u ∈ G p ( u ) ν u , W p ( G ) \frac{\sum_{u\in G}p(u)\nu_{u,W}}{p(G)} p ( G ) ∑ u ∈ G p ( u ) ν u , W up to an error tending uniformly to zero with η \eta η χ \chi χ ( ∣ A r , W ∣ η + χ ) / p ( G ) (|A_{r,W}|\eta+ \chi)/p(G) ( ∣ A r , W ∣ η + χ ) / p ( G ) D ′ D' D ′ ∣ A r , W ∣ η |A_{r,W}|\eta ∣ A r , W ∣ η χ \chi χ p ( G ) p(G) p ( G ) exp ( m ( J W + o η , χ ( 1 ) ) + O ( log ( m + 2 ) ) ) \exp(m(J_W + o_{\eta,\chi}(1)) + O(\log(m + 2))) exp ( m ( J W + o η , χ ( 1 )) + O ( log ( m + 2 )))
For the right half, use the column sums of D ′ D' D ′ g W − k j g_W-k_j g W − k j p ( g − u ) = p ( u ) p(g-u)=p(u) p ( g − u ) = p ( u ) J W J_W J W ν g − u , W \nu_{g-u,W} ν g − u , W D ′ D' D ′
a ≤ exp ( m ( 2 J W + o η , χ ( 1 ) ) + O ( log ( m + 2 ) ) ) . a \le\exp(m(2J_W + o_{\eta,\chi}(1)) + O(\log(m + 2))). a ≤ exp ( m ( 2 J W + o η , χ ( 1 )) + O ( log ( m + 2 ))) . There is no factor for choosing group locations: those locations were fixed with c c c (25) and uniform continuity of entropy on a finite simplex,
b ≤ exp ( m ( H ( p ) − H ( D W ) + 2 J W + o η , χ ( 1 ) ) + O ( log ( m + 2 ) ) ) . b \le\exp(m(H(p) - H(D_W) + 2J_W + o_{\eta,\chi}(1)) + O(\log(m + 2))). b ≤ exp ( m ( H ( p ) − H ( D W ) + 2 J W + o η , χ ( 1 )) + O ( log ( m + 2 ))) . For an ordinary population all candidates are compatible, and their number is exp ( m ( H ( p ) − H ( p W ) ) + O ( log ( m + 2 ) ) ) \exp(m(H(p) - H(p_W)) + O(\log(m + 2))) exp ( m ( H ( p ) − H ( p W )) + O ( log ( m + 2 ))) (24) .
Sequential assignment by variable deletion
Choose η , χ > 0 \eta,\chi> 0 η , χ > 0 δ / 4 \delta/4 δ /4 θ > 0 \theta> 0 θ > 0 χ \chi χ N N N
First delete an X X X eligible . Freeze this list for all subsequent tests. By (18) , (19) , and (23) , a target triple e e e S e S_e S e exp ( − δ N + O ( log N ) ) \exp(-\delta N + O(\log N)) exp ( − δ N + O ( log N )) X X X
On Y Y Y Z Z Z I Z \mathcal{I}_Z I Z
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 e e X X X e e e X X X e e e u Z = 0 u_Z=0 u Z = 0 Y Y Y X X X Y Y Y e e e Y Y Y e e e
For Z Z Z u Y = 0 u_Y=0 u Y = 0 X X X u X = 0 u_X=0 u X = 0 u Y > 0 u_Y>0 u Y > 0 Y Y Y u X = u Y = 0 u_X=u_Y=0 u X = u Y = 0 e e e I Z \mathcal{I}_Z I Z Z Z Z e e e
Different assignments share no retained fine variable on any side. Within assignment e e e Q e Q_e Q e Q e Q_e Q e Q e h o l e Q_e^{\mathrm{hole}} Q e hole Q e Q_e Q e
Here is the probability estimate needed to repair these holes. For a fixed e e e v v v Q e Q_e Q e R e , v R_{e,v} R e , v X X X v v v Y Y Y Z Z Z v v v R e , v R_{e,v} R e , v all target triples before eligibility and other deletions. Lemma 3.2 and (23) then give, for some constant c > 0 c>0 c > 0
Pr ( R e , v ∣ S e ) ≤ exp ( − c N ) , (26) \Pr(R_{e,v}\mid S_e)\leq\exp(-cN), \tag*{(26)} Pr ( R e , v ∣ S e ) ≤ exp ( − c N ) , (26) uniformly in e e e N N N W W W N ( E − C W − δ + ξ ) + O ( log N ) N(E-C_W-\delta+\xi)+O(\log N) N ( E − C W − δ + ξ ) + O ( log N ) C W ≥ E C_W\geq E C W ≥ E S e S_e S e
For reference in the recovery argument, let G e G_e G e ( r , u , half ) (r,u,\text{half}) ( r , u , half ) Q e Q_e Q e G e G_e G e (26) , selects exponentially many good assignments using (17) and (22) , and applies Lemma 4.2 to reconstruct their ideal outputs.
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.
Fix all population masses, rational laws, and positive tolerances before letting the divisible integer N N N e e e Q e Q_e Q e c c c n c = c c N n_c = c_cN n c = c c N c c > 0 c_c > 0 c c > 0
Let G e G_e G e Q e Q_e Q e
Lemma 4.1 (Uniform loss from inherited masks). The total number of G e G_e G e N N N e e e C 0 C_0 C 0 C 0 / N C_0/N C 0 / N e e e N N N
Proof. Let A c , W \mathcal{A}_{c,W} A c , W W W W c c c W W W
∏ c ( n c + 1 ) ∣ A c , W ∣ = O ( N d W ) \prod_c (n_c+1)^{|\mathcal{A}_{c,W}|}=O(N^{d_W}) c ∏ ( n c + 1 ) ∣ A c , W ∣ = O ( N d W ) for a fixed integer d W d_W d W
Consider one mask with tolerance η > 0 \eta> 0 η > 0 m = c N m = cN m = c N a a a w a = n a / m w_a = n_a/m w a = n a / m q a , L , q a , R q_{a,L}, q_{a,R} q a , L , q a , R ν a , L , ν a , R \nu_{a,L}, \nu_{a,R} ν a , L , ν a , R τ \tau τ
∣ q a , L ( s ) q a , R ( t ) − ν a , L ( s ) ν a , R ( t ) ∣ ≤ 2 τ \left|q_{a,L}(s)q_{a,R}(t)-\nu_{a,L}(s)\nu_{a,R}(t)\right| \le2\tau ∣ q a , L ( s ) q a , R ( t ) − ν a , L ( s ) ν a , R ( t ) ∣ ≤ 2 τ shows that the mean mixture differs from ∑ a w a ν a , L ⊗ ν a , R \sum_a w_a\nu_{a,L}\otimes\nu_{a,R} ∑ a w a ν a , L ⊗ ν a , R 2 τ 2\tau 2 τ α ≤ η / 4 \alpha\le\eta/4 α ≤ η /4 τ ≤ η / 8 \tau\le\eta/8 τ ≤ η /8 η / 2 \eta/2 η /2 α = 0 \alpha=0 α = 0
Uniformly permute an element of the orbit. Within one parent-triple class of size n n n s s s t t t a a a b b b K s , t K_{s,t} K s , t n ≥ 2 n \ge2 n ≥ 2
E K s , t = n a b , Var ( K s , t ) = n 2 a ( 1 − a ) b ( 1 − b ) n − 1 ≤ n 8 . (27) \mathbb{E}K_{s,t}=nab,\qquad\operatorname{Var}(K_{s,t})=\frac{n^2a(1-a)b(1-b)}{n-1}\le\frac{n}{8}. \tag*{(27)} E K s , t = nab , Var ( K s , t ) = n − 1 n 2 a ( 1 − a ) b ( 1 − b ) ≤ 8 n . (27) Indeed, fix the positions of the n a na na t t t b b b b ( 1 − b ) b(1-b) b ( 1 − b ) − b ( 1 − b ) / ( n − 1 ) -b(1-b)/(n-1) − b ( 1 − b ) / ( n − 1 ) (27) . This calculation is uniform over a , b ∈ [ 0 , 1 ] a,b\in[0,1] a , b ∈ [ 0 , 1 ]
Different parent-triple classes use independent permutations. Consequently the variance of a pair count summed over a population is at most m / 8 m/8 m /8
Pr ( ∣ ∑ a K s , t ( a ) m − E ∑ a K s , t ( a ) m ∣ > η / 2 ) ≤ 1 2 c η 2 N . \Pr\left(\left|\frac{\sum_a K_{s,t}^{(a)}}{m}-\mathbb{E}\frac{\sum_a K_{s,t}^{(a)}}{m}\right|>\eta/2\right)\le\frac{1}{2c\eta^2N}. Pr ( m ∑ a K s , t ( a ) − E m ∑ a K s , t ( a ) > η /2 ) ≤ 2 c η 2 N 1 . For a mask on a fixed function of the ordered pair, a coordinate of the pushed-forward law is a sum of at most B B B B B B τ ≤ η / ( 8 B ) \tau\le\eta/(8B) τ ≤ η / ( 8 B ) η / ( 2 B ) \eta/(2B) η / ( 2 B ) O ( 1 / N ) O(1/N) O ( 1/ N ) C 0 / N C_0/N C 0 / N C 0 C_0 C 0
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.
Lemma 4.2 (Exact repair by presence masks). Let Q N Q_N Q N exp ( b N ) \exp(bN) exp ( b N ) b > 0 b>0 b > 0 G N G_N G N H N H_N H N Q N Q_N Q N C / N C/N C / N G N G_N G N C > 0 C>0 C > 0 N N N
R N = exp ( O ( N / log N ) ) R_N=\exp(O(N/\log N)) R N = exp ( O ( N / log N )) copies of H N H_N H N Q N Q_N Q N H N , Q N , G N H_N,Q_N,G_N H N , Q N , G N Proof. We first cover all ideal monomials by shifted copies. Partitioning variables by their presence masks then converts this cover into an exact linear restriction. Put γ = C / N \gamma= C/N γ = C / N N > 3 C N > 3C N > 3 C
L = ⌈ ( b + 1 ) N log ( N / ( 3 C ) ) ⌉ = O ( N / log N ) . L = \left\lceil\frac{(b+1)N}{\log(N/(3C))} \right\rceil= O(N/\log N). L = ⌈ log ( N / ( 3 C )) ( b + 1 ) N ⌉ = O ( N / log N ) . Take L L L g 1 , … , g L g_1,\ldots,g_L g 1 , … , g L G N G_N G N g i H N g_iH_N g i H N γ \gamma γ x y z xyz x y z Q N Q_N Q N 3 γ 3\gamma 3 γ L L L
exp ( b N ) ( 3 γ ) L ≤ e − N < 1. \exp(bN)(3\gamma)^L \le e^{-N} < 1. exp ( b N ) ( 3 γ ) L ≤ e − N < 1. Fix a family covering every monomial. The group need only preserve Q N Q_N Q N H N H_N H N
For an ideal variable x x x
A ( x ) = { i ∈ { 1 , … , L } : x is retained in g i H N } , A(x) = \{i \in\{1,\ldots,L\}: x\text{ is retained in }g_iH_N\}, A ( x ) = { i ∈ { 1 , … , L } : x is retained in g i H N } , and define B ( y ) B(y) B ( y ) C ( z ) C(z) C ( z ) X A , Y B , Z C X_A,Y_B,Z_C X A , Y B , Z C 2 L 2^L 2 L X A × Y B × Z C X_A \times Y_B \times Z_C X A × Y B × Z C Q N Q_N Q N A ∩ B ∩ C ≠ ∅ A \cap B \cap C \ne\varnothing A ∩ B ∩ C = ∅ i ( A , B , C ) i(A,B,C) i ( A , B , C ) g i ( A , B , C ) H N g_{i(A,B,C)}H_N g i ( A , B , C ) H N Q N Q_N Q N
Use a separate copy of H N H_N H N g i ( A , B , C ) g_{i(A,B,C)} g i ( A , B , C ) ( A , B , C , x ) (A,B,C,x) ( A , B , C , x ) x x x x y z xyz x y z 2 3 L 2^{3L} 2 3 L R N R_N R N □ \square □
Completion of the proof of Theorem 3.1. Use the hash slack δ > 0 \delta> 0 δ > 0 e e e S e S_e S e Pr ( S e ) = h M = ∣ U ∣ / M 2 \Pr(S_e)=h_M=|U|/M^2 Pr ( S e ) = h M = ∣ U ∣/ M 2 P e ( v ) P_e(v) P e ( v ) v v v Q e Q_e Q e Q e Q_e Q e G e G_e G e O \mathcal{O} O
d e , O = ∣ { v ∈ O : ¬ P e ( v ) } ∣ ∣ O ∣ ≤ C 0 / N . d_{e,\mathcal{O}}=\frac{|\{v\in\mathcal{O}:\neg P_e(v)\}|}{|\mathcal{O}|}\le C_0/N. d e , O = ∣ O ∣ ∣ { v ∈ O : ¬ P e ( v )} ∣ ≤ C 0 / N . For a passing variable v v v R e , v R_{e,v} R e , v e e e X X X v v v
Pr ( R e , v ∣ S e ) ≤ e − c N (28) \Pr(R_{e,v}\mid S_e)\le e^{-cN} \tag*{(28)} Pr ( R e , v ∣ S e ) ≤ e − c N (28) for one fixed c > 0 c>0 c > 0 e e e v v v N N N P e ( v ) P_e(v) P e ( v ) S e S_e S e
r e , O = 1 ∣ O ∣ ∑ v ∈ O 1 R e , v P e ( v ) r_{e,O}=\frac{1}{|O|}\sum_{v\in O}\frac{\mathbf{1}_{R_{e,v}}}{P_e(v)} r e , O = ∣ O ∣ 1 v ∈ O ∑ P e ( v ) 1 R e , v By linearity of expectation, E ( r e , O ∣ S e ) ≤ e − c N \mathbb{E}(r_{e,O}\mid S_e)\le e^{-cN} E ( r e , O ∣ S e ) ≤ e − c N P e P_e P e d e , O d_{e,O} d e , O P ( N ) P(N) P ( N )
Pr ( ∃ O : r e , O > 1 / N ∣ S e ) ≤ N P ( N ) e − c N = e − c N + O ( log N ) . \Pr\left(\exists O:r_{e,O}>1/N\mid S_e\right)\le NP(N)e^{-cN}=e^{-cN+O(\log N)}. Pr ( ∃ O : r e , O > 1/ N ∣ S e ) ≤ N P ( N ) e − c N = e − c N + O ( l o g N ) . Declare e e e 1 / N 1/N 1/ N e e e
γ N = ( C 0 + 1 ) / N (29) \gamma_N=(C_0+1)/N \tag*{(29)} γ N = ( C 0 + 1 ) / N (29) in each orbit. The eligible list remains the fixed list used in Section 3. Deterministic masks are accounted for as additional deletion flags; they do not trigger a recomputation of that list or of the compatibility candidates.
There are exp ( N A a m b + O ( log N ) ) \exp(NA_{\mathrm{amb}}+O(\log N)) exp ( N A amb + O ( log N )) log M = N ( A a m b − E + δ ) + O ( 1 ) \log M=N(A_{\mathrm{amb}}-E+\delta)+O(1) log M = N ( A amb − E + δ ) + O ( 1 ) log ∣ U ∣ = log M − o ( N ) \log|U|=\log M-o(N) log ∣ U ∣ = log M − o ( N ) G G G
E ∣ G ∣ ≥ exp ( N A a m b + O ( log N ) ) h M ( 1 − e − c N + O ( log N ) ) = exp ( N ( E − δ ) − o ( N ) ) . \mathbb{E}|G|\ge\exp(NA_{\mathrm{amb}}+O(\log N))h_M\left(1-e^{-cN+O(\log N)}\right)
=\exp(N(E-\delta)-o(N)). E ∣ G ∣ ≥ exp ( N A amb + O ( log N )) h M ( 1 − e − c N + O ( l o g N ) ) = exp ( N ( E − δ ) − o ( N )) . Thus one hash choice has at least this many good triples, up to integer rounding. This uses no independence between different targets or between their losses. The assignment proof has already made their holed outputs H e H_e H e
All strand lengths and alphabets are bounded, and there are O ( N ) O(N) O ( N ) Q e Q_e Q e exp ( b N ) \exp(bN) exp ( b N ) b b b a N aN a N C W 5 \mathrm{CW}_5 CW 5 18 a N 18^{aN} 1 8 a N C W 5 \mathrm{CW}_5 CW 5 3 ⋅ 5 + 3 = 18 3\cdot5+3=18 3 ⋅ 5 + 3 = 18 b > a log 18 b>a\log18 b > a log 18 C = C 0 + 1 C=C_0+1 C = C 0 + 1 R N = exp ( O ( N / log N ) ) R_N=\exp(O(N/\log N)) R N = exp ( O ( N / log N ))
⨁ r = 1 R N ⨁ e ∈ G H e ≅ ⨁ e ∈ G ⨁ r = 1 R N H e . \bigoplus_{r=1}^{R_N}\ \bigoplus_{e\in G}H_e\cong\bigoplus_{e\in G}\ \bigoplus_{r=1}^{R_N}H_e. r = 1 ⨁ R N e ∈ G ⨁ H e ≅ e ∈ G ⨁ r = 1 ⨁ R N H e . The same replication slots supply each summand with R N R_N R N ⨁ e ∈ G Q e \bigoplus_{e\in G}Q_e ⨁ e ∈ G Q e R N R_N R N
Finally, exact target types give the same number of factors in every population, history, split-triple, and half class for every e e e Q e Q_e Q e Q N Q_N Q N 0 < δ < min ( E , ε ) 0<\delta<\min(E,\varepsilon) 0 < δ < min ( E , ε ) N N N o ( N ) o(N) o ( N ) exp ( N ( E − ε ) ) \exp(N(E-\varepsilon)) exp ( N ( E − ε )) exp ( o ( N ) ) \exp(o(N)) exp ( o ( N ))
Composition and subdivision
To iterate Theorem 3.1, we record the two algebraic operations explicitly. Write D r ( T ) = ⨁ i = 1 r T D_r(T) = \bigoplus_{i=1}^{r} T D r ( T ) = ⨁ i = 1 r T A ⪯ B A \preceq B A ⪯ B A A A B B B
Lemma 4.3 (Replication and composition). Suppose D s 1 ( T ) ⪯ D r 1 ( S ) D_{s_1}(T) \preceq D_{r_1}(S) D s 1 ( T ) ⪯ D r 1 ( S ) and D s 2 ( V ) ⪯ D r 2 ( T ) D_{s_2}(V) \preceq D_{r_2}(T) D s 2 ( V ) ⪯ D r 2 ( T ) Then
D s 1 s 2 ( V ) ⪯ D r 1 r 2 ( S ) . D_{s_1s_2}(V) \preceq D_{r_1r_2}(S). D s 1 s 2 ( V ) ⪯ D r 1 r 2 ( S ) . For any finite collection of tensors,
⨂ i = 1 j D r i ( F i ) ≅ D ∏ i = 1 j r i ( ⨂ i = 1 j F i ) . \bigotimes_{i=1}^{j} D_{r_i}(F_i) \cong D_{\prod_{i=1}^{j} r_i}\left(\bigotimes_{i=1}^{j} F_i\right). i = 1 ⨂ j D r i ( F i ) ≅ D ∏ i = 1 j r i ( i = 1 ⨂ j F i ) . The same assertions permit different maps in different direct-sum branches, provided a common upper bound on their replication counts is used. Consequently every fixed finite sequence of the joint extractions above, including finite tensor products of them, costs only exp ( o ( N ) ) \exp(o(N)) exp ( o ( N ))
Proof. Take r 2 r_2 r 2 D s 1 ( D r 2 ( T ) ) D_{s_1}(D_{r_2}(T)) D s 1 ( D r 2 ( T )) s 1 s_1 s 1 r 1 r 2 r_1r_2 r 1 r 2 s 1 s_1 s 1 exp ( o ( N ) ) \exp(o(N)) exp ( o ( N )) exp ( o ( N ) ) \exp(o(N)) exp ( o ( N )) c N cN c N c > 0 c > 0 c > 0 o ( c N ) o(cN) o ( c N ) o ( N ) o(N) o ( N )
There is also an exact way to subdivide a received population before its next use. Let B B B ν W \nu_W ν W W W W U ( m , ν , η ) U(m,\nu,\eta) U ( m , ν , η ) B ⊗ m B^{\otimes m} B ⊗ m η \eta η m 1 , … , m j m_1,\ldots,m_j m 1 , … , m j η i ≤ η \eta_i \leq\eta η i ≤ η
⨂ i = 1 j U ( m i , ν , η i ) ⪯ U ( ∑ i = 1 j m i , ν , η ) . (30) \bigotimes_{i=1}^{j} U(m_i,\nu,\eta_i) \preceq U\left(\sum_{i=1}^{j} m_i,\nu,\eta\right). \tag*{(30)} i = 1 ⨂ j U ( m i , ν , η i ) ⪯ U ( i = 1 ∑ j m i , ν , η ) . (30) To see this, the empirical law of a concatenated variable is the weighted average of its partwise empirical laws, with error at most ∑ i ( m i / ∑ j m j ) η i ≤ η \sum_i (m_i/\sum_j m_j)\eta_i \leq\eta ∑ i ( m i / ∑ j m j ) η i ≤ η
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 N N N N N
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.
A lot consists of N N N 8 8 8 8 N 8N 8 N C W 5 \mathrm{CW}_5 CW 5 8 8 8 4 4 4 4 4 4 2 2 2 2 2 2 1 1 1
Shapes, prescriptions, and the three stages
All coordinate labels in this section belong to { 0 , 1 , 2 } \{0,1,2\} { 0 , 1 , 2 } positive if all its coordinates are positive. Choose a symmetric product-weight law on the ordered shapes of size 16 16 16 ( a , b , c ) (a,b,c) ( a , b , c ) α a α b α c \alpha_a\alpha_b\alpha_c α a α b α c α j > 0 \alpha_j>0 α j > 0 a + b + c = 16 a+b+c=16 a + b + c = 16 A g A_g A g g g g A g A_g A g ρ g \rho_g ρ g 1 / 3 1/3 1/3 g g g
μ = ∑ g A g ρ g , H 0 = H ( μ ) . (31) \mu=\sum_g A_g\rho_g,\qquad H_0=H(\mu). \tag*{(31)} μ = g ∑ A g ρ g , H 0 = H ( μ ) . (31) The product-weight hypothesis verifies maximum entropy at the given marginals. The initial ordinary extraction therefore yields exp ( N ( H 0 − o ( 1 ) ) ) \exp(N(H_0-o(1))) exp ( N ( H 0 − o ( 1 )))
Give each sorted g g g 0 , 1 , 2 0,1,2 0 , 1 , 2 N A g / 6 NA_g/6 N A g /6 g g g s g s_g s g g g g 6 / s g 6/s_g 6/ s g N A g s g / 6 NA_gs_g/6 N A g s g /6 s g s_g s g ( 4 , 6 , 6 ) (4,6,6) ( 4 , 6 , 6 ) 6 6 6
For each positive sorted g g g 16 16 16 P g ( t ) P_g(t) P g ( t )
∣ t ∣ = 8 , 0 ≤ t ≤ g , \lvert t\rvert=8,\qquad0\le t\le g, ∣ t ∣ = 8 , 0 ≤ t ≤ g , with P g ( t ) = P g ( g − t ) P_g(t)=P_g(g-t) P g ( t ) = P g ( g − t ) ordered t t t 8 8 8 p t ( u ) p_t(u) p t ( u ) ∣ u ∣ = 4 \lvert u\rvert=4 ∣ u ∣ = 4 0 ≤ u ≤ t 0\le u\le t 0 ≤ u ≤ t p t ( u ) = p t ( t − u ) p_t(u)=p_t(t-u) p t ( u ) = p t ( t − u ) d t , u ∈ [ 0 , 1 ] d_{t,u}\in[0,1] d t , u ∈ [ 0 , 1 ] z t z_t z t
The length-2 statistic on one side is its unordered pair of weights. We use the following fixed coding; D i D_i D i i i i q = 5 q=5 q = 5
κ = ( 5 , 4 , 2 , 3 , 1 , 0 ) . (32) \kappa= (5,4,2,3,1,0). \tag*{(32)} κ = ( 5 , 4 , 2 , 3 , 1 , 0 ) . (32) Here r i r_i r i κ \kappa κ t t t u u u v t , u , W v_{t,u,W} v t , u , W W W W r i = u W r_i=u_W r i = u W u W ≠ 2 u_W\ne2 u W = 2 u W = 2 u_W=2 u W = 2 1 − d t , u 1-d_{t,u} 1 − d t , u d t , u d_{t,u} d t , u u u u
On a length-4 strand the statistic is the ordered pair of the statistics of its length-2 halves. For positive t t t
V t , W = ∑ u p t ( u ) v t , u , W ⊗ v t , t − u , W . (33) V_{t,W}=\sum_u p_t(u)\,v_{t,u,W}\otimes v_{t,t-u,W}. \tag*{(33)} V t , W = u ∑ p t ( u ) v t , u , W ⊗ v t , t − u , W . (33) For a zero-coordinate t t t W ∗ W_* W ∗ max t \max t max t z t z_t z t ( i , j ) (i,j) ( i , j ) r i + r j = max t r_i+r_j=\max t r i + r j = max t V t , W ∗ = z t V_{t,W_*}=z_t V t , W ∗ = z t ( 0 , 0 ) (0,0) ( 0 , 0 ) κ \kappa κ z t z_t z t u u u
Stage A is a sharing split of T 8 , g T_{8,g} T 8 , g P g P_g P g V t , W V_{t,W} V t , W ( 0 , 1 , 2 ) (0,1,2) ( 0 , 1 , 2 ) Stage B is a sharing split of T 4 , t T_{4,t} T 4 , t p t p_t p t v t , u , W v_{t,u,W} v t , u , W π ( t ) \pi(t) π ( t ) t t t
( 1 , 1 , 6 ) , ( 1 , 2 , 5 ) , ( 1 , 3 , 4 ) , ( 2 , 2 , 4 ) , ( 3 , 2 , 3 ) . (34) (1,1,6),\qquad(1,2,5),\qquad(1,3,4),\qquad(2,2,4),\qquad(3,2,3). \tag*{(34)} ( 1 , 1 , 6 ) , ( 1 , 2 , 5 ) , ( 1 , 3 , 4 ) , ( 2 , 2 , 4 ) , ( 3 , 2 , 3 ) . (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 ) t=(2,3,3) t = ( 2 , 3 , 3 ) ( 1 , 0 , 2 ) (1,0,2) ( 1 , 0 , 2 )
Stage C is an ordinary split of a positive T 2 , u T_{2,u} T 2 , u u u u ( a , b , c ) (a,b,c) ( a , b , c ) c c c
The right shape is u u u 1 / 2 1/2 1/2 d = 0 d=0 d = 0
h b ( d ) = H ( 1 − d , d ) + d log 2. h_b(d)=H(1-d,d)+d\log2. h b ( d ) = H ( 1 − d , d ) + d log 2. Its three ordinary capacities are log 2 \log2 log 2 log 2 \log2 log 2 h b ( d t , u ) h_b(d_{t,u}) h b ( d t , u ) c c c
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 d_{t,u} d t , u 1 − d t , u 1-d_{t,u} 1 − d t , u v t , u , W v_{t,u,W} v t , u , W d d d
After Stage B is repaired, its ideal children carry the prescribed v t , u , W v_{t,u,W} v t , u , W V t , W V_{t,W} V t , W v t , u , W v_{t,u,W} v t , u , W
A history records the lot, initial g g g u u u t t t d t , u d_{t,u} d t , u
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 log 2 \log2 log 2 h b ( d t , u ) h_b(d_{t,u}) h b ( d t , u )
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 ∑ min g > 0 A g P g ( t ) , m t , u = 2 m t p t ( u ) ( min t > 0 ) . (35) m_t = 2 \sum_{\min g>0} A_gP_g(t), \qquad m_{t,u}=2m_tp_t(u)\quad(\min t>0). \tag*{(35)} m t = 2 m i n g > 0 ∑ A g P g ( t ) , m t , u = 2 m t p t ( u ) ( min t > 0 ) . (35) 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 ∈ R 3 L_A\in\mathbb{R}^3 L A ∈ R 3 A g A_g A g g g g L B L_B L B m t m_t m t π ( t ) \pi(t) π ( t )
( H ( p X ) , H ( D Y ) − 2 J Y , H ( D Z ) − 2 J Z ) , \left(H(p_X),\ H(D_Y)-2J_Y,\ H(D_Z)-2J_Z\right), ( H ( p X ) , H ( D Y ) − 2 J Y , H ( D Z ) − 2 J Z ) , 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 T T B ∗ B_\ast B ∗ C ∗ C_\ast C ∗
T = ∑ min t > 0 , min u > 0 m t , u , B ∗ = ∑ min t > 0 , min u > 0 m t , u 2 log 2 + h b ( d t , u ) 3 , T=\sum_{\min t>0,\min u>0}m_{t,u},\qquad
B_\ast=\sum_{\min t>0,\min u>0}m_{t,u}\frac{2\log2+h_b(d_{t,u})}{3}, T = m i n t > 0 , m i n u > 0 ∑ m t , u , B ∗ = m i n t > 0 , m i n u > 0 ∑ m t , u 3 2 log 2 + h b ( d t , u ) , C ∗ = B ∗ + 1 3 ∑ i = 0 2 ( L A + L B ) i . (36) C_\ast=B_\ast+\frac{1}{3}\sum_{i=0}^{2}(L_A+L_B)_i. \tag*{(36)} C ∗ = B ∗ + 3 1 i = 0 ∑ 2 ( L A + L B ) i . (36) Suppose, as the numerical certificate verifies, that
T log 2 > B ∗ , C ∗ − ( L A + L B ) i < T log 2 ( 0 ≤ i < 3 ) . (37) T\log2>B_\ast,\qquad C_\ast-(L_A+L_B)_i<T\log2\quad(0\le i<3). \tag*{(37)} T log 2 > B ∗ , C ∗ − ( L A + L B ) i < T log 2 ( 0 ≤ i < 3 ) . (37) The denominator and each numerator below are positive by (38). The numbers
λ i = T log 2 − C ∗ + ( L A + L B ) i 3 ( T log 2 − B ∗ ) ( 0 ≤ i < 3 ) (38) \lambda_i=\frac{T\log2-C_\ast+(L_A+L_B)_i}{3(T\log2-B_\ast)}
\quad(0\le i<3) \tag*{(38)} λ i = 3 ( T log 2 − B ∗ ) T log 2 − C ∗ + ( L A + L B ) i ( 0 ≤ i < 3 ) (38) sum to 1: their numerators sum to 3 ( T log 2 − B ∗ ) 3(T\log2-B_\ast) 3 ( T log 2 − B ∗ ) ? ]. Divide each positive length-2 history class into these proportions. In part i i i i i i d t , u d_{t,u} d t , u
( L C ) i = T log 2 − λ i ∑ min t > 0 , min u > 0 m t , u ( log 2 − h b ( d t , u ) ) = T log 2 − 3 λ i ( T log 2 − B ∗ ) = C ∗ − ( L A + L B ) i . (39) (L_C)_i = T\log2 - \lambda_i \sum_{\min t>0,\min u>0} m_{t,u}(\log2-h_b(d_{t,u}))
= T\log2 - 3\lambda_i(T\log2-B_*) = C_*-(L_A+L_B)_i. \tag*{(39)} ( L C ) i = T log 2 − λ i m i n t > 0 , m i n u > 0 ∑ m t , u ( log 2 − h b ( d t , u )) = T log 2 − 3 λ i ( T log 2 − B ∗ ) = C ∗ − ( L A + L B ) i . (39) Consequently L A + L B + L C = ( C ∗ , C ∗ , C ∗ ) L_A+L_B+L_C=(C_*,C_*,C_*) 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 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 h h ϕ \phi ϕ a h N / 6 a_hN/6 a h N /6 a h a_h a h ρ h \rho_h ρ h ϕ ∘ ρ h \phi\circ\rho_h ϕ ∘ ρ h σ \sigma σ
ϕ = σ ∘ ρ h − 1 . (40) \phi=\sigma\circ\rho_h^{-1}. \tag*{(40)} ϕ = σ ∘ ρ h − 1 . (40) 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 L_A,L_B,L_C L A , L B , L C E > 0 E>0 E > 0
Fix an integer K ≥ 2 K\ge2 K ≥ 2 K K K j j j j j j j + 1 j+1 j + 1 j + 2 j+2 j + 2
A ; A + B ; A + B + C ; … ; A + B + C A + B + C ⏟ K − 2 ticks ; B + C ; C . (41) A;\quad A+B;\quad A+B+C;\quad\ldots;\quad A+B+C\underset{K-2\ \text{ticks}}{\underbrace{\phantom{A+B+C}}};\quad B+C;\quad C. \tag*{(41)} A ; A + B ; A + B + C ; … ; A + B + C K − 2 ticks A + B + C ; B + C ; C . (41) 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
1 6 ( L A + L B + L C ) = 1 6 ( C ∗ , C ∗ , C ∗ ) . \frac{1}{6}(L_A+L_B+L_C)=\frac{1}{6}(C_*,C_*,C_*). 6 1 ( L A + L B + L C ) = 6 1 ( C ∗ , C ∗ , C ∗ ) . Its minimum is C ∗ / 6 C_*/6 C ∗ /6 N C ∗ NC_* N C ∗ N N N
min L A , min ( L A + L B ) , min ( L B + L C ) , min L C , \min L_A,\qquad\min(L_A+L_B),\qquad\min(L_B+L_C),\qquad\min L_C, min L A , min ( L A + L B ) , min ( L B + L C ) , min L C , where min x = min 0 ≤ i < 3 x i \min x = \min_{0 \le i < 3} x_i min x = min 0 ≤ i < 3 x i x x x K K K
β = 2 C ∗ − min L A − min ( L A + L B ) − min ( L B + L C ) − min L C . (42) \beta= 2C_* - \min L_A - \min(L_A + L_B) - \min(L_B + L_C) - \min L_C. \tag*{(42)} β = 2 C ∗ − min L A − min ( L A + L B ) − min ( L B + L C ) − min L C . (42) Using L A + L B + L C = C ∗ 1 L_A + L_B + L_C = C_* \mathbf{1} L A + L B + L C = C ∗ 1 β = ( max L A − min L A ) + ( max L C − min L C ) ≥ 0 \beta= (\max L_A - \min L_A) + (\max L_C - \min L_C) \ge0 β = ( max L A − min L A ) + ( max L C − min L C ) ≥ 0 β < 1 \beta< 1 β < 1 K − 2 K - 2 K − 2 K C ∗ − β KC_* - \beta K C ∗ − β K H 0 KH_0 K H 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 ∗ ) − β K(H_0 + C_*) - \beta K ( H 0 + C ∗ ) − β
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
c ℓ ( j ) = [ x j ] ( 1 + 5 x + x 2 ) ℓ c_\ell(j) = [x^j](1 + 5x + x^2)^\ell c ℓ ( j ) = [ x j ] ( 1 + 5 x + x 2 ) ℓ for the number of labeled weight words of length ℓ \ell ℓ j j j
S 0 = ∑ min g = 0 A g log c 8 ( max g ) , (43) S_0=\sum_{\min g=0} A_g\log c_8(\max g), \tag*{(43)} S 0 = m i n g = 0 ∑ A g log c 8 ( max g ) , (43) S 1 = ∑ min t = 0 m t ( H ( z t ) + ∑ i , j z t ( i , j ) log ( D i D j ) ) , (44) S_1=\sum_{\min t=0}m_t\left(H(z_t)+\sum_{i,j}z_t(i,j)\log(D_iD_j)\right), \tag*{(44)} S 1 = m i n t = 0 ∑ m t ( H ( z t ) + i , j ∑ z t ( i , j ) log ( D i D j ) ) , (44) S 2 = ∑ min t > 0 ∑ u ≤ t , ∑ i u i = 4 m t , u R t , u , (45) S_2=\sum_{\min t>0}\sum_{u\leq t,\ \sum_i u_i=4}m_{t,u}R_{t,u}, \tag*{(45)} S 2 = m i n t > 0 ∑ u ≤ t , ∑ i u i = 4 ∑ m t , u R t , u , (45) S ∗ = S 0 + S 1 + S 2 , S_* = S_0+S_1+S_2, S ∗ = S 0 + S 1 + S 2 , where g g g t t t u u u
R t , u = { 0 , max u = 4 , log 10 , max u = 3 , h b ( d t , u ) + 2 ( 1 − d t , u ) log 5 , max u = 2 , min u = 0 , ( 2 − d t , u ) log 5 , min u > 0. (46) R_{t,u}=
\begin{cases}
0, & \max u=4,\\
\log10, & \max u=3,\\
h_b(d_{t,u})+2(1-d_{t,u})\log5, & \max u=2,\ \min u=0,\\
(2-d_{t,u})\log5, & \min u>0.
\end{cases} \tag*{(46)} R t , u = ⎩ ⎨ ⎧ 0 , log 10 , h b ( d t , u ) + 2 ( 1 − d t , u ) log 5 , ( 2 − d t , u ) log 5 , max u = 4 , max u = 3 , max u = 2 , min u = 0 , min u > 0. (46) In these sums, infeasible or zero-mass populations are omitted.
Proposition 6.1 (Leaf volumes and common dimensions). Fix a finite number K K K (30) ; exact capacity balance is not required for this volume count. For all sufficiently divisible N N N ⟨ a N , b N , c N ⟩ \langle a_N,b_N,c_N\rangle ⟨ a N , b N , c N ⟩
log ( a N b N c N ) ≥ K N S ∗ − O K ( log ( N + 2 ) ) . (47) \log(a_Nb_Nc_N)\geq KNS_*-O_K(\log(N+2)). \tag*{(47)} log ( a N b N c N ) ≥ K N S ∗ − O K ( log ( N + 2 )) . (47) The implied constant may depend on the fixed laws and subdivisions. For limiting real data, the corresponding volume rate can approach S ∗ S_* S ∗
Proof. We first count one terminal population. When a shape has a zero on side X X X Y Y Y Z Z Z 0 ↔ 2 0\leftrightarrow2 0 ↔ 2 1 1 1 M M M ⟨ 1 , 1 , M ⟩ \langle1,1,M\rangle ⟨ 1 , 1 , M ⟩ Y Y Y ⟨ M , 1 , 1 ⟩ \langle M,1,1\rangle ⟨ M , 1 , 1 ⟩ Z Z Z ⟨ 1 , M , 1 ⟩ \langle1,M,1\rangle ⟨ 1 , M , 1 ⟩ x i j y j k z k i x_{ij}y_{jk}z_{ki} x ij y j k z k i M M M M = 1 M=1 M = 1
For an unrestricted length-eight leaf, the generating function above counts the choices on an axis of maximum weight. Complementation is a bijection to the other axis, so the volume is c 8 ( max g ) c_8(\max g) c 8 ( max g ) (43) .
Here is the exact count needed for the restricted leaves. Suppose the statistic on the chosen nonzero side has values σ \sigma σ b σ b_\sigma b σ m m m θ \theta θ n σ = m θ σ n_\sigma=m\theta_\sigma n σ = m θ σ
M ( m , θ ) = m ! ∏ σ n σ ! ∏ σ b σ n σ . (48) M(m,\theta)=\frac{m!}{\prod_\sigma n_\sigma!}\prod_\sigma b_\sigma^{n_\sigma}. \tag*{(48)} M ( m , θ ) = ∏ σ n σ ! m ! σ ∏ b σ n σ . (48) Indeed, first choose the positions of each statistic and then its independent labeled realization at each position. The other side is uniquely determined. Prescribing the pushforward type under complementation on that side retains all these pairs. For a fixed alphabet the multinomial estimate gives
log M ( m , θ ) = m ( H ( θ ) + ∑ σ θ σ log b σ ) + O ( log ( m + 2 ) ) . (49) \log M(m,\theta)=m\left(H(\theta)+\sum_{\sigma}\theta_{\sigma}\log b_{\sigma}\right)+O(\log(m+2)). \tag*{(49)} log M ( m , θ ) = m ( H ( θ ) + σ ∑ θ σ log b σ ) + O ( log ( m + 2 )) . (49) Zero type entries cause no difficulty, with 0 ! = 1 0! = 1 0 ! = 1
At a zero-coordinate length-four leaf, the statistic is the ordered pair ( i , j ) (i,j) ( i , j ) D i D j D_iD_j D i D j z t z_t z t (49) therefore gives precisely the summand in (44) . Within a length-two statistic, 11 has 5 2 = 25 5^2=25 5 2 = 25 D D D z t z_t z t i ≤ j i \le j i ≤ j D i D j D_iD_j D i D j (48) .
The complement involution κ \kappa κ D κ ( i ) = D i D_{\kappa(i)}=D_i D κ ( i ) = D i ( i , j ) (i,j) ( i , j ) ( κ ( i ) , κ ( j ) ) (\kappa(i),\kappa(j)) ( κ ( i ) , κ ( j )) z t z_t z t z t z_t z t
The nonnegative shapes of size four have sorted forms ( 0 , 0 , 4 ) (0,0,4) ( 0 , 0 , 4 ) ( 0 , 1 , 3 ) (0,1,3) ( 0 , 1 , 3 ) ( 0 , 2 , 2 ) (0,2,2) ( 0 , 2 , 2 ) ( 1 , 1 , 2 ) (1,1,2) ( 1 , 1 , 2 ) (46) . The first has volume one. The second has ten matched words, since the weight-three side has either order of weights 1, 2 and five choices for the weight-one label. For the third, write d = d t , u d=d_{t,u} d = d t , u m m m m ( 1 − d ) m(1-d) m ( 1 − d ) m d md m d
( m m d ) 25 m ( 1 − d ) 2 m d . \binom{m}{md}25^{m(1-d)}2^{md}. ( m d m ) 2 5 m ( 1 − d ) 2 m d . Its logarithmic rate is H ( 1 − d , d ) + 2 ( 1 − d ) log 5 + d log 2 H(1-d,d)+2(1-d)\log5+d\log2 H ( 1 − d , d ) + 2 ( 1 − d ) log 5 + d log 2 (46) . Complementation fixes both of these unordered statistics, so the same exact type is allowed on both nonzero sides.
For the positive case, consider first u = ( 1 , 1 , 2 ) u=(1,1,2) u = ( 1 , 1 , 2 ) ( X , Y , Z ) (X,Y,Z) ( X , Y , Z ) Z Z Z d = d t , u d=d_{t,u} d = d t , u
Every selected exact coarse type therefore produces, from m m m
⟨ 5 m ( 1 − d ) , 5 m d , 5 m ( 1 − d ) ⟩ . (50) \left\langle5^{m(1-d)},5^{md},5^{m(1-d)}\right\rangle. \tag*{(50)} ⟨ 5 m ( 1 − d ) , 5 m d , 5 m ( 1 − d ) ⟩ . (50) Its volume is 5 m ( 2 − d ) 5^{m(2-d)} 5 m ( 2 − d ) (46) . This is the dimension of one output with fixed coarse blocks; the choices of coarse blocks have already contributed to the extraction yield. Permuting the physical sides gives the other orientations; the volume remains the same. This formula includes d = 0 d=0 d = 0 d = 1 d=1 d = 1
Both children must be counted in the volume sum. For each positive parent t t t
m t ∑ u p t ( u ) ( R t , u + R t , t − u ) = 2 m t ∑ u p t ( u ) R t , u = ∑ u m t , u R t , u . m_t\sum_u p_t(u)(R_{t,u}+R_{t,t-u})=2m_t\sum_u p_t(u)R_{t,u}=\sum_u m_{t,u}R_{t,u}. m t u ∑ p t ( u ) ( R t , u + R t , t − u ) = 2 m t u ∑ p t ( u ) R t , u = u ∑ m t , u R t , u . The equality changes variables u ↦ t − u u\mapsto t-u u ↦ t − u p t ( u ) = p t ( t − u ) p_t(u)=p_t(t-u) p t ( u ) = p t ( t − u ) d t , u d_{t,u} d t , u d t , t − u d_{t,t-u} d t , t − u P g P_g P g m t m_t m t (43) –(45) count every terminal factor once.
Finally we verify that these counts provide common oriented dimensions, as required by Lemma 2.1. Keep separate every finite class specified by its lot, full ancestry, left or right half, coordinate-label placement on the physical sides, and subdivision for a priority choice. Exact coarse types fix the number of factors in each such class in every output. A simultaneous relabeling of positions on all three sides takes each class to the same canonical set of positions. Its ideal tensor and its prescribed type windows are consequently the same in every output. The recovery argument restores these ideal tensors before the terminal restrictions are made.
Choose once, in each zero-coordinate class with a statistic prescription, the exact matching type used in (48) ; use the same choice in every output. For rational data and divisible N N N (50) or its prescribed side permutation. Multiplying these fixed dimensions over all classes gives one common triple ( a N , b N , c N ) (a_N,b_N,c_N) ( a N , b N , c N )
The parts of each subdivision retain the same prescribed laws, so their leading logarithmic contributions add to that of the original class. Allocating these parts among extraction priorities therefore does not change S ∗ S_* S ∗ K K K (49) over them contributes only O K ( log ( N + 2 ) ) O_K(\log(N+2)) O K ( log ( N + 2 )) K N ( S 0 + S 1 + S 2 ) KN(S_0+S_1+S_2) K N ( S 0 + S 1 + S 2 ) (47) . For real limiting laws, choose consistent rational laws first and then a divisible N N N S ∗ S_* S ∗
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.
Proposition 6.2 (Finite staggered yield). Assume the prescriptions of Section 5, the balance conditions (37) , and positive entries of L A , L B , L C L_A,L_B,L_C L A , L B , L C Let S ∗ = S 0 + S 1 + S 2 S_* = S_0 + S_1 + S_2 S ∗ = S 0 + S 1 + S 2 be the terminal rate defined above. For every fixed integer K ≥ 2 K \ge2 K ≥ 2 and every ϵ > 0 \epsilon> 0 ϵ > 0 suitable fixed rational approximations, part allocations, and tolerances give, for all sufficiently large divisible N N N a restriction of exp ( o K ( N ) ) \exp(o_K(N)) exp ( o K ( N )) copies of C W 5 ⊗ 8 K N \mathrm{CW}_{5}^{\otimes8KN} CW 5 ⊗ 8 K N to s N s_N s N identical matrix tensors of volume V N V_N V N where
log s N N ≥ K ( H 0 + C ∗ ) − β − ϵ , log V N N ≥ K S ∗ − ϵ . (51) \frac{\log s_N}{N} \ge K(H_0+C_*)-\beta-\epsilon,\qquad\frac{\log V_N}{N} \ge KS_*-\epsilon. \tag*{(51)} N log s N ≥ K ( H 0 + C ∗ ) − β − ϵ , N log V N ≥ K S ∗ − ϵ . (51) Proof. Use the initial extractions and the K + 2 K+2 K + 2 (41) . Their total limiting logarithmic yield, divided by N N N K ( H 0 + C ∗ ) − β K(H_0+C_*)-\beta K ( H 0 + C ∗ ) − β K − 2 K-2 K − 2 C ∗ C_* C ∗ (42) . We show that fixed rational data and a finite composition of joint steps attain these rates to within the stated losses.
Fix K K K d d d z z z v v v V V V (38) . For these approximations the full-tick capacities approach C ∗ / 6 C_*/6 C ∗ /6 N N N N N N
There are K K K 6 ( K + 2 ) 6(K+2) 6 ( K + 2 ) exp ( o K ( N ) ) \exp(o_K(N)) exp ( o K ( N )) ϵ \epsilon ϵ K K K N N N o K ( N ) o_K(N) o K ( N )
Proposition 6.1 applies to these fixed rational laws and subdivisions: the schedule keeps all histories distinct, and repair restores their ideal windows before any terminal restriction. Its common exact terminal types and exact Stage C counts give one oriented matrix tensor in every final summand, with volume rate approaching K S ∗ K S_* K S ∗ (51) .
Lemma 2.2 bounds the rank of the replicated source by
exp ( o K ( N ) ) 7 8 K N ( 24 K N + 2 2 ) \exp(o_K(N)) 7^{8KN} \binom{24KN+2}{2} exp ( o K ( N )) 7 8 K N ( 2 24 K N + 2 ) Apply Lemma 2.1 to the identical outputs of Proposition 6.2, divide its logarithm by K N KN K N N → ∞ N \to\infty N → ∞ K K K
H 0 + C ∗ − β K + w 3 S ∗ ≤ 8 log 7. H_0 + C_* - \frac{\beta}{K} + \frac{w}{3}S_* \le8\log7. H 0 + C ∗ − K β + 3 w S ∗ ≤ 8 log 7. Letting K → ∞ K \to\infty K → ∞
H 0 + C ∗ + w 3 S ∗ ≤ 8 log 7. (52) H_0 + C_* + \frac{w}{3}S_* \le8\log7. \tag*{(52)} H 0 + C ∗ + 3 w S ∗ ≤ 8 log 7. (52) Only fixed finite schedules were used; no estimate uniform in a simultaneously growing K K K
Exact parameters and numerical certification
We now evaluate the logarithmic yield rate H 0 + C ∗ H_0 + C_* H 0 + C ∗ S ∗ S_* S ∗ S ∗ > 0 S_* > 0 S ∗ > 0 (52) . 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 n n
F ( n ) = ( ∑ j = 0 16 ( n / 640000 ) j j ! ) 64 . (53) F(n) = \left(\sum_{j=0}^{16}\frac{(n/640000)^j}{j!}\right)^{64}. \tag*{(53)} F ( n ) = ( j = 0 ∑ 16 j ! ( n /640000 ) j ) 64 . (53) The initial weights, the two split-weight arrays, and the terminal weights use 223 distinct arguments of F F F − 120770 -120770 − 120770 45052 45052 45052 n / 10 6 n/10^6 n /1 0 6 F F F
2 − 23 < F ( n ) < 2 23 . (54) 2^{-23} < F(n) < 2^{23}. \tag*{(54)} 2 − 23 < F ( n ) < 2 23 . (54) 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 s s 2 ℓ 2\ell 2 ℓ
B ( s ) = { b ∈ Z ≥ 0 3 : b 0 + b 1 + b 2 = ℓ , b i ≤ s i ( 0 ≤ i < 3 ) } . \mathcal{B}(s)=\{b\in\mathbb{Z}_{\geq0}^{3}: b_0+b_1+b_2=\ell,\ b_i\leq s_i\ (0\leq i<3)\}. B ( s ) = { b ∈ Z ≥ 0 3 : b 0 + b 1 + b 2 = ℓ , b i ≤ s i ( 0 ≤ i < 3 )} . The arrays are consumed as follows.
The 17 entries a 0 , … , a 16 a_0,\ldots,a_{16} a 0 , … , a 16
A g = mult ( g ) ∏ i = 0 2 F ( a g i ) ∑ h 0 ≤ h 1 ≤ h 2 , ∑ h i = 16 mult ( h ) ∏ i = 0 2 F ( a h i ) , mult ( g ) = 3 ! ∏ j ( # { i : g i = j } ) ! . A_g=\frac{\operatorname{mult}(g)\prod_{i=0}^{2}F(a_{g_i})}{\sum_{h_0\leq h_1\leq h_2,\ \sum h_i=16}\operatorname{mult}(h)\prod_{i=0}^{2}F(a_{h_i})},\qquad\operatorname{mult}(g)=\frac{3!}{\prod_j(\#\{i:g_i=j\})!}. A g = ∑ h 0 ≤ h 1 ≤ h 2 , ∑ h i = 16 mult ( h ) ∏ i = 0 2 F ( a h i ) mult ( g ) ∏ i = 0 2 F ( a g i ) , mult ( g ) = ∏ j ( # { i : g i = j })! 3 ! . Thus the law on ordered shapes, before coalescing permutations, is a product of three one-coordinate weights.
The 118 entries in the Stage A array are read over all positive sorted g g g ordered t t t s s s ℓ = 1 2 ∑ i s i \ell=\frac{1}{2}\sum_i s_i ℓ = 2 1 ∑ i s i i = 0 , 1 , 2 i=0,1,2 i = 0 , 1 , 2 k = s i k=s_i k = s i n s , i ( j ) n_{s,i}(j) n s , i ( j )
max ( 0 , k − ℓ ) ≤ j < ⌊ k / 2 ⌋ , n s , i ( ⌊ k / 2 ⌋ ) = 0 \max(0,k-\ell)\leq j<\lfloor k/2\rfloor,\qquad n_{s,i}(\lfloor k/2\rfloor)=0 max ( 0 , k − ℓ ) ≤ j < ⌊ k /2 ⌋ , n s , i (⌊ k /2 ⌋) = 0 (the final zero consumes no entry). For b ∈ B ( s ) b\in\mathcal{B}(s) b ∈ B ( s )
w s ( b ) = ∏ i = 0 2 F ( n s , i ( min ( b i , s i − b i ) ) ) , q s ( b ) = w s ( b ) ∑ c ∈ B ( s ) w s ( c ) . w_s(b)=\prod_{i=0}^{2}F(n_{s,i}(\min(b_i,s_i-b_i))),\qquad q_s(b)=\frac{w_s(b)}{\sum_{c\in\mathcal{B}(s)}w_s(c)}. w s ( b ) = i = 0 ∏ 2 F ( n s , i ( min ( b i , s i − b i ))) , q s ( b ) = ∑ c ∈ B ( s ) w s ( c ) w s ( b ) . Use P g = q g P_g=q_g P g = q g p t = q t p_t=q_t p t = q t q s ( b ) = q s ( s − b ) q_s(b)=q_s(s-b) q s ( b ) = q s ( s − b )
Read the 75 entries of the fourth array over positive ordered t t t u ∈ B ( t ) u\in\mathcal{B}(t) u ∈ B ( t ) max u = 2 \max u=2 max u = 2 n n n d t , u = n / 10 6 d_{t,u}=n/10^6 d t , u = n /1 0 6 0 ≤ d t , u ≤ 0.110106 0\leq d_{t,u}\leq0.110106 0 ≤ d t , u ≤ 0.110106
Read the 36 entries of the fifth array over all ordered t t t t t t
( i , j ) , 0 ≤ i ≤ j ≤ 5 , r i + r j = max t . (i,j),\qquad0\leq i\leq j\leq5,\qquad r_i+r_j=\max t. ( i , j ) , 0 ≤ i ≤ j ≤ 5 , r i + r j = max t . Read an integer for each pair except the last, whose integer is zero. Assign its F F F ( i , j ) (i,j) ( i , j ) ( j , i ) (j,i) ( j , i ) ordered pairs to obtain z t z_t z t D i D j D_iD_j D i D j
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 ) (6,1,1) ( 6 , 1 , 1 ) z z z
The complement prescriptions in Section 5 can be checked without logarithms. On the six statistic slots, κ \kappa κ D κ ( i ) = D i D_{\kappa(i)}=D_i D κ ( i ) = D i r κ ( i ) = 4 − r i r_{\kappa(i)}=4-r_i r κ ( i ) = 4 − r i z t z_t z t
d ( 1 , 3 , 4 ) , ( 0 , 2 , 2 ) = 92966 10 6 , d ( 1 , 3 , 4 ) , ( 1 , 1 , 2 ) = 1204 10 6 . d_{(1,3,4),(0,2,2)}=\frac{92966}{10^6},\qquad d_{(1,3,4),(1,1,2)}=\frac{1204}{10^6}. d ( 1 , 3 , 4 ) , ( 0 , 2 , 2 ) = 1 0 6 92966 , d ( 1 , 3 , 4 ) , ( 1 , 1 , 2 ) = 1 0 6 1204 . 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 x x
K ( x ) = ( ∑ i x i ) log ( ∑ i x i ) − ∑ i x i log x i , 0 log 0 = 0. \mathcal{K}(x)=\left(\sum_i x_i\right)\log\left(\sum_i x_i\right)-\sum_i x_i\log x_i,\qquad0\log0=0. K ( x ) = ( i ∑ x i ) log ( i ∑ x i ) − i ∑ x i log x i , 0 log 0 = 0. Thus K ( x ) = M H ( x / M ) \mathcal{K}(x)=MH(x/M) K ( x ) = M H ( x / M ) M = ∑ i x i > 0 M=\sum_i x_i>0 M = ∑ i x i > 0 K ( 0 ) = 0 \mathcal{K}(0)=0 K ( 0 ) = 0 s s s q q q ( X , Y , Z ) (X,Y,Z) ( X , Y , Z ) Q b , W Q_{b,W} Q b , W
D W ( i , j ) = ∑ b ∈ B ( s ) q ( b ) Q b , W ( i ) Q s − b , W ( j ) . D_W(i,j)=\sum_{b\in\mathcal{B}(s)}q(b)Q_{b,W}(i)Q_{s-b,W}(j). D W ( i , j ) = b ∈ B ( s ) ∑ q ( b ) Q b , W ( i ) Q s − b , W ( j ) . For W = Y W=Y W = Y I W = { b : b Z = 0 } \mathcal{I}_W=\{b:b_Z=0\} I W = { b : b Z = 0 } W = Z W=Z W = Z I W = { b : b X b Y = 0 } \mathcal{I}_W=\{b:b_Xb_Y=0\} I W = { b : b X b Y = 0 }
J W = ∑ b ∈ I W q ( b ) K ( Q b , W ) + ∑ k = 0 s W K ( ∑ b ∉ I W b W = k q ( b ) Q b , W ) . (55) 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*{(55)} J W = b ∈ I W ∑ q ( b ) K ( Q b , W ) + k = 0 ∑ s W K b ∈ / I W b W = k ∑ q ( b ) Q b , W . (55) The capacity vector is
( K ( ( ∑ b : b X = k q ( b ) ) k ) , K ( D Y ) − 2 J Y , K ( D Z ) − 2 J Z ) . \left(\mathcal{K}\left(\left(\sum_{b:b_X=k}q(b)\right)_k\right),\mathcal{K}(D_Y)-2J_Y,\mathcal{K}(D_Z)-2J_Z\right). K ( b : b X = k ∑ q ( b ) ) k , K ( D Y ) − 2 J Y , K ( D Z ) − 2 J Z . At A substitute ( s , q , Q ) = ( g , P g , V ) (s,q,Q)=(g,P_g,V) ( s , q , Q ) = ( g , P g , V ) A g A_g A g ( t , p t , v t , ⋅ , ⋅ ) (t,p_t,v_{t,\cdot,\cdot}) ( t , p t , v t , ⋅ , ⋅ ) m t m_t m t H 0 H_0 H 0 B ∗ B_* B ∗ T T T S 0 S_0 S 0 S 1 S_1 S 1 S 2 S_2 S 2
Table 1 (PDF p. 30). Partial sums defining L A L_A L A L B L_B L B 4.795 ⋅ 10 − 10 4.795 \cdot10^{-10} 4.795 ⋅ 1 0 − 10
Proposition 7.1 (Numerical certificate). The exact parameters above satisfy every positivity and balance condition used in Proposition 6.2. All thirty partial capacity entries in Table 1 are positive. In particular, S ∗ > 0 S_* > 0 S ∗ > 0 T log 2 − B ∗ > 0 T \log2 - B_* > 0 T log 2 − B ∗ > 0 L A L_A L A L B L_B L B L C L_C L C
5.612983956059236756 < H 0 + C ∗ < 5.612983956059236757 (56) 5.612983956059236756 < H_0 + C_* < 5.612983956059236757 \tag*{(56)} 5.612983956059236756 < H 0 + C ∗ < 5.612983956059236757 (56) 12.594770321594676362 < S ∗ < 12.594770321594676363 (57) 12.594770321594676362 < S_* < 12.594770321594676363 \tag*{(57)} 12.594770321594676362 < S ∗ < 12.594770321594676363 (57) 2.371054886006745684 < 3 ( 8 log 7 − H 0 − C ∗ ) S ∗ < 2.371054886006745685 (58) 2.371054886006745684 < \frac{3(8\log7 - H_0 - C_*)}{S_*} < 2.371054886006745685 \tag*{(58)} 2.371054886006745684 < S ∗ 3 ( 8 log 7 − H 0 − C ∗ ) < 2.371054886006745685 (58) With Ω = 2.371056 \Omega= 2.371056 Ω = 2.371056
0.000004676829725968 < H 0 + C ∗ + Ω 3 S ∗ − 8 log 7 < 0.000004676829725969 (59) 0.000004676829725968 < H_0 + C_* + \frac{\Omega}{3}S_* - 8\log7 < 0.000004676829725969 \tag*{(59)} 0.000004676829725968 < H 0 + C ∗ + 3 Ω S ∗ − 8 log 7 < 0.000004676829725969 (59) Proof. We give the elementary interval rule and its error accounting, so that the certificate does not depend on assuming decimal logarithms are accurate. For 1 ≤ y ≤ 2 1 \le y \le2 1 ≤ y ≤ 2
P ( y ) = 2 ∑ j = 0 30 1 2 j + 1 ( y − 1 y + 1 ) 2 j + 1 , L ( x ) = e P ( 2 ) + P ( 2 − e x ) , e = ⌊ log 2 x ⌋ . P(y) = 2\sum_{j=0}^{30}\frac{1}{2j+1}\left(\frac{y-1}{y+1}\right)^{2j+1}, \qquad L(x) = eP(2) + P(2^{-e}x), \quad e = \left\lfloor\log_2 x \right\rfloor. P ( y ) = 2 j = 0 ∑ 30 2 j + 1 1 ( y + 1 y − 1 ) 2 j + 1 , L ( x ) = e P ( 2 ) + P ( 2 − e x ) , e = ⌊ log 2 x ⌋ . For rational x > 0 x > 0 x > 0 e e e 2 / ( 1 − z 2 ) 2/(1-z^2) 2/ ( 1 − z 2 )
0 ≤ log y − P ( y ) ≤ τ : = 2 ⋅ 3 − 63 63 ( 1 − 1 / 9 ) < 3.120348 ⋅ 10 − 32 . 0 \le\log y - P(y) \le\tau:= \frac{2 \cdot3^{-63}}{63(1-1/9)} < 3.120348 \cdot10^{-32}. 0 ≤ log y − P ( y ) ≤ τ := 63 ( 1 − 1/9 ) 2 ⋅ 3 − 63 < 3.120348 ⋅ 1 0 − 32 . Thus ∣ log x − L ( x ) ∣ ≤ ( ∣ e ∣ + 1 ) τ |\log x - L(x)| \le(|e|+1)\tau ∣ log x − L ( x ) ∣ ≤ ( ∣ e ∣ + 1 ) τ e < 0 e < 0 e < 0 L L L e P ( 2 ) + P ( 2 ) = ( e + 1 ) P ( 2 ) eP(2) + P(2) = (e+1)P(2) e P ( 2 ) + P ( 2 ) = ( e + 1 ) P ( 2 ) ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) P P P log x \log x log x ∣ e ∣ < 2048 |e| < 2048 ∣ e ∣ < 2048 (54) , a nonzero product-law probability exceeds 2 − 146 2^{-146} 2 − 146 z z z 2 − 54 2^{-54} 2 − 54 2 − 20 2^{-20} 2 − 20 2 − 148 2^{-148} 2 − 148 V V V 2 − 186 2^{-186} 2 − 186 2 − 332 2^{-332} 2 − 332 2 − 518 2^{-518} 2 − 518 7 8 < 2 23 7^8 < 2^{23} 7 8 < 2 23 2 − 518 2^{-518} 2 − 518 2 23 2^{23} 2 23
ϵ = 2048 τ < 6.391 ⋅ 10 − 29 . (60) \epsilon= 2048\tau< 6.391 \cdot10^{-29}. \tag*{(60)} ϵ = 2048 τ < 6.391 ⋅ 1 0 − 29 . (60) Here is an independent propagation bound for replacing every logarithm literally by L \mathcal{L} L K \mathcal{K} K M M M K \mathcal{K} K 2 M ϵ 2M\epsilon 2 M ϵ (55) sum to one, so its error is at most 2 ϵ 2\epsilon 2 ϵ ( 2 , 6 , 6 ) ϵ (2,6,6)\epsilon ( 2 , 6 , 6 ) ϵ T T T L A + L B L_A+L_B L A + L B ( 6 , 18 , 18 ) ϵ (6,18,18)\epsilon ( 6 , 18 , 18 ) ϵ 14 ϵ 14\epsilon 14 ϵ h b ( d ) h_b(d) h b ( d ) 3 ϵ 3\epsilon 3 ϵ B ∗ B_* B ∗ 20 ϵ / 3 20\epsilon/3 20 ϵ /3 H 0 H_0 H 0
∣ error in ( H 0 + C ∗ ) ∣ ≤ 68 3 ϵ . \lvert\text{error in }(H_0+C_*)\rvert\le\frac{68}{3}\epsilon. ∣ error in ( H 0 + C ∗ )∣ ≤ 3 68 ϵ . For S 0 , S 1 , S 2 S_0,S_1,S_2 S 0 , S 1 , S 2 ϵ \epsilon ϵ 6 ϵ 6\epsilon 6 ϵ 20 ϵ 20\epsilon 20 ϵ
∣ error in S ∗ ∣ ≤ 27 ϵ , ∣ error in the comparison at Ω ∣ ≤ ( 68 3 + 9 Ω + 8 ) ϵ < 3.324 ⋅ 10 − 27 . \lvert\text{error in }S_*\rvert\le27\epsilon,\qquad
\lvert\text{error in the comparison at }\Omega\rvert\le\left(\frac{68}{3}+9\Omega+8\right)\epsilon< 3.324\cdot10^{-27}. ∣ error in S ∗ ∣ ≤ 27 ϵ , ∣ error in the comparison at Ω ∣ ≤ ( 3 68 + 9Ω + 8 ) ϵ < 3.324 ⋅ 1 0 − 27 . The file verification/scripts/verify_parameters.py implements the stated finite contractions. It constructs every F ( n ) F(n) F ( n ) 10 − 76 10^{-76} 1 0 − 76 3 ⋅ 10 − 29 3\cdot10^{-29} 3 ⋅ 1 0 − 29
In addition to (56) –(59) , the resulting bounds include
0.468025165562828972 < T log 2 − B ∗ < 0.468025165562828973. 0.468025165562828972 < T\log2-B_* < 0.468025165562828973. 0.468025165562828972 < T log 2 − B ∗ < 0.468025165562828973. The following entries enclose L C L_C L C b i = T log 2 − C ∗ + ( L A + L B ) i b_i=T\log2-C_*+(L_A+L_B)_i b i = T log 2 − C ∗ + ( L A + L B ) i λ i \lambda_i λ i 10 − 15 10^{-15} 1 0 − 15
Table 1 (PDF p. 31).
The fractions sum to one exactly by their definition, since the sum of their numerators is 3 ( T log 2 − B ∗ ) 3(T\log2-B_*) 3 ( T log 2 − B ∗ ) L A , L B L_A,L_B L A , L B
0.533798153 < 2 C ∗ − min i ( L A ) i − min i ( L A + L B ) i − min i ( L B + L C ) i − min i ( L C ) i < 0.533798155 < 1. 0.533798153 < 2C_*-\min_i(L_A)_i-\min_i(L_A+L_B)_i-\min_i(L_B+L_C)_i-\min_i(L_C)_i < 0.533798155 < 1. 0.533798153 < 2 C ∗ − i min ( L A ) i − i min ( L A + L B ) i − i min ( L B + L C ) i − i min ( L C ) i < 0.533798155 < 1. These bounds verify all stated feasibility conditions. The script checks every displayed enclosure and stores the full interval outputs with the packaged integer data.
The rounded entries in Table 1 and Table 2 already certify ω < 2.371056 \omega< 2.371056 ω < 2.371056 (58) . For the rounded-table check, allow independent errors of 4 ⋅ 10 − 8 4 \cdot10^{-8} 4 ⋅ 1 0 − 8 H 0 H_0 H 0 B ∗ B_* B ∗
Table 2. The other scalar contractions, each with absolute error less than 3 ⋅ 10 − 8 3 \cdot10^{-8} 3 ⋅ 1 0 − 8
( 12 + Ω ) 4 ⋅ 10 − 8 = 5.7484224 ⋅ 10 − 7 . (12+\Omega)4\cdot10^{-8}=5.7484224\cdot10^{-7}. ( 12 + Ω ) 4 ⋅ 1 0 − 8 = 5.7484224 ⋅ 1 0 − 7 . Using the displayed centers and an outward bound on 8 log 7 8\log7 8 log 7 4.1011 ⋅ 10 − 6 4.1011\cdot10^{-6} 4.1011 ⋅ 1 0 − 6
Proof of Theorem 1.1. Since S ∗ > 0 S_*>0 S ∗ > 0
ω ≤ w ≤ 3 ( 8 log 7 − H 0 − C ∗ ) S ∗ < 2.371054886006746 < 2.371054887. \omega\le w \le\frac{3(8\log7-H_0-C_*)}{S_*}<2.371054886006746<2.371054887. ω ≤ w ≤ S ∗ 3 ( 8 log 7 − H 0 − C ∗ ) < 2.371054886006746 < 2.371054887. 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.
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 a 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 P 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 p 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 d 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 z 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
