Complex Matrix Multiplication Below 2.258 and Rectangular Bounds

1 Introduction

Matrix multiplication asks for the bilinear map (A,B)\mapsto AB, where the two input matrices have compatible sizes. Its arithmetic complexity measures the number of field operations needed to compute all entries of the product. Except in the field-transfer results of Section 14, the field is \C, and the constants in an algorithm may belong to \C. For 0\le k\le1, let

be the infimum of exponents for multiplying an n\times\lceil n^k\rceil matrix by a \lceil n^k\rceil\times n matrix. The bound w(k)\le\tau means that for every \varepsilon>0 these products can be computed using O(n^{\tau+\varepsilon}) arithmetic operations. The square exponent is \omega=w(1), and the dual exponent is

The output size gives w(k)\ge2. Thus \alpha measures how far the inner dimension can grow while multiplication retains the exponent of its output size. Square and rectangular multiplication are basic operations in algebraic algorithms; controlling the rectangular shape can matter even when a square bound is already available.

1.1 Context and main result

Strassen’s rank-seven algorithm for 2\times2 multiplication gave \omega\le\log_2 7, establishing subcubic arithmetic complexity [28]. Approximate bilinear algorithms and their conversion to exact algorithms [5], Schönhage’s asymptotic sum inequality [24], and Strassen’s laser method [30] made tensor powers and degenerations central to subsequent advances. Coppersmith and Winograd combined low-border-rank tensors with arithmetic-progression constructions [10]. Their extraction method restricts powers of a small tensor to direct sums of matrix products, whose dimensions enter the asymptotic sum inequality; their tensor-square analysis gave \omega<2.375477 [10, Section 8]. Higher powers and more detailed analyses of these tensors led to the improvements of Stothers, Vassilevska Williams, and Le Gall [18, 27, 32].

Rectangular multiplication requires separate control of the three matrix dimensions. Early work of Coppersmith and of Lotti and Romani developed this direction [8, 20]; later constructions of Coppersmith, Le Gall, and Le Gall and Urrutia improved the available rectangular and dual bounds [9, 17, 19]. Recent advances include the refined laser method of Alman and Vassilevska Williams [2], the asymmetric hashing of Duan, Wu, and Zhou [14], and the square and rectangular analyses of Vassilevska Williams, Xu, Xu, and Zhou [33] and Alman, Duan, Vassilevska Williams, Xu, Xu, and Zhou [1]. The four-author work establishes \alpha\ge0.321334; these two papers also give detailed tables of rectangular estimates. Dupont et al. subsequently optimized the asymmetric framework at a larger scale to obtain \omega<2.371177 [15], a bound incorporated into the updated table of [1].

The common extraction problem is to separate many candidate products that share variables, while accounting for the cost of every operation used to separate them. We adjoin auxiliary group tensors that both resolve shared labels and supply useful matrix-product factors. Their full rank cost enters the resulting inequalities. This construction gives the following bounds.

Corollary 14.1 transfers the strict square and k=0.709 inequalities to every field of characteristic zero or outside one finite set of positive characteristics, in the same arithmetic-operation model. It selects two fixed exact rank schemes, realizes their coefficients over one number field, and specializes their polynomial identities. The exceptional primes are not computed. Corollary 14.2 also gives the same dual-exponent bound over every field of characteristic zero. No dual-exponent transfer in positive characteristic is asserted.

The square bound also lowers the arithmetic exponent of basic linear-algebra tasks. Given A\in\C^{n\times n} and b\in\C^n, one can compute \det A and, when A is nonsingular, A^{-1} and the solution of Ax=b, using O(n^c) field operations for some fixed c<2.258, with exact zero tests for pivot selection. Choose \omega<c<2.258 and apply the fast elimination reductions of Strassen [28] and Ibarra, Moran, and Hui [16, Theorem 2.1 and Corollary 2.1].

Two applications of the same separation lemma prove the theorem. The square bound uses finite tensor constructions, a differential comparison for their attainable values, and an exact numerical certificate. The dual and rectangular bounds come from explicit conditional-label trees and rational entropy certificates. We also optimize all leaf probability laws in a specified finite family of such trees, obtaining a bound for every aspect ratio in [0,1]. The square and rectangular construction families, and the precise way a square estimate augments the latter, are described below.

1.2 Separating labels with an auxiliary tensor

A trilinear tensor is a sum of monomials xyz, with variables drawn from three finite coordinate sets X,Y,Z. Its rank is the least number of products of three linear forms needed to express it. A restriction substitutes linear forms separately on the three sides. A degeneration allows parameter-dependent substitutions and takes a leading coefficient. Border rank is the least rank of tensors approaching the given tensor. These operations are local: a coordinate substitution cannot depend on information visible only on another side.

Suppose that the supported monomials carry K labels, and that each of two sides can independently determine the label from its own coordinate. The third side may still share variables between labels. The pairwise separation lemma, Lemma 3.3, tensors the input with a finite abelian group-addition tensor of rank K^{1+o(1)}. Local projections then give a direct sum over the labels, with a size-K dot-product factor on the two original readers in every summand. The label is now visible on all three sides. Dot-product factors on the three possible reader pairs combine into a matrix multiplication tensor.

The construction combines Fourier diagonalization of the group tensor with tags of equal Euclidean norm and a separate constant-inner-product slice for each tag. Its geometry adapts Behrend’s construction [4], following the progression-free constructions of Salem and Spencer [23]. The use of group algebras also has an established place in the approach of Cohn and Umans [7]; the local separation identity needed here is proved in full. It preserves every original coordinate and coefficient, including additional tensor indices correlated across occurrences. Consequently the same identity can be applied inside a previously restricted tensor. A separate support argument ensures that every summand counted in an application is nonzero.

Successive separations are organized by exact conditional counts. Once a preceding label is direct on all three sides, each side can locate the positions on which the next operation acts. Fixing the number of each possible continuation makes the next auxiliary tensor and the output dimensions common to all branches. The multinomial counts and entropy chain rule are the standard method-of-types tools [13, 25]; locality and the uniform tensor accounting are proved alongside them here.

1.3 The square bound: finite constructions and comparison

The square argument starts from the six-term Coppersmith–Winograd tensor

which has border rank three [10, Section 7, equation (10)]. A five-term degeneration of T has three groups, each detectable on one designated side. A local degeneration of three copies retains 75 scalar components. Separating their successive labels gives the elementary estimate \omega\le9\log3/\log75<2.290108 in Theorem 3.7. This example displays the auxiliary-rank accounting before the larger construction is introduced.

For a proposed exponent \beta, suppose a finite construction from n copies of T and an auxiliary tensor of border rank at most R produces L independent matrix products of common dimensions a\times b by b\times c. Its normalized score is

Schönhage’s asymptotic sum inequality implies that a score strictly greater than \log3 proves \omega<\beta. Thus the square argument must produce a strict score gain while retaining the entire auxiliary charge.

We organize the finite constructions by their source distribution. There are six collections of original tensor occurrences, called orientation banks, one for each permutation of the three sides. The distribution records the same exact frequencies in the original coordinates of each bank. This keeps a physical permutation of a tensor distinct from a change of its recorded law. The square sections use \alpha for this vector-valued source law; the dual exponent in Theorem 1.1 is a scalar. A construction preserves arbitrary unresolved tensors attached to its original words, and its output labels identify distinct surviving words. Taking the closure of the finite law–score pairs gives a continuous concave attainable-value function. Conditional pooling and a new application of the group separator to each longer pool provide the composition properties needed in the comparison.

The key analytic step uses restrictions on sums of the local grades i,j,k. Each side can read its own sum. Windows placed at progression-free target indices force the three locally read targets to agree, creating another direct label. The progression-free construction and the matching argument have the ancestry of Behrend and Coppersmith–Winograd [4, 10]. To exploit the new labels, a finite-horizon control steers every word allowed by its controls into the assigned terminal window. This every-word guarantee is what permits all the resulting tensor summands to be counted. Exact rational prefix populations then translate the finite control tree into local tensor maps with common auxiliary supplies.

This construction forces a differential inequality on any smooth function touching the attainable value from below. The covariance of the local grades determines the weighted combination of second derivatives in this inequality. Smooth touching tests and strict comparison follow the viscosity-solution methodology of Crandall and Lions and of Crandall, Ishii, and Lions [11, 12]; the required inequality and comparison are proved directly from the finite tensor constructions. A rational polynomial chart and a polynomial barrier then give the strict score gain at an interior source distribution. Boundary constructions supply the initial lower estimates, while explicit residual, interpolation, and rounding bounds turn the finite integer checks into inequalities on the entire comparison domain.

Finally, a strict gain in the closed attainable set selects one actual finite construction with score greater than \log3. Its law may be close to the chart’s central law. All control horizons, rational approximations, group sizes, and bank sizes are fixed before the asymptotic sum inequality is applied.

1.4 Rectangular bounds and finite-family optimization

The rectangular argument tracks the three matrix dimensions separately. A readable label tree partitions a tensor’s support until each leaf is one monomial; at every node, conditional on the preceding labels, the next child is independently readable on two specified sides. Fix a rational probability law on its leaves and apply the tree to an admissible number of copies with those exact leaf frequencies; arbitrary leaf laws follow by approximation. The number of child words at a node is a multinomial coefficient. The product of these coefficients is exactly the number of final direct summands, so the leading auxiliary rank charge is canceled by this multiplicity in the equal-summand inequality. The three remaining logarithmic dimensions are the conditional entropies accumulated on the three reader pairs. This is Theorem 9.2.

Explicit polynomial degenerations giving border-rank bounds two and three supply the initial trees. Their supports have three colors, with a designated side able to detect its own color. A completion takes several copies, chooses a center color, and retains color words containing at most one distinct noncenter color. Local color tests implement this leading-term degeneration and preserve the conditional trees. Deleting one color at the end gives a fully readable tree. The family \calF_7 consists of both bases, at most seven completions of sizes two or three, all center choices, all pairs of retained colors, and all choices of a distinguished side.

For each member of this finite family, a three-state recurrence maximizes every nonnegative weighted sum of its incident and nonincident conditional entropies over all leaf laws. Its support function therefore describes the closed downward convex hull of the normalized rate pairs exactly. Theorem 11.3 turns this description into a maximization over one real parameter for each aspect ratio. An available square estimate contributes one additional rate point. In particular, the square part of Theorem 1.1 supplies the point for p=2.258. This finite-family optimization is distinct from the square attainable-value construction with orientation banks and count windows.

Two explicit laws give the dual and rectangular conclusions. For the dual exponent, an exact conditional-independence identity preserves all the entropy of a uniform coordinate word on its incident reader pairs. This equality certifies exponent two, and the remaining entropy certifies the inner dimension. A small fiber histogram gives the rectangular point. Rational enclosures establish their strict numerical margins. The same finite family also gives an independent square bound below 2.267 by an integer leaf count.

Section 13 compares the resulting bounds with the specified numerical tables of [1, 33], augmented by the same square point p=2.258 and closed under the ordinary combination operations stated there. The new bounds strictly improve this table baseline for 0.321334<k<1. This comparison concerns recorded upper estimates. Extensions to additional estimates retain their stated separator or envelope hypotheses, and strict improvement is asserted only where the enlarged baseline itself exceeds two.

1.5 Organization

Section 2 establishes the tensor and arithmetic-exponent conventions. Section 3 proves the shared separation lemma and the finite tensor constructions. The square argument begins in Sections 4 and 5, which define the attainable values and prove the count-window comparison. Section 6 establishes the three-state boundary estimate used by the numerical certificate in Section 7. Section 8 extracts the finite witness proving the square part of Theorem 1.1. Sections 9, 10 and 11 develop conditional entropy, completion trees, and exact finite-family optimization. Section 12 proves the remaining parts of Theorem 1.1, and Section 13 gives the baseline comparisons. Section 14 proves the finite-exception field corollary from two exact rank witnesses and the characteristic-zero dual corollary using accuracy-dependent witnesses. The appendices give barrier coefficients and reproduction details.

2 Tensors and arithmetic exponents

We first fix the tensor conventions shared by the square and rectangular constructions, then relate rank and explicit polynomial degenerations to arithmetic exponents. The equal-summand inequality at the end of the section will convert separated tensors into rectangular bounds.

