1
$\begingroup$

Let $\mathbf{v}_1, \mathbf{v}_2, ..., \mathbf{v}_n$ be $n$ linearly independent vectors in an $n$-dimensional lattice $\Lambda$ in $\mathbf{R}^n$ and let $\mathbf{v}^*_1 ,\mathbf{v}^*_2, ..., \mathbf{v}^*_n$ denote the Gram-Schmidt orthogonalization of $\mathbf{v}_1, \mathbf{v}_2, ..., \mathbf{v}_n$.

I'm interested in the following quantity:

$$f_n(\Lambda) =\min_{{\mathbf{v}_1, \mathbf{v}_2, ..., \mathbf{v}_n \in \Lambda}} \{\max_i \Vert\mathbf{v}^*_i\Vert \}$$

Notice that — in a definition similar to Minkowski's successive minima — $f_n(\Lambda)$ is the smallest radius of a ball in $\mathbf{R}^n$ that contains $n$ linearly independent Gram–Schmidt vectors generated by $\Lambda$.

In particular we have that $$(1)\;\;f_n(\Lambda)\leq \lambda_n(\Lambda),$$ where $\lambda_n(\Lambda)$ is the $n$-th successive minimum of $\Lambda$, and $$\;\;\;\;\; \ (2)\;\;\det(\Lambda)^{{1}/{n}} \leq f_n(\Lambda).$$

So I come to my question: Is it possible to bound (1) or (2) in the opposite direction to make a statement that qualitatively reads: $f_n(\Lambda)$ is not much larger than $\det(\Lambda)^{{1}/{n}}$ and/or not much smaller than $\lambda_n(\Lambda)$?

For example, say something like:

$$ f_n(\Lambda)\leq c_1 \det(\Lambda)^{{1}/{n}} \;\;\;\mbox{ and/or }\;\;\; f_n(\Lambda)\geq \frac{1}{c_2}\lambda_n(\Lambda) $$

for some quantities $c_1,c_2$ that are "not too large" ?

$\endgroup$
2
  • $\begingroup$ Since there are lattices in ${\bf R}^n$ with $\lambda_n(\Lambda)/\det(\Lambda)^{\frac 1 n}$ arbitrarily large (for example the ones gererated by the $(0,\ldots,1,\ldots,0)$ and $(0,\ldots,0,N)$ for $N\ge 1$ I doubt that the two inequalities could both be valid. $\endgroup$ Apr 5, 2013 at 11:52
  • $\begingroup$ @Jean Thanks for the comment. Now that you mention it I see that there are lattices with $f_n(\Lambda)/det(\Lambda)$ arbitrarily large. E.g. in $\mathbb{R}^2$ the lattice generated by $(1/a , 0)$, $(0 , a)$ for $a>1$ has $f_n(\Lambda)/det(\Lambda) = a$. $\endgroup$
    – Alexander
    Apr 5, 2013 at 12:50

1 Answer 1

2
$\begingroup$

As already pointed out by Jean and Alexander, bound (2) does not hold in the opposite direction. For bound (1), the opposite inequality holds with $c_2=n$.

Theorem For any $n$-dimensional lattice $\Lambda$, $f_n(\Lambda)\geq \lambda_n(\Lambda)/n$.

Proof: Let ${\bf v}_1,\ldots,{\bf v}_n$ be a set of linearly independent vectors in a lattice minimizing $\max_i \|{\bf v}_i^*\|$. You can always turn ${\bf v}_1,\ldots,{\bf v}_n$ into a basis without increasing $\|{\bf v}_i^*\|$. So, assume it is a basis. Let ${\bf w}_1,\ldots,{\bf w}_n$ be a basis of the dual lattice $\Lambda^*$ such that ${\bf v_i}\cdot {\bf w_j}=\delta_{i,j}$.

Orthogonalizing ${\bf w}_1,\ldots,{\bf w}_n$ in reverse order gives $\|{\bf w}_i^*\| = \|{\bf v}_i^*\|^{-1}$. So, $\max_i \|{\bf v}_i^*\| = (\min_i \|{\bf w}_i^*\|)^{-1}$. Using the bound $\min_i \|{\bf w}_i^*\| \leq \lambda_1(\Lambda^*)$ and Banaszczyk's transference theorem $\lambda_n(\Lambda)\lambda_1(\Lambda^*)\leq n$ gives: $\max_i \|{\bf v}_i^*\| = (\min_i \|{\bf w}_i^*\|)^{-1} \geq \lambda_1(\Lambda^*)^{-1}\geq \lambda_n(\Lambda)/n$. So, $f_n(\Lambda)\geq \lambda_n(\Lambda)/n$. $\Box$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.