Recursivity

Prime numbers -- the positive integers that are only evenly divisible by themselves and one -- are the multiplicative building blocks of the integers. The "fundamental theorem of arithmetic", proved by Gauss in 1801, states that every positive integer can be written as the product of primes in exactly one way (up to reordering of the factors). For example, 1001 is 7 x 11 x 13, and each of the factors are primes, and there is no other way to write 1001 as a product of primes, other than trivial rearrangements such as 11 x 7 x 13. Note that 1 is not a prime number; it is the "empty product" of no prime factors, and it's called a "unit" by mathematicians. There are 25 primes less than 100:

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89, and 97.

Prime numbers have attracted a lot of attention throughout mathematical history. As long ago as 250 B.C.E., Eratosthenes gave a method for determining all the primes less than a given limit, now known as the sieve of Eratosthenes. Write down the numbers down from 2 up to n. Circle the number 2. Now cross off every second number after 2: 4, 6, 8, etc. Look for the smallest uncrossed-off, uncircled number. It is 3. Circle it, and cross off every thrid number after 3: 6 (which was crossed off earlier), 9, 12, etc. Now again look for the smallest uncrossed-off, uncircled number. It is 5. Continuing in this fashion, we get a list of all the primes up to n.

In recent years, there has been lot of progress in understanding the primes. For example, in 2002, Agrawal, Kayal, and Saxena found a very efficient method of determining whether a number is a prime. It runs in polynomial time; that is, the number of steps to determine if a number n is prime is bounded by a polynomial in the number of digits of n. And just this year (correcting two previous versions that were incorrect), Goldston, Motohashi, Pintz, and Yildririm proved that the smallest possible gap between a prime p and the next-larger prime grows more slowly than log p. This is a small step towards proving the "twin prime conjecture", which says that there are infinitely many primes p such that p+2 is also prime.

Despite this progress, many open problems about the primes remain. For example, while it is known that there are infinitely many prime numbers, no one knows if there are infinitely many primes of the form 2^p - 1. These are called Mersenne primes, after the 17th century French priest who studied these primes (and made some incorrect claims about them.) Mersenne primes are interesting because they are particularly easy to test for primality, and because of their relationship to an historical problem in number theory, the perfect number problem.

A positive integer is perfect if the sum of its divisors is equal to twice the number. For example, the divisors of 6 are 1, 2, 3, and 6, and they sum to 12, which is twice 6. No one knows currently if there are infinitely many perfect numbers, but Euclid (around 300 B.C.E.) noted that if 2^p - 1 is a prime number, then (2^p - 1)2^p-1 is perfect, and Euler proved that all even perfect numbers are of this form. No odd perfect numbers are known, but there is still no proof that none exists.

Now a new Mersenne prime has been found: 2^30402457-1. This immense number of 9,152,052 digits was discovered by Curtis Cooper and Steven Boone at Central Missouri State. This is the largest known prime number and the 43rd known Mersenne prime.

To get some idea of the recent progress in finding Mersenne primes, when my book Algorithmic Number Theory was published in 1996, we included a table of the largest primes known throughout history. We stopped with 2⁸⁵⁹⁴³³-1, the 33rd Mersenne prime. Since then, 10 new Mersenne primes have been found! What accounts for this progress?

Largely, it is distributed computing. The GIMPS project ("Great Internet Mersenne Prime Search") coordinates factorization efforts by thousands of computers worldwide. While there are millions of computers, few are actually doing anything useful at any given time. The genius of GIMPS is to harness these unused cycles to find new large primes.

I'm often asked, what is it good for? The answer is -- like a painting by da Vinci -- nothing, really. It adds to our knowledge about Mersenne primes, but it probably will never lead to a proof that infinitely many Mersenne primes exist. Nor does knowing large Mersenne primes contribute to cryptography. But -- again like the da Vinci painting -- the subtle mysteries of the primes have a worldwide and longstanding appeal.

I live in a community (Kitchener, Ontario) with a lot of religious fundamentalists -- more than any other place I've ever lived. And they write letters to the editor. Really stupid letters. Really stupid letters about evolution.

Take this example, from the Record, December 27, 2005, by "R. F. M., P. Eng.". (P. Eng. means "professional engineer" -- another piece of data for the Salem hypothesis.)

