God Plays Dice

From Robert Sedgewick's web site: slides for a talk entitled Impatiemment Attendu, given at a conference in honor of Phillipe Flajolet's 60th birthday. The gist of this talk appears to have been something like "The book will be out soon, after about thirty years of gestation." (That's Analytic Combinatorics, in case you're wondering.)

I mention it because apparently, at the beginning of this month in Paris, this post I made in September was projected on a big screen in front of a bunch of important people. I am of course amused. (The title "impatiemment attendu" is not mine, though; I took it from a paper by Nicolas Pouyanne. I suppose the English translation "impatiently awaited" is mine, but this was not a translation that required some huge inspiration.)

At the time, Amazon said that the book would be out on December 31. It's December 31. It's not out yet, as far as I know. I'll be at ANALCO '09 on Saturday. A slide in the presentation says that the book will be available at SODA (ANALCO takes place the day before); maybe the book will be there?

I have a new e-mail address.

To figure it out, concatenate the first three letters of my first name, my entire last name, and "@gmail.com".

The intrepid reader can figure out my "academic" e-mail address. Once I get things set up those should redirect to the same place anyway. (I'm tired of checking multiple addresses.)

And I apologize for obfuscating the address like this, but it's a new address, and I'd like to keep the spammers at bay for at least a little while.

Happy New Year! (Do I have any readers in Japan, Korea, Australia, or anywhere else where it's 2009 already? And Kate, if you're reading this, I urge you to remember that you're on vacation and you should get off the Internet.)

While reading a paper (citation omitted to protect the "guilty"), I came across a reference to an "n-dimensional tetrahedron", meaning the subset of Rⁿ given by

x₁, ..., x_n ≥ 0 and x₁ w₁ + ... x_n w_n ≤ τ

for positive constants w₁,..., w_n and τ.

Of course this is an n-simplex. But calling it a "tetrahedron" is etymologically incorrect -- that means "four faces", while an n-simplex has n+1 faces. This probably occurs because most of us tend to visualize in three dimensions, not in arbitrary high-dimensional spaces.

I'm not saying that "tetrahedron" shouldn't be used here -- I'm just pointing out an interesting linguistic phenomenon.

I recently read What Mad Pursuit: A Personal View of Scientific Discovery
, which is Francis Crick's account of the "classical period" of molecular biology, from the discovery of the double helix structure of DNA to the eventual figuring out of the genetic code. It differs from the more well-known book by James Watson, The Double Helix: A Personal Account of the Discovery of the Structure of DNA, which focuses more on the characters involved and less on the science.

Crick was trained as a physicist, and learned some mathematics as well, and every so often this pokes through. For example, back when the nature of the genetic code wasn't known, combinatorial problems arose to prove that a genetic code of a certain type was or was not possible. One idea, due to Gamow and Ycas was that since there are twenty combinations of four bases taken three at a time where order doesn't matter, perhaps each one of those corresponded to a different amino acid. This turned out to be false. Another, more interesting problem comes from asking how the cell knows where to begin reading the code. What is the largest size of a collection of triplets of four bases such that if UVW and XYZ are both in the collection, then neither VWX nor WXY is? The reason for this constraint is so that the "phase" of a genetic sequence is unambiguous; if we see the sequence UVWXYZ, we know to start reading at the U, not the V or the W. Thus the collection can't contain any triplet in which all three elements are the same, and it can contain at most one of {XYZ, YZX, ZXY} for any bases X, Y, Z, not necessarily distinct. There are sixty triplets where not all three elements are the same, thus at most twenty amino acids can be encoded in such a code. There are solutions that acheive twenty; see the paper of Crick, Griffith, and Orgel.

Note that the "20" in the two types of code here arises in different ways. If we assume a triplet code with n bases, then the first type of code can encode as many as n(n+1)(n+2)/6 amino acids, the second (n³-n)/3.

Crick says that the more general problem of enumerating the number of codes which imply their own "reading frame" was considered by Golomb and Welch, and separately Freudenthal. Based on the title and the date, I think the first of these is the paper I point to below -- but our library doesn't have that journal in electronic form, and the physical library is closed this week!

References
F. H. C. Crick, J. S. Griffith, L. E. Orgel. Codes Without Commas. Proceedings of the National Academy of Sciences of the United States of America, Vol. 43, No. 5 (May 15, 1957), pp. 416-421.

George Gamow, Martynas Ycas. Statistical Correlation of Protein and Ribonucleic Acid Composition Statistical Correlation of Protein and Ribonucleic Acid Composition. Vol. 41, No. 12 (Dec. 15, 1955), pp. 1011-1019.

Golomb, S.W., Gordon, B., and Welch, L.R., "Comma-Free Codes", The Canadian Journal of Mathematics, Vol. 10, 1958. (Citation from this list of Golomb's publications; I haven't read it.)

Terence Tao: Use basic examples to calibrate exponents. This article, for the eventual Tricki, gives many examples of the following basic procedure. In many problems there is a "size" parameter N, and the problem has an "answer" that we believe for some reason behaves like N^k for some constant k. A quick way to find N is to look at "basic examples" (say, random graphs in a graph-theoretic problem).

The interesting thing about this article -- and about the Tricki as a whole, once it finally launches -- is that its organizational principles are not the same as most mathematical exposition. A typical lecture or section of a textbook gives problems with similar statements but not necessarily with similar proofs; the Tricki will group together problems with similar proofs but not necessarily with similar statements.

Comfort with meaninglessness the key to good programmers, from Boingboing.

Is this true for mathematics as well as computer programming?

The New York Times reports on bad housing news:

The median price of a home plunged 13 percent from October to November, to 181,300ドル from 208,000ドル a year ago. That was the lowest price since February 2004.

They mean that house prices have gone down 13 percent in a year, i. e. from November 2007 to November 2008. That's what the National Association of Realtors press release says.

But one sees this pretty often -- the confusion between monthly declines and annual declines. And sometimes a 1% decline in a month might be reported as a "12% per year" decline -- but then the "per year" gets dropped, the statement "prices of X dropped 12% this month" is made, and those who aren't familiar with how people who care about the price of X report their numbers get confused.

Don't get me wrong -- a drop of 13% in a year is still a big deal. But a drop of 13% in a month would be a much bigger deal.