Block Designs and Finite Projective Planes

Fix a point $p\in P$, and let $r_p$ be the number of blocks containing $p$. Count the ordered pairs $(q,B)$ with $q\in P\setminus \{p\}$ and $\{p,q\}\subseteq B$.

Counting by blocks through $p$, each such block contributes $k-1$ choices of $q$, so the number of pairs is $r_p(k-1)$.

Counting by the second point, each $q\in P\setminus \{p\}$ contributes exactly $\lambda$ blocks, so the number of pairs is $\lambda (v-1)$.

Therefore $r_p(k-1)=\lambda (v-1)$, so $r_p=\lambda (v-1)\mathrm{/}(k-1)$ depends only on $v$, $k$, and $\lambda$, not on $p$. Thus every point lies in the same number $r$ of blocks.

Let $b:=\mathrm{\mid }\mathcal{B}\mathrm{\mid }$, and let $r$ be the common number of blocks through a point from [L1].

Count the incident pairs $(p,B)$ with $p\in B$. Each block contributes $k$ such pairs, so the total is $bk$; each of the $v$ points contributes $r$ such pairs, so the total is also $vr$. Hence $bk=vr$.

Fix a point $p\in P$ and count the ordered pairs $(q,B)$ with $q\in P\setminus \{p\}$ and $\{p,q\}\subseteq B$. By [L2], each of the $r$ blocks through $p$ contributes $k-1$ choices of $q$, while each of the $v-1$ other points contributes exactly $\lambda$ blocks. Therefore $r(k-1)=\lambda (v-1)$.

Solving the second identity of [L1] gives $r=\lambda (v-1)\mathrm{/}(k-1)$, so $k-1$ divides $\lambda (v-1)$.

Substituting step 1.1 into the first identity of [L1] gives $b=v\lambda (v-1)\mathrm{/}(k(k-1))$, so $k(k-1)$ divides $v\lambda (v-1)$.

The $(p,p)$ entry of $N{N}^{\mathsf{T}}$ counts the blocks containing $p$, so every diagonal entry is $r$ by [L1].

If $p\mathrm{\ne }q$, then the $(p,q)$ entry of $N{N}^{\mathsf{T}}$ counts the blocks containing both $p$ and $q$, so every off-diagonal entry is $\lambda$ by [L2].

The matrix on the right has diagonal entries $(r-\lambda )+\lambda =r$ and off-diagonal entries $\lambda$, so steps 1.1 and 1.2 identify it with $N{N}^{\mathsf{T}}$.

From [L2] one gets $r-\lambda =\lambda (v-k)\mathrm{/}(k-1)>0$, because $\lambda \ge 1$ and $v>k$.

If $x\in {\mathbb{R}}^v$ is nonzero, then [L1] gives $x^{\mathsf{T}}N{N}^{\mathsf{T}}x=(r-\lambda ){\sum }_i{x}_i^2+\lambda ({\sum }_i{x}_i{)}^2>0$ by step 1.1. Therefore no nonzero vector satisfies $x^{\mathsf{T}}N=0$.

So the $v$ rows of $N$ are linearly independent in ${\mathbb{R}}^b$. A family of $v$ linearly independent vectors in ${\mathbb{R}}^b$ requires $v\le b$.

Symmetry gives $b=v$, so the first identity in [L1] yields $r=k$.

Using step 1.1 in the second identity of [L1], one gets $k(k-1)=\lambda (v-1)$, so $k-\lambda =k(v-k)\mathrm{/}(v-1)>0$ because $k<v$.

If $x^{\mathsf{T}}N=0$, then $x^{\mathsf{T}}N{N}^{\mathsf{T}}x=0$, but [L2] and step 2.1 give $x^{\mathsf{T}}N{N}^{\mathsf{T}}x=(k-\lambda ){\sum }_i{x}_i^2+\lambda ({\sum }_i{x}_i{)}^2$, which is positive for every nonzero $x$. Hence $N$ is invertible.

Every row and every column of $N$ has sum $k$: rows because each point lies in $r=k$ blocks by step 1.1, and columns because every block has size $k$. Therefore $N{J}_v=J_{v}N=k{J}_v$, so step 3.1 gives $N^{-1}{J}_{v}N=J_v$.

Multiplying the identity of [L2] on the left by $N^{-1}$ and on the right by $N$ gives $N^{\mathsf{T}}N=(k-\lambda )I_v+\lambda J_v$.

The $(B,C)$ entry of $N^{\mathsf{T}}N$ counts the points in $B\cap C$, so step 5.1 shows that every off-diagonal entry is $\lambda$. Thus distinct blocks meet in exactly $\lambda$ points.

Substituting $k=3$ and $\lambda =1$ into [L2] gives $r=(v-1)\mathrm{/}2\in \mathbb{N}$, so $v$ is odd.

The same substitution gives $b=v(v-1)\mathrm{/}6\in \mathbb{N}$, so $3$ divides $v(v-1)\mathrm{/}2$.

