Why are vectors approximately orthogonal after Gaussian lattice reduction?

Question

In "An Introduction to Mathematical Cryptography"'s section on lattice reduction algorithms, the authors describe Gaussian lattice reduction and claim:

... the angle $\theta$ between $v1$ and $v2$ satisfies $\left| cos \theta \right| \leq \frac{\lvert v1 \rvert}{2\lvert v2 \rvert}$, so in particular $ \frac{\pi}{3} \leq \theta \leq \frac{2\pi}{3}$.

Where $v1$ and $v2$ are the output of the Gaussian lattice reduction algorithm and $\lvert v1 \rvert \leq \lvert v2 \rvert $. This result seems very close to a few trigonometric identities but I don't see why this is true in every case. Can someone shine some light on why this guarantees the reduced vectors share an angle in that range?

Answer 1

When the algorithm ends, $m = 0$, which means that

$$\left| \frac{v_1v_2}{||v_1||^2} \right| \le \frac{1}{2}$$

otherwise, the nearest integer would not be zero (and $m$ would be different from zero).

Now, you just use the well-known cosine similarity: since both vectors are non-zero (because they belong to a basis of the lattice), we have that $v_1 v_2 = || v_1 || || v_2 || \cos \theta$.

Combining those two expressions, we get

$$\left| \frac{v_1v_2}{||v_1||^2} \right| = \left| \frac{|| v_1 || || v_2 || \cos \theta}{||v_1||^2} \right| = \left| \frac{|| v_2 || \cos \theta}{||v_1||} \right| = \frac{|| v_2 || \left| \cos \theta \right|}{||v_1||} \le \frac{1}{2} $$

which gives us $\left| \cos \theta \right| \le \frac{||v_1||}{2||v_2||}$, the expected inequality.

-- EDIT

As galvatron commented, the inequality involving the angle $\theta$ is obtained simply by using the fact that $||v_1|| \le ||v_2||$, which together with the first inequality, gives you $| \cos \theta | \le \frac{||v_2||}{2||v_2||} = \frac{1}{2}$. Therefore, $- \frac{1}{2} \le \cos \theta \le \frac{1}{2}$.

But $\cos \theta$ equals $\frac{1}{2}$ when $\theta = \frac{\pi}{2}$ and equals $-\frac{1}{2}$ when $\theta = \frac{2\pi}{3}$.