Opinion 58: `I Saw Their Proof Now I'm a Believer': The Marcus-Tardos Proof of the Füredi-Hajnal and Stanley-Wilf Conjectures

By Doron Zeilberger

Written: Dec. 3, 2003

Once I thought that proofs of long-standing conjectures had to be difficult. After all didn't brilliant people make them, and didn't these people, and many other brilliant people, unsuccessfully try to prove them? Isn't that a meta-proof that the proof, if it exists, should be long, difficult, and ugly? And if not, shouldn't they, at least, contain entirely new ideas and/or techniques?

Then I saw the proof by Adam Marcus and Gabor Tardos of the Füredi- Hajnal conjecture, that was known, thanks to Martin Klazar, to imply the Stanley - Wilf conjecture. Brilliant people like Noga Alon and Ehud Friedgut came very very close, and the great enumerator Miklos Bona proved it for an important class of permutations. Not to forget yours truly who was sure that one day it would be shown to follow from his pet concept, Enumeration Scheme. I am sure that many other, equally brilliant people, also tried to attack it.

When you read the beautiful one-page proof, you realize that "all" that Marcus and Tardos used were two of the most basic tools of our trade, the pigeon-hole principle, and divide-and-conquer, or equivalently, a take-off of the fact that the sequence a(n):=2n, not only satisfies the linear ("defining") recurrence, a(n)=2*a(n-1), but lots of non-linear recurrences as well: a(n)=a(n/k)k, for any k, and we are free to use the k that suits us. This basic idea is also behind the Fast Fourier Transform and the Renormalization Group method in physics.

But this by no means detracts from their achievement! Quite the contrary. If they would have used heavy guns and/or brand-new methods or thousands of hours of computer time, we would all have had an excuse why we didn't find it ourselves. Their "proof from the book" is so beautiful and compelling in its simplicity, that we are forced to kick ourselves for not coming up with it ourselves.

But let's stop whining and start rejoicing. OK, we didn't score on this one, but there are many fish in the sea. It is very unlikely that the Füredi-Hajnal and Stanley-Wilf conjectures are the only open problems that have nice short proofs using existing methods. [Of course, dear old uncle Paul (Erdös), believed that all problems have such "proofs from the book", but he was an incurable optimist]. We have to resist the natural tendency not to try simple things, assuming that `someone would surely have thought about it before, so why bother?'. It is worth trying, because you never know, and besides, it is fun to try, even if you fail.

Perhaps even RH and P vs. NP have such simple proofs? Probably not! The same thing is true for any specific open problem. But the precedent of the Marcus-Tardos proof (and the Agrawal-Kayal-Saxena primality algorithm, and even de Branges's proof of Bieberbach and Apéry's zeta(3), and there are quite a few other examples), show that, with probability 1-epsilon, there exist quite a few fairly famous open problem that are amenable to simple (but of course, ingenious) arguments in the style of Marcus-Tardos. The meta-problem is: which ones?

So let's get to work, and Keep It Simple Stupid!

P.S.: I loved the Marcus-Tardos proof so much that I wrote a Loving Rendition. Enjoy!
Doron Zeilberger's Opinion's Table of Content

Doron Zeilberger's Homepage