Saturday, May 30, 2009

Jason Brown on Mathematics and Music

At the recent Canadam conference on discrete and algorithmic mathematics, Jason Brown of Dalhousie gave a great talk on mathematics and music. He accompanied his talk on the guitar, playing excerpts from jazz and rock standards to illustrate his points.

Jason was featured in the Wall Street Journal, among other places, for his work on using the Fourier transform to decode the mysterious opening chord in the Beatles song "A Hard Day's Night" (it turns out that the key ingredient is an F played on the piano).

Jason used his analysis of the mathematical underpinnings of Beatles songs to compose a song in the style of the Beatles, which he then recorded in the studio with musicians Scott Ferguson, Alex Vaughan and vocalist Hal Bruce. There's a great video of the performance of "A Million Whys" here.

Thursday, May 28, 2009

Dejean's Conjecture Solved!

Dejean's conjecture is one of the oldest conjectures in combinatorics on words. Yesterday, at the CANADAM conference in Montréal (where I also gave a talk), James Currie and my former Ph. D. student Narad Rampersad announced the final step in the proof of this famous conjecture. That's Narad at the left and James on the right. (Photo courtesy of Amy Glen.)



Dejean's conjecture concerns repetitions in infinite words. A square is a repetition of the form xx, where x is a nonempty word. We can write this in shorthand as x2. Examples of squares include the English word hotshots and the French word chercher. A cube is a repetition of the form xxx; the only example I know of in English is the sort-of-word shshsh. About a hundred years ago, the Norwegian mathematician Axel Thue gave examples of an infinite word over a 2-letter alphabet containing no cubes and an infinite word over a 3-letter alphabet containing no squares. It is easy to see that there are no infinite words without squares over a 2-letter alphabet, or cubes over a 1-letter alphabet.

More generally, one can try to avoid rational powers, not just integer powers. We say a string w is a p/q power if it can be written in the form xkx' where x' is a prefix of x and the length of w is p/q times the length of x. For example, the French word entente is a 7/3 power, as it can be written in the form (ent)2e. Similarly, entanglement is a 4/3 power.

Dejean's conjecture concerns the largest possible exponent e such that there exists no infinite word over a k-letter alphabet avoiding powers of exponent e or greater. We write this exponent as RT(k), where RT stands for "repetitive threshold". Thue proved that RT(2) = 2. In 1972, Françoise Dejean proved that RT(3) = 7/4. She conjectured that RT(4) = 7/5 (which was later proved by Pansiot) and RT(k) = k/(k-1) for k ≥ 5.

Over the last 35 years the range of exponents for which Dejean's conjecture was known to hold slowly increased. Moulin Ollagnier proved the conjecture for 5 ≤ k ≤ 11; Mohammad-Noori and Currie proved it for 12 ≤ k ≤ 14. A real breakthrough occurred a couple of years ago, when Carpi proved the conjecture for all k ≥ 33. Currie and Rampersad then improved Carpi's construction to resolve k ≥ 27, and more recently they used Moulin Ollagnier's techniques to resolve the remaining cases 15 ≤ k ≤ 26. This competely resolves Dejean's conjecture. You can read Currie and Rampersad's paper here.

At the conference we also learned that (as is often the case in mathematics and computer science) nearly simultaneously, a proof of the remaining cases along different lines has been described by Michaël Rao of the Université de Bordeaux.

So congratulations to James Currie, Narad Rampersad, and Michaël Rao for finally resolving this famous conjecture!

Thursday, May 21, 2009

Poll Confirms It: The More Religious You Are, The More Immoral You Are

Here's a link to a fascinating poll conducted by the Pew Forum on Religion and Public Life.

According to the results, 62% of white evangelical Protestants say torture against suspected terrorists can "often" or "sometimes" be justified. But only 40% of the "unaffiliated" agreed with that.

Among those who attend religious services at least weekly, 54% agreed that torture can "often" or "sometimes" be justified. But only 42% of those who "seldom" attend religious services agreed with that.