The ruling by Judge John Jones in the District Court of the U.S. to exclude intelligent design from the scientific classroom is appalling.

If evolution is to be taught, and it should be, then creation should be taught in the same classroom.

Oops, Mr. M. Didn't you know, intelligent design isn't creationism? The Discovery Institute says so, so it must be true. Get with the program!


Many people wrongly elevate the study of evolution to some exclusive level.

Yes. It excludes morons.

From a scientific perspective, both creation and evoution are hypotheses or theories only, and that is all that they will ever remain.

From a scientific perspective, creation is a myth. And please, not the oldest canard in the creationist playbook, evolution is just a theory. That one's so dumb, even some creationists say their fellow creationists should avoid it.

Science can be used to explore either theory, but neither evolution nor creation conform to the scientific method because, essentially, they can neither be repeated or observed.

I agree that creation by supernatural beings hasn't been observed. But it is simply false to claim that evolution hasn't been observed. See here and here, for example.

Unlike gravitational, thermodynamic, hydraulic, chemical, biological, structural, electrical or other laws about our universe, the study of our origins will always be outside the realm of scientific proof.

Whenever you hear anyone babbling about "scientific proof", you know they have no idea what they're talking about. And if evolution isn't part of biology, what is? And what is a biological law? This guy's becoming totally incoherent.

Does it matter what our schools teach about our origins? It sure does. It shapes our entire world view.

How do we teach our children, for example, to adopt moral accountability if we teach them that they are no more than the chance product arising out of the muck and slime of a primordial Earth and that their ancestors are monkeys and amoebae?

That our ancestors were monkey-like creatures is a fact. I don't know why Mr. M would have us lie to schoolchildren and tell them otherwise. But then, Mr. M is apparently such a moral reprobate that he cannot behave properly without a supernatural being around to make sure he conforms to the law.

When I look at the world today, I sure don't see that Christianity is doing such a good job on the moral accountability front. And I don't know any criminals who got their start in evolutionary biology class.

The pathetic irony in all of this is that it is the same God of creation who is the God of all science.

Mr. M, you probably believe that God gave you a brain. Why not use it?

For those of you kind enough to leave comments on this blog -- thanks a million. I really appreciate them. If you were wondering why they didn't appear before now, it's because I'm new to the blog biz and didn't understand how to approve them. Now that I do, you can expect to see more.

By the way, here's the policy for comments: basically, anybody can post anything that's relevant, provided it's not ridiculously over the top or pure self-promotion (such as ads for other sites). I have a pretty high tolerance level. Unlike Dembski, I genuinely welcome criticism, even really harsh criticism.

A professor, as you know, is someone who thinks expertise in one area allows him to pontificate in all areas -- so many times I'll need correction by those who know more.

Still jacking in from Oswego, New York...

Addendum, posted January 2 2006:

Comments are moderated -- that's why they don't appear immediately when you provide them. There's no need to post your comments more than once -- I'll get to them eventually. Extra copies of the same comment will be ruthlessly deleted.

Addendum, posted December 21 2008:

Comments that are essentially just ads for other blogs or web sites that don't interest me will be ruthlessly deleted, as will comments that insult members of my family, or include gratuitous insults or threats of violence.

Tom Bethell, ignoramus extraordinaire, has had a problem with evolution for thirty years now. But in all that time, it seems he hasn't bothered to learn much about it. In his latest screed in the Washington Times, Bethell resorts to the usual creationist tactics: lies, distortions, omissions, and misrepresentations.

Starting from the very first sentence, Bethell is dishonest. It's not just "Darwinists" that are happy about the ruling in Dover, it's scientists of all stripes, not to mention those who respect the Constitution. And contrary to Bethell's claim, there's no free speech concerns: intelligent design can still be discussed in high school philosophy or religion classes -- it just can't be falsely represented as science.

Bethell claims that intelligent design has advanced because "a sizable number of Americans are capable of reading and thinking for themselves". Yet intelligent design has not made many inroads outside of the US. Are we to conclude that Americans, and only Americans, are capable of "reading and thinking for themselves", that those in Canada, England, France, Germany, Australia, the Netherlands, Italy, and Spain are all under the grip of some thought control imposed by jackbooted thugs? Or could it be that fundamentalist religion is the key to intelligent design's advance, and those other countries are largely free of that scourge?

