finite projective plane

Finite projective planes from axioms

Let us start from the beginning and assume we are given a set of $n$ things called points and a set of $\nu$ things called lines, with an incidence relation between them (a point is incident with a line iff the line is incident with the point) that satisfies only two axioms, the two unique incidence properties:

• For any two distinct points, there is exactly one line through both of them.

• For any two distinct lines, there is exactly one point on both of them.

Given these http://planetmath.org/node/6940projective plane axioms we can apply the De Bruijn–Erdős theorem twice (once with the rôle of points and lines swapped) which tells us we must have $n=\nu$, and one of two possible configurations:

• One “degenerate” solution has one special line ${\mathrm{\ell }}_0$ and $n-1$ ordinary lines ${\mathrm{\ell }}_i$, and a special point P${}_0$ and $n-1$ ordinary points P${}_i$. Each P${}_i$ ($i\ne 0$) is incident with its own ${\mathrm{\ell }}_i$ and with ${\mathrm{\ell }}_0$; each ${\mathrm{\ell }}_i$ ($i\ne 0$) with its own P${}_i$ and with P${}_0$. Now ${\mathrm{\ell }}_0$ is incident with every point except ${\mathrm{\ell }}_0$ while P${}_0$ is incident with every line except ${\mathrm{\ell }}_0$.

• The other solution is a projective plane:

  • the number of points and the number of lines are of the form $q^2+q+1$ for some integer $q$;

  • each point is incident with $q+1$ lines and each line with $q+1$ points.

