5
$\begingroup$

Given a polytope $P$, what do the points of the secondary polytope correspond to?

I know that the vertices of the secondary polytope correspond to regular triangulations of $P$. But what do the interior points of the secondary polytope correspond to?

$\endgroup$
5
  • 1
    $\begingroup$ Vertices correspond to regular triangulations. I believe there is a sense in which other lattice points correspond to (non-regular) triangulations, but the correspondence is not exact (i.e., not one-to-one). $\endgroup$ Commented May 6, 2022 at 12:59
  • 2
    $\begingroup$ Okay, I think the paper "The Polytope of All Triangulations of a Point Configuration" by de Loera, Hosten, Santos, and Sturmfels (math.uni-bielefeld.de/documenta/vol-01/04.pdf) may explain a bit more precisely what I said above: there is a (much bigger) polytope whose points correspond to all triangulations of $P$, and the secondary polytope is a projection of this bigger polytope, so integer points of the secondary polytope can in general be associated to triangulations, but not in a bijective fashion. $\endgroup$ Commented May 6, 2022 at 13:11
  • $\begingroup$ My mistake for forgetting the adjective "regular". I just added it to the wording of my question. $\endgroup$ Commented May 6, 2022 at 15:08
  • $\begingroup$ @SamHopkins. I'm not sure what you mean by an integer point of the secondary polytope... Were you assuming that $P$ is itself a polytope whose points have integer coordinates (I certainly wasn't assuming that)? What about the case when $P$ has rational coordinates? Can you then also say something along the lines of what you said in your second comment – a correspondence between arbitrary rational points and some kind triangulations?... $\endgroup$ Commented May 6, 2022 at 15:14
  • $\begingroup$ You are right that it does not make much sense to talk about integer points for the secondary polytope in general, but note that for the bigger ("universal") polytope that projects to the secondary polytope, its vertices are integer points by definition (and actually it only depends on the oriented matroid structure of the original point set, not the specific geometry, unlike the secondary polytope). $\endgroup$ Commented May 6, 2022 at 21:00

2 Answers 2

4
$\begingroup$

