On the coordinates of minimal vectors in a Minkowski-reduced basis
DOI:
https://doi.org/10.17398/Keywords:
Dirichlet-Voronoi cell, minimum vector of a lattice, Minkowski-reduction, admissible centering, positive quadratic formsAbstract
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.
Downloads
References
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, 1987.
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. Math. 40 (1850), 279 – 290.
Á.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, 145 – 148.
S.S. Ryskov, On Hermite, Minkowski and Venkov reduction of positive quadratic forms in n variables (Russian), Soviet Math. Dokl. 13 (1972), 1676 – 1679.
S.S. Ryskov, The theory of Hermite-Minkowski reduction of positive definite quadratic forms (Russian), Zap. Naučn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 33 (1973), 37 – 64.
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”, Univ. Lecture Ser., 48, American Mathematical Society, Providence, RI, 2009.
P.P. Tammela, On reduction theory of positive quadratic forms (Russian), Zap. Naučn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 50 (1975), 6 – 96, 195.
P.P. Tammela, The minkowski reduction domain for positive quadratic forms of seven variables (Russian), Zap. Naučn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 67 (1977), 108 – 143, 226.
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 (Russian), Trudy Mat. Inst. Steklov. 152 (1980), 97 – 123, 237. Correction: N.V. Novikova, Three admissible centerings of eight-dimensional lattices (Russian), Deposited in VINITI No. 4842-81, Dep. 1981, I.8.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 The author
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