Next Bethell goes off on a wacky tangent, claiming that legislatures and courts tried to make "liberalism ... compulsory and its rivals illegal". Not a single example is advanced to support this crackpot claim.

Now it's time to bring in the usual creationist lies. Bethell babbles about "the paucity of the fossil record", the lack of transitional forms, and the supposed impotency of the "Darwinian mechanism" to account for the diversity of life. Bethell doesn't let the fact that no reputable biologists would agree get in his way of this nonsense.

Next Bethell implies that computer science and information technology have raised difficult questions for Darwinism. This will certainly be news to my colleagues in bioinformatics in the School of Computer Science at my university. Nearly everything they do is based on evolution, and they do it successfully (search for Ming Li and Dan Brown in the bioinformatics literature). Bethell makes the claim that DNA cannot have arisen "by accident, but accident is the only method available to the evolutionists". Of course, this claim completely overlooks the fact that living things function according to the laws of physics and chemistry, which are largely not stochastic and cannot be reasonably termed an accident.

Bethell quotes Francis Collins and Bill Gates as backing up his argument, but doesn't present any evidence that either man denies evolution or supports the claims of the intelligent design movement. Next he cites Antony Flew, but fails to point out that Flew has in the meantime backpedaled from his previous rejection of naturalistic solutions to the origin of life.

All in all, it's a really poor and dishonest performance by Bethell, who has been making the same bogus claims without any support for years. And who publishes his latest book? Why, it's Regnery Publishing, the same folks who published the Swift Boat slime, the nutsy ramblings of Phyllis Schlafly, and Michelle Malkin's grotesque defense of the internment of Japanese during World War II. Yup, just the place I'd go to learn about science.

Jacking in from Oswego, New York...

Hold the presses! Convicted Watergate criminal Charles Colson doesn't like the Dover decision!

I'm sure that came as a big surprise to everyone. But go read it anyway.
I like this line: "...this tells us what has to be done in other cases if we are going to succeed." Yes, Chuck, it means you've got to lie to conceal your religious purpose even better than the Dover board did.

Colson points to another page as the kind of "material that will equip you well to make a case—a case that is strong and will withstand constitutional challenge." Here's what that page says:

When we talk with our children and our neighbors about evolution, we must focus on the fundamental assumptions that generate the evolutionary story. We must make sure they understand that the real debate is between two creation narratives: between one that says, "In the beginning were the particles," and one that says, "In the beginning was the Word, and the Word was with God, and the Word was God; all things were made through him."

Oops. Listen Chuck, you screwed up big time. If you want to hide your religious purpose, you really gotta stop bringing in that "In the beginning was the Word" stuff.

Well, what can we expect from the former "evil genius" who suggested firebombing the Brookings Institution? He's still a criminal -- but now he's a criminal for Jesus.

You may remember Mohammed Elmasry, the University of Waterloo professor who claimed that Israeli citizens were fair game for Palestinian attacks. (He later apologized for the remarks.)

Well, he's back in the local paper again. Today's Kitchener-Waterloo Record reports the following remark regarding the recent Canadian Supreme Court decisions legalizing swinger's clubs (R v. Labaye and R v. Kouri): "This decision doesn't reflect attitudes of most Canadians and it's doing more harm than good." Well, gee, the last time I looked, the Canadian Charter of Rights and Freedoms didn't say, "The following rights are protected, provided most Canadians agree". The whole theory behind enshrining civil rights in a document like the Charter is that those rights can't be taken away just because most people disapprove. As Robert Jackson remarked in the flag salute case, "The very purpose of a Bill of Rights was to withdraw certain subjects from the vicissitudes of political controversy, to place them beyond the reach of majorities."

But wait, the irony factor gets bigger. The Record also reports, "Elmasry ... said the ruling only protects the interest of a small minority." Now consider that Elmasry is the "Chair and National President" of the Canadian Islamic Congress, and he's been quick to attack any perceived slight against the rights of Muslims. Well, aren't Muslims just a "small minority", too? Elmasry doesn't seem to understand that the Charter of Rights and Freedoms protects Muslims and other minorities.

Here in Canada we're an ecumenical bunch: busybodies of all religious persuasions disapprove of your right to have consensual sex in the way you want.

