The statistics of continued fractions for polynomials over a finite field
Authors:
Christian Friesen and Doug Hensley
Journal:
Proc. Amer. Math. Soc. 124 (1996), 26612673
MSC (1991):
Primary 11A55
MathSciNet review:
1328349
Fulltext 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 PV 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
(41 #3406)
 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
(92i:11009)
 3.
Loo
Keng Hua and Yuan
Wang, Applications of number theory to numerical analysis,
SpringerVerlag, BerlinNew York; Kexue Chubanshe (Science Press), Beijing,
1981. Translated from the Chinese. MR 617192
(83g:10034)
 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 (92c:11144), http://dx.doi.org/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
(88h:12002), http://dx.doi.org/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
(90d:11138), http://dx.doi.org/10.1007/3540459618_17
 1.
 H. Heilbronn, On the average length of a class of finite continued fractions, Number Theory and Analysis, Plenum Press, New York, 1969, pp. (8796). MR 41:3406
 2.
 D. Hensley, The largest digit in the continued fraction expansion of a rational number, Pacific Jour. Math. 151 (1991), 237255. 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 , Proc. Edinburgh Math. Soc. 34 (1991), 717. MR 92c:11144
 5.
 H. Niederreiter, Rational functions with partial quotients of small degree in their continued fraction expansion, Monatshefte Math. 103 (1987), 269288. MR 88h:12002
 6.
 H. Niederreiter, The probabilistic theory of linear complexity, Advances in CryptologyEURO
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
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:
http://dx.doi.org/10.1090/S0002993996033941
PII:
S 00029939(96)033941
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
