8 Finite Geometry

A sub-geometry of $\mathcal{S}$ is a geometry ${\mathcal{S}}^{\prime }=({\mathcal{P}}^{\prime },{\mathcal{L}}^{\prime },{\mathrm{I}}^{\prime })$ with ${\mathcal{P}}^{\prime }\subseteq P$, ${\mathcal{L}}^{\prime }\subseteq \mathcal{L}$ and ${\mathrm{I}}^{\prime }=\mathrm{I}\cap ({\mathcal{P}}^{\prime }\times {\mathcal{L}}^{\prime })$.

Link to original

Definition

An incidence geometry is a pair $\mathcal{G}=(\Omega ,I)$ where $\Omega$ is a set and $I\subseteq \Omega \times \Omega$ is symmetric and transitive.

Definition

Let $\mathcal{G}=(\Omega ,I)$ be an incidence geometry. A (maximal) flag in $\mathcal{G}$ is a (maximal) chain with $\mathcal{G}$ seen as a poset.

Definition

A geometry $\mathcal{G}=(\Omega ,I)$ has rank $r$ if we can partition $\Omega$ into $r$ antichains ${\Omega }_1,\cdots ,{\Omega }_r$.

Definition

A projective plane is an incidence geometry of points and lines with the following properties:

• Every two points are incident with a unique common line.
• Every two lines are incident with a unique common point.
• There are four points, no three collinear.

Note that i) and ii) are dual, and iii) implies its dual.

Proposition

• Every point in a finite projective plane is incident with $(n+1)$ lines.
• Dually, every line is incident with $(n+1)$ points.

$n$ is called the order of the projective plane $\mathcal{G}=(\mathcal{P},\mathcal{L},I)$.

\begin{proof} There exist a point $P$ and a line $L$ such that $P/IL$. Note that the number of points incident with $L$ equals the number of lines incident with $P$. There also exists point $Q$ such that $Q/IL$, so the number of lines incident with $P$ equals the number of lines incident with $Q$.

The $P,Q,L$ are arbitrarily chosen, so we finish the proof. \end{proof}

Proposition

A finite projective plane of order $n$ has $n^2+n+1$ points and $n^2+n+1$ lines.

\begin{proof} Each point $x$ has valency $n+1$ and each line incident with $x$ has $n+1$ points including $x$. Then $|S|=(n+1)n+1=n^2+n+1$. \end{proof}

Prime Order Conjecture

For a prime $n$, $PG(2,n)$ is the only projective plane of order $n$.

Prime Power Conjecture

The order of a projective plane is necessarily a prime power.

Later we will investigate projective planes in higher dimension. There all are $PG(n,q)$, where points are $1$-spaces of $V(n+1,q)$, lines are $2$-spaces and so on.

Bruck-Ryser-Chowla

If there is a projective plane of order $n$ and $n\equiv 1(\mathrm{mod}4)$ of $n\equiv 2(\mathrm{mod}4)$, then $n$ is the sum of two squares.

\begin{proof} See A course in combinatorics - 1992 - van Lint, Wilson.pdf. \end{proof}

Remark. For example, a projective plane of order $10$ does not exist, proved by Clement Lam in 1989. Furthermore, the existence of projective plane of order $12$ is still open.

One More Construction

Definition

Let $n$ be a positive integer. A set $\mathcal{D}$ of positive integer is called difference set of order $n$ if

• $|\mathcal{D}|=n+1$
• Each number $m$ in $[n^2+n]$ has a unique representation $m\equiv d-d^{\prime }(\mathrm{mod}{n}^2+n+1)$ for $d,d^{\prime }\in \mathcal{D}$.

Examples.

• ${\mathcal{D}}_2=\{1,2,4\}$
• ${\mathcal{D}}_3=\{1,2,4,10\}$
• ${\mathcal{D}}_4=\{1,2,5,15,17\}$

Theorem

Let $\mathcal{D}$ be a different set of order $n⩾2$. Then the following is a projective plane of order $n$:

• the points are $0,1,\cdots ,n^2+n$;
• the lines are $\mathcal{D}+i$ with $i\in \{0,\cdots ,n^2+n\}$, where $\mathcal{D}+i=\{d+i:d\in \mathcal{D}\}$ module $n^2+n+1$.

Remark. The projective plane induced from ${\mathcal{D}}_2$ is Fano plane.

