Welcome to MathOverflow

Question

3

1

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, 1², 3², 5², 7², ...). 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.

flag	asked Nov 18 2009 at 22:51 Jimmy Miller 300●2●9

Martin M. W. · Accepted Answer · 2009-11-18 23:19:22Z UTC

13

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

answered Nov 18 2009 at 23:19

Martin M. W.
1,866●9●11

David Eppstein · Answer 2 · 2009-11-18 23:19:58Z UTC

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.

Kevin O'Bryant · Answer 3 · 2009-11-19 14:59:32Z UTC

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

Glenn · Answer 4 · 2011-10-26 01:14:57Z UTC

0

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.

answered Oct 26 2011 at 1:14

Glenn
5●2

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 2011 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 2011 at 4:07

I still see no universal test for rationality. – Douglas Zare Dec 17 2011 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 2012 at 3:23

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 2012 at 14:56

Patterns in Generalized Continued Fractions

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

4 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.