Minkowski Sums
  1. Show that vertices of the Minkowski sum of two polytopes $P_1$ and $P_2$ have the form $v_1+v_2$ where $v_1$ and $v_2$ are vertices of $P_1$ and $P_2$ respectively.
  2. Show that any face $F$ of the Minkowski sum of two polytopes $P_1$ and $P_2$ can be written uniquely as $F = F_1 + F_2$ where $F_1$ and $F_2$ are faces of $P_1$ and $P_2$ respectively.
  3. Show that the Newton polytope of the product $f g$ of two polynomials $f$ and $g$ is the Minkowski sum of the Newton polytopes of $f$ and $g$. What can you say about multiplicities?
  4. Show that the normal fan of the Minkowski sum $P_1 + P_2$ is the common refinement of the normal fans of $P_1$ and $P_2$.
  5. Show the tropical hypersurface $\mathcal{T}(f g)$ of the product $f g$ is the union of the tropical hypersurfaces $\mathcal{T}(f)$ and $\mathcal{T}(g)$.
  6. Describe the Newton polytope of the following polynomial. Do you know its name? Describe the tropical hypersurface of the polytope.

$$(x_1 - x_2) (x_1 - x_3) (x_1 - x_4) (x_2-x_3) (x_2 - x_4) (x_3 - x_4).$$


Solution:

1. This appears to be a special case of the second problem.

2. Let $F$ be a face of the Minkowski sum $P=P_1+P_2$ of polytopes $P_1,P_2$. By definition, there is a $w$ for which $F=\{x \in P | w\cdot x \leq w \cdot y, \forall y \in P\}$. Define $F_j = \{ x \in P_j | w\cdot x \leq w \cdot y, \forall y \in P_j \}$ for $j=1,2$. By definition, $F_j$ is a face of $P_j$. It remains to show that $F=F_1+F_2$ and that this decomposition is unique.

Suppose $x \in F$. Then $x \in P=P_1+P_2$, so we may write $x = x_1+x_2$ where $x_j \in P_j$. If $x_1 \notin F_1$, then there exists $y \in P_1$ such that $w\cdot x > w \cdot y$. But then we have $w \cdot x =w \cdot (x_1 +x_2) = w \cdot x_1 + w \cdot x_2 > w \cdot y + w \cdot x_2 = w \cdot (y+x_2)$. Since $y+x_2 \in P$, this would imply that $x \notin F$. Thus we have shown that $x \in F$ implies $x_1 \in F_1$ and $x_2 \in F_2$. Therefore $F \subset F_1+F_2$.

Conversely, suppose that $x_j \in F_j$ and $y_j \in P_j$. Then $w\cdot x_j \leq w \cdot y_j$, and therefore $w \cdot (x_1+x_2) \leq w \cdot (y_1+y_2)$, so that $x_1+x_2 \in F$. This shows $F=F_1+F_2$. Finally, note that our proof of the inclusion $F \subset F_1+F_2$ shows uniqueness.

3. The easy direction, that $\mathcal{N}(fg) \subseteq \mathcal{N}(f) +\mathcal{N}(g)$, follows from the observation that the support of $fg$ is contained in the sum on the right.

In the other direction, we take a vertex $v$ of $\mathcal{N}(f) +\mathcal{N}(g)$. Write $v = v_1 +v_2$ uniquely as in the above problem. By this uniqueness, we must have $v \in \operatorname{supp}(fg)$. Thus we have shown that $\mathcal{N}(fg)$ contains all vertices of the polytope $\mathcal{N}(f) +\mathcal{N}(g)$. Since $\mathcal{N}(fg)$ is a convex set, it must contain the convex hull of these vertices, namely the set $\mathcal{N}(f) +\mathcal{N}(g)$.

4. Using the notation from the "Tropical Book", we need to prove that $\mathcal{N}_{P+Q} = \mathcal{N}_P \wedge \mathcal{N}_Q$ for polytopes $P,Q$.

First note that $\mathcal{N}_P(F)$ for a face $F$ of $P$ is equal to $\{w : w(f) \leq w(p), \text{ for all } f\in F, p \in P\}$: if we denote by $V$ the set of vertices of $P$ belonging to $F$, and by $U$ the set of those not in $F$, then

$\{w : \operatorname{face}_w(P) = F\}=\{w : w(v)=w(v^') \text{ for all } v, v^' \in V \text{ and } w(v) < w(u) \text{ for all } v \in V, u \in U\}$.

Taking the closure gives $\{w : w(f) \leq w(p), \text{ for all } f\in F, p \in P\}$, or equivalently $\{w : F \subset \operatorname{face}_w(P) \}$. We now show that for any faces $F,G$ of $P,Q$ one has

$\mathcal{N}_{P+Q}(H(F,G)) = \mathcal{N}_P(F) \cap \mathcal{N}_Q(G)$,

where $H(F,G)$ is defined to be the smallest face of $P+Q$ containing $F+G$ (could be $F+G$ itself!). Suppose $w \in \mathcal{N}_{P+Q}(H(F,G))$. Since $F+G \subset H(F,G)$, for any $f \in F, g \in G, p \in P$ we have $w(f+g) \leq w(p+g)$ and so $w(f) \leq w(p)$, which shows $w \in \mathcal{N}_P(F)$. And $w \in \mathcal{N}_Q(G)$ by the same reasoning.

Conversely, suppose $w \in \mathcal{N}_P(F) \cap \mathcal{N}_Q(G)$. Then $w(x) \leq w(y)$ for all $x \in F+G$ and $y \in P+Q$. In other words, $F+G \subset \operatorname{face}_w(P+Q)$, and therefore $H(F,G) \subset \operatorname{face}_w(P+Q)$. But this says that $w \in \mathcal{N}_{P+Q}(H(F,G))$. So we've proved

$\mathcal{N}_{P+Q}(H(F,G)) = \mathcal{N}_P(F) \cap \mathcal{N}_Q(G)$.

This clearly shows $\mathcal{N}_{P+Q} \supset \mathcal{N}_P \wedge \mathcal{N}_Q$. Finally, given a face $F$ of $P+Q$, we decompose as in the previous problem to get

$\mathcal{N}_{P+Q}(F)=\mathcal{N}_{P+Q}(H(F_1,F_2)) =\mathcal{N}_P(F_1) \cap \mathcal{N}_Q(F_2) \in \mathcal{N}_P \wedge \mathcal{N}_Q$.

5. Recall that $w \in \mathcal{T}(fg)$ exactly when it supports a nonvertex face of $\operatorname{Newt}(fg)$. Since $\operatorname{Newt}(fg)=\operatorname{Newt}(f) +\operatorname{Newt}(g)$, the above argument shows that $w \in \mathcal{T}(fg)$ exactly when $w$ supports a nonvertex face of $\operatorname{Newt}(f)$ or of $\operatorname{Newt}(g)$. In other words, $w \in \mathcal{T}(fg)$ exactly when $w \in \mathcal{T}(f) \cup \mathcal{T}(g)$
-MH

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License