# How to know if convex-hull of a set contains zero?

Let $(\lambda_1 , \cdots , \lambda_d) \vdash k$ be a partition of $k$ of length $d$. Is there any way to decide if $0 \in \text{Conv}\{(\underbrace{\alpha_1, \cdots, \alpha_1}_{\lambda_1}, \cdots , \underbrace{\alpha_d , \cdots, \alpha_d}_{\lambda_d}) \in \mathbb{Z}^k: \, (\alpha_1, \cdots , \alpha_d) \in \mathbb{Z}^d,\, \sum_{i=1}^d \alpha_i = 0\}$, where not all $\alpha_i$s are zero?

• I don't understand what the set is of which you're taking the convex hull. The way it's written now it seems like the set is $\{\lambda_i\alpha_i:i=1,\ldots,d\}$ which is a set of integers, not a set of points in $\mathbb{Z}^d$. – Yoav Kallus Aug 11 '17 at 17:33
• Sorry for that! I rewrote it and hopefully it is clear now. – SMD Aug 11 '17 at 17:57
• Convex combination preserves the property that the first $\lambda_1$ coordinates are the same, etc. That is, if all the $\lambda_i$ are positive, the question is equivalent to simply if $0\in\mathrm{Conv}\{(\alpha_1,\dots,\alpha_d)\in\mathbb Z^d:\sum_{i=1}^d\alpha_i=0\}$. Either way, the answer is trivially yes, as $0$ (by which I assume you mean $(0,\dots,0)$) is already in the given set. Or am I missing something? – Emil Jeřábek Aug 11 '17 at 18:14
• OK, the new formulation parses, but also seems like it must be wrong. $0\in\mathbb{Z}^k$ is a point of the set, so obviously it is in its convex hull. – Yoav Kallus Aug 11 '17 at 18:14
• I am sorry guys! Added one more edit. In fact, we know that $\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_d$. – SMD Aug 11 '17 at 18:26

Like Emil noted in the comments, the question is equivalent to whether $0\in\mathrm{Conv}(\{\alpha\in\mathbb{Z}^d: \sum_{i=1}^{d}\alpha_i=0\}\setminus\{0\})$. To see that it is, note that it is the average of $(d-1,-1,-1,\ldots,-1)$ and its permutations.
Given $n$ points $x_i \in \mathbb R^d$, $0$ is in their convex hull iff there is no $y \in \mathbb R^d$ such that $y \cdot x_i \ge 1$ for all $i$. You can use linear programming software to check this.