Minimal condition for shortest vectors in lattices of low dimension

Juhee Lee, Seunghwan Chang, Taewan Kim, Hyang Sook Lee, Seongan Lim

Research output: Contribution to journalArticlepeer-review


For a lattice, finding a nonzero shortest vector is computationally difficult in general. The problem becomes quite complicated even when the dimension of the lattice is five. There are two related notions of reduced bases, say, Minkowski-reduced basis and greedy-reduced basis. When the dimension becomes d = 5, there are greedy-reduced bases without achieving the first minimum while any Minkowski-reduced basis contains the shortest four linearly independent vectors. This suggests that the notion of Minkowski-reduced basis is somewhat strong and the notion of greedy-reduced basis is too weak for a basis to achieve the first minimum of the lattice. In this work, we investigate a more appropriate condition for a basis to achieve the first minimum for d = 5. We present a minimal sufficient condition, APG + , for a five dimensional lattice basis to achieve the first minimum in the sense that any proper subset of the required inequalities is not sufficient to achieve the first minimum.

Original languageEnglish
Pages (from-to)9-14
Number of pages6
JournalElectronic Notes in Discrete Mathematics
StatePublished - Mar 2019


  • greedy-reduced basis
  • lattice
  • Minkowski-reduced basis
  • shortest vector problem


Dive into the research topics of 'Minimal condition for shortest vectors in lattices of low dimension'. Together they form a unique fingerprint.

Cite this