As pointed out by Sam Hopkins in a comment above, secondary polytopes can be seen as a particular case of the fiber polytopes of Billera and Sturmfels (https://doi.org/10.2307/2946575). This fiber polytope view provides the answer (or, at least, one answer) to what each point in the secondary polytope represents:

Consider a point configuration $A=\{a_1,\dots,a_n\}\subset \mathbb R^d$ (For the secondary polytope of a polytope $P$, take as $A$ the set of vertices of $P$, and substitute $P$ for $\operatorname{conv(A)}$ in all the description below). There is a canonical projection \begin{align} \pi: \Delta^{n-1} &\to \operatorname{conv(A)}\\ e_i &\mapsto a_i, \end{align} where $e_1,\dots,e_n$ are the standard basis in $\mathbb R^n$ and $\Delta^{n-1}$ is their convex hull, that is, the standard $n-1$-simplex.

Now, consider the space $\mathcal S$ of all sections of $\pi$. That is, elements of $\mathcal S$ are maps $s:\operatorname{conv(A)} \to \Delta^{n-1}$ such that $\phi\circ s$ is the identity map. Put differently, they are maps that choose a point in the fiber $\pi^{-1}(x)$ for each point $x\in \operatorname{conv(A)}$. (You can restrict to continuous sections, or to piecewise-linear sections, but you don't need to; what I say below holds for arbitrary sections too, as long as you can integrate them to compute their average).

Finally, consider the map that computes the average (or barycenter) of each such section. This is a map from $\mathcal S$ to the fiber $\pi^{-1}(b)$, where $b$ is the barycenter of $\operatorname{conv(A)}$. The secondary polytope of $\operatorname{conv(A)}$ is nothing but the image of this last map.

That is, each point in the secondary polytope corresponds, not uniquely, to a section of $\pi$; or, more precisely, it corresponds to the set of all sections with that average.

Vertices of the secondary polytope are special in that each of them is the image of a unique, and extremal, section, obtained by ``coherently'' picking the vertex of each fiber in a fixed direction. The section obtained in this coherent way is a union of faces of $\Delta^{n-1}$ forming (via $\pi$) the regular triangulation of $A$ corresponding to that vertex. This is why regular triangulations are also sometimes called coherent.

$\endgroup$
3
  • $\begingroup$ This is an excellent answer! I wonder whether there exists a way of selecting one "best" section amongst the set of all sections with given average... $\endgroup$ Commented Oct 14, 2022 at 20:58
  • $\begingroup$ I do not see a natural way of choosing one section. Let $A$ be the vertices of a quadrilateral. $\pi$ projects a tetrahedron $T$ to $\conv(A)$ and there are two extremal sections, the "upper" and "lower hull" of $T$ (wrt $\pi$), corresponding to the two vertices of the secondary polytope, a segment. Certainly, you can say that any convex combination of these two extremal sections is a section, and they give a canonical representative for each point in the secondary polytope. But you are able to do this only because your secondary polytope was a simplex (continues below). $\endgroup$ Commented Oct 16, 2022 at 8:37
  • $\begingroup$ (continued) In general, you can still say that every convex combination of extremal sections (regular triangs) is a section, and that they cover all points in the secondary polytope. But you loose uniqueness: for each point $x$ in the secondary polytope you get as many sections as ways there are of writing $x$ as a convex combination of vertices. Ok, one way to make the section unique (but not very canonical) is to choose a triangulation of the secondary polytope, and for each $x$ use the convex combination coming from the vertices of the simplex containing $x$... $\endgroup$ Commented Oct 16, 2022 at 8:43
1
$\begingroup$

Okay, let me convert my comments into something more coherent. It may not be what you're looking for, though, because the short answer is: I'm not sure an arbitrary real point in the secondary polytope of $P$ corresponds to anything particularly significant in terms of $P$.

First let me review the Gelfand, Kapranov, Zelevinsky definition of the secondary polytope. A good reference for this is "Constructions and complexity of secondary polytopes" by Billera, Filliman, and Sturmfels (https://doi.org/10.1016/0001-8708(90)90077-Z).

More generally we can associate a secondary polytope, a polytope in $\mathbb{R}^n$, to any finite set $\mathcal{A}=\{x_1,\ldots,x_n\}$ of points in $\mathbb{R}^d$, which we assume has the maximum dimension $d$ (where the dimension of $\mathcal{A}$ is the dimension of its affine span). The case where we take $\mathcal{A}$ to be the vertices of polytope $P$ is the one commonly considered.

To any triangulation $\tau$ of $\mathcal{A}$ we associate the point $\phi^{\tau}$ in $\mathbb{R}^n$ with coordinates $(\phi^{\tau}_1,\ldots,\phi^{\tau}_n)$ where $\phi^{\tau}_i = \sum_{\Delta \in \tau, x_i \in \Delta} \mathrm{vol}(\Delta)$, where the sum is over all maximal dimensional simplices $\Delta$ in $\tau$ that have the point $x_i$ as a vertex.

The secondary polytope of $\mathcal{A}$ is the convex hull of the $\phi^{\tau}$ over all triangulations $\tau$ of $\mathcal{A}$.

The main result here is that the vertices of the secondary polytope are exactly the $\phi^{\tau}$ for $\tau$ a regular triangulation, and this sets up a bijection between vertices and regular triangulations. More generally, the faces of the secondary polytope correspond to regular polyhedral subdivisions, and in fact the poset of faces is anti-isomorphic to the poset of regular polyhedral subdivisions.

Notice that $\phi^{\tau}$ for $\tau$ a non-regular decomposition gives some point (not a vertex) inside the secondary polytope: see Example 2.4 of the Billera, Filliman, and Sturmfels paper for an example of this. So for some of the other real points in the secondary polytope we can say that they "correspond" to non-regular triangulations (though note that in general, a point may correspond to multiple such triangulations- see Example 2.4).

But for a general real point in the secondary polytope, again I'm not sure we can say it corresponds to something very concrete about the point set $\mathcal{A}$.


As I mentioned in my comments, there is also something called the "universal polytope" of the point set $\mathcal{A}$ whose vertices correspond to all the triangulations (regular and non-regular) of $\mathcal{A}$. This polytope lives in a much bigger dimensional space and the secondary polytope is a projection of it. It is discussed in the Billera, Filliman, and Sturmfels paper. Though actually its existence does not say much about your question, beyond the aforementioned fact that some non-vertex points in the secondary polytope correspond to non-regular triangulations.


EDIT: Maybe what you really want after all is the following construction. To any point in the secondary polytope, we can associate it with the highest dimensional face it is in the relative interior of; that face corresponds to some regular polyhedral decomposition of $P$; so we can map the point to that subdivision. This sets up a map from points in the secondary polytope to regular polyhedral decompositions which restricts to the map from vertices to regular triangulations. Of course, it is very very far from injective.

$\endgroup$
2
  • $\begingroup$ Thank you Sam for this very detailed exposition. Really, what I'm asking is how to think of a general real point in the secondary polytope. It must correspond to something significant in terms of $P$... I'm just not sure what. $\endgroup$ Commented May 6, 2022 at 22:58
  • 1
    $\begingroup$ One more perspective you might find enlightening: secondary polytopes are a special case of the fiber polytopes of Billera-Sturmfels (see doi-org.proxyhu.wrlc.org/10.2307/2946575). $\endgroup$ Commented May 6, 2022 at 23:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .