Geometry of the minimal solutions of a linear Diophantine Equation

Abstract

Let $a_1,\dots ,a_n$ and $b_1,\dots ,b_m$ be fixed positive integers, and let $\mathcal{S}$ denote the set of all nonnegative integer solutions of the equation $x_1{a}_1+\dots +x_n{a}_n=y_1{b}_1+\dots +y_m{b}_m$. A solution $(x_1,\dots ,x_n,y_1,\dots ,y_m)$ in $\mathcal{S}$ is called $\text{minimal}$ if it cannot be expressed as the sum of two nonzero solutions in $\mathcal{S}$. For each pair $(i,j)$ with $1\le i\le n$ and $1\le j\le m$, the solution whose only nonzero coordinates are $x_i=b_j$ and $y_j=a_i$ is called a $\text{generator}$. Our main result shows that every minimal solution is a convex combination of the generators and the zero-solution. This proves a conjecture of Henk-Weismantel and, independently, Hoşten-Sturmfels.

arXiv comment12 pages; To appear in SIAM J. Discrete Math