Saturday, January 07, 2006

A Search Without End

Finding the 5th moon of Jupiter was a big deal. Finding the 14th moon was a big deal. But it's hard to get excited about the 63rd moon. Now imagine if Jupiter had an infinite number of moons.

New York Times, August 29, 1989

After more than a year of computation, six researchers at a California computer company have found the largest known prime number, which is 65,087 digits long and would fill more than 32 double-spaced typed pages.

While the search for the largest prime may seem like an esoteric pursuit, one of the researchers, Landon Curt Noll, said the work that permitted them to discover the number has a wide variety of commercial and scientific applications.

Associated Press, March 31, 1992
Mathematicians using a supercomputer have advanced the quest of a 17th-century French monk (Mersenne) by discovering the largest known prime number. The number begins 174 135 906 820 087 097 325 and goes on and on and on for 227,832 digits, filling 32 pages of computer paper.

Jeffrey Lagarias, a mathematician at A.T.& T. Bell Laboratories in Murray Hill, N.J., said that the discovery might have some significance in pure number theory but that "it's not going to revolutionize anything."

New York Times, March 29, 2005
An eye surgeon in Germany has discovered the world's largest known prime number—or at least his computer did. The surgeon, Dr. Martin Nowak of Michelfeld, is among thousands of participants in the Great Internet Mersenne Prime Search, one of several big projects that tap idle computers worldwide. The number, rendered in exponential shorthand, is 225,964,951-1. It has 7,816,230 digits, and if printed in its entirety, would fill 235 pages of this newspaper.

"Finding an additional prime doesn't enlighten us very much," said Dr. Andrew M. Odlyzko, a mathematician at the University of Minnesota.

Associated Press, January 3, 2006
Researchers at a Missouri university have identified the largest known prime number, officials said Tuesday. The number that the team found is 9.1 million digits long. It is a Mersenne prime known as M30402457—that's 2 to the 30,402,457th power minus 1.

