Simultaneous reduction of a lattice basis and its reciprocal basis

Given a latticeL we are looking for a basisB=[b ₁, ...b _n ] ofL with the property that bothB and the associated basisB ^*=[b ₁ ^* , ...,b _n ^* ] of the reciprocal latticeL ^* consist of short vectors. For any such basisB with reciprocal basisB ^* let . Håstad and Lagarias [7] show that each latticeL of full rank has a basisB withS(B)exp(c ₁·n ^1/3) for a constantc ₁ independent ofn. We improve this upper bound toS(B)exp(c ₂·(lnn)²) withc ₂ independent ofn.We will also introduce some new kinds of lattice basis reduction and an algorithm to compute one of them. The new algorithm proceeds by reducing the quantity . In combination with an exhaustive search procedure, one obtains an algorithm to compute the shortest vector and a Korkine-Zolotarev reduced basis of a lattice that is efficient in practice for dimension up to 30.     

On the best bound of the minimal twisted height of linear subspaces

Let V be a vector space over a global field k, g an element of the adele group and H_g the twisted height defined on the k-subspaces of V . We show that the square root of the generalized Hermite-Rankin constant for k gives the best upper bound of the function , where runs over all m-dimensional k-subspaces of V and runs over all n-dimensional k-subspaces of . Received: 17 June 2005     

Ideal lattices over totally real number fields and Euclidean minima

No Abstract. . Received: 14 February 2005     

A Minkowski-type theorem for covering minima in the plane

For a convex bodyKE ² and a latticeLE ² let _i (K, L),i=1, 2, denote its covering minima introduced by Kannan and Lovasz. We show ₁(K, L) ₂(K, L)V(K)3/4 det(L), whereV denotes the area. This inequality is tight and there are five different cases of equality.     

On Vectors whose Span Contains a Given Linear Subspace

Estimates are given for the product of the lengths of integer vectors spanning a given linear subspace.The first author was supported by FWF Austrian Science Fund, project M672.     

On odd points and the volume of lattice polyhedra

Denote by _n ³ ,n 2, the lattice consisting of all pointsx in ³ such thatnx belongs to the fundamental lattice ³ of points with integer coordinates. Letl _n be the subset of _n ³ consisting of all points whose coordinates are odd multiples of 1/n. The purpose of this paper is to give several new Pick-type formulae for the volume of three-dimensional lattice polyhedra, that is, polyhedra with vertices in ³. Our formulae are in terms of numbers of only thel _n-points belonging to a lattice polyhedronP in contrast to already known formulae which employ numbers of all the _n ³ -points inP. On our way to establishing the formulae we show that the number of points froml _n belonging to a three-dimensional lattice polyhedronP has some polynomiality properties similar to those of the well-known Ehrhart polynomial expressing the number of points of _n ³ inP. The paper contains also some comments on a problem of finding a volume formula which would employ only the setsl _n and which would be applicable to lattice polyhedra in arbitrary dimensions.Research partially supported by KBN Grant 2 P03A 008 10.     

A new formula for the volume of lattice polyhedra

LetL _n be the lattice consisting of all pointsx inR ^N such thatnx belongs to the fundamental latticeL ₁ of points with integer coordinates. When the vertices of a polyhedronP inR ^N are restricted to lie inL ₁ there is a formula which relates the volume ofP to the numbers of points ofL ₁,...,L _N in the interior and on the boundary ofP. The aim of this note is to show that the volume ofP can be determined only by means of the numbers of points ofL ₁,...,L _N lying in the interior ofP and cannot be expressed by the numbers of points ofL ₁,...,L _N lying on the boundary ofP. The latter numbers in turn can be used to compute to comopute the Euler characteristic of the boundary ofP.     

Irredundant self-dual bases for self-dual lattice varieties

For any finitely based self-dual variety of lattices, we determine the sizes of all equational bases that are both irredundant and self-dual. We make the same determination for {0, 1}-lattice varieties.Received July 11, 2002; accepted in final form August 27, 2004.     

On the sublattices of the Barnes-wall lattice