All vector spaces and tensors are over \C. A tensor on three finite coordinate sets X,Y,Z is identified with a trilinear form

A restriction is obtained by a linear map on each of the three sides. In particular, a local zeroing-out sets selected variables on each side to zero. A degeneration U\unrhd V permits these maps to depend polynomially or Laurent polynomially on a parameter and extracts the transformed tensor’s first nonzero coefficient, after an overall rescaling. The maps may be composed finitely many times. Finitely many parameters can be replaced by sufficiently separated powers of a single parameter.

The rank \rank(T) is the minimum number of products of three linear forms whose sum is T. Its border rank \brank(T) is the least integer r such that tensors of rank at most r can approach T. Border rank is submultiplicative under tensor product and cannot increase under degeneration. The direct sum U\oplus V uses disjoint variable spaces on all three sides. A claimed direct sum must therefore have both disjoint pieces and no additional terms joining their variables.

Our matrix-multiplication convention is

For positive integers l_1,l_2,l_3, write \mathcal R(l_1,l_2,l_3)=\rank\langle l_1,l_2,l_3\rangle.

For a_1,a_2,a_3\ge0, let W(a_1,a_2,a_3) denote the arithmetic exponent for the three dimensions \lceil n^{a_i}\rceil. The trilinear interpretation makes W invariant under permutations, including those implemented by transposition. In particular w(k)=W(1,k,1).

All logarithms in this paper are natural. The properties in Lemma 2.1 imply that w is convex. For instance, subadditivity and homogeneity applied to \lambda(1,k_1,1)+(1-\lambda)(1,k_2,1) give its usual convexity inequality.

The approximate bilinear algorithms of Bini [5] and the asymptotic-sum method of Schönhage [24] motivate the following explicit form of a rank budget. We use polynomial border-rank witnesses. Saying that T has cost R means that T, up to a nonzero scalar, is the first nonzero coefficient of a polynomial or Laurent polynomial tensor family with a rank-R decomposition. This is a supplied witness and a certified upper bound, which need not be minimal. It implies \brank(T)\le R; it is not our definition of border rank. All uses of cost below have an explicit witness, so no converse assertion about arbitrary border-rank limits is needed. Coordinate restrictions and monomial leading-term degenerations preserve such witnesses and their budgets. Finitely many parameters can be combined into one by assigning sufficiently separated powers, so a composition of the operations used below again has a univariate witness.

The following interpolation argument is the border-to-exact transfer for polynomial approximate bilinear algorithms [5].

A dot tensor on the pair Y,Z of size D is x_0\sum_{j=1}^D y_jz_j. The product of dot tensors on the three pairs is a matrix-multiplication tensor. More precisely, if their lengths on XY,XZ,YZ are d_{XY},d_{XZ},d_{YZ}, respectively, their product is

Thus the edge XZ supplies the index i, the edge XY supplies j, and the edge YZ supplies k in our convention. Dot sizes on the same pair multiply. A tuple of logarithmic edge rates listed in the order (XY,XZ,YZ) therefore gives matrix-dimension rates in the order (XZ,XY,YZ). By the permutation invariance in Lemma 2.1, either order gives the same value of W. This accounts for the edge-rate order used in the later conditional-label entropy bound.

This is the equal-summand rectangular form of the asymptotic-sum principle [24]. The proof applies it to each fixed instance before varying that instance. Later auxiliary tensors may therefore grow with a type parameter without any uniformity assumption on the interpolation constant in Lemma 2.2.

3 Finite tensor constructions

The elementary construction in this section already gives \omega\leq 9\log 3/\log 75=2.290107196\ldots. Its main ingredient separates a label that two parties can read independently. The operation supplies the missing label to the third party and leaves a large dot product. We pay for the auxiliary tensor that performs this operation. At the exponential scale, the new direct labels compensate for that payment, while the dot product remains available for matrix multiplication. We first prove the operation, including its action on unresolved tensor factors, and then give the finite constructions used later for the boundary estimates.

3.1 Pairing conventions and the input rank

We use the tensor and matrix-dimension conventions of Section 2. A pairing on X,Y of length m, with a scalar third side, is \langle1,m,1\rangle; the other orientations are \langle m,1,1\rangle on X,Z and \langle1,1,m\rangle on Y,Z. Their tensor products satisfy

The logarithmic volumes of such factors therefore add.

The input is the six-term specialization of the Coppersmith–Winograd tensor [10, Section 7, equation (10)],

Write \mathcal S=\{200,020,002,011,101,110\} for its support, abbreviating (i,j,k) by ijk. At every position the three indices sum to two. The maps in our square construction for this input have algebraic coefficients. The general preservation identities below also allow arbitrary complex coefficients in the unresolved tensors.

We use the following established theorem in exactly its border-rank form; see also the explicit statement in Ambainis et al. [3, Theorem 3.1].

The auxiliary rank R in (3.3) is part of the input cost. Thus, for a proposed exponent \beta, a finite realization with

proves \omega<\beta. We never cancel an auxiliary tensor as a tensor identity; only its explicitly charged logarithmic rank will be offset by output multiplicity.

3.2 Supplying a label to its missing party

Suppose a tensor is partitioned into pieces whose X-variables are disjoint and whose Y-variables are disjoint. Each of these two parties can then determine the same piece label from its own variable. The Z-variables may still be shared. The next lemma resolves this last sharing without resolving the terms inside a piece. We call this operation GROUP.

The construction uses equal-norm shells, following the geometry of Behrend [4], together with affine slices that constrain two independently chosen auxiliary indices. Its auxiliary tensor is the multiplication tensor of a finite abelian group, linking the construction to the group-theoretic tensor approach of Cohn and Umans [7]. The identity and its full rank charge are proved below.

For repeated uses at different label counts, fix one such group G_K for each K, and write A_K=\mathcal A_{G_K}. This is the auxiliary-tensor notation used in the conditional-label entropy bound.

The geometry rules out a stronger collision than the usual three-term-progression condition: the two slice points u,u' are chosen independently. Their difference is perpendicular to t_s; any nonzero such displacement from t_s lies outside its sphere. Requiring the endpoint to be another tag therefore forces that difference to vanish. Figure 1 shows this displacement argument.

This preservation statement is a locality statement, not a nonvanishing statement. If an earlier support restriction makes a designated source word absent, its fiber is zero and cannot be counted as an output. Our finite constructions below explicitly retain every counted word. The later count construction will require a separate guarantee for every complete controlled path.

3.3 Exact types and a finite hierarchy of labels

For a probability vector p on a finite alphabet, write H(p)=-\sum_i p_i\log p_i, with 0\log0=0. Exact types provide the finite counting form of entropy used here; see Csiszár [13] for the method of types. For rational p and admissible integers N, the number of words having exactly Np_i occurrences of symbol i is

The implicit constant depends only on the fixed alphabet. We use exact types so that the number of positions assigned to every later conditional operation is independent of the previously selected direct output.

The following lemma makes precise how multiple separation steps share auxiliary tensors and count each label once. Its accounting is the conditional-entropy chain rule [25], applied to labels that the tensor maps can actually read.

Nothing in this lemma permits arbitrary support deletion. The locally obtainable support and the two-sided readability must be established for each hierarchy. Once they are established, exact conditional types select its desired joint frequencies through accessible labels.

3.4 An explicit four-component construction

First remove the term 101 from T. Scale each of x_1,z_1,y_0,y_2 by t. The five other terms have degree one in t, whereas 101 has degree three. Dividing by t and taking the limit gives

A local predicate on each side identifies exactly one group: Z>0 identifies A, X>0 identifies B, and Y=2 identifies C. Exactly one of these predicates holds on every retained term. We call any such three-group partition a W-partition; the three predicates, rather than the original numerical indices, are its one-hot flags.

Delete C by setting y_2=0, and take (A+B)^{\otimes N}, with 4\mid N. Retain coarse words with N/2 copies of A and N/2 copies of B. This is local on X, since a zero X index means A and a positive one means B. The Z side also identifies the word, with the roles reversed. There are \binom{N}{N/2} coarse words. Lemma 3.3 separates them by supplying their label to Y, and gives each word a pairing on X,Z of logarithmic length N\log2+o(N).

Inside a fixed coarse word, A’s two terms 002,011 are each identified by Y and by Z. Retain N/4 occurrences of each among the N/2 A positions and separate their words. This adds a pairing on Y,Z of logarithmic length (N/2)\log2+o(N). Similarly, B’s two terms 200,110 are each identified by X,Y; resolving their equal-frequency words adds a pairing on X,Y of the same logarithmic length. These restrictions are conditional on the already-direct coarse word and therefore are local.

The three pairings combine by (3.1). The total logarithmic output count, auxiliary rank, and volume are each N\log4+o(N). Theorem 3.2 consequently gives

The scalar original terms alone would not supply any volume to which \omega could be applied. Here the three pairing orientations supply that volume, while all three auxiliary rank costs have been included.

3.5 Completion and the 75-component bound

A W-partition has a useful local description even when its three groups contain unresolved tensors: side i knows precisely the positions at which its own group occurs. This permits a degeneration of a block of several occurrences before any group has been made direct. We call the following operation COMPLETE.

For the groups A,B,C in (3.9), assign labels 0,1,2 in that order. The group sizes are 2,2,1. A completed block has three group sizes

Delete its all-A group: its active Z predicate is that every original index is positive. The remaining groups will be denoted P_B and P_C. The X side recognizes P_B by the occurrence of a positive index, and the Y side recognizes P_C by the occurrence of index two. Since only these two groups remain, either side independently determines which group occurs.

The neighboring block lengths illustrate that this particular completion is not monotone in b:

No optimization claim over all restrictions of the corresponding power is needed. The length-three construction already gives the stated bound.

3.6 Parity and conditional W constructions

Completion gives one way of making a new W-partition. A different local restriction on three occurrences supplies two useful W labels, which can be resolved in either order. We call this operation PARITY.

If the three occurrences have internal scalar counts (a_i)_i,(b_i)_i,(c_i)_i, the fiber with majority i and odd-count label j has size

Each term for i\ne j describes one singleton placement. For the boundary weights (2,2,1) on all three occurrences, this is

For example, delete the third majority row and resolve the remaining binary majority label. Within the first direct row delete its first odd-count column; within the second direct row delete its second column. These are permitted conditional local deletions because the majority is already direct. Each row then has size 36, giving 72 original scalar components. Lemma 3.5 yields \omega\leq9\log3/\log72=2.311966920\ldots. This illustrative restriction is weaker than Theorem 3.7. Parity is useful because its two conditional groupings enlarge the finite construction family at nonuniform distributions.

3.7 Finite recipes and weighted laws

We now track the source law and score of a finite tree of W constructions. Fix labels 0,1,2 on each original W-partitioned occurrence before applying the tree. These are its canonical labels: later physical permutations may change which side reads a flag, but the original labels are still counted in this fixed ordering.

For the score calculations below, fix a finite operation tree and its rational conditional laws. Admissible exact-type populations, together with the efficient GROUP tensors of (3.6), give a family of finite realizations. The limiting score of this fixed tree and law data is the limit along increasing populations; each member remains one finite recipe with fixed tensor supplies and maps. A later operation may depend on a label only once that label is direct on all three sides. At every stage, previously produced pairings are separate tensor factors; their internal indices are never used to choose subsequent controls.

For a realization on n original occurrences, let L be its direct multiplicity, R its auxiliary rank bound, and v its additional matrix multiplication volume. The rates are

Here M excludes any tensor initially present inside a coarse group. For the W recipes the convenient formal score is u_\gamma=\gamma(D-A)+M, where \gamma\geq1. For 0<\beta\leq3,

Thus u_\gamma rescales the normalized score expression in (3.4) so that the coefficient of the added volume is one. Its definition assumes no bound on \omega. Definitions 4.1 and 4.2 will specify the banked realizations and the closure of their law–score pairs. For a fixed tree consisting only of pairwise separation, completion, parity, and conditional exact types, its total D-A tends to zero when the group/type supplies grow. Consequently its limiting score is independent of \gamma.

A binary leaf deletes one W label locally and resolves the remaining binary word by Lemma 3.3. At law q on that pair, its limiting score is H(q). If positive numbers d_i are assigned as weights for choosing a law, the weighted score is H(q)+\sum_iq_i\log d_i. Maximizing on the retained pair i,j gives \log(d_i+d_j). These weights may guide selection of a finite rational law; they do not change the coefficients of a tensor.

