40.06.03 · combinatorics / design-coding-theory

Finite Projective and Affine Planes, MOLS, and the 36-Officers Problem

shipped3 tiersLean: none

Anchor (Master): van Lint-Wilson 2001 *A Course in Combinatorics* 2e Ch. 19, 22 & 17 (Desarguesian planes $\mathrm{PG}(2,q)$ from $\mathbb{F}_q^3$, the MOLS-plane equivalence, the field construction of $q-1$ MOLS, Euler's conjecture and the Bose-Shrikhande-Parker disproof, Bruck-Ryser on plane orders); Hughes-Piper 1973 *Projective Planes* (Springer); Euler 1782 *Verh. Zeeuwsch Genootsch.* (the officers problem); Bose-Shrikhande-Parker 1960 *Canad. J. Math.* 12 (the disproof)

Intuition Beginner

Ordinary geometry has an annoying exception built into it: most pairs of lines cross, but parallel lines never do. Projective geometry removes the exception by adding new points "at infinity," one for each direction, where parallel lines are declared to meet. Once you do this, the rules become perfectly symmetric: any two points lie on exactly one line, and any two lines cross in exactly one point. There is no longer a special case.

A finite projective plane keeps these clean rules but uses only finitely many points. The smallest one is the Fano plane from the block-design unit: seven points, seven lines, three points on each line. Bigger ones come in a family controlled by a single number $n$ , the order. A plane of order $n$ has exactly $n^{2} + n + 1$ points, the same number of lines, and $n + 1$ points on every line. So the counting is rigid: pick the order and everything else is forced.

Stripping the line at infinity back off gives an affine plane: the everyday picture of points, lines, and genuine parallel classes, now with $n^{2}$ points arranged in a tidy grid. Affine and projective planes are two views of the same object, and both turn out to be hiding inside a puzzle about Latin squares.

Visual Beginner

A Latin square of order $n$ is an $n \times n$ grid filled with $n$ symbols so that each symbol appears once in every row and once in every column — a solved Sudoku ignoring the boxes. Two Latin squares are orthogonal when, laying one on top of the other, every one of the $n^{2}$ ordered pairs of symbols shows up exactly once. The picture below stacks two orthogonal squares of order $3$ .

   Square A         Square B        Overlay (A,B)
  1  2  3          1  2  3          11 22 33
  2  3  1          3  1  2          23 31 12
  3  1  2          2  3  1          32 13 21

Read the overlay grid. Its nine cells carry the pairs $11, 22, 33, 23, 31, 12, 32, 13, 21$ — all nine ordered pairs of ${1, 2, 3}$ , each once. That is what orthogonal means. A family of Latin squares that are pairwise orthogonal is a set of mutually orthogonal Latin squares, or MOLS. The headline fact of this unit is that a big enough MOLS family is the same thing as a finite plane.

Worked example Beginner

Let us count a projective plane of order $n = 3$ from the rules alone, then connect it to Latin squares. The rules: any two points on one line, any two lines meet once, and every line holds $n + 1 = 4$ points.

Step 1. Count lines through one point. Fix a point $P$ . Every other point joins $P$ by exactly one line, and each line through $P$ carries $n = 3$ other points. So the lines through $P$ split the rest of the plane into groups of $3$ . If there are $L$ lines through $P$ , they cover $3 L$ other points with no overlap.

Step 2. Find the total number of points. By symmetry every point sits on the same number of lines, and that number is $n + 1 = 4$ . The $4$ lines through $P$ each carry $3$ points besides $P$ , covering $4 \times 3 = 12$ other points, all distinct. Adding $P$ back: $12 + 1 = 13$ points. And $13 = 3^{2} + 3 + 1$ , matching the formula.

Step 3. Count lines. Each line has $4$ points; each point is on $4$ lines. Counting point-on-line pairs two ways gives (lines) $\times 4 =$ (points) $\times 4$ , so there are also $13$ lines.

Step 4. Connect to MOLS. An order- $3$ plane is built from $n - 1 = 2$ mutually orthogonal Latin squares of order $3$ — exactly the pair drawn in the Visual. The two squares supply the two "extra" parallel directions beyond rows and columns.

What this tells us: the order alone fixes the whole plane — $13$ points, $13$ lines, $4$ points per line — and the plane is repackaged Latin-square data.

Check your understanding Beginner

Formal definition Intermediate+

A finite projective plane is an incidence structure $(P, L, \in)$ of points $P$ and lines $L$ satisfying three axioms: (P1) any two distinct points lie on a unique common line; (P2) any two distinct lines meet in a unique common point; (P3) there exist four points no three of which are collinear (a quadrangle, ruling out degenerate cases). Axiom (P3) forces every line to carry the same number of points; that common number is $n + 1$ , and $n \geq 2$ is the order of the plane ^{[van Lint-Wilson Ch. 22]}.

Proposition (parameters). A projective plane of order $n$ has exactly $n^{2} + n + 1$ points and $n^{2} + n + 1$ lines; every line carries $n + 1$ points and every point lies on $n + 1$ lines. Fixing a point $P$ , the lines through $P$ partition the remaining $n^{2} + n$ points into classes of size $n$ (the other points on each line), so there are $n + 1$ lines through $P$ ; a flag count then gives $∣ P ∣ (n + 1) = ∣ L ∣ (n + 1)$ and the total $n^{2} + n + 1$ .

Equivalence with symmetric designs. A projective plane of order $n$ is exactly a symmetric $2 - (n^{2} + n + 1, n + 1, 1)$ design 40.06.01: points are points, lines are blocks, $v = b = n^{2} + n + 1$ , block size $k = r = n + 1$ , and the index $λ = 1$ records that two points determine a unique line. The dual symmetric-design property — two blocks meet in $λ = 1$ points — is axiom (P2).

Definition (affine plane). A finite affine plane of order $n$ is an incidence structure with: (A1) any two distinct points on a unique line; (A2) for each point $P$ off a line $ℓ$ , a unique line through $P$ disjoint from $ℓ$ (the parallel to $ℓ$ through $P$ ); (A3) a triangle (three non-collinear points) exists. Parallelism is an equivalence relation; its classes are parallel classes. An affine plane of order $n$ has $n^{2}$ points, $n^{2} + n$ lines, $n$ points per line, and $n + 1$ parallel classes of $n$ lines each.

Projective completion. Given an affine plane, adjoin one new point per parallel class (a point at infinity) lying on every line of that class, and one new line at infinity through all the new points. The result is a projective plane of order $n$ . Deleting any single line and its points from a projective plane inverts this, returning an affine plane. Projective and affine planes of order $n$ exist together or not at all.

Definition (Latin square; orthogonality). A Latin square of order $n$ on symbol set $[n] = {1, \dots, n}$ is an $n \times n$ array $L$ with $L (i, j) \in [n]$ such that each symbol occurs once per row and once per column. Two Latin squares $L, L^{'}$ of order $n$ are orthogonal if the map $(i, j) \mapsto (L (i, j), L^{'} (i, j))$ is a bijection onto $[n] \times [n]$ ; equivalently every ordered pair of symbols occurs in exactly one cell. A set ${L_{1}, \dots, L_{t}}$ of pairwise orthogonal Latin squares is a set of mutually orthogonal Latin squares (MOLS); $N (n)$ denotes the maximum size of such a set.