This paper is connected with the fundamental work of E.S. Barnes and G.E. Wall [1] in which the authors defined the so-called Barnes-Wall lattice. We shall determine the number of minima of some special sublattices of dimension 2 ⁿ –k of this lattice, where 1kn.Supported by Hung. Nat. Found for Sci. Research (OTKA) grant no. 1615 (1992)     

When do abstract bases generate continuous lattices and L-domains

In this note, the new concepts of C-bases (resp., BC-bases, L-bases) which are special kinds of abstract bases are introduced. It is proved that the round ideal completion of a C-basis (resp., BC-basis, L-basis) is a continuous lattice (resp., bc-domain, L-domain). Furthermore, representation theorems of continuous lattices (resp., bc-domains, L-domains) by means of the round ideal completions of C-bases (resp., BC-bases, L-bases) are obtained. Supported by the NSF of China (10371106, 60774073) and by the Fund (S0667-082) from Nanjing University of Aeronautics and Astronautics.     

Rational approximation to orthogonal bases and of the solutions of elliptic equations

It is shown that given , an orthogonal basis of can be approximated by an orthogonal basis , where has integral and have rational components, such that the angle between and is at most and the length , . This improves the length of the integral approximation due to Schmidt (1995). As an application, we improve a theorem of Kocan (1995) about the minimal size of grids in the solutions of elliptic equations. Our result fits the need in Kuo and Trudinger (1990). Received January 27, 1997 / Revised version received April 1, 1998     

On the proof of humbert’s volume formula

We close a gap in Humbert’s classical calculation of the volume of the quotient of three-dimensional hyperbolic space by SL₂ over the ring of integers of an imaginary quadratic number field.     

The distribution of sublattices of ℤ m

Lattices , are similar if one can be transformed into the other by an angle-preserving linear map. Similarity classes of lattices of rankn may be parametrized by a fundamental domain of the action ofGL _n () on the generalized upper half-plane _n . Given 1<nm and, letN(D,T) be the number of sublattices of _n which have rankn, similarity class inD, and determinant T. Our most basic result will be thatN(D,T)c ₁(m, n)(D)T ^m asT for suitable setsD, where is the invariant measure on _n . The casen=2 had been dealt with by Roelcke and by Maass using the theory of modular forms.Herrn Professor Hlawka zum achtzigsten Geburtstag gewidmetSupported in part by NSF-DMS-9401426     

Hecke actions on certain strongly modular genera of lattices

We calculate the action of some Hecke operators on spaces of modular forms spanned by the Siegel theta-series of certain genera of strongly modular lattices closely related to the Leech lattice. Their eigenforms provide explicit examples of Siegel cusp forms.Received: 10 September 2004     

From Membership to Separation, a Simple Construction

In [3], Martin Grötschel, László Lovász and Alexander Schrijver use a construction of Dmitrii Yudin et Arkadiĭ Nemirovskiĭ to polynomially separate a point x from a centered bounded convex K using a membership oracle. In this note, we present a natural and simple construction which solve the same problem but for the simpler case of polyhedra. Namely, given a well defined polyhedron P with a non-empty interior, a point and a point , using a polynomial number of calls of the membership oracle, we find a facet of P whose supporting hyperplane separates x from P.     

Minkowski’s Second Theorem over a Simple Algebra

We generalize the notion of successive minima, Minkowski’s second theorem and Siegel’s lemma to a free module over a simple algebra whose center is a global field. The author was partly supported by the Grant-in-Aid for Scientific Research (C), Japan Society for the Promotion of Science.     

Integral Points of Small Height Outside of a Hypersurface

Let F be a non-zero polynomial with integer coefficients in N variables of degree M. We prove the existence of an integral point of small height at which F does not vanish. Our basic bound depends on N and M only. We separately investigate the case when F is decomposable into a product of linear forms, and provide a more sophisticated bound. We also relate this problem to a certain extension of Siegel’s Lemma as well as to Faltings’ version of it. Finally we exhibit an application of our results to a discrete version of the Tarski plank problem.