Minkowski bases, Korkin-Zolotarev bases and successive minima

2021/06/06 by Shvo Regavim, Regavim, Shvo · 1 citation
Computer Science · Engineering · #11H55 #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #Number Theory (math.NT) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2106.03183

openalex publication_date 2021/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let λ_k denote the k-th successive minimum of a lattice L. We study properties of the lengths of certain bases of L. If v₁, … v_n is a basis which is reduced in the sense of Minkowski we show that | v_k |² ≤ (k)/(4) λ_k² for k = 6, 7, confirming a conjecture of Schürmann, and obtaining the first improvement of a classical bound by Van der Waerden. We construct a sequences of lattices where | v_n | is significantly longer than the longest vector in a Korkin-Zolotarev reduced basis, answering a question of Schürmann. In an appendix joint with Lior Hadassi we construct a lattice L with the surprising property that any basis containing the shortest vector of L is not the shortest basis.

Cited by

• On the Shortest Lattice Vector vs. the Shortest Basis

Related

• Strongly Reduced Lattice Bases
• Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases
• Upper and lower bound on the cardinality containing shortest vectors in a lattice reduced by block Korkin-Zolotarev method (Russian)
• A Minkowski-type theorem on distances to cusps: the class number one case
• On the coordinates of minimal vectors in a Minkowski-reduced basis