On the coordinates of minimal vectors in a Minkowski-reduced basis

• Akos G. Horváth ^[1]
  1. [1] Department of Algebra and Geometry, Budapest University of Technology Egry József u. 1, Budapest, Hungary, 1111
• Localización: Extracta mathematicae, ISSN-e 0213-8743, Vol. 40, Nº 1, 2025, págs. 27-41
• Idioma: inglés
• DOI: 10.17398/2605-5686.40.1.27
• Enlaces
  • Texto completo (pdf)
• Resumen

  • Finding the shortest non-zero vectors in a lattice is a computationally hard problem (NP-hard in general dimensions), making results in low dimensions particularly important in lattice reduction theory. This paper focuses on the coordinates of minimal lattice vectors when expressed in a Minkowski-reduced basis. By applying Ryskov’s findings on admissible centerings and Tammela’s work characterizing Minkowski-reduced forms via a finite set of inequalities (up to dimension 6), we demonstrate sharp bounds on the absolute values of these coordinates. Specifically, we show that for dimensions n ≤ 6, the absolute values of the coordinates of any minimal vector with respect to a Minkowski-reduced basis are bounded by 1 (for n = 2, 3), 2 (for n = 4, 5), and 3 (for n = 6). This refines bounds implicitly available from Tammela’s results by combining geometric arguments from lattice theory, admissible centering theory, and reduction theory.

• Referencias bibliográficas
  • L. Afflerbach, Minkowskische Reduktionsbedingungen für positiv definite quadratische Formen in 5 Variablen, Monatsh. Math. 94 (1982), 1 – 8.
  • G. Csóka, On an extremal property of Minkowski-reduced frames (Russian), Studia Sci. Math. Hungar. 13 (1978), 469 – 475.
  • P.M. Gruber, C.G. Lekkerkerker, “Geometry of numbers”, Second Edition, North-Holland Math. Library, 37, North-Holland Publishing Co., Amsterdam,...
  • C. Hermite, Extraits de lettres de M.Ch. Hermite à M. Jacobi sur différents objets de la théorie des nombres, deuxième lettre, J. Reine Angew....
  • Á.G. Horváth, On n-dimensional Minkowski-reduced and Hermite-reduced lattice bases (Hungarian), Mat. Lapok 33 (1982/86), 93 – 98.
  • A. Korkine, G. Zolotareff, Sur les formes quadratiques (French), Math. Ann. 6 (1873), 336 – 389.
  • H. Minkowski, “Geometrie der Zahlen”, Teubner-Verlag, 1896.
  • H. Minkowski, Sur la reduction des formes quadratiques positives quaternaries, in “Gesammelte Abhandlungen I”, Teubner, Leipzig-Berlin, 1911,...
  • S.S. Ryskov, On Hermite, Minkowski and Venkov reduction of positive quadratic forms in n variables (Russian), Soviet Math. Dokl. 13 (1972),...
  • S.S. Ryskov, The theory of Hermite-Minkowski reduction of positive definite quadratic forms (Russian), Zap. Naučn. Sem. Leningrad. Otdel....
  • S.S. Ryskov, On the problem of finding perfect quadratic forms in higher space (in Russian), Trudy Mat. Inst. Steklov. 142 (1976), 215 – 239.
  • A. Schürmann, “Computational geometry of positive definite quadratic forms: polyhedral reduction theories, algorithms, and applications”,...
  • P.P. Tammela, On reduction theory of positive quadratic forms (Russian), Zap. Naučn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 50...
  • P.P. Tammela, The minkowski reduction domain for positive quadratic forms of seven variables (Russian), Zap. Naučn. Sem. Leningrad. Otdel....
  • B.A. Venkov, On the reduction of positive quadratic forms. Izv. Akad. Nauk SSSR Ser. Mat. 4/1 (1940), 37 – 52.
  • N.V. Zakharova, Centerings of eight-dimensional lattices that preserves a frame of successive minima, Geometry of positive quadratic forms...