Wednesday, December 31, 2008

Messianic Jews, The United States Military and The First Amendment.

Jews in Green recently reported that the U.S. military is requiring Messianic Jewish chaplains to wear on their uniforms crosses, the standard Christian symbol, rather than a small pair of tablets, the standard symbol for Jewish chaplains. The military has yet to issue an official statement. This report raises a variety of First Amendment issues.

A bit of background: Messianic Judaism is a movement composed of individuals who claim to be both practicing Jews while they accept Jesus as Messiah. While there is variety among the various Messianic groups, most have beliefs very similar to the beliefs found in Protestant Christianity. In particular, Messianic Jews emphasize the divinity of Jesus, not just his messiahood , and emphasize their acceptance of Jesus as their personal lord and savior. Additionally, many Messianic Jews (according to some sources, a majority) are not halachically Jewish and a substantial fraction have no actual Jewish heritage, but are Christians who have decided to identify as Messianic Jews for a variety of reasons. The Jewish element of Messianic Judaism comes from many of them keeping some degree of Kashrut and some Sabbath observance starting on Friday and ending Saturday night. Mainline Christian denominations, most evangelical Christians and almost all Jews consider Messianic Judaism to be a form of Christianity, not Judaism. There is a perception among many Jews and Christians that Messianic Jews have been deceptive in their proselytizing practices and have presented themselves as a standard form of Judaism, particularly to Jews who have little background in Jewish knowledge.[i]

Michael Hiles, a self-identified Messianic Jew, was training to become a Navy chaplain. He was informed that he would be required to wear the cross on his uniform rather than the small pair of tablets representing the Ten Commandments, which is the symbol for Jewish chaplains. Hiles objected , and, after unsuccessful appeals up the chain of command, ceased training to be a chaplain rather than comply.

These events raise a variety of questions. I will examine two of these and then propose a solution. First, is the Navy’s decision constitutional? Second, is the Navy’s decision, assuming it is constitutional, the best course as a matter of policy?

Does this Navy’s decision interfere with Hiles’s First Amendment rights? The Navy’s actions appear to be constitutional under existing precedent. However, it is plausible that, if the matter were to be litigated, the Navy’s treatment of Hiles might be declared unconstitutional. In 1986, Simcha Goldman, an Orthodox Jew and member of the U.S. Air Force, argued that Air Force uniform regulations prohibiting head coverings indoors violated his right to free expression of religion, given his need to wear a keepah. The Supreme Court decided 5-4 in Goldman v. Weinberger that Goldman’s rights were not violated. In particular, the Court noted the long-standing deference given to the military. Thus, the burden that the Air Force had to meet was very low. The four dissenters agreed with this premise but argued that the Air Force had failed to meet the low burden of rationality needed to justify its regulation preventing a religious airman from wearing a keepah[ii]

Goldman suggests that Hiles has no case. However, the Navy’s decision with Hiles is arguably a theological decision, i.e. Messianic Judaism is not a branch of Judaism. Hiles can argue that his rights under the First Amendment’s Establishment Clause rather than his rights under the Free Expression have been violated. Arguably, the Court should give less deference to the Navy when Establishment Clause issues are concerned. However, as I will discuss shortly, the Navy’s decision is pragmatically justifiable. Thus, even if the burden the Navy would face in a hypothetical court case is greater than the Air Force’s burden in Goldman, the Navy would likely be able to meet that burden.

Does the Navy’s decision as to Mr. Hiles make sense? Tentatively, I’d say yes. The accuracy of military uniforms and the perceived accuracy of military uniforms is important to morale. There is a serious potential to damage the morale and unit cohesion of soldiers who interact with a Messianic chaplain under the mistaken impression that the chaplain is Jewish. Such confusion can reduce respect for and reliability of the chaplaincy core as a whole. This is particularly likely given the history of Messianic Jews engaging in deceptive practices and the repeated problems of proselytizing by evangelical groups in the U.S. military.

However, there is another solution which is constitutionally and pragmatically preferable. The military should give all chaplains the same, religiously neutral, symbol rather than different symbols based on religious affiliation. One obvious possibility would be simply the letter “C”, denoting that the officer is chaplain without indicating his or her religious affiliation Since most duties of chaplains are identical, this approach keeps the military from having to make essentially theological decisions about which chaplains should be treated as members of which religions. This will not solve all the First Amendment problems presented by the chaplaincy. Some of these problems, such as the necessity of allocating chaplains by religion in large military bases, may be unresolvable. However, this approach – identifying all chaplains as such without specifying on their uniforms the religions to which they belong, will eliminate the problem posed by Mr. Hiles.

Hat tip to Ed Brayton at Dispatches from the Culture Wars. Brayton’s blog entry has a long comments thread which discusses and raises some interesting points which I have not addressed here. For more information, one should also look at the entry at Jews in Green which gives further background of the Hiles incident.

[i] Although most Jews use the term “Messianic Judaism” and “Jews for Jesus” interchangeably, this is not accurate and most Messianic Jews strongly object to the grouping of the two. Jews for Jesus generally have even less Jewish content. Almost none keep kosher or keep Shabbat in any form.. Jews for Jesus also emphasizes Jewishness as an ethnic group and is much more explicit and blatant in their desire to evangelize to Jews. Jews for Jesus as an organization is a member of the World Evangelical Alliance and various other Christian evangelical organizations. As far as Jews (and almost all Christians) are concerned, Messianic Judaism and Jews for Jesus are both Christian. They both believe that Jesus is their personal lord and savior and that such belief, including the divinity of Jesus, is necessary to avoid eternal hellfire. They both believe in a standard Trinity. Thus, one should not mistakenly label the Messianics as somehow less Christian simply because the Jews for Jesus are even more blatantly evangelical.

[ii] I am simplifying the breakdown. There were 3 dissenting opinions and one concurring opinion. Also note that Goldman was subsequently overturned by legislation that "a member of the armed forces may wear an item of religious apparel while wearing the uniform" so long as the item is “neat and conservative” and does not interfere with the member’s ability to carry out his duties.

Friday, December 26, 2008

Critical Thinking and Popular Culture.

Many things reinforce our natural tendencies against critical thinking and skepticism.[i] These include human tendencies to see patterns, wishful thinking, and the presence of pre-existing irrational beliefs and superstitions. One often overlooked reinforcement mechanism is popular entertainment, where critical thinking and skepticism are portrayed as tendencies to be overcome. In television and movies, there is an emphasis on the need to have faith and the importance of belief. Moreover, skepticism is often caricatured as a stubborn refusal to acknowledge the supernatural in the face of overwhelming evidence.

This theme of skepticism as a problem is not new; some episodes of the original Twilight Zone included this theme. One modern television show which repeats this theme is The X-Files in which two FBI agents investigate paranormal activity. Mulder, the credulous agent with the slogan "I want to believe," is invariably correct about the existence of whatever paranormal phenomenon he is investigating while Scully, the skeptical agent, refuses to believe in the supernatural no matter how much evidence she has seen.

