What counts as a trivial piece of mathematics?

If you read Doron Zeilberger's entertaining opinions on mathematics, you will find that he makes some apparently very curious remarks about mathematical theorems. Let me quote a couple, just to give the idea:

I have a meta-proof that FLT is trivial. After all, a mere human (even though a very talented as far as humans go), with a tiny RAM, disk-space, and very unreliable circuitry, did it. So any theorem that a human can prove is, ipso facto, utterly trivial. (From Opinion 36.)

If humans will keep trying to find human proofs, and fail, it will raise the probability that 4CT is indeed deep. On the other hand, if some human will prove 4CT tomorrow, only with pencil-and-paper, then this would be very nice for the prover, who will become instantly famous, but very depressing for our mathematical culture as a whole. It would mean that perhaps we humans are so trivial that we are not even capable of stating and conjecturing deep results. (From Opinion 51.)

What is Zeilberger on about? Many mathematicians will find what he says merely ridiculous - Fermat's Last Theorem is very far from trivial, and the chances are that a beautiful, conceptual argument for the four-colour theorem would be much deeper than the check-thousands-of-cases argument that has been found so far.

But if we start from the premise that Zeilberger is not being wilfully perverse (provocative perhaps, but that's another matter) then we cannot dismiss him just like that. Instead, we should try to understand what is going on in his mind. What induces him to write the words he writes? The best way to sort this out is to try to decide what he means by words such as "deep" and "trivial". If these words have their standard meanings, then what he writes is patently false, so we should give him the benefit of the doubt and look for non-standard meanings that do justice to his writings. What follows is my attempt to carry out this task. (I am not relying solely on his web page - I have also had several interesting conversations with Zeilberger himself.)

The normal use of the word "deep" is something like this: a theorem is deep if it depends on a long chain of ideas, each involving a significant insight. Suppose some definition leads to a new and thriving branch of mathematics. Initial results may be relatively straightforward consequences of the basic axioms being assumed. Then from time to time natural statements appear that do not have easy proofs or disproofs. With a certain amount of ingenuity, some of these problems are solved and some of the solutions turn out to be very fruitful, in that they can be used to solve many other problems. Such results then form a new body of statements, one layer deeper than the original axioms. Once these statements become familiar to experts, they take on the feel of axioms themselves, and the process can repeat, giving rise to a second layer - of non-trivial consequences of non-trivial consequences of the basic axioms. The longer this process continues (and of course you can't actually say precisely which layer a result belongs to - this is just a model) the deeper the layers are that you reach, and the more utterly impossible it would be for a non-expert to prove your results from first principles. So, according to the standard view, those results are deep.

How about "trivial"? Perhaps there are subtle distinctions between this word and others such as "obvious", "easy", "standard" or "elementary", but let me pick one possible definition out of many: a proof of a result is trivial if each step of the argument is easy to find, once you understand the previous one, and more or less the only sensible thing to write down. This definition allows for the possibility that a result is trivial even when its triviality is not obvious. For example, there is a definition I present from time to time with the following logical form:

A set is **** if for at least (1-c)N elements k of {1,2,...,N} the maximum over r in C of f(k,r) is at most t.

The following statement is a trivial consequence of the above definition, but most people have some trouble seeing this.

Let A be a set that is NOT ****. Then we can find a subset B of {1,2,...,N} with |B|> cN and a function g:B-->C such that f(k,g(k))> t for every k in B.

What is trivial about this consequence is that it is the result of simple logical manipulations, and what makes it troublesome is merely that it may be hard to do these manipulations in one's head.

What does Zeilberger mean by the words "trivial" and "deep"? I have some sympathy with the feedback by Yair Caro , who complains that he is more or less defining these words to mean "humanly solvable" and "hard to find by humans". That is, he adopts non-standard definitions (to put it mildly) that make his subsequent statements true by definition - or, dare I say it, trivial.

But even this is perhaps to deal with his views a little too hastily. For there is a subtler definition of "deep" that is a bit closer to what Zeilberger (as I understand him) really means. The process of discovering a proof can be thought of as a search through the vast space of possible mathematical arguments. It is clear that we humans only ever look at a tiny part of this space. Indeed, if P does not equal NP then we cannot expect to deal with the whole space - if a theorem has only an arbitrary, meaningless proof with lots of completely unmotivated steps, then we will never manage to prove the theorem, even if there does in fact exist a proof that we would be able to follow (though not enjoy).

How do we get round this problem? It is not easy to say in detail, but one can certainly identify several commonly occurring features of the statements and proofs that appear in actual mathematics. For example, they usually have a hierarchical structure (this applies to proofs and definitions), they are often adaptations of already existing arguments, and at their best they are based on clearly motivated and understandable ideas.

And what makes a proof "motivated" and "understandable"? I believe that a proof has these qualities when it can be presented as the outcome of an obviously feasible search. There can be non-obvious steps, but there has to be a story of discovery, which is usually something like this:

(1) I tried the natural thing, A, but it didn't work because ... so I was forced to try the more complicated B instead. (And perhaps that didn't work, pushing me yet further to C.)

Occasionally, however, the story may be more like this:

(2) I needed a step that would do Q. Of course, there are lots of potential ways of achieving Q, so I arbitrarily narrowed down my search to T. There was absolutely no guarantee that an argument of the form T would exist, but I could establish whether there was in an afternoon by doing some calculations and seeing if any of them happened to work. To my great pleasure, I came up with the following.

Justifications such as (2) are, to most mathematicians, less satisfying than (1), but they do at least do what I said - present the step as the outcome of a search that could be predicted in advance not to be too long, rather than as an extraordinary gift from heaven.

Now, computers can't solve NP-hard problems either, so where might they have the edge? It will be in discoveries of the form (2), since they will be happy to make much longer searches. Of course, they will have to be careful to restrict their searches as well to avoid combinatorial explosions, but there may well be circumstances where searching through a million possibilities will yield steps that a human would never ever discover.

This, I think, is what Zeilberger means by "deep". He finds justifications of the form (2) far more satisfying than those of the more "linear" form (1). And the bigger the (carefully controlled) search, the "deeper" and less "trivial" the outcome, according to his definition. I do not fully agree with him, because (1)-type search procedures throw up so many interesting challenges and lead to so many beautiful results. I also think that his use of the word "deep" is perverse, since large (2)-style searches are better suited to proofs with a small number of layers (because a long chain of large searches threatens to lead to a combinatorial explosion). But if I have explicated Zeilberger's view correctly, then it is clearly a defensible and non-tautological one. Maybe it is best to say that there is room in mathematics for both kinds of result. Here is a diplomatic view of the theorems Zeilberger discusses. Wiles's proof of FLT is a very deep, multi-layered piece of mathematics indeed, one of the greatest achievements of (1)-type mathematics (though it is perfectly possible that some parts of the edifice were built using mini-(2)-type searches - I don't know about this), while the Appel-Haken proof of the four-colour theorem is one of the supreme achievements of (2)-type mathematics. The first is not trivial, and the second is not boring and uninformative. They just represent different styles.

A final remark. It would be fascinating to find a (2)-style proof of FLT. See this paper of Zeilberger, pages 6 and 7, for a suggestion of how this might be done (a fantasy maybe, but it illustrates very well what he would regard as an ultimately non-trivial proof). Similarly, it would be fascinating to find a (1)-style proof of the four-colour theorem. Zeilberger should not be disappointed if attempts to find such a proof eventually succeed. What is wrong with discovering that some results can be proved in both ways?