The Farey series of polynomials over a finite field (Q1074633)

The Farey series \(F_ n\) for the finite field \(\mathrm{GF}(p^ r)\) is defined as the set of all rational functions \(P/Q\) over \(\mathrm{GF}(p^ r)\) with \(\deg (P)<\deg (Q)\leq n\), \(\gcd (P,Q)=1\), and \(Q\) monic. Let \(|\cdot |\) be the usual degree valuation of the field of formal Laurent series in \(x^{-1}\) over \(\mathrm{GF}(p^ r)\) and let \(I\) be the corresponding valuation ideal. If \(P/Q\in F_ n\), then an element \(H/K\neq P/Q\) in \(F_ n\) with \(\deg (K)=k\) is called a \(k\)-neighbor of \(P/Q\) if \(| P/Q-H/K| \leq | P/Q-H'/K'|\) for all H'/K' with \(\deg (K')=k\). The elements \(P/Q\) and \(H/K\) of \(F_ n\) with \(\deg (Q)=q\) and \(\deg (K)=k\) are called neighbors if \(P/Q\) is a \(q\)-neighbor of \(H/K\) and \(H/K\) is a \(k\)-neighbor of \(P/Q\). It is shown that \(P_ 1/Q_ 1\) and \(P_ 2/Q_ 2\) in \(F_ n\) are neighbors if and only if \(\deg (P_ 1Q_ 2-P_ 2Q_ 1)=0\). Furthermore, \(P/Q\in F_ n\) with \(\deg (Q)=q\) has exactly \((p^ r-1)p^{rt}\) neighbors with denominators of degree \(q+t\) for \(t\geq 0\) and exactly one neighbor with denominator of degree \(<q\). It is also proved that if \(\alpha\in I\) and \(n\) are given, then there exists a \(P/Q\in F_ n\) such that \[ | \alpha -P/Q| \leq p^{-r(n+1+\deg (Q))}. \] It should be noted that this analog of Dirichlet's approximation theorem follows immediately by considering the continued fraction expansion of \(\alpha\) and letting \(P/Q\) be a suitable convergent to \(\alpha\).