In other words, the more you are drenched with God-talk, the more you are likely to okay the abhorrent practice of torture.

The next time some theist rails about the immorality of atheists, point them to this poll.

Tuesday, May 19, 2009

What a Drag!

I just discovered last night that the slow leak we had in the kitchen sink leaked through the kitchen floor to the basement below. Unfortunately this was exactly where I was storing my issues of Skeptic (I had a complete collection starting with Vol. 1 No. 1) and Skeptical Inquirer, with the result that nearly all of the issues I had been saving have been destroyed by water and mold. I am now, with mask over mouth, removing all the issues and dumping them. Too bad -- I had planned to donate my complete collection of Skeptic to the local public library.

Saturday, May 16, 2009

Michael Egnor Misses the Point

Whenever the Discovery Institute wants to hire a new spokesman, I imagine a conversation like this:

"Who can we get who is abysmally ignorant, illogical, and not afraid to show it?"

"Casey Luskin?"

"No, we already hired him. How about Michael Egnor?"

"Great idea. He has the added bonus of the arrogance of a surgeon. I'll send the invitation off right away."

Michael Egnor read my recent piece criticizing Margaret Somerville's article in Academic Matters. Somerville claimed that when parents decide to abort a child with Down's syndrome, that is a "eugenic" decision. "Only the decision not to abort when the fetus has Down's syndrome", Somerville claimed, "is not a eugenic decision". I pointed out that Somerville was doing here exactly what she decried earlier: labeling a decision she doesn't like as "eugenic", and therefore bad, without explaining why it is bad. I also pointed out that many parental decisions, such as choosing whom to have children with, could be considered "eugenic" in exactly the same way, yet I imagine Somerville would consider those acceptable. Following Somerville's logic, only picking someone at random for your mate "is not a eugenic decision."

But of course, Egnor missed the point entirely (and also managed to misspell my name). The point was not about eugenics, or Down's syndrome children at all; it was about Somerville's hypocrisy.

There are lots of other fallacies in Egnor's piece; you may enjoy spotting them all. Here are a few:

Here is how Egnor defends religion: "The existence of God is not a “ridiculous and unverifiable claim;” it's the conclusion reached by the vast majority of human beings living today and who have ever lived, and is a viewpoint held by most of the best philosophers, ethicists and scientists in history." Here he is using both the Fallacy of Appeal to Belief and the Fallacy of Appeal to Authority. Two fallacies in one sentence; truly a remarkable achievement.

Next, he claims there are thoughtful arguments for atheism (but doesn't provide a single example of an argument he believes is "thoughtful"). Then he dismisses the arguments of "Dawkins, Dennett, Harris, Myers, and Hitchens" as "puerile". (Of course, like Somerville, he doesn't give a single reason why he thinks this.) This is the Fallacy of Appeal to Ridicule.

He then invents an argument against Christianity -- ‘some bad things have been done by Christians, therefore Christianity is untrue’ -- and implies it is something that I believe (or that Dawkins et al. believe). This is the Fallacy of the Straw Man.

Next he goes on to smear Planned Parenthood, the National Organization of Women, and the Pro-Choice Resource Project as "eugenic". There's no denying that the word "eugenic" has a nasty reputation in our society, and Egnor doesn't hesitate to exploit it. (For the same reason, creationists love to associate "Darwinism" with both fascism and communism; they know how effective a smear can be to incite the Fallacy of Appeal to Emotion.) I can't resist pointing out that along the way, Egnor confuses "inference" with "implication".

Why does "eugenics" have a nasty reputation? It is not because the goal - to have healthy offspring - is something any parent would disagree with. After all, parents of Asheknazi Jewish heritage get tested for the Tay-Sachs gene, but I don't see Egnor labeling Dor Yeshorim as "eugenic" (but he would have to if he were consistent). No, it is because "eugenics" is equated in many people's minds with the centrally-directed, government-enforced, coercive eugenics advocated by the Nazis. It is one thing - and I think entirely acceptable - for parents to decide to not have a child with Tay-Sachs; it is another thing entirely for the government to murder or sterilize people perceived to have defective genes. Labeling both as "eugenic" is facile -- par for the course for Egnor -- but misses an essential difference.

