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, , such that for almost all
in
, if the continued fraction representation of
is
, then
as
.
It turns out the constant, dubbed Khinchin’s constant, is , according to Wikipedia anyway. An exact expression for
is
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 . I’ll take
irrational, for convenience. Since
, we have
, and we let
be the largest integer less than
, denoted
, and we know that
. That leaves a little bit over, which I’ll denote
. We have
, the first step in our continued fraction. You now iterate this process, looking at
, setting
and
, and obtaining
Since I picked irrational, this process keeps going – you keep getting
(all positive integers) and
(all in
). And then instead of writing huge nested fractions, you trim it down to
. That initial zero is just becuase I started with
, you could instead let
, if you started with an
outside
. I’ll continue assuming my values are in
, so I’ll frequently just write
, dropping the initial zero.
This process gives us, for every , a sequence of values
. Restated, we have functions
(and
as well) from
to positive integers. To start getting at Khinchin’s constant, you think about combinations of
, for collections of
s and
s. That is, given
and
, all positive integers, what does the set of all
such that
for
look like?
Let’s start with , since it is the easiest. What does
look like? Well,
means that
. Which is to say,
, or
. So the graph of
is a step function, taking the value
on the interval
. 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, is
, the third stair from the right.
Now, on to . What does
look like? Well, in finding the continued fraction for
, we find first
, and if
then
, or
. So we find that for any
, all values between
and
have
. That is, in each of the “stairs” from the discussion of
, the graph of
has another staircase, this time ascending as you move from left to right.
For example, comprises, in the ascending staircases in each interval
, the second stair from the left. It is an infinite collection of intervals. If you also ask about those where
is some constant, you pick out a single subinterval.
So we’ve got at least a little idea about how these functions work. Given
and
as above, the set of all
with
will be an infinite collection of subintervals of
. Next you could ask, what is the measure (sum of lengths of intervals) of this set? I’ll mostly talk about the case when
,
, and
. I’ll denote the set of appropriate
by
, and the measure of that set by
.
Apparently Gauss had a go at questions like this. He defined to be the measure of the set of all
such that
, and found that
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 . 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, and
, such that
On integrating and taking limits, we obtain Gauss’ result. Alternatively, using the relation
one can also obtain
Or, taking limits,
This, by itself, seems pretty interesting. I find it a hard limit to interpret. After all, and
have nothing to do with eachother, so the measure that we are calculating is of a completely different set with each
. 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 is a function from positive integers to positive reals such that
for some positive constants
and
, then for almost every
in
,
Khinchin’s constant is obtained from the case when , simply messing with the equality using log and exponent rules.
Another interesting case is when you take if
and 0 otherwise. Then the limit on the left of the equality in Khinchin’s theorem should be interpreted as the density of
among the values of the
in the continued fraction for
. The expression on the right in the equality simplifies to a single term, instead of an infinite series. For example, with
we find that approximately 42% of the terms (Khinchin calls them “elements”) in the continued fraction for just about any
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 you want (pick several!). Find all of the elements in the continued fraction for
, and the percentage that are your chosen integer (it will be a positive percentage!). You’ll get the same percentage for all of the
you pick. Unless, of course, you have terrible luck (or are malicious) in picking
. 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
, 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 -th convergent for a continued fraction
is the fraction
. As this is a finite continued fraction, it represents a rational number, and it is typically denoted
(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
and
, you can find that
. The interesting theorem I have in mind is another “there is a constant” theorem:
Theorem: For almost all ,
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 , in the process of finding the continued fraction for
, 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?