## 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!

There’s an amusing notation for this q-analogue of n!, pronounced “n q-torial” and written with a q over the dot in !, instead of a line. Then at q=1 you almost recover the standard notation.

Hahaha, that is awesome! I never heard of that. ðŸ™‚ Maybe next time I’ll make a corresponding cartoon.

Great intro to q-analogs. Can’t wait for next post. I think the L’Hopital’s Rule example should have a ^4 in there.

Ah, thanks for the typo correction! Glad you enjoyed it.