Ehrhart positivity for generalized permutohedra

Fu LiuEhrhart positivity for
generalized permutohedra
Fu LiuUniversity of California, Davis

Workshop on Computational Commutative Algebra and Convex Polytopes
RIMS, Kyoto, Japan
August 2, 2016

This is joint work with Federico Castillo.

Page 1

Ehrhart positivity for generalized permutohedra

Fu LiuOutline• Introduction– Polytopes and Ehrhart positivity– Generalized permutohedra and first conjecture• McMullen’s formula and consequences– McMullen’s formula– Reduction theorem and second conjecture– Partial results to the conjectures• The BV-construction and idea of proofs• Other questions and results

Page 2

Ehrhart positivity for generalized permutohedra

Fu LiuPART I:

Introduction

Page 3

Ehrhart positivity for generalized permutohedra

Fu LiuLattice points of a polytope
A (convex) polytope is a bounded solution set of a finite system of linear inequalities,
or is the convex hull of a finite set of points.

Page 4

Ehrhart positivity for generalized permutohedra

Fu LiuLattice points of a polytope
A (convex) polytope is a bounded solution set of a finite system of linear inequalities,
or is the convex hull of a finite set of points.
An integral polytope is a polytope whose vertices are all lattice points. i.e., points
with integer coordinates.

Page 4

Ehrhart positivity for generalized permutohedra

Fu LiuLattice points of a polytope
A (convex) polytope is a bounded solution set of a finite system of linear inequalities,
or is the convex hull of a finite set of points.
An integral polytope is a polytope whose vertices are all lattice points. i.e., points
with integer coordinates.
Definition. For any polytope P ⊂ Rd and positive integer t ∈ N, the tth dilation of P
is tP = {tx : x ∈ P }. We definei(P, t) = |tP ∩ Zd |to be the number of lattice points in the tP.

Page 4

Ehrhart positivity for generalized permutohedra

Fu LiuLattice points of a polytope
A (convex) polytope is a bounded solution set of a finite system of linear inequalities,
or is the convex hull of a finite set of points.
An integral polytope is a polytope whose vertices are all lattice points. i.e., points
with integer coordinates.
Definition. For any polytope P ⊂ Rd and positive integer t ∈ N, the tth dilation of P
is tP = {tx : x ∈ P }. We definei(P, t) = |tP ∩ Zd |to be the number of lattice points in the tP.
Example: For any d, let P = {x ∈ Rd

: 0 ≤ xi ≤ 1, ∀i} be the unit cube in Rd .
Then tP = {x ∈ Rd : 0 ≤ xi ≤ t, ∀i} and i(P, t) = (t + 1)d .

P

3PPage 4

Ehrhart positivity for generalized permutohedra

Fu LiuTheorem of Ehrhart (on integral polytopes)
Theorem 1 (Ehrhart). Let P be a d-dimensional integral polytope. Then i(P, t) is apolynomial in t of degree d.
Therefore, we call i(P, t) the Ehrhart polynomial of P.

Page 5

Ehrhart positivity for generalized permutohedra

Fu LiuCoefficients of Ehrhart polynomials
If P is an integral polytope, what can we say about the coefficients of its Ehrhart
polynomial i(P, t)?

Page 6

Ehrhart positivity for generalized permutohedra

Fu LiuCoefficients of Ehrhart polynomials
If P is an integral polytope, what can we say about the coefficients of its Ehrhart
polynomial i(P, t)?

➠ The leading coefficient of i(P, t) is the volume vol(P ) of P.

Page 6

Ehrhart positivity for generalized permutohedra

Fu LiuCoefficients of Ehrhart polynomials
If P is an integral polytope, what can we say about the coefficients of its Ehrhart
polynomial i(P, t)?

➠ The leading coefficient of i(P, t) is the volume vol(P ) of P.
➠ The second coefficient equals 1/2 of the sum of the normalized volumes of eachfacet.

Page 6

Ehrhart positivity for generalized permutohedra

Fu LiuCoefficients of Ehrhart polynomials
If P is an integral polytope, what can we say about the coefficients of its Ehrhart
polynomial i(P, t)?

➠ The leading coefficient of i(P, t) is the volume vol(P ) of P.
➠ The second coefficient equals 1/2 of the sum of the normalized volumes of eachfacet.

➠ The constant term of i(P, t) is always 1.

Page 6

Ehrhart positivity for generalized permutohedra

Fu LiuCoefficients of Ehrhart polynomials
If P is an integral polytope, what can we say about the coefficients of its Ehrhart
polynomial i(P, t)?

➠ The leading coefficient of i(P, t) is the volume vol(P ) of P.
➠ The second coefficient equals 1/2 of the sum of the normalized volumes of eachfacet.

➠ The constant term of i(P, t) is always 1.
➠ No simple forms known for other coefficients for general polytopes.

Page 6

Ehrhart positivity for generalized permutohedra

Fu LiuCoefficients of Ehrhart polynomials
If P is an integral polytope, what can we say about the coefficients of its Ehrhart
polynomial i(P, t)?

➠ The leading coefficient of i(P, t) is the volume vol(P ) of P.
➠ The second coefficient equals 1/2 of the sum of the normalized volumes of eachfacet.

➠ The constant term of i(P, t) is always 1.
➠ No simple forms known for other coefficients for general polytopes.
• It is NOT even true that all the coefficients are positive. For example, for thepolytope P with vertices (0, 0, 0), (1, 0, 0), (0, 1, 0) and (1, 1, 13), its Ehrhart
polynomial is

13 3
2 1
i(P, t) = t + t − t + 1.
6
6

Page 6

Ehrhart positivity for generalized permutohedra

Fu LiuEhrhart positivity
Definition. We say an integral polytope is Ehrhart positive if it has positive coefficientsin its Ehrhart polynomial.

Page 7

Ehrhart positivity for generalized permutohedra

