Mathematicians in today's New York Times crossword

A clue from today's New York Times crossword puzzle: "Mathematician Post or Artin". (Four letters. If you don't know the answer, click on the links.)

The crossword blogs (here, here, here) think this was an unfair clue; this one says that "Neither [...] will be familiar to most solvers, or even to all mathematicians."

I got this with no problem. But it took me a moment, because the son of the Artin the clue was about was one of my professors as an undergrad. A few commenters here and there say they needed some of the crossing letters to decide which Artin the clue referred to.

On today's New York Times crossword

Today's New York Times crossword is by Tim Wescott. There is someone who's commented at Secret Blogging Seminar with that name.

Anyway, here are some of the answers:

4 down: EVEN TENOR
6 down: PERFECT GAME
11 down: ODD MEN OUT
25 down: SQUARE KNOTS
33 down: REAL MCCOY
37 down: PRIME TIME

There was one more clue saying that the first word of each of those answers (which had a star before the clue) described the number of its clue. So 4 is even, 6 is perfect, 11 is odd, 25 is square, 33 is real, and 37 is prime.

33 down seems like a bit of a cop-out to me. But I'm not saying I could do better at making a crossword. Crosswords (especially American-style ones) are hard to make; read the information-theoretic argument in MacKay's book for some justification why.