Egnor goes on to say "In the atheist/Darwinian view, eugenics is moral, even virtuous." Here he is committing yet another fallacy: the Fallacy of Is-Ought. Darwinists (more properly, any scientist or person who understands the theory of evolution) are what they are because they hold to a scientific theory, not a description of ethical behavior.

Egnor then gives three reasons against parental choice. Unfortunately, none of them are very good. His first is "I have fairly traditional Christian beliefs, and I find the assertion that people should be bred and culled like farm animals to be repugnant." But when partners decide not to have children because (say) they both carry a gene like Tay-Sachs, or decide to abort a fetus that will have the disease, that has nothing to do with "be[ing] bred and culled like farm animals", unless the farm animals Egnor is thinking of are breeding themselves. By equating government-enforced eugenics with parental choice, Egnor commits the Fallacy of Equivocation. Furthermore, since 80% of pregnancies end unsuccessfully, with about half that figure attributed to genetic defects, it may be fairly said that Egnor's god is the Great Eugenicist in the Sky.

The second is "eugenics has stained my profession". But again, the eugenics that stained the medical profession consisted of, e.g., forced sterilization, not parents deciding whether to have children or to abort a fetus with a severe defect.

The third reason is that Egnor knows children with cognitive defects and finds they have value. That's nice, but nobody's claiming that these children should be killed or their parents made a mistake. What Egnor misses entirely, because of his sectarian religious viewpoint, is that for many parents, the decision is not between "having this child who will die a painful and gruesome death from Tay-Sachs before age 4" or "not having any child at all", but rather "having this child who will die of Tay-Sachs" or "not having it, and having a healthy child later on".

Finally, recall that my original question was "Why, exactly, would the world be better off with more Down's syndrome children?" Egnor says in response "The world is made better by every person." Even if we ignore the fact that Egnor's Pollyanna claim is clearly untrue (how was the world made better by Hitler or Pol Pot?), his response doesn't address the question. Parents are faced with limited resources. If they choose to raise a healthy child instead of an unhealthy child, why does Egnor want to refuse them that choice?

If Egnor really believes that the world would be better off with more Down's syndrome children, he should be doing everything he can to promote their production. As a medical doctor, he should be counselling couples to postpone having children until the wife is at least 40; after age 45, that increases the chances of having a Down's syndrome child to 1 in 19. Similarly, he should be encouraging older men to have more children, since paternal age is apparently a factor, too. Since he does not, it is clear that even Egnor does not believe that the world would be better off with more Down's syndrome children.

About 90% of parents decide to abort after a Down's syndrome diagnosis. If I shared Michael Egnor's fondness for logical fallacies, I would say that is evidence he is wrong. Instead, I will simply point out that most parents do not view having a Down's syndrome child as a good way to spend their limited parental resources. I don't demand that parents choose the way I would under the circumstances; I have great sympathy for parents faced with such a difficult decision, and I support their right to choose, no matter how they decide. Despite his attempt to tar me with the eugenic brush, it is his viewpoint that has more in common with totalitarian thinking.

And like the totalitarian, Egnor chooses to attack me from a forum that does not allow comments. What is he afraid of?

Thursday, May 14, 2009

Monty Hall is out


A pleasant surprise arrived in the mail today: Jason Rosenhouse's new book, The Monty Hall Problem. I read a first draft of the book and found it excellent.

Alf van der Poorten says that the definition of a good book is that it mentions you. Under that criterion, this is a very good book indeed, as I appear on the back cover, giving the book an endorsement.

I recommend this book to anyone interested in probability.

Sunday, May 10, 2009

Weird Google Maps Error

If you search for 2212 Line 34, Shakespeare, ON on Google Maps, you get a location that is something like 50 km from the true location. Shakespeare is actually between New Hamburg and Stratford, Ontario.

