Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



The statistics of continued fractions
for polynomials over a finite field

Authors: Christian Friesen and Doug Hensley
Journal: Proc. Amer. Math. Soc. 124 (1996), 2661-2673
MSC (1991): Primary 11A55
MathSciNet review: 1328349
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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}).$

References [Enhancements On Off] (What's this?)

  • 1. H. Heilbronn, On the average length of a class of finite continued fractions, Number Theory and Analysis, Plenum Press, New York, 1969, pp. (87--96). MR 41:3406
  • 2. D. Hensley, The largest digit in the continued fraction expansion of a rational number, Pacific Jour. Math. 151 (1991), 237--255. MR 92i:11009
  • 3. L. K. Hua and Y. Wang, Applications of Number Theory to Numerical Analysis, Springer, Berlin, 1981. MR 83g:10034
  • 4. A. Knopfmacher, The length of the continued fraction expansion for a class of rational functions in ${\mathcal {F} }_q (X)$, Proc. Edinburgh Math. Soc. 34 (1991), 7--17. MR 92c:11144
  • 5. H. Niederreiter, Rational functions with partial quotients of small degree in their continued fraction expansion, Monatshefte Math. 103 (1987), 269--288. MR 88h:12002
  • 6. H. Niederreiter, The probabilistic theory of linear complexity, Advances in Cryptology-EURO-
    CRYPT '88, Lecture Notes in Computer Science, vol. 330, Springer, Berlin, 1988. MR 90d:11138

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (1991): 11A55

Retrieve articles in all journals with MSC (1991): 11A55

Additional Information

Christian Friesen
Affiliation: Department of Mathematics, Ohio State University, Marion Campus, Marion, Ohio 43302

Doug Hensley
Affiliation: Department of Mathematics, Texas A& M University, College Station, Texas 77843

Received by editor(s): August 20, 1994
Received by editor(s) in revised form: March 27, 1995
Communicated by: William W. Adams
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society