Simultaneously good bases of a lattice and its reciprocal lattice
type: Item
instance of: scholarly article
title: Simultaneously good bases of a lattice and its reciprocal lattice
zbMATH Open document ID: 0671.10028
DOI: 10.1007/BF01446883
author: Jeffrey C. Lagarias
author: Johan Hastad
published in: Mathematische Annalen
publication date: 1990-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/164675
review text: Associate to an ordered basis \(B=[{\mathfrak b}_ 1,...,{\mathfrak b}_ n]\) of a lattice L the reciprocal basis \(B^*=[{\mathfrak b}^*_ 1,...,{\mathfrak b}^*_ n]\) of the reciprocal lattice \(L^*\) defined by \(<{\mathfrak b}_ i,{\mathfrak b}^*_{n+1-j}>=0\) if \(i\neq j\) and 1 otherwise. This paper studies the problem of choosing a basis B such that B and \(B^*\) simultaneously consist of short vectors. Let \(\lambda_ i(L)\), \(\lambda_ i(L^*)\) denote the successive minima of L and \(L^*\) respectively. It is shown that every lattice L has an ordered basis such that simultaneously \(\| {\mathfrak b}_ i\| \leq c(n)\lambda_ i(L)\) and \(\| {\mathfrak b}^*_ i\| \leq c(n)\lambda_ i(L^*)\) for \(1\leq i\leq n\), where \(c(n)=\exp (c_ 0n^{1/3})\) and \(c_ 0\) is a positive constant independent of n. This result is obtained by a study of the unipotent group N(n,\({\mathbb{R}})\) of all lower triangular matrices with diagonal entries equal to one, under the action of its discrete subgroup N(n,\({\mathbb{Z}})\). For any M in N(n,\({\mathbb{R}})\) there exists some W in N(n,\({\mathbb{Z}})\) such that \(Max(\| WM\|, \| (WM)^{-1}\|)\leq \exp (cn^{1/3}),\) where c is a positive constant independent of n.
Mathematics Subject Classification ID: 11H06
Mathematics Subject Classification ID: 11H55
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4097485
zbMATH Keywords: ordered basis
zbMATH Keywords: lattice
zbMATH Keywords: reciprocal basis
zbMATH Keywords: reciprocal lattice
zbMATH Keywords: short vectors
zbMATH Keywords: successive minima
zbMATH Keywords: unipotent group
zbMATH Keywords: lattice basis reduction
reviewed by: Johan Hastad
Wikidata QID: Q56959213
MaRDI profile type: Publication
cites work: On Lovász' lattice reduction and the nearest lattice point problem
cites work: Q5611106
cites work: Q4177654
cites work: Dual vectors and lower bounds for the nearest lattice point problem
cites work: Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
cites work: Minkowski's Convex Body Theorem and Integer Programming
cites work: Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
cites work: Q5595275
cites work: Factoring polynomials with rational coefficients
cites work: Q5770049
cites work: A hierarchy of polynomial time lattice basis reduction algorithms
cites work: A more efficient algorithm for lattice basis reduction
OpenAlex ID: W2095141442
Recommended article: Simultaneous reduction of a lattice basis and its reciprocal basis
Recommended article: On lattice bases with special properties
Recommended article: Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
Recommended article: Basis-Homogeneous Geometric Lattices
Recommended article: Lattice Bases of Planar Lattices
Recommended article: On orthogonal bases for rational lattices
Recommended article: On lattices equivalent to their duals
Recommended article: Common hyperbolic bases for chains of alternating or quadratic lattices
Recommended article: Q5580263
Recommended article: Q5592275
description: scientific article; zbMATH DE number 4097485