Google Maps seems quite unreliable for Southern Ontario. It used to be that when you searched for the Waterloo-Wellington
airport, you would get a location about 25 km from the true one.

It would be interesting to understand what about the data or algorithm results in such a bizarre error. It would also be nice if it were easier to report errors in Google maps.

Wednesday, May 06, 2009

Acknowledging Priority

One of the principles of publishing in mathematical and scientific journals is that, generally speaking, you cannot publish results that are already known.

Of course, publishing known results happens all the time anyway, because authors and referees cannot know the entire literature, and different authors use different terminology and notation. I once rediscovered a simple way to provide a lower bound on the size of nondeterministic finite automata, and published it, but later found out the result had already appeared in the literature -- indeed, the author had even sent me a reprint which, to my chagrin, I found languishing in my files. The point is that

1. Authors should not knowingly attempt to republish known results;

2. Referees should make at least some attempt to verify that the claimed results are new;

3. Editors should not agree to publish papers containing known results presented as if new.

There are some exceptions to these rules, however. Often one needs to state other researchers' results because the statement is crucial to the exposition. In this case, authors must be careful to provide the attribution and correct citation to the literature. In a "survey paper", one often brings together a large number of known results and tries to tie them into an overarching theme. Again, authors must be careful to provide the correct citations.

It is a violation of scientific/mathematical ethics to knowingly publish as new, results that are already known.

Recently a paper was submitted to a journal I edit. I sent it out to a referee, who observed that he/she had already refereed the paper for another journal, and the referee sent me the old report. That report pointed out that several of the results claimed as new were actually already in the literature. The authors had resubmitted the paper to me without making the required changes, acknowledging priority to others. This is a violation of mathematical ethics.

Saturday, May 02, 2009

Margaret Somerville in "Academic Matters"

Here's a piece by McGill philosopher Margaret Somerville in the OCUFA publication Academic Matters. (OCUFA is the Ontario Confederation of University Faculty Associations.) I found it very shoddily argued.

For example, she rightly decries the suppression of speech on campus (something that I have also done; see here). But she then says "some people are going even further: they want to force physicians to act against their conscience under threat of being in breach of human rights or subject to professional disciplinary procedures for refusing to do so". I think these cases are not remotely comparable. The latter question revolves around whether physicians have the right to shirk their professional duty and engage in discrimination simply by calling their view "religious". Would Somerville also support the right of a physician to refuse to treat black patients, because the physician belongs to an Aryan church that views blacks as subhuman? I doubt it. Then how can she support the "right" of physicians to treat lesbian couples differently from heterosexual couples?

She says, "Political correctness operates by shutting down non-politically correct people's freedom of speech. Anyone who challenges the politically correct stance is, thereby, automatically labeled as intolerant, a bigot, or hatemonger. The substance of their arguments ... is not addressed ..." But then, just a few paragraphs later, she labels Richard Dawkins, Sam Harris, and Christopher Hitchens as "fundamentalists". I do not know exactly what she means by "fundamentalist" in this context, but it seems to me she is doing here exactly what she decried previously: applying a label to them without addressing the substance of their arguments.

Later she says "Only the decision not to abort when the fetus has Down's syndrome is not a eugenic decision". But here she is begging the question: why are decisions that she labels as "eugenic" necessarily bad? Why, exactly, would the world be better off with more Down's syndrome children? By her reasoning, positive assortative mating would be considered "eugenic"; yet most of us practice some form of it.

She seems to imply that religion deserves an equal place at the table as science. But she doesn't say why, other than to point out the obvious fact that many people hold religious views. Many people believe that 9/11 was a US government conspiracy, too, but I don't see why we are obligated to take their views seriously. With respect to religion, why should religious dogma, which maintains ridiculous and unverifiable claims, be treated in the same way as science and rational thinking?

Probably you can find more examples of shoddy argument in this piece. Academic Matters has a history of publishing anti-science and anti-rationalist screeds.