==== TABLE OF CONTENTS ====
Staggered-extraction-for-exact-matrix-multiplication-over-every-field//figures/pipeline.tex
Staggered-extraction-for-exact-matrix-multiplication-over-every-field//main.tex
Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/foundations.tex
Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/introduction.tex
Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/joint-extraction.tex
Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/leaf-volumes.tex
Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/parameter-tables.tex
Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/parameters.tex
Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/recovery.tex
Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/staggering.tex
Staggered-extraction-for-exact-matrix-multiplication-over-every-field//references.bib
===========================
==== BEGIN Staggered-extraction-for-exact-matrix-multiplication-over-every-field//figures/pipeline.tex ====
\begin{figure}[t]
\centering
\begin{tikzpicture}[x=1cm,y=1cm,font=\small,
stageA/.style={fill=blue!10,draw=blue!50!black},
stageB/.style={fill=orange!13,draw=orange!65!black},
stageC/.style={fill=green!10,draw=green!45!black},
cell/.style={minimum height=.57cm,minimum width=1.65cm,
rounded corners=1pt,inner sep=3pt,align=center}]
\node[anchor=west,font=\bfseries\small] at (0,0.65)
{(a) A finite schedule: each entry names the lot being processed};
\fill[black!4,rounded corners=2pt] (5.55,-2.82) rectangle (8.55,0.25);
\node at (2.50,0) {tick $1$};
\node at (4.25,0) {tick $2$};
\node[align=center] at (7.05,0) {tick $\tau$, $3\leq\tau\leq K$};
\node at (9.80,0) {tick $K+1$};
\node at (11.90,0) {tick $K+2$};
\node[anchor=west] at (0,-.65) {A: $8\to4$};
\node[anchor=west] at (0,-1.38) {B: $4\to2$};
\node[anchor=west] at (0,-2.11) {C: $2\to1$};
\node[cell,stageA] (a1) at (2.50,-.65) {lot $1$};
\node[cell,stageA] at (4.25,-.65) {lot $2$};
\node[cell,stageA,minimum width=2.32cm] at (7.05,-.65) {lot $\tau$};
\node[cell,stageB] (b1) at (4.25,-1.38) {lot $1$};
\node[cell,stageB,minimum width=2.32cm] at (7.05,-1.38) {lot $\tau-1$};
\node[cell,stageB] at (9.80,-1.38) {lot $K$};
\node[cell,stageC,minimum width=2.32cm] (cfull) at (7.05,-2.11) {lot $\tau-2$};
\node[cell,stageC] at (9.80,-2.11) {lot $K-1$};
\node[cell,stageC] at (11.90,-2.11) {lot $K$};
\draw[->,thin,black!55] (a1.south east) -- (b1.north west);
\node[font=\footnotesize,black!65] at (2.50,-2.60) {start};
\node[font=\footnotesize,black!65] at (4.25,-2.60) {start};
\node[font=\footnotesize] at (7.05,-2.60) {$K-2$ full ticks};
\node[font=\footnotesize,black!65] at (9.80,-2.60) {finish};
\node[font=\footnotesize,black!65] at (11.90,-2.60) {finish};
\node[anchor=west,font=\bfseries\small] at (0,-3.35)
{(b) One full tick: six physical-order factors, each with all three depths};
\node[cell,stageA,minimum width=1.90cm] (aa) at (1.10,-4.03)
{A: lot $\tau$};
\node[cell,stageB,minimum width=1.90cm] (bb) at (1.10,-4.84)
{B: lot $\tau-1$};
\node[cell,stageC,minimum width=1.90cm] (cc) at (1.10,-5.65)
{C: lot $\tau-2$};
\node[draw=black!55,rounded corners=2pt,align=center,
minimum width=3.12cm,minimum height=2.30cm] (order)
at (4.78,-4.84)
{factor for $\sigma\in S_3$\\[4pt]
$\phi\circ\rho_h=\sigma$\\[4pt]
one sixth of each history};
\draw[->] (aa.east) -- (order.north west);
\draw[->] (bb.east) -- (order.west);
\draw[->] (cc.east) -- (order.south west);
\node[draw=black!55,fill=black!3,rounded corners=2pt,align=center,
minimum width=4.55cm,minimum height=2.30cm] (joint)
at (10.18,-4.84)
{one joint extraction\\[5pt]
$\displaystyle\frac{L_A+L_B+L_C}{6}
=\frac{C_*}{6}(1,1,1)$\\[6pt]
limiting log-yield per $N$: $\displaystyle\frac{C_*}{6}$};
\draw[->] (order.east) -- (joint.west);
\node[align=center,font=\footnotesize] at (7.03,-6.39)
{Tensoring the six outputs adds their limiting rates: $6\cdot C_*/6=C_*$.};
\end{tikzpicture}
\caption{Mixed-depth extraction with finite boundaries ($K\geq2$).
A lot advances one stage per tick, while a full tick combines three
different lots. Within each physical-order factor, the common order
$\sigma$ permits one application of Theorem~\ref{thm:joint-step} to
the summed capacities. The four boundary ticks have the positive
minima appearing in \eqref{eq:boundary-deficit}; they incur only the
fixed deficit $\beta$. The middle column is absent when $K=2$.}
\label{fig:pipeline}
\end{figure}
==== END Staggered-extraction-for-exact-matrix-multiplication-over-every-field//figures/pipeline.tex ====
==== BEGIN Staggered-extraction-for-exact-matrix-multiplication-over-every-field//main.tex ====
\documentclass[11pt]{article}
\pdftrailerid{}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{booktabs,array,longtable}
\usepackage{graphicx,tikz}
\usetikzlibrary{arrows.meta,positioning,calc}
\usepackage{microtype}
\usepackage{xcolor}
\usepackage[colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=blue!45!black]{hyperref}
\usepackage{bookmark}
\usepackage{placeins}
\usepackage[all]{hypcap}
\usepackage[nottoc]{tocbibind}
\hypersetup{pdftitle={Staggered extraction for exact matrix multiplication over every field},pdfauthor={OpenAI}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\F}{\mathbb F}
\newcommand{\R}{\operatorname{R}}
\newcommand{\CW}{\mathrm{CW}}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\av}{av}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\diag}{diag}
\newcommand{\1}{\mathbf{1}}
\allowdisplaybreaks[2]
\setlength{\emergencystretch}{2em}
\title{Staggered extraction for exact matrix multiplication over every field}
\author{OpenAI}
\date{September 24, 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove that the arithmetic exponent of square matrix multiplication over
every fixed field satisfies $\omega<2.371054886006746$. This includes every
positive characteristic.
\end{abstract}
\input{sections/introduction}
\input{sections/foundations}
\input{sections/joint-extraction}
\input{sections/recovery}
\input{sections/staggering}
\input{sections/leaf-volumes}
\input{sections/parameters}
\clearpage
\appendix
\input{sections/parameter-tables}
\clearpage
\bibliographystyle{plain}
\bibliography{references}
\end{document}
==== END Staggered-extraction-for-exact-matrix-multiplication-over-every-field//main.tex ====
==== BEGIN Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/foundations.tex ====
\section{Rank and the basic tensor}\label{sec:foundations}
Fix an arbitrary field $\F$. All tensor identities and linear maps below
are over $\F$, and all logarithms are natural. A tensor is viewed as a
trilinear form in three disjoint
sets of variables. Its rank $\R(T)$ is the least number of products of
three linear forms, one on each side, whose sum is $T$. A
\emph{restriction} substitutes linear forms separately on the three
sides. Restrictions cannot increase rank. A direct sum uses disjoint
variables, and a tensor product pairs the variable indices on each side;
rank is subadditive under direct sum and submultiplicative under tensor
product. These statements follow by applying the indicated operations
to rank decompositions.
For positive integers $a,b,c$, write
\[
\langle a,b,c\rangle
=\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c}
x_{ij}y_{jk}z_{ki}.
\]
This is the tensor for multiplying an $a\times b$ matrix by a
$b\times c$ matrix. Its \emph{volume} is $abc$. Pairing the three
matrix indices gives
\[
\langle a,b,c\rangle\otimes\langle a',b',c'\rangle
\cong\langle aa',bb',cc'\rangle.
\]
Cyclically permuting the three variable spaces replaces the parameters
by $(b,c,a)$ or $(c,a,b)$ and preserves rank.
\subsection{Exact rank and the arithmetic exponent}
Put $R_d=\R(\langle d,d,d\rangle)$ and
\begin{equation}\label{eq:rank-exponent}
w=\inf_{d\geq2}\frac{\log R_d}{\log d},
\qquad d\text{ an integer}.
\end{equation}
The flattening that sends a $z$ coordinate to its coefficient bilinear
form has rank $d^2$: the $d^2$ forms
$\sum_jx_{ij}y_{jk}$ are linearly independent. A rank-one tensor has
flattening rank at most one. Thus
$d^2\leq R_d\leq d^3$ and $2\leq w\leq3$. In particular,
\begin{equation}\label{eq:square-rank-lower}
R_d\geq d^w\qquad(d\geq1),
\end{equation}
where $R_1=1$ handles the unit case.
Let $\omega$ denote the arithmetic exponent of square matrix
multiplication over $\F$, counting scalar additions and multiplications.
A fixed rank-$R_d$ decomposition gives a bilinear matrix multiplication
identity with $R_d$ products. This identity remains valid on matrix
blocks: every product has its $x$-linear factor before its $y$-linear
factor, and comparison of coefficients proves the same identity for
noncommuting blocks with central coefficients in $\F$. At size $d^k$
the resulting arithmetic cost satisfies
\[
C_k\leq R_d C_{k-1}+O_d(d^{2k}).
\]
The implied constant may depend on the chosen decomposition. Since
$R_d\geq d^2$, this gives $C_k=O_d(kR_d^k)$, including the boundary
case $R_d=d^2$. Padding an arbitrary size to the next power of $d$
therefore gives cost $O_d(n^{\log_d R_d}\log(n+1))$. The logarithmic
factor is absorbed by $n^\eta$ for every $\eta>0$; taking the
infimum in \eqref{eq:rank-exponent} proves
\begin{equation}\label{eq:omega-rank-exponent}
\omega\leq w.
\end{equation}
We also need a uniform upper bound on exact square rank. Given
$\varepsilon>0$, choose one integer $d\geq2$ with
$\theta=\log_d R_d<w+\varepsilon$. For $h\geq1$, tensor powers and
padding give
\begin{equation}\label{eq:square-rank-upper}
\R(\langle h,h,h\rangle)
\leq R_d^{\lceil\log_d h\rceil}
\leq C_\varepsilon h^{w+\varepsilon},
\qquad C_\varepsilon=R_d.
\end{equation}
This argument uses one approximating dimension; it does not require the
infimum defining $w$ to be attained.
We use the following identical-summand form of Sch\"onhage's asymptotic
sum inequality~\cite{Schonhage1981}, with a proof from exact rank.
\begin{lemma}[Direct sums of identical matrix tensors]\label{lem:direct-sum}
Let $s,a,b,c$ be positive integers. If
\[
\R\left(\bigoplus_{j=1}^{s}\langle a,b,c\rangle\right)\leq R_*,
\]
then
\begin{equation}\label{eq:identical-direct-sum}
s(abc)^{w/3}\leq R_*.
\end{equation}
\end{lemma}
\begin{proof}
First consider $s$ copies of $\langle d,d,d\rangle$. When $s=1$,
the assertion $sd^w\leq R_*$ is \eqref{eq:square-rank-lower}.
When $d=1$, the direct sum is $\sum_{j=1}^s x_jy_jz_j$, whose
flattening has rank $s$, so the assertion also holds. We may therefore
assume $s,d\geq2$.
Fix $\varepsilon>0$ and the constant in
\eqref{eq:square-rank-upper}. For all sufficiently large integers $k$,
set
\[
h_k=\left\lfloor
(s^k/C_\varepsilon)^{1/(w+\varepsilon)}
\right\rfloor.
\]
Then $h_k\geq2$,
$\R(\langle h_k,h_k,h_k\rangle)\leq s^k$, and
\[
\lim_{k\to\infty}\frac{\log h_k}{k}
=\frac{\log s}{w+\varepsilon}.
\]
The $k$th tensor power of the given direct sum is a direct sum of
$s^k$ copies of $\langle d^k,d^k,d^k\rangle$, of rank at most $R_*^k$.
A rank-$r$ decomposition of $\langle h_k,h_k,h_k\rangle$, with
$r\leq s^k$, expresses it as a restriction of $r$ independent scalar
products. Tensor this restriction with
$\langle d^k,d^k,d^k\rangle$ and discard unused copies. It gives
$\langle d^kh_k,d^kh_k,d^kh_k\rangle$ as a restriction of the
available direct sum. Consequently
\[
R_*^k\geq(d^kh_k)^w.
\]
Taking logarithms, dividing by $k$, and then taking $k\to\infty$
at fixed $\varepsilon$ yields
\[
\log R_*\geq w\log d+\frac{w}{w+\varepsilon}\log s.
\]
Letting $\varepsilon\downarrow0$ proves $sd^w\leq R_*$.
For the rectangular case, let
$U=\bigoplus_{j=1}^s\langle a,b,c\rangle$ and tensor $U$ with its
two cyclic rotations. Distributivity gives $s^3$ independent copies of
\[
\langle a,b,c\rangle\otimes\langle b,c,a\rangle
\otimes\langle c,a,b\rangle
\cong\langle abc,abc,abc\rangle,
\]
and the product has rank at most $R_*^3$. The square case gives
$s^3(abc)^w\leq R_*^3$, whose cube root is
\eqref{eq:identical-direct-sum}. The same proof covers $abc=1$
through the unit square case.
\end{proof}
The hypothesis in Lemma~\ref{lem:direct-sum} specifies one common
\emph{oriented} triple $(a,b,c)$ for all summands. In the construction
below, exact history counts and common terminal type restrictions will
provide these identical dimensions.
\subsection{An integer coefficient construction}
The relation between approximate bilinear identities and exact algorithms
was studied by Bini~\cite{Bini1980}. Here a direct coefficient calculation
gives an exact rank bound over the original field, including when that
field is finite.
For an integer $q\geq1$, define the symmetric Coppersmith--Winograd
tensor~\cite{CoppersmithWinograd1990}
\begin{align*}
\CW_q={}&\sum_{i=1}^q
(x_0y_iz_i+x_iy_0z_i+x_iy_iz_0)\\
&+x_{q+1}y_0z_0+x_0y_{q+1}z_0+x_0y_0z_{q+1}.
\end{align*}
We use $q=5$. The following exact-rank estimate makes the field
independence and the polynomial overhead explicit.
\begin{lemma}[Rank bound for powers of the basic tensor]\label{lem:cw-rank}
Over every field and for every integer $m\geq0$,
\begin{equation}\label{eq:cw-power-rank}
\R(\CW_q^{\otimes m})
\leq(q+2)^m\binom{3m+2}{2}.
\end{equation}
\end{lemma}
\begin{proof}
We use the Laurent-polynomial identity of Coppersmith and
Winograd~\cite[Section~7, equation~(10)]{CoppersmithWinograd1990}
over the integers, with a formal variable $t$. Set
$X_1=\sum_{i=1}^q x_i$, $Y_1=\sum_{i=1}^q y_i$, and
$Z_1=\sum_{i=1}^q z_i$, and consider
\begin{align}
P(t)={}&t^{-2}\sum_{i=1}^q
(x_0+tx_i)(y_0+ty_i)(z_0+tz_i)\notag\\
&-t^{-3}(x_0+t^2X_1)(y_0+t^2Y_1)(z_0+t^2Z_1)\notag\\
&+(t^{-3}-qt^{-2})
(x_0+t^3x_{q+1})(y_0+t^3y_{q+1})(z_0+t^3z_{q+1}).
\label{eq:cw-laurent}
\end{align}
The only possible negative degrees are $-3,-2,-1$. Their
coefficients are, respectively,
\[
(-1+1)x_0y_0z_0,\qquad
(q-q)x_0y_0z_0,\qquad
(1-1)(X_1y_0z_0+x_0Y_1z_0+x_0y_0Z_1).
\]
The degree-zero coefficient is precisely $\CW_q$. Thus
$P(t)=\CW_q+tQ(t)$ for a polynomial $Q$ with integer coefficients.
In particular,
\begin{equation}\label{eq:cw-constant-power}
[t^0]P(t)^{\otimes m}=\CW_q^{\otimes m}.
\end{equation}
These coefficient identities remain valid after reduction to any field.
Regard \eqref{eq:cw-laurent} as $q+2$ products of three
Laurent-polynomial linear forms, absorbing the scalar prefactor of
each product into its $x$ form. In one tensor position the possible
degrees on the $x$ side lie, respectively, in
\[
\{-2,-1\},\qquad\{-3,-1\},\qquad\{-3,-2,0,1\}.
\]
The last set includes both terms of $t^{-3}-qt^{-2}$ within a single
linear form. On each of the other two sides the degrees lie between
$0$ and $3$.
Expanding $P(t)^{\otimes m}$ therefore gives $(q+2)^m$ products,
each of the form $A(t)B(t)C(t)$ with
\[
A(t)=\sum_{a=-3m}^{m}A_at^a,\qquad
B(t)=\sum_{b=0}^{3m}B_bt^b,\qquad
C(t)=\sum_{c=0}^{3m}C_ct^c.
\]
Here each coefficient is one linear form in the corresponding
tensor-product variables. The constant coefficient of this product
is
\[
\sum_{\substack{b,c\geq0\\b+c\leq3m}}
A_{-b-c}B_bC_c,
\]
a sum of at most $\binom{3m+2}{2}$ rank-one tensors. Summing over
the $(q+2)^m$ choices and using \eqref{eq:cw-constant-power} proves
\eqref{eq:cw-power-rank}. For $m=0$, both sides equal $1$ under
the empty tensor product convention. Only coefficient addition and
multiplication were used; no interpolation or field division is needed.
\end{proof}
\subsection{Strands and shapes}
Give the label $0$ weight $0$, the labels $1,\ldots,q$ weight $1$,
and the label $q+1$ weight $2$. Every term of $\CW_q$ has total
weight $2$. A \emph{strand of length $\ell$} is a copy of
$\CW_q^{\otimes\ell}$; its variable indices are words of length
$\ell$. For a triple $g=(g_0,g_1,g_2)$ of nonnegative integers
with $g_0+g_1+g_2=2\ell$, let $T_{\ell,g}$ be the restriction in
which the weight sums on the three sides are $g_0,g_1,g_2$.
The coordinates of $g$ refer to sides, whereas the weights $0,1,2$
refer to individual labels. A shape is \emph{positive} if all three
coordinates are positive. When $\ell$ is even, splitting a strand
into its two consecutive halves gives child shapes $u$ and $g-u$,
where $0\leq u\leq g$ coordinatewise and $\sum_i u_i=\ell$.
A zero coordinate gives an especially simple terminal tensor.
Suppose $g_0=0$. The $x$ word is then forced to be the all-zero
word. In each position a label on the $y$ side uniquely determines
the $z$ label: $0$ and $q+1$ are exchanged, and every label
$i\in\{1,\ldots,q\}$ is fixed. Thus the other two sides are
matched bijectively, and $T_{\ell,g}$ is
$\langle1,1,M\rangle$, where
\[
M=[z^{g_1}](1+qz+z^2)^\ell.
\]
For $g_1=0$ or $g_2=0$ the corresponding orientations are
$\langle M,1,1\rangle$ or $\langle1,M,1\rangle$. Restricting
the matched words by corresponding type conditions on their two
sides preserves this form, with $M$ replaced by the number of
allowed matched pairs; an empty matching gives the zero tensor.
This observation will supply the terminal volume counts.
==== END Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/foundations.tex ====
==== BEGIN Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/introduction.tex ====
\section{Introduction}\label{sec:introduction}
For a fixed field $\F$, the matrix multiplication exponent
$\omega=\omega_\F$ is the infimum of the real numbers $\tau$ for which
two $n\times n$ matrices over $\F$ can be multiplied using
$O(n^{\tau+o(1)})$ scalar additions and multiplications. This exponent
measures the asymptotic arithmetic cost of a central bilinear operation
and of many algorithms built from it. The field is fixed throughout;
constants in an arithmetic algorithm may depend on the field and on its
chosen finite construction.
Strassen's seven-product algorithm for $2\times2$ matrices gave the
subcubic exponent $\log_2 7$~\cite{Strassen1969}. Subsequent advances
used tensors to record bilinear operations: tensor rank counts the
products of linear forms needed to realize an operation. Approximate
bilinear identities and their conversion to exact algorithms
\cite{Bini1980}, Sch\"onhage's asymptotic sum inequality
\cite{Schonhage1981}, and Strassen's laser method
\cite{Strassen1987} established the main ingredients of this approach.
The sum inequality converts a low-rank direct sum of matrix tensors into
an exponent bound. The laser method constructs such direct sums by
restricting powers of a tensor with low asymptotic rank. Coppersmith and
Winograd combined these ideas with progression-free sets and introduced
the tensor family used here~\cite{CoppersmithWinograd1990}.
Passing to a larger tensor power gives more freedom in choosing the
intermediate pieces before extracting matrix tensors from them.
Stothers analyzed the fourth power, in work subsequently published with
Davie~\cite{Stothers2010,DavieStothers2013}. Vassilevska Williams
analyzed the eighth power, and Le Gall continued through the
thirty-second power~\cite{VassilevskaWilliams2012,LeGall2014}.
Alman and Vassilevska Williams then reduced the extraction loss that
arises when prescribed marginal distributions permit several joint
distributions, obtaining $\omega<2.3728596$
\cite{AlmanWilliams2024}.
A further source of loss is requiring entire variable blocks to be
disjoint when the final matrix tensors need only disjoint subsets of
those blocks. Duan, Wu, and Zhou used asymmetric hashing to reduce this
\emph{combination loss} in the recursive analysis
\cite{DuanWuZhou2023}. Vassilevska Williams, Xu, Xu, and Zhou allowed
finer sharing of variables and extended recovery from deletions on all
three sides to the restricted tensor products needed in the recursion
\cite{VXXZ2023}. Alman, Duan, Vassilevska Williams, Xu, Xu, and Zhou
then introduced successive compatibility tests that treat all three
sides differently~\cite{MoreAsymmetry2026}. These tests underlie the
extraction studied here.
For a recent numerical comparison, Dupont et al.\ obtained
$\omega<2.371177$ by optimizing the eighth-power instance of this
asymmetric framework, combining modern optimization with AlphaEvolve
\cite{Dupont2026}. Version~3 of \emph{More Asymmetry Yields Faster
Matrix Multiplication} records that improvement and credits the new
parameters to Dupont et al.\ \cite[Table~1]{MoreAsymmetry2026}.
We prove the following bound over every fixed field.
\begin{theorem}\label{thm:main}
Over every fixed field $\F$, the arithmetic exponent of square matrix
multiplication satisfies
\[
\omega_\F<2.371054886006746<2.371054887.
\]
\end{theorem}
The construction gives exact arithmetic algorithms, including in positive
characteristic. Its finite choices are independent of the input matrices.
The theorem concerns asymptotic arithmetic cost; the counting arguments
and parameter choices do not give bit-complexity or practical crossover
estimates.
\subsection{Proof overview}
We use the Coppersmith--Winograd tensor with parameter $5$, denoted
$\CW_5$. Section~\ref{sec:foundations} defines it and proves that the
rank of its $m$th tensor power is at most $7^m$ times a polynomial in
$m$, over the original field. A \emph{strand of length $\ell$} is a
copy of $\CW_5^{\otimes\ell}$. On each side the variables of $\CW_5$
are indexed by $0,\ldots,6$, with weights $0,1,1,1,1,1,2$.
A strand variable is a word of these indices, and a \emph{shape} records
the weight sums on the three sides. We start with strands of
length $8$ and split them successively into lengths $4$, $2$, and $1$.
At each depth we restrict by shape. A shape with a zero coordinate
already gives a matrix multiplication tensor; positive shapes pass to
the next split.
\paragraph{Combining capacities across depths.}
An extraction restricts a tensor to a direct sum of specified tensor
products. To make the outputs disjoint, its three side-assignment tests
each impose a bound on the guaranteed logarithmic number of outputs;
we call these bounds its \emph{directional capacities}. The guarantee
uses their minimum. The constituent-stage analysis in
\cite[Theorem~6.4]{MoreAsymmetry2026} already combines differently
prescribed populations at one depth before taking this minimum.
Our joint step also combines populations at different depths, provided
their priority orders agree on the physical tensor sides. For their
weighted capacity vectors $v_r\in\mathbb R^3$, the benefit of pooling
across depths is expressed by
\[
\sum_r\min_W v_{r,W}\ \leq\ \min_W\sum_r v_{r,W}.
\]
Thus a shortage on one side at one depth can be offset by capacity from
another depth.
Section~\ref{sec:joint} proves this joint extraction by following the
actual order of the tests. On the first side, variables are grouped by
their sequences of strand or half-strand weight sums; these groups are
the \emph{coarse blocks}. Each retained coarse block is assigned to a
unique output. Compatibility with that assignment then determines which
complete variables on the second and third sides
can be retained. The result is a direct sum of the intended products
with some variables deleted. Populations retain their ancestry and
physical placement throughout, so each subsequent split receives its
own prescribed distributions.
\paragraph{Recovering outputs with inherited restrictions.}
Some variables are missing because an earlier extraction imposed type
conditions, meaning conditions on empirical distributions of variable
statistics. Others are deleted to resolve competing assignments in the
current extraction. Earlier recovery arguments already treat
three-side deletions and inherited type conditions
\cite[Section~7]{VXXZ2023}, \cite[Section~6.5]{MoreAsymmetry2026}.
Section~\ref{sec:recovery} proves the form needed for our joint step.
With $N$ the large strand-count parameter, the extraction selects outputs
in which every orbit of complete variables under the allowed position
permutations loses at most $C/N$ of its variables, uniformly over the orbits. Here $C$ depends only on
the fixed population data and tolerances. Independent symmetry shifts
then cover the ideal tensor. Partitioning variables by their presence
in those shifts reconstructs every coefficient exactly once, over the
original field. Only a subexponential number of independent input copies
is needed. The recovered products can then be subdivided and used in
further extractions.
\paragraph{Staggering and the final rank comparison.}
A \emph{lot} contains $N$ length-$8$ strands. We stagger finitely many
lots so that, at an interior time step, one lot is at each of the three
splitting stages. Stage priorities balance the summed directional
capacities. The work is partitioned among the six physical axis orders;
one joint extraction acts on each part, and the six output counts
multiply. Section~\ref{sec:stagger} constructs this schedule, shown in
Figure~\ref{fig:pipeline}, and computes its finite boundary loss.
Section~\ref{sec:leaf-volumes} counts the common oriented dimensions
of the terminal matrix tensors and combines these counts with the
schedule to prove the total yield and rank comparison.
Write $H_0$ for the initial logarithmic yield, $C_*$ for the contribution
of the three staggered stages, and $S_*$ for the terminal logarithmic
matrix volume, all normalized per initial length-$8$ strand. The
direct-sum rank inequality then gives
\begin{equation}\label{eq:intro-constraint}
\omega_\F\leq\frac{3(8\log7-H_0-C_*)}{S_*}.
\end{equation}
For each fixed number of lots, we first take the divisible strand count
$N$ to infinity and remove approximation losses; the number of lots
tends to infinity last. Thus the boundary cost vanishes without a
uniform assertion for a growing schedule. The explicit rational data
in Section~\ref{sec:parameters} and Appendix~\ref{app:parameter-tables}
certify $S_*>0$ and place the ratio in
\eqref{eq:intro-constraint} below the bound in Theorem~\ref{thm:main}.
The complete parameter verifier and its rational-logarithm interval
certificate accompany the source. The proof requires a single feasible
choice of parameters, with no assertion that this choice is optimal.
==== END Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/introduction.tex ====
==== BEGIN Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/joint-extraction.tex ====
\section{A joint extraction at several depths}\label{sec:joint}
The constituent-stage analysis of
\cite[Theorem~6.4]{MoreAsymmetry2026} combines differently prescribed
populations at a common depth. The extraction below also permits
populations at different depths to share one hashing step, provided
their priority orders agree on the physical tensor sides. Population
data, strand lengths, and the constant sums defining their coarse
supports may differ. The successive compatibility checks follow
\cite[Section~4.1]{MoreAsymmetry2026}, building on the asymmetric
hashing and interface-tensor methods of
\cite{DuanWuZhou2023,VXXZ2023}. We specify the intended output first,
then derive the three capacities that govern its extraction yield.
For a probability vector $p$ on a finite alphabet, write
$H(p)=-\sum_a p(a)\log p(a)$, with $0\log0=0$. A word has
\emph{type} $p$ if its empirical distribution is exactly $p$; a type window
of width $\theta$ means coordinatewise distance at most $\theta$.
All alphabets, populations, and positive population masses in this
section are fixed as $N$ tends to infinity.
\subsection{The data of a joint step}
Index the populations by a finite set $\mathcal R$. Population $r$ has
$m_r=c_rN$ copies of a fixed strand tensor $F_r$ with finite variable
sets, where $c_r>0$ is rational. On each side its variables are
partitioned into coarse blocks indexed by $\{0,\ldots,16\}$.
Every monomial of $F_r$ has its triple of coarse indices in an
ambient support $\Omega_r$, whose elements $u=(u_X,u_Y,u_Z)$ satisfy
\begin{equation}\label{eq:coarse-sum}
u_X+u_Y+u_Z=s_r.
\end{equation}
Here $X,Y,Z$ is one common ordering of the physical sides. In the
product $\bigotimes_r F_r^{\otimes m_r}$, a coarse block is specified
by a sequence of indices, one for every strand.
A fine side variable is a complete basis variable of the product input;
its coarse block records the coarse index at every strand position.
The fixed strand tensor in a population is repeated identically at
all its positions. Populations with different histories or physical
placements are kept distinct.
Choose a rational law $p_r$ on $\Omega_r$ that maximizes entropy among
all laws on $\Omega_r$ with its three marginals. The support of $p_r$
may be smaller than $\Omega_r$. There are two kinds of population.
\begin{enumerate}
\item An \emph{ordinary population} delivers the full tensor block at
each selected triple $u$, without further output type tests. The
blocks may themselves be tensor products of child strands. This
includes extraction by whole-strand shape and the final split into
length-one strands.
\item A \emph{sharing population} consists of copies of $T_{\ell,g}$,
with even $\ell$ and $\sum_Wg_W=2\ell$. Its coarse index $u_W$ is
the weight sum in the left half, so
\[
\Omega_r=\{u:0\le u\le g,\ \textstyle\sum_Wu_W=\ell\},
\qquad T_{\ell,g}|_u=T_{\ell/2,u}\otimes T_{\ell/2,g-u}.
\]
Assume $p_r(u)=p_r(g-u)$. On each side $W$, a statistic of the full
half-strand variable takes values in a fixed finite alphabet
$\mathcal A_{r,W}$. A map $\rho_W$ from this alphabet to weights
determines the half weight sum. For every half-shape $u$ with
$p_r(u)>0$, prescribe a rational law $\nu_{r,u,W}$ supported on
$\rho_W^{-1}(u_W)$.
When a half-shape has a zero coordinate, the full variables on the
other two sides match by complementation. Require that their
statistics also match by a fixed bijection and that their prescribed
laws are its pushforwards. A side having a unique possible variable
has its corresponding point-mass prescription. These requirements
apply as well when two coordinates vanish.
\end{enumerate}
\paragraph{Ideal outputs and inherited masks.}
A \emph{target triple} $e$ is a triple of coarse sequences having exact
joint type $p_r$ in each population. Start with the tensor block at $e$.
In every sharing population, impose a positive type window around
$\nu_{r,u,W}$ separately in every class of positions of given
$(r,u,\text{half})$, on each side. The right-half prescription in the
class indexed by $u$ is $\nu_{r,g-u,W}$. Leave ordinary blocks
unrestricted. The resulting tensor product is the \emph{ideal output}
$Q_e$. Target triples have the same class sizes, so
their ideal outputs are isomorphic by position permutations preserving
the physical sides; denote a canonical such tensor by $Q_N$.
A fine side variable in a coarse block of $e$ is \emph{useful for $e$}
if it satisfies all these output windows; ordinary populations
contribute no further condition. Thus usefulness specifies the
variables of the ideal tensor. Additional input or separation tests
may delete some of them.
The child windows constrain the two halves separately. Inherited
conditions can also constrain how their statistics are paired at parent
positions. For a sharing population, suppress $r$ temporarily and define
the mixture law, omitting all zero-mass shapes as we do below:
\begin{equation}\label{eq:joint-pair-law}
D_W=\sum_{u\in\Omega_r}p(u)\,
\nu_{u,W}\otimes\nu_{g-u,W}.
\end{equation}
This is the expected pair law when, within each shape class, the left
and right statistics have their prescribed laws and are independently
arranged.
An input mask is always a deletion of individual side variables.
For sharing populations we allow finitely many empirical tests on
the ordered pair of half statistics, or a fixed function of that pair.
Their centers must be the law $D_{r,W}$ in
\eqref{eq:joint-pair-law}, or its corresponding pushforward, and their
widths must be fixed positive numbers. Ordinary input masks must
already follow from the exact target coarse types and the specified
ideal blocks. No other inherited masks are assumed. All masks are
imposed separately in the populations just defined. A mask on a
larger received class can instead be enforced separately, with
tighter widths and the same center, on any fixed subdivision; the
resulting partwise restrictions imply the original one.
Choose output widths small enough that replacing each prescribed
child law by any law in its window leaves the expected ordered-pair
law strictly inside every inherited window. This condition has a
uniform positive margin: for coordinatewise child errors at most
$\theta$, a product-law coordinate changes by at most $2\theta$,
and all relevant collections are finite. The same margin will be
required for the additional pair tests introduced in the proof.
\paragraph{Compatibility groups and capacities.}
The extraction will first separate targets by their $X$ coarse blocks
and impose the $X$ output windows. It then separates $Y$ variables,
imposes their output windows, and finally separates $Z$ variables.
The later-side separation tests use only those individual shape types
that matching forces from an earlier side. Define their designated
shapes by
\begin{equation}\label{eq:designated-compatibility}
\mathcal I_Y=\{u\in\supp p:u_Z=0\},\qquad
\mathcal I_Z=\{u\in\supp p:u_Xu_Y=0\}.
\end{equation}
A zero $Z$ coordinate lets matching transfer the $X$-side output
type condition to $Y$. For $Z$, a zero
$Y$ coordinate transfers the condition from $X$; a zero $X$ coordinate
instead uses $Y$, after its output windows have been imposed. If both
$X$ and $Y$ coordinates vanish, the $Z$ variable is forced.
For the remaining shapes with a given $W$ coordinate, the pair law
$D_W$ determines only an aggregate statistic law after the designated
contributions are removed. We impose no individual compatibility
test on these shapes. The exact predicate and its tolerances are
given in the incidence count below.
For $W\in\{Y,Z\}$, the partition $\mathcal G_W$ consists of the
individual groups $\{u\}$ for $u\in\mathcal I_W$, and the residual
groups $\{u\in\supp p\setminus\mathcal I_W:u_W=i\}$.
Empty groups are omitted. A residual group is treated as residual
even when it contains just one shape. Put $p(G)=\sum_{u\in G}p(u)$
and define
\begin{equation}\label{eq:joint-group-entropy}
J_W=\sum_{G\in\mathcal G_W}p(G)
H\left(\frac{\sum_{u\in G}p(u)\nu_{u,W}}{p(G)}\right),
\qquad W\in\{Y,Z\}.
\end{equation}
The entropy $J_W$ measures the choices for one half-statistic word
within these groups. Counting both halves gives the cost $2J_W$;
comparison with the pair-word entropy $H(D_W)$ gives the saving that
controls the number of compatible targets. Accordingly, define the
sharing capacities by
\begin{equation}\label{eq:sharing-capacities}
C_{r,X}=H(p_{r,X}),\qquad
C_{r,Y}=H(D_{r,Y})-2J_{r,Y},\qquad
C_{r,Z}=H(D_{r,Z})-2J_{r,Z}.
\end{equation}
Only the law of half-shapes is assumed invariant under $u\mapsto g-u$;
the two prescriptions $\nu_{u,W}$ and $\nu_{g-u,W}$ may differ.
For an ordinary population no compatibility restriction is needed,
and the capacities are simply
\[
C_{r,X}=H(p_{r,X}),\qquad C_{r,Y}=H(p_{r,Y}),\qquad
C_{r,Z}=H(p_{r,Z}).
\]
The counting arguments below give a common interpretation: each
$C_{r,W}$ is the entropy saving in the bound on competitors at side $W$.
The joint step adds these savings over populations before taking their
minimum.
\begin{theorem}[Heterogeneous joint step]\label{thm:joint-step}
Let $B_N$ be the restriction of $\bigotimes_r F_r^{\otimes m_r}$
by the inherited masks just specified, with the population data above. Set
\begin{equation}\label{eq:joint-totals}
A_{\rm amb}=\sum_{r\in\mathcal R}c_rH(p_r),\qquad
C_W=\sum_{r\in\mathcal R}c_rC_{r,W},\qquad
E=\min\{C_X,C_Y,C_Z\}.
\end{equation}
If $E>0$, then for every $\varepsilon>0$ one can choose positive
output widths, as small as desired, such that for all sufficiently
large $N$ divisible by the fixed type denominators, a direct sum of
$\exp(o(N))$ independent copies of $B_N$ has a linear restriction
to at least $\lfloor\exp(N(E-\varepsilon))\rfloor$ independent
copies of $Q_N$.
The choices of populations, rational laws, positive widths, and
divisibility requirements precede the limit $N\to\infty$.
In particular, the assertion does not require common strand lengths.
\end{theorem}
We first bound hash survival and assignment collisions. The sequential
$X,Y,Z$ tests then put surviving monomials in a direct sum of variable
restrictions of the ideal outputs. Section~\ref{sec:recovery} completes
the proof by bounding the missing fraction on every full-variable orbit
and restoring the ideal outputs from $\exp(o(N))$ input copies.
\subsection{Entropy and a common modular hash}
For a fixed alphabet $\mathcal A$, the number of words of type $p$ is
\begin{equation}\label{eq:type-count}
\frac{m!}{\prod_a(mp(a))!}
=\exp\bigl(mH(p)+O(\log(m+2))\bigr).
\end{equation}
Indeed, comparing the sum $\sum_{j=1}^n\log j$ with its integral
gives $\log(n!)=n\log n-n+O(\log(n+2))$.
There are at most $(m+1)^{|\mathcal A|}$ possible types.
Both bounds are uniform on each fixed alphabet, including types
with zero coordinates.
One convenient way to meet the entropy hypothesis is to use positive
weights $a_i,b_j,c_k$ and set
\[
p(i,j,k)=Z^{-1}a_i b_j c_k\quad ((i,j,k)\in\Omega_r).
\]
For any competing law $q$ with the same marginals,
$-\sum q\log p=-\sum p\log p=H(p)$, because $\log p$ is a sum
of three one-coordinate functions and a constant. Further,
\[
\sum_{q(u)>0}q(u)\log\frac{p(u)}{q(u)}
\le \sum_{q(u)>0}(p(u)-q(u))\le0,
\]
by $\log t\le t-1$. Thus $H(q)\le H(p)$.
Positive rational weights give rational laws with this same property.
When the marginals specify a unique law, maximality also holds,
including boundary laws with zero probabilities.
First keep, on each side, just the coarse sequences having marginal
type $p_{r,W}$ in every population. Call a triple satisfying these
three filters and the support conditions \emph{ambient}. The total
number of target triples is
\begin{equation}\label{eq:target-count}
|\mathcal T_N|=\exp\bigl(NA_{\rm amb}+O(\log N)\bigr).
\end{equation}
For a fixed $X$ coarse sequence, each possible ambient joint type
$q_r$ has the prescribed marginals. Its number of completions in
population $r$ is
\[
\frac{\prod_i(mp_{r,X}(i))!}{\prod_u(mq_r(u))!}
=\exp\bigl(m(H(q_r)-H(p_{r,X}))+O(\log N)\bigr).
\]
Summing over the polynomially many types and using maximality yields
the degree bound
\begin{equation}\label{eq:ambient-x-degree}
\#\{\text{ambient triples at a fixed $X$ block}\}
\le \exp\bigl(N(A_{\rm amb}-C_X)+O(\log N)\bigr).
\end{equation}
Here and below the coarse counts ignore all fine masks, thereby
bounding every interaction that could actually occur.
Fix a small slack $\delta>0$. Since $C_X\le A_{\rm amb}$ and
$E\le C_X$, choose a power $M=37^k$ with
\begin{equation}\label{eq:hash-size}
\log M=N(A_{\rm amb}-E+\delta)+O(1).
\end{equation}
There is a set $U\subset\mathbb Z/M\mathbb Z$ with
\begin{equation}\label{eq:ap-free-size}
\log|U|=\log M-O(\sqrt{\log M})
\end{equation}
and no nonconstant three-term arithmetic progression. Here is a
version of Behrend's construction~\cite{Behrend1946} that also rules
out modular wraparound. Put
$h=\lfloor\sqrt{\log M}\rfloor$, $b=\lfloor M^{1/h}/2\rfloor$,
and encode $d\in\{0,\ldots,b-1\}^h$ as
$n(d)=\sum_{j=0}^{h-1}d_j(2b)^j$. Choose a largest class with
fixed $\sum_jd_j^2$. Every encoded integer is less than
$(2b)^h/2\le M/2$, so a modular progression among them is an
integer progression. In $n(d)+n(e)=2n(f)$ all digit sums are at
most $2b-2$, so there is no carry and $d+e=2f$.
Equal squared norms now give
$\|d-e\|^2=2\|d\|^2+2\|e\|^2-\|d+e\|^2=0$.
There are at most $1+h(b-1)^2$ norm classes, whence
$|U|\ge b^h/(1+hb^2)$. The inequalities
$b\ge M^{1/h}/4$ and $b\le M^{1/h}$ imply
\eqref{eq:ap-free-size}.
Concatenate all $d=\sum_r m_r$ strand positions to form coarse words
$I,J,K$.
Let $S$ have entry $s_r$ at positions in population $r$. Every
ambient triple satisfies $I+J+K=S$, even though the entries of $S$
can vary. Choose independent uniform offsets $a,b'$ and a uniform
vector $v$ over $\mathbb Z/M\mathbb Z$, and set
\begin{equation}\label{eq:joint-hashes}
x(I)=a+\langle v,I\rangle,\quad
y(J)=b'+\langle v,J\rangle,\quad
z(K)=\frac{a+b'+\langle v,S-K\rangle}{2}.
\end{equation}
Division by $2$ is defined since $M$ is odd. Keep only coarse blocks
whose hashes lie in $U$. Since $x+y=2z$, a surviving triple has
$x=y=z$.
For a fixed ambient triple $e$, let $S_e$ be its full hash-survival
event. For every $v$ and $t\in U$ there is exactly one offset pair
giving $x=y=z=t$, so
\begin{equation}\label{eq:hash-survival}
\Pr(S_e)=h_M:=\frac{|U|}{M^2}.
\end{equation}
Conditional on $S_e$, $(v,t)$ is uniform on
$(\mathbb Z/M\mathbb Z)^d\times U$. A second triple with
differences $(\Delta I,\Delta J,\Delta K)$ has hashes
\[
t+\langle v,\Delta I\rangle,\quad
t+\langle v,\Delta J\rangle,\quad
t-\tfrac12\langle v,\Delta K\rangle.
\]
If it shares $X$ with $e$, survival is equivalent to
$\langle v,\Delta J\rangle=0$; if it shares $Y$ or $Z$, it is
equivalent to $\langle v,\Delta I\rangle=0$. In the shared-$Z$
case use $\Delta J=-\Delta I$. Distinct triples cannot share two
blocks, by their common sum $S$. Thus the tested difference vector
has a nonzero coordinate of absolute value at most $16$, which is
a unit modulo $37^k$. Conditioning on the other coordinates of
$v$ shows, in all three cases, that
\begin{equation}\label{eq:hash-collision}
\Pr(S_{e'}\mid S_e)=\frac1M
\quad\text{for distinct triples sharing a block}.
\end{equation}
No further hash-dependent event is included in this conditioning.
\subsection{The finite compatibility count}
In a sharing population, prefilter side $W\in\{Y,Z\}$ by requiring
its empirical ordered-pair law to be within width $\eta$ of $D_W$.
A fine side variable is \emph{compatible} with a target triple if
its statistic type is within width $\chi$ of the prescribed law
in every designated shape class, separately on the two halves.
On the left these are the positions with $u\in\mathcal I_W$, using
$\nu_{u,W}$; on the right they are the positions with
$g-u\in\mathcal I_W$, using $\nu_{g-u,W}$.
No individual compatibility test is imposed on a residual group,
including a residual group with one shape.
The positions of each tested class are read from the target triple.
Ordinary populations impose no compatibility test. A variable for
the whole product is compatible exactly when it is compatible in
every population.
\begin{lemma}[Compatibility incidence count]\label{lem:compatibility-count}
For fixed population data, there is a function
$\xi(\eta,\chi)\to0$ as $(\eta,\chi)\to(0,0)$ such that any
fine side variable passing the pair filters is compatible with at most
\begin{equation}\label{eq:compatibility-degree}
\exp\bigl(N(A_{\rm amb}-C_W+\xi(\eta,\chi))
+O(\log N)\bigr),\qquad W\in\{Y,Z\},
\end{equation}
target triples containing its coarse block, before hashing.
The estimate is uniform in the variable and the target arrangement.
\end{lemma}
\begin{proof}
Consider first one sharing population of size $m$, and fix the
coarse $W$ word $k=(k_1,\ldots,k_m)$. If $k$ does not have type
$p_W$, no target contains it and the bound is immediate. Assume
henceforth that it has this type, and let $\mathcal C$ be the
set of shape words $(u_1,\ldots,u_m)$ of type $p$ with $u_{j,W}=k_j$.
Such a word determines a complete coarse triple. If the given fine
variable has pair-statistic word $z=((a_j,b_j))_{j=1}^m$ and empirical
law $D'$, let $\mathcal B$ be its orbit under
\[
\Gamma_k=\prod_i\operatorname{Sym}\{j:k_j=i\}.
\]
This group acts transitively on $\mathcal B$ by definition and on
$\mathcal C$ because all shape counts within every coarse class are
fixed. Compatibility is unchanged by applying the same permutation
to a candidate and a statistic word. Hence its incidence degrees
$a=\#\{z\in\mathcal B:z\text{ compatible with }c\}$ and
$b=\#\{c\in\mathcal C:z\text{ compatible with }c\}$ do not depend
on $c$ and $z$, respectively. Counting incidences gives the exact
finite identity
\begin{equation}\label{eq:incidence-identity}
|\mathcal C|a=|\mathcal B|b.
\end{equation}
Since the statistic determines the half weight,
\begin{align*}
|\mathcal C|&=\frac{\prod_i(mp_W(i))!}{\prod_u(mp(u))!},
&\log|\mathcal C|&=m(H(p)-H(p_W))+O(\log(m+2)),\\
|\mathcal B|&=\frac{\prod_i(mp_W(i))!}{\prod_{a,b}(mD'(a,b))!},
&\log|\mathcal B|&=m(H(D')-H(p_W))+O(\log(m+2)).
\end{align*}
To bound $a$, now fix a candidate $c\in\mathcal C$. This fixes the
position set of every left and right compatibility group. On the
left, compatibility specifies the law within each designated group
to accuracy $\chi$. The row sums of $D'$ give the total count of
each statistic among positions with each coarse value, since
$\rho_W(a_j)=k_j$. Subtracting the designated-group counts leaves, in the
remaining group with coarse value $i$, the law
\[
\frac{\sum_{u\in G}p(u)\nu_{u,W}}{p(G)}
\]
up to an error tending uniformly to zero with $\eta$ and $\chi$.
More explicitly, each coordinate error is at most
$(|\mathcal A_{r,W}|\eta+\chi)/p(G)$: summing a row of $D'$
costs at most $|\mathcal A_{r,W}|\eta$, and the weighted errors
of the subtracted designated laws total at most $\chi$.
Only fixed positive numbers $p(G)$ are divided by. A product of
multinomial counts over these fixed position sets, and then a sum
over polynomially many types, bounds the number of left-statistic
assignments by $\exp(m(J_W+o_{\eta,\chi}(1))+O(\log(m+2)))$.
For the right half, use the column sums of $D'$. Its coarse value
is $g_W-k_j$, so those sums determine precisely the analogous
aggregate counts. The right half-shape distribution is
$p(g-u)=p(u)$, giving the same entropy $J_W$, with the actual right
prescription $\nu_{g-u,W}$. Count the two halves independently;
discarding the requirement that they reassemble the exact pair law
$D'$ can only enlarge the count. We obtain
\[
a\le\exp\bigl(m(2J_W+o_{\eta,\chi}(1))+O(\log(m+2))\bigr).
\]
There is no factor for choosing group locations: those locations
were fixed with $c$. By \eqref{eq:incidence-identity} and uniform
continuity of entropy on a finite simplex,
\[
b\le\exp\bigl(m(H(p)-H(D_W)+2J_W+o_{\eta,\chi}(1))
+O(\log(m+2))\bigr).
\]
For an ordinary population all candidates are compatible, and their
number is $\exp(m(H(p)-H(p_W))+O(\log(m+2)))$ directly. The
candidate sets, permutation groups, and compatibility conditions
factor over populations. Multiplying their bounds proves
\eqref{eq:compatibility-degree}.
\end{proof}
\subsection{Sequential assignment by variable deletion}
Choose $\eta,\chi>0$ sufficiently small that the error in
Lemma~\ref{lem:compatibility-count} is below $\delta/4$. Next
choose output widths $\theta>0$ smaller than $\chi$ and small
enough for the positive margins required by all inherited and pair
tests. Complementary prescribed laws ensure that usefulness of
one side transfers to the compatibility window on a matching side.
Every choice here is fixed before $N$ grows.
First delete an $X$ coarse block unless it belongs to exactly one
ambient hash survivor and that survivor is a target triple. Call
the retained triples \emph{eligible}. Freeze this list for all
subsequent tests. By \eqref{eq:ambient-x-degree},
\eqref{eq:hash-size}, and \eqref{eq:hash-collision}, a target triple
$e$ fails this test, conditional only on $S_e$, with probability at
most $\exp(-\delta N+O(\log N))$. Each retained $X$ block now has
an unambiguous assignment. In that block retain only the fine
variables useful for its assigned triple, that is, those satisfying
its output windows.
On $Y$, apply its pair filters and delete every fine variable
having other than exactly one compatible eligible triple containing
its coarse block. Assign it to that triple and impose usefulness
for that assignment. Apply the same procedure to $Z$, using
the designated classes $\mathcal I_Z$. Include all inherited masks
as side-variable deletions; their application does not change the frozen eligible
list or the definitions of the compatible lists.
We verify that these operations produce a direct sum, rather than
merely a list of proposed components. Take an actual monomial
surviving every deletion, and let $e$ be its ambient coarse triple.
Its $X$ block survived, so $e$ is that block's unique eligible
triple and its $X$ variable is useful for $e$. In every sharing
half with $u_Z=0$, the $Y$ statistics are complementary to the
$X$ statistics. Thus the actual $Y$ variable is compatible with
$e$; deterministic sides satisfy their point-mass tests as well.
The $Y$ uniqueness test therefore assigns this variable to $e$.
Its usefulness is now known for the actual triple.
For $Z$, a half with $u_Y=0$ transfers the required statistics from
$X$. A half with $u_X=0$ and $u_Y>0$ transfers them from the
already useful $Y$ variable. With both $u_X=u_Y=0$, the remaining
variable is forced. These cases prove compatibility with $e$ on
every designated shape class in $\mathcal I_Z$. Its uniqueness test then
assigns the actual $Z$ variable to $e$ as well. Ordinary
populations add no compatibility conditions in either argument.
All three variables of every retained monomial therefore have the
same assignment.
Different assignments share no retained fine variable on any side.
Within assignment $e$, usefulness restricts precisely to $Q_e$;
all other tests delete individual variables of $Q_e$. Consequently
the surviving tensor is a direct sum of tensors $Q_e^{\rm hole}$,
each obtained from its ideal $Q_e$ solely by variable deletion.
This statement concerns complete variables of the population
product; sharing a local coordinate factor between two complete
variables does not identify those variables.
Here is the probability estimate needed to repair these holes.
For a fixed $e$ and a fixed variable $v$ of $Q_e$ passing all its
deterministic inherited and pair masks, own-triple compatibility
and usefulness hold. Let $R_{e,v}$ be the union of the $X$
eligibility-failure event and, when $v$ is on side $Y$ or $Z$,
the events that another compatible target triple sharing its
coarse block survives the hash. Every random deletion of $v$ is
contained in $R_{e,v}$. Bound those competitors among
\emph{all} target triples before eligibility and other deletions.
Lemma~\ref{lem:compatibility-count} and
\eqref{eq:hash-collision} then give, for some constant $c>0$,
\begin{equation}\label{eq:joint-conditional-loss}
\Pr(R_{e,v}\mid S_e)
\le \exp(-cN),
\end{equation}
uniformly in $e$ and the passing variable, for all large $N$.
Indeed, the exponent for side $W$ is at most
$N(E-C_W-\delta+\xi)+O(\log N)$ and $C_W\ge E$.
This estimate is conditioned only on $S_e$, never on eligibility
or on passing a hash-dependent test.
For reference in the recovery argument, let $G_e$ act by independent
position permutations in every ideal child class $(r,u,\text{half})$,
simultaneously on all three sides. In ordinary whole-strand blocks
use their position permutations; for a factorized ordinary block
one may also permute its child factors independently. These are
automorphisms of $Q_e$. The full variable alphabets in its finitely
many classes are fixed, so $G_e$ has only polynomially many orbits
of variables. Lemma~\ref{lem:orbit-masks} supplies the uniform
deterministic mask bound on these orbits. The completion of
Theorem~\ref{thm:joint-step} in Section~\ref{sec:recovery} combines
that bound with \eqref{eq:joint-conditional-loss}, selects
exponentially many good assignments using
\eqref{eq:target-count} and \eqref{eq:hash-survival}, and applies
Lemma~\ref{lem:hole-repair} to reconstruct their ideal outputs.
==== END Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/joint-extraction.tex ====
==== BEGIN Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/leaf-volumes.tex ====
\section{Terminal dimensions and the rank comparison}
\label{sec:leaf-volumes}
The terminal factors have either a zero coordinate or length one.
Their dimensions can be counted directly, including the restrictions on
their prescribed statistics. We first show that the completed ideal
outputs restrict to one common oriented matrix tensor. We then combine
its volume with the finite schedule's yield and compare ranks.
Write
\[
c_\ell(j)=[x^j](1+5x+x^2)^\ell
\]
for the number of labeled weight words of length $\ell$ and weight sum $j$.
With the amounts and laws of Section~\ref{sec:stagger}, define
\begin{align}
S_0&=\sum_{\min g=0}A_g\log c_8(\max g),
\label{eq:leaf-s0}\\
S_1&=\sum_{\min t=0}m_t
\left(H(z_t)+\sum_{i,j}z_t(i,j)\log(D_iD_j)\right),
\label{eq:leaf-s1}\\
S_2&=\sum_{\min t>0}\ \sum_{u\leq t,\,\sum_i u_i=4}
m_{t,u}R_{t,u},
\label{eq:leaf-s2}\\
S_*&=S_0+S_1+S_2,\nonumber
\end{align}
where $g$ is sorted, $t$ and $u$ retain their coordinate labels, and
\begin{equation}
R_{t,u}=\begin{cases}
0,&\max u=4,\\
\log 10,&\max u=3,\\
h_b(d_{t,u})+2(1-d_{t,u})\log 5,
&\max u=2,\ \min u=0,\\
(2-d_{t,u})\log 5,&\min u>0.
\end{cases}
\label{eq:leaf-rates}
\end{equation}
In these sums, infeasible or zero-mass populations are omitted.
\begin{proposition}[Leaf volumes and common dimensions]
\label{prop:leaf-volume}
Fix a finite number $K$ of lots and rational stage laws satisfying the
prescriptions of Section~\ref{sec:stagger}. Use fixed rational
subdivisions retaining each history class's prescribed laws, as in
\eqref{eq:subdivision-restriction}; exact capacity balance is not required
for this volume count.
For all sufficiently divisible $N$, every completed ideal output in the
staggered construction has a restriction to the same oriented matrix
tensor $\langle a_N,b_N,c_N\rangle$, with
\begin{equation}
\log(a_Nb_Nc_N)\geq KN S_*-O_K(\log(N+2)).
\label{eq:leaf-volume-bound}
\end{equation}
The implied constant may depend on the fixed laws and subdivisions.
For limiting real data, the corresponding volume rate can approach
$S_*$ arbitrarily closely by consistent rational approximation.
\end{proposition}
\begin{proof}
We first count one terminal population. When a shape has a zero on side
$X$, that side has a unique weight word and a unique variable. Every
variable on $Y$ has exactly one partner on $Z$: complement each weight
$0\leftrightarrow2$ and retain the label at each weight $1$.
Consequently a set of $M$ such matched pairs gives
$\langle1,1,M\rangle$. A zero on $Y$ gives
$\langle M,1,1\rangle$, and a zero on $Z$ gives
$\langle1,M,1\rangle$. These orientations follow from the convention
$x_{ij}y_{jk}z_{ki}$; in every case the volume is $M$.
If two coordinates are zero, $M=1$.
For an unrestricted length-eight leaf, the generating function above
counts the choices on an axis of maximum weight. Complementation is a
bijection to the other axis, so the volume is $c_8(\max g)$.
Their total contribution per initial strand is therefore
\eqref{eq:leaf-s0}.
Here is the exact count needed for the restricted leaves. Suppose the
statistic on the chosen nonzero side has values $\sigma$ with
multiplicities $b_\sigma$, and a population of $m$ strands is restricted
to an exact statistic type $\theta$ with integer counts
$n_\sigma=m\theta_\sigma$. The number of surviving matching words is
\begin{equation}
M(m,\theta)=\frac{m!}{\prod_\sigma n_\sigma!}
\prod_\sigma b_\sigma^{n_\sigma}.
\label{eq:exact-leaf-count}
\end{equation}
Indeed, first choose the positions of each statistic and then its
independent labeled realization at each position. The other side is
uniquely determined. Prescribing the pushforward type under
complementation on that side retains all these pairs. For a fixed
alphabet the multinomial estimate gives
\begin{equation}
\log M(m,\theta)
=m\left(H(\theta)+\sum_\sigma\theta_\sigma\log b_\sigma\right)
+O(\log(m+2)).
\label{eq:leaf-type-rate}
\end{equation}
Zero type entries cause no difficulty, with $0!=1$.
At a zero-coordinate length-four leaf, the statistic is the ordered
pair $(i,j)$ of the two length-two statistics. Its multiplicity is
$D_iD_j$, and its type is $z_t$. Equation~\eqref{eq:leaf-type-rate}
therefore gives precisely the summand in \eqref{eq:leaf-s1}.
Within a length-two statistic, $11$ has $5^2=25$ labelings and $02$ has
two orders; these choices have already been included in $D$.
The two halves remain ordered. Thus, when $z_t$ is specified by
weights on $i\leq j$, an off-diagonal weight occurs twice in its
normalizing sum, once for each ordered pair. There is no further
multiplicity factor beyond $D_iD_j$ in
\eqref{eq:exact-leaf-count}.
The complement involution $\kappa$ satisfies
$D_{\kappa(i)}=D_i$ and sends $(i,j)$ to
$(\kappa(i),\kappa(j))$. The prescription on the second nonzero axis
is exactly this pushforward of $z_t$. The same matching count applies
when the two nonzero coordinates tie for the maximum: choosing the
first maximum only chooses which of the two matched words is counted.
No invariance of $z_t$ under complementation is needed.
The nonnegative shapes of size four have sorted forms
$(0,0,4)$, $(0,1,3)$, $(0,2,2)$, and $(1,1,2)$.
These are the four disjoint cases of \eqref{eq:leaf-rates}.
The first has volume one. The second has ten matched words, since
the weight-three side has either order of weights $1,2$ and five
choices for the weight-one label.
For the third, write $d=d_{t,u}$. In $m$ strands, impose the exact
type with $m(1-d)$ statistics $11$ and $md$ statistics $02$.
Its matching count is
\[
\binom{m}{md}25^{m(1-d)}2^{md}.
\]
Its logarithmic rate is
$H(1-d,d)+2(1-d)\log5+d\log2$, the third case of
\eqref{eq:leaf-rates}. Complementation fixes both of these unordered
statistics, so the same exact type is allowed on both nonzero sides.
For the positive case, consider first $u=(1,1,2)$ on the physical sides
$(X,Y,Z)$, so $Z$ is distinguished, and again put $d=d_{t,u}$.
The four Stage C choices are
\[
\begin{array}{c|c|c}
\text{left and right shapes}&\text{probability}&
\text{product of the two matrix tensors}\\ \hline
(0,0,2),\ (1,1,0)&d/2&\langle1,5,1\rangle\\
(1,1,0),\ (0,0,2)&d/2&\langle1,5,1\rangle\\
(0,1,1),\ (1,0,1)&(1-d)/2&\langle5,1,5\rangle\\
(1,0,1),\ (0,1,1)&(1-d)/2&\langle5,1,5\rangle.
\end{array}
\]
Every selected exact coarse type therefore produces, from $m$ strands,
the oriented tensor
\begin{equation}
\left\langle5^{m(1-d)},\,5^{md},\,5^{m(1-d)}\right\rangle.
\label{eq:positive-leaf-dimensions}
\end{equation}
Its volume is $5^{m(2-d)}$, proving the final case of
\eqref{eq:leaf-rates}. This is the dimension of one output with fixed
coarse blocks; the choices of coarse blocks have already contributed
to the extraction yield. Permuting the physical sides gives the other
orientations; the volume remains the same. This formula includes
$d=0$ and $d=1$ whenever they are allowed by the chosen laws.
Both children must be counted in the volume sum. For each positive
parent $t$, their contribution is
\[
m_t\sum_u p_t(u)\bigl(R_{t,u}+R_{t,t-u}\bigr)
=2m_t\sum_u p_t(u)R_{t,u}
=\sum_u m_{t,u}R_{t,u}.
\]
The equality changes variables $u\mapsto t-u$ in the second sum and
uses only $p_t(u)=p_t(t-u)$. It does not identify
$d_{t,u}$ with $d_{t,t-u}$. The analogous calculation with $P_g$
gives the amounts $m_t$ after Stage A. Thus
\eqref{eq:leaf-s0}--\eqref{eq:leaf-s2} count every terminal factor
once.
Finally we verify that these counts provide common oriented dimensions,
as required by Lemma~\ref{lem:direct-sum}. Keep separate every finite
class specified by its lot, full ancestry, left or right half,
coordinate-label placement on the physical sides, and subdivision for
a priority choice. Exact coarse types fix the number of factors in
each such class in every output. A simultaneous relabeling of
positions on all three sides takes each class to the same canonical
set of positions. Its ideal tensor and its prescribed type windows
are consequently the same in every output. The recovery argument
restores these ideal tensors before the terminal restrictions are
made.
Choose once, in each zero-coordinate class with a statistic
prescription, the exact matching type used in
\eqref{eq:exact-leaf-count}; use the same choice in every output.
For rational data and divisible $N$, this type equals the
prescribed law and lies in every positive tolerance window. Each
class then has the same integer matching dimension and the same zero
physical side; unrestricted classes already have fixed matching
dimensions. At positive length-two classes the exact Stage C
counts give the same oriented dimensions in
\eqref{eq:positive-leaf-dimensions} or its prescribed side permutation.
Multiplying these fixed dimensions over all classes gives one common
triple $(a_N,b_N,c_N)$, with each dimension fixed separately.
The parts of each subdivision retain the same prescribed laws, so
their leading logarithmic contributions add to that of the original
class. Allocating these parts among extraction priorities therefore
does not change $S_*$.
There are finitely many classes for fixed $K$. Summing
\eqref{eq:leaf-type-rate} over them contributes only
$O_K(\log(N+2))$ to the logarithm, while the leading term is
$KN(S_0+S_1+S_2)$. This proves
\eqref{eq:leaf-volume-bound}. For real limiting laws, choose
consistent rational laws first and then a divisible $N$.
The entropy function is continuous on each finite probability simplex,
so the resulting normalized volume rates tend to $S_*$.
\end{proof}
\subsection{Finite extraction and the rank comparison}
\label{sec:staggered-assembly}
We now combine the schedule of Section~\ref{sec:stagger} with the
terminal dimensions just established. The finite statement records
both the boundary deficit and the order in which the data are fixed.
\begin{proposition}[Finite staggered yield]\label{prop:staggered-yield}
Assume the prescriptions of Section~\ref{sec:stagger}, the balance
conditions \eqref{eq:balance-feasibility}, and positive entries of
$L_A,L_B,L_C$. Let $S_*=S_0+S_1+S_2$ be the terminal rate defined above.
For every fixed integer $K\geq2$ and every $\epsilon>0$, suitable
fixed rational approximations, part allocations, and tolerances give,
for all sufficiently large divisible $N$, a restriction of
$\exp(o_K(N))$ copies of $\CW_5^{\otimes8KN}$ to $s_N$ identical
matrix tensors of volume $V_N$, where
\begin{equation}\label{eq:finite-stagger-yield}
\frac{\log s_N}{N}\geq K(H_0+C_*)-\beta-\epsilon,
\qquad
\frac{\log V_N}{N}\geq KS_*-\epsilon.
\end{equation}
\end{proposition}
\begin{proof}
Use the initial extractions and the $K+2$-tick schedule
\eqref{eq:finite-schedule}. Their total limiting logarithmic yield,
divided by $N$, is $K(H_0+C_*)-\beta$: each of the $K-2$ full ticks
contributes $C_*$ and the four boundaries contribute the positive
minima in \eqref{eq:boundary-deficit}. We show that fixed rational
data and a finite composition of joint steps attain these rates to
within the stated losses.
Fix $K$ before making any asymptotic choices.
Choose rational product weights for the initial, A, and B laws,
preserving their symmetries, and rational $d$ and $z$ data. Define
$v$ and $V$ from these same choices by their formulas; do not
approximate an inherited mixture separately. Choose rational
allocations approaching \eqref{eq:balance-fractions}. For these
approximations the full-tick capacities approach $C_*/6$, which is
all the yield bound requires. By continuity, the approximations may
also be chosen to keep every boundary minimum strictly positive.
There are finitely many histories,
and all positive history masses are now fixed rational multiples
of $N$. Omit zero classes and make $N$ divisible by every required
denominator. Choose the finitely many tolerances successively
smaller toward the leaves, so all inherited masks and subdivisions
meet Theorem~\ref{thm:joint-step}.
There are $K$ initial operations and at most $6(K+2)$ subsequent
joint operations. Lemma~\ref{lem:replication} pulls their finitely
many replication factors back to $\exp(o_K(N))$ copies of the
original source. This cost is per operation, including all its
already disjoint summands; it is not repeated multiplicatively for
each summand. Entropy continuity makes the total approximation and
tolerance loss less than $\epsilon$, for this fixed $K$, before
$N$ tends to infinity. Integer rounding and polynomial type-class
factors contribute $o_K(N)$.
Proposition~\ref{prop:leaf-volume} applies to these fixed rational
laws and subdivisions: the schedule keeps all histories distinct, and
repair restores their ideal windows before any terminal restriction.
Its common exact terminal types and exact Stage C counts give one
oriented matrix tensor in every final summand, with volume rate
approaching $KS_*$. Thus the approximation and extraction losses can
be chosen to satisfy both bounds in \eqref{eq:finite-stagger-yield}.
\end{proof}
Lemma~\ref{lem:cw-rank} bounds the rank of the replicated source by
\[
\exp(o_K(N))\,7^{8KN}\binom{24KN+2}{2}.
\]
Apply Lemma~\ref{lem:direct-sum} to the identical outputs of
Proposition~\ref{prop:staggered-yield}, divide its logarithm by $KN$,
and first let divisible $N\to\infty$. For fixed $K$ let the
approximation and tolerance losses tend to zero. The result is
\[
H_0+C_*-\frac{\beta}{K}+\frac{w}{3}S_*\leq8\log7.
\]
Letting $K\to\infty$ last gives the promised constraint
\begin{equation}\label{eq:rank-constraint}
\boxed{\displaystyle H_0+C_*+\frac{w}{3}S_*\leq8\log7.}
\end{equation}
Only fixed finite schedules were used; no estimate uniform in a
simultaneously growing $K$ is required.
==== END Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/leaf-volumes.tex ====
==== BEGIN Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/parameter-tables.tex ====
\section{Exact integer parameter tables}\label{app:parameter-tables}
These five arrays, with the traversals in Section~\ref{sec:parameters},
specify all rational distributions used in the construction. Every integer is
exact; line breaks carry no meaning. Array indices start at zero.
\paragraph{Initial shape weights: 17 entries ($a$).}
{\footnotesize
\begin{verbatim}
-55839 -36137 -17449 -1780 11561 22640 31188 36731 38593 35898
29051 18387 3823 -14569 -39776 -38598 -23708
\end{verbatim}
}
\paragraph{Stage A split weights: 118 entries ($P$).}
{\footnotesize
\begin{verbatim}
-3070 295 -20546 -1514 -38211 -9654 -7530 -2765 -55230 -16412
-14246 -5912 -78106 -32809 -7009 -26324 -13519 -3592 -96458 -47439
-16217 -46871 -25058 -9643 -95643 -62269 -28725 -8576 -2535 -2550
-34711 -7207 -3270 -6376 -53221 -15352 -3477 -14828 -4187 -74924
-32439 -7231 -3578 -24599 -8700 -92989 -46655 -16926 -3517 -42976
-20283 -5132 -107049 -63201 -31013 -9730 -3705 -67421 -35684 -13735
-68829 -36752 -13993 -7658 -7586 -76746 -33496 -7329 -7447 -17336
-4721 -96770 -49297 -17874 -7143 -30044 -10107 -116558 -68325 -33467
-10424 -7476 -51341 -24711 -5530 -76548 -41988 -15608 -17266 -4357
-17106 -4343 -120770 -70820 -34294 -10580 -16819 -4315 -32943 -9992
-83616 -44202 -16154 -17098 -4371 -56609 -25990 -5564 -56356 -25900
-5561 -33052 -9918 -32951 -9906 -57255 -26128 -5560
\end{verbatim}
}
\paragraph{Stage B split weights: 54 entries ($p$).}
{\footnotesize
\begin{verbatim}
-39594 -5561 -55254 -15178 -62331 -19672 -54917 -18539 -16455 -32184
-5716 -11688 -5527 -53009 -6669 -6669 -64938 -20286 -6616 -26336
-26429 -6696 -60888 -19760 -6690 -5724 -32216 -15829 -58477 -18987
-26339 -6619 -26393 -26340 -26359 -6620 -16239 -55176 -18587 -55107
-18571 -16272 -60868 -19755 -6696 -6692 -55133 -18580 -16247 -32128
-5727 -32138 -5725 -122
\end{verbatim}
}
\paragraph{Binary parameters: 75 entries ($d$).}
{\footnotesize
\begin{verbatim}
63 97655 0 42132 92966 1204 42148 95604 41743 3057
109933 42092 3747 41991 1 100622 42166 103562 9039 42157
103577 42165 63582 110082 4584 42175 104091 38838 102383 104793
42126 11814 63338 42165 104864 3587 42166 110086 2207 94768
42166 104185 4735 38889 110065 42166 102372 104314 38956 4876
102395 42166 110068 2953 42166 96000 41863 95723 3031 63321
42040 42174 104662 11860 104902 42189 2967 96042 42047 109872
3986 42200 3834 110106 60257
\end{verbatim}
}
\paragraph{Terminal length-four weights: 36 entries ($z$).}
{\footnotesize
\begin{verbatim}
-11037 -36170 -4779 23107 -12831 29263 45052 22289 -6216 23895
-14326 -40670 -9623 -34674 -12708 -36610 -2174 21564 -5587 22521
-9766 28961 43809 22299 -12216 28778 44147 22176 -7811 21870
-6053 23786 -166 94 -52 17
\end{verbatim}
}
==== END Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/parameter-tables.tex ====
==== BEGIN Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/parameters.tex ====
\section{Exact parameters and numerical certification}\label{sec:parameters}
We now evaluate the logarithmic yield rate $H_0+C_*$ and terminal
logarithmic volume rate $S_*$ for one choice of distributions.
The same calculation verifies positive entries
of the stage-capacity vectors, the balance conditions, and $S_*>0$, then
bounds the exponent ratio obtained from \eqref{eq:rank-constraint}.
Five integer arrays in
Appendix~\ref{app:parameter-tables}, followed by rational operations,
specify this choice; no optimization procedure is part of the certificate.
For an integer argument $n$, define the rational weight
\begin{equation}\label{eq:rational-weight}
F(n)=\left(\sum_{j=0}^{16}\frac{(n/640000)^j}{j!}\right)^{64}.
\end{equation}
The initial weights, the two split-weight arrays, and the terminal weights
use 223 distinct arguments of $F$, including the implicit zero, all between
$-120770$ and $45052$. The binary-parameter array instead supplies the
fractions $n/10^6$ and is not passed to $F$. For the 223 weight arguments,
exact rational evaluation gives
\begin{equation}\label{eq:weight-bounds}
2^{-23}<F(n)<2^{23}.
\end{equation}
The truncated series is positive directly as well: for nonnegative arguments
all terms are nonnegative, and for negative arguments the even Taylor partial
sum lies above the positive exponential. This observation concerns ordinary
real arithmetic used to choose probabilities, and imposes no restriction on
the field of the tensor construction.
\paragraph{Complete decoding rules.}
All shapes and pairs below are traversed in increasing lexicographic order,
and coordinate labels and array indices start at zero. For a shape $s$ of
size $2\ell$, write
\[
\mathcal B(s)=\{b\in\mathbb Z_{\ge0}^3:
b_0+b_1+b_2=\ell,\ b_i\le s_i\ (0\le i<3)\}.
\]
The arrays are consumed as follows.
\begin{enumerate}
\item The 17 entries $a_0,\ldots,a_{16}$ define the initial sorted law by
\[
A_g=\frac{\operatorname{mult}(g)\prod_{i=0}^2F(a_{g_i})}
{\sum_{h_0\le h_1\le h_2,\,\sum h_i=16}
\operatorname{mult}(h)\prod_{i=0}^2F(a_{h_i})},
\qquad
\operatorname{mult}(g)=\frac{3!}{\prod_j\bigl(\#\{i:g_i=j\}\bigr)!}.
\]
Thus the law on ordered shapes, before coalescing permutations, is a product
of three one-coordinate weights.
\item The 118 entries in the Stage A array are read over all positive sorted
$g$ of size 16. The 54 entries in the Stage B array are read over all positive
\emph{ordered} $t$ of size 8. At either parent $s$, set
$\ell=\frac12\sum_i s_i$. For coordinate $i=0,1,2$, with $k=s_i$, read one
integer $n_{s,i}(j)$ for each
\[
\max(0,k-\ell)\le j<\lfloor k/2\rfloor,
\qquad n_{s,i}(\lfloor k/2\rfloor)=0
\]
(the final zero consumes no entry). For $b\in\mathcal B(s)$ put
\[
w_s(b)=\prod_{i=0}^2F\bigl(n_{s,i}(\min(b_i,s_i-b_i))\bigr),
\qquad q_s(b)=\frac{w_s(b)}{\sum_{c\in\mathcal B(s)}w_s(c)}.
\]
Use $P_g=q_g$ at Stage A and $p_t=q_t$ at Stage B. Each is a positive
product-weight law and satisfies $q_s(b)=q_s(s-b)$ exactly.
\item Read the 75 entries of the fourth array over positive ordered $t$ of
size 8, and then over $u\in\mathcal B(t)$ with $\max u=2$. An entry $n$
means $d_{t,u}=n/10^6$. These include both the zero-coordinate $022$ shapes
and the positive $112$ shapes. The range is $0\le d_{t,u}\le0.110106$.
\item Read the 36 entries of the fifth array over all ordered $t$ of size 8
with a zero coordinate. For each $t$, list the pairs
\[
(i,j),\qquad 0\le i\le j\le5,\qquad r_i+r_j=\max t.
\]
Read an integer for each pair except the last, whose integer is zero.
Assign its $F$-weight to both $(i,j)$ and $(j,i)$ and normalize over
\emph{ordered} pairs to obtain $z_t$. Hence an off-diagonal weight occurs
twice in the denominator, while a diagonal weight occurs once. The
multiplicities $D_iD_j$ count words at the leaf and are not included in this
probability normalization.
\end{enumerate}
There are 30 sorted initial shapes, 21 positive sorted initial shapes,
21 positive ordered size-8 shapes, and 24 size-8 shapes with a zero.
All specified parents consume their entries, including parents whose eventual
amount is zero. For example, $(6,1,1)$ is included in the Stage B and binary
traversals. Skipping it, or a zero-amount parent in the $z$ traversal, would
change the meaning of the arrays. The exact types in this construction are
rational, because \eqref{eq:rational-weight} and every normalization are
rational. Only the balance fractions, and limiting tolerance choices, require
subsequent rational approximation.
The complement prescriptions in Section~\ref{sec:stagger} can be checked
without logarithms. On the six statistic slots, $\kappa$ is an involution
with $D_{\kappa(i)}=D_i$ and $r_{\kappa(i)}=4-r_i$. At a $022$ child it fixes
both slots 2 and 3, so the common parameter on the two nonzero sides gives
exactly matching laws. At zero-coordinate length-four shapes the other side
receives the pushforward of $z_t$ in both slots. These identities, including
all zero-axis cases, are checked with exact integers and fractions by the
archived verifier. Complementary \emph{child shapes} need not have equal
parameters: for instance
\[
d_{(1,3,4),(0,2,2)}=\frac{92966}{10^6},\qquad
d_{(1,3,4),(1,1,2)}=\frac{1204}{10^6}.
\]
They retain their separate prescriptions throughout the contractions.
\paragraph{Finite contractions.}
Here is an explicit evaluation rule for the conditional entropies appearing
in the capacities. For a finite nonnegative vector $x$, let
\[
\mathcal K(x)=\left(\sum_i x_i\right)\log\left(\sum_i x_i\right)
-\sum_i x_i\log x_i,
\qquad 0\log0=0.
\]
Thus $\mathcal K(x)=M H(x/M)$ when $M=\sum_i x_i>0$, and
$\mathcal K(0)=0$. Given a parent $s$, its split law $q$, a priority
$(X,Y,Z)$, and half-laws $Q_{b,W}$, form the ordered pair law
\[
D_W(i,j)=\sum_{b\in\mathcal B(s)}q(b)Q_{b,W}(i)Q_{s-b,W}(j).
\]
For $W=Y$, let $\mathcal I_W=\{b:b_Z=0\}$; for $W=Z$, let
$\mathcal I_W=\{b:b_Xb_Y=0\}$. The grouped entropy is exactly
\begin{equation}\label{eq:finite-group-contraction}
J_W=\sum_{b\in\mathcal I_W}q(b)\mathcal K(Q_{b,W})
+\sum_{k=0}^{s_W}
\mathcal K\left(\sum_{\substack{b\notin\mathcal I_W\\b_W=k}}
q(b)Q_{b,W}\right).
\end{equation}
The capacity vector is
\[
\left(\mathcal K\bigl((\sum_{b:b_X=k}q(b))_k\bigr),
\mathcal K(D_Y)-2J_Y,\mathcal K(D_Z)-2J_Z\right).
\]
At A substitute $(s,q,Q)=(g,P_g,V)$ and weight by $A_g$; at B substitute
$(t,p_t,v_{t,\cdot,\cdot})$ and weight by $m_t$, with the priorities already
specified. This rule uses each parent once. Child amounts and leaf volumes
use both halves as in Proposition~\ref{prop:leaf-volume}. Along with the
formulas for $H_0,B_*,T,S_0,S_1,S_2$, it specifies only finite additions,
multiplications, divisions, and logarithms of rational numbers.
\begin{table}[htbp]
\centering
\small
\begin{tabular}{c r r r}
\hline
Partial capacity & position 0 & position 1 & position 2\\\hline
A: $\min g=1$ & .010739192 & .016912163 & .016213531\\
A: $\min g=2$ & .081941050 & .088150511 & .082591626\\
A: $\min g=3$ & .292033029 & .283922596 & .257330639\\
A: $\min g=4$ & .547143900 & .527202791 & .487211274\\
A: $\min g=5$ & .247999127 & .248080948 & .237330883\\\hline
B: $116$ & .002770751 & .002770751 & .000443544\\
B: $125$ & .080908872 & .106275766 & .087117877\\
B: $134$ & .386356324 & .454421695 & .323639129\\
B: $224$ & .395346750 & .395353092 & .248930076\\
B: $233$ & .611253765 & .686627626 & .634289551\\\hline
\end{tabular}
\caption{Partial sums defining $L_A$ and $L_B$. A B row sums over all ordered
parents with that sorted shape. Each displayed entry has absolute error less
than $4.795\cdot10^{-10}$.}
\label{tab:capacities}
\end{table}
\begin{table}[htbp]
\centering
\begin{tabular}{c r@{\qquad}c r@{\qquad}c r}
\hline
$H_0$ & 1.841147374 & $B_*$ & 1.158066972 & $T$ & 2.345955063\\
$S_0$ & .031704071 & $S_1$ & .882362236 & $S_2$ & 11.680704014\\\hline
\end{tabular}
\caption{The other scalar contractions, each with absolute error less than
$3\cdot10^{-8}$.}
\label{tab:scalars}
\end{table}
\FloatBarrier
\begin{proposition}[Numerical certificate]\label{prop:numerical-certificate}
The exact parameters above satisfy every positivity and balance condition
used in Proposition~\ref{prop:staggered-yield}. All thirty partial capacity
entries in Table~\ref{tab:capacities} are positive. In particular, $S_*>0$,
$T\log2-B_*>0$, all entries of $L_A,L_B,L_C$ are positive, and the three
balance fractions are strictly positive. Moreover,
\begin{align}
5.612983956059236756&<H_0+C_*<5.612983956059236757,\label{eq:yield-certificate}\\
12.594770321594676362&<S_*<12.594770321594676363,\label{eq:volume-certificate}\\
2.371054886006745684
&<\frac{3(8\log7-H_0-C_*)}{S_*}
<2.371054886006745685.\label{eq:ratio-certificate}
\end{align}
With $\Omega=2.371056$, the strict comparison has the outward enclosure
\begin{equation}\label{eq:gap-certificate}
0.000004676829725968
< H_0+C_*+\frac{\Omega}{3}S_*-8\log7
<0.000004676829725969.
\end{equation}
\end{proposition}
\begin{proof}
We give the elementary interval rule and its error accounting, so that the
certificate does not depend on assuming decimal logarithms are accurate.
For $1\le y\le2$ put
\[
P(y)=2\sum_{j=0}^{30}\frac{1}{2j+1}
\left(\frac{y-1}{y+1}\right)^{2j+1},
\qquad
\mathcal L(x)=eP(2)+P(2^{-e}x),\quad e=\lfloor\log_2x\rfloor.
\]
For rational $x>0$, its exponent $e$ is determined by exact comparisons with
powers of two. Integrating the geometric series for $2/(1-z^2)$ gives
\[
0\le\log y-P(y)\le
\tau:=\frac{2\,3^{-63}}{63(1-1/9)}<3.120348\cdot10^{-32}.
\]
Thus $|\log x-\mathcal L(x)|\le(|e|+1)\tau$, including when $e<0$.
On each dyadic interval $\mathcal L$ is increasing; at a boundary its left
limit is $eP(2)+P(2)=(e+1)P(2)$, the value from the next interval.
It is therefore continuous and increasing on $(0,\infty)$. Applying $P$
at outward endpoints, then enlarging by the indicated tail, encloses
$\log x$ even if an input interval crosses a dyadic boundary.
For completeness, all exponents in this evaluation satisfy $|e|<2048$.
There are fewer than 256 ordered points in every product-law support.
By \eqref{eq:weight-bounds}, a nonzero product-law probability exceeds
$2^{-146}$, a $z$ entry exceeds $2^{-54}$, and a positive binary entry
exceeds $2^{-20}$. The initial marginal entries exceed $2^{-148}$.
Positive entries of a length-four law $V$ exceed $2^{-186}$; multiplying
one by a Stage A probability gives $2^{-332}$, and multiplying two gives
$2^{-518}$. These bounds also cover sums within nonzero groups; all these
masses are at most one. The integer leaf multiplicities and coefficients
are less than $7^8<2^{23}$. Hence the actual logarithm arguments lie between
$2^{-518}$ and $2^{23}$, a stronger range than needed. One may uniformly use
\begin{equation}\label{eq:log-error}
\epsilon=2048\tau<6.391\cdot10^{-29}.
\end{equation}
Here is an independent propagation bound for replacing every logarithm
literally by $\mathcal L$, without presuming that the resulting rational
version of $\mathcal K$ is homogeneous. For a vector of total mass $M$, the
error in $\mathcal K$ is at most $2M\epsilon$. The total singleton and
nonsingleton group masses in \eqref{eq:finite-group-contraction} sum to one,
so its error is at most $2\epsilon$. A sharing capacity has errors at most
$(2,6,6)\epsilon$ in its three positions. The A parent amounts sum to at
most one, the B parent amounts to at most two, and the positive length-two
amount $T$ is at most four. Consequently the entrywise error in $L_A+L_B$
is at most $(6,18,18)\epsilon$, and its average has error at most
$14\epsilon$. The error in $h_b(d)$ is at most $3\epsilon$, hence that in
$B_*$ at most $20\epsilon/3$. Including $H_0$ gives
\[
|\text{error in }(H_0+C_*)|\le\tfrac{68}{3}\epsilon.
\]
For $S_0,S_1,S_2$ the corresponding bounds are
$\epsilon,6\epsilon,20\epsilon$, respectively. Therefore
\[
|\text{error in }S_*|\le27\epsilon,\qquad
|\text{error in the comparison at }\Omega|
\le\left(\tfrac{68}{3}+9\Omega+8\right)\epsilon
<3.324\cdot10^{-27}.
\]
The file \texttt{verification/scripts/verify\_parameters.py} implements the
stated finite contractions. It constructs every $F(n)$ as an exact fraction,
then uses outward interval operations for all arithmetic, including each
normalizing denominator. Shared occurrences of a denominator are retained
as interval occurrences; no independence or cancellation is assumed to
reduce error. Exact structural checks establish normalization by division
by the positive total, complement symmetry, and statistic support before
the numerical checks. The interval checks of zero differences are only
consistency checks of these identities.
The primary verification evaluates the rational series above and adds its
tail; a second run uses directed native logarithms as a cross-check.
Binary interval endpoints are converted to exact fractions and serialized
by floor for lower bounds and ceiling for upper bounds, including negative
endpoints. These operations give outward decimal bounds without a
nearest-rounding assumption. At 80 decimal digits, every reported native-log
interval has width below $10^{-76}$; with the rational-series tail included,
every reported interval has width below $3\cdot10^{-29}$. These bounds include
all normalization and subsequent arithmetic rounding.
In addition to \eqref{eq:yield-certificate}--\eqref{eq:gap-certificate},
the resulting bounds include
\[
0.468025165562828972<T\log2-B_*<0.468025165562828973.
\]
The following entries enclose $L_C$, the numerators
$b_i=T\log2-C_*+(L_A+L_B)_i$ of the balance fractions, and the fractions
$\lambda_i$, respectively. Each listed number is a lower bound; adding
$10^{-15}$ to it gives an upper bound.
\[
\begin{array}{c|rrr}
&0&1&2\\\hline
L_C&1.115343821954349&.962118642424118&1.396738451843254\\
b&.510748315682386&.663973495212618&.229353685793481\\
\lambda&.363761291246081&.472890166361139&.163348542392779
\end{array}
\]
The fractions sum to one exactly by their definition, since the sum of
their numerators is $3(T\log2-B_*)$. Positivity of $L_A,L_B$ follows
already from the thirty positive partial entries. The boundary deficit
used in the finite-lot schedule also satisfies
\[
0.533798153<2C_*-\min_i(L_A)_i-\min_i(L_A+L_B)_i
-\min_i(L_B+L_C)_i-\min_i(L_C)_i<0.533798155<1.
\]
These bounds verify all stated feasibility conditions. The script checks
every displayed enclosure and stores the full interval outputs
with the packaged integer data.
The rounded entries in Tables~\ref{tab:capacities} and~\ref{tab:scalars}
already certify $\omega<2.371056$. The stronger bound in
Theorem~\ref{thm:main} uses the interval enclosure
\eqref{eq:ratio-certificate}.
For the rounded-table check, allow independent errors of $4\cdot10^{-8}$ in all 30 partial capacities, $H_0$, $B_*$, and the three
volume rows. The total uncertainty in the comparison is at most
\[
\left(12+\Omega\right)4\cdot10^{-8}=5.7484224\cdot10^{-7}.
\]
Using the displayed centers and an outward bound on $8\log7$ leaves a
positive margin greater than $4.1011\cdot10^{-6}$. Thus the strict inequality
has ample room for both arithmetic enclosure and the arbitrarily small
losses in the construction.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:main}]
Since $S_*>0$, Proposition~\ref{prop:numerical-certificate} and
\eqref{eq:rank-constraint} give
\[
\omega\le w\le\frac{3(8\log7-H_0-C_*)}{S_*}
<2.371054886006746<2.371054887.\qedhere
\]
\end{proof}
The integer tables and their full traversal are sufficient to reproduce this
comparison. The verification package includes a readable assignment table and both
interval outputs; verification requires Python 3.10 or later and
\texttt{mpmath} 1.3.0, with no optimization software or external data.
==== END Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/parameters.tex ====
==== BEGIN Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/recovery.tex ====
\section{Recovering the ideal outputs and composing extractions}
\label{sec:recovery}
The assignment procedure in Section~\ref{sec:joint} leaves a direct sum
of variable restrictions of the intended outputs. We now select
sufficiently many of these outputs and recover them exactly. Two different probability spaces occur: permutations
of an ideal output control inherited masks, whereas the random hash
controls assignment collisions. Keeping these spaces separate is
essential when a received population already has type restrictions.
Recovery from deletions on all three sides appears in
\cite[Section~7, especially Property~7.1 and Theorem~7.2]{VXXZ2023};
its interface-tensor consequence is Corollary~4.2 there. The
constituent-stage analysis in \cite[Section~6.5]{MoreAsymmetry2026}
also accounts for inherited approximate type restrictions. Here we
establish uniform loss on every full-variable orbit of each selected
heterogeneous output and reconstruct its coefficients by an exact linear
restriction.
\subsection{Uniform control of inherited masks}\label{sec:recovery-masks}
Fix all population masses, rational laws, and positive tolerances before
letting the divisible integer $N$ grow. Classes of zero mass are omitted.
For a target coarse triple $e$, write $Q_e$ for its ideal child product,
including its prescribed child-side type windows, but before inherited
input masks and global pair-frequency masks. Keep distinct the
population, its previous history, its exact parent split triple, and its
left or right half. Each resulting child class $c$ has $n_c=c_cN$
positions, with $c_c>0$ fixed. At an ordinary extraction the corresponding
whole-strand classes, or the unrestricted child classes of an ordinary
split, are used instead.
Let $G_e$ be the product of the symmetric groups on these classes.
A permutation acts simultaneously on the three sides of a child tensor,
and different child classes, including opposite halves, are permuted
independently. This action preserves both the tensor factors and the
child-side type windows, so it consists of coefficient-preserving
automorphisms of $Q_e$. The action is on complete variables: a symbol
records the entire child word, including its weight-one labels.
\begin{lemma}[Uniform loss from inherited masks]
\label{lem:orbit-masks}
The total number of $G_e$-orbits of variables on the three sides is
polynomial in $N$, uniformly over target triples $e$.
Suppose every inherited or global mask is either implied by the exact
coarse choices, or tests an empirical ordered pair of child statistics
(or a fixed function of that pair) against its prescribed mixture law
with a fixed positive tolerance.
Choose the child tolerances sufficiently smaller than those mask
tolerances, with the mixture laws consistent as in
Theorem~\ref{thm:joint-step}. There is then a constant $C_0$ such that,
in every full-variable orbit on every side, the fraction failing any
of these deterministic masks is at most $C_0/N$.
The constant may depend on the fixed data and tolerances, but not on
$e$, the orbit, or $N$.
\end{lemma}
\begin{proof}
Let $\mathcal A_{c,W}$ be the finite alphabet of complete child variables
on side $W$ in class $c$. An orbit is specified by the multiplicity of
every symbol in every class. Its number on side $W$ is therefore at
most
\[
\prod_c(n_c+1)^{|\mathcal A_{c,W}|}=O(N^{d_W})
\]
for a fixed integer $d_W$. Child type windows merely select some of
these orbits. The alphabets include all labels, even when a mask uses
only a much coarser statistic.
Consider one mask with tolerance $\eta>0$, on a population of size
$m=cN$. Its tested law is an ordered-pair mixture. Write its exact
parent-triple classes as $a$, with weights $w_a=n_a/m$, and let
$q_{a,L},q_{a,R}$ be the two empirical statistic laws in a fixed orbit.
For the prescribed laws $\nu_{a,L},\nu_{a,R}$, the child windows give
coordinate errors at most $\tau$. If a coarsening of a child statistic
is needed, choose its original window smaller by the fixed alphabet
size, so this assertion holds for the statistic actually tested.
The elementary inequality
\[
|q_{a,L}(s)q_{a,R}(t)
-\nu_{a,L}(s)\nu_{a,R}(t)|\leq 2\tau
\]
shows that the mean mixture differs from
$\sum_a w_a\nu_{a,L}\otimes\nu_{a,R}$ by at most $2\tau$
in each coordinate. More generally, suppose the mask center differs
from this prescribed mixture by coordinatewise error at most
$\alpha\leq\eta/4$. Choosing $\tau\leq\eta/8$ then leaves a margin
of at least $\eta/2$ inside the mask's acceptance interval. For the
consistent rational prescriptions of Theorem~\ref{thm:joint-step},
$\alpha=0$. This margin holds also for orbits at the boundary of a child window.
Uniformly permute an element of the orbit. Within one parent-triple
class of size $n$, the two half-statistic words are independently
arranged. If the frequencies of $s$ and $t$ are $a$ and $b$, their
paired count $K_{s,t}$ satisfies, for $n\geq2$,
\begin{equation}
\mathbb E K_{s,t}=nab,\qquad
\operatorname{Var}(K_{s,t})
=\frac{n^2a(1-a)b(1-b)}{n-1}\leq\frac n8.
\label{eq:matching-variance}
\end{equation}
Indeed, fix the positions of the $na$ occurrences on the left.
The indicators that the right symbol is $t$ have mean $b$,
variance $b(1-b)$, and covariance $-b(1-b)/(n-1)$ at distinct
positions. Summing gives~\eqref{eq:matching-variance}. This calculation
is uniform over $a,b\in[0,1]$, including deterministic symbols.
Different parent-triple classes use independent permutations.
Consequently the variance of a pair count summed over a population
is at most $m/8$. Chebyshev's inequality and the acceptance margin give
\[
\Pr\left(\left|\frac{\sum_a K_{s,t}^{(a)}}m
-\mathbb E\frac{\sum_a K_{s,t}^{(a)}}m\right|>\eta/2\right)
\leq \frac{1}{2c\eta^2N}.
\]
For a mask on a fixed function of the ordered pair, a coordinate of
the pushed-forward law is a sum of at most $B$ pair coordinates,
where $B$ is fixed. Choose $\tau\leq\eta/(8B)$ and apply the last
bound to each pair coordinate with deviation threshold $\eta/(2B)$.
Summing coordinate errors and taking a finite union bound proves the
same $O(1/N)$ conclusion for that mask. All positive classes eventually
have size at least two. There are only finitely many masks and
statistic coordinates, so another union bound gives $C_0/N$.
A uniform group element sends any fixed variable uniformly
over its full orbit; thus this probability is exactly the rejected
fraction of that orbit. We have not conditioned on passing a mask.
Taking a minimum of the finitely many positive tolerance gaps and
positive population masses makes $C_0$ uniform as asserted. A statistic
that is itself an ordered pair is simply a symbol of a larger fixed
alphabet. Masks implied by the exact coarse choices cause no loss.
\end{proof}
\subsection{Exact repair}\label{sec:recovery-exact}
We next give an algebraic recovery statement. A variable restriction
of a tensor means that some basis variables are set to zero; all
coefficients on the remaining variables retain their original values.
\begin{lemma}[Exact repair by presence masks]
\label{lem:hole-repair}
Let $Q_N$ be a tensor over an arbitrary field, with at most $\exp(bN)$
nonzero monomials for a fixed $b>0$. Let $G_N$ be a finite group of
coefficient-preserving permutations of its variables, acting separately
on the three sides. Suppose a variable restriction $H_N$ of $Q_N$
omits at most $C/N$ of each $G_N$-orbit of variables, for a fixed $C>0$.
For all sufficiently large $N$, a direct sum of
\[
R_N=\exp\bigl(O(N/\log N)\bigr)
\]
copies of $H_N$ has $Q_N$ as a linear restriction. Every coefficient
is reconstructed exactly once. The bound is uniform over all
$H_N,Q_N,G_N$ satisfying these same constants.
\end{lemma}
\begin{proof}
We first cover all ideal monomials by shifted copies. Partitioning
variables by their presence masks then converts this cover into an exact
linear restriction.
Put $\gamma=C/N$ and, for $N>3C$, choose
\[
L=\left\lceil\frac{(b+1)N}{\log(N/(3C))}\right\rceil
=O(N/\log N).
\]
Take $L$ independent uniform elements $g_1,\ldots,g_L$ of $G_N$.
For a fixed ideal variable, its probability of absence from $g_iH_N$
is at most $\gamma$. For a fixed nonzero monomial $xyz$ of $Q_N$,
the union bound on its three variables makes its probability of absence
at most $3\gamma$. Independence of the $L$ shifts, followed by a
union bound over the support, bounds the probability of an uncovered
monomial by
\[
\exp(bN)(3\gamma)^L\leq e^{-N}<1.
\]
Fix a family covering every monomial. The group need only preserve
$Q_N$; it is allowed to move the holes of $H_N$.
For an ideal variable $x$, define its presence mask
\[
A(x)=\{i\in\{1,\ldots,L\}:x\text{ is retained in }g_iH_N\},
\]
and define $B(y)$ and $C(z)$ similarly. Partition the three sides
into the classes $X_A,Y_B,Z_C$ of equal masks. There are at most
$2^L$ classes on each side. For each triple of classes whose rectangle
$X_A\times Y_B\times Z_C$ contains a nonzero monomial of $Q_N$,
coverage implies $A\cap B\cap C\ne\varnothing$. Choose one index
$i(A,B,C)$ in this intersection. All variables in these three classes
are present in $g_{i(A,B,C)}H_N$. Since this is a variable restriction
of $Q_N$, its restriction to these classes is the full ideal tensor
on the rectangle, with every original coefficient.
Use a separate copy of $H_N$ for each such rectangle, permute that
copy by the chosen $g_{i(A,B,C)}$, and zero all other variables. In
the direct sum of these rectangular tensors, map the copied variable
$(A,B,C,x)$ to the ideal variable $x$, and similarly on the other two
sides. These are ordinary linear maps. Every nonzero monomial $xyz$
belongs to exactly one triple of mask classes, so its coefficient is
supplied once and only once. Identifying a variable used in several
rectangles introduces no additional monomials: linear maps act on
the sum of the existing tensor terms. There is no division or
characteristic restriction. At most $2^{3L}$ copies are used, and
padding with unused copies gives the asserted common bound $R_N$.
\end{proof}
\subsection{Completing the joint extraction}\label{sec:recovery-completion}
\begin{proof}[Completion of the proof of Theorem~\ref{thm:joint-step}]
Use the hash slack $\delta>0$ from Section~\ref{sec:joint}, with all
entropy errors chosen smaller than a fixed fraction of this slack.
For a target triple $e$, let $S_e$ be its own hash-survival event;
$\Pr(S_e)=h_M=|U|/M^2$. Let $P_e(v)$ denote the deterministic
assertion that an ideal variable $v$ of $Q_e$ passes its inherited and
global masks. Membership in $Q_e$, together with the tolerance
inclusions, supplies usefulness and compatibility with its own triple.
For every $G_e$-orbit $\mathcal O$, Lemma~\ref{lem:orbit-masks} gives
\[
d_{e,\mathcal O}
=\frac{|\{v\in\mathcal O:\neg P_e(v)\}|}{|\mathcal O|}
\leq C_0/N.
\]
For a passing variable $v$, use the event $R_{e,v}$ defined at the
end of Section~\ref{sec:joint}: it includes failure of $e$ at the $X$
uniqueness test and all compatible-target collisions relevant to $v$.
Equation~\eqref{eq:joint-conditional-loss} gives
\begin{equation}
\Pr(R_{e,v}\mid S_e)\leq e^{-cN}
\label{eq:conditional-variable-loss}
\end{equation}
for one fixed $c>0$, uniformly in $e$ and $v$, for all large $N$.
Here $P_e(v)$ is fixed before choosing the hash; the conditioning is
still only $S_e$. We now average this individual loss over each full
ideal orbit, including in the denominator the variables that fail the
deterministic masks.
Specifically, put
\[
r_{e,\mathcal O}
=\frac{1}{|\mathcal O|}
\sum_{\substack{v\in\mathcal O\\P_e(v)}}
\mathbf1_{R_{e,v}}.
\]
By linearity of expectation,
$\mathbb E(r_{e,\mathcal O}\mid S_e)\leq e^{-cN}$.
Variables failing $P_e$ contribute to $d_{e,\mathcal O}$, and need
no collision estimate. If $P(N)$ bounds the total number of orbits
on all three sides, Markov's inequality and a union bound imply
\[
\Pr\left(\exists\mathcal O:r_{e,\mathcal O}>1/N\mid S_e\right)
\leq NP(N)e^{-cN}=e^{-cN+O(\log N)}.
\]
Declare $e$ good if it survives hashing, remains eligible, and all
these random fractions are at most $1/N$. Including the exponentially
small eligibility failure explicitly changes only the polynomial
factor in this bound. Every good $e$ therefore has missing fraction
at most
\begin{equation}
\gamma_N=(C_0+1)/N
\label{eq:uniform-good-holes}
\end{equation}
in each orbit. The eligible list remains the fixed list used in
Section~\ref{sec:joint}. Deterministic masks are accounted for as
additional deletion flags; they do not trigger a recomputation of
that list or of the compatibility candidates.
There are $\exp(NA_{\mathrm{amb}}+O(\log N))$ target triples, and
$\log M=N(A_{\mathrm{amb}}-E+\delta)+O(1)$ with
$\log|U|=\log M-o(N)$. If $\mathcal G$ is the set of good triples,
\begin{align*}
\mathbb E|\mathcal G|
&\geq\exp(NA_{\mathrm{amb}}+O(\log N))\,h_M
\bigl(1-e^{-cN+O(\log N)}\bigr)\\
&=\exp\bigl(N(E-\delta)-o(N)\bigr).
\end{align*}
Thus one hash choice has at least this many good triples, up to
integer rounding. This uses no independence between different
targets or between their losses. The assignment proof has already
made their holed outputs $H_e$ disjoint. Discard all other outputs.
All strand lengths and alphabets are bounded, and there are $O(N)$
factors, so every ideal $Q_e$ has at most $\exp(bN)$ monomials for
one fixed $b$. For example, a product on at most $aN$ original
$\CW_5$ sites has at most $18^{aN}$ terms before any masks, since
$\CW_5$ has $3\cdot5+3=18$ terms; any $b>a\log18$ suffices.
Apply Lemma~\ref{lem:hole-repair} with
$C=C_0+1$ to every good output. A common
$R_N=\exp(O(N/\log N))$ works for all of them. Indeed,
\[
\bigoplus_{r=1}^{R_N}\ \bigoplus_{e\in\mathcal G} H_e
\cong
\bigoplus_{e\in\mathcal G}\ \bigoplus_{r=1}^{R_N}H_e.
\]
The same replication slots supply each summand with $R_N$ copies.
Within a summand choose its own covering family and rectangular
maps, and keep variables of different summands distinct. This
produces $\bigoplus_{e\in\mathcal G}Q_e$ with $R_N$ copies of the
original joint input. The number of summands does not multiply the
replication cost.
Finally, exact target types give the same number of factors in every
population, history, split-triple, and half class for every $e$.
After repair, simultaneous position relabelings within each population
put these classes in a fixed canonical order. They identify all
$Q_e$ with a single ideal product $Q_N$, without permuting the physical
tensor sides. This canonicalization concerns the repaired ideal
tensors and their child windows; no invariance of an earlier hole
pattern is needed. Choose $0<\delta<\min(E,\varepsilon)$ and then $N$ large
enough to absorb the $o(N)$ term. The result is at least
$\exp(N(E-\varepsilon))$ identical ideal outputs from
$\exp(o(N))$ input copies, as claimed.
\end{proof}
\subsection{Composition and subdivision}\label{sec:recovery-composition}
To iterate Theorem~\ref{thm:joint-step}, we record the two algebraic
operations explicitly. Write $D_r(T)=\bigoplus_{i=1}^r T$,
and write $A\preceq B$ when $A$ is a linear restriction of $B$.
\begin{lemma}[Replication and composition]
\label{lem:replication}
Suppose $D_{s_1}(T)\preceq D_{r_1}(S)$ and
$D_{s_2}(V)\preceq D_{r_2}(T)$. Then
\[
D_{s_1s_2}(V)\preceq D_{r_1r_2}(S).
\]
For any finite collection of tensors,
\[
\bigotimes_{i=1}^j D_{r_i}(F_i)
\cong D_{\prod_{i=1}^j r_i}\left(\bigotimes_{i=1}^jF_i\right).
\]
The same assertions permit different maps in different direct-sum
branches, provided a common upper bound on their replication counts
is used. Consequently every fixed finite sequence of the joint
extractions above, including finite tensor products of them, costs
only $\exp(o(N))$ replications of its original input.
\end{lemma}
\begin{proof}
Take $r_2$ copies of the first restriction and reorder their direct
sum as $D_{s_1}(D_{r_2}(T))$. Apply the second restriction separately
to its $s_1$ disjoint blocks. This gives the first identity with
$r_1r_2$ source copies, regardless of the value of $s_1$.
The second identity is direct-sum distributivity: its summands are
indexed by the choices of one replication slot for each factor.
A finished factor can be tensored through with replication count one.
Branch-dependent maps act block by block after padding unused slots
to the common bound. Lemma~\ref{lem:hole-repair} provides such a
bound uniformly over the selected outputs of each joint step.
Products of finitely many $\exp(o(N))$ quantities are $\exp(o(N))$.
For a fixed finite set of population specifications, all positive
sizes are $cN$ with $c>0$ fixed, so a local $o(cN)$ is also $o(N)$.
\end{proof}
There is also an exact way to subdivide a received population before
its next use. Let $B$ be its strand tensor, let $\nu_W$ be the
prescribed statistic law on side $W$, and denote by
$U(m,\nu,\eta)$ the restriction of $B^{\otimes m}$ to the three
coordinatewise type windows with tolerance $\eta$. Partition the
positions into fixed parts of sizes $m_1,\ldots,m_j$, and on each part
use the same laws and a positive tolerance $\eta_i\leq\eta$. There is an exact
variable restriction
\begin{equation}
\bigotimes_{i=1}^j U(m_i,\nu,\eta_i)
\preceq U\left(\sum_{i=1}^j m_i,\nu,\eta\right).
\label{eq:subdivision-restriction}
\end{equation}
To see this, the empirical law of a concatenated variable is the
weighted average of its partwise empirical laws, with error at most
$\sum_i(m_i/\sum_jm_j)\eta_i\leq\eta$. Hence every retained
variable satisfies the original window; after the partwise masks are
imposed, no condition couples different parts, giving exactly the
displayed product. Different side tolerances are handled in the same
way. Apply this argument separately within every received history
class; classes with different prescriptions remain distinct.
Equation~\eqref{eq:subdivision-restriction} need not retain a large
fraction of the earlier variables. The next application of
Theorem~\ref{thm:joint-step} starts from this exact product, with its
new positive population masses and its consistent inherited laws.
Thus it supplies its own yield and mask analysis. Together with
canonicalization after repair, this explains why arbitrary fixed
finite subdivisions and heterogeneous populations can be used in a
subsequent joint step. All such subdivisions and tolerances are fixed
before $N$ grows; no assertion of uniformity in a number of populations
growing with $N$ is needed.
The required tolerance hierarchy exists for any fixed finite
calculation. At a step first make its global and compatibility
tolerances small enough for the entropy errors allowed by its hash
slack. Then choose its child windows smaller than all those tests and
all inherited windows that they must satisfy. Repeat toward the
descendants. There are finitely many constraints, each allowing a
strictly positive choice. All constants in this section may depend
on this fixed calculation; the strand limit is taken only after these
choices.
==== END Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/recovery.tex ====
==== BEGIN Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/staggering.tex ====
\section{Staggering the three extraction stages}\label{sec:stagger}
A \emph{lot} consists of $N$ strands of length $8$, hence of $8N$
copies of $\CW_5$. Its positive shapes pass successively through
three stages: A splits length $8$ into length $4$, B splits length $4$
into length $2$, and C splits length $2$ into length $1$. Every shape
with a zero coordinate terminates immediately as a matrix tensor.
Theorem~\ref{thm:joint-step} lets one extraction act on populations
from different stages. We specify their data first, then give the
finite schedule that exploits this freedom.
\subsection{Shapes, prescriptions, and the three stages}
All coordinate labels in this section belong to $\{0,1,2\}$.
A shape is \emph{positive} if all its coordinates are positive.
Choose a symmetric product-weight law on the ordered shapes of size
$16$: its probability at $(a,b,c)$ is proportional to
$\alpha_a\alpha_b\alpha_c$, where every $\alpha_j>0$ and $a+b+c=16$.
Write $A_g$ for the resulting probability of the sorted shape $g$.
Thus the multiplicity of its distinct permutations is included in
$A_g$. If $\rho_g$ gives mass $1/3$ to each coordinate of $g$, counting
multiplicities, the common marginal and initial ordinary yield are
\begin{equation}\label{eq:initial-yield}
\mu=\sum_g A_g\rho_g,\qquad H_0=H(\mu).
\end{equation}
The product-weight hypothesis verifies maximum entropy at the given
marginals. The initial ordinary extraction therefore yields
$\exp(N(H_0-o(1)))$ identical products of shape tensors, after the
arbitrarily small losses of Theorem~\ref{thm:joint-step}.
Give each sorted $g$ canonical labels $0,1,2$. Its six placements of
these labels on the three physical sides will each have amount
$NA_g/6$. To implement this when $g$ has ties, let $s_g$ be the number
of label permutations fixing $g$. There are $6/s_g$ distinct physical
shapes, each with $NA_gs_g/6$ positions. Divide its positions into
$s_g$ equal classes and assign the distinct tied-label placements to
them. This is a regrouping of full tensor factors: no fine mask has
yet been imposed. For example, each physical arrangement of $(4,6,6)$
has two such classes. Later laws may distinguish its two labels of
weight $6$. Descendants retain these canonical labels and are never
re-sorted.
For each positive sorted $g$ of size $16$, choose a positive
product-weight law $P_g(t)$ on
\[
|t|=8,\qquad 0\leq t\leq g,
\]
with $P_g(t)=P_g(g-t)$. For every positive \emph{ordered} $t$ of size
$8$, likewise choose a positive product-weight law $p_t(u)$ on
$|u|=4$, $0\leq u\leq t$, with $p_t(u)=p_t(t-u)$. The numerical data
in Section~\ref{sec:parameters} specify these laws, as well as the
parameters $d_{t,u}\in[0,1]$ and terminal laws $z_t$ used below.
Infeasible subscripts always have probability zero.
The length-$2$ statistic on one side is its unordered pair of weights.
We use the following fixed coding; $D_i$ counts the actual index words
with statistic $i$, including the $q=5$ choices at a weight-$1$ site:
\begin{equation}\label{eq:pair-statistics}
\begin{array}{c|rrrrrr}
i&0&1&2&3&4&5\\ \hline
\text{weight pair}&00&01&11&02&12&22\\
r_i&0&1&2&2&3&4\\
D_i&1&10&25&2&10&1
\end{array}
\qquad \kappa=(5,4,2,3,1,0).
\end{equation}
Here $r_i$ is the sum of the two weights, and $\kappa$ is the image
list for complementation. For positive $t$ and a feasible child $u$,
define the law $v_{t,u,W}$ on these six statistics, for each canonical
label $W$, by requiring support on $r_i=u_W$. If $u_W\ne2$ this
determines the law. If $u_W=2$, put masses $1-d_{t,u}$ and $d_{t,u}$
on $11$ and $02$, respectively. A parameter is needed precisely when
$u$ is a permutation of $022$ or $112$.
On a length-$4$ strand the statistic is the \emph{ordered} pair of
the statistics of its length-$2$ halves. For positive $t$ prescribe
\begin{equation}\label{eq:inherited-mixture}
V_{t,W}=\sum_u p_t(u)\,
v_{t,u,W}\otimes v_{t,t-u,W}.
\end{equation}
For a zero-coordinate $t$, let $W_*$ be its first canonical label
attaining $\max t$. Choose $z_t$ on the ordered pairs $(i,j)$ with
$r_i+r_j=\max t$. Prescribe $V_{t,W_*}=z_t$, prescribe the point mass
at $(0,0)$ on zero coordinates, and prescribe the coordinatewise
$\kappa$-image of $z_t$ on the remaining nonzero coordinate, if any.
The laws of the two matched sides therefore agree under
complementation. The same property holds for zero-coordinate $u$:
$01$ complements $12$, while $11$ and $02$ complement themselves.
These are exactly the zero-side consistency requirements of
Theorem~\ref{thm:joint-step}.
\emph{Stage A} is a sharing split of $T_{8,g}$ with coarse law $P_g$,
child laws $V_{t,W}$, and canonical priority $(0,1,2)$.
\emph{Stage B} is a sharing split of $T_{4,t}$ with coarse law $p_t$,
child laws $v_{t,u,W}$, and canonical priority $\pi(t)$. This priority
is the lexicographically first permutation of the labels that reads
$t$ as one of
\begin{equation}\label{eq:B-priority}
(1,1,6),\quad(1,2,5),\quad(1,3,4),\quad(2,2,4),\quad(3,2,3).
\end{equation}
These represent every positive size-$8$ shape up to permutation.
The last representative intentionally gives the middle priority to
the coordinate of weight $2$: for $t=(2,3,3)$ the priority is
$(1,0,2)$. The symbols here remain inherited labels.
\emph{Stage C} is an ordinary split of a positive $T_{2,u}$.
Such $u$ is a permutation of $112$. Write its labels as $(a,b,c)$,
where $c$ is the distinguished label of weight $2$. In this order,
the four possible left shapes and their probabilities are
\begin{equation}\label{eq:C-law}
\begin{array}{c|cccc}
\text{left shape}&(1,1,0)&(0,0,2)&(1,0,1)&(0,1,1)\\ \hline
\text{probability}&d_{t,u}/2&d_{t,u}/2&(1-d_{t,u})/2&(1-d_{t,u})/2.
\end{array}
\end{equation}
The right shape is $u$ minus the left one. The distinguished marginal
fixes the first two probabilities, and the two Bernoulli-$1/2$
marginals fix the other two. Thus the coupling is uniquely determined
by its marginals, also at $d=0$ or $1$, and has the required maximum
entropy. Put
\[
h_b(d)=H(1-d,d)+d\log2.
\]
Its three ordinary capacities are $\log2,\log2,h_b(d_{t,u})$, with the
last at label $c$. Every delivered length-$1$ shape has a zero
coordinate and is already a matrix tensor.
This also verifies the inherited masks. At A to B, the input law
required by B is exactly the mixture \eqref{eq:inherited-mixture}
prescribed by A; the orbit-mask estimate of
Lemma~\ref{lem:orbit-masks} applies with smaller child tolerances.
At B to C, an exact type in \eqref{eq:C-law} forces unordered frequency
$d_{t,u}$ on $02$ and $1-d_{t,u}$ on $11$ at the distinguished label,
and forces $01$ at the other labels. Hence it satisfies the received
$v_{t,u,W}$ masks exactly. Complementary children may have different
$d$ parameters: each is a separate factor, and both actual laws appear
in \eqref{eq:inherited-mixture}.
After Stage B is repaired, its ideal children carry the prescribed
$v_{t,u,W}$ windows. The earlier $V_{t,W}$ masks were constraints on
the input to B; their holes have been repaired, so they are not additional
constraints on the recovered children. Thus the exact Stage C types
need only satisfy the $v_{t,u,W}$ windows, as verified above. The
permutation group used for repair preserves the ideal child tensor,
without needing to preserve the historical pattern of input holes.
A history records the lot, initial $g$, its label placement, every
coarse split, its left/right provenance, and any subsequent part.
We keep all these populations separate, even when their present
shapes coincide. In particular equal $u$ from different $t$ never
merge their $d_{t,u}$ values. The sums below record total amounts;
they do not combine differently prescribed populations.
\subsection{Capacity balance}
Stages A and B have fixed capacities in their chosen priority orders.
At Stage C, each positive length-$2$ population has two capacities equal
to $\log2$ and one equal to $h_b(d_{t,u})$. We may assign the latter
to any priority position by choosing the extraction order. We use this
freedom to make the sum of the three stages' capacity vectors have equal
coordinates.
Amounts throughout are measured per initial length-$8$ strand.
After summing over histories while retaining their specifications,
the amounts of the smaller shapes are
\begin{equation}\label{eq:population-counts}
m_t=2\sum_{\min g>0}A_gP_g(t),\qquad
m_{t,u}=2m_t p_t(u)\quad(\min t>0).
\end{equation}
The factors $2$ count the left and right children; reflection symmetry
of the coarse laws justifies each equality. A parent split is charged
only once when computing its capacity.
Let $L_A\in\mathbb R^3$ be the sharing-capacity vectors of Stage A,
weighted by $A_g$ and summed over positive $g$, with entries in priority
order. Likewise let $L_B$ be the Stage B vectors weighted by $m_t$
and read in the order $\pi(t)$. More explicitly, for each parent its
vector is
\[
\bigl(H(p_X),\ H(D_Y)-2J_Y,\ H(D_Z)-2J_Z\bigr),
\]
using its own coarse law and child prescriptions in the definitions of
Section~\ref{sec:joint}. Thus the two vectors are fully determined
by the data just specified. Let $T$ be the total positive length-$2$
amount, and let $B_*$ be the sum of those populations' average capacities,
weighted by their amounts. The average over priority positions of the
total stage capacity is $C_*$, where
\begin{align}\label{eq:balance-data}
T&=\sum_{\min t>0,\,\min u>0}m_{t,u}, &
B_*&=\sum_{\min t>0,\,\min u>0}
m_{t,u}\frac{2\log2+h_b(d_{t,u})}{3},\notag\\
C_*&=B_*+\frac13\sum_{i=0}^2(L_A+L_B)_i.
\end{align}
Suppose, as the numerical certificate verifies, that
\begin{equation}\label{eq:balance-feasibility}
T\log2>B_*,\qquad
C_*-(L_A+L_B)_i<T\log2\quad(0\leq i<3).
\end{equation}
The denominator and each numerator below are positive by
\eqref{eq:balance-feasibility}. The numbers
\begin{equation}\label{eq:balance-fractions}
\lambda_i=
\frac{T\log2-C_*+(L_A+L_B)_i}{3(T\log2-B_*)}
\qquad(0\leq i<3)
\end{equation}
sum to $1$: their numerators sum to $3(T\log2-B_*)$ by
\eqref{eq:balance-data}. Divide \emph{each} positive length-$2$ history class into
these proportions. In part $i$, place its distinguished label in
priority position $i$ and order the other labels increasingly in the
remaining positions. This changes the extraction order only; it
keeps the same parent-specific $d_{t,u}$ and masks. The resulting
Stage C capacity vector satisfies
\begin{align}\label{eq:stage-balance}
(L_C)_i
&=T\log2-\lambda_i
\sum_{\min t>0,\,\min u>0}m_{t,u}
\bigl(\log2-h_b(d_{t,u})\bigr)\notag\\
&=T\log2-3\lambda_i(T\log2-B_*)
=C_*-(L_A+L_B)_i.
\end{align}
Consequently $L_A+L_B+L_C=(C_*,C_*,C_*)$.
\subsection{Physical orders and the finite schedule}
Apply the subdivision restriction \eqref{eq:subdivision-restriction}
separately within each received history class, keeping the same
prescribed laws and using smaller positive windows. Different parts may
use different widths. The resulting tensor is exactly the product of
the partwise restrictions; no retained-fraction estimate is required,
since Theorem~\ref{thm:joint-step} acts on this specified product directly.
After each repair, exact coarse counts let simultaneous position
permutations put its ideal child classes in a canonical order.
All selected summands therefore have identical future inputs. These
permutations are made after repair and need not preserve the earlier
hole patterns.
Suppress the physical placement in a fixed canonical history $h$.
At each of its six placements $\phi$, its amount is $a_hN/6$ for the
same $a_h$. This is true initially by the tied-label subdivision.
Every child split and part allocation multiplies it by a number
depending only on the canonical history, so it remains true
inductively. If $\rho_h$ maps priority positions to canonical labels,
the physical priority is $\phi\circ\rho_h$. For any prescribed
physical order $\sigma$ there is exactly one contributing placement,
\begin{equation}\label{eq:physical-order-map}
\phi=\sigma\circ\rho_h^{-1}.
\end{equation}
Thus the six physical orders give a disjoint partition of the work,
with one sixth of every history's priority-capacity vector in each
factor. This applies to the Stage C parts as well as to A and B.
Assume that $L_A,L_B,L_C$ have positive entries, as verified in
Proposition~\ref{prop:numerical-certificate}. Then each vector obtained
by summing any nonempty subset of the active stages also has positive
minimum capacity. This supplies the condition $E>0$ of
Theorem~\ref{thm:joint-step} for each physical-order factor at every
tick of the following schedule. Its finite applications will use
the rational choices made in Section~\ref{sec:staggered-assembly}.
Fix an integer $K\geq2$ and perform the initial ordinary extraction on
each of $K$ lots. Within every resulting summand, launch lot $j$ at A
on tick $j$, at B on tick $j+1$, and at C on tick $j+2$. The active
stage patterns are
\begin{equation}\label{eq:finite-schedule}
A;\quad A+B;\quad
\underbrace{A+B+C;\ \ldots;\ A+B+C}_{K-2\text{ ticks}};
\quad B+C;\quad C.
\end{equation}
Every lot is processed once at each of its three depths. We first
compute the rates for the prescribed data. The rational approximations
and arbitrarily small extraction losses are handled in
Section~\ref{sec:staggered-assembly}.
At a tick, collect all currently active populations with one physical
priority into one tensor factor, using \eqref{eq:subdivision-restriction}
if a received type class needs subdivision. Apply one joint step to
each of the six factors. A full tick has, in each factor, total
priority-capacity vector
\[
\frac16(L_A+L_B+L_C)=\frac16(C_*,C_*,C_*).
\]
Its minimum is $C_*/6$, so multiplying the six output counts gives
log-yield approaching $NC_*$. The four boundary ticks similarly
have log-yields divided by $N$ approaching
\[
\min L_A,\qquad \min(L_A+L_B),\qquad
\min(L_B+L_C),\qquad \min L_C,
\]
where $\min x=\min_{0\leq i<3}x_i$ for a vector $x$.
All four minima are strictly positive by the entrywise positivity
assumption. Relative to $K$ full-tick contributions, their deficit is
\begin{equation}\label{eq:boundary-deficit}
\beta=2C_*-\min L_A-\min(L_A+L_B)
-\min(L_B+L_C)-\min L_C.
\end{equation}
Using $L_A+L_B+L_C=C_*\mathbf1$, this is equivalently
$\beta=(\max L_A-\min L_A)+(\max L_C-\min L_C)\geq0$.
The certificate in Proposition~\ref{prop:numerical-certificate}
also verifies $\beta<1$.
Thus the $K-2$ full ticks and four boundary ticks contribute
$KC_*-\beta$, and the initial extractions add $KH_0$.
Figure~\ref{fig:pipeline} shows the distinction between progression of
one lot and joint extraction of three distinct lots.
\input{figures/pipeline.tex}
Finished matrix factors are carried through subsequent operations by
tensor product. After the last tick, every lot has terminated, and
exact coarse counts fix the number of terminal factors in every oriented
history class. The next section computes their dimensions and then
combines that count with the yield $K(H_0+C_*)-\beta$ to obtain the rank
constraint.
==== END Staggered-extraction-for-exact-matrix-multiplication-over-every-field//sections/staggering.tex ====
==== BEGIN Staggered-extraction-for-exact-matrix-multiplication-over-every-field//references.bib ====
@article{Behrend1946,
author = {Behrend, F. A.},
title = {On Sets of Integers Which Contain No Three Terms in Arithmetical Progression},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
volume = {32},
number = {12},
pages = {331--332},
year = {1946},
month = dec,
doi = {10.1073/pnas.32.12.331},
url = {https://doi.org/10.1073/pnas.32.12.331},
note = {\url{https://doi.org/10.1073/pnas.32.12.331}}
}
@article{Strassen1969,
author = {Strassen, Volker},
title = {Gaussian Elimination Is Not Optimal},
journal = {Numerische Mathematik},
volume = {13},
pages = {354--356},
year = {1969},
month = aug,
doi = {10.1007/BF02165411},
url = {https://doi.org/10.1007/BF02165411},
note = {\url{https://doi.org/10.1007/BF02165411}}
}
@article{Schonhage1981,
author = {Sch{\"o}nhage, Arnold},
title = {Partial and Total Matrix Multiplication},
journal = {SIAM Journal on Computing},
volume = {10},
number = {3},
pages = {434--455},
year = {1981},
month = aug,
doi = {10.1137/0210032},
url = {https://doi.org/10.1137/0210032},
note = {\url{https://doi.org/10.1137/0210032}}
}
@article{Strassen1987,
author = {Strassen, Volker},
title = {Relative Bilinear Complexity and Matrix Multiplication},
journal = {Journal f{\"u}r die reine und angewandte Mathematik},
volume = {375/376},
pages = {406--443},
year = {1987},
doi = {10.1515/crll.1987.375-376.406},
url = {https://doi.org/10.1515/crll.1987.375-376.406},
note = {\url{https://doi.org/10.1515/crll.1987.375-376.406}}
}
@article{CoppersmithWinograd1990,
author = {Coppersmith, Don and Winograd, Shmuel},
title = {Matrix Multiplication via Arithmetic Progressions},
journal = {Journal of Symbolic Computation},
volume = {9},
number = {3},
pages = {251--280},
year = {1990},
month = mar,
doi = {10.1016/S0747-7171(08)80013-2},
url = {https://doi.org/10.1016/S0747-7171(08)80013-2},
note = {\url{https://doi.org/10.1016/S0747-7171(08)80013-2}}
}
@misc{Dupont2026,
author = {Dupont, Emilien and Eisenberger, Marvin and Kozlovskii, Borislav and Mehrabian, Abbas and Ruiz, Francisco J. R. and See, Abigail and Zhou, Renfei and Alman, Josh and Vassilevska Williams, Virginia and Balog, Matej},
title = {Improving the Matrix Multiplication Exponent with Modern Optimization and {AlphaEvolve}},
year = {2026},
month = aug,
howpublished = {arXiv:2608.16884v1 [cs.DS]},
eprint = {2608.16884v1},
archivePrefix = {arXiv},
primaryClass = {cs.DS},
doi = {10.48550/arXiv.2608.16884},
url = {https://arxiv.org/abs/2608.16884v1},
note = {Submitted August 17, 2026; PDF dated August 18, 2026. \url{https://arxiv.org/abs/2608.16884v1}}
}
@phdthesis{Stothers2010,
author={Stothers, Andrew James}, title={On the complexity of matrix multiplication},
school={University of Edinburgh}, year={2010},
url={https://era.ed.ac.uk/handle/1842/4734},
note={\url{https://era.ed.ac.uk/handle/1842/4734}}
}
@article{DavieStothers2013,
author={Davie, A. M. and Stothers, A. J.},
title={Improved bound for complexity of matrix multiplication},
journal={Proceedings of the Royal Society of Edinburgh Section A: Mathematics},
volume={143}, number={2}, pages={351--369}, year={2013},
doi={10.1017/S0308210511001648}, url={https://doi.org/10.1017/S0308210511001648},
note={\url{https://doi.org/10.1017/S0308210511001648}}
}
@inproceedings{VassilevskaWilliams2012,
author={Vassilevska Williams, Virginia},
title={Multiplying matrices faster than {Coppersmith--Winograd}},
booktitle={Proceedings of the 44th Annual ACM Symposium on Theory of Computing},
pages={887--898}, year={2012}, doi={10.1145/2213977.2214056},
note={Corrected full version, entitled \emph{Multiplying matrices in $O(n^{2.373})$ time}, July 1, 2014. \url{https://people.csail.mit.edu/virgi/matrixmult-f.pdf}},
url={https://people.csail.mit.edu/virgi/matrixmult-f.pdf}
}
@inproceedings{LeGall2014,
author={Le Gall, Fran\c{c}ois}, title={Powers of Tensors and Fast Matrix Multiplication},
booktitle={Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation},
pages={296--303}, year={2014},
eprint={1401.7714v1}, archivePrefix={arXiv}, url={https://arxiv.org/abs/1401.7714v1},
note={\url{https://arxiv.org/abs/1401.7714v1}}
}
@article{AlmanWilliams2024,
author={Alman, Josh and Vassilevska Williams, Virginia},
title={A Refined Laser Method and Faster Matrix Multiplication},
journal={TheoretiCS}, volume={3}, eid={21}, year={2024},
doi={10.46298/theoretics.24.21}, url={https://theoretics.episciences.org/14213},
note={First posted 2020; conference version at SODA 2021. \url{https://theoretics.episciences.org/14213}}
}
@misc{DuanWuZhou2023,
author={Duan, Ran and Wu, Hongxun and Zhou, Renfei},
title={Faster Matrix Multiplication via Asymmetric Hashing},
year={2023}, eprint={2210.10173v5}, archivePrefix={arXiv}, primaryClass={cs.DS},
note={FOCS 2023; arXiv version 5, November 28, 2023. \url{https://arxiv.org/abs/2210.10173v5}},
url={https://arxiv.org/abs/2210.10173v5}
}
@misc{VXXZ2023,
author={Vassilevska Williams, Virginia and Xu, Yinzhan and Xu, Zixuan and Zhou, Renfei},
title={New Bounds for Matrix Multiplication: from Alpha to Omega},
year={2023}, eprint={2307.07970v2}, archivePrefix={arXiv}, primaryClass={cs.DS},
note={SODA 2024; arXiv version 2, November 4, 2023. \url{https://arxiv.org/abs/2307.07970v2}},
url={https://arxiv.org/abs/2307.07970v2}
}
@misc{MoreAsymmetry2026,
author={Alman, Josh and Duan, Ran and Vassilevska Williams, Virginia and Xu, Yinzhan and Xu, Zixuan and Zhou, Renfei},
title={More Asymmetry Yields Faster Matrix Multiplication},
year={2026}, eprint={2404.16349v3}, archivePrefix={arXiv}, primaryClass={cs.DS},
note={First posted 2024; SODA 2025; version 3, August 19, 2026. \url{https://arxiv.org/abs/2404.16349v3}},
url={https://arxiv.org/abs/2404.16349v3}
}
@article{Bini1980,
author={Bini, Dario},
title={Relations between exact and approximate bilinear algorithms. Applications},
journal={Calcolo}, volume={17}, number={1}, pages={87--97}, year={1980},
doi={10.1007/BF02575865}, url={https://doi.org/10.1007/BF02575865},
note={\url{https://doi.org/10.1007/BF02575865}}
}
==== END Staggered-extraction-for-exact-matrix-multiplication-over-every-field//references.bib ====