Misunderstanding Euclid

Category: things you thought you knew that are wrong
Today's entry is from mathoverflow:

Many students believe that 1 plus the product of the first n primes is always a prime number. They have misunderstood the contradiction in Euclid's proof that there are infinitely many primes. (By the way, 2 * 3 * 5 * 7 * 11 * 13 + 1 is not prime.)

Let's ask Python:

from math import sqrt def f(N): N += 1 print 'N', N n = int(sqrt(N)) for i in range(2, n+1): if not N % i: print i, N/i >>> N = 2*3*5*7*11*13 >>> f(N) N 30031 59 509 >>> N *= 17 >>> f(N) N 510511 19 26869 97 5263 277 1843 >>> N *= 19 >>> f(N) N 9699691 347 27953

What the theorem actually says (wikipedia):

Take any finite list of prime numbers p₁, p₂, ..., p_n. It will be shown that at least one additional prime number not in this list exists. Let P be the product of all the prime numbers in the list: P = p₁p₂...p_n. Let q = P + 1.

Then, q is either prime or not:

If q is prime then there is at least one more prime than is listed.

If q is not prime then some prime factor p divides q. This factor p is not on our list: if it were, then it would divide P (since P is the product of every number on the list); but as we know, p divides P + 1 = q. Then p would have to divide the difference of the two numbers, which is (P + 1) − P or just 1. But no prime number divides 1 so there would be a contradiction, and therefore p cannot be on the list. This means at least one more prime number exists beyond those in the list.

Late nights on the web

This is just a short post to document some interesting links. I recently posted about getting matplotlib installed with minimum fuss on OS X Lion, and this seems to have helped quite a few folks.

The person who showed me how to do this is named Rui Carmo, and I finally found the time to begin browsing through his extensive site; he has lots of good stuff about Macs and other technology (like here).

Perhaps the most interesting thing I found is what appears to be a very high quality company called Linode, offering Linux Virtual Servers in the cloud, their docs include an extensive library related to the topic. I'm thinking seriously about trying it (it only costs just a bit more than the NY Times).

And the final result (of browsing the web on a sleepless night) is to note the profusion of different sites connected to Stack Overflow, including serverfault and superuser. Very rewarding to browse through Q & A, and of course, when I have a question of my own.

One more thing: a pdf form-filler link that is not Adobe. One of the sites I use for work has Adobe forms on it that I can only read through Safari if I have Reader installed as the default pdf viewer. Maybe it will help with this, since I loathe Adobe.

Random Quotes, get your Random Quotes

A nice collection of quotes here. Perhaps my favorite:

"A month in the laboratory can often save an hour in the library."

-- F. H. Westheimer

Advice to a neuroscientist.

Money quote for folks at my place:

Third: learn how to do your own data analysis. Know statistics well. Know at least some basic programming/scripting in Python, R, Matlab, etc. This will be of immense value in helping you get your research done efficiently and correctly, without needing to rely on other people's code (and time and commitment). This will become more important as our field becomes more data driven.

--Bradley Voytek (here)
h/t Tyler Cowen

My prior on the probability that they'll notice? 0.01 :)

Information

I just finished reading James Gleick's new book, The Information (link).

The book features Claude Shannon prominently. It's unusual, including long discussions of (among other topics): African drum language, Charles Babbage, Shannon's information, Turing, quantum computing, and Wikipedia. It's broader and not as technical as I'd hoped, but very enjoyable and highly recommended. Gleick is a talented writer (I loved his book about Richard Feynman and the biography of Newton is also excellent).

Gleick introduces the famous equation from information theory (and entropy)

H = Σp_i log₂p_i

and quotes Shannon:

"The resulting units may be called binary digits, or more briefly, bits."

Gleick:

"As the smallest possible quantity of information, a bit represents the amount of uncertainty that exists in the flipping of a coin. The coin toss makes a choice between two possibilities of equal likelihood: in this case p₁ and p₂ each equal 1/2; the base 2 logarithm of 1/2 is -1; so H = 1 bit. A single character chosen randomly from an alphabet of 32 conveys more information: 5 bits, to be exact, because there are 32 possible messages and the logarithm of 32 is 5."

He goes on to describe a test Shannon performed:

".. in point of fact his test subject was his wife, Betty. He pulled a book from the shelf (it was a Raymond Chandler detective novel, Pickup on Noon Street), put his finger on a short passage at random, and asked Betty to start guessing the letter, then the next letter, then the next. The more text she saw, of course, the better her chances of guessing right. After 'A SMALL OBLONG READING LAMP ON THE' she got the next letter wrong. But once she knew it was D, she had no trouble guessing the next three letters. .. Quantifying predictability and redundancy in this way is a backward way of measuring information content."

Later in the book Gleick describes measuring complexity or information content by asking how far we can compress a message. For example, the message:

DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD

might be given as

Dx50

So it has very little information.

But this example leads to something that's counterintuitive. Namely, the least compressible message is a completely random string of the allowed characters, and by this argument such a string has the highest possible information content. In a way that makes sense, I suppose. If we happen to possess just the right one-time pad, such a message could be very informative. But I find it pretty confusing.

On the stubborn vacuity of the New York Times

I have nothing to add to this.
h/t Jonathan Bernstein (here)

Dropbox

Here is some interesting comment on why people like Dropbox.

Like they say---it just works. I've never understood why iDisk sucks so badly (slow, slow, slow...). And I'm allergic to Microsoft, so Windows live or whatever it is was never even considered.

h/t Brad DeLong---just to show I don't hold a grudge. :)

Sal Khan rocks

I'm always the last person to learn about cool new stuff, so when I say I was scouting around on the web today and ran into Sal Khan and his Khanacademy, I expect you will say, I know about him already. I mean, it's 10,000,000 downloads and counting, or something.

If you don't know, the site consists of a very large number of videos on math, science, economics and a few other topics (here). Since Sal's been interviewed a lot, if I still watched PBS reliably, I would've known about him already. But I decided a while ago to watch as little TV as possible.

Several things to say about the material:

(1) the scope is incredible
(2) the depth is also incredible
(3) the quality is excellent

I'm using it to flesh out what I'm getting from Gil Strang on Linear Algebra.

He also seems to be a really nice guy. Check it out!

More hidden treasure in Python

Saw another "easter egg" for the first time this morning (here).

It was tantalizing enough that I grabbed Python 2.7 from Macports:

