# Positive integer combination of non-negative integer vectors

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.

• Also, we may suppose that $a$ is a positive integer linear combination of exactly $n+1$ vectors with sum of coordinates equal to $k$. Oct 8, 2017 at 21:34
• I am not sure how to interpret this problem. It seems false though. For example (240,120) is a combination of more than two vectors in more than two ways, e.g (30-t,t) for various choices of t. Perhaps more examples are needed to clarify, or show your proof for n=2. Gerhard "Maybe It's Not About Vectors" Paseman, 2017.10.08. Oct 8, 2017 at 21:34
• @GerhardPaseman: I claim that I can always find at most $n$ vectors satisfying the above described property, maybe the English in the problem statement is not perfect. Oct 8, 2017 at 21:48
• @FedorPetrov: why? Oct 8, 2017 at 21:52
• @kakia if we solve this case, we may decrease the number of vectors used in such a combination until it becomes less than $n$ Oct 8, 2017 at 22:09

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$.

• I am afraid that these planes partition it onto more complicated convex parts. Say, if $1<k<n-1$, the polytope with $\binom{n}k$ vertices $(p_1,\dots,p_n)\in \{0,1\}^n,\sum p_i=k$, is not a simplex. Oct 9, 2017 at 7:37
• @FedorPetrov, thank you, fortunately such polytopes can always be given unimodular decompositions. Oct 9, 2017 at 18:14
• Taking into account the exposition in the paper by Lam and Postnikov, I would rather stress that these polytopes are hypersimplices, and have several very specific unimodular trianglations. This is the first thing they recall, before defining alcoved polytopes. Oct 9, 2017 at 18:36
• The question states that $n \lt k$ but one could keep the restrictions on all except $p_n \in \{n-k-1,n-k\}.$ Oct 11, 2017 at 8:12

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.

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.