One usually avoids the degenerate case by demanding there is a quadrangle in the plane: four points no three of which lie on the same line. This, or a similar non-triviality clause, can then be adopted as a third axiom. Unfortunately it also has the effect of excluding projective planes of orders $q=0$ and $1$. The De Bruijn–Erdös (http://planetmath.org/DeBruijnErdHosTheorem) theorem actually makes an additional assumption: that no two lines are incident with the same set of points (and when applied dually that no two points are incident with the same set of lines). That is not a problem for a line incident with more than one point or vice versa, because then the axioms forbid it. We just get some more degenerate cases consisting of multiple lines intersecting one point or none, or vice versa; the insistence on a quadrangle catches these too.

I will not prove the whole theorem here, but under the assumption that a quadrangle exists it is not hard show the interesting part, that those numbers $q+1$ and $q^2+q+1$ drop out by necessity. The same construction can also be used to give coordinates to the points and lines of the plane (see below).

Projective planes as bipartite graphs

Projective planes are, apart from anything else, also bipartite graphs: let the $q^2+q+1$ points be represented by “black” nodes (vertices) of the graph, and let the $q^2+q+1$ lines also be nodes, “white” ones say. Edges will represent incidence between a “black” and a “white” node, so there are $(q^2+q+1)(q+1)=q^3+2q^2+2q+1$ edges in all.

• In a bipartite graph, nodes of the same color have even distance. This is 0 for any node and itself and must be 2 for any two distinct nodes of the same color: for any two points there is a path via the line they share, and for any two lines a path via the point they share. So distance 4 does not occur.

  For nodes of opposite color we can have 1 (if the point lies on the line) or 3 (otherwise); we can’t have distance 5 which would imply 4 for some nodes. So the graph has diameter (maximum distance) 3.

• In a bipartite graph, all cycles (if any) have even length. We don’t have 2-cycles (this is not a multigraph) but no 4-cycles either, by the following argument: such a cycle P$\mathrm{\ell }$Q$m$ would mean two lines intersecting in two different points, and vice versa. So the girth (minimum cycle length) is 6 (showing there indeed are 6-cycles for $q⩾2$ is left as exercise for the reader).

These two conditions, diameter 3 and girth 6, are not only necessary for the graph to represent a projective plane, they are also sufficient, and therefore form an alternative formulation of what it means to be a projective plane.

These graphs could be called the bipartite analogue of Moore graphs of diameter 2 and girth 5; many of the same arguments can be used [vG03].

Coördinates for finite projective planes

The details on how to impose coordinates on a projective plane can be found in [Hal59, dRe96], or in this entry (http://planetmath.org/IntroducingCoordinatesInAProjectivePlane). We summarize it for a finite projective plane below:

Setup: Use a set $Q$ of $q$ different symbols for coordinate values, two of which are 0 and 1. Start with four points O, I, X, Y forming a quadrangle. XY is the “line at infinity” $\mathrm{\ell }$.

Construction: O and I are given coordinates $(0,0)$ and $(1,1)$, and the other points on OI (except its intersection with $\mathrm{\ell }$) arbitrarily $(c,c)$ with unique $c\in Q$. For any point P not on $\mathrm{\ell }$, let YP intersect OI at $(a,a)$, and let XP intersect OI at $(b,b)$. Then P will be given $(a,b)$. For the coordinates of points on $\mathrm{\ell }$, intersect the lines joining $(0,0)$ with $(1,m)$, for all $m\in Q$, with $\mathrm{\ell }$, calling the intersection $(m)$. Finally, Y gets coordinate $()$ (instead of $(\mathrm{\infty })$ in the literature).

Lines not through Y are given coordinates $[m,k]$ where $(m)$ and $(0,k)$ are their intersections with $\mathrm{\ell }$ and with OY respectively; lines through Y (other than $\mathrm{\ell }$) get coordinates $[k]$ going by their intersection $(k,0)$ with OX. The line $\mathrm{\ell }$ gets $[]$ (instead of $[\mathrm{\infty }]$ in the literature).

Coordinates from bipartite graphs

The whole business with coordinates becomes a bit more transparent when we try to actually construct the thing as a bipartite graph, starting from one edge, Y$\mathrm{\ell }$ say.

There are $q$ more points (other than Y) incident to $\mathrm{\ell }$, let’s call them Y${}_m$ where $m$ ranges over the $q$ different values of the set $Q$. Again, each Y${}_m$ is incident to $q$ more lines (apart from $\mathrm{\ell }$), let’s call those ${\mathrm{\ell }}_{mb}$ where $b$ is another subscript from $Q$. Likewise there are $q$ more lines (other than $\mathrm{\ell }$) incident to Y, let’s call them ${\mathrm{\ell }}_x$ and to each of them are incident $q$ more points (apart from Y) which we can label Y${}_{xy}$.

This immediately produces the incidence list of the preceding section. Pictorially, for $q=2$ (with the “to be assessed” portion filled in as thinner lines):

We already have ${\mathrm{\ell }}_0$ containing all points Y${}_{0y}$, and in addition if we wanted we could easily arrange for ${\mathrm{\ell }}_{00}$ to be incident with all the Y${}_{x0}$ (just renumber the labels $y$ in the sets Y${}_{x0}$ for every $x$), and for ${\mathrm{\ell }}_{10}$ to be incident with all the Y${}_{cc}$ (just look at which Y${}_{xy}$ are incident with ${\mathrm{\ell }}_{10}$, then exercise the freedom we still have to relabel all the $x$, matching each time the corresponding $y$ there). This reproduces the entire coordinatisation.

Projective planes as permutation systems

Five sides of the hexagon are self-evident. On the left we have the single edge Y$\mathrm{\ell }$, along the top we fan out in two stages to $q$ and $q^2$ items, along the bottom we also fan out in two stages to $q$ and $q^2$ items, and the hard part is the right. We have by now accounted for $2q^2+2q+1$ edges so we know there must be exactly $q^3$ more edges, between some of those $q^2$ points and some of those $q^2$ lines. But where?

For $q=2$ it is simple enough to avoid 4-cycle clashes (and the diagram shows what is, up to isomorphism, the only solution). In general, it is an open problem to find all possible solutions.

From the projective plane properties it is easy to see that any point Y${}_{xy}$ must, for every value of $m$, be incident to no more than one of the ${\mathrm{\ell }}_{mb}$ (because if it was incident to two they would intersect both in our Y${}_{xy}$ and in their shared Y${}_m$ at the bottom). On the other hand, Y${}_{xy}$ needs $q$ more mates so it needs to choose exactly one ${\mathrm{\ell }}_{mb}$ for every value of $m$.

By exactly the same reasoning, any ${\mathrm{\ell }}_{mb}$ needs to be incident with, for every value of $x$, at most one and then exactly one Y${}_{xy}$. In other words, the projective plane structure takes the form of, for each pair of values $x$ and $m$, a bijection ${\psi }_{xm}$ between the $y$ indices and the $b$ indices.

This is not yet the only constraint. A closer analysis [vG03] shows that, in order to prevent any two lines meeting in more than one point or any two points in more than two lines, all compound bijections of the form

$${\psi }_{xm}{\psi }_{x^{\prime }m}^{-1}{\psi }_{x^{\prime }{m}^{\prime }}{\psi }_{x{m}^{\prime }}^{-1}$$

(for $m\ne m^{\prime }$ and $x\ne x^{\prime }$) must be derangements, i.e. permutations that do not leave any index in place. It is not hard to see this is just a device to prevent 4-cycles. And careful scrutiny of the graph shows that, after arranging 5 of 6 edges along trees fanning out as above, and after recognising there are those bijections along the sixth edge, these derangement shenanigans stop the only remaining gap for 4-cycles to lurk.

This could be called the permutation group interpretation of projective plane structure. The algebraic version appears in the next section.

Planar ternary rings

We’ve been giving our points and lines cooordinates from a set $Q$ of $q$ different labels. We can give $Q$ the structure of a ternary ring, that is, a set with a ternary operation $p\bullet q\circ r$, by defining

$$y=x\bullet m\circ b⟺(x,y)\text{is on}[m,b]$$ (1)

Thus, geometric properties of a projective plane may not be analyzed algebraically. See this entry (http://planetmath.org/TernaryRingOfAProjectivePlane) for more detail. Conversely, every ternary ring determines a projective plane with coordinates as above, so that algebraic properties of the ring can be interpreted geometrically. For more detail on this, see this entry (http://planetmath.org/ProjectivePlaneOfATernaryRing).

Fields and division rings are examples of ternary rings. But there are other classes of algebraic structures intermediate between fields and ternary rings. See [dRe96] for a survey. There are four different projective planes known of order 9, many more of order 16, and so on.

Finding all PTRs in general remains of course just as hard as finding projective planes!

Finite projective planes as incidence structures

Finite projective planes can be defined as (simple square) 2-$(q^2+q+1,q+1,\mathrm{\hspace{0.17em}1})$ designs, or what’s the same thing, Steiner systems $S(2,q+1,q^2+q+1)$. This way, we already assume in the definition that each “block” (line) contains exactly $q+1$ points, from which it follows by calculation that the number of lines that contain a given point is also $q+1$, and that the total number of lines equals the total number of points.

Also, the unique incidence property that every two points lie together on exactly one line is given, and the dual one that every two lines meet in exactly one point then follows from the numbers and the properties that define a design or Steiner system.

We took a different route to projective planes above: we saw we only need to start with these two unique incidence properties, and can prove from them that the number of points on a line and the number of lines through a point are both fixed (i.e. that the projective plane and its dual are both designs).

Finite projective planes as incidence matrices

Consider an arbitrary projective plane of order $q$. We know there are $n=q^2+q+1$ points and the same number of lines. Let $A$ be an $n\times n$ matrix of which the rows and columns represent lines and points of the plane, and give the value 1 to entries at intersections where the point (represented by the column) lies on the line (represented by the row), and leave the other entries zeros. Such an $A$ is known as the incidence matrix of the plane.

$A{A}^{\top }$ has rows and columns both representing lines, and the entries here are the dot products of any two rows of $A$, i.e. the number of points any two lines $l$ and $m$ have in common, which is $q+1$ when $l=m$ and 1 otherwise, by the projective plane properties.

where $I$ is the identity matrix (ones along the diagonal, zeros everywhere else) and $J$ is the matrix filled with ones in every entry. Note $A{A}^{\top }$ has this same value for every projective plane with $n$ points and $n$ lines, while $A$ on its own of course varies if there is more than one plane of the same order, as the plane is fully determined by its incidence matrix. Also, $A{A}^{\top }$ having this value is the only thing needed to make the plane specified by $A$ satisfy the projective plane properties; it is a fully equivalent formulation of those properties.

The determinant of $A$ is best evaluated via that of $A{A}^{\top }$, because ${(detA)}^2=(detA)(det{A}^{\top })=detA{A}^{\top }$, and we know every entry of $A{A}^{\top }$. The eigenvalues of any $n\times n$ matrix of the form $J+qI$ are easily seen to be

• $q+n$ (once) with eigenvector $𝐱$ for which $x_0=x_1=x_2\mathrm{\dots }$

• $q$ (multiplicity $n-1$) for the complementary eigenspace $x_0+x_1+x_2\mathrm{\cdots }=0$

by letting the matrix act on these eigenvectors. This gives

$$detA{A}^{\top }=q^{n-1}(q+n)$$

which in our case ($n=q^2+q+1$) amounts to

$$detA{A}^{\top }=q^{q^2+q}(q^2+2q+1)$$

As $q^2+q$ is even and the other factor a square, we get an integer

$$detA=\pm q^{\frac{q^2+q}{2}}(q+1)=\pm q^{\left(\genfrac{}{}{0pt}{}{q+1}{2}\right)}(q+1)$$

where the sign is moot, as $A$ has no correspondence between its columns and rows.

Existence

The Bruck–Ryser theorem [BR49] states that

If $q$ is the order of a projective plane, and $q\mathrm{\equiv }\mathrm{1}$ or $\mathrm{2}\mathit{}\mathrm{(}\mathrm{mod}\mathit{}\mathrm{\hspace{0.17em}\hspace{0.17em}4}\mathrm{)}$, then $q$ is the sum of two integer squares (one of which can be ${\mathrm{0}}^{\mathrm{2}}$).

It can be proven [BR49, Cam94] using the incidence matrix $A$, by a clever rearrangement of $𝐱A{A}^{\top }𝐱$ (plus one extra term) for an arbitrary vector $𝐱$, on which gradually constraints are imposed four components at a time using the fact that each integer is a sum of four squares. The argument only works when $q^2+q+1=n\equiv -1(\mathrm{mod}\mathrm{\hspace{0.17em}\hspace{0.17em}4})$, hence the constraint on $q$ (mod 4).

Interestingly, there is a partial converse [HR54]: whenever $q$ is allowed by the theorem (either congruent 0 or 3 (mod 4), or congruent 1 or 2 (mod 4) and a sum of two squares), there always is a rational $n\times n$ matrix $A$ (where $n=q^2+q+1$) such that $A{A}^{\top }=M$. Of course, the matrix is only a proper incidence matrix if that rational matrix only has entries 0 and 1.

The theorem doesn’t rule out any potential projective plane orders $q\equiv 0$ or $3(\mathrm{mod}\mathrm{\hspace{0.17em}\hspace{0.17em}4})$, but does rule out a large number of $q\equiv 1$ or $2(\mathrm{mod}\mathrm{\hspace{0.17em}\hspace{0.17em}4})$, starting with $n=6,14,21,22\mathrm{\dots }$. Note in passing that it is easy to prove no prime power falls foul of Bruck–Ryser, which is just as well, as (classical) planes exist for all those orders.

The only other order ruled out to date is 10, via an epic computer search by Lam, Swiercz and Thiel (read http://www.cecm.sfu.ca/organics/papers/lam/index.htmlhttp://www.cecm.sfu.ca/organics/papers/lam/index.html for Lam’s account).

All projective planes actually found to date, even the non-classical ones, have an order $q$ that is the power of a prime. The prime power conjecture says this is the case for all projective planes. It is still open.

Title	finite projective plane
Canonical name	FiniteProjectivePlane
Date of creation	2013-03-22 15:11:15
Last modified on	2013-03-22 15:11:15
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	11
Author	Mathprof (13753)
Entry type	Topic
Classification	msc 51E15
Classification	msc 51A35
Classification	msc 05B25
Related topic	ProjectivePlane2
Related topic	IncidenceStructures
Related topic	Geometry
Related topic	DeBruijnErdHosTheorem
Defines	prime power conjecture
Defines	planar ternary ring
Defines	PTR