CS Paper Radar

Integral Tensor Isomorphism via Cubic Rings and Lattice Methods

Thomas Huffstutler

cs.CC quant-ph ·submitted 2026-11-17 18:30 UTC · v1
theory

Abstract

We prove that isomorphism of integral $2\times3\times3$ tensors under $\mathrm{GL}_2(\mathbb{Z})\times\mathrm{GL}_3(\mathbb{Z})\times\mathrm{GL}_3(\mathbb{Z})$ is decidable in bounded-error quantum polynomial time. For a tensor $T=(A,B)$ with nonzero determinant form $\det(xA-yB)$, we use the parametrization of Wood by balanced modules to reduce the isomorphism problem to principality tests for compatible lattices, and use the algorithms of Bley, Hofmann, and Johnston to solve this in BQP. When the determinant form vanishes identically, we get either an integral $2\times2\times2$ core, or a polynomial kernel vector of degree one or two. The linear-kernel case yields another compatible lattice problem, while the quadratic-kernel case reduces to a fixed system of polynomial congruences and unimodular lifting. A quantifier-elimination argument decides these congruences in deterministic polynomial time given the prime factorization of the modulus, which quantum integer factorization supplies. Finally, we show that zero padding preserves integral $2\times2\times2$ tensor isomorphism, yielding a polynomial-time reduction from real-quadratic principality to the identically singular $2\times3\times3$ problem.

