\documentclass[finalversion]{FPSAC2018}
\articlenumber{27}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{hyperref,graphicx,color,tikz}

% \usepackage{a4wide}
\usepackage{soul}

%-------- Meta Data ------------------------------------------
\title[Proof of Chapoton's conjecture on Newton polygons of $q$-Ehrhart
polynomials (extended abstract)]{Proof of Chapoton's conjecture on Newton
polygons of $q$-Ehrhart polynomials\\ (extended abstract)}

\author{Jang Soo
Kim\thanks{\href{mailto:jangsookim@skku.edu}{jangsookim@skku.edu}}\addressmark{1}
and U-Keun
Song\thanks{\href{mailto:sukeun319@skku.edu}{sukeun319@skku.edu}}\addressmark{1}}

\address{\addressmark{1}Department of Mathematics, Sungkyunkwan
University, Suwon 16420, South Korea}

\received{\today}


\keywords{$q$-Ehrhart polynomial, Newton polygon, order polytope, $P$-partition}


% 06A07  Combinatorics of partially ordered sets
% 52B20  	Lattice polytopes (including relations with commutative algebra and algebraic geometry) [See also 06A11, 13F20, 13Hxx]
% 05A30 	$q$-calculus and related topics [See also 33Dxx]

% 06Axx	       Ordered sets
% 06A05  	Total order
% 06A06  	Partial order, general
% 06A07  	Combinatorics of partially ordered sets
% 06A11  	Algebraic aspects of posets
% 06A12  	Semilattices [See also 20M10; for topological semilattices see 22A26]
% 06A15  	Galois correspondences, closure operators
% 06A75  	Generalizations of ordered sets
% 06A99  	None of the above, but in this section

% 52Bxx	Polytopes and polyhedra
% 52B10  	Three-dimensional polytopes
% 52B11  	$n$-dimensional polytopes
% 52B12  	Special polytopes (linear programming, centrally symmetric, etc.)
% 52B15  	Symmetry properties of polytopes
% 52B20  	Lattice polytopes (including relations with commutative algebra and algebraic geometry) [See also 06A11, 13F20, 13Hxx]
% 52B40  	Matroids 
% 52B60  	Isoperimetric problems for polytopes

% 05Axx	Enumerative combinatorics {For enumeration in graph theory, see 05C30}
% 05A05 	Permutations, words, matrices
% 05A10 	Factorials, binomial coefficients, combinatorial functions [See also 11B65, 33Cxx]
% 05A15 	Exact enumeration problems, generating functions [See also 33Cxx, 33Dxx]
% 05A16 	Asymptotic enumeration
% 05A17 	Partitions of integers [See also 11P81, 11P82, 11P83]
% 05A18 	Partitions of sets
% 05A19 	Combinatorial identities, bijective combinatorics
% 05A20 	Combinatorial inequalities
% 05A30 	$q$-calculus and related topics [See also 33Dxx]
% 05A40 	Umbral calculus
% 05A99 	None of the above, but in this section
% 05Exx	Algebraic combinatorics
% 05E05  	Symmetric functions and generalizations
% 05E10  	Combinatorial aspects of representation theory [See also 20C30]
% 05E15  	Combinatorial aspects of groups and algebras [See also 14Nxx, 22E45, 33C80]
% 05E18  	Group actions on combinatorial structures
% 05E30  	Association schemes, strongly regular graphs
% 05E40  	Combinatorial aspects of commutative algebra
% 05E45  	Combinatorial aspects of simplicial complexes
% 05E99  	None of the above, but in this section

