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

  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Mar 10 '11 at 4:20
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Mar 10 '11 at 4:25
  • $\begingroup$ 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$. $\endgroup$ – Greg Martin Mar 11 '11 at 22:10

These papers may not deal with exactly this question, but with very closely related ones, and are probably worth a look:

Borosh, Flahive, Rubin, Treybig, A sharp bound for solutions of linear Diophantine equations, Proc. Amer. Math. Soc. 105 (1989), no. 4, 844–846, MR0955458 (89i:15022).

Borosh, Flahive, Treybig, Small solutions of linear Diophantine equations, Discrete Math. 58 (1986), no. 3, 215–220, MR0831816 (87e:11029).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.