3
$\begingroup$

Does a notion of Farey sequence (or something equivalent) exist for polynomials over finite fields?

1 Answers 1

3

The terms in the Farey sequence exhaust the rationals, which form a field. The polynomials over a field don't form a field. The terms in a Farey sequence are listed in increasing order. The polynomials over a field don't have a natural order. So it's hard to think what properties you are expecting such a sequence to have.

I suppose you could do this. For the field of $p$ elements, the "Farey sequence" of order $n$ could be all the polynomials of degree at most $n$, ordered by increasing value when evaluated at $1/p$. The coefficients would be restricted to the range 0 to $p-1$. E.g., there are 27 polynomials of degree at most 2 over the field of 3 elements: $0,1,2,x,x+1,x+2,2x,2x+1,2x+2,x^2,x^2+1,x^2+2,x^2+x,x^2+x+1,x^2+x+2,x^2+2x,x^2+2x+1,x^2+2x+2, 2x^2,2x^2+1,2x^2+2,2x^2+x,2x^2+x+1,2x^2+x+2,2x^2+2x,2x^2+2x+1,2x^2+2x+2.$ You can evaluate each of these at $x=1/3$, getting 27 different numbers, which you could then put in increasing order, and then you could order the polynomials accordingly. Doesn't look very exciting.

EDIT: I'm surprised to find that there is a paper by William Webb, titled The Farey series of polynomials over a finite field. The citation is Elem. Math. 41 (1986), no. 1, 6–11, MR0880238 (88j:11086). The review begins,

Denote by $R$ the ring of polynomials in $X$ with coefficients in the field of $q$ elements. The Farey series of order $n$ for $R$ is denoted $F_n$ and defined by $F_n=\{{P/Q:P,Q\in R,\deg P\lt\deg Q\le n,(P,Q)=1,Q{\rm\ monic}\}}$ The author develops the elementary theory of $F_n$ along the lines of that of the classical Farey series.

What I find most surprising is that I wrote that review.

  • 0
    @Mark, what Webb does exhausts the rational functions with numerator of lower degree than denominator, much as the usual Fareys exhaust the (positive) rationals with numerator less than denominator.2012-07-23