Finite projective planes

Given a field F, finite or infinite, you can construct a projective plane over F by starting with pairs of elements of F and adding “points at infinity,” one point for each direction.

Motivation: Bézout’s theorem

A few days ago I mentioned Bézout’s theorem as an example of a simple theorem that rests on complex definitions. Bézout (1730–1783) stated that in general a curve of degree n and a curve of degree m intersect in nm points. There are a lot of special cases excluded by the phrase “in general” that go away when you state Bézout’s theorem in a sophisticated context.

To make Bézout’s theorem rigorous you have to work over an algebraically complete field (e.g. the complex numbers rather than the real numbers), you have to count intersections with multiplicity, and you have to add points at infinity, i.e. you have to work in a projective plane.

Motivation: Elliptic curves

Bézout’s theorem involves infinite field ℂ, but this post is about finite projective planes. Elliptic curves over finite fields provide a motivating example of working in finite projective planes.

This blog is served over HTTPS and so serving up its pages involves public key cryptography. And depending on what protocol your browser negotiates with my server, you may be using elliptic curve cryptography to view this page.

An elliptic curve over a finite field is not an ellipse and not a curve, at least not a curve in the sense of a continuum of points. Elliptic curves over ℝ really are curves in the usual sense, but the definition is then abstracted in a way that extends to any field, including finite fields.

Homogeneous coordinates

In order to make this idea of “points at infinity” rigorous, we have to introduce a new coordinate system. We now describe points by (equivalence classes of) triples of field elements rather than pairs of field elements. The benefit of this added complexity is that points at infinity can be handled perfectly rigorously. Often the third coordinate can be ignored, but then you pay attention to it when you need to be careful.

In homogeneous coordinates, we consider two points (x, y, z) and (x′, y′, z′) equivalent if there is a λ ≠ 0 such that

(x, y, z) = (λx′, λy′, λz′).

Also, we require that not all three coordinates are 0, i.e. (0, 0, 0) is not an element of the projective plane.

We associate a point (x, y) with the triple (x, y, 1) and all its equivalents, i.e. all triples of the form (λx, λy, λ) with λ ≠ 0.

Points at infinity

A point at infinity is simply a point with third coordinate 0.

In the post mentioning Bézout’s theorem I said in passing that the lines y = 5 and y = 6 meet at infinity. Here’s how we can make this rigorous. The line y = 5 in the finite plane is the set of points of the form (x, 5), which embed in the projective plane as

(x, 5, 1)

and these points are equivalent to the set of points

(1, 5/x, 1/x)

Now take the limit as x → ∞ and we get (1, 0, 0). We consider this addition point to be part of the line y = 5 when the line is considered part of the projective plane. You can see that the line y = 6 contains the same point. So we can be very specific about where the lines y = 5 and y = 6 intersect: they intersect at (1, 0, 0).

You can go through a similar exercise to show that the lines y = x and y = x – 57 also intersect “at infinity” but at a different point at infinity, namely at (1, 1, 0) and its equivalents.This also shows that although the lines y = 5 and y = x both go off to infinity, they “reach” infinity at different points. The former goes to the point at infinity associated with horizontal lines and the latter goes to the point at infinity associated with 45 degree lines.

Note also that parallel lines meet at one point at infinity, not two. You might want to say, for example, that y = 5 and y = 6 meet twice, once at positive infinity and once at negative infinity. You could construct a system that works that way, but that’s not now projective planes work. Since non-zero multiples of a point are equivalent, (1, 0, 0) and (-1, 0, 0) are in the same equivalence class.

See this post for practical examples of when you might choose to have one or two points at infinity depending on your application.

Finite projective planes

We can construct projective planes containing a finite number of points by repeating the construction above using a finite field F. Finding finite projective planes not isomorphic to one constructed this way is hard [1].

Let F be a finite field with q elements. Then q is necessarily either a prime or a power of a prime, though that fact isn’t needed here.

The points of the finite projective plane over F are the points of the finite plane over F, i.e. pairs of elements of F, and the additional “points at infinity.” We can say exactly what these points at infinity are and count them.

A point (x, y) is embedded in the projective plane as (x, y, 1) and all points in its equivalence class. So for starters we have at least q² points in the finite projective plane, one for each pair (x, y).

First consider the case x ≠ 0. Then (x, y, 1) is equivalent to (1, y/x, 1/x) and so without loss of generality we can assume x = 1 (the multiplicative identity of the field). So for each y, (1, y, 0) is a point at infinity. That gives us q more elements of the finite projective plane.

Next consider the case x = 0. Then (0, y, 0) is another point at infinity as long as y ≠ 0. It’s only one point, because all non-zero multiples of (0, 1, 0) are in the same equivalence class.

So all together we have q² + q + 1 points, represented by the following elements of their equivalence classes:

• (x, y, 0) for all x, y in F,
• (1, y, 0) for all y, and
• (0, 1, 0).

Related posts

• Elliptic curves used in cryptography
• Vector spaces over finite fields
• Curve 25519

[1] There are for non-isomorphic finite projective planes of order 9, i.e. planes with 9² + 9 + 1 = 91 points. And there are other examples of finite projective planes not isomorphic to planes constructed as outlined here. However, so far all such planes have the same number of points as a finite projective plane constructed as above.