10
$\begingroup$

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?

$\endgroup$
8
  • 2
    $\begingroup$ 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 $\endgroup$ Oct 2 '12 at 5:43
  • $\begingroup$ $g(k)$ is a typo for $f(k)$? $\endgroup$ Oct 2 '12 at 5:45
  • $\begingroup$ 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 $\endgroup$ Oct 2 '12 at 5:51
  • $\begingroup$ I just realized again zero is an integer. I apologize for the misdirection. Gerhard "Enlightenment Can Come With Tolerance" Paseman, 2012.10.01 $\endgroup$ Oct 2 '12 at 5:59
  • $\begingroup$ 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)$. $\endgroup$ Oct 2 '12 at 14:30
9
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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 $\endgroup$ Oct 3 '12 at 17:30
  • 1
    $\begingroup$ 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 $\endgroup$ Oct 3 '12 at 19:20
  • $\begingroup$ Great! Thanks Francois, this is exactly what I wanted. $\endgroup$
    – Denis Osin
    Oct 4 '12 at 2:26
  • 1
    $\begingroup$ 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$? $\endgroup$ Oct 5 '12 at 13:40
  • 1
    $\begingroup$ 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! $\endgroup$ Oct 5 '12 at 15:56
2
$\begingroup$

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$ one 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$ the choices are $x_1’=-1,x_2’=t+1$ and slightly better $x_1=1,x_2=-t$ with $|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]]

$\endgroup$
5
  • 1
    $\begingroup$ 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$ $\endgroup$ Oct 2 '12 at 13:27
  • $\begingroup$ 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)$. $\endgroup$ Oct 2 '12 at 14:23
  • $\begingroup$ So the maximum indeed occurs for $(a_1,a_2)=(2,2t-1)$, not for Fibonacci numbers. $\endgroup$ Oct 2 '12 at 14:33
  • $\begingroup$ Am good at coding, and am sure have it in Python. Still request code, would help as your experience can help in many ways. $\endgroup$
    – jiten
    Jan 16 at 10:52
  • $\begingroup$ @jiten I’m sure it was some quick Maple code to exhaustively run through the possibilities for small cases $\endgroup$ Jan 18 at 19:38
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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