%--------------------------------------------------------------- % 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 \\ & #5 & #6 \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}