\begin{proof} i) Let $x,x^{\prime }$ be points. By definition of $\mathcal{D}$, there exist unique $d,d^{\prime }\in \mathcal{D}$ such that $x-x^{\prime }\equiv d-d^{\prime }(\mathrm{mod}{n}^2+n+1)$. Put $i=x-d$, then $i=x^{\prime }-d^{\prime }$ module $n^2+n+1$. Thus $\mathcal{D}+i$ is a line through $x$ and $x^{\prime }$. Conversely, if $x,x^{\prime }\in \mathcal{D}+i^{\ast }$, then $x=d_1+i^{\ast }$ and $x^{\prime }=d_2+i^{\ast }$. It deduces that $x-x^{\prime }=d_1-d_2(\mathrm{mod}{n}^2+n+1)$, and so $d_1=d$, $d_2=d^{\prime }$. Therefore, $i^{\ast }=i$ and the line through $x$ and $x^{\prime }$ is unique.

ii) Let $\mathcal{D}+i$ and $\mathcal{D}+j$ be distinct lines. Then $x\in (\mathcal{D}+i)\cap (\mathcal{D}+j)$ iff there exists $d,d^{\prime }\in \mathcal{D}$ such that $x\equiv d+i\equiv d^{\prime }+j(\mathrm{mod}{n}^2+n+1)$. Then $d,d^{\prime }$ are determined by $j-i$ and so $x$ is uniquely determined. \end{proof}

Ovals

Definition

An arc in a projective plane is a set of points such that no three points are collinear.

Lemma

Let $G$ be an arc of a projective plane of order $n$. Then $|G|⩽n+2$ and $|G|⩽n+1$ if $n$ is odd.

\begin{proof} Take $P\in G$, then there are $n+1$ lines through $P$ and each line has at most one point in $G$. Hence $|G|⩽1+n+1=n+2$.

If the equality holds, then no line intersects $G$ in $1$ point. Take point $Q\notin G$. Let $m$ denote number of secant lines through $Q$. Then $n+2=|G|=2m$. It is impossible for $n$ odd. \end{proof}

Definition

• An arc of size $n+1$ is called an oval.
• An arc of size $n+2$ is called hyperoval.
• Conic is anything isomorphic to

$$\begin{array}{rl}G& =\{⟨x,y,z⟩:x^2=yz\}\\ & =\{⟨(0,1,0)⟩\}\cup \{⟨(t,t^2,1)⟩:t\in \mathrm{GF}(q)\}.\end{array}$$

Remark that conics are ovals when $q$ is odd.

We will prove later that each oval of $PG(2,q)$ is a conic when $q$ is odd, see ^mrpzaz. When $q$ is even, there exist some oval is not a conic, the following proposition is an example.

Proposition

The set ${\mathcal{O}}_i=\{⟨(0,0,1)⟩\}\cup \{⟨(1,t,t^{2^i})⟩:t\in \mathrm{GF}(2^h)\}$ is an oval in $PG(2,2^h)$ iff $\gcd (i,h)=1$.

\begin{proof} Every line incident with $⟨(0,0,1)⟩$ of the form $y=ax$ is incident with precisely one more point of ${\mathcal{O}}_i$, namely, $⟨(1,a,a^{2^i})⟩$. The line $x=0$ is a tangent. The other lines are of the form $z=ax+by$. The line $z=ax+by$ is incident with $⟨(1,t,t^{2^i})⟩$ iff $t^2=bt+a$. If $u^{2^i}=bu+a$ and $v^{2^i}=bv+a$, then $u^{2^i}-v^{2^i}=b(u-v)$, but also $u^{2^i}-v^{2^i}=(u-v{)}^{2^i}$. Thus, $b=(u-v{)}^{2^i-1}$.

As $\gcd (i,h)=1$, there exists $m,n$ such that $m(2^i-1)+n(2^h-1)=1$. Hence $b^m=(u-v{)}^{1-n(2^h-1)}=u-v$. So $u,v$ determine $b$ and we do not have further solutions. \end{proof}

Lemma

Let $\mathcal{O}$ be an oval in a projective plane of order $n$, where $n$ is odd. Then any point not in $\mathcal{O}$ has $0$ or $2$ tangents.

\begin{proof} Let $x_i$ be the number of points not in $\mathcal{O}$ incident with $i$ tangents. Clearly, $\sum x_i=n^2$.

Count $(P,L)$, $P$ exterior point, $L$ tangent and $PIL$. Then $\sum i{x}_i=(n+1)n$.

Now count $(P,L,M)$, where $P$ exterior point, $L,M$ tangent and $PIL,M$. Then $\sum i(i-1)x_i=(n+1)n$.

Thus, $\sum i(i-2)x_i=0$. Now $n+1$ is even, so any exterior point is on even number of tangents. Therefore, $x_i=0$ when $i\ne 0,2$. \end{proof}

