## 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.

### 20 Responses to “A solution to an exposition problem”

1. Ryan O'Donnell Says:

I have no proper internet access right now, and look forward to reading your exposition when I get it, Tim.

In the meantime, I vaguely remember liking the proof Berg and Ulfberg gave:

2. harrison Says:

This looks wonderful! Of course, many of Razborov’s results share the quality of seeming “miraculous” or “magical,” and it’s always nice to see that you don’t have to be Razborov-level brilliant to obtain these kind of results (though, apparently, it helps ;)).

Incidentally, the idea of “giving a plausible account of how a proof could have been discovered” reminds me of a famous story of Borges, whose title I forget, in which his character decides to take it upon himself to independently write the text of Don Quixote. Fortunately, the exposition problem seems nowhere near that hard. Maybe once I’ve digested the meta-problem of how to write an expository paper of this nature, I’ll give it a try myself.

• gowers Says:

It’s Pierre Menard, Author of The Quixote. I remember being struck by that and the equally famous The Library of Babel when I read them (a long time ago) — of course, they have an obvious appeal to a mathematician.

3. Qiaochu Yuan Says:

This is a great idea. My non-mathematical friends frequently complain that one of the things they don’t like about mathematics is that they can’t see how anyone could possibly have come up with the results they have to learn, and I don’t blame them.

My current pet peeve in this regard is the definition of the determinant. I don’t know of a good reference that thoroughly explains how the permutation expansion of the determinant could be written down by someone who’s never seen it before. And while we’re on the subject, I also don’t know a satisfying theoretical reason why determinants should be so absurdly useful in algebraic combinatorics (Gessel-Viennot, the method of Pfaffians).

• Jason Dyer Says:

There has been discussion a while back on this very blog about how to show determinants intuitively. It’s on my back burner to write a “gentle introduction” style exposition which should make it entirely clear, but if there’s enough demand I can always bump it up on the queue.

• gowers Says:

I suppose one answer is that you go into a dark corner somewhere and work out what linear maps do to volumes and eventually you tidy up your answer and find that, lo and behold, you’ve got the determinant. But maybe that leads more naturally to the alternating multilinear forms view than to the permutation expansion view. But the first could be said to lead to the second perhaps. (These remarks are meant more as a plan of what to do than an actual exposition of course.)

4. Stones Cry Out - If they keep silent… » Things Heard: e68v4 Says:

[...] The exposition problem. [...]

5. Ryan O'Donnell Says:

Thanks Tim — I always like to see these kinds of expositions (especially when they’re in my own field)!

For this particular problem, I have always been very fond of the Berg-Ulfberg proof: pdf.

• Ryan O'Donnell Says:

I didn’t really mean to post twice, but my first post got caught in the spam queue I think, so I tried reposting…

6. James Says:

Closely related to open exposition problems are when you feel you need to get to the bottom of some topic X. For instance, X is often understood by many people, but you still feel that there ought to be a better way, that you don’t know what’s really going on.

I think that, while getting to the bottom of X might look like a purely expository task, it is probably a very important thing to do. This is because new theorems usually come from understanding basic things very well, and not the other way around. In my case, I owe my whole research program to a few months spent trying (successfully!) to get to the bottom of something important and basic but fundamentally simple and often passed over.

The reason why I mention this here is that I think open exposition problems and things we need to get to the bottom of are often indistinguishable in the beginning. So, even if our measure of value is only progress in research, I would still put a very high value on solving open exposition problems.

• gowers Says:

A similar thought I had while writing the account of Razborov’s proof was that it is possible to distinguish two kinds of solution to an exposition problem, which one might call “weak” and “strong”. A weak solution is what I gave: for each step of the proof, you try to explain why it is reasonable to expect somebody to come up with it. But sometimes, and it happened here, it is reasonable to expect somebody to attempt a calculation, and the calculation works, but one is still left wanting to understand why it works. A strong solution would be one where for each calculation there is a better explanation than “Try it — it works”. A super-strong solution is one where you can come up with such an explanation in advance and not just with the benefit of hindsight. That is, for each calculation you have good theoretical reasons for being virtually certain that it will do what you want it to do, and the calculation itself is just a sort of check that your ideas are sound.

