A true, unprovable and simple statement

[lockecole]

"Since I am a mathematician, I give a precise answer to this question. Thanks to Kurt Gödel, we know that there are true mathematical statements that cannot be proved. But I want a little more than this. I want a statement that is true, unprovable, and simple enough to be understood by people who are not mathematicians. Here it is."

http://www.edge.org/q2005/q05_9.html#dysonf

 

[0rthodontist]

I don't believe it. He says the probability of a given power of 2 reversing to be a power of 5 is less than 1 in a billion, but there is an unlimited number of such powers. Also maybe he has some reasonable argument behind his statement that it cannot be proved but what he's given is not reasonable.

 

[mathman]

The digits in a big power of two seem to occur in a random way without any regular pattern. If it ever happened that the reverse of a power of two was a power of five, this would be an unlikely accident, and the chance of it happening grows rapidly smaller as the numbers grow bigger. If we assume that the digits occur at random, then the chance of the accident happening for any power of two greater than a billion is less than one in a billion. It is easy to check that it does not happen for powers of two smaller than a billion. So the chance that it ever happens at all is less than one in a billion. That is why I believe the statement is true.

Above is Dyson's argument. If you look at it carefully, he is definitely hedging. First sentence "seems to occur". Second sentence "unlikely to happen". etc. Finally "believe it to be true".

This is certainly not a case of a true but unprovable statement, as far as any respectable mathematician would say.

 

[WhyIsItSo]

I'm going to take a shot at this. I've only got 1Gb of RAM on my PC, so I won't get into mind-boggling numbers, but we'll see if within the limits I have I can find a number that satisifes the process.

I just need to find out how to calculate 5th roots. I've got a question about this on another forum, but if anyone knows the answer, pipe up. For these very large numbers, the only function of this "type" available to me is pow (power).

 

[matt grime]

What an utter nonsensical (and false) way of writing things (2^0 for instance is a contradiction). Goedel, last time I checked, wasn't a statement about probability.

 

[JonF]

This is a good accessible explanation of godel’s theorem that I recently read. Not sure if it helps. http://www.ncsu.edu/felder-public/kenny/papers/godel.html

 

[CRGreathouse]

"It is easy to find other examples of statements that are likely to be true but unprovable. The essential trick is to find an infinite sequence of events, each of which might happen by accident, but with a small total probability for even one of them happening. Then the statement that none of the events ever happens is probably true but cannot be proved."


I'm of course unconvinced; heuristic arguments don't settle it for me at all. Heck, I've seen (good!) heuristics that suggest that there should be few or no Mersenne primes... of course it wasn't designed for that purpose, but it goes to show how hard it is to work with just such arguments.

 

[WhyIsItSo]

FYI, I've almost finished a program to test Dyson's proposal. I did it for the exercise of programming, but I'll let you know if anything "interesting" comes of it.

 

[robert Ihnot]

I might not be the best one (?) to analyze this, but Dyson says that a number is power of two is a random event, while a power of three is not.

So if a power of two is a completely random event among the integers, then it would be, assumedly, impossible to get a tight grip on its properties. So that if its reverse is a power of 5 is very, very unlikely, we are left with an event probably true but improvable.

Is that not good enough? Maybe not?

I remember the name Dyson from Number Theory. Well, how are you going to show that any statement is true but improvable? Dyson is operating with some sort of "Uncertainty principal." Actually Physicists do it all the time!

 

[haki]

Fascinating,

I just made a simple program in Java to test if the reverse of a power of two is never a power of five. Soo far the program is processing Integers with 8300+ places and found no contradictions.

Funny, a mathematical statement, that cannot be proven? Is this possible? I find it hard to believe that a Mathematician would make such a clame. We are just supose to take this as it is? How can we be sure that this is true? Where is the rigour that mathematicians cannot live without?

Guess the proofs techniques that we learn in College cannot be applied? This is rather ad hoc, tought that Mathematicians don't work that way.

 

[WhyIsItSo]

Fascinating,

I just made a simple program in Java to test if the reverse of a power of two is never a power of five. Soo far the program is processing Integers with 8300+ places and found no contradictions.

