Rational functions with partial quotients of small degree in their continued fraction expansion (Q1092113): Difference between revisions

For a rational function \(f/g=f(x)/g(x)\) over a field \(F\) with \(\gcd (f,g)=1\) and \(\deg(g)\geq 1\) let \(K(f/g)\) be the maximum degree of the partial quotients in the continued fraction expansion of \(f/g\). For \(f\in F[x]\) with \(\deg (f)=k\geq 1\) and \(f(0)\neq 0\) put \(L(f)=K(f(x)/x^k)\). It is shown by an explicit construction that for every integer \(b\) with \(1\leq b\leq k\) there exists an \(f\) with \(L(f)=b\). If \(F=\mathbb F_2\), the binary field, then for every \(k\) there is exactly one \(f\in\mathbb F_2[x]\) with \(\deg (f)=k\), \(f(0)\neq 0\), and \(L(f)=1\). If \(\mathbb F_q\) is the finite field with \(q\) elements and \(g\in\mathbb F_q[x]\) is monic of degree \(k\geq 1\), then there exists a monic irreducible \(f\in\mathbb F_q[x]\) with \(\deg (f)=k\), \(\gcd (f,g)=1\), and \(K(f/g)<2+2(\log k)/\log q,\) where the case \(q=k=2\) and \(g(x)=x^2+x+1\) is excluded. An analogous existence theorem is also shown for primitive polynomials over finite fields. These results have applications to pseudorandom number generation.