# Proof for Minkowski reduced basis

I've read a few articles explaining the way to use the Minkowski reduced basis in a lattice in order to measure the uniformity of the output of a random number generator. However, I can't prove a conclusion drawn from the following statement.

Given a set of linearly independent vectors $\{v_{1}, v_{2}, ... ,v_{d}\}$ in $\mathbb{R^{d}}$, a lattice is the set of vectors $w$ of the form $\sum_{i=1}^{d}z_{i}v_{i}$, where $z_{i}$ are integers. The set of vectors $\{v_{i}\}$ is a basis for the lattice. The basis is a Minkowski reduced basis if

$$||v_{k}||\leq||\sum_{i=1}^{d}z_{i}v_{i}||, \qquad \text{for} \quad 1\leq k \leq d,$$

for all sets of $d$ integers $z_{i}$ such that the greatest common divisor of the set $\{z_{k},z_{k+1},...,z_{d}\}$ is $1$. Accordingly, this implies $|v_{1}|\leq |v_{2}| \leq ... \leq |v_{d}|$. In the condition for a Minkowski reduced basis, $||v||$ denotes the Euclidean norm of the vector $v$.

Why can we infer that $|v_{1}|\leq |v_{2}| \leq ... \leq |v_{d}|$)?. That's what I'd like to know.

As far as I know, $||v_{1}||$ (for example), differs only from $||v_{2}||$ in having the restriction $\text{gcd}(\{z_{1},z_{2}\})=1$, while the second vector has $\text{gcd}(\{z_{2}\})=1$ in $\mathbb{R^{2}}$, however, I don't know how can I reach the conclusion from that fact.

Ideas?

-

Just consider the sets $\{z_1,\ldots,z_d\} = \{0,\ldots,0,1,0,\ldots 0 \}$ in the definition of Minkowski reduced bases, where for $v_k$ you put a 1 at the $k+1$-st place.
Thanks for your answer. Obviously, such a set works, however, the statement refers to all sets of integers $z_{i}$, not just to a particular choice. –  Robert Smith Nov 7 '10 at 4:46
But for considering that a proof, you need (or I need) to prove that all other sets are reducible to the set that you wrote. Otherwise, it could be true for the set you wrote and yet, fail to be true for any other set. Furthermore, $v_{k}$ doesn't necessarily share the same set $\{z_{i}\}$ than $v_{k+1}$ (in general, they don't). Although, maybe I'm misinterpreting the statement. If that's the case, I would appreciate further explanation. Thank you, Alex. –  Robert Smith Nov 7 '10 at 7:15
Robert, I don't know what I can say to make it clearer to you other than "just read the definition carefully". The vectors $v_i$ form a Minkowski basis if for each $v_i$ and for all sets of d integers $z_i$ satisfying that the greatest common divisor of the set {z_k,z_{k+1},...,z_d} is 1, the inequality holds. In particular, it must hold for the sets I have written down, since they satisfy the hypothesis about the gcd. There are many other sets z_i satisfying this hypothesis, and for each one of them the ineq. of the defn must hold. Otherwise, you don't have a Minkowski basis. –  Alex B. Nov 7 '10 at 11:49
'There are many other sets z_i satisfying this hypothesis, and for each one of them the ineq. of the defn must hold. Otherwise, you don't have a Minkowski basis.'. Well, I know that. But that requires a proof. Moreover, what happens with the condition $gcd(\{z_{k},z_{k+1},...,z_{d}\})=1$? That's the key to ensure that a vector is smaller than the following vector, but you're not dealing with that condition. –  Robert Smith Nov 7 '10 at 15:50