Average in an open set, does it imply convexity?

Question

Let $C$ be an open subset of $\mathbb{R}^n$. If for all $a,b \in C$, $(a+b)/2 \in C$, then prove that $C$ is convex.

Answer 1

Lord_Farin's answer uses an abstract argument. Here is a more concrete solution:

You probably have noticed (e.g. from the other answers) that you inductively have all points of the form $a+\frac{i(b-a)}{2^n}$ in the set $C$. The kicker is now that you also have an open ball around $a$ of radius $\epsilon_1$ and one around $b$ or radius $\epsilon_2$ in $C$ (because $C$ is open). If $\epsilon=\min\{\epsilon_1,\epsilon_2\}$, then balls of radius $\epsilon$ around $a$ and $b$ are in $C$. Now you can show that you actually have a ball of radius $\epsilon$ around each of the points $a+\frac{i(b-a)}{2^n}$ in the set $C$ (do you see why?)! Since you can approximate any point between $a$ and $b$ arbitrarily close by a point of this form, you are done.

Answer 2

We have to show that $\theta x + (1-\theta )y \in C$ for all $\theta \in [0,1]$ and $x,y \in C$. Let $\theta^{(k)}$ be the binary number of length k, i.e., a number of the form

$$\theta^{(k)} = c_12^{-1}+c_22^{-2}+ \ldots +c_k2^{-k}$$

with $c_i\in\{0,1\}$, closest to $\theta$

By midpoint convexity (applied k times, recursively),

$$\theta^{(k)}x+(1-\theta^{(k)})y \in C$$

If C is closed, $$\lim_{k\rightarrow\infty}\theta^{(k)}x+(1-\theta^{(k)})y = \theta x+(1-\theta)y \in C$$ Hence, $C$ is convex.

If C is not closed, the above will not hold.

Answer 3

Assume that we have the result for closed $C$ (see damned's answer; i.e. approximate $\theta \in [0,1]$ by its dyadic convergents and use that $\Bbb R^n$ is complete).

Now suppose $C$ is open. Define for $c \in C$:

$$d(c, C^c) = \inf \{\|x-c\|: x \notin C\}$$

Since $C$ is open, $d(c,C^c) > 0$ for all $c \in C$. In particular, if we define:

$$C_n = \left\{c \in C: d(c,C^c) \ge \frac1n\right\}$$

we have that:

$$C = \bigcup_{n\in\Bbb N} C_n$$

Now, given $c,c' \in C$, there exists an $n \in \Bbb N$ such that $c,c' \in C_n$. Since $C_n$ is closed, the proposition for open sets follows from that for closed sets, provided we can show $C_n$ has the "average property". (Thanks Daniel for pointing this out.)

---

So given $c,c' \in C_n$, we want to show that $c''= \frac12(c+c') \in C_n$. Suppose that $x \in \Bbb R^n$ and $\|x-c''\| < \frac1n$.

Then since $\|x-c''\| < \frac1n$, we have that $c + (x-c'') \in C$, and similarly $c'+(x-c'') \in C$. Hence by the hypothesis on $C$:

$$\frac12\left[c+(x-c'') \,+\, c'+(x-c'')\right] = \frac12(c+c') + (x-c'') = x \in C$$

It follows that $d(c'', C^c) \ge \frac1n$, as desired.

Answer 4

The responses actually did the solution. Here I'm summarizing the solution in possibly with simpler notation.

Let $\epsilon_1$ and $\epsilon_2$ are the radii around points $a, b$ respectively so that the corresponding open balls around those points $B_1(a,\epsilon_1) := \{z \in S | ||a-z|| < \epsilon_1\}$ and $B_2(b,\epsilon_2) := \{z \in S | ||b-z|| < \epsilon_2\}$ lie entirely within $S$. Let $\epsilon = \min \{\epsilon_1,\epsilon_2\}$. Let $c = (a+b)/2$. Pick any $x$ such that $||x - c|| < \epsilon$. We show that all such points lie in $S$. To see this, we notice that $a + (x - c) \in S$, and $b + (x -c) \in S$. Therefore, we have $x = (a + (x - c) + b + (x -c))/2 \in S$. Hence the ball around $c$ with radius $\epsilon$ lies entirely within $S$.

To prove the result, we need to show that for any $\lambda \in [0,1]$, the point $p = \lambda a + (1-\lambda) b$ lies in $S$. Now we can construct a sequence $\{p_n\}$, where $p_{-1} = a, p_0 = b$. Define $p_n = (p_{\arg\min_k \{||p_k - p|| : p_k \in ls(a,p), k \leq n-1\}} + p_{\arg\min_k \{||p - p_k|| : p_k \in ls(p,b), k \leq n-1\}}) / 2$, for $n \geq 1$, where $ls(a,p)$ denotes the line segment between $a$ and $p$. Essentially, the construction encloses the point $p$ within the closest two elements of this sequence which are already in $S$. Clearly, the distance $||p_n - p||$ decreases in each iteration. Hence, for all $\epsilon > 0$ there exists a $N_{\epsilon}$ such that $\forall \ n \geq N_{\epsilon}$, $||p_n - p|| < \epsilon$. And since we have shown that for all such points in the sequence the open ball of radius $\epsilon$ centering those points lie entirely within $S$, we conclude that $p \in S$.