Ruling Out Small Denominators
 

Suppose that I have the decimal expansion (up to a certain number of decimal places, which can easily be extended if I have the patience) of a real number (of no special form) and I suspect that the number is irrational. However, I don't know how to prove that the number is irrational.

What is the most computationally efficient way to set a as large as possible lower bound on the size of the denominator, if the number were rational?

[QUOTE=jinydu;85793]Suppose that I have the decimal expansion (up to a certain number of decimal places, which can easily be extended if I have the patience) of a real number (of no special form) and I suspect that the number is irrational. However, I don't know how to prove that the number is irrational.

What is the most computationally efficient way to set a as large as possible lower bound on the size of the denominator, if the number were rational?[/QUOTE]
The solution to your problem is to generate the continued fraction expansion of the number. If it is rational, the number of coefficients will be finite.

So continued fractions is the [B]fastest[/B] way? And if I stop the process after a certain number of steps, recombine the result into a single fraction, then this rules out all fractions with smaller denominators?

[QUOTE=jinydu;85799]So continued fractions is the [B]fastest[/B] way?[/QUOTE]It is the fastest I know. The trick is to compute the continued fraction fast.
[QUOTE=jinydu;85799]And if I stop the process after a certain number of steps, recombine the result into a single fraction, then this rules out all fractions with smaller denominators?[/QUOTE]
Yes.

Rational vs irrational numbers.
 

[QUOTE=alpertron;85798]The solution to your problem is to generate the continued fraction expansion of the number. If it is rational, the number of coefficients will be finite.[/QUOTE]
:no:
What about the rational number 1/3 = 0.3333333.............
The rational number in decimal form will repeat itself sooner or later unless it comes to a dead stop like 7/8 =0.875.
The irrational number will NOT. Take a random example and try it out.
This does not mean that an irratioanl number cannot have a pattern.
Take foir instance 0.123456789101112131415161718...
It is an irrational number and the digits can be predicted. The hundreth digit, the millionith digit and the trillionth didgit will end in 5,1,1,.
There are many different types of numbers besides these but it will go beyond this topic.
Mally :coffee:

[QUOTE=mfgoode;85839]:no:
What about the rational number 1/3 = 0.3333333.............
The rational number in decimal form will repeat itself sooner or later unless it comes to a dead stop like 7/8 =0.875.
The irrational number will NOT. Take a random example and try it out.
This does not mean that an irratioanl number cannot have a pattern.
Take foir instance 0.123456789101112131415161718...
It is an irrational number and the digits can be predicted. The hundreth digit, the millionith digit and the trillionth didgit will end in 5,1,1,.
There are many different types of numbers besides these but it will go beyond this topic.
Mally :coffee:[/QUOTE]
The original poster wrote:

[QUOTE=jinydu]...up to a certain number of decimal places, which can easily be extended if I have the patience...[/QUOTE]

So when he tries 0.3333333... he will find 1/3 very quickly. Adding more 3's will not change the fraction. So after trying, say 100 digits, the fraction found will still be 1/3.

The number 0.123456789101112131415161718... that you wrote above will have an infinite continued fraction expansion. So after you add more digits to the irrational number, you will be able to find more terms of the continued fraction, meaning that the number cannot be expressed by a simple fraction.

Rational vs irrational numbers.
 

[QUOTE=alpertron;85841]The original poster wrote:

So when he tries 0.3333333... he will find 1/3 very quickly. Adding more 3's will not change the fraction. So after trying, say 100 digits, the fraction found will still be 1/3.
.[/QUOTE]
:smile:
The fraction 1/3 is known as an open ended rational.
No amount of three's can give its exact value. It comes closer and closer to
1/3 as one adds more and more of 3's but never the exact 1/3.
After 100 digits the fraction will NOT be 'still' 1/3.
Hence one needs an infinite amount of fractions to describe 1/3.
Over all I agree you mean what you say, but remember, we are dealing in mathematics and rigid exactitude.

