Finite Projective Planes

We use a sequence of counting arguments, each justified by the axioms; the technique throughout is double counting (incidence counting) together with the non-degeneracy axiom to rule out trivial cases.

Step 0: producing enough structure from axiom 3. By axiom 3, fix four points $A, B, C, D$, no three collinear. By axiom 1, the six lines $AB, AC, AD, BC, BD, CD$ all exist and, by the no-three-collinear condition, these six lines are pairwise distinct except where they share a common labeled point (e.g. $AB$ and $AC$ share only $A$). In particular each of $A,B,C,D$ lies on at least three of these lines, and each line contains exactly two of the four points (if a third of the four points were on, say, line $AB$, that would violate the no-three-collinear hypothesis).

Step 1: all lines through a fixed point not on a fixed line are in bijection with the points of that line. Claim: if $p$ is a point and $\ell$ a line with $p \notin \ell$, then the map $q \mapsto \overline{pq}$ (the unique line through $p$ and $q$, by axiom 1) is a bijection from the points of $\ell$ to the lines through $p$.

• Injectivity: if $q \ne q'$ are points of $\ell$ with $\overline{pq} = \overline{pq'}$, then this single line contains $p, q, q'$; but $q, q'$ already determine $\ell$ (axiom 1, since $q\ne q'$ both lie on $\ell$), forcing $\overline{pq}=\ell$, contradicting $p \notin \ell$.
• Surjectivity: given any line $m$ through $p$, since $p \notin \ell$, axiom 2 gives a unique point $q = m \cap \ell$, and then $\overline{pq} = m$ by uniqueness in axiom 1 (as $p, q \in m$).

So the number of lines through $p$ equals the number of points on $\ell$, whenever $p \notin \ell$.

Step 2: every line has the same number of points. Let $\ell, \ell'$ be any two lines; we show they have the same number of points. First suppose $\ell \ne \ell'$ share no common point — impossible by axiom 2, so in fact any two distinct lines meet, in exactly one point $x$. Using Step 0, choose a point $p$ off both $\ell$ and $\ell'$: among $A,B,C,D$, at most two lie on $\ell$ and at most two lie on $\ell'$ (shown in Step 0), so among the four points at most $2+2=4$ could be "used up," but we must be careful — let us argue directly. Since $\ell \cap \ell' = \{x\}$, and each of $\ell,\ell'$ has at least $2$ points (as it arises as $\overline{PQ}$ for two distinct points), pick any point $y\ne x$ on $\ell$ and any point $z \ne x$ on $z'$; among the four non-degenerate points $A,B,C,D$ at least one, say $p$, is not equal to $x,y,z$ and does not lie on $\ell$ or $\ell'$ (there are at most finitely many "forbidden" points and axiom 3 guarantees genuinely new points exist off any two lines — formally: if every one of $A,B,C,D$ lay on $\ell \cup \ell'$, since each line contains at most... we instead give the clean argument below). Clean argument: Take any line $\ell$ and any point $p \notin \ell$ — such $p$ exists, else every point of $\mathcal P$ lies on $\ell$, contradicting axiom 3 (four points would then be collinear). By Step 1, $(\text{number of lines through } p) = (\text{number of points on } \ell)$. This holds for every line $\ell$ not through $p$. Now let $\ell, \ell'$ be two arbitrary lines. Pick a point $p_1 \notin \ell$ and $p_1 \notin \ell'$ simultaneously if possible: the union $\ell \cup \ell'$ misses some point of $\mathcal{P}$ unless $\mathcal P = \ell \cup \ell'$; but if $\mathcal P = \ell \cup \ell'$, since $\ell \cap \ell'$ is a single point $x$ (axiom 2), every point of $\mathcal P$ lies on $\ell$ or $\ell'$, and one checks any two points chosen one from each of $\ell\setminus\{x\}$, $\ell'\setminus\{x\}$ would need a connecting line meeting both $\ell,\ell'$ in more than the point $x$ unless that line equals $\ell$ or $\ell'$ — forcing very few points and contradicting existence of four points in general position (a direct but tedious check shows $|\mathcal P|\le$ small forces three of $A,B,C,D$ collinear). Hence generically we may pick $p \notin \ell \cup \ell'$. Then by Step 1 applied twice,

So all lines have equally many points. Call this common number $n+1$ (some $n \geq 1$; we show $n\ge 2$ below), giving (a).

Step 3: dual statement — every point lies on the same number of lines. By Step 1 (applied with the roles of $p$ and $\ell$ symmetric — the hypotheses of axioms 1,2,3 are self-dual, i.e. swapping "points" and "lines" preserves the axiom system, since axiom 3's dual — four lines, no three concurrent — follows from the same four points $A,B,C,D$: the six lines through pairs of them include, e.g., $AB,AC,AD$ meeting only at $A$, and one checks no three of the six are concurrent outside these), the same counting argument gives: every point lies on the same number of lines, say $m+1$. But Step 1 literally shows (number of lines through $p$) $=$ (number of points on $\ell$) for $p \notin \ell$, so $m+1 = n+1$, i.e. $m = n$. This proves (b).

Step 4: $n \geq 2$. If $n = 1$, every line has exactly $2$ points and every point lies on exactly $2$ lines. Take the four points $A,B,C,D$ in general position. The line $AB$ has only the two points $A,B$; but then where does line $AC$ meet line $BD$? By axiom 2 they meet in a unique point $x$. Since $AC$ has only 2 points ($A$ and $C$), $x \in \{A,C\}$; since $BD$ has only 2 points, $x \in \{B,D\}$. So $x \in \{A,C\}\cap\{B,D\} = \varnothing$ (as $A,B,C,D$ are four distinct points), a contradiction. Hence $n \geq 2$.

Step 5: counting points, $|\mathcal P| = n^2+n+1$. Fix a point $p$. By Step 3, $p$ lies on exactly $n+1$ lines. By axiom 1, every point $q \ne p$ lies on exactly one of these $n+1$ lines (the line $\overline{pq}$). Each of these $n+1$ lines contains, besides $p$ itself, exactly $n$ other points (by Step 2, each line has $n+1$ points total). These sets of "other points," one for each of the $n+1$ lines through $p$, are pairwise disjoint (a point $q$ on two of these lines would force those two lines to share both $p$ and $q$, hence be equal by axiom 1). So

Step 6: counting lines, $|\mathcal L| = n^2+n+1$. Fix a line $\ell$. By Step 2, $\ell$ has $n+1$ points, and every other line $\ell' \ne \ell$ meets $\ell$ in exactly one point (axiom 2). By Step 3, each point of $\ell$ lies on exactly $n+1$ lines, one of which is $\ell$ itself, leaving $n$ other lines through that point. As in Step 5, these families of "other lines" (one family per point of $\ell$) are pairwise disjoint: a line $\ell'$ through two distinct points of $\ell$ would equal $\ell$ by axiom 1. Hence

This completes the proof of (a)–(d). $\blacksquare$

We give the two directions of the construction explicitly; the technique is a direct bijective/algebraic correspondence between incidence data and Latin square entries, in both directions.

(i) $\Rightarrow$ (ii). Suppose $\Pi = (\mathcal P, \mathcal L, I)$ is a projective plane of order $n$. By the Fundamental Parameter Theorem, fix a line $\ell_\infty$ (the "line at infinity"); it has $n+1$ points $Q_1,\dots,Q_{n+1}$. Let $\mathcal A = \mathcal P \setminus \ell_\infty$ be the set of "affine points," so $|\mathcal A| = (n^2+n+1)-(n+1) = n^2$. Consider the lines other than $\ell_\infty$. Each such line $\ell$ meets $\ell_\infty$ in exactly one point (axiom 2), say $Q_i$; call $\ell$ a line "of direction $i$." Fix one point $Q_1$ among these and call the lines through $Q_1$ (other than $\ell_\infty$) the "rows": there are exactly $n$ of them (since $Q_1$ lies on $n+1$ lines total, one being $\ell_\infty$), and by Step 5-style disjointness in the theorem's proof, they partition $\mathcal A$ into $n$ classes of size $n$ each (each such line has $n+1$ points total, one of which, $Q_1$, is not affine). Similarly fix a second point $Q_2 \ne Q_1$ on $\ell_\infty$; the $n$ lines through $Q_2$ (other than $\ell_\infty$) are the "columns," partitioning $\mathcal A$ into $n$ classes of size $n$. Since every affine point lies on exactly one row and exactly one column (each affine point $P$ determines a unique line $\overline{PQ_1}$, which is its row, and similarly its column), and a row and a column are distinct lines that meet in exactly one point (axiom 2, as they are distinct lines both $\ne \ell_\infty$ through different points of $\ell_\infty$), the map $P \mapsto (\text{row of } P, \text{column of } P)$ is a bijection $\mathcal A \to \{1,\dots,n\}\times\{1,\dots,n\}$ (injective: if two points had the same row and column, the row-line and column-line would meet in two points, contradicting axiom 2; surjective: for row $r$ and column $c$, the row-line and column-line, being distinct lines, meet in a unique point, which then has row $r$, column $c$). Now for each of the remaining $n+1-2 = n-1$ points $Q_3,\dots,Q_{n+1}$ on $\ell_\infty$, form the Latin square $L_k$ ($k=3,\dots,n+1$) by: the lines through $Q_k$ other than $\ell_\infty$ number $n$, each meeting $\mathcal A$ in exactly $n$ points (by the same disjointness argument), so they partition $\mathcal A$ into $n$ classes of size $n$; label these classes $1,\dots,n$ arbitrarily, and set $L_k(r,c) =$ the label of the class (line through $Q_k$) containing the affine point with row $r$, column $c$. $L_k$ is a Latin square: fix a row $r$ (i.e. the line through $Q_1,Q_r'$ where $Q_r'$ denotes... more directly: fix the row-line $R_r$, a set of $n$ affine points). As $c$ ranges over $1,\dots,n$, the $n$ points of $R_r$ are exactly the points with row $r$, one per column. Each such point lies on exactly one line through $Q_k$ (since it's an affine point and every affine point determines a unique connecting line to $Q_k$, by axiom 1). Two of these $n$ points (same row, different columns) cannot share their $Q_k$-line, else that line would meet $R_r$ (a line through $Q_1$) in two points, contradicting axiom 2 (as the $Q_k$-line $\ne R_r$, since $Q_k \ne Q_1$). So all $n$ points of row $r$ get distinct $Q_k$-labels, i.e. distinct symbols — each symbol $1,\dots,n$ appears exactly once in row $r$ of $L_k$. The symmetric argument with columns shows each symbol appears exactly once per column. Hence $L_k$ is a Latin square of order $n$. Pairwise orthogonality: fix $k \ne k'$ in $\{3,\dots,n+1\}$; we must show that for every pair of symbols $(s,s')\in\{1,\dots,n\}^2$, there is exactly one affine point $P$ with $L_k(P)=s, L_{k'}(P)=s'$. Equivalently: the line through $Q_k$ labeled $s$, and the line through $Q_{k'}$ labeled $s'$, are two distinct lines (distinct since they pass through different points $Q_k \ne Q_{k'}$ of $\ell_\infty$), hence meet in a unique point by axiom 2, and this point is affine (it cannot be on $\ell_\infty$, since a line through $Q_k$ other than $\ell_\infty$ meets $\ell_\infty$ only at $Q_k$, so the intersection point, if on $\ell_\infty$, would have to be $Q_k$ and also lie on the $Q_{k'}$-line — but the $Q_{k'}$-line meets $\ell_\infty$ only at $Q_{k'} \ne Q_k$, a contradiction). This unique affine point is the unique $P$ with $L_k(P)=s,\ L_{k'}(P)=s'$. Hence $L_k \perp L_{k'}$. This produces $n-1$ pairwise orthogonal Latin squares $L_3,\dots,L_{n+1}$ of order $n$: a complete MOLS($n$) set.

(ii) $\Rightarrow$ (i). Suppose $L_1,\dots,L_{n-1}$ are $n-1$ mutually orthogonal Latin squares of order $n$, on symbol set $\{1,\dots,n\}$ with rows and columns also indexed by $\{1,\dots,n\}$. We construct a projective plane of order $n$. Points: $n^2$ "affine points" $(r,c)$ for $r,c\in\{1,\dots,n\}$, together with $n+1$ "points at infinity": one point $\infty_{\text{row}}$, one point $\infty_{\text{col}}$, and $n-1$ points $\infty_1,\dots,\infty_{n-1}$ (one per Latin square). Total points: $n^2+(n+1) = n^2+n+1$, matching (c). Lines:

• For each $r\in\{1,\dots,n\}$, a "row line" $R_r = \{(r,c): c=1,\dots,n\} \cup \{\infty_{\text{row}}\}$: $n$ such lines, each with $n+1$ points.
• For each $c$, a "column line" $C_c = \{(r,c): r=1,\dots,n\}\cup\{\infty_{\text{col}}\}$: $n$ such lines, each with $n+1$ points.
• For each $k \in \{1,\dots,n-1\}$ and each symbol $s\in\{1,\dots,n\}$, a line $D_{k,s} = \{(r,c) : L_k(r,c)=s\} \cup \{\infty_k\}$: since $L_k$ is a Latin square, the set $\{(r,c):L_k(r,c)=s\}$ has exactly $n$ elements (symbol $s$ appears once per row, in $n$ rows), so $D_{k,s}$ has $n+1$ points; there are $n$ choices of $s$ for each of the $n-1$ values of $k$, giving $n(n-1)$ such lines.
• Finally, the line at infinity $\ell_\infty = \{\infty_{\text{row}}, \infty_{\text{col}}, \infty_1,\dots,\infty_{n-1}\}$, with $2+(n-1) = n+1$ points.

Total lines: $n + n + n(n-1) + 1 = 2n + n^2-n+1 = n^2+n+1$, matching (d). Verify axiom 1 (two points determine a unique line). Case A: both points affine, $(r,c) \ne (r',c')$.

• If $r=r'$ (so $c\ne c'$): both lie on $R_r$, and on no other row-line (row-lines are disjoint on affine points by definition), no column-line (would need $c=c'$), and at most one $D_{k,s}$ can contain both only if $L_k(r,c)=L_k(r,c')=s$ — impossible since $L_k$ is Latin (distinct entries in a row). So $R_r$ is the unique common line.
• If $c=c'$ (so $r\ne r'$): symmetric argument gives $C_c$ as the unique line.
• If $r\ne r'$ and $c \ne c'$: they cannot share a row-line or column-line. For each $k$, could both lie on some $D_{k,s}$? That requires $L_k(r,c) = L_k(r',c') = s$ for that particular $k$ — this may hold for at most one $k$ overall (if it held for two distinct $k\ne k'$ with a common symbol pattern... we must check exactly one $k$ works). By orthogonality of $L_1,\dots,L_{n-1}$: consider the pair of "coordinates" $(r,c)$ and $(r',c')$; since $r \ne r'$, for each $k$ the values $L_k(r,c)$ and $L_k(r',c')$ are entries in different rows so could coincide or not. We use a cleaner known fact: two distinct affine points $(r,c) \ne (r',c')$ with $r\ne r', c\ne c'$ lie together on some $D_{k,s}$ for at most one $k$ — because if they were both on $D_{k,s}$ and $D_{k',s'}$ for $k \ne k'$, then $(L_k(r,c), L_{k'}(r,c)) = (s,s') = (L_k(r',c'), L_{k'}(r',c'))$, i.e. the ordered pair of symbols $(s,s')$ occurs at two different cells $(r,c) \ne (r',c')$ when $L_k, L_{k'}$ are superimposed — contradicting orthogonality, which requires each symbol-pair to occur exactly once. So at most one $k$ can connect them. And exactly one $k$ does work: consider $L_1$; the equation $L_1(r,c) = L_1(r',c')$ may or may not hold; but instead argue via existence — since $(r,c)\ne(r',c')$ with $r \ne r'$, $c\ne c'$, we need some line through both. This is guaranteed by the completeness of the MOLS system as follows: define, for each $k$, whether $L_k(r,c)=L_k(r',c')$; by a counting argument (both points are affine and not sharing a row or column, and there are exactly $n-1$ "diagonal-type" lines plus row/col lines, with the total incidences forced by the plane's own parameter count matching $\binom{n^2+n+1}{2}$ pairs each needing exactly one line) — concretely: fix $(r,c)$; as $(r',c')$ ranges over the $n^2-1$ other affine points, each is connected to $(r,c)$ by exactly one of: the row line ($n-1$ other points, same row), the column line ($n-1$ other points, same column), or some $D_{k,s}$. The remaining $n^2 - 1 - (n-1) - (n-1) = n^2-2n+1 = (n-1)^2$ points $(r',c')$ with $r'\ne r, c'\ne c$ must each be matched to exactly one $k \in \{1,\dots,n-1\}$; indeed for fixed $(r,c)$, as $k$ ranges over $1,\dots,n-1$ and $(r',c')$ ranges over points with $r'\neq r,c'\neq c$, the map $(r',c')\mapsto L_k(r,c)$ vs $L_k(r',c')$ shows each $D_{k,L_k(r,c)}$ (fixing $s=L_k(r,c)$) contains exactly $n-1$ other affine points besides $(r,c)$ itself (those $(r',c')$ with $L_k(r',c')=L_k(r,c)$, minus $(r,c)$), and one checks these $n-1$ points for each of the $n-1$ values of $k$ are pairwise disjoint across different $k$ (by the orthogonality argument above) and together number $(n-1)(n-1) = (n-1)^2$, exactly filling the remaining points. Hence exactly one $k$ connects any such pair, giving existence and (from the disjointness shown) uniqueness of the connecting line.

Case B: one point affine $(r,c)$, one at infinity. If the infinity point is $\infty_{\text{row}}$: the unique line is $R_r$ (any other line containing $(r,c)$ is a $C_c$-type or $D_{k,s}$-type line, neither of which contains $\infty_{\text{row}}$ by construction). Similarly for $\infty_{\text{col}}$ (unique line $C_c$) and $\infty_k$ (unique line $D_{k, L_k(r,c)}$). Case C: both points at infinity: both lie only on $\ell_\infty$ (no affine-type line contains two points at infinity, by construction each row/column/diagonal line contains exactly one infinity point), so $\ell_\infty$ is the unique common line. Verify axiom 2 (two lines meet in a unique point), by duality of the construction. Two row-lines $R_r \ne R_{r'}$ meet only at $\infty_{\text{row}}$ (their affine parts are disjoint by definition, sharing no $(r,c)$ since $r\ne r'$). A row-line $R_r$ and column-line $C_c$ meet only at the single affine point $(r,c)$ (and not at infinity, since $\infty_{\text{row}}\ne \infty_{\text{col}}$), by definition of these sets. A row-line $R_r$ and a diagonal line $D_{k,s}$ meet at the unique affine point with row $r$ and $L_k$-value $s$ — unique since $L_k$ is Latin (symbol $s$ appears exactly once in row $r$) — and not at infinity since $\infty_{\text{row}} \ne \infty_k$. Symmetric argument for $C_c, D_{k,s}$. Two diagonal lines $D_{k,s}, D_{k',s'}$ with $k\ne k'$ meet at the unique affine point where $L_k=s, L_{k'}=s'$ simultaneously — existence and uniqueness both guaranteed by orthogonality of $L_k, L_{k'}$ — and not at infinity ($\infty_k\ne \infty_{k'}$). Two diagonal lines with the same $k$ but $s \ne s'$ share no affine point (Latin square: a cell can't have two different symbol values for the same $L_k$) and meet only at $\infty_k$. Finally, any of the $n^2+n$ non-$\ell_\infty$ lines meets $\ell_\infty$ in exactly its one infinity point, by construction. Verify axiom 3. Take the four points $(1,1), (1,2), (2,1), (2,2)$ (using $n \geq 2$ so these are $4$ distinct valid coordinates). No three are collinear: any two of them lying on a common row-line forces equal first coordinates, which fails for e.g. $(1,1),(2,1),(1,2)$ having only $(1,1),(1,2)$ sharing a row and $(1,1),(2,1)$ sharing a column — so no line among $R_r, C_c$ contains three of these four points (each such line, being determined by one shared coordinate, contains at most $2$ of our four points, since the four points use only $2$ distinct row-values and $2$ distinct column-values). For diagonal lines $D_{k,s}$: such a line contains three of our four points only if three of $L_k(1,1), L_k(1,2), L_k(2,1), L_k(2,2)$ coincide; but $L_k(1,1) \ne L_k(1,2)$ (Latin, same row) and $L_k(1,1)\ne L_k(2,1)$ (Latin, same column), so at most a coincidence like $L_k(1,1)=L_k(2,2)$ or $L_k(1,2)=L_k(2,1)$ is possible, never three equal among four values where two pairs are already forced unequal by row/column constraints — concretely, of the four values, $L_k(1,1),L_k(1,2)$ differ, and $L_k(1,1),L_k(2,1)$ differ, and $L_k(1,2),L_k(2,2)$ differ (same column $2$), and $L_k(2,1),L_k(2,2)$ differ (same row $2$); so any three of the four values include at least one differing pair from these four "row/column-forced-distinct" pairs, hence cannot all be equal. So no $D_{k,s}$ contains three of our four points. Hence no three of $(1,1),(1,2),(2,1),(2,2)$ are collinear, verifying axiom 3. By the Fundamental Parameter Theorem, this incidence structure, having lines of size exactly $n+1$ (row/column/diagonal lines all constructed with $n+1$ points, and $\ell_\infty$ with $n+1$ points), is a projective plane of order $n$. $\blacksquare$