# Continued fractions using all natural integers

What can one say about the set of continued fractions $[0;a_1,a_2,\ldots]$, where $a_1,a_2,\ldots$ are a permutation of the set of natural numbers?

-
I'm going to take a wild guess here: nothing. Except, of course, for the fact that those numbers cannot be rational or quadratic irrationalities. Since I've nothing to support this guess really, I'll leave this as a comment rather than an answer. – Alon Amit Nov 20 '09 at 5:44

Yeah, it has measure 0 by what Qiaochu said, although I strongly suspect there's probably a more elementary way to prove this (or at least give a strong heuristic argument.)

It's also uncountable, which means that in particular: 1. There exist numbers of this type that are transcendental, 2. There exist numbers of this type that are uncomputable, 3. It's very very very very unlikely that you'll be able to come up with a nontrivially different characterization of them.

They don't form any algebraic structure of any significance as far as I can tell (not a field, not a ring, I'm 100% sure but not completely convinced not a group), they're obviously not dense in the reals...

In essence, these are pretty much a completely typical uncountable set of measure 0, as far as I can tell.

-
Actually, I think it's nowhere dense. Topologically this resembles the Cantor set, except I'm not sure if it's dense in itself or not. – Harrison Brown Nov 20 '09 at 8:04
Is there any algebraic number at all in this set? Continued fraction [1,2,3,4,5...] itself evaluates to a quotient of Bessel functions, so is presumably not algebraic. – Gerald Edgar May 6 '10 at 17:59
@Prof. Edgar: See the answers of Timothy Gowers and David Speyer below . – Steven Gubkin May 6 '10 at 21:46
I should point out that my answer only argues that the approximation rate of this continued fraction is consistent with the set containing an algebraic number; I have no opinion as to whether there actually is an algebraic number in this set. – David Speyer May 7 '10 at 11:48
@Gerald: Although I've not seen the conjecture about transcendence of such CFs (but this is indeed a very unnatural set as already pointed out), it's something that one should expect. The CF for $[1,2,3,\dots]$ (as quotient of the values of Bessel functions) is trancendental. @David: almost all numbers have approximation rate consistent with algebraic numbers. Algebraic numbers are too rare to appear. – Wadim Zudilin May 7 '10 at 14:19

It has measure zero; see the Wikipedia article on Khinchin's constant.

-

Using techniques from ergodic theory there are some good results on what the continued fraction of a random number looks like. In particular, the entries should follow the Guass-Kuzman distribution. This says that the entry is 1 roughly 40% of the time. So getting a permutation of the set of natural numbers is exceedingly unlikely.

-
Do you need Gauss-Kuzmin? It seems like such a strong condition on the continued fraction should be attainable with much weaker techniques. (Actually, looking at Wikipedia, the approach I had in mind looks like it could be pretty easily modified to yield Gauss-Kuzmin, but I still wonder if this is easier.) – Harrison Brown Nov 20 '09 at 17:32