Counterexamples to common slips Intermediate+

Orthogonality is a condition on the pair, not on each square. Each $L_{i}$ is Latin on its own; orthogonality constrains how two squares overlay. A square is never "orthogonal" in isolation.
The order of a plane is $n$ , not the number of points on a line. A line has $n + 1$ points; the order is one less. The Fano plane has order $2$ , lines of size $3$ .
Affine $\neq =$ projective minus arbitrary deletions. You delete one whole line together with all its points to get an affine plane. Deleting a single point, or a line while keeping its points, breaks the axioms.
$N (n) = n - 1$ is the maximum, attained iff a plane exists; it is not automatic. Every prime power attains it, but $N (6) = 1$ : there is no pair of order- $6$ MOLS, so no projective plane of order $6$ .

Key theorem with proof Intermediate+

The structural heart of the unit is that the two superficially unrelated objects — a complete set of mutually orthogonal Latin squares and a finite plane — carry identical data. The bound $N (n) \leq n - 1$ falls out of the same bookkeeping.

Theorem (the MOLS bound and the plane equivalence). For $n \geq 2$ , the number of mutually orthogonal Latin squares of order $n$ satisfies $N (n) \leq n - 1$ , and $N (n) = n - 1$ if and only if a projective (equivalently affine) plane of order $n$ exists ^{[van Lint-Wilson Ch. 22]}.