Lemma

Let $\mathcal{O}$ be an oval in a projective plane of order $n$, with $n$ even. Then every point not in $\mathcal{O}$ is on precisely $1$ or $(n+1)$ tangents. In particular, there is precisely one point on $n+1$ tangents.

\begin{proof} See ^a8a6er. \end{proof}

Definition

The point on $n+1$ tangents is called nucleus.

Corollary

Any oval in a projective plane of even order can be extended to an hyperoval by adding its nucleus.

Segre

An oval in $PG(2,q)$ with odd $q$ is a conic.

The definition of oval can be generalized to projective geometry of higher dimension.

MDS = Maximal Distance Separable Code

An arc $\mathcal{A}$ of $PG(r,q)$ is a set of points such that no hyperplane contains more than $r$ points. If $r⩽q-1$, then

• If $q$ even, $r=2$ or $r=q-2$, then $|\mathcal{A}|⩽q+2$;
• if $q$ odd, $3⩽r⩽q-3$, then $|\mathcal{A}|⩽q+1$.

Subplanes

Definition

A projective plane ${\Pi }^{\prime }=({\mathcal{P}}^{\prime },{\mathcal{L}}^{\prime },I^{\prime })$ is a subplane of $\Pi =(\mathcal{P},\mathcal{L},I)$ if ${\mathcal{P}}^{\prime }\subseteq \mathcal{P}$, ${\mathcal{L}}^{\prime }\subseteq \mathcal{L}$ and $I^{\prime }=(\mathcal{P}\times \mathcal{L})\cap I$.

Bruck

If a projective plane ${\Pi }_n$ of order $n$ contains a subplane ${\Pi }_s$ of order $s$, then either $n=s^2$ or $n⩾s^2+s$.

\begin{proof} Let $T$ be a tangent of ${\Pi }_s$, i.e. $T$ is a line of ${\Pi }_n$ containing a single point $P$ of ${\Pi }_s$. There are $s^2$ lines in ${\Pi }_s$ that does not contain $P$. No two of these meet $T$ in the same point (otherwise their intersection is contained in ${\Pi }_s$.)
Thus $n⩾s^2$. (The existence of $T$: for a point $P\in {\Pi }_s$, there are $s+1$ lines in ${\Pi }_s$ through $P$ and $n+1$ lines in ${\Pi }_n$ through $P$. Hence there are $n-s$ lines of ${\Pi }_n$ containing a single point $P$ of ${\Pi }_s$. )

Now we prove that if $n\ne s^2$, then $n⩾s^2+s$. The total number of tangents of ${\Pi }_s$ is $(n-s)(s^2+s+1)$, using the argument above. It deduces that there are $(n^2+n+1)-(s^2+s+1)-(s^2+s+1)(n-s)=(n-s^2)(n-s)$ lines containing no point of ${\Pi }_s$. If $n>s^2$, then there is an external line $L$. Since all lines of ${\Pi }_s$ intersect with $L$ with different intersection, we know $s^2+s+1⩽n+1$ and so $n⩾s^2+s$. \end{proof}

Definition

A projective subspace of order $\sqrt{n}$ is called Baer subspace.

Remark. Note that each line intersects a Baer subplane in precisely $1$ or $\sqrt{n}+1$ points.

Remarks.

• Hyperovals: $0$ or $2$
• Baer subplanes: $1$ or $\sqrt{n}+1$ ($n+\sqrt{n}+1$ points in total)
• Unitals: $1$ or $\sqrt{n}+1$ ($n^{1.5}+1$ points in total)

Unitals

Definition

A unital $\mathcal{U}$ of a projective plane of order $n^2$ is a set of $n^3+1$ points such that every line intersects $\mathcal{U}$ in $1$ or $n+1$ points.

Exercise. The Hermitian unital in $PG(2,q)$:

$$\mathcal{H}=\{⟨(x,y,z)⟩\subseteq {\mathbb{F}}_{q^2}^3:x^{q+1}+y^{q+1}+z^{q+1}=0\}.$$

\begin{proof} Here we show that $\mathcal{H}$ is a unital.

First show $|\mathcal{H}|=q^3+1$.

Count points of the form $⟨(x,y,1)⟩$. Note that $x^{q+1}=c\in {\mathbb{F}}_q^{\ast }$ has $q+1$ solutions. If $y^{q+1}=-1$, then $x^{q+1}=0$ and so $x=0$. Thus $q+1$ choices on $y$. If $y^{q+1}\ne -1$, then $x^{q+1}=-y^{q+1}+1$ has $q+1$ solutions for gives $y^{q+1}$. In total, there are $(q^2-(q+1))(q+1)$ choices. So number of points of the form $⟨(x,y,1)⟩$ is $(q+1)+(q^2-(q+1))(q+1)$.

