Order Polytopes of Dimension ≤ 13 \leq 13 are Ehrhart Positive

Feihu Liu, Guoce Xin, Zihao Zhang · 2024

Read Order Polytopes of Dimension ≤ 13 \leq 13 are Ehrhart Positive by Feihu Liu, Guoce Xin, Zihao Zhang (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-07164.txt.

Introduction

Feihu Liu, Guoce Xin, and Zihao Zhang settle a positivity question for shapes built from ordered sets, in this 2024 paper. An order polytope encodes a finite partially ordered set as a geometric body. Its Ehrhart polynomial counts lattice points in scaled copies, and positivity of its coefficients was long conjectured to hold widely.

Counterexamples exist in dimension fourteen and up, so the question became where the boundary lies. Dimensions up to eleven were already known positive. The trio now confirm positivity for dimensions twelve and thirteen as well, closing the gap and solving the open problem completely: positivity holds exactly through dimension thirteen. They also verify that the related h-star polynomials have only real roots in the same range. The result completes a clean classification for this family of polytopes.

Catalog record

CREATORFeihu Liu, Guoce Xin, Zihao Zhang
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-07164

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Order Polytopes of Dimension ≤ 13 \leq 13 are Ehrhart Positive Feihu Liu, Guoce Xin, Zihao Zhang Abstract The order polytopes arising from the finite poset were first introduced and studied by Stanley. For any positive integer d ≥ 14 d\geq 14 , Liu and Tsuchiya proved that there exists a non-Ehrhart positive order polytope of dimension d d . They also proved that any order polytope of dimension d ≤ 11 d\leq 11 is Ehrhart positive. We confirm that any order polytope of dimension 12 12 or 13 13 is Ehrhart positive. This solves an open problem proposed by Liu and Tsuchiya. Besides, we also verify that any h ∗ h^{*} -polynomial of order polytope of dimension d ≤ 13 d\leq 13 is real-rooted. Mathematic subject classification : Primary 05A15; Secondary 06A07, 68R05. Keywords : Order polytope; Ehrhart polynomial; Ehrhart positive; Real-rooted polynomial. 1 Introduction A convex polytope is called integral if any of its vertices has integer coordinates. Let \mathcal{P} represent a d -dimensional integral convex polytope in \mathbb{R}^{n} . The function \mathrm{ehr}(\mathcal{P},t)=|t\mathcal{P}\cap\mathbb{Z}^{n}|,\ \ \ \ \ t=1,2,\ldots, counts the integer points within t\mathcal{P} , where t\mathcal{P}=\{t\alpha:\alpha\in\mathcal{P}\} denotes the t -th dilation of \mathcal{P} . Ehrhart [ 5 ] proved that \mathrm{ehr}(\mathcal{P},t) is a polynomial in t of degree d . This polynomial is referred to as the Ehrhart polynomial of \mathcal{P} . Moreover, the coefficient of t^{d} in \mathrm{ehr}(\mathcal{P},t) equals the (relative) volume of \mathcal{P} , the coefficient of t^{d-1} is half of the boundary volume of \mathcal{P} , and the constant term is always 1 (see [ 2 ] ). The remaining coefficients are complicated to describe [ 14 ] . An integral convex polytope \mathcal{P} is said to be Ehrhart positive (or have Ehrhart positivity ) if all the coefficients of \mathrm{ehr}(\mathcal{P},t) are non-negative. In the case of dimension 3 , a well-known non-Ehrhart positive example is Reeve’s tetrahedron [ 2 , Example 3.22] . For a comprehensive introduction to Ehrhart positivity, please refer to Liu’s survey [ 9 ] . A recent development in Ehrhart positivity is presented in [ 7 ] . The generating function \mathrm{Ehr}(\mathcal{P},x)=1+\sum_{t\geq 1}\mathrm{ehr}(\mathcal{P},t)x^{t} is known as the Ehrhart series of \mathcal{P} . It is of the form \mathrm{Ehr}(\mathcal{P},x)=\frac{h^{*}(x)}{(1-x)^{d+1}}, where \dim\mathcal{P}=d and h^{*}(x) is a polynomial in x of degree \deg h^{*}(x)\leq d (as detailed in [ 2 ] ). The h^{*}(x) is usually referred to as the h^{*} -polynomial of \mathcal{P} . Stanley [ 18 ] proved that the coefficients of the h^{*} -polynomial are nonnegative integers. Subsequently, plenty of work has been done on various properties of the h^{*} -polynomial of an integral polytope. Let f(x)=a_{m}x^{m}+a_{m-1}x^{m-1}+\cdots+a_{1}x+a_{0} be a polynomial with nonnegative real coefficients. The polynomial f(x) is said to be unimodal if its coefficients satisfy a_{0}\leq\cdots\leq a_{i-1}\leq a_{i}\geq a_{i+1}\geq\cdots\geq a_{m} for some 0\leq i\leq m . It is called log-concave if a_{i}^{2}\geq a_{i-1}a_{i+1} for 1\leq i\leq m-1 . It is said to be real-rooted if all roots of f(x) are real numbers. If f(x) is real-rooted, then it is log-concave; If f(x) is log-concave with a_{i}>0 for all i , then it is unimodal. See [ 22 , Section 5] or [ 20 ] . This paper focuses on the families of order polytopes arising from finite partially ordered sets (or poset for short), which were initially introduced and studied by Stanley. See [ 19 ] for detailed definitions. Definition 1.1 (Stanley [ 19 ] ) . Given a poset P on the set [p]:=\{1,2,\ldots,p\} , we associate a polytope \mathcal{O}(P) , called the order polytope of P . It is defined to be the convex polytope consisting of those (x_{1},x_{2},\ldots,x_{p})\in\mathbb{R}^{p} such that \displaystyle x_{i}\leq x_{j}\ \ \ \text{if}\ \ \ i\prec_{P}j; \displaystyle 0\leq x_{i}\leq 1\ \ \ \text{for}\ \ \ 1\leq i\leq p. The order polytope is an integral polytope of dimension \dim\mathcal{O}(P)=p [ 19 ] . Regarding the Ehrhart positivity of order polytopes, Stanley provided an example of a non-Ehrhart-positive order polytope of dimension 21 in [ 23 ] (or [ 1 ] ). Subsequently, Liu and Tsuchiya [ 10 ] proved that for any positive integer d\geq 14 , there exists a non-Ehrhart-positive order polytope of dimension d . They also confirmed that any order polytope of dimension d\leq 11 is Ehrhart positive. Naturally, they proposed the following open question. Open Problem 1.2 (Liu–Tsuchiya, [ 10 ] ) . For d=12 or 13 , does there exist an order polytope of dimension d such that its Ehrhart polynomial has a negative coefficient? Our first contribution in this paper is to provide a negative solution to the above problem. That is, we confirm that any order polytope of dimension d\leq 13 is Ehrhart positive. Now the h^{*} -polynomial of order polytope \mathcal{O}(P) is denoted by h^{*}(x;P) . For any graded poset P , Reiner and Welker [ 16 ] proved that the h^{*}(x;P) is unimodal. Brändén [ 3 ] showed that the h^{*}(x;P) is not only unimodal but also symmetric. Recently, a comprehensive research development of h^{*} -polynomials was presented by Ferroni and Higashitani in [ 6 ] . They also raised the following open questions concerning order polytopes. Open Problem 1.3 . [ 6 , Section 6] or [ 25 , Section 7] For any graded poset P , prove that the h^{*} -polynomial h^{*}(x;P) is real-rooted. There exists an order polytope whose h^{*} -polynomial is not real-rooted. Such an example was given by Stembridge in [ 25 ] . Similarly, Ferroni and Higashitani also raised the following open questions. Open Problem 1.4 . [ 6 , Section 6] or [ 25 , Section 7] For a general poset P , prove that the h^{*} -polynomial h^{*}(x;P) is log-concave (or even unimodal). We verify that the h^{*} -polynomial of order polytopes \mathcal{O}(P) of dimension d\leq 13 is real-rooted. Consequently, these h^{*} -polynomials are log-concave and unimodal. This paper is organized as follows. In Section 2, we will briefly introduce how to compute the Ehrhart polynomial by Stembridge’s posets package [ 24 ] . In Section 3, we first introduce how to generate posets. Then we study the Ehrhart positivity of order polytopes of dimensions 12 and 13 . We also verify the real-rootedness of the h^{*}(x;P) of \#P\leq 13 . 2 Ehrhart Polynomial and h^{*} -polynomial Let P be a finite poset on [p] . The h^{*} -polynomial of the order polytope \mathcal{O}(P) is denoted by h^{*}(x;P)=h_{p}x^{p}+h_{p-1}x^{p-1}+\cdots+h_{1}x+h_{0}. Equivalently, the Ehrhart polynomial of \mathcal{O}(P) is given by \mathrm{ehr}(\mathcal{O}(P),t)=\sum_{i=0}^{p}h_{i}\binom{t+p-i}{p}. Stembridge’s posets package [ 24 ] can be used to compute the Ehrhart polynomial of \mathcal{O}(P) , but not directly. Denoted by \mathbf{t} the t -element chain on the set [t] . The number of order-preserving maps from P to \mathbf{t} turns out to be a polynomial in t of degree p . This polynomial is referred to as the order polynomial of P , and denoted \Omega_{P}(t) . Stanley [ 19 ] showed that \mathrm{ehr}(\mathcal{O}(P),t)=\Omega_{P}(t+1). The command omega in the posets package computes the order polynomial of P directly, and hence can be used to compute the Ehrhart polynomial. The package posets is available at: https://dept.math.lsa.umich.edu/ \sim jrs/. There are other algorithms to compute the Ehrhart polynomial or the h^{*} polynomial of a given order polytope. Stembridge’s

Read the complete text