{'fraction_non_alphanumeric': 0.058306528337788245, 'fraction_numerical': 0.018151889940953504, 'mean_word_length': 3.9073662368460056, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 40, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On positivity of Ehrhart polynomials

Ehrhart discovered that the function that counts the number of lattice points in dilations of an integral polytope is a polynomial. We call the coefficients of this polynomial Ehrhart coefficients, and say a polytope is Ehrhart positive if all Ehrhart coefficients are positive (which is not true for all integral polytopes). The main purpose of this article is to survey interesting families of polytopes that are known to be Ehrhart positive and discuss the reasons from which their Ehrhart positivity follows. We also include examples of polytopes that have negative Ehrhart coefficients and polytopes that are conjectured to be Ehrhart positive, as well as pose a few relevant questions.


Introduction
A polyhedron in the D-dimensional Euclidean space R D is the solution set of a finite set of linear inequalities: where a i,j ∈ R, b i ∈ R and I is a finite set of indices. A polytope is a bounded polyhedron. Equivalently, a polytope in R D can also be defined as the convex hull of finitely many points in R D . We assume readers are familiar with basic definitions such as faces and dimensions of polytopes as presented in [108]. In this paper, the letter d usually denotes the dimension of a polytope and D denotes the dimension of the ambient space. For majority of the examples presented here, we either have d = D or d = D − 1.
A lattice point or an integral point is a point in Z D . Counting lattice points inside polytopes is a fundamental and useful step in many mathematical analyses. A lot of combinatorial structures can be counted as lattice points of polytopes. For example, matchings on graphs [63], t-designs [74], (semi-)magic squares [10,Chapter 6], and linear extensions of posets [100] are all of this form. Counting lattice points not only appears in combinatorial problems, it also appears, for instance, in the context of representation theory [52,89], algebraic geometry [37], statistics [34,36], and number theory [7,75].
One approach to study the question of computing the number of lattice points in a polytope P is to consider a more general counting problem: For any nonnegative integer t, let tP := {tx : x ∈ P } be the t th dilation of P , and then consider the function i(P, t) := |tP ∩ Z D |, which counts the number of lattice points in tP. We say two polytopes P and Q are unimodularly equivalent 1 if there exists an affine transformation from the affine hull aff(P ) of P to the affine hull aff(Q) of Q that induces a bijection from lattice points in aff(P ) to lattice points in aff(Q). Such an affine transformation is called a unimodular transformation. It is easy to see that if two polytopes P and Q are unimodularly equivalent, then i(P, t) = i(Q, t). An integral polytope (or a lattice polytope) is a polytope whose vertices are lattice points. In the 1960's Eugène Ehrhart [35] discovered that the function i(P, t) has nice properties when P is an integral polytope. Theorem 1.1 (Ehrhart). For any integral d-polytope P, the function i(P, t) is always a polynomial (with real coefficients) of degree d in t.
Thus, we call i(P, t) the Ehrhart polynomial of an integral polytope P , and call the coefficients of i(P, t) the Ehrhart coefficients of P. Note that Ehrhart's theorem can be extended to rational polytopes with the concept of a quasi-polynomial; however, we will focus on integral polytopes in this article.
There is much work on the Ehrhart coefficients of integral polytopes. In the 1990's, many people studied the problem of counting lattice points inside integral (or more generally rational) polytopes [17,22,50,81,85] by using the theory of toric varieties. Although explicit formulas for coefficients of Ehrhart polynomials can be deduced from these results, they are often quite complicated. Only three coefficients of i(P, t) have simple known forms for arbitrary integral polytopes P : the leading coefficient is equal to the normalized volume of P , the second coefficient is one half of the sum of the normalized volumes of facets, and the constant term is always 1.
Although these three coefficients can be described in terms of volumes (recall 1 is the normalized volume of a point), and thus are positive, it is not true that all the coefficients of i(P, t) are positive. (The first counterexample comes up in dimension 3 known as the Reeve tetrahedron; see §4.1.) We say a polytope has Ehrhart positivity or is Ehrhart positive if it has positive Ehrhart coefficients. It is natural to ask the following question: This turns out to be a challenging question. Even though multiple families of polytopes have been shown to be Ehrhart positive in the literature, the techniques involved are (almost) all different. In Section 2, we will survey families of polytopes with the Ehrhart positivity property, discussing different reasons why they have this property. In particular, as a consequence of the techniques discussed in §2.4, one can show that any combinatorial type of rational polytopes can be realized as an integral polytope that is Ehrhart positive (see Theorem 2.4.8). This result indicates that Ehrhart positivity is not a combinatorial property. Therefore, it is desirable to find more geometric methods to prove Ehrhart positivity. In Section 3, we introduce such a tool called McMullen's formula, which we use to give a refinement of Ehrhart positivity, called α-positivity. We then use this tool to attack the Ehrhart positivity conjecture of "generalized permutohedra", a family of polytopes introduced by Postnikov [82] and report partial progress on this conjecture. In Section 4, we include negative results on Question 1.2, presenting examples with negative Ehrhart coefficients. In particular, we will discuss progress on a question asked and studied by Hibi, Higashitani, Tsuchiya and Yoshida [48] on all possible sign patterns of Ehrhart coefficients (see §4. 2). Note that this question can be considered to be a refinement of Question 1.2. Finally, in Section 5, we include various conjectures on Ehrhart positivity, and pose related questions.
We finish our introduction with the following remark on the coefficients of the h * -polynomial, which is closely related to the Ehrhart polynomials.
Remark on h * -vector. One method of proving Ehrhart's theorem (Theorem 1.1) is by considering the Ehrhart series of a d-dimensional integral polytope P : It turns out that Theorem 1.1 is equivalent to the existence of a polynomial h * P (z) of degree at most d such that h * P (1) = 0 and See [102, Chapter 4] for a statement for the above equivalence result and a proof for Ehrhart's theorem.
We call h * P (z) the h * -polynomial of P , and the vector (h * 0 , h * 1 , . . . , h * d ), where h * i is the coefficient of z i in h * P (z), the h * -vector of P. One can recover the Ehrhart polynomial of a d-dimensional integral polytope P easily from its h * -vector: It is a well-known result due to Stanley that the entries in h * -vectors are all nonnegative integers [93] in contrast to the fact that Ehrhart coefficients could be negative. As a consequence, positivity is not such an interesting question for h * -polynomials. Nevertheless, active research have been conducted in other directions. The most natural question probably is: for each d, can we give a complete characterization for all possible h * -vector of d-dimensional integral polytopes? For d = 2, the answer was first provided in 1976 by Scott [90] known as Scott's condition. However, for d ≥ 3, the question is wide open. A lot of work has been done in the literature on searching for inequalities and equalities satisfied by h * -vectors. Most of them were discovered by Hibi [43,45,46,47] and Stanley [93,95] in the 1990s using commutative algebra and combinatorial methods. In 2009, Stapledon [103] contributes more inequalities using the idea of degree and codegree of a polytope. Known equalities on h * -vectors include Please see [8,103] for lists of known inequalities. Recently, instead of focusing on inequalities satisfied by all polytopes, much work has been done on finding inequalities for polytopes under certain constraints. For example, Treutlein [105] shows that the necessary statement of Scott's condition holds for any integral polytope whose h * -polynomial is of degree at most 2, i.e., h * i = 0 for all i > 2. Most recently, Balletti and Higashitani [5] improve the result further to any integral polytope whose h * -polynomial satisfies h * 3 = 0.
In the literature, there are multiple interesting families of polytopes shown to be Ehrhart positive using very different techniques. In this section, we put together a collection of such families, separating them into four categories based on the reasons why they are Ehrhart positive. However, we make no attempt to give a comprehensive account of all families with this property. We also note that as the leading coefficient of i(P, t) is the volume of P, one can often extract a formula for volume from descriptions for Ehrhart polynomials we give below. However, we will focus only on results on Ehrhart polynomials here, and omit related formulas for volumes.
In this article, we use bold letters to denote both vectors and points in R D . For example, e i denotes both the ith vector in the standard basis and the point (0, . . . , 0, 1, 0, . . . , 0) where 1 is in the ith position.
For convenience, we use N to denote the set of nonnegative integers, and P the set of positive integers.
2.1. Products of positive linear polynomials. In this part, we present families of polytopes whose Ehrhart polynomials can be described explicitly, which can be shown to have positive coefficients using the following naive lemma. We start with the two simplest families of polytopes: unit cubes and standard simplices, whose Ehrhart polynomials fit into situation (a) of Lemma 2.1.1, and thus Ehrhart positivity follows. As these are the first examples of Ehrhart polynomials in this article, and the computations are straightforward, we include all the details. For most of the remaining examples we discuss in this paper, we only state the results without providing detailed proofs.
2.1.1. Unit cubes. The d-dimensional unit cube, denoted by d , is the convex hull of all points in R d with coordinates in {0, 1}, i.e., It is easy to verify that the unit cube is the solution set to the following linear system of inequalities: Then for any t ∈ N, Thus, 2.1.2. Standard simplices. The d-dimensional standard simplex, denoted by ∆ d , is the convex hull of all the elements in the standard basis e 1 , e 2 , . . . , e d+1 of R d+1 : ∆ d := conv{e 1 , e 2 , . . . , e d+1 }.
Hence, for any t ∈ N, Hence, i(∆ d , t) counts the number of nonnegative integer solutions to This is a classic combinatorial problem which is the same as counting the number of weak compositions of t into d + 1 parts (see [102, Page 18]), and the answer is given by As we mentioned above, Ehrhart positivity of unit cubes and standard simplices follows from situation (a) of Lemma 2.1.1. Next, we present two families of examples with Ehrhart polynomials in the form of situation (b) of Lemma 2.1.1.
2.1.3. Pitman-Stanley polytopes. Let a = (a 1 , . . . , a d ) ∈ N d . The following polytope is introduced and studied by Pitman and Stanley [79]: Then the Ehrhart polynomial of PS d (a) is given by For each i, both a1t+1 i1 and a k t i k are products of linear polynomials in t with positive coefficients, so it follows from Lemma 2.1.1/(b) that any Pitman-Stanley polytope PS d (a) is Ehrhart positive.
Pitman-Stanley polytopes are contained in two different more general families of polytopes: flow polytopes and generalized permutohedra. For each of these two bigger families of polytopes, formulas for Ehrhart polynomials of some subfamily have been derived, generalizing Formula (2.1). We present results on flow polytopes in the next part below, while the results on generalized permutohedra are postponed to §3.1.2 as part of a general discussion on the Ehrhart positivity conjecture of generalized permutohedra in Section 3.
2.1.4. Subfamilies of flow polytopes. Let G be a (loopless) directed acyclic connected graph on [n + 1] = {1, 2, . . . , n + 1} such that each edge {i, j} with i < j is always directed from i to j. Hence, we denote the edge by (i, j) to indicate the orientation. For any a = (a 1 , a 2 , . . . , a n ) ∈ N n , we associate to it another vector Anā-flow on G is a vector f = (f (e)) e∈E(G) ∈ (R ≥0 ) E(G) such that for i = 1, 2, . . . , n, we have that is, the netflow at vertex i is a i . Note these conditions imply that the netflow at vertex n + 1 is − n i=1 a i . The flow polytope F G (ā) associated to G and the integer netflowā as the set of allā-flows f on G. For each edge e = (i, j) of G, we associate to it the positive type A n root α(e) = α(i, j) = e i − e j . For any b ∈ Z n+1 , the Kostant partition function KP G evaluated at b is It is straightforward to verify that for a ∈ N n , i.e., KP G (ā) counts the number of lattice points in the flow polytope F G (ā). In the literature, various groups of people [55,84,4,70] obtained formulas for Kostant partition functions, or equivalently, the number of lattice points in flow polytopes.
As a consequence, we can easily obtain formulas for the Ehrhart polynomial of F G (ā).
Suppose G is a connected graph on the vertex set [n + 1], with m edges directed i → j if i < j, and with at least one outgoing edge at vertex i for i = 1, . . . , n. Let out k (and in k , respectively) denote the outdegree (and the indegree, respectively) of vertex k in G minus 1.
Then for any a = (a 1 , . . . , a n ) ∈ N n , the Ehrhart polynomial of F G (ā) is given by where each summation is over all weak compositions j = (j 1 , . . . , j n ) of m − n that are ≥ (out 1 , . . . , out n ) in dominance order.
We remark that Lidskii [55] gives a formula for computing Kostant partition functions associated to the complete graph K n+1 , which yields Formula (2.3) above with G = K n+1 . Postnikov and Stanley [84, unpublished] were the first to discover Formula (2.3) for arbitrary graphs G using the Elliott-MacMahon algorithm. Baldoni and Vergne [4] give a proof for both formulas in Theorem 2.
is a product of linear polynomials in t with positive coefficients as long as in k = 0 or −1. Also, note that KP G (j 1 − out 1 , j 2 − out 2 , . . . , j n − out n , 0) is nonnegative and i(F G (ā), t) = 0. The following result immediately follows from Lemma 2.1.1/(b).  Proof. Let a > 0. If −a < 0 is a real root of p(t), then t + a is a factor of p(t). If −a + bi is a complex root of p(t) for some b ∈ R, then −a − bi must be a root of p(t) as well, which implies that is a factor of p(t). Hence, p(t) is a product of factors with positive coefficients. Thus, our conclusion follows.
We say that a polynomial (with real coefficients) is negative-real-part-rooted or NRPR if all of its roots have negative real parts. The above lemma implies that if i(P, t) is NRPR, then P is Ehrhart positive. Ehrhart polynomials of unit cubes and standard simplices are all trivially NRPR, as they factor into linear polynomials with positive real coefficients. Hence, we would like to rule them out, and are only interested in examples of Ehrhart polynomials that are nontrivially NRPR.
It turns out that the following theorem which establishes a connection between roots of the h * -polynomial and roots of the Ehrhart polynomial of a polytope is very useful. ). Let P be a d-dimensional integral polytope, let k be the degree of the polynomial h * P (z) (so that 0 ≤ k ≤ d), and suppose that every root of h * P (z) lies on the circle {z ∈ C : |z| = 1} in the complex plane. Then there exists a polynomial f (t) of degree k such that and every root of f (t) has real part −(1 + (d − k))/2.
We say a polytope P is h * -unit-circle-rooted if the h * -polynomial h * P (z) of P has all of its roots on the unit circle of the complex plane. Below we introduce three families of polytopes, and show that each polytope P in these families is h * -unitcircle-rooted. Therefore, Ehrhart positivity for these families follows from Theorem 2.2.2 and Lemma 2.2.1.

