Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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
    
You are having an issue of logic here: if the definition demands that the inequality be true for all suitable sets, then in particular it should be true for the sets I wrote down. But it being true for the sets I wrote down implies the inequality you wanted. –  Alex B. Nov 7 '10 at 4:59
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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