0
$\begingroup$

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?

1 Answers 1

1

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.

  • 0
    @ Alex B. I think your accusation towards the poster was uncalled for. Just because someone might struggle with something does not mean that person is unwilling to 'stop and think for just 5 minutes.'2012-06-13