I trust you mean the reverse of a power of two is never a power of 5. Otherwise, the statement is trivially proven true.

BTW, does your PC make a "new" noise when processing this? Mine has a distinct sound that I hear only when running my program. Tis rather disquieting as I envision silicon melting

Funny, a mathematical statement, that cannot be proven? Is this possible? I find it hard to believe that a Mathematician would make such a clame. We are just supose to take this as it is? How can we be sure that this is true? Where is the rigour that mathematicians cannot live without?

Guess the proofs techniques that we learn in College cannot be applied? This is rather ad hoc, tought that Mathematicians don't work that way.

Isn't this just like saying pi never repeats? I understood this could not be proven mathematically, but is understood to be true. Have I missed something?

 

[shmoe]

Isn't this just like saying pi never repeats? I understood this could not be proven mathematically, but is understood to be true. Have I missed something?

pi is proven to be irrational (and also transcendental), and hence it never repeats.

 

[matt grime]

Isn't this just like saying pi never repeats? I understood this could not be proven mathematically, but is understood to be true. Have I missed something?

Yes. Quite a bit in fact. It is conjectured that pi is a normal number, it is experimentally substantiated, but it is not proven. This does not mean it is true, nor does it mean it cannot be proven (mathematically). All it means is it has not been shown to be true (in some model).

 

[matt grime]

Funny, a mathematical statement, that cannot be proven? Is this possible? I find it hard to believe that a Mathematician would make such a clame. We are just supose to take this as it is? How can we be sure that this is true? Where is the rigour that mathematicians cannot live without?

What do you do when you prove something? You show it is implied by something 'simpler' that we know to be true. Now, go read that link about Goedel in this thread which I'm sure explains that if we start from a finite number of axioms (and the integers) that we there are models of said axioms where some statement is true, and some where the same statement is false.

 

[robert Ihnot]

Dyson talks about relations between numbers which are accidents. This does not seem unreasonable that there are many such relations. (Though some might not believe that.) But if there are such relationships, then they would be beyond any way of proving them, particularly if one had to search all the integers to find an example.

Fermat's Last Theorem seemed, for a long time, to be almost in that category. Modifying that theorem, such as X^P+Y^Pnot equal to P(Z^P) for all P might take a lot of effort to figure out, and possibly could not be figured out.

 

[haki]

I trust you mean the reverse of a power of two is never a power of 5. Otherwise, the statement is trivially proven true.

BTW, does your PC make a "new" noise when processing this? Mine has a distinct sound that I hear only when running my program. Tis rather disquieting as I envision silicon melting

That is correct, I use the reverse.

My laptops is loud as it is. There is no added sound.

Btw: you have nothing to worry about. You temperature is fine. Even if there was something wrong with your fan, most todays CPUs(am sure for P4), shut-down if there is excessive overheating. Soo there is no way the hardware could get damadged.

btw: you did use Java? I just love Java.

 

[CRGreathouse]

btw: you did use Java? I just love Java.

Myself, I don't like Java at all for numrical work. It's slow and doesn't do floating point quite right, and never takes advantage of the Intel/AMD 80-bit FPU (it's always treated as if it were 64 bits).

 

[chronon]

My respect for Dyson has just dropped a notch. In the first place in his example one has to assume that he is talking about the standard integers (rather than allowing non-standard models) in which case Godel tells us nothing of the sort.

Secondly his conjecture that the reverse of a power of two is never a power of five may well be true. He seems to think that because it seems so random it is likely to be unprovable. But can he really have any idea of what techniques might arise in number theory in the next few centuries to deal with questions like this? I think not.

 

[Office_Shredder]

Yes. Quite a bit in fact. It is conjectured that pi is a normal number, it is experimentally substantiated, but it is not proven. This does not mean it is true, nor does it mean it cannot be proven (mathematically). All it means is it has not been shown to be true (in some model).

I thought pi has been proven to be transcendental, and thus irrational

 

[CRGreathouse]

I thought pi has been proven to be transcendental, and thus irrational

Pi was proved to be transcendental (though it was proved irrational first), but that has little to do with matt's point. It hasn't been shown to be normal.

 

