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
    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.2010-11-07
  • 0
    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.2010-11-07
  • 0
    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.2010-11-07
  • 0
    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.2010-11-07
  • 0
    '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.2010-11-07
  • 0
    By the way, by saying 'But that requires a proof' I meant the conclusion $|v_{1}|\leq |v_{2}| \leq ... \leq |v_{d}|$, not the conditions, of course.2010-11-07
  • 0
    @Robert: It may be silly to write this a month later, but I agree with Alex that you are confused here. *If* you have a Minkowski basis, then *any particular* choice of coefficients that satisfies the gcd condition will yield a valid inequality (in particular, the given choice). It is indeed not true that simply having $|v_1|\leq\cdots\leq|v_d|$ is sufficient to be a Minkowski basis; that is, the choices given by Alex are not *sufficient* to establish "Minkowski-ness", but you are not trying to establish that the set satisfies the Minkowski definition, you are *assuming* it does.2010-12-07
  • 0
    @Arturo Magidin I confess that I gave up on this. The poster was unwilling to stop and think for just 5 minutes.2010-12-08
  • 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