1970-01-01

(2026-08) Nullity-One Canonicalization for Average-Case 4-Tensor Isomorphism

• Jingchuan Ma
• Yanhua Liu
• Qiaoyun Huang

2026-08-12

• #cryptography
• #paper

Abstract

We study square 4-Tensor Isomorphism over finite fields in the average-case model where the first tensor is uniform and the second is arbitrary. The closest polynomial-time method exploits a higher-dimensional flattening kernel. The denser corank-one stratum occurs on the $1/q$ scale, but its one-dimensional kernel loses the matrix-pair information used by that method. We make this minimal defect algorithmically useful. After normalizing the left and right kernel matrices to the identity, the residual action becomes a pair of adjoint actions on $\mathfrak{sl}_n$. The normalized flattening induces a uniform map $\Phi\in\mathrm{GL}(\mathfrak{sl}_n)$; its two Gram operators yield linked projective spectral matrix pairs. We prove constant-probability scalar common-centralizer bounds for their actual orthogonality-conditioned distribution, recover both residual conjugations without enumerating field elements, and lift them to all four tensor factors.

For every odd prime power $q\geq 5$ and $n\geq 5$ with $\operatorname{char}(\mathbb{F}_q)\nmid n$, this gives a randomized partial algorithm with expected $\operatorname{poly}(n,\log q)$ running time that is correct on at least $c/q$ of uniform first tensors, for an explicit universal $c>0$. Its only randomized components are Las Vegas finite-field subroutines. We also give a complementary large-field result on tensors whose three standard $2|2$ flattenings are invertible. These results concern certified average-case complexity, and both tractable events are efficiently recognizable.