This release from Health Canada is yet another warning that just 'cause the label says it's "natural", that doesn't mean it's safe to ingest.

Decisive as it was, the Dover victory won't end the push to get religion into public schools in the guise of science--our opponents are too fanatical for that. Tom Toles nails it.

First, it was Dembski and Meyer who bailed out of testifying in the Dover intelligent design trial. Then John Angus Campbell. Then Warren Nord and Dick Carpenter. Now yet another rat has deserted the Good Ship Dover: Pennsylvania Senator Rick Santorum. Read more here in the Philadelphia Inquirer. The bad news is that Santorum apparently still believes intelligent design is legit science. Well, what can you expect from a man who blamed the Boston pedophile priest scandals on liberalism? In our kakocracy, Santorum is one of the head rats, leaving a disgusting trail wherever he goes.

Whenever NPR needs a reliably ignorant voice from the Religious Right, they turn to their man at the Heritage Foundation, Joe Loconte. His most recent contribution, Intelligent Design Has a Place in the Classroom, is typical.

Contains No Original Ideas: Loconte's main argument just echoes the testimony of Michael Behe at Dover, saying that intelligent design today is just like the Big Bang 70 years ago: originally resisted by scientists because of its religious implications, then ultimately accepted because of the evidence.

Repeats Platitudes Uncritically: In echoing Behe, Loconte didn't bother to investigate whether Behe's claims were true. Is the Big Bang really like intelligent design?

Not really. The Big Bang theory is supported by multiple, independent lines of evidence: the cosmic background radiation, Olbers' paradox, Hubble's law, isotropy, deuterium and lithium isotope abundance, etc. In turn, these lines of evidence are supported by dozens of scientific papers published in the peer-reviewed literature. Intelligent design, on the other hand, is not supported by any papers in the peer-reviewed literature.

Furthermore, many of the arguments against the claims of intelligent design are scientific. In my own contribution to Why Intelligent Design Fails, for example, I focus on the mathematical mistakes of William Dembski. There's nothing in my contribution about the "religious implications".

Another way the Big Bang history differs from intelligent design is the hype behind the latter. Those advocating the Big Bang didn't hire public relations firms, or demand to get their theory included in high school physics textbooks. Instead, they concentrated on finding evidence to support their hypothesis.

Makes False Statements: Loconte says "the court ruling in the Dover case claims that the question of intelligent design is settled". Only someone who didn't read the ruling carefully could make that claim. The judge did not say the question was settled. On page 137, Judge Jones says "Nor do we controvert that ID should continue to be studied, debated, and discussed." On page 64, Jones admits that "ID arguments may be true". What the judge did find was that intelligent design was not science, a conclusion he supported with abundant evidence presented at the trial. How can Loconte miss such an obvious point? Is it stupidity, or willful blindness?

Doesn't Understand the Issues: Loconte says he's not a physicist. Well, that's a relief. It explains why Loconte doesn't seem to understand that the existence of a cosmological constant could still allow an expanding universe; the crucial thing is the magnitude of the constant. He derides the cosmological constant as Einstein's mistake, but doesn't seem to understand that its existence is still an active subject of study and debate. Loconte laughs at the description of intelligent design as "the progeny of creationism", without noticing the pages and pages of trial transcript that established exactly that.

All in all, it's more breathtaking inanity from Loconte. Why does NPR continue to give him air time?

When I was a teenager, Saturday morning was one of the few times I was allowed to watch television. One of my favorite shows was Scooby Doo, Where Are You?, the cartoon featuring teenage detectives and their lovable half-articulate dog. Of course, it was formulaic. Velma's glasses always got knocked off at a critical moment, Fred and Daphne always wore the same clothes, Scooby could always be induced to participate in some ridiculous plan by being offered a Scooby snack, Daphne could be depended upon to get nabbed by the bad guys, the kids' plan to trap the criminals was always ridiculously complicated and failure-prone, but succeeded anyway, and the villains always complained at the end that they "would have gotten away with it if it hadn't been for those kids and their mangy dog". But one thing I didn't realize that the time, and have grown to appreciate, is the subversive skepticism of the first two seasons.

