Tag Archives: lattice

Pick’s Theorem

Let a=(a_1,a_2) and b=(b_1,b_2) be two vectors in \mathbb Z^2. In the last post we showed that a and b generate \mathbb Z^2 (as an abelian group under +, or a \mathbb Z-module) iff the parallelogram determined by them has unit area.

Define a lattice polygon to be a polygon whose vertices are lattice points, i.e. points in \mathbb Z^2. Note that a and b generate \mathbb Z^2 iff the parallelogram determined by them contains no further lattice points. (In the language of groups, \langle a,b\rangle=\mathbb Z^2 iff the quotient \mathbb Z^2/\langle a,b\rangle is trivial.) Hence:

Lemma 1. A lattice parallelogram has unit area iff it contains no further lattice points.

This can also be phrased in terms of lattice triangles:

Lemma 2. A lattice triangle has area 1/2 iff it contains no further lattice points.

Call such triangles elementary. We can use lemma 2 to prove Pick’s theorem:

Theorem (Pick). A lattice polygon has area i+b/2-1, where i and b are the number of interior and boundary lattice points respectively.

Proof. Triangulate the polygon into elementary triangles, then induct on the number of elementary triangles. (If the polygon can be triangulated into m and also into n elementary triangles, then its area by lemma 2 is m/2=n/2 which shows that the number is well-defined.)

Consider an elementary triangle on the boundary. There are two possibilities:

  1. All three vertices lie on the boundary. In this case deletion of the triangle reduces b by 1 and keeps i fixed. By the induction hypothesis the new polygon has area i+(b-1)/2-1, and so the area of the original polygon is i+(b-1)/2-1+1/2=i+b/2-1.
  2. One of the vertices is an interior point. Then deletion of the triangle increases b by 1, but reduces i by 1. Hence by the induction hypothesis the new polygon has area i-1+(b+1)/2-1, and so the area of the original polygon is i+b/2-1.

Finally, the base case follows from lemma 2. Hence the proof is complete. \square

Corollary. In any triangulation of a lattice polygon into elementary triangles, the number of elementary triangles is 2i+b-2.

Leave a comment

Filed under Combinatorics, Geometry

Discriminants and Lattices

Let K=\mathbb Q(\alpha) be a quadratic number field. For a,b\in K, recall that the discriminant \Delta(a,b) is defined as

\displaystyle \Delta(a,b):=\left|\begin{matrix} a^{(1)} & a^{(2)}\\ b^{(1)} & b^{(2)}\end{matrix}\right|^2

where a^{(1)}, a^{(2)} are the Galois conjugates of a and b^{(1)}, b^{(2)} are those of b. For any \beta\in K we define its discriminant to be \Delta(\beta):=\Delta(1,\beta).

Write a=a_1+a_2\alpha and b=b_1+b_2\alpha. Then

\left(\begin{matrix} a\\ b\end{matrix}\right)=\underbrace{\left(\begin{matrix} a_1 & a_2\\ b_1 & b_2\end{matrix}\right)}_{A}\left(\begin{matrix} 1\\\alpha\end{matrix}\right)

If \alpha,\bar\alpha are the Galois conjugates of \alpha, then

\Delta(a,b)=\left|\begin{matrix} a_1+a_2\alpha & a_1+a_2\bar\alpha\\ b_1+b_2\alpha & b_1+b_2\bar\alpha\end{matrix}\right|^2=\left|\begin{matrix} a_1 & a_2\\ b_1 & b_2\end{matrix}\right|^2\left|\begin{matrix} 1 & 1\\\alpha & \bar\alpha\end{matrix}\right|^2

\therefore\boxed{\Delta(a,b)=(\det A)^2\Delta(\alpha)}

Now suppose that \mathbb Z[\alpha]=a\mathbb Z+b\mathbb Z. Then \mathbb Z[\alpha] is spanned by \{a,b\}, so there are integers p,q,r,s such that

\underbrace{\left(\begin{matrix} p & q\\ r & s\end{matrix}\right)}_{M}\left(\begin{matrix} a\\ b\end{matrix}\right)=\left(\begin{matrix} 1\\\alpha\end{matrix}\right)

So we have

MA\left(\begin{matrix} 1\\\alpha\end{matrix}\right)=\left(\begin{matrix} 1\\\alpha\end{matrix}\right).

Lemma. If P is a 2\times 2 matrix with integer coefficients and w=(1,\alpha)^T with \alpha\not\in\mathbb Q, then Pw=w if and only if P=I, the 2\times 2 identity matrix.

Proof. This follows from the \mathbb Z-linear independence of \{1,\alpha\}. More concretely,

\underbrace{\left(\begin{matrix} s & t\\ u & v\end{matrix}\right)}_{P}\left(\begin{matrix}1\\\alpha\end{matrix}\right)=\left(\begin{matrix} 1\\\alpha\end{matrix}\right)\Rightarrow\begin{cases}s+t\alpha=1\\ u+v\alpha=\alpha\end{cases}

\therefore s=1,\ t=0,\ u=0,\ v=1\Rightarrow P=I. \square

Thus MA=I, so that \det(M)\det(A)=1. But \det(M) and \det(A) are integers. Hence |\det(M)|=|\det(A)|=1, i.e. \Delta(a,b)=\Delta(\alpha). Thus

Fact. \{a,b\}\subset\mathbb Z[\alpha] spans \mathbb Z[\alpha] if and only if \Delta(a,b)=\Delta(\alpha).

Note that all of the above arguments generalize to arbitrary number fields.

A nice corollary:

Corollary. (a,b) and (c,d) generate \mathbb Z^2 (as a group) if and only if

\left|\begin{matrix} a & b\\ c & d\end{matrix}\right|=\pm 1.

In other words, two bases generate the same lattice only if their fundamental parallelograms have equal areas.

1 Comment

Filed under Geometry, Linear Algebra, Number Theory