The realization problem

An exact rank decomposition specifies how many products of two input-dependent linear forms are needed. It does not specify the linear circuits computing those forms, the order in which gates run, when values die, how a high-fan-out value is distributed, or how a degeneration is evaluated and extracted at finite precision.

The basic receipt therefore keeps separate coordinates for nonscalar products $M$ , additions and subtractions $A$ , fixed-scalar gates $C$ , dependency depth $D$ , peak live scalar storage $S$ , raw fan-out $F$ , explicit copy buffers, and coefficient or working-precision data. Each theorem names the model in which those coordinates are measured.

The distant question $\omega=2$ is not resolved here. The results explain how known algebraic certificates become executable DAGs and which resource bounds survive that transfer.

MMR-009 · fixed-certificate calibration

One Strassen certificate supports different executable tradeoffs

The standard $2\times2$ Strassen formulas have seven nonscalar products and eighteen linear additions or subtractions. In the one-shot scalar-register model, the same products and operation counts admit both

(D,S)=(5,5) \qquad\text{and}\qquad (D,S)=(4,6).

The five-register point uses an explicitly scheduled association; balancing the four-term output trees shortens the critical path but requires six registers in the declared family. Exact order-ideal search checked all 225 per-output associations and all nine balanced depth-four pairings.

This is the first separation in the excursion: tensor rank and even fixed addition count do not determine an executable depth–storage point. It is a calibration result, not a new Strassen algorithm.

MMR-014 · exact composition

Sealed arithmetic receipts compose exactly

Write an exact bilinear algorithm as three explicit linear straight-line programs: $L_U$ and $L_V$ create the input forms, and $L_W$ recombines the $r$ products. Under literal typed DAG substitution into a sealed extension context, the receipt adds exactly $r$ nonscalar products and the declared gates of those three circuits.

Coefficient matrices alone give useful row-wise upper bounds,

A(B)\le \operatorname{nnz}(B)-z(B), \qquad C(B)\le \operatorname{nnz}(B),

but they do not record sharing or dependency order. If optimization is allowed across the seam, the literal receipt remains an executable upper bound rather than an exact optimized count.

MMR-025 · MMR-031 · MMR-036 · MMR-042

Storage needs a continuation-sensitive boundary receipt

The audited chain uses fixed finite acyclic arithmetic DAGs, one-shot execution without recomputation, free read-only inputs, unit scalar storage, and transparent downstream-only sewing. A legal prefix is an order ideal. These hypotheses are part of the theorem: atomic module execution, resynthesis, communication cost, bounded fan-out, and repebbling are different models. Peak-memory scheduling in this one-shot setting is the weighted one-shot black-pebbling problem; Jin, Purohit, Svitkina, Vee, and Wang give the relevant modern formulation and algorithms (reference).

Two gadgets can agree semantically and have the same aggregate gate counts, depth, storage, labelled output-arrival vector, and unlabelled fan-out multiset, yet require different peak storage in the same transparent downstream context. The missing information is which boundary values remain live after each reachable internal prefix and what work can follow.

For a fixed acyclic gadget, an executed prefix is an order ideal. The complete boundary-ideal receipt records the reachable ideal graph, exposed ports, pending internal uses, and the nonboundary live-frontier count. The downstream context supplies the external-pending bits. Compatible gadget and context ideals form a product system; min–max dynamic programming on that system gives exact optimal peak storage for every finite downstream transparent context. This is a finite sufficiency theorem, not a claim that the exponentially large receipt is minimal or efficiently constructible.

More precisely, if $I$ and $J$ are compatible gadget and context ideals, the exact live weight is

w(I,J)=\lambda_G(I)+\lambda_H(J)+ \left|\{b\in B\cap I:\mu_I(b)\lor\eta_J(b)\}\right|.

The two lambda terms count live nonboundary frontiers. The two pending-use predicates record whether a boundary value is still needed inside or outside the gadget; their disjunction counts that value once. The optimal peak is the least possible maximum of $w$ along a path from the empty compatible pair to the terminal pair.

The receipt can be compressed. Give an ideal the observation $\ell(I)=(R(I),\mu_I,\lambda_G(I))$ . Strong bisimulation requires equal observations and matching successors in both directions; quotienting by it preserves every compatible product path and hence the exact optimum. Standard partition refinement supplies its algorithmic setting (Paige–Tarjan). Equality of the sets of completed contracted observation traces is also sufficient: record $\ell$ along every complete gadget path, contract adjacent repeats, and retain an explicit terminal marker. Context steps commute across a repeated-observation block, so equal completed trace sets produce the same attainable peak values.

The trace receipt is strictly coarser than strong bisimulation only in the stated untrimmed model: the separating gadget contains an isolated dead gate whose execution changes no storage observation. Removing dead code removes that witness. Whether a separation survives when every internal vertex reaches a boundary output remains open. No claim is made that completed trace equality is the coarsest exact storage congruence. The distinction between trace and branching equivalences is classical concurrency theory; the storage theorem applies that distinction to the displayed min–max sewing product (Groote–Vaandrager; van Glabbeek).

