Suddenly, without warning, his feverish activity was interrupted and was replaced by a kind of fascination. He spent several days as if he were bewitched, softly repeating to himself a string of fearful conjectures without giving credit to his own understanding. Finally, one Tuesday in December, at lunchtime, all at once he released the whole weight of his torment. The children would remember for the rest of their lives the august solemnity with which their father, devastated by his prolonged vigil and by the wrath of his imagination, revealed his discovery to them: `The earth is round, like an orange.'
Today we put our theory to work by solving the following problem.
Problem
The affine plane $\FF_3^2$ has $12$ lines, so there are $12^3 = 1728$ ordered triples of lines $(\ell_1, \ell_2, \ell_3)$. How many of these triples are essentially different, up to an affine change of coordinates?
Classifying $1728$ configurations directly by hand would suck. Instead we will use the arithmetic of group actions to break this problem down into manageable pieces. The tool that makes this possible is the correspondence between double cosets and orbits on products from Problem Set 4.
2.1The Affine Plane Over $\FF_3$
Recall that the affine group of a ring $R$ is $\aff(R) = \{ax + b : a \in R^\times,\ b \in R\}$, acting on $R$ by evaluation. The two-dimensional version replaces $R$ by $R^2$ and the unit $a$ by an invertible matrix: \[ \aff_2(\FF_3) := \{\, v \mapsto Av + b : A \in \gl_2(\FF_3),\ b \in \FF_3^2 \,\}. \] Elements of $\aff_2(\FF_3)$ are the affine changes of coordinates of the “plane” $\FF_3^2$. Throughout, let $G := \aff_2(\FF_3)$. An affine line in $\FF_3^2$ is a set of the form \[ \ell = \{(x,y) \in \FF_3^2 : ax + by = c\} \qquad \text{with } (a,b) \neq (0,0). \] Equivalently, $\ell = v_0 + W$ is a coset of a one-dimensional subspace $W \subseteq \FF_3^2$. We call the subspace $W$ the direction of $\ell$, and two lines are parallel if they have the same direction. Let $L$ denote the set of all affine lines in $\FF_3^2$. Using the language of group actions, our Problem is equivalent to asking: How many $G$ orbits are there in the $G$-set $L^3$? To approach this systematically, we first study $L$ as a $G$-set.
Problem 2.1 · Lines
- How many directions are there, and how many lines in each direction? Use this to count $|L|$ the total number of affine lines in $\FF_3^2$.
- The group $G$ acts on $L$ by $g(\ell) = \{g(p) : p \in \ell\}$. Prove that $G$ acts transitively on $L$.
- Find the order $|G|$, and use the Orbit-Stabilizer Theorem to find the order of the stabilizer $H := G_{\ell_0}$ of the line $\ell_0 = \{y = 0\}$.
Since $G$ acts transitively on $L$, we have an isomorphism of $G$-sets $L \cong G/H$.
2.2Reduction Lemma
The key lesson for today is the following principle: to classify configurations that contain a $t$, fix $t$ and let its stabilizer act on the rest.
Lemma 2.1 (Reduction Lemma)
Let $T$ be a transitive $G$-set, let $t \in T$, and let $X$ be any $G$-set. The map $x \mapsto (t, x)$ induces a bijection \[ X/G_t \longrightarrow (T \times X)/G \] between the $G_t$-orbits on $X$ and the $G$-orbits on $T \times X$. Moreover, the $G$-orbit of $(t,x)$ has size $|T| \cdot |G_t x|$.
Proof
Every $G$-orbit on $T \times X$ contains a point of the form $(t, x)$: given $(t', x')$, transitivity gives $g \in G$ with $g t' = t$, and then $g(t', x') = (t, gx')$. So the map is surjective. If $(t, x)$ and $(t, x')$ lie in the same $G$-orbit, then $g(t,x) = (t,x')$ for some $g$, which says exactly that $g \in G_t$ and $gx = x'$; so $x$ and $x'$ lie in the same $G_t$-orbit. Thus the map is injective, hence bijective. Finally, the stabilizer of $(t,x)$ in $G$ is $G_t \cap G_x$, which is the stabilizer of $x$ in $G_t$, so \[ |G(t,x)| = \frac{|G|}{|G_t \cap G_x|} = \frac{|G|}{|G_t|} \cdot \frac{|G_t|}{|G_t \cap G_x|} = |T| \cdot |G_t x|. \tag*{$\square$}\]
Remark
When $T = G/H$ and $X = G/K$ with $t = H$, the $H$-orbits on $G/K$ are precisely the double cosets $HgK$, and the lemma becomes the bijection $H\backslash G/K \to (G/H \times G/K)/G$ from Problem Set 4. The lemma is slightly more flexible since $X$ need not be transitive.
2.3Pairs of Lines
Our next step towards counting the orbits in $L^3$ is to study the structure of $L^2 = L \times L$. We apply the Reduction Lemma with $T = X = L$ and $t = \ell_0 = \{y = 0\}$. The $G$-orbits on $L \times L$ correspond to the $H$-orbits on $L$, and an $H$-orbit on $L$ is a “relative position” of a second line with respect to $\ell_0$.
Problem 2.2 · Relative positions of two lines
- Determine the $H$-orbits on $L$. Describe each orbit geometrically and record its size. Keep in mind that the sizes must sum to $12$.
Define three subsets of $L \times L$:
\[\begin{aligned} D &:= \{(\ell, \ell) : \ell \in L\}, \\ P &:= \{(\ell_1, \ell_2) : \ell_1 \parallel \ell_2,\ \ell_1 \neq \ell_2\}, \\ I &:= \{(\ell_1, \ell_2) : \ell_1 \cap \ell_2 \text{ is a single point}\}. \end{aligned}\]Show that each of $D$, $P$, $I$ is a transitive $G$-set and compute their sizes. Note that their sizes must sum to $|L \times L| = 144$.
- Prove that $D \cong L$.
Thus it follows that in the Burnside semiring $B(G)$ we have \[ [L]^2 = [D] + [P] + [I] = [L] + [P] + [I]. \]
Remark
This is the sense in which a double coset is a “relative position”. The double cosets $H \backslash G / H$ are in bijection with $G$-orbits on $L \times L$, and we have just seen that these orbits are “equal,” “parallel,” and “intersecting.” Notice that these are exactly the relationships between two lines that an affine map preserves. Angles and distances never appeared, because $\aff_2(\FF_3)$ does not preserve them.
2.4Triples of Lines
Now we return to the Problem. In $B(G)$ we have
Thus to calculate the number of $G$-orbits in $L^3$ it suffices to work out the number of orbits in $P \times L$ and $I \times L$.
Problem 2.3 · Case $P$: the first two lines are distinct and parallel
Fix the pair $\ell_1 = \{y = 0\}$ and $\ell_2 = \{y = 1\}$ in $P$, and let $S := G_{(\ell_1, \ell_2)}$ be the stabilizer of this ordered pair.
- Describe $S$ explicitly and compute its order. Check your answer against the Orbit-Stabilizer Theorem applied to $P$.
- Determine the $S$-orbits on $L$. Describe each orbit geometrically and record its size.
- Using the size formula in the Reduction Lemma, list the sizes of the $G$-orbits on $P \times L$. Note that the orbit sizes sum to $|P \times L| = 288$.
Problem 2.4 · Case $I$: the first two lines intersect
Fix the pair $\ell_1 = \{x = 0\}$ and $\ell_2 = \{y = 0\}$ in $I$, and let $S := G_{(\ell_1, \ell_2)}$.
- Describe $S$ explicitly and compute its order.
- Determine the $S$-orbits on $L$. Describe each geometrically and record its size.
- List the sizes of the $G$-orbits on $I \times L$ and check that they sum to $|I \times L| = 1296$.
Problem 2.5 · Reassembling the answer
- Solve the original problem: how many $G$-orbits are there on ordered triples of lines? What are the sizes of these orbits?
- Which of the $13$ orbits is isomorphic to $G$ itself as a $G$-set? Which orbits are isomorphic to $L$?
Let's reflect on what we did here. We never looked at $1728$ triples individually. Instead we classified the relative position of two lines once, recorded the answer as $[L]^2 = [L] + [P] + [I]$, and then multiplied by $[L]$. The identity $[L]^2 = [L] + [P] + [I]$ was reusable information which simplified our analysis.
Problem 2.6 · (Challenge)
Replace $\FF_3$ by $\FF_p$ for a prime $p$. Show that $\aff_2(\FF_p)$ has exactly $p + 10$ orbits on ordered triples of lines in $\FF_p^2$.