For completion of b occurrences with weights d_{r,i}, the three fiber weights are

When the weights are scalar term counts, this is literal counting of the supports in Lemma 3.6. For arbitrary positive weights it is the corresponding generating polynomial. For parity the analogous matrix is (3.13).

3.8 Physical orientations and canonical laws

A physical permutation acts on the full tensor factors of an occurrence or completed block. Each original occurrence keeps both its canonical label and its net physical side permutation. For \sigma\in\mathfrak S_3, the orientation bank \sigma is the collection of original occurrences with that net permutation relative to their canonical coordinates. We will arrange that all six banks have the same exact canonical label histogram. Their common normalized histogram is the source law; it is not the aggregate law of the physical flags after the bank orientations are forgotten.

The exact types used below fix canonical histograms within each relative orientation. The next lemma shows how the six global physical permutations then distribute these counts equally among the original banks, while keeping one common auxiliary supply.

In particular, rotating the flags of an intermediate completed block changes its grouping and its readers, but does not recode the labels of the original occurrences inside it. To recover a canonical label from a physically permuted occurrence, undo that occurrence’s permutation.

3.9 Resolving and composing nested recipes

An operation in the finite library may complete two occurrences, physically transpose that completed block, and then complete it with a third occurrence. Resolving its original word calls for a hierarchy inside the final fiber. The following statement supplies that hierarchy for any fixed finite composition of completion gates.

To spell out the three-position case used in the library, let c(i,j) be the two-child completion label: it is zero for (i,j)=(0,0), and is a\in\{1,2\} if both entries belong to \{0,a\} and at least one equals a. It is undefined on (1,2),(2,1). Write

The subtraction by k represents the physical rotation of the whole first completed block. In a fixed final fiber s, first resolve the top-level operand labels (z,r). This fixes a=z+k\pmod3, after which the inner word (i,j) can be resolved using the pair of sides belonging to that inner completion, with its physical rotation included. If C_s is an arbitrary rational law on the retained triples, the two levels supply

Here Z is a deterministic function of I,J, so no intermediate label adds a second entropy count. The intermediate rotation changes the grouping flag and its physical reader; it does not recode I,J,R when the original canonical word histogram is calculated.

The words in (3.16) are counted in their original canonical coordinates. The resulting q is the exact common law of the original orientation banks, providing the finite input to the banked-value construction of the next section.

4 Banked constructions and attainable values

A local separation identity must remain valid when the positions on which it acts are correlated with positions to be processed later. It is also necessary to distinguish a distribution in the coordinates of a tensor from the aggregate distribution after physically permuting its sides. We make both requirements explicit. This gives the finite objects whose attainable values will enter the differential comparison.

4.1 Canonical banks and preservation of unresolved tensors

Let \mathcal S=\{200,020,002,011,101,110\} and \mathcal W=\{100,010,001\}. The latter is the support of the ordinary three-state tensor

An element of either alphabet is a triple of local grades. We use \mathcal B to denote either alphabet in definitions that apply to both. Write \mathfrak S_3 for the group of permutations of the three tensor sides. A banked input of size N has N occurrences in each orientation \sigma\in\mathfrak S_3, for a total of n=6N occurrences. Its original component words are

The triple w_{\sigma,t} is expressed in canonical coordinates: its physical grade triple is \sigma w_{\sigma,t}. Thus physical side j observes the canonical coordinate \sigma^{-1}(j). Both T and the ordinary \mathsf W tensor are symmetric under these physical permutations, so this banking does not change the underlying input tensor. Its purpose is to record types and permitted transposes accurately.

A banked word has exact law \alpha\in\Delta(\mathcal B) if, separately for each \sigma, every symbol s occurs N\alpha_s times. In particular, \alpha is not the histogram obtained by forgetting the bank orientations. All normalizations below divide by 6N.

We allow additional, unresolved local indices. To state the preservation requirement precisely, for every original component word w attach an arbitrary three-tensor P_w on these additional indices. The tensors P_w may share their variable spaces, may correlate all the positions, and may be zero. Denote the resulting input by \mathcal T(P): its restriction to the original word w is the original scalar component at w tensored with P_w. This description includes preceding local count restrictions by setting the corresponding fibers to zero. It does not assert that all such families arise as independent products.

The maps in this paper retain each original local index and act on auxiliary coordinates conditionally on that index and on already direct labels. Consequently they commute with local projections depending only on the original indices. The same statement holds when the maps are expressed as leading monomial degenerations. This observation concerns locality; it does not prove nonvanishing after an earlier projection. Nonvanishing will be checked by support identities for the algebraic primitives and by the universal path condition in Lemma 5.3 for arithmetic-progression (AP) count constructions.

Lemma 3.3 supplies (4.1) term by term. Indeed its sphere and slice argument decides the retained auxiliary terms without referring to any coefficient of P_w. Local singleton projections and direct matchings have the same preservation property. The conditional composition rules of Section 4.2 use only these identities; they never presume independence of unresolved fibers.

For the banking operation of Lemma 3.9, group the original input occurrences of a finite schedule by their relative physical orientation \tau. The lemma requires their total canonical histogram H_\tau to be fixed independently of the direct history and shared by all six globally permuted replicas. Exact types of complete original words supply these grouped histograms in the completion and parity recipes. When an already strong child is physically permuted as a whole, each of its original input banks supplies a fixed histogram by Definition 4.1. The letter at an individual position may still vary between direct outputs.

In outer replica \sigma, the group of relative orientation \tau has absolute orientation \sigma\tau. Each absolute bank therefore receives one copy of H_\tau for every \tau, and has histogram \sum_\tau H_\tau. Equal conditional pool sizes alone would not imply this histogram identity. The pool sizes instead fix how many child calls and auxiliary supplies are used; the grouped types or strong child banks supply the required letter counts. A physical permutation of an intermediate macro acts on every original occurrence inside it.

4.2 Finite recipes and the closure of their values

A structural recipe is a finite expression describing local projections and leading degenerations, direct-label-controlled maps, locally imposed exact joint and conditional types, auxiliary GROUP calls, and tensor products on specified collections of positions. Its bank sizes, rational types, and integer group parameters are finite. A conditional choice is permitted only after its controlling label is direct on all three sides. Each byproduct matrix multiplication factor is kept as a separate factor: later decisions use original-word labels and do not read, identify, or spend its indices.

We use the following two classes of such recipes.

1. (a)

   The \mathsf W class starts with singleton projections, binary deletion followed by GROUP, and the finite COMPLETE and PARITY compositions of Proposition 3.11. It allows rational time-sharing on separate positions, physical permutation banking, and finite AP count compositions of previously constructed recipes.

2. (b)

   The six-state class starts with singleton projections, the direct matching construction of Proposition 4.9, and the five-state face substitutions of Proposition 4.10 using finite \mathsf W recipes. It has the same time-sharing, banking, and finite AP closure.

Both classes also allow two explicit finite rearrangements. First, one may reindex the orientation banks by \sigma\mapsto\sigma\tau for a fixed \tau\in\mathfrak S_3, with the corresponding canonical letter relabeling; Lemma 4.4 proves its precise effect. Second, one may conditionally recompile an earlier finite recipe: expand its finite direct-label refinement tree, take finitely many replicas, impose a rational exact type of complete terminal transcripts through its induced conditional types, and replace corresponding GROUP calls by GROUP on the longer conditional pools. All other original support predicates are retained on their old macroblocks. This is a finite construction rule using the same local primitives, not an operation on scores. Its instances must preserve Definition 4.1 and nonzero support like every other recipe; Lemma 4.6 proves those requirements for the uniform terminal type used below. Neither rearrangement authorizes an infinite composition.

Here an AP composition is the finite count-window construction of Lemma 5.3. Its children are finite recipes, not calls to an attainable-value function. The full expression can therefore be expanded to a finite tree. Equivalently, take the union of all finite levels of this construction rule. The \mathsf W class is defined independently of the six-state class.

A recipe belongs to these classes only when its local identities establish Definition 4.1, its counted original words survive all of its restrictions, and its auxiliary profile and output dimensions are fixed across its direct histories. These are algebraic conditions, not inequalities for numerical scores. The primitive support proofs, exact conditional-type composition, and Lemma 5.3 establish these conditions for the listed generators. In particular, introducing the AP closure here does not assume the differential inequality that it will later prove.

The auxiliary tensor in every recipe is a product of finite group tensors. We charge the product of their ranks, which is also their tensor product’s rank by Fourier diagonalization and flattening. It is harmless to charge a larger certified bound. No tensor already present in an unresolved fiber is included in the byproduct volume.

For a realization with n=6N original occurrences, L=|\Lambda| counted nonzero direct summands, auxiliary rank bound R, and common additional volume v=abc, put

For 0<\beta\le3 and \gamma\ge1, respectively, the two scores are

These are formal tensor rates. Their definitions impose no assumption on \omega. In particular, on the same realization u_{3/\beta}=(3/\beta)f_\beta.

Allowing smaller scores makes these sets downward closed. The closure allows irrational laws and limits of finite recipes of increasing size; it does not introduce an infinite composition acting on a finite tensor. In particular, if F_\beta(\alpha)>c, then some actual finite realization has score greater than c, possibly at a law arbitrarily close to \alpha.

4.3 Conditional pooling and monotonicity in the formal parameter

A finite GROUP call pays a small excess of auxiliary rank over its number of labels. Tensor-repeating that particular finite map does not remove its normalized excess. The following lemma replaces each GROUP call by a new one acting on a long conditional pool. It is the requisite justification for monotonicity in \gamma. The face substitution below evaluates the W value at \gamma=3/\beta; monotonicity will let the certificate use a lower estimate obtained at a smaller formal parameter.

4.4 A direct matching lower bound

The first boundary estimate separates original scalar components without an auxiliary tensor. The matching argument uses progression-free hashing and collision removal as in Coppersmith and Winograd [10, Section 6]; we give the details with the bank normalization needed here.

4.5 The five-component face

On one face the six-state tensor has a genuine three-state \mathsf W partition. The remaining distinctions within its coarse groups must be separated only after that partition has been resolved. This gives the second boundary estimate used in the certificate.

5 Arithmetic-progression restrictions and differential comparison

An attainable value contains information about nearby source laws, not merely about a single tensor restriction. This section makes that information quantitative. If a supporting plane loses too little value when the mean grade changes, one can steer long grade sequences into many disjoint count windows at a total cost smaller than the entropy of the windows. Their labels then give an improved tensor construction, contradicting the supporting plane. The steering argument must control every path permitted by its controls: an estimate that only holds with high probability would not justify counting all the output tensors. We first construct the shared count labels and prove their finite tensor gain. We then build controls whose cost is strictly smaller than that gain.

All source laws in this section are the canonical laws in each of the six physical orientation banks of Definition 4.1. In particular, they are not the aggregate physical law obtained by forgetting the banks.

Let

We use orthonormal coordinates on this plane when forming covariances, gradients, and Hessians. For the six-state alphabet, the grade of a source letter is its vector in S=\{2e_i,\boldsymbol 1-e_i:0\leq i\leq2\}. For a law \alpha, write

The covariance is positive definite when every letter has positive probability. Indeed, the three grades 2e_i alone affinely span the mean plane. For a twice continuously differentiable chart \alpha(\mu) whose grade mean is \mu, set

This is the full covariance contraction; the corresponding probabilistic generator has an additional factor 1/2.

Smooth touching tests are a standard formulation in viscosity-solution theory [12]; see in particular [11, Section 2]. The differential inequality below is derived directly from finite tensor constructions.

Here “touches from below” means equality at the indicated point and the inequality \varphi\leq F_\beta\circ\alpha in a neighborhood. No derivatives of F_\beta are assumed. A supporting supergradient is a vector such that

Such vectors exist at positive laws by Proposition 4.3.

Write h=F_\beta, \mu_0=\mu_*, \alpha_0=\alpha(\mu_0), and

For a finite construction with law q and utility u, its supporting-plane cost is \ell(q)-u. It is nonnegative because u\leq h(q)\leq\ell(q). This cost measures lost utility; it is not an additional auxiliary rank charge.

5.1 Locally readable target windows

