Research · Papers · Direct sums, wedges and the p14 frontier · ML-086
Ineffectiveness of 3-tensor slice rank for multiplicative complexity bounds
srank(T) ≤ m implies MC ≥ ⌈srank(T)/3⌉ ≤ ⌈m/3⌉ < m, which fails to improve upon the trivial linear dimension floor m
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity measures the minimum number of multiplication steps needed to evaluate a system of equations in binary logic. Researchers have tested whether tensor slice rank—a tool from combinatorics that measures how easily multidimensional tables break into simple slices—can prove lower bounds on this count.
This work shows that 3-tensor slice rank cannot produce useful lower bounds. Any system of m quadratic equations splits into m slices along the output index, capping the slice rank of the corresponding order-3 tensor at m. When converted into a circuit lower bound, this yields at most ceil(m / 3) multiplications. Because calculating m independent outputs already requires at least m operations, the slice rank bound falls below the baseline floor. This closes 3-tensor slice rank as a way to beat trivial linear baselines.
Result
Let T be the order-3 tensor over F_2 representing a system of m quadratic forms in n variables. The slice rank of T satisfies:
srank(T) <= m
The resulting lower bound on multiplicative complexity:
MC >= ceil(srank(T) / 3) <= ceil(m / 3) < m
fails to improve upon the trivial linear dimension floor dim(V) = m or the MF-137 packing lemma for any system of Boolean forms.
Setting and definitions
Let f = (f_1, ..., f_m) be a system of m quadratic forms over F_2 in n Boolean variables, corresponding to an order-3 tensor T ∈ F_2^(n x n x m).
Following Tao (2016) and the partition rank framework of Naslund (2020), the slice rank srank(T) is the minimum number of 1-slice tensors whose sum equals T. A 1-slice in F_2^(n x n x m) is a tensor u ⊗ M, where u is a vector along one mode and M is an order-2 matrix across the remaining two modes. Multiplicative complexity MC(f) is the minimum number of bilinear multiplications (AND gates) in a straight-line program computing f over F_2.
Method
Decomposing T along the third mode (the output index) yields an explicit slice cover. Because T consists of m matrix slices T(:,:,k) for k = 1, ..., m, expressing T as the sum of m 1-slices of the form e_k ⊗ T(:,:,k), with e_k the standard basis vector in F_2^m, yields srank(T) <= m.
Applying the standard tensor rank relation MC >= ceil(srank(T) / 3) caps the resulting lower bound at ceil(m / 3). The certificate and formal derivation are recorded in wave2-slice-rank/slice_rank_audit.json.
Discussion
Order-3 tensor slice rank and partition rank methods cannot surpass the linear dimension floor m for systems of Boolean forms over F_2. Because spanning an m-dimensional output space requires at least m operations, the ceil(m / 3) upper bound is strictly sub-linear in the output dimension.
Under the bilinear / tensor rank cost model, 3-tensor slice rank cannot yield non-trivial circuit lower bounds. Non-trivial tensor bounds require higher-order formulations that prevent single-mode slice projections along output coordinates.
For everyone — the takeaway
What this means
Proving that a calculation requires many multiplication steps is a fundamental challenge in circuit complexity. Slice rank solved major open problems in combinatorics, prompting researchers to test whether it could prove strong circuit lower bounds for quadratic systems.
This result shows that 3-dimensional slice rank is capped strictly below the number of equations in the system. Because simple counting already gives a higher baseline, 3-tensor slice rank cannot prove non-trivial circuit lower bounds. Future tensor-based lower bound methods must use higher-dimensional representations instead.
Attribution and prior art
Prior art: This result builds on tensor slice rank and partition rank techniques introduced by Tao (2016) and Naslund (2020).
Register references
- Register entry: ML-086
- Receipt:
wave2-slice-rank/slice_rank_audit.json - Prior art: Tao (2016), Naslund (2020), MF-137 packing lemma
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 1 of 1 receipt files bundled (2 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-04
- 2026-09-04Published on this site.