Fu LiuEhrhart positivity
Definition. We say an integral polytope is Ehrhart positive if it has positive coefficientsin its Ehrhart polynomial.
Families of integral polytopes that are known to be Ehrhart positive.

• Standard simplices.
• Zonotopes.
• Stanley-Pitman polytopes.
• Cyclic polytopes.

Page 7

Ehrhart positivity for generalized permutohedra

Fu LiuEhrhart positivity
Definition. We say an integral polytope is Ehrhart positive if it has positive coefficientsin its Ehrhart polynomial.
Families of integral polytopes that are known to be Ehrhart positive.

• Standard simplices.
• Zonotopes.
• Stanley-Pitman polytopes.
• Cyclic polytopes.
Conjecture 2 (DeLoera-Haws-Koeppe). All matroid polytopes are Ehrhart positive.

Page 7

Ehrhart positivity for generalized permutohedra

Fu LiuEhrhart positivity
Definition. We say an integral polytope is Ehrhart positive if it has positive coefficientsin its Ehrhart polynomial.
Families of integral polytopes that are known to be Ehrhart positive.

• Standard simplices.
• Zonotopes.
• Stanley-Pitman polytopes.
• Cyclic polytopes.
Conjecture 2 (DeLoera-Haws-Koeppe). All matroid polytopes are Ehrhart positive.
We consider generalized permutohedra, a family of polytopes that include both StanleyPitman polytopes and matroid polytopes.
Conjecture 3 (Castillo-L.). All integral generalized permutohera are Ehrhart positive.

Page 7

Ehrhart positivity for generalized permutohedra

Fu LiuUsual permutohedra
Definition. Suppose v = (v1 , v2 , · · · , vn ) is a (nondecreasing) sequence. We define
the usual permutohedronPerm (v) := conv vσ(1) , vσ(2) , · · · , vσ(n) : σ ∈ Sn .
• If v = (1, 2, · · · , n), we get the regular permutohedron Πn−1 .
Example. Π2 :Any usual permutohedron in Rn is (n − 1)-dimensional.
Page 8

Ehrhart positivity for generalized permutohedra

Fu LiuGeneralized permutohedra
Definition (Postnikov). A generalized permutohedron is a polytope obtained from ausual permutohedron by moving the facets while keeping the normal directions.

Page 9

Ehrhart positivity for generalized permutohedra

Fu LiuGeneralized permutohedra
Definition (Postnikov). A generalized permutohedron is a polytope obtained from ausual permutohedron by moving the facets while keeping the normal directions.
For n = 3, we get 2-dimensional polytopes.

Page 9

Ehrhart positivity for generalized permutohedra

Fu LiuGeneralized permutohedra
Definition (Postnikov). A generalized permutohedron is a polytope obtained from ausual permutohedron by moving the facets while keeping the normal directions.
For n = 3, we get 2-dimensional polytopes.

regular permutohedron

usual permutohedra

generalized
permutohedra

Page 9

Ehrhart positivity for generalized permutohedra

Fu LiuGeneralized permutohedra
Definition (Postnikov). A generalized permutohedron is a polytope obtained from ausual permutohedron by moving the facets while keeping the normal directions.
For n = 3, we get 2-dimensional polytopes.

regular permutohedron

usual permutohedra

generalized
permutohedra

Page 9

Ehrhart positivity for generalized permutohedra

Fu LiuGeneralized permutohedra
Definition (Postnikov). A generalized permutohedron is a polytope obtained from ausual permutohedron by moving the facets while keeping the normal directions.
For n = 3, we get 2-dimensional polytopes.

regular permutohedron

usual permutohedra

generalized
permutohedra

Page 9

Ehrhart positivity for generalized permutohedra

Fu LiuGeneralized permutohedra
Definition (Postnikov). A generalized permutohedron is a polytope obtained from ausual permutohedron by moving the facets while keeping the normal directions.
For n = 3, we get 2-dimensional polytopes.

regular permutohedron

usual permutohedra

generalized
permutohedra

Page 9

Ehrhart positivity for generalized permutohedra

Fu LiuAlternative definition
Let V be the subspace of Rn defined by x1 + x2 + · · · + xn = 0. The braidarrangement fan denoted by Bn , is the complete fan in V given by the hyperplanesxi − xj = 0 for all i 6= j .

Page 10

Ehrhart positivity for generalized permutohedra

Fu LiuAlternative definition
Let V be the subspace of Rn defined by x1 + x2 + · · · + xn = 0. The braidarrangement fan denoted by Bn , is the complete fan in V given by the hyperplanesxi − xj = 0 for all i 6= j .
Proposition 4 (Postnikov-Reiner-Williams). A polytope P ∈ Rn is a generalized permutoheron if and only if its normal fan is refined by the braid arrangement fan Bn .

Page 10

Ehrhart positivity for generalized permutohedra

Fu LiuAlternative definition
Let V be the subspace of Rn defined by x1 + x2 + · · · + xn = 0. The braidarrangement fan denoted by Bn , is the complete fan in V given by the hyperplanesxi − xj = 0 for all i 6= j .
Proposition 4 (Postnikov-Reiner-Williams). A polytope P ∈ Rn is a generalized permutoheron if and only if its normal fan is refined by the braid arrangement fan Bn .

regular permutohedron

usual permutohedra

generalized
permutohedra

Page 10

Ehrhart positivity for generalized permutohedra

Fu LiuWhat is known about Ehrhart positivity?

Page 11

Ehrhart positivity for generalized permutohedra

Fu LiuWhat is known about Ehrhart positivity?

Postnikov studied the y -family , a subset of generalized permutohedra defined by

P =
y

X

yS ∆S

S⊆[n]

where

∆S = conv(ei : i ∈ S)
and the yS all nonnegative.
He gave an explicit formula for the Ehrhart polynomial of any polytope in this family.
As a consequence of his formula, any polytope in the y -family is Ehrhart positive.

Page 11

Ehrhart positivity for generalized permutohedra

