A Favorite Theorem

The other day I was hanging out with some math folk, and one asked the group what our favorite theorems are. A tough question, clearly, since there are soo many fantastic theorems to choose from. For me, there’s a place in my heart for slightly esoteric theorems. They should be surprising and seem to come from basically nowhere (unless you’ve been looking at the subject, perhaps). They should be fairly easy to state… possibly with a few minutes introduction of some easy definitions or results. And I seem to have taken up thinking that continued fractions are pretty cool. With that in mind, I present one of my favorite theorems:

Theorem: There is a constant, $K$ , such that for almost all $\alpha$ in $(0,1)$ , if the continued fraction representation of $\alpha$ is $[0;a_1,a_2,\ldots]$ , then $\sqrt[n]{a_1\cdots a_n}\to K$ as $n\to\infty$ .

It turns out the constant, dubbed Khinchin’s constant, is $K\approx 2.685$ , according to Wikipedia anyway. An exact expression for $K$ is

$\displaystyle K=\prod_{r=1}^{\infty}\left(1+\frac{1}{r(r+2)}\right)^{\log_2(r)}.$

I’d like to try to give some very brief background on this theorem, along with the “few minutes introduction of some easy definitions and results”.

I should mention, first, that I take Khinchin’s book “Continued Fractions” as my primary reference. Hardy and Wright also have some chapters on continued fractions. And, of course, there’s Wikipedia.

Let’s begin with the process of constructing the continued fraction for an $\alpha\in (0,1)$ . I’ll take $\alpha$ irrational, for convenience. Since $0<\alpha<1$ , we have $1<1/\alpha$ , and we let $a_1$ be the largest integer less than $1/\alpha$ , denoted $\lfloor 1/\alpha\rfloor$ , and we know that $a_1\geq 1$ . That leaves a little bit over, which I’ll denote $z_1=(1/\alpha)-a_1\in (0,1)$ . We have $\alpha=1/(a_1+z_1)$ , the first step in our continued fraction. You now iterate this process, looking at $1/z_1$ , setting $a_2=\lfloor 1/z_1\rfloor$ and $z_2=(1/z_1)-a_2$ , and obtaining

$\displaystyle \alpha=\cfrac{1}{a_1+\cfrac{1}{a_2+z_2}}.$

Since I picked $\alpha$ irrational, this process keeps going – you keep getting $a_n$ (all positive integers) and $z_n$ (all in $(0,1)$ ). And then instead of writing huge nested fractions, you trim it down to $\alpha=[0;a_1,a_2,\ldots]$ . That initial zero is just becuase I started with $\alpha\in (0,1)$ , you could instead let $a_0=\lfloor \alpha'\rfloor$ , if you started with an $\alpha'$ outside $(0,1)$ . I’ll continue assuming my values are in $(0,1)$ , so I’ll frequently just write $[a_1,a_2,\ldots]$ , dropping the initial zero.

This process gives us, for every $\alpha\in(0,1)$ , a sequence of values $a_1,a_2,a_3,\ldots$ . Restated, we have functions $a_n$ (and $z_n$ as well) from $(0,1)$ to positive integers. To start getting at Khinchin’s constant, you think about combinations of $a_n^{-1}(k)$ , for collections of $n$ s and $k$ s. That is, given $n_1,n_2,\ldots,n_s$ and $k_1,k_2,\ldots,k_s$ , all positive integers, what does the set of all $\alpha=[a_1,a_2,\ldots]$ such that $a_{n_i}=k_i$ for $i=1,\ldots,s$ look like?

Let’s start with $a_1$ , since it is the easiest. What does $a_1^{-1}(k)$ look like? Well, $a_1(\alpha)=k$ means that $\lfloor 1/\alpha\rfloor=k$ . Which is to say, $k\leq 1/\alpha<k+1$ , or $1/(k+1)<\alpha\leq 1/k$ . So the graph of $a_1(x)$ is a step function, taking the value $k$ on the interval $(1/(k+1),1/k]$ . I picture this as a staircase descending as you move to the right. Of course, the stairs are pretty narrow on the left…