We require many target indices with no nonconstant three-term arithmetic progression. We use the integer form of the progression-free set construction of Behrend [4], proved in Lemma 4.8. Using such labels to separate tensor products follows the progression-free extraction method of Coppersmith–Winograd [10, Sections 4–7]; the count-window restriction needed here is given explicitly below.

For a length-n word with grades g_1,\ldots,g_n, its centered grade sum is \sum_{t=1}^n(g_t-\mu_0). Use the targets

and coordinate windows with radius \rho=\sqrt n/(10L). Each side reads its own centered sum. Because the three centered sums add to zero, a retained triple whose three local window labels are j_0,j_1,j_2 satisfies

The left side is an integer, and hence is zero. The progression-free property gives j_0=j_1=j_2. Windows are disjoint on every side, including the side whose target spacing is twice as large. Thus a nonzero retained tensor has a shared direct target label.

In a physical orientation bank \sigma\in\mathfrak S_3, the mean \mu_0, the target vector, and the local windows are all permuted by \sigma. The coordinate-sum test is expressed in canonical coordinates. A physical side reads the corresponding permuted coordinate. The coordinate-sum argument is unchanged, so the target remains shared. There is no averaging of the canonical grade covariance across orientations in this operation.

5.2 Exact finite compilation

At each target and prefix, a control specifies a probability law on the source alphabet and a cost. A permitted path chooses at every step a letter in the prescribed law’s support. In the next lemma, every node law and utility must be supplied by an earlier finite strong realization. The lemma turns these realizations into tensor maps when every permitted path ends inside its assigned target windows. It is useful to state it for either alphabet, and with a general coefficient \lambda>0 on the direct-label logarithm. For the six-state score D-A+(\beta/3)M this coefficient is \lambda=1; for the W score \gamma(D-A)+M it is \lambda=\gamma.

The exact populations and multinomial entropy estimates use the method of types [13, Section II]. The proof also establishes the local tensor maps, their uniform auxiliary supply, and nonvanishing of every counted output.

For any affine functional \ell, define the node cost by c_v=\ell(q_v)-u_v. The prefix weights sum to one at each time, so the averaged law in the lemma satisfies

Thus (5.3) has the equivalent form

The expectation denotes the finite sum \sum_v w_vc_v. For the six-state supporting plane fixed above, \lambda=1 and every node cost is nonnegative. To contradict that plane, it is therefore enough to send every permitted path into its window while keeping the expected cost strictly below H(a). The remaining argument constructs such controls from a failed lower test.

5.3 A lower test supplies inexpensive small drifts

At a lower contact, \ell\circ\alpha-\varphi has a local minimum zero. Thus its first derivative vanishes and

If (5.1) fails, \Tr(Q_0C(\alpha_0))<1. Choose \varepsilon>0 so small that

Taylor’s theorem and \varphi\leq h\circ\alpha give, after reducing the neighborhood if necessary,

By the definition of the closed attainable set, the law and utility in this display can be approximated simultaneously, to any prescribed positive accuracy, by a finite earlier construction. We postpone these finitely many approximations until the entire control tree has been fixed.

Transform centered grades by Q^{1/2}. A grade g then gives the increment X=Q^{1/2}(g-\mu_0). A small prescribed mean m is obtained by taking the law \alpha(\mu_0+Q^{-1/2}m). We call these chart laws soft controls; their ideal cost satisfies

There is a fixed bound B>0 on the magnitude of every increment, and

The limit concerns the second moment, which equals the covariance trace at mean zero.

We also allow exact singleton controls. The point \mu_0 is in the relative interior of the grade convex hull, so there is a \kappa>0 such that for every unit vector u\in\mathcal P, one singleton increment satisfies u\cdot X\leq-\kappa. Its utility is zero. The costs of the finitely many singleton choices have a finite common upper bound C_*.

5.4 A control that retains every path

We now construct controls for the bounded increments just described whose cost is smaller than the target-label gain in (5.5). The terminal guarantee must hold for every permitted path. Soft controls will be made safe for every letter in the entire source alphabet, so later rational approximation cannot create an unsafe new outcome.

5.5 The contradiction and the order of limits

Write U_\gamma=U^W_\gamma for the three-state attainable value.

The following interior-maximum argument is the strict-comparison strategy of viscosity-solution theory [11, Section 5.C]. Its short proof uses the lower-test inequalities just established.

5.6 Controlling the supporting-plane term

The lower-test inequality retains g\cdot\mathcal L\alpha when the chart is not exactly harmonic. Although the supporting supergradient is unknown, concavity and a uniform value bound control this term. The certificate will apply the following estimate where every chart coordinate has a positive lower bound.

6 The three-state boundary seed

Proposition 4.10 bounds the six-state value on a five-component face by a three-state value and an explicit conditional entropy. We now construct the three-state lower bound needed for that estimate. Binary separation gives an entropy baseline throughout the simplex. A finite family of completion and parity constructions improves this baseline on a closed curve in its interior. The lower-test inequality then carries that improvement inside the curve.

Throughout this section put

where \en(0)=0. As in the definition of the W value, its score is \gamma _0(D-A)+M, and M excludes the volume of any payload already inside a coarse component. All decimals specifying coefficients or thresholds below denote exact rational numbers.

6.1 The affine chart and the baseline

For q=(q_0,q_1,q_2) in the probability simplex, set

The three deterministic laws correspond to 1,\zeta^2,\zeta. If Z takes these values with probabilities q_0,q_1,q_2, respectively, then \E Z=z, \E Z^2=\bar z, and \E|Z|^2=1. Thus the full covariance contraction, with \partial_z=(\partial_x-\mathrm i\partial_y)/2, is

There is no factor 1/2 in this formula. Equivalently, in affine simplex coordinates it is (\diag(q)-qq^{\mathsf T}):D^2.

Define

Since \en''(t)=-1/t, the diagonal covariance entries give

Consequently \mathcal L_WF_0=-\gamma _0. On each edge the two entropy sums coincide with the binary entropy. Lemma 3.3 achieves that entropy by binary separation, with D-A tending to zero. Both coefficients in (6.3) are positive. Hence, for 0<\delta<1, (1-\delta)F_0\le U on the boundary and \mathcal L_W((1-\delta)F_0)>-\gamma _0 in the interior. The comparison consequence of Corollary 5.5 and continuity of the values prove, upon letting \delta decrease to zero, that

6.2 A polynomial improvement and its domain

Let

Here and below inequalities on this compact set include its boundary; comparison is applied to its open interior. The proposed improvement is a real polynomial H_W. Its exact specification is short despite its degree. Put

Set a_{3k,0}=s_k/(.32)^{3k} for 0\le k\le6. All other pure coefficients a_{j,0},a_{0,j} are zero, except the already assigned a_{0,0}. For d=0,\ldots,110, and i+j=d, define

A negative index denotes a zero coefficient. Every coefficient on the right has degree at most d+1, so this is a finite rational recursion. Finally set

Here are explicit bounds on this polynomial; their verification uses only rational arithmetic. Put R_W=.357, and, for k=0,1,2, put

where the empty product is one. The recursion gives

For clarity, a finite procedure for checking the residual is as follows. For each a_{ij}, add its four contributions

and omit negative exponents. Call the resulting coefficients b_{ij}. Equation (6.6) makes b_{ij}=0 for i+j\le110, exactly. The remaining rational sum satisfies

This proves |\mathcal L_WH_W|<7\cdot10^{-13} on |z|\le R_W.

The geometry of the shell has similarly direct bounds. Write

The lower triangle inequality gives \rho\ge.20947544>.2, whereas \rho\le r_*<.357. Formula (6.1) therefore implies q_i>.095 throughout \Omega_W. For z(\theta)=\rho(\theta)e^{\mathrm i\theta},

Differentiating each monomial in (6.7) gives |(H_W\circ z)''|\le S_2|z'|^2+S_1|z''|<30.348. One can also verify the needed baseline bound without cancellation. For a single summand f(t)=(\gamma _0-1)\en(t)+(2-\gamma _0)\en(1-t), on .095<t<.572 we have |f'(t)|<2.5 and |f''(t)|<5.1. These follow, for example, from 1.32<\gamma _0<1.33, -\log(.095)<2.4, and -\log(.428)<.9. Using |q_i'|\le2|z'|/3 and |q_i''|\le2|z''|/3 gives

The slightly larger bound 68 will be used in interpolation.

6.3 What is certified by the finite library

We next describe the mathematical objects in the library. A record fixes a finite tree of completion, parity, binary-separation, and side-permutation operations, with rational conditional distributions on its branches. Proposition 3.11 compiles this hierarchy into a family of finite realizations using growing exact-type populations and efficient GROUP parameters, preserving arbitrary payloads and the canonical bank convention. The utility of a record is the limiting attainable score of this family. Every positive accuracy is achieved with finite supplies, so the record gives a lower bound on the closed value U. The arithmetic below evaluates these laws and limiting utilities; the final strict excess over \log3 will later select an actual finite realization.

Here is an explicit description of its word groups, which is also useful for checking the library independently. Number the W labels 0,1,2 and define the partial completion map

the pairs (1,2) and (2,1) are discarded. A two-position completion has outer label c(i,j). A three-position completion has outer label c(c(i,j)-k\pmod3,r), where k\in\{0,1,2\}; an undefined intermediate label discards the word. Its inner label is deterministic. Independent permutations of the three labels are allowed in the two or three positions. These are precisely finite compositions of the completion restriction. For parity on three positions discard the six words with all labels different. A retained word has a majority label and an odd-count label; on a constant word both equal its sole label. Either label can be the outer label and the other the inner label. A nonconstant outer/inner group has three words and a constant group has one. This is the parity restriction proved earlier, followed by two W separations.

Suppose the block length is L\in\{2,3\}. Let t_i be the outer law, v_{ij} the inner law conditional on i, and C_{ij} the law of the retained words in that group. Let n(w) count the original canonical source labels, obtained by undoing each positional reindexing. The intermediate cyclic rotation changes only the completed-block flag and fiber membership, not these source labels. If the child constructions have limiting utilities u_t,u_{v_i}, the original law and limiting utility are given exactly by

For completion the inner utility is zero. The last term is supplied by Proposition 3.11: once the outer label is direct, resolve the gate refinements in the order of Lemma 3.10, using each gate’s own pair of knowing sides. The flattened final word need not be readable by one fixed pair. Exact conditional types fix the populations and canonical histograms of every pool, including under the positional permutations, and the entropy chain rule counts the remaining word law once. For parity, after its two labels are direct, the remaining choice is the primitive three-word group of Lemma 3.8. These are precisely the hypotheses behind the last term of (6.13). Each auxiliary separation has D-A\to0; hence the limiting utilities of these pure completion/parity records satisfy u=M\le H(q)\le\log3.

The following finite menu protocol specifies the candidates used in the arithmetic check. Its deterministic integer implementation is menu.hpp in the accompanying certificate sources.

1. 1.

   For weights d=(i/64,j/64,1) with 0\le i\le j\le64, the terminal operation deletes a least-weight label and separates the remaining two, with probabilities proportional to their weights, rounded as specified below. The zero pair uses the deterministic record.

2. 2.

   The initial record repeats two-position completion twelve times, placing a maximum-weight label first at each step, and ends with this terminal operation. Positive integer weights are renormalized at each recursive call, with a lower bound of one integer unit.

3. 3.

   Fourteen improvement layers may retain an earlier record or assemble earlier records using two-position completion, three-position completion, or either order of the parity labels above. All positional permutations and the three intermediate cyclic offsets are available. A child call also permits terminal binary separation. Candidate comparison uses u+\sum_iq_i\log d_i; lookup examines the nearby indices within two of the nearest 64d_i/\max d after sorting the weights, and all compatible side permutations. The outer weights in parity may themselves be chosen from the rounded exponentials of such child scores.

4. 4.

   Each conditional word receives a positive integer weight equal to the rounded product of its positional weights, clamped below by one. The cumulative normalization in (6.14) fixes its exact conditional law. Append all six side permutations of the selected final records and the three deterministic records.

The preliminary scores that select operation types, the integer roots or exponentials used as search weights, and ties in selection have no mathematical accuracy requirement: they only choose among the explicitly admissible finite trees just described. In particular, a computed score is never used as the utility of a record. Utilities and laws are evaluated anew by (6.12)–(6.13). The supplied finite program fixes all these selection choices, including ties; the certificate verifies feasible mixtures of its resulting records. Neither global optimization of the records nor optimality of a mixture is needed for the lower bound.

