Enumerating places of $\mathbf{P}^{1}$ up to
automorphisms of $\mathbf{P}^{1}$ in quasilinear time

Let $q=\#k$, let $r=(n-1)/2$, and let $\alpha\in{\mathbf{F}}_{q^{n}}$ be a root of $f$. Then

is a list of $2r+2=n+1$ elements of ${\mathbf{F}}_{q^{n}}$, so there is an ${\mathbf{F}}_{q}$-linear relation among these elements, say

We know that the two sides of this equality are nonzero, because otherwise $\alpha$ would be a root of a polynomial of degree smaller than $n$. Therefore we can write

Let $F$ be the rational function

Then $[\alpha^{q}\,{:}\,1]=F([\alpha\,{:}\,1])$, and the same holds if we replace $\alpha$ by any of its conjugates. Also, $F$ is a rational function of degree at most $r$ (“at most” because there may be common factors in the numerator and denominator that cancel one another). This proves the existence claim of the theorem.

Suppose $F_{1}$ and $F_{2}$ are two rational functions of degree at most $r$ such that $[\alpha^{q}\,{:}\,1]=F_{i}([\alpha\,{:}\,1])$ for $i=1$ and $i=2$. Write $F_{i}=g_{i}/h_{i}$ for homogeneous polynomials $g_{i}$ and $h_{i}$ of degree at most $r$. Then since $F_{1}([\alpha\,{:}\,1])=F_{2}([\alpha\,{:}\,1])$, we see that $[\alpha\,{:}\,1]$ is zero of the homogeneous polynomial $g_{1}h_{2}-g_{2}h_{1}$, whose degree is at most $2r<n$. Since $\alpha$ generates a degree-$n$ extension of ${\mathbf{F}}_{q}$, this is impossible unless $g_{1}h_{2}=g_{2}h_{1}$; that is, unless $F_{1}=F_{2}$. This proves the uniqueness claim of the theorem. ∎

If $\beta$ is a root of $\Gamma(f)$ then we have $[\beta\,{:}\,1]=\Gamma([\alpha\,{:}\,1])$ for a root $\alpha$ of $f$. We check that

so $\Gamma\circ F\circ\Gamma^{-1}$ is the Frobenius function for $\Gamma(f)$. Suppose $\bigl{[}\begin{smallmatrix}a&b\\ c&d\end{smallmatrix}\bigr{]}$ is a matrix that represents $\Gamma$, and suppose $g$ and $h$ are coprime homogenous polynomials such that $F=g/h$. Using the definition of $\Phi$, we find that $\Phi(\Gamma\circ F\circ\Gamma^{-1})$ is the divisor of the polynomial

where $x^{\prime}=dx-by$ and $y^{\prime}=-cx+ay$. But this simplifies to

and the class of this polynomial in $R_{\textup{hom}}/k^{\times}$ is nothing other than $\Gamma([xh-yg])$. By (1), we see that (2) holds. ∎

In order for a rational function $F$ to have $\Phi(F)=D$, we must be able to write $F=g/h$ for two coprime elements $g,h\in R_{r}$, with $h$ monic, so that $\operatorname{div}(xh-yg)=D$. This holds if and only if $xh-yg=cp$ for some $c\in k^{\times}$.

Suppose we have $xh-yg=cp$ for such a $g$, $h$, and $c$, and suppose $p$ is not divisible by $y$. Then $h$ must also be coprime to $y$. Since $p$ and $h$ are both monic, it follows that the coefficient of $x^{r+1}$ in $p$, and the coefficient of $x^{r}$ in $h$, are both equal to $1$. Since the monomial $x^{r+1}$ does not occur in $yg$, it follows that $c=1$, so $g=(xh-p)/y$. Finally, we see that $h$ and $p$ can share no common factor other than $y$, because otherwise $h$ and $g$ would not be coprime. Conversely, if $h$ is a monic polynomial of degree $r$ that is coprime to $yp$, then $(xh-p)/(yh)$ is a degree-$r$ function with divisor of fixed points equal to $D$.

