I’ve entitled this post “fourth day” in an attempt to encourage myself to write less and get this account finished: with each passing day I find that more has slipped out of my mind (for instance, there are several hours of this day that I no longer remember anything about), and in any case the fourth day of a nine-day conference that ended last week is hardly hot news any more. Having said that, I have tried the trick with several previous posts in this sequence and been forced to change their titles.

Yet again the organizers gave the first slot of the day to a speaker I couldn’t bear to miss — David Aldous, one of the world’s very top probabilists. So yet again I arrived exhausted at the convention centre. Incidentally, here is a photo (from the second day, as it happens) that shows what arriving at the convention centre looked like. If you look closely you’ll see that there is a dramatic gender imbalance: that is because the “ladies” had been told to go to a different queue. At first I was extremely surprised by this, but there was a simple reason for the segregation: the male queue had a male frisker and the female queue had a female frisker. You can also just make out the airport-like metal-detecting cuboid skeletons we had to walk through on entering the building.

David Aldous did not disappoint me — he was definitely worth getting up for. (I think it was on this day that I finally overslept for the first time. That meant that I got up half an hour after my alarm had gone off, and had to get dressed in a hurry, miss breakfast, etc. But it might have been the day before.) There were three things that I wrote down, and one other that I remember. What I remember but did not write down was that he brought up a subject that I have encountered twice before: mathematicians who are not probabilists don’t know how to think about random variables. What did he mean by this? Well, we mathematicians like to define them as measurable functions on probability spaces — that makes us feel comfortable because that sort of reduces the probability to a nice simple piece of pure mathematics. But for some strange reason probabilists don’t want to get rid of the probability.

The first time I became aware that there was a problem here was when I was editing an article by James Norris, a colleague of mine at Cambridge, on probability distributions for the Princeton Companion to Mathematics. I think I did some rewriting that introduced the wrong way of thinking into his article, and had real difficulty in understanding what it was that he objected to. But eventually I sort of got there, and here’s one way of looking at it (related to what he said to me during our conversation, but if anyone objects to anything I say then it’s probably my fault for not doing justice to James’s arguments).

Suppose that is a random variable that is uniformly distributed on What, mathematically speaking, is ? Well, a simple answer would be to say that we can put Lebesgue measure on and that is just the function defined on the probability space that takes to So far so good. Now let be another random variable that is uniformly distributed on What is Well, surely whatever worked for must work for so surely is also the function on that takes to

But hang on, we don’t want to say that any two random variables that are uniformly distributed on are equal do we? Something has gone wrong. So let’s try again. Perhaps we ought to say that and are any two functions that are defined on and have the property that the set of values such that the function belongs to a measurable set always has the same measure as

OK, so let’s take an important case, where and are independent. What are the functions then? It turns out to be possible to define two functions such that for any measurable sets the probability that and is the product of the measures of and But it is not that easy, and it is not what we would ordinarily want to do. It is much easier to take the probability space to be and to define to be and to be

But in that case, if someone says, “Let be a random variable that is uniformly distributed on ,” what are we to think? One possibility is to say that is a function from some probability space that we don’t actually know until we’ve seen the entire problem, and in particular have found out whether it involves other random variables. But a much better approach is just not to be hung up on the sample space and think only about how the random variable itself is distributed.

So what is a random variable, I can hear some people still asking. It might be possible to define it as some sort of equivalence class of functions on probability spaces, but you won’t make any probabilist friends if you go down that road. I think it is better to treat random variables as we treat things like real numbers or functions: we know that there are definitions around such as Dedekind cuts or subsets of Cartesian products, but in practice we do not use these definitions and instead concentrate on various properties that are used over and over again. That is, we use an abstract approach rather than a concrete one. When I lectured a first-year course in probability (and the probabilists in Cambridge were slightly worried that I’d give the unfortunate pure-mathematics perspective) I found that it was indeed almost always possible to talk about random variables without mentioning sample spaces. The one place I found I couldn’t do it was when proving linearity of expectation, which is trivial if you use the functions-on-probability-spaces definition. But if you take that as an axiom then the rest follows.

I mentioned in an earlier post that Aldous had some good lines. One of them, which I like very much despite still not completely understanding it, was, “There’s a difference between a recipe for a cake and a cake.” He explained that probability measures were analogous to recipes and random variables to actual cakes. I sort of see what he means — a function on a probability space is a way of realizing a given random variable — but … actually, perhaps I do finally understand it. Going back to my and example, perhaps you could say that the function on that takes to is a recipe for producing and but it cannot be or because they are distinct things that happen to be given by the same recipe. So you have to take your function and sort of detach it from itself until it becomes an autonomous object. (Perhaps another analogy would be that there is a difference between a musical score and a performance of the piece.) I wonder what two independent cakes would be like — I have a strange vision of their intersecting but not completely.

Aldous told us, or in some cases reminded us, that any random variable (probably subject to certain conditions that I have forgotten) can be realized as a function defined on This produced the second of his nice quotations: “It’s a non-obvious theorem that has to be true or life wouldn’t make sense whatsoever.” Why not? Because it would tell us that there were some random variables that could not be simulated.

The one other thing I remember particularly from the talk was that he mentioned some work of Tim Austin, who was one of Cambridge’s recent undergraduate superstars and has recently finished as a PhD student of Terence Tao. He told us that this was a name we should remember, and predicted that it would feature increasingly at future ICMs. From what I know of Tim, I wouldn’t want to bet against that.

After Aldous’s lecture I made another of my looking-after-myself decisions to skip a talk, and the third slot of the morning was free because Ngo Bao Chau had been due to give a plenary lecture then but would now be giving a lecture in the 1.45-2.45 slot as a new Fields medallist. So quite what I did between 10.00 and 12.30 I am not sure, though I am pretty sure it involved a reasonable amount of blogging.

At 12.30 I was invited to lunch in the restaurant of the conference hotel by some of the organizers of the Klein project, which aims to present research mathematics to schoolteachers in the spirit of the book, Elementary Mathematics from an Advanced Standpoint, by Felix Klein. I arrived at 12.35 and therefore (this being a lunch of mathematicians) last. I was asked what I wanted, the options being the full lunch buffet or a soup and salad option. Hint: everybody else had gone for soup and salad. I took my courage into both hands and went for the full lunch buffet (which turned out to be a good decision because going to the play in the evening left no opportunity for eating anything).

One of the things the Klein project wants to do is produce a book that covers mathematics area by area, with each chapter written by a team of authors. I was asked if I had any ideas about who could contribute. It’s a difficult one because although as a result of the Princeton Companion to Mathematics I now know a lot of people who can write general articles about mathematics, it may be that those very people are now less willing to write such articles, having already done so (not that the Klein project brief is the same as the Princeton Companion brief). But it occurs to me that publicizing the project here may achieve something. If you have any suggestions, then Bill Barton (b.barton@auckland.ac.nz) would be delighted to hear from you. (He is looking for teams of people to write, in a way that would be interesting and comprehensible to schoolteachers, on such subjects as geometry, algebra, analysis, combinatorics, probability, etc.) If you follow the link above, you will find that there is also a wiki that they hope will develop into a useful resource.

When I got back to the main hall for Ngo’s lecture, I had to use the dare-to-sit-in-the-middle-of-the-fourth-row strategy again. That brought me near to an Indian woman who had introduced herself to me at some earlier point in the Congress — I no longer remember when. She handed me an envelope. I opened it and inside was a voucher that entitled me to a free set of proceedings (which at this ICM, unlike at the other ICMs I have been to, one had to pay extra for). That was very good of someone, I thought to myself, while not being quite sure who to be grateful to.

I had asked Jim Arthur three days earlier whether Ngo gave good talks. Yes, he assured me, though he followed it up by saying that they were very clear and well-organized. That got me slightly worried, so I asked whether they were understandable if you didn’t know what an automorphic form was. “That might be a problem,” he confessed.

In the event, I didn’t get much out of Ngo’s talk that I had not already got out of Arthur’s laudatio, apart from this photo, which I think captures quite well the experience of being alone while surrounded by people.

The fact that I didn’t learn much from the talk was at least as much my fault as Ngo’s — I made a conscious decision not to concentrate very hard, because by this time I was feeling so unpleasantly tired that I thought I would get a lot more out of sleeping a little than I would out of the talk itself. But my plans were thwarted by my intolerance of certain sorts of noises, and a habit that my next-door neighbour had of building up pressure behind a part of the body I don’t know the name for, but it’s a sort of door thing about an inch up your nose that you can use to block the air flow, and suddenly releasing it. I found these little exhalations with their preliminary kicks maddening enough to have to abandon all thoughts of sleeping. They didn’t help me concentrate on Ngo either. As usual, the Gowers glare had no effect at all.

After the talk, I hastened to the stall in the exhibition area where I could pick up my ICM proceedings. But while I was still in the main hall, someone stopped me and asked if they could be photographed with me. When I got to the stall, I couldn’t find the envelope any more. They weren’t prepared to give me the proceedings without the voucher, so I was forced to think how it could possibly have disappeared. I realized it must have been when I transferred my belongings from one hand to the other to look better in the photograph. I was in a hurry because there were only 15 minutes between the end of Ngo’s talk and the beginning of Assaf Naor’s, so I ran back to the main hall, and found that the envelope was exactly where my theory predicted it should be. I then ran back to the exhibition area, filled out a form, and was handed a canvas bag with volumes 2-4 of the proceedings in it.

The good news: I was now the owner of volumes 2-4 of the proceedings of ICM2010. The bad news: the bag weighed a ton. It wasn’t just that the weight of my luggage would now go up by a significant fraction (which wasn’t really a problem as Emirates has a generous baggage allowance). I also had to lug this bag around for the rest of the day, which would include going to the play later on.

Talking of additions to luggage, I meant to say that after each talk the speaker would be presented with two gifts. That included panellists, so I got to find out what these two gifts were. The first will be very easy to guess by any mathematician who has reached a certain level of experience. There is a bizarre tradition amongst mathematicians for distributing large ugly mugs of the kind that are designed for large milky cups of coffee. The trouble is, I like my coffee short, strong and black, and I have plenty of quite carefully chosen mugs and cups for that purpose. So over the years I have built up a collection of huge mathematical mugs that I never use. My wife, whose aesthetic sensibilities are more keenly felt than mine, can hardly bear even to look at them: when I proudly showed her my new mug that said, “Prof. Timothy Gowers, Panelist,” on it, she instructed me to find a place other than our house for it to live. Come to think of it, you can enjoy it for yourself: let me take a photo of it and post the photo.

When I got to Assaf’s talk, I stupidly went up and told him that there was a chance that my eyes would close from time to time, and that this would not be a reflection on his talk but just on my state of tiredness. “Why are you tired?” he asked. “Because I switched my light off late for no good reason” didn’t feel like an answer he would understand, so I ducked out of the question somehow and went to sit down. (Just to prove that I mean what I was saying, I even found it hard to keep my eyes open during part of Spielman’s talk, and that definitely had nothing to do with the talk itself.)

In the end, although there were one or two moments during Assaf’s talk where my eyelids felt a bit heavy, it was mostly fine. Assaf is another superb speaker: he often starts with problems that are easy to understand, and then takes you on a journey, several times transforming the problems into other equivalent ones until one leaves the original problem a long way behind and is bringing in tools from areas that one would not have expected to be relevant. For example, deep results in the geometry of Banach spaces turn out to be closely connected with approximation algorithms. To get a quick impression of what I am talking about, I would recommend glancing through his paper in the proceedings.

In the next slot, I should have gone to hear Manfred Einsiedler (of Einsiedler, Katok and Lindenstrauss fame) but opted instead for a blog break. That meant that my next, and for this year final, ICM talk was Benny Sudakov, speaking about Ramsey and Turán type problems. Like Irit Dinur’s talk, this one contained quite a lot that I knew (things like statements of the Erdős-Stone theorem) but that a typical ICM delegate could not be expected to know and that were therefore essential to include. But to my slight surprise there were also a number of very interesting results mentioned that I had not yet heard about, including some that were co-authored by Jacob Fox and David Conlon — the latter being a collaborator and former research student of mine.

One of these I found particularly memorable — I took no notes and can still remember it. (I hope I’ll still say that when I’ve tried to explain it.) An old problem in Ramsey theory is to understand the rough form of the functions : that is the number of points you need in a set such that if you colour all the subsets of of size with two colours, then you can find a subset of size such that all its subsets of size have the same colour. (In the language of hypergraphs, you colour the edges of a -uniform hypergraph and you want a monochromatic complete subhypergraph with vertices.) When one has the usual finite Ramsey theorem for graphs, and although getting good asymptotics for is a major open problem in combinatorics, at least the general type of function is known: the growth is exponential in

When the general type of the function is no longer known. What is known is that it is at least exponential in and is at most doubly exponential in It is also known that beyond 3, each time you add 1 to the lower bound goes up by an exponential. What this basically means is that the bound for is either a -fold exponential or a -fold exponential. So sorting out the problem for will sort it out for general

It might seem rather strange that the function should go up by one exponential each time, but only from onwards. I don’t myself know why the proof works only from onwards, so I can’t give any insight into that. But I wanted to mention a few interesting facts connected with the problem when First of all, Erdős and Hajnal showed that if you allow four colours, then you do obtain a doubly exponential lower bound. Again, I do not know, so cannot give you, any hint about why having more colours helps so much. (It obviously helps, but why it should help enough to change the form of the function is what I don’t know.) They (or at least I think it was they) also introduced a variant of the problem where you try to find a set of vertices such that almost all its subsets of size have the same colour.

It is on this problem, amongst others, that Conlon, Fox and Sudakov have a very interesting result. They showed that for every the size of the set you need in order to guarantee the existence of a set of vertices such that at least of its subsets of size 3 have the same colour is exponential rather than doubly exponential. Since in the case of graphs (that is, the case ) there is very little difference to the bounds when you try to make almost all the edges the same colour rather than all of them the same colour, this looks like impressive evidence that the smaller of the two bounds is the right one.

But not so fast, Benny explained: their proof worked just as well with four colours as it did with two, and that, in view of the lower bound of Erdős and Hajnal for four colours, shows that the problem is genuinely different from the everything problem. I very much enjoy the feeling that you can get from certain talks, of which this was one, where you think you know where the speaker is going, but as you lean back smugly in your seat the mathematics jumps up and bites you.

Benny pitched his talk at exactly the right level. I got plenty out of it, but I’m pretty sure that people who knew less about combinatorics would have as well. (Another good aspect of the talk was that it was in a proper-sized room — the size Lurie’s would have been if Richard Thomas had got his way.) Quite a lot of what he mentioned, but by no means all, can be found in this paper.

After another hour of hanging about, it was time to catch a bus to A Disappearing Number. I said a rather sheepish hello to Roger Heath-Brown, who had also been persuaded by the speeches at the previous evening’s reception that he wanted to go. (I said that I had been intending to anyway, which is true, but the reception turned that into an even more definite decision.)

I enjoyed the bus journey because it was in a different direction from all the bus journeys I had gone on previously, though after a while we found ourselves at a junction that I remembered from my very first journey — the one from the airport to the convention centre. It was there that the taxi I had been in had turned left, done a U-turn, and turned left again. Now, approaching from the other direction, we turned left, did a U-turn, and went straight on. This was because there was some half-built flyover that made it impossible to turn directly right. (Another explanation might have been that turning right would be difficult when it meant crossing the lanes that were going from right to left. But that did not in general seem to be a problem: at a certain point a bus would just cross the lanes and the cars had to stop for it.)

Soon we were at the Global Peace Auditorium, and I went in to see if I could get hold of the ticket that Simon McBurney had said would be waiting for me. As an insurance, I had bought a ticket that morning, since it was only 100 rupees (about £1.50), but I then saw that there were many different ticket prices, so if I had to use my 100-rupee ticket I would probably be in an awful seat.

There wasn’t an obvious box office, but there were several tables with people behind them. I was by no means the only person vying for the attention of those people, but in due course I managed to get it. At first they appeared to have no knowledge of any ticket being left for me, but after a bit they gave me one and I went into the auditorium to sit down. I was in the third row but right round to the side.

Next to me was a man who said he was a journalist and asked whether I was a mathematician. When I said I was he said he would like to interview me briefly after the play about whether I had liked it. I said I’d be prepared to do that. We chatted for a bit and then fell silent.

Then, to my not quite total surprise, a woman arrived and asked me what seat number I had. I told her C41, and she told me that she was also in C41. I showed her my ticket, but also admitted to her that “C41″ had been written on it within the last few minutes, so she was probably more entitled to sit there than I was. She said, “It’s OK,” and went off to sort things out. Not long after that she was back with one of the people from the theatre who asked me to follow him. I felt slightly as though I had done something naughty, but in the end all I had to do was walk up the rows of the by now pretty full auditorium, go back into the foyer, get my “real” ticket, give back the wrong one, and go back and sit in a place (E40 or something) that was very close to where I had been before but actually slightly better because the angle was less extreme.

I’m not sure how much it is worth doing this, but here are two photos, one of the exterior of the theatre (if you look very carefully with your screen at maximum brightness, you may be able to make out two sculpted elephants guarding the entrance) and one of the auditorium, looking towards the stage, which is set for the first scene, which takes place at the front of a lecture theatre.

And what about the play itself? A more basic question might be how one can base a play around the Hardy-Ramanujan story when so much of the fascination of that story depends on the actual mathematics. Perhaps it will give you some idea if I say that the play began with Saskia Reeves talking about infinite series. She started with some simple ones, like but soon moved to the assertion that which she proceeded to justify by means of the functional equation for the Riemann zeta function (which allowed her to think of the series as and calculate it by relating it to ). The amusing thing about the justification was that it was correct, and that, presumably, Saskia Reeves didn’t understand what she was saying — although she was of course a good enough actress to sound completely convincing. During some of this introduction she spoke only quietly and one of the other actors addressed the audience about the nature of mathematics.

The rest of the play was a mixture of talking about mathematics, showing some famous episodes from the Ramanujan story (the discovery of the approximation to the partition function, the 1729 episode, the election of Ramanujan as a fellow of Trinity against the wishes of several fellows, his death at the age of 32) but not in a straight chronological sequence, and interspersed with a present-day story about Saskia Reeves’s character and a young businessman who falls in love with her. The whole thing works very well — especially the interaction between the two main stories — and you should see it if you get the chance. If I had to make a small negative comment, it would be that the characters tell us too often that mathematics is beautiful, which came across to me as a bit preachy (especially as one knew that the actors saying it had almost certainly not experienced that beauty for themselves to any great extent). But I’m not sure whether I’d feel the same way if I were a non-mathematician: perhaps then I would have had a little thrill each time the delicious paradox that mathematics can be beautiful was mentioned. And, just as a plenary lecture should be aimed at non-experts, so this play is principally aimed at non-mathematicians.

One other small negative aspect of the experience had nothing to do with the play, but with my second dose of maddening neighbour noise for the day. This time it was two young men who talked during the performance. They weren’t even whispering, and sometimes I missed lines of the play — though whether that was mainly due to the noise or mainly due to my being distracted by my annoyance at the noise is hard to say. I gave them several glares, once again with no result, and lacked the courage to ask them to shut up.

Afterwards, I loitered about a bit in case I met any of the cast and crew (which Simon McBurney had ordered me to do) but I didn’t, and I gave up fairly quickly because I was anxious not to miss the bus to my hotel. If I had, I would certainly have managed to get there somehow, but equally certainly I would have got there a lot later, and given that I had to pack, and also to get up early to catch a flight the next day, that was something I did not want to do. (An additional factor in my calculations was that the following day I was expecting to reach Cambridge by about 10pm and would have to get up in time for a taxi at 5am the following morning.)

When I got back to the hotel, I started to think that I couldn’t leave Hyderabad without experiencing very slightly more the city itself. Basically, all I had seen of it was from inside a bus, which was certainly interesting but it didn’t count as seeing it properly. Neither did what I did next, but it helped slightly: I went for a short walk. As I may have mentioned, my hotel had a quaint view over a flyover, so as soon as I could, I walked in the opposite direction from that. After I had walked for a while, I decided to turn back, but to walk back on the other side of the road, which was quite a main one. I chose some traffic lights to cross at, but they didn’t help much because first they took ages to go red, and then when they did go red there was no discernible difference in the behaviour of the constant stream of traffic. But I cast my mind back to Furstenberg’s words of wisdom: what can happen will happen. If I waited long enough, there would be a gap in the cars that was long enough for me to get across. (It’s possible that there was some convention I didn’t know, such as that if you walk across a busy road then the cars will not run you over. But I didn’t want to experiment.) I suppose, strictly speaking, I needed a quantitative form of this principle, but in any case eventually my gap appeared and I got across. I did not make any blogworthy observations about India during this walk, but I was glad to have done it.

It remained to pack. Although my suitcase had been underfull when I came out, packing turned out to be a serious challenge. And the main reason for that was the three volumes of ICM2010 proceedings, which I still had with me despite numerous opportunities to leave it in the bus, or the theatre, or the convention centre. I also kept thinking I had finished, and managed the problem rather ingeniously, when I would see something else that I had forgotten to pack. A phase transition occurred when I spotted the mug and the other gift I had been given after the panel discussio, which I had not yet opened. I decided to open it then and there, even if it meant leaving the ICM2010 wrapping paper behind, and found a quite nice small chess set — one of those boxes that contains the pieces, which were wooden, and unfolds into a board. These occupied enough space to force a rethink — in the end I squeezed my hand-luggage bag into the slightly larger conference bag so that they would count as one item, with the plan that I would separate them again once I was through airport security. (I don’t suppose they would have been all that bothered if I’d taken them as two bags as, combined, they were much smaller than the hand luggage allowance.)

I could go on — as I write I realize that I haven’t mentioned ordering a taxi when I arrived at the hotel, and a telephone call to say that because of likely traffic on a Monday morning I should leave half an hour earlier than planned. In the end I left at 7.10am instead of the planned 7.30 because the promised taxi wasn’t there. And we got onto a raised road that went for miles and miles with barely another car to be seen and I arrived at the airport in time to write almost an entire blog post before getting on to the plane.

I also feel as though some kind of summary is called for, but this post has reached over 5,500 words, the series of posts is now longer than Mathematics, A Very Short Introduction (yes, I actually checked), and in any case the congress was only at the half-way stage. I may at some point write a sort of summing-up post, but for now I must get back to some real work. If anyone wants to tell me how the rest of the congress went — perhaps even contribute a guest post — then I’d be very interested to know, since I’ve heard nothing about it at all. But the next post here will be EDP18.

