Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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

3 Answers 3

up vote 6 down vote accepted

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.

share|improve this answer
1  
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
1  
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
1  
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
1  
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

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

share|improve this answer
1  
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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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