A conversation about complexity lower bounds, X

This is the final post in the series about complexity lower bounds. It ends not with any grand conclusion, but just with the three characters running out of steam. The main focus of this final instalment is the Gaussian-elimination problem mentioned in earlier instalments (find an explicit nonsingular matrix over that needs a superlinear number of row operations to turn it into the identity). The discussion follows a familiar pattern, starting out with some ideas for solving the question, understanding why they are hopelessly over-optimistic, and ending with some speculations about why even this problem might be extremely hard.

A mathematician watches tennis

Because the French Open and Wimbledon have been available on the BBC website I’ve been watching a lot of tennis recently. And as I do so I can’t help thinking about whether mathematics has anything to say about the tactics that the players should adopt in various situations. And the more I think (or rather, idly muse) about this question, the more it becomes clear that the modelling problem it presents is a pretty hard one. Most of this post will be a discussion of questions rather than a serious attempt to supply answers.

Just to make the discussion more concrete, here are a couple of more specific questions, which I’ll come back to later. The first one is fairly simple.

1. It is generally held to be a slight advantage to serve first in a set. The reasoning goes like this. Let’s suppose (for simplicity) that the game goes with serve till 4-4. If you are serving first, then you will be in a very dangerous position if your serve is broken, since you will then have to break back immediately or lose the set. However, at least you won’t have lost. By contrast, if you are serving second and the score is 4-5, then you can’t afford to be broken — if you are broken then you lose the set and do not get even a small chance to redeem yourself. And if you have just broken your opponent so that it’s 5-4, then you still have the task of serving for the set.

However, a simple model would suggest that this reasoning is flawed. If you have a probability of winning a game on your serve and a probability of winning it on your opponent’s serve, then over the next two games you have a probability of winning both, of winning one, and of losing both, and the order the games are played in makes no difference.

To thread or not to thread

The 500s thread of polymath1 is going to run out soon. Before I start what I think will be the 800s thread, I would like to ask whether the general view is that threaded comments would be a good idea for this, because I have recently learned from Luca Trevisan that WordPress now allows them. At the beginning of the experiment there appeared to be a clear view that threaded comments would be highly desirable. Now that things have quietened down somewhat, I find it less obvious. The simple numbering system has served us well (though one could have a numbering system like 8.13.2 for the second comment on the 13th comment of what would have been the 800s thread) and with a more tree-like structure one would lose the easily viewed chronological order of the comments. But perhaps a very limited amount of threading would be helpful, e.g. for quick comments such as “There’s an easy counterexample to that: just take …” or “I have now seen how to prove this: more details can be found in comment 8.27 below.” So the choices are to go the whole hog and allow many levels of nested comments, to leave things as they are, or to allow limited threading (up to a maximum depth of 1, say, counting a comment itself as level 0) with a general agreement that it will be used sparingly. (The last option sounds potentially good, but would depend on people adhering to this agreement, and I can’t tell at this stage whether they would.)

The possible merger of the LMS and the IMA

Discussions concerning a proposed merger between the London Mathematical Society and the Institute of Mathematics and its Applications are at a fairly advanced stage. Details can be found here. A series of meetings has taken place round the UK, and the project is taking on a feel of inevitability. I am still trying to work out what I think about it, but my natural instinct would be against it. At the very least, I hope that LMS members will not vote for it just because they assume that those who are calling for it and have put a great deal of work into it must be right. The purpose of this brief post is not to discuss the merits or otherwise of the idea, but just to draw attention to the fact that there are some who oppose it: their arguments should be carefully considered. If you want to consider them then you might like to look at a blog that has been started by some LMS council members, where some of these arguments are set out. Even if you are not a member of the LMS, comments would be welcome. That is particularly true if you have relevant experience of other mathematical societies.

A small countability question

This is a short post to ask a simple question that arises out of the discussion in a previous post about countability. As is well-known, the familiar statement that a countable union of countable sets is countable requires the axiom of countable choice. Indeed, it comes in in the very first step of the proof, where one says something along the lines of, “For each set let be an enumeration of its elements.” This uses the axiom of choice because if we don’t know anything about the sets then we can’t actually define these enumerations: we just have to assert that a sequence of enumerations exists.

However, if we do have explicit enumerations of the sets then the proof yields for us an explicit enumeration of their union. So one might take the following attitude to this particular application of the axiom of choice: the real theorem is “An explicitly enumerated union of explicitly enumerated sets is explicitly enumerated,” but because we often care only that enumerations should exist and don’t want to keep having to define artificial ones, it is convenient to appeal to the axiom of choice so that we can extend the theorem to the murky world of countable but not explicitly enumerated sets.

Open problems concerning card games

I’m glad to say that editorial work on the Princeton Companion is within a whisker of being completed (about three articles remain to be edited), so although I don’t quite feel that I have the leisure to give proper attention to this blog, which will be obvious from some of the messages that I haven’t got round to deleting, I can at least write a quick post. It starts with a conversation I had a couple of years ago. I was waiting for a plane to take me from Mykonos to Athens. The plane was severely delayed, but the situation could have been a lot worse as I had Persi Diaconis for company. He told me the not very surprising fact that it was not known what the probability of a win is in the game known as Patience in the UK and Solitaire in the US. (I’m talking about the one where you start by putting down a row of seven cards with just the first one face up, then on top of all but this first one a row of six cards with just the first one face up, and so on.) To be clear about the probability he is asking for, he simplifies the game by letting you see what all the cards are, so that you can play optimally and don’t have to worry about probabilities.