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