At some point earlier in the day — I forget exactly when — Oliver Riordan asked me whether I was going to a reception hosted by the British Council and EPSRC (the Engineering and Physical Sciences Research Council — an administrative body that decides how quite a bit of Britain’s science budget is spent). I had had an email invitation in the morning and not got round to replying to it, but Oliver said he was going over to an EPSRC stall in the large room where various publishers and other organizations had stalls, and would be happy to tell them I was coming, which they needed to know because it involved taking us to a hotel in the centre of town by bus. I thought, “Well, if Oliver’s going then I may as well go,” which turned out to be a good decision.

Also happening that evening was a performance of A Disappearing Number, a play by Théatre de Complicité, a British theatre company directed by, and co-founded by, Simon McBurney. If that name means nothing to you, you may still remember a seedy British diplomat in the film The Last King of Scotland. He was, or rather played, that diplomat. The play is partly about the Hardy-Ramanujan story, and has had several runs in Britain over the last two or three years, to great acclaim. Despite knowing Simon (about which more later) I had not got round to seeing it, but neither had I got round to getting a ticket for today’s performance while they were still available — which was OK because the play was on in Hyderabad both today and tomorrow.

I hadn’t quite made the connection, but the main point of the reception that I had decided to go to was to celebrate the fact that it had been possible to get Théatre de Complicité over to India to perform the play. This relied on a generous grant from the British Council. I had assumed that, like the Indian dance performance, it was on in the Convention Centre somewhere, but actually it was shown in a proper theatre.

Because of that, the reception was due to start on the late side, and the buses were not due till 8.15. I decided to use the time between the end of Lurie’s talk and the bus writing more of these blog posts, but that didn’t work out because they booted us out of the “Internet Café” at 7.00. That left me an hour to kill, so I found a quiet chair and tried to make progress on the Erdős discrepancy problem. (I haven’t mentioned this very much, but I thought about that problem quite a bit during the Congress, and made what felt like very considerable progress, though now with a bit of hindsight I think it was only modest progress. As soon as I’ve finished these ICM posts I’ll have a long post on that.)

That reminds me of how I spent the time between the talks of Marianna Csornyei and Jacob Lurie. At Spielman’s talk I was given a draft of the interview that I had given about Polymath the previous day after the panel discussion, in case I had any comments or corrections. As it was, I felt the need to do more: they had had a tape recorder on, and their algorithm for writing up the interview seemed to be to extract one sentence in ten from what I said. The result was a long sequence of weird non sequiturs. I offered to rewrite the whole thing, and they accepted. It was good to have a time limit, because it meant I just answered, or rather reanswered, each question with the first thing that came into my head rather than spending ages thinking up little aphorisms and polishing them. I learnt later from Professor Raghunathan, who was at the British Council reception, that the interview was going to fill up the whole of the first page of the ICM Daily News, a four-page publication handed out free each day to delegates, so the effort that I did make was definitely worth it.

During the hour I was sitting about trying to make progress on the Erdős discrepancy problem, I saw that it was raining very heavily. Quite a lot of people were leaving in various buses and I think several of them must have got soaked in the process. I felt a bit silly for having neither of my two umbrellas (the one I brought with me and the one I was given in my kit bag) with me. But I was lucky and the rain stopped by the time I needed to go outdoors. I spent about ten minutes near 8.15 feeling worried that nobody else seemed to be hanging about waiting to go to the reception (in particular, there was no sign of Oliver), but that was just pointless neurosis because they did in the end turn up. It was then that I had my chat with Richard Thomas about Jacob Lurie.

The reception itself started out rather similarly to several receptions/dinners I had already been to. The obligatory bits of chicken started coming round, and I ate a few of them before thinking, in view of the long row of chafing dishes I could see in the middle distance, that I should try to pace myself. The biggest differences between this reception and the conference dinner the previous day were that it was far less crowded — we were all a bit dwarfed by the tent we were in — and that we were offered whisky. I had noticed the whisky earlier when I went to the bar to get a glass of wine. I decided to avoid it because it wasn’t serious single malt or anything like that (it was either Bell’s or Teacher’s — I can’t remember which) and I was still anxious about how little I had been sleeping: these days the main effect alcohol has on me is to make me miserably tired, especially if I am already tired.

After a while, we discovered that we were waiting for the cast and crew and some of the audience of the play, and that they weren’t expected for some time. The first sign that they had arrived, apart from a general filling up of the tent with people, was that … it couldn’t be … was that Saskia Reeves? I don’t know how well known she is outside Britain, but to someone British of my age, which is similar to her age, she counts as a household name. (I’m a little surprised by how short the Wikipedia article about her is.) And then I saw Simon McBurney.

How do I come to know him? There are two reasons. One is that he has a nephew who sang in a choir in which a son of mine also sang. That might not sound like enough of a connection, but it turned out to be, partly because he is fascinated by mathematics and heard that I was a mathematician. The other is that a rather strange event took place in Cambridge just over a year ago. It was supposed to be about bridging gaps between disciplines, and Simon McBurney, Marcus du Sautoy and I were given the task of talking to each other for an hour in a way that would interest an audience of humanities people. (Is there a proper word for that? “Humanists” isn’t quite right.)

We were told about it a long time in advance, and then a game of chicken ensued: who would be the first of the three of us to email the other two in a panic and ask what on earth we were going to do? I lost, and then lost again a few weeks later. But it turned out that I was at a disadvantage. Marcus had been advising Simon about the mathematical content of A Disappearing Number, and the two of them had a pretty good conception of what they wanted to do in Cambridge, which was to take some parts out of the play and perform them.

The day before the performance, after we had consulted each other much more about what we would do, Marcus went down with swine flu, so it was down to two of us. But Simon brought a few of his Complicité friends along, and basically ran the show: I did a few mathematical turns from time to time while he held everything together.

When I saw that he had arrived at the reception, I went up to say hello, and was reminded of the difference between thespians and mathematicians by his manner of greeting: a hug of a kind that I would probably reserve for a long-lost relative who had just saved my life. But it made me feel good rather than horribly embarrassed. (Having said that, let me make it clear that if a mathematician greeted me like that, then I would feel horribly embarrassed.)

A little later there were some speeches about how wonderful it was that A Disappearing Number was finally being shown in India, and we mathematicians were encouraged to mingle with the actors, who would, we were assured, be delighted to meet us after having spent a long time working on a play that centred on mathematics. I thought, “I’ll never forgive myself if, having been given permission — even encouragement — to say hello to Saskia Reeves, I fail to do so.” However, I remained rooted to the spot. But then I had a piece of good fortune. On our way to the reception I had been sitting next to Sedhar Chozam, wife of John Ball, and had learnt that she had been an actress in the past and was just reviving her career. She decided that she wanted to go and talk to the group of actors of whom Saskia Reeves was one, so I tagged along behind.

My opening gambit was in retrospect a bit crass and didn’t seem to be well received. I told Saskia Reeves that although I hadn’t yet seen the play, I had enjoyed her performance in a recent detective series called Luther, which stars the wonderful Idris Elba, who played Stringer Bell in The Wire. (When I watched Luther, my wife and I had recently got to the end of the final series of The Wire and were in mourning.) She replied, “Oh.”

My stock rose a little when Shane Shambhu, one of the actors I had got to know in Cambridge (I remembered him chiefly for a display of Indian rhythms he did with Simon McBurney — the two of them repeated things like “Taka takata” but longer and with different periods that came together only after several cycles, and ended up exactly together with a big “TA!”) arrived and I was able to prove that I wasn’t a completely random jerk but someone who had some connection with the play. And then Simon arrived and said things that I am embarrassed to repeat (unfortunately, even saying that is embarrassing), after which I felt comfortable again. But soon I decided that I should quit while I was ahead, and did. Simon told me that he would murder me if I didn’t go to the play the next day (at which he would unfortunately not be present), which was OK as I was intending to anyway. He also said he’d make sure a good ticket was waiting for me.

Soon after that came the usual hanging about for transport back to the hotel, but this time there were about twenty of us rather than three thousand and I ended up in a taxi rather than a bus.

One small thing I haven’t really mentioned is that pretty well everywhere there was quite a bit of security. To get into the hotel where this reception took place, we had to have our bags put through X-ray machines and be frisked. The same was true of the convention centre. I don’t know whether it’s been like that for a long time or whether the attacks in Mumbai have caused it to be hugely stepped up.

I can no longer remember to what extent I failed to be idiotic on this night. I’m fairly sure that I got back early enough to have something like eight hours of sleep, but that I ended up (after a bit of post writing and mindless TV watching) having more like six.

I’ll begin this with a question: why is it that theoretical computer scientists are, on average, far better than other mathematicians at giving general-audience talks? Irit Dinur’s plenary lecture at the ICM was, as I have already said, excellent, but that kind of excellence seems to be the norm for theoretical computer scientists: I basically know, when I go to the TCS plenary lecture at an ICM, that I’m in for a treat. (But that is not the whole story at all. For example, I also know that if I’m at an additive combinatorics conference at which Ryan O’Donnell is speaking, then again I am guaranteed an extremely interesting, entertaining and comprehensible talk.)

Even by the exalted standards of theoretical computer scientists, Spielman’s talk was masterful. (If you’ve been reading all these posts, you may remember that I predicted this after hearing him answer a question at the post-opening-ceremony press conference. Well, my prediction was not just correct but hypercorrect.) He started by thanking all sorts of people who had inspired him to become a theoretical computer scientist, and even this he made interesting and amusing — for instance, he showed us a picture of one person, a high-school teacher or something, and ended a brief discussion of that person by saying, “And he was the one who made me want to become a mathematician.” And then after the next person he said, “And he was the one who made me want to become a computer scientist.” And at the end of the talk he somehow (in a way that I’ve now forgotten) brought the whole thing full circle and reminded us of these initial remarks about his early intellectual life.

During the talk, he marched about the stage, always talking to us, the audience, and never to his slides — it was as though he knew from memory what was in them, though there was something on the stage (other than the lectern) that may have been a display for the benefit of the speakers. I never quite got round to checking.

In between the initial remarks and the clever return to them, he told us about one of his main interests: quick ways of solving systems of linear equations. He began by telling us what the holy grail was: to find an algorithm that can solve the equation where is an matrix and and are appropriate vectors, in a time that is linear in the number of non-zero entries of Such an algorithm would be of major theoretical and practical interest, and it seems from what Spielman was saying that it might even exist.

But if we don’t see how to devise it, what else can be done? One natural line of enquiry is to look at important classes of systems of linear equations and try to find fast algorithms for those. For instance, if you are trying to solve a PDE by discretizing it, you end up with a large number of equations, but they have some special properties: each equation involves only a few variables, and those few variables will typically correspond to points in some nice space that are very close to each other. For example, one big and interesting class of equations is Laplace’s equation on the graph of a triangulation of a surface. (That is, one wants the combinatorial Laplacian at each point in the graph to be zero.)

One thing that is always nice to get out of a mathematics talk is a bit of philosophy, or an insight into other people’s philosophies. Spielman at one point said something like, “I find I don’t understand a graph unless it is a …” and although I remember liking this statement very much, I can’t now remember it. The basic idea was that the graph should have been produced in some concrete way, but what he said was more specific than that.

I find that I have written almost nothing about the talk — I was just sitting back and enjoying it. So I’ll end by saying that one of Spielman’s main themes was that in order to solve these special cases of the problem about solving systems of linear equations, it had been necessary to draw on a large amount of existing work that had been done in connection with quite different questions. He demonstrated this convincingly, thereby justifying Gil Kalai’s remark that Spielman’s work was a wonderful marriage of theory and applicability.

That was the regular 1.45-2.45 slot. I then had to decide which talks to go to in the parallel sessions. I decided on two prodigies: Marianna Csörnyei and Jacob Lurie. Marianna I have known quite well for many years, and she works in areas that I can be expected to understand reasonably well (which is not quite the same as saying that I do understand them reasonably well, but in fact I do usually follow quite a bit of her talks). Jacob Lurie is the opposite: I had never met him, or even seen him, and had absolutely no chance of understanding anything he would say, so I was going for the sole purpose of gawping.

Why do I describe them both as prodigies? Well, in Marianna’s case there are some extraordinary anecdotes about how David Preiss, then at University College London and now at Warwick, brought her over to England at some extremely young age such as 18 (I can’t remember exactly) and set her unsolved problems with deadlines of, say, 48 hours. In case you want me to confirm what I’ve just written, I do indeed mean that he would say things like, “This is an interesting unsolved problem: you have until the day after tomorrow to tell me the answer.” And the even more extraordinary thing was that Marianna would indeed come back two days later with the answer. And I’m not talking about something that happened just once: it was a regular occurrence. The problems were things like finding sets of real numbers with extraordinary properties, and to solve them Marianna would produce incredibly delicate inductive constructions of sequences of sets that would tend to a limit with the desired properties. I think there are similar stories about Jacob Lurie — I heard about professional mathematicians consulting him when he was about 16 and getting the answers they sought the next day. And the amazing thing was that it wasn’t amazing — they consulted him because they knew he would be able to do it.

While I’m on this subject, let me counteract it with another story, that of James McKernan. He was an undergraduate at Trinity College, Cambridge in the same year that I was. I did not know him all that well (there were 40 of us), but I remember him as someone who was … I don’t know quite the right way of putting it because the truth is that I don’t remember all that well how good he was at mathematics at this stage. But the fact that I don’t remember puts upper and lower bounds on his performance: he wasn’t one of the best in the year and he wasn’t one of the worst in the year. I think the result of that was that he did not get a PhD place in Cambridge, but it’s possible that he just didn’t want to do a PhD here, and so he disappeared out of my life — I think he did his PhD at Brown — to reappear over twenty years later as the coauthor with Christopher Hacon of some astonishing papers that completed Mori’s minimal model programme. Now I don’t know what that programme is, but I do have some conception of how important it is, and have seen how excited algebraic geometers are about these developments.

Both Hacon and McKernan were invited speakers at the ICM. I was strongly tempted to go to McKernan’s talk, but, agonizingly, it clashed with Assaf Naor’s and I went for the latter. It occurs to me that, given that I tended to bump into the people I knew about two or three times a day, I may have accidentally cut McKernan dead a few times (I stupidly didn’t remind myself what he looked like until well after I had left Hyderabad). James, if I did, and if by any chance you read this, then please know that it was the opposite of what I planned. What I would have liked to do is tell him how pleased I was at how well he has done. I don’t know whether it is right to describe him as a late developer, but the evidence I have suggests that that is a reasonable description. I hope it is, because I very much like stories of late developers: I think it is important to show the world that if you are not a Marianna Csörnyei or a Jacob Lurie, then you still have a chance of proving major theorems.

Marianna’s talk was packed, partly because the room was much too small for an invited lecture at an ICM, so I ended up standing. Given my state of tiredness and the temperature in the room, this was both a good thing (it stopped me going to sleep) and a bad thing (it was pretty tiring). Marianna spoke quietly, but loudly enough to be audible in that room, at least if there wasn’t any background noise. I’ve forgotten what she said about her own work, except that it sounded amazing in the way that it always does, but let me mention a pair of results of David Preiss that she mentioned as part of her introduction. (Added later: if you want to know about more than this, here is her ICM proceedings article.)

A Lipschitz function from to is differentiable almost everywhere. But some very subtle questions arise if you ask about the nature of the exceptional set. Preiss showed that there is a set of measure zero in such that every Lipschitz function is differentiable at at least one point in By contrast, given any set of measure zero in there exists a Lipschitz function that is not differentiable at any point of Marianna (I’m calling her that rather than Csörnyei not out of sexism but because I know her well enough that it would feel weird to say Csörnyei — I’ll do the same for Assaf Naor and Benny Sudakov) explained that a feature of the first result that makes it pretty deep is that the proof does not tell you in any sense that almost all points of are points of differentiability of — it just tells you what it says on the tin, that there exists such a point.

After Marianna’s talk I allowed myself a break (as I had in the morning when I skipped Carlos Kenig’s plenary lecture — today, as on the previous day, I was sufficiently worried about overdoing it that I missed some talks that I would ordinarily have liked to go to) of just over an hour until Jacob Lurie’s talk. I thought that there were likely to be many people besides me who would be there for entirely extra-algebro-topological reasons, so I decided to turn up ten minutes early. The room was already very full, but I tried a tactic that sometimes works — to march to the front, spot one seat right in the middle of the fourth row that nobody has quite been able to face getting to, and to face getting to it. OK you have to climb over six sets of knees, but it seems that people don’t hold permanent grudges against you for this (except perhaps if you arrive late for a film and clamber over someone, blocking their view at a crucial moment, but then you’ll probably never see them again).

As I’ve already made clear, Lurie is a certified genius. I mean “certified” in the sense of “universally acknowledged” but there was just a hint of an alternative interpretation in the way that he moved his head, which seemed somehow more loosely attached to the rest of him than most people’s heads are. We sat waiting for quite a long time, partly because I had arrived early (which I was glad of, because there were plenty of people standing for this talk as well) and partly because Richard Thomas, who was chairing the session, was trying to persuade the conference organizers to remove the partition between the room we were in and the room next door, which was empty. Unfortunately, he failed to persuade them, although in another way it wasn’t unfortunate: I think it does something good for the atmosphere of a talk if the room is packed.

What can I say about the talk itself? Well, early on he put up a slide that had the following names on it: Deligne, Drinfeld, Feigin, Hinich, Kontsevitch, Milgram, Schlessinger, Soibelmann, Stasheff. I haven’t heard of all of those, but I’ve definitely heard of some of them and was duly intimidated. And Deligne-Mumford stacks made an appearance too (you may remember those from Ngo’s work). There were also some things called Artin stacks.

By the end of the talk, Lurie had leapt into first place for interesting or amusing quotations with three. (The next day David Aldous managed two, but he had an hour.) The first one was one of those bits of folk wisdom that I mentioned earlier: having pointed out that it was difficult to define (or discuss, or do something to) something or other using equations, he said, “If you can’t use equations, then what you want to do is use words.” In other words, you wanted to be more conceptual about what you were doing (where “you” means “Jacob Lurie”).

I’ve written, “Lots of mathematical structures — abstract.” What I meant was that to someone like me, who still has the temerity to think about mathematical objects rather than sticking to sets of sets of sets of objects (all very nicely structured of course), the experience was a sort of bombardment. I don’t really understand why I should be happy that we can define a canonical sequence of graded Artin stacks or whatever it might be (whatever it was, it wasn’t that, but it sort of sounded like that). But I wasn’t there to understand — just to drink in the experience while Lurie told us, “And then one can do A, and then B, and then C,” and the algebraic structures he mentioned became more and more sophisticated (or did they? I can’t claim to be sure of this).

I think Lurie is slightly sensitive to the criticism that his work is too abstract (not that I’m making that criticism myself — I’m not really in a position to judge how abstract it is). This sensitivity led to the second of his great quotes, which came about two thirds of the way through, when he said, “I don’t want you to think all this is theory for the sake of it, or rather for the sake of itself. It’s theory for the sake of other theory.” This got a good laugh, as you might imagine. He said that he would demonstrate that by giving us an example, which to my inexperienced eyes seemed to be yet another building of algebraic structures, but I suppose to be fair to him he did say at one point (or at least I wrote), “ is the moduli stack ,” where I think had been an abstract something or other about which something in one of his abstract results had been stated.

There was one bit that intrigued me, where he talked about things called algebras (which I would completely have forgotten about had I not written anything down). If I remember correctly, an algebra is associative, and as the algebras become more and more commutative in some sense. Additive combinatorialists will see why I found this idea appealing, though I think the appeal might vanish on closer investigation (or rather the reasons for it might — I wouldn’t rule out their being replaced by different and better reasons).

The third quotable sentence came after 35 minutes or so. He said, “I expected that I would be going overtime, but I think I haven’t.” And that was the end of the talk, apart from some questions that sounded frighteningly intelligent to me. I found myself wondering about a nightmarish scenario in which my brain suddenly inhabited Lurie’s body. Would I be able to answer the questions in a way that would seem genuine to most of the audience? Each time Lurie answered one, I realized that the answer was definitely no — there were little touches of a kind that I just wouldn’t have thought of, that made it clear that some kind of communication really was going on.

A short time afterwards I found myself chatting with Richard Thomas, who clearly had a very great respect for Lurie. I asked him two questions that I can now remember. The first was, roughly speaking, whether it was true that Lurie is revolutionizing mathematics. The answer is yes, apparently. Richard told me that Lurie has a huge programme and is slowly working through it, writing hundreds and hundreds of pages. (I think I had heard this from other sources too.) The second question was whether all this theory was leading to solutions of open problems that could not be solved without it. The answer to this is also yes, apparently, though it seems that the process of using the theory for applications is in its infancy. In other words, we can expect to hear a great deal more about Lurie over the next few years. He also said that Lurie has made several claims about what he will eventually be able to do, and already has an impressive record of backing those claims up with results. It’s just that there’s a lot more work to do.

I’ll end this post with perhaps my worst photo — unfortunately, the camera decided to focus on the head of the person just in front of me rather than on Lurie. But at least you get some idea of what he looks like.

I dragged myself out of bed on the third day feeling pretty terrible — in fact, terrible enough to be slightly worried that I would be doing myself some damage with this succession of short nights, which I couldn’t see how to do anything about, given the necessity of starting early (a result of the schedulers’ evil decision to put superstars and known excellent speakers on in the first slot of the day). But nothing much distinguishes the beginning of the third day from the beginnings of the two previous days, so let me jump to the first talk, Artur Avila’s plenary lecture.

But before I do so, I have remembered one small thing that did make this day slightly different. In order to put on the unpleasant insect repellent, I took off my name badge, and then I forgot to put it back on again. I realized what I had done just as the bus was pulling out of the hotel. I wondered whether it was worth delaying the bus for three minutes while I dashed to my room and back, but Irit Dinur, who was in the same bus (I had not previously realized she was even at the same hotel, because she took a much more relaxed attitude than I did about getting up for the first talk — the previous day she’d watched the streaming video from the hotel instead), told me that she had forgotten hers yesterday, and the only consequence was that she had had to go and ask for a replacement. Well, that wasn’t quite the only consequence — the replacement badge no longer said, “Invited Speaker” on it, and she did not get a new set of coupons for lunch and coffee.

