Exploring the Relationship Between Lattice Successive Minima and Basis Vectors

[Peter_Newman]

Hello,

I've been thinking a bit about the definition of the $i$-th successive minima of a lattice (denoted with $\lambda_i(\Lambda)$), and I would argue that the $i$-th successive minimum is at most as large as the largest lattice basis vector $b_i$.

More formally:

$\lambda_i(\Lambda) \leq \max_{i} ||b_i||$

So purely intuitively I would say that makes sense, but is there any way to show this?

Now you could also come up with the idea to claim that the following holds:

$\lambda_i(\Lambda) \leq ||b_i||$

Is there a way to prove this here, I can't find one at the moment unfortunately, while I'm also not sure if this is even possible...

I would be very grateful for any helpful comments!

 

[Office_Shredder]

What is your definition of the successive minima? The one I know makes this really obvious.

 

[Peter_Newman]

There are different definitions. I would suggest this one:

$\lambda_i(\Lambda) = inf\left\{r > 0 | \text{ Linear independent lattice vectors } v_1,...,v_i \text{ with } ||v_j|| \leq r \text{ for } j = 1,2,...,i\right\} \quad \text{ for } i = 1,...,n$

The one I know makes this really obvious.

Which one do you have?

 

[Office_Shredder]

That's the one I know.So if you pick $i$ basis vectors, they are independent. That's an example of a set of vectors used in the definition of $\lambda_i$ What does that say about the length of the longest vector compared to $\lambda_i$?

 

[Peter_Newman]

That's the one I know.So if you pick $i$ basis vectors, they are independent. That's an example of a set of vectors used in the definition of $\lambda_i$ What does that say about the length of the longest vector compared to $\lambda_i$?

By definition I would say that $\lambda_i$ has to be less or equal to that longest vector. Is this ok? Basis vector alone makes no shortest vector, but it could...

 

[Office_Shredder]

Yeah, that's the whole proof

 

[Peter_Newman]

Thanks, so this proofs $\lambda_i(\Lambda) \leq \max_{i} ||b_i||$. This also makes sense from the definition!

Then I have another question about this $\lambda_i(\Lambda) \leq ||b_i||$, how would one prove or argue this. I'm bothered by the $i$ in the vector ($b_i$) here, because that implies some sort of "sorting" of the vectors...

 

[Office_Shredder]

You have bad notation with that max, having the index be the same as the left hand side. I would say given a basis $b_1,...,b_n$ of the lattice, for $1\leq i \leq n$, $\lambda_i \leq \max_{j} ||b_j||$. In fact, we even know $\lambda_i \leq \max_{j\leq i} ||b_j||$. (Or same for the max over any $i$ of the basis vectors) In the case where the basis is ordered such that $||b_1|| \leq ||b_2|| \leq ... \leq ||b_n||$, this implies $\lambda_i \leq ||b_i||$

 

[Peter_Newman]

You have bad notation with that max, having the index be the same as the left hand side.

Yes, that' s true, I agree!

I would say given a basis $b_1,...,b_n$ of the lattice, for $1\leq i \leq n$, $\lambda_i \leq \max_{j} ||b_j||$. In fact, we even know $\lambda_i \leq \max_{j\leq i} ||b_j||$. (Or same for the max over any $i$ of the basis vectors) In the case where the basis is ordered such that $||b_1|| \leq ||b_2|| \leq ... \leq ||b_n||$, this implies $\lambda_i \leq ||b_i||$

That's a good way of putting it! Thank you!