A Proof of George Andrews' and Dave Robbins' q-TSPP Conjecture
(modulo a finite amount of routine calculations)

By Manuel Kauers, Christoph Koutschan, and Doron Zeilberger

.pdf     .tex  
Pour Pierre Leroux, In Memoriam
Written: Aug. 2, 2008.
Exclusively published in the Personal Journal of Ekhad and Zeilberger and the arxiv.org .
Added Feb. 24, 2010: Hooray! Yesterday we posted a fully rigororous proof.

We hope that Pierre Leroux would have enjoyed this tribute to him. Not only was he a great "pure" combinatorialist, one of the co-founders of the very abstract theory of species, he was also very interested in symbolic computation, and inspired his students to concretize these abstract species by programming them. While the present article does not talk about species, we are sure that Pierre would have liked it all the same, especially since it tackles a conjecture discussed by Richard Stanley, in the problem session that he chaired, back in May 1985, in the conference so efficiently and warmly organized by him and Gilbert Labelle.

Added Feb. 19, 2009: read the abstract of a talk I gave about this work at the Rutgers Experimental Math seminar.
Important: This article is accompanied by the following two Maple packages
  • qTSPP, that contains the substance of our result, a q-holonomic description of the function B(n,j) of the paper. It is called qB(n,j) in the package. It also contains the procedure CheckqTSPP(N), that empirically verifies identities (Soichi) and (Okada) from the paper for all n &le N, thereby supplying a semi-rigorous proof (the larger N, the better).
  • TSPP, The "ordinary" analog of qTSSP, (semi-rigorously) reproving Stembridge's theorem.

Sample Input and Output

  • Once you have the Maple package qTSPP, and want to emprically check (Soichi) and (Okada) for n ≤ 100, unfortunately, at present (at least on our small computer) you can't use symbolic q, but you can plug-in any numeric value of q and see if you get it right.
  • Once you have the Maple package TSPP, as well as the input file inTSPP400, both in the same directory, staying in that directory, in order to verify (Soichi) and (Okada) for n ≤ 400 doing maple -q < inTSPP400 > oTSPP400 would yield the output.
Added Aug. 6, 2008: We have found a j-free operator ,of the form P(N,J,n), where N and J are the fundamental shift operators in the n and j variables respectively, annihilating B(n,j) (for the q=1 case). This is very encouraging, since it indicates that with a bit of more computation, one should get a j-free operator annihilating the summand of (Soichi) and (Okada) enabling a fully rigorous proof in the style of Sister Celine.

This operator has been added to TSPP, as procedure ManueljFree(n,j); . Procedure CheckManueljFree verifies it empirically for all 1<=j TSPP, as well as the input file inMa500, both in the same directory, staying in that directory, in order to check that the proposed j-free operator does indeed annihilate B(n,j) for 1 ≤ j ≤ n ≤ 500 doing
maple -q < inMa500 > oMa500
would yield the output.

Added June 5, 2009: Christoph Koutschan just won a $300 prize (from my personal funds) that I offered him for extending the method of the present article to get a fully rigorous proof of the q=1 case, i.e. he (and his computer) gave a completely "human-free" proof of Stembridge's so-called TSPP theorem (or rather of the Okada determinant evaluation that was shown by HB (Human Being) Soichi Okada to imply it). Congratulations, Christoph!, and good luck in doing the q-case, and making narrow-minded pedants like the editors of SLC "happy" (aha, of course, they won't be happy, they are happier now that they can claim that we don't "realy" have a proof). Doron Zeilberger's List of Papers

Added Feb. 24, 2010: Hooray! Yesterday we posted a fully rigororous proof.

Doron Zeilberger's Home Page