# Estimates for Bezout coefficients

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?

-
For n=2, I suspect the maximum will occur near consecutive Fibonacci numbers. Perhaps Fibonacci will be useful for larger n. Also, it helps to assume the gcd is 1. Gerhard "Ask Me About System Design" Paseman, 2012.10.01 –  Gerhard Paseman Oct 2 '12 at 5:43
$g(k)$ is a typo for $f(k)$? –  Gerry Myerson Oct 2 '12 at 5:45
Actually, it seems (1,a) does a better job for n=2, if the coefficients are added. I suspect something similar (perhaps (1,a,...,a)?) happens for larger n. Gerhard "Wait For A Third Comment" Paseman, 2012.10.01 –  Gerhard Paseman Oct 2 '12 at 5:51
I just realized again zero is an integer. I apologize for the misdirection. Gerhard "Enlightenment Can Come With Tolerance" Paseman, 2012.10.01 –  Gerhard Paseman Oct 2 '12 at 5:59
In the case $n=2$, we can always choose $|x_1| \leq |a_2|$ and $|x_2| \leq |a_1|$. This shows that $f(k)=O(k)$. –  François Brunault Oct 2 '12 at 14:30

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.

-
You can tweak the above to get abs(x_i) < (a_1)/2 for all i > 1, ignoring the signs, and then observe that the last coefficient must be about half the sum of the other a_i's. Gerhard "Thanks For Finishing The Job" Paseman, 2012.10.03 –  Gerhard Paseman Oct 3 '12 at 17:30
The literature on the Frobenius coin problem may also have some ideas. Further, one might get even nicer results when n is much greater than a_1, for example. Gerhard "Ask Me About System Design" Paseman, 2012.10.03 –  Gerhard Paseman Oct 3 '12 at 19:20
Great! Thanks Francois, this is exactly what I wanted. –  Denis Osin Oct 4 '12 at 2:26
I must be missing something. If I make $|x_i|\le a_1/2$ for each $i>1$ as indicated, then $|x_1|=|1-\sum_{i>1}a_ix_i|/a_1\le 1/a_1+\sum_{i>1}a_i/2$, hence $\sum_i|x_i|\le 1/a_1+\sum_{i>1}a_i/2+(n-1)a_1/2$. How is this bounded by $k/2$? –  Emil Jeřábek Oct 5 '12 at 13:40
Actually, I'm not sure anymore I can strengthen the inequality to $b(a_1,\ldots,a_n) \leq (a_1+\cdots+a_n)/2$. The point is that I'm not allowed to change the signs of $x_i$ since this destroys the Bézout identity. At least I'm sure that $b(a_1,\ldots,a_n) \leq a_1+\cdots+a_n$. Sorry! –  François Brunault Oct 5 '12 at 15:56
show 1 more comment

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

-
I fixed the $a$ and $x$ problem. $21\cdot 5+13\cdot (-8)=1$ is not as dramatic as $17\cdot 9 +19\cdot (-8)=1$ for $a_1+a_2=34$ –  Aaron Meyerowitz Oct 2 '12 at 13:27
Indeed, if $(a_1,a_2)$ are consecutive Fibonacci numbers $(F_n,F_{n+1})$ then we get $b(a_1,a_2) = F_{n-2}+F_{n-1} \sim \frac{1}{\phi^2} (a_1+a_2)$ with $\phi = \frac{1+\sqrt{5}}{2}$, which is less than $\frac12(a_1+a_2)$. –  François Brunault Oct 2 '12 at 14:23
So the maximum indeed occurs for $(a_1,a_2)=(2,2t-1)$, not for Fibonacci numbers. –  François Brunault Oct 2 '12 at 14:33