Estimates for Bezout coefficients - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T13:37:27Z http://mathoverflow.net/feeds/question/108601 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108601/estimates-for-bezout-coefficients Estimates for Bezout coefficients Denis Osin 2012-10-02T05:32:46Z 2012-10-05T16:00:42Z <p>The answer to my question is probably well-known, but I was unable to find a reference. </p> <p>The Bezout's identity states that for any positive non-zero integers $a_1, \ldots , a_n$ there exist integers $x_1, \ldots , x_n$ such that $$a_1x_1+ \cdots + a_nx_n=gcd(a_1, \ldots, a_n) .$$ What is the best estimate for $|x_1|+\cdots + |x_n|$ in terms of $|a_1|+\cdots +|a_n|$? </p> <p>More precisely, we define $$b(a_1, \ldots , a_n) =\min\limits_{a_1x_1+ \cdots + a_nx_n=gcd(a_1, \ldots, a_n)} (|x_1|+\cdots + |x_n|)$$ and $$f(k)= \max\limits_{|a_1|+\cdots +|a_n|\le k} b(a_1, \ldots, a_n) .$$ What is known about the growth of $f(k)$?</p> <p>Here is a very particular question. It is not hard to show that $f(k)=O(k^2)$. Is there any better estimate? Does $f(k)=O(k\log k)$ hold?</p> http://mathoverflow.net/questions/108601/estimates-for-bezout-coefficients/108607#108607 Answer by Aaron Meyerowitz for Estimates for Bezout coefficients Aaron Meyerowitz 2012-10-02T06:50:51Z 2012-10-03T11:46:49Z <p>I'm sure that $2\sum|x_i| \lt \sum|a_i|$ is about best possible. That is certainly true in case $n=2.$ Then there will be two solutions with $|x_1| \le a_2$ and $|x_2|\le a_1$. They are $x_1a_1+x_2a_2=x_1^'a_1+x_2^'a_2=1$ with $|x_1|+|x_1^'|=a_2$ and $|x_2|+|x_2^'|=a_2.$ Since at least one of the $a_i$ is odd, we can't get a better result than $|x_1|+|x_2| =\lfloor \frac{a_1+a_2-1}{2}\rfloor.$ </p> <p>In the two odds case $a_1=2t-1,a_2=2t+1$ has best choices $x_1^'=t+1,x_2^'=-t$ and slightly better $x_1=-t,x_2=t-1$ with $|x_1|+|x_2|= \frac{a_1+a_2-2}{2}.$ In the even-odd case $a_1=2t+1,a_2=2$ with $x_1^{'}=-1,x_2^{'}=t+1$ and slightly better $x_1=1,x_2=-t$ has $|x_1|+|x_2|= \frac{a_1+a_2-1}{2}.$</p> <p>If we say that the $a_i$ are non-negative we can trivially make those examples work for arbitrary $n$ by setting $a_3=a_4=\cdots=a_n=0.$ But you stipulated positive. </p> <p>It is not immediately clear to me how to generalize the first example. In the second case we can take $a_1=2t+1$ but $a_2=\cdots=a_n=2$ and have $\sum|x_i| = \frac{(\sum a_i)-(2n-3)}{2}.$ A sharp conjecture is that this is best possible.</p> <p><strong>later</strong></p> <p>If a quick program I wrote is correct, then the results for $n=3$ are fairly orderly but contain some aspects which are not obvious. Usually the optimum examples for a given sum $k$ have $a_1=a_2$.The exceptions up to $k-300$ are $k=10,12,18,24$ </p> <p>For an odd sum $k=2t+1$ the unique best thing is $$k,\sum|x_i|,[[a_1,a_2,a_3],[x_1,x_2,x_3]]=2t+1,t-1,[[2,2,2t-3],[2-t,0,1]]$$. </p> <p>With that convention, here are all the even cases for $10 \le k \le 40$ </p> <p>10, 2, [[2, 3, 5], [-1, 1, 0]], [[3, 3, 4], [-1, 0, 1]]</p> <p>12, 2, [[2, 3, 7], [-1, 1, 0]], [[3, 4, 5], [0, -1, 1], [-1, 1, 0]]</p> <p>14, 4, [[3, 3, 8], [3, 0, -1]]</p> <p>16, 4, [[3, 3, 10], [-3, 0, 1]]</p> <p>18, 5, [[2, 7, 9], [-2, 2, -1]], [[5, 5, 8], [-3, 0, 2]]</p> <p>20, 6, [[3, 3, 14], [5, 0, -1]]</p> <p>22, 7, [[5, 5, 12], [5, 0, -2]]</p> <p>24, 5, [[2, 9, 13], [-2, 2, -1]], [[5, 7, 12], [3, -2, 0]], [[7, 7, 10], [3, 0, -2]]</p> <p>26, 8, [[3, 3, 20], [7, 0, -1]], [[7, 7, 12], [-5, 0, 3]]</p> <p>28, 9, [[5, 5, 18], [-7, 0, 2]]</p> <p>30, 10, [[7, 7, 16], [7, 0, -3]]</p> <p>32, 11, [[5, 5, 22], [9, 0, -2]]</p> <p>34, 11, [[9, 9, 16], [-7, 0, 4]]</p> <p>36, 9, [[11, 11, 14], [-5, 0, 4]]</p> <p>38, 13, [[5, 5, 28], [-11, 0, 2]], [[9, 9, 20], [9, 0, -4]]</p> <p>40, 14, [[7, 7, 26], [-11, 0, 3]]</p> <p>Here are all the other cases up to $k=300$ with more than one optimal solution. Only $k=24$ has more than two such.</p> <p>52, 19, [[5, 5, 42], [17, 0, -2]], [[9, 9, 34], [-15, 0, 4]]</p> <p>68, 26, [[7, 7, 54], [-23, 0, 3]], [[11, 11, 46], [21, 0, -5]]</p> <p>86, 34, [[7, 7, 72], [31, 0, -3]], [[11, 11, 64], [-29, 0, 5]]</p> <p>106, 43, [[9, 9, 88], [-39, 0, 4]], [[13, 13, 80], [37, 0, -6]]</p> <p>128, 53, [[9, 9, 110], [49, 0, -4]], [[13, 13, 102], [-47, 0, 6]]</p> <p>144, 51, [[31, 31, 82], [-37, 0, 14]], [[35, 37, 72], [34, -1, -16]]</p> <p>152, 64, [[11, 11, 130], [-59, 0, 5]], [[15, 15, 122], [57, 0, -7]]</p> <p>178, 76, [[11, 11, 156], [71, 0, -5]], [[15, 15, 148], [-69, 0, 7]]</p> <p>206, 89, [[13, 13, 180], [-83, 0, 6]], [[17, 17, 172], [81, 0, -8]]</p> <p>236, 103, [[13, 13, 210], [97, 0, -6]], [[17, 17, 202], [-95, 0, 8]]</p> <p>268, 118, [[15, 15, 238], [-111, 0, 7]], [[19, 19, 230], [109, 0, -9]]</p> http://mathoverflow.net/questions/108601/estimates-for-bezout-coefficients/108675#108675 Answer by Gerhard Paseman for Estimates for Bezout coefficients Gerhard Paseman 2012-10-02T23:41:56Z 2012-10-02T23:41:56Z <p>I won't quite satisfy Denis Osin's request, but indicate the main idea to bound the sum of the absolute value of the x's, given that k is the sum of the given positive a's, and that a dot x = 1 (leaving the case gcd > 1 to Denis).</p> <p>So pick a coefficient that is large in absolute value (assume it is x_i associated with a_i) , and then find a different large x_j with opposite sign belonging to a_j . Then x_j can be reduced by a_i and x_i enhanced by a_j, without changing the sum of 1, but possibly minimizing the sum of the absolute value of the x's, unless 2(abs(x_i) + abs(x_j)) =&lt; a_i + a_j . So I think we can get the abs(x)'s down to k/2 or lower.</p> <p>One can ask questions like "what if there is only one large x, and it belongs to the biggest a_i?" I would respond that there is something wierd going on, but that if the sum of the abs(x)'s also exceeds the sum of the a's, then there must be a lot of x's opposite in sign to the large x, and that they can share the burden of adjustment among themselves. After I recover from dental surgery, I will try firming this up if no one else has.</p> <p>Gerhard "Medication Making Mathematics More Mellow" Paseman, 2012.10.02</p> http://mathoverflow.net/questions/108601/estimates-for-bezout-coefficients/108723#108723 Answer by François Brunault for Estimates for Bezout coefficients François Brunault 2012-10-03T16:59:08Z 2012-10-05T16:00:42Z <p>We can prove $b(a_1,\ldots,a_n) \leq a_1+\cdots+a_n$ (and thus $f(k) \leq k$) by elementary means as follows.</p> <p>We may assume $\operatorname{gcd}(a_1,\ldots,a_n)=1$ and <code>$1 &lt; a_1&lt; \cdots &lt;a_n$</code>.</p> <p>Start with any Bézout identity $x_1 a_1+ \cdots + x_n a_n = 1$. Using the transformations $x_n \leftarrow x_n + ka_1, x_1 \leftarrow x_1-ka_n$, we may ensure $|x_n| \leq a_1$.</p> <p>Similarly, we ensure $|x_{n-1}| \leq a_1$, but we choose the sign of $x_{n-1}$ so that $x_{n-1} a_{n-1}$ and $x_n a_n$ have opposite signs. In this way $|x_{n-1}a_{n-1}+x_n a_n| \leq \max(|x_{n-1} a_{n-1}|,|x_n a_n|) \leq a_1 a_n$.</p> <p>Repeating the process, for each $n-2 \geq k \geq 2$, we change $x_k$ so that $|x_k| \leq a_1$ and $x_k a_k$ and $\sum_{j=k+1}^n x_j a_j$ have opposite signs. Thus $|\sum_{j=k}^n x_j a_j| \leq \max(|x_k a_k|,|\sum_{j=k+1}^n x_j a_j|) \leq a_1 a_n$.</p> <p>At the end we have <code>$|x_1 a_1| \leq 1+ |\sum_{j=2}^n x_j a_j| \leq 1+a_1 a_n&lt;a_1(1+a_n)$</code> so $|x_1| \leq a_n$ and finally $|x_1|+\cdots+|x_n| \leq a_n+(n-1)a_1 \leq a_1+\cdots+a_n$.</p> <p>I suspect that there are better bounds when $n$ is big.</p>