As an example, $a_1^{-1}(3)$ is $(1/4,1/3]$ , the third stair from the right.

Now, on to $a_2$ . What does $a_2^{-1}(k)$ look like? Well, in finding the continued fraction for $\alpha$ , we find first $\alpha=1/(a_1+z_1)$ , and if $a_2(\alpha)=k$ then $\lfloor 1/z_1\rfloor =k$ , or $1/(k+1)<z_1<1/k$ . So we find that for any $a_1$ , all values between $1/(a_1+1/k)$ and $1/(a_1+1/(k+1))$ have $a_2=k$ . That is, in each of the “stairs” from the discussion of $a_1$ , the graph of $a_2$ has another staircase, this time ascending as you move from left to right.

For example, $a_2^{-1}(2)$ comprises, in the ascending staircases in each interval $(1/(k+1),1/k]$ , the second stair from the left. It is an infinite collection of intervals. If you also ask about those where $a_1$ is some constant, you pick out a single subinterval.

So we’ve got at least a little idea about how these functions $a_n$ work. Given $n_1,\ldots,n_s$ and $k_1,\ldots,k_s$ as above, the set of all $\alpha$ with $a_{n_i}=k_i$ will be an infinite collection of subintervals of $(0,1)$ . Next you could ask, what is the measure (sum of lengths of intervals) of this set? I’ll mostly talk about the case when $s=1$ , $n_1=n$ , and $k_1=k$ . I’ll denote the set of appropriate $\alpha$ by $E\binom{n}{k}$ , and the measure of that set by $\mathcal{M}\binom{n}{k}$ .

Apparently Gauss had a go at questions like this. He defined $m_n(x)$ to be the measure of the set of all $\alpha$ such that $z_n(\alpha)<x$ , and found that

$\displaystyle \lim_{n\to\infty} m_n(x)=\frac{\ln(1+x)}{\ln 2}.$

Crazy (brilliant) old Gauss (who apparently had an awesome signature). Khinchin suggests that Gauss probably arrived at this result based on a recurrence relation (functional equation, if you’d rather) among the $m_i$ . I’ll let you read about it in Khinchin’s book. Anyway, in 1928, Kuz’min came along and found a generalization. Kuz’min’s theorem gives a more precise result than Gauss’ (at least, as stated above). Namely:

Theorem: There are positive constants, $A$ and $\lambda$ , such that

$\displaystyle \left|m_n'(x)-\frac{1}{(1+x)\ln 2}\right|<Ae^{-\lambda\sqrt{n}}.$

On integrating and taking limits, we obtain Gauss’ result. Alternatively, using the relation

$\displaystyle \mathcal{M}\binom{n}{k}=m_{n-1}(\tfrac{1}{k})-m_{n-1}(\tfrac{1}{k+1})=\int_{1/(k+1)}^{1/k}m_{n-1}'(x)\ dx,$

one can also obtain

$\displaystyle \left|\mathcal{M}\binom{n}{k}-\log_2\left(1+\frac{1}{k(k+2)}\right)\right| < \frac{A}{k(k+1)}e^{-\lambda\sqrt{n-1}}.$

Or, taking limits,

$\displaystyle \lim_{n\to\infty} \mathcal{M}\binom{n}{k}=\log_2\left(1+\frac{1}{k(k+2)}\right).$

This, by itself, seems pretty interesting. I find it a hard limit to interpret. After all, $E\binom{n}{k}$ and $E\binom{n+1}{k}$ have nothing to do with eachother, so the measure that we are calculating is of a completely different set with each $n$ . If, instead, we were taking measures of a sequence of nested subsets, or something, I feel like I could get a better handle on this theorem. But we’re not. If anybody has a nice interpretation of this limit, I’d love to hear it.

Anyway, it’s about time for Khinchin’s theorem:

Theorem: If $f$ is a function from positive integers to positive reals such that $f(r)<C\cdot r^{\frac{1}{2}-\delta}$ for some positive constants $C$ and $\delta$ , then for almost every $\alpha=[a_1,a_2,\ldots]$ in $(0,1)$ ,

$\displaystyle \lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{\infty}f(a_k)=\sum_{r=1}^{\infty}f(r)\log_2\left(1+\frac{1}{r(r+2)}\right).$

Khinchin’s constant is obtained from the case when $f(r)=\ln(r)$ , simply messing with the equality using log and exponent rules.

Another interesting case is when you take $f(r)=1$ if $r=\ell$ and 0 otherwise. Then the limit on the left of the equality in Khinchin’s theorem should be interpreted as the density of $\ell$ among the values of the $a_n$ in the continued fraction for $\alpha$ . The expression on the right in the equality simplifies to a single term, instead of an infinite series. For example, with $\ell=1$ we find that approximately 42% of the terms (Khinchin calls them “elements”) in the continued fraction for just about any $\alpha$ you pick will be 1. Khinchin summarizes the result:

“Thus, an arbitrary natural number occurs as an element in the expansion of almost all numbers with equal average frequency.”

Pretty awesome. Pick a positive integer. Pick any $\alpha$ you want (pick several!). Find all of the elements in the continued fraction for $\alpha$ , and the percentage that are your chosen integer (it will be a positive percentage!). You’ll get the same percentage for all of the $\alpha$ you pick. Unless, of course, you have terrible luck (or are malicious) in picking $\alpha$ . When you’re done with all of that, you might check, as a fun little algebra exercise, that the sum of all of the expected densities, over all choices of $\ell$ , is 1, as it should be.

There are a few other interesting results like this. For some reason I have a harder time remembering them, and so they didn’t get to be my favorite theorem. But they’re just as cool, really.

For the first, I should remind you that the $n$ -th convergent for a continued fraction $[a_1,\ldots]$ is the fraction $[a_1,\ldots,a_n]$ . As this is a finite continued fraction, it represents a rational number, and it is typically denoted $p_n/q_n$ (relatively prime). The growth of the denominators in the sequence of convergents in a continued fraction is a fairly worthwhile question. Using some elementary relationships among the $a_i$ and $q_i$ , you can find that $a_1\cdots a_n<q_n<2^na_1\cdots a_n$ . The interesting theorem I have in mind is another “there is a constant” theorem:

Theorem: For almost all $\alpha=[a_1,\ldots]$ ,

$\displaystyle \lim_{n\to \infty}\sqrt[n]{q_n}=e^{\pi^2/(12\ln 2)}.$

This constant gets called the Lévy-Khinchin constant on Wikipedia.

Another interesting result, which I stumbled across while preparing a talk about some of these things, is called Lochs’ theorem. I know even less about this than the previous theorems (it isn’t in Khinchin’s book), but apparently it basically says that each time you find a new $a_n$ , in the process of finding the continued fraction for $\alpha$ , the convergent has one better decimal place of accuracy than the previous convergent. So continued fractions are just as expressive as decimals. They just don’t add together quite so easily 🙂

So anyway, what’s your favorite theorem?

Tags: continued fraction, khinchin

This entry was posted on November 30, 2009 at 11:53 pm and is filed under Play. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “A Favorite Theorem”

Samuel Vidal Says:
May 12, 2012 at 8:11 pm | Reply
Very great post ! Thank you for taking the time.
To answer the question: My favorite theorem depends on what excites me at the moment. For the moment I’m fascinated with umbral calculus 😉 this is why I came to this blog in the first place.

In the field of continued fraction my favorite theorem in date is the fiendishly clever Gosper algorithm to add, multiply, subtract, divide two numbers in continuous fraction representation, all the operations comes from the same insight… really clever.

∑idiot's Blog