> sudo port install python27 > /opt/local/bin/python2.7 Python 2.7.1 (r271:86832, Jan 8 2011, 09:26:04) [GCC 4.2.1 (Apple Inc. build 5664)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> import antigravity

But I don't want to spoil the secret completely.

Hidden treasure in Python

Some fun Python history on this:

> python Python 2.6.1 (r261:67515, Jun 24 2010, 21:47:49) [GCC 4.2.1 (Apple Inc. build 5646)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> import this The Zen of Python, by Tim Peters Beautiful is better than ugly. Explicit is better than implicit. Simple is better than complex. Complex is better than complicated. Flat is better than nested. Sparse is better than dense. Readability counts. Special cases aren't special enough to break the rules. Although practicality beats purity. Errors should never pass silently. Unless explicitly silenced. In the face of ambiguity, refuse the temptation to guess. There should be one-- and preferably only one --obvious way to do it. Although that way may not be obvious at first unless you're Dutch. Now is better than never. Although never is often better than *right* now. If the implementation is hard to explain, it's a bad idea. If the implementation is easy to explain, it may be a good idea. Namespaces are one honking great idea -- let's do more of those!

How was this ever found? It's not in
>>> dir(__builtins__)

What are the odds?

In its breathless way, the New York Times reports today that it is shocked, shocked, at the controversy surrounding the report of arsenic replacing phosphorus in a bacterium (original NYT article; paper's PMID 21127214). (Read the commentary if you don't think the editors were fooled). I saw the original story and thought, "life is too short to worry about this kind of bullsh*t."

My favorite sentence in the original article was:

"Then Felisa found them!" said Dr. Davies

And I was all excited for a while until I read that

Dr. Joyce, however, said that the experimenters had yet to provide a “smoking gun” that there was arsenic in the backbone of working DNA.

And I thought, WTF!

What has become of Science?
I'm very happy to see that my friend (does she remember me?) Rosie Redfield is all over it (here). Go get 'em.

The case against intelligent design

I always make a point of telling my students about the fatal problem that type III secretion poses for Michael Behe's use of the bacterial flagellum as an example of "irreducible complexity" (discussion here).

Today I came across a paper (here) by Joe Felsenstein that was new to me, which deals with the other intellectual force behind Intelligent Design, William Dembski. In classic Felsenstein style, he restates the arguments in a way that starkly reveals their problems. His analogies are simply fantastic. It's very well written, and a must read for anyone interested in bioinformatics.

What's on the shelf

Ten Favorite Books On Science

The Ascent of Man Bronowski
Disturbing the Universe Dyson
Genius Gleick
A Short History of Nearly Everything Bryson
The Making of the Fittest Carroll
Why Evolution Is True Coyne
The Beak of the Finch Weiner
Time, Love, Memory Weiner
Surely You're Joking, Mr. Feynman Feynman
On Becoming A Biologist Janovy
The Log From the Sea of Cortez Steinbeck
At the Waters Edge Zimmer
The Statue Within Jacob
The Number Devil EnzensBerger

So, I couldn't keep it to ten. Sorry.
Check for a good quality used hardback on abebooks.

Boltzmann by Lindley

A very nice book about the history of atoms, and Boltzmann. Although it was out of print, I bought it through abebooks for $$$, because I'd read Lindley's other books. This one is great. And the notation on the withdrawal stamp, simply sad ("out-of-date, no longer needed" ??). It is virtually unmarked.

Moses wrote the U.S. Constitution

wikimedia

Read about it here. All I can say is, holy sh*t!

Don't forget D.C.

I spend much more time on politics than I really should. More precisely, on trying to "suss out" the remarkably large differences between what politicians profess to believe and what they actively support. Also, to try to understand which policies are good ones and what the prospects are for those to be enacted.

One of my favorite sources is Nate Silver's blog FiveThirtyEight, even though he's been absorbed into the currently undistinguished national newspaper of record.

The question arises: why 538?

Because that is the number of electors in the Electoral College. OK. And why is that not equal to the number of Congress critters (435) + Senators (100)? It isn't because of the non-voting delegates (American Samoa, the District of Columbia, the Virgin Islands, Guam, and the Northern Mariana Islands) and one Commissioner (Puerto Rico).

It's because the 23rd Amendment to the U.S. Constitution says:



wikimedia

Progressive politics

Mark Kleiman had a post this morning in which he says

Evolution is just like global warming: each has such overwhelming scientific evidence behind it that denial of either one is strong evidence that the speaker is either ot-nay oo-tay ight-bray or blinded by some prejudice.

This would be a typical statement from "the reality-based community" but it glosses over a point which should be remembered.

Evolution as a theory is on a par with the theory of atoms. The weight of evidence is literally overwhelming. Imagine that TV-personality like Glenn Beck declared his non-acceptance of the theory of atoms. Obviously, no one would care. So why do the media care when he says the equivalent about evolution? It makes no sense from a reality-based perspective, it's just political theater. The really odd thing about evolution is that the average person seem to believe that the evidence can be evaluated by amateurs like himself.

Climate change is more complicated. The evidence that the earth's temperature is rising is unequivocal, according to the experts. The real question at issue is: what part of that change is due to human activity? And perhaps more important for me, what is the prospect for changes in policy in the U.S. or around the world that would have an impact on our carbon footprint.

I remember seeing a video featuring Steven Chu in which he said that his reading of the experts was that there's about an 80% chance that the change is due to human activity. Unfortunately, I can't find the link now, so here's another video in which he gives an estimate of a 50% chance of a 3°C temperature rise in this century and talks about what that would mean. In short, chaos.

With respect to policy, raw political advantage trumps good policy for the republicans (at least right now), so we will likely not achieve anything on this front, even by mechanisms like "cap and trade" that were originally republican "market-driven" ideas. Also, of the estimated roughly 900 billion tons of coal in the world, a substantial fraction is in China, and I expect them to burn all of that.

Is Heinlein a Bayesian?

Brad DeLong had a post yesterday about Robert Heinlein, who I read extensively as a teenager and enjoyed tremendously. The subject was The Moon Is A Harsh Mistress, which I thought was a great story. I like Brad's blog a lot, and learn a lot about economic issues from him, but I thought the post so wrong as to make me question whether he is as knowledgable on other topics as he seems to be.

DeLong says "Heinlein [has a] failure to understand the Law of the Reverend Thomas Bayes," and then approvingly quotes another writer who complains that you can't compute the odds for an event and come up with different answers at different times. But of course this is the whole point of Bayes. If you understand nothing else about the issue, you should realize that what Bayes makes possible is to update probabilities as new evidence becomes available.

So I decided to say something in a comment, nicely I thought. I'm quite mystified to find my comment has been deleted a few hours later. I'll shrug my shoulders and go on, but I am shocked, shocked, first, that Brad DeLong is clueless about Bayes, second, that a whole string of commenters has missed the central point, and then finally that a polite comment pointing this out should be thought subversive. Very weird indeed, and disheartening.

[UPDATE: Perhaps it's just a misunderstanding. The original post says:

I have two problems with Mike. One is the figuring the odds for the revolution. I’d have bought it if he did it once. It’s the complex refiguring and odds changing and—no. People complain about the Dust hypothesis in Permutation City that you can’t calculate things out of order, and this is worse. You can’t work out odds of 7 to 1 against and then say they will keep getting worse until they get better.

The statement about "complex refiguring and odds changing and—no" is just wrong. And you can calculate in any order you like.

But it turns out Brad's objection and maybe this poster's is that they read Heinlein as saying " [the odds] will keep getting worse until they get better." You can't keep getting installments of bad news and say things are looking up.

But that's not how I remember the book. Mike knows things, everything public anyway. Some events break the revolutionists' way early, but a thousand small unmentioned things change the balance. And time is running out. Read the book, and judge for yourself. One of Heinlein's best, along with my favorite, Stranger in a Strange Land.]

[UPDATE 2:

I dug into it a little bit and I am convinced that I'm right. The original post is a very nice review of the book. Great story, but lots of not-PC stuff, characteristic Heinlein. However, it is clear that (1) Jo Walton does not understand Bayes (hence the first part of the quote above) and (2) Heinlein does, at least to the extent he knows how to bet on a horse race, and can appropriately update odds when in possession of new information.

I looked through an online version of the book (pdf) and read all the pages where the word "odds" appears, and nearby. For an example showing Heinlein's understanding, you might read the discussion about the comparative advantage of various strategies depending on the selected time frame (p. 57-58).

The sequence that Brad DeLong thinks damning, that the revolutionists' odds of success are improved after the trip to earth, is just unclear. We're never told what Mike has been "thinking" during this time, or much about what's been happening overall. The evidence used to update the odds is not given to us.

The only counterargument that I could find against my interpretation is based on this dialog on p. 110:

As soon as Stu went Earthside, Mike set odds at one in thirteen. I asked him what in hell? “But, Man,” he explained patiently, “it increases risk. That it is necessary risk does not change the fact that risk is increased."

This doesn't make any sense. But I think Heinlein was probably just seduced by the fact that it sounds a good line. And maybe he is thinking about the time-frame dependence.

The whole rest of the book makes perfect sense from a Bayesian perspective.

Now, I'm not defending Heinlein's political philosophy. There is a lot to complain about (just look at the wikipedia entry for this book). But it's still a great story. Three things irritated me (from most to least important):

• the post held up as a model of correctness was itself wrong on the fundamentals
• DeLong wrongly criticized Heinlein as a mathematical simpleton
• he deleted my comment pointing this out

Too bad no one will ever know. ]

Genes not patentable?

In the news (New York Times) is a ruling in a case before the US District Court for the Southern District of New York (Judge Robert W. Sweet) that invalidates Myriad Genetics' patent on the BRCA1 and BRCA2 genes (article, opinion).

For everyone I know (scientists), the idea of patenting genes---particularly unmodified genes---is ludicrous. It exemplifies the nature of our age, which we might call capitalism gone wild. On the other hand, the first lawyer I talked to (who happens to be my brother) explained to me "that's the way the world works." (I'm paraphrasing). Money talks, and all that.

Here is an excerpt of the article that gives the main themes:

“It’s really quite a dramatic holding that would have the effect of invalidating many, many patents on which the biotechnology industry has invested considerable money,” said Rebecca S. Eisenberg, a professor of law at the University of Michigan who has written extensively on gene patents.

The Genomics Law Report, an Internet journal, called the decision “radical and astonishing in its sweep.” It headlined its article, “Pigs Fly.”

Although patents are not granted on things found in nature, the DNA being patented had long been considered a chemical that was isolated from, and different from, what was found in nature.

But Judge Sweet ruled that the distinguishing feature of DNA is its information content, its conveyance of the genetic code. And in that regard, he wrote, the isolated DNA “is not markedly different from native DNA as it exists in nature.”

Executive summary:

P1 says that a lot of money is at stake (implies patents are good)
P2 expresses incredulity: "Pigs Fly"
P3 summarizes Myriad's core scientific proposition

To be clear, the argument (which is complete and total bullshit) is that the DNA in cells is different than that which has been purified away from histones and other stuff, or cloned in bacteria, or amplified by PCR. It's been "transformed," presto, and is now something different enough to be patentable. Trust me, it's a stretch. Particularly to a geneticist who has spent his whole career thinking about genes as sequences. In my view, today is the day the Emperor discovered he is naked.

P4 Well, I include paragraph 4 because it illustrates for me how silly it is for the New York Times to claim to be the "paper of record." Some time ago, I emailed them to explain that it is not correct to talk about sequencing a genome as "decoding" it, or explicating its "genetic code." I wish I still had the message I received in reply. They explained that they were not interested in one scientist's or even consensus opinion about English usage. The editors felt strongly that their readers would not be comfortable with "determined the DNA sequence of X" and would like the sound of "decoded X." Accuracy be damned.

So there you have it. If you have time, read the decision. Yet another example of the intelligence to be seen on the U.S. District Courts of the nation.

Idiots

They call themselves the "paper of record":

FAA, NTSB Investigate Near Mid-Air Crash Over SF
By THE ASSOCIATED PRESS
Published: March 30, 2010

Filed at 8:21 p.m. ET

SAN FRANCISCO (AP) -- Federal investigators are looking into the weekend near collision of a commercial jet and small airplane that came within 300 feet of each other over San Francisco.
...

The closest the planes came to each other was 300 feet vertically and 1,500 feet horizontally, Gregor said.

(from the New York Times)

>>> math.sqrt(300**2 + 1500**2)
1529.7058540778355