CS Paper Radar

Bounds on the real tensor rank of octonion multiplication

Hardik Jain

cs.CC ·submitted 2026-08-17 14:48 UTC · v1
theorycode/data

Abstract

The tensor rank of a bilinear map is the least number of multiplications any bilinear algorithm needs to compute it; for the multiplication of an algebra it measures how cheaply the algebra can be multiplied at all. For the even-dimensional real normed division algebras it is $3$ for the complex numbers and $8$ for the quaternions, both classical, while for the octonions $\mathbb{O}$ only a range was known: at least $15$ (Fiduccia and Zalcstein, 1977) and at most $30$ (Cariow and Cariowa). We prove $$18 \le \operatorname{R}_{\mathbb{R}}(T_{\mathbb{O}}) \le 25.$$ The lower bound peels the eight slices of $T_{\mathbb{O}}$ down to two and bounds the rank of the surviving pencil through the octonion norm. Nothing in it is special to dimension $8$: the same steps give $\operatorname{R}_{\mathbb{R}}(T_A) \ge \frac{5}{2}n - 2$ for every real normed division algebra $A$ of even dimension $n$, sharp for $\mathbb{C}$ and $\mathbb{H}$ and the best bound we know for $\mathbb{O}$. The upper bound is a separate construction, an explicit rank-$25$ decomposition certified by a Krawczyk argument, in exact rational arithmetic, to sit within $10^{-6}$ of an exact one. The same two arguments pin down the rank of a smaller three-slice quaternion tensor $τ$, giving $\operatorname{R}_{\mathbb{R}}(τ) = 7$. The Lean 4 kernel checks the lower bounds and the Krawczyk existence principle; the accompanying scripts check the certificate's finitely many exact-rational inequalities.

Comment
Code at https://github.com/hxrdxkxvxd/octonion-rank

Closest papers

Nearest neighbours by meaning across the whole index.

A lower bound for $\langle 3,2,m \rangle$ matrix multiplication

cs.CC cs.DS ·2026-09-18 ·Askar Tsyganov, Uliana Parkina, Sergey Samsonov, Maxim Rakhuba
theorycode/data similarity 0.62
Abstract

We prove that, over any field, the bilinear complexity of multiplying a $3\times 2$ matrix by a $2\times m$ matrix is strictly greater than $24m/5$. In particular, every exact bilinear algorithm for multiplying a $3\times 2$ matrix by a $2\times 5$ matrix requires at least $25$ multiplications. Together with the Hopcroft-Kerr upper bound, this proves that the $\langle 3,2,5\rangle$ matrix multiplication tensor has rank exactly $25$. The proof has been formally verified in Lean 4, with the formalization available at https://github.com/fallnlove/mm325_proof.

0.25

Tensor value and the 9/4 bound for matrix multiplication

cs.CC math.RT ·2026-11-06 ·Mahmut Levent Doğan, Vladimir Lysikov, Keiya Sakabe, Michael Walter
theory similarity 0.58
Abstract

We give an exposition of OpenAI's recent result that the exponent of matrix multiplication is at most 9/4 valid over every field. Our main tool is a fractional symmetrized variant of the tensor value introduced by Coppersmith and Winograd, used in place of spectral points (tensor characters) in the original proof. We prove a superadditivity inequality for a power of this value on partially direct sums, whose summands share one tensor factor and occupy independent subspaces in the other two. Together with the degenerations of polynomial multiplication tensors from the OpenAI proof, this inequality yields the bound.

0.08

Quasilinear multiplication in the Cayley-Dickson tower

cs.SC math.RAmath.NA ·2026-09-10 ·Harrison Lemley
code/data similarity 0.58
Abstract · 28 pages, 2 tables. v2: title changed from 'Quasilinear multiplication in the real Cayley--Dickson tower'; results generalized from $\mathbb…