Hence this is in direct contradiction of your earlier post
[Quote=alpertron] The solution to your problem is to generate the continued fraction expansion of the number. If it is rational, the number of coefficients will be finite.[/QUOTE]

Mally :coffee:

The idea is that adding more 3's you will not be able to extend the continued fraction:

0.3 = [3, 3]
0.33 = [3, 33]
0.333 = [3, 333]
0.3333 = [3, 3333]
0.33333 = [3, 33333]
0.333333 = [3, 333333]
and so on.

So it appears that the expansion cannot continue after the first three, because the second term increases without limit. So the fraction must be 1/3.

I think that the notion of ""continued fraction expansion" and "decimal expansion " are being mixed up here.

Adding 3's to a continued fraction expansion of 1/3 changes the rational number you are dealing with.

e.g. 1/3= [0;3], but [0;3,3] is not the same as 1/3. In fact, [0;3,3 ] = 3/10.

[QUOTE=Hatori27;85855]I think that the notion of ""continued fraction expansion" and "decimal expansion " are being mixed up here.

Adding 3's to a continued fraction expansion of 1/3 changes the rational number you are dealing with.

e.g. 1/3= [0;3], but [0;3,3] is not the same as 1/3. In fact, [0;3,3 ] = 3/10.[/QUOTE]
Yes, it agrees with the first line I wrote above: 0.3 = [3, 3]. It appears that your notation [0;3,3] is 0+[3,3] (or [3,3])

Continuing with the problem set by the original poster, if the number in question is 0.12345678910111213141516... (which is obviously irrational) we find its continued fraction expansion:

[ 8 , 9 , 1 , 149083 , 1 , 1 , 1 , 4 , 1 , 1 , 1 , 3 , 4 , 1 , 1 , 1 , 15 ,
4575401113910310764836466282429561185996039397104575\
5500066200439309026265925631493795320774712865626829\
1352511788034072479309738318986794132119711326023863\
081376170,
6 , 4 , 1 , 5 , 1 , 1 , ...]

If we convert the continued fraction to standard fractions just before the huge coefficients we get:

10 / 81
60499999499 / 490050000000

The first 189 digits of the last number agrees with the decimal expansion of our irrational number.

Mathematica seems to be behaving strangely. I'm getting:

ContinuedFraction[0.3] = {0, 3}

ContinuedFraction[3/10] = {0, 3, 3}

Even worse:

ContinuedFraction[0.2] = {0}

[QUOTE=jinydu;85897]Mathematica seems to be behaving strangely. I'm getting:

ContinuedFraction[0.3] = {0, 3}

ContinuedFraction[3/10] = {0, 3, 3}

Even worse:

ContinuedFraction[0.2] = {0}[/QUOTE]

Use PARI/GP, then. :cool:

gp>contfrac(0.3)
%104 = [0, 3, 3]
gp>contfrac(3/10)
%105 = [0, 3, 3]
gp>contfrac(0.2)
%106 = [0, 5]

[QUOTE=jinydu;85897]Mathematica seems to be behaving strangely. I'm getting:

ContinuedFraction[0.3] = {0, 3}

ContinuedFraction[3/10] = {0, 3, 3}

Even worse:

ContinuedFraction[0.2] = {0}[/QUOTE]

The Mathematica strange behaviour continues by introducing a small error

ContinuedFraction[0.2-10^-10] returns {0,5}
and
ContinuedFraction[0.2+10^-10] returns {0,4,1}

This is on version 4.1

I'm using Version 4.0.2. Are you saying that this problem is fixed in versions newer than 4.1?

In any case, given that such errors occur, I'm not so sure that I can trust the answer that Mathematica gives for, say:

ContinuedFraction[[tex]\pi^3[/tex]]

[QUOTE=alpertron;85861]Yes, it agrees with the first line I wrote above: 0.3 = [3, 3]. It appears that your notation [0;3,3] is 0+[3,3] (or [3,3])

