Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

According to the Wikipedia page on generalized continued fractions, $\pi$ can be given several GCF representations which have very regular structures; for example, one has the partial denominators as (1, 2, 2, 2, ...) and the partial numerators as (4, 12, 32, 52, 72, ...). My question is, can every real number be represented as a GCF that exhibits some sort of "structure"? I put that word in quotes because I'm not really sure how to define it concretely; ideally, the sequence of either partial numerators or partial denominators should be expressable using a predictable, explicit formula. Are there any theorems establishing results like this, or are there some numbers that have no GCF representation that is indistinguishable from random noise? If some numbers need to be expressed in other forms for a pattern to emerge, like Engel expansions, I'd be interested in knowing about that too.

share|improve this question

4 Answers 4

up vote 13 down vote accepted

I think under any reasonable definition there will be only countably many explicit formulas or patterns. So in fact most reals can't be expressed this way. (See also the concept of "computable number.")

share|improve this answer

It depends on what you mean by "generalized continued fraction". Greg Martin has a nice paper where the role of reciprocal is replaced by other things; he shows that all nice things happen, and do so simultaneously.

I don't agree with the negative countable/uncountable explanations (although I agree with the conclusion) given in other answers. For example, let $A(x)=(\{\lfloor n x \rfloor: n\in {\mathbb Z}\})$, and consider the simple continued fractions $y=[0;a_1,a_2,...]$ where $a_i=1$ if $i=A(x)$, and $a_i=2$ otherwise. Distinct $x$ yield distinct $y$, so we get uncountably many reals this way, all of whose simple continued fractions have "structure".

share|improve this answer
1  
I wouldn't call this "structure" unless x had certain nice Diophantine properties. –  Qiaochu Yuan Nov 19 '09 at 19:26
1  
If you came across a number, computed its cf, and found that it happened to have this form, you'd say "holy moly!" To me, that's structure. –  Kevin O'Bryant Nov 20 '09 at 6:02

I assume you're restricting the numerators and denominators to be integers, else there's the trivial generalized continued fraction (x;0,0,0,...) for any x.

I'm going to interpret "formula" broadly, as the sequence generated by an algorithm. Again one has to make an integer restriction, because there's a simple algorithm to generate the standard continued fraction for any x. I think the right way to state the restriction is that within the algorithms generating the sequences of numberators and denominators all numerical constants should be integers. But with that restriction, the answer to your question is no: there are uncountably many real numbers and only countably many algorithms that can be used to generate generalized continued fractions.

share|improve this answer

It's true that certain types of real numbers can be expressed as patterned generalized continued fractions, as indicated by the "Examples" section of the cited article. However, not all reals can be so expressed. For example, according to Wikipedia, the Euler–Mascheroni constant (aka "gamma" or γ) "has not been proved algebraic or transcendental. In fact, it is not even known whether γ is irrational," but finding a generalized continued fraction for γ would answer the latter question.

share|improve this answer
1  
How would finding a generalized continued fraction determine whether $\gamma$ is irrational? $2=1+3/(2+3/(2+3/(2+...$. –  Douglas Zare Oct 26 '11 at 10:28
    
If you look more closely in the "Examples" section, you'll see that your GCF for "2" is a special case of the GCF for the square root of (x^2+y), where in your case x=1 and y=3. It's certainly possible for nth roots be rational, but they generally have a simpler form than transcental functions and numbers. I expect that should a pattern be found, it will be cyclic, but the numbers themselves will not repeat, similar to the nth root examples in the same article, but requiring several terms before the repeating pattern becames apparent. –  Glenn Nov 27 '11 at 4:07
    
I still see no universal test for rationality. –  Douglas Zare Dec 17 '11 at 19:37
    
For rationality, if the SIMPLE (!) continued fraction for an expression terminates after a finite number of terms, the expression is rational; otherwise, it is not. Your above example shows that rational numbers can have nonterminating GENERALIZED CFs, but that's because there can be infinitely many of those for a given number, as opposed to only one SIMPLE CF (two if the final term b(k) > 1 is re-expressed as [..., b(k)-1, 1], but this is trivial). I try to choose my CFs to combine speed with relative simplicity. –  Glenn Jan 13 '12 at 3:23
1  
I'm well aware of the theory of simple continued fractions. Your statement that finding a GENERALIZED continued fraction for $\gamma$ would settle the rationality of $\gamma$ appears wrong. –  Douglas Zare Jan 15 '12 at 14:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.