For the non-mathematicians who may have stumbled in (and the mathematicians who don't remember this particular bit of trivia), I feel like I should point out what a perfect number is. A number is perfect if it's equal to the sum of all the numbers it's divisible by. So 6 is divisible by 1, 2, and 3, and 1 + 2 + 3 = 6. 28 is the next perfect number; it's divisible by 1, 2, 4, 7, and 14, and 1 + 2 + 4 + 7 + 14 = 28. But 12 isn't perfect; it's divisible by 1, 2, 3, 4, and 6, and 1 + 2 + 3 + 4 + 6 = 16, which isn't 12. We call 12 "abundant" because 16 (the sum of its divisors) is more than 12. Just under one quarter of integers are abundant, which is entirely irrelevant.

First prime numero

From Merv Griffin's Crosswords, a crossword clue: "First prime numero", three letters.

Three of the contestants answered UNO.

Of course, the answer is DOS.

From today's New York Times crossword

Setting numbered in multiples of the square root of 2. (Five letters.)

The answer.

The Frogger crossword

Check out the New York Sun's crossword for today, September 6, 2007.

The theme of this puzzle is "FROGGER", as we're told by the entry in the center; the crossword was constructed so that you can get from a square at the bottom to a square at the top going via only squares that contain letters in the word FROGGER. A picture of the solved crossword with just the FROGGER letters is at the left.

As it turned out, I'd been absent-mindedly flipping through Percolation by Geoffrey Grimmett right before taking a break to do this crossword. One of the standard results in the theory of percolationis that if we start with an infinite grid and fill in some proportion p of the squares at random, then with probability 1 there will be an infinitely large filled cluster containing the origin when p > 1/2, and if p < 1/2 there's an infinite filled cluster containing the origin with probability 0. (Usually one talks about open and closed bonds -- the lines connecting the sites -- instead of open and closed sites, but since the square lattice is self-dual that doesn't matter.)

So it's noteworthy that this is possible here; it wouldn't be possible in a random crossword. We wouldn't be able to get "far away" from a given site using only letters that are taken from some small set. The transition isn't going to be quite so sharp in the non-infinite cases, and the standard 15-by-15 crossword isn't all that close to infinity. Furthermore, finding a long path is even less likely in a crossword than in an ordinary square lattice, because in a crossword there are some black squares.

Furthermore, percolation theory usually assumes that sites are independent; this isn't true in a crossword, because the letters in sites adjacent to each other are correlated. For example, if a given square contains a T, the letter to the right of it or below it is probably more likely to be an H than otherwise, because the pair of letters "TH" is quite common. Any serious attempt to think about percolation in crosswords -- although I can't imagine anyone would study that seriously -- would have to take this into account.

A brief explanation, What is... Percolation by Harry Kesten, was published in May 2006 in the notices of the AMS.

Who gets credit for quadratic reciprocity?

In today's New York Times crossword, there's a clue "Discoverer of the law of quadratic reciprocity." The correct answer is, according to the crossword, this guy. I originally put in this guy instead. It turns out, according to the Wikipedia article on quadratic reciprocity, that "The theorem was conjectured by [first guy] and Legendre and first satisfactorily proven by [second guy]. [Second guy] called it the 'golden theorem' and was so fond of it that he went on to provide eight separate proofs over his lifetime." (I am deliberately obscuring the links because you might still want to do the crossword.)

Now, who should get the credit for "discovering" a mathematical result? The one who first suspected it might be true, or the one who proved it? I'm of the opinion that in this case they should share the credit (along with Legendre), mostly motivated by the fact that both of the people involved are Really Big Names. There are some examples in which First Guy discovered something and it's not named after him, but Erdos (and I don't think I'm spoiling anything by admitting that Erdos is neither First Guy nor Second Guy) once said that Goldbach's conjecture should be named for Goldbach, not First Guy, because "[First Guy] is so rich and Goldbach is so poor, it would be like taking candy from a baby." I don't know the history in the case of quadratic reciprocity. But I'm motivated here mostly by the fact that it's a lot easier to prove something if you already have reason to suspect it's true. For one thing, if you suspect something is true it is often on the basis of data, and you can look at that data and see how you might generalize the patterns you can see in it. (Quadratic reciprocity is almost certainly such a case, since data is easy to generate.) Secondly, there's a tremendous psychological boost to be gained from knowing that someone whose judgment you trust thinks something is true. Mathematicians are trained to think that only proofs matter, and I suspect there's an extreme strain of this that thinks that we really don't have any idea whether something is true until we've proven it or not; but someone who has given copious hints in the right direction surely deserves some of the credit. The tendency seems to be to give the credit to the person who put the last link in place; the highest-profile example is of course Wiles' proof of Fermat's last theorem. But what Wiles really showed was a special case of the Taniyama-Shimura conjecture; Ribet had already shown that Fermat would follow from this special case. So it seems to me that Ribet definitely deserves some of the credit (for establishing that as the right target for anyone wishing to prove FLT) and probably Taniyama and Shimura as well.

In the case of this particular theorem I realize that there are a very large number of people involved in one way or another, and it's hard to know who exactly to assign credit to, or -- and this is getting really silly -- how much credit to assign to them. Fermat proved that x³ + y³ = z³ has no trivial solutions. What should this count for? On the one hand, it's the first case. On the other hand, there are infinitely many cases. Should Pythagoras get some credit for coming up with his theorem, which inspired the whole thing? (Incidentally, any reasonable scheme of assigning "credit" to every mathematical result ever to all the mathematicians who were in some way involved has a pretty good chance of putting Pythagoras on top -- or at least of putting the Pythagorean theorem on top among theorems.) But even in the case of less famous results there are clearly a lot of people who did something towards them -- the people who first conjectured them, the people who proved some special case, the people who disproved some other special case (thereby helping to establish the boundaries of the result), and so on. Fortunately we don't need to find a way to quantify these contributions; decisions of who to hire or who to give prizes to can be made without them. (I'm not saying that the current hiring system is perfect, but it seems to work well enough.) And do you really want mathematicians in charge of some scheme that assigns a number to their total amount of mathematical contributions? Because let's face it, if you made up such a scheme mathematicians would find a way to beat it.

Except if it involved arithmetic. Mathematicians aren't any good at arithmetic.

(Oh, and this was going to be a post on how mathematically oriented people are good at crosswords. But it's not! Oh well. I'm sure I'll get around to writing that eventually.)

"Typewriter Trivia"

I do too many crosswords.

The New York Sun runs an excellent crossword, which yesterday was entitled "Typewriter Trivia" and featured the following four long entries, here with their clues:

Disposition to credulity (and the longest common word that alternates typing hands): ANTISKEPTICISM

Violet variety (and the longest common word that uses just the right typing hand): JOHNNYJUMPUP

Seesaw (and the longest common word that uses just the top typewriter row): TEETERTOTTER

Knitted garments for women (and the longest common word that uses just the left typing hand): SWEATERDRESSES

If you want to read more about crosswords, check out Amy Reynaldo's blog Diary of a Crossword Fiend -- the link is to the entry on the crosswords which were published yesterday. This particular entry also mentions her book How to Conquer the New York Times Crossword Puzzle: Tips, Tricks and Techniques to Master America's Favorite Puzzle, which comes out today.
Wikipedia, which has a lot of silly lists like this, tells us that TESSERADECADES and AFTERCATARACTS are also typeable entirely with the left hand, though they're less common. TETRASTEARATES also has this property, according to A Collection of Word Oddities and Trivia. To someone who does too many crosswords, it's also recognizable as a word that would often be found up against the right or bottom edge of a crossword, because it consists of letters that occur often at the end of words. (ASSERTS, ASSESSES, and so on are common in those positions.)

The longest word entirely typeable with the middle row is SHAKALSHAS, which is shorter than the others and also more obscure. There are no words which are entirely typeable with the bottom row of the standard keyboary, since it has no vowels. (The

What I'm led to wonder is, do we expect such words to be long? Longer words should be possible if we have larger sets of letters to work with. Georges Perec once wrote a novel called La Disparition which doesn't contain the letter "e" (and in French, no less, where this should be harder than in English!) and also Les Revenentes which contains no a, i, o, or u. The first of these was "translated" into English as A Void, although I don't know enough to know if this can really be called a "translation". This is considered noteworthy. But if someone wrote a book without a Q in it, nobody would care!

Letter frequencies can be found here, without regard for the frequency of the word in ordinary text. We can compute that 48.03% of letters come from the top row; 32.49% from the middle row; 19.74% from the bottom row. So we expect that it will be easiest to form words which come entirely from the top row, then the middle row, then the bottom row; this is in fact the case. Similarly, 61.27% of letters are drawn from the left hand; we can form even longer words with the left hand (14 letters) than with the top row (12 letters).

As for why we can form such long words with alternating hands? The Dvorak keyboard, which is a widely used alternate to the standard QWERTY keyboard, is set up so that letters which often occur consecutively are typed with opposite hands. It wouldn't surprise me if QWERTY uses that same principle, even if it's not consciously incorporated into the design.

(An earlier version of this post had some broken links. They should be fixed now.)