Deciding whether a lattice has an orthonormal basis is in co-NP
成果类型：
Article
署名作者：
Hunkenschroeder, Christoph
署名单位：
Technical University of Berlin
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-023-02052-1
发表日期：
2024
页码：
763-775
关键词：
摘要：
We show that the problem of deciding whether a given Euclidean lattice L has an orthonormal basis is in NP and co-NP. Since this is equivalent to saying that L is isomorphic to the standard integer lattice, this problem is a special form of the lattice isomorphism problem, which is known to be in the complexity class SZK. We achieve this by deploying a result on characteristic vectors by Elkies that gained attention in the context of 4-manifolds and Seiberg-Witten equations, but seems rather unnoticed in the algorithmic lattice community. On the way, we also show that for a given Gram matrix G is an element of Q(nxn), we can efficiently find a rational lattice that is embedded in at most four times the initial dimension n, i.e. a rational matrix B is an element of Q(4nxn) such that B-T B=G.
来源URL：