1. Deciding whether a lattice has an orthonormal basis is in co-NP.
- Author
-
Hunkenschröder, Christoph
- Subjects
- *
ORTHONORMAL basis , *RIESZ spaces , *EQUATIONS , *INTEGERS , *DECISION making - Abstract
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 ∈ Q n × n , 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 ∈ Q 4 n × n such that B ⊺ B = G . [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF