2
$\begingroup$

For any set $P,Q$ in the Euclid space, define Minkowski sum '+' as follows: $P+Q=\{p+q|p\in P, q\in Q\}$. And define 'zonotope': a zonotope is the Minkowski sum of some (finite) segments (for example, parallelograms).

In the 4-dimension Euclid space, $A=\{\operatorname{conv}(P\cup Q)\mid P, Q \text{ are zonotopes}\}$, (all points and segments are zonotopes as well, thus all points, segment, trianges and tetrahedrons are in $A$).

Let $B=\{\text{any finite Minkowski sum of elements in $A$}\}$.

The question is that, for a 4-dimension simplex $a$, are there $b,c$ in $B$ such that $b = a+c$ (here $+$ is the Minkowski sum). By affine transformation, we can just consider the case where the vertices of $a$ are $(0,0,0,0),(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)$ (so that $a$ is the convex hull of these five points).

Here is my attempt: I try to consider the 3-dimension version: $A=\{\operatorname{conv}(P\cup Q)\mid P \text{ is a zonotope}, Q\text{ is a single point}\}$ and the define $B$ similarly. The question becomes: for a 3-dimension simplex $a$, are there $b,c$ in $B$ such that $b=a+c$.

$\endgroup$
3
  • $\begingroup$ What are zonotopes? Are they simply simplices of dimension $\, \le 4$? $\endgroup$
    – Wlod AA
    Commented Oct 22, 2019 at 6:30
  • 1
    $\begingroup$ @WlodAA, oh, thank you for your asking, I should have explained this. A zonotope is the Minkowski sum of some (finite) segments. A typical example is parallelograms(the Minkowski sum of two segments). (I have edited now:) $\endgroup$
    – Yachy
    Commented Oct 22, 2019 at 14:12
  • $\begingroup$ Is there any constraint on $\displaystyle a$ ? if no, then the answer should be yes. based on the definition, pick \begin{gather*} b\ =\ \frac{1}{2} p_{1} +\frac{1}{2} q_{1} ,\ c\ =\ \frac{1}{2} p_{2} +\frac{1}{2} q_{2} \ \\ p_{1} ,p_{2} \ \in \ P\\ q_{1} ,q_{2} \ \in Q \end{gather*} Since $\displaystyle b,c$ and convex combination of elements from $\displaystyle P,\ Q$, then are in $\displaystyle A$, hence in $B$, Pick $\displaystyle a\ =\ \frac{1}{2}( p_{1} \ -\ p_{2}) +\ \frac{1}{2}( q_{1} -q_{2})$, Then $\displaystyle b\ =\ a+c$ $\endgroup$
    – yupbank
    Commented Jul 24, 2020 at 0:56

1 Answer 1

1
$\begingroup$

Just to say this at the beginning: I do not have an answer to your question. I would have used the comment option if I had enough reputation to do so.

I am not sure what motivation you had originally in mind, but the reason why I am highly interested is as follows: Your question is equivalent to asking whether a neural network with two hidden layers of ReLU activations can compute the maximum of five numbers. More details about this question can be found in this paper: https://proceedings.neurips.cc/paper/2021/hash/1b9812b99fe2672af746cefda86be5f9-Abstract.html, where the authors conjecture that the answer to your question is "no". The maximum function is so interesting in this context because it is, with respect to depth and given arbitrary width, provably the hardest function to represent for a neural network.

Since I spent quite some time thinking about it, I am quite sure that your question is indeed an open question and it definitely deserves to be investigated!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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