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 occurrence 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?