Positive integer combination of non-negative integer vectors

Question

A vector of positive integer numbers with $n$ coordinates is given $a=(a_1,\ldots,a_n)$. It holds that $a_1+\cdots+a_n$ is divisible by some positive integer number $k$. I have checked many cases and arrived to the conjecture that one can always find at most $n$ vectors with $n$ non-negative integer coordinates such that in all the vectors the sum of the coordinates is exactly equal to $k$ and $a$ is represented as a positive integer combination of these vectors.

Example: $n=3$, $k=5$ and $a = (12,7,6)$, then the $3$ vectors satisfying above described property are $(2,2,1)$, $(5,0,0)$ and $(1,1,3)$, because $a = 3\cdot (2,2,1) + 1\cdot (5, 0, 0) + 1\cdot (1,1,3)$.

One can manually show that the conjecture holds for $k=2,3,4,5$ or $n=2$. It is also easy to see that only $n<k$ is an interesting case, $n\geq k$ can be reduced to the former.

Answer 1

Consider the regular (n-1)-simplex $x_1+x_2+\cdots+x_n=k$ and $x_i\geq 0$. The collection of hyperplanes $x_i=p$ where $1\le i\le n$, $p\in \mathbb Z$, partition our simplex into smaller polytopes with disjoint interiors. These polytopes are alcoved polytopes in the sense of Lam and Postnikov, and therefore have unimodular triangulations. By taking the cones over these triangulations you get a unimodular decomposition of $\mathbb N^n$ intersected with your lattice of vectors whose coordinates add to a multiple of $k$.

Answer 2

We follow Gjergji Zaimi's approach. Consider the integer points in a simplex $\Delta(n,k)$ with vertices $ke_1,\dots,ke_n$, where $e_i$ are standard basic vectors. Call a simplex formed by $n$ points $v_1,\dots,v_n\in \mathbb{Z}^n\cap \Delta(n,k)$ unimodular, if the vectors $v_i-v_j$ generate the lattice $\{(x_1,\dots,x_n):x_i\in \mathbb{Z},\sum x_i=0\}$. Note that in this case the lattice generated by $v_1,\dots,v_n$ consists of all vectors in $\mathbb{Z}^d$ with sum of coordiantes divisible by $k$.

It suffices to prove that any point $u\in \Delta(n,k)$ (not integer in general) belongs to a unimodular simplex. Indeed, applying this to a point $\frac{k}{\sum a_i}(a_1,\dots,a_n)$ we get $n$ vectors $v_1,\dots,v_n$ such that $a$ is their non-negative linear combination and belongs to a lattice generated by them. This is what we need.

We prove it by induction in $n$. Base $n=1$, say, is clear ($n=2$ and $n=3$ are also clear, by the way, in the latter case we get a triangular lattice and a large triangle partitioned by smaller triangles.) Assume that for smaller values of $n$ this is proved. Denote $u=(u_1,\dots,u_n)=m+w=(m_1,\dots,m_n)+(w_1,\dots,w_n)$, where $m_i\in \mathbb{Z},0\leqslant w_i\leqslant 1$. Then $\sum w_i=k-\sum m_i=:d$ is non-negative integer and we may solve the problem for a point $w\in \Delta(n,d)$. We prove that $w$ lies in a unimodular simplex with vertices belonging to the set $\{0,1\}^n\cap \Delta(n,d)$ (that is, all coordinates are 0'1 or 1's), again inducting in $n$ (with obvious base). If $d>n/2$, we replace $w$ to $(1-w_1,\dots,1-w_n)$ and $d$ to $n-d$. So, we may suppose that $d\leqslant n/2$. Assume that $w_1\geqslant w_2\geqslant \dots \geqslant w_n$. Denote $p=(1,\dots,1,0,\dots,0,1)\in \{0,1\}^n\cap \Delta(n,d)$. Then $$w=a_n\cdot p+(1-a_n)\cdot \frac{w-a_n\cdot p}{1-a_n}.$$ The vector $\tilde{w}:=\frac{w-a_n\cdot p}{1-a_n}$ has $n$-th coordiante equal to 0; sum of coordinates equal to $d$.Thus if we manage to prove that all coordinates are between 0 and 1, we may do induction step (since $p$ and any unimodular simplex in $\Delta(n-1,d)$ form a unimodular simplex in $\Delta(n,d)$). Clearly all coordinates of $\tilde{w}$ are non-negative, and if they are also at most 1, unless $a_d>1-a_n$. In that case we would have $$d=a_1+\dots+a_n>(1-a_n)d+a_n(n-d)=d+a_n(n-2d)\geqslant d,$$ a contradiction.

Answer 3

I still think it is inductively easy, but I will admit there is some detail involved. I will sketch some reductions which should help you make a complete proof.

One reduction is straightforward: if any of the components $a_j$ add up to $k$ or less, pick one vector with those components, farm out the rest to other components, and now with one vector you have reduced the dimension of the problem by at least one, and you can finish with a claim of induction on n. A variant on this is if one coordinate is smaller than another by a factor of (k-1) or more, use the vector (1,k-1) in the appropriate coordinates to zero out one coordinate and reduce the other one, again reducing the problem by one dimension.

Therefore, you need to handle the hard case, which is that the two smallest coordinates each have values greater than k, and also that we can't use (1,k-1) as above. Now the reduction is to show you can pick two vectors, a linear combination of which will zero out both coordinates, and now you reduce the dimension by 2 and refer to the inductive hypothesis.

So we now focus on a simpler problem: given a_1 and a_2 the smallest valued of the coordinates both greater than k, find integers c ,d , and e and find r,s and t and values x and y so that xc +yr =a_1, xd +ys = a_2, so that c+d+e=k=r+s+t and so that xe + st is not too big. If n is 4 or greater, we can likely manage the "not too big" portion by spreading e and t across several coordinates, turning these integers into integer vector components instead. So we will worry about the "not too big" condition some other time.

So to find c,d, r, and s, we will make c,d look like a scaled down version of a_1 , a_2 as best we can, take a large multiple of (c,d), and try to make up the rest with (r,s). Since we can't use (1,k-1) as above, that means (a_1,a_2) "looks like" a smaller vector, say (j,k-j), or (j,k-i). Essentially we subtract multiples of (j,k-j) from (a_1,a_2) until what remains has coordinates summing to at most k, and then we use these coordinates as our r and s, and let t take up the rest. If need be, we use parity and try to keep y=2 if we can't make y=1.

To do it carefully and make sure nothing goes wrong does require more work. However, the insight that you can reduce two dimensions at a time is one that I think helps make the proof more natural. If I can improve upon this to complete it before someone else does, I will.

Gerhard "Hand Waving To Get Airborne" Paseman, 2017.10.08.