Skepticism, because no matter how supernatural the mystery appeared at first glace (and they were usually populated with ghosts and vampires), the end result was always the same: there was a perfectly reasonable natural explanation, usually involving a plot to scare people away from a location where some nefarious activity was going on. (But never too nefarious; they didn't want to scare away the kids.) Ghosts weren't really ghosts; they were people dressed up as ghosts. Vampires were't really vampires; they were people with fangs on, together with bats bought at the local exotic pet store. And while Scooby and Shaggy were usually credulous, Velma and Fred used reason to solve the mystery. They didn't say to themselves, "Oh, it's a ghost, that explains it." They said, "Hmm, I wonder if there is some reasonable explanation." This was the best skepticism on television until MythBusters.

Subversive, because the underlying message was contrary to many, perhaps most, Americans' perception of the world. A recent survey shows that 32% of Americans believe in ghosts and 37% believe houses can be haunted. And of course, 90% to 95% of Americans believe in the ultimate supernatural folly, god. In always providing a natural explanation, the subtext was clear: the supernatural doesn't exist, and scientific reasoning is the best tool to ascertain truth. That's a message directly in opposition to an America populated by Pat Robertsons and George Bushes.

But like all good things, this subversive skepticism had to come to an end. A few years ago, when one of my kids was sick, and he didn't want to hear another story read to him by Dad, I rented a Scooby Doo movie to try to keep him entertained: Scooby Doo on Zombie Island. I was really horrified to see that the basic premise of Scooby Doo had been violated: this time, the zombies were real. My kid was so scared we had to turn the video off. While Zombie Island had some good points (making fun of the show's repetitive themes), I was saddened by the sell-out to the paranormal.

The first two seasons are still watchable, and can be found on DVD. If you know any young skeptics (or even young believers), buy them a copy.

I thought all that could be said had been said about yesterday's tremendous legal victory in Kitzmiller v. Dover, but I was wrong. The York Daily Record's Mike Argento, the 21st century Mencken, is worth reading. Now.

I am currently the director of graduate studies for my department. Applicants for graduate study -- and there are hundreds each year -- must complete a personal statement that describes their interests, and I get to read them. One thing I've noticed is the contrast between the statements written by Chinese and North American applicants.

The personal statements by North Americans tend to be fairly prosaic, listing their interests and achievements. But the statements from China are often unabashedly passsionate. Here's a typical example:


The important thing in life, I believe, is to have a great aim, and the determination to achieve it. After developing a strong connection with the world of computer science while still in high school, choosing computer software was the most natural step to me upon enrolling in college. During my undergraduate studies, as the world of computer science began to unveil before me, I felt that every step I took within this world served to deepen my interest in scientific work and my commitment to becoming a scientist. As I accumulated more knowledge and skills, my confidence in working with cutting-edge computer technology was strengthened, and the time and efforts I have put into these studies have helped build my current aspirations -- I am now eager to climb to the heights of intellectual achievement through pursuing Master and Ph.D. in computer science, which, I hope will enable me to push forward myself to the forefront of computer science and technology.


Some may find this flowery language laughable. I find it wonderful. The Chinese applicants are determined. They are passionate and not afraid to show that passion. A North American student expressing similar sentiments would be worried that people (even those who read the applications) might laugh at him (or her).

Intellectual achievement just isn't cool in North America. Is it a relic of the frontier society, which respected brawn over brains, or a result of fundamentalist religion that stresses revelation over reason? I don't know. But I do know that unless North America makes it possible for people to passionate about mathematics and science without being ashamed, we're in deep trouble. While we're arguing about whether to include intelligent design in schools, the Chinese will be pursuing genuine scientific research and reaping the fruits of that pursuit, and we'll be left behind.

Welcome to Recursivity!

This blog is an outlet for my thoughts about mathematics, science, politics, music, religion, and other subjects. I hope you'll want to visit again and again and again and again and...

I am a professor of computer science at the University of Waterloo. My research interests include combinatorics on words, finite automata, number theory, algebra, formal languages, history of mathematics and computer science, ethical use of computers, and pseudoscience and its practitioners. In my spare time, I like to read, hike, play with my kids, play the guitar, play chess, write angry letters to the editor, watch movies, listen to NPR, and go hunting for interesting rocks and minerals. But not all at the same time.

I also blog occasionally at The Panda's Thumb, a pro-science blog.