Fu LiuWhat is known about Ehrhart positivity?

Postnikov studied the y -family , a subset of generalized permutohedra defined by

P =
y

X

yS ∆S

S⊆[n]

where

∆S = conv(ei : i ∈ S)
and the yS all nonnegative.
He gave an explicit formula for the Ehrhart polynomial of any polytope in this family.
As a consequence of his formula, any polytope in the y -family is Ehrhart positive.
The y -family includes: regular permutohedra, associahedra, cyclohedra, StanleyPitman polytopes, and more.

Page 11

Ehrhart positivity for generalized permutohedra

Fu LiuWhat is known about Ehrhart positivity?

Postnikov studied the y -family , a subset of generalized permutohedra defined by

P =
y

X

yS ∆S

S⊆[n]

where

∆S = conv(ei : i ∈ S)
and the yS all nonnegative.
He gave an explicit formula for the Ehrhart polynomial of any polytope in this family.
As a consequence of his formula, any polytope in the y -family is Ehrhart positive.
The y -family includes: regular permutohedra, associahedra, cyclohedra, StanleyPitman polytopes, and more.
Unfortunately, it fails to contain the matroid polytopes.

Page 11

Ehrhart positivity for generalized permutohedra

Fu LiuPART II:

McMullen’s formula and consequences

Page 12Ehrhart positivity for generalized permutohedra

Fu LiuMcMullen’s formula
Definition. Suppose F is a face of P. The feasible cone of P at F , denoted byfcone(F, P ), is the cone of all feasible directions of P at F .
p

The pointed feasible cone of P at F is fcone (F, P ) = fcone(F, P )/L, where L
pis the subspace spanned by F. In general, fcone (F, P ) is k -dim pointed cone where
if F is codimensional k .

Page 13

Ehrhart positivity for generalized permutohedra

Fu LiuMcMullen’s formula
Definition. Suppose F is a face of P. The feasible cone of P at F , denoted byfcone(F, P ), is the cone of all feasible directions of P at F .
p

The pointed feasible cone of P at F is fcone (F, P ) = fcone(F, P )/L, where L
pis the subspace spanned by F. In general, fcone (F, P ) is k -dim pointed cone where
if F is codimensional k .
In 1975 Danilov asked if it is possible to assign values Ψ(C) to all rational cones C
such that the following McMullen’s formula holdsd|P ∩ Z | =X

α(F, P ) vol(F ).

F : a face of Ppwhere α(F, P ) := Ψ(fcone (F, P )).

Page 13

Ehrhart positivity for generalized permutohedra

Fu LiuMcMullen’s formula
Definition. Suppose F is a face of P. The feasible cone of P at F , denoted byfcone(F, P ), is the cone of all feasible directions of P at F .
p

The pointed feasible cone of P at F is fcone (F, P ) = fcone(F, P )/L, where L
pis the subspace spanned by F. In general, fcone (F, P ) is k -dim pointed cone where
if F is codimensional k .
In 1975 Danilov asked if it is possible to assign values Ψ(C) to all rational cones C
such that the following McMullen’s formula holdsd|P ∩ Z | =pX

α(F, P ) vol(F ).

F : a face of P

where α(F, P ) := Ψ(fcone (F, P )).

• McMullen proved it was possible in a non constructive way.
• Subsequently, explicit constructions of Ψ/α(F, P ) were given by Morelli, PommersheimThomas, and Berline-Vergne.
We will use Berline-Vergne’s construction, which we will refer to as the BV-construction.

Page 13

Ehrhart positivity for generalized permutohedra

Fu LiuAn expression for Ehrhart coefficients
Given an integral polytope P ⊆ Rd , any dilation tP of P is integral as well. We
havedi(P, t) = |tP ∩ Z | =X

α(tF, tP ) vol(tF )X

α(F, P ) vol(F )tdim(F )F : a face of P=

F : a face of P

Page 14

Ehrhart positivity for generalized permutohedra

Fu LiuAn expression for Ehrhart coefficients
Given an integral polytope P ⊆ Rd , any dilation tP of P is integral as well. We
havedi(P, t) = |tP ∩ Z | =X

α(tF, tP ) vol(tF )X

α(F, P ) vol(F )tdim(F )F : a face of P=

F : a face of P

Hence, the coefficient of tk in i(P, t) is given byX

α(F, P ) vol(F ).

F : a k -dimensional face of P

Page 14

Ehrhart positivity for generalized permutohedra

Fu LiuAn expression for Ehrhart coefficients
Given an integral polytope P ⊆ Rd , any dilation tP of P is integral as well. We
havedi(P, t) = |tP ∩ Z | =X

α(tF, tP ) vol(tF )X

α(F, P ) vol(F )tdim(F )F : a face of P=

F : a face of P

Hence, the coefficient of tk in i(P, t) is given byX

α(F, P ) vol(F ).

F : a k -dimensional face of P

Hence, the coefficient of tk is positive if α(F, P ) is positive for any k -dimensional
face F of P.
Moreover, as long as all α for P are positive, P is Ehrhart positive.

Page 14

Ehrhart positivity for generalized permutohedra

Fu LiuReduction Theorem
For the rest of this part, we assume that α is the BV-construction.
Theorem 5 (Castillo-L.). Suppose α(F, Πn−1 ) > 0 for any k -dimensional face F of
the regular permutohedron Πn−1 . Then α(G, Q) > 0 for any k -dimensional face Gof any generalized permutohedron Q in Rn .

Page 15

Ehrhart positivity for generalized permutohedra

Fu LiuReduction Theorem
For the rest of this part, we assume that α is the BV-construction.
Theorem 5 (Castillo-L.). Suppose α(F, Πn−1 ) > 0 for any k -dimensional face F of
the regular permutohedron Πn−1 . Then α(G, Q) > 0 for any k -dimensional face Gof any generalized permutohedron Q in Rn .

regular permutohedron

usual permutohedra

generalized
permutohedra