Direct evaluation of the defining product of the Cayley-Dickson algebra $A_n$ of rank $N:=2^n$ over a unital commutative ring $R$ in which $2$ is invertible requires a quadratic number of arithmetic operations. This paper gives a uniform bilinear algorithm for multiplication in this algebra costing $O(N \log N)$ arithmetic operations in $R$ and $O(N)$ auxiliary storage when the doubling parameters of $A_n$ are units whose square roots lie in a fixed commutative coefficient algebra $S$ finitely generated as an $R$-module and admitting an $R$-linear map $π\colon S \to R$ with $π(1) = 1$. In particular, over $\mathbb{R}$ and every finite field $\mathbb{F}_{q}$ of odd characteristic, a quadratic field extension contains a square root of every possible doubling parameter, so the algorithm applies to every Cayley-Dickson tower over these fields, and the tensor rank of multiplication in $A_n$ over them is at most $(9n-21)2^n+28$ when $n\ge2$. When the top doubling parameter is a non-square, as in the standard real tower, the bound is $(9n-15)2^{n-1}+10$. To the author's knowledge, the algorithm presented in this paper is the first uniform subquadratic algorithm for multiplication in $A_n$. When $R=\mathbb{R}$ with every doubling parameter equal to $-1$, the real quasilinear schedule uses fewer total arithmetic operations than both direct multiplication and a uniform algorithm of Cariow-Cariowa for $n\ge4$. An implementation for the standard real tower is available in the MIT-licensed C11 library fastCD, with a NumPy-backed Python interface. In single-core benchmarks against direct multiplication and the uniform Cariow-Cariowa method, the quasilinear implementation had the lowest mean time of the three at every tested dimension $N\ge32$, for both single and batched products, and was over $17$ times faster than direct multiplication at $N=1024$.

0.34

New lower bounds on tensor rank of $(n,2,m)$ matrix multiplication with GPT-6

cs.CC ·2026-09-13 ·Jason Yang
theory similarity 0.57
Abstract · 8 pages, improvement for (n,2,m) with m and n at least 4

The tensor rank of $n\times 2$-with-$2\times m$ matrix multiplication is at least $\left\lceil \frac{24m+2}{5} \right\rceil$ if $m\ge n=3$ and at least $(n+2)m+n-3$ if $m\ge n\ge 4$, over arbitrary fields. This result matches the Hopcroft-Kerr upper bound for $n=3$ and $m\le 6$.

0.47

Certified local rank and uniqueness barriers for a 48-term matrix-multiplication decomposition

cs.SC cs.CC ·2026-09-11 ·Abhinav Agarwal
theoryhot direction similarity 0.57
Abstract

We study replacements in fixed bilinear tensor decompositions, counting changes to complete rank-one summands, including output factors. The shortening frontier records the maximum rank defect of a fixed-size subset and determines the minimum length attainable within a change budget. For the rational 48-term Li--Wang--Hu decomposition \(D(2)\) of \(4\times4\) matrix multiplication over \(\mathbb{C}\), we prove rank radius at least 12, strong radius exactly 11, and border radius at least 8. Every shorter complex decomposition therefore changes at least thirteen original summands. An exact rational twelve-term replacement attains the equal-length barrier. The proofs combine exhaustive support reductions with saturated projected kernels and zero-corner completion arguments controlling arbitrary minimal competitors. A reduced-incidence argument transfers kernel certificates to tensor-space neighborhoods. A Laurent normal form gives strong radius exactly 11 for the sixteen-term core at every nonzero complex parameter. On a nonempty Zariski-open subset of the actual parameter curve, the rank radius is at least 12, the strong radius exactly 11, and the border radius at least 8. We also prove incomparability of the full Kothari--Moitra--Wein sufficient criterion and the Sylvester-equipped kernel criterion. These results describe local decomposition structure rather than a new rank bound for full matrix multiplication.

0.25

The rank of 3x3 matrix multiplication over F2 is 23

