# Given $H_{N}=\{\vec{x} \in [-1,1]^N:\sum_{i=1}^N x_i = 0\}$, what is the smallest subset $S \subset H_{2N}$ such that $\mathrm{conv}(S)=H_{2N}$

## Motivation:

This is related to a different question I asked in April. It occurred to me while thinking about the sums of uniform random variables and it stuck in my mind because it's the special case of a more general problem:

Given the hyperplane cut of $$[-1,1]^N$$,$$H_{N}=\{\vec{x} \in [-1,1]^N:\sum_{i=1}^N x_i = 0\}$$, what is the vertex set of $$H_N$$?

which reduces to the original question when $$N \in 2\mathbb{N}$$.

## My conjecture for this problem:

I conjecture that:

$$\begin{equation} V_{2N}=\{\vec{x} \in \{-1,+1\}^{2N}:\sum_{i=1}^{2N} x_i = 0\} \tag{1} \end{equation}$$

is the smallest set such that $$\mathrm{conv}(V_{2N})=H_{2N}$$ where we note that:

$$\begin{equation} \lvert V_{2N} \rvert= {2N \choose N} \tag{2} \end{equation}$$

and it's relatively easy to show that:

$$\begin{equation} \mathrm{conv}(V_{2N}) \subset H_{2N} \tag{3} \end{equation}$$

So far I haven't managed to show that $$\mathrm{conv}(V_{2N}) = H_{2N}$$ but I have managed to show that if we define:

$$\begin{equation} \forall k < N, V_{2k}=\{\vec{x} \in H_{2N}:\sum_{i \in \Gamma} x_i = \sum_{j \notin \Gamma} \lvert x_j \rvert = 0 \land \{x_i\}_{i \in \Gamma} \in \{-1,+1\}^{2k} \} \tag{4} \end{equation}$$

then we have:

$$\begin{equation} \forall k < N-1, \mathrm{conv}(V_{2k}) \subset \mathrm{conv}(V_{2k+2}) \tag{5} \end{equation}$$

I have spent some time thinking about this problem and at this point I'm not sure how to proceed. The challenge is basically to show that $$V_{2N}$$ is the vertex set of $$H_{2N}$$.

• You should consider the extreme points as, if $C$ is a convex body and $x\in EP(C)$ (its extreme points) $C\setminus \{x\}$ is convex, therefore $EP(C)\subset S$. Jul 5, 2019 at 8:34
• Insight : It seems to me that, if $C$ is intersection of closed half-spaces and bounded, then $S=EP(C)$, but I didn't check this formally. Jul 5, 2019 at 9:14
• @DuchampGérardH.E. Thank you for sharing these insights. I suspect that your last point is true and I'm currently thinking about a proof. Jul 5, 2019 at 9:56
• Good Luck ! Do not hesitate to interact anyway. Jul 5, 2019 at 10:16

It suffices to verify (see the comment by Duchamp Gérard H. E. and (https://en.wikipedia.org/wiki/Extreme_point)) that the set $$V_{2N}$$ is precisely the set of extreme points $${\bf EP}(H_{2N})$$ of $$H_{2N}$$. Clearly $$V_{2N} \subset {\bf EP}(H_{2N})$$. To see the converse, suppose $$x \in {\bf EP}(H_{2N})$$. Let $$\{e_j\}_{j=1}^{2N}$$ denote the standard basis vectors in $${\bf R}^{2N}$$. If there were two coordinates $$1 \le i such that $$|x_i|<1$$ and $$|x_j| <1$$, then the representation $$x=\frac{(x+\delta (e_i-e_j))+(x-\delta (e_i-e_j))}{2}$$ for small enough $$\delta$$, would show that $$x$$ is not an extreme point of $$H_{2N}$$. If precisely one index $$i \le 2N$$ satisfies $$|x_i|<1$$, then the sum $$\sum_{j \le 2N \,: \, j \ne i}x_j$$ is $$\pm 1$$, so $$x$$ could not be in $$H_{2N}$$. The only remaining possibility is that $$x \in V_{2N}.$$