Continuing with the problem set by the original poster, if the number in question is 0.12345678910111213141516... (which is obviously irrational) we find its continued fraction expansion:

[ 8 , 9 , 1 , 149083 , 1 , 1 , 1 , 4 , 1 , 1 , 1 , 3 , 4 , 1 , 1 , 1 , 15 ,
4575401113910310764836466282429561185996039397104575\
5500066200439309026265925631493795320774712865626829\
1352511788034072479309738318986794132119711326023863\
081376170,
6 , 4 , 1 , 5 , 1 , 1 , ...]

If we convert the continued fraction to standard fractions just before the huge coefficients we get:

10 / 81
60499999499 / 490050000000

The first 189 digits of the last number agrees with the decimal expansion of our irrational number.[/QUOTE]Indeed, the presence of a particularly large term in the CF expansion of a number indicates that it is especially well represented by a rational approximation. There can be practical benefits of observing such things. For instance, it can have cryptographic significance. See the justly famous Blum, Blum & Shub paper for a concrete example. Yes, I am being deliberately obscure in the hope that you'll put just a little effort into tracking down the paper mentioned. The effort brings its own rewards.

Paul

[QUOTE=alpertron;85861]Yes, it agrees with the first line I wrote above: 0.3 = [3, 3]. It appears that your notation [0;3,3] is 0+[3,3] (or [3,3])

Continuing with the problem set by the original poster, if the number in question is 0.12345678910111213141516... (which is obviously irrational) we find its continued fraction expansion:

[ 8 , 9 , 1 , 149083 , 1 , 1 , 1 , 4 , 1 , 1 , 1 , 3 , 4 , 1 , 1 , 1 , 15 ,
4575401113910310764836466282429561185996039397104575\
5500066200439309026265925631493795320774712865626829\
1352511788034072479309738318986794132119711326023863\
081376170,
6 , 4 , 1 , 5 , 1 , 1 , ...]

If we convert the continued fraction to standard fractions just before the huge coefficients we get:

10 / 81
60499999499 / 490050000000

The first 189 digits of the last number agrees with the decimal expansion of our irrational number.[/QUOTE]Simple exercise: predict when the next huge coefficient occurs in the CF expansion of this number. Explain your reasoning.

Slightly harder exercise: find the next huge coefficient and see whether its position is in accordance with your prediction.

Further exercise: repeat the previous two exercises until you run out of computational resources.


Paul

[QUOTE=xilman;85913]Indeed, the presence of a particularly large term in the CF expansion of a number indicates that it is especially well represented by a rational approximation. There can be practical benefits of observing such things. For instance, it can have cryptographic significance. See the justly famous Blum, Blum & Shub paper for a concrete example. Yes, I am being deliberately obscure in the hope that you'll put just a little effort into tracking down the paper mentioned. The effort brings its own rewards.

Paul[/QUOTE]

Indeed. The presence of such a large term early on also strongly
suggests that the number is transcendental, because Thue's Theorem
limits how quickly the denominators can grow for ALGEBRAIC irrationals.

[QUOTE=xilman;85913]Indeed, the presence of a particularly large term in the CF expansion of a number indicates that it is especially well represented by a rational approximation. There can be practical benefits of observing such things. For instance, it can have cryptographic significance. See the justly famous Blum, Blum & Shub paper for a concrete example. Yes, I am being deliberately obscure in the hope that you'll put just a little effort into tracking down the paper mentioned. The effort brings its own rewards.

Paul[/QUOTE]

Indeed. The presence of such a large term early on also strongly
suggests that the number is transcendental, because Thue's Theorem
limits how quickly the denominators can grow for ALGEBRAIC irrationals.

[QUOTE=xilman;85914]Simple exercise: predict when the next huge coefficient occurs in the CF expansion of this number. Explain your reasoning.

Slightly harder exercise: find the next huge coefficient and see whether its position is in accordance with your prediction.

Further exercise: repeat the previous two exercises until you run out of computational resources.

