# Separating compact, non-convex sets in $\mathbb R^n$

Let $m>1$. For disjoint compact subsets $E$ and $F$ of $\mathbb{R}^n$ we can define $$d(E,F) := \sup_\phi \inf \{\phi(x)-\phi(y)| x\in E, y\in F\},$$ where the supremum is taken over all bounded $\phi\in C^\infty(\mathbb R^n; \mathbb R )$ with $\|D^\alpha\phi\|_\infty \leq 1$ for $1\leq |\alpha| \leq m$.

We easily get $d(E,F)\leq n^{1/2} \tilde d (E,F),$ for $\tilde d$ being the Euclidean distance. Since for compact convex sets we can always find a linear function with gradient of norm 1 such that $$\tilde d(E,F) = \inf \{\phi(x)-\phi(y)| x\in E, y\in F\},$$ we can approximate it by a sequence of bounded $C^\infty$ functions to obtain

$\tilde d(E,F)\leq d (E,F),$ whenever $E, F \subseteq \mathbb R^n$ are two disjoint, compact and convex sets.

The question I have been struggling with is: can we relax the condition that both sets need to be convex to obtain the above inequality (with possibly some extra, but uniform, constants)? I am particularly interested in the case when $E$ is the closed unit ball and $F$ is $\{x\in \mathbb R^n| 2\leq|x|\leq 4\}$. First I took a linear function as above separating $E$ and $B= \{x\in \mathbb R^n| |x-3e_1|\leq 1\}$ a compact and convex subset of $F$. This can't work though, because if I allow $y\in F\setminus B$ the infimum becomes negative.

Should it be possible to construct some kind of a cut-off function with the above properties?

I will be grateful for help!

PS. the answer to the above question for $m=1$ is yes, since the distance function is Lipschitz continuous.

Update: The claim holds for any disjoint closed subsets of $\mathbb R^n$. The idea of the following proof comes from Lemma 2.3 in this paper.

Let $s=\tilde d(E,F) >0$ and $\psi \in C^\infty_c(\mathbb R^n)$, supported in the unit ball, with $\int \psi =1$. We consider the rescaled function $\psi_\varepsilon = \varepsilon^{-n}\psi(\cdot/\varepsilon)$ for $\varepsilon>0$. Let us fix $\varepsilon = \frac{s}{4}$ and denote the $\delta$-neighbourhood of $E$ w.r.t. $\tilde d$ by $\tilde E_\delta$. Define $C_\psi = \sum_{1\leq|\alpha|\leq m} \int |D^\alpha\psi|.$ We distinct two cases:

Case 1. $\varepsilon\ge 1$ Let $\phi = \frac{\varepsilon}{C_\psi}\chi_{\tilde E_\varepsilon} \ast \psi_\varepsilon$. Then $\phi$ satisfies $\|D^\alpha\phi\|_\infty \leq 1$ for $1\leq |\alpha| \leq m$. We obtain for $x\in E, y\in F$

\begin{align} \phi(x)-\phi(y)=\phi (x) & = \frac{\varepsilon}{C_\psi}\int_{B(x,\varepsilon)} \psi_\varepsilon(x-z) dz \\ & = \frac{\varepsilon}{C_\psi}\ge C\tilde d(E,F)\end{align}.

Case 2. $\varepsilon\leq 1$ Let $\delta=\varepsilon^{\frac{1}{m}}$ and we set $\phi = \frac{\varepsilon}{C_\psi}\chi_{\tilde E_\delta} \ast \psi_\delta$. Then one checks that $\phi$ also satisfies $\|D^\alpha\phi\|_\infty \leq 1$ for $1\leq |\alpha| \leq m$. We have for $x\in E, y\in F$

\begin{align} \phi(x)-\phi(y)=\phi (x) & = \frac{\varepsilon}{C_\psi}\int_{B(x,\delta)} \psi_\delta(x-z) dz \\ & = \frac{\varepsilon}{C_\psi}\ge C\tilde d(E,F)\end{align}.

