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

%%a Plain TeX file by Manuel Kauers, Christoph 
%%Koutschan and Doron Zeilberger (6 pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\N{{\cal N}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\R{{\cal R}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\def\Tilde{\char126\relax}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{A Proof of George Andrews' and Dave Robbins' q-TSPP 
Conjecture}
\centerline{
{ \eightrm (modulo a finite amount of routine calculations)}
\footnote{$^{1}$}
{\eightrm
Accompanied by Maple packages TSPP and qTSPP available from
\hfill\break
{\eighttt
http://www.math.rutgers.edu/\Tilde zeilberg/mamarim/mamarimhtml/qtspp.html}.
The work of M. Kauers and C. Koutschan was supported in part
by the Austrian FWF grants SFB F1305, P19462-N18, and
P20162-N18. \hfill\break
The work of D. Zeilberger was supported in part
by the United States of America National Science Foundation. 
First Written: Aug. 2, 2008. This version:  Aug. 5, 2008 .
}
}

\rm
\bigskip

\centerline
{By Manuel KAUERS, Christoph KOUTSCHAN, and Doron ZEILBERGER}


\bigskip
\qquad\qquad\qquad\qquad\qquad\qquad
\qquad\qquad\qquad\qquad\qquad\qquad {\it Pour Pierre Leroux, In Memoriam}
\bigskip



{\bf Preface: Montr\'eal, May 1985}

In the historic conference {\it Combinatoire \'Enum\'erative}~[LL]
wonderfully organized by Gilbert Labelle and {\bf Pierre Leroux}
there were many stimulating lectures, including a very interesting one
by Pierre Leroux himself, who talked about his joint work with
Xavier Viennot~[LV], on solving differential equations
combinatorially! 
During the problem session of that very same {\it colloque},
chaired by Pierre Leroux,
Richard Stanley raised some intriguing problems about the
enumeration of plane partitions, that he later expanded
into a fascinating article~[Sta1]. Most of these problems
concerned the enumeration of {\it symmetry classes} of
{\it plane partitions}, that were discussed in more detail
in another article of Stanley~[Sta2].  {\it All} of the
conjectures in the latter article have since been proved
(see Dave Bressoud's modern classic~[B]), {\it except}
one, that, so far, {\it resisted} the efforts of the greatest minds
in enumerative combinatorics. It concerns the proof of an
explicit formula for the $q$-enumeration
of {\it totally symmetric plane partitions}, conjectured independently by
George Andrews and Dave Robbins~([Sta2], [Sta1] (conj. 7),
[B] (conj. 13)). In this tribute to Pierre Leroux,
we describe how to prove that last stronghold.

{\bf $q$-TSPP: The Last Surviving Conjecture About Plane Partitions}

Recall that a {\it plane partition} $\pi$ is an array
$\pi=(\pi_{ij})$, ${i,j \geq 1}$, of positive integers
$\pi_{ij}$ with finite sum $|\pi|=\sum \pi_{ij}$,
which is weakly decreasing in rows and columns.
By stacking $\pi_{ij}$ unit cubes on top of the
$ij$ location, one gets the 3D Ferrers diagram,
that can be identified with the plane-partition,
and is a left-, up-, and bottom- justified structure
of unit cubes, and we can refer to the locations
$(i,j,k)$ of the individual unit cubes.

A plane partition is {\it totally symmetric} iff
whenever $(i,j,k)$ is occupied (i.e. $\pi_{ij} \geq k$),
it follows that all its (up to $5$) permutations:
$\{(i,k,j),(j,i,k),(j,k,i),(k,i,j),(k,j,i)\}$ are
also occupied. In 1995, John Stembridge~[Ste] proved 
Ian Macdonald's conjecture that
the number of totally symmetric plane partitions (TSPPs)
whose $3D$ Ferrers diagram is bounded inside the cube
$[0,n]^3$ is given by the nice product-formula
$$
\prod_{ 1 \leq i \leq j \leq k \leq n} {{i+j+k-1} \over {i+j+k-2}} \quad.
$$
Ten years after Stembridge's completely human-generated proof,
George Andrews, Peter Paule, and Carsten Schneider~[APS] came up
with a {\it computer-assisted} proof, that, however required lots
of human ingenuity and ad hoc tricks, in addition to a considerable
amount of computer time. 

Way back in the early-to-mid eighties (ca. 1983),
George Andrews and Dave Robbins independently conjectured
a {\it $q$-analog} of this formula, namely that the
{\it orbit-counting generating function} ([B], p. 200, [Sta1], p. 289)
is given by
$$
\prod_{ 1 \leq i \leq j \leq k \leq n} 
{
{1-q^{i+j+k-1}}  \over {1-q^{i+j+k-2}}  
}
\quad.
$$

In this article we will show how to prove this conjecture
(modulo a finite amount of routine computer calculations that
may be already feasible today (with great technical effort),
but that would most likely be routinely checkable on a standard
desktop in twenty years).

{\bf Soichi Okada's Crucial Insight}

Our starting point is an elegant reduction, by Soichi Okada~[O],
of the $q$-TSPP statement, to the problem of evaluating
a certain ``innocent-looking'' determinant. This is also listed
as Conjecture~46 (p. 42) in Christian Krattenthaler's celebrated
essay~[K] on the art of determinant evaluation.

{\bf Okada's Determinant} (Shown by Okada to imply the $q$-TSPP conj.)

Let, as usual, $\delta(\alpha,\beta)$ be
the Kronecker delta function
($\delta(\alpha,\beta)=1$ when $\alpha=\beta$ and
$\delta(\alpha,\beta)=0$ when $\alpha \neq \beta$), and let,
also as usual,
$$
\left [ {{a} \atop {b}} \right ]=
{
{(1-q^a)(1-q^{a-1}) \cdots (1-q^{a-b+1})}
\over
{(1-q^b)(1-q^{b-1}) \cdots (1-q)}
} \quad.
$$
Define the discrete function $a(i,j)$ by:
$$
a(i,j)=  q^{i+j-1} \left (
\left [ {{i+j-2} \atop {i-1}} \right ]
+q \left [ {{i+j-1} \atop {i}} \right ] \right )+
(1+q^i)\delta(i,j)-\delta(i,j+1) \quad .
$$
Soichi Okada ([O],~see also [K], Conj.~46) proved that the
following conjectured determinant evaluation would imply
the $q$-TSPP conjecture.

For any nonnegative integer $n$, there holds:
$$
\det(a(i,j))_{1 \leq i,j \leq n}=
\prod_{ 1 \leq i \leq j \leq k \leq n} 
{
\left ( { 1-q^{i+j+k-1}}  \over {1-q^{i+j+k-2}}   \right )^2
}
\quad.
$$
So in order to prove the $q$-TSPP conjecture, all we need is
to prove Okada's conjectured determinant evaluation.

\vfill\eject
{\bf The $q$-Holonomic Ansatz}

In~[Z3], an empirical (yet fully rigorous!) approach is described to
(symbolically!)
evaluate determinants $A(n):=\det (a(i,j))_{1 \leq i, j \leq n}$,
where $a(i,j)$ is a holonomic discrete function of $i$ and $j$. 
Note that this is an {\it approach}, not a method! It is not
guaranteed to always work (and probably usually doesn't!).

Let's first describe this approach in more general terms, not just
within the holonomic ansatz.

Suppose that $a(i,j)$ is given ``explicitly''
(as it sure is here),
and we want to prove for {\it all} $n \geq 0$ that
$$
\det (a(i,j))_{1 \leq i,j \leq n} =Nice(n) \quad,
$$
for some {\it explicit} expression $Nice(n)$ (as it sure is here).

The approach is to
{\it pull out of the hat} another ``explicit''
(possibly in a much broader sense of the word {\it explicit})
discrete function $B(n,j)$, and then verify the
identities
$$
\sum_{j=1}^{n} B(n,j)a(i,j) =0 \quad, \quad (1 \leq i <n < \infty) \quad ,
\eqno(Soichi)
$$
$$
B(n,n)=1  \quad , \quad (1 \leq n < \infty) \quad.
\eqno(Normalization)
$$
If we could do that, then by {\it uniqueness}, it would follow that
$B(n,j)$ equals the co-factor of the $(n,j)$ entry of
the $n \times n$ determinant divided by the $(n-1)\times(n-1)$ determinant
(that is the  co-factor of the $(n,n)$ entry in the $n \times n$ determinant).
Finally one has to prove the identity
$$
\sum_{j=1}^{n} B(n,j) a(n,j)= Nice(n)/Nice(n-1) \quad .
\eqno(Okada)
$$
While~[Z3] was concerned with the holonomic ansatz
([Z1]), everything goes {\it verbatim}
to the $q$-holonomic ansatz. Recall that the nice features
of both the holonomic and $q$-holonomic ansatzes are

(i) They are closed under addition and multiplication .

(ii) It is always algorithmically decidable whether A=B .

(iii) If $F(i_1,i_2, \dots , i_r)$ is a $q$-holonomic function of its
  variables, then 
$$
G(i_1, \dots, i_{r-1}):= \sum_{i_r=-\infty}^{\infty} F(i_1, \dots, i_{r-1},
i_r) 
\quad
$$
is $q$-holonomic in the surviving variables $i_1, \dots , i_{r-1}$.
Furthermore, if one has a $q$-holonomic description of $F$, one
can get a $q$-holonomic description of $G$.

\vfill\eject
{\bf What is a $q$-Holonomic Description?}

A $q$-holonomic discrete function of {\bf one} variable $f(n)$
is determined in  terms of
a {\it linear recurrence equation}
$$
f(n)= \sum_{r=1}^{R} a_r(q,q^n)f(n-r) \quad,
$$
where $a_r(q,q^n)$ are certain rational functions of their arguments,
together with the {\bf initial values} 
$$
f(0), ..., f(R-1) \quad .
$$

Analogously, 
A $q$-holonomic discrete function $f(m,n)$ of {\bf two} variables 
$m$ and $n$ is determined in  terms of
a {\it linear recurrence equation}
$$
f(m,n)= \sum_{r=1}^{R} a_r(q,q^m, q^n)f(m,n-r) \quad,
$$
where $a_r(q,q^m, q^n)$ are rational functions in their arguments,
together with the {\bf initial values} $f(m,0), ..., f(m,R-1)$
that should be given holonomic descriptions on their own right
as holonomic functions of a single variable (as described above).
This can be continued to discrete functions of
any number of variables.

Note that while every holonomic discrete function can be described
as above, not every function that is described as above, with
{\it arbitrary} $a_r$'s is necessarily holonomic (usually it isn't!).
However there are efficient algorithms for deciding whether a candidate
discrete function given as above is holonomic or not. 
One empirical way of doing this is to use the description
to crank many values, and then ``guess'' a pure recurrence with polynomial
coefficients in the other variable, $m$, that can be 
routinely proved {\it a posteriori}.

{\bf The Computational Challenge}

{\it A priori} we don't have a clue whether the normalized
cofactors, let's call them $A'(n,j)$, are $q$-holonomic.
One has to {\it hope}. By cranking out enough values, one
tries to guess a ``$q$-holonomic'' description as above. Without
this guess, there is nothing one can do!

Using several clever tools of the trade in the art of efficient guessing
-a straightforward brute-force approach is hopeless!-we were
able to come up with a conjectured $q$-holonomic description of these
normalized cofactors. It is contained in the Maple package
{\tt qTSPP} accompanying this article. The much easier $q=1$ case
(that would give a new proof to the already proved Stembridge theorem)
is contained in the Maple package {\tt TSPP}.

Note that {\it once} we have a {\it conjectured} $q$-holonomic
description of the normalized cofactors, proving it rigorously
is completely routine. 
Identity $(Soichi)$ is a decidable $q$-holonomic identity and
there exist algorithms of Chyzak, Salvy, and Takayama ([CS], [T])
to prove it. 
Also $(Normalization)$ is automatically satisfied, it being
part of the definition of $B(n,j)$.
Finally $(Okada)$ is also of the form $A=B$ where both
sides are $q$-holonomic. The left side is holonomic because
of the closure under multiplication and definite-summation,
and the right side, $Nice(n)/Nice(n-1)$ is not just $q$-holonomic
(a solution of {\it some} linear recurrence  with polynomial coefficients
(in $q,q^n$) ) but in fact {\it closed-form}
(the defining recurrence is first-order).

{\bf The Semi-Rigorous Shortcut}

We believe that even today, performing the above steps is feasible,
but it would require a huge technical effort. But why bother?
First, if we wait for twenty more years, Moore's Law will probably
enable us to finish up these finitely-many routine calculations
with no sweat. Besides, since now we {\bf know for sure} that
a {\it fully rigorous} proof {\bf exists}, do we really want to
see it? It won't give us any new {\it insight}. The beauty of
the present approach is in the {\it meta-insight}, reducing 
the statement of the conjecture
to a {\it finite} calculation. Furthermore, we know {\it a priori} that
there exists an operator $P(q,q^n,N)$ (where $N$ is the shift operator in $n$:
Nf(n):=f(n+1)) that annihilates the
difference of the left and right sides of $(Okada)$. If that
operator has order $L$, say, then a completely rigorous proof
would be to check $(Okada)$ for $0 \leq n \leq L-1$.
At present, we are unable to find $P$, and hence do not know
the value of $L$. But it is very reasonable that $L$ would be
less than, say, $400$, and checking the first $400$ cases
of $(Okada)$ (and analogously for $(Soichi)$) is certainly
doable (we did it for $L=100$, and $L=400$ for TSPP, but
you are welcome to go further). These are done in procedures
{\tt CheckqTSPP} in the Maple package {\tt qTSPP}, and
{\tt CheckTSPP} in the Maple package {\tt TSPP}, respectively.
The corresponding input and output files can be found
in the webpage of this article mentioned above.
As a technical aside, let's confess that Maple running on our computer
was only able to check (Soichi) and (Okada) for $L \leq 30$, for
{\it symbolic} $q$, but for random numerical choices of $q$ it went
up to $L=100$, and it is easy to see that with sufficiently many
choices of numerical $q$ for a given $L$, one can prove it for
symbolic~$q$.

In 1993, Zeilberger~[Z2] proposed the notion of
{\it semi-rigorous} proof. At the time he didn't have any
{\it natural} examples. The present determinant evaluation,
that was shown by Okada to imply a long-standing open
problem in enumerative combinatorics, is an {\it excellent}
example of a semi-rigorous proof that is (at least) as good 
as a rigorous proof. Let us conclude
by promising that if any one is willing
to pay us \$$10^7$ 
(ten million US dollars), we will be more than glad to fill-in-the details.

{\bf References}

[APS] George E. Andrews, Peter Paule, and Carsten Schneider,
{\it Plane Partitions VI. Stembridge's TSPP theorem},
Adv.Appl.Math. {\bf 34} (2005), 709-739.

[B] David M. Bressoud, {\it ``Proofs and Confirmations''},
Math. Assoc. America and Cambridge University Press (1999).

[CS] Fr\'ed\'eric Chyzak and Bruno Salvy,
{\it Non-commutative elimination in Ore algebras proves
multivariate identities}, J. of Symbolic Computation
{\bf 26} (1998), 187-227.

[K] Christian Krattenthaler, {\it Advanced Determinant Calculus},
S\'em. Lothar. Comb. {\bf 42} (1999), B42q.
(``The Andrews Festschrift'', D. Foata and G.-N. Han
(eds.))

[LL] G. Labelle and P. Leroux (editors),
{\it Combinatoire \'enum\'erative},
Lecture Notes in Mathematics
{\bf 1234}. Springer Verlag, New York.

[LV] Pierre Leroux and G. X. Viennot, 
{\it Combinatorial resolution of systems of differential
equations, I. Ordinary differential equations}.
In {\it Combinatoire \'enum\'erative}, ed.
G. Labelle and P. Leroux. Lecture Notes in Mathematics
{\bf 1234}, 285-293. Springer Verlag, New York.

[O] Soichi Okada, {\it On the generating functions for certain
classes of plane partitions}, J. Comb. Theory, Series A
{\bf 53} (1989), 1-23.

[Sta1] Richard Stanley, {\it A baker's dozen of conjectures concerning
plane partitions}. In {\it Combinatoire \'enum\'erative}, ed.
G. Labelle and P. Leroux. Lecture Notes in Mathematics
{\bf 1234}, 285-293. Springer Verlag, New York.

[Sta2] Richard Stanley, {\it Symmetries 
of plane partitions}, J. Comb. Theory, Series A
{\bf 43} (1986), 103-113.

[Ste] John Stembridge, {\it The enumeration of totally
symmetric plane partitions}, Advances in Mathematics {\bf 111},
227-243 (1995).

[T] Nobuki Takayama, {\it Gr\"obner basis, integration and
transcendental functions}. In ``Proceedings of ISSAC'90'' (1990), 152-156.

[Z1] Doron Zeilberger,
{\it A Holonomic systems approach to special functions
identities}, J. of Computational and Applied Math. {\bf 32},
321-368 (1990).

[Z2] Doron Zeilberger,
{\it Theorems for a price: Tomorrow's semi-rigorous mathematical culture},
Notices of the Amer. Math. Soc. {\bf 40 \# 8}, 978-981 (Oct. 1993).
Reprinted: Math. Intell. {\bf 16}, no. 4, 11-14 (Fall 1994).

[Z3] Doron Zeilberger, {\it The HOLONOMIC ANSATZ II.
Automatic DISCOVERY(!) and PROOF(!!) of Holonomic Determinant Evaluations},
Annals of Combinatorics {\bf 11} (2007), 241-247.

\bigskip

{\bf Manuel Kauers}, Research Institute for Symbolic Computation,
J. Kepler Univ. Linz, Austria. mkauers@risc.uni-linz.ac.at .

\smallskip

{\bf Christoph Koutschan}, Research Institute for Symbolic Computation,
J. Kepler Univ. Linz, Austria. ckoutsch@risc.uni-linz.ac.at .

\smallskip

{\bf Doron Zeilberger}, Mathematics Department, Rutgers University
(New Brunswick), Piscataway, NJ, USA.  zeilberg@math.rutgers.edu .


\end






