Minkowski sum of small connected sets

Question

Suppose that the convex hull of the Minkowski sum of several compact connected sets in $\mathbb R^d$ contains the unit ball centered at the origin and the diameter of each set is less than $\delta$. If $\delta$ is very small (this smallness may depend on $d$ but on nothing else), does it follow that the sum itself contains the origin?

Answer 1

I finally figured it out. My solution is here. I would repost it on mathoverflow but until LaTeX is enabled, it is quite hard for me to communicate such things here...

Answer 2

Argh! I tried to add this as a comment but when submitting it, I was told that there was a 600 character limit and all my typing just disappeared without trace.

Anyway, my point was that you can get "straight paths". The reason is that if $a=\sum_ i x_ i$ and $b=\sum_ i y_ i$ are in the sum, then the vectors $v_ i=y_ i-x_ i-(b-a)/n$ are small and add up to $0$. There is a cute result that then you can rearrange them in such order that all partial sums are small (just constant times larger than the vectors themselves). If you switch from $x_ i$ to $y_ i$ along the corresponding compact in this order, you get a curve that travels from $a$ to $b$ within a small neighborhood of the segment $[a,b]$.

Another observation that may be useful is that the sum is $d\delta$ dense in its convex hull. Indeed, if $a=\sum_ i v_ i$ and $v_ i$ are in the convex hull of $K_ i$, then we can start moving $v_ i$ until their representations as convex combinations of points in $K_ i$ get shorter and we can do it as long as there are at least $d+1$ vectors $v_ i$ that do not belong to $K_ i$ themselves (any $d+1$ vectors in $\mathbb R^d$ are linearly dependent). Thus, in the representation of every point in the convex hull as a sum, we need only $d$ vectors from convex hulls and the rest may be taken in $K_ i$.

I feel that these two observations put together should be enough and I just do not see how to add 2 and 2 here.

Answer 3

I don't have a proof yet, but here are some ideas that might lead to one. I'll stick to two dimensions. Suppose that your sets are X_ 1,X_ 2,...,X_ m and in each X_ i-X_ i you take a vector x_ i. Now let's suppose that x_ 1+...+x_ r=x and x_ {r+1}+...+x_ m=y, and that x and y are quite a lot bigger than the x_ i and point in very different directions. Then the Minkowski sum of the X_i contains a path that goes from some z to z+x and from there to z+x+y, using bits out of different sets for the two parts of the path. Now we could get from z to z+x+y using the same bits in a different order. For exampe we could go first to z+y and from there to z+x+y. And I'm fairly sure that a topological argument will show that the region bounded by those four bits of path will all be in the Minkowski sum. So it would be enough to show that we can get paths that are reasonably straight.

Why should the bits in between be in the Minkowski sum? It's enough to prove that in the case r=1 and m=2. (After that one just keeps swapping xs from the first half with xs from the second half -- I hope all this is making sense, but I haven't thought about it carefully enough to be sure it isn't stupid in some way.) If X_ 1 contains a path P_ 1 from 0 to x (WLOG) and X_ 2 contains a path x+P_ 2 from x to y, and if the four paths P_ 1, x+P_ 2, P_ 2, y+P_ 1 do not cross and bound some region, then the sets P_ 1+u with u in P_ 2 trace out that region I think.

There are plenty of details to check there and even if they all work one still needs to prove that in the Minkowski sum you can get from any point to any other using a "reasonably straight path", whatever that means. So this is just my preliminary thoughts.

A very nice problem, though!

Answer 4

In dimension 1, why are the sets {-100}, {80},{120} not a counterexample?

(In particular, they are compact connected sets with 'diameter' 0; their Minkowski sum, going by the wikipedia definition, is {-20,20,200}, which does not contain 0, but whose convex hull [-20,200] contains a large ball around 0)

This example of course has nothing to do with dimension, and you can easily flush out the points into tiny balls, if you like. I suspect that this is based on a misreading of the question.