Paper 2026/1665

Deterministic Almost-All Recovery for Square Four-Tensor Isomorphism

Abstract

We give deterministic exact recovery for almost all square four-tensors over every finite field. For every \(n \ge 2^{24}\) and prime power \(q \ge 2\), an explicit \(\mathrm{GL}_n(\mathbb{F}_q)^4\)-invariant family contains a \(1-O((\log n)^2/n)\) fraction of all \(q^{n^4}\) coefficient arrays, with an explicit failure bound uniform in \(q\). Membership and isomorphism decision and recovery against every target are deterministic in \(\operatorname{poly}(n,\log q)\) bit time, with four invertible factors over the original field. The source distribution is uniform without any conditioning on flattening ranks. The proof combines linked extension-field eigenmatrices, a submodule sieve under the joint law of a matrix and its inverse, and recovery from the kernels of singular original flattenings. Partial traces of matrix products provide a factorization-free algorithm in large characteristic. Complementary results give explicit positive source fractions in smaller dimensions, including a \(1/q+O(q^{-2})\) family with deterministic recovery. The algorithms invert the coefficient-uniform square-tensor group action with the stated success probabilities. A deterministic exhaustive fallback gives total correctness and a polynomial running-time bound with high probability; no polynomial expected running time is claimed.

Note: Major revision. The paper has been retitled and substantially strengthened. The new version proves deterministic exact recovery for a 1-O((log n)^2/n) fraction of coefficient-uniform square four-tensors over every finite field for n >= 2^24, without conditioning on flattening ranks. It adds linked two-sided spectral recovery, recovery from singular original flattenings, a factorization-free large-characteristic branch, and explicit complementary finite-parameter results. A deterministic exhaustive fallback gives total correctness; polynomial expected running time for the total solver is not claimed. This version supersedes the earlier manuscript titled "Nullity-One Canonicalization for Average-Case 4-Tensor Isomorphism."