Counting lines in finite geometries

If you’ve ever played SET, you’ll know that it’s a fast-paced card game that some people are really annoyingly good at. But more interestingly, it’s based on the geometry of four-dimensional space over the finite field $\mathbb{F}_3$. Each card in SET has four attributes: color, shape, number, and shading, which can be thought of as the $x$, $y$, $z$, and $t$ axes in a four dimensional space. Then, each of these attributes has 3 possible values, so we can think of them as numbers modulo $3$, or more rigorously, elements of the finite field $\mathbb{F}_3$. So a card in SET is a point in $\mathbb{F}_3^4$, which looks like a $3\times 3\times 3\times 3$ grid of points. The “sets” in SET are then “lines” in this finite geometry!

It’s hard to imagine four dimensional grids, though, so let’s consider the finite plane $\mathbb{F}_3^2$, which looks like this:

A line can be defined like lines in the usual plane: the solution set to a linear equation $ax+by=c$, where all variables are assumed to have variables in $\mathbb{F}_3^4$. So for instance, the line $x+y=0$ consists of the points $(0,0)$, $(1,2)$, and $(2,1)$ above. It certainly doesn’t look like those three points form a “line”, but remember, we’re taking everything modulo $3$ and so the geometry is bound to look a bit different.

How many lines are there in $\mathbb{F}_3^2$? Well, let’s first count the lines passing through $(0,0)$, which must be defined by equations of the form $ax+by=0$. It is still true in this finite geometry that there is a unique line passing through any two points (can you see why?), and there are $3^2-1$ points other than $(0,0)$ that we can choose as the second point on the line. So our answer must be $8$, right?

Wrong! We double-counted – for instance, the line $(0,0),(1,2),(2,1)$ was counted once by choosing $(1,2)$ as the second point, and again by choosing $(2,1)$. Since each line contains three points (can you see why?), we overcounted each line $3-1$ times. So, the number of lines through $(0,0)$ is $\frac{3^2-1}{3-1}=4$.

To count all lines, then, for each equation of the form $ax+by=0$, there are two more of the form $ax+by=1$ and $ax+by=2$ which do not pass through $(0,0)$. Thus, there are three times as many lines total as those that pass through the origin. Our total is $4\cdot 3=12$.

By the same argument, in $\mathbb{F}_q^n$, we’d have $q^n-1$ ways to choose a point other than the origin, which overcounts the lines through the origin $q-1$ times each. So there are $\frac{q^n-1}{q-1}$ lines through the origin, and $q\frac{q^n-1}{q-1}$ lines total. Look familiar?

Indeed, we’ve stumbled across our $q$-analog of $n$, in sort of an odd place: the geometry over a finite field $\mathbb{F}_q$ where $q=p^r$ is a power of a prime. This is rather strange because there is no finite field of order $1$, and yet somehow we are supposed to set $q=1$ to determine that this is, indeed, a $q$-analog of something. In fact, there is a theory of geometry over the finite field of order $1$, even though such a field cannot exist! The theory turns out to reduce to basic combinatorics of sets, and the link between the two is summarized nicely here.

Counting subspaces

What if we now try to count $k$-dimensional subspaces, like planes or hyperplanes, rather than lines through the origin? It turns out that the easier place to start is to count the flags in $\mathbb{F}_q^n$, that is, the chains of subspaces $$0=F_0\subset F_1\subset F_2 \subset \cdots \subset F_n=\mathbb{F}_q^n$$ of subspaces where $\dim F_i=i$ for all $i$. The space $F_0$ must be $0$, and there are $(n)_q=\frac{q^n-1}{q-1}$ ways to choose the subspace $F_1$. Now, each $2$-dimensional subspace $F_2$ containing $F_1$ corresponds to a unique line in the $n-1$-dimensional quotient space $\mathbb{F}_q^n/F_1$, which gives $(n-1)_q$ possibilities for $F_2$. Continuing in this fashion, there are $$(n)_q(n-1)_q(n-2)_q\cdots (2)_q(1)_q$$ flags. We call this the $q$-factorial, and is often written $(n)_q!$. We explored the combinatorics of this polynomial in this post and this one, and from this it’s clear that the $q$-factorial gives a natural combinatorial analog of the fact that there are $n!$ permutations of $1,\ldots,n$. It gives us a more refined count of permutations, according to how “mixed up” they are.

Finally, we can count the number of $k$-dimensional subspaces $F_k$ as follows. Any such subspace $F_k$ can be extended to form a complete flag, and there are $(k)_q!$ ways of forming the subspaces contained in $F_k$, and $(n-k)_q!$ ways of forming the larger subspaces containing $F_k$. Since there are $(n)_q!$ flags total, and each $F_k$ appears $(k)_q!(n-k)_q!$ times in this count, we have that there are $$\frac{(n)_q!}{(k)_q!(n-k)_q!}$$ $k$-dimensional subspaces of $\mathbb{F}_q^n$. This expression is a natural $q$-analog of the binomial coefficient $\binom{n}{q}=\frac{n!}{k!(n-k)!}$.

This $q$-binomial coefficient appears everywhere, and we’ll continue exploring its properties next week!