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 of order and polynomials of degrees respectively, there is the continued fraction representation . Let denote the number of such pairs for which and for . We give both an exact recurrence relation, and an asymptotic analysis, for . The polynomial associated with the recurrence relation turns out to be of P-V type. We also study the distribution of . Averaged over all and as above, this presents no difficulties. The average value of is , and there is full information about the distribution. When is fixed and only is allowed to vary, we show that this is still the average. Moreover, few pairs give a value of that differs from this average by more than

**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

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