I decided I could handle walking around as a mere delegate, and could even handle not having a lunch coupon, though that was slightly disappointing. But for some reason when I asked for my replacement badge it was an exact replica of the original one and it did come with the coupons. (So in theory I could have had seconds for lunch the next day — but in fact I ended up not even having firsts.)

Artur Avila is young (we were told that he was this ICM’s youngest plenary speaker) and strikingly handsome in a black polo shirt and dark jeans, as this photo demonstrates rather inadequately.

To his left in the photo is Etienne Ghys, who gave an excellent plenary lecture in Madrid four years ago.

Talking of plenary lectures and their virtues, if you are unfamiliar with this opinion of Doron Zeilberger, and particularly the appendix, and find me disappointingly polite, then it’s a must read.

However, I can in all sincerity say that the two plenary lectures I attended on this morning were excellent. The first thing I wrote about Avila’s was, “Started well.” I can’t remember quite what it was that provoked that, but it was probably something like a very good setting out of his stall — explaining in elementary terms what the talk was going to be about. His voice sounded oddly Russian to my ears (oddly since he’s not Russian at all) and then later reminded me a bit of Mihalis Dafermos, a colleague of mine at Cambridge who is, as his name suggests, Greek but who has spent quite a bit of time in the US. He shared with Mihalis a tendency to end sentences on a high-pitched note.

He spent quite a bit of the talk telling us about iterating polynomials such as the famous explaining why this was interesting, informing us what a Lyapounov exponent was (something I ought to have known but didn’t), and discussing period doubling, the onset of chaos, etc. After a short while I stopped taking notes and as a result I am left without a clear idea of what Avila’s own contribution to this area is. What I remember is that I did have a reasonable idea of it at the time, but now it is a week later and it has slipped out of my mind. The one thing I do remember is that Etienne Ghys told us that Avila is famous as a problem solver, and also as somebody who likes to work in collaboration.

Next was Irit Dinur’s plenary lecture. I asked her earlier in the morning whether she felt nervous about addressing an audience of something like 500 people (I’m not sure why I didn’t say 1000). She said she was, but in a way that was consistent with either feeling nervous or not feeling particularly nervous but just responding in a fairly automatic way to my question. Here is a picture of her and Hendrik Lenstra (who, as it happens, was chairman of the programme committee) just before her talk.

Lenstra started singing her praises, but fairly soon stopped and said that while there were plenty more good things he could tell us about her, he did not want to embarrass her further. She then started her talk with a good show of mild embarrassment, followed by some charming apologies, such as for having a not quite perfect set of slides because her computer had crashed when she had tried to put the finishing touches to them. (Apart from one small mistake that she later pointed out to us, there was no sign of this supposed imperfection.)

Pretty soon she was into her stride, and gave an exemplary ICM plenary lecture: keeping it simple and comprehensible to non-experts, and having time for a few hints about her own work at the end. My only disappointment was a selfish one — I would have preferred less introduction (things like being told what P and NP are and why they are important) and more about her proof of the PCP theorem. But the fact that I felt that way is the opposite of a criticism: it is a sign that she was doing her job. Strange though it may seem to some people, a significant proportion of professional mathematicians do not know what NP is, and if they had not been told then they would not have had a chance of understanding the talk. (At one point Dinur told us that NP does not stand for “non-polynomial time”. I think it is quite common to believe that it does, but one wonders how somebody can think that and also be aware that the question of whether P=NP is a famous open problem.)

I took no notes in this talk, but let me see if I can give an informal statement of the PCP theorem without completely butchering it. First, PCP stands for “probabilistically checkable proof”. What is a probabilistically checkable proof? Well, let me give a very simple example. Suppose I have a bag of marbles and I want to convince you that at least half of them are blue. And suppose that in fact two thirds of them are blue. Then I could invite you to perform the following experiment: you put your hand in the bag, take out a marble, look at it, and put it back again. The chances that you will take out a blue marble are 2/3. Now that doesn’t prove much, but if you do it a hundred times (shaking the bag a lot in between so that the outcomes are independent) then you will almost certainly draw out well over 50 blue marbles, so much so that you can calculate that the probability that I am lying is extremely small.

The main points here are that you can be convinced that I am telling the truth after looking at only a constant number of marbles, where by “convinced” I mean that you can make your probability of being wrong as small as you like.

However, this is not a perfect example, because it applies just to one bag of marbles, and does not work if, say, the number of blue balls is exactly 50%. But if for some strange reason we knew in advance that the number of blue marbles would either be at most half the total number of marbles or at least two thirds of the total number of marbles, then to convince ourselves of which, with an error probability of at most 0.0001, say, it is enough to look at just a constant number of marbles.

Now let’s consider another example that is related but that doesn’t quite work. This time suppose we are interested in whether a certain graph is 3-colourable. A typical “proof” that a graph is 3-colourable consists of … a 3-colouring of that graph. But that is not a probabilistically checkable proof because you need to look at more than a constant amount of a colouring to be convinced that it is a colouring. For instance, suppose I had a graph that was not quite 3-colourable but had a way of colouring the vertices so that just a tiny fraction of edges joined vertices of the same colour. If you now looked at 100 edges, then with high probability each one would join two vertices of different colours in my “fake” 3-colouring. So with this protocol (given a 3-colourable graph, I 3-colour it and you look at a constant-sized random sample of edges and check whether they join vertices of different colours) you cannot be convinced of the reliability of my proof that a graph is 3-coloured (even if my proof itself is perfectly valid). Of course, with a different protocol, one that runs in polynomial time, you can be convinced — you just look at every single edge of my colouring — but that is merely telling us that the problem belongs to NP.

So how might one devise a probabilistically checkable proof that a graph is 3-colourable? What would we even want? Well, suppose I had a way of transforming any graph , in polynomial time, into a new graph with the following properties.

1. If has a proper 3-colouring, then has a proper 3-colouring.
2. If does not have a proper 3-colouring, then for any 3-colouring of , at least 10% of the edges of join vertices of the same colour.

Then we can adopt the following protocol. You give me a graph and I transform it into and hand it back to you, together with a 3-colouring of the vertices of . (If you’re worried about how I found that 3-colouring, don’t. The point is that we’re not claiming that it is easy to find a colouring. We’re just talking about a system for efficiently verifying that a graph is 3-colourable if a 3-colouring is magically provided.) You then look at 1000 edges of at random and see whether they join vertices of the same colour. If they all do, then you should be convinced beyond all reasonable doubt that is 3-colourable. Why? Because if were not 3-colourable, then at least 10% of the edges of would join vertices that had the same colour in my colouring, and with extremely high probability you would choose several of these bad edges in your sample of 1000 random edges.

I’m not going to say much more about what the PCP theorem says. But three points are particularly worth noting. One is the main point of the theorem itself, which is that every problem in NP has a probabilistically checkable proof system like the one just mentioned (which, I stress, depends on the huge unanswered question of how to construct the graph ). For example, if the problem is to input the statement of a mathematical theorem and output a proof (in some suitable formal language) of length at most if such a proof exists, then there is a PCP system for that. In principle, we could all write our proofs in a formal language, then apply some clever transformation to them in such a way that all a journal would need to do to be 99.9999999% certain that the proof was correct is check 1000 bits of the transformed proof. As Dinur said, that is not actually a practical suggestion, but it is certainly an amusing one to fantasize about.

Another is that the PCP theorem turns out to be equivalent to the statement about graphs above. That is, if you have found a clever transformation of graphs that sends 3-colourable graphs to 3-colourable graphs, but sends non-3-colourable graphs to graphs that don’t just fail to be 3-colourable but fail badly to be 3-colourable, then you have in fact proved the entire theorem: all other examples can be reduced to this one.

If you think that makes the problem sound easy, then I recommend spending a couple of hours trying to think of a method of transforming graphs that has these two properties.

The third point is the question of why computer scientists are so interested in the theorem. It is regarded as not just a pretty theorem with amusing consequences, but as one of everybody’s top half dozen results in theoretical computer science. (Or at least, that’s how it seems to me that it is treated.) The main reason for this is that it can be shown also to be equivalent to hardness of approximation results.

To see what this means, consider the following attractive idea. We know that finding a 3-colouring of a graph is, if PNP, extremely hard. And the same goes for many other problems, such as finding a Hamilton cycle. But in practice we would like to be able to do some of these things. Perhaps a good compromise would be to accept slightly imperfect approximations: for instance, we might be satisfied with a colouring such that 99.9% of edges joined vertices of different colours.

But note that the PCP theorem in its graph formulation tells us that that cannot be done. If we had a way of efficiently finding a colouring that worked for 99.9% of edges, then we could apply it to our transformed graph If we succeeded in finding such a colouring, it would tell us that the original graph had a proper 3-colouring, since if not then the best colouring of would yield only 90% of edges that joined vertices of different colours. The moral of all this is that the PCP theorem tells us that even approximating is hard. There are by now some amazing results that say that even finding approximations that are very slightly better than trivial ones is hard. For instance, suppose you have a bunch of linear equations in variables over and want to know how many of them can be simultaneously satisfied. If you choose the randomly, then on average half the equations will be satisfied. Hastad proved that even if it is possible to satisfy 99% simultaneously, actually finding variables such that 51% of them are satisfied simultaneously cannot be done in polynomial time if PNP.

Having made those points, I’ve thought of a couple more things I’d like to say. The first is to stress the importance that constructing from should be done with a polynomial-time algorithm: it is trivial to find some transformation that works (e.g. make a large complete graph if cannot be properly 3-coloured and a large empty graph if it can).

I also want to say a tiny bit about the proof. You may find that the statement reminds you slightly of coding theory. A good code is one that transforms bit sequences to bit sequences in such a way that any two distinct sequences become very distinct. That’s a bit like a graph that is not 3-colourable becoming very non-3-colourable. So it will not come as a big surprise to hear that the original proof of the PCP theorem (due to Arora and Safra, and Arora, Lund, Motwani, Sudan and Szegedy, building on previous work by several further authors — you’ll have to look it up if you want to know who did what) did indeed involve coding theory in an essential way. (I’m saying this based on some vague memory of hearing the proof described, and have not managed to find definitive confirmation of it online.)

Dinur’s proof is different. As she pointed out to us, it is sufficient to find a way of transforming a graph with vertices into a new graph with at most vertices in such a way that if can be properly 3-coloured then so can , while if cannot be properly 3-coloured, then any defect in the colouring of , which initially affects just one edge … hmm … I now realize that what I felt as though I was understanding during the talk has not lasted well enough in my brain for me to be able to reproduce it. Here is what it felt like: you have a graph that cannot be 3-coloured without at least one error somewhere. For some reason, the graph is an expander (meaning that any set of at most half the vertices has at least neighbours not in ) and when you build the next graph the error propagates to the immediate neighbourhood of where the errors were last time. To achieve this, the new graph has edges where the previous graph had short paths, but they are chosen in a clever way. So after logarithmically many transformations the error has spread all over the graph and you’ve got your desired outcome. But actually the steps are divided into two, which Dinur described as being a bit like inhaling and exhaling. The “exhaling” deals with some features that you don’t want that result from the “inhaling” part. Sorry that’s all a bit vague, but I have at least found a much less vague account for anyone who might be interested. (Of course, you can also look at Dinur’s paper, which, to judge from a quick look, seems to be very well written.)

[Update: this post is now complete.]

On my way to the ICM I bought my first ever digital camera. From the quality of the photo below, you may not be surprised to hear that it is my first, though actually I have taken some good photos with my wife’s — I just couldn’t seem to get mine to take decent photos in the windowless main hall of the convention centre, which was not very light but had screens that were lit in a way that made the rest of one’s photos come out dark. Also, I took this photo from a distance that meant that even with the zoom on full I had to crop it quite a bit to get what you see below. But that’s enough excuses — I also want to celebrate the first ever illustrated post on this blog. The picture shows Smirnov and Kesten just before the first of five talks given by a new Fields medallist or Nevanlinna prizewinner: Smirnov to give the talk and Kesten to introduce it.

My small experience of Smirnov’s talks has been very positive, and this was another good talk. But by this stage of the congress I was no longer trying nearly so hard to take enough notes to be able to remember the talks afterwards. He opened by saying that he would be talking about discrete complex analysis, which, if I remember correctly, was also part of his title. He mentioned the well-known theorem of Brooks, Smith, Stone and Tutte, and more particularly its beautiful proof using electrical networks (BSS&T were undergraduates when they found it), that a square can be decomposed into smaller squares, no two of which have the same side length. In general, he discussed how one might discretize the notion of analyticity so that it could be applied to functions on planar graphs, and drew attention to a very important criterion: one would like one’s definition to have a scaling limit, which means, roughly speaking, that if you let the mesh tend to zero then your function will tend, in some appropriate sense, to an analytic function on the plane. The climax of the talk was Smirnov’s remarkable result that the Ising model has a conformally invariant scaling limit and that it is universal. Again I didn’t catch the precise universality statement, but you don’t have to to know that it is a big deal.

I was slightly nervous during the talk because it was scheduled to end at 2.45 and the panel discussion I was chairing was scheduled to begin at 3.00. That in itself wasn’t a problem, but I had met only one of my co-panellists, Bill McCallum, whom I first met in 1994 when we were both at IHES for long visits. I had bumped into Bill a couple of times here in Hyderabad, which took the edge off my nerves somewhat. Incidentally, since I have just discussed Smirnov’s talk, perhaps it is a good moment to discuss a stochastic process that you will know well if you have ever been to an ICM: the process of meeting people you know. I myself, and I expect this behaviour is typical, made very few formal rendezvous (what on earth is the plural of rendezvous? — I mean it to be pronounced RONDAYVOOZ), and instead relied on chance meetings. These ought to be something like a Poisson process, and a nice aspect of this ICM was that the mean seemed to be fairly small. A partial list, off the top of my head, of people I knew (not necessarily well) and regularly bumped into is Bill Barton, Alex Bellos, Marianna Csornyei, Irit Dinur, Marianne Freiberger, Martin Grötschel, Roger Heath-Brown, Elon Lindenstrauss, Laci Lovász, Bill McCallum, Rob Morris, Assaf Naor, Oliver Riordan, Stas Smirnov, Benny Sudakov, Anatoly Vershik — I’m sure I’m missing some obvious people. But the point is that everyone would have had their own neighbourhood in the I-know-you graph (or is it a directed graph?) and the 3000 people at the congress were bound together by these chance meetings.

The reason I was nervous about the panel was twofold. The panellists were instructed to give short presentations of about ten minutes each. In my position as chairman, I had decided that the best way to fill two hours without the audience falling asleep would be to divide them into three portions, each with two ten-minute presentations and twenty minutes of discussion and questions. But I had no idea whether this format would work or whether I or any of the other panellists had anything worth saying. (In general, when people asked me about the panel discussion I advised them to go to the real mathematical talks that were going on at the same time.) My other source of anxiety was that there might be technical problems: I had uploaded my slides on to the ICM website, but if anything had gone wrong then I didn’t have a back-up plan (apart from a stick in my pocket that the organizers probably wouldn’t allow me to use in case of viruses).

In the event, my worries were unfounded. In particular, I found my co-panellists’ contributions much more interesting than they might have been, and everybody was good about sticking to time (another worry that I had as chairman). Here are a few highlights.

The first to talk was Carlos Bosch, who told us of a very amusing and interesting experiment they had done on mathematics teachers in Latin America. They asked the following question. Pablo buys a horse for $10,000, sells it again for $12,000, buys it again for $14,000, and finally sells it again for $16,000. Did Pablo make a profit or a loss, and if so, how much of one?

Apparently, only a very small percentage of answers were correct. Two common wrong answers were as follows.

1. Pablo bought the horse for $10,000 and sold it for $12,000, making a profit of $2,000. But then he bought it again for $14,000, so he made a loss of $2,000. Finally, he sold it for $16,000, making a profit of $2,000. Adding up the profits and loss you get $2,000.

2. Pablo started off buying the horse for $10,000 and ended up selling it for $16,000 so at the end of the whole process he had made a profit of $6,000.

But that wasn’t the end of the story. In an effort to get the point across to the schoolteachers, the experimenters said, “Ah, but imagine that Pablo had bought two horses, one for $10,000 and one for $14,000, and had sold them again for $12,000 and $16,000, respectively.” To this apparently excellent explanation, a typical response was, “You’ve changed the question! Now you’re asking about two horses whereas last time you asked about only one horse.”

That gave us some idea of the challenges facing us mathematicians if we want the whole world to see the light.

But the positive side of the story was that in Mexico there has been an initiative where professional mathematicians get together with mathematics teachers and show them how they think, by discussing the solutions to various problems, and more importantly the processes by which they reach these solutions. It seems that even after a fairly small number of sessions, the results of those taught by the teachers improve dramatically — not just in mathematics but in Spanish as well.

Next was Ivan Yashchenko, who told us how a mathematics education in Russia was much more problem-oriented than in most countries. The syllabus content took a back seat. He was fairly pessimistic about the quality of Russian mathematics education, but his pessimism was directed at the education of the masses rather than of the elite — the very best mathematicians in Russia, it seems, are still receiving an education that is as good as it has always been. He told us a nice problem that has been used in mathematics circles in Russia: you take a square grid — say ten by ten. Then round the boundary you put an arrow in each square, going in the direction that corresponds to going clockwise round the boundary. (At the corners it doesn’t matter which of two possibilities you choose.) Now the object is to fill in all the remaining squares with horizontal or vertical arrows in such a way that no two neighbouring squares — including diagonal neighbours — have oppositely pointing arrows. Or rather, the object is to prove that this cannot be done.

This post isn’t finished, but since I’m not going to be able to finish it for over 24 hours I think I’ll post an incomplete version for now and finish it later.

Later. During the over 24 hours, as it turns out, since I broke off from writing I have indeed thought of several more mathematicians who were part of my acquaintance neighbourhood at the ICM (and I still don’t expect it to be a complete list): John Ball, John Coates, Ingrid Daubechies, Gil Kalai, Gyula Katona, Peter Markovic, Jaroslav Nesetril, Gilles Pisier, Richard Thomas, Ulrike Tillmann, John Toland and Cédric Villani. One thing I noticed was that the vast majority of the people I knew had to be there for one reason or another — either they were speaking or they were high up in the IMU. Since they were also a very small sample of the mathematicians that I know comparably well, I want to ask why so few people decide to go to the ICM just for the fun of it. Of course, the number of delegates is large, but the proportion of mathematicians from faculties at major universities round the world, say, seems to be pretty small. I think quite a lot of people just don’t really like ICMs all that much, and others were perhaps reluctant to go all the way to Hyderabad, organizing flights, visa, hotel, etc. But perhaps there are further reasons.

Going back to the panel discussion, the next person to speak was Heinz Steinbring, who I soon realized was a man after my own heart when he advocated giving examples first. He also recommended another principle, for which I do not have a good slogan but which I strongly believe in, which is to teach theory having first established the need for it by means of a problem. An example I have in mind for this is matrix multiplication. If you have got to the point where somebody understands how matrices related to linear maps — in two dimensions, say — then it is not a hugely difficult exercise to work out the matrix that gives you the composition of the maps defined by two other matrices. And if you’ve been through that exercise, then matrix multiplication seems much less bizarre and arbitrary.

Next was Ramanujam. (He liked to be known just by that one name.) The thing I remember best from his presentation was a beautiful list of thought processes that all research mathematicians would agree are essential to mathematics — things like generalizing a problem to make it simpler — and that he claimed, I think rightly, were almost entirely absent from school mathematics.

It occurs to me that I may not have mentioned that the title of the discussion was “Relation between the discipline and school mathematics.” “The discipline” referred to research mathematics. I also haven’t said much about the questions from the floor. Some of these were quite hard to understand (in which case I would look expectantly at my co-panellists in the hope that one of them would have a go at an answer), but several of them were interesting. One that I remember best was a suggestion that professional mathematicians should write school textbooks, which is something I’ve vaguely (VERY vaguely) thought of doing at some point.

Bill McCallum gave a very interesting and entertaining presentation about quadratic equations, a mixture of history (the discovery of the solution, the difficulties that were involved, and so on) and current affairs (a debate in the British parliament about whether it was worth teaching children how to solve them). And I gave the last presentation, in which I argued that university-style analysis with epsilons and deltas is not as far removed from school-style analysis as is often supposed.

Once the final question was over, I found myself whisked to some chairs at the back of the hall, where I was interviewed, mostly about the Polymath project. That lasted for nearly an hour, and in particular ruled out going to an invited talk between 5 and 5.45.

From 6 to 7.30 was a performance of classical Indian dance in the main hall. I decided I would go to it but not necessarily stay for the whole thing. The criterion I applied was that I would stay until the information content was close to zero. By that I mean that at the beginning I didn’t have all that much idea what to expect, but as the performance went on it all started to seem fairly similar (which was of course a reflection of my ignorance of what was going on, but given that ignorance the rate of extra information I was receiving was small). Anyhow, I stayed for half an hour, and then came back for the final quarter of an hour, having worked on a blog post in between. The performance began with a man who had a kind of tragic clown face on his own on the stage. I should perhaps say, after the rather dry words about information content, that I enjoyed what I saw — the very characteristically Indian shapes that the dancers made with their bodies, which again reminded me of Indian sculptures. I have another photo, again not a good one but it gives some impression of what it was like.

After that was the conference banquet, something that happens at every ICM and has a different style each time. I think the most memorable was the one in Beijing, where they had a room that was large enough for everyone to sit down (at round tables). This was memorable for the logistics of getting three thousand people from the convention centre to the different place where the banquet was held, in buses that took about twenty people each. A huge mass of delegates assembled just outside a (large) side entrance to the building, and a sort of semi-orderly queue formed. We were told many times please to be patient, which by and large we were, but a little bit of impatience right at the end seemed to be necessary to get on a bus — those who were too well-behaved would simply stand and watch as thousands of other delegates swarmed past. I was one of the first to go, by which I mean one of the first two or three hundred to go, and to my surprise we were set down next to something that I had passed each day in the bus on the way to the convention centre and found interesting. I don’t know how to describe it but it had pink walls and the phrase that jumped into my mind was “Hindu park.” Anyway, it was a sort of park, and it had a slightly Hindu feel, I thought, quite possibly wrongly. We walked about two or three hundred yards through it until we got to a sort of marquee, which had a covered corridor leading to it. I was relieved to get there because it was starting to rain. (The weather forecast I looked at before leaving predicted heavy rain for the entire week, but although there were one or two very heavy showers they were also quite brief and I was lucky enough never to be caught by one.)

