THE STATISTICS OF CONTINUED FRACTIONS FOR POLYNOMIALS OVER A FINITE-FIELD

Given a finite held F of order q and polynomials a, b is an element of F[X] of degrees m < n respectively, there is the continued fraction r epresentation b/a = a(1) + 1/(a(2) + 1/(a(2) + 1/a(3) + ... + 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 less than or equal to j less than or equal to r, deg a(j) less than or equal to k. We give both an exact recurrence re lation, and an asymptotic analysis, for CF(n, k, q). The polynomial as sociated 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), a nd there is full information about the distribution. When b is fixed a nd 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 b y more than O(root n/q).