6.4 Arithmetic errors and exact distributions

Let B=2^{52}. For positive integer word weights w_1,\ldots,w_m set

These probabilities are nonnegative and telescope to one. Zero-probability words are omitted. This formula, not an unrounded idealized weight law, defines every conditional distribution used by a record.

The evaluator represents a real number by an integer divided by B. Multiplication and division truncate toward zero, and an input constant x is stored as \lfloor Bx+1/2\rfloor. Logs are evaluated by reducing the argument to x\in[1,2] with powers of two and using

Since |t|\le1/3, summing the geometric propagation of rounding errors in Horner evaluation gives an error below 7/B on [1,2]. For a probability represented at scale B, reduction uses at most 52 doublings. Keeping the factor p_j in -p_j\log p_j, rather than bounding all reduced-log errors by their worst case separately, gives entropy error less than 400/B for any conditional word distribution here (which has at most 27 words). For example, \sum_jp_j|h_j|\le1+H(p)/\log2\le1+\log_2 27, where h_j is the reduction exponent; the log errors and the at most 27 final product roundings are already less than 100/B. The allowance 400/B includes the other normalization and evaluation roundings.

Let e_r^{\rm init} be the \ell^1 error between the exact law of a record and its stored law after r initial completion steps, and let f_r^{\rm init} be its utility error. The terminal binary law is exact at scale B, with utility error at most 400/B. In a completion, averaging normalized count vectors contracts the child-law error. There are three groups; rounding the count averages and restoring the missing mass to the first coordinate contributes less than 15/B. The outer child utility is divided by two. Perturbing its weights in the conditional entropy term contributes at most 2e_r^{\rm init}, and the local entropy and arithmetic errors contribute less than 250/B. Thus

At r=12 these give e_0\le180/B and f_0\le1700/B for the improvement layers. (The displayed initial recurrence actually gives f_{12}^{\rm init}\le1159.991/B.)

For an improvement layer let e_h,f_h be uniform errors over its records. A parity assembly combines at most an outer law and an inner law, so their errors total at most 2e_{h-1}. There are at most nine groups. The sum of product and count roundings leaves fewer than 21 missing probability units before restoration; adding that mass to one coordinate costs less than 42/B in \ell^1. The two child utility contributions are divided by three, giving coefficient 2/3; completion has the smaller coefficient 1/2. Inner utilities are at most \log3, and the conditional word entropy is at most \log27. Applying these bounds to (6.13), with the just obtained law-error allowance, gives the conservative recurrence

To see that the last fixed allowance is sufficient, the entropy errors contribute at most 400/(LB)\le200/B; the at most nine group-weight products, their utility products, the three inner-utility products, and the final division contribute less than 50/B after normalization. For parity, each conditional group actually has at most three words, so the weight-perturbation estimate in (6.17) has additional slack. Retaining a record from an earlier layer preserves these bounds. At h=14 they give

For mixture evaluation, project the stored first two coordinates and utility down to scale 2^{30}. A feasible triple of projected library points determines nonnegative barycentric weights by exact determinant ratios. Applying those same weights to the true records gives a genuine attainable law \widehat q. The singleton points are in the library, so every projected simplex target admits a feasible triple. The implementation’s pivot search is used only to locate a triple with a sufficient utility; feasibility is verified by its nonnegative determinant ratios.

The difference between two floor remainders in a first or second coordinate is less than 2^{-30}; the third coordinate is their complement. Combining this with (6.18) gives |\widehat q_i-q_i|<2.8\cdot10^{-9}, including the much smaller error in a shell target’s trigonometric evaluation. We may cap the utility claimed for a mixture at K=1.5. Lemma 6.1 then bounds its correction loss on the shell by 1.5(2.8\cdot10^{-9})/.095. Adding the library utility and projection errors proves the following bounds, also recording the grid bound needed later:

The last two bounds can be checked directly as follows. Store the scaled polynomial coefficients a_{ij}R_W^{i+j}, evaluate in polar coordinates with r/R_W<1, and sum the finitely many roundings. There are 6441 monomials, degree at most 112, and (6.8) bounds the effects of coordinate error. For cosine, reduce the angle to [0,\pi] and use its degree-48 Taylor polynomial in Horner form. Its Taylor remainder and propagated fixed-point errors total less than 300/B. Coefficient rounding, at most 112 radial multiplications, and the two products per monomial give an error well below 10^{-9}, including this trigonometric error. Applying (6.15) to the six entropy terms in (6.3) gives the stated 10^{-11} allowance.

6.5 The finite checks and the continuum conclusion

The finite shell check uses

At each angle it forms r=\rho(\theta_l) and the target law by (6.1), evaluates a feasible library mixture as above, and subtracts the stored values of F_0 and H_W. Thus the finite statement to check is a collection of 2161 integer inequalities: if g_l is the resulting gap in units of B^{-1}, then

In particular the recorded minimum is exactly -4180063084/2^{52} in utility units, approximately -0.928160457\cdot10^{-6}. This finite arithmetic result is reproducible from the coefficient and menu specifications above and the supplied integer checker. Its mathematical meaning is a lower bound from feasible constructions, with the proved error allowances; it is not a claim that the numerical candidate is an optimizer. Using the conservative threshold -5\cdot10^{-6} in (6.20), subtracting the preceding evaluation and exact-law correction allowances, and transporting from rounded targets to exact sample targets gives

It remains to fill the intervals between these samples; no sampling assumption is made here. If a twice differentiable scalar function has |f''|\le M on an interval of length h, its difference from its linear interpolant is at most Mh^2/8. Mix the two sample constructions with their linear interpolation weights. Their law is the chord between the two sample laws. By (6.10), each coordinate differs from the desired curved law by at most 2.11h^2/8. Correct this discrepancy using Lemma 6.1; since q_i>.095, the utility loss is at most 1.5(2.11/.095)h^2/8. The interpolation error of F_0+H_W is at most 68h^2/8 by (6.11). With h=\pi/6480 their total is

Both the shell and the polynomial are invariant under rotation by 2\pi/3 and conjugation: the recurrence preserves i-j\equiv0\pmod3 and has real coefficients. The value is invariant under label permutations. These symmetries extend the interval [0,\pi/3] to the entire boundary.

At the target exponent \beta=1129/500, we have 3/\beta>\gamma _0. Proposition 4.7 therefore transfers both the baseline and the seed to U_{3/\beta}. Together with Proposition 4.10, this is the promised attainable lower bound on the five-component face.

7 A rational certificate for the comparison bound

We now construct a smooth family of six-component laws and a polynomial that lies below the attainable value on its boundary. The polynomial has slightly more curvature than the lower-test inequality permits at an interior contact point. This forces it below the attainable value throughout the family. Its value at the center is strictly greater than \log 3.

There are two numerical difficulties. First, the chart is only approximately harmonic, so we must retain the supporting-covector term in Theorem 5.1. Second, a finite list of point evaluations does not prove a differential or boundary inequality on a continuous region. We address the first by moving the boundary slightly into the positive simplex, and the second by coefficient majorants, polynomial interval bounds, and interpolation of actual attainable constructions. All decimal constants in this section that define polynomials or arithmetic thresholds denote exact rational numbers.

The proof occupies this section. The finite checks are specified together with analytic bounds that turn their integer conclusions into uniform inequalities. Section B gives the implementation and reproduction interface. In particular, the computations used below are finite certificate verifications; they do not presume convergence of a numerical optimizer or of an infinite harmonic series.

7.1 The chart and its exact coefficients

Put \zeta=\exp(2\pi i/3) and R=31/25. For a real polynomial P on the complex plane define, with subscripts modulo three,

Their six-coordinate sum is one. In the six-state support, their mean satisfies \mu_i=1-r_i. Thus

is an invertible affine coordinate on the mean plane. Whenever all six coordinates are positive, (7.1) is a chart to which Theorem 5.1 applies.

Here is a finite rational definition of P. For integers N\geq8 and b\geq1, put Q=2^b and \operatorname{rnd}(t)=\lfloor t+1/2\rfloor. Let

We define symmetric integers A_{ij}=A_{ji} for i+j\leq N. The pure coefficients are

Let c_{00}=8, c_{10}=c_{01}=2, c_{20}=c_{02}=-1, and c_{11}=-2, with every other c_{ij} zero; after computing A_{ij} set C_{ij}=72A_{ij}+Qc_{ij}. For 1\leq i\leq j, in increasing total degree, form the following sum. For 0\leq x<i, 0\leq y<j, (x,y)\ne(0,0), put

and set

Then define

The indices a,c are nonnegative, and both a+c and x+y are smaller than i+j. Thus (7.3) is a definition by finite recursion. For both choices used here, 21<C_{00}/Q<22, so its denominator is positive. Finally put

The chart used in the proof is defined by P. The smaller polynomial P^{\rm ref} makes the finite evaluations less expensive; uniform bounds on its difference from P will transfer those evaluations to the chart. The symmetry of the coefficients makes these polynomials real-valued and invariant under conjugation. Rotation permutes the three functions p_i; it need not fix P itself.

7.2 Uniform residual and polynomial comparisons

The reason for the recursion is most transparent at the coefficient level. For the chart P_{N,b} form

Write \mathcal C^{[s]} for the terms whose exponent difference is s modulo three. Then

The coefficient of z^{i-1}\bar z^{j-1} in \mathcal L P_{N,b} is

Indeed, the three second derivatives give exactly the shifts and factors in (7.3). A term outside x<i, y<j has zero derivative factor. Every other coefficient on the right has already been computed. Nearest rounding therefore leaves a defect of absolute value at most C_{00}ij/(2Q^2)<36ij/Q. Reflection handles i>j.

For any polynomial F=\sum f_{ij}z^i\bar z^j, the elementary inequality

provides a uniform, rather than sampled, bound. A convenient majorant for all low-degree rounding defects is

For the remaining products put, for s=0,1,2,

where (v_0,v_1,v_2)=(ac,c(c-1),a(a-1)). A product with covariance degree k and differentiated chart degree m has degree k+m-2. Every coefficient outside the recursion is consequently included in

All terms on the right are nonnegative rational numbers. They can be bounded using integer arithmetic: set U=2^{160}, replace each D_{s,k} and V_{s,m} by its upper integer multiple at scale U, round each summand of \rho upwards at the same scale, and divide the two sums by U^2 and U, respectively. For N=780,b=500 this gives

The exact upper numerator and denominator, as well as the complete coefficients regenerated by (7.3), form part of the finite certificate. Thus the small low-degree defect is attached to the defined polynomial, not assumed for an arbitrary supplied coefficient list.

For two polynomials, with missing coefficients interpreted as zero, define

using (i+j)^0=1 also at the constant term. A unit real directional derivative of a monomial costs at most i+j and a second one at most (i+j)(i+j-1). Hence

Computing the coefficient differences exactly before taking absolute values, and rounding the resulting positive sums upwards, gives the following bounds on the entire closed disk:

Here the subscript denotes truncation by total degree. The same sums with factors k and k(k-1) prove, for either full or reference chart,

Truncating either chart at degree 40 changes its value by less than .0002 and its gradient by less than .006. These derivative estimates will control interpolation and root locations; value closeness alone would not suffice.

7.3 Geometry of the domain

Work first in the sector 0\leq\theta\leq\pi/3, writing z=re^{i\theta}. Define its probability domain by r\leq R and E_1\geq0. We shall prove that the other five coordinates are uniformly positive there. Rotations and conjugation then provide the full domain \Omega.

From (7.9),

Divide the sector into 480 radial and 480 angular cells, with centers

Evaluate the degree-40 reference chart at these centers, including its radial derivative and unit-tangential derivative r^{-1}\partial_\theta. The following are the exact integer center tests, after division by the arithmetic scale:

For completeness, their arithmetic specification uses T=2^{45}, the rational approximation 3141592653589793238/10^{18} to \pi, and sine and cosine series through degree 64 on arguments reduced to [0,2\pi). Every division in these recurrences is rounded down. The Taylor remainder is below 10^{-30}; propagation of rounding errors is bounded by 65e^{2\pi}/T. Including the argument approximation gives error below 2\cdot10^{-9} in either trigonometric value. There are 861 possible chart coefficients through degree 40; their absolute majorant is below .921, and the first-derivative majorant is below .592. Product and summation errors consequently leave a common allowance 10^{-7} for the displayed scalar fields and gradient vectors. These rules specify finite integer evaluations at all 230400 centers, and all tests (7.11) hold.