Among the odd residue classes modulo $6$, only $1$ and $3$ make $v(v-1)\mathrm{/}2$ divisible by $3$. Hence $v\equiv 1$ or $3(\mathrm{m}\mathrm{o}\mathrm{d}6)$.

In $\mathbb{Z}\mathrm{/}n$ one has $[2{]}_n[(n+1)\mathrm{/}2{]}_n=[1{]}_n$, because $2\cdot (n+1)\mathrm{/}2=n+1\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$. Therefore $x\circ x=x$ for every $x\in Q$, and if $x\circ z=x\circ z^{\mathrm{\prime }}$ then multiplying by $[2{]}_n$ gives $z=z^{\mathrm{\prime }}$. So for each fixed $x$, the map $z\mapsto x\circ z$ is a bijection of $Q$.

By [L1], the point set $Q\times (\mathbb{Z}\mathrm{/}3)$ has $3n=6m+3$ points.

There are $n$ vertical blocks $V_x$ and $3\left(\genfrac{}{}{0px}{}{n}{2}\right)$ blocks of the form $B_{\{x,y\},i}$.

A pair of points with the same first coordinate and different second coordinates lies in exactly one vertical block, namely $V_x$. No block of the form $B_{\{x,y\},i}$ contains such a pair, because its first two points have distinct first coordinates.

A pair of points of the form $(x,i)$ and $(y,i)$ with $x\mathrm{\ne }y$ lies in exactly one block of the form $B_{\{x,y\},i}$, because the unordered pair $\{x,y\}$ and the layer $i$ determine that block. No vertical block contains such a pair.

A pair of points of the form $(x,i)$ and $(y,i+[1{]}_3)$ with $x\mathrm{\ne }y$ lies in exactly one block of the form $B_{\{x,z\},i}$: by step 1.1 there is a unique $z\in Q$ with $x\circ z=y$, and $z\mathrm{\ne }x$ because $x\circ x=x\mathrm{\ne }y$. Distinct choices of $z$ would contradict the injectivity from step 1.1.

Every unordered pair of distinct points falls into exactly one of the three cases from steps 1.4, 1.5, and 2.1, after swapping the pair if necessary to make the second coordinates differ by $[1{]}_3$. Hence every pair of distinct points lies in exactly one block.

Every block has size $3$, and step 3.1 shows that the block family is a $2$-$(3n,3,1)$ design. Since $m\ge 1$, one has $n\ge 3$ and therefore $3<3n$, so [L3] applies and yields a Steiner triple system on $3n=6m+3$ points.

If a Steiner triple system of order $v$ exists, then [L4] gives $v>3$, and [L1] gives $v\equiv 1$ or $3(\mathrm{m}\mathrm{o}\mathrm{d}6)$.

Conversely, suppose $v>3$ and $v\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}6)$. Then $v=6m+3$ for some natural number $m$, and $v>3$ forces $m\ge 1$. So [L2] gives a Steiner triple system of order $v$.

Suppose instead that $v>3$ and $v\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}6)$. Then $v=6m+1$ for some integer $m\ge 1$, because $v\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}6)$ and $v>3$ force $v\ge 7$. Now [L3] gives a Steiner triple system of order $v$.

The two congruence classes $1$ and $3$ modulo $6$ exhaust the converse assumption, so steps 1.2 and 1.3 prove that direction. Together with step 1.1, this proves the theorem.

Let $\mathrm{\ell }$ and $m$ be distinct lines, and write $p:=\mathrm{\ell }\cap m$, which exists and is unique by [L1].

There is a point $x$ outside $\mathrm{\ell }\cup m$. If one of the four noncollinear points from [L1] lies outside $\mathrm{\ell }\cup m$, choose it. Otherwise exactly two of them lie on $\mathrm{\ell }$ and two lie on $m$; let $a\in \mathrm{\ell }\setminus m$ and $c\in m\setminus \mathrm{\ell }$ be such points. The line through $a$ and $c$ is distinct from both $\mathrm{\ell }$ and $m$, so because every line contains at least three points, it has a point $x$ different from $a$ and $c$, and that $x$ lies on neither $\mathrm{\ell }$ nor $m$.

For each $y\in \mathrm{\ell }\setminus \{p\}$, let $\phi (y)$ be the unique point where the line through $x$ and $y$ meets $m$. Since $x\mathrm{\notin }m$, one has $\phi (y)\mathrm{\ne }p$, and if $\phi (y_1)=\phi (y_2)$ then the lines through $x$ and $y_1,y_2$ coincide, forcing $y_1=y_2$. So $\phi$ is injective from $\mathrm{\ell }\setminus \{p\}$ to $m\setminus \{p\}$.

Reversing the same construction with the roles of $\mathrm{\ell }$ and $m$ exchanged gives an injective map from $m\setminus \{p\}$ to $\mathrm{\ell }\setminus \{p\}$. Since the two sets are finite, they have the same cardinality. Therefore $\mathrm{\mid }\mathrm{\ell }\mathrm{\mid }=\mathrm{\mid }m\mathrm{\mid }$.