2.2.1.
Cross-polytopes. The d-dimensional cross-polytope, denoted by ♦ d , is a polytope in R d defined by or equivalently by the following linear system: Hence, i(♦ d , t) counts the number of integer solutions to Counting the number of integer solutions with exactly k nonzero x i 's for k = 0, 1, 2, . . . , d, we obtain that Unfortunately, it is not clear whether the above expression expands positively in powers of t. We compute its Ehrhart series instead. First, notice that i(♦ d , t) counts the number of integer solutions to where the summation is over all weak compositions (a 1 , . . . , a d , b) of t into d + 1 parts, g(b) = 1 for all b ≥ 0 and f (a) = 1 if a = 0 and f (a) = 2 if a > 0. Therefore, Thus, (1 + z) d is the h * -polynomial of the cross-polytope ♦ d . Hence, ♦ d is h * -unitcircle-rooted, and thus are Ehrhart positive. (1,q) . Let q = (q 1 , q 2 , . . . , q d ) ∈ P d be a sequence of positive integers. For each such a vector q, we define a simplex

Certain families of ∆
In [29], Conrads studied simplices of this form and showed that ∆ (1,q) is reflexive if and only if Recently, Braun, Davis and Solus studied ∆ (1,q) in their investigation of a Conjecture by Hibi and Ohsugi, and they provided a number-theoretic characterization of the h * -polynomial of ∆ (1,q) Formula (2.5) allows us to compute the h * -polynomial for ∆ (1,q) with special choices of q easily. We give two examples below such that ∆ (1,q) satisfies the hypothesis of Theorem 2.2.2 with k = d.
Example 2.2.4 (Standard reflexive simplices). If we choose q = 1 = (1, 1, . . . , 1) ∈ P d , then ∆ (1,q) is the d-dimensional standard reflexive simplex. Note that in this case, we have that q 1 + q 2 + · · · + q d = d. Furthermore, for each b ∈ {0, 1, 2, . . . , d}, one can verify that w(b) = b. Hence, Example 2.2.5 (Payne's construction). In [78], Payne constructed reflexive simplices that do not have unimodal h * -vectors. His construction is equivalent to the simplices ∆ (1,q) with the following choices of q : Given r ≥ 0, s ≥ 3 and k ≥ r + 2, let d = r + sk and   2.2.3. One family of order polytopes. Given a finite poset (partially ordered set) P, the order polytope, denoted by O(P), is the collection of functions x ∈ R P satisfying • 0 ≤ x a ≤ 1, for all a ∈ P, and • x a ≤ x b , if a ≤ b in P. The order polytope O(P) was first defined and studied by Stanley [100]. Here we consider a family of order polytopes constructed from a certain family of posets.
Let P k be the ordinal sum of k copies of 2 element antichains, equivalently, P k is the poset on the 2k-element set {a i,j : i = 1, 2 and j = 1, 2, . . . , k} satisfying Hence, i(O(P k ), t) counts the number of integer solutions x satisfying the above two conditions. Note that each solution gives a weak composition (y 1 , z 1 , y 2 , . . . , y k , z k , y k+1 ) of t into 2k + 1 parts, where and by convention let max(x 1,0 , x 2,0 ) = 0 and min(x 1,k+1 , x 2,k+1 ) = t. Thus, where the summation is over all weak compositions of t into 2k + 1 parts, g(y) = 1 for all y ≥ 0, and f (z) = 1 if z = 0 and f (z) = 2 if z > 0. Therefore, similar to the calculation for cross-polytopes, we obtain  Therefore, the conclusions we draw above for the order polytope O(P k ) all hold for the chain polytope C(P k ).
It turns out that the polytopes studied in §2.2.1 and §2.2.2 are "reflexive" polytopes, and the order polytopes studied in §2.2.3 are "Gorenstein" polytopes. These are not coincidences as we will discuss below.
Connection to reflexivity and Gorensteinness. An integral polytope P in R D is reflexive (up to lattice translation) if the origin is in the interior of P and its dual It follows from the Macdonald Reciprocity Theorem [64] that if an integral polytope P is reflexive, then the roots of i(P, t) are symmetrically distributed with respect to the line {z ∈ C : Re(z) = −1/2} in the complex plane. Bey, Henk and Wills show that the converse is true if we include polytopes that are unimodularly equivalent to reflexive polytopes [ Reflexive polytopes are special cases of a more general family of polytopes: Gorenstein polytopes. Recall that the codegree of P is defined to be codeg(P ) := dim(P ) + 1 − deg (h * P (z)) . It is (again) a consequence of the Macdonald Reciprocity Theorem [64] that codeg(P ) is the smallest positive integer s such that sP contains a lattice point in its interior (see, for example, [44]). A Gorenstein polytope is an integral polytope P of codegree s such that sP is a reflexive polytope. The work [99] of Stanley gives a nice characterization for the h * -polynomials of Gorenstein polytopes: a d-dimensional integral polytope P is a Gorenstein polytope if and only if its h * -polynomial is symmetric, Furthermore, if the above condition holds, the integer s is the codegree of P.
Proof. The conclusion of the lemma follows from the observation that a number t 0 is a root of i(P, t) if and only if t 0 /s is a root of i(sP, t).
Then P is a Gorenstein polytope (up to unimodular transformation). Moreover, if the degree of the h * -polynomial h * P (z) is d, then P is reflexive. Proof. Let k be the degree of h * P (z). By Theorem 2.2.2, among all the roots of i(P, t), k of them have real parts −(1 + (d − k))/2, and the other (d − k) roots are −1, −2, . . . , −(d − k). As i(P, t) is a polynomial with real coefficients, the sum of roots of i(P, t) is the sum of the real parts of roots of i(P, t), which is Then the conclusions follow from Lemma 2.2.8.
Therefore, when an integral polytope P is h * -unit-circle-rooted, we not only get Ehrhart positivity for P but can also conclude that P is a Gorenstein polytope of codegree d − k + 1, where k is the degree of the h * -polynomial of P.

Coefficients with combinatorial meanings.
2.3.1. Zonotopes. In this part, we introduce a special family of polytopes, zonotopes, whose Ehrhart coefficients can be described combinatorially. As a consequence, Ehrhart coefficients of a zonotope are not only positive but also positive integers.
The Minkowski sum of two polytopes (or sets) P and Q is In [96, Theorem 2.2], Stanley gives a combinatorial description for the Ehrhart coefficients of zonotopes.
where X ranges over all linearly independent k-subsets of {v 1 , . . . , v n }, and h(X) is the greatest common divisor of all k × k minors of the matrix whose column vectors are elements of X.
The main ingredient for the proof of the above theorem is that Z(v 1 , . . . , v n ) can be written as a disjoint union of half open parallelepiped C X ranging over all linearly The theorem then follows from the fact that the number of lattice points in the half open parallelepiped C X is the volume of C X , which can be calculated by h(X).
The simplest examples of zonotopes are unit cubes considered in §2.1.1. We may recover the Ehrhart polynomial of a unit cube using Theorem 2.3.1. However, a more interesting example is the regular permutohedron.
The regular permutohedron, denoted by Π d , is the convex hull of all permutations in S d+1 ; that is, For Then it follows from matroid theory that X is linearly independent if and only if G X is a forest on [d + 1]. (Recall that a forest is a collection of trees, or equivalently, is acyclic.) Furthermore, if X is linearly independent, then G X is a forest of d+1−|X| trees, and h(X) (described in Theorem 2.3.1) is 1.
Therefore, we conclude that the coefficient of t k in i(Π d , t) counts the number of forests on [d + 1] that contain exactly d + 1 − k trees. Therefore, we can compute, for example, i(Π 3 , t) = 16t 3 + 15t 2 + 6t + 1.

2.3.2.
Positivity of a generalized Ehrhart polynomial. The polynomial we discuss in this part is not exactly an Ehrhart polynomial. However, it is closely related to the result on zonotopes we have presented in the last part, and thus is included here. Galashin, Hopkins, McConville and Postnikov, in their study of root system chip firing [38], considered the following lattice points counting problem: Given an integral polytope P and a set of integer vectors v 1 , v 2 , . . . , v n , describe the number of lattice point in Then there exists a polynomial L(t) = L(t 1 , . . . , t n ) in n variables with nonnegative integer coefficients such that |(P + tZ) ∩ Z D | = L(t).
In particular, if we take t = (t, t, . . . , t), then is a polynomial in t of degree dim(Z) with positive integer coefficients.
Note that the second part of the above theorem was not explicitly stated in [38, Theorem 16.1]; but it was a consequence of the techniques used in its proof.
One sees that if we choose P to be the origin, then the above theorem recovers the Ehrhart positivity of zonotopes. However, in contrast with Stanley's results, no explicit formulas were given in [38] for the positive/nonnegative integer coefficients asserted in Theorem 2.3.3. Recently, Hopkins and Postnikov [49] analyzed techniques used in [38] further, and provided the desired explicit formula, completing the generalization of Theorem 2.3.1.
Theorem 2.3.4 (Hopkins-Postnikov). The homogeneous degree k part of the polynomial L(t) assumed by Theorem 2.3.3 is given by where X ranges over all linearly independent k-subsets of {v 1 , . . . , v n }, quot X : is the canonical quotient map, and h(X) is the greatest common divisor of all k × k minors of the matrix whose column vectors are elements of X.

2.4.
Higher integrality conditions. In this part, we will introduce families of polytopes whose Ehrhart coefficients are always volumes of certain projections of the original polytopes and are hence positive.
2.4.1. Cyclic polytopes. We start with a well-known family of polytopes: cyclic polytopes: The moment curve in R d is defined by Let U = {u 1 , . . . , u n } < be a linear ordered set. Then the cyclic polytope C d (U ) = C d (u 1 , . . . , u n ) is the convex hull of n > d distinct points ν d (t i ), 1 ≤ i ≤ n, on the moment curve: Cyclic polytopes form an interesting family of polytopes. For instance, its facets are determined by the Gale evenness condition [108, Theorem 0.7], and the number is the upper bound for the number of i-dimensional faces of all d-dimensional polytopes with n vertices [66].
The following theorem on the Ehrhart polynomial of integral cyclic polytopes was initially conjectured in [8] by Beck, De Loera, Develin, Pfeifle and Stanley, and then proved in [56] by the author.
The first step of the proof is to reduce the problem to simplices by using triangulations. For the simplex case, we consider the set obtained by removing the lower envelope of C d (U ) (with |U | = d + 1), and we decompose this set into d! signed (convex) half-open sets S σ , each of which corresponds to a permutation σ in the symmetric group S d . One important feature of this decomposition is that the number of lattice points in each piece S σ can be expressed in a simple formula involving the permutation σ, which makes it possible to compute the summation of all d! terms.
2.4.2. k-integral polytopes. Since the work in [56], the author generalized the family of integral cyclic polytopes to a bigger family of integral polytopes, "latticeface polytopes", and showed that their Ehrhart polynomials are also in the simple form of (2.6) [57, 58]. Later in [59], the author improved her results by introducing a notion of "higher integrality", which we will detail below.
Recall that a lattice point is also called an integral point. A point can be considered as a 0-dimensional affine space. We first extend this concept of integrality to higher dimensional affine spaces: Note that this definition with ℓ = 0 is consistent with the original definition of an integral point.  Note that in the above example, even though L 1 is not integral, after the projection, we still get a 1-dimensional lattice, which has the same dimension as L 1 .
In this case, we say L 1 is in general position. On the contrary, L 2 is not in general position.
for any face F of P of dimension less than or equal to k, the affine hull aff(F ) of F is integral.
In particular, when k = d, we call P a fully integral polytope.
Remark 2.4.4. With the above definition, lattice-face polytopes, introduced in [57, 58], can be defined as polytopes that can be triangulated into fully integral simplices, which is a property any (integral) cyclic polytope has. Therefore, any cyclic polytope or lattice-polytope is fully integral.
The main result in [59] is a complete description for the Ehrhart coefficients of a k-integral polytope in terms of volumes of projections and Ehrhart polynomials of slices.
Definition 2.4.5. For any y ∈ π (d−k) (P ), we define the slice of P over y, denoted by π d−k (y, P ), to be the intersection of P with the inverse image of y under π (d−k) .
Theorem 2.4.6 (L.). If P is a k-integral polytope, then Therefore, if P is fully integral, the Ehrhart polynomial of P is in the form of (2.6), and thus P is Ehrhart positive.
Because both cyclic polytopes and lattice-face polytopes are fully integral polytopes, the above theorem generalizes results in [56,57,58].
The following is an example showing how to use Theorem 2.4.6 to obtain the Ehrhart polynomial of a 1-integral polytope. For the higher Ehrhart coefficients of P , we need to compute the Ehrhart polynomials of slices of P over lattice points in π (2) (P ) = [0, 4]. In the picture, the three shaded triangles are the slices of P over the lattice points 1, 2 and 3. The slices of P over lattice points 0 and 4 are the single points (0, 0, 0) and (4, 0, 0), respectively. We calculate the Ehrhart polynomials of all five slices, by summing which up we obtain 8t 2 + 10t + 5. Then the second part of Theorem 2.4.6 says that Therefore, i(P, t) = 8t 3 + 10t 2 + 4t + 1.
Recall that the face poset of a polytope P is the set of all faces of P ordered by inclusion. We say two polytopes have the same combinatorial type if they have the same face poset. As a byproduct of the study of Ehrhart polynomials of fullintegral polytopes, we can also show that Ehrhart positivity is independent from combinatorial types of polytopes [58].
Theorem 2.4.8 (L.). For any rational polytope P, there exists a polytope P ′ with the same face lattice such that P ′ satisfies the higher integrality condition and thus is Ehrhart positive.
Sketch of proof. First, by choosing appropriate bases for our underlying lattice Z d , we may assume that the affine hull of any face of P is in general position.
Next, for any s = (s 1 , . . . , s d ) ∈ Z d and x ∈ R d , we define So s is an operator on R d that dilates points with different scalars at different coordinates. We observe that for any ℓ-dimensional affine space W ⊂ R d that is in general position, there exist (positive) integer scalars c 1 , . . . , c ℓ such that for any Since P has finitely many faces, we can apply the above operations inductively on dimensions of faces to obtain a full integral polytope P ′ that actually defined as s ⋆ P for some s ∈ Z d =0 .
Remark 2.4.9. There are a lot of properties of polytopes people study other than Ehrhart positivity, such as "normality", "integer decomposition property" (or IDP), "existence of a (regular) unimodular triangulation". For the majority of them, even if you start with a polytope P that does not have a certain property, dilating P with a large enough scalar often yields a polytope with the desired property (see, for example, [19,30,39]). Clearly, simple dilations won't change the answer to the Ehrhart positivity question for any polytope. After all, i(kP, t) = i(P, kt). Hence, the Ehrhart coefficients of a dilation of P have exactly the same sign pattern as Ehrhart coefficients of P. However, our proof of Theorem 2.4.8 says that dilating in different directions with different scalars can change a non-Ehrhart-positive polytope to a Ehrhart-positive one.

McMullen's formula and positivity of generalized permutohedra
The main purpose of this section is to study the Ehrhart positivity conjecture for generalized permutohedra. After reviewing previously known results supporting this conjecture, we introduce McMullen's formula, which is a formula for computing the number of lattice points inside polytopes. This provides us a way of attacking the question of Ehrhart positivity by reducing the problem to "α-positivity". We then discuss the author's joint work [26,24] with Castillo on the Ehrhart positivity conjecture of generalized permutohedra using this approach.
3.1. Motivation and evidence. In this part, we discuss the motivation for considering the Ehrhart positivity conjecture of generalized permutohedra and prior work by Postnikov which provides evidence for this conjecture. We start by formally defining generalized permutohedra, the main family of polytopes we study in this section. Whenever we talk about generalized permutohedra, we have D = d + 1.
3.1.1. Definition and first positivity conjecture. Given a strictly increasing sequence α = (α 1 , α 2 , · · · , α d+1 ) ∈ R d+1 , we define the usual permutohedron associated with α as Perm(α) := conv (α π(1) , α π(2) , · · · , α π(d+1) ) : π ∈ S d+1 In particular, if α = (1, 2, . . . , d + 1  Indeed, due to Postnikov's work, a big family of generalized permutohedra is already known to be Ehrhart positive, which provides a strong evidence to the above conjecture. We describe his work below. y I ∆ I as the Minkowski sum of the simplices ∆ I dilated by the factor y I . Postnikov shows that P Y d (y) is always a generalized permutohedron [82, Proposition 6.3]; however not every generalized permutohedron can be expressed as P Y d (y) for some y [82, Remark 6.4]. Therefore, we call P Y d (y) a type-Y generalized permutohedron. Postnikov then reformulates the construction of P Y d (y) using bipartite graphs: Let G be a subgraph of the bipartite graph K c,d+1 without isolated vertices. Label the vertices of G on the left by l 1 , l 2 , . . . , l c and vertices on the right by r 1 , r 2 , . . . , r d+1 . For each 1 ≤ j ≤ c, we let  In [82, Section 11], Postnikov defines the "trimmed generalized permutohedron" as the "Minkowski difference" of P G (y 1 , . . . , y c ) and the simplex ∆ [d+1] . By providing a formula for the number of lattice points in a trimmed generalized permutohedron, he obtains a formula for the number of lattice points in P G (y 1 , . . . , y c ) [82,Theorem 11.3], which leads to an expression for the Ehrhart polynomial of P G (y 1 , . . . , y c ) as a summation over G-draconian sequences. , we have |I G j1 ∪ · · · ∪ I G j k | ≥ g j1 + · · · + g j k + 1. Theorem 3.1.4 (Postnikov). Suppose G is a subgraph of K c,d+1 without isolated vertices such that I G 1 = [d + 1]. Let y 1 , . . . , y c ∈ N. Then the Ehrhart polynomial of P G (y 1 , . . . , y c ) is given by where the summation is over all G-draconian sequences g = (g 1 , . . . , g c ).
Similar to the results discussed in §2.1.3 and §2.1.4, it follows from Lemma 2.1.1/(b) that the Ehrhart polynomial described in the above theorem has positive coefficients. Thus, by Remark 3.1.2, we immediately have the following: Note that as we pointed out above, type-Y generalized permutohedra do not contain all generalized permutohedra. Thus, Conjecture 3.1.1 does not follow from the above result.
Hence, it can be verified that Theorem 2.1.2 is a special case of Theorem 3.1.4.
The family of type-Y generalized permutohedra not only includes the Pitman-Stanley polytope as we have seen in the example above, but also includes associahedra, cyclohedra, and more (see [82,Section 8]). However, it follows from work by Ardila, Benedetti and Doker that type-Y generalized permutohedra do not contain all matroid base polytopes [1, Proposition 2.3 and Example 2.6]. Therefore, Corollary 3.1.5 does not settle either Conjecture 3.1.1 or the Ehrhart positivity conjecture on matroid base polytopes by De Loera et al [31].

3.2.
McMullen's formula, α-positivity, and a reduction theorem. The goal of this part is to introduce McMullen's formula and discuss why it is a good tool to show Ehrhart positivity of a family of polytopes constructed from a fixed projective fan when an α-construction satisfies certain valuation properties. (We will discuss in §3.3 that generalized permutohedra form a family of polytopes constructed from the Braid fan. Hence, the techniques introduced here are relevant to our question.) Throughout the rest of this section, we let V be a subspace of R D and V * be the dual space of V. For any polytope P , we use the notation lin(P ) to denote the linear space obtained by shifting the affine span aff(P ) to the origin.

Cones.
We need the concepts of cones, particularly feasible cones and normal cones, before we start our discussion.
A (polyhedral) cone is the set of all nonnegative linear combinations of a finite set of vectors. A cone is pointed if it does not contain a line. (ii) Given any face F of P , the normal cone of P at F with respect to V is ncone V (F, P ) := {u ∈ V * : u, p 1 ≥ u, p 2 , ∀p 1 ∈ F, ∀p 2 ∈ P } .
Therefore, ncone V (F, P ) is the collection of linear functionals u in V * such that u attains maximum value at F over all points in P.
The normal fan Σ V (P ) of P with respect to V is the collection of all normal cones of P .
Normal cones and pointed feasible cones are related by polarity.   [24]). Suppose P is a polytope satisfying lin(P ) ⊆ V and F is a face of P. Then (ncone V (F, P )) • is a pointed cone, and is invariant under the choice of V . So we may omit the subscript V and just write (ncone(F, P )) • . Furthermore, ncone(F, P ) • = fcone p (F, P ).

3.2.2.
McMullen's formula and a refinement of positivity. In 1975 Danilov asked, in the context of toric varieties, whether it is possible to construct a function α such that for any integral polytope P , we have where α(F, P ) depends only on the normal cone of P at F, and nvol(F ) is the volume of F normalized to the lattice aff(F ) ∩ Z D .
McMullen [67] was the first to confirm the existence of (3.1) in a non-constructive way. Hence, we refer to the above formula as McMullen's formula. Pommersheim and Thomas [80] provide a canonical construction based on choices of flags. Berline and Vergne [11] give a construction in a computable way. Most recently, Ring-Schürmann [87] give another construction for McMullen's formula based on a choice of fundamental cells.
Before discussing a specific construction, even the existence of McMullen's formula has interesting consequences. In fact, it was one of the ingredients used in proving the results on higher integrality conditions discussed in §2.4.2. More importantly, it provides another proof for Ehrhart's theorem (Theorem 1.1) as well as a refinement of Ehrhart positivity. Note that pointed feasible cones do not change when we dilate a polytope. Thus, applying McMullen's formula to tP and rearranging coefficients, we obtain a formula for the function i(P, t) : Hence, i(P, t) is a polynomial in t of degree dim P, and the coefficient of t k in i(P, t) is given by  Note that [t 0 ]i(P, t) is the constant term of the Ehrhart polynomial of P, which is known to be 1 for any integral polytope P. Furthermore, the normalized volume of any vertex is 1. Hence, the above equation becomes v:vertex of P α(P, v) = 1.
See Figure 2 for α-values of the vertices of the triangle P = conv((0, 0), (2, 0), (2, 1)) arising from different constructions. Berline-Vergne Since nvol(F ) is a positive number, it follows from (3.2) that α-values refine Ehrhart coefficients. We say a polytope P is α-positive for k-faces if α(F, P ) is positive for all k-dimensional faces F of P, and say P is α-positive if all α's associated to P are positive. The following result immediately follows from expression (3.2). Lemma 3.2.5. Suppose α is a solution to McMullen's formula. Let P be an integral polytope. For a fixed k, if P is α-positive for k-faces, then the coefficient of t k in the Ehrhart polynomial i(P, t) of P is positive.

Pommersheim-Thomas
Hence, if P is α-positive, then P is Ehrhart positive.

BV-construction and the Reduction Theorem.
At the first glance, αpositivity, being a refinement of Ehrhart-positivity, is a more difficult question to consider. However, for α-constructions that satisfy certain properties, studying α-positivity instead does not necessarily make the problem harder. Berline and Vergne [11] give such an α-construction, of which we give a quick review below.  We refer to Berline-Vergne's construction of Ψ and α as BV-construction and BV-α-valuation, respectively. If α is the BV-α-valuation, we use the terminology BV-α-positivity instead of α-positivity.

Recall that the indicator function of a set
Properties (P1) and (P2) are the "certain valuation properties" we mentioned at the beginning of §3.2. The following Reduction Theorem lays out a consequence of these two properties.
Theorem 3.2.7 (Castillo-L., Reduction Theorem [24]). Suppose Ψ is a function from the set of indicator functions of rational cones C in V to R such that properties (P1) and (P2) hold, and suppose α is defined as in (3.3).
Let P and Q be two polytopes such that lin(P ) and lin(Q) are both subspaces of V. Assume the normal fan Σ V (P ) of P with respect to V is a refinement of the normal fan Σ V (Q) of Q with respect to V .
Then for any fixed k, if P is α-positive for k-faces, then Q is α-positive for k-faces.
One important implication of the Reduction Theorem is that we can reduce the problem of α-positivity of a family of polytopes constructed from a fan to the problem of α-positivity of a single polytope in the family. Definition 3.2.8. Let Σ be a projective fan in V * , i.e., a fan that is a normal fan of some polytope. Let Poly(Σ) be the set of polytopes Q whose normal fan Σ V (Q) with respect to V coarsens Σ.
Corollary 3.2.9. Assume the hypothesis on Ψ and α in Theorem 3.2.7. Let Σ be a projective fan in V * , and let P be a polytope such that Σ V (P ) = Σ. Then α-positivity (for k-faces) of P implies α-positivity (for k-faces) of Q for any Q ∈ Poly(Σ).
Assume further that α is a solution to McMullen's formula. Then for any integral polytope Q ∈ Poly(Σ), α-positivity for k-faces of P implies the coefficient of t k in i(Q, t) is positive. Hence, α-positivity of P implies Ehrhart-positivity of Q.
Proof. The first part follows directly from the Reduction Theorem, and the second assertion follows from the first part and Lemma 3.2.5.
Therefore, even though proving α-positivity is more difficult than proving Ehrhartpositivity for an individual polytope, it could be easier if we consider a family of polytopes Poly(Σ) associated to a fixed projective fan Σ, as we only need to prove α-positivity for one polytope in the family. Finally, because the BV-construction satisfies properties (P1), (P2) and (P4), all the results discussed above apply to the BV-construction or the BV-α-valuation. These ideas are illustrated by Example 3.3.3 below.
3.3. Positivity of generalized permutohedra. In this part, we apply the Reduction Theorem to reduce our first conjecture -Conjecture 3.1.1 -to a conjecture on α-positivity of regular permutohedra. Then we report partial progress made on both conjectures by using McMullen's formula with BV-α-valuation [26, 24].
3.3.1. Second positivity conjecture. Postnikov, Reiner, and Williams give several equivalent definitions for generalized permutohedra, one of which uses concepts of normal fans [83,Proposition 3.2]. Recall that the Braid fan, denoted by Br d , is the complete fan in R d+1 given by the hyperplanes x i − x j = 0 for all i = j. Proposition 3.3.1 (Postnikov-Reiner-Williams). A polytope P in V = R d+1 is a generalized permutohedron if and only if its normal fan Σ V (P ) with respect to V is refined by the Braid fan Br d .
Using the notation we give in Definition 3.2.8, the above result precisely says that the family of generalized permutohedra in R d+1 is Poly(Br d ). Furthermore, it follows from [82, Proposition 2.6] that any usual permutohedron in R d+1 has the Braid fan Br d as its normal fan. In particular, the normal fan of the regular permutohedron Π d is Br d . In [24], Castillo and the author use these results together with the Reduction theorem and its consequence (i.e., Corollary 3.2.9) to reduce Conjecture 3.1.1 to the following conjecture: The following example demonstrates how Corollary 3.2.9 works and why Conjecture 3.1.1 can be reduced to Conjecture 3.3.2.    Figure 3. One notices that P is the regular permutohedron Π 2 whose normal fan is Br 2 , and each Q i is a generalized permutohedron whose normal fan coarsens Br 2 .
All the BV-α-values of the six vertices of P are 1/6. Since Q 1 has the same normal fan as P , all of its six vertices also have the same BV-α-values. Now the normal fan of Q 2 coarsens that of P. In particular, if we let v be the vertex on the bottom-left of Q 2 , then the normal cone ncone(v, Q 2 ) of Q 2 at v is the union of the normal cones of P at two of its vertices. It is a consequence of the "valuation properties" (P1) and (P2) that the BV-α-values α(v, Q 2 ) is the sum of the BV-α-values of these two vertices of P. Therefore, as shown in the figure, α(v, Q 2 ) = 1/6 + 1/6 = 1/3. One sees that similar phenomenon happens for the polytope Q 3 .
The above discussion shows that even if we did not know the BV-α-values of vertices of P, because each BV-α-value arising from Q i is a summation of a subset of BV-α-values of vertices of P, BV-α-positivity of vertices of the regular permutohedron P = Π 2 would imply BV-α-positivity of vertices of the generalized permutohedron Q i , and thus would imply the constant Ehrhart coefficient of Q i is positive. Conjecture 3.3.2 was the main conjecture studied in [24], and partial progress was made on proving it, which gave us corresponding partial results on Conjecture 3.1.1.

3.3.2.
Partial results. The first approach of attacking Conjecture 3.3.2 is to directly compute BV-α-valuations. In order to do that, we need to compute the BV-construction Ψ. One obvious benefit of considering Conjecture 3.3.2 instead of Conjecture 3.1.1 is that in each dimension there is only one regular permutohedron, and thus there are a limited number of BV-α-values or Ψ-values to be computed, especially for small d. Therefore, by explicit computation, we obtain the following result. Next, instead of focusing on all the coefficients of Ehrhart polynomials, we study certain special coefficients. Note that the first, second and last Ehrhart coefficients are always positive, so we only consider other Ehrhart coefficients. Correspondingly, we need to know how to compute the BV-construction Ψ(C) of cones C of dimension 2, 3, . . . , d − 1. The computation of the function Ψ is carried out recursively. Hence, it is quicker to compute Ψ for lower dimensional cones. As a result, the value of α(F, P ) is easier to compute if F is a higher dimensional face.
In general, the computation of Ψ(C) is quite complicated. However, when C is a unimodular cone computations are greatly simplified. In dimensions 2 and 3, with the help of Maple code provided by Berline and Vergne, simple closed expression for Ψ of unimodular cones can be obtained [24, Lemmas 3.9 and 3.10]. Applying these formulas to Π d , we obtain the second partial result towards Conjectures 3.3.2 and 3.1.1: Hence, the third and fourth Ehrhart coefficients of any integral generalized permutohedron (including matroid base polytopes) are positive.
Finally, the last partial result presented in [24] is the following: Hence, the linear Ehrhart coefficient of any integral generalized permutohedron (including matroid base polytopes) of dimension at most 500 is positive.
As we have discussed above, in order to compute the BV-α-values for an edge of a d-dimensional polytope, we have to compute the Ψ-value of a (d − 1)-dimensional cone, which is extremely difficult for large d if we use Berline-Vergne's algorithm directly. Therefore, we use a completely different strategy. Recall Property (P3) of the BV-construction, which says that Ψ is symmetric about coordinates. Note that the regular permutohedron Π d is a polytope with much symmetry. So a lot of BV-α-values of Π d coincide. In particular, we can separate edges of Π d into to d 2 groups, where edges in each group share the same BV-α-values.
Idea of Proof for Lemma 3.3.6. If we know the α-values for a give polytope P, Equation (3.2) gives us a way to compute the Ehrhart coefficients. However, we can also use (3.2) in the other direction: Suppose we know the linear coefficient of i(P, t), Equation (3.2) gives us an equation for α-values arising from edges of P : The α-values for the regular permutohedron also appear in other generalized permutohedra as all of them are in the family Poly(Br d ). Therefore, if we can find d 2 "independent" generalized permutohedra for which we know their linear Ehrhart coefficients, then we can set up a d 2 × d α-values arising from edges of Π d . Solving the system, we obtain all these α-values. See [24,Example 3.15] for an example of how we can solve a linear system to find α's.
Recall that Postnikov gives explicit formulas for the Ehrhart polynomials of type-Y generalized permutohedra (see Theorem 3.1.4). Among all the non-trivial Ehrhart coefficients, the linear terms can be easily described. Using these, we were able to set up, for each d, a desired linear system which is actually triangular.
Solving the system for d ≤ 500, we confirmed positivity of all d 2 α's arising from edges of Π d .
Equivalence Statements. In addition to the partial results discussed above, two equivalent statements to Conjecture 3.3.2 were discovered. The first states that

Negative Results
In this section, we will discuss examples and constructions of polytopes with negative Ehrhart coefficients. We start in §4.1 with the well-known Reeve tetrahedra, a family of 3-dimensional polytopes with negative linear coefficients. Constructions given in §4.2 were motivated by a refinement of Question 1.2, considering all possible sign patterns of Ehrhart coefficients. Examples studied in §4.3 and §4.4 provide negative answers to Question 1.2 for different families of polytopes (such as smooth polytopes and order polytopes), which will be summarized in §4.5. Finally in §4.6, we give negative examples addressing the question of whether Minkowski summation preserves Ehrhart positivity.
As mentioned before, due to the fact that the first, second, and last Ehrhart coefficients are always positive, given a d-dimensional polytope P, we need to ask the positivity question only for the coefficients of t d−2 , t d−3 , . . . , t 1 in i(P, t). We call these coefficients the middle Ehrhart coefficients of P.
One sees that the linear coefficient is 0 when m = 12 and is negative when m ≥ 13.

4.2.
Possible sign patterns. Motivated by the example of Reeve tetrahedra, Hibi, Higashitani, Tsuchiya and Yoshida study possible sign patterns of middle Ehrhart coefficients, and ask the following question: Question 4.2.1 (Question 3.1 of [48]). Given a positive integer d ≥ 3 and integers 1 ≤ i 1 < · · · < i q ≤ d − 2, does there exist a d-dimensional integral polytope P such that the coefficients of t i1 , . . . , t iq of i(P, t) are negative, and the remaining coefficients are positive?
The following is the main result in [48] providing a partial answer to Question 4.2.1. The proof of both parts of the theorem is by construction. We will briefly discuss the construction for Theorem 4.2.2/(a), and refer interested readers to the original paper [48] for the other construction.
Sketch of proof for Theorem 4.2.2/ (a). Let L n := [0, n], which is a 1-dimensional polytope and its Ehrhart polynomial is i(L n , t) = nt + 1. Define the polytope P (d) m be the direct product of (d−3) copies of L d−3 and one copy of the Reeve tetrahedron The coefficients of the Ehrhart polynomial of P   Figure 4 for an example.) Using inclusion-exclusion and the fact that the BV-α-values of cubes and standard simplices can be obtained easily due to property (P3), we obtain explicit formulas for all BV-α-values arising from P d (a, b), which we use to search for negative BV-α-values. The first negative values appear at d = 7, suggesting that we might have a negative Ehrhart coefficient in Q 7 (a, b). By direct computation, we are able to show that for some choices of (a, b), e.g., (5,2), the polytope Q d (a, b) has a negative linear Ehrhart coefficient for any d ≥ 7. Therefore, we have the following result [27, Proposition 1.3]:   Q d (a, b) is not only a smooth polytope, but also a "type-B generalized permutohedron". The generalized permutohedra considered in Section 3 are of type A as the corresponding normal fan, Br d , is constructed from the type A root system. As a consequence, a polytope P is a (type-A) generalized permutohedron if and only if each edge direction of P is of the form of e i − e j for some i = j. Similarly, we can define a polytope P in R d is a type-B generalized permutohedron if each edge direction of P is in the form of e i ± e j for some i = j or of the form ±e i for some i. It is then straightforward to verify that Q d (a, b) is a type-B generalized permutohedron.
Using the idea of iterated chiseling cubes, we then improve the dimension range of our counterexamples from d ≥ 7 to d ≥ 3. (See [27, Section 2] for details.) Note that the above theorem is a stronger version than part (a) of Theorem 4.2.2. Even though the original purpose of the paper [27] was to answer Bruns' question, in the process of searching for a counterexample, we obtained a separate result answering a different question. For positive integers a > b, we let P d (a, b) be the polytope obtained by chiseling one vertex off a d at distance b. It is clear that P d (a, b) share the same BV-α-values with Q d (a, b). Hence, it has negative BV-αvalues at d ≥ 7. However, it turns out any d-dimensional integral polytope P that has the same normal fan as P d (a, b) is Ehrhart positive [27,Lemma 3.9]. Therefore, BV-α-positivity is strictly stronger than Ehrhart-positivity.
Finally, we studied a weaker version of Brun's question by requiring the smooth polytopes to be reflexive. More precisely, we asked whether all smooth reflexive polytopes have positive Ehrhart coefficients. Unfortunately, the answer to this question is still negative.
In fixed dimension d, there are only finitely many reflexive polytopes up to unimodular transformations. Because of their correspondence to toric Fano manifolds, smooth reflexive polytopes were completely classified up to dimension 9 [76,62]. We used polymake [2] to verify that up to dimension 8 all of them are Ehrhart positive, but in dimension 9 the following counterexample came up [27]: One can compute that Hence, the linear Ehrhart coefficient of O(Q k ) is negative when k = 20.
Based on Stanley's example, the author and Tsuchiya studied the Ehrhart positivity question on polytopes O(Q k ) for any k, and gave a complete description of which Ehrhart coefficients of O(Q k ) are negative [61]. The following theorem is an immediate consequence to this description. Stanley's example and its extension are very interesting as O(Q k ) belongs to a lot of different families of polytopes. First of all, it is an order polytope, and thus is a (0, 1)-polytope.
Recall that a Gorenstein polytope of codegree s is an integral polytope such that sP is reflexive. It follows from a result by Hibi [42] that an order polytope is Gorenstein if and only if the underlying poset is pure, i.e., all maximal chains have the same length. Clearly, Q k is pure. Thus, O(Q k ) is a Gorenstein polytope.
Finally, Mészáros, Morales and Striker proved a result observed by Postnikov establishing a connection between flow polytopes of planar graphs and order polytopes [72,Theorem 3.8]. Using this connection, Morales (private communication) observes that the order polytope O(Q k ) is unimodularly equivalent to the flow polytope F G (1, 0, . . . , 0, −1), where G is the black graph on k + 1 vertices in Figure  5. (Note the red part of the figure is Q k .)   (1,19,19,20).
Notice that the polytopes given in Example 4.6.1 satisfy dim(P ) + dim(Q) = dim(P + Q), and those in Example 4.6.2 satisfy dim(P ) = dim(Q) = dim(P + Q). These are the two extreme situations in terms of dimensions. Therefore, even with some restrictions on the dimensions of P , Q and P + Q, the answer to the question above is false. Note that if r = 1, we obtain a polytope that is unimodularly equivalent to the standard d-simplex. The family of base-r d-simplices are introduced by Solus in his study of simplices for numeral systems [91], in which he shows that the h *polynomial of B (r,d) is real-rooted and thus is unimodal. Based on computational evidence, Solus makes the following conjecture [91, Section 5]:

Further discussion
Conjecture 5.1.1 (Solus). The base-r d-simplex is Ehrhart positive.
We remark that this family of ∆ (1,q) is very different from the ones constructed by Payne discussed in Example 2.2.5. If r > 1, the base-r simplex B (r,d) always contains the origin as an interior point, and it follows from (1.2) that the degree of h * -polynomial of B (r,d) is d. Since B (r,d) is not reflexive, by Corollary 2.2.9 the roots of its h * -polynomial are not all on the unit circle in the complex plane. Therefore, the techniques used to prove Ehrhart positivity for Payne's construction would not work here. 5.1.2. Birkhoff polytopes. The Birkhoff polytope B n is the convex polytope of n × n doubly-stochastic matrices; that is, the set of real nonnegative matrices with all row and column sums equal to one. Equivalently, B n can also be defined as the convex hull of all n × n permutation matrices. (See [106, Chapters 5 and 6] for a detailed introduction to B n .) There has been a lot of research on computing the volumes and Ehrhart polynomials of Birkhoff polytopes [9,21,32,77] By checking the available data [9], the first nine i(B n , t) have the property that all the roots have negative real parts. More importantly, Figure 6 in [8] suggests that the roots of i(B n , t) form a certain pattern. Hence, it could be promising to use Lemma 2.2.1 to attack this conjecture.
We also remark that B n is a Gorenstein polytope (up to lattice translation) of codegree n. However, with aforementioned data, one can see that B n is not h *unit-circle-rooted. Hence, we cannot apply Theorem 2.2.2 to show that all roots of i(B n , t) have negative real parts. (m k,k + m k,k+1 + · · · + m k,n ) − (m 1,k + m 2,k + · · · + m k−1,k ).
For each a = (a 1 , . . . , a n ) ∈ N n , Mészáros, Morales, and Rhoades [71] define the Tesler polytope, denoted by Tes n (a), to be the set of all n × n upper triangular matrices M with nonnegative entries and of hook sum a, i.e., the k th hook sum of M is a k . The lattice points in Tes n (a) are exactly Tesler matrices of hook sum a. When a = (1, 1, . . . , 1), these are important objects in Haglund's work on diagonal harmonics [40]. Therefore, we call Tes n (1, 1, . . . , 1) the Tesler matrix polytope as Tesler matrices of hook sum (1, 1, . . . , 1) were the original Tesler matrices defined by Haglund.
Another interesting example of a Tesler polytope is Tes n (1, 0, . . . , 0), which turns out to be the Chan-Robbins-Yuen polytope or CRY polytope, a face of the Birkhoff polytope. The CRY polytope, denote by CRY n , is the convex hull of all the n × n permutation matrices M = (m i,j ) such that m i,j = 0 if i ≥ j + 2, i.e., all entries below the sub-diagonal are zeros. It was initially introduced by Chan, Robbins and Yuen in [28], in which they made an intriguing conjecture on a formula for the volume of CRY n as a product of Catalan numbers. It was since proved by Zeilberger [107], Baldoni-Vergne [4], and Mészáros [68,69].
Using the Maple code provided by Baldoni, Beck, Cochet and Vergne [3], Morales computed the Ehrhart polynomials of both CRY polytopes and Tesler matrix polytopes for small n, and made the following conjecture [73].  We call the coefficients c ν λ,µ in the above expression the Littlewood-Richardson coefficients or LR coefficients. There are many different ways of computing c ν λ,µ . For example, it counts the number of semistandard Young tableaux T of shape ν/λ with content µ such that the reading word of T satisfies the "Yamanouchi word condition" [65]. One immediate consequence of these descriptions is that the LR coefficients are nonnegative integers. In this article, we use the hive model [20,53,54] to describe the LR coefficients.
A hive of size n is a triangular array of numbers a i,j with 0 ≤ i, j, i + j ≤ n arranged on a triangular grid consisting of n 2 small equilateral triangles. See the left side of Figure 6 for how a hive of size 4 should look like. For any adjacent triangles {a, b, c} and {b, c, d} in the hive, they form a rhombus {a, b, c, d}. The hive condition for this rhombus is (HC) b + c ≥ a + d.
With this definition, the LR-coefficient c ν λ,µ counts the number of LR-hives of type (ν, λ, µ). (Note that this is independent from n as long as l(ν), l(λ), l(µ) ≤ n.) For example, if ν = (4, 3, 1), λ = (3, 2) and µ = (2, 1), then the border of a corresponding LR-hive of size 4 is shown on the right side of Figure 6. In fact, the hive condition will force a 2,1 = 8 and a 1,2 = 7. So it will be reduced to a hive of size 3. Finally, it follows from the hive condition that 6 ≤ a 1,1 ≤ 7. Thus, we have two LR-hives of this type, and we conclude that c (4,3,1) (3,2),(2,1) = 2. From the above description, it is not hard to see that c ν λ,µ counts the number of lattice points inside a polytope P ν λ,µ determined by the border condition and the hive condition. Furthermore, for any positive integer t, the LR-coefficient c tν tλ,tµ counts the number of lattice points inside the t th dilation of P ν λ,µ : c tν tλ,tµ = |tP ν λ,µ ∩ Z D |. King, Tollu and Toumazet studied c tν tλ,tµ , which they call the stretched Littlewood-Richardson coefficients, and made the following conjecture [ One notices that if P ν λ,µ is an integral polytope, then the polynomiality part of the above conjecture follows from Ehrhart's theorem. However, in general, P ν λ,µ is a rational polytope, which only implies that c tν tλ,tµ is a quasi-polynomial with some period. Nevertheless, the assertion of polynomiality in the above conjecture was established first by Derksen and Weyman [33] using semi-invariants of quivers, and then by Rassart [86] using Steinberg's formula [104] and hyperplane arrangements. Hence, the polynomial asserted in Conjecture 5.1.4 can be considered to be an Ehrhart polynomial, and positivity assertion in the conjecture (which is still open) is exactly an Ehrhart-positivity question.

Other questions. Many questions related to Ehrhart positivity remain open.
We include a few below. 5.2.1. Modified Bruns question. As we have discussed in §4.3, the answer to Bruns' question of whether all smooth polytopes are Ehrhart positive is negative, where counterexamples are constructed for each dimension d ≥ 3. Furthermore, we verify, with the help of polymake [2], that all smooth reflexive polytopes of dimension up to 8 are Ehrhart positive, and that there exists a non-Ehrhart-positive smooth reflexive polytopes of dimension 9. However, we did not investigate smooth reflexive polytopes of higher dimensions. Therefore, one can ask: Bruns' question can be rephrased using the language of fans: For any smooth projective fan Σ, is it true that any polytope with normal fan Σ is Ehrhart positive. Since the answer is false, a weaker version of this question can be asked: Question 5.2.2. Is it true that for any smooth projective fan Σ, there exists one integral polytope P with normal fan Σ that is Ehrhart positive? 5.2.2. h * -vector for 3-dimensional polytopes. Here instead of studying Ehrhart positivity question for families of polytopes in which dimensions vary, we focus on polytopes with a fixed dimension, and ask the following question: Since integral polytopes of dimension at most 2 are always Ehrhart positive, dimension 3 is a natural starting point.
We have mentioned in the introduction that various inequalities for h * -vectors have been found. So we may use Formula (1.1) which gives a connection between the h * -vector and Ehrhart coefficients together with known inequalities to study Question 5.2.3. Note that in dimension 3, only the linear Ehrhart coefficient could be negative. Applying (1.1), we obtain that P is Ehrhart positive (equivalently the linear Ehrhart coefficient of P is positive) if and only if the h * -vector (h * 0 , h * 1 , h * 2 , h * 3 ) of P satisfies (5.1) 11h * 0 + 2h * 1 − h * 2 + 2h * 3 > 0. In [6], Balletti and Kasprzyk give classifications for 3-dimensional polytopes with 1 or 2 interior lattice points, using which they extract all possible h * -vectors. Assume the number of interior lattice points is fixed to be 1 or 2. Applying (1.2), we obtain h * 0 = 1 and h * 3 = 1 or 2. Hence, only h * 1 and h * 2 change. Balletti and Kasprzyk then plot all occurring pairs of (h * 1 , h * 2 ) in [6, Figure 5]. The black part of Figure 7 is their figure, which we modify to include a red line representing the inequality (5.1), where points below the red line arise from polytopes with the Ehrhart positivity property. Note that in each part of the figure, the big triangular area is bounded by three known inequalities for h * -vectors. It is clear from the figure that these inequalities are far from optimal. Comparing the red line with the plotted data, one sees that a very high percentage of data points correspond to Ehrhart positive polytopes. However, if we only look at the triangular region (without the data points), then the area below the red line has a much lower percentage of the region. Therefore, improving the inequality bounds for h * -vectors will be helpful in understanding the Ehrhart positivity problem, in particular, in giving a more accurate answer to Question 5.2.3.  . The plot of (h * 1 , h * 2 ) of 3-dimensional polytopes with 1 or 2 interior lattice points.