Estimates for Bezout coefficients - MathOverflow

Estimates for Bezout coefficients

2012-10-02T05:32:46Z

The answer to my question is probably well-known, but I was unable to find a reference.

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|$?

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

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?

Answer by Aaron Meyerowitz for Estimates for Bezout coefficients

2012-10-02T06:50:51Z

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

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

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.

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.

later

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$

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

With that convention, here are all the even cases for $10 \le k \le 40$

10, 2, [[2, 3, 5], [-1, 1, 0]], [[3, 3, 4], [-1, 0, 1]]

12, 2, [[2, 3, 7], [-1, 1, 0]], [[3, 4, 5], [0, -1, 1], [-1, 1, 0]]

14, 4, [[3, 3, 8], [3, 0, -1]]

16, 4, [[3, 3, 10], [-3, 0, 1]]

18, 5, [[2, 7, 9], [-2, 2, -1]], [[5, 5, 8], [-3, 0, 2]]

20, 6, [[3, 3, 14], [5, 0, -1]]

22, 7, [[5, 5, 12], [5, 0, -2]]

24, 5, [[2, 9, 13], [-2, 2, -1]], [[5, 7, 12], [3, -2, 0]], [[7, 7, 10], [3, 0, -2]]

26, 8, [[3, 3, 20], [7, 0, -1]], [[7, 7, 12], [-5, 0, 3]]

28, 9, [[5, 5, 18], [-7, 0, 2]]

30, 10, [[7, 7, 16], [7, 0, -3]]

32, 11, [[5, 5, 22], [9, 0, -2]]

34, 11, [[9, 9, 16], [-7, 0, 4]]

36, 9, [[11, 11, 14], [-5, 0, 4]]

38, 13, [[5, 5, 28], [-11, 0, 2]], [[9, 9, 20], [9, 0, -4]]

40, 14, [[7, 7, 26], [-11, 0, 3]]

Here are all the other cases up to $k=300$ with more than one optimal solution. Only $k=24$ has more than two such.

52, 19, [[5, 5, 42], [17, 0, -2]], [[9, 9, 34], [-15, 0, 4]]

68, 26, [[7, 7, 54], [-23, 0, 3]], [[11, 11, 46], [21, 0, -5]]

86, 34, [[7, 7, 72], [31, 0, -3]], [[11, 11, 64], [-29, 0, 5]]

106, 43, [[9, 9, 88], [-39, 0, 4]], [[13, 13, 80], [37, 0, -6]]

128, 53, [[9, 9, 110], [49, 0, -4]], [[13, 13, 102], [-47, 0, 6]]

144, 51, [[31, 31, 82], [-37, 0, 14]], [[35, 37, 72], [34, -1, -16]]

152, 64, [[11, 11, 130], [-59, 0, 5]], [[15, 15, 122], [57, 0, -7]]

178, 76, [[11, 11, 156], [71, 0, -5]], [[15, 15, 148], [-69, 0, 7]]

206, 89, [[13, 13, 180], [-83, 0, 6]], [[17, 17, 172], [81, 0, -8]]

236, 103, [[13, 13, 210], [97, 0, -6]], [[17, 17, 202], [-95, 0, 8]]

268, 118, [[15, 15, 238], [-111, 0, 7]], [[19, 19, 230], [109, 0, -9]]

Answer by Gerhard Paseman for Estimates for Bezout coefficients

2012-10-02T23:41:56Z

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

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)) =< a_i + a_j . So I think we can get the abs(x)'s down to k/2 or lower.

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.

Gerhard "Medication Making Mathematics More Mellow" Paseman, 2012.10.02

Answer by François Brunault for Estimates for Bezout coefficients

2012-10-03T16:59:08Z

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.

We may assume $\operatorname{gcd}(a_1,\ldots,a_n)=1$ and $1 < a_1< \cdots <a_n$ .

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

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

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

At the end we have $|x_1 a_1| \leq 1+ |\sum_{j=2}^n x_j a_j| \leq 1+a_1 a_n<a_1(1+a_n)$ 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$.

I suspect that there are better bounds when $n$ is big.