• I'm not sure I get your question, but if you want to separate $E = \{x \in \mathbb{R}^n : ||x||\leq 1\}$ from $F = \{x \in \mathbb{R}^n: 2\leq ||x|| \leq 4\}$ via a smooth nonlinear function, then what about $f:\mathbb{R}^n \rightarrow\mathbb{R}$ given by $f(x) = ||x||^2 =x_1^2 + ... + x_n^2$? It gives $E \subseteq \{x : f(x)\leq 1\}$ and $F\subseteq \{x : f(x)\geq 4\}$. May 14, 2018 at 7:17
• Thanks, but unfortunately the gradient of this function is unbounded.
– Wiki
May 15, 2018 at 0:55
• Well then, what about $f(x) = c \sum_{i=1}^n \arctan(dx_i^2)$? (For sufficiently small positive values of $c, d$). The intuition is that if $d$ is sufficiently small the $\arctan$ function looks linear about $x=0$, so we get similar separation properties as $||x||^2$. But I believe for any positive integer $m$ we have all $k$-level derivatives are bounded for $1\leq k \leq m$. Then $c$ comes in to simply make the derivatives small enough. Similarly you could use $f(x) = c \sum_{i=1}^n g(dx_i^2)$ for some function $g$ like $g(x) = \frac{x}{x+1}$. May 15, 2018 at 5:15

This gives details to my comment. Define $g:[0,\infty)\rightarrow\mathbb{R}$ by $$g(x) = \frac{x}{x+1}$$ Note that $g$ is increasing and concave. Fix $n$ as a positive integer and define $h:\mathbb{R}^n\rightarrow\mathbb{R}$ by $$h(x) = \sum_{i=1}^n g(dx_i^2)$$ for some $d>0$. Then $h$ is infinitely differentiable. Let $||x||=\sum_{i=1}^n x_i^2$ be the standard Euclidean norm.

### Claim 1: $||x||\leq 1 \implies h(x)\leq \frac{d}{1+d/n}$

Suppose $||x|| \leq 1$. Then by Jensen's inequality for the concave function $g$: \begin{align} h(x) &= n\cdot \frac{1}{n}\sum_{i=1}^n g(dx_i^2) \\ &\leq ng\left(\frac{1}{n} \sum_{i=1}^n dx_i^2\right) \\ &= ng\left(\frac{d}{n}||x||^2\right) \\ &\leq ng(d/n)\\ &= \frac{d}{1+d/n} \end{align} $\Box$

### Claim 2: $||x||\geq 2 \implies h(x)\geq \min[1/2, 2d]$.

Suppose $||x||\geq 2$. Notice that $$g(y) \geq y/2 \quad \mbox{whenever y \in [0,1]} \quad (Eq. *)$$

Case 1: If there is an index $i \in \{1, ..., n\}$ such that $dx_i^2>1$ then $$h(x) \geq g(d x_i^2) \geq g(1) = 1/2$$

Case 2: If $dx_i^2 \in [0,1]$ for all $i \in \{1, ..., n\}$, then $g(dx_i^2)\geq dx_i^2/2$ for all $i \in \{1, ..., n\}$ (by (Eq. *)) and $$h(x) = \sum_{i=1}^n g(dx_i^2) \geq \sum_{i=1}^n dx_i^2/2 = (d/2)||x||^2\geq 2d$$ $\Box$

### Claim 3: If $d=1/4$ we have a strict separation.

By Claims 1 and 2:
\begin{align} E &= \{x \in \mathbb{R}^n : ||x||\leq 1\} \subseteq \left\{x \in \mathbb{R}^n : h(x)\leq \frac{d}{1+d/n} \right\} \\ F &= \{x \in \mathbb{R}^n : 2 \leq ||x|| \leq 4\} \subseteq\left\{x \in \mathbb{R}^n : h(x)\geq \min[1/2, 2d]\right\} \end{align} Since $d=1/4$ we have \begin{align} E &\subseteq \left\{x \in \mathbb{R}^n : h(x)\leq \frac{1}{4+1/n} \right\} \\ F &\subseteq \left\{x \in \mathbb{R}^n : h(x)\geq 1/2\right\} \end{align} $\Box$

### Claim 4: We can choose $f(x) = ch(x)$ for small $c>0$

Fix $c>0$. Clearly the strict separation still holds for the scaled function $f(x) = ch(x)$.

Fix $m$ as a positive integer. It can be shown that there is a value $B>0$ such that for all $i \in \{1, ..., n\}$ and all $k \in \{1, ..., m\}$ we have $$|\frac{\partial^k}{\partial x_i^k} h(x) |\leq B \quad \forall x \in \mathbb{R}^n$$
and so we can choose $c>0$ sufficiently small to ensure the gradients of $ch(x)$ are sufficiently small.

• That is a clever idea, thank you! With different constants this also works for any ball with radius $r>0$ and radii with radii replaced by $2^m r$ and $2^{m+1}r$. Also, I have just found that the claim above holds for any disjoint and closed subsets (see link Lemma 2.3.)
– Wiki
May 15, 2018 at 13:25
• Thanks. I believe that for arbitrary $r>0, \epsilon>0$, we can choose a small enough $d>0$ so that $h$ separates radii $r$ and $r+\epsilon$. May 15, 2018 at 14:52