Audited step	Exact role in the chain
MMR-023–MMR-025	Equal aggregate receipts can produce composed peaks two and three; labelled arrival times still do not suffice.
MMR-029–MMR-031	Composite prefixes are compatible ideal pairs, the displayed weight is exact, and the min–max recurrence is complete.
MMR-036 and MMR-039	Label-preserving strong bisimulation is sound, while equality of the current label alone is not.
MMR-042 and MRF-025	Completed stutter-trace equality is a sound coarser receipt, and strong bisimulation is not minimal in the untrimmed model.

Four retained exact checkers reproduced the separating peaks, the product/monolithic recurrence agreement, the $625\to256$ bisimulation quotient, and equality over all 118 enumerated productive one-port contexts. These finite checks corroborate the analytic proofs; they do not replace them. The exact transcript and checker hashes are in the audit certificate.

These are one-shot live-storage theorems. They are not red-blue pebble I/O bounds and do not introduce a memory hierarchy or communication cost that the model lacks.

MMR-052 · MMR-059 · MMR-061 · MMR-062

Explicit recursion keeps depth, storage, and fan-out on one graph

A literal block recursion inherits arithmetic counts from the base DAG, but its storage depends on the recursive-call frontier of the chosen macro schedule. For the two calibrated standard-Strassen schedules,

\begin{aligned} D_{\rm store}(N)&=1+4\log_2N, &S_{\rm store}(N)&=\frac{5N^2-2}{3},\\ D_{\rm depth}(N)&=1+3\log_2N, &S_{\rm depth}(N)&=2N^2-1. \end{aligned}

Literal recursion also grows raw fan-out. An ownership-aware fan-out-two compiler inserts exactly

C_2(N)=\frac{24}{7}N^{\log_2 7}-4N^2

identity buffers for powers of two in the sealed copy-only model. The resulting construction has exact depth $1+5\log_2N$ and a proved live storage upper bound $S(N)\le3N^2$ . Finite expanded-DAG checks through $N=32$ return $3N^2-2$ , but that equality remains conjectural beyond the checked cases.

Polynomial degenerations become finite exact algorithms

A border-rank statement is executable only after choosing an explicit polynomial curve. Suppose

\sum_{\ell=1}^{r} u_\ell(t)\otimes v_\ell(t)\otimes w_\ell(t) =t^qT+t^{q+1}E_1+\cdots+t^{q+e}E_e.

After normalization by $t^{-q}$ , exact coefficient extraction at $e+1$ nonzero evaluation points gives a literal finite realization with at most $(e+1)r$ nonscalar products. Tensor powering changes the receipt to length $r^k$ and normalized error degree $ke$ , so direct interpolation uses $(ke+1)r^k$ products.

The actual coefficient curve, field, denominator height, and chosen linear circuits are indispensable. A numerical border-rank upper bound alone cannot supply them, and exact interpolation does not by itself imply numerical stability.

MMR-087 · MMR-095 · MMR-104 · MMR-110

Two complete DAGs realize the same BCLR certificate differently

Two complementary five-term BCLR curves first produce a length-ten degeneration of the rectangular $\langle3,2,2\rangle$ tensor. Three cyclic orientations then give a length-1000 degeneration of $\langle12,12,12\rangle$ with order three, total degree six, and normalized error degree three.

Base realization	Receipt $(M,A,C,D,S,F)$	Rounded-path increment
Canonical coefficient rows	$(1000,13408,15552,14,2001,60)$	17
Shared separable Kronecker circuits	$(1000,4504,8128,19,2002,5)$	23

The second DAG improves additions, fixed-scalar gates, fan-out, and fan-out-two buffer count while worsening raw depth, declared storage by one scalar, and rounded-path length. They are therefore genuine Pareto-incomparable common-DAG receipts; their best coordinates cannot be combined into a fictitious third algorithm.

Both have maximum-entry error amplification base 768 in the declared floating-point model. Combined with the truncation envelope and $|t|=O(1/k)$ , this yields the sufficient mantissa law

p=3k\log_2k+O\!\left(k+\log k+\log(1/\tau)\right).

This is a forward-error upper bound for the declared DAGs, not backward stability and not a precision lower bound.

MMR-115 · direct-sum boundary

Complete direct sums are neutral; selection carries information

If $D=\bigoplus_i\langle n_i,m_i,p_i\rangle$ , then its $N$ th tensor power is the labelled direct sum over words of constituent types. For $v_i=n_im_ip_i$ ,

\sum_{\mathbf i}\operatorname{Vol}(D_{\mathbf i})^{\rho/3} =\left(\sum_i v_i^{\rho/3}\right)^N.

Consequently, merely powering a complete direct sum gives the same asymptotic-sum inequality raised to the $N$ th power. Gains require a selected or merged subfamily. Arbitrary survivor masks can carry linear-size labelled information even when their aggregate volumes agree; structured type classes avoid this obstruction because a count vector plus combinatorial unranking generates them.

MMR-120 · MMR-122 · MMR-123 · MMR-124 · MMR-125 · MMR-126

A finite compiler reconstructs the asymptotic sum inequality

Let an explicit length- $r$ polynomial degeneration of normalized error degree $e$ realize

