**Update: If somebody can answer [my question there](https://mathoverflow.net/questions/364197/), 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](https://en.wikipedia.org/wiki/Talagrand%27s_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.



Proving equivalence of two definitions of a convex-type Hamming distance
Answer inspired by [this great answer to a very related question](https://mathoverflow.net/a/364202/129831) by [Paata Ivanishvili](https://mathoverflow.net/users/50901/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](https://en.wikipedia.org/wiki/Minimax_theorem) was used.  

(\*\*): Here, the [Bauer maximum principle](https://en.wikipedia.org/wiki/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$.


