I have just been reading the recently published book "Seeing Further". Edited by Bill Bryson, it contains essays commissioned for the 350th anniversary of the Royal Society. Among the contributors are James Gleick, Neal Stephenson, and Richard Dawkins. The last essay is written by Martin Rees. A cosmologist and science writer, he was president of the Society from 2005 to 2010. On page 476 of the U.S. edition, he writes on how today scientific results are publicized in ways different than even in the recent past:
A few years ago, three young Indian mathematicians invented a faster scheme for factoring large numbers - something that would be crucial for code-breaking. They posted their results on the web. Such was the interest that within just a day, twenty thousand people had downloaded the work, which was the topic of hastily convened discussions in many centres of mathematical research around the world.As readers of this blog know, the result he refers to is the 2002 paper PRIMES is in P by Agrawal, Kayal, and Saxena. Now the point of the paragraph is how the web is changing the way scientific results get promulgated. Still, I thought it odd that he would mis-state the result. He does mention that faster factoring would have cryptographic import so he (or an editor?) has some knowledge beyond what was in the headlines.
My question is: Is it indeed odd that a scientist would not realize that this is a result about decision and not about search, that if a "faster scheme" had been found to solve the search problem then even a very quick literature search would have turned about up quite a bit more about the code-breaking implications?
This is, unfortunately, typical.
ReplyDeleteA recent article by Freeman Dyson in the Notices of the AMS (!) confused decision problems with search problems, and P with NP.
A 1994 book by Nobel prizewinner (in Physics) Philip Anderson claimed that NP stands for "not polynomial" and that linear programming is NP-complete.
A book by physicist Paul Davies claimed that quantum computers could solve the traveling salesman problem efficiently.
And mathematicians routinely assert claims like "There is no formula for the prime numbers" without bothering to inquire about what this would mean.
I would like to propose the following maxim, which I modestly call Shallit's Law of Computational Ignorance: "Whenever a non-computer scientist makes an assertion about computational complexity, it is nearly always wrong."
Maybe it was an ironic, and very sophisticated, way of making the point that, on the web, a result can travel, and its correctness be checked, within days, but, via books, it takes years and, even so, mistakes are not checked.
ReplyDeleteAs another comment, I find the "three young Indian mathematicians" weird. I am not saying that Manindra Agrawal was old in 2002 (nor is he right now!), but he was of course not young in the same sense as Neeraj Kayal and Nitin Saxena were. This is just to mention that my impression is that Martin Rees speaks about the AKS paper mostly by hearsay.
ReplyDeleteYet the question to know whether this is a big deal is left open.
The real question is, why did the Royal Society choose Bill Bryson as the editor for their book?
ReplyDeleteHe probably read an article about the paper, saw the important bits: 3 guys from India came up with an algorithm, many people from around the world were reading it within a day, the topic is related to cryptography. Why read further to get all the facts right once he has enough information to support his thesis?
ReplyDeleteJeffrey Shallit said: "And mathematicians routinely assert claims like "There is no formula for the prime numbers" without bothering to inquire about what this would mean."
ReplyDeleteWhen I was still in the Air Force, self-teaching myself algebra with whatever scraps I could find at the base library (an ancient group theory book by Rotman), I read in that book a breathless claim that "no formula is known for the number of isomorphism classes of groups with n elements". I quickly came up with such a formula, one which was of course absolutely useless computationally and basically amounted to "programming" the function in a formula instead of in a programming language*. I thought that was a really big deal, like I'd solved some big open problem, though now I understand what I did was quite trivial.
*(In my undergrad paper here, I give a method for finding formulas for any computable function. The results are of course quite useless computationally!)
Stuart Kauffman, a 'complexity theorist' of the Santa Fe Institute variety, wrote an (IMO) awesome, inspiring book, 'The Origins of Order', in which he nevertheless identified NP problems as 'non-polynomial'.
ReplyDeleteIn popular news, it is often boiler-plate when discussing any topic in number theory --- even something like proofs of the Riemann Hypothesis --- to add some comments about this may have great implications for code-breaking and/or code-making. This particular example is no worse an offender than usual.
ReplyDelete@David: Sharing the general sentiment, but then there is some connection between (forms of) the Riemann Hypothesis and number theoretic algorithms.
ReplyDeleteThus, mentioning some (vague) connection between RH and 'code-breaking' is not completely wrong.
While saying AKS is on factoring is just wrong; leaving aside the fact that, as far as I known, while a great theoretical achievement, the 'practise' of deciding primeness was not that much influenced by it.
Sorry, in case I got the details (or verything) wrong. I'm only a mathematician trying to prove Jeffrey Shallit right.