[shmoe]

I thought pi has been proven to be transcendental, and thus irrational

It is, though a separate proof of irrationality came before it was proven to be transcendental.

matt's talking about the conjecture pi is normal.

 

[Alkatran]

I find it ironic that a mathematician would ever say anything like this, especially in the interest of helping people who don't understand Goedel. Someone hearing this might double the fact that if we knew the statement was true, then it clearly isn't unprovable.

 

[Office_Shredder]

It is, though a separate proof of irrationality came before it was proven to be transcendental.

matt's talking about the conjecture pi is normal.

Whoops... I kind of lost the train of thought of the conversation, and thought by normal he meant rational.

 

[AKG]

Let p denote the smallest prime number greater than one billion. If we look at the first billion numbers, then we see no multiples of p, so we conclude that the probability of the existence of a multiple of p amongst all the naturals is less than one billion. Sound reasonable?

 

[Alkatran]

Let p denote the smallest prime number greater than one billion. If we look at the first billion numbers, then we see no multiples of p, so we conclude that the existence of a multiple of p amongst all the naturals is less than one billion. Sound reasonable?

That doesn't make any sense. How can the existence of something be less than a number?

 

[AKG]

Sorry, I meant "probability of existence". Edited.

 

[WhyIsItSo]

btw: you did use Java? I just love Java.

Yes I did. And because my motivation was primarily for Java experience, I built the application in 3 threads; the numebr cruncher, a GUI monitor, and a sort of controller to act as go between and preserve status should the number cruncher fall over (as it must when it runs out of memory).

It was a neat exercise

 

[MeJennifer]

Dyson claims that: "The digits in a big power of two seem to occur in a random way without any regular pattern. If it ever happened that the reverse of a power of two was a power of five, this would be an unlikely accident, and the chance of it happening grows rapidly smaller as the numbers grow bigger".

Why is that? I fail to see that.

 

[shmoe]

Powers of 5 get sparser and sparser very quick. If you randomly select an n digit number, the probability this is a power of 5 drops very fast as n grows larger.

He's making the assumption that the reverse of a power of two is somewhat 'random'. Not strictly trure of course, so this is really just a heuristic argument (even if they were perfectly random in some way, it still wouldn't be a proof).

 

[MeJennifer]

Powers of 5 get sparser and sparser very quick. If you randomly select an n digit number, the probability this is a power of 5 drops very fast as n grows larger.

I still don't get it.

For instance think of powers of 10. The probability of a power of 10 occurring in an n-digit number is 1 correct? And it stays 1 even if we increase n, correct?

So then for a power of 5, which is less than 10, the probability of finding a power of 10 in an n-digit number must be 1 as well right? In fact the occurence of a power of 5 in any n-digit number seems to be larger than 1. For instance 125 and 625 are both powers of 5 and 3 digits long.

So how does that imply it drops very fast if the number of digits increase?

 

[Robokapp]

If I'm to try to approach this problem, I'd have to say the following:

by jumping from a power of 2 to the next, you multiply the number by two. That means...the FIRST digit of the 2^{x} will always be a 2, 4, 6 or 8. (1)

When you reverse the number, this becomes the last digit of the number that you divide by 5^{x}. To divide by 5^{x} is same as dividing repeteadly by 5. Meaning the number must end in 5 or zero.

SInce it's a reverse it can't end in zero...so it must be a power of 2 having the highest unit a 5.

well 2^9=512...and 512 divides by 5 but it's not a power of 5.

let's look at the problem backwards. numberd divisible by 5^{x} are numbers ending in 5...because zero is lost in reversion.

so

512, 524288, 536870912, 549755813888, 562949953421312, 576...

are the numbers ending in 5.

2^9, 2^19, 2^29, 2^39, 2^49, 2^59, 2^69, 2^78, 2^88, 2^98 end in 5s.
I don't know if that's relevant or not yet.
Well as you can see, the front numbers aren't as "without pattern" as the guy claims, they look pretty patterned around the repeat of first digit every 2^10...which is common sense. 2^10 = 1024...close to 1000.

