# Gauss-Kuzmin Theorem (continued fractions) - why is important?

As we know, Gauss wrote that \begin{equation} \lim_{n \rightarrow \infty} \lambda \left(\tau^n \leq x\right) = \frac{\log(1+x)}{\log2}, \quad 0 \leq x < 1, \end{equation} with $\lambda$ is Lebesgue measure and the map $\tau : [0, 1) \rightarrow [0, 1)$, the so-called regular continued fraction or Gauss transformation, is defined by \begin{equation} \tau (x) = \frac{1}{x}-\left\lfloor \displaystyle \frac{1}{x} \right\rfloor, x \neq 0 \end{equation} and $\tau (x) = 0$, where $\left\lfloor \cdot \right\rfloor$ denotes the floor (or entire) function.

My question is "Why this theorem is important?" I am interested of a non-trivial and interesting explanation.

Thank you!

• This kind of theorem is important for understanding the statistical properties of the entries in (regular) continued fractions, which are quite different from the properties of decimal digits. The point is that the Gauss map, which is essentially a shift map on entries in continued fraction expansions, does not have Lebesgue measure as a measure-preserving transformation, but the measure (1/log 2)dx/(1+x) is a m.p.t. for the Gauss map. If you care about understanding patterns in continued fraction expansions then this theorem is important to you; if you don't care then forget about it. Nov 21, 2011 at 17:02
• The standard application is to compute the expected running time of the Euclidean algorithm. See Knuth, Art of Computer Programming, Volume 2. Nov 21, 2011 at 18:11
• Important to whom? Interesting in what sense? Nov 21, 2011 at 21:41

Well here is one answer: The study of the Gauss-Kuzmin problem eventually led to a fruitful connection between continued fractions and functional analysis. Namely, the distribution function of the Gauss measure is the leading eigenfunction for the transfer operator associated to the Gauss transformation. It turns out that this is the hidden explanation for the theorem you quoted in your question.

Understanding this connection recently led to a detailed study of transfer operators of the Gauss map and related transformations, and their associated Dirichlet series, which paved the way for major breakthroughs by Baladi, Vallee, and others, in understanding the statistics of the Euclidean algorithm and its various analogues. It would be difficult to give more details than this without writing a very long post, but if you are interested in finding out more then here are two references:

1) "Euclidean algorithms are Gaussian", Baladi and Vallee, available on Viviane Baladi's webpage.

2) "Continued fractions", Doug Hensley, Chapter 9.

If you can solve some problem using continued fraction then (via Gauss-Kuz'min statistics) you can study this problem from statistical point of view.

Some simplest examples are:

(i) Fast variants of Euclidean algorithm. The length of "neaest integer" continued fraction and "odd" continued fractions can be expressed in terms of Gauss-Kuz'min statistics for classical continued fractions. Corrolary: formula for the average length of such fractions (and corresponding Euclidean algorithms).

(ii) (Almost the same as (i).) Lattice reduction. Gauss-Kuz'min statistics give you average distribution of 2-dimensional rediced bases.

(iii) Distribution of Frobenius numbers. The simplest way to find Frobenius number with three arguments is to use Rodseth's formula. It expresses Frobenius number in terms of some continued fraction. Gauss-Kuz'min statistics give you average behaviour of Frobenius numbers.

Why do we need Gauss-Kuz'min statistics? (A talk given at the conference «Diophantine approximation: state of the art and applications», Minsk, 2011).

Kuzmin's proof seems to be really important.

1. The rate of convergence leads to mixing properties of the Gauss map. c.f. the paper 'Some metrical theorems in number theory'.

2. The proof is really interesting in its own right. Any sequence of nice functions $$f_n$$ on the unit interval satisfying the functional equation $$f_{n+1}(x) = \sum^\infty_{k=1} \frac{1}{(k+x)^2}f_n\left(\frac{1}{k+x}\right)$$ must converge exponentially fast to a constant times the density $$\frac{1}{1+x}$$. See the book of Khintchine on continued fractions for a discussion of this.