Speaker:James Davies, University of Cambridge Title: Odd distances in colourings of the plane

Abstract: We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd integer distance from each other. The proof uses a spectral method.

Happy New Year from all of us at the Matroid Union!

Decomposition of objects into smaller or simpler objects is a central theme in combinatorics. Think about decomposing a graph into its connected components or blocks, or into forests. In today’s post, I discuss decomposing finite projective geometries into projective geometries of smaller rank.

Definition: Let $q$ be prime power, let $n \ge t \ge 1$ be integers and let $M = \text{PG}(n-1,q)$ be the projective geometry over the field with $q$ elements. A $t$-spread of $G$ is a collection of rank-$t$ flats of $M$ that partition the points of $M$—that is, these flats are pairwise disjoint and their union is the set of all points of $M$.

(Geometers often use dimension instead of rank; the dimension of a projective geometry is one less than its rank. Their $t$-spreads are collections of $t$-dimensional subspaces of an $n$-dimensional space. We will however stick to the terminology that is more familiar in the matroid theory setting.)

Every projective geometry has a 1-spread: the flats making up the spread are simply the points of the geometry. It is much more interesting to look into the existence of $t$-spreads when $t \ge 2$.

The Fano plane $F_7 = \text{PG}(2,2)$ does not admit a decomposition into triangles. The quickest argument to see this is based on counting the number of points: any matroid that can be decomposed into triangles necessarily has a number of points that is a multiple of 3, but the Fano plane has seven points. By contrast, the projective geometry $\text{PG}(3,2)$, which has fifteen points, can be partitioned into five triangles (as encoded using different colours in the following representation:

The counting argument above can be generalised. In order for $M = \text{PG}(n-1,q)$ to have any hope of admitting a $t$-spread, the number of points in a projective geometry of rank $t$ should evenly divide the number of points in $M$, or $\frac{q^t-1}{q-1} \bigg| \frac{q^n-1}{q-1}$. It is a nice exercise to show that the latter happens precisely when $n$ is a multiple of $t$. So, if $\text{PG}(n-1,q)$ can be decomposed into rank-$t$ subgeometries, we must have $t|n$.

It turns out that this divisibility criterion is not only necessary—it is sufficient as well. We end this blog post with a slick proof of this fact. The proof can be found in many introductory texts on projective geometry.

Theorem: The projective geometry $M=\text{PG}(n-1,q)$ admits a $t$-spread if and only if $t|n$.

Proof: We already proved the implication from left to right. The implication in the other direction follows from a construction.

Suppose that $n = kt$ for some integer $k$. The points of $M$ can be identified with the 1-dimensional subspaces of the vector space $\mathbb{F}_q^n$. We will show that $\mathbb{F}_q^n$ can be decomposed into $t$-dimensional subpspaces that are pairwise disjoint (except that they all contain the zero-vector). As the 1-dimensional subspaces of $\mathbb{F}_q^t$ can be identified with the points of a $\text{PG}(t-1,q)$, this immediately implies the theorem.

Consider the $k$-dimensional $\mathbb{F}_{q^t}$-vector space $\mathbb{F}_{q^t}^k$. Its 1-dimensional subspaces intersect only in the zero-vector. These 1-dimensional subspaces give us our spread, as each such subspace can alternatively be viewed as a $t$-dimensional $\mathbb{F}_q$-vector space. $\Box$