SO we know the wanted scenario doesn't occur in first 2^100 cases. then the numbers cycle at an almoust 1000x going pretty much in same pattern regarding front digits.

The way I'd put this into words is that as the power of 2 inreases, the need for a 5^x to equal the reverse of that number keeps on increasing the conditions, while the 2^x is in an almoust undisturbed cycle. With higher demand and same pattern, it's not possible for the two to intersect...

By higher demand I mean conditions of division...dividing by 5*5*5*5*5*5... asks for more and more multiples of 5 to exist in first digits...which are not changing much due to the 1024* cycle.

-----------------

Now I honestly don't know if this will even be read. I don't know if it's right or wrong, it's just how I'd look at it.

 

[shmoe]

I still don't get it.

For instance think of powers of 10. The probability of a power of 10 occurring in an n-digit number is 1 correct? And it stays 1 even if we increase n, correct?

There are O(n) powers of 5 with n-digits. there are 10^n numbers with n-digits (or fewer). the probability a randomly selected n-digit number is a power of 5 is then O(n/10^n), whhich tends to zero very quickly.

 

[MeJennifer]

There are O(n) powers of 5 with n-digits. there are 10^n numbers with n-digits (or fewer). the probability a randomly selected n-digit number is a power of 5 is then O(n/10^n), whhich tends to zero very quickly.

I realize that but that is something different.

For each n-digit occurance the number of powers of 2 and 5 remains constant. Sure the numbers get larger so the probability that something is a power of 5 or 2 is lower, but not when measured against the number of digits.
So how could Dyson reason that the probability of finding a number that applies in an n digit number is far greater than in an >>n number?

 

[shmoe]

by jumping from a power of 2 to the next, you multiply the number by two. That means...the FIRST digit of the 2^{x} will always be a 2, 4, 6 or 8. (1)

You seem to know this isn't true:

2^9, 2^19, 2^29, 2^39, 2^49, 2^59, 2^69, 2^78, 2^88, 2^98 end in 5s.
I don't know if that's relevant or not yet.
Well as you can see, the front numbers aren't as "without pattern" as the guy claims, they look pretty patterned around the repeat of first digit every 2^10...which is common sense. 2^10 = 1024...close to 1000.

Though 2^78, 2^88, 2^98 don't begin with a 5. Maybe you used a calculator that is rounding at some point.

 

[shmoe]

I realize that but that is something different.

For each n-digit occurance the number of powers of 2 and 5 remains constant. Sure the numbers get larger so the probability that something is a power of 5 or 2 is lower, but not when measured against the number of digits.
So how could Dyson reason that the probability of finding a number that applies in an n digit number is far greater than in an >>n number?

It's no different. He's considering the reverse of the powers of 2 to be "random" large digit numbers. as such, the probability of hitting one of the powers of 5 decreases rapidly as the powers of 2 are increasing.

I don't see where the confusion is. As the number of digits grows, the number of 'spots' for these powers of 2 and 5 are increasing exponentially, so a collision seems highly unlikely.

 

[Robokapp]

Though 2^78, 2^88, 2^98 don't begin with a 5. Maybe you used a calculator that is rounding at some point.

ouch...good point. yeah...the 5 becomes 6 due to the 24 units. I used the start/applications one. I figured since it slowly goes up in the 5s it will hit 6 so I'll lower one power. I wasn't thinking. I didn't hit "=" 100 times...I just checked up to 59 or so...

Even so, that actually consolidates the point. The powers of 2 that begin with 5 actually stretch apart as numbers increase.

The way I see it, it's not that it can't be proven, it just can't be...put in a form that makes everyone happy. It can't be put in a nice deffinition or justified by formulas and other calculations but by...logic.

 

[CRGreathouse]

ouch...good point. yeah...the 5 becomes 6 due to the 24 units. I used the start/applications one. I figured since it slowly goes up in the 5s it will hit 6 so I'll lower one power. I wasn't thinking. I didn't hit "=" 100 times...I just checked up to 59 or so...

Even so, that actually consolidates the point. The powers of 2 that begin with 5 actually stretch apart as numbers increase.

