A solution to an exposition problem

Let me explain the title of this post by quoting from Timothy Chow’s highly recommended expository article A beginner’s guide to forcing: “All mathematicians are familiar with the concept of an open research problem. I propose the less familiar concept of an open exposition problem. Solving an open exposition problem means explaining a mathematical subject in a way that renders it totally perspicuous. Every step should be motivated and clear; ideally, students should feel that they could have arrived at the results themselves.” He goes on to claim that forcing was an open exposition problem, since there was no explanation in the literature that had these qualities.

I have just finished giving a graduate course in Cambridge on two highlights of theoretical computer science: Razborov’s lower bound for the monotone circuit complexity of the clique function, and Shor’s quantum algorithm for factorizing integers. Because nobody was taking an exam on the course, I was free to be somewhat informal in the lectures, but at one or two points it got slightly too informal so I rashly promised that I would produce notes on Razborov’s theorem. However, the document that resulted ended up being less a set of lecture notes in the usual sense and more an attempt to solve an exposition problem in Chow’s sense. Very briefly, Razborov produces a lattice of a certain kind, with a rather strange definition, and it goes on to do the job it is supposed to do in a seemingly miraculous way. What I have written is an attempt to solve the problem, “Where did Razborov’s definition come from?”

A few qualifying remarks are in order here. I’m not sure I’d describe this particular exposition problem as open, since many people have digested Razborov’s argument, and Razborov himself presumably knows how he discovered it (unless he has forgotten, which often happens but I suspect less often in Razborov’s case). It may even be that an account similar to mine exists in written form somewhere. And there is a chapter in Alon and Spencer’s book on the probabilistic method in which they look at the simpler but still interesting problem of finding a lower bound for the monotone circuit complexity of determining whether a graph contains a triangle, which could probably be developed into a different and equally convincing explanation of where the ideas come from. Finally, I do not mind if in fact Razborov thought of his proof in a completely different way: my aim has simply been to show that there exists a reasonable thought process that leads to the argument.

Unfortunately, what I wrote is too long to give as a blog post (though I suppose in principle I could split it up into chunks). So here it is as a pdf file instead. It is a first draft and not carefully checked, so if anyone has any comments or corrections, then they will be gratefully received.

I should also mention, though I do so with a small degree of embarrassment, that the quantum computing group in Cambridge’s Department of Applied Mathematics and Theoretical Physics are creating an archive of videoed lectures, and I agreed to let them video my course. The lectures are pretty informal, to the point of containing mistakes, though most of those were cleared up thanks to audience comments, either during the lectures themselves or in time for the next one. But since the lectures are there on the web, and could be regarded as some sort of resource, it would be a bit odd not to give the link. Here is an index to the first eight lectures out of ten — the other two should go up soon.