Proving equivalence of two definitions of a convex-type Hamming distance

Question

Update: If somebody can answer my question there, then I will be able to fully answer my question here.

Consider $n\in\mathbb N$ and a non-empty set $M\subset\{0,1\}^n$. I have the following conjecture:

Conjecture. It is true that $$\sup_{\alpha\in[0,1]^n, \lVert \alpha\rVert_2=1}\min_{m\in M} \langle \alpha, m\rangle = \min_{\beta\in[0,1]^M, \sum_{m\in M} \beta_m = 1} \left\lVert\sum_{m\in M}\beta_m m\right\rVert_2.$$

Here, $\beta_m m$ is just the scalar multiplication of the number $\beta_m$ with $m\in M\subset\{0,1\}^n$. Also, $\lVert \cdot\rVert_2$ is the usual euclidean norm and $\langle\cdot,\cdot\rangle$ is the usual euclidean inner product. (And note, of course, that $[0,1]^M$ is the set of all functions $\beta: M\to[0,1]$ where I will write $\beta_m$ for $\beta(m)$.)

---

For instance, it is true if $M=\{m\}$, i.e. if $M$ only contains one element. In that case, the left-hand side equals $$\sup_{\alpha\in[0,1]^n, \lVert \alpha\rVert_2 =1}\langle \alpha,m\rangle.$$

By Cauchy-Schwarz, we know that $\langle\alpha, m\rangle\le\lVert \alpha\rVert_2\lVert m\rVert_2=\lVert m\rVert_2$ and we have equality if and only if $\alpha=\frac{m}{\lVert m\rVert_2}$. Hence the left-hand side equals $\lVert m\rVert_2$.

The right-hand side is, as we must have $\beta=1$, $\lVert m\rVert_2$.

---

If $M=\{m_1, m_2\}$, then we would have to prove $$\sup_{\alpha\in[0,1]^n, \lVert \alpha\rVert_2 = 1} \min(\langle \alpha, m_1\rangle, \langle\alpha, m_2\rangle) = \min_{\beta\in[0,1]} \lVert \beta\, m_1+(1-\beta)\, m_2\rVert_2.$$

This is already not obvious to me. However, for example with $M=\{(1,0),(0,1)\}$, both sides can be computed to equal $\frac1{\sqrt 2}$.

---

Note: This conjecture is a Lemma that I would need to prove the equivalence of different definitions of convex distance that I found in the context of Talagrand's concentration inequality.

---

Another example: Consider $n=4$ and (with a slight abuse of notation) $M=\{m_1,m_2,m_3\}=\{(1,1,0,0),(0,1,1,0),(0,1,1,1)\}$.

The right-hand side is $$\min_{(\beta_1,\beta_2,\beta_3)\in[0,1]^3, \beta_1+\beta_2+\beta_3=1} \lVert (\beta_1,\beta_1+\beta_2+\beta_3,\beta_2+\beta_3,\beta_3)\rVert_2.$$

It is not too hard to see that the minimizer is $\beta=(1/2,1/2,0)$ for which we have $$\lVert (\beta_1,\beta_1+\beta_2+\beta_3,\beta_2+\beta_3,\beta_3)\rVert_2=\lVert (1/2,1,1/2,0)\rVert_2=\sqrt{\frac32}.$$

The left-hand side is $$\sup_{(\alpha_1,\alpha_2,\alpha_3,\alpha_4)\in[0,1]^4, \alpha_1^2+\alpha_2^2+\alpha_3^2+\alpha_4^2=1} \min(\alpha_1+\alpha_2,\alpha_2+\alpha_3,\alpha_2+\alpha_3)=\sup_{(\alpha_1,\alpha_2,\alpha_3,\alpha_4)\in[0,1]^4, \alpha_1^2+\alpha_2^2+\alpha_3^2+\alpha_4^2=1}\min(\alpha_1+\alpha_2,\alpha_2+\alpha_3).$$

The supremum occurs only if $\alpha_1+\alpha_2=\alpha_2+\alpha_3$, which happens for $\alpha=\left(\sqrt{\frac16},\sqrt{\frac23},\sqrt{\frac16},0\right)$.

For that $\alpha$, we have $$\alpha_1+\alpha_2=\alpha_2+\alpha_3=\sqrt{\frac32}$$ and so we indeed have equality of both sides.

Answer 1

Answer inspired by this great answer to a very related question by Paata Ivanishvili.

The right-hand side is equal to $\min_{m\in\operatorname{conv}(M)} \lVert m\rVert_2$, where $\operatorname{conv}(M)$ is the convex hull of $M$ in $\mathbb R^n$. Hence we have:

\begin{equation} \begin{split} \min_{m\in\mathrm{conv}(M)} \|m\|_{2}&=\min_{m \in \operatorname{conv} (M)} \max_{\|\alpha\|_{2}\leq 1} \langle \alpha, m\rangle \\ &\overset{(*)}= \max_{\|\alpha\|_{2}\leq 1} \min_{m \in \operatorname{conv}(M)}\langle \alpha, m\rangle \\ &\overset{(**)}= \max_{\substack{\alpha \in [0, \infty[^{n}\\\|\alpha\|_{2}\leq 1}} \min_{m \in M}\langle \alpha, m\rangle \\ &=\max_{\alpha\in[0,1]^n \\ \lVert\alpha\rVert_2=1}\min_{m \in M}\langle \alpha, m\rangle. \end{split} \end{equation}

(*): Here, a minimax Theorem was used.
(**): Here, the Bauer maximum principle was used (as the minimum of $m\mapsto\langle\alpha, m\rangle$ will be attained on the extremal points of $\operatorname{conv}(M)$, and they are contained in $M$.) Notice that it is also used that $M\subset\mathbb R_+^n$ in order to restrict the $\alpha$'s to $[0,\infty[^n$.

Note. This works for any compact $M\subset\mathbb R_+^n$, not just $M\subset\{0,1\}^n$.