Let b=\pi/2880. Every point of a cell is within distance

of its center. Adding the truncation tails, arithmetic allowance, and Lipschitz variation gives

If the true E_1 at a point is at most .01, its truncated center value is below .01+.0006+G\delta+10^{-7}<.018. Thus the derivative tests apply. Using the Hessian variation and the degree-40 gradient tail yields

Only the first line needs the term Gb, accounting for rotation of the radial unit vector between the point and the center.

In particular -\partial_rE_1>.144 wherever E_1\leq.01. At the origin, E_1=1/3-P(0)>.1471. Once a ray reaches .01, its value decreases strictly while below that level and cannot cross upwards through it. Consequently each ray has at most one zero. Let r_*(\theta) be this zero if it lies below R, and R otherwise. Implicit differentiation on the smooth face and clipping at R give

where the second inequality is used only on intervals wholly in a smooth face. The clipped radius is Lipschitz; its second derivative is not used across a face–cap junction.

The eigenvalues of the matrix in (7.2) are

The center tests give a smaller eigenvalue at least 2; d\geq.488 ensures the required sign before taking square roots. A cell containing a point with E_1\geq0 has computed center E_1>-.004546, so the test is active. Throughout the sector r_i\in[-.08,.746667], and hence

The change from the truncated center to the full value is less than 2(.0002)+1.571(.001871)+10^{-7}<.00334. If all D_i change by at most t, then \|\Delta C\|_{\rm op}\leq15t: the three coefficients of D_i in a unit-direction quadratic form are 3+6\cos(2a+2\pi i/3); they sum to 9, at most one is negative, and a negative coefficient has magnitude at most 3. Their absolute sum is at most 15. We conclude

All full/reference differences in (7.8) fit within the remaining strict slacks, so these conclusions hold for P_{780,500}.

7.4 The barrier and the interior inequality

Finite Taylor polynomials, explicit remainder bounds, and subdivision into certified boxes are standard techniques of validated numerics; see [21, Section 2 and Algorithm 1] and [26, Section 2]. We specify the integer arithmetic and all error allowances for the present certificate below.

Let

The 52 exact rational coefficients a_{ij} in Table 1 define

For i>j, the real part gives a_{ij}(z^i\bar z^j+z^j\bar z^i)/2; a diagonal term occurs once. This polynomial is invariant under z\mapsto\zeta z and conjugation. Its constant term is 1.098619383270680538.

7.5 The six-component boundary inequality

We apply the three-state seed to a face of the six-component domain, and the matching construction to its circular cap. It is important to keep these two sources of attainable values distinct.

Put U=U_{\gamma_0}, where \gamma_0=300000/225925. Since 3/\beta>\gamma_0, Proposition 4.7 permits us to use this lower parameter in the face estimate of Proposition 4.10. At E_1=0 define

The face lower bound is

At the cap put l_h=E_{h+1}+E_{h+2}. The side-h marginal is (1-l_h-p_h,l_h,p_h), so Proposition 4.9 gives

A finite lower estimate for U. For evaluation in (7.25), use the entropy baseline, the improved shell bound, and finite-library mixtures from Section 6. The library bounds are tabulated on the three-state simplex grid of spacing 1/500. Within a grid square whose four vertices are in the simplex, bilinear interpolation is a convex combination of the four vertex laws and reproduces the target law exactly. Concavity of U therefore makes the interpolant of lower utilities a valid lower bound. Every grid vertex used here has all coordinates greater than .03.

At each grid vertex subtract 2\cdot10^{-6} from the computed library utility. Subtract a further 2\cdot10^{-8} from the maximum of this interpolant and F_0. Inside the shell also consider F_0+H_W-24\cdot10^{-6}, using a radial guard 10^{-8} to ensure that the point really lies in the shell. Take the maximum of the available bounds and cap it at 1.45. The resulting evaluated estimate is nonnegative. The error recurrences, entropy evaluation, and distribution correction proved above allow at most 10^{-7} additional overstatement; we include it in the boundary arithmetic allowance. Neither selection of the maximum nor downward capping requires the library to be optimal.

Locating boundary points. Set

Evaluate the boundary at the K+1 endpoint angles. Use the degree-220 reference chart and arithmetic scale B=2^{52}. The value error relative to P is below 7\cdot10^{-11}, and each E-coordinate error is below 2.5\cdot10^{-10}. The chart coefficient tail was already bounded in Section 7.2. For evaluation, combine conjugate coefficients as real cosines and evaluate radial powers by Horner’s rule. The fundamental cosine is computed by the degree-48 Taylor polynomial on [0,\pi] after symmetry reduction, with error at most 300/B. Higher angular harmonics are formed by the recurrence c_{s+1}=2c_1c_s-c_{s-1}; their error amplification is controlled by the k^2-weighted coefficient sum. The total absolute coefficient sum of the reference chart on the disk is below .414, and its k^2-weighted sum is below 6. These majorants bound the additional coefficient, trigonometric, and Horner errors within the stated allowances.

If the computed E_1(Re^{i\theta}) is nonnegative, take the clipped radius R; otherwise perform 38 bisections on [0,R]. By (7.13), the combined evaluation and bisection error in r_*(\theta) is below 2\cdot10^{-9}: the dominant term is (2.5\cdot10^{-10})/.144, and R2^{-38} is smaller than the remaining slack. The same bound holds when a sign uncertainty changes whether the root is clipped.

Use the band

to classify a complete angular cell from its left endpoint. This is valid because |\partial_\theta E_1(Re^{i\theta})|<GR<2.62. A value below -b_K identifies a full face cell; one above b_K identifies a full cap cell. In the other cells, subdivide into 8192 equal subcells and use the analogous band at that scale. Where the sign remains uncertain, evaluate both bounds.

At an endpoint the face bound is computed whenever the cap value is below 2.1b_K, and the cap bound whenever it is above -2.1b_K. Such a face evaluation may occur at a clipped cap point with E_1\ne0. Its three-state law is normalized by setting

On the face, \widehat Q=Q. At a sampled point off the face, use \widehat Q in the right side of (7.25), with the same internal coordinates and first two coarse coordinates in (7.24). This is an auxiliary comparison expression; the interpolation and displacement estimates below transport it to actual face laws, where Proposition 4.10 supplies attainability.

The band rule ensures that both endpoints required for a full-cell test have been evaluated: for example, a left value below -b_K forces the next value below -b_K+2.62h plus evaluation error, which is below 2.1b_K. This also guarantees the face samples near cap points at which the inset will become active. There are six transition cells in the finite check.

Barrier evaluation and derivative bounds. For (7.16), store the scaled radial coefficients at B_\varphi=2^{44}, rounded to nearest integers. Evaluate powers of r/R and the appropriate cosine or sine for angular differentiation. For a term of radial degree d=i+j and angular frequency s=i-j, an a-th radial and b-th angular derivative has multiplier d(d-1)\cdots(d-a+1)s^b with the appropriate phase shift. Exact coefficient sums give the following value and derivative error bounds:

One may obtain these by summing, for each monomial, its coefficient rounding error, the at most d radial-power division errors, and its trigonometric error, multiplied by the displayed derivative factor. The absolute radial coefficient sums weighted by d^k, k=0,\ldots,4, are respectively below

These conservative rational bounds make the calculation independent of cancellation in the evaluated polynomial.

At every sampled point where a face bound is evaluated, the integer checks in physical polar coordinates give

When evaluated using normalized radius r/R, the threshold contains R^a, converting it to precisely this physical-coordinate statement. Cap samples satisfy |\varphi_\theta|<999 and |\varphi_{\theta\theta}|<4999 before the errors (7.28) are restored.

A useful uniform fourth-derivative bound is

These are five finite rational sums. Their largest value is less than 434439204, so the stated integer bound has spare margin. Taylor’s theorem with (7.30) extends the sampled derivative estimates between boundary samples.

Interpolation on a smooth face. On a full face cell the additional integer secant test is

where hats denote the computed physical radii. The coarse bound |r_*''|<22000 and the root-location errors show |r_*'|<3.05+22000h+4\cdot10^{-9}/h<3.41. Substitute this in (7.14) to get

Write z(\theta)=r_*(\theta)e^{i\theta}. Then

Equations (7.9) and (7.10) now give

Here are details for the last two estimates. In differentiating \en(s), use \en'(s)=-1-\log s and \en''(s)=-1/s. The four internal arguments in J exceed .05, and Q_0,Q_1>.10. The first-derivative bounds for an internal p and E are .592|z'| and 2.11|z'|; their second derivatives are bounded by 3.05|z'|^2+.592|z''| and 9.15|z'|^2+2.11|z''|. The six entropy chain-rule terms are bounded using |\en'(s)|<2 on [.05,1] and |\en'(s)|<1.31 on [.10,1]. Their sum is below 30000. For the barrier, expand its first and second polar derivatives about a sampled endpoint, using (7.29), (7.28), and (7.30). The polar displacement is at most (3.41+1)h+4\cdot10^{-9}. Throughout the cell the first derivatives are below 2.91 and the second derivatives below 80.3. Therefore

For a function with |f''|\leq M, its difference from linear interpolation over an interval of length h is at most Mh^2/8. Concavity of U lets us interpolate the closed attainable law–utility pairs at neighboring endpoints, giving a lower bound at the chord law. The first two Q coordinates differ from the curved target by at most 2900h^2/8. On the actual face the third coordinate is Q_2=p_1; using it directly gives

Since Q_0,Q_1>.10 and Q_2>.05, the curvature divided by a coordinate lower bound is at most 29000. The exact-law correction of Lemma 6.1 costs at most 1.5\cdot29000h^2/8 in U. Adding the conditional-entropy and barrier interpolation costs gives

where .754>1129/1500.

Interpolation on a cap. On an actual cap all entropy arguments in (7.26) exceed .049. The chart derivative bounds and |z'|=|z''|=R give |B_c''|<1600. For example, the gradient bounds for the three marginal arguments are 4.22, .592, and 4.812, and the Hessian bounds are 18.3, 3.05, and 21.35; substituting these in the entropy chain rule already gives the stated bound. The cap sample derivative checks extend to |\varphi_{\theta\theta}|<10000. A direct coefficient bound gives |\varphi_{\theta\theta\theta}|<3875770, so the second derivative can move by less than 62 in one full cell. It follows that the full-cap interpolation loss is less than (1600+10000)h^2/8<.4\cdot10^{-6}.

Transition subcells. No second derivative across the clipped corner is needed. In a subcell the actual boundary point and its sampled clipped point have complex displacement less than

This changes Q_0,Q_1 by less than 1.12\cdot10^{-7} each, and their reconstructed third coordinate by less than 2.24\cdot10^{-7}. The singleton correction costs at most

The conditional-entropy differential for one split is \log((a+b)/a)\,da+\log((a+b)/b)\,db. All internal coordinates remain above .049 on this displacement, so each logarithmic factor is less than 3.1. Summing the four internal-coordinate changes and multiplying by 1129/1500 gives less than .52\cdot10^{-6}. The local barrier first derivatives, extended from (7.29) with (7.30), are below 3; its change is less than .13\cdot10^{-6}. Thus the total face displacement loss is less than 6.5\cdot10^{-6}. This estimate remains valid if the sampled clipped point is just on the cap: reconstructing Q_2 absorbs its small active-coordinate mass into the five-state face law, and the same correction reaches the actual face law.

For a cap transition, evaluate the smooth entropy expression in (7.26) even if the sampled cap point has E_1<0. Attainability is asserted only at the actual cap target, where Proposition 4.9 applies; the displacement estimate compares the two entropy expressions. All their arguments stay above .049, and |B_c'|<26. The cap derivative checks, followed by the local second bound just established, give |\varphi_\theta|<1001. The subcell width is below 2\cdot10^{-9}, so displacement together with the cap endpoint arithmetic allowance costs less than 2.4\cdot10^{-6}.

Arithmetic checks and retained margins. The finite evaluations compare the face and cap lower estimates against \varphi. The smallest recorded integer gaps at scale B=2^{52} are

