The statistics of continued fractions for polynomials over a finite field
HTML articles powered by AMS MathViewer
- by Christian Friesen and Doug Hensley
- Proc. Amer. Math. Soc. 124 (1996), 2661-2673
- DOI: https://doi.org/10.1090/S0002-9939-96-03394-1
- PDF | Request permission
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
- 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 258760
- 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, DOI 10.2140/pjm.1991.151.237
- 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, DOI 10.1007/978-3-642-67829-5
- Arnold Knopfmacher, The length of the continued fraction expansion for a class of rational functions in $\textbf {F}_q(X)$, Proc. Edinburgh Math. Soc. (2) 34 (1991), no. 1, 7–17. MR 1093172, DOI 10.1017/S001309150000496X
- 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, DOI 10.1007/BF01318069
- 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, DOI 10.1007/3-540-45961-8_{1}7
Bibliographic 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
- Received by editor(s): August 20, 1994
- Received by editor(s) in revised form: March 27, 1995
- Communicated by: William W. Adams
- © Copyright 1996 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 124 (1996), 2661-2673
- MSC (1991): Primary 11A55
- DOI: https://doi.org/10.1090/S0002-9939-96-03394-1
- MathSciNet review: 1328349