2000 Mathematics Subject Classification. 11J13, 11H06, 11H31, 52C07.
<ph f="cmbx">Successive minima and best simultaneous Diophantine approximations </ph>

### Martin Henk

Technische Universitat Wien, Wiedner Hauptstrae 8-10 / 1046, 1040 Wien, Osterreich E-mail address : ialiev@osiris.tuwien.ac.at Martin Henk, Universitat Magdeburg, Institut fur Algebra und Geometrie, Universitatsplatz 2, D-39106 Magdeburg, Germany E-mail address : henk@math.uni-magdeburg.de
• Abstract. We study the problem of best approximations of a vector $\alpha \in {\mathbb{R}}^{n}$  by rational vectors of a lattice $\Lambda \subset {\mathbb{R}}^{n}$  whose common denominator is bounded. To this end we introduce successive minima for a periodic lattice structure and extend some classical results from geometry of numbers to this structure. This leads to bounds for the best approximation problem which generalize and improve former results.

1 Introduction

Let ${\mathcal{K}}_{0}^{n}$  be the set of all $0$  -symmetric convex bodies in the $n$  -dimensional Euclidean space ${\mathbb{R}}^{n}$  . For $K\in {\mathcal{K}}_{0}^{n}$  and $x\in {\mathbb{R}}^{n}$  we denote by $|x{|}_{K}=min\left\{\lambda \ge 0:x\in \lambda K\right\}$  the norm of $x$  induced by $K$  . If $K$  is the $n$  -dimensional unit ball ${B}^{n}$  centered at the origin then we write $\parallel x\parallel$  instead of $|x{|}_{{B}^{n}}$  and the associated inner product is denoted by $x\cdot y$  , for $x,y\in {\mathbb{R}}^{n}$  . The volume, i.e., the $n$  -dimensional Lebesgue measure, of a set $S\subset {\mathbb{R}}^{n}$  is denoted by $vol\left(S\right)$  .
For a lattice $\Lambda =B{\mathbb{Z}}^{n}\subset {\mathbb{R}}^{n}$  , $B\in GL\left(n,\mathbb{R}\right)$  , a vector $\alpha \in {\mathbb{R}}^{n}$  and an integer $Q\ge 1$  the functional $\beta \left(\alpha ,Q,\Lambda ,K\right):=min\left\{|q\alpha -b{|}_{K}>0:q\in \left\{0,...,Q\right\},b\in \Lambda \right\}$  measures the quality of a best approximation of $\alpha$  by a rational vector of the lattice $\Lambda$  whose common denominator is bounded by $Q$  . This functional has been studied from various respects. For instance, for $n=1$  and based on continued fractions, Klein [8gave a geometric interpretation of such a “best approximation point” as a vertex of an associated $2$  -dimensional Klein polyhedron. Davenport and Mahler [2proved that there exist infinitely many points $\left(q,z{\right)}^{⊺}\in {\mathbb{Z}}^{3}$  , $z\in {\mathbb{Z}}^{2}$  , such that $\parallel q\alpha -z{\parallel }^{2}\le \left(2/\sqrt{23}\right)/q$  and the constant on the right hand side is best possible. In the context of primal methods for integer linear programs it has been also shown that these best approximations are related to so called Hilbert Bases of rational polyhedral pointed cones [6.
$\beta \left(\alpha ,Q,\Lambda ,K\right)$  was embedded by W.B. Jurkat [7and W. Kratz [9in a series of functionals, namely for $1\le i\le n+1$  they defined
 $\begin{array}{cc}{\stackrel{~}{\lambda }}_{i}\left(\alpha ,Q,\Lambda ,K\right):=min\left\{\lambda \ge 0:& \exists \text{}i\text{linearly independent points}\left({q}_{j},{b}_{j}{\right)}^{⊺}\in {\mathbb{R}}^{n+1},\end{array}$
 $\begin{array}{cc}& {q}_{j}\in \left\{0,...,Q\right\},{b}_{j}\in \Lambda \text{with}|{q}_{j}\alpha -{b}_{j}{|}_{K}\le \lambda \right\}.\end{array}$
 $\begin{array}{}\end{array}$
${\stackrel{~}{\lambda }}_{i}\left(\alpha ,Q,\Lambda ,K\right)$  is called the $i$  -th successive minimum with respect to $\alpha ,Q,\Lambda$  and $K$  . For abbreviation we just write ${\stackrel{~}{\lambda }}_{i}$  , since the dependency on $\alpha$  etc. will be clear from the context. Note that ${\stackrel{~}{\lambda }}_{1}=\beta \left(\alpha ,Q,\Lambda ,K\right)$  and ${\stackrel{~}{\lambda }}_{i}\le {\stackrel{~}{\lambda }}_{i+1}$  .
In [9successive-minima-type inequalities with constraints were studied and, among others, the following inequalities were proven in the case $K={B}^{n}$
 $\begin{array}{c}\frac{{2}^{\frac{n+1}{2}}}{\left(n+1\right)!}det\Lambda \le {\stackrel{~}{\lambda }}_{1}\cdot {\stackrel{~}{\lambda }}_{2}\cdots {\stackrel{~}{\lambda }}_{n+1}vol\left({B}^{n+1}\right){max}_{1\le i\le n+1}\left\{\frac{{q}_{i}}{{\stackrel{~}{\lambda }}_{i}}\right\}\le {2}^{2n+1}det\Lambda ,\end{array}$ (1.1)
where ${q}_{i}$  belongs to a point $\left({q}_{i},{b}_{i}{\right)}^{⊺}$  attaining the $i$  -th successive minimum, i.e., ${\stackrel{~}{\lambda }}_{i}=\parallel {q}_{i}\alpha -{b}_{i}\parallel$  . For $n=2$  these inequalities were improved by Kratz [10to
 $\begin{array}{c}\frac{2}{3\sqrt{3}}det\Lambda \le {\stackrel{~}{\lambda }}_{1}{\stackrel{~}{\lambda }}_{2}{\stackrel{~}{\lambda }}_{3}{max}_{1\le i\le 3}\left\{\frac{{q}_{i}}{{\stackrel{~}{\lambda }}_{i}}\right\}\le \frac{2}{\sqrt{3}}det\Lambda \end{array}$ (1.2)
and moreover it was shown
 $\begin{array}{c}{\stackrel{~}{\lambda }}_{1}{\stackrel{~}{\lambda }}_{2}\le \frac{2}{\sqrt{3}}\frac{det\Lambda }{Q}.\end{array}$ (1.3)
All the constants in  1.2 and  1.3 are best possible. Inequalities of that type give us information on the quality of the simultaneous approximation of a vector by a system of rational vectors of a lattice whose common denominators are bounded.
The inequalities  1.1 and  1.2 may be regarded as analogs (in the case $K={B}^{n}$  ) to Minkowski's classical inequalities on successive minima(cf. [3,pp. 59)
 $\begin{array}{c}\frac{{2}^{n}}{n!}det\Lambda \le {\lambda }_{1}\left(\Lambda ,K\right)\cdot \dots \cdot {\lambda }_{n}\left(\Lambda ,K\right)vol\left(K\right)\le {2}^{n}det\Lambda .\end{array}$ (1.4)
Here the $i$  -th successive minimum ${\lambda }_{i}\left(\Lambda ,K\right)$  is defined as ${\lambda }_{i}\left(\Lambda ,K\right):=min\left\{\lambda \ge 0:dim\left(\Lambda \cap \lambda K\right)\ge i\right\}.$  Both bounds in  1.4 are best possible. Statement  1.3 is the $2$  -dimensional analog of another result of Minkowski (cf. [3,pp. 195) on successive minima of $n$  -dimensional unit ball
 $\begin{array}{c}{\lambda }_{1}\left(\Lambda ,{B}^{n}\right)\cdot \dots \cdot {\lambda }_{n}\left(\Lambda ,{B}^{n}\right)\Delta \left({B}^{n}\right)\le det\Lambda .\end{array}$ (1.5)
Here $\Delta \left(K\right)$  denotes the critical determinant of $K\in {\mathcal{K}}_{0}^{n}$  , i.e., the minimal determinant of a lattice whose only lattice point belonging to the interior of $K$  is the origin. Since $\Delta \left({B}^{2}\right)=\frac{\sqrt{3}}{2}$  (cf. [3,pp. 244, [14,pp. 8) the analogy between  1.3 and  1.5 is obvious.
The fact that the constant $\frac{2}{\sqrt{3}}$  in  1.3 is best possible follows also from a recent and more general result by I. Aliev and P. M. Gruber [1, who showed that for every $\epsilon >0$  there exists a vector $\alpha \in {\mathbb{R}}^{n}\\left\{0\right\}$  and a $Q\in \mathbb{N}$  such that
 $\begin{array}{c}{\left({\stackrel{~}{\lambda }}_{1}\right)}^{n}>\frac{1-\epsilon }{\Delta \left(K\right)}\frac{det\Lambda }{Q}.\end{array}$ (1.6)
Hence  1.3 cannot be improved. In fact,  1.6 was not only proven for $0$  -symmetric convex bodies, but for any bounded star body $K$  . Finally, it is also known (cf. [3,p. 197) that in the planar case  1.5 can be generalized to all $K\in {\mathcal{K}}_{0}^{n}$  , i.e.,
 $\begin{array}{c}{\lambda }_{1}\left(\Lambda ,K\right)\cdot {\lambda }_{2}\left(\Lambda ,K\right)\Delta \left(K\right)\le det\Lambda .\end{array}$ (1.7)
In this paper we want to introduce and study a slightly different series of successive minima associated to this best approximation problem. With these successive minima we can give best possible upper and lower bounds of a similar type as in  1.1 and  1.3 with respect to all $0$  -symmetric convex bodies and, in addition, these results include the classical inequalities  1.4 ,  1.5 and  1.7 . To this end we consider the special periodic lattice $\Lambda \left(\alpha ,Q\right):=\Lambda \cup \left(\alpha +\Lambda \right)\cup \left(2\alpha +\Lambda \right)\cup \cdot \cdot \cdot \cup \left(Q\alpha +\Lambda \right),$  where we always assume that $k\alpha /\in \Lambda$  for $1\le k\le Q$  . In order to allow the case $\alpha \in \Lambda$  we admit $Q=0$  . Next we define for $1\le i\le n$  ${\lambda }_{i}\left(\Lambda \left(\alpha ,Q\right),K\right):=min\left\{\lambda \ge 0:dim\left(\Lambda \left(\alpha ,Q\right)\cap \lambda K\right)\ge i\right\},$  and again for abbreviation we just write ${\lambda }_{i}$  instead of ${\lambda }_{i}\left(\Lambda \left(\alpha ,Q\right),K\right)$  . In comparison with the successive minima ${\stackrel{~}{\lambda }}_{i}$  we note that ${\stackrel{~}{\lambda }}_{1}={\lambda }_{1},\text{and}{\stackrel{~}{\lambda }}_{i}\le {\lambda }_{i},2\le i\le n.$  Hence any upper bound on ${\lambda }_{i}$  gives us also an upper bound on ${\stackrel{~}{\lambda }}_{i}$  . In order to state our results concerning these successive minima we need some more notation. For $K\in {\mathcal{K}}_{0}^{n}$  we denote by $\delta \left(K\right)$  the density of a densest packing of translates of $K$  (cf. [3,pp. 218) and the dual lattice of $\Lambda$  is denoted by ${\Lambda }^{*}$  (cf. [3,pp. 23).
Theorem 1.1. Let $K\in {\mathcal{K}}_{0}^{n}$  , $\alpha \in {\mathbb{R}}^{n}$  , $\Lambda \subset {\mathbb{R}}^{n}$  be a lattice and $Q\in {\mathbb{N}}_{\ge 0}$  such that $k\alpha /\in \Lambda$  for $1\le k\le Q$  . Then with ${\lambda }_{i}={\lambda }_{i}\left(\Lambda \left(\alpha ,Q\right),K\right)$  we have
 $\begin{array}{cc}\text{i)}& \left({\lambda }_{1}{\right)}^{n}vol\left(K\right)\le \delta \left(K\right){2}^{n}\frac{det\Lambda }{Q+1},\end{array}$
 $\begin{array}{cc}\text{ii)}& \frac{{2}^{n}}{n!}det\Lambda \gamma \left(\alpha ,\Lambda ,Q,n\right)\le {\lambda }_{1}\cdot \dots \cdot {\lambda }_{n}vol\left(K\right)\le {2}^{n}\frac{det\Lambda }{Q+1},\end{array}$
 $\begin{array}{}\end{array}$
where
 $\begin{array}{cc}\gamma \left(\alpha ,\Lambda ,Q,n\right)=min\left\{& |{u}^{*}\cdot \alpha +z|>0:{u}^{*}\in {\Lambda }^{*},z\in \mathbb{Z},\end{array}$
 $\begin{array}{cc}& \parallel \left({u}^{*},z{\right)}^{⊺}\parallel \le \left(n{\lambda }_{n}+Q\parallel \left(\alpha ,1{\right)}^{⊺}\parallel {\right)}^{n}/det\Lambda \right\}.\end{array}$
 $\begin{array}{}\end{array}$
Remark 1.2.
• (1) If $K=\left[-1,1{\right]}^{n}$  is the standard cube of edge length 2 centered at the origin, i.e., $|\cdot {|}_{K}$  is the maximum norm, and if $\Lambda ={\mathbb{Z}}^{n}$  statement i) implies that for any $\left({\alpha }_{1},...,{\alpha }_{n}{\right)}^{⊺}\in {\mathbb{R}}^{n}$  there exist a $\left({z}_{1},...,{z}_{n}{\right)}^{⊺}\in {\mathbb{Z}}^{n}$  and $q\in \left\{1,...,Q\right\}$  such that $|q{\alpha }_{i}-{z}_{i}|<{Q}^{-1/n},1\le i\le n.$  This is Dirichlet's classical approximation theorem.
• (2) If $\left(Q+1\right)\alpha \in \Lambda$  then $\Lambda \left(\alpha ,Q\right),K\right)$  is a lattice of determinant $det\Lambda /\left(Q+1\right)$  and we also have $\gamma \left(\alpha ,\Lambda ,Q,n\right)\ge 1/\left(Q+1\right)$  . Thus, in this situation, statement ii) becomes  1.4 . In particular, these inequalities are best possible.
• (3) In general we cannot expect to find a lower bound in ii) which depends only on $\Lambda$  , $n$  and $Q$  . For instance, let $\Lambda ={\mathbb{Z}}^{n}$  and for a positive integer $m$  let $K\left(m\right)$  be the cross-polytope with vertices $\left\{±\frac{1}{m}{e}_{1},±{e}_{i}:2\le i\le n\right\}$  . Here ${e}_{i}\in {\mathbb{R}}^{n}$  denotes the $i$  -th unit vector. Then $vol\left(K\left(m\right)\right)=\left(1/m\right){2}^{n}/n!$  and for $\alpha =\frac{1}{m}{e}_{1}$  , $Q  , we have ${\lambda }_{i}=1$  , $1\le i\le n$  , and so ${\lambda }_{1}\cdot \dots \cdot {\lambda }_{n}vol\left(K\right)=\left(1/m\right){2}^{n}/n!$  . In this case we also have $\gamma \left(\alpha ,{\mathbb{Z}}^{n},Q,n\right)=1/m$  and thus equality in the lower bound.
For the special cases $K={B}^{n}$  or $n=2$  we obtain the following improvements on the upper bound in Theorem  1.1 ii).
Proposition 1.3. With the notation as in Theorem  1.1 we have
 $\begin{array}{cc}\text{i)}& {\lambda }_{1}\cdot {\lambda }_{2}\cdot \dots \cdot {\lambda }_{n}vol\left({B}^{n}\right)\le \delta \left({B}^{n}\right){2}^{n}\frac{det\Lambda }{Q+1},\end{array}$
 $\begin{array}{cc}\text{ii)}& {\lambda }_{1}\cdot {\lambda }_{2}\Delta \left(K\right)\le \frac{det\Lambda }{Q+1},\text{for}n=2.\end{array}$
 $\begin{array}{}\end{array}$
Remark 1.4.
• (1) By  1.6 we see that ii) is best possible and it generalizes  1.3 to all norms in ${\mathbb{R}}^{2}$  .
• (2) Since $\Delta \left(K\right)=vol\left(K\right){2}^{-n}/{\delta }_{L}\left(K\right)$  where ${\delta }_{L}\left(K\right)$  denotes the density of a densest lattice packing of $K$  (cf. [3,p. 221), inequality i) is a bit weaker than  1.5 . However, since we deal with more general structures than lattice we have to replace, in comparison with  1.5 , ${\delta }_{L}\left(K\right)$  by $\delta \left(K\right)$  .
• (3) It is still an open conjecture of Davenport that  1.5 can be generalized to arbitrary $K\in {\mathcal{K}}_{0}^{n}$  and the same can be conjectured for inequality i).
According to the announced proofs of the Kepler-Conjecture (cf. [4, [5) we also know $\delta \left({B}^{3}\right)={\delta }_{L}\left({B}^{3}\right)=\pi /\sqrt{18}$  and therefore, Proposition  1.3 i) leads to
Corollary 1.5. For $K={B}^{3}$  we have ${\lambda }_{1}\cdot {\lambda }_{2}\cdot {\lambda }_{3}\le \sqrt{2}\frac{det\Lambda }{Q+1}.$
Again, from  1.6 we see that this inequality is best possible.

2 Proofs

The basic properties of our set $\Lambda \left(\alpha ,Q\right)$  , which allow us to extend inequalities on lattices and convex bodies to this structure are
 $\begin{array}{c}\begin{array}{cccccccc}i\right)& \Lambda \left(\alpha ,Q\right)\text{is invariant with respect to lattice translations of}\Lambda .& ii\right)& \text{A fundamental cell of}\Lambda \text{contains exactly}Q+1\text{points of}\Lambda \left(\alpha ,Q\right).& iii\right)& \text{For}{a}_{1},{a}_{2}\in \Lambda \left(\alpha ,Q\right)\text{at least one of the points}{a}_{1}-{a}_{2},{a}_{2}-{a}_{1}& & \text{belongs to}\Lambda \left(\alpha ,Q\right).\end{array}\end{array}$ (2.1)
A set $S$  satisfying the first two properties is called a periodic lattice. For such a periodic lattice and a set $X$  the arrangement $S+X$  is called a periodic lattice packing if for all ${c}_{1},{c}_{2}\in S$  , ${c}_{1}\ne {c}_{2}$  , ${c}_{1}+int\left(X\right)\cap {c}_{2}+int\left(X\right)=\varnothing ,$  where $int\left(\cdot \right)$  denotes the interior. If $X$  is measurable and bounded then the density $\delta \left(S,X\right)$  of such a periodic packing can be calculated by (cf. [12,pp. 26)
 $\begin{array}{c}\delta \left(S,X\right)=vol\left(X\right)\frac{Q+1}{det\Lambda }.\end{array}$ (2.2)
Now let ${\lambda }_{1}={\lambda }_{1}\left(\Lambda \left(\alpha ,Q\right),K\right)$  . First we note that on account of  2.1 iii) ${\lambda }_{1}=min\left\{|{a}_{1}-{a}_{2}{|}_{K}:{a}_{1},{a}_{2}\in \Lambda \left(\alpha ,Q\right)\right),{a}_{1}\ne {a}_{2}\right\}.$  Hence $\frac{2}{{\lambda }_{1}}\Lambda \left(\alpha ,Q\right)+K$  is a periodic lattice packing of $K$  and thus $\delta \left(K\right)\ge \delta \left(\frac{2}{{\lambda }_{1}}\Lambda \left(\alpha ,Q\right),K\right)=\left(Q+1\right)\frac{vol\left(K\right)}{det\left(\frac{2}{{\lambda }_{1}}\Lambda \right)}=\left(Q+1\right)\frac{{\lambda }_{1}^{n}}{{2}^{n}}\frac{vol\left(K\right)}{det\Lambda }.$  This shows already Theorem  1.1 i).
As an immediate consequence we have the following analog to a theorem of Blichfeldt [3,p. 42
Lemma 2.1. Let $X\subset {\mathbb{R}}^{n}$  be a measurable set with $vol\left(X\right)>det\left(\Lambda \right)/\left(Q+1\right)$  . Then there exist two distinct ${x}_{1},{x}_{2}\in X$  such that ${x}_{1}-{x}_{2}\in \Lambda \left(\alpha ,Q\right)$  .
• Proof. W.l.o.g. let $X$  be bounded. Now suppose the contrary, i.e., for all ${x}_{1},{x}_{2}\in X$  , ${x}_{1}\ne {x}_{2}$  , we have ${x}_{1}-{x}_{2}/\in \Lambda \left(\alpha ,Q\right)$  . Then $\Lambda \left(\alpha ,Q\right)+X$  is a periodic lattice packing of $X$  , because $x\in {c}_{i}+int\left(X\right)$  for two distinct ${c}_{1},{c}_{2}\in \Lambda \left(\alpha ,Q\right)$  implies $x-{c}_{1},x-{c}_{2}\in X$  . Together with  2.1 iii) this shows that $x-{c}_{1}-\left(x-{c}_{2}\right)={c}_{2}-{c}_{1}\in \Lambda \left(\alpha ,Q\right)$  or $x-{c}_{2}-\left(x-{c}_{1}\right)={c}_{1}-{c}_{2}\in \Lambda \left(\alpha ,Q\right)$  .
Thus $\Lambda \left(\alpha ,Q\right)+X$  is a periodic lattice packing of $X$  and by  2.2 we obtain the contradiction $1\ge \delta \left(\Lambda \left(\alpha ,Q\right),X\right)=vol\left(X\right)\frac{Q+1}{det\Lambda }.$
Now we come to
• Proof of Theorem  1.1  ii). On account of Lemma  2.1 the upper bound can be shown completely analogous to the upper bound of Minkowski's classical inequality  1.4 . Here we will follow Siegel's proof [13,pp.33and we will just give the main arguments. Let ${a}_{1},...,{a}_{n}\in \Lambda \left(\alpha ,Q\right)$  be linearly independent such that ${a}_{i}\in {\lambda }_{i}K$  , $1\le i\le n$  . For $x\in {\mathbb{R}}^{n}$  and $0\le k\le n-1$  we denote by ${L}_{k}\left(x\right)$  the $k$  -dimensional affine plane given by ${L}_{k}\left(x\right)=x+lin\left\{{a}_{1},...,{a}_{k}\right\}$  , where $lin\left\{\right\}$  denotes the linear hull. Let $\stackrel{~}{K}=int\left(K\right)$  and for $x\in \stackrel{~}{K}$  let ${c}_{k}\left(x\right)$  be the center of gravity of the intersection ${L}_{k}\left(x\right)\cap \stackrel{~}{K}$  . Since $\stackrel{~}{K}$  is convex ${c}_{k}\left(x\right)$  belongs to $\stackrel{~}{K}$  , and moreover, ${c}_{k}\left(x\right)$  depends continuously on $x$  . Let $f:\stackrel{~}{K}\to {\mathbb{R}}^{n}$  be the map  $\begin{array}{c}f\left(x\right)={\lambda }_{1}{c}_{0}\left(x\right)+\left({\lambda }_{2}-{\lambda }_{1}\right){c}_{1}\left(x\right)+\cdots +\left({\lambda }_{n}-{\lambda }_{n-1}\right){c}_{n-1}\left(x\right).\end{array}$ (2.3)
Then it is shown that $f$  is an injective map and that the volume of the bounded set $C=f\left(\stackrel{~}{K}\right)$  (which, in general, is not convex) is given by (cf. [13,pp.33)  $\begin{array}{c}vol\left(C\right)={\lambda }_{1}\cdot {\lambda }_{2}\cdot \dots \cdot {\lambda }_{n}vol\left(K\right).\end{array}$ (2.4)
Next we claim  $\begin{array}{c}\Lambda \left(\alpha ,Q\right)\text{is a periodic lattice packing of}\frac{1}{2}C.\end{array}$ (2.5)
Suppose the opposite and let ${y}_{1},{y}_{2}\in C$  , ${y}_{1}\ne {y}_{2}$  , such that $\frac{1}{2}\left({y}_{1}-{y}_{2}\right)\in \Lambda \left(\alpha ,Q\right)$  . Let ${x}_{1},{x}_{2}\in \stackrel{~}{K}$  with ${y}_{i}=f\left({x}_{i}\right)$  and let $r$  be minimal such that ${x}_{1}-{x}_{2}\in lin\left\{{a}_{1},...,{a}_{r}\right\}$  . Then ${c}_{k}\left({x}_{1}\right)={c}_{k}\left({x}_{2}\right)$  for $k=r,...,n-1$  and therefore we may write  $\begin{array}{c}\begin{array}{cccc}\frac{1}{2}\left({y}_{1}-{y}_{2}\right)=& {\lambda }_{1}\frac{1}{2}\left({c}_{0}\left({x}_{1}\right)-{c}_{0}\left({x}_{2}\right)\right)+\left({\lambda }_{2}-{\lambda }_{1}\right)\frac{1}{2}\left({c}_{1}\left({x}_{1}\right)-{c}_{1}\left({x}_{2}\right)\right)+& & \cdot \cdot \cdot +\left({\lambda }_{r}-{\lambda }_{r-1}\right)\frac{1}{2}\left({c}_{r-1}\left({x}_{1}\right)-{c}_{r-1}\left({x}_{2}\right)\right).\end{array}\end{array}$ (2.6)
Since $\stackrel{~}{K}$  is a convex $0$  -symmetric open set we have $\frac{1}{2}\left({c}_{i}\left({x}_{1}\right)-{c}_{i}\left({x}_{2}\right)\right)\in \stackrel{~}{K}$  and so we find by  2.6   $\begin{array}{c}\frac{1}{2}\left({y}_{1}-{y}_{2}\right)\in int\left\{{\lambda }_{r}K\right\}.\end{array}$ (2.7)
On the other hand,  2.6 also shows $\frac{1}{2}\left({y}_{1}-{y}_{2}\right)\in {\lambda }_{r}\frac{1}{2}\left({x}_{1}-{x}_{2}\right)+lin\left\{{a}_{1},...,{a}_{r-1}\right\}$  and thus, by the choice of $r$  , the point $\frac{1}{2}\left({y}_{1}-{y}_{2}\right)$  is linearly independent from ${a}_{1},...,{a}_{r-1}$  . In view of  2.7 , however, this contradicts the definition of ${\lambda }_{r}$  .
Thus  2.5 is shown and by Lemma  2.1 (applied to $\frac{1}{2}C$  ) and  2.4 we obtain the upper bound in Theorem  1.1 ii).
For the lower bound let ${a}_{i}$  as above. Then $K$  contains the cross-polytope with vertices $\left\{±\frac{1}{{\lambda }_{i}}{a}_{i}:1\le i\le n\right\}$  . Hence  $\begin{array}{c}vol\left(K\right)\ge \frac{{2}^{n}}{n!}\frac{1}{{\lambda }_{1}\cdot \dots \cdot {\lambda }_{n}}|det\left({a}_{1}{a}_{2}...{a}_{n}\right)|.\end{array}$ (2.8)
With ${a}_{i}={b}_{i}-{q}_{i}\alpha$  , ${b}_{i}\in \Lambda$  , ${q}_{i}\in \left\{0,...,Q\right\}$  , $1\le i\le n$  , we may write  $\begin{array}{c}det\left({a}_{1}{a}_{2}...{a}_{n}\right)=det\left(\begin{array}{ccccc}{b}_{1}& {b}_{2}& \cdot \cdot \cdot & {b}_{n}& \alpha \\ {q}_{1}& {q}_{2}& \cdot \cdot \cdot & {q}_{n}& 1\end{array}\right)=:detA.\end{array}$ (2.9)
Now let ${\Lambda }^{\prime }=\left\{\left(b,z{\right)}^{⊺}\in {\mathbb{R}}^{n+1}:b\in \Lambda ,z\in \mathbb{Z}\right\}=\Lambda ×\mathbb{Z}$  be the lattice given by the Cartesian product of $\Lambda$  and $\mathbb{Z}$  . Obviously, we have ${{\Lambda }^{\prime }}^{◆}={\Lambda }^{◆}×\mathbb{Z}$  . Let ${{u}^{\prime }}^{*}=\left({u}^{*},z\right)\in {{\Lambda }^{\prime }}^{◆}$  be the uniquely (up to $±$  ) determined primitive vector which is orthogonal to the lattice hyperplane $L$  of ${\Lambda }^{\prime }$  generated by $\left({b}_{1},{q}_{1}{\right)}^{⊺},...,\left({b}_{1},{q}_{n}{\right)}^{⊺}$  .
Next we supplement ${{u}^{\prime }}^{*}$  to a basis of ${{\Lambda }^{\prime }}^{◆}$  and let ${A}^{*}$  be the matrix consisting of these basis vectors as column vectors. Since the inner product of a vector of lattice with a vector of the dual lattice is an integer we get  $\begin{array}{c}det\left(A\right)=\frac{1}{det{{\Lambda }^{\prime }}^{◆}}det\left({A}^{⊺}{A}^{*}\right)\ge det\Lambda |{u}^{*}\alpha +z|.\end{array}$ (2.10)
On the other hand we have (cf. [11,pp. 28) $det\left(L\cap {\Lambda }^{\prime }\right)=det{\Lambda }^{\prime }\cdot \parallel {{u}^{\prime }}^{*}\parallel =det\Lambda \parallel {{u}^{\prime }}^{*}\parallel ,$  and since the $n$  linearly independent points $\left({b}_{i},{q}_{i}{\right)}^{⊺}$  belong to $L\cap {\Lambda }^{\prime }$  we can bound $\parallel {{u}^{\prime }}^{*}\parallel$  by  $\begin{array}{c}\parallel {{u}^{\prime }}^{*}\parallel \le \frac{det\left(L\cap {\Lambda }^{\prime }\right)}{det\Lambda }\le \frac{\parallel \left({b}_{1},{q}_{1}{\right)}^{⊺}\parallel \cdot \dots \cdot \parallel \left({b}_{n},{q}_{n}{\right)}^{⊺}\parallel }{det\Lambda }.\end{array}$ (2.11)
Finally we observe that $\parallel \left({b}_{i},{q}_{i}{\right)}^{⊺}\parallel \le \parallel \left({b}_{i},{q}_{i}{\right)}^{⊺}-{q}_{i}\left(\alpha ,1{\right)}^{⊺}\parallel +Q\parallel \left(\alpha ,1{\right)}^{⊺}\parallel \le \sqrt{n}{\lambda }_{i}+Q\parallel \left(\alpha ,1{\right)}^{⊺}\parallel$  and together with  2.8  2.11 we get the desired lower bound.
• Proof of Proposition  1.3 . As in the case of  1.5 and  1.7 with respect to Minkowski's successive minima, these inequalities are to some extend just a consequence of the proof of the upper bound in Theorem  1.1 ii). Roughly speaking, the main observation is that for $K={B}^{n}$  or $n=2$  the map $f$  in  2.3 can be made linear.
For details we refer to [3,pp. 195,p. 197.
If $f$  is linear the resulting body $f\left(K\right)$  is still a $0$  -symmetric convex body and from  2.5 we know that $\Lambda \left(\alpha ,Q\right)$  is a periodic lattice packing of $\frac{1}{2}f\left(K\right)$  . Thus we know that ${\lambda }_{1}\left(\Lambda \left(\alpha ,Q\right),f\left(K\right)\right)\ge 1$  and with Theorem  1.1 i) we get for $K={B}^{n}$  or $n=2$  ${\lambda }_{1}\cdot \dots \cdot {\lambda }_{n}vol\left(K\right)=vol\left(f\left(K\right)\right)\le \delta \left(f\left(K\right)\right){2}^{n}\frac{det\Lambda }{Q+1}=\delta \left(K\right){2}^{n}\frac{det\Lambda }{Q+1},$  since the density of a densest packing is invariant with respect to affine transformations. For $K={B}^{n}$  we get Proposition  1.3 i). In the planar case it is well known that $\delta \left(K\right)={\delta }_{L}\left(K\right)=vol\left(K\right){2}^{-n}/\Delta \left(K\right)$  (cf. [3,pp. 248) and so we also obtain the second statement.

3 Acknowledgement

The first author was supported by FWF Austrian Science Fund, projects M672 and M821-N12. References

1. I. Aliev and P.M. Gruber, Best simultaneous Diophantine approximations under a constraint on the denomiantor, submitted, 2004.
2. H. Davenport and K. Mahler, Simultaneous diophantine approximation, Duke Math. J. 13 (1946), 105–111.
3. P. M. Gruber and C. G. Lekkerkerker, Geometry of numbers, second ed., vol. 37, North-Holland Publishing Co., Amsterdam, 1987.
4. T.C. Hales, The Kepler Conjecture, see http://www.math.pitt.edu/~thales/kepler98/ and the references within, 1998.
5. W. Hsiang, Least action principle of crystal formation of dense packing type and Kepler's conjecture, Nankai Tracts in Mathematics, vol. 3, World Scientific Publishing Co. Inc., River Edge, NJ, 2001.
6. M. Henk and R. Weismantel, Diphantine approximations and integer points of cones, Combinatorica 22 (2002), no. 3, 401–408.
7. W.B. Jurkat, On successive minima with constraints, Analysis 1 (1981), 33–44.
8. F. Klein, Über eine geometrische Auffassung der gewöhnlichen Kettenbruchentwicklung, Nachr. Ges. Wiss. Göttingen, Math.-Phys. 3 (1895), 357–359.
9. W. Kratz, Sukzessive Minima mit und ohne Nebenbedingungen, Mh. Math. 91 (1981), 275–289.
10. , On optimal constants for best two-dimensional simultaneous Diophantine approximations, Mh. Math. 128 (1999), 99–110.
11. J. Martinet, Perfect lattices in Euclidean spaces, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 327, Springer-Verlag, Berlin, 2003.
12. C. A. Rogers, Packing and covering, Cambridge Tracts in Mathematics and Mathematical Physics, No. 54, Cambridge University Press, New York, 1964.
13. C. L. Siegel, Lectures on the geometry of numbers, Springer-Verlag, Berlin, 1989.
14. Ch. Zong, Sphere packings, Springer-Verlag, New York, 1999.

Technische Universitat Wien, Wiedner Hauptstrae 8-10 / 1046, 1040 Wien, Osterreich E-mail address : ialiev@osiris.tuwien.ac.at Martin Henk, Universitat Magdeburg, Institut fur Algebra und Geometrie, Universitatsplatz 2, D-39106 Magdeburg, Germany E-mail address : henk@math.uni-magdeburg.de