No more Knuth checks

Have you seen the news? Knuth has announced that he will no longer be writing personal cheques, for security reasons. As an alternative, he suggests

Instead of writing personal checks, I’ll write personal certificates of deposit to each awardee’s account at the Bank of San Serriffe, which is an offshore institution that has branches in Blefuscu and Elbonia on the planet Pincus.

As most Knuth cheques are never cashed anyway (they “have apparently been cached”), this is perfectly as good and perfunctory as the old system, with the additional advantage that there is now a Hall of Fame :-)

Although it is brownie points that are being awarded now (“kudos, not escudos”), he also offers to find a way to send actual money to anyone who wants it :P

Advertisement

Google and inflection

It is a generally useful feature that Google tries to “Do What I Mean” instead of taking our queries literally to “Do What I Say”, but sometimes it’s annoying.

For example, searching for [sarah palin trigonometry] includes results that do not contain the word ‘trigonometry’ at all. Fortunately, searching for [sarah palin “trigonometry”] works (which might contradict intuition that putting quotes around single words should not matter).

I have seen Google do this many times (return results which do not contain the words searched for), but can’t recall other examples right now… can you?

A theorem by Euler on partitions

There are so many beautiful facts in mathematics that are not as well known as they deserve to be. [Just today I couldn’t find an online reference for the Robinson-Schensted(-Knuth) correspondence.] Some efforts in the direction of communicating these to an online audience have been collected in the Carnival of Mathematics (41 so far) posts on various blogs. Another good idea I recently found is Theorem of the Day. [EtA: Found at Theorem of the Day: RSK correspondence.]

Anyway… today I attended a lecture on Euler by William Dunham (great talk!) where after a brief biography of Euler and a tour through some of his results, he showed Euler’s proof of a particular theorem about partitions. It will be familiar to anyone who has read about integer partitions, but it deserves to be familiar to everyone! So here is a sketch of the proof, for your reading pleasure. [It doesn’t do justice to present only a “sketch”, but I have assignments due tomorrowtoday… feel free to take it and turn it into some form worthy of the content. :-)]

Now when I say “a theorem by Euler”, it is very ambiguous which one I mean, and even with the “on partitions” restriction, there are several. So let me state it:

The number of partitions of a number into odd parts is the same as the number of partitions of the number into distinct parts.

[If I remember correctly what was narrated in the talk, one of the Bernoullis wrote to Euler asking him a question about partitions, and within a few days (think of the postal system then) Euler replied with a proof of the theorem, along with a apology for the delay caused by the poor eyesight he had recently been suffering from. This is an outline of his proof, ask me about the details.]

Let D(n) denote the number of partitions into distinct parts, and O(n) denote the number of partitions into odd parts. Then we have:






which proves the theorem.
The first equality, which gives the generating function for the D(n)s, can be seen as follows: when you “expand” and write out , you get , where the coefficient of any term is exactly the number of ways of writing as a product of distinct factors of the form , which is . Similarly, the last equality, about the generating function for the O(n)s, is because the coefficient of any term in is exactly the number of ways of writing as a product of (not necessarily distinct) for odd .

The result might not be terribly important, but this idea was the starting point for proving several observations about partitions, and the method has led to the discovery of several facts and is more widely applicable than you think!

If you want a combinatorial proof by bijection (“For Entertainment Only”) here is an outline of one:
Given a partition of n into odd parts, say
,
write each “in binary”, by which I mean as a sum of distinct powers of two. So you have
.
Now just get rid of the brackets, and note that all terms are distinct.
E.g. for ,
i.e. , you get the partition
.
[Exercise: Why are all parts distinct?]

Conversely, given a partition into distinct parts, we can separate the “even part” from the “odd part” in each term, so for example with , we write
, and collect the coefficients of each odd number, so , which was our original odd partition.
[Exercise: Why can’t we do the same thing starting with any partition?]

[Question: Is the bijective proof related to the algebraic one?]

Windows semicolon

XP came and went (sure nobody likes Vista, but how long do you think anyone will have a choice?), but this doesn’t seem to have received enough attention:

A semicolon in Windows XP’s shutdown screen:

The last time a semicolon was sighted, the New York Times made a big fuss of it, and included a baffling comment by Noam Chomsky.