Continued fractions using all natural integers - MathOverflow

Continued fractions using all natural integers

2009-11-20T05:29:06Z

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?

Answer by Noah Snyder for Continued fractions using all natural integers

2009-11-20T05:55:15Z

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.

Answer by Qiaochu Yuan for Continued fractions using all natural integers

2009-11-20T06:06:24Z

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

Answer by Harrison Brown for Continued fractions using all natural integers

2009-11-20T06:28:50Z

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.

Answer by gowers for Continued fractions using all natural integers

2009-11-20T11:50:23Z

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.

Answer by David Speyer for Continued fractions using all natural integers

2009-11-20T14:20:15Z

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?

Answer by Ian Morris for Continued fractions using all natural integers

2009-11-20T16:31:29Z

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.

Answer by Roland Bacher for Continued fractions using all natural integers

2010-05-06T17:28:05Z

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

Answer by SJR for Continued fractions using all natural integers

2010-05-07T09:31:09Z

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.