Reading a paper by John Franks, at a certain point it is proven that $0$ is in the interior of the convex hull of $v_1, v_2, v_3, v_4$, where the $v_j$ are certain vectors in the plane with rational coordinates, that is $v_j \in \mathbb{Q}^2$ for each $j$.

The author then proceeds to claim that it is possible to solve $\sum_{j=1}^{4} a_j v_j = 0$ with certain positive integers coefficients $a_j$. It is not clear to me how that can be achieved (it might be worthy noting that I have no background in combinatorics nor convex analysis).

I started noticing that it suffices to show that it has rational solutions, which would naturally lead us to the problem of writing $0$ as a convex combination with rational coefficients, or even to the weaker (but too optimistic) possibility that $\sum_{j=1}^{4} \lambda_j b_j = 0$ for $b_j$ rational and $\sum_{j=1}^{4} \lambda_j = 1$, $\lambda_j \geq 0$, already implies $\lambda_j$ rational. A completely different, topological approach, using approximations (since the point is in the interior) could be a possibility too, but I now realize it is not such a trivial fact as it seemed in the first place. Any hints would be appreciated.

  • $\begingroup$ If $p\in C\subset \Bbb R^2$ then $p\in \partial (C)$ or $ p\in Int(C)$ but not both.... If $C$ is the convex hull of $\{v_1,v_2,v_3,v_4\}$ and $0\in C$ then whether $0\in \partial (C)$ or $0\in Int(C)$ depends on the "certain $v_1,..,v_4$" that he is taking about. For example if $v_1,...,v_4$ are the corners of a square and $v_1=0$ then $ v_1\not \in Int (C).$ $\endgroup$ – DanielWainfleet Dec 13 '17 at 21:08
  • $\begingroup$ It is already in the hypothesis that $0 \in Int (C)$, thus ruling out $v_1 = 0$. $\endgroup$ – ulilaka Dec 13 '17 at 22:15

More generally: if $0\in \mathbb{R}^m$ is in the interior of the convex hull of $n>m$ points $v_1,\dots, v_n\in \mathbb{Q}^m$, then there exist positive rational numbers $c_1,\dots, c_n$ such that $\sum_{k=1}^n c_kv_k =0$.

The proof employs a lemma of independent interest: a surjective linear map commutes with the interior of a convex body: that is, if $T:\mathbb{R}^n\to\mathbb{R}^m$ is linear and surjective, and $A\subset\mathbb{R}^n$ is convex with nonempty interior, then $\operatorname{int}(T(A)) = T(\operatorname{int}A)$. Here we have a linear map $$ T(c_1,\dots, c_n) = \sum_{k=1}^n c_kv_k $$ from $\mathbb{R}^n$ onto $\mathbb{R}^m$. (The surjectivity of $T$ follows from the fact that its range contains $0$ in its interior.)

Since $0$ is in the interior of the image of the box $A = [0,1]^n$ under $T$, it follows from the lemma that $0$ is in the image of open box $(0,1)^n$ under $T$. That is, we have positive real numbers $c_1,\dots, c_n$ such that $\sum_{k=1}^n c_kv_k =0$.

Consider the linear system $\sum_{k=1}^n t_kv_k =0$; it has rational coefficients. As usual with underdetermined linear systems, we get a formula for its general solution by designating some variables as "free", with the rest being determined by them. This formula has rational coefficients, because the coefficients come from the matrix by way of four arithmetic operations (we never leave the field of coefficients when solving a linear system). By the above, there exists a solution $c_1,\dots, c_n$ in positive real numbers. Assign to the free variables some rational values close to the corresponding values $c_k$; then the result will be a rational solution close to $c_1,\dots, c_n$, and therefore positive.

  • $\begingroup$ This is great, since also adds a lot to general culture. For the sake of completeness for future readers, I here link the proof of the aforementioned fact: math.stackexchange.com/questions/1908731/… $\endgroup$ – ulilaka May 22 '18 at 22:38

(This would have been presented as just a comment on an earlier answer if I had had the proper privilege level. Apologies for that.)

By Carathéodory's theorem there is a selection of 3 out of those 4 points for which the convex hull contains $0$. If $0$ is not an interior point of this convex hull it must be one of these 3 points or lie on a line segment that connects 2 of these points.


Assume that $0$ is in the convex hull of $v_1$, $v_2$ and $v_3$. Let us assume that these three vectors are affinely independent. Then, we need that the linear system $$ \begin{pmatrix}(v_1)_1 & (v_2)_1 &(v_3)_1 \\ (v_1)_2 & (v_2)_2 &(v_3)_2 \\ 1 & 1 & 1\end{pmatrix}\begin{pmatrix}\alpha_1 \\ \alpha_2\\\alpha_3\end{pmatrix} = \begin{pmatrix}0 \\ 0 \\ 1\end{pmatrix} $$ has a non-negative, rational solution. Since the system matrix is rational, it has a rational inverse. Hence, the unique solution of this system is rational and this unique solution are the unique convex combination coefficients.

  • $\begingroup$ This gives non-negative coefficients, what about positive ones? $\endgroup$ – user357151 Dec 14 '17 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.