Page 15

Ehrhart positivity for generalized permutohedra

Fu LiuReduction Theorem
For the rest of this part, we assume that α is the BV-construction.
Theorem 5 (Castillo-L.). Suppose α(F, Πn−1 ) > 0 for any k -dimensional face F of
the regular permutohedron Πn−1 . Then α(G, Q) > 0 for any k -dimensional face Gof any generalized permutohedron Q in Rn .

regular permutohedron1
6

usual permutohedra

1
6
1
6

1
6
1
6

1
6

generalized
permutohedra

Page 15

Ehrhart positivity for generalized permutohedra

Fu LiuReduction Theorem
For the rest of this part, we assume that α is the BV-construction.
Theorem 5 (Castillo-L.). Suppose α(F, Πn−1 ) > 0 for any k -dimensional face F of
the regular permutohedron Πn−1 . Then α(G, Q) > 0 for any k -dimensional face Gof any generalized permutohedron Q in Rn .

usual permutohedra

regular permutohedron
1
6

1
6

1
6
1
6

1
6
1
6

1
6

1
6

1
6
1
6

1
6

1
6

1
6

generalized
permutohedra

1
6

1
6

1
6
1
6

1
6

Page 15

Ehrhart positivity for generalized permutohedra

Fu LiuReduction Theorem
For the rest of this part, we assume that α is the BV-construction.
Theorem 5 (Castillo-L.). Suppose α(F, Πn−1 ) > 0 for any k -dimensional face F of
the regular permutohedron Πn−1 . Then α(G, Q) > 0 for any k -dimensional face Gof any generalized permutohedron Q in Rn .

usual permutohedra

regular permutohedron
1
6

1
6

1
6
1
6

1
6
1
6

1
6

1
6

1
6

1
6

1
6

1
6

1
6

generalized
permutohedra

1
6

1
6

1
6
1
6

1
6
1
6

1
6

1
6
1
3

1
6

Page 15

Ehrhart positivity for generalized permutohedra

Fu LiuReduction Theorem
For the rest of this part, we assume that α is the BV-construction.
Theorem 5 (Castillo-L.). Suppose α(F, Πn−1 ) > 0 for any k -dimensional face F of
the regular permutohedron Πn−1 . Then α(G, Q) > 0 for any k -dimensional face Gof any generalized permutohedron Q in Rn .

usual permutohedra

regular permutohedron
1
6

1
6

1
6
1
6

1
6
1
6

1
6

1
6

1
6

1
6

1
6

1
6

1
6

generalized
permutohedra

1
6

1
6

1
6
1
6

1
6
1
6

1
6

1
6

1
6

1
6
1
3

1
6

1
3

1
3

Page 15

Ehrhart positivity for generalized permutohedra

Fu LiuReduction Theorem
For the rest of this part, we assume that α is the BV-construction.
Theorem 5 (Castillo-L.). Suppose α(F, Πn−1 ) > 0 for any k -dimensional face F of
the regular permutohedron Πn−1 . Then α(G, Q) > 0 for any k -dimensional face Gof any generalized permutohedron Q in Rn .

usual permutohedra

regular permutohedron
1
6

1
6

1
6
1
6

1
6
1
6

1
6

1
6

1
6

1
6

1
6

1
6

1
6

generalized
permutohedra

1
3

1
6

1
6

1
6
1
6

1
6
1
6

1
6

1
3

1
3

1
6

1
6

1
6
1
3

1
6

1
3

1
3

Page 15

Ehrhart positivity for generalized permutohedra

Fu LiuA stronger conjecture
Conjecture 6 (Castillo-L.). The α values (from the BV-construction) of the regular permutoheron Πn−1 are all positive.
This conjecture clearly implies our first conjecture by the reduction theorem.
Note. The “regular permutohedron Πn−1 ” can be replaced with “any generalized permutohedron whose normal fan is the braid arrangement fan Bn ”.
Thus we may state this conjecture as “the α values for Bn are all positive”.

Page 16

Ehrhart positivity for generalized permutohedra

Fu LiuA more general form of the reduction theorem
The reduction theorem does not only work for Πn−1 and generalized permutohedra.
Theorem 7 (Castillo-L.). Suppose Q is a deformation of P, or the normal fan of P is arefinement of the normal fan of Q. If α(F, P ) > 0 for any k -dimensional face F of P ,then α(G, Q) > 0 for any k -dimensional face G of Q.

Page 17

Ehrhart positivity for generalized permutohedra

Fu LiuWhat can we show?

Page 18

Ehrhart positivity for generalized permutohedra

Fu LiuWhat can we show?

Partial results to the second conjecture:

Page 18

Ehrhart positivity for generalized permutohedra

Fu LiuWhat can we show?

Partial results to the second conjecture:
Lemma (Castillo-L.). The α values for regular permutohedra of dimension ≤ 6 are all
positive.

Page 18

Ehrhart positivity for generalized permutohedra

Fu LiuWhat can we show?

Partial results to the second conjecture:
Lemma (Castillo-L.). The α values for regular permutohedra of dimension ≤ 6 are all
positive.
Lemma (Castillo-L.). α(F, Πn−1 ) > 0 for any face F of Πn−1 of codimension 2 or 3.

Page 18

Ehrhart positivity for generalized permutohedra

Fu LiuWhat can we show?

Partial results to the second conjecture:
Lemma (Castillo-L.). The α values for regular permutohedra of dimension ≤ 6 are all
positive.
Lemma (Castillo-L.). α(F, Πn−1 ) > 0 for any face F of Πn−1 of codimension 2 or 3.
Lemma (Castillo-L.). α(E, Πn−1 ) > 0 for any edge E of Πn−1 of dimension ≤ 100.

Page 18

Ehrhart positivity for generalized permutohedra

Fu LiuWhat can we show?