The team at Central Missouri State University, led by associate dean Steven Boone and mathematics professor Curtis Cooper, found it in mid-December after programming 700 computers years ago. "We're super excited," said Boone, a chemistry professor. "We've been looking for such a number for a long time."



  1. From "The new prime is 9,152,052 digits long. This means the Electronic Frontier Foundation $100,000 award for the discovery of the first 10 million digit prime is still up for grabs!"

    And from "The Electronic Frontier Foundation (EFF), the first civil liberties group dedicated to protecting the health and growth of the Internet, is sponsoring cooperative computing awards, with over half a million dollars in prize money, to encourage ordinary Internet users to contribute to solving huge scientific problems."

    Perhaps "ordinary Internet users" get interested in (scientific) computing.

  2. What do you mean Why?. Perhaps these guys know something about the number that you don't. To you it seems a useless quest because, I presume, "it does not seem to have any application". But that is a subjective question whose answer depends on who you ask. What seems useless to you may seem useful to a mathematician. And what seems immensely useful and important to you may be totally useless to a more empirical person.

  3. Dr. Odlyzko wrote:

    ". . . Finding an additional prime doesn't enlighten us very much . . ."

    The search itself may be uninteresting to some, but it is a hobby to others.

    Much like Sudoku (known as Number Place in Dell Puzzle books for 15+ years until the recent marketing wave and popularity increase) and a sense of accomplishment upon completion of a puzzle, finding a big (and I use that term loosely) prime number probably provides that same sense. Again, like Sudoku, the search for primes is the application of known algorithms to the search space, as opposed to the discovery of new theory. Like other forms of "mental golf", I think it is healthy.

  4. "But that is a subjective question whose answer depends on who [sic] you ask."

    This attitude implies that no research is any more or less valuable than any other. Viewed in this light, it seems clear that either some other justification is required or all our jobs are in jeopardy.

    There are several obvious, though, perhaps, not entirely satisfactory answers: It is a mathematical achievement that the lay person can easily understand (this is evidenced by the fact that clips describe the size of the prime in terms of how many pages it fills, hardly a scientific explanation). The previous commentator gives another explanation. Finally, new concepts may be conquered in the quest to find such numbers (such as distributed computing, Mersenne primes, or other things I don�t really understand or care much about).

  5. "This attitude implies that no research is any more or less valuable than any other."

    But who is to judge whether a piece of research is valuable or not? One popular (though not always correct) judge of the usefulness of research is whether it has immediate applications, or whether agencies like NSF fund you for your efforts. But that is hardly a good judge of the value of a piece of research, is it? Viewed this way, research in abstract mathematics would cease to exist.

    Not that finding large primes is in any way abstract mathematics, but this debate brings about an interest ing question "What is good research?". I wish that Lance would start a blog entry on this to solicit more feedback from his readers on answers to this question.

  6. Progress on finding larger and larger prime numbers used to involve a mix of mathematical ingenuity and engineer prowess. But these days, it basically scales with the power of emerging technology. On the other hand, I think it would be difficult to argue that the task of finding large primes _drives_ the emergence of technology. In this sense, finding larger primes is merely a symptom of better technology, and thus wouldn't be classified as research.

    Advances in factoring larger and larger composites, on the other hand, often involves significant mathematical breakthroughs.

    Hopefully this is a clear enough distinction to justify Lance's point.

  7. Lance's point is that there will always be a larger prime number to be found, no matter how many we find.

    I predict it will still be big news so long as the findings sound like a heroic effort (using 700 computers over many years *is* heroic). After that, it will only be special barriers or special awards that will get any attention. Finally, perhaps it'll happen so frequently and predictabley that it could not even by definition be considered news.

  8. "Lance's point is that there will always be a larger prime number to be found, no matter how many we find."

    I hope this is not Lance's point, because it's not a very good one.

    By the same reasoning:
    "No matter how many theorems we prove to be true, there are always more to be found, thus why do mathematics at all?"

  9. Actually, I think Lance's point is an excellent one; I wondered why this even made the news. And I don't understand why people are rushing to defend this result as some sort of great research --- it's not. (And the pseudo-relativist claims that "no one has the right to judge what is valuable research and what is not" are silly --- would you say the same thing about intelligent design? Besides, we do exactly that every time we are on a program committee or funding panel...)

    If you defend this research then please give a reason (he, I might be wrong...), rather than just suggesting that there might be one.

  10. "No matter how many theorems we prove to be true, there are always more to be found, thus why do mathematics at all"

    That's a bad analogy. Theorems are more or less interesting, and there is a fair degree of consensus on what's interesting and what's not. As far as prime numbers are concerned, the question precisely is: why should a prime number be interesting because it's the biggest one we can discover at the present point in time using a certain technology?

    The claim could be made that these newly discovered numbers are interesting for additional reasons. Perhaps the purpose of the post is to move the debate in that direction...

  11. It wasn't meant to be a complete analogy. I am in agreement that finding larger primes is not very exciting. On the other hand, factoring larger and larger composites is interesting for a number of reasons, if only so that we know how strong our cryptography has to be, but also because reductions in the exponent of factoring algorithms often require significant mathematics. So the response "It's not interesting because we'll never run out of numbers" isn't very effective.

  12. Perhaps finding the actual prime number is uninteresting but that doesn't necessarily make the research involved uninteresting. Maybe its an application of a powerful new distributed technique. What if the research led to an "evil" computer proof of the twin prime conjecture or some other deep insight into prime numbers in general? It's a bit harsh to criticize the researchers involved without knowing their real goals.

  13. I think people are missing the point here: If Jupiter had an infinite number of moons, that would be really exciting.

  14. If Jupiter had an infinite number of moons it *would* be exciting, at first. At one point it was exciting to prove that there are an infinite number of primes. Now any undergrad math major can give you that proof.

    But each new moon found, provided it didn't use any heroics to do so, would not be news! In fact... it would be news if no new moons could be found.

  15. Well clearly there is still utility in searching for a sense of humor.

  16. Dilbert's internet debate rule #5: "Assume the dumbest interpretation. For example, if someone says that he can run a mile in 12 minutes, assume he means it happens underwater and argue that no one can hold his breath that long."

  17. I happened to be reading "A Mathematician's Miscellany" by the great English mathematician Littlewood last night, and came across a rather excited discussion by Littlewood of the (then) state-of-the-art in finding large primes. It'd be interesting to know what got Littlewood so excited.

    Michael Nielsen

  18. Littlewood was quite concerned with the distribution of prime numbers, and thus probably saw the ability to find larger and larger primes as a great way of generating "experimental data," much the same way as a physicist might champion the building of the next generation of particle accelerators.

  19. "... perhaps it'll happen so frequently and predictabley that it could not even by definition be considered news."

    I doubt it. Things like this will always make news. Maybe just finding the largest known prime will cease to be newsworthy, but finding a prime that has, say, ten times as many digits as the largest previously known prime will always be. Aside from the question of whether this is good research (or even research at all), the public easily grasps the results as new milestones in technology.

  20. I agree with the meta-question:
    "What do you mean Why?"

    Why did they do it?

    Who knows. Maybe they like holding the record for biggest prime number. People like holding records. It's nice to be the best at something. I'm enough of a geek that I think having found the biggest prime number on record would be a very cool thing.

    Why would it be considered good research?

    I'm not sure anyone actually said it was. My experience suggests that when something scientific appears in the news, that does not mean it's good research, and of course lots of worthy research never makes the news!

    It may be good research, or it may just be an exercise in taking old research and doing it on shinier, newer machines. I don't know enough to say. From the comments, I'm not sure anyone else really has any compelling argument one way or another.

    Why would this be in the news?

    People can understand it. Most laymen know what a prime is. Finding big primes for a long time was something of a computational challenge problem, so many people (including perhaps science writers for the newspaper) can grok the story. They can imagine that finding big primes represents some sort of mathematical progress. We might suspect that it really doesn't, but so what? It apparently sells newspapers.

    Hey, I've got a why question!

    Why don't we in CS theory do a better PR job and get articles like this -- or even better ones! -- in the papers describing our work?

  21. I wonder - what's the largest known composite number? And why do they never make the news? :-)

  22. I really dislike how they find a Mersenne prime and then brag about how it takes so and so many pages to write down. These numbers have too little Kolmogorov complexity to be taken serious :)

  23. The search for a new microscopic lubricant for use in the computer field led to the (accicental) discovery (in a rather embarrasing way ) of................

    ........Super Glue , one of the most valueable daily use products known to us simple minded non expansive carbon based , opinion biased homosapienic spiritual wannnabe`s

  24. "I doubt it. Things like this will always make news."

    It used to be news when a graphics scene was rendered by a computer. Now thousands of CGI are generated every hour.

    The point is that it's not at all about how important it is. It's important that everyone stop at red lights. It's important that children get taught. None of these are news worthy because they are an expected part of daily life. It's only the exceptions that make it news.

    (Which, obviously, could be about an exceptional teacher, about an intersection that's rated the safest in the world, yes, yes, we are all clever and can think of obvious exceptions to points.)