2
$\begingroup$

Apologies if this question might be trivial or has been asked already (haven't found an equivalent post), but I am trying to figure out whether the following is true:

Given two convex sets $\mathcal{X} \subseteq \mathbb{R}^n$ and $\mathcal{Y} \subseteq \mathbb{R}^n$, is $\mathcal{Z} := \{x \odot y ~|~ x \in \mathcal{X}, y \in \mathcal{Y}\}$ convex? (Here $\odot$ represents the elementwise multiplication of both vectors.)

If I had to guess I'd say "yes", because if $\mathcal{X}$ is just a point, then $\mathcal{Z}$ is a re-scaled/flipped version of $\mathcal{Y}$ which is convex, and if $\mathcal{X}$ is a line segment (i.e. we only vary a single entry) then $\mathcal{Z}$ is the union of convex sets that can only grow/shrink in one direction, which is also convex. Beyond that I am not sure...

Thank you!

$\endgroup$
4
  • 7
    $\begingroup$ No. In $\mathbb R^2$ if you multiply the line $x=y$ by a point you typically get a line through the origin, and if you multiply it by a short line segment you typically get a non-convex union of two sectors. $\endgroup$ Mar 26, 2018 at 23:34
  • $\begingroup$ Good counter example Tom, what if X,Y are limited to be inside the positive orthant? $\endgroup$
    – MrRed
    Mar 27, 2018 at 0:01
  • $\begingroup$ Still not true. See Matt's answer below. Remarkably, I was about to mention the same example Matt F gives! $\endgroup$ Mar 27, 2018 at 12:20
  • $\begingroup$ I wish I could also add your comment as a correct answer Tom! $\endgroup$
    – MrRed
    Mar 27, 2018 at 17:35

2 Answers 2

4
$\begingroup$

No. Consider $X=Y=\{(u,u+1): u\in R^{\ge 0}\}$. Then $(0^2,1^2)$ and $(2^2,3^2)$ are both in $Z$. If $Z$ is convex then their average $(2,5)$ must also be in $Z$. But $uv=2, (u+1)(v+1)=5$ has no real solutions, so $(2,5)$ is not in $Z$ and $Z$ is not convex.

UPDATE: Even if $X$ and $Y$ are required to contain the origin, the answer is still no. Consider the homogeneous version of the above sets, $X=Y=\{(x,y,y-x): y \ge x \ge 0\}$. Then $X$ is clearly convex. Now the homogeneous version of the above example works too: $(0,1,1)^2$ and $(2,3,1)^2$ are both in $Z$. If $Z$ is convex, then their average $(2,5,1)$ must also be in $Z$. But $xa=2$, $yb=5$, $(y-x)(b-a)=1$ has no real solutions, so $(2,5,1)$ is not in $Z$ and $Z$ is not convex.

$\endgroup$
5
  • $\begingroup$ Thank you all for the responses, they were clear and concise :) $\endgroup$
    – MrRed
    Mar 27, 2018 at 17:33
  • $\begingroup$ Finally, even though I've marked the question as answered, a final question lingers... is there any instance when that would hold true? (i.e. any special cases) $\endgroup$
    – MrRed
    Mar 27, 2018 at 17:44
  • $\begingroup$ What if one or both of $X$ and $Y$ contain the origin? $\endgroup$ Mar 5, 2019 at 10:45
  • $\begingroup$ @YaakovBaruch, see the updated answer $\endgroup$
    – user44143
    Mar 5, 2019 at 16:04
  • 1
    $\begingroup$ Thank you. I now noticed that even in the plane, the "square" of a triangle with vertices (0,0), (0,1) and (1,0) will be the triangoloid with same vertices and straight edges from (0,0), but a convex (i.e. concave upward) edge between (0,1) and (1,0). $\endgroup$ Mar 5, 2019 at 19:43
0
$\begingroup$

The natural "multiplication" for convex bodies (and also for their Minkowski differences, the so-called "hedgehogs") is the convolution product of support functions restricted to the unit sphere. See e.g.:

https://hal.archives-ouvertes.fr/hal-01885039/document

pages 31 and 32.

$\endgroup$
2
  • $\begingroup$ I looked at that but can’t follow it. 1) I know how to subtract angles on S^1 but not on S^2, so how does the convolution works for bodies in R^3? 2) How is the characteristic function defined for a hedgehog? Or does a hedgehog have a formal difference of characteristic functions instead? Will you present a more detailed and more self-contained answer? $\endgroup$
    – user44143
    Mar 5, 2019 at 14:11
  • $\begingroup$ Groemer proved that Minkowski addition of convex bodies corresponds to convolution (with respect to the Euler characteristic) of their characteristic functions. When support functions are analytic, the same is true for hedgehogs. The characteristic functions of hedgehogs (named "Euler index") can also be defined in terms of convolution with respect to the Euler characteristic: see hal.archives-ouvertes.fr/hal-00776724v2/document pages 10 and 11. $\endgroup$
    – Clement
    Mar 5, 2019 at 15:19

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.