7. Michael Nielsen » Biweekly links for 05/22/2009 Says:

[...] A solution to an exposition problem « Gowers’s Weblog [...]

8. Miguel Lacruz Says:

Tim, concerning the exposition problem for determinants, you probably know about the paper Down with determinants! by Sheldon Axler, where he shows that many things can be done without determinants, e.g. the existence of eigenvalues for a square complex matrix.

9. conformal Says:

Hi Tim,
Apologies for this off-topic question: in the problem to show there is an arithmetic progression of any length consisting of consecutive prime numbers, is there a better calculation than a 7 with 120 difference?

10. Student Says:

Professor Gowers,

Thank you for posting video of your computational complexity course. I am a graduate student in the US, and while I have never had the opportunity to sit in on your courses, I have studied your notes on Combinatorial Number Theory, as well as several of the other expository notes on your website. I find your courses (and notes) to be very interesting and comprehensible. As my graduate program offers very few topics courses, I was hopeful that I could persuade you to consider posting video of future courses on the web as well. While I can understand why some faculty members wouldn’t want to do this, I would also encourage anyone else reading this with the resources to to do so to consider posting video of topics courses!

As an aside, I also need to say that the video production was particularly well done in this case. Most taped math lectures I have seen suffer from bad audio and an inability to read what the lecturer is writing on the board. These were very well done!

11. Mark Bennet Says:

Perhaps the material on why the problems you have chosen are actually interesting needs to be in there somewhere. Being somewhat out of the loop on contemporary mathematical results, I still know about P=?NP, and had heard that there was a proof that there was no natural proof of P=NP (or something a bit like that). To have this explained is a great joy.

But it was only after following the lectures that I realised that monotone circuit complexity had something to do with these problems. I would have been much more excited about the lectures had I been inducted into the significance of the result – perhaps a few comments on the blog as a reminder to amateurs like me as to what it is all about??

• gowers Says:

You’re right of course. The reason I didn’t was that my primary purpose in writing the notes was to make sure that a certain portion of the course was adequately written up for the sake of an audience to which I had already explained the motivation for the results. But let me briefly explain what that motivation is for the sake of anyone who doesn’t know it and would like to.

The problem of whether P=NP is very closely related to the question of whether there is any problem in NP that cannot be solved with a (family of) polynomial-sized circuit(s). A circuit is a network of AND, OR and NOT gates that process an input (a string of n 0s and 1s) and produce an output (either 0 or 1). It is fairly easy to prove that if a function from $\{0,1\}^n$ to \$\{0,1\}\$ can be computed in polynomial time, then there is a circuit of polynomial size that will compute that function as well. This means that a potential way to prove that P does not equal NP is to prove that some function in NP cannot be computed by a polynomial-sized circuit. And this is useful because circuits are easier to contemplate from a purely combinatorial point of view than algorithms or Turing machines.

Now one might think that if the function f is monotone, which means that the set of input strings x such that f(x)=1 is closed under changing coordinates from 0 to 1, then there would be no advantage in using NOT gates (though in fact this supposition is known to be wrong). At any rate, it is interesting to try to obtain circuit lower bounds when NOT gates are not allowed. This was for a long time as wide open as the general problem, until it was spectacularly solved by Razborov. It is quite easy to reformulate the problem as the question about unions and intersections that I put at the beginning of the document.

So the short answer to why the result is interesting is that it is a very natural weakening of a statement that would imply that P does not equal NP.

Unfortunately, the insights of Razborov and Rudich and others have told us that, impressive as the result is, it is unlikely to represent a significant step towards a proof that P does not equal NP. Nevertheless, it does hugely improve our understanding of the problem.

12. conformal Says:

Hi Tim,
Could we please continue to discuss primes? I would like to think about a hard problem in analytic number theory, however it seems to me we should first build our thinking on an appropriate for the task proof of existence of infinitely many primes. Kummers’ is considered the cleanest – is Schorn’s combinatoric enough?