CS Paper Radar

Maximal rank of $4\times 4\times 4$ and $k\times 4\times 3$ tensors over $\mathbb{F}_2$

Jason Yang

cs.SC math.CO ·submitted 2026-09-04 18:30 UTC · v1

Abstract

We determine the maximum rank of $4\times 4\times 4$ and $k\times 4\times 3$ multidimensional arrays over the finite field $\mathbb{F}_2$. These results are made possible by a new method of enumerating non-isomorphic tensors.

Comment
11 pages

Closest papers

Nearest neighbours by meaning across the whole index.

A Lower Bound of 21 for $3\times3$ Matrix Multiplication over $\mathbb{F}_2$

cs.CC cs.DS ·2026-09-06 ·Chengu Wang
theory similarity 0.60
Abstract

We prove that $3\times3$ matrix multiplication over $\mathbb{F}_2$ has bilinear complexity at least $21$, improving the previous lower bound of $20$. Lower bounds for restrictions of the first input constrain how many first factors of a decomposition can lie in each subspace. For a hypothetical $20$-term decomposition, the strengthened restriction bounds force all first factors of matrix rank at least two into a single coset of a three-dimensional rank-one subspace. An exhaustive computation finds no admissible first-factor profile with $20$ terms. We also prove that $2\times3$ by $3\times3$ matrix multiplication over $\mathbb{F}_3$ has rank exactly $15$: three profiles with $14$ terms survive the corresponding computation up to symmetry, and short restriction arguments exclude them. We combine Wang's automated framework for tensor-rank lower bounds with D'Ambrosio's capacity-and-profile strategy. Our computational contributions are rank-one-span searches that strengthen the subspace lower-bound table and a direct, symmetry-reduced profile enumerator that enforces all subspace capacities simultaneously.

0.28

A Structural Proof of the Lower Bound 21 for $3\times3$ Matrix Multiplication over $\mathbb F_2$

cs.CC cs.DScs.SC ·2026-09-16 ·Shuxing Yang, Rui Zhao, Junyao Wu, Yize Wang, Wenhao Li +11 more
theorycode/data similarity 0.59
Abstract · 27 pages. Complete Lean formalization, finite certificates, source code, and reproducibility materials are available in the accompanying pub…

We prove that the tensor rank of $3\times3$ matrix multiplication over $\mathbb F_2$ is at least $21$. The structural proof, independently developed by Qiushi Engine, converts occupation constraints on a single tensor factor into algebraic relations coupling all three factors. Certified quotient-rank bounds and finite geometry force any hypothetical $20$-term decomposition to have first-factor matrix-rank profile $(16,1,3)$. The ranks of the corresponding split-flattened summands therefore sum to $27$, exactly the rank of the full split flattening. Equality in rank subadditivity forces their images to form a direct sum; normalization by the inverse flattening then makes the summands pairwise annihilating idempotents. An explicit product identity for matrix multiplication implies that at most one first factor can be invertible, contradicting the three forced by the profile. The same obstruction constrains $22$-term decompositions attaining the split-rank bound. The complete proof, including the finite quotient bounds, is formalized in Lean. The accompanying research trajectory records Qiushi Engine's long-horizon autonomous research, from numerical experiments and quotient constructions to the structural proof.

0.24

The rank of 3x3 matrix multiplication over F2 is 23

cs.CC math.RA ·2026-10-08 ·Tejasvi Singh Tomar
theorycode/data similarity 0.58
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

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.57
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

Border rank=rank for Kruskal tensors and a Kruskal's theorem for skew decompositions

cs.DS math.AG ·2026-08-21 ·Alexander Taveira Blomenhofer, Benjamin Lovitz
theory similarity 0.56
Abstract · 33 pages

We show that border rank is equal to rank for Kruskal tensors. We also give an analogous Kruskal condition for alternating tensors, which certifies uniqueness of skew rank decompositions. Furthermore, we show that border skew rank is equal to skew rank for alternating Kruskal tensors, and we give an algorithm to find the minimum skew rank decomposition of alternating Kruskal tensors.

0.49

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.54
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.48

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.53
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

Concise tensors with maximal symmetries

cs.CC math.AGmath.GR ·2026-09-15 ·Annika Holtrup, Jeroen Zuiddam
theory similarity 0.52
Abstract

Conner, Gesmundo, Landsberg and Ventura (2019) determined the largest stabilizer dimension of concise $n\times n \times n$ tensors that are binding, and they determined the corresponding maximizing tensors to be the null algebra tensors. They left as an open problem to extend this to all concise $n \times n \times n$ tensors (i.e. dropping binding). We solve this problem: We prove that the largest stabilizer dimension of concise $n\times n\times n$ tensors is $n^2 + 1$ and the maximizers are the null algebra tensors (as in the binding case) and the skew symmetric tensor $e_1 \wedge e_2 \wedge e_3$. As part of our approach we obtain upper bounds on the stabilizer dimension of matrix tuples under left-right action (generalized Kronecker quiver representations), which we think are of independent interest.

0.27