12
$\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$
  • $\begingroup$ Do you agree with my edit? $\endgroup$ – Rodrigo de Azevedo Dec 1 '20 at 18:06
16
$\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$
  • $\begingroup$ Thank you very much. There is no closed formula then? Do you have any information on the very ampleness? $\endgroup$ – Jim Ross Nov 30 '20 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$ – Sam Hopkins Nov 30 '20 at 18:40
  • $\begingroup$ The number of forests on $[n]$ is this OEIS sequence: oeis.org/A001858. $\endgroup$ – Sam Hopkins Nov 30 '20 at 18:42
  • $\begingroup$ Also, compare this with the Birkhoff polytope, where the Ehrhart polynomial is still unknown $\endgroup$ – Per Alexandersson Nov 30 '20 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$ – John Machacek Nov 30 '20 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.