Partial results to the second conjecture:
Lemma (Castillo-L.). The α values for regular permutohedra of dimension ≤ 6 are all
positive.
Lemma (Castillo-L.). α(F, Πn−1 ) > 0 for any face F of Πn−1 of codimension 2 or 3.
Lemma (Castillo-L.). α(E, Πn−1 ) > 0 for any edge E of Πn−1 of dimension ≤ 100.
Applying the reduction theorem, we get:Corollary (Castillo-L.).

i. Any integral generalized permutohedron of dimension ≤ 6

is Ehrhart positive.
ii. The third and fourth coefficients in the Ehrhart polynomial of any integral generalized
permutohedron is positive.
iii. The linear coefficient in the Ehrhart polynomial of any integral generalized permutohedron of dimension ≤ 100 is positive.

Page 18

Ehrhart positivity for generalized permutohedra

Fu LiuPART III:The BV-construction and idea of proofs

Page 19

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-construction
In order to attack our conjectures, we want to compute α for cones arising from regular permutohedra Πn−1 , or equivalently compute Ψ arising from the braid arrangement
fan Bn .

Page 20

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-construction

In order to attack our conjectures, we want to compute α for cones arising from regular permutohedra Πn−1 , or equivalently compute Ψ arising from the braid arrangement
fan Bn .
Different constructions were given for Ψ/α. We use Berline-Vergne’s construction
for its nice properties.

Page 20

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-construction

In order to attack our conjectures, we want to compute α for cones arising from regular permutohedra Πn−1 , or equivalently compute Ψ arising from the braid arrangement
fan Bn .
Different constructions were given for Ψ/α. We use Berline-Vergne’s construction
for its nice properties.
In general, the computation of Ψ(C) is quite complicated. However, when the cone

C is unimodular, computations are greatly simplified.

Page 20

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-construction

In order to attack our conjectures, we want to compute α for cones arising from regular permutohedra Πn−1 , or equivalently compute Ψ arising from the braid arrangement
fan Bn .
Different constructions were given for Ψ/α. We use Berline-Vergne’s construction
for its nice properties.
In general, the computation of Ψ(C) is quite complicated. However, when the cone

C is unimodular, computations are greatly simplified.
Lemma 8. Let C be a one-dimensional (unimodular) cone. Then Ψ(C) = 1/2.

Page 20

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-Construction (cont’d)Page 21

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-Construction (cont’d)Lemma 9. If C = Cone(u1 , u2 ), where {u1 , u2 } is a basis for the lattice span(u1 , u2 )∩Zn , then11
Ψ(C) = +
4 12





hu1 , u2 i hu1 , u2 i+.
hu1 , u1 i hu2 , u2 iPage 21

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-Construction (cont’d)Lemma 9. If C = Cone(u1 , u2 ), where {u1 , u2 } is a basis for the lattice span(u1 , u2 )∩Zn , then11
Ψ(C) = +
4 12





hu1 , u2 i hu1 , u2 i+.
hu1 , u1 i hu2 , u2 i

Example. Consider the polygon P in R2 with vertices v1 = (0, 0), v2 = (2, 0), andv3 = (0, 1). Let Ci = fconep (vi , P ).
v3 = (0, 1)

v1 = (0, 0)

v2 = (2, 0)Page 21

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-Construction (cont’d)Lemma 9. If C = Cone(u1 , u2 ), where {u1 , u2 } is a basis for the lattice span(u1 , u2 )∩Zn , then11
Ψ(C) = +
4 12





hu1 , u2 i hu1 , u2 i+.
hu1 , u1 i hu2 , u2 i

Example. Consider the polygon P in R2 with vertices v1 = (0, 0), v2 = (2, 0), andv3 = (0, 1). Let Ci = fconep (vi , P ).
v3 = (0, 1)

v1 = (0, 0)

v2 = (2, 0)

C1 = Cone((1, 0), (0, 1)) is a unimodular cone. Thus,


1 0 0
1
1
+
= .
α(v1 , P ) = Ψ(C1 ) = +4 12 1 1
4

Page 21

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-Construction (cont’d)Lemma 9. If C = Cone(u1 , u2 ), where {u1 , u2 } is a basis for the lattice span(u1 , u2 )∩n

Z , then11
Ψ(C) = +
4 12





hu1 , u2 i hu1 , u2 i+.
hu1 , u1 i hu2 , u2 i

Example. Consider the polygon P in R2 with vertices v1 = (0, 0), v2 = (2, 0), andv3 = (0, 1). Let Ci = fconep (vi , P ).
v3 = (0, 1)

v1 = (0, 0)

v2 = (2, 0)

C1 = Cone((1, 0), (0, 1)) is a unimodular cone. Thus,


1 0 0
1
1
+
= .
α(v1 , P ) = Ψ(C1 ) = +4 12 1 1
4
C2 = Cone((−2, 1), (−1, 0)) is a unimodular cone. Thus,


1 2 2
9
1
+
= .
α(v2 , P ) = Ψ(C2 ) = +4 12 5 1
20
Page 21

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-Construction (cont’d)

C3 = Cone((0, −1), (2, −1)), which is not unimodular. So we cannot directly
apply the formula to compute Ψ(C3 ).

Page 22

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-Construction (cont’d)

C3 = Cone((0, −1), (2, −1)), which is not unimodular. So we cannot directly
apply the formula to compute Ψ(C3 ). In order to compute it, we first decompose C3 :

 
 

[C3 ] = Cone (0, −1), (1, −1) + Cone (1, −1), (2, −1) − Cone (1, −1) .
v3 = (0, 1)

v1 = (0, 0)(1,0)

v2 = (2, 0)Page 22

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-Construction (cont’d)

C3 = Cone((0, −1), (2, −1)), which is not unimodular. So we cannot directly
apply the formula to compute Ψ(C3 ). In order to compute it, we first decompose C3 :

 
 

[C3 ] = Cone (0, −1), (1, −1) + Cone (1, −1), (2, −1) − Cone (1, −1) .
v3 = (0, 1)