D=\bigoplus_i\langle a_i,b_i,d_i\rangle, \qquad v_i=a_ib_id_i.

Given a current exact square base $\langle n,n,n\rangle\le\langle R\rangle$ , choose a type vector $\mathbf c$ at power $N$ and put

L_{\mathbf c}=\binom N{\mathbf c},\qquad k=\left\lfloor\log_RL_{\mathbf c}\right\rfloor, \qquad V_{\mathbf c}=\prod_i v_i^{c_i}.

Inject the current algorithm's $R^k$ rank terms into identical type constituents, apply the construction in three cyclic orientations, and interpolate the common curve once. This yields the literal finite restriction

\boxed{ s=n^{3k}V_{\mathbf c}, \qquad R(\langle s,s,s\rangle)\le(3Ne+1)r^{3N}.}

With $\tau$ defined by $\sum_i v_i^\tau=r$ and Gibbs weights $p_i=v_i^\tau/r$ , the ideal exponent update is

\Phi(\beta)=\frac{3\beta\log r}{3H+\beta L}, \qquad \frac1{\Phi(\beta)}= \alpha\frac1\beta+(1-\alpha)\frac1{3\tau}.

The reciprocal form is a geometric contraction toward $3\tau$ . Explicit method-of-types thresholds therefore produce, for every fixed rational $\varepsilon>0$ , a finite exact base satisfying $\log_sR\le3\tau+\varepsilon$ , starting from naive multiplication rather than an oracle for $\omega$ .

Expanding the final base into balanced coefficient rows gives fewer than $3Rs^2$ additions, fixed-scalar gates, and fan-out-two buffers at the base. Sealed recursion preserves the product exponent, uses fan-out two, has dependency depth $O(\log n)$ , and pinned live scalar storage $O(n^2)$ . For rational certificates, coefficient height is computable and the final exact stationary base needs only $O_\varepsilon(\log n+\lambda)$ mantissa bits for the stated absolute-error target.

The construction is effective but not practical: a coarse bound is $s_\varepsilon\le \exp(\exp(O((\log(1/\varepsilon))^2)))$ .

Limits and failed transfers

The public failure record contains sixty-eight rejected arguments or overstatements. The recurring boundaries are substantive mathematical distinctions:

tensor rank is not total scalar arithmetic or an executable schedule;
live scalar storage is not communication or memory-hierarchy I/O;
transparent and atomic module boundaries have different composition laws;
finite receipt sufficiency is not receipt minimality or efficient compilation;
border-rank membership without an explicit curve cannot be compiled;
exact interpolation is not numerical stability;
resource coordinates from different DAGs cannot be spliced together; and
effectivity and exponent preservation do not imply practicality or a new exponent bound.

Each failure has its own stable $\mathrm{MRF}$ identifier in the Claims index, with the rejected inference, reason, and surviving lesson preserved.

Claims and evidence

The public research record contains 127 $\mathrm{MMR}$ records and 68 $\mathrm{MRF}$ failed-approach records. Their source statuses remain distinct: internal analytic proof, finite computational verification, published external calibration, conditional result, mixed evidence, or provisional boundary.

Principal results on this page are supported at L4. The remaining records remain at L2 or L3 until their complete proof or checker is exposed and independently re-audited through the public claim record.

Browse the complete matrix-realization claim and failure records

Sources

Boyer, Dumas, Pernet, and Zhou, “Memory efficient scheduling of Strassen-Winograd's matrix multiplication algorithm,” ISSAC 2009. arXiv:0707.2347.
Holtz and Shomron, “Computational Complexity and Numerical Stability of Linear Problems.” arXiv:0906.0687.
Ce Jin, Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua R. Wang, “New Tools for Peak Memory Scheduling,” preprint, 2023. arXiv:2312.13526.
Robert Paige and Robert E. Tarjan, “Three Partition Refinement Algorithms,” SIAM Journal on Computing 16(6) (1987), 973–989. DOI.
Jan Friso Groote and Frits W. Vaandrager, “An Efficient Algorithm for Branching Bisimulation and Stuttering Equivalence,” inICALP 1990, LNCS 443, 626–638. DOI.
Rob J. van Glabbeek, “The Linear Time–Branching Time Spectrum,” in CONCUR 1990, LNCS 458, 278–297. DOI.
Bini, Lotti, and Romani, “Approximate Solutions for the Bilinear Form Computational Problem,” SIAM Journal on Computing 9 (1980). DOI.
Landsberg and Ryder, “On the Geometry of Border Rank Algorithms for $n\times2$ by $2\times2$ Matrix Multiplication,” Experimental Mathematics 26 (2017). arXiv:1509.08323.
Demmel, Dumitriu, Holtz, and Kleinberg, “Fast Matrix Multiplication is Stable,” Numerische Mathematik 106 (2007). arXiv:math/0603207.
Schönhage, “Partial and Total Matrix Multiplication,” SIAM Journal on Computing 10 (1981). DOI.
Romani, “Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication,” SIAM Journal on Computing 11 (1982). DOI.
Vrana, “Partial and Weighted Matrix Multiplication.” arXiv:2408.15728.