I’ll finish the description of the banquet tomorrow, and then I’ll have finished day two.

Banquet. Come to think of it, I can’t remember whether they actually called it a banquet. Perhaps it was just the Conference Dinner. Foodwise, it was pretty similar to what I had been getting used to from various receptions, breakfast, and so on. For instance, bits of chicken were handed round, and various familiar Indian were lined up in chafing dishes at tables round the edge of the marquee (which was open at the sides). However, there were so many people at this dinner that there were long queues for the real food.

After a while I decided to brave one of them, and when I got to the front about fifteen minutes later (and glared, with absolutely no effect, at people who just walked up to the front and queue barged), I found that I was in the queue for vegetarian food. I asked for a bit of that and then tried to sidle over to a meatier set of chafing dishes. But it didn’t work, with the result that I ended up with a half-full plate of vegetarian food and not much prospect of supplementing it. I went back to the people I had been chatting with, who were standing round a little heap of conference bags and discarded outer clothing — it was getting extremely hot with all the people there — and continued to chat until somebody said that there was a heavenly world just a few yards away from us. That is, there was another marquee, just like the one we were in but cooler, with fewer people, with an abundance of readily accessible food. It sounded too good to be true, but it was true. We went up another corridor (red carpet below, tented roof) to a higher level where to the left was another large marquee that was just as described. The one thing that kept it earthly was that the half plate I had eaten had taken the edge off my appetite. But it was worth it for the reasonable temperature alone.

Getting back to the hotel was another logistical miracle. At some point I sensed that it might be a good idea to make my way outside and try to find out how the system would be working. I asked someone who appeared to know, who told me to go a bit further and wait for somebody carrying a placard with the name of my hotel on it. I decided to take a little bit of initiative, and walked out of the park and into the street (which had, now as before, a rather sulphurous smell) where a mass of buses had congregated. I walked down, looking for one that had the name of my hotel in its window, and eventually found it a long way back. I got in, and was the first in, which enabled me to choose the one seat that had room for my legs: right at the back with the aisle in front of me rather than another seat.

The one other thing to report about the day was that after the rest of the bus had filled up apart from the rest of the back row, three people got on. There were four seats in the back row, and I was in the second from the left (as you looked forward). The bus had single seats on the left and pairs on the right. OK, so obviously I had to share the back row with those three people. But I made a mistake: I moved my legs to the left, thereby gently encouraging the first person, a young woman, towards my right. Except that, thinking about it now, it wasn’t really a mistake, because if I had sent her the other way it would have been forcing her to sit next to me when she had had the chance not to. If you don’t understand why I couldn’t have done that, then perhaps it’s a British thing.

Anyhow, it turned out the other two people were a couple, and they, quite reasonably, asked if I would move so that they could sit together. Had I, by getting there way before them, built up a right to leg room that exceeded their right to sit together? I don’t know. Again the most my Britishness would allow me was just the faintest hint of reluctance and the tiniest gesture of discomfort during the journey.

I find that one thing I lose at conferences is discipline about going to sleep. I often get very tired and think, “I must have a good night or I’m going to have some kind of collapse.” And I’m quite good at getting myself in a position where a good night is possible. And then I write one of these blog posts — which is OK, because there’s still a reasonable amount of night left — and then, just to help me get in a sleepy mood, I … er … switch on the TV and discover that there’s a not very well known film on starring someone like Mickey Rourke. As I watch further, I come to realize that it is fairly near the beginning …

That’s not exactly what happened this time, but I didn’t do a great job catching up on the sleep I badly needed to catch up on. And the next day I absolutely needed to be at the convention centre by 9am, because the first talk was to be given by Artur Avila and I didn’t want to miss that.

Normally at an ICM the first day has its own very distinct atmosphere because of the opening ceremony, the laudationes, and so on, after which the congress settles into a more regular, working format, with plenary lectures in the morning and invited lectures in parallel sessions in the afternoon. This year, because the number of prizes has increased and one of them needed inaugurating, some of the first-day feeling continued into the second day. And because my panel discussion was in the afternoon and lasted two hours, I had to miss the parallel sessions, so I personally had no sense of the ICM having properly started until the third day.

After the coffee break that failed to live up to its name was a lecture by Yan Yan Li on the work of Louis Nirenberg. From a distance, Yan Yan Li looked about 25, though later I caught a glimpse of him from closer up and could see that he belonged to the age range one might expect. (After writing that, I looked him up and found that he was slightly older than me — I certainly wasn’t expecting that. I must ask him how he got hold of the elixir of youth.) He was another member of the read-directly-from-slides school. I have no good suggestion about what to do when a slide with the next two or three minutes of talk appears. Do you read through it in the twenty seconds it takes and then listen to a repeat of all but the first twenty seconds? Do you try to discipline yourself not to read ahead? (I think the effort of doing that would soon cause me to forget about actually thinking about what the words mean.) Or do you ignore the speaker entirely, and if you can get through the slides more quickly than the speaker then you spend the remaining 75-80% of the talk catching up on sleep in little two-minute bursts? There are drawbacks with all these strategies. It follows, as night follows day, that there is a drawback with this style of talk …

However, some of the content was quite amusing. I didn’t write much in my notebook, so I may as well reproduce the lot (not word for word, but in slightly expanded form).

Why did Nirenberg get the first ever Chern prize for lifetime achievement? Yan Yan LI’s short answer was that he was one of the most outstanding analysts of the twentieth century, who worked in partial differential equations, inequalities, and regularity theory.

If you like amusing statistics, then you’ll be interested to know that in each of the last ten years, Nirenberg has had at least two of the top fifteen most cited papers. His mathematical ancestry can be traced back to Hilbert as follows: Hilbert — Schmidt — Hopf — Stoker — Nirenberg. And Nirenberg is one up on Chern with 45 students.

Two famous results were to solve the Weyl and Minkowski problems, pioneering the use of nonlinear PDEs in geometry. What are these problems? They turn out to have very nice simple statements. Weyl asked whether if you have a smooth metric on the 2-sphere with positive Gaussian curvature everywhere, you can find an embedding of the sphere in to that gives rise to precisely that metric. To put it another way, an obvious way of producing smooth metrics on the sphere with positive curvature everywhere is to take smooth embeddings of the sphere into that have positive curvature (defined extrinsically) everywhere and pull back the metric you get. (That is, if is the embedding, you define to be the distance in between and ) In 1938, Lewy solved this problem for analytic embeddings; Nirenberg managed to remove the analyticity assumption.

The Minkowski problem was a similar problem but the question was about curvature instead. Since the first problem mentioned curvature, I had better explain further: this time one wants an embedding such that the curvature at is given by the extrinsically defined curvature at

I would love to tell you something about the ideas that went into the proofs of these results, but I have nothing written down. I cannot remember whether Yan Yan Li told us anything about the proofs, apart from the fact that nonlinear PDEs came into them somehow.

So let me give a total guess instead, one that I would not have been able to make had I not heard innumerable accounts of Richard Hamilton’s general strategy for solving the Poincaré conjecture. Perhaps Nirenberg devised a very clever PDE such that if you start with a smooth embedding of the sphere as your initial data and allow your embedding to evolve according to the PDE, then it will converge to an embedding that has the metric you want. But it’s equally possible that he did nothing of the kind.

After a while, I have written in my notes, the talk became a long list of statements of theorems of Nirenberg and related results of other people. I stopped being able to concentrate, I think because I lost all sense of what was important and why. I started to long for the talk to end. It became rather like a brilliant spoof by Dudley Moore of a Beethoven piano sonata, where he keeps playing what you think must be the final climactic cadence of the piece, and it keeps not being the end. Similarly, Yan Yan Li would come to a good stopping point, and then up would come a new slide and he would say, “Part 6. [Insert branch of analysis here],” which we had of course all read in the previous second or two. But he did enough to convince me that Nirenberg was a worthy winner of the prize.

I’ve just realized that I made a mistake in my previous post. The coffee break came not after Bryant’s talk but after this one of Yan Yan Li. Perhaps that explains better why I was so desperate for it to finish. (The overrunning was principally due to Bryant, so I had been hoping for the most unlikely event that Yan Yan Li would not use up his 45 minutes.) And perhaps it excuses me for the decision I made next, which was to sit near the back of the next talk, Ingrid Daubechies on Yves Meyer, so that I could listen to the beginning and leave it early when it got more technical (if it did).

The half or so of the talk that I heard was extremely good, and under normal circumstances would definitely not have justified walking out. (I later heard from other people that the whole talk was excellent.) Meyer was best known to me, as is Daubechies herself, as a key protagonist in the story of the discovery of wavelets and the explosion in their use that took place from about the 1980s. But Daubechies began by telling us about a very pretty early result of Meyer’s that I had not heard of: he constructed sequences of integers such that for each real number the integer parts of are equidistributed in if and only if is transcendental. At the moment all I can tell you is this statement — I need to think about the result for a while to appreciate it properly. But I presume that it is a genuinely hard result and not some easyish exercise that uses nothing more than the fact that the set of algebraic numbers is countable.

In fact, having written that, let me at least check that it does not have a trivial proof of that kind. Let be a countable set of reals. Can we construct a sequence such that is not equidistributed mod 1 for any but is equidistributed mod 1 for any ? Let’s think how one might find a very general class of sequences satisfying just the first condition. One obvious method would be to enumerate as and insist that has the property that lies in the interval mod 1 for every and every By Dirichlet’s box principle we can certainly construct such a sequence, and we can make it grow as fast as we like.

But what would make all the other sequences equidistributed mod 1? Now we have uncountably many things to check. The only way I can even vaguely imagine of dealing with this would be an intricate bookkeeping exercise: one would choose a large and ensure that all but a small set of numbers in have multiples that are approximately equidistributed mod 1; then one would repeat the exercise with a much larger and so on.

Of course, I’m not expecting this to work, since I don’t actually believe that Meyer’s result can be generalized to all cocountable sets (or, to avoid triviality, all cocountable sets of irrational numbers).

Come to think of it, I don’t see why I don’t have a counterexample to Meyer’s result. Given a sequence let’s try to build a transcendental number such that the sequence is not equidistributed mod 1. To begin with …

