On the complexity of isomorphism problems for tensors, groups, and polynomials V: over commutative rings

Abstract

Tensors over commutative rings naturally appear in number theory, geometry, and group theory. For example, $2\times 2\times 2$ tensors over $\mathbb{Z}$ form the starting point of Bhargava's celebrated works generalising Gauss's composition law (Bhargava, Ann. Math., 2004). Symmetric tensors over $\mathbb{Z}$ 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 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: 1. Let $\mathrm{R}$ be a commutative ring. We introduce two complexity classes: ${3TI}_{\mathrm{R}}$ consisting of problems that are polynomial-time reducible to isomorphism problems of tensor products of three modules over $\mathrm{R}$, and ${3FTI}_{\mathrm{R}}$ consisting of problems that are polynomial-time reducible to isomorphism problems of tensor products of three free modules over $\mathrm{R}$. 2. We show that some classical problems considered by Grunewald and Segal (ibid.), and the problem of classifying Calabi--Yau threefolds, are ${3FTI}_{\mathbb{Z}}$-complete. We also show that many natural problems are complete for ${3TI}_{\mathbb{Z}/p^e\mathbb{Z}}$. 3. We show that testing isomorphism of tensors in ${\mathbb{Z}}^2\otimes {\mathbb{Z}}^2\otimes {\mathbb{Z}}^2$ is polynomial-time equivalent to the principal ideal problem in algorithmic number theory. 4. We present an $N^{O((\log N{)}^{8/9})}$-time algorithm for testing isomorphism of finite nilpotent groups of class $2$ and odd order $N$.

arXiv comment74 pages, extended abstract appeared at STOC'25, abstract shortened to meet arXiv requirement