Dimension arguments in combinatorics

Here is another article that I hope to develop into an entry on the Tricks Wiki. It concerns the use of linear algebra to solve extremal problems in combinatorics. The method is quite easy to illustrate with some well-known examples, but what I find interesting is the question of how to recognise the kind of problem where the method is likely to apply. I have something to say about that, but I’d like to make clear that I didn’t think of it for myself. If I remember rightly, I read it in something that Noga Alon wrote. I’ll draw attention to it when I get there.

Recognising countable sets

As may be obvious from the sudden increase in my posting rate (which I don’t expect to be able to keep up) The Princeton Companion to Mathematics is now off my hands, which gives me the chance to devote a bit of attention to other projects, of which the Tricks Wiki is one. So in this post I’m going to discuss a relatively elementary piece of university mathematics, and will do so in the form of a sample article for that site. I’ll be a little careful about predicting when the site itself will be up and running, but let me just say that I’ve put some work into it recently and I don’t want to waste that work.

In what follows, I shall adhere to what I hope will be the basic format of an article on the site. The most important elements of that format are that there is a brief description, or “slogan”, that encapsulates the basic idea, and a general discussion of the idea that is illustrated by several clearly delineated examples.

More quasi-automatic theorem proving

In this post I shall continue some of the themes of the previous one by looking at fairly simple but not completely trivial mathematical statements and trying to imagine how a computer might systematically solve them. The main one comes later on: I shall look at how a computer might arrive at a construction of an injection from to . (If you don’t know what this means, it’s simple to explain: to each pair of positive integers one must assign a positive integer in such a way that no two pairs get assigned the same positive integer.)

What is deep mathematics?

Note added 12/9/09: It seems that many people are looking at this post, because Derren Brown claims to have used “deep mathematics” combined with “the wisdom of crowds” to predict the lottery. All I can say is that this is obvious nonsense. Whatever method you use to predict the lottery, the drawing of the balls is a random process, so you will not improve your chances of being correct. Brown has done a clever trick — I won’t speculate about his methods, as I’m not interested enough in them — but his explanation of how he did it is not to be taken seriously.

In this post I shall discuss the proofs of two statements in real analysis, one of which is clearly deeper than the other. My aim is to shed some small light on what it is that we mean when we make that judgment. A related aim is to try to demonstrate that a computer is in principle capable of “having mathematical ideas”. To do these two things I shall attempt to explain how an automatic theorem prover might go about proving the two statements in real analysis: in one case this is quite easy and in the other quite hard but by no means impossible. In the hard case what interests me is the precise ways that it is hard, which I think say something about the notion of depth in mathematics. 

Punctuation question

The Princeton Companion to Mathematics is even more nearly nearly finished than it was last time I said it was nearly finished. In fact, this time I can give a date — July 13th — past which it will be too late for me to do any work on it. The book will be printed in September and available in November.

As an example of the important issues we now face, here is a question about hyphens: I’m fairly sure there will be a small but passionate minority of mathematicians who care about these, and a question has come up. I am curious to know what other people think, so I’m not going to say what I think: I’ll just try to present the question as neutrally as possible. And here it is.