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.

Advertisements

Leave a comment

Filed under Combinatorics, Geometry

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s