mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2007-07-21, 08:21   #1
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

7·467 Posts
Default Status of GIMPS proofs

If I've understood things - but please correct me if I'm wrong or incomplete - GIMPS aims to discover and prove three aspects of Mersenne numbers:

(1) Discover new Mersenne Primes
(2) Prove that there are no lower Mersenne Primes than the ones already discovered
(3) For composite Mersenne numbers with accessible factor(s) find the lowest factor

(1) and (3) are clearly relatively easy to verify by the Mathematical community because they involve individual Mersenne numbers. But what about (2)? It is not really independently verifiable that what GIMPS now calls M39 is the 39th Mersenne because no-one can run tens of thousands of computers for another 10 years.

My question is: is there feedback, positive or negative, by independent Mathematicians about the status of GIMPS' findings about the number of Mersenne Primes in particular exponent ranges? Are the safeguards (the double checking of Lucas Lehmer tests and requirement of two tests with the same final residue) generally accepted as proof by the general Mathematical community or is there some controversy? I've seen only positive references to GIMPS on the internet by the way.
Brian-E is offline   Reply With Quote
Old 2007-07-26, 02:17   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts
Default

Quote:
Originally Posted by Brian-E View Post
(1) Discover new Mersenne Primes
(2) Prove that there are no lower Mersenne Primes than the ones already discovered
Or, you could combine (1) & (2) like: "Discover new Mersenne Primes in exhaustive search through all untested candidates."

Some earlier Mersenne-hunting efforts tested only certain ranges and skipped others, so were nonexhaustive.

Quote:
(3) For composite Mersenne numbers with accessible factor(s) find the lowest factor
That is not actually a GIMPS goal.

In GIMPS, factoring has been only secondary, performed only because it was the most efficient way, up to a certain point, to eliminate candidates without performing the costly Lucas-Lehmer computation.

Early in the project, finding the lowest factor was a convenient side-effect of this prime-candidate-elimination effort. It does have some mathematical value. So, the trial-factoring portion of the software, which for reasons of efficiency searches for factors somewhat out-of-order (though eventually checking all possibilities), would, upon finding a factor, spend a small amount of extra time determining whether there was also a slightly smaller factor or factors that would have been found if candidates had been tried in strictly sequential order. That guaranteed that the smallest factor was found.

Unfortunately, there was a software bug that sometimes caused that extra end-search to be skipped. Once it was discovered, it meant that some earlier GIMPS factoring results were not guaranteed to be the lowest factors. It was decided to omit that extra end-search for all efforts beyond a certain point. So, currently, factors found are not guaranteed to be the lowest.

Quote:
(1) and (3) are clearly relatively easy to verify by the Mathematical community because they involve individual Mersenne numbers. But what about (2)?
Well, each individual candidate is easily verifiable there, too. It is true that there are a much larger number of candidates to be verified for (2) than for (1), but that's just a matter of allocating sufficient resources, not a matter of actual impossibility.

Quote:
It is not really independently verifiable that what GIMPS now calls M39 is the 39th Mersenne because no-one can run tens of thousands of computers for another 10 years.
Yes, it is possible to do independent verification! What GIMPS did in its first 10 years takes less and less time to independently verify as computers get faster. The CPU I now use is over 40 times as fast as the one I used my first five years in GIMPS. I (or anyone else) could re-perform my first five years of GIMPS work in a couple of months now, using independently-written software if so wished to serve as verification.

Quote:
Are the safeguards (the double checking of Lucas Lehmer tests and requirement of two tests with the same final residue) generally accepted as proof by the general Mathematical community
Welcome to the era of experimental computational mathematics, in which not all results are absolutely proven certain beyond any shadow of a doubt. (Actually, that has always been true. Ask Pythagoras about the square root of -1. Ask someone who's found a flaw in a proof that had been generally accepted for decades.) We can only do our best to check for errors, including error analysis similar to that used in other experimental science. This has been discussed many times in this forum.

Another example of what I'm calling experimental computational mathematics was the 1977 proof of the Four-Color Theorem. It was done by computer program, it had the possibility of hardware or software error, and so was not _absolutely_ proven. (But as of 2005 another, independent proof seems to have been more certainly verified.) Indeed, the Four-Color Theorem had a pre-computer history of published "proofs" that turned out to have flaws! See the MathWorld entry at http://mathworld.wolfram.com/Four-ColorTheorem.html.
cheesehead is offline   Reply With Quote
Old 2007-07-26, 03:10   #3
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

79·101 Posts
Default

Brian-E

Is the guinea pig in your avatar yours?

Xyzzy is offline   Reply With Quote
Old 2007-07-26, 10:25   #4
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

7×467 Posts
Default

Cheesehead thanks for your detailed reply!
OK, so (3) the lowest factor of composite Mersenne numbers is not a GIMPS goal.
And I appreciate the points you make so succinctly that the goals are perfectly verifiable with increasing computer power, plus that all cutting edge Mathematics is hard to verify in any case and errors have been made throughout history. The Four Color theorem was indeed a nice example of an early (in computer history) very difficult proof carried out using brute force software attack based initially on clever Mathematics and programming. Also a good example of previous flawed attempts as I read in the link you give. I appreciate that GIMPS and other distributed computing projects are not really any different in principle, just larger scale because of widespread participation. Thanks again for your lucid help.
Brian.
Brian-E is offline   Reply With Quote
Old 2007-07-26, 10:29   #5
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

7×467 Posts
Default

Quote:
Originally Posted by Xyzzy View Post
Brian-E

Is the guinea pig in your avatar yours?

Ah.... you've got me. No, sadly it's not my guinea pig. You've correctly identified the species, I hope you haven't identified the individual and are claiming any damages or anything.
No, I got this little guy (or girl?) from a large number of photos posted on the internet by a guinea pig breeder who -I hope- couldn't possibly object. Hope the guinea pig wouldn't either.
I'm really hoping to pre-empt the habit you moderators apparently have of imposing an avatar on people - because I'd really like to use this one. Hope that's OK.

Brian-E is offline   Reply With Quote
Old 2007-07-27, 00:40   #6
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

79×101 Posts
Default

Guinea pigs are cool.
Xyzzy is offline   Reply With Quote
Old 2007-08-02, 21:48   #7
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

23·7·167 Posts
Default

Quote:
Originally Posted by Xyzzy View Post
Guinea pigs are cool.
Tasty too!
Uncwilly is offline   Reply With Quote
Old 2007-08-02, 23:15   #8
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

1F2B16 Posts
Default

We read they are actually a food staple for people in some countries in South America. Peru or Chile maybe?

At least if they try to run away they aren't getting very far.

The few we had couldn't even jump (purposely) 2-3 inches. They did tend to have random seizure-like jumps that exceeded that distance but we doubt they could use that to their advantage during an escape attempt.
Xyzzy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Share N+/-1 Primality Proofs wblipp FactorDB 427 2020-11-29 16:52
Leyland Primes: ECPP proofs Batalov XYYXF Project 16 2019-08-04 00:32
Avoidance of self- & other-deception in proofs cheesehead Soap Box 71 2010-01-14 09:04
The GIMPS Status page is going (gone?) to V5... petrw1 PrimeNet 36 2008-04-26 00:48
Collection of Proofs? Orgasmic Troll Math 1 2004-12-30 15:10

All times are UTC. The time now is 10:12.

Sat Feb 27 10:12:14 UTC 2021 up 86 days, 6:23, 0 users, load averages: 1.62, 1.63, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.