Sum of products with bounded coefficients

Question

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

Answer 1

An $O(n^2 \log r)$ bound can be obtained by Bézout's lemma:

Lemma. For every integers $0 < c_i \leq n$, $\gcd(c_1,\ldots,c_r) = \sum_i m_i c_i$ for some integers $m_i$ with $|m_i| \leq n \log r$.

This lemma is obtained by recursively applying Bézout's lemma on two variables and the identity $\gcd(x_1,x_2,x_3) = \gcd(\gcd(x_1,x_2),x_3)$.

Without loss of generality assume that $\gcd(c_1,\ldots,c_r) = 1$ by dividing $\gcd(c_1,\ldots,c_r)$ on both sides of $\sum_i m_i c_i = k$. By Bézout's lemma there exists integers $m_i$ with $|m_i| \leq n \log r$ such that

$$k \cdot \sum_i m_i c_i = \sum_i (k \cdot m_i) c_i = k \cdot 1 \text,$$

by observing $k = O(n)$ we have the desired $m'_i = k \cdot m_i$ with $|m'_i| = O(n^2 \log r)$.

---

If you are searching for literature, the keyword is inhomogeneous linear Diophantine equations, that is the equation $\sum_i m_i c_i = k$ when $k = 0$. For the homogeneous one, one can obtain a linear bound on $|m_i'|$, see e.g. this or this paper. As for the inhomogeneous one, I have not yet found such a result; however this paper seems relevant.