The statistics of continued fractions for polynomials over a finite field

Abstract:

Given a finite field $F$ of order $q$ and polynomials $a,b\in F[X]$ of degrees $m<n$ respectively, there is the continued fraction representation $b/a=a_1+1/(a_2+1/(a_3+\dots +1/a_r))$. Let $CF(n,k,q)$ denote the number of such pairs for which $\deg b=n, \deg a<n,$ and for $1\le j\le r,$ $\deg a_j \le k$. We give both an exact recurrence relation, and an asymptotic analysis, for $CF(n,k,q)$. The polynomial associated with the recurrence relation turns out to be of P-V type. We also study the distribution of $r$. Averaged over all $a$ and $b$ as above, this presents no difficulties. The average value of $r$ is $n(1-1/q)$, and there is full information about the distribution. When $b$ is fixed and only $a$ is allowed to vary, we show that this is still the average. Moreover, few pairs give a value of $r$ that differs from this average by more than $O(\sqrt {n/q}).$