% 05Bxx		Designs and configurations {For applications of design theory, see 94C30}
% 05B05  	Block designs [See also 51E05, 62K10]
% 05B07  	Triple systems
% 05B10  	Difference sets (number-theoretic, group-theoretic, etc.) [See also 11B13]
% 05B15  	Orthogonal arrays, Latin squares, Room squares
% 05B20  	Matrices (incidence, Hadamard, etc.)
% 05B25  	Finite geometries [See also 51D20, 51Exx]
% 05B30  	Other designs, configurations [See also 51E30]
% 05B35  	Matroids, geometric lattices [See also 52B40, 90C27]
% 05B40  	Packing and covering [See also 11H31, 52C15, 52C17]
% 05B45  	Tessellation and tiling problems [See also 52C20, 52C22]
% 05B50  	Polyominoes
% 05B99  	None of the above, but in this section
% 05Cxx		Graph theory {For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15}
% 05C05  	Trees
% 05C07  	Vertex degrees [See also 05E30]
% 05C10  	Planar graphs; geometric and topological aspects of graph theory [See also 57M15, 57M25]
% 05C12  	Distance in graphs
% 05C15  	Coloring of graphs and hypergraphs
% 05C17  	Perfect graphs
% 05C20  	Directed graphs (digraphs), tournaments
% 05C21  	Flows in graphs
% 05C22  	Signed and weighted graphs
% 05C25  	Graphs and abstract algebra (groups, rings, fields, etc.) [See also 20F65]
% 05C30  	Enumeration in graph theory
% 05C31  	Graph polynomials
% 05C35  	Extremal problems [See also 90C35]
% 05C38  	Paths and cycles [See also 90B10]
% 05C40  	Connectivity
% 05C42  	Density (toughness, etc.)
% 05C45  	Eulerian and Hamiltonian graphs
% 05C50  	Graphs and linear algebra (matrices, eigenvalues, etc.)
% 05C51  	Graph designs and isomomorphic decomposition [See also 05B30]
% 05C55  	Generalized Ramsey theory [See also 05D10]
% 05C57  	Games on graphs [See also 91A43, 91A46]
% 05C60  	Isomorphism problems (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
% 05C62  	Graph representations (geometric and intersection representations, etc.) {For graph drawing, see also 68R10}
% 05C63  	Infinite graphs
% 05C65  	Hypergraphs
% 05C69  	Dominating sets, independent sets, cliques
% 05C70  	Factorization, matching, partitioning, covering and packing
% 05C72  	Fractional graph theory, fuzzy graph theory
% 05C75  	Structural characterization of families of graphs
% 05C76  	Graph operations (line graphs, products, etc.)
% 05C78  	Graph labelling (graceful graphs, bandwidth, etc.)
% 05C80  	Random graphs [See also 60B20]
% 05C81  	Random walks on graphs
% 05C82  	Small world graphs, complex networks [See also 90Bxx, 91D30]
% 05C83  	Graph minors
% 05C85  	Graph algorithms [See also 68R10, 68W05]
% 05C90  	Applications [See also 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15]
% 05C99  	None of the above, but in this section
% 05Dxx		Extremal combinatorics
% 05D05  	Extremal set theory
% 05D10  	Ramsey theory [See also 05C55]
% 05D15  	Transversal (matching) theory
% 05D40  	Probabilistic methods
% 05D99  	None of the above, but in this section

%-------- theorems ------------------------------------------
\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}
\newtheorem{question}[thm]{Question}
\newtheorem{problem}[thm]{Problem}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{note}{Note}
%-------- macros ------------------------------------------
\newcommand\comment[1]{\textbf{\color{red}#1}}

\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}}


%-------- start here ------------------------------------------




\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.}



\usepackage[backend=bibtex]{biblatex}
\addbibresource{27-Kim-Song.bib}


\begin{document}

\maketitle
% \tableofcontents


\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 \dots\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}. 

This is an extended abstract of \cite{KimSong}.

\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{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\}$.


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}

The following corollary is an immediate consequence of Proposition~\ref{prop:mc}. 

\begin{cor}\label{cor: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)$.
Then, for $0\le k\le m$, we have
\[
\min\left\{\maj(\pi)-k\des(\pi)+\binom{k+1}2: \pi\in\LL(P)\right\}
=b_1+\dots+b_k.
\]
Moreover, for $1\le k\le m$, if $P$ is not a chain, we have
\[
\min\left\{\maj(\pi)-k\des(\pi)+\binom{k+1}2: \pi\in\LL(P),
1\le \des(\pi)\le k\right\} =b_1+\dots+b_k.
\]
\end{cor}

Note that Corollary~\ref{cor:mc} allows us to find the minimum of $\maj(\pi)-k \des(\pi)$ over  $\pi\in\LL(P)$. 
The second part of Corollary~\ref{cor:mc} means that if $1\le k\le m$ and $P$ is not a chain, 
the minimum of $\maj(\pi)-k\des(\pi)+\binom{k+1}2$ for all $\pi\in\LL(P)$ is attained for $\pi\in\LL(P)$ satisfying
$1\le \des(\pi)\le k$. This will be used in the next section.



\section{Proof of Theorem~\ref{thm:main}}
\label{sec:proof-theor-refthm:m}

In this section we assume that $P$ is a naturally labeled poset on $\{1,2,\dots,m\}$
and $b_1\le b_2\le \dots\le b_m$ is the increasing rearrangement of $\mc(1),\dots,\mc(m)$.

For a polynomial $f(q)$ in $q$, define
\begin{align*}
q_{\max}(f(q)) &= \max\{i:[q^i]f(q) \ne 0\},\\
q_{\min}(f(q)) &= \min\{i:[q^i]f(q) \ne 0\}.
\end{align*}
When $f(q)=0$, we use the following convention:
\[
q_{\max}(0)=-\infty, \qquad q_{\min}(0)=\infty.
\]

