Gauss-Kuzmin-Wirsing Constant

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.

Let $x_0$ be a random number from $[0,1]$ written as a simple Continued Fraction

$$x_0=0+{1\over a_1+{\strut\displaystyle 1\over\strut\displays... ...+{\strut\displaystyle 1\over\strut\displaystyle a_3+\ldots}}}.$$ (1)

Define

$$x_n = 0+{1\over\strut\displaystyle a_{n+1}+{\strut\displaystyle 1\over\... ...ystyle a_{n+2}+{\strut\displaystyle 1\over\strut\displaystyle a_{n+3}+\ldots}}}$$

$$= {1\over x_{n-1}}-\left\lfloor{1\over x_{n-1}}\right\rfloor .$$ (2)

Gauß (1800) showed that if $F(n,x)$ is the probability that $x_n<x$, then

$$\lim_{n\to\infty} F(n,x)={\ln(1+x)\over\ln 2}.$$ (3)

Kuzmin (1928) published the first proof, which was subsequently improved by Lévy (1929). Wirsing (1974) showed, among other results, that

$$\lim_{n\to\infty} {F(n,x)-{\ln(1+x)\over\ln 2}\over (-\lambda)^n}=\Psi(x),$$ (4)

where $\lambda=0.3036630029\ldots$ and $\Psi(x)$ is an analytic function with $\Psi(0)=\Psi(1)=0.$ This constant is connected to the efficiency of the Euclidean Algorithm (Knuth 1981).

References

Babenko, K. I. ``On a Problem of Gauss.'' Soviet Math. Dokl. 19, 136-140, 1978.

Daudé, H.; Flajolet, P.; and Vallée, B. ``An Average-Case Analysis of the Gaussian Algorithm for Lattice Reduction.'' Submitted.

Durner, A. ``On a Theorem of Gauss-Kuzmin-Lévy.'' Arch. Math. 58, 251-256, 1992.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/kuzmin/kuzmin.html

Flajolet, P. and Vallée, B. ``On the Gauss-Kuzmin-Wirsing Constant.'' Unpublished memo. 1995. http://pauillac.inria.fr/algo/flajolet/Publications/gauss-kuzmin.ps.

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1981.

MacLeod, A. J. ``High-Accuracy Numerical Values of the Gauss-Kuzmin Continued Fraction Problem.'' Computers Math. Appl. 26, 37-44, 1993.

Wirsing, E. ``On the Theorem of Gauss-Kuzmin-Lévy and a Frobenius-Type Theorem for Function Spaces.'' Acta Arith. 24, 507-528, 1974.