# Sum of products with bounded coefficients

The following lemma is not hard to prove.

Lemma : Let $c_1 \neq c_2 \neq \dots \neq c_r \in [n]$ and $k \in [n]$. If $m_1, m_2, \dots, m_r$ are integers (some of them might be negative) such that $m_1c_1 + m_2c_2 + \dots + m_rc_r = k$, then $\exists$ integers $m'_1, m'_2, \dots,m'_r$ satisfying $m'_1c_1 + m'_2c_2 + \dots + m'_rc_r = k$ such that $|m'_1|+|m'_2|+\dots+|m'_r| \leq poly(n)$. Here $poly(n)$ means $O(n^c)$ for some positive constant $c$.

I am guessing that the above lemma is well known. I am looking for a reference of the above lemma and the best possible bound for $poly(n)$.

• You should be able to prove c <= 2. More specifically, I am having a hard time imagining a size-minimal case where any m' has size larger than n. Use literature on Bezout's theorem and the Euclidean algorithm if you need something to cite. Gerhard "Ask Me About System Design" Paseman, 2011.03.09 – Gerhard Paseman Mar 10 '11 at 4:20
• Also, there are cases where r=3 and at least one m' is \Omega(n), so I will be surprised if you find c < 1. Gerhard "Ask Me About System Design" Paseman, 2011.03.09 – Gerhard Paseman Mar 10 '11 at 4:25
• I assume you're looking for a $poly(n)$ that's uniform over all choices of $c_1,\dots,c_r$ (perhaps with $r$ fixed). Otherwise you can just write $g=\gcd\{c_1,\dots,c_r\}$, fix a solution to $m_1c_1+\cdots+m_rc_r=g$, and then scale by the integer $k/g$. – Greg Martin Mar 11 '11 at 22:10