Biggest convex set inside a concave unit ball

249 Views Asked by At

Denote the unit ball for the $p$-norm in $\mathbb{R}^N$ with $p \in (0,1]$, $$S_p^N = \Big \{ x \in \mathbb{R}^N,\ \Big(\sum \limits_{i=1}^N |x_i|^p\Big)^{1/p} \le 1 \Big\}$$

We want to find a convex subset of this ball having maximum Lebesgue measure.

My conjecture is that this set is the biggest ball for the $1$-norm that fits inside $S_p^N$. Solving $\lambda S_1^N \subset S_p^N$ yields $\lambda \le N^{1-1/p}$. The points of intersection of $S_p^N$ and $N^{1-1/p}S_1^N$ are the all the points $\big(\pm N^{-1/p},...,\pm N^{-1/p}\big)$. The Lebesgue measure of this convex set is $\frac{2^N}{N!}N^{N\big(1-\frac{1}{p}\big)}$. Is that the highest volume of a convex set inside $S_p^N$?

$\hspace{7cm}$

For example, in $\mathbb{R}^2$, we have the figure just above. I can prove that among all losanges inside $S_{0.5}^2$, $\frac{1}{2}S_1^2$ has the highest volume, yet I can not prove that there are no other convex set that could be better, and I can't either generalize to higher dimensions.

1

There are 1 best solutions below

1
On

Let us consider one of the $2^N$ hyperquadrants of $\mathbb{R}^N$. For simplicity's sake, we look only at the region $$Q = \big\{x \in \mathbb{R}^N\ | \ \forall i \in [\![1,N]\!], x_i \ge 0\big\}.$$

We consider some convex set $C$ with a non zero volume that lies $S_p^N$, that we assume if closed (its closure still is inside $S_p^N$), and $C_0 = N^{1-1/p}S_1^N$ our best candidate. We want to show that $\lambda(C \cap Q) \le \lambda (C_0 \cap Q)$, where $\lambda$ is the Lebesgue measure on $\mathbb{R}^N$.

Last, denote $f(x) = \sum \limits_{i=1}^N |x_i|^p$, and let $x \cdot y$ be the standard euclidean product in $\mathbb{R}^N$, and $d(\cdot, \cdot)$ be the associated distance.

$ $

Technical Lemma: there exists $x_0 \in \mathring{Q}$ with $||x_0||_p=1$ such that for all $c \in C$, $(c-x_0) \cdot \nabla f(x_0) \le 0$

The previous lemma is quite intuitive (we can find some tangent hyperplane that separates $C$ from the outside of the ball), but I could not find a concise proof, so I put a rather lengthy one at the bottom.

$ $

Lemma $2$: for $\alpha_1,...,\alpha_N,L>0$, the volume of the region $\{x \in Q\ |\ \sum \limits_{i=1}^N \alpha_i x_i \le L\}$ is $\frac{L^N}{N! \prod \limits_{i=1}^N \alpha_i}$.

Proof: this is just a change of variable $y_i=\alpha x_i$ and the use of the equality: $\displaystyle{\int}_{\substack{y_1,....,y_N \ge 0\\ \sum \limits_{i=1}^N y_i \le L}} dy_1...dy_n = \frac{L^N}{N!}$, which is simply the volume of one of the $2^N$ quadrants of a hypersphere which volume is known.

$ $

From the two previous results we will deduce our last lemma:

Lemma $2$: $\lambda (C \cap Q) \le \lambda (C_0 \cap Q)$

Proof: if $p=1$ the result is obvious since in that case $C_0 = S_1^N$ is indeed the maximum convex set. Assume $p<1$. We know that $C \cap Q$ is included in $\{x \in Q\ |\ x\cdot \nabla f(x_0) \le x_0 \nabla f(x_0)\}$ for some $x_0 \in Q$ with $||x_0||_p=1$. Since $\nabla f(x_0) = \big(p(x_0)_i^{p-1}\big)_{1 \le i \le N}$ and $x_0 \cdot \nabla f(x_0) = p$, the lemma $2$ gives us $\lambda (C \cap Q) \le \frac{1}{N!} \cdot \frac{p^N}{\prod \limits_{i=1}^N \big(p(x_0)_i^{p-1}\big)} = \frac{\prod \limits_{i=1}^N (x_0)_i^{1-p}}{N!}$. Now let's see when the function $\phi(x) = \sum \limits_{i=1}^N \mbox{ln}(x_i) \cdot (1-p)$ is maximized on the set of $x \in \mathring{Q}$ satisfying the constraint $1 = f(x) = \sum \limits_{i=1}^N x_i^p$. The Lagrange multiplier theorem gives us some $\alpha \neq 0$ such that at the maximum $x_1$, $\nabla \phi(x_1) = \alpha \nabla f(x_1)$, so for all $_i$, $(1-p) \frac{1}{(x_1)_i} = \alpha p (x_1)_i^{p-1}$. Then we find that $(x_1)_i = Cste$, so $(x_1)_i=...=(x_1)_N = \frac{1}{N^{1/p}}$. Taking the exponential of $\phi$, that means $\prod \limits_{i=1}^N (x_0)_i^{p-1}$ is maximal at $x_0=x_1$ and its value is $N^{N \big(1-1/p\big)}$. That concludes the proof since $C_0 = N^{1-1/p}S_1^N$, so $\lambda (C_0 \cap Q) = N^{N\big(1-1/p\big)} \cdot \frac{1}{N!}$ (see again the volume of $S_1^N$ here as in the second lemma.

