<p>An $O(n^2 \log r)$ bound can be obtained by <a href="https://cstheory.stackexchange.com/questions/3444/overflow-in-extended-euclidean-algorithm/3450#3450">Bézout's lemma</a>:</p>

<blockquote>
  <p><strong>Lemma.</strong> For every integers $0 &lt; 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$.</p>
</blockquote>

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

<p>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 </p>

<p>$$k \cdot \sum_i m_i c_i = \sum_i (k \cdot m_i) c_i = k \cdot 1 \text,$$</p>

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

<hr>

<p>If you are searching for literature, the keyword is <strong>inhomogeneous linear Diophantine  equations</strong>, 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. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.9120&amp;rep=rep1&amp;type=pdf&amp;ei=OWB4TcDTFY_CvQODvfDNBQ&amp;usg=AFQjCNGX5mF3bXMd7YchFuKF9dQhpITZoQ" rel="nofollow noreferrer">this</a> or <a href="http://www.google.com.tw/url?sa=t&amp;source=web&amp;cd=4&amp;ved=0CEMQFjAD&amp;url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.94.299%26rep%3Drep1%26type%3Dpdf&amp;ei=-GV4TaakK4eOuQOklOHkBQ&amp;usg=AFQjCNGUE9C85puc38mkp3dVeIZzRirYkQ" rel="nofollow noreferrer">this paper</a>. As for the inhomogeneous one, I have not yet found such a result; however <a href="http://www.jstor.org/pss/2154384" rel="nofollow noreferrer">this paper</a> seems relevant. </p>

CC BY-SA 2.5
2011-03-10T17:45:53.633Z
Yes. I have $poly(n) = O(n^3)$. I am wondering if it is known to be $O(n^2)$.
Shiva Kintali
CC BY-SA 2.5
2011-03-10T05:02:39.207Z
2011-03-10T06:49:02.980Z
2017-04-13T12:32:28.117Z
Hsien-Chih Chang 張顯之
<p>The following lemma is not hard to prove.</p>

<p><strong>Lemma</strong> : 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&#39;_1, m&#39;_2, \dots,m&#39;_r$ satisfying $m&#39;_1c_1 + m&#39;_2c_2 + \dots + m&#39;_rc_r = k$ such that $|m&#39;_1|+|m&#39;_2|+\dots+|m&#39;_r| \leq poly(n)$. Here $poly(n)$ means $n^c$ for some positive constant $c$.</p>

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

CC BY-SA 2.5
2011-03-10T04:16:34.020Z
Crosspost at MathOverflow: http://mathoverflow.net/questions/58034/sum-of-products-with-bounded-coefficients
Hsien-Chih Chang 張顯之
<reference-request><nt.number-theory>
Sum of products with bounded coefficients
Shiva Kintali
# Sum of products with bounded coefficients

(Asked by: username_0 on 2011-03-10)

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

**Tags:** reference-request, nt.number-theory
> **Comments:**
> **username_1**: Crosspost at MathOverflow: http://mathoverflow.net/questions/58034/sum-of-products-with-bounded-coefficients  

---

## 1 answers

### Answer by username_1 on 2011-03-10. Score: 5 | Accepted answer

An $O(n^2 \log r)$ bound can be obtained by [Bézout's lemma](https://cstheory.stackexchange.com/questions/3444/overflow-in-extended-euclidean-algorithm/3450#3450):

> **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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.9120&rep=rep1&type=pdf&ei=OWB4TcDTFY_CvQODvfDNBQ&usg=AFQjCNGX5mF3bXMd7YchFuKF9dQhpITZoQ) or [this paper](http://www.google.com.tw/url?sa=t&source=web&cd=4&ved=0CEMQFjAD&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.94.299%26rep%3Drep1%26type%3Dpdf&ei=-GV4TaakK4eOuQOklOHkBQ&usg=AFQjCNGUE9C85puc38mkp3dVeIZzRirYkQ). As for the inhomogeneous one, I have not yet found such a result; however [this paper](http://www.jstor.org/pss/2154384) seems relevant.

> **Comments:**
> **username_0**: Yes. I have $poly(n) = O(n^3)$. I am wondering if it is known to be $O(n^2)$.  

---