v1 = (0, 0)(1,0)

v2 = (2, 0)

We apply the formula to the two first cones in the above decomposition and get Ψvalues of 3/8 and 17/40. Since the last cone is one-dimensional, we get its Ψ value
to be 1/2.

Page 22

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-Construction (cont’d)

C3 = Cone((0, −1), (2, −1)), which is not unimodular. So we cannot directly
apply the formula to compute Ψ(C3 ). In order to compute it, we first decompose C3 :

 
 

[C3 ] = Cone (0, −1), (1, −1) + Cone (1, −1), (2, −1) − Cone (1, −1) .
v3 = (0, 1)

v1 = (0, 0)(1,0)

v2 = (2, 0)

We apply the formula to the two first cones in the above decomposition and get Ψvalues of 3/8 and 17/40. Since the last cone is one-dimensional, we get its Ψ value
to be 1/2. Finally, by Ψ is a valuation function, we get

3 17 13α(v3 , P ) = Ψ(C3 ) = +− = .
8 40 2 10

Page 22

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-Construction (cont’d)Lemma 10. If C

= Cone(u1 , u2 , u3 ) where u1 , u2 , u3 is a basis for the latticespan(u1 , u2 ) ∩ Zn , then
1 hu1 , u2 i hu1 , u2 i hu1 , u3 i hu1 , u3 i hu3 , u2i hu3 , u2 i
1
+
+
+
+
+
Ψ(C) = +.
8 24 hu1 , u1 i hu2 , u2 i hu1 , u1 i hu3 , u3 i hu2 , u2i hu3 , u3 iPage 23

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-Construction (cont’d)Lemma 10. If C

= Cone(u1 , u2 , u3 ) where u1 , u2 , u3 is a basis for the latticespan(u1 , u2 ) ∩ Zn , then
1 hu1 , u2 i hu1 , u2 i hu1 , u3 i hu1 , u3 i hu3 , u2i hu3 , u2 i
1
+
+
+
+
+
Ψ(C) = +.
8 24 hu1 , u1 i hu2 , u2 i hu1 , u1 i hu3 , u3 i hu2 , u2i hu3 , u3 i
Remark 11. The formulas for 2-dim and 3-dim unimodular cones appear to be simple.
However, the apparent simplicity breaks down for dimension 4. The formula for 4-dim
unimodular cones include (way) more than 1000 terms.

Page 23

Ehrhart positivity for generalized permutohedra

Fu LiuComputing the BV-Construction (cont’d)Lemma 10. If C

= Cone(u1 , u2 , u3 ) where u1 , u2 , u3 is a basis for the latticespan(u1 , u2 ) ∩ Zn , then
1 hu1 , u2 i hu1 , u2 i hu1 , u3 i hu1 , u3 i hu3 , u2i hu3 , u2 i
1
+
+
+
+
+
Ψ(C) = +.
8 24 hu1 , u1 i hu2 , u2 i hu1 , u1 i hu3 , u3 i hu2 , u2i hu3 , u3 i
Remark 11. The formulas for 2-dim and 3-dim unimodular cones appear to be simple.
However, the apparent simplicity breaks down for dimension 4. The formula for 4-dim
unimodular cones include (way) more than 1000 terms.
Fact 12. Ψ is computed recursively. So lower dimensional cones are easier to compute.
pRecall that if F is a codimension k face of P , then fcone (F, P ) is k -dimensional.
Thus, α(F, P ) is easier to compute if F is a higher dimensional face.

Page 23

Ehrhart positivity for generalized permutohedra

Fu LiuProofs of lemmas
Lemma (Castillo-L.). The α values for regular permutohedra of dimension ≤ 6 are all
positive.
Proof. Directly compute all the α’s.

Page 24

Ehrhart positivity for generalized permutohedra

Fu LiuProofs of lemmas
Lemma (Castillo-L.). The α values for regular permutohedra of dimension ≤ 6 are all
positive.
Proof. Directly compute all the α’s.
Lemma (Castillo-L.). α(F, Πn−1 ) > 0 for any face F of Πn−1 of codimension 2 or 3.
Proof. We have precise formulas for Ψ of unimodular cones of dimension ≤ 3. Applying
these to regular permutohedra, we get α-positivity for faces of codimension ≤ 3.

Page 24

Ehrhart positivity for generalized permutohedra

Fu LiuProofs of lemmas
Lemma (Castillo-L.). The α values for regular permutohedra of dimension ≤ 6 are all
positive.
Proof. Directly compute all the α’s.
Lemma (Castillo-L.). α(F, Πn−1 ) > 0 for any face F of Πn−1 of codimension 2 or 3.
Proof. We have precise formulas for Ψ of unimodular cones of dimension ≤ 3. Applying
these to regular permutohedra, we get α-positivity for faces of codimension ≤ 3.
Lemma 13 (Castillo-L.). α(E, Πn−1 ) > 0 for any edge E of Πn−1 of dimension ≤100.
The approaches used above do not work. Since α(E, Πn−1 ) is Ψ of an (n − 2)dimensional cone, which is very hard to compute directly.

Page 24

Ehrhart positivity for generalized permutohedra

Fu LiuProofs of lemmas
Lemma (Castillo-L.). The α values for regular permutohedra of dimension ≤ 6 are all
positive.
Proof. Directly compute all the α’s.
Lemma (Castillo-L.). α(F, Πn−1 ) > 0 for any face F of Πn−1 of codimension 2 or 3.
Proof. We have precise formulas for Ψ of unimodular cones of dimension ≤ 3. Applying
these to regular permutohedra, we get α-positivity for faces of codimension ≤ 3.
Lemma 13 (Castillo-L.). α(E, Πn−1 ) > 0 for any edge E of Πn−1 of dimension ≤100.
The approaches used above do not work. Since α(E, Πn−1 ) is Ψ of an (n − 2)dimensional cone, which is very hard to compute directly.
Remark. The number “100” in the lemma can be pushed further.