Paul[/QUOTE]

This is a known constant. See: [URL="http://mathworld.wolfram.com/ChampernowneConstant.html"]http://mathworld.wolfram.com/ChampernowneConstant.html[/URL]

It is clear that this number must have very large coefficients in the continued fraction expansion:

From:

[tex]\large \frac{1}{\left(10^n-1\right)^2} = \frac{1}{10^{2n}} + \frac{2}{10^{3n}} + \frac{3}{10^{4n}} + ...[/tex]

Now we multiply by a power p of 10 such that the consecutive numbers of n digits are in the same location than the Champernowne constant C. For example when n=2, p=11. Let B be this product.

Now the product has 9n(10[sup]n-1[/sup]) - n - 1 digits equals to C starting from the digit G(n) (G(2) = 10, G(3) = 190, G(4) = 2890, ..., G(n) = G(n-1) + 9(n-1)(10[sup]n-2[/sup])). (Notice that G(n) is near (n-1)10[sup]n-1[/sup]). This means that the difference between C and the product is very near a fraction whose denominator is 10[sup]G(n)-1[/sup]. Call it D.

Now B - D is extremely near to C, with about n 10[sup]n[/sup] digits correct, while the denominator of D - B is lcm ((10[sup]n[/sup]-1)[sup]2[/sup], 10[sup]G(n)-1[/sup]) which has about (n-1)10[sup]n-1[/sup] digits.

This implies a very huge coefficient in the continued fraction expansion of the constant, which are larger when n increases.

[QUOTE=alpertron;85926]It is clear that this number must have very large coefficients in the continued fraction expansion:[/QUOTE]Thank you! :bow:

i'm always pleased when someone takes seriously my suggestions of worthwhile "exercises", which are sometimes trivial to answer and sometimes turn out to be research problems.


Paul

I would like to repeat the question I asked earlier, lest it be forgotten:

[QUOTE=jinydu;85911]I'm using Version 4.0.2. Are you saying that this problem is fixed in versions newer than 4.1?

In any case, given that such errors occur, I'm not so sure that I can trust the answer that Mathematica gives for, say:

ContinuedFraction[[tex]\pi^3[/tex]][/QUOTE]

Know constant
 

[QUOTE=R. Gerbicz;85918]This is a known constant. See: [URL="http://mathworld.wolfram.com/ChampernowneConstant.html"]http://mathworld.wolfram.com/ChampernowneConstant.html[/URL][/QUOTE]
:bow:
Thank you R. Gerbicz for hitting the nail on the head by pinning down the Chempernowne constant which is normal for base 10 and also transcendental which I gave as an example.
This was a revelation for me and with your URL for Math World I went on to the 'binary' and ternary 'Champ' and also the Copeland-Erdos constant for the concatenation of the primes which is a normal number.

Particular examples of quadratic irrationals are (a + sq.rt. b) where a =0 and b is a non square natural number (or greater than 1 :) like
Sq roots of 2 ,3, 5, e tc..

The continued fraction representation of such a number is striking.
The sequence of natural numbers that defines it as a continued fraction has a curious characteristic.
It starts with some number A, t hen it is immediately followed by a 'palindromic sewquence ( that is one which reads the same backwards) like B, C, D,.... D,C,B, followed by 2A repeats itself indefinitely.
Take the number sq.rt. 14 as an example for which the sequence is
3,1,2,1,6,1,2.1,6,1,2,1,6,.1,2,1,6........
Here A = 3 and the palindromic sequence D,C,B is just the three term sequence 1,2,1,.

For converting decimal to its rational fraction I give an example for the method.
Eg: Say we have 1.42857 142857 142857.
Let x = 1.42857 repeating
Get rid of the decimal by multiplying
So 100000x = 142857
Subtract the two eqn.s
We get 99999x = 142857
x = 142857/99999 = 1/7

Try it out for x = .01 01 01 01....
You should get 1/99
Mally :coffee: