Deciding whether a lattice has an orthonormal basis is in co-NP
Abstrak
AbstractWe 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 \in \mathbb {Q}^{n \times n}$$ 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 \in \mathbb {Q}^{4n \times n}$$ B ∈ Q 4 n × n such that $$B^\intercal B = G$$ B ⊺ B = G .
Penulis (1)
Christoph Hunkenschröder
Akses Cepat
- Tahun Terbit
- 2024
- Bahasa
- en
- Sumber Database
- CrossRef
- DOI
- 10.1007/s10107-023-02052-1
- Akses
- Open Access ✓