%---------------------------------------------------------------
% Dec 11, 2003 LaTeX version, submitted to SLC.
%---------------------------------------------------------------
\documentclass[12pt]{amsart}
\usepackage{graphicx}
%\usepackage{latexsym,amscd,amssymb,epsfig}
%\usepackage[dvips]{color}

\theoremstyle{plain}
   \newtheorem{theorem}{Theorem}[section]
   \newtheorem{proposition}[theorem]{Proposition}
   \newtheorem{lemma}[theorem]{Lemma}
   \newtheorem{corollary}[theorem]{Corollary}
   \newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
   \newtheorem{definition}[theorem]{Definition}
   \newtheorem{example}[theorem]{Example}
   \newtheorem{examples}[theorem]{Examples}
   \newtheorem{question}[theorem]{Question}
   \newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

\newcommand\condns[2]{\substack{#1 \\ #2}}
\newcommand\TwoFOne[4]{\,\,{}_2F_1
               \left( \left. \begin{matrix}
                  #1 & #2 \\  & #3 \end{matrix} \right|  #4 \right)}
\newcommand\ThreeFTwo[6]{\,\,{}_3F_2
               \left( \left. \begin{matrix}
                  #1 & #2 & #3 \\  & #4 & #5 \end{matrix} \right|  #6
\right)}
\newcommand\NF[8]{\,\,{}_NF_{N-1}
               \left( \left. \begin{matrix}
                  #1 & #2 & #3&#4 \\  & #5 & #6&#7 \end{matrix} 
\right|  #8
\right)}

\def\naturals{{\mathbf N}}
\def\integers{{\mathbf Z}}
\def\reals{{\mathbf R}}
\def\complexes{{\mathbf C}}
\def\top{{\alpha}}
\def\In{{\mathrm in}}
\def\JH{{\mathcal L}}
\def\EChain{{\mathcal E}}
\def\RChain{{\mathcal R}}
\def\AA{{\mathcal A}}
\def\OO{{\mathcal O}}
\def\PP{{\mathcal P}}
\def\des{\operatorname{des}}
\def\Des{\operatorname{Des}}
\def\Tor{\operatorname{Tor}}
\def\pos{\operatorname{pos}}
\def\Hilb{\operatorname{Hilb}}
\def\pull{\operatorname{pull}}
\def\Ehrhart{\operatorname{Ehrhart}}
\def\Baxter{\operatorname{Baxter}}
\def\width{\operatorname{width}}
\def\rank{\operatorname{r}}
\def\Sym{{\mathfrak S}}
\def\mm{{\mathfrak m}}
\def\eq{{eq}}
\def\sstar{\operatorname{star}}

%--------------------------------------------------


\begin{document}

\title[Charney-Davis quantity for graded posets]
{The Charney-Davis quantity for certain graded posets}

\author{V. Reiner}
\address{School of Mathematics\\
University of Minnesota\\
Minneapolis, MN 55455, USA}
\email{reiner@math.umn.edu}

\author{D. Stanton}
\address{School of Mathematics\\
University of Minnesota\\
Minneapolis, MN 55455, USA}
\email{stanton@math.umn.edu}


\author{V. Welker}
\address{Fachbereich Mathematik und Informatik\\
Philipps-Universit\"at Marburg\\
35032 Marburg, Germany}
\email{welker@mathematik.uni-marburg.de}


\thanks{First, second author supported by NSF grants DMS-9877047, DMS-0203282
respectively.  Third author supported by DFG and European Union grant 
HPRN-CR-2001-00272}

\keywords{Charney-Davis conjecture, Neggers-Stanley conjecture,
alternating permutations, Baxter permutations, Catalan numbers, Franel numbers}

\begin{abstract}
Given a naturally labelled graded poset $P$ with $r$ ranks,
the alternating sum
$$
W(P,-1):=\sum_{w \in \JH(P)} (-1)^{\des(w)}
$$
is related to a quantity occurring in the
Charney-Davis Conjecture on flag simplicial
spheres.  When $|P|-r$ is odd it vanishes.
When $|P|-r$ is even and $P$ satisfies the Neggers-Stanley Conjecture,
it has sign $(-1)^{\frac{|P|-r}{2}}$.

We interpret this quantity combinatorially for several classes
of graded posets $P$,
including certain disjoint unions of chains and products of chains.
These interpretations involve alternating multiset permutations, Baxter
permutations, Catalan numbers, and Franel numbers.
\end{abstract}

\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 50 \rms (2003), Article~B50c\hfill}
\def\thepage{}
%
%

\section{Introduction}
\label{introduction}

We begin by recalling the Neggers-Stanley Conjecture; see \cite{Brenti, ReinerWelker,
Wagner-posets} for background and its current status.  For any poset $P$
on $[n]:=\{1,2,\ldots,n\}$, with order relation denoted $<_P$, let
$\JH(P)$ be the set of its linear extensions, that is,
permutations $w = (w_1,\ldots, w_n)$, for which
$i <_P j$ implies $w^{-1}(i) < w^{-1}(j)$.  The
{\it $P$-Eulerian polynomial}
$$
W(P,t) := \sum_{w \in \JH(P)} t^{\des(w)}
$$
is the generating function for these linear extensions according
to the cardinality of their {\it descent sets}:
$$
\begin{aligned}
\Des(w) &:= \{i \in [n-1] : w_i > w_{i+1} \} \\
\des(w) &:= |\Des(w)|.
\end{aligned}
$$

\begin{conjecture}[Neggers-Stanley] \label{neggers-stanley}
For any poset $P$ on $[n]$ the polynomial
$W(P,t)$ has only real (non-positive) zeroes.
\end{conjecture}

We will mainly be interested in the case where $P$ is
{\it naturally labelled}, that is $i <_P j$ implies $i < j$.
For naturally labelled posets Conjecture~\ref{neggers-stanley} was made
originally by Neggers \cite{Neggers} and proposed in the form above
by Stanley in 1986 (see \cite[\S 2]{Wagner-posets}).

In \cite{ReinerWelker}, it is shown that if $P$ is naturally labelled and {\it graded}
with $r$ ranks (that is, every maximal chain has exactly $r$ elements),
then there exists a simplicial convex polytope of dimension $|P|-r$
whose boundary complex
$\Delta_P$ has its {\it $h$-polynomial} equal to $W(P,t)$.  This implies
that $W(P,t)$ is a polynomial in $t$ of degree $|P|-r$ with
positive, symmetric and unimodal coefficient sequence, and hence that
$W(P,-1)$ vanishes for $|P|-r$ odd.  Furthermore, it turns out that in
some cases 
(e.g. if $P$ has width at most $2$; see \cite[Thm. 3.23]{ReinerWelker}) then 
$\Delta_P$ is a {\it flag} (or {\it clique}) complex.  In this case,
$W(P,t)$ is related to a conjecture of 
Charney and Davis \cite[Conjecture D]{CharneyDavis}
which would imply that
\begin{equation}
\label{CD-inequality}
(-1)^{\frac{|P|-r}{2}} W(P,-1) \geq 0.
\end{equation}

For this reason, we call this conjecturally non-negative
quantity the {\it Charney-Davis quantity} for any graded poset $P$.
It is an easy consequence
(see \cite[Lemma 7.5]{CharneyDavis} or \cite[Proposition
1.4]{ReinerWelker})
of the symmetry of $W(P,t)$ that whenever the Neggers-Stanley
Conjecture holds for $P$, the above Charney-Davis inequality
\eqref{CD-inequality} follows.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL V. REINER, D. STANTON AND V. WELKER}{\SMALL THE 
CHARNEY--DAVIS QUANTITY FOR CERTAIN GRADED POSETS}

This suggests looking for a combinatorial interpretation for
this non-negative integer in these instances.
We give such interpretations for subfamilies of posets of two kinds:
disjoint unions of chains (Section~\ref{disjoint-unions}), and 
products of two chains (Section~\ref{direct-products}).

We should remark that there has been recent interest in the
quantity analogous to $W(P,-1)$ obtained by replacing the descent number
$\des(w)$ with the {\it major index} $\mathrm{maj}(w)$ or the
{\it inversion number} $\mathrm{inv}(w)$;
see \cite{Stanley-sign-balance} and the references therein.
We are not aware of any relation between those results and ours.

We record here one fact that will be useful in what follows.
For any naturally labelled poset $P$ on $[n]$, define
the {\it order polynomial} $\Omega(P,m)$ to be the number of
order-preserving maps from $P$ to an $m$-element chain ${\bf m}$.
Then it is known \cite[Theorem 4.5.14]{Stanley-ECI} that
\begin{equation}
\label{order-poly-gf}
\sum_{m \geq 1} \Omega(P,m) t^m = \frac{tW(P,t)}{(1-t)^{|P|+1}}.
\end{equation}
For the naturally labelled posets which we consider, $\Omega(P,m)$
has a simple enough form to make the above formula useful.

\section{Disjoint unions of chains}
\label{disjoint-unions}

In \cite{Simion}, R. Simion gave the first non-trivial results on the
Neggers-Stanley Conjecture by proving it in the
case $P = {\bf r_1} \sqcup \cdots \sqcup {\bf r_N}$ is
a naturally labelled
disjoint union of $N$ chains ${\bf r_i}$, $i \in [N]$, where
${\bf r_i}$ denotes a chain of $r_i$ elements.

In this case, one can
alternately interpret $W(P,t)$ in terms of rearrangements of a multiset
as follows.  Let  $1^{r_1} \cdots N^{r_N}$ denote a multiset of letters
containing $r_i$ occurrences of the letter $i$ for each $i \in [N]$,
and let $\Sym(1^{r_1} \cdots N^{r_N})$ denote the set of all
rearrangements $w=w_1 w_2 \cdots w_n$
of these letters, where $n= \sum_{i=1}^N r_i$.
Then there is an obvious bijection between
$\JH({\bf r_1} \sqcup \cdots \sqcup{\bf r_N})$
and $\Sym(1^{r_1} \cdots N^{r_N})$, having the property that descents 
in a
permutation
in $\JH(P)$ correspond to (strict) descents $w_i > w_{i+1}$ in
the rearrangement $w$.  Thus
$$
W({\bf r_1} \sqcup \cdots \sqcup {\bf r_N}, t)
= \sum_{w \in \Sym(1^{r_1} \cdots N^{r_N})} t^{\des(w)}.
$$


We are mostly interested in the case where $P$ is a {\it graded}
disjoint union of chains, that is $N$ chains each having $r$ elements;
call this poset $P_{N,r}$.  Note that $P_{N,r}$ has an explicit formula for
its order polynomial, namely
$$
\Omega(P_{N,r},m) = \binom{r+m-1}{m-1}^N = \binom{r+m-1}{r}^N.
$$
Hence formula \eqref{order-poly-gf} yields in this case that
\begin{equation}
\label{Wchain}
\begin{aligned}
W(P_{N,r},t)&=(1-t)^{Nr+1}\sum_{m \geq 0} \binom{r+m}{m}^N t^m\\
&= (1-t)^{Nr+1}\NF{r+1,}{r+1,}{\cdots,}{r+1}{1,}{\cdots,}{1}{t}.
\end{aligned}
\end{equation}
where ${}_rF_s$ denotes the usual hypergeometric function \cite[Chapter
2]{Bateman}.


We start with small values of $r$.
If $r=1$ then $P_{N,1}$ is an antichain on $[N]$.  In this case
$W(P_{N,1},t) = \sum_{ w \in \Sym_N} t^{\des(w)}$ is (essentially)
the classical {\it Eulerian polynomial}, whose exponential generating
function

\begin{equation}
\label{classical-Eulerian-polynomial}
\sum_{N \geq 0} W(P_{N,1},t) \frac{u^N}{N!} =
\frac{(1-t)e^{u(1-t)}}{1-t e^{u(1-t)}}.
\end{equation}
is well-known, and can be derived easily from \eqref{Wchain}.

Setting $t=-1$ gives the exponential generating function
$$
\begin{aligned}
\sum_{N \geq 0} W(P_{N,1},-1) \frac{u^N}{N!} &=
\sum_{N \geq 0} \sum_{w \in \Sym_N} (-1)^{\des(w)} \frac{u^N}{N!} \\
&= \frac{2e^{2u}}{1+e^{2u}} = 1+\tanh(u).
\end{aligned}
$$
This implies that for $N$ odd (so $|P|-r=N-1$ is even) the Charney-Davis
quantity $(-1)^{\frac{N-1}{2}} W(P_{N,1},-1)$
is the {\it Euler number} $E_{N}$.  The Euler number $E_N$ counts
the number of {\it alternating permutations} $w \in
\Sym_N$,
that is, those permutations with $\Des(w) = \{2,4,\ldots\}$;
see \cite[\S 3.16]{Stanley-ECI}.
The authors thank Ira Gessel for pointing out the following
proof of this fact by a sign-reversing involution.

\smallskip

\begin{proposition} ~
\label{SRI-for-r=1}

There is an involution $\iota: \Sym_N \rightarrow \Sym_N$ satisfying:
\begin{enumerate}
\item[$\bullet$] $\des(\iota(w)) = \des(w) \pm 1$ if $\iota(w) \neq w$,
\item[$\bullet$] if $N$ is even then $\iota$ has no fixed points, and
\item[$\bullet$] if $N$ is odd then
$\iota(w) = w \Leftrightarrow w$ is an alternating permutation.
\end{enumerate}

In particular, the following identity holds:
$$
W(P_{N,1},-1)=\sum_{w \in \Sym_N}  (-1)^{\des(w)} =
\begin{cases}
(-1)^{\frac{N-1}{2}} E_N  &\text{for }N\text{ odd,} \\
0 & \text{for }N\text{ even.}
\end{cases}
$$
\end{proposition}
\begin{proof}
We recall a standard encoding of permutations $w \in \Sym_N$
as {\it decreasing binary trees} on vertex set $[N]$, that is
planar binary trees in which the labels along any path away from the
root are decreasing (cf. \cite[\S 1.3]{Stanley-ECI}).
In this encoding we choose the largest letter in $w$ as the root vertex
and divide $w$ into a left subword consisting of those letters to the
left of the largest letter and an analogously defined
right subword. The left and right subtree of the root are
then obtained by applying the same procedure recursively to the left
and right subword.

Under this correspondence, complete binary trees
(those in which every non-leaf has both
left and right subtrees non-empty) correspond to alternating 
permutations.
To define $\iota$ on each {\it incomplete} binary tree, find the smallest
labelled
vertex having exactly one of its left and right subtrees non-empty,
and exchange the empty subtree for the non-empty one.  It is easy to see
this
either removes or creates exactly one descent.
\end{proof}

An intriguing variation holds when $r=2$.
Generalizing the definition of alternating permutations from sets to
multisets, call a multiset permutation $w \in \Sym(1^{r_1} \cdots
N^{r_N})$
{\it alternating} if
$$
w_1 \leq w_2 > w_3 \leq w_4 > \cdots,
$$
that is if $\Des(w) = \{2,4,\ldots\}$.  Such multiset permutations
were studied by Carlitz \cite{Carlitz}.

\begin{theorem}
\label{SRI-for-r=2}
~


There is an involution $\iota: \Sym(1^2 2^2 \cdots N^2) \rightarrow
\Sym(1^2 2^2 \cdots N^2)$ satisfying:
\begin{enumerate}
\item[$\bullet$] $\des(\iota(w)) = \des(w) \pm 1$ if $\iota(w) \neq w$, and
\item[$\bullet$] $\iota(w) = w \Leftrightarrow w$ is an alternating
permutation.
\end{enumerate}

In particular, the following identity holds:
$$
\begin{aligned}
(-1)^{N-1}W(P_{N,2},-1)&=(-1)^{N-1}\sum_{w \in \Sym(1^2 2^2 \cdots N^2)}
(-1)^{\des(w)} \\
&= \#\{\text{alternating }w \in \Sym(1^2 2^2 \cdots N^2)\}.
\end{aligned}
$$
\end{theorem}

\noindent
Note that the sign $(-1)^{N-1}$ appearing in the proposition
is the appropriate sign $(-1)^{\frac{|P|-r}{2}}$ for the
Charney-Davis quantity, as $|P|-r=2N-2$.
\begin{proof}
Given $w \in \Sym(1^2 2^2 \cdots N^2)$, append a $0$ to its right,
creating a multiset permutation $\hat{w}\in \Sym(0^1 1^2 2^2 \cdots N^2)$
that ends with $0$.  As in the proof of Proposition~\ref{SRI-for-r=1},
encode
$\hat{w} \in \Sym(01^2 2^2 \cdots N^2)$ as a decreasing binary tree on
vertices
labelled $0,1,1,2,2,\ldots,N,N$, with root labelled by the {\it 
rightmost}
occurrence of the largest value, defining left and right subtrees
recursively.
Here {\it decreasing} is modified to mean that labels only weakly
decrease along edges from a parent to its left-child, but strictly
decrease along
edges from a parent to its right-child.

One can then define an involution $\iota$ as in the proof of
Proposition~\ref{SRI-for-r=1}, by finding the smallest labelled vertex
having only a left or right-subtree but not both, in which it is {\it
possible}
to switch it from left to right or vice-versa.  When this is possible,
it is easy to see that this creates or destroys exactly one descent.

As before, the alternating permutations $w$ exactly correspond to 
complete
decreasing binary trees;  the $0$ vertex will always occur to the far
right,
creating an extra descent $w_{2N} > 0$ as a right-child to $w_{2N}$.
But there will also be other fixed points $w$.  These will correspond to
incomplete trees in which there is at least one non-leaf vertex,
labelled $i$ for some $i \in [N]$,
which cannot do the switch required for $\iota$ because of one of
two possible types of violations:
\begin{enumerate}
\item[{\sf Type 1:}]  $i$ has left-child also labelled $i$, and empty
right subtree,
\item[{\sf Type 2:}] $i$ has $0$ contained somewhere in its right 
subtree,
and empty left subtree.
\end{enumerate}
It is possible to pair up {\sf Type 1} and {\sf Type 2} violations as
follows.
Note that it is impossible for a value $i$ to label both a {\sf Type 1}
and {\sf Type 2} violator.  Let $i$ be the smallest labelled
vertex among all violators of both types.

If $i$ labels a {\sf Type 1} violator, contract the edge between the
parent
and left-child vertices labelled $i$, while inserting a vertex labelled
$i$ at the appropriate place in the decreasing sequence of right-children
one encounters in reading downward to the right from the root $N$ to
the $0$ vertex. This adds one descent to $w$ arising from this decreasing
sequence,
while affecting no other descents.

If $i$ labels a {\sf Type 2} violator, remove the vertex labelled $i$
which
has $0$ in its right subtree, replacing it with an edge directly
connecting
its former parent to its former right child.
Meanwhile, replace the other vertex labelled $i$
with an edge between a parent labelled $i$ and left-child labelled $i$,
giving both of its former subtrees to the left-child $i$, and giving no
right subtree
to the parent $i$.  This removes one descent.
\end{proof}

\begin{remark}
In light of Proposition~\ref{SRI-for-r=1} and Theorem \ref{SRI-for-r=2},
one might hope that for general $N, r$ the Charney-Davis quantity
$$
(-1)^{\frac{r(N-1)}{2}}\sum_{w \in \Sym(1^r 2^r \cdots N^r)}
(-1)^{\des(w)}
$$
could be interpreted as
\begin{equation*}
\label{tempting-interpretation}
\begin{cases}
        \#\{\text{alternating perms }w \in \Sym(1^r 2^r \cdots N^r)\}
       & \text{ for }r(N-1)\text{ even,} \\
     0 & \text{ for }r(N-1)\text{ odd}.
\end{cases}
\end{equation*}
Unfortunately, this fails already for $r=3, N=3$.
\end{remark}

\vskip .1in

Having looked at cases where $r$ is small, we turn to those where $N$ is
small.
If $N=1$, then $P_{N,r}$ is a chain, so everything is trivial.
When $N=2$, one has the following proposition.

%Note that by the theory of Hibi-rings $W(P_{2,r},t)$ actually
%coincides with the h-polynomial of the determinantal ring of
%$(2 \times 2)$-minors of a square matrix and hence the result is a special
%case of \cite{ConcaHerzog}.
%
%On the other hand, it also coincides with the rank-generating function
%of the type B-non-crossing partition lattice, and with the h-polynomial of
%the cyclohedron (the type B associahedron or Fomin-Zelevinsky polytope)
%So there are a lot of connections here that we are not mentioning.

\begin{proposition}
\label{N=2-prop}
$$
W(P_{2,r},t) = \sum_{k=0}^r \binom{r}{k}^2 t^k,
$$
and
$$
W(P_{2,r},-1)=
\begin{cases}
    (-1)^{\frac{r}{2}}\binom{r}{\frac{r}{2}} & \text{ for }r\text{ even},
\\
    0                                        & \text{ for }r\text{ odd}.
\end{cases}
$$
\end{proposition}
\begin{proof} Although various easy combinatorial proofs can be given for
both assertions (e.g. \cite[Vol. 1, \S144, p. 169]{MacMahon}), 
they also follow from \eqref{Wchain}  and Lemma \ref{2F1lemma}
with $a_1=a_2=1$.
%
%We can also give a combinatorial proof.
%Multiset permutations $w \in \Sym(1^r 2^r)$ biject with
%pairs of subsets $(S, T)$ of $[r]$ having equal cardinality:
%given $w$, extend it to
%$$
%\hat{w}: = 1 w_1 w_2 \cdots w_{2r-1} w_{2r} 2
%$$
%and define
%$$
%\begin{aligned}
%S &:=\{ i \in [r]: i^{th} \text{ occurrence of }1\text{ in }\hat{w}
%                 \text{ is followed by a }2\} \\
%T &:=\{ i \in [r]: i^{th} \text{ occurrence of }2\text{ in }\hat{w}
%                 \text{ is followed by a }1\}. \\
%\end{aligned}
%$$
%It is straightforward to check that this is a bijection.
%As $\Des(w) = T$, the assertion follows.
\end{proof}

For $N=3$, one has the following result.
\begin{theorem}
\label{Stanton-result}
$$
W(P_{3,r},-1)  =
    (-1)^{r} \sum_{k=0}^r \binom{r}{k}^3.
$$
\end{theorem}

\begin{proof} This follows from \eqref{Wchain}  and Lemma \ref{3F2lemma}
with $a_1=a_2=a_3=1$.
\end{proof}

\begin{remark}
The sum of the cubes of the binomial coefficients appearing in
Theorem \ref{Stanton-result}
have appeared in the literature under the name {\it Franel numbers}
\cite{Franel1, Franel2}.
We remark that Proposition~\ref{N=2-prop} can be phrased in
suggestively similar terms, using the identity
$\binom{r}{\frac{r}{2}} = \sum_{k=0}^{\frac{r}{2}}
\binom{\frac{r}{2}}{k}^2$.
However, for $N=4$, there does not appear to be a connection between the
quantities
$$
\sum_{w \in \Sym(1^r 2^r 3^r 4^r)} (-1)^{\des(w)}
\text{ and }
\sum_{k=0}^r \binom{\frac{r}{2}}{k}^4.
$$
\end{remark}






\begin{remark}
MacMahon gave two generating functions for the polynomials
$W({\bf r_1} \sqcup \cdots \sqcup {\bf r_N}, t)$, which we state here;
the authors thank Ira Gessel for pointing out these results.
Recall that the elementary
symmetric function in $N$ variables is denoted $e_k(x_1,\cdots,x_N)$.

\begin{proposition}\cite[pp. 186, 212]{MacMahon}
$W({\bf r_1} \sqcup \cdots \sqcup {\bf r_N}, t)$
is the coefficient of $x_1^{r_1}\cdots x_N^{r_N}$ in
$$
(1-\sum_{k=1}^N e_k(x_1,\cdots, x_N) (t-1)^{k-1})^{-1},
$$
and it is also the same coefficient in
$$
\prod_{i=1}^N (x_1+\cdots+x_i+t(x_{i+1}+\cdots+x_N))^{r_i}.
$$
\end{proposition}

Thus  $W(P_{3,r},-1)$ is the coefficient of
$x^r y^r z^r$ in
$$
(x+y+z)^r (x+y-z)^r (x-y-z)^r \quad or \quad (1-e_1+2e_2-4e_3)^{-1}.
$$
One would like a simple bijective proof of Theorem~\ref{Stanton-result},
perhaps via the fact that $\sum_{k=0}^r \binom{r}{k}^3$ is the 
coefficient
of $x^r y^r z^r$ in $$(x+y)^r (x+z)^r (y+z)^r,$$ but
we have no such proof so far.
\end{remark}


\section{Direct Product of Chains}
\label{direct-products}
The direct product $P = {\bf r} \times {\bf s}$ of chains
of size $r, s$ is a prime example of a {\it Gaussian poset}
\cite[Exercise 4.25]{Stanley-ECI}.
Brenti proved the Neggers-Stanley conjecture for naturally labelled Gaussian posets
\cite[Theorem 5.6.5]{Brenti}, using the fact that their order polynomial
has the following simple expression in terms of their rank function
$\rank(x)$:
\begin{equation}
\label{Gaussian-identity}
\Omega(P,m) = \prod_{x \in P} \frac{m + \rank(x)}{1 + \rank(x)}.
\end{equation}
In this subsection, we examine combinatorial
interpretations for the Charney-Davis
quantity of $P={\bf r} \times {\bf s}$ for small values of $s$.

For these particular Gaussian posets, combining
\eqref{order-poly-gf} with \eqref{Gaussian-identity} yields the
expression
\begin{equation}
\label{chain-product-W}
W({\bf s} \times {\bf r},t) =
(1-t)^{rs+1}
   \sum_{m \geq 0} \prod_{i=1}^{s} \frac{(i+m)_r}{(i)_r} t^{m}
\end{equation}
where $(a)_r:=(a)(a+1)\cdots(a+r-1)$.

If $s = 1$ then ${\bf s} \times {\bf r} \cong {\bf r}$ is a chain, so
everything
is trivial.

If $s=2$, renaming $r=n$, the identity
$$
W({\bf 2} \times {\bf n},t) =
\sum_{k = 0}^{n-1} \frac{1}{n}\binom{n}{k}\binom{n}{k+1} t^k
$$
can be deduced either from \eqref{chain-product-W} and the first
equality in Lemma \ref{2F1lemma} specialized to $a_1=2, a_2=1$,
or using the standard interpretation for the {\it Narayana number}
$\frac{1}{n}\binom{n}{k}\binom{n}{k+1}$ as
the number of lattice paths from $(0,0)$ to $(n,n)$ taking north or east
steps
which stay weakly above the diagonal $y=x$ and have exactly $k$
right turns \cite[Problem 6.36]{Stanley-ECII}.
The Charney-Davis quantity in this case can be evaluated
using the second equality of Lemma \ref{2F1lemma} specialized
to $a_1=2, a_2=1$
(see also \cite[\S4]{LeungReiner}):
\begin{proposition}
\begin{equation*}
\label{chain2xr}
W({\bf 2} \times {\bf n},-1)=
\begin{cases}
0 & \text{ for } n \text{ even,} \\
(-1)^m C_m
   & \text{ for } n = 2m+1 \text{ odd}.
\end{cases}
\end{equation*}
where $C_m= \frac{1}{m+1} \binom{2m}{m}$ is the Catalan number.
\end{proposition}

For $s = 3$, Baxter permutations come into play.
A permutation $\pi = \pi_1 \cdots \pi_n \in S_n$ is called a
{\it Baxter permutation} if for all
$1 \leq i < j < k < l \leq n$ the following two conditions are satisfied:

\begin{itemize}
\item[$\triangleright$] if $\pi_i + 1 = \pi_l$ and $\pi_j > \pi_l$ then
$\pi_k > \pi_l$,
\item[$\triangleright$] if $\pi_l + 1 = \pi_i$ and $\pi_k > \pi_i$ then
$\pi_j > \pi_i$.
\end{itemize}

In \cite{CGHK} it was shown that there are exactly
$$
\begin{aligned}
\Baxter(n):&=\frac{1}{\binom{n+1}{1} \binom{n+1}{2}}\sum_{m=0}^{n-1}
\binom{n+1}{m} \binom{n+1}{m+1} \binom{n+1}{m+2}\\
&=\ThreeFTwo{1-n,}{-n,}{-1-n}{2,}{3}{-1}
\end{aligned}
$$
Baxter permutations in $\Sym_n$.


The following result was discovered by computer experimentation.

\begin{theorem}
\label{chain3xr}
$$
W({\bf 3} \times {\bf n},-1) = (-1)^{n-1} \Baxter(n-1).
$$
\end{theorem}
\begin{proof} When $s=3$, one has from \eqref{chain-product-W} that
$$
\begin{aligned}
\frac{t W({\bf 3} \times {\bf n},t)}{(1-t)^{3n+1}}
   &= \sum_{ m \geq 1} t^m \frac{(m)_n (m+1)_n (m+2)_n}{(1)_n (2)_n (3)_n}
\\
   &= t \ThreeFTwo{n+3,}{n+2,}{n+1}{2,}{3}{t}.
\end{aligned}
$$
Applying Lemma \ref{3F2lemma} with $a_1=3, a_2=1, a_3=2$ we have
$$
\begin{aligned}
W({\bf 3} \times {\bf n},-1)
  &= (-1)^{n-1} \ThreeFTwo{2-n,}{1-n,}{-n}{2,}{3}{-1}\\
&=(-1)^{n-1}\Baxter(n-1).
\end{aligned}
$$
\end{proof}

\begin{remark} \rm \ \\
  The previous theorem begs for a combinatorial proof. 
$W({\bf 3} \times {\bf n},t)$ is the generating function for
standard Young tableaux of shape $3 \times n$ counted by their
number of descents.   Dulucq and Guibert \cite{DulucqGuibert} 
have shown that $\Baxter(n-1)$ counts those
standard Young tableaux of shape $3 \times (n-1)$ having no
consecutive values in the same row.  We were unable to find
a combinatorial proof based on these tempting facts.
\end{remark}

\begin{remark} \rm \ \\
%The following table lists a few of the first few
%values of the Charney-Davis quantity for direct products
%$\underbrace{{\bf r} \times \cdots \times
%{\bf r}}_{N~times}$, computed with the help of the Maple {\tt posets}
%package
%by Stembridge \cite{stembridge}.
%
%\begin{center}
%$$
%\begin{array}{|r|rrrr|}
%\hline
%r \backslash  N &    2  &        3 &   4 & 5 \\
%\hline
%2     &    0  &        4 &   0 & 18428170583040 \\
%3     &    2  & 80643222 &  ?? & ?? \\
%\hline
%\end{array}
%$$
%\end{center}
%
%\centerline{Table 1. The Charney-Davis quantity for $\underbrace{{\bf r}
%\times \cdots \%times {\bf r}}_{N~times}$}
%
From \eqref{Wchain} and \eqref{chain-product-W}, one can write down 
explicit double sums for the polynomials $W(P,t)$ when
$P=P_{N,r}$ or $P={\bf r} \times {\bf n}$.
Unfortunately, even when one sets $t=-1$, these double sums
involve alternating signs, and hence don't explain the sign of
the associated Charney-Davis quantity $W(P,-1)$.  More temptingly,
both for $P=P_{4,r}$ and $P={\bf 4} \times {\bf r}$,
it is possible to re-express $W(P,-1)$ in terms of a single sum,
provable using the $WZ$-method.  We state here (without proof)
the explicit answer for $P=P_{4,r}$.  If $r$ is odd then $W(P_{4,r},-1) =0$.
For $r$ even, setting $R=\frac{r}{2}$, one has 
$$
W(P_{4,r},-1) = (-1)^{R} 
  \sum_{k=0}^r (-1)^k \, 2^{2r-2k} \,
         \binom{r+k}{k,k,r-k} \binom{r+2k}{R,k,R+k}.
$$
%
%and for $r$ odd,
%$$
%W({\bf 4} \times {\bf r},-1) =
%     (-1)^{R}
%          \sum_{k=0}^{r-1}(-1)^k \, 2^{2r-2k-2} \,
%         \frac{\binom{r+k-1}{k, \, k, \, r-k-1}\binom{r+2k+2}{R,\, k+2,\, R+k+1}}
%            {\binom{r+2}{2}\binom{r+3}{4}}
%$$
Note that this single sum of integer terms involves
alternating signs.  However, an anonymous referee pointed out
that this can be rewritten.
Applying a ${}_3F_2(1)={}_4F_3(1)$ hypergeometric transformation,
which is a limit of Singh's $q$-quadratic ${}_4\phi_3$-transformation 
\cite[(III.21), p. 243]{GasperRahman}),
one obtains
$$
W(P_{4,r},-1) = (-1)^{R} \binom{r}{R}
  \sum_{k=0}^R \binom{r}{2k} 
     \left( 
           \frac{1}{k!}\left( \frac{r+1}{2} \right)_k 2^{2k}
     \right)^2 2^{2r-4k},
$$
a summation with positive integer summands.
Unfortunately, we have no conjecture for
a combinatorial interpretation in this case. 
Similarly, for $W({\bf r_1} \times \cdots \times {\bf r_N},-1)$ with
$N \geq 3$, we have no such combinatorial interpretation.
\end{remark}

\medskip


%  For the sake of record-keeping, we write down some single
% summations that Dennis came up with for W(P_{4,r},-1), and
% for W(4 x r, -1), even though they don't have an obvious sign...
%
%******
%A single sum for the CD quantity for a union of 4 disjoint chains each 
%with r elements, r even,
%
%(-1)^{r/2}*\sum_{k=0}^r (r+k choose k,k,r-k)*(r+2k choose 
%r/2,k,r/2+k)*2^{2r-2k}*(-1)^k
%
%They are
%
%1,-104, 88536, -108415040, 155722204120,....
%
%proven by WZ
%
%*******
%
%A single sum for the CD quantity for a product of 4\times r,   r  odd, 
%R=(r-1)/2
%
%(-1)^{R}*\sum_{k=0}^{r-1} (r+k-1 choose k,k,r-k-1)*(r+2k+2 choose 
%R,k+2,R+k+1)*2^{2r-2k-2}*(-1)^k
%/(r+2 choose 2)*(r+3 choose 4).
%
%They are
%
%1,-6, 580, -145362, 59723496, -33365926704, ....
%
%proven by algorithm Zb
%



\section{Appendix: Hypergeometric lemmas}

In this appendix we collect the lemmas for the proofs in the previous
sections.

\begin{lemma}
\label{2F1lemma}
Let $r, a_1,$ and $a_2$ be non-negative
integers with $r+a_2-1\ge a_1-a_2\ge 0.$ Then
$$
\begin{aligned}
p_r(t)=&(1-t)^{2r+2a_2-1}\TwoFOne{r+a_1,}{r+a_2}{1+a_1-a_2}{t}\\
=&\binom{r+a_2-1}{a_1-a_2}^{-1}
\sum_{s=0}^{r+a_2-1}\binom{r-a_2+1}{s}\binom{r+a_2-1}{a_1-a_2+s}t^s\\
=&\sum_{s=0}^{(r+2a_2-a_1-1)/2} \binom{r+2a_2-a_1-1}{2s} \times \\
& \qquad \qquad \qquad \qquad
\frac{(2s)!}{s!(1+a_1-a_2)_s}  t^s(1+t)^{r+2a_2-a_1-1-2s}.
\end{aligned}
$$
\end{lemma}

\begin{proof} The first statement is Euler's transformation
\cite[p. 105, (2)]{Bateman}  while the second is a quadratic
transformation
\cite[p. 113, (35)]{Bateman}.
\end{proof}

\begin{lemma}
\label{3F2lemma}
Let $r,$ $a_1,$ $a_2,$ and $a_3$ be non-negative integers with
$$a_1\ge a_3\ge a_2,\quad  r+a_2+a_3\ge a_1+1.$$
If
$$
\begin{aligned}
&f_r(t)=\\
&(1-t)^{3r-2-a_1+2a_2+2a_3}
\ThreeFTwo{r+a_1,}{r+a_2,}{r+a_3}{1+a_1-a_2,}{1+a_1-a_3}{t},
\end{aligned}
$$
then $f_r(t)$ is a polynomial in $t$ of degree $2r-2-2a_1+2a_2+2a_3$.
Moreover
$$
\begin{aligned}
&f_r(-1)=\\
&C\ThreeFTwo{1+a_1-2a_2-r,}{1-a_2-r,}
{1-a_3+a_1-a_2-r}{1+a_1-a_2,}{1+a_3-a_2}{-1},
\end{aligned}
$$
where
$$
C= (-1)^{r+a_1+a_2+a_3+1}
\frac{(1+a_3-a_2)_{r+a_3+a_2-a_1-1}}{(1+a_1-a_3)_{r+a_3+a_2-a_1-1}}.
$$
\end{lemma}
\begin{proof} If we apply the well-poised ${}_3F_2$ transformation
\cite[p. 190, (1)]{Bateman} we have
$$
\begin{aligned}
&f_r(t)=(1-t)^{2r-2-2a_1+2a_2+2a_3}\times\\
&\ThreeFTwo{(r+a_1)/2,}{(r+a_1+1)/2,}{1+a_1-a_2-a_3-r}{1+a_1-a_2,}{1+a_1-a_3}
{\frac{-4t}{(1-t)^2}},
\end{aligned}
$$
which establishes polynomiality of $f_r(t)$, and shows that $f_r(-1)$
is a ${}_3F_2(1).$

We apply two ${}_3F_2(1)$ transformations to derive the second part of
Lemma \ref{3F2lemma}. First use \cite[p. 98, Ex. 7]{Bailey}
$$
\begin{aligned}
&\ThreeFTwo{a,}{b,}{c}{d,}{e}{1}\\
&=
\frac{\Gamma(e) \Gamma(e+d-a-b-c)}{\Gamma(e-c) \Gamma(d+e-a-b)}
\ThreeFTwo{d-a,}{d-b,}{c}{d,}{d+e-a-b}{1}
\end{aligned}
$$
with 
$$
\begin{aligned}
a &=(r+a_1)/2\\
b &=(r+a_1+1)/2\\
c &=1+a_1-a_2-a_3-r\\
d &=1+a_1-a_2\\
e &=1+a_1-a_3.
\end{aligned}
$$
Then use the terminating transformation \cite[p. 21,
(1)]{Bailey}
$$
(d)_N \ThreeFTwo{a,}{b,}{-N}{c,}{1-d-N}{1} =
(a+d)_N \ThreeFTwo{a,}{c-b,}{-N}{c,}{a+d}{1}
$$
with 
$$
\begin{aligned}
a &=1+a_1/2-a_2-r/2\\
b &=1+a_1-a_2-a_3-r\\
N &=r/2+a_2-a_1/2-1/2\\
c &=1+a_1-a_2\\
1-d-N &=3/2+a_1-a_2-a_3-r.
\end{aligned}
$$
\end{proof}

\section*{Acknowledgments}

The authors thank Ira Gessel, Olivier Guibert and an anonymous referee
for helpful comments.


\begin{thebibliography}{99}

\bibitem{Bailey}
W.N. Bailey,
{\it Generalized Hypergeometric Series}.
{\it Cambridge Tracts in Math. and Math. Phys.} {\bf 32},
Cambridge University Press, 1935.


\bibitem{Brenti}
F. Brenti, {\it Unimodal, Log-Concave and Polya Frequency Sequences
in Combinatorics}.
{\it Memoirs Amer. Math. Soc.} {\bf 413},
Amer. Math. Soc., Providence, 1989.


\bibitem{Carlitz}
L. Carlitz,
Enumeration of up-down sequences.
{\it Discrete Math.} {\bf 4} (1973), 273--286.

\bibitem{CharneyDavis}
R. Charney and M. Davis,
Euler characteristic of a nonpositively curved, piecewise Euclidean
manifold.
{\it Pac. J. Math.}, {\bf 171} (1995), 117--137.

\bibitem{CGHK}
F.R.K. Chung, R.L. Graham, V.E. Hoggatt, and M. Kleiman,
The number of Baxter permutations.
{\it J. Combin. Theory Ser. A} {\bf 24} (1978), 382--394.

\bibitem{Bateman}
A. Erd\'elyi, W. Magnus, F. Oberhettinger, and F.G. Tricomi,
{\it Higher Transcendental Functions}. Vol. I. Based on
notes left by Harry Bateman. McGraw-Hill, 1953.

%\bibitem{ConcaHerzog}
%A. Conca, J. Herzog,
%On the Hilbert function of determinantal rings and their canonical module. 
%{\it Proc. Amer. Math. Soc.} {\bf 122} (1994) 677--681.

\bibitem{DulucqGuibert}
S. Dulucq and O. Guibert,
Stack words, standard tableaux and Baxter permutations.
Proceedings of the 6th Conference on Formal 
Power Series and Algebraic Combinatorics (New Brunswick, NJ, 1994). 
{\it Discrete Math.} {\bf 157} (1996), 91--106.



\bibitem{Franel1}
J. Franel, On a question of Laisant.
{\it L'interm\'ediaire des math\'ematiciens} {\bf 1}(1894), 45--47.

\bibitem{Franel2}
J. Franel, On a question of J. Franel.
{\it L'interm\'ediaire des math\'ematiciens} {\bf 2}(1895), 33--35.

\bibitem{LeungReiner}
N.C. Leung and V. Reiner,
The signature of a toric variety.
{\it Duke Math. J.} {\bf 111} (2002), 253--286.

\bibitem{GasperRahman}
G. Gasper and M. Rahman,
{\it Basic hypergeometric series.} 
{\it Encyclopedia of Mathematics and its Applications} {\bf 35},
Cambridge University Press, Cambridge, 1990. 

\bibitem{MacMahon}
P.A. MacMahon, {\it Combinatory Analysis -- Two Volumes in One},
Chelsea Publishing, New York 1960.

\bibitem{Neggers}
J. Neggers, Representations of finite partially ordered sets.
{\it J. Comb. Inf. Syst. Sci.} {\bf 3} (1978), 113--133.

\bibitem{ReinerWelker}
V. Reiner and V. Welker, On the Charney-Davis and
Neggers-Stanley conjectures.  Available at
{\tt http://www.math.umn.edu/\~{}reiner}.

\bibitem{Simion}
R. Simion,
A multiindexed Sturm sequence of polynomials and unimodality of certain
combinatorial sequences.
{\it J. Comb. Theory, Ser. A} {\bf 36} (1984), 15--22.

\bibitem{Stanley-ECI}
R.P. Stanley,
{\it Enumerative Combinatorics, Vol. 1}.
{\it Cambridge Studies in Advanced Mathematics} {\bf 49}.
Cambridge University Press, Cambridge, 1997.

\bibitem{Stanley-ECII}
R.P. Stanley,
{\it Enumerative Combinatorics Vol. 2}.
{\it Cambridge Studies in Advanced Mathematics} {\bf 62}.
Cambridge University Press, Cambridge, 1999.

\bibitem{Stanley-sign-balance}
R.P. Stanley,
Some remarks on sign-balanced and maj-balanced posets,
math Ar$\chi$iv preprint {\tt math.CO/0211113}.

\bibitem{Wagner-posets}
D. Wagner, Enumeration of functions from posets to chains.
{\it Eur. J. Comb.} {\bf 13} (1992), 313--324.

\end{thebibliography}
\end{document}