Count points of the form $⟨(x,1,0)⟩$. Here we solve $x^{q+1}+1=0$, which has $q+1$ solutions. Furthermore, $⟨(1,0,0)⟩$ not on $\mathcal{H}$.

Therefore, $|\mathcal{H}|=q^3+1$.

Define $H(u,v)=u_1{v}_1^q+u_2{v}_2^2+u_3{v}_3^q$.

• $H(u,v)=H(v,u{)}^q$
• $H(u+v,w)=H(u,w)+H(v,w)$
• $H(w,u+v)=H(w,u)+H(w,v)$
• $H(\alpha u,v)=\alpha H(u,v)$
• $H(u,\alpha v)={\alpha }^{q}H(u,v)$

So $H$ is a sesquilinear form.

Let $L=⟨u,v⟩$, $u,v\in \mathcal{H}$, i.e., $H(u,u)=0=H(v,v)$. We claim that $L$ has $q+1$ points. Indeed, for $P=⟨u+\alpha v⟩\subseteq L$ with $\alpha \in {\mathbb{F}}_{q^2}$, we have

$$0=H(u+\alpha v,u+\alpha v)={\alpha }^{q}H(u,v)+\alpha H(u,v{)}^q={\alpha }^q\beta +\alpha {\beta }^q$$

for $\beta =H(u,v)$. Note that $\alpha =0$ is a solution. If $\alpha \ne 0$, then ${\alpha }^{q-1}\beta +{\beta }^q=0$ has $q-1$ solutions with $\alpha \ne 0$ if $\beta \ne 0$. Remark that $\beta \ne 0$ follows from $H(u,v)=u^T{v}^q$ having full rank. We are left with $|L\cap \mathcal{H}|\in \{0,1,q+1\}$. Counting shows that $0$ does not occur. \end{proof}

Remark. The Hermitian unital provides a crucial algebraic construction for establishing lower bounds on Ramsey numbers, specifically $R(4,t)$. By utilizing the fact that the Hermitian unital contains no O’Nan configurations, one can construct a $K_4$​-free graph that significantly improves the known lower bound for $R(4,t)$.

Blocking Sets

Definition

A blocking set in a projective plane is a set of points $\mathcal{B}$ such that each line contains at least one point of $\mathcal{B}$. It is minimal if every point of $\mathcal{B}$ lies on at least one tangent.

Remark. Trivial blocking set: a line.

Theorem

Let $\mathcal{B}$ be a non-trivial minimal blocking set. Then

• $q+\sqrt{q}+1⩽|\mathcal{B}|⩽q\sqrt{q}+1$;
• equality holds in the lower bound if $\mathcal{B}$ is a Baer subplane;
• equality holds in the upper bound only if $\mathcal{B}$ is a unital.

\begin{proof} We will show iii) as an exercise in the future.

Now only lower bound and ii). If a line contains at least $\sqrt{q}+1$ points in $\mathcal{B}$, then we are done: take $P\in L\setminus \mathcal{B}$, then $P$ lies on $q$ other lines, each line contains one more point in $\mathcal{B}$. Thus $|\mathcal{B}|⩾q+\sqrt{q}+1$.

Put $n=\lceil \sqrt{q}\rceil$, and suppose that no line contains more than $n$ points of $\mathcal{B}$. Let $J_i$ be the number of $i$-secants of $\mathcal{B}$, i.e., the number of lines $L$ with $|L\cap \mathcal{B}|=i$. Then ${\sum }_{i=1}^n{J}_i=q^2+q+1$, ${\sum }_{i=1}^{n}i{J}_i=B(q+1)$, and ${\sum }_{i=1}^{n}i(i-1)J_i=B(B-1)$, where $|\mathcal{B}|=B$. Since $1⩽|L\cap B|⩽n$ for all line $L$, we have ${\sum }_{i=1}^n(i-1)(i-n-1)J_i<0$. Note that equations above $(3)-(n+1)(2)-(n+1)(1)$ yields

$$B(B-1)-(n+1)(q+1)B+(n+1)(q^2+q+1)<0$$

and so $q+\sqrt{q}+1⩽q+n+1⩽B⩽qn+1$. The equality holds if there is a line $L$ with $|L\cap \mathcal{B}|=\sqrt{q}+1$. Argument implies that $|L\cap \mathcal{B}|\in \{1,\sqrt{q}+1\}$ and so is Baer subplane. (see here.) \end{proof}