Page 24

Ehrhart positivity for generalized permutohedra

Fu LiuThe symmetry property
Lemma. The valuation Ψ (from the BV-construction) is symmetric about the coordinates, i.e., for any cone C ∈ Rn and any signed permutation (σ, s) ∈ Sn × {±1}n ,we haveΨ(C) = Ψ((σ, s)(C)),
where (σ, s)(C) = {(s1 xσ(1) , s2 xσ(2) , . . . , sn xσ(n) ) : (x1 , . . . , xn ) ∈ C}.

Page 25

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13
Recall that the coefficient of tk in i(P, t) is given byX

α(F, P ) vol(F ).

F : a k -dimensional face of P

In particular, the coefficient of the linear term is given byX

α(E, P ) vol(E).

E: edge of P

Page 26

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13
Recall that the coefficient of tk in i(P, t) is given byX

α(F, P ) vol(F ).

F : a k -dimensional face of P

In particular, the coefficient of the linear term is given byX

α(E, P ) vol(E).

E: edge of P

General idea: Suppose you have a family of polytopes such that• they have same pointed feasible cones (for edges) up to signed permutations, andthus have the same α-values;• the Ehrhart polynomial of each polytope in the family is known (or at least the linear
Ehrhart coefficient is known).
Then as long as you have enough “independent” polytopes in your family, you can figureout the α-values.
Page 26

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13 (cont’d)Example. When n = 3 : Π2 = Perm((1, 2, 3)) = conv{σ : σ ∈ S3 }.
(2, 1, 3)(3, 1, 2)(3, 2, 1)(1, 2, 3)(1, 3, 2)(2, 3, 1)

The pointed feasible cones of the six edges of Π2 areCone((1, 1, −2)), Cone((2, −1, −1)), Cone((1, −2, 1)),Cone((−1, −1, 2)), Cone((−2, 1, 1)), Cone((−1, 2, −1)),

Page 27

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13 (cont’d)Example. When n = 3 : Π2 = Perm((1, 2, 3)) = conv{σ : σ ∈ S3 }.
(2, 1, 3)(3, 1, 2)(3, 2, 1)(1, 2, 3)(1, 3, 2)(2, 3, 1)

The pointed feasible cones of the six edges of Π2 areCone((1, 1, −2)), Cone((2, −1, −1)), Cone((1, −2, 1)),Cone((−1, −1, 2)), Cone((−2, 1, 1)), Cone((−1, 2, −1)),

By the symmetry property of Ψ, these cones all have the same value. Therefore, allα(E, Π2 ) are a single value, say α.

Page 27

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13 (cont’d)Example. When n = 3 : Π2 = Perm((1, 2, 3)) = conv{σ : σ ∈ S3 }.
(2, 1, 3)(1, 2, 3)(3, 1, 2)(3, 2, 1)

The pointed feasible cones of the six edges of Π2 are(1, 3, 2)Cone((1, 1, −2)), Cone((2, −1, −1)), Cone((1, −2, 1)),Cone((−1, −1, 2)), Cone((−2, 1, 1)), Cone((−1, 2, −1)),(2, 3, 1)

By the symmetry property of Ψ, these cones all have the same value. Therefore, allα(E, Π2 ) are a single value, say α.
The Ehrhart polynomial of Π2 is 3t2 + 3t + 1. Thus,

3=X

α(E, Π2 ) · vol(E) = 6α⇒

α = 1/2 > 0.

E

Page 27

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13 (cont’d)Example. When n = 4 : Π3 = Perm((1, 2, 3, 4)) = {σ : σ ∈ S4 }.

Page 28

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13 (cont’d)Example. When n = 4 : Π3 = Perm((1, 2, 3, 4)) = {σ : σ ∈ S4 }.

Π3 have 36 edges of two kinds.
24 short edges have the same αvalues, say α1 , and 12 long edges
have the same α-values, say α2 .

Page 28

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13 (cont’d)Example. When n = 4 : Π3 = Perm((1, 2, 3, 4)) = {σ : σ ∈ S4 }.

Π3 have 36 edges of two kinds.
24 short edges have the same αvalues, say α1 , and 12 long edges
have the same α-values, say α2 .

The Ehrhart polynomial of Π3 is 16t3 + 15t2 + 6t + 1. Thus,

6=X

α(E, Π3 ) · vol(E) = 24α1 + 12α2 .

EPage 28

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13 (cont’d)Example. When n = 4 : Π3 = Perm((1, 2, 3, 4)) = {σ : σ ∈ S4 }.

Π3 have 36 edges of two kinds.
24 short edges have the same αvalues, say α1 , and 12 long edges
have the same α-values, say α2 .

The Ehrhart polynomial of Π3 is 16t3 + 15t2 + 6t + 1. Thus,

6=X

α(E, Π3 ) · vol(E) = 24α1 + 12α2 .

E

Not enough equations!
Page 28

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13 (cont’d)
Consider the hypersimplex ∆2,4 = Perm((0, 0, 1, 1)). It has 12 edges whose corresponding pointed feasible cones are the same as that of the 12 long edges of Π3 . So
they all have α-values α2 .

Page 29

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13 (cont’d)
Consider the hypersimplex ∆2,4 = Perm((0, 0, 1, 1)). It has 12 edges whose corresponding pointed feasible cones are the same as that of the 12 long edges of Π3 . So
they all have α-values α2 .
The Ehrhart polynomial of ∆2,4 is2 3
7
t + 2t2 + t + 1. Thus,
3
3

7 X
=
α(E, ∆2,4 ) · vol(E) = 12α2 .
3EPage 29

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13 (cont’d)
Consider the hypersimplex ∆2,4 = Perm((0, 0, 1, 1)). It has 12 edges whose corresponding pointed feasible cones are the same as that of the 12 long edges of Π3 . So
they all have α-values α2 .
The Ehrhart polynomial of ∆2,4 is2 3
7
t + 2t2 + t + 1. Thus,
3
3