Now suppose $xh-yg=cp$ for such a $g$, $h$, and $c$, where $p$ is divisible by $y$. Then $h$ must also be divisible by $y$. But $p$ and $h$ cannot both be divisibly by $y^{2}$, for otherwise $g$ would be divisible by $y$, contradicting the requirement that $g$ and $h$ be coprime. Then $g=x(h/y)-c(p/y)$, and if $h$ and $p$ had any common factors other than $y$, this common factor would divide $g$ as well. Also, since $g$ must not be divisible by $y$, we see that $cp\not\equiv xh\bmod y^{2}$. Conversely, if $h$ is a monic polynomial of degree $r$ with $(h,p)=y$ and if $c\in k^{\times}$ satisfies $cp\not\equiv xh\bmod y^{2}$, then $(xh-cp)/(yh)$ is a degree-$r$ function with divisor of fixed points equal to $D$. ∎

Let $P$ be a degree-$n$ place whose Frobenius function is $F$ and let $f$ be the monic homogeneous polynomial whose divisor is $P$. Let $\alpha$ be a root of $f$, so that we have $[\alpha^{q}\,{:}\,1]=F([\alpha\,{:}\,1])$. Applying Frobenius to both sides, we find that

where the first equality follows from the fact that $F$ is ${\mathbf{F}}_{q}$-rational. Continuing in this way, we see that

It follows that $\alpha$ is a root of the function defining the divisor of fixed points for $G$, so the place $P$ appears in $\Phi(G)$. ∎

Suppose $P$ is a place of ${\mathbf{P}}^{1}\phantom{{\mathbf{F}}_{q}}\hbox to0.0pt{\hss$\mathchoice{\raisebox{-1.72218pt}{$\displaystyle\scriptstyle/{\mathbf{F}}_{q}$}}{\raisebox{-1.72218pt}{$\textstyle\scriptstyle/{\mathbf{F}}_{q}$}}{\raisebox{-1.72218pt}{$\scriptstyle\scriptstyle/{\mathbf{F}}_{q}$}}{\raisebox{-1.72218pt}{$\scriptscriptstyle\scriptstyle/{\mathbf{F}}_{q}$}}$}$ of odd degree $n>1$ whose Frobenius function $F$ has degree $1$. Since $F$ has degree $1$ we can view it as an element of $\operatorname{PGL}_{2}({\mathbf{F}}_{q})$. Let $f$ be the monic irreducible homogeneous polynomial in ${\mathbf{F}}_{q}[x,y]$ that defines $P$, and let $\alpha\in\overline{{\mathbf{F}}}_{q}$ be a root of $f$. Then for every $i\geq 0$ we have

so $F^{(i)}$ is not the identity for $0<i<n$. On the other hand, $F^{(n)}$ fixes $[\alpha\,{:}\,1]$ and all of its conjugates, so it must be the identity. In other words, as an element of $\operatorname{PGL}_{2}({\mathbf{F}}_{q})$, the function $F$ has order $n$.

An easy exercise shows that the set of orders of elements of $\operatorname{PGL}_{2}({\mathbf{F}}_{q})$ consists of the union of the prime divisor of $q$, the divisors of $q-1$, and the divisors of $q+1$. This proves the first statement of the theorem.

Let $P_{\infty}$ be the place of ${\mathbf{P}}^{1}\phantom{{\mathbf{F}}_{q}}\hbox to0.0pt{\hss$\mathchoice{\raisebox{-1.72218pt}{$\displaystyle\scriptstyle/{\mathbf{F}}_{q}$}}{\raisebox{-1.72218pt}{$\textstyle\scriptstyle/{\mathbf{F}}_{q}$}}{\raisebox{-1.72218pt}{$\scriptstyle\scriptstyle/{\mathbf{F}}_{q}$}}{\raisebox{-1.72218pt}{$\scriptscriptstyle\scriptstyle/{\mathbf{F}}_{q}$}}$}$ at infinity, let $P_{0}$ be the place at $0$, and let $P_{s}$ be the degree-$2$ place whose geometric points are $[s\,{:}\,1]$ and $[s^{q}\,{:}\,1]$, where $s$ is the element of ${\mathbf{F}}_{q^{2}}\setminus{\mathbf{F}}_{q}$ from the statement of the theorem. If the Frobenius function of a place $P$ has degree $1$, then the Frobenius divisor of $P$ has degree $2$. Every divisor of degree $2$ on ${\mathbf{P}}^{1}\phantom{{\mathbf{F}}_{q}}\hbox to0.0pt{\hss$\mathchoice{\raisebox{-1.72218pt}{$\displaystyle\scriptstyle/{\mathbf{F}}_{q}$}}{\raisebox{-1.72218pt}{$\textstyle\scriptstyle/{\mathbf{F}}_{q}$}}{\raisebox{-1.72218pt}{$\scriptstyle\scriptstyle/{\mathbf{F}}_{q}$}}{\raisebox{-1.72218pt}{$\scriptscriptstyle\scriptstyle/{\mathbf{F}}_{q}$}}$}$ is in the $\operatorname{PGL}_{2}({\mathbf{F}}_{q})$ orbit of exactly one of the following divisors: $D_{1}\colonequals 2P_{\infty}$, $D_{2}\colonequals P_{\infty}+P_{0}$, and $D_{3}\colonequals P_{s}$. Therefore, by Lemma 2.4 we may choose our orbit representatives for the action of $\operatorname{PGL}_{2}({\mathbf{F}}_{q})$ on the degree-$n$ places with Frobenius functions of degree $1$ to have one of these three divisors as their Frobenius divisors.