Recall that
\begin{align*}
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)\\
&=\sum_{s=0}^{m-1} \sum_{\pi\in\LL(P), \des(\pi)=s} q^{\maj(\pi)}
\prod_{i=1}^m( q^{i-s} x + [i-s]_q).
\end{align*}
Since $P$ is naturally labeled, $\LL(P)$ contains the identity permutation. Therefore, 
\begin{equation}
  \label{eq:FAB}
F_P(q,x)=A+B,  
\end{equation}
where
\begin{align*}
A &=\prod_{i=1}^m( q^{i} x + [i]_q),\\
B &=x\sum_{s=1}^{m-1} \sum_{\pi\in\LL(P), \des(\pi)=s} q^{\maj(\pi)-\binom s2}
\prod_{i=1}^{s-1}(x - [i]_q)
\prod_{i=1}^{m-s}( q^{i} x + [i]_q).
\end{align*}
Since $[x^0]F_P(q,x)=[x^0]A=[m]_q!$, we have
\[
q_{\max}([x^0]F_P(q,x)) = \binom m2,\qquad q_{\min}([x^0]F_P(q,x)) = 0.
\]
Therefore, in order to prove Theorem~\ref{thm:main}, it suffices to show the following two propositions.

\begin{prop}\label{prop:max}
For $1\le k\le m$, we have
\[
q_{\max}([x^k]F_P(q,x)) = \binom m2 +k.
\]  
\end{prop}

\begin{prop}\label{prop:min}
For $1\le k\le m$, we have
\[
q_{\min}([x^k]F_P(q,x)) = b_1+\dots+b_k.
\]  
\end{prop}


\begin{proof}[Proof of Proposition~\ref{prop:max}]
By \eqref{eq:FAB}, it is enough to show that
\begin{equation}
  \label{eq:Amax}
q_{\max}([x^k]A) = \binom m2 +k,
\end{equation}
\begin{equation}
  \label{eq:Bmax}
q_{\max}([x^k]B) < \binom m2 +k.
\end{equation}
In order to get the largest power of $q$, when we expand the product in $A$, we 
must select $q^ix$ or $q^{i-1}$. This implies \eqref{eq:Amax}. 

To prove \eqref{eq:Bmax}, consider $\pi\in\Sym_m$ with $\des(\pi)=s\ge1$.
Then 
\begin{align*}
&q_{\max}\left([x^{k-1}] q^{\maj(\pi)-\binom s2}
\prod_{i=1}^{s-1}(x - [i]_q) \prod_{i=1}^{m-s}( q^{i} x + [i]_q)
\right)\\
&\le \sum_{i=1}^s(m-i)-\binom s2 + 
\sum_{i=1}^{s-1}(i-1) +\sum_{i=1}^{m-s}(i-1) + (k-1)\\
&= \binom m2 -(s-1)+(k-1) < \binom m2 +k.
\end{align*}
Therefore, we obtain~\eqref{eq:Bmax}. 
\end{proof}

The rest of this section is devoted to proving Proposition~\ref{prop:min}.  

For $\pi\in\Sym_m$ with $\des(\pi)=s\ge1$ and an integer $1\le k\le m$, let
\begin{equation}
  \label{eq:t}
t(\pi,k)=[x^{k-1}] q^{\maj(\pi)-\binom s2}
\prod_{i=1}^{s-1}(x - [i]_q) \prod_{i=1}^{m-s}( q^{i} x + [i]_q).
\end{equation}
Then we always have
\begin{equation}
  \label{eq:maj-s2}
q_{\min}(t(\pi,k)) \ge \maj(\pi)-\binom{\des(\pi)}2.  
\end{equation}

We need the following two lemmas.

\begin{lem}\label{lem:qmin}
Let $\pi\in\Sym_m$ with $\des(\pi)=s\ge1$. Then,
for $s\le k\le m$, we have
\[
q_{\min}(t(\pi,k))  =\maj(\pi)-ks+\binom{k+1}2.
\]
\end{lem}

\begin{lem}\label{lem:qmin2}
Let $P$ be a naturally labeled poset on  $\{1,2,\dots,m\}$. 
Suppose that  $P$ is not a chain. Then, for $1\le k\le m$, we have
\[
q_{\min}([x^{k}]B) = \min\left\{
\maj(\pi)-k\des(\pi)+\binom{k+1}2 : \pi\in\LL(P), 1\le \des(\pi)\le k 
\right\}.
\]
\end{lem}


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}

\acknowledgements{The authors would like to thank the anonymous referees
for their useful comments.}

\printbibliography

\end{document}


\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{KimSong}
J.~S. Kim and U.~Song.
\newblock Proof of Chapoton's conjecture on Newton polygons of q-Ehrhart polynomials.
\newblock arXiv:1704.05621.


\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}