cs.CC math.RA ·2026-10-08 ·Tejasvi Singh Tomar
theorycode/data similarity 0.57
Abstract · 18 pages. Kernel-only Lean proof: https://github.com/tejasvi/rank333-f2-kernel (archived at https://doi.org/10.5281/zenodo.23304899). Lean p…

The rank of the tensor of $3\times 3$ matrix multiplication over the field with two elements is at most $23$ by Laderman's algorithm, and Rudich and Rousseau recently proved that it is at least $22$. We prove that it equals $23$. Hence Laderman's algorithm uses the fewest multiplications among all bilinear algorithms over $\mathbb{F}_2$ and among all bilinear algorithms with integer coefficients. The proof uses the substitution method in the form developed by D'Ambrosio, Wang and Yang et al., which bounds the number of first factors of a decomposition that lie in a given subspace of the space of first factors. We sharpen these bounds for $111$ of Wang's $496$ classes of subspaces, constrain the ranks of the first factors through a $27\times 27$ flattening of the tensor, and list, up to symmetry, all sets of $22$ first factors that satisfy these constraints. An exact completion search shows that none of them is the set of first factors of a decomposition. The computation emits certificates, which are checked in the Lean 4 proof assistant. In one formal proof the largest checks are evaluated as compiled code, and in a second one the kernel evaluates every check, so that its final theorem depends only on the three standard axioms of Lean. The Lean proofs build on the formalization of Rudich and Rousseau and import their table of bounds and their reduction for block algorithms.

0.22

Disjoint and nearly disjoint sums of matrix multiplication tensors and their centroids

cs.CC math.AGmath.ACmath.RA ·2026-08-27 ·Martin Kassabov, J. M. Landsberg, Victor Souza, Philip Speegle
theory similarity 0.55
Abstract · 52 pages, 3 figures

This paper addresses centroids, which are fundamental invariants of tensors. Our main results are as follows: (i) The construction of explicit tensors with very large centroids, whereas previously it had been conjectured that none such exist. (ii) An upper bound on the dimension of the centroid that is essentially attained by our examples. (iii) The development of a geometric technique to write down border rank decomposition of tensors using centroids and "extended centroids". (iv) The technique is applied to tensors of this paper to prove they are of minimal border rank. The technique is versatile and enables us to geometrically derive and improve upon previous ad hoc decompositions. (v) The construction of symmetric tensors with large centroids and proof that they are wild in the sense of Buczyńska-Buczyński. Our results also pave the way for new upper bounds on the exponent of matrix multiplication. The geometric technique also constructs new "better" tensors for Strassen's laser method from old, and we apply this to the tensors of Strassen and Schönhage to get better tensors in the sense that they give better upper bounds on the exponent than the original tensors.

0.46

Latin cubes of order $4$ and $4320$-point quaternionic constructions in ${\mathbb R}^{16}$

cs.IT math.CO ·2026-10-31 ·Rustem Takhanov
theory similarity 0.54
Abstract

Possibly the most enduring lower-bound record for kissing numbers in dimensions greater than $8$ (excluding $24$) is $$ κ_{16}\geq 4320. $$ This lower bound is attained by a shell of the famous Barnes--Wall lattice, which was discovered in 1959. Besides this configuration, at least one alternative $4320$-point kissing arrangement is currently known. Recently, it was noticed that all these configurations can be described in terms of the so-called quaternionic construction, a general type of construction that was instrumental in explaining the geometry of the $841$-point kissing arrangement in ${\mathbb R}^{12}$. We give a simple generalization of quaternionic constructions in ${\mathbb R}^{16}$ obtained from record configurations. They are parameterized by three Latin cubes of order $4$, six permutations of $3$-element set, and are all infinitesimally jammed. Computer-aided counting shows that there are $4\,072\,728\,621$ isometry classes in this family of $4320$-point kissing arrangements.

0.16