OK, I take that back. My proposed proof would have worked for irrational numbers too, but we all know that the sequence will do for those. My misconception was to think of as a very rapidly growing sequence, whereas in fact to make the result work one will need the opposite. Now I’ve been through that thought process, I have a slightly more informed respect for the result. (I’d be even happier with an example of a cocountable set of irrationals for which the result is false. The next exercise I would want to try is to take all irrationals apart from That is, if you know that is equidistributed for all irrationals apart from , can you deduce it for as well? If that turns out to be easy, as I think it may, then I would change it to all irrationals apart from rational multiples of There I think it is probably enough to take to do something like running through all the integers such that lies between and for some integer

Another very nice looking number-theoretic result proved by Meyer, and again one that I haven’t understood properly in the sense of appreciating where the difficulty lies, is this. Define a subset of to be a model set if there exists a finite set such that That is, the differences of elements of all belong to the union of a finite set of translates of Meyer showed that if is a model set, then there must be a Pisot or Salem number such that Conversely, if is a Pisot or Salem number, then there must exist a model set such that

If you haven’t heard of Pisot or Salem numbers, let me tell you what I remember from an explanation I received from Jonatan Katznelson (son of Izzy) sixteen years ago. (I’ve been reminded a few times since, or I would have forgotten by now.) We know that the multiples of an irrational number are equidistributed mod 1, but what about the powers of an irrational number? Well, trivially they don’t have to be equidistributed, since you could take an irrational number that’s less than 1 in modulus. But what if we insist on an irrational number that is greater than 1? Must its powers be equidistributed? And do we even need the number to be irrational? Are the powers of 3/2 equidistributed, for instance?

This kind of question takes one rapidly to some fascinating open problems, but one question at least is easily answered: there are some very nice irrational numbers with powers that are not equidistributed. The canonical example is the golden ratio Since the th Fibonacci number is and is less than 1, the powers of get closer and closer to Fibonacci numbers, so they tend to zero mod 1. If I remember correctly, a Pisot number is a number for which this proof works: that is, an algebraic number greater than 1 such that all its conjugates are less than 1 in modulus. Actually, thinking about it, one should also insist that it is a root of a monic polynomial with integer coefficients, so that the corresponding recurrence relation gives you an integer sequence with each term an integer combination of previous terms. Why might such numbers pop up when one has a model set? I do not know, though for reasons that I cannot explain, even to myself, I don’t find it completely implausible.

Going back to the general question of when powers of a number are equidistributed, I suppose there are numbers like that fail for the trivial reason that every other other power is an integer. But I’m fairly sure that all the known examples of numbers with powers that are not equidistributed have fairly simple reasons for not being equidistributed: as soon as you don’t have a simple reason (as you don’t, for instance, for the number ) then you have an open problem.

Meyer is interested in all sorts of topics that are of huge practical interest. For instance, he has worked on denoising and deconvolution: if you have a noisy or blurred image, can you find good algorithm for producing from it a clean focused one? The human brain somehow manages to extract information from imperfect images. Obviously, that is partly because it interprets those images. But there seems to be a big automatic part there too that is amenable to mathematics: the kind of thing one would like to do is expand the image in a clever basis so that the noise or blur goes to certain coefficients that can be thrown away, whereas the “real” image goes to other coefficients. And wavelets are just such a clever basis for many applications.

A beautiful moment in the talk came when Daubechies reminded us of a strange few seconds in the Jim Simons video, during which he stopped looking like Jim Simons and looked more like the villain in Terminator 2 during one of his (its?) semi-liquid moments. I would have forgotten about that almost immediately, but as soon as Daubechies mentioned it, I realized that it was quite puzzling: what kind of fault would lead to that very strange effect? She explained that with modern image compression techniques, if you lose part of an image, then it won’t be a particular region or anything like that, but a particular aspect of the image, such as its textural quality. In this case, she told us, we had lost the texture but retained a sense of edges and boundaries. It made me want to go back and look at the weird video moment all over again and appreciate it properly (instead of just sniggering as I had the first time) but it was too late.

There was more, not just of the talk, but even of the part of the talk that I attended, but I think I’ll leave it there for now. When I get time, I’ll cover Smirnov’s talk, the panel discussion, and the conference dinner. And that will take me to the end of the second day.

I’ll finish this post with a reminder that the work of Nirenberg and Meyer is discussed by Terry Tao on his blog.

Yesterday I wrote a post in the Rajiv Gandhi International Airport in Hyderabad. I couldn’t post it there because I wasn’t connected, but Dubai airport had free wi-fi so I could finish the job a few hours later. The ICM interrupted a holiday I was having in the South of France with my wife’s family, so now, after a refreshing four-hour night, I find myself at 6.30am in the rather less glamorous Luton airport, stupidly early for a flight on a rather less glamorous airline than Emirates, with whom I flew to Hyderabad and back. Talking of stupid punctuality, there’s a maxim I quite like, which is probably very well known but I heard it only within the last year or two, which is that if you have never missed a plane then you spend too much of your life in airports. I like the maxim, but I don’t live by it, because I have an irrational dread of missing planes, and an entirely rational lack of dread of spending time in airports — if all else fails, they are a pretty good place to do mathematics. Today, all else has not failed, since I have a charged up computer (that’s an issue these days — I think my laptop is due a new battery) and multiple blog posts to write. I haven’t quite decided what form these will take: I cannot possibly write about days 2-4 in the same amount of detail as I have written about day 1, but once I start, it is hard to stop. So do I prefer to keep up the detail and risk stopping in the middle of day 2, or to force myself to become a bit sketchier? Perhaps I’ll be detailed, but more selective about what I write about.

It was never quite clear exactly when the bus would leave the hotel for the convention centre, so if I was short of sleep, I couldn’t afford to set my alarm so that I would have just enough time to catch it. So for me, each day of the ICM started with waking up earlier than I would like, and a little earlier than was strictly necessary. I’m not too fond of sleeping with air conditioning, so I would wake up feeling sticky and in definite need of a shower. The shower, I have to say, was one of the best hotel showers I can remember. Like many showers, it had a two-dimensional tap (one for temperature and one for amount of water), and once I had got the temperature to my liking on the first day, all I had to do on subsequent days was pull the little lever without rotating it and the water would be ready for me almost instantly, in generous quantities and at the same temperature that I had previously established. Once I was in a fit state to face the world, I would go downstairs to the lobby, ask about the bus and hear that I had time for breakfast. Breakfast was a buffet with Indian food in what I now know to be chafing dishes, of a kind that I would not normally feel like first thing but that I became used to. There was also more standard Western food available, but it wasn’t quite standard enough for me to feel tempted by it: for instance, there were croissants that were scaled down by a factor of about 3 in every direction that were a bit too pale and looked dry. There was also someone there cooking eggs — I had a couple of pretty good omelettes while I was there.

I was to come to knw the bus pretty well. As well as the driver, there would be one or two people who were either boys or very young men — the same people each time — who would shepherd us on. Even though the bus was pretty small, more like an outsized minibus, the driver was in a separate compartment at the front. To get into this compartment, there was a door that was strangely un-car-like: it was wooden with a window in it, and it was … well, just an ordinary door that opened on a hinge.

There were two things I was a little anxious about when I was in India. One was Delhi belly (after a lot of thought, I’ve given up on trying to think of a suitable Hyderabad equivalent). Every time I felt the smallest stomach twinge or hint of indigestion, I wondered whether this was the moment. And I know what I’m talking about here. In Beijing in 2002 I took a day off to go to an untouristy part of the Great Wall of China, which involved explaining to a taxi driver whose linguistic competence was disjoint from mine how to get to an obscure part of Beijing — not a bus station — from where the bus would leave. I got up stupidly early for that too, and then the bus didn’t leave for about an hour after the scheduled time. And a small way into the journey, but enough time for us to have reached a major traffic jam, I started to have serious worries about whether I would be able to last to our destination without a disastrous accident. Any more on that (and there is more) will probably be more information than you strictly need, so I’ll say merely that I did just make it, helped by the fact that we stopped off at a much less interesting place first. I think I may have been lucky and escaped from India without any illness, even minor. I was pretty careful when there, avoiding all salad and fresh fruit, drinking only bottled water, and so on.

My other worry was malaria, even though I had been told at my doctor’s surgery that this part of India was low risk (meaning that it wasn’t worth taking any medication). I had insect repellent with me, which was an unpleasant lotion that left my skin with a stickiness very similar to what I had removed in the shower. (It also stung if I put it on soon after shaving, which I did.) However, my first bus journey, the one to the opening ceremony, had taught me that there could be mosquitoes on buses. In fact, there were a few on every daylight bus journey I made (and possibly the ones after dark too, but those would have been harder to spot). They didn’t actually seem to be out to get me, even on the day that I did not wear repellent, but others later told me that they had been bitten a lot. (On the first day, I decided that it was worth looking ridiculous in order to lessen still further my tiny risk of malaria, so in the bus I wore my shirt collar up with the top button done up. I also pulled my socks as high up my legs as they would go.) I left India without a single bite, from which I deduce that I did not get malaria. And it’s getting to the point where I’m pretty sure I did not get any kind of stomach problem either. (The last few sentences are written from my destination in the south of France.)

The traffic was again not nothing but not dreadful and we arrived in good time, so I probably made straight for the “Internet Café,” which was all internet and no café. And I probably didn’t go to the main hall until just before 9.30 when the day’s events started, reasoning (based on my experiences of previous ICMs) that places there would be at far less of a premium than they had been for the opening ceremony. I was actually a bit hazy about what was going to happen, but Lovász helpfully told us: we were going to have some talks and videos about the life and work of Shiing-Shen Chern, in order to inaugurate his new prize. (It had been awarded to Nirenberg the previous day, but not enough song and dance had yet been made about the prize itself.)

Present there was May Chu, Chern’s daughter, and present in the way that the stars are present in the sky (in the sense that the light we see was emitted long ago) were Jim Simons, famous collaborator of Chern’s and endower of two thirds of the prize, and others. May Chu was completely Americanized (or rather her voice was — I don’t know how she lives), confident in a good way, and articulate. She also had interesting traces of Chern’s looks in her face, though I wouldn’t have noticed that had I not known in advance that she was his daughter. She told us that we would be seeing three short videos, one a communication from Jim Simons, one a biographical sketch of Chern, and one a series of reminiscences.

The first was the Jim Simons video. I won’t describe the whole thing but here are a few highlights. It began with Simons directly addressing us, saying the kind of thing you would expect, but most of it was an interview: Dennis Sullivan was called in to interview Simons about Chern, and between the two of them they managed to make it highly entertaining. Simons, by the way, looked about 60, with white hair and a short white beard. And you know those moments when you spot a striking resemblance between two people who don’t look like each other, some kind of Gestalt that you cannot analyse? I had that with Dennis Sullivan and Bill Murray. Does anyone else see it? Here is Dennis Sullivan and here is Bill Murray. (Of course, two pictures chosen fairly randomly from Google images won’t convey the similarity as well as actually seeing Sullivan moving and talking and having a mental image of Murray. Looking at the pictures though, I think the sloping eyebrows have something to do with it, together with the look of someone who has lived a lot of life, which I think they both have — I’m not talking about number of years.)

The video lasted about 15 minutes and you can watch it by going to the ICM home page, clicking on “online streaming activities” and choosing Day 2 Part 1 (and jumping forward a bit to get to it). But if you haven’t got time for that, then here are a few highlights. The first was Simons’s description of what it was like to see Chern for the first time. Simons had gone to Berkeley to do a PhD because of Chern, but for his first year Chern was on sabbatical. Then one day Simons was at a seminar and in walked a tall Chinese man with a large head (this point was emphasized in one of the other videos) who was clearly somebody. He asked who it was, and was amazed to discover that it was Chern: he had assumed that Chern was a shortening of something like Chernovsky. “Chen” would have suggested someone Chinese, but that extra “r” made all the difference to his perception.

When Sullivan asked whether Chern had been helpful to Simons when he was working on his PhD, he said a straight no, though qualified it by saying that Chern had been very encouraging. (I imagine this could be telling us that Simons was an independent thinker at an early stage.)

Sullivan told Simons that he had been to Chern’s talk at the ICM in Nice in 1970. Afterwards, he had gone up and asked Chern whether he could have his transparencies. Chern, who was completely uninterested in them, said of course he could. And apparently the only name mentioned on the transparencies was that of Simons, so now, 40 years later, Sullivan was going to give the transparencies to Simons.

As I mentioned in an earlier post, Simons is famous not just as a mathematician but also as somebody who left mathematics to set up a hedge fund, which he did so successfully that he is now one of the richest men in the world and a major philanthropist, with a particular interest in mathematical causes. Sullivan asked him how Chern had reacted on hearing that Simons would be leaving mathematics. Simons replied that Chern had never said anything critical to him about it, but that Chern had not heard the news in his presence, and that he, Simons, had heard about it later. Apparently, Chern said, “After all, he is not David Hilbert.”

Once the videos were over, Robert Bryant, the director of MSRI and a professor at Berkeley, gave a talk about the work of Chern. I don’t think I want to say that much about the talk, since there are much better ways of finding out about Chern’s work than reading an expansion of my notes on that talk. But that is not to say that I learnt nothing. For instance, though I had heard of Chern characters (since they are one of those concepts that becomes a buzzword, so that even if you are in another area and don’t know what they are, you know that they are central and important), I did not know the back story, so to speak, which is that they arose out of Chern’s (successful) efforts to find an intrinsic proof of the Gauss-Bonnet formula.

Before that, Bryant explained that Chern initially rose to prominence by being almost the only person in the world to understand something called the “method of equivalence,” which was invented by Elie Cartan. (Of course, Cartan himself understood it.) This caused me to reflect on how different the routes are by which mathematicians manage to prove theorems. Once Chern had understood Cartan’s method, he went on to find many deep applications of it. And there are several other stories like that. I don’t know how accurate it is, but the picture I have of Deligne is that he was at one time the only person who truly understood Grothendieck’s work, with spectacular consequences. But I know that I myself cannot work like that: I find it almost impossible to understand anything unless I already strongly feel the need for it, and can give myself the illusion that I am discovering it for myself. (Of course, it must be partly true that Chern was aware in advance of the kinds of problems that Cartan’s methods could help him with, but I still think that there is a distinction here.) This closes off large parts of mathematics to me, but leaves me with a niche where I can operate. And the subject is so big that a niche is all one needs.

I learned that Chern-Simons invariants are “secondary” invariants, in the sense that they are what you get when Chern classes vanish. As with what I learned about Ngo’s work, this is replacing one thing I don’t fully understand with some others, but that is nevertheless useful: the image is still blurred but less so than before.

At the end of the talk, Bryant told us that Chern had had 44 PhD students and 697 mathematical descendants (as of the 16th — Bryant suggested that after a couple of days one could no longer be sure that the figure was accurate).

The last note I wrote says, “Went way over time.” The effect of that was that what was supposed to be a measly 25-minute coffee break after almost two hours sitting in the same place became an even more measly coffee break of 15 minutes after exactly two hours sitting in the same place. Had I been in charge, I would have suggested starting the next talk (about the work of Nirenberg) a bit later, but perhaps that was not practical given that there might be people not present who would be coming to the later talk. It may sound trivial now, but this mattered: such were the queues for coffee that the difference between 25 minutes and 15 minutes was the difference between a cup of coffee and no cup of coffee. And after the night I had had, that meant the difference between feeling vaguely human and not feeling vaguely human.

As I write this I'm sitting in the Rajiv Gandhi international Aiport waiting for a flight to Dubai. The ICM lasts till Friday, but for me it is over: with a son of two and a half, there are limits to how long it is reasonable to be away, and the marginal utility of the ICM has dipped below the marginal cost of staying away (or rather, that is how I judged it in advance). Actually, today (Monday the 23rd) is the half-way point and is a free day. Most of the delegates, to judge from the people I've spoken to, are taking the opportunity to go on ICM-organized tours. It is pretty tantalizing not to be doing that myself, but I leave India with a huge affection for the country and a strong sense that I'll be back.

Listening to five laudationes in a row is pretty gruelling — as I know from having done it five times now. After they were over, Assaf Naor asked whether I wanted to go and get a cup of coffee somewhere, or whether I would be listening to the talk by Varadhan, a recent Abel prize winner. To make my decision easier, he explained that he himself was skipping the talk only because he had heard it before, and he knew that it was excellent. I hesitated, and in the end decided that self-preservation was in order, a principle that I continued to adopt later. By that I mean that if you go to every talk that has a good chance of being superb, plus every talk that is sufficiently noteworthy that you don't want to miss it even if it is terrible, then you end up utterly exhausted. Because the laudationes had started late, there was very little break between them and the beginning of Varadhan's talk, and I just couldn't face three and half hours, or whatever it would have been, of continuous talk. The difference between this ICM and previous ICMs is that these little decisions of mine, which I normally like to make rather discreetly (which is particularly easy for parallel sessions, because you might always be at a different talk), are now completely public. But I think I'm ready to live with this.

Assaf also introduced me to Irit Dinur, whom I was very pleased to meet. [By the way, I'd like to point out, for the sake of the very small percentage of readers who might care, that I dithered for a long time about whether to write "who" or "whom" there. One is more correct, but sounds a bit pedantic. In the end I couldn't quite bear to write "who", having initially written it and even started this explanation but as an explanation of why I couldn't quite bear to write "whom". But then I found that my dislike of "whom" wore off slightly. In the end, the truth is that neither reads very well: what I should do is go back and just paraphrase the whole sentence, but life is short.] The three of us ended up at a place that called itself a Deli, which was on a corridor that linked the main conference hotel to the conference centre. I've already mentioned our conversation. The other parts that I remember were some detailed mathematical explanations from Assaf, whose enthusiasm for our subject is boundless, and a debate about whether the current format for laudationes is as good as it could be. Irit thinks they should be ten minutes only. I can see the point of this: it would make it impossible to go into much detail and would force the speakers to concentrate on the headline reasons, so to speak, for the award going to the person in question. It would also make the laudationes less of an ordeal. In the end, however, I disagree. Or rather, I can see that at the end of some laudationes (I'm not talking about this year's) it might be the case that the useful information could have been conveyed in ten minutes, but I still think that an optimal 25-minute laudatio (which I think is what it is supposed to be) is better than an optimal ten-minute laudatio. Talking of which, I forgot to mention Jacob Palis's style of chairmanship: one or two of the talks ran over, his response to which was to get up from his chair and stand on the stage with his arms folded in a way that would have embarrassed me into stopping pretty quickly, but didn't seem to have that effect on the speakers.

Next up for me was two receptions, one hosted by the US National Committee for Mathematics and one by the Royal Norwegian Embassy and the Norwegian Academy of Science and Letters, both from 6-8pm. I randomly decided to go to the US one first. Soon I found myself with a glass of red wine in one hand, which left the other free to spear little bits of chicken with a cocktail stick (which I was offered frequently) and dip them in a sauce before I ate them. I don't actually know that what I've just written is true, because by now I have been to so many receptions that I cannot distinguish between them down to this kind of detail. But what I can say is that approximately 100 percent of these receptions had little bits of chicken coming round frequently. Often the sauce was green, made with mint and coriander.

Cédric Villani was at the reception. I had met him once before, briefly in Madrid in 2006 where he was an invited speaker, and he also knows my wife slightly. So I congratulated him, and reminded him of that, but he didn't need reminding. It must have been about his hundredth conversation of a very similar kind. After about 30 seconds of it (which was about the right length — I'm not trying to suggest that it was cut off prematurely), he headed towards the drinks and the hundred and first …

At around 7.05, somebody started giving a speech. It seemed an appropriate moment to head off to the Norwegian reception, held at the Novotel ballroom (the Novotel being the hotel adjacent to the congress building). There I found many of the same people I had been talking to at the US reception, but some others as well. (Part of the explanation for the others was that they had chosen the opposite order from me, but there may have been a few people who had been invited to just one of the two receptions.) Whatever the precise details of the food on offer, what I am confident of was that it was very similar at the two receptions, though I have a dim memory that it was slightly better at the Norwegian one.

At 8.15 I had an invitation to a dinner that, according to the invitation from the Executive Organizing Committee of the ICM, was to "felicitate the awardees". I could translate that into more conventional English (which reminds me that I meant to point out a rather charming mistake on the lunch coupons, for which the dates were given as 19th, 20th, 21th, 22th, etc.), but it wasn't clear in advance what "dinner" meant. Did it mean a rather formal sit-down occasion for just a small number of people, or would it be a vast dinner with huge queues for food, or would it be something in between? Two clues were that Oliver Riordan (the person I ran into in Dubai airport who was an invited speaker) was invited too, and that it was to be held in Halls G.01 – G.06. So perhaps the invitation had been extended to all invited speakers. (As I mentioned before, I was officially an invited speaker, even if not one in reality.)

It was indeed something in between. The combination of Halls G.01 – G.06 (the convention centre was the kind of place where almost all walls could be folded up, if that's the right phrase, so that rooms were of variable size — in particular, the vast room where the opening ceremony took place was divided up afterwards into one, still vast, room of about half the size of the original one, a corridor, a smaller room for talks, and the room where the computers were) produced a room that was not too large. In fact, looking back on it I'm not sure they used all of 1-6. The food started with yet more chickeny eats being handed round and continued with what would become the other standard culinary experience, something pretty similar to a buffet in an Indian restaurant: you would take a plate and help yourself to a selection of different dishes, each in a metal something for which I can't think of a good word. Since I'm a mathematician, let us take X to be the container in question. Then X had a domed lid hinged at two antipodal points so that either the lid was underneath X, or you took hold of a handle and pulled the lid till it formed a hemisphere above X, closing it and keeping the food warm.

I'm not sure why I'm telling you this. Perhaps more interesting is that as I came into the room, Lindenstrauss was leaving it with his wife and children. He was carrying a very tired-looking daughter, and said he'd be back once he'd got his children to bed. He duly was, and I had a chance to congratulate him too, which meant that the only younger awardees I did not felicitate were Ngo and Spielman, who were the only ones I did not know, and still do not know, even slightly. In fact I'm not at all sure that they were at the dinner. I almost had a chance to felicitate Spielman, since he knew Assaf and ran into the two of us earlier. I was hoping to be introduced, but Assaf, like a true mathematician, did not do the honours, and I, like a true mathematician, did not take matters into my own hands. So I have come tantalizingly close to meeting and felicitating Dan Spielman, but didn't quite make it.

After that I shared a taxi back to the hotel with Marianne Freiberger and Rachel I-didn't-catch-her-surname from plus magazine, who were (and still are) also covering the ICM and happened to be in the same hotel. By the time we got back it was about 10.00. I then spent about three hours at my computer, writing one of my earlier posts and having a long Skype conversation with one of my sons (not the two-and-a-half year old). As I have already mentioned, I found myself annoyingly un-tired, so did not get to sleep until ridiculously late, which was unfortunate as the next day I would have to get up early enough to catch the bus that would get me to HICC in time for the beginning of the next day’s proceedings, which were connected with the new Chern prize and were due to start at 9.30.

I’ve saved the best till last, which should not be taken as a negative comment about the other laudationes, since Gil Kalai’s was a tour de force. His first distinction was that he was the only one of the five speakers not to be wearing a tie. He was, however, wearing a suit, so the result was to look smart in a trendy way rather than smart in a more standard mathematician-giving-important-talk way. And he opened his talk daringly with the promise that his would be a comprehensible talk, which got a laugh from the audience.

On a more negative note, I was a bit shocked that a significant proportion of the audience got up to leave before he started, as if to say, “The real business is over — this is just the Nevanlinna prize.” All I can say is that it was their loss, not just because of the wonderful talk but also because of the wonderful mathematics described in the talk.

One of the big achievements of Spielman (in joint work with his long-time collaborator Shanghua Teng) is a technique known as smoothed analysis. Here is Gil’s explanation (except that if anything seems wrong about it, that is my fault not his) of what it is and what the point of it is.

Much of complexity is concerned with worst-case analysis of algorithms. That is, you have an algorithm, and to assess how good it is, you ask yourself what the longest it could possibly take is over any input of length But there are some algorithms, notably the simplex algorithm, that work very well in practice, even though there are examples that show that their worst-case behaviour is exponentially bad. This was a mystery for decades after the algorithm was first introduced. (More accurately, at first it was believed to be good for all inputs, but then Klee and Minty found an example that demonstrated that is was not, and that was the start of the mystery.)

One obvious idea is to study the average case behaviour. That is, one might like to show that the algorithm works quickly for almost all inputs. However, this is not a great idea, since what it is basically saying is that the algorithm works well for random inputs, but in practice the inputs to which one applies algorithms such as the simplex algorithm are far from random. In principle, one might prove excellent average-case behaviour and have a result that tells you nothing about any input that you are likely to need the algorithm for.

The highly ingenious idea of Spielman and Teng (at least I think it was their idea — certainly, they were the ones who got it to work) was to mix worst-case analysis and average-case analysis as follows: you take an arbitrary input (that is the worst-case part) and randomly perturb it (that is the average-case part) and prove that with high probability the algorithm runs in a time that is polynomial in the size of the input, the dimension, and the reciprocal of the amount by which you perturb. (This is the variance of a Gaussian, though more recently Tao and Vu have shown that the result holds for a much wider class of perturbations.) So we now have a beautiful and conceptual explanation for the success of the simplex algorithm.

I’m trying to be a bit more concise now, especially given that I am still on day one of the ICM. So I’ll finish by saying that Spielman has also proved a result that I found out about while writing my smiley-complexity conversations: there is an error-correcting linear code that has a positive rate, corrects a positive fraction of errors, and can be encoded and decoded in linear time. That was joint with Michael Sipser. If you’ve heard of tornado codes, that is Spielman too (with Luby, Mitzenmacher and Shokrollahi). Finally, he has worked on fast algorithms for solving systems of linear equations — which was the topic of his talk the next day. Here he has found almost linear-time algorithms for several important classes of equations.

Gil summarized Spielman’s achievements by describing them as a beautiful interface between theory and practice. And that is quite obviously correct: all the results are deeply rooted in the need for fast algorithms, and they all turn out to involve mathematics that is extremely interesting quite independently of the applications.

The first thing that stood out when H-T Yau got up on to the stage was his relative youth. (I’ve just looked him up and he was born in 1959.) He began with an amusing quote from von Neumann, who advised Shannon to use the word “entropy” on the grounds that “Nobody knows what entropy really is, so in a debate you will always have the advantage.” Part of the reason von Neumann said that was that there has always been a tension between the irreversible nature of entropy and the reversibility of the Newtonian mechanics that is supposed to underpin it. How can the two be reconciled? My impression is that this quaisi-philosophical problem has largely been sorted out (so in particular, I’m not about to say that Villani has “solved the mystery of entropy” or something like that). In fact, let me reproduce Yau’s list of Villani’s three major achievements.

1. He established a rigorous connection between entropy and entropy production. (I don’t actually quite know what he meant by this.)

2. He established entropy as a fundamental tool in optimal transport, and curvature in metric spaces.

3. He rigorously proved a phenomenon known as Landau damping, a very surprising decay of the electric field in a plasma without particle collisions (and therefore without entropy increase).

I’ve just looked at Tao’s post on the Fields medallists and my understanding is such that I’m not even quite certain which of the above three achievements he is describing in detail. (That’s a comment about the headings — Tao writes with his usual clarity.)

I’m not going to try to explain Villani’s work beyond this. Let me just mention a few random things from what Yau said, and some even more random thoughts that I had during the talk. One of the latter was that amongst the other mathematicians Yau mentioned were Cergignani, who conjectured that the decay to global equilibrium of, I think, solutions to the Boltzmann equation is exponentially fast, Toscani, who proved with Villani that this conjecture is almost always (in a certain precise sense)correct (which was interesting as there are counterexamples due to Bobylev and Cergignani himself), and Gualdani, whose role in the story I did not write down and have forgotten. Could there be a pattern here?

Here, just to give you an idea of what being at the talk was like, is another note I wrote: existence of renormalized solution … other stuff … slide too quick.

I think I’ll finish this short post with a summary that gives some idea of why Villani’s results (some proved with Clement Mouhot) about Landau damping are considered so spectacular. They are the first rigorous results to establish fast decay to equilibrium in confined collisionless time-reversible dynamics.

There was also an interesting discussion about a function — which, looking at an earlier part of my notes, probably should in fact be the Boltzmann H-functional (whatever that is). Apparently, it carries all the information of the initial data for all time, which might sound hard to reconcile with fast decay to equilibrium, but the point is that it pushes this information to higher and higher frequencies. (I’m mentioning this as another example of how it is possible for a sentence that one doesn’t understand at all well nevertheless to create a mental picture that provides some help when thinking about an unfamiliar subject.)

One other point that was strongly emphasized was that Villani has been an inspiration to a generation of younger mathematicians. You can get some idea of why this might be by visiting his home page, which includes a link to informal presentations of his research. It also includes a statement that becoming, at a remarkably young age, director of the Institut Henri Poincaré will not stop him being an active researcher.

Based on what I’ve seen from his home page and what I hear about his interactions with younger mathematicians, I can’t help thinking that Villani is a blogger who just doesn’t realize it yet. Cédric, if you’re reading this, please start a blog. Post as frequently or infrequently as you like (as long as it’s a non-zero amount). It would be great to have somebody in your area to tell the rest of us about it, not to mention your general perspective on mathematics: you would be guaranteed a large and enthusiastic readership.

Next, Kesten shuffled on to the stage. He has an unusual face, in that he has a white beard of the kind that looks as though it is never trimmed — indeed, I think that is probably the case, given the way it grows out sideways as well as down — and looks slightly fake, to the point where one cannot help imagining what he would look like without it, to which the answer is that he would probably look a lot younger as the hair on the top of his head is black. (As I write this, in a large room with dozens of terminals, he has just walked in.)

He began by telling us that Smirnov had got perfect scores in the International Mathematical Olympiads in 1986 and 1987, just in case we were in any doubt about his mathematical talents. His next remark came as a very pleasant surprise: even since the committee had made its decision — in fact, in the last two months — Smirnov had proved a major result. Let me begin by saying what that was.

A self-avoiding walk is a path in a graph that never visits the same vertex twice. (I suppose that is what a graph theorist would just call a path, but here we are thinking of random walks that are conditioned on avoiding themselves.) Self-avoiding walks lead to some of the most fascinating open problems in mathematics, since (i) much of their behaviour is extremely well-understood and (ii) very little of this understanding is rigorously proved. For example, it is known to physicists that a typical self-avoiding walk in of length has end-to-end distance about but nobody has rigorously proved an upper bound of for any and even more remarkably, nobody has proved a lower bound of even (I’ll leave it as an exercise to see that the “obvious counting argument” doesn’t work, even though the idea of its not working is fairly preposterous.)

One thing it is easy to show is that the number of self-avoiding walks of length starting at the origin is of the form where is a function that grows subexponentially. Equivalently, if is the number of walks of length then tends to a limit (Sketch of proof: it is easy to see that for all and and it is a general fact that submultiplicative functions have the desired property.) The constant is called the connective constant of the lattice on which the walk is taking place.

In theory, you can work out the connective constant to any desired accuracy by working out what is for larger and larger However, in practice the calculation gets pretty big pretty quickly. Exact values of have not until now been discovered, but Smirnov and his former (I think) student Hugo Duminil-Copin have proved that the connective constant of the planar hexagonal lattice is Apparently the result itself was the predicted answer, and it had been shown that was an upper bound, but proving the opposite inequality was much harder. Where does a strange number like come from? This may be obvious to some people but it wasn’t to me. Fortunately, I bumped into Smirnov later and he told me it was When I told him it wasn’t, he went very pale indeed …

Actually, that’s not true. He corrected himself and said As I think about it, I see that even that is false, but that makes me not quite sure that that is what he said. More likely, it is closely related to in some way. That’ll be a nice problem to work on if I’m short of something to do during a boring talk. (Incidentally, the talks I’ve been to so far — I’m writing this before the first talk on Sunday — have not been boring at all. I’ll try to write about some of them in due course.)

I should add that even in cases where physicists don’t know the connective constant they can still tell us the extraordinary fact that the right behaviour of is Fascinatingly, the is independent of the lattice, and in fact independent of a whole lot more — basically, any model of self-avoiding walks that is even remotely reasonable leads to this term. This is the mysterious phenomenon of universality. One of the holy grails of mathematics is to prove universality, which basically says that if you stand back from a self-avoiding walk so that the mesh of the lattice is too small for you to see it, then you will not be able to tell what the model is. Universality appears in many other contexts too, and non-trivial universality results are always hugely interesting. (The central-limit theorem can be viewed as such a result. And if you think about it, it is remarkable that a random walk in should have a distribution that, in the large scale, is rotation invariant, which is just one small consequence of universality.)

I said that hearing about this result was a pleasant surprise. I’ve explained the surprise part, I hope. The pleasantness was simply that as a member of the committee one wants reassurance that one has made the right choices (to the extent that the notion of “right choices” makes any sense, which is an important qualification). Part of the point of the medal is to reward promise, so I greet with grateful amazement the fact that Smirnov has been fulfilling his promise in a big way even before the ICM. (I’ve often wondered how the members of the committee that chose Witten felt when the Seiberg-Witten invariants burst on to the scene. Up to then there had been some criticism of the choice, on the grounds that Witten did not tend to publish formal theorems. Afterwards, the critics were silenced.)

I’ve got to get to David Aldous’s plenary talk, so I’m going to speed up. The other highlights of Smirnov’s mathematical output are that percolation on the triangular lattice has a continuum limit that is conformally invariant (which then has amazing consequences thanks to the work of Lawler, Werner and Schramm). See Tao’s blog post for more on this. And more recently Smirnov has proved conformal invariance for the Ising model in the plane — another truly remarkable result. And if I understand correctly (this certainly seems to be claimed in Julie Rehmeyer’s account) he has proved universality in this case, jointly with Dmitry Chelkak.

In case you are not familiar with it, the Ising model is a model for the behaviour of arrays of magnetic particles. There is a tendency for these particles to want to align with each other, but there is also a “temperature” parameter that goes in the opposite direction. (One can think of it as follows: the more the particles are vibrating, the less strong is their tendency to align.) To model this, one takes a grid of numbers, each equal to 1 or -1, and associates with it an energy, which is the number of neighbouring pairs of numbers that are different. Call this number One then chooses a parameter and defines a probability distribution on the set of all possible assignments of 1s and -1s, in such a way that the probability of any given assignment is proportional to To understand this, it is helpful to look at the extreme cases. If then all probabilities are the same, so we have the uniform distribution, and there is no tendency for neighbouring signs to be the same. This corresponds to the case of infinite temperature (and indeed, the temperature is thought of as ). If is very large, then the probability is very heavily weighted in favour of low-energy configurations, which means that one expects to see big areas of 1s and big areas of -1s. For intermediate low-energy configurations are also heavily favoured, but this is compensated for by the fact that there are far fewer of them, so a typical configuration will not obviously have low energy — whether it does depends on the value of And there is a critical value of where the system changes from having big patches of 1s and -1s to being much more random in appearance. The behaviour of the Ising model near the critical probability is particularly interesting, and exhibits the kind of conformal invariance and universality that gets people excited. Up to now, we have “known” this without actually knowing it. Thanks to Smirnov and his collaborators, we know it.

More on Ngo.

I received an email last night from Kartik Prasanna, who was a graduate student in Princeton when I was there as a visiting professor from 2000-2002 and is now at Ann Arbor, with an answer to Assaf Naor’s question about what the Langlands programme, if successful, would tell us about more down-to-earth matters such as solutions to Diophantine equations. With his permission, I reproduce his very interesting thoughts. (I don’t understand all the details, but the general points are made very clearly and cogently.)

[I] felt compelled to write in to respond to the question that Assaf Naor raised about whether the Langlands program is useful in any way in understanding Diophantine equations. Broadly, the answer is, yes, it should provide some basic tools to do so, but there is significant work required beyond ….

To describe what might be involved, it’s best to look at one concrete example where fantastic progress has been made – that of the Birch and Swinnerton-Dyer (BSD) conjecture for elliptic curves over the rationals of analytic rank less than or equal to one. (I’d say is as concrete as you could get !) In this case, the basic conjecture, namely that the analytic rank equals the algebraic rank is known to be true. The proof itself is a combination of many remarkable results, the main landmarks being (not in chronological order, so I’ve added the years these results were roughly proved ):

1. (1994) The theorem of Wiles ( and Taylor-Wiles, Breuil-Conrad-Diamond-Taylor) that elliptic curves are modular. This tells us that the p-adic Galois representation associated to the Tate module of an elliptic curve E is isomorphic to the Galois representation coming from a modular form for a particular congruence subgroup of In particular, this Galois representation occurs in the cohomology of an associated modular curve where is the so-called conductor of the elliptic curve ( a measure of its bad reduction.)

2. (1982) The theorem of Faltings on the Tate conjecture for divisors on a product of two curves, one of the results for which Faltings got a Fields medal. (He proved something more general, and also the Mordell conjecture in the same article.) This theorem implies from 1 above that there is an actual geometric map

of algebraic curves over the rationals, that is defined over the rationals as well.

3. (1984) The theorem of Gross-Zagier. They look at certain specific points on constructed using the theory of complex multiplication – the so-called Heegner points, and study the images of these points under the map Roughly what they show is that when the analytic rank is 1, then the image of a suitably chosen Heegner point is nontorsion, by proving a precise formula relating the derivative of the L-function to the “height” of the point. This implies that the algebraic rank is greater than or equal to 1, which equals the analytic rank.

4. Waldspurger’s theorem (1980) on nonvanishing on central values of L-functions of quadratic twists for modular forms on GL_2. This is a key ingredient in proving nonvanishing of the Heegner point above.

5. (late 80′s) The work of Kolyvagin on Euler systems that proves the reverse inequalities in the case of analytic rank 0 and 1.

What role did automorphic forms and the Langlands program play in this ?

(a) Certainly, a very important role in 1. For instance, the starting point for Wiles’ work is the Langlands-Tunnell theorem on modularity of certain Artin representations that uses Langland’s theory of base change for a particular case of the general Langlands’ conjectures.

(b) Waldspurger’s result is based on a deep study of automophic forms on and their transfers to metaplectic groups. Interestingly, this is not part of the original Langlands’ conjectures, since metaplectic groups are not algebraic. But there are close connections nevertheless.

(c) Most of the above can be generalized to the case of elliptic curves over a totally real field F. In this case, step 1 (due to Skinner-Wiles, Fujiwara etc.) would produce a Hilbert modular form, which under a suitable hypothesis admits a “Jacquet-Langlands transfer” to an automorphic form on the multiplicative group of a quaternion algebra B that is split at precisely one infinite place of F. The associated “Shimura variety” is actually a curve, which I will call X. Then Faltings’ theorem says there is a map

as before. Shouwu Zhang (around 1999) showed the analogs of 3 and 5 in this context. Again the Langlands program played a crucial role, in allowing one to move our modular form to a different group, namely the multiplicative group of the quaternion algebra B, where the geometry of the associated Shimura variety is simpler and particularly well adapted to constructing rational points.

You might note that the cases of the Langlands program used here were all those proved many many years ago. Also, while it provides some key inputs and basic tools, one needs to go significantly beyond what is predicted by the Langlands program in order to understand Diophantine questions. For instance, one of the key themes in the work of Wiles is the study of the INTEGRAL structure of Hecke algebras – these appeared in your post. One might say that the Langlands program is about understanding the eigencharacters of the Hecke algebra – in other words the structure of the Hecke algebra tensor Q – but it doesn’t say anything about their fine integral structure, the study of which requires understanding CONGRUENCES between modular forms. This study of congruences is in a sense one of the main themes of Wiles’ work, that led to the proof of 1.

Going forward, one might ask: what Diophantine questions might one study and what role will the Langlands program play ? A big open problem is of course the BSD conjecture for curves of analytic rank greater than 1. Another is possible generalizations to higher dimensional varieties. The analog of the BSD conjecture is the Bloch-Beilinson conjecture that predicts that ranks of Chow groups of homologically trivial cycles should be related to orders of vanishing of L-functions. These are difficult questions, but there are reasons to believe that progress on them will require some analogs of steps 1-4 above. Namely, let’s say one is interested in studying algebraic cycles on some variety V. Very speculatively, one would need:

1′. Modularity results – showing that under suitable conditions, the Galois representations associated with the cohomology of V come from automorphic forms that live on Shimura varieties. (This would only work for varieties closely related to Shimura varieties.)

2′: The Tate conjecture ! (for the product of the variety V and the Shimura variety X of part 1.)

3′: Studying special cycles on X and their relation to derivatives of
L-functions.

3”: Finally, study the cycles on V that one gets by correspondence via the Tate cycle of part 2′.

4′: Nonvanishing results for twists of automorphic L-functions.

5′: Some analog of the Euler system argument, which I cannot even begin to imagine …..

What is likely is that the Langlands’ program will provide some key basic tools in trying to understand these questions. However, the point I want to make is that as before, one needs to go SIGNIFICANTLY beyond the Langlands program to understand the rich arithmetic of Shimura varieties and their associated Diophantine geometry. So even if one assumed all the Langlands conjectures, it would just be a starting point. Nevertheless, if one doesn’t have the basic tools that are provided by the Langlands program, one cannot even begin in most cases.

By the way, there is all kinds of interesting work going on, especially on steps 1′ (eg. Taylor and his students) and 3′ (eg. Kudla and his collaborators, Shouwu Zhang and his students.) There is even a notion of an “arithmetic fundamental lemma” – see the paper of Wei Zhang by the same title on his webpage:

http://www.math.harvard.edu/~wzhang/

There is also lots of interesting related work from the p-adic side that would take too long to describe !

Best regards,

- Kartik

Before I continue with brief descriptions of the laudationes, let me mention that Julie Rehmeyer has written descriptions of their work for a general audience and Terence Tao has now posted about the work of the Fields medallists and the other prizewinners. And as I have already said, the ICM website has links to the full texts of the laudationes themselves. So anybody now wanting to understand the mathematics has an excellent starting point, and I am free to concentrate on the more frivolous details of the talks, perhaps slipping in the odd mathematical comment as I do so.

Jim Arthur went next. His was the terrifying task (though much less terrifying for him than for most) of explaining the work of Ngô Bảo Châu to a general mathematical audience. I’d say that he did about as well as it is possible to do, which meant that he was able to convey some of the flavour, but obviously without managing to transmit to the non-expert the sort of wisdom tht it takes the experts in this particular area years to accumulate.

Ngô’s big result is a proof of the so-called Fundamental Lemma, conjectured by Langlands. Not bad to get a Fields medal for a lemma, you might think. The story here is that Langlands, while working out his famous programme, recognised the need for this lemma, and thought that it would be reasonably straightforward to prove. However, it turned out that he had wildly underestimated its difficulty. As Arthur put it, what Langlands was seeing was the visible part of the iceberg, and to prove the lemma it was necessary to uncover and understand the iceberg in its entirety. (I can’t remember his exact words, but he did not use the phrase “tip of the iceberg” and definitely did talk about icebergs.)

Arthur then gave a general description of the Langlands programme (having apologized in advance that much of what he was going to say would be “murky”). After the laudationes I found myself having coffee with Assaf Naor and Irit Dinur. (If you haven’t heard of them, they are both fabulous mathematicians, and both speaking here. In fact, Irit has just given her talk, the theoretical computer science plenary lecture, about the famous PCP theorem, of which she has a famous new proof.) The conversation turned to the topic of how many Fields medals could in theory be given for advances in the Langlands programme. My view was I suppose the official line, which is that it is such a deep and difficult area that any major advance is huge news, though I couldn’t resist a joke comparison to pole vault records, where people who are in a position to beat them deliberately don’t beat them by much because you get big money for beating world records. (I’m not seriously suggesting that somebody who had a proof of all the Langlands conjectures would sit on it, or release it only gradually.) Assaf (and I hope he won’t mind my making his views public) was more sceptical, maintaining that all mathematicians have their icebergs to explore and that the Langlands programme was not as unusual in this respect as perhaps it is sometimes conveyed as being. He said that he likes to ask the experts whether if they could assume all the results they wanted that are currently conjectural, they would know more about any concrete Diophantine equations. Apparently they don’t particularly like this question. Whether it is an appropriate criterion to judge the area is of course a matter for debate. In fact, that is what prompted me to say that perhaps the iceberg was the true and fascinating object of study in that area. I didn’t think of saying it at the time, but after a while there is not much interest in solving more and more Diophantine equations (not that Assaf was claiming that there was), and attention must turn to more global phenomena somehow. Perhaps that is what algebraic number theory is. I’m not sure why I’m musing on this at such length, but one more thought is that the question, “What is the most general statement of which Gauss’s law of quadratic reciprocity is a particular example?” is an obviously entirely valid and interesting one, and if I understand correctly, one of the Langlands conjectures is more or less a proposed answer to it.

I don’t understand what an automorphic form is, but there are levels of non-understanding (I would be enjoying several deeper ones later in the talk) and Jim Arthur lifted me to a slightly higher one — by which I mean that I had a slightly better idea what automorphic forms were after the next section of his talk. Before, I just thought of them as particularly nice kinds of functions that number theorists liked, and often mentioned in the same breath as modular forms (which I understand slightly better but still by no means fully). Anyhow, automorphic forms are eigenforms of natural operators on arithmetic symmetric spaces. He then said that these natural operators were Hecke operators, which themselves were Laplace-Beltrami operators on … er … I can’t remember. Hang on, we’ve got some spaces around — those symmetric spaces — so that’s OK.

What does one get out of a portion of talk like that? That is, what does one get out of hearing one concept one does not understand explained in terms of others? Let me try to say in this case. I don’t know exactly what an eigenform is but I presume it’s an eigenvector (and in fact he described them as simultaneous eigenvectors, so perhaps they were simultaneous eigenvectors for all Hecke operators — hmm, not sure about that). He talks about natural operators, which is obviously not meant to be precise and can therefore be understood in a non-precise way. Then he said “arithmetic symmetric spaces”. I don’t know what those are, though I imagine they are one of those definitions that is rather simple when you finally get told it. (I had that experience with algebraic groups, objects that I was afraid of until I learned that they were just groups where the set and the group operation are defined by means of polynomials.) I happen to know that a Laplace-Beltrami operator is what you get when you ask what the right analogue of the Laplace operator should be for a function defined on a manifold. (These last two definitions I know only as a result of editing the Princeton Companion to Mathematics, which forced me to pick up quite a lot of this kind of general knowledge.) And I’ve heard Hecke operators mentioned numerous times without ever actually finding out what they are. As a result of all that I now know that automorphic forms are eigenfunctions of operators that come up in a nice natural way in a number-theoretic context and that relate to all sorts of buzzwords I’ve heard many times. That doesn’t tell me exactly what an automorphic form is but it is non-trivial information. (What are they good for? There I cannot say anything that’s worth saying.)

Anyhow, the Langlands programme is about connecting automorphic forms with representation theory and looking at objects called automorphic representations. The difficulty of the area is this. One has some nice concrete operators (the Hecke operators mentioned above) and would like to know about their eigenvalues. However, just because an operator is concrete, it doesn’t mean you can write down its eigenvalues, and in this case you can’t. However, what you can hope to do is relate automorphic representations for different groups to each other, and this, if you manage it, gives you very deep reciprocity laws.

There’s something else called the principle of functoriality, which I won’t attempt to describe here even vaguely. Jim Arthur said, “The principle of functoriality awaits the efforts of future Fields medallists.”

The slides were getting more and more difficult to get anything out of by this stage, and I think I won’t say very much more. But Arthur gave us some idea of why the Fundamental Lemma has so many interesting consequences, and then started to explain what was so remarkable about Ngô’s proof.

If you want to impress your friends, here’s how to pretend you understand the proof in detail. If someone asks what his main idea was, you can reply, “Well, his deepest insight was to show that the Hitchin fibration of the anisotropic part of the trace formula is a Deligne-Mumford stack.” If that doesn’t do the job, then try to drop the phrase “perverse sheaves” into the conversation — they are relevant apparently. If you want to show that you have a broad view, then you could also say that Ngô very remarkably used global methods such as Hitchin fibrations to prove a local theorem. If you’re looking for a single amazing idea, then probably the use of Hitchin fibrations was it. Finally, here’s a list of names to splash about: Goresky, Hales, Kottwitz, Langlands, Laumon, MacPherson, Shelstad and Waldspurger. (This is apparently a far from complete list of the people on whose work Ngo builds.) A final summary from Jim Arthur: Ngô’s work opens up automorphic forms to some wonderful applications.

After the unceremonial closing of the opening ceremony it was lunch time. I soon found myself in the first of what would turn out to be many queues of the kind where the optimal strategy is far from obvious but obviously not very good. One of the army of volunteers (the males of whom were wearing smart purple Indian shirts — collarless and going down to the thigh) told me to go up a floor, so I did, and I found a number of parallel queues. There was also a borderline-legitimate queuelet round to the side, and I joined that, hoping that it was legitimate enough not to annoy people and not too far to the side to get the attention of the people serving lunch. Lunch was basically an Indian takeaway — a choice of various Indian dishes served in an aluminium tray and a white cardboard lid that was rectangular apart from being curved off at the vertices, and held in place by a fold at the top of the aluminium. (I’m not certain it was aluminium but that’s my best guess.) After about 15 minutes of anxious waiting I was in a position to ask for lamb biryani, which I had also had for breakfast. It cost me two coupons from my kit bag, and came with a small pot of yoghurt, and the option of a fierce looking chutney, which I took. (I was about to say “took with relish” but then realized that to some people that would be ambiguous.) I was told that if I wanted to sit down I could go into the gallery of the main hall, so I did. A table would have been nice, but I could manage without.

The lamb biryani was slightly disappointing in that it had just one piece of lamb which, though large, was about 80% bone. That left quite a lot of rice to get through, and I was glad of the opportunity to spice it up with the chutney. For what it’s worth, we were provided with small wooden disposable spoons and forks to eat with. The chutney passed a basic test: it made my nose run.

After I’d finished that I wandered about and accidentally found myself in a room where there was a press conference with the new prizewinners. Nobody seemed to mind my standing there at the back of the room (and I wasn’t the only one, though it wasn’t clear whether anyone else was there quite as randomly as I was). Spielman was in the middle of a spiel about codes and smooth analysis, which I’ll discuss a bit later. He was obviously extremely articulate in a way that makes me look forward very much to his talk.

When he had finished, Alex Bellos, a British mathematics popularizer and journalist (author of the recent Alex’s Adventures in Numberland, which he was forced to call Here’s Looking at Euclid for the US edition) asked two questions: what did the prizewinners think about the 40 age limit for Fields medals and the Nevanlinna prize, and did they believe in the distinction between pure and applied mathematics?

The answers were interestingly uniform. Yves Meyer said flat out that there was no distinction any more between pure and applied mathematics, which for someone working in the areas he has worked in is a very natural view to hold. He said that in the 16th century Montaigne, aged 40, had described himself as entering old age, and then pointed to Nirenberg, still active at 85, as a demonstration that the world has changed a lot since then.

Spielman basically agreed with Meyer. Lindenstrauss came nearest to disputing the claim that there was no pure/applied distinction (but in a context of having said that there wasn’t one) when he drew attention to the point that mathematics should not be judged by its immediate applicability. To his great credit, he didn’t wheel out the example of Hardy and the RSA algorithm. He also mentioned that Marina Ratner had proved her big theorem aged over 50.

Smirnov agreed that the boundary between pure and applied was blurred. (I much prefer this way of stating it to saying that there is no distinction. I think there is a distinction, one that can sometimes even be useful, but obviously I agree that the boundary is blurred. In that respect it’s a bit like the distinction between left wing and right wing.) He also mentioned applications to biology.

Nirenberg marvelled at how different parts of mathematics influence each other. On the age question he said, “I’m still trying.”

Villani said he didn’t have much to add as he agreed with everyone else. And I couldn’t hear Ngo Bao Chau’s answer.

After that I wandered out of the press conference again.

I got to the laudationes a little bit early to be sure of a good seat. I have, annoyingly, reached the age where my eyesight, which was previously extremely good, has started to go. Even more annoyingly, this was predicted by my optometrist in my last eye test but one. She said, “You’ll need glasses next time,” and went on to explain that she was saying that purely on the basis of my age. I felt as I might have felt if I had been told, “You’ll find that although you continue to prove theorems, they won’t be as interesting any more.” But she was right. (I hope, however, that the analogy breaks down right there …) I now have a pair of reading glasses, but I’m not in the habit of using them.

I’ve got them in India, but I hadn’t taken them with me, and was to be punished for it, since what I’m bad at is changing rapidly from looking at things that are close to things that are at a distance, which I had to do in order to listen to the laudationes and take notes on them at the same time. But I’m getting ahead of myself here.

I got my good seat, and then sat, and sat, and sat. The talks were due to start at 2. Somehow when nothing had happened by 2.05 I got a bad feeling about it, not so much because it was five minutes after the scheduled start time but because there didn’t seem to be any pre-talk activity — things like the president of the ICM up on the stage milling around talking with other very important people. At 2.20 there was an announcement: “Is Harry Kesten here please?” From where I was sitting, the answer appeared to be no. But even now I’m a little mystified because Kesten was on third, so his absence was not a good reason for delaying proceedings. Some canned music, which had stopped for the announcement, started up again. I had quite liked it at first — sort of Indian/jazz fusion — but it was on a cycle, and the third time round I was less keen.

Finally Jacob Palis, who was IMU president at the 1998 congress and was chairing this session, got up on stage, the music faded, there was a pause, and Palis said a few words … honour to chair session … writing names in history of mathematics … Ramanujan … and it was time for the first laudatio.

This was Furstenberg talking about Lindenstrauss. The full text can be found here so instead of trying to summarize the talk I’ll try to summarize my experience of the talk.

As Furstenberg climbed up on to the stage, there was a smattering of applause — why just a smattering I couldn’t understand. He fished out some papers, hunched a little over his laptop, looked puzzled, didn’t say anything for just long enough to get us worried, then started. He said that Lindenstrauss’s main achievements were in number theory and dynamical systems, in particular the progress on the Littlewood conjecture and on the solution of the quantum unique ergodicity conjecture of Rudnick and Sarnak. He then said, “I was expecting some of this to go on screen.” Eventually it did.

Furstenberg always speaks at a measured pace, and I was beginning to admire just how well-chosen his words were, but when his slides started working it was revealed that he was reading from them. This is perhaps a natural interpretation of the instructions to submit one’s talk in advance of the proceedings, and Furstenberg was by no means the only person to do it. But I think if I were organizing the next ICM I would instruct speakers to prepare slides that were distinct from, and much more schematic than, the full articles. However, if you want to, you can at least now find out exactly what Furstenberg said in his talk. One memorable quote was, “If it can happen, it will happen.” This is supposed to convey the philosophy of ergodic theory. (To be strictly accurate, he qualified it with the words “approximately, at least”.) As an example (this doesn’t come from Furstenberg’s talk), if you take a pair of real numbers and look at its multiples mod (equivalently, if you repeatedly translate the torus by ) then the closure of the orbit will consist either of a finite set of points (this happens if and only if some multiple of belongs to which happens if and only if both and are rational), or a closed curve in the torus (this happens, for instance, if and are irrational but their ratio is rational, which forces the multiples to lie on a line that goes through an integer point, and therefore forces their reductions mod 1 to lie on a curve that looks like a finite union of line segments if you draw it on the unit square), or the entire torus (this happens if and are irrational and independent over ). In each case, one can argue that there are certain obvious restrictions you can place on the orbit, which confine the orbit to some “nice” set, and then the orbit itself is equidistributed in that nice set.

This turns out to be a very simple example of a very general and important story. I am not competent to tell that story, but fortunately Terence Tao has blogged on it. (That is not the only post of Terry’s on that topic: another I would recommend is this one. More generally, you can click on promising tags such as “Ratner’s theorems” and get a list of relevant posts.)

I’ve got lots of notes on the talk, taken before I realized that the whole talk would be available online. But I think Furstenberg has done a beautiful job, so there really isn’t much point in my providing a different and worse version, especially as his full text is short. I’ve just noticed one thing that I can add to it. Towards the end, Furstenberg mentions that Hecke operators, which came into the work on the Littlewood conjecture, also come into Lindenstrauss’s solution of the QUE conjecture. In the written version Furstenberg just states this, but when he gave the talk he emphasized that it was very surprising that Lindenstrauss’s methods were applicable in this different-looking context. I feel this is an important point — one wants to hear words like “very surprising” or “technical tour de force” in a talk of this kind.

Perhaps I should also make clear that Lindenstrauss’s work is about groups that do not satisfy the conditions for Ratner’s theorem, and concerns hyperbolic systems, which Ratner’s theorem does not deal with. (I may have made that last statement too general, but in any case the area that Lindenstrauss works in is the area of groups where Ratner’s theorem breaks down but conclusions of a similar type still seem to be valid.)

Last night, I realized that my sleep strategy for the previous night had not been even close to optimal: I had had too much sleep on the previous night so had a bout of insomnia (which I normally never suffer from) last night. So now I’m back to feeling jet-lagged. I promised I’d be in bed by midnight and it’s now nearly quarter past, so the remaining laudationes will have to wait.

I’d got up to the awarding of the Nevanlinna prize to Dan Spielman. Next up was the Gauss prize. Yves Meyer came up on stage with a dark blue jacket and dark grey trousers (both dark enough that you had to look hard to see that they didn’t form a suit). We were told that he had “created a new way of multiresolution thinking,” a conclusion that would be hard to dispute. He had a grey beard and moustache and a vigorous handshake. This was the second ever Gauss prize, the first going to Ito in Madrid in 2006.

An even newer prize followed, the first award of the new Chern prize for lifetime achievement. This is an interesting prize in that it comes with a lot of money — half a million dollars (some of it from Chern’s family and some from the Simons foundation, about which more later) — which is split 50-50 between the recipient and good mathematical causes nominated by the recipient. I wonder if we will get to hear how Nirenberg decides to spend the charitable half. (Update: I’ve just discovered on the web that he’s giving it to the Courant Institute.) Nirenberg had white hair, beard and moustache, and did not smile.

After that was all over, the president (of India, not the IMU) told us once again what the ICM was, but after that unpromising start she moved into a speech about India’s mathematical heritage and various other topics, all discussed in a way that made it clear that somebody — I presume not her — knew what they were talking about. She told us of an old Sanskrit saying, “Mathematics stands at the helm of all sciences.” I think I prefer the “queen of” metaphor that is more prevalent in the west. She told us that the concept of zero originated in India, and that calculus was anticipated in India in the 15th century. I wondered before the opening ceremony started how many times Ramanujan would be mentioned. There was a mention here, and a few others, but I forgot to count. At one point the president referred to India’s rich cultural heritage twice in successive sentences. There was plenty about the impact of mathematics in technology, economics, cultural life — you get the idea. But this was a pretty good speech as such things go, and the president seemed intelligent, and young for her years.

Rajat Tandon, one of the main congress organizers, got up and gave a vote of thanks. I’ve written that he looked a bit like a guru, but more academic. I can’t quite remember what prompted that. Anyhow, the president then left, which meant we all had to stand again, and to listen once more to the national anthem, which once again ended with the curious modulation to the subdominant. And then the big doors opened, the white car was there — in fact, the arrival of the president was basically reversed.

Well, that’s it, you might think. But Lovász quickly got up to tell us that it was not it. He asked us to bear with him for some traditional functions, by which he meant things that were traditionally done at ICM opening ceremonies. He started by commemorating some notable mathematicians who had died since the last ICM: Henri Cartan (who, amazingly given that he was born in 1904, died only in 2008), Vladimir Arnold (1937-2010) and Kyosi Ito (the aforementioned Gauss prize winner, 1915-2008). Then Lovász “revealed” the programme committee (inverted commas because the names were in the programme booklet), which included Terence Tao amongst others. (I feel that on a mathematics blog it is appropriate to single him out, but if you are interested, then I’m pretty sure all the names can be found on the web by now.) I’ve mentioned a couple of things that he went on to announce: that Ingrid Daubechies will be the next president of the IMU and that the next ICM will be in Seoul. One other thing he told us was that the IMU will have a permanent office in Berlin. There has been some debate about whether there should be a permanent office at all, and if so where. We shall see how it works, but from a purely selfish point of view I’m glad it’s in Europe.

We were then told who would be giving the laudationes. We were told that there would be a one-off prize, called the Leelavati prize, for the popularization of mathematics, to be awarded at the closing ceremony. And we were reminded of the winners of the Abel and Ramanujan prizes since the last ICM.

A supremely bathetic moment followed: the opening of the Hyderabad Intelligencer. Lovász was handed a copy of this publication, wrapped up, and had to unwrap it in front of us. Now unwrapping is sometimes a very straightforward process, and sometimes it is a bit on the fiddly side. Unfortunately, this particular parcel fell into the latter category, the situation made worse by the fact that Lovász didn’t want to tear the paper. But eventually his need to finish the process overtook his wish to preserve what he described as “this beautiful paper” so he ripped it up more vigorously. He then showed us the back and the front (which we’d all seen, since we had each been given a copy in our kit bag), thereby finishing a ritual that I don’t remember from previous ICMs and wouldn’t mind not seeing at future ones.

Next up was Martin Grötschel, who wanted to tell us about the work of the IMU. I was expecting this to be very dull, but in fact it was extremely entertaining. How was that possible? Well, he talked for a while about the work that the IMU has done on citation statistics, and came up with the memorable quote that “Impact factors are not statistics but game theory.” There are some depressing anecdotes about the behaviour of some journals that explain this statement, though he didn’t tell us about them. He told us of the huge amount of work that has been going into the IMU web page, much of it voluntary. For example, now you can find a list of all speakers at all ICMs, and there is a new page (which I’ve mentioned briefly already) with all the proceedings of all the ICMs, in a searchable format. To demonstrate the latter, he got up the page and typed in Hilbert. That gave a list of Hilbert articles, the second of which was the famous 23-problems article. He clicked on that, and said, after a pause, “Now I have to subscribe to Adobe.” Unfortunately, he had tested the system on a different computer. But, miraculously, he sorted that problem out in real time (without subscribing to Adobe I’m pretty sure), though he also told us that he had a fake copy as back-up, and a scan of the first page of the famous paper was there for us to see (and the rest was available too). To get to this, type ICM on the IMU web page. (Update: here is a link to the relevant page. Many thanks to Kevin O’Bryant for finding it and letting me know about it — the page was harder to find than I realized.)

Finally, M. S. Raghunathan, who had been elected (by acclamation) president of the congress, got up for the closing of the opening ceremony. (That’s actually what they said. I suppose another of his duties will be the opening of the closing ceremony.) He gave a rather surprising speech, in that he opened with an apology to those who had had difficulties obtaining visas, and then … er … that was it and the opening ceremony was over. Or rather, all over bar the shouting, which consisted in the woman in green telling us that it was over and that we were free to go and find lunch.

That’s all I’ve got time for, as I’m off to hear Smirnov talking about his work. But it’s quite a good stopping point I suppose.

Let me try to give a stream-of-consciousness description of the opening ceremony, by which I mean translate the notes I feverishly took into continuous prose and not do much else to them.

I booked my hotel fairly late in the day, for the obvious reason that if I left it longer, the work needed would be identical but I would have less choice. And so it turned out: instead of staying in the hotel right next to the congress (so much so that you can get from one to the other without going out of doors) I am, as I mentioned in my first post, about 40 minutes away. The disadvantages of this are obvious — I can’t nip back to my room to get something, and I have to worry each day about how I’m going to get to and from the hotel. But the hotel itself is nice, and I quite like getting to know the city a bit rather than being cocooned in the conference area the whole time.

This morning they laid on buses to take people from the hotels to the congress (as they will every morning). I had had dire warnings about traffic, and been told to expect a two-hour journey, which would still have been quick enough to get to the opening ceremony on time but would have left me slightly anxious. As it was, the journey took the usual 40 minutes or so, so I got to the HICC at about 8.30. We had been told to be in our seats by 10.30, so I thought I had a couple of hours to kill. However, this turned out to be a miscalculation on my part.

I decided to use a bit of those two hours to check my email and work on a forthcoming EDP-related blog post. By the time I emerged from that a big queue had formed to get into the main hall, and by the time I got into the hall myself the nearest available seat to the front was a long way back, or not quite so far back but a long way round to the side. The room, I should explain, was a huge box shape, with lots and lots of chairs laid out — not a fancy auditorium such as they had in Madrid or Beijing or Berlin with banked seats. (The non-banking of seats would have been more of a problem had the average height of delegates been greater, and may have been a problem for those delegates unfortunate enough to find themselves behind me.) But it was better than Zurich, where the main hall was also box-shaped and not big enough to accommodate everyone, which left me having to settle for an overflow room with a video link.

A big compensation for being a long way back was that I was near a small group of musicians playing pulsating Indian music. Normally I’m not much of a fan of Indian music, but this converted me to some extent. What was so good about it? Well, the line-up (if that’s the right word) was three people playing instruments that sounded, and to a lesser extent looked, like a cross between a saxophone and an oboe, and then there were two people playing drums. Each drum was roughly cylindrical, with two ends that you could hit, and the drummers had a stick to hit one end with and their other hand to hit the other end with. On the non-stick hand they wore objects a bit like thimbles, except that they were fixed on somehow. They went on every finger apart from the thumb. And with the stick and the hand they played what were obviously very complicated rhythms, which I would have loved to understand but couldn’t. It was obvious that there was a system to them, partly because I know that there is a system, but partly because sometimes one drummer would stop playing and do a counting exercise with his hand. But unlike counting 1, 2, 3, 4, 1, 2, 3, 4 with your fingers, this was counting in a syncopated rhythm with various different hand positions and wonderful jerky movements that coincided exactly with emphases in the drumming. I found it mesmerising, and a great help in filling the two hours or so that I had to spend in my seat. Also helpful were my two neighbours, one a graph theorist from Hyderabad and the other a PhD student in algebra from Chennai. And also helpful was the opportunity my notebook gave me to think about mathematics a bit (in relation to the EDP blog post).

At 10.45, a woman in a green sari began proceedings. I didn’t concentrate at a crucial moment and so never quite found out who she was, but she acted as a kind of master of ceremonies (I don’t know a non-sexist term for that job) throughout the morning.

She started by saying that no statement about India is true or false, except that that statement itself was true. As you can imagine, this went down well with an audience of mathematicians. I haven’t bothered to think about whether that entire statement is true, false or neither. (OK, if we’re being boring about it, it is absolutely true that most of India is further south than most of Pakistan, so both halves of her statement were false. But … oh never mind.) She told us that Hyderabad was a city of 7 million people, that it was the intellectual capital of India, that the Koh-I-Noor diamond was mined nearby (I squirmed a little in my seat at that point), that it is famous for something — I think edible — called something I didn’t catch but it sounded like billani, or did I just think that because of Villani? She ended by asking us to stand for the president of India and remain standing for the Indian national anthem.

Did you assume on reading that that the president of India was a man? I’m sorry to say that I got a surprise when something the woman in green said made it clear that the president of India is in fact a woman. At the front right-hand corner of the hall (which, incidentally, was a lot wider than it was long) some doors opened and right outside them was a fancy white car, out of which the president and her entourage emerged. (I haven’t mentioned, but there was of course heavy security, though in the end it turns out that I could easily have brought my camera. In fact, I could have brought more or less any non-weapon, and the only consequence would have been that I had to pass my bag through an x-ray machine.

The president was short and looked a sprightly 70 or so, but from the distance I was at I could have got that wrong. When she reached her seat, but had not yet sat down, she greeted us by putting her two hands together, pointing upwards, a gesture I was familiar with only from Indian sculptures. The national anthem was, like the previous music, just a tune with drum accompaniment, notable for modulating just at the very end. (To be precise, it was in a very clear E major — to describe it in Western terms — but strangely ended, in even quavers apart from a held last note, with E E F# F# G# G# F# G# A.)

After the national anthem was over came a ceremony to light a lamp (symbolizing all sorts of obvious things). The result of this was that there were four small flames, lit by the president, the governor of Andhra Pradesh (the state where Hyderabad is), the chief minister of Andhra Pradesh, and Laci Lovász, the president of the IMU.

Then started some speeches. The usual challenge on these occasions is to know what to say that isn’t so obvious that everyone else will say it too — the ICM is over 100 years old, is wonderful, as is the host country, as is the particular city in the host country, as is mathematics, etc. etc. The chairman of the organizing committee spoke in this vein but had the advantage of being near the beginning. Then Lovász spoke, also fairly standard stuff but he kept it very short.

Then the chief minister of Andhra Pradesh told us a few things about Hyderabad — that it was a composite culture, a centre of education and research (with 12 universities), rivalling Bangalore as an IT centre, a top place in DNA fingerprinting (also mentioned by the woman in green, so it’s obviously a big deal here). He told us an Indian proverb: one who is good at calculations is a great man. Where does that leave a good mathematician who messes up calculations, I idly wondered as he told us of various mathematicians from Andhra Pradesh, of whom Rao was the most notable example.

Then the woman in green said, “And now the moment you have been perhaps anxiously waiting for.” And perhaps you, dear reader, have too, but if I have kept you waiting for longer than you might have liked, then I will indirectly have conveyed what a typical ICM opening ceremony is like. And actually the wait is a good thing — if it were all over right at the beginning then there is a risk that the announcement of the prizes would be a bit of a damp squib.

Martin Grötschel read the citations and then each prizewinner received a medal from the president and a cheque from Lovász. But first he announced the names of the people on the committee. My neighbours were amused to find that their neighbour was one of them.

Elon Lindenstrauss was the first to be announced. In a piece of not ideal timing (repeated for the later winners) his name appeared on the big screens in the hall before it was spoken, but it didn’t matter too much. A strange noise of obvious approval greeted the announcement (again repeated for the later winners). I can’t quite explain what it was that gave me that impression, but others noted the same.

Lindenstrauss looked a bit nervous. He was wearing jacket and tie, but not a suit, and didn’t quite know where to put his hands. (I have no idea where one is supposed to put one’s hands, so this is not meant as a criticism.) As he was about to receive the medal, he put his hands together in the same Indian-sculpture way, which was either a slightly cheeky joke or something he had been instructed to do. My money was on the latter but I would wait to see whether everyone else did it as well. He then shook hands with Lovász. Since most of these details are the same for all four Fields medallists (in particular the hand gesture was not a joke), I won’t keep repeating them.

Ngô Bảo Châu had on a light grey suit, with fairly baggy trousers, and tie. He was smiling, but in an in-control way. He looked pretty young. He was about a head shorter than Lindenstrauss.

Smirnov had on a slightly lighter grey suit, and had a half smile. He did two quick bows to accompany the hand gesture.

And then the moment I had been anxiously waiting for. Villani was wearing a three-piece suit, dark grey, with an interesting (as in stylish rather than weird) cut, and the sort of cross between a bow tie and a scarf that can be seen in this picture. He, Smirnov and Lindenstrauss were all of a very similar height, which was easy to tell because after receiving their prizes, each winner went to the back of the stage and stood against a wall that was mostly yellow but had a horizontal boundary with a red area at something close to head height. (If you’ve seen The Usual Suspects you’ll have some idea what I’m talking about.)

The Nevanlinna prize was then announced, and now I had absolutely no idea who was going to get it (except that I had heard a possible name mentioned, who turned out not to be the person). It was given to Daniel Spielman, whose name was new to me. Or at least, I thought it was, but when his work was described later in the day I realized that actually I had heard of several of his results and just forgotten the name attached to them. Anyhow, I won’t forget his name now. He had a dark grey suit and a nice natural smile. And he was slightly shorter than the non-Ngo medallists.

I’ve still got the Gauss and Chern prizes to go, and then the rest of the ceremony, and I won’t even have started on the Laudationes, but it’s getting late and I’ve got to get up early. This task is already beginning to feel like an illustration my father once gave me of the nature of infinity: if you write such a detailed diary that it takes a week to write up each day, then you will nevertheless end up writing about every single day. But I’ll try not to finish covering the ICM in mid-September.

Quick update. I’ve just discovered that the handing out of the Fields medals can be seen on Youtube here. Not sure where that leaves my verbal description, but it seems silly not to mention the video. The other prizes are there too if you do obvious searches for them.

The laudationes start in half an hour, so all I have time for is a few headlines (though you will almost certainly have these from other sources).

The Fields medals went to Elon Lindenstrauss, Ngô Bảo Châu, Stanislav Smirnov and Cedric Villani. The Nevanlinna prize was awarded to Dan Spielman. The Gauss prize went to Yves Meyer and the Chern medal was given to Louis Nirenberg. The Laudationes for the Fields medals and Nevanlinna prize will be given by Hillel Furstenberg, Jim Arthur, Harry Kesten, Horng-Tzer Yau and Gil Kalai, respectively, and I’m looking forward to them. I’ll admit now that I was on the Fields medal committee — a difficult job, and moreover one that means that there are things that I cannot discuss on this blog (not that in any case I would like to engage publicly in discussions about whether the right decisions were made). What I can say is that the four people who have won Fields medals have spectacular achievements to their names.

Other interesting news was that the next ICM will be in South Korea (in Seoul), that the next IMU president will be Ingrid Daubechies, the first woman to hold the post, and that if you type “ICM” into the IMU web page you can now find every single article that has ever appeared in an ICM proceedings, and that this database is searchable.

I’ll describe the opening ceremony in more detail in my next post. I’ll include a description of what the prizewinners were wearing. (If you look up Cedric Villani in Google images, you’ll see that this is a more interesting question than you might at first think.)

That’s it for the time being.

I’m writing this post from a hotel room in Hyderabad at 3.20pm, trying to stay up for exactly the right length of time to deal with any jet lag I might have: stay up too little and I’ll wake up tomorrow morning at 4am and be unable to get back to sleep and will then still have the problem to deal with tomorrow; stay up too much and instead I’ll be woken tomorrow by my alarm and will desperately not want to get up, which would be bad as then I would miss the bus that will take me to the International Convention Centre for the opening ceremony of ICM2010. By the intermediate value theorem, there must be an optimal time to collapse into bed (given data such as the time change and the small bits of sleep I snatched between London and Dubai and between Dubai and Hyderabad). Unfortunately, I don’t know how to work it out.

So I’m guessing about 6.30pm, which would allow me to sleep for twelve hours and still comfortably make the bus. And to keep myself awake for the next three hours I plan to write this post and complete another more mathematical one that I started a few days ago. And over the next few days, if I can find the time, I thought I might write a traditional-style ICM blog. After all, for every one of the many mathematicians who are here there are dozens who are not. Perhaps some of those would have liked to come but couldn’t quite face organizing a trip all the way to Hyderabad. And perhaps some of those wouldn’t mind being kept in the loop, so to speak.

It’s my first time in India, and one of the first things I saw when there was finally a gap in the clouds, which was not until we were beginning our descent into Hyderabad, was that the cars drive on the left here. I think I must have known at some point that that was the case, but I had forgotten, so I had a small and pleasurable shock when I saw it. Other initial impressions were rather more standard and apply to many countries: the sudden heat as you step out of the plane (not that it’s all that intensely hot here), the longish immigration queue, a man at immigration who insisted that I write down my mobile number even though I told him I didn’t have my mobile with me (which later turned out to be false, as I discovered when its alarm clock went off inside my suitcase at 2pm, because I had set it for 8.30am the day before — bizarrely, Hyderabad time is not an integer multiple of one hour different from all the other time zones I have ever experienced), and who kept typing things into his computer and looking in a puzzled and sceptical way at my passport until I was convinced he was about to tell me that my visa was invalid. When I was finally through the baggage reclaim, I was welcomed by another long queue, this time for an ICM desk to sort out transport to hotels.

I decided it would be better to go straight to the conference centre to register — a decision that turned out to be correct as the distance between there and the hotel is much larger than it looks on the map, so I’ve saved myself a substantial journey between the two. A large part of the drive (in a taxi with the company of Oliver Riordan, Oxford combinatorialist and invited speaker at this congress) was down a new 8-lane highway that was almost deserted. My first taste of the contrast between the old rural way of life and the hew hi-tech India that we hear so much about was when we passed about half a dozen black cows calmly walking along the other four lanes (in the right direction). More remarkable than the cows themselves was the fact that nobody seemed in the slightest bit perturbed by them. And when we then came upon some more cows, this time on our side, pale brown, some of them calves, and sitting down in the middle two lanes or so, the driver just swerved round them and continued. I tried to get a photo but couldn’t time the click well enough.

Once we reached Hyderabad proper the most obvious features were large numbers of incomplete concrete buildings, often with clusters of metal wires/rods (I’m not sure of the right word — sort of half way between a wire and a rod) sticking up out of the tops of them, and even larger numbers of small yellow vehicles that were open at the sides and had benches for seating. I wondered whether they were motorized rickshaws, and having looked that up on Google images I think they probably were. Other amusing aspects of the journey were veering from lane to lane, tailgating, a great deal of hooting, right turns that could be achieved only by doing a U-turn and then turning left, etc.

When we finally got to HICC (the Hyderabad International Convention Centre), the taxi was security checked, and then I had to put my bags and self through aiport-like security before I could get into the building. Once inside, I went to the registration desk where there was no queue and a very quick process, a welcome contrast to some previous ICMs and ECMs I have known. I was given a little book of vouchers, most of them for food, coffee, snacks etc., but one for the “kit bag”, an immensely heavy bag (not the bag but its contents) that contained a programme for the conference (except that after the driving-on-the-left remark I feel obliged to point out that it actually says “Conference Program,” and US spelling seems to be the norm here), two postcards, one actually with stamps, a small hardback in a plastic wrap called “International Congress of Matheamticians, Hyderabad 2010″ that I have not yet opened, some leaflets, a special issue of a journal called Mathematics Newsletter with some quite nice general interest mathematical articles, mostly by Indian mathematicians, the Hyderabad Intelligencer, also wrapped in plastic and as yet unopened by me (but I expect it to be reasonably entertaining), a book of abstracts of the plenary lectures, the invited lectures and the panel discussions, and finally, and most bulkily by far, a book of abstracts of short communications and posters. So the heaviest item in the bag is, fortunately, one that I can manage without. Actually, I’ll have to manage without any of them tomorrow because we are allowed to bring almost nothing with us, so that we can’t use our Hyderabad Intelligencers and Mathematics Newsletters to threaten the life of the Very Important Person who will be formally opening the congress. More about that tomorrow. Oh, and there was also an umbrella in the bag, which removed my feeling of satisfaction at having been efficient enough to look up the weather forecast, see that heavy rain was predicted for more or less the whole week, and bring one myself.

What am I doing here? I have two reasons for coming to ICM2010 (together with the slightly silly reason that I have been to every ICM since 1994 and am reluctant to break the sequence). The first is that I am chairing a panel discussion called “Relation between the discipline and school mathematics.” (I too wondered what on earth that meant when I was first invited.) This entitles me to a green name tag with “INVITED SPEAKER” at the bottom, despite the fact that I am not one. (I will get ten minutes to say a few words as part of my contribution to the discussion — more about that on Friday after it has taken place.) The other reason, which doesn’t oblige me to come here but makes it make sense somehow, is … well, I’ll talk about that tomorrow, even though the information I’m reluctant to reveal is in the conference program and therefore basically in the public domain already.

Tomorrow I’ll listen to the opening ceremony and the laudationes for the new Fields medallists. I’ll then report back on what the ceremony was like and see if I can give some kind of summary of (what I understood of) what was said in the laudationes.

It seems that the informal argument in my previous post may have been aiming off target. Here is a sort of counter to it, by Jun Tarui. (See also this earlier comment of his, and the ensuing discussion.)

If I’ve understood various comments correctly, Deolalikar is making a move that I, for one, had not thought of, which is to assume that P=NP and derive a contradiction. How could that help? Well, it allows us to strengthen any hypothesis we might like to make about polynomial-time computable functions to one that is preserved by projection.

Let me spell that out a bit. Suppose that is a polynomial-time computable function on bits, where is at most polynomial in Then we can fix a set of bits, and for each we can ask the question, “Does there exist such that ?” (By I mean the sequence that agrees with on and with on ) And we can set if and only if the answer is yes.

Now these functions belong to NP (provided the choice of is made uniform in some way or other, but let me for now ignore the distinction between uniformity and non-uniformity). So if P=NP then they belong to P. To see this intuitively, note that if you are provided with and merely asked to verify that then you can do so in polynomial time (since by hypothesis is in P). That makes belong to P as well if P=NP.

Note that the solution sets of the functions are projections of the solution space of (the obvious projection from to ).

So it may be that Deolalikar is saying not that functions in P have some simplicity property (polylog parametrizability) but that functions with all their projections in P have this property. And a random function in P will then not be relevant, since its projections definitely don’t look as though they belong in P.

Terence Tao has a suggestion for dealing with this, which is to observe that if is smaller than then the function does belong to P after all, since we can just go through all possible and see whether they work. But if is bigger than then with immensely high probability there does exist such that so the function should be more or less trivial. (Of course, given that we have in mind a function that is not genuinely random, this probabilistic argument is not rigorous, but it seems extremely likely that its conclusion is correct.)

Playing Deolalikar’s advocate for a bit, let me see whether there might be a way to wriggle out of this. It occurs to me that he might consider adding a sparseness hypothesis: instead of looking at arbitrary polynomial-time computable functions, let’s concentrate on functions that are 1 only rather infrequently. Note that if you want to create an interesting function in NP, then this is a very natural restriction: it stops all the fibres containing a 1 and making the projection trivial.

It’s easy to create a pseudorandom function with this sparseness: whereas before I suggested doing a sequence of random bijections on triples of coordinates and then taking the value of the first coordinate, now I would suggest doing a sequence of bijections as before and taking the function to be 1 if and only if the first coordinates are equal to 1 after the bijections have been performed. The result is a function that should be 1 with density about

If we now do a projection to a set of size then it will be 1 with probability about so it will be far from trivial. But checking for a satisfying assignment (that is, a such that ) by brute force now takes time

So here is a proof strategy for Deolalikar to which I don’t see an immediate objection along the lines I have been proposing (which does not rescue Deolalikar’s argument from the many other objections, but I still find it of some small interest). We shall try to find a simplicity property of polynomial-time computable functions with the following properties.

(i) They take the value 1 with exponentially small density.

(ii) They are reasonably uniform. (This is to avoid a function that is just an ordinary random computable function of the first bits, provided the last bits are all equal to zero.) That is, there are no “nice” sets on which their density is much bigger than exponentially small.

(iii) All their projections belong to P as well.

This is all very well and good, but what should the simplicity property be, and how does one use the vitally important hypothesis that the projections are in P? Well, I’m imagining that Deolalikar’s answer to the latter is something to do with finite model theory. For instance, perhaps in some sense the projections “ought” to be introducing an existential quantifier, so if they don’t, then it “ought” to be saying something pretty strong about the function, if we use a logical characterization of P. (Unfortunately, I don’t understand anything about finite model theory, so I can’t be more detailed here.) Perhaps this allows him to conclude that a function with properties (i)-(iii) has a simplicity property that k-SAT at the critical density lacks.

Let me make very clear that I am not endorsing Deolalikar’s argument. This post is more about me than about the argument: it is saying that I no longer have my own pet explanation for why a proof of this general kind could not possibly work. But that is a very far cry from saying that the vague outline above can be turned into a proof: I don’t have the faintest idea how to get from the finite model theoretic characterization of P (which I cannot even state) to something about polylog parametrization (the definition of which I do not understand).

Update. On thinking about this a little further, I now think that even a more sophisticated approach such as I have outlined above will run into very serious difficulties, which are basically the same difficulties as before but pushed to a different place. To see this, let us consider the contrapositive of the statement one would need to prove.

First, for clarity’s sake, here is the statement itself (not in precise form): if is a function in P (perhaps satisfying certain extra conditions that are satisfied by random k-SAT) and all its projections are also in P, then has a structure that random k-SAT lacks.

It seems to me that this statement is equivalent to the following (also not completely precise) statement: there exists a projection of k-SAT with some property that functions in P lack.

If so, then we still have to decide what that property is. If it is a simplicity property, then we appear to be doomed for the reasons outlined in my previous post.

Why did I say that the two statements “seemed to be” equivalent? I did so because there just conceivably might be some magic that gets from the property that all projections are in P to some global simplicity property. So one might end up needing to show merely that random k-SAT lacked the global property. But I’m not sure that really helps, since again the contrapositive will show that any function that lacks the global simplicity property has a projection that has a property not shared by any function in P. What is that property?

Without a pretty amazing answer to that question, I go back to feeling that no argument along these lines can succeed.

This post comes with the same warning as my previous one: my acquaintance with the ideas of Deolalikar’s paper is derived not from the paper itself (apart from a glance through it to get some kind of general impression) but from some of the excellent commentary that has been taking place on the blogs of Dick Lipton and Scott Aaronson. One comment that many people, including me, have found very useful has been one of Terence Tao, who attempted to summarize the state of the discussion up to the time he made the comment. Here is a portion of his summary.

The paper introduces a property on solution spaces, which for sake of discussion we will call “property A” (feel free to suggest a better name here). Formally, a solution space obeys property A if it can be efficiently defined by a special family of LFP formulae, the monadic formulae (and there may be additional requirements as well, such as those relating to order). Intuitively, spaces with property A have a very simple structure.
Deolilakar then asserts
Claim 1. The solution space to P problems always obey property A.
Claim 2. The solution space to k-SAT does not obey property A.

The latest from Dick Lipton’s blog seems to be that Neil Immerman has identified two serious flaws with Deolalikar’s proof. However, Tao, commenting on that, has pointed out that Deolalikar’s general strategy has not yet been shown to be hopeless in the way that, say, an attempted natural proof would have been shown to be hopeless by Razborov. In this post, I’d like to argue that it might be hopeless. I’m not sure I can say what that means in the abstract, so let me just give the argument.

First, here is a slightly more detailed version of Tao’s summary, provided on Dick Lipton’s blog by Albert Atserias.

If I may I would rephrase the thing as follows. Let “polylog-parametrizable” be a property of solution spaces yet to be defined.

Claim 1: The solution spaces of problems in P are polylog-parametrizable.

Claim 2: The solution space of k-SAT is not polylog-parametrizable.

Now, Claim 1 could be split as follows:

Claim 1.1: The solution spaces to problems in Monadic LFP are polylog-parametrizable.

Claim 1.2: Every problem in LFP reduces to a problem Monadic LFP by a reduction that preserves polylog-parametrizability of the solution spaces.

From these Claim 1 would follow from Immerman-Vardi Theorem (we need successor or linear order of course).

Perhaps Claim 1.1 could be true (we know a lot about Monadic LFP, in particular unconditional lower bounds using Hanf-Gaifman locality). But Claim 1.2 looks very unlikely. The reduction that Deolalikar proposes is standard but definitely does not preserve anything on which we can apply Hanf-Gaifman locality.

What I would like to do here is attempt to reinforce Atserias’s conclusion, by explaining why it seems to me very unlikely, unless somebody can tell me an amazing idea that gets round the problem (that is an important qualification, since one’s mathematical intuition can certainly be affected by unexpected ideas) that Claim 1.2 could be true. To do that, I’ll exhibit a specific problem in P that just doesn’t feel as though it could be reduced.

All this is completely independent of what any of the words in Atserias’s summary mean. I don’t know what polylog-parametrizability is (my comfort here is that I know of nobody apart from Deolalikar who does), or what the Immerman-Vardi theorem states, or what Hanf-Gaifman locality or monadic LFP are. And one thing Deolalikar’s paper has done is make me quite curious about these concepts and results. But for the purposes of this discussion, all that really matters is that polylog-parametrizability should mean something vaguely like what its name suggests.

OK, the problem in P I have in mind is this. Let me start with the following model of a random circuit (which I have discussed before in my sequence of “conversations between smileys” about the P versus NP problem in late 2009). Start with a 01 sequence of length (which we think of as the input). Now at each step of the computation, perform the following process. Choose three random numbers between 1 and (that is, choose a subset of of size 3 uniformly at random), and a random bijection Now apply to the values of the sequence at those three numbers. That is, if we choose with then take the 01-sequence apply to it, and put the transformed sequence back in places , and

Now just repeat this process for, say, steps. Define the output of the function to be the value of the first term of the sequence once this process has finished.

Not very much has been proved rigorously about functions like this, but what little is known points to a conclusion of the following kind: their solution spaces (that is, the set of input sequences that give rise to a 1) are very very hard to distinguish from random subsets of This provides a rather useful sanity check for any proposed proof that PNP. It is similar to the natural-proofs barrier, but with the important disadvantage of not being rigorous. And it goes something like this: if I have a property that is supposed to distinguish between the solution spaces of problems in P and the solution space of at least one other problem, is it at least plausible that this property applies to the solution spaces of random computable functions (defined according to the above model) if and only if it applies to random functions? If so, then the failure of the property at some specific problem in NP has to be a rather particular to that problem in NP. (This is similar to Razborov and Rudich’s requirement that a property that distinguishes P from NP should either be very strange, or else should apply to almost all functions — not including some specific function in NP.)

Now whatever polylog-parametrizability might mean, it doesn’t sound like something that would apply to a purely random function. Indeed, Tao describes it as a “simplicity” property. This already worries me — why doesn’t Deolalikar’s argument fall foul of the natural-proofs barrier?

The suggested answer to this is that Deolalikar uses uniformity in an essential way. Note that the random computable functions I defined above are not uniform — I was giving a different circuit (or rather, something that can easily be realized by a circuit) for each But I find it incredibly unlikely that this makes a serious difference, since I could always generate the circuits pseudorandomly in some silly way. For instance, I could use digits of to help me make my random choices. Will that suddenly make the solution space far nicer than it was before? I don’t think so.

Now Deolalikar could simply counter that, whether I like it or not, he has found a simplicity property of pseudorandom computable functions. But if that assertion is in doubt, then it is legitimate to step back and consider the general strategy, as I am now doing, and ask whether something might conceivably be salvaged from Deolalikar’s proof attempt. And I have tried to present reasons to be pessimistic about this.

I don’t feel as though the arguments in this post are watertight. Indeed, somewhere I read a rather sophisticated comment (which I cannot relocate) about how Deolalikar might be evading the natural-proofs barrier, and it may be that a similar comment would deal with my worries. Also, my total lack of understanding of any of the logic and finite model theory used in the argument means that I am not properly taking account of the possibility that the property involves some kind of trace that a function in P has of how it has been put together. (However, if I was given the solution space of a pseudorandomly computable function in P, I wouldn’t fancy my chances of reconstructing the circuit that led to it …)

So to finish with, here are my main two questions. Apologies if they have already been answered in other places.

1. Is polylog-parametrizability supposed to be a “simplicity” property that applies to functions in P but not to random functions?

2. If so, then can anyone give me a half-plausible idea of how it might distinguish between a function computed by a pseudorandom circuit of length and a genuinely random function?

I have a feeling that the answer to 1 may in fact be no, and that Deolalikar is claiming that almost all functions are simple, but that at a certain critical probability random k-SAT has very delicate features that are shared by very few functions and that make it complex. But I’d still like to be sure about this.

Given that I have expressed rather unambiguously an interest in the P/NP problem on this blog, I feel duty bound to make some kind of remark about Deolalikar’s recent attempt to prove the theorem. (If by some extraordinary chance you don’t know what I am talking about, then an excellent starting point is Dick Lipton’s blog, a link to which can be found in my blogroll.)

The problem is that I haven’t looked at Deolalikar’s paper in any detail, and already I can tell that I cannot possibly compete with the extremely knowledgeable comments that have been made by several TCS experts. So instead, let me say that, like everybody else, I greatly admire what Deolalikar has done, whether or not it turns out to be correct, and am happy to wait to see how things pan out.

Instead of commenting directly on his work, I thought I’d air some thoughts I had a few years ago. I was reminded of them by reading that an important feature of Deolalikar’s proof is that it uses uniformity in an essential way (though whether this is really the case has been disputed by some commenters).

For the benefit of readers not versed in complexity theory, let me briefly say what uniformity is. One of the key strategies in the attempts to prove lower bounds for computational complexity is to use circuit models. Roughly speaking, a circuit is an array of AND, OR and NOT gates. You feed in a Boolean function, calculate what all the gates do, and get an output. It turns out that a function that can be computed by a Turing machine in time n can be calculated by a circuit of size m, where m has a polynomial dependence on n. Therefore, a lower bound on the size of a circuit needed to compute a function gives a lower bound for the number of steps needed in a Turing computation.

Now a major difference between Turing complexity and circuit complexity is that if you have a sequence of related Boolean functions with inputs of increasing size (such as trying to find a Hamilton circuit in a graph with n vertices), then in a certain sense the Turing complexity is the number of steps you need if you use “the same process” whatever the size of the problem. And that is characteristic of the kinds of algorithms we produce in real life. Whereas, in principle, a circuit complexity lower bound is much stronger, since you could come up with a completely different circuit for each size of problem.

In practice, however, nobody has the slightest idea how completely different circuits for each size of problem could ever give you an advantage over a good old-fashioned algorithm. (I say that without being sure that it is true — so if anybody would like to point me towards a paper in the literature that gives an interesting non-uniform upper bound where there is not a corresponding known uniform upper bound, then I’d be fascinated and would happily correct what I’ve just said.) Nevertheless, the theoretical distinction is undeniably there.

One can make the two definitions equivalent by insisting that the sequence of circuits is uniform, meaning that they can be produced in polynomial time by an algorithm. If that is the case, then a polynomial upper bound for the circuit size gives you a polynomial-time algorithm for the original problem, since all you have to do is generate the circuit and then see what it does.

My idle thoughts were concerned with the following question: what could a proof that PNP conceivably look like if it made essential use of uniformity? That is, how might one reason about algorithms without generalizing them to circuits? It seems pretty hard, because circuits are nice set-theoretic objects that can be formulated in terms of intersections, unions and complements, whereas algorithms are difficult things that are made precise via quite complicated notions such as that of a Turing machine.

Before I go any further, I want to stress that this is a blog post rather than a paper. I am using it to air ideas that I do not consider interesting or original enough to attempt to publish in a more conventional way. Indeed, I would go further and say that with one exception (a minor result in complexity that was published over a decade ago) I have not had any ideas in theoretical computer science that are both new and interesting to experts. Once or twice I’ve met the latter criterion but then they have turned out to be very far from new. I’m not sure whether I’ve had any new ideas, but if I have then they have been ideas with flaws that would be instantly apparent to experts.

Perhaps the most promising aspect of algorithms that is not shared by arbitrary circuits is the heavy use they make of iteration. In a sense, this is a triviality: a Turing computation just is the iteration of a fairly simple function, which, if you set it up correctly, will have a fixed point when the computation halts. But the connection can be made more direct via the equivalence of Turing computable functions and recursive functions.

The problem from the point of view of proving lower bounds is that iteration can give rise to some very strange functions: one has only to think of sets like the Mandelbrot set. So it does not look easy to argue that a set of the form “the set of all Boolean sequences that output 1 when you iterate the following function until you reach a fixed point in polynomial time” must have some simplicity property that is not shared by all NP functions.

Nevertheless, here is a little fantasy. It has all sorts of superficial problems with it, and I’m pretty sure it has deep problems with it too, but that gives it a small interest to the non-expert as an illustration of what makes the P/NP problem so hard.

The idea has two aspects to it. The first is to exploit the fact that an obvious analogue of the statement PNP in the infinite world is known to be true and is not that hard to prove. To spell out this analogy, let’s talk about sets instead of functions. (Corresponding to the function is the set ) A set in P (or rather, a set of polynomial circuit complexity) is one that can be built up from the basic coordinate hyperplanes by means of not too many intersections, unions and complements. This should call to mind Borel subsets of , which are sets that can be built up from basic coordinate hyperplanes using only countable intersections, unions and complements. Now an NP set is a projection of a set in P. (That is, if is a set in P, then the set of all such that for some is a set in NP.) Projections of Borel sets are called analytic sets, and they are known to be different from Borel sets in general. Moreover, there are also “complete” sets: that is, there are universal analytic sets with the property that if they were Borel then all other analytic sets would have to be Borel.

Once one is aware of these facts, the temptation to try to exploit them is obvious. Indeed, this idea comes into the category of ideas that were quite interesting but far from new: it is credited to Michael Sipser, who, I should also say, had much more detailed and interesting proposals about how to use it than anything I have ever come up with. There are a number of snags with it, however, and I think it is now generally thought of as an approach to PNP that is “known not to work”. (Again, if there are variants of the idea that make some attempt to get round the relativization, natural proofs and algebrization barriers, then I am very happy to retract that last statement.)

OK, here was the thought I had, which is almost certainly something that has been considered in depth by the TCS community — so this post is party a request for a good reference, perhaps even to Sipser himself. It is not hard to show that the set of all graphs with vertex set that contain an infinite clique is analytic but not Borel. Could one perhaps take a purported polynomial-time algorithm for the clique problem for finite graphs, and “see what it does in the infinite case”? The hope would be that it would translate into an “efficient infinite procedure” for determining whether an infinite graph contains an infinite clique, which would in turn amount to a proof that the set of graphs containing an infinite clique was Borel. This would be a contradiction, which would prove that there was no polynomial-time algorithm for the clique problem in the finite case.

Before I list the numerous bad aspects of this idea, let me try to give it some veneer of plausibility by discussing one example where it does seem clear what the “infinite version” of a finite algorithm is. (But I’ll undercut myself in advance by saying that doing this for one algorithm is very different from doing it for a completely general algorithm.)

Let’s consider the following simple algorithm for deciding whether two given points and in a finite graph are joined by a path. You just write the number zero next to then 1 next to the neighbours of and in general at the kth stage you write a k next to all not-yet-labelled vertices that are neighbours of vertices that have been labelled (which will necessarily have been labelled k-1, or the new vertices would have been labelled earlier). You keep going until either you label or you can no longer label any new vertices. It’s easy to see that this takes polynomial time (however you reasonably choose to implement it) and that by the end you have labelled all vertices that are connected to with their distance from

Equally clearly, there is a sense in which this algorithm works for infinite graphs. You just do exactly the same thing that you do in the finite case, and after a countable number of steps either you will have identified a shortest path from to (if you label then start at and choose at each stage a neighbour with smaller label until you reach ) or you will have shown that and are not connected.

Not quite so obviously, the existence of this infinite algorithm can be used to show that the set of all infinite graphs such that is joined to is Borel.

So could this be an example of a much more general phenomenon, showing that polynomial-time algorithms have infinitary analogues that produce Borel sets? Here are a number of reasons to think not.

1. The parity function (which is 1 if there is an even number of 1s and 0 if there is an odd number of 1s) is computable in polynomial time. However, the natural infinitary analogue of this function is not even Lebesgue measurable (by the Lebesgue density theorem). More precisely, no function of infinite 01-sequences that changes its value whenever you change a single bit is Lebesgue measurable.

2. There are known complexity lower bounds for parity but they concern restricted classes of circuits. Particularly relevant is Hastad’s result that parity requires exponentially large circuits if those circuits are of constant depth. This suggests that the correct finitary analogue of Borel sets is not polynomially computable sets but sets that are computable by polynomial circuits of bounded depth. (I think this is the direction Sipser went in, but I can’t find a copy of his paper Borel Sets and Circuit Complexity online and am not near a library.)

3. A straightforward result in descriptive set theory is that a set is Borel if and only if it and its complement are both analytic. It is conceivable that sets that are in both NP and co-NP are thereby in P, but if that is true then it certainly does not have a straightforward proof. The class NPco-NP includes such famous problems as factorizing. I think it is fair to say that the general belief among experts is that NPco-NP does not equal P, but that this belief is considerably less strong than the belief that PNP. In particular, a number of people have expressed doubts that factorizing requires a super-polynomial algorithm, and if a polynomial-time algorithm were to be found for factorizing, then as well as causing a massive shake-up of internet security, it would make it much harder to argue that PNPco-NP.

4. There is a polynomial-time algorithm for deciding whether a bipartite graph has a perfect matching. However, the problem of deciding whether an infinite bipartite graph has a perfect matching is analytic but not Borel. So the infinitary analogue of the result about perfect matchings would have to be a slightly non-obvious one. (Perhaps it could be something like that the set of bipartite graphs with perfect matchings that don’t match any number to another number that is too far from the first number is Borel.)

5. When it is straightforward to produce an infinite version of a finite algorithm, it tends to be possible also to produce a rather boring infinite version. For instance, in the connectivity problem, one can check in a nice countable way whether and are joined by simply enumerating all finite paths and seeing whether any of them happens to link to The obvious finitary analogue of this infinitary algorithm is not a polynomial-time algorithm. This suggests that Borelness is somehow “crude and insensitive” in a way that polynomial time computability is not.

6. I am not sure about this one, but I have a feeling that experts would tell me that any attempt along these lines would relativize: that is, it would also prove the false result that PNP relative to any oracle. I don’t want to say more than that because my understanding of this barrier is such that I am likely to get things wrong. Instead, let me refer you to this post of Terry Tao.

Despite these fairly devastating objections, I can’t help having a teeny affection for this general approach. Probably I am wrong to do so, so if anyone would like to hit me with even stronger reasons to think that it cannot work, then you will cure me of a minor ailment and earn a corresponding amount of gratitude.