Minkowski sums (and how big they must be)

So, this is the promised actual first post, motivated by and answering a question recently posed to me by Yue Ren (and several before him that I apologize for forgetting). It comes with a problem, and that is, to prove the result in a simpler, more elementary way.

I had written a longer paper (with Raman Sanyal) on a problem concerning Upper Bounds on the complexity of Minkowski sums that dealt with the problem quite thoroughly.

But after we submitted the paper, and it was accepted and published in Publications IHES, someone asked me a question. I thought for a while, and answered that it follows from that and that lemma in the paper. But the question came up again and again, seemingly being quite relevant. On the other hand, writing a new paper on the matter was tedious, as it promised to be 90% repetition of paper number one. Which was an annoying prospect at best.

The problem is this: Consider a bunch (say m of polytopes (P_i) in a euclidean vector space of dimension d. For simplicity, and to be interesting, let us assume that all these polytopes are of positive dimension. Also, let us assume that all these polytopes are in general position with respect to each other.

Question: How many vertices must the Minkowski sum of the family (P_i) have? Surely, it has to be at least the number of vertices as the Minkowski sum of m segments in general position.

Turns out, the naive guess is correct. Also turns out that the proof seems to be quite a bit harder than I initially thought it would be. Indeed, the naive idea, that the Minkowski sum of two polytopes of positive dimension P and Q, P fixed, is minimized if and only if Q is a line segments, is not true. The real proof, unfortunately, seems to need a considerable detour. Let me sketch it here.

The first idea here is to consider the Cayley polytope of the family (P_i). This is a polytope in \mathbb{R}^{d+m-1}= \mathbb{R}^{d} \otimes \mathbb{R}^{m-1} obtained by translating each of the P_i independently into general positon, for instance by translating each of them along a choice of m vectors v_i in general position in \mathbb{R}^{m-1} that sum to zero. And then passing to the convex hull.

That is a rather powerful trick, as we now have a new polytope C(P_i) that encodes the Minkowski sum: we obtain it back by slicing the polytope with the subspace \mathbb{R}^{d}. The collection of faces of C(P_i) that intersects \mathbb{R}^{d} is called the “open Cayley complex” T^\circ(P_i), its closure is the Cayley complex T(P_i).

Now we count the number of faces f_j of the Minkowski sum, or equivaently, the face numbers of the open Cayley complex (shifted by m-1). That is best done by first transforming to the h-vector,

h_k := \sum_{i=0}^k (-1)^{k-j}\binom{d-j}{k-j}f_{j-1}.

and estimating this. There are now two essential facts: We have the Dehn-Sommerville relations

h_k(T(P_i)) \ =\ h_{d+m-j}(T^\circ(P_i)) + E

where the error E only depends on number of summands, and the important inequality

h_1(T(P_i)) \ \le\ h_{d-j}(T^\circ(P_i))

for all j\ge 1. That last inequality is key, and seems to only really follow from that Lefschetz theorem for polytopes (or the associate toric variety) where the first, the Dehn-Sommerville relations, follow from “only” a version of Poincar\’e duality.

Now the path is clear: if we want to estimate the number of k-faces of the Minkowski sum, then we can equally estimate the number of k+m-1-faces of the open Cayley complexes, which amounts to estimating h_{k+m}(T^\circ(P_i)), or equivalently, h_{d-k+1}(T^\circ(P_i)).

Which of course is bounded below by h_1(T(P_i)), which is quickly computed to be the total number of vertices of summands, minus d+m-1, and gives the desired lower bound.

The details can be found here and in its appendix here.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s