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$
  • 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$ – Tom Goodwillie Mar 26 '18 at 23:34
  • $\begingroup$ Good counter example Tom, what if X,Y are limited to be inside the positive orthant? $\endgroup$ – MrRed Mar 27 '18 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$ – Tom Goodwillie Mar 27 '18 at 12:20
  • $\begingroup$ I wish I could also add your comment as a correct answer Tom! $\endgroup$ – MrRed Mar 27 '18 at 17:35
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$
  • $\begingroup$ Thank you all for the responses, they were clear and concise :) $\endgroup$ – MrRed Mar 27 '18 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 '18 at 17:44
  • $\begingroup$ What if one or both of $X$ and $Y$ contain the origin? $\endgroup$ – Yaakov Baruch Mar 5 at 10:45
  • $\begingroup$ @YaakovBaruch, see the updated answer $\endgroup$ – Matt F. Mar 5 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$ – Yaakov Baruch Mar 5 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$
  • $\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$ – Matt F. Mar 5 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 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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