Proof. For the bound, take MOLS $L_{1}, \dots, L_{t}$ and standardise: by relabelling the symbols of each $L_{m}$ (an operation preserving the Latin and orthogonality conditions), arrange that row $1$ of every $L_{m}$ reads $1, 2, \dots, n$ in order. Consider cell $(2, 1)$ , the start of row $2$ . In $L_{m}$ its entry is not $L_{m} (1, 1) = 1$ (column $1$ already holds $1$ in row $1$ ). The entries $L_{1} (2, 1), \dots, L_{t} (2, 1)$ are pairwise distinct: if $L_{m} (2, 1) = L_{m^{'}} (2, 1) = s$ for $m \neq = m^{'}$ , then the pair $(s, s)$ occurs at $(2, 1)$ and, because row $1$ is the identity, also at cell $(1, s)$ where both squares read $s$ — contradicting orthogonality. So $t$ distinct values, each in ${2, \dots, n}$ , give $t \leq n - 1$ .

For the equivalence, suppose a set of $n - 1$ MOLS $L_{1}, \dots, L_{n - 1}$ exists. Build an affine plane on the $n^{2}$ points $(i, j) \in [n] \times [n]$ . The lines are: the $n$ rows ${(i, j) : j fixed}$ , the $n$ columns ${(i, j) : i fixed}$ , and, for each square $L_{m}$ and each symbol $s \in [n]$ , the level set $ℓ_{m, s} = {(i, j) : L_{m} (i, j) = s}$ . A Latin square makes each level set a transversal — one cell per row and per column, so $n$ points; the $n$ level sets of one $L_{m}$ partition the grid into a parallel class. Two points $(i, j) \neq = (i^{'}, j^{'})$ : if they share a row or column, one of those lines joins them; otherwise $i \neq = i^{'}$ and $j \neq = j^{'}$ , and orthogonality of $L_{m}, L_{m^{'}}$ guarantees that for each ordered symbol-pair there is a unique cell, so the two points lie together on a level set of exactly one square. Thus (A1) holds. The $n + 1$ parallel classes (rows, columns, and one per square) give (A2). Conversely, an affine plane of order $n$ has $n + 1$ parallel classes; designating two as rows and columns coordinatises the points by $[n] \times [n]$ , and each remaining class defines a Latin square via $L_{m} (i, j) =$ (the class- $m$ line through $(i, j)$ ); distinctness of joining lines forces the squares mutually orthogonal. Adjoining the line at infinity converts the affine plane to a projective one. $□$

Bridge. This equivalence builds toward the entire existence theory of finite planes by reducing a geometric question to an array-filling one, and it appears again in the orthogonal-array and transversal-design reformulations of the Advanced results, where the same incidence is read as a code. The foundational reason the bound is $n - 1$ and not larger is exactly the standardisation argument: the $n - 1$ free slots in the first column of standardised squares are the $n - 1$ parallel classes beyond rows and columns. This is dual to the symmetric-design picture of 40.06.01, where the plane is the $λ = 1$ case and Fisher's equality $b = v$ is the self-duality of points and lines; putting these together, a complete set of MOLS, a symmetric $2 - (n^{2} + n + 1, n + 1, 1)$ design, and a projective plane are three encodings of one object, and the central insight is that orthogonality of two Latin squares is precisely the unique-intersection axiom (P2) read in coordinates. The bridge is that filling $n - 1$ orthogonal squares and drawing $n^{2} + n + 1$ concurrent lines are the same act.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Let $q$ be a prime power and for each nonzero $a \in F_{q}$ define $L_{a} (i, j) = a i + j$ for $i, j \in F_{q}$ . Prove each $L_{a}$ is a Latin square and that $L_{a}, L_{b}$ are orthogonal for $a \neq = b$ .

Hint

Latin: fix $i$ and vary $j$ ; fix $j$ and vary $i$ . Orthogonal: solve the system $ai + j = s$ , $bi + j = t$ for $(i, j)$ and show it has a unique solution when $a \neq = b$ .

Answer

Fix a row $i$ . As $j$ ranges over $F_{q}$ , $L_{a} (i, j) = ai + j$ takes each field value once (it is a translation of $j$ ), so every symbol appears once per row. Fix a column $j$ . As $i$ ranges over $F_{q}$ , $ai + j$ takes each value once because $a \neq = 0$ makes $i \mapsto ai$ a bijection; so every symbol appears once per column. Hence $L_{a}$ is Latin. For orthogonality with $a \neq = b$ , given target symbols $(s, t)$ solve $ai + j = s$ and $bi + j = t$ . Subtracting, $(a - b) i = s - t$ , and $a - b \neq = 0$ gives a unique $i = (s - t) / (a - b)$ , then $j = s - ai$ . So each pair $(s, t)$ arises from exactly one cell $(i, j)$ : the squares are orthogonal. The $q - 1$ squares ${L_{a} : a \neq = 0}$ form a complete MOLS set. Rubric: full credit for the row/column bijections and the unique-solution argument using $a \neq = b$ .

Exercise 7 (hard, symbolic).

Prove the Bruck-Ryser necessary condition's hypothesis applies to planes: show that a projective plane of order $n$ with $n \equiv 1$ or $2 (mod 4)$ requires $n$ to be a sum of two integer squares. You may invoke the symmetric-design incidence identity and the Hasse-Minkowski theorem for rational quadratic forms.

Hint

A plane is a symmetric $2 - (v, n + 1, 1)$ design with $v = n^{2} + n + 1$ odd. Apply the Bruck-Ryser-Chowla theorem with $k - λ = n$ to the odd- $v$ case.

Answer

A projective plane of order $n$ is a symmetric design with $v = n^{2} + n + 1$ , $k = n + 1$ , $λ = 1$ , so $k - λ = n$ . Here $v$ is always odd. The Bruck-Ryser-Chowla theorem for symmetric designs with $v$ odd asserts that the Diophantine equation $z^{2} = (k - λ) x^{2} + (- 1)^{(v - 1) /2} λ y^{2}$ has a nontrivial integer solution; with $k - λ = n$ , $λ = 1$ , this is $z^{2} = n x^{2} + (- 1)^{(v - 1) /2} y^{2}$ . Compute the sign: $(v - 1) /2 = (n^{2} + n) /2 = n (n + 1) /2$ . When $n \equiv 1 (mod 4)$ , $n (n + 1) /2$ is odd, giving $z^{2} = n x^{2} - y^{2}$ , i.e. $z^{2} + y^{2} = n x^{2}$ ; when $n \equiv 2 (mod 4)$ , $n (n + 1) /2$ is also odd, the same form. The solvability of $z^{2} + y^{2} = n x^{2}$ over $Q$ , by Hasse-Minkowski and the two-squares theorem, forces $n$ to be a sum of two integer squares. Hence orders $6, 14, 21, 22$ — none of which is a sum of two squares — are excluded. Rubric: full credit for identifying $k - λ = n$ , computing the parity of $n (n + 1) /2$ , and reducing to $z^{2} + y^{2} = n x^{2}$ .

Exercise 8 (hard, symbolic).

Prove that a set of $t$ MOLS of order $n$ is equivalent to a transversal design $TD (t + 2, n)$ : a set of $(t + 2) n$ points partitioned into $t + 2$ groups of size $n$ , with blocks of size $t + 2$ meeting each group once, such that every pair of points from different groups lies in exactly one block.

Hint

Take groups indexed by rows, columns, and the $t$ squares. A cell $(i, j)$ gives a block ${$ row $i$ , column $j$ , $L_{1} (i, j), \dots, L_{t} (i, j)}$ . Check the pairwise-coverage condition against the Latin and orthogonality axioms.

Answer

Form $t + 2$ groups $G_{0}, \dots, G_{t + 1}$ , each a copy of $[n]$ : $G_{0}$ for rows, $G_{1}$ for columns, and $G_{2}, \dots, G_{t + 1}$ for the symbol sets of $L_{1}, \dots, L_{t}$ . For each cell $(i, j)$ create the block $B_{ij} = {i_{G_{0}}, j_{G_{1}}, L_{1} (i, j)_{G_{2}}, \dots, L_{t} (i, j)_{G_{t + 1}}}$ , of size $t + 2$ , meeting each group once. There are $n^{2}$ blocks. A pair of points from $G_{0}, G_{1}$ (a row $i$ and column $j$ ) lies in the unique block $B_{ij}$ . A pair from $G_{0}$ (row $i$ ) and $G_{m + 2}$ (symbol $s$ of $L_{m}$ ) lies in the blocks $B_{ij}$ with $L_{m} (i, j) = s$ ; since $L_{m}$ is Latin, exactly one $j$ in row $i$ has $L_{m} (i, j) = s$ , so exactly one block. A pair from $G_{m + 2}$ (symbol $s$ ) and $G_{m^{'} + 2}$ (symbol $s^{'}$ ), $m \neq = m^{'}$ , lies in blocks $B_{ij}$ with $L_{m} (i, j) = s$ and $L_{m^{'}} (i, j) = s^{'}$ ; orthogonality of $L_{m}, L_{m^{'}}$ gives exactly one cell $(i, j)$ , hence one block. Every cross-group pair is covered once: a $TD (t + 2, n)$ . Reversing — coordinatise two groups as rows/columns and read off each further group as a square — recovers $t$ MOLS, and the cross-group coverage is exactly the Latin and orthogonality conditions. Rubric: full credit for the block construction, all three pair cases, and the reverse direction.

Advanced results Master

The MOLS-plane equivalence organises the deeper theory: the field construction supplies planes at every prime power, the Bruck-Ryser theorem and the order- $10$ computation supply nonexistence, the orthogonal-array and transversal-design languages translate the question into coding and combinatorial-design terms, and Euler's conjecture together with its disproof maps the small-order landscape.

Theorem 1 (Desarguesian planes from $F_{q}^{3}$ ). For a prime power $q$ , the projective plane $PG (2, q)$ has as points the one-dimensional subspaces of $F_{q}^{3}$ and as lines the two-dimensional subspaces, with incidence given by containment. It has $q^{2} + q + 1$ points and lines, order $n = q$ , and is Desarguesian (Desargues' theorem holds, equivalently it is coordinatised by the field $F_{q}$ ). The number of $1$ - and $2$ -dimensional subspaces is the Gaussian binomial $(1 3)_{q} = (2 3)_{q} = q^{2} + q + 1$ , tying the count to the $q$ -analogue subspace enumeration 40.01.06. Every known finite projective plane has prime-power order ^{[Hughes-Piper]}.

Theorem 2 (field MOLS and completeness). For $q$ a prime power, ${L_{a} : a \in F_{q}^{\times}}$ with $L_{a} (i, j) = ai + j$ is a complete set of $q - 1$ MOLS, so $N (q) = q - 1$ , and the associated affine plane is $AG (2, q)$ , the projective completion $PG (2, q)$ . Thus planes — equivalently complete MOLS sets — exist for every prime power. No construction is known at any non-prime-power order, and the smallest undecided order is $n = 12$ ^{[Stinson Ch. 6]}.

Theorem 3 (Bruck-Ryser and the order-10 verdict). If $n \equiv 1$ or $2 (mod 4)$ , a projective plane of order $n$ exists only if $n$ is a sum of two integer squares ^{[Bruck-Ryser 1949]}. This excludes orders $6, 14, 21, 22, 30, 33, 38, \dots$ . The bound is silent on $n = 10$ (which is $1 + 9$ , a sum of two squares) and $n = 12$ . Order $10$ was settled negatively by Lam, Thiel, and Swiercz (1989) through a CDC supercomputer search ruling out the requisite codewords of the hypothetical plane's incidence code — the first plane order excluded by computation rather than by the arithmetic criterion. Order $12$ remains open.

Theorem 4 (orthogonal arrays). A set of $t$ MOLS of order $n$ is equivalent to an orthogonal array $OA (t + 2, n)$ : an $(t + 2) \times n^{2}$ array over $[n]$ such that every $2 \times n^{2}$ subarray contains each ordered pair from $[n]^{2}$ exactly once (strength $2$ , index $1$ ). The rows index rows, columns, and the $t$ squares; the columns index the $n^{2}$ cells. Completeness $t = n - 1$ gives $OA (n + 1, n)$ , equivalent to the plane and to the transversal design $TD (n + 1, n)$ . The orthogonal array is the bridge to coding theory: an $OA$ of strength $2$ and index $1$ is an MDS-like code, linking planes to the Singleton-bound family of 40.06.06.

Theorem 5 (Euler's conjecture and its disproof). Euler (1782) conjectured that no pair of orthogonal Latin squares of order $n$ exists when $n \equiv 2 (mod 4)$ — orders $2, 6, 10, 14, \dots$ ^{[Euler 1782]}. Order $2$ ( $N (2) = 1$ ) and order $6$ ( $N (6) = 1$ , Tarry 1900) confirm the conjecture there. But Bose, Shrikhande, and Parker (1960) constructed orthogonal Latin squares for every other order $n \equiv 2 (mod 4)$ , starting with $n = 10, 14, 18, 22$ , proving $N (n) \geq 2$ for all $n \neq = 2, 6$ ^{[Bose-Shrikhande-Parker 1960]}. The conjecture is false except at the two genuine exceptions. The construction uses pairwise balanced designs and the MacNeish-type product bound $N (mn) \geq min (N (m), N (n))$ refined by group-divisible designs.

Theorem 6 (MacNeish and growth of $N (n)$ ). Writing $n = \prod p_{i}^{a_{i}}$ , MacNeish's theorem gives $N (n) \geq min_{i} (p_{i}^{a_{i}} - 1)$ , so $N (n) \geq 2$ whenever $n$ is not $\equiv 2 (mod 4)$ , and the Bose-Shrikhande-Parker result extends $N (n) \geq 2$ to all $n \geq 3$ except $6$ . Asymptotically $N (n) \to \infty$ ; Wilson (1974) showed $N (n) \geq n^{1/17}$ for large $n$ , later improved to $N (n) \geq n^{1/14.8}$ and beyond. The exact value $N (n) = n - 1$ holds iff a projective plane of order $n$ exists, so the gap between $N (n)$ and $n - 1$ at non-prime-powers measures how far planes fail to exist.

Synthesis. Putting these together, the foundational reason finite geometry, Latin squares, designs, and codes form one subject is that a projective plane of order $n$ , a complete set of $n - 1$ MOLS, a symmetric $2 - (n^{2} + n + 1, n + 1, 1)$ design, an $OA (n + 1, n)$ , and a transversal design $TD (n + 1, n)$ are literally the same datum read five ways. This is exactly the $λ = 1$ apex of the symmetric-design theory of 40.06.01: Fisher's equality $b = v$ is the point-line self-duality, and the central insight is that orthogonality of Latin squares is the unique-intersection axiom in coordinates. The field construction $PG (2, q)$ generalises the small examples to every prime power, and the $q$ -analogue count $(1 3)_{q} = q^{2} + q + 1$ of 40.01.06 is dual to the axiomatic count from the plane axioms — the subspace lattice of $F_{q}^{3}$ and the incidence structure are the same object. The bridge from existence to nonexistence is the Bruck-Ryser arithmetic and the computational exclusion of order $10$ , which together show the prime-power orders are not known to be the only ones yet are the only ones realised, leaving the prime-power conjecture — that every plane order is a prime power — as the governing open problem the whole apparatus circles.

Full proof set Master

Proposition 1 (parameters of a projective plane). A projective plane of order $n$ has $n^{2} + n + 1$ points and lines, with $n + 1$ points per line and $n + 1$ lines per point.

Proof. By (P3) fix a quadrangle; one shows every line has the same number of points, call it $n + 1$ . Fix a point $P$ . Each other point $Q$ determines, by (P1), a unique line $P Q$ through $P$ ; conversely each line through $P$ carries $n$ points besides $P$ . The lines through $P$ thus partition $P ∖ {P}$ into classes of size $n$ . Let $d$ be the number of lines through $P$ ; then $∣ P ∣ - 1 = d n$ . To find $d$ , take a line $ℓ$ not through $P$ (one exists by (P3)); by (P2) each line through $P$ meets $ℓ$ in one point, and by (P1) each of the $n + 1$ points of $ℓ$ joins $P$ by one line, a bijection, so $d = n + 1$ . Hence $∣ P ∣ = 1 + (n + 1) n = n^{2} + n + 1$ . Dualising (swapping points and lines, which preserves the axioms) gives the same count of lines and $n + 1$ points per line. $□$

Proposition 2 (plane $\Leftrightarrow$ symmetric $2$ -design). Projective planes of order $n$ are exactly the symmetric $2 - (n^{2} + n + 1, n + 1, 1)$ designs.

Proof. Given a plane, take points as points and lines as blocks. By Proposition 1, $v = b = n^{2} + n + 1$ , every block (line) has $k = n + 1$ points, every point is on $r = n + 1$ blocks, and by (P1) every pair of points lies on exactly $λ = 1$ line: a symmetric $2 - (n^{2} + n + 1, n + 1, 1)$ design. Conversely, in such a design $λ = 1$ gives (P1); the symmetric dual property that two blocks meet in $λ = 1$ points [40.06.01, Prop. 4] gives (P2); and $v = n^{2} + n + 1 >$ any degenerate configuration forces a quadrangle, giving (P3). The order is recovered from $k = n + 1$ . $□$

Proposition 3 (affine completion and decompletion). Adjoining a line at infinity to an affine plane of order $n$ yields a projective plane of order $n$ ; deleting a line and its points from a projective plane yields an affine plane of order $n$ .

Proof. In an affine plane parallelism is an equivalence relation: reflexive and symmetric by definition, and transitive because if $ℓ_{1} ∥ ℓ_{2}$ and $ℓ_{2} ∥ ℓ_{3}$ but $ℓ_{1} \cap ℓ_{3} = {X}$ , then through $X$ run two lines ( $ℓ_{1}, ℓ_{3}$ ) parallel to $ℓ_{2}$ , violating (A2). The $n + 1$ parallel classes each get a new point at infinity, placed on every line of the class and on the new line $ℓ_{\infty}$ . Two old parallel lines now meet at their shared infinity point; two non-parallel old lines still meet at their finite point; any old line meets $ℓ_{\infty}$ at its class's infinity point; two infinity points meet on $ℓ_{\infty}$ . So (P2) holds, (P1) is inherited with infinity points joined along $ℓ_{\infty}$ , and the point count becomes $n^{2} + (n + 1) = n^{2} + n + 1$ . For the reverse, deleting a line $ℓ_{\infty}$ and its $n + 1$ points from a projective plane leaves $n^{2}$ points; two remaining lines that met only on $ℓ_{\infty}$ are now disjoint (parallel), and (A2) follows from (P2) applied before deletion. $□$

Proposition 4 ( $N (n) \leq n - 1$ ). At most $n - 1$ Latin squares of order $n$ are mutually orthogonal.

Proof. Standardise $L_{1}, \dots, L_{t}$ so each has first row $1, 2, \dots, n$ (relabel symbols of each square independently; this preserves both properties). The entries $L_{1} (2, 1), \dots, L_{t} (2, 1)$ lie in ${2, \dots, n}$ : each is $\neq = 1$ since column $1$ already shows $1$ at $(1, 1)$ . They are pairwise distinct: if $L_{m} (2, 1) = L_{m^{'}} (2, 1) = s$ with $m \neq = m^{'}$ , the overlaid pair $(s, s)$ occurs at $(2, 1)$ ; but with first row the identity, cell $(1, s)$ has $L_{m} (1, s) = L_{m^{'}} (1, s) = s$ , so $(s, s)$ also occurs at $(1, s)$ , contradicting orthogonality. Hence $t$ distinct values in an $(n - 1)$ -element set, so $t \leq n - 1$ . $□$

Proposition 5 (complete MOLS $\Leftrightarrow$ plane). A set of $n - 1$ MOLS of order $n$ exists iff an affine (equivalently projective) plane of order $n$ exists.

Proof. ( $\Rightarrow$ ) Given $L_{1}, \dots, L_{n - 1}$ , take points $[n] \times [n]$ and lines: $n$ rows, $n$ columns, and for each $m$ and symbol $s$ the level set $ℓ_{m, s} = {(i, j) : L_{m} (i, j) = s}$ . Each $ℓ_{m, s}$ has $n$ points (one per row, since $L_{m}$ is Latin), and the level sets of a fixed $m$ partition the grid (a parallel class). Two distinct points sharing a coordinate are joined by a row or column; two points $(i, j), (i^{'}, j^{'})$ with $i \neq = i^{'}$ , $j \neq = j^{'}$ are joined by exactly one level set, because for the pair $(L_{m} (i, j), L_{m} (i^{'}, j^{'}))$ to coincide as a single symbol $s$ requires $L_{m}$ to repeat $s$ — impossible unless they lie on one level set, and orthogonality across the family ensures exactly one $m$ places them together. Counting parallel classes: $2 + (n - 1) = n + 1$ , giving (A2). ( $\Leftarrow$ ) An affine plane has $n + 1$ parallel classes; pick two as the row and column classes, coordinatising points by $[n] \times [n]$ . Each other class $m$ defines $L_{m} (i, j) =$ the index within class $m$ of the line through $(i, j)$ . Each $L_{m}$ is Latin (each class line meets each row and column once), and distinct classes give orthogonal squares because two points lie on a unique non-row/column line, forcing each symbol pair once. Adjoining $ℓ_{\infty}$ (Proposition 3) gives the projective plane. $□$

Proposition 6 (field construction). For a prime power $q$ the squares $L_{a} (i, j) = ai + j$ , $a \in F_{q}^{\times}$ , are $q - 1$ MOLS, so $N (q) = q - 1$ .

Proof. Each $L_{a}$ is Latin: fixing $i$ , $j \mapsto ai + j$ is a bijection of $F_{q}$ (translation); fixing $j$ , $i \mapsto ai + j$ is a bijection since $a \neq = 0$ . For $a \neq = b$ , the system $ai + j = s$ , $bi + j = t$ subtracts to $(a - b) i = s - t$ with unique $i = (s - t) (a - b)^{- 1}$ and then $j = s - ai$ , so $(i, j) \mapsto (L_{a}, L_{b})$ is a bijection onto $F_{q}^{2}$ : orthogonal. There are $q - 1$ choices of $a \neq = 0$ , attaining the bound of Proposition 4. $□$

Connections Master

The symmetric-design unit 40.06.01 is where this material's algebraic backbone lives: a projective plane of order $n$ is exactly the $λ = 1$ symmetric $2 - (n^{2} + n + 1, n + 1, 1)$ design, Fisher's equality $b = v$ is the point-line duality, and the incidence identity $N N^{⊤} = n I + J$ proved there is the matrix form of axioms (P1)-(P2). The foundational reason plane existence is constrained is the same eigenvalue computation that drives Fisher's inequality, specialised to $r = k = n + 1$ , $λ = 1$ .
The Bruck-Ryser-Chowla unit 40.06.02 supplies the arithmetic nonexistence test: for $n \equiv 1, 2 (mod 4)$ a plane of order $n$ forces $n$ to be a sum of two squares, the Hasse-Minkowski reading of the symmetric-design quadratic form at the plane parameters. This unit supplies the geometric object and its design parameters; 40.06.02 reads the form $p$ -adically to exclude orders $6, 14, 21, 22, \dots$ . The unit 40.06.04 on Steiner systems is the broader $λ = 1$ context — a projective plane is a Steiner system $S (2, n + 1, n^{2} + n + 1)$ — so the plane sits inside the Steiner-triple-and-beyond family there.
The $q$ -analogue and Gaussian-binomial unit 40.01.06 counts the Desarguesian plane: the points and lines of $PG (2, q)$ are the $1$ - and $2$ -dimensional subspaces of $F_{q}^{3}$ , enumerated by $(1 3)_{q} = (2 3)_{q} = q^{2} + q + 1$ . The subspace lattice of $F_{q}^{3}$ and the plane's incidence structure are the same object, so the $q$ -binomial subspace count and the axiomatic point count are dual derivations of $n^{2} + n + 1$ .
The finite-field unit 21.02.01 is the engine of all known planes: the field $F_{q}$ supplies both the coordinates of $PG (2, q)$ and the complete MOLS set $L_{a} (i, j) = ai + j$ , whose orthogonality rests entirely on $a - b$ being invertible for $a \neq = b$ . This is dual to the Hadamard/Paley construction of 40.06.05, where the same field structure — there its quadratic-residue character — manufactures a different family of combinatorial designs, placing planes and Hadamard designs as two field-built corners of the design-coding landscape.

Historical & philosophical context Master

Finite projective planes grew from two roots: the synthetic projective geometry of the nineteenth century, where points at infinity regularised the meeting of parallels, and the combinatorial puzzles of magic and Latin squares. Leonhard Euler studied the latter in 1782 ^{[Euler 1782]}, posing the 36-officers problem — arrange six officers from each of six ranks and six regiments in a $6 \times 6$ square with no rank and no regiment repeated in any row or column — which asks precisely for a pair of orthogonal Latin squares of order $6$ . Euler conjectured impossibility for every order $n \equiv 2 (mod 4)$ . Gaston Tarry confirmed the order- $6$ case in 1900 by an exhaustive enumeration, but the general conjecture stood until Raj Chandra Bose, Sharadchandra Shrikhande, and Ernest Parker demolished it in 1960 ^{[Bose-Shrikhande-Parker 1960]}, constructing orthogonal squares for every order $n \equiv 2 (mod 4)$ beyond $6$ ; the three became known as "Euler's spoilers."

The bridge to geometry was the recognition that a complete set of $n - 1$ MOLS coordinatises a plane, made systematic by Bose and developed in the axiomatic theory of Marshall Hall and of Daniel Hughes and Frederick Piper ^{[Hughes-Piper]}. The arithmetic obstruction came from Richard Bruck and Herbert Ryser in 1949 ^{[Bruck-Ryser 1949]}, who applied the Hasse-Minkowski theory of rational quadratic forms to the incidence equation, excluding orders such as $6$ and $14$ . The criterion is silent on order $10$ ; that case fell only in 1989, when Clement Lam, Larry Thiel, and Stanley Swiercz proved nonexistence by an extensive computer search over the codewords of the hypothetical incidence matrix, the first plane order decided by machine. Order $12$ remains undecided, and whether every finite projective plane has prime-power order is open.

Bibliography Master

@article{euler1782quarres,
  author  = {Euler, Leonhard},
  title   = {Recherches sur une nouvelle esp\`{e}ce de quarr\'{e}s magiques},
  journal = {Verhandelingen uitgegeven door het Zeeuwsch Genootschap der Wetenschappen te Vlissingen},
  volume  = {9},
  pages   = {85--239},
  year    = {1782}
}

@article{tarry1900probleme,
  author  = {Tarry, Gaston},
  title   = {Le probl\`{e}me des 36 officiers},
  journal = {Comptes Rendus de l'Association Fran\c{c}aise pour l'Avancement des Sciences},
  volume  = {29},
  pages   = {170--203},
  year    = {1900}
}

@article{bruckryser1949nonexistence,
  author  = {Bruck, Richard H. and Ryser, Herbert J.},
  title   = {The nonexistence of certain finite projective planes},
  journal = {Canadian Journal of Mathematics},
  volume  = {1},
  pages   = {88--93},
  year    = {1949}
}

@article{boseshrikhandeparker1960euler,
  author  = {Bose, Raj Chandra and Shrikhande, Sharadchandra S. and Parker, Ernest T.},
  title   = {Further results on the construction of mutually orthogonal {Latin} squares and the falsity of {Euler's} conjecture},
  journal = {Canadian Journal of Mathematics},
  volume  = {12},
  pages   = {189--203},
  year    = {1960}
}

@article{lamthielswiercz1989projective,
  author  = {Lam, Clement W. H. and Thiel, Larry and Swiercz, Stanley},
  title   = {The non-existence of finite projective planes of order 10},
  journal = {Canadian Journal of Mathematics},
  volume  = {41},
  pages   = {1117--1123},
  year    = {1989}
}

@article{wilson1974concerning,
  author  = {Wilson, Richard M.},
  title   = {Concerning the number of mutually orthogonal {Latin} squares},
  journal = {Discrete Mathematics},
  volume  = {9},
  pages   = {181--198},
  year    = {1974}
}

@book{hughespiper1973projective,
  author    = {Hughes, Daniel R. and Piper, Frederick C.},
  title     = {Projective Planes},
  series    = {Graduate Texts in Mathematics},
  volume    = {6},
  publisher = {Springer},
  year      = {1973}
}

@book{vanlintwilson2001course,
  author    = {van Lint, J. H. and Wilson, R. M.},
  title     = {A Course in Combinatorics},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2001}
}

@book{stinson2004combinatorial,
  author    = {Stinson, Douglas R.},
  title     = {Combinatorial Designs: Constructions and Analysis},
  publisher = {Springer},
  year      = {2004}
}

Prerequisites

40.06.01

Tier anchors

beginner: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 19 & 22 (finite projective planes by hand: points, lines, every two points on a line, every two lines meeting; the Fano plane and the order-3 plane; Latin squares and the officers puzzle); Euler's 36-officers problem as the motivating story
intermediate: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 19 & 22 (projective planes of order $n$ as symmetric $2\text{-}(n^2+n+1, n+1, 1)$ designs, affine planes and projective completion, mutually orthogonal Latin squares, the bound $N(n) \le n-1$, the equivalence between a complete set of MOLS and a plane); Stinson 2004 *Combinatorial Designs* (Springer) Ch. 6
master: van Lint-Wilson 2001 *A Course in Combinatorics* 2e Ch. 19, 22 & 17 (Desarguesian planes $\mathrm{PG}(2,q)$ from $\mathbb{F}_q^3$, the MOLS-plane equivalence, the field construction of $q-1$ MOLS, Euler's conjecture and the Bose-Shrikhande-Parker disproof, Bruck-Ryser on plane orders); Hughes-Piper 1973 *Projective Planes* (Springer); Euler 1782 *Verh. Zeeuwsch Genootsch.* (the officers problem); Bose-Shrikhande-Parker 1960 *Canad. J. Math.* 12 (the disproof)

References

van Lint, J. H. & Wilson, R. M. — A Course in Combinatorics · Cambridge University Press, 2nd edition (2001). Chapter 19 treats symmetric 2-designs and identifies projective planes of order $n$ as symmetric $2\text{-}(n^2+n+1, n+1, 1)$ designs; Chapter 22 develops finite geometry directly: the axioms for a projective plane, the count of $n^2+n+1$ points and lines with $n+1$ points per line and $n+1$ lines per point, affine planes of order $n$ with $n^2$ points and $n^2+n$ lines, the projective completion adding a line at infinity, Latin squares and mutually orthogonal Latin squares, the bound $N(n) \le n-1$, the equivalence between a complete set of $n-1$ MOLS and a projective (equivalently affine) plane of order $n$, the field construction over $\mathbb{F}_q$, Euler's 36-officers problem, and the Bose-Shrikhande-Parker disproof of Euler's conjecture.
Euler, L. — Recherches sur une nouvelle espèce de quarrés magiques · Verhandelingen uitgegeven door het Zeeuwsch Genootschap der Wetenschappen te Vlissingen 9 (1782), 85-239. Euler's study of Graeco-Latin squares: the impossibility of arranging 36 officers of six ranks and six regiments in a 6×6 square so that each row and column contains one officer of each rank and each regiment, and his conjecture that no pair of orthogonal Latin squares exists for any order $n \equiv 2 \pmod 4$.
Bose, R. C., Shrikhande, S. S. & Parker, E. T. — Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler's conjecture · Canadian Journal of Mathematics 12 (1960), 189-203. The proof that a pair of mutually orthogonal Latin squares of order $n$ exists for every $n$ except $n = 2$ and $n = 6$, disproving Euler's conjecture for all $n \equiv 2 \pmod 4$ with $n > 6$ and establishing $N(n) \ge 2$ for all $n \ne 2, 6$.
Bruck, R. H. & Ryser, H. J. — The nonexistence of certain finite projective planes · Canadian Journal of Mathematics 1 (1949), 88-93. The theorem that for $n \equiv 1$ or $2 \pmod 4$ a projective plane of order $n$ can exist only if $n$ is a sum of two integer squares, obtained by applying the Hasse-Minkowski theory of rational quadratic forms to the incidence equation of the symmetric design; rules out orders 6, 14, 21, 22, ...
Hughes, D. R. & Piper, F. C. — Projective Planes · Springer Graduate Texts in Mathematics 6 (1973). The axiomatic and algebraic theory of finite projective planes: the order, the Desarguesian planes $\mathrm{PG}(2,q)$ from a three-dimensional vector space over $\mathbb{F}_q$, coordinatisation by ternary rings, collineation groups, and the equivalence of planes with complete sets of mutually orthogonal Latin squares.
Stinson, D. R. — Combinatorial Designs: Constructions and Analysis · Springer (2004). Chapter 6 develops Latin squares and mutually orthogonal Latin squares: the definition of orthogonality, the bound $N(n) \le n-1$, the prime-power field construction giving $n-1$ MOLS, transversal designs and the equivalence with nets and planes, and MacNeish's product bound $N(mn) \ge \min(N(m), N(n))$.

Estimated time

beginner: 18m
intermediate: 45m
master: 85m