Generators of a 2D lattice

Question

Dear MO_World,

I'm hoping someone can point me towards a reference for something. I have an invertible $2\times 2$ matrix, $A$, with real entries such that for both of the rows, the entries are rationally independent (this ensures that $A\mathbb Z^2$ only intersects the coordinate axes at the origin).

What I want is a pair of generators of the lattice, $u$ and $v$, with $u$ belonging to the first quadrant and $v$ to the fourth quadrant.

I have a proof that I'm not entirely happy with using continued fraction convergents, but as it's going in an already-long paper, I'd love to have a self-contained reference for this.

Does anyone have any suggestions?

Answer 1

EDIT: why does a lattice have a shortest vector? To get to the other side? No. Because it is too far to walk around. Also your matrix $A$ is invertible, $A^{-1}$ has an operator norm with respect to the ordinary length, for any vector $w$ we have $|A^{-1} w| \leq C |w|$ with a constant $C > 0$ that depends on the matrix. So $|A x| \geq |x| / C. $ All nonzero lattice vectors have length at least 1, so all vectors in your lattice have length at least $1/C.$ Furthermore, the number of lattice vectors with length below any given bound is finite. So there is a shortest vector.

EDITEDIT: For the why is the shortest vector part of a basis? Call it $u.$ It is expressed as $r x + s y,$ for $x,y$ the columns of your matrix. If $\gcd(r,s) = g > 1,$ then $u/g$ is a strictly shorter vector in the lattice.

ORIGINAL: Take a shortest vector $u,$ and a fairly short vector $v,$ with $$ u \cdot u = a, \; \; u \cdot v = b, \; \; v \cdot v = c. $$ Without loss of generality, $u$ is in the first quadrant. If $v$ is in the second or fourth quadrant we are done. If $v$ is in the third quadrant, replace by $-v.$ So now both are in the first quadrant, the angle $\theta$ between them is below $\pi/2$ and we get $$ 1 > \cos \theta = \frac{b}{\sqrt{ac}} > 0. $$ So $$ 0 \leq b \leq a \leq c $$ and $$ b^2 < a c. $$

So, take the fairly short vector $v$ and subtract off multiples of $u$. We know that $u$ is shortest so for any integer $k$
$$ | v - k u|^2 \geq |u|^2 = a. $$

Now, take the circle of radius $\sqrt a$ around the origin. For real $t,$ we know that, if the line $v - t u$ passes through the circle at all, the length of the segment of intersection is no longer than $\sqrt a,$ otherwise there would be an integral value of $t$ giving a lattice point inside the circle, which is forbidden. It follows that the point of closest approach to the origin is not closer than $\frac{\sqrt{3a}}{2}.$ In turn, pretending that the line passes through the fourth quadrant next, the length of the line segment between the intersections with the $x$ and $y$ axes is no shorter than $$ \sqrt {3a} > \sqrt a.$$ That is, there is an integral value $t = t_0$ for which $v - t_0 u$ lies in the fourth quadrant. The new basis for the lattice is $$u, v-t_0 u.$$

Answer 2

Here is an other proof.

I will construct a hexagon with the vertices $u, v, w, -u, -v, -w$ from your lattice $L$ such that $$\angle(u,v),\ \angle(v,w),\ \angle(w,-u)\le \tfrac\pi2$$ and such that each pair $$(u,v),\ (v,w),\ (w,-u),\ (-u,-v),\ (-v,-w), (-w,u)$$ forms a basis of $L$. Clearly in this case one of these bases will satisfy your condition.

Construction.

• Take $u$ in $L$ which minimize the norm.
• Take $v$ in $L\backslash\langle u\rangle$ which minimize the norm.

Note that $u$ and $v$ form a basis of $L$. WLOG we may assume that $\angle(u,v)\le\tfrac\pi2$. Note that for $w=v-u$ all the above conditions hold.