% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.51}{25(2)}{2018} % Please remove all commands that change parameters such as % margins or page sizes. % Packages amssymb and amsthm are already loaded. % We recommend these AMS packages: \usepackage{amsmath,amssymb} % 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{tikz} % Theorem-like environments that are declared in the style file are: % theorem, lemma, corollary, proposition, fact, observation, claim, % definition, example, conjecture, open, problem, question, remark, note %%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Give the submission and acceptance dates in the format shown. % The editors will insert the publication date in the third argument. \dateline{Sep 15, 2017}{May 22, 2018}{Jun 22, 2018} % Give one or more subject codes separated by commas. % Codes are available from http://www.ams.org/mathscinet/freeTools.html \MSC{06A07, 52B20, 05A30} % Uncomment exactly one of the following copyright statements. Alternatively, % you can write your own copyright statement subject to the approval of the journal. % See https://creativecommons.org/licenses/ for a full explanation of the % Creative Commons licenses. % % We strongly recommend CC BY-ND or CC BY. Both these licenses allow others % to freely distribute your work while giving credit to you. The difference between % them is that CC BY-ND only allows distribution unchanged and in whole, while % CC BY also allows remixing, tweaking and building upon your work. % % One author: %\Copyright{The author.} %\Copyright{The author. Released under the CC BY license (International 4.0).} %\Copyright{The author. Released under the CC BY-ND license (International 4.0).} % More than one author: %\Copyright{The authors.} %\Copyright{The authors. Released under the CC BY license (International 4.0).} \Copyright{The authors. Released under the CC BY-ND license (International 4.0).} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % If needed, include a line break (\\) at an appropriate place in the title. \title{Proof of Chapoton's conjecture on Newton \\polygons of $q$-Ehrhart polynomials} % Input author, affiliation, address and support information as follows; % The address should include the country, but does not have to include % the street address. Give at least one email address. \author{Jang Soo Kim\thanks{This work was supported by NRF grants \#2016R1D1A1A09917506 and \#2016R1A5A1008055.} \qquad U-Keun Song\\ \small Department of Mathematics\\[-0.8ex] \small Sungkyunkwan University\\[-0.8ex] \small Suwon 16419, South Korea \\ \small\tt \{jangsookim, sukeun319\}@skku.edu} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract may be distributed without the rest of the % paper so it must be entirely self-contained. Try to include all words % and phrases that someone might search for when looking for your paper. \begin{abstract} Recently, Chapoton found a $q$-analog of Ehrhart polynomials, which are polynomials in $x$ whose coefficients are rational functions in $q$. Chapoton conjectured the shape of the Newton polygon of the numerator of the $q$-Ehrhart polynomial of an order polytope. In this paper, we prove Chapoton's conjecture. \end{abstract} \newtheorem{thm}{Theorem}[section] \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \newtheorem{cor}[thm]{Corollary} \theoremstyle{definition} \newtheorem{exam}[thm]{Example} \newtheorem{defn}[thm]{Definition} \newtheorem{conj}[thm]{Conjecture} \newcommand\Qbinom[3]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{#3}} \newcommand\qbinom[2]{\Qbinom{#1}{#2}{q}} \newcommand\LL{\mathcal{L}} \newcommand\NN{\mathbb{N}} \newcommand\order{\mathcal{O}} \newcommand\Sym{\mathfrak{S}} \newcommand\inv{\operatorname{inv}} \newcommand\maj{\operatorname{maj}} \newcommand\Des{\operatorname{Des}} \newcommand\des{\operatorname{des}} \newcommand\DB{\operatorname{DB}} \newcommand\mc{\operatorname{mc}} \newcommand\PP{\mathcal{P}} \newcommand\RR{\mathbb{R}} \newcommand\QQ{\mathbb{Q}} \newcommand\ZZ{\mathbb{Z}} \newcommand\NT{\mathrm{Newton}} \renewcommand\vec[1]{\mathbf{#1}} \section{Introduction} In 1962, Ehrhart \cite{Ehrhart} discovered certain polynomials associated to lattice polytopes. These polynomials are now widely known and called Ehrhart polynomials. They contain important information of lattice polytopes such as the number of lattice points in the polytope, the number of lattice points in the relative interior and the relative volume of the polytope. Recently, Chapoton \cite{Chapoton2016} found a $q$-analog of Ehrhart polynomials and generalized some properties of them. A $q$-Ehrhart polynomial is a polynomial in variable $x$ whose coefficients are rational functions in $q$. Thus we can write a $q$-Ehrhart polynomial as a rational function in $q$ and $x$ whose numerator is a polynomial in $q$ and $x$, and whose denominator is a polynomial in $q$. In the same paper, Chapoton conjectured the shape of the Newton polygon of the numerator of the $q$-Ehrhart polynomial associated to an order polytope. The goal of this paper is to prove Chapoton's conjecture. First, we briefly review basic properties of Ehrhart polynomials and their $q$-analogs. See \cite{Barvinok1999, Beck2007, Beck2012} for more details in Ehrhart polynomials. A point in $\RR^m$ is called a \emph{lattice point} if all the coordinates are integers. A \emph{lattice polytope} is a polytope whose vertices are lattice points. All polytopes considered in this paper are lattice polytopes. For a polytope $M$ and an integer $n$, we denote by $nM$ the dilation of $M$ by a scale factor of $n$, i.e., \[ nM = \{n\vec x: \vec x\in M\}. \] For a lattice polytope $M$ in $\RR^m$, there exists a polynomial $E(x)$, called the \emph{Ehrhart polynomial of $M$}, satisfying the following interesting properties: \begin{itemize} \item $E(n) = |nM\cap \ZZ^m|$ for all integers $n\ge0$. \item $(-1)^{\dim M}E(-n) = |nM^\circ\cap \ZZ^m|$ for all integers $n\ge0$, where $\dim M$ is the dimension of $M$ and $M^\circ$ is the relative interior of $M$. \item The degree of $E(x)$ is equal to the dimension of $M$. \item The leading coefficient of $E(x)$ is equal to the relative volume of $M$. \end{itemize} For a polytope $M$ in $\RR^m$, let \[ W(M,q) = \sum_{\vec x\in M\cap \ZZ^m} q^{|\vec x|}, \] where for $\vec x=(x_1,\dots,x_m)$ we denote \[ |\vec x| = x_1+\dots+x_m. \] We use the standard notation for $q$-integers: for $n\in\ZZ$, \[ [n]_q := \frac{1-q^n}{1-q}, \] and, for integers $n\ge k\ge 0$, \[ [n]_q!: = [1]_q[2]_q\dots[n]_q, \qquad \qbinom{n}{k}: = \frac{[n]_q!}{[k]_q![n-k]_q!}. \] Note that for $n\ge0$ and $a,b\in\ZZ$, we have \begin{align*} [n]_q &= 1+q+q^2+\dots+q^{n-1}, \\ [-n]_q &= -q^{-n}[n]_q,\\ [a+b]_q &= [a]_q+q^a [b]_q. \end{align*} Chapoton \cite[Theorem~3.1]{Chapoton2016} found a $q$-analog of Ehrhart polynomials as follows. \begin{thm}[Chapoton]\label{thm:Chapoton} Let $M$ be a polytope satisfying the following conditions: \begin{itemize} \item For every vertex $\vec x$ of $M$, we have $|\vec x|\ge0$. \item For every edge between two vertices $\vec x$ and $\vec y$ of $M$, we have $|\vec x|\ne |\vec y|$. \end{itemize} Then there is a polynomial $E(x)\in \QQ(q)[x]$ such that for every integer $n\ge0$, \[ E([n]_q) = W(nM,q). \] \end{thm} The polynomial $E(x)$ in Theorem~\ref{thm:Chapoton} is called the \emph{$q$-Ehrhart polynomial} of the polytope $M$. We note that in \cite{Chapoton2016}, more generally, Chapoton considers a linear form $\lambda(\vec x)$ on $\RR^m$ in place of $|\vec x|$. In this setting with a linear form, Chapoton \cite[Theorem~3.5]{Chapoton2016} also shows a nice $q$-analog of the Ehrhart-Macdonald reciprocity: \[ E([-n]_q) =(-1)^{\dim M} W(nM^\circ,1/q). \] We note that Kim and Stanton \cite[Theorem~9.3]{KimStanton17} showed that the leading coefficient of the $q$-Ehrhart polynomial of an order polytope is equal to the $q$-volume of the order polytope, which is defined as a Jackson's $q$-integral over the order polytope. In order to state Chapoton's conjecture we need some notation and terminology. For a polynomial $f(x_1,\dots,x_k)$ in $x_1,\dots,x_k$, we denote by $[x_1^{i_1}\dots x_k^{i_k}]f(x_1,\dots,x_k)$ the coefficient of $x_1^{i_1}\dots x_k^{i_k}$ in $f(x_1,\dots,x_k)$. For a polynomial $f(x_1,\dots,x_k)$ in $x_1,\dots,x_k$, the \emph{Newton polytope} of $f(x_1,\dots,x_k)$, denoted by $\NT(f(x_1,\dots,x_k))$, is the convex hull of the points $(i_1,\dots,i_k)$ such that $[x_1^{i_1}\dots x_k^{i_k}]f(x_1,\dots,x_k)\ne 0$. In this paper, we consider \emph{Newton polygons}, which are Newton polytopes of two-variable functions. For a poset $P$ on $\{1,2,\dots,m\}$, the \emph{order polytope} $\order(P)$ of $P$ is defined by \[ \order(P)=\{(x_1,\dots,x_m)\in [0,1]^m: x_i\le x_j \mbox{ if } i\le_P j\}. \] As mentioned in \cite{Chapoton2016}, using the properties of vertices and edges of an order polytope in \cite{Stanley_two_poset} one can check that every order polytope satisfies the conditions in Theorem~\ref{thm:Chapoton}. Therefore, we can consider the $q$-Ehrhart polynomial of an order polytope. Let $E_P(x)$ be the $q$-Ehrhart polynomial of $\order(P)$. We denote by $N_P(q,x)$ be the numerator of $E_P(x)$. More precisely, $N_P(q,x)$ is the unique polynomial in $\ZZ[q,x]$ with positive leading coefficient such that \[ E_P(x) = \frac{N_P(q,x)}{D(q)}, \] for some polynomial $D(q)\in \ZZ[q]$ with $\gcd(N_P(q,x),D(q))=1$. For integers $1\le a_1\le a_2\le \dots\le a_m$ and $h\ge a_1+\dots+a_m$, we define $C(a_1,\dots,a_m;h)$ to be the convex hull of the points $(0,0)$, $(a_1+\dots+a_i,i)$ for $1\le i\le m$, $(h,m)$ and $(h-m,0)$. See Figure~\ref{fig:C} for an example. \begin{figure} \centering \begin{tikzpicture}[scale=0.5] \draw[step=1cm,gray,very thin] (0,0) grid (10.5,4.5); \foreach \x in {1,...,10} \draw (\x cm,1pt) -- (\x cm,-1pt) node[anchor=north] {$\x$}; \foreach \y in {1,...,4} \draw (1pt, \y cm) -- (-1pt, \y cm) node[anchor=east] {$\y$}; \draw[->,thick] (-.5,0) -- (11.5,0) node[anchor=north] {$q$}; \draw[->,thick] (0,-.5) -- (0,5.5) node[anchor=north west] {$x$}; \draw [fill=lightgray,very thick] (0,0) -- (1,1) -- (3,2) -- (5,3) -- (8,4) -- (10,4) -- (6,0) -- (0,0); \draw (0,0) node[anchor=north east] {$0$}; \end{tikzpicture} \caption{The polygon $C(1,2,2,3;10)$ in the $(q,x)$-coordinate system.} \label{fig:C} \end{figure} Let $P$ be a poset and $x\in P$. A \emph{chain ending at $x$} (resp.~\emph{starting at $x$}) is a subset $\{t_1<_P \dots <_P t_k\}$ of $P$ with $t_k=x$ (resp.~$t_1=x$). The \emph{size} of a chain is the number of elements in the chain. We denote by $\mc_P(x)$ the maximum size of a chain ending at $x$. We also denote by $\overline{\mc}_P(x)$ the maximum size of a chain starting at $x$. When there is no possible confusion, we will simply write as $\mc(x)$ and $\overline{\mc}(x)$ instead of $\mc_P(x)$ and $\overline{\mc}_P(x)$. In \cite[Conjecture~5.3]{Chapoton2016}, Chapoton proposed the following conjecture on the shape of the Newton polygon of $N_P(q,x)$. \begin{conj}\label{conj:chapoton} Let $P$ be a poset on $\{1,2,\dots,m\}$. Suppose that $a_1\le a_2\le \cdots\le a_m$ is the increasing rearrangement of $\overline{\mc}(1),\dots,\overline{\mc}(m)$. Then the Newton polygon of the numerator of the $q$-Ehrhart polynomial of $\order(P)$ is given by \[ \NT(N_P(q,x))=C(a_1,\dots,a_m;h), \] for some integer $h\ge a_1+\dots+a_m$. \end{conj} The goal of this paper is to prove Conjecture~\ref{conj:chapoton}. As Chapoton points out in \cite{Chapoton2016}, the $q$-Ehrhart polynomial $E_P(x)$ of $\order(P)$ can be understood as a generating function for $P$-partitions of $\overline{P}$, the dual poset of $P$. It is well-known that the generating function for $P$-partitions can be expressed in terms of linear extensions of the poset. One of the main ingredients of our proof of Conjecture~\ref{conj:chapoton} is Corollary~\ref{cor:mc}, which gives a description of the minimum of $\maj(\pi)-k \des(\pi)$ over all linear extensions $\pi$ of $P$. The rest of this paper is organized as follows. In Section~\ref{sec:main-result}, we recall necessary definitions and state our main result (Theorem~\ref{thm:main}), which describes the precise shape of the Newton polygon of $[m]_q!E_{P}(x)$. Then we show that Theorem~\ref{thm:main} implies Conjecture~\ref{conj:chapoton}. In Section~\ref{sec:some-prop-posets} we find some property of the linear extensions of a poset. In Section~\ref{sec:proof-theor-refthm:m} we prove Theorem~\ref{thm:main}. \section{The main result} \label{sec:main-result} In this section we state our main theorem, which implies Conjecture~\ref{conj:chapoton}. We first recall some definitions on permutations and posets. We refer the reader to \cite{EC1} for more details. The set of nonnegative integers is denoted by $\NN$. Let $\Sym_m$ be the set of permutations of $\{1,2,\dots,m\}$. For $\pi=\pi_1\dots\pi_m\in\Sym_m$, a \emph{descent} of $\pi$ is an integer $1\le i\le m-1$ such that $\pi_i>\pi_{i+1}$. We denote by $\Des(\pi)$ the set of descents of $\pi$. We define $\maj(\pi)=\sum_{i\in\Des(\pi)}i$ and $\des(\pi)=|\Des(\pi)|$. Let $P$ be a poset on $\{1,2,\dots,m\}$. A \emph{$P$-partition} is an order-reversing map $\sigma:P\to\NN$, i.e., $\sigma(x)\ge \sigma(y)$ if $x\le_P y$. For a $P$-partition $\sigma$, let $|\sigma|=\sigma(1)+\dots+\sigma(m)$. We denote by $\PP(P)$ the set of $P$-partitions. For an integer $n$, we denote by $\PP(P,n)$ the set of $P$-partitions $\sigma$ satisfying $\sigma(x)\le n$ for all $x\in P$. We say that $P$ is \emph{naturally labeled} if $x\le_P y$ implies $x\le y$. A \emph{linear extension} of $P$ is a permutation $\pi=\pi_1\dots\pi_m\in\Sym_m$ such that $\pi_i\le_P\pi_j$ implies $i\le j$. We denote by $\LL(P)$ the set of linear extensions of $P$. Note that if $P$ is naturally labeled, $\LL(P)$ always contains the identity permutation. We need the following lemma, which gives a connection between certain generating functions for $\PP(P,n)$ and $\LL(P)$. \begin{lem}\label{lem:qbinom} For a naturally labeled poset $P$ on $\{1,2,\dots,m\}$, we have \[ \sum_{\sigma\in \PP(P,n)} q^{|\sigma|} =\sum_{\pi\in\LL(P)}q^{\maj(\pi)} \qbinom{n-\des(\pi)+m}{m}. \] \end{lem} \begin{proof} For a permutation $w\in\Sym_m$, let $S_w$ denote the set of all functions $f:P\to\NN$ satisfying the following conditions: \begin{itemize} \item $f(w_1)\ge f(w_2)\ge \cdots\ge f(w_m)$ and \item $f(w_i)>f(w_{i+1})$ if $i\in\Des(w)$. \end{itemize} It is well known \cite[Lemma~3.15.3]{EC1} that \[ \PP(P) = \biguplus_{\pi\in\LL(P)} S_\pi. \] Let $S_\pi(n)=S_\pi\cap \PP(P,n) $. Then we have \[ \PP(P,n) = \biguplus_{\pi\in\LL(P)} S_\pi(n). \] Thus, \[ \sum_{\sigma\in \PP(P,n)} q^{|\sigma|} = \sum_{\pi\in\LL(P)}\sum_{\sigma\in S_\pi(n)}q^{|\sigma|} = \sum_{\pi\in\LL(P)}\sum_{\substack{n\ge i_1\ge \cdots\ge i_m\ge0\\ i_j>i_{j+1} \:\:\: {\rm if} \:\:\: j\in\Des(\pi)}} q^{i_1+\dots+i_m}. \] It is shown in \cite[Lemma~4.5]{KimStanton17} that \[ \sum_{\substack{n\ge i_1\ge \cdots\ge i_m\ge0\\ i_j>i_{j+1} \:\:\: {\rm if} \:\:\: j\in\Des(\pi)}} q^{i_1+\dots+i_m} =q^{\maj(\pi)} \qbinom{n-\des(\pi)+m}{m}, \] which completes the proof. \end{proof} For a poset $P$, we denote its dual by $\overline{P}$, that is, $x\le_P y$ if and only if $y\le_{\overline{P}} x$. By definition, for a poset $P$ and an integer $n\in\NN$, we have \begin{equation} \label{eq:W} W(n\order(P),q) = \sum_{\sigma\in \PP(\overline{P},n)} q^{|\sigma|}. \end{equation} Therefore, the $q$-Ehrhart polynomial $E_P(x)$ of $\order(P)$ is closely related to $P$-partitions of $\overline{P}$. The next proposition shows that $E_P(x)$ can be written as a generating function for linear extensions of $\overline{P}$. \begin{prop}\label{prop:Ep} Let $P$ be a poset on $\{1,2,\dots,m\}$. Suppose that $\overline{P}$ is naturally labeled. Then the $q$-Ehrhart polynomial of $\order(P)$ is \[ E_P(x)=\frac{1}{[m]_q!}\sum_{\pi\in\LL(\overline{P})} q^{\maj(\pi)} \prod_{i=1}^m([i-\des(\pi)]_q+ q^{i-\des(\pi)} x). \] \end{prop} \begin{proof} Let $f(x)$ be the right hand side. Then \[ f([n]_q)=\sum_{\pi\in\LL(\overline{P})} q^{\maj(\pi)} \frac{\prod_{i=1}^m[i-\des(\pi)+n]_q}{[m]_q!}= \sum_{\pi\in\LL(\overline{P})}q^{\maj(\pi)} \qbinom{n-\des(\pi)+m}{m}. \] On the other hand, by Lemma~\eqref{lem:qbinom} and \eqref{eq:W}, we have \[ W(n\order(P),q) =\sum_{\pi\in\LL(\overline{P})}q^{\maj(\pi)} \qbinom{n-\des(\pi)+m}{m}. \] Thus $f([n]_q)=W(n\order(P),q)$ for all $n\in\NN$ and we obtain $E_P(x)=f(x)$. \end{proof} Now we define a polynomial $F_P(q,x)$ in $q$ and $x$, which will be used throughout this paper. \begin{defn} For a poset $P$ on $\{1,2,\dots,m\}$, we define \[ F_P(q,x)=\sum_{\pi\in\LL(P)} q^{\maj(\pi)} \prod_{i=1}^m([i-\des(\pi)]_q+ q^{i-\des(\pi)} x). \] \end{defn} Note that we always have $F_P(q,x)\in \ZZ[q,x]$ because for every $\pi\in\LL(P)$, the power of $q$ in each summand is at least \[ \maj(\pi)+\sum_{i=1}^{\des(\pi)}(i-\des(\pi)) \ge \binom{\des(\pi)+1}2 +\binom{\des(\pi)+1}2 - \des(\pi)^2\ge0. \] Proposition~\ref{prop:Ep} implies that for a naturally labeled poset $P$ on $\{1,2,\dots,m\}$, we have \begin{equation} \label{eq:Fp} F_P(q,x)=[m]_q!E_{\overline{P}}(x). \end{equation} \begin{prop}\label{prop:parallelogram} Let $P$ be a poset on $\{1,2,\dots,m\}$ such that $\overline{P}$ is naturally labeled. Suppose that $a_1\le a_2\le \dots\le a_m$ is the increasing rearrangement of $\overline{\mc}(1),\dots,\overline{\mc}(m)$. Then we have \[ \NT(N_P(q,x))=C(a_1,\dots,a_m;h), \] for some $h\ge a_1+\dots+a_m$ if and only if \[ \NT(F_{\overline{P}}(q,x))=C(a_1,\dots,a_m;h'), \] for some $h'\ge a_1+\dots+a_m$. Moreover, in this case we always have $h'=h+r$, where $r=\deg\phi(q)$ and $\phi(q)=\gcd(F_{\overline{P}}(q,x),[m]_q!)$. \end{prop} \begin{proof} By \eqref{eq:Fp}, we have \[ F_{\overline{P}}(q,x) = N_P(q,x) \phi(q). \] Since $\phi(q)$ divides $[m]_q!$, the leading coefficient and the constant term of $\phi(q)$ are both $1$. Thus, we have \[ \phi(q) = q^r+c_{r-1}q^{r-1}+\dots+c_1q^1+1, \] for some $c_1,\dots,c_{r-1}\in \ZZ$. Hence, for each $1\le k\le m$, we have \[ \max\{i:[q^ix^k]N_{P}(q,x)\ne 0\} =\max\{i:[q^{i+r}x^k]F_{\overline{P}}(q,x)\ne 0\}, \] \[ \min\{i:[q^ix^k]N_{P}(q,x)\ne0\} =\min\{i:[q^{i}x^k]F_{\overline{P}}(q,x)\ne0\}, \] which imply the statement. \end{proof} Now we state our main theorem. \begin{thm}\label{thm:main} Let $P$ be a naturally labeled poset on $\{1,2,\dots,m\}$. Let $b_1\le b_2\le\dots\le b_m$ be the increasing rearrangement of $\mc(1),\mc(2),\dots,\mc(m)$. Then the Newton polygon of \[ F_P(q,x)=[m]_q!E_{\overline{P}}(x)=\sum_{\pi\in\LL(P)} q^{\maj(\pi)} \prod_{i=1}^m([i-\des(\pi)]_q+ q^{i-\des(\pi)} x) \] is given by \[ \NT(F_{P}(q,x))=C\left(b_1,\dots,b_m;\binom{m+1}2\right). \] \end{thm} We prove Theorem~\ref{thm:main} in Section~\ref{sec:proof-theor-refthm:m}. Note that in Theorem~\ref{thm:main} we have \[ b_1+\dots+b_m \le \binom{m+1}2, \] which follows from the fact that $b_1=1$ and $b_{i+1}\le b_i+1$ for all $i$. We finish this section by showing that Theorem~\ref{thm:main} implies Conjecture~\ref{conj:chapoton}. \begin{proof}[Proof of Conjecture~\ref{conj:chapoton}] Note that relabeling of $P$ does not affect $E_P(q,x)$. Hence, we can assume that $\overline{P}$ is naturally labeled. Observe that $\overline{\mc}_P(x)=\mc_{\overline{P}}(x)$ for all $x\in \{1,2,\dots,m\}$. By Theorem~\ref{thm:main}, \[ \NT(F_{\overline{P}}(q,x))=C\left(a_1,\dots,a_m;\binom{m+1}2\right). \] By Proposition~\ref{prop:parallelogram}, we obtain that \[ \NT(N_P(q,x))=C(a_1,\dots,a_m;h), \] for some integer $h\ge a_1+\dots+a_m$. This completes the proof. \end{proof} \section{Some properties of linear extensions} \label{sec:some-prop-posets} In this section we prove some properties of posets which will be used in the next section. \begin{lem}\label{lem:resolve} Let $P$ be a naturally labeled poset on $\{1,2,\dots,m\}$ and $\pi\in\LL(P)$. Suppose that $\Des(\pi)\ne\emptyset$ and $c$ is the largest descent of $\pi$. Then there is a permutation $\sigma\in\LL(P)$ such that $\Des(\sigma)=\Des(\pi)\setminus\{c\}$. \end{lem} \begin{proof} Let $j$ be the second largest descent of $\pi$. If $c$ is the only descent of $\pi$, we set $j=0$. Let $\sigma=\pi_1\dots \pi_j \pi_{j+1}' \dots \pi_m'$, where $\pi_{j+1}'<\cdots<\pi_m'$ is the increasing rearrangement of $\pi_{j+1},\dots,\pi_m$. We claim that $\sigma\in\LL(P)$. Consider two elements $x$ and $y$ with $x<_P y$. If $y$ is in $\pi_1\dots\pi_j$, since $\pi$ is a linear extension, $x$ must appear before $y$. Otherwise $y$ is in the increasing sequence $\pi_{j+1}' \dots \pi_m'$. Since $P$ is naturally labeled, $x\pi_{j+1}\ge \pi_{j+1}'$, we have $\Des(\sigma)=\Des(\pi)\setminus\{c\}$. \end{proof} \begin{defn} Let $\pi=\pi_1\dots\pi_m\in \Sym_m$. A \emph{descent block} of $\pi$ is a maximal consecutive subsequence of $\pi$ which is in decreasing order. We denote by $\DB_i(\pi)$ the set of elements in the $i$th descent block of $\pi$. \end{defn} For example, if $\pi=384196725$, then the descent blocks of $\pi$ are $3$, $841$, $96$, $72$, $5$, and $\DB_1(\pi) = \{3\}$, $\DB_2(\pi) = \{1,4,8\}$, $\DB_3(\pi) = \{6,9\}$, $\DB_4(\pi) = \{2,7\}$, $\DB_5(\pi) = \{5\}$. \begin{lem}\label{lem:partition} Fix integers $r,p,k,m$ and mutually disjoint subsets $C_1,\dots,C_p$ of $\{1,2,\dots,m\}$ such that \[ |C_1|+\dots+|C_{p-1}|\le k<|C_1|+\dots+|C_{p}|. \] Let $u=|C_1|+\dots+|C_{p}|-k$. Then, for every $r$-tuples $B=(B_1,\dots,B_r)$ of mutually disjoint subsets of $\{1,2,\dots,k\}$ satisfying $B_i\subseteq C_1\cup\dots \cup C_i$ for $1\le i\le r$, we have \begin{equation} \label{eq:BC} |B_1|+2|B_2|+\dots+r|B_r|\ge |C_1|+2|C_2|+\dots+(p-1)|C_{p-1}|+p(|C_p|-u). \end{equation} Moreover, the equality holds if and only if the following conditions hold: $r=p$ and $B_i=C_i$ for $1\le i\le r-1$ and $B_r\subseteq C_r$. \end{lem} \begin{proof} First assume that the conditions for the equality hold. Then \[ \sum_{i=1}^r i |B_i|= \sum_{i=1}^{r-1} i |C_i|+r|B_r|. \] Since $p=r$, we have $|B_r|=|C_p|-u$ and the equality of \eqref{eq:BC} holds. Now suppose that $B=(B_1,\dots,B_r)$ is an $r$-tuple of mutually disjoint subsets of $\{1,2,\dots,k\}$ satisfying $B_i\subseteq C_1\cup\dots \cup C_i$ for $1\le i\le r$ that minimizes the value $\sum_{i=1}^r i |B_i|$. It suffices to show that $B$ satisfies the conditions for the equality. For a contradiction, suppose that the conditions do not hold. Then there are two cases. Case 1: We can find the smallest $1\le s\le r-1$ such that $B_s\ne C_s$. By the assumption on $B$, there is an element $x\in B_s\cap C_j$ for some $1\le j\le s-1$. Define $B' =(B'_1,\dots,B'_r)$ to be the $r$-tuple obtained from $B$ by replacing $B_j$ by $B_j\cup\{x\}$ and $B_s$ by $B_s\setminus\{x\}$. Then $\sum_{i=1}i|B'_i|<\sum_{i=1}i|B_i|$, which is a contradiction. Case 2: $\DB_i(\pi)\ne C_i$ for $1\le i\le r-1$ and $\DB_r(\pi)\not\subseteq C_r$. Similarly, we can find an element $x\in B_r\cap C_j$ for some $1\le j\le r-1$ and obtain a contradiction. By the above two cases, $B$ must satisfy the conditions for the equality. This finishes the proof. \end{proof} The following proposition is the key ingredient for proving Chapoton's conjecture. \begin{prop}\label{prop:mc} Let $P$ be a naturally labeled poset on $\{1,2,\dots,m\}$. Suppose that $b_1\le b_2\le\dots\le b_m$ is the increasing rearrangement of $\mc(1),\mc(2),\dots,\mc(m)$ and \[ C_i=\{x\in P: \mc(x)=i\}. \] Then, for $\pi\in\LL(P)$ and $0\le k\le m$, we have \[ \maj(\pi)-k\des(\pi)+\binom{k+1}2 \ge b_1+\dots+b_k. \] The equality holds if and only if all of the following conditions hold: \begin{itemize} \item $\Des(\pi)\subseteq \{1,2,\dots,k\}$, \item $\DB_i(\pi)=C_i$, for $1\le i\le p-1$, \item $\DB_p(\pi)\subseteq C_p$, \end{itemize} where $p$ is the integer satisfying \[ |C_1|+\dots+|C_{p-1}| < k \le |C_1|+\dots+|C_{p}|. \] Furthermore, for every $0\le k\le m$, there is a permutation in $\LL(P)$ satisfying these conditions. \end{prop} \begin{proof} For $\pi\in \Sym_m$, let \[ b(\pi) = \maj(\pi)-k\des(\pi)+\binom{k+1}2. \] Suppose that $\pi$ is a permutation in $\LL(P)$ such that $b(\pi)$ is the smallest. If $\pi$ has a descent greater than $k$, by Lemma~\ref{lem:resolve}, we can find $\sigma\in\LL(P)$ with $\Des(\sigma)=\Des(\pi)\setminus\{\max(\Des(\pi))\}$. Then $b(\sigma)\maj(\sigma)-\binom{\des(\sigma)}2. \] By repeating this argument, we obtain that \begin{equation} \label{eq:1} \maj(\pi)-\binom{\des(\pi)}2 >\maj(\tau)-\binom{\des(\tau)}2, \end{equation} for some $\tau\in\LL(P)$ with $\des(\tau)=k$. On the other hand, by Lemma~\ref{lem:qmin}, we have \begin{equation} \label{eq:2} q_{\min}([x^{k-1}]t(\tau,k))=\maj(\tau)-k^2+\binom{k+1}2= \maj(\tau)-\binom{\des(\tau)}2. \end{equation} By \eqref{eq:1} and \eqref{eq:2}, we have $m_1 < m_2$. Therefore $q_{\min}([x^{k}]B) = m_1$. By applying Lemma~\ref{lem:qmin} to $m_1$, we obtain the desired identity. \end{proof} Now we give a proof of Proposition~\ref{prop:min}. \begin{proof}[Proof of Proposition~\ref{prop:min}] First, observe that \[ q_{\min}([x^k]A) = \binom{k+1}2. \] If $P$ is a chain, then the identity permutation is the only linear extension of $P$. In this case $B=0$ and $b_i=i$. Thus \[ q_{\min}([x^k]F_P(q,x)) = q_{\min}([x^k]A) =\binom{k+1}2= b_1+\dots+b_k. \] Now suppose that $P$ is not a chain. By Lemma~\ref{lem:qmin2} and Corollary~\ref{cor:mc} we have \[ q_{\min}([x^k]B) =b_1+\dots+b_k \le \binom{k+1}2. \] Therefore we also obtain \[ q_{\min}([x^k]F_P(q,x)) = b_1+\dots+b_k. \qedhere \] \end{proof} \subsection*{Acknowledgements} The authors would like to thank the anonymous referee for his or her careful reading and helpful comments. \begin{thebibliography}{1} \bibitem{Barvinok1999} A.~Barvinok and J.~E. Pommersheim. \newblock An algorithmic theory of lattice points. \newblock {\em New perspectives in algebraic combinatorics}, 38:91, 1999. \bibitem{Beck2012} M.~Beck. \newblock Combinatorial reciprocity theorems. \newblock {\em Jahresbericht der Deutschen Mathematiker-Vereinigung}, 114(1):3--22, 2012. \bibitem{Beck2007} M.~Beck and S.~Robins. \newblock {\em Computing the continuous discretely}. \newblock Springer, 2007. \bibitem{Chapoton2016} F.~Chapoton. \newblock q-analogues of {E}hrhart polynomials. \newblock {\em Proceedings of the Edinburgh Mathematical Society (Series 2)}, 59:339--358, 2016. \bibitem{Ehrhart} E.~Ehrhart. \newblock Sur les poly{\`e}dres rationnels homoth{\'e}tiques {\`a} {$n$}\ dimensions. \newblock {\em C. R. Acad. Sci. Paris}, 254:616--618, 1962. \bibitem{KimStanton17} J.~S. Kim and D.~Stanton. \newblock On {$q$}-integrals over order polytopes. \newblock {\em Adv. Math.}, 308:1269--1317, 2017. \bibitem{Stanley_two_poset} R.~P. Stanley. \newblock Two poset polytopes. \newblock {\em Discrete Comput. Geom.}, 1(1):9--23, 1986. \bibitem{EC1} R.~P. Stanley. \newblock {\em Enumerative Combinatorics. {V}ol. 1, second ed.} \newblock Cambridge University Press, New York/Cambridge, 2011. \end{thebibliography} \end{document}