In The X-Files skepticism is not just incorrect, but pathologically false; the skeptics, represented by Scully, refuse to modify or reduce their skepticism in the face of clear evidence of the supernatural. In this case, skepticism is reduced to a caricature of people who simply refuse to believe despite evidence to the contrary.

This theme occurs not just in television, but across many genres of movie. In horror movies, this occurs almost every movie. [ii] A few examples from the last few years are “Gothika,” “White Noise” and “Darkness Falls.”

This theme is so common that the rare cases where there is a strong skeptical bent are noteworthy. Consider, for example, the original Scooby Doo. I am curious if readers can point to any others like Scooby Doo.

Moreover, in a handful of cases critical thinking is not just a barrier to be overcome, but actually causes death and destruction. One of the most extreme examples of this is an episode of Dark Visions, a recent Twilight Zone knockoff. In an episode entitled “Harmony”, a young man goes to a town where no one sings and the townspeople kill anyone in the town who tries to sing. The people believe if anyone in the town sings, some sort of supernatural creature will be woken up and it will then kill everyone. The end of the episode features a mob about to kill the young man and his friends. He gives a stirring speech that convinces the people that the only monster which exists is inside themselves,and that they are afraid of singing due to the emotion it brings. The entire town begins to sing "Amazing Grace". And then in the last 30 seconds of the episode, it turns out that the monster is real and that their singing has woken it up. The episode ends as the monster begins to destroy the town. The last note by the Rod Serling knock-off is a warning against questioning the beliefs of others. I’m hard pressed to imagine how one could send a message that was more anti-critical thinking.

There is one place where such messages are both particularly common and particularly nefarious in their impact: movies and television aimed at children. In such cases, even when there is a skeptical element, it becomes quickly watered down. For example, many of the sequels to Scooby Doo had supernatural elements.

A recent and glaring example is the charming movie “Mr. Magorium's Wonder Emporium”. The premise of the film is that there is a magical toy store powered by belief in magic. The new owner does not have sufficient belief and so the store's magic fails. However, the store’s magic begins to return when a child playing with a magnetic toy asks if the toy is magical and the shop owner replies that she believes it to be. According to “Magorium,” critical thinking is not just bad. Rather, one should actively convince oneself and others that well-understood phenomena are magic.

As long as the entertainment industry continues to reinforce in the popular mind that critical thinking and skepticism are barriers to be overcome by unquestioning faith and magical thinking, the proponents of rationalism and reason will face uphill battles.

[i] The exact distinction between critical thinking and skepticism is not always clear. For purposes of this entry I will use the terms interchangeably.

[ii] This isn't strictly true. There are some movies such as “Unrest” that just take the spirit world's existence for granted with only token skepticism. In “Unrest” all the characters take for granted that souls and an afterlife exist. The character taking the most skeptical outlook believes in souls and an afterlife but does not believe in “corporeal manifestations.” This character pays for his attempt at rationality by suffering the loss of multiple limbs at the hands of a ghost.

Wednesday, December 24, 2008

Cantor, Infinite Sets and Cardinality

Many people from a young age are fascinated by the concept of infinity. This post will examine one way that the notion of infinity can be examined rigorously and compare different sizes of infinity.

When we look at finite sets, how can we tell if they are the same size without counting? Imagine a primitive tribe that determines social status based on who owns more goats, but no one in the tribe can count past 5. If two members of the tribe both own more than 5 goats , how can the tribe compare the total number of goats the two people own? One solution is they can take out pairs of goats with one goat from each person. When one of the two goat owners runs out of goats first, that person has fewer goats. If they run out at the same time, they have the same number of goats. (This goat analogy is a good analogy, but is not, as far as I am aware, frequently used to motivate what we are doing here. I'm not sure where I saw this analogy. If someone can point out where it comes from, I'd appreciate it.)

We wish to do the same thing with infinite sets. We are like the primitive tribe and we can only count finite numbers. So we say that two sets in general are the same size if there is a function which maps elements from one to the other with no overlap and no element missed. That is, if we have two sets A and B, if they are of the same size, then there is a function f from A to B such that for any b in B there is some a in A such that f(a)=b and for any x and y in A f(x)=f(y) if and only if x=y. A mathematician would call such a function a bijection or say that it is one-to-one and onto. Thus, for example the sets {a,b,c} and {cow, potato, glockenspiel} are the same size and we could define the function f by f(a)=cow, f(b)=potato and f(c)=glockenspiel. We can generalize this notion to sets that are not necessarily finite. We call this notion "cardinality". We say that |A|=|B| if A and B share a function like that above. We similarly say that |A|<|B| if there is no such function, but there is a subset C of B such that |A|=|C|. It is not hard to see that cardinality obeys the properties one would expect a notion of equal size to obey. For example, if |A|=|B| then |B|=|A|. Similarly, if |A|=|B| and |B|=|C| then |A|=|C|.

At first glance, cardinality leads to some strange results. For example, the positive even integers are the same cardinality as the positive integers. We can see this by setting f(n)=2n. So a set can be the same cardinality as a proper subset of itself. That's not intuitive. And if one plays around a bit, one will see that any infinite subset of the natural numbers is the same cardinality as the set of natural numbers.

One might tentatively conclude that all infinite sets are the same cardinality. In the 1870s, Cantor systematically examined infinite sets and first made the notion of cardinality precise. Cantor first showed that the natural numbers have the same cardinality as the rational numbers.

This is even more counterintuitive than the earlier results since the rationals are dense on the real line, but this result fits with our tentative conclusion that all infinite sets are the same cardinality.

There are a variety of proofs of Cantor’s result. One method is to show that N, the set of natural numbers, has the same cardinality as N x N, the set of ordered pairs of natural numbers. We can use the map (m,n) -> k = 2(m-1)(2n-1). Thus, for any positive natural number k, m determines the highest power of 2 that divides k and n determines the largest odd divisor. It is easy to see from that m and n uniquely determines k. From that result it is not hard to show that that the rationals and natural numbers have the same cardinality.

Then Cantor hit upon a surprising result. Cantor showed that there was no one-to-one and onto function from the natural numbers to the real numbers. Not all infinite sets are the same size. We shall discuss this and related results in a follow up blog entry.

Wednesday, December 10, 2008

The MBTA and Icehouse

Icehouse pieces are small colored plastic pyramids used in a variety of games.

(this image is in the public domain)

I recently had the pleasure of introducing one such game, Zendo, to the Boston University Hillel. Zendo is a game in which one player, the Master, makes a rule for which configurations of Icehouse pieces are valid and which are not. For example, a very simple rule might be "A valid configuration must contain a red piece." Other players then take turns presenting configurations of Icehouse pieces and find out if those configurations are valid or not. The goal of the game is to figure out the rule. When this game is generally played, the game terminology uses terms from Zen Buddhism. Thus, configurations are called "koans" which are described as having Buddha-nature or not. At the BU Hillel, this quickly mutated into whether or not configurations were kosher or treif.

