Pick’s Theorem and Some Interesting Applications

[ Background required: none. ]

A lattice point on the cartesian plane is a point (x,y) \in \mathbb R^2 where both coordinates are integers. Let P be a polygon on the cartesian plane such that every vertex is a lattice point (we call it a lattice polygon). Pick’s theorem tells us that the area of P can be computed solely by counting lattice points:

The area of P is given by i + \frac b 2 -1, where i = number of lattice points in P and b = number of lattice points on the boundary of P.

For example, the area of the polygon below is 4 + 12/2 – 1 = 9 square units.

The polygon can be of arbitrary shape and size, concave or convex, but it mustn’t have a hole in it. For example, in the diagram below, the area should be 11/2 and not 9/2. To achieve the right formula, each hole contributes a value of +1 to the equation. This means that Pick’s formula is sensitive to the topology of the diagram (which reminds us of Euler’s V-E+F formula, but that’s another story for another day).

It’s a lovely result. Unfortunately, there’s no short proof of it, so we will merely hightlight the steps which constitute a possible proof:

  • An elementary triangle is a lattice polygon with i=0, b=3. Thus it contains no lattice points other than the 3 vertices. By chopping P into a union of elementary triangles, we only need to focus on this case.
  • Without loss of generality, assume = (0, 0), v = (a, b), w = (c, d). It suffices to show that the parallelogram P formed by 0, v, w and v+w has area 1 if P contains no lattice points other than the 4 vertices.
  • On one hand, the area is given by |ad-bc| \ge 1.
  • On the other hand, for any (m,n)\in \mathbb Z \times \mathbb Z, m, n not both zero, P and the translate P + (m, n) have disjoint interior. [ If they share an interior point, then P must contain a vertex of P + (m, n) which is not one of 0, v, w, v+w. ]
  • Hence, if we cut the parallelogram according to the gridlines and translate them to the unit square 0 \le x, y \le 1 (see below), the pieces do not intersect. As a result, the area is at most 1.

Physical Intuition

Here’s a nice way of looking at Pick’s theorem: imagine the sides of the polygon forming the walls of a room, and at each lattice point, a light is placed. The sum of the angles formed by the lights within the room then add up to 2\pi (i + b/2 - 1). Indeed: each light at an internal point clearly contributes 2\pi while the sum of the angles in an m-sided polygon is \pi(m - 2) by elementary geometry.

This intuition also explains why the formula fails when the polygon contains a hole. In our example earlier (a triangle with a triangular hole), we have to take the sum of the external angles of the triangular hole, thus giving 5\pi on the inside and 6\pi on the outside. So the total angle is 11\pi which corresponds to an area of 11/2.

Application : Farey Sequence

Fix a bound N and consider all positive rational numbers \frac a b where b \le N. Arrange them in increasing order. E.g. for N = 4, we get:

\frac 0 1 < \frac 1 4 < \frac 1 3 < \frac 1 2 < \frac 2 3 < \frac 3 4 < \frac 1 1 < \frac 5 4 < \dots

This is called the Farey sequence of order N. For any two consecutive fractions \frac a b < \frac c d in lowest terms, we have bc - ad = 1. Although not obvious at first glance, this follows directly from Pick’s theorem. Indeed, let’s draw a ray from the origin (0, 0) to the point (a, b) for each reduced fraction \frac a b in the sequence. Note that \frac a b is precisely the gradient of this ray. Then the Farey sequence is obtained by sweeping a ray through the origin, starting at angle \theta = 0 and stopping whenever the ray hits a lattice point (a, b) for some 1 \le b \le N, i.e. the shaded region below:

Why does it follow that bc - ad = 1 for, say, points B and C? Consider the triangle OBC.

  • The open line segment OB contains no lattice points since \frac a b is reduced.
  • Likewise, open segment OC contains no lattice points.
  • Open segment BC and the interior of OBC contain no lattice points because such a point would correspond to another ray between OB and OC, thereby contradicting the fact that \frac a b and \frac c d are consecutive in the Farey sequence. This requires the fact that the shaded region is convex. [ A region R is said to be convex if whenever points P and Q lie in R, so is the entire line segment PQ. ]

Hence by Pick’s theorem, the area must be 1/2. On the other hand, by coordinate geometry the area is also \frac 1 2 (bc-ad), so the result follows.

Note that we can vastly generalise the result. E.g. suppose we take all fractions \frac a b for a^2 + b^2 \le N^2 and sort them in ascending order. Then since the resulting shaded region is also convex, we also have bc-ad=1 for any consecutive reduced fractions \frac a b < \frac c d.

Ford Circles

Start with two horizontal lines: y=0 and y=1. At each integer m, construct the circle with ends of the diameter at (m, 0) and (m, 1). This gives an infinite sequence of circles with radii 1/2 which are tangent to both lines. Now between two neighbouring circles, construct the circle which is tangent to both, and also to the line y=0. If we iterate this process, we eventually get something like:

The nice thing is that the point at which each circle touches the line y=0 is rational, and two circles are tangent if and only if the corresponding rational numbers are consecutive in a Farey sequence of some order.

Theorem. Let 0 < r_1 < r_2 < \dots be a Farey sequence of some order. Write r_i = \frac {a_i}{b_i} in lowest terms and construct a circle on the upper-half plane which is tangent to (r_i, 0) and has radius \frac 1 {2b_i^2}. Then two consecutive circles are tangent.

The proof is quite straight-forward as it merely uses the fact that consecutive fractions \frac a b < \frac c d satisfy bc - ad = 1. [ Try it. ]

This entry was posted in Extra and tagged , , , , , , . Bookmark the permalink.

One Response to Pick’s Theorem and Some Interesting Applications

  1. Pingback: MAT-1: Pick’s Theorem (G. Pick, 1899) « Sid Nadendla

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