Tibor Szőnyi, 1980s

For prime $p$, there exists minimal blocking set of size $⩾Cq\log q$.

\begin{proof} Uses $R(3,t)⩽C\frac{t^2}{\log t}$. \end{proof}

Remark.

• Hunte, Pohonta, Verstrate, Zhang, 2026, $⩾q^{1.2334}$ for $q$ prime. (Use a number theory construction.)
• Ih, Yue Zhou (2026) “local arcs” of size $⩾q^{1.2334}$, improving coding theory bounds. See here.

For $q>0$, define

$$[a]:=[a{]}_q=\{\begin{array}{ll}\frac{q^a-1}{q-1},& \text{ for }q\ne 1\\ a& \text{ for }q=1\end{array}=\underset{x\to q}{\lim }\frac{x^a-1}{x-1}.$$

Define $\left[\begin{array}{c}a\\ b\end{array}\right]:={\left[\begin{array}{c}a\\ b\end{array}\right]}_q={\prod }_{i=1}^b\frac{[a-i+1{]}_q}{[b-i{]}_q}$ as Gaussian coefficient or $q$-binomial coefficient.

Theorem

The number of $k$-spaces in $V(n,q)$ equals $\left[\begin{array}{c}n\\ k\end{array}\right]$.

\begin{proof} Easy. \end{proof}

Lemma

$\left[\begin{array}{c}n\\ k\end{array}\right]=\left[\begin{array}{c}n-1\\ k\end{array}\right]+q^{n-k}\left[\begin{array}{c}n-1\\ k-1\end{array}\right]=q^k\left[\begin{array}{c}n-1\\ k\end{array}\right]+\left[\begin{array}{c}n-1\\ k-1\end{array}\right]$

\begin{proof} Count $k$-spaces in two ways. By ^ac91vg, $\#k$-spaces $=\left[\begin{array}{c}n\\ k\end{array}\right]$.

Fix a hyperplane $H$, then $H$ contains $\left[\begin{array}{c}n-1\\ k\end{array}\right]$ spaces. A $k$-space not in $H$ meets $H$ in a $(k-1)$-space, there are $\left[\begin{array}{c}n-1\\ k-1\end{array}\right]$. Each $k-1$ spaces lies in $[n-k+1]-[n-k]=q^{n-k}$ $k$-spaces not in $H$. \end{proof}

Theorem

There exists a family of $k$-subspaces of $V(n,q)$ that partitions the $1$-subspaces of $V(n,q)$ iff $k\mid n$.

\begin{proof} Note that $q^k-1\mid q^n-1$ iff $k\mid n$, so one direction is easy.

Conversely, the $1$-subspaces of $V(n/k,q^k)$ correspond to $k$-subspaces of $v(n,q)$. \end{proof}

Remark.

Jamison-Brouwer-Schrijver

If $A$ is a subset of $AG(n,q)$, the affine space of dimension $n$ over the finite field with $q$ elements, which meets all hyperplanes, i.e., $A$ is a blocking set with respect to hyperplanes, then $|A|⩾n(q-1)+1$.

\begin{proof} Let $A$ be a blocking set w.r.t. hyperplanes. WLOG $0\in A$. Put $B:=A\setminus \{0\}$, then $B$ meets all hyperplanes that do not contain $0$, i.e. hyperplanes of the form

$$w_1{x}_1+\cdots +w_n{x}_n=1,w\ne 0.$$

Put $F(x_1,\cdots ,x_n)={\prod }_{b\in B}(b_1{x}_1+\cdots +b_n{x}_n-1)$. Then $F(x_1,\cdots ,x_n)=0$ except for $x=0$. Write $F$ modulo the ideal generated by the polynomials $x_i^q-x_i$, $i=1,\cdots ,n$. Write $F(x_1,\cdots ,x_n)={\sum }_{i=1}^n{F}_i(x_1,\cdots ,x_n)(x_i^q-x_i)+G(x_1,\cdots ,x_n)$, where the highest degree of $x_i$ in $G$ is $⩽q-1$. For each $i$, $x_{i}F(x_1,\cdots ,x_n)=0$ and so $x_{i}G(x_1,\cdots ,x_n)=0$. Thus $\prod (x_i^{q-1}-1)\mid G$. Then $|B|=\mathrm{deg}(F)⩾\mathrm{deg}(G)⩾n(q-1)$. It deduces that $|A|=|B|+1⩾n(q-1)+1$. \end{proof}