2023/05/31 by Yael Eisenberg, Eisenberg, Yael, Itamar Rot +3
Computer Science · Mathematics · #Coding theory and cryptography #Computational Complexity (cs.CC) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Approximation and Integration #Metric Geometry (math.MG) #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.2305.19777
openalex publication_date 2023/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given an arbitrary basis for a mathematical lattice, to find a ``good" basis for it is one of the classic and important algorithmic problems. In this note, we give a new and simpler proof of a theorem by Regavim (arXiv:2106.03183): we construct a 18-dimensional lattice that does not have a basis that satisfies the following two properties simultaneously: 1. The basis includes the shortest non-zero lattice vector. 2. The basis is shortest, that is, minimizes the longest basis vector (alternatively: the sum or the sum-of-squares of the basis vectors). The vectors' length can be measured in any ℓq norm, for q∈ ℕ+ (albeit, via another lattice, of a somewhat larger dimension).