8
$\begingroup$

The $n$-dimensional permutohedron $P_n$ is the polytope given by the convex hull of all the possible permutations of the vector $(1,2,\dots,n+1)\in\mathbb{R}^{n+1}$. So it has $(n+1)!$ vertexes.

I would like to ask if there is a formula for the the number of integer points of $P_n$ and whether it is known that $P_n$ is a very ample polytope for any $n\geq 1$.

For instance, $P_2$ is an hexagon in $\mathbb{R}^3$ contained in the plane $x_1+x_2+x_3 = 6$. It has $7$ integer points and it is very ample.

$\endgroup$
1
  • $\begingroup$ Do you agree with my edit? $\endgroup$ Dec 1, 2020 at 18:06

1 Answer 1

15
$\begingroup$

The number of integer points in $P_n$ is the number of forests on $[n]$; see Section 3 of Stanley's Decompositions of rational convex polytopes. In fact you can see there a simple description of its entire Ehrhart polynomial in terms of forests. (See also Section 9.3 of Beck and Robins's book Computing the continuous discretely.)

The toric variety corresponding to the permutohedron is also very well-studied, and is often called the "permutohedral variety," but I don't know off the top of my head an answer to your question on ampleness. I would take a look at the book by Gelfand-Kapranov-Zelevinsky, which is a seminal source for a lot of this.

EDIT: Okay, I looked up the definition of very ample polytope. A lattice polytope $\mathcal{P}$ is very ample if for every $N \gg 0$, and $\mathbf{a} \in \mathbb{Z}^{n}\cap N\mathcal{P}$, there are $\mathbf{a}_1,\ldots,\mathbf{a}_N\in \mathbb{Z}\cap \mathcal{P}$ such that $\mathbf{a}=\mathbf{a}_1+\cdots+\mathbf{a}_N$. In fact, the (standard) permutohedron has a stronger property than this. It has the Integer Decomposition Property (IDP) which says that for every $N\geq 1$, and $\mathbf{a} \in \mathbb{Z}^{n}\cap N\mathcal{P}$, there are $\mathbf{a}_1,\ldots,\mathbf{a}_N\in \mathbb{Z}\cap \mathcal{P}$ such that $\mathbf{a}=\mathbf{a}_1+\cdots+\mathbf{a}_N$ (this property is also sometimes called normal, in the context of algebraic geometry, I think). The reason the permutohedron is IDP is because any lattice zonotope is IDP: every zonotope has a tiling by half-open parallelepipeds, and these parallelepipeds are easily seen to be IDP; and the permutohedron is a lattice zonotope- see Chapter 9 of the Beck-Robins book mentioned above.

As John Machacek linked to below, a recent paper of Higashitani and Ohsugi shows that in fact the class of Minkowski sums of unit simplices (which includes the regular permutohedra and many of the generalized permutohedra of Postnikov) have the IDP property.

$\endgroup$
9
  • $\begingroup$ Thank you very much. There is no closed formula then? Do you have any information on the very ampleness? $\endgroup$
    – user82886
    Nov 30, 2020 at 18:38
  • $\begingroup$ There's not going to be a product formula (like there is for the number of trees, Cayley's formula $n^{n-2}$, which is the normalized volume of the permutohedron), but you can certainly write a summation formula. I added a remark about the ampleness question- I don't know the answer to it. $\endgroup$ Nov 30, 2020 at 18:40
  • $\begingroup$ The number of forests on $[n]$ is this OEIS sequence: oeis.org/A001858. $\endgroup$ Nov 30, 2020 at 18:42
  • $\begingroup$ Also, compare this with the Birkhoff polytope, where the Ehrhart polynomial is still unknown $\endgroup$ Nov 30, 2020 at 18:48
  • 3
    $\begingroup$ See also this recent paper for IDP with Minkowski sums of simplicies: alco.centre-mersenne.org/item/ALCO_2020__3_4_831_0 $\endgroup$ Nov 30, 2020 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.