A Proof of the Loehr-Warrington Amazing TEN to the Power n Conjecture

By Shalosh B. Ekhad, Vince Vatter and Doron Zeilberger

.pdf   .ps   .tex  
Exclusively published in the Personal Journal of Ekhad and Zeilberger and in Vince Vatter's website .

Written: Sept. 14, 2005.

Last Update of this page: Oct. 1, 2006.

Note added Oct. 1, 2006: We just found out that this masterpiece was narrow-mindedly rejected by Electronic Research Announcements of the American Mathematical Society. Since editing and refereeing is still done by humans, we decided to forgoe publishing in a "real" journal (even an electronic one), and keep this in our respective websites. You may find it instructive and/or amusing to see the referee's stupid report and our response to it.

Some conjectures are irresistable. Nick Loehr and Greg Warrington told Bruce Sagan, who told Vince Vatter, who told me, that they believe that a certain easy-to-describe set of lattice paths are enumerated by 10**n. Such a simple result must be trivial to prove. And sure it is! So what if it took Vince and I a week to write a Maple program, another two weeks to debug it completely, and Shalosh 5 seconds to find a `grammar' in terms of a family (binary) tree with 81 leaves and 80 internal vertices, and another 30 seconds to prove it rigorously. It sure is trivial, at least a posteriori.

Inspired by our proof, Nick and Greg and Bruce Sagan found a `computer-free' proof (for what it is worth), but, more interestingly, they used their humanized approach to generalize it. Stand by for their forthcoming paper. [Once it is ready we will put a link to it here.]

Added Sept. 23, 2005: These humans, with all their flaws, are sometimes surprisingly ingenious. Exactly a week after our article was posted at arXiv.org, the clever human Jonas Sjöstrand found a beautiful bijecive proof of the most general conjecture, thereby even beating Loehr, Sagan, and Warrington. Congratulations, Jonas. Of course, as we mention in remark TEN of our paper, the main point of our paper was to develop and illustrate a methodology of completely computer-generated research, and this methodology should extend to many other cases where the answers are not so beautiful, and hence it is very unlikely that there exist nice human proofs. At any rate we greatly admire Jonas's proof.

Added Oct. 23, 2005: I loved Jonas's proof so much that I wrote an expository article about it in my Personal Journal.

Important: This article is accompanied by Maple package TEN that did everything.
  • For the terse version, you would run, input, and would get output.
  • For the verbose version, you would run, input, and would get output.
  • For the very verbose version, you would run, input, and would get output.
  • For a blow-by-blow, annotated description of the discovery of the grammar, run the input, and would get output.
    Added Sept. 20, 2005: TEN now has a very verbose version, TENverbose, that gives all the details, and makes the proof completely humanly-readable. The input, would yield the very long-winded output.

Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page