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

As we know, Gauss wrote that $$\lim_{n \rightarrow \infty} \lambda \left(\tau^n \leq x\right) = \frac{\log(1+x)}{\log2}, \quad 0 \leq x < 1,$$ 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 $$\tau (x) = \frac{1}{x}-\left\lfloor \displaystyle \frac{1}{x} \right\rfloor, x \neq 0$$ 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!

-
Subjective and argumentative, voting to close. –  Igor Rivin Nov 21 '11 at 14:17
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. –  KConrad Nov 21 '11 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. –  David Speyer Nov 21 '11 at 18:11
Important to whom? Interesting in what sense? –  Yemon Choi Nov 21 '11 at 21:41

## 2 Answers

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).

-