I could be saying something accidentally stupid here, but let me risk it. It seems to me that Roth's theorem, which tells us that algebraic numbers can't be approximated substantially better than quadratic irrationalities, implies that the quotients in a continued fraction grow more slowly than linearly (or indeed any power that's greater than zero). If that's right, then a number of the kind you are talking about would have to be transcendental. My doubt about this argument is whether I've got the relationship between the quotients and rational approximation correct.

Of course, this is ignoring completely the fact that the quotients are a permutation of the positive integers and just using the fact that they must be quite large. It sounds as though your question is not "What can we say about a number with that property?" but rather "What can we say about the set of all numbers with that property?" so this observation, even if correct, may not have much to do with your question.

-
I don't think this works, see my answer. – David Speyer Nov 20 '09 at 14:21
I think you're right -- and indeed I was worried that something like that would happen. So it seems that the quotients have to grow rather fast to make the number transcendental. – gowers Nov 20 '09 at 15:24

This is a comment on gowers' answer, but it is long enough that I am making it an answer on its own.

I don't think this quite works. If $[a_0, a_1, \ldots, a_i]=p_i/q_i$, and $x$ is the value of the infinite continued fraction, then $$|x-p_i/q_i|= 1/(q_i q_{i+1})-1/(q_{i+1} q_{i+2}) + \cdots \approx 1/(q_i q_{i+1}).$$ We have $a_{i+1} q_i < q_{i+1} < (a_{i+1} +1 ) q_i$, so $q_{i+1} \approx a_{i+1} q_i$.

If $a_i$ is a permutation of the integers which doesn't reorder them too much then $a_i$ is about $i$ so $q_i \approx i!$. Inverting Stirling's approximation, $i \approx \log q_i/\log \log q_i$.

So we have $$|x-p/q| \approx \frac{\log \log q}{q^2 \log q}.$$

This is consistent with Roth's theorem.

My hazy memory is that there is a conjecture that, for $\phi(q)$ a decreasing positive function, there is an algebraic number $x$ with infinitely many solutions to $|x-p/q| < \phi(q)$ if and only if $\sum q \phi(q)$ diverges. That would predict that the error rate above is consistent with being algebraic. Does any one know if I remember this correctly?

-

An obvious thing to ask is what its Hausdorff dimension and box dimension are, although I can't give you an answer. Calculating the Hausdorff dimension of a set of numbers defined in terms of a restriction on continued fraction expansions has been a popular topic in ergodic theory lately, see for example:

http://www.informatik.uni-bremen.de/~mhk/papers/Texan.pdf

http://www.maths.qmw.ac.uk/~omj/hensley4.ps

http://www.jstor.org/pss/117986

However I am not aware of anyone's having studied this particular restriction.

-

The closure of this set in $[0,1]$ is exactly the subset $\mathcal C$ of all real numbers whose continued fraction expansions involve only different numbers. Rational numbers are fine for membership in $\mathcal C$ if they have a continued fraction expansion involves only distinct integers.

The set $\mathcal C$ is a Kantor set and it is also the closure of all real numbers whose continued fraction is a permutation of $\mathbb N$ with finite support (identity outside a finite set).

-

First some comments on the previous comments: Let $\theta=[0,a_0,a_1,\ldots]$ have convergents $p_i/q_i$. Then the connection between the $a_i$ and how well $p_i/q_i$ approximates $\theta$ is given by the following inequality:

$$\frac{1}{q_k^2(a_{k+1}+2)} < |a-p_k/q_k| \le \frac{1}{q_k^2a_{k+1}}.$$

This is taken from Khintchin's book on continued fractions, Page 36 (with a typo corrected.) This is why Roland's statement is true: For example you can make $\theta:=[0,a_0,a_1,\ldots]$ close to the number $2/3=[0,1,2]$, by taking for $\theta$ something like $[0,1,2,10^{100},\ldots]$.

As for Roth's theorem, if for some $\epsilon>0$ and for infinitely many $k$ it holds that $a_{k+1}\ge q_k^{\epsilon}$, then by the above double inequality, Roth's theorem is violated, and $\theta$ can't be algebraic. But consider $[0,1,2,3,\ldots]$. Here the $q_k$ are bounded below by the Fibonacci sequence and the $a_k$ grow linearly, so there is no problem with Roth's Theorem. For all I can see (SEE THE COMMENTS BELOW!!), $[0,1,2,3,\ldots]$ might be an algebraic number, although that might be ruled out by some of Lang's conjectural strengthenings of Roth.

-
But $[0,1,2,3,\dots]$ is known to be a transcendental number! – Wadim Zudilin May 7 '10 at 11:46
Oh!! Do you have a reference? Are you sure you're not thinking of Champernowne's constant .1234.... ? – SJR May 7 '10 at 12:12
A classical (Lambert-Euler) continued fraction is $(e-1)/(e+1)=[0;2,6,10,14,\dots]$ (Lang's or Cassels's books on Diophantine approximations). In a similar way one can show that $[1,2,3,\dots]$ is of the form $I_0(2)/I_0(1)$ (or something like this) for Bessel's functions. The algebraic independence of the numerator and denominator in this quotient was shown by C. Siegel already in 1929. – Wadim Zudilin May 7 '10 at 13:54
There is nothing to do with Roth's theorem! The number $[0,1,2,\dots]$ has irrationality exponent 2 (as algebraics) and even the exact quality of its approximation by rationals is known (see B.\,G.~Tasoev's paper [Math. Notes 67 (2000), 786--791]). There are no such results for algebraic irrationalities of degree $>2$. – Wadim Zudilin May 7 '10 at 15:05