% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.17}{25(1)}{2018} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} \usepackage{ytableau} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} %\usepackage[colorlinks,linkcolor=blue,anchorcolor=blue,citecolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins \def\ps{\mathrm{ps}} \newtheorem{thm}{Theorem}[section] \newtheorem{deff}[thm]{Definition} \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \newtheorem{prob}[thm]{Problem} \newtheorem{coro}[thm]{Corollary} \newtheorem{conj}[thm]{Conjecture} \newtheorem{remark}[thm]{Remark} \newtheorem{exam}[thm]{Example} \numberwithin{equation}{section} %% \DeclareMathOperator{\asc}{asc} \DeclareMathOperator{\D}{D} \DeclareMathOperator{\Asc}{Asc} \DeclareMathOperator{\cyc}{cyc} \DeclareMathOperator{\des}{des} \DeclareMathOperator{\Des}{Des} \DeclareMathOperator{\exc}{exc} \DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\stat}{stat} %%%5 \renewcommand{\theequation}{\arabic{section}.\arabic{equation}} \renewcommand{\thetable}{\arabic{section}.\arabic{table}} \renewcommand{\thefigure}{\arabic{section}.\arabic{figure}} \newdimen\Squaresize \Squaresize=11pt \newdimen\Thickness \Thickness=0.7pt \def\Square#1{\hbox{\vrule width \Thickness \vbox to \Squaresize{\hrule height \Thickness\vss \hbox to \Squaresize{\hss#1\hss} \vss\hrule height\Thickness} \unskip\vrule width \Thickness} \kern-\Thickness} \def\Vsquare#1{\vbox{\Square{$#1$}}\kern-\Thickness} \def\blk{\omit\hskip\Squaresize} \def\young#1{ \vbox{\smallskip\offinterlineskip \halign{&\Vsquare{##}\cr #1}}} \def\putd#1{\scriptsize{-#1-}} \def\moins{\raise 1pt\hbox{{$\scriptstyle -$}}} %\parskip 6pt % declare theorem-like environments %\theoremstyle{plain} %\newtheorem{theorem}{Theorem} %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{fact}[theorem]{Fact} %\newtheorem{observation}[theorem]{Observation} %\newtheorem{claim}[theorem]{Claim} % %\theoremstyle{definition} %\newtheorem{definition}[theorem]{Definition} %\newtheorem{example}[theorem]{Example} %\newtheorem{conjecture}[theorem]{Conjecture} %\newtheorem{open}[theorem]{Open Problem} %\newtheorem{problem}[theorem]{Problem} %\newtheorem{question}[theorem]{Question} % %\theoremstyle{remark} %\newtheorem{remark}[theorem]{Remark} %\newtheorem{note}[theorem]{Note} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Kirillov's Unimodality Conjecture for the Rectangular Narayana Polynomials} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Herman Z. Q. Chen\\ \small School of Science\\[-0.8ex] \small Tianjin Chengjian University, Tianjin 300384, P. R. China \\[-0.8ex] \small\tt zqchern@163.com \and Arthur L. B. Yang\\ \small Center for Combinatorics, LPMC \\[-0.8ex] \small Nankai University, Tianjin 300071, P. R. China \\[-0.8ex] \small\tt yang@nankai.edu.cn \and Philip B. Zhang\thanks{This work was supported by the National Science Foundation of China (Nos. 11231004, 11522110, 11626172, 11701424). % The first author was partially supported by the PHD Program of Tianjin Chengjian University (160501436). The third author was partially supported by the PHD Program of Tianjin Normal University (52XB1616). }\\ \small College of Mathematical Science \\[-0.8ex] \small Tianjin Normal University, Tianjin 300387, P. R. China \\[-0.8ex] \small\tt zhangbiaonk@163.com } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Feb 6, 2017}{Jan 8, 2018}{Jan 25, 2018}\\ \small Mathematics Subject Classifications: 05A20, 30C15} \begin{document} \maketitle \begin{abstract} In the study of Kostka numbers and Catalan numbers, Kirillov posed a unimodality conjecture for the rectangular Narayana polynomials. We prove that the rectangular Narayana polynomials have only real zeros, and thereby confirm Kirillov's unimodality conjecture. By using an equidistribution property between descent numbers and ascent numbers on ballot paths due to Sulanke and a bijection between lattice words and standard Young tableaux, we show that the rectangular Narayana polynomial is equal to the descent generating function on standard Young tableaux of certain rectangular shape, up to a power of the indeterminate. Then we obtain the real-rootedness of the rectangular Narayana polynomial based on a result of Brenti which implies that the descent generating function of standard Young tableaux has only real zeros. \bigskip \noindent \textbf{Keywords:} rectangular Narayana polynomials; lattice words; Young tableaux; Ferrers posets \end{abstract} \section{Introduction} The main objective of this paper is to prove a unimodality conjecture for the rectangular Narayana polynomials in the study of Kostka numbers and Catalan numbers. This conjecture was first posed by Kirillov \cite{Kirillov99} in 1999, and restated by himself \cite{Kirillov15} in 2015. In this paper we prove that the rectangular Narayana polynomials have only real zeros, an even stronger result than Kirillov's conjecture. Let us begin with an overview of Kirillov's conjecture. Throughout this paper, we abbreviate the vector $(m,m,\ldots,m)$ with $n$ occurrences of $m$ as $(m^n)$ for any positive integers $m$ and $n$. We say that a word $\mathtt{w}=w_1w_2\cdots w_{nm}$ in symbols $1,2,\ldots, m$ is a {lattice word} of weight $(m^n)$, if the following conditions hold: \begin{itemize} \item[(a)] each $i$ between $1$ and $m$ occurs exactly $n$ times and \item[(b)] for each $1\leq r\leq nm$ and $1\leq i \leq m-1$, the number of $i$'s in $w_1w_2\cdots w_r$ is not less than the number of $(i+1)$'s. \end{itemize} Given a word $\mathtt{w}=w_1w_2\cdots w_p$ of length $p$, we say that $i$ is an {ascent} of $\mathtt{w}$ if $w_i < w_{i+1}$, and a {descent} of $\mathtt{w}$ if $w_i >w_{i+1}$. Denote the number of ascents of $\mathtt{w}$ by $\asc(\mathtt{w})$, and the number of descents $\des(\mathtt{w})$. For any $m$ and $n$, the rectangular Narayana polynomial $N(n,m;t)$ is defined by \begin{align}\label{def-Narayana_Pol} N(n,m;t)= \sum_{\mathtt{w}\in \mathcal{N}(n,m)} t^{\des(\mathtt{w})}, \end{align} where $\mathcal{N}(n,m)$ is the set of lattice words of weight $(m^n)$. Note that $N(n,2;t)$ is the classical Narayana polynomial, and $N(n,2;1)$ is the classical Catalan number, see \cite{Kirillov15}. For this reason, $N(n,m;1)$ is called the rectangular Catalan number. Kirillov's conjecture is concerned with the unimodality of the rectangular Narayana polynomial $N(n,m;t)$. Recall that a sequence $\{a_0,a_1,\ldots,a_n\}$ of positive real numbers is said to be {unimodal} if there exists an integer $i\geq0$ such that $$a_0\leq \cdots \leq a_{i-1}\leq a_i \geq a_{i+1}\geq\cdots\geq a_n,$$ and {log-concave} if, for each $1\leq i\leq n-1$, there holds $$a_i^2\geq a_{i-1}a_{i+1}.$$ Clearly, for a sequence of positive numbers, its log-concavity implies unimodality. Given a polynomial with real coefficients $$f(t)=\sum_{k=0}^n a_k t^k,$$ it is unimodal (or log-concave) if its coefficient sequence $\{a_0,a_1,\ldots,a_n\}$ is unimodal (resp. log-concave). Kirillov proposed the following conjecture. \begin{conj}[{\cite[Conjecture 2.5]{Kirillov15}}] \label{Conj-Kirillov} For any $m$ and $n$, the rectangular Narayana polynomial $N(n,m;t)$ is unimodal as a polynomial of $t$. \end{conj} In this paper, we give an affirmative answer to the above conjecture. Instead of directly proving its unimodality, we shall show that the rectangular Narayana polynomial $N(n,m;t)$ has only real zeros. By the well known Newton's inequality, if a polynomial with nonnegative coefficients has only real zeros, then its coefficient sequence must be log-concave and hence unimodal. Thus, from the real-rootedness of $N(n,m;t)$ we deduce its log-concavity and unimodality. The remainder of this paper is organized as follows. In Section \ref{section-2}, we show that the rectangular Narayana polynomial $N(n,m;t)$ is equal to the descent generating function on standard Young tableaux of shape $(n^m)$, up to a power of $t$. We use a result of Sulanke \cite{Sulanke04} that the ascent and descent statistics are equidistributed over the set of ballot paths. In Section \ref{section-3}, we first prove the real-rootedness of the descent generating function on standard Young tableaux, and then obtain the real-rootedness of $N(n,m;t)$. The key to this approach is a connection between the descent generating functions of standard Young tableaux and the Eulerian polynomials of column-strict labeled Ferrers posets. The latter polynomials have only real zeros, as proven by Brenti \cite{Brenti89} in the study of the Neggers-Stanley conjecture. \section{Tableau interpretation} \label{section-2} The aim of this section is to interpret the rectangular Narayana polynomials as the descent generating functions on standard Young tableaux. Let us first recall some definitions. Given an integer partition $\lambda=(\lambda_1, \lambda_2, \ldots, \lambda_{\ell})$, its Young diagram is defined to be an array of squares in the plane justified from the top left corner with $\ell$ rows and $\lambda_i$ squares in row $i$. By transposing the diagram of $\lambda$, we get the conjugate partition of $\lambda$, denoted $\lambda'$. A cell $(i,j)$ of $\lambda$ is in the $i$-th row from the top and in the $j$-th column from the left. A {semistandard Young tableau (SSYT)} of shape $\lambda$ is a filling of its diagram by positive integers such that it is weakly increasing in every row and strictly increasing down every column. The type of $T$ is defined to be the composition $\alpha=(\alpha_1,\alpha_2,\ldots)$, where $\alpha_i$ is the number of $i$'s in $T$. Let $|\lambda|=\lambda_1+\cdots+\lambda_{\ell}$. If $T$ is of type $\alpha$ with $\alpha_i=1$ for $1\leq i\leq |\lambda|$ and $\alpha_i=0$ for $i> |\lambda|$, then it is called a {standard Young tableau (SYT)} of shape $\lambda$. Let $\mathcal{T}_{\lambda}$ denote the set of SYTs of shape $\lambda$. Given a standard Young tableau, we say that $i$ is a {descent} of $T$ if $i+1$ appears in a lower row of $T$ than $i$. Define the descent set $D(T)$ to be the set of all descents of $T$, and denote by $\des(T)$ the number of descents of $T$. The main result of this section is as follows. \begin{thm} \label{main-thm-0} For any positive integers $m$ and $n$, we have \begin{align} N(n,m;t)=t^{1-m}\sum_{T\in \mathcal{T}_{(n^m)}}t^{\des(T)}. \end{align} \end{thm} To prove the above result, we need a bijection between the set of lattice paths and the set of standard Young tableaux. Here we use a very natural bijection $\phi$ between the lattice word of weight $(m^n)$ and the standard Young tableau of shape $(n^m)$, see \cite[p. 92]{Coleman68}, \cite[p. 221]{Hamermesh89} and \cite{Stanley99}. To be self-contained, we shall give a description of this bijection in the following. Given a lattice word $\mathtt{w}=w_1\cdots w_{nm}$ of weight $(m^n)$, let $T=\phi(\mathtt{w})$ be the tableau of shape $(n^m)$ obtained by filling the square $(i,j)$ with $k$ provided that $w_k$ is the $j$-th occurrence of $i$ in $\mathtt{w}$ from left to right. Clearly, $T$ is a standard Young tableau. Conversely, given a standard Young tableau $T$ of shape $(n^m)$, define a word $\mathtt{w}$ by letting $w_i$ to be $j$ if $i$ is in the $j$-th row of $T$. It is easy to verify that $\mathtt{w}=\phi^{-1}(T)$. Figure \ref{fig-1} gives an illustration of this bijection, where $T$ is of shape $(4^3)$ and $\mathtt{w}$ is of weight $(3^4)$. \begin{figure}[ht] \begin{center} $\mathtt{w}=~121113223233$~$\mapsto$~ $T=$~ \begin{ytableau} 1 & 3 & 4 & 5 \\ 2 & 7 & 8 & 10\\ 6 & 9 & 11 & 12 \end{ytableau} \end{center} \caption{Bijection between standard Young tableaux and lattice words}\label{fig-1} \end{figure} By using the above bijection $\phi$, we obtain the following result. \begin{lem} For any positive integers $m$ and $n$, we have \begin{align}\label{D_TandA_w} \sum_{T\in \mathcal{T}_{(n^m)}}t^{\des(T)}=\sum_{\mathtt{w}\in\mathcal{N}(n,m)} t^{\asc(\mathtt{w})}. \end{align} \end{lem} \begin{proof} Suppose that $T=\phi(\mathtt{w})$. Note that if $i$ is an ascent in $\mathtt{w}$, i.e. $w_i< w_{i+1}$, then $i+1$ is filled in the $w_{i+1}$-th row, which is lower than the row including $i$ in $T$. Hence, $i$ is a descent of $T$. Conversely, given a tableau $T$, let $i$ be a descent of $T$ and $\mathtt{w}=\phi^{-1}(T)$. Since $i+1$ appears in a lower row of $T$ than $i$, it follows that $w_{i}l \}|.$$ Sulanke \cite{Sulanke04} obtained the following result by a nice bijection. \begin{lem}[{\cite[Proposition 2]{Sulanke04}}] For any positive integers $m$ and $n$, we have \begin{align} \sum_{P\in \mathcal{C}(m,n)} t^{\asc(P)}=\sum_{P\in \mathcal{C}(m,n)} t^{\des(P)-m+1}. \end{align} \end{lem} Note that there is an obvious bijection between $\mathcal{C}(m,n)$ and $\mathcal{N}(n,m)$: given a path $P\in\mathcal{C}(m,n)$, simply replace each step $X_i$ of $P$ by the symbol $m-i+1$, and the resulting word $\mathtt{w}$ is clearly a lattice word of $\mathcal{N}(n,m)$. Moreover, we have $\asc(P)=\des(\mathtt{w})$ and $\des(P)=\asc(\mathtt{w})$. With this bijection, Sulanke's result can be restated as \eqref{eq-sun}. \begin{proof}[Proof of Theorem \ref{main-thm-0}] Combining \eqref{def-Narayana_Pol}, \eqref{D_TandA_w} and \eqref{eq-sun}, we immediately obtain the desired result. \end{proof} \section{Real zeros} \label{section-3} In this section, we aim to prove the real-rootedness of rectangular Narayana polynomials. Our main result of this section is as follows. \begin{thm}\label{main-thm} The rectangular Narayana polynomial $N(n,m;t)$ has only real zeros for any $m$ and $n$. \end{thm} By Theorem \ref{main-thm-0}, we only need to show that the following polynomial $$\sum_{T\in \mathcal{T}_{(n^m)}}t^{\des(T)}$$ has only real zeros. To this end, we shall use a result due to Brenti \cite{Brenti89} during his study of the Neggers-Stanley Conjecture. For more information on the Neggers-Stanley Conjecture, see \cite{Stembridge07} and references therein. Given a partition $\lambda=(\lambda_1,\ldots,\lambda_{\ell})$, the corresponding Ferrers poset $P_{\lambda}$ is the poset \[ P_{\lambda}=\{(i,j)\in \mathbb{P} \times \mathbb{P}: 1\leq i\leq \ell, 1\leq j\leq \lambda_i \},\] ordered by the standard product ordering. Let $\omega$ be a column strict labeling of $P_{\lambda}$, namely, $\omega(i,j)>\omega(i+1,j)$ and $\omega(i,j)<\omega(i,j+1)$ for all $(i,j)\in P_{\lambda}$. Brenti \cite{Brenti89} proved the following result, see also Br\"{a}nd\'{e}n \cite{Branden04}. \begin{thm}\cite[p. 60, Proof of Theorem 5.3.2]{Brenti89} Let $(P_{\lambda},\omega)$ be labeled column strict. Then the $(P_{\lambda},\omega)$\,-Eulerian polynomial \begin{align} W(P_{\lambda},\omega;t)=\sum_{\pi\in\mathcal{L}(P_{\lambda},\omega)} t^{\des(\pi)} \end{align} has only real zeros, where $\mathcal{L}(P_{\lambda},\omega)$ is the Jordan-H\"older set of $(P_{\lambda},\omega)$. \end{thm} Based on the above theorem, we obtain the following result. \begin{coro}\label{WPrz} For any partition $\lambda$, the polynomial $$\sum_{T\in \mathcal{T}_{\lambda}}t^{\des(T)}$$ has only real zeros. \end{coro} \begin{proof} It suffices to show that \begin{align} W(P_{\lambda},\omega;t)=\sum_{T\in \mathcal{T}_{\lambda}}t^{\des(T)}. \end{align} To this end, we need to establish a bijection $\psi$ from $\mathcal{L}(P_{\lambda},\omega)$ to $\mathcal{T}_{\lambda}$ such that $\des(\pi)=\des(\psi(\pi))$ for any $\pi\in \mathcal{L}(P_{\lambda},\omega)$. Suppose that $|\lambda|=p$. Note that, given a permutation $\pi=\pi_1\pi_2\cdots\pi_p\in \mathcal{L}(P_{\lambda},\omega)$, the sequence $\omega^{-1}(\pi_1)\omega^{-1}(\pi_2)\cdots\omega^{-1}(\pi_p)$ is a linear extension of $P_{\lambda}$. Let $\psi(\pi)$ be the tableau of shape $\lambda$ by filling the square $\omega^{-1}(\pi_k)$ with $k$. Since $\omega$ is column strict, it is readily to see that $\psi(\pi)$ is a standard Young tableau and $\psi$ is a bijection. Furthermore, $k$ is a descent in $\pi$ if and only if $k$ is a descent in $\psi(\pi)$. In fact, suppose that $k$ and $k+1$ are in the square $(x,y)$ and $(x',y')$ then $\pi_k>\pi_{k+1}$ implies that $x