Choose a line $\mathrm{\ell }\in \mathcal{L}$. Since no line contains three of the four noncollinear points from [L2], some point $p\in P$ lies outside $\mathrm{\ell }$.

For each point $q\in \mathrm{\ell }$, there is a unique line through $p$ and $q$, and distinct points of $\mathrm{\ell }$ give distinct lines through $p$. Conversely, any line through $p$ meets $\mathrm{\ell }$ in exactly one point by [L2]. Therefore exactly $n+1$ lines pass through $p$.

Each of the $n+1$ lines through $p$ contains exactly $n$ points besides $p$, and the sets of those other points are pairwise disjoint because two distinct lines through $p$ meet only at $p$. Every point distinct from $p$ lies on exactly one of these lines, namely its unique joining line with $p$. Therefore $\mathrm{\mid }P\mathrm{\mid }=1+n(n+1)=n^2+n+1$.

Count incident pairs $(x,{\mathrm{\ell }}^{\mathrm{\prime }})$ with $x\in {\mathrm{\ell }}^{\mathrm{\prime }}$. By [L1], each line contributes $n+1$ such pairs. By step 2.1 and the argument there applied to an arbitrary point, each point also lies on exactly $n+1$ lines. Therefore $\mathrm{\mid }\mathcal{L}\mathrm{\mid }(n+1)=\mathrm{\mid }P\mathrm{\mid }(n+1)$, and step 3.1 gives $\mathrm{\mid }\mathcal{L}\mathrm{\mid }=\mathrm{\mid }P\mathrm{\mid }=n^2+n+1$.

By [L1], every block has size $n+1$, and by [L2], every pair of distinct points lies in exactly one block. Thus $(P,\mathcal{L})$ is a $2$-$(n^2+n+1,n+1,1)$ design.

By [L3], the number of blocks equals the number of points, namely $n^2+n+1$, so the design is symmetric.

Choose a field $F$ with $q$ elements by [L1], and let points and lines be the one-dimensional and two-dimensional subspaces of $F^3$.

If $U$ and $V$ are distinct points, choose nonzero vectors $u\in U$ and $v\in V$. They are linearly independent, so their span is a two-dimensional subspace containing both $U$ and $V$. Any two-dimensional subspace containing $U$ and $V$ contains $u$ and $v$, hence contains their span, so this line is unique.

Let $W_1$ and $W_2$ be distinct lines. Each has $q^2$ elements by [L2]. If $W_1\cap W_2=\{0\}$, then the map $W_1\times W_2\to F^3$, $(x,y)\mapsto x+y$, is injective, so $F^3$ would have at least $q^4$ elements, contradicting [L2]. Thus $W_1\cap W_2$ contains a nonzero vector and therefore at least one point. If it contained two distinct points, then it would contain the two-dimensional span of those points, forcing $W_1=W_2$. So distinct lines meet in exactly one point.

The four one-dimensional subspaces $⟨e_1⟩$, $⟨e_2⟩$, $⟨e_3⟩$, and $⟨e_1+e_2+e_3⟩$ have no three on one line: the span of any two coordinate axes is the set of vectors with one coordinate $0$, which does not contain $e_1+e_2+e_3$, and the span of $⟨e_i⟩$ with $⟨e_1+e_2+e_3⟩$ does not contain either of the other two coordinate axes.

Let $W$ be a line. By [L2], $W$ has $q^2-1$ nonzero vectors. Each point on $W$ has $q-1$ nonzero vectors, and two distinct points meet only in $0$, so the points on $W$ partition the nonzero vectors of $W$ into pieces of size $q-1$. Hence $W$ contains $(q^2-1)\mathrm{/}(q-1)=q+1$ points, which is at least $3$ because every prime power satisfies $q\ge 2$.

Steps 2.1, 2.2, 2.3, and 2.4 verify the axioms of A finite projective plane, and step 2.4 identifies the common line size as $q+1$. Therefore The order of a finite projective plane gives order $q$.

For fixed $i$, the map $j\mapsto ai+j$ is a translation of $F$, so it is a bijection. For fixed $j$, the map $i\mapsto ai+j$ is the composition of multiplication by the nonzero scalar $a$ and a translation, so it is also a bijection. Thus $L_a$ is a Latin square of order $q$.

Assume $a\mathrm{\ne }b$. Given symbols $s,t\in F$, a cell $(i,j)$ satisfies $L_a(i,j)=s$ and $L_b(i,j)=t$ exactly when $ai+j=s$ and $bi+j=t$. Subtracting gives $(a-b)i=s-t$, and since $a-b\mathrm{\ne }0$ there is a unique solution $i$. Then $j=s-ai$ is also unique. Therefore every ordered pair $(s,t)$ occurs exactly once, so $L_a$ and $L_b$ are orthogonal.

Choose a field $F$ with $q$ elements by [L1]. It has exactly $q-1$ nonzero elements.

By [L2], the squares $L_a$ for $a\in F^{\times }$ are pairwise orthogonal Latin squares of order $q$. Since there are exactly $q-1$ of them, [L3] makes this family complete.