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, 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. ]

1 Response to Pick’s Theorem and Some Interesting Applications

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