All 65536 cells, and all 8192 subcells of each of the six transition cells, satisfy the corresponding tests. On full face cells the secant tests used above also hold. The conditional laws and mixture checks used to produce these values are the finite rational constructions of Section 6.

A conservative endpoint arithmetic allowance is 10\cdot10^{-6} for a face evaluation and .2\cdot10^{-6} for a cap evaluation. To see that the former suffices, account separately for the 2\cdot10^{-9} root-location error with the chart gradient bounds, correct the resulting coarse-law error by singleton dilution with coordinates above .03, include the 10^{-7} possible error in the computed lower estimate for U, and add the entropy and barrier errors. Each coordinate moves by less than 6\cdot10^{-9}, with less than 12\cdot10^{-9} for the reconstructed coordinate; this dilution costs less than 6\cdot10^{-7} before the prefactor. The entropy and barrier evaluation estimates above fit well within the remaining allowance. A cap needs no root correction; the chart error in its entropy arguments and the barrier value error give the stated .2\cdot10^{-6} bound. All trigonometric, logarithmic, coefficient, and integer-division errors have been included.

We use the recorded face minimum in (7.34) and charge the full face arithmetic allowance in transition cells separately from displacement. The resulting bounds are

Every entry leaves more than 5.5\cdot10^{-6}.

All arithmetic has an exact-integer interpretation with specified truncating or floor divisions. In the finite-width implementation, probabilities and counts are below 3B, and scores and accumulated utilities below 100B. Projected-law determinants and barycentric numerators have magnitude at most 2^{60}; utility-gap products are below 2^{94}, ratio-test products below 2^{122}, and barrier products below 10^{36}<2^{127}. Narrowing casts are checked. These bounds justify the integer interpretation independently of the additional runtime checks described in Section B. We have proved the following uniform statement.

7.6 The positive inset and the comparison argument

The supporting-covector estimate requires all six probabilities to be bounded away from zero. Set \eta=2\cdot10^{-9} and replace each active face E_i=0 by E_i=\eta, retaining the cap where it is reached first. Let the resulting domain be \Omega_\eta. It contains the origin, has compact closure, and all six coordinates are at least \eta there. We now transfer Lemma 7.4 to its boundary.

On a removed terminal segment of a ray, 0\leq E_1\leq\eta and -\partial_rE_1>.144. Its length is at most

This also handles an original cap endpoint with 0\leq E_1<\eta. The five other coordinates remain greater than .05 and each changes by less than 2.11\Delta r<2.94\cdot10^{-8}. Write \alpha_b and \alpha_\eta for the original and new endpoint laws. With

the active coordinate contributes nothing, and \lambda<2.94\cdot10^{-8}/.05=5.88\cdot10^{-7}. If \lambda>0, the vector

is a probability distribution. Mix a construction at \alpha_b with singleton constructions of average law s. Singleton utility is nonnegative, and the original utility is at most \log6<2. The loss is below 2\lambda<1.18\cdot10^{-6}. When \lambda=0 no correction is required. The closure of rational mixtures gives the same conclusion for limiting endpoint laws.

To bound the change of the barrier, every point of the inset segment has a face-check sample within angular distance h=\pi/(3\cdot65536). The band test covers even cap endpoints where the inset becomes active. The radial Lipschitz bound, root error, and inset displacement give total polar-coordinate distance at most

Taylor’s theorem for \partial_r\varphi, using (7.29), (7.28), and (7.30), gives

Thus the barrier changes by less than 3\Delta r<4.2\cdot10^{-8}. The two transfer losses total less than 1.3\cdot10^{-6}, leaving more than 4.2\cdot10^{-6} slack on the inset boundary. At unchanged cap points there is no loss. Symmetry treats all faces.

8 From the certificate to the exponent bound

We now pass from the strict comparison to the exponent bound. This last step uses the finite construction class defining the attainable value, rather than a limiting tensor.

For the rational exponent in this paper, the sufficient finite inequality has the equivalent integer form

Thus the strict comparison does not depend on taking an asymptotic sum inequality at an infinite tensor or discarding an ancillary charge. The argument establishes an arithmetic exponent. It does not estimate the size of a useful finite implementation or its numerical stability.

9 Conditional labels and entropy

Lemma 3.5 counted the total pairing volume supplied by successive labels. We now keep track of which pair of sides supplies each contribution. The input is a finite tree describing which label each pair can read; the output is a matrix-multiplication bound in terms of the three accumulated conditional entropies. Preserving previously read labels on every side is essential when the next reader pair changes.

For a probability law \pi on the leaves, write \Prb(\nu) for the mass passing through a node \nu. Assign to each pair UV the rate

Zero-mass contributions are zero. The sum of the three rates is \HH(\pi).

This identity is the entropy chain rule [25, Section 6]. The exact conditional counts below use the method of types [13, Section II]; the tensor restrictions and their full auxiliary costs are proved explicitly.

The auxiliary cost in Theorem 9.2 is not suppressed. Its exponential contribution is precisely what the multiplicity (9.2) cancels after Lemma 2.3. This exact accounting is what permits many successive conditional separations.

10 Recursive completion trees

This section constructs the finite trees to which the entropy bound will be applied. Two small tensors supply the starting points; a local degeneration preserves three readable color flags through repeated completions, and a final deletion makes the entire tree readable.

We use colors \colB,\colA,\colC owned by X,Z,Y, respectively. A three-flag tensor is a W-partition, as in Section 3.4, together with a conditional readable tree on the support of each color. Thus exactly one color is assigned to each supported monomial, and its owning side reads whether that color’s flag is on. The additional trees will let us continue separating labels after a completion has identified a color word.

10.1 Two starting tensors

The second starting tensor is the five-term tensor T' from (3.9), obtained from the q=1 Coppersmith–Winograd tensor [10, Section 7]. We retain its color flags and make the conditional trees explicit. The formulas below give short polynomial witnesses for both starting budgets.

The first base has budget R=2 and support

It is the coefficient of order one in

whose constant coefficient is zero. Its conditional trees are trivial.

The second base has budget R=3 and support

The triples give indices on X,Y,Z, with unit coefficients. The flag tests are z>0, x>0, and y=2. Within \colA, the choice is read by Y,Z; within \colB, it is read by X,Y.

To verify the budget, put

The first coefficient of P(t)+P(-t)-2P(0) is twice the sum of the six monomials with index sum two; the family has rank at most three. Now give weight one to x_1,z_1,y_0,y_2 and weight zero to all other variables. The term 101 has total weight three and the other five terms have weight one. The leading part is exactly (10.1).

10.2 Completion and termination

To terminate, delete one color using its owning flag. The choice between the two surviving colors is read by both their owning sides. Follow it with their conditional trees. This is a readable tree to which Theorem 9.2 applies.

A script consists of a base, a finite list of completions, and a termination pair. Its base-factor count is

(the empty product is one), and its cost before the auxiliary tensors of the readable tree are introduced is R^b. No conditional branch is exempt from this cost.

11 An exact finite-family optimization

For each completion script, the entropy bound gives many possible rate pairs, one for each leaf law. We compute their exact support function by optimizing a weighted sum of rates. A convex-geometric step then selects the best point at a prescribed rectangular shape.

Fix a distinguished side L and a parameter t\ge0. For two different colors i,j, let

A label read by those sides contributes with coefficient \eta_{ij} to the score S+tT.

For a conditional tree of color i, denote its maximum score by V_i. For base two, all three values start at zero. For base three they start at

A completion with center i and size m updates them simultaneously:

For a termination keeping i,j, the score is

At weight zero, these expressions mean their continuous limits. Equivalently, replace a weighted log-sum by the maximum score of the allowed words. In particular, in (11.3) the all-i word remains excluded; its zero-weight value is

All ranges in this definition are finite. The recurrences use only three conditional scores per script, even though the underlying readable tree can be much larger.

The entropy maximization identity used below is the standard conjugacy between log-sum-exp and negative entropy [6, Example 3.25]. We include its elementary proof and the conditional-tree argument needed for these recurrences.

The geometric step uses the supporting-halfspace description of a closed convex set [22, Theorem 8.24]. The reduction to a ray and the restriction of the parameter interval are proved below for this family. Let \calH_F be the closed downward convex hull of the normalized rate pairs in Lemma 11.2, and let \calH_{F_p} also include the square rate point (2/p,1/p) before taking that hull. These hulls are taken in the nonnegative quadrant. Their intersection with the ray (S/C,T/C)=(2d,kd) determines the best balanced bound supplied by these rates.

The theorem supplies a finite mathematical prescription for every aspect ratio. For an active script, (11.6) gives exposed leaf laws. At a nonsmooth contact, convex combinations of points on the exposed face meet the desired ray. Coordinatewise decrease is also allowed. These laws and combinations can be approximated as in Theorem 9.2. No assertion that one center sequence is numerically optimal is needed.

Smaller script lists give valid subfamilies, while allowing more completions gives further valid bounds. The truncation to t\le1 uses all three distinguished-side choices; they should be retained when such subfamilies are formed.

12 Three parameter certificates

We now select three scripts in \calF_7 and specify their leaf laws. The first two establish the dual-exponent and rectangular conclusions of Theorem 1.1. The third records the square bound \omega<2.267 achieved by this finite family, independently of the stronger square construction in Theorem 1.1. The inequalities in this section use rational enclosures, not numerical feasibility assumptions.

12.1 A dual-exponent witness

Use base two, distinguished side X, and its color \colB. After b base factors, regard the X-coordinates as binary words of length b; the logarithmic base cost is b\log2. We seek a final leaf law for which X is uniform on all these words and S=\HH(X)=b\log2. By Corollary 9.3 and the output-size lower bound, such a law gives

The construction will preserve the exact incident-entropy equality while increasing the nonincident entropy T.

To identify what preserves this equality, let X also denote the random coordinate induced by a leaf law on a readable tree, including a tree conditional on one color. At a node \nu, conditioning means that the path reaches that node, and the conditional mutual information is

Since a leaf determines X, successive conditioning at the nonterminal nodes telescopes to

At an incident node the child is a function of X and the prefix, so its mutual information is \HH(\text{child}\mid\nu). Subtracting these incident contributions gives

The terms on the right are nonnegative. Thus S=\HH(X) precisely when every nonincident choice at a positive-mass node is independent of X, conditional on the preceding choices.

We maintain this equality separately within each color. Partition the binary words into an active set P and its complement Q, with the following properties:

1. 1.

   color \colB permits precisely P, while each other color permits precisely Q;

2. 2.

   the chosen conditional law of each color makes X uniform on its permitted set;

3. 3.

   its conditional incident entropy is exactly the logarithm of that set’s size.

Write \rho=|P|/2^b, and let h_i be color i’s nonincident entropy; initially (\rho,b,h_i)=(1/2,1,0).

Terminate by keeping \colB and the inactive color with larger h, placing mass \rho on \colB. The incident termination label and the uniform conditional laws make X uniform on all 2^b binary words. Hence

By Corollary 9.3 and the size lower bound,

Use the following seven completions:

A minus sign means center \colB. A plus sign means the inactive color with larger h, with an arbitrary fixed tie choice. The absolute value is the completion size. Resolving the first tie as \colA, the centers are \colB,\colA,\colC,\colB,\colC,\colB,\colA.

For a short certificate, set \delta=|h_{\colA}-h_{\colC}|. A minus step leaves D unchanged and gives

At a plus step put

Substitution in Lemma 12.1 yields

Indeed h_i is the larger inactive entropy, and h'_j=mh_i+z, so the new maximum is mh_i+\max\{0,z\}.

After the first three steps, at b=8,

The two plus steps here have z=\log3 and z=\log(7/9). The subsequent bounds are

Their elementary verification is given in Section 12.4. Since \log2<0.6932 and \log3>1.098,

This proves the dual-exponent conclusion without any approximate equality being used to certify exponent two.

12.2 A one-parameter rectangular curve