Comment
51 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.CC math.ACmath.NT ·2026-10-31 ·Joshua A. Grochow, Youming Qiao, Katherine E. Stange, Xiaorui Sun
top venuehighly cited similarity 0.63
Abstract · 74 pages, extended abstract appeared at STOC'25, abstract shortened to meet arXiv requirement

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: $\mathsf{3TI}_\mathrm{R}$ consisting of problems that are polynomial-time reducible to isomorphism problems of tensor products of three modules over $\mathrm{R}$, and $\mathsf{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 $\mathsf{3FTI}_\mathbb{Z}$-complete. We also show that many natural problems are complete for $\mathsf{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$.

0.73

The rank of 3x3 matrix multiplication over F2 is 23

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

NP-hardness of ideal lattice problems

cs.CC math.NT ·2026-09-14 ·Daniel E. Martin
similarity 0.59
Abstract · 27 pages, 2 figures

We establish the worst-case hardness of several ideal lattice problems (including SVP and CVP) in the $\ell_2$ norm by providing a dimension-preserving, deterministic polynomial time reduction from their generic lattice versions. The reduction constructs an ideal lattice in the canonical embedding of a number field that approximates some input lattice up to scaling and orthogonal transformation. The integers defining the ideal and the ambient number ring, in particular its discriminant, are all polynomial in bit length relative to the generic input lattice. Furthermore, the ideal is invertible, the ring is monogenic, and the number field is totally real. If the number ring is also required to be a full ring of integers, the reduction conjecturally succeeds in bounded-error quantum polynomial time.

0.32

A Dichotomy for Cubic Bipartite Holant Problems with Complex Algebraic Weights

cs.CC ·2026-09-27 ·Yin Liu
similarity 0.59
Abstract · 87 pages. Supplementary polynomial certificates and verification code included. Corrected author metadata; manuscript unchanged

We classify the exact evaluation of $\operatorname{Holant}(f\mid=_3)$ for every fixed complex algebraic symmetric Boolean ternary signature $f$. An input is a cubic bipartite multigraph: every vertex on one side carries $f$, every vertex on the other side carries ternary equality, and no auxiliary signatures are freely available. The tractable signatures are precisely rank-one tensors, generalized equalities, and equality-preserving cube-root diagonal transformations of six affine signatures, together with nonzero scalings and reversal. Every other signature gives a $\#\mathrm{P}$-hard problem under polynomial-time Turing reductions. We also identify the exact real intersection: it consists of the same tractable families as in the rational classification, with real algebraic parameters. The proof preserves degree exactly three on both sides of every oracle instance. A rank-one matrix extracted by interpolation supplies one unary signature only after its unused factor has been absorbed in triples. Over the complex numbers this absorption has three exceptional projective directions. We combine this constraint with projective matrix-group orbits, explicit ternary replacements, and an exhaustive treatment of finite projective orders. The cases of orders three and five include exact polynomial certificates; the certificate identities and a rational-arithmetic verifier are supplied as supplementary material.

0.13

Exponential Lower Bounds for Products of Cubic Polynomials over Prime Fields

cs.CC ·2026-11-02 ·Bin Fu, Yunhui Fu
theory similarity 0.58
Abstract

We study exact representations of explicit signed modular predicates on $\{-1,1\}^n$ as products of bounded-degree polynomials over prime fields, measured by total variable-occurrence cost. Our main result is an exponential lower bound for products of cubic polynomials. Over $\mathbb F_3$ the proof is self-contained: every cubic factor in a nonvanishing product is a unit on the sign cube, the unit identity forces bounded affine-observation complexity, and a simultaneous clustering argument converts this structural compression into an exponential occurrence lower bound. We also give an alternative reconstruction route that isolates the quadratic structure behind the cubic classification. We then extend the cubic theorem to every fixed prime field $\mathbb F_p$ of characteristic greater than three for odd target modulus $q$ coprime to $p$. The only non-elementary structural input in this extension is Karam's restricted-range rank theorem; the conversion from multiplication to parity and the $p$-tuple clustering argument are proved explicitly. Finally, we establish a coefficient-field-independent degree-lifting principle. If a lower bound is known at one fixed degree, restriction to a large independent set yields a quantitative lower bound at the next degree. In particular, the exponential cubic theorem implies $ L^{(p,q)}_4(n)=Ω_{p,q}\!\left(\frac{n^4}{(\log(2+n))^3}\right). $ For the characteristic-three core this already gives a lower bound for a restricted mixed-modulus circuit class.

0.17

Euclidean SVP is NP-hard for Cyclic Lattices

cs.CC ·2026-09-15 ·Daqing Wan
theory similarity 0.57
Abstract · 39 pages

We prove that exact Euclidean SVP is NP-hard under deterministic polynomial-time many-one reductions for full-rank cyclic integer lattices, equivalently full-rank ideals of $R_N:=\mathbb{Z}[X]/(X^N-1)$ in the coefficient norm. Hardness holds with $N=q-1$ for a varying odd prime $q$. As an application, we prove the same hardness for the algebraic class of NTRU-form lattices $\{(x,z)\in R_N^2:Hx\equiv z\pmod{QR_N}\}$, where $H,Q$ are unrestricted inputs. The decision problems are NP-complete, and the exact search problems are NP-hard under polynomial-time Turing reductions. No hardness claim is made for cryptographic NTRU parameter subclasses or key-generation distributions.

0.40

On Applications of Polynomial-Time Group Isomorphism Algorithm

cs.CC ·2026-11-13 ·Wenkang Zhang, Zhinan Wang, Jincheng Zhuang
similarity 0.57
Abstract · 10 pages

The group isomorphism problem is a fundamental problem in computational group theory and is closely related to many other problems. Recently, Qiao and Zhang proposed a polynomial-time algorithm for finite group isomorphism in the multiplication-table model that computes the coset of all isomorphisms. Based on the algorithm of Qiao and Zhang, we study applications to finite associative ring isomorphism, bilinear map isotopism over finite commutative rings and free three-tensor isomorphism over finite commutative rings. First, we obtain a polynomial-time algorithm that returns the coset of all isomorphisms for finite associative rings. Second, we extend efficient isotopism and isomorphism algorithms for bilinear maps and free three-tensors from fields to general finite commutative rings.

0.22

Tensor--Action Ko--Lee Cryptography: A Framework and Structural Cryptanalysis of Commuting Subgroup Constructions

cs.CR ·2026-08-15 ·Ziyan Chen, Yuqiao Wang
similarity 0.57
Abstract · 28 pages, 3 images, 1 table

Tensor isomorphism has been studied as an algebraic problem relevant to post-quantum cryptography, while its use in public-key encryption remains open. In this paper, we formulate a Ko--Lee-style framework for public-key encryption from cubic tensor actions and prove its formal correctness. We then show that the framework is generically insecure when the commuting matrix subgroups are given by public finite generating sets. Viewing a cubic tensor as a vector in a $d^3$-dimensional space, a linear decomposition attack recovers the shared tensor from the public transcript in polynomial time without recovering either secret action. We also cryptanalyze three natural commuting-subgroup constructions---field-extension, block-diagonal, and tensor-product constructions---and give toy-scale experiments illustrating their specific structural leakage. Finally, we examine the lower-dimensional leakage caused by scaled-block structure. The contribution is therefore a framework proposal together with its cryptanalysis; it does not provide a secure public-key encryption scheme.

0.10