4
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\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
    Commented Mar 10, 2011 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
    Commented Mar 10, 2011 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
    Commented Mar 11, 2011 at 22:10

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .