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 ns and ks. 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: ,

One Response to “A Favorite Theorem”

  1. Samuel Vidal Says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: