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 Free Access

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 (Papers in Honor of Edmund Landau), Plenum, New York, 1969, pp. 87–96. MR 0258760
  • 2. Douglas Hensley, The largest digit in the continued fraction expansion of a rational number, Pacific J. Math. 151 (1991), no. 2, 237–255. MR 1132388
  • 3. Loo Keng Hua and Yuan Wang, Applications of number theory to numerical analysis, Springer-Verlag, Berlin-New York; Kexue Chubanshe (Science Press), Beijing, 1981. Translated from the Chinese. MR 617192
  • 4. Arnold Knopfmacher, The length of the continued fraction expansion for a class of rational functions in 𝐹_{𝑞}(𝑋), Proc. Edinburgh Math. Soc. (2) 34 (1991), no. 1, 7–17. MR 1093172, 10.1017/S001309150000496X
  • 5. Harald Niederreiter, Rational functions with partial quotients of small degree in their continued fraction expansion, Monatsh. Math. 103 (1987), no. 4, 269–288. MR 897953, 10.1007/BF01318069
  • 6. Harald Niederreiter, The probabilistic theory of linear complexity, Advances in cryptology—EUROCRYPT ’88 (Davos, 1988) Lecture Notes in Comput. Sci., vol. 330, Springer, Berlin, 1988, pp. 191–209. MR 994663, 10.1007/3-540-45961-8_17

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
Email: friesen.4@osu.edu

Doug Hensley
Affiliation: Department of Mathematics, Texas A& M University, College Station, Texas 77843
Email: doug.hensley@math.tamu.edu

DOI: https://doi.org/10.1090/S0002-9939-96-03394-1
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