7 X
=
α(E, ∆2,4 ) · vol(E) = 12α2 .
3ETherefore, we solve the 2 × 2 linear system, and get

11
> 0,
α1 =
72

7
α2 =
> 0.
36

Page 29

Ehrhart positivity for generalized permutohedra

Fu LiuIdea of the proof of Lemma 13 (cont’d)
Consider the hypersimplex ∆2,4 = Perm((0, 0, 1, 1)). It has 12 edges whose corresponding pointed feasible cones are the same as that of the 12 long edges of Π3 . So
they all have α-values α2 .
The Ehrhart polynomial of ∆2,4 is

7
2 3
t + 2t2 + t + 1. Thus,
3
3

7 X
=
α(E, ∆2,4 ) · vol(E) = 12α2 .
3ETherefore, we solve the 2 × 2 linear system, and get

11
α1 =
> 0,
72

7
α2 =
> 0.
36

For arbitrary n: The linear Ehrhart coeffcient of some polytopes in the y -family can beeasily described. Using these, we were able to set up an explicit triangular linear systemfor {α(E, Πn−1 ) : E is an edge of Πn−1 } for any n.

Page 29

Ehrhart positivity for generalized permutohedra

Fu LiuPART IV:

Other questions and results

Page 30

Ehrhart positivity for generalized permutohedra

Fu LiuUniqueness of the construction of Ψ
The solution Ψ to McMullen’s formula is not unique since we know there are different
constructions.
Observation 14. When we prove Lemma 13, we did not really compute Berline-Vergne’s
construction. Instead, we just use the fact that their construction is symmetric about thecoordinates to set up linear system to solve.
E.g., in the case of Π3 we did in the last example, as long as we know a constructionΨ• satisfies McMullen’s formula, and• is symmetric about the coordinates,
we will set up exactly the same 2 × 2 linear system, and find exactly the same two

α-values.
So Ψ of the cones appeared in the example or the values of α(E, Π3 ) are unique.

Page 31

Ehrhart positivity for generalized permutohedra

Fu LiuUniqueness of the construction of Ψ
Question 15. Is it true that Ψ in McMullen’s formula is uniquely determined if we require
it to be symmetric about the coordinates?

Page 32

Ehrhart positivity for generalized permutohedra

Fu LiuUniqueness of the construction of Ψ
Question 15. Is it true that Ψ in McMullen’s formula is uniquely determined if we require
it to be symmetric about the coordinates?
If so, then the BV-construction is the only symmetric construction.

Page 32

Ehrhart positivity for generalized permutohedra

Fu LiuUniqueness of the construction of Ψ
Question 15. Is it true that Ψ in McMullen’s formula is uniquely determined if we require
it to be symmetric about the coordinates?
If so, then the BV-construction is the only symmetric construction.
Theorem 16 (Castillo-L.). Suppose Ψ is a solution to McMullen’s formula and is symmetric about the coordinates. Then the values of Ψ on cones arising from generalized
permutohedron are uniquely determined.

Page 32

Ehrhart positivity for generalized permutohedra

Fu LiuUniqueness of the construction of Ψ
Question 15. Is it true that Ψ in McMullen’s formula is uniquely determined if we require
it to be symmetric about the coordinates?
If so, then the BV-construction is the only symmetric construction.
Theorem 16 (Castillo-L.). Suppose Ψ is a solution to McMullen’s formula and is symmetric about the coordinates. Then the values of Ψ on cones arising from generalized
permutohedron are uniquely determined.
Idea of proof: Use mixed Ehrhart theory.

Page 32

Ehrhart positivity for generalized permutohedra

Fu LiuMixed Ehrhart Theorem
Consider the following Minkwoski sum:P = w1 P1 + w2 P2 + · · · + wk Pk ,where wi are variables and Pi are polytopes.
Mixed Ehrhart Theorem The number of integer points in P is a polynomial in wi ’s.
The coefficients are called mixed Ehrhart coefficients.

Page 33

Ehrhart positivity for generalized permutohedra

Fu LiuMixed Ehrhart Theorem
Consider the following Minkwoski sum:P = w1 P1 + w2 P2 + · · · + wk Pk ,where wi are variables and Pi are polytopes.
Mixed Ehrhart Theorem The number of integer points in P is a polynomial in wi ’s.
The coefficients are called mixed Ehrhart coefficients.
Postnikov showed that usual permutohedra are Minkowski sums of hypersimplices.

Perm(v) = w1 ∆1,n + w2 ∆2,n + · · · + wn−1 ∆n−1,n ,where

wi := vi+1 − vi for i = 1, 2, . . . , n − 1,and the hypersimplex ∆k,n is defined as∆k,n = Perm(0, · · · , 0, 1, · · · , 1).
| {z } | {z }n−kkPage 33

Ehrhart positivity for generalized permutohedra

Fu LiuA formula
Theorem 17 (Castillo-L.). Suppose Ψ is a solution to McMullen’s formula and is symmetric about the coordinates. Then the α values for the regular permutohedron Πn−1
(or the braid arrangement fan Bn ) are positive scalars of mixed Ehrhart coefficients ofhypersimplices.

Page 34

Ehrhart positivity for generalized permutohedra

Fu LiuConsequences
i. We obtain a proof for Theorem 16 (the theorem on uniqueness of Ψ).

Page 35

Ehrhart positivity for generalized permutohedra

Fu LiuConsequences

i. We obtain a proof for Theorem 16 (the theorem on uniqueness of Ψ).
ii. The following three statements are equivalent:(a) All α values of Πn−1 are positive. (The strong conjecture).
(b) All mixed Ehrhart coefficients of hypersimplices are positive.
(c) Let X be corresponding toric variety to the braid arrangement fan Bn . The Toddclass is positive with respect to the torus invariant cycles, that isTodd(X) =X

rσ [V (σ)],σ∈Bnfor some rσ > 0.

Page 35