Consider the set $S_{1}$ of monic irreducible degree-$n$ homogenous polynomials $f$ that define places whose Frobenius divisors are equal to $D_{1}$. By Proposition 2.6, the functions $F$ with $\Phi(F)=D_{1}$ are the functions $x/y+r$ for $r\in{\mathbf{F}}_{q}$ with $r\neq 0.$ Every such function $F$ has order equal to the prime divisor of $q$, so in this case $n$ must be that prime.

The subgroup of $\operatorname{PGL}_{2}({\mathbf{F}}_{q})$ that stabilizes the set $S_{1}$ is the “$ax+b$” group — that is, the classes of the upper triangular matrices. We check that if $\alpha$ and $\beta$ are elements of ${\mathbf{F}}_{q^{n}}$ such that both $\alpha^{q}-\alpha$ and $\beta^{q}-\beta$ are nonzero elements of ${\mathbf{F}}_{q}$, then there is an element of this subgroup that takes $\alpha$ to $\beta$. Thus, all of the places with Frobenius divisors equal to $D_{1}$ are equivalent up to $\operatorname{PGL}_{2}({\mathbf{F}}_{q})$, and one of them is given by the divisor of the unique polynomial in the set $T$ given in the theorem in the case where $n$ is the prime divisor of $q$.

Now consider the set $S_{2}$ of monic irreducible degree-$n$ homogenous polynomials $f$ that define places whose Frobenius divisors are equal to $D_{2}$. By Proposition 2.6, the functions $F$ with $\Phi(F)=D_{2}$ are the functions $rx/y$ for $r\in{\mathbf{F}}_{q}$ with $r\neq 0$ and $r\neq 1$, so if $f$ is an element of $S_{2}$ and if $\alpha\in{\mathbf{F}}_{q^{n}}$ is a root of $f$, then $\alpha^{q}=r\alpha$ for some $r\in{\mathbf{F}}_{q}^{\times}$. Since $F\in\operatorname{PGL}_{2}({\mathbf{F}}_{q})$ has order $n$, the element $r$ of ${\mathbf{F}}_{q}^{\times}$ must also have order $n$, so $n\mid q-1$. Conversely, if $\alpha$ is an element of ${\mathbf{F}}_{q^{n}}^{\times}$ such that $\alpha^{q-1}$ has order $n$, then $\alpha$ defines a place with Frobenius divisor $D_{2}$. Since $n$ divides $q-1$, there are elements of ${\mathbf{F}}_{q^{n}}^{\times}$ of order $n(q-1)$; let $\omega$ be one of these. Then the $\alpha$ that give places of degree $n$ with Frobenius divisor $D_{1}$ are exactly the elements $\omega^{i}$ with $\gcd(i,n)=1$.

The subgroup of $\operatorname{PGL}_{2}({\mathbf{F}}_{q})$ that stabilizes the set $S_{2}$ consists of the classes of the diagonal and antidiagonal matrices. The action of this subgroup on the set $\{\omega^{i}\ |\ \gcd(i,n)=1\}$ is generated by multiplication by nonzero elements of ${\mathbf{F}}_{q}$ (which are exactly the powers of $\omega^{n}$) and by inversion. It is clear that the set ${\{\omega^{i}\ |\ 0<i<n/2,\ \gcd(i,n)=1\}}$ is a complete set of unique representatives for this action. The homogenized minimal polynomials of these elements are exactly the elements of the set $T$ given in the theorem in the case $n\mid q-1$.