The way I see it, it's not that it can't be proven, it just can't be...put in a form that makes everyone happy. It can't be put in a nice deffinition or justified by formulas and other calculations but by...logic.

Here's the list of exponents to 5000, for reference. This took 359 ms with PARI/GP.
9 19 29 39 49 59 69 102 112 122 132 142 152 162 172 195 205 215 225 235 245 255 265 298 308 318 328 338 348 358 391 401 411 421 431 441 451 461 494 504 514 524 534 544 554 587 597 607 617 627 637 647 657 680 690 700 710 720 730 740 750 783 793 803 813 823 833 843 876 886 896 906 916 926 936 946 979 989 999 1009 1019 1029 1039 1072 1082 1092 1102 1112 1122 1132 1142 1165 1175 1185 1195 1205 1215 1225 1235 1268 1278 1288 1298 1308 1318 1328 1338 1361 1371 1381 1391 1401 1411 1421 1431 1464 1474 1484 1494 1504 1514 1524 1557 1567 1577 1587 1597 1607 1617 1627 1650 1660 1670 1680 1690 1700 1710 1720 1753 1763 1773 1783 1793 1803 1813 1823 1846 1856 1866 1876 1886 1896 1906 1916 1949 1959 1969 1979 1989 1999 2009 2042 2052 2062 2072 2082 2092 2102 2112 2135 2145 2155 2165 2175 2185 2195 2205 2238 2248 2258 2268 2278 2288 2298 2308 2331 2341 2351 2361 2371 2381 2391 2401 2434 2444 2454 2464 2474 2484 2494 2527 2537 2547 2557 2567 2577 2587 2597 2630 2640 2650 2660 2670 2680 2690 2723 2733 2743 2753 2763 2773 2783 2793 2816 2826 2836 2846 2856 2866 2876 2886 2919 2929 2939 2949 2959 2969 2979 3012 3022 3032 3042 3052 3062 3072 3082 3115 3125 3135 3145 3155 3165 3175 3208 3218 3228 3238 3248 3258 3268 3278 3301 3311 3321 3331 3341 3351 3361 3371 3404 3414 3424 3434 3444 3454 3464 3497 3507 3517 3527 3537 3547 3557 3567 3600 3610 3620 3630 3640 3650 3660 3693 3703 3713 3723 3733 3743 3753 3763 3786 3796 3806 3816 3826 3836 3846 3856 3889 3899 3909 3919 3929 3939 3949 3959 3982 3992 4002 4012 4022 4032 4042 4052 4085 4095 4105 4115 4125 4135 4145 4178 4188 4198 4208 4218 4228 4238 4248 4271 4281 4291 4301 4311 4321 4331 4341 4374 4384 4394 4404 4414 4424 4434 4444 4467 4477 4487 4497 4507 4517 4527 4537 4570 4580 4590 4600 4610 4620 4630 4663 4673 4683 4693 4703 4713 4723 4733 4766 4776 4786 4796 4806 4816 4826 4859 4869 4879 4889 4899 4909 4919 4929 4952 4962 4972 4982 4992

I don't think this supports your assertion that the "powers of 2 that begin with 5 actually stretch apart as numbers increase", unless you meant trivially since the powers are spread out more as they increase. There are 81 of these 'special' powers of 2 with exponents between 1 and 999 and 81 between 50000 and 50999. Here's the exact count in baches of 1000:

1000: 81
2000: 78
3000: 79
4000: 80
5000: 79
6000: 78
7000: 79
8000: 81
9000: 77
10000: 81
11000: 79
12000: 79
13000: 78
14000: 80
15000: 80
16000: 77
17000: 81
18000: 79
19000: 79
20000: 79
21000: 80
22000: 78
23000: 79
24000: 79
25000: 80
26000: 78
27000: 80
28000: 81
29000: 77
30000: 81
31000: 79
32000: 79
33000: 79
34000: 80
35000: 79
36000: 78
37000: 80
38000: 79
39000: 78
40000: 79
41000: 81
42000: 78
43000: 80
44000: 80
45000: 79
46000: 78
47000: 79
48000: 80
49000: 77
50000: 81

This is rather in keeping with Benford's law.