Proof of the number of nodes in a finite projective plane

A finite projective plane is a hypergraph in which 1. Any two edges shere exactly one node 2. There is exactly one edge containing any given pair of nodes 3. You can choose 4 nodes such that no three are contained in a common edge

I'm trying to solve an exercise to prove that for any such object, the number of nodes is $n^2+n+1$ for some n. I pretty much have a proof, which I will post as an answer. However, what I'm really looking for is a cleaner proof or way of thinking about it, as my method seems way too convoluted.

-
Not going to take the time to write up a full answer right now, but the usual method is that first you show that every line has the same number of points (call it n+1 -- n is called the order of the projective plane), then you show every point has the same number of lines, and then that this is also n+1. I guess you don't actually need all of that for just this, but it's true so you may as well prove it. :) Note therefore the number of lines is n^2+n+1 as well! – Harry Altman Nov 15 '11 at 6:07
For an elementary and well write account of finite projective (the related finite affine planes) look at Excursions into Mathematics by A. Beck, M. Bleicher, and D. Crowe, A.K. Peters, 2000. (The Chapter Exotic Geometries, Section 9 deals with Finite Geometries.) In particular the "combinatorics" of such planes - total number of points, number of points on a line, number of lines through a point, etc. is treated. – Joseph Malkevitch Jan 15 '12 at 15:23

If we have a line $L$ containing $s$ points and a point $P$ not on $L$, then the $s$ lines joining $P$ to the points of $L$ are distinct and account for all of the lines through $P$. Hence all points not on $L$ have the same number $s$ of lines passing through them.

Likewise, if we have a point $P$ with $t$ lines through it and a line $L$ that does not pass through $P$, then the $t$ points of intersection of the lines through $P$ with $L$ are distinct, and account for all of the points of $L$. Hence all of the lines that do not pass through $P$ contain the same number $t$ of points.

Axiom 3 guarantees us a quadrangle. Let's say its points are $a$, $b$, $c$, $d$. Let the number of points on the line $\overline{cd}$ be $n+1$. Neither $a$ nor $b$ lies on $\overline{cd}$. Therefore both $a$ and $b$ have $n+1$ lines passing through them. Since neither $b$ nor $c$ lies on $\overline{ad}$, the same number of lines pass through each, so $c$ also has $n+1$ lines passing through it. Now every line of the plane avoids at least one of $a$, $b$, $c$. Hence every line contains $n+1$ points.

Furthermore, every point lies off of at least one line, which implies that every point has $n+1$ lines passing through it. To see that every point lies off of at least one line, observe that $\overline{ab}$ and $\overline{cd}$ have exactly one point in common - call it $e$. Every point other than $e$ lies off of at least one of $\overline{ab}$ and $\overline{cd}$, while $e$ itself lies off of $\overline{ac}$ since $a$, $b$, $c$, $d$ is a quadrangle.

To count the points of the plane, let $P$ be a point. Every point of the plane except for $P$ lies on exactly one of the $n+1$ lines through $P$. Each of these lines contains $n$ points apart from $P$, for a total of $(n+1)n+1$ points. That the number of lines in the plane is also $n^2+n+1$ can be shown similarly.

-
Referring to the third part of your proof, Why can't there be 3 lines through each point? (e.g. lines $\overline{ab}$, $\overline{ac}$, and $\overline{ad}$ all go through point a, but each only have two points on each line, their endpoints) – Amber Sep 20 '13 at 16:53
@Amber: There can be three lines through each point; the projective plane with exactly three lines through each point is called the Fano plane. But it is not the case that there are only two points on each line. This is not hard to see. – Will Orrick Sep 21 '13 at 5:42
@Amber: Let $a,b,c,d$ be points of a quadrangle and suppose that there are exactly three lines through $a,$ namely $\overline{ab},$ $\overline{ac},$ and $\overline{ad}.$ The line $\overline{bc}$ is distinct from these three lines by definition of quadrangle. Each of the lines $\overline{ab},$ $\overline{ac},$ and $\overline{ad}$ must intersect $\overline{bc}$ in a point. Clearly $\overline{ab}$ and $\overline{ac}$ do, but $\overline{ad}$ must intersect $\overline{bc}$ in a new point $e.$ Therefore $\overline{ad}$ contains a third point. – Will Orrick Sep 21 '13 at 5:43
@Amber: Similar arguments, replacing $\overline{bc}$ with $\overline{bd}$ and $\overline{cd},$ establish that $\overline{ac}$ and $\overline{ab}$ each contains a third point. – Will Orrick Sep 21 '13 at 13:44
@Amber: Without the third axiom, you could indeed have configurations like the one you describe. For example, let there be $n+1$ points, $p,q_1,q_2,\ldots,q_n,$ and let there be $n$ lines $\overline{pq_j}$ containing two points, and one line $\overline{q_1q_2\ldots q_n}$ containing $n$ points. If there must be a quadrangle, however, such configurations are impossible. – Will Orrick Sep 21 '13 at 13:46

My idea at the moment goes as follows: Given an arbitrary projective plane, take the (one of the) longest line(s), and call the number of nodes in this line $n+1$. Note that $n \ge 2$. Separate one node out as the "leader" node. We know that there are at least two other nodes because of rule 3. There are two possibilities for how these nodes add on, given in the picture below (for the $n=4$ case). The leftmost node in each configuration is the "leader."

Now, in the left configuration, there must be a line from 1a to 1b, as well as from 2a to 1b. These cannot both contain 1c, but they must cross the line going from the leader to 1c. Therefore, there must be a "2c" node. This reduces the left configuration to a stronger version of the right configuration.

Now, for the right configuration. There is one line going down from each $1a \dots na$ through each $1b \dots kb$. Each of the lines $2a\to2b \dots na\to2b$ must intersect the line $1a\to1b$, but since they have all already touched, they must each meet $1a\to1b$ at a new node, so we get $n-1$ new nodes. These must all be in different rows, so we now have a total of $n+1$ rows. Sort these rows by length, so the $n+1$th is the shortest. If the $n+1$th row is shorter than the 2nd, then some line that I have already created does not reach the line going from the leader through the $n+1$th row. Therefore, all of the rows $b$ and on must be the same length.

Since n is at least 2, there are at least three rows, so we can look at the last two rows to see that there must be $m^2$ lines between them, where m is the length of the last row (excluding the leader). These must be the same lines as between the first two rows, and it is clear that there are $nm$ lines connecting the first two rows, so we see that $n=m$. Therefore, it is clear that, if this is a finite projective plane, it is an $(n+1)n$ grid, along with a leader node.

-
Presumably you mean an arbitrary finite projective plane. It seems strange to talk about "longest" line in such a plane. All the lines in a fixed finite projective have the same number of points on them. In fact, this is a helpful lemma in counting what the total number of points in a finite projective plane of "order" n. Traditionally, one says the plane has order n if it has n+1 points on some line. Planes are known for when n is a prime power and it is still an open problem as to whether all finite projective planes have prime power order. The plane of order 2 is known as the Fano plane. – Joseph Malkevitch Nov 15 '11 at 16:35
Although that is true, I was assuming only the 3 things at the top of my original post, and by "longest" I really mean "not shorter than any other line". I guess I'll think more about whether I can prove that all lines the same amount of points easily. – Carl Nov 16 '11 at 1:08