$ $

Conclusion: Summing over all $2^N$ disjoint quadrants $Q$, this last results gives us $\lambda(C) \le \lambda(C_0)$. We conclude that $C_0 = N^{1-1/p}S_1^N$ is the biggest convex set inside $S_p^N$.

$ $


Proof of the technical lemma: since $Q \cap \partial S_p^N$ is compact, there exists $x_0 \in Q \cap \partial S_p^N$ such that $d(x_0, C) = \inf \limits_{x \in Q \cap \partial S_p^N} d(x,C)$. If for some $i \in [\![1,N]\!]$ we had $(x_0)_i = 0$, using the concavity of $x \mapsto x^p$, for all $c \in C$ we would have $c_i = 0$, so $C$ could not have a non zero volume. Thus $x_0 \in \mathring{Q}$, and $\nabla f(x_0)$ is well defined.

Since we assumed $C$ is closed, and since it is bounded, $C$ is compact, so there exists $c_0 \in C$ such that $d(x_0,c_0) = \inf \limits_{x \in Q \cap \partial S_p^N} \inf \limits_{c \in C} d(x,c)$.

Case 1: if $c_0 \neq x_0$. Let us write $x_0 - c_0 = \alpha \nabla f(x_0) + h$ with $h$ some vector orthogonal to $\nabla f(x_0)$. Ad absurdum, assume that $h \neq 0$, and for $\varepsilon>0$ denote $x_{\varepsilon}=\frac{x_0 - \varepsilon h}{||x_0 - \varepsilon h||_p}\big)$. As $||x_0 - \varepsilon h||_p = f(x_0-\varepsilon h)^{1/p}$ is a differentiable function of $\varepsilon$ in a neighborhood of $0$, with a zero derivative at zero (since $h \cdot \nabla f(x_0)=0$), we have $||x_0-\varepsilon h||_p = 1 + O(\varepsilon^2)$. For $\varepsilon$ small enough, \begin{align*}(x_0 - c_0) \cdot (x_0 - x_{\varepsilon}) & = \alpha \nabla f(x_0) \cdot (x_0-x_{\varepsilon}) + h \cdot \big(-\varepsilon h + O(\varepsilon^2)\big) \\ & = \Big(1-\frac{1}{||x_0-\varepsilon h||_p}\Big) \alpha \nabla f(x_0) \cdot x_0 + \varepsilon h \cdot h + O(\varepsilon^2) \\ & = \varepsilon ||h||_2^2 + O(\varepsilon^2) \end{align*}

and then $d(c_0,x_{\varepsilon})^2 = d(c_0,x_0)^2 - 2(x_0-c_0)\cdot(x_0-x_{\varepsilon}) + d(x_0,x_{\varepsilon})^2 = d(c_0,x_0)^2 - 2\varepsilon ||h||_2^2 + O(\varepsilon^2)$ so for $\varepsilon$ small enough, $d\big(c_0, x_{\varepsilon}\big) < d(c_0, x_0)$, which is absurd. Thus $x_0 - c_0 = \alpha \nabla f(x_0)$ is proportional to the gradient. Finally, since $C$ is convex, for any $c \in C$, $(c-x_0) \cdot (c_0 - x_0) \le 0$, and as $\alpha \neq 0$, we get $(c-x_0) \cdot \nabla f(x_0) \le 0$.

Case $2$: $c_0=x_0$. In that case, we know there is a separation hyperplane between $Q \backslash S_p^N$ and $C$. It has to be the supporting hyperplane of $Q \backslash S_p^N$ at $x_0$, which has $\nabla f(x_0)$ as a normal vector. Then, for all $c \in C$, $c \cdot \nabla f(x_0) \le x_0 \cdot \nabla f(x_0)$.