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!