Readers may be wondering what this has to do with the MBTA. A few days ago, I decided to purchase more Icehouse pieces since Zendo is hard to play with only a few pieces. After buying a new set of pieces I got onto the subway heading back to Kenmore Square. Icehouse pieces come in small, rectangular boxes of transparent plastic with pieces of different colors stacked up on top of each. The boxes are about 6 inches long with a 1 by 1 inch base (in metric that's around 15 cm long with a 2.5 by 2.5 cm base). One of the MBTA personnel stopped me and asked what I was carrying. I explained that they were plastic pieces for a game. The MBTA official said "Oh. Ok. You should put that in a bag. Someone might think that it's a weapon." I must confess that I was speechless. Considering the idiocy about such issues that Boston is known for, I should be happy I'm not in jail right now.

Sunday, December 7, 2008

Wikipedia, Great Britain and Censorship

ISPs in Great Britain are censoring Wikipedia. From the Wikinews article:

Wikinews has learned that at least six of the United Kingdom's main Internet Service Providers (ISPs) have implemented monitoring and filtering mechanisms that are causing major problems for UK contributors on websites operated by the Wikimedia Foundation, amongst up to 1200 other websites. The filters appear to be applied because Wikimedia sites are hosting a Scorpions album cover which some call child pornography. The Scorpions are a German rock band who have used several controversial album covers and are perhaps best known for their song, "Rock You Like a Hurricane".
The evil wiki witch Durova already has an entry on this topic which I recommend reading. My own analysis follows.

While there has already been a large amount of reaction against this perceived censorship accompanied by cries that of course this image is not child porn, I can see how a reasonable individual might consider the image to be over the line. The image in question consists of a nude girl of about 11 years of age with an apparent lens crack over her genitalia. Moreover, the pose the girl is in is a pose which would arguably be sexual if that pose were done by an adult even if she were fully clothed. However, it is clear that the image is legal in the United States and the State of Florida where the Wikipedia servers reside.

The censorship has been done in a very hamfisted fashion. Among other consequences it forces the majority of people accessing Wikipedia in Great Britain to do so only through a handful of IP addresses. This is making it difficult for Wikipedia admins to deal with vandalism from anywhere in Great Britain and is making it difficult for people in Britain to edit Wikipedia in general.

There are two issues which I find particularly disturbing.

First, the ISPs made the decision after the Internet Watch Foundation, a non-profit dedicated to stoping child pornography on the internet, decided that the image was close enough to child porn to be included in their list. There's thus nothing even resembling an appeal process or any form of transparency about these decisions. Indeed, even now the IWF has not clarified whether any other pages on Wikipedia are being similarly censored.

Second, many of the people in Great Britain who have attempted to access the page have received a 404 error rather than be told that the content is being censored. If this occurs in less prominent cases people might not even realize there is censorship occurring and simply assume that the server in question is down or has some other problem. This is thus a subtle form of censorship which can be hard to detect.

Update: David Gerard appeared on the Today show to talk about this. He has a transcript of that appearance as well as his thoughts on the matter.

Monday, December 1, 2008

Israeli religious courts and precedent

In an earlier entry, I've discussed some of the oddities of the Israeli secular court system. I'd like in this entry to touch briefly upon a serious problem in the Israeli religious court system that is not widely discussed. I'm not going to discuss the weird way the religious courts interact with the secular courts and I'm not going to discuss the serious problems with having a theocracy. What I am going to discuss is an issue I only recently came across: there is close to no weight of precedent on the religious courts.

Here is an example given recently by Rabbi Chayim Tobasky at a talk at Boston University.

Consider the following hypothetical: A man and woman who get married, have a kid and then get divorced. She goes to a beit din (religious court) for child support. The court mandates some fraction of his income go to child support (say 60%). Now, the man remarries and has three kids with the new wife. She can go back to the beit din or to another beit din and get the arrangement reapportioned so that all kids can get at least the same amount from the father. But there's one snag: contractually obligated debts take precedence over child support. That means, for example, if the man had an obligation to pay off some debt accrued jointly with the first wife, that money could not be readjusted for the second. This leads to the following question: suppose that the husband and the first wife agreed that he pay the 60% for child support as part of the divorce settlement rather than as mandated by a beit din. Does this count as child support or as a debt? Apparently, every court in Israel rules that such a contract does not count as child support except the beit din in Rechovot. The Rechovot court has been repeatedly overruled and it continues to rule the same way, knowing that, if the case is appealed, it will be overruled.

Regardless of what one thinks of the religious court system in Israel, this is no way to run a judicial system. It is at best inefficient. It needlessly turns legal disputes into even more of chess games, and places unfair burdens on people with few resources.

Wednesday, November 19, 2008

Politically correct idiocy at Queen's University

Metroblog has brought to my attention an apparent real life caricature of political correctness. According to an article in the Globe and Mail, Queen's University is appointing a series of "student facilitators" who will have the job of "censuring" students who engage in various behavior deemed to be unacceptable. Some of the behavior discussed is offensive such as using "gay" as a slur. However, it is not at all clear to me why a University should be attempting to control speech in this fashion. At best, it seems like a waste of time.

But Metroblog noticed something in the article that really stands out and makes one wonder what the Queen's University administration was thinking. Included in the list of behavior which will receive "censure" is "If a student avoids a classmate's birthday party for faith-based reasons." I'm having trouble seeing how that is similar to calling someone "gay" as a slur or calling someone a "retard" (the second does not strike me as a big deal anyways. Sometimes you need a word to describe that someone is just not an intelligent person).

I, as well as everyone I've talked to about this, is puzzled about what this hypothetical has to do with the other situation. I had some difficulty thinking about what sort of situation they were talking about. Do they mean say an Orthodox Jew who would not go to a party on Friday night? Or maybe a Catholic not going to a party during Lent? Or a Muslim not going due to the presence of alcohol? How are any of these offensive? The closest I've been able to come to a minimally sensible interpretation in this context is a student who would not go to a party because there were gays dancing at the party (which actually is less halachicly problematic than mixed dancing).

The most coherent interpretation I have is that to someone birthdays are so important that it is unacceptably offensive to not attend them over silly religious obligations. If anyone has an interpretation that is more charitable or simply makes more, sense please post it.

I'm reminded of a conversation I had with a friend a few years ago when I could not go to an event because it was the same time as Shabbat dinner. She remarked "That's so `gay', where by gay I mean Jewish." I wonder how the Queen's University facilitators would respond to that.

Monday, November 17, 2008

One step forward, one step backwards

There have been two developments connected to intelligent design in the last few days. One is heartening; the other is disappointing. William Dembski, one of the chief proponents of intelligent design, has announced that he will stop spending time running the Uncommon Descent blog and spend more time doing "technical research." This is a good thing. Whether or not there is any scientific merit to intelligent design, the desultory attempts by ID proponents to produce any scientific work about intelligent design has not helped intelligent design in the eyes of the scientific community. It is likely that the lack of scientific merit of intelligent design has forced the proponents to engage in the wastes of time that they have. However, on the off chance that there is any minimal scientific merit to their ideas, Dembski has some chance of finding it.

The second development is that Catholic philosopher Francis Beckwith, a former Fellow of the Discovery Institute and a professor at Baylor University, has forcefully come out against intelligent design. In the past, Beckwith has spoken sympathetically about ID so this comes as a surprise. Unfortunately, he now opposes intelligent design for the wrong reasons:
Despite my interest in this subject and my sympathy for the ID movement’s goal to dismantle materialism and its deleterious implications on our understanding of what is real and what counts as knowledge, I am not, and have never been, a proponent of ID. My reasons have to do with my philosophical opposition to the ID movement’s acquiescence to the modern idea that an Enlightenment view of science is the paradigm of knowledge. By seeming to agree with their materialist foes that the mind or intellect cannot have direct knowledge of real immaterial universals, such as natures, essences, and moral properties, many in the ID movement seem to commit the same mistake as the one committed by the late medieval nominalists such as William of Ockham, who gave us what is often called “Ockham’s razor,”...
I imagine some readers are sputtering a bit as they read that. The complete context of Beckwith's remarks does not cast Beckwith in a better light. Beckwith's remarks are disturbing for a great many reasons, but I will only focus briefly on two of them.

First, as one friend cogently asked what is an "Enlightenment view of science? Newton's? Bacon's? Hume's? Paley's? Whewell's?" One would like to think that a tenured philosophy professor such as Beckwith would be more precise with language.

Second, many if not most scientists would agree that science has no essential monopoly on on all knowledge. Moreover, many proponents of intelligent design would also agree even as proponents of ID frequently attempt to push the bounds of what science can reasonably talk about. Thus, Beckwith's objection is either to some sort of extreme strawman or Beckwith's objection is to the entire notion of science as a separate epistomological method. Indeed, Beckwith goes on to claim that "According to many scholars, the practical consequence of “Ockham’s razor”[sic] is that claims about a thing’s nature, purpose, or intrinsic dignity—universal properties it shares with other things of the same sort—are “unnecessary” for our scientific investigation of the world because they don’t add anything of explanatory importance to our direct empirical observations." It appears thus that Beckwith does object to the entire scientific method. This is the opposite of something like non-overlapping magisteria. This is aside from the fact that archaeologists engage in trying to find artifacts' "purpose" all the time. I have no idea how science would incorporate the "intrinsic dignity" of objects.

I've paid some attention to Beckwith in the past and knew he had reservations about intelligent design. For a long-time I suspected that his stated reservations were for rhetorical effect while he argued for the constitutionality of teaching ID in public schools. In my naivete I never would have thought that Beckwith's objection was to science as a whole.

Beckwith appears to be objecting to ID, not because it drags us back a few centuries, but because it does not drag us back far enough. As William Dembski takes a step to join the 19th century, Beckwith is trying his hardest to join the 10th.

Friday, November 14, 2008

Great Britain, Germany and Internet Censorship

There is a common belief that modern technology makes it harder to censor people. Unfortunately, recent events have shown otherwise. Great Britain is leading a charge that, if unchecked, will allow almost any government to censor almost anyone anywhere.

Great Britain recently extradited Gerald Toben, an Australian national, to Germany to face charges of Holocaust denial after Toben landed at Heathrow airport. Toben is no doubt an odious human being. However, laws such as Germany’s laws on H holocaust denial are infringement of free speech rights. More disturbingly, Toben did not commit his crime in Germany. However, since his blog was visible in Germany, Germany asserts that he has violated their laws. And Great Britain is going along with it.

In the past, Great Britain’s actions have been detrimental to free speech. Great Britain has been strongly criticized in the past for its libel laws under which the burden of proof to is placed automatically on the defendant. Together with a very low standard of what constitutes publication in Great Britain, Britain has become known for “libel tourism.” In one memorable case, an American author was successfully sued in Great Britain when 23 copies of her book were bought online by people in Great Britain. However, the British libel laws have at least one saving grace: they are civil penalties. The German law in question is criminal.

This is all the more disturbing because many countries are in the process of strengthening their laws restricting speech or are cracking down on offensive speech. Italy has recently attempted to prosecute an Italian comedian for insulting the Pope. The Netherlands recently decided to expand its anti-blasphemy laws to include speech offensive to any group. . If I insult the Pope and then land in Great Britain, would they send me to Italy or the Netherlands first?

Great Britain’s reaction to Toben is not productive. Great Britain should officially repudiate this stance and Germany should officially repudiate prosecution of people whose only crime is to have a website that can be accessed in Germany. These laws may be used now to imprison those whom we despise but the risk is too high.

Edit: The above contains some minor factual issues that don't detract from the central point. See the anonymous commentator's remark below for details.

Follow up edit: It looks like Toben will not be sent to Germany after all. See this article.

Wednesday, November 12, 2008

New Gospel Discovered

A new gospel was discovered recently by a team of archaeologists. The incomplete text was apparently found in a dig near Petra. Carbon 14 dating and surrounding pottery shards suggest that the physical text dates to somewhere between 150 and 300 c.e. The gospel is apparently in an obscure dialect of Aramaic which, combined with the incomplete nature of the text, is making a complete translation difficult. Imaginary Review has a discussion along with partial translation.

Sunday, November 9, 2008

Diffie-Hellman: How to share a secret with everyone listening.

This post is the third post of a series of three posts on why we care about prime numbers. The first entry gave an overview of primes. The second discussed the link between Mersenne primes and perfect numbers. This post will discuss practical applications of large prime numbers and provide a concrete example.

The main focus of this post is the Diffie-Hellman algorithm. Diffie-Hellman is a procedure whereby two people can have a conversation and at the end of the conversation they will share a secret number. The remarkable thing is that even if an eavesdropper hears the entire conversation, the eavesdropper will have no feasible way of figuring out the secret. . By repeating this procedure many times two people develop can have a list of secret numbers which they can use to encrypt messages to each other that only they can read. As is standard in cryptography, I will refer to three people, Alice and Bob who want to share a secret number and Eve the evil eavesdropper wishes to obtain their secret number.

There is a standard analogy in cryptographic circles to accomplish this sort of task. Suppose Alice and Bob want to exchange an object through a mail system that they don't trust. But they know the mail employees aren't going to be able to get into a locked box. How can Alice send an object to Bob? She cannot just send a locked box because Bob won't have a key. Nor can she send a box and a key because then the corrupt mailmen can use the key to open the box. Here is the solution: Alice puts her object into the box and locks it with her lock. She mails this to Bob. Bob puts a second lock on the box and mails it back to Alice. Alice now removes her lock and sends it back to Bob. Bob can now remove his own lock and gain access to the contents of the box.

Before we discuss this algorithm in detail we need a few small mathematical facts. We call doing arithmetic where we only care about the remainder when divided by k to be “arithmetic mod k”. So for example, 4+6= 3 mod 7 since 4+6 = 10 and the remainder of 10 when divided by 7 is 3. For a concrete analog, when we tell what time it will be on a clock some number of hours from now we are doing arithmetic mod 12.

Now, we need to define a primitive root: Suppose for a fixed prime p we have some u such that u1 u2 u3 u4… up-1 mod p cycle through 1,2,3,4… p-1 in some order then we say that u is a primitive root for p. For example, if p=5, then 2 is a primitive root for 5 since 21=2,22=4,23=3,24=1. But 4 is not a primitive root for 5 since 41=4, 42=1,43=4,44=1 so we only cycled through 1 and 4. Now, it happens that every prime p has some primitive root u. The proof will not be given here but this fact is the only piece of non-trivial number theory we will need for this procedure.[1]

The last detail we need is to note how it is possible to quickly raises numbers to large powers. Naively, if I want to calculate xn for some fixed x and large integer n I need to multiply by x n times. And this applies if I am operating mod k also. But we have a nice trick called repeated squaring that allows us to get around this. Observe that if we know xy then we can calculate x2y by squaring xy. Thus, we can easily calculate x2, x4, x8, x16 all the way up to the largest power of 2 less than n. Then we can write n in base 2 and calculate xy in the obvious fashion by multiplying together the relevant powers of the form x2^t. Thus, calculating xn takes at most c log n multiplications for some fixed constant c.

We are now ready to outline the procedure. Alice says to Bob: Hey Bob, I want to talk to you. Let’s use Diffie-Hellman. Bob says ok and picks a large prime p (by large probably in the order of 100s of decimal digits) and Bob finds a primitive root u for this prime. Bob then picks a random positive integer between 1 and p-1, call it b. Bob calculates B = ub mod p which is easy to calculate by our above remark. Bob then transmits B, p and u to Alice. Alice picks some a and calculates A = ua mod p and sends A to Bob. Alice calculates S = Ba = (ub)a = uab mod p and Bob calculates by taking Ab mod p. Alice and Bob now share S. However, suppose we have our evil eavesdropper Eve. What information does she have? She has A. She has B. She has u and she has p. There’s no obvious way for Eve to work out uab mod p. If Eve had a fast way of finding a or b from knowing ua=A mod p she’d be set. But that turns out to be quite hard. This problem, known as the discrete log, is very difficult in general. So Eve is stuck. Alice and Bob can construct an agreed upon code by repeatedly using this procedure and there’s nothing Eve can do about it. If Alice and Bob set p to be a few hundred digits than the computation necessary for Eve to work out what S is turns out to be more than all the computational power on Earth today.

Let's do a small example with Say p=17 and u=3. Bob says "My prime is 17, my primitive root is 3." Bob picks 6 as his random number. Bob calculates that 36 mod 17 which is 15. So he says "my B is 15."

Alice picks a random number, say 13 and calculates 313 mod 17 which is 12 so she says "My A is 12.".

Bob then calculates A^b mod 17, which is 126 mod 17 which is 2. Alice calculates B^a mod 17 which is 1513 mod 17 which is 2

So Alice and Bob now share the secret number S = 2. Obviously, for 17 it isn’t that hard for Eve to work out the answer. She just needs to write out a table of powers of 3 mod 17. But if instead of 17 she had to deal with a prime that was a few hundred digits long that strategy would never work; Eve's table would have more entries in it than the number of atoms in the universe. There are other strategies Eve could try to attack this but in general she doesn’t have many options.

An important caveat: No one knows a quick way of doing the discrete log but it has not yet been proven that there is no quick way to do so. Almost everyone who has studied the problem is very sure that there isn’t a quick way.

Diffie-Hellman turns out to have a variety of practical problems with implementation. So more often a related algorithm called RSA is used instead. In a later post, I will discuss RSA. RSA has even more counter-intuitive properties than Diffie-Hellman. While Diffie-Hellman required Alice and Bob to be work with each other, in RSA the intended recipient simply needs to publish a key which can then be used by anyone to encrypt messages such that only the recipient can read them. The standard analogy used by cryptographers to describe this procedure of a box that anyone is able to lock but only the person with a special key can unlock. The fact that this is mathematically doable turns out to be very useful. Readers have likely used RSA without even realizing it if they have engaged in almost any form of commerce over the internet. Modern web browsers and other software implement RSA in a way that is invisible to casual user. Even though one does not notice it RSA is responsible for keeping credit card numbers and similar data to safe and secure.

Both Diffie-Hellman and RSA rest heavily on the ability to find large primes. Moreover, the security of these algorithms is connected strongly to our understanding of prime numbers and their properties. Thus, the mathematics of large primes is vital to the functioning of the modern economy.

Edit: Added the locked box analogy.

[1] In fact we won’t really need that fact other than that we need in the procedure access to a prime that has a primitive root and we want to know that there are large primes with this property. Since all primes have this property, so do all large primes.

Wednesday, November 5, 2008

Thoughts the day after the 2008 election

Overall, I'm pretty happy with the results. The situation of Obama with the Presidency but the Democrats lacking a filibuster-proof majority in the Senate was the ideal result for me. While final tallies still need to be calculated, it looks like the Democrats will not have 60 in the Senate.

Here at Boston University students on the whole seemed to be very happy. They spent more time drunkenly screaming "Obama!" at the top of their lungs than actually sitting down and watching the ongoing returns in the House and Senate. And they kept screaming until about 2 AM when sane people were trying to sleep. I must wonder if they were plants sent by the Republican party to make people so annoyed with Obama that they won't vote for him in 2012.

Now as to specific elections: I'm disappointed at Chris Shays' defeat since he is a moderate Republican and it seems that people voted against him primarily for reasons that had little to do with his voting record. I'm appalled that Ted Stevens won despite his recent convictions. Really Alaska, haven't you been made fun of enough in the last year? Finally, as of right now, it looks like California's Proposition 8 passed which is unfortunate. My ideal is to have no legal recognition of any marriages but, if we are going to be recognizing some, we should recognize all of them.

Specific pieces I recommend reading: My twin has a piece up on the Huffington Post discussing McCain and Obama's respective final speeches. Mark Chu-Carroll has a piece up which discusses his personal views and raises interesting points about how statistics are reported during elections. Orac presents some worrying evidence that an Obama administration may not be as pro-science as many hoped. Razib Khan over at Gene Expression has as usual a variety of interesting posts with good analysis of data to back them up. There's a piece in Commentary's blogs by Abe Greenwald suggesting that the Republicans did not do anything wrong this election. Then people should immediately read Ramesh Ponnuru's response.

One final note: As I was writing this piece I noticed that this version of Firefox does not have "Obama" in the default list for the spellchecker. I presume that will not be the case for future versions.

Monday, November 3, 2008

Dixville Notch for Obama

Dixville Notch went for Obama. Dixville Notch is a tiny town in New Hampshire that votes just at midnight. They have only around 20 registered voters and under New Hampshire law can count the ballots if all registered voters have voted. Dixville Notch has traditionally gone Republican. They haven't voted for a Democrat in 40 years. And in this case it was a landslide for Obama at 15-6. This could be an interesting election.

A message of gratitude

In spirit of the upcoming election as well as the upcoming holiday of Thanksgiving I'd like to give thanks to a specific subset of the blogosphere. This is a message of thanks to all the people who this election cycle who have used the terms "Demoncrat" and "Rethuglican." I would never have realized that the Democratic Party were spawn of satan without seeing the incredibly original and clever wordplay contained in the word "Demoncrat" repeated over and over. And I would never have realized that every single person who votes Republican is obviously a corrupt, racist criminal if not for having seen the amazing coinage "Rethuglican" over and over.

When I see a comment in a blog or see a blog post that uses one of these terms, I know immediately to pay attention. I know that the comment will be the product of clear and careful thinking with a good attention to shades of gray. I know that the writer must be a great wordsmith and master of the English language, more skilled and knowledgeable than William Safire. The only thing that could make me pay more attention would be if the comment were written in all caps.

You have helped make dialogue in this country more nuanced, well-reasoned and calm. You have heightened political discourse to levels undreamed of by past generations. Without your repetition of these terms we would be a terribly divided nation with no appreciation that reasonable people can disagree. Thank you.

Thursday, October 30, 2008

The Economy, Prayer, and Idolatry

There has been a long-standing argument in halachah (Orthodox Jewish law) over whether Christianity is considered avodah zara (the technical term for idolatry in Jewish law). The problem of a human being declared to be divine is particularly troubling and Jews have been debating this issue for almost as long as Christianity has been around.

However, some Christians have recently been nice enough to make the Jews have an easier time figuring out how to treat Christianity. According to Wonkette, Christian groups have gathered at the statue of the bull at Wall Street to pray for a better economy. That's right: they are praying at a Golden Calf. Really. You can't make this sort of thing up. I have tried in the past to argue against claims that evangelical Christians are Biblically illiterate, and then they go and do something like this. Between this and Reverend Jeremiah Cumming's inability to quote basic scripture I should just give up.

Hat tip to Pharyngula for bringing this to our attention.

Sunday, October 26, 2008

Censorship, guns, and Lone Star College Tomball

Lone Star College Tomball, a small college in Texas, is at the center of criticism by various right-wing groups for perceived censorship. The college's branch of Young Conservatives of Texas distributed a "satirical" "gun-safety flier" for which they are now in trouble. The branch may be put under probation at the school and the students may face disciplinary action. While this has received some attention in right-wing blogs, so far the go to source is from that bastion of fair and balanced news World Net Daily.

I am normally strongly against anything resembling censorship, but in this case the circumstances are not clear cut. The list of safety tips included "Always keep your gun pointed in a safe direction, such as at a Hippy or a Communist". Now, I'm not going to discuss the fact that this sounds like it was from 1965 other than to speculate that possibly Tomball is so isolated that the upheaval of the 60s is just starting to reach there. I'm not going to discuss that the Cold War is over. (And Emily, if you are reading this- as far as I'm concerned I still think that communism in most of its variations a threat to basic liberties and to humanity and all remarks about what to do when at war still apply. My views on this are absolutely unchanged. Don't think otherwise). I don't need to discuss the abject stupidity of the remark because it is far from what constitutes reasonable political discourse. You don't make jokes about how segments of society are ok to shoot. In this case, it amounts to a borderline threat. This line by itself is simply appalling.

Moreover, I'm disturbed that none of the right-wing groups commenting on this matter have had the good graces to say something like "well, we think this is within free-speech rights but we understand how you would be offended or threatened." These people are joking about how it is ok if students who they don't like get shot. If there is anything that pushes the bounds of acceptable speech, this is it. And I haven't even discussed how the list also included "Don't load your gun unless you are ready to shoot something or are just feeling generally angry." It doesn't take much effort to put these together.

Frankly, I hope that the college does not punish the Young Conservatives. The speech is arguably on the ok side of the border and we should be careful not to impinge on speech even when it is idiotic. But I also have a selfish reason for wanting the college to leave them alone. I really want to see what their next piece is that passes for "humor."

Sunday, October 19, 2008

Don McLeroy Jenkins: Epic failure by the creationists. Again.

Some readers may be vaguely aware that Texas is going through their aperiodic burst of anti-evolution sentiments from their school board. Don McLeroy, the current Chairman of the Texas State Board of Education has managed to effectively lay the groundwork for any possible legal challenge by his opponents.

First a bit of background: The creationists used to try to teach creationism next to evolution. The federal courts said that was unconstitutional because of that whole First Amendment thing. It can be so pesky and inconvenient sometimes. Then suddenly a mutation showed up and they started to teach “creation science” which was completely different from “creationism.” The Supreme Court in Edwards v. Aguillard ruled that this was nothing more than thinly disguised creationism.[1] Then miraculously, a new mutation occurred. Now, there was “intelligent design” which had nothing to do with that unconstitutional “creation science” thing. Not all. (Actually it wasn't a single mutation but a series including a well-preserved transitional form). In Kitzmiller v. Dover, this new variation was ruled unconstitutional. The latest version is “teaching the controversy.”

However, McLeroy has gone and shot himself in the foot. In a recent editorial, he justified teaching the controversy by saying that, under the new proposed curriculum claims about evolution … will be challenged by creationists.” Oops. He said the c-word. I can see his legal allies carefully planning a case in front of a federal judge to explain how what they want has nothing to do with creationism at all. And then he arrives, running into the courtroom screaming “McLerooooy Jennnnkins! Creationism!”

[1] If one does have opportunity to read this decision, I strongly recommend reading Scalia’s dissent as well. It gives one real appreciation for Scalia’s intelligence and thoughtfulness and raises serious issues that are worth thinking about.

Saturday, October 18, 2008

On the complete uselessness of the TSA

Jeffrey Goldberg has a piece in this month's The Atlantic on how easy it is to penetrate airport security in the United States. Goldberg relies primarily on the advice of security guru Bruce Schneier. To say that Goldberg demonstrates the uselessness of post-9/11 security procedures is an understatement. I strongly recommend that people read this article. The article does drive one point home which is worth repeating explicitly here: none of the security precautions will stop a smart terrorist. All they will do is possibly catch dumb terrorists.

Wednesday, October 15, 2008

Three youtube videos related to the Presidential campaign

Three people have endorsed candidates for President recently: Sarah Silverman, Jackie Mason and Marty Chalfie. The first two are well known comedians. The third is a Nobel Prize winning scientist.

Comedian Sarah Silverman recently posted a Youtube video calling for young Jews to persuade their retired relatives in Florida to vote for Obama. Jackie Mason (yes he is still alive) posted a rebuttal video. Frankly, they both seemed like close to a waste of time. Silverman's video wasn't that funny and Mason's video missed the entire point of Silverman's video. Mason seems to think that Silverman is using her video to persuade people to vote for Obama. That's clearly not what she intended. The video is to persaude people who are already voting for Obama to talk to their elderly relatives. Mason attacks Silverman's video for being contentless but his own is about as contentless. Also here's a minor hint for Mason if you are reading this: most old people in Florida probably aren't going to spend much time watching Youtube videos.

But enough about the comedians. The video out that should matter a lot more is that by Chalfie. Marty Chalfie, one of the three nobel prize winners in Chemistry for 2008, has endorsed Obama. That brings the total to 65 Nobel Prize winning scientists who have endorsed Obama. That total includes all the American winners of the 2008 prizes. When James Watson is endorsing a black man that says something. And Chalfie's video gives a detailed, contentful rationale for voting for Obama. An interesting note: As of writing this message Chalfie's video has been viewed 4,120 times. Silverman's video in contrast has been viewed 189,661 times and Mason's video 7,873. So even with the information contained in our little hint above, Mason's video has still been viewed over twice as many times as Chalfie's. Apparently people prefer listening to comedians over Nobel Prize winning scientists for advice.

One interesting argument I've heard in the context of the Nobel endorsements of Obama is that the scientists are just another special interest group. That argument is flawed. Most seriously, no endeavor is as influential to the long-term success of the United States or humanity as science. Scientific research impacts everyone from the discoveries that make many consumer goods possible to the drugs that stop cancer to the agricultural techniques that provide cheap food. Moreover, even aside from issues of funding (where one might be able to make something resembling a coherent argument that scientists function like a standard lobbying group) science provide guidance on what policies make sense and what do not. In that regard, science offers far more relevance than any other "interest" group.

(I'm having some trouble embedding videos for some reason for now here are three links to the videos: Silverman. Mason. Chalfie.)

Note: This post underwent substantial revisions after talking to a few people about it. Also, I acknowledge that the comparison between Chalfie and the comedians suffers from a variety of flaws. If I have time I'll write another post discussing this in more detail.

Sunday, October 12, 2008

Bill Maher's Religulous

I saw Bill Maher's Religulous last night. I had mixed feelings about the movie. The movie was amusing but some of Maher's comments were cheap shots. At other points one felt that Maher was sloppy. Here are my thoughts in a not completely organized fashion:

The thesis through most of the movie was that religion is silly and that it would be harmless but for the fact that it also causes serious violence. Given Maher's stated views that isn't that surprising.

In an odd way, I could not help comparing the movie to Expelled(see my previous review of that movie here). And unfortunately, there was a lot to compare. As with Stein's Expelled, Maher frequently used clips intended for humorous effect rather than seriously considering the points or claims made by the people he was interviewing. Unlike with Stein these clips were actually funny and sometimes even moderately germane. However, over all, direct confrontation of the ideas and claims presented would have served better since most of the ideas so mocked could be easily dismantled. There was however, one example that did strike me as amusing and well-played. During an interview with Jeremiah Cummings (more on him later) Cummings talks about how he counseled a young man who wanted to kill himself over a lady that the young man should instead "have that sort of passion for God. Imagine what it would be like if people had that sort of passion for God?" Maher then switched immediately to a clip of an apparent suicide bombing. The connection is tasteless, amusing and certainly more directly relevant than any of Stein's clips.

Another similarity between the movies was that it was not clear how much material was being left on the cutting room floor. The interviews appeared to be heavily edited and it was difficult to tell whether comments were in sensible contexts. Unlike with Expelled this was a serious concern since the people being interviewed did frequently come across as idiots.

In a few cases there was no way to imagine a better context for the comments. For example, Cummings in his interview tries to defend his lavish lifestyle by attempting to assert that there is a Bible verse that supports being rich. Maher immediately makes clear that the verse that Cummings seems to be trying to stumble over is the statement found in the synoptic gospels that "it is easier for a camel to go through the eye of a needle than for a rich man to enter the kingdom of God." How Cummings can manage to be taken at all seriously by his congregation given his ignorance of basic Christian scripture is beyond me.

Similarly, Senator Mark Pryor came across as about as much of an idiot as was expected by the previews. And yes, he really does try to defend his views at one point by saying that "You don't have to pass an IQ test to be in the Senate." The statement in fact comes in the middle of an extended clip with minimal editing anyways.

One interesting interview was with Aki Nawaz who is a radical Islamic rapper whose lyrics glorify suicide bombing and terrorism. Nawaz attempted to argue that he had a free speech right to his lyrics but that Salman Rushdie did not have a similar right. People like Nawaz make me want to believe in a vengeful God who will make sure that Nawaz burns for a very long time.

Maher focused almost exclusively on Christianity and Islam and never addressed the non-Abrahamic religions aside from a few minor cults. Judaism is addressed mainly as an opportunity to make self-deprecating jokes (I suspect that Maher is quick to discuss that his mother is Jewish is part to allow him to make such jokes).

Maher was in a variety of circumstances just sloppy. For example, he interviewed one of the members of Neturei Karta. While Maher noted that Neturei Karta was an extreme minority view in "Orthodox" Judaism, that's an understatement. Neturei Karta is an extreme minority view in Charedi Judaism.

Similarly, Maher at one point talks to Dean Hamer about both the "Gay Gene" and the "God Gene" and fails to note that there are serious reservations in the scientific community about much of Hamer's work.

Maher also excepted uncritically certain claims about parallelism the stories of Horus and Mithra to those of Jesus. Some of these claims are disputed and they weaken what would otherwise be a good case.

Maher also used tactics similar to those used in Expelled to get his interviews including lying to some interviewees about what the movie was going to be about. That is unfortunate and intellectually dishonest. Maher was however much more up front about this tactic than the makers of Expelled were and Maher seemed to make clear in the movie when people were unhappy with his interviews or worried about what they were focusing on.

Maher's concluding claims did not fit well with the rest of the movie and felt a bit tacked on. The end of the movie consisted of Maher engaging it what amounted to a call-to-arms to atheists and agnostics to speak up while at the same time calling for moderate religious individuals to stop giving aid and comfort to extremists. The last part seems particularly difficult; in general moderately religious individuals don't like extremists and rarely will the defend them or support them. The moderate religious individuals who do support such individuals will be likely extreme enough that they won't be listening to Maher anyways.

There has been some discussion on the blogosphere comparing this movie's box office ratings to those of Expelled. This film opened on about half as many screens and did about as well on its first weekend. Moreover, there was no similar campaign as there was in Expelled to pay churchs and schools to send students to the movie. Thus, it seems that by reasonable measures of success Religulous comes out ahead of Expelled.

I'm frankly a bit uncomfortable comparing this movie too closely to Expelled. Expelled claimed to be about science and was really about demagogery and deception. Religulous did not make any claim to be about science as a subject matter. Moreover, a focus on Expelled v. Religulous puts to much emphasis on a science v. religion view of things which is simplistic and unhelpful (if someone wants to talk about rationalism v. religion that would be a different situation).

While I disagree with a large part of Abbie's more positive assessment of the movie she is correct to point out that many of the responses by religious individuals to the movie have been kneejerk responses to criticism. Claiming that Maher somehow doesn't understand religion is obviously false. He may get details wrong but many of the interviewers and facts speak for themselves. A lot (and possibly the vast majority) of religions out there have some pretty silly ideas. And people kill over them.

Overall, this is not a movie brimming over with intellectualism and deep thought. Religulous does not substantially raise the level of dialogue. The movie is at times sloppy and inaccurate. However, this blog entry's focus onprimarily negative aspects should not be construed as a reason not to see the movie. Religulous was funny and brought up serious issues that society needs to discuss. I strongly recommend that readers go see it.

Saturday, October 11, 2008

Mersenne Primes and Perfect Numbers

This is the second part of a series of three posts about why people care about large prime numbers. The first part can be found here. This post will focus on primes that are of the form 2n-1. Such primes are generally called Mersenne primes.

The historical reason for caring about Mersenne primes is that they are related to perfect numbers. A positive integer n is said to be perfect if n is the sum of all its proper divisors. For example, 6 is perfect because 1+2+3=6 but 8 is not perfect since 1+2+4=7 and 7 is not equal to 8. Perfect numbers were first studied by the ancient Greeks and have been connected to various numerological ideas. For example, St. Augustine noted that the world was created in 6 days and 6 is a perfect number.

The first few perfect numbers are 6, 28, 496 and 8128. These were the only perfect numbers known to the ancients with the next one 33550336 not discovered until much later. Now, how are these numbers related to Mersenne primes? Well, it turns out that every even perfect number is associated with a Mersenne prime. More particularly, an even number is prime if and only if it is of the form (2n-1)(2n-1) where 2n-1 is a Mersenne prime. For example, 6= 2*3 = (22-1)21 and 28=7*4 = (23-1)22. That numbers of this form are perfect was proven by Euclid about 2300 years ago. About 2000 years later, Euler proved that these were the only even numbers that were perfect.[1] The main aim of this post will be to sketch out Euclid’s and Euler’s proofs in modern notation and then to discuss a few other properties of Mersenne primes.

First we need a small lemma:

Lemma 1: 1+2+4+8…+2n = 2n+1-1.

Proof: Consider S=1+2+4 + 8…+ 2n. Then 2S=2+4+8…+2n+1 = S - 1 + 2n+1. So

2S=S - 1 + 2n+1 and solving for S now gives us the desired result. Readers who recall their high school algebra will note that this is just the proof for the sum of a finite geometric series in the specific case with the first as 1 and with each succeeding term as twice the previous.

Proposition: A number of Euclid’s form is a perfect number. That is (2n-1)(2n-1) with 2n-1 is a perfect number.

Proof: The proof isn’t anything that complicated in modern notation. Euclid had to do this using highly geometric notation but we can use modern notation to do this easily. All we are going to do is take the sum of the proper divisors of N=(2n-1)(2n-1) and note that they are precisely N. Divisors of N take two forms, they either have a 2n-1 in them or they do not. The proper divisors that do not have such a factor are precisely the powers of 2. 1+2+4+8…+2n-1 = 2n-1 by our previous lemma. Then there are the divisors that do contain a factor of 2n-1. Those divisors are all of the form (2n-1)2k. For those divisors we get 1*(2n-1) +2(2n-1) 4*(2n-1) ... + 2n-2 = (2n-1) (1+2+4+8…+2n-2) =

(2n-1)(2n-1-1) by Lemma 1. So the sum of all the proper divisors is (2n-1)(2n-1-1) + (2n-1) = (2n-1)(2n-1) = N. And so we are done.

The proof of Euler’s result (that every even perfect number is of Euclid’s form) is more involved than than Euler’s proof but is not difficult. First a small notational change: Let σ(n) be the sum of the positive divisors of n. For example, σ(4)=1+2+4=7. Note that unlike are previous sums this includes the number itself. Observe that N is perfect if and only if σ(N)=2N. It turns out that for most purposes σ(n) is nicer to work with than the sum of the proper divisors which is of course σ(n)-n.

Lemma 2: σ is multiplicative. That is, σ(ab)= σ(a)σ(b) whenever a and b are relatively prime.[2]

Proof: Observe that for any divisor d of ab we can write d=a1b1 where a1 divides a and b1 divides b. Moreover, since a and b are relatively prime this representation is unique. Thus, σ(ab)= (1+d1 + d2… + dk) = (1+a1+a2..+am)(1+b1+b2…+bn)= σ(a)σ(b) since every di can is the product of some aj and bh. Q.E.D.

We also need one other function. Define h(n)= σ(n)/n.

Lemma 3:

1) h(n) equal to the sum of the reciprocals of the positive divisors of n.

2) Furthermore, h(n) is multiplicactive.

3) If a divides b a is less than b then h(a) is less than h(b).

The proof of this lemma will be left as an exercise to the reader.

Also, it is helpful to note that N is perfect if and only if h(N)=2. It turns out that for constructing a general theory h(n) is the function in that some sense matters the most.

Now we are ready to prove Euler’s result:

Proposition: If N is an even perfect number then we may write N = (2n-1)(2n-1) where 2n-1 is prime.

Proof: Assume N is an even perfect number. We may write N as m2k where m is odd. By our earlier remarks this means σ(m2k) = 2m2k = m2k+1. Now, since m is odd it is certainly relatively prime to 2k. So σ(m2k) = σ(m)σ (2k)= σ(m)(2k+1-1) (by Lemma 1). So σ(m)(2k+1-1)= m2k+1. Now, 2k+1-1 divides m2k+1. Since 2k+1 is a power of 2, we must have 2k+1-1 divides m. Now, if m is not prime we must have h(m) >= 1 + 1/(2k+1-1) + 1/d >>= 1 + 1/(2k+1-1) for some non-trivial divisor d (see part 1 of Lemma 3 above). But then an easy calculation establishes that h(m2k) > 2m2k which is a contradiction. So m must be prime and we are done.

Throughout this blog post I have referred to Mersenne primes as primes of the form 2n-1. In fact, in order for such an integer to be prime one also needs that n is prime. If n=ab for some a,b>1 then we can use the factorization trick xm-ym =(x-y)(xm-1 +xm-2y +xm-3y2… xym-2+ym-1) to get 2ab-1 = 2ab-1a = (2b-1)(2b(a-1) … +1). Thus, mathematicians talk about Mersenne numbers being numbers of the form 2p-1 prime. Not all such numbers are prime. For example, 211-1 = 23*89. But it turns out that there are very quick ways of testing whether such numbers are prime. Those methods are beyond the scope of this blog post which is already becoming quite lengthy. However, I will say that those fast methods have resulted in Mersenne primes being the largest known primes for most of the last 100 years.

There is a distributed computing project searching for more such primes. The project, called “GIMPS” for Great Internet Mersenne Prime Search, has found most of the Mersenne primes found recently. That project allows you to download software which runs in the background and uses your computer’s spare processing power to search for Mersenne primes. Recently they discovered the 45th and 46th known Mersenne primes. These two numbers 243,112,609-1 and 237,156,667-1 are each in the range of 10 million decimal digits long. These are big numbers. I strongly urge readers to go download the software for GIMPS. It doesn’t cost anything, doesn’t take up your time and you might even find something interesting.

In this post I’ve laid out the historical basis and some of the intellectual basis for caring about large primes. In my next post in this series I will discuss practical reasons why people care about large primes. I’ll discuss how you can share a secret with someone without having to worry about eavesdroppers and how that is relies on prime numbers.

[1] The astute reader will note that we have switched from talking about perfect numbers in general to only talking about even perfect numbers. What about perfect numbers that are odd? The answer is that no one knows. There are many restrictions on what an odd perfect number must look like. Any odd perfect number must be very large (greater than 10300) and have at least 9 distinct prime factors. There are good reasons (especially those presented by Carl Pomerance) to believe that no such numbers exist. However, a proof is not in sight.

[2] If anyone suspects that I’m writing posts on this subject so I can talk about multiplicative functions which are some of my favorite functions, they may be right.