Finally we consider the set $S_{3}$ of monic irreducible degree-$n$ homogenous polynomials $f$ that define places whose Frobenius divisors are equal to $D_{3}=P_{s}$. Let $p$ be the monic homogeneous polynomial that defines the place $P_{s}$, and write $p=x^{2}+axy+by^{2}$ for $a,b\in{\mathbf{F}}_{q}$. Now Proposition 2.6 tells us that the functions $F$ with $\Phi(F)=D_{3}$ are the functions of the form $F_{r}\colonequals((r-a)x-by)/(x+ry)$ for $r\in{\mathbf{F}}_{q}$.

Given an $\alpha\in{\mathbf{F}}_{q^{n}}$ with $\alpha^{q}=((r-a)\alpha-b)/(\alpha+r)$, set $\beta=(s^{q}-\alpha)/(\alpha-s)$, so that $\beta\in{\mathbf{F}}_{q^{2n}}$ and $\alpha=(s\beta+s^{q})/(\beta+1)$. Note that then

and more generally

Since $\alpha^{q^{n}}=\alpha$ and $n$ is odd, we find that

so that $\beta^{-q^{n}}=\beta$. Then (3) shows that $c\colonequals(r+s^{q})/(r+s)\in{\mathbf{F}}_{q^{2}}$ has order $n$. It is also clear that the norm of $c$ from ${\mathbf{F}}_{q^{2}}$ to ${\mathbf{F}}_{q}$ is $1$, so its order divides $q+1$, and we see that $n\mid q+1$. Since $\beta^{q+1}=c$, we see that the $\beta$ has order dividing $n(q+1)$, so that $\beta$ is a power of the element $\xi\in{\mathbf{F}}_{q^{2n}}$ chosen in the statement of the theorem. Furthermore, if we write $\beta=\xi^{i}$, then we must have $\gcd(i,n)=1$, for otherwise $\beta^{q+1}$ would not have order $n$. On the other hand, we check that if we set $\alpha=(s\xi^{i}+s^{q})/(\xi^{i}+1)$ for an integer $i$ with $\gcd(i,n)=1$, then we have

where

Using the fact that $\xi$ has order $n(q+1)$ and that $n\mid q+1$ we see that $\xi^{q^{2}+q}\cdot\xi^{q+1}=1$, and from this we calculate that $r^{q}=r$, so that $r\in{\mathbf{F}}_{q}$. Thus, the place associated to this $\alpha$ has Frobenius divisor equal to $D_{3}$.

We calculate that the subgroup of $\operatorname{PGL}_{2}({\mathbf{F}}_{q})$ that stabilizes the set $S_{3}$ is generated by the classes of the matrices $M_{u}\colonequals\bigl{[}\begin{smallmatrix}u-a&-b\\ 1&\phantom{-}u\end{smallmatrix}\bigr{]}$ (which fix $s$ and $s^{q}$) and the matrix $N\colonequals\bigl{[}\begin{smallmatrix}-1&-a\\ \phantom{-}0&\phantom{-}1\end{smallmatrix}\bigr{]}$ (which swaps $s$ and $s^{q}$).

Suppose $\alpha$ and $\beta$ are as above, set $\alpha^{\prime}\colonequals M_{u}(\alpha)$, and let $\beta^{\prime}=(s^{q}-\alpha^{\prime})/(\alpha^{\prime}-s)$. We check that $\beta^{\prime}=(u+s)/(u+s^{q})\beta.$ Since $(u+s)/(u+s^{q})$ is an element of ${\mathbf{F}}_{q^{2}}$ whose norm to ${\mathbf{F}}_{q}$ is $1$, we see that it is a power of $\xi^{n}$. Therefore, if we write $\beta=\xi^{i}$ and $\beta^{\prime}=\xi^{i^{\prime}}$, then $i^{\prime}\equiv i\bmod n$. Likewise, if we let $\alpha^{\prime}=N(\alpha)$ and $\beta^{\prime}=(s^{q}-\alpha^{\prime})/(\alpha^{\prime}-s)$, then $\beta^{\prime}=1/\beta$, so if we write $\beta=\xi^{i}$ and $\beta^{\prime}=\xi^{i^{\prime}}$, then $i^{\prime}\equiv-i\bmod n(q+1)$. From this we see that the set $\{\xi^{i}\ |\ 0<i<n/2,\ \gcd(i,n)=1\}$ is a complete set of unique representatives for the action of the stabilizer of $S_{3}$ on the set of $\beta$s, so the set

is a complete set of unique representatives for the action of the stabilizer of $S_{3}$ on the set of $\alpha$s whose associated places have Frobenius divisor $D_{3}$. The theorem follows. ∎