On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V: Over Commutative Rings

Tensors over commutative rings naturally appear in number theory, geometry, and group theory. For example, 2× 2× 2 tensors over ℤ form the starting point of Bhargava’s celebrated works generalising Gauss’s composition law (Bhargava, Ann. Math., 2004). Symmetric tensors over ℤ are central to the classification of Calabi–Yau threefolds (Yau, Commun. Pure Appl. Math., 1978; Wall, Invent. Math., 1966), geometric objects of significance in string theory. Additionally, tensors over finite commutative rings closely correspond to finite nilpotent groups of class 2 (Baer, Trans. Am. Math. Soc., 1938). In these settings, testing isomorphism of tensors is of great interest. For example, in mathematical physics, several recent works apply machine learning techniques to distinguish symmetric tensors from Calabi–Yau threefolds. For group isomorphism, a recent breakthrough of Sun (STOC, 2023) gives the first No(logN)-time algorithm for testing isomorphism of p-groups of class 2 and exponent p of order N, using tensor-based techniques. Grunewald and Segal studied the computability of tensor isomorphism problems over ℤ, showing that they are computable in finite time (Ann. Math., 1980). In this work, we study isomorphism testing of tensors over commutative rings from a complexity-theoretic viewpoint, and its applications. Some of our main results are as follows. Let R be a commutative ring. We introduce two complexity classes: 3TIR consisting of problems that are polynomial-time reducible to isomorphism problems of tensor products of three modules over R, and 3FTIR consisting of problems that are polynomial-time reducible to isomorphism problems of tensor products of three free modules over R. We show that some classical problems considered by Grunewald and Segal (ibid.), and the problem of classifying Calabi–Yau threefolds, are 3FTIℤ-complete. We also show that many natural problems are complete for 3TIℤ/peℤ. We show that testing isomorphism of tensors in ℤ2⊗ℤ2⊗ℤ2 is polynomial-time equivalent to the principal ideal problem in algorithmic number theory. The key to this reduction is Bhargava’s work (Ann. Math., 2004). Using our equivalence, a result of Hallgren (J. ACM, 2007) then implies that 2× 2× 2 tensor isomorphism over ℤ is in quantum polynomial time. We present an NO((logN)8/9)-time algorithm for testing isomorphism of finite nilpotent groups of class 2 and odd order N. This is achieved by considering tensor isomorphism over ℤ/peℤ. Following the strategy of (Sun, STOC, 2023), the algorithm is a reduction to testing the congruence of matrix tuples over ℤ/peℤ, for which we present a polynomial-time solution following and generalizing (Ivanyos–Qiao, SIAM J. Comput., 2019), who solved the analogous problem over finite fields of odd order.