Use base three, one size-three completion centered on \colA, keep \colB,\colC, and distinguish X. This is the 75-component support of Theorem 3.7; the leaf law below tunes its two balanced outer dimensions and its inner dimension. Every word in \{0,1,2\}^3 occurs on X. For a nonzero word x, its outer color is \colB, and the number of supported leaves in its fiber is d(x)=2^{\#\{\text{zero entries of }x\}}. For the zero word, its outer color is \colC, and d(0)=3^3-2^3=19. The fiber histogram is therefore

The total number of leaves is 75.

Give x probability proportional to d(x)^t, and choose a leaf uniformly within its fiber. Put

Then \HH(X)=h(t) and \HH(\text{leaf}\mid X)=g(t). In the nonzero branch, the \colA/\colB pattern and the choices within \colB are incident to X; the choices within \colA are hidden on Y,Z. In the zero branch all choices after branching are on Y,Z. The outer \colB/\colC label is incident to X. To check that the hidden choices do not leak information about X, fix a nonzero outer branch and its \colA/\colB pattern. Then d(x)=2^{\#\colA} is constant over that pattern. Each leaf has probability d(x)^{t-1}/Z(t), so the hidden choices in its \colA-slots are independent of the remaining X-coordinates, including after any preceding slot histories. The zero branch has fixed X. The information identity (12.1) therefore gives precisely S=h(t), T=g(t). Its base cost is 3^3, and Corollary 9.3 gives

Here w(k)=W(1,k,1) can also be read for k>1; we use only aspect ratios in [0,1].

At t=2/3, write u=2^{2/3}, v=19^{2/3}. Then

Cubing verifies

Using the logarithm bounds below gives

In particular

Monotonicity proves w(0.709)<2.092.

12.3 A finite-family square witness

Use base three and the completions

then keep \colB,\colC. The number of original factors is b=72. Let d_i be the number of conditional monomials of color i. Initially (d_{\colB},d_{\colA},d_{\colC})=(2,2,1). A size-m completion at i updates counts to

After three steps the vector is (20691584,13993344,10144225). After four it is

coordinatewise. The final sum of the kept counts is

and in particular

The substitution of lower counts is legitimate: the polynomial (a+b)^3+(a+c)^3-2a^3 has nonnegative coefficients.

Under the uniform leaf law, the sum of the three pair rates is \log N. Averaging over permutations balances all three at \log N/3. Thus Theorem 9.2 gives

The three constructions above yield their stated bounds once the following elementary enclosures are verified.

12.4 Elementary interval verification

For 1\le y\le2, put s=(y-1)/(y+1). The logarithm series has the rational enclosure

It follows by summing the positive series for 2\operatorname{arctanh}s and bounding its tail geometrically. For a positive rational x, write x=2^a y with 1\le y\le2 and use \log x=a\log2+\log y. Rational substitution in (12.14) gives

For the dual witness,

the displayed bounds for \rho_{24} and \delta_{24} now use only rational arithmetic. Alternating Taylor bounds through degrees six and seven give

Consequently the logarithm series at

proves 0.635<z_{48}<0.651 and z_{288}>0.628. Also

The remaining \rho inequalities are direct rational powers. This verifies every inequality used in (12.10). The cube-root brackets and the expression for g similarly verify the curve certificate.

For reference only, evaluation of the exact formulas gives

The proofs above rely on the rational inequalities, not these decimal approximations. The accompanying certificate scripts reproduce the finite support/count calculations and all stated rational enclosures. In a fresh writable copy of verification/certificates/, the command python3 checks/run_checks.py uses integer and rational arithmetic from the Python standard library; its three checkers separately verify the numerical inequalities, finite supports and counts, and declared baseline data. The optional numerical diagnostics are not used in these certificates.

13 Comparison with ordinary combinations

Theorem 1.1 supplies the square estimate needed by Proposition 13.3 at p=2.258. We retain the general statement for any available square estimate w(1)\le p with 2<p\le2.258, together with the specified baseline and the hypotheses on further inputs below. We also give a comparison through aspect ratio 0.93 using only the finite-family witnesses of Section 12 on the new-algorithm side.

We compare upper-bound estimates, not unknown exact values of W. A cost tuple (a,b,c;e) records the certified estimate W(a,b,c)\le e. The operations considered below act on such recorded estimates.

We use Table 1 of arXiv:2307.07970v2 and arXiv:2404.16349v3. The latter’s version 2 has the same listed rectangular entries; the updated square entry does not affect the argument. This definition makes the numerical baseline reproducible. It does not assert that the tables exhaust every possible parameter choice in the source algorithms.

13.1 A separator preserved by the baseline operations

Let

Then 0<v_p\le u_p\le1. For a triple with smallest coordinate c, put

Equivalently, without ordering the coordinates,

the maximum of the three linear forms that assign v_p to one coordinate and u_p to the other two.

For any additional old input it suffices to check the plane at p=2.258 together with the usual size bound. Indeed, after ordering,

If the parenthesis is nonnegative, this increases with p. Otherwise it is at most the size bound a+b.

For shapes (1,\ell,1), the test at p=2.258 is

If \ell\le0.45, or \ell\ge2/0.45-1, it already follows from the size bound. Between those regimes the following downward roundings of the published entry values suffice. They are bounds on the reported costs, not lower bounds on matrix-multiplication exponents.

For example, the newer entries at \ell=.50,.60,.70 are 2.042776,2.092351,2.152770, respectively [1]. All displayed roundings satisfy (13.3) by substitution. The other entries either lie in the automatic size-bound region or are covered by these grouped tests. It follows from Lemma 13.2 that every estimate generated by \mathcal B_p remains on or above P_p.

13.2 The strict improvement interval

The endpoint at one is excluded because the comparison uses the same square point on both sides. By Theorem 1.1, w(1)<2.258, so Proposition 13.3 applies at p=2.258 and proves strict improvement over \mathcal B_{2.258} throughout 0.321334<k<1. If a more precise old exponent-two endpoint is supplied, the same statement uses that endpoint in place of the rounded table entry. No strict improvement is asserted where the baseline already gives two.

There is also a comparison using only the constructions in \calF_7. Interpolate their three proved points

Against the numerical p=2.258 separator, the comparisons at k=0.465,0.709,0.93 are

Both differences are affine on the intervening segments. The smallest endpoint margin is greater than 0.0002598; these inequalities also follow directly from rational arithmetic. Thus this finite family improves that numerical baseline through k=0.93, in addition to the flat-range improvement.

13.3 A sufficient test for further old estimates

The table comparison can be extended without evaluating a large nonconvex parameter program, provided the extra input estimates satisfy an explicit condition. Let f be the convex upper-bound envelope from such old estimates before adding the new square point. Suppose

and include the known estimates

Condition (13.5) concerns the specified envelope of estimates. The published record values alone do not prove it for every possible untabulated parameter choice.

This is a sufficient inclusion rule for further baseline inputs, not a claim about all future analyses of the source tensors. For an enlarged baseline, Proposition 13.3 gives strict improvement wherever that baseline exceeds two in 0<k<1. The comparison with \mathcal B_{2.258} uses the proved dual-exponent witness together with Theorem 1.1; the extension in Proposition 13.4 still requires (13.5). The finite-family numerical bounds were established independently in Section 12.

Scope of the result. The family yields asymptotic arithmetic exponents with arbitrarily small positive slack. It does not claim a practical crossover size or global optimality of the chosen seven-completion family. The finite-family entropy argument and parameter certificates are independent of the square construction in Theorem 1.1. In the rectangular support bound and this comparison, an available square estimate enters through its explicitly charged exponent point (2/p,1/p).

14 Finite-exception characteristic transfer

For a field F and 0\le k\le1, let w_F(k) denote the arithmetic exponent for the dimensions (n,\lceil n^k\rceil,n), defined as in the introduction but counting operations over F and allowing constants from F. Put \omega_F=w_F(1) and \alpha_F=\sup\{k\in[0,1]:w_F(k)=2\}. The constants in operation-count bounds may depend on the field and the fixed schemes below; coefficient bit sizes and numerical stability are not part of this model.

The argument neither computes \mathcal S nor covers its primes. It applies only to the two fixed schemes chosen above.

The accuracy-dependent schemes in this corollary do not supply a common finite set of exceptional positive characteristics. No transfer of \alpha_F>0.465 to positive characteristic is asserted.

A Complete barrier coefficients

The following table completes the rational definition (7.16). Every displayed decimal, including those in scientific notation, is exact. The terms are listed in increasing i and then increasing j; no further coefficient file or optimizer is needed to specify the barrier.

B Reproducing the finite certificate

The accompanying certificate verifies the finite arithmetic statements used in Theorem 7.1. The tensor constructions, the passage from grid checks to continuum inequalities, and the error allowances used in that passage are proved in the body of the manuscript.

Inputs and source identity. The directory verification/certificate/ contains the 52 exact decimal coefficients of the barrier, both integer coefficient charts, all numerical generators and checkers, and their reference outputs. The packet manifest records the size and SHA-256 of every source and input file. The README describes the package, and the supplemental checker verifies the additional arithmetic bounds used in this manuscript.

The two chart hashes are

qP420_gmp:
7dc037ea127cece2216f3219eeeca4cdab0288319a10111a78d272586b776f0b
qP780_gmp:
f23c0480f1109509545fdd17bb4de81602f50952411554b337105defbe7a070c

The barrier coefficient file, inputs/newc22, has SHA-256

41d42a58936b9da0f01a98a24fc4e998a00b83c9f4032a4ae166b7ef11073912

The working-copy path substitutions made by the driver are recorded separately from the source hashes. They change input locations and compiler selection, not arithmetic formulas or thresholds.

Running the check. A standard run requires Python 3.10 or later, a POSIX system supporting fork, a C++17 compiler with signed 128-bit integer support and UndefinedBehaviorSanitizer, and the GMP C++ library for chart generation. A preflight checks the additional assumptions of a 64-bit long and arithmetic right shift of signed negative integers. Assertions must remain enabled. From verification/certificate/, run

python3 reproduce.py \
  --cxx 'g++ -fsanitize=undefined -fno-sanitize-recover=all' \
  --work-dir ../../certificate-run
python3 verify_manuscript_bounds.py --work-dir ../../certificate-run

A compatible Clang installation may be selected instead. The commands make no network requests or package installations. They write into a new output directory and refuse to overwrite an existing run or supplemental report. The optional flag --reuse-charts uses the supplied chart bytes after hash verification; omitting it regenerates both charts.

This distinction matters mathematically. The low-degree residual calculation uses the rounding-defect bound for the coefficient recurrence. Matching a stored hash alone does not independently establish that recurrence. Both full charts were regenerated with GMP integer arithmetic, with fail-fast undefined-behavior checks, and found to agree byte-for-byte with the supplied inputs. Separate small-degree comparisons also matched the GMP generator against the Python recurrence. The computation of the residual and chart differences then uses exact integer upper bounds.

Finite coverage. The complete run passed all stages listed below. The preserved command records include compiler flags, exit codes, source substitutions, hashes, and logs.

The finite tensor examples check selected identities; their general forms are proved earlier. For the interior run, the sector identifiers were independently checked to be exactly 0,\ldots,127, without omissions or duplicates. Each saved sector-input hash agreed with the corresponding reference hash, and every checker process returned success. The interval checker rejects an unresolved box at its maximum depth rather than accepting it.

The reproduced boundary output is

h -4180063084
b 0 65536 amb 6 terms 7250 edge 128315602072 cap 152568202355

In particular, the actual edge-sample minimum is

The boundary proof uses this stronger measured minimum when paying its conservative endpoint and displacement allowances. It does not replace it by the checker’s weaker acceptance threshold 12\cdot10^{-6}. A supplemental execution also asserted that each endpoint gap used in a nonambiguous boundary interval had actually been evaluated; its full output was unchanged.

The interface with the analytic estimates. The rational certificate gives

The logarithm comparison uses a finite positive series for 2\operatorname{atanh}(1/2) and an exact geometric remainder. The physical fourth-derivative coefficient sum is also checked exactly to be less than 435\cdot10^6.

The final-summary program takes the analytic interior margin 9.8\cdot10^{-8}, boundary margin 5.5\cdot10^{-6}, and inset cost 1.3\cdot10^{-6} as inputs; it does not prove those estimates. The supplemental program verify_manuscript_bounds.py explicitly records this interface, checks the actual boundary minimum and the exact allowance subtractions, and rechecks the complete interior-sector identities and hashes. The justification of each allowance, and hence of the continuum conclusion, is the analytic argument of Theorem 7.1. These programs are not a proof-assistant formalization and do not claim a practical matrix-multiplication implementation.