Continued fractions using all natural integers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T10:31:57Z http://mathoverflow.net/feeds/question/6222 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/6222/continued-fractions-using-all-natural-integers Continued fractions using all natural integers timur 2009-11-20T05:29:06Z 2010-05-07T14:30:52Z <p>What can one say about the set of continued fractions $[0;a_1,a_2,\ldots]$, where $a_1,a_2,\ldots$ are a <em>permutation</em> of the set of natural numbers?</p> http://mathoverflow.net/questions/6222/continued-fractions-using-all-natural-integers/6223#6223 Answer by Noah Snyder for Continued fractions using all natural integers Noah Snyder 2009-11-20T05:55:15Z 2009-11-20T05:55:15Z <p>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.</p> http://mathoverflow.net/questions/6222/continued-fractions-using-all-natural-integers/6226#6226 Answer by Qiaochu Yuan for Continued fractions using all natural integers Qiaochu Yuan 2009-11-20T06:06:24Z 2009-11-20T06:06:24Z <p>It has measure zero; see the Wikipedia article on <a href="http://en.wikipedia.org/wiki/Khinchin%27s_constant" rel="nofollow">Khinchin's constant</a>.</p> http://mathoverflow.net/questions/6222/continued-fractions-using-all-natural-integers/6228#6228 Answer by Harrison Brown for Continued fractions using all natural integers Harrison Brown 2009-11-20T06:28:50Z 2009-11-20T06:28:50Z <p>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.)</p> <p>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.</p> <p>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...</p> <p>In essence, these are pretty much a completely typical uncountable set of measure 0, as far as I can tell. </p> http://mathoverflow.net/questions/6222/continued-fractions-using-all-natural-integers/6256#6256 Answer by gowers for Continued fractions using all natural integers gowers 2009-11-20T11:50:23Z 2009-11-20T11:50:23Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/6222/continued-fractions-using-all-natural-integers/6269#6269 Answer by David Speyer for Continued fractions using all natural integers David Speyer 2009-11-20T14:20:15Z 2009-11-20T14:26:12Z <p>This is a comment on <a href="http://mathoverflow.net/questions/6222/continued-fractions-using-all-natural-integers/6256#6256" rel="nofollow">gowers' answer</a>, but it is long enough that I am making it an answer on its own.</p> <p>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 &lt; q_{i+1} &lt; (a_{i+1} +1 ) q_i$, so $q_{i+1} \approx a_{i+1} q_i$. </p> <p>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$.</p> <p>So we have $$|x-p/q| \approx \frac{\log \log q}{q^2 \log q}.$$</p> <p>This is consistent with Roth's theorem. </p> <p>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| &lt; \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?</p> http://mathoverflow.net/questions/6222/continued-fractions-using-all-natural-integers/6280#6280 Answer by Ian Morris for Continued fractions using all natural integers Ian Morris 2009-11-20T16:31:29Z 2009-11-20T16:31:29Z <p>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:</p> <p><a href="http://www.informatik.uni-bremen.de/~mhk/papers/Texan.pdf" rel="nofollow">http://www.informatik.uni-bremen.de/~mhk/papers/Texan.pdf</a></p> <p><a href="http://www.maths.qmw.ac.uk/~omj/hensley4.ps" rel="nofollow">http://www.maths.qmw.ac.uk/~omj/hensley4.ps</a></p> <p><a href="http://www.jstor.org/pss/117986" rel="nofollow">http://www.jstor.org/pss/117986</a></p> <p>However I am not aware of anyone's having studied this particular restriction.</p> http://mathoverflow.net/questions/6222/continued-fractions-using-all-natural-integers/23753#23753 Answer by Roland Bacher for Continued fractions using all natural integers Roland Bacher 2010-05-06T17:28:05Z 2010-05-07T06:53:34Z <p>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. </p> <p>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).</p> http://mathoverflow.net/questions/6222/continued-fractions-using-all-natural-integers/23836#23836 Answer by SJR for Continued fractions using all natural integers SJR 2010-05-07T09:31:09Z 2010-05-07T14:30:52Z <p>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:</p> <p>$$\frac{1}{q_k^2(a_{k+1}+2)} &lt; |a-p_k/q_k| \le \frac